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