[PATCH net-next v3 0/3] net/sched: bound the deficit-refill dequeue loops

[PATCH net-next v3 0/3] net/sched: bound the deficit-refill dequeue loops

[Victor Nogueira]

DRR, ETS, sfq, fq, fq_codel and fq_pie refill the head entity one
quantum at a time until it can send. With a size table that inflates
packets to 1 MiB and a quantum of 256, one dequeue can loop thousands of
times under the qdisc lock. This series skips the rounds in which
nothing can send, so a stalled round costs O(N).

1/3 fixes drr, ets and sfq.
2/3 fixes fq, fq_codel and fq_pie. There a flow can still fail to send
after the skip (throttled, or dropped by the AQM), so a setup built to
change state on every refill is still slow.
3/3 adds DRR and ETS tests for the refill result and service order.

v2 -> v3:
- drr, ets: a class quantum change takes the tree lock, so the round
  count and the refill use one snapshot.
- drr, ets, fq, fq_codel, fq_pie: the skip is repeated after a bulk
  refill, so a child that exposes a longer head or changes state leaves
  the fast path after one more pass instead of falling back to the
  one-quantum loop for the rest of the dequeue.
- 3/3 is unchanged.

About the request to fold the loops together: the three dequeue loops
read different data structures with different eligibility rules (DRR/ETS
classes, fq bands and flows, fq_codel/fq_pie flow lists), so a shared
helper would add an indirect call to the dequeue path without removing
any of that logic. The common shape is described in the commit logs
instead. cake_dequeue() has the same one-quantum refill, but its
dithered quantum makes the right fix a different one; it is not part of
this series.

v2: https://lore.kernel.org/netdev/QDISC-TIAE.v2.r0.20261015163454@mojatatu.com/
v1: https://lore.kernel.org/netdev/QDISC-TIAE.v1.20261008110502@mojatatu.com/

Victor Nogueira (3):
  net/sched: drr, ets, sfq: skip empty rounds in the deficit-refill
    dequeue loop
  net/sched: fq, fq_codel, fq_pie: skip empty rounds in the
    deficit-refill dequeue loop
  selftests: tc-testing: pin DRR and ETS deficit refill semantics

 net/sched/sch_drr.c                           | 57 +++++++++++-
 net/sched/sch_ets.c                           | 53 ++++++++++-
 net/sched/sch_fq.c                            | 87 ++++++++++++++++++-
 net/sched/sch_fq_codel.c                      | 80 ++++++++++++++++-
 net/sched/sch_fq_pie.c                        | 74 +++++++++++++++-
 net/sched/sch_sfq.c                           | 41 ++++++++-
 .../tc-testing/tc-tests/qdiscs/drr.json       | 82 +++++++++++++++++
 .../tc-testing/tc-tests/qdiscs/ets.json       | 54 ++++++++++++
 8 files changed, 519 insertions(+), 9 deletions(-)

-- 
2.43.0

[PATCH net-next v3 1/3] net/sched: drr, ets, sfq: skip empty rounds in the deficit-refill dequeue loop

[Victor Nogueira]

The issue: DRR and ETS refill the head class one quantum per iteration
until its packet fits the deficit. A size table that inflates the packet
length to QDISC_PKT_LEN_MAX (1 MiB) with a quantum of 256 makes that
~4096 iterations per packet, so one dequeue over N backlogged classes
can spin N * 4096 times under the qdisc lock with BH disabled. Draining
16384 DRR classes this way takes about a second.

The Fix: after a full round in which no class could dequeue, compute how
many more rounds it takes until one can and add that many quanta to every
class at once. Deficits and service order are the same as with the
one-quantum loop, and a stalled round costs one pass over the active
list.

The skip is repeated after every bulk refill, so a child that exposes a
longer head once its deficit is positive costs one more pass, not
N * 4096. A child that empties itself while being peeked is skipped
instead of ending the scan. DRR and ETS change a class quantum under the
tree lock, the same lock the dequeue path holds, so the rounds and the
refill come from one snapshot.

sfq has the same loop and gets the same one-shot bulk refill. A slot's
readiness depends only on the allot the bulk pass sets, so it needs no
repeat scan. ETS has at most 16 bands, so it was never that slow; it is
changed to match DRR.

This follows commit 8f735d64382d ("net/sched: bound qdisc_pkt_len to
prevent qdisc soft lockup"). With 16384 DRR classes the drain goes from
~1.0s to ~0.12s.

Conditions to recreate:
- tc qdisc add dev veth0 root handle 1: stab mtu 2048 tsize 0 \
    overhead 1048576 drr
- 16384 classes with quantum 256, one packet in each (sent with
  SO_PRIORITY set to the classid), plus one catch-all u32 filter so ARP
  is not dropped
- CAP_NET_ADMIN (unshare -Urn is enough)

Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260819143213.57401-1-jhs@mojatatu.com
Link: https://lore.kernel.org/netdev/3ab59725-e34c-4243-bc72-d93f837bcad1@redhat.com/
Link: https://lore.kernel.org/netdev/CA+NMeC_kwd5yihR3SSqb+Z8wX+NuobntbvpKtAyOwjZ1Xa4mVg@mail.gmail.com/
Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
v2 -> v3:
- drr, ets: the class quantum is changed under the tree lock, so the
  round count and the refill use one snapshot.
- drr, ets: the skip scan is repeated after a bulk refill and tolerates a
  child that empties itself while being peeked.
v1 -> v2:
- drr, ets, sfq: the dequeue loop skips the empty rounds in one bulk
  refill.
 net/sched/sch_drr.c | 57 +++++++++++++++++++++++++++++++++++++++++++--
 net/sched/sch_ets.c | 53 ++++++++++++++++++++++++++++++++++++++++-
 net/sched/sch_sfq.c | 41 +++++++++++++++++++++++++++++++-
 3 files changed, 147 insertions(+), 4 deletions(-)

diff --git a/net/sched/sch_drr.c b/net/sched/sch_drr.c
index 8621d057edd9..bff7b307e98e 100644
--- a/net/sched/sch_drr.c
+++ b/net/sched/sch_drr.c
@@ -98,8 +98,15 @@ static int drr_change_class(struct Qdisc *sch, u32 classid, u32 parentid,
 			}
 		}
 
-		if (tb[TCA_DRR_QUANTUM])
+		if (tb[TCA_DRR_QUANTUM]) {
+			/* The dequeue path reads the quantum while it holds
+			 * the tree lock; take it here as well so that the
+			 * rounds and the refill come from one snapshot.
+			 */
+			sch_tree_lock(sch);
 			WRITE_ONCE(cl->quantum, quantum);
+			sch_tree_unlock(sch);
+		}
 
 		return 0;
 	}
@@ -372,7 +379,8 @@ static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 {
 	struct drr_sched *q = qdisc_priv(sch);
-	struct drr_class *cl;
+	struct drr_class *cl, *first = NULL;
+	bool scanned = false;
 	struct sk_buff *skb;
 	unsigned int len;
 
@@ -402,6 +410,51 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
 			return skb;
 		}
 
+		/* No class could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && cl == first) {
+			unsigned int rounds = UINT_MAX;
+			struct drr_class *iter, *tmp;
+			bool skip = true;
+
+			scanned = true;
+			list_for_each_entry_safe(iter, tmp, &q->active, alist) {
+				unsigned int pkt_len;
+				struct sk_buff *peek;
+
+				/* A child that emptied itself while peeking
+				 * is no longer in the list and needs no rounds.
+				 */
+				peek = iter->qdisc->ops->peek(iter->qdisc);
+				if (!peek)
+					continue;
+				pkt_len = qdisc_pkt_len(peek);
+				if (pkt_len <= iter->deficit) {
+					skip = false;
+					break;
+				}
+				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));
+				/* A child may show a longer head now that its
+				 * deficit is positive; scan again if it still
+				 * cannot send.
+				 */
+				first = NULL;
+				scanned = false;
+				continue;
+			}
+		}
+
+		if (!first)
+			first = cl;
 		WRITE_ONCE(cl->deficit, cl->deficit + READ_ONCE(cl->quantum));
 		list_move_tail(&cl->alist, &q->active);
 	}
diff --git a/net/sched/sch_ets.c b/net/sched/sch_ets.c
index 6cc902a03838..86fdf772fe2e 100644
--- a/net/sched/sch_ets.c
+++ b/net/sched/sch_ets.c
@@ -243,7 +243,13 @@ static int ets_class_change(struct Qdisc *sch, u32 classid, u32 parentid,
 	if (err)
 		return err;
 
+	/* The dequeue path reads the quantum while it holds the tree lock;
+	 * take it here as well so that the rounds and the refill come from
+	 * one snapshot.
+	 */
+	sch_tree_lock(sch);
 	WRITE_ONCE(cl->quantum, quantum);
+	sch_tree_unlock(sch);
 
 	ets_offload_change(sch);
 	return 0;
@@ -459,7 +465,8 @@ ets_qdisc_dequeue_skb(struct Qdisc *sch, struct sk_buff *skb)
 static struct sk_buff *ets_qdisc_dequeue(struct Qdisc *sch)
 {
 	struct ets_sched *q = qdisc_priv(sch);
-	struct ets_class *cl;
+	struct ets_class *cl, *first = NULL;
+	bool scanned = false;
 	struct sk_buff *skb;
 	unsigned int band;
 	unsigned int len;
@@ -493,6 +500,50 @@ static struct sk_buff *ets_qdisc_dequeue(struct Qdisc *sch)
 			return ets_qdisc_dequeue_skb(sch, skb);
 		}
 
+		/* No class could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && cl == first) {
+			unsigned int rounds = UINT_MAX;
+			struct ets_class *iter, *tmp;
+			bool skip = true;
+
+			scanned = true;
+			list_for_each_entry_safe(iter, tmp, &q->active, alist) {
+				unsigned int pkt_len;
+				struct sk_buff *peek;
+
+				/* A child that emptied itself while peeking
+				 * is no longer in the list and needs no rounds.
+				 */
+				peek = iter->qdisc->ops->peek(iter->qdisc);
+				if (!peek)
+					continue;
+				pkt_len = qdisc_pkt_len(peek);
+				if (pkt_len <= iter->deficit) {
+					skip = false;
+					break;
+				}
+				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)
+					iter->deficit += rounds *
+							 READ_ONCE(iter->quantum);
+				/* A child may show a longer head now that its
+				 * deficit is positive; scan again if it still
+				 * cannot send.
+				 */
+				first = NULL;
+				scanned = false;
+				continue;
+			}
+		}
+
+		if (!first)
+			first = cl;
 		cl->deficit += READ_ONCE(cl->quantum);
 		list_move_tail(&cl->alist, &q->active);
 	}
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 8bbcfc9e85d9..83a698af2d58 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -479,9 +479,11 @@ static struct sk_buff *
 sfq_dequeue(struct Qdisc *sch)
 {
 	struct sfq_sched_data *q = qdisc_priv(sch);
+	sfq_index first = SFQ_EMPTY_SLOT;
 	struct sk_buff *skb;
-	sfq_index a, next_a;
 	struct sfq_slot *slot;
+	bool scanned = false;
+	sfq_index a, next_a;
 
 	/* No active slots */
 	if (q->tail == NULL)
@@ -491,6 +493,43 @@ sfq_dequeue(struct Qdisc *sch)
 	a = q->tail->next;
 	slot = &q->slots[a];
 	if (slot->allot <= 0) {
+		/* No slot could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && a == first) {
+			unsigned int rounds = UINT_MAX;
+			bool skip = true;
+			sfq_index i = a;
+
+			scanned = true;
+			do {
+				struct sfq_slot *s = &q->slots[i];
+				unsigned int r;
+
+				if (s->allot > 0) {
+					skip = false;
+					break;
+				}
+				r = DIV_ROUND_UP(1 - s->allot, q->quantum);
+				rounds = min(rounds, r);
+				i = s->next;
+			} while (i != a);
+			if (skip && rounds != UINT_MAX) {
+				i = a;
+				do {
+					struct sfq_slot *s = &q->slots[i];
+
+					WRITE_ONCE(s->allot,
+						   s->allot +
+						   rounds * q->quantum);
+					i = s->next;
+				} while (i != a);
+				goto next_slot;
+			}
+		}
+
+		if (first == SFQ_EMPTY_SLOT)
+			first = a;
 		q->tail = slot;
 		WRITE_ONCE(slot->allot, slot->allot + q->quantum);
 		goto next_slot;
-- 
2.43.0

[PATCH net-next v3 2/3] net/sched: fq, fq_codel, fq_pie: skip empty rounds in the deficit-refill dequeue loop

[Victor Nogueira]

The issue: fq, fq_codel and fq_pie refill the head flow one quantum per
iteration until it has credit. With a size table that inflates the packet
length to 1 MiB and a quantum of 256 that is ~4096 iterations per packet,
so a dequeue over N flows can spin N * 4096 times under the qdisc lock
with BH disabled.

The Fix: apply the same skip-ahead as the previous patch for DRR. After a
full round in which no flow could dequeue, add the quanta for the
remaining rounds to every flow at once. An empty flow that the one-quantum
loop would have removed during those rounds is credited the same amount
and removed in the same pass, so credits and list order match the old
loop.

The skip is repeated after every bulk refill, so a flow that changes
state (throttled in fq, dropped by the AQM in fq_codel and fq_pie, or a
new packet at the head) does not leave the loop on the one-quantum path
for the rest of the dequeue. A setup built to change state on every
refill is still as slow as before; normal ones are O(N).

Conditions to recreate:
- root: stab mtu 2048 tsize 0 overhead 1048576 tbf rate 100kbit
  burst 2mb limit 1000000 (stab must be on the root)
- child: fq_codel or fq_pie, flows 65536 quantum 256, target and
  interval 100s so the AQM never drops
- one packet in each of 8192 flows (SO_PRIORITY = 0x10:<i> or a distinct
  destination per packet so the flow hash separates them), then raise the
  tbf rate to release them
- the last dequeue takes 65-70 ms (fq_codel) / 74-75 ms (fq_pie)
  before this change and under 0.4 ms after
- fq hits the same loop when a band holds only empty flows while
  packets wait in another band or in throttled flows

Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
Link: https://lore.kernel.org/netdev/179182028153.434549.4854377793269282267@kernel.org/
Link: https://lore.kernel.org/netdev/3ab59725-e34c-4243-bc72-d93f837bcad1@redhat.com/
Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
v2 -> v3:
- fq, fq_codel, fq_pie: the skip is repeated after a bulk refill instead
  of running once per dequeue.
v1 -> v2:
- fq, fq_codel, fq_pie: skip empty rounds as in 1/3, empty flows
  credited as the old loop would.
 net/sched/sch_fq.c       | 87 +++++++++++++++++++++++++++++++++++++++-
 net/sched/sch_fq_codel.c | 80 +++++++++++++++++++++++++++++++++++-
 net/sched/sch_fq_pie.c   | 74 +++++++++++++++++++++++++++++++++-
 3 files changed, 236 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_fq.c b/net/sched/sch_fq.c
index a282812c192e..4229065e4809 100644
--- a/net/sched/sch_fq.c
+++ b/net/sched/sch_fq.c
@@ -737,8 +737,10 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
 	struct fq_sched_data *q = qdisc_priv(sch);
 	u64 offload_horizon = fq_offload_horizon(sch, q);
 	struct fq_perband_flows *pband;
+	struct fq_flow *first = NULL;
 	struct fq_flow_head *head;
 	u64 time_next_packet = 0;
+	bool scanned = false;
 	struct sk_buff *skb;
 	struct fq_flow *f;
 	unsigned long rate;
@@ -769,8 +771,12 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
 			pband = &q->band_flows[q->band_nr];
 			pband->credit = min(pband->credit + pband->quantum,
 					    pband->quantum);
-			if (pband->credit > 0)
+			if (pband->credit > 0) {
+				/* New band: start a new round. */
+				first = NULL;
+				scanned = false;
 				goto begin;
+			}
 			retry = 0;
 		}
 		if (q->time_next_delayed_flow != ~0ULL)
@@ -782,9 +788,82 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
 	f = head->first;
 	retry = 0;
 	if (f->credit <= 0) {
+		/* No flow could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && f == first) {
+			unsigned int rounds = UINT_MAX;
+			struct fq_flow *iter, *prev;
+			bool skip = true;
+
+			scanned = true;
+			/* new_flows is empty after a full round. */
+			for (iter = pband->old_flows.first; iter;
+			     iter = iter->next) {
+				/* Empty flows don't limit the rounds. */
+				if (!fq_peek(iter))
+					continue;
+				if (iter->credit > 0) {
+					skip = false;
+					break;
+				}
+				rounds = min(rounds,
+					     DIV_ROUND_UP(1 - iter->credit,
+							  q->quantum));
+			}
+			if (skip) {
+				prev = NULL;
+				for (iter = pband->old_flows.first; iter;
+				     iter = iter->next) {
+					unsigned int k = 0;
+
+					/* An empty flow leaves the list after
+					 * k more refills. If that falls within
+					 * the skipped rounds, remove it now.
+					 * fq keeps the credit if the flow comes
+					 * back, so give it exactly k quanta.
+					 */
+					if (fq_peek(iter)) {
+						iter->credit += rounds * q->quantum;
+						prev = iter;
+						continue;
+					}
+					if (iter->credit <= 0)
+						k = DIV_ROUND_UP(1 - iter->credit,
+								 q->quantum);
+					if (k >= rounds) {
+						iter->credit += rounds * q->quantum;
+						prev = iter;
+						continue;
+					}
+					iter->credit += k * q->quantum;
+					if (prev)
+						prev->next = iter->next;
+					else
+						pband->old_flows.first = iter->next;
+					if (pband->old_flows.last == iter)
+						pband->old_flows.last = prev;
+					fq_flow_set_detached(iter);
+				}
+				/* A flow may show a non-empty queue, a new
+				 * packet or a throttled one now; scan again if
+				 * the loop still cannot dequeue.
+				 */
+				first = NULL;
+				scanned = false;
+				goto begin;
+			}
+		}
+
+		/* Remember which flow started this round. */
+		if (!first)
+			first = f;
 		f->credit += q->quantum;
 		head->first = f->next;
 		fq_flow_add_tail(q, f, OLD_FLOW);
+		/* f may have moved to another band's list. */
+		if (f == first && f->band != q->band_nr)
+			first = NULL;
 		goto begin;
 	}
 
@@ -796,6 +875,9 @@ 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;
+			/* The round's first flow left; the next one takes over. */
+			if (f == first)
+				first = scanned ? NULL : head->first;
 			fq_flow_set_throttled(q, f);
 			goto begin;
 		}
@@ -814,6 +896,9 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
 		if (head == &pband->new_flows) {
 			fq_flow_add_tail(q, f, OLD_FLOW);
 		} else {
+			/* The round's first flow left; the next one takes over. */
+			if (f == first)
+				first = scanned ? NULL : head->first;
 			fq_flow_set_detached(f);
 		}
 		goto begin;
diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index e6c87a32950f..25d7bc9b6414 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -284,6 +284,8 @@ static void drop_func(struct sk_buff *skb, void *ctx)
 static struct sk_buff *__fq_codel_dequeue(struct Qdisc *sch)
 {
 	struct fq_codel_sched_data *q = qdisc_priv(sch);
+	struct fq_codel_flow *first = NULL;
+	bool scanned = false;
 	struct sk_buff *skb;
 	struct fq_codel_flow *flow;
 	struct list_head *head;
@@ -298,6 +300,73 @@ static struct sk_buff *__fq_codel_dequeue(struct Qdisc *sch)
 	flow = list_first_entry(head, struct fq_codel_flow, flowchain);
 
 	if (flow->deficit <= 0) {
+		/* No flow could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && flow == first) {
+			unsigned int rounds = UINT_MAX;
+			struct fq_codel_flow *iter;
+			bool skip = true;
+
+			scanned = true;
+			/* new_flows is empty after a full round. */
+			list_for_each_entry(iter, &q->old_flows, flowchain) {
+				unsigned int r;
+
+				/* Empty flows don't limit the rounds. */
+				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) {
+				struct fq_codel_flow *tmp;
+
+				list_for_each_entry_safe(iter, tmp, &q->old_flows,
+							 flowchain) {
+					unsigned int k = 0;
+
+					/* An empty flow leaves the list after
+					 * k more refills. If that falls within
+					 * the skipped rounds, remove it now.
+					 */
+					if (iter->head) {
+						WRITE_ONCE(iter->deficit,
+							   iter->deficit +
+							   rounds * q->quantum);
+						continue;
+					}
+					if (iter->deficit <= 0)
+						k = DIV_ROUND_UP(1 - iter->deficit,
+								 q->quantum);
+					if (k < rounds) {
+						WRITE_ONCE(iter->deficit,
+							   iter->deficit +
+							   k * q->quantum);
+						list_del_init(&iter->flowchain);
+						continue;
+					}
+					WRITE_ONCE(iter->deficit,
+						   iter->deficit +
+						   rounds * q->quantum);
+				}
+				/* A flow may show a non-empty queue or a
+				 * dropped packet now; scan again if the loop
+				 * still cannot dequeue.
+				 */
+				first = NULL;
+				scanned = false;
+				goto begin;
+			}
+		}
+
+		/* Remember which flow started this round. */
+		if (!first)
+			first = flow;
 		WRITE_ONCE(flow->deficit, flow->deficit + q->quantum);
 		list_move_tail(&flow->flowchain, &q->old_flows);
 		goto begin;
@@ -309,10 +378,17 @@ static struct sk_buff *__fq_codel_dequeue(struct Qdisc *sch)
 
 	if (!skb) {
 		/* force a pass through old_flows to prevent starvation */
-		if ((head == &q->new_flows) && !list_empty(&q->old_flows))
+		if (head == &q->new_flows && !list_empty(&q->old_flows)) {
 			list_move_tail(&flow->flowchain, &q->old_flows);
-		else
+		} else {
 			list_del_init(&flow->flowchain);
+			/* The round's first flow left; the next one takes over. */
+			if (flow == first)
+				first = scanned ? NULL :
+					list_first_entry_or_null(&q->old_flows,
+								 struct fq_codel_flow,
+								 flowchain);
+		}
 		goto begin;
 	}
 	qdisc_bstats_update(sch, skb);
diff --git a/net/sched/sch_fq_pie.c b/net/sched/sch_fq_pie.c
index 5982847df8f8..15ae97710120 100644
--- a/net/sched/sch_fq_pie.c
+++ b/net/sched/sch_fq_pie.c
@@ -238,6 +238,8 @@ static inline struct sk_buff *dequeue_head(struct fq_pie_flow *flow)
 static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)
 {
 	struct fq_pie_sched_data *q = qdisc_priv(sch);
+	struct fq_pie_flow *first = NULL;
+	bool scanned = false;
 	struct sk_buff *skb = NULL;
 	struct fq_pie_flow *flow;
 	struct list_head *head;
@@ -254,6 +256,67 @@ static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)
 	flow = list_first_entry(head, struct fq_pie_flow, flowchain);
 	/* Flow has exhausted all its credits */
 	if (flow->deficit <= 0) {
+		/* No flow could dequeue in the last full round. Add the
+		 * quanta for the rounds still needed in one pass.
+		 */
+		if (!scanned && flow == first) {
+			unsigned int rounds = UINT_MAX;
+			struct fq_pie_flow *iter;
+			bool skip = true;
+
+			scanned = true;
+			/* new_flows is empty after a full round. */
+			list_for_each_entry(iter, &q->old_flows, flowchain) {
+				unsigned int r;
+
+				/* Empty flows don't limit the rounds. */
+				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) {
+				struct fq_pie_flow *tmp;
+
+				list_for_each_entry_safe(iter, tmp, &q->old_flows,
+							 flowchain) {
+					unsigned int k = 0;
+
+					/* An empty flow leaves the list after
+					 * k more refills. If that falls within
+					 * the skipped rounds, remove it now.
+					 */
+					if (iter->head) {
+						iter->deficit += rounds * q->quantum;
+						continue;
+					}
+					if (iter->deficit <= 0)
+						k = DIV_ROUND_UP(1 - iter->deficit,
+								 q->quantum);
+					if (k < rounds) {
+						iter->deficit += k * q->quantum;
+						list_del_init(&iter->flowchain);
+						continue;
+					}
+					iter->deficit += rounds * q->quantum;
+				}
+				/* A flow may show a non-empty queue or a
+				 * dropped packet now; scan again if the loop
+				 * still cannot dequeue.
+				 */
+				first = NULL;
+				scanned = false;
+				goto begin;
+			}
+		}
+
+		/* Remember which flow started this round. */
+		if (!first)
+			first = flow;
 		flow->deficit += q->quantum;
 		list_move_tail(&flow->flowchain, &q->old_flows);
 		goto begin;
@@ -269,10 +332,17 @@ static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)
 
 	if (!skb) {
 		/* force a pass through old_flows to prevent starvation */
-		if (head == &q->new_flows && !list_empty(&q->old_flows))
+		if (head == &q->new_flows && !list_empty(&q->old_flows)) {
 			list_move_tail(&flow->flowchain, &q->old_flows);
-		else
+		} else {
 			list_del_init(&flow->flowchain);
+			/* The round's first flow left; the next one takes over. */
+			if (flow == first)
+				first = scanned ? NULL :
+					list_first_entry_or_null(&q->old_flows,
+								 struct fq_pie_flow,
+								 flowchain);
+		}
 		goto begin;
 	}
 
-- 
2.43.0

[PATCH net-next v3 3/3] selftests: tc-testing: pin DRR and ETS deficit refill semantics

[Victor Nogueira]

Add tests that check the DRR and ETS deficit refill, so a change to the
refill loop can't silently alter the result.

The cases:
- 3f3e: one DRR class, quantum 256, sends a 1514-byte packet; the
  deficit ends at 22.
- 57a1: two DRR classes with 1514- and 514-byte packets; the 514-byte
  packet goes first.
- 2177: the same as 57a1 under ETS. IPv6 is disabled on the device so
  its router solicitation doesn't land in a band.

57a1 and 2177 put netem under the classful qdisc, so they log the usual
"non-work-conserving?" warning. All three pass with and without the
previous patches.

Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
 .../tc-testing/tc-tests/qdiscs/drr.json       | 82 +++++++++++++++++++
 .../tc-testing/tc-tests/qdiscs/ets.json       | 54 ++++++++++++
 2 files changed, 136 insertions(+)

diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
index 2b61d8d79bde..d7ac32294738 100644
--- a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
+++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
@@ -86,5 +86,87 @@
         "teardown": [
             "$TC qdisc del dev $DUMMY root"
         ]
+    },
+    {
+        "id": "3f3e",
+        "name": "DRR deficit after refilling a 1514-byte packet at quantum 256",
+        "category": [
+            "qdisc",
+            "drr"
+        ],
+        "plugins": {
+            "requires": "nsPlugin"
+        },
+        "setup": [
+            "$IP addr add 10.10.11.10/24 dev $DUMMY",
+            "$TC qdisc add dev $DUMMY root handle 1: drr",
+            "$TC class add dev $DUMMY parent 1: classid 1:1 drr quantum 256",
+            "$TC qdisc add dev $DUMMY parent 1:1 handle 10: netem delay 2s limit 10",
+            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match u32 0 0 flowid 1:1",
+            "ping -c 2 -s 1472 -i 1 10.10.11.11 -I $DUMMY -W 0.01 >/dev/null 2>&1 &"
+        ],
+        "cmdUnderTest": "sleep 2.5",
+        "expExitCode": "0",
+        "verifyCmd": "$TC -s class show dev $DUMMY",
+        "matchPattern": "deficit 22b",
+        "matchCount": "1",
+        "teardown": [
+            "$TC qdisc del dev $DUMMY root"
+        ]
+    },
+    {
+        "id": "57a1",
+        "name": "DRR serves the class that fits its deficit first",
+        "category": [
+            "qdisc",
+            "drr"
+        ],
+        "plugins": {
+            "requires": "nsPlugin"
+        },
+        "setup": [
+            "$IP addr add 10.10.11.10/24 dev $DUMMY",
+            "$TC qdisc add dev $DUMMY root handle 1: drr",
+            "$TC class add dev $DUMMY parent 1: classid 1:1 drr quantum 256",
+            "$TC class add dev $DUMMY parent 1: classid 1:2 drr quantum 256",
+            "$TC qdisc add dev $DUMMY parent 1:1 handle 10: netem delay 3s limit 10",
+            "$TC qdisc add dev $DUMMY parent 1:2 handle 20: netem delay 3s limit 10",
+            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match ip dport 1111 0xffff flowid 1:1",
+            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match ip dport 2222 0xffff flowid 1:2",
+            "python3 -c \"import socket; a=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); b=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); a.sendto(b'A'*1472,('10.10.11.11',1111)); b.sendto(b'B'*472,('10.10.11.11',2222))\" >/dev/null 2>&1 &",
+            "sleep 1",
+            "python3 -c \"import socket; a=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); b=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); a.sendto(b'A'*1472,('10.10.11.11',1111)); b.sendto(b'B'*472,('10.10.11.11',2222))\" >/dev/null 2>&1 &"
+        ],
+        "cmdUnderTest": "sleep 2.5",
+        "expExitCode": "0",
+        "verifyCmd": "$TC -j -s class show dev $DUMMY",
+        "matchJSON": [
+            {
+                "class": "drr",
+                "handle": "1:1",
+                "root": true,
+                "stats": {
+                    "bytes": 0,
+                    "packets": 0,
+                    "backlog": 3028,
+                    "qlen": 2
+                }
+            },
+            {
+                "class": "drr",
+                "handle": "1:2",
+                "root": true,
+                "stats": {
+                    "bytes": 514,
+                    "packets": 1,
+                    "backlog": 514,
+                    "qlen": 1
+                }
+            }
+        ],
+        "matchCount": "1",
+        "teardown": [
+            "$TC qdisc del dev $DUMMY root"
+        ]
     }
 ]
diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
index d2eab61c099a..ea3adba2f06c 100644
--- a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
+++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
@@ -1007,5 +1007,59 @@
         "teardown": [
             "echo \"1\" > /sys/bus/netdevsim/del_device"
         ]
+    },
+    {
+        "id": "2177",
+        "name": "ETS serves the band that fits its deficit first",
+        "category": [
+            "qdisc",
+            "ets"
+        ],
+        "plugins": {
+            "requires": "nsPlugin"
+        },
+        "setup": [
+            "$IP addr add 10.10.11.10/24 dev $DUMMY",
+            "sh -c 'echo 1 > /proc/sys/net/ipv6/conf/$DUMMY/disable_ipv6' || true",
+            "$TC qdisc add dev $DUMMY root handle 1: ets bands 2 quanta 256 256",
+            "$TC qdisc add dev $DUMMY parent 1:1 handle 10: netem delay 3s limit 10",
+            "$TC qdisc add dev $DUMMY parent 1:2 handle 20: netem delay 3s limit 10",
+            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match ip dport 1111 0xffff flowid 1:1",
+            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match ip dport 2222 0xffff flowid 1:2",
+            "python3 -c \"import socket; a=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); b=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); a.sendto(b'A'*1472,('10.10.11.11',1111)); b.sendto(b'B'*472,('10.10.11.11',2222))\" >/dev/null 2>&1 &",
+            "sleep 1",
+            "python3 -c \"import socket; a=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); b=socket.socket(socket.AF_INET,socket.SOCK_DGRAM); a.sendto(b'A'*1472,('10.10.11.11',1111)); b.sendto(b'B'*472,('10.10.11.11',2222))\" >/dev/null 2>&1 &"
+        ],
+        "cmdUnderTest": "sleep 2.5",
+        "expExitCode": "0",
+        "verifyCmd": "$TC -j -s class show dev $DUMMY",
+        "matchJSON": [
+            {
+                "class": "ets",
+                "handle": "1:1",
+                "root": true,
+                "stats": {
+                    "bytes": 1514,
+                    "packets": 1,
+                    "backlog": 3028,
+                    "qlen": 2
+                }
+            },
+            {
+                "class": "ets",
+                "handle": "1:2",
+                "root": true,
+                "stats": {
+                    "bytes": 514,
+                    "packets": 1,
+                    "backlog": 514,
+                    "qlen": 1
+                }
+            }
+        ],
+        "matchCount": "1",
+        "teardown": [
+            "$TC qdisc del dev $DUMMY root"
+        ]
     }
 ]
-- 
2.43.0

Re: [PATCH net-next v3 2/3] net/sched: fq, fq_codel, fq_pie: skip empty rounds in the deficit-refill dequeue loop

[Eric Dumazet]

Le mar. 10 nov. 2026 à 15:30, Victor Nogueira <victor@mojatatu.com> a écrit :
>
> The issue: fq, fq_codel and fq_pie refill the head flow one quantum per
> iteration until it has credit. With a size table that inflates the packet
> length to 1 MiB and a quantum of 256 that is ~4096 iterations per packet,
> so a dequeue over N flows can spin N * 4096 times under the qdisc lock
> with BH disabled.

I am quite worried by the complexity this series adds to six dequeue paths,
for a problem that needs a pretty unusual size table to show up.

I do not think the round tracking (first/scanned) is needed.

As long as no flow can be served, a round gives one quantum to every flow
and leaves the list in the same order. So the number of rounds needed
before the first flow can be served can be computed from the current head,
at any time, and added to all flows in one pass. There is no need to know
where the round started, nor to fix up 'first' in the throttle, drop and
detach paths.

Empty flows do not need to be removed in the bulk pass either: give them
the credit they would have had when detached, and let the normal path
detach them on their next visit. For fq_codel, this also keeps the reset
of the CoDel vars done by codel_dequeue(), which was one of the v2 issues.

To bound the cost of the scans, a dequeue-local refill counter is enough:
scan after a few refills, then allow the next scan only after as many
refills as flows scanned. The scan stops at the first flow with credit,
so normal setups only look at a couple of flows.

Something like the following for fq. It adds a helper and a few lines
where the head flow is refilled, and does not touch the other paths.
All flows share the same quantum, so the scan needs a single divide,
plus one per empty flow about to be detached.

With a setup close to yours (8192 flows, stab overhead 1MB, quantum 256,
fq under tbf), the longest fq_dequeue() goes from 8.4 ms to 19 us, and
the total time spent in fq_dequeue() during the drain goes from 138 ms
to 3.4 ms. The dequeue order captured with tcpdump on four mixed loads
is the same before and after.

The same helper shape should work for fq_codel, fq_pie, drr and sfq.
For DRR, a class whose child returns NULL from peek() can simply abort
the scan, as the main loop already handles that case.

ETS has at most 16 bands, I would leave it alone.

Also please, one patch per qdisc.

diff --git a/net/sched/sch_fq.c b/net/sched/sch_fq.c
index a282812c192eedea36320c21df2fdde793880b14..d0515ab14956af0b6a63d896b7cf659fbb77cf1d
100644
--- a/net/sched/sch_fq.c
+++ b/net/sched/sch_fq.c
@@ -732,11 +732,82 @@ static struct fq_flow_head
*fq_pband_head_select(struct fq_perband_flows *pband)
        return pband->old_flows.first ? &pband->old_flows : NULL;
 }

