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