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 <linux/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 list_head list; 83 struct gnet_stats_basic *bstats; 84 struct gnet_stats_rate_est *rate_est; 85 spinlock_t *stats_lock; 86 int ewma_log; 87 u64 last_bytes; 88 u32 last_packets; 89 u32 avpps; 90 u32 avbps; 91 struct rcu_head e_rcu; 92 }; 93 94 struct gen_estimator_head 95 { 96 struct timer_list timer; 97 struct list_head list; 98 }; 99 100 static struct gen_estimator_head elist[EST_MAX_INTERVAL+1]; 101 102 /* Protects against NULL dereference */ 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 rcu_read_lock(); 111 list_for_each_entry_rcu(e, &elist[idx].list, list) { 112 u64 nbytes; 113 u32 npackets; 114 u32 rate; 115 116 spin_lock(e->stats_lock); 117 read_lock(&est_lock); 118 if (e->bstats == NULL) 119 goto skip; 120 121 nbytes = e->bstats->bytes; 122 npackets = e->bstats->packets; 123 rate = (nbytes - e->last_bytes)<<(7 - idx); 124 e->last_bytes = nbytes; 125 e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log; 126 e->rate_est->bps = (e->avbps+0xF)>>5; 127 128 rate = (npackets - e->last_packets)<<(12 - idx); 129 e->last_packets = npackets; 130 e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log; 131 e->rate_est->pps = (e->avpps+0x1FF)>>10; 132 skip: 133 read_unlock(&est_lock); 134 spin_unlock(e->stats_lock); 135 } 136 137 if (!list_empty(&elist[idx].list)) 138 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 139 rcu_read_unlock(); 140 } 141 142 /** 143 * gen_new_estimator - create a new rate estimator 144 * @bstats: basic statistics 145 * @rate_est: rate estimator statistics 146 * @stats_lock: statistics lock 147 * @opt: rate estimator configuration TLV 148 * 149 * Creates a new rate estimator with &bstats as source and &rate_est 150 * as destination. A new timer with the interval specified in the 151 * configuration TLV is created. Upon each interval, the latest statistics 152 * will be read from &bstats and the estimated rate will be stored in 153 * &rate_est with the statistics lock grabed during this period. 154 * 155 * Returns 0 on success or a negative error code. 156 * 157 * NOTE: Called under rtnl_mutex 158 */ 159 int gen_new_estimator(struct gnet_stats_basic *bstats, 160 struct gnet_stats_rate_est *rate_est, 161 spinlock_t *stats_lock, 162 struct nlattr *opt) 163 { 164 struct gen_estimator *est; 165 struct gnet_estimator *parm = nla_data(opt); 166 int idx; 167 168 if (nla_len(opt) < sizeof(*parm)) 169 return -EINVAL; 170 171 if (parm->interval < -2 || parm->interval > 3) 172 return -EINVAL; 173 174 est = kzalloc(sizeof(*est), GFP_KERNEL); 175 if (est == NULL) 176 return -ENOBUFS; 177 178 idx = parm->interval + 2; 179 est->bstats = bstats; 180 est->rate_est = rate_est; 181 est->stats_lock = stats_lock; 182 est->ewma_log = parm->ewma_log; 183 est->last_bytes = bstats->bytes; 184 est->avbps = rate_est->bps<<5; 185 est->last_packets = bstats->packets; 186 est->avpps = rate_est->pps<<10; 187 188 if (!elist[idx].timer.function) { 189 INIT_LIST_HEAD(&elist[idx].list); 190 setup_timer(&elist[idx].timer, est_timer, idx); 191 } 192 193 if (list_empty(&elist[idx].list)) 194 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 195 196 list_add_rcu(&est->list, &elist[idx].list); 197 return 0; 198 } 199 200 static void __gen_kill_estimator(struct rcu_head *head) 201 { 202 struct gen_estimator *e = container_of(head, 203 struct gen_estimator, e_rcu); 204 kfree(e); 205 } 206 207 /** 208 * gen_kill_estimator - remove a rate estimator 209 * @bstats: basic statistics 210 * @rate_est: rate estimator statistics 211 * 212 * Removes the rate estimator specified by &bstats and &rate_est 213 * and deletes the timer. 214 * 215 * NOTE: Called under rtnl_mutex 216 */ 217 void gen_kill_estimator(struct gnet_stats_basic *bstats, 218 struct gnet_stats_rate_est *rate_est) 219 { 220 int idx; 221 struct gen_estimator *e, *n; 222 223 for (idx=0; idx <= EST_MAX_INTERVAL; idx++) { 224 225 /* Skip non initialized indexes */ 226 if (!elist[idx].timer.function) 227 continue; 228 229 list_for_each_entry_safe(e, n, &elist[idx].list, list) { 230 if (e->rate_est != rate_est || e->bstats != bstats) 231 continue; 232 233 write_lock_bh(&est_lock); 234 e->bstats = NULL; 235 write_unlock_bh(&est_lock); 236 237 list_del_rcu(&e->list); 238 call_rcu(&e->e_rcu, __gen_kill_estimator); 239 } 240 } 241 } 242 243 /** 244 * gen_replace_estimator - replace rate estimator configuration 245 * @bstats: basic statistics 246 * @rate_est: rate estimator statistics 247 * @stats_lock: statistics lock 248 * @opt: rate estimator configuration TLV 249 * 250 * Replaces the configuration of a rate estimator by calling 251 * gen_kill_estimator() and gen_new_estimator(). 252 * 253 * Returns 0 on success or a negative error code. 254 */ 255 int gen_replace_estimator(struct gnet_stats_basic *bstats, 256 struct gnet_stats_rate_est *rate_est, 257 spinlock_t *stats_lock, struct nlattr *opt) 258 { 259 gen_kill_estimator(bstats, rate_est); 260 return gen_new_estimator(bstats, rate_est, stats_lock, opt); 261 } 262 263 264 EXPORT_SYMBOL(gen_kill_estimator); 265 EXPORT_SYMBOL(gen_new_estimator); 266 EXPORT_SYMBOL(gen_replace_estimator); 267