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) <[email protected]> Link: https://lore.kernel.org/netdev/[email protected]/ Reviewed-by: Jamal Hadi Salim <[email protected]> Signed-off-by: Victor Nogueira <[email protected]> --- 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
