alarm: Force unset_alarm to grab the CV lock
[akaros.git] / kern / src / alarm.c
1 /* Copyright (c) 2011 The Regents of the University of California
2  * Barret Rhoden <brho@cs.berkeley.edu>
3  * See LICENSE for details.
4  *
5  * Alarms.  This includes ways to defer work on a specific timer.  These can be
6  * per-core, global or whatever.  Like with most systems, you won't wake up til
7  * after the time you specify. (for now, this might change).
8  *
9  * TODO:
10  *      - have a kernel sense of time, instead of just the TSC or whatever timer the
11  *      chain uses...
12  *      - coalesce or otherwise deal with alarms that are close to cut down on
13  *      interrupt overhead. */
14
15 #include <ros/common.h>
16 #include <sys/queue.h>
17 #include <kthread.h>
18 #include <alarm.h>
19 #include <stdio.h>
20 #include <smp.h>
21 #include <kmalloc.h>
22
23 /* Helper, resets the earliest/latest times, based on the elements of the list.
24  * If the list is empty, we set the times to be the 12345 poison time.  Since
25  * the list is empty, the alarm shouldn't be going off. */
26 static void reset_tchain_times(struct timer_chain *tchain)
27 {
28         if (TAILQ_EMPTY(&tchain->waiters)) {
29                 tchain->earliest_time = ALARM_POISON_TIME;
30                 tchain->latest_time = ALARM_POISON_TIME;
31         } else {
32                 tchain->earliest_time = TAILQ_FIRST(&tchain->waiters)->wake_up_time;
33                 tchain->latest_time =
34                         TAILQ_LAST(&tchain->waiters, awaiters_tailq)->wake_up_time;
35         }
36 }
37
38 /* One time set up of a tchain, currently called in per_cpu_init() */
39 void init_timer_chain(struct timer_chain *tchain,
40                       void (*set_interrupt)(struct timer_chain *))
41 {
42         spinlock_init_irqsave(&tchain->lock);
43         TAILQ_INIT(&tchain->waiters);
44         tchain->set_interrupt = set_interrupt;
45         reset_tchain_times(tchain);
46 }
47
48 static void __init_awaiter(struct alarm_waiter *waiter)
49 {
50         waiter->wake_up_time = ALARM_POISON_TIME;
51         waiter->on_tchain = false;
52         waiter->is_running = false;
53         waiter->no_rearm = false;
54         cv_init_irqsave(&waiter->done_cv);
55 }
56
57 void init_awaiter(struct alarm_waiter *waiter,
58                   void (*func) (struct alarm_waiter *awaiter))
59 {
60         waiter->irq_ok = FALSE;
61         assert(func);
62         waiter->func = func;
63         __init_awaiter(waiter);
64 }
65
66 void init_awaiter_irq(struct alarm_waiter *waiter,
67                       void (*func_irq) (struct alarm_waiter *awaiter,
68                                         struct hw_trapframe *hw_tf))
69 {
70         waiter->irq_ok = TRUE;
71         assert(func_irq);
72         waiter->func_irq = func_irq;
73         __init_awaiter(waiter);
74 }
75
76 /* Give this the absolute time.  For now, abs_time is the TSC time that you want
77  * the alarm to go off. */
78 void set_awaiter_abs(struct alarm_waiter *waiter, uint64_t abs_time)
79 {
80         waiter->wake_up_time = abs_time;
81 }
82
83 /* Give this a relative time from now, in microseconds.  This might be easier to
84  * use than dealing with the TSC. */
85 void set_awaiter_rel(struct alarm_waiter *waiter, uint64_t usleep)
86 {
87         uint64_t now, then;
88         now = read_tsc();
89         then = now + usec2tsc(usleep);
90         /* This will go off if we wrap-around the TSC.  It'll never happen for legit
91          * values, but this might catch some bugs with large usleeps. */
92         assert(now <= then);
93         set_awaiter_abs(waiter, then);
94 }
95
96 /* Increment the timer that was already set, so that it goes off usleep usec
97  * from the previous tick.  This is different than 'rel' in that it doesn't care
98  * about when 'now' is. */
99 void set_awaiter_inc(struct alarm_waiter *waiter, uint64_t usleep)
100 {
101         assert(waiter->wake_up_time != ALARM_POISON_TIME);
102         waiter->wake_up_time += usec2tsc(usleep);
103 }
104
105 /* Helper, makes sure the interrupt is turned on at the right time.  Most of the
106  * heavy lifting is in the timer-source specific function pointer. */
107 static void reset_tchain_interrupt(struct timer_chain *tchain)
108 {
109         assert(!irq_is_enabled());
110         if (TAILQ_EMPTY(&tchain->waiters)) {
111                 /* Turn it off */
112                 printd("Turning alarm off\n");
113                 tchain->set_interrupt(tchain);
114         } else {
115                 /* Make sure it is on and set to the earliest time */
116                 assert(tchain->earliest_time != ALARM_POISON_TIME);
117                 /* TODO: check for times in the past or very close to now */
118                 printd("Turning alarm on for %llu\n", tchain->earliest_time);
119                 tchain->set_interrupt(tchain);
120         }
121 }
122
123 static void __finish_awaiter(struct alarm_waiter *waiter)
124 {
125         int8_t irq_state = 0;
126
127         /* Syncing with unset_alarm.  They are waiting for us to tell them the
128          * waiter is not running.
129          *
130          * 'is_running' is set true under the tchain lock.  It's checked and cleared
131          * under the cv_lock, but not necessarily with the tchain lock. */
132         cv_lock_irqsave(&waiter->done_cv, &irq_state);
133         waiter->is_running = false;
134         /* broadcast, instead of signal.  This allows us to have multiple unsetters
135          * concurrently.  (only one of which will succeed, so YMMV.) */
136         __cv_broadcast(&waiter->done_cv);
137         cv_unlock_irqsave(&waiter->done_cv, &irq_state);
138 }
139
140 static void __run_awaiter(uint32_t srcid, long a0, long a1, long a2)
141 {
142         struct alarm_waiter *waiter = (struct alarm_waiter*)a0;
143
144         waiter->func(waiter);
145         __finish_awaiter(waiter);
146 }
147
148 static void wake_awaiter(struct alarm_waiter *waiter,
149                          struct hw_trapframe *hw_tf)
150 {
151         if (waiter->irq_ok) {
152                 waiter->func_irq(waiter, hw_tf);
153                 __finish_awaiter(waiter);
154         } else {
155                 send_kernel_message(core_id(), __run_awaiter, (long)waiter,
156                                     0, 0, KMSG_ROUTINE);
157         }
158 }
159
160 /* This is called when an interrupt triggers a tchain, and needs to wake up
161  * everyone whose time is up.  Called from IRQ context. */
162 void __trigger_tchain(struct timer_chain *tchain, struct hw_trapframe *hw_tf)
163 {
164         struct alarm_waiter *i, *temp;
165         uint64_t now = read_tsc();
166         struct awaiters_tailq to_wake = TAILQ_HEAD_INITIALIZER(to_wake);
167
168         spin_lock_irqsave(&tchain->lock);
169         TAILQ_FOREACH_SAFE(i, &tchain->waiters, next, temp) {
170                 printd("Trying to wake up %p who is due at %llu and now is %llu\n",
171                        i, i->wake_up_time, now);
172                 /* TODO: Could also do something in cases where we're close to now */
173                 if (i->wake_up_time > now)
174                         break;
175                 /* At this point, unset must wait until it has finished */
176                 i->on_tchain = false;
177                 i->is_running = true;
178                 TAILQ_REMOVE(&tchain->waiters, i, next);
179                 TAILQ_INSERT_TAIL(&to_wake, i, next);
180         }
181         reset_tchain_times(tchain);
182         reset_tchain_interrupt(tchain);
183         spin_unlock_irqsave(&tchain->lock);
184
185         TAILQ_FOREACH_SAFE(i, &to_wake, next, temp) {
186                 /* Don't touch the waiter after waking it, since it could be in use on
187                  * another core (and the waiter can be clobbered as the kthread unwinds
188                  * its stack).  Or it could be kfreed.  Technically, the waiter hasn't
189                  * finished until we cleared is_running and unlocked the cv lock. */
190                 TAILQ_REMOVE(&to_wake, i, next);
191                 wake_awaiter(i, hw_tf);
192         }
193 }
194
195 /* Helper, inserts the waiter into the tchain, returning TRUE if we still need
196  * to reset the tchain interrupt.  Caller holds the lock. */
197 static bool __insert_awaiter(struct timer_chain *tchain,
198                              struct alarm_waiter *waiter)
199 {
200         struct alarm_waiter *i, *temp;
201
202         waiter->on_tchain = TRUE;
203         /* Either the list is empty, or not. */
204         if (TAILQ_EMPTY(&tchain->waiters)) {
205                 tchain->earliest_time = waiter->wake_up_time;
206                 tchain->latest_time = waiter->wake_up_time;
207                 TAILQ_INSERT_HEAD(&tchain->waiters, waiter, next);
208                 /* Need to turn on the timer interrupt later */
209                 return TRUE;
210         }
211         /* If not, either we're first, last, or in the middle.  Reset the interrupt
212          * and adjust the tchain's times accordingly. */
213         if (waiter->wake_up_time < tchain->earliest_time) {
214                 tchain->earliest_time = waiter->wake_up_time;
215                 TAILQ_INSERT_HEAD(&tchain->waiters, waiter, next);
216                 /* Changed the first entry; we'll need to reset the interrupt later */
217                 return TRUE;
218         }
219         /* If there is a tie for last, the newer one will really go last.  We need
220          * to handle equality here since the loop later won't catch it. */
221         if (waiter->wake_up_time >= tchain->latest_time) {
222                 tchain->latest_time = waiter->wake_up_time;
223                 /* Proactively put it at the end if we know we're last */
224                 TAILQ_INSERT_TAIL(&tchain->waiters, waiter, next);
225                 return FALSE;
226         }
227         /* Insert before the first one you are earlier than.  This won't scale well
228          * (TODO) if we have a lot of inserts.  The proactive insert_tail up above
229          * will help a bit. */
230         TAILQ_FOREACH_SAFE(i, &tchain->waiters, next, temp) {
231                 if (waiter->wake_up_time < i->wake_up_time) {
232                         TAILQ_INSERT_BEFORE(i, waiter, next);
233                         return FALSE;
234                 }
235         }
236         panic("Could not find a spot for awaiter %p\n", waiter);
237 }
238
239 /* Sets the alarm.  If it is a kthread-style alarm (func == 0), sleep on it
240  * later. */
241 void set_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter)
242 {
243         assert(waiter->wake_up_time != ALARM_POISON_TIME);
244         assert(!waiter->on_tchain);
245
246         spin_lock_irqsave(&tchain->lock);
247         if (waiter->no_rearm) {
248                 /* no_rearm exists to prevent alarm handlers from perpetually rearming
249                  * when another thread is trying to unset the alarm.  We could return an
250                  * error / false, but I don't have a use for that yet. */
251                 spin_unlock_irqsave(&tchain->lock);
252                 return;
253         }
254         if (__insert_awaiter(tchain, waiter))
255                 reset_tchain_interrupt(tchain);
256         spin_unlock_irqsave(&tchain->lock);
257 }
258
259 /* Helper, rips the waiter from the tchain, knowing that it is on the list.
260  * Returns TRUE if the tchain interrupt needs to be reset.  Callers hold the
261  * lock. */
262 static bool __remove_awaiter(struct timer_chain *tchain,
263                              struct alarm_waiter *waiter)
264 {
265         struct alarm_waiter *temp;
266         bool reset_int = FALSE;         /* whether or not to reset the interrupt */
267
268         /* Need to make sure earliest and latest are set, in case we're mucking with
269          * the first and/or last element of the chain. */
270         if (TAILQ_FIRST(&tchain->waiters) == waiter) {
271                 temp = TAILQ_NEXT(waiter, next);
272                 tchain->earliest_time = (temp) ? temp->wake_up_time : ALARM_POISON_TIME;
273                 reset_int = TRUE;               /* we'll need to reset the timer later */
274         }
275         if (TAILQ_LAST(&tchain->waiters, awaiters_tailq) == waiter) {
276                 temp = TAILQ_PREV(waiter, awaiters_tailq, next);
277                 tchain->latest_time = (temp) ? temp->wake_up_time : ALARM_POISON_TIME;
278         }
279         TAILQ_REMOVE(&tchain->waiters, waiter, next);
280         waiter->on_tchain = FALSE;
281         return reset_int;
282 }
283
284 /* Removes waiter from the tchain before it goes off.  Returns TRUE if we
285  * disarmed before the alarm went off, FALSE if it already fired.  May block,
286  * since the handler may be running asynchronously. */
287 bool unset_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter)
288 {
289         int8_t irq_state = 0;
290
291         spin_lock_irqsave(&tchain->lock);
292         if (waiter->on_tchain) {
293                 if (__remove_awaiter(tchain, waiter))
294                         reset_tchain_interrupt(tchain);
295                 spin_unlock_irqsave(&tchain->lock);
296                 return true;
297         }
298
299         /* no_rearm is set and checked under the tchain lock.  It is cleared when
300          * unset completes, outside the lock.  That is safe since we know the alarm
301          * service is no longer aware of waiter (either the handler ran or we
302          * stopped it). */
303         waiter->no_rearm = true;
304         spin_unlock_irqsave(&tchain->lock);
305
306         cv_lock_irqsave(&waiter->done_cv, &irq_state);
307         while (waiter->is_running)
308                 cv_wait(&waiter->done_cv);
309         cv_unlock_irqsave(&waiter->done_cv, &irq_state);
310
311         waiter->no_rearm = false;
312         return false;
313 }
314
315 bool reset_alarm_abs(struct timer_chain *tchain, struct alarm_waiter *waiter,
316                      uint64_t abs_time)
317 {
318         bool ret;
319
320         ret = unset_alarm(tchain, waiter);
321         set_awaiter_abs(waiter, abs_time);
322         set_alarm(tchain, waiter);
323         return ret;
324 }
325
326 bool reset_alarm_rel(struct timer_chain *tchain, struct alarm_waiter *waiter,
327                      uint64_t usleep)
328 {
329         bool ret;
330
331         ret = unset_alarm(tchain, waiter);
332         set_awaiter_rel(waiter, usleep);
333         set_alarm(tchain, waiter);
334         return ret;
335 }
336
337 /* Sets the timer interrupt for the timer chain passed as parameter.
338  * The next interrupt will be scheduled at the nearest timer available in the
339  * chain.
340  * This function can be called either for the local CPU, or for a remote CPU.
341  * If called for the local CPU, it proceeds in setting up the local timer,
342  * otherwise it will trigger an IPI, and will let the remote CPU IRQ handler
343  * to setup the timer according to the active information on its timer chain.
344  *
345  * Needs to set the interrupt to trigger tchain at the given time, or disarm it
346  * if time is 0.   Any function like this needs to do a few things:
347  *      - Make sure the interrupt is on and will go off when we want
348  *      - Make sure the interrupt source can find tchain
349  *      - Make sure the interrupt handler calls __trigger_tchain(tchain)
350  *      - Make sure you don't clobber an old tchain here (a bug)
351  * This implies the function knows how to find its timer source/void
352  *
353  * Called with the tchain lock held, and IRQs disabled.  However, we could be
354  * calling this cross-core, and we cannot disable those IRQs (hence the
355  * locking). */
356 void set_pcpu_alarm_interrupt(struct timer_chain *tchain)
357 {
358         uint64_t time, rel_usec, now;
359         int pcoreid = core_id();
360         struct per_cpu_info *rem_pcpui, *pcpui = &per_cpu_info[pcoreid];
361         struct timer_chain *pcpui_tchain = &pcpui->tchain;
362
363         if (pcpui_tchain != tchain) {
364                 /* cross-core call.  we can simply send an alarm IRQ.  the alarm handler
365                  * will reset its pcpu timer, based on its current lists.  they take an
366                  * extra IRQ, but it gets the job done. */
367                 rem_pcpui = (struct per_cpu_info*)((uintptr_t)tchain -
368                                     offsetof(struct per_cpu_info, tchain));
369                 /* TODO: using the LAPIC vector is a bit ghetto, since that's x86.  But
370                  * RISCV ignores the vector field, and we don't have a global IRQ vector
371                  * namespace or anything. */
372                 send_ipi(rem_pcpui - &per_cpu_info[0], IdtLAPIC_TIMER);
373                 return;
374         }
375         time = TAILQ_EMPTY(&tchain->waiters) ? 0 : tchain->earliest_time;
376         if (time) {
377                 /* Arm the alarm.  For times in the past, we just need to make sure it
378                  * goes off. */
379                 now = read_tsc();
380                 if (time <= now)
381                         rel_usec = 1;
382                 else
383                         rel_usec = tsc2usec(time - now);
384                 rel_usec = MAX(rel_usec, 1);
385                 printd("Setting alarm for %llu, it is now %llu, rel_time %llu "
386                        "tchain %p\n", time, now, rel_usec, pcpui_tchain);
387                 set_core_timer(rel_usec, FALSE);
388         } else  {
389                 /* Disarm */
390                 set_core_timer(0, FALSE);
391         }
392 }
393
394 /* Debug helpers */
395
396 void print_chain(struct timer_chain *tchain)
397 {
398         struct alarm_waiter *i;
399         spin_lock_irqsave(&tchain->lock);
400         printk("Chain %p is%s empty, early: %llu latest: %llu\n", tchain,
401                TAILQ_EMPTY(&tchain->waiters) ? "" : " not",
402                tchain->earliest_time,
403                tchain->latest_time);
404         TAILQ_FOREACH(i, &tchain->waiters, next) {
405                 uintptr_t f;
406
407                 if (i->irq_ok)
408                         f = (uintptr_t)i->func_irq;
409                 else
410                         f = (uintptr_t)i->func;
411                 printk("\tWaiter %p, time %llu, func %p (%s)\n", i,
412                        i->wake_up_time, f, get_fn_name(f));
413         }
414         spin_unlock_irqsave(&tchain->lock);
415 }
416
417 /* Prints all chains, rather verbosely */
418 void print_pcpu_chains(void)
419 {
420         struct timer_chain *pcpu_chain;
421         printk("PCPU Chains:  It is now %llu\n", read_tsc());
422
423         for (int i = 0; i < num_cores; i++) {
424                 pcpu_chain = &per_cpu_info[i].tchain;
425                 print_chain(pcpu_chain);
426         }
427 }