On Thu, Apr 11, 2024 at 8:24 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

From: Xu Kuohai xukuohai@huawei.com

Add macro LSM_RET_INT to annotate lsm hook return integer type and the default return value, and the expected return range.

The LSM_RET_INT is declared as:

LSM_RET_INT(defval, min, max)

where

• defval is the default return value

• min and max indicate the expected return range is [min, max]

The return value range for each lsm hook is taken from the description in security/security.c.

The expanded result of LSM_RET_INT is not changed, and the compiled product is not changed.

Signed-off-by: Xu Kuohai xukuohai@huawei.com

include/linux/lsm_hook_defs.h | 591 +++++++++++++++++----------------- include/linux/lsm_hooks.h | 6 - kernel/bpf/bpf_lsm.c | 10 + security/security.c | 1 + 4 files changed, 313 insertions(+), 295 deletions(-)

...

diff --git a/include/linux/lsm_hook_defs.h b/include/linux/lsm_hook_defs.h index 334e00efbde4..708f515ffbf3 100644 --- a/include/linux/lsm_hook_defs.h +++ b/include/linux/lsm_hook_defs.h @@ -18,435 +18,448 @@

• The macro LSM_HOOK is used to define the data structures required by
• the LSM framework using the pattern:

• • LSM_HOOK(<return_type>, <default_value>, <hook_name>, args...)
    

• • LSM_HOOK(<return_type>, <return_description>, <hook_name>, args...)
    

  • struct security_hook_heads {

• • #define LSM_HOOK(RET, DEFAULT, NAME, ...) struct hlist_head NAME;

• • #define LSM_HOOK(RET, RETVAL_DESC, NAME, ...) struct hlist_head NAME;
  • #include <linux/lsm_hook_defs.h>
  • #undef LSM_HOOK
  • };
  */

-LSM_HOOK(int, 0, binder_set_context_mgr, const struct cred *mgr) -LSM_HOOK(int, 0, binder_transaction, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_set_context_mgr, const struct cred *mgr) +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transaction, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_binder, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_binder, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_file, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_file, const struct cred *from, const struct cred *to, const struct file *file)

I'm not overly excited about injecting these additional return value range annotations into the LSM hook definitions, especially since the vast majority of the hooks "returns 0 on success, negative values on error". I'd rather see some effort put into looking at the feasibility of converting some (all?) of the LSM hook return value exceptions into the more conventional 0/-ERRNO format. Unfortunately, I haven't had the time to look into that myself, but if you wanted to do that I think it would be a good thing.

On Sat, Jun 8, 2024 at 1:04 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

On 6/7/2024 5:53 AM, Paul Moore wrote:

...

On Thu, Apr 11, 2024 at 8:24 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

From: Xu Kuohai xukuohai@huawei.com

Add macro LSM_RET_INT to annotate lsm hook return integer type and the default return value, and the expected return range.

The LSM_RET_INT is declared as:

LSM_RET_INT(defval, min, max)

where

• defval is the default return value

• min and max indicate the expected return range is [min, max]

The return value range for each lsm hook is taken from the description in security/security.c.

The expanded result of LSM_RET_INT is not changed, and the compiled product is not changed.

Signed-off-by: Xu Kuohai xukuohai@huawei.com

include/linux/lsm_hook_defs.h | 591 +++++++++++++++++----------------- include/linux/lsm_hooks.h | 6 - kernel/bpf/bpf_lsm.c | 10 + security/security.c | 1 + 4 files changed, 313 insertions(+), 295 deletions(-)

...

...

diff --git a/include/linux/lsm_hook_defs.h b/include/linux/lsm_hook_defs.h index 334e00efbde4..708f515ffbf3 100644 --- a/include/linux/lsm_hook_defs.h +++ b/include/linux/lsm_hook_defs.h @@ -18,435 +18,448 @@

• The macro LSM_HOOK is used to define the data structures required by
• the LSM framework using the pattern:

• • LSM_HOOK(<return_type>, <default_value>, <hook_name>, args...)
    

• • LSM_HOOK(<return_type>, <return_description>, <hook_name>, args...)
    

  • struct security_hook_heads {

• • #define LSM_HOOK(RET, DEFAULT, NAME, ...) struct hlist_head NAME;

• • #define LSM_HOOK(RET, RETVAL_DESC, NAME, ...) struct hlist_head NAME;
  • #include <linux/lsm_hook_defs.h>
  • #undef LSM_HOOK
  • };
  */

-LSM_HOOK(int, 0, binder_set_context_mgr, const struct cred *mgr) -LSM_HOOK(int, 0, binder_transaction, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_set_context_mgr, const struct cred *mgr) +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transaction, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_binder, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_binder, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_file, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_file, const struct cred *from, const struct cred *to, const struct file *file)

I'm not overly excited about injecting these additional return value range annotations into the LSM hook definitions, especially since the vast majority of the hooks "returns 0 on success, negative values on error". I'd rather see some effort put into looking at the feasibility of converting some (all?) of the LSM hook return value exceptions into the more conventional 0/-ERRNO format. Unfortunately, I haven't had the time to look into that myself, but if you wanted to do that I think it would be a good thing.

I agree that keeping all hooks return a consistent range of 0/-ERRNO is more elegant than adding return value range annotations. However, there are two issues that might need to be addressed first:

1. Compatibility

For instance, security_vm_enough_memory_mm() determines whether to set cap_sys_admin by checking if the hook vm_enough_memory returns a positive number. If we were to change the hook vm_enough_memory to return 0 to indicate the need for cap_sys_admin, then for the LSM BPF program currently returning 0, the interpretation of its return value would be reversed after the modification.

This is not an issue. bpf lsm progs are no different from other lsm-s. If the meaning of return value or arguments to lsm hook change all lsm-s need to adjust as well. Regardless of whether they are written as in-kernel lsm-s, bpf-lsm, or out-of-tree lsm-s.

2. Expressing multiple non-error states using 0/-ERRNO

IIUC, although 0/-ERRNO can be used to express different errors, only 0 can be used for non-error state. If there are multiple non-error states, they cannot be distinguished. For example, security_inode_need_killpriv() returns < 0 on error, 0 if security_inode_killpriv() doesn't need to be called, and > 0 if security_inode_killpriv() does need to be called.

This looks like a problem indeed. Converting all hooks to 0/-errno doesn't look practical.

On Sun, Jun 9, 2024 at 1:39 PM Casey Schaufler casey@schaufler-ca.com wrote:

On 6/8/2024 6:54 AM, Alexei Starovoitov wrote:

...

On Sat, Jun 8, 2024 at 1:04 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

On 6/7/2024 5:53 AM, Paul Moore wrote:

...

On Thu, Apr 11, 2024 at 8:24 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

From: Xu Kuohai xukuohai@huawei.com

Add macro LSM_RET_INT to annotate lsm hook return integer type and the default return value, and the expected return range.

The LSM_RET_INT is declared as:

LSM_RET_INT(defval, min, max)

where

• defval is the default return value

• min and max indicate the expected return range is [min, max]

The return value range for each lsm hook is taken from the description in security/security.c.

The expanded result of LSM_RET_INT is not changed, and the compiled product is not changed.

Signed-off-by: Xu Kuohai xukuohai@huawei.com

include/linux/lsm_hook_defs.h | 591 +++++++++++++++++----------------- include/linux/lsm_hooks.h | 6 - kernel/bpf/bpf_lsm.c | 10 + security/security.c | 1 + 4 files changed, 313 insertions(+), 295 deletions(-)

...

...

diff --git a/include/linux/lsm_hook_defs.h b/include/linux/lsm_hook_defs.h index 334e00efbde4..708f515ffbf3 100644 --- a/include/linux/lsm_hook_defs.h +++ b/include/linux/lsm_hook_defs.h @@ -18,435 +18,448 @@

• The macro LSM_HOOK is used to define the data structures required by
• the LSM framework using the pattern:

• • LSM_HOOK(<return_type>, <default_value>, <hook_name>, args...)
    

• • LSM_HOOK(<return_type>, <return_description>, <hook_name>, args...)
    

  • struct security_hook_heads {

• • #define LSM_HOOK(RET, DEFAULT, NAME, ...) struct hlist_head NAME;

• • #define LSM_HOOK(RET, RETVAL_DESC, NAME, ...) struct hlist_head NAME;
  • #include <linux/lsm_hook_defs.h>
  • #undef LSM_HOOK
  • };
  */

-LSM_HOOK(int, 0, binder_set_context_mgr, const struct cred *mgr) -LSM_HOOK(int, 0, binder_transaction, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_set_context_mgr, const struct cred *mgr) +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transaction, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_binder, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_binder, const struct cred *from, const struct cred *to) -LSM_HOOK(int, 0, binder_transfer_file, const struct cred *from, +LSM_HOOK(int, LSM_RET_INT(0, -MAX_ERRNO, 0), binder_transfer_file, const struct cred *from, const struct cred *to, const struct file *file)

I'm not overly excited about injecting these additional return value range annotations into the LSM hook definitions, especially since the vast majority of the hooks "returns 0 on success, negative values on error". I'd rather see some effort put into looking at the feasibility of converting some (all?) of the LSM hook return value exceptions into the more conventional 0/-ERRNO format. Unfortunately, I haven't had the time to look into that myself, but if you wanted to do that I think it would be a good thing.

I agree that keeping all hooks return a consistent range of 0/-ERRNO is more elegant than adding return value range annotations. However, there are two issues that might need to be addressed first:

1. Compatibility

For instance, security_vm_enough_memory_mm() determines whether to set cap_sys_admin by checking if the hook vm_enough_memory returns a positive number. If we were to change the hook vm_enough_memory to return 0 to indicate the need for cap_sys_admin, then for the LSM BPF program currently returning 0, the interpretation of its return value would be reversed after the modification.

This is not an issue. bpf lsm progs are no different from other lsm-s. If the meaning of return value or arguments to lsm hook change all lsm-s need to adjust as well. Regardless of whether they are written as in-kernel lsm-s, bpf-lsm, or out-of-tree lsm-s.

Yes, the are no guarantees around compatibility in kernel/LSM interface from one kernel release to the next. If we need to change a LSM hook, we can change a LSM hook; the important part is that when we change the LSM hook we must make sure to update all of the in-tree LSMs which make use of that hook.

...

...

2. Expressing multiple non-error states using 0/-ERRNO

IIUC, although 0/-ERRNO can be used to express different errors, only 0 can be used for non-error state. If there are multiple non-error states, they cannot be distinguished. For example, security_inode_need_killpriv() returns < 0 on error, 0 if security_inode_killpriv() doesn't need to be called, and > 0 if security_inode_killpriv() does need to be called.

This looks like a problem indeed.

Hang on. There aren't really three states here. security_inode_killpriv() is called only on the security_inode_need_killpriv() > 0 case. I'm not looking at the code this instant, but adjusting the return to something like -ENOSYS (OK, maybe not a great choice, but you get the idea) instead of 0 in the don't call case and switching the positive value to 0 should work just fine.

We're working on getting the LSM interfaces to be more consistent. This particular pair of hooks is an example of why we need to do that.

Yes, exactly. Aside from the issues with BPF verification, we've seen problems in the past with LSM hooks that differ from the usual "0 on success, negative values on failure" pattern. I'm not saying it is possible to convert all of the hooks to fit this model, but even if we can only adjust one or two I think that is still a win.

As far as security_inode_need_killpriv()/security_inode_killpriv() is concerned, one possibility would be to shift the ATTR_KILL_PRIV set/mask operation into the LSM hook, something like this:

[WARNING: completely untested, likely broken, yadda yadda]

/** * ... * Returns: Return 0 on success, negative values on failure. @attrs may be updated * on success. */ int security_inode_need_killpriv(*dentry, attrs) { int rc; rc = call_int_hook(inode_killpriv, dentry); if (rc < 0) return rc; if (rc > 0) attrs |= ATTR_KILL_PRIV; else if (rc == 0) attrs &= ~ATTR_KILL_PRIV; return 0; }

Yes, that doesn't fix the problem for the individual LSMs, but it does make the hook a bit more consistent from the rest of the kernel.

On Thu, Apr 11, 2024 at 5:24 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

From: Xu Kuohai xukuohai@huawei.com

After checking lsm hook return range in verifier, the test case "test_progs -t test_lsm" failed, and the failure log says:

libbpf: prog 'test_int_hook': BPF program load failed: Invalid argument libbpf: prog 'test_int_hook': -- BEGIN PROG LOAD LOG -- 0: R1=ctx() R10=fp0 ; int BPF_PROG(test_int_hook, struct vm_area_struct *vma, @ lsm.c:89 0: (79) r0 = *(u64 *)(r1 +24) ; R0_w=scalar(smin=smin32=-4095,smax=smax32=0) R1=ctx()

[...]

24: (b4) w0 = -1 ; R0_w=0xffffffff ; int BPF_PROG(test_int_hook, struct vm_area_struct *vma, @ lsm.c:89 25: (95) exit At program exit the register R0 has smin=4294967295 smax=4294967295 should have been in [-4095, 0]

It can be seen that instruction "w0 = -1" zero extended -1 to 64-bit register r0, setting both smin and smax values of r0 to 4294967295. This resulted in a false reject when r0 was checked with range [-4095, 0].

Given bpf_retval_range is a 32-bit range, this patch fixes it by changing the compare between r0 and return range from 64-bit operation to 32-bit operation.

Fixes: 8fa4ecd49b81 ("bpf: enforce exact retval range on subprog/callback exit") Signed-off-by: Xu Kuohai xukuohai@huawei.com

---

kernel/bpf/verifier.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 05c7c5f2bec0..5393d576c76f 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -9879,7 +9879,7 @@ static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)

static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg) {

•   return range.minval <= reg->smin_value && reg->smax_value <= range.maxval;
  

•   return range.minval <= reg->s32_min_value && reg->s32_max_value <= range.maxval;
  

are all BPF programs treated as if they return int instead of long? If not, we probably should have a bool flag in bpf_retval_range whether comparison should be 32-bit or 64-bit?

}

static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx)

2.30.2

On 4/24/2024 5:55 AM, Yonghong Song wrote:

On 4/20/24 1:33 AM, Xu Kuohai wrote:

...

On 4/20/2024 7:00 AM, Eduard Zingerman wrote:

...

On Thu, 2024-04-11 at 20:27 +0800, Xu Kuohai wrote:

...

From: Xu Kuohai xukuohai@huawei.com

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    0: (b7) r0 = 0                        ; R0_w=0    1: (79) r2 = *(u64 *)(r1 +0)    func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'    2: R1=ctx() R2_w=trusted_ptr_bpf_map()    ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29    2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4)    4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx()    ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32    6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))    7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)    ;  @ test_libbpf_get_fd_by_id_opts.c:0    8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    9: (95) exit

And here is the C code of the prog.

SEC("lsm/bpf_map") int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) {     if (map != (struct bpf_map *)&data_input)         return 0;

if (fmode & FMODE_WRITE)         return -EACCES;

return 0; }

It is clear that the prog can only return either 0 or -EACCESS, and both values are legal.

So why is it rejected by the verifier?

The verifier log shows that the second if and return value setting statements in the prog is optimized to bitwise operations "r0 s>>= 63" and "r0 &= -13". The verifier correctly deduces that the the value of r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63". But when the verifier proceeds to verify instruction "r0 &= -13", it fails to deduce the correct value range of r0.

7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) 8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))

So why the verifier fails to deduce the result of 'r0 &= -13'?

The verifier uses tnum to track values, and the two ranges "[-1, 0]" and "[0, -1ULL]" are encoded to the same tnum. When verifing instruction "r0 &= -13", the verifier erroneously deduces the result from "[0, -1ULL] AND -13", which is out of the expected return range [-4095, 0].

To fix it, this patch simply adds a special SCALAR32 case for the verifier. That is, when the source operand of the AND instruction is a constant and the destination operand changes from negative to non-negative and falls in range [-256, 256], deduce the result range by enumerating all possible AND results.

Signed-off-by: Xu Kuohai xukuohai@huawei.com

Hello,

Sorry for the delay, I had to think about this issue a bit. I found the clang transformation that generates the pattern this patch tries to handle. It is located in DAGCombiner::SimplifySelectCC() method (see [1]). The transformation happens as a part of DAG to DAG rewrites (LLVM uses several internal representations:   - generic optimizer uses LLVM IR, most of the work is done     using this representation;   - before instruction selection IR is converted to Selection DAG,     some optimizations are applied at this stage,     all such optimizations are a set of pattern replacements;   - Selection DAG is converted to machine code, some optimizations     are applied at the machine code level).

