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>
40 #include <linux/netfilter_ipv4/lockhelp.h>
42 /* FIXME: this is just for IP_NF_ASSERRT */
43 #include <linux/netfilter_ipv4/ip_conntrack.h>
45 MODULE_LICENSE("GPL");
46 MODULE_AUTHOR("Harald Welte <laforge@netfilter.org>");
47 MODULE_DESCRIPTION("iptables match for limiting per hash-bucket");
49 /* need to declare this at the top */
50 static struct proc_dir_entry
*hashlimit_procdir
;
51 static struct file_operations dl_file_ops
;
58 /* ports have to be consecutive !!! */
64 /* static / read-only parts in the beginning */
65 struct hlist_node node
;
66 struct dsthash_dst dst
;
68 /* modified structure members in the end */
69 unsigned long expires
; /* precalculated expiry time */
71 unsigned long prev
; /* last modification */
73 u_int32_t credit_cap
, cost
;
77 struct ipt_hashlimit_htable
{
78 struct hlist_node node
; /* global list of all htables */
81 struct hashlimit_cfg cfg
; /* config */
84 spinlock_t lock
; /* lock for list_head */
85 u_int32_t rnd
; /* random seed for hash */
86 struct timer_list timer
; /* timer for gc */
87 atomic_t count
; /* number entries in table */
90 struct proc_dir_entry
*pde
;
92 struct hlist_head hash
[0]; /* hashtable itself */
95 static DECLARE_LOCK(hashlimit_lock
); /* protects htables list */
96 static DECLARE_MUTEX(hlimit_mutex
); /* additional checkentry protection */
97 static HLIST_HEAD(hashlimit_htables
);
98 static kmem_cache_t
*hashlimit_cachep
;
100 static inline int dst_cmp(const struct dsthash_ent
*ent
, struct dsthash_dst
*b
)
102 return (ent
->dst
.dst_ip
== b
->dst_ip
103 && ent
->dst
.dst_port
== b
->dst_port
104 && ent
->dst
.src_port
== b
->src_port
105 && ent
->dst
.src_ip
== b
->src_ip
);
108 static inline u_int32_t
109 hash_dst(const struct ipt_hashlimit_htable
*ht
, const struct dsthash_dst
*dst
)
111 return (jhash_3words(dst
->dst_ip
, (dst
->dst_port
<<16 | dst
->src_port
),
112 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 */
141 get_random_bytes(&ht
->rnd
, 4);
144 atomic_read(&ht
->count
) >= ht
->cfg
.max
) {
145 /* FIXME: do something. question is what.. */
148 "ipt_hashlimit: max count of %u reached\n",
153 ent
= kmem_cache_alloc(hashlimit_cachep
, GFP_ATOMIC
);
157 "ipt_hashlimit: can't allocate dsthash_ent\n");
161 atomic_inc(&ht
->count
);
163 ent
->dst
.dst_ip
= dst
->dst_ip
;
164 ent
->dst
.dst_port
= dst
->dst_port
;
165 ent
->dst
.src_ip
= dst
->src_ip
;
166 ent
->dst
.src_port
= dst
->src_port
;
168 hlist_add_head(&ent
->node
, &ht
->hash
[hash_dst(ht
, dst
)]);
174 __dsthash_free(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*ent
)
176 hlist_del(&ent
->node
);
177 kmem_cache_free(hashlimit_cachep
, ent
);
178 atomic_dec(&ht
->count
);
180 static void htable_gc(unsigned long htlong
);
182 static int htable_create(struct ipt_hashlimit_info
*minfo
)
186 struct ipt_hashlimit_htable
*hinfo
;
189 size
= minfo
->cfg
.size
;
191 size
= (((num_physpages
<< PAGE_SHIFT
) / 16384)
192 / sizeof(struct list_head
));
193 if (num_physpages
> (1024 * 1024 * 1024 / PAGE_SIZE
))
198 /* FIXME: don't use vmalloc() here or anywhere else -HW */
199 hinfo
= vmalloc(sizeof(struct ipt_hashlimit_htable
)
200 + (sizeof(struct list_head
) * size
));
202 printk(KERN_ERR
"ipt_hashlimit: Unable to create hashtable\n");
205 minfo
->hinfo
= hinfo
;
207 /* copy match config into hashtable config */
208 memcpy(&hinfo
->cfg
, &minfo
->cfg
, sizeof(hinfo
->cfg
));
209 hinfo
->cfg
.size
= size
;
211 hinfo
->cfg
.max
= 8 * hinfo
->cfg
.size
;
212 else if (hinfo
->cfg
.max
< hinfo
->cfg
.size
)
213 hinfo
->cfg
.max
= hinfo
->cfg
.size
;
215 for (i
= 0; i
< hinfo
->cfg
.size
; i
++)
216 INIT_HLIST_HEAD(&hinfo
->hash
[i
]);
218 atomic_set(&hinfo
->count
, 0);
219 atomic_set(&hinfo
->use
, 1);
221 spin_lock_init(&hinfo
->lock
);
222 hinfo
->pde
= create_proc_entry(minfo
->name
, 0, hashlimit_procdir
);
227 hinfo
->pde
->proc_fops
= &dl_file_ops
;
228 hinfo
->pde
->data
= hinfo
;
230 init_timer(&hinfo
->timer
);
231 hinfo
->timer
.expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.gc_interval
);
232 hinfo
->timer
.data
= (unsigned long )hinfo
;
233 hinfo
->timer
.function
= htable_gc
;
234 add_timer(&hinfo
->timer
);
236 LOCK_BH(&hashlimit_lock
);
237 hlist_add_head(&hinfo
->node
, &hashlimit_htables
);
238 UNLOCK_BH(&hashlimit_lock
);
243 static int select_all(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
248 static int select_gc(struct ipt_hashlimit_htable
*ht
, struct dsthash_ent
*he
)
250 return (jiffies
>= he
->expires
);
253 static void htable_selective_cleanup(struct ipt_hashlimit_htable
*ht
,
254 int (*select
)(struct ipt_hashlimit_htable
*ht
,
255 struct dsthash_ent
*he
))
259 IP_NF_ASSERT(ht
->cfg
.size
&& ht
->cfg
.max
);
261 /* lock hash table and iterate over it */
262 spin_lock_bh(&ht
->lock
);
263 for (i
= 0; i
< ht
->cfg
.size
; i
++) {
264 struct dsthash_ent
*dh
;
265 struct hlist_node
*pos
, *n
;
266 hlist_for_each_entry_safe(dh
, pos
, n
, &ht
->hash
[i
], node
) {
267 if ((*select
)(ht
, dh
))
268 __dsthash_free(ht
, dh
);
271 spin_unlock_bh(&ht
->lock
);
274 /* hash table garbage collector, run by timer */
275 static void htable_gc(unsigned long htlong
)
277 struct ipt_hashlimit_htable
*ht
= (struct ipt_hashlimit_htable
*)htlong
;
279 htable_selective_cleanup(ht
, select_gc
);
281 /* re-add the timer accordingly */
282 ht
->timer
.expires
= jiffies
+ msecs_to_jiffies(ht
->cfg
.gc_interval
);
283 add_timer(&ht
->timer
);
286 static void htable_destroy(struct ipt_hashlimit_htable
*hinfo
)
288 /* remove timer, if it is pending */
289 if (timer_pending(&hinfo
->timer
))
290 del_timer(&hinfo
->timer
);
292 /* remove proc entry */
293 remove_proc_entry(hinfo
->pde
->name
, hashlimit_procdir
);
295 htable_selective_cleanup(hinfo
, select_all
);
299 static struct ipt_hashlimit_htable
*htable_find_get(char *name
)
301 struct ipt_hashlimit_htable
*hinfo
;
302 struct hlist_node
*pos
;
304 LOCK_BH(&hashlimit_lock
);
305 hlist_for_each_entry(hinfo
, pos
, &hashlimit_htables
, node
) {
306 if (!strcmp(name
, hinfo
->pde
->name
)) {
307 atomic_inc(&hinfo
->use
);
308 UNLOCK_BH(&hashlimit_lock
);
312 UNLOCK_BH(&hashlimit_lock
);
317 static void htable_put(struct ipt_hashlimit_htable
*hinfo
)
319 if (atomic_dec_and_test(&hinfo
->use
)) {
320 LOCK_BH(&hashlimit_lock
);
321 hlist_del(&hinfo
->node
);
322 UNLOCK_BH(&hashlimit_lock
);
323 htable_destroy(hinfo
);
328 /* The algorithm used is the Simple Token Bucket Filter (TBF)
329 * see net/sched/sch_tbf.c in the linux source tree
332 /* Rusty: This is my (non-mathematically-inclined) understanding of
333 this algorithm. The `average rate' in jiffies becomes your initial
334 amount of credit `credit' and the most credit you can ever have
335 `credit_cap'. The `peak rate' becomes the cost of passing the
338 `prev' tracks the last packet hit: you gain one credit per jiffy.
339 If you get credit balance more than this, the extra credit is
340 discarded. Every time the match passes, you lose `cost' credits;
341 if you don't have that many, the test fails.
343 See Alexey's formal explanation in net/sched/sch_tbf.c.
345 To get the maximum range, we multiply by this factor (ie. you get N
346 credits per jiffy). We want to allow a rate as low as 1 per day
347 (slowest userspace tool allows), which means
348 CREDITS_PER_JIFFY*HZ*60*60*24 < 2^32 ie.
350 #define MAX_CPJ (0xFFFFFFFF / (HZ*60*60*24))
352 /* Repeated shift and or gives us all 1s, final shift and add 1 gives
353 * us the power of 2 below the theoretical max, so GCC simply does a
355 #define _POW2_BELOW2(x) ((x)|((x)>>1))
356 #define _POW2_BELOW4(x) (_POW2_BELOW2(x)|_POW2_BELOW2((x)>>2))
357 #define _POW2_BELOW8(x) (_POW2_BELOW4(x)|_POW2_BELOW4((x)>>4))
358 #define _POW2_BELOW16(x) (_POW2_BELOW8(x)|_POW2_BELOW8((x)>>8))
359 #define _POW2_BELOW32(x) (_POW2_BELOW16(x)|_POW2_BELOW16((x)>>16))
360 #define POW2_BELOW32(x) ((_POW2_BELOW32(x)>>1) + 1)
362 #define CREDITS_PER_JIFFY POW2_BELOW32(MAX_CPJ)
364 /* Precision saver. */
365 static inline u_int32_t
366 user2credits(u_int32_t user
)
368 /* If multiplying would overflow... */
369 if (user
> 0xFFFFFFFF / (HZ
*CREDITS_PER_JIFFY
))
371 return (user
/ IPT_HASHLIMIT_SCALE
) * HZ
* CREDITS_PER_JIFFY
;
373 return (user
* HZ
* CREDITS_PER_JIFFY
) / IPT_HASHLIMIT_SCALE
;
376 static inline void rateinfo_recalc(struct dsthash_ent
*dh
, unsigned long now
)
378 dh
->rateinfo
.credit
+= (now
- xchg(&dh
->rateinfo
.prev
, now
))
380 if (dh
->rateinfo
.credit
> dh
->rateinfo
.credit_cap
)
381 dh
->rateinfo
.credit
= dh
->rateinfo
.credit_cap
;
384 static inline int get_ports(const struct sk_buff
*skb
, int offset
,
390 sctp_sctphdr_t sctph
;
393 /* Must not be a fragment. */
397 /* Must be big enough to read ports (both UDP and TCP have
398 them at the start). */
399 ptr_u
= skb_header_pointer(skb
, skb
->nh
.iph
->ihl
*4, 8, &hdr_u
);
403 switch (skb
->nh
.iph
->protocol
) {
405 ports
[0] = ptr_u
->th
.source
;
406 ports
[1] = ptr_u
->th
.dest
;
409 ports
[0] = ptr_u
->uh
.source
;
410 ports
[1] = ptr_u
->uh
.dest
;
413 ports
[0] = ptr_u
->sctph
.source
;
414 ports
[1] = ptr_u
->sctph
.dest
;
417 /* all other protocols don't supprot per-port hash
419 ports
[0] = ports
[1] = 0;
428 hashlimit_match(const struct sk_buff
*skb
,
429 const struct net_device
*in
,
430 const struct net_device
*out
,
431 const void *matchinfo
,
435 struct ipt_hashlimit_info
*r
=
436 ((struct ipt_hashlimit_info
*)matchinfo
)->u
.master
;
437 struct ipt_hashlimit_htable
*hinfo
= r
->hinfo
;
438 unsigned long now
= jiffies
;
439 struct dsthash_ent
*dh
;
440 struct dsthash_dst dst
;
442 /* build 'dst' according to hinfo->cfg and current packet */
443 memset(&dst
, 0, sizeof(dst
));
444 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DIP
)
445 dst
.dst_ip
= skb
->nh
.iph
->daddr
;
446 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SIP
)
447 dst
.src_ip
= skb
->nh
.iph
->saddr
;
448 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
449 ||hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
) {
451 if (get_ports(skb
, offset
, ports
)) {
452 /* We've been asked to examine this packet, and we
453 can't. Hence, no choice but to drop. */
457 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_SPT
)
458 dst
.src_port
= ports
[0];
459 if (hinfo
->cfg
.mode
& IPT_HASHLIMIT_HASH_DPT
)
460 dst
.dst_port
= ports
[1];
463 spin_lock_bh(&hinfo
->lock
);
464 dh
= __dsthash_find(hinfo
, &dst
);
466 dh
= __dsthash_alloc_init(hinfo
, &dst
);
469 /* enomem... don't match == DROP */
471 printk(KERN_ERR
"%s: ENOMEM\n", __FUNCTION__
);
472 spin_unlock_bh(&hinfo
->lock
);
476 dh
->expires
= jiffies
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
478 dh
->rateinfo
.prev
= jiffies
;
479 dh
->rateinfo
.credit
= user2credits(hinfo
->cfg
.avg
*
481 dh
->rateinfo
.credit_cap
= user2credits(hinfo
->cfg
.avg
*
483 dh
->rateinfo
.cost
= user2credits(hinfo
->cfg
.avg
);
485 spin_unlock_bh(&hinfo
->lock
);
489 /* update expiration timeout */
490 dh
->expires
= now
+ msecs_to_jiffies(hinfo
->cfg
.expire
);
492 rateinfo_recalc(dh
, now
);
493 if (dh
->rateinfo
.credit
>= dh
->rateinfo
.cost
) {
494 /* We're underlimit. */
495 dh
->rateinfo
.credit
-= dh
->rateinfo
.cost
;
496 spin_unlock_bh(&hinfo
->lock
);
500 spin_unlock_bh(&hinfo
->lock
);
502 /* default case: we're overlimit, thus don't match */
507 hashlimit_checkentry(const char *tablename
,
508 const struct ipt_ip
*ip
,
510 unsigned int matchsize
,
511 unsigned int hook_mask
)
513 struct ipt_hashlimit_info
*r
= matchinfo
;
515 if (matchsize
!= IPT_ALIGN(sizeof(struct ipt_hashlimit_info
)))
518 /* Check for overflow. */
519 if (r
->cfg
.burst
== 0
520 || user2credits(r
->cfg
.avg
* r
->cfg
.burst
) <
521 user2credits(r
->cfg
.avg
)) {
522 printk(KERN_ERR
"ipt_hashlimit: Overflow, try lower: %u/%u\n",
523 r
->cfg
.avg
, r
->cfg
.burst
);
528 || r
->cfg
.mode
> (IPT_HASHLIMIT_HASH_DPT
529 |IPT_HASHLIMIT_HASH_DIP
530 |IPT_HASHLIMIT_HASH_SIP
531 |IPT_HASHLIMIT_HASH_SPT
))
534 if (!r
->cfg
.gc_interval
)
540 /* This is the best we've got: We cannot release and re-grab lock,
541 * since checkentry() is called before ip_tables.c grabs ipt_mutex.
542 * We also cannot grab the hashtable spinlock, since htable_create will
543 * call vmalloc, and that can sleep. And we cannot just re-search
544 * the list of htable's in htable_create(), since then we would
545 * create duplicate proc files. -HW */
547 r
->hinfo
= htable_find_get(r
->name
);
548 if (!r
->hinfo
&& (htable_create(r
) != 0)) {
554 /* Ugly hack: For SMP, we only want to use one set */
561 hashlimit_destroy(void *matchinfo
, unsigned int matchsize
)
563 struct ipt_hashlimit_info
*r
= (struct ipt_hashlimit_info
*) matchinfo
;
565 htable_put(r
->hinfo
);
568 static struct ipt_match ipt_hashlimit
= {
570 .match
= hashlimit_match
,
571 .checkentry
= hashlimit_checkentry
,
572 .destroy
= hashlimit_destroy
,
578 static void *dl_seq_start(struct seq_file
*s
, loff_t
*pos
)
580 struct proc_dir_entry
*pde
= s
->private;
581 struct ipt_hashlimit_htable
*htable
= pde
->data
;
582 unsigned int *bucket
;
584 spin_lock_bh(&htable
->lock
);
585 if (*pos
>= htable
->cfg
.size
)
588 bucket
= kmalloc(sizeof(unsigned int), GFP_ATOMIC
);
590 return ERR_PTR(-ENOMEM
);
596 static void *dl_seq_next(struct seq_file
*s
, void *v
, loff_t
*pos
)
598 struct proc_dir_entry
*pde
= s
->private;
599 struct ipt_hashlimit_htable
*htable
= pde
->data
;
600 unsigned int *bucket
= (unsigned int *)v
;
603 if (*pos
>= htable
->cfg
.size
) {
610 static void dl_seq_stop(struct seq_file
*s
, void *v
)
612 struct proc_dir_entry
*pde
= s
->private;
613 struct ipt_hashlimit_htable
*htable
= pde
->data
;
614 unsigned int *bucket
= (unsigned int *)v
;
618 spin_unlock_bh(&htable
->lock
);
621 static inline int dl_seq_real_show(struct dsthash_ent
*ent
, struct seq_file
*s
)
623 /* recalculate to show accurate numbers */
624 rateinfo_recalc(ent
, jiffies
);
626 return seq_printf(s
, "%ld %u.%u.%u.%u:%u->%u.%u.%u.%u:%u %u %u %u\n",
627 (long)(ent
->expires
- jiffies
)/HZ
,
628 NIPQUAD(ent
->dst
.src_ip
), ntohs(ent
->dst
.src_port
),
629 NIPQUAD(ent
->dst
.dst_ip
), ntohs(ent
->dst
.dst_port
),
630 ent
->rateinfo
.credit
, ent
->rateinfo
.credit_cap
,
634 static int dl_seq_show(struct seq_file
*s
, void *v
)
636 struct proc_dir_entry
*pde
= s
->private;
637 struct ipt_hashlimit_htable
*htable
= pde
->data
;
638 unsigned int *bucket
= (unsigned int *)v
;
639 struct dsthash_ent
*ent
;
640 struct hlist_node
*pos
;
642 if (!hlist_empty(&htable
->hash
[*bucket
]))
643 hlist_for_each_entry(ent
, pos
, &htable
->hash
[*bucket
], node
) {
644 if (dl_seq_real_show(ent
, s
)) {
645 /* buffer was filled and unable to print that tuple */
653 static struct seq_operations dl_seq_ops
= {
654 .start
= dl_seq_start
,
660 static int dl_proc_open(struct inode
*inode
, struct file
*file
)
662 int ret
= seq_open(file
, &dl_seq_ops
);
665 struct seq_file
*sf
= file
->private_data
;
666 sf
->private = PDE(inode
);
671 static struct file_operations dl_file_ops
= {
672 .owner
= THIS_MODULE
,
673 .open
= dl_proc_open
,
676 .release
= seq_release
679 static int init_or_fini(int fini
)
686 if (ipt_register_match(&ipt_hashlimit
)) {
688 goto cleanup_nothing
;
691 hashlimit_cachep
= kmem_cache_create("ipt_hashlimit",
692 sizeof(struct dsthash_ent
), 0,
694 if (!hashlimit_cachep
) {
695 printk(KERN_ERR
"Unable to create ipt_hashlimit slab cache\n");
697 goto cleanup_unreg_match
;
700 hashlimit_procdir
= proc_mkdir("ipt_hashlimit", proc_net
);
701 if (!hashlimit_procdir
) {
702 printk(KERN_ERR
"Unable to create proc dir entry\n");
704 goto cleanup_free_slab
;
710 remove_proc_entry("ipt_hashlimit", proc_net
);
712 kmem_cache_destroy(hashlimit_cachep
);
714 ipt_unregister_match(&ipt_hashlimit
);
720 static int __init
init(void)
722 return init_or_fini(0);
725 static void __exit
fini(void)