Loading...
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
81struct 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
96struct gen_estimator_head
97{
98 struct timer_list timer;
99 struct list_head list;
100};
101
102static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
103
104/* Protects against NULL dereference */
105static DEFINE_RWLOCK(est_lock);
106
107/* Protects against soft lockup during large deletion */
108static struct rb_root est_root = RB_ROOT;
109static DEFINE_SPINLOCK(est_tree_lock);
110
111static void est_timer(unsigned long arg)
112{
113 int idx = (int)arg;
114 struct gen_estimator *e;
115
116 rcu_read_lock();
117 list_for_each_entry_rcu(e, &elist[idx].list, list) {
118 u64 nbytes;
119 u64 brate;
120 u32 npackets;
121 u32 rate;
122
123 spin_lock(e->stats_lock);
124 read_lock(&est_lock);
125 if (e->bstats == NULL)
126 goto skip;
127
128 nbytes = e->bstats->bytes;
129 npackets = e->bstats->packets;
130 brate = (nbytes - e->last_bytes)<<(7 - idx);
131 e->last_bytes = nbytes;
132 e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
133 e->rate_est->bps = (e->avbps+0xF)>>5;
134
135 rate = (npackets - e->last_packets)<<(12 - idx);
136 e->last_packets = npackets;
137 e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
138 e->rate_est->pps = (e->avpps+0x1FF)>>10;
139skip:
140 read_unlock(&est_lock);
141 spin_unlock(e->stats_lock);
142 }
143
144 if (!list_empty(&elist[idx].list))
145 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
146 rcu_read_unlock();
147}
148
149static void gen_add_node(struct gen_estimator *est)
150{
151 struct rb_node **p = &est_root.rb_node, *parent = NULL;
152
153 while (*p) {
154 struct gen_estimator *e;
155
156 parent = *p;
157 e = rb_entry(parent, struct gen_estimator, node);
158
159 if (est->bstats > e->bstats)
160 p = &parent->rb_right;
161 else
162 p = &parent->rb_left;
163 }
164 rb_link_node(&est->node, parent, p);
165 rb_insert_color(&est->node, &est_root);
166}
167
168static
169struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats,
170 const struct gnet_stats_rate_est64 *rate_est)
171{
172 struct rb_node *p = est_root.rb_node;
173
174 while (p) {
175 struct gen_estimator *e;
176
177 e = rb_entry(p, struct gen_estimator, node);
178
179 if (bstats > e->bstats)
180 p = p->rb_right;
181 else if (bstats < e->bstats || rate_est != e->rate_est)
182 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 */
205int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
206 struct gnet_stats_rate_est64 *rate_est,
207 spinlock_t *stats_lock,
208 struct nlattr *opt)
209{
210 struct gen_estimator *est;
211 struct gnet_estimator *parm = nla_data(opt);
212 int idx;
213
214 if (nla_len(opt) < sizeof(*parm))
215 return -EINVAL;
216
217 if (parm->interval < -2 || parm->interval > 3)
218 return -EINVAL;
219
220 est = kzalloc(sizeof(*est), GFP_KERNEL);
221 if (est == NULL)
222 return -ENOBUFS;
223
224 idx = parm->interval + 2;
225 est->bstats = bstats;
226 est->rate_est = rate_est;
227 est->stats_lock = stats_lock;
228 est->ewma_log = parm->ewma_log;
229 est->last_bytes = bstats->bytes;
230 est->avbps = rate_est->bps<<5;
231 est->last_packets = bstats->packets;
232 est->avpps = rate_est->pps<<10;
233
234 spin_lock_bh(&est_tree_lock);
235 if (!elist[idx].timer.function) {
236 INIT_LIST_HEAD(&elist[idx].list);
237 setup_timer(&elist[idx].timer, est_timer, idx);
238 }
239
240 if (list_empty(&elist[idx].list))
241 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
242
243 list_add_rcu(&est->list, &elist[idx].list);
244 gen_add_node(est);
245 spin_unlock_bh(&est_tree_lock);
246
247 return 0;
248}
249EXPORT_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 */
260void 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 while ((e = gen_find_node(bstats, rate_est))) {
267 rb_erase(&e->node, &est_root);
268
269 write_lock(&est_lock);
270 e->bstats = NULL;
271 write_unlock(&est_lock);
272
273 list_del_rcu(&e->list);
274 kfree_rcu(e, e_rcu);
275 }
276 spin_unlock_bh(&est_tree_lock);
277}
278EXPORT_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 */
292int 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 gen_kill_estimator(bstats, rate_est);
297 return gen_new_estimator(bstats, rate_est, stats_lock, opt);
298}
299EXPORT_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 */
308bool 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 ASSERT_RTNL();
314
315 spin_lock_bh(&est_tree_lock);
316 res = gen_find_node(bstats, rate_est) != NULL;
317 spin_unlock_bh(&est_tree_lock);
318
319 return res;
320}
321EXPORT_SYMBOL(gen_estimator_active);
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 * Eric Dumazet <edumazet@google.com>
11 *
12 * Changes:
13 * Jamal Hadi Salim - moved it to net/core and reshulfed
14 * names to make it usable in general net subsystem.
15 */
16
17#include <linux/uaccess.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>
24#include <linux/mm.h>
25#include <linux/socket.h>
26#include <linux/sockios.h>
27#include <linux/in.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>
34#include <linux/slab.h>
35#include <linux/seqlock.h>
36#include <net/sock.h>
37#include <net/gen_stats.h>
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
46struct net_rate_estimator {
47 struct gnet_stats_basic_packed *bstats;
48 spinlock_t *stats_lock;
49 seqcount_t *running;
50 struct gnet_stats_basic_cpu __percpu *cpu_bstats;
51 u8 ewma_log;
52 u8 intvl_log; /* period : (250ms << intvl_log) */
53
54 seqcount_t seq;
55 u32 last_packets;
56 u64 last_bytes;
57
58 u64 avpps;
59 u64 avbps;
60
61 unsigned long next_jiffies;
62 struct timer_list timer;
63 struct rcu_head rcu;
64};
65
66static void est_fetch_counters(struct net_rate_estimator *e,
67 struct gnet_stats_basic_packed *b)
68{
69 if (e->stats_lock)
70 spin_lock(e->stats_lock);
71
72 __gnet_stats_copy_basic(e->running, b, e->cpu_bstats, e->bstats);
73
74 if (e->stats_lock)
75 spin_unlock(e->stats_lock);
76
77}
78
79static void est_timer(unsigned long arg)
80{
81 struct net_rate_estimator *est = (struct net_rate_estimator *)arg;
82 struct gnet_stats_basic_packed b;
83 u64 rate, brate;
84
85 est_fetch_counters(est, &b);
86 brate = (b.bytes - est->last_bytes) << (8 - est->ewma_log);
87 brate -= (est->avbps >> est->ewma_log);
88
89 rate = (u64)(b.packets - est->last_packets) << (8 - est->ewma_log);
90 rate -= (est->avpps >> est->ewma_log);
91
92 write_seqcount_begin(&est->seq);
93 est->avbps += brate;
94 est->avpps += rate;
95 write_seqcount_end(&est->seq);
96
97 est->last_bytes = b.bytes;
98 est->last_packets = b.packets;
99
100 est->next_jiffies += ((HZ/4) << est->intvl_log);
101
102 if (unlikely(time_after_eq(jiffies, est->next_jiffies))) {
103 /* Ouch... timer was delayed. */
104 est->next_jiffies = jiffies + 1;
105 }
106 mod_timer(&est->timer, est->next_jiffies);
107}
108
109/**
110 * gen_new_estimator - create a new rate estimator
111 * @bstats: basic statistics
112 * @cpu_bstats: bstats per cpu
113 * @rate_est: rate estimator statistics
114 * @stats_lock: statistics lock
115 * @running: qdisc running seqcount
116 * @opt: rate estimator configuration TLV
117 *
118 * Creates a new rate estimator with &bstats as source and &rate_est
119 * as destination. A new timer with the interval specified in the
120 * configuration TLV is created. Upon each interval, the latest statistics
121 * will be read from &bstats and the estimated rate will be stored in
122 * &rate_est with the statistics lock grabbed during this period.
123 *
124 * Returns 0 on success or a negative error code.
125 *
126 */
127int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
128 struct gnet_stats_basic_cpu __percpu *cpu_bstats,
129 struct net_rate_estimator __rcu **rate_est,
130 spinlock_t *stats_lock,
131 seqcount_t *running,
132 struct nlattr *opt)
133{
134 struct gnet_estimator *parm = nla_data(opt);
135 struct net_rate_estimator *old, *est;
136 struct gnet_stats_basic_packed b;
137 int intvl_log;
138
139 if (nla_len(opt) < sizeof(*parm))
140 return -EINVAL;
141
142 /* allowed timer periods are :
143 * -2 : 250ms, -1 : 500ms, 0 : 1 sec
144 * 1 : 2 sec, 2 : 4 sec, 3 : 8 sec
145 */
146 if (parm->interval < -2 || parm->interval > 3)
147 return -EINVAL;
148
149 est = kzalloc(sizeof(*est), GFP_KERNEL);
150 if (!est)
151 return -ENOBUFS;
152
153 seqcount_init(&est->seq);
154 intvl_log = parm->interval + 2;
155 est->bstats = bstats;
156 est->stats_lock = stats_lock;
157 est->running = running;
158 est->ewma_log = parm->ewma_log;
159 est->intvl_log = intvl_log;
160 est->cpu_bstats = cpu_bstats;
161
162 est_fetch_counters(est, &b);
163 est->last_bytes = b.bytes;
164 est->last_packets = b.packets;
165 old = rcu_dereference_protected(*rate_est, 1);
166 if (old) {
167 del_timer_sync(&old->timer);
168 est->avbps = old->avbps;
169 est->avpps = old->avpps;
170 }
171
172 est->next_jiffies = jiffies + ((HZ/4) << intvl_log);
173 setup_timer(&est->timer, est_timer, (unsigned long)est);
174 mod_timer(&est->timer, est->next_jiffies);
175
176 rcu_assign_pointer(*rate_est, est);
177 if (old)
178 kfree_rcu(old, rcu);
179 return 0;
180}
181EXPORT_SYMBOL(gen_new_estimator);
182
183/**
184 * gen_kill_estimator - remove a rate estimator
185 * @rate_est: rate estimator
186 *
187 * Removes the rate estimator.
188 *
189 */
190void gen_kill_estimator(struct net_rate_estimator __rcu **rate_est)
191{
192 struct net_rate_estimator *est;
193
194 est = xchg((__force struct net_rate_estimator **)rate_est, NULL);
195 if (est) {
196 del_timer_sync(&est->timer);
197 kfree_rcu(est, rcu);
198 }
199}
200EXPORT_SYMBOL(gen_kill_estimator);
201
202/**
203 * gen_replace_estimator - replace rate estimator configuration
204 * @bstats: basic statistics
205 * @cpu_bstats: bstats per cpu
206 * @rate_est: rate estimator statistics
207 * @stats_lock: statistics lock
208 * @running: qdisc running seqcount (might be NULL)
209 * @opt: rate estimator configuration TLV
210 *
211 * Replaces the configuration of a rate estimator by calling
212 * gen_kill_estimator() and gen_new_estimator().
213 *
214 * Returns 0 on success or a negative error code.
215 */
216int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
217 struct gnet_stats_basic_cpu __percpu *cpu_bstats,
218 struct net_rate_estimator __rcu **rate_est,
219 spinlock_t *stats_lock,
220 seqcount_t *running, struct nlattr *opt)
221{
222 return gen_new_estimator(bstats, cpu_bstats, rate_est,
223 stats_lock, running, opt);
224}
225EXPORT_SYMBOL(gen_replace_estimator);
226
227/**
228 * gen_estimator_active - test if estimator is currently in use
229 * @rate_est: rate estimator
230 *
231 * Returns true if estimator is active, and false if not.
232 */
233bool gen_estimator_active(struct net_rate_estimator __rcu **rate_est)
234{
235 return !!rcu_access_pointer(*rate_est);
236}
237EXPORT_SYMBOL(gen_estimator_active);
238
239bool gen_estimator_read(struct net_rate_estimator __rcu **rate_est,
240 struct gnet_stats_rate_est64 *sample)
241{
242 struct net_rate_estimator *est;
243 unsigned seq;
244
245 rcu_read_lock();
246 est = rcu_dereference(*rate_est);
247 if (!est) {
248 rcu_read_unlock();
249 return false;
250 }
251
252 do {
253 seq = read_seqcount_begin(&est->seq);
254 sample->bps = est->avbps >> 8;
255 sample->pps = est->avpps >> 8;
256 } while (read_seqcount_retry(&est->seq, seq));
257
258 rcu_read_unlock();
259 return true;
260}
261EXPORT_SYMBOL(gen_estimator_read);