~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/netfilter/xt_limit.c

Version: ~ [ linux-5.10-rc5 ] ~ [ linux-5.9.10 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.79 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.159 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.208 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.245 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.245 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.85 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* (C) 1999 Jérôme de Vivie <devivie@info.enserb.u-bordeaux.fr>
  2  * (C) 1999 Hervé Eychenne <eychenne@info.enserb.u-bordeaux.fr>
  3  * (C) 2006-2012 Patrick McHardy <kaber@trash.net>
  4  *
  5  * This program is free software; you can redistribute it and/or modify
  6  * it under the terms of the GNU General Public License version 2 as
  7  * published by the Free Software Foundation.
  8  */
  9 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
 10 
 11 #include <linux/slab.h>
 12 #include <linux/module.h>
 13 #include <linux/skbuff.h>
 14 #include <linux/spinlock.h>
 15 #include <linux/interrupt.h>
 16 
 17 #include <linux/netfilter/x_tables.h>
 18 #include <linux/netfilter/xt_limit.h>
 19 
 20 struct xt_limit_priv {
 21         unsigned long prev;
 22         uint32_t credit;
 23 };
 24 
 25 MODULE_LICENSE("GPL");
 26 MODULE_AUTHOR("Herve Eychenne <rv@wallfire.org>");
 27 MODULE_DESCRIPTION("Xtables: rate-limit match");
 28 MODULE_ALIAS("ipt_limit");
 29 MODULE_ALIAS("ip6t_limit");
 30 
 31 /* The algorithm used is the Simple Token Bucket Filter (TBF)
 32  * see net/sched/sch_tbf.c in the linux source tree
 33  */
 34 
 35 static DEFINE_SPINLOCK(limit_lock);
 36 
 37 /* Rusty: This is my (non-mathematically-inclined) understanding of
 38    this algorithm.  The `average rate' in jiffies becomes your initial
 39    amount of credit `credit' and the most credit you can ever have
 40    `credit_cap'.  The `peak rate' becomes the cost of passing the
 41    test, `cost'.
 42 
 43    `prev' tracks the last packet hit: you gain one credit per jiffy.
 44    If you get credit balance more than this, the extra credit is
 45    discarded.  Every time the match passes, you lose `cost' credits;
 46    if you don't have that many, the test fails.
 47 
 48    See Alexey's formal explanation in net/sched/sch_tbf.c.
 49 
 50    To get the maxmum range, we multiply by this factor (ie. you get N
 51    credits per jiffy).  We want to allow a rate as low as 1 per day
 52    (slowest userspace tool allows), which means
 53    CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32. ie. */
 54 #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
 55 
 56 /* Repeated shift and or gives us all 1s, final shift and add 1 gives
 57  * us the power of 2 below the theoretical max, so GCC simply does a
 58  * shift. */
 59 #define _POW2_BELOW2(x) ((x)|((x)>>1))
 60 #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
 61 #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
 62 #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
 63 #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
 64 #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
 65 
 66 #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
 67 
 68 static bool
 69 limit_mt(const struct sk_buff *skb, struct xt_action_param *par)
 70 {
 71         const struct xt_rateinfo *r = par->matchinfo;
 72         struct xt_limit_priv *priv = r->master;
 73         unsigned long now = jiffies;
 74 
 75         spin_lock_bh(&limit_lock);
 76         priv->credit += (now - xchg(&priv->prev, now)) * CREDITS_PER_JIFFY;
 77         if (priv->credit > r->credit_cap)
 78                 priv->credit = r->credit_cap;
 79 
 80         if (priv->credit >= r->cost) {
 81                 /* We're not limited. */
 82                 priv->credit -= r->cost;
 83                 spin_unlock_bh(&limit_lock);
 84                 return true;
 85         }
 86 
 87         spin_unlock_bh(&limit_lock);
 88         return false;
 89 }
 90 
 91 /* Precision saver. */
 92 static u32 user2credits(u32 user)
 93 {
 94         /* If multiplying would overflow... */
 95         if (user > 0xFFFFFFFF / (HZ*CREDITS_PER_JIFFY))
 96                 /* Divide first. */
 97                 return (user / XT_LIMIT_SCALE) * HZ * CREDITS_PER_JIFFY;
 98 
 99         return (user * HZ * CREDITS_PER_JIFFY) / XT_LIMIT_SCALE;
100 }
101 
102 static int limit_mt_check(const struct xt_mtchk_param *par)
103 {
104         struct xt_rateinfo *r = par->matchinfo;
105         struct xt_limit_priv *priv;
106 
107         /* Check for overflow. */
108         if (r->burst == 0
109             || user2credits(r->avg * r->burst) < user2credits(r->avg)) {
110                 pr_info("Overflow, try lower: %u/%u\n",
111                         r->avg, r->burst);
112                 return -ERANGE;
113         }
114 
115         priv = kmalloc(sizeof(*priv), GFP_KERNEL);
116         if (priv == NULL)
117                 return -ENOMEM;
118 
119         /* For SMP, we only want to use one set of state. */
120         r->master = priv;
121         /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
122            128. */
123         priv->prev = jiffies;
124         priv->credit = user2credits(r->avg * r->burst); /* Credits full. */
125         if (r->cost == 0) {
126                 r->credit_cap = priv->credit; /* Credits full. */
127                 r->cost = user2credits(r->avg);
128         }
129         return 0;
130 }
131 
132 static void limit_mt_destroy(const struct xt_mtdtor_param *par)
133 {
134         const struct xt_rateinfo *info = par->matchinfo;
135 
136         kfree(info->master);
137 }
138 
139 #ifdef CONFIG_COMPAT
140 struct compat_xt_rateinfo {
141         u_int32_t avg;
142         u_int32_t burst;
143 
144         compat_ulong_t prev;
145         u_int32_t credit;
146         u_int32_t credit_cap, cost;
147 
148         u_int32_t master;
149 };
150 
151 /* To keep the full "prev" timestamp, the upper 32 bits are stored in the
152  * master pointer, which does not need to be preserved. */
153 static void limit_mt_compat_from_user(void *dst, const void *src)
154 {
155         const struct compat_xt_rateinfo *cm = src;
156         struct xt_rateinfo m = {
157                 .avg            = cm->avg,
158                 .burst          = cm->burst,
159                 .prev           = cm->prev | (unsigned long)cm->master << 32,
160                 .credit         = cm->credit,
161                 .credit_cap     = cm->credit_cap,
162                 .cost           = cm->cost,
163         };
164         memcpy(dst, &m, sizeof(m));
165 }
166 
167 static int limit_mt_compat_to_user(void __user *dst, const void *src)
168 {
169         const struct xt_rateinfo *m = src;
170         struct compat_xt_rateinfo cm = {
171                 .avg            = m->avg,
172                 .burst          = m->burst,
173                 .prev           = m->prev,
174                 .credit         = m->credit,
175                 .credit_cap     = m->credit_cap,
176                 .cost           = m->cost,
177                 .master         = m->prev >> 32,
178         };
179         return copy_to_user(dst, &cm, sizeof(cm)) ? -EFAULT : 0;
180 }
181 #endif /* CONFIG_COMPAT */
182 
183 static struct xt_match limit_mt_reg __read_mostly = {
184         .name             = "limit",
185         .revision         = 0,
186         .family           = NFPROTO_UNSPEC,
187         .match            = limit_mt,
188         .checkentry       = limit_mt_check,
189         .destroy          = limit_mt_destroy,
190         .matchsize        = sizeof(struct xt_rateinfo),
191 #ifdef CONFIG_COMPAT
192         .compatsize       = sizeof(struct compat_xt_rateinfo),
193         .compat_from_user = limit_mt_compat_from_user,
194         .compat_to_user   = limit_mt_compat_to_user,
195 #endif
196         .me               = THIS_MODULE,
197 };
198 
199 static int __init limit_mt_init(void)
200 {
201         return xt_register_match(&limit_mt_reg);
202 }
203 
204 static void __exit limit_mt_exit(void)
205 {
206         xt_unregister_match(&limit_mt_reg);
207 }
208 
209 module_init(limit_mt_init);
210 module_exit(limit_mt_exit);
211 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp