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>
28 static int limit = MAX_RANGE;
31 jhash_ip(const struct ip_set_iphash *map, uint16_t i, ip_set_ip_t ip)
33 return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
37 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
39 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
44 *hash_ip = ip & map->netmask;
45 DP("set: %s, ip:%u.%u.%u.%u, %u.%u.%u.%u, %u.%u.%u.%u",
46 set->name, HIPQUAD(ip), HIPQUAD(*hash_ip), HIPQUAD(map->netmask));
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)
54 /* No shortcut at testing - there can be deleted
61 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
63 return (ip && hash_id(set, ip, hash_ip) != UINT_MAX);
67 testip(struct ip_set *set, const void *data, size_t size,
70 struct ip_set_req_iphash *req =
71 (struct ip_set_req_iphash *) data;
73 if (size != sizeof(struct ip_set_req_iphash)) {
74 ip_set_printk("data length wrong (want %zu, have %zu)",
75 sizeof(struct ip_set_req_iphash),
79 return __testip(set, req->ip, hash_ip);
83 testip_kernel(struct ip_set *set,
84 const struct sk_buff *skb,
86 const u_int32_t *flags,
90 ntohl(flags[index] & IPSET_SRC
92 : skb->nh.iph->daddr),
97 __addip(struct ip_set_iphash *map, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
103 if (!ip || map->elements > limit)
106 *hash_ip = ip & map->netmask;
108 for (i = 0; i < map->probes; i++) {
109 probe = jhash_ip(map, i, *hash_ip) % map->hashsize;
110 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
111 if (*elem == *hash_ip)
119 /* Trigger rehashing */
124 addip(struct ip_set *set, const void *data, size_t size,
125 ip_set_ip_t *hash_ip)
127 struct ip_set_req_iphash *req =
128 (struct ip_set_req_iphash *) data;
130 if (size != sizeof(struct ip_set_req_iphash)) {
131 ip_set_printk("data length wrong (want %zu, have %zu)",
132 sizeof(struct ip_set_req_iphash),
136 return __addip((struct ip_set_iphash *) set->data, req->ip, hash_ip);
140 addip_kernel(struct ip_set *set,
141 const struct sk_buff *skb,
142 ip_set_ip_t *hash_ip,
143 const u_int32_t *flags,
146 return __addip((struct ip_set_iphash *) set->data,
147 ntohl(flags[index] & IPSET_SRC
149 : skb->nh.iph->daddr),
153 static int retry(struct ip_set *set)
155 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
156 ip_set_ip_t hash_ip, *elem;
158 u_int32_t i, hashsize = map->hashsize;
160 struct ip_set_iphash *tmp;
162 if (map->resize == 0)
168 /* Calculate new hash size */
169 hashsize += (hashsize * map->resize)/100;
170 if (hashsize == map->hashsize)
173 ip_set_printk("rehashing of set %s triggered: "
174 "hashsize grows from %u to %u",
175 set->name, map->hashsize, hashsize);
177 tmp = kmalloc(sizeof(struct ip_set_iphash)
178 + map->probes * sizeof(uint32_t), GFP_ATOMIC);
180 DP("out of memory for %d bytes",
181 sizeof(struct ip_set_iphash)
182 + map->probes * sizeof(uint32_t));
185 tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
187 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
191 tmp->hashsize = hashsize;
193 tmp->probes = map->probes;
194 tmp->resize = map->resize;
195 tmp->netmask = map->netmask;
196 memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t));
198 write_lock_bh(&set->lock);
199 map = (struct ip_set_iphash *) set->data; /* Play safe */
200 for (i = 0; i < map->hashsize && res == 0; i++) {
201 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
203 res = __addip(tmp, *elem, &hash_ip);
206 /* Failure, try again */
207 write_unlock_bh(&set->lock);
208 harray_free(tmp->members);
213 /* Success at resizing! */
214 members = map->members;
216 map->hashsize = tmp->hashsize;
217 map->members = tmp->members;
218 write_unlock_bh(&set->lock);
220 harray_free(members);
227 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
229 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
230 ip_set_ip_t id, *elem;
235 id = hash_id(set, ip, hash_ip);
239 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
247 delip(struct ip_set *set, const void *data, size_t size,
248 ip_set_ip_t *hash_ip)
250 struct ip_set_req_iphash *req =
251 (struct ip_set_req_iphash *) data;
253 if (size != sizeof(struct ip_set_req_iphash)) {
254 ip_set_printk("data length wrong (want %zu, have %zu)",
255 sizeof(struct ip_set_req_iphash),
259 return __delip(set, req->ip, hash_ip);
263 delip_kernel(struct ip_set *set,
264 const struct sk_buff *skb,
265 ip_set_ip_t *hash_ip,
266 const u_int32_t *flags,
270 ntohl(flags[index] & IPSET_SRC
272 : skb->nh.iph->daddr),
276 static int create(struct ip_set *set, const void *data, size_t size)
278 struct ip_set_req_iphash_create *req =
279 (struct ip_set_req_iphash_create *) data;
280 struct ip_set_iphash *map;
283 if (size != sizeof(struct ip_set_req_iphash_create)) {
284 ip_set_printk("data length wrong (want %zu, have %zu)",
285 sizeof(struct ip_set_req_iphash_create),
290 if (req->hashsize < 1) {
291 ip_set_printk("hashsize too small");
295 if (req->probes < 1) {
296 ip_set_printk("probes too small");
300 map = kmalloc(sizeof(struct ip_set_iphash)
301 + req->probes * sizeof(uint32_t), GFP_KERNEL);
303 DP("out of memory for %d bytes",
304 sizeof(struct ip_set_iphash)
305 + req->probes * sizeof(uint32_t));
308 for (i = 0; i < req->probes; i++)
309 get_random_bytes(((uint32_t *) map->initval)+i, 4);
311 map->hashsize = req->hashsize;
312 map->probes = req->probes;
313 map->resize = req->resize;
314 map->netmask = req->netmask;
315 map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL);
317 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
326 static void destroy(struct ip_set *set)
328 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
330 harray_free(map->members);
336 static void flush(struct ip_set *set)
338 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
339 harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
343 static void list_header(const struct ip_set *set, void *data)
345 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
346 struct ip_set_req_iphash_create *header =
347 (struct ip_set_req_iphash_create *) data;
349 header->hashsize = map->hashsize;
350 header->probes = map->probes;
351 header->resize = map->resize;
352 header->netmask = map->netmask;
355 static int list_members_size(const struct ip_set *set)
357 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
359 return (map->hashsize * sizeof(ip_set_ip_t));
362 static void list_members(const struct ip_set *set, void *data)
364 struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
365 ip_set_ip_t i, *elem;
367 for (i = 0; i < map->hashsize; i++) {
368 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i);
369 ((ip_set_ip_t *)data)[i] = *elem;
373 static struct ip_set_type ip_set_iphash = {
374 .typename = SETTYPE_NAME,
375 .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE,
376 .protocol_version = IP_SET_PROTOCOL_VERSION,
380 .reqsize = sizeof(struct ip_set_req_iphash),
382 .addip_kernel = &addip_kernel,
385 .delip_kernel = &delip_kernel,
387 .testip_kernel = &testip_kernel,
388 .header_size = sizeof(struct ip_set_req_iphash_create),
389 .list_header = &list_header,
390 .list_members_size = &list_members_size,
391 .list_members = &list_members,
395 MODULE_LICENSE("GPL");
396 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
397 MODULE_DESCRIPTION("iphash type of IP sets");
398 module_param(limit, int, 0600);
399 MODULE_PARM_DESC(limit, "maximal number of elements stored in the sets");
401 static int __init init(void)
403 return ip_set_register_set_type(&ip_set_iphash);
406 static void __exit fini(void)
408 /* FIXME: possible race with ip_set_create() */
409 ip_set_unregister_set_type(&ip_set_iphash);