bpf verification fails when accessing an array element


William Tu
 

Hi,

I'm new to BPF and I'm trying to implement the following logic but fails due to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing list.)

So I have an integer array of size 32 as the value of a bpf hashmap. I save the index of the array at skb->cb[0], so that another bpf can tail_call it with different index value. I've checked that the index is within the range and I couldn't understand why this fails. Any comments are appreciated!

--- bpf code ---
struct actions {
    int action[32];
};
struct bpf_map_def SEC("maps") test_map = {
    .type = BPF_MAP_TYPE_HASH,
    .key_size = sizeof(uint32_t),
    .value_size = sizeof(struct actions),
    .max_entries = 1024,
};

SEC("socket2")
int bpf_prog2(struct __sk_buff *skb)
{
    u32 key = 0;
    int v = 0;
    char fmt[] = "%d\n";
    uint32_t index = 0;
    struct actions *acts;
    acts = bpf_map_lookup_elem(&test_map, &key);   
    if (!acts)
        return 0; 

    index = skb->cb[0];
    if (index >= 32)
        return 0;
   
    v = acts->action[index];
    bpf_trace_printk(fmt, sizeof(fmt), v);
    return 0;
}

--- error log ---
bpf_prog_load() err=13
0: (bf) r6 = r1
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -4) = r1
3: (b7) r1 = 680997
4: (63) *(u32 *)(r10 -8) = r1
5: (bf) r2 = r10
6: (07) r2 += -4
7: (18) r1 = 0x1c10c5a0
9: (85) call 1
10: (15) if r0 == 0x0 goto pc+9
 R0=map_value(ks=4,vs=128) R6=ctx R10=fp
11: (61) r1 = *(u32 *)(r6 +56)
12: (25) if r1 > 0x1f goto pc+7
 R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
13: (67) r1 <<= 2
14: (0f) r0 += r1
15: (61) r3 = *(u32 *)(r0 +0)
R0 invalid mem access 'inv'

btw, if I change to using switch-case, basically listing all 32 cases, then the program passes.

I wonder if I'm doing something wrong, or fundamentally BPF does not allow us to do it?
Thank you~

William


Alexei Starovoitov
 

On Mon, Apr 18, 2016 at 12:47 PM, William Tu via iovisor-dev
<iovisor-dev@...> wrote:
Hi,

I'm new to BPF and I'm trying to implement the following logic but fails due
to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing
list.)

So I have an integer array of size 32 as the value of a bpf hashmap. I save
the index of the array at skb->cb[0], so that another bpf can tail_call it
with different index value. I've checked that the index is within the range
and I couldn't understand why this fails. Any comments are appreciated!

--- bpf code ---
struct actions {
int action[32];
};
struct bpf_map_def SEC("maps") test_map = {
.type = BPF_MAP_TYPE_HASH,
.key_size = sizeof(uint32_t),
.value_size = sizeof(struct actions),
.max_entries = 1024,
};

SEC("socket2")
int bpf_prog2(struct __sk_buff *skb)
{
u32 key = 0;
int v = 0;
char fmt[] = "%d\n";
uint32_t index = 0;
struct actions *acts;
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;

v = acts->action[index];
bpf_trace_printk(fmt, sizeof(fmt), v);
return 0;
}

--- error log ---
bpf_prog_load() err=13
0: (bf) r6 = r1
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -4) = r1
3: (b7) r1 = 680997
4: (63) *(u32 *)(r10 -8) = r1
5: (bf) r2 = r10
6: (07) r2 += -4
7: (18) r1 = 0x1c10c5a0
9: (85) call 1
10: (15) if r0 == 0x0 goto pc+9
R0=map_value(ks=4,vs=128) R6=ctx R10=fp
11: (61) r1 = *(u32 *)(r6 +56)
12: (25) if r1 > 0x1f goto pc+7
R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
13: (67) r1 <<= 2
14: (0f) r0 += r1
15: (61) r3 = *(u32 *)(r0 +0)
R0 invalid mem access 'inv'

btw, if I change to using switch-case, basically listing all 32 cases, then
the program passes.

I wonder if I'm doing something wrong, or fundamentally BPF does not allow
us to do it?
currently there is such limitation, since in the following:
index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index];
verifier couldn't recognize that 'index' variable is actually capped
to a valid range.
It is possible to address though.
I'm actually working on something similar to make packet access
work with direct loads.


William Tu
 

