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 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
 291bool 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). */
 321void 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
 361void 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 */
 388void 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}
 401