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 <net/sock.h>
  35 #include <net/gen_stats.h>
  36
  37 /*
  38    This code is NOT intended to be used for statistics collection,
  39    its purpose is to provide a base for statistical multiplexing
  40    for controlled load service.
  41    If you need only statistics, run a user level daemon which
  42    periodically reads byte counters.
  43
  44    Unfortunately, rate estimation is not a very easy task.
  45    F.e. I did not find a simple way to estimate the current peak rate
  46    and even failed to formulate the problem 8)8)
  47
  48    So I preferred not to built an estimator into the scheduler,
  49    but run this task separately.
  50    Ideally, it should be kernel thread(s), but for now it runs
  51    from timers, which puts apparent top bounds on the number of rated
  52    flows, has minimal overhead on small, but is enough
  53    to handle controlled load service, sets of aggregates.
  54
  55    We measure rate over A=(1<<interval) seconds and evaluate EWMA:
  56
  57    avrate = avrate*(1-W) + rate*W
  58
  59    where W is chosen as negative power of 2: W = 2^(-ewma_log)
  60
  61    The resulting time constant is:
  62
  63    T = A/(-ln(1-W))
  64
  65
  66    NOTES.
  67
  68    * The stored value for avbps is scaled by 2^5, so that maximal
  69      rate is ~1Gbit, avpps is scaled by 2^10.
  70
  71    * Minimal interval is HZ/4=250msec (it is the greatest common divisor
  72      for HZ=100 and HZ=1024 8)), maximal interval
  73      is (HZ*2^EST_MAX_INTERVAL)/4 = 8sec. Shorter intervals
  74      are too expensive, longer ones can be implemented
  75      at user level painlessly.
  76  */
  77
  78 #define EST_MAX_INTERVAL        5
  79
  80 struct gen_estimator
  81 {
  82         struct list_head        list;
  83         struct gnet_stats_basic *bstats;
  84         struct gnet_stats_rate_est      *rate_est;
  85         spinlock_t              *stats_lock;
  86         int                     ewma_log;
  87         u64                     last_bytes;
  88         u32                     last_packets;
  89         u32                     avpps;
  90         u32                     avbps;
  91         struct rcu_head         e_rcu;
  92 };
  93
  94 struct gen_estimator_head
  95 {
  96         struct timer_list       timer;
  97         struct list_head        list;
  98 };
  99
 100 static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
 101
 102 /* Protects against NULL dereference and RCU write-side */
 103 static DEFINE_RWLOCK(est_lock);
 104
 105 static void est_timer(unsigned long arg)
 106 {
 107         int idx = (int)arg;
 108         struct gen_estimator *e;
 109
 110         rcu_read_lock();
 111         list_for_each_entry_rcu(e, &elist[idx].list, list) {
 112                 u64 nbytes;
 113                 u32 npackets;
 114                 u32 rate;
 115
 116                 spin_lock(e->stats_lock);
 117                 read_lock(&est_lock);
 118                 if (e->bstats == NULL)
 119                         goto skip;
 120
 121                 nbytes = e->bstats->bytes;
 122                 npackets = e->bstats->packets;
 123                 rate = (nbytes - e->last_bytes)<<(7 - idx);
 124                 e->last_bytes = nbytes;
 125                 e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
 126                 e->rate_est->bps = (e->avbps+0xF)>>5;
 127
 128                 rate = (npackets - e->last_packets)<<(12 - idx);
 129                 e->last_packets = npackets;
 130                 e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
 131                 e->rate_est->pps = (e->avpps+0x1FF)>>10;
 132 skip:
 133                 read_unlock(&est_lock);
 134                 spin_unlock(e->stats_lock);
 135         }
 136
 137         if (!list_empty(&elist[idx].list))
 138                 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
 139         rcu_read_unlock();
 140 }
 141
 142 /**
 143  * gen_new_estimator - create a new rate estimator
 144  * @bstats: basic statistics
 145  * @rate_est: rate estimator statistics
 146  * @stats_lock: statistics lock
 147  * @opt: rate estimator configuration TLV
 148  *
 149  * Creates a new rate estimator with &bstats as source and &rate_est
 150  * as destination. A new timer with the interval specified in the
 151  * configuration TLV is created. Upon each interval, the latest statistics
 152  * will be read from &bstats and the estimated rate will be stored in
 153  * &rate_est with the statistics lock grabed during this period.
 154  *
 155  * Returns 0 on success or a negative error code.
 156  *
 157  * NOTE: Called under rtnl_mutex
 158  */
 159 int gen_new_estimator(struct gnet_stats_basic *bstats,
 160                       struct gnet_stats_rate_est *rate_est,
 161                       spinlock_t *stats_lock,
 162                       struct nlattr *opt)
 163 {
 164         struct gen_estimator *est;
 165         struct gnet_estimator *parm = nla_data(opt);
 166         int idx;
 167
 168         if (nla_len(opt) < sizeof(*parm))
 169                 return -EINVAL;
 170
 171         if (parm->interval < -2 || parm->interval > 3)
 172                 return -EINVAL;
 173
 174         est = kzalloc(sizeof(*est), GFP_KERNEL);
 175         if (est == NULL)
 176                 return -ENOBUFS;
 177
 178         idx = parm->interval + 2;
 179         est->bstats = bstats;
 180         est->rate_est = rate_est;
 181         est->stats_lock = stats_lock;
 182         est->ewma_log = parm->ewma_log;
 183         est->last_bytes = bstats->bytes;
 184         est->avbps = rate_est->bps<<5;
 185         est->last_packets = bstats->packets;
 186         est->avpps = rate_est->pps<<10;
 187
 188         write_lock_bh(&est_lock);
 189         if (!elist[idx].timer.function) {
 190                 INIT_LIST_HEAD(&elist[idx].list);
 191                 setup_timer(&elist[idx].timer, est_timer, idx);
 192         }
 193
 194         if (list_empty(&elist[idx].list))
 195                 mod_timer(&elist[idx].timer, jiffies + ((HZ/4) << idx));
 196
 197         list_add_rcu(&est->list, &elist[idx].list);
 198         write_unlock_bh(&est_lock);
 199         return 0;
 200 }
 201
 202 static void __gen_kill_estimator(struct rcu_head *head)
 203 {
 204         struct gen_estimator *e = container_of(head,
 205                                         struct gen_estimator, e_rcu);
 206         kfree(e);
 207 }
 208
 209 /**
 210  * gen_kill_estimator - remove a rate estimator
 211  * @bstats: basic statistics
 212  * @rate_est: rate estimator statistics
 213  *
 214  * Removes the rate estimator specified by &bstats and &rate_est
 215  * and deletes the timer.
 216  *
 217  */
 218 void gen_kill_estimator(struct gnet_stats_basic *bstats,
 219         struct gnet_stats_rate_est *rate_est)
 220 {
 221         int idx;
 222         struct gen_estimator *e, *n;
 223
 224         for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
 225
 226                 /* Skip non initialized indexes */
 227                 if (!elist[idx].timer.function)
 228                         continue;
 229
 230                 write_lock_bh(&est_lock);
 231                 list_for_each_entry_safe(e, n, &elist[idx].list, list) {
 232                         if (e->rate_est != rate_est || e->bstats != bstats)
 233                                 continue;
 234
 235                         e->bstats = NULL;
 236
 237                         list_del_rcu(&e->list);
 238                         call_rcu(&e->e_rcu, __gen_kill_estimator);
 239                 }
 240                 write_unlock_bh(&est_lock);
 241         }
 242 }
 243
 244 /**
 245  * gen_replace_estimator - replace rate estimator configuration
 246  * @bstats: basic statistics
 247  * @rate_est: rate estimator statistics
 248  * @stats_lock: statistics lock
 249  * @opt: rate estimator configuration TLV
 250  *
 251  * Replaces the configuration of a rate estimator by calling
 252  * gen_kill_estimator() and gen_new_estimator().
 253  *
 254  * Returns 0 on success or a negative error code.
 255  */
 256 int gen_replace_estimator(struct gnet_stats_basic *bstats,
 257                           struct gnet_stats_rate_est *rate_est,
 258                           spinlock_t *stats_lock, struct nlattr *opt)
 259 {
 260         gen_kill_estimator(bstats, rate_est);
 261         return gen_new_estimator(bstats, rate_est, stats_lock, opt);
 262 }
 263
 264
 265 EXPORT_SYMBOL(gen_kill_estimator);
 266 EXPORT_SYMBOL(gen_new_estimator);
 267 EXPORT_SYMBOL(gen_replace_estimator);