1 /* iptables match extension to limit the number of packets per second
2 * seperately for each hashbucket (sourceip/sourceport/dstip/dstport)
4 * (C) 2003-2004 by Harald Welte <laforge@netfilter.org>
6 * $Id: ipt_hashlimit.c 3244 2004-10-20 16:24:29Z laforge@netfilter.org $
8 * Development of this code was funded by Astaro AG, http://www.astaro.com/
10 * based on ipt_limit.c by:
11 * Jérôme de Vivie <devivie@info.enserb.u-bordeaux.fr>
12 * Hervé Eychenne <eychenne@info.enserb.u-bordeaux.fr>
13 * Rusty Russell <rusty@rustcorp.com.au>
15 * The general idea is to create a hash table for every dstip and have a
16 * seperate limit counter per tuple. This way you can do something like 'limit
17 * the number of syn packets for each of my internal addresses.
19 * Ideally this would just be implemented as a general 'hash' match, which would
20 * allow us to attach any iptables target to it's hash buckets. But this is
21 * not possible in the current iptables architecture. As always, pkttables for
24 #include <linux/module.h>
25 #include <linux/skbuff.h>
26 #include <linux/spinlock.h>
27 #include <linux/random.h>
28 #include <linux/jhash.h>
29 #include <linux/slab.h>
30 #include <linux/vmalloc.h>
31 #include <linux/proc_fs.h>
32 #include <linux/seq_file.h>
33 #include <linux/list.h>
35 #include <linux/netfilter_ipv4/ip_tables.h>
36 #include <linux/netfilter_ipv4/ipt_hashlimit.h>
38 /* FIXME: this is just for IP_NF_ASSERRT */
39 #include <linux/netfilter_ipv4/ip_conntrack.h>
40 #include <linux/mutex.h>
42 MODULE_LICENSE("GPL");
43 MODULE_AUTHOR("Harald Welte <laforge@netfilter.org>");
44 MODULE_DESCRIPTION("iptables match for limiting per hash-bucket");
46 /* need to declare this at the top */
47 static struct proc_dir_entry
*hashlimit_procdir
;
48 static struct file_operations dl_file_ops
;
55 /* ports have to be consecutive !!! */
61 /* static / read-only parts in the beginning */
62 struct hlist_node node
;
63 struct dsthash_dst dst
;
65 /* modified structure members in the end */
66 unsigned long expires
; /* precalculated expiry time */
68 unsigned long prev
; /* last modification */
70 u_int32_t credit_cap
, cost
;
74 struct ipt_hashlimit_htable
{
75 struct hlist_node node
; /* global list of all htables */
78 struct hashlimit_cfg cfg
; /* config */
81 spinlock_t lock
; /* lock for list_head */
82 u_int32_t rnd
; /* random seed for hash */
84 struct timer_list timer
; /* timer for gc */
85 atomic_t count
; /* number entries in table */
88 struct proc_dir_entry
*pde
;
90 struct hlist_head hash
[0]; /* hashtable itself */
93 static DEFINE_SPINLOCK(hashlimit_lock
); /* protects htables list */
94 static DEFINE_MUTEX(hlimit_mutex
); /* additional checkentry protection */
95 static HLIST_HEAD(hashlimit_htables
);
96 static kmem_cache_t
*hashlimit_cachep __read_mostly
;
98 static inline int dst_cmp(const struct dsthash_ent
*ent
, struct dsthash_dst
*b
)
100 return (ent
->dst
.dst_ip
== b
->dst_ip
101 && ent
->dst
.dst_port
== b
->dst_port
102 && ent
->dst
.src_port
== b
->src_port
103 && ent
->dst
.src_ip
== b
->src_ip
);
106 static inline u_int32_t
107 hash_dst(const struct ipt_hashlimit_htable
*ht
, const struct dsthash_dst
*dst
)
109 return (jhash_3words((__force u32
)dst
->dst_ip
,
110 ((__force u32
)dst
->dst_port
<<16 |
111 (__force u32
)dst
->src_port
),
112 (__force u32
)dst
->src_ip
, ht
->rnd
) % ht
->cfg
.size
);
115 static inline struct dsthash_ent
*
116 __dsthash_find(const struct ipt_hashlimit_htable
*ht
, struct dsthash_dst
*dst
)
118 struct dsthash_ent
*ent
;
119 struct hlist_node
*pos
;
120 u_int32_t hash
= hash_dst(ht
, dst
);
122 if (!hlist_empty(&ht
->hash
[hash
]))
123 hlist_for_each_entry(ent
, pos
, &ht
->hash
[hash
], node
) {
124 if (dst_cmp(ent
, dst
)) {
132 /* allocate dsthash_ent, initialize dst, put in htable and lock it */
133 static struct dsthash_ent
*
134 __dsthash_alloc_init(struct ipt_hashlimit_htable
*ht
, struct dsthash_dst
*dst
)
136 struct dsthash_ent
*ent
;
138 /* initialize hash with random val at the time we allocate
139 * the first hashtable entry */
140 if (!ht
->rnd_initialized
) {
141 get_random_bytes(&ht
->rnd
, 4);
142 ht
->rnd_initialized
= 1;
146 atomic_read(&ht
->count
) >= ht
->cfg
.max
) {
147 /* FIXME: do something. question is what.. */
150 "ipt_hashlimit: max count of %u reached\n",
155 ent
= kmem_cache_alloc(hashlimit_cachep
, GFP_ATOMIC
);
159 "ipt_hashlimit: can't allocate dsthash_ent\n");
163 atomic_inc(&ht
->count
);
165 ent
->dst
.dst_ip
= dst
->dst_ip
;
166 ent
->dst
.dst_port
= dst
->dst_port
;
167 ent
->dst
.src_ip
= dst
->src_ip
;
168 ent
->dst
.src_port
= dst
->src_port
;
170 hlist_add_head(&ent
->node
, &ht
->hash
[hash_dst(ht
, dst
)]);
176 __dsthash_free(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*ent
)
178 hlist_del(&ent
->node
);
179 kmem_cache_free(hashlimit_cachep
, ent
);
180 atomic_dec(&ht
->count
);
182 static void htable_gc(unsigned long htlong
);
184 static int htable_create(struct ipt_hashlimit_info
*minfo
)
188 struct ipt_hashlimit_htable
*hinfo
;
191 size
= minfo
->cfg
.size
;
193 size
= (((num_physpages
<< PAGE_SHIFT
) / 16384)
194 / sizeof(struct list_head
));
195 if (num_physpages
> (1024 * 1024 * 1024 / PAGE_SIZE
))
200 /* FIXME: don't use vmalloc() here or anywhere else -HW */
201 hinfo
= vmalloc(sizeof(struct ipt_hashlimit_htable
)
202 + (sizeof(struct list_head
) * size
));
204 printk(KERN_ERR
"ipt_hashlimit: Unable to create hashtable\n");
207 minfo
->hinfo
= hinfo
;
209 /* copy match config into hashtable config */
210 memcpy(&hinfo
->cfg
, &minfo
->cfg
, sizeof(hinfo
->cfg
));
211 hinfo
->cfg
.size
= size
;
213 hinfo
->cfg
.max
= 8 * hinfo
->cfg
.size
;
214 else if (hinfo
->cfg
.max
< hinfo
->cfg
.size
)
215 hinfo
->cfg
.max
= hinfo
->cfg
.size
;
217 for (i
= 0; i
< hinfo
->cfg
.size
; i
++)
218 INIT_HLIST_HEAD(&hinfo
->hash
[i
]);
220 atomic_set(&hinfo
->count
, 0);
221 atomic_set(&hinfo
->use
, 1);
222 hinfo
->rnd_initialized
= 0;
223 spin_lock_init(&hinfo
->lock
);
224 hinfo
->pde
= create_proc_entry(minfo
->name
, 0, hashlimit_procdir
);
229 hinfo
->pde
->proc_fops
= &dl_file_ops
;
230 hinfo
->pde
->data
= hinfo
;
232 init_timer(&hinfo
->timer
);
233 hinfo
->timer
.expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.gc_interval
);
234 hinfo
->timer
.data
= (unsigned long )hinfo
;
235 hinfo
->timer
.function
= htable_gc
;
236 add_timer(&hinfo
->timer
);
238 spin_lock_bh(&hashlimit_lock
);
239 hlist_add_head(&hinfo
->node
, &hashlimit_htables
);
240 spin_unlock_bh(&hashlimit_lock
);
245 static int select_all(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
250 static int select_gc(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
252 return (jiffies
>= he
->expires
);
255 static void htable_selective_cleanup(struct ipt_hashlimit_htable
*ht
,
256 int (*select
)(struct ipt_hashlimit_htable
*ht
,
257 struct dsthash_ent
*he
))
261 IP_NF_ASSERT(ht
->cfg
.size
&& ht
->cfg
.max
);
263 /* lock hash table and iterate over it */
264 spin_lock_bh(&ht
->lock
);
265 for (i
= 0; i
< ht
->cfg
.size
; i
++) {
266 struct dsthash_ent
*dh
;
267 struct hlist_node
*pos
, *n
;
268 hlist_for_each_entry_safe(dh
, pos
, n
, &ht
->hash
[i
], node
) {
269 if ((*select
)(ht
, dh
))
270 __dsthash_free(ht
, dh
);
273 spin_unlock_bh(&ht
->lock
);
276 /* hash table garbage collector, run by timer */
277 static void htable_gc(unsigned long htlong
)
279 struct ipt_hashlimit_htable
*ht
= (struct ipt_hashlimit_htable
*)htlong
;
281 htable_selective_cleanup(ht
, select_gc
);
283 /* re-add the timer accordingly */
284 ht
->timer
.expires
= jiffies
+ msecs_to_jiffies(ht
->cfg
.gc_interval
);
285 add_timer(&ht
->timer
);
288 static void htable_destroy(struct ipt_hashlimit_htable
*hinfo
)
290 /* remove timer, if it is pending */
291 if (timer_pending(&hinfo
->timer
))
292 del_timer(&hinfo
->timer
);
294 /* remove proc entry */
295 remove_proc_entry(hinfo
->pde
->name
, hashlimit_procdir
);
297 htable_selective_cleanup(hinfo
, select_all
);
301 static struct ipt_hashlimit_htable
*htable_find_get(char *name
)
303 struct ipt_hashlimit_htable
*hinfo
;
304 struct hlist_node
*pos
;
306 spin_lock_bh(&hashlimit_lock
);
307 hlist_for_each_entry(hinfo
, pos
, &hashlimit_htables
, node
) {
308 if (!strcmp(name
, hinfo
->pde
->name
)) {
309 atomic_inc(&hinfo
->use
);
310 spin_unlock_bh(&hashlimit_lock
);
314 spin_unlock_bh(&hashlimit_lock
);
319 static void htable_put(struct ipt_hashlimit_htable
*hinfo
)
321 if (atomic_dec_and_test(&hinfo
->use
)) {
322 spin_lock_bh(&hashlimit_lock
);
323 hlist_del(&hinfo
->node
);
324 spin_unlock_bh(&hashlimit_lock
);
325 htable_destroy(hinfo
);
330 /* The algorithm used is the Simple Token Bucket Filter (TBF)
331 * see net/sched/sch_tbf.c in the linux source tree
334 /* Rusty: This is my (non-mathematically-inclined) understanding of
335 this algorithm. The `average rate' in jiffies becomes your initial
336 amount of credit `credit' and the most credit you can ever have
337 `credit_cap'. The `peak rate' becomes the cost of passing the
340 `prev' tracks the last packet hit: you gain one credit per jiffy.
341 If you get credit balance more than this, the extra credit is
342 discarded. Every time the match passes, you lose `cost' credits;
343 if you don't have that many, the test fails.
345 See Alexey's formal explanation in net/sched/sch_tbf.c.
347 To get the maximum range, we multiply by this factor (ie. you get N
348 credits per jiffy). We want to allow a rate as low as 1 per day
349 (slowest userspace tool allows), which means
350 CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32 ie.
352 #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
354 /* Repeated shift and or gives us all 1s, final shift and add 1 gives
355 * us the power of 2 below the theoretical max, so GCC simply does a
357 #define _POW2_BELOW2(x) ((x)|((x)>>1))
358 #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
359 #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
360 #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
361 #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
362 #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
364 #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
366 /* Precision saver. */
367 static inline u_int32_t
368 user2credits(u_int32_t user
)
370 /* If multiplying would overflow... */
371 if (user
> 0xFFFFFFFF / (HZ
*CREDITS_PER_JIFFY
))
373 return (user
/ IPT_HASHLIMIT_SCALE
) * HZ
* CREDITS_PER_JIFFY
;
375 return (user
* HZ
* CREDITS_PER_JIFFY
) / IPT_HASHLIMIT_SCALE
;
378 static inline void rateinfo_recalc(struct dsthash_ent
*dh
, unsigned long now
)
380 dh
->rateinfo
.credit
+= (now
- xchg(&dh
->rateinfo
.prev
, now
))
382 if (dh
->rateinfo
.credit
> dh
->rateinfo
.credit_cap
)
383 dh
->rateinfo
.credit
= dh
->rateinfo
.credit_cap
;
387 hashlimit_match(const struct sk_buff
*skb
,
388 const struct net_device
*in
,
389 const struct net_device
*out
,
390 const struct xt_match
*match
,
391 const void *matchinfo
,
393 unsigned int protoff
,
396 struct ipt_hashlimit_info
*r
=
397 ((struct ipt_hashlimit_info
*)matchinfo
)->u
.master
;
398 struct ipt_hashlimit_htable
*hinfo
= r
->hinfo
;
399 unsigned long now
= jiffies
;
400 struct dsthash_ent
*dh
;
401 struct dsthash_dst dst
;
403 /* build 'dst' according to hinfo->cfg and current packet */
404 memset(&dst
, 0, sizeof(dst
));
405 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DIP
)
406 dst
.dst_ip
= skb
->nh
.iph
->daddr
;
407 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SIP
)
408 dst
.src_ip
= skb
->nh
.iph
->saddr
;
409 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
410 ||hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
) {
411 __be16 _ports
[2], *ports
;
413 switch (skb
->nh
.iph
->protocol
) {
418 ports
= skb_header_pointer(skb
, skb
->nh
.iph
->ihl
*4,
419 sizeof(_ports
), &_ports
);
422 _ports
[0] = _ports
[1] = 0;
427 /* We've been asked to examine this packet, and we
428 can't. Hence, no choice but to drop. */
432 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
)
433 dst
.src_port
= ports
[0];
434 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
)
435 dst
.dst_port
= ports
[1];
438 spin_lock_bh(&hinfo
->lock
);
439 dh
= __dsthash_find(hinfo
, &dst
);
441 dh
= __dsthash_alloc_init(hinfo
, &dst
);
444 /* enomem... don't match == DROP */
446 printk(KERN_ERR
"%s: ENOMEM\n", __FUNCTION__
);
447 spin_unlock_bh(&hinfo
->lock
);
451 dh
->expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
453 dh
->rateinfo
.prev
= jiffies
;
454 dh
->rateinfo
.credit
= user2credits(hinfo
->cfg
.avg
*
456 dh
->rateinfo
.credit_cap
= user2credits(hinfo
->cfg
.avg
*
458 dh
->rateinfo
.cost
= user2credits(hinfo
->cfg
.avg
);
460 /* update expiration timeout */
461 dh
->expires
= now
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
462 rateinfo_recalc(dh
, now
);
465 if (dh
->rateinfo
.credit
>= dh
->rateinfo
.cost
) {
466 /* We're underlimit. */
467 dh
->rateinfo
.credit
-= dh
->rateinfo
.cost
;
468 spin_unlock_bh(&hinfo
->lock
);
472 spin_unlock_bh(&hinfo
->lock
);
474 /* default case: we're overlimit, thus don't match */
479 hashlimit_checkentry(const char *tablename
,
481 const struct xt_match
*match
,
483 unsigned int hook_mask
)
485 struct ipt_hashlimit_info
*r
= matchinfo
;
487 /* Check for overflow. */
488 if (r
->cfg
.burst
== 0
489 || user2credits(r
->cfg
.avg
* r
->cfg
.burst
) <
490 user2credits(r
->cfg
.avg
)) {
491 printk(KERN_ERR
"ipt_hashlimit: Overflow, try lower: %u/%u\n",
492 r
->cfg
.avg
, r
->cfg
.burst
);
497 || r
->cfg
.mode
> (IPT_HASHLIMIT_HASH_DPT
498 |IPT_HASHLIMIT_HASH_DIP
499 |IPT_HASHLIMIT_HASH_SIP
500 |IPT_HASHLIMIT_HASH_SPT
))
503 if (!r
->cfg
.gc_interval
)
509 if (r
->name
[sizeof(r
->name
) - 1] != '\0')
512 /* This is the best we've got: We cannot release and re-grab lock,
513 * since checkentry() is called before ip_tables.c grabs ipt_mutex.
514 * We also cannot grab the hashtable spinlock, since htable_create will
515 * call vmalloc, and that can sleep. And we cannot just re-search
516 * the list of htable's in htable_create(), since then we would
517 * create duplicate proc files. -HW */
518 mutex_lock(&hlimit_mutex
);
519 r
->hinfo
= htable_find_get(r
->name
);
520 if (!r
->hinfo
&& (htable_create(r
) != 0)) {
521 mutex_unlock(&hlimit_mutex
);
524 mutex_unlock(&hlimit_mutex
);
526 /* Ugly hack: For SMP, we only want to use one set */
533 hashlimit_destroy(const struct xt_match
*match
, void *matchinfo
)
535 struct ipt_hashlimit_info
*r
= matchinfo
;
537 htable_put(r
->hinfo
);
541 struct compat_ipt_hashlimit_info
{
543 struct hashlimit_cfg cfg
;
545 compat_uptr_t master
;
548 static void compat_from_user(void *dst
, void *src
)
550 int off
= offsetof(struct compat_ipt_hashlimit_info
, hinfo
);
552 memcpy(dst
, src
, off
);
553 memset(dst
+ off
, 0, sizeof(struct compat_ipt_hashlimit_info
) - off
);
556 static int compat_to_user(void __user
*dst
, void *src
)
558 int off
= offsetof(struct compat_ipt_hashlimit_info
, hinfo
);
560 return copy_to_user(dst
, src
, off
) ? -EFAULT
: 0;
564 static struct ipt_match ipt_hashlimit
= {
566 .match
= hashlimit_match
,
567 .matchsize
= sizeof(struct ipt_hashlimit_info
),
569 .compatsize
= sizeof(struct compat_ipt_hashlimit_info
),
570 .compat_from_user
= compat_from_user
,
571 .compat_to_user
= compat_to_user
,
573 .checkentry
= hashlimit_checkentry
,
574 .destroy
= hashlimit_destroy
,
580 static void *dl_seq_start(struct seq_file
*s
, loff_t
*pos
)
582 struct proc_dir_entry
*pde
= s
->private;
583 struct ipt_hashlimit_htable
*htable
= pde
->data
;
584 unsigned int *bucket
;
586 spin_lock_bh(&htable
->lock
);
587 if (*pos
>= htable
->cfg
.size
)
590 bucket
= kmalloc(sizeof(unsigned int), GFP_ATOMIC
);
592 return ERR_PTR(-ENOMEM
);
598 static void *dl_seq_next(struct seq_file
*s
, void *v
, loff_t
*pos
)
600 struct proc_dir_entry
*pde
= s
->private;
601 struct ipt_hashlimit_htable
*htable
= pde
->data
;
602 unsigned int *bucket
= (unsigned int *)v
;
605 if (*pos
>= htable
->cfg
.size
) {
612 static void dl_seq_stop(struct seq_file
*s
, void *v
)
614 struct proc_dir_entry
*pde
= s
->private;
615 struct ipt_hashlimit_htable
*htable
= pde
->data
;
616 unsigned int *bucket
= (unsigned int *)v
;
620 spin_unlock_bh(&htable
->lock
);
623 static inline int dl_seq_real_show(struct dsthash_ent
*ent
, struct seq_file
*s
)
625 /* recalculate to show accurate numbers */
626 rateinfo_recalc(ent
, jiffies
);
628 return seq_printf(s
, "%ld %u.%u.%u.%u:%u->%u.%u.%u.%u:%u %u %u %u\n",
629 (long)(ent
->expires
- jiffies
)/HZ
,
630 NIPQUAD(ent
->dst
.src_ip
), ntohs(ent
->dst
.src_port
),
631 NIPQUAD(ent
->dst
.dst_ip
), ntohs(ent
->dst
.dst_port
),
632 ent
->rateinfo
.credit
, ent
->rateinfo
.credit_cap
,
636 static int dl_seq_show(struct seq_file
*s
, void *v
)
638 struct proc_dir_entry
*pde
= s
->private;
639 struct ipt_hashlimit_htable
*htable
= pde
->data
;
640 unsigned int *bucket
= (unsigned int *)v
;
641 struct dsthash_ent
*ent
;
642 struct hlist_node
*pos
;
644 if (!hlist_empty(&htable
->hash
[*bucket
]))
645 hlist_for_each_entry(ent
, pos
, &htable
->hash
[*bucket
], node
) {
646 if (dl_seq_real_show(ent
, s
)) {
647 /* buffer was filled and unable to print that tuple */
655 static struct seq_operations dl_seq_ops
= {
656 .start
= dl_seq_start
,
662 static int dl_proc_open(struct inode
*inode
, struct file
*file
)
664 int ret
= seq_open(file
, &dl_seq_ops
);
667 struct seq_file
*sf
= file
->private_data
;
668 sf
->private = PDE(inode
);
673 static struct file_operations dl_file_ops
= {
674 .owner
= THIS_MODULE
,
675 .open
= dl_proc_open
,
678 .release
= seq_release
681 static int init_or_fini(int fini
)
688 if (ipt_register_match(&ipt_hashlimit
)) {
690 goto cleanup_nothing
;
693 hashlimit_cachep
= kmem_cache_create("ipt_hashlimit",
694 sizeof(struct dsthash_ent
), 0,
696 if (!hashlimit_cachep
) {
697 printk(KERN_ERR
"Unable to create ipt_hashlimit slab cache\n");
699 goto cleanup_unreg_match
;
702 hashlimit_procdir
= proc_mkdir("ipt_hashlimit", proc_net
);
703 if (!hashlimit_procdir
) {
704 printk(KERN_ERR
"Unable to create proc dir entry\n");
706 goto cleanup_free_slab
;
712 remove_proc_entry("ipt_hashlimit", proc_net
);
714 kmem_cache_destroy(hashlimit_cachep
);
716 ipt_unregister_match(&ipt_hashlimit
);
722 static int __init
ipt_hashlimit_init(void)
724 return init_or_fini(0);
727 static void __exit
ipt_hashlimit_fini(void)
732 module_init(ipt_hashlimit_init
);
733 module_exit(ipt_hashlimit_fini
);