[PATCH v5 5/5] lib/dlock-list: Make sibling CPUs share the same linked list

[Waiman Long]

The dlock list needs one list for each of the CPUs available. However,
for sibling CPUs, they are sharing the L2 and probably L1 caches
too. As a result, there is not much to gain in term of avoiding
cacheline contention while increasing the cacheline footprint of the
L1/L2 caches as separate lists may need to be in the cache.

This patch makes all the sibling CPUs share the same list, thus
reducing the number of lists that need to be maintained in each
dlock list without having any noticeable impact on performance. It
also improves dlock list iteration performance as fewer lists need
to be iterated.

Signed-off-by: Waiman Long <Waiman.Long@xxxxxxx>
---
 include/linux/dlock-list.h |    3 ++
 lib/dlock-list.c           |   79 +++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 77 insertions(+), 5 deletions(-)

diff --git a/include/linux/dlock-list.h b/include/linux/dlock-list.h
index 19f897e..f5d4251 100644
--- a/include/linux/dlock-list.h
+++ b/include/linux/dlock-list.h
@@ -39,6 +39,7 @@ struct dlock_list_head {
 
 struct dlock_list_heads {
 	struct dlock_list_head *heads;
+	int nhead;
 };
 
 /*
@@ -58,6 +59,7 @@ struct dlock_list_node {
  */
 struct dlock_list_iter {
 	int index;
+	int nhead;
 	struct dlock_list_head *head, *entry;
 };
 
@@ -65,6 +67,7 @@ struct dlock_list_iter {
 	{					\
 		.index = -1,			\
 		.head = (dlist)->heads,		\
+		.nhead = (dlist)->nhead,	\
 	}
 
 #define DEFINE_DLOCK_LIST_ITER(s, heads)	\
diff --git a/lib/dlock-list.c b/lib/dlock-list.c
index 9d4950c..b8b3524 100644
--- a/lib/dlock-list.c
+++ b/lib/dlock-list.c
@@ -28,6 +28,71 @@
  */
 static struct lock_class_key dlock_list_key;
 
+/*
+ * Mapping CPU number to dlock list index.
+ */
+static DEFINE_PER_CPU_READ_MOSTLY(int, cpu2list);
+static int nr_dlists;
+
+/*
+ * Initialize cpu2list mapping table & nr_dlists;
+ *
+ * All the sibling CPUs of a sibling group will map to the same dlock list so
+ * as to reduce the number of dlock lists to be maintained while minimizing
+ * cacheline contention.
+ *
+ * As the sibling masks are set up in the core initcall phase, this function
+ * has to be done in the postcore phase to get the right data. An alloc can
+ * be called before init. In this case, we just do a simple 1-1 mapping
+ * between CPU and dlock list head. After init, multiple CPUs may map to the
+ * same dlock list head.
+ */
+static int __init cpu2list_init(void)
+{
+	int idx, cpu;
+	int nr_siblings;
+	cpumask_var_t sibling_mask;
+	static struct cpumask mask __initdata;
+
+	/*
+	 * Check # of sibling CPUs for CPU 0
+	 */
+	sibling_mask = topology_sibling_cpumask(0);
+	if (!sibling_mask)
+		goto done;
+	nr_siblings = cpumask_weight(sibling_mask);
+	if (nr_siblings == 1)
+		goto done;
+
+	cpumask_setall(&mask);
+	idx = 0;
+	for_each_possible_cpu(cpu) {
+		int scpu;
+
+		if (!cpumask_test_cpu(cpu, &mask))
+			continue;
+		sibling_mask = topology_sibling_cpumask(cpu);
+		for_each_cpu(scpu, sibling_mask) {
+			per_cpu(cpu2list, scpu) = idx;
+			cpumask_clear_cpu(scpu, &mask);
+		}
+		idx++;
+	}
+
+	/*
+	 * nr_dlists can only be set after cpu2list_map is properly initialized.
+	 */
+	smp_mb();
+	nr_dlists = nr_cpu_ids/nr_siblings;
+
+	WARN_ON(cpumask_weight(&mask) != 0);
+	WARN_ON(idx > nr_dlists);
+	pr_info("dlock-list: %d head entries per dlock list.\n", nr_dlists);
+done:
+	return 0;
+}
+postcore_initcall(cpu2list_init);
+
 /**
  * alloc_dlock_list_heads - Initialize and allocate the list of head entries
  * @dlist: Pointer to the dlock_list_heads structure to be initialized
@@ -42,13 +107,14 @@ int alloc_dlock_list_heads(struct dlock_list_heads *dlist)
 {
 	int idx;
 
-	dlist->heads = kcalloc(nr_cpu_ids, sizeof(struct dlock_list_head),
+	dlist->nhead = nr_dlists ? nr_dlists : nr_cpu_ids;
+	dlist->heads = kcalloc(dlist->nhead, sizeof(struct dlock_list_head),
 			       GFP_KERNEL);
 
 	if (!dlist->heads)
 		return -ENOMEM;
 
-	for (idx = 0; idx < nr_cpu_ids; idx++) {
+	for (idx = 0; idx < dlist->nhead; idx++) {
 		struct dlock_list_head *head = &dlist->heads[idx];
 
 		INIT_LIST_HEAD(&head->list);
@@ -69,6 +135,7 @@ void free_dlock_list_heads(struct dlock_list_heads *dlist)
 {
 	kfree(dlist->heads);
 	dlist->heads = NULL;
+	dlist->nhead = 0;
 }
 
 /**
@@ -84,7 +151,7 @@ bool dlock_list_empty(struct dlock_list_heads *dlist)
 {
 	int idx;
 
-	for (idx = 0; idx < nr_cpu_ids; idx++)
+	for (idx = 0; idx < dlist->nhead; idx++)
 		if (!list_empty(&dlist->heads[idx].list))
 			return false;
 	return true;
@@ -102,7 +169,9 @@ bool dlock_list_empty(struct dlock_list_heads *dlist)
 void dlock_list_add(struct dlock_list_node *node,
 		    struct dlock_list_heads *dlist)
 {
-	struct dlock_list_head *head = &dlist->heads[smp_processor_id()];
+	int cpu = smp_processor_id();
+	int idx = (dlist->nhead < nr_cpu_ids) ? per_cpu(cpu2list, cpu) : cpu;
+	struct dlock_list_head *head = &dlist->heads[idx];
 
 	/*
 	 * There is no need to disable preemption
@@ -175,7 +244,7 @@ next_list:
 	/*
 	 * Try next list
 	 */
-	if (++iter->index >= nr_cpu_ids)
+	if (++iter->index >= iter->nhead)
 		return NULL;	/* All the entries iterated */
 
 	if (list_empty(&iter->head[iter->index].list))
-- 
1.7.1