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 hash 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_iphash.h>
26 #include <linux/netfilter_ipv4/ip_set_jhash.h>
29 jhash_ip(const struct ip_set_iphash *map, uint16_t i, ip_set_ip_t ip)
31 return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
35 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
37 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
42 *hash_ip = ip & map->netmask;
43 DP("set: %s, ip:%u.%u.%u.%u, %u.%u.%u.%u, %u.%u.%u.%u",
44 set->name, HIPQUAD(ip), HIPQUAD(*hash_ip), HIPQUAD(map->netmask));
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)
52 /* No shortcut at testing - there can be deleted
59 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
61 return (hash_id(set, ip, hash_ip) != UINT_MAX);
65 testip(struct ip_set *set, const void *data, size_t size,
68 struct ip_set_req_iphash *req =
69 (struct ip_set_req_iphash *) data;
71 if (size != sizeof(struct ip_set_req_iphash)) {
72 ip_set_printk("data length wrong (want %zu, have %zu)",
73 sizeof(struct ip_set_req_iphash),
77 return __testip(set, req->ip, hash_ip);
81 testip_kernel(struct ip_set *set,
82 const struct sk_buff *skb,
84 const u_int32_t *flags,
88 ntohl(flags[index] & IPSET_SRC
90 : skb->nh.iph->daddr),
95 __addip(struct ip_set_iphash *map, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
101 *hash_ip = ip & map->netmask;
103 for (i = 0; i < map->probes; i++) {
104 probe = jhash_ip(map, i, *hash_ip) % map->hashsize;
105 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
106 if (*elem == *hash_ip)
113 /* Trigger rehashing */
118 addip(struct ip_set *set, const void *data, size_t size,
119 ip_set_ip_t *hash_ip)
121 struct ip_set_req_iphash *req =
122 (struct ip_set_req_iphash *) data;
124 if (size != sizeof(struct ip_set_req_iphash)) {
125 ip_set_printk("data length wrong (want %zu, have %zu)",
126 sizeof(struct ip_set_req_iphash),
130 return __addip((struct ip_set_iphash *) set->data, req->ip, hash_ip);
134 addip_kernel(struct ip_set *set,
135 const struct sk_buff *skb,
136 ip_set_ip_t *hash_ip,
137 const u_int32_t *flags,
140 return __addip((struct ip_set_iphash *) set->data,
141 ntohl(flags[index] & IPSET_SRC
143 : skb->nh.iph->daddr),
147 static int retry(struct ip_set *set)
149 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
150 ip_set_ip_t hash_ip, *elem;
152 u_int32_t i, hashsize = map->hashsize;
154 struct ip_set_iphash *tmp;
156 if (map->resize == 0)
162 /* Calculate new hash size */
163 hashsize += (hashsize * map->resize)/100;
164 if (hashsize == map->hashsize)
167 ip_set_printk("rehashing of set %s triggered: "
168 "hashsize grows from %u to %u",
169 set->name, map->hashsize, hashsize);
171 tmp = kmalloc(sizeof(struct ip_set_iphash)
172 + map->probes * sizeof(uint32_t), GFP_ATOMIC);
174 DP("out of memory for %d bytes",
175 sizeof(struct ip_set_iphash)
176 + map->probes * sizeof(uint32_t));
179 tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
181 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
185 tmp->hashsize = hashsize;
186 tmp->probes = map->probes;
187 tmp->resize = map->resize;
188 tmp->netmask = map->netmask;
189 memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t));
191 write_lock_bh(&set->lock);
192 map = (struct ip_set_iphash *) set->data; /* Play safe */
193 for (i = 0; i < map->hashsize && res == 0; i++) {
194 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
196 res = __addip(tmp, *elem, &hash_ip);
199 /* Failure, try again */
200 write_unlock_bh(&set->lock);
201 harray_free(tmp->members);
206 /* Success at resizing! */
207 members = map->members;
209 map->hashsize = tmp->hashsize;
210 map->members = tmp->members;
211 write_unlock_bh(&set->lock);
213 harray_free(members);
220 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
222 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
223 ip_set_ip_t id = hash_id(set, ip, hash_ip);
229 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
236 delip(struct ip_set *set, const void *data, size_t size,
237 ip_set_ip_t *hash_ip)
239 struct ip_set_req_iphash *req =
240 (struct ip_set_req_iphash *) data;
242 if (size != sizeof(struct ip_set_req_iphash)) {
243 ip_set_printk("data length wrong (want %zu, have %zu)",
244 sizeof(struct ip_set_req_iphash),
248 return __delip(set, req->ip, hash_ip);
252 delip_kernel(struct ip_set *set,
253 const struct sk_buff *skb,
254 ip_set_ip_t *hash_ip,
255 const u_int32_t *flags,
259 ntohl(flags[index] & IPSET_SRC
261 : skb->nh.iph->daddr),
265 static int create(struct ip_set *set, const void *data, size_t size)
267 struct ip_set_req_iphash_create *req =
268 (struct ip_set_req_iphash_create *) data;
269 struct ip_set_iphash *map;
272 if (size != sizeof(struct ip_set_req_iphash_create)) {
273 ip_set_printk("data length wrong (want %zu, have %zu)",
274 sizeof(struct ip_set_req_iphash_create),
279 if (req->hashsize < 1) {
280 ip_set_printk("hashsize too small");
284 if (req->probes < 1) {
285 ip_set_printk("probes too small");
289 map = kmalloc(sizeof(struct ip_set_iphash)
290 + req->probes * sizeof(uint32_t), GFP_KERNEL);
292 DP("out of memory for %d bytes",
293 sizeof(struct ip_set_iphash)
294 + req->probes * sizeof(uint32_t));
297 for (i = 0; i < req->probes; i++)
298 get_random_bytes(((uint32_t *) map->initval)+i, 4);
299 map->hashsize = req->hashsize;
300 map->probes = req->probes;
301 map->resize = req->resize;
302 map->netmask = req->netmask;
303 map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL);
305 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
314 static void destroy(struct ip_set *set)
316 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
318 harray_free(map->members);
324 static void flush(struct ip_set *set)
326 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
327 harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
330 static void list_header(const struct ip_set *set, void *data)
332 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
333 struct ip_set_req_iphash_create *header =
334 (struct ip_set_req_iphash_create *) data;
336 header->hashsize = map->hashsize;
337 header->probes = map->probes;
338 header->resize = map->resize;
339 header->netmask = map->netmask;
342 static int list_members_size(const struct ip_set *set)
344 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
346 return (map->hashsize * sizeof(ip_set_ip_t));
349 static void list_members(const struct ip_set *set, void *data)
351 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
352 ip_set_ip_t i, *elem;
354 for (i = 0; i < map->hashsize; i++) {
355 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
356 ((ip_set_ip_t *)data)[i] = *elem;
360 static struct ip_set_type ip_set_iphash = {
361 .typename = SETTYPE_NAME,
362 .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE,
363 .protocol_version = IP_SET_PROTOCOL_VERSION,
367 .reqsize = sizeof(struct ip_set_req_iphash),
369 .addip_kernel = &addip_kernel,
372 .delip_kernel = &delip_kernel,
374 .testip_kernel = &testip_kernel,
375 .header_size = sizeof(struct ip_set_req_iphash_create),
376 .list_header = &list_header,
377 .list_members_size = &list_members_size,
378 .list_members = &list_members,
382 MODULE_LICENSE("GPL");
383 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
384 MODULE_DESCRIPTION("iphash type of IP sets");
386 static int __init init(void)
388 return ip_set_register_set_type(&ip_set_iphash);
391 static void __exit fini(void)
393 /* FIXME: possible race with ip_set_create() */
394 ip_set_unregister_set_type(&ip_set_iphash);