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); 250