From: Jarek Poplawski <jarkao2@gmail.com>
To: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Patrick McHardy <kaber@trash.net>,
David Miller <davem@davemloft.net>,
netdev <netdev@vger.kernel.org>
Subject: Re: [RFC PATCH] net_sched: sch_sfq: better struct layouts
Date: Sun, 19 Dec 2010 22:22:34 +0100 [thread overview]
Message-ID: <20101219212234.GA2323@del.dom.local> (raw)
In-Reply-To: <1292604766.2906.51.camel@edumazet-laptop>
On Fri, Dec 17, 2010 at 05:52:46PM +0100, Eric Dumazet wrote:
> Le jeudi 16 décembre 2010 ?? 14:08 +0100, Eric Dumazet a écrit :
...
> > struct sfq_slot {
> > struct sk_buff *first;
> > struct sk_buff *last;
> > u8 qlen;
> > sfq_index next; /* dequeue chain */
> > u16 hash;
> > short allot;
> > /* 16bit hole */
> > };
> >
> > This would save 768 bytes on x86_64 (and much more if LOCKDEP is used)
I think open coding sk_buff_head is a wrong idea. Otherwise, this
patch looks OK to me, only a few cosmetic suggestions below.
>
> Here is a preliminary patch, shrinking sizeof(struct sfq_sched_data)
> from 0x14f8 (or more if spinlocks are bigger) to 0x1180 bytes, and
> reduce text size as well.
>
> text data bss dec hex filename
> 4821 152 0 4973 136d old/net/sched/sch_sfq.o
> 4651 136 0 4787 12b3 new/net/sched/sch_sfq.o
>
>
> All data for a slot/flow is now grouped in a compact and cache friendly
> structure :
>
> struct sfq_slot {
> struct sk_buff *skblist_next;
> struct sk_buff *skblist_prev;
> sfq_index qlen; /* number of skbs in skblist */
> sfq_index next; /* next slot in sfq chain */
> unsigned short hash; /* hash value (index in ht[]) */
> short allot; /* credit for this slot */
> struct sfq_head anchor; /* anchor in dep[] chains */
> };
>
>
>
> net/sched/sch_sfq.c | 223 +++++++++++++++++++++++-------------------
> 1 file changed, 125 insertions(+), 98 deletions(-)
>
> diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
> index 3cf478d..28968eb 100644
> --- a/net/sched/sch_sfq.c
> +++ b/net/sched/sch_sfq.c
> @@ -69,25 +69,40 @@
> This implementation limits maximal queue length to 128;
> maximal mtu to 2^15-1; number of hash buckets to 1024.
> The only goal of this restrictions was that all data
> - fit into one 4K page :-). Struct sfq_sched_data is
> - organized in anti-cache manner: all the data for a bucket
> - are scattered over different locations. This is not good,
> - but it allowed me to put it into 4K.
> + fit into one 4K page on 32bit arches.
>
> It is easy to increase these values, but not in flight. */
>
> -#define SFQ_DEPTH 128
> +#define SFQ_DEPTH 128 /* max number of packets per slot (per flow) */
> +#define SFQ_SLOTS 128 /* max number of flows */
> +#define EMPTY_SLOT 255
SFQ_EMPTY_SLOT?
> #define SFQ_HASH_DIVISOR 1024
>
> -/* This type should contain at least SFQ_DEPTH*2 values */
> +/* This type should contain at least SFQ_DEPTH + SFQ_SLOTS values */
> typedef unsigned char sfq_index;
>
> +/*
> + * We dont use pointers to save space.
> + * Small indexes [0 ... SFQ_SLOTS - 1] are 'pointers' to slots[] array
> + * while following values [SFQ_SLOTS ... SFQ_SLOTS + SFQ_DEPTH - 1]
> + * are 'pointers' to dep[] array
> + */
> struct sfq_head
> {
> sfq_index next;
> sfq_index prev;
> };
>
> +struct sfq_slot {
> + struct sk_buff *skblist_next;
> + struct sk_buff *skblist_prev;
> + sfq_index qlen; /* number of skbs in skblist */
> + sfq_index next; /* next slot in sfq chain */
> + unsigned short hash; /* hash value (index in ht[]) */
> + short allot; /* credit for this slot */
> + struct sfq_head anchor; /* anchor in dep[] chains */
struct sfq_head dep?
> +};
> +
> struct sfq_sched_data
> {
> /* Parameters */
> @@ -99,17 +114,24 @@ struct sfq_sched_data
> struct tcf_proto *filter_list;
> struct timer_list perturb_timer;
> u32 perturbation;
> - sfq_index tail; /* Index of current slot in round */
> - sfq_index max_depth; /* Maximal depth */
> + sfq_index max_depth; /* depth of longest slot */
depth and/or length? (One dimension should be enough.)
>
> + struct sfq_slot *tail; /* current slot in round */
> sfq_index ht[SFQ_HASH_DIVISOR]; /* Hash table */
> - sfq_index next[SFQ_DEPTH]; /* Active slots link */
> - short allot[SFQ_DEPTH]; /* Current allotment per slot */
> - unsigned short hash[SFQ_DEPTH]; /* Hash value indexed by slots */
> - struct sk_buff_head qs[SFQ_DEPTH]; /* Slot queue */
> - struct sfq_head dep[SFQ_DEPTH*2]; /* Linked list of slots, indexed by depth */
> + struct sfq_slot slots[SFQ_SLOTS];
> + struct sfq_head dep[SFQ_DEPTH]; /* Linked list of slots, indexed by depth */
> };
>
> +/*
> + * sfq_head are either in a sfq_slot or in dep[] array
> + */
> +static inline struct sfq_head *get_head(struct sfq_sched_data *q, sfq_index val)
static inline struct sfq_head *sfq_dep_head()?
...
> @@ -304,31 +328,36 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
> hash--;
>
> x = q->ht[hash];
> - if (x == SFQ_DEPTH) {
> - q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
> - q->hash[x] = hash;
> + slot = &q->slots[x];
> + if (x == EMPTY_SLOT) {
> + x = q->dep[0].next; /* get a free slot */
> + q->ht[hash] = x;
> + slot = &q->slots[x];
> + slot->hash = hash;
> + slot->skblist_next = slot->skblist_prev = (struct sk_buff *)slot;
> }
>
> - /* If selected queue has length q->limit, this means that
> - * all another queues are empty and that we do simple tail drop,
No reason to remove this line.
> + /* If selected queue has length q->limit, do simple tail drop,
> * i.e. drop _this_ packet.
> */
> - if (q->qs[x].qlen >= q->limit)
> + if (slot->qlen >= q->limit)
> return qdisc_drop(skb, sch);
>
> sch->qstats.backlog += qdisc_pkt_len(skb);
> - __skb_queue_tail(&q->qs[x], skb);
> + skb->prev = slot->skblist_prev;
> + skb->next = (struct sk_buff *)slot;
> + slot->skblist_prev->next = skb;
> + slot->skblist_prev = skb;
If you really have to do this, all these: __skb_queue_tail(),
__skb_dequeue(), skb_queue_head_init(), skb_peek() etc. used here
should stay as (local) inline functions to remain readability.
Jarek P.
next prev parent reply other threads:[~2010-12-19 21:22 UTC|newest]
Thread overview: 40+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-12-15 14:03 [PATCH] net_sched: sch_sfq: fix allot handling Eric Dumazet
2010-12-15 16:03 ` Patrick McHardy
2010-12-15 16:27 ` Eric Dumazet
2010-12-15 16:40 ` [PATCH v2] " Eric Dumazet
2010-12-15 16:43 ` Patrick McHardy
2010-12-15 16:55 ` Eric Dumazet
2010-12-15 17:03 ` Patrick McHardy
2010-12-15 17:09 ` Eric Dumazet
2010-12-15 17:21 ` Patrick McHardy
2010-12-15 17:30 ` [PATCH v3] " Eric Dumazet
2010-12-15 18:18 ` [PATCH net-next-2.6] net_sched: sch_sfq: add backlog info in sfq_dump_class_stats() Eric Dumazet
2010-12-15 19:10 ` Eric Dumazet
2010-12-16 8:16 ` Jarek Poplawski
2010-12-16 10:18 ` [PATCH v2 " Eric Dumazet
2010-12-16 11:03 ` [PATCH " Eric Dumazet
2010-12-16 13:09 ` Jarek Poplawski
2010-12-20 21:14 ` David Miller
2010-12-20 21:18 ` [PATCH v3] net_sched: sch_sfq: fix allot handling David Miller
2010-12-16 13:08 ` [PATCH v2] " Eric Dumazet
2010-12-17 16:52 ` [RFC PATCH] net_sched: sch_sfq: better struct layouts Eric Dumazet
2010-12-19 21:22 ` Jarek Poplawski [this message]
2010-12-20 17:02 ` [PATCH v2] " Eric Dumazet
2010-12-20 21:33 ` David Miller
2010-12-20 21:42 ` Eric Dumazet
2010-12-20 22:54 ` [PATCH v3 net-next-2.6] " Eric Dumazet
2010-12-21 5:33 ` David Miller
2010-12-20 22:55 ` [PATCH v2] " Jarek Poplawski
2010-12-20 23:16 ` [PATCH net-next-2.6] sch_sfq: allow big packets and be fair Eric Dumazet
2010-12-21 10:15 ` Jarek Poplawski
2010-12-21 10:30 ` Jarek Poplawski
2010-12-21 10:44 ` Eric Dumazet
2010-12-21 10:56 ` Jarek Poplawski
2010-12-21 10:57 ` Eric Dumazet
2010-12-21 11:39 ` Jarek Poplawski
2010-12-21 12:17 ` Jarek Poplawski
2010-12-21 13:04 ` [PATCH v2 " Eric Dumazet
2010-12-21 13:47 ` Jarek Poplawski
2010-12-28 21:46 ` David Miller
2010-12-29 7:53 ` [PATCH v3 " Eric Dumazet
2010-12-31 20:48 ` David Miller
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20101219212234.GA2323@del.dom.local \
--to=jarkao2@gmail.com \
--cc=davem@davemloft.net \
--cc=eric.dumazet@gmail.com \
--cc=kaber@trash.net \
--cc=netdev@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.