1 /* Copyright (C) 2003-2004 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License version 2 as
5 * published by the Free Software Foundation.
8 /* Kernel module implementing an ip+port hash set */
10 #include <linux/module.h>
12 #include <linux/tcp.h>
13 #include <linux/udp.h>
14 #include <linux/skbuff.h>
15 #include <linux/netfilter_ipv4/ip_tables.h>
16 #include <linux/netfilter_ipv4/ip_set.h>
17 #include <linux/errno.h>
18 #include <asm/uaccess.h>
19 #include <asm/bitops.h>
20 #include <linux/spinlock.h>
21 #include <linux/vmalloc.h>
22 #include <linux/random.h>
26 #include <linux/netfilter_ipv4/ip_set_malloc.h>
27 #include <linux/netfilter_ipv4/ip_set_ipporthash.h>
28 #include <linux/netfilter_ipv4/ip_set_jhash.h>
30 static int limit = MAX_RANGE;
32 /* We must handle non-linear skbs */
33 static inline ip_set_ip_t
34 get_port(const struct sk_buff *skb, u_int32_t flags)
36 struct iphdr *iph = skb->nh.iph;
37 u_int16_t offset = ntohs(iph->frag_off) & IP_OFFSET;
39 switch (iph->protocol) {
43 /* See comments at tcp_match in ip_tables.c */
47 if (skb_copy_bits(skb, skb->nh.iph->ihl*4, &tcph, sizeof(tcph)) < 0)
48 /* No choice either */
51 return ntohs(flags & IPSET_SRC ?
52 tcph.source : tcph.dest);
60 if (skb_copy_bits(skb, skb->nh.iph->ihl*4, &udph, sizeof(udph)) < 0)
61 /* No choice either */
64 return ntohs(flags & IPSET_SRC ?
65 udph.source : udph.dest);
73 jhash_ip(const struct ip_set_ipporthash *map, uint16_t i, ip_set_ip_t ip)
75 return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
78 #define HASH_IP(map, ip, port) (port + ((ip - ((map)->first_ip)) << 16))
81 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t port,
84 struct ip_set_ipporthash *map =
85 (struct ip_set_ipporthash *) set->data;
90 *hash_ip = HASH_IP(map, ip, port);
91 DP("set: %s, ipport:%u.%u.%u.%u:%u, %u.%u.%u.%u",
92 set->name, HIPQUAD(ip), port, HIPQUAD(*hash_ip));
94 for (i = 0; i < map->probes; i++) {
95 id = jhash_ip(map, i, *hash_ip) % map->hashsize;
96 DP("hash key: %u", id);
97 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
98 if (*elem == *hash_ip)
100 /* No shortcut at testing - there can be deleted
107 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t port,
108 ip_set_ip_t *hash_ip)
110 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
112 if (ip < map->first_ip || ip > map->last_ip)
115 return (hash_id(set, ip, port, hash_ip) != UINT_MAX);
119 testip(struct ip_set *set, const void *data, size_t size,
120 ip_set_ip_t *hash_ip)
122 struct ip_set_req_ipporthash *req =
123 (struct ip_set_req_ipporthash *) data;
125 if (size != sizeof(struct ip_set_req_ipporthash)) {
126 ip_set_printk("data length wrong (want %zu, have %zu)",
127 sizeof(struct ip_set_req_ipporthash),
131 return __testip(set, req->ip, req->port, hash_ip);
135 testip_kernel(struct ip_set *set,
136 const struct sk_buff *skb,
137 ip_set_ip_t *hash_ip,
138 const u_int32_t *flags,
143 if (flags[index+1] == 0)
146 port = get_port(skb, flags[index+1]);
148 DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
149 flags[index] & IPSET_SRC ? "SRC" : "DST",
150 NIPQUAD(skb->nh.iph->saddr),
151 NIPQUAD(skb->nh.iph->daddr));
152 DP("flag %s port %u",
153 flags[index+1] & IPSET_SRC ? "SRC" : "DST",
155 if (port == INVALID_PORT)
159 ntohl(flags[index] & IPSET_SRC
161 : skb->nh.iph->daddr),
167 __add_haship(struct ip_set_ipporthash *map, ip_set_ip_t hash_ip)
173 for (i = 0; i < map->probes; i++) {
174 probe = jhash_ip(map, i, hash_ip) % map->hashsize;
175 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
176 if (*elem == hash_ip)
184 /* Trigger rehashing */
189 __addip(struct ip_set_ipporthash *map, ip_set_ip_t ip, ip_set_ip_t port,
190 ip_set_ip_t *hash_ip)
192 if (map->elements > limit)
194 if (ip < map->first_ip || ip > map->last_ip)
197 *hash_ip = HASH_IP(map, ip, port);
199 return __add_haship(map, *hash_ip);
203 addip(struct ip_set *set, const void *data, size_t size,
204 ip_set_ip_t *hash_ip)
206 struct ip_set_req_ipporthash *req =
207 (struct ip_set_req_ipporthash *) data;
209 if (size != sizeof(struct ip_set_req_ipporthash)) {
210 ip_set_printk("data length wrong (want %zu, have %zu)",
211 sizeof(struct ip_set_req_ipporthash),
215 return __addip((struct ip_set_ipporthash *) set->data,
216 req->ip, req->port, hash_ip);
220 addip_kernel(struct ip_set *set,
221 const struct sk_buff *skb,
222 ip_set_ip_t *hash_ip,
223 const u_int32_t *flags,
228 if (flags[index+1] == 0)
231 port = get_port(skb, flags[index+1]);
233 DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
234 flags[index] & IPSET_SRC ? "SRC" : "DST",
235 NIPQUAD(skb->nh.iph->saddr),
236 NIPQUAD(skb->nh.iph->daddr));
237 DP("flag %s port %u",
238 flags[index+1] & IPSET_SRC ? "SRC" : "DST",
240 if (port == INVALID_PORT)
243 return __addip((struct ip_set_ipporthash *) set->data,
244 ntohl(flags[index] & IPSET_SRC
246 : skb->nh.iph->daddr),
251 static int retry(struct ip_set *set)
253 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
256 u_int32_t i, hashsize = map->hashsize;
258 struct ip_set_ipporthash *tmp;
260 if (map->resize == 0)
266 /* Calculate new hash size */
267 hashsize += (hashsize * map->resize)/100;
268 if (hashsize == map->hashsize)
271 ip_set_printk("rehashing of set %s triggered: "
272 "hashsize grows from %u to %u",
273 set->name, map->hashsize, hashsize);
275 tmp = kmalloc(sizeof(struct ip_set_ipporthash)
276 + map->probes * sizeof(uint32_t), GFP_ATOMIC);
278 DP("out of memory for %d bytes",
279 sizeof(struct ip_set_ipporthash)
280 + map->probes * sizeof(uint32_t));
283 tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
285 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
289 tmp->hashsize = hashsize;
291 tmp->probes = map->probes;
292 tmp->resize = map->resize;
293 tmp->first_ip = map->first_ip;
294 tmp->last_ip = map->last_ip;
295 memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t));
297 write_lock_bh(&set->lock);
298 map = (struct ip_set_ipporthash *) set->data; /* Play safe */
299 for (i = 0; i < map->hashsize && res == 0; i++) {
300 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
302 res = __add_haship(tmp, *elem);
305 /* Failure, try again */
306 write_unlock_bh(&set->lock);
307 harray_free(tmp->members);
312 /* Success at resizing! */
313 members = map->members;
315 map->hashsize = tmp->hashsize;
316 map->members = tmp->members;
317 write_unlock_bh(&set->lock);
319 harray_free(members);
326 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t port,
327 ip_set_ip_t *hash_ip)
329 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
333 if (ip < map->first_ip || ip > map->last_ip)
336 id = hash_id(set, ip, port, hash_ip);
341 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
349 delip(struct ip_set *set, const void *data, size_t size,
350 ip_set_ip_t *hash_ip)
352 struct ip_set_req_ipporthash *req =
353 (struct ip_set_req_ipporthash *) data;
355 if (size != sizeof(struct ip_set_req_ipporthash)) {
356 ip_set_printk("data length wrong (want %zu, have %zu)",
357 sizeof(struct ip_set_req_ipporthash),
361 return __delip(set, req->ip, req->port, hash_ip);
365 delip_kernel(struct ip_set *set,
366 const struct sk_buff *skb,
367 ip_set_ip_t *hash_ip,
368 const u_int32_t *flags,
373 if (flags[index+1] == 0)
376 port = get_port(skb, flags[index+1]);
378 DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
379 flags[index] & IPSET_SRC ? "SRC" : "DST",
380 NIPQUAD(skb->nh.iph->saddr),
381 NIPQUAD(skb->nh.iph->daddr));
382 DP("flag %s port %u",
383 flags[index+1] & IPSET_SRC ? "SRC" : "DST",
385 if (port == INVALID_PORT)
389 ntohl(flags[index] & IPSET_SRC
391 : skb->nh.iph->daddr),
396 static int create(struct ip_set *set, const void *data, size_t size)
398 struct ip_set_req_ipporthash_create *req =
399 (struct ip_set_req_ipporthash_create *) data;
400 struct ip_set_ipporthash *map;
403 if (size != sizeof(struct ip_set_req_ipporthash_create)) {
404 ip_set_printk("data length wrong (want %zu, have %zu)",
405 sizeof(struct ip_set_req_ipporthash_create),
410 if (req->hashsize < 1) {
411 ip_set_printk("hashsize too small");
415 if (req->probes < 1) {
416 ip_set_printk("probes too small");
420 map = kmalloc(sizeof(struct ip_set_ipporthash)
421 + req->probes * sizeof(uint32_t), GFP_KERNEL);
423 DP("out of memory for %d bytes",
424 sizeof(struct ip_set_ipporthash)
425 + req->probes * sizeof(uint32_t));
428 for (i = 0; i < req->probes; i++)
429 get_random_bytes(((uint32_t *) map->initval)+i, 4);
431 map->hashsize = req->hashsize;
432 map->probes = req->probes;
433 map->resize = req->resize;
434 map->first_ip = req->from;
435 map->last_ip = req->to;
436 map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL);
438 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
447 static void destroy(struct ip_set *set)
449 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
451 harray_free(map->members);
457 static void flush(struct ip_set *set)
459 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
460 harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
464 static void list_header(const struct ip_set *set, void *data)
466 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
467 struct ip_set_req_ipporthash_create *header =
468 (struct ip_set_req_ipporthash_create *) data;
470 header->hashsize = map->hashsize;
471 header->probes = map->probes;
472 header->resize = map->resize;
473 header->from = map->first_ip;
474 header->to = map->last_ip;
477 static int list_members_size(const struct ip_set *set)
479 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
481 return (map->hashsize * sizeof(ip_set_ip_t));
484 static void list_members(const struct ip_set *set, void *data)
486 struct ip_set_ipporthash *map = (struct ip_set_ipporthash *) set->data;
487 ip_set_ip_t i, *elem;
489 for (i = 0; i < map->hashsize; i++) {
490 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
491 ((ip_set_ip_t *)data)[i] = *elem;
495 static struct ip_set_type ip_set_ipporthash = {
496 .typename = SETTYPE_NAME,
497 .features = IPSET_TYPE_IP | IPSET_TYPE_PORT | IPSET_DATA_DOUBLE,
498 .protocol_version = IP_SET_PROTOCOL_VERSION,
502 .reqsize = sizeof(struct ip_set_req_ipporthash),
504 .addip_kernel = &addip_kernel,
507 .delip_kernel = &delip_kernel,
509 .testip_kernel = &testip_kernel,
510 .header_size = sizeof(struct ip_set_req_ipporthash_create),
511 .list_header = &list_header,
512 .list_members_size = &list_members_size,
513 .list_members = &list_members,
517 MODULE_LICENSE("GPL");
518 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
519 MODULE_DESCRIPTION("ipporthash type of IP sets");
520 module_param(limit, int, 0600);
521 MODULE_PARM_DESC(limit, "maximal number of elements stored in the sets");
523 static int __init init(void)
525 return ip_set_register_set_type(&ip_set_ipporthash);
528 static void __exit fini(void)
530 /* FIXME: possible race with ip_set_create() */
531 ip_set_unregister_set_type(&ip_set_ipporthash);