[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 <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.

   * The stored value for avbps is scaled by 2^5, so that maximal
     rate is ~1Gbit, avpps is scaled by 2^10.

   * 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	*bstats;
	struct gnet_stats_rate_est	*rate_est;
	spinlock_t		*stats_lock;
	int			ewma_log;
	u64			last_bytes;
	u32			last_packets;
	u32			avpps;
	u32			avbps;
	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;
		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;
		rate = (nbytes - e->last_bytes)<<(7 - idx);
		e->last_bytes = nbytes;
		e->avbps += ((long)rate - (long)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 += ((long)rate - (long)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 *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 *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 *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 *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 *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>
1da177e4 LT	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) + rateW
	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	* The stored value for avbps is scaled by 2^5, so that maximal
	70	rate is ~1Gbit, avpps is scaled by 2^10.
	71
	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	{
0929c2dd	83	struct list_head list;
1da177e4 LT	84	struct gnet_stats_basic *bstats;
	85	struct gnet_stats_rate_est *rate_est;
	86	spinlock_t *stats_lock;
1da177e4 LT	87	int ewma_log;
	88	u64 last_bytes;
	89	u32 last_packets;
	90	u32 avpps;
	91	u32 avbps;
0929c2dd	92	struct rcu_head e_rcu;
4db0acf3	93	struct rb_node node;
1da177e4 LT	94	};
	95
	96	struct gen_estimator_head
	97	{
	98	struct timer_list timer;
0929c2dd	99	struct list_head list;
1da177e4 LT	100	};
	101
	102	static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
	103
deb3abf1	104	/* Protects against NULL dereference */
1da177e4 LT	105	static DEFINE_RWLOCK(est_lock);
1da177e4 LT	106
4db0acf3 JP	107	/* Protects against soft lockup during large deletion */
	108	static struct rb_root est_root = RB_ROOT;
	109
1da177e4 LT	110	static void est_timer(unsigned long arg)
	111	{
	112	int idx = (int)arg;
	113	struct gen_estimator *e;
	114
0929c2dd RZ	115	rcu_read_lock();
0929c2dd RZ	116	list_for_each_entry_rcu(e, &elist[idx].list, list) {
1da177e4 LT	117	u64 nbytes;
	118	u32 npackets;
	119	u32 rate;
	120
	121	spin_lock(e->stats_lock);
0929c2dd RZ	122	read_lock(&est_lock);
	123	if (e->bstats == NULL)
	124	goto skip;
	125
1da177e4 LT	126	nbytes = e->bstats->bytes;
	127	npackets = e->bstats->packets;
	128	rate = (nbytes - e->last_bytes)<<(7 - idx);
	129	e->last_bytes = nbytes;
	130	e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
	131	e->rate_est->bps = (e->avbps+0xF)>>5;
	132
	133	rate = (npackets - e->last_packets)<<(12 - idx);
	134	e->last_packets = npackets;
	135	e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
	136	e->rate_est->pps = (e->avpps+0x1FF)>>10;
0929c2dd RZ	137	skip:
0929c2dd RZ	138	read_unlock(&est_lock);
1da177e4 LT	139	spin_unlock(e->stats_lock);
	140	}
	141
0929c2dd	142	if (!list_empty(&elist[idx].list))
789675e2	143	mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
0929c2dd	144	rcu_read_unlock();
1da177e4 LT	145	}
1da177e4 LT	146
4db0acf3 JP	147	static void gen_add_node(struct gen_estimator *est)
	148	{
	149	struct rb_node *p = &est_root.rb_node, parent = NULL;
	150
	151	while (*p) {
	152	struct gen_estimator *e;
	153
	154	parent = *p;
	155	e = rb_entry(parent, struct gen_estimator, node);
	156
	157	if (est->bstats > e->bstats)
	158	p = &parent->rb_right;
	159	else
	160	p = &parent->rb_left;
	161	}
	162	rb_link_node(&est->node, parent, p);
	163	rb_insert_color(&est->node, &est_root);
	164	}
	165
244e6c2d JP	166	static
	167	struct gen_estimator gen_find_node(const struct gnet_stats_basic bstats,
	168	const struct gnet_stats_rate_est *rate_est)
4db0acf3 JP	169	{
	170	struct rb_node *p = est_root.rb_node;
	171
	172	while (p) {
	173	struct gen_estimator *e;
	174
	175	e = rb_entry(p, struct gen_estimator, node);
	176
	177	if (bstats > e->bstats)
	178	p = p->rb_right;
	179	else if (bstats < e->bstats \|\| rate_est != e->rate_est)
	180	p = p->rb_left;
	181	else
	182	return e;
	183	}
	184	return NULL;
	185	}
	186
1da177e4 LT	187	/**
	188	* gen_new_estimator - create a new rate estimator
	189	* @bstats: basic statistics
	190	* @rate_est: rate estimator statistics
	191	* @stats_lock: statistics lock
	192	* @opt: rate estimator configuration TLV
	193	*
	194	* Creates a new rate estimator with &bstats as source and &rate_est
	195	* as destination. A new timer with the interval specified in the
	196	* configuration TLV is created. Upon each interval, the latest statistics
	197	* will be read from &bstats and the estimated rate will be stored in
	198	* &rate_est with the statistics lock grabed during this period.
4ec93edb	199	*
1da177e4	200	* Returns 0 on success or a negative error code.
0929c2dd RZ	201	*
0929c2dd RZ	202	* NOTE: Called under rtnl_mutex
1da177e4 LT	203	*/
1da177e4 LT	204	int gen_new_estimator(struct gnet_stats_basic *bstats,
0929c2dd RZ	205	struct gnet_stats_rate_est *rate_est,
0929c2dd RZ	206	spinlock_t *stats_lock,
1e90474c	207	struct nlattr *opt)
1da177e4 LT	208	{
1da177e4 LT	209	struct gen_estimator *est;
1e90474c	210	struct gnet_estimator *parm = nla_data(opt);
0929c2dd	211	int idx;
1da177e4	212
1e90474c	213	if (nla_len(opt) < sizeof(*parm))
1da177e4 LT	214	return -EINVAL;
	215
	216	if (parm->interval < -2 \|\| parm->interval > 3)
	217	return -EINVAL;
	218
77d04bd9	219	est = kzalloc(sizeof(*est), GFP_KERNEL);
1da177e4 LT	220	if (est == NULL)
	221	return -ENOBUFS;
	222
0929c2dd	223	idx = parm->interval + 2;
1da177e4 LT	224	est->bstats = bstats;
	225	est->rate_est = rate_est;
	226	est->stats_lock = stats_lock;
	227	est->ewma_log = parm->ewma_log;
	228	est->last_bytes = bstats->bytes;
	229	est->avbps = rate_est->bps<<5;
	230	est->last_packets = bstats->packets;
	231	est->avpps = rate_est->pps<<10;
	232
0929c2dd RZ	233	if (!elist[idx].timer.function) {
	234	INIT_LIST_HEAD(&elist[idx].list);
	235	setup_timer(&elist[idx].timer, est_timer, idx);
1da177e4	236	}
0929c2dd RZ	237
0929c2dd RZ	238	if (list_empty(&elist[idx].list))
789675e2	239	mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
0929c2dd RZ	240
0929c2dd RZ	241	list_add_rcu(&est->list, &elist[idx].list);
4db0acf3 JP	242	gen_add_node(est);
4db0acf3 JP	243
1da177e4 LT	244	return 0;
1da177e4 LT	245	}
c1b56878	246	EXPORT_SYMBOL(gen_new_estimator);
1da177e4	247
0929c2dd RZ	248	static void __gen_kill_estimator(struct rcu_head *head)
	249	{
	250	struct gen_estimator *e = container_of(head,
	251	struct gen_estimator, e_rcu);
	252	kfree(e);
	253	}
	254
1da177e4 LT	255	/**
	256	* gen_kill_estimator - remove a rate estimator
	257	* @bstats: basic statistics
	258	* @rate_est: rate estimator statistics
	259	*
4db0acf3	260	* Removes the rate estimator specified by &bstats and &rate_est.
0929c2dd	261	*
deb3abf1	262	* NOTE: Called under rtnl_mutex
1da177e4 LT	263	*/
1da177e4 LT	264	void gen_kill_estimator(struct gnet_stats_basic *bstats,
4db0acf3	265	struct gnet_stats_rate_est *rate_est)
1da177e4	266	{
4db0acf3	267	struct gen_estimator *e;
0929c2dd	268
4db0acf3 JP	269	while ((e = gen_find_node(bstats, rate_est))) {
4db0acf3 JP	270	rb_erase(&e->node, &est_root);
1da177e4	271
4db0acf3 JP	272	write_lock_bh(&est_lock);
	273	e->bstats = NULL;
	274	write_unlock_bh(&est_lock);
1da177e4	275
4db0acf3 JP	276	list_del_rcu(&e->list);
4db0acf3 JP	277	call_rcu(&e->e_rcu, __gen_kill_estimator);
1da177e4 LT	278	}
1da177e4 LT	279	}
c1b56878	280	EXPORT_SYMBOL(gen_kill_estimator);
1da177e4 LT	281
1da177e4 LT	282	/**
96750162	283	* gen_replace_estimator - replace rate estimator configuration
1da177e4 LT	284	* @bstats: basic statistics
	285	* @rate_est: rate estimator statistics
	286	* @stats_lock: statistics lock
	287	* @opt: rate estimator configuration TLV
	288	*
	289	* Replaces the configuration of a rate estimator by calling
	290	* gen_kill_estimator() and gen_new_estimator().
4ec93edb	291	*
1da177e4 LT	292	* Returns 0 on success or a negative error code.
1da177e4 LT	293	*/
96750162 JP	294	int gen_replace_estimator(struct gnet_stats_basic *bstats,
96750162 JP	295	struct gnet_stats_rate_est *rate_est,
1e90474c	296	spinlock_t stats_lock, struct nlattr opt)
1da177e4	297	{
96750162 JP	298	gen_kill_estimator(bstats, rate_est);
96750162 JP	299	return gen_new_estimator(bstats, rate_est, stats_lock, opt);
1da177e4	300	}
c1b56878 SH	301	EXPORT_SYMBOL(gen_replace_estimator);
	302
	303	/**
	304	* gen_estimator_active - test if estimator is currently in use
244e6c2d	305	* @bstats: basic statistics
c1b56878 SH	306	* @rate_est: rate estimator statistics
c1b56878 SH	307	*
244e6c2d	308	* Returns true if estimator is active, and false if not.
c1b56878	309	*/
244e6c2d JP	310	bool gen_estimator_active(const struct gnet_stats_basic *bstats,
244e6c2d JP	311	const struct gnet_stats_rate_est *rate_est)
c1b56878	312	{
c1b56878	313	ASSERT_RTNL();
1da177e4	314
244e6c2d	315	return gen_find_node(bstats, rate_est) != NULL;
c1b56878 SH	316	}
c1b56878 SH	317	EXPORT_SYMBOL(gen_estimator_active);