net_sched: sch_fq: round of optimizations
Subsystems (3)
cover net_sched: sch_fq: round of optimizations
This series is focused on better layout of struct fq_flow to reduce number of cache line misses in fq_enqueue() and dequeue operations.
Eric Dumazet (5):
net_sched: sch_fq: avoid touching f->next from fq_gc()
net_sched: sch_fq: change fq_flow size/layout
net_sched: sch_fq: use bulk freeing in fq_gc()
net_sched: sch_fq: do not call fq_peek() twice per packet
net_sched: sch_fq: perform a prefetch() earlier
net/sched/sch_fq.c | 86 ++++++++++++++++++++++++++-------------------- 1 file changed, 49 insertions(+), 37 deletions(-)
Signature · 1 line
2.26.2.526.g744177e7f7-goog
PATCH 1/5 net_sched: sch_fq: avoid touching f->next from fq_gc()
A significant amount of cpu cycles is spent in fq_gc()
When fq_gc() does its lookup in the rb-tree, it needs the following fields from struct fq_flow :
f->sk (lookup key in the rb-tree) f->fq_node (anchor in the rb-tree) f->next (used to determine if the flow is detached) f->age (used to determine if the flow is candidate for gc)
This unfortunately spans two cache lines (assuming 64 bytes cache lines)
We can avoid using f->next, if we use the low order bit of f->{age|tail}
This low order bit is 0, if f->tail points to an sk_buff. We set the low order bit to 1, if the union contains a jiffies value.
Combined with the following patch, this makes sure we only need to bring into cpu caches one cache line per flow.
--- net/sched/sch_fq.c | 21 +++++++++++++-------- 1 file changed, 13 insertions(+), 8 deletions(-)
net/sched/sch_fq.c +13 -8
@@ -70,14 +70,14 @@ struct fq_flow {struct sk_buff *head;/* list of skbs for this flow : first skb */ union {struct sk_buff *tail;/* last skb in the list */ -unsigned long age;/* jiffies when flow was emptied, for gc */ +unsigned long age;/* (jiffies | 1UL) when flow was emptied, for gc */ };struct rb_node fq_node;/* anchor in fq_root[] trees */ struct sock *sk;int qlen;/* number of packets in flow queue */ int credit;u32 socket_hash;/* sk_hash */ -struct fq_flow *next;/* next pointer in RR lists, or &detached */ +struct fq_flow *next;/* next pointer in RR lists */ struct rb_node rate_node;/* anchor in q->delayed tree */ u64 time_next_packet;
@@ -130,20 +130,25 @@ struct fq_sched_data {struct qdisc_watchdog watchdog; }; -/* special value to mark a detached flow (not on old/new list) */ -static struct fq_flow detached, throttled; - +/* +* f->tail and f->age share the same location. +* We can use the low order bit to differentiate if this location points +* to a sk_buff or contains a jiffies value, if we force this value to be odd. +* This assumes f->tail low order bit must be 0 since alignof(struct sk_buff) >= 2 +*/ static void fq_flow_set_detached (struct fq_flow *f) { - f->next = &detached; - f->age = jiffies; + f->age = jiffies |1UL ; }static bool fq_flow_is_detached (const struct fq_flow *f) { -return f->next == &detached; +return !!(f->age &1UL ); } +/* special value to mark a throttled flow (not on old/new list) */ +static struct fq_flow throttled; +static bool fq_flow_is_throttled (const struct fq_flow *f) {return f->next == &throttled;
Signature · 1 line
2.26.2.526.g744177e7f7-goog
PATCH 2/5 net_sched: sch_fq: change fq_flow size/layout
In reply to Eric Dumazetsizeof(struct fq_flow) is 112 bytes on 64bit arches.
This means that half of them use two cache lines, but 50% use three cache lines.
This patch adds cache line alignment, and makes sure that only the first cache line is touched by fq_enqueue(), which is more expensive that fq_dequeue() in general.
--- net/sched/sch_fq.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
net/sched/sch_fq.c +7 -2
@@ -66,6 +66,7 @@ static inline struct fq_skb_cb *fq_skb_cb(struct sk_buff *skb)* in linear list (head,tail), otherwise are placed in a rbtree (t_root). */ struct fq_flow { +/* First cache line : used in fq_gc(), fq_enqueue(), fq_dequeue() */ struct rb_root t_root;struct sk_buff *head;/* list of skbs for this flow : first skb */ union {
@@ -74,14 +75,18 @@ struct fq_flow { };struct rb_node fq_node;/* anchor in fq_root[] trees */ struct sock *sk; +u32 socket_hash;/* sk_hash */ int qlen;/* number of packets in flow queue */ + +/* Second cache line, used in fq_dequeue() */ int credit; -u32 socket_hash;/* sk_hash */ +/* 32bit hole on 64bit arches */ +struct fq_flow *next;/* next pointer in RR lists */ struct rb_node rate_node;/* anchor in q->delayed tree */ u64 time_next_packet; -}; +}____cacheline_aligned_in_smp ;struct fq_flow_head {struct fq_flow *first;
Signature · 1 line
2.26.2.526.g744177e7f7-goog
PATCH 3/5 net_sched: sch_fq: use bulk freeing in fq_gc()
In reply to Eric Dumazetfq_gc() already builds a small array of pointers, so using kmem_cache_free_bulk() needs very little change.
--- net/sched/sch_fq.c | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-)
net/sched/sch_fq.c +12 -8
@@ -218,9 +218,10 @@ static void fq_gc(struct fq_sched_data *q,struct rb_root *root, struct sock *sk) { - struct fq_flow *f, *tofree[FQ_GC_MAX]; struct rb_node **p, *parent; -int fcnt =0 ; +void *tofree[FQ_GC_MAX ]; +struct fq_flow *f; +int i, fcnt =0 ; p = &root->rb_node; parent =NULL ;
@@ -243,15 +244,18 @@ static void fq_gc(struct fq_sched_data *q, p = &parent->rb_left; } - q->flows -= fcnt; - q->inactive_flows -= fcnt; - q->stat_gc_flows += fcnt; -while (fcnt) { -struct fq_flow *f = tofree[--fcnt]; +if (!fcnt) +return ; +for (i = fcnt; i >0 ; ) { + f = tofree[--i];rb_erase (&f->fq_node, root); -kmem_cache_free (fq_flow_cachep, f); } + q->flows -= fcnt; + q->inactive_flows -= fcnt; + q->stat_gc_flows += fcnt; + +kmem_cache_free_bulk (fq_flow_cachep, fcnt, tofree); }static struct fq_flow *fq_classify (struct sk_buff *skb,struct fq_sched_data *q)
Signature · 1 line
2.26.2.526.g744177e7f7-goog
PATCH 4/5 net_sched: sch_fq: do not call fq_peek() twice per packet
In reply to Eric DumazetThis refactors the code to not call fq_peek() from fq_dequeue_head() since the caller can provide the skb.
Also rename fq_dequeue_head() to fq_dequeue_skb() because 'head' is a bit vague, given the skb could come from t_root rb-tree.
--- net/sched/sch_fq.c | 34 ++++++++++++++++------------------ 1 file changed, 16 insertions(+), 18 deletions(-)
net/sched/sch_fq.c +16 -18
@@ -388,19 +388,17 @@ static void fq_erase_head(struct Qdisc *sch, struct fq_flow *flow, } } -/* remove one skb from head of flow queue */ -static struct sk_buff *fq_dequeue_head (struct Qdisc *sch,struct fq_flow *flow) +/* Remove one skb from flow queue. +* This skb must be the return value of prior fq_peek(). +*/ +static void fq_dequeue_skb (struct Qdisc *sch,struct fq_flow *flow, +struct sk_buff *skb) { -struct sk_buff *skb =fq_peek (flow); - -if (skb) { -fq_erase_head (sch, flow, skb); -skb_mark_not_on_list (skb); - flow->qlen--; -qdisc_qstats_backlog_dec (sch, skb); - sch->q.qlen--; - } -return skb; +fq_erase_head (sch, flow, skb); +skb_mark_not_on_list (skb); + flow->qlen--; +qdisc_qstats_backlog_dec (sch, skb); + sch->q.qlen--; }static void flow_queue_add (struct fq_flow *flow,struct sk_buff *skb)
@@ -538,9 +536,11 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)if (!sch->q.qlen)return NULL ; - skb =fq_dequeue_head (sch, &q->internal); -if (skb) + skb =fq_peek (&q->internal); +if (unlikely (skb)) { +fq_dequeue_skb (sch, &q->internal, skb); goto out; + } q->ktime_cache = now =ktime_get_ns ();fq_check_throttled (q, now);
@@ -580,10 +580,8 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)INET_ECN_set_ce (skb); q->stat_ce_mark++; } - } - - skb =fq_dequeue_head (sch, f); -if (!skb) { +fq_dequeue_skb (sch, f, skb); + }else { head->first = f->next;/* force a pass through old_flows to prevent starvation */ if ((head == &q->new_flows) && q->old_flows.first) {
Signature · 1 line
2.26.2.526.g744177e7f7-goog
PATCH 5/5 net_sched: sch_fq: perform a prefetch() earlier
In reply to Eric DumazetThe prefetch() done in fq_dequeue() can be done a bit earlier after the refactoring of the code done in the prior patch.
--- net/sched/sch_fq.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
net/sched/sch_fq.c +1 -1
@@ -576,6 +576,7 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch)fq_flow_set_throttled (q, f); goto begin; } +prefetch (&skb->end);if ((s64)(now - time_next_packet - q->ce_threshold) >0 ) {INET_ECN_set_ce (skb); q->stat_ce_mark++;
@@ -592,7 +593,6 @@ static struct sk_buff *fq_dequeue(struct Qdisc *sch) } goto begin; } -prefetch (&skb->end); plen =qdisc_pkt_len (skb); f->credit -= plen;
Signature · 1 line
2.26.2.526.g744177e7f7-goog
David Miller
maintainerFrom: Eric Dumazet <[email protected]>
Date: Sat, 2 May 2020 19:54:17 -0700
Quoted 9 lines
This series is focused on better layout of struct
fq_flowto reduce number of cache line misses infq_enqueue()and dequeue operations.Eric Dumazet (5):
net_sched:sch_fq: avoid touchingf->nextfromfq_gc()
net_sched:sch_fq: changefq_flowsize/layout
net_sched:sch_fq: use bulk freeing infq_gc()
net_sched:sch_fq: do not callfq_peek()twice per packet
net_sched:sch_fq: perform aprefetch()earlier
Series applied, thanks Eric.