net/ipv6/netfilter/ip6t_limit.c

   1 /* Kernel module to control the rate
   2  *
   3  * Jérôme de Vivie   <devivie@info.enserb.u-bordeaux.fr>
   4  * Hervé Eychenne   <eychenne@info.enserb.u-bordeaux.fr>
   5  *
   6  * 2 September 1999: Changed from the target RATE to the match
   7  *                   `limit', removed logging.  Did I mention that
   8  *                   Alexey is a fucking genius?
   9  *                   Rusty Russell (rusty@rustcorp.com.au).  */
  10 #include <linux/module.h>
  11 #include <linux/skbuff.h>
  12 #include <linux/spinlock.h>
  13 #include <linux/interrupt.h>
  14
  15 #include <linux/netfilter_ipv6/ip6_tables.h>
  16 #include <linux/netfilter_ipv6/ip6t_limit.h>
  17
  18 /* The algorithm used is the Simple Token Bucket Filter (TBF)
  19  * see net/sched/sch_tbf.c in the linux source tree
  20  */
  21
  22 static spinlock_t limit_lock = SPIN_LOCK_UNLOCKED;
  23
  24 /* Rusty: This is my (non-mathematically-inclined) understanding of
  25    this algorithm.  The `average rate' in jiffies becomes your initial
  26    amount of credit `credit' and the most credit you can ever have
  27    `credit_cap'.  The `peak rate' becomes the cost of passing the
  28    test, `cost'.
  29
  30    `prev' tracks the last packet hit: you gain one credit per jiffy.
  31    If you get credit balance more than this, the extra credit is
  32    discarded.  Every time the match passes, you lose `cost' credits;
  33    if you don't have that many, the test fails.
  34
  35    See Alexey's formal explanation in net/sched/sch_tbf.c.
  36
  37    To avoid underflow, we multiply by 128 (ie. you get 128 credits per
  38    jiffy).  Hence a cost of 2^32-1, means one pass per 32768 seconds
  39    at 1024HZ (or one every 9 hours).  A cost of 1 means 12800 passes
  40    per second at 100HZ.  */
  41
  42 #define CREDITS_PER_JIFFY 128
  43
  44 static int
  45 ip6t_limit_match(const struct sk_buff *skb,
  46                 const struct net_device *in,
  47                 const struct net_device *out,
  48                 const void *matchinfo,
  49                 int offset,
  50                 const void *hdr,
  51                 u_int16_t datalen,
  52                 int *hotdrop)
  53 {
  54         struct ip6t_rateinfo *r = ((struct ip6t_rateinfo *)matchinfo)->master;
  55         unsigned long now = jiffies;
  56
  57         spin_lock_bh(&limit_lock);
  58         r->credit += (now - xchg(&r->prev, now)) * CREDITS_PER_JIFFY;
  59         if (r->credit > r->credit_cap)
  60                 r->credit = r->credit_cap;
  61
  62         if (r->credit >= r->cost) {
  63                 /* We're not limited. */
  64                 r->credit -= r->cost;
  65                 spin_unlock_bh(&limit_lock);
  66                 return 1;
  67         }
  68
  69         spin_unlock_bh(&limit_lock);
  70         return 0;
  71 }
  72
  73 /* Precision saver. */
  74 static u_int32_t
  75 user2credits(u_int32_t user)
  76 {
  77         /* If multiplying would overflow... */
  78         if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))
  79                 /* Divide first. */
  80                 return (user / IP6T_LIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;
  81
  82         return (user * HZ * CREDITS_PER_JIFFY) / IP6T_LIMIT_SCALE;
  83 }
  84
  85 static int
  86 ip6t_limit_checkentry(const char *tablename,
  87                      const struct ip6t_ip6 *ip,
  88                      void *matchinfo,
  89                      unsigned int matchsize,
  90                      unsigned int hook_mask)
  91 {
  92         struct ip6t_rateinfo *r = matchinfo;
  93
  94         if (matchsize != IP6T_ALIGN(sizeof(struct ip6t_rateinfo)))
  95                 return 0;
  96
  97         /* Check for overflow. */
  98         if (r->burst == 0
  99             || user2credits(r->avg * r->burst) < user2credits(r->avg)) {
 100                 printk("Call rusty: overflow in ip6t_limit: %u/%u\n",
 101                        r->avg, r->burst);
 102                 return 0;
 103         }
 104
 105         /* User avg in seconds * IP6T_LIMIT_SCALE: convert to jiffies *
 106            128. */
 107         r->prev = jiffies;
 108         r->credit = user2credits(r->avg * r->burst);     /* Credits full. */
 109         r->credit_cap = user2credits(r->avg * r->burst); /* Credits full. */
 110         r->cost = user2credits(r->avg);
 111
 112         /* For SMP, we only want to use one set of counters. */
 113         r->master = r;
 114
 115         return 1;
 116 }
 117
 118 static struct ip6t_match ip6t_limit_reg
 119 = { { NULL, NULL }, "limit", ip6t_limit_match, ip6t_limit_checkentry, NULL,
 120     THIS_MODULE };
 121
 122 static int __init init(void)
 123 {
 124         if (ip6t_register_match(&ip6t_limit_reg))
 125                 return -EINVAL;
 126         return 0;
 127 }
 128
 129 static void __exit fini(void)
 130 {
 131         ip6t_unregister_match(&ip6t_limit_reg);
 132 }
 133
 134 module_init(init);
 135 module_exit(fini);
 136 MODULE_LICENSE("GPL");