[Bug target/110657] New: BPF verifier rejects generated code due to invalid stack access

[Bug target/110657] New: BPF verifier rejects generated code due to invalid stack access

[kris.van.hees at oracle dot com]

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

            Bug ID: 110657
           Summary: BPF verifier rejects generated code due to invalid
                    stack access
           Product: gcc
           Version: 13.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: target
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kris.van.hees at oracle dot com
  Target Milestone: ---

Created attachment 55535
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55535&action=edit
C source code file for BPF function

The attached BPF program compiles into code that the BPF kernel verifier
rejects because of invalid stack access.  Code is compiled with:

bpf-gcc -gbtf -D__amd64 -Ilibdtrace -Iinclude
-I/scratch/dtrace-bpf-user/build/include -O2 -Wall -Wno-unknown-pragmas -MP
-MMD -MF /scratch/dtrace-bpf-user/build/bpf--inet_ntoa6.o.deps -MT
/scratch/dtrace-bpf-user/build/bpf--inet_ntoa6.o -c -o
/scratch/dtrace-bpf-user/build/bpf--inet_ntoa6.o bpf/inet_ntoa6.c

The bpf/inet_ntoa6.c code is attached (incomplete implementation of the
function but exhibiting the issue).  The function gets included in a larger
program so instruction numbers are much higher than in e.g. objdump output. 
Function entry point is at instruction 2432.

The BPF verifier output is:

BPF: 2432: (7b) *(u64 *)(r10 -32) = r1     ; frame2:
R1_w=map_value(off=0,ks=4,vs=528,umin=8,umax=263,var_off=(0x0;
0x1ff),s32_min=0,s32_max=511,u32_max=511) R10=fp0 fp-32_w=map_value
BPF: 2433: (bf) r6 = r2                    ; frame2:
R2_w=map_value(off=2208,ks=4,vs=3529,imm=0)
R6_w=map_value(off=2208,ks=4,vs=3529,imm=0)
BPF: 2434: (bf) r3 = r1                    ; frame2:
R1_w=map_value(off=0,ks=4,vs=528,umin=8,umax=263,var_off=(0x0;
0x1ff),s32_min=0,s32_max=511,u32_max=511)
R3_w=map_value(off=0,ks=4,vs=528,umin=8,umax=263,var_off=(0x0;
0x1ff),s32_min=0,s32_max=511,u32_max=511)
BPF: 2435: (b7) r2 = 16                    ; frame2: R2_w=P16
BPF: 2436: (bf) r1 = r10                   ; frame2: R1_w=fp0 R10=fp0
BPF: 2437: (07) r1 += -16                  ; frame2: R1_w=fp-16
BPF: 2438: (85) call bpf_probe_read#4      ; frame2: R0=Pscalar() fp-8=mmmmmmmm
fp-16=mmmmmmmm
BPF: 2439: (71) r0 = *(u8 *)(r10 -14)      ; frame2:
R0_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2440: (67) r0 <<= 8                   ; frame2:
R0_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2441: (71) r1 = *(u8 *)(r10 -13)      ; frame2:
R1_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2442: (4f) r0 |= r1                   ; frame2: R0_w=Pscalar()
R1_w=Pscalar(umax=255,var_off=(0x0; 0xff))
BPF: 2443: (71) r8 = *(u8 *)(r10 -12)      ; frame2:
R8_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2444: (67) r8 <<= 8                   ; frame2:
R8_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2445: (71) r2 = *(u8 *)(r10 -11)      ; frame2:
R2_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2446: (4f) r8 |= r2                   ; frame2:
R2_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R8_w=Pscalar()
BPF: 2447: (71) r7 = *(u8 *)(r10 -10)      ; frame2:
R7_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2448: (67) r7 <<= 8                   ; frame2:
R7_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2449: (71) r3 = *(u8 *)(r10 -9)       ; frame2:
R3_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2450: (4f) r7 |= r3                   ; frame2:
R3_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R7_w=Pscalar()
BPF: 2451: (7b) *(u64 *)(r10 -40) = r7     ; frame2: R7_w=Pscalar() R10=fp0
fp-40_w=mmmmmmmm
BPF: 2452: (71) r1 = *(u8 *)(r10 -8)       ; frame2:
R1_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2453: (67) r1 <<= 8                   ; frame2:
R1_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2454: (71) r4 = *(u8 *)(r10 -7)       ; frame2:
R4_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2455: (4f) r1 |= r4                   ; frame2: R1_w=Pscalar()
R4_w=Pscalar(umax=255,var_off=(0x0; 0xff))
BPF: 2456: (71) r3 = *(u8 *)(r10 -6)       ; frame2:
R3_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2457: (67) r3 <<= 8                   ; frame2:
R3_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2458: (71) r5 = *(u8 *)(r10 -5)       ; frame2:
R5_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2459: (4f) r3 |= r5                   ; frame2: R3_w=Pscalar()
R5_w=Pscalar(umax=255,var_off=(0x0; 0xff))
BPF: 2460: (71) r4 = *(u8 *)(r10 -4)       ; frame2:
R4_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2461: (67) r4 <<= 8                   ; frame2:
R4_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2462: (71) r2 = *(u8 *)(r10 -3)       ; frame2:
R2_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2463: (4f) r4 |= r2                   ; frame2:
R2_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R4_w=Pscalar()
BPF: 2464: (71) r5 = *(u8 *)(r10 -2)       ; frame2:
R5_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2465: (67) r5 <<= 8                   ; frame2:
R5_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2466: (71) r7 = *(u8 *)(r10 -1)       ; frame2:
R7_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2467: (4f) r5 |= r7                   ; frame2: R5_w=Pscalar()
R7_w=Pscalar(umax=255,var_off=(0x0; 0xff))
BPF: 2468: (71) r2 = *(u8 *)(r10 -16)      ; frame2:
R2_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2469: (64) w2 <<= 8                   ; frame2:
R2_w=Pscalar(umax=65280,var_off=(0x0; 0xff00))
BPF: 2470: (71) r7 = *(u8 *)(r10 -15)      ; frame2:
R7_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0
BPF: 2471: (73) *(u8 *)(r10 -20) = r7      ; frame2:
R7_w=Pscalar(umax=255,var_off=(0x0; 0xff)) R10=fp0 fp-24=???m????
BPF: 2472: (61) r7 = *(u32 *)(r10 -20)
BPF: invalid read from stack off -20+1 size 4
BPF: verification time 75240 usec
BPF: stack depth 96+16+0+0+96+0+0+40+0+0
BPF: processed 27048 insns (limit 1000000) max_states_per_insn 33 total_states
2418 peak_states 2318 mark_read 131

