On Mon, Nov 14, 2022 at 04:32:10PM +0200, Andy Shevchenko wrote:

On Sat, Nov 12, 2022 at 11:09:45AM -0800, Yury Norov wrote:

quoted

The function finds Nth set CPU in a given cpumask starting from a given
node.

Leveraging the fact that each hop in sched_domains_numa_masks includes the
same or greater number of CPUs than the previous one, we can use binary
search on hops instead of linear walk, which makes the overall complexity
of O(log n) in terms of number of cpumask_weight() calls.

...

quoted

+struct __cmp_key {
+	const struct cpumask *cpus;
+	struct cpumask ***masks;
+	int node;
+	int cpu;
+	int w;
+};
+
+static int cmp(const void *a, const void *b)

Calling them key and pivot (as in the caller), would make more sense.

quoted

+{

What about

	const (?) struct cpumask ***masks = (...)pivot;

quoted

+	struct cpumask **prev_hop = *((struct cpumask ***)b - 1);

	= masks[-1];

quoted

+	struct cpumask **cur_hop = *(struct cpumask ***)b;

	= masks[0];

?

quoted

+	struct __cmp_key *k = (struct __cmp_key *)a;

quoted

+	if (cpumask_weight_and(k->cpus, cur_hop[k->node]) <= k->cpu)
+		return 1;

quoted

+	k->w = (b == k->masks) ? 0 : cpumask_weight_and(k->cpus, prev_hop[k->node]);
+	if (k->w <= k->cpu)
+		return 0;

Can k->cpu be negative? If no, we can rewrite above as

	k->w = 0;
	if (b == k->masks)
		return 0;

	k->w = cpumask_weight_and(k->cpus, prev_hop[k->node]);

quoted

+	return -1;
+}

...

quoted

+int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node)
+{
+	struct __cmp_key k = { cpus, NULL, node, cpu, 0 };

You can drop NULL and 0 while using C99 assignments.

quoted

+	int hop, ret = nr_cpu_ids;

quoted

+	rcu_read_lock();

+ Blank line?

quoted

+	k.masks = rcu_dereference(sched_domains_numa_masks);
+	if (!k.masks)
+		goto unlock;

quoted

+	hop = (struct cpumask ***)
+		bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), cmp) - k.masks;

Strange indentation. I would rather see the split on parameters and
maybe '-' operator.

sizeof(*k.masks) is a bit shorter, right?

Also we may go with


	struct cpumask ***masks;
	struct __cmp_key k = { .cpus = cpus, .node = node, .cpu = cpu };

quoted

+	ret = hop ?
+		cpumask_nth_and_andnot(cpu - k.w, cpus, k.masks[hop][node], k.masks[hop-1][node]) :
+		cpumask_nth_and(cpu - k.w, cpus, k.masks[0][node]);

quoted

+unlock:

out_unlock: shows the intention more clearly, no?

quoted

+	rcu_read_unlock();
+	return ret;
+}

Below is a diff I have got on top of your patch, only compile tested:

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index 024f1da0e941..e04262578b52 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c

@@ -2070,26 +2070,28 @@ int sched_numa_find_closest(const struct cpumask *cpus, int cpu)
 }
 
 struct __cmp_key {
-	const struct cpumask *cpus;
 	struct cpumask ***masks;
+	const struct cpumask *cpus;
 	int node;
 	int cpu;
 	int w;
 };
 
-static int cmp(const void *a, const void *b)
+static int cmp(const void *key, const void *pivot)
 {
-	struct cpumask **prev_hop = *((struct cpumask ***)b - 1);
-	struct cpumask **cur_hop = *(struct cpumask ***)b;
-	struct __cmp_key *k = (struct __cmp_key *)a;
+	struct __cmp_key *k = container_of(key, struct __cmp_key, masks);
+	const struct cpumask ***masks = (const struct cpumask ***)pivot;
+	const struct cpumask **prev = masks[-1];
+	const struct cpumask **cur = masks[0];
 
-	if (cpumask_weight_and(k->cpus, cur_hop[k->node]) <= k->cpu)
+	if (cpumask_weight_and(k->cpus, cur[k->node]) <= k->cpu)
 		return 1;
 
-	k->w = (b == k->masks) ? 0 : cpumask_weight_and(k->cpus, prev_hop[k->node]);
-	if (k->w <= k->cpu)
+	k->w = 0;
+	if (masks == (const struct cpumask ***)k->masks)
 		return 0;
 
+	k->w = cpumask_weight_and(k->cpus, prev[k->node]);
 	return -1;
 }
 

@@ -2103,17 +2105,17 @@ static int cmp(const void *a, const void *b)
  */
 int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node)
 {
-	struct __cmp_key k = { cpus, NULL, node, cpu, 0 };
+	struct __cmp_key k = { .cpus = cpus, .node = node, .cpu = cpu };
 	int hop, ret = nr_cpu_ids;
+	struct cpumask ***masks;
 
 	rcu_read_lock();
 	k.masks = rcu_dereference(sched_domains_numa_masks);
 	if (!k.masks)
 		goto unlock;
 
-	hop = (struct cpumask ***)
-		bsearch(&k, k.masks, sched_domains_numa_levels, sizeof(k.masks[0]), cmp) - k.masks;
-
+	masks = bsearch(&k.masks, k.masks, sched_domains_numa_levels, sizeof(*k.masks), cmp);
+	hop = masks - k.masks;
 	ret = hop ?
 		cpumask_nth_and_andnot(cpu - k.w, cpus, k.masks[hop][node], k.masks[hop-1][node]) :
 		cpumask_nth_and(cpu - k.w, cpus, k.masks[0][node]);

-- 
With Best Regards,
Andy Shevchenko