blob: c2e628dfaaccb0f2dacffa9bbc5dec34bbb5f291 [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>
Eric Dumazet817fb152011-01-20 00:14:58 +000024#include <linux/vmalloc.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070025#include <net/ip.h>
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -070026#include <net/netlink.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070027#include <net/pkt_sched.h>
28
29
30/* Stochastic Fairness Queuing algorithm.
31 =======================================
32
33 Source:
34 Paul E. McKenney "Stochastic Fairness Queuing",
35 IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
36
37 Paul E. McKenney "Stochastic Fairness Queuing",
38 "Interworking: Research and Experience", v.2, 1991, p.113-131.
39
40
41 See also:
42 M. Shreedhar and George Varghese "Efficient Fair
43 Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
44
45
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090046 This is not the thing that is usually called (W)FQ nowadays.
Linus Torvalds1da177e2005-04-16 15:20:36 -070047 It does not use any timestamp mechanism, but instead
48 processes queues in round-robin order.
49
50 ADVANTAGE:
51
52 - It is very cheap. Both CPU and memory requirements are minimal.
53
54 DRAWBACKS:
55
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +090056 - "Stochastic" -> It is not 100% fair.
Linus Torvalds1da177e2005-04-16 15:20:36 -070057 When hash collisions occur, several flows are considered as one.
58
59 - "Round-robin" -> It introduces larger delays than virtual clock
60 based schemes, and should not be used for isolating interactive
61 traffic from non-interactive. It means, that this scheduler
62 should be used as leaf of CBQ or P3, which put interactive traffic
63 to higher priority band.
64
65 We still need true WFQ for top level CSZ, but using WFQ
66 for the best effort traffic is absolutely pointless:
67 SFQ is superior for this purpose.
68
69 IMPLEMENTATION:
70 This implementation limits maximal queue length to 128;
Eric Dumazeteeaeb062010-12-28 21:53:33 +000071 max mtu to 2^18-1; max 128 flows, number of hash buckets to 1024.
Linus Torvalds1da177e2005-04-16 15:20:36 -070072 The only goal of this restrictions was that all data
Eric Dumazeteda83e32010-12-20 12:54:58 +000073 fit into one 4K page on 32bit arches.
Linus Torvalds1da177e2005-04-16 15:20:36 -070074
75 It is easy to increase these values, but not in flight. */
76
Eric Dumazeteda83e32010-12-20 12:54:58 +000077#define SFQ_DEPTH 128 /* max number of packets per flow */
78#define SFQ_SLOTS 128 /* max number of flows */
79#define SFQ_EMPTY_SLOT 255
Eric Dumazet817fb152011-01-20 00:14:58 +000080#define SFQ_DEFAULT_HASH_DIVISOR 1024
81
Eric Dumazeteeaeb062010-12-28 21:53:33 +000082/* We use 16 bits to store allot, and want to handle packets up to 64K
83 * Scale allot by 8 (1<<3) so that no overflow occurs.
84 */
85#define SFQ_ALLOT_SHIFT 3
86#define SFQ_ALLOT_SIZE(X) DIV_ROUND_UP(X, 1 << SFQ_ALLOT_SHIFT)
Linus Torvalds1da177e2005-04-16 15:20:36 -070087
Eric Dumazeteda83e32010-12-20 12:54:58 +000088/* This type should contain at least SFQ_DEPTH + SFQ_SLOTS values */
Linus Torvalds1da177e2005-04-16 15:20:36 -070089typedef unsigned char sfq_index;
90
Eric Dumazeteda83e32010-12-20 12:54:58 +000091/*
92 * We dont use pointers to save space.
93 * Small indexes [0 ... SFQ_SLOTS - 1] are 'pointers' to slots[] array
94 * while following values [SFQ_SLOTS ... SFQ_SLOTS + SFQ_DEPTH - 1]
95 * are 'pointers' to dep[] array
96 */
Eric Dumazetcc7ec452011-01-19 19:26:56 +000097struct sfq_head {
Linus Torvalds1da177e2005-04-16 15:20:36 -070098 sfq_index next;
99 sfq_index prev;
100};
101
Eric Dumazeteda83e32010-12-20 12:54:58 +0000102struct sfq_slot {
103 struct sk_buff *skblist_next;
104 struct sk_buff *skblist_prev;
105 sfq_index qlen; /* number of skbs in skblist */
106 sfq_index next; /* next slot in sfq chain */
107 struct sfq_head dep; /* anchor in dep[] chains */
108 unsigned short hash; /* hash value (index in ht[]) */
109 short allot; /* credit for this slot */
110};
111
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000112struct sfq_sched_data {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700113/* Parameters */
114 int perturb_period;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000115 unsigned int quantum; /* Allotment per round: MUST BE >= MTU */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700116 int limit;
Eric Dumazet817fb152011-01-20 00:14:58 +0000117 unsigned int divisor; /* number of slots in hash table */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700118/* Variables */
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800119 struct tcf_proto *filter_list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700120 struct timer_list perturb_timer;
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700121 u32 perturbation;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000122 sfq_index cur_depth; /* depth of longest slot */
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000123 unsigned short scaled_quantum; /* SFQ_ALLOT_SIZE(quantum) */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000124 struct sfq_slot *tail; /* current slot in round */
Eric Dumazet817fb152011-01-20 00:14:58 +0000125 sfq_index *ht; /* Hash table (divisor slots) */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000126 struct sfq_slot slots[SFQ_SLOTS];
127 struct sfq_head dep[SFQ_DEPTH]; /* Linked list of slots, indexed by depth */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700128};
129
Eric Dumazeteda83e32010-12-20 12:54:58 +0000130/*
131 * sfq_head are either in a sfq_slot or in dep[] array
132 */
133static inline struct sfq_head *sfq_dep_head(struct sfq_sched_data *q, sfq_index val)
134{
135 if (val < SFQ_SLOTS)
136 return &q->slots[val].dep;
137 return &q->dep[val - SFQ_SLOTS];
138}
139
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000140static unsigned int sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700141{
Eric Dumazet817fb152011-01-20 00:14:58 +0000142 return jhash_2words(h, h1, q->perturbation) & (q->divisor - 1);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700143}
144
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000145static unsigned int sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700146{
147 u32 h, h2;
148
149 switch (skb->protocol) {
Arnaldo Carvalho de Melo60678042008-09-20 22:20:49 -0700150 case htons(ETH_P_IP):
Linus Torvalds1da177e2005-04-16 15:20:36 -0700151 {
Changli Gaof2f00982010-08-04 04:58:59 +0000152 const struct iphdr *iph;
Changli Gaob9959c22010-08-17 19:07:35 +0000153 int poff;
Changli Gaof2f00982010-08-04 04:58:59 +0000154
155 if (!pskb_network_may_pull(skb, sizeof(*iph)))
156 goto err;
157 iph = ip_hdr(skb);
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700158 h = (__force u32)iph->daddr;
159 h2 = (__force u32)iph->saddr ^ iph->protocol;
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000160 if (iph->frag_off & htons(IP_MF | IP_OFFSET))
Changli Gaob9959c22010-08-17 19:07:35 +0000161 break;
162 poff = proto_ports_offset(iph->protocol);
163 if (poff >= 0 &&
164 pskb_network_may_pull(skb, iph->ihl * 4 + 4 + poff)) {
165 iph = ip_hdr(skb);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000166 h2 ^= *(u32 *)((void *)iph + iph->ihl * 4 + poff);
Changli Gaob9959c22010-08-17 19:07:35 +0000167 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700168 break;
169 }
Arnaldo Carvalho de Melo60678042008-09-20 22:20:49 -0700170 case htons(ETH_P_IPV6):
Linus Torvalds1da177e2005-04-16 15:20:36 -0700171 {
Changli Gaof2f00982010-08-04 04:58:59 +0000172 struct ipv6hdr *iph;
Changli Gaob9959c22010-08-17 19:07:35 +0000173 int poff;
Changli Gaof2f00982010-08-04 04:58:59 +0000174
175 if (!pskb_network_may_pull(skb, sizeof(*iph)))
176 goto err;
177 iph = ipv6_hdr(skb);
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700178 h = (__force u32)iph->daddr.s6_addr32[3];
179 h2 = (__force u32)iph->saddr.s6_addr32[3] ^ iph->nexthdr;
Changli Gaob9959c22010-08-17 19:07:35 +0000180 poff = proto_ports_offset(iph->nexthdr);
181 if (poff >= 0 &&
182 pskb_network_may_pull(skb, sizeof(*iph) + 4 + poff)) {
183 iph = ipv6_hdr(skb);
Eric Dumazetcc7ec452011-01-19 19:26:56 +0000184 h2 ^= *(u32 *)((void *)iph + sizeof(*iph) + poff);
Changli Gaob9959c22010-08-17 19:07:35 +0000185 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700186 break;
187 }
188 default:
Changli Gaof2f00982010-08-04 04:58:59 +0000189err:
Eric Dumazet0eae88f2010-04-20 19:06:52 -0700190 h = (unsigned long)skb_dst(skb) ^ (__force u32)skb->protocol;
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800191 h2 = (unsigned long)skb->sk;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700192 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800193
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194 return sfq_fold_hash(q, h, h2);
195}
196
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800197static unsigned int sfq_classify(struct sk_buff *skb, struct Qdisc *sch,
198 int *qerr)
199{
200 struct sfq_sched_data *q = qdisc_priv(sch);
201 struct tcf_result res;
202 int result;
203
204 if (TC_H_MAJ(skb->priority) == sch->handle &&
205 TC_H_MIN(skb->priority) > 0 &&
Eric Dumazet817fb152011-01-20 00:14:58 +0000206 TC_H_MIN(skb->priority) <= q->divisor)
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800207 return TC_H_MIN(skb->priority);
208
209 if (!q->filter_list)
210 return sfq_hash(q, skb) + 1;
211
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700212 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800213 result = tc_classify(skb, q->filter_list, &res);
214 if (result >= 0) {
215#ifdef CONFIG_NET_CLS_ACT
216 switch (result) {
217 case TC_ACT_STOLEN:
218 case TC_ACT_QUEUED:
Jarek Poplawski378a2f02008-08-04 22:31:03 -0700219 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800220 case TC_ACT_SHOT:
221 return 0;
222 }
223#endif
Eric Dumazet817fb152011-01-20 00:14:58 +0000224 if (TC_H_MIN(res.classid) <= q->divisor)
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800225 return TC_H_MIN(res.classid);
226 }
227 return 0;
228}
229
Eric Dumazeteda83e32010-12-20 12:54:58 +0000230/*
231 * x : slot number [0 .. SFQ_SLOTS - 1]
232 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700233static inline void sfq_link(struct sfq_sched_data *q, sfq_index x)
234{
235 sfq_index p, n;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000236 int qlen = q->slots[x].qlen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700237
Eric Dumazeteda83e32010-12-20 12:54:58 +0000238 p = qlen + SFQ_SLOTS;
239 n = q->dep[qlen].next;
240
241 q->slots[x].dep.next = n;
242 q->slots[x].dep.prev = p;
243
244 q->dep[qlen].next = x; /* sfq_dep_head(q, p)->next = x */
245 sfq_dep_head(q, n)->prev = x;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700246}
247
Eric Dumazeteda83e32010-12-20 12:54:58 +0000248#define sfq_unlink(q, x, n, p) \
249 n = q->slots[x].dep.next; \
250 p = q->slots[x].dep.prev; \
251 sfq_dep_head(q, p)->next = n; \
252 sfq_dep_head(q, n)->prev = p
253
254
Linus Torvalds1da177e2005-04-16 15:20:36 -0700255static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x)
256{
257 sfq_index p, n;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000258 int d;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700259
Eric Dumazeteda83e32010-12-20 12:54:58 +0000260 sfq_unlink(q, x, n, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261
Eric Dumazeteda83e32010-12-20 12:54:58 +0000262 d = q->slots[x].qlen--;
263 if (n == p && q->cur_depth == d)
264 q->cur_depth--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700265 sfq_link(q, x);
266}
267
268static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x)
269{
270 sfq_index p, n;
271 int d;
272
Eric Dumazeteda83e32010-12-20 12:54:58 +0000273 sfq_unlink(q, x, n, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700274
Eric Dumazeteda83e32010-12-20 12:54:58 +0000275 d = ++q->slots[x].qlen;
276 if (q->cur_depth < d)
277 q->cur_depth = d;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278 sfq_link(q, x);
279}
280
Eric Dumazeteda83e32010-12-20 12:54:58 +0000281/* helper functions : might be changed when/if skb use a standard list_head */
282
283/* remove one skb from tail of slot queue */
284static inline struct sk_buff *slot_dequeue_tail(struct sfq_slot *slot)
285{
286 struct sk_buff *skb = slot->skblist_prev;
287
288 slot->skblist_prev = skb->prev;
Eric Dumazetee09b3c2010-12-22 11:39:59 -0800289 skb->prev->next = (struct sk_buff *)slot;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000290 skb->next = skb->prev = NULL;
291 return skb;
292}
293
294/* remove one skb from head of slot queue */
295static inline struct sk_buff *slot_dequeue_head(struct sfq_slot *slot)
296{
297 struct sk_buff *skb = slot->skblist_next;
298
299 slot->skblist_next = skb->next;
Eric Dumazet18c8d822010-12-31 12:48:55 -0800300 skb->next->prev = (struct sk_buff *)slot;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000301 skb->next = skb->prev = NULL;
302 return skb;
303}
304
305static inline void slot_queue_init(struct sfq_slot *slot)
306{
307 slot->skblist_prev = slot->skblist_next = (struct sk_buff *)slot;
308}
309
310/* add skb to slot queue (tail add) */
311static inline void slot_queue_add(struct sfq_slot *slot, struct sk_buff *skb)
312{
313 skb->prev = slot->skblist_prev;
314 skb->next = (struct sk_buff *)slot;
315 slot->skblist_prev->next = skb;
316 slot->skblist_prev = skb;
317}
318
319#define slot_queue_walk(slot, skb) \
320 for (skb = slot->skblist_next; \
321 skb != (struct sk_buff *)slot; \
322 skb = skb->next)
323
Linus Torvalds1da177e2005-04-16 15:20:36 -0700324static unsigned int sfq_drop(struct Qdisc *sch)
325{
326 struct sfq_sched_data *q = qdisc_priv(sch);
Eric Dumazeteda83e32010-12-20 12:54:58 +0000327 sfq_index x, d = q->cur_depth;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700328 struct sk_buff *skb;
329 unsigned int len;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000330 struct sfq_slot *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700331
Eric Dumazeteda83e32010-12-20 12:54:58 +0000332 /* Queue is full! Find the longest slot and drop tail packet from it */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333 if (d > 1) {
Eric Dumazeteda83e32010-12-20 12:54:58 +0000334 x = q->dep[d].next;
335 slot = &q->slots[x];
336drop:
337 skb = slot_dequeue_tail(slot);
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700338 len = qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700339 sfq_dec(q, x);
Eric Dumazeteda83e32010-12-20 12:54:58 +0000340 kfree_skb(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700341 sch->q.qlen--;
342 sch->qstats.drops++;
Patrick McHardyf5539eb2006-03-20 19:01:38 -0800343 sch->qstats.backlog -= len;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 return len;
345 }
346
347 if (d == 1) {
348 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000349 x = q->tail->next;
350 slot = &q->slots[x];
351 q->tail->next = slot->next;
352 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
353 goto drop;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354 }
355
356 return 0;
357}
358
359static int
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800360sfq_enqueue(struct sk_buff *skb, struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700361{
362 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800363 unsigned int hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700364 sfq_index x;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000365 struct sfq_slot *slot;
Jarek Poplawski7f3ff4f2008-12-21 20:14:48 -0800366 int uninitialized_var(ret);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800367
368 hash = sfq_classify(skb, sch, &ret);
369 if (hash == 0) {
Jarek Poplawskic27f3392008-08-04 22:39:11 -0700370 if (ret & __NET_XMIT_BYPASS)
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800371 sch->qstats.drops++;
372 kfree_skb(skb);
373 return ret;
374 }
375 hash--;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700376
377 x = q->ht[hash];
Eric Dumazeteda83e32010-12-20 12:54:58 +0000378 slot = &q->slots[x];
379 if (x == SFQ_EMPTY_SLOT) {
380 x = q->dep[0].next; /* get a free slot */
381 q->ht[hash] = x;
382 slot = &q->slots[x];
383 slot->hash = hash;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800385
Eric Dumazeteda83e32010-12-20 12:54:58 +0000386 /* If selected queue has length q->limit, do simple tail drop,
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700387 * i.e. drop _this_ packet.
388 */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000389 if (slot->qlen >= q->limit)
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700390 return qdisc_drop(skb, sch);
391
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700392 sch->qstats.backlog += qdisc_pkt_len(skb);
Eric Dumazeteda83e32010-12-20 12:54:58 +0000393 slot_queue_add(slot, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394 sfq_inc(q, x);
Eric Dumazeteda83e32010-12-20 12:54:58 +0000395 if (slot->qlen == 1) { /* The flow is new */
396 if (q->tail == NULL) { /* It is the first flow */
397 slot->next = x;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700398 } else {
Eric Dumazeteda83e32010-12-20 12:54:58 +0000399 slot->next = q->tail->next;
400 q->tail->next = x;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700401 }
Eric Dumazeteda83e32010-12-20 12:54:58 +0000402 q->tail = slot;
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000403 slot->allot = q->scaled_quantum;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700404 }
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800405 if (++sch->q.qlen <= q->limit)
Ben Greear9871e502010-08-10 01:45:40 -0700406 return NET_XMIT_SUCCESS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700407
408 sfq_drop(sch);
409 return NET_XMIT_CN;
410}
411
Patrick McHardy48a8f512008-10-31 00:44:18 -0700412static struct sk_buff *
413sfq_peek(struct Qdisc *sch)
414{
415 struct sfq_sched_data *q = qdisc_priv(sch);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700416
Patrick McHardy48a8f512008-10-31 00:44:18 -0700417 /* No active slots */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000418 if (q->tail == NULL)
Patrick McHardy48a8f512008-10-31 00:44:18 -0700419 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700420
Eric Dumazeteda83e32010-12-20 12:54:58 +0000421 return q->slots[q->tail->next].skblist_next;
Patrick McHardy48a8f512008-10-31 00:44:18 -0700422}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700423
424static struct sk_buff *
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800425sfq_dequeue(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700426{
427 struct sfq_sched_data *q = qdisc_priv(sch);
428 struct sk_buff *skb;
Eric Dumazetaa3e2192010-12-20 13:18:16 -0800429 sfq_index a, next_a;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000430 struct sfq_slot *slot;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431
432 /* No active slots */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000433 if (q->tail == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700434 return NULL;
435
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000436next_slot:
Eric Dumazeteda83e32010-12-20 12:54:58 +0000437 a = q->tail->next;
438 slot = &q->slots[a];
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000439 if (slot->allot <= 0) {
440 q->tail = slot;
441 slot->allot += q->scaled_quantum;
442 goto next_slot;
443 }
Eric Dumazeteda83e32010-12-20 12:54:58 +0000444 skb = slot_dequeue_head(slot);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700445 sfq_dec(q, a);
Eric Dumazet9190b3b2011-01-20 23:31:33 -0800446 qdisc_bstats_update(sch, skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700447 sch->q.qlen--;
Jussi Kivilinna0abf77e2008-07-20 00:08:27 -0700448 sch->qstats.backlog -= qdisc_pkt_len(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700449
450 /* Is the slot empty? */
Eric Dumazeteda83e32010-12-20 12:54:58 +0000451 if (slot->qlen == 0) {
452 q->ht[slot->hash] = SFQ_EMPTY_SLOT;
453 next_a = slot->next;
Eric Dumazetaa3e2192010-12-20 13:18:16 -0800454 if (a == next_a) {
Eric Dumazeteda83e32010-12-20 12:54:58 +0000455 q->tail = NULL; /* no more active slots */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700456 return skb;
457 }
Eric Dumazeteda83e32010-12-20 12:54:58 +0000458 q->tail->next = next_a;
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000459 } else {
460 slot->allot -= SFQ_ALLOT_SIZE(qdisc_pkt_len(skb));
Linus Torvalds1da177e2005-04-16 15:20:36 -0700461 }
462 return skb;
463}
464
465static void
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800466sfq_reset(struct Qdisc *sch)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467{
468 struct sk_buff *skb;
469
470 while ((skb = sfq_dequeue(sch)) != NULL)
471 kfree_skb(skb);
472}
473
474static void sfq_perturbation(unsigned long arg)
475{
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800476 struct Qdisc *sch = (struct Qdisc *)arg;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700477 struct sfq_sched_data *q = qdisc_priv(sch);
478
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800479 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700480
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700481 if (q->perturb_period)
482 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483}
484
Patrick McHardy1e904742008-01-22 22:11:17 -0800485static int sfq_change(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700486{
487 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy1e904742008-01-22 22:11:17 -0800488 struct tc_sfq_qopt *ctl = nla_data(opt);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800489 unsigned int qlen;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700490
Patrick McHardy1e904742008-01-22 22:11:17 -0800491 if (opt->nla_len < nla_attr_size(sizeof(*ctl)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 return -EINVAL;
493
stephen hemminger119b3d32011-02-02 15:19:51 +0000494 if (ctl->divisor &&
495 (!is_power_of_2(ctl->divisor) || ctl->divisor > 65536))
496 return -EINVAL;
497
Linus Torvalds1da177e2005-04-16 15:20:36 -0700498 sch_tree_lock(sch);
David S. Miller5ce2d482008-07-08 17:06:30 -0700499 q->quantum = ctl->quantum ? : psched_mtu(qdisc_dev(sch));
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000500 q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800501 q->perturb_period = ctl->perturb_period * HZ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700502 if (ctl->limit)
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700503 q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 1);
stephen hemminger119b3d32011-02-02 15:19:51 +0000504 if (ctl->divisor)
Eric Dumazet817fb152011-01-20 00:14:58 +0000505 q->divisor = ctl->divisor;
Patrick McHardy5e50da02006-11-29 17:36:20 -0800506 qlen = sch->q.qlen;
Alexey Kuznetsov5588b402007-09-19 10:42:03 -0700507 while (sch->q.qlen > q->limit)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700508 sfq_drop(sch);
Patrick McHardy5e50da02006-11-29 17:36:20 -0800509 qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700510
511 del_timer(&q->perturb_timer);
512 if (q->perturb_period) {
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700513 mod_timer(&q->perturb_timer, jiffies + q->perturb_period);
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800514 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700515 }
516 sch_tree_unlock(sch);
517 return 0;
518}
519
Patrick McHardy1e904742008-01-22 22:11:17 -0800520static int sfq_init(struct Qdisc *sch, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700521{
522 struct sfq_sched_data *q = qdisc_priv(sch);
Eric Dumazet817fb152011-01-20 00:14:58 +0000523 size_t sz;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700524 int i;
525
Stephen Hemmingerd3e99482008-01-20 17:18:45 -0800526 q->perturb_timer.function = sfq_perturbation;
Fernando Carrijoc19a28e2009-01-07 18:09:08 -0800527 q->perturb_timer.data = (unsigned long)sch;
Stephen Hemmingerd3e99482008-01-20 17:18:45 -0800528 init_timer_deferrable(&q->perturb_timer);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800530 for (i = 0; i < SFQ_DEPTH; i++) {
Eric Dumazeteda83e32010-12-20 12:54:58 +0000531 q->dep[i].next = i + SFQ_SLOTS;
532 q->dep[i].prev = i + SFQ_SLOTS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700533 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800534
Alexey Kuznetsov32740dd2007-09-30 17:51:33 -0700535 q->limit = SFQ_DEPTH - 1;
Eric Dumazeteda83e32010-12-20 12:54:58 +0000536 q->cur_depth = 0;
537 q->tail = NULL;
Eric Dumazet817fb152011-01-20 00:14:58 +0000538 q->divisor = SFQ_DEFAULT_HASH_DIVISOR;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700539 if (opt == NULL) {
David S. Miller5ce2d482008-07-08 17:06:30 -0700540 q->quantum = psched_mtu(qdisc_dev(sch));
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000541 q->scaled_quantum = SFQ_ALLOT_SIZE(q->quantum);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700542 q->perturb_period = 0;
Stephen Hemmingerd46f8dd2008-01-20 17:19:43 -0800543 q->perturbation = net_random();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700544 } else {
545 int err = sfq_change(sch, opt);
546 if (err)
547 return err;
548 }
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800549
Eric Dumazet817fb152011-01-20 00:14:58 +0000550 sz = sizeof(q->ht[0]) * q->divisor;
551 q->ht = kmalloc(sz, GFP_KERNEL);
552 if (!q->ht && sz > PAGE_SIZE)
553 q->ht = vmalloc(sz);
554 if (!q->ht)
555 return -ENOMEM;
556 for (i = 0; i < q->divisor; i++)
557 q->ht[i] = SFQ_EMPTY_SLOT;
558
Eric Dumazet18c8d822010-12-31 12:48:55 -0800559 for (i = 0; i < SFQ_SLOTS; i++) {
560 slot_queue_init(&q->slots[i]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700561 sfq_link(q, i);
Eric Dumazet18c8d822010-12-31 12:48:55 -0800562 }
Eric Dumazet23624932011-01-21 16:26:09 -0800563 if (q->limit >= 1)
564 sch->flags |= TCQ_F_CAN_BYPASS;
565 else
566 sch->flags &= ~TCQ_F_CAN_BYPASS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700567 return 0;
568}
569
570static void sfq_destroy(struct Qdisc *sch)
571{
572 struct sfq_sched_data *q = qdisc_priv(sch);
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800573
Patrick McHardyff31ab52008-07-01 19:52:38 -0700574 tcf_destroy_chain(&q->filter_list);
Jarek Poplawski980c4782008-04-29 03:29:03 -0700575 q->perturb_period = 0;
576 del_timer_sync(&q->perturb_timer);
Eric Dumazet817fb152011-01-20 00:14:58 +0000577 if (is_vmalloc_addr(q->ht))
578 vfree(q->ht);
579 else
580 kfree(q->ht);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700581}
582
583static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb)
584{
585 struct sfq_sched_data *q = qdisc_priv(sch);
Arnaldo Carvalho de Melo27a884d2007-04-19 20:29:13 -0700586 unsigned char *b = skb_tail_pointer(skb);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587 struct tc_sfq_qopt opt;
588
589 opt.quantum = q->quantum;
Stephen Hemminger6f9e98f2008-01-20 17:20:56 -0800590 opt.perturb_period = q->perturb_period / HZ;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591
592 opt.limit = q->limit;
Eric Dumazet817fb152011-01-20 00:14:58 +0000593 opt.divisor = q->divisor;
David S. Millercdec7e52008-07-26 02:28:09 -0700594 opt.flows = q->limit;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700595
Patrick McHardy1e904742008-01-22 22:11:17 -0800596 NLA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700597
598 return skb->len;
599
Patrick McHardy1e904742008-01-22 22:11:17 -0800600nla_put_failure:
Arnaldo Carvalho de Melodc5fc572007-03-25 23:06:12 -0700601 nlmsg_trim(skb, b);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602 return -1;
603}
604
Jarek Poplawski41065fb2010-08-10 22:31:02 +0000605static struct Qdisc *sfq_leaf(struct Qdisc *sch, unsigned long arg)
606{
607 return NULL;
608}
609
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800610static unsigned long sfq_get(struct Qdisc *sch, u32 classid)
611{
612 return 0;
613}
614
Jarek Poplawskieb4a5522010-08-06 00:22:35 +0000615static unsigned long sfq_bind(struct Qdisc *sch, unsigned long parent,
616 u32 classid)
617{
Eric Dumazet23624932011-01-21 16:26:09 -0800618 /* we cannot bypass queue discipline anymore */
619 sch->flags &= ~TCQ_F_CAN_BYPASS;
Jarek Poplawskieb4a5522010-08-06 00:22:35 +0000620 return 0;
621}
622
Jarek Poplawskida7115d2010-08-09 12:18:17 +0000623static void sfq_put(struct Qdisc *q, unsigned long cl)
624{
625}
626
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800627static struct tcf_proto **sfq_find_tcf(struct Qdisc *sch, unsigned long cl)
628{
629 struct sfq_sched_data *q = qdisc_priv(sch);
630
631 if (cl)
632 return NULL;
633 return &q->filter_list;
634}
635
Patrick McHardy94de78d2008-01-31 18:37:16 -0800636static int sfq_dump_class(struct Qdisc *sch, unsigned long cl,
637 struct sk_buff *skb, struct tcmsg *tcm)
638{
639 tcm->tcm_handle |= TC_H_MIN(cl);
640 return 0;
641}
642
643static int sfq_dump_class_stats(struct Qdisc *sch, unsigned long cl,
644 struct gnet_dump *d)
645{
646 struct sfq_sched_data *q = qdisc_priv(sch);
Eric Dumazetee09b3c2010-12-22 11:39:59 -0800647 sfq_index idx = q->ht[cl - 1];
648 struct gnet_stats_queue qs = { 0 };
649 struct tc_sfq_xstats xstats = { 0 };
Eric Dumazetc4266262010-12-15 08:18:36 +0000650 struct sk_buff *skb;
651
Eric Dumazetee09b3c2010-12-22 11:39:59 -0800652 if (idx != SFQ_EMPTY_SLOT) {
653 const struct sfq_slot *slot = &q->slots[idx];
Patrick McHardy94de78d2008-01-31 18:37:16 -0800654
Eric Dumazeteeaeb062010-12-28 21:53:33 +0000655 xstats.allot = slot->allot << SFQ_ALLOT_SHIFT;
Eric Dumazetee09b3c2010-12-22 11:39:59 -0800656 qs.qlen = slot->qlen;
657 slot_queue_walk(slot, skb)
658 qs.backlog += qdisc_pkt_len(skb);
659 }
Patrick McHardy94de78d2008-01-31 18:37:16 -0800660 if (gnet_stats_copy_queue(d, &qs) < 0)
661 return -1;
662 return gnet_stats_copy_app(d, &xstats, sizeof(xstats));
663}
664
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800665static void sfq_walk(struct Qdisc *sch, struct qdisc_walker *arg)
666{
Patrick McHardy94de78d2008-01-31 18:37:16 -0800667 struct sfq_sched_data *q = qdisc_priv(sch);
668 unsigned int i;
669
670 if (arg->stop)
671 return;
672
Eric Dumazet817fb152011-01-20 00:14:58 +0000673 for (i = 0; i < q->divisor; i++) {
Eric Dumazeteda83e32010-12-20 12:54:58 +0000674 if (q->ht[i] == SFQ_EMPTY_SLOT ||
Patrick McHardy94de78d2008-01-31 18:37:16 -0800675 arg->count < arg->skip) {
676 arg->count++;
677 continue;
678 }
679 if (arg->fn(sch, i + 1, arg) < 0) {
680 arg->stop = 1;
681 break;
682 }
683 arg->count++;
684 }
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800685}
686
687static const struct Qdisc_class_ops sfq_class_ops = {
Jarek Poplawski41065fb2010-08-10 22:31:02 +0000688 .leaf = sfq_leaf,
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800689 .get = sfq_get,
Jarek Poplawskida7115d2010-08-09 12:18:17 +0000690 .put = sfq_put,
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800691 .tcf_chain = sfq_find_tcf,
Jarek Poplawskieb4a5522010-08-06 00:22:35 +0000692 .bind_tcf = sfq_bind,
Jarek Poplawskida7115d2010-08-09 12:18:17 +0000693 .unbind_tcf = sfq_put,
Patrick McHardy94de78d2008-01-31 18:37:16 -0800694 .dump = sfq_dump_class,
695 .dump_stats = sfq_dump_class_stats,
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800696 .walk = sfq_walk,
697};
698
Eric Dumazet20fea082007-11-14 01:44:41 -0800699static struct Qdisc_ops sfq_qdisc_ops __read_mostly = {
Patrick McHardy7d2681a2008-01-31 18:36:52 -0800700 .cl_ops = &sfq_class_ops,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700701 .id = "sfq",
702 .priv_size = sizeof(struct sfq_sched_data),
703 .enqueue = sfq_enqueue,
704 .dequeue = sfq_dequeue,
Patrick McHardy48a8f512008-10-31 00:44:18 -0700705 .peek = sfq_peek,
Linus Torvalds1da177e2005-04-16 15:20:36 -0700706 .drop = sfq_drop,
707 .init = sfq_init,
708 .reset = sfq_reset,
709 .destroy = sfq_destroy,
710 .change = NULL,
711 .dump = sfq_dump,
712 .owner = THIS_MODULE,
713};
714
715static int __init sfq_module_init(void)
716{
717 return register_qdisc(&sfq_qdisc_ops);
718}
YOSHIFUJI Hideaki10297b92007-02-09 23:25:16 +0900719static void __exit sfq_module_exit(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700720{
721 unregister_qdisc(&sfq_qdisc_ops);
722}
723module_init(sfq_module_init)
724module_exit(sfq_module_exit)
725MODULE_LICENSE("GPL");