Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Thomas Gleixner]

On Wed, Sep 11 2024 at 10:54, Thomas Gleixner wrote:
> On Wed, Sep 11 2024 at 15:44, Leizhen wrote:
>> 2. Member tot_cnt of struct global_pool can be deleted. We can get it
>>simply and quickly through (slot_idx * ODEBUG_BATCH_SIZE). Avoid
>>redundant maintenance.
>
> Agreed.
>
>> 3. debug_objects_pool_min_level also needs to be adjusted accordingly,
>>the number of batches of the min level.
>
> Sure. There are certainly more problems with that code. As I said, it's
> untested and way to big to be reviewed. I'll split it up into more
> manageable bits and pieces.

I finally found some time and ended up doing it differently. I'll send
out the patches later today.

Thanks,

tglx

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Leizhen (ThunderTown)]

On 2024/9/11 16:54, Thomas Gleixner wrote:
> On Wed, Sep 11 2024 at 15:44, Leizhen wrote:
>> On 2024/9/10 19:44, Thomas Gleixner wrote:
>>> That minimizes the pool lock contention and the cache foot print. The
>>> global to free pool must have an extra twist to accomodate non-batch
>>> sized drops and to handle the all slots are full case, but that's just a
>>> trivial detail.
>>
>> That's great. I really admire you for completing the refactor in such a
>> short of time.
> 
> The trick is to look at it from the data model and not from the
> code. You need to sit down and think about which data model is required
> to achieve what you want. So the goal was batching, right?

Yes, when I found a hole in the road, I thought about how to fill it. But
you think more deeply, why is there a pit, is there a problem with the
foundation? I've benefited a lot from communicating with you these days.

> 
> That made it clear that the global pools need to be stacks of batches
> and never handle single objects because that makes it complex. As a
> consequence the per cpu pool is the one which does single object
> alloc/free and then either gets a full batch from the global pool or
> drops one into it. The rest is just mechanical.
> 
>> But I have a few minor comments.
>> 1. When kmem_cache_zalloc() is called to allocate objs for filling,
>>if less than one batch of objs are allocated, all of them can be
>>pushed to the local CPU. That's, call pcpu_free() one by one.
> 
> If that's the case then we should actually immediately give them back
> because thats a sign of memory pressure.

Yes, that makes sense, and that's a solution too.

> 
>> 2. Member tot_cnt of struct global_pool can be deleted. We can get it
>>simply and quickly through (slot_idx * ODEBUG_BATCH_SIZE). Avoid
>>redundant maintenance.
> 
> Agreed.
> 
>> 3. debug_objects_pool_min_level also needs to be adjusted accordingly,
>>the number of batches of the min level.
> 
> Sure. There are certainly more problems with that code. As I said, it's
> untested and way to big to be reviewed. I'll split it up into more
> manageable bits and pieces.

Looking forward to...

> 
> Thanks,
> 
> tglx
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Thomas Gleixner]

On Wed, Sep 11 2024 at 15:44, Leizhen wrote:
> On 2024/9/10 19:44, Thomas Gleixner wrote:
>> That minimizes the pool lock contention and the cache foot print. The
>> global to free pool must have an extra twist to accomodate non-batch
>> sized drops and to handle the all slots are full case, but that's just a
>> trivial detail.
>
> That's great. I really admire you for completing the refactor in such a
> short of time.

The trick is to look at it from the data model and not from the
code. You need to sit down and think about which data model is required
to achieve what you want. So the goal was batching, right?

That made it clear that the global pools need to be stacks of batches
and never handle single objects because that makes it complex. As a
consequence the per cpu pool is the one which does single object
alloc/free and then either gets a full batch from the global pool or
drops one into it. The rest is just mechanical.

> But I have a few minor comments.
> 1. When kmem_cache_zalloc() is called to allocate objs for filling,
>if less than one batch of objs are allocated, all of them can be
>pushed to the local CPU. That's, call pcpu_free() one by one.

If that's the case then we should actually immediately give them back
because thats a sign of memory pressure.

> 2. Member tot_cnt of struct global_pool can be deleted. We can get it
>simply and quickly through (slot_idx * ODEBUG_BATCH_SIZE). Avoid
>redundant maintenance.

Agreed.

> 3. debug_objects_pool_min_level also needs to be adjusted accordingly,
>the number of batches of the min level.

