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 a cidr nethash set */
10 #include <linux/module.h>
12 #include <linux/skbuff.h>
13 #include <linux/netfilter_ipv4/ip_tables.h>
14 #include <linux/netfilter_ipv4/ip_set.h>
15 #include <linux/errno.h>
16 #include <asm/uaccess.h>
17 #include <asm/bitops.h>
18 #include <linux/spinlock.h>
19 #include <linux/vmalloc.h>
20 #include <linux/random.h>
24 #include <linux/netfilter_ipv4/ip_set_malloc.h>
25 #include <linux/netfilter_ipv4/ip_set_nethash.h>
26 #include <linux/netfilter_ipv4/ip_set_jhash.h>
28 static int limit = MAX_RANGE;
31 jhash_ip(const struct ip_set_nethash *map, uint16_t i, ip_set_ip_t ip)
33 return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
37 hash_id_cidr(struct ip_set_nethash *map,
46 *hash_ip = pack(ip, cidr);
48 for (i = 0; i < map->probes; i++) {
49 id = jhash_ip(map, i, *hash_ip) % map->hashsize;
50 DP("hash key: %u", id);
51 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
52 if (*elem == *hash_ip)
59 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
61 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
65 for (i = 0; i < 30 && map->cidr[i]; i++) {
66 id = hash_id_cidr(map, ip, map->cidr[i], hash_ip);
74 __testip_cidr(struct ip_set *set, ip_set_ip_t ip, unsigned char cidr,
77 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
79 return (ip && hash_id_cidr(map, ip, cidr, hash_ip) != UINT_MAX);
83 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
85 return (ip && hash_id(set, ip, hash_ip) != UINT_MAX);
89 testip(struct ip_set *set, const void *data, size_t size,
92 struct ip_set_req_nethash *req =
93 (struct ip_set_req_nethash *) data;
95 if (size != sizeof(struct ip_set_req_nethash)) {
96 ip_set_printk("data length wrong (want %zu, have %zu)",
97 sizeof(struct ip_set_req_nethash),
101 return (req->cidr == 32 ? __testip(set, req->ip, hash_ip)
102 : __testip_cidr(set, req->ip, req->cidr, hash_ip));
106 testip_kernel(struct ip_set *set,
107 const struct sk_buff *skb,
108 ip_set_ip_t *hash_ip,
109 const u_int32_t *flags,
113 ntohl(flags[index] & IPSET_SRC
115 : skb->nh.iph->daddr),
120 __addip_base(struct ip_set_nethash *map, ip_set_ip_t ip)
126 for (i = 0; i < map->probes; i++) {
127 probe = jhash_ip(map, i, ip) % map->hashsize;
128 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
137 /* Trigger rehashing */
142 __addip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr,
143 ip_set_ip_t *hash_ip)
145 if (!ip || map->elements > limit)
148 *hash_ip = pack(ip, cidr);
149 DP("%u.%u.%u.%u/%u, %u.%u.%u.%u", HIPQUAD(ip), cidr, HIPQUAD(*hash_ip));
151 return __addip_base(map, *hash_ip);
155 update_cidr_sizes(struct ip_set_nethash *map, unsigned char cidr)
160 for (i = 0; i < 30 && map->cidr[i]; i++) {
161 if (map->cidr[i] == cidr) {
163 } else if (map->cidr[i] < cidr) {
174 addip(struct ip_set *set, const void *data, size_t size,
175 ip_set_ip_t *hash_ip)
177 struct ip_set_req_nethash *req =
178 (struct ip_set_req_nethash *) data;
181 if (size != sizeof(struct ip_set_req_nethash)) {
182 ip_set_printk("data length wrong (want %zu, have %zu)",
183 sizeof(struct ip_set_req_nethash),
187 ret = __addip((struct ip_set_nethash *) set->data,
188 req->ip, req->cidr, hash_ip);
191 update_cidr_sizes((struct ip_set_nethash *) set->data,
198 addip_kernel(struct ip_set *set,
199 const struct sk_buff *skb,
200 ip_set_ip_t *hash_ip,
201 const u_int32_t *flags,
204 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
206 ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC
208 : skb->nh.iph->daddr);
211 ret = __addip(map, ip, map->cidr[0], hash_ip);
216 static int retry(struct ip_set *set)
218 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
221 u_int32_t i, hashsize = map->hashsize;
223 struct ip_set_nethash *tmp;
225 if (map->resize == 0)
231 /* Calculate new parameters */
232 hashsize += (hashsize * map->resize)/100;
233 if (hashsize == map->hashsize)
236 ip_set_printk("rehashing of set %s triggered: "
237 "hashsize grows from %u to %u",
238 set->name, map->hashsize, hashsize);
240 tmp = kmalloc(sizeof(struct ip_set_nethash)
241 + map->probes * sizeof(uint32_t), GFP_ATOMIC);
243 DP("out of memory for %d bytes",
244 sizeof(struct ip_set_nethash)
245 + map->probes * sizeof(uint32_t));
248 tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
250 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
254 tmp->hashsize = hashsize;
256 tmp->probes = map->probes;
257 tmp->resize = map->resize;
258 memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t));
259 memcpy(tmp->cidr, map->cidr, 30 * sizeof(unsigned char));
261 write_lock_bh(&set->lock);
262 map = (struct ip_set_nethash *) set->data; /* Play safe */
263 for (i = 0; i < map->hashsize && res == 0; i++) {
264 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
266 res = __addip_base(tmp, *elem);
269 /* Failure, try again */
270 write_unlock_bh(&set->lock);
271 harray_free(tmp->members);
276 /* Success at resizing! */
277 members = map->members;
279 map->hashsize = tmp->hashsize;
280 map->members = tmp->members;
281 write_unlock_bh(&set->lock);
283 harray_free(members);
290 __delip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr,
291 ip_set_ip_t *hash_ip)
293 ip_set_ip_t id, *elem;
298 id = hash_id_cidr(map, ip, cidr, hash_ip);
302 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
309 delip(struct ip_set *set, const void *data, size_t size,
310 ip_set_ip_t *hash_ip)
312 struct ip_set_req_nethash *req =
313 (struct ip_set_req_nethash *) data;
315 if (size != sizeof(struct ip_set_req_nethash)) {
316 ip_set_printk("data length wrong (want %zu, have %zu)",
317 sizeof(struct ip_set_req_nethash),
321 /* TODO: no garbage collection in map->cidr */
322 return __delip((struct ip_set_nethash *) set->data,
323 req->ip, req->cidr, hash_ip);
327 delip_kernel(struct ip_set *set,
328 const struct sk_buff *skb,
329 ip_set_ip_t *hash_ip,
330 const u_int32_t *flags,
333 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
335 ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC
337 : skb->nh.iph->daddr);
340 ret = __delip(map, ip, map->cidr[0], hash_ip);
345 static int create(struct ip_set *set, const void *data, size_t size)
347 struct ip_set_req_nethash_create *req =
348 (struct ip_set_req_nethash_create *) data;
349 struct ip_set_nethash *map;
352 if (size != sizeof(struct ip_set_req_nethash_create)) {
353 ip_set_printk("data length wrong (want %zu, have %zu)",
354 sizeof(struct ip_set_req_nethash_create),
359 if (req->hashsize < 1) {
360 ip_set_printk("hashsize too small");
363 if (req->probes < 1) {
364 ip_set_printk("probes too small");
368 map = kmalloc(sizeof(struct ip_set_nethash)
369 + req->probes * sizeof(uint32_t), GFP_KERNEL);
371 DP("out of memory for %d bytes",
372 sizeof(struct ip_set_nethash)
373 + req->probes * sizeof(uint32_t));
376 for (i = 0; i < req->probes; i++)
377 get_random_bytes(((uint32_t *) map->initval)+i, 4);
379 map->hashsize = req->hashsize;
380 map->probes = req->probes;
381 map->resize = req->resize;
382 memset(map->cidr, 0, 30 * sizeof(unsigned char));
383 map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL);
385 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
394 static void destroy(struct ip_set *set)
396 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
398 harray_free(map->members);
404 static void flush(struct ip_set *set)
406 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
407 harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
408 memset(map->cidr, 0, 30 * sizeof(unsigned char));
412 static void list_header(const struct ip_set *set, void *data)
414 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
415 struct ip_set_req_nethash_create *header =
416 (struct ip_set_req_nethash_create *) data;
418 header->hashsize = map->hashsize;
419 header->probes = map->probes;
420 header->resize = map->resize;
423 static int list_members_size(const struct ip_set *set)
425 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
427 return (map->hashsize * sizeof(ip_set_ip_t));
430 static void list_members(const struct ip_set *set, void *data)
432 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
433 ip_set_ip_t i, *elem;
435 for (i = 0; i < map->hashsize; i++) {
436 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
437 ((ip_set_ip_t *)data)[i] = *elem;
441 static struct ip_set_type ip_set_nethash = {
442 .typename = SETTYPE_NAME,
443 .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE,
444 .protocol_version = IP_SET_PROTOCOL_VERSION,
448 .reqsize = sizeof(struct ip_set_req_nethash),
450 .addip_kernel = &addip_kernel,
453 .delip_kernel = &delip_kernel,
455 .testip_kernel = &testip_kernel,
456 .header_size = sizeof(struct ip_set_req_nethash_create),
457 .list_header = &list_header,
458 .list_members_size = &list_members_size,
459 .list_members = &list_members,
463 MODULE_LICENSE("GPL");
464 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
465 MODULE_DESCRIPTION("nethash type of IP sets");
466 module_param(limit, int, 0600);
467 MODULE_PARM_DESC(limit, "maximal number of elements stored in the sets");
469 static int __init init(void)
471 return ip_set_register_set_type(&ip_set_nethash);
474 static void __exit fini(void)
476 /* FIXME: possible race with ip_set_create() */
477 ip_set_unregister_set_type(&ip_set_nethash);