From: Patrick McHardy <kaber@trash•net>
To: Eric Dumazet <eric.dumazet@gmail•com>
Cc: David Miller <davem@davemloft•net>,
Juliusz Chroboczek <Juliusz.Chroboczek@pps•jussieu.fr>,
"John W. Linville" <linville@tuxdriver•com>,
Stephen Hemminger <shemminger@vyatta•com>,
netdev <netdev@vger•kernel.org>, Andi Kleen <andi@firstfloor•org>
Subject: Re: [PATCH net-next-2.6 v3] net_sched: SFB flow scheduler
Date: Wed, 23 Feb 2011 17:24:35 +0100 [thread overview]
Message-ID: <4D6534C3.1080305@trash.net> (raw)
In-Reply-To: <1298474091.3301.364.camel@edumazet-laptop>
Am 23.02.2011 16:14, schrieb Eric Dumazet:
> diff --git a/include/net/sch_generic.h b/include/net/sch_generic.h
> index 16626a0..f40d32e 100644
> --- a/include/net/sch_generic.h
> +++ b/include/net/sch_generic.h
> @@ -218,6 +218,7 @@ struct tcf_proto {
>
> struct qdisc_skb_cb {
> unsigned int pkt_len;
> + unsigned int sfb_classid;
> char data[];
> };
This could be moved into a SFB specific cb, similar to what netem
does.
> diff --git a/net/sched/sch_sfb.c b/net/sched/sch_sfb.c
> new file mode 100644
> index 0000000..b7f1c6e
> --- /dev/null
> +++ b/net/sched/sch_sfb.c
> @@ -0,0 +1,696 @@
> +/*
> + * net/sched/sch_sfb.c Stochastic Fair Blue
> + *
> + * Copyright (c) 2008-2011 Juliusz Chroboczek <jch@pps•jussieu.fr>
> + * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail•com>
> + *
> + * This program is free software; you can redistribute it and/or
> + * modify it under the terms of the GNU General Public License
> + * version 2 as published by the Free Software Foundation.
> + *
> + * W. Feng, D. Kandlur, D. Saha, K. Shin. Blue:
> + * A New Class of Active Queue Management Algorithms.
> + * U. Michigan CSE-TR-387-99, April 1999.
> + *
> + * http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf
> + *
> + */
> +
> +#include <linux/module.h>
> +#include <linux/types.h>
> +#include <linux/kernel.h>
> +#include <linux/errno.h>
> +#include <linux/skbuff.h>
> +#include <linux/random.h>
> +#include <linux/jhash.h>
> +#include <net/ip.h>
> +#include <net/pkt_sched.h>
> +#include <net/inet_ecn.h>
> +
> +/*
> + * SFB uses two B[l][n] : L x N arrays of bins (L levels, N bins per level)
> + * This implementation uses L = 8 and N = 16
> + * This permits us to split one 32bit hash (provided per packet by rxhash or
> + * external classifier) into 8 subhashes of 4 bits.
> + */
> +#define SFB_BUCKET_SHIFT 4
If you want to make this dynamic, there are a couple of papers analyzing
combined hash functions for bloom filters, f.i.
"Less Hashing, Same Performance: Building a Better Bloom Filter".
> +/*
> + * If using 'internal' SFB flow classifier, sfb_classid is skb rxhash
> + * If using external classifier, sfb_classid contains the classid.
> + */
> +static u32 sfb_hash(const struct sk_buff *skb, u32 slot,
> + struct sfb_sched_data *q)
> +{
> + return jhash_1word(qdisc_skb_cb(skb)->sfb_classid,
> + q->bins[slot].perturbation);
> +}
> +
> +/* Probabilities are coded as Q0.16 fixed-point values,
> + * with 0xFFFF representing 65535/65536 (almost 1.0)
> + * Addition and subtraction are saturating in [0, 65535]
> + */
> +static u32 prob_plus(u32 p1, u32 p2)
> +{
> + u32 res = p1 + p2;
> +
> + return min_t(u32, res, SFB_MAX_PROB);
> +}
> +
> +static u32 prob_minus(u32 p1, u32 p2)
> +{
> + return p1 > p2 ? p1 - p2 : 0;
> +}
> +
> +static void increment_one_qlen(u32 sfbhash, u32 slot, struct sfb_sched_data *q)
> +{
> + int i;
> + struct sfb_bucket *b = &q->bins[slot].bins[0][0];
> +
> + for (i = 0; i < SFB_LEVELS; i++) {
> + u32 hash = sfbhash & SFB_BUCKET_MASK;
> +
> + sfbhash >>= SFB_BUCKET_SHIFT;
> + if (b[hash].qlen < 0xFFFF)
> + b[hash].qlen++;
> + b += SFB_NUMBUCKETS; /* next level */
> + }
> +}
> +
> +static void increment_qlen(u32 hashes[2], struct sfb_sched_data *q)
> +{
> + u32 slot = q->slot;
> +
> + increment_one_qlen(hashes[slot], slot, q);
> + if (q->double_buffering) {
> + slot ^= 1;
> + increment_one_qlen(hashes[slot], slot, q);
> + }
> +}
> +
> +static void decrement_one_qlen(u32 sfbhash, u32 slot,
> + struct sfb_sched_data *q)
> +{
> + int i;
> + struct sfb_bucket *b = &q->bins[slot].bins[0][0];
> +
> + for (i = 0; i < SFB_LEVELS; i++) {
> + u32 hash = sfbhash & SFB_BUCKET_MASK;
> +
> + sfbhash >>= SFB_BUCKET_SHIFT;
> + if (b[hash].qlen > 0)
> + b[hash].qlen--;
> + b += SFB_NUMBUCKETS; /* next level */
> + }
> +}
> +
> +static void decrement_qlen(struct sk_buff *skb, struct sfb_sched_data *q)
> +{
> + u32 slot = q->slot;
> + u32 sfbhash = sfb_hash(skb, slot, q);
> +
> + decrement_one_qlen(sfbhash, slot, q);
> + if (q->double_buffering) {
This needs to be a per-skb property, otherwise you could have the
situation:
- enqueue skb, double_buffering=0, increment buffer 0
- enable double buffering
- swap buffers
- dequeue same skb, decrement buffer 1
after which the qlen values of buffer 1 will be incorrect.
> + slot ^= 1;
> + sfbhash = sfb_hash(skb, slot, q);
Isn't there room in the cb to store both hash values?
> + decrement_one_qlen(sfbhash, slot, q);
> + }
> +}
> +
next prev parent reply other threads:[~2011-02-23 16:24 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20110221160306.GA9650@tuxdriver.com>
[not found] ` <1298308283.2849.5.camel@edumazet-laptop>
[not found] ` <1298390536.2861.9.camel@edumazet-laptop>
2011-02-23 15:14 ` [PATCH net-next-2.6 v3] net_sched: SFB flow scheduler Eric Dumazet
2011-02-23 15:43 ` Stephen Hemminger
2011-02-23 16:13 ` Eric Dumazet
2011-02-23 16:20 ` Patrick McHardy
2011-02-23 16:24 ` Patrick McHardy [this message]
2011-02-23 16:48 ` Eric Dumazet
2011-02-23 16:58 ` Patrick McHardy
2011-02-23 17:16 ` Eric Dumazet
2011-02-23 17:05 ` [PATCH] net_sched: long word align struct qdisc_skb_cb data Eric Dumazet
2011-02-23 17:30 ` Stephen Hemminger
2011-02-23 22:17 ` David Miller
2011-02-23 20:56 ` [PATCH net-next-2.6 v4] net_sched: SFB flow scheduler Eric Dumazet
2011-02-23 21:11 ` Stephen Hemminger
2011-02-23 21:28 ` Eric Dumazet
2011-02-23 21:30 ` David Miller
2011-02-23 22:06 ` David Miller
2011-02-24 5:40 ` Eric Dumazet
2011-02-24 6:51 ` Stephen Hemminger
2011-02-24 7:14 ` Eric Dumazet
2011-02-24 7:18 ` Eric Dumazet
2011-03-24 17:44 ` [PATCH iproute2] tc : " Eric Dumazet
2011-03-24 21:59 ` Stephen Hemminger
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=4D6534C3.1080305@trash.net \
--to=kaber@trash$(echo .)net \
--cc=Juliusz.Chroboczek@pps$(echo .)jussieu.fr \
--cc=andi@firstfloor$(echo .)org \
--cc=davem@davemloft$(echo .)net \
--cc=eric.dumazet@gmail$(echo .)com \
--cc=linville@tuxdriver$(echo .)com \
--cc=netdev@vger$(echo .)kernel.org \
--cc=shemminger@vyatta$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox