Branch data Line data Source code
1 : : /*
2 : : * net/sched/gen_estimator.c Simple rate estimator.
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 : : * Changes:
12 : : * Jamal Hadi Salim - moved it to net/core and reshulfed
13 : : * names to make it usable in general net subsystem.
14 : : */
15 : :
16 : : #include <asm/uaccess.h>
17 : : #include <linux/bitops.h>
18 : : #include <linux/module.h>
19 : : #include <linux/types.h>
20 : : #include <linux/kernel.h>
21 : : #include <linux/jiffies.h>
22 : : #include <linux/string.h>
23 : : #include <linux/mm.h>
24 : : #include <linux/socket.h>
25 : : #include <linux/sockios.h>
26 : : #include <linux/in.h>
27 : : #include <linux/errno.h>
28 : : #include <linux/interrupt.h>
29 : : #include <linux/netdevice.h>
30 : : #include <linux/skbuff.h>
31 : : #include <linux/rtnetlink.h>
32 : : #include <linux/init.h>
33 : : #include <linux/rbtree.h>
34 : : #include <linux/slab.h>
35 : : #include <net/sock.h>
36 : : #include <net/gen_stats.h>
37 : :
38 : : /*
39 : : This code is NOT intended to be used for statistics collection,
40 : : its purpose is to provide a base for statistical multiplexing
41 : : for controlled load service.
42 : : If you need only statistics, run a user level daemon which
43 : : periodically reads byte counters.
44 : :
45 : : Unfortunately, rate estimation is not a very easy task.
46 : : F.e. I did not find a simple way to estimate the current peak rate
47 : : and even failed to formulate the problem 8)8)
48 : :
49 : : So I preferred not to built an estimator into the scheduler,
50 : : but run this task separately.
51 : : Ideally, it should be kernel thread(s), but for now it runs
52 : : from timers, which puts apparent top bounds on the number of rated
53 : : flows, has minimal overhead on small, but is enough
54 : : to handle controlled load service, sets of aggregates.
55 : :
56 : : We measure rate over A=(1<<interval) seconds and evaluate EWMA:
57 : :
58 : : avrate = avrate*(1-W) + rate*W
59 : :
60 : : where W is chosen as negative power of 2: W = 2^(-ewma_log)
61 : :
62 : : The resulting time constant is:
63 : :
64 : : T = A/(-ln(1-W))
65 : :
66 : :
67 : : NOTES.
68 : :
69 : : * avbps is scaled by 2^5, avpps is scaled by 2^10.
70 : : * both values are reported as 32 bit unsigned values. bps can
71 : : overflow for fast links : max speed being 34360Mbit/sec
72 : : * Minimal interval is HZ/4=250msec (it is the greatest common divisor
73 : : for HZ=100 and HZ=1024 8)), maximal interval
74 : : is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
75 : : are too expensive, longer ones can be implemented
76 : : at user level painlessly.
77 : : */
78 : :
79 : : #define EST_MAX_INTERVAL 5
80 : :
81 : : struct gen_estimator
82 : : {
83 : : struct list_head list;
84 : : struct gnet_stats_basic_packed *bstats;
85 : : struct gnet_stats_rate_est64 *rate_est;
86 : : spinlock_t *stats_lock;
87 : : int ewma_log;
88 : : u64 last_bytes;
89 : : u64 avbps;
90 : : u32 last_packets;
91 : : u32 avpps;
92 : : struct rcu_head e_rcu;
93 : : struct rb_node node;
94 : : };
95 : :
96 : : struct gen_estimator_head
97 : : {
98 : : struct timer_list timer;
99 : : struct list_head list;
100 : : };
101 : :
102 : : static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
103 : :
104 : : /* Protects against NULL dereference */
105 : : static DEFINE_RWLOCK(est_lock);
106 : :
107 : : /* Protects against soft lockup during large deletion */
108 : : static struct rb_root est_root = RB_ROOT;
109 : : static DEFINE_SPINLOCK(est_tree_lock);
110 : :
111 : 0 : static void est_timer(unsigned long arg)
112 : : {
113 : 0 : int idx = (int)arg;
114 : : struct gen_estimator *e;
115 : :
116 : : rcu_read_lock();
117 [ # # ]: 0 : list_for_each_entry_rcu(e, &elist[idx].list, list) {
118 : : u64 nbytes;
119 : : u64 brate;
120 : : u32 npackets;
121 : : u32 rate;
122 : :
123 : 0 : spin_lock(e->stats_lock);
124 : 0 : read_lock(&est_lock);
125 [ # # ]: 0 : if (e->bstats == NULL)
126 : : goto skip;
127 : :
128 : 0 : nbytes = e->bstats->bytes;
129 : 0 : npackets = e->bstats->packets;
130 : 0 : brate = (nbytes - e->last_bytes)<<(7 - idx);
131 : 0 : e->last_bytes = nbytes;
132 : 0 : e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
133 : 0 : e->rate_est->bps = (e->avbps+0xF)>>5;
134 : :
135 : 0 : rate = (npackets - e->last_packets)<<(12 - idx);
136 : 0 : e->last_packets = npackets;
137 : 0 : e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
138 : 0 : e->rate_est->pps = (e->avpps+0x1FF)>>10;
139 : : skip:
140 : : read_unlock(&est_lock);
141 : 0 : spin_unlock(e->stats_lock);
142 : : }
143 : :
144 [ # # ]: 0 : if (!list_empty(&elist[idx].list))
145 : 0 : mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
146 : : rcu_read_unlock();
147 : 0 : }
148 : :
149 : 0 : static void gen_add_node(struct gen_estimator *est)
150 : : {
151 : : struct rb_node **p = &est_root.rb_node, *parent = NULL;
152 : :
153 [ # # ]: 0 : while (*p) {
154 : : struct gen_estimator *e;
155 : :
156 : : parent = *p;
157 : : e = rb_entry(parent, struct gen_estimator, node);
158 : :
159 [ # # ]: 0 : if (est->bstats > e->bstats)
160 : 0 : p = &parent->rb_right;
161 : : else
162 : 0 : p = &parent->rb_left;
163 : : }
164 : 0 : rb_link_node(&est->node, parent, p);
165 : 0 : rb_insert_color(&est->node, &est_root);
166 : 0 : }
167 : :
168 : : static
169 : : struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats,
170 : : const struct gnet_stats_rate_est64 *rate_est)
171 : : {
172 : 0 : struct rb_node *p = est_root.rb_node;
173 : :
174 [ # # ][ # # ]: 0 : while (p) {
175 : : struct gen_estimator *e;
176 : :
177 : 0 : e = rb_entry(p, struct gen_estimator, node);
178 : :
179 [ # # ][ # # ]: 0 : if (bstats > e->bstats)
180 : 0 : p = p->rb_right;
181 [ # # ][ # # ]: 0 : else if (bstats < e->bstats || rate_est != e->rate_est)
[ # # ][ # # ]
182 : 0 : p = p->rb_left;
183 : : else
184 : : return e;
185 : : }
186 : : return NULL;
187 : : }
188 : :
189 : : /**
190 : : * gen_new_estimator - create a new rate estimator
191 : : * @bstats: basic statistics
192 : : * @rate_est: rate estimator statistics
193 : : * @stats_lock: statistics lock
194 : : * @opt: rate estimator configuration TLV
195 : : *
196 : : * Creates a new rate estimator with &bstats as source and &rate_est
197 : : * as destination. A new timer with the interval specified in the
198 : : * configuration TLV is created. Upon each interval, the latest statistics
199 : : * will be read from &bstats and the estimated rate will be stored in
200 : : * &rate_est with the statistics lock grabed during this period.
201 : : *
202 : : * Returns 0 on success or a negative error code.
203 : : *
204 : : */
205 : 0 : int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
206 : : struct gnet_stats_rate_est64 *rate_est,
207 : : spinlock_t *stats_lock,
208 : 0 : struct nlattr *opt)
209 : : {
210 : : struct gen_estimator *est;
211 : : struct gnet_estimator *parm = nla_data(opt);
212 : : int idx;
213 : :
214 [ # # ]: 0 : if (nla_len(opt) < sizeof(*parm))
215 : : return -EINVAL;
216 : :
217 [ # # ]: 0 : if (parm->interval < -2 || parm->interval > 3)
218 : : return -EINVAL;
219 : :
220 : : est = kzalloc(sizeof(*est), GFP_KERNEL);
221 [ # # ]: 0 : if (est == NULL)
222 : : return -ENOBUFS;
223 : :
224 : 0 : idx = parm->interval + 2;
225 : 0 : est->bstats = bstats;
226 : 0 : est->rate_est = rate_est;
227 : 0 : est->stats_lock = stats_lock;
228 : 0 : est->ewma_log = parm->ewma_log;
229 : 0 : est->last_bytes = bstats->bytes;
230 : 0 : est->avbps = rate_est->bps<<5;
231 : 0 : est->last_packets = bstats->packets;
232 : 0 : est->avpps = rate_est->pps<<10;
233 : :
234 : : spin_lock_bh(&est_tree_lock);
235 [ # # ]: 0 : if (!elist[idx].timer.function) {
236 : 0 : INIT_LIST_HEAD(&elist[idx].list);
237 : 0 : setup_timer(&elist[idx].timer, est_timer, idx);
238 : : }
239 : :
240 [ # # ]: 0 : if (list_empty(&elist[idx].list))
241 : 0 : mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
242 : :
243 : 0 : list_add_rcu(&est->list, &elist[idx].list);
244 : 0 : gen_add_node(est);
245 : : spin_unlock_bh(&est_tree_lock);
246 : :
247 : 0 : return 0;
248 : : }
249 : : EXPORT_SYMBOL(gen_new_estimator);
250 : :
251 : : /**
252 : : * gen_kill_estimator - remove a rate estimator
253 : : * @bstats: basic statistics
254 : : * @rate_est: rate estimator statistics
255 : : *
256 : : * Removes the rate estimator specified by &bstats and &rate_est.
257 : : *
258 : : * Note : Caller should respect an RCU grace period before freeing stats_lock
259 : : */
260 : 0 : void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
261 : : struct gnet_stats_rate_est64 *rate_est)
262 : : {
263 : : struct gen_estimator *e;
264 : :
265 : : spin_lock_bh(&est_tree_lock);
266 [ # # ]: 0 : while ((e = gen_find_node(bstats, rate_est))) {
267 : 0 : rb_erase(&e->node, &est_root);
268 : :
269 : 0 : write_lock(&est_lock);
270 : 0 : e->bstats = NULL;
271 : : write_unlock(&est_lock);
272 : :
273 : : list_del_rcu(&e->list);
274 : 0 : kfree_rcu(e, e_rcu);
275 : : }
276 : : spin_unlock_bh(&est_tree_lock);
277 : 0 : }
278 : : EXPORT_SYMBOL(gen_kill_estimator);
279 : :
280 : : /**
281 : : * gen_replace_estimator - replace rate estimator configuration
282 : : * @bstats: basic statistics
283 : : * @rate_est: rate estimator statistics
284 : : * @stats_lock: statistics lock
285 : : * @opt: rate estimator configuration TLV
286 : : *
287 : : * Replaces the configuration of a rate estimator by calling
288 : : * gen_kill_estimator() and gen_new_estimator().
289 : : *
290 : : * Returns 0 on success or a negative error code.
291 : : */
292 : 0 : int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
293 : : struct gnet_stats_rate_est64 *rate_est,
294 : : spinlock_t *stats_lock, struct nlattr *opt)
295 : : {
296 : 0 : gen_kill_estimator(bstats, rate_est);
297 : 0 : return gen_new_estimator(bstats, rate_est, stats_lock, opt);
298 : : }
299 : : EXPORT_SYMBOL(gen_replace_estimator);
300 : :
301 : : /**
302 : : * gen_estimator_active - test if estimator is currently in use
303 : : * @bstats: basic statistics
304 : : * @rate_est: rate estimator statistics
305 : : *
306 : : * Returns true if estimator is active, and false if not.
307 : : */
308 : 0 : bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
309 : : const struct gnet_stats_rate_est64 *rate_est)
310 : : {
311 : : bool res;
312 : :
313 [ # # ]: 0 : ASSERT_RTNL();
314 : :
315 : : spin_lock_bh(&est_tree_lock);
316 : 0 : res = gen_find_node(bstats, rate_est) != NULL;
317 : : spin_unlock_bh(&est_tree_lock);
318 : :
319 : 0 : return res;
320 : : }
321 : : EXPORT_SYMBOL(gen_estimator_active);
|
