aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMateusz Guzik <mjg@FreeBSD.org>2017-02-07 14:49:36 +0000
committerMateusz Guzik <mjg@FreeBSD.org>2017-02-07 14:49:36 +0000
commit8e5a3e9a9d926ac36fbc43133ed9e1d03e5d47e9 (patch)
tree9a9906685ffe17df8862adb359e8a58be41c303f
parent5267f6243d05744730cb1ab7be660d2f3972dda9 (diff)
downloadsrc-8e5a3e9a9d926ac36fbc43133ed9e1d03e5d47e9.tar.gz
src-8e5a3e9a9d926ac36fbc43133ed9e1d03e5d47e9.zip
locks: change backoff to exponential
Previous implementation would use a random factor to spread readers and reduce chances of starvation. This visibly reduces effectiveness of the mechanism. Switch to the more traditional exponential variant. Try to limit starvation by imposing an upper limit of spins after which spinning is half of what other threads get. Note the mechanism is turned off by default. Reviewed by: kib (previous version)
Notes
Notes: svn path=/head/; revision=313386
-rw-r--r--sys/kern/kern_mutex.c54
-rw-r--r--sys/kern/kern_rwlock.c24
-rw-r--r--sys/kern/kern_sx.c24
-rw-r--r--sys/kern/subr_lock.c62
-rw-r--r--sys/sys/lock.h14
5 files changed, 68 insertions, 110 deletions
diff --git a/sys/kern/kern_mutex.c b/sys/kern/kern_mutex.c
index e37fb34cd521..76617cf6b76f 100644
--- a/sys/kern/kern_mutex.c
+++ b/sys/kern/kern_mutex.c
@@ -140,63 +140,27 @@ struct lock_class lock_class_mtx_spin = {
#ifdef ADAPTIVE_MUTEXES
static SYSCTL_NODE(_debug, OID_AUTO, mtx, CTLFLAG_RD, NULL, "mtx debugging");
-static struct lock_delay_config __read_mostly mtx_delay = {
- .initial = 1000,
- .step = 500,
- .min = 100,
- .max = 5000,
-};
+static struct lock_delay_config __read_mostly mtx_delay;
-SYSCTL_INT(_debug_mtx, OID_AUTO, delay_initial, CTLFLAG_RW, &mtx_delay.initial,
- 0, "");
-SYSCTL_INT(_debug_mtx, OID_AUTO, delay_step, CTLFLAG_RW, &mtx_delay.step,
- 0, "");
-SYSCTL_INT(_debug_mtx, OID_AUTO, delay_min, CTLFLAG_RW, &mtx_delay.min,
+SYSCTL_INT(_debug_mtx, OID_AUTO, delay_base, CTLFLAG_RW, &mtx_delay.base,
0, "");
SYSCTL_INT(_debug_mtx, OID_AUTO, delay_max, CTLFLAG_RW, &mtx_delay.max,
0, "");
-static void
-mtx_delay_sysinit(void *dummy)
-{
-
- mtx_delay.initial = mp_ncpus * 25;
- mtx_delay.step = (mp_ncpus * 25) / 2;
- mtx_delay.min = mp_ncpus * 5;
- mtx_delay.max = mp_ncpus * 25 * 10;
-}
-LOCK_DELAY_SYSINIT(mtx_delay_sysinit);
+LOCK_DELAY_SYSINIT_DEFAULT(mtx_delay);
#endif
static SYSCTL_NODE(_debug, OID_AUTO, mtx_spin, CTLFLAG_RD, NULL,
"mtx spin debugging");
-static struct lock_delay_config __read_mostly mtx_spin_delay = {
- .initial = 1000,
- .step = 500,
- .min = 100,
- .max = 5000,
-};
+static struct lock_delay_config __read_mostly mtx_spin_delay;
-SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_initial, CTLFLAG_RW,
- &mtx_spin_delay.initial, 0, "");
-SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_step, CTLFLAG_RW, &mtx_spin_delay.step,
- 0, "");
-SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_min, CTLFLAG_RW, &mtx_spin_delay.min,
- 0, "");
-SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_max, CTLFLAG_RW, &mtx_spin_delay.max,
- 0, "");
+SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_base, CTLFLAG_RW,
+ &mtx_spin_delay.base, 0, "");
+SYSCTL_INT(_debug_mtx_spin, OID_AUTO, delay_max, CTLFLAG_RW,
+ &mtx_spin_delay.max, 0, "");
-static void
-mtx_spin_delay_sysinit(void *dummy)
-{
-
- mtx_spin_delay.initial = mp_ncpus * 25;
- mtx_spin_delay.step = (mp_ncpus * 25) / 2;
- mtx_spin_delay.min = mp_ncpus * 5;
- mtx_spin_delay.max = mp_ncpus * 25 * 10;
-}
-LOCK_DELAY_SYSINIT(mtx_spin_delay_sysinit);
+LOCK_DELAY_SYSINIT_DEFAULT(mtx_spin_delay);
/*
* System-wide mutexes
diff --git a/sys/kern/kern_rwlock.c b/sys/kern/kern_rwlock.c
index 0a59bf94f3f8..365c0c452b48 100644
--- a/sys/kern/kern_rwlock.c
+++ b/sys/kern/kern_rwlock.c
@@ -100,32 +100,14 @@ static SYSCTL_NODE(_debug, OID_AUTO, rwlock, CTLFLAG_RD, NULL,
SYSCTL_INT(_debug_rwlock, OID_AUTO, retry, CTLFLAG_RW, &rowner_retries, 0, "");
SYSCTL_INT(_debug_rwlock, OID_AUTO, loops, CTLFLAG_RW, &rowner_loops, 0, "");
-static struct lock_delay_config __read_mostly rw_delay = {
- .initial = 1000,
- .step = 500,
- .min = 100,
- .max = 5000,
-};
+static struct lock_delay_config __read_mostly rw_delay;
-SYSCTL_INT(_debug_rwlock, OID_AUTO, delay_initial, CTLFLAG_RW, &rw_delay.initial,
- 0, "");
-SYSCTL_INT(_debug_rwlock, OID_AUTO, delay_step, CTLFLAG_RW, &rw_delay.step,
- 0, "");
-SYSCTL_INT(_debug_rwlock, OID_AUTO, delay_min, CTLFLAG_RW, &rw_delay.min,
+SYSCTL_INT(_debug_rwlock, OID_AUTO, delay_base, CTLFLAG_RW, &rw_delay.base,
0, "");
SYSCTL_INT(_debug_rwlock, OID_AUTO, delay_max, CTLFLAG_RW, &rw_delay.max,
0, "");
-static void
-rw_delay_sysinit(void *dummy)
-{
-
- rw_delay.initial = mp_ncpus * 25;
- rw_delay.step = (mp_ncpus * 25) / 2;
- rw_delay.min = mp_ncpus * 5;
- rw_delay.max = mp_ncpus * 25 * 10;
-}
-LOCK_DELAY_SYSINIT(rw_delay_sysinit);
+LOCK_DELAY_SYSINIT_DEFAULT(rw_delay);
#endif
/*
diff --git a/sys/kern/kern_sx.c b/sys/kern/kern_sx.c
index c0fc26aabd32..777f31e535dc 100644
--- a/sys/kern/kern_sx.c
+++ b/sys/kern/kern_sx.c
@@ -148,32 +148,14 @@ static SYSCTL_NODE(_debug, OID_AUTO, sx, CTLFLAG_RD, NULL, "sxlock debugging");
SYSCTL_UINT(_debug_sx, OID_AUTO, retries, CTLFLAG_RW, &asx_retries, 0, "");
SYSCTL_UINT(_debug_sx, OID_AUTO, loops, CTLFLAG_RW, &asx_loops, 0, "");
-static struct lock_delay_config __read_mostly sx_delay = {
- .initial = 1000,
- .step = 500,
- .min = 100,
- .max = 5000,
-};
+static struct lock_delay_config __read_mostly sx_delay;
-SYSCTL_INT(_debug_sx, OID_AUTO, delay_initial, CTLFLAG_RW, &sx_delay.initial,
- 0, "");
-SYSCTL_INT(_debug_sx, OID_AUTO, delay_step, CTLFLAG_RW, &sx_delay.step,
- 0, "");
-SYSCTL_INT(_debug_sx, OID_AUTO, delay_min, CTLFLAG_RW, &sx_delay.min,
+SYSCTL_INT(_debug_sx, OID_AUTO, delay_base, CTLFLAG_RW, &sx_delay.base,
0, "");
SYSCTL_INT(_debug_sx, OID_AUTO, delay_max, CTLFLAG_RW, &sx_delay.max,
0, "");
-static void
-sx_delay_sysinit(void *dummy)
-{
-
- sx_delay.initial = mp_ncpus * 25;
- sx_delay.step = (mp_ncpus * 25) / 2;
- sx_delay.min = mp_ncpus * 5;
- sx_delay.max = mp_ncpus * 25 * 10;
-}
-LOCK_DELAY_SYSINIT(sx_delay_sysinit);
+LOCK_DELAY_SYSINIT_DEFAULT(sx_delay);
#endif
void
diff --git a/sys/kern/subr_lock.c b/sys/kern/subr_lock.c
index f83ba58f7aa4..2ed5fdb6bb72 100644
--- a/sys/kern/subr_lock.c
+++ b/sys/kern/subr_lock.c
@@ -56,6 +56,9 @@ __FBSDID("$FreeBSD$");
#include <machine/cpufunc.h>
+SDT_PROVIDER_DEFINE(lock);
+SDT_PROBE_DEFINE1(lock, , , starvation, "u_int");
+
CTASSERT(LOCK_CLASS_MAX == 15);
struct lock_class *lock_classes[LOCK_CLASS_MAX + 1] = {
@@ -103,32 +106,56 @@ lock_destroy(struct lock_object *lock)
lock->lo_flags &= ~LO_INITIALIZED;
}
+static SYSCTL_NODE(_debug, OID_AUTO, lock, CTLFLAG_RD, NULL, "lock debugging");
+static SYSCTL_NODE(_debug_lock, OID_AUTO, delay, CTLFLAG_RD, NULL,
+ "lock delay");
+
+static u_int __read_mostly starvation_limit = 131072;
+SYSCTL_INT(_debug_lock_delay, OID_AUTO, starvation_limit, CTLFLAG_RW,
+ &starvation_limit, 0, "");
+
+static u_int __read_mostly restrict_starvation = 0;
+SYSCTL_INT(_debug_lock_delay, OID_AUTO, restrict_starvation, CTLFLAG_RW,
+ &restrict_starvation, 0, "");
+
void
lock_delay(struct lock_delay_arg *la)
{
- u_int i, delay, backoff, min, max;
struct lock_delay_config *lc = la->config;
+ u_int i;
- delay = la->delay;
+ la->delay <<= 1;
+ if (__predict_false(la->delay > lc->max))
+ la->delay = lc->max;
- if (delay == 0)
- delay = lc->initial;
- else {
- delay += lc->step;
- max = lc->max;
- if (delay > max)
- delay = max;
+ for (i = la->delay; i > 0; i++)
+ cpu_spinwait();
+
+ la->spin_cnt += la->delay;
+ if (__predict_false(la->spin_cnt > starvation_limit)) {
+ SDT_PROBE1(lock, , , starvation, la->delay);
+ if (restrict_starvation)
+ la->delay = lc->base;
}
+}
- backoff = cpu_ticks() % delay;
- min = lc->min;
- if (backoff < min)
- backoff = min;
- for (i = 0; i < backoff; i++)
- cpu_spinwait();
+static u_int
+lock_roundup_2(u_int val)
+{
+ u_int res;
+
+ for (res = 1; res <= val; res <<= 1)
+ continue;
+
+ return (res);
+}
- la->delay = delay;
- la->spin_cnt += backoff;
+void
+lock_delay_default_init(struct lock_delay_config *lc)
+{
+
+ lc->base = lock_roundup_2(mp_ncpus) / 4;
+ lc->max = lc->base * 1024;
}
#ifdef DDB
@@ -655,7 +682,6 @@ out:
critical_exit();
}
-static SYSCTL_NODE(_debug, OID_AUTO, lock, CTLFLAG_RD, NULL, "lock debugging");
static SYSCTL_NODE(_debug_lock, OID_AUTO, prof, CTLFLAG_RD, NULL,
"lock profiling");
SYSCTL_INT(_debug_lock_prof, OID_AUTO, skipspin, CTLFLAG_RW,
diff --git a/sys/sys/lock.h b/sys/sys/lock.h
index dbe715a31540..89b61ab73ddd 100644
--- a/sys/sys/lock.h
+++ b/sys/sys/lock.h
@@ -202,9 +202,7 @@ extern struct lock_class lock_class_lockmgr;
extern struct lock_class *lock_classes[];
struct lock_delay_config {
- u_int initial;
- u_int step;
- u_int min;
+ u_int base;
u_int max;
};
@@ -215,19 +213,25 @@ struct lock_delay_arg {
};
static inline void
-lock_delay_arg_init(struct lock_delay_arg *la, struct lock_delay_config *lc) {
+lock_delay_arg_init(struct lock_delay_arg *la, struct lock_delay_config *lc)
+{
la->config = lc;
- la->delay = 0;
+ la->delay = lc->base;
la->spin_cnt = 0;
}
#define LOCK_DELAY_SYSINIT(func) \
SYSINIT(func##_ld, SI_SUB_LOCK, SI_ORDER_ANY, func, NULL)
+#define LOCK_DELAY_SYSINIT_DEFAULT(lc) \
+ SYSINIT(lock_delay_##lc##_ld, SI_SUB_LOCK, SI_ORDER_ANY, \
+ lock_delay_default_init, &lc)
+
void lock_init(struct lock_object *, struct lock_class *,
const char *, const char *, int);
void lock_destroy(struct lock_object *);
void lock_delay(struct lock_delay_arg *);
+void lock_delay_default_init(struct lock_delay_config *);
void spinlock_enter(void);
void spinlock_exit(void);
void witness_init(struct lock_object *, const char *);