Full pattern is described as follows:

// fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A)    // where y is has a single bit set.    // A plaintext description would be, we can turn the SELECT_CC into an AND    // when the condition can be materialized as an all-ones register.  Any    // single bit-test can be materialized as an all-ones register with    // shift-left and shift-right-arith.

For this particular test case the DAG is converted as follows:

.---------------- lhs         The meaning of this select_cc is:                      |        .------- rhs         `lhs == rhs ? true value : false value`                      |        | .----- true value                      |        | |  .-- false value                      v        v v  v    (select_cc seteq (and X 2) 0 0 -13)                            ^ ->                        '---------------.    (and (sra (sll X 62) 63)                |         -13)                               |                                            | Before pattern is applied, it checks that second 'and' operand has only one bit set, (which is true for '2').

The pattern itself generates logical shift left / arithmetic shift right pair, that ensures that result is either all ones (-1) or all zeros (0). Hence, applying 'and' to shifts result and false value generates a correct result.

Thanks for your detailed and invaluable explanation!

Thanks Eduard for detailed explanation. It looks like we could resolve this issue without adding too much complexity to verifier. Also, this code pattern above seems generic enough to be worthwhile with verifier change.

Kuohai, please added detailed explanation (as described by Eduard) in the commit message.

Sure, already added, the commit message and the change now is like this:

---

bpf: Fix a false rejection caused by AND operation

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0 ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 0: (b7) r0 = 0 ; R0_w=0 1: (79) r2 = *(u64 *)(r1 +0) func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map' 2: R1=ctx() R2_w=trusted_ptr_bpf_map() ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29 2: (18) r3 = 0xffff9742c0951a00 ; R3_w=map_ptr(map=data_input,ks=4,vs=4) 4: (5d) if r2 != r3 goto pc+4 ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4) ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 5: (79) r0 = *(u64 *)(r1 +8) ; R0_w=scalar() R1=ctx() ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32 6: (67) r0 <<= 62 ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000)) 7: (c7) r0 s>>= 63 ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) ; @ test_libbpf_get_fd_by_id_opts.c:0 8: (57) r0 &= -13 ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 9: (95) exit

And here is the C code of the prog.

SEC("lsm/bpf_map") int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) { if (map != (struct bpf_map *)&data_input) return 0;

if (fmode & FMODE_WRITE) return -EACCES;

return 0; }

It is clear that the prog can only return either 0 or -EACCESS, and both values are legal.

So why is it rejected by the verifier?

The verifier log shows that the second if and return value setting statements in the prog is optimized to bitwise operations "r0 s>>= 63" and "r0 &= -13". The verifier correctly deduces that the the value of r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63". But when the verifier proceeds to verify instruction "r0 &= -13", it fails to deduce the correct value range of r0.

7: (c7) r0 s>>= 63 ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) 8: (57) r0 &= -13 ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))

So why the verifier fails to deduce the result of 'r0 &= -13'?

The verifier uses tnum to track values, and the two ranges "[-1, 0]" and "[0, -1ULL]" are encoded to the same tnum. When verifing instruction "r0 &= -13", the verifier erroneously deduces the result from "[0, -1ULL] AND -13", which is out of the expected return range [-4095, 0].

As explained by Eduard in [0], the clang transformation that generates this pattern is located in DAGCombiner::SimplifySelectCC() method (see [1]).

The transformation happens as a part of DAG to DAG rewrites (LLVM uses several internal representations: - generic optimizer uses LLVM IR, most of the work is done using this representation; - before instruction selection IR is converted to Selection DAG, some optimizations are applied at this stage, all such optimizations are a set of pattern replacements; - Selection DAG is converted to machine code, some optimizations are applied at the machine code level).

Full pattern is described as follows:

// fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A) // where y is has a single bit set. // A plaintext description would be, we can turn the SELECT_CC into an AND // when the condition can be materialized as an all-ones register. Any // single bit-test can be materialized as an all-ones register with // shift-left and shift-right-arith.

For this particular test case the DAG is converted as follows:

.---------------- lhs The meaning of this select_cc is: | .------- rhs `lhs == rhs ? true value : false value` | | .----- true value | | | .-- false value v v v v (select_cc seteq (and X 2) 0 0 -13) ^ -> '---------------. (and (sra (sll X 62) 63) | -13) | | Before pattern is applied, it checks that second 'and' operand has only one bit set, (which is true for '2').

The pattern itself generates logical shift left / arithmetic shift right pair, that ensures that result is either all ones (-1) or all zeros (0). Hence, applying 'and' to shifts result and false value generates a correct result.

As suggested by Eduard, this patch makes a special case for source or destination register of '&=' operation being in range [-1, 0].

Meaning that one of the '&=' operands is either: - all ones, in which case the counterpart is the result of the operation; - all zeros, in which case zero is the result of the operation.

And MIN and MAX values could be derived based on above two observations.

[0] https://lore.kernel.org/bpf/e62e2971301ca7f2e9eb74fc500c520285cad8f5.camel@g... [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985...

Suggested-by: Eduard Zingerman eddyz87@gmail.com Signed-off-by: Xu Kuohai xukuohai@huawei.com

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 640747b53745..30c551d39329 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13374,6 +13374,24 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, dst_reg->u32_min_value = var32_off.value; dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);

+ /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ + if (src_known && + dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0 && + dst_reg->smin_value == -1 && dst_reg->smax_value == 0) { + dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0); + dst_reg->s32_max_value = max_t(s32, src_reg->s32_min_value, 0); + return; + } + + /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ + if (dst_known && + src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0 && + src_reg->smin_value == -1 && src_reg->smax_value == 0) { + dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0); + dst_reg->s32_max_value = max_t(s32, dst_reg->s32_min_value, 0); + return; + } + /* Safe to set s32 bounds by casting u32 result into s32 when u32 * doesn't cross sign boundary. Otherwise set s32 bounds to unbounded. */ @@ -13404,6 +13422,24 @@ static void scalar_min_max_and(struct bpf_reg_state *dst_reg, dst_reg->umin_value = dst_reg->var_off.value; dst_reg->umax_value = min(dst_reg->umax_value, umax_val);

+ /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ + if (src_known && + dst_reg->smin_value == -1 && dst_reg->smax_value == 0 && + dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) { + dst_reg->smin_value = min_t(s64, src_reg->smin_value, 0); + dst_reg->smax_value = max_t(s64, src_reg->smin_value, 0); + return; + } + + /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ + if (dst_known && + src_reg->smin_value == -1 && src_reg->smax_value == 0 && + src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) { + dst_reg->smin_value = min_t(s64, dst_reg->smin_value, 0); + dst_reg->smax_value = max_t(s64, dst_reg->smin_value, 0); + return; + } + /* Safe to set s64 bounds by casting u64 result into s64 when u64 * doesn't cross sign boundary. Otherwise set s64 bounds to unbounded. */

...

...

In my opinion the approach taken by this patch is sub-optimal:

• 512 iterations is too much;
• this does not cover all code that could be generated by the above

mentioned LLVM transformation    (e.g. second 'and' operand could be 1 << 16).

Instead, I suggest to make a special case for source or dst register of '&=' operation being in range [-1,0]. Meaning that one of the '&=' operands is either:

• all ones, in which case the counterpart is the result of the operation;
• all zeros, in which case zero is the result of the operation;
• derive MIN and MAX values based on above two observations.

Totally agree, I'll cook a new patch as you suggested.

...

[1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985...

Best regards, Eduard

On 4/25/2024 6:06 AM, Yonghong Song wrote:

On 4/23/24 7:25 PM, Xu Kuohai wrote:

...

On 4/24/2024 5:55 AM, Yonghong Song wrote:

...

On 4/20/24 1:33 AM, Xu Kuohai wrote:

...

On 4/20/2024 7:00 AM, Eduard Zingerman wrote:

...

On Thu, 2024-04-11 at 20:27 +0800, Xu Kuohai wrote:

...

From: Xu Kuohai xukuohai@huawei.com

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    0: (b7) r0 = 0                        ; R0_w=0    1: (79) r2 = *(u64 *)(r1 +0)    func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'    2: R1=ctx() R2_w=trusted_ptr_bpf_map()    ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29    2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4)    4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx()    ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32    6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))    7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)    ;  @ test_libbpf_get_fd_by_id_opts.c:0    8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27    9: (95) exit

And here is the C code of the prog.

SEC("lsm/bpf_map") int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) {     if (map != (struct bpf_map *)&data_input)         return 0;

if (fmode & FMODE_WRITE)         return -EACCES;

return 0; }

It is clear that the prog can only return either 0 or -EACCESS, and both values are legal.

So why is it rejected by the verifier?

The verifier log shows that the second if and return value setting statements in the prog is optimized to bitwise operations "r0 s>>= 63" and "r0 &= -13". The verifier correctly deduces that the the value of r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63". But when the verifier proceeds to verify instruction "r0 &= -13", it fails to deduce the correct value range of r0.

7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) 8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))