The core issue is seen in instructions 2471 and 2472, where an 8-bit value is
stored on the stack but we try to read a 32-bit value from the stack.  That is
flagged as a BPF verifier error because we end up reading uninitialized data
from the stack which is a no-no in BPF land.

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[jemarch at gcc dot gnu.org]

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

Jose E. Marchesi <jemarch at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jemarch at gcc dot gnu.org
           Assignee|unassigned at gcc dot gnu.org      |jemarch at gcc dot gnu.org

--- Comment #1 from Jose E. Marchesi <jemarch at gcc dot gnu.org> ---
Can you please provide a pre-processed version of the reproducer?
Thanks.

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[kris.van.hees at oracle dot com]

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

--- Comment #2 from Kris Van Hees <kris.van.hees at oracle dot com> ---
Created attachment 55536
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=55536&action=edit
Pre-processed source file

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[jemarch at gcc dot gnu.org]

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

Jose E. Marchesi <jemarch at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-07-13
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED

--- Comment #3 from Jose E. Marchesi <jemarch at gcc dot gnu.org> ---
Thanks.

Confirmed with master bpf-unknown-gcc:

        stxb    [%fp+-20],%r7
        ldxw    %r7,[%fp+-20]

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[jemarch at gcc dot gnu.org]

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

--- Comment #4 from Jose E. Marchesi <jemarch at gcc dot gnu.org> ---
Looks like `combine' is generating paradoxical subregs of mems, which seem to
confuse LRA and these weird incorrect reloads end up being generated.  The
easiest fix for this is to make the backend to use the instruction scheduler,
which makes `combine' to not generate such subregs.

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jose E. Marchesi <jemarch@gcc.gnu.org>:

https://gcc.gnu.org/g:53d12ecd624ec901d8449cfa1917f6f90e910927

commit r14-2522-g53d12ecd624ec901d8449cfa1917f6f90e910927
Author: Jose E. Marchesi <jose.marchesi@oracle.com>
Date:   Fri Jul 14 13:54:06 2023 +0200

    bpf: enable instruction scheduling

    This patch adds a dummy FSM to bpf.md in order to get INSN_SCHEDULING
    defined.  If the later is not defined, the `combine' pass generates
    paradoxical subregs of mems, which seems to then be mishandled by LRA,
    resulting in invalid code.

    Tested in bpf-unknown-none.

    gcc/ChangeLog:

    2023-07-14  Jose E. Marchesi  <jose.marchesi@oracle.com>

            PR target/110657
            * config/bpf/bpf.md: Enable instruction scheduling.

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[jemarch at gcc dot gnu.org]

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

--- Comment #6 from Jose E. Marchesi <jemarch at gcc dot gnu.org> ---
Hello Kris.

The commit above (now in gcc master) should fix the issue.  Can you please
confirm?

Thanks!

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[kris.van.hees at oracle dot com]

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

--- Comment #7 from Kris Van Hees <kris.van.hees at oracle dot com> ---
Confirmed that it resolves the issue

Thanks!

[Bug target/110657] BPF verifier rejects generated code due to invalid stack access

[jemarch at gcc dot gnu.org]

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

Jose E. Marchesi <jemarch at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #8 from Jose E. Marchesi <jemarch at gcc dot gnu.org> ---
Thanks for confirming.  Resolving as fixed.