Merge with rsync://fileserver/linux
[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 = kmalloc(sizeof(*est), GFP_KERNEL);
163         if (est == NULL)
164                 return -ENOBUFS;
165
166         memset(est, 0, sizeof(*est));
167         est->interval = parm->interval + 2;
168         est->bstats = bstats;
169         est->rate_est = rate_est;
170         est->stats_lock = stats_lock;
171         est->ewma_log = parm->ewma_log;
172         est->last_bytes = bstats->bytes;
173         est->avbps = rate_est->bps<<5;
174         est->last_packets = bstats->packets;
175         est->avpps = rate_est->pps<<10;
176
177         est->next = elist[est->interval].list;
178         if (est->next == NULL) {
179                 init_timer(&elist[est->interval].timer);
180                 elist[est->interval].timer.data = est->interval;
181                 elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
182                 elist[est->interval].timer.function = est_timer;
183                 add_timer(&elist[est->interval].timer);
184         }
185         write_lock_bh(&est_lock);
186         elist[est->interval].list = est;
187         write_unlock_bh(&est_lock);
188         return 0;
189 }
190
191 /**
192  * gen_kill_estimator - remove a rate estimator
193  * @bstats: basic statistics
194  * @rate_est: rate estimator statistics
195  *
196  * Removes the rate estimator specified by &bstats and &rate_est
197  * and deletes the timer.
198  */
199 void gen_kill_estimator(struct gnet_stats_basic *bstats,
200         struct gnet_stats_rate_est *rate_est)
201 {
202         int idx;
203         struct gen_estimator *est, **pest;
204
205         for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
206                 int killed = 0;
207                 pest = &elist[idx].list;
208                 while ((est=*pest) != NULL) {
209                         if (est->rate_est != rate_est || est->bstats != bstats) {
210                                 pest = &est->next;
211                                 continue;
212                         }
213
214                         write_lock_bh(&est_lock);
215                         *pest = est->next;
216                         write_unlock_bh(&est_lock);
217
218                         kfree(est);
219                         killed++;
220                 }
221                 if (killed && elist[idx].list == NULL)
222                         del_timer(&elist[idx].timer);
223         }
224 }
225
226 /**
227  * gen_replace_estimator - replace rate estimator configruation
228  * @bstats: basic statistics
229  * @rate_est: rate estimator statistics
230  * @stats_lock: statistics lock
231  * @opt: rate estimator configuration TLV
232  *
233  * Replaces the configuration of a rate estimator by calling
234  * gen_kill_estimator() and gen_new_estimator().
235  * 
236  * Returns 0 on success or a negative error code.
237  */
238 int
239 gen_replace_estimator(struct gnet_stats_basic *bstats,
240         struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock,
241         struct rtattr *opt)
242 {
243     gen_kill_estimator(bstats, rate_est);
244     return gen_new_estimator(bstats, rate_est, stats_lock, opt);
245 }
246     
247
248 EXPORT_SYMBOL(gen_kill_estimator);
249 EXPORT_SYMBOL(gen_new_estimator);
250 EXPORT_SYMBOL(gen_replace_estimator);