Spin-PDR locks (preemption detection and recovery)
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 22 Feb 2013 00:45:46 +0000 (16:45 -0800)
committerBarret Rhoden <brho@cs.berkeley.edu>
Fri, 22 Feb 2013 00:45:46 +0000 (16:45 -0800)
Two variants: with and without CAS.  You can control which one you get
via the CONFIG var in your makelocal.  The default is to use CAS, and
RISCV will get NO_CAS (in spinlock.h) regardless of what you ask for.

The main drawback to the NO_CAS variety is the race where a lockholder
isn't advertised yet, and we're forced to do a linear scan of the
vcoremap to make sure all possible vcores are not preempted.  It won't
deadlock, but it could suck (though it might just be a minor
inconvenience compared to being preempted).

Makeconfig
Makelocal.template
user/parlib/include/spinlock.h
user/parlib/spinlock.c

index 909ce94..740d087 100644 (file)
@@ -18,6 +18,7 @@ CONFIG_SERIAL_IO:=                 -D__CONFIG_SERIAL_IO__
 CONFIG_BSD_ON_CORE0:=              -D__CONFIG_BSD_ON_CORE0__
 CONFIG_SEQLOCK_DEBUG:=             -D__CONFIG_SEQLOCK_DEBUG__
 CONFIG_SPINLOCK_DEBUG:=            -D__CONFIG_SPINLOCK_DEBUG__
 CONFIG_BSD_ON_CORE0:=              -D__CONFIG_BSD_ON_CORE0__
 CONFIG_SEQLOCK_DEBUG:=             -D__CONFIG_SEQLOCK_DEBUG__
 CONFIG_SPINLOCK_DEBUG:=            -D__CONFIG_SPINLOCK_DEBUG__
+CONFIG_SPINPDR_NO_CAS:=            -D__CONFIG_SPINPDR_NO_CAS__
 CONFIG_PAGE_COLORING:=             -D__CONFIG_PAGE_COLORING__
 CONFIG_DEMAND_PAGING:=             -D__CONFIG_DEMAND_PAGING__
 CONFIG_NOMTRRS:=                   -D__CONFIG_NOMTRRS__
 CONFIG_PAGE_COLORING:=             -D__CONFIG_PAGE_COLORING__
 CONFIG_DEMAND_PAGING:=             -D__CONFIG_DEMAND_PAGING__
 CONFIG_NOMTRRS:=                   -D__CONFIG_NOMTRRS__
index 1a0717f..76bf7ba 100644 (file)
@@ -12,6 +12,7 @@ KERN_CFLAGS += $(CONFIG_KFS)
 # Enabling this can cause userspace to make the kernel panic.
 #KERN_CFLAGS += $(CONFIG_SEQLOCK_DEBUG)
 #KERN_CFLAGS += $(CONFIG_SPINLOCK_DEBUG)
 # Enabling this can cause userspace to make the kernel panic.
 #KERN_CFLAGS += $(CONFIG_SEQLOCK_DEBUG)
 #KERN_CFLAGS += $(CONFIG_SPINLOCK_DEBUG)
+#KERN_CFLAGS += $(CONFIG_SPINPDR_NO_CAS)
 #KERN_CFLAGS += $(CONFIG_PAGE_COLORING)
 #KERN_CFLAGS += $(CONFIG_DEMAND_PAGING)
 #KERN_CFLAGS += $(CONFIG_NOMTRRS)
 #KERN_CFLAGS += $(CONFIG_PAGE_COLORING)
 #KERN_CFLAGS += $(CONFIG_DEMAND_PAGING)
 #KERN_CFLAGS += $(CONFIG_NOMTRRS)
