[PARISC] Pretty print the name of the lba type on kernel boot
[linux-2.6/lfs.git] / net / core / gen_estimator.c
blob3cad026764f0c9b94f9615ee22da0f9b4ed16833
1 /*
2 * net/sched/gen_estimator.c Simple rate estimator.
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.
9 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
11 * Changes:
12 * Jamal Hadi Salim - moved it to net/core and reshulfed
13 * names to make it usable in general net subsystem.
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>
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.
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)
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.
55 We measure rate over A=(1<<interval) seconds and evaluate EWMA:
57 avrate = avrate*(1-W) + rate*W
59 where W is chosen as negative power of 2: W = 2^(-ewma_log)
61 The resulting time constant is:
63 T = A/(-ln(1-W))
66 NOTES.
68 * The stored value for avbps is scaled by 2^5, so that maximal
69 rate is ~1Gbit, avpps is scaled by 2^10.
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.
78 #define EST_MAX_INTERVAL 5
80 struct gen_estimator
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;
94 struct gen_estimator_head
96 struct timer_list timer;
97 struct gen_estimator *list;
100 static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
102 /* Estimator array lock */
103 static DEFINE_RWLOCK(est_lock);
105 static void est_timer(unsigned long arg)
107 int idx = (int)arg;
108 struct gen_estimator *e;
110 read_lock(&est_lock);
111 for (e = elist[idx].list; e; e = e->next) {
112 u64 nbytes;
113 u32 npackets;
114 u32 rate;
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;
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);
131 mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
132 read_unlock(&est_lock);
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
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.
148 * Returns 0 on success or a negative error code.
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)
153 struct gen_estimator *est;
154 struct gnet_estimator *parm = RTA_DATA(opt);
156 if (RTA_PAYLOAD(opt) < sizeof(*parm))
157 return -EINVAL;
159 if (parm->interval < -2 || parm->interval > 3)
160 return -EINVAL;
162 est = kzalloc(sizeof(*est), GFP_KERNEL);
163 if (est == NULL)
164 return -ENOBUFS;
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;
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);
184 write_lock_bh(&est_lock);
185 elist[est->interval].list = est;
186 write_unlock_bh(&est_lock);
187 return 0;
191 * gen_kill_estimator - remove a rate estimator
192 * @bstats: basic statistics
193 * @rate_est: rate estimator statistics
195 * Removes the rate estimator specified by &bstats and &rate_est
196 * and deletes the timer.
198 void gen_kill_estimator(struct gnet_stats_basic *bstats,
199 struct gnet_stats_rate_est *rate_est)
201 int idx;
202 struct gen_estimator *est, **pest;
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;
213 write_lock_bh(&est_lock);
214 *pest = est->next;
215 write_unlock_bh(&est_lock);
217 kfree(est);
218 killed++;
220 if (killed && elist[idx].list == NULL)
221 del_timer(&elist[idx].timer);
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
232 * Replaces the configuration of a rate estimator by calling
233 * gen_kill_estimator() and gen_new_estimator().
235 * Returns 0 on success or a negative error code.
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)
242 gen_kill_estimator(bstats, rate_est);
243 return gen_new_estimator(bstats, rate_est, stats_lock, opt);
247 EXPORT_SYMBOL(gen_kill_estimator);
248 EXPORT_SYMBOL(gen_new_estimator);
249 EXPORT_SYMBOL(gen_replace_estimator);