Re: [PATCH v7 3/5] locking/qspinlock: Introduce CNA into the slow path of qspinlock

Peter Zijlstra
2020-01-21T20:29:58Z

various notes and changes in the below.

---

Index: linux-2.6/kernel/locking/qspinlock.c
===================================================================
--- linux-2.6.orig/kernel/locking/qspinlock.c
+++ linux-2.6/kernel/locking/qspinlock.c
@@ -598,10 +598,10 @@ EXPORT_SYMBOL(queued_spin_lock_slowpath)
#define _GEN_CNA_LOCK_SLOWPATH

#undef pv_wait_head_or_lock
-#define pv_wait_head_or_lock cna_pre_scan
+#define pv_wait_head_or_lock cna_wait_head_or_lock

#undef try_clear_tail
-#define try_clear_tail cna_try_change_tail
+#define try_clear_tail cna_try_clear_tail

#undef mcs_pass_lock
#define mcs_pass_lock cna_pass_lock
Index: linux-2.6/kernel/locking/qspinlock_cna.h
===================================================================
--- linux-2.6.orig/kernel/locking/qspinlock_cna.h
+++ linux-2.6/kernel/locking/qspinlock_cna.h
@@ -8,37 +8,37 @@
/*
* Implement a NUMA-aware version of MCS (aka CNA, or compact NUMA-aware lock).
*
- * In CNA, spinning threads are organized in two queues, a main queue for
+ * In CNA, spinning threads are organized in two queues, a primary queue for
* threads running on the same NUMA node as the current lock holder, and a
- * secondary queue for threads running on other nodes. Schematically, it
- * looks like this:
+ * secondary queue for threads running on other nodes. Schematically, it looks
+ * like this:
*
* cna_node
- * +----------+ +--------+ +--------+
- * |mcs:next | -> |mcs:next| -> ... |mcs:next| -> NULL [Main queue]
- * |mcs:locked| -+ +--------+ +--------+
+ * +----------+ +--------+ +--------+
+ * |mcs:next | --> |mcs:next| --> ... |mcs:next| --> NULL [Primary queue]
+ * |mcs:locked| -. +--------+ +--------+
* +----------+ |
- * +----------------------+
- * \/
+ * `----------------------.
+ * v
* +--------+ +--------+
- * |mcs:next| -> ... |mcs:next| [Secondary queue]
+ * |mcs:next| --> ... |mcs:next| [Secondary queue]
* +--------+ +--------+
* ^ |
- * +--------------------+
+ * `--------------------'
*
- * N.B. locked = 1 if secondary queue is absent. Othewrise, it contains the
+ * N.B. locked := 1 if secondary queue is absent. Othewrise, it contains the
* encoded pointer to the tail of the secondary queue, which is organized as a
* circular list.
*
* After acquiring the MCS lock and before acquiring the spinlock, the lock
- * holder scans the main queue looking for a thread running on the same node
- * (pre-scan). If found (call it thread T), all threads in the main queue
+ * holder scans the primary queue looking for a thread running on the same node
+ * (pre-scan). If found (call it thread T), all threads in the primary queue
* between the current lock holder and T are moved to the end of the secondary
- * queue. If such T is not found, we make another scan of the main queue when
- * unlocking the MCS lock (post-scan), starting at the node where pre-scan
+ * queue. If such T is not found, we make another scan of the primary queue
+ * when unlocking the MCS lock (post-scan), starting at the node where pre-scan
* stopped. If both scans fail to find such T, the MCS lock is passed to the
* first thread in the secondary queue. If the secondary queue is empty, the
- * lock is passed to the next thread in the main queue.
+ * lock is passed to the next thread in the primary queue.
*
* For more details, see https://arxiv.org/abs/1810.05600.
*
@@ -49,8 +49,8 @@
struct cna_node {
struct mcs_spinlock mcs;
int numa_node;
- u32 encoded_tail;
- u32 pre_scan_result; /* 0 or encoded tail */
+ u32 encoded_tail; /* self */
+ u32 partial_order;
};

