Uthread helpers for disabling notifs
[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
8 // MCS locks
9 void mcs_lock_init(struct mcs_lock *lock)
10 {
11         memset(lock,0,sizeof(mcs_lock_t));
12 }
13
14 static inline mcs_lock_qnode_t *mcs_qnode_swap(mcs_lock_qnode_t **addr,
15                                                mcs_lock_qnode_t *val)
16 {
17         return (mcs_lock_qnode_t*)atomic_swap_ptr((void**)addr, val);
18 }
19
20 void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
21 {
22         qnode->next = 0;
23         cmb();  /* swap provides a CPU mb() */
24         mcs_lock_qnode_t *predecessor = mcs_qnode_swap(&lock->lock, qnode);
25         if (predecessor) {
26                 qnode->locked = 1;
27                 wmb();
28                 predecessor->next = qnode;
29                 /* no need for a wrmb(), since this will only get unlocked after they
30                  * read our previous write */
31                 while (qnode->locked)
32                         cpu_relax();
33         }
34         cmb();  /* just need a cmb, the swap handles the CPU wmb/wrmb() */
35 }
36
37 void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
38 {
39         /* Check if someone is already waiting on us to unlock */
40         if (qnode->next == 0) {
41                 cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
42                 /* Unlock it */
43                 mcs_lock_qnode_t *old_tail = mcs_qnode_swap(&lock->lock,0);
44                 /* no one else was already waiting, so we successfully unlocked and can
45                  * return */
46                 if (old_tail == qnode)
47                         return;
48                 /* someone else was already waiting on the lock (last one on the list),
49                  * and we accidentally took them off.  Try and put it back. */
50                 mcs_lock_qnode_t *usurper = mcs_qnode_swap(&lock->lock,old_tail);
51                 /* since someone else was waiting, they should have made themselves our
52                  * next.  spin (very briefly!) til it happens. */
53                 while (qnode->next == 0)
54                         cpu_relax();
55                 if (usurper) {
56                         /* an usurper is someone who snuck in before we could put the old
57                          * tail back.  They now have the lock.  Let's put whoever is
58                          * supposed to be next as their next one. */
59                         usurper->next = qnode->next;
60                 } else {
61                         /* No usurper meant we put things back correctly, so we should just
62                          * pass the lock / unlock whoever is next */
63                         qnode->next->locked = 0;
64                 }
65         } else {
66                 /* mb()s necessary since we didn't call an atomic_swap() */
67                 wmb();  /* need to make sure any previous writes don't pass unlocking */
68                 rwmb(); /* need to make sure any reads happen before the unlocking */
69                 /* simply unlock whoever is next */
70                 qnode->next->locked = 0;
71         }
72 }
73
74 /* CAS style mcs locks, kept around til we use them.  We're using the
75  * usurper-style, since RISCV and SPARC both don't have a real CAS. */
76 void mcs_lock_unlock_cas(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
77 {
78         /* Check if someone is already waiting on us to unlock */
79         if (qnode->next == 0) {
80                 cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
81                 /* If we're still the lock, just swap it with 0 (unlock) and return */
82                 if (atomic_cas_ptr((void**)&lock->lock, qnode, 0))
83                         return;
84                 /* We failed, someone is there and we are some (maybe a different)
85                  * thread's pred.  Since someone else was waiting, they should have made
86                  * themselves our next.  Spin (very briefly!) til it happens. */
87                 while (qnode->next == 0)
88                         cpu_relax();
89                 /* Alpha wants a read_barrier_depends() here */
90                 /* Now that we have a next, unlock them */
91                 qnode->next->locked = 0;
92         } else {
93                 /* mb()s necessary since we didn't call an atomic_swap() */
94                 wmb();  /* need to make sure any previous writes don't pass unlocking */
95                 rwmb(); /* need to make sure any reads happen before the unlocking */
96                 /* simply unlock whoever is next */
97                 qnode->next->locked = 0;
98         }
99 }
100
101 /* We don't bother saving the state, like we do with irqsave, since we can use
102  * whether or not we are in vcore context to determine that.  This means you
103  * shouldn't call this from those moments when you fake being in vcore context
104  * (when switching into the TLS, etc). */
105 void mcs_lock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
106 {
107         uth_disable_notifs();
108         mcs_lock_lock(lock, qnode);
109 }
110
111 /* Note we turn off the DONT_MIGRATE flag before enabling notifs.  This is fine,
112  * since we wouldn't receive any notifs that could lead to us migrating after we
113  * set DONT_MIGRATE but before enable_notifs().  We need it to be in this order,
114  * since we need to check messages after ~DONT_MIGRATE. */
115 void mcs_unlock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
116 {
117         mcs_lock_unlock(lock, qnode);
118         uth_enable_notifs();
119 }
120
121 // MCS dissemination barrier!
122 int mcs_barrier_init(mcs_barrier_t* b, size_t np)
123 {
124         if(np > max_vcores())
125                 return -1;
126         b->allnodes = (mcs_dissem_flags_t*)malloc(np*sizeof(mcs_dissem_flags_t));
127         memset(b->allnodes,0,np*sizeof(mcs_dissem_flags_t));
128         b->nprocs = np;
129
130         b->logp = (np & (np-1)) != 0;
131         while(np >>= 1)
132                 b->logp++;
133
134         size_t i,k;
135         for(i = 0; i < b->nprocs; i++)
136         {
137                 b->allnodes[i].parity = 0;
138                 b->allnodes[i].sense = 1;
139
140                 for(k = 0; k < b->logp; k++)
141                 {
142                         size_t j = (i+(1<<k)) % b->nprocs;
143                         b->allnodes[i].partnerflags[0][k] = &b->allnodes[j].myflags[0][k];
144                         b->allnodes[i].partnerflags[1][k] = &b->allnodes[j].myflags[1][k];
145                 } 
146         }
147
148         return 0;
149 }
150
151 void mcs_barrier_wait(mcs_barrier_t* b, size_t pid)
152 {
153         mcs_dissem_flags_t* localflags = &b->allnodes[pid];
154         size_t i;
155         for(i = 0; i < b->logp; i++)
156         {
157                 *localflags->partnerflags[localflags->parity][i] = localflags->sense;
158                 while(localflags->myflags[localflags->parity][i] != localflags->sense);
159         }
160         if(localflags->parity)
161                 localflags->sense = 1-localflags->sense;
162         localflags->parity = 1-localflags->parity;
163 }
164