Adds MCS unlock code that uses CAS.
authorBarret Rhoden <brho@cs.berkeley.edu>
Mon, 10 Oct 2011 23:24:12 +0000 (16:24 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:08 +0000 (17:36 -0700)
We don't use this since SPARC and RISCV don't have a native CAS yet, but
I want the code in place for a couple upcoming commits.

This patch also comments on how the MCS locks work, which helps a bit.

user/parlib/mcs.c

index ae4d23a..99a3865 100644 (file)
@@ -36,22 +36,64 @@ void mcs_lock_lock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
 
 void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
 {
 
 void mcs_lock_unlock(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
 {
+       /* Check if someone is already waiting on us to unlock */
        if (qnode->next == 0) {
                cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
        if (qnode->next == 0) {
                cmb();  /* no need for CPU mbs, since there's an atomic_swap() */
+               /* Unlock it */
                mcs_lock_qnode_t *old_tail = mcs_qnode_swap(&lock->lock,0);
                mcs_lock_qnode_t *old_tail = mcs_qnode_swap(&lock->lock,0);
+               /* no one else was already waiting, so we successfully unlocked and can
+                * return */
                if (old_tail == qnode)
                        return;
                if (old_tail == qnode)
                        return;
+               /* someone else was already waiting on the lock (last one on the list),
+                * and we accidentally took them off.  Try and put it back. */
                mcs_lock_qnode_t *usurper = mcs_qnode_swap(&lock->lock,old_tail);
                mcs_lock_qnode_t *usurper = mcs_qnode_swap(&lock->lock,old_tail);
+               /* since someone else was waiting, they should have made themselves our
+                * next.  spin (very briefly!) til it happens. */
                while (qnode->next == 0)
                        cpu_relax();
                while (qnode->next == 0)
                        cpu_relax();
-               if (usurper)
+               if (usurper) {
+                       /* an usurper is someone who snuck in before we could put the old
+                        * tail back.  They now have the lock.  Let's put whoever is
+                        * supposed to be next as their next one. */
                        usurper->next = qnode->next;
                        usurper->next = qnode->next;
-               else
+               } else {
+                       /* No usurper meant we put things back correctly, so we should just
+                        * pass the lock / unlock whoever is next */
                        qnode->next->locked = 0;
                        qnode->next->locked = 0;
+               }
        } else {
                /* mb()s necessary since we didn't call an atomic_swap() */
                wmb();  /* need to make sure any previous writes don't pass unlocking */
                rwmb(); /* need to make sure any reads happen before the unlocking */
        } else {
                /* mb()s necessary since we didn't call an atomic_swap() */
                wmb();  /* need to make sure any previous writes don't pass unlocking */
                rwmb(); /* need to make sure any reads happen before the unlocking */
+               /* simply unlock whoever is next */
+               qnode->next->locked = 0;
+       }
+}
+
+/* CAS style mcs locks, kept around til we use them.  We're using the
+ * usurper-style, since RISCV and SPARC both don't have a real CAS. */
+void mcs_lock_unlock_cas(struct mcs_lock *lock, struct mcs_lock_qnode *qnode)
+{
+       /* Check if someone is already waiting on us to unlock */
+       if (qnode->next == 0) {
+               cmb();  /* no need for CPU mbs, since there's an atomic_cas() */
+               /* If we're still the lock, just swap it with 0 (unlock) and return */
+               if (atomic_cas_ptr((void**)&lock->lock, qnode, 0))
+                       return;
+               /* We failed, someone is there and we are some (maybe a different)
+                * thread's pred.  Since someone else was waiting, they should have made
+                * themselves our next.  Spin (very briefly!) til it happens. */
+               while (qnode->next == 0)
+                       cpu_relax();
+               /* Alpha wants a read_barrier_depends() here */
+               /* Now that we have a next, unlock them */
+               qnode->next->locked = 0;
+       } else {
+               /* mb()s necessary since we didn't call an atomic_swap() */
+               wmb();  /* need to make sure any previous writes don't pass unlocking */
+               rwmb(); /* need to make sure any reads happen before the unlocking */
+               /* simply unlock whoever is next */
                qnode->next->locked = 0;
        }
 }
                qnode->next->locked = 0;
        }
 }