<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/61874>61874</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            bpf: verifier fails, because clang generates a 32-bit zero extension (<<=32, >>=32) on pkt_end pointer when branching is too complex
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          gentoo-root
      </td>
    </tr>
</table>

<pre>
    A standard primitive in network BPF programs is checking that `data + expected_length <= data_end`, bailing out if this condition doesn't hold. For example, [revalidate_data in Cilium](https://github.com/cilium/cilium/blob/5d4504b18b32923cc054bd38bf118ccd859488dc/bpf/lib/common.h#L175-L198) checks that the packet is long enough to contain L2 and L3 headers.

The issue happens when revalidate_data is called multiple times within a complex graph of branching. [Attached](https://github.com/llvm/llvm-project/files/11122783/custom.txt) is the minimal example of reproduction. Every part seems to be important: putting the body of the inline function lb4_extract_tuple directly into handle_ipv4 produces good bytecode, removing seemingly useless conditions that never happen (`ret == TC_ACT_SHOT` or `ret == TC_ACT_REDIRECT`) also produces good bytecode, but the whole thing together produces buggy bytecode.

Compilation and testing command line:

```
$ clang -O2 -g -target bpf -std=gnu99 -nostdinc -Wall -Wextra -Werror -c custom.c -o custom.o
# bpftool prog load custom.o /sys/fs/bpf/test type sk_skb
# rm -v /sys/fs/bpf/test
```

Verifier output:

```
libbpf: prog 'tail_handle_ipv4_from_netdev': BPF program load failed: Permission denied
libbpf: prog 'tail_handle_ipv4_from_netdev': -- BEGIN PROG LOAD LOG --
0: R1=ctx(off=0,imm=0) R10=fp0
; int tail_handle_ipv4_from_netdev(struct __sk_buff *ctx)
0: (bf) r6 = r1 ; R1=ctx(off=0,imm=0) R6_w=ctx(off=0,imm=0)
1: (18) r0 = 0xffffff7a               ; R0_w=4294967162
; return (void *)(unsigned long)ctx->data_end;
3: (61) r2 = *(u32 *)(r6 +80)         ; R2_w=pkt_end(off=0,imm=0) R6_w=ctx(off=0,imm=0)
; return (void *)(unsigned long)ctx->data;
4: (61) r1 = *(u32 *)(r6 +76)         ; R1_w=pkt(off=0,r=0,imm=0) R6_w=ctx(off=0,imm=0)
; if (data + tot_len > data_end)
5: (bf) r3 = r1                       ; R1_w=pkt(off=0,r=0,imm=0) R3_w=pkt(off=0,r=0,imm=0)
6: (07) r3 += 34 ; R3_w=pkt(off=34,r=0,imm=0)
; if (data + tot_len > data_end)
7: (2d) if r3 > r2 goto pc+49         ; R2_w=pkt_end(off=0,imm=0) R3_w=pkt(off=34,r=34,imm=0)
; if (!(ctx->tc_index & TC_INDEX_F_SKIP_NODEPORT)) {
8: (61) r4 = *(u32 *)(r6 +44)         ; R4_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6_w=ctx(off=0,imm=0)
; if (!(ctx->tc_index & TC_INDEX_F_SKIP_NODEPORT)) {
9: (57) r4 &= 4                       ; R4_w=scalar(umax=4,var_off=(0x0; 0x4))
10: (bf) r3 = r1                      ; R1_w=pkt(off=0,r=34,imm=0) R3_w=pkt(off=0,r=34,imm=0)
; if (!(ctx->tc_index & TC_INDEX_F_SKIP_NODEPORT)) {
11: (55) if r4 != 0x0 goto pc+35 47: R0_w=4294967162 R1_w=pkt(off=0,r=34,imm=0) R2_w=pkt_end(off=0,imm=0) R3_w=pkt(off=0,r=34,imm=0) R4_w=scalar(umax=4,var_off=(0x0; 0x4)) R6_w=ctx(off=0,imm=0) R10=fp0
; if (data + tot_len > data_end)
47: (07) r3 += 34                     ; R3_w=pkt(off=34,r=34,imm=0)
; 
48: (2d) if r3 > r2 goto pc+8         ; R2_w=pkt_end(off=0,imm=0) R3_w=pkt(off=34,r=34,imm=0)
; return (void *)(unsigned long)ctx->data_end;
49: (67) r2 <<= 32
R2 pointer arithmetic on pkt_end prohibited
processed 45 insns (limit 1000000) max_states_per_insn 1 total_states 4 peak_states 4 mark_read 2
-- END PROG LOAD LOG --
libbpf: prog 'tail_handle_ipv4_from_netdev': failed to load: -13
libbpf: failed to load object '/home/max/projects/cilium/cilium/bpf/tests/custom.o'
Error: failed to load object file
```

As can be observed with [godbolt](https://godbolt.org/z/4hd48csPW), clang generated the following transformation on pkt and pkt_end pointers (ctx->data and ctx->data_end) for one of revalidate_data calls:

```
        r2 <<= 32
        r2 >>= 32
        r1 <<= 32
        r1 >>= 32
```

The other revalidate_data calls don't have this zero-extension sequence, but the one that produces it fails to pass the verifier.

A similar issue has been reported recently (#59908, where this pattern of bitshifts was produced under other circumstances), but my case is more severe, because these useless instructions also make the verifier reject the program.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJy8WF9vozoW_zTuy1EqMCSBhz60TTI72mpa9VY7-4YMPoC3xmZtk6b3069sSNrMtJnbjvaiKIFgn3_-nWP_DrNWNArxgsyvyHx1xgbXanPRoHJaz4zW7qzU_PniEqxjijPDoTeiE05sEYQChe5Jm0e4uttAb3RjWGdBWKharB6FasC1zAFZRJw5BoReAe56rBzyQqJqXAskuSbJCvz7AhUni4jQayiZkH66HhyIGlzrZWrFhRNaAddoFaFLB62W_Bw22gDuWNdL9JPJ_MrglknBmcMiaBYKroUUQ0fmK0Kz1rnekuSS0A2hm0a4dijPK90RuqnGYa9uSqlLQjdzns6jtIyzMqE5TaoqmqclT7KyjuOsqng2z9Ms45Wf0deEbqTw0yrddVqdt4QmN_FyPruJ84zQfIyQHePjWoSeVY_ofOykVg2g0kPTgtPebceEghsKTHG4SaBFxtHYcxKtSHQ5fj-0CMLaAaFlfY_KwlOLCn6Kg4WKSYkcukE60UsEJzq08CRcKxQwqLQP4w4aw_oWdA2lYapqhWrOfWAvnWNVi_yXcZRyu_-Z9Ub_BytH6KYWEi2hmziOKV1miQ_QYJ3uzt3O-bAIG6LRCSU6Jver6u0w2BvNh8oj4BzWWzTP0DPjwCJ21keqRBBdr41jypHkEvrBuRGDCB7FXoq_F0oKhVAPKggDWaYF7pxhlSvc4NVxYbBy8hmEchpaprjEQvTbFEYb0EKjNYfy2WGleUCdwU5vvTpvj1CNfIbBokT7CrnTeivcopkWCgjNyCIy6IAkK58KD9fF5fVD8cc_bh_IIgJt4M339-vV1_v19UPImByYtPqEdeUwwuyp1X7N2xAX3aBr0bxMK4emeT7MOwLYte56IVkImMehQxuC6_Htn31IPRJeTfGWjZ_xkaZQSaYamN1SmDUwc8w06KDsa5hZx0myatSQ5zBT2jouVAWz70xKmH0Py-N_jdEGZhVMqKlgpvf3eq8m8RKd1jKUJJCa8cMYIHRjnz0Ea3vIVO8LuOcewT4W9rF8EWQ6mG3fnfO2m-H7X2hELdD4CtYP7nRkpCi9UA9Zb7CvbEzI4hXuitrorlDoOG4JXfqhr0ru6GLNhETuX92h6YS1oVSiEsh_Q81sBlfrL1-_wd397Re4ub1cwc3tF5jNRpmRH3Mfk2RVuR2hma5rkqx8DRddN97lcB9HJFnV_T5CyZVPLDitPbPODJWDorCPRTnUNRB6GZTkr1QTmpW112EWPj_AxODF_9KiRfF0csSoIp5UxKFkmyioiHZ1uJYMjq-gOAqCU5qn-WIZL-iLywbdYEK-b7Xg3huvh2aDCnswD4Wf0LxyuxlJ1ocdMbkaZSSTMYs4GEODMUFKNiT0RZ6PBL3Kgp9HptFgWv_ogtjfi8wnHTo4kx47E592Zrn4yZl478yRmea3HBIeY9nhqOK086cUIMn65XyyHz8_Rl-yR9_b1wdNTv7iyNGUxWRKtNybQq-8NUk66v1ZWpKeEPfRSCwn9ZSHDbweg7H2CG2009BXhF6ln8LiCcvDzfumExoTmk3Ic1UhFMcdELrw2-fXb6v1v4tN8cc_v94V325X67vb-4eAtxzIckJodozQ9DRC0_QnhKbBeFsxyYyf1LHdS2Wg-ZzQ6y0zxeiXX75d5Ofty0tdTxZ9GMC_73s--T5f7n2nC-9-egre7_j7rpvpqHWqtNFH8ukX6fQDNk7l0_8dRvF-D5nP9-nhwxmPO0n0KkWSOaQhl37aQz7k62cz612Bn1zXX-P2zXPBBwpPuny_8L2Lms-UlEld9lcKXfZ31bnfPU6k-yRfLA_nieuJjSfTseWeQq-FcmiAGeHaDp2oQCuYHPIHyVaUwu2PmL3RFVqLHNI5CGWV9Rqk6ISDOAqXV9axXWEdc2iLHk3hB0LsF5vJ6X9IoUf2-PLUMfNYGGQcJttmM1h_W71zLP3UUXc8QHsm6c_T4fAbJz_KOx4EuvTM1isgdNPqDgnd-AShm4n02rd7CgcOYV8osPZSgrq1pznva_Ms-gT3uPQkX3k6rEuLZos80HtP3xvNSy3dm-x9fHWuTUPo5k9CN2nL06yyd98DsK4n8tagQsOct6pFqLWU-imwScOUrbXpRo44giRQxQNYRigFSLxCZRjzI0ppDrU2oNXE_Y_bGBWT0p7mVPssfBPXRy_X4fPGy_jUzPiNmW-uxkOLoAPNftML4HpqZbEtjo2uP9HoGe4cqkDhLP53QFUd0Xgfl9BKOFB34QJYQiOkZ3Zso2wnFnrE5C_Bik5IZg4NIwslhmZRr41fWIMVKiefxx0wmed5lHntTy2aycaeOYdGhQaRcLYVtbPwxOzeIA6D4p7-Bs8rYaqhs46pCu2EJu9K9wwVswjCQqcNgsUtmtFRrNhgvTK0eGikCDWSwtBKCR2Pjj3ikatgMORI6KmN9Pj8jF8kPE9ydoYX8SKL6DJJ6PKsvajykkZ1Mq_LLJ8j8jor0zRm1bJmKc9pfiYuaESTKEniOE3mdHleUsZ4lEaLOaWcZRlJI-yYkOdSbjufO2chqBeLOFumZ5KVKO2-uWouQjesHBpL0kgK6-zLNCecxIupyBycCUv6Oh7HOWiBQUJnpXABNPACGr9ye_AmNHRF93D1j_lREZ9KfOgYHtp9oRWn9b4heDYYefHhfl8Ihi9xIR7_CwAA___uwpqH">