Re: [PATCH net-next 1/2] net/sched: skip empty rounds in the deficit-refill dequeue loops

[netdev-bot+sashiko@kernel.org]

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

Critical: 0 · High: 4 · Medium: 2 · Low: 2

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] In fq_dequeue() and __fq_codel_dequeue(), the bulk skip runs at
  most once per dequeue call.
- [High] The commit message lists the qdiscs that share the 'refill-and-
  rotate shape' (fq_codel, fq_pie, fq, sfq) and bounds them, but…
- [High] In __fq_codel_dequeue() and fq_pie_qdisc_dequeue(), and per band
  in fq_dequeue(), the bulk refill never fires when every flow waiting…
- [High] In fq_dequeue(), the round sentinel `first` assumes that a flow
  refilled through `fq_flow_add_tail(q, f, OLD_FLOW)` stays on the…
- [Medium] In fq_dequeue(), __fq_codel_dequeue() and
  fq_pie_qdisc_dequeue(), the scan that sizes `rounds` skips empty flows…
- [Medium] In fq_dequeue(), __fq_codel_dequeue() and
  fq_pie_qdisc_dequeue(), the sentinel is set with `if (!first) first =…
- [Low] The patch fixes a BH-off stall under the qdisc lock that, per its
  own reproducer, can be triggered from an unprivileged user namespace…
- [Low] drr_dequeue() and ets_qdisc_dequeue() now read each class's
  quantum twice.

--

net/sched: skip empty rounds in the deficit-refill dequeue loops

This patch bounds the deficit-refill dequeue loops in drr, ets, fq,
fq_codel, fq_pie and sfq. After one full round in which no class or flow
becomes eligible, it computes the minimum number of rounds needed and
applies that many quantum refills to every class or flow at once.

Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260819143213.57401-1-jhs@mojatatu.com

> The same refill-and-rotate shape is shared by fq_codel, fq_pie, fq and
> sfq, so bound those at the same time.

[Severity: High]
Should sch_cake be on this list too? cake_dequeue() has the same
refill-and-rotate loop, and this patch leaves it unchanged:

net/sched/sch_cake.c:cake_dequeue() {
    ...
		WRITE_ONCE(flow->deficit,
			   flow->deficit + cake_get_flow_quantum(b, flow, q->config->flow_mode));
		list_move_tail(&flow->flowchain, &b->old_flows);

		goto retry;
    ...
}

The deficit is charged with the length from cake_overhead(), which starts
from qdisc_pkt_len(). The same crafted stab can therefore push it to
QDISC_PKT_LEN_MAX.

The quantum added per refill also shrinks as host_load grows:

net/sched/sch_cake.c:cake_get_flow_quantum() {
    ...
	return (q->flow_quantum * quantum_div[host_load] +
		get_random_u16()) >> 16;
}

flow_quantum is clamped to 300..1514 and quantum_div[i] is 65535 / i. In
the default triple-isolate mode, host_load can reach CAKE_QUEUES (1024), so
the average refill can be well under one byte.

Could a 1 MiB charge then take millions of refills per flow? That would
apply to up to 1024 flows per tin, all under the qdisc lock with BH off.

> It is not a regression and is not marked for stable: the walk has been
> linear in the number of classes times the per-class refill count (up to
> 4096 with a crafted size table) since these schedulers were introduced,
> so there is no regression commit to blame and no narrow fix to
> backport.

[Severity: Low]
Does this match how the predecessor was tagged? Commit 8f735d64382d
("net/sched: bound qdisc_pkt_len to prevent qdisc soft lockup") covers the
same bug class with the same unshare -Urn reproduction path, and it
carries:

    Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")

Without a Fixes: tag here, stable kernels get the 1 MiB cap but keep the
N * 4096 multi-class stall. The reproducer above shows that stall can be
triggered with namespace-local CAP_NET_ADMIN.

> diff --git a/net/sched/sch_drr.c b/net/sched/sch_drr.c
> index 8621d057edd9f..27d216b777f24 100644
> --- a/net/sched/sch_drr.c
> +++ b/net/sched/sch_drr.c

[ ... ]

> @@ -402,6 +403,45 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
>  			return skb;
>  		}
>  
> +		/* The head cannot dequeue. Once a full round passes with
> +		 * no class becoming eligible, skip the remaining empty
> +		 * rounds in a single bulk refill.
> +		 */
> +		if (!scanned && cl == first) {
> +			unsigned int rounds = UINT_MAX;
> +			struct drr_class *iter;
> +			bool skip = true;
> +
> +			scanned = true;
> +			list_for_each_entry(iter, &q->active, alist) {

[ ... ]

> +				rounds = min(rounds,
> +					     DIV_ROUND_UP(pkt_len - iter->deficit,
> +							  READ_ONCE(iter->quantum)));
> +			}
> +			if (skip && rounds != UINT_MAX) {
> +				list_for_each_entry(iter, &q->active, alist)
> +					WRITE_ONCE(iter->deficit,
> +						   iter->deficit + rounds *
> +						   READ_ONCE(iter->quantum));

[Severity: Low]
Can a concurrent quantum change over-credit a class here? quantum is read
once to size rounds and again to apply it.

drr_change_class() updates an existing class while holding only RTNL, not
the root qdisc lock:

	if (tb[TCA_DRR_QUANTUM])
		WRITE_ONCE(cl->quantum, quantum);

Suppose the quantum goes from 256 to 1 << 20 between the two reads while
rounds is about 4094. The class then gets roughly 4 GiB of deficit at
once, while the one-quantum walk could give at most pkt_len plus the new
quantum. That class could then dequeue a long run of packets while the
other active classes starve.

ets_qdisc_dequeue() has the same double read, with ets_class_change() as
the writer.

> +				continue;
> +			}
> +		}

[ ... ]

> diff --git a/net/sched/sch_fq.c b/net/sched/sch_fq.c
> index a282812c192ee..125c6bf836b9f 100644
> --- a/net/sched/sch_fq.c
> +++ b/net/sched/sch_fq.c

[ ... ]

> @@ -782,6 +792,45 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
>  	f = head->first;
>  	retry = 0;
>  	if (f->credit <= 0) {
> +		/* The head cannot dequeue. Once a full round passes with
> +		 * no flow becoming eligible, skip the remaining empty
> +		 * rounds in a single bulk refill.
> +		 */
> +		if (!scanned && f == first) {
> +			unsigned int rounds = UINT_MAX;
> +			struct fq_flow *iter;
> +
> +			scanned = true;
> +			/* A completed round leaves new_flows empty, so
> +			 * only old_flows still holds flows awaiting a
> +			 * refill.
> +			 */
> +			for (iter = pband->old_flows.first; iter;
> +			     iter = iter->next) {
> +				/* A flow that cannot dequeue next round
> +				 * (empty queue) is removed instead, so it
> +				 * neither arms nor sizes the skip.
> +				 */
> +				if (!fq_peek(iter))
> +					continue;
> +				if (iter->credit > 0) {
> +					rounds = 0;
> +					break;
> +				}
> +				rounds = min(rounds,
> +					     DIV_ROUND_UP(1 - iter->credit,
> +							  q->quantum));
> +			}
> +			if (rounds && rounds != UINT_MAX) {
> +				for (iter = pband->old_flows.first; iter;
> +				     iter = iter->next)
> +					iter->credit += rounds * q->quantum;

[Severity: Medium]
Does this refill over-credit empty flows? The scan skips flows with no
packet, but the refill loop adds rounds * q->quantum to every flow on
old_flows, including the empty ones.

In the one-quantum walk, an empty flow with credit <= 0 is refilled only
until it turns positive. It is then detached with credit in (0, quantum].
An empty flow that already had credit > 0 is never refilled at all.

Here, an empty flow that needed fewer rounds than rounds (or none) can be
left with up to about (rounds - r) * quantum of extra credit, where r is
the number of rounds that flow needed itself.

fq_enqueue() keeps that credit across detach and re-attach:

	if (fq_flow_is_detached(f)) {
		fq_flow_add_tail(q, f, NEW_FLOW);
		if (time_after(jiffies, f->age + q->flow_refill_delay))
			f->credit = max_t(u32, f->credit, q->quantum);
	}

so the flow can burst above its fair share in its next active period.

__fq_codel_dequeue() and fq_pie_qdisc_dequeue() have the same mismatch. In
those, the deficit is reset only when the flow was unlinked:

	if (list_empty(&flow->flowchain)) {
		list_add_tail(&flow->flowchain, &q->new_flows);
		q->new_flow_count++;
		WRITE_ONCE(flow->deficit, q->quantum);
	}

Suppose the flow that dequeues comes before the empty flow in list order.
The empty flow is then still linked when its next packet arrives. It keeps
the inflated deficit and is not promoted to new_flows.

This seems to contradict the comment that empty flows "neither arm nor
size the skip". It also seems to contradict the commit message's claim
that "each class ends with the same deficit the one-quantum loop converged
to". Is that intended?

> +				goto begin;
> +			}
> +		}
> +
> +		if (!first)
> +			first = f;
>  		f->credit += q->quantum;
>  		head->first = f->next;
>  		fq_flow_add_tail(q, f, OLD_FLOW);

[Severity: High]
Can the sentinel leave this band's list here? fq_flow_add_tail() picks
the destination list from flow->band:

	struct fq_perband_flows *pband = &q->band_flows[flow->band];

fq_enqueue() sets the band on every enqueue, even when the flow is already
linked on another band's list:

		f->band = band;
		q->band_pkt_count[band]++;
		fq_skb_cb(skb)->band = band;

Suppose the sentinel flow got a later packet whose priority maps to
another band, for example after a SO_PRIORITY change on the same socket.
This refill then moves it onto that band's old_flows. first is not
cleared, so f == first never matches again during this pband walk. The
scan never runs, and the walk falls back to one quantum per iteration.

The throttle and detach exits re-arm first, but this path does not.
Should it?

> @@ -796,6 +845,11 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
>  		if (now + offload_horizon < time_next_packet) {
>  			head->first = f->next;
>  			f->time_next_packet = time_next_packet;
> +			/* first would point at an off-list flow and
> +			 * the scan would never arm; re-arm it.
> +			 */
> +			if (f == first)
> +				first = NULL;
>  			fq_flow_set_throttled(q, f);
>  			goto begin;
>  		}

[Severity: High]
Does re-arming first help once the scan has already run? The scan is
gated on "!scanned && f == first", and scanned is reset only on a band
switch. After one scan, clearing first here only picks a new sentinel
that can never trigger another scan.

The scan treats every flow with fq_peek() != NULL as able to dequeue. It
does not look at time_to_send or time_next_packet.

Take a paced or SO_TXTIME flow that becomes eligible, either through the
bulk refill or by turning positive in the first round (which makes the
scan abort with rounds = 0). It then reaches the head with credit > 0 and
is throttled here without dequeuing.

The remaining flows go back to one quantum per iteration for all their
remaining rounds. That is the N * 4096 walk under the qdisc lock with BH
off.

__fq_codel_dequeue() has the same problem. codel_dequeue() can drop every
remaining packet of the eligible flow, because codel_should_drop() looks
at the whole qdisc backlog. The flow is then list_del_init()'d while
scanned is already true.

Is the commit message's claim that "neither case can silently disable the
bound" still accurate once the scan has been used?

[ ... ]

> diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
> index e6c87a32950f9..79f1f25525e74 100644
> --- a/net/sched/sch_fq_codel.c
> +++ b/net/sched/sch_fq_codel.c

[ ... ]

> @@ -298,6 +300,47 @@ static struct sk_buff *__fq_codel_dequeue(struct Qdisc *sch)
>  	flow = list_first_entry(head, struct fq_codel_flow, flowchain);
>  
>  	if (flow->deficit <= 0) {

[ ... ]

> +			list_for_each_entry(iter, &q->old_flows, flowchain) {
> +				unsigned int r;
> +
> +				/* An empty flow cannot dequeue next round
> +				 * (it is removed instead), so it neither
> +				 * arms nor sizes the skip.
> +				 */
> +				if (!iter->head)
> +					continue;
> +				if (iter->deficit > 0) {
> +					skip = false;
> +					break;
> +				}
> +				r = DIV_ROUND_UP(1 - iter->deficit, q->quantum);
> +				rounds = min(rounds, r);
> +			}
> +			if (skip && rounds != UINT_MAX) {

[Severity: High]
What happens when every flow on old_flows is empty? rounds stays UINT_MAX
and the code falls through to the one-quantum walk.

The comment also does not match how empty flows are handled. An empty
flow with deficit <= 0 is refilled and rotated. It is removed only once
its deficit turns positive.

For example, N flows each send one packet with a 1 MiB stab-inflated
pkt_len, at quantum 256. Each flow is drained and left on old_flows with a
deficit of about quantum - 1 MiB.

Neither fq_codel_dequeue() nor fq_pie_qdisc_dequeue() checks qlen, and
dequeue_skb() calls q->dequeue() without checking it either. The next
dequeue call then does about 4096 refills per flow before each flow is
list_del_init()'d, and it returns no packet.

Isn't that the same N * 4096 walk under the qdisc lock that this patch is
meant to bound?

fq_pie_qdisc_dequeue() has the same structure. fq_dequeue() checks
sch->q.qlen, but the same per-band walk can happen in two cases: the
serviced band's old_flows are all empty with negative credit, and another
band still holds packets.

> +				list_for_each_entry(iter, &q->old_flows, flowchain)
> +					WRITE_ONCE(iter->deficit,
> +						   iter->deficit +
> +						   rounds * q->quantum);
> +				goto begin;
> +			}
> +		}
> +
> +		if (!first)
> +			first = flow;
>  		WRITE_ONCE(flow->deficit, flow->deficit + q->quantum);
>  		list_move_tail(&flow->flowchain, &q->old_flows);
>  		goto begin;

[Severity: Medium]
Can a run of empty flows stop the scan from ever running? The sentinel is
chosen without checking whether the flow holds a packet.

Consider old_flows ordered as empty flows E1..Ek, where Ei has deficit
1 - i * Q, followed by M backlogged flows with deficit 1 - (k + 1) * Q:

  E1 becomes first and turns positive after one refill.
  On its next visit, E1 takes the list_del_init() path, which clears
  first.
  E2 becomes the sentinel and turns positive at its next refill, and so
  on.

No sentinel is ever revisited with a non-positive deficit, so the scan
never runs. Each backlogged flow takes about k single refills. That is
O(k * (M + k)) visits under the qdisc lock.

The same pattern applies to fq_pie_qdisc_dequeue(), and to fq_dequeue()
through the fq_flow_set_detached() path. I have not confirmed that
userspace can reliably build this staggered-deficit ordering, though.

[ ... ]

-- 
Sashiko AI review · https://netdev-ai.bots.linux.dev/sashiko/#/patchset/QDISC-TIAE.v1.20261008110502%40mojatatu.com