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/[email protected]/ 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