Hi Alexei,

I see, thanks a lot!
I look forward to your work.

Regards,
William

On Mon, Apr 18, 2016 at 1:00 PM, Alexei Starovoitov <alexei.starovoitov@...> wrote:
On Mon, Apr 18, 2016 at 12:47 PM, William Tu via iovisor-dev
<iovisor-dev@...> wrote:
> Hi,
>
> I'm new to BPF and I'm trying to implement the following logic but fails due
> to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing
> list.)
>
> So I have an integer array of size 32 as the value of a bpf hashmap. I save
> the index of the array at skb->cb[0], so that another bpf can tail_call it
> with different index value. I've checked that the index is within the range
> and I couldn't understand why this fails. Any comments are appreciated!
>
> --- bpf code ---
> struct actions {
>     int action[32];
> };
> struct bpf_map_def SEC("maps") test_map = {
>     .type = BPF_MAP_TYPE_HASH,
>     .key_size = sizeof(uint32_t),
>     .value_size = sizeof(struct actions),
>     .max_entries = 1024,
> };
>
> SEC("socket2")
> int bpf_prog2(struct __sk_buff *skb)
> {
>     u32 key = 0;
>     int v = 0;
>     char fmt[] = "%d\n";
>     uint32_t index = 0;
>     struct actions *acts;
>     acts = bpf_map_lookup_elem(&test_map, &key);
>     if (!acts)
>         return 0;
>
>     index = skb->cb[0];
>     if (index >= 32)
>         return 0;
>
>     v = acts->action[index];
>     bpf_trace_printk(fmt, sizeof(fmt), v);
>     return 0;
> }
>
> --- error log ---
> bpf_prog_load() err=13
> 0: (bf) r6 = r1
> 1: (b7) r1 = 0
> 2: (63) *(u32 *)(r10 -4) = r1
> 3: (b7) r1 = 680997
> 4: (63) *(u32 *)(r10 -8) = r1
> 5: (bf) r2 = r10
> 6: (07) r2 += -4
> 7: (18) r1 = 0x1c10c5a0
> 9: (85) call 1
> 10: (15) if r0 == 0x0 goto pc+9
>  R0=map_value(ks=4,vs=128) R6=ctx R10=fp
> 11: (61) r1 = *(u32 *)(r6 +56)
> 12: (25) if r1 > 0x1f goto pc+7
>  R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
> 13: (67) r1 <<= 2
> 14: (0f) r0 += r1
> 15: (61) r3 = *(u32 *)(r0 +0)
> R0 invalid mem access 'inv'
>
> btw, if I change to using switch-case, basically listing all 32 cases, then
> the program passes.
>
> I wonder if I'm doing something wrong, or fundamentally BPF does not allow
> us to do it?

currently there is such limitation, since in the following:
     index = skb->cb[0];
     if (index >= 32)
         return 0;
     v = acts->action[index];
verifier couldn't recognize that 'index' variable is actually capped
to a valid range.
It is possible to address though.
I'm actually working on something similar to make packet access
work with direct loads.


William Tu
 

Hi Alexei,

I wonder if anyone is working on this issue currently?
Or I could start learning from your "direct packet access" patch and
see if could implement it? Thanks.

Regards,
William

On Mon, Apr 18, 2016 at 1:00 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Mon, Apr 18, 2016 at 12:47 PM, William Tu via iovisor-dev
<iovisor-dev@...> wrote:
Hi,

I'm new to BPF and I'm trying to implement the following logic but fails due
to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing
list.)

So I have an integer array of size 32 as the value of a bpf hashmap. I save
the index of the array at skb->cb[0], so that another bpf can tail_call it
with different index value. I've checked that the index is within the range
and I couldn't understand why this fails. Any comments are appreciated!

--- bpf code ---
struct actions {
int action[32];
};
struct bpf_map_def SEC("maps") test_map = {
.type = BPF_MAP_TYPE_HASH,
.key_size = sizeof(uint32_t),
.value_size = sizeof(struct actions),
.max_entries = 1024,
};

SEC("socket2")
int bpf_prog2(struct __sk_buff *skb)
{
u32 key = 0;
int v = 0;
char fmt[] = "%d\n";
uint32_t index = 0;
struct actions *acts;
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;

v = acts->action[index];
bpf_trace_printk(fmt, sizeof(fmt), v);
return 0;
}