+/* Called from fq_dequeue() when the first flow of pband->old_flows has
+ * no credit, and new_flows is empty.
+ *
+ * As long as no flow can be served, each round gives one quantum to every
+ * flow and leaves old_flows in the same order. When packets are much bigger
+ * than the quantum (for example inflated by a size table), thousands of such
+ * rounds can be needed. Add them all at once.
+ *
+ * An empty flow gets the credit it would have had when detached by the
+ * one-quantum loop. It stays in the list and is detached on its next visit.
+ *
+ * Returns true if credits were changed, and the number of flows looked at
+ * in *scanned.
+ */
+static bool fq_skip_rounds(const struct fq_sched_data *q,
+                          const struct fq_perband_flows *pband,
+                          unsigned int *scanned)
+{
+       u32 add = U32_MAX, quantum = q->quantum;
+       int max_credit = INT_MIN;
+       unsigned int n = 0;
+       bool changed = false;
+       struct fq_flow *f;
+
+       for (f = pband->old_flows.first; f; f = f->next) {
+               n++;
+               /* fq_flow_add_tail() would move f to another band. */
+               if (f->band != q->band_nr)
+                       goto out;
+               if (!f->qlen)
+                       continue;
+               if (f->credit > 0)
+                       goto out;
+               max_credit = max(max_credit, f->credit);
+       }
+
+       /* All flows have the same quantum: the non-empty flow with the
+        * highest credit is the first one to get credit.
+        */
+       if (max_credit != INT_MIN)
+               add = DIV_ROUND_UP(1U - (u32)max_credit, quantum) * quantum;
+
+       for (f = pband->old_flows.first; f; f = f->next) {
+               int credit = f->credit;
+
+               if (!f->qlen) {
+                       if (credit > 0)
+                               continue;
+                       /* Only flows to be detached need a divide. */
+                       if (add > (u32)-credit) {
+                               f->credit = credit + DIV_ROUND_UP(1U -
(u32)credit,
+
quantum) * quantum;
+                               changed = true;
+                               continue;
+                       }
+               }
+               f->credit = credit + add;
+               changed = true;
+       }
+out:
+       *scanned = n;
+       return changed;
+}
+
+/* Number of one-quantum refills in fq_dequeue() before fq_skip_rounds()
+ * is tried.
+ */
+#define FQ_SKIP_ROUNDS_THRESH  8
+
 static struct sk_buff *fq_dequeue(struct Qdisc *sch)
 {
        struct fq_sched_data *q = qdisc_priv(sch);
        u64 offload_horizon = fq_offload_horizon(sch, q);
+       unsigned int next_skip = FQ_SKIP_ROUNDS_THRESH;
        struct fq_perband_flows *pband;
+       unsigned int refills = 0;
        struct fq_flow_head *head;
        u64 time_next_packet = 0;
        struct sk_buff *skb;
@@ -782,6 +853,16 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
        f = head->first;
        retry = 0;
        if (f->credit <= 0) {
+               if (unlikely(++refills >= next_skip) &&
+                   head == &pband->old_flows) {
+                       unsigned int scanned;
+                       bool skipped = fq_skip_rounds(q, pband, &scanned);
+
+                       /* Bound the cost of scans to the number of refills. */
+                       next_skip = refills + scanned;
+                       if (skipped)
+                               goto begin;
+               }
                f->credit += q->quantum;
                head->first = f->next;
                fq_flow_add_tail(q, f, OLD_FLOW);

Re: [PATCH net-next v3 1/3] net/sched: drr, ets, sfq: skip empty rounds in the deficit-refill dequeue loop

[netdev-bot+sashiko]

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

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

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).

- [Medium] The bulk-refill scan in drr_dequeue()
  (net/sched/sch_drr.c:422-431) and ets_qdisc_dequeue()…
- [Low] The commit "net/sched: drr, ets, sfq: skip empty rounds in the
  deficit-refill dequeue loop" fixes a dequeue stall: one dequeue spins…

--

net/sched: drr, ets, sfq: skip empty rounds in the deficit-refill dequeue loop

This patch changes the DRR, ETS and SFQ dequeue loops. After a full round
in which no class could dequeue, they compute how many rounds remain and
credit every active class that many quanta at once. It also takes the tree
lock when a DRR or ETS class quantum is changed.

Link: https://lore.kernel.org/netdev/3ab59725-e34c-4243-bc72-d93f837bcad1@redhat.com/
Link: https://lore.kernel.org/netdev/CA+NMeC_kwd5yihR3SSqb+Z8wX+NuobntbvpKtAyOwjZ1Xa4mVg@mail.gmail.com/

> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260819143213.57401-1-jhs@mojatatu.com

[Severity: Low]
Should this have a Fixes: tag? The patch fixes a dequeue stall: one dequeue
spins up to N * 4096 times under the root lock with BH disabled. It has
Reported-by and Closes trailers, but no Fixes:.

The earlier commit 8f735d64382d ("net/sched: bound qdisc_pkt_len to
prevent qdisc soft lockup") fixed the unbounded form of the same refill
loop, and it carried Fixes: 1da177e4c3f4. Without a Fixes: tag here,
stable has nothing to target for the remaining bounded but long form of
the loop.

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

[ ... ]

> @@ -402,6 +410,51 @@ static struct sk_buff *drr_dequeue(struct Qdisc *sch)
>  			return skb;
>  		}
>  
> +		/* No class could dequeue in the last full round. Add the
> +		 * quanta for the rounds still needed in one pass.
> +		 */
> +		if (!scanned && cl == first) {
> +			unsigned int rounds = UINT_MAX;
> +			struct drr_class *iter, *tmp;
> +			bool skip = true;
> +
> +			scanned = true;
> +			list_for_each_entry_safe(iter, tmp, &q->active, alist) {
> +				unsigned int pkt_len;
> +				struct sk_buff *peek;
> +
> +				/* A child that emptied itself while peeking
> +				 * is no longer in the list and needs no rounds.
> +				 */
> +				peek = iter->qdisc->ops->peek(iter->qdisc);
> +				if (!peek)
> +					continue;
> +				pkt_len = qdisc_pkt_len(peek);
> +				if (pkt_len <= iter->deficit) {
> +					skip = false;
> +					break;
> +				}
> +				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: Medium]
Is the comment above the peek accurate? When peek() returns NULL in
drr_dequeue() the class is skipped with continue. Nothing checks that it
has actually left q->active.

If the class is still linked, its need never limited rounds. But the
refill loop above walks all of q->active and adds rounds * quantum to
that class too.

Can a backlogged child return NULL here after it returned a packet earlier
in the same round? multiq_peek() does not cache its result, and it skips
bands whose TX queue is stopped:

net/sched/sch_multiq.c:multiq_peek() {
    ...
		if (!netif_xmit_stopped(
		    netdev_get_tx_queue(qdisc_dev(sch), curband))) {
			qdisc = q->queues[curband];
			skb = qdisc->ops->peek(qdisc);
    ...
}

Another CPU can change the TX queue state while this CPU holds the root
lock. Examples are a qdisc-bypass sender going through dev_direct_xmit(),
or a driver reset or link-down path.

multiq can be grafted under a DRR or ETS class. Such a class stays on
q->active because it still has packets.

Every class that is counted has deficit >= quantum >= 256, and pkt_len is
bounded by QDISC_PKT_LEN_MAX. So rounds <= 4095, and rounds * quantum on
its own fits in a u32.

The sum can still wrap. Take a skipped class B with quantum 1 << 20 that
already got its quantum this round, so its deficit is in [2^20, 2^21).
If a quantum 256 class needs 4095 rounds, then:

    iter->deficit + rounds * READ_ONCE(iter->quantum)

wraps B's u32 deficit. With a smaller rounds nothing wraps, but B can still
gain up to about 4 GiB of credit. It can then send thousands of
stab-inflated packets back to back and starve the other classes. Each
repeated scan after a refill can add more credit.

In the old loop, a NULL peek at the head ended the dequeue through
qdisc_warn_nonwc() and goto out. A class gained at most one quantum per
visit.

Does this conflict with the commit message statement that "Deficits and
service order are the same as with the one-quantum loop"?

One option is to abandon the bulk refill (skip = false; break) when peek()
returns NULL and !list_empty(&iter->alist). Another is to credit only the
classes that were counted. Either way, the comment above the peek would
need updating.

> +				/* A child may show a longer head now that its
> +				 * deficit is positive; scan again if it still
> +				 * cannot send.
> +				 */
> +				first = NULL;
> +				scanned = false;
> +				continue;
> +			}
> +		}

[ ... ]

> diff --git a/net/sched/sch_ets.c b/net/sched/sch_ets.c
> index 6cc902a038387..86fdf772fe2e5 100644
> --- a/net/sched/sch_ets.c
> +++ b/net/sched/sch_ets.c

[ ... ]

> @@ -493,6 +500,50 @@ static struct sk_buff *ets_qdisc_dequeue(struct Qdisc *sch)

[ ... ]

> +				peek = iter->qdisc->ops->peek(iter->qdisc);
> +				if (!peek)
> +					continue;

[ ... ]

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

[Severity: Medium]
The same pattern is in ets_qdisc_dequeue(). A class whose child peek()
returns NULL is skipped without checking that it left q->active. It then
gets rounds * quantum in the refill loop, and the ETS quantum can also be
up to 1 << 20.

Would the same fix apply here?

[ ... ]

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

Re: [PATCH net-next v3 2/3] net/sched: fq, fq_codel, fq_pie: skip empty rounds in the deficit-refill dequeue loop

[netdev-bot+sashiko]

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

Critical: 0 · High: 1 (1) · Medium: 1 · 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] The skip-ahead can be turned off for the rest of a dequeue call,
  so the N * rounds spin the patch says it removes is still reachable.
- [Medium] In __fq_codel_dequeue() (net/sched/sch_fq_codel.c), the bulk-
  skip loop removes empty flows with k < rounds by calling…
- [Low] The commit message and the new comments give reasons for the
  repeated scan that do not match the code.
- [Low] The patch is written as a bug fix ("The issue" / "The Fix", a
  reproducer, a Reported-by from the netdev bot) for a user-triggerable…

Pre-existing issues:
- [High] This problem wasn't introduced by this patch, but sch_cake has
  the same unbounded deficit-refill loop, and the series leaves it as is.

--

net/sched: fq, fq_codel, fq_pie: skip empty rounds in the deficit-refill dequeue loop

This patch adds a skip-ahead to the deficit-refill loops in fq_dequeue(),
__fq_codel_dequeue() and fq_pie_qdisc_dequeue(). After a full round in
which no flow could dequeue, the quanta for the remaining rounds are added
to every flow in one pass. Empty flows that the old loop would have removed
during those rounds are removed in the same pass, and the skip is retried
after every bulk refill.

Link: https://lore.kernel.org/netdev/179182028153.434549.4854377793269282267@kernel.org/
Link: https://lore.kernel.org/netdev/3ab59725-e34c-4243-bc72-d93f837bcad1@redhat.com/

> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> Link: https://lore.kernel.org/netdev/179182028153.434549.4854377793269282267@kernel.org/
> Link: https://lore.kernel.org/netdev/3ab59725-e34c-4243-bc72-d93f837bcad1@redhat.com/
> Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
> Signed-off-by: Victor Nogueira <victor@mojatatu.com>

[Severity: Low]
This isn't a bug, but the patch is written as a fix for a stall that users
can trigger under the qdisc lock. Should it carry Fixes: tags for the
commits that added the one-quantum refill loops in sch_fq.c,
sch_fq_codel.c and sch_fq_pie.c? If a stable backport isn't intended, a
note saying so would also help.

The sibling patch "net/sched: drr, ets, sfq: skip empty rounds in the
deficit-refill dequeue loop" doesn't have Fixes: tags either.

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

[ ... ]

> @@ -782,9 +788,82 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)
>  	f = head->first;
>  	retry = 0;
>  	if (f->credit <= 0) {
> +		/* No flow could dequeue in the last full round. Add the
> +		 * quanta for the rounds still needed in one pass.
> +		 */
> +		if (!scanned && f == first) {
> +			unsigned int rounds = UINT_MAX;
> +			struct fq_flow *iter, *prev;
> +			bool skip = true;
> +
> +			scanned = true;
> +			/* new_flows is empty after a full round. */
> +			for (iter = pband->old_flows.first; iter;
> +			     iter = iter->next) {
> +				/* Empty flows don't limit the rounds. */
> +				if (!fq_peek(iter))
> +					continue;
> +				if (iter->credit > 0) {
> +					skip = false;
> +					break;
> +				}

[ ... ]

> @@ -796,6 +875,9 @@ 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;
> +			/* The round's first flow left; the next one takes over. */
> +			if (f == first)
> +				first = scanned ? NULL : head->first;
>  			fq_flow_set_throttled(q, f);
>  			goto begin;
>  		}

[Severity: High]
Can the skip-ahead be turned off for the rest of this fq_dequeue() call?
scanned is set to true before every scan. It is only cleared again after
a successful bulk refill or on a band switch.

Suppose the scan finds a non-empty flow P with credit > 0, so skip is
false. P can have picked up that credit from its own one-quantum refill
in the round that just ended. If P's head packet has an EDT (SO_TXTIME)
or pacing time in the future, P is throttled here, and only first is
adjusted:

	if (f == first)
		first = scanned ? NULL : head->first;
	fq_flow_set_throttled(q, f);

>From then on "!scanned && f == first" is always false, so the remaining
flows go back to one-quantum refills. With the 1 MiB stab setup that is
about 4096 iterations per flow, under the qdisc lock with BH disabled.

__fq_codel_dequeue() looks like it has the same problem. If codel_dequeue()
drops all of P's packets and returns NULL, P is removed with
list_del_init() and scanned stays true.

The commit message says:

  "a flow that changes state (throttled in fq, dropped by the AQM in
  fq_codel and fq_pie, or a new packet at the head) does not leave the
  loop on the one-quantum path for the rest of the dequeue"

Does that still hold when the state change follows a failed scan rather
than a bulk refill? Should scanned also be reset on these paths?

fq_pie doesn't seem to be affected, because a non-empty flow with positive
deficit always returns an skb there.

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

[ ... ]

> @@ -298,6 +300,73 @@ static struct sk_buff *__fq_codel_dequeue(struct Qdisc *sch)

[ ... ]

> +			if (skip) {
> +				struct fq_codel_flow *tmp;
> +
> +				list_for_each_entry_safe(iter, tmp, &q->old_flows,
> +							 flowchain) {
> +					unsigned int k = 0;
> +
> +					/* An empty flow leaves the list after
> +					 * k more refills. If that falls within
> +					 * the skipped rounds, remove it now.
> +					 */
> +					if (iter->head) {
> +						WRITE_ONCE(iter->deficit,
> +							   iter->deficit +
> +							   rounds * q->quantum);
> +						continue;
> +					}
> +					if (iter->deficit <= 0)
> +						k = DIV_ROUND_UP(1 - iter->deficit,
> +								 q->quantum);
> +					if (k < rounds) {
> +						WRITE_ONCE(iter->deficit,
> +							   iter->deficit +
> +							   k * q->quantum);
> +						list_del_init(&iter->flowchain);
> +						continue;
> +					}

[Severity: Medium]
Does this bulk removal skip the CoDel state reset that the old path did?
In the old one-quantum loop, an empty flow only left old_flows after
codel_dequeue() had run on it. When dequeue_func() returns NULL,
codel_dequeue() does:

include/net/codel_impl.h:codel_dequeue() {
    ...
	if (!skb) {
		vars->first_above_time = 0;
		WRITE_ONCE(vars->dropping, false);
		return skb;
	}
    ...
}

Here the flow is removed with list_del_init() without going through
codel_dequeue(). first_above_time, dropping, drop_next and count keep
whatever values they had.

When fq_codel_enqueue() re-attaches the flow, it only resets the deficit:

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

Could a returning flow, or a new connection that hashes to the same
bucket, then be dropped or ECN marked right away? codel_should_drop()
would see a stale first_above_time that is already in the past, or
dropping would still be true.

This path runs in normal operation whenever quantum is smaller than the
packet length, for example quantum 300 with 1514 byte packets, not only
with an inflated stab.

The commit message says "credits and list order match the old loop", but
it doesn't mention this per-flow AQM reset.

> diff --git a/net/sched/sch_fq_pie.c b/net/sched/sch_fq_pie.c
> index 5982847df8f85..15ae977101207 100644
> --- a/net/sched/sch_fq_pie.c
> +++ b/net/sched/sch_fq_pie.c

[ ... ]

> @@ -254,6 +256,67 @@ static struct sk_buff *fq_pie_qdisc_dequeue(struct Qdisc *sch)

[ ... ]

> +					iter->deficit += rounds * q->quantum;
> +				}
> +				/* A flow may show a non-empty queue or a
> +				 * dropped packet now; scan again if the loop
> +				 * still cannot dequeue.
> +				 */
> +				first = NULL;
> +				scanned = false;
> +				goto begin;
> +			}
> +		}

[Severity: Low]
Is this comment accurate for fq_pie? fq_pie_qdisc_dequeue() never drops
on dequeue. It calls dequeue_head() and then pie_process_dequeue(), which
returns void and only updates qdelay, avg_dq_rate and burst_time.

A non-empty flow with positive deficit always returns an skb here, so the
repeated scan can never find a stalled round in fq_pie.

The commit message makes the same claim:

  "dropped by the AQM in fq_codel and fq_pie"

The matching comments in __fq_codel_dequeue() ("a non-empty queue") and
fq_dequeue() ("a non-empty queue, a new packet") also list state changes
that can't happen inside one dequeue call. Nothing is enqueued while the
qdisc lock is held, and fq_check_throttled() only runs before the begin
label. The only real changes seem to be CoDel drops in fq_codel and
throttling in fq.

Could the comments and the commit message be updated to match?

> +
> +		/* Remember which flow started this round. */
> +		if (!first)
> +			first = flow;
>  		flow->deficit += q->quantum;
>  		list_move_tail(&flow->flowchain, &q->old_flows);
>  		goto begin;

[Severity: High]
This isn't a bug introduced by this patch, but sch_cake seems to have the
same unbounded refill loop, and the series leaves it unchanged:

net/sched/sch_cake.c:cake_dequeue() {
    ...
	if (flow->deficit <= 0) {
		...
		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;
	}
    ...
}

Deficits are charged with adjusted_len, which is derived from
qdisc_pkt_len(), so a root stab can inflate it to 1 MiB. The refill is
flow_quantum (300..1514) scaled by host load:

	return (q->flow_quantum * quantum_div[host_load] +
		get_random_u16()) >> 16;

With the default triple-isolate mode and many bulk flows from one host,
each refill can add well under one byte on average, about 0.29 bytes at
1024 flows.

Even without host scaling, 1024 flows at about -1 MiB need about 3500
refills each. That is roughly 3.6M iterations per stalled dequeue under
the qdisc lock with BH disabled.

Should cake get the same skip-ahead, or could the commit messages say why
it is left out? hhf has the same loop, but with only two buckets it stays
bounded.

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

Re: [PATCH net-next v3 3/3] selftests: tc-testing: pin DRR and ETS deficit refill semantics

[netdev-bot+sashiko]

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

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

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).

- [Medium] All three new tests pass or fail based on wall-clock timing,
  with roughly ±0.5 s of margin, and nothing synchronises them with when…
- [Low] The commit message says only 57a1 and 2177 put netem under the
  classful qdisc and log the "non-work-conserving?" warning.
- [Low] In ETS test 2177, band 1:1 is expected to show "bytes": 1514,
  "packets": 1, although the band was never served (backlog 3028, qlen…
- [Low] The commit says it pins the DRR/ETS deficit refill 'so a change
  to the refill loop can't silently alter the result'.

--

selftests: tc-testing: pin DRR and ETS deficit refill semantics

This commit adds three tc-testing cases. 3f3e checks the DRR deficit after
a 1514-byte packet at quantum 256. 57a1 and 2177 check that DRR and ETS
serve a 514-byte packet before a 1514-byte one, using netem delay under the
classful qdisc to hold packets while stats are inspected.

> diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
> index 2b61d8d79bde8..d7ac32294738e 100644
> --- a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
> +++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/drr.json
> @@ -86,5 +86,87 @@

[ ... ]

> +        "setup": [
> +            "$IP addr add 10.10.11.10/24 dev $DUMMY",
> +            "$TC qdisc add dev $DUMMY root handle 1: drr",
> +            "$TC class add dev $DUMMY parent 1: classid 1:1 drr quantum 256",
> +            "$TC qdisc add dev $DUMMY parent 1:1 handle 10: netem delay 2s limit 10",

[Severity: Low]
The commit message says:

    57a1 and 2177 put netem under the classful qdisc, so they log the usual
    "non-work-conserving?" warning.

3f3e also puts netem under DRR class 1:1 here, so doesn't it log the same
warning? The first ping packet is enqueued and qdisc_run() calls
drr_dequeue(). netem's peek, qdisc_peek_dequeued()->netem_dequeue(),
returns NULL because the packet is not due for 2s:

net/sched/sch_drr.c:drr_dequeue() {
    ...
		skb = cl->qdisc->ops->peek(cl->qdisc);
		if (skb == NULL) {
			qdisc_warn_nonwc(__func__, cl->qdisc);
			goto out;
		}
    ...
}

Each test creates a new netem qdisc with TCQ_F_WARN_NONWC clear, so it
looks like all three tests print the warning, not two.

Should the commit message say that all three tests log it?

> +            "$TC filter add dev $DUMMY parent 1: protocol ip prio 1 u32 match u32 0 0 flowid 1:1",
> +            "ping -c 2 -s 1472 -i 1 10.10.11.11 -I $DUMMY -W 0.01 >/dev/null 2>&1 &"
> +        ],
> +        "cmdUnderTest": "sleep 2.5",
> +        "expExitCode": "0",
> +        "verifyCmd": "$TC -s class show dev $DUMMY",
> +        "matchPattern": "deficit 22b",

[Severity: Medium]
Can these tests fail intermittently because of scheduling latency?

nsPlugin runs the traffic generators in the background with & through ip
netns exec. The verify step then runs after a fixed sleep 2.5. Nothing
ties the verify step to the time the packets are actually enqueued.

In 3f3e, ping sends at T+d1 and T+d1+1, and netem releases each packet 2s
later. drr_dump_class_stats() reports the deficit only while the class is
backlogged:

net/sched/sch_drr.c:drr_dump_class_stats() {
    ...
	if (qlen)
		xstats.deficit = READ_ONCE(cl->deficit);
    ...
}

So "deficit 22b" only matches while the first packet has been dequeued and
the second is still held by netem. If ping start-up or tdc overhead moves
things by more than about 0.5s, tc prints either deficit 256b (nothing
released yet) or deficit 0b (class drained).

57a1 and 2177 have the same problem. Batch 1 is released at about T0+p1+3,
and verify runs at about T0+1+2.5 plus overhead:

- If starting ip netns exec plus python3 takes more than about 0.5s,
  batch 1 is still held at verify time. Class 1:2 then shows bytes 0 with
  backlog 1028 / qlen 2 instead of 514 / 1.
- If tdc overhead between setup and verify is too large, batch 2 is
  released and backlog/qlen change.

tdc.sh runs tdc.py -J"$(nproc)", which adds CPU contention. Debug kernels
such as KASAN or lockdep slow start-up further.

Could the tests wait for the packets to appear in the qdisc backlog before
the timed window starts? Alternatively, could the margin between the netem
delay and the verify time be made wider?

[ ... ]

> +        "cmdUnderTest": "sleep 2.5",
> +        "expExitCode": "0",
> +        "verifyCmd": "$TC -j -s class show dev $DUMMY",
> +        "matchJSON": [
> +            {
> +                "class": "drr",
> +                "handle": "1:1",
> +                "root": true,
> +                "stats": {
> +                    "bytes": 0,
> +                    "packets": 0,
> +                    "backlog": 3028,
> +                    "qlen": 2
> +                }
> +            },

[Severity: Low]
The commit message says the tests ensure "a change to the refill loop
can't silently alter the result". Does 57a1 actually pin the multi-class
refill?

This matchJSON only checks bytes, packets, backlog and qlen, which only
shows the service order. The batched refill in drr_dequeue() adds
rounds * quantum to every active class:

net/sched/sch_drr.c:drr_dequeue() {
    ...
			if (skip && rounds != UINT_MAX) {
				list_for_each_entry(iter, &q->active, alist)
					WRITE_ONCE(iter->deficit,
						   iter->deficit + rounds *
						   READ_ONCE(iter->quantum));
    ...
}

Suppose that loop were changed to refill only the first class. B would
still be dequeued first, and the asserted stats would match exactly.
Class 1:1's deficit, though, would end at 1280 (or 768) instead of 1024.
Class 1:2 ends at 254 in both cases. 3f3e has only one class, so it can't
tell these cases apart either.

Class 1:1 still has qlen 2 at verify time, so drr_dump_class_stats()
exports its deficit. Could 57a1 also check the per-class deficits (1024
and 254)? ETS does not export a deficit, so 2177 can only check the order.

[ ... ]

> diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
> index d2eab61c099a8..ea3adba2f06c7 100644
> --- a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
> +++ b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
> @@ -1007,5 +1007,59 @@

[ ... ]

> +        "verifyCmd": "$TC -j -s class show dev $DUMMY",
> +        "matchJSON": [
> +            {
> +                "class": "ets",
> +                "handle": "1:1",
> +                "root": true,
> +                "stats": {
> +                    "bytes": 1514,
> +                    "packets": 1,
> +                    "backlog": 3028,
> +                    "qlen": 2
> +                }
> +            },

[Severity: Low]
Is "bytes": 1514, "packets": 1 the intended expectation for band 1:1?

Band 1:1 still has backlog 3028 and qlen 2. Both 1514-byte packets are
still queued, so the band was never served. The count seems to come from
netem's accounting at peek time. ets_class_dump_stats() reports the
child's bstats:

net/sched/sch_ets.c:ets_class_dump_stats() {
    ...
	if (gnet_stats_copy_basic(d, NULL, &cl_q->bstats, true) < 0 ||
    ...
}

netem's peek is qdisc_peek_dequeued(), which calls netem_dequeue(). That
updates bstats before the skb is stashed back in gso_skb:

net/sched/sch_netem.c:netem_dequeue() {
    ...
deliver:
		qdisc_qstats_backlog_dec(sch, skb);
		qdisc_bstats_update(sch, skb);
		return skb;
    ...
}

So a single ETS peek of the first A packet sets band 1:1 to 1514/1.

The DRR version, 57a1, runs the same scenario and expects bytes 0 /
packets 0. That is because drr_dump_class_stats() reports cl->bstats,
which is only updated on a real dequeue.

The expectation here depends on how netem accounts a peek. Could band 1:1
check only backlog/qlen, so the test does not break if that accounting
changes while ETS scheduling stays the same?

[ ... ]

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