So why the verifier fails to deduce the result of 'r0 &= -13'?

The verifier uses tnum to track values, and the two ranges "[-1, 0]" and "[0, -1ULL]" are encoded to the same tnum. When verifing instruction "r0 &= -13", the verifier erroneously deduces the result from "[0, -1ULL] AND -13", which is out of the expected return range [-4095, 0].

To fix it, this patch simply adds a special SCALAR32 case for the verifier. That is, when the source operand of the AND instruction is a constant and the destination operand changes from negative to non-negative and falls in range [-256, 256], deduce the result range by enumerating all possible AND results.

Signed-off-by: Xu Kuohai xukuohai@huawei.com

Hello,

Sorry for the delay, I had to think about this issue a bit. I found the clang transformation that generates the pattern this patch tries to handle. It is located in DAGCombiner::SimplifySelectCC() method (see [1]). The transformation happens as a part of DAG to DAG rewrites (LLVM uses several internal representations:   - generic optimizer uses LLVM IR, most of the work is done     using this representation;   - before instruction selection IR is converted to Selection DAG,     some optimizations are applied at this stage,     all such optimizations are a set of pattern replacements;   - Selection DAG is converted to machine code, some optimizations     are applied at the machine code level).

Full pattern is described as follows:

// fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A)    // where y is has a single bit set.    // A plaintext description would be, we can turn the SELECT_CC into an AND    // when the condition can be materialized as an all-ones register.  Any    // single bit-test can be materialized as an all-ones register with    // shift-left and shift-right-arith.

For this particular test case the DAG is converted as follows:

.---------------- lhs         The meaning of this select_cc is:                      |        .------- rhs         `lhs == rhs ? true value : false value`                      |        | .----- true value                      |        | |  .-- false value                      v        v v  v    (select_cc seteq (and X 2) 0 0 -13)                            ^ ->                        '---------------.    (and (sra (sll X 62) 63)                |         -13)                               |                                            | Before pattern is applied, it checks that second 'and' operand has only one bit set, (which is true for '2').

The pattern itself generates logical shift left / arithmetic shift right pair, that ensures that result is either all ones (-1) or all zeros (0). Hence, applying 'and' to shifts result and false value generates a correct result.

Thanks for your detailed and invaluable explanation!

Thanks Eduard for detailed explanation. It looks like we could resolve this issue without adding too much complexity to verifier. Also, this code pattern above seems generic enough to be worthwhile with verifier change.

Kuohai, please added detailed explanation (as described by Eduard) in the commit message.

Sure, already added, the commit message and the change now is like this:

---

bpf: Fix a false rejection caused by AND operation

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts     is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     0: (b7) r0 = 0                        ; R0_w=0     1: (79) r2 = *(u64 *)(r1 +0)     func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'     2: R1=ctx() R2_w=trusted_ptr_bpf_map()     ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29     2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4)     4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx()     ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32     6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))     7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)     ;  @ test_libbpf_get_fd_by_id_opts.c:0     8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     9: (95) exit

And here is the C code of the prog.

SEC("lsm/bpf_map")     int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode)     {         if (map != (struct bpf_map *)&data_input)                 return 0;

if (fmode & FMODE_WRITE)                 return -EACCES;

return 0;     }

It is clear that the prog can only return either 0 or -EACCESS, and both     values are legal.

So why is it rejected by the verifier?

The verifier log shows that the second if and return value setting     statements in the prog is optimized to bitwise operations "r0 s>>= 63"     and "r0 &= -13". The verifier correctly deduces that the the value of     r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63".     But when the verifier proceeds to verify instruction "r0 &= -13", it     fails to deduce the correct value range of r0.

7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)     8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))

So why the verifier fails to deduce the result of 'r0 &= -13'?

The verifier uses tnum to track values, and the two ranges "[-1, 0]" and     "[0, -1ULL]" are encoded to the same tnum. When verifing instruction     "r0 &= -13", the verifier erroneously deduces the result from     "[0, -1ULL] AND -13", which is out of the expected return range     [-4095, 0].

As explained by Eduard in [0], the clang transformation that generates this     pattern is located in DAGCombiner::SimplifySelectCC() method (see [1]).

The transformation happens as a part of DAG to DAG rewrites     (LLVM uses several internal representations:      - generic optimizer uses LLVM IR, most of the work is done        using this representation;      - before instruction selection IR is converted to Selection DAG,        some optimizations are applied at this stage,        all such optimizations are a set of pattern replacements;      - Selection DAG is converted to machine code, some optimizations        are applied at the machine code level).

Full pattern is described as follows:

// fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A)       // where y is has a single bit set.       // A plaintext description would be, we can turn the SELECT_CC into an AND       // when the condition can be materialized as an all-ones register.  Any       // single bit-test can be materialized as an all-ones register with       // shift-left and shift-right-arith.

For this particular test case the DAG is converted as follows:

.---------------- lhs         The meaning of this select_cc is:                         |        .------- rhs         `lhs == rhs ? true value : false value`                         |        | .----- true value                         |        | |  .-- false value                         v        v v  v       (select_cc seteq (and X 2) 0 0 -13)                               ^     ->                        '---------------.       (and (sra (sll X 62) 63)                |            -13)                               |                                               |     Before pattern is applied, it checks that second 'and' operand has     only one bit set, (which is true for '2').

The pattern itself generates logical shift left / arithmetic shift     right pair, that ensures that result is either all ones (-1) or all     zeros (0). Hence, applying 'and' to shifts result and false value     generates a correct result.

As suggested by Eduard, this patch makes a special case for source     or destination register of '&=' operation being in range [-1, 0].

Meaning that one of the '&=' operands is either:     - all ones, in which case the counterpart is the result of the operation;     - all zeros, in which case zero is the result of the operation.

And MIN and MAX values could be derived based on above two observations.

[0] https://lore.kernel.org/bpf/e62e2971301ca7f2e9eb74fc500c520285cad8f5.camel@g...     [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985...

Suggested-by: Eduard Zingerman eddyz87@gmail.com     Signed-off-by: Xu Kuohai xukuohai@huawei.com

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 640747b53745..30c551d39329 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13374,6 +13374,24 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg,         dst_reg->u32_min_value = var32_off.value;         dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);

+       /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ +       if (src_known && +               dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0 && +               dst_reg->smin_value == -1 && dst_reg->smax_value == 0) {

do we need to check dst_reg->smin_value/smax_value here? They should not impact final dst_reg->s32_{min,max}_value computation, right?

right, the check was simply copied from the old code, which only handled the case where 64-bit range is the same as the 32-bit range

Similarly, for later 64bit min/max and, 32bit value does not really matter.

hmm, the 32-bit check is completely unnecessary.

...

• dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);

+               dst_reg->s32_max_value = max_t(s32, src_reg->s32_min_value, 0); +               return; +       }

+       /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ +       if (dst_known && +               src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0 && +               src_reg->smin_value == -1 && src_reg->smax_value == 0) { +               dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0); +               dst_reg->s32_max_value = max_t(s32, dst_reg->s32_min_value, 0); +               return; +       }