Sure. There are certainly more problems with that code. As I said, it's
untested and way to big to be reviewed. I'll split it up into more
manageable bits and pieces.

Thanks,

tglx

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Leizhen (ThunderTown)]

On 2024/9/10 19:44, Thomas Gleixner wrote:
> On Tue, Sep 10 2024 at 12:00, Leizhen wrote:
>> On 2024/9/10 2:41, Thomas Gleixner wrote:
>>> All related functions have this problem and all of this code is very
>>> strict about boundaries. Instead of accurately doing the refill, purge
>>> etc. we should look into proper batch mode mechanisms. Let me think
>>> about it.
>> It may be helpful to add several arrays to record the first node of each 
>> batch
>> in each free list. Take 'percpu_pool' as an example:
>>
>> struct debug_percpu_free {
>>  struct hlist_head   free_objs;
>>  int obj_free;
>> +int batch_idx;
>> +struct hlist_node   *batch_first[4]; // ODEBUG_POOL_PERCPU_SIZE / 
>> ODEBUG_BATCH_SIZE
>> };
>>
>> A new free node is added to the header of the list, and the batch is cut 
>> from the tail
>> of the list.
>>   NodeA<-->...<-->NodeB<-->...<-->NodeC<-->NodeD<--> free_objs
>> |---one batch---|---one batch---|
>> |   |
>> batch_first[0]  batch_first[1]
> The current data structures are not fit for the purpose. Glueing
> workarounds into the existing mess makes it just worse.
> 
> So the data structures need to be redesigned from ground up to be fit
> for the purpose.
> 
> allocation:
> 
>1) Using the global pool for single object allocations is wrong
> 
>   During boot this can be a completely disconnected list, which does
>   not need any accounting, does not need pool_lock and can be just
>   protected with irqsave like the per CPU pools. It's effectivly a
>   per CPU pool because at that point there is only one CPU and
>   everything is single threaded.
> 
>2) The per CPU pool handling is backwards
> 
>   If the per CPU pool is empty, then the pool needs to be refilled
>   with a batch from the global pool and allocated from there.
> 
>   Allocation then always happens from the active per CPU batch slot.
> 
> free:
> 
>1) Early boot
> 
>   Just put it back on the dedicated boot list and be done
> 
>2) After obj_cache is initialized
> 
>   Put it back to the per CPU pool into the active batch slot.  If
>   the slot becomes full then make the next slot the active slot. It
>   the full slot was the top most slot then move that slot either
>   into the global pool when there is a free slot, or move it to the
>   to_free pool.
> 
> That means the per CPU pool is different from the global pools as it can
> allocate/free single objects, while the global pools are strictly stacks
> of batches. Any movement between per CPU pools and global pools is batch
> based and just moves lists from one head to another.
> 
> That minimizes the pool lock contention and the cache foot print. The
> global to free pool must have an extra twist to accomodate non-batch
> sized drops and to handle the all slots are full case, but that's just a
> trivial detail.

That's great. I really admire you for completing the refactor in such a
short of time. But I have a few minor comments.
1. When kmem_cache_zalloc() is called to allocate objs for filling,
   if less than one batch of objs are allocated, all of them can be
   pushed to the local CPU. That's, call pcpu_free() one by one.
   In this way, the number of free objs cached by pool_global and
   pool_to_free is always an integer multiple of ODEBUG_BATCH_SIZE.
2. Member tot_cnt of struct global_pool can be deleted. We can get it
   simply and quickly through (slot_idx * ODEBUG_BATCH_SIZE). Avoid
   redundant maintenance.
3. debug_objects_pool_min_level also needs to be adjusted accordingly,
   the number of batches of the min level.

> 
> See the completely untested combo patch against tip core/debugobjects
> below.
> 
> Thanks,
> 
> tglx

-- 
Regards,
  Zhen Lei

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Thomas Gleixner]