index 2bf061c..a119dfc 100644 (file)
@@ -1,8 +1,9 @@
-/*
- * Copyright (c) 2011 The Regents of the University of California
+/* Copyright (c) 2013 The Regents of the University of California
  * Barret Rhoden <brho@cs.berkeley.edu>
  * Kevin Klues <klueska@cs.berkeley.edu>
  *
  * Barret Rhoden <brho@cs.berkeley.edu>
  * Kevin Klues <klueska@cs.berkeley.edu>
  *
+ * Spinlocks and Spin-PDR locks (preemption detection/recovery)
+ *
  * This file is part of Parlib.
  * 
  * Parlib is free software: you can redistribute it and/or modify
  * This file is part of Parlib.
  * 
  * Parlib is free software: you can redistribute it and/or modify
@@ -16,8 +17,7 @@
  * Lesser GNU General Public License for more details.
  * 
  * See COPYING.LESSER for details on the GNU Lesser General Public License.
  * Lesser GNU General Public License for more details.
  * 
  * See COPYING.LESSER for details on the GNU Lesser General Public License.
- * See COPYING for details on the GNU General Public License.
- */
+ * See COPYING for details on the GNU General Public License. */
 
 #ifndef SPINLOCK_H
 #define SPINLOCK_H
 
 #ifndef SPINLOCK_H
 #define SPINLOCK_H
@@ -40,6 +40,39 @@ int spinlock_trylock(spinlock_t *lock);
 void spinlock_lock(spinlock_t *lock);
 void spinlock_unlock(spinlock_t *lock);
 
 void spinlock_lock(spinlock_t *lock);
 void spinlock_unlock(spinlock_t *lock);
 
+/* RISCV doesn't support CAS, so til it does, we use the NO_CAS, even if they
+ * didn't ask for it in their config. */
+#ifdef __riscv__
+# ifndef __CONFIG_SPINPDR_NO_CAS__
+#  define __CONFIG_SPINPDR_NO_CAS__ 1
+# endif
+#endif
+
+/* Two different versions, with and without CAS.  Default is with CAS. */
+#ifndef __CONFIG_SPINPDR_NO_CAS__
+
+# define SPINPDR_UNLOCKED ((uint32_t)-1)
+
+struct spin_pdr_lock {
+       uint32_t lock;
+};
+# define SPINPDR_INITIALIZER {SPINPDR_UNLOCKED}
+
+#else /* NO_CAS */
+
+# define SPINPDR_VCOREID_UNKNOWN ((uint32_t)-1)
+
+struct spin_pdr_lock {
+       spinlock_t spinlock;
+       uint32_t lockholder;
+};
+# define SPINPDR_INITIALIZER {SPINLOCK_INITIALIZER, SPINPDR_VCOREID_UNKNOWN}
+
+#endif /* __CONFIG_SPINPDR_NO_CAS__ */
+
+void spin_pdr_init(struct spin_pdr_lock *pdr_lock);
+void spin_pdr_lock(struct spin_pdr_lock *pdr_lock);
+void spin_pdr_unlock(struct spin_pdr_lock *pdr_lock);
 
 #ifdef __cplusplus
 }
 
 #ifdef __cplusplus
 }
index 9f9a455..abd8e88 100644 (file)
@@ -1,8 +1,9 @@
-/*
- * Copyright (c) 2011 The Regents of the University of California
+/* Copyright (c) 2013 The Regents of the University of California
  * Barret Rhoden <brho@cs.berkeley.edu>
  * Kevin Klues <klueska@cs.berkeley.edu>
  *
  * Barret Rhoden <brho@cs.berkeley.edu>
  * Kevin Klues <klueska@cs.berkeley.edu>
  *
+ * Spinlocks and Spin-PDR locks (preemption detection/recovery)
+ *
  * This file is part of Parlib.
  * 
  * Parlib is free software: you can redistribute it and/or modify
  * This file is part of Parlib.
  * 
  * Parlib is free software: you can redistribute it and/or modify
  * Lesser GNU General Public License for more details.
  * 
  * See COPYING.LESSER for details on the GNU Lesser General Public License.
  * Lesser GNU General Public License for more details.
  * 
  * See COPYING.LESSER for details on the GNU Lesser General Public License.
- * See COPYING for details on the GNU General Public License.
- */
+ * See COPYING for details on the GNU General Public License. */
 
 #include <stdlib.h>
 #include <errno.h>
 #include <assert.h>
 
 #include <stdlib.h>
 #include <errno.h>
 #include <assert.h>
-#include "spinlock.h"
+
+#include <spinlock.h>
+#include <vcore.h>
+#include <uthread.h>
 
 void spinlock_init(spinlock_t *lock)
 {
 
 void spinlock_init(spinlock_t *lock)
 {
@@ -43,9 +46,91 @@ void spinlock_lock(spinlock_t *lock)
     cpu_relax();
 }
 
     cpu_relax();
 }
 
