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         struct list_head        list;
  83         struct gnet_stats_basic_packed  *bstats;
  84         struct gnet_stats_rate_est64    *rate_est;
  85         spinlock_t              *stats_lock;
  86         seqcount_t              *running;
  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         unsigned long           next_jiffies;
 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                 if (e->stats_lock)
 125                         spin_lock(e->stats_lock);
 126                 read_lock(&est_lock);
 127                 if (e->bstats == NULL)
 128                         goto skip;
 129
 130                 __gnet_stats_copy_basic(e->running, &b, e->cpu_bstats, e->bstats);
 131
 132                 brate = (b.bytes - e->last_bytes)<<(7 - idx);
 133                 e->last_bytes = b.bytes;
 134                 e->avbps += (brate >> e->ewma_log) - (e->avbps >> e->ewma_log);
 135                 WRITE_ONCE(e->rate_est->bps, (e->avbps + 0xF) >> 5);
 136
 137                 rate = b.packets - e->last_packets;
 138                 rate <<= (7 - idx);
 139                 e->last_packets = b.packets;
 140                 e->avpps += (rate >> e->ewma_log) - (e->avpps >> e->ewma_log);
 141                 WRITE_ONCE(e->rate_est->pps, (e->avpps + 0xF) >> 5);
 142 skip:
 143                 read_unlock(&est_lock);
 144                 if (e->stats_lock)
 145                         spin_unlock(e->stats_lock);
 146         }
 147
 148         if (!list_empty(&elist[idx].list)) {
 149                 elist[idx].next_jiffies += ((HZ/4) << idx);
 150
 151                 if (unlikely(time_after_eq(jiffies, elist[idx].next_jiffies))) {
 152                         /* Ouch... timer was delayed. */
 153                         elist[idx].next_jiffies = jiffies + 1;
 154                 }
 155                 mod_timer(&elist[idx].timer, elist[idx].next_jiffies);
 156         }
 157         rcu_read_unlock();
 158 }
 159
 160 static void gen_add_node(struct gen_estimator *est)
 161 {
 162         struct rb_node **p = &est_root.rb_node, *parent = NULL;
 163
 164         while (*p) {
 165                 struct gen_estimator *e;
 166
 167                 parent = *p;
 168                 e = rb_entry(parent, struct gen_estimator, node);
 169
 170                 if (est->bstats > e->bstats)
 171                         p = &parent->rb_right;
 172                 else
 173                         p = &parent->rb_left;
 174         }
 175         rb_link_node(&est->node, parent, p);
 176         rb_insert_color(&est->node, &est_root);
 177 }
 178
 179 static
 180 struct gen_estimator *gen_find_node(const struct gnet_stats_basic_packed *bstats,
 181                                     const struct gnet_stats_rate_est64 *rate_est)
 182 {
 183         struct rb_node *p = est_root.rb_node;
 184
 185         while (p) {
 186                 struct gen_estimator *e;
 187
 188                 e = rb_entry(p, struct gen_estimator, node);
 189
 190                 if (bstats > e->bstats)
 191                         p = p->rb_right;
 192                 else if (bstats < e->bstats || rate_est != e->rate_est)
 193                         p = p->rb_left;
 194                 else
 195                         return e;
 196         }
 197         return NULL;
 198 }
 199
 200 /**
 201  * gen_new_estimator - create a new rate estimator
 202  * @bstats: basic statistics
 203  * @cpu_bstats: bstats per cpu
 204  * @rate_est: rate estimator statistics
 205  * @stats_lock: statistics lock
 206  * @running: qdisc running seqcount
 207  * @opt: rate estimator configuration TLV
 208  *
 209  * Creates a new rate estimator with &bstats as source and &rate_est
 210  * as destination. A new timer with the interval specified in the
 211  * configuration TLV is created. Upon each interval, the latest statistics
 212  * will be read from &bstats and the estimated rate will be stored in
 213  * &rate_est with the statistics lock grabbed during this period.
 214  *
 215  * Returns 0 on success or a negative error code.
 216  *
 217  */
 218 int gen_new_estimator(struct gnet_stats_basic_packed *bstats,
 219                       struct gnet_stats_basic_cpu __percpu *cpu_bstats,
 220                       struct gnet_stats_rate_est64 *rate_est,
 221                       spinlock_t *stats_lock,
 222                       seqcount_t *running,
 223                       struct nlattr *opt)
 224 {
 225         struct gen_estimator *est;
 226         struct gnet_estimator *parm = nla_data(opt);
 227         struct gnet_stats_basic_packed b = {0};
 228         int idx;
 229
 230         if (nla_len(opt) < sizeof(*parm))
 231                 return -EINVAL;
 232
 233         if (parm->interval < -2 || parm->interval > 3)
 234                 return -EINVAL;
 235
 236         est = kzalloc(sizeof(*est), GFP_KERNEL);
 237         if (est == NULL)
 238                 return -ENOBUFS;
 239
 240         __gnet_stats_copy_basic(running, &b, cpu_bstats, bstats);
 241
 242         idx = parm->interval + 2;
 243         est->bstats = bstats;
 244         est->rate_est = rate_est;
 245         est->stats_lock = stats_lock;
 246         est->running  = running;
 247         est->ewma_log = parm->ewma_log;
 248         est->last_bytes = b.bytes;
 249         est->avbps = rate_est->bps<<5;
 250         est->last_packets = b.packets;
 251         est->avpps = rate_est->pps<<10;
 252         est->cpu_bstats = cpu_bstats;
 253
 254         spin_lock_bh(&est_tree_lock);
 255         if (!elist[idx].timer.function) {
 256                 INIT_LIST_HEAD(&elist[idx].list);
 257                 setup_timer(&elist[idx].timer, est_timer, idx);
 258         }
 259
 260         if (list_empty(&elist[idx].list)) {
 261                 elist[idx].next_jiffies = jiffies + ((HZ/4) << idx);
 262                 mod_timer(&elist[idx].timer, elist[idx].next_jiffies);
 263         }
 264         list_add_rcu(&est->list, &elist[idx].list);
 265         gen_add_node(est);
 266         spin_unlock_bh(&est_tree_lock);
 267
 268         return 0;
 269 }
 270 EXPORT_SYMBOL(gen_new_estimator);
 271
 272 /**
 273  * gen_kill_estimator - remove a rate estimator
 274  * @bstats: basic statistics
 275  * @rate_est: rate estimator statistics
 276  *
 277  * Removes the rate estimator specified by &bstats and &rate_est.
 278  *
 279  * Note : Caller should respect an RCU grace period before freeing stats_lock
 280  */
 281 void gen_kill_estimator(struct gnet_stats_basic_packed *bstats,
 282                         struct gnet_stats_rate_est64 *rate_est)
 283 {
 284         struct gen_estimator *e;
 285
 286         spin_lock_bh(&est_tree_lock);
 287         while ((e = gen_find_node(bstats, rate_est))) {
 288                 rb_erase(&e->node, &est_root);
 289
 290                 write_lock(&est_lock);
 291                 e->bstats = NULL;
 292                 write_unlock(&est_lock);
 293
 294                 list_del_rcu(&e->list);
 295                 kfree_rcu(e, e_rcu);
 296         }
 297         spin_unlock_bh(&est_tree_lock);
 298 }
 299 EXPORT_SYMBOL(gen_kill_estimator);
 300
 301 /**
 302  * gen_replace_estimator - replace rate estimator configuration
 303  * @bstats: basic statistics
 304  * @cpu_bstats: bstats per cpu
 305  * @rate_est: rate estimator statistics
 306  * @stats_lock: statistics lock
 307  * @running: qdisc running seqcount (might be NULL)
 308  * @opt: rate estimator configuration TLV
 309  *
 310  * Replaces the configuration of a rate estimator by calling
 311  * gen_kill_estimator() and gen_new_estimator().
 312  *
 313  * Returns 0 on success or a negative error code.
 314  */
 315 int gen_replace_estimator(struct gnet_stats_basic_packed *bstats,
 316                           struct gnet_stats_basic_cpu __percpu *cpu_bstats,
 317                           struct gnet_stats_rate_est64 *rate_est,
 318                           spinlock_t *stats_lock,
 319                           seqcount_t *running, struct nlattr *opt)
 320 {
 321         gen_kill_estimator(bstats, rate_est);
 322         return gen_new_estimator(bstats, cpu_bstats, rate_est, stats_lock, running, opt);
 323 }
 324 EXPORT_SYMBOL(gen_replace_estimator);
 325
 326 /**
 327  * gen_estimator_active - test if estimator is currently in use
 328  * @bstats: basic statistics
 329  * @rate_est: rate estimator statistics
 330  *
 331  * Returns true if estimator is active, and false if not.
 332  */
 333 bool gen_estimator_active(const struct gnet_stats_basic_packed *bstats,
 334                           const struct gnet_stats_rate_est64 *rate_est)
 335 {
 336         bool res;
 337
 338         ASSERT_RTNL();
 339
 340         spin_lock_bh(&est_tree_lock);
 341         res = gen_find_node(bstats, rate_est) != NULL;
 342         spin_unlock_bh(&est_tree_lock);
 343
 344         return res;
 345 }
 346 EXPORT_SYMBOL(gen_estimator_active);