[PATCH net] net/sched: fq_codel: read flowchain under the qdisc lock in fq_codel_walk

[PATCH net] net/sched: fq_codel: read flowchain under the qdisc lock in fq_codel_walk

[Dudu Lu]

fq_codel_walk() tests list_empty(&q->flows[i].flowchain) to decide whether a
flow is on the new/old flow lists.  It runs from the RTM_GETTCLASS dump
(tc_dump_tclass -> __tc_dump_tclass -> tc_dump_tclass_root ->
tc_dump_tclass_qdisc -> cl_ops->walk).  RTM_GETTCLASS is registered without
RTNL_FLAG_DUMP_UNLOCKED (net/sched/sch_api.c:2533-2534), so rtnl_dumpit()
runs the walker under rtnl_lock.

The egress datapath splices the same flowchain under the qdisc root lock
instead, not rtnl:

  [w] list_add_tail(&flow->flowchain, &q->new_flows)   fq_codel_enqueue :211
  [w] list_move_tail(&flow->flowchain, &q->old_flows)  fq_codel_dequeue :302/:313
  [w] list_del_init(&flow->flowchain)                  fq_codel_dequeue :315
  [r] list_empty(&q->flows[i].flowchain)               fq_codel_walk    :742

list_empty() reads one word (head->next, via READ_ONCE); __list_add() writes
it with a plain store.  The two locks are disjoint, so the walker's read is
not excluded from the datapath writers.  The walker and the enqueue path can
run concurrently (enqueue is on the xmit path and does not take rtnl), so this
is a genuine unsynchronised read of a list_head that the datapath mutates.

Impact is limited: a stale "empty" answer only makes the dump skip a class
(the per-class stats path re-takes the lock in fq_codel_dump_class_stats), so
this is a data-race / cosmetic-dump-accuracy issue rather than memory
corruption.

Take the qdisc root lock around the membership read, the same lock the
datapath holds when it mutates the list.  The lock is released before
tc_qdisc_stats_dump() (which takes it again in fq_codel_dump_class_stats), so
there is no recursion.

Observed:

  (observed on the same path; the sampled race was in __alloc_skb, not the walker)
  BUG: KCSAN: data-race in __alloc_skb+0x17c/0x314
   __alloc_skb+0x17c/0x314
   netlink_dump+0x30c/0x74c
   __netlink_dump_start+0x304/0x450
   rtnetlink_rcv_msg+0x5f0/0x830

Fixes: 4b549a2ef4be ("fq_codel: Fair Queue Codel AQM")
Assisted-by: LLM
Signed-off-by: Dudu Lu <phx0fer@gmail.com>
---
Tested base
-----------
Detected on Linux 7.3-rc4 (commit 93f51579e7df), arm64 QEMU guest.
Re-checked against mainline f47d223627f8 (v7.3-341): the affected code
is unchanged between the two, so the bug is still present there.
Checked against linux-next next-20261021 (commit 9a482184d910): the
affected code is unchanged there as well, so the bug is still present in
linux-next too.

Reproducer status
-----------------
A reproducer was written and executed on an arm64 QEMU guest (KCSAN); it
opens both gates (the dumpit arm reaches fq_codel_walk), though the sampled
KCSAN report landed on a different symbol on the same netlink-dump path, not on
fq_codel_walk itself.  The defect below is argued from the code (disjoint locks
on the same list_head).  The reproducer source is not posted here per
Documentation/process/security-bugs.rst; it is available on request.

Triggering conditions
---------------------
Unprivileged: RTM_GETTCLASS is an RTNL_KIND_GET, so no CAP_NET_ADMIN is
required for the dump that reaches the walker.  Impact is limited (a stale
"empty" answer makes the dump skip a class).

