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 <linux/rbtree.h> 35#include <linux/slab.h> 36#include <net/sock.h> 37#include <net/gen_stats.h> 38 39/* 40 This code is NOT intended to be used for statistics collection, 41 its purpose is to provide a base for statistical multiplexing 42 for controlled load service. 43 If you need only statistics, run a user level daemon which 44 periodically reads byte counters. 45 46 Unfortunately, rate estimation is not a very easy task. 47 F.e. I did not find a simple way to estimate the current peak rate 48 and even failed to formulate the problem 8)8) 49 50 So I preferred not to built an estimator into the scheduler, 51 but run this task separately. 52 Ideally, it should be kernel thread(s), but for now it runs 53 from timers, which puts apparent top bounds on the number of rated 54 flows, has minimal overhead on small, but is enough 55 to handle controlled load service, sets of aggregates. 56 57 We measure rate over A=(1<<interval) seconds and evaluate EWMA: 58 59 avrate = avrate*(1-W) + rate*W 60 61 where W is chosen as negative power of 2: W = 2^(-ewma_log) 62 63 The resulting time constant is: 64 65 T = A/(-ln(1-W)) 66 67 68 NOTES. 69 70 * avbps is scaled by 2^5, avpps is scaled by 2^10. 71 * both values are reported as 32 bit unsigned values. bps can 72 overflow for fast links : max speed being 34360Mbit/sec 73 * Minimal interval is HZ/4=250msec (it is the greatest common divisor 74 for HZ=100 and HZ=1024 8)), maximal interval 75 is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals 76 are too expensive, longer ones can be implemented 77 at user level painlessly. 78 */ 79 80#define EST_MAX_INTERVAL 5 81 82struct gen_estimator 83{ 84 struct list_head list; 85 struct gnet_stats_basic_packed *bstats; 86 struct gnet_stats_rate_est *rate_est; 87 spinlock_t *stats_lock; 88 int ewma_log; 89 u64 last_bytes; 90 u64 avbps; 91 u32 last_packets; 92 u32 avpps; 93 struct rcu_head e_rcu; 94 struct rb_node node; 95}; 96 97struct gen_estimator_head 98{ 99 struct timer_list timer; 100 struct list_head list; 101}; 102 103static struct gen_estimator_head elist[EST_MAX_INTERVAL+1]; 104 105/* Protects against NULL dereference */ 106static DEFINE_RWLOCK(est_lock); 107 108/* Protects against soft lockup during large deletion */ 109static struct rb_root est_root = RB_ROOT; 110static DEFINE_SPINLOCK(est_tree_lock); 111 112static void est_timer(unsigned long arg) 113{ 114 int idx = (int)arg; 115 struct gen_estimator *e; 116 117 rcu_read_lock(); 118 list_for_each_entry_rcu(e, &elist[idx].list, list) { 119 u64 nbytes; 120 u64 brate; 121 u32 npackets; 122 u32 rate; 123 124 spin_lock(e->stats_lock); 125 read_lock(&est_lock); 126 if (e->bstats == NULL) 127 goto skip; 128 129 nbytes = e->bstats->bytes; 130 npackets = e->bstats->packets; 131 brate = (nbytes - e->last_bytes)<<(7 - idx); 132 e->last_bytes = nbytes; 133 e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log); 134 e->rate_est->bps = (e->avbps+0xF)>>5; 135 136 rate = (npackets - e->last_packets)<<(12 - idx); 137 e->last_packets = npackets; 138 e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log); 139 e->rate_est->pps = (e->avpps+0x1FF)>>10; 140skip: 141 read_unlock(&est_lock); 142 spin_unlock(e->stats_lock); 143 } 144 145 if (!list_empty(&elist[idx].list)) 146 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 147 rcu_read_unlock(); 148} 149 150static void gen_add_node(struct gen_estimator *est) 151{ 152 struct rb_node **p = &est_root.rb_node, *parent = NULL; 153 154 while (*p) { 155 struct gen_estimator *e; 156 157 parent = *p; 158 e = rb_entry(parent, struct gen_estimator, node); 159 160 if (est->bstats > e->bstats) 161 p = &parent->rb_right; 162 else 163 p = &parent->rb_left; 164 } 165 rb_link_node(&est->node, parent, p); 166 rb_insert_color(&est->node, &est_root); 167} 168 169static 170struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats, 171 const struct gnet_stats_rate_est *rate_est) 172{ 173 struct rb_node *p = est_root.rb_node; 174 175 while (p) { 176 struct gen_estimator *e; 177 178 e = rb_entry(p, struct gen_estimator, node); 179 180 if (bstats > e->bstats) 181 p = p->rb_right; 182 else if (bstats < e->bstats || rate_est != e->rate_est) 183 p = p->rb_left; 184 else 185 return e; 186 } 187 return NULL; 188} 189 190/** 191 * gen_new_estimator - create a new rate estimator 192 * @bstats: basic statistics 193 * @rate_est: rate estimator statistics 194 * @stats_lock: statistics lock 195 * @opt: rate estimator configuration TLV 196 * 197 * Creates a new rate estimator with &bstats as source and &rate_est 198 * as destination. A new timer with the interval specified in the 199 * configuration TLV is created. Upon each interval, the latest statistics 200 * will be read from &bstats and the estimated rate will be stored in 201 * &rate_est with the statistics lock grabed during this period. 202 * 203 * Returns 0 on success or a negative error code. 204 * 205 */ 206int gen_new_estimator(struct gnet_stats_basic_packed *bstats, 207 struct gnet_stats_rate_est *rate_est, 208 spinlock_t *stats_lock, 209 struct nlattr *opt) 210{ 211 struct gen_estimator *est; 212 struct gnet_estimator *parm = nla_data(opt); 213 int idx; 214 215 if (nla_len(opt) < sizeof(*parm)) 216 return -EINVAL; 217 218 if (parm->interval < -2 || parm->interval > 3) 219 return -EINVAL; 220 221 est = kzalloc(sizeof(*est), GFP_KERNEL); 222 if (est == NULL) 223 return -ENOBUFS; 224 225 idx = parm->interval + 2; 226 est->bstats = bstats; 227 est->rate_est = rate_est; 228 est->stats_lock = stats_lock; 229 est->ewma_log = parm->ewma_log; 230 est->last_bytes = bstats->bytes; 231 est->avbps = rate_est->bps<<5; 232 est->last_packets = bstats->packets; 233 est->avpps = rate_est->pps<<10; 234 235 spin_lock_bh(&est_tree_lock); 236 if (!elist[idx].timer.function) { 237 INIT_LIST_HEAD(&elist[idx].list); 238 setup_timer(&elist[idx].timer, est_timer, idx); 239 } 240 241 if (list_empty(&elist[idx].list)) 242 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 243 244 list_add_rcu(&est->list, &elist[idx].list); 245 gen_add_node(est); 246 spin_unlock_bh(&est_tree_lock); 247 248 return 0; 249} 250EXPORT_SYMBOL(gen_new_estimator); 251 252static void __gen_kill_estimator(struct rcu_head *head) 253{ 254 struct gen_estimator *e = container_of(head, 255 struct gen_estimator, e_rcu); 256 kfree(e); 257} 258 259/** 260 * gen_kill_estimator - remove a rate estimator 261 * @bstats: basic statistics 262 * @rate_est: rate estimator statistics 263 * 264 * Removes the rate estimator specified by &bstats and &rate_est. 265 * 266 * Note : Caller should respect an RCU grace period before freeing stats_lock 267 */ 268void gen_kill_estimator(struct gnet_stats_basic_packed *bstats, 269 struct gnet_stats_rate_est *rate_est) 270{ 271 struct gen_estimator *e; 272 273 spin_lock_bh(&est_tree_lock); 274 while ((e = gen_find_node(bstats, rate_est))) { 275 rb_erase(&e->node, &est_root); 276 277 write_lock_bh(&est_lock); 278 e->bstats = NULL; 279 write_unlock_bh(&est_lock); 280 281 list_del_rcu(&e->list); 282 call_rcu(&e->e_rcu, __gen_kill_estimator); 283 } 284 spin_unlock_bh(&est_tree_lock); 285} 286EXPORT_SYMBOL(gen_kill_estimator); 287 288/** 289 * gen_replace_estimator - replace rate estimator configuration 290 * @bstats: basic statistics 291 * @rate_est: rate estimator statistics 292 * @stats_lock: statistics lock 293 * @opt: rate estimator configuration TLV 294 * 295 * Replaces the configuration of a rate estimator by calling 296 * gen_kill_estimator() and gen_new_estimator(). 297 * 298 * Returns 0 on success or a negative error code. 299 */ 300int gen_replace_estimator(struct gnet_stats_basic_packed *bstats, 301 struct gnet_stats_rate_est *rate_est, 302 spinlock_t *stats_lock, struct nlattr *opt) 303{ 304 gen_kill_estimator(bstats, rate_est); 305 return gen_new_estimator(bstats, rate_est, stats_lock, opt); 306} 307EXPORT_SYMBOL(gen_replace_estimator); 308 309/** 310 * gen_estimator_active - test if estimator is currently in use 311 * @bstats: basic statistics 312 * @rate_est: rate estimator statistics 313 * 314 * Returns true if estimator is active, and false if not. 315 */ 316bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats, 317 const struct gnet_stats_rate_est *rate_est) 318{ 319 bool res; 320 321 ASSERT_RTNL(); 322 323 spin_lock_bh(&est_tree_lock); 324 res = gen_find_node(bstats, rate_est) != NULL; 325 spin_unlock_bh(&est_tree_lock); 326 327 return res; 328} 329EXPORT_SYMBOL(gen_estimator_active); 330