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 82 struct 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 97 struct gen_estimator_head 98 { 99 struct timer_list timer; 100 struct list_head list; 101 }; 102 103 static struct gen_estimator_head elist[EST_MAX_INTERVAL+1]; 104 105 /* Protects against NULL dereference */ 106 static DEFINE_RWLOCK(est_lock); 107 108 /* Protects against soft lockup during large deletion */ 109 static struct rb_root est_root = RB_ROOT; 110 111 static void est_timer(unsigned long arg) 112 { 113 int idx = (int)arg; 114 struct gen_estimator *e; 115 116 rcu_read_lock(); 117 list_for_each_entry_rcu(e, &elist[idx].list, list) { 118 u64 nbytes; 119 u64 brate; 120 u32 npackets; 121 u32 rate; 122 123 spin_lock(e->stats_lock); 124 read_lock(&est_lock); 125 if (e->bstats == NULL) 126 goto skip; 127 128 nbytes = e->bstats->bytes; 129 npackets = e->bstats->packets; 130 brate = (nbytes - e->last_bytes)<<(7 - idx); 131 e->last_bytes = nbytes; 132 e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log); 133 e->rate_est->bps = (e->avbps+0xF)>>5; 134 135 rate = (npackets - e->last_packets)<<(12 - idx); 136 e->last_packets = npackets; 137 e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log); 138 e->rate_est->pps = (e->avpps+0x1FF)>>10; 139 skip: 140 read_unlock(&est_lock); 141 spin_unlock(e->stats_lock); 142 } 143 144 if (!list_empty(&elist[idx].list)) 145 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 146 rcu_read_unlock(); 147 } 148 149 static void gen_add_node(struct gen_estimator *est) 150 { 151 struct rb_node **p = &est_root.rb_node, *parent = NULL; 152 153 while (*p) { 154 struct gen_estimator *e; 155 156 parent = *p; 157 e = rb_entry(parent, struct gen_estimator, node); 158 159 if (est->bstats > e->bstats) 160 p = &parent->rb_right; 161 else 162 p = &parent->rb_left; 163 } 164 rb_link_node(&est->node, parent, p); 165 rb_insert_color(&est->node, &est_root); 166 } 167 168 static 169 struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats, 170 const struct gnet_stats_rate_est *rate_est) 171 { 172 struct rb_node *p = est_root.rb_node; 173 174 while (p) { 175 struct gen_estimator *e; 176 177 e = rb_entry(p, struct gen_estimator, node); 178 179 if (bstats > e->bstats) 180 p = p->rb_right; 181 else if (bstats < e->bstats || rate_est != e->rate_est) 182 p = p->rb_left; 183 else 184 return e; 185 } 186 return NULL; 187 } 188 189 /** 190 * gen_new_estimator - create a new rate estimator 191 * @bstats: basic statistics 192 * @rate_est: rate estimator statistics 193 * @stats_lock: statistics lock 194 * @opt: rate estimator configuration TLV 195 * 196 * Creates a new rate estimator with &bstats as source and &rate_est 197 * as destination. A new timer with the interval specified in the 198 * configuration TLV is created. Upon each interval, the latest statistics 199 * will be read from &bstats and the estimated rate will be stored in 200 * &rate_est with the statistics lock grabed during this period. 201 * 202 * Returns 0 on success or a negative error code. 203 * 204 * NOTE: Called under rtnl_mutex 205 */ 206 int 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 if (!elist[idx].timer.function) { 236 INIT_LIST_HEAD(&elist[idx].list); 237 setup_timer(&elist[idx].timer, est_timer, idx); 238 } 239 240 if (list_empty(&elist[idx].list)) 241 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx)); 242 243 list_add_rcu(&est->list, &elist[idx].list); 244 gen_add_node(est); 245 246 return 0; 247 } 248 EXPORT_SYMBOL(gen_new_estimator); 249 250 static void __gen_kill_estimator(struct rcu_head *head) 251 { 252 struct gen_estimator *e = container_of(head, 253 struct gen_estimator, e_rcu); 254 kfree(e); 255 } 256 257 /** 258 * gen_kill_estimator - remove a rate estimator 259 * @bstats: basic statistics 260 * @rate_est: rate estimator statistics 261 * 262 * Removes the rate estimator specified by &bstats and &rate_est. 263 * 264 * NOTE: Called under rtnl_mutex 265 */ 266 void gen_kill_estimator(struct gnet_stats_basic_packed *bstats, 267 struct gnet_stats_rate_est *rate_est) 268 { 269 struct gen_estimator *e; 270 271 while ((e = gen_find_node(bstats, rate_est))) { 272 rb_erase(&e->node, &est_root); 273 274 write_lock_bh(&est_lock); 275 e->bstats = NULL; 276 write_unlock_bh(&est_lock); 277 278 list_del_rcu(&e->list); 279 call_rcu(&e->e_rcu, __gen_kill_estimator); 280 } 281 } 282 EXPORT_SYMBOL(gen_kill_estimator); 283 284 /** 285 * gen_replace_estimator - replace rate estimator configuration 286 * @bstats: basic statistics 287 * @rate_est: rate estimator statistics 288 * @stats_lock: statistics lock 289 * @opt: rate estimator configuration TLV 290 * 291 * Replaces the configuration of a rate estimator by calling 292 * gen_kill_estimator() and gen_new_estimator(). 293 * 294 * Returns 0 on success or a negative error code. 295 */ 296 int gen_replace_estimator(struct gnet_stats_basic_packed *bstats, 297 struct gnet_stats_rate_est *rate_est, 298 spinlock_t *stats_lock, struct nlattr *opt) 299 { 300 gen_kill_estimator(bstats, rate_est); 301 return gen_new_estimator(bstats, rate_est, stats_lock, opt); 302 } 303 EXPORT_SYMBOL(gen_replace_estimator); 304 305 /** 306 * gen_estimator_active - test if estimator is currently in use 307 * @bstats: basic statistics 308 * @rate_est: rate estimator statistics 309 * 310 * Returns true if estimator is active, and false if not. 311 */ 312 bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats, 313 const struct gnet_stats_rate_est *rate_est) 314 { 315 ASSERT_RTNL(); 316 317 return gen_find_node(bstats, rate_est) != NULL; 318 } 319 EXPORT_SYMBOL(gen_estimator_active); 320