[net-next-2.6.git] / net / core / gen_estimator.c

/*
 * net/sched/gen_estimator.c	Simple rate estimator.
 *
 *		This program is free software; you can redistribute it and/or
 *		modify it under the terms of the GNU General Public License
 *		as published by the Free Software Foundation; either version
 *		2 of the License, or (at your option) any later version.
 *
 * Authors:	Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
 *
 * Changes:
 *              Jamal Hadi Salim - moved it to net/core and reshulfed
 *              names to make it usable in general net subsystem.
 */

#include <asm/uaccess.h>
#include <asm/system.h>
#include <linux/bitops.h>
#include <linux/module.h>
#include <linux/types.h>
#include <linux/kernel.h>
#include <linux/jiffies.h>
#include <linux/string.h>
#include <linux/mm.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/in.h>
#include <linux/errno.h>
#include <linux/interrupt.h>
#include <linux/netdevice.h>
#include <linux/skbuff.h>
#include <linux/rtnetlink.h>
#include <linux/init.h>
#include <linux/rbtree.h>
#include <linux/slab.h>
#include <net/sock.h>
#include <net/gen_stats.h>

/*
   This code is NOT intended to be used for statistics collection,
   its purpose is to provide a base for statistical multiplexing
   for controlled load service.
   If you need only statistics, run a user level daemon which
   periodically reads byte counters.

   Unfortunately, rate estimation is not a very easy task.
   F.e. I did not find a simple way to estimate the current peak rate
   and even failed to formulate the problem 8)8)

   So I preferred not to built an estimator into the scheduler,
   but run this task separately.
   Ideally, it should be kernel thread(s), but for now it runs
   from timers, which puts apparent top bounds on the number of rated
   flows, has minimal overhead on small, but is enough
   to handle controlled load service, sets of aggregates.

   We measure rate over A=(1<<interval) seconds and evaluate EWMA:

   avrate = avrate*(1-W) + rate*W

   where W is chosen as negative power of 2: W = 2^(-ewma_log)

   The resulting time constant is:

   T = A/(-ln(1-W))


   NOTES.

   * avbps is scaled by 2^5, avpps is scaled by 2^10.
   * both values are reported as 32 bit unsigned values. bps can
     overflow for fast links : max speed being 34360Mbit/sec
   * Minimal interval is HZ/4=250msec (it is the greatest common divisor
     for HZ=100 and HZ=1024 8)), maximal interval
     is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
     are too expensive, longer ones can be implemented
     at user level painlessly.
 */

#define EST_MAX_INTERVAL	5

struct gen_estimator
{
	struct list_head	list;
	struct gnet_stats_basic_packed	*bstats;
	struct gnet_stats_rate_est	*rate_est;
	spinlock_t		*stats_lock;
	int			ewma_log;
	u64			last_bytes;
	u64			avbps;
	u32			last_packets;
	u32			avpps;
	struct rcu_head		e_rcu;
	struct rb_node		node;
};

struct gen_estimator_head
{
	struct timer_list	timer;
	struct list_head	list;
};

static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];

/* Protects against NULL dereference */
static DEFINE_RWLOCK(est_lock);

/* Protects against soft lockup during large deletion */
static struct rb_root est_root = RB_ROOT;

static void est_timer(unsigned long arg)
{
	int idx = (int)arg;
	struct gen_estimator *e;

	rcu_read_lock();
	list_for_each_entry_rcu(e, &elist[idx].list, list) {
		u64 nbytes;
		u64 brate;
		u32 npackets;
		u32 rate;

		spin_lock(e->stats_lock);
		read_lock(&est_lock);
		if (e->bstats == NULL)
			goto skip;

		nbytes = e->bstats->bytes;
		npackets = e->bstats->packets;
		brate = (nbytes - e->last_bytes)<<(7 - idx);
		e->last_bytes = nbytes;
		e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
		e->rate_est->bps = (e->avbps+0xF)>>5;

		rate = (npackets - e->last_packets)<<(12 - idx);
		e->last_packets = npackets;
		e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
		e->rate_est->pps = (e->avpps+0x1FF)>>10;
skip:
		read_unlock(&est_lock);
		spin_unlock(e->stats_lock);
	}

	if (!list_empty(&elist[idx].list))
		mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
	rcu_read_unlock();
}

