akaros/kern/include/atomic.h
<<
>>
Prefs
   1/* Copyright (c) 2009-2011 The Regents of the University of California
   2 * Barret Rhoden <brho@cs.berkeley.edu>
   3 * See LICENSE for details.
   4 *
   5 * Kernel atomics and locking functions.
   6 *
   7 * The extern inline declarations are arch-dependent functions.  We do this
   8 * so that each arch can either static inline or just have a regular function,
   9 * whichever is appropriate. The actual implementation usually will be in
  10 * arch/atomic.h (for inlines).
  11 *
  12 * The static inlines are defined farther down in the file (as always). */
  13
  14#pragma once
  15
  16#include <ros/common.h>
  17#include <ros/atomic.h>
  18#include <arch/membar.h>
  19#include <arch/mmu.h>
  20#include <arch/arch.h>
  21#include <assert.h>
  22
  23/* Atomics */
  24extern inline void atomic_init(atomic_t *number, long val);
  25extern inline long atomic_read(atomic_t *number);
  26extern inline void atomic_set(atomic_t *number, long val);
  27extern inline void atomic_add(atomic_t *number, long val);
  28extern inline void atomic_inc(atomic_t *number);
  29extern inline void atomic_dec(atomic_t *number);
  30extern inline long atomic_fetch_and_add(atomic_t *number, long val);
  31extern inline void atomic_and(atomic_t *number, long mask);
  32extern inline void atomic_or(atomic_t *number, long mask);
  33extern inline long atomic_swap(atomic_t *addr, long val);
  34extern inline bool atomic_cas(atomic_t *addr, long exp_val, long new_val);
  35extern inline bool atomic_cas_ptr(void **addr, void *exp_val, void *new_val);
  36extern inline bool atomic_cas_u32(uint32_t *addr, uint32_t exp_val,
  37                                  uint32_t new_val);
  38extern inline bool atomic_add_not_zero(atomic_t *number, long val);
  39extern inline bool atomic_sub_and_test(atomic_t *number, long val);
  40
  41/* Spin locks */
  42struct spinlock {
  43        volatile uint32_t rlock;
  44#ifdef CONFIG_SPINLOCK_DEBUG
  45        uintptr_t call_site;
  46        uint32_t calling_core;
  47        bool irq_okay;
  48#endif
  49};
  50typedef struct spinlock spinlock_t;
  51#define SPINLOCK_INITIALIZER {0}
  52
  53#ifdef CONFIG_SPINLOCK_DEBUG
  54#define SPINLOCK_INITIALIZER_IRQSAVE {0, .irq_okay = TRUE}
  55#else
  56#define SPINLOCK_INITIALIZER_IRQSAVE SPINLOCK_INITIALIZER
  57#endif
  58
  59/* Arch dependent helpers/funcs: */
  60extern inline void __spinlock_init(spinlock_t *lock);
  61extern inline bool spin_locked(spinlock_t *lock);
  62extern inline void __spin_lock(spinlock_t *lock);
  63extern inline void __spin_unlock(spinlock_t *lock);
  64
  65/* So we can inline a __spin_lock if we want.  Even though we don't need this
  66 * if we're debugging, its helpful to keep the include at the same place for
  67 * all builds. */
  68#include <arch/atomic.h>
  69
  70#ifdef CONFIG_SPINLOCK_DEBUG
  71/* Arch indep, in k/s/atomic.c */
  72void spin_lock(spinlock_t *lock);
  73bool spin_trylock(spinlock_t *lock);
  74void spin_unlock(spinlock_t *lock);
  75void spinlock_debug(spinlock_t *lock);
  76
  77#else
  78/* Just inline the arch-specific __ versions */
  79static inline void spin_lock(spinlock_t *lock)
  80{
  81        __spin_lock(lock);
  82}
  83
  84static inline bool spin_trylock(spinlock_t *lock)
  85{
  86        return __spin_trylock(lock);
  87}
  88
  89static inline void spin_unlock(spinlock_t *lock)
  90{
  91        __spin_unlock(lock);
  92}
  93
  94static inline void spinlock_debug(spinlock_t *lock)
  95{
  96}
  97
  98#endif /* CONFIG_SPINLOCK_DEBUG */
  99
 100/* Inlines, defined below */
 101static inline void spinlock_init(spinlock_t *lock);
 102static inline void spinlock_init_irqsave(spinlock_t *lock);
 103static inline void spin_lock_irqsave(spinlock_t *lock);
 104static inline bool spin_trylock_irqsave(spinlock_t *lock);
 105static inline void spin_unlock_irqsave(spinlock_t *lock);
 106static inline bool spin_lock_irq_enabled(spinlock_t *lock);
 107
 108/* Hash locks (array of spinlocks).  Most all users will want the default one,
 109 * so point your pointer to one of them, though you could always kmalloc a
 110 * bigger one.  In the future, they might be growable, etc, which init code may
 111 * care about. */
 112struct hashlock {
 113        unsigned int                    nr_entries;
 114        struct spinlock                 locks[];
 115};
 116#define HASHLOCK_DEFAULT_SZ 53          /* nice prime, might be a bit large */
 117struct small_hashlock {
 118        unsigned int                    nr_entries;
 119        struct spinlock                 locks[HASHLOCK_DEFAULT_SZ];
 120};
 121
 122void hashlock_init(struct hashlock *hl, unsigned int nr_entries);
 123void hashlock_init_irqsave(struct hashlock *hl, unsigned int nr_entries);
 124void hash_lock(struct hashlock *hl, long key);
 125void hash_unlock(struct hashlock *hl, long key);
 126void hash_lock_irqsave(struct hashlock *hl, long key);
 127void hash_unlock_irqsave(struct hashlock *hl, long key);
 128
 129/* Seq locks */
 130/* An example seq lock, built from the counter.  I don't particularly like this,
 131 * since it forces you to use a specific locking type.  */
 132typedef struct seq_lock {
 133        spinlock_t                      w_lock;
 134        seq_ctr_t                       r_ctr;
 135} seqlock_t;
 136
 137static inline void __seq_start_write(seq_ctr_t *seq_ctr);
 138static inline void __seq_end_write(seq_ctr_t *seq_ctr);
 139static inline void write_seqlock(seqlock_t *lock);
 140static inline void write_sequnlock(seqlock_t *lock);
 141static inline seq_ctr_t read_seqbegin(seqlock_t *lock);
 142static inline bool read_seqretry(seqlock_t *lock, seq_ctr_t ctr);
 143
 144/* Post work and poke synchronization.  This is a wait-free way to make sure
 145 * some code is run, usually by the calling core, but potentially by any core.
 146 * Under contention, everyone just posts work, and one core will carry out the
 147 * work.  Callers post work (the meaning of which is particular to their
 148 * subsystem), then call this function.  The function is not run concurrently
 149 * with itself.
 150 *
 151 * In the future, this may send RKMs to LL cores to ensure the work is done
 152 * somewhere, but not necessarily on the calling core.  Will reserve 'flags'
 153 * for that. */
 154struct poke_tracker {
 155        atomic_t                        need_to_run;
 156        atomic_t                        run_in_progress;
 157        void                            (*func)(void *);
 158};
 159void poke(struct poke_tracker *tracker, void *arg);
 160
 161static inline void poke_init(struct poke_tracker *tracker, void (*func)(void*))
 162{
 163        tracker->need_to_run = 0;
 164        tracker->run_in_progress = 0;
 165        tracker->func = func;
 166}
 167#define POKE_INITIALIZER(f) {.func = f}
 168
 169/* Arch-specific implementations / declarations go here */
 170#include <arch/atomic.h>
 171
 172#define MAX_SPINS 1000000000
 173
 174/* Will spin for a little while, but not deadlock if it never happens */
 175#define spin_on(x)                                                             \
 176        for (int i = 0; (x); i++) {                                            \
 177                cpu_relax();                                                   \
 178                if (i == MAX_SPINS) {                                          \
 179                        printk("Probably timed out/failed.\n");                \
 180                        break;                                                 \
 181                }                                                              \
 182        }
 183
 184/*********************** Checklist stuff **********************/
 185typedef struct checklist_mask {
 186        // only need an uint8_t, but we need the bits[] to be word aligned
 187        uint32_t size;
 188        volatile uint8_t bits[MAX_NUM_CORES];
 189} checklist_mask_t;
 190
 191// mask contains an unspecified array, so it needs to be at the bottom
 192struct checklist {
 193        spinlock_t lock;
 194        checklist_mask_t mask;
 195        // eagle-eyed readers may know why this might have been needed.
 196        // 2009-09-04
 197        //volatile uint8_t (COUNT(BYTES_FOR_BITMASK(size)) bits)[];
 198};
 199typedef struct checklist checklist_t;
 200
 201#define ZEROS_ARRAY(size) {[0 ... ((size)-1)] 0}
 202
 203#define DEFAULT_CHECKLIST_MASK(sz) {(sz), ZEROS_ARRAY(BYTES_FOR_BITMASK(sz))}
 204#define DEFAULT_CHECKLIST(sz) {SPINLOCK_INITIALIZER_IRQSAVE,                   \
 205                               DEFAULT_CHECKLIST_MASK(sz)}
 206#define INIT_CHECKLIST(nm, sz)  \
 207        checklist_t nm = DEFAULT_CHECKLIST(sz);
 208#define INIT_CHECKLIST_MASK(nm, sz)     \
 209        checklist_mask_t nm = DEFAULT_CHECKLIST_MASK(sz);
 210
 211int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask);
 212int commit_checklist_nowait(checklist_t* list, checklist_mask_t* mask);
 213int waiton_checklist(checklist_t* list);
 214int release_checklist(checklist_t* list);
 215int checklist_is_locked(checklist_t* list);
 216int checklist_is_clear(checklist_t* list);
 217int checklist_is_full(checklist_t* list);
 218void reset_checklist(checklist_t* list);
 219void down_checklist(checklist_t* list);
 220// TODO - do we want to adjust the size?  (YES, don't want to check it all)
 221// TODO - do we want to be able to call waiton without having called commit?
 222//      - in the case of protected checklists
 223// TODO - want a destroy checklist (when we have kmalloc, or whatever)
 224// TODO - some sort of dynamic allocation of them in the future
 225// TODO - think about deadlock issues with one core spinning on a lock for
 226// something that it is the hold out for...
 227//      - probably should have interrupts enabled, and never grab these locks
 228//      from interrupt context (and not use irq_save)
 229/**************************************************************/
 230
 231/* Barrier: currently made for everyone barriering.  Change to use checklist */
 232struct barrier {
 233        spinlock_t lock;
 234        uint32_t init_count;
 235        uint32_t current_count;
 236        volatile uint8_t ready;
 237};
 238
 239typedef struct barrier barrier_t;
 240
 241void init_barrier(barrier_t *barrier, uint32_t count);
 242void reset_barrier(barrier_t* barrier);
 243void waiton_barrier(barrier_t* barrier);
 244
 245/* Spinlock bit flags */
 246#define SPINLOCK_IRQ_EN                 0x80000000
 247
 248static inline void spinlock_init(spinlock_t *lock)
 249{
 250        __spinlock_init(lock);
 251#ifdef CONFIG_SPINLOCK_DEBUG
 252        lock->call_site = 0;
 253        lock->calling_core = 0;
 254        lock->irq_okay = FALSE;
 255#endif
 256}
 257
 258static inline void spinlock_init_irqsave(spinlock_t *lock)
 259{
 260        __spinlock_init(lock);
 261#ifdef CONFIG_SPINLOCK_DEBUG
 262        lock->call_site = 0;
 263        lock->calling_core = 0;
 264        lock->irq_okay = TRUE;
 265#endif
 266}
 267
 268// If ints are enabled, disable them and note it in the top bit of the lock
 269// There is an assumption about releasing locks in order here...
 270static inline void spin_lock_irqsave(spinlock_t *lock)
 271{
 272        uint32_t irq_en;
 273        irq_en = irq_is_enabled();
 274        disable_irq();
 275        spin_lock(lock);
 276        if (irq_en)
 277                lock->rlock |= SPINLOCK_IRQ_EN;
 278}
 279
 280static inline bool spin_trylock_irqsave(spinlock_t *lock)
 281{
 282        uint32_t irq_en = irq_is_enabled();
 283
 284        disable_irq();
 285        if (!spin_trylock(lock)) {
 286                if (irq_en)
 287                        enable_irq();
 288                return FALSE;
 289        }
 290        if (irq_en)
 291                lock->rlock |= SPINLOCK_IRQ_EN;
 292        return TRUE;
 293}
 294
 295// if the high bit of the lock is set, then re-enable interrupts
 296// (note from asw: you're lucky this works, you little-endian jerks)
 297static inline void spin_unlock_irqsave(spinlock_t *lock)
 298{
 299        if (spin_lock_irq_enabled(lock)) {
 300                spin_unlock(lock);
 301                enable_irq();
 302        } else
 303                spin_unlock(lock);
 304}
 305
 306/* Returns whether or not unlocking this lock should enable interrupts or not.
 307 * Is meaningless on locks that weren't locked with irqsave. */
 308static inline bool spin_lock_irq_enabled(spinlock_t *lock)
 309{
 310        return lock->rlock & SPINLOCK_IRQ_EN;
 311}
 312
 313/* Note, the seq_ctr is not a full seq lock - just the counter guts.  Write
 314 * access can be controlled by another lock (like the proc-lock).  start_ and
 315 * end_write are the writer's responsibility to signal the readers of a
 316 * concurrent write. */
 317static inline void __seq_start_write(seq_ctr_t *seq_ctr)
 318{
 319#ifdef CONFIG_SEQLOCK_DEBUG
 320        assert(*seq_ctr % 2 == 0);
 321#endif
 322        (*seq_ctr)++;
 323        /* We're the only writer, so we need to prevent the compiler (and some
 324         * arches) from reordering writes before this point. */
 325        wmb();
 326}
 327
 328static inline void __seq_end_write(seq_ctr_t *seq_ctr)
 329{
 330#ifdef CONFIG_SEQLOCK_DEBUG
 331        assert(*seq_ctr % 2 == 1);
 332#endif
 333        /* Need to prevent the compiler (and some arches) from reordering older
 334         * stores */
 335        wmb();
 336        (*seq_ctr)++;
 337}
 338
 339/* Untested reference implementation of a seq lock.  As mentioned above, we
 340 * might need a variety of these (for instance, this doesn't do an irqsave).  Or
 341 * there may be other invariants that we need the lock to protect. */
 342static inline void write_seqlock(seqlock_t *lock)
 343{
 344        spin_lock(&lock->w_lock);
 345        __seq_start_write(&lock->r_ctr);
 346}
 347
 348static inline void write_sequnlock(seqlock_t *lock)
 349{
 350        __seq_end_write(&lock->r_ctr);
 351        spin_unlock(&lock->w_lock);
 352}
 353
 354static inline seq_ctr_t read_seqbegin(seqlock_t *lock)
 355{
 356        seq_ctr_t retval = lock->r_ctr;
 357        rmb();  /* don't want future reads to come before our ctr read */
 358        return retval;
 359}
 360
 361static inline bool read_seqretry(seqlock_t *lock, seq_ctr_t ctr)
 362{
 363        return seqctr_retry(lock->r_ctr, ctr);
 364}
 365