linux-kernel - Re: [RFC PATCH v2] Introduce Hierarchical Per-CPU Counters

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: <Z_VWc6Z90rhfyLBp@casper.infradead.org>
Date: Tue, 8 Apr 2025 18:01:39 +0100
From: Matthew Wilcox <willy@...radead.org>
To: "Christoph Lameter (Ampere)" <cl@...two.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
	Sweet Tea Dorminy <sweettea@...gle.com>,
	Mateusz Guzik <mjguzik@...il.com>, linux-kernel@...r.kernel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	"Paul E. McKenney" <paulmck@...nel.org>,
	Steven Rostedt <rostedt@...dmis.org>,
	Masami Hiramatsu <mhiramat@...nel.org>,
	Dennis Zhou <dennis@...nel.org>, Tejun Heo <tj@...nel.org>,
	Martin Liu <liumartin@...gle.com>,
	David Rientjes <rientjes@...gle.com>, christian.koenig@....com,
	Shakeel Butt <shakeel.butt@...ux.dev>,
	Johannes Weiner <hannes@...xchg.org>,
	Lorenzo Stoakes <lorenzo.stoakes@...cle.com>,
	"Liam R . Howlett" <Liam.Howlett@...cle.com>,
	Suren Baghdasaryan <surenb@...gle.com>,
	Vlastimil Babka <vbabka@...e.cz>,
	Christian Brauner <brauner@...nel.org>,
	Wei Yang <richard.weiyang@...il.com>,
	David Hildenbrand <david@...hat.com>,
	Miaohe Lin <linmiaohe@...wei.com>,
	Al Viro <viro@...iv.linux.org.uk>, linux-mm@...ck.org,
	linux-trace-kernel@...r.kernel.org, Yu Zhao <yuzhao@...gle.com>,
	Roman Gushchin <roman.gushchin@...ux.dev>
Subject: Re: [RFC PATCH v2] Introduce Hierarchical Per-CPU Counters

On Tue, Apr 08, 2025 at 09:37:18AM -0700, Christoph Lameter (Ampere) wrote:
> > The hierarchical per-CPU counters propagate a sum approximation through
> > a binary tree. When reaching the batch size, the carry is propagated
> > through a binary tree which consists of log2(nr_cpu_ids) levels. The
> > batch size for each level is twice the batch size of the prior level.
> 
> A binary tree? Could we do this N-way? Otherwise the tree will be 8 levels
> on a 512 cpu machine. Given the inflation of the number of cpus this
> scheme better work up to 8K cpus.

I find that a fan-out somewhere between 8 and 16 works well in practice.
log16(512) gives a 3 level tree as does a log8 tree.  log16(8192) is a 4
level tree whereas log8(8192) is a 5 level tree.  Not a big difference
either way.

Somebody was trying to persuade me that a new tree type that maintained
additional information at each level of the tree to make some operations
log(log(N)) would be a better idea than a B-tree that is log(N).  I
countered that a wider tree made the argument unsound at any size tree
up to 100k.  And we don't tend to have _that_ many objects in a
data structure inside the kernel.

ceil(log14(100,000)) = 5
ceil(log2(log2(100,000))) = 5

at a million, there's actually a gap, 6 vs 5.  But constant factors
become a much larger factor than scalability arguments at that point.