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

["Leizhen (ThunderTown)" <thunder.leizhen@huawei.com>]

On 2024/9/5 11:11, Leizhen (ThunderTown) wrote:
> 
> 
> 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).

Should be:
==> (1/2)^((256+16^ncpus)/17) * 5% * 2/17 < 9e-8 (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

Should be:
==> (1/3)^((256+16^ncpus)/17) * (5%^2) * 3/17 < 1.03e-11 (ncpus=1).

> 1/3 ==> denominator sequence: 0,1,2; numerator sequence: 2
> 3/17 ==> denominator sequence: 0-16; numerator sequence: 0,1,2

Hi, Thomas Gleixner:
  Seems to need to add an additional patch as follows to be foolproof.
I'll prepare it.

diff --git a/lib/debugobjects.c b/lib/debugobjects.c
index e175cc74f7b7899..d3f8cc7dc1c9291 100644
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -245,6 +245,21 @@ alloc_object(void *addr, struct debug_bucket *b, const struct debug_obj_descr *d

        raw_spin_lock(&pool_lock);
        obj = __alloc_object(&obj_pool);
+       if (!obj) {
+               raw_spin_unlock(&pool_lock);
+               obj = kmem_cache_zalloc(obj_cache, __GFP_HIGH | GFP_NOWAIT);
+               if (!obj)
+                       return NULL;
+
+               raw_spin_lock(&pool_lock);
+               debug_objects_allocated++;
+
+               /*
+                * It can be understood that obj is allocated immediately after
+                * being added to obj_pool.
+                */
+               obj_pool_used++;
+       }
        if (obj) {
                int cnt = 0;



> 
>> 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@huawei.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