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>
29 jhash_ip(const struct ip_set_nethash *map, uint16_t i, ip_set_ip_t ip)
31 return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
35 hash_id_cidr(struct ip_set_nethash *map,
44 *hash_ip = pack(ip, cidr);
46 for (i = 0; i < map->probes; i++) {
47 id = jhash_ip(map, i, *hash_ip) % map->hashsize;
48 DP("hash key: %u", id);
49 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
50 if (*elem == *hash_ip)
57 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
59 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
63 for (i = 0; i < 30 && map->cidr[i]; i++) {
64 id = hash_id_cidr(map, ip, map->cidr[i], hash_ip);
72 __testip_cidr(struct ip_set *set, ip_set_ip_t ip, unsigned char cidr,
75 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
77 return (hash_id_cidr(map, ip, cidr, hash_ip) != UINT_MAX);
81 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
83 return (hash_id(set, ip, hash_ip) != UINT_MAX);
87 testip(struct ip_set *set, const void *data, size_t size,
90 struct ip_set_req_nethash *req =
91 (struct ip_set_req_nethash *) data;
93 if (size != sizeof(struct ip_set_req_nethash)) {
94 ip_set_printk("data length wrong (want %zu, have %zu)",
95 sizeof(struct ip_set_req_nethash),
99 return (req->cidr == 32 ? __testip(set, req->ip, hash_ip)
100 : __testip_cidr(set, req->ip, req->cidr, hash_ip));
104 testip_kernel(struct ip_set *set,
105 const struct sk_buff *skb,
106 ip_set_ip_t *hash_ip,
107 const u_int32_t *flags,
111 ntohl(flags[index] & IPSET_SRC
113 : skb->nh.iph->daddr),
118 __addip_base(struct ip_set_nethash *map, ip_set_ip_t ip)
124 for (i = 0; i < map->probes; i++) {
125 probe = jhash_ip(map, i, ip) % map->hashsize;
126 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
134 /* Trigger rehashing */
139 __addip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr,
140 ip_set_ip_t *hash_ip)
142 *hash_ip = pack(ip, cidr);
143 DP("%u.%u.%u.%u/%u, %u.%u.%u.%u", HIPQUAD(ip), cidr, HIPQUAD(*hash_ip));
145 return __addip_base(map, *hash_ip);
149 update_cidr_sizes(struct ip_set_nethash *map, unsigned char cidr)
154 for (i = 0; i < 30 && map->cidr[i]; i++) {
155 if (map->cidr[i] == cidr) {
157 } else if (map->cidr[i] < cidr) {
168 addip(struct ip_set *set, const void *data, size_t size,
169 ip_set_ip_t *hash_ip)
171 struct ip_set_req_nethash *req =
172 (struct ip_set_req_nethash *) data;
175 if (size != sizeof(struct ip_set_req_nethash)) {
176 ip_set_printk("data length wrong (want %zu, have %zu)",
177 sizeof(struct ip_set_req_nethash),
181 ret = __addip((struct ip_set_nethash *) set->data,
182 req->ip, req->cidr, hash_ip);
185 update_cidr_sizes((struct ip_set_nethash *) set->data,
192 addip_kernel(struct ip_set *set,
193 const struct sk_buff *skb,
194 ip_set_ip_t *hash_ip,
195 const u_int32_t *flags,
198 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
200 ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC
202 : skb->nh.iph->daddr);
205 ret = __addip(map, ip, map->cidr[0], hash_ip);
210 static int retry(struct ip_set *set)
212 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
215 u_int32_t i, hashsize = map->hashsize;
217 struct ip_set_nethash *tmp;
219 if (map->resize == 0)
225 /* Calculate new parameters */
226 hashsize += (hashsize * map->resize)/100;
227 if (hashsize == map->hashsize)
230 ip_set_printk("rehashing of set %s triggered: "
231 "hashsize grows from %u to %u",
232 set->name, map->hashsize, hashsize);
234 tmp = kmalloc(sizeof(struct ip_set_nethash)
235 + map->probes * sizeof(uint32_t), GFP_ATOMIC);
237 DP("out of memory for %d bytes",
238 sizeof(struct ip_set_nethash)
239 + map->probes * sizeof(uint32_t));
242 tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
244 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
248 tmp->hashsize = hashsize;
249 tmp->probes = map->probes;
250 tmp->resize = map->resize;
251 memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t));
252 memcpy(tmp->cidr, map->cidr, 30 * sizeof(unsigned char));
254 write_lock_bh(&set->lock);
255 map = (struct ip_set_nethash *) set->data; /* Play safe */
256 for (i = 0; i < map->hashsize && res == 0; i++) {
257 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
259 res = __addip_base(tmp, *elem);
262 /* Failure, try again */
263 write_unlock_bh(&set->lock);
264 harray_free(tmp->members);
269 /* Success at resizing! */
270 members = map->members;
272 map->hashsize = tmp->hashsize;
273 map->members = tmp->members;
274 write_unlock_bh(&set->lock);
276 harray_free(members);
283 __delip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr,
284 ip_set_ip_t *hash_ip)
286 ip_set_ip_t id = hash_id_cidr(map, ip, cidr, hash_ip);
292 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
298 delip(struct ip_set *set, const void *data, size_t size,
299 ip_set_ip_t *hash_ip)
301 struct ip_set_req_nethash *req =
302 (struct ip_set_req_nethash *) data;
304 if (size != sizeof(struct ip_set_req_nethash)) {
305 ip_set_printk("data length wrong (want %zu, have %zu)",
306 sizeof(struct ip_set_req_nethash),
310 /* TODO: no garbage collection in map->cidr */
311 return __delip((struct ip_set_nethash *) set->data,
312 req->ip, req->cidr, hash_ip);
316 delip_kernel(struct ip_set *set,
317 const struct sk_buff *skb,
318 ip_set_ip_t *hash_ip,
319 const u_int32_t *flags,
322 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
324 ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC
326 : skb->nh.iph->daddr);
329 ret = __delip(map, ip, map->cidr[0], hash_ip);
334 static int create(struct ip_set *set, const void *data, size_t size)
336 struct ip_set_req_nethash_create *req =
337 (struct ip_set_req_nethash_create *) data;
338 struct ip_set_nethash *map;
341 if (size != sizeof(struct ip_set_req_nethash_create)) {
342 ip_set_printk("data length wrong (want %zu, have %zu)",
343 sizeof(struct ip_set_req_nethash_create),
348 if (req->hashsize < 1) {
349 ip_set_printk("hashsize too small");
352 if (req->probes < 1) {
353 ip_set_printk("probes too small");
357 map = kmalloc(sizeof(struct ip_set_nethash)
358 + req->probes * sizeof(uint32_t), GFP_KERNEL);
360 DP("out of memory for %d bytes",
361 sizeof(struct ip_set_nethash)
362 + req->probes * sizeof(uint32_t));
365 for (i = 0; i < req->probes; i++)
366 get_random_bytes(((uint32_t *) map->initval)+i, 4);
367 map->hashsize = req->hashsize;
368 map->probes = req->probes;
369 map->resize = req->resize;
370 memset(map->cidr, 0, 30 * sizeof(unsigned char));
371 map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL);
373 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
382 static void destroy(struct ip_set *set)
384 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
386 harray_free(map->members);
392 static void flush(struct ip_set *set)
394 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
395 harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
396 memset(map->cidr, 0, 30 * sizeof(unsigned char));
399 static void list_header(const struct ip_set *set, void *data)
401 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
402 struct ip_set_req_nethash_create *header =
403 (struct ip_set_req_nethash_create *) data;
405 header->hashsize = map->hashsize;
406 header->probes = map->probes;
407 header->resize = map->resize;
410 static int list_members_size(const struct ip_set *set)
412 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
414 return (map->hashsize * sizeof(ip_set_ip_t));
417 static void list_members(const struct ip_set *set, void *data)
419 struct ip_set_nethash *map = (struct ip_set_nethash *) set->data;
420 ip_set_ip_t i, *elem;
422 for (i = 0; i < map->hashsize; i++) {
423 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
424 ((ip_set_ip_t *)data)[i] = *elem;
428 static struct ip_set_type ip_set_nethash = {
429 .typename = SETTYPE_NAME,
430 .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE,
431 .protocol_version = IP_SET_PROTOCOL_VERSION,
435 .reqsize = sizeof(struct ip_set_req_nethash),
437 .addip_kernel = &addip_kernel,
440 .delip_kernel = &delip_kernel,
442 .testip_kernel = &testip_kernel,
443 .header_size = sizeof(struct ip_set_req_nethash_create),
444 .list_header = &list_header,
445 .list_members_size = &list_members_size,
446 .list_members = &list_members,
450 MODULE_LICENSE("GPL");
451 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
452 MODULE_DESCRIPTION("nethash type of IP sets");
454 static int __init init(void)
456 return ip_set_register_set_type(&ip_set_nethash);
459 static void __exit fini(void)
461 /* FIXME: possible race with ip_set_create() */
462 ip_set_unregister_set_type(&ip_set_nethash);