net_sched: SFB flow scheduler
Subsystems (3)
PATCH v3 1/1 net_sched: SFB flow scheduler
In reply to a message not in the archiveHi David & Juliusz
Here is v3 of SFB. (previous ones were from Juliusz)
Thanks
[PATCH net-next-2.6 v3] net_sched: SFB flow scheduler
This is the Stochastic Fair Blue scheduler, based on work from :
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
This implementation is based on work done by Juliusz Chroboczek
General SFB algorithm can be found in figure 14, page 15:
B[l][n] : L x N array of bins (L levels, N bins per level) enqueue()
Calculate hash function values h{0}, h{1}, .. h{L-1} Update bins at each level
for i = 0 to L - 1
if (B[i][h{i}].qlen > bin_size)
B[i][h{i}].pm += delta;
else if (B[i][h{i}].qlen == 0)
B[i][h{i}].pm -= delta;
pmin = min(B[0][h{0}].pm ... B[L-1][h{L-1}].pm);
if (pmin == 1.0)
ratelimit();
else
mark/drop with probabilty pmin;I did the adaptation of Juliusz code to meet current kernel standards, and various changes to address previous comments :
http://thread.gmane.org/gmane.linux.network/90225
http://thread.gmane.org/gmane.linux.network/90375
Default flow classifier is the rxhash introduced by RPS in 2.6.35, but we can use an external flow classifier if wanted.
tc qdisc add dev $IFB parent 1:11 handle 11: \
est 0.5sec 2sec sfb limit 128
tc filter add dev $DEV protocol ip parent 11: handle 3 \
flow hash keys dst divisor 1024
Notes:
1) SFB default child qdisc is pfifo_fast. It can be changed by another qdisc but a child qdisc MUST not drop a packet previously queued. This is because SFB needs to handle a dequeued packet in order to maintain its virtual queue states. pfifo_head_drop or CHOKe should not be used.
2) I added one field in qdisc_skb_cb because SFB needs to remember the hash/classid of an skb to decrement virtual queue lengthes at dequeue() time.
3) ECN is enabled by default, unlike RED/CHOKe/GRED
With help from Patrick McHardy & Andi Kleen
--- include/linux/pkt_sched.h | 38 + include/net/sch_generic.h | 1 net/sched/Kconfig | 11 net/sched/Makefile | 1 net/sched/sch_sfb.c | 696 ++++++++++++++++++++++++++++++++++++ 5 files changed, 747 insertions(+)
include/linux/pkt_sched.h +38 -0
@@ -522,4 +522,42 @@ struct tc_mqprio_qopt { __u16 offset[TC_QOPT_MAX_QUEUE]; }; +/* SFB */ + +enum { +TCA_SFB_UNSPEC , +TCA_SFB_PARMS , + __TCA_SFB_MAX, +}; + +#define TCA_SFB_MAX (__TCA_SFB_MAX - 1) + +/* +* Note: increment, decrement are Q0.16 fixed-point values. +*/ +struct tc_sfb_qopt { +__u32 rehash_interval;/* delay between hash flip, in seconds */ +__u32 db_interval;/* double buffering interval in seconds (db_interval < rehash_interval) */ +__u32 max;/* max len of qlen_min */ +__u32 target;/* bin_size */ +__u32 increment;/* delta, (d1 in Blue) */ +__u32 decrement;/* delta, (d2 in Blue) */ +__u32 limit;/* max SFB queue length */ +__u32 penalty_rate; +__u32 penalty_burst; +}; + +struct tc_sfb_xstats { +__u32 earlydrop; +__u32 penaltydrop; +__u32 bucketdrop; +__u32 queuedrop; +__u32 childdrop;/* drops in child qdisc */ +__u32 marked; +__u32 maxqlen; +__u32 maxprob; +}; + +#define SFB_MAX_PROB 0xFFFF +#endif
include/net/sch_generic.h +1 -0
@@ -218,6 +218,7 @@ struct tcf_proto {struct qdisc_skb_cb {unsigned int pkt_len; +unsigned int sfb_classid;char data[]; };
net/sched/Kconfig +11 -0
@@ -126,6 +126,17 @@ config NET_SCH_RED To compile this code as a module, choose M here: the module will be called sch_red. +config NET_SCH_SFB + tristate "Stochastic Fair Blue (SFB)" + ---help--- + Say Y here if you want to use the Stochastic Fair Blue (SFB) + packet scheduling algorithm. + + See the top of <file:net/sched/sch_sfb.c> for more details. + + To compile this code as a module, choose M here: the + module will be called sch_sfb. + config NET_SCH_SFQ tristate "Stochastic Fairness Queueing (SFQ)" ---help---
net/sched/Makefile +1 -0
@@ -24,6 +24,7 @@ obj-$(CONFIG_NET_SCH_RED) += sch_red.o obj-$(CONFIG_NET_SCH_GRED) += sch_gred.o obj-$(CONFIG_NET_SCH_INGRESS) += sch_ingress.o obj-$(CONFIG_NET_SCH_DSMARK) += sch_dsmark.o +obj-$(CONFIG_NET_SCH_SFB) += sch_sfb.o obj-$(CONFIG_NET_SCH_SFQ) += sch_sfq.o obj-$(CONFIG_NET_SCH_TBF) += sch_tbf.o obj-$(CONFIG_NET_SCH_TEQL) += sch_teql.o
net/sched/sch_sfb.c new file +696 -0
696 lines not on this page · raw message
Quoted 4 lines · On Wed, 23 Feb 2011 16:14:51 +0100 Eric Dumazet <[email protected]> wrote:
1) SFB default child qdisc is
pfifo_fast. It can be changed by another qdisc but a child qdisc MUST not drop a packet previously queued. This is because SFB needs to handle a dequeued packet in order to maintain its virtual queue states.pfifo_head_dropor CHOKe should not be used.
Why not add a flag field to Qdisc_ops and to mark qdisc's that are (or not) work conserving?
Quoted 11 lines · Stephen Hemminger
Quoted 4 lines · On Wed, 23 Feb 2011 16:14:51 +0100 Eric Dumazet <[email protected]> wrote:
1) SFB default child qdisc is
pfifo_fast. It can be changed by another qdisc but a child qdisc MUST not drop a packet previously queued. This is because SFB needs to handle a dequeued packet in order to maintain its virtual queue states.pfifo_head_dropor CHOKe should not be used.Why not add a flag field to
Qdisc_opsand to mark qdisc's that are (or not) work conserving?
That was my initial idea, but have no idea how to implement it (outside of fast path, I mean...)
Am 23.02.2011 17:13, schrieb Eric Dumazet:
Quoted 9 lines · Stephen Hemminger
Quoted 8 lines
Quoted 4 lines · On Wed, 23 Feb 2011 16:14:51 +0100 Eric Dumazet <[email protected]> wrote:
1) SFB default child qdisc is
pfifo_fast. It can be changed by another qdisc but a child qdisc MUST not drop a packet previously queued. This is because SFB needs to handle a dequeued packet in order to maintain its virtual queue states.pfifo_head_dropor CHOKe should not be used.
Quoted 6 lines
Quoted 3 lines
Why not add a flag field to
Qdisc_opsand to mark qdisc's that are (or not) work conserving?That was my initial idea, but have no idea how to implement it (outside of fast path, I mean...)
This also doesn't really have anything to do with work-conserving qdiscs, SFB f.i. is work conserving, but still might drop other packets. Actually I don't think there's any qdisc besides the *fifos that can reasonably be used with SFB, so we might as well only support a built-in qdisc.
Am 23.02.2011 16:14, schrieb Eric Dumazet:
include/net/sch_generic.h struct tcf_proto { · line 223
Quoted 11 lines
include/net/sch_generic.h +1
-0@@ -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.
Quoted 32 lines
net/sched/sch_sfb.c new file +26
-0@@ -0,0 +1,696 @@ +/* +* net/sched/sch_sfb.c Stochastic Fair Blue +* +* Copyright (c) 2008-2011 Juliusz Chroboczek <[email protected]> +* Copyright (c) 2011 Eric Dumazet <[email protected]> +* +* 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>
net/sched/sch_sfb.c line 36
Quoted 10 lines
net/sched/sch_sfb.c new file +10
-0+#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".
Quoted 66 lines
net/sched/sch_sfb.c new file +66
-0+/* +* 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 */
net/sched/sch_sfb.c line 160
Quoted 10 lines
net/sched/sch_sfb.c new file +10
-0+ } +} + +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.
net/sched/sch_sfb.c line 114
Quoted 2 lines
net/sched/sch_sfb.c new file +2
-0+ slot ^=1 ; + sfbhash =sfb_hash (skb, slot, q);
Isn't there room in the cb to store both hash values?
Quoted 4 lines
net/sched/sch_sfb.c new file +4
-0+decrement_one_qlen (sfbhash, slot, q); + } +} +
Quoted 10 lines · Patrick McHardy
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 1after which the qlen values of buffer 1 will be incorrect.
Normally its OK, because we bzero() the zone, and the "decrement" is 0-bounded.
I had this idea (of storing two bits per skb), but :
- It means that swap_buffer() should not touch (bzero) the 'old' bins
- Since hash perturbator is changed, we have to store the two hash values per skb (instead of one u32 / classid).
Quoted 5 lines
Review
Quoted 3 lines
(quoted diff) +2
-0+ slot ^= 1; + sfbhash = sfb_hash(skb, slot, q);Isn't there room in the cb to store both hash values?
Yes, I am going to implement your idea, its probably OK to use two u32 on skb_cb for this.
Thanks !
Am 23.02.2011 17:48, schrieb Eric Dumazet:
Quoted 10 lines · Patrick McHardy
Quoted 9 lines
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
Quoted 5 lines
Quoted 2 lines
after which the qlen values of buffer 1 will be incorrect.
Normally its OK, because we
bzero()the zone, and the "decrement" is 0-bounded.
Yeah, but we might decrement buckets of different flows which are non-zero. Probably not too bad, but still not correct.
Quoted 3 lines
I had this idea (of storing two bits per skb), but :
- It means that
swap_buffer()should not touch (bzero) the 'old' bins
Yes, it means we have to properly decrement the old buffer until all bins reached zero.
Quoted 2 lines
- Since hash perturbator is changed, we have to store the two hash values per skb (instead of one u32 / classid).
Indeed.
PATCH 1/1 net_sched: long word align struct qdisc_skb_cb data
In reply to Patrick McHardyQuoted 7 lines · Patrick McHardy
Am 23.02.2011 16:14, schrieb Eric Dumazet:
Quoted 6 lines
include/net/sch_generic.h +0
-0@@ -218,6 +218,7 @@ struct tcf_proto {
Quoted 8 lines
include/net/sch_generic.h struct tcf_proto { · line 223
Quoted 5 lines
include/net/sch_generic.h +1
-0struct 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.
Hmm... well... I want to be sure no other sch will destroy my values.
netem seems buggy then.
Probably following patch is needed ?
Thanks
[PATCH] net_sched: long word align struct qdisc_skb_cb data
netem_skb_cb() does :
return (struct netem_skb_cb *)qdisc_skb_cb(skb)->data;
Unfortunatly struct qdisc_skb_cb data is not long word aligned, so access to psched_time_t time_to_send uses a non aligned access.
--- include/net/sch_generic.h | 2 +- 1 files changed, 1 insertion(+), 1 deletion(-)
include/net/sch_generic.h +1 -1
@@ -218,7 +218,7 @@ struct tcf_proto {struct qdisc_skb_cb {unsigned int pkt_len; -char data[]; +long data[]; };static inline int qdisc_qlen (struct Qdisc *q)
Quoted 24 lines · Patrick McHardy
Am 23.02.2011 17:48, schrieb Eric Dumazet:
Quoted 10 lines · Patrick McHardy
Quoted 9 lines
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 1Quoted 5 lines
Quoted 2 lines
after which the qlen values of buffer 1 will be incorrect.
Normally its OK, because we
bzero()the zone, and the "decrement" is 0-bounded.Yeah, but we might decrement buckets of different flows which are non-zero. Probably not too bad, but still not correct.
Quoted 3 lines
I had this idea (of storing two bits per skb), but :
- It means that
swap_buffer()should not touch (bzero) the 'old' bins
Quoted 7 lines
Yes, it means we have to properly decrement the old buffer until all bins reached zero.
Quoted 2 lines
- Since hash perturbator is changed, we have to store the two hash values per skb (instead of one u32 / classid).
Indeed.
BTQ, I had this idea of storing the double_buffer per skb reading SFB paper, because paper says the double buffering is really needed only for unelastic flows, not for all packets.
paper quote :
As one set of bins is being used
for queue management, a second set of bins using the next set of hash functions can be warmed up. In this
case, any time a flow is classified as non-responsive, it is hashed using the second set of hash functions and
the marking probabilities of the corresponding bins in the warmup set are updated.
So using two 'hash' values per skb is the way to go, with special 0 value meanings : skb was not 'inserted' into virtual queues.
Re: [PATCH] net_sched: long word align struct qdisc_skb_cb data
In reply to Eric DumazetQuoted 17 lines · On Wed, 23 Feb 2011 18:05:07 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 7 lines · Patrick McHardy
Am 23.02.2011 16:14, schrieb Eric Dumazet:
Quoted 6 lines
include/net/sch_generic.h +0
-0@@ -218,6 +218,7 @@ struct tcf_proto {Quoted 8 lines
include/net/sch_generic.h struct tcf_proto { · line 222
Quoted 5 lines
include/net/sch_generic.h +1
-0struct 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.
Quoted 5 lines
Hmm... well... I want to be sure no other sch will destroy my values.
netem seems buggy then.
Probably following patch is needed ?
Yes, it was long word aligned when netem was written but we seem to have bit creep.
PATCH v4 1/1 net_sched: SFB flow scheduler
In reply to Eric DumazetThis is the Stochastic Fair Blue scheduler, based on work from :
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
This implementation is based on work done by Juliusz Chroboczek
General SFB algorithm can be found in figure 14, page 15:
B[l][n] : L x N array of bins (L levels, N bins per level) enqueue()
Calculate hash function values h{0}, h{1}, .. h{L-1} Update bins at each level
for i = 0 to L - 1
if (B[i][h{i}].qlen > bin_size)
B[i][h{i}].p_mark += p_increment;
else if (B[i][h{i}].qlen == 0)
B[i][h{i}].p_mark -= p_decrement;
p_min = min(B[0][h{0}].p_mark ... B[L-1][h{L-1}].p_mark);
if (p_min == 1.0)
ratelimit();
else
mark/drop with probabilty p_min;I did the adaptation of Juliusz code to meet current kernel standards, and various changes to address previous comments :
http://thread.gmane.org/gmane.linux.network/90225
http://thread.gmane.org/gmane.linux.network/90375
Default flow classifier is the rxhash introduced by RPS in 2.6.35, but we can use an external flow classifier if wanted.
tc qdisc add dev $DEV parent 1:11 handle 11: \
est 0.5sec 2sec sfb limit 128
tc filter add dev $DEV protocol ip parent 11: handle 3 \
flow hash keys dst divisor 1024
Notes:
1) SFB default child qdisc is pfifo_fast. It can be changed by another qdisc but a child qdisc MUST not drop a packet previously queued. This is because SFB needs to handle a dequeued packet in order to maintain its virtual queue states. pfifo_head_drop or CHOKe should not be used.
2) ECN is enabled by default, unlike RED/CHOKe/GRED
With help from Patrick McHardy & Andi Kleen
---
V4: added sfb_skb_cb to hold two hashes values per skb
double buffering takes place only for inelastic flows some fields renames.
timeouts are now given in ms instead of seconds
include/linux/pkt_sched.h | 39 + net/sched/Kconfig | 11 net/sched/Makefile | 1 net/sched/sch_sfb.c | 709 ++++++++++++++++++++++++++++++++++++ 4 files changed, 760 insertions(+)
include/linux/pkt_sched.h +39 -0
@@ -522,4 +522,43 @@ struct tc_mqprio_qopt { __u16 offset[TC_QOPT_MAX_QUEUE]; }; +/* SFB */ + +enum { +TCA_SFB_UNSPEC , +TCA_SFB_PARMS , + __TCA_SFB_MAX, +}; + +#define TCA_SFB_MAX (__TCA_SFB_MAX - 1) + +/* +* Note: increment, decrement are Q0.16 fixed-point values. +*/ +struct tc_sfb_qopt { +__u32 rehash_interval;/* delay between hash move, in ms */ +__u32 warmup_time;/* double buffering warmup time in ms (warmup_time < rehash_interval) */ +__u32 max;/* max len of qlen_min */ +__u32 bin_size;/* maximum queue length per bin */ +__u32 increment;/* probability increment, (d1 in Blue) */ +__u32 decrement;/* probability decrement, (d2 in Blue) */ +__u32 limit;/* max SFB queue length */ +__u32 penalty_rate;/* inelastic flows are rate limited to 'rate' pps */ +__u32 penalty_burst; +}; + +struct tc_sfb_xstats { +__u32 earlydrop; +__u32 penaltydrop; +__u32 bucketdrop; +__u32 queuedrop; +__u32 childdrop;/* drops in child qdisc */ +__u32 marked; +__u32 maxqlen; +__u32 maxprob; +__u32 avgprob; +}; + +#define SFB_MAX_PROB 0xFFFF +#endif
net/sched/Kconfig +11 -0
@@ -126,6 +126,17 @@ config NET_SCH_RED To compile this code as a module, choose M here: the module will be called sch_red. +config NET_SCH_SFB + tristate "Stochastic Fair Blue (SFB)" + ---help--- + Say Y here if you want to use the Stochastic Fair Blue (SFB) + packet scheduling algorithm. + + See the top of <file:net/sched/sch_sfb.c> for more details. + + To compile this code as a module, choose M here: the + module will be called sch_sfb. + config NET_SCH_SFQ tristate "Stochastic Fairness Queueing (SFQ)" ---help---
net/sched/Makefile +1 -0
@@ -24,6 +24,7 @@ obj-$(CONFIG_NET_SCH_RED) += sch_red.o obj-$(CONFIG_NET_SCH_GRED) += sch_gred.o obj-$(CONFIG_NET_SCH_INGRESS) += sch_ingress.o obj-$(CONFIG_NET_SCH_DSMARK) += sch_dsmark.o +obj-$(CONFIG_NET_SCH_SFB) += sch_sfb.o obj-$(CONFIG_NET_SCH_SFQ) += sch_sfq.o obj-$(CONFIG_NET_SCH_TBF) += sch_tbf.o obj-$(CONFIG_NET_SCH_TEQL) += sch_teql.o
net/sched/sch_sfb.c new file +709 -0
709 lines not on this page · raw message
Quoted 1 line · On Wed, 23 Feb 2011 21:56:17 +0100 Eric Dumazet <[email protected]> wrote:
+struct
Qdisc_opssfb_qdisc_ops__read_mostly= {
Should be static?
Quoted 8 lines · Stephen Hemminger
Quoted 1 line · On Wed, 23 Feb 2011 21:56:17 +0100 Eric Dumazet <[email protected]> wrote:
+struct
Qdisc_opssfb_qdisc_ops__read_mostly= {Should be static?
Sure ! ;)
David Miller
maintainerFrom: Eric Dumazet <[email protected]>
Date: Wed, 23 Feb 2011 22:28:36 +0100
Quoted 11 lines · Stephen Hemminger
Quoted 8 lines
Quoted 1 line · On Wed, 23 Feb 2011 21:56:17 +0100 Eric Dumazet <[email protected]> wrote:
+struct
Qdisc_opssfb_qdisc_ops__read_mostly= {Should be static?
Sure ! ;)
I can make this simple fixup when I apply the patch to net-next-2.6, Eric you don't have to respin it just for this.
David Miller
maintainerFrom: Eric Dumazet <[email protected]>
Date: Wed, 23 Feb 2011 21:56:17 +0100
Quoted 1 line
This is the Stochastic Fair Blue scheduler, based on work from :
Applied with the 'static' fix, thanks Eric!
Re: [PATCH] net_sched: long word align struct qdisc_skb_cb data
In reply to Stephen HemmingerFrom: Stephen Hemminger <[email protected]>
Date: Wed, 23 Feb 2011 09:30:01 -0800
Quoted 20 lines
Quoted 17 lines · On Wed, 23 Feb 2011 18:05:07 +0100 Eric Dumazet <[email protected]> wrote:
Quoted 15 lines · Patrick McHardy
Am 23.02.2011 16:14, schrieb Eric Dumazet:
include/net/sch_generic.h struct tcf_proto { · line 223
Quoted 11 lines
include/net/sch_generic.h +1
-0@@ -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.
Quoted 8 lines
Quoted 5 lines
Hmm... well... I want to be sure no other sch will destroy my values.
netem seems buggy then.
Probably following patch is needed ?
Yes, it was long word aligned when netem was written but we seem to have bit creep.
Applied to net-2.6, thanks!
Quoted 6 lines · David Miller
From: Eric Dumazet <[email protected]>
Date: Wed, 23 Feb 2011 21:56:17 +0100Quoted 1 line
This is the Stochastic Fair Blue scheduler, based on work from :
Applied with the 'static' fix, thanks Eric!
Thanks David !
My next step is to expand the idea I had some time ago (with my SFQ works in december) :
Add a generic (core) service :
- Timestamp skb when it enters qdisc (might use skb->tstamp ?)
- At dequeue time, compute the delay.
1) Be able to mark/drop the packet right before giving it to device if delay above a threshold, or use an array of thresholds depending on TOS
2) Integrate the delay into one EWMA
3) For SFB : Use the EWMA to eventually replace the non convenient penalty_box by auto adaptative mechanism : Allow non elastic flows to take part of the bandwidth, using a drop/mark probability depending on this EWMA.
Where is the iproute (q_sfb) piece?
Quoted 3 lines · Stephen Hemminger
Where is the iproute (
q_sfb) piece?
I'll send it this morning after polishing.
As a matter of fact, I might add Patrick idea to use nested attributes, before official SFB release.
Thanks
Quoted 10 lines · Eric Dumazet
Quoted 3 lines · Stephen Hemminger
Where is the iproute (
q_sfb) piece?I'll send it this morning after polishing.
As a matter of fact, I might add Patrick idea to use nested attributes, before official SFB release.
BTW, one can use old iproute (tc command) for SFB with default params.
PATCH 1/1 tc : SFB flow scheduler
In reply to Stephen HemmingerFrom: Juliusz Chroboczek <[email protected]>
Supports SFB qdisc (included in linux-2.6.39)
1) Setup phase : accept non default parameters
2) dump information
qdisc sfb 11: parent 1:11 limit 1 max 25 target 20
increment 0.00050 decrement 0.00005 penalty rate 10 burst 20 (600000ms 60000ms)
Sent 47991616 bytes 521648 pkt (dropped 549245, overlimits 549245 requeues 0) rate 7193Kbit 9774pps backlog 0b 0p requeues 0
earlydrop 0 penaltydrop 0 bucketdrop 0 queuedrop 549245 childdrop 0 marked 0 maxqlen 0 maxprob 0.00000 avgprob 0.00000
--- tc/Makefile | 1 tc/q_sfb.c | 200 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 201 insertions(+)
tc/Makefile +1 -0
@@ -16,6 +16,7 @@ TCMODULES += q_rr.o TCMODULES += q_multiq.o TCMODULES += q_netem.o TCMODULES += q_choke.o +TCMODULES += q_sfb.o TCMODULES += f_rsvp.o TCMODULES += f_u32.o TCMODULES += f_route.o
tc/q_sfb.c new file +200 -0
200 lines not on this page · raw message
Re: [PATCH iproute2] tc : SFB flow scheduler
Quoted 15 lines · On Thu, 24 Mar 2011 18:44:09 +0100 Eric Dumazet <[email protected]> wrote:
From: Juliusz Chroboczek <[email protected]>
Supports SFB qdisc (included in linux-2.6.39)
1) Setup phase : accept non default parameters
2) dump information
qdisc sfb 11: parent 1:11 limit 1 max 25 target 20
increment 0.00050 decrement 0.00005 penalty rate 10 burst 20 (600000ms 60000ms)
Sent 47991616 bytes 521648 pkt (dropped 549245, overlimits 549245 requeues 0) rate 7193Kbit 9774pps backlog 0b 0p requeues 0
earlydrop 0 penaltydrop 0 bucketdrop 0 queuedrop 549245 childdrop 0 marked 0 maxqlen 0 maxprob 0.00000 avgprob 0.00000
Quoted 2 lines
Signed-off-by Juliusz Chroboczek <[email protected]>Signed-off-by Eric Dumazet <[email protected]>
Applied (to net-next branch)