[Mesa-dev] [PATCH 1/5] compiler: guard list iteration macros against undefined behavior

[Nicolai Hähnle]

On 09.05.2016 14:03, Matt Turner wrote:
> On Sat, May 7, 2016 at 3:05 PM, Nicolai Hähnle <nhaehnle at gmail.com> wrote:
>> From: Nicolai Hähnle <nicolai.haehnle at amd.com>
>>
>> The old iteration casts sentinel nodes (which are mere exec_nodes) into
>> whatever type we're looping over, which leads to badness (in fact, gcc's
>> undefined behaviour sanitizer crashes while trying to verify that we have
>> the correct type at hand).
>>
>> These modified looping constructs postpone the cast until its correctness
>> has been established. The odd two-level loop construct is used to be able
>> to define variables of different types, and the __sentinel variable
>> ensures that the outer loop is only run once. gcc is able to optimize the
>> outer loop away in the cases I have examined.
>
> Thanks for doing this.
>
> If I understand the issue with the current macros correctly, the
> "step" expression "(__inst) = (__type *)(__inst)->next" casts a
> sentinel node to another type, and (if that's not enough) the
> condition "!(__inst)->is_tail_sentinel()" dereferences the pointer
> through the other type, which is undefined behavior.

Thanks for taking a look!

You're right. I do think it's "only" the dereferencing which triggers 
it, but in the end that doesn't help much.

> Couldn't we avoid the double loop by changing the condition and step
> expressions like this?
>
> #define foreach_in_list(__type, __inst, __list)      \
>     for (__type *(__inst) = (__type *)(__list)->head; \
>          (__inst) != NULL;                            \
>          (__inst) = (__type *)(((__inst)->next)->is_tail_sentinel() ?
> NULL : (__inst)->next))
>
> That's perhaps simpler. What do you think?

That would _almost_ work as well. The thing is, you also need to guard 
against the list being empty (which means __list->head is a non-NULL 
pointer to a sentinel), and I believe the _safe variants of the macros 
also need to guard the initial assignment to __next. Because of this, I 
feel that the current version is simpler in the end.

> (At first I thought your implementation suffered from a problem I
> noticed with a trick like this -- "break" would only break from the
> inner loop -- but I don't think this implementation does since the
> outer loop only executes once)

Yes, that's precisely why the loops are nested this way and not the 
other way around :)

Cheers,
Nicolai