99a386573c5b31c883fc8d899f3c6b8964c04744
[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         if (!in_vcore_context() && in_multi_mode()) {
108                 if (current_uthread)
109                         current_uthread->flags |= UTHREAD_DONT_MIGRATE;
110                 cmb();  /* don't issue the flag write before the vcore_id() read */
111                 disable_notifs(vcore_id());
112         }
113         mcs_lock_lock(lock, qnode);
114 }
115
116 /* Note we turn off the DONT_MIGRATE flag before enabling notifs.  This is fine,
117  * since we wouldn't receive any notifs that could lead to us migrating after we
118  * set DONT_MIGRATE but before enable_notifs().  We need it to be in this order,
119  * since we need to check messages after ~DONT_MIGRATE. */
120 void mcs_unlock_notifsafe(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
121 {
122         mcs_lock_unlock(lock, qnode);
123         if (!in_vcore_context() && in_multi_mode()) {
124                 if (current_uthread)
125                         current_uthread->flags &= ~UTHREAD_DONT_MIGRATE;
126                 cmb();  /* don't enable before ~DONT_MIGRATE */
127                 enable_notifs(vcore_id());
128         }
129 }
130
131 // MCS dissemination barrier!
132 int mcs_barrier_init(mcs_barrier_t* b, size_t np)
133 {
134         if(np > max_vcores())
135                 return -1;
136         b->allnodes = (mcs_dissem_flags_t*)malloc(np*sizeof(mcs_dissem_flags_t));
137         memset(b->allnodes,0,np*sizeof(mcs_dissem_flags_t));
138         b->nprocs = np;
139
140         b->logp = (np & (np-1)) != 0;
141         while(np >>= 1)
142                 b->logp++;
143
144         size_t i,k;
145         for(i = 0; i < b->nprocs; i++)
146         {
147                 b->allnodes[i].parity = 0;
148                 b->allnodes[i].sense = 1;
149
150                 for(k = 0; k < b->logp; k++)
151                 {
152                         size_t j = (i+(1<<k)) % b->nprocs;
153                         b->allnodes[i].partnerflags[0][k] = &b->allnodes[j].myflags[0][k];
154                         b->allnodes[i].partnerflags[1][k] = &b->allnodes[j].myflags[1][k];
155                 } 
156         }
157
158         return 0;
159 }
160
161 void mcs_barrier_wait(mcs_barrier_t* b, size_t pid)
162 {
163         mcs_dissem_flags_t* localflags = &b->allnodes[pid];
164         size_t i;
165         for(i = 0; i < b->logp; i++)
166         {
167                 *localflags->partnerflags[localflags->parity][i] = localflags->sense;
168                 while(localflags->myflags[localflags->parity][i] != localflags->sense);
169         }
170         if(localflags->parity)
171                 localflags->sense = 1-localflags->sense;
172         localflags->parity = 1-localflags->parity;
173 }
174