Remove unnecessary panic() in rread()
[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
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         }
79 lock:
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. */
87 bool 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
96 void 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
104 void 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. */
120 void 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
130 void 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. */
141 static 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
147 void hash_lock(struct hashlock *hl, long key)
148 {
149         spin_lock(get_spinlock(hl, key));
150 }
151
152 void hash_unlock(struct hashlock *hl, long key)
153 {
154         spin_unlock(get_spinlock(hl, key));
155 }
156
157 void hash_lock_irqsave(struct hashlock *hl, long key)
158 {
159         spin_lock_irqsave(get_spinlock(hl, key));
160 }
161
162 void 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. */
177 void 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
216 int 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
241 int 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
275 int 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
288 int 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
295 int checklist_is_locked(checklist_t* list)
296 {
297         return spin_locked(&list->lock);
298 }
299
300 // no synch guarantees - just looks at the list
301 int 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
307 int 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
313 void 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
319 void down_checklist(checklist_t* list)
320 {
321         CLR_BITMASK_BIT_ATOMIC(list->mask.bits, core_id());
322 }
323
324 /* Barriers */
325 void 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
333 void reset_barrier(barrier_t* barrier)
334 {
335         barrier->current_count = barrier->init_count;
336 }
337
338 // primitive barrier function.  all cores call this.
339 void 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 }