Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | /* |
| 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 Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 12 | #include <linux/module.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 13 | #include <linux/types.h> |
| 14 | #include <linux/kernel.h> |
| 15 | #include <linux/jiffies.h> |
| 16 | #include <linux/string.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 17 | #include <linux/in.h> |
| 18 | #include <linux/errno.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 19 | #include <linux/init.h> |
Patrick McHardy | 0ba4805 | 2007-07-02 22:49:07 -0700 | [diff] [blame] | 20 | #include <linux/ipv6.h> |
| 21 | #include <linux/skbuff.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 22 | #include <net/ip.h> |
Arnaldo Carvalho de Melo | dc5fc57 | 2007-03-25 23:06:12 -0700 | [diff] [blame] | 23 | #include <net/netlink.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 24 | #include <net/pkt_sched.h> |
| 25 | |
| 26 | |
| 27 | /* Stochastic Fairness Queuing algorithm. |
| 28 | ======================================= |
| 29 | |
| 30 | Source: |
| 31 | Paul E. McKenney "Stochastic Fairness Queuing", |
| 32 | IEEE INFOCOMM'90 Proceedings, San Francisco, 1990. |
| 33 | |
| 34 | Paul E. McKenney "Stochastic Fairness Queuing", |
| 35 | "Interworking: Research and Experience", v.2, 1991, p.113-131. |
| 36 | |
| 37 | |
| 38 | See also: |
| 39 | M. Shreedhar and George Varghese "Efficient Fair |
| 40 | Queuing using Deficit Round Robin", Proc. SIGCOMM 95. |
| 41 | |
| 42 | |
YOSHIFUJI Hideaki | 10297b9 | 2007-02-09 23:25:16 +0900 | [diff] [blame] | 43 | This is not the thing that is usually called (W)FQ nowadays. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 44 | It does not use any timestamp mechanism, but instead |
| 45 | processes queues in round-robin order. |
| 46 | |
| 47 | ADVANTAGE: |
| 48 | |
| 49 | - It is very cheap. Both CPU and memory requirements are minimal. |
| 50 | |
| 51 | DRAWBACKS: |
| 52 | |
YOSHIFUJI Hideaki | 10297b9 | 2007-02-09 23:25:16 +0900 | [diff] [blame] | 53 | - "Stochastic" -> It is not 100% fair. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 54 | When hash collisions occur, several flows are considered as one. |
| 55 | |
| 56 | - "Round-robin" -> It introduces larger delays than virtual clock |
| 57 | based schemes, and should not be used for isolating interactive |
| 58 | traffic from non-interactive. It means, that this scheduler |
| 59 | should be used as leaf of CBQ or P3, which put interactive traffic |
| 60 | to higher priority band. |
| 61 | |
| 62 | We still need true WFQ for top level CSZ, but using WFQ |
| 63 | for the best effort traffic is absolutely pointless: |
| 64 | SFQ is superior for this purpose. |
| 65 | |
| 66 | IMPLEMENTATION: |
| 67 | This implementation limits maximal queue length to 128; |
| 68 | maximal mtu to 2^15-1; number of hash buckets to 1024. |
| 69 | The only goal of this restrictions was that all data |
| 70 | fit into one 4K page :-). Struct sfq_sched_data is |
| 71 | organized in anti-cache manner: all the data for a bucket |
| 72 | are scattered over different locations. This is not good, |
| 73 | but it allowed me to put it into 4K. |
| 74 | |
| 75 | It is easy to increase these values, but not in flight. */ |
| 76 | |
| 77 | #define SFQ_DEPTH 128 |
| 78 | #define SFQ_HASH_DIVISOR 1024 |
| 79 | |
| 80 | /* This type should contain at least SFQ_DEPTH*2 values */ |
| 81 | typedef unsigned char sfq_index; |
| 82 | |
| 83 | struct sfq_head |
| 84 | { |
| 85 | sfq_index next; |
| 86 | sfq_index prev; |
| 87 | }; |
| 88 | |
| 89 | struct sfq_sched_data |
| 90 | { |
| 91 | /* Parameters */ |
| 92 | int perturb_period; |
| 93 | unsigned quantum; /* Allotment per round: MUST BE >= MTU */ |
| 94 | int limit; |
| 95 | |
| 96 | /* Variables */ |
| 97 | struct timer_list perturb_timer; |
| 98 | int perturbation; |
| 99 | sfq_index tail; /* Index of current slot in round */ |
| 100 | sfq_index max_depth; /* Maximal depth */ |
| 101 | |
| 102 | sfq_index ht[SFQ_HASH_DIVISOR]; /* Hash table */ |
| 103 | sfq_index next[SFQ_DEPTH]; /* Active slots link */ |
| 104 | short allot[SFQ_DEPTH]; /* Current allotment per slot */ |
| 105 | unsigned short hash[SFQ_DEPTH]; /* Hash value indexed by slots */ |
| 106 | struct sk_buff_head qs[SFQ_DEPTH]; /* Slot queue */ |
| 107 | struct sfq_head dep[SFQ_DEPTH*2]; /* Linked list of slots, indexed by depth */ |
| 108 | }; |
| 109 | |
| 110 | static __inline__ unsigned sfq_fold_hash(struct sfq_sched_data *q, u32 h, u32 h1) |
| 111 | { |
| 112 | int pert = q->perturbation; |
| 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 | } |
| 119 | |
| 120 | static unsigned sfq_hash(struct sfq_sched_data *q, struct sk_buff *skb) |
| 121 | { |
| 122 | u32 h, h2; |
| 123 | |
| 124 | switch (skb->protocol) { |
| 125 | case __constant_htons(ETH_P_IP): |
| 126 | { |
Arnaldo Carvalho de Melo | eddc9ec | 2007-04-20 22:47:35 -0700 | [diff] [blame] | 127 | const struct iphdr *iph = ip_hdr(skb); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 128 | h = iph->daddr; |
| 129 | h2 = iph->saddr^iph->protocol; |
| 130 | if (!(iph->frag_off&htons(IP_MF|IP_OFFSET)) && |
| 131 | (iph->protocol == IPPROTO_TCP || |
| 132 | iph->protocol == IPPROTO_UDP || |
Patrick McHardy | a8d0f95 | 2007-02-07 15:07:43 -0800 | [diff] [blame] | 133 | iph->protocol == IPPROTO_UDPLITE || |
Patrick McHardy | ae82af5 | 2006-01-17 13:01:06 -0800 | [diff] [blame] | 134 | iph->protocol == IPPROTO_SCTP || |
| 135 | iph->protocol == IPPROTO_DCCP || |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 136 | iph->protocol == IPPROTO_ESP)) |
| 137 | h2 ^= *(((u32*)iph) + iph->ihl); |
| 138 | break; |
| 139 | } |
| 140 | case __constant_htons(ETH_P_IPV6): |
| 141 | { |
Arnaldo Carvalho de Melo | 0660e03 | 2007-04-25 17:54:47 -0700 | [diff] [blame] | 142 | struct ipv6hdr *iph = ipv6_hdr(skb); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 143 | h = iph->daddr.s6_addr32[3]; |
| 144 | h2 = iph->saddr.s6_addr32[3]^iph->nexthdr; |
| 145 | if (iph->nexthdr == IPPROTO_TCP || |
| 146 | iph->nexthdr == IPPROTO_UDP || |
Patrick McHardy | a8d0f95 | 2007-02-07 15:07:43 -0800 | [diff] [blame] | 147 | iph->nexthdr == IPPROTO_UDPLITE || |
Patrick McHardy | ae82af5 | 2006-01-17 13:01:06 -0800 | [diff] [blame] | 148 | iph->nexthdr == IPPROTO_SCTP || |
| 149 | iph->nexthdr == IPPROTO_DCCP || |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 150 | iph->nexthdr == IPPROTO_ESP) |
| 151 | h2 ^= *(u32*)&iph[1]; |
| 152 | break; |
| 153 | } |
| 154 | default: |
| 155 | h = (u32)(unsigned long)skb->dst^skb->protocol; |
| 156 | h2 = (u32)(unsigned long)skb->sk; |
| 157 | } |
| 158 | return sfq_fold_hash(q, h, h2); |
| 159 | } |
| 160 | |
| 161 | static inline void sfq_link(struct sfq_sched_data *q, sfq_index x) |
| 162 | { |
| 163 | sfq_index p, n; |
| 164 | int d = q->qs[x].qlen + SFQ_DEPTH; |
| 165 | |
| 166 | p = d; |
| 167 | n = q->dep[d].next; |
| 168 | q->dep[x].next = n; |
| 169 | q->dep[x].prev = p; |
| 170 | q->dep[p].next = q->dep[n].prev = x; |
| 171 | } |
| 172 | |
| 173 | static inline void sfq_dec(struct sfq_sched_data *q, sfq_index x) |
| 174 | { |
| 175 | sfq_index p, n; |
| 176 | |
| 177 | n = q->dep[x].next; |
| 178 | p = q->dep[x].prev; |
| 179 | q->dep[p].next = n; |
| 180 | q->dep[n].prev = p; |
| 181 | |
| 182 | if (n == p && q->max_depth == q->qs[x].qlen + 1) |
| 183 | q->max_depth--; |
| 184 | |
| 185 | sfq_link(q, x); |
| 186 | } |
| 187 | |
| 188 | static inline void sfq_inc(struct sfq_sched_data *q, sfq_index x) |
| 189 | { |
| 190 | sfq_index p, n; |
| 191 | int d; |
| 192 | |
| 193 | n = q->dep[x].next; |
| 194 | p = q->dep[x].prev; |
| 195 | q->dep[p].next = n; |
| 196 | q->dep[n].prev = p; |
| 197 | d = q->qs[x].qlen; |
| 198 | if (q->max_depth < d) |
| 199 | q->max_depth = d; |
| 200 | |
| 201 | sfq_link(q, x); |
| 202 | } |
| 203 | |
| 204 | static unsigned int sfq_drop(struct Qdisc *sch) |
| 205 | { |
| 206 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 207 | sfq_index d = q->max_depth; |
| 208 | struct sk_buff *skb; |
| 209 | unsigned int len; |
| 210 | |
| 211 | /* Queue is full! Find the longest slot and |
| 212 | drop a packet from it */ |
| 213 | |
| 214 | if (d > 1) { |
| 215 | sfq_index x = q->dep[d+SFQ_DEPTH].next; |
| 216 | skb = q->qs[x].prev; |
| 217 | len = skb->len; |
| 218 | __skb_unlink(skb, &q->qs[x]); |
| 219 | kfree_skb(skb); |
| 220 | sfq_dec(q, x); |
| 221 | sch->q.qlen--; |
| 222 | sch->qstats.drops++; |
Patrick McHardy | f5539eb | 2006-03-20 19:01:38 -0800 | [diff] [blame] | 223 | sch->qstats.backlog -= len; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 224 | return len; |
| 225 | } |
| 226 | |
| 227 | if (d == 1) { |
| 228 | /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */ |
| 229 | d = q->next[q->tail]; |
| 230 | q->next[q->tail] = q->next[d]; |
| 231 | q->allot[q->next[d]] += q->quantum; |
| 232 | skb = q->qs[d].prev; |
| 233 | len = skb->len; |
| 234 | __skb_unlink(skb, &q->qs[d]); |
| 235 | kfree_skb(skb); |
| 236 | sfq_dec(q, d); |
| 237 | sch->q.qlen--; |
| 238 | q->ht[q->hash[d]] = SFQ_DEPTH; |
| 239 | sch->qstats.drops++; |
Patrick McHardy | f5539eb | 2006-03-20 19:01:38 -0800 | [diff] [blame] | 240 | sch->qstats.backlog -= len; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 241 | return len; |
| 242 | } |
| 243 | |
| 244 | return 0; |
| 245 | } |
| 246 | |
| 247 | static int |
| 248 | sfq_enqueue(struct sk_buff *skb, struct Qdisc* sch) |
| 249 | { |
| 250 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 251 | unsigned hash = sfq_hash(q, skb); |
| 252 | sfq_index x; |
| 253 | |
| 254 | x = q->ht[hash]; |
| 255 | if (x == SFQ_DEPTH) { |
| 256 | q->ht[hash] = x = q->dep[SFQ_DEPTH].next; |
| 257 | q->hash[x] = hash; |
| 258 | } |
Patrick McHardy | f5539eb | 2006-03-20 19:01:38 -0800 | [diff] [blame] | 259 | sch->qstats.backlog += skb->len; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 260 | __skb_queue_tail(&q->qs[x], skb); |
| 261 | sfq_inc(q, x); |
| 262 | if (q->qs[x].qlen == 1) { /* The flow is new */ |
| 263 | if (q->tail == SFQ_DEPTH) { /* It is the first flow */ |
| 264 | q->tail = x; |
| 265 | q->next[x] = x; |
| 266 | q->allot[x] = q->quantum; |
| 267 | } else { |
| 268 | q->next[x] = q->next[q->tail]; |
| 269 | q->next[q->tail] = x; |
| 270 | q->tail = x; |
| 271 | } |
| 272 | } |
Alexey Kuznetsov | 5588b40 | 2007-09-19 10:42:03 -0700 | [diff] [blame^] | 273 | if (++sch->q.qlen <= q->limit) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 274 | sch->bstats.bytes += skb->len; |
| 275 | sch->bstats.packets++; |
| 276 | return 0; |
| 277 | } |
| 278 | |
| 279 | sfq_drop(sch); |
| 280 | return NET_XMIT_CN; |
| 281 | } |
| 282 | |
| 283 | static int |
| 284 | sfq_requeue(struct sk_buff *skb, struct Qdisc* sch) |
| 285 | { |
| 286 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 287 | unsigned hash = sfq_hash(q, skb); |
| 288 | sfq_index x; |
| 289 | |
| 290 | x = q->ht[hash]; |
| 291 | if (x == SFQ_DEPTH) { |
| 292 | q->ht[hash] = x = q->dep[SFQ_DEPTH].next; |
| 293 | q->hash[x] = hash; |
| 294 | } |
Patrick McHardy | f5539eb | 2006-03-20 19:01:38 -0800 | [diff] [blame] | 295 | sch->qstats.backlog += skb->len; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 296 | __skb_queue_head(&q->qs[x], skb); |
| 297 | sfq_inc(q, x); |
| 298 | if (q->qs[x].qlen == 1) { /* The flow is new */ |
| 299 | if (q->tail == SFQ_DEPTH) { /* It is the first flow */ |
| 300 | q->tail = x; |
| 301 | q->next[x] = x; |
| 302 | q->allot[x] = q->quantum; |
| 303 | } else { |
| 304 | q->next[x] = q->next[q->tail]; |
| 305 | q->next[q->tail] = x; |
| 306 | q->tail = x; |
| 307 | } |
| 308 | } |
Alexey Kuznetsov | 5588b40 | 2007-09-19 10:42:03 -0700 | [diff] [blame^] | 309 | if (++sch->q.qlen <= q->limit) { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 310 | sch->qstats.requeues++; |
| 311 | return 0; |
| 312 | } |
| 313 | |
| 314 | sch->qstats.drops++; |
| 315 | sfq_drop(sch); |
| 316 | return NET_XMIT_CN; |
| 317 | } |
| 318 | |
| 319 | |
| 320 | |
| 321 | |
| 322 | static struct sk_buff * |
| 323 | sfq_dequeue(struct Qdisc* sch) |
| 324 | { |
| 325 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 326 | struct sk_buff *skb; |
| 327 | sfq_index a, old_a; |
| 328 | |
| 329 | /* No active slots */ |
| 330 | if (q->tail == SFQ_DEPTH) |
| 331 | return NULL; |
| 332 | |
| 333 | a = old_a = q->next[q->tail]; |
| 334 | |
| 335 | /* Grab packet */ |
| 336 | skb = __skb_dequeue(&q->qs[a]); |
| 337 | sfq_dec(q, a); |
| 338 | sch->q.qlen--; |
Patrick McHardy | f5539eb | 2006-03-20 19:01:38 -0800 | [diff] [blame] | 339 | sch->qstats.backlog -= skb->len; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 340 | |
| 341 | /* Is the slot empty? */ |
| 342 | if (q->qs[a].qlen == 0) { |
| 343 | q->ht[q->hash[a]] = SFQ_DEPTH; |
| 344 | a = q->next[a]; |
| 345 | if (a == old_a) { |
| 346 | q->tail = SFQ_DEPTH; |
| 347 | return skb; |
| 348 | } |
| 349 | q->next[q->tail] = a; |
| 350 | q->allot[a] += q->quantum; |
| 351 | } else if ((q->allot[a] -= skb->len) <= 0) { |
| 352 | q->tail = a; |
| 353 | a = q->next[a]; |
| 354 | q->allot[a] += q->quantum; |
| 355 | } |
| 356 | return skb; |
| 357 | } |
| 358 | |
| 359 | static void |
| 360 | sfq_reset(struct Qdisc* sch) |
| 361 | { |
| 362 | struct sk_buff *skb; |
| 363 | |
| 364 | while ((skb = sfq_dequeue(sch)) != NULL) |
| 365 | kfree_skb(skb); |
| 366 | } |
| 367 | |
| 368 | static void sfq_perturbation(unsigned long arg) |
| 369 | { |
| 370 | struct Qdisc *sch = (struct Qdisc*)arg; |
| 371 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 372 | |
| 373 | q->perturbation = net_random()&0x1F; |
| 374 | |
| 375 | if (q->perturb_period) { |
| 376 | q->perturb_timer.expires = jiffies + q->perturb_period; |
| 377 | add_timer(&q->perturb_timer); |
| 378 | } |
| 379 | } |
| 380 | |
| 381 | static int sfq_change(struct Qdisc *sch, struct rtattr *opt) |
| 382 | { |
| 383 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 384 | struct tc_sfq_qopt *ctl = RTA_DATA(opt); |
Patrick McHardy | 5e50da0 | 2006-11-29 17:36:20 -0800 | [diff] [blame] | 385 | unsigned int qlen; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 386 | |
| 387 | if (opt->rta_len < RTA_LENGTH(sizeof(*ctl))) |
| 388 | return -EINVAL; |
| 389 | |
| 390 | sch_tree_lock(sch); |
| 391 | q->quantum = ctl->quantum ? : psched_mtu(sch->dev); |
| 392 | q->perturb_period = ctl->perturb_period*HZ; |
| 393 | if (ctl->limit) |
Alexey Kuznetsov | 5588b40 | 2007-09-19 10:42:03 -0700 | [diff] [blame^] | 394 | q->limit = min_t(u32, ctl->limit, SFQ_DEPTH - 2); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 395 | |
Patrick McHardy | 5e50da0 | 2006-11-29 17:36:20 -0800 | [diff] [blame] | 396 | qlen = sch->q.qlen; |
Alexey Kuznetsov | 5588b40 | 2007-09-19 10:42:03 -0700 | [diff] [blame^] | 397 | while (sch->q.qlen > q->limit) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 398 | sfq_drop(sch); |
Patrick McHardy | 5e50da0 | 2006-11-29 17:36:20 -0800 | [diff] [blame] | 399 | qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 400 | |
| 401 | del_timer(&q->perturb_timer); |
| 402 | if (q->perturb_period) { |
| 403 | q->perturb_timer.expires = jiffies + q->perturb_period; |
| 404 | add_timer(&q->perturb_timer); |
| 405 | } |
| 406 | sch_tree_unlock(sch); |
| 407 | return 0; |
| 408 | } |
| 409 | |
| 410 | static int sfq_init(struct Qdisc *sch, struct rtattr *opt) |
| 411 | { |
| 412 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 413 | int i; |
| 414 | |
| 415 | init_timer(&q->perturb_timer); |
| 416 | q->perturb_timer.data = (unsigned long)sch; |
| 417 | q->perturb_timer.function = sfq_perturbation; |
| 418 | |
| 419 | for (i=0; i<SFQ_HASH_DIVISOR; i++) |
| 420 | q->ht[i] = SFQ_DEPTH; |
| 421 | for (i=0; i<SFQ_DEPTH; i++) { |
| 422 | skb_queue_head_init(&q->qs[i]); |
| 423 | q->dep[i+SFQ_DEPTH].next = i+SFQ_DEPTH; |
| 424 | q->dep[i+SFQ_DEPTH].prev = i+SFQ_DEPTH; |
| 425 | } |
Alexey Kuznetsov | 5588b40 | 2007-09-19 10:42:03 -0700 | [diff] [blame^] | 426 | q->limit = SFQ_DEPTH - 2; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 427 | q->max_depth = 0; |
| 428 | q->tail = SFQ_DEPTH; |
| 429 | if (opt == NULL) { |
| 430 | q->quantum = psched_mtu(sch->dev); |
| 431 | q->perturb_period = 0; |
| 432 | } else { |
| 433 | int err = sfq_change(sch, opt); |
| 434 | if (err) |
| 435 | return err; |
| 436 | } |
| 437 | for (i=0; i<SFQ_DEPTH; i++) |
| 438 | sfq_link(q, i); |
| 439 | return 0; |
| 440 | } |
| 441 | |
| 442 | static void sfq_destroy(struct Qdisc *sch) |
| 443 | { |
| 444 | struct sfq_sched_data *q = qdisc_priv(sch); |
| 445 | del_timer(&q->perturb_timer); |
| 446 | } |
| 447 | |
| 448 | static int sfq_dump(struct Qdisc *sch, struct sk_buff *skb) |
| 449 | { |
| 450 | struct sfq_sched_data *q = qdisc_priv(sch); |
Arnaldo Carvalho de Melo | 27a884d | 2007-04-19 20:29:13 -0700 | [diff] [blame] | 451 | unsigned char *b = skb_tail_pointer(skb); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 452 | struct tc_sfq_qopt opt; |
| 453 | |
| 454 | opt.quantum = q->quantum; |
| 455 | opt.perturb_period = q->perturb_period/HZ; |
| 456 | |
| 457 | opt.limit = q->limit; |
| 458 | opt.divisor = SFQ_HASH_DIVISOR; |
| 459 | opt.flows = q->limit; |
| 460 | |
| 461 | RTA_PUT(skb, TCA_OPTIONS, sizeof(opt), &opt); |
| 462 | |
| 463 | return skb->len; |
| 464 | |
| 465 | rtattr_failure: |
Arnaldo Carvalho de Melo | dc5fc57 | 2007-03-25 23:06:12 -0700 | [diff] [blame] | 466 | nlmsg_trim(skb, b); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 467 | return -1; |
| 468 | } |
| 469 | |
| 470 | static struct Qdisc_ops sfq_qdisc_ops = { |
| 471 | .next = NULL, |
| 472 | .cl_ops = NULL, |
| 473 | .id = "sfq", |
| 474 | .priv_size = sizeof(struct sfq_sched_data), |
| 475 | .enqueue = sfq_enqueue, |
| 476 | .dequeue = sfq_dequeue, |
| 477 | .requeue = sfq_requeue, |
| 478 | .drop = sfq_drop, |
| 479 | .init = sfq_init, |
| 480 | .reset = sfq_reset, |
| 481 | .destroy = sfq_destroy, |
| 482 | .change = NULL, |
| 483 | .dump = sfq_dump, |
| 484 | .owner = THIS_MODULE, |
| 485 | }; |
| 486 | |
| 487 | static int __init sfq_module_init(void) |
| 488 | { |
| 489 | return register_qdisc(&sfq_qdisc_ops); |
| 490 | } |
YOSHIFUJI Hideaki | 10297b9 | 2007-02-09 23:25:16 +0900 | [diff] [blame] | 491 | static void __exit sfq_module_exit(void) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 492 | { |
| 493 | unregister_qdisc(&sfq_qdisc_ops); |
| 494 | } |
| 495 | module_init(sfq_module_init) |
| 496 | module_exit(sfq_module_exit) |
| 497 | MODULE_LICENSE("GPL"); |