/* Safe to set s32 bounds by casting u32 result into s32 when u32          * doesn't cross sign boundary. Otherwise set s32 bounds to unbounded.          */ @@ -13404,6 +13422,24 @@ static void scalar_min_max_and(struct bpf_reg_state *dst_reg,         dst_reg->umin_value = dst_reg->var_off.value;         dst_reg->umax_value = min(dst_reg->umax_value, umax_val);

+       /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ +       if (src_known && +               dst_reg->smin_value == -1 && dst_reg->smax_value == 0 && +               dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) { +               dst_reg->smin_value = min_t(s64, src_reg->smin_value, 0); +               dst_reg->smax_value = max_t(s64, src_reg->smin_value, 0); +               return; +       }

+       /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ +       if (dst_known && +               src_reg->smin_value == -1 && src_reg->smax_value == 0 && +               src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) { +               dst_reg->smin_value = min_t(s64, dst_reg->smin_value, 0); +               dst_reg->smax_value = max_t(s64, dst_reg->smin_value, 0); +               return; +       }

/* Safe to set s64 bounds by casting u64 result into s64 when u64          * doesn't cross sign boundary. Otherwise set s64 bounds to unbounded.          */

...

...

...

In my opinion the approach taken by this patch is sub-optimal:

• 512 iterations is too much;
• this does not cover all code that could be generated by the above

mentioned LLVM transformation    (e.g. second 'and' operand could be 1 << 16).

Instead, I suggest to make a special case for source or dst register of '&=' operation being in range [-1,0]. Meaning that one of the '&=' operands is either:

• all ones, in which case the counterpart is the result of the operation;
• all zeros, in which case zero is the result of the operation;
• derive MIN and MAX values based on above two observations.

Totally agree, I'll cook a new patch as you suggested.

...

[1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985...

Best regards, Eduard

On 4/26/2024 12:28 AM, Yonghong Song wrote:

On 4/24/24 7:42 PM, Xu Kuohai wrote:

...

On 4/25/2024 6:06 AM, Yonghong Song wrote:

...

On 4/23/24 7:25 PM, Xu Kuohai wrote:

...

On 4/24/2024 5:55 AM, Yonghong Song wrote:

...

On 4/20/24 1:33 AM, Xu Kuohai wrote:

...

On 4/20/2024 7:00 AM, Eduard Zingerman wrote: > On Thu, 2024-04-11 at 20:27 +0800, Xu Kuohai wrote: >> From: Xu Kuohai xukuohai@huawei.com >> >> With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts >> is rejected by the verifier, and the log says: >> >>    0: R1=ctx() R10=fp0 >>    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >>    0: (b7) r0 = 0                        ; R0_w=0 >>    1: (79) r2 = *(u64 *)(r1 +0) >>    func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map' >>    2: R1=ctx() R2_w=trusted_ptr_bpf_map() >>    ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29 >>    2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4) >>    4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4) >>    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >>    5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx() >>    ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32 >>    6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000)) >>    7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) >>    ;  @ test_libbpf_get_fd_by_id_opts.c:0 >>    8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) >>    ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >>    9: (95) exit >> >> And here is the C code of the prog. >> >> SEC("lsm/bpf_map") >> int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) >> { >>     if (map != (struct bpf_map *)&data_input) >>         return 0; >> >>     if (fmode & FMODE_WRITE) >>         return -EACCES; >> >>     return 0; >> } >> >> It is clear that the prog can only return either 0 or -EACCESS, and both >> values are legal. >> >> So why is it rejected by the verifier? >> >> The verifier log shows that the second if and return value setting >> statements in the prog is optimized to bitwise operations "r0 s>>= 63" >> and "r0 &= -13". The verifier correctly deduces that the the value of >> r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63". >> But when the verifier proceeds to verify instruction "r0 &= -13", it >> fails to deduce the correct value range of r0. >> >> 7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) >> 8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) >> >> So why the verifier fails to deduce the result of 'r0 &= -13'? >> >> The verifier uses tnum to track values, and the two ranges "[-1, 0]" and >> "[0, -1ULL]" are encoded to the same tnum. When verifing instruction >> "r0 &= -13", the verifier erroneously deduces the result from >> "[0, -1ULL] AND -13", which is out of the expected return range >> [-4095, 0]. >> >> To fix it, this patch simply adds a special SCALAR32 case for the >> verifier. That is, when the source operand of the AND instruction is >> a constant and the destination operand changes from negative to >> non-negative and falls in range [-256, 256], deduce the result range >> by enumerating all possible AND results. >> >> Signed-off-by: Xu Kuohai xukuohai@huawei.com >> --- > > Hello, > > Sorry for the delay, I had to think about this issue a bit. > I found the clang transformation that generates the pattern this patch > tries to handle. > It is located in DAGCombiner::SimplifySelectCC() method (see [1]). > The transformation happens as a part of DAG to DAG rewrites > (LLVM uses several internal representations: >   - generic optimizer uses LLVM IR, most of the work is done >     using this representation; >   - before instruction selection IR is converted to Selection DAG, >     some optimizations are applied at this stage, >     all such optimizations are a set of pattern replacements; >   - Selection DAG is converted to machine code, some optimizations >     are applied at the machine code level). > > Full pattern is described as follows: > >    // fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A) >    // where y is has a single bit set. >    // A plaintext description would be, we can turn the SELECT_CC into an AND >    // when the condition can be materialized as an all-ones register.  Any >    // single bit-test can be materialized as an all-ones register with >    // shift-left and shift-right-arith. > > For this particular test case the DAG is converted as follows: > >                      .---------------- lhs         The meaning of this select_cc is: >                      |        .------- rhs         `lhs == rhs ? true value : false value` >                      |        | .----- true value >                      |        | |  .-- false value >                      v        v v  v >    (select_cc seteq (and X 2) 0 0 -13) >                            ^ > ->                        '---------------. >    (and (sra (sll X 62) 63)                | >         -13)                               | >                                            | > Before pattern is applied, it checks that second 'and' operand has > only one bit set, (which is true for '2'). > > The pattern itself generates logical shift left / arithmetic shift > right pair, that ensures that result is either all ones (-1) or all > zeros (0). Hence, applying 'and' to shifts result and false value > generates a correct result. >

Thanks for your detailed and invaluable explanation!

Thanks Eduard for detailed explanation. It looks like we could resolve this issue without adding too much complexity to verifier. Also, this code pattern above seems generic enough to be worthwhile with verifier change.

Kuohai, please added detailed explanation (as described by Eduard) in the commit message.

Sure, already added, the commit message and the change now is like this:

---

bpf: Fix a false rejection caused by AND operation

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts     is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     0: (b7) r0 = 0                        ; R0_w=0     1: (79) r2 = *(u64 *)(r1 +0)     func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'     2: R1=ctx() R2_w=trusted_ptr_bpf_map()     ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29     2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4)     4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx()     ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32     6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))     7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)     ;  @ test_libbpf_get_fd_by_id_opts.c:0     8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))     ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27     9: (95) exit

And here is the C code of the prog.

SEC("lsm/bpf_map")     int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode)     {         if (map != (struct bpf_map *)&data_input)                 return 0;

if (fmode & FMODE_WRITE)                 return -EACCES;

return 0;     }

It is clear that the prog can only return either 0 or -EACCESS, and both     values are legal.

So why is it rejected by the verifier?

The verifier log shows that the second if and return value setting     statements in the prog is optimized to bitwise operations "r0 s>>= 63"     and "r0 &= -13". The verifier correctly deduces that the the value of     r0 is in the range [-1, 0] after verifing instruction "r0 s>>= 63".     But when the verifier proceeds to verify instruction "r0 &= -13", it     fails to deduce the correct value range of r0.

7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)     8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))

So why the verifier fails to deduce the result of 'r0 &= -13'?

The verifier uses tnum to track values, and the two ranges "[-1, 0]" and     "[0, -1ULL]" are encoded to the same tnum. When verifing instruction     "r0 &= -13", the verifier erroneously deduces the result from     "[0, -1ULL] AND -13", which is out of the expected return range     [-4095, 0].

As explained by Eduard in [0], the clang transformation that generates this     pattern is located in DAGCombiner::SimplifySelectCC() method (see [1]).

The transformation happens as a part of DAG to DAG rewrites     (LLVM uses several internal representations:      - generic optimizer uses LLVM IR, most of the work is done        using this representation;      - before instruction selection IR is converted to Selection DAG,        some optimizations are applied at this stage,        all such optimizations are a set of pattern replacements;      - Selection DAG is converted to machine code, some optimizations        are applied at the machine code level).

Full pattern is described as follows:

// fold (select_cc seteq (and x, y), 0, 0, A) -> (and (sra (shl x)) A)       // where y is has a single bit set.       // A plaintext description would be, we can turn the SELECT_CC into an AND       // when the condition can be materialized as an all-ones register.  Any       // single bit-test can be materialized as an all-ones register with       // shift-left and shift-right-arith.

For this particular test case the DAG is converted as follows:

.---------------- lhs         The meaning of this select_cc is:                         |        .------- rhs         `lhs == rhs ? true value : false value`                         |        | .----- true value                         |        | |  .-- false value                         v        v v  v       (select_cc seteq (and X 2) 0 0 -13)                               ^     ->                        '---------------.       (and (sra (sll X 62) 63)                |            -13)                               |                                               |     Before pattern is applied, it checks that second 'and' operand has     only one bit set, (which is true for '2').

The pattern itself generates logical shift left / arithmetic shift     right pair, that ensures that result is either all ones (-1) or all     zeros (0). Hence, applying 'and' to shifts result and false value     generates a correct result.

As suggested by Eduard, this patch makes a special case for source     or destination register of '&=' operation being in range [-1, 0].

Meaning that one of the '&=' operands is either:     - all ones, in which case the counterpart is the result of the operation;     - all zeros, in which case zero is the result of the operation.

And MIN and MAX values could be derived based on above two observations.

[0] https://lore.kernel.org/bpf/e62e2971301ca7f2e9eb74fc500c520285cad8f5.camel@g...     [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985...

Suggested-by: Eduard Zingerman eddyz87@gmail.com     Signed-off-by: Xu Kuohai xukuohai@huawei.com

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 640747b53745..30c551d39329 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13374,6 +13374,24 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg,         dst_reg->u32_min_value = var32_off.value;         dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);

+       /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ +       if (src_known && +               dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0 && +               dst_reg->smin_value == -1 && dst_reg->smax_value == 0) {

do we need to check dst_reg->smin_value/smax_value here? They should not impact final dst_reg->s32_{min,max}_value computation, right?

right, the check was simply copied from the old code, which only handled the case where 64-bit range is the same as the 32-bit range

What if we do not have 64bit smin_value/smax_value check? Could you give more explanation here? In my opinion, deducing lower 32bit range should not care upper 32bit values.

I agree that for AND operation there's no need to check the upper 32bit. But for other operations, we may need to consider the impact of upper 32bit overflow.

I added 64bit check in the old patch is to make sure the special case only works when 64bit and 32bit ranges are the same since ranges are the same in the failure verifier log.

...

...

Similarly, for later 64bit min/max and, 32bit value does not really matter.

hmm, the 32-bit check is completely unnecessary.

...

...

• dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);

+               dst_reg->s32_max_value = max_t(s32, src_reg->s32_min_value, 0); +               return; +       }

+       /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ +       if (dst_known && +               src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0 && +               src_reg->smin_value == -1 && src_reg->smax_value == 0) { +               dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0); +               dst_reg->s32_max_value = max_t(s32, dst_reg->s32_min_value, 0); +               return; +       }

/* Safe to set s32 bounds by casting u32 result into s32 when u32          * doesn't cross sign boundary. Otherwise set s32 bounds to unbounded.          */ @@ -13404,6 +13422,24 @@ static void scalar_min_max_and(struct bpf_reg_state *dst_reg,         dst_reg->umin_value = dst_reg->var_off.value;         dst_reg->umax_value = min(dst_reg->umax_value, umax_val);

+       /* Special case: src_reg is known and dst_reg is in range [-1, 0] */ +       if (src_known && +               dst_reg->smin_value == -1 && dst_reg->smax_value == 0 && +               dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) { +               dst_reg->smin_value = min_t(s64, src_reg->smin_value, 0); +               dst_reg->smax_value = max_t(s64, src_reg->smin_value, 0); +               return; +       }

+       /* Special case: dst_reg is known and src_reg is in range [-1, 0] */ +       if (dst_known && +               src_reg->smin_value == -1 && src_reg->smax_value == 0 && +               src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) { +               dst_reg->smin_value = min_t(s64, dst_reg->smin_value, 0); +               dst_reg->smax_value = max_t(s64, dst_reg->smin_value, 0); +               return; +       }

/* Safe to set s64 bounds by casting u64 result into s64 when u64          * doesn't cross sign boundary. Otherwise set s64 bounds to unbounded.          */

...

...

> In my opinion the approach taken by this patch is sub-optimal: > - 512 iterations is too much; > - this does not cover all code that could be generated by the above >    mentioned LLVM transformation >    (e.g. second 'and' operand could be 1 << 16). > > Instead, I suggest to make a special case for source or dst register > of '&=' operation being in range [-1,0]. > Meaning that one of the '&=' operands is either: > - all ones, in which case the counterpart is the result of the operation; > - all zeros, in which case zero is the result of the operation; > - derive MIN and MAX values based on above two observations. >

Totally agree, I'll cook a new patch as you suggested.

> [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985... > > Best regards, > Eduard

On 4/27/2024 4:36 AM, Andrii Nakryiko wrote:

On Tue, Apr 23, 2024 at 7:26 PM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

On 4/24/2024 5:55 AM, Yonghong Song wrote:

...

On 4/20/24 1:33 AM, Xu Kuohai wrote:

...

On 4/20/2024 7:00 AM, Eduard Zingerman wrote:

...

On Thu, 2024-04-11 at 20:27 +0800, Xu Kuohai wrote:

...

From: Xu Kuohai xukuohai@huawei.com

With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts is rejected by the verifier, and the log says:

0: R1=ctx() R10=fp0
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
0: (b7) r0 = 0                        ; R0_w=0
1: (79) r2 = *(u64 *)(r1 +0)
func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map'
2: R1=ctx() R2_w=trusted_ptr_bpf_map()
; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29
2: (18) r3 = 0xffff9742c0951a00       ; R3_w=map_ptr(map=data_input,ks=4,vs=4)
4: (5d) if r2 != r3 goto pc+4         ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4)
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
5: (79) r0 = *(u64 *)(r1 +8)          ; R0_w=scalar() R1=ctx()
; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32
6: (67) r0 <<= 62                     ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000))
7: (c7) r0 s>>= 63                    ; R0_w=scalar(smin=smin32=-1,smax=smax32=0)
;  @ test_libbpf_get_fd_by_id_opts.c:0
8: (57) r0 &= -13                     ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3))
; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27
9: (95) exit

[...]

...

  As suggested by Eduard, this patch makes a special case for source
  or destination register of '&=' operation being in range [-1, 0].

  Meaning that one of the '&=' operands is either:
  - all ones, in which case the counterpart is the result of the operation;
  - all zeros, in which case zero is the result of the operation.

  And MIN and MAX values could be derived based on above two observations.

  [0] https://lore.kernel.org/bpf/e62e2971301ca7f2e9eb74fc500c520285cad8f5.camel@gmail.com/
  [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985a51565/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

  Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
  Signed-off-by: Xu Kuohai <xukuohai@huawei.com>

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 640747b53745..30c551d39329 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13374,6 +13374,24 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, dst_reg->u32_min_value = var32_off.value; dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);

•   /* Special case: src_reg is known and dst_reg is in range [-1, 0] */
  

•   if (src_known &&
  

•           dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0 &&
  

•           dst_reg->smin_value == -1 && dst_reg->smax_value == 0) {
  

please keep if () condition aligned across multiple lines, it's super confusing this way

OK, will update the align style

...

•           dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, src_reg->s32_min_value, 0);
  

do we need to update tnum parts as well (or reset and re-derive, probably)?

btw, can't we support src being a range here? the idea is that dst_reg either all ones or all zeros. For and it means that it either stays all zero, or will be *exactly equal* to src, right? So I think the logic would be:

a) if [s32_min, s32_max] is on the same side of zero, then resulting range would be [min(s32_min, 0), max(s32_max, 0)], just like you have here

b) if [s32_min, s32_max] contains zero, then resulting range will be exactly [s32_min, s32_max]

Or did I make a mistake above?

Totally agree, the AND of any set with the range [-1,0] is equivalent to adding number 0 to the set!

Based on this observation, I've rewritten the patch as follows.

diff --git a/include/linux/tnum.h b/include/linux/tnum.h index 3c13240077b8..5e795d728b9f 100644 --- a/include/linux/tnum.h +++ b/include/linux/tnum.h @@ -52,6 +52,9 @@ struct tnum tnum_mul(struct tnum a, struct tnum b); /* Return a tnum representing numbers satisfying both @a and @b */ struct tnum tnum_intersect(struct tnum a, struct tnum b);

