]> git.hungrycats.org Git - linux/commit
assoc_array: keep gc's cleanup out of the live tree on allocation failure
authorLinus Torvalds <torvalds@linux-foundation.org>
Sun, 11 Oct 2026 18:24:04 +0000 (11:24 -0700)
committerGreg Kroah-Hartman <gregkh@linuxfoundation.org>
Tue, 17 Nov 2026 10:14:21 +0000 (11:14 +0100)
commitc80609763abd3f8ee7c1fe69dd43b07abff474f0
tree3ae65cf21990f718299850fc5ccd3649425e5955
parenta7990a72267f264f5284f6bcb90d397b29ac00ed
assoc_array: keep gc's cleanup out of the live tree on allocation failure

[ Upstream commit 8afff2e4b90978b8203f9e3898995dcf86821b49 ]

assoc_array_gc() builds a copy of the tree.  Where the copy reaches a
shortcut, it allocates the copy of the shortcut with kmalloc_flex(),
fills it with memcpy(), links it into the new tree, and only then
allocates the copy of the node after it.  The memcpy() leaves the new
shortcut's next_node pointing at the old tree's node, so if that second
allocation fails, the cleanup, assoc_array_destroy_subtree() on the new
tree, follows the new shortcut into the old tree, and the BUG_ON() on
the old node's back pointer fires.

Allocate the node first, and the shortcut once the node exists, freeing
the node again if the shortcut cannot be allocated.  A copied shortcut
is then only linked into the new tree when the copy of its node is there
to follow it.  Nothing else changes: with no allocation failing, the
trees gc builds are the same as before.

Found by a userspace test that makes each allocation of each operation
fail in turn.

Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Assisted-by: LLM
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Tested-by: David Howells <dhowells@redhat.com>
Reviewed-by: David Howells <dhowells@redhat.com>
Signed-off-by: Sasha Levin <sashal@kernel.org>
lib/assoc_array.c