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 int limit = MAX_RANGE;
  29
  30 static inline __u32
  31 jhash_ip(const struct ip_set_iphash *map, uint16_t i, ip_set_ip_t ip)
  32 {
  33         return jhash_1word(ip, *(((uint32_t *) map->initval) + i));
  34 }
  35
  36 static inline __u32
  37 hash_id(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  38 {
  39         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
  40         __u32 id;
  41         u_int16_t i;
  42         ip_set_ip_t *elem;
  43
  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));
  47
  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)
  53                         return id;
  54                 /* No shortcut at testing - there can be deleted
  55                  * entries. */
  56         }
  57         return UINT_MAX;
  58 }
  59
  60 static inline int
  61 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  62 {
  63         return (ip && hash_id(set, ip, hash_ip) != UINT_MAX);
  64 }
  65
  66 static int
  67 testip(struct ip_set *set, const void *data, size_t size,
  68        ip_set_ip_t *hash_ip)
  69 {
  70         struct ip_set_req_iphash *req =
  71             (struct ip_set_req_iphash *) data;
  72
  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),
  76                               size);
  77                 return -EINVAL;
  78         }
  79         return __testip(set, req->ip, hash_ip);
  80 }
  81
  82 static int
  83 testip_kernel(struct ip_set *set,
  84               const struct sk_buff *skb,
  85               ip_set_ip_t *hash_ip,
  86               const u_int32_t *flags,
  87               unsigned char index)
  88 {
  89         return __testip(set,
  90                         ntohl(flags[index] & IPSET_SRC
  91                                 ? skb->nh.iph->saddr
  92                                 : skb->nh.iph->daddr),
  93                         hash_ip);
  94 }
  95
  96 static inline int
  97 __addip(struct ip_set_iphash *map, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
  98 {
  99         __u32 probe;
 100         u_int16_t i;
 101         ip_set_ip_t *elem;
 102
 103         if (!ip || map->elements > limit)
 104                 return -ERANGE;
 105
 106         *hash_ip = ip & map->netmask;
 107
 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)
 112                         return -EEXIST;
 113                 if (!*elem) {
 114                         *elem = *hash_ip;
 115                         map->elements++;
 116                         return 0;
 117                 }
 118         }
 119         /* Trigger rehashing */
 120         return -EAGAIN;
 121 }
 122
 123 static int
 124 addip(struct ip_set *set, const void *data, size_t size,
 125         ip_set_ip_t *hash_ip)
 126 {
 127         struct ip_set_req_iphash *req =
 128             (struct ip_set_req_iphash *) data;
 129
 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),
 133                               size);
 134                 return -EINVAL;
 135         }
 136         return __addip((struct ip_set_iphash *) set->data, req->ip, hash_ip);
 137 }
 138
 139 static int
 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,
 144              unsigned char index)
 145 {
 146         return __addip((struct ip_set_iphash *) set->data,
 147                        ntohl(flags[index] & IPSET_SRC
 148                                 ? skb->nh.iph->saddr
 149                                 : skb->nh.iph->daddr),
 150                        hash_ip);
 151 }
 152
 153 static int retry(struct ip_set *set)
 154 {
 155         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 156         ip_set_ip_t hash_ip, *elem;
 157         void *members;
 158         u_int32_t i, hashsize = map->hashsize;
 159         int res;
 160         struct ip_set_iphash *tmp;
 161
 162         if (map->resize == 0)
 163                 return -ERANGE;
 164
 165     again:
 166         res = 0;
 167
 168         /* Calculate new hash size */
 169         hashsize += (hashsize * map->resize)/100;
 170         if (hashsize == map->hashsize)
 171                 hashsize++;
 172
 173         ip_set_printk("rehashing of set %s triggered: "
 174                       "hashsize grows from %u to %u",
 175                       set->name, map->hashsize, hashsize);
 176
 177         tmp = kmalloc(sizeof(struct ip_set_iphash)
 178                       + map->probes * sizeof(uint32_t), GFP_ATOMIC);
 179         if (!tmp) {
 180                 DP("out of memory for %d bytes",
 181                    sizeof(struct ip_set_iphash)
 182                    + map->probes * sizeof(uint32_t));
 183                 return -ENOMEM;
 184         }
 185         tmp->members = harray_malloc(hashsize, sizeof(ip_set_ip_t), GFP_ATOMIC);
 186         if (!tmp->members) {
 187                 DP("out of memory for %d bytes", hashsize * sizeof(ip_set_ip_t));
 188                 kfree(tmp);
 189                 return -ENOMEM;
 190         }
 191         tmp->hashsize = hashsize;
 192         tmp->elements = 0;
 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));
 197
 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);
 202                 if (*elem)
 203                         res = __addip(tmp, *elem, &hash_ip);
 204         }
 205         if (res) {
 206                 /* Failure, try again */
 207                 write_unlock_bh(&set->lock);
 208                 harray_free(tmp->members);
 209                 kfree(tmp);
 210                 goto again;
 211         }
 212
 213         /* Success at resizing! */
 214         members = map->members;
 215
 216         map->hashsize = tmp->hashsize;
 217         map->members = tmp->members;
 218         write_unlock_bh(&set->lock);
 219
 220         harray_free(members);
 221         kfree(tmp);
 222
 223         return 0;
 224 }
 225
 226 static inline int
 227 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
 228 {
 229         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 230         ip_set_ip_t id, *elem;
 231
 232         if (!ip)
 233                 return -ERANGE;
 234
 235         id = hash_id(set, ip, hash_ip);
 236         if (id == UINT_MAX)
 237                 return -EEXIST;
 238
 239         elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
 240         *elem = 0;
 241         map->elements--;
 242
 243         return 0;
 244 }
 245
 246 static int
 247 delip(struct ip_set *set, const void *data, size_t size,
 248         ip_set_ip_t *hash_ip)
 249 {
 250         struct ip_set_req_iphash *req =
 251             (struct ip_set_req_iphash *) data;
 252
 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),
 256                               size);
 257                 return -EINVAL;
 258         }
 259         return __delip(set, req->ip, hash_ip);
 260 }
 261
 262 static int
 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,
 267              unsigned char index)
 268 {
 269         return __delip(set,
 270                        ntohl(flags[index] & IPSET_SRC
 271                                 ? skb->nh.iph->saddr
 272                                 : skb->nh.iph->daddr),
 273                        hash_ip);
 274 }
 275
 276 static int create(struct ip_set *set, const void *data, size_t size)
 277 {
 278         struct ip_set_req_iphash_create *req =
 279             (struct ip_set_req_iphash_create *) data;
 280         struct ip_set_iphash *map;
 281         uint16_t i;
 282
 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),
 286                                size);
 287                 return -EINVAL;
 288         }
 289
 290         if (req->hashsize < 1) {
 291                 ip_set_printk("hashsize too small");
 292                 return -ENOEXEC;
 293         }
 294
 295         if (req->probes < 1) {
 296                 ip_set_printk("probes too small");
 297                 return -ENOEXEC;
 298         }
 299
 300         map = kmalloc(sizeof(struct ip_set_iphash)
 301                       + req->probes * sizeof(uint32_t), GFP_KERNEL);
 302         if (!map) {
 303                 DP("out of memory for %d bytes",
 304                    sizeof(struct ip_set_iphash)
 305                    + req->probes * sizeof(uint32_t));
 306                 return -ENOMEM;
 307         }
 308         for (i = 0; i < req->probes; i++)
 309                 get_random_bytes(((uint32_t *) map->initval)+i, 4);
 310         map->elements = 0;
 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);
 316         if (!map->members) {
 317                 DP("out of memory for %d bytes", map->hashsize * sizeof(ip_set_ip_t));
 318                 kfree(map);
 319                 return -ENOMEM;
 320         }
 321
 322         set->data = map;
 323         return 0;
 324 }
 325
 326 static void destroy(struct ip_set *set)
 327 {
 328         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 329
 330         harray_free(map->members);
 331         kfree(map);
 332
 333         set->data = NULL;
 334 }
 335
 336 static void flush(struct ip_set *set)
 337 {
 338         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 339         harray_flush(map->members, map->hashsize, sizeof(ip_set_ip_t));
 340         map->elements = 0;
 341 }
 342
 343 static void list_header(const struct ip_set *set, void *data)
 344 {
 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;
 348
 349         header->hashsize = map->hashsize;
 350         header->probes = map->probes;
 351         header->resize = map->resize;
 352         header->netmask = map->netmask;
 353 }
 354
 355 static int list_members_size(const struct ip_set *set)
 356 {
 357         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 358
 359         return (map->hashsize * sizeof(ip_set_ip_t));
 360 }
 361
 362 static void list_members(const struct ip_set *set, void *data)
 363 {
 364         struct ip_set_iphash *map = (struct ip_set_iphash *) set->data;
 365         ip_set_ip_t i, *elem;
 366
 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;
 370         }
 371 }
 372
 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,
 377         .create                 = &create,
 378         .destroy                = &destroy,
 379         .flush                  = &flush,
 380         .reqsize                = sizeof(struct ip_set_req_iphash),
 381         .addip                  = &addip,
 382         .addip_kernel           = &addip_kernel,
 383         .retry                  = &retry,
 384         .delip                  = &delip,
 385         .delip_kernel           = &delip_kernel,
 386         .testip                 = &testip,
 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,
 392         .me                     = THIS_MODULE,
 393 };
 394
 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");
 400
 401 static int __init init(void)
 402 {
 403         return ip_set_register_set_type(&ip_set_iphash);
 404 }
 405
 406 static void __exit fini(void)
 407 {
 408         /* FIXME: possible race with ip_set_create() */
 409         ip_set_unregister_set_type(&ip_set_iphash);
 410 }
 411
 412 module_init(init);
 413 module_exit(fini);