2 * net/sched/gen_estimator.c Simple rate estimator.
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 * Jamal Hadi Salim - moved it to net/core and reshulfed
13 * names to make it usable in general net subsystem.
16 #include <asm/uaccess.h>
17 #include <asm/system.h>
18 #include <linux/bitops.h>
19 #include <linux/module.h>
20 #include <linux/types.h>
21 #include <linux/kernel.h>
22 #include <linux/jiffies.h>
23 #include <linux/string.h>
25 #include <linux/socket.h>
26 #include <linux/sockios.h>
28 #include <linux/errno.h>
29 #include <linux/interrupt.h>
30 #include <linux/netdevice.h>
31 #include <linux/skbuff.h>
32 #include <linux/rtnetlink.h>
33 #include <linux/init.h>
35 #include <net/gen_stats.h>
38 This code is NOT intended to be used for statistics collection,
39 its purpose is to provide a base for statistical multiplexing
40 for controlled load service.
41 If you need only statistics, run a user level daemon which
42 periodically reads byte counters.
44 Unfortunately, rate estimation is not a very easy task.
45 F.e. I did not find a simple way to estimate the current peak rate
46 and even failed to formulate the problem 8)8)
48 So I preferred not to built an estimator into the scheduler,
49 but run this task separately.
50 Ideally, it should be kernel thread(s), but for now it runs
51 from timers, which puts apparent top bounds on the number of rated
52 flows, has minimal overhead on small, but is enough
53 to handle controlled load service, sets of aggregates.
55 We measure rate over A=(1<<interval) seconds and evaluate EWMA:
57 avrate = avrate*(1-W) + rate*W
59 where W is chosen as negative power of 2: W = 2^(-ewma_log)
61 The resulting time constant is:
68 * The stored value for avbps is scaled by 2^5, so that maximal
69 rate is ~1Gbit, avpps is scaled by 2^10.
71 * Minimal interval is HZ/4=250msec (it is the greatest common divisor
72 for HZ=100 and HZ=1024 8)), maximal interval
73 is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
74 are too expensive, longer ones can be implemented
75 at user level painlessly.
78 #define EST_MAX_INTERVAL 5
82 struct list_head list
;
83 struct gnet_stats_basic
*bstats
;
84 struct gnet_stats_rate_est
*rate_est
;
85 spinlock_t
*stats_lock
;
91 struct rcu_head e_rcu
;
94 struct gen_estimator_head
96 struct timer_list timer
;
97 struct list_head list
;
100 static struct gen_estimator_head elist
[EST_MAX_INTERVAL
+1];
102 /* Protects against NULL dereference and RCU write-side */
103 static DEFINE_RWLOCK(est_lock
);
105 static void est_timer(unsigned long arg
)
108 struct gen_estimator
*e
;
111 list_for_each_entry_rcu(e
, &elist
[idx
].list
, list
) {
116 spin_lock(e
->stats_lock
);
117 read_lock(&est_lock
);
118 if (e
->bstats
== NULL
)
121 nbytes
= e
->bstats
->bytes
;
122 npackets
= e
->bstats
->packets
;
123 rate
= (nbytes
- e
->last_bytes
)<<(7 - idx
);
124 e
->last_bytes
= nbytes
;
125 e
->avbps
+= ((long)rate
- (long)e
->avbps
) >> e
->ewma_log
;
126 e
->rate_est
->bps
= (e
->avbps
+0xF)>>5;
128 rate
= (npackets
- e
->last_packets
)<<(12 - idx
);
129 e
->last_packets
= npackets
;
130 e
->avpps
+= ((long)rate
- (long)e
->avpps
) >> e
->ewma_log
;
131 e
->rate_est
->pps
= (e
->avpps
+0x1FF)>>10;
133 read_unlock(&est_lock
);
134 spin_unlock(e
->stats_lock
);
137 if (!list_empty(&elist
[idx
].list
))
138 mod_timer(&elist
[idx
].timer
, jiffies
+ ((HZ
/4) << idx
));
143 * gen_new_estimator - create a new rate estimator
144 * @bstats: basic statistics
145 * @rate_est: rate estimator statistics
146 * @stats_lock: statistics lock
147 * @opt: rate estimator configuration TLV
149 * Creates a new rate estimator with &bstats as source and &rate_est
150 * as destination. A new timer with the interval specified in the
151 * configuration TLV is created. Upon each interval, the latest statistics
152 * will be read from &bstats and the estimated rate will be stored in
153 * &rate_est with the statistics lock grabed during this period.
155 * Returns 0 on success or a negative error code.
157 * NOTE: Called under rtnl_mutex
159 int gen_new_estimator(struct gnet_stats_basic
*bstats
,
160 struct gnet_stats_rate_est
*rate_est
,
161 spinlock_t
*stats_lock
,
164 struct gen_estimator
*est
;
165 struct gnet_estimator
*parm
= nla_data(opt
);
168 if (nla_len(opt
) < sizeof(*parm
))
171 if (parm
->interval
< -2 || parm
->interval
> 3)
174 est
= kzalloc(sizeof(*est
), GFP_KERNEL
);
178 idx
= parm
->interval
+ 2;
179 est
->bstats
= bstats
;
180 est
->rate_est
= rate_est
;
181 est
->stats_lock
= stats_lock
;
182 est
->ewma_log
= parm
->ewma_log
;
183 est
->last_bytes
= bstats
->bytes
;
184 est
->avbps
= rate_est
->bps
<<5;
185 est
->last_packets
= bstats
->packets
;
186 est
->avpps
= rate_est
->pps
<<10;
188 write_lock_bh(&est_lock
);
189 if (!elist
[idx
].timer
.function
) {
190 INIT_LIST_HEAD(&elist
[idx
].list
);
191 setup_timer(&elist
[idx
].timer
, est_timer
, idx
);
194 if (list_empty(&elist
[idx
].list
))
195 mod_timer(&elist
[idx
].timer
, jiffies
+ ((HZ
/4) << idx
));
197 list_add_rcu(&est
->list
, &elist
[idx
].list
);
198 write_unlock_bh(&est_lock
);
202 static void __gen_kill_estimator(struct rcu_head
*head
)
204 struct gen_estimator
*e
= container_of(head
,
205 struct gen_estimator
, e_rcu
);
210 * gen_kill_estimator - remove a rate estimator
211 * @bstats: basic statistics
212 * @rate_est: rate estimator statistics
214 * Removes the rate estimator specified by &bstats and &rate_est
215 * and deletes the timer.
218 void gen_kill_estimator(struct gnet_stats_basic
*bstats
,
219 struct gnet_stats_rate_est
*rate_est
)
222 struct gen_estimator
*e
, *n
;
224 for (idx
=0; idx
<= EST_MAX_INTERVAL
; idx
++) {
226 /* Skip non initialized indexes */
227 if (!elist
[idx
].timer
.function
)
230 write_lock_bh(&est_lock
);
231 list_for_each_entry_safe(e
, n
, &elist
[idx
].list
, list
) {
232 if (e
->rate_est
!= rate_est
|| e
->bstats
!= bstats
)
237 list_del_rcu(&e
->list
);
238 call_rcu(&e
->e_rcu
, __gen_kill_estimator
);
240 write_unlock_bh(&est_lock
);
245 * gen_replace_estimator - replace rate estimator configuration
246 * @bstats: basic statistics
247 * @rate_est: rate estimator statistics
248 * @stats_lock: statistics lock
249 * @opt: rate estimator configuration TLV
251 * Replaces the configuration of a rate estimator by calling
252 * gen_kill_estimator() and gen_new_estimator().
254 * Returns 0 on success or a negative error code.
256 int gen_replace_estimator(struct gnet_stats_basic
*bstats
,
257 struct gnet_stats_rate_est
*rate_est
,
258 spinlock_t
*stats_lock
, struct nlattr
*opt
)
260 gen_kill_estimator(bstats
, rate_est
);
261 return gen_new_estimator(bstats
, rate_est
, stats_lock
, opt
);
265 EXPORT_SYMBOL(gen_kill_estimator
);
266 EXPORT_SYMBOL(gen_new_estimator
);
267 EXPORT_SYMBOL(gen_replace_estimator
);
This page took 0.041628 seconds and 6 git commands to generate.