errors when storing comm in map key

[brendangregg]

Test program, testkey:

#!/usr/bin/python

from __future__ import print_function
from bcc import BPF
from time import sleep

# load BPF program
b = BPF(text = """
#include <uapi/linux/ptrace.h>
#include <linux/sched.h>

struct key_t {
    u32 pid;
    char name[TASK_COMM_LEN];
};
BPF_HASH(counts, struct key_t);

int trace_count(struct pt_regs *ctx) {
    u32 pid = bpf_get_current_pid_tgid();
    struct key_t key = {};
    u64 zero = 0, *val;
    key.pid = pid;
    if (bpf_get_current_comm(&key.name, sizeof(key.name)) == 0) {
        val = counts.lookup_or_init(&key, &zero);
        (*val)++;
    }
    return 0;
}
""")
b.attach_kprobe(event_re='^[sS]y[sS]_read', fn_name="trace_count")
sleep(1)
counts = b.get_table("counts")
for k, v in sorted(counts.items(), key=lambda counts: counts[1].value):
    print("%-6d %-16s %8d" % (k.pid, k.name, v.value))

This gets:

bpf: Permission denied
0: (85) call 14
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -8) = r1
3: (7b) *(u64 *)(r10 -16) = r1
4: (7b) *(u64 *)(r10 -24) = r1
5: (7b) *(u64 *)(r10 -32) = r1
6: (63) *(u32 *)(r10 -24) = r0
7: (bf) r1 = r10
8: (07) r1 += -24
9: (47) r1 |= 4
10: (b7) r2 = 16
11: (85) call 16
R1 type=inv expected=fp
[...]

But if I swap the pid and name members in the key around (ie, name is first):

# ./testkey 
1936028263 112                     1
1735355497 109                     1
1735355497 109                     1
1936291442 115                     3
7955819 116                     3
1936291442 115                     3
1936261234 109                     6
1768383593 115                     7
1936261230 99                      7
1768383593 115                     7
1936291442 114                    12
1936291442 114                    14
1668248176 114                   128
Segmentation fault

[yonghong-song]

I cannot reproduce the issue.

yhs@ubuntu:~/work/bcc/examples$ cat ex.py
#!/usr/bin/python

from future import print_function
from bcc import BPF
from time import sleep

load BPF program

b = BPF(text = """
#include <uapi/linux/ptrace.h>
#include <linux/sched.h>

struct key_t {
char name[TASK_COMM_LEN];
u32 pid;
};
BPF_HASH(counts, struct key_t);

int trace_count(struct pt_regs _ctx) {
u32 pid = bpf_get_current_pid_tgid();
struct key_t key = {};
u64 zero = 0, *val;
key.pid = pid;
if (bpf_get_current_comm(&key.name, sizeof(key.name)) == 0) {
val = counts.lookup_or_init(&key, &zero);
(_val)++;
}
return 0;
}
""")
b.attach_kprobe(event_re='^[sS]y[sS]_read', fn_name="trace_count")
sleep(1)
counts = b.get_table("counts")
for k, v in sorted(counts.items(), key=lambda counts: counts[1].value):
print("%-6d %-16s %8d" % (k.pid, k.name, v.value))
yhs@ubuntu:/work/bcc/examples$ sudo ./ex.py
1946186341 100 1
1953038457 101 3
yhs@ubuntu:/work/bcc/examples$ sudo ./ex.py
1946186341 100 1
1953038457 101 3
1851878497 105 15
yhs@ubuntu:/work/bcc/examples$ sudo ./ex.py
1946186341 100 1
1936028263 112 1
1953038457 101 3
yhs@ubuntu:/work/bcc/examples$

Using debug=2, the bpf disassembly code is dumped.

yhs@ubuntu:~/work/bcc/examples$ sudo ./ex.py
0: (85) call 14
1: (b7) r1 = 0
2: (7b) *(u64 *)(r10 -16) = r1
3: (7b) *(u64 *)(r10 -24) = r1
4: (7b) *(u64 *)(r10 -32) = r1
5: (63) *(u32 *)(r10 -8) = r0
6: (bf) r1 = r10
7: (07) r1 += -24
8: (b7) r2 = 16
9: (85) call 16
10: (67) r0 <<= 32
11: (77) r0 >>= 32
12: (55) if r0 != 0x0 goto pc+23
R0=imm0 R10=fp
.....

The above disassembly code looks correct to me.
(location r10-32 is for local variable "zero".)

linux/sched.h:#define TASK_COMM_LEN 16

There is a padding r10 - r10+4 in the data structure.

In your case, the bpf code looks like:

0: (85) call 14
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -8) = r1
3: (7b) *(u64 *)(r10 -16) = r1
4: (7b) *(u64 *)(r10 -24) = r1
5: (7b) *(u64 *)(r10 -32) = r1
6: (63) *(u32 *)(r10 -24) = r0
7: (bf) r1 = r10
8: (07) r1 += -24
9: (47) r1 |= 4
10: (b7) r2 = 16
11: (85) call 16
R1 type=inv expected=fp
[...]

