diff options
Diffstat (limited to 'kernel/ip_set_nethash.c')
| -rw-r--r-- | kernel/ip_set_nethash.c | 490 |
1 files changed, 490 insertions, 0 deletions
diff --git a/kernel/ip_set_nethash.c b/kernel/ip_set_nethash.c new file mode 100644 index 0000000..bb866b5 --- /dev/null +++ b/kernel/ip_set_nethash.c @@ -0,0 +1,490 @@ +/* Copyright (C) 2003-2004 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License version 2 as + * published by the Free Software Foundation. + */ + +/* Kernel module implementing a cidr nethash set */ + +#include <linux/module.h> +#include <linux/ip.h> +#include <linux/skbuff.h> +#include <linux/version.h> +#include <linux/jhash.h> +#include <linux/netfilter_ipv4/ip_tables.h> +#include <linux/netfilter_ipv4/ip_set.h> +#include <linux/errno.h> +#include <asm/uaccess.h> +#include <asm/bitops.h> +#include <linux/spinlock.h> +#include <linux/vmalloc.h> +#include <linux/random.h> + +#include <net/ip.h> + +#include <linux/netfilter_ipv4/ip_set_malloc.h> +#include <linux/netfilter_ipv4/ip_set_nethash.h> + +static int limit = MAX_RANGE; + +static inline __u32 +jhash_ip(const struct ip_set_nethash *map, uint16_t i, ip_set_ip_t ip) +{ + return jhash_1word(ip, *(((uint32_t *) map->initval) + i)); +} + +static inline __u32 +hash_id_cidr(struct ip_set_nethash *map, + ip_set_ip_t ip, + unsigned char cidr, + ip_set_ip_t *hash_ip) +{ + __u32 id; + u_int16_t i; + ip_set_ip_t *elem; + + *hash_ip = pack(ip, cidr); + + for (i = 0; i < map->probes; i++) { + id = jhash_ip(map, i, *hash_ip) % map->hashsize; + DP("hash key: %u", id); + elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id); + if (*elem == *hash_ip) + return id; + } + return UINT_MAX; +} + +static inline __u32 +hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip) +{ + struct ip_set_nethash *map = set->data; + __u32 id = UINT_MAX; + int i; + + for (i = 0; i < 30 && map->cidr[i]; i++) { + id = hash_id_cidr(map, ip, map->cidr[i], hash_ip); + if (id != UINT_MAX) + break; + } + return id; +} + +static inline int +__testip_cidr(struct ip_set *set, ip_set_ip_t ip, unsigned char cidr, + ip_set_ip_t *hash_ip) +{ + struct ip_set_nethash *map = set->data; + + return (ip && hash_id_cidr(map, ip, cidr, hash_ip) != UINT_MAX); +} + +static inline int +__testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip) +{ + return (ip && hash_id(set, ip, hash_ip) != UINT_MAX); +} + +static int +testip(struct ip_set *set, const void *data, size_t size, + ip_set_ip_t *hash_ip) +{ + const struct ip_set_req_nethash *req = data; + + if (size != sizeof(struct ip_set_req_nethash)) { + ip_set_printk("data length wrong (want %zu, have %zu)", + sizeof(struct ip_set_req_nethash), + size); + return -EINVAL; + } + return (req->cidr == 32 ? __testip(set, req->ip, hash_ip) + : __testip_cidr(set, req->ip, req->cidr, hash_ip)); +} + +static int +testip_kernel(struct ip_set *set, + const struct sk_buff *skb, + ip_set_ip_t *hash_ip, + const u_int32_t *flags, + unsigned char index) +{ + return __testip(set, + ntohl(flags[index] & IPSET_SRC +#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,22) + ? ip_hdr(skb)->saddr + : ip_hdr(skb)->daddr), +#else + ? skb->nh.iph->saddr + : skb->nh.iph->daddr), +#endif + hash_ip); +} + +static inline int +__addip_base(struct ip_set_nethash *map, ip_set_ip_t ip) +{ + __u32 probe; + u_int16_t i; + ip_set_ip_t *elem; + + for (i = 0; i < map->probes; i++) { + probe = jhash_ip(map, i, ip) % map->hashsize; + elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe); + if (*elem == ip) + return -EEXIST; + if (!*elem) { + *elem = ip; + map->elements++; + return 0; + } + } + /* Trigger rehashing */ + return -EAGAIN; +} + +static inline int +__addip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr, + ip_set_ip_t *hash_ip) +{ + if (!ip || map->elements >= limit) + return -ERANGE; + + *hash_ip = pack(ip, cidr); + DP("%u.%u.%u.%u/%u, %u.%u.%u.%u", HIPQUAD(ip), cidr, HIPQUAD(*hash_ip)); + + return __addip_base(map, *hash_ip); +} + +static void +update_cidr_sizes(struct ip_set_nethash *map, unsigned char cidr) +{ + unsigned char next; + int i; + + for (i = 0; i < 30 && map->cidr[i]; i++) { + if (map->cidr[i] == cidr) { + return; + } else if (map->cidr[i] < cidr) { + next = map->cidr[i]; + map->cidr[i] = cidr; + cidr = next; + } + } + if (i < 30) + map->cidr[i] = cidr; +} + +static int +addip(struct ip_set *set, const void *data, size_t size, + ip_set_ip_t *hash_ip) +{ + const struct ip_set_req_nethash *req = data; + int ret; + + if (size != sizeof(struct ip_set_req_nethash)) { + ip_set_printk("data length wrong (want %zu, have %zu)", + sizeof(struct ip_set_req_nethash), + size); + return -EINVAL; + } + ret = __addip(set->data, req->ip, req->cidr, hash_ip); + + if (ret == 0) + update_cidr_sizes(set->data, req->cidr); + + return ret; +} + +static int +addip_kernel(struct ip_set *set, + const struct sk_buff *skb, + ip_set_ip_t *hash_ip, + const u_int32_t *flags, + unsigned char index) +{ + struct ip_set_nethash *map = set->data; + int ret = -ERANGE; + ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC +#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,22) + ? ip_hdr(skb)->saddr + : ip_hdr(skb)->daddr); +#else + ? skb->nh.iph->saddr + : skb->nh.iph->daddr); +#endif + + if (map->cidr[0]) + ret = __addip(map, ip, map->cidr[0], hash_ip); + + return ret; +} + +static int retry(struct ip_set *set) +{ + struct ip_set_nethash *map = set->data; + ip_set_ip_t *elem; + void *members; + u_int32_t i, hashsize = map->hashsize; + int res; + struct ip_set_nethash *tmp; + + if (map->resize == 0) + return -ERANGE; + + again: + res = 0; + + /* Calculate new parameters */ + hashsize += (hashsize * map->resize)/100; + if (hashsize == map->hashsize) + hashsize++; + + ip_set_printk("rehashing of set %s triggered: " + "hashsize grows from %u to %u", + set->name, map->hashsize, hashsize); + + tmp = kmalloc(sizeof(struct ip_set_nethash) + + map->probes * sizeof(uint32_t), GFP_ATOMIC); + if (!tmp) { + DP("out of memory for %d bytes", + sizeof(struct ip_set_nethash) + + map->probes * sizeof(uint32_t)); + return -ENOMEM; + } + tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC); + if (!tmp->members) { + DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t)); + kfree(tmp); + return -ENOMEM; + } + tmp->hashsize = hashsize; + tmp->elements = 0; + tmp->probes = map->probes; + tmp->resize = map->resize; + memcpy(tmp->initval, map->initval, map->probes * sizeof(uint32_t)); + memcpy(tmp->cidr, map->cidr, 30 * sizeof(unsigned char)); + + write_lock_bh(&set->lock); + map = set->data; /* Play safe */ + for (i = 0; i < map->hashsize && res == 0; i++) { + elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i); + if (*elem) + res = __addip_base(tmp, *elem); + } + if (res) { + /* Failure, try again */ + write_unlock_bh(&set->lock); + harray_free(tmp->members); + kfree(tmp); + goto again; + } + + /* Success at resizing! */ + members = map->members; + + map->hashsize = tmp->hashsize; + map->members = tmp->members; + write_unlock_bh(&set->lock); + + harray_free(members); + kfree(tmp); + + return 0; +} + +static inline int +__delip(struct ip_set_nethash *map, ip_set_ip_t ip, unsigned char cidr, + ip_set_ip_t *hash_ip) +{ + ip_set_ip_t id, *elem; + + if (!ip) + return -ERANGE; + + id = hash_id_cidr(map, ip, cidr, hash_ip); + if (id == UINT_MAX) + return -EEXIST; + + elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id); + *elem = 0; + map->elements--; + return 0; +} + +static int +delip(struct ip_set *set, const void *data, size_t size, + ip_set_ip_t *hash_ip) +{ + const struct ip_set_req_nethash *req = data; + + if (size != sizeof(struct ip_set_req_nethash)) { + ip_set_printk("data length wrong (want %zu, have %zu)", + sizeof(struct ip_set_req_nethash), + size); + return -EINVAL; + } + /* TODO: no garbage collection in map->cidr */ + return __delip(set->data, req->ip, req->cidr, hash_ip); +} + +static int +delip_kernel(struct ip_set *set, + const struct sk_buff *skb, + ip_set_ip_t *hash_ip, + const u_int32_t *flags, + unsigned char index) +{ + struct ip_set_nethash *map = set->data; + int ret = -ERANGE; + ip_set_ip_t ip = ntohl(flags[index] & IPSET_SRC +#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,6,22) + ? ip_hdr(skb)->saddr + : ip_hdr(skb)->daddr); +#else + ? skb->nh.iph->saddr + : skb->nh.iph->daddr); +#endif + + if (map->cidr[0]) + ret = __delip(map, ip, map->cidr[0], hash_ip); + + return ret; +} + +static int create(struct ip_set *set, const void *data, size_t size) +{ + const struct ip_set_req_nethash_create *req = data; + struct ip_set_nethash *map; + uint16_t i; + + if (size != sizeof(struct ip_set_req_nethash_create)) { + ip_set_printk("data length wrong (want %zu, have %zu)", + sizeof(struct ip_set_req_nethash_create), + size); + return -EINVAL; + } + + if (req->hashsize < 1) { + ip_set_printk("hashsize too small"); + return -ENOEXEC; + } + if (req->probes < 1) { + ip_set_printk("probes too small"); + return -ENOEXEC; + } + + map = kmalloc(sizeof(struct ip_set_nethash) + + req->probes * sizeof(uint32_t), GFP_KERNEL); + if (!map) { + DP("out of memory for %d bytes", + sizeof(struct ip_set_nethash) + + req->probes * sizeof(uint32_t)); + return -ENOMEM; + } + for (i = 0; i < req->probes; i++) + get_random_bytes(((uint32_t *) map->initval)+i, 4); + map->elements = 0; + map->hashsize = req->hashsize; + map->probes = req->probes; + map->resize = req->resize; + memset(map->cidr, 0, 30 * sizeof(unsigned char)); + map->members = harray_malloc(map->hashsize, sizeof(ip_set_ip_t), GFP_KERNEL); + if (!map->members) { + DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t)); + kfree(map); + return -ENOMEM; + } + + set->data = map; + return 0; +} + +static void destroy(struct ip_set *set) +{ + struct ip_set_nethash *map = set->data; + + harray_free(map->members); + kfree(map); + + set->data = NULL; +} + +static void flush(struct ip_set *set) +{ + struct ip_set_nethash *map = set->data; + harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t)); + memset(map->cidr, 0, 30 * sizeof(unsigned char)); + map->elements = 0; +} + +static void list_header(const struct ip_set *set, void *data) +{ + const struct ip_set_nethash *map = set->data; + struct ip_set_req_nethash_create *header = data; + + header->hashsize = map->hashsize; + header->probes = map->probes; + header->resize = map->resize; +} + +static int list_members_size(const struct ip_set *set) +{ + struct ip_set_nethash *map = set->data; + + return (map->hashsize * sizeof(ip_set_ip_t)); +} + +static void list_members(const struct ip_set *set, void *data) +{ + const struct ip_set_nethash *map = set->data; + ip_set_ip_t i, *elem; + + for (i = 0; i < map->hashsize; i++) { + elem = HARRAY_ELEM(map->members, ip_set_ip_t *, i); + ((ip_set_ip_t *)data)[i] = *elem; + } +} + +static struct ip_set_type ip_set_nethash = { + .typename = SETTYPE_NAME, + .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE, + .protocol_version = IP_SET_PROTOCOL_VERSION, + .create = &create, + .destroy = &destroy, + .flush = &flush, + .reqsize = sizeof(struct ip_set_req_nethash), + .addip = &addip, + .addip_kernel = &addip_kernel, + .retry = &retry, + .delip = &delip, + .delip_kernel = &delip_kernel, + .testip = &testip, + .testip_kernel = &testip_kernel, + .header_size = sizeof(struct ip_set_req_nethash_create), + .list_header = &list_header, + .list_members_size = &list_members_size, + .list_members = &list_members, + .me = THIS_MODULE, +}; + +MODULE_LICENSE("GPL"); +MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>"); +MODULE_DESCRIPTION("nethash type of IP sets"); +module_param(limit, int, 0600); +MODULE_PARM_DESC(limit, "maximal number of elements stored in the sets"); + +static int __init ip_set_nethash_init(void) +{ + init_max_page_size(); + return ip_set_register_set_type(&ip_set_nethash); +} + +static void __exit ip_set_nethash_fini(void) +{ + /* FIXME: possible race with ip_set_create() */ + ip_set_unregister_set_type(&ip_set_nethash); +} + +module_init(ip_set_nethash_init); +module_exit(ip_set_nethash_fini); |