Merge master.kernel.org:/home/rmk/linux-2.6-serial
[linux-2.6] / net / core / gen_estimator.c
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) + rate*W
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
162         est = kzalloc(sizeof(*est), GFP_KERNEL);
163         if (est == NULL)
164                 return -ENOBUFS;
165
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);