[Bug c/98503] New: [11 regression] -Warray-bounds false positive with global variables at -O2

[Bug c/98503] New: [11 regression] -Warray-bounds false positive with global variables at -O2

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

            Bug ID: 98503
           Summary: [11 regression] -Warray-bounds false positive with
                    global variables at -O2
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: w at 1wt dot eu
  Target Milestone: ---

First, please note that I saw a handful of related reports but couldn't judge
if this one might be merged with another one; if you think it can, feel free to
do so!

We've had build errors reported on haproxy with gcc-11 due to walking over a 
list whose head is in a global variable. We could simplify the reproducer to
this and confirm it on godbolt.org:

  #include <stddef.h>

  struct list {
    struct list *n;
    struct list *p;
  };

  struct list head;

  struct ref {
        struct list list;
        char *filename;
  };

  struct list *first(void)
  {
        struct ref *tmp;

        /*tmp = (struct ref *)((char *)&head - (size_t)&((struct ref
*)0)->list);*/
        tmp = (struct ref *)&head;
        //asm("" : "+rm"(tmp)); // hide tmp's origin to shut the warning.
        //asm("" : "=rm"(tmp) : "0"(&head)); // discretely assign tmp from head
        return tmp->list.n;
  }

Note that only the "ref->list" part is accessed here, hence it exactly matches
"head" (both of type struct list). But since gcc 11 (and only this one, 1.27 to
10.2 are OK), we're getting this:

  <source>: In function 'first':
  <source>:22:19: warning: array subscript 'struct ref[0]' is partly outside
array bounds of 'struct list[1]' [-Warray-bounds]
     22 |         return tmp->list.n;
        |                   ^~
  <source>:8:13: note: while referencing 'head'
      8 | struct list head;
        |             ^~~~
  Compiler returned: 0

Changing "head" to a function argument makes the warning disappear, building at
-O1 as well, and obviously, cheating with the asm statement to hide "tmp"
solves it (though it degrades the code quality).

Removing the unused "filename" from struct "ref" removes the warning. It looks
to me as if the compiler doesn't know what part of a structure is being
dereferenced when we access any member, making the warning systematically bogus
for embedded members accessed via container_of() and friends when the list's
head is global.

For now we can disable the warning, I've confirmed the generated code is
correct, but since it's the first time we have a false positive on this one,
I'd prefer if we can keep it as much as possible as it's one which can
definitely help spot real bugs.

I've just verified the version used on godbolt.org, it's "gcc version 11.0.0
20210101 (experimental) (Compiler-Explorer-Build)". I haven't rebuilt the trunk
locally so it might be possible this bug got solved since as part of one of the
few related ones.

Thanks!
Willy

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #1 from Willy Tarreau <w at 1wt dot eu> ---
Re-reading godbolt's version more closely, it's just 1 day old (I thought I
read 20201010) so the issue is still valid.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[marxin at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Liška <marxin at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to fail|                            |11.0
            Summary|[11 regression]             |[11 regression]
                   |-Warray-bounds false        |-Warray-bounds false
                   |positive with global        |positive with global
                   |variables at -O2            |variables at -O2 since
                   |                            |r11-3306-g3f9a497d1b0dd9da
      Known to work|                            |10.2.0
                 CC|                            |marxin at gcc dot gnu.org,
                   |                            |msebor at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-01-04
     Ever confirmed|0                           |1
   Target Milestone|---                         |11.0

--- Comment #2 from Martin Liška <marxin at gcc dot gnu.org> ---
Thank you for the report, started with r11-3306-g3f9a497d1b0dd9da.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #3 from Martin Sebor <msebor at gcc dot gnu.org> ---
The phrasing of the warning could stand to be made clearer but it is by design.
  With the exception of a union with a /common initial sequence/, it's not
valid to access [members of] an object of one type (struct list) using a
pointer to an incompatible type (struct ref).  It doesn't matter if the offset
of the member is less than the size of the object.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #4 from Willy Tarreau <w at 1wt dot eu> ---
Hi Martin,

I'm sorry but I'm missing something, as this is how linked lists are
implemented everywhere nowadays. I'm not actually casting the pointer, it was
made for simplification. I'm only following the list elements which are linked
together from a list head accessed via a container_of.

The code does nothing but follow the list from the head (which is only a struct
list) and visiting all nodes in turn. There is absolutely zero dereference of a
list using a wrong pointer here.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Willy Tarreau <w at 1wt dot eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|INVALID                     |---
             Status|RESOLVED                    |REOPENED

--- Comment #5 from Willy Tarreau <w at 1wt dot eu> ---
apparently I closed it by accident, reopening, sorry.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|REOPENED                    |RESOLVED
         Resolution|---                         |INVALID

--- Comment #6 from Martin Sebor <msebor at gcc dot gnu.org> ---
In the test case in comment #0 the operand of the return statement in first()
dereferences the tmp pointer:

  return tmp->list.n;

The expression is equivalent to (*tmp).list.n where the dereference should be
more obvious.  The dereference is invalid if tmp points to an object of an
incompatible type.  This is a basic type-based aliasing requirement that GCC
relies on.

If the test case isn't representative of the problem you see in the code base
please submit one that does.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Willy Tarreau <w at 1wt dot eu> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|INVALID                     |---
             Status|RESOLVED                    |REOPENED

--- Comment #7 from Willy Tarreau <w at 1wt dot eu> ---
It's not easy because as often with optimizations, depending on the code moves
I'm doing, the issue appears and disappears. The closest looking one is below.

The general idea is that we're having a function that is called to dump a
certain number of elements to a buffer and return when the buffer is full, to
give back control to other parts of the code, then it's called again from the
last list element where the dump was started. A common practice with such
interruptible processing of list consists in starting from the head and letting
the dump function iterate. This would roughly look like this (still simplified
quite a bit to grasp the principle). The code below manages to trigger the
warning. If you're interested in the original code (I doubt it), it's on this
line: https://github.com/haproxy/haproxy/blob/master/src/ssl_sock.c#L6366 and
the initial call is made here:
https://github.com/haproxy/haproxy/blob/master/src/ssl_sock.c#L6437

#include <stddef.h>

#define container_of(ptr, type, member) ({                              \
        void *__mptr = (void *)(ptr);                                   \
        ((type *)(__mptr - __builtin_offsetof(type, member))); })