-
 void spinlock_unlock(spinlock_t *lock) 
 {
   assert(lock);
   __sync_lock_release(&lock->lock, 0);
 }
 void spinlock_unlock(spinlock_t *lock) 
 {
   assert(lock);
   __sync_lock_release(&lock->lock, 0);
 }
+
+/* Two different versions, with and without CAS.  Default is with CAS. */
+#ifndef __CONFIG_SPINPDR_NO_CAS__ /* CAS version */
+
+/* Spin-PRD locks (preemption detection/recovery).  Idea is to CAS and put the
+ * lockholder's vcoreid in the lock, and all spinners ensure that vcore runs. */
+void spin_pdr_init(struct spin_pdr_lock *pdr_lock)
+{
+       pdr_lock->lock = SPINPDR_UNLOCKED;
+}
+
+/* Internal version of the locking func, doesn't care if notifs are disabled */
+void __spin_pdr_lock(struct spin_pdr_lock *pdr_lock)
+{
+       uint32_t vcoreid = vcore_id();
+       uint32_t lock_val;
+       assert(vcoreid != SPINPDR_UNLOCKED);
+       do {
+               while ((lock_val = pdr_lock->lock) != SPINPDR_UNLOCKED) {
+                       ensure_vcore_runs(lock_val);
+                       cmb();
+               }
+       } while (!atomic_cas_u32(&pdr_lock->lock, lock_val, vcoreid));
+       cmb();  /* just need a cmb, the CAS handles the CPU wmb/wrmb() */
+}
+
+void __spin_pdr_unlock(struct spin_pdr_lock *pdr_lock)
+{
+       /* could make an arch-dependent 'release barrier' out of these */
+       wmb();  /* Need to prevent the compiler from reordering older stores. */
+       rwmb(); /* And no old reads passing either.   x86 makes both mbs a cmb() */
+       pdr_lock->lock = SPINPDR_UNLOCKED;
+}
+
+#else /* NON-CAS version */
+
+/* Using regular spinlocks, with SPINPDR_VCOREID_UNKNOWN (-1) meaning 'no
+ * lockholder advertised yet'.  There are two spots where the lockholder still
+ * holds the lock but hasn't advertised its vcoreid, and in those cases we
+ * ensure all vcores aren't preempted (linear scan). */
+void spin_pdr_init(struct spin_pdr_lock *pdr_lock)
+{
+       spinlock_init(&pdr_lock->spinlock);
+       pdr_lock->lockholder = SPINPDR_VCOREID_UNKNOWN;
+}
+
+void __spin_pdr_lock(struct spin_pdr_lock *pdr_lock)
+{
+       uint32_t vcoreid = vcore_id();
+       uint32_t ensure_tgt;
+       assert(vcoreid != SPINPDR_VCOREID_UNKNOWN);
+       while (spinlock_trylock(&pdr_lock->spinlock)) {
+               ensure_tgt = pdr_lock->lockholder;
+               /* ensure will make sure *every* vcore runs if you pass it your self. */
+               if (ensure_tgt == SPINPDR_VCOREID_UNKNOWN)
+                       ensure_tgt = vcoreid;
+               ensure_vcore_runs(ensure_tgt);
+               cpu_relax();
+       }
+       pdr_lock->lockholder = vcoreid;
+}
+
+void __spin_pdr_unlock(struct spin_pdr_lock *pdr_lock)
+{
+       pdr_lock->lockholder = SPINPDR_VCOREID_UNKNOWN;
+       spinlock_unlock(&pdr_lock->spinlock);
+}
+
+#endif /* __CONFIG_SPINPDR_NO_CAS__ */
+
+void spin_pdr_lock(struct spin_pdr_lock *pdr_lock)
+{
+       /* Disable notifs, if we're an _M uthread */
+       uth_disable_notifs();
+       __spin_pdr_lock(pdr_lock);
+}
+
+void spin_pdr_unlock(struct spin_pdr_lock *pdr_lock)
+{
+       __spin_pdr_unlock(pdr_lock);
+       /* Enable notifs, if we're an _M uthread */
+       uth_enable_notifs();
+}