On 7/15/19 3:25 PM, Alex Kogan wrote: > +/* > + * 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 > + * threads running on the same node as the current lock holder, and a > + * secondary queue for threads running on other nodes. At the unlock time, > + * the lock holder scans the main queue looking for a thread running on > + * the same node. If found (call it thread T), all threads in the main queue > + * between the current lock holder and T are moved to the end of the > + * secondary queue, and the lock is passed to T. If such T is not found, the > + * lock is passed to the first node in the secondary queue. Finally, if the > + * secondary queue is empty, the lock is passed to the next thread in the > + * main queue. To avoid starvation of threads in the secondary queue, > + * those threads are moved back to the head of the main queue > + * after a certain expected number of intra-node lock hand-offs. > + * > + * For more details, see https://arxiv.org/abs/1810.05600. > + * > + * Authors: Alex Kogan <alex.kogan@xxxxxxxxxx> > + * Dave Dice <dave.dice@xxxxxxxxxx> > + */ > + > +struct cna_node { > + struct mcs_spinlock mcs; > + u32 numa_node; > + u32 encoded_tail; > + struct cna_node *tail; /* points to the secondary queue tail */ > +}; > + > +#define CNA_NODE(ptr) ((struct cna_node *)(ptr)) > + > +static void cna_init_node(struct mcs_spinlock *node) > +{ > + struct cna_node *cn = CNA_NODE(node); > + struct mcs_spinlock *base_node; > + int cpuid; > + > + BUILD_BUG_ON(sizeof(struct cna_node) > sizeof(struct qnode)); > + /* we store a pointer in the node's @locked field */ > + BUILD_BUG_ON(sizeof(uintptr_t) > sizeof_field(struct mcs_spinlock, locked)); > + > + cpuid = smp_processor_id(); > + cn->numa_node = cpu_to_node(cpuid); > + > + base_node = this_cpu_ptr(&qnodes[0].mcs); > + cn->encoded_tail = encode_tail(cpuid, base_node->count - 1); > +} > + > +/** > + * find_successor - Scan the main waiting queue looking for the first > + * thread running on the same 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 T; otherwise, return NULL. > + */ Here you talk about main and secondary queues. However, there is no mention of what are those queues. As I am familiar with qspinlock queue, I can figure out that the main queue is the mcs_node->next chain that starts from the MCS lock holder. The secondary queue is a separate MCS node chain with its head stored in the mcs_node->locked value of the MCS lock holder and the tail stored in the cna->tail. More detail comments on what and where they are will help to improve the readability of the code. A simple graphic to illustrate those queues will help too, for example /* * MCS lock holder * =============== * mcs_node * +--------+ +----+ +----+ * | next | ---> |next| -> ... |next| -> NULL [Main queue] * | locked | -+ +----+ +----+ * +--------+ | * | +----+ +----+ * +-> |next| -> ... |next| -> X [Secondary queue] * cna_node +----+ +----+ * +--------* ^ * | tail | ----------------------+ * +--------* * * N.B. locked = 1 if secondary queue is absent. */ > +static struct cna_node *find_successor(struct mcs_spinlock *me) > +{ > + struct cna_node *me_cna = CNA_NODE(me); > + struct cna_node *head_other, *tail_other, *cur; As you have talked about secondary queue, how about head_2nd, tail_2nd instead of *_other? Cheers, Longman
