bpf: permit map_ptr arithmetic with opcode add and offset 0
Subsystems (6)
PATCH v3 1/2 bpf: permit map_ptr arithmetic with opcode add and offset 0
In reply to Yonghong SongCommit 41c48f3a98231 ("bpf: Support access
to bpf map fields") added support to access map fields with CORE support. For example,
struct bpf_map {
__u32 max_entries;
} __attribute__((preserve_access_index));
struct bpf_array {
struct bpf_map map;
__u32 elem_size;
} __attribute__((preserve_access_index));
struct {
__uint(type, BPF_MAP_TYPE_ARRAY);
__uint(max_entries, 4);
__type(key, __u32);
__type(value, __u32);
} m_array SEC(".maps");
SEC("cgroup_skb/egress")
int cg_skb(void *ctx)
{
struct bpf_array *array = (struct bpf_array *)&m_array;
/* .. array->map.max_entries .. */
}In kernel, bpf_htab has similar structure,
struct bpf_htab {
struct bpf_map map;
...
}In the above cg_skb(), to access array->map.max_entries, with CORE, the clang will generate two builtin's.
base = &m_array;
/* access array.map */
map_addr = __builtin_preserve_struct_access_info(base, 0, 0);
/* access array.map.max_entries */
max_entries_addr = __builtin_preserve_struct_access_info(map_addr, 0, 0);
max_entries = *max_entries_addr;In the current llvm, if two builtin's are in the same function or
in the same function after inlining, the compiler is smart enough to chain them together and generates like below:
base = &m_array;
max_entries = *(base + reloc_offset); /* reloc_offset = 0 in this case */
and we are fine.
But if we force no inlining for one of functions in test_map_ptr() selftest, e.g., check_default(), the above two __builtin_preserve_* will be in two different functions. In this case, we will have code like:
func check_hash():
reloc_offset_map = 0;
base = &m_array;
map_base = base + reloc_offset_map;
check_default(map_base, ...)
func check_default(map_base, ...):
max_entries = *(map_base + reloc_offset_max_entries);In kernel, map_ptr (CONST_PTR_TO_MAP) does not allow any arithmetic.
The above "map_base = base + reloc_offset_map" will trigger a verifier failure.
; VERIFY(check_default(&hash->map, map));
0: (18) r7 = 0xffffb4fe8018a004
2: (b4) w1 = 110
3: (63) *(u32 *)(r7 +0) = r1
R1_w=invP110 R7_w=map_value(id=0,off=4,ks=4,vs=8,imm=0) R10=fp0
; VERIFY_TYPE(BPF_MAP_TYPE_HASH, check_hash);
4: (18) r1 = 0xffffb4fe8018a000
6: (b4) w2 = 1
7: (63) *(u32 *)(r1 +0) = r2
R1_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R2_w=invP1 R7_w=map_value(id=0,off=4,ks=4,vs=8,imm=0) R10=fp0
8: (b7) r2 = 0
9: (18) r8 = 0xffff90bcb500c000
11: (18) r1 = 0xffff90bcb500c000
13: (0f) r1 += r2
R1 pointer arithmetic on map_ptr prohibited
To fix the issue, let us permit map_ptr + 0 arithmetic which will result in exactly the same map_ptr.
--- kernel/bpf/verifier.c | 4 ++++ 1 file changed, 4 insertions(+)
kernel/bpf/verifier.c +4 -0
@@ -5317,6 +5317,10 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, dst, reg_type_str[ptr_reg->type]);return -EACCES ;case CONST_PTR_TO_MAP : +/* smin_val represents the known value */ +if (known && smin_val ==0 && opcode ==BPF_ADD ) +break ; +/* fall-through */ case PTR_TO_PACKET_END :case PTR_TO_SOCKET :case PTR_TO_SOCKET_OR_NULL :
Signature · 1 line
2.24.1
v3 cover bpf: permit map_ptr arithmetic with opcode add and offset 0
With CORE, it is possible that the compiler may produce code like
r1 = 0 // relocation instruction
map_ptr += r1
...
Currently verifier does not allow map_ptr arithmetic, even for adding with 0. This patch set relaxed the condition so the above code can be accepted. Patch #1 is the kernel implementation and Patch #2 added selftest tests to cover the new functionality.
Changelog:
v2 -> v3:
. only change hashmap subtest to use non-inline version of check_default(),
other subtests still used inline version. This will provide coverage for both inline and non-inline check_default(). (Andrey)
v1 -> v2:
. add comment to clarify smin_val represents the const. (Andrii)
Yonghong Song (2):
bpf: permit map_ptr arithmetic with opcode add and offset 0 selftests/bpf: add test for map_ptr arithmetic
kernel/bpf/verifier.c | 4 +++ .../selftests/bpf/progs/map_ptr_kern.c | 10 +++++- .../testing/selftests/bpf/verifier/map_ptr.c | 32 +++++++++++++++++++ 3 files changed, 45 insertions(+), 1 deletion(-)
Signature · 1 line
2.24.1
PATCH v3 2/2 selftests/bpf: add test for map_ptr arithmetic
Change selftest map_ptr_kern.c with disabling inlining for one of subtests, which will fail the test without previous verifier change. Also added to verifier test for both "map_ptr += scalar" and "scalar += map_ptr" arithmetic.
--- .../selftests/bpf/progs/map_ptr_kern.c | 10 +++++- .../testing/selftests/bpf/verifier/map_ptr.c | 32 +++++++++++++++++++ 2 files changed, 41 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/progs/map_ptr_kern.c +9 -1
@@ -82,6 +82,14 @@ static inline int check_default(struct bpf_map *indirect,return 1 ; } +static __attribute__ ((noinline))int +check_default_noinline (struct bpf_map *indirect,struct bpf_map *direct) +{ +VERIFY (check (indirect, direct,sizeof (__u32),sizeof (__u32), +MAX_ENTRIES )); +return 1 ; +} +typedef struct {int counter; }atomic_t ;
@@ -107,7 +115,7 @@ static inline int check_hash(void)struct bpf_map *map = (struct bpf_map *)&m_hash;int i; -VERIFY (check_default (&hash->map, map)); +VERIFY (check_default_noinline (&hash->map, map));VERIFY (hash->n_buckets ==MAX_ENTRIES );VERIFY (hash->elem_size ==64 );
tools/testing/selftests/bpf/verifier/map_ptr.c +32 -0
@@ -60,3 +60,35 @@ .result = ACCEPT, .retval = 1, }, +{ + "bpf_map_ptr: r = 0, map_ptr = map_ptr + r", + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_16b = { 4 }, + .result = ACCEPT, +}, +{ +"bpf_map_ptr: r = 0, r = r + map_ptr" , + .insns = { +BPF_ST_MEM (BPF_DW ,BPF_REG_10 ,-8 ,0 ), +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_MOV64_IMM (BPF_REG_1 ,0 ), +BPF_LD_MAP_FD (BPF_REG_0 ,0 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_0 ), +BPF_RAW_INSN (BPF_JMP |BPF_CALL ,0 ,0 ,0 , BPF_FUNC_map_lookup_elem), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map_hash_16b = { 4 }, + .result = ACCEPT, +},
Signature · 1 line
2.24.1
Re: [PATCH bpf-next v3 2/2] selftests/bpf: add test for map_ptr arithmetic
Quoted 8 lines · Yonghong Song
Change selftest
map_ptr_kern.cwith disabling inlining for one of subtests, which will fail the test without previous verifier change. Also added to verifier test for both "map_ptr+= scalar" and "scalar +=map_ptr" arithmetic.Signed-off-by Yonghong Song <[email protected]>---
tools/testing/selftests/bpf/progs/map_ptr_kern.c static inline int check_default(struct bpf_map *indirect, · line 85
Quoted 13 lines
.../selftests/bpf/progs/map_ptr_kern.c | 10 +++++- .../testing/selftests/bpf/verifier/map_ptr.c | 32 +++++++++++++++++++ 2 files changed, 41 insertions(+), 1 deletion(-)tools/testing/selftests/bpf/progs/map_ptr_kern.c +1
-0@@ -82,6 +82,14 @@ static inline int check_default(struct bpf_map *indirect,return 1 ; } +static __attribute__ ((noinline)) int
just fyi: there is now __noinline defined in bpf_helpers.h, saving a bunch of typing
Quoted 10 lines
tools/testing/selftests/bpf/progs/map_ptr_kern.c +7
-0+check_default_noinline(struct bpf_map *indirect, struct bpf_map *direct) +{ + VERIFY(check(indirect, direct, sizeof(__u32), sizeof(__u32), +MAX_ENTRIES )); +return 1 ; +} +typedef struct {int counter; }atomic_t ;
[...]
Quoted 81 lines · Yonghong Song
Commit
41c48f3a98231("bpf: Support access
to bpf map fields") added support to access map fields with CORE support. For example,struct bpf_map { __u32 max_entries; } __attribute__((preserve_access_index)); struct bpf_array { struct bpf_map map; __u32 elem_size; } __attribute__((preserve_access_index)); struct { __uint(type, BPF_MAP_TYPE_ARRAY); __uint(max_entries, 4); __type(key, __u32); __type(value, __u32); } m_array SEC(".maps"); SEC("cgroup_skb/egress") int cg_skb(void *ctx) { struct bpf_array *array = (struct bpf_array *)&m_array; /* .. array->map.max_entries .. */ }In kernel,
bpf_htabhas similar structure,struct bpf_htab { struct bpf_map map; ... }In the above
cg_skb(), to accessarray->map.max_entries, with CORE, the clang will generate two builtin's.base = &m_array; /* access array.map */ map_addr = __builtin_preserve_struct_access_info(base, 0, 0); /* access array.map.max_entries */ max_entries_addr = __builtin_preserve_struct_access_info(map_addr, 0, 0); max_entries = *max_entries_addr;In the current llvm, if two builtin's are in the same function or
in the same function after inlining, the compiler is smart enough to chain them together and generates like below:
base =&m_array;
max_entries= *(base +reloc_offset); /*reloc_offset= 0 in this case */
and we are fine.But if we force no inlining for one of functions in
test_map_ptr()selftest, e.g.,check_default(), the above two __builtin_preserve_* will be in two different functions. In this case, we will have code like:func check_hash(): reloc_offset_map = 0; base = &m_array; map_base = base + reloc_offset_map; check_default(map_base, ...) func check_default(map_base, ...): max_entries = *(map_base + reloc_offset_max_entries);In kernel,
map_ptr(CONST_PTR_TO_MAP) does not allow any arithmetic.
The above "map_base= base +reloc_offset_map" will trigger a verifier failure.
;VERIFY(check_default(&hash->map, map));
0: (18) r7 =0xffffb4fe8018a004
2: (b4) w1 = 110
3: (63) *(u32 *)(r7 +0) = r1
R1_w=invP110 R7_w=map_value(id=0,off=4,ks=4,vs=8,imm=0) R10=fp0
;VERIFY_TYPE(BPF_MAP_TYPE_HASH, check_hash);
4: (18) r1 =0xffffb4fe8018a000
6: (b4) w2 = 1
7: (63) *(u32 *)(r1 +0) = r2
R1_w=map_value(id=0,off=0,ks=4,vs=8,imm=0) R2_w=invP1 R7_w=map_value(id=0,off=4,ks=4,vs=8,imm=0) R10=fp0
8: (b7) r2 = 0
9: (18) r8 =0xffff90bcb500c000
11: (18) r1 =0xffff90bcb500c000
13: (0f) r1 += r2
R1 pointer arithmetic onmap_ptrprohibited
Quoted 5 lines
To fix the issue, let us permit
map_ptr+ 0 arithmetic which will result in exactly the samemap_ptr.Signed-off-by Yonghong Song <[email protected]>---
[...]
Re: [PATCH bpf-next v3 2/2] selftests/bpf: add test for map_ptr arithmetic
In reply to Andrii NakryikoQuoted 24 lines · Andrii Nakryiko
Quoted 8 lines · Yonghong Song
Change selftest
map_ptr_kern.cwith disabling inlining for one of subtests, which will fail the test without previous verifier change. Also added to verifier test for both "map_ptr+= scalar" and "scalar +=map_ptr" arithmetic.Signed-off-by Yonghong Song <[email protected]>---
Acked-by Andrii Nakryiko <[email protected]>Quoted 12 lines
.../selftests/bpf/progs/map_ptr_kern.c | 10 +++++- .../testing/selftests/bpf/verifier/map_ptr.c | 32 +++++++++++++++++++ 2 files changed, 41 insertions(+), 1 deletion(-)tools/testing/selftests/bpf/progs/map_ptr_kern.c +0
-0@@ -82,6 +82,14 @@ static inline int check_default(struct bpf_map *indirect,return 1 ; }
Quoted 4 lines
tools/testing/selftests/bpf/progs/map_ptr_kern.c static inline int check_default(struct bpf_map *indirect, · line 85
Quoted 1 line
tools/testing/selftests/bpf/progs/map_ptr_kern.c +1
-0+static __attribute__ ((noinline)) intjust fyi: there is now
__noinlinedefined inbpf_helpers.h, saving a bunch of typing
I fixed it manually while applying.
Thanks everyone.