aboutsummaryrefslogtreecommitdiffstats
path: root/net/sched
diff options
context:
space:
mode:
authorAlexey Kuznetsov <kaber@ms2.inr.ac.ru>2007-09-30 20:51:33 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2007-10-02 00:01:23 -0400
commit32740ddc1095e5e320bf961dda146bf97bc28adb (patch)
tree613fccb815ed1c0a8e7712848a0ddea5d0d52b5e /net/sched
parent3146b39c185f8a436d430132457e84fa1d8f8208 (diff)
[SFQ]: Remove artificial limitation for queue limit.
This is followup to Patrick's patch. A little optimization to enqueue routine allows to remove artificial limitation on queue length. Plus, testing showed that hash function used by SFQ is too bad or even worse. It does not even sweep the whole range of hash values. Switched to Jenkins' hash. Signed-off-by: Alexey Kuznetsov <kaber@ms2.inr.ac.ru> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/sched')
-rw-r--r--net/sched/sch_sfq.c47
1 files changed, 31 insertions, 16 deletions
diff --git a/net/sched/sch_sfq.c b/net/sched/sch_sfq.c
index 3a23e30bc79e..b542c875e154 100644
--- a/net/sched/sch_sfq.c
+++ b/net/sched/sch_sfq.c
@@ -19,6 +19,7 @@
19#include <linux/init.h> 19#include <linux/init.h>
20#include <linux/ipv6.h> 20#include <linux/ipv6.h>
21#include <linux/skbuff.h> 21#include <linux/skbuff.h>
22#include <linux/jhash.h>
22#include <net/ip.h> 23#include <net/ip.h>
23#include <net/netlink.h> 24#include <net/netlink.h>
24#include <net/pkt_sched.h> 25#include <net/pkt_sched.h>
@@ -95,7 +96,7 @@ struct sfq_sched_data
95 96
96/* Variables */ 97/* Variables */
97 struct timer_list perturb_timer; 98 struct timer_list perturb_timer;
98 int perturbation; 99 u32 perturbation;
99 sfq_index tail; /* Index of current slot in round */ 100 sfq_index tail; /* Index of current slot in round */
100 sfq_index max_depth; /* Maximal depth */ 101 sfq_index max_depth; /* Maximal depth */
101 102
@@ -109,12 +110,7 @@ struct sfq_sched_data
109 110
110static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1) 111static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
111{ 112{
112 int pert = q->perturbation; 113 return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
113
114 /* Have we any rotation primitives? If not, WHY? */
115 h ^= (h1<<pert) ^ (h1>>(0x1F - pert));
116 h ^= h>>10;
117 return h & 0x3FF;
118} 114}
119 115
120static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb) 116static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
@@ -256,6 +252,13 @@ sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch)
256 q->ht[hash] = x = q->dep[SFQ_DEPTH].next; 252 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
257 q->hash[x] = hash; 253 q->hash[x] = hash;
258 } 254 }
255 /* If selected queue has length q->limit, this means that
256 * all another queues are empty and that we do simple tail drop,
257 * i.e. drop _this_ packet.
258 */
259 if (q->qs[x].qlen >= q->limit)
260 return qdisc_drop(skb, sch);
261
259 sch->qstats.backlog += skb->len; 262 sch->qstats.backlog += skb->len;
260 __skb_queue_tail(&q->qs[x], skb); 263 __skb_queue_tail(&q->qs[x], skb);
261 sfq_inc(q, x); 264 sfq_inc(q, x);
@@ -294,6 +297,19 @@ sfq_requeue(struct sk_buff *skb, struct Qdisc* sch)
294 } 297 }
295 sch->qstats.backlog += skb->len; 298 sch->qstats.backlog += skb->len;
296 __skb_queue_head(&q->qs[x], skb); 299 __skb_queue_head(&q->qs[x], skb);
300 /* If selected queue has length q->limit+1, this means that
301 * all another queues are empty and we do simple tail drop.
302 * This packet is still requeued at head of queue, tail packet
303 * is dropped.
304 */
305 if (q->qs[x].qlen > q->limit) {
306 skb = q->qs[x].prev;
307 __skb_unlink(skb, &q->qs[x]);
308 sch->qstats.drops++;
309 sch->qstats.backlog -= skb->len;
310 kfree_skb(skb);
311 return NET_XMIT_CN;
312 }
297 sfq_inc(q, x); 313 sfq_inc(q, x);
298 if (q->qs[x].qlen == 1) { /* The flow is new */ 314 if (q->qs[x].qlen == 1) { /* The flow is new */
299 if (q->tail == SFQ_DEPTH) { /* It is the first flow */ 315 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
@@ -370,12 +386,10 @@ static void sfq_perturbation(unsigned long arg)
370 struct Qdisc *sch = (struct Qdisc*)arg; 386 struct Qdisc *sch = (struct Qdisc*)arg;
371 struct sfq_sched_data *q = qdisc_priv(sch); 387 struct sfq_sched_data *q = qdisc_priv(sch);
372 388
373 q->perturbation = net_random()&0x1F; 389 get_random_bytes(&q->perturbation, 4);
374 390
375 if (q->perturb_period) { 391 if (q->perturb_period)
376 q->perturb_timer.expires = jiffies + q->perturb_period; 392 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
377 add_timer(&q->perturb_timer);
378 }
379} 393}
380 394
381static int sfq_change(struct Qdisc *sch, struct rtattr *opt) 395static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
@@ -391,7 +405,7 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
391 q->quantum = ctl->quantum ? : psched_mtu(sch->dev); 405 q->quantum = ctl->quantum ? : psched_mtu(sch->dev);
392 q->perturb_period = ctl->perturb_period*HZ; 406 q->perturb_period = ctl->perturb_period*HZ;
393 if (ctl->limit) 407 if (ctl->limit)
394 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 2); 408 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
395 409
396 qlen = sch->q.qlen; 410 qlen = sch->q.qlen;
397 while (sch->q.qlen > q->limit) 411 while (sch->q.qlen > q->limit)
@@ -400,8 +414,8 @@ static int sfq_change(struct Qdisc *sch, struct rtattr *opt)
400 414
401 del_timer(&q->perturb_timer); 415 del_timer(&q->perturb_timer);
402 if (q->perturb_period) { 416 if (q->perturb_period) {
403 q->perturb_timer.expires = jiffies + q->perturb_period; 417 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
404 add_timer(&q->perturb_timer); 418 get_random_bytes(&q->perturbation, 4);
405 } 419 }
406 sch_tree_unlock(sch); 420 sch_tree_unlock(sch);
407 return 0; 421 return 0;
@@ -423,12 +437,13 @@ static int sfq_init(struct Qdisc *sch, struct rtattr *opt)
423 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH; 437 q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH;
424 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH; 438 q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH;
425 } 439 }
426 q->limit = SFQ_DEPTH - 2; 440 q->limit = SFQ_DEPTH - 1;
427 q->max_depth = 0; 441 q->max_depth = 0;
428 q->tail = SFQ_DEPTH; 442 q->tail = SFQ_DEPTH;
429 if (opt == NULL) { 443 if (opt == NULL) {
430 q->quantum = psched_mtu(sch->dev); 444 q->quantum = psched_mtu(sch->dev);
431 q->perturb_period = 0; 445 q->perturb_period = 0;
446 get_random_bytes(&q->perturbation, 4);
432 } else { 447 } else {
433 int err = sfq_change(sch, opt); 448 int err = sfq_change(sch, opt);
434 if (err) 449 if (err)