linux-kernel - Re: [PATCH v2 3/4] sched: add sched_numa_find_nth

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <xhsmh5yfgyvt9.mognet@vschneid.remote.csb>
Date:   Tue, 15 Nov 2022 17:25:06 +0000
From:   Valentin Schneider <vschneid@...hat.com>
To:     Yury Norov <yury.norov@...il.com>, linux-kernel@...r.kernel.org,
        "David S. Miller" <davem@...emloft.net>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Barry Song <baohua@...nel.org>,
        Ben Segall <bsegall@...gle.com>,
        haniel Bristot de Oliveira <bristot@...hat.com>,
        Dietmar Eggemann <dietmar.eggemann@....com>,
        Gal Pressman <gal@...dia.com>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Heiko Carstens <hca@...ux.ibm.com>,
        Ingo Molnar <mingo@...hat.com>,
        Jakub Kicinski <kuba@...nel.org>,
        Jason Gunthorpe <jgg@...dia.com>,
        Jesse Brandeburg <jesse.brandeburg@...el.com>,
        Jonathan Cameron <Jonathan.Cameron@...wei.com>,
        Juri Lelli <juri.lelli@...hat.com>,
        Leon Romanovsky <leonro@...dia.com>,
        Mel Gorman <mgorman@...e.de>,
        Peter Zijlstra <peterz@...radead.org>,
        Rasmus Villemoes <linux@...musvillemoes.dk>,
        Saeed Mahameed <saeedm@...dia.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Tariq Toukan <tariqt@...dia.com>,
        Tariq Toukan <ttoukan.linux@...il.com>,
        Tony Luck <tony.luck@...el.com>,
        Vincent Guittot <vincent.guittot@...aro.org>
Cc:     Yury Norov <yury.norov@...il.com>, linux-crypto@...r.kernel.org,
        netdev@...r.kernel.org, linux-rdma@...r.kernel.org
Subject: Re: [PATCH v2 3/4] sched: add sched_numa_find_nth_cpu()

On 12/11/22 11:09, Yury Norov wrote:
> 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.
>

So one thing regarding the bsearch and NUMA levels; until not so long ago
we couldn't even support 3 hops [1], and this only got detected when such
machines started showing up.

Your bsearch here operates on NUMA levels, which represent hops, and so far
we know of systems that have up to 4 levels. I'd be surprised (and also
appalled) if we even doubled that in the next decade, so with that in mind,
a linear walk might not be so horrible.

[1]: https://lore.kernel.org/all/20210224030944.15232-1-song.bao.hua@hisilicon.com/


> Signed-off-by: Yury Norov <yury.norov@...il.com>
> ---
> +int sched_numa_find_nth_cpu(const struct cpumask *cpus, int cpu, int node)
> +{
> +	struct __cmp_key k = { cpus, NULL, node, cpu, 0 };
> +	int hop, ret = nr_cpu_ids;
> +
> +	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;
> +
> +	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]);
                                      ^^^
                  wouldn't this always be 0 here?

> +unlock:
> +	rcu_read_unlock();
> +	return ret;
> +}
> +EXPORT_SYMBOL_GPL(sched_numa_find_nth_cpu);
>  #endif /* CONFIG_NUMA */
>
>  static int __sdt_alloc(const struct cpumask *cpu_map)
> --
> 2.34.1