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