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