--- error log ---
bpf_prog_load() err=13
0: (bf) r6 = r1
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -4) = r1
3: (b7) r1 = 680997
4: (63) *(u32 *)(r10 -8) = r1
5: (bf) r2 = r10
6: (07) r2 += -4
7: (18) r1 = 0x1c10c5a0
9: (85) call 1
10: (15) if r0 == 0x0 goto pc+9
R0=map_value(ks=4,vs=128) R6=ctx R10=fp
11: (61) r1 = *(u32 *)(r6 +56)
12: (25) if r1 > 0x1f goto pc+7
R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
13: (67) r1 <<= 2
14: (0f) r0 += r1
15: (61) r3 = *(u32 *)(r0 +0)
R0 invalid mem access 'inv'

btw, if I change to using switch-case, basically listing all 32 cases, then
the program passes.

I wonder if I'm doing something wrong, or fundamentally BPF does not allow
us to do it?
currently there is such limitation, since in the following:
index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index];
verifier couldn't recognize that 'index' variable is actually capped
to a valid range.
It is possible to address though.
I'm actually working on something similar to make packet access
work with direct loads.


Alexei Starovoitov
 

On Mon, Aug 8, 2016 at 10:56 AM, William Tu <u9012063@...> wrote:
Hi Alexei,

I wonder if anyone is working on this issue currently?
Or I could start learning from your "direct packet access" patch and
see if could implement it? Thanks.
This patch does direct packet access from helpers (like lookup and csum):
https://git.kernel.org/cgit/linux/kernel/git/ast/bpf.git/commit/?id=d2c24a2769693524d
it's waiting for net-next to reopen.

here is high level todo list:
https://github.com/iovisor/bcc/issues/574
the e1000+xdp patch that you've tested is not finished yet.
Would you be interested in taking it over?

Thanks

Regards,
William

On Mon, Apr 18, 2016 at 1:00 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Mon, Apr 18, 2016 at 12:47 PM, William Tu via iovisor-dev
<iovisor-dev@...> wrote:
Hi,

I'm new to BPF and I'm trying to implement the following logic but fails due
to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing
list.)

So I have an integer array of size 32 as the value of a bpf hashmap. I save
the index of the array at skb->cb[0], so that another bpf can tail_call it
with different index value. I've checked that the index is within the range
and I couldn't understand why this fails. Any comments are appreciated!

--- bpf code ---
struct actions {
int action[32];
};
struct bpf_map_def SEC("maps") test_map = {
.type = BPF_MAP_TYPE_HASH,
.key_size = sizeof(uint32_t),
.value_size = sizeof(struct actions),
.max_entries = 1024,
};

SEC("socket2")
int bpf_prog2(struct __sk_buff *skb)
{
u32 key = 0;
int v = 0;
char fmt[] = "%d\n";
uint32_t index = 0;
struct actions *acts;
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;

v = acts->action[index];
bpf_trace_printk(fmt, sizeof(fmt), v);
return 0;
}

--- error log ---
bpf_prog_load() err=13
0: (bf) r6 = r1
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -4) = r1
3: (b7) r1 = 680997
4: (63) *(u32 *)(r10 -8) = r1
5: (bf) r2 = r10
6: (07) r2 += -4
7: (18) r1 = 0x1c10c5a0
9: (85) call 1
10: (15) if r0 == 0x0 goto pc+9
R0=map_value(ks=4,vs=128) R6=ctx R10=fp
11: (61) r1 = *(u32 *)(r6 +56)
12: (25) if r1 > 0x1f goto pc+7
R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
13: (67) r1 <<= 2
14: (0f) r0 += r1
15: (61) r3 = *(u32 *)(r0 +0)
R0 invalid mem access 'inv'

btw, if I change to using switch-case, basically listing all 32 cases, then
the program passes.

I wonder if I'm doing something wrong, or fundamentally BPF does not allow
us to do it?
currently there is such limitation, since in the following:
index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index];
verifier couldn't recognize that 'index' variable is actually capped
to a valid range.
It is possible to address though.
I'm actually working on something similar to make packet access
work with direct loads.


William Tu
 

Hi Alexei,

Thanks.

This patch does direct packet access from helpers (like lookup and csum):
https://git.kernel.org/cgit/linux/kernel/git/ast/bpf.git/commit/?id=d2c24a2769693524d
it's waiting for net-next to reopen.
I'm confused. Isn't "commit 969bf05eb bpf: direct packet access"
already in net-next?


