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) <[email protected]>
Closes:
https://netdev-ai.bots.linux.dev/sashiko/#/patchset/[email protected]
Reviewed-by: Jamal Hadi Salim <[email protected]>
Signed-off-by: Victor Nogueira <[email protected]>
---
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