static void gen_add_node(struct gen_estimator *est)
{
	struct rb_node **p = &est_root.rb_node, *parent = NULL;

	while (*p) {
		struct gen_estimator *e;

		parent = *p;
		e = rb_entry(parent, struct gen_estimator, node);

		if (est->bstats > e->bstats)
			p = &parent->rb_right;
		else
			p = &parent->rb_left;
	}
	rb_link_node(&est->node, parent, p);
	rb_insert_color(&est->node, &est_root);
}

static
struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats,
				    const struct gnet_stats_rate_est *rate_est)
{
	struct rb_node *p = est_root.rb_node;

	while (p) {
		struct gen_estimator *e;

		e = rb_entry(p, struct gen_estimator, node);

		if (bstats > e->bstats)
			p = p->rb_right;
		else if (bstats < e->bstats || rate_est != e->rate_est)
			p = p->rb_left;
		else
			return e;
	}
	return NULL;
}

/**
 * gen_new_estimator - create a new rate estimator
 * @bstats: basic statistics
 * @rate_est: rate estimator statistics
 * @stats_lock: statistics lock
 * @opt: rate estimator configuration TLV
 *
 * Creates a new rate estimator with &bstats as source and &rate_est
 * as destination. A new timer with the interval specified in the
 * configuration TLV is created. Upon each interval, the latest statistics
 * will be read from &bstats and the estimated rate will be stored in
 * &rate_est with the statistics lock grabed during this period.
 *
 * Returns 0 on success or a negative error code.
 *
 * NOTE: Called under rtnl_mutex
 */
int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
		      struct gnet_stats_rate_est *rate_est,
		      spinlock_t *stats_lock,
		      struct nlattr *opt)
{
	struct gen_estimator *est;
	struct gnet_estimator *parm = nla_data(opt);
	int idx;

	if (nla_len(opt) < sizeof(*parm))
		return -EINVAL;

	if (parm->interval < -2 || parm->interval > 3)
		return -EINVAL;

	est = kzalloc(sizeof(*est), GFP_KERNEL);
	if (est == NULL)
		return -ENOBUFS;

	idx = parm->interval + 2;
	est->bstats = bstats;
	est->rate_est = rate_est;
	est->stats_lock = stats_lock;
	est->ewma_log = parm->ewma_log;
	est->last_bytes = bstats->bytes;
	est->avbps = rate_est->bps<<5;
	est->last_packets = bstats->packets;
	est->avpps = rate_est->pps<<10;

	if (!elist[idx].timer.function) {
		INIT_LIST_HEAD(&elist[idx].list);
		setup_timer(&elist[idx].timer, est_timer, idx);
	}

	if (list_empty(&elist[idx].list))
		mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));

	list_add_rcu(&est->list, &elist[idx].list);
	gen_add_node(est);

	return 0;
}
EXPORT_SYMBOL(gen_new_estimator);

static void __gen_kill_estimator(struct rcu_head *head)
{
	struct gen_estimator *e = container_of(head,
					struct gen_estimator, e_rcu);
	kfree(e);
}

/**
 * gen_kill_estimator - remove a rate estimator
 * @bstats: basic statistics
 * @rate_est: rate estimator statistics
 *
 * Removes the rate estimator specified by &bstats and &rate_est.
 *
 * NOTE: Called under rtnl_mutex
 */
void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
			struct gnet_stats_rate_est *rate_est)
{
	struct gen_estimator *e;

	while ((e = gen_find_node(bstats, rate_est))) {
		rb_erase(&e->node, &est_root);

		write_lock_bh(&est_lock);
		e->bstats = NULL;
		write_unlock_bh(&est_lock);

		list_del_rcu(&e->list);
		call_rcu(&e->e_rcu, __gen_kill_estimator);
	}
}
EXPORT_SYMBOL(gen_kill_estimator);

