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

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

[Josh Law]

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 v2] lib/assoc_array: fix stale nr_leaves_on_tree after gc

[David Howells]

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.

This just moves the window.  The count is then inconsistent before the new
root becomes visible.

Note that there's no guarantee that nr_leaves_on_tree is stable if you're not
locking against modification.  Further, if you look in:

	Documentation/core-api/assoc_array.rst

there's no mention of nr_leaves_on_tree being part of the API.  Unfortunately,
C doesn't allow me to put in a private: marker as C++ does.

Note that neither assoc_array_iterate() nor assoc_array_find() make reference
to the value.

Are you actually seeing a problem stemming from this?

David

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

[Josh Law]

On 19 March 2026 14:14:58 GMT, David Howells <dhowells@redhat.com> wrote:
>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.
>
>This just moves the window.  The count is then inconsistent before the new
>root becomes visible.
>
>Note that there's no guarantee that nr_leaves_on_tree is stable if you're not
>locking against modification.  Further, if you look in:
>
>	Documentation/core-api/assoc_array.rst
>
>there's no mention of nr_leaves_on_tree being part of the API.  Unfortunately,
>C doesn't allow me to put in a private: marker as C++ does.
>
>Note that neither assoc_array_iterate() nor assoc_array_find() make reference
>to the value.
>
>Are you actually seeing a problem stemming from this?
>
>David
>



Well, the bug actually is there, and if i made a mistake, this patch should atleast be hardening level, (As i say, better safe than sorry)


V/R


Josh Law

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

[David Howells]

Josh Law <objecting@objecting.org> wrote:

> Well, the bug actually is there,

But is there a bug?  The field is internal to assoc_array, and the assoc_array
code only accesses it if the caller is holding a lock to prevent other
modifications.  The field is not pertinent to searching the tree under just
the RCU read lock.

> and if i made a mistake, this patch should atleast be hardening level, (As i
> say, better safe than sorry)

Your patch doesn't actually fix the issue; it merely slides the window.  The
window *could* be closed on x86_64, say, by using CMPXCHG16 to change both the
root pointer and the counter simultaneously, but beyond that you can't close
it without using a lock.

David

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

[Josh Law]

On 19 March 2026 17:04:32 GMT, David Howells <dhowells@redhat.com> wrote:
>Josh Law <objecting@objecting.org> wrote:
>
>> Well, the bug actually is there,
>
>But is there a bug?  The field is internal to assoc_array, and the assoc_array
>code only accesses it if the caller is holding a lock to prevent other
>modifications.  The field is not pertinent to searching the tree under just
>the RCU read lock.
>
>> and if i made a mistake, this patch should atleast be hardening level, (As i
>> say, better safe than sorry)
>
>Your patch doesn't actually fix the issue; it merely slides the window.  The
>window *could* be closed on x86_64, say, by using CMPXCHG16 to change both the
>root pointer and the counter simultaneously, but beyond that you can't close
>it without using a lock.
>
>David
>


After double checking, it appears you are right, sorry for wasting your time 

V/R


Josh Law

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

[David Howells]

Josh Law <objecting@objecting.org> wrote:

> After double checking, it appears you are right, sorry for wasting your time 

Don't worry about it :-)  Better to have it checked than to miss something!

David