Re: [PATCH v2 3/3] assoc_array: trim the final shortcut word using the current chunk end

[Jarkko Sakkinen <jarkko@kernel.org>]

On Sat, Jul 18, 2026 at 09:38:01PM +0300, Jarkko Sakkinen wrote:
> On Tue, Jul 14, 2026 at 07:54:51AM -0400, Michael Bommarito wrote:
> > assoc_array_walk() masks off the bits past shortcut->skip_to_level in the
> > word that contains skip_to_level, gated on
> > round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > skip_to_level.
> > 
> > That guard is wrong in two opposite ways:
> > 
> >  - When sc_level is word-aligned (every word after the first) round_up()
> >    is a no-op, so the guard is sc_level > skip_to_level and never fires for
> >    the word that holds skip_to_level.  A shortcut that spans more than one
> >    word and ends in the middle of its last word leaves that word untrimmed,
> >    and its stale high bits leak into the dissimilarity word and can steer
> >    the walk down the wrong descendant.
> > 
> >  - When sc_level is unaligned (the first word) and skip_to_level sits on
> >    the next chunk boundary, sc_level + CHUNK would exceed skip_to_level and
> >    fire the trim with shift = skip_to_level & CHUNK_MASK == 0, which clears
> >    the whole dissimilarity word and makes a differing shortcut compare
> >    equal.
> > 
> > Use the end of the chunk that contains sc_level instead:
> > 
> > 	skip_to_level < round_down(sc_level, CHUNK) + CHUNK
> > 
> > For an aligned sc_level whose word holds skip_to_level this now fires (the
> > first bug); for an unaligned sc_level with skip_to_level on the following
> > boundary it does not, so shift is never 0 when the branch runs and the trim
> > never clears the whole word.
> > 
> > Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> > Assisted-by: Claude:claude-opus-4-8
> > Signed-off-by: Michael Bommarito <michael.bommarito@gmail.com>
> > ---
> >  lib/assoc_array.c | 3 ++-
> >  1 file changed, 2 insertions(+), 1 deletion(-)
> > 
> > diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> > index bcc6e0a013eb8..b6c9723e12ced 100644
> > --- a/lib/assoc_array.c
> > +++ b/lib/assoc_array.c
> > @@ -255,7 +255,8 @@ assoc_array_walk(const struct assoc_array *array,
> >  		sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
> >  		dissimilarity = segments ^ sc_segments;
> >  
> > -		if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
> > +		if (shortcut->skip_to_level < round_down(sc_level,
> > +				ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) {
> >  			/* Trim segments that are beyond the shortcut */
> >  			int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
> >  			dissimilarity &= ~(ULONG_MAX << shift);
> > -- 
> > 2.53.0
> > 
> 
> Reviewed-by: Jarkko Sakkinen <jarkko@kernel.org>
> 
> BR, Jarkko

Were you able to reproduce this with basic command-line tools? The
patches are verifiable by reading the code but asking this just in
case if you had a snippet at hand (not interested on complex
reproducers).

BR, Jarkko