akaros/kern/src/atomic.c
<<
>>
Prefs
   1#include <arch/arch.h>
   2#include <arch/kdebug.h>
   3
   4#include <bitmask.h>
   5#include <atomic.h>
   6#include <error.h>
   7#include <string.h>
   8#include <assert.h>
   9#include <hashtable.h>
  10#include <smp.h>
  11#include <kmalloc.h>
  12#include <kdebug.h>
  13
  14static void increase_lock_depth(uint32_t coreid)
  15{
  16        per_cpu_info[coreid].lock_depth++;
  17}
  18
  19static void decrease_lock_depth(uint32_t coreid)
  20{
  21        per_cpu_info[coreid].lock_depth--;
  22}
  23
  24#ifdef CONFIG_SPINLOCK_DEBUG
  25
  26/* Put locks you want to ignore here. */
  27static uintptr_t blacklist_locks[] = {
  28        //0xffffffffc03bd000,
  29};
  30
  31/* Could do this on the output side, though noisly locks will crowd us out */
  32static bool can_trace(spinlock_t *lock)
  33{
  34        for (int i = 0; i < ARRAY_SIZE(blacklist_locks); i++) {
  35                if (blacklist_locks[i] == (uintptr_t)lock)
  36                        return FALSE;
  37        }
  38        return TRUE;
  39}
  40
  41/* spinlock and trylock call this after locking */
  42static __always_inline void post_lock(spinlock_t *lock, uint32_t coreid)
  43{
  44        struct per_cpu_info *pcpui = &per_cpu_info[coreid];
  45        if ((pcpui->__lock_checking_enabled == 1) && can_trace(lock))
  46                pcpui_trace_locks(pcpui, lock);
  47        lock->call_site = get_caller_pc();
  48        lock->calling_core = coreid;
  49        /* TODO consider merging this with __ctx_depth (unused field) */
  50        increase_lock_depth(lock->calling_core);
  51}
  52
  53void spin_lock(spinlock_t *lock)
  54{
  55        uint32_t coreid = core_id_early();
  56        struct per_cpu_info *pcpui = &per_cpu_info[coreid];
  57
  58        /* Short circuit our lock checking, so we can print or do other things
  59         * to announce the failure that require locks.  Also avoids anything
  60         * else requiring pcpui initialization. */
  61        if (pcpui->__lock_checking_enabled != 1)
  62                goto lock;
  63        if (lock->irq_okay) {
  64                if (!can_spinwait_irq(pcpui)) {
  65                        pcpui->__lock_checking_enabled--;
  66                        print_kctx_depths("IRQOK");
  67                        panic("Lock %p tried to spin when it shouldn't\n", lock);
  68                        pcpui->__lock_checking_enabled++;
  69                }
  70        } else {
  71                if (!can_spinwait_noirq(pcpui)) {
  72                        pcpui->__lock_checking_enabled--;
  73                        print_kctx_depths("NOIRQ");
  74                        panic("Lock %p tried to spin when it shouldn't\n",
  75                              lock);
  76                        pcpui->__lock_checking_enabled++;
  77                }
  78        }
  79lock:
  80        __spin_lock(lock);
  81        /* Memory barriers are handled by the particular arches */
  82        post_lock(lock, coreid);
  83}
  84
  85/* Trylock doesn't check for irq/noirq, in case we want to try and lock a
  86 * non-irqsave lock from irq context. */
  87bool spin_trylock(spinlock_t *lock)
  88{
  89        uint32_t coreid = core_id_early();
  90        bool ret = __spin_trylock(lock);
  91        if (ret)
  92                post_lock(lock, coreid);
  93        return ret;
  94}
  95
  96void spin_unlock(spinlock_t *lock)
  97{
  98        decrease_lock_depth(lock->calling_core);
  99        /* Memory barriers are handled by the particular arches */
 100        assert(spin_locked(lock));
 101        __spin_unlock(lock);
 102}
 103
 104void spinlock_debug(spinlock_t *lock)
 105{
 106        uintptr_t pc = lock->call_site;
 107
 108        if (!pc) {
 109                printk("Lock %p: never locked\n", lock);
 110                return;
 111        }
 112        printk("Lock %p: currently %slocked.  Last locked at [<%p>] in %s on core %d\n",
 113               lock, spin_locked(lock) ? "" : "un", pc, get_fn_name(pc),
 114               lock->calling_core);
 115}
 116
 117#endif /* CONFIG_SPINLOCK_DEBUG */
 118
 119/* Inits a hashlock. */
 120void hashlock_init(struct hashlock *hl, unsigned int nr_entries)
 121{
 122        hl->nr_entries = nr_entries;
 123        /* this is the right way to do it, though memset is faster.  If we ever
 124         * find that this is taking a lot of time, we can change it. */
 125        for (int i = 0; i < hl->nr_entries; i++) {
 126                spinlock_init(&hl->locks[i]);
 127        }
 128}
 129
 130void hashlock_init_irqsave(struct hashlock *hl, unsigned int nr_entries)
 131{
 132        hl->nr_entries = nr_entries;
 133        /* this is the right way to do it, though memset is faster.  If we ever
 134         * find that this is taking a lot of time, we can change it. */
 135        for (int i = 0; i < hl->nr_entries; i++) {
 136                spinlock_init_irqsave(&hl->locks[i]);
 137        }
 138}
 139
 140/* Helper, gets the specific spinlock for a hl/key combo. */
 141static spinlock_t *get_spinlock(struct hashlock *hl, long key)
 142{
 143        /* using the hashtable's generic hash function */
 144        return &hl->locks[__generic_hash((void*)key) % hl->nr_entries];
 145}
 146
 147void hash_lock(struct hashlock *hl, long key)
 148{
 149        spin_lock(get_spinlock(hl, key));
 150}
 151
 152void hash_unlock(struct hashlock *hl, long key)
 153{
 154        spin_unlock(get_spinlock(hl, key));
 155}
 156
 157void hash_lock_irqsave(struct hashlock *hl, long key)
 158{
 159        spin_lock_irqsave(get_spinlock(hl, key));
 160}
 161
 162void hash_unlock_irqsave(struct hashlock *hl, long key)
 163{
 164        spin_unlock_irqsave(get_spinlock(hl, key));
 165}
 166
 167/* This is the 'post (work) and poke' style of sync.  We make sure the poke
 168 * tracker's function runs.  Once this returns, the func either has run or is
 169 * currently running (in case someone else is running now).  We won't wait or
 170 * spin or anything, and it is safe to call this recursively (deeper in the
 171 * call-graph).
 172 *
 173 * It's up to the caller to somehow post its work.  We'll also pass arg to the
 174 * func, ONLY IF the caller is the one to execute it - so there's no guarantee
 175 * the func(specific_arg) combo will actually run.  It's more for info
 176 * purposes/optimizations/etc.  If no one uses it, I'll get rid of it. */
 177void poke(struct poke_tracker *tracker, void *arg)
 178{
 179        atomic_set(&tracker->need_to_run, TRUE);
 180        /* will need to repeatedly do it if someone keeps posting work */
 181        do {
 182                /* want an wrmb() btw posting work/need_to_run and in_progress.
 183                 * the swap provides the HW mb. just need a cmb, which we do in
 184                 * the loop to cover the iterations (even though i can't imagine
 185                 * the compiler reordering the check it needed to do for the
 186                 * branch).. */
 187                cmb();
 188                /* poke / make sure someone does it.  if we get a TRUE (1) back,
 189                 * someone is already running and will deal with the posted
 190                 * work.  (probably on their next loop).  if we got a 0 back, we
 191                 * won the race and have the 'lock'. */
 192                if (atomic_swap(&tracker->run_in_progress, TRUE))
 193                        return;
 194                /* if we're here, then we're the one who needs to run the func.
 195                 * */
 196                /* clear the 'need to run', since we're running it now.  new
 197                 * users will set it again.  this write needs to be wmb()'d
 198                 * after in_progress.  the swap provided the HW mb(). */
 199                cmb();
 200                /* no internal HW mb */
 201                atomic_set(&tracker->need_to_run, FALSE);
 202                /* run the actual function.  the poke sync makes sure only one
 203                 * caller is in that func at a time. */
 204                assert(tracker->func);
 205                tracker->func(arg);
 206                /* ensure the in_prog write comes after the run_again. */
 207                wmb();
 208                /* no internal HW mb */
 209                atomic_set(&tracker->run_in_progress, FALSE);
 210                /* in_prog write must come before run_again read */
 211                wrmb();
 212        } while (atomic_read(&tracker->need_to_run));
 213}
 214
 215// Must be called in a pair with waiton_checklist
 216int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask)
 217{
 218        assert(list->mask.size == mask->size);
 219        // abort if the list is locked.  this will protect us from trying to
 220        // commit and thus spin on a checklist that we are already waiting on.
 221        // it is still possible to not get the lock, but the holder is on
 222        // another core.  Or, bail out if we can see the list is already in use.
 223        // This check is just an optimization before we try to use the list for
 224        // real.
 225        if ((checklist_is_locked(list)) || !checklist_is_clear(list))
 226                return -EBUSY;
 227
 228        // possession of this lock means you can wait on it and set it
 229        spin_lock_irqsave(&list->lock);
 230        // wait til the list is available.  could have some adaptive thing here
 231        // where it fails after X tries (like 500), gives up the lock, and
 232        // returns an error code
 233        while (!checklist_is_clear(list))
 234                cpu_relax();
 235
 236        // list is ours and clear, set it to the settings of our list
 237        COPY_BITMASK(list->mask.bits, mask->bits, mask->size);
 238        return 0;
 239}
 240
 241int commit_checklist_nowait(checklist_t* list, checklist_mask_t* mask)
 242{
 243        int e = 0;
 244        if ((e = commit_checklist_wait(list, mask)))
 245                return e;
 246        // give up the lock, since we won't wait for completion
 247        spin_unlock_irqsave(&list->lock);
 248        return e;
 249}
 250// The deal with the lock:
 251// what if two different actors are waiting on the list, but for different
 252// reasons?
 253// part of the problem is we are doing both set and check via the same path
 254//
 255// aside: we made this a lot more difficult than the usual barriers or even
 256// the RCU grace-period checkers, since we have to worry about this construct
 257// being used by others before we are done with it.
 258//
 259// how about this: if we want to wait on this later, we just don't release the
 260// lock.  if we release it, then we don't care who comes in and grabs and starts
 261// checking the list.
 262// - regardless, there are going to be issues with people looking for a free
 263// item.  even if they grab the lock, they may end up waiting a while and
 264// wantint to bail (like test for a while, give up, move on, etc).
 265// - still limited in that only the setter can check, and only one person
 266// can spinwait / check for completion.  if someone else tries to wait (wanting
 267// completion), they may miss it if someone else comes in and grabs the lock
 268// to use it for a new checklist
 269//      - if we had the ability to sleep and get woken up, we could have a
 270//      queue.  actually, we could do a queue anyway, but they all spin
 271//      and it's the bosses responsibility to *wake* them
 272
 273// Must be called after commit_checklist
 274// Assumed we held the lock if we ever call this
 275int waiton_checklist(checklist_t* list)
 276{
 277        extern atomic_t outstanding_calls;
 278        // can consider breakout out early, like above, and erroring out
 279        while (!checklist_is_clear(list))
 280                cpu_relax();
 281        spin_unlock_irqsave(&list->lock);
 282        // global counter of wrappers either waited on or being contended for.
 283        atomic_dec(&outstanding_calls);
 284        return 0;
 285}
 286
 287// like waiton, but don't bother waiting either
 288int release_checklist(checklist_t* list)
 289{
 290        spin_unlock_irqsave(&list->lock);
 291        return 0;
 292}
 293
 294// peaks in and sees if the list is locked with it's spinlock
 295int checklist_is_locked(checklist_t* list)
 296{
 297        return spin_locked(&list->lock);
 298}
 299
 300// no synch guarantees - just looks at the list
 301int checklist_is_clear(checklist_t* list)
 302{
 303        return BITMASK_IS_CLEAR(list->mask.bits, list->mask.size);
 304}
 305
 306// no synch guarantees - just looks at the list
 307int checklist_is_full(checklist_t* list)
 308{
 309        return BITMASK_IS_FULL(list->mask.bits, list->mask.size);
 310}
 311
 312// no synch guarantees - just resets the list to empty
 313void reset_checklist(checklist_t* list)
 314{
 315        CLR_BITMASK(list->mask.bits, list->mask.size);
 316}
 317
 318// CPU mask specific - this is how cores report in
 319void down_checklist(checklist_t* list)
 320{
 321        CLR_BITMASK_BIT_ATOMIC(list->mask.bits, core_id());
 322}
 323
 324/* Barriers */
 325void init_barrier(barrier_t* barrier, uint32_t count)
 326{
 327        spinlock_init_irqsave(&barrier->lock);
 328        barrier->init_count = count;
 329        barrier->current_count = count;
 330        barrier->ready = 0;
 331}
 332
 333void reset_barrier(barrier_t* barrier)
 334{
 335        barrier->current_count = barrier->init_count;
 336}
 337
 338// primitive barrier function.  all cores call this.
 339void waiton_barrier(barrier_t* barrier)
 340{
 341        uint8_t local_ready = barrier->ready;
 342
 343        spin_lock_irqsave(&barrier->lock);
 344        barrier->current_count--;
 345        if (barrier->current_count) {
 346                spin_unlock_irqsave(&barrier->lock);
 347                while (barrier->ready == local_ready)
 348                        cpu_relax();
 349        } else {
 350                spin_unlock_irqsave(&barrier->lock);
 351                reset_barrier(barrier);
 352                wmb();
 353                barrier->ready++;
 354        }
 355}
 356