Le mar. 10 nov. 2026 à 15:30, Victor Nogueira [off-list ref] 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);