]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - net/sched/sch_sfq.c
2 * net/sched/sch_sfq.c Stochastic Fairness Queueing discipline.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
12 #include <linux/module.h>
13 #include <linux/types.h>
14 #include <linux/kernel.h>
15 #include <linux/jiffies.h>
16 #include <linux/string.h>
18 #include <linux/errno.h>
19 #include <linux/init.h>
20 #include <linux/ipv6.h>
21 #include <linux/skbuff.h>
22 #include <linux/jhash.h>
24 #include <net/netlink.h>
25 #include <net/pkt_sched.h>
28 /* Stochastic Fairness Queuing algorithm.
29 =======================================
32 Paul E. McKenney "Stochastic Fairness Queuing",
33 IEEE INFOCOMM'90 Proceedings, San Francisco, 1990.
35 Paul E. McKenney "Stochastic Fairness Queuing",
36 "Interworking: Research and Experience", v.2, 1991, p.113-131.
40 M. Shreedhar and George Varghese "Efficient Fair
41 Queuing using Deficit Round Robin", Proc. SIGCOMM 95.
44 This is not the thing that is usually called (W)FQ nowadays.
45 It does not use any timestamp mechanism, but instead
46 processes queues in round-robin order.
50 - It is very cheap. Both CPU and memory requirements are minimal.
54 - "Stochastic" -> It is not 100% fair.
55 When hash collisions occur, several flows are considered as one.
57 - "Round-robin" -> It introduces larger delays than virtual clock
58 based schemes, and should not be used for isolating interactive
59 traffic from non-interactive. It means, that this scheduler
60 should be used as leaf of CBQ or P3, which put interactive traffic
61 to higher priority band.
63 We still need true WFQ for top level CSZ, but using WFQ
64 for the best effort traffic is absolutely pointless:
65 SFQ is superior for this purpose.
68 This implementation limits maximal queue length to 128;
69 maximal mtu to 2^15-1; number of hash buckets to 1024.
70 The only goal of this restrictions was that all data
71 fit into one 4K page :-). Struct sfq_sched_data is
72 organized in anti-cache manner: all the data for a bucket
73 are scattered over different locations. This is not good,
74 but it allowed me to put it into 4K.
76 It is easy to increase these values, but not in flight. */
79 #define SFQ_HASH_DIVISOR 1024
81 /* This type should contain at least SFQ_DEPTH*2 values */
82 typedef unsigned char sfq_index
;
94 unsigned quantum
; /* Allotment per round: MUST BE >= MTU */
98 struct timer_list perturb_timer
;
100 sfq_index tail
; /* Index of current slot in round */
101 sfq_index max_depth
; /* Maximal depth */
103 sfq_index ht
[SFQ_HASH_DIVISOR
]; /* Hash table */
104 sfq_index next
[SFQ_DEPTH
]; /* Active slots link */
105 short allot
[SFQ_DEPTH
]; /* Current allotment per slot */
106 unsigned short hash
[SFQ_DEPTH
]; /* Hash value indexed by slots */
107 struct sk_buff_head qs
[SFQ_DEPTH
]; /* Slot queue */
108 struct sfq_head dep
[SFQ_DEPTH
*2]; /* Linked list of slots, indexed by depth */
111 static __inline__
unsigned sfq_fold_hash(struct sfq_sched_data
*q
, u32 h
, u32 h1
)
113 return jhash_2words(h
, h1
, q
->perturbation
) & (SFQ_HASH_DIVISOR
- 1);
116 static unsigned sfq_hash(struct sfq_sched_data
*q
, struct sk_buff
*skb
)
120 switch (skb
->protocol
) {
121 case __constant_htons(ETH_P_IP
):
123 const struct iphdr
*iph
= ip_hdr(skb
);
125 h2
= iph
->saddr
^iph
->protocol
;
126 if (!(iph
->frag_off
&htons(IP_MF
|IP_OFFSET
)) &&
127 (iph
->protocol
== IPPROTO_TCP
||
128 iph
->protocol
== IPPROTO_UDP
||
129 iph
->protocol
== IPPROTO_UDPLITE
||
130 iph
->protocol
== IPPROTO_SCTP
||
131 iph
->protocol
== IPPROTO_DCCP
||
132 iph
->protocol
== IPPROTO_ESP
))
133 h2
^= *(((u32
*)iph
) + iph
->ihl
);
136 case __constant_htons(ETH_P_IPV6
):
138 struct ipv6hdr
*iph
= ipv6_hdr(skb
);
139 h
= iph
->daddr
.s6_addr32
[3];
140 h2
= iph
->saddr
.s6_addr32
[3]^iph
->nexthdr
;
141 if (iph
->nexthdr
== IPPROTO_TCP
||
142 iph
->nexthdr
== IPPROTO_UDP
||
143 iph
->nexthdr
== IPPROTO_UDPLITE
||
144 iph
->nexthdr
== IPPROTO_SCTP
||
145 iph
->nexthdr
== IPPROTO_DCCP
||
146 iph
->nexthdr
== IPPROTO_ESP
)
147 h2
^= *(u32
*)&iph
[1];
151 h
= (u32
)(unsigned long)skb
->dst
^skb
->protocol
;
152 h2
= (u32
)(unsigned long)skb
->sk
;
154 return sfq_fold_hash(q
, h
, h2
);
157 static inline void sfq_link(struct sfq_sched_data
*q
, sfq_index x
)
160 int d
= q
->qs
[x
].qlen
+ SFQ_DEPTH
;
166 q
->dep
[p
].next
= q
->dep
[n
].prev
= x
;
169 static inline void sfq_dec(struct sfq_sched_data
*q
, sfq_index x
)
178 if (n
== p
&& q
->max_depth
== q
->qs
[x
].qlen
+ 1)
184 static inline void sfq_inc(struct sfq_sched_data
*q
, sfq_index x
)
194 if (q
->max_depth
< d
)
200 static unsigned int sfq_drop(struct Qdisc
*sch
)
202 struct sfq_sched_data
*q
= qdisc_priv(sch
);
203 sfq_index d
= q
->max_depth
;
207 /* Queue is full! Find the longest slot and
208 drop a packet from it */
211 sfq_index x
= q
->dep
[d
+SFQ_DEPTH
].next
;
214 __skb_unlink(skb
, &q
->qs
[x
]);
219 sch
->qstats
.backlog
-= len
;
224 /* It is difficult to believe, but ALL THE SLOTS HAVE LENGTH 1. */
225 d
= q
->next
[q
->tail
];
226 q
->next
[q
->tail
] = q
->next
[d
];
227 q
->allot
[q
->next
[d
]] += q
->quantum
;
230 __skb_unlink(skb
, &q
->qs
[d
]);
234 q
->ht
[q
->hash
[d
]] = SFQ_DEPTH
;
236 sch
->qstats
.backlog
-= len
;
244 sfq_enqueue(struct sk_buff
*skb
, struct Qdisc
* sch
)
246 struct sfq_sched_data
*q
= qdisc_priv(sch
);
247 unsigned hash
= sfq_hash(q
, skb
);
251 if (x
== SFQ_DEPTH
) {
252 q
->ht
[hash
] = x
= q
->dep
[SFQ_DEPTH
].next
;
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.
259 if (q
->qs
[x
].qlen
>= q
->limit
)
260 return qdisc_drop(skb
, sch
);
262 sch
->qstats
.backlog
+= skb
->len
;
263 __skb_queue_tail(&q
->qs
[x
], skb
);
265 if (q
->qs
[x
].qlen
== 1) { /* The flow is new */
266 if (q
->tail
== SFQ_DEPTH
) { /* It is the first flow */
269 q
->allot
[x
] = q
->quantum
;
271 q
->next
[x
] = q
->next
[q
->tail
];
272 q
->next
[q
->tail
] = x
;
276 if (++sch
->q
.qlen
<= q
->limit
) {
277 sch
->bstats
.bytes
+= skb
->len
;
278 sch
->bstats
.packets
++;
287 sfq_requeue(struct sk_buff
*skb
, struct Qdisc
* sch
)
289 struct sfq_sched_data
*q
= qdisc_priv(sch
);
290 unsigned hash
= sfq_hash(q
, skb
);
294 if (x
== SFQ_DEPTH
) {
295 q
->ht
[hash
] = x
= q
->dep
[SFQ_DEPTH
].next
;
298 sch
->qstats
.backlog
+= skb
->len
;
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
305 if (q
->qs
[x
].qlen
> q
->limit
) {
307 __skb_unlink(skb
, &q
->qs
[x
]);
309 sch
->qstats
.backlog
-= skb
->len
;
314 if (q
->qs
[x
].qlen
== 1) { /* The flow is new */
315 if (q
->tail
== SFQ_DEPTH
) { /* It is the first flow */
318 q
->allot
[x
] = q
->quantum
;
320 q
->next
[x
] = q
->next
[q
->tail
];
321 q
->next
[q
->tail
] = x
;
325 if (++sch
->q
.qlen
<= q
->limit
) {
326 sch
->qstats
.requeues
++;
338 static struct sk_buff
*
339 sfq_dequeue(struct Qdisc
* sch
)
341 struct sfq_sched_data
*q
= qdisc_priv(sch
);
345 /* No active slots */
346 if (q
->tail
== SFQ_DEPTH
)
349 a
= old_a
= q
->next
[q
->tail
];
352 skb
= __skb_dequeue(&q
->qs
[a
]);
355 sch
->qstats
.backlog
-= skb
->len
;
357 /* Is the slot empty? */
358 if (q
->qs
[a
].qlen
== 0) {
359 q
->ht
[q
->hash
[a
]] = SFQ_DEPTH
;
365 q
->next
[q
->tail
] = a
;
366 q
->allot
[a
] += q
->quantum
;
367 } else if ((q
->allot
[a
] -= skb
->len
) <= 0) {
370 q
->allot
[a
] += q
->quantum
;
376 sfq_reset(struct Qdisc
* sch
)
380 while ((skb
= sfq_dequeue(sch
)) != NULL
)
384 static void sfq_perturbation(unsigned long arg
)
386 struct Qdisc
*sch
= (struct Qdisc
*)arg
;
387 struct sfq_sched_data
*q
= qdisc_priv(sch
);
389 get_random_bytes(&q
->perturbation
, 4);
391 if (q
->perturb_period
)
392 mod_timer(&q
->perturb_timer
, jiffies
+ q
->perturb_period
);
395 static int sfq_change(struct Qdisc
*sch
, struct rtattr
*opt
)
397 struct sfq_sched_data
*q
= qdisc_priv(sch
);
398 struct tc_sfq_qopt
*ctl
= RTA_DATA(opt
);
401 if (opt
->rta_len
< RTA_LENGTH(sizeof(*ctl
)))
405 q
->quantum
= ctl
->quantum
? : psched_mtu(sch
->dev
);
406 q
->perturb_period
= ctl
->perturb_period
*HZ
;
408 q
->limit
= min_t(u32
, ctl
->limit
, SFQ_DEPTH
- 1);
411 while (sch
->q
.qlen
> q
->limit
)
413 qdisc_tree_decrease_qlen(sch
, qlen
- sch
->q
.qlen
);
415 del_timer(&q
->perturb_timer
);
416 if (q
->perturb_period
) {
417 mod_timer(&q
->perturb_timer
, jiffies
+ q
->perturb_period
);
418 get_random_bytes(&q
->perturbation
, 4);
420 sch_tree_unlock(sch
);
424 static int sfq_init(struct Qdisc
*sch
, struct rtattr
*opt
)
426 struct sfq_sched_data
*q
= qdisc_priv(sch
);
429 setup_timer(&q
->perturb_timer
, sfq_perturbation
, (unsigned long)sch
);
431 for (i
=0; i
<SFQ_HASH_DIVISOR
; i
++)
432 q
->ht
[i
] = SFQ_DEPTH
;
433 for (i
=0; i
<SFQ_DEPTH
; i
++) {
434 skb_queue_head_init(&q
->qs
[i
]);
435 q
->dep
[i
+SFQ_DEPTH
].next
= i
+SFQ_DEPTH
;
436 q
->dep
[i
+SFQ_DEPTH
].prev
= i
+SFQ_DEPTH
;
438 q
->limit
= SFQ_DEPTH
- 1;
442 q
->quantum
= psched_mtu(sch
->dev
);
443 q
->perturb_period
= 0;
444 get_random_bytes(&q
->perturbation
, 4);
446 int err
= sfq_change(sch
, opt
);
450 for (i
=0; i
<SFQ_DEPTH
; i
++)
455 static void sfq_destroy(struct Qdisc
*sch
)
457 struct sfq_sched_data
*q
= qdisc_priv(sch
);
458 del_timer(&q
->perturb_timer
);
461 static int sfq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
463 struct sfq_sched_data
*q
= qdisc_priv(sch
);
464 unsigned char *b
= skb_tail_pointer(skb
);
465 struct tc_sfq_qopt opt
;
467 opt
.quantum
= q
->quantum
;
468 opt
.perturb_period
= q
->perturb_period
/HZ
;
470 opt
.limit
= q
->limit
;
471 opt
.divisor
= SFQ_HASH_DIVISOR
;
472 opt
.flows
= q
->limit
;
474 RTA_PUT(skb
, TCA_OPTIONS
, sizeof(opt
), &opt
);
483 static struct Qdisc_ops sfq_qdisc_ops
= {
487 .priv_size
= sizeof(struct sfq_sched_data
),
488 .enqueue
= sfq_enqueue
,
489 .dequeue
= sfq_dequeue
,
490 .requeue
= sfq_requeue
,
494 .destroy
= sfq_destroy
,
497 .owner
= THIS_MODULE
,
500 static int __init
sfq_module_init(void)
502 return register_qdisc(&sfq_qdisc_ops
);
504 static void __exit
sfq_module_exit(void)
506 unregister_qdisc(&sfq_qdisc_ops
);
508 module_init(sfq_module_init
)
509 module_exit(sfq_module_exit
)
510 MODULE_LICENSE("GPL");