/**
 * gen_replace_estimator - replace rate estimator configuration
 * @bstats: basic statistics
 * @rate_est: rate estimator statistics
 * @stats_lock: statistics lock
 * @opt: rate estimator configuration TLV
 *
 * Replaces the configuration of a rate estimator by calling
 * gen_kill_estimator() and gen_new_estimator().
 *
 * Returns 0 on success or a negative error code.
 */
int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
			  struct gnet_stats_rate_est *rate_est,
			  spinlock_t *stats_lock, struct nlattr *opt)
{
	gen_kill_estimator(bstats, rate_est);
	return gen_new_estimator(bstats, rate_est, stats_lock, opt);
}
EXPORT_SYMBOL(gen_replace_estimator);

/**
 * gen_estimator_active - test if estimator is currently in use
 * @bstats: basic statistics
 * @rate_est: rate estimator statistics
 *
 * Returns true if estimator is active, and false if not.
 */
bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
			  const struct gnet_stats_rate_est *rate_est)
{
	ASSERT_RTNL();

	return gen_find_node(bstats, rate_est) != NULL;
}
EXPORT_SYMBOL(gen_estimator_active);
Commit	Line	Data
1da177e4 LT	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 <asm/system.h>
1977f032	18	#include <linux/bitops.h>
1da177e4 LT	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>
4db0acf3	34	#include <linux/rbtree.h>
5a0e3ad6	35	#include <linux/slab.h>
1da177e4 LT	36	#include <net/sock.h>
	37	#include <net/gen_stats.h>
	38
	39	/*
	40	This code is NOT intended to be used for statistics collection,
	41	its purpose is to provide a base for statistical multiplexing
	42	for controlled load service.
	43	If you need only statistics, run a user level daemon which
	44	periodically reads byte counters.
	45
	46	Unfortunately, rate estimation is not a very easy task.
	47	F.e. I did not find a simple way to estimate the current peak rate
	48	and even failed to formulate the problem 8)8)
	49
	50	So I preferred not to built an estimator into the scheduler,
	51	but run this task separately.
	52	Ideally, it should be kernel thread(s), but for now it runs
	53	from timers, which puts apparent top bounds on the number of rated
	54	flows, has minimal overhead on small, but is enough
	55	to handle controlled load service, sets of aggregates.
	56
	57	We measure rate over A=(1<<interval) seconds and evaluate EWMA:
	58
	59	avrate = avrate(1-W) + rateW
	60
	61	where W is chosen as negative power of 2: W = 2^(-ewma_log)
	62
	63	The resulting time constant is:
	64
	65	T = A/(-ln(1-W))
	66
	67
	68	NOTES.
	69
511e11e3 ED	70	* avbps is scaled by 2^5, avpps is scaled by 2^10.
	71	* both values are reported as 32 bit unsigned values. bps can
	72	overflow for fast links : max speed being 34360Mbit/sec
1da177e4 LT	73	* Minimal interval is HZ/4=250msec (it is the greatest common divisor
	74	for HZ=100 and HZ=1024 8)), maximal interval
	75	is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
	76	are too expensive, longer ones can be implemented
	77	at user level painlessly.
	78	*/
	79
	80	#define EST_MAX_INTERVAL 5
	81
	82	struct gen_estimator
	83	{
0929c2dd	84	struct list_head list;
c1a8f1f1	85	struct gnet_stats_basic_packed *bstats;
1da177e4 LT	86	struct gnet_stats_rate_est *rate_est;
1da177e4 LT	87	spinlock_t *stats_lock;
1da177e4 LT	88	int ewma_log;
1da177e4 LT	89	u64 last_bytes;
511e11e3	90	u64 avbps;
1da177e4 LT	91	u32 last_packets;
1da177e4 LT	92	u32 avpps;
0929c2dd	93	struct rcu_head e_rcu;
4db0acf3	94	struct rb_node node;
1da177e4 LT	95	};
	96
	97	struct gen_estimator_head
	98	{
	99	struct timer_list timer;
0929c2dd	100	struct list_head list;
1da177e4 LT	101	};
	102
	103	static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
	104
deb3abf1	105	/* Protects against NULL dereference */
1da177e4 LT	106	static DEFINE_RWLOCK(est_lock);
1da177e4 LT	107
4db0acf3 JP	108	/* Protects against soft lockup during large deletion */
	109	static struct rb_root est_root = RB_ROOT;
	110
1da177e4 LT	111	static void est_timer(unsigned long arg)
	112	{
	113	int idx = (int)arg;
	114	struct gen_estimator *e;
	115
0929c2dd RZ	116	rcu_read_lock();
0929c2dd RZ	117	list_for_each_entry_rcu(e, &elist[idx].list, list) {
1da177e4	118	u64 nbytes;
511e11e3	119	u64 brate;
1da177e4 LT	120	u32 npackets;
	121	u32 rate;
	122
	123	spin_lock(e->stats_lock);
0929c2dd RZ	124	read_lock(&est_lock);
	125	if (e->bstats == NULL)
	126	goto skip;
	127
1da177e4 LT	128	nbytes = e->bstats->bytes;
1da177e4 LT	129	npackets = e->bstats->packets;
511e11e3	130	brate = (nbytes - e->last_bytes)<<(7 - idx);
1da177e4	131	e->last_bytes = nbytes;
a1dcb662	132	e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
1da177e4 LT	133	e->rate_est->bps = (e->avbps+0xF)>>5;
	134
	135	rate = (npackets - e->last_packets)<<(12 - idx);
	136	e->last_packets = npackets;
a1dcb662	137	e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
1da177e4	138	e->rate_est->pps = (e->avpps+0x1FF)>>10;
0929c2dd RZ	139	skip:
0929c2dd RZ	140	read_unlock(&est_lock);
1da177e4 LT	141	spin_unlock(e->stats_lock);
	142	}
	143
0929c2dd	144	if (!list_empty(&elist[idx].list))
789675e2	145	mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
0929c2dd	146	rcu_read_unlock();
1da177e4 LT	147	}
1da177e4 LT	148
4db0acf3 JP	149	static 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
244e6c2d	168	static
c1a8f1f1	169	struct gen_estimator gen_find_node(const struct gnet_stats_basic_packed bstats,
244e6c2d	170	const struct gnet_stats_rate_est *rate_est)
4db0acf3 JP	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
1da177e4 LT	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.
4ec93edb	201	*
1da177e4	202	* Returns 0 on success or a negative error code.
0929c2dd RZ	203	*
0929c2dd RZ	204	* NOTE: Called under rtnl_mutex
1da177e4	205	*/
c1a8f1f1	206	int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
0929c2dd RZ	207	struct gnet_stats_rate_est *rate_est,
0929c2dd RZ	208	spinlock_t *stats_lock,
1e90474c	209	struct nlattr *opt)
1da177e4 LT	210	{
1da177e4 LT	211	struct gen_estimator *est;
1e90474c	212	struct gnet_estimator *parm = nla_data(opt);
0929c2dd	213	int idx;
1da177e4	214
1e90474c	215	if (nla_len(opt) < sizeof(*parm))
1da177e4 LT	216	return -EINVAL;
	217
	218	if (parm->interval < -2 \|\| parm->interval > 3)
	219	return -EINVAL;
	220
77d04bd9	221	est = kzalloc(sizeof(*est), GFP_KERNEL);
1da177e4 LT	222	if (est == NULL)
	223	return -ENOBUFS;
	224
0929c2dd	225	idx = parm->interval + 2;
1da177e4 LT	226	est->bstats = bstats;
	227	est->rate_est = rate_est;
	228	est->stats_lock = stats_lock;
	229	est->ewma_log = parm->ewma_log;
	230	est->last_bytes = bstats->bytes;
	231	est->avbps = rate_est->bps<<5;
	232	est->last_packets = bstats->packets;
	233	est->avpps = rate_est->pps<<10;
	234
0929c2dd RZ	235	if (!elist[idx].timer.function) {
	236	INIT_LIST_HEAD(&elist[idx].list);
	237	setup_timer(&elist[idx].timer, est_timer, idx);
1da177e4	238	}
0929c2dd RZ	239
0929c2dd RZ	240	if (list_empty(&elist[idx].list))
789675e2	241	mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
0929c2dd RZ	242
0929c2dd RZ	243	list_add_rcu(&est->list, &elist[idx].list);
4db0acf3 JP	244	gen_add_node(est);
4db0acf3 JP	245
1da177e4 LT	246	return 0;
1da177e4 LT	247	}
c1b56878	248	EXPORT_SYMBOL(gen_new_estimator);
1da177e4	249
0929c2dd RZ	250	static void __gen_kill_estimator(struct rcu_head *head)
	251	{
	252	struct gen_estimator *e = container_of(head,
	253	struct gen_estimator, e_rcu);
	254	kfree(e);
	255	}
	256
