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