Debug helpers for BNX2X
[akaros.git] / user / parlib / mcs.c
1 #include <vcore.h>
2 #include <mcs.h>
3 #include <arch/atomic.h>
4 #include <string.h>
5 #include <stdlib.h>
6 #include <uthread.h>
7 #include <parlib.h>
8 #include <malloc.h>
9
10 // MCS locks
11 void mcs_lock_init(struct mcs_lock *lock)
12 {
13         memset(lock,0,sizeof(mcs_lock_t));
14 }
15
16 static inline mcs_lock_qnode_t *mcs_qnode_swap(mcs_lock_qnode_t **addr,
17                                                mcs_lock_qnode_t *val)
18 {
19         return (mcs_lock_qnode_t*)atomic_swap_ptr((void**)addr, val);
20 }
21
22 void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
23 {
24         qnode->next = 0;
25         cmb();  /* swap provides a CPU mb() */
26         mcs_lock_qnode_t *predecessor = mcs_qnode_swap(&lock->lock, qnode);
27         if (predecessor) {
28                 qnode->locked = 1;
29                 wmb();
30                 predecessor->next = qnode;
31                 /* no need for a wrmb(), since this will only get unlocked after they
32                  * read our previous write */
33                 while (qnode->locked)
34                         cpu_relax();
35         }
36         cmb();  /* just need a cmb, the swap handles the CPU wmb/wrmb() */
37 }
38
39 void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
40 {
41         /* Check if someone is already waiting on us to unlock */
42         if (qnode->next == 0) {
43                 cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
44                 /* Unlock it */
45                 mcs_lock_qnode_t *old_tail = mcs_qnode_swap(&lock->lock,0);
46                 /* no one else was already waiting, so we successfully unlocked and can
47                  * return */
48                 if (old_tail == qnode)
49                         return;
50                 /* someone else was already waiting on the lock (last one on the list),
51                  * and we accidentally took them off.  Try and put it back. */
52                 mcs_lock_qnode_t *usurper = mcs_qnode_swap(&lock->lock,old_tail);
53                 /* since someone else was waiting, they should have made themselves our
54                  * next.  spin (very briefly!) til it happens. */
55                 while (qnode->next == 0)
56                         cpu_relax();
57                 if (usurper) {
58                         /* an usurper is someone who snuck in before we could put the old
59                          * tail back.  They now have the lock.  Let's put whoever is
60                          * supposed to be next as their next one. */
61                         usurper->next = qnode->next;
62                 } else {
63                         /* No usurper meant we put things back correctly, so we should just
64                          * pass the lock / unlock whoever is next */
65                         qnode->next->locked = 0;
66                 }
67         } else {
68                 /* mb()s necessary since we didn't call an atomic_swap() */
69                 wmb();  /* need to make sure any previous writes don't pass unlocking */
70                 rwmb(); /* need to make sure any reads happen before the unlocking */
71                 /* simply unlock whoever is next */
72                 qnode->next->locked = 0;
73         }
74 }
75
76 /* CAS style mcs locks, kept around til we use them.  We're using the
77  * usurper-style, since RISCV doesn't have a real CAS (yet?). */
78 void mcs_lock_unlock_cas(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
79 {
80         /* Check if someone is already waiting on us to unlock */
81         if (qnode->next == 0) {
82                 cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
83                 /* If we're still the lock, just swap it with 0 (unlock) and return */
84                 if (atomic_cas_ptr((void**)&lock->lock, qnode, 0))
85                         return;
86                 /* We failed, someone is there and we are some (maybe a different)
87                  * thread's pred.  Since someone else was waiting, they should have made
88                  * themselves our next.  Spin (very briefly!) til it happens. */
89                 while (qnode->next == 0)
90                         cpu_relax();
91                 /* Alpha wants a read_barrier_depends() here */
92                 /* Now that we have a next, unlock them */
93                 qnode->next->locked = 0;
94         } else {
95                 /* mb()s necessary since we didn't call an atomic_swap() */
96                 wmb();  /* need to make sure any previous writes don't pass unlocking */
97                 rwmb(); /* need to make sure any reads happen before the unlocking */
98                 /* simply unlock whoever is next */
99                 qnode->next->locked = 0;
100         }
101 }
102
103 /* We don't bother saving the state, like we do with irqsave, since we can use
104  * whether or not we are in vcore context to determine that.  This means you
105  * shouldn't call this from those moments when you fake being in vcore context
106  * (when switching into the TLS, etc). */
107 void mcs_lock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
108 {
109         uth_disable_notifs();
110         mcs_lock_lock(lock, qnode);
111 }
112
113 /* Note we turn off the DONT_MIGRATE flag before enabling notifs.  This is fine,
114  * since we wouldn't receive any notifs that could lead to us migrating after we
115  * set DONT_MIGRATE but before enable_notifs().  We need it to be in this order,
116  * since we need to check messages after ~DONT_MIGRATE. */
117 void mcs_unlock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
118 {
119         mcs_lock_unlock(lock, qnode);
120         uth_enable_notifs();
121 }
122
123 // MCS dissemination barrier!
124 int mcs_barrier_init(mcs_barrier_t* b, size_t np)
125 {
126         if(np > max_vcores())
127                 return -1;
128         b->allnodes = (mcs_dissem_flags_t*)malloc(np*sizeof(mcs_dissem_flags_t));
129         memset(b->allnodes,0,np*sizeof(mcs_dissem_flags_t));
130         b->nprocs = np;
131
132         b->logp = (np & (np-1)) != 0;
133         while(np >>= 1)
134                 b->logp++;
135
136         size_t i,k;
137         for(i = 0; i < b->nprocs; i++)
138         {
139                 b->allnodes[i].parity = 0;
140                 b->allnodes[i].sense = 1;
141
142                 for(k = 0; k < b->logp; k++)
143                 {
144                         size_t j = (i+(1<<k)) % b->nprocs;
145                         b->allnodes[i].partnerflags[0][k] = &b->allnodes[j].myflags[0][k];
146                         b->allnodes[i].partnerflags[1][k] = &b->allnodes[j].myflags[1][k];
147                 } 
148         }
149
150         return 0;
151 }
152
153 void mcs_barrier_wait(mcs_barrier_t* b, size_t pid)
154 {
155         mcs_dissem_flags_t* localflags = &b->allnodes[pid];
156         size_t i;
157         for(i = 0; i < b->logp; i++)
158         {
159                 *localflags->partnerflags[localflags->parity][i] = localflags->sense;
160                 while(localflags->myflags[localflags->parity][i] != localflags->sense);
161         }
162         if(localflags->parity)
163                 localflags->sense = 1-localflags->sense;
164         localflags->parity = 1-localflags->parity;
165 }
166
167 /* Preemption detection and recovering MCS locks. */
168 /* Old style.  Has trouble getting out of 'preempt/change-to storms' under
169  * heavy contention and with preemption. */
170 void mcs_pdro_init(struct mcs_pdro_lock *lock)
171 {
172         lock->lock = 0;
173 }
174
175 void mcs_pdro_fini(struct mcs_pdro_lock *lock)
176 {
177 }
178
179 /* Internal version of the locking function, doesn't care if notifs are
180  * disabled.  While spinning, we'll check to see if other vcores involved in the
181  * locking are running.  If we change to that vcore, we'll continue when our
182  * vcore gets restarted.  If the change fails, it is because the vcore is
183  * running, and we'll continue.
184  *
185  * It's worth noting that changing to another vcore won't hurt correctness.
186  * Even if they are no longer the lockholder, they will be checking preemption
187  * messages and will help break out of the deadlock.  So long as we don't
188  * spin uncontrollably, we're okay. */
189 void __mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
190 {
191         struct mcs_pdro_qnode *predecessor;
192         uint32_t pred_vcoreid;
193         /* Now the actual lock */
194         qnode->next = 0;
195         cmb();  /* swap provides a CPU mb() */
196         predecessor = atomic_swap_ptr((void**)&lock->lock, qnode);
197         if (predecessor) {
198                 qnode->locked = 1;
199                 /* Read-in the vcoreid before releasing them.  We won't need to worry
200                  * about their qnode memory being freed/reused (they can't til we fill
201                  * in the 'next' slot), which is a bit of a performance win.  This also
202                  * cuts down on cache-line contention when we ensure they run, which
203                  * helps a lot too. */
204                 pred_vcoreid = ACCESS_ONCE(predecessor->vcoreid);
205                 wmb();  /* order the locked write before the next write */
206                 predecessor->next = qnode;
207                 /* no need for a wrmb(), since this will only get unlocked after they
208                  * read our previous write */
209                 while (qnode->locked) {
210                         /* We don't know who the lock holder is (it hurts performance via
211                          * 'true' sharing to track it)  Instead we'll make sure our pred is
212                          * running, which trickles up to the lock holder. */
213                         ensure_vcore_runs(pred_vcoreid);
214                         cpu_relax();
215                 }
216         }
217 }
218
219 /* Using the CAS style unlocks, since the usurper recovery is a real pain in the
220  * ass */
221 void __mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
222 {
223         uint32_t a_tail_vcoreid;
224         /* Check if someone is already waiting on us to unlock */
225         if (qnode->next == 0) {
226                 cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
227                 /* If we're still the lock, just swap it with 0 (unlock) and return */
228                 if (atomic_cas_ptr((void**)&lock->lock, qnode, 0))
229                         return;
230                 /* Read in the tail (or someone who recently was the tail, but could now
231                  * be farther up the chain), in prep for our spinning. */
232                 a_tail_vcoreid = ACCESS_ONCE(lock->lock->vcoreid);
233                 /* We failed, someone is there and we are some (maybe a different)
234                  * thread's pred.  Since someone else was waiting, they should have made
235                  * themselves our next.  Spin (very briefly!) til it happens. */
236                 while (qnode->next == 0) {
237                         /* We need to get our next to run, but we don't know who they are.
238                          * If we make sure a tail is running, that will percolate up to make
239                          * sure our qnode->next is running */
240                         ensure_vcore_runs(a_tail_vcoreid);
241                         cpu_relax();
242                 }
243                 /* Alpha wants a read_barrier_depends() here */
244                 /* Now that we have a next, unlock them */
245                 qnode->next->locked = 0;
246         } else {
247                 /* mb()s necessary since we didn't call an atomic_swap() */
248                 wmb();  /* need to make sure any previous writes don't pass unlocking */
249                 rwmb(); /* need to make sure any reads happen before the unlocking */
250                 /* simply unlock whoever is next */
251                 qnode->next->locked = 0;
252         }
253 }
254
255 /* Actual MCS-PDRO locks.  Don't worry about initializing any fields of qnode.
256  * We'll do vcoreid here, and the locking code deals with the other fields */
257 void mcs_pdro_lock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
258 {
259         /* Disable notifs, if we're an _M uthread */
260         uth_disable_notifs();
261         cmb();  /* in the off-chance the compiler wants to read vcoreid early */
262         qnode->vcoreid = vcore_id();
263         __mcs_pdro_lock(lock, qnode);
264 }
265
266 /* CAS-less unlock, not quite as efficient and will make sure every vcore runs
267  * (since we don't have a convenient way to make sure our qnode->next runs
268  * yet, other than making sure everyone runs).
269  *
270  * To use this without ensuring all vcores run, you'll need the unlock code to
271  * save pred to a specific field in the qnode and check both its initial pred
272  * as well as its run time pred (who could be an usurper).  It's all possible,
273  * but a little more difficult to follow.  Also, I'm adjusting this comment
274  * months after writing it originally, so it is probably not sufficient, but
275  * necessary. */
276 void __mcs_pdro_unlock_no_cas(struct mcs_pdro_lock *lock,
277                              struct mcs_pdro_qnode *qnode)
278 {
279         struct mcs_pdro_qnode *old_tail, *usurper;
280         /* Check if someone is already waiting on us to unlock */
281         if (qnode->next == 0) {
282                 cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
283                 /* Unlock it */
284                 old_tail = atomic_swap_ptr((void**)&lock->lock, 0);
285                 /* no one else was already waiting, so we successfully unlocked and can
286                  * return */
287                 if (old_tail == qnode)
288                         return;
289                 /* someone else was already waiting on the lock (last one on the list),
290                  * and we accidentally took them off.  Try and put it back. */
291                 usurper = atomic_swap_ptr((void*)&lock->lock, old_tail);
292                 /* since someone else was waiting, they should have made themselves our
293                  * next.  spin (very briefly!) til it happens. */
294                 while (qnode->next == 0) {
295                         /* make sure old_tail isn't preempted.  best we can do for now is
296                          * to make sure all vcores run, and thereby get our next. */
297                         for (int i = 0; i < max_vcores(); i++)
298                                 ensure_vcore_runs(i);
299                         cpu_relax();
300                 }
301                 if (usurper) {
302                         /* an usurper is someone who snuck in before we could put the old
303                          * tail back.  They now have the lock.  Let's put whoever is
304                          * supposed to be next as their next one. 
305                          *
306                          * First, we need to change our next's pred.  There's a slight race
307                          * here, so our next will need to make sure both us and pred are
308                          * done */
309                         /* I was trying to do something so we didn't need to ensure all
310                          * vcores run, using more space in the qnode to figure out who our
311                          * pred was a lock time (guessing actually, since there's a race,
312                          * etc). */
313                         //qnode->next->pred = usurper;
314                         //wmb();
315                         usurper->next = qnode->next;
316                         /* could imagine another wmb() and a flag so our next knows to no
317                          * longer check us too. */
318                 } else {
319                         /* No usurper meant we put things back correctly, so we should just
320                          * pass the lock / unlock whoever is next */
321                         qnode->next->locked = 0;
322                 }
323         } else {
324                 /* mb()s necessary since we didn't call an atomic_swap() */
325                 wmb();  /* need to make sure any previous writes don't pass unlocking */
326                 rwmb(); /* need to make sure any reads happen before the unlocking */
327                 /* simply unlock whoever is next */
328                 qnode->next->locked = 0;
329         }
330 }
331
332 void mcs_pdro_unlock(struct mcs_pdro_lock *lock, struct mcs_pdro_qnode *qnode)
333 {
334         __mcs_pdro_unlock(lock, qnode);
335         /* Enable notifs, if we're an _M uthread */
336         uth_enable_notifs();
337 }
338
339 /* New style: under heavy contention with preemption, they won't enter the
340  * 'preempt/change_to storm' that can happen to PDRs, at the cost of some
341  * performance.  This is the default. */
342 void mcs_pdr_init(struct mcs_pdr_lock *lock)
343 {
344         int ret;
345         lock->lock = 0;
346         lock->lockholder_vcoreid = MCSPDR_NO_LOCKHOLDER;
347         ret = posix_memalign((void**)&lock->qnodes,
348                              __alignof__(struct mcs_pdr_qnode),
349                              sizeof(struct mcs_pdr_qnode) * max_vcores());
350         assert(!ret);
351 }
352
353 void mcs_pdr_fini(struct mcs_pdr_lock *lock)
354 {
355         free(lock->qnodes);
356 }
357
358 /* Similar to the original PDR lock, this tracks the lockholder for better
359  * recovery from preemptions.  Under heavy contention, changing to the
360  * lockholder instead of pred makes it more likely to have a vcore outside the
361  * MCS chain handle the preemption.  If that never happens, performance will
362  * suffer.
363  *
364  * Simply checking the lockholder causes a lot of unnecessary traffic, so we
365  * first look for signs of preemption in read-mostly locations (by comparison,
366  * the lockholder changes on every lock/unlock).
367  *
368  * We also use the "qnodes are in the lock" style, which is slightly slower than
369  * using the stack in regular MCS/MCSPDR locks, but it speeds PDR up a bit by
370  * not having to read other qnodes' memory to determine their vcoreid.  The
371  * slowdown may be due to some weird caching/prefetch settings (like Adjacent
372  * Cacheline Prefetch).
373  *
374  * Note that these locks, like all PDR locks, have opportunities to accidentally
375  * ensure some vcore runs that isn't in the chain.  Whenever we read lockholder
376  * or even pred, that particular vcore might subsequently unlock and then get
377  * preempted (or change_to someone else) before we ensure they run.  If this
378  * happens and there is another VC in the MCS chain, it will make sure the right
379  * cores run.  If there are no other vcores in the chain, it is up to the rest
380  * of the vcore/event handling system to deal with this, which should happen
381  * when one of the other vcores handles the preemption message generated by our
382  * change_to. */
383 void __mcs_pdr_lock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
384 {
385         struct mcs_pdr_qnode *predecessor;
386         uint32_t pred_vcoreid;
387         struct mcs_pdr_qnode *qnode0 = qnode - vcore_id();
388         seq_ctr_t seq;
389         qnode->next = 0;
390         cmb();  /* swap provides a CPU mb() */
391         predecessor = atomic_swap_ptr((void**)&lock->lock, qnode);
392         if (predecessor) {
393                 qnode->locked = 1;
394                 pred_vcoreid = predecessor - qnode0;    /* can compute this whenever */
395                 wmb();  /* order the locked write before the next write */
396                 predecessor->next = qnode;
397                 seq = ACCESS_ONCE(__procinfo.coremap_seqctr);
398                 /* no need for a wrmb(), since this will only get unlocked after they
399                  * read our pred->next write */
400                 while (qnode->locked) {
401                         /* Check to see if anything is amiss.  If someone in the chain is
402                          * preempted, then someone will notice.  Simply checking our pred
403                          * isn't that great of an indicator of preemption.  The reason is
404                          * that the offline vcore is most likely the lockholder (under heavy
405                          * lock contention), and we want someone farther back in the chain
406                          * to notice (someone that will stay preempted long enough for a
407                          * vcore outside the chain to recover them).  Checking the seqctr
408                          * will tell us of any preempts since we started, so if a storm
409                          * starts while we're spinning, we can join in and try to save the
410                          * lockholder before its successor gets it.
411                          *
412                          * Also, if we're the lockholder, then we need to let our pred run
413                          * so they can hand us the lock. */
414                         if (vcore_is_preempted(pred_vcoreid) ||
415                             seq != __procinfo.coremap_seqctr) {
416                                 if (lock->lockholder_vcoreid == MCSPDR_NO_LOCKHOLDER ||
417                                     lock->lockholder_vcoreid == vcore_id())
418                                         ensure_vcore_runs(pred_vcoreid);
419                                 else
420                                         ensure_vcore_runs(lock->lockholder_vcoreid);
421                         }
422                         cpu_relax();
423                 }
424         } else {
425                 lock->lockholder_vcoreid = vcore_id();
426         }
427 }
428
429 void __mcs_pdr_unlock(struct mcs_pdr_lock *lock, struct mcs_pdr_qnode *qnode)
430 {
431         uint32_t a_tail_vcoreid;
432         struct mcs_pdr_qnode *qnode0 = qnode - vcore_id();
433         /* Check if someone is already waiting on us to unlock */
434         if (qnode->next == 0) {
435                 cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
436                 /* If we're still the lock, just swap it with 0 (unlock) and return */
437                 if (atomic_cas_ptr((void**)&lock->lock, qnode, 0)) {
438                         /* This is racy with the new lockholder.  it's possible that we'll
439                          * clobber their legit write, though it doesn't actually hurt
440                          * correctness.  it'll get sorted out on the next unlock. */
441                         lock->lockholder_vcoreid = MCSPDR_NO_LOCKHOLDER;
442                         return;
443                 }
444                 /* Get the tail (or someone who recently was the tail, but could now
445                  * be farther up the chain), in prep for our spinning.  Could do an
446                  * ACCESS_ONCE on lock->lock */
447                 a_tail_vcoreid = lock->lock - qnode0;
448                 /* We failed, someone is there and we are some (maybe a different)
449                  * thread's pred.  Since someone else was waiting, they should have made
450                  * themselves our next.  Spin (very briefly!) til it happens. */
451                 while (qnode->next == 0) {
452                         /* We need to get our next to run, but we don't know who they are.
453                          * If we make sure a tail is running, that will percolate up to make
454                          * sure our qnode->next is running */
455                         ensure_vcore_runs(a_tail_vcoreid);
456                         cpu_relax();
457                 }
458                 /* Alpha wants a read_barrier_depends() here */
459                 lock->lockholder_vcoreid = qnode->next - qnode0;
460                 wmb();  /* order the vcoreid write before the unlock */
461                 qnode->next->locked = 0;
462         } else {
463                 /* Note we're saying someone else is the lockholder, though we still are
464                  * the lockholder until we unlock the next qnode.  Our next knows that
465                  * if it sees itself is the lockholder, that it needs to make sure we
466                  * run. */
467                 lock->lockholder_vcoreid = qnode->next - qnode0;
468                 /* mb()s necessary since we didn't call an atomic_swap() */
469                 wmb();  /* need to make sure any previous writes don't pass unlocking */
470                 rwmb(); /* need to make sure any reads happen before the unlocking */
471                 /* simply unlock whoever is next */
472                 qnode->next->locked = 0;
473         }
474 }
475
476 void mcs_pdr_lock(struct mcs_pdr_lock *lock)
477 {
478         uth_disable_notifs();
479         cmb();  /* in the off-chance the compiler wants to read vcoreid early */
480         __mcs_pdr_lock(lock, &lock->qnodes[vcore_id()]);
481 }
482
483 void mcs_pdr_unlock(struct mcs_pdr_lock *lock)
484 {
485         __mcs_pdr_unlock(lock, &lock->qnodes[vcore_id()]);
486         uth_enable_notifs();
487 }