assoc_array: don't lose objects when a shortcut is split on a word boundary

When assoc_array_insert_mid_shortcut() splits a shortcut at level diff,
the new shortcut in front of the split, new_s0, gets the first
round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE) bits of the old shortcut's
index key, and the bits from diff onwards are then cleared from its
last word:

	blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
	new_s0->index_key[keylen - 1] &= ~blank;

When diff is a multiple of ASSOC_ARRAY_KEY_CHUNK_SIZE, the shift is 0,
blank is all ones, and the whole last word is cleared, although all of
it lies below diff.  A walk then compares the key it is looking for
against that zeroed word, takes the shortcut to point elsewhere, and
every object below it can no longer be found.

assoc_array_insert_into_terminal_node() trims a new shortcut's key the
same way, and only when the level is not a multiple of the chunk size.
Do the same here.

Found by a userspace build of the array with a test that inserts, in
order, string keys whose first word is their length and the rest their
bytes.  The 102nd key split a shortcut at bit 256, and 76 of the keys
already in the array could no longer be found; AddressSanitizer also
reported assoc_array_walk() reading a word past the end of a shortcut's
index key.  With this change the test passes, and AddressSanitizer and
UndefinedBehaviorSanitizer report nothing.

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