[Mesa-dev] [PATCH] Fix strict-aliasing violations in GLSL shader list implementation

[Ian Romanick]

On 06/24/2015 03:59 PM, Davin McCall wrote:
> Hi Ian,
> 
> On 23/06/15 23:26, Ian Romanick wrote:
>> On 06/23/2015 02:36 PM, Thomas Helland wrote:
>>> 2015-06-24 23:05 GMT+02:00 Davin McCall <davmac at davmac.org>:
>>>> Hi - I'm new here.
>>>>
>>>> I've recently started poking the Mesa codebase for little reason other than
>>>> personal interest. In the "help wanted" section of the website it mentions
>>>> aliasing violations as a target for newcomers to fix, so with that in mind
>>>> I've attached a patch (against git head) which resolves a few of them, by
>>>> targeting the linked list implementation (list.h) used in the GLSL
>>>> compiler/optimizers. This change slightly increases the storage requirements
>>>> for a list (adds one word) but resolves the blatant aliasing violation that
>>>> was caused by the trick used to conserve that word in the first place.
>>>>
>>>> (I toyed with another approach - using a single sentinel node for both the
>>>> head and tail of a list - but this was much more invasive, and meant that
>>>> you could no longer check whether a particular node was a sentinel node
>>>> unless you had a reference to the list, so I gave up and went with this
>>>> simpler approach).
>>>>
>>>> The most essential change is in the 'exec_list' structure. Three fields
>>>> 'head', 'tail' and 'tail_pred' are removed, and two separate sentinel nodes
>>>> are inserted in their place. The old 'head' is replaced by
>>>> 'head_sentinel.next', 'tail_pred' by 'tail_sentinel.prev', and tail (always
>>>> NULL) by 'head_sentinel.prev' and 'tail_sentinel.next' (both always NULL).
>> NAK.  The datastructure is correct as-is.  It has been in common use
>> since at least 1985.  See the references in the header file.
> 
> I understand the data structure and how it is supposed to work; the
> issue is that the trick it employs cannot be implemented in C without
> breaking the strict aliasing rules (or at least, the current
> implementation in Mesa breaks the strict aliasing rules). The current
> code works correctly only with the -fno-strict-aliasing compiler option.
> The issue is that a pair of 'exec_node *' do not constitute an exec_node
> in the eyes of the language spec, even though exec_node is declared as
> holding two such pointers. Consider (from src/glsl/list.h):
> 
>     static inline void
>     exec_list_make_empty(struct exec_list *list)
>     {
>        list->head = (struct exec_node *) & list->tail;
>        list->tail = NULL;
>        list->tail_pred = (struct exec_node *) & list->head;
>     }
> 
> 
> 'list->head' is of type 'struct exec_node *', and so should point at a
> 'struct  exec_node'. In the code above it is instead co-erced to point
> at a 'struct exec_node *' (list->tail). That in itself doesn't break the
> alias rules, but then:
> 
>     static inline bool
>     exec_node_is_tail_sentinel(const struct exec_node *n)
>     {
>        return n->next == NULL;
>     }
> 
> 
> In 'exec_node_is_tail_sentinel', the sentinel is not actually an
> exec_node - it is &list->tail. So, if the parameter n does refer to the
> sentinel, then it does not point to an actual exec_node structure.
> However, it is de-referenced (by 'n->next') which breaks the strict
> aliasing rules. This means that the method above can only ever return
> false, unless it violates the aliasing rules.
> 
> (The above method could be fixed by casting n to an 'struct exec_node
> **' and then comparing '**n' against NULL. However, there are other
> similar examples throughout the code that I do not think would be so
> trivial).
> 
> I can quote the relevant parts of the standard if necessary, but your
> tone somewhat implies that you wouldn't even consider this patch?

Please quote the spec.  I have a hard time believing that the compiler
magically decides that an exec_node* is not really an exec_node* and
just does whatever it wants (which sounds like what you're describing).
 That sounds pretty rubbish... and I'm surprised that anything works in
such an environment.

Mesa has also had -fno-strict-aliasing for as long as I can remember,
and this structure has only been used here for a few years.  The whole
thing just doesn't smell right.

> Davin