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/ (local)
v1: https://lore.kernel.org/netdev/QDISC-TIAE.v1.20261008110502@mojatatu.com/ (local)
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