// returns number of bytes emitted or 0 if it failed to dump.
extern int try_dump_string(const char *name);

struct list {
    struct list *n;
    struct list *p;
};

static struct list head;

struct ref {
        struct list list;
        char *filename;
};

static struct ref *last_dumped;

/* try to dump one ref, returns 0 on failure */
static inline int try_dump_next_ref(struct ref *ref)
{
    return try_dump_string(ref->filename);
}

static inline struct ref *get_initial_step()
{
    return container_of(&head, struct ref, list);
}

static inline struct ref *next_step(struct ref *cur)
{
    return container_of(cur->list.n, struct ref, list);
}

/* restarts a dump from dump_context or starts a new one if NULL */
struct ref *restart_dump(struct ref *last)
{
        struct ref *curr;

        if (!last)
            last = get_initial_step();

        curr = next_step(last);
        while (&curr->list != &head) {
            if (try_dump_next_ref(curr)) {
                last = curr;
                curr = next_step(curr);
            } else {
                /* do something to yield or flush the output */
            }
        }
        return last;
}

void cont_dump()
{
    restart_dump(last_dumped);
}


Please note that here "last_dump" isn't updated and if the compiler sees it
being written to, it eliminates some optimizations that result in the warning
(I think it sees that the get_initial_step() is conditional and thus doesn't
complain anymore).

I understand from your description that there could be an aliasing issue. I'd
argue that as soon as we're using lists there are potential aliasing issues and
that these may then be addressed using -fno-strict-aliasing but this one has no
effect here either.

Also I suspect based on your description, that accessing *any* field of a
struct implies the whole struct must be mapped in memory. But then there are
limits in case of aliased struct like above, or even when using VLAs since you
can't figure the possible extent of the variable part.

I think I see how I could cheat to eliminate the warning (not easy to test as I
don't have the trunk version of the compiler locally), but I suspect that doing
so would definitely make the code more error-prone.

I sincerely think that this *exact* case is counter-productive as it will
basically force a number of users of lists to disable the whole warning, which
was otherwise particularly effective at detecting real out-of-bounds accesses,
especially in such use cases. Or maybe you could assign it a different level
(-Warray-bounds=3 ?) to indicate a suspicious usage that might also be a valid
one ?

Thanks!
Willy

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #8 from Richard Biener <rguenth at gcc dot gnu.org> ---
Note the example clearly violates C TBAA rules and the "optimization" of
eliding the data member(s) for 'head' are invalid.  It's not only about
diagnostics but about wrong-code generation waiting to happen (unless you use
-fno-strict-aliasing).

If you access only the list head part then use a pointer to list for the
access.
Note I don't see the actual bogus access (the accesses seem to be guarded
with &curr->list != &head) but the warning might be exposed by path isolating
of actually unreachable code.

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #9 from Willy Tarreau <w at 1wt dot eu> ---
Hi Richard,

indeed, the &curr->list == &head is the test for end of list that prevents any
bad access from happening.

I know that usually the right way to do this is by using a list element, but
sometimes it requires placing casts all over the code, or container_of() and
friends in every single call, which is way more error-prone. Writing state
machines with different input types in general doesn't result in reliable
long-term code. It turns out that in the code affected by this there were only
two call places that I could tear a little bit to use the list instead (and an
alias pointer, which I hate keeping) but I'm not extremely happy with this
workaround.