static void __init cna_init_nodes_per_cpu(unsigned int cpu)
@@ -66,7 +66,7 @@ static void __init cna_init_nodes_per_cp
cn->encoded_tail = encode_tail(cpu, i);
/*
* @encoded_tail has to be larger than 1, so we do not confuse
- * it with other valid values for @locked or @pre_scan_result
+ * it with other valid values for @locked or @partial_order
* (0 or 1)
*/
WARN_ON(cn->encoded_tail <= 1);
@@ -92,8 +92,8 @@ static int __init cna_init_nodes(void)
}
early_initcall(cna_init_nodes);

-static inline bool cna_try_change_tail(struct qspinlock *lock, u32 val,
- struct mcs_spinlock *node)
+static inline bool cna_try_clear_tail(struct qspinlock *lock, u32 val,
+ struct mcs_spinlock *node)
{
struct mcs_spinlock *head_2nd, *tail_2nd;
u32 new;
@@ -106,7 +106,9 @@ static inline bool cna_try_change_tail(s
* Try to update the tail value to the last node in the secondary queue.
* If successful, pass the lock to the first thread in the secondary
* queue. Doing those two actions effectively moves all nodes from the
- * secondary queue into the main one.
+ * secondary queue into the primary one.
+ *
+ * XXX: reformulate, that's just confusing.
*/
tail_2nd = decode_tail(node->locked);
head_2nd = tail_2nd->next;
@@ -116,6 +118,9 @@ static inline bool cna_try_change_tail(s
/*
* Try to reset @next in tail_2nd to NULL, but no need to check
* the result - if failed, a new successor has updated it.
+ *
+ * XXX: figure out what how where..
+ * XXX: cns_pass_lock() does something relared
*/
cmpxchg_relaxed(&tail_2nd->next, head_2nd, NULL);
arch_mcs_pass_lock(&head_2nd->locked, 1);
@@ -126,7 +131,7 @@ static inline bool cna_try_change_tail(s
}

/*
- * cna_splice_tail -- splice nodes in the main queue between [first, last]
+ * cna_splice_tail -- splice nodes in the primary queue between [first, last]
* onto the secondary queue.
*/
static void cna_splice_tail(struct mcs_spinlock *node,
@@ -153,77 +158,56 @@ static void cna_splice_tail(struct mcs_s
}

/*
- * cna_scan_main_queue - scan the main waiting queue looking for the first
- * thread running on the same NUMA node as the lock holder. If found (call it
- * thread T), move all threads in the main queue between the lock holder and
- * T to the end of the secondary queue and return 0; otherwise, return the
- * encoded pointer of the last scanned node in the primary queue (so a
- * subsequent scan can be resumed from that node)
+ * cna_order_queue - scan the primary queue looking for the first lock node on
+ * the same NUMA node as the lock holder and move any skipped nodes onto the
+ * secondary queue.
*
- * Schematically, this may look like the following (nn stands for numa_node and
- * et stands for encoded_tail).
- *
- * when cna_scan_main_queue() is called (the secondary queue is empty):
- *
- * A+------------+ B+--------+ C+--------+ T+--------+
- * |mcs:next | -> |mcs:next| -> |mcs:next| -> |mcs:next| -> NULL
- * |mcs:locked=1| |cna:nn=0| |cna:nn=2| |cna:nn=1|
- * |cna:nn=1 | +--------+ +--------+ +--------+
- * +----------- +
- *
- * when cna_scan_main_queue() returns (the secondary queue contains B and C):
- *
- * A+----------------+ T+--------+
- * |mcs:next | -> |mcs:next| -> NULL
- * |mcs:locked=C.et | -+ |cna:nn=1|
- * |cna:nn=1 | | +--------+
- * +--------------- + +-----+
- * \/
- * B+--------+ C+--------+
- * |mcs:next| -> |mcs:next| -+
- * |cna:nn=0| |cna:nn=2| |
- * +--------+ +--------+ |
- * ^ |
- * +---------------------+
+ * Returns 0 if a matching node is found; otherwise return the encoded pointer
+ * to the last element inspected (such that a subsequent scan can continue there).
*
* The worst case complexity of the scan is O(n), where n is the number
* of current waiters. However, the amortized complexity is close to O(1),
* as the immediate successor is likely to be running on the same node once
* threads from other nodes are moved to the secondary queue.
+ *
+ * XXX does not compute; given equal contention it should average to O(nr_nodes).
*/
-static u32 cna_scan_main_queue(struct mcs_spinlock *node,
- struct mcs_spinlock *pred_start)
+static u32 cna_order_queue(struct mcs_spinlock *node,
+ struct mcs_spinlock *iter)
{
+ struct cna_node *cni = (struct cna_node *)READ_ONCE(iter->next);
struct cna_node *cn = (struct cna_node *)node;
- struct cna_node *cni = (struct cna_node *)READ_ONCE(pred_start->next);
+ int nid = cn->numa_node;
struct cna_node *last;
- int my_numa_node = cn->numa_node;

/* find any next waiter on 'our' NUMA node */
for (last = cn;
- cni && cni->numa_node != my_numa_node;
+ cni && cni->numa_node != nid;
last = cni, cni = (struct cna_node *)READ_ONCE(cni->mcs.next))
;

- /* if found, splice any skipped waiters onto the secondary queue */
- if (cni) {
- if (last != cn) /* did we skip any waiters? */
- cna_splice_tail(node, node->next,
- (struct mcs_spinlock *)last);
- return 0;
- }
+ if (!cna)
+ return last->encoded_tail; /* continue from here */
+
+ if (last != cn) /* did we skip any waiters? */
+ cna_splice_tail(node, node->next, (struct mcs_spinlock *)last);

- return last->encoded_tail;
+ return 0;
}

-__always_inline u32 cna_pre_scan(struct qspinlock *lock,
- struct mcs_spinlock *node)
+/* abuse the pv_wait_head_or_lock() hook to get some work done */
+static __always_inline u32 cna_wait_head_or_lock(struct qspinlock *lock,
+ struct mcs_spinlock *node)
{
struct cna_node *cn = (struct cna_node *)node;

- cn->pre_scan_result = cna_scan_main_queue(node, node);
+ /*
+ * Try and put the time otherwise spend spin waiting on
+ * _Q_LOCKED_PENDING_MASK to use by sorting our lists.
+ */
+ cn->partial_order = cna_order_queue(node, node);

- return 0;
+ return 0; /* we lied; we didn't wait, go do so now */
}

static inline void cna_pass_lock(struct mcs_spinlock *node,
@@ -231,33 +215,27 @@ static inline void cna_pass_lock(struct
{
struct cna_node *cn = (struct cna_node *)node;
struct mcs_spinlock *next_holder = next, *tail_2nd;
- u32 val = 1;
+ u32 partial_order = cn->partial_order;
+ u32 val = _Q_LOCKED_VAL;

- u32 scan = cn->pre_scan_result;
+ /* cna_wait_head_or_lock() left work for us. */
+ if (partial_order) {
+ partial_order = cna_order_queue(node, decode_tail(partial_order));

- /*
- * check if a successor from the same numa node has not been found in
- * pre-scan, and if so, try to find it in post-scan starting from the
- * node where pre-scan stopped (stored in @pre_scan_result)
- */
- if (scan > 0)
- scan = cna_scan_main_queue(node, decode_tail(scan));
-
- if (!scan) { /* if found a successor from the same numa node */
+ if (!partial_order) { /* ordered; use primary queue */
next_holder = node->next;
- /*
- * we unlock successor by passing a non-zero value,
- * so set @val to 1 iff @locked is 0, which will happen
- * if we acquired the MCS lock when its queue was empty
- */
- val = node->locked ? node->locked : 1;
- } else if (node->locked > 1) { /* if secondary queue is not empty */
+ val |= node->locked; /* preseve secondary queue */
+
+ } else if (node->locked > 1) { /* try secondary queue */
+
/* next holder will be the first node in the secondary queue */
tail_2nd = decode_tail(node->locked);
/* @tail_2nd->next points to the head of the secondary queue */
next_holder = tail_2nd->next;
- /* splice the secondary queue onto the head of the main queue */
+ /* splice the secondary queue onto the head of the primary queue */
tail_2nd->next = next;
+
+ // XXX cna_try_clear_tail also does something like this
}

arch_mcs_pass_lock(&next_holder->locked, val);