kern/include/atomic.h

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