From nobody Sat Sep 26 04:30:04 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B39EB3BFE44 for ; Fri, 4 Sep 2026 16:07:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538074; cv=none; b=iuG3oy9C2xZJcPNkfZUzKi0ONog+qNzvuyX0eNriXUn4bVCYgkwxEUwV7hAy5YQwBmxSCAClCwDP8fXeQ+ox7pYj2iKqwho+kZUOB/hKhNAfUcrOSQaTrv573CwmmfAEmyNhnDB7GnrB9enwWJ91ztfGM0WaFzNykyQIoBBHxs0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538074; c=relaxed/simple; bh=YEBxtx2tOSttrVbdSgjXG0BK8vfseWy5kvUeptlxwxs=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=TgfVHc2/H78wel7LFo5MnoYY2V5480swEHt/tg+sq5subH1P3g8NtRWbpAjQyQnmo+weM2SaV1hQb1Bz6JYqgicVyoVl3+rPm2HrLRyXZ9M4g7gwNbUZo01pRuvza6kHKjE4qphep0wbLB2RWc7327mcQPZlB8eynMquFxFzMqY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=C8W1vxTQ; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="C8W1vxTQ" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538057; bh=FHi0zdrEvXn5qCL/X4oRLWq75p3tEGelkftxbxFlfgg=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=C8W1vxTQIvnBjKBEkEhyQ9VFoMszJWZoQbIt0YFb0yW5gbbCIIAGDf3WBWBW7Vftl pMWk0eDXJcUULUHhkyArLBiOQmu3/TnkWTIDFEvUtb88uEgOH53wbsxQhIqNQKVClx D2+9JJRxzJsgb2WzSj1UQzX/gIZ1qcWZgR+ykHI1+FH/yUAVP5qoASrxEZhPXENPsy Sj5X4Z90j6emvT3pXW7Wv0nsrMFOA9t7cP9zdGJFL2THYk861O26zk3I+vY3Ec/6bR KbS936AS3fW7ClD8DWKQBfm74+gofte3hpIFMs3tg66tMdzD4BbTPA9u8hoDAz9MWL H3DfI0jWNrKrw== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zd2M7dzX3d; Fri, 04 Sep 2026 12:07:37 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 01/10] lib: introduce hierarchical per-cpu counters Date: Fri, 4 Sep 2026 12:07:13 -0400 Message-ID: <20260904160734.23445-2-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable This series introduces the hierarchical tree counter (hpcc) to increase accuracy of approximated RSS counters exposed through proc interfaces. With a test program hopping across CPUs doing frequent mmap/munmap operations, the upstream implementation approximation reaches a 1GB delta from the precise value after a few minutes, compared to a 80MB delta with the hierarchical counter. The hierarchical counter provides a guaranteed maximum approximation inaccuracy of 192MB on that hardware topology. * 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_cpu_ids) * nr_cpu_ids 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. * Memory Use The most important parts in terms of memory use are the per-cpu counters and the tree items which propagate the carry. In the proposed implementation, the per-cpu counters are allocated within per-cpu data structures, so they end up using: nr_possible_cpus * sizeof(unsigned long) This is in addition to the tree items. The size of those items is defined by the per_nr_cpu_order_config table "nr_items" field. Each item is aligned on cacheline size (typically 64 bytes) to minimize false sharing. Here is the footprint for a few nr_cpu_ids on a 64-bit arch: nr_cpu_ids percpu counters (bytes) nr_items items size (bytes) = total (bytes) 2 16 1 64 = 80 4 32 3 192 = 224 8 64 7 448 = 512 64 512 21 1344 = 1856 128 1024 21 1344 = 2368 256 2048 37 2368 = 4416 512 4096 73 4672 = 8768 There are of course various trade offs we can make here. We can: * Increase the n-arity of the intermediate items to shrink the nr_items required for a given nr_cpus. This will increase contention of carry propagation across more cores. * Remove cacheline alignment of intermediate tree items. This will shrink the memory needed for tree items, but will increase false sharing. * Represent intermediate tree items on a byte rather than long. This further reduces the memory required for intermediate tree items, but further increases false sharing. * Represent per-cpu counters on bytes rather than long. This makes the "sum" operation trickier, because it needs to iterate on the intermediate carry propagation nodes as well and synchronize with ongoing "tree add" operations. It further reduces memory use. * Implement a custom strided allocator for intermediate items carry propagation bytes. This shares cachelines across different tree instances, keeping good locality. This ensures that all accesses from a given location in the machine topology touch the same cacheline for the various tree instances. This adds complexity, but provides compactness as well as minimal false-sharing. Compared to this, the upstream percpu counters use a 32-bit integer per-cpu (4 bytes), and accumulate within a 64-bit global value. So there is an extra memory footprint added by the current hpcc implementation, but if it's an issue we have various options to consider to reduce its footprint. Link: https://lkml.kernel.org/r/20260227153730.1556542-1-mathieu.desnoyers@= efficios.com Link: https://lore.kernel.org/lkml/20250331223516.7810-2-sweettea-kernel@do= rminy.me/ # [1] Link: https://lkml.kernel.org/r/20260227153730.1556542-2-mathieu.desnoyers@= efficios.com Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- .../core-api/percpu-counter-tree.rst | 75 ++ include/linux/mm_types.h | 4 +- include/linux/percpu_counter_tree.h | 367 +++++++++ init/main.c | 2 + lib/Makefile | 1 + lib/percpu_counter_tree.c | 702 ++++++++++++++++++ 6 files changed, 1149 insertions(+), 2 deletions(-) create mode 100644 Documentation/core-api/percpu-counter-tree.rst create mode 100644 include/linux/percpu_counter_tree.h create mode 100644 lib/percpu_counter_tree.c diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation= /core-api/percpu-counter-tree.rst new file mode 100644 index 000000000000..196da056e7b4 --- /dev/null +++ b/Documentation/core-api/percpu-counter-tree.rst @@ -0,0 +1,75 @@ +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +The Hierarchical Per-CPU Counters (HPCC) +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +:Author: Mathieu Desnoyers + +Introduction +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Counters come in many varieties, each with their own trade offs: + + * A global atomic counter provides a fast read access to the current + sum, at the expense of cache-line bouncing on updates. This leads to + poor performance of frequent updates from various cores on large SMP + systems. + + * A per-cpu split counter provides fast updates to per-cpu counters, + at the expense of a slower aggregation (sum). The sum operation needs + to iterate over all per-cpu counters to calculate the current total. + +The hierarchical per-cpu counters attempt to provide the best of both +worlds (fast updates, and fast sum) by relaxing requirements on the sum +accuracy. It allows quickly querying an approximated sum value, along +with the possible min/max ranges of the associated precise sum. The +exact precise sum can still be calculated with an iteration on all +per-cpu counter, but the availability of an approximated sum value with +possible precise sum min/max ranges allows eliminating candidates which +are certainly outside of a known target range without the overhead of +precise sums. + +Overview +=3D=3D=3D=3D=3D=3D=3D=3D + +The herarchical per-cpu counters are organized as a tree with the tree +root at the bottom (last level) and the first level of the tree +consisting of per-cpu counters. + +The intermediate tree levels contain carry propagation counters. When +reaching a threshold (batch size), the carry is propagated down the +tree. + +This allows reading an approximated value at the root, which has a +bounded accuracy (minimum/maximum possible precise sum range) determined +by the tree topology. + +Use Cases +=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Use cases HPCC is meant to handle invove tracking resources which are +used across many CPUs to quickly sum as feedback for decision making to +apply throttling, quota limits, sort tasks, and perform memory or task +migration decisions. When considering approximated sums within the +accuracy range of the decision threshold, the user can either: + + * Be conservative and fast: Consider that the sum has reached the + limit as soon as the given limit is within the approximation range. + + * Be aggressive and fast: Consider that the sum is over the + limit only when the approximation range is over the given limit. + + * Be precise and slow: Do a precise comparison with the limit, which + requires a precise sum when the limit is within the approximated + range. + +One use-case for these hierarchical counters is to implement a two-pass +algorithm to speed up sorting picking a maximum/minimunm sum value from +a set. A first pass compares the approximated values, and then a second +pass only needs the precise sum for counter trees which are within the +possible precise sum range of the counter tree chosen by the first pass. + +Functions and structures +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +.. kernel-doc:: include/linux/percpu_counter_tree.h +.. kernel-doc:: lib/percpu_counter_tree.c diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h index 6d815f6440c9..dff5fd1c1b06 100644 --- a/include/linux/mm_types.h +++ b/include/linux/mm_types.h @@ -1462,8 +1462,8 @@ static inline void __mm_flags_set_mask_bits_word(stru= ct mm_struct *mm, MT_FLAGS_USE_RCU) extern struct mm_struct init_mm; =20 -#define MM_STRUCT_FLEXIBLE_ARRAY_INIT \ -{ \ +#define MM_STRUCT_FLEXIBLE_ARRAY_INIT \ +{ \ [0 ... sizeof(cpumask_t) + MM_CID_STATIC_SIZE - 1] =3D 0 \ } =20 diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_cou= nter_tree.h new file mode 100644 index 000000000000..828c763edd4a --- /dev/null +++ b/include/linux/percpu_counter_tree.h @@ -0,0 +1,367 @@ +/* SPDX-License-Identifier: GPL-2.0+ OR MIT */ +/* SPDX-FileCopyrightText: 2025 Mathieu Desnoyers */ + +#ifndef _PERCPU_COUNTER_TREE_H +#define _PERCPU_COUNTER_TREE_H + +#include +#include +#include + +#ifdef CONFIG_SMP + +#if NR_CPUS =3D=3D (1U << 0) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 0 +#elif NR_CPUS <=3D (1U << 1) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 1 +#elif NR_CPUS <=3D (1U << 2) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 3 +#elif NR_CPUS <=3D (1U << 3) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 7 +#elif NR_CPUS <=3D (1U << 4) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 7 +#elif NR_CPUS <=3D (1U << 5) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 11 +#elif NR_CPUS <=3D (1U << 6) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 21 +#elif NR_CPUS <=3D (1U << 7) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 21 +#elif NR_CPUS <=3D (1U << 8) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 37 +#elif NR_CPUS <=3D (1U << 9) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 73 +#elif NR_CPUS <=3D (1U << 10) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 149 +#elif NR_CPUS <=3D (1U << 11) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 293 +#elif NR_CPUS <=3D (1U << 12) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 585 +#elif NR_CPUS <=3D (1U << 13) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 1173 +#elif NR_CPUS <=3D (1U << 14) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 2341 +#elif NR_CPUS <=3D (1U << 15) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 4681 +#elif NR_CPUS <=3D (1U << 16) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 4681 +#elif NR_CPUS <=3D (1U << 17) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 8777 +#elif NR_CPUS <=3D (1U << 18) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 17481 +#elif NR_CPUS <=3D (1U << 19) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 34953 +#elif NR_CPUS <=3D (1U << 20) +# define PERCPU_COUNTER_TREE_STATIC_NR_ITEMS 69905 +#else +# error "Unsupported number of CPUs." +#endif + +struct percpu_counter_tree_level_item { + atomic_long_t count; /* + * Count the number of carry for this tree item. + * The carry counter is kept at the order of the + * carry accounted for at this tree level. + */ +} ____cacheline_aligned_in_smp; + +#define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE \ + (PERCPU_COUNTER_TREE_STATIC_NR_ITEMS * sizeof(struct percpu_counter_tree_= level_item)) + +struct percpu_counter_tree { + /* Fast-path fields. */ + unsigned long __percpu *level0; /* Pointer to per-CPU split counters (tre= e level 0). */ + unsigned long level0_bit_mask; /* Bit mask to apply to detect carry propa= gation from tree level 0. */ + union { + unsigned long *i; /* Approximate sum for single-CPU topology. */ + atomic_long_t *a; /* Approximate sum for SMP topology. */ + } approx_sum; + long bias; /* Bias to apply to counter precise and approximate values. = */ + + /* Slow-path fields. */ + struct percpu_counter_tree_level_item *items; /* Array of tree items for = levels 1 to N. */ + unsigned long batch_size; /* + * The batch size is the increment step at level 0 which + * triggers a carry propagation. The batch size is required + * to be greater than 1, and a power of 2. + */ + /* + * The tree approximate sum is guaranteed to be within this accuracy rang= e: + * (precise_sum - approx_accuracy_range.under) <=3D approx_sum <=3D (prec= ise_sum + approx_accuracy_range.over). + * This accuracy is derived from the hardware topology and the tree batch= _size. + * The "under" accuracy is larger than the "over" accuracy because the ne= gative range of a + * two's complement signed integer is one unit larger than the positive r= ange. This delta + * is summed for each tree item, which leads to a significantly larger "u= nder" accuracy range + * compared to the "over" accuracy range. + */ + struct { + unsigned long under; + unsigned long over; + } approx_accuracy_range; +}; + +size_t percpu_counter_tree_items_size(void); +int percpu_counter_tree_init_many(struct percpu_counter_tree *counters, st= ruct percpu_counter_tree_level_item *items, + unsigned int nr_counters, unsigned long batch_size, gfp_t gfp_flags); +int percpu_counter_tree_init(struct percpu_counter_tree *counter, struct p= ercpu_counter_tree_level_item *items, + unsigned long batch_size, gfp_t gfp_flags); +void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counter,= unsigned int nr_counters); +void percpu_counter_tree_destroy(struct percpu_counter_tree *counter); +void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc= ); +long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter); +int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,= struct percpu_counter_tree *b); +int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tr= ee *counter, long v); +int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a, str= uct percpu_counter_tree *b); +int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *= counter, long v); +void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v); +int percpu_counter_tree_subsystem_init(void); + +/** + * percpu_counter_tree_approximate_sum() - Return approximate counter sum. + * @counter: The counter to sum. + * + * Querying the approximate sum is fast, but it is only accurate within + * the bounds delimited by percpu_counter_tree_approximate_accuracy_range(= ). + * This is meant to be used when speed is preferred over accuracy. + * + * Return: The current approximate counter sum. + */ +static inline +long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *count= er) +{ + unsigned long v; + + if (!counter->level0_bit_mask) + v =3D READ_ONCE(*counter->approx_sum.i); + else + v =3D atomic_long_read(counter->approx_sum.a); + return (long) (v + (unsigned long)READ_ONCE(counter->bias)); +} + +/** + * percpu_counter_tree_approximate_accuracy_range - Query the accuracy ran= ge for a counter tree. + * @counter: Counter to query. + * @under: Pointer to a variable to be incremented of the approximation + * accuracy range below the precise sum. + * @over: Pointer to a variable to be incremented of the approximation + * accuracy range above the precise sum. + * + * Query the accuracy range limits for the counter. + * Because of two's complement binary representation, the "under" range is= typically + * slightly larger than the "over" range. + * Those values are derived from the hardware topology and the counter tre= e batch size. + * They are invariant for a given counter tree. + * Using this function should not be typically required, see the following= functions instead: + * * percpu_counter_tree_approximate_compare(), + * * percpu_counter_tree_approximate_compare_value(), + * * percpu_counter_tree_precise_compare(), + * * percpu_counter_tree_precise_compare_value(). + */ +static inline +void percpu_counter_tree_approximate_accuracy_range(struct percpu_counter_= tree *counter, + unsigned long *under, unsigned long *over) +{ + *under +=3D counter->approx_accuracy_range.under; + *over +=3D counter->approx_accuracy_range.over; +} + +#else /* !CONFIG_SMP */ + +#define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE 0 + +struct percpu_counter_tree_level_item; + +struct percpu_counter_tree { + atomic_long_t count; +}; + +static inline +size_t percpu_counter_tree_items_size(void) +{ + return 0; +} + +static inline +int percpu_counter_tree_init_many(struct percpu_counter_tree *counters, st= ruct percpu_counter_tree_level_item *items, + unsigned int nr_counters, unsigned long batch_size, gfp_t gfp_flags) +{ + for (unsigned int i =3D 0; i < nr_counters; i++) + atomic_long_set(&counters[i].count, 0); + return 0; +} + +static inline +int percpu_counter_tree_init(struct percpu_counter_tree *counter, struct p= ercpu_counter_tree_level_item *items, + unsigned long batch_size, gfp_t gfp_flags) +{ + return percpu_counter_tree_init_many(counter, items, 1, batch_size, gfp_f= lags); +} + +static inline +void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counter,= unsigned int nr_counters) +{ +} + +static inline +void percpu_counter_tree_destroy(struct percpu_counter_tree *counter) +{ +} + +static inline +long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter) +{ + return atomic_long_read(&counter->count); +} + +static inline +int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a, str= uct percpu_counter_tree *b) +{ + long count_a =3D percpu_counter_tree_precise_sum(a), + count_b =3D percpu_counter_tree_precise_sum(b); + + if (count_a =3D=3D count_b) + return 0; + if (count_a < count_b) + return -1; + return 1; +} + +static inline +int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *= counter, long v) +{ + long count =3D percpu_counter_tree_precise_sum(counter); + + if (count =3D=3D v) + return 0; + if (count < v) + return -1; + return 1; +} + +static inline +int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,= struct percpu_counter_tree *b) +{ + return percpu_counter_tree_precise_compare(a, b); +} + +static inline +int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tr= ee *counter, long v) +{ + return percpu_counter_tree_precise_compare_value(counter, v); +} + +static inline +void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v) +{ + atomic_long_set(&counter->count, v); +} + +static inline +void percpu_counter_tree_approximate_accuracy_range(struct percpu_counter_= tree *counter, + unsigned long *under, unsigned long *over) +{ +} + +static inline +void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc) +{ + atomic_long_add(inc, &counter->count); +} + +static inline +long percpu_counter_tree_approximate_sum(struct percpu_counter_tree *count= er) +{ + return percpu_counter_tree_precise_sum(counter); +} + +static inline +int percpu_counter_tree_subsystem_init(void) +{ + return 0; +} + +#endif /* CONFIG_SMP */ + +/** + * percpu_counter_tree_approximate_sum_positive() - Return a positive appr= oximate counter sum. + * @counter: The counter to sum. + * + * Return an approximate counter sum which is guaranteed to be greater + * or equal to 0. + * + * Return: The current positive approximate counter sum. + */ +static inline +long percpu_counter_tree_approximate_sum_positive(struct percpu_counter_tr= ee *counter) +{ + long v =3D percpu_counter_tree_approximate_sum(counter); + return v > 0 ? v : 0; +} + +/** + * percpu_counter_tree_precise_sum_positive() - Return a positive precise = counter sum. + * @counter: The counter to sum. + * + * Return a precise counter sum which is guaranteed to be greater + * or equal to 0. + * + * Return: The current positive precise counter sum. + */ +static inline +long percpu_counter_tree_precise_sum_positive(struct percpu_counter_tree *= counter) +{ + long v =3D percpu_counter_tree_precise_sum(counter); + return v > 0 ? v : 0; +} + +/** + * percpu_counter_tree_approximate_min_max_range() - Return the approximat= ion min and max precise values. + * @approx_sum: Approximated sum. + * @under: Tree accuracy range (under). + * @over: Tree accuracy range (over). + * @precise_min: Minimum possible value for precise sum (output). + * @precise_max: Maximum possible value for precise sum (output). + * + * Calculate the minimum and maximum precise values for a given + * approximation and (under, over) accuracy range. + * + * The range of the approximation as a function of the precise sum is expr= essed as: + * + * approx_sum >=3D precise_sum - approx_accuracy_range.under + * approx_sum <=3D precise_sum + approx_accuracy_range.over + * + * Therefore, the range of the precise sum as a function of the approximat= ion is expressed as: + * + * precise_sum <=3D approx_sum + approx_accuracy_range.under + * precise_sum >=3D approx_sum - approx_accuracy_range.over + */ +static inline +void percpu_counter_tree_approximate_min_max_range(long approx_sum, unsign= ed long under, unsigned long over, + long *precise_min, long *precise_max) +{ + *precise_min =3D approx_sum - over; + *precise_max =3D approx_sum + under; +} + +/** + * percpu_counter_tree_approximate_min_max() - Return the tree approximati= on, min and max possible precise values. + * @counter: The counter to sum. + * @approx_sum: Approximate sum (output). + * @precise_min: Minimum possible value for precise sum (output). + * @precise_max: Maximum possible value for precise sum (output). + * + * Return the approximate sum, minimum and maximum precise values for + * a counter. + */ +static inline +void percpu_counter_tree_approximate_min_max(struct percpu_counter_tree *c= ounter, + long *approx_sum, long *precise_min, long *precise_max) +{ + unsigned long under =3D 0, over =3D 0; + long v =3D percpu_counter_tree_approximate_sum(counter); + + percpu_counter_tree_approximate_accuracy_range(counter, &under, &over); + percpu_counter_tree_approximate_min_max_range(v, under, over, precise_min= , precise_max); + *approx_sum =3D v; +} + +#endif /* _PERCPU_COUNTER_TREE_H */ diff --git a/init/main.c b/init/main.c index 2613d3f9b3ce..eda2170bb21f 100644 --- a/init/main.c +++ b/init/main.c @@ -108,6 +108,7 @@ #include #include #include +#include #include =20 #include @@ -1041,6 +1042,7 @@ void start_kernel(void) vfs_caches_init_early(); sort_main_extable(); trap_init(); + percpu_counter_tree_subsystem_init(); mm_core_init(); maple_tree_init(); poking_init(); diff --git a/lib/Makefile b/lib/Makefile index dfab958327c5..f1d0cb831630 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -182,6 +182,7 @@ obj-$(CONFIG_TEXTSEARCH_KMP) +=3D ts_kmp.o obj-$(CONFIG_TEXTSEARCH_BM) +=3D ts_bm.o obj-$(CONFIG_TEXTSEARCH_FSM) +=3D ts_fsm.o obj-$(CONFIG_SMP) +=3D percpu_counter.o +obj-$(CONFIG_SMP) +=3D percpu_counter_tree.o obj-$(CONFIG_AUDIT_GENERIC) +=3D audit.o obj-$(CONFIG_AUDIT_COMPAT_GENERIC) +=3D compat_audit.o =20 diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c new file mode 100644 index 000000000000..5c8fc2dcdc16 --- /dev/null +++ b/lib/percpu_counter_tree.c @@ -0,0 +1,702 @@ +// SPDX-License-Identifier: GPL-2.0+ OR MIT +// SPDX-FileCopyrightText: 2025 Mathieu Desnoyers + +/* + * Split Counters With Tree Approximation Propagation + * + * * Propagation diagram when reaching batch size thresholds (=C2=B1 batch= size): + * + * Example diagram for 8 CPUs: + * + * log2(8) =3D 3 levels + * + * At each level, each pair propagates its values to the next level when + * reaching the batch size thresholds. + * + * Counters at levels 0, 1, 2 can be kept on a single byte ([-128 .. +127]= range), + * although it may be relevant to keep them on "long" counters for + * simplicity. (complexity vs memory footprint tradeoff) + * + * Counter at level 3 can be kept on a "long" counter. + * + * Level 0: 0 1 2 3 4 5 6 7 + * | / | / | / | / + * | / | / | / | / + * | / | / | / | / + * Level 1: 0 1 2 3 + * | / | / + * | / | / + * | / | / + * Level 2: 0 1 + * | / + * | / + * | / + * Level 3: 0 + * + * * Approximation accuracy: + * + * BATCH(level N): Level N batch size. + * + * Example for BATCH(level 0) =3D 32. + * + * BATCH(level 0) =3D 32 + * BATCH(level 1) =3D 64 + * BATCH(level 2) =3D 128 + * BATCH(level N) =3D BATCH(level 0) * 2^N + * + * per-counter global + * accuracy accuracy + * Level 0: [ -32 .. +31] =C2=B1256 (8 * 32) + * Level 1: [ -64 .. +63] =C2=B1256 (4 * 64) + * Level 2: [-128 .. +127] =C2=B1256 (2 * 128) + * Total: ------ =C2=B1768 (log2(nr_cpu_ids) * BATCH(level 0= ) * nr_cpu_ids) + * + * Note that the global accuracy can be calculated more precisely + * by taking into account that the positive accuracy range is + * 31 rather than 32. + * + * ----- + * + * Approximate Sum Carry Propagation + * + * Let's define a number of counter bits for each level, e.g.: + * + * log2(BATCH(level 0)) =3D log2(32) =3D 5 + * Let's assume, for this example, a 32-bit architecture (sizeof(long) =3D= =3D 4). + * + * nr_bit value_mask range + * Level 0: 5 bits v 0 .. +31 + * Level 1: 1 bit (v & ~((1UL << 5) - 1)) 0 .. +63 + * Level 2: 1 bit (v & ~((1UL << 6) - 1)) 0 .. +127 + * Level 3: 25 bits (v & ~((1UL << 7) - 1)) 0 .. 2^32-1 + * + * Note: Use a "long" per-cpu counter at level 0 to allow precise sum. + * + * Note: Use cacheline aligned counters at levels above 0 to prevent false= sharing. + * If memory footprint is an issue, a specialized allocator could be= used + * to eliminate padding. + * + * Example with expanded values: + * + * counter_add(counter, inc): + * + * if (!inc) + * return; + * + * res =3D percpu_add_return(counter @ Level 0, inc); + * orig =3D res - inc; + * if (inc < 0) { + * inc =3D -(-inc & ~0b00011111); // Clear used bits + * // xor bit 5: underflow + * if ((inc ^ orig ^ res) & 0b00100000) + * inc -=3D 0b00100000; + * } else { + * inc &=3D ~0b00011111; // Clear used bits + * // xor bit 5: overflow + * if ((inc ^ orig ^ res) & 0b00100000) + * inc +=3D 0b00100000; + * } + * if (!inc) + * return; + * + * res =3D atomic_long_add_return(counter @ Level 1, inc); + * orig =3D res - inc; + * if (inc < 0) { + * inc =3D -(-inc & ~0b00111111); // Clear used bits + * // xor bit 6: underflow + * if ((inc ^ orig ^ res) & 0b01000000) + * inc -=3D 0b01000000; + * } else { + * inc &=3D ~0b00111111; // Clear used bits + * // xor bit 6: overflow + * if ((inc ^ orig ^ res) & 0b01000000) + * inc +=3D 0b01000000; + * } + * if (!inc) + * return; + * + * res =3D atomic_long_add_return(counter @ Level 2, inc); + * orig =3D res - inc; + * if (inc < 0) { + * inc =3D -(-inc & ~0b01111111); // Clear used bits + * // xor bit 7: underflow + * if ((inc ^ orig ^ res) & 0b10000000) + * inc -=3D 0b10000000; + * } else { + * inc &=3D ~0b01111111; // Clear used bits + * // xor bit 7: overflow + * if ((inc ^ orig ^ res) & 0b10000000) + * inc +=3D 0b10000000; + * } + * if (!inc) + * return; + * + * atomic_long_add(counter @ Level 3, inc); + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#define MAX_NR_LEVELS 5 + +/* + * The counter configuration is selected at boot time based on the + * hardware topology. + */ +struct counter_config { + unsigned int nr_items; /* + * nr_items is the number of items in the tree for levels 1 + * up to and including the final level (approximate sum). + * It excludes the level 0 per-CPU counters. + */ + unsigned char nr_levels; /* + * nr_levels is the number of hierarchical counter tree levels. + * It excludes the final level (approximate sum). + */ + unsigned char n_arity_order[MAX_NR_LEVELS]; /* + * n-arity of tree nodes for each level from + * 0 to (nr_levels - 1). + */ +}; + +static const struct counter_config per_nr_cpu_order_config[] =3D { + [0] =3D { .nr_items =3D 0, .nr_levels =3D 0, .n_arity_order =3D { 0 } }, + [1] =3D { .nr_items =3D 1, .nr_levels =3D 1, .n_arity_order =3D { 1 } }, + [2] =3D { .nr_items =3D 3, .nr_levels =3D 2, .n_arity_order =3D { 1, 1 }= }, + [3] =3D { .nr_items =3D 7, .nr_levels =3D 3, .n_arity_order =3D { 1, 1, = 1 } }, + [4] =3D { .nr_items =3D 7, .nr_levels =3D 3, .n_arity_order =3D { 2, 1, = 1 } }, + [5] =3D { .nr_items =3D 11, .nr_levels =3D 3, .n_arity_order =3D { 2, 2,= 1 } }, + [6] =3D { .nr_items =3D 21, .nr_levels =3D 3, .n_arity_order =3D { 2, 2,= 2 } }, + [7] =3D { .nr_items =3D 21, .nr_levels =3D 3, .n_arity_order =3D { 3, 2,= 2 } }, + [8] =3D { .nr_items =3D 37, .nr_levels =3D 3, .n_arity_order =3D { 3, 3,= 2 } }, + [9] =3D { .nr_items =3D 73, .nr_levels =3D 3, .n_arity_order =3D { 3, 3,= 3 } }, + [10] =3D { .nr_items =3D 149, .nr_levels =3D 4, .n_arity_order =3D { 3, = 3, 2, 2 } }, + [11] =3D { .nr_items =3D 293, .nr_levels =3D 4, .n_arity_order =3D { 3, = 3, 3, 2 } }, + [12] =3D { .nr_items =3D 585, .nr_levels =3D 4, .n_arity_order =3D { 3, = 3, 3, 3 } }, + [13] =3D { .nr_items =3D 1173, .nr_levels =3D 5, .n_arity_order =3D { 3,= 3, 3, 2, 2 } }, + [14] =3D { .nr_items =3D 2341, .nr_levels =3D 5, .n_arity_order =3D { 3,= 3, 3, 3, 2 } }, + [15] =3D { .nr_items =3D 4681, .nr_levels =3D 5, .n_arity_order =3D { 3,= 3, 3, 3, 3 } }, + [16] =3D { .nr_items =3D 4681, .nr_levels =3D 5, .n_arity_order =3D { 4,= 3, 3, 3, 3 } }, + [17] =3D { .nr_items =3D 8777, .nr_levels =3D 5, .n_arity_order =3D { 4,= 4, 3, 3, 3 } }, + [18] =3D { .nr_items =3D 17481, .nr_levels =3D 5, .n_arity_order =3D { 4= , 4, 4, 3, 3 } }, + [19] =3D { .nr_items =3D 34953, .nr_levels =3D 5, .n_arity_order =3D { 4= , 4, 4, 4, 3 } }, + [20] =3D { .nr_items =3D 69905, .nr_levels =3D 5, .n_arity_order =3D { 4= , 4, 4, 4, 4 } }, +}; + +static const struct counter_config *counter_config; /* Hierarchical counte= r configuration for the hardware topology. */ +static unsigned int nr_cpus_order; /* Order of nr_cpu_ids. */ +static unsigned long accuracy_multiplier; /* Calculate accuracy for a giv= en batch size (multiplication factor). */ + +static +int __percpu_counter_tree_init(struct percpu_counter_tree *counter, + unsigned long batch_size, gfp_t gfp_flags, + unsigned long __percpu *level0, + struct percpu_counter_tree_level_item *items) +{ + /* Batch size must be greater than 1, and a power of 2. */ + if (WARN_ON(batch_size <=3D 1 || (batch_size & (batch_size - 1)))) + return -EINVAL; + counter->batch_size =3D batch_size; + counter->bias =3D 0; + counter->level0 =3D level0; + counter->items =3D items; + if (!nr_cpus_order) { + counter->approx_sum.i =3D per_cpu_ptr(counter->level0, 0); + counter->level0_bit_mask =3D 0; + } else { + counter->approx_sum.a =3D &counter->items[counter_config->nr_items - 1].= count; + counter->level0_bit_mask =3D 1UL << get_count_order(batch_size); + } + /* + * Each tree item signed integer has a negative range which is + * one unit greater than the positive range. + */ + counter->approx_accuracy_range.under =3D batch_size * accuracy_multiplier; + counter->approx_accuracy_range.over =3D (batch_size - 1) * accuracy_multi= plier; + return 0; +} + +/** + * percpu_counter_tree_init_many() - Initialize many per-CPU counter trees. + * @counters: An array of @nr_counters counters to initialize. + * Their memory is provided by the caller. + * @items: Pointer to memory area where to store tree items. + * This memory is provided by the caller. + * Its size needs to be at least @nr_counters * percpu_counter_tree_ite= ms_size(). + * @nr_counters: The number of counter trees to initialize + * @batch_size: The batch size is the increment step at level 0 which trig= gers a + * carry propagation. + * The batch size is required to be greater than 1, and a power of 2. + * @gfp_flags: gfp flags to pass to the per-CPU allocator. + * + * Initialize many per-CPU counter trees using a single per-CPU + * allocator invocation for @nr_counters counters. + * + * Return: + * * %0: Success + * * %-EINVAL: - Invalid @batch_size argument + * * %-ENOMEM: - Out of memory + */ +int percpu_counter_tree_init_many(struct percpu_counter_tree *counters, st= ruct percpu_counter_tree_level_item *items, + unsigned int nr_counters, unsigned long batch_size, gfp_t gfp_flags) +{ + void __percpu *level0, *level0_iter; + size_t counter_size =3D sizeof(*counters->level0), + items_size =3D percpu_counter_tree_items_size(); + void *items_iter; + unsigned int i; + int ret; + + memset(items, 0, items_size * nr_counters); + level0 =3D __alloc_percpu_gfp(nr_counters * counter_size, + __alignof__(*counters->level0), gfp_flags); + if (!level0) + return -ENOMEM; + level0_iter =3D level0; + items_iter =3D items; + for (i =3D 0; i < nr_counters; i++) { + ret =3D __percpu_counter_tree_init(&counters[i], batch_size, gfp_flags, = level0_iter, items_iter); + if (ret) + goto free_level0; + level0_iter +=3D counter_size; + items_iter +=3D items_size; + } + return 0; + +free_level0: + free_percpu(level0); + return ret; +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_init_many); + +/** + * percpu_counter_tree_init() - Initialize one per-CPU counter tree. + * @counter: Counter to initialize. + * Its memory is provided by the caller. + * @items: Pointer to memory area where to store tree items. + * This memory is provided by the caller. + * Its size needs to be at least percpu_counter_tree_items_size(). + * @batch_size: The batch size is the increment step at level 0 which trig= gers a + * carry propagation. + * The batch size is required to be greater than 1, and a power of 2. + * @gfp_flags: gfp flags to pass to the per-CPU allocator. + * + * Initialize one per-CPU counter tree. + * + * Return: + * * %0: Success + * * %-EINVAL: - Invalid @batch_size argument + * * %-ENOMEM: - Out of memory + */ +int percpu_counter_tree_init(struct percpu_counter_tree *counter, struct p= ercpu_counter_tree_level_item *items, + unsigned long batch_size, gfp_t gfp_flags) +{ + return percpu_counter_tree_init_many(counter, items, 1, batch_size, gfp_f= lags); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_init); + +/** + * percpu_counter_tree_destroy_many() - Destroy many per-CPU counter trees. + * @counters: Array of counters trees to destroy. + * @nr_counters: The number of counter trees to destroy. + * + * Release internal resources allocated for @nr_counters per-CPU counter t= rees. + */ + +void percpu_counter_tree_destroy_many(struct percpu_counter_tree *counters= , unsigned int nr_counters) +{ + free_percpu(counters->level0); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_destroy_many); + +/** + * percpu_counter_tree_destroy() - Destroy one per-CPU counter tree. + * @counter: Counter to destroy. + * + * Release internal resources allocated for one per-CPU counter tree. + */ +void percpu_counter_tree_destroy(struct percpu_counter_tree *counter) +{ + return percpu_counter_tree_destroy_many(counter, 1); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_destroy); + +static +long percpu_counter_tree_carry(long orig, long res, long inc, unsigned lon= g bit_mask) +{ + if (inc < 0) { + inc =3D -(-inc & ~(bit_mask - 1)); + /* + * xor bit_mask: underflow. + * + * If inc has bit set, decrement an additional bit if + * there is _no_ bit transition between orig and res. + * Else, inc has bit cleared, decrement an additional + * bit if there is a bit transition between orig and + * res. + */ + if ((inc ^ orig ^ res) & bit_mask) + inc -=3D bit_mask; + } else { + inc &=3D ~(bit_mask - 1); + /* + * xor bit_mask: overflow. + * + * If inc has bit set, increment an additional bit if + * there is _no_ bit transition between orig and res. + * Else, inc has bit cleared, increment an additional + * bit if there is a bit transition between orig and + * res. + */ + if ((inc ^ orig ^ res) & bit_mask) + inc +=3D bit_mask; + } + return inc; +} + +/* + * It does not matter through which path the carry propagates up the + * tree, therefore there is no need to disable preemption because the + * cpu number is only used to favor cache locality. + */ +static +void percpu_counter_tree_add_slowpath(struct percpu_counter_tree *counter,= long inc) +{ + unsigned int level_items, nr_levels =3D counter_config->nr_levels, + level, n_arity_order; + unsigned long bit_mask; + struct percpu_counter_tree_level_item *item =3D counter->items; + unsigned int cpu =3D raw_smp_processor_id(); + + WARN_ON_ONCE(!nr_cpus_order); /* Should never be called for 1 cpu. */ + + n_arity_order =3D counter_config->n_arity_order[0]; + bit_mask =3D counter->level0_bit_mask << n_arity_order; + level_items =3D 1U << (nr_cpus_order - n_arity_order); + + for (level =3D 1; level < nr_levels; level++) { + /* + * For the purpose of carry propagation, the + * intermediate level counters only need to keep track + * of the bits relevant for carry propagation. We + * therefore don't care about higher order bits. + * Note that this optimization is unwanted if the + * intended use is to track counters within intermediate + * levels of the topology. + */ + if (abs(inc) & (bit_mask - 1)) { + atomic_long_t *count =3D &item[cpu & (level_items - 1)].count; + unsigned long orig, res; + + res =3D atomic_long_add_return_relaxed(inc, count); + orig =3D res - inc; + inc =3D percpu_counter_tree_carry(orig, res, inc, bit_mask); + if (likely(!inc)) + return; + } + item +=3D level_items; + n_arity_order =3D counter_config->n_arity_order[level]; + level_items >>=3D n_arity_order; + bit_mask <<=3D n_arity_order; + } + atomic_long_add(inc, counter->approx_sum.a); +} + +/** + * percpu_counter_tree_add() - Add to a per-CPU counter tree. + * @counter: Counter added to. + * @inc: Increment value (either positive or negative). + * + * Add @inc to a per-CPU counter tree. This is a fast-path which will + * typically increment per-CPU counters as long as there is no carry + * greater or equal to the counter tree batch size. + */ +void percpu_counter_tree_add(struct percpu_counter_tree *counter, long inc) +{ + unsigned long bit_mask =3D counter->level0_bit_mask, orig, res; + + res =3D this_cpu_add_return(*counter->level0, inc); + orig =3D res - inc; + inc =3D percpu_counter_tree_carry(orig, res, inc, bit_mask); + if (likely(!inc)) + return; + percpu_counter_tree_add_slowpath(counter, inc); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_add); + +static +long percpu_counter_tree_precise_sum_unbiased(struct percpu_counter_tree *= counter) +{ + unsigned long sum =3D 0; + int cpu; + + for_each_possible_cpu(cpu) + sum +=3D *per_cpu_ptr(counter->level0, cpu); + return (long) sum; +} + +/** + * percpu_counter_tree_precise_sum() - Return precise counter sum. + * @counter: The counter to sum. + * + * Querying the precise sum is relatively expensive because it needs to + * iterate over all CPUs. + * This is meant to be used when accuracy is preferred over speed. + * + * Return: The current precise counter sum. + */ +long percpu_counter_tree_precise_sum(struct percpu_counter_tree *counter) +{ + return percpu_counter_tree_precise_sum_unbiased(counter) + READ_ONCE(coun= ter->bias); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_sum); + +static +int compare_delta(long delta, unsigned long accuracy_neg, unsigned long ac= curacy_pos) +{ + if (delta >=3D 0) { + if (delta <=3D accuracy_pos) + return 0; + else + return 1; + } else { + if (-delta <=3D accuracy_neg) + return 0; + else + return -1; + } +} + +/** + * percpu_counter_tree_approximate_compare - Approximated comparison of tw= o counter trees. + * @a: First counter to compare. + * @b: Second counter to compare. + * + * Evaluate an approximate comparison of two counter trees. + * This approximation comparison is fast, and provides an accurate + * answer if the counters are found to be either less than or greater + * than the other. However, if the approximated comparison returns + * 0, the counters respective sums are found to be within the two + * counters accuracy range. + * + * Return: + * * %0 - Counters @a and @b do not differ by more than the sum of their = respective + * accuracy ranges. + * * %-1 - Counter @a less than counter @b. + * * %1 - Counter @a is greater than counter @b. + */ +int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,= struct percpu_counter_tree *b) +{ + return compare_delta(percpu_counter_tree_approximate_sum(a) - percpu_coun= ter_tree_approximate_sum(b), + a->approx_accuracy_range.over + b->approx_accuracy_range.under, + a->approx_accuracy_range.under + b->approx_accuracy_range.over); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compare); + +/** + * percpu_counter_tree_approximate_compare_value - Approximated comparison= of a counter tree against a given value. + * @counter: Counter to compare. + * @v: Value to compare. + * + * Evaluate an approximate comparison of a counter tree against a given va= lue. + * This approximation comparison is fast, and provides an accurate + * answer if the counter is found to be either less than or greater + * than the value. However, if the approximated comparison returns + * 0, the value is within the counter accuracy range. + * + * Return: + * * %0 - The value @v is within the accuracy range of the counter. + * * %-1 - The value @v is less than the counter. + * * %1 - The value @v is greater than the counter. + */ +int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tr= ee *counter, long v) +{ + return compare_delta(v - percpu_counter_tree_approximate_sum(counter), + counter->approx_accuracy_range.under, + counter->approx_accuracy_range.over); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compare_value); + +/** + * percpu_counter_tree_precise_compare - Precise comparison of two counter= trees. + * @a: First counter to compare. + * @b: Second counter to compare. + * + * Evaluate a precise comparison of two counter trees. + * As an optimization, it uses the approximate counter comparison + * to quickly compare counters which are far apart. Only cases where + * counter sums are within the accuracy range require precise counter + * sums. + * + * Return: + * * %0 - Counters are equal. + * * %-1 - Counter @a less than counter @b. + * * %1 - Counter @a is greater than counter @b. + */ +int percpu_counter_tree_precise_compare(struct percpu_counter_tree *a, str= uct percpu_counter_tree *b) +{ + long count_a =3D percpu_counter_tree_approximate_sum(a), + count_b =3D percpu_counter_tree_approximate_sum(b); + unsigned long accuracy_a, accuracy_b; + long delta =3D count_a - count_b; + int res; + + res =3D compare_delta(delta, + a->approx_accuracy_range.over + b->approx_accuracy_range.under, + a->approx_accuracy_range.under + b->approx_accuracy_range.over); + /* The values are distanced enough for an accurate approximated compariso= n. */ + if (res) + return res; + + /* + * The approximated comparison is within the accuracy range, therefore at= least one + * precise sum is needed. Sum the counter which has the largest accuracy = first. + */ + if (delta >=3D 0) { + accuracy_a =3D a->approx_accuracy_range.under; + accuracy_b =3D b->approx_accuracy_range.over; + } else { + accuracy_a =3D a->approx_accuracy_range.over; + accuracy_b =3D b->approx_accuracy_range.under; + } + if (accuracy_b < accuracy_a) { + count_a =3D percpu_counter_tree_precise_sum(a); + res =3D compare_delta(count_a - count_b, + b->approx_accuracy_range.under, + b->approx_accuracy_range.over); + if (res) + return res; + /* Precise sum of second counter is required. */ + count_b =3D percpu_counter_tree_precise_sum(b); + } else { + count_b =3D percpu_counter_tree_precise_sum(b); + res =3D compare_delta(count_a - count_b, + a->approx_accuracy_range.over, + a->approx_accuracy_range.under); + if (res) + return res; + /* Precise sum of second counter is required. */ + count_a =3D percpu_counter_tree_precise_sum(a); + } + if (count_a - count_b < 0) + return -1; + if (count_a - count_b > 0) + return 1; + return 0; +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare); + +/** + * percpu_counter_tree_precise_compare_value - Precise comparison of a cou= nter tree against a given value. + * @counter: Counter to compare. + * @v: Value to compare. + * + * Evaluate a precise comparison of a counter tree against a given value. + * As an optimization, it uses the approximate counter comparison + * to quickly identify whether the counter and value are far apart. + * Only cases where the value is within the counter accuracy range + * require a precise counter sum. + * + * Return: + * * %0 - The value @v is equal to the counter. + * * %-1 - The value @v is less than the counter. + * * %1 - The value @v is greater than the counter. + */ +int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *= counter, long v) +{ + long count =3D percpu_counter_tree_approximate_sum(counter); + int res; + + res =3D compare_delta(v - count, + counter->approx_accuracy_range.under, + counter->approx_accuracy_range.over); + /* The values are distanced enough for an accurate approximated compariso= n. */ + if (res) + return res; + + /* Precise sum is required. */ + count =3D percpu_counter_tree_precise_sum(counter); + if (v - count < 0) + return -1; + if (v - count > 0) + return 1; + return 0; +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare_value); + +static +void percpu_counter_tree_set_bias(struct percpu_counter_tree *counter, lon= g bias) +{ + WRITE_ONCE(counter->bias, bias); +} + +/** + * percpu_counter_tree_set - Set the counter tree sum to a given value. + * @counter: Counter to set. + * @v: Value to set. + * + * Set the counter sum to a given value. It can be useful for instance + * to reset the counter sum to 0. Note that even after setting the + * counter sum to a given value, the counter sum approximation can + * return any value within the accuracy range around that value. + */ +void percpu_counter_tree_set(struct percpu_counter_tree *counter, long v) +{ + percpu_counter_tree_set_bias(counter, + v - percpu_counter_tree_precise_sum_unbiased(counter)); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_set); + +/* + * percpu_counter_tree_items_size - Query the size required for counter tr= ee items. + * + * Query the size of the memory area required to hold the counter tree + * items. This depends on the hardware topology and is invariant after + * boot. + * + * Return: Size required to hold tree items. + */ +size_t percpu_counter_tree_items_size(void) +{ + if (!nr_cpus_order) + return 0; + return counter_config->nr_items * sizeof(struct percpu_counter_tree_level= _item); +} +EXPORT_SYMBOL_GPL(percpu_counter_tree_items_size); + +static void __init calculate_accuracy_topology(void) +{ + unsigned int nr_levels =3D counter_config->nr_levels, level; + unsigned int level_items =3D 1U << nr_cpus_order; + unsigned long batch_size =3D 1; + + for (level =3D 0; level < nr_levels; level++) { + unsigned int n_arity_order =3D counter_config->n_arity_order[level]; + + /* + * The accuracy multiplier is derived from a batch size of 1 + * to speed up calculating the accuracy at tree initialization. + */ + accuracy_multiplier +=3D batch_size * level_items; + batch_size <<=3D n_arity_order; + level_items >>=3D n_arity_order; + } +} + +int __init percpu_counter_tree_subsystem_init(void) +{ + nr_cpus_order =3D get_count_order(nr_cpu_ids); + if (WARN_ON_ONCE(nr_cpus_order >=3D ARRAY_SIZE(per_nr_cpu_order_config)))= { + printk(KERN_ERR "Unsupported number of CPUs (%u)\n", nr_cpu_ids); + return -1; + } + counter_config =3D &per_nr_cpu_order_config[nr_cpus_order]; + calculate_accuracy_topology(); + return 0; +} --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C67243E44ED for ; Fri, 4 Sep 2026 16:07:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538075; cv=none; b=nf54o0AIdqU2bHNkL/SaYUYuVyyK/NC7au+7mlNFeihTDqsB5ZRjya/RmexZxtzAuNn6P3nGtlp4af/ymZhh4sWeRKdNHxpDsj5bDweu8arYBUiQUMKHUulylKryBnHNCt5d/W9fXPKrYzAF1NVFnDybD16e3HDig7NQE9cqLDw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538075; c=relaxed/simple; bh=NnjPSnVYedhRhWI76knfpDgI5uJSnTKtJUZv2sO1wRo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=RceMUz48FJ2SNjKrMtXJ99+qgVrulcRT17IJz6M3Ztq8QSXznuBP+13dm4fZnXaRpdJF3KWqgxK60sEsCyKqnjtO7BpF0gmdURqjWs/a1pRnlqihh4CuZEmcByCFkhHzF49VBUXy4ToDvzqrcH7GtVNyM5lYQ33CvzISnn4rimQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=TVMRNpdR; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="TVMRNpdR" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538057; bh=tL1cmKSs0ZNOuF7NNYcj/4wBqlHVdgHSzS/qIxPqsfg=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=TVMRNpdR4irqd+KXoAZHu4cVDh/3JMWFTxlrYkqbrzDz1OmLPAw7B7KDGa07j+vot KVDPelqDC2CkIs2JEXoSkfmkihhzIznBz5FHYSq7WkgpeHY4EQdkOuvHilgdYkPzru mm3s3qdLG0NaJ5pRY5dGXDbdVKmYfoyXOZeRLcXTf8Djai4RvAa+y874/LzzW6O0H8 qGeDvF9xKVTpjtsrIN0z83xTI4pQH1+GJ0vXoK76HqAMTqN4yYD5dNtphlRoAwnFnb tXrFQLvXUdGLNZsS5t9KyD9MLk6SjYur3+yM6WWDbOTsr7KFGzcB5hm9pDweYE+zwN kXc76ZhrKesjQ== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zd3YwYzVqf; Fri, 04 Sep 2026 12:07:37 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 02/10] lib: test hierarchical per-cpu counters Date: Fri, 4 Sep 2026 12:07:14 -0400 Message-ID: <20260904160734.23445-3-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce Kunit tests for hierarchical per-cpu counters. Keep track of two sets of hierarchical counters, each meant to have the same precise sum at any time, but distributed differently across the topology. Keep track of an atomic counter along with each hierarchical counter, for sum validation. Those tests cover: - Single-threaded (no concurrency) updates. - Concurrent updates of counters from various CPUs. Perform the following validations: - Compare the precise sum of counters with the sum tracked by an atomic counter. - Compare the precise sum of two sets of hierarchical counters. - Approximated comparison of hierarchical counter with atomic counter. - Approximated comparison of two sets of hierarchical counters. - Validate the bounds of approximation ranges. Run with the following .kunit/.kunitconfig: CONFIG_KUNIT=3Dy CONFIG_SMP=3Dy CONFIG_PREEMPT=3Dy CONFIG_NR_CPUS=3D32 CONFIG_HOTPLUG_CPU=3Dy CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST=3Dy With the following execution (to use SMP): ./tools/testing/kunit/kunit.py run --arch=3Dx86_64 --qemu_args=3D"-smp 12" Link: https://lkml.kernel.org/r/20260227153730.1556542-3-mathieu.desnoyers@= efficios.com Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- Changes since v19: - Rename config option to PERCPU_COUNTER_TREE_KUNIT_TEST. --- lib/Kconfig | 12 + lib/tests/Makefile | 2 + lib/tests/percpu_counter_tree_kunit.c | 399 ++++++++++++++++++++++++++ 3 files changed, 413 insertions(+) create mode 100644 lib/tests/percpu_counter_tree_kunit.c diff --git a/lib/Kconfig b/lib/Kconfig index 4e6b34c3346d..c0524258b205 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -41,6 +41,18 @@ config PACKING_KUNIT_TEST =20 When in doubt, say N. =20 +config PERCPU_COUNTER_TREE_KUNIT_TEST + tristate "KUnit tests for hierarchical per-cpu counters" if !KUNIT_ALL_TE= STS + depends on KUNIT + default KUNIT_ALL_TESTS + help + This builds Kunit tests for the hierarchical per-cpu counters. + + For more information on KUnit and unit tests in general, + please refer to the KUnit documentation in Documentation/dev-tools/kuni= t/. + + When in doubt, say N. + config BITREVERSE tristate select GENERIC_BITREVERSE if !HAVE_ARCH_BITREVERSE diff --git a/lib/tests/Makefile b/lib/tests/Makefile index 3cac3b63a752..051e73705977 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -58,4 +58,6 @@ obj-$(CONFIG_UTIL_MACROS_KUNIT) +=3D util_macros_kunit.o obj-$(CONFIG_RATELIMIT_KUNIT_TEST) +=3D test_ratelimit.o obj-$(CONFIG_UUID_KUNIT_TEST) +=3D uuid_kunit.o =20 +obj-$(CONFIG_PERCPU_COUNTER_TREE_KUNIT_TEST) +=3D percpu_counter_tree_kuni= t.o + obj-$(CONFIG_TEST_RUNTIME_MODULE) +=3D module/ diff --git a/lib/tests/percpu_counter_tree_kunit.c b/lib/tests/percpu_count= er_tree_kunit.c new file mode 100644 index 000000000000..a79176655c4b --- /dev/null +++ b/lib/tests/percpu_counter_tree_kunit.c @@ -0,0 +1,399 @@ +// SPDX-License-Identifier: GPL-2.0+ OR MIT +// SPDX-FileCopyrightText: 2026 Mathieu Desnoyers + +#include +#include +#include +#include +#include + +struct multi_thread_test_data { + long increment; + int nr_inc; + int counter_index; +}; + +#define NR_COUNTERS 2 + +/* Hierarchical per-CPU counter instances. */ +static struct percpu_counter_tree counter[NR_COUNTERS]; +static struct percpu_counter_tree_level_item *items; + +/* Global atomic counters for validation. */ +static atomic_long_t global_counter[NR_COUNTERS]; + +static DECLARE_WAIT_QUEUE_HEAD(kernel_threads_wq); +static atomic_t kernel_threads_to_run; + +static void complete_work(void) +{ + if (atomic_dec_and_test(&kernel_threads_to_run)) + wake_up(&kernel_threads_wq); +} + +static void hpcc_print_info(struct kunit *test) +{ + kunit_info(test, "Running test with %d CPUs\n", num_online_cpus()); +} + +static void add_to_counter(int counter_index, unsigned int nr_inc, long in= crement) +{ + unsigned int i; + + for (i =3D 0; i < nr_inc; i++) { + percpu_counter_tree_add(&counter[counter_index], increment); + atomic_long_add(increment, &global_counter[counter_index]); + } +} + +static void check_counters(struct kunit *test) +{ + int counter_index; + + /* Compare each counter with its global counter. */ + for (counter_index =3D 0; counter_index < NR_COUNTERS; counter_index++) { + long v =3D atomic_long_read(&global_counter[counter_index]); + long approx_sum =3D percpu_counter_tree_approximate_sum(&counter[counter= _index]); + unsigned long under_accuracy =3D 0, over_accuracy =3D 0; + long precise_min, precise_max; + + /* Precise comparison. */ + KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&counter[counter_i= ndex]), v); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare_value(&coun= ter[counter_index], v)); + + /* Approximate comparison. */ + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&= counter[counter_index], v)); + + /* Accuracy limits checks. */ + percpu_counter_tree_approximate_accuracy_range(&counter[counter_index], = &under_accuracy, &over_accuracy); + + KUNIT_EXPECT_GE(test, (long)(approx_sum - (v - under_accuracy)), 0); + KUNIT_EXPECT_LE(test, (long)(approx_sum - (v + over_accuracy)), 0); + KUNIT_EXPECT_GT(test, (long)(approx_sum - (v - under_accuracy - 1)), 0); + KUNIT_EXPECT_LT(test, (long)(approx_sum - (v + over_accuracy + 1)), 0); + + /* Precise min/max range check. */ + percpu_counter_tree_approximate_min_max_range(approx_sum, under_accuracy= , over_accuracy, &precise_min, &precise_max); + + KUNIT_EXPECT_GE(test, v - precise_min, 0); + KUNIT_EXPECT_LE(test, v - precise_max, 0); + KUNIT_EXPECT_GT(test, v - (precise_min - 1), 0); + KUNIT_EXPECT_LT(test, v - (precise_max + 1), 0); + } + /* Compare each counter with the second counter. */ + KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&counter[0]), percp= u_counter_tree_precise_sum(&counter[1])); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_precise_compare(&counter[0],= &counter[1])); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare(&counter= [0], &counter[1])); +} + +static int multi_thread_worker_fn(void *data) +{ + struct multi_thread_test_data *td =3D data; + + add_to_counter(td->counter_index, td->nr_inc, td->increment); + complete_work(); + kfree(td); + return 0; +} + +static void test_run_on_specific_cpu(struct kunit *test, int target_cpu, i= nt counter_index, unsigned int nr_inc, long increment) +{ + struct task_struct *task; + struct multi_thread_test_data *td =3D kzalloc(sizeof(struct multi_thread_= test_data), GFP_KERNEL); + + KUNIT_EXPECT_PTR_NE(test, td, NULL); + td->increment =3D increment; + td->nr_inc =3D nr_inc; + td->counter_index =3D counter_index; + atomic_inc(&kernel_threads_to_run); + task =3D kthread_run_on_cpu(multi_thread_worker_fn, td, target_cpu, "kuni= t_multi_thread_worker"); + KUNIT_ASSERT_NOT_ERR_OR_NULL(test, task); +} + +static void init_kthreads(void) +{ + atomic_set(&kernel_threads_to_run, 1); +} + +static void fini_kthreads(void) +{ + /* Release our own reference. */ + complete_work(); + /* Wait for all others threads to run. */ + wait_event(kernel_threads_wq, (atomic_read(&kernel_threads_to_run) =3D=3D= 0)); +} + +static void test_sync_kthreads(void) +{ + fini_kthreads(); + init_kthreads(); +} + +static void init_counters(struct kunit *test, unsigned long batch_size) +{ + int i, ret; + + items =3D kzalloc(percpu_counter_tree_items_size() * NR_COUNTERS, GFP_KER= NEL); + KUNIT_EXPECT_PTR_NE(test, items, NULL); + ret =3D percpu_counter_tree_init_many(counter, items, NR_COUNTERS, batch_= size, GFP_KERNEL); + KUNIT_EXPECT_EQ(test, ret, 0); + + for (i =3D 0; i < NR_COUNTERS; i++) + atomic_long_set(&global_counter[i], 0); +} + +static void fini_counters(void) +{ + percpu_counter_tree_destroy_many(counter, NR_COUNTERS); + kfree(items); +} + +enum up_test_inc_type { + INC_ONE, + INC_MINUS_ONE, + INC_RANDOM, +}; + +/* + * Single-threaded tests. Those use many threads to run on various CPUs, + * but synchronize for completion of each thread before running the + * next, effectively making sure there are no concurrent updates. + */ +static void do_hpcc_test_single_thread(struct kunit *test, int _cpu0, int = _cpu1, enum up_test_inc_type type) +{ + unsigned long batch_size_order =3D 5; + int cpu0 =3D _cpu0; + int cpu1 =3D _cpu1; + int i; + + init_counters(test, 1UL << batch_size_order); + init_kthreads(); + for (i =3D 0; i < 10000; i++) { + long increment; + + switch (type) { + case INC_ONE: + increment =3D 1; + break; + case INC_MINUS_ONE: + increment =3D -1; + break; + case INC_RANDOM: + increment =3D (long) get_random_long() % 50000; + break; + } + if (_cpu0 < 0) + cpu0 =3D cpumask_any_distribute(cpu_online_mask); + if (_cpu1 < 0) + cpu1 =3D cpumask_any_distribute(cpu_online_mask); + test_run_on_specific_cpu(test, cpu0, 0, 1, increment); + test_sync_kthreads(); + test_run_on_specific_cpu(test, cpu1, 1, 1, increment); + test_sync_kthreads(); + check_counters(test); + } + fini_kthreads(); + fini_counters(); +} + +static void hpcc_test_single_thread_first(struct kunit *test) +{ + int cpu =3D cpumask_first(cpu_online_mask); + + do_hpcc_test_single_thread(test, cpu, cpu, INC_ONE); + do_hpcc_test_single_thread(test, cpu, cpu, INC_MINUS_ONE); + do_hpcc_test_single_thread(test, cpu, cpu, INC_RANDOM); +} + +static void hpcc_test_single_thread_first_random(struct kunit *test) +{ + int cpu =3D cpumask_first(cpu_online_mask); + + do_hpcc_test_single_thread(test, cpu, -1, INC_ONE); + do_hpcc_test_single_thread(test, cpu, -1, INC_MINUS_ONE); + do_hpcc_test_single_thread(test, cpu, -1, INC_RANDOM); +} + +static void hpcc_test_single_thread_random(struct kunit *test) +{ + do_hpcc_test_single_thread(test, -1, -1, INC_ONE); + do_hpcc_test_single_thread(test, -1, -1, INC_MINUS_ONE); + do_hpcc_test_single_thread(test, -1, -1, INC_RANDOM); +} + +/* Multi-threaded SMP tests. */ + +static void do_hpcc_multi_thread_increment_each_cpu(struct kunit *test, un= signed long batch_size, unsigned int nr_inc, long increment) +{ + int cpu; + + init_counters(test, batch_size); + init_kthreads(); + for_each_online_cpu(cpu) { + test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); + test_run_on_specific_cpu(test, cpu, 1, nr_inc, increment); + } + fini_kthreads(); + check_counters(test); + fini_counters(); +} + +static void do_hpcc_multi_thread_increment_even_cpus(struct kunit *test, u= nsigned long batch_size, unsigned int nr_inc, long increment) +{ + int cpu; + + init_counters(test, batch_size); + init_kthreads(); + for_each_online_cpu(cpu) { + test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); + test_run_on_specific_cpu(test, cpu & ~1, 1, nr_inc, increment); /* even = cpus. */ + } + fini_kthreads(); + check_counters(test); + fini_counters(); +} + +static void do_hpcc_multi_thread_increment_single_cpu(struct kunit *test, = unsigned long batch_size, unsigned int nr_inc, long increment) +{ + int cpu; + + init_counters(test, batch_size); + init_kthreads(); + for_each_online_cpu(cpu) { + test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); + test_run_on_specific_cpu(test, cpumask_first(cpu_online_mask), 1, nr_inc= , increment); + } + fini_kthreads(); + check_counters(test); + fini_counters(); +} + +static void do_hpcc_multi_thread_increment_random_cpu(struct kunit *test, = unsigned long batch_size, unsigned int nr_inc, long increment) +{ + int cpu; + + init_counters(test, batch_size); + init_kthreads(); + for_each_online_cpu(cpu) { + test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); + test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask), = 1, nr_inc, increment); + } + fini_kthreads(); + check_counters(test); + fini_counters(); +} + +static void hpcc_test_multi_thread_batch_increment(struct kunit *test) +{ + unsigned long batch_size_order; + + for (batch_size_order =3D 2; batch_size_order < 10; batch_size_order++) { + unsigned int nr_inc; + + for (nr_inc =3D 1; nr_inc < 1024; nr_inc *=3D 2) { + long increment; + + for (increment =3D 1; increment < 100000; increment *=3D 10) { + do_hpcc_multi_thread_increment_each_cpu(test, 1UL << batch_size_order,= nr_inc, increment); + do_hpcc_multi_thread_increment_even_cpus(test, 1UL << batch_size_order= , nr_inc, increment); + do_hpcc_multi_thread_increment_single_cpu(test, 1UL << batch_size_orde= r, nr_inc, increment); + do_hpcc_multi_thread_increment_random_cpu(test, 1UL << batch_size_orde= r, nr_inc, increment); + } + } + } +} + +static void hpcc_test_multi_thread_random_walk(struct kunit *test) +{ + unsigned long batch_size_order =3D 5; + int loop; + + for (loop =3D 0; loop < 100; loop++) { + int i; + + init_counters(test, 1UL << batch_size_order); + init_kthreads(); + for (i =3D 0; i < 1000; i++) { + long increment =3D (long) get_random_long() % 512; + unsigned int nr_inc =3D ((unsigned long) get_random_long()) % 1024; + + test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask),= 0, nr_inc, increment); + test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask),= 1, nr_inc, increment); + } + fini_kthreads(); + check_counters(test); + fini_counters(); + } +} + +static void hpcc_test_init_one(struct kunit *test) +{ + struct percpu_counter_tree pct; + struct percpu_counter_tree_level_item *counter_items; + int ret; + + counter_items =3D kzalloc(percpu_counter_tree_items_size(), GFP_KERNEL); + KUNIT_EXPECT_PTR_NE(test, counter_items, NULL); + ret =3D percpu_counter_tree_init(&pct, counter_items, 32, GFP_KERNEL); + KUNIT_EXPECT_EQ(test, ret, 0); + + percpu_counter_tree_destroy(&pct); + kfree(counter_items); +} + +static void hpcc_test_set(struct kunit *test) +{ + static long values[] =3D { + 5, 100, 127, 128, 255, 256, 4095, 4096, 500000, 0, + -5, -100, -127, -128, -255, -256, -4095, -4096, -500000, + }; + struct percpu_counter_tree pct; + struct percpu_counter_tree_level_item *counter_items; + int i, ret; + + counter_items =3D kzalloc(percpu_counter_tree_items_size(), GFP_KERNEL); + KUNIT_EXPECT_PTR_NE(test, counter_items, NULL); + ret =3D percpu_counter_tree_init(&pct, counter_items, 32, GFP_KERNEL); + KUNIT_EXPECT_EQ(test, ret, 0); + + for (i =3D 0; i < ARRAY_SIZE(values); i++) { + long v =3D values[i]; + + percpu_counter_tree_set(&pct, v); + KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), v); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&= pct, v)); + + percpu_counter_tree_add(&pct, v); + KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), 2 * v); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&= pct, 2 * v)); + + percpu_counter_tree_add(&pct, -2 * v); + KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&pct), 0); + KUNIT_EXPECT_EQ(test, 0, percpu_counter_tree_approximate_compare_value(&= pct, 0)); + } + + percpu_counter_tree_destroy(&pct); + kfree(counter_items); +} + +static struct kunit_case hpcc_test_cases[] =3D { + KUNIT_CASE(hpcc_print_info), + KUNIT_CASE(hpcc_test_single_thread_first), + KUNIT_CASE(hpcc_test_single_thread_first_random), + KUNIT_CASE(hpcc_test_single_thread_random), + KUNIT_CASE(hpcc_test_multi_thread_batch_increment), + KUNIT_CASE(hpcc_test_multi_thread_random_walk), + KUNIT_CASE(hpcc_test_init_one), + KUNIT_CASE(hpcc_test_set), + {} +}; + +static struct kunit_suite hpcc_test_suite =3D { + .name =3D "percpu_counter_tree", + .test_cases =3D hpcc_test_cases, +}; + +kunit_test_suite(hpcc_test_suite); + +MODULE_DESCRIPTION("Test cases for hierarchical per-CPU counters"); +MODULE_LICENSE("Dual MIT/GPL"); --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B3AF23E5A0A for ; Fri, 4 Sep 2026 16:07:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538072; cv=none; b=j0CxC9K2L0eedEJZxWlOkVbp9qHzVhFfOsUlozOPj29q7D5wWZptX6tqzzyxOY5z4nEQbEt0+jOXD+TF2utn2udTLsRilXWOEEaiCFbiAOmlIl7SvpWNtD7RESIiPszT2mnEctbmu7Ut5UBii/GhJUK1kba+n5uGs1VTZrQ1yf8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538072; c=relaxed/simple; bh=xvPbcwqICKrt5ycWdQQH/2agWCABQ992DpE0sksopWU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=ARjqfdRAYWbksBKJZWR/K8X1By0Dk2QKokq9kXwiTae5DW0hRPVDLfDO+6WE47+EqLm16oXFozjuaRPMpmys8LN0nFvf1s55HEWj5uI0SdYtBd76ASaW44VndnYtJhZDg9JvsU2uGNaLuFlfWCwUpPBgIZWTGTZqa60xkPk09t0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=aCY8I/E4; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="aCY8I/E4" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538057; bh=Q5XjUMcgmvN6EiMKr1kiGvv/bXDNdn2svG6c9pEzr3Y=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=aCY8I/E4AZotvStO3XxDJslKNIh2d6ZCQc8isQzd1KAGAKHUkRoSYS2zMOMdmcwud hk405Eb/ymckhJ3tOyC3oVKHolpksgZlZtva+l8AnkqoTmFQrtiP+98maqgBT/NGPZ uH53XzTwD+uhx+cAvuwyepwRp1sLcrWEAz0/GBP5/1u3O4PXDBfZYZ2K9HCsTa7B9o UeCNTjdyMEUZTYXmHkOq9BrnwU+tYG5nyUTeKmjHQaP6M7Gd1cKR329UgWxJBph+ag IuQtgW48r8jZ0h+vmN/y7Jjm7Kkrk1vcK8+32NW1xZGNw4D7KhiJRbU8L5JrdCMAof 5IiUbuznJP6Sg== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zd4jrRzWpK; Fri, 04 Sep 2026 12:07:37 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 03/10] mm: improve RSS counter approximation accuracy for proc interfaces Date: Fri, 4 Sep 2026 12:07:15 -0400 Message-ID: <20260904160734.23445-4-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Use hierarchical per-cpu counters for RSS tracking to improve the accuracy of per-mm RSS sum approximation on large many-core systems [1]. This improves the accuracy of the RSS values returned by proc interfaces. Here is a (possibly incomplete) list of the prior approaches that were used or proposed, along with their downside: 1) Per-thread rss tracking: large error on many-thread processes. 2) Per-CPU counters: up to 12% slower for short-lived processes and 9% increased system time in make test workloads [1]. Moreover, the inaccuracy increases with O(n^2) with the number of CPUs. 3) Per-NUMA-node counters: requires atomics on fast-path (overhead), error is high with systems that have lots of NUMA nodes (32 times the number of NUMA nodes). 4) Use a percise per-cpu counter sum for each counter value query: Requires iteration on each possible CPUs for each sum, which adds overhead on large many-core systems running many processes. The approach proposed here is to replace the per-cpu counters by the hierarchical per-cpu counters, which bounds the inaccuracy based on the system topology with O(N*logN). * Testing results: Test hardware: 2 sockets AMD EPYC 9654 96-Core Processor (384 logical CPUs = total) Methodology: Comparing the current upstream implementation with the hierarchical counters is done by keeping both implementations wired up in parallel, and running a single-process, single-threaded program which hops randomly across CPUs in the system, calling mmap(2) and munmap(2) on random CPUs, keeping track of an array of allocated mappings, randomly choosing entries to either map or unmap. get_mm_counter() is instrumented to compare the upstream counter approximation to the precise value, and print the delta when going over a given threshold. The delta of the hierarchical counter approximation to the precise value is also printed for comparison. After a few minutes running this test, the upstream implementation counter approximation reaches a 1GB delta from the precise value, compared to 80MB delta with the hierarchical counter. The hierarchical counter provides a guaranteed maximum approximation inaccuracy of 192MB on that hardware topology. * Fast path implementation comparison The new inline percpu_counter_tree_add() uses a this_cpu_add_return() for the fast path (under a certain allocation size threshold). Above that, it calls a slow path which "trickles up" the carry to upper level counters with atomic_add_return. In comparison, the upstream counters implementation calls percpu_counter_add_batch which uses this_cpu_try_cmpxchg() on the fast path, and does a raw_spin_lock_irqsave above a certain threshold. The hierarchical implementation is therefore expected to have less contention on mid-sized allocations than the upstream counters because the atomic counters tracking those bits are only shared across nearby CPUs. In comparison, the upstream counters immediately use a global spinlock when reaching the threshold. * Benchmarks Using will-it-scale page_fault1 benchmarks to compare the upstream counters to the hierarchical counters. This is done with hyperthreading disabled. The speedup is within the standard deviation of the upstream runs, so the overhead is not significant. upstream hierarchical speedup page_fault1_processes -s 100 -t 1 614783 615558 +0.1% page_fault1_threads -s 100 -t 1 612788 612447 -0.1% page_fault1_processes -s 100 -t 96 37994977 37932035 -0.2% page_fault1_threads -s 100 -t 96 2484130 2504860 +0.8% page_fault1_processes -s 100 -t 192 71262917 71118830 -0.2% page_fault1_threads -s 100 -t 192 2446437 2469296 +0.1% * Memory Use The most important parts in terms of memory use are the per-cpu counters and the tree items which propagate the carry. In the proposed implementation, the per-cpu counters are allocated within per-cpu data structures, so they end up using: nr_possible_cpus * sizeof(unsigned long) This is in addition to the tree items. The size of those items is defined by the per_nr_cpu_order_config table "nr_items" field. Each item is aligned on cacheline size (typically 64 bytes) to minimize false sharing. Here is the footprint for a few nr_cpu_ids on a 64-bit arch: nr_cpu_ids percpu counters (bytes) nr_items items size (bytes) = total (bytes) 2 16 1 64 = 80 4 32 3 192 = 224 8 64 7 448 = 512 64 512 21 1344 = 1856 128 1024 21 1344 = 2368 256 2048 37 2368 = 4416 512 4096 73 4672 = 8768 Compared to this, the upstream percpu counters use a 32-bit integer per-cpu (4 bytes), and accumulate within a 64-bit global value. So there is an extra memory footprint added by the current hpcc implementation, but if it's an issue we have various options to consider to reduce its footprint. Link: https://lore.kernel.org/lkml/20250331223516.7810-2-sweettea-kernel@do= rminy.me/ # [1] Link: https://lkml.kernel.org/r/20260227153730.1556542-4-mathieu.desnoyers@= efficios.com Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- include/linux/mm.h | 19 ++++++++++---- include/linux/mm_types.h | 50 +++++++++++++++++++++++++++---------- include/trace/events/kmem.h | 2 +- kernel/fork.c | 22 +++++++++------- 4 files changed, 65 insertions(+), 28 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index dd09c438fa23..7dd6fdda9bc8 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -3447,38 +3447,47 @@ static inline bool get_user_page_fast_only(unsigned= long addr, { return get_user_pages_fast_only(addr, 1, gup_flags, pagep) =3D=3D 1; } + +static inline struct percpu_counter_tree_level_item *get_rss_stat_items(st= ruct mm_struct *mm) +{ + unsigned long ptr =3D (unsigned long)mm; + + ptr +=3D offsetof(struct mm_struct, flexible_array); + return (struct percpu_counter_tree_level_item *)ptr; +} + /* * per-process(per-mm_struct) statistics. */ static inline unsigned long get_mm_counter(struct mm_struct *mm, int membe= r) { - return percpu_counter_read_positive(&mm->rss_stat[member]); + return percpu_counter_tree_approximate_sum_positive(&mm->rss_stat[member]= ); } =20 static inline unsigned long get_mm_counter_sum(struct mm_struct *mm, int m= ember) { - return percpu_counter_sum_positive(&mm->rss_stat[member]); + return percpu_counter_tree_precise_sum_positive(&mm->rss_stat[member]); } =20 void mm_trace_rss_stat(struct mm_struct *mm, int member); =20 static inline void add_mm_counter(struct mm_struct *mm, int member, long v= alue) { - percpu_counter_add(&mm->rss_stat[member], value); + percpu_counter_tree_add(&mm->rss_stat[member], value); =20 mm_trace_rss_stat(mm, member); } =20 static inline void inc_mm_counter(struct mm_struct *mm, int member) { - percpu_counter_inc(&mm->rss_stat[member]); + percpu_counter_tree_add(&mm->rss_stat[member], 1); =20 mm_trace_rss_stat(mm, member); } =20 static inline void dec_mm_counter(struct mm_struct *mm, int member) { - percpu_counter_dec(&mm->rss_stat[member]); + percpu_counter_tree_add(&mm->rss_stat[member], -1); =20 mm_trace_rss_stat(mm, member); } diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h index dff5fd1c1b06..96ad6ac20b11 100644 --- a/include/linux/mm_types.h +++ b/include/linux/mm_types.h @@ -18,7 +18,7 @@ #include #include #include -#include +#include #include #include #include @@ -1170,6 +1170,19 @@ typedef struct { DECLARE_BITMAP(__mm_flags, NUM_MM_FLAG_BITS); } __private mm_flags_t; =20 +/* + * The alignment of the mm_struct flexible array is based on the largest + * alignment of its content: + * __alignof__(struct percpu_counter_tree_level_item) provides a + * cacheline aligned alignment on SMP systems, else alignment on + * unsigned long on UP systems. + */ +#ifdef CONFIG_SMP +# define __mm_struct_flexible_array_aligned __aligned(__alignof__(struct p= ercpu_counter_tree_level_item)) +#else +# define __mm_struct_flexible_array_aligned __aligned(__alignof__(unsigned= long)) +#endif + struct kioctx_table; struct iommu_mm_data; struct mm_struct { @@ -1312,7 +1325,7 @@ struct mm_struct { unsigned long saved_e_flags; #endif =20 - struct percpu_counter rss_stat[NR_MM_COUNTERS]; + struct percpu_counter_tree rss_stat[NR_MM_COUNTERS]; =20 struct linux_binfmt *binfmt; =20 @@ -1422,10 +1435,13 @@ struct mm_struct { } __randomize_layout; =20 /* - * The mm_cpumask needs to be at the end of mm_struct, because it - * is dynamically sized based on nr_cpu_ids. + * The rss hierarchical counter items, mm_cpumask, and mm_cid + * masks need to be at the end of mm_struct, because they are + * dynamically sized based on nr_cpu_ids. + * The content of the flexible array needs to be placed in + * decreasing alignment requirement order. */ - char flexible_array[] __aligned(__alignof__(unsigned long)); + char flexible_array[] __mm_struct_flexible_array_aligned; }; =20 /* Copy value to the first system word of mm flags, non-atomically. */ @@ -1464,22 +1480,28 @@ extern struct mm_struct init_mm; =20 #define MM_STRUCT_FLEXIBLE_ARRAY_INIT \ { \ - [0 ... sizeof(cpumask_t) + MM_CID_STATIC_SIZE - 1] =3D 0 \ + [0 ... (PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE * NR_MM_COUNTERS) + sizeof(= cpumask_t) + MM_CID_STATIC_SIZE - 1] =3D 0 \ } =20 -/* Pointer magic because the dynamic array size confuses some compilers. */ -static inline void mm_init_cpumask(struct mm_struct *mm) +static inline size_t get_rss_stat_items_size(void) { - unsigned long cpu_bitmap =3D (unsigned long)mm; - - cpu_bitmap +=3D offsetof(struct mm_struct, flexible_array); - cpumask_clear((struct cpumask *)cpu_bitmap); + return percpu_counter_tree_items_size() * NR_MM_COUNTERS; } =20 /* Future-safe accessor for struct mm_struct's cpu_vm_mask. */ static inline cpumask_t *mm_cpumask(struct mm_struct *mm) { - return (struct cpumask *)&mm->flexible_array; + unsigned long ptr =3D (unsigned long)mm; + + ptr +=3D offsetof(struct mm_struct, flexible_array); + /* Skip RSS stats counters. */ + ptr +=3D get_rss_stat_items_size(); + return (struct cpumask *)ptr; +} + +static inline void mm_init_cpumask(struct mm_struct *mm) +{ + cpumask_clear((struct cpumask *)mm_cpumask(mm)); } =20 #ifdef CONFIG_LRU_GEN @@ -1571,6 +1593,8 @@ static inline cpumask_t *mm_cpus_allowed(struct mm_st= ruct *mm) unsigned long bitmap =3D (unsigned long)mm; =20 bitmap +=3D offsetof(struct mm_struct, flexible_array); + /* Skip RSS stats counters. */ + bitmap +=3D get_rss_stat_items_size(); /* Skip cpu_bitmap */ bitmap +=3D cpumask_size(); return (struct cpumask *)bitmap; diff --git a/include/trace/events/kmem.h b/include/trace/events/kmem.h index cd7920c81f85..290ccb9fd25d 100644 --- a/include/trace/events/kmem.h +++ b/include/trace/events/kmem.h @@ -448,7 +448,7 @@ TRACE_EVENT(rss_stat, */ __entry->curr =3D current->mm =3D=3D mm && !(current->flags & PF_KTHREAD= ); __entry->member =3D member; - __entry->size =3D (percpu_counter_sum_positive(&mm->rss_stat[member]) + __entry->size =3D (percpu_counter_tree_approximate_sum_positive(&mm->rss= _stat[member]) << PAGE_SHIFT); ), =20 diff --git a/kernel/fork.c b/kernel/fork.c index 416758c8a3d4..5bad7a24d186 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -137,6 +137,11 @@ */ #define MAX_THREADS FUTEX_TID_MASK =20 +/* + * Batch size of rss stat approximation + */ +#define RSS_STAT_BATCH_SIZE 32 + /* * Protected counters by write_lock_irq(&tasklist_lock) */ @@ -633,14 +638,12 @@ static void check_mm(struct mm_struct *mm) "Please make sure 'struct resident_page_types[]' is updated as well"); =20 for (i =3D 0; i < NR_MM_COUNTERS; i++) { - long x =3D percpu_counter_sum(&mm->rss_stat[i]); - - if (unlikely(x)) { + if (unlikely(percpu_counter_tree_precise_compare_value(&mm->rss_stat[i],= 0) !=3D 0)) pr_alert("BUG: Bad rss-counter state mm:%p type:%s val:%ld Comm:%s Pid:= %d\n", - mm, resident_page_types[i], x, + mm, resident_page_types[i], + percpu_counter_tree_precise_sum(&mm->rss_stat[i]), current->comm, task_pid_nr(current)); - } } =20 if (mm_pgtables_bytes(mm)) @@ -738,7 +741,7 @@ void __mmdrop(struct mm_struct *mm) check_mm(mm); mm_pasid_drop(mm); mm_destroy_cid(mm); - percpu_counter_destroy_many(mm->rss_stat, NR_MM_COUNTERS); + percpu_counter_tree_destroy_many(mm->rss_stat, NR_MM_COUNTERS); =20 free_mm(mm); } @@ -1144,8 +1147,9 @@ static struct mm_struct *mm_init(struct mm_struct *mm= , struct task_struct *p) if (mm_alloc_sched(mm)) goto fail_sched; =20 - if (percpu_counter_init_many(mm->rss_stat, 0, GFP_KERNEL_ACCOUNT, - NR_MM_COUNTERS)) + if (percpu_counter_tree_init_many(mm->rss_stat, get_rss_stat_items(mm), + NR_MM_COUNTERS, RSS_STAT_BATCH_SIZE, + GFP_KERNEL_ACCOUNT)) goto fail_pcpu; =20 lru_gen_init_mm(mm); @@ -3122,7 +3126,7 @@ void __init mm_cache_init(void) * dynamically sized based on the maximum CPU number this system * can have, taking hotplug into account (nr_cpu_ids). */ - mm_size =3D sizeof(struct mm_struct) + cpumask_size() + mm_cid_size(); + mm_size =3D sizeof(struct mm_struct) + cpumask_size() + mm_cid_size() + g= et_rss_stat_items_size(); =20 mm_cachep =3D kmem_cache_create_usercopy("mm_struct", mm_size, ARCH_MIN_MMSTRUCT_ALIGN, --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C59AA3E16A9 for ; Fri, 4 Sep 2026 16:07:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538071; cv=none; b=nZY9x9YL3kX2AvdQkNicXLNeuQ2l/NENg6ktFxnJ/h7Clilw+yHqRdEbRH+Sga44BaSvj3Qm4bFo/NhX/3AQOjMo/7ATmBTSYfRkCB4TLLnY4TGSzSspG+WfWlwoYrzltlOT31Y94S474ntoshkd8K6kROV56CxrOyaenETGS/8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538071; c=relaxed/simple; bh=hEnNJDWu/iKivIKNptkuLs6mjqBw72pkpWIdB/8pOYQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=rJnzsFe8YXXbwQYuaSGcU/3BO6txw/3pV5vVRKN4hYOhdyuW7YsmgY4jUo0zAtP/xm+iBt2cDaoD3HlZ3VYOEw7A0U3gNALHEh/cUtcZ5BO2UGaIieBMlwSZ/4/4P8jYXAE+TK/v6VXqFtxVafLgxhNNY/c4CxoBz/JNlDfUO7c= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=lp9uu06z; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="lp9uu06z" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538057; bh=hjDwQHd1TIkqr3Ad7cKo//QgmO9EQnnm4D2U1FbPu7k=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=lp9uu06zNPQl7khWMI1vssh/2dU1Ru/wZAZAUeCHuPfV7QBZkjo9/UElf5Q85z9+N qK9uSEPNd25d4bfkFlQPtjB9whU1NFhNgN0GGgI3y4mM6aAxIWHc0M4uivqu4ivxuX uBfY8e19VjWNXqsRO3un3IoAiKfu4FwnbL8NoK4lNCXZGqpP+RZwUhYct+psqbnrkC 6bOilv2IVEERA4lEhML4qr8xAxkrKif90thNkbJOTJARFBsuWiAlcatrqLZfm3JP53 rmUOG8CEP5PCmnYyt9BCHTBUA0xj9WfltXwXb/Pu3+z39kXsqndZJ1hFShSNAxxjfh OfT8AUlIRqi4Q== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zd5whLzWjm; Fri, 04 Sep 2026 12:07:37 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 04/10] mm: reorder mm_struct flexible array to place mm_cpumask first Date: Fri, 4 Sep 2026 12:07:16 -0400 Message-ID: <20260904160734.23445-5-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Reorder the mm_struct flexible array layout from: [HPCC tree items][mm_cpumask][mm_cid] to: [mm_cpumask][mm_cid][alignment padding][HPCC tree items] The previous layout placed the HPCC tree items first, which required mm_cpumask() to skip past them using percpu_counter_tree_items_size(). This created a boot-time initialization ordering dependency: any use of mm_cpumask() before percpu_counter_tree_subsystem_init() would compute the wrong pointer offset, reading from or writing to the HPCC items region instead of the actual cpumask. On powerpc, switch_mm_irqs_off() accesses mm_cpumask() early in boot via VM_WARN_ON_ONCE(!cpumask_test_cpu(cpu, mm_cpumask(prev))), which could fire spuriously or cause silent memory corruption if the HPCC subsystem was not yet initialized. By placing mm_cpumask first, mm_cpumask() remains a simple &mm->flexible_array with no runtime dependency on HPCC initialization. The HPCC tree items are accessed via get_rss_stat_items_offset(), which skips past the cpumask and mm_cid with appropriate cacheline alignment padding. This accessor is only used during mm_struct initialization (percpu_counter_tree_init_many), not on context switch or other hot paths. Introduce the PERCPU_COUNTER_TREE_ITEMS_ALIGN() macro to handle the SMP cacheline alignment vs !SMP no-op in a single place, used by both the static init_mm flexible array initializer and the runtime offset computation. The cost is at most one cacheline (typically 64 bytes) of padding per mm_struct between the mm_cid data and the HPCC tree items. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- include/linux/mm.h | 1 + include/linux/mm_types.h | 47 +++++++++++++++++------------ include/linux/percpu_counter_tree.h | 3 ++ kernel/fork.c | 4 ++- 4 files changed, 34 insertions(+), 21 deletions(-) diff --git a/include/linux/mm.h b/include/linux/mm.h index 7dd6fdda9bc8..ffbcd18c4ecb 100644 --- a/include/linux/mm.h +++ b/include/linux/mm.h @@ -3453,6 +3453,7 @@ static inline struct percpu_counter_tree_level_item *= get_rss_stat_items(struct m unsigned long ptr =3D (unsigned long)mm; =20 ptr +=3D offsetof(struct mm_struct, flexible_array); + ptr +=3D get_rss_stat_items_offset(); return (struct percpu_counter_tree_level_item *)ptr; } =20 diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h index 96ad6ac20b11..b26160b85f93 100644 --- a/include/linux/mm_types.h +++ b/include/linux/mm_types.h @@ -1435,11 +1435,12 @@ struct mm_struct { } __randomize_layout; =20 /* - * The rss hierarchical counter items, mm_cpumask, and mm_cid - * masks need to be at the end of mm_struct, because they are + * The mm_cpumask, mm_cid masks, and rss hierarchical counter + * items need to be at the end of mm_struct, because they are * dynamically sized based on nr_cpu_ids. - * The content of the flexible array needs to be placed in - * decreasing alignment requirement order. + * The HPCC counter tree items are placed last and aligned + * with PERCPU_COUNTER_TREE_ITEMS_ALIGN to satisfy their + * cacheline alignment requirement. */ char flexible_array[] __mm_struct_flexible_array_aligned; }; @@ -1478,25 +1479,18 @@ static inline void __mm_flags_set_mask_bits_word(st= ruct mm_struct *mm, MT_FLAGS_USE_RCU) extern struct mm_struct init_mm; =20 -#define MM_STRUCT_FLEXIBLE_ARRAY_INIT \ -{ \ - [0 ... (PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE * NR_MM_COUNTERS) + sizeof(= cpumask_t) + MM_CID_STATIC_SIZE - 1] =3D 0 \ -} - -static inline size_t get_rss_stat_items_size(void) -{ - return percpu_counter_tree_items_size() * NR_MM_COUNTERS; +#define MM_STRUCT_FLEXIBLE_ARRAY_INIT \ +{ \ + [0 ... PERCPU_COUNTER_TREE_ITEMS_ALIGN( \ + sizeof(cpumask_t) + MM_CID_STATIC_SIZE) \ + + (PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE * NR_MM_COUNTERS) \ + - 1] =3D 0 \ } =20 /* Future-safe accessor for struct mm_struct's cpu_vm_mask. */ static inline cpumask_t *mm_cpumask(struct mm_struct *mm) { - unsigned long ptr =3D (unsigned long)mm; - - ptr +=3D offsetof(struct mm_struct, flexible_array); - /* Skip RSS stats counters. */ - ptr +=3D get_rss_stat_items_size(); - return (struct cpumask *)ptr; + return (struct cpumask *)&mm->flexible_array; } =20 static inline void mm_init_cpumask(struct mm_struct *mm) @@ -1593,8 +1587,6 @@ static inline cpumask_t *mm_cpus_allowed(struct mm_st= ruct *mm) unsigned long bitmap =3D (unsigned long)mm; =20 bitmap +=3D offsetof(struct mm_struct, flexible_array); - /* Skip RSS stats counters. */ - bitmap +=3D get_rss_stat_items_size(); /* Skip cpu_bitmap */ bitmap +=3D cpumask_size(); return (struct cpumask *)bitmap; @@ -1677,6 +1669,21 @@ static inline void mm_destroy_sched(struct mm_struct= *mm) { } =20 #endif /* CONFIG_SCHED_CACHE */ =20 +static inline size_t get_rss_stat_items_size(void) +{ + return percpu_counter_tree_items_size() * NR_MM_COUNTERS; +} + +/* + * Return the offset of the RSS stat HPCC items within the mm_struct + * flexible array. The items are placed after the cpumask and mm_cid, + * aligned to the cacheline boundary required by the tree level items. + */ +static inline size_t get_rss_stat_items_offset(void) +{ + return PERCPU_COUNTER_TREE_ITEMS_ALIGN(cpumask_size() + mm_cid_size()); +} + struct mmu_gather; extern void tlb_gather_mmu(struct mmu_gather *tlb, struct mm_struct *mm); extern void tlb_gather_mmu_fullmm(struct mmu_gather *tlb, struct mm_struct= *mm); diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_cou= nter_tree.h index 828c763edd4a..3e8a820e2d1d 100644 --- a/include/linux/percpu_counter_tree.h +++ b/include/linux/percpu_counter_tree.h @@ -66,6 +66,8 @@ struct percpu_counter_tree_level_item { =20 #define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE \ (PERCPU_COUNTER_TREE_STATIC_NR_ITEMS * sizeof(struct percpu_counter_tree_= level_item)) +#define PERCPU_COUNTER_TREE_ITEMS_ALIGN(offset) \ + ALIGN((offset), __alignof__(struct percpu_counter_tree_level_item)) =20 struct percpu_counter_tree { /* Fast-path fields. */ @@ -167,6 +169,7 @@ void percpu_counter_tree_approximate_accuracy_range(str= uct percpu_counter_tree * #else /* !CONFIG_SMP */ =20 #define PERCPU_COUNTER_TREE_ITEMS_STATIC_SIZE 0 +#define PERCPU_COUNTER_TREE_ITEMS_ALIGN(offset) (offset) =20 struct percpu_counter_tree_level_item; =20 diff --git a/kernel/fork.c b/kernel/fork.c index 5bad7a24d186..db398b6c5288 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -3126,7 +3126,9 @@ void __init mm_cache_init(void) * dynamically sized based on the maximum CPU number this system * can have, taking hotplug into account (nr_cpu_ids). */ - mm_size =3D sizeof(struct mm_struct) + cpumask_size() + mm_cid_size() + g= et_rss_stat_items_size(); + mm_size =3D sizeof(struct mm_struct) + + PERCPU_COUNTER_TREE_ITEMS_ALIGN(cpumask_size() + mm_cid_size()) + + get_rss_stat_items_size(); =20 mm_cachep =3D kmem_cache_create_usercopy("mm_struct", mm_size, ARCH_MIN_MMSTRUCT_ALIGN, --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 512803C5522 for ; Fri, 4 Sep 2026 16:07:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538079; cv=none; b=QnoUzyK/vW80ty1pKJC1VzE+vLqtz0Fr+bRxlisZGxjY3S/w3gqa5acdNbJRhCsv46fw85rmQiPFhYiXoILE8a2Tma6FXBDwunC+mPej81b4fOm/k8NMVbrTjCQfn5vJ17S9I4DJ1Ri72irYGUIdBhoFoUUReU461I1i/IyF2wQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538079; c=relaxed/simple; bh=d0rPPJLR58Grj5g6WrWaYlhVdbvhMvShcBm1vU+F4qw=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=HD4ywOjl4GL/It0NQ5C3yW+y+I107BkntNY2YG+7mMYHH4m5iPNvXW8VQ9ZFnf/QHvIJi3yfVT/KlHGYYmzNN9ABuDrUOdojVx2Xqudx+LY//XIaeSubFv1j2nz9D3Kv1NHjQY6AzXeu8a+gE7QXEOtjuvIXNIc24H0ATzo6oaM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=cW6VJOSA; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="cW6VJOSA" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=MVIkjcqq74IZZNU1n5Q5hTuCbDzAa7ExJXxmdI4hdXI=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=cW6VJOSAfBFhelVHcj0Vu6YZwxjtUoz4A2tuXiPyDVOHLWBwEqJtNtQA9QKYKy4C2 opyQa4xh2f13h5yEhqS51TqSVAvLtPsYWy64nAE98WYZfD3SNGxyNA4D5+LqsKNhBP prsg2XS1x/SyowWHVR+RJd+4SVB2S1+GggUl0Sw0rq/KbLWFYGZCvsPRU6lM79drQV NH1mpUi6NK9AoaLU0G4fmLzSUg47Wor4KkqCleAMsyR5PT1DhykYbDJ+m2xTltXYVd +kKKAqdpbPHbCapIgqGXhiWdwPSMvPqKueNcqASNM4+LijddQ9IXZAUGJIX0zmR2u7 HDvUUqt5yIiww== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zd754SzWfd; Fri, 04 Sep 2026 12:07:37 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 05/10] init: move percpu_counter_tree_subsystem_init() earlier in boot Date: Fri, 4 Sep 2026 12:07:17 -0400 Message-ID: <20260904160734.23445-6-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Move percpu_counter_tree_subsystem_init() from after trap_init() to immediately after setup_nr_cpu_ids() in start_kernel(). The function's only dependency is nr_cpu_ids: it calls get_count_order(nr_cpu_ids), indexes into a const configuration table, and performs arithmetic to derive accuracy parameters. It requires no memory allocator, percpu areas, or other infrastructure. Initialize the subsystem as soon as its dependency is available rather than deferring until later in the boot sequence. This ensures percpu_counter_tree_items_size() returns the correct value well before its first use in mm_cache_init(). Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- init/main.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/init/main.c b/init/main.c index eda2170bb21f..845cb57e9096 100644 --- a/init/main.c +++ b/init/main.c @@ -1011,6 +1011,7 @@ void start_kernel(void) setup_boot_config(); setup_command_line(command_line); setup_nr_cpu_ids(); + percpu_counter_tree_subsystem_init(); setup_per_cpu_areas(); smp_prepare_boot_cpu(); /* arch-specific boot-cpu hooks */ early_numa_node_init(); @@ -1042,7 +1043,6 @@ void start_kernel(void) vfs_caches_init_early(); sort_main_extable(); trap_init(); - percpu_counter_tree_subsystem_init(); mm_core_init(); maple_tree_init(); poking_init(); --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5AFF83E5A07 for ; Fri, 4 Sep 2026 16:07:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538082; cv=none; b=EWhW1+x03QS6/ABXvfKExKaxvsXY+S6yJYJ3XQsl+YMi3GvPt7jPxeayLEgTlCzNIlxHmaSfpMXaR6Ih3bW5pRcFduC7D3LUAqfg0qF1rzGtD04703E+iQBc2bn78BucrYkpfC52oeDRuhq6zF/jwZelWrqp6dLiSec7u7H4yio= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538082; c=relaxed/simple; bh=FRBzQuF9NKvbTxzaWx4pzpaKcPAZeQr1CV0FO/0Fhpg=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=FZlEwqUgs8Ly6axnkw+K6S2niG8D25Bb6ALd7QmkHyBF6+wgOeHApiYuhmQ7cFZgw63MZnSbTMbpFOZlzOEnRyhHQMAJBUbs52i1Z2nqQ4YaUyAIeuRRERiE1QSTGvJgHpSX7ZLbTGABUqWR2ut6bHUhA9vnHPf4eeCF/IYdRlQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=iAI7MDjK; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="iAI7MDjK" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=Tup5QvhrUxBuHbOp/mUBjVWrl1apXEgoVpX9q/lsPY8=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=iAI7MDjKfQGX3aAx+Rv3MxGlwtRFZ3Q7uJJnX/myA4eyvbhkxvesBifrbSflySDKc qtfTvjE/PtSh/PiLzn6BXZmhyUq08ouLgs4IhSv8U5jkZp5uIbl/bYTIyuGJcBZydY wWIRzX9MxfPtbmjfmk7o3nanb2aBY3kQ+Q2TMgorh4b8Ad+WaZ/XnQ5kWqS072icfc AQCO8nUlCP94jI4O3VTtUWAJadMaOi7OHemMo8/aObgKGDKL2ontawa/yYgUxFZGQd F9xqcYpzfa4XaHL0p9d11yI26EWY8CEGEbfSxYdGbBA+2kRfm9jO6twR58jzAmpgYs L5SAfK70Ou0Ng== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zf19WkzWWX; Fri, 04 Sep 2026 12:07:38 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 06/10] lib: inline percpu_counter_tree_items_size with boot-safety sentinel Date: Fri, 4 Sep 2026 12:07:18 -0400 Message-ID: <20260904160734.23445-7-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace the out-of-line percpu_counter_tree_items_size() function with a static inline that loads the __ro_after_init variable __percpu_counter_tree_items_size directly. This eliminates a function call on paths that compute mm_struct flexible array layout offsets. Initialize the variable to SIZE_MAX as a sentinel value, and add a WARN_ON_ONCE check in the inline accessor to catch any accidental use before percpu_counter_tree_subsystem_init() sets the real value based on nr_cpu_ids. An early misuse would produce an absurd offset that triggers the warning with a stack trace pointing at the offending caller, rather than silently computing wrong memory offsets. percpu_counter_tree_subsystem_init() sets the variable to the runtime value immediately after deriving counter_config from nr_cpu_ids, before calculate_accuracy_topology(). After boot, __ro_after_init moves the variable into read-only memory. On !CONFIG_SMP, the existing inline returning 0 is unchanged and requires no sentinel. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- include/linux/percpu_counter_tree.h | 19 ++++++++++++++++++- lib/percpu_counter_tree.c | 24 ++++++++---------------- 2 files changed, 26 insertions(+), 17 deletions(-) diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_cou= nter_tree.h index 3e8a820e2d1d..4095acdc879b 100644 --- a/include/linux/percpu_counter_tree.h +++ b/include/linux/percpu_counter_tree.h @@ -101,7 +101,24 @@ struct percpu_counter_tree { } approx_accuracy_range; }; =20 -size_t percpu_counter_tree_items_size(void); +extern size_t __percpu_counter_tree_items_size __ro_after_init; + +/* + * percpu_counter_tree_items_size - Query the size required for counter tr= ee items. + * + * Query the size of the memory area required to hold the counter tree + * items. This depends on the hardware topology and is invariant after + * boot. + * + * Return: Size required to hold tree items. + */ +static inline +size_t percpu_counter_tree_items_size(void) +{ + WARN_ON_ONCE(__percpu_counter_tree_items_size =3D=3D SIZE_MAX); + return __percpu_counter_tree_items_size; +} + int percpu_counter_tree_init_many(struct percpu_counter_tree *counters, st= ruct percpu_counter_tree_level_item *items, unsigned int nr_counters, unsigned long batch_size, gfp_t gfp_flags); int percpu_counter_tree_init(struct percpu_counter_tree *counter, struct p= ercpu_counter_tree_level_item *items, diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c index 5c8fc2dcdc16..cfa5b04e05d7 100644 --- a/lib/percpu_counter_tree.c +++ b/lib/percpu_counter_tree.c @@ -653,22 +653,9 @@ void percpu_counter_tree_set(struct percpu_counter_tre= e *counter, long v) } EXPORT_SYMBOL_GPL(percpu_counter_tree_set); =20 -/* - * percpu_counter_tree_items_size - Query the size required for counter tr= ee items. - * - * Query the size of the memory area required to hold the counter tree - * items. This depends on the hardware topology and is invariant after - * boot. - * - * Return: Size required to hold tree items. - */ -size_t percpu_counter_tree_items_size(void) -{ - if (!nr_cpus_order) - return 0; - return counter_config->nr_items * sizeof(struct percpu_counter_tree_level= _item); -} -EXPORT_SYMBOL_GPL(percpu_counter_tree_items_size); +/* Initialize to SIZE_MAX to catch early boot misuses. */ +size_t __percpu_counter_tree_items_size __ro_after_init =3D SIZE_MAX; +EXPORT_SYMBOL_GPL(__percpu_counter_tree_items_size); =20 static void __init calculate_accuracy_topology(void) { @@ -697,6 +684,11 @@ int __init percpu_counter_tree_subsystem_init(void) return -1; } counter_config =3D &per_nr_cpu_order_config[nr_cpus_order]; + if (!nr_cpus_order) + __percpu_counter_tree_items_size =3D 0; + else + __percpu_counter_tree_items_size =3D counter_config->nr_items * + sizeof(struct percpu_counter_tree_level_item); calculate_accuracy_topology(); return 0; } --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 604E249B1E8 for ; Fri, 4 Sep 2026 16:07:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538084; cv=none; b=fdbFYaFbv6wJps9UKocf2ZaGU5TSZr6XivoeLuBv6H2/DmNhNEAXkU1DVyfsXVBFPTQ8g4Udo4JT4Er4f17JMPve3iW62NZI6BzfnLti/tVpPhTZDuAkBoCKr/u5szS7ibv7xDuGPkDGXNEgLX8yxZUbeATXAMzqYYJ4LrLShlg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538084; c=relaxed/simple; bh=vUk2Qy+wWuwkPKXrWW5oqDWUEunpPdYcZyIzmWzLvHQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=HgzxXkQHeB+em0dNxUoe9dFvs3OZ0jWw9vorCztOnCVTnab+QlpywC5wgsfkmV0cNHnMGTvMYJfCZwQKgmRLDmfI2vN86YroPhXeFHovvmNUR92Kyz99tmhLhGCj9Qqim8X/zrsg8PuSnklWmLCgNcKUteJE7AckgpjWTZZI/tc= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=u41Mh3jE; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="u41Mh3jE" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=f61pjVNcG3vfV4ruWkC/0g9a79TuVBC5x25qutrEOrw=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=u41Mh3jEJRteYmwrd/a6v5pGZjWY66A+h8ipRzrmzS3bE2DGea24bwVQTv/7LmmnP 5jdwHYRjYfuTMJTkWkcdSUiYquVshrj5KNIbsFdDpAGxIm67v3HqzwTYBOlNW5CqeT H+jDSf1VbWmEF1odRRacFujOa1TEP8CVcqMX9gLgN1/oMHHI4YVPxvIDfUQRVHZy8P 0wwbWkTGHByec34uO88Kq9m4bj6ORAL74aDmWok6qzSLF1l12ORYa54kCd5TMWDcrp CQ7xLAgUhYcjnxoCAAyV+TBGUp+KNJlfzNEf3HrW+oJuWPW+K+nyM3y5S/RHoigJTS vTrJw3/XHN9wA== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zf2MC5zXNR; Fri, 04 Sep 2026 12:07:38 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 07/10] lib/hpcc: Document that accuracy is a property of settled counters Date: Fri, 4 Sep 2026 12:07:19 -0400 Message-ID: <20260904160734.23445-8-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Answer a report from Sashiko at: https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers@eff= icios.com This change is documentation only. The bound describes a settled tree; the two-counter comparisons read their operands independently. No code change. I considered and rejected the preempt_disable() proposed by Sashiko and an alternative dual pre/post counters design. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- Documentation/core-api/percpu-counter-tree.rst | 4 ++++ include/linux/percpu_counter_tree.h | 10 +++++++--- lib/percpu_counter_tree.c | 6 ++++-- 3 files changed, 15 insertions(+), 5 deletions(-) diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation= /core-api/percpu-counter-tree.rst index 196da056e7b4..bb13e28bef11 100644 --- a/Documentation/core-api/percpu-counter-tree.rst +++ b/Documentation/core-api/percpu-counter-tree.rst @@ -43,6 +43,10 @@ This allows reading an approximated value at the root, w= hich has a bounded accuracy (minimum/maximum possible precise sum range) determined by the tree topology. =20 +The bounded accuracy is a property of the settled tree. While updates are +in flight the transient error can exceed it, bounded by the number of +updaters and their increment size. + Use Cases =3D=3D=3D=3D=3D=3D=3D=3D=3D =20 diff --git a/include/linux/percpu_counter_tree.h b/include/linux/percpu_cou= nter_tree.h index 4095acdc879b..d593806b4ab2 100644 --- a/include/linux/percpu_counter_tree.h +++ b/include/linux/percpu_counter_tree.h @@ -93,7 +93,8 @@ struct percpu_counter_tree { * The "under" accuracy is larger than the "over" accuracy because the ne= gative range of a * two's complement signed integer is one unit larger than the positive r= ange. This delta * is summed for each tree item, which leads to a significantly larger "u= nder" accuracy range - * compared to the "over" accuracy range. + * compared to the "over" accuracy range. The accuracy range is a bound o= n a settled counter: + * one with no update in progress. */ struct { unsigned long under; @@ -169,6 +170,8 @@ long percpu_counter_tree_approximate_sum(struct percpu_= counter_tree *counter) * slightly larger than the "over" range. * Those values are derived from the hardware topology and the counter tre= e batch size. * They are invariant for a given counter tree. + * The bounds describe a settled counter: one with no update in progress. + * An update in flight between its per-CPU increment and its carry propaga= tion is not covered. * Using this function should not be typically required, see the following= functions instead: * * percpu_counter_tree_approximate_compare(), * * percpu_counter_tree_approximate_compare_value(), @@ -341,8 +344,9 @@ long percpu_counter_tree_precise_sum_positive(struct pe= rcpu_counter_tree *counte * @precise_min: Minimum possible value for precise sum (output). * @precise_max: Maximum possible value for precise sum (output). * - * Calculate the minimum and maximum precise values for a given - * approximation and (under, over) accuracy range. + * Calculate the minimum and maximum precise values for a given approximat= ion + * and (under, over) accuracy range. The accuracy range is a bound on a se= ttled + * tree: one with no update in progress. * * The range of the approximation as a function of the precise sum is expr= essed as: * diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c index cfa5b04e05d7..cd71581f56bb 100644 --- a/lib/percpu_counter_tree.c +++ b/lib/percpu_counter_tree.c @@ -483,7 +483,8 @@ int compare_delta(long delta, unsigned long accuracy_ne= g, unsigned long accuracy * answer if the counters are found to be either less than or greater * than the other. However, if the approximated comparison returns * 0, the counters respective sums are found to be within the two - * counters accuracy range. + * counters accuracy range. The two counters are read independently; + * the result is not an atomic snapshot of both. * * Return: * * %0 - Counters @a and @b do not differ by more than the sum of their = respective @@ -532,7 +533,8 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compa= re_value); * As an optimization, it uses the approximate counter comparison * to quickly compare counters which are far apart. Only cases where * counter sums are within the accuracy range require precise counter - * sums. + * sums. The two counters are read independently; the result is not an + * atomic snapshot of both. * * Return: * * %0 - Counters are equal. --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 069873E49F2 for ; Fri, 4 Sep 2026 16:07:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538082; cv=none; b=Ew/ClqHUq9BUn7ut5gFVsVZk7KPDtM17Ejq3+G5rQB/Srmju/cFCUwrNFV5lWZmGtAFdEHpVeR9lVB0oCaa5TQ6bXPJJ+Cw2H7ZHzvnp697w/5eLuQCLfnK2CbiBIoi6C0pqg5XOPPv8dPmPvr/7p3UBX1cih68TW+w7a9u5khw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538082; c=relaxed/simple; bh=nhiKumAHhpO4fJrNze7+Vk7fwTr7RXwMdq+K1R7SNH8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=fgMhuRK506aB00GK+v3khDqjLGrVZHcV3RjJa6LZ7Pyuo5V4d7f0qXECsZfuJiZBt459fYTjyvY68NSIg21AD3jJl1hBSRipZEoX7o5NudeNuuuz9MO2ua+BWDBSAD33QGqQ7opINX5ULcy1Me4soPSjnapgVof+P0mdfJdgGCE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=ZtArIxs3; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="ZtArIxs3" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=lradUNjQ28/3mgjgcohJ5akUg3r+w3Kdj2J+iydSJdo=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=ZtArIxs36rzznKd2FiPR6bsMWG98lM6zzCRxyDLG0UFs6hz+gDG/jeNe3GW19Sreg HfM5ADbXr7bwXq270tGwlDUvKC3sSf0adM1lTlD3PduSl08LkU2cLfBYiHLcqJpz7S 7Ksoy6hLprKYuabeX9dOqjX3xZGKcBhI0mcQImgvwYzcqhtCqSeSIqWVZrjYmIAsJU So9KxR6oWF7scAXrAS7z51ONPjnWNpw284SGIYcTXHalDngJ0s2XiiRgMAs639pUKJ tsM/fIiZNoo2ll2Kam2AW6MvqA+gJJFggCiX/0hKpBr26Ju3rzuc0gJnP8CXGxxnfX Ur2hOcWYKlyNg== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zf3dnqzXNS; Fri, 04 Sep 2026 12:07:38 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 08/10] lib/hpcc: Clarify accuracy range documentation Date: Fri, 4 Sep 2026 12:07:20 -0400 Message-ID: <20260904160734.23445-9-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Answer a report from Sashiko at: https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers@eff= icios.com Note that both Sashiko and Claude got it wrong with respect to what was going on there. I took out pen and paper to draw the range situation, and presented the result to Claude through ascii art, which solved the matter. Having two LLMs misguided by the code, I decided to add a visual representation of the approximation ranges to compare_delta() so anyone reviewing this code won't fall into the same traps. This change is documentation only. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- lib/percpu_counter_tree.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c index cd71581f56bb..a8351c53d062 100644 --- a/lib/percpu_counter_tree.c +++ b/lib/percpu_counter_tree.c @@ -457,6 +457,32 @@ long percpu_counter_tree_precise_sum(struct percpu_cou= nter_tree *counter) } EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_sum); =20 +/* + * Each counter's approximation lies within [precise - under, precise + ov= er]: + * + * approx_a range + * <-----------+-----------> + * under_a | over_a + * precise_a + * | approx_b range + * | <-----------+-----------> + * | under_b | over_b + * | precise_b + * | | + * |<------------ gap ------------->| + * ----------------------+--------------------------------+------------->= values + * + * The two ranges are disjoint, and the comparison can return a definitive + * answer, only once the gap exceeds the two facing half-widths: + * + * a below b: gap > over_a + under_b (a's upper edge, b's lower edge) + * a above b: gap > under_a + over_b (a's lower edge, b's upper edge) + * + * When comparing against a plain value, the value has zero width, so the + * margins reduce to that single counter's under and over. + * + * accuracy_neg is used when delta < 0, and accuracy_pos is used when delt= a >=3D 0. + */ static int compare_delta(long delta, unsigned long accuracy_neg, unsigned long ac= curacy_pos) { @@ -494,6 +520,7 @@ int compare_delta(long delta, unsigned long accuracy_ne= g, unsigned long accuracy */ int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,= struct percpu_counter_tree *b) { + /* See the range geometry above compare_delta(). */ return compare_delta(percpu_counter_tree_approximate_sum(a) - percpu_coun= ter_tree_approximate_sum(b), a->approx_accuracy_range.over + b->approx_accuracy_range.under, a->approx_accuracy_range.under + b->approx_accuracy_range.over); @@ -549,6 +576,7 @@ int percpu_counter_tree_precise_compare(struct percpu_c= ounter_tree *a, struct pe long delta =3D count_a - count_b; int res; =20 + /* See the range geometry above compare_delta(). */ res =3D compare_delta(delta, a->approx_accuracy_range.over + b->approx_accuracy_range.under, a->approx_accuracy_range.under + b->approx_accuracy_range.over); --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B3E073EC683 for ; Fri, 4 Sep 2026 16:07:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538081; cv=none; b=XXjNacnSnDzeQnst8jgFWRCxsObggtCJvUCVJCkgUv1Ub/2oAu7dZnyP15lpkCoKX9ulfKJFDjiwCtlLS927pg440jVAnAuT3PorXhn2ebqjlvBTJlTOkSsEj3S5jr2rDs/r+d5tW7pYKN/Noy8xr/yo4qFpE8f8e1hn32zYgFs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538081; c=relaxed/simple; bh=baOAvP7RiN6IFCgsRNzYX4lPYV0J17aJKHFqE+wtHTU=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=MyTb0+7PqSmPLdqagQgfRNQLA5vWeqH8vJu6FxNmOo6+pI4lMkFFf5GPyPtTMgGkSbHW5qWB9b9tQurBUsuSglveJJVxdLeYazXvEYEYYixRIghm0Vet99t94nkOaE1tY/U72m0ynjk9v7j5ULgBBxtzUt6sjQDpfoRGATYYWd0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=wCfgFlTr; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="wCfgFlTr" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=GFrBGotQmUFPk7Hx6MxhQ//71RXmwImDPFS9Iw0UAsM=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=wCfgFlTrbJPjdAcgG+nlLqQIYCEOi18LXYFjG4sdjtoD9r3ycBDcKFXnBwxiB6yDm nRi+nE7vTEVoXinUKEwDsB9WQXjs3xyUsf6soQ27ieg8+U0j7NYvcq2aAuE6TlZMbd yi73XpBkuXv1qliojg9bKREXw/3UdcB2bmNKiDZA33cQ+bFnxD4R0wzgg8Xa1n741e dQ/EBC2e2YlP7Nb29YGFNQCpu1X5qbexT6KPbH5o+1OXCia+8RBvEWpJkuTE0CjtdS 1IomSsc/kAtjEavizxiiwtA9TJjL09xwGfhdoq5+/5LPeDj6KjQuQxyuwrkAomm0E5 9H0/jjaWhbosQ== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zf4svrzWWY; Fri, 04 Sep 2026 12:07:38 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 09/10] lib/hpcc: Introduce wrapped delta helper Date: Fri, 4 Sep 2026 12:07:21 -0400 Message-ID: <20260904160734.23445-10-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Answer a report from Sashiko at: https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers@eff= icios.com Document that the comparison between counters is on the wrapped difference. It is valid only when the two counters differ by less than LONG_MAX, and results are undefined beyond that. Introduce a wrapped_delta() static inline helper to perform this subtraction on unsigned types, which define the subtraction across overflow, and use it in the comparison API. I've reflowed some kdocs comments that were around the addition of new sentences about wrapped difference. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- .../core-api/percpu-counter-tree.rst | 3 + lib/percpu_counter_tree.c | 81 ++++++++++++------- 2 files changed, 55 insertions(+), 29 deletions(-) diff --git a/Documentation/core-api/percpu-counter-tree.rst b/Documentation= /core-api/percpu-counter-tree.rst index bb13e28bef11..878cbd85304c 100644 --- a/Documentation/core-api/percpu-counter-tree.rst +++ b/Documentation/core-api/percpu-counter-tree.rst @@ -72,6 +72,9 @@ a set. A first pass compares the approximated values, and= then a second pass only needs the precise sum for counter trees which are within the possible precise sum range of the counter tree chosen by the first pass. =20 +Because the comparison is on the wrapped difference, it is not transitive: +ordering is undefined over a set of counters spanning more than LONG_MAX. + Functions and structures =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 diff --git a/lib/percpu_counter_tree.c b/lib/percpu_counter_tree.c index a8351c53d062..26bfe183a882 100644 --- a/lib/percpu_counter_tree.c +++ b/lib/percpu_counter_tree.c @@ -457,6 +457,17 @@ long percpu_counter_tree_precise_sum(struct percpu_cou= nter_tree *counter) } EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_sum); =20 +/* + * The comparison between counters is on the wrapped difference. It is val= id + * only when the two counters differ by less than LONG_MAX, and results are + * undefined beyond that. + */ +static inline +long wrapped_delta(long a, long b) +{ + return (long)((unsigned long)a - (unsigned long)b); +} + /* * Each counter's approximation lies within [precise - under, precise + ov= er]: * @@ -504,13 +515,15 @@ int compare_delta(long delta, unsigned long accuracy_= neg, unsigned long accuracy * @a: First counter to compare. * @b: Second counter to compare. * - * Evaluate an approximate comparison of two counter trees. - * This approximation comparison is fast, and provides an accurate - * answer if the counters are found to be either less than or greater - * than the other. However, if the approximated comparison returns - * 0, the counters respective sums are found to be within the two - * counters accuracy range. The two counters are read independently; - * the result is not an atomic snapshot of both. + * Evaluate an approximate comparison of two counter trees. This approxima= tion + * comparison is fast, and provides an accurate answer if the counters are + * found to be either less than or greater than the other. However, if the + * approximated comparison returns 0, the counters respective sums are fou= nd to + * be within the two counters accuracy range. The two counters are read + * independently; the result is not an atomic snapshot of both. + * The comparison between counters is on the wrapped difference. It is val= id + * only when the two counters differ by less than LONG_MAX, and results are + * undefined beyond that. * * Return: * * %0 - Counters @a and @b do not differ by more than the sum of their = respective @@ -521,7 +534,8 @@ int compare_delta(long delta, unsigned long accuracy_ne= g, unsigned long accuracy int percpu_counter_tree_approximate_compare(struct percpu_counter_tree *a,= struct percpu_counter_tree *b) { /* See the range geometry above compare_delta(). */ - return compare_delta(percpu_counter_tree_approximate_sum(a) - percpu_coun= ter_tree_approximate_sum(b), + return compare_delta(wrapped_delta(percpu_counter_tree_approximate_sum(a), + percpu_counter_tree_approximate_sum(b)), a->approx_accuracy_range.over + b->approx_accuracy_range.under, a->approx_accuracy_range.under + b->approx_accuracy_range.over); } @@ -537,6 +551,9 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compa= re); * answer if the counter is found to be either less than or greater * than the value. However, if the approximated comparison returns * 0, the value is within the counter accuracy range. + * The comparison between counters is on the wrapped difference. It is val= id + * only when @v and the counter differ by less than LONG_MAX, and results = are + * undefined beyond that. * * Return: * * %0 - The value @v is within the accuracy range of the counter. @@ -545,7 +562,7 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_compa= re); */ int percpu_counter_tree_approximate_compare_value(struct percpu_counter_tr= ee *counter, long v) { - return compare_delta(v - percpu_counter_tree_approximate_sum(counter), + return compare_delta(wrapped_delta(v, percpu_counter_tree_approximate_sum= (counter)), counter->approx_accuracy_range.under, counter->approx_accuracy_range.over); } @@ -556,12 +573,14 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_approximate_com= pare_value); * @a: First counter to compare. * @b: Second counter to compare. * - * Evaluate a precise comparison of two counter trees. - * As an optimization, it uses the approximate counter comparison - * to quickly compare counters which are far apart. Only cases where - * counter sums are within the accuracy range require precise counter - * sums. The two counters are read independently; the result is not an - * atomic snapshot of both. + * Evaluate a precise comparison of two counter trees. As an optimization,= it + * uses the approximate counter comparison to quickly compare counters whi= ch + * are far apart. Only cases where counter sums are within the accuracy ra= nge + * require precise counter sums. The two counters are read independently; = the + * result is not an atomic snapshot of both. + * The comparison between counters is on the wrapped difference. It is val= id + * only when the two counters differ by less than LONG_MAX, and results are + * undefined beyond that. * * Return: * * %0 - Counters are equal. @@ -573,7 +592,7 @@ int percpu_counter_tree_precise_compare(struct percpu_c= ounter_tree *a, struct pe long count_a =3D percpu_counter_tree_approximate_sum(a), count_b =3D percpu_counter_tree_approximate_sum(b); unsigned long accuracy_a, accuracy_b; - long delta =3D count_a - count_b; + long delta =3D wrapped_delta(count_a, count_b); int res; =20 /* See the range geometry above compare_delta(). */ @@ -597,7 +616,7 @@ int percpu_counter_tree_precise_compare(struct percpu_c= ounter_tree *a, struct pe } if (accuracy_b < accuracy_a) { count_a =3D percpu_counter_tree_precise_sum(a); - res =3D compare_delta(count_a - count_b, + res =3D compare_delta(wrapped_delta(count_a, count_b), b->approx_accuracy_range.under, b->approx_accuracy_range.over); if (res) @@ -606,7 +625,7 @@ int percpu_counter_tree_precise_compare(struct percpu_c= ounter_tree *a, struct pe count_b =3D percpu_counter_tree_precise_sum(b); } else { count_b =3D percpu_counter_tree_precise_sum(b); - res =3D compare_delta(count_a - count_b, + res =3D compare_delta(wrapped_delta(count_a, count_b), a->approx_accuracy_range.over, a->approx_accuracy_range.under); if (res) @@ -614,9 +633,10 @@ int percpu_counter_tree_precise_compare(struct percpu_= counter_tree *a, struct pe /* Precise sum of second counter is required. */ count_a =3D percpu_counter_tree_precise_sum(a); } - if (count_a - count_b < 0) + delta =3D wrapped_delta(count_a, count_b); + if (delta < 0) return -1; - if (count_a - count_b > 0) + if (delta > 0) return 1; return 0; } @@ -627,11 +647,13 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare= ); * @counter: Counter to compare. * @v: Value to compare. * - * Evaluate a precise comparison of a counter tree against a given value. - * As an optimization, it uses the approximate counter comparison - * to quickly identify whether the counter and value are far apart. - * Only cases where the value is within the counter accuracy range - * require a precise counter sum. + * Evaluate a precise comparison of a counter tree against a given value. = As + * an optimization, it uses the approximate counter comparison to quickly + * identify whether the counter and value are far apart. Only cases where = the + * value is within the counter accuracy range require a precise counter su= m. + * The comparison between counters is on the wrapped difference. It is val= id + * only when @v and the counter differ by less than LONG_MAX, and results = are + * undefined beyond that. * * Return: * * %0 - The value @v is equal to the counter. @@ -640,10 +662,10 @@ EXPORT_SYMBOL_GPL(percpu_counter_tree_precise_compare= ); */ int percpu_counter_tree_precise_compare_value(struct percpu_counter_tree *= counter, long v) { - long count =3D percpu_counter_tree_approximate_sum(counter); + long count =3D percpu_counter_tree_approximate_sum(counter), delta; int res; =20 - res =3D compare_delta(v - count, + res =3D compare_delta(wrapped_delta(v, count), counter->approx_accuracy_range.under, counter->approx_accuracy_range.over); /* The values are distanced enough for an accurate approximated compariso= n. */ @@ -652,9 +674,10 @@ int percpu_counter_tree_precise_compare_value(struct p= ercpu_counter_tree *counte =20 /* Precise sum is required. */ count =3D percpu_counter_tree_precise_sum(counter); - if (v - count < 0) + delta =3D wrapped_delta(v, count); + if (delta < 0) return -1; - if (v - count > 0) + if (delta > 0) return 1; return 0; } --=20 2.43.0 From nobody Sat Sep 26 04:30:05 2026 Received: from smtpout.efficios.com (smtpout.efficios.com [158.69.130.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E55212E7393 for ; Fri, 4 Sep 2026 16:07:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=158.69.130.18 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538078; cv=none; b=cQ14vLJpLkiCMZwwZAvFRonjXRh2XvReKnHfS+U9T1bpN7tSmQ8J6atOSt+HzliwehMtH2nir/MzdFowwYpKr5xIEsO1rtRyv5ECv9Vp+JvMGfPUSAnJYImraOcVu1ZhVNeaTv97AOQZB5bV8z7y/xNwdhhPz1DroMjWiSWFa7M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1788538078; c=relaxed/simple; bh=cgrxemdbFLrv3U76zxpLCYyy9RF7SDA8yNgZEvEdO2A=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=AiLgigj6o3ZNmek14plr3AACeFdO9skrxXpYQESlnPpH0dljFWtfU6lo5JZzDF6T1esu28nFZ8SFSZt2dw0cNE5t2ycGopjw5dYkWMB8o5Rct2YISMqnxqUzWXM69kMRNDK+tvly8IofEDtV8Akr9T8ccs9LF9Lv9eafgzuH8Lk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com; spf=pass smtp.mailfrom=efficios.com; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b=vgA5TNJu; arc=none smtp.client-ip=158.69.130.18 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=efficios.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=efficios.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=efficios.com header.i=@efficios.com header.b="vgA5TNJu" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=efficios.com; s=smtpout1; t=1788538058; bh=8IFEeV8PcQPSD1vEIqV53mGLAZ2GqdJfZuwCTddGWLs=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=vgA5TNJuOiu4SR7r/Ew5GtX8A1DjTiJ+9CRRFg5I6F7yfgPrKYeVkEt4hd7jQZQ6s /TbTB5jASyMU3xtcMwmTy125/7ZCnzoCAqJcbk0ngMpc5uASkDi6mgR/JB0tABv1wV ecmwMuwBqYlkWjaG5bBGkMp/Jf3Yx8lfShZx0Dt8lTvM0/tiaQHa9gv/5rjz/tcQUu DebWTS6Tm4pASPpsSXo1710s2y6Ux82xQcruJqxPhEJKfglB7Zv1EHpnkuotf16PDD iNj2gFHkczwSA9Zix6OVbQw2mADcJKEHWauaT0hMnzHMtaQ/CKJFVOFsKllY6+4MtL v5Y5cHUegc+iA== Received: from compudjdev.. (mtl.efficios.com [216.120.195.104]) by smtpout.efficios.com (Postfix) with ESMTPSA id 4hc1Zf64N1zWWZ; Fri, 04 Sep 2026 12:07:38 -0400 (EDT) From: Mathieu Desnoyers To: Andrew Morton Cc: linux-kernel@vger.kernel.org, Mathieu Desnoyers , "Paul E. McKenney" , Steven Rostedt , Masami Hiramatsu , Dennis Zhou , Tejun Heo , Christoph Lameter , Martin Liu , David Rientjes , christian.koenig@amd.com, Shakeel Butt , SeongJae Park , Michal Hocko , Johannes Weiner , Sweet Tea Dorminy , Lorenzo Stoakes , "Liam R . Howlett" , Mike Rapoport , Suren Baghdasaryan , Vlastimil Babka , Christian Brauner , Wei Yang , David Hildenbrand , Miaohe Lin , Al Viro , Yu Zhao , Roman Gushchin , Mateusz Guzik , Matthew Wilcox , Baolin Wang , Aboorva Devarajan , David Carlier , Josh Law , linux-mm@kvack.org Subject: [PATCH v22 10/10] lib/tests/hpcc: Fix hotplug, module unload, and error handling Date: Fri, 4 Sep 2026 12:07:22 -0400 Message-ID: <20260904160734.23445-11-mathieu.desnoyers@efficios.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> References: <20260904160734.23445-1-mathieu.desnoyers@efficios.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Answer a report from Sashiko at: https://sashiko.dev/#/patchset/20260901182857.26690-1-mathieu.desnoyers@eff= icios.com Those were good catches. Following them up surfaced more than the report contained: ERR_PTR handling, a td leak, hotplug locking, allocation sizing, the cpu & ~1 skip, and a lost-worker bug where kthread_stop() could preempt the threadfn before it ran, plus a task_struct reaping race that only shows up at 1000 workers. Plainly following Sashiko's advice to move to kthread_stop() did not work: the thread running the worker needed a task struct reference, a completion to ensure the work was actually done, in addition to the kthread_stop. The kthread_stop only ensure that the thread is really done before module unload, without guaranteeing that the kthread has actually done its work. Signed-off-by: Mathieu Desnoyers Cc: "Paul E. McKenney" Cc: Steven Rostedt Cc: Masami Hiramatsu Cc: Dennis Zhou Cc: Tejun Heo Cc: Christoph Lameter Cc: Martin Liu Cc: David Rientjes Cc: christian.koenig@amd.com Cc: Shakeel Butt Cc: SeongJae Park Cc: Michal Hocko Cc: Johannes Weiner Cc: Sweet Tea Dorminy Cc: Lorenzo Stoakes Cc: Liam R. Howlett Cc: Mike Rapoport Cc: Suren Baghdasaryan Cc: Vlastimil Babka Cc: Christian Brauner Cc: Wei Yang Cc: David Hildenbrand Cc: Miaohe Lin Cc: Al Viro Cc: Yu Zhao Cc: Roman Gushchin Cc: Mateusz Guzik Cc: Matthew Wilcox Cc: Baolin Wang Cc: Aboorva Devarajan Cc: David Carlier Cc: Josh Law Cc: Andrew Morton Cc: linux-mm@kvack.org --- lib/tests/percpu_counter_tree_kunit.c | 280 +++++++++++++++++++++----- 1 file changed, 232 insertions(+), 48 deletions(-) diff --git a/lib/tests/percpu_counter_tree_kunit.c b/lib/tests/percpu_count= er_tree_kunit.c index a79176655c4b..8af8d2659b57 100644 --- a/lib/tests/percpu_counter_tree_kunit.c +++ b/lib/tests/percpu_counter_tree_kunit.c @@ -6,10 +6,13 @@ #include #include #include +#include +#include +#include =20 struct multi_thread_test_data { long increment; - int nr_inc; + unsigned int nr_inc; int counter_index; }; =20 @@ -31,6 +34,9 @@ static void complete_work(void) wake_up(&kernel_threads_wq); } =20 +/* Random tasks test. */ +#define NR_RAND_TASKS 1000 + static void hpcc_print_info(struct kunit *test) { kunit_info(test, "Running test with %d CPUs\n", num_online_cpus()); @@ -67,18 +73,19 @@ static void check_counters(struct kunit *test) /* Accuracy limits checks. */ percpu_counter_tree_approximate_accuracy_range(&counter[counter_index], = &under_accuracy, &over_accuracy); =20 + /* + * under_accuracy and over_accuracy are unsigned long, so the + * inner expression promotes to unsigned. Compute the difference + * in unsigned and cast to signed for the comparison against 0. + */ KUNIT_EXPECT_GE(test, (long)(approx_sum - (v - under_accuracy)), 0); KUNIT_EXPECT_LE(test, (long)(approx_sum - (v + over_accuracy)), 0); - KUNIT_EXPECT_GT(test, (long)(approx_sum - (v - under_accuracy - 1)), 0); - KUNIT_EXPECT_LT(test, (long)(approx_sum - (v + over_accuracy + 1)), 0); =20 /* Precise min/max range check. */ percpu_counter_tree_approximate_min_max_range(approx_sum, under_accuracy= , over_accuracy, &precise_min, &precise_max); =20 KUNIT_EXPECT_GE(test, v - precise_min, 0); KUNIT_EXPECT_LE(test, v - precise_max, 0); - KUNIT_EXPECT_GT(test, v - (precise_min - 1), 0); - KUNIT_EXPECT_LT(test, v - (precise_max + 1), 0); } /* Compare each counter with the second counter. */ KUNIT_EXPECT_EQ(test, percpu_counter_tree_precise_sum(&counter[0]), percp= u_counter_tree_precise_sum(&counter[1])); @@ -96,18 +103,26 @@ static int multi_thread_worker_fn(void *data) return 0; } =20 -static void test_run_on_specific_cpu(struct kunit *test, int target_cpu, i= nt counter_index, unsigned int nr_inc, long increment) +static struct task_struct *test_run_on_specific_cpu(int target_cpu, int co= unter_index, unsigned int nr_inc, long increment) { - struct task_struct *task; struct multi_thread_test_data *td =3D kzalloc(sizeof(struct multi_thread_= test_data), GFP_KERNEL); + struct task_struct *task; =20 - KUNIT_EXPECT_PTR_NE(test, td, NULL); + if (!td) + return NULL; td->increment =3D increment; td->nr_inc =3D nr_inc; td->counter_index =3D counter_index; atomic_inc(&kernel_threads_to_run); - task =3D kthread_run_on_cpu(multi_thread_worker_fn, td, target_cpu, "kuni= t_multi_thread_worker"); - KUNIT_ASSERT_NOT_ERR_OR_NULL(test, task); + task =3D kthread_create_on_cpu(multi_thread_worker_fn, td, target_cpu, "k= unit_multi_thread_worker"); + if (IS_ERR_OR_NULL(task)) { + complete_work(); + kfree(td); + return task; + } + get_task_struct(task); + wake_up_process(task); + return task; } =20 static void init_kthreads(void) @@ -115,6 +130,9 @@ static void init_kthreads(void) atomic_set(&kernel_threads_to_run, 1); } =20 +/* + * The caller needs to wait for work completion _before_ stopping kthreads. + */ static void fini_kthreads(void) { /* Release our own reference. */ @@ -129,23 +147,27 @@ static void test_sync_kthreads(void) init_kthreads(); } =20 -static void init_counters(struct kunit *test, unsigned long batch_size) +static int init_counters(unsigned long batch_size) { int i, ret; =20 - items =3D kzalloc(percpu_counter_tree_items_size() * NR_COUNTERS, GFP_KER= NEL); - KUNIT_EXPECT_PTR_NE(test, items, NULL); + items =3D kvcalloc(NR_COUNTERS, percpu_counter_tree_items_size(), GFP_KER= NEL); + if (!items) + return -ENOMEM; ret =3D percpu_counter_tree_init_many(counter, items, NR_COUNTERS, batch_= size, GFP_KERNEL); - KUNIT_EXPECT_EQ(test, ret, 0); - + if (ret) { + kvfree(items); + return ret; + } for (i =3D 0; i < NR_COUNTERS; i++) atomic_long_set(&global_counter[i], 0); + return 0; } =20 static void fini_counters(void) { percpu_counter_tree_destroy_many(counter, NR_COUNTERS); - kfree(items); + kvfree(items); } =20 enum up_test_inc_type { @@ -164,11 +186,16 @@ static void do_hpcc_test_single_thread(struct kunit *= test, int _cpu0, int _cpu1, unsigned long batch_size_order =3D 5; int cpu0 =3D _cpu0; int cpu1 =3D _cpu1; - int i; + int ret, i; =20 - init_counters(test, 1UL << batch_size_order); + ret =3D init_counters(1UL << batch_size_order); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + return; init_kthreads(); + cpus_read_lock(); for (i =3D 0; i < 10000; i++) { + struct task_struct *task; long increment; =20 switch (type) { @@ -181,18 +208,34 @@ static void do_hpcc_test_single_thread(struct kunit *= test, int _cpu0, int _cpu1, case INC_RANDOM: increment =3D (long) get_random_long() % 50000; break; + default: + WARN_ON_ONCE(1); + increment =3D 0; } if (_cpu0 < 0) cpu0 =3D cpumask_any_distribute(cpu_online_mask); if (_cpu1 < 0) cpu1 =3D cpumask_any_distribute(cpu_online_mask); - test_run_on_specific_cpu(test, cpu0, 0, 1, increment); + task =3D test_run_on_specific_cpu(cpu0, 0, 1, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task); + if (IS_ERR_OR_NULL(task)) { + fini_kthreads(); + goto end; + } test_sync_kthreads(); - test_run_on_specific_cpu(test, cpu1, 1, 1, increment); + kthread_stop_put(task); + task =3D test_run_on_specific_cpu(cpu1, 1, 1, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task); + if (IS_ERR_OR_NULL(task)) { + fini_kthreads(); + goto end; + } test_sync_kthreads(); + kthread_stop_put(task); check_counters(test); } - fini_kthreads(); +end: + cpus_read_unlock(); fini_counters(); } =20 @@ -225,62 +268,168 @@ static void hpcc_test_single_thread_random(struct ku= nit *test) =20 static void do_hpcc_multi_thread_increment_each_cpu(struct kunit *test, un= signed long batch_size, unsigned int nr_inc, long increment) { - int cpu; - - init_counters(test, batch_size); + struct task_struct *(*task)[NR_COUNTERS]; + int ret, cpu; + + task =3D kvcalloc(nr_cpu_ids, sizeof(*task), GFP_KERNEL); + KUNIT_EXPECT_NOT_NULL(test, task); + if (!task) + return; + ret =3D init_counters(batch_size); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; init_kthreads(); + cpus_read_lock(); for_each_online_cpu(cpu) { - test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); - test_run_on_specific_cpu(test, cpu, 1, nr_inc, increment); + task[cpu][0] =3D test_run_on_specific_cpu(cpu, 0, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][0]); + if (IS_ERR_OR_NULL(task[cpu][0])) + break; + task[cpu][1] =3D test_run_on_specific_cpu(cpu, 1, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][1]); + if (IS_ERR_OR_NULL(task[cpu][1])) + break; } fini_kthreads(); + for_each_online_cpu(cpu) { + if (!IS_ERR_OR_NULL(task[cpu][0])) + kthread_stop_put(task[cpu][0]); + if (!IS_ERR_OR_NULL(task[cpu][1])) + kthread_stop_put(task[cpu][1]); + } + cpus_read_unlock(); check_counters(test); fini_counters(); +end: + kvfree(task); } =20 static void do_hpcc_multi_thread_increment_even_cpus(struct kunit *test, u= nsigned long batch_size, unsigned int nr_inc, long increment) { - int cpu; - - init_counters(test, batch_size); + struct task_struct *(*task)[NR_COUNTERS]; + int ret, cpu; + + task =3D kvcalloc(nr_cpu_ids, sizeof(*task), GFP_KERNEL); + KUNIT_EXPECT_NOT_NULL(test, task); + if (!task) + return; + ret =3D init_counters(batch_size); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; init_kthreads(); + cpus_read_lock(); for_each_online_cpu(cpu) { - test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); - test_run_on_specific_cpu(test, cpu & ~1, 1, nr_inc, increment); /* even = cpus. */ + /* + * Funnel pairs of CPU indexes to their associated even index. + * + * Map 0 and 1 -> index 0 + * Map 2 and 3 -> index 2 and so on. + */ + int even_cpu =3D cpu & ~1; + + if (!cpumask_test_cpu(even_cpu, cpu_online_mask)) + continue; + task[cpu][0] =3D test_run_on_specific_cpu(cpu, 0, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][0]); + if (IS_ERR_OR_NULL(task[cpu][0])) + break; + task[cpu][1] =3D test_run_on_specific_cpu(even_cpu, 1, nr_inc, increment= ); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][1]); + if (IS_ERR_OR_NULL(task[cpu][1])) + break; } fini_kthreads(); + for_each_online_cpu(cpu) { + if (!IS_ERR_OR_NULL(task[cpu][0])) + kthread_stop_put(task[cpu][0]); + if (!IS_ERR_OR_NULL(task[cpu][1])) + kthread_stop_put(task[cpu][1]); + } + cpus_read_unlock(); check_counters(test); fini_counters(); +end: + kvfree(task); } =20 static void do_hpcc_multi_thread_increment_single_cpu(struct kunit *test, = unsigned long batch_size, unsigned int nr_inc, long increment) { - int cpu; - - init_counters(test, batch_size); + struct task_struct *(*task)[NR_COUNTERS]; + int ret, cpu; + + task =3D kvcalloc(nr_cpu_ids, sizeof(*task), GFP_KERNEL); + KUNIT_EXPECT_NOT_NULL(test, task); + if (!task) + return; + ret =3D init_counters(batch_size); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; init_kthreads(); + cpus_read_lock(); for_each_online_cpu(cpu) { - test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); - test_run_on_specific_cpu(test, cpumask_first(cpu_online_mask), 1, nr_inc= , increment); + task[cpu][0] =3D test_run_on_specific_cpu(cpu, 0, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][0]); + if (IS_ERR_OR_NULL(task[cpu][0])) + break; + task[cpu][1] =3D test_run_on_specific_cpu(cpumask_first(cpu_online_mask)= , 1, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][1]); + if (IS_ERR_OR_NULL(task[cpu][1])) + break; } fini_kthreads(); + for_each_online_cpu(cpu) { + if (!IS_ERR_OR_NULL(task[cpu][0])) + kthread_stop_put(task[cpu][0]); + if (!IS_ERR_OR_NULL(task[cpu][1])) + kthread_stop_put(task[cpu][1]); + } + cpus_read_unlock(); check_counters(test); fini_counters(); +end: + kvfree(task); } =20 static void do_hpcc_multi_thread_increment_random_cpu(struct kunit *test, = unsigned long batch_size, unsigned int nr_inc, long increment) { - int cpu; - - init_counters(test, batch_size); + struct task_struct *(*task)[NR_COUNTERS]; + int ret, cpu; + + task =3D kvcalloc(nr_cpu_ids, sizeof(*task), GFP_KERNEL); + KUNIT_EXPECT_NOT_NULL(test, task); + if (!task) + return; + ret =3D init_counters(batch_size); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; init_kthreads(); + cpus_read_lock(); for_each_online_cpu(cpu) { - test_run_on_specific_cpu(test, cpu, 0, nr_inc, increment); - test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask), = 1, nr_inc, increment); + task[cpu][0] =3D test_run_on_specific_cpu(cpu, 0, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][0]); + if (IS_ERR_OR_NULL(task[cpu][0])) + break; + task[cpu][1] =3D test_run_on_specific_cpu(cpumask_any_distribute(cpu_onl= ine_mask), 1, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[cpu][1]); + if (IS_ERR_OR_NULL(task[cpu][1])) + break; } fini_kthreads(); + for_each_online_cpu(cpu) { + if (!IS_ERR_OR_NULL(task[cpu][0])) + kthread_stop_put(task[cpu][0]); + if (!IS_ERR_OR_NULL(task[cpu][1])) + kthread_stop_put(task[cpu][1]); + } + cpus_read_unlock(); check_counters(test); fini_counters(); +end: + kvfree(task); } =20 static void hpcc_test_multi_thread_batch_increment(struct kunit *test) @@ -305,25 +454,50 @@ static void hpcc_test_multi_thread_batch_increment(st= ruct kunit *test) =20 static void hpcc_test_multi_thread_random_walk(struct kunit *test) { + struct task_struct *(*task)[NR_COUNTERS]; unsigned long batch_size_order =3D 5; int loop; =20 + task =3D kvcalloc(NR_RAND_TASKS, sizeof(*task), GFP_KERNEL); + KUNIT_EXPECT_NOT_NULL(test, task); + if (!task) + return; for (loop =3D 0; loop < 100; loop++) { - int i; + int ret, i; =20 - init_counters(test, 1UL << batch_size_order); + memset(task, 0, NR_RAND_TASKS * sizeof(*task)); + ret =3D init_counters(1UL << batch_size_order); + KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; init_kthreads(); - for (i =3D 0; i < 1000; i++) { + cpus_read_lock(); + for (i =3D 0; i < NR_RAND_TASKS; i++) { long increment =3D (long) get_random_long() % 512; unsigned int nr_inc =3D ((unsigned long) get_random_long()) % 1024; =20 - test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask),= 0, nr_inc, increment); - test_run_on_specific_cpu(test, cpumask_any_distribute(cpu_online_mask),= 1, nr_inc, increment); + task[i][0] =3D test_run_on_specific_cpu(cpumask_any_distribute(cpu_onli= ne_mask), 0, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[i][0]); + if (IS_ERR_OR_NULL(task[i][0])) + break; + task[i][1] =3D test_run_on_specific_cpu(cpumask_any_distribute(cpu_onli= ne_mask), 1, nr_inc, increment); + KUNIT_EXPECT_NOT_ERR_OR_NULL(test, task[i][1]); + if (IS_ERR_OR_NULL(task[i][1])) + break; } fini_kthreads(); + for (i =3D 0; i < NR_RAND_TASKS; i++) { + if (!IS_ERR_OR_NULL(task[i][0])) + kthread_stop_put(task[i][0]); + if (!IS_ERR_OR_NULL(task[i][1])) + kthread_stop_put(task[i][1]); + } + cpus_read_unlock(); check_counters(test); fini_counters(); } +end: + kvfree(task); } =20 static void hpcc_test_init_one(struct kunit *test) @@ -333,11 +507,16 @@ static void hpcc_test_init_one(struct kunit *test) int ret; =20 counter_items =3D kzalloc(percpu_counter_tree_items_size(), GFP_KERNEL); - KUNIT_EXPECT_PTR_NE(test, counter_items, NULL); + KUNIT_EXPECT_NOT_NULL(test, counter_items); + if (!counter_items) + return; ret =3D percpu_counter_tree_init(&pct, counter_items, 32, GFP_KERNEL); KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; =20 percpu_counter_tree_destroy(&pct); +end: kfree(counter_items); } =20 @@ -352,9 +531,13 @@ static void hpcc_test_set(struct kunit *test) int i, ret; =20 counter_items =3D kzalloc(percpu_counter_tree_items_size(), GFP_KERNEL); - KUNIT_EXPECT_PTR_NE(test, counter_items, NULL); + KUNIT_EXPECT_NOT_NULL(test, counter_items); + if (!counter_items) + return; ret =3D percpu_counter_tree_init(&pct, counter_items, 32, GFP_KERNEL); KUNIT_EXPECT_EQ(test, ret, 0); + if (ret) + goto end; =20 for (i =3D 0; i < ARRAY_SIZE(values); i++) { long v =3D values[i]; @@ -373,6 +556,7 @@ static void hpcc_test_set(struct kunit *test) } =20 percpu_counter_tree_destroy(&pct); +end: kfree(counter_items); } =20 --=20 2.43.0