linux-kernel - Re: [PATCH v2 4/6] debugobjects: Don't start fill if there are remaining nodes locally

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

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

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

Message-ID: <336109d9-2eea-4d67-ee22-ed218b9504c3@huawei.com>
Date: Thu, 5 Sep 2024 11:11:46 +0800
From: "Leizhen (ThunderTown)" <thunder.leizhen@...wei.com>
To: Andrew Morton <akpm@...ux-foundation.org>, Thomas Gleixner
	<tglx@...utronix.de>, <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH v2 4/6] debugobjects: Don't start fill if there are
 remaining nodes locally



On 2024/9/4 21:39, Zhen Lei wrote:
> If the conditions for starting fill are met, it means that all cores that
> call fill() later are blocked until the first core completes the fill
> operation. But obviously, for a core that has free nodes locally, it does
> not need to be blocked(see below for why). This is good in stress
> situations.
> 
> 1. In the case of no nesting, a core uses only one node at a time. As long
>    as there is a local node, there is no need to use the free node in
>    obj_pool.
> 2. In the case of nesting depth is one, nodes in obj_pool need to be used
>    only when there is only one local node.
>    #define ODEBUG_POOL_PERCPU_SIZE      64
>    #define ODEBUG_BATCH_SIZE            16
>    Assume that when nested, the probability of percpu_obj_pool having each
>    number of nodes is the same. The probability of only one node is less
>    than 1/17=6%. Assuming the probability of nesting is 5%, that's a
>    pretty high estimate. Then the probability of using obj_pool is
>    6% * 5% = 0.3%. In other words, a 333-core environment produces only
>    one core to compete for obj_pool.
>    #define ODEBUG_POOL_MIN_LEVEL        256
>    #define ODEBUG_BATCH_SIZE            16
>    But we can tolerate "256 / (16 + 1)" = 15 cores competing at the same
>    time.

One detail is omitted. In function debug_objects_mem_init(), an extra batch
is reserved for each core.
	extras = num_possible_cpus() * ODEBUG_BATCH_SIZE;
	debug_objects_pool_min_level += extras;

In addition, above method of calculating probabilities is wrong. The correct
calculation method is as follows:
When the number of local nodes is 0, fill is performed. When the number of
local nodes is 1 and nested, 16 nodes are moved from obj_pool to obj_pool.
As a result, the obj_pool resource pool keeps decreasing. When this happens
continuously(The number of local nodes equal 0 is not met), the resource
pool will eventually be exhausted. The error probability is:
(1/2)^((256+16^ncpus)/17) * (5% + 5%^2 + ... + 5%^N) * 2/17 < 1e-7 (ncpus=1).
1/2 ==> denominator sequence: 0,1; numerator sequence: 1
(5% + 5%^2 + ... + 5%^N) < 5% + (5%^2) * 2 = 0.055
17 = ODEBUG_BATCH_SIZ + 1, amount moved from obj_pool when the number of local nodes is 0.
2/17 ==> denominator sequence: 0-16; numerator sequence: 0,1
The more cores, the lower the probability of exhaustion.

If obj_pool is not filled only when there are more than two local nodes,
the probability of exhaustion is:
(1/3)^((256+16^ncpus)/17) * (5% + 5%^2 + ... + 5%^N) * 3/17 < 2.3e-10
1/3 ==> denominator sequence: 0,1,2; numerator sequence: 2
3/17 ==> denominator sequence: 0-16; numerator sequence: 0,1,2

> 3. In the case of nesting depth more than one, the probability is lower
>    and negligible.
>    Nesting Depth=2: "2/17 * 5% * 5%" = 0.03%
>    Nesting Depth=3: "3/17 * 5% * 5% * 5%" = 0.002%
> 
> However, to ensure sufficient reliability, obj_pool is not filled only
> when there are more than two local nodes, reduce the probability of
> problems to the impossible.
> 
> Signed-off-by: Zhen Lei <thunder.leizhen@...wei.com>
> ---
>  lib/debugobjects.c | 10 ++++++++++
>  1 file changed, 10 insertions(+)
> 
> diff --git a/lib/debugobjects.c b/lib/debugobjects.c
> index 7a8ccc94cb037ba..4f64b5d4329c27d 100644
> --- a/lib/debugobjects.c
> +++ b/lib/debugobjects.c
> @@ -131,6 +131,16 @@ static void fill_pool(void)
>  	struct debug_obj *obj;
>  	unsigned long flags;
>  
> +	/*
> +	 * The upper-layer function uses only one node at a time. If there are
> +	 * more than two local nodes, it means that even if nesting occurs, it
> +	 * doesn't matter. The probability of nesting depth >= 2 is extremely
> +	 * low, and the number of global free nodes guarded by
> +	 * debug_objects_pool_min_level is adequate.
> +	 */
> +	if (likely(obj_cache) && this_cpu_read(percpu_obj_pool.obj_free) >= 2)
> +		return;
> +
>  	if (likely(READ_ONCE(obj_pool_free) >= debug_objects_pool_min_level))
>  		return;
>  
> 

-- 
Regards,
  Zhen Lei