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