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