On Tue, Sep 10 2024 at 12:00, Leizhen wrote:
> On 2024/9/10 2:41, Thomas Gleixner wrote:
>> All related functions have this problem and all of this code is very
>> strict about boundaries. Instead of accurately doing the refill, purge
>> etc. we should look into proper batch mode mechanisms. Let me think
>> about it.
>
> It may be helpful to add several arrays to record the first node of each batch
> in each free list. Take 'percpu_pool' as an example:
>
> struct debug_percpu_free {
>   struct hlist_head   free_objs;
>   int obj_free;
> + int batch_idx;
> + struct hlist_node   *batch_first[4]; // ODEBUG_POOL_PERCPU_SIZE / 
> ODEBUG_BATCH_SIZE
> };
>
> A new free node is added to the header of the list, and the batch is cut from 
> the tail
> of the list.
>   NodeA<-->...<-->NodeB<-->...<-->NodeC<-->NodeD<--> free_objs
> |---one batch---|---one batch---|
> |   |
> batch_first[0]  batch_first[1]

The current data structures are not fit for the purpose. Glueing
workarounds into the existing mess makes it just worse.

So the data structures need to be redesigned from ground up to be fit
for the purpose.

allocation:

   1) Using the global pool for single object allocations is wrong

  During boot this can be a completely disconnected list, which does
  not need any accounting, does not need pool_lock and can be just
  protected with irqsave like the per CPU pools. It's effectivly a
  per CPU pool because at that point there is only one CPU and
  everything is single threaded.

   2) The per CPU pool handling is backwards

  If the per CPU pool is empty, then the pool needs to be refilled
  with a batch from the global pool and allocated from there.

  Allocation then always happens from the active per CPU batch slot.

free:

   1) Early boot

  Just put it back on the dedicated boot list and be done

   2) After obj_cache is initialized

  Put it back to the per CPU pool into the active batch slot.  If
  the slot becomes full then make the next slot the active slot. It
  the full slot was the top most slot then move that slot either
  into the global pool when there is a free slot, or move it to the
  to_free pool.

That means the per CPU pool is different from the global pools as it can
allocate/free single objects, while the global pools are strictly stacks
of batches. Any movement between per CPU pools and global pools is batch
based and just moves lists from one head to another.

That minimizes the pool lock contention and the cache foot print. The
global to free pool must have an extra twist to accomodate non-batch
sized drops and to handle the all slots are full case, but that's just a
trivial detail.

See the completely untested combo patch against tip core/debugobjects
below.

Thanks,

tglx
---
--- a/lib/debugobjects.c
+++ b/lib/debugobjects.c
@@ -21,10 +21,17 @@
 #define ODEBUG_HASH_BITS   14
 #define ODEBUG_HASH_SIZE   (1 << ODEBUG_HASH_BITS)
 
+/* Must be power of two */
+#define ODEBUG_BATCH_SIZE  16
+#define ODEBUG_BATCH_SIZE_MASK (ODEBUG_BATCH_SIZE - 1)
+
+/* Must all be a multiple of batch size */
 #define ODEBUG_POOL_SIZE   1024
 #define ODEBUG_POOL_MIN_LEVEL  256
 #define ODEBUG_POOL_PERCPU_SIZE64
-#define ODEBUG_BATCH_SIZE  16
+
+#define ODEBUG_POOL_SLOTS  (NR_CPUS + (ODEBUG_POOL_SIZE / 
ODEBUG_BATCH_SIZE))
+#define ODEBUG_PCPU_SLOTS  (ODEBUG_POOL_PERCPU_SIZE / ODEBUG_BATCH_SIZE)
 
 #define ODEBUG_CHUNK_SHIFT PAGE_SHIFT
 #define ODEBUG_CHUNK_SIZE  (1 << ODEBUG_CHUNK_SHIFT)
@@ -43,16 +50,22 @@ struct debug_bucket {
raw_spinlock_t  lock;
 };
 
