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/tcp.h>
32 #include <linux/udp.h>
33 #include <linux/sctp.h>
34 #include <linux/proc_fs.h>
35 #include <linux/seq_file.h>
36 #include <linux/list.h>
38 #include <linux/netfilter_ipv4/ip_tables.h>
39 #include <linux/netfilter_ipv4/ipt_hashlimit.h>
41 /* FIXME: this is just for IP_NF_ASSERRT */
42 #include <linux/netfilter_ipv4/ip_conntrack.h>
44 MODULE_LICENSE("GPL");
45 MODULE_AUTHOR("Harald Welte <laforge@netfilter.org>");
46 MODULE_DESCRIPTION("iptables match for limiting per hash-bucket");
48 /* need to declare this at the top */
49 static struct proc_dir_entry
*hashlimit_procdir
;
50 static struct file_operations dl_file_ops
;
57 /* ports have to be consecutive !!! */
63 /* static / read-only parts in the beginning */
64 struct hlist_node node
;
65 struct dsthash_dst dst
;
67 /* modified structure members in the end */
68 unsigned long expires
; /* precalculated expiry time */
70 unsigned long prev
; /* last modification */
72 u_int32_t credit_cap
, cost
;
76 struct ipt_hashlimit_htable
{
77 struct hlist_node node
; /* global list of all htables */
80 struct hashlimit_cfg cfg
; /* config */
83 spinlock_t lock
; /* lock for list_head */
84 u_int32_t rnd
; /* random seed for hash */
85 struct timer_list timer
; /* timer for gc */
86 atomic_t count
; /* number entries in table */
89 struct proc_dir_entry
*pde
;
91 struct hlist_head hash
[0]; /* hashtable itself */
94 static DEFINE_SPINLOCK(hashlimit_lock
); /* protects htables list */
95 static DECLARE_MUTEX(hlimit_mutex
); /* additional checkentry protection */
96 static HLIST_HEAD(hashlimit_htables
);
97 static kmem_cache_t
*hashlimit_cachep
;
99 static inline int dst_cmp(const struct dsthash_ent
*ent
, struct dsthash_dst
*b
)
101 return (ent
->dst
.dst_ip
== b
->dst_ip
102 && ent
->dst
.dst_port
== b
->dst_port
103 && ent
->dst
.src_port
== b
->src_port
104 && ent
->dst
.src_ip
== b
->src_ip
);
107 static inline u_int32_t
108 hash_dst(const struct ipt_hashlimit_htable
*ht
, const struct dsthash_dst
*dst
)
110 return (jhash_3words(dst
->dst_ip
, (dst
->dst_port
<<16 | dst
->src_port
),
111 dst
->src_ip
, ht
->rnd
) % ht
->cfg
.size
);
114 static inline struct dsthash_ent
*
115 __dsthash_find(const struct ipt_hashlimit_htable
*ht
, struct dsthash_dst
*dst
)
117 struct dsthash_ent
*ent
;
118 struct hlist_node
*pos
;
119 u_int32_t hash
= hash_dst(ht
, dst
);
121 if (!hlist_empty(&ht
->hash
[hash
]))
122 hlist_for_each_entry(ent
, pos
, &ht
->hash
[hash
], node
) {
123 if (dst_cmp(ent
, dst
)) {
131 /* allocate dsthash_ent, initialize dst, put in htable and lock it */
132 static struct dsthash_ent
*
133 __dsthash_alloc_init(struct ipt_hashlimit_htable
*ht
, struct dsthash_dst
*dst
)
135 struct dsthash_ent
*ent
;
137 /* initialize hash with random val at the time we allocate
138 * the first hashtable entry */
140 get_random_bytes(&ht
->rnd
, 4);
143 atomic_read(&ht
->count
) >= ht
->cfg
.max
) {
144 /* FIXME: do something. question is what.. */
147 "ipt_hashlimit: max count of %u reached\n",
152 ent
= kmem_cache_alloc(hashlimit_cachep
, GFP_ATOMIC
);
156 "ipt_hashlimit: can't allocate dsthash_ent\n");
160 atomic_inc(&ht
->count
);
162 ent
->dst
.dst_ip
= dst
->dst_ip
;
163 ent
->dst
.dst_port
= dst
->dst_port
;
164 ent
->dst
.src_ip
= dst
->src_ip
;
165 ent
->dst
.src_port
= dst
->src_port
;
167 hlist_add_head(&ent
->node
, &ht
->hash
[hash_dst(ht
, dst
)]);
173 __dsthash_free(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*ent
)
175 hlist_del(&ent
->node
);
176 kmem_cache_free(hashlimit_cachep
, ent
);
177 atomic_dec(&ht
->count
);
179 static void htable_gc(unsigned long htlong
);
181 static int htable_create(struct ipt_hashlimit_info
*minfo
)
185 struct ipt_hashlimit_htable
*hinfo
;
188 size
= minfo
->cfg
.size
;
190 size
= (((num_physpages
<< PAGE_SHIFT
) / 16384)
191 / sizeof(struct list_head
));
192 if (num_physpages
> (1024 * 1024 * 1024 / PAGE_SIZE
))
197 /* FIXME: don't use vmalloc() here or anywhere else -HW */
198 hinfo
= vmalloc(sizeof(struct ipt_hashlimit_htable
)
199 + (sizeof(struct list_head
) * size
));
201 printk(KERN_ERR
"ipt_hashlimit: Unable to create hashtable\n");
204 minfo
->hinfo
= hinfo
;
206 /* copy match config into hashtable config */
207 memcpy(&hinfo
->cfg
, &minfo
->cfg
, sizeof(hinfo
->cfg
));
208 hinfo
->cfg
.size
= size
;
210 hinfo
->cfg
.max
= 8 * hinfo
->cfg
.size
;
211 else if (hinfo
->cfg
.max
< hinfo
->cfg
.size
)
212 hinfo
->cfg
.max
= hinfo
->cfg
.size
;
214 for (i
= 0; i
< hinfo
->cfg
.size
; i
++)
215 INIT_HLIST_HEAD(&hinfo
->hash
[i
]);
217 atomic_set(&hinfo
->count
, 0);
218 atomic_set(&hinfo
->use
, 1);
220 spin_lock_init(&hinfo
->lock
);
221 hinfo
->pde
= create_proc_entry(minfo
->name
, 0, hashlimit_procdir
);
226 hinfo
->pde
->proc_fops
= &dl_file_ops
;
227 hinfo
->pde
->data
= hinfo
;
229 init_timer(&hinfo
->timer
);
230 hinfo
->timer
.expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.gc_interval
);
231 hinfo
->timer
.data
= (unsigned long )hinfo
;
232 hinfo
->timer
.function
= htable_gc
;
233 add_timer(&hinfo
->timer
);
235 spin_lock_bh(&hashlimit_lock
);
236 hlist_add_head(&hinfo
->node
, &hashlimit_htables
);
237 spin_unlock_bh(&hashlimit_lock
);
242 static int select_all(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
247 static int select_gc(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
249 return (jiffies
>= he
->expires
);
252 static void htable_selective_cleanup(struct ipt_hashlimit_htable
*ht
,
253 int (*select
)(struct ipt_hashlimit_htable
*ht
,
254 struct dsthash_ent
*he
))
258 IP_NF_ASSERT(ht
->cfg
.size
&& ht
->cfg
.max
);
260 /* lock hash table and iterate over it */
261 spin_lock_bh(&ht
->lock
);
262 for (i
= 0; i
< ht
->cfg
.size
; i
++) {
263 struct dsthash_ent
*dh
;
264 struct hlist_node
*pos
, *n
;
265 hlist_for_each_entry_safe(dh
, pos
, n
, &ht
->hash
[i
], node
) {
266 if ((*select
)(ht
, dh
))
267 __dsthash_free(ht
, dh
);
270 spin_unlock_bh(&ht
->lock
);
273 /* hash table garbage collector, run by timer */
274 static void htable_gc(unsigned long htlong
)
276 struct ipt_hashlimit_htable
*ht
= (struct ipt_hashlimit_htable
*)htlong
;
278 htable_selective_cleanup(ht
, select_gc
);
280 /* re-add the timer accordingly */
281 ht
->timer
.expires
= jiffies
+ msecs_to_jiffies(ht
->cfg
.gc_interval
);
282 add_timer(&ht
->timer
);
285 static void htable_destroy(struct ipt_hashlimit_htable
*hinfo
)
287 /* remove timer, if it is pending */
288 if (timer_pending(&hinfo
->timer
))
289 del_timer(&hinfo
->timer
);
291 /* remove proc entry */
292 remove_proc_entry(hinfo
->pde
->name
, hashlimit_procdir
);
294 htable_selective_cleanup(hinfo
, select_all
);
298 static struct ipt_hashlimit_htable
*htable_find_get(char *name
)
300 struct ipt_hashlimit_htable
*hinfo
;
301 struct hlist_node
*pos
;
303 spin_lock_bh(&hashlimit_lock
);
304 hlist_for_each_entry(hinfo
, pos
, &hashlimit_htables
, node
) {
305 if (!strcmp(name
, hinfo
->pde
->name
)) {
306 atomic_inc(&hinfo
->use
);
307 spin_unlock_bh(&hashlimit_lock
);
311 spin_unlock_bh(&hashlimit_lock
);
316 static void htable_put(struct ipt_hashlimit_htable
*hinfo
)
318 if (atomic_dec_and_test(&hinfo
->use
)) {
319 spin_lock_bh(&hashlimit_lock
);
320 hlist_del(&hinfo
->node
);
321 spin_unlock_bh(&hashlimit_lock
);
322 htable_destroy(hinfo
);
327 /* The algorithm used is the Simple Token Bucket Filter (TBF)
328 * see net/sched/sch_tbf.c in the linux source tree
331 /* Rusty: This is my (non-mathematically-inclined) understanding of
332 this algorithm. The `average rate' in jiffies becomes your initial
333 amount of credit `credit' and the most credit you can ever have
334 `credit_cap'. The `peak rate' becomes the cost of passing the
337 `prev' tracks the last packet hit: you gain one credit per jiffy.
338 If you get credit balance more than this, the extra credit is
339 discarded. Every time the match passes, you lose `cost' credits;
340 if you don't have that many, the test fails.
342 See Alexey's formal explanation in net/sched/sch_tbf.c.
344 To get the maximum range, we multiply by this factor (ie. you get N
345 credits per jiffy). We want to allow a rate as low as 1 per day
346 (slowest userspace tool allows), which means
347 CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32 ie.
349 #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
351 /* Repeated shift and or gives us all 1s, final shift and add 1 gives
352 * us the power of 2 below the theoretical max, so GCC simply does a
354 #define _POW2_BELOW2(x) ((x)|((x)>>1))
355 #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
356 #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
357 #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
358 #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
359 #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
361 #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
363 /* Precision saver. */
364 static inline u_int32_t
365 user2credits(u_int32_t user
)
367 /* If multiplying would overflow... */
368 if (user
> 0xFFFFFFFF / (HZ
*CREDITS_PER_JIFFY
))
370 return (user
/ IPT_HASHLIMIT_SCALE
) * HZ
* CREDITS_PER_JIFFY
;
372 return (user
* HZ
* CREDITS_PER_JIFFY
) / IPT_HASHLIMIT_SCALE
;
375 static inline void rateinfo_recalc(struct dsthash_ent
*dh
, unsigned long now
)
377 dh
->rateinfo
.credit
+= (now
- xchg(&dh
->rateinfo
.prev
, now
))
379 if (dh
->rateinfo
.credit
> dh
->rateinfo
.credit_cap
)
380 dh
->rateinfo
.credit
= dh
->rateinfo
.credit_cap
;
383 static inline int get_ports(const struct sk_buff
*skb
, int offset
,
389 sctp_sctphdr_t sctph
;
392 /* Must not be a fragment. */
396 /* Must be big enough to read ports (both UDP and TCP have
397 them at the start). */
398 ptr_u
= skb_header_pointer(skb
, skb
->nh
.iph
->ihl
*4, 8, &hdr_u
);
402 switch (skb
->nh
.iph
->protocol
) {
404 ports
[0] = ptr_u
->th
.source
;
405 ports
[1] = ptr_u
->th
.dest
;
408 ports
[0] = ptr_u
->uh
.source
;
409 ports
[1] = ptr_u
->uh
.dest
;
412 ports
[0] = ptr_u
->sctph
.source
;
413 ports
[1] = ptr_u
->sctph
.dest
;
416 /* all other protocols don't supprot per-port hash
418 ports
[0] = ports
[1] = 0;
427 hashlimit_match(const struct sk_buff
*skb
,
428 const struct net_device
*in
,
429 const struct net_device
*out
,
430 const void *matchinfo
,
434 struct ipt_hashlimit_info
*r
=
435 ((struct ipt_hashlimit_info
*)matchinfo
)->u
.master
;
436 struct ipt_hashlimit_htable
*hinfo
= r
->hinfo
;
437 unsigned long now
= jiffies
;
438 struct dsthash_ent
*dh
;
439 struct dsthash_dst dst
;
441 /* build 'dst' according to hinfo->cfg and current packet */
442 memset(&dst
, 0, sizeof(dst
));
443 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DIP
)
444 dst
.dst_ip
= skb
->nh
.iph
->daddr
;
445 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SIP
)
446 dst
.src_ip
= skb
->nh
.iph
->saddr
;
447 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
448 ||hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
) {
450 if (get_ports(skb
, offset
, ports
)) {
451 /* We've been asked to examine this packet, and we
452 can't. Hence, no choice but to drop. */
456 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
)
457 dst
.src_port
= ports
[0];
458 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
)
459 dst
.dst_port
= ports
[1];
462 spin_lock_bh(&hinfo
->lock
);
463 dh
= __dsthash_find(hinfo
, &dst
);
465 dh
= __dsthash_alloc_init(hinfo
, &dst
);
468 /* enomem... don't match == DROP */
470 printk(KERN_ERR
"%s: ENOMEM\n", __FUNCTION__
);
471 spin_unlock_bh(&hinfo
->lock
);
475 dh
->expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
477 dh
->rateinfo
.prev
= jiffies
;
478 dh
->rateinfo
.credit
= user2credits(hinfo
->cfg
.avg
*
480 dh
->rateinfo
.credit_cap
= user2credits(hinfo
->cfg
.avg
*
482 dh
->rateinfo
.cost
= user2credits(hinfo
->cfg
.avg
);
484 spin_unlock_bh(&hinfo
->lock
);
488 /* update expiration timeout */
489 dh
->expires
= now
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
491 rateinfo_recalc(dh
, now
);
492 if (dh
->rateinfo
.credit
>= dh
->rateinfo
.cost
) {
493 /* We're underlimit. */
494 dh
->rateinfo
.credit
-= dh
->rateinfo
.cost
;
495 spin_unlock_bh(&hinfo
->lock
);
499 spin_unlock_bh(&hinfo
->lock
);
501 /* default case: we're overlimit, thus don't match */
506 hashlimit_checkentry(const char *tablename
,
507 const struct ipt_ip
*ip
,
509 unsigned int matchsize
,
510 unsigned int hook_mask
)
512 struct ipt_hashlimit_info
*r
= matchinfo
;
514 if (matchsize
!= IPT_ALIGN(sizeof(struct ipt_hashlimit_info
)))
517 /* Check for overflow. */
518 if (r
->cfg
.burst
== 0
519 || user2credits(r
->cfg
.avg
* r
->cfg
.burst
) <
520 user2credits(r
->cfg
.avg
)) {
521 printk(KERN_ERR
"ipt_hashlimit: Overflow, try lower: %u/%u\n",
522 r
->cfg
.avg
, r
->cfg
.burst
);
527 || r
->cfg
.mode
> (IPT_HASHLIMIT_HASH_DPT
528 |IPT_HASHLIMIT_HASH_DIP
529 |IPT_HASHLIMIT_HASH_SIP
530 |IPT_HASHLIMIT_HASH_SPT
))
533 if (!r
->cfg
.gc_interval
)
539 /* This is the best we've got: We cannot release and re-grab lock,
540 * since checkentry() is called before ip_tables.c grabs ipt_mutex.
541 * We also cannot grab the hashtable spinlock, since htable_create will
542 * call vmalloc, and that can sleep. And we cannot just re-search
543 * the list of htable's in htable_create(), since then we would
544 * create duplicate proc files. -HW */
546 r
->hinfo
= htable_find_get(r
->name
);
547 if (!r
->hinfo
&& (htable_create(r
) != 0)) {
553 /* Ugly hack: For SMP, we only want to use one set */
560 hashlimit_destroy(void *matchinfo
, unsigned int matchsize
)
562 struct ipt_hashlimit_info
*r
= (struct ipt_hashlimit_info
*) matchinfo
;
564 htable_put(r
->hinfo
);
567 static struct ipt_match ipt_hashlimit
= {
569 .match
= hashlimit_match
,
570 .checkentry
= hashlimit_checkentry
,
571 .destroy
= hashlimit_destroy
,
577 static void *dl_seq_start(struct seq_file
*s
, loff_t
*pos
)
579 struct proc_dir_entry
*pde
= s
->private;
580 struct ipt_hashlimit_htable
*htable
= pde
->data
;
581 unsigned int *bucket
;
583 spin_lock_bh(&htable
->lock
);
584 if (*pos
>= htable
->cfg
.size
)
587 bucket
= kmalloc(sizeof(unsigned int), GFP_ATOMIC
);
589 return ERR_PTR(-ENOMEM
);
595 static void *dl_seq_next(struct seq_file
*s
, void *v
, loff_t
*pos
)
597 struct proc_dir_entry
*pde
= s
->private;
598 struct ipt_hashlimit_htable
*htable
= pde
->data
;
599 unsigned int *bucket
= (unsigned int *)v
;
602 if (*pos
>= htable
->cfg
.size
) {
609 static void dl_seq_stop(struct seq_file
*s
, void *v
)
611 struct proc_dir_entry
*pde
= s
->private;
612 struct ipt_hashlimit_htable
*htable
= pde
->data
;
613 unsigned int *bucket
= (unsigned int *)v
;
617 spin_unlock_bh(&htable
->lock
);
620 static inline int dl_seq_real_show(struct dsthash_ent
*ent
, struct seq_file
*s
)
622 /* recalculate to show accurate numbers */
623 rateinfo_recalc(ent
, jiffies
);
625 return seq_printf(s
, "%ld %u.%u.%u.%u:%u->%u.%u.%u.%u:%u %u %u %u\n",
626 (long)(ent
->expires
- jiffies
)/HZ
,
627 NIPQUAD(ent
->dst
.src_ip
), ntohs(ent
->dst
.src_port
),
628 NIPQUAD(ent
->dst
.dst_ip
), ntohs(ent
->dst
.dst_port
),
629 ent
->rateinfo
.credit
, ent
->rateinfo
.credit_cap
,
633 static int dl_seq_show(struct seq_file
*s
, void *v
)
635 struct proc_dir_entry
*pde
= s
->private;
636 struct ipt_hashlimit_htable
*htable
= pde
->data
;
637 unsigned int *bucket
= (unsigned int *)v
;
638 struct dsthash_ent
*ent
;
639 struct hlist_node
*pos
;
641 if (!hlist_empty(&htable
->hash
[*bucket
]))
642 hlist_for_each_entry(ent
, pos
, &htable
->hash
[*bucket
], node
) {
643 if (dl_seq_real_show(ent
, s
)) {
644 /* buffer was filled and unable to print that tuple */
652 static struct seq_operations dl_seq_ops
= {
653 .start
= dl_seq_start
,
659 static int dl_proc_open(struct inode
*inode
, struct file
*file
)
661 int ret
= seq_open(file
, &dl_seq_ops
);
664 struct seq_file
*sf
= file
->private_data
;
665 sf
->private = PDE(inode
);
670 static struct file_operations dl_file_ops
= {
671 .owner
= THIS_MODULE
,
672 .open
= dl_proc_open
,
675 .release
= seq_release
678 static int init_or_fini(int fini
)
685 if (ipt_register_match(&ipt_hashlimit
)) {
687 goto cleanup_nothing
;
690 hashlimit_cachep
= kmem_cache_create("ipt_hashlimit",
691 sizeof(struct dsthash_ent
), 0,
693 if (!hashlimit_cachep
) {
694 printk(KERN_ERR
"Unable to create ipt_hashlimit slab cache\n");
696 goto cleanup_unreg_match
;
699 hashlimit_procdir
= proc_mkdir("ipt_hashlimit", proc_net
);
700 if (!hashlimit_procdir
) {
701 printk(KERN_ERR
"Unable to create proc dir entry\n");
703 goto cleanup_free_slab
;
709 remove_proc_entry("ipt_hashlimit", proc_net
);
711 kmem_cache_destroy(hashlimit_cachep
);
713 ipt_unregister_match(&ipt_hashlimit
);
719 static int __init
init(void)
721 return init_or_fini(0);
724 static void __exit
fini(void)