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 is scaled by 2^5, avpps is scaled by 2^10.
  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         u64                     last_bytes;
  89         u64                     avbps;
  90         u32                     last_packets;
  91         u32                     avpps;
  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                 u64 brate;
 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                 __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)<<(12 - idx);
 137                 e->last_packets = b.packets;
 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_est64 *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 grabbed 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_basic_cpu __percpu *cpu_bstats,
 208                       struct gnet_stats_rate_est64 *rate_est,
 209                       spinlock_t *stats_lock,
 210                       struct nlattr *opt)
 211 {
 212         struct gen_estimator *est;
 213         struct gnet_estimator *parm = nla_data(opt);
 214         struct gnet_stats_basic_packed b = {0};
 215         int idx;
 216
 217         if (nla_len(opt) < sizeof(*parm))
 218                 return -EINVAL;
 219
 220         if (parm->interval < -2 || parm->interval > 3)
 221                 return -EINVAL;
 222
 223         est = kzalloc(sizeof(*est), GFP_KERNEL);
 224         if (est == NULL)
 225                 return -ENOBUFS;
 226
 227         __gnet_stats_copy_basic(&b, cpu_bstats, bstats);
 228
 229         idx = parm->interval + 2;
 230         est->bstats = bstats;
 231         est->rate_est = rate_est;
 232         est->stats_lock = stats_lock;
 233         est->ewma_log = parm->ewma_log;
 234         est->last_bytes = b.bytes;
 235         est->avbps = rate_est->bps<<5;
 236         est->last_packets = b.packets;
 237         est->avpps = rate_est->pps<<10;
 238         est->cpu_bstats = cpu_bstats;
 239
 240         spin_lock_bh(&est_tree_lock);
 241         if (!elist[idx].timer.function) {
 242                 INIT_LIST_HEAD(&elist[idx].list);
 243                 setup_timer(&elist[idx].timer, est_timer, idx);
 244         }
 245
 246         if (list_empty(&elist[idx].list))
 247                 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
 248
 249         list_add_rcu(&est->list, &elist[idx].list);
 250         gen_add_node(est);
 251         spin_unlock_bh(&est_tree_lock);
 252
 253         return 0;
 254 }
 255 EXPORT_SYMBOL(gen_new_estimator);
 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 : Caller should respect an RCU grace period before freeing stats_lock
 265  */
 266 void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
 267                         struct gnet_stats_rate_est64 *rate_est)
 268 {
 269         struct gen_estimator *e;
 270
 271         spin_lock_bh(&est_tree_lock);
 272         while ((e = gen_find_node(bstats, rate_est))) {
 273                 rb_erase(&e->node, &est_root);
 274
 275                 write_lock(&est_lock);
 276                 e->bstats = NULL;
 277                 write_unlock(&est_lock);
 278
 279                 list_del_rcu(&e->list);
 280                 kfree_rcu(e, e_rcu);
 281         }
 282         spin_unlock_bh(&est_tree_lock);
 283 }
 284 EXPORT_SYMBOL(gen_kill_estimator);
 285
 286 /**
 287  * gen_replace_estimator - replace rate estimator configuration
 288  * @bstats: basic statistics
 289  * @rate_est: rate estimator statistics
 290  * @stats_lock: statistics lock
 291  * @opt: rate estimator configuration TLV
 292  *
 293  * Replaces the configuration of a rate estimator by calling
 294  * gen_kill_estimator() and gen_new_estimator().
 295  *
 296  * Returns 0 on success or a negative error code.
 297  */
 298 int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
 299                           struct gnet_stats_basic_cpu __percpu *cpu_bstats,
 300                           struct gnet_stats_rate_est64 *rate_est,
 301                           spinlock_t *stats_lock, struct nlattr *opt)
 302 {
 303         gen_kill_estimator(bstats, rate_est);
 304         return gen_new_estimator(bstats, cpu_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_est64 *rate_est)
 317 {
 318         bool res;
 319
 320         ASSERT_RTNL();
 321
 322         spin_lock_bh(&est_tree_lock);
 323         res = gen_find_node(bstats, rate_est) != NULL;
 324         spin_unlock_bh(&est_tree_lock);
 325
 326         return res;
 327 }
 328 EXPORT_SYMBOL(gen_estimator_active);