assoc_array: don't lose objects when a root shortcut is split at level 4

assoc_array_insert_mid_shortcut() takes level, the level of the node
holding the shortcut as assoc_array_walk() reports it, and adds
ASSOC_ARRAY_LEVEL_STEP to get the level of a node in that shortcut's
place.  If the new key first differs from the shortcut no further in
than that, no shortcut is made in front of the split, and new_n0 takes
the old shortcut's place directly.

A shortcut at the root is held by no node.  assoc_array_walk() reports
level 0 for it, and whatever takes its place is the root, which is read
at level 0.  So when the new key first differs from a root shortcut in
bits 4-7, diff is 4, no shortcut is made in front, and new_n0, whose
slots are indexed by bits 4-7, becomes the root and is indexed by bits
0-3.  Objects already in the array can no longer be found, and the new
one lands in a slot its key does not select.

Eighteen keys are enough: seventeen that agree on bits 0-7 make the root
a shortcut, and one that agrees with them on bits 0-3 only splits it.
Three of the eighteen objects can then not be found, and inserting one
of those keys again adds a second object instead of replacing it.

Only add the step for a shortcut that hangs from a node.  A root
shortcut split at level 4 then gets a shortcut in front of the split
that ends at level 4, as assoc_array_insert_into_terminal_node() already
makes when the leaves of a full root node first differ there.

Found by a userspace test that builds a shortcut ending at every level
and splits it at every level inside it, from the root and from a node:
every split of a root shortcut at level 4 failed, and nothing else did.

Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
Assisted-by: LLM
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

0 files changed, 0 insertions, 0 deletions