blob: cad8e791f28e060adb8d774d7c2c5e375c0ffe8f [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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>
Jiri Slaby1977f032007-10-18 23:40:25 -070017#include <linux/bitops.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070018#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>
Jarek Poplawski4db0acf32008-11-24 15:48:05 -080033#include <linux/rbtree.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090034#include <linux/slab.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#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
Eric Dumazet32f675b2015-07-02 15:57:19 +020069 * avbps and avpps are scaled by 2^5.
Eric Dumazet511e11e2009-05-18 19:26:37 -070070 * both values are reported as 32 bit unsigned values. bps can
71 overflow for fast links : max speed being 34360Mbit/sec
Linus Torvalds1da177e2005-04-16 15:20:36 -070072 * 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{
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -070083 struct list_head list;
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +000084 struct gnet_stats_basic_packed *bstats;
Eric Dumazet45203a32013-06-06 08:43:22 -070085 struct gnet_stats_rate_est64 *rate_est;
Linus Torvalds1da177e2005-04-16 15:20:36 -070086 spinlock_t *stats_lock;
Eric Dumazetedb09eb2016-06-06 09:37:16 -070087 seqcount_t *running;
Linus Torvalds1da177e2005-04-16 15:20:36 -070088 int ewma_log;
Eric Dumazet32f675b2015-07-02 15:57:19 +020089 u32 last_packets;
90 unsigned long avpps;
Linus Torvalds1da177e2005-04-16 15:20:36 -070091 u64 last_bytes;
Eric Dumazet511e11e2009-05-18 19:26:37 -070092 u64 avbps;
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -070093 struct rcu_head e_rcu;
Jarek Poplawski4db0acf32008-11-24 15:48:05 -080094 struct rb_node node;
John Fastabend22e0f8b2014-09-28 11:52:56 -070095 struct gnet_stats_basic_cpu __percpu *cpu_bstats;
96 struct rcu_head head;
Linus Torvalds1da177e2005-04-16 15:20:36 -070097};
98
99struct gen_estimator_head
100{
101 struct timer_list timer;
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700102 struct list_head list;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700103};
104
105static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
106
David S. Millerdeb3abf2008-08-18 22:32:10 -0700107/* Protects against NULL dereference */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700108static DEFINE_RWLOCK(est_lock);
109
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800110/* Protects against soft lockup during large deletion */
111static struct rb_root est_root = RB_ROOT;
Eric Dumazetae638c42010-06-08 23:39:10 +0000112static DEFINE_SPINLOCK(est_tree_lock);
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800113
Linus Torvalds1da177e2005-04-16 15:20:36 -0700114static void est_timer(unsigned long arg)
115{
116 int idx = (int)arg;
117 struct gen_estimator *e;
118
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700119 rcu_read_lock();
120 list_for_each_entry_rcu(e, &elist[idx].list, list) {
John Fastabend22e0f8b2014-09-28 11:52:56 -0700121 struct gnet_stats_basic_packed b = {0};
Eric Dumazet32f675b2015-07-02 15:57:19 +0200122 unsigned long rate;
Eric Dumazet511e11e2009-05-18 19:26:37 -0700123 u64 brate;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700124
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700125 if (e->stats_lock)
126 spin_lock(e->stats_lock);
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700127 read_lock(&est_lock);
128 if (e->bstats == NULL)
129 goto skip;
130
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700131 __gnet_stats_copy_basic(e->running, &b, e->cpu_bstats, e->bstats);
John Fastabend22e0f8b2014-09-28 11:52:56 -0700132
133 brate = (b.bytes - e->last_bytes)<<(7 - idx);
134 e->last_bytes = b.bytes;
Jarek Poplawskia1dcb662009-05-25 22:47:01 -0700135 e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700136 WRITE_ONCE(e->rate_est->bps, (e->avbps + 0xF) >> 5);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700137
Eric Dumazet32f675b2015-07-02 15:57:19 +0200138 rate = b.packets - e->last_packets;
139 rate <<= (7 - idx);
John Fastabend22e0f8b2014-09-28 11:52:56 -0700140 e->last_packets = b.packets;
Jarek Poplawskia1dcb662009-05-25 22:47:01 -0700141 e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700142 WRITE_ONCE(e->rate_est->pps, (e->avpps + 0xF) >> 5);
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700143skip:
144 read_unlock(&est_lock);
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700145 if (e->stats_lock)
146 spin_unlock(e->stats_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700147 }
148
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700149 if (!list_empty(&elist[idx].list))
Eric Dumazet789675e2008-01-03 20:40:01 -0800150 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700151 rcu_read_unlock();
Linus Torvalds1da177e2005-04-16 15:20:36 -0700152}
153
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800154static void gen_add_node(struct gen_estimator *est)
155{
156 struct rb_node **p = &est_root.rb_node, *parent = NULL;
157
158 while (*p) {
159 struct gen_estimator *e;
160
161 parent = *p;
162 e = rb_entry(parent, struct gen_estimator, node);
163
164 if (est->bstats > e->bstats)
165 p = &parent->rb_right;
166 else
167 p = &parent->rb_left;
168 }
169 rb_link_node(&est->node, parent, p);
170 rb_insert_color(&est->node, &est_root);
171}
172
Jarek Poplawski244e6c22008-11-26 15:24:32 -0800173static
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +0000174struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats,
Eric Dumazet45203a32013-06-06 08:43:22 -0700175 const struct gnet_stats_rate_est64 *rate_est)
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800176{
177 struct rb_node *p = est_root.rb_node;
178
179 while (p) {
180 struct gen_estimator *e;
181
182 e = rb_entry(p, struct gen_estimator, node);
183
184 if (bstats > e->bstats)
185 p = p->rb_right;
186 else if (bstats < e->bstats || rate_est != e->rate_est)
187 p = p->rb_left;
188 else
189 return e;
190 }
191 return NULL;
192}
193
Linus Torvalds1da177e2005-04-16 15:20:36 -0700194/**
195 * gen_new_estimator - create a new rate estimator
196 * @bstats: basic statistics
Luis de Bethencourte9fc2f02016-03-19 21:31:38 +0000197 * @cpu_bstats: bstats per cpu
Linus Torvalds1da177e2005-04-16 15:20:36 -0700198 * @rate_est: rate estimator statistics
199 * @stats_lock: statistics lock
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700200 * @running: qdisc running seqcount
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201 * @opt: rate estimator configuration TLV
202 *
203 * Creates a new rate estimator with &bstats as source and &rate_est
204 * as destination. A new timer with the interval specified in the
205 * configuration TLV is created. Upon each interval, the latest statistics
206 * will be read from &bstats and the estimated rate will be stored in
Masanari Iidae793c0f2014-09-04 23:44:36 +0900207 * &rate_est with the statistics lock grabbed during this period.
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +0900208 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700209 * Returns 0 on success or a negative error code.
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700210 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700211 */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +0000212int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
John Fastabend22e0f8b2014-09-28 11:52:56 -0700213 struct gnet_stats_basic_cpu __percpu *cpu_bstats,
Eric Dumazet45203a32013-06-06 08:43:22 -0700214 struct gnet_stats_rate_est64 *rate_est,
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700215 spinlock_t *stats_lock,
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700216 seqcount_t *running,
Patrick McHardy1e904742008-01-22 22:11:17 -0800217 struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700218{
219 struct gen_estimator *est;
Patrick McHardy1e904742008-01-22 22:11:17 -0800220 struct gnet_estimator *parm = nla_data(opt);
John Fastabend22e0f8b2014-09-28 11:52:56 -0700221 struct gnet_stats_basic_packed b = {0};
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700222 int idx;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700223
Patrick McHardy1e904742008-01-22 22:11:17 -0800224 if (nla_len(opt) < sizeof(*parm))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700225 return -EINVAL;
226
227 if (parm->interval < -2 || parm->interval > 3)
228 return -EINVAL;
229
Andrew Morton77d04bd2006-04-07 14:52:59 -0700230 est = kzalloc(sizeof(*est), GFP_KERNEL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700231 if (est == NULL)
232 return -ENOBUFS;
233
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700234 __gnet_stats_copy_basic(running, &b, cpu_bstats, bstats);
John Fastabend22e0f8b2014-09-28 11:52:56 -0700235
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700236 idx = parm->interval + 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700237 est->bstats = bstats;
238 est->rate_est = rate_est;
239 est->stats_lock = stats_lock;
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700240 est->running = running;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700241 est->ewma_log = parm->ewma_log;
John Fastabend22e0f8b2014-09-28 11:52:56 -0700242 est->last_bytes = b.bytes;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700243 est->avbps = rate_est->bps<<5;
John Fastabend22e0f8b2014-09-28 11:52:56 -0700244 est->last_packets = b.packets;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700245 est->avpps = rate_est->pps<<10;
John Fastabend22e0f8b2014-09-28 11:52:56 -0700246 est->cpu_bstats = cpu_bstats;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700247
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700248 spin_lock_bh(&est_tree_lock);
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700249 if (!elist[idx].timer.function) {
250 INIT_LIST_HEAD(&elist[idx].list);
251 setup_timer(&elist[idx].timer, est_timer, idx);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700252 }
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700253
254 if (list_empty(&elist[idx].list))
Eric Dumazet789675e2008-01-03 20:40:01 -0800255 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700256
257 list_add_rcu(&est->list, &elist[idx].list);
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800258 gen_add_node(est);
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700259 spin_unlock_bh(&est_tree_lock);
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800260
Linus Torvalds1da177e2005-04-16 15:20:36 -0700261 return 0;
262}
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800263EXPORT_SYMBOL(gen_new_estimator);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700264
265/**
266 * gen_kill_estimator - remove a rate estimator
267 * @bstats: basic statistics
268 * @rate_est: rate estimator statistics
269 *
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800270 * Removes the rate estimator specified by &bstats and &rate_est.
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700271 *
Eric Dumazetc7de2cf2010-06-09 02:09:23 +0000272 * Note : Caller should respect an RCU grace period before freeing stats_lock
Linus Torvalds1da177e2005-04-16 15:20:36 -0700273 */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +0000274void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
Eric Dumazet45203a32013-06-06 08:43:22 -0700275 struct gnet_stats_rate_est64 *rate_est)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700276{
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800277 struct gen_estimator *e;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700278
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700279 spin_lock_bh(&est_tree_lock);
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800280 while ((e = gen_find_node(bstats, rate_est))) {
281 rb_erase(&e->node, &est_root);
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700282
stephen hemminger9ca7f872010-09-08 09:16:28 +0000283 write_lock(&est_lock);
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800284 e->bstats = NULL;
stephen hemminger9ca7f872010-09-08 09:16:28 +0000285 write_unlock(&est_lock);
Ranko Zivojnovic0929c2d2007-07-16 18:28:32 -0700286
Jarek Poplawski4db0acf32008-11-24 15:48:05 -0800287 list_del_rcu(&e->list);
Lai Jiangshandad178f2011-03-18 11:43:26 +0800288 kfree_rcu(e, e_rcu);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289 }
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700290 spin_unlock_bh(&est_tree_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700291}
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800292EXPORT_SYMBOL(gen_kill_estimator);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700293
294/**
Jarek Poplawski96750162008-01-21 02:36:02 -0800295 * gen_replace_estimator - replace rate estimator configuration
Linus Torvalds1da177e2005-04-16 15:20:36 -0700296 * @bstats: basic statistics
Luis de Bethencourte9fc2f02016-03-19 21:31:38 +0000297 * @cpu_bstats: bstats per cpu
Linus Torvalds1da177e2005-04-16 15:20:36 -0700298 * @rate_est: rate estimator statistics
299 * @stats_lock: statistics lock
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700300 * @running: qdisc running seqcount (might be NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700301 * @opt: rate estimator configuration TLV
302 *
303 * Replaces the configuration of a rate estimator by calling
304 * gen_kill_estimator() and gen_new_estimator().
YOSHIFUJI Hideaki4ec93ed2007-02-09 23:24:36 +0900305 *
Linus Torvalds1da177e2005-04-16 15:20:36 -0700306 * Returns 0 on success or a negative error code.
307 */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +0000308int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
John Fastabend22e0f8b2014-09-28 11:52:56 -0700309 struct gnet_stats_basic_cpu __percpu *cpu_bstats,
Eric Dumazet45203a32013-06-06 08:43:22 -0700310 struct gnet_stats_rate_est64 *rate_est,
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700311 spinlock_t *stats_lock,
312 seqcount_t *running, struct nlattr *opt)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700313{
Jarek Poplawski96750162008-01-21 02:36:02 -0800314 gen_kill_estimator(bstats, rate_est);
Eric Dumazetedb09eb2016-06-06 09:37:16 -0700315 return gen_new_estimator(bstats, cpu_bstats, rate_est, stats_lock, running, opt);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700316}
Linus Torvalds1da177e2005-04-16 15:20:36 -0700317EXPORT_SYMBOL(gen_replace_estimator);
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800318
319/**
320 * gen_estimator_active - test if estimator is currently in use
Jarek Poplawski244e6c22008-11-26 15:24:32 -0800321 * @bstats: basic statistics
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800322 * @rate_est: rate estimator statistics
323 *
Jarek Poplawski244e6c22008-11-26 15:24:32 -0800324 * Returns true if estimator is active, and false if not.
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800325 */
Eric Dumazetc1a8f1f2009-08-16 09:36:49 +0000326bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
Eric Dumazet45203a32013-06-06 08:43:22 -0700327 const struct gnet_stats_rate_est64 *rate_est)
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800328{
Eric Dumazetae638c42010-06-08 23:39:10 +0000329 bool res;
330
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800331 ASSERT_RTNL();
332
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700333 spin_lock_bh(&est_tree_lock);
Eric Dumazetae638c42010-06-08 23:39:10 +0000334 res = gen_find_node(bstats, rate_est) != NULL;
Jarek Poplawski0b5d4042010-09-02 13:22:11 -0700335 spin_unlock_bh(&est_tree_lock);
Eric Dumazetae638c42010-06-08 23:39:10 +0000336
337 return res;
Stephen Hemmingerc1b56872008-11-25 21:14:06 -0800338}
339EXPORT_SYMBOL(gen_estimator_active);