-/*
- * Debug object percpu free list
- * Access is protected by disabling irq
- */
-struct debug_percpu_free {
-   struct hlist_head   free_objs;
-   int obj_free;
+struct pcpu_pool {
+   unsigned intslot_idx;
+   unsigned intcnt;
+   struct hlist_head   slots[ODEBUG_PCPU_SLOTS];
 };
 
-static DEFINE_PER_CPU(struct debug_percpu_free, percpu_obj_pool);
+struct global_pool {
+   unsigned intslot_idx;
+   unsigned inttot_cnt;
+   unsigned intbulk_cnt;
+   struct hlist_head   slots[ODEBUG_POOL_SLOTS];
+   struct hlist_head   bulk;
+} cacheline_aligned;
+
+
+static DEFINE_PER_CPU_ALIGNED(struct pcpu_pool, percpu_pool);
 
 static struct debug_bucket obj_hash[ODEBUG_HASH_SIZE];
 
@@ -60,8 +73,10 @@ static struct debug_obj  obj_static_pool
 
 static DEFINE_RAW_SPINLOCK(pool_lock);
 
-static HLIST_HEAD(obj_pool);
-static HLIST_HEAD(obj_to_free);
+static struct global_pool  pool_global;
+static struct global_pool  pool_to_free;
+
+static HLIST_HEAD(pool_boot);
 
 /*
  * Because of the presence of percpu free pools, obj_pool_free will
@@ -71,12 +86,9 @@ static HLIST_HEAD(obj_

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Leizhen (ThunderTown)]

On 2024/9/10 2:41, Thomas Gleixner wrote:
> On Wed, Sep 04 2024 at 21:41, Zhen Lei wrote:
> 
>> Currently, there are multiple instances where several nodes are extracted
>> from one list and added to another list. One by one extraction, and then
>> one by one splicing, not only low efficiency, readability is also poor.
>> The work can be done well with hlist_cut_number() and hlist_splice_init(),
>> which move the entire sublist at once.
>>
>> When the number of nodes expected to be moved is less than or equal to 0,
>> or the source list is empty, hlist_cut_number() safely returns 0. The
>> splicing is performed only when the return value of hlist_cut_number() is
>> greater than 0.
>>
>> For two calls to hlist_cut_number() in __free_object(), the result is
>> obviously positive, the check of the return value is omitted.
> 
> Sure but hlist_cut_number() suffers from the same problem as the current
> code. If is a massive cache line chase as you actually have to walk the
> list to figure out where to cut it off.
> 
> All related functions have this problem and all of this code is very
> strict about boundaries. Instead of accurately doing the refill, purge
> etc. we should look into proper batch mode mechanisms. Let me think
> about it.

It may be helpful to add several arrays to record the first node of each batch
in each free list. Take 'percpu_pool' as an example:

struct debug_percpu_free {
struct hlist_head   free_objs;
int obj_free;
+   int batch_idx;
+   struct hlist_node   *batch_first[4]; // ODEBUG_POOL_PERCPU_SIZE / 
ODEBUG_BATCH_SIZE
};

A new free node is added to the header of the list, and the batch is cut from 
the tail
of the list.
  NodeA<-->...<-->NodeB<-->...<-->NodeC<-->NodeD<--> free_objs
|---one batch---|---one batch---|
|   |
batch_first[0]  batch_first[1]

__free_object():
//add obj into percpu_pool
obj_free++;
if (obj_free % ODEBUG_BATCH_SIZE == 0) {
idx = 0x3 & (batch_idx + (obj_free / ODEBUG_BATCH_SIZE) - 1);
//update batch_first[idx]
}

if (obj_free >= ODEBUG_POOL_PERCPU_SIZE) {
//move one batch
//cut batch at 'batch_idx' into obj_to_free (or obj_pool, if 
less than debug_objects_pool_min_level)
batch_idx++;
obj_free -= ODEBUG_BATCH_SIZE
}

> 
> Thanks,
> 
> tglx
> 
> 
> .
> 

-- 
Regards,
  Zhen Lei

Re: [PATCH 3/3] debugobjects: Use hlist_cut_number() to optimize performance and improve readability

[Thomas Gleixner]

On Wed, Sep 04 2024 at 21:41, Zhen Lei wrote:

> Currently, there are multiple instances where several nodes are extracted
> from one list and added to another list. One by one extraction, and then
> one by one splicing, not only low efficiency, readability is also poor.
> The work can be done well with hlist_cut_number() and hlist_splice_init(),
> which move the entire sublist at once.
>
> When the number of nodes expected to be moved is less than or equal to 0,
> or the source list is empty, hlist_cut_number() safely returns 0. The
> splicing is performed only when the return value of hlist_cut_number() is
> greater than 0.
>
> For two calls to hlist_cut_number() in __free_object(), the result is
> obviously positive, the check of the return value is omitted.

Sure but hlist_cut_number() suffers from the same problem as the current
code. If is a massive cache line chase as you actually have to walk the
list to figure out where to cut it off.

All related functions have this problem and all of this code is very
strict about boundaries. Instead of accurately doing the refill, purge
etc. we should look into proper batch mode mechanisms. Let me think
about it.

Thanks,

tglx