net/ipv4/netfilter/ip_set_iphash.c

   1 /* Copyright (C) 2003-2004 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
   2  *
   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.
   6  */
   7
   8 /* Kernel module implementing an ip hash set */
   9
  10 #include <linux/module.h>
  11 #include <linux/ip.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>
  21
  22 #include <net/ip.h>
  23
  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>
  27
  28 static inline __u32
  29 jhash_ip(const struct ip_set_iphash *map, uint16_t i, ip_set_ip_t ip)
  30 {
  31         return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
  32 }
  33
  34 static inline __u32
  35 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  36 {
  37         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
  38         __u32 id;
  39         u_int16_t i;
  40         ip_set_ip_t *elem;
  41
  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));
  45
  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)
  51                         return id;
  52                 /* No shortcut at testing - there can be deleted
  53                  * entries. */
  54         }
  55         return UINT_MAX;
  56 }
  57
  58 static inline int
  59 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  60 {
  61         return (hash_id(set, ip, hash_ip) != UINT_MAX);
  62 }
  63
  64 static int
  65 testip(struct ip_set *set, const void *data, size_t size,
  66        ip_set_ip_t *hash_ip)
  67 {
  68         struct ip_set_req_iphash *req =
  69             (struct ip_set_req_iphash *) data;
  70
  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),
  74                               size);
  75                 return -EINVAL;
  76         }
  77         return __testip(set, req->ip, hash_ip);
  78 }
  79
  80 static int
  81 testip_kernel(struct ip_set *set,
  82               const struct sk_buff *skb,
  83               ip_set_ip_t *hash_ip,
  84               const u_int32_t *flags,
  85               unsigned char index)
  86 {
  87         return __testip(set,
  88                         ntohl(flags[index] & IPSET_SRC
  89                                 ? skb->nh.iph->saddr
  90                                 : skb->nh.iph->daddr),
  91                         hash_ip);
  92 }
  93
  94 static inline int
  95 __addip(struct ip_set_iphash *map, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  96 {
  97         __u32 probe;
  98         u_int16_t i;
  99         ip_set_ip_t *elem;
 100
 101         *hash_ip = ip & map->netmask;
 102
 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)
 107                         return -EEXIST;
 108                 if (!*elem) {
 109                         *elem = *hash_ip;
 110                         return 0;
 111                 }
 112         }
 113         /* Trigger rehashing */
 114         return -EAGAIN;
 115 }
 116
 117 static int
 118 addip(struct ip_set *set, const void *data, size_t size,
 119         ip_set_ip_t *hash_ip)
 120 {
 121         struct ip_set_req_iphash *req =
 122             (struct ip_set_req_iphash *) data;
 123
 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),
 127                               size);
 128                 return -EINVAL;
 129         }
 130         return __addip((struct ip_set_iphash *) set->data, req->ip, hash_ip);
 131 }
 132
 133 static int
 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,
 138              unsigned char index)
 139 {
 140         return __addip((struct ip_set_iphash *) set->data,
 141                        ntohl(flags[index] & IPSET_SRC
 142                                 ? skb->nh.iph->saddr
 143                                 : skb->nh.iph->daddr),
 144                        hash_ip);
 145 }
 146
 147 static int retry(struct ip_set *set)
 148 {
 149         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 150         ip_set_ip_t hash_ip, *elem;
 151         void *members;
 152         u_int32_t i, hashsize = map->hashsize;
 153         int res;
 154         struct ip_set_iphash *tmp;
 155
 156         if (map->resize == 0)
 157                 return -ERANGE;
 158
 159     again:
 160         res = 0;
 161
 162         /* Calculate new hash size */
 163         hashsize += (hashsize * map->resize)/100;
 164         if (hashsize == map->hashsize)
 165                 hashsize++;
 166
 167         ip_set_printk("rehashing of set %s triggered: "
 168                       "hashsize grows from %u to %u",
 169                       set->name, map->hashsize, hashsize);
 170
 171         tmp = kmalloc(sizeof(struct ip_set_iphash)
 172                       + map->probes * sizeof(uint32_t), GFP_ATOMIC);
 173         if (!tmp) {
 174                 DP("out of memory for %d bytes",
 175                    sizeof(struct ip_set_iphash)
 176                    + map->probes * sizeof(uint32_t));
 177                 return -ENOMEM;
 178         }
 179         tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
 180         if (!tmp->members) {
 181                 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
 182                 kfree(tmp);
 183                 return -ENOMEM;
 184         }
 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));
 190
 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);
 195                 if (*elem)
 196                         res = __addip(tmp, *elem, &hash_ip);
 197         }
 198         if (res) {
 199                 /* Failure, try again */
 200                 write_unlock_bh(&set->lock);
 201                 harray_free(tmp->members);
 202                 kfree(tmp);
 203                 goto again;
 204         }
 205
 206         /* Success at resizing! */
 207         members = map->members;
 208
 209         map->hashsize = tmp->hashsize;
 210         map->members = tmp->members;
 211         write_unlock_bh(&set->lock);
 212
 213         harray_free(members);
 214         kfree(tmp);
 215
 216         return 0;
 217 }
 218
 219 static inline int
 220 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
 221 {
 222         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 223         ip_set_ip_t id = hash_id(set, ip, hash_ip);
 224         ip_set_ip_t *elem;
 225
 226         if (id == UINT_MAX)
 227                 return -EEXIST;
 228
 229         elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
 230         *elem = 0;
 231
 232         return 0;
 233 }
 234
 235 static int
 236 delip(struct ip_set *set, const void *data, size_t size,
 237         ip_set_ip_t *hash_ip)
 238 {
 239         struct ip_set_req_iphash *req =
 240             (struct ip_set_req_iphash *) data;
 241
 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),
 245                               size);
 246                 return -EINVAL;
 247         }
 248         return __delip(set, req->ip, hash_ip);
 249 }
 250
 251 static int
 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,
 256              unsigned char index)
 257 {
 258         return __delip(set,
 259                        ntohl(flags[index] & IPSET_SRC
 260                                 ? skb->nh.iph->saddr
 261                                 : skb->nh.iph->daddr),
 262                        hash_ip);
 263 }
 264
 265 static int create(struct ip_set *set, const void *data, size_t size)
 266 {
 267         struct ip_set_req_iphash_create *req =
 268             (struct ip_set_req_iphash_create *) data;
 269         struct ip_set_iphash *map;
 270         uint16_t i;
 271
 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),
 275                                size);
 276                 return -EINVAL;
 277         }
 278
 279         if (req->hashsize < 1) {
 280                 ip_set_printk("hashsize too small");
 281                 return -ENOEXEC;
 282         }
 283
 284         if (req->probes < 1) {
 285                 ip_set_printk("probes too small");
 286                 return -ENOEXEC;
 287         }
 288
 289         map = kmalloc(sizeof(struct ip_set_iphash)
 290                       + req->probes * sizeof(uint32_t), GFP_KERNEL);
 291         if (!map) {
 292                 DP("out of memory for %d bytes",
 293                    sizeof(struct ip_set_iphash)
 294                    + req->probes * sizeof(uint32_t));
 295                 return -ENOMEM;
 296         }
 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);
 304         if (!map->members) {
 305                 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
 306                 kfree(map);
 307                 return -ENOMEM;
 308         }
 309
 310         set->data = map;
 311         return 0;
 312 }
 313
 314 static void destroy(struct ip_set *set)
 315 {
 316         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 317
 318         harray_free(map->members);
 319         kfree(map);
 320
 321         set->data = NULL;
 322 }
 323
 324 static void flush(struct ip_set *set)
 325 {
 326         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 327         harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
 328 }
 329
 330 static void list_header(const struct ip_set *set, void *data)
 331 {
 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;
 335
 336         header->hashsize = map->hashsize;
 337         header->probes = map->probes;
 338         header->resize = map->resize;
 339         header->netmask = map->netmask;
 340 }
 341
 342 static int list_members_size(const struct ip_set *set)
 343 {
 344         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 345
 346         return (map->hashsize * sizeof(ip_set_ip_t));
 347 }
 348
 349 static void list_members(const struct ip_set *set, void *data)
 350 {
 351         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 352         ip_set_ip_t i, *elem;
 353
 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;
 357         }
 358 }
 359
 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,
 364         .create                 = &create,
 365         .destroy                = &destroy,
 366         .flush                  = &flush,
 367         .reqsize                = sizeof(struct ip_set_req_iphash),
 368         .addip                  = &addip,
 369         .addip_kernel           = &addip_kernel,
 370         .retry                  = &retry,
 371         .delip                  = &delip,
 372         .delip_kernel           = &delip_kernel,
 373         .testip                 = &testip,
 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,
 379         .me                     = THIS_MODULE,
 380 };
 381
 382 MODULE_LICENSE("GPL");
 383 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
 384 MODULE_DESCRIPTION("iphash type of IP sets");
 385
 386 static int __init init(void)
 387 {
 388         return ip_set_register_set_type(&ip_set_iphash);
 389 }
 390
 391 static void __exit fini(void)
 392 {
 393         /* FIXME: possible race with ip_set_create() */
 394         ip_set_unregister_set_type(&ip_set_iphash);
 395 }
 396
 397 module_init(init);
 398 module_exit(fini);