1. Patchew
  2. linux
  3. View series

[PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc

Josh Law posted 1 patch 2 weeks, 4 days ago
There is a newer version of this series
lib/assoc_array.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
[PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Josh Law 2 weeks, 4 days ago 
In assoc_array_gc(), assoc_array_apply_edit() publishes the new tree
root before nr_leaves_on_tree is updated, creating a window where the
tree is visible with a stale leaf count. Move the nr_leaves_on_tree
assignment before assoc_array_apply_edit() so the count is consistent
when the new root becomes visible.

Signed-off-by: Josh Law <objecting@objecting.org>
---
 lib/assoc_array.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/assoc_array.c b/lib/assoc_array.c
index bcc6e0a013eb..0752fd44e066 100644
--- a/lib/assoc_array.c
+++ b/lib/assoc_array.c
@@ -1711,8 +1711,8 @@ int assoc_array_gc(struct assoc_array *array,
 
 gc_complete:
 	edit->set[0].to = new_root;
-	assoc_array_apply_edit(edit);
 	array->nr_leaves_on_tree = nr_leaves_on_tree;
+	assoc_array_apply_edit(edit);
 	return 0;
 
 enomem:
-- 
2.34.1
Re: [PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Andrew Morton 2 weeks, 4 days ago 
On Wed, 18 Mar 2026 16:49:59 +0000 Josh Law <objecting@objecting.org> wrote:

> In assoc_array_gc(), assoc_array_apply_edit() publishes the new tree
> root before nr_leaves_on_tree is updated, creating a window where the
> tree is visible with a stale leaf count. Move the nr_leaves_on_tree
> assignment before assoc_array_apply_edit() so the count is consistent
> when the new root becomes visible.
> 
> ...
>
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -1711,8 +1711,8 @@ int assoc_array_gc(struct assoc_array *array,
>  
>  gc_complete:
>  	edit->set[0].to = new_root;
> -	assoc_array_apply_edit(edit);
>  	array->nr_leaves_on_tree = nr_leaves_on_tree;
> +	assoc_array_apply_edit(edit);
>  	return 0;

But assoc_array_apply_edit() alters array->nr_leaves_on_tree and now we
immediately overwrite that alteration?
Re: [PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Josh Law 2 weeks, 4 days ago 

On 18 March 2026 17:23:19 GMT, Andrew Morton <akpm@linux-foundation.org> wrote:
>On Wed, 18 Mar 2026 16:49:59 +0000 Josh Law <objecting@objecting.org> wrote:
>
>> In assoc_array_gc(), assoc_array_apply_edit() publishes the new tree
>> root before nr_leaves_on_tree is updated, creating a window where the
>> tree is visible with a stale leaf count. Move the nr_leaves_on_tree
>> assignment before assoc_array_apply_edit() so the count is consistent
>> when the new root becomes visible.
>> 
>> ...
>>
>> --- a/lib/assoc_array.c
>> +++ b/lib/assoc_array.c
>> @@ -1711,8 +1711,8 @@ int assoc_array_gc(struct assoc_array *array,
>>  
>>  gc_complete:
>>  	edit->set[0].to = new_root;
>> -	assoc_array_apply_edit(edit);
>>  	array->nr_leaves_on_tree = nr_leaves_on_tree;
>> +	assoc_array_apply_edit(edit);
>>  	return 0;
>
>But assoc_array_apply_edit() alters array->nr_leaves_on_tree and now we
>immediately overwrite that alteration?


2/2

No, unless if the resulting tree is completely empty (edit->array->root == NULL). In that scenario, assoc_array_apply_edit() explicitly sets edit->array->nr_leaves_on_tree = 0, but since it's zero, it overwrites 0 with 0, 

and In the assoc_array_gc() path, the edit struct is allocated with kzalloc(), 
and edit->adjust_count_on is never set (it stays NULL). Because it's NULL,
 assoc_array_apply_edit() actually skips the block that alters array->nr_leaves_on_tree

V/R

Josh Law
Re: [PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Josh Law 2 weeks, 4 days ago 

On 18 March 2026 17:23:19 GMT, Andrew Morton <akpm@linux-foundation.org> wrote:
>On Wed, 18 Mar 2026 16:49:59 +0000 Josh Law <objecting@objecting.org> wrote:
>
>> In assoc_array_gc(), assoc_array_apply_edit() publishes the new tree
>> root before nr_leaves_on_tree is updated, creating a window where the
>> tree is visible with a stale leaf count. Move the nr_leaves_on_tree
>> assignment before assoc_array_apply_edit() so the count is consistent
>> when the new root becomes visible.
>> 
>> ...
>>
>> --- a/lib/assoc_array.c
>> +++ b/lib/assoc_array.c
>> @@ -1711,8 +1711,8 @@ int assoc_array_gc(struct assoc_array *array,
>>  
>>  gc_complete:
>>  	edit->set[0].to = new_root;
>> -	assoc_array_apply_edit(edit);
>>  	array->nr_leaves_on_tree = nr_leaves_on_tree;
>> +	assoc_array_apply_edit(edit);
>>  	return 0;
>
>But assoc_array_apply_edit() alters array->nr_leaves_on_tree and now we
>immediately overwrite that alteration?


Hi Andrew,

It probably doesn't overwrite it in this specific case.


In assoc_array_gc(), the edit script is zero-initialized, meaning edit->adjust_count_on is NULL. Because of this (and since array->root isn't NULL), assoc_array_apply_edit() safely skips the block that modifies nr_leaves_on_tree.

Since apply_edit() doesn't touch the count here, the explicit assignment right after is necessary to record the newly calculated post-GC count.


V/R


Josh Law
Re: [PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Andrew Morton 2 weeks, 4 days ago 
On Wed, 18 Mar 2026 17:29:10 +0000 Josh Law <objecting@objecting.org> wrote:

> >
> >But assoc_array_apply_edit() alters array->nr_leaves_on_tree and now we
> >immediately overwrite that alteration?
> 
> 
> Hi Andrew,
> 
> It probably doesn't overwrite it in this specific case.
> 
> 
> In assoc_array_gc(), the edit script is zero-initialized, meaning edit->adjust_count_on is NULL. Because of this (and since array->root isn't NULL), assoc_array_apply_edit() safely skips the block that modifies nr_leaves_on_tree.

wordwrapping, please.

> Since apply_edit() doesn't touch the count here, the explicit assignment right after is necessary to record the newly calculated post-GC count.

How about asking the author of this code?
Re: [PATCH] lib/assoc_array: fix stale nr_leaves_on_tree after gc
Posted by Josh Law 2 weeks, 4 days ago 

On 18 March 2026 18:36:52 GMT, Andrew Morton <akpm@linux-foundation.org> wrote:
>On Wed, 18 Mar 2026 17:29:10 +0000 Josh Law <objecting@objecting.org> wrote:
>
>> >
>> >But assoc_array_apply_edit() alters array->nr_leaves_on_tree and now we
>> >immediately overwrite that alteration?
>> 
>> 
>> Hi Andrew,
>> 
>> It probably doesn't overwrite it in this specific case.
>> 
>> 
>> In assoc_array_gc(), the edit script is zero-initialized, meaning edit->adjust_count_on is NULL. Because of this (and since array->root isn't NULL), assoc_array_apply_edit() safely skips the block that modifies nr_leaves_on_tree.
>
>wordwrapping, please.
>
>> Since apply_edit() doesn't touch the count here, the explicit assignment right after is necessary to record the newly calculated post-GC count.
>
>How about asking the author of this code?


+ CC: dhowells@redhat.com (file author)

Sorry Andrew, my email client isn't the best (Thunderbird mobile), I'm away from my laptop right now for a little bit..

V/R

Josh Law

Patchew 2.1-devel-ea86937

© 2016 - 2026 Red Hat, Inc.