assoc_array.c uninitialized variable (was: Re: [PATCH 02/10] Add a generic associative array implementation.)

assoc_array.c uninitialized variable (was: Re: [PATCH 02/10] Add a generic associative array implementation.)

[Geert Uytterhoeven]

On Wed, Jul 17, 2013 at 10:43 PM, David Howells <dhowells@redhat.com> wrote:
> +/*
> + * Handle insertion into a terminal node.
> + */
> +static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
> +                                                 const struct assoc_array_ops *ops,
> +                                                 const void *index_key,
> +                                                 struct assoc_array_walk_result *result)
> +{
> +       struct assoc_array_shortcut *shortcut, *new_s0;
> +       struct assoc_array_node *node, *new_n0, *new_n1, *side;
> +       struct assoc_array_ptr *ptr;
> +       unsigned long dissimilarity, base_seg, blank;
> +       size_t keylen;
> +       bool have_meta;
> +       int level, diff;
> +       int slot, next_slot, free_slot, i, j;

lib/assoc_array.c: In function ‘assoc_array_insert_into_terminal_node’:
lib/assoc_array.c:502: warning: ‘j’ may be used uninitialized in this function

> +       /* Begin by finding two matching leaves.  There have to be at least two
> +        * that match - even if there are meta pointers - because any leaf that
> +        * would match a slot with a meta pointer in it must be somewhere
> +        * behind that meta pointer and cannot be here.  Further, given N
> +        * remaining leaf slots, we now have N+1 leaves to go in them.
> +        */
> +       for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
> +               slot = edit->segment_cache[i];
> +               if (slot != 0xff)
> +                       for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)

j is initialized here, but only if slot != 0xff.

The comment above states "there have to be at least two that match",
so this may be a false positive, but better safe than sorry.

> +                               if (edit->segment_cache[j] == slot)
> +                                       goto found_slot_for_multiple_occupancy;
> +       }
> +found_slot_for_multiple_occupancy:
> +       pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
> +       BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
> +       BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
> +       BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

Re: assoc_array.c uninitialized variable (was: Re: [PATCH 02/10] Add a generic associative array implementation.)

[David Howells]

Geert Uytterhoeven <geert@linux-m68k.org> wrote:

> > +       int slot, next_slot, free_slot, i, j;
> 
> lib/assoc_array.c: In function ‘assoc_array_insert_into_terminal_node’:
> lib/assoc_array.c:502: warning: ‘j’ may be used uninitialized in this function

What compiler are you using?  Mine doesn't show this.

Technically, the compiler is correct - but we should never see the variable
undefined following the found_slot_for_multiple_occupancy unless the tree
changes under us. Out of a set of N+1 integers that can only be in the range
0..N-1 there must be at least two the same.

I guess I could preclear j to make the warning go away.

David

Re: assoc_array.c uninitialized variable (was: Re: [PATCH 02/10] Add a generic associative array implementation.)

[Geert Uytterhoeven]

Hi David,

On Mon, Nov 25, 2013 at 10:36 AM, David Howells <dhowells@redhat.com> wrote:
> Geert Uytterhoeven <geert@linux-m68k.org> wrote:
>
>> > +       int slot, next_slot, free_slot, i, j;
>>
>> lib/assoc_array.c: In function ‘assoc_array_insert_into_terminal_node’:
>> lib/assoc_array.c:502: warning: ‘j’ may be used uninitialized in this function
>
> What compiler are you using?  Mine doesn't show this.

Good old 4.2.1. Newer compilers don't give these warnings anymore, presumably
because there were too many false positives. But from time to time, there's
a real issue.

> Technically, the compiler is correct - but we should never see the variable
> undefined following the found_slot_for_multiple_occupancy unless the tree
> changes under us. Out of a set of N+1 integers that can only be in the range
> 0..N-1 there must be at least two the same.

OK.

> I guess I could preclear j to make the warning go away.

Please use a big number instead of zero, so the

        BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);

will catch it later.

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds