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

[PATCH net-next v2 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 millions of
times under the qdisc lock. This series skips the rounds in which
nothing can send, so a dequeue 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 AQM drop), so a crafted setup can still be
slow.
3/3 adds DRR and ETS tests for the refill result and service order.

v1 -> v2:
- fq, fq_codel and fq_pie moved to their own patch (2/3)
- empty flows are credited and removed as the old loop would
- tests reworded, ETS case added
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                           | 42 +++++++++-
 net/sched/sch_ets.c                           | 41 +++++++++-
 net/sched/sch_fq.c                            | 81 +++++++++++++++++-
 net/sched/sch_fq_codel.c                      | 74 ++++++++++++++++-
 net/sched/sch_fq_pie.c                        | 68 ++++++++++++++-
 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, 475 insertions(+), 8 deletions(-)

-- 
2.43.0

[PATCH net-next v2 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 dequeue costs O(N).

sfq has the same loop and is fixed the same way. 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
Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
v1 -> v2:
- drr, ets, sfq: the dequeue loop skips the empty rounds in one bulk
  refill.
 net/sched/sch_drr.c | 42 +++++++++++++++++++++++++++++++++++++++++-
 net/sched/sch_ets.c | 41 ++++++++++++++++++++++++++++++++++++++++-
 net/sched/sch_sfq.c | 41 ++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 121 insertions(+), 3 deletions(-)

diff --git a/net/sched/sch_drr.c b/net/sched/sch_drr.c
index 8621d057edd9..d6cb389a55f0 100644
--- a/net/sched/sch_drr.c
+++ b/net/sched/sch_drr.c
@@ -372,7 +372,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 +403,45 @@ 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;
+			bool skip = true;
+
+			scanned = true;
+			list_for_each_entry(iter, &q->active, alist) {
+				unsigned int pkt_len;
+				struct sk_buff *peek;
+
+				/* An empty child unlinks iter; stop here. */
+				peek = iter->qdisc->ops->peek(iter->qdisc);
+				if (!peek) {
+					skip = false;
+					break;
+				}
+				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));
+				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..331c6d886fde 100644
--- a/net/sched/sch_ets.c
+++ b/net/sched/sch_ets.c
@@ -459,7 +459,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 +494,44 @@ 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;
+			bool skip = true;
+
+			scanned = true;
+			list_for_each_entry(iter, &q->active, alist) {
+				unsigned int pkt_len;
+				struct sk_buff *peek;
+
+				/* An empty child unlinks iter; stop here. */
+				peek = iter->qdisc->ops->peek(iter->qdisc);
+				if (!peek) {
+					skip = false;
+					break;
+				}
+				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);
+				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 v2 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 runs once per dequeue. If the flow it makes eligible is then
throttled (fq) or all its packets are dropped by the AQM (fq_codel,
fq_pie), the loop goes back to one quantum at a time. A setup built to
make that happen every time is 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/
Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
Signed-off-by: Victor Nogueira <victor@mojatatu.com>
---
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       | 81 +++++++++++++++++++++++++++++++++++++++-
 net/sched/sch_fq_codel.c | 74 +++++++++++++++++++++++++++++++++++-
 net/sched/sch_fq_pie.c   | 68 ++++++++++++++++++++++++++++++++-
 3 files changed, 218 insertions(+), 5 deletions(-)

diff --git a/net/sched/sch_fq.c b/net/sched/sch_fq.c
index a282812c192e..5c724ec04d90 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,76 @@ 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);
+				}
+				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 +869,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 +890,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..bc74690e2323 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,67 @@ 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);
+				}
+				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 +372,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..55c88f4bbd7c 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,61 @@ 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;
+				}
+				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 +326,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 v2 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>
---
v1 -> v2:
- DRR cases reworded, ETS case added.
 .../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 v2 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 3 potential
issue(s) to consider.

Critical: 0 · High: 0 (1) · Medium: 2 · 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] drr_dequeue() and ets_qdisc_dequeue() allow only one bulk
  refill per dequeue: `scanned = true` is set at sch_drr.c:414 /…
- [Medium] The new two-pass bulk refill in drr_dequeue() and
  ets_qdisc_dequeue() reads each class's quantum separately in the scan…
- [Low] The commit fixes a user-triggerable long busy loop under the
  qdisc lock with BH disabled (the commit itself says ~1 s per drain,…

Pre-existing issues:
- [High] This problem wasn't introduced by this patch, but the sibling-
  site audit in this series is incomplete.

--

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 now compute how many more rounds are
needed and add that many quanta to every class in one pass, instead of
refilling one quantum per iteration. It follows commit 8f735d64382d to bound
the dequeue cost when a size table inflates packet lengths to 1 MiB.

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

> sfq has the same loop and is fixed the same way. ETS has at most 16
> bands, so it was never that slow; it is changed to match DRR.

[Severity: High]
This is a pre-existing issue and was not introduced by this patch.
cake_dequeue() in net/sched/sch_cake.c seems to have the same
one-quantum-per-visit refill, and no patch in the series changes it.

The later patch "net/sched: fq, fq_codel, fq_pie: skip empty rounds in the
deficit-refill dequeue loop" covers fq, fq_codel and fq_pie. That leaves
cake:

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;
	}
    ...
}

cake_overhead() starts from qdisc_pkt_len(skb). With a root stab of
overhead 1048576, each flow can therefore be left about 1 MiB in deficit
after a single dequeue.

The per-visit quantum is also much smaller than DRR's minimum of 256:

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

Take the default triple-isolate mode with 1024 bulk flows from one host.
That averages about 1.46 bytes per visit, or about 0.29 bytes with
flow_quantum 300.

Could one cake_dequeue() over 1024 flows at -1 MiB then need roughly 7e8
to 3.7e9 iterations under the root lock with BH disabled? That is well
past the 16384-class DRR case that the commit message describes as a ~1s
stall.

> Reported-by: Sashiko (nipa) <sashiko-bot@kernel.org>
> Closes: https://netdev-ai.bots.linux.dev/sashiko/#/patchset/20260819143213.57401-1-jhs@mojatatu.com
> Reviewed-by: Jamal Hadi Salim <jhs@mojatatu.com>
> Signed-off-by: Victor Nogueira <victor@mojatatu.com>

[Severity: Low]
Should this have a Fixes: tag? The commit message says this follows
commit 8f735d64382d ("net/sched: bound qdisc_pkt_len to prevent qdisc
soft lockup"), and that commit carries:

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

Without a matching tag, stable may take 8f735d64382d without this patch.
8f735d64382d on its own still allows N * 4096 iterations per dequeue.

> diff --git a/net/sched/sch_drr.c b/net/sched/sch_drr.c
> index 8621d057edd9f..d6cb389a55f03 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;
>  		}
>  
> +		/* 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;
> +			bool skip = true;
> +
> +			scanned = true;

[Severity: Medium]
scanned is never cleared, so each dequeue gets at most one bulk refill.
Can a child's peeked head change between this scan and the loop's next
visit to that class?

prio_peek() polls every band again on each call:

net/sched/sch_prio.c:prio_peek() {
    ...
	for (prio = 0; prio < q->bands; prio++) {
		struct Qdisc *qdisc = q->queues[prio];
		struct sk_buff *skb = qdisc->ops->peek(qdisc);
		if (skb)
			return skb;
	}
    ...
}

A netem band also decides readiness from a fresh ktime_get_ns() in
netem_dequeue().

Here is an example setup. One DRR class has a PRIO child with a delayed
netem band 0 and a pfifo band 1 that holds a small packet. Every other
class has a 1 MiB head and quantum 256. The scan sees the small packet,
picks rounds=2 and raises every deficit to 1024.

Suppose the netem deadline passes before the loop gets back to the PRIO
class. prio_peek() then returns the 1 MiB netem packet and no class is
eligible. Because scanned is already true, the loop falls back to the
one-quantum path:

		WRITE_ONCE(cl->deficit, cl->deficit + READ_ONCE(cl->quantum));
		list_move_tail(&cl->alist, &q->active);

That costs roughly N * 4091 more iterations.

The commit message says "a dequeue costs O(N)" for DRR/ETS without a
caveat. The follow-up fq patch documents a similar limitation, but this
one does not.

Would clearing scanned and first after a bulk pass avoid this?
ets_qdisc_dequeue() has the same one-shot guard, although there it is
bounded by 16 bands.

> +			list_for_each_entry(iter, &q->active, alist) {
> +				unsigned int pkt_len;
> +				struct sk_buff *peek;
> +
> +				/* An empty child unlinks iter; stop here. */
> +				peek = iter->qdisc->ops->peek(iter->qdisc);
> +				if (!peek) {
> +					skip = false;
> +					break;
> +				}
> +				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]
quantum is read once in the scan to compute rounds, then read again here
when the refill is applied. Can it change between the two reads?

drr_change_class() updates an existing class without sch_tree_lock():

net/sched/sch_drr.c:drr_change_class() {
    ...
	if (cl != NULL) {
		...
		if (tb[TCA_DRR_QUANTUM])
			WRITE_ONCE(cl->quantum, quantum);

		return 0;
	}
    ...
}

tc_ctl_tclass() calls cops->change() under RTNL only. It does not take
the qdisc root lock that dequeue holds.

As an example, say the scan computes rounds=1 from a class with quantum
524288, deficit 524288 and a 1 MiB head. A concurrent change then sets
that quantum to 256 before this pass, so the refill adds only 256 and no
class becomes eligible.

Since scanned is already true, would the loop then fall back to about
2047 one-quantum rounds over all N classes?

ets_qdisc_dequeue() and ets_class_change() have the same pattern.
Snapshotting each class's quantum, or taking sch_tree_lock() around the
quantum update, would close this.

> +				continue;
> +			}
> +		}
> +
> +		if (!first)
> +			first = cl;
>  		WRITE_ONCE(cl->deficit, cl->deficit + READ_ONCE(cl->quantum));
>  		list_move_tail(&cl->alist, &q->active);
>  	}

[ ... ]

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

Re: [PATCH net-next v2 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 3 potential
issue(s) to consider.

Critical: 0 · High: 0 (1) · Medium: 2 · 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] In __fq_codel_dequeue() (net/sched/sch_fq_codel.c), the new
  skip pass unlinks empty flows with k < rounds by calling…
- [Medium] The skip-ahead can run only once per dequeue call, and one
  trap flow per dequeue is enough to undo it.
- [Low] The commit message is missing the tags a bug fix needs.

Pre-existing issues:
- [High] This problem wasn't introduced by this patch, but the series
  leaves the same bug class open in sch_cake.

--

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 dequeue loops of fq,
fq_codel and fq_pie. After a full round in which no flow could dequeue, it
gives every flow the quanta for the remaining rounds in one pass. In the
same pass it removes the empty flows the old one-quantum loop would have
removed.

Link: https://lore.kernel.org/netdev/179182028153.434549.4854377793269282267@kernel.org/

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

[Severity: Low]
This isn't a bug in the code, but should this have a Fixes: tag and a
Cc: stable? The dequeue spin has been in fq, fq_codel and fq_pie since they
were merged. Without those tags, stable maintainers have nothing to act on.

The companion commit "net/sched: drr, ets, sfq: skip empty rounds in the
deficit-refill dequeue loop" says the trigger only needs CAP_NET_ADMIN
("unshare -Urn is enough"). Could this commit message say the same?

Using Link: rather than Closes: after Reported-by: is fine as it is, since
checkpatch accepts either.

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

[ ... ]

> @@ -782,9 +788,76 @@ 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 +869,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: Medium]
Can one trap flow per dequeue bring back the full cost here?

In fq_dequeue(), scanned is set to true as soon as the scan starts. That
includes the case where the scan stops early because a non-empty flow
already has credit > 0 (skip = false; break;). After that, the
!scanned && f == first check cannot pass again in this call. fq clears
scanned only when the band changes.

If the flow that became eligible is then throttled, the code above sets
first to NULL. The remaining flows then go back to one quantum per
iteration. With the 1 MiB stab inflation and quantum 256, that is about
N * 4096 iterations again.

__fq_codel_dequeue() has the same latch and never clears scanned. There the
trap is an eligible flow whose packets codel_dequeue() all drops, which hits
the !skb path:

	list_del_init(&flow->flowchain);
	if (flow == first)
		first = scanned ? NULL : ...;

The commit message mentions this ("A setup built to make that happen every
time is as slow as before"). In fq, though, one paced or EDT flow with a
small deficit (SO_TXTIME, SO_MAX_PACING_RATE, maxrate or
low_rate_threshold) per dequeue looks like enough. The message also doesn't
cover the early-stop case.

Would it make sense to allow the scan to run again after the round's first
flow leaves, instead of once per dequeue?

Also, fq_pie_qdisc_dequeue() never drops at dequeue, so an eligible
non-empty flow always dequeues. Is the "all its packets are dropped by the
AQM (fq_codel, fq_pie)" wording accurate for fq_pie?

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

[ ... ]

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

[ ... ]

> +			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]
Do flows removed here keep stale CoDel state?

The old one-quantum loop always reached such an empty flow with
deficit > 0 before any non-empty flow became eligible (k < rounds). It then
called codel_dequeue() on it. With no skb, that resets the CoDel vars
before the !skb path calls list_del_init():

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

The skip pass unlinks the flow without that reset. When the flow comes
back, fq_codel_enqueue() only restores list membership and deficit:

	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's last packet had sojourn >= target while the backlog was
above mtu. Then first_above_time stays non-zero and in the past. On the
first packet after the flow comes back, codel_should_drop() takes the
codel_time_after(now, vars->first_above_time) branch and returns
ok_to_drop.

If dropping is still true and drop_next has passed, codel_dequeue() goes
straight into its drop loop with the old count and rec_inv_sqrt. The old
code would have set first_above_time = now + interval and not dropped.

The commit message says the new pass matches the old loop, but the CoDel
state differs here. fq and fq_pie don't have this side effect when they
remove a flow, so only fq_codel seems to be affected.

[ ... ]

