| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20101219212234.GA2323@del.dom.local>
Date: Sun, 19 Dec 2010 22:22:34 +0100
From: Jarek Poplawski <jarkao2@...il.com>
To: Eric Dumazet <eric.dumazet@...il.com>
Cc: Patrick McHardy <kaber@...sh.net>,
David Miller <davem@...emloft.net>,
netdev <netdev@...r.kernel.org>
Subject: Re: [RFC PATCH] net_sched: sch_sfq: better struct layouts
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.
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists