net/sched/estimator.c

   1 /*
   2  * net/sched/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
  12 #include <asm/uaccess.h>
  13 #include <asm/system.h>
  14 #include <asm/bitops.h>
  15 #include <linux/module.h>
  16 #include <linux/types.h>
  17 #include <linux/kernel.h>
  18 #include <linux/jiffies.h>
  19 #include <linux/string.h>
  20 #include <linux/mm.h>
  21 #include <linux/socket.h>
  22 #include <linux/sockios.h>
  23 #include <linux/in.h>
  24 #include <linux/errno.h>
  25 #include <linux/interrupt.h>
  26 #include <linux/netdevice.h>
  27 #include <linux/skbuff.h>
  28 #include <linux/rtnetlink.h>
  29 #include <linux/init.h>
  30 #include <net/sock.h>
  31 #include <net/pkt_sched.h>
  32
  33 /*
  34    This code is NOT intended to be used for statistics collection,
  35    its purpose is to provide a base for statistical multiplexing
  36    for controlled load service.
  37    If you need only statistics, run a user level daemon which
  38    periodically reads byte counters.
  39
  40    Unfortunately, rate estimation is not a very easy task.
  41    F.e. I did not find a simple way to estimate the current peak rate
  42    and even failed to formulate the problem 8)8)
  43
  44    So I preferred not to built an estimator into the scheduler,
  45    but run this task separately.
  46    Ideally, it should be kernel thread(s), but for now it runs
  47    from timers, which puts apparent top bounds on the number of rated
  48    flows, has minimal overhead on small, but is enough
  49    to handle controlled load service, sets of aggregates.
  50
  51    We measure rate over A=(1<<interval) seconds and evaluate EWMA:
  52
  53    avrate = avrate*(1-W) + rate*W
  54
  55    where W is chosen as negative power of 2: W = 2^(-ewma_log)
  56
  57    The resulting time constant is:
  58
  59    T = A/(-ln(1-W))
  60
  61
  62    NOTES.
  63
  64    * The stored value for avbps is scaled by 2^5, so that maximal
  65      rate is ~1Gbit, avpps is scaled by 2^10.
  66
  67    * Minimal interval is HZ/4=250msec (it is the greatest common divisor
  68      for HZ=100 and HZ=1024 8)), maximal interval
  69      is (HZ/4)*2^EST_MAX_INTERVAL = 8sec. Shorter intervals
  70      are too expensive, longer ones can be implemented
  71      at user level painlessly.
  72  */
  73
  74 #if (HZ%4) != 0
  75 #error Bad HZ value.
  76 #endif
  77
  78 #define EST_MAX_INTERVAL        5
  79
  80 struct qdisc_estimator
  81 {
  82         struct qdisc_estimator  *next;
  83         struct tc_stats         *stats;
  84         unsigned                interval;
  85         int                     ewma_log;
  86         u64                     last_bytes;
  87         u32                     last_packets;
  88         u32                     avpps;
  89         u32                     avbps;
  90 };
  91
  92 struct qdisc_estimator_head
  93 {
  94         struct timer_list       timer;
  95         struct qdisc_estimator  *list;
  96 };
  97
  98 static struct qdisc_estimator_head elist[EST_MAX_INTERVAL+1];
  99
 100 /* Estimator array lock */
 101 static rwlock_t est_lock = RW_LOCK_UNLOCKED;
 102
 103 static void est_timer(unsigned long arg)
 104 {
 105         int idx = (int)arg;
 106         struct qdisc_estimator *e;
 107
 108         read_lock(&est_lock);
 109         for (e = elist[idx].list; e; e = e->next) {
 110                 struct tc_stats *st = e->stats;
 111                 u64 nbytes;
 112                 u32 npackets;
 113                 u32 rate;
 114
 115                 spin_lock(st->lock);
 116                 nbytes = st->bytes;
 117                 npackets = st->packets;
 118                 rate = (nbytes - e->last_bytes)<<(7 - idx);
 119                 e->last_bytes = nbytes;
 120                 e->avbps += ((long)rate - (long)e->avbps) >> e->ewma_log;
 121                 st->bps = (e->avbps+0xF)>>5;
 122
 123                 rate = (npackets - e->last_packets)<<(12 - idx);
 124                 e->last_packets = npackets;
 125                 e->avpps += ((long)rate - (long)e->avpps) >> e->ewma_log;
 126                 e->stats->pps = (e->avpps+0x1FF)>>10;
 127                 spin_unlock(st->lock);
 128         }
 129
 130         mod_timer(&elist[idx].timer, jiffies + ((HZ/4)<<idx));
 131         read_unlock(&est_lock);
 132 }
 133
 134 int qdisc_new_estimator(struct tc_stats *stats, struct rtattr *opt)
 135 {
 136         struct qdisc_estimator *est;
 137         struct tc_estimator *parm = RTA_DATA(opt);
 138
 139         if (RTA_PAYLOAD(opt) < sizeof(*parm))
 140                 return -EINVAL;
 141
 142         if (parm->interval < -2 || parm->interval > 3)
 143                 return -EINVAL;
 144
 145         est = kmalloc(sizeof(*est), GFP_KERNEL);
 146         if (est == NULL)
 147                 return -ENOBUFS;
 148
 149         memset(est, 0, sizeof(*est));
 150         est->interval = parm->interval + 2;
 151         est->stats = stats;
 152         est->ewma_log = parm->ewma_log;
 153         est->last_bytes = stats->bytes;
 154         est->avbps = stats->bps<<5;
 155         est->last_packets = stats->packets;
 156         est->avpps = stats->pps<<10;
 157
 158         est->next = elist[est->interval].list;
 159         if (est->next == NULL) {
 160                 init_timer(&elist[est->interval].timer);
 161                 elist[est->interval].timer.data = est->interval;
 162                 elist[est->interval].timer.expires = jiffies + ((HZ/4)<<est->interval);
 163                 elist[est->interval].timer.function = est_timer;
 164                 add_timer(&elist[est->interval].timer);
 165         }
 166         write_lock_bh(&est_lock);
 167         elist[est->interval].list = est;
 168         write_unlock_bh(&est_lock);
 169         return 0;
 170 }
 171
 172 void qdisc_kill_estimator(struct tc_stats *stats)
 173 {
 174         int idx;
 175         struct qdisc_estimator *est, **pest;
 176
 177         for (idx=0; idx <= EST_MAX_INTERVAL; idx++) {
 178                 int killed = 0;
 179                 pest = &elist[idx].list;
 180                 while ((est=*pest) != NULL) {
 181                         if (est->stats != stats) {
 182                                 pest = &est->next;
 183                                 continue;
 184                         }
 185
 186                         write_lock_bh(&est_lock);
 187                         *pest = est->next;
 188                         write_unlock_bh(&est_lock);
 189
 190                         kfree(est);
 191                         killed++;
 192                 }
 193                 if (killed && elist[idx].list == NULL)
 194                         del_timer(&elist[idx].timer);
 195         }
 196 }
 197
 198 EXPORT_SYMBOL(qdisc_kill_estimator);
 199 EXPORT_SYMBOL(qdisc_new_estimator);