Re: [PATCH 3/3] assoc_array: trim the final shortcut word when skip_to_level is chunk-aligned

[Jarkko Sakkinen]

On Sat, Jul 18, 2026 at 09:32:46PM +0300, Jarkko Sakkinen wrote:
> On Sat, Jul 11, 2026 at 09:45:00PM -0400, Michael Bommarito wrote:
> > assoc_array_walk() masks off the bits past shortcut->skip_to_level in
> > the final word of a shortcut before testing it, gated on
> > round_up(sc_level, chunk_size) > skip_to_level.  Once sc_level is
> > word-aligned (every word after the first) round_up() is a no-op and the
> > guard never fires for the word that contains skip_to_level, so its stale
> > high bits leak into the dissimilarity word and can steer the walk down
> > the wrong descendant.
> > 
> > Test sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE > skip_to_level directly; an
> > exact-multiple skip_to_level ends on the boundary and stays untrimmed.
> > 
> > Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> > Assisted-by: Claude:claude-opus-4-8
> > Signed-off-by: Michael Bommarito <michael.bommarito@xxxxxxxxx>
> > ---
> >  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 bcc6e0a013eb8..1de2c337f8fcf 100644
> > --- a/lib/assoc_array.c
> > +++ b/lib/assoc_array.c
> > @@ -255,7 +255,7 @@ 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 (sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE > shortcut->skip_to_level) {
> >  			/* 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
> > 
> 
> Ditto.
> 
> Reviewed-by: Jarkko Sakkinen <jarkko@xxxxxxxxxx>
> 
> BR, Jarkko

On holiday up until end of this month so expect some delay in my
responses.

BR, Jarkko