[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 <asm/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 <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 gen_estimator	*next;
	struct gnet_stats_basic	*bstats;
	struct gnet_stats_rate_est	*rate_est;
	spinlock_t		*stats_lock;
	unsigned		interval;
	int			ewma_log;
	u64			last_bytes;
	u32			last_packets;
	u32			avpps;
	u32			avbps;
};

struct gen_estimator_head
{
	struct timer_list	timer;
	struct gen_estimator	*list;
};

static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];

/* Estimator array lock */
static DEFINE_RWLOCK(est_lock);

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

	read_lock(&est_lock);
	for (e = elist[idx].list; e; e = e->next) {
		u64 nbytes;
		u32 npackets;
		u32 rate;

		spin_lock(e->stats_lock);
		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;
		spin_unlock(e->stats_lock);
	}

	mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
	read_unlock(&est_lock);
}

/**
 * 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.
 */
int gen_new_estimator(struct gnet_stats_basic *bstats,
	struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock, struct rtattr *opt)
{
	struct gen_estimator *est;
	struct gnet_estimator *parm = RTA_DATA(opt);

	if (RTA_PAYLOAD(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;

	est->interval = 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;

	est->next = elist[est->interval].list;
	if (est->next == NULL) {
		init_timer(&elist[est->interval].timer);
		elist[est->interval].timer.data = est->interval;
		elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
		elist[est->interval].timer.function = est_timer;
		add_timer(&elist[est->interval].timer);
	}
	write_lock_bh(&est_lock);
	elist[est->interval].list = est;
	write_unlock_bh(&est_lock);
	return 0;
}

/**
 * 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
 * and deletes the timer.
 */
void gen_kill_estimator(struct gnet_stats_basic *bstats,
	struct gnet_stats_rate_est *rate_est)
{
	int idx;
	struct gen_estimator *est, **pest;

	for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
		int killed = 0;
		pest = &elist[idx].list;
		while ((est=*pest) != NULL) {
			if (est->rate_est != rate_est || est->bstats != bstats) {
				pest = &est->next;
				continue;
			}

			write_lock_bh(&est_lock);
			*pest = est->next;
			write_unlock_bh(&est_lock);

			kfree(est);
			killed++;
		}
		if (killed && elist[idx].list == NULL)
			del_timer(&elist[idx].timer);
	}
}

/**
 * gen_replace_estimator - replace rate estimator configruation
 * @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 rtattr *opt)
{
    gen_kill_estimator(bstats, rate_est);
    return gen_new_estimator(bstats, rate_est, stats_lock, opt);
}
    

EXPORT_SYMBOL(gen_kill_estimator);
EXPORT_SYMBOL(gen_new_estimator);
EXPORT_SYMBOL(gen_replace_estimator);
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>
	18	#include <asm/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 <net/sock.h>
	35	#include <net/gen_stats.h>
	36
	37	/*
	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.
	43
	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)
	47
	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.
	54
	55	We measure rate over A=(1<<interval) seconds and evaluate EWMA:
	56
	57	avrate = avrate(1-W) + rateW
	58
	59	where W is chosen as negative power of 2: W = 2^(-ewma_log)
	60
	61	The resulting time constant is:
	62
	63	T = A/(-ln(1-W))
	64
65
66	NOTES.
67
68	* The stored value for avbps is scaled by 2^5, so that maximal
69	rate is ~1Gbit, avpps is scaled by 2^10.
70
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.
76	*/
77
78	#define EST_MAX_INTERVAL 5
79
80	struct gen_estimator
81	{
82	struct gen_estimator *next;
83	struct gnet_stats_basic *bstats;
84	struct gnet_stats_rate_est *rate_est;
85	spinlock_t *stats_lock;
86	unsigned interval;
87	int ewma_log;
88	u64 last_bytes;
89	u32 last_packets;
90	u32 avpps;
91	u32 avbps;
92	};
93
94	struct gen_estimator_head
95	{
96	struct timer_list timer;
97	struct gen_estimator *list;
98	};
99
100	static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
101
102	/* Estimator array lock */
103	static DEFINE_RWLOCK(est_lock);
104
105	static void est_timer(unsigned long arg)
106	{
107	int idx = (int)arg;
108	struct gen_estimator *e;
109
110	read_lock(&est_lock);
111	for (e = elist[idx].list; e; e = e->next) {
112	u64 nbytes;
113	u32 npackets;
114	u32 rate;
115
116	spin_lock(e->stats_lock);
117	nbytes = e->bstats->bytes;
118	npackets = e->bstats->packets;
119	rate = (nbytes - e->last_bytes)<<(7 - idx);
120	e->last_bytes = nbytes;
121	e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
122	e->rate_est->bps = (e->avbps+0xF)>>5;
123
124	rate = (npackets - e->last_packets)<<(12 - idx);
125	e->last_packets = npackets;
126	e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
127	e->rate_est->pps = (e->avpps+0x1FF)>>10;
128	spin_unlock(e->stats_lock);
129	}
130
131	mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
132	read_unlock(&est_lock);
133	}
134
135	/**
136	* gen_new_estimator - create a new rate estimator
137	* @bstats: basic statistics
138	* @rate_est: rate estimator statistics
139	* @stats_lock: statistics lock
140	* @opt: rate estimator configuration TLV
141	*
142	* Creates a new rate estimator with &bstats as source and &rate_est
143	* as destination. A new timer with the interval specified in the
144	* configuration TLV is created. Upon each interval, the latest statistics
145	* will be read from &bstats and the estimated rate will be stored in
146	* &rate_est with the statistics lock grabed during this period.
147	*
148	* Returns 0 on success or a negative error code.
149	*/
150	int gen_new_estimator(struct gnet_stats_basic *bstats,
151	struct gnet_stats_rate_est rate_est, spinlock_t stats_lock, struct rtattr *opt)
152	{
153	struct gen_estimator *est;
154	struct gnet_estimator *parm = RTA_DATA(opt);
155
156	if (RTA_PAYLOAD(opt) < sizeof(*parm))
157	return -EINVAL;
158
159	if (parm->interval < -2 \|\| parm->interval > 3)
160	return -EINVAL;
161
77d04bd9	162	est = kzalloc(sizeof(*est), GFP_KERNEL);
1da177e4 LT	163	if (est == NULL)
	164	return -ENOBUFS;
	165
1da177e4 LT	166	est->interval = parm->interval + 2;
	167	est->bstats = bstats;
	168	est->rate_est = rate_est;
	169	est->stats_lock = stats_lock;
	170	est->ewma_log = parm->ewma_log;
	171	est->last_bytes = bstats->bytes;
	172	est->avbps = rate_est->bps<<5;
	173	est->last_packets = bstats->packets;
	174	est->avpps = rate_est->pps<<10;
	175
	176	est->next = elist[est->interval].list;
	177	if (est->next == NULL) {
	178	init_timer(&elist[est->interval].timer);
	179	elist[est->interval].timer.data = est->interval;
	180	elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
	181	elist[est->interval].timer.function = est_timer;
	182	add_timer(&elist[est->interval].timer);
	183	}
	184	write_lock_bh(&est_lock);
	185	elist[est->interval].list = est;
	186	write_unlock_bh(&est_lock);
	187	return 0;
	188	}
	189
	190	/**
	191	* gen_kill_estimator - remove a rate estimator
	192	* @bstats: basic statistics
	193	* @rate_est: rate estimator statistics
	194	*
	195	* Removes the rate estimator specified by &bstats and &rate_est
	196	* and deletes the timer.
	197	*/
	198	void gen_kill_estimator(struct gnet_stats_basic *bstats,
	199	struct gnet_stats_rate_est *rate_est)
	200	{
	201	int idx;
	202	struct gen_estimator est, *pest;
	203
	204	for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
	205	int killed = 0;
	206	pest = &elist[idx].list;
	207	while ((est=*pest) != NULL) {
	208	if (est->rate_est != rate_est \|\| est->bstats != bstats) {
	209	pest = &est->next;
	210	continue;
	211	}
	212
	213	write_lock_bh(&est_lock);
	214	*pest = est->next;
	215	write_unlock_bh(&est_lock);
	216
	217	kfree(est);
	218	killed++;
	219	}
	220	if (killed && elist[idx].list == NULL)
	221	del_timer(&elist[idx].timer);
	222	}
	223	}
	224
	225	/**
	226	* gen_replace_estimator - replace rate estimator configruation
	227	* @bstats: basic statistics
	228	* @rate_est: rate estimator statistics
	229	* @stats_lock: statistics lock
230	* @opt: rate estimator configuration TLV
231	*
232	* Replaces the configuration of a rate estimator by calling
233	* gen_kill_estimator() and gen_new_estimator().
234	*
235	* Returns 0 on success or a negative error code.
236	*/
237	int
238	gen_replace_estimator(struct gnet_stats_basic *bstats,
239	struct gnet_stats_rate_est rate_est, spinlock_t stats_lock,
240	struct rtattr *opt)
241	{
242	gen_kill_estimator(bstats, rate_est);
243	return gen_new_estimator(bstats, rate_est, stats_lock, opt);
244	}
245
246
247	EXPORT_SYMBOL(gen_kill_estimator);
248	EXPORT_SYMBOL(gen_new_estimator);
249	EXPORT_SYMBOL(gen_replace_estimator);