net_sched: sch_sfq: reject limit of 1
Subsystems (4)
cover net_sched: sch_sfq: reject limit of 1
The implementation does not properly support limits of 1. Add an in-kernel check, in addition to existing iproute2 check, since other tools may be used for configuration.
This patch set also adds a selfcheck to test that a limit of 1 is rejected.
An alternative (or in addition) we could fix the implementation by setting q->tail to NULL in sfq_drop if this is the last slot we marked empty, e.g.:
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -317,8 +317,11 @@ static unsigned int sfq_drop(struct Qdisc *sch, struct sk_buff **to_free)
/* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
x = q->tail->next;
slot = &q->slots[x];
- q->tail->next = slot->next;
q->ht[slot->hash] = SFQ_EMPTY_SLOT;
+ if (x == slot->next)
+ q->tail = NULL; /* no more active slots */
+ else
+ q->tail->next = slot->next;
goto drop;
}Octavian Purdila (2):
net_sched: sch_sfq: don't allow 1 packet limit selftests/tc-testing: sfq: test that kernel rejects limit of 1
net/sched/sch_sfq.c | 4 ++++ .../tc-testing/scripts/sfq_rejects_limit_1.py | 21 +++++++++++++++++++ .../tc-testing/tc-tests/qdiscs/sfq.json | 20 ++++++++++++++++++ 3 files changed, 45 insertions(+) create mode 100755 tools/testing/selftests/tc-testing/scripts/sfq_rejects_limit_1.py
Signature · 1 line
2.47.0.338.g60cca15819-goog
PATCH 1/2 net_sched: sch_sfq: don't allow 1 packet limit
The current implementation does not work correctly with a limit of
1. iproute2 actually checks for this and this patch adds the check in kernel as well.
This fixes the following syzkaller reported crash:
UBSAN: array-index-out-of-bounds in net/sched/sch_sfq.c:210:6 index 65535 is out of range for type 'struct sfq_head[128]' CPU: 0 PID: 2569 Comm: syz-executor101 Not tainted 5.10.0-smp-DEV #1 Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 09/13/2024 Call Trace: __dump_stack lib/dump_stack.c:79 [inline] dump_stack+0x125/0x19f lib/dump_stack.c:120 ubsan_epilogue lib/ubsan.c:148 [inline] __ubsan_handle_out_of_bounds+0xed/0x120 lib/ubsan.c:347 sfq_link net/sched/sch_sfq.c:210 [inline] sfq_dec+0x528/0x600 net/sched/sch_sfq.c:238 sfq_dequeue+0x39b/0x9d0 net/sched/sch_sfq.c:500 sfq_reset+0x13/0x50 net/sched/sch_sfq.c:525 qdisc_reset+0xfe/0x510 net/sched/sch_generic.c:1026 tbf_reset+0x3d/0x100 net/sched/sch_tbf.c:319 qdisc_reset+0xfe/0x510 net/sched/sch_generic.c:1026 dev_reset_queue+0x8c/0x140 net/sched/sch_generic.c:1296 netdev_for_each_tx_queue include/linux/netdevice.h:2350 [inline] dev_deactivate_many+0x6dc/0xc20 net/sched/sch_generic.c:1362 __dev_close_many+0x214/0x350 net/core/dev.c:1468 dev_close_many+0x207/0x510 net/core/dev.c:1506 unregister_netdevice_many+0x40f/0x16b0 net/core/dev.c:10738 unregister_netdevice_queue+0x2be/0x310 net/core/dev.c:10695 unregister_netdevice include/linux/netdevice.h:2893 [inline] __tun_detach+0x6b6/0x1600 drivers/net/tun.c:689 tun_detach drivers/net/tun.c:705 [inline] tun_chr_close+0x104/0x1b0 drivers/net/tun.c:3640 __fput+0x203/0x840 fs/file_table.c:280 task_work_run+0x129/0x1b0 kernel/task_work.c:185 exit_task_work include/linux/task_work.h:33 [inline] do_exit+0x5ce/0x2200 kernel/exit.c:931 do_group_exit+0x144/0x310 kernel/exit.c:1046 __do_sys_exit_group kernel/exit.c:1057 [inline] __se_sys_exit_group kernel/exit.c:1055 [inline] __x64_sys_exit_group+0x3b/0x40 kernel/exit.c:1055 do_syscall_64+0x6c/0xd0 entry_SYSCALL_64_after_hwframe+0x61/0xcb RIP: 0033:0x7fe5e7b52479 Code: Unable to access opcode bytes at RIP 0x7fe5e7b5244f. RSP: 002b:00007ffd3c800398 EFLAGS: 00000246 ORIG_RAX: 00000000000000e7 RAX: ffffffffffffffda RBX: 0000000000000000 RCX: 00007fe5e7b52479 RDX: 000000000000003c RSI: 00000000000000e7 RDI: 0000000000000000 RBP: 00007fe5e7bcd2d0 R08: ffffffffffffffb8 R09: 0000000000000014 R10: 0000000000000000 R11: 0000000000000246 R12: 00007fe5e7bcd2d0 R13: 0000000000000000 R14: 00007fe5e7bcdd20 R15: 00007fe5e7b24270
The crash can be also be reproduced with the following (with a tc recompiled to allow for sfq limits of 1):
tc qdisc add dev dummy0 handle 1: root tbf rate 1Kbit burst 100b lat 1s ../iproute2-6.9.0/tc/tc qdisc add dev dummy0 handle 2: parent 1:10 sfq limit 1 ifconfig dummy0 up
ping -I dummy0 -f -c2 -W0.1 8.8.8.8
sleep 1
Scenario that triggers the crash:
* the first packet is sent and queued in TBF and SFQ; qdisc qlen is 1
* TBF dequeues: it peeks from SFQ which moves the packet to the gso_skb list and keeps qdisc qlen set to 1. TBF is out of tokens so it schedules itself for later.
* the second packet is sent and TBF tries to queues it to SFQ. qdisc qlen is now 2 and because the SFQ limit is 1 the packet is dropped by SFQ. At this point qlen is 1, and all of the SFQ slots are empty, however q->tail is not NULL.
At this point, assuming no more packets are queued, when sch_dequeue runs again it will decrement the qlen for the current empty slot causing an underflow and the subsequent out of bounds access.
--- net/sched/sch_sfq.c | 4 ++++ 1 file changed, 4 insertions(+)
net/sched/sch_sfq.c +4 -0
@@ -652,6 +652,10 @@ static int sfq_change(struct Qdisc *sch, struct nlattr *opt,if (!p)return -ENOMEM ; } +if (ctl->limit ==1 ) { +NL_SET_ERR_MSG_MOD (extack,"invalid limit" ); +return -EINVAL ; + }sch_tree_lock (sch);if (ctl->quantum) q->quantum = ctl->quantum;
Signature · 1 line
2.47.0.338.g60cca15819-goog
Re: [PATCH net-next 1/2] net_sched: sch_sfq: don't allow 1 packet limit
Quoted 30 lines · Octavian Purdila
The current implementation does not work correctly with a limit of
1. iproute2 actually checks for this and this patch adds the check in kernel as well.This fixes the following syzkaller reported crash:
The crash can be also be reproduced with the following (with a tc recompiled to allow for sfq limits of 1):
tc qdisc add dev dummy0 handle 1: root tbf rate 1Kbit burst 100b lat 1s ../iproute2-6.9.0/tc/tc qdisc add dev dummy0 handle 2: parent 1:10 sfq limit 1 ifconfig dummy0 up
ping -I dummy0 -f -c2 -W0.1 8.8.8.8
sleep 1Scenario that triggers the crash:
* the first packet is sent and queued in TBF and SFQ; qdisc qlen is 1
* TBF dequeues: it peeks from SFQ which moves the packet to the
gso_skblist and keeps qdisc qlen set to 1. TBF is out of tokens so it schedules itself for later.* the second packet is sent and TBF tries to queues it to SFQ. qdisc qlen is now 2 and because the SFQ limit is 1 the packet is dropped by SFQ. At this point qlen is 1, and all of the SFQ slots are empty, however
q->tailis not NULL.
Quoted 7 lines
At this point, assuming no more packets are queued, when
sch_dequeueruns again it will decrement the qlen for the current empty slot causing an underflow and the subsequent out of bounds access.Reported-by syzbot <[email protected]>Fixes 1da177e4c3f4 ("Linux-2.6.12-rc2")Signed-off-by Octavian Purdila <[email protected]>
PATCH 2/2 selftests/tc-testing: sfq: test that kernel rejects limit of 1
In reply to Octavian PurdilaAdd test to check that the kernel rejects a configuration with the limit set to 1.
--- .../tc-testing/scripts/sfq_rejects_limit_1.py | 21 +++++++++++++++++++ .../tc-testing/tc-tests/qdiscs/sfq.json | 20 ++++++++++++++++++ 2 files changed, 41 insertions(+) create mode 100755 tools/testing/selftests/tc-testing/scripts/sfq_rejects_limit_1.py
tools/testing/selftests/tc-testing/scripts/sfq_rejects_limit_1.py new file +21 -0
@@ -0,0 +1,21 @@ +#!/usr/bin/env python3 +# SPDX-License-Identifier: GPL-2.0 +# +# Script that checks that SFQ rejects a limit of 1 at the kernel +# level. We can't use iproute2's tc because it does not accept a limit +# of 1. + +import sys +import os + +from pyroute2 import IPRoute +from pyroute2.netlink.exceptions import NetlinkError + +ip = IPRoute() +ifidx = ip.link_lookup(ifname=sys.argv[1]) + +try: + ip.tc('add', 'sfq', ifidx, limit=1) + sys.exit(1) +except NetlinkError: + sys.exit(0)
tools/testing/selftests/tc-testing/tc-tests/qdiscs/sfq.json +20 -0
@@ -208,5 +208,25 @@ "teardown": [ "$TC qdisc del dev $DUMMY handle 1: root" ] + }, + { + "id": "4d6f", + "name": "Check that limit of 1 is rejected", + "category": [ + "qdisc", + "sfq" + ], + "plugins": { + "requires": "nsPlugin" + }, + "setup": [ + ], + "cmdUnderTest": "./scripts/sfq_rejects_limit_1.py $DUMMY", + "expExitCode": "0", + "verifyCmd": "$TC qdisc show dev $DUMMY", + "matchPattern": "sfq", + "matchCount": "0", + "teardown": [ + ] } ]
Signature · 1 line
2.47.0.338.g60cca15819-goog
This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:
Hello:
This series was applied to netdev/net-next.git (main) by Jakub Kicinski <[email protected]>:
Quoted 8 lines · On Tue, 3 Dec 2024 19:05:18 -0800 you wrote:
The implementation does not properly support limits of 1. Add an in-kernel check, in addition to existing iproute2 check, since other tools may be used for configuration.
This patch set also adds a selfcheck to test that a limit of 1 is rejected.
[...]
Here is the summary with links:
- [net-next,1/2] net_sched: sch_sfq: don't allow 1 packet limit
https://git.kernel.org/netdev/net-next/c/10685681bafc - [net-next,2/2] selftests/tc-testing: sfq: test that kernel rejects limit of 1 https://git.kernel.org/netdev/net-next/c/1e7e1f0e8be1
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html