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