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 <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 static DEFINE_SPINLOCK(est_tree_lock);
 111
 112 static 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;
 140 skip:
 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
 150 static 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
 169 static
 170 struct 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  */
 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         spin_lock(&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(&est_tree_lock);
 247
 248         return 0;
 249 }
 250 EXPORT_SYMBOL(gen_new_estimator);
 251
 252 static 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  */
 267 void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
 268                         struct gnet_stats_rate_est *rate_est)
 269 {
 270         struct gen_estimator *e;
 271
 272         spin_lock(&est_tree_lock);
 273         while ((e = gen_find_node(bstats, rate_est))) {
 274                 rb_erase(&e->node, &est_root);
 275
 276                 write_lock_bh(&est_lock);
 277                 e->bstats = NULL;
 278                 write_unlock_bh(&est_lock);
 279
 280                 list_del_rcu(&e->list);
 281                 call_rcu(&e->e_rcu, __gen_kill_estimator);
 282         }
 283         spin_unlock(&est_tree_lock);
 284 }
 285 EXPORT_SYMBOL(gen_kill_estimator);
 286
 287 /**
 288  * gen_replace_estimator - replace rate estimator configuration
 289  * @bstats: basic statistics
 290  * @rate_est: rate estimator statistics
 291  * @stats_lock: statistics lock
 292  * @opt: rate estimator configuration TLV
 293  *
 294  * Replaces the configuration of a rate estimator by calling
 295  * gen_kill_estimator() and gen_new_estimator().
 296  *
 297  * Returns 0 on success or a negative error code.
 298  */
 299 int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
 300                           struct gnet_stats_rate_est *rate_est,
 301                           spinlock_t *stats_lock, struct nlattr *opt)
 302 {
 303         gen_kill_estimator(bstats, rate_est);
 304         return gen_new_estimator(bstats, rate_est, stats_lock, opt);
 305 }
 306 EXPORT_SYMBOL(gen_replace_estimator);
 307
 308 /**
 309  * gen_estimator_active - test if estimator is currently in use
 310  * @bstats: basic statistics
 311  * @rate_est: rate estimator statistics
 312  *
 313  * Returns true if estimator is active, and false if not.
 314  */
 315 bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
 316                           const struct gnet_stats_rate_est *rate_est)
 317 {
 318         bool res;
 319
 320         ASSERT_RTNL();
 321
 322         spin_lock(&est_tree_lock);
 323         res = gen_find_node(bstats, rate_est) != NULL;
 324         spin_unlock(&est_tree_lock);
 325
 326         return res;
 327 }
 328 EXPORT_SYMBOL(gen_estimator_active);