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>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation.
9 #include <linux/module.h>
10 #include <linux/skbuff.h>
11 #include <linux/spinlock.h>
12 #include <linux/interrupt.h>
14 #include <linux/netfilter/x_tables.h>
15 #include <linux/netfilter/xt_limit.h>
17 struct xt_limit_priv
{
22 MODULE_LICENSE("GPL");
23 MODULE_AUTHOR("Herve Eychenne <rv@wallfire.org>");
24 MODULE_DESCRIPTION("Xtables: rate-limit match");
25 MODULE_ALIAS("ipt_limit");
26 MODULE_ALIAS("ip6t_limit");
28 /* The algorithm used is the Simple Token Bucket Filter (TBF)
29 * see net/sched/sch_tbf.c in the linux source tree
32 static DEFINE_SPINLOCK(limit_lock
);
34 /* Rusty: This is my (non-mathematically-inclined) understanding of
35 this algorithm. The `average rate' in jiffies becomes your initial
36 amount of credit `credit' and the most credit you can ever have
37 `credit_cap'. The `peak rate' becomes the cost of passing the
40 `prev' tracks the last packet hit: you gain one credit per jiffy.
41 If you get credit balance more than this, the extra credit is
42 discarded. Every time the match passes, you lose `cost' credits;
43 if you don't have that many, the test fails.
45 See Alexey's formal explanation in net/sched/sch_tbf.c.
47 To get the maxmum range, we multiply by this factor (ie. you get N
48 credits per jiffy). We want to allow a rate as low as 1 per day
49 (slowest userspace tool allows), which means
50 CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32. ie. */
51 #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
53 /* Repeated shift and or gives us all 1s, final shift and add 1 gives
54 * us the power of 2 below the theoretical max, so GCC simply does a
56 #define _POW2_BELOW2(x) ((x)|((x)>>1))
57 #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
58 #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
59 #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
60 #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
61 #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
63 #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
66 ipt_limit_match(const struct sk_buff
*skb
,
67 const struct net_device
*in
,
68 const struct net_device
*out
,
69 const struct xt_match
*match
,
70 const void *matchinfo
,
75 const struct xt_rateinfo
*r
= (struct xt_rateinfo
*)matchinfo
;
76 struct xt_limit_priv
*priv
= r
->master
;
77 unsigned long now
= jiffies
;
79 spin_lock_bh(&limit_lock
);
80 priv
->credit
+= (now
- xchg(&priv
->prev
, now
)) * CREDITS_PER_JIFFY
;
81 if (priv
->credit
> r
->credit_cap
)
82 priv
->credit
= r
->credit_cap
;
84 if (priv
->credit
>= r
->cost
) {
85 /* We're not limited. */
86 priv
->credit
-= r
->cost
;
87 spin_unlock_bh(&limit_lock
);
91 spin_unlock_bh(&limit_lock
);
95 /* Precision saver. */
97 user2credits(u_int32_t user
)
99 /* If multiplying would overflow... */
100 if (user
> 0xFFFFFFFF / (HZ
*CREDITS_PER_JIFFY
))
102 return (user
/ XT_LIMIT_SCALE
) * HZ
* CREDITS_PER_JIFFY
;
104 return (user
* HZ
* CREDITS_PER_JIFFY
) / XT_LIMIT_SCALE
;
108 ipt_limit_checkentry(const char *tablename
,
110 const struct xt_match
*match
,
112 unsigned int hook_mask
)
114 struct xt_rateinfo
*r
= matchinfo
;
115 struct xt_limit_priv
*priv
;
117 /* Check for overflow. */
119 || user2credits(r
->avg
* r
->burst
) < user2credits(r
->avg
)) {
120 printk("Overflow in xt_limit, try lower: %u/%u\n",
125 priv
= kmalloc(sizeof(*priv
), GFP_KERNEL
);
129 /* For SMP, we only want to use one set of state. */
132 /* User avg in seconds * XT_LIMIT_SCALE: convert to jiffies *
134 priv
->prev
= jiffies
;
135 priv
->credit
= user2credits(r
->avg
* r
->burst
); /* Credits full. */
136 r
->credit_cap
= user2credits(r
->avg
* r
->burst
); /* Credits full. */
137 r
->cost
= user2credits(r
->avg
);
142 static void limit_mt_destroy(const struct xt_match
*match
, void *matchinfo
)
144 const struct xt_rateinfo
*info
= matchinfo
;
150 struct compat_xt_rateinfo
{
156 u_int32_t credit_cap
, cost
;
161 /* To keep the full "prev" timestamp, the upper 32 bits are stored in the
162 * master pointer, which does not need to be preserved. */
163 static void compat_from_user(void *dst
, void *src
)
165 struct compat_xt_rateinfo
*cm
= src
;
166 struct xt_rateinfo m
= {
169 .prev
= cm
->prev
| (unsigned long)cm
->master
<< 32,
170 .credit
= cm
->credit
,
171 .credit_cap
= cm
->credit_cap
,
174 memcpy(dst
, &m
, sizeof(m
));
177 static int compat_to_user(void __user
*dst
, void *src
)
179 struct xt_rateinfo
*m
= src
;
180 struct compat_xt_rateinfo cm
= {
185 .credit_cap
= m
->credit_cap
,
187 .master
= m
->prev
>> 32,
189 return copy_to_user(dst
, &cm
, sizeof(cm
)) ? -EFAULT
: 0;
191 #endif /* CONFIG_COMPAT */
193 static struct xt_match xt_limit_match
[] = {
197 .checkentry
= ipt_limit_checkentry
,
198 .match
= ipt_limit_match
,
199 .destroy
= limit_mt_destroy
,
200 .matchsize
= sizeof(struct xt_rateinfo
),
202 .compatsize
= sizeof(struct compat_xt_rateinfo
),
203 .compat_from_user
= compat_from_user
,
204 .compat_to_user
= compat_to_user
,
211 .checkentry
= ipt_limit_checkentry
,
212 .match
= ipt_limit_match
,
213 .destroy
= limit_mt_destroy
,
214 .matchsize
= sizeof(struct xt_rateinfo
),
219 static int __init
xt_limit_init(void)
221 return xt_register_matches(xt_limit_match
, ARRAY_SIZE(xt_limit_match
));
224 static void __exit
xt_limit_fini(void)
226 xt_unregister_matches(xt_limit_match
, ARRAY_SIZE(xt_limit_match
));
229 module_init(xt_limit_init
);
230 module_exit(xt_limit_fini
);