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 <asm/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 gen_estimator    *next;
  83         struct gnet_stats_basic *bstats;
  84         struct gnet_stats_rate_est      *rate_est;
  85         spinlock_t              *stats_lock;
  86         unsigned                interval;
  87         int                     ewma_log;
  88         u64                     last_bytes;
  89         u32                     last_packets;
  90         u32                     avpps;
  91         u32                     avbps;
  92 };
  93
  94 struct gen_estimator_head
  95 {
  96         struct timer_list       timer;
  97         struct gen_estimator    *list;
  98 };
  99
 100 static struct gen_estimator_head elist[EST_MAX_INTERVAL+1];
 101
 102 /* Estimator array lock */
 103 static rwlock_t est_lock = RW_LOCK_UNLOCKED;
 104
 105 static void est_timer(unsigned long arg)
 106 {
 107         int idx = (int)arg;
 108         struct gen_estimator *e;
 109
 110         read_lock(&est_lock);
 111         for (e = elist[idx].list; e; e = e->next) {
 112                 u64 nbytes;
 113                 u32 npackets;
 114                 u32 rate;
 115
 116                 spin_lock(e->stats_lock);
 117                 nbytes = e->bstats->bytes;
 118                 npackets = e->bstats->packets;
 119                 rate = (nbytes - e->last_bytes)<<(7 - idx);
 120                 e->last_bytes = nbytes;
 121                 e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
 122                 e->rate_est->bps = (e->avbps+0xF)>>5;
 123
 124                 rate = (npackets - e->last_packets)<<(12 - idx);
 125                 e->last_packets = npackets;
 126                 e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
 127                 e->rate_est->pps = (e->avpps+0x1FF)>>10;
 128                 spin_unlock(e->stats_lock);
 129         }
 130
 131         mod_timer(&elist[idx].timer, jiffies + ((HZ<<idx)/4));
 132         read_unlock(&est_lock);
 133 }
 134
 135 int gen_new_estimator(struct gnet_stats_basic *bstats,
 136         struct gnet_stats_rate_est *rate_est, spinlock_t *stats_lock, struct rtattr *opt)
 137 {
 138         struct gen_estimator *est;
 139         struct gnet_estimator *parm = RTA_DATA(opt);
 140
 141         if (RTA_PAYLOAD(opt) < sizeof(*parm))
 142                 return -EINVAL;
 143
 144         if (parm->interval < -2 || parm->interval > 3)
 145                 return -EINVAL;
 146
 147         est = kmalloc(sizeof(*est), GFP_KERNEL);
 148         if (est == NULL)
 149                 return -ENOBUFS;
 150
 151         memset(est, 0, sizeof(*est));
 152         est->interval = parm->interval + 2;
 153         est->bstats = bstats;
 154         est->rate_est = rate_est;
 155         est->stats_lock = stats_lock;
 156         est->ewma_log = parm->ewma_log;
 157         est->last_bytes = bstats->bytes;
 158         est->avbps = rate_est->bps<<5;
 159         est->last_packets = bstats->packets;
 160         est->avpps = rate_est->pps<<10;
 161
 162         est->next = elist[est->interval].list;
 163         if (est->next == NULL) {
 164                 init_timer(&elist[est->interval].timer);
 165                 elist[est->interval].timer.data = est->interval;
 166                 elist[est->interval].timer.expires = jiffies + ((HZ<<est->interval)/4);
 167                 elist[est->interval].timer.function = est_timer;
 168                 add_timer(&elist[est->interval].timer);
 169         }
 170         write_lock_bh(&est_lock);
 171         elist[est->interval].list = est;
 172         write_unlock_bh(&est_lock);
 173         return 0;
 174 }
 175
 176 void gen_kill_estimator(struct gnet_stats_basic *bstats,
 177         struct gnet_stats_rate_est *rate_est)
 178 {
 179         int idx;
 180         struct gen_estimator *est, **pest;
 181
 182         for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
 183                 int killed = 0;
 184                 pest = &elist[idx].list;
 185                 while ((est=*pest) != NULL) {
 186                         if (est->rate_est != rate_est || est->bstats != bstats) {
 187                                 pest = &est->next;
 188                                 continue;
 189                         }
 190
 191                         write_lock_bh(&est_lock);
 192                         *pest = est->next;
 193                         write_unlock_bh(&est_lock);
 194
 195                         kfree(est);
 196                         killed++;
 197                 }
 198                 if (killed && elist[idx].list == NULL)
 199                         del_timer(&elist[idx].timer);
 200         }
 201 }
 202
 203 EXPORT_SYMBOL(gen_kill_estimator);
 204 EXPORT_SYMBOL(gen_new_estimator);