[PATCH] back-off algorithm for spinning
"Attilio Rao" <[email protected]> Mon, 2 Jun 2008 15:12:18 +0200
| Newsgroups | gmane.os.freebsd.devel.smp |
|---|---|
| Message-ID | <[email protected]> |
The attached patch implements a back-off algorithm for adaptive spinning in order to reduce cache traffics in big SMP environments. I really need to tune values (CAP and SHIFT) on a big SMP machine (16/32 ways possibily) and currently I have no-one available. Some tips: - uint32_t has been choosen for the back-off counters as we want a fixed size because we want to have a deterministic size for words - Possibily, in the spinlock case, the loop for the first number of loop counting can be reduced now, but we still need to maintain the same difference between this and the later value for determining "spinlock held too long". Revisions are appreciated. Thanks, Attilio -- Peace can only be achieved by understanding - A. Einstein _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-smp To unsubscribe, send any mail to "[email protected]"
lock_backoff.diff
(application/octet-stream, 6.1 KB)
--- /usr/src/sys/kern/kern_mutex.c 2008-05-31 23:42:14.000000000 +0200
+++ sys/kern/kern_mutex.c 2008-06-02 00:12:26.000000000 +0200
@@ -123,6 +123,26 @@
struct mtx blocked_lock;
struct mtx Giant;
+#ifdef ADAPTIVE_MUTEXES
+static __inline void
+mtx_adapt_spin(struct mtx *m, volatile struct thread *owner)
+{
+ uint32_t backoff, tback;
+
+ /*
+ * Use a back-off counter in order to reduce caches traffic when
+ * reading the lock state.
+ */
+ for (backoff = LOCK_BACKOFF_INIT; mtx_owner(m) == owner &&
+ TD_IS_RUNNING(owner); backoff <<= LOCK_BACKOFF_SHIFT) {
+ if (backoff > LOCK_BACKOFF_CAP)
+ backoff = LOCK_BACKOFF_CAP;
+ for (tback = 0; tback != backoff; tback++)
+ cpu_spinwait();
+ }
+}
+#endif
+
void
assert_mtx(struct lock_object *lock, int what)
{
@@ -338,9 +358,7 @@
CTR3(KTR_LOCK,
"%s: spinning on %p held by %p",
__func__, m, owner);
- while (mtx_owner(m) == owner &&
- TD_IS_RUNNING(owner))
- cpu_spinwait();
+ mtx_adapt_spin(m, owner);
continue;
}
}
@@ -448,6 +466,7 @@
_mtx_lock_spin(struct mtx *m, uintptr_t tid, int opts, const char *file,
int line)
{
+ uint32_t backoff, tback;
int i = 0, contested = 0;
uint64_t waittime = 0;
@@ -459,9 +478,14 @@
/* Give interrupts a chance while we spin. */
spinlock_exit();
+ backoff = LOCK_BACKOFF_INIT;
while (m->mtx_lock != MTX_UNOWNED) {
if (i++ < 10000000) {
- cpu_spinwait();
+ if (backoff > LOCK_BACKOFF_CAP)
+ backoff = LOCK_BACKOFF_CAP;
+ for (tback = 0; tback != backoff; tback++)
+ cpu_spinwait();
+ backoff <<= LOCK_BACKOFF_SHIFT;
continue;
}
if (i < 60000000 || kdb_active || panicstr != NULL)
@@ -488,6 +512,7 @@
uintptr_t tid;
int i, contested;
uint64_t waittime;
+ uint32_t backoff, tback;
contested = i = 0;
waittime = 0;
@@ -516,10 +541,16 @@
&contested, &waittime);
/* Give interrupts a chance while we spin. */
spinlock_exit();
+ backoff = LOCK_BACKOFF_INIT;
while (m->mtx_lock != MTX_UNOWNED) {
- if (i++ < 10000000)
- cpu_spinwait();
- else if (i < 60000000 ||
+ if (i++ < 10000000) {
+ if (backoff > LOCK_BACKOFF_CAP)
+ backoff = LOCK_BACKOFF_CAP;
+ for (tback = 0; tback != backoff;
+ tback++)
+ cpu_spinwait();
+ backoff <<= LOCK_BACKOFF_SHIFT;
+ } else if (i < 60000000 ||
kdb_active || panicstr != NULL)
DELAY(1);
else
--- /usr/src/sys/kern/kern_rwlock.c 2008-05-31 23:42:15.000000000 +0200
+++ sys/kern/kern_rwlock.c 2008-06-01 23:32:24.000000000 +0200
@@ -114,6 +114,27 @@
#define _rw_assert(rw, what, file, line)
#endif
+#ifdef ADAPTIVE_RWLOCKS
+static __inline void
+rw_adapt_spin(struct rwlock *rw, volatile struct thread *owner)
+{
+ uint32_t backoff, tback;
+
+ /*
+ * Use a back-off counter in order to reduce caches traffic when
+ * reading the lock state.
+ */
+ for (backoff = LOCK_BACKOFF_INIT; owner ==
+ (struct thread*)RW_OWNER(rw->rw_lock) && TD_IS_RUNNING(owner);
+ backoff <<= LOCK_BACKOFF_SHIFT) {
+ if (backoff > LOCK_BACKOFF_CAP)
+ backoff = LOCK_BACKOFF_CAP;
+ for (tback = 0; tback != backoff; tback++)
+ cpu_spinwait();
+ }
+}
+#endif
+
void
assert_rw(struct lock_object *lock, int what)
{
@@ -271,8 +292,7 @@
struct turnstile *ts;
#ifdef ADAPTIVE_RWLOCKS
volatile struct thread *owner;
- int spintries = 0;
- int i;
+ int i, spintries = 0;
#endif
uint64_t waittime = 0;
int contested = 0;
@@ -331,9 +351,7 @@
CTR3(KTR_LOCK,
"%s: spinning on %p held by %p",
__func__, rw, owner);
- while ((struct thread*)RW_OWNER(rw->rw_lock) ==
- owner && TD_IS_RUNNING(owner))
- cpu_spinwait();
+ rw_adapt_spin(rw, owner);
continue;
}
} else if (spintries < rowner_retries) {
@@ -573,8 +591,7 @@
struct turnstile *ts;
#ifdef ADAPTIVE_RWLOCKS
volatile struct thread *owner;
- int spintries = 0;
- int i;
+ int i, spintries = 0;
#endif
uint64_t waittime = 0;
uintptr_t v, x;
@@ -609,9 +626,7 @@
if (LOCK_LOG_TEST(&rw->lock_object, 0))
CTR3(KTR_LOCK, "%s: spinning on %p held by %p",
__func__, rw, owner);
- while ((struct thread*)RW_OWNER(rw->rw_lock) == owner &&
- TD_IS_RUNNING(owner))
- cpu_spinwait();
+ rw_adapt_spin(rw, owner);
continue;
}
if ((v & RW_LOCK_READ) && RW_READERS(v) &&
--- /usr/src/sys/kern/kern_sx.c 2008-05-31 23:42:15.000000000 +0200
+++ sys/kern/kern_sx.c 2008-06-01 23:40:22.000000000 +0200
@@ -126,6 +126,27 @@
#define _sx_assert(sx, what, file, line)
#endif
+#ifdef ADAPTIVE_SX
+static __inline void
+sx_adapt_spin(struct sx *sx, volatile struct thread *owner)
+{
+ uint32_t backoff, tback;
+
+ /*
+ * Use a back-off counter in order to reduce caches traffic when
+ * reading the lock state.
+ */
+ for (backoff = LOCK_BACKOFF_INIT; owner ==
+ (struct thread *)SX_OWNER(sx->sx_lock) && TD_IS_RUNNING(owner);
+ backoff <<= LOCK_BACKOFF_SHIFT) {
+ if (backoff > LOCK_BACKOFF_CAP)
+ backoff = LOCK_BACKOFF_CAP;
+ for (tback = 0; tback != backoff; tback++)
+ cpu_spinwait();
+ }
+}
+#endif
+
void
assert_sx(struct lock_object *lock, int what)
{
@@ -466,9 +487,7 @@
"%s: spinning on %p held by %p",
__func__, sx, owner);
GIANT_SAVE();
- while (SX_OWNER(sx->sx_lock) == x &&
- TD_IS_RUNNING(owner))
- cpu_spinwait();
+ sx_adapt_spin(sx, owner);
continue;
}
}
@@ -693,9 +712,7 @@
"%s: spinning on %p held by %p",
__func__, sx, owner);
GIANT_SAVE();
- while (SX_OWNER(sx->sx_lock) == x &&
- TD_IS_RUNNING(owner))
- cpu_spinwait();
+ sx_adapt_spin(sx, owner);
continue;
}
}
--- /usr/src/sys/sys/lock.h 2008-05-31 23:45:13.000000000 +0200
+++ sys/sys/lock.h 2008-06-02 12:45:35.000000000 +0200
@@ -186,6 +186,13 @@
#define MPASS4(ex, what, file, line) \
KASSERT((ex), ("Assertion %s failed at %s:%d", what, file, line))
+/*
+ * Back-off counters handling macros.
+ */
+#define LOCK_BACKOFF_CAP 0x40000
+#define LOCK_BACKOFF_INIT 0x01
+#define LOCK_BACKOFF_SHIFT 0x01
+
extern struct lock_class lock_class_mtx_sleep;
extern struct lock_class lock_class_mtx_spin;
extern struct lock_class lock_class_sx;