> +		/* 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;

[Severity: High]
This is a pre-existing issue, not one introduced by this patch, but should
sch_cake get the same treatment? cake_dequeue() still has the DRR++ refill
loop this series replaces in fq_codel:

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;
	}
	...
}

cake_overhead() starts from qdisc_pkt_len(), so the same 1 MiB stab
overhead applies to cake.

cake_set_rate() clamps b->flow_quantum to 300..1514. cake_get_flow_quantum()
then scales it by quantum_div[host_load], and host_load can reach
CAKE_QUEUES (1024). So the average refill can drop below one byte.

With up to 1024 bulk flows in a tin, that is roughly 1024 * (2^20 / 300),
about 3.6M iterations per dequeue without host scaling, and far more with
it. All of this runs under the root qdisc lock with BH disabled.

hhf_dequeue() in sch_hhf.c has the same loop. It only has two WDRR buckets
and quantum >= 256, though, so its cost doesn't grow with the number of
flows.

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

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

[netdev-bot+sashiko]

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

Critical: 0 · High: 0 · Medium: 2 · 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).

- [Medium] The three new tests (3f3e, 57a1, 2177) coordinate with their
  background traffic only through wall-clock sleeps measured against…
- [Medium] selftests: tc: mathematically contradictory expected stats in
  ETS test 2177

--

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

This adds three tdc tests (3f3e, 57a1 and 2177) that check DRR and ETS
deficit refill. Each test puts netem delay qdiscs under DRR or ETS. It
starts background traffic in setup and checks the class stats after a
fixed sleep.

> 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",
> +            "$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 this test fail now and then on a loaded or debug kernel? The verify
step is tied to the background ping only by wall-clock sleeps measured
against the netem delay. That leaves about 0.5s of slack either way.

exec_cmd() in tdc.py waits only for the shell to exit:

    proc = subprocess.Popen(command,
        shell=True,
        ...
    (rawout, serr) = proc.communicate(timeout=NAMES['TIMEOUT'])

The ping runs in the background with its output sent to /dev/null. Setup
can therefore move on before ping has started or queued anything.
nsPlugin also wraps every command in ip netns exec, which adds more
startup latency.

Say ping sends at T and T+1. Netem then releases the packets at T+2 and
T+3, and the verify command runs at about T+2.5 plus overheads.

If verify runs before the first release, the deficit is still 256. If it
runs after the second release, qlen is 0 and drr_dump_class_stats()
reports 0:

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

In both cases "deficit 22b" won't match.

Test 57a1 in drr.json and test 2177 in ets.json have the same timing
dependency. Netem must release the first python3 pair (send time + 3s)
before verify runs at about 3.5s. It must still hold the second pair,
which is sent after "sleep 1" plus python3 startup.

Both conditions hold only if python3 startup, ip netns exec and the
sleep overheads vary by less than about 0.5s.

These are nsPlugin tests, so mp_bins() puts them in the parallel bins.
tdc.sh runs ./tdc.py -J"$(nproc)", which is capped at 4 workers. That
means they run alongside other namespace-heavy tests, and startup latency
gets longer and less predictable on KASAN or lockdep kernels.

Could the tests sync with the traffic instead? One option is to have
setup wait for the expected qlen or backlog before the sleep. Another is
a much longer netem delay, so the window doesn't depend on process
startup time.

[ ... ]

> diff --git a/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json b/tools/testing/selftests/tc-testing/tc-tests/qdiscs/ets.json
> --- 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"
> +        ]
>      }
>  ]

[Severity: Medium]
Does the expectation for band 1:1 match the traffic the setup
generates? Only two packets ever reach 1:1: the 1514-byte datagrams
from the two python3 runs. The expected stats say one of them was
sent (bytes 1514, packets 1), yet both are still queued (backlog 3028,
qlen 2). Read literally, that needs three packets in the band.

It also differs from 57a1. The commit message calls 2177 the same
case under ETS, but 57a1 expects bytes 0 and packets 0 for 1:1.

If the test really passes, as the commit message says, I suspect the
reason is how ETS reports band stats. ets_class_dump_stats() returns
the child qdisc's counters (cl->qdisc->bstats and its qstats), not
per-band ETS counters.

ets_qdisc_dequeue() looks at the head of the band through
cl->qdisc->ops->peek(), which for netem is qdisc_peek_dequeued(). That
calls netem_dequeue(), which bumps netem's bstats. It then parks the
skb in gso_skb and adds it back to qlen and backlog. So "bytes": 1514
would be the packet ETS peeked at and couldn't afford, not one it
sent.

If that is what happens, this assertion pins netem's peek accounting
rather than the ETS deficit refill. A change to how ETS peeks, or to
how the child's counters are kept, would break the test without any
change in scheduling order. If it isn't what happens, the test fails
every time.

Could you confirm which it is? If it's the peek artifact, would it be
better to assert only on band 1:2, or on something that reflects ETS's
own dequeue decision? Either way, please note in the test why 1:1 is
expected to differ from 57a1.

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