akaros/kern/src/alarm.c
<<
>>
Prefs
   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. */
  27static 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() */
  41void 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
  51void 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. */
  62void 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. */
  69void 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. */
  84void 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. */
  92static 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
 108static 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. */
 157void __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. */
 165static 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. */
 210void 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. */
 224static 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. */
 251bool 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
 280bool unset_alarm_nosync(struct timer_chain *tchain, struct alarm_waiter *waiter)
 281{
 282        bool ret = false;
 283
 284        spin_lock_irqsave(&tchain->lock);
 285        if (waiter->on_tchain) {
 286                if (__remove_awaiter(tchain, waiter))
 287                        reset_tchain_interrupt(tchain);
 288                ret = true;
 289        }
 290        spin_unlock_irqsave(&tchain->lock);
 291        return ret;
 292}
 293
 294bool reset_alarm_abs(struct timer_chain *tchain, struct alarm_waiter *waiter,
 295                     uint64_t abs_time)
 296{
 297        bool ret;
 298
 299        ret = unset_alarm_nosync(tchain, waiter);
 300        set_awaiter_abs(waiter, abs_time);
 301        set_alarm(tchain, waiter);
 302        return ret;
 303}
 304
 305bool reset_alarm_rel(struct timer_chain *tchain, struct alarm_waiter *waiter,
 306                     uint64_t usleep)
 307{
 308        bool ret;
 309
 310        ret = unset_alarm_nosync(tchain, waiter);
 311        set_awaiter_rel(waiter, usleep);
 312        set_alarm(tchain, waiter);
 313        return ret;
 314}
 315
 316/* Sets the timer interrupt for the timer chain passed as parameter.
 317 * The next interrupt will be scheduled at the nearest timer available in the
 318 * chain.
 319 * This function can be called either for the local CPU, or for a remote CPU.
 320 * If called for the local CPU, it proceeds in setting up the local timer,
 321 * otherwise it will trigger an IPI, and will let the remote CPU IRQ handler
 322 * to setup the timer according to the active information on its timer chain.
 323 *
 324 * Needs to set the interrupt to trigger tchain at the given time, or disarm it
 325 * if time is 0.   Any function like this needs to do a few things:
 326 *      - Make sure the interrupt is on and will go off when we want
 327 *      - Make sure the interrupt source can find tchain
 328 *      - Make sure the interrupt handler calls __trigger_tchain(tchain)
 329 *      - Make sure you don't clobber an old tchain here (a bug)
 330 * This implies the function knows how to find its timer source/void
 331 *
 332 * Called with the tchain lock held, and IRQs disabled.  However, we could be
 333 * calling this cross-core, and we cannot disable those IRQs (hence the
 334 * locking). */
 335void set_pcpu_alarm_interrupt(struct timer_chain *tchain)
 336{
 337        uint64_t time, rel_usec, now;
 338        int pcoreid = core_id();
 339        struct per_cpu_info *rem_pcpui, *pcpui = &per_cpu_info[pcoreid];
 340        struct timer_chain *pcpui_tchain = &pcpui->tchain;
 341
 342        if (pcpui_tchain != tchain) {
 343                /* cross-core call.  we can simply send an alarm IRQ.  the alarm
 344                 * handler will reset its pcpu timer, based on its current
 345                 * lists.  they take an extra IRQ, but it gets the job done. */
 346                rem_pcpui = (struct per_cpu_info*)((uintptr_t)tchain -
 347                                    offsetof(struct per_cpu_info, tchain));
 348                /* TODO: using the LAPIC vector is a bit ghetto, since that's
 349                 * x86.  But RISCV ignores the vector field, and we don't have a
 350                 * global IRQ vector namespace or anything. */
 351                send_ipi(rem_pcpui - &per_cpu_info[0], IdtLAPIC_TIMER);
 352                return;
 353        }
 354        time = TAILQ_EMPTY(&tchain->waiters) ? 0 : tchain->earliest_time;
 355        if (time) {
 356                /* Arm the alarm.  For times in the past, we just need to make
 357                 * sure it goes off. */
 358                now = read_tsc();
 359                if (time <= now)
 360                        rel_usec = 1;
 361                else
 362                        rel_usec = tsc2usec(time - now);
 363                rel_usec = MAX(rel_usec, 1);
 364                printd("Setting alarm for %llu, it is now %llu, rel_time %llu "
 365                       "tchain %p\n", time, now, rel_usec, pcpui_tchain);
 366                set_core_timer(rel_usec, FALSE);
 367        } else  {
 368                /* Disarm */
 369                set_core_timer(0, FALSE);
 370        }
 371}
 372
 373/* Debug helpers */
 374
 375void print_chain(struct timer_chain *tchain)
 376{
 377        struct alarm_waiter *i;
 378        struct timespec x = {0}, y = {0};
 379
 380        spin_lock_irqsave(&tchain->lock);
 381        if (TAILQ_EMPTY(&tchain->waiters)) {
 382                printk("Chain %p is empty\n", tchain);
 383                spin_unlock_irqsave(&tchain->lock);
 384                return;
 385        }
 386        x = tsc2timespec(tchain->earliest_time);
 387        y = tsc2timespec(tchain->latest_time);
 388        printk("Chain %p:  earliest: [%7d.%09d] latest: [%7d.%09d]\n",
 389               tchain, x.tv_sec, x.tv_nsec, y.tv_sec, y.tv_nsec);
 390        TAILQ_FOREACH(i, &tchain->waiters, next) {
 391                uintptr_t f = (uintptr_t)i->func;
 392
 393                x = tsc2timespec(i->wake_up_time);
 394                printk("\tWaiter %p, time [%7d.%09d] (%p), func %p (%s)\n",
 395                       i, x.tv_sec, x.tv_nsec, i->wake_up_time, f,
 396                       get_fn_name(f));
 397        }
 398        spin_unlock_irqsave(&tchain->lock);
 399}
 400
 401/* Prints all chains, rather verbosely */
 402void print_pcpu_chains(void)
 403{
 404        struct timer_chain *pcpu_chain;
 405        struct timespec ts;
 406
 407        ts = tsc2timespec(read_tsc());
 408        printk("PCPU Chains:  It is now [%7d.%09d]\n", ts.tv_sec, ts.tv_nsec);
 409
 410        for (int i = 0; i < num_cores; i++) {
 411                pcpu_chain = &per_cpu_info[i].tchain;
 412                print_chain(pcpu_chain);
 413        }
 414}
 415