+/* Return a tnum representing numbers satisfying either @a or @b */ +struct tnum tnum_union(struct tnum a, struct tnum b); + /* Return @a with all but the lowest @size bytes cleared */ struct tnum tnum_cast(struct tnum a, u8 size);

diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c index 9dbc31b25e3d..9d4480a683ca 100644 --- a/kernel/bpf/tnum.c +++ b/kernel/bpf/tnum.c @@ -150,6 +150,29 @@ struct tnum tnum_intersect(struct tnum a, struct tnum b) return TNUM(v & ~mu, mu); }

+/* + * Each bit has 3 states: unkown, known 0, known 1. If using x to represent + * unknown state, the result of the union of two bits is as follows: + * + * | x 0 1 + * -----+------------ + * x | x x x + * 0 | x 0 x + * 1 | x x 1 + * + * For tnum a and b, only the bits that are both known 0 or known 1 in a + * and b are known in the result of union a and b. + */ +struct tnum tnum_union(struct tnum a, struct tnum b) +{ + u64 v0, v1, mu; + + mu = a.mask | b.mask; // unkown bits either in a or b + v1 = (a.value & b.value) & ~mu; // "known 1" bits in both a and b + v0 = (~a.value & ~b.value) & ~mu; // "known 0" bits in both a and b + return TNUM(v1, mu | ~(v0 | v1)); +} + struct tnum tnum_cast(struct tnum a, u8 size) { a.value &= (1ULL << (size * 8)) - 1; { a.value &= (1ULL << (size * 8)) - 1; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8f0f2e21699e..b69c89bc5cfc 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13478,6 +13478,28 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, return; }

+ /* Special case: dst_reg is in range [-1, 0] */ + if (dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) { + var32_off = tnum_union(src_reg->var_off, tnum_const(0)); + dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off); + dst_reg->u32_min_value = var32_off.value; + dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val); + dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0); + dst_reg->s32_max_value = max_t(s32, src_reg->s32_max_value, 0); + return; + } + + /* Special case: src_reg is in range [-1, 0] */ + if (src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) { + var32_off = tnum_union(dst_reg->var_off, tnum_const(0)); + dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off); + dst_reg->u32_min_value = var32_off.value; + dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val); + dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0); + dst_reg->s32_max_value = max_t(s32, dst_reg->s32_max_value, 0); + return; + } + /* We get our minimum from the var_off, since that's inherently * bitwise. Our maximum is the minimum of the operands' maxima. */ @@ -13508,6 +13530,26 @@ static void scalar_min_max_and(struct bpf_reg_state *dst_reg, return; }

+ /* Special case: dst_reg is in range [-1, 0] */ + if (dst_reg->smin_value == -1 && dst_reg->smax_value == 0) { + dst_reg->var_off = tnum_union(src_reg->var_off, tnum_const(0)); + dst_reg->umin_value = dst_reg->var_off.value; + dst_reg->umax_value = min(dst_reg->umax_value, umax_val); + dst_reg->smin_value = min_t(s64, src_reg->smin_value, 0); + dst_reg->smax_value = max_t(s64, src_reg->smax_value, 0); + return; + } + + /* Special case: src_reg is in range [-1, 0] */ + if (src_reg->smin_value == -1 && src_reg->smax_value == 0) { + dst_reg->var_off = tnum_union(dst_reg->var_off, tnum_const(0)); + dst_reg->umin_value = dst_reg->var_off.value; + dst_reg->umax_value = min(dst_reg->umax_value, umax_val); + dst_reg->smin_value = min_t(s64, dst_reg->smin_value, 0); + dst_reg->smax_value = max_t(s64, dst_reg->smax_value, 0); + return; + } +

...

•           return;
  

•   }
  

•   /* Special case: dst_reg is known and src_reg is in range [-1, 0] */
  

•   if (dst_known &&
  

•           src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0 &&
  

•           src_reg->smin_value == -1 && src_reg->smax_value == 0) {
  

•           dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, dst_reg->s32_min_value, 0);
  

•           return;
  

•   }
  

•     /* Safe to set s32 bounds by casting u32 result into s32 when u32
       * doesn't cross sign boundary. Otherwise set s32 bounds to unbounded.
       */
  

[...]

On Mon, 2024-04-29 at 13:58 -0700, Andrii Nakryiko wrote:

[...]

...

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8f0f2e21699e..b69c89bc5cfc 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13478,6 +13478,28 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, return; }

•   /* Special case: dst_reg is in range [-1, 0] */
  

•   if (dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) {
  

•           var32_off = tnum_union(src_reg->var_off, tnum_const(0));
  

•           dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off);
  

•           dst_reg->u32_min_value = var32_off.value;
  

•           dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);
  

can you explain the logic behing u32 min/max updates, especially that we use completely different values for min/max and it's not clear why u32_min <= u32_max invariant will always hold. Same below

I agree with Andrii here. It appears that dst_reg.{min,max} fields should be set as {min(src.min, 0), max(src.max, 0)} for both signed and unsigned cases. Wdyt?

...

•           dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, src_reg->s32_max_value, 0);
  

•           return;
  

•   }
  

•   /* Special case: src_reg is in range [-1, 0] */
  

•   if (src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) {
  

•           var32_off = tnum_union(dst_reg->var_off, tnum_const(0));
  

•           dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off);
  

•           dst_reg->u32_min_value = var32_off.value;
  

•           dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);
  

•           dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, dst_reg->s32_max_value, 0);
  

•           return;
  

•   }
  

•    /* We get our minimum from the var_off, since that's inherently
      * bitwise.  Our maximum is the minimum of the operands' maxima.
      */
  

[...]

On 4/30/2024 4:58 AM, Andrii Nakryiko wrote:

On Sun, Apr 28, 2024 at 8:15 AM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

On 4/27/2024 4:36 AM, Andrii Nakryiko wrote:

...

On Tue, Apr 23, 2024 at 7:26 PM Xu Kuohai xukuohai@huaweicloud.com wrote:

...

On 4/24/2024 5:55 AM, Yonghong Song wrote:

...

On 4/20/24 1:33 AM, Xu Kuohai wrote:

...

On 4/20/2024 7:00 AM, Eduard Zingerman wrote: > On Thu, 2024-04-11 at 20:27 +0800, Xu Kuohai wrote: >> From: Xu Kuohai xukuohai@huawei.com >> >> With lsm return value check, the no-alu32 version test_libbpf_get_fd_by_id_opts >> is rejected by the verifier, and the log says: >> >> 0: R1=ctx() R10=fp0 >> ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >> 0: (b7) r0 = 0 ; R0_w=0 >> 1: (79) r2 = *(u64 *)(r1 +0) >> func 'bpf_lsm_bpf_map' arg0 has btf_id 916 type STRUCT 'bpf_map' >> 2: R1=ctx() R2_w=trusted_ptr_bpf_map() >> ; if (map != (struct bpf_map *)&data_input) @ test_libbpf_get_fd_by_id_opts.c:29 >> 2: (18) r3 = 0xffff9742c0951a00 ; R3_w=map_ptr(map=data_input,ks=4,vs=4) >> 4: (5d) if r2 != r3 goto pc+4 ; R2_w=trusted_ptr_bpf_map() R3_w=map_ptr(map=data_input,ks=4,vs=4) >> ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >> 5: (79) r0 = *(u64 *)(r1 +8) ; R0_w=scalar() R1=ctx() >> ; if (fmode & FMODE_WRITE) @ test_libbpf_get_fd_by_id_opts.c:32 >> 6: (67) r0 <<= 62 ; R0_w=scalar(smax=0x4000000000000000,umax=0xc000000000000000,smin32=0,smax32=umax32=0,var_off=(0x0; 0xc000000000000000)) >> 7: (c7) r0 s>>= 63 ; R0_w=scalar(smin=smin32=-1,smax=smax32=0) >> ; @ test_libbpf_get_fd_by_id_opts.c:0 >> 8: (57) r0 &= -13 ; R0_w=scalar(smax=0x7ffffffffffffff3,umax=0xfffffffffffffff3,smax32=0x7ffffff3,umax32=0xfffffff3,var_off=(0x0; 0xfffffffffffffff3)) >> ; int BPF_PROG(check_access, struct bpf_map *map, fmode_t fmode) @ test_libbpf_get_fd_by_id_opts.c:27 >> 9: (95) exit