I'm well aware that there can be aliasing issues while doing this, which is
also why I tested with -fno-strict-aliasing and saw the warninig remain, which
I'd argue is definitely not appropriate in this case.

I really think that this one is border-line. Not useless at all, but should
only trigger at a higher level so that users don't have to get rid of
-Warray-bounds just because of it. The linux kernel already had to disable it
for other reasons and that's really sad in my opinion, which is why I'm trying
hard to keep it.

Thanks,
Willy

[Bug c/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #10 from Martin Sebor <msebor at gcc dot gnu.org> ---
The main purpose of the "partly outside" warning is to detect reads/writes that
cross the trailing array boundary.  Those typically come up when a "typeless"
buffer (either char array or one allocated by a function like malloc) is used
to store a sequence of heterogeneous elements.  Besides these bugs the warning
also detects other kinds of invalid accesses that span the boundary, like in
comment #0.  The access there in invalid for a different reason than the usual
-Warray-bounds, so issuing a warning that's controlled by a different option
would be appropriate (-Wstrict-aliasing seems like a good fit).  It's something
we have discussed doing but it's not at the top my to do list.  Making it
conditional on -fstrict-aliasing might be worth considering as well.

[Bug middle-end/98503] [11 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |patch
          Component|c                           |middle-end
           Assignee|unassigned at gcc dot gnu.org      |msebor at gcc dot gnu.org
             Status|REOPENED                    |ASSIGNED

--- Comment #11 from Martin Sebor <msebor at gcc dot gnu.org> ---
Patch to issue -Wstrict-aliasing instead of -Warray-bounds in the subset of
cases when the member access is fully in bounds but the enclosing struct is
not:
  https://gcc.gnu.org/pipermail/gcc-patches/2021-January/564483.html

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.0                        |11.2

--- Comment #12 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 11.1 has been released, retargeting bugs to GCC 11.2.

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|msebor at gcc dot gnu.org          |unassigned at gcc dot gnu.org
             Status|ASSIGNED                    |NEW

--- Comment #13 from Martin Sebor <msebor at gcc dot gnu.org> ---
The patch was rejected so we'll have to live with a confusing warning.

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #14 from Willy Tarreau <w at 1wt dot eu> ---
(In reply to Martin Sebor from comment #13)
> The patch was rejected so we'll have to live with a confusing warning.

sadly it's not the first one and I don't count the number of bugs I have
introduced in my code just to try to work around inappropriate warnings :-(
It's really sad that over time code is getting more and more fragile instead of
getting more and more robust :-(

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|11.2                        |11.3

--- Comment #15 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 11.2 is being released, retargeting bugs to GCC 11.3

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Martin Sebor <msebor at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |slyfox at gcc dot gnu.org

--- Comment #16 from Martin Sebor <msebor at gcc dot gnu.org> ---
*** Bug 103292 has been marked as a duplicate of this bug. ***

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #17 from Martin Sebor <msebor at gcc dot gnu.org> ---
*** Bug 104341 has been marked as a duplicate of this bug. ***

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #18 from Richard Biener <rguenth at gcc dot gnu.org> ---
So at the point we diagnose we see the following IL for cont_dump:

<bb 2> [local count: 1073741824]:
__mptr_5 = MEM[(struct ref *)&head].list.n;
goto <bb 8>; [100.00%]

that's because the testcase has static 'last_dumped' which means it is NULL
and we start restart_dump with

        if (!last)
            last = get_initial_step();

which does

static inline struct ref *get_initial_step()
{
    return container_of(&head, struct ref, list);
}

that means next_step will do the bad access of 'head' using the struct ref
type.

[Bug middle-end/98503] [11/12 regression] -Warray-bounds false positive with global variables at -O2 since r11-3306-g3f9a497d1b0dd9da

[w at 1wt dot eu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98503

--- Comment #19 from Willy Tarreau <w at 1wt dot eu> ---
Hello Richard,

Thanks for looking at this old issue.

> that means next_step will do the bad access of 'head' using the struct ref
> type.

Actually there's no bad access, as if you look closely, next_step() restarts
from cur->list.n, hence undoes exactly what initial_step() did.

In addition for the special case here, the list happens to be at the beginning
of the struct so there's not even an offset of difference between the list head
and the member, so get_initial_step() really returns head here, and next_step()
will return exactly head as well, which does match the stop condition in the
following while() block and never causes any dereference of any unmapped area.

I noticed I have left a mistake when writing the simplified reproducer, I
didn't initialise head, thus I thought it could have contributed to the warning
in the reproducer, but retesting with:

    static struct list head = { .n = &head, .p = &head };

doesn't change anything.

Since then we've worked around this problem by using some ugly casts because
removing the warning could have more long-term consequences if it occasionally
allows to trigger on a real issue. Still I find it sad when a warning forces us
to introduce dangerous casts as a workaround.