1da177e4 LT	257	/**
	258	* gen_kill_estimator - remove a rate estimator
	259	* @bstats: basic statistics
	260	* @rate_est: rate estimator statistics
	261	*
4db0acf3	262	* Removes the rate estimator specified by &bstats and &rate_est.
0929c2dd	263	*
deb3abf1	264	* NOTE: Called under rtnl_mutex
1da177e4	265	*/
c1a8f1f1	266	void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
4db0acf3	267	struct gnet_stats_rate_est *rate_est)
1da177e4	268	{
4db0acf3	269	struct gen_estimator *e;
0929c2dd	270
4db0acf3 JP	271	while ((e = gen_find_node(bstats, rate_est))) {
4db0acf3 JP	272	rb_erase(&e->node, &est_root);
1da177e4	273
4db0acf3 JP	274	write_lock_bh(&est_lock);
	275	e->bstats = NULL;
	276	write_unlock_bh(&est_lock);
1da177e4	277
4db0acf3 JP	278	list_del_rcu(&e->list);
4db0acf3 JP	279	call_rcu(&e->e_rcu, __gen_kill_estimator);
1da177e4 LT	280	}
1da177e4 LT	281	}
c1b56878	282	EXPORT_SYMBOL(gen_kill_estimator);
1da177e4 LT	283
1da177e4 LT	284	/**
96750162	285	* gen_replace_estimator - replace rate estimator configuration
1da177e4 LT	286	* @bstats: basic statistics
	287	* @rate_est: rate estimator statistics
	288	* @stats_lock: statistics lock
	289	* @opt: rate estimator configuration TLV
	290	*
	291	* Replaces the configuration of a rate estimator by calling
	292	* gen_kill_estimator() and gen_new_estimator().
4ec93edb	293	*
1da177e4 LT	294	* Returns 0 on success or a negative error code.
1da177e4 LT	295	*/
c1a8f1f1	296	int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
96750162	297	struct gnet_stats_rate_est *rate_est,
1e90474c	298	spinlock_t stats_lock, struct nlattr opt)
1da177e4	299	{
96750162 JP	300	gen_kill_estimator(bstats, rate_est);
96750162 JP	301	return gen_new_estimator(bstats, rate_est, stats_lock, opt);
1da177e4	302	}
c1b56878 SH	303	EXPORT_SYMBOL(gen_replace_estimator);
	304
	305	/**
	306	* gen_estimator_active - test if estimator is currently in use
244e6c2d	307	* @bstats: basic statistics
c1b56878 SH	308	* @rate_est: rate estimator statistics
c1b56878 SH	309	*
244e6c2d	310	* Returns true if estimator is active, and false if not.
c1b56878	311	*/
c1a8f1f1	312	bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
244e6c2d	313	const struct gnet_stats_rate_est *rate_est)
c1b56878	314	{
c1b56878	315	ASSERT_RTNL();
1da177e4	316
244e6c2d	317	return gen_find_node(bstats, rate_est) != NULL;
c1b56878 SH	318	}
c1b56878 SH	319	EXPORT_SYMBOL(gen_estimator_active);