linux-kernel - Re: [PATCH v16 1/3] lib: 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 for Android: free password hash cracker in your pocket

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

Message-ID: <aWfHTLDA8-Fja_gD@tiehlicka>
Date: Wed, 14 Jan 2026 17:41:48 +0100
From: Michal Hocko <mhocko@...e.com>
To: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.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>,
	Christoph Lameter <cl@...ux.com>, Martin Liu <liumartin@...gle.com>,
	David Rientjes <rientjes@...gle.com>, christian.koenig@....com,
	Shakeel Butt <shakeel.butt@...ux.dev>,
	SeongJae Park <sj@...nel.org>, Johannes Weiner <hannes@...xchg.org>,
	Sweet Tea Dorminy <sweettea-kernel@...miny.me>,
	Lorenzo Stoakes <lorenzo.stoakes@...cle.com>,
	"Liam R . Howlett" <liam.howlett@...cle.com>,
	Mike Rapoport <rppt@...nel.org>,
	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>,
	Mateusz Guzik <mjguzik@...il.com>,
	Matthew Wilcox <willy@...radead.org>,
	Baolin Wang <baolin.wang@...ux.alibaba.com>,
	Aboorva Devarajan <aboorvad@...ux.ibm.com>
Subject: Re: [PATCH v16 1/3] lib: Introduce hierarchical per-cpu counters

On Wed 14-01-26 09:59:13, Mathieu Desnoyers wrote:
> * Motivation
> 
> The purpose of this hierarchical split-counter scheme is to:
> 
> - Minimize contention when incrementing and decrementing counters,
> - Provide fast access to a sum approximation,
> - Provide a sum approximation with an acceptable accuracy level when
>   scaling to many-core systems.
> - Provide approximate and precise comparison of two counters, and
>   between a counter and a value.
> - Provide possible precise sum ranges for a given sum approximation.
> 
> Its goals are twofold:
> 
> - Improve the accuracy of the approximated RSS counter values returned
>   by proc interfaces [1],
> - Reduce the latency of the OOM killer on large many-core systems.
> 
> * Design
> 
> The hierarchical per-CPU counters propagate a sum approximation through
> a N-way tree. When reaching the batch size, the carry is propagated
> through a binary tree which consists of logN(nr_cpu_ids) levels. The
> batch size for each level is twice the batch size of the prior level.
> 
> Example propagation diagram with 8 cpus through a binary tree:
> 
> Level 0:  0    1    2    3    4    5    6    7
>           |   /     |   /     |   /     |   /
>           |  /      |  /      |  /      |  /
>           | /       | /       | /       | /
> Level 1:  0         1         2         3
>           |       /           |       /
>           |    /              |    /
>           | /                 | /
> Level 2:  0                   1
>           |               /
>           |         /
>           |   /
> Level 3:  0
> 
> For a binary tree, the maximum inaccuracy is bound by:
>    batch_size * log2(nr_cpus) * nr_cpus
> which evolves with O(n*log(n)) as the number of CPUs increases.
> 
> For a N-way tree, the maximum inaccuracy can be pre-calculated
> based on the the N-arity of each level and the batch size.

One thing you should probably mention here is the memory consumption of
the structure.

I have briefly looked at the implementation and concluded that I do not
have enough time to make a thorough review. Sorry about that. As I've
said in previous version the overall idea is sound. Especially if the
additional memory consumption is not a factor. I will let others judge
implementation details.

Thanks!
-- 
Michal Hocko
SUSE Labs