Basically I want to read bytes from the array map via index and offset, but I get invalid access to map value even though I have performed bounds checking
I really have no idea what's going wrong, may be related to an overflow risk?
Any comments are appreciated, thanks!
Here's the code:
struct bpf_elf_map __section("maps") data_store = {
.type = BPF_MAP_TYPE_ARRAY,
.size_key = sizeof(__u32),
.size_value = 1024,
.max_elem = 4096,
.pinning = PIN_GLOBAL_NS,
};
static __always_inline void read_data(__u32 idx, __u32 offset, void *dst,
__u32 size) {
if (size > 512 || offset >= 1024) {
// for the ebpf verifier
return;
}
void *b = bpf_map_lookup_elem(&data_store, &idx);
if (!b) {
// shouldn't happen
return;
}
if (offset + size <= 1024) {
for (__u32 i = 0; i < size && i < 512; ++i) {
if (offset + i >= 1024) {
return;
}
// !! where the verifier complains
memcpy(dst + i, b + offset + i, sizeof(__u8));
}
} else {
// ...
}
}
verifier log:
; for (__u32 i = 0; i < size && i < 512; ++i) {
197: (25) if r1 > 0x1fe goto pc+8
;
198: (bf) r2 = r1
199: (07) r2 += 1
; for (__u32 i = 0; i < size && i < 512; ++i) {
200: (3d) if r2 >= r8 goto pc+5
R0=map_value(id=0,off=0,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R1=invP0 R2_w=invP1 R3_w=inv(id=0,umax_value=255,var_off=(0x0; 0xff)) R6=map_value(id=0,off=0,ks=4,vs=32,imm=0) R7=map_value(id=0,off=0,ks=4,vs=512,imm=0) R8=inv(id=261,umin_value=2,umax_value=512,var_off=(0x0; 0x3ff)) R9=invP(id=0,umin_value=1,umax_value=1024,var_off=(0x0; 0x7ff)) R10=fp0 fp-8=mmmmm??? fp-48=????mmmm
201: (bf) r3 = r9
202: (0f) r3 += r1
203: (bf) r1 = r2
204: (25) if r3 > 0x3ff goto pc+1
R0=map_value(id=0,off=0,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R1=invP1 R2=invP1 R3=invP(id=0,umin_value=1,umax_value=1023,var_off=(0x0; 0x3ff)) R6=map_value(id=0,off=0,ks=4,vs=32,imm=0) R7=map_value(id=0,off=0,ks=4,vs=512,imm=0) R8=inv(id=261,umin_value=2,umax_value=512,var_off=(0x0; 0x3ff)) R9=invP(id=263,umin_value=1,umax_value=1024,var_off=(0x0; 0x7ff)) R10=fp0 fp-8=mmmmm??? fp-48=????mmmm
205: (05) goto pc-15
; memcpy(dst + i, b + offset + i, sizeof(__u8));
191: (bf) r2 = r7
192: (0f) r2 += r1
193: (bf) r3 = r0
194: (0f) r3 += r1
195: (71) r3 = *(u8 *)(r3 +0)
R0=map_value(id=0,off=0,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R1=invP1 R2_w=map_value(id=0,off=1,ks=4,vs=512,imm=0) R3_w=map_value(id=0,off=1,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R6=map_value(id=0,off=0,ks=4,vs=32,imm=0) R7=map_value(id=0,off=0,ks=4,vs=512,imm=0) R8=inv(id=261,umin_value=2,umax_value=512,var_off=(0x0; 0x3ff)) R9=invP(id=263,umin_value=1,umax_value=1024,var_off=(0x0; 0x7ff)) R10=fp0 fp-8=mmmmm??? fp-48=????mmmm
invalid access to map value, value_size=1024 off=1024 size=1
R3 max value is outside of the allowed memory range
TL;DR. When it checks the memcpy's memory access, the verifier has lost information from the previous bounds check (offset + i >= 1024) and therefore errors.
193: (bf) r3 = r0
194: (0f) r3 += r1
195: (71) r3 = *(u8 *)(r3 +0)
R0=map_value(id=0,off=0,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R1=invP1 R2_w=map_value(id=0,off=1,ks=4,vs=512,imm=0) R3_w=map_value(id=0,off=1,ks=4,vs=1024,umax_value=1023,var_off=(0x0; 0x3ff)) R6=map_value(id=0,off=0,ks=4,vs=32,imm=0) R7=map_value(id=0,off=0,ks=4,vs=512,imm=0) R8=inv(id=261,umin_value=2,umax_value=512,var_off=(0x0; 0x3ff)) R9=invP(id=263,umin_value=1,umax_value=1024,var_off=(0x0; 0x7ff)) R10=fp0 fp-8=mmmmm??? fp-48=????mmmm
invalid access to map value, value_size=1024 off=1024 size=1
In this output, R1 is i and R0 is b + offset.
The verifier complains that, when i=1 (i.e., r1=invP1) and offset=1023 (i.e., R0's umax_value=1023), the memory load could read outside of the 1024 bytes of the value. This is easily checked by adding R3's umax_value to R3's off to the access size (1023 + 1 + 1).
That seems unexpected at first sight because you did check that the memory load is bounded just before:
if (offset + i >= 1024) {
return;
}
The additions offset + i and b + offset + i are however computed separately and the bounds are therefore lost. We can see that in the verifier output where the first addition is computed at instruction 202 while the second is computed at instruction 194.
I believe this is happening because you're compiler reorganized your code to move the computation of b + offset outside the loop body.
To prevent the compiler from reorganizing code that way, you could maybe change the loop to:
dst -= offset;
for (__u32 i = offset; i < size + offset && i < 1024; ++i)
memcpy(dst + i, b + i, sizeof(__u8));