compat/nes: Adding pci_zalloc_consistent backport
[compat-rdma/compat.git] / compat / sch_codel.c
1 /*
2  * Codel - The Controlled-Delay Active Queue Management algorithm
3  *
4  *  Copyright (C) 2011-2012 Kathleen Nichols <nichols@pollere.com>
5  *  Copyright (C) 2011-2012 Van Jacobson <van@pollere.net>
6  *
7  *  Implemented on linux by :
8  *  Copyright (C) 2012 Michael D. Taht <dave.taht@bufferbloat.net>
9  *  Copyright (C) 2012 Eric Dumazet <edumazet@google.com>
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 1. Redistributions of source code must retain the above copyright
15  *    notice, this list of conditions, and the following disclaimer,
16  *    without modification.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. The names of the authors may not be used to endorse or promote products
21  *    derived from this software without specific prior written permission.
22  *
23  * Alternatively, provided that this notice is retained in full, this
24  * software may be distributed under the terms of the GNU General
25  * Public License ("GPL") version 2, in which case the provisions of the
26  * GPL apply INSTEAD OF those given above.
27  *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
39  * DAMAGE.
40  *
41  */
42
43 #include <linux/module.h>
44 #include <linux/slab.h>
45 #include <linux/types.h>
46 #include <linux/kernel.h>
47 #include <linux/errno.h>
48 #include <linux/skbuff.h>
49 #include <linux/prefetch.h>
50 #include <net/pkt_sched.h>
51 #include <net/codel.h>
52
53
54 #define DEFAULT_CODEL_LIMIT 1000
55
56 struct codel_sched_data {
57         struct codel_params     params;
58         struct codel_vars       vars;
59         struct codel_stats      stats;
60         u32                     drop_overlimit;
61 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
62         u32 limit;
63 #endif
64 };
65
66 /* This is the specific function called from codel_dequeue()
67  * to dequeue a packet from queue. Note: backlog is handled in
68  * codel, we dont need to reduce it here.
69  */
70 static struct sk_buff *dequeue(struct codel_vars *vars, struct Qdisc *sch)
71 {
72         struct sk_buff *skb = __skb_dequeue(&sch->q);
73
74         prefetch(&skb->end); /* we'll need skb_shinfo() */
75         return skb;
76 }
77
78 static struct sk_buff *codel_qdisc_dequeue(struct Qdisc *sch)
79 {
80         struct codel_sched_data *q = qdisc_priv(sch);
81         struct sk_buff *skb;
82
83         skb = codel_dequeue(sch, &q->params, &q->vars, &q->stats, dequeue);
84
85         /* We cant call qdisc_tree_decrease_qlen() if our qlen is 0,
86          * or HTB crashes. Defer it for next round.
87          */
88         if (q->stats.drop_count && sch->q.qlen) {
89                 qdisc_tree_decrease_qlen(sch, q->stats.drop_count);
90                 q->stats.drop_count = 0;
91         }
92         if (skb)
93                 qdisc_bstats_update(sch, skb);
94         return skb;
95 }
96
97 static int codel_qdisc_enqueue(struct sk_buff *skb, struct Qdisc *sch)
98 {
99         struct codel_sched_data *q;
100
101         q = qdisc_priv(sch);
102
103 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
104         if (likely(qdisc_qlen(sch) < q->limit)) {
105 #else
106         if (likely(qdisc_qlen(sch) < sch->limit)) {
107 #endif
108                 codel_set_enqueue_time(skb);
109                 return qdisc_enqueue_tail(skb, sch);
110         }
111         q->drop_overlimit++;
112         return qdisc_drop(skb, sch);
113 }
114
115 static const struct nla_policy codel_policy[TCA_CODEL_MAX + 1] = {
116         [TCA_CODEL_TARGET]      = { .type = NLA_U32 },
117         [TCA_CODEL_LIMIT]       = { .type = NLA_U32 },
118         [TCA_CODEL_INTERVAL]    = { .type = NLA_U32 },
119         [TCA_CODEL_ECN]         = { .type = NLA_U32 },
120 };
121
122 static int codel_change(struct Qdisc *sch, struct nlattr *opt)
123 {
124         struct codel_sched_data *q = qdisc_priv(sch);
125         struct nlattr *tb[TCA_CODEL_MAX + 1];
126         unsigned int qlen;
127         int err;
128
129         if (!opt)
130                 return -EINVAL;
131
132         err = nla_parse_nested(tb, TCA_CODEL_MAX, opt, codel_policy);
133         if (err < 0)
134                 return err;
135
136         sch_tree_lock(sch);
137
138         if (tb[TCA_CODEL_TARGET]) {
139                 u32 target = nla_get_u32(tb[TCA_CODEL_TARGET]);
140
141                 q->params.target = ((u64)target * NSEC_PER_USEC) >> CODEL_SHIFT;
142         }
143
144         if (tb[TCA_CODEL_INTERVAL]) {
145                 u32 interval = nla_get_u32(tb[TCA_CODEL_INTERVAL]);
146
147                 q->params.interval = ((u64)interval * NSEC_PER_USEC) >> CODEL_SHIFT;
148         }
149
150         if (tb[TCA_CODEL_LIMIT])
151 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
152                 q->limit = nla_get_u32(tb[TCA_CODEL_LIMIT]);
153 #else
154                 sch->limit = nla_get_u32(tb[TCA_CODEL_LIMIT]);
155 #endif
156
157         if (tb[TCA_CODEL_ECN])
158                 q->params.ecn = !!nla_get_u32(tb[TCA_CODEL_ECN]);
159
160         qlen = sch->q.qlen;
161 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
162         while (sch->q.qlen > q->limit) {
163 #else
164         while (sch->q.qlen > sch->limit) {
165 #endif
166                 struct sk_buff *skb = __skb_dequeue(&sch->q);
167
168                 sch->qstats.backlog -= qdisc_pkt_len(skb);
169                 qdisc_drop(skb, sch);
170         }
171         qdisc_tree_decrease_qlen(sch, qlen - sch->q.qlen);
172
173         sch_tree_unlock(sch);
174         return 0;
175 }
176
177 static int codel_init(struct Qdisc *sch, struct nlattr *opt)
178 {
179         struct codel_sched_data *q = qdisc_priv(sch);
180
181 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
182         q->limit = DEFAULT_CODEL_LIMIT;
183 #else
184         sch->limit = DEFAULT_CODEL_LIMIT;
185 #endif
186
187         codel_params_init(&q->params);
188         codel_vars_init(&q->vars);
189         codel_stats_init(&q->stats);
190
191         if (opt) {
192                 int err = codel_change(sch, opt);
193
194                 if (err)
195                         return err;
196         }
197
198 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
199         if (q->limit >= 1)
200 #else
201         if (sch->limit >= 1)
202 #endif
203                 sch->flags |= TCQ_F_CAN_BYPASS;
204         else
205                 sch->flags &= ~TCQ_F_CAN_BYPASS;
206
207         return 0;
208 }
209
210 static int codel_dump(struct Qdisc *sch, struct sk_buff *skb)
211 {
212         struct codel_sched_data *q = qdisc_priv(sch);
213         struct nlattr *opts;
214
215         opts = nla_nest_start(skb, TCA_OPTIONS);
216         if (opts == NULL)
217                 goto nla_put_failure;
218
219         if (nla_put_u32(skb, TCA_CODEL_TARGET,
220                         codel_time_to_us(q->params.target)) ||
221             nla_put_u32(skb, TCA_CODEL_LIMIT,
222 #if (LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,39))
223                         q->limit) ||
224 #else
225                         sch->limit) ||
226 #endif
227             nla_put_u32(skb, TCA_CODEL_INTERVAL,
228                         codel_time_to_us(q->params.interval)) ||
229             nla_put_u32(skb, TCA_CODEL_ECN,
230                         q->params.ecn))
231                 goto nla_put_failure;
232
233         return nla_nest_end(skb, opts);
234
235 nla_put_failure:
236         nla_nest_cancel(skb, opts);
237         return -1;
238 }
239
240 static int codel_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
241 {
242         const struct codel_sched_data *q = qdisc_priv(sch);
243         struct tc_codel_xstats st = {
244                 .maxpacket      = q->stats.maxpacket,
245                 .count          = q->vars.count,
246                 .lastcount      = q->vars.lastcount,
247                 .drop_overlimit = q->drop_overlimit,
248                 .ldelay         = codel_time_to_us(q->vars.ldelay),
249                 .dropping       = q->vars.dropping,
250                 .ecn_mark       = q->stats.ecn_mark,
251         };
252
253         if (q->vars.dropping) {
254                 codel_tdiff_t delta = q->vars.drop_next - codel_get_time();
255
256                 if (delta >= 0)
257                         st.drop_next = codel_time_to_us(delta);
258                 else
259                         st.drop_next = -codel_time_to_us(-delta);
260         }
261
262         return gnet_stats_copy_app(d, &st, sizeof(st));
263 }
264
265 static void codel_reset(struct Qdisc *sch)
266 {
267         struct codel_sched_data *q = qdisc_priv(sch);
268
269         qdisc_reset_queue(sch);
270         codel_vars_init(&q->vars);
271 }
272
273 static struct Qdisc_ops codel_qdisc_ops __read_mostly = {
274         .id             =       "codel",
275         .priv_size      =       sizeof(struct codel_sched_data),
276
277         .enqueue        =       codel_qdisc_enqueue,
278         .dequeue        =       codel_qdisc_dequeue,
279 #if (LINUX_VERSION_CODE > KERNEL_VERSION(2,6,28))
280         .peek           =       qdisc_peek_dequeued,
281 #endif
282         .init           =       codel_init,
283         .reset          =       codel_reset,
284         .change         =       codel_change,
285         .dump           =       codel_dump,
286         .dump_stats     =       codel_dump_stats,
287         .owner          =       THIS_MODULE,
288 };
289
290 static int __init codel_module_init(void)
291 {
292         return register_qdisc(&codel_qdisc_ops);
293 }
294
295 static void __exit codel_module_exit(void)
296 {
297         unregister_qdisc(&codel_qdisc_ops);
298 }
299
300 module_init(codel_module_init)
301 module_exit(codel_module_exit)
302
303 MODULE_DESCRIPTION("Controlled Delay queue discipline");
304 MODULE_AUTHOR("Dave Taht");
305 MODULE_AUTHOR("Eric Dumazet");
306 MODULE_LICENSE("Dual BSD/GPL");