blob: c65762823f5ee58f8992b494d741ba667c190fad [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * net/sched/sch_sfq.c Stochastic Fairness Queueing discipline.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version
7 * 2 of the License, or (at your option) any later version.
8 *
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
10 */
11
Linus Torvalds1da177e2005-04-16 15:20:36 -070012#include <linux/module.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070013#include <linux/types.h>
14#include <linux/kernel.h>
15#include <linux/jiffies.h>
16#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070017#include <linux/in.h>
18#include <linux/errno.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070019#include <linux/init.h>
Patrick McHardy0ba48052007-07-02 22:49:07 -070020#include <linux/ipv6.h>
21#include <linux/skbuff.h>
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -070022#include <linux/jhash.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090023#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070024#include <net/ip.h>
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -070025#include <net/netlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070026#include <net/pkt_sched.h>
27
28
29/* Stochastic Fairness Queuing algorithm.
30 =======================================
31
32 Source:
33 Paul E. McKenney "Stochastic Fairness Queuing",
34 IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
35
36 Paul E. McKenney "Stochastic Fairness Queuing",
37 "Interworking: Research and Experience", v.2, 1991, p.113-131.
38
39
40 See also:
41 M. Shreedhar and George Varghese "Efficient Fair
42 Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
43
44
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090045 This is not the thing that is usually called (W)FQ nowadays.
Linus Torvalds1da177e2005-04-16 15:20:36 -070046 It does not use any timestamp mechanism, but instead
47 processes queues in round-robin order.
48
49 ADVANTAGE:
50
51 - It is very cheap. Both CPU and memory requirements are minimal.
52
53 DRAWBACKS:
54
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090055 - "Stochastic" -> It is not 100% fair.
Linus Torvalds1da177e2005-04-16 15:20:36 -070056 When hash collisions occur, several flows are considered as one.
57
58 - "Round-robin" -> It introduces larger delays than virtual clock
59 based schemes, and should not be used for isolating interactive
60 traffic from non-interactive. It means, that this scheduler
61 should be used as leaf of CBQ or P3, which put interactive traffic
62 to higher priority band.
63
64 We still need true WFQ for top level CSZ, but using WFQ
65 for the best effort traffic is absolutely pointless:
66 SFQ is superior for this purpose.
67
68 IMPLEMENTATION:
69 This implementation limits maximal queue length to 128;
70 maximal mtu to 2^15-1; number of hash buckets to 1024.
71 The only goal of this restrictions was that all data
72 fit into one 4K page :-). Struct sfq_sched_data is
73 organized in anti-cache manner: all the data for a bucket
74 are scattered over different locations. This is not good,
75 but it allowed me to put it into 4K.
76
77 It is easy to increase these values, but not in flight. */
78
79#define SFQ_DEPTH 128
80#define SFQ_HASH_DIVISOR 1024
81
82/* This type should contain at least SFQ_DEPTH*2 values */
83typedef unsigned char sfq_index;
84
85struct sfq_head
86{
87 sfq_index next;
88 sfq_index prev;
89};
90
91struct sfq_sched_data
92{
93/* Parameters */
94 int perturb_period;
95 unsigned quantum; /* Allotment per round: MUST BE >= MTU */
96 int limit;
97
98/* Variables */
Patrick McHardy7d2681a2008-01-31 18:36:52 -080099 struct tcf_proto *filter_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700100 struct timer_list perturb_timer;
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700101 u32 perturbation;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700102 sfq_index tail; /* Index of current slot in round */
103 sfq_index max_depth; /* Maximal depth */
104
105 sfq_index ht[SFQ_HASH_DIVISOR]; /* Hash table */
106 sfq_index next[SFQ_DEPTH]; /* Active slots link */
107 short allot[SFQ_DEPTH]; /* Current allotment per slot */
108 unsigned short hash[SFQ_DEPTH]; /* Hash value indexed by slots */
109 struct sk_buff_head qs[SFQ_DEPTH]; /* Slot queue */
110 struct sfq_head dep[SFQ_DEPTH*2]; /* Linked list of slots, indexed by depth */
111};
112
113static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
114{
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700115 return jhash_2words(h, h1, q->perturbation) & (SFQ_HASH_DIVISOR - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116}
117
118static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
119{
120 u32 h, h2;
121
122 switch (skb->protocol) {
Arnaldo Carvalho de Melo60678042008-09-20 22:20:49 -0700123 case htons(ETH_P_IP):
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124 {
Arnaldo Carvalho de Meloeddc9ec2007-04-20 22:47:35 -0700125 const struct iphdr *iph = ip_hdr(skb);
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700126 h = (__force u32)iph->daddr;
127 h2 = (__force u32)iph->saddr ^ iph->protocol;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128 if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) &&
129 (iph->protocol == IPPROTO_TCP ||
130 iph->protocol == IPPROTO_UDP ||
Patrick McHardya8d0f952007-02-07 15:07:43 -0800131 iph->protocol == IPPROTO_UDPLITE ||
Patrick McHardyae82af52006-01-17 13:01:06 -0800132 iph->protocol == IPPROTO_SCTP ||
133 iph->protocol == IPPROTO_DCCP ||
Linus Torvalds1da177e2005-04-16 15:20:36 -0700134 iph->protocol == IPPROTO_ESP))
135 h2 ^= *(((u32*)iph) + iph->ihl);
136 break;
137 }
Arnaldo Carvalho de Melo60678042008-09-20 22:20:49 -0700138 case htons(ETH_P_IPV6):
Linus Torvalds1da177e2005-04-16 15:20:36 -0700139 {
Arnaldo Carvalho de Melo0660e032007-04-25 17:54:47 -0700140 struct ipv6hdr *iph = ipv6_hdr(skb);
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700141 h = (__force u32)iph->daddr.s6_addr32[3];
142 h2 = (__force u32)iph->saddr.s6_addr32[3] ^ iph->nexthdr;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143 if (iph->nexthdr == IPPROTO_TCP ||
144 iph->nexthdr == IPPROTO_UDP ||
Patrick McHardya8d0f952007-02-07 15:07:43 -0800145 iph->nexthdr == IPPROTO_UDPLITE ||
Patrick McHardyae82af52006-01-17 13:01:06 -0800146 iph->nexthdr == IPPROTO_SCTP ||
147 iph->nexthdr == IPPROTO_DCCP ||
Linus Torvalds1da177e2005-04-16 15:20:36 -0700148 iph->nexthdr == IPPROTO_ESP)
149 h2 ^= *(u32*)&iph[1];
150 break;
151 }
152 default:
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700153 h = (unsigned long)skb_dst(skb) ^ (__force u32)skb->protocol;
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800154 h2 = (unsigned long)skb->sk;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700155 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800156
Linus Torvalds1da177e2005-04-16 15:20:36 -0700157 return sfq_fold_hash(q, h, h2);
158}
159
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800160static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
161 int *qerr)
162{
163 struct sfq_sched_data *q = qdisc_priv(sch);
164 struct tcf_result res;
165 int result;
166
167 if (TC_H_MAJ(skb->priority) == sch->handle &&
168 TC_H_MIN(skb->priority) > 0 &&
169 TC_H_MIN(skb->priority) <= SFQ_HASH_DIVISOR)
170 return TC_H_MIN(skb->priority);
171
172 if (!q->filter_list)
173 return sfq_hash(q, skb) + 1;
174
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700175 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800176 result = tc_classify(skb, q->filter_list, &res);
177 if (result >= 0) {
178#ifdef CONFIG_NET_CLS_ACT
179 switch (result) {
180 case TC_ACT_STOLEN:
181 case TC_ACT_QUEUED:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700182 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800183 case TC_ACT_SHOT:
184 return 0;
185 }
186#endif
187 if (TC_H_MIN(res.classid) <= SFQ_HASH_DIVISOR)
188 return TC_H_MIN(res.classid);
189 }
190 return 0;
191}
192
Linus Torvalds1da177e2005-04-16 15:20:36 -0700193static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
194{
195 sfq_index p, n;
196 int d = q->qs[x].qlen + SFQ_DEPTH;
197
198 p = d;
199 n = q->dep[d].next;
200 q->dep[x].next = n;
201 q->dep[x].prev = p;
202 q->dep[p].next = q->dep[n].prev = x;
203}
204
205static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
206{
207 sfq_index p, n;
208
209 n = q->dep[x].next;
210 p = q->dep[x].prev;
211 q->dep[p].next = n;
212 q->dep[n].prev = p;
213
214 if (n == p && q->max_depth == q->qs[x].qlen + 1)
215 q->max_depth--;
216
217 sfq_link(q, x);
218}
219
220static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
221{
222 sfq_index p, n;
223 int d;
224
225 n = q->dep[x].next;
226 p = q->dep[x].prev;
227 q->dep[p].next = n;
228 q->dep[n].prev = p;
229 d = q->qs[x].qlen;
230 if (q->max_depth < d)
231 q->max_depth = d;
232
233 sfq_link(q, x);
234}
235
236static unsigned int sfq_drop(struct Qdisc *sch)
237{
238 struct sfq_sched_data *q = qdisc_priv(sch);
239 sfq_index d = q->max_depth;
240 struct sk_buff *skb;
241 unsigned int len;
242
243 /* Queue is full! Find the longest slot and
244 drop a packet from it */
245
246 if (d > 1) {
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800247 sfq_index x = q->dep[d + SFQ_DEPTH].next;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248 skb = q->qs[x].prev;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700249 len = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700250 __skb_unlink(skb, &q->qs[x]);
251 kfree_skb(skb);
252 sfq_dec(q, x);
253 sch->q.qlen--;
254 sch->qstats.drops++;
Patrick McHardyf5539eb2006-03-20 19:01:38 -0800255 sch->qstats.backlog -= len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 return len;
257 }
258
259 if (d == 1) {
260 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
261 d = q->next[q->tail];
262 q->next[q->tail] = q->next[d];
263 q->allot[q->next[d]] += q->quantum;
264 skb = q->qs[d].prev;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700265 len = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700266 __skb_unlink(skb, &q->qs[d]);
267 kfree_skb(skb);
268 sfq_dec(q, d);
269 sch->q.qlen--;
270 q->ht[q->hash[d]] = SFQ_DEPTH;
271 sch->qstats.drops++;
Patrick McHardyf5539eb2006-03-20 19:01:38 -0800272 sch->qstats.backlog -= len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273 return len;
274 }
275
276 return 0;
277}
278
279static int
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800280sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700281{
282 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800283 unsigned int hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700284 sfq_index x;
Jarek Poplawski7f3ff4f2008-12-21 20:14:48 -0800285 int uninitialized_var(ret);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800286
287 hash = sfq_classify(skb, sch, &ret);
288 if (hash == 0) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700289 if (ret & __NET_XMIT_BYPASS)
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800290 sch->qstats.drops++;
291 kfree_skb(skb);
292 return ret;
293 }
294 hash--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700295
296 x = q->ht[hash];
297 if (x == SFQ_DEPTH) {
298 q->ht[hash] = x = q->dep[SFQ_DEPTH].next;
299 q->hash[x] = hash;
300 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800301
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700302 /* If selected queue has length q->limit, this means that
303 * all another queues are empty and that we do simple tail drop,
304 * i.e. drop _this_ packet.
305 */
306 if (q->qs[x].qlen >= q->limit)
307 return qdisc_drop(skb, sch);
308
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700309 sch->qstats.backlog += qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700310 __skb_queue_tail(&q->qs[x], skb);
311 sfq_inc(q, x);
312 if (q->qs[x].qlen == 1) { /* The flow is new */
313 if (q->tail == SFQ_DEPTH) { /* It is the first flow */
314 q->tail = x;
315 q->next[x] = x;
316 q->allot[x] = q->quantum;
317 } else {
318 q->next[x] = q->next[q->tail];
319 q->next[q->tail] = x;
320 q->tail = x;
321 }
322 }
Alexey Kuznetsov5588b402007-09-19 10:42:03 -0700323 if (++sch->q.qlen <= q->limit) {
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700324 sch->bstats.bytes += qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700325 sch->bstats.packets++;
326 return 0;
327 }
328
329 sfq_drop(sch);
330 return NET_XMIT_CN;
331}
332
Patrick McHardy48a8f512008-10-31 00:44:18 -0700333static struct sk_buff *
334sfq_peek(struct Qdisc *sch)
335{
336 struct sfq_sched_data *q = qdisc_priv(sch);
337 sfq_index a;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700338
Patrick McHardy48a8f512008-10-31 00:44:18 -0700339 /* No active slots */
340 if (q->tail == SFQ_DEPTH)
341 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700342
Patrick McHardy48a8f512008-10-31 00:44:18 -0700343 a = q->next[q->tail];
344 return skb_peek(&q->qs[a]);
345}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700346
347static struct sk_buff *
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800348sfq_dequeue(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700349{
350 struct sfq_sched_data *q = qdisc_priv(sch);
351 struct sk_buff *skb;
352 sfq_index a, old_a;
353
354 /* No active slots */
355 if (q->tail == SFQ_DEPTH)
356 return NULL;
357
358 a = old_a = q->next[q->tail];
359
360 /* Grab packet */
361 skb = __skb_dequeue(&q->qs[a]);
362 sfq_dec(q, a);
363 sch->q.qlen--;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700364 sch->qstats.backlog -= qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700365
366 /* Is the slot empty? */
367 if (q->qs[a].qlen == 0) {
368 q->ht[q->hash[a]] = SFQ_DEPTH;
369 a = q->next[a];
370 if (a == old_a) {
371 q->tail = SFQ_DEPTH;
372 return skb;
373 }
374 q->next[q->tail] = a;
375 q->allot[a] += q->quantum;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700376 } else if ((q->allot[a] -= qdisc_pkt_len(skb)) <= 0) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700377 q->tail = a;
378 a = q->next[a];
379 q->allot[a] += q->quantum;
380 }
381 return skb;
382}
383
384static void
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800385sfq_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700386{
387 struct sk_buff *skb;
388
389 while ((skb = sfq_dequeue(sch)) != NULL)
390 kfree_skb(skb);
391}
392
393static void sfq_perturbation(unsigned long arg)
394{
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800395 struct Qdisc *sch = (struct Qdisc *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 struct sfq_sched_data *q = qdisc_priv(sch);
397
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800398 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700399
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700400 if (q->perturb_period)
401 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700402}
403
Patrick McHardy1e904742008-01-22 22:11:17 -0800404static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700405{
406 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800407 struct tc_sfq_qopt *ctl = nla_data(opt);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800408 unsigned int qlen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700409
Patrick McHardy1e904742008-01-22 22:11:17 -0800410 if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 return -EINVAL;
412
413 sch_tree_lock(sch);
David S. Miller5ce2d482008-07-08 17:06:30 -0700414 q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800415 q->perturb_period = ctl->perturb_period * HZ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416 if (ctl->limit)
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700417 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700418
Patrick McHardy5e50da02006-11-29 17:36:20 -0800419 qlen = sch->q.qlen;
Alexey Kuznetsov5588b402007-09-19 10:42:03 -0700420 while (sch->q.qlen > q->limit)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700421 sfq_drop(sch);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800422 qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700423
424 del_timer(&q->perturb_timer);
425 if (q->perturb_period) {
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700426 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800427 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700428 }
429 sch_tree_unlock(sch);
430 return 0;
431}
432
Patrick McHardy1e904742008-01-22 22:11:17 -0800433static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700434{
435 struct sfq_sched_data *q = qdisc_priv(sch);
436 int i;
437
Stephen Hemmingerd3e99482008-01-20 17:18:45 -0800438 q->perturb_timer.function = sfq_perturbation;
Fernando Carrijoc19a28e2009-01-07 18:09:08 -0800439 q->perturb_timer.data = (unsigned long)sch;
Stephen Hemmingerd3e99482008-01-20 17:18:45 -0800440 init_timer_deferrable(&q->perturb_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700441
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800442 for (i = 0; i < SFQ_HASH_DIVISOR; i++)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700443 q->ht[i] = SFQ_DEPTH;
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800444
445 for (i = 0; i < SFQ_DEPTH; i++) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700446 skb_queue_head_init(&q->qs[i]);
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800447 q->dep[i + SFQ_DEPTH].next = i + SFQ_DEPTH;
448 q->dep[i + SFQ_DEPTH].prev = i + SFQ_DEPTH;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800450
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700451 q->limit = SFQ_DEPTH - 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700452 q->max_depth = 0;
453 q->tail = SFQ_DEPTH;
454 if (opt == NULL) {
David S. Miller5ce2d482008-07-08 17:06:30 -0700455 q->quantum = psched_mtu(qdisc_dev(sch));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 q->perturb_period = 0;
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800457 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700458 } else {
459 int err = sfq_change(sch, opt);
460 if (err)
461 return err;
462 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800463
464 for (i = 0; i < SFQ_DEPTH; i++)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 sfq_link(q, i);
466 return 0;
467}
468
469static void sfq_destroy(struct Qdisc *sch)
470{
471 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800472
Patrick McHardyff31ab52008-07-01 19:52:38 -0700473 tcf_destroy_chain(&q->filter_list);
Jarek Poplawski980c4782008-04-29 03:29:03 -0700474 q->perturb_period = 0;
475 del_timer_sync(&q->perturb_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700476}
477
478static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
479{
480 struct sfq_sched_data *q = qdisc_priv(sch);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -0700481 unsigned char *b = skb_tail_pointer(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700482 struct tc_sfq_qopt opt;
483
484 opt.quantum = q->quantum;
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800485 opt.perturb_period = q->perturb_period / HZ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486
487 opt.limit = q->limit;
488 opt.divisor = SFQ_HASH_DIVISOR;
David S. Millercdec7e52008-07-26 02:28:09 -0700489 opt.flows = q->limit;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490
Patrick McHardy1e904742008-01-22 22:11:17 -0800491 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492
493 return skb->len;
494
Patrick McHardy1e904742008-01-22 22:11:17 -0800495nla_put_failure:
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -0700496 nlmsg_trim(skb, b);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700497 return -1;
498}
499
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800500static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
501{
502 return 0;
503}
504
505static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
506{
507 struct sfq_sched_data *q = qdisc_priv(sch);
508
509 if (cl)
510 return NULL;
511 return &q->filter_list;
512}
513
Patrick McHardy94de78d2008-01-31 18:37:16 -0800514static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
515 struct sk_buff *skb, struct tcmsg *tcm)
516{
517 tcm->tcm_handle |= TC_H_MIN(cl);
518 return 0;
519}
520
521static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
522 struct gnet_dump *d)
523{
524 struct sfq_sched_data *q = qdisc_priv(sch);
525 sfq_index idx = q->ht[cl-1];
526 struct gnet_stats_queue qs = { .qlen = q->qs[idx].qlen };
527 struct tc_sfq_xstats xstats = { .allot = q->allot[idx] };
528
529 if (gnet_stats_copy_queue(d, &qs) < 0)
530 return -1;
531 return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
532}
533
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800534static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
535{
Patrick McHardy94de78d2008-01-31 18:37:16 -0800536 struct sfq_sched_data *q = qdisc_priv(sch);
537 unsigned int i;
538
539 if (arg->stop)
540 return;
541
542 for (i = 0; i < SFQ_HASH_DIVISOR; i++) {
543 if (q->ht[i] == SFQ_DEPTH ||
544 arg->count < arg->skip) {
545 arg->count++;
546 continue;
547 }
548 if (arg->fn(sch, i + 1, arg) < 0) {
549 arg->stop = 1;
550 break;
551 }
552 arg->count++;
553 }
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800554}
555
556static const struct Qdisc_class_ops sfq_class_ops = {
557 .get = sfq_get,
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800558 .tcf_chain = sfq_find_tcf,
Patrick McHardy94de78d2008-01-31 18:37:16 -0800559 .dump = sfq_dump_class,
560 .dump_stats = sfq_dump_class_stats,
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800561 .walk = sfq_walk,
562};
563
Eric Dumazet20fea082007-11-14 01:44:41 -0800564static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800565 .cl_ops = &sfq_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 .id = "sfq",
567 .priv_size = sizeof(struct sfq_sched_data),
568 .enqueue = sfq_enqueue,
569 .dequeue = sfq_dequeue,
Patrick McHardy48a8f512008-10-31 00:44:18 -0700570 .peek = sfq_peek,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571 .drop = sfq_drop,
572 .init = sfq_init,
573 .reset = sfq_reset,
574 .destroy = sfq_destroy,
575 .change = NULL,
576 .dump = sfq_dump,
577 .owner = THIS_MODULE,
578};
579
580static int __init sfq_module_init(void)
581{
582 return register_qdisc(&sfq_qdisc_ops);
583}
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900584static void __exit sfq_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585{
586 unregister_qdisc(&sfq_qdisc_ops);
587}
588module_init(sfq_module_init)
589module_exit(sfq_module_exit)
590MODULE_LICENSE("GPL");