[...]

...

   As suggested by Eduard, this patch makes a special case for source
   or destination register of '&=' operation being in range [-1, 0].

   Meaning that one of the '&=' operands is either:
   - all ones, in which case the counterpart is the result of the operation;
   - all zeros, in which case zero is the result of the operation.

   And MIN and MAX values could be derived based on above two observations.

   [0] https://lore.kernel.org/bpf/e62e2971301ca7f2e9eb74fc500c520285cad8f5.camel@gmail.com/
   [1] https://github.com/llvm/llvm-project/blob/4523a267829c807f3fc8fab8e5e9613985a51565/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

   Suggested-by: Eduard Zingerman <eddyz87@gmail.com>
   Signed-off-by: Xu Kuohai <xukuohai@huawei.com>

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 640747b53745..30c551d39329 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13374,6 +13374,24 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, dst_reg->u32_min_value = var32_off.value; dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);

•   /* Special case: src_reg is known and dst_reg is in range [-1, 0] */
  

•   if (src_known &&
  

•           dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0 &&
  

•           dst_reg->smin_value == -1 && dst_reg->smax_value == 0) {
  

please keep if () condition aligned across multiple lines, it's super confusing this way

OK, will update the align style

...

...

•           dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, src_reg->s32_min_value, 0);
  

do we need to update tnum parts as well (or reset and re-derive, probably)?

btw, can't we support src being a range here? the idea is that dst_reg either all ones or all zeros. For and it means that it either stays all zero, or will be *exactly equal* to src, right? So I think the logic would be:

a) if [s32_min, s32_max] is on the same side of zero, then resulting range would be [min(s32_min, 0), max(s32_max, 0)], just like you have here

b) if [s32_min, s32_max] contains zero, then resulting range will be exactly [s32_min, s32_max]

Or did I make a mistake above?

Totally agree, the AND of any set with the range [-1,0] is equivalent to adding number 0 to the set!

Based on this observation, I've rewritten the patch as follows.

diff --git a/include/linux/tnum.h b/include/linux/tnum.h index 3c13240077b8..5e795d728b9f 100644 --- a/include/linux/tnum.h +++ b/include/linux/tnum.h @@ -52,6 +52,9 @@ struct tnum tnum_mul(struct tnum a, struct tnum b); /* Return a tnum representing numbers satisfying both @a and @b */ struct tnum tnum_intersect(struct tnum a, struct tnum b);

+/* Return a tnum representing numbers satisfying either @a or @b */ +struct tnum tnum_union(struct tnum a, struct tnum b);

• /* Return @a with all but the lowest @size bytes cleared */ struct tnum tnum_cast(struct tnum a, u8 size);

diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c index 9dbc31b25e3d..9d4480a683ca 100644 --- a/kernel/bpf/tnum.c +++ b/kernel/bpf/tnum.c @@ -150,6 +150,29 @@ struct tnum tnum_intersect(struct tnum a, struct tnum b) return TNUM(v & ~mu, mu); }

+/*

• • Each bit has 3 states: unkown, known 0, known 1. If using x to represent
• • unknown state, the result of the union of two bits is as follows:

• •     | x    0    1
    

• • -----+------------

• • x   | x    x    x
    

• • 0   | x    0    x
    

• • 1   | x    x    1
    

• • For tnum a and b, only the bits that are both known 0 or known 1 in a
• • and b are known in the result of union a and b.
• */

+struct tnum tnum_union(struct tnum a, struct tnum b) +{

•   u64 v0, v1, mu;
  

•   mu = a.mask | b.mask; // unkown bits either in a or b
  

•   v1 = (a.value & b.value) & ~mu; // "known 1" bits in both a and b
  

•   v0 = (~a.value & ~b.value) & ~mu; // "known 0" bits in both a and b
  

no C++-style comments, please

OK, will fix in the formal patch.

...

•   return TNUM(v1, mu | ~(v0 | v1));
  

+}

I've CC'ed Edward, hopefully he can take a look as well. Please CC him on future patches touching tnum as well.

Sure

...

struct tnum tnum_cast(struct tnum a, u8 size) { a.value &= (1ULL << (size * 8)) - 1; { a.value &= (1ULL << (size * 8)) - 1; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 8f0f2e21699e..b69c89bc5cfc 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -13478,6 +13478,28 @@ static void scalar32_min_max_and(struct bpf_reg_state *dst_reg, return; }

•   /* Special case: dst_reg is in range [-1, 0] */
  

•   if (dst_reg->s32_min_value == -1 && dst_reg->s32_max_value == 0) {
  

•           var32_off = tnum_union(src_reg->var_off, tnum_const(0));
  

•           dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off);
  

•           dst_reg->u32_min_value = var32_off.value;
  

•           dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);
  

can you explain the logic behing u32 min/max updates, especially that we use completely different values for min/max and it's not clear why u32_min <= u32_max invariant will always hold. Same below

We're adding 0 to the existing range, and 0 is the smallest unsigned number, so the resulted unsigned min can only get smaller, and the unsigned max will not be affected. In fact, since 0 is added to the range, var32_off.value should be 0. And since -1 is in included in dst_reg, dst_reg->u32_max_value should be -1U, the maximum unsigned integer. So we can just set u32_min to 0, and set u32_max to umax_val.

...

•           dst_reg->s32_min_value = min_t(s32, src_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, src_reg->s32_max_value, 0);
  

•           return;
  

•   }
  

•   /* Special case: src_reg is in range [-1, 0] */
  

•   if (src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0) {
  

•           var32_off = tnum_union(dst_reg->var_off, tnum_const(0));
  

•           dst_reg->var_off = tnum_with_subreg(dst_reg->var_off, var32_off);
  

•           dst_reg->u32_min_value = var32_off.value;
  

•           dst_reg->u32_max_value = min(dst_reg->u32_max_value, umax_val);
  

•           dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, dst_reg->s32_max_value, 0);
  

•           return;
  

•   }
  

•     /* We get our minimum from the var_off, since that's inherently
       * bitwise.  Our maximum is the minimum of the operands' maxima.
       */
  

@@ -13508,6 +13530,26 @@ static void scalar_min_max_and(struct bpf_reg_state *dst_reg, return; }

•   /* Special case: dst_reg is in range [-1, 0] */
  

•   if (dst_reg->smin_value == -1 && dst_reg->smax_value == 0) {
  

•           dst_reg->var_off = tnum_union(src_reg->var_off, tnum_const(0));
  

•           dst_reg->umin_value = dst_reg->var_off.value;
  

•           dst_reg->umax_value = min(dst_reg->umax_value, umax_val);
  

•           dst_reg->smin_value = min_t(s64, src_reg->smin_value, 0);
  

•           dst_reg->smax_value = max_t(s64, src_reg->smax_value, 0);
  

•           return;
  

•   }
  

•   /* Special case: src_reg is in range [-1, 0] */
  

•   if (src_reg->smin_value == -1 && src_reg->smax_value == 0) {
  

•           dst_reg->var_off = tnum_union(dst_reg->var_off, tnum_const(0));
  

•           dst_reg->umin_value = dst_reg->var_off.value;
  

•           dst_reg->umax_value = min(dst_reg->umax_value, umax_val);
  

•           dst_reg->smin_value = min_t(s64, dst_reg->smin_value, 0);
  

•           dst_reg->smax_value = max_t(s64, dst_reg->smax_value, 0);
  

•           return;
  

•   }
  

...

...

•           return;
  

•   }
  

•   /* Special case: dst_reg is known and src_reg is in range [-1, 0] */
  

•   if (dst_known &&
  

•           src_reg->s32_min_value == -1 && src_reg->s32_max_value == 0 &&
  

•           src_reg->smin_value == -1 && src_reg->smax_value == 0) {
  

•           dst_reg->s32_min_value = min_t(s32, dst_reg->s32_min_value, 0);
  

•           dst_reg->s32_max_value = max_t(s32, dst_reg->s32_min_value, 0);
  

•           return;
  

•   }
  

•      /* Safe to set s32 bounds by casting u32 result into s32 when u32
        * doesn't cross sign boundary. Otherwise set s32 bounds to unbounded.
        */
  

[...]