This is not correct.
2: (63) *(u32 *)(r10 -8) = r1
3: (7b) *(u64 *)(r10 -16) = r1
4: (7b) *(u64 *)(r10 -24) = r1
5: (7b) *(u64 *)(r10 -32) = r1
6: (63) *(u32 *)(r10 -24) = r0

9: (47) r1 |= 4

With debug=4, rewriter does not touch this piece of source code:

#include <uapi/linux/ptrace.h>
#include <linux/sched.h>

struct key_t {
char name[TASK_COMM_LEN];
u32 pid;
};
BPF_HASH(counts, struct key_t);

attribute((section(".bpf.fn.trace_count")))
int trace_count(struct pt_regs ctx) {
u32 pid = bpf_get_current_pid_tgid();
struct key_t key = {};
u64 zero = 0, *val;
key.pid = pid;
if (bpf_get_current_comm(&key.name, sizeof(key.name)) == 0) {
val = ({typeof(counts.leaf) *leaf =
bpf_map_lookup_elem(bpf_pseudo_fd(1, 3), &key); if (!leaf) {
bpf_map_update_elem_(bpf_pseudo_fd(1, 3), &key, &zero, BPF_NOEXIST); leaf =
bpf_map_lookup_elem_(bpf_pseudo_fd(1, 3), &key); if (!leaf) return
0;}leaf;});
(_val)++;
}
return 0;
}

I am using latest bcc source code, and my llvm/clang is built a while back
from source (see INSTALL.md):
yhs@ubuntu:$ clang -v
clang version 3.8.0 (http://llvm.org/git/clang.git
1694b9d193ea9f50314856b0f2d769ba20e92778) (http://llvm.org/git/llvm.git
69d051c87d28550b8721143a4d3135b4fa593af0)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/yhs/temp/llvm/build/install/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8.4
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.9.1
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/4.8
Candidate multilib: .;@m64
Selected multilib: .;@m64
yhs@ubuntu:$

Which llvm/clang did you use?

On Fri, Sep 18, 2015 at 2:48 PM, Brendan Gregg notifications@github.com
wrote:

Test program:

#!/usr/bin/python
from future import print_functionfrom bcc import BPFfrom time import sleep

load BPF program

b = BPF(text = """#include <uapi/linux/ptrace.h>#include <linux/sched.h>struct key_t { char name[TASK_COMM_LEN]; u32 pid;};BPF_HASH(counts, struct key_t);int trace_count(struct pt_regs _ctx) { u32 pid = bpf_get_current_pid_tgid(); struct key_t key = {}; u64 zero = 0, *val; key.pid = pid; if (bpf_get_current_comm(&key.name, sizeof(key.name)) == 0) { val = counts.lookup_or_init(&key, &zero); (_val)++; } return 0;}""")
b.attach_kprobe(event_re='^[sS]y[sS]_read', fn_name="trace_count")
sleep(1)
counts = b.get_table("counts")for k, v in sorted(counts.items(), key=lambda counts: counts[1].value):
print("%-6d %-16s %8d" % (k.pid, k.name, v.value))

This gets:

bpf: Permission denied
0: (85) call 14
1: (b7) r1 = 0
2: (63) *(u32 *)(r10 -8) = r1
3: (7b) *(u64 *)(r10 -16) = r1
4: (7b) *(u64 *)(r10 -24) = r1
5: (7b) *(u64 *)(r10 -32) = r1
6: (63) *(u32 *)(r10 -24) = r0
7: (bf) r1 = r10
8: (07) r1 += -24
9: (47) r1 |= 4
10: (b7) r2 = 16
11: (85) call 16
R1 type=inv expected=fp
[...]

But if I swap the pid and name members in the key around (ie, name is
first):

./testkey

1936028263 112 1
1735355497 109 1
1735355497 109 1
1936291442 115 3
7955819 116 3
1936291442 115 3
1936261234 109 6
1768383593 115 7
1936261230 99 7
1768383593 115 7
1936291442 114 12
1936291442 114 14
1668248176 114 128
Segmentation fault

—
Reply to this email directly or view it on GitHub
#234.

[brendangregg]

Sorry, I had pid and name in key_t switched the wrong way in the ticket; I updated the ticket. So you tried the second case first, and didn't hit the segfault, which I suppose is good (but the output is still not right). I'm using an llvm/clang I built from source about a week ago.

[yonghong-song]

@brendangregg, https://github.com/brendangregg I can reproduce the issue
now. Am looking.

On Fri, Sep 18, 2015 at 3:59 PM, Brendan Gregg notifications@github.com
wrote:

Sorry, I had pid and name in key_t switched the wrong way in the ticket; I
updated the ticket. So you tried the second case first, and didn't hit the
segfault, which I suppose is good (but the output is still not right). I'm
using an llvm/clang I built from source about a week ago.

—
Reply to this email directly or view it on GitHub
#234 (comment).