Notes
-----
Built and checkpatch-clean: this patch was applied on top of 7.3-rc4
(commit 93f51579e7df) and a full arm64 kernel (defconfig) was built with
it -- no new warnings or errors.  scripts/checkpatch.pl reports 0 errors,
0 warnings.

 net/sched/sch_fq_codel.c | 13 +++++++++++--
 1 file changed, 11 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index e6c87a32950f..789fdc6551a6 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -739,7 +739,18 @@ static void fq_codel_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 		return;
 
 	for (i = 0; i < q->flows_cnt; i++) {
-		if (list_empty(&q->flows[i].flowchain)) {
+		bool empty;
+
+		/* flowchain is spliced by the datapath (fq_codel_enqueue/
+		 * fq_codel_dequeue) under the qdisc root lock.  This walker
+		 * runs under rtnl_lock, which does not exclude those writers,
+		 * so read the membership under the same lock they use.
+		 */
+		sch_tree_lock(sch);
+		empty = list_empty(&q->flows[i].flowchain);
+		sch_tree_unlock(sch);
+
+		if (empty) {
 			arg->count++;
 			continue;
 		}

Re: [PATCH net] net/sched: fq_codel: read flowchain under the qdisc lock in fq_codel_walk

[netdev-bot+sashiko]

Thank you for your contribution! Sashiko AI review found 1 potential
issue(s) to consider.

Critical: 0 · High: 1 · Medium: 0 · Low: 0

If you believe none of the issues are legitimate, please reply to each
issue of Medium severity or higher and explain why the AI is wrong.
If any of them are legitimate and you plan to respin, please let patchwork
know by including "pw-bot: cr" as a separate line at the end of your reply
(one such reply per series is enough).

- [High] fq_codel_walk() (net/sched/sch_fq_codel.c:741-759) now takes
  sch_tree_lock()/sch_tree_unlock(), i.e. spin_lock_bh on the root qdisc…

--

net/sched: fq_codel: read flowchain under the qdisc lock in fq_codel_walk

This patch takes the qdisc root lock around the list_empty() check on each
flow's flowchain in fq_codel_walk(). The commit message gives the reason:
the RTM_GETTCLASS dump runs under rtnl_lock, while enqueue and dequeue
change the same list under the root qdisc lock.

> diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
> index e6c87a32950f9..789fdc6551a6a 100644
> --- a/net/sched/sch_fq_codel.c
> +++ b/net/sched/sch_fq_codel.c
> @@ -739,7 +739,18 @@ static void fq_codel_walk(struct Qdisc *sch, struct qdisc_walker *arg)
>  		return;
>  
>  	for (i = 0; i < q->flows_cnt; i++) {
> -		if (list_empty(&q->flows[i].flowchain)) {
> +		bool empty;
> +
> +		/* flowchain is spliced by the datapath (fq_codel_enqueue/
> +		 * fq_codel_dequeue) under the qdisc root lock.  This walker
> +		 * runs under rtnl_lock, which does not exclude those writers,
> +		 * so read the membership under the same lock they use.
> +		 */
> +		sch_tree_lock(sch);
> +		empty = list_empty(&q->flows[i].flowchain);
> +		sch_tree_unlock(sch);

[Severity: High]
Could this slow down the transmit fast path for every packet on the
interface?

With this change, fq_codel_walk() does a spin_lock_bh() and unlock on the
root qdisc lock once for every flow index. That includes empty flows and
flows the dump is going to skip. flows_cnt defaults to 1024, and
fq_codel_change() allows up to 65536.

A multi-part dump also walks again from index 0 on each continuation.
tc_dump_tclass_qdisc() does this:

net/sched/sch_api.c:tc_dump_tclass_qdisc() {
    ...
	arg.w.skip = cb->args[1];
	arg.w.count = 0;
	q->ops->cl_ops->walk(q, &arg.w);
    ...
}

and the skip only happens inside tc_qdisc_stats_dump(), after the walker
has already taken and dropped the lock for that index:

include/net/pkt_sched.h:tc_qdisc_stats_dump() {
	if (arg->count >= arg->skip && arg->fn(sch, cl, arg) < 0) {
    ...
}

So each dump chunk locks every earlier flow again, which comes to roughly
flows_cnt times the number of chunks. fq_codel_enqueue() and
fq_codel_dequeue() take the same lock for every packet, so every one of
these acquisitions competes with them.

RTM_GETTCLASS is registered as a GET handler, so it does not need
CAP_NET_ADMIN. Any local user can send it in a loop, from many CPUs at
the same time:

rtnetlink_rcv_msg()->tc_dump_tclass()->tc_dump_tclass_root()->
    tc_dump_tclass_qdisc()->fq_codel_walk()

This seems to go against the earlier design. Commit edb09eb17ed8 ("net:
sched: do not acquire qdisc spinlock in qdisc/class stats dump") removed
root-lock use from the dump path. It noted that dumps "also slow down the
fast path (queue/dequeue packets) by 10 % to 20 % in some cases". Commit
f83e07b29246 ("net/sched: sch_fq_codel: annotate data-races from
fq_codel_dump_class_stats()") then annotated the lockless reads with
READ_ONCE()/WRITE_ONCE(). Since then, fq_codel_dump_class_stats() takes
the lock only when a flow has queued skbs:

net/sched/sch_fq_codel.c:fq_codel_dump_class_stats() {
    ...
		if (READ_ONCE(flow->head)) {
			sch_tree_lock(sch);
    ...
}

The lock also does not seem to make the result any more accurate. It is
dropped before empty is used, so the answer can be stale by the time the
loop acts on it, just as it could before.

The commit message says the race is benign ("a stale "empty" answer only
makes the dump skip a class"). Would annotating it be enough, along the
lines of f83e07b29246? For example, data_race(list_empty(...)) in
fq_codel_walk(), or WRITE_ONCE() on the writer side. That would avoid
adding locking to the dump path.

> +
> +		if (empty) {
>  			arg->count++;
>  			continue;
>  		}

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20261021155705.69457-1-phx0fer%40gmail.com