From bb2f930d6dd708469a587dc9ed1efe1ef969c0bf Mon Sep 17 00:00:00 2001 From: Davide Caratti Date: Wed, 27 May 2020 02:04:26 +0200 Subject: net/sched: fix infinite loop in sch_fq_pie this command hangs forever: # tc qdisc add dev eth0 root fq_pie flows 65536 watchdog: BUG: soft lockup - CPU#1 stuck for 23s! [tc:1028] [...] CPU: 1 PID: 1028 Comm: tc Not tainted 5.7.0-rc6+ #167 RIP: 0010:fq_pie_init+0x60e/0x8b7 [sch_fq_pie] Code: 4c 89 65 50 48 89 f8 48 c1 e8 03 42 80 3c 30 00 0f 85 2a 02 00 00 48 8d 7d 10 4c 89 65 58 48 89 f8 48 c1 e8 03 42 80 3c 30 00 <0f> 85 a7 01 00 00 48 8d 7d 18 48 c7 45 10 46 c3 23 00 48 89 f8 48 RSP: 0018:ffff888138d67468 EFLAGS: 00000246 ORIG_RAX: ffffffffffffff13 RAX: 1ffff9200018d2b2 RBX: ffff888139c1c400 RCX: ffffffffffffffff RDX: 000000000000c5e8 RSI: ffffc900000e5000 RDI: ffffc90000c69590 RBP: ffffc90000c69580 R08: fffffbfff79a9699 R09: fffffbfff79a9699 R10: 0000000000000700 R11: fffffbfff79a9698 R12: ffffc90000c695d0 R13: 0000000000000000 R14: dffffc0000000000 R15: 000000002347c5e8 FS: 00007f01e1850e40(0000) GS:ffff88814c880000(0000) knlGS:0000000000000000 CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033 CR2: 000000000067c340 CR3: 000000013864c000 CR4: 0000000000340ee0 Call Trace: qdisc_create+0x3fd/0xeb0 tc_modify_qdisc+0x3be/0x14a0 rtnetlink_rcv_msg+0x5f3/0x920 netlink_rcv_skb+0x121/0x350 netlink_unicast+0x439/0x630 netlink_sendmsg+0x714/0xbf0 sock_sendmsg+0xe2/0x110 ____sys_sendmsg+0x5b4/0x890 ___sys_sendmsg+0xe9/0x160 __sys_sendmsg+0xd3/0x170 do_syscall_64+0x9a/0x370 entry_SYSCALL_64_after_hwframe+0x44/0xa9 we can't accept 65536 as a valid number for 'nflows', because the loop on 'idx' in fq_pie_init() will never end. The extack message is correct, but it doesn't say that 0 is not a valid number for 'flows': while at it, fix this also. Add a tdc selftest to check correct validation of 'flows'. CC: Ivan Vecera Fixes: ec97ecf1ebe4 ("net: sched: add Flow Queue PIE packet scheduler") Signed-off-by: Davide Caratti Reviewed-by: Ivan Vecera Signed-off-by: David S. Miller --- .../tc-testing/tc-tests/qdiscs/fq_pie.json | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 tools/testing/selftests/tc-testing/tc-tests/qdiscs/fq_pie.json (limited to 'tools') diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/fq_pie.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/fq_pie.json new file mode 100644 index 000000000000..1cda2e11b3ad --- /dev/null +++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/fq_pie.json @@ -0,0 +1,21 @@ +[ + { + "id": "83be", + "name": "Create FQ-PIE with invalid number of flows", + "category": [ + "qdisc", + "fq_pie" + ], + "setup": [ + "$IP link add dev $DUMMY type dummy || /bin/true" + ], + "cmdUnderTest": "$TC qdisc add dev $DUMMY root fq_pie flows 65536", + "expExitCode": "2", + "verifyCmd": "$TC qdisc show dev $DUMMY", + "matchPattern": "qdisc", + "matchCount": "0", + "teardown": [ + "$IP link del dev $DUMMY" + ] + } +] -- cgit v1.3-18-gd494 From e3effcdfe02eb20f23d4f1833c75658ddc49e65a Mon Sep 17 00:00:00 2001 From: John Fastabend Date: Fri, 29 May 2020 10:28:59 -0700 Subject: bpf, selftests: Verifier bounds tests need to be updated After previous fix for zero extension test_verifier tests #65 and #66 now fail. Before the fix we can see the alu32 mov op at insn 10 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0, smin_value=4294967168,smax_value=4294967423, umin_value=4294967168,umax_value=4294967423, var_off=(0x0; 0x1ffffffff), s32_min_value=-2147483648,s32_max_value=2147483647, u32_min_value=0,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm 10: (bc) w1 = w1 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0, smin_value=0,smax_value=2147483647, umin_value=0,umax_value=4294967295, var_off=(0x0; 0xffffffff), s32_min_value=-2147483648,s32_max_value=2147483647, u32_min_value=0,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm After the fix at insn 10 because we have 's32_min_value < 0' the following step 11 now has 'smax_value=U32_MAX' where before we pulled the s32_max_value bound into the smax_value as seen above in 11 with smax_value=2147483647. 10: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0, smin_value=4294967168,smax_value=4294967423, umin_value=4294967168,umax_value=4294967423, var_off=(0x0; 0x1ffffffff), s32_min_value=-2147483648, s32_max_value=2147483647, u32_min_value=0,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm 10: (bc) w1 = w1 11: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0, smin_value=0,smax_value=4294967295, umin_value=0,umax_value=4294967295, var_off=(0x0; 0xffffffff), s32_min_value=-2147483648, s32_max_value=2147483647, u32_min_value=0, u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm The fall out of this is by the time we get to the failing instruction at step 14 where previously we had the following: 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0, smin_value=72057594021150720,smax_value=72057594029539328, umin_value=72057594021150720,umax_value=72057594029539328, var_off=(0xffffffff000000; 0xffffff), s32_min_value=-16777216,s32_max_value=-1, u32_min_value=-16777216,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm 14: (0f) r0 += r1 We now have, 14: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=inv(id=0, smin_value=0,smax_value=72057594037927935, umin_value=0,umax_value=72057594037927935, var_off=(0x0; 0xffffffffffffff), s32_min_value=-2147483648,s32_max_value=2147483647, u32_min_value=0,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm 14: (0f) r0 += r1 In the original step 14 'smin_value=72057594021150720' this trips the logic in the verifier function check_reg_sane_offset(), if (smin >= BPF_MAX_VAR_OFF || smin <= -BPF_MAX_VAR_OFF) { verbose(env, "value %lld makes %s pointer be out of bounds\n", smin, reg_type_str[type]); return false; } Specifically, the 'smin <= -BPF_MAX_VAR_OFF' check. But with the fix at step 14 we have bounds 'smin_value=0' so the above check is not tripped because BPF_MAX_VAR_OFF=1<<29. We have a smin_value=0 here because at step 10 the smaller smin_value=0 means the subtractions at steps 11 and 12 bring the smin_value negative. 11: (17) r1 -= 2147483584 12: (17) r1 -= 2147483584 13: (77) r1 >>= 8 Then the shift clears the top bit and smin_value is set to 0. Note we still have the smax_value in the fixed code so any reads will fail. An alternative would be to have reg_sane_check() do both smin and smax value tests. To fix the test we can omit the 'r1 >>=8' at line 13. This will change the err string, but keeps the intention of the test as suggseted by the title, "check after truncation of boundary-crossing range". If the verifier logic changes a different value is likely to be thrown in the error or the error will no longer be thrown forcing this test to be examined. With this change we see the new state at step 13. 13: R0_w=map_value(id=0,off=0,ks=8,vs=8,imm=0) R1_w=invP(id=0, smin_value=-4294967168,smax_value=127, umin_value=0,umax_value=18446744073709551615, s32_min_value=-2147483648,s32_max_value=2147483647, u32_min_value=0,u32_max_value=-1) R10=fp0 fp-8_w=mmmmmmmm Giving the expected out of bounds error, "value -4294967168 makes map_value pointer be out of bounds" However, for unpriv case we see a different error now because of the mixed signed bounds pointer arithmatic. This seems OK so I've only added the unpriv_errstr for this. Another optino may have been to do addition on r1 instead of subtraction but I favor the approach above slightly. Signed-off-by: John Fastabend Signed-off-by: Alexei Starovoitov Acked-by: Yonghong Song Link: https://lore.kernel.org/bpf/159077333942.6014.14004320043595756079.stgit@john-Precision-5820-Tower --- tools/testing/selftests/bpf/verifier/bounds.c | 24 ++++++++++-------------- 1 file changed, 10 insertions(+), 14 deletions(-) (limited to 'tools') diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c index a253a064e6e0..fafa5409bdac 100644 --- a/tools/testing/selftests/bpf/verifier/bounds.c +++ b/tools/testing/selftests/bpf/verifier/bounds.c @@ -238,7 +238,7 @@ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), BPF_LD_MAP_FD(BPF_REG_1, 0), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), - BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8), /* r1 = [0x00, 0xff] */ BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 0xffffff80 >> 1), @@ -253,10 +253,6 @@ * [0xffff'ffff'0000'0080, 0xffff'ffff'ffff'ffff] */ BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 0xffffff80 >> 1), - /* r1 = 0 or - * [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff] - */ - BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8), /* error on OOB pointer computation */ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), /* exit */ @@ -265,8 +261,10 @@ }, .fixup_map_hash_8b = { 3 }, /* not actually fully unbounded, but the bound is very high */ - .errstr = "value 72057594021150720 makes map_value pointer be out of bounds", - .result = REJECT + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root", + .result_unpriv = REJECT, + .errstr = "value -4294967168 makes map_value pointer be out of bounds", + .result = REJECT, }, { "bounds check after truncation of boundary-crossing range (2)", @@ -276,7 +274,7 @@ BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8), BPF_LD_MAP_FD(BPF_REG_1, 0), BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem), - BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 9), + BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 8), /* r1 = [0x00, 0xff] */ BPF_LDX_MEM(BPF_B, BPF_REG_1, BPF_REG_0, 0), BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, 0xffffff80 >> 1), @@ -293,10 +291,6 @@ * [0xffff'ffff'0000'0080, 0xffff'ffff'ffff'ffff] */ BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 0xffffff80 >> 1), - /* r1 = 0 or - * [0x00ff'ffff'ff00'0000, 0x00ff'ffff'ffff'ffff] - */ - BPF_ALU64_IMM(BPF_RSH, BPF_REG_1, 8), /* error on OOB pointer computation */ BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1), /* exit */ @@ -305,8 +299,10 @@ }, .fixup_map_hash_8b = { 3 }, /* not actually fully unbounded, but the bound is very high */ - .errstr = "value 72057594021150720 makes map_value pointer be out of bounds", - .result = REJECT + .errstr_unpriv = "R1 has unknown scalar with mixed signed bounds, pointer arithmetic with it prohibited for !root", + .result_unpriv = REJECT, + .errstr = "value -4294967168 makes map_value pointer be out of bounds", + .result = REJECT, }, { "bounds check after wrapping 32-bit addition", -- cgit v1.3-18-gd494 From cf66c29bd7534813d2e1971fab71e25fe87c7e0a Mon Sep 17 00:00:00 2001 From: John Fastabend Date: Fri, 29 May 2020 10:29:18 -0700 Subject: bpf, selftests: Add a verifier test for assigning 32bit reg states to 64bit ones Added a verifier test for assigning 32bit reg states to 64bit where 32bit reg holds a constant value of 0. Without previous kernel verifier.c fix, the test in this patch will fail. Signed-off-by: Yonghong Song Signed-off-by: John Fastabend Signed-off-by: Alexei Starovoitov Link: https://lore.kernel.org/bpf/159077335867.6014.2075350327073125374.stgit@john-Precision-5820-Tower --- tools/testing/selftests/bpf/verifier/bounds.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'tools') diff --git a/tools/testing/selftests/bpf/verifier/bounds.c b/tools/testing/selftests/bpf/verifier/bounds.c index fafa5409bdac..58f4aa593b1b 100644 --- a/tools/testing/selftests/bpf/verifier/bounds.c +++ b/tools/testing/selftests/bpf/verifier/bounds.c @@ -535,3 +535,25 @@ }, .result = ACCEPT }, +{ + "assigning 32bit bounds to 64bit for wA = 0, wB = wA", + .insns = { + BPF_LDX_MEM(BPF_W, BPF_REG_8, BPF_REG_1, + offsetof(struct __sk_buff, data_end)), + BPF_LDX_MEM(BPF_W, BPF_REG_7, BPF_REG_1, + offsetof(struct __sk_buff, data)), + BPF_MOV32_IMM(BPF_REG_9, 0), + BPF_MOV32_REG(BPF_REG_2, BPF_REG_9), + BPF_MOV64_REG(BPF_REG_6, BPF_REG_7), + BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_2), + BPF_MOV64_REG(BPF_REG_3, BPF_REG_6), + BPF_ALU64_IMM(BPF_ADD, BPF_REG_3, 8), + BPF_JMP_REG(BPF_JGT, BPF_REG_3, BPF_REG_8, 1), + BPF_LDX_MEM(BPF_W, BPF_REG_5, BPF_REG_6, 0), + BPF_MOV64_IMM(BPF_REG_0, 0), + BPF_EXIT_INSN(), + }, + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + .result = ACCEPT, + .flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS, +}, -- cgit v1.3-18-gd494