[yonghong-song]

The reason for failure is again due to specific compile code
generation/optimization.

For
.....
struct key_t {
u32 pid;
char name[TASK_COMM_LEN];
};
BPF_HASH(counts, struct key_t);

int trace_count(struct pt_regs _ctx) {
u32 pid = bpf_get_current_pid_tgid();
struct key_t key = {};
u64 zero = 0, *val;
key.pid = pid;
if (bpf_get_current_comm(&key.name, sizeof(key.name)) == 0) {
val = counts.lookup_or_init(&key, &zero);
(_val)++;
}
return 0;
}

The "struct key_t key = {}" will be allocated with 20 bytes.
For the above specific code, with debug=1, you can dump LLVM IR:

; Function Attrs: alwaysinline nounwind uwtable
define i32 @trace_count(%struct.pt_regs* nocapture readnone %ctx) #3
section ".bpf.fn.trace_count" {
%key = alloca %struct.key_t, align 4
%zero = alloca i64, align 8
%1 = tail call i64 inttoptr (i64 14 to i64 ())() #7
%2 = trunc i64 %1 to i32
%3 = bitcast %struct.key_t %key to i8*
call void @llvm.memset.p0i8.i64(i8* %3, i8 0, i64 20, i32 4, i1 false)
store i64 0, i64* %zero, align 8
%4 = getelementptr inbounds %struct.key_t, %struct.key_t* %key, i64 0,
i32 0
store i32 %2, i32* %4, align 4
%5 = getelementptr inbounds %struct.key_t, %struct.key_t* %key, i64 0,
i32 1, i64 0
%6 = call i32 inttoptr (i64 16 to i32 (i8_, i32)_)(i8* %5, i32 16) #7
%7 = icmp eq i32 %6, 0
br i1 %7, label %8, label %21

The &key will be 8 bytes aligned.
This will cause key.name is 4 bytes aligned.
Unfortunately, the compiler generates
9: (47) r1 |= 4

If it generates:
9: (47) r1 += 4

We should be fine.

I do not have workaround except to reorder two fields in key_t structure to
please the compiler.
Another way is to improve the LLVM compiler.

On Fri, Sep 18, 2015 at 3:59 PM, Brendan Gregg notifications@github.com
wrote:

Sorry, I had pid and name in key_t switched the wrong way in the ticket; I
updated the ticket. So you tried the second case first, and didn't hit the
segfault, which I suppose is good (but the output is still not right). I'm
using an llvm/clang I built from source about a week ago.

—
Reply to this email directly or view it on GitHub
#234 (comment).

[yonghong-song]

The following kernel patch can recognize the above pattern and make verifier happy:

yhs@ubuntu:~/work/net-next$ git diff
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index b074b23..fb553029 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1064,14 +1064,34 @@ static int check_alu_op(struct reg_state *regs, struct bpf_insn *insn)
                    BPF_SRC(insn->code) == BPF_K)
                        stack_relative = true;

-               /* check dest operand */
-               err = check_reg_arg(regs, insn->dst_reg, DST_OP);
-               if (err)
-                       return err;
+               /* pattern match 'bpf_or Rx, imm' instruction
+                * 7: (bf) r1 = r10
+                * 8: (07) r1 += -24
+                * 9: (47) r1 |= 4
+                */
+               if (opcode == BPF_OR && BPF_CLASS(insn->code) == BPF_ALU64 &&
+                   regs[insn->dst_reg].type == PTR_TO_STACK &&
+                   insn->imm != 0 &&
+                   regs[insn->dst_reg].imm % (insn->imm << 1) == 0 &&
+                   BPF_SRC(insn->code) == BPF_K)
+                       stack_relative = true;
+
+               /* 7: (bf) r1 = r10
+                * 8: (07) r1 += -24
+                */
+               if (!stack_relative || !regs[insn->dst_reg].type == PTR_TO_STACK) {
+                       /* check dest operand */
+                       err = check_reg_arg(regs, insn->dst_reg, DST_OP);
+                       if (err)
+                               return err;
+               }

                if (stack_relative) {
-                       regs[insn->dst_reg].type = PTR_TO_STACK;
-                       regs[insn->dst_reg].imm = insn->imm;
+                       if (regs[insn->dst_reg].type == FRAME_PTR) {
+                               regs[insn->dst_reg].type = PTR_TO_STACK;
+                               regs[insn->dst_reg].imm = insn->imm;
+                       } else
+                               regs[insn->dst_reg].imm += insn->imm;
                }
        }

yhs@ubuntu:~/work/net-next$ 

Basically, it permits composition of relative stack pointers and recognize the "|" operator
specially.

Will need to discuss with Alexey about this whether we should fix in compiler side (to generate
verifier friendly code) or in kernel side.

[yonghong-song]

The LLVM fix has been pushed to the trunk.
http://reviews.llvm.org/rL249371
Please sync with latest llvm trunk repo.

[yonghong-song]

Fixed in llvm trunk (3.8)