diff --git a/net/sched/sch_fq.c b/net/sched/sch_fq.c
index a282812c192e..4229065e4809 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,82 @@ 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);
+ }
+ /* A flow may show a non-empty queue, a new
+ * packet or a throttled one now; scan again if
+ * the loop still cannot dequeue.
+ */
+ first = NULL;
+ scanned = false;
+ 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 +875,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 +896,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..25d7bc9b6414 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,73 @@ 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);
+ }
+ /* A flow may show a non-empty queue or a
+ * dropped packet now; scan again if the loop
+ * still cannot dequeue.
+ */
+ first = NULL;
+ scanned = false;
+ 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 +378,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..15ae97710120 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,67 @@ 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;
+ }
+ /* A flow may show a non-empty queue or a
+ * dropped packet now; scan again if the loop
+ * still cannot dequeue.
+ */
+ first = NULL;
+ scanned = false;
+ 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 +332,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