here is high level todo list:
https://github.com/iovisor/bcc/issues/574
the e1000+xdp patch that you've tested is not finished yet.
Would you be interested in taking it over?
I didn't see an item related to this verifier issue.
The problem I have is for a map's value containing an array, the
verifier isn't able to verify the array access is safe or not, even
though the index to the array is bounded correctly.

like the example here:
struct actions {
int action[32];
};
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index]; // fail verifier

It's not related to packet access, but I think from the verifier's
point of view, it's similar that once we check index is within correct
range, the access to the array is safe.

Regards,
William


Thanks

Regards,
William

On Mon, Apr 18, 2016 at 1:00 PM, Alexei Starovoitov
<alexei.starovoitov@...> wrote:
On Mon, Apr 18, 2016 at 12:47 PM, William Tu via iovisor-dev
<iovisor-dev@...> wrote:
Hi,

I'm new to BPF and I'm trying to implement the following logic but fails due
to "R0 invalid mem access 'inv'". (Apology if this is not the right mailing
list.)

So I have an integer array of size 32 as the value of a bpf hashmap. I save
the index of the array at skb->cb[0], so that another bpf can tail_call it
with different index value. I've checked that the index is within the range
and I couldn't understand why this fails. Any comments are appreciated!

--- bpf code ---
struct actions {
int action[32];
};
struct bpf_map_def SEC("maps") test_map = {
.type = BPF_MAP_TYPE_HASH,
.key_size = sizeof(uint32_t),
.value_size = sizeof(struct actions),
.max_entries = 1024,
};

SEC("socket2")
int bpf_prog2(struct __sk_buff *skb)
{
u32 key = 0;
int v = 0;
char fmt[] = "%d\n";
uint32_t index = 0;
struct actions *acts;
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;

v = acts->action[index];
bpf_trace_printk(fmt, sizeof(fmt), v);
return 0;
}

--- error log ---
bpf_prog_load() err=13
0: (bf) r6 = r1
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -4) = r1
3: (b7) r1 = 680997
4: (63) *(u32 *)(r10 -8) = r1
5: (bf) r2 = r10
6: (07) r2 += -4
7: (18) r1 = 0x1c10c5a0
9: (85) call 1
10: (15) if r0 == 0x0 goto pc+9
R0=map_value(ks=4,vs=128) R6=ctx R10=fp
11: (61) r1 = *(u32 *)(r6 +56)
12: (25) if r1 > 0x1f goto pc+7
R0=map_value(ks=4,vs=128) R1=inv R6=ctx R10=fp
13: (67) r1 <<= 2
14: (0f) r0 += r1
15: (61) r3 = *(u32 *)(r0 +0)
R0 invalid mem access 'inv'

btw, if I change to using switch-case, basically listing all 32 cases, then
the program passes.

I wonder if I'm doing something wrong, or fundamentally BPF does not allow
us to do it?
currently there is such limitation, since in the following:
index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index];
verifier couldn't recognize that 'index' variable is actually capped
to a valid range.
It is possible to address though.
I'm actually working on something similar to make packet access
work with direct loads.


Alexei Starovoitov
 

On Mon, Aug 8, 2016 at 11:29 AM, William Tu <u9012063@...> wrote:
Hi Alexei,

Thanks.

This patch does direct packet access from helpers (like lookup and csum):
https://git.kernel.org/cgit/linux/kernel/git/ast/bpf.git/commit/?id=d2c24a2769693524d
it's waiting for net-next to reopen.
I'm confused. Isn't "commit 969bf05eb bpf: direct packet access"
already in net-next?
nope. haven't sent it to the list yet.


here is high level todo list:
https://github.com/iovisor/bcc/issues/574
the e1000+xdp patch that you've tested is not finished yet.
Would you be interested in taking it over?
I didn't see an item related to this verifier issue.
The problem I have is for a map's value containing an array, the
verifier isn't able to verify the array access is safe or not, even
though the index to the array is bounded correctly.

like the example here:
struct actions {
int action[32];
};
acts = bpf_map_lookup_elem(&test_map, &key);
if (!acts)
return 0;

index = skb->cb[0];
if (index >= 32)
return 0;
v = acts->action[index]; // fail verifier

It's not related to packet access, but I think from the verifier's
point of view, it's similar that once we check index is within correct
range, the access to the array is safe.
I see. yes. that would be useful.
Looking forward to your patch.