Changes from v10:
----------------
- Revise the scan function to move waiters into the secondary queue
one at a time. This way, the worst case complexity of cna_order_queue()
decreases from O(n) down to O(1), as we always “scan" only one waiter.
- Make the decision on when to flush the secondary queue and
force lock transition to a waiter on a different NUMA node to be
timer-based rather than a counter-based one, as suggested in a patch
povided by Longman.
- Make prioritized waiters to inherit the NUMA node id of the primary
queue, to maintain the preference even if the prioritized waiter is on a
different node. This is based on the patch provided by Longman.
The relative performance numbers with the revised series (included below)
have not changed much.
Summary
-------
Lock throughput can be increased by handing a lock to a waiter on the
same NUMA node as the lock holder, provided care is taken to avoid
starvation of waiters on other NUMA nodes. This patch introduces CNA
(compact NUMA-aware lock) as the slow path for qspinlock. It is
enabled through a configuration option (NUMA_AWARE_SPINLOCKS).
CNA is a NUMA-aware version of the MCS lock. Spinning threads are
organized in two queues, a primary queue for threads running on the same
node as the current lock holder, and a secondary queue for threads
running on other nodes. Threads store the ID of the node on which
they are running in their queue nodes. After acquiring the MCS lock and
before acquiring the spinlock, the MCS lock holder checks whether the next
waiter in the primary queue (if exists) is running on the same NUMA node.
If it is not, that waiter is detached from the main queue and moved into
the tail of the secondary queue. This way, we gradually filter the primary
queue, leaving only waiters running on the same preferred NUMA node. Note
that certain priortized waiters (e.g., in irq and nmi contexts) are
excluded from being moved to the secondary queue. We change the NUMA node
preference after a waiter at the head of the secondary queue spins for a
certain amount of time. We do that by flushing the secondary queue into
the head of the primary queue, effectively changing the preference to the
NUMA node of the waiter at the head of the secondary queue at the time of
the flush.
More details are available at https://arxiv.org/abs/1810.05600.
We have done some performance evaluation with the locktorture module
as well as with several benchmarks from the will-it-scale repo.
The following locktorture results are from an Oracle X5-4 server
(four Intel Xeon E7-8895 v3 @ 2.60GHz sockets with 18 hyperthreaded
cores each). Each number represents an average (over 25 runs) of the
total number of ops (x10^7) reported at the end of each run. The
standard deviation is also reported in (), and in general is about 3%
from the average. The 'stock' kernel is v5.9.0-rc4,
commit f4d51dffc6c0, compiled in the default configuration.
'patch-CNA' is the modified kernel with NUMA_AWARE_SPINLOCKS set;
the speedup is calculated dividing 'patch-CNA' by 'stock'.
#thr stock patch-CNA speedup (patch-CNA/stock)
1 2.682 (0.100) 2.695 (0.075) 1.005
2 2.810 (0.155) 2.797 (0.145) 0.995
4 4.273 (0.134) 4.294 (0.159) 1.005
8 5.071 (0.108) 6.755 (0.198) 1.332
16 5.840 (0.125) 8.940 (0.188) 1.531
32 6.246 (0.113) 9.866 (0.220) 1.580
36 6.355 (0.096) 9.968 (0.215) 1.569
72 6.129 (0.116) 10.231 (0.210) 1.669
108 5.921 (0.084) 10.246 (0.208) 1.731
142 5.763 (0.089) 10.186 (0.238) 1.768
The following tables contain throughput results (ops/us) from the same
setup for will-it-scale/open1_threads:
#thr stock patch-CNA speedup (patch-CNA/stock)
1 0.498 (0.003) 0.513 (0.001) 1.029
2 0.793 (0.014) 0.803 (0.017) 1.012
4 1.429 (0.027) 1.455 (0.027) 1.019
8 1.667 (0.089) 1.687 (0.132) 1.012
16 1.785 (0.047) 1.716 (0.068) 0.961
32 1.000 (0.064) 1.738 (0.107) 1.737
36 0.934 (0.073) 1.744 (0.076) 1.867
72 0.823 (0.043) 1.651 (0.071) 2.007
108 0.821 (0.031) 1.695 (0.063) 2.065
142 0.787 (0.027) 1.723 (0.069) 2.190
and will-it-scale/lock2_threads:
#thr stock patch-CNA speedup (patch-CNA/stock)
1 1.600 (0.002) 1.614 (0.004) 1.009
2 2.792 (0.066) 2.813 (0.060) 1.007
4 5.395 (0.379) 5.210 (0.500) 0.966
8 4.285 (0.278) 4.125 (0.413) 0.963
16 4.168 (0.134) 3.960 (0.146) 0.950
32 2.450 (0.106) 3.999 (0.141) 1.632
36 2.403 (0.106) 3.922 (0.106) 1.632
72 1.842 (0.098) 3.913 (0.091) 2.124
108 1.888 (0.116) 3.937 (0.074) 2.085
142 1.806 (0.113) 3.894 (0.107) 2.156
Our evaluation shows that CNA also improves performance of user
applications that have hot pthread mutexes. Those mutexes are
blocking, and waiting threads park and unpark via the futex
mechanism in the kernel. Given that kernel futex chains, which
are hashed by the mutex address, are each protected by a
chain-specific spin lock, the contention on a user-mode mutex
translates into contention on a kernel level spinlock.
Here are the results for the leveldb ‘readrandom’ benchmark:
#thr stock patch-CNA speedup (patch-CNA/stock)
1 0.529 (0.023) 0.525 (0.029) 0.993
2 0.829 (0.045) 0.847 (0.036) 1.021
4 1.122 (0.112) 1.144 (0.132) 1.020
8 1.126 (0.145) 1.124 (0.186) 0.998
16 1.029 (0.145) 1.207 (0.024) 1.173
32 0.721 (0.037) 1.158 (0.026) 1.605
36 0.690 (0.043) 1.159 (0.028) 1.680
72 0.622 (0.016) 1.136 (0.020) 1.826
108 0.608 (0.013) 1.144 (0.017) 1.882
142 0.602 (0.014) 1.122 (0.020) 1.864
Further comments are welcome and appreciated.
Alex Kogan (5):
locking/qspinlock: Rename mcs lock/unlock macros and make them more
generic
locking/qspinlock: Refactor the qspinlock slow path
locking/qspinlock: Introduce CNA into the slow path of qspinlock
locking/qspinlock: Introduce starvation avoidance into CNA
locking/qspinlock: Avoid moving certain threads between waiting queues
in CNA
.../admin-guide/kernel-parameters.txt | 19 +
arch/arm/include/asm/mcs_spinlock.h | 6 +-
arch/x86/Kconfig | 20 +
arch/x86/include/asm/qspinlock.h | 4 +
arch/x86/kernel/alternative.c | 4 +
include/asm-generic/mcs_spinlock.h | 4 +-
kernel/locking/mcs_spinlock.h | 20 +-
kernel/locking/qspinlock.c | 82 +++-
kernel/locking/qspinlock_cna.h | 421 ++++++++++++++++++
kernel/locking/qspinlock_paravirt.h | 2 +-
10 files changed, 559 insertions(+), 23 deletions(-)
create mode 100644 kernel/locking/qspinlock_cna.h
--
2.21.1 (Apple Git-122.3)
Move some of the code manipulating the spin lock into separate functions.
This would allow easier integration of alternative ways to manipulate
that lock.
Signed-off-by: Alex Kogan <[email protected]>
Reviewed-by: Steve Sistare <[email protected]>
Reviewed-by: Waiman Long <[email protected]>
---
kernel/locking/qspinlock.c | 38 ++++++++++++++++++++++++++++++++++++--
1 file changed, 36 insertions(+), 2 deletions(-)
diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 435d696f9250..24b5802fc6f1 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -289,6 +289,34 @@ static __always_inline u32 __pv_wait_head_or_lock(struct qspinlock *lock,
#define queued_spin_lock_slowpath native_queued_spin_lock_slowpath
#endif
+/*
+ * __try_clear_tail - try to clear tail by setting the lock value to
+ * _Q_LOCKED_VAL.
+ * @lock: Pointer to the queued spinlock structure
+ * @val: Current value of the lock
+ * @node: Pointer to the MCS node of the lock holder
+ */
+static __always_inline bool __try_clear_tail(struct qspinlock *lock,
+ u32 val,
+ struct mcs_spinlock *node)
+{
+ return atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL);
+}
+
+/*
+ * __mcs_lock_handoff - pass the MCS lock to the next waiter
+ * @node: Pointer to the MCS node of the lock holder
+ * @next: Pointer to the MCS node of the first waiter in the MCS queue
+ */
+static __always_inline void __mcs_lock_handoff(struct mcs_spinlock *node,
+ struct mcs_spinlock *next)
+{
+ arch_mcs_lock_handoff(&next->locked, 1);
+}
+
+#define try_clear_tail __try_clear_tail
+#define mcs_lock_handoff __mcs_lock_handoff
+
#endif /* _GEN_PV_LOCK_SLOWPATH */
/**
@@ -533,7 +561,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
* PENDING will make the uncontended transition fail.
*/
if ((val & _Q_TAIL_MASK) == tail) {
- if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
+ if (try_clear_tail(lock, val, node))
goto release; /* No contention */
}
@@ -550,7 +578,7 @@ void queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
if (!next)
next = smp_cond_load_relaxed(&node->next, (VAL));
- arch_mcs_lock_handoff(&next->locked, 1);
+ mcs_lock_handoff(node, next);
pv_kick_node(lock, next);
release:
@@ -575,6 +603,12 @@ EXPORT_SYMBOL(queued_spin_lock_slowpath);
#undef pv_kick_node
#undef pv_wait_head_or_lock
+#undef try_clear_tail
+#define try_clear_tail __try_clear_tail
+
+#undef mcs_lock_handoff
+#define mcs_lock_handoff __mcs_lock_handoff
+
#undef queued_spin_lock_slowpath
#define queued_spin_lock_slowpath __pv_queued_spin_lock_slowpath
--
2.21.1 (Apple Git-122.3)
Prohibit moving certain threads (e.g., in irq and nmi contexts)
to the secondary queue. Those prioritized threads will always stay
in the primary queue, and so will have a shorter wait time for the lock.
Signed-off-by: Alex Kogan <[email protected]>
Reviewed-by: Steve Sistare <[email protected]>
Reviewed-by: Waiman Long <[email protected]>
---
kernel/locking/qspinlock_cna.h | 26 ++++++++++++++++++++------
1 file changed, 20 insertions(+), 6 deletions(-)
diff --git a/kernel/locking/qspinlock_cna.h b/kernel/locking/qspinlock_cna.h
index d3e27549c769..ac3109ab0a84 100644
--- a/kernel/locking/qspinlock_cna.h
+++ b/kernel/locking/qspinlock_cna.h
@@ -4,6 +4,7 @@
#endif
#include <linux/topology.h>
+#include <linux/sched/rt.h>
/*
* Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock).
@@ -35,7 +36,8 @@
* running on the same NUMA node. If it is not, that waiter is detached from the
* main queue and moved into the tail of the secondary queue. This way, we
* gradually filter the primary queue, leaving only waiters running on the same
- * preferred NUMA node.
+ * preferred NUMA node. Note that certain priortized waiters (e.g., in
+ * irq and nmi contexts) are excluded from being moved to the secondary queue.
*
* We change the NUMA node preference after a waiter at the head of the
* secondary queue spins for a certain amount of time (10ms, by default).
@@ -49,6 +51,8 @@
* Dave Dice <[email protected]>
*/
+#define CNA_PRIORITY_NODE 0xffff
+
struct cna_node {
struct mcs_spinlock mcs;
u16 numa_node;
@@ -121,9 +125,10 @@ static int __init cna_init_nodes(void)
static __always_inline void cna_init_node(struct mcs_spinlock *node)
{
+ bool priority = !in_task() || irqs_disabled() || rt_task(current);
struct cna_node *cn = (struct cna_node *)node;
- cn->numa_node = cn->real_numa_node;
+ cn->numa_node = priority ? CNA_PRIORITY_NODE : cn->real_numa_node;
cn->start_time = 0;
}
@@ -262,11 +267,13 @@ static u32 cna_order_queue(struct mcs_spinlock *node)
next_numa_node = ((struct cna_node *)next)->numa_node;
if (next_numa_node != numa_node) {
- struct mcs_spinlock *nnext = READ_ONCE(next->next);
+ if (next_numa_node != CNA_PRIORITY_NODE) {
+ struct mcs_spinlock *nnext = READ_ONCE(next->next);
- if (nnext) {
- cna_splice_next(node, next, nnext);
- next = nnext;
+ if (nnext) {
+ cna_splice_next(node, next, nnext);
+ next = nnext;
+ }
}
/*
* Inherit NUMA node id of primary queue, to maintain the
@@ -284,6 +291,13 @@ static __always_inline u32 cna_wait_head_or_lock(struct qspinlock *lock,
struct cna_node *cn = (struct cna_node *)node;
if (!cn->start_time || !intra_node_threshold_reached(cn)) {
+ /*
+ * We are at the head of the wait queue, no need to use
+ * the fake NUMA node ID.
+ */
+ if (cn->numa_node == CNA_PRIORITY_NODE)
+ cn->numa_node = cn->real_numa_node;
+
/*
* Try and put the time otherwise spent spin waiting on
* _Q_LOCKED_PENDING_MASK to use by sorting our lists.
--
2.21.1 (Apple Git-122.3)