release/src-rt-6.x/linux/linux-2.6/net/ipv4/netfilter/ip_set_nethash.c

   1 /* Copyright (C) 2003-2008 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 a cidr nethash set */
   9
  10 #include <linux/module.h>
  11 #include <linux/moduleparam.h>
  12 #include <linux/ip.h>
  13 #include <linux/skbuff.h>
  14 #include <linux/netfilter_ipv4/ip_set_jhash.h>
  15 #include <linux/errno.h>
  16 #include <asm/uaccess.h>
  17 #include <asm/bitops.h>
  18 #include <linux/spinlock.h>
  19 #include <linux/random.h>
  20
  21 #include <net/ip.h>
  22
  23 #include <linux/netfilter_ipv4/ip_set_nethash.h>
  24
  25 static int limit = MAX_RANGE;
  26
  27 static inline __u32
  28 nethash_id_cidr(const struct ip_set_nethash *map,
  29                 ip_set_ip_t ip,
  30                 uint8_t cidr)
  31 {
  32         __u32 id;
  33         u_int16_t i;
  34         ip_set_ip_t *elem;
  35
  36         ip = pack_ip_cidr(ip, cidr);
  37         if (!ip)
  38                 return MAX_RANGE;
  39
  40         for (i = 0; i < map->probes; i++) {
  41                 id = jhash_ip(map, i, ip) % map->hashsize;
  42                 DP("hash key: %u", id);
  43                 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
  44                 if (*elem == ip)
  45                         return id;
  46                 /* No shortcut - there can be deleted entries. */
  47         }
  48         return UINT_MAX;
  49 }
  50
  51 static inline __u32
  52 nethash_id(struct ip_set *set, ip_set_ip_t ip)
  53 {
  54         const struct ip_set_nethash *map = set->data;
  55         __u32 id = UINT_MAX;
  56         int i;
  57
  58         for (i = 0; i < 30 && map->cidr[i]; i++) {
  59                 id = nethash_id_cidr(map, ip, map->cidr[i]);
  60                 if (id != UINT_MAX)
  61                         break;
  62         }
  63         return id;
  64 }
  65
  66 static inline int
  67 nethash_test_cidr(struct ip_set *set, ip_set_ip_t ip, uint8_t cidr)
  68 {
  69         const struct ip_set_nethash *map = set->data;
  70
  71         return (nethash_id_cidr(map, ip, cidr) != UINT_MAX);
  72 }
  73
  74 static inline int
  75 nethash_test(struct ip_set *set, ip_set_ip_t ip)
  76 {
  77         return (nethash_id(set, ip) != UINT_MAX);
  78 }
  79
  80 static int
  81 nethash_utest(struct ip_set *set, const void *data, u_int32_t size)
  82 {
  83         const struct ip_set_req_nethash *req = data;
  84
  85         if (req->cidr <= 0 || req->cidr > 32)
  86                 return -EINVAL;
  87         return (req->cidr == 32 ? nethash_test(set, req->ip)
  88                 : nethash_test_cidr(set, req->ip, req->cidr));
  89 }
  90
  91 #define KADT_CONDITION
  92
  93 KADT(nethash, test, ipaddr)
  94
  95 static inline int
  96 __nethash_add(struct ip_set_nethash *map, ip_set_ip_t *ip)
  97 {
  98         __u32 probe;
  99         u_int16_t i;
 100         ip_set_ip_t *elem, *slot = NULL;
 101
 102         for (i = 0; i < map->probes; i++) {
 103                 probe = jhash_ip(map, i, *ip) % map->hashsize;
 104                 elem = HARRAY_ELEM(map->members, ip_set_ip_t *, probe);
 105                 if (*elem == *ip)
 106                         return -EEXIST;
 107                 if (!(slot || *elem))
 108                         slot = elem;
 109                 /* There can be deleted entries, must check all slots */
 110         }
 111         if (slot) {
 112                 *slot = *ip;
 113                 map->elements++;
 114                 return 0;
 115         }
 116         /* Trigger rehashing */
 117         return -EAGAIN;
 118 }
 119
 120 static inline int
 121 nethash_add(struct ip_set *set, ip_set_ip_t ip, uint8_t cidr)
 122 {
 123         struct ip_set_nethash *map = set->data;
 124         int ret;
 125
 126         if (map->elements >= limit || map->nets[cidr-1] == UINT16_MAX)
 127                 return -ERANGE;
 128         if (cidr <= 0 || cidr >= 32)
 129                 return -EINVAL;
 130
 131         ip = pack_ip_cidr(ip, cidr);
 132         if (!ip)
 133                 return -ERANGE;
 134
 135         ret = __nethash_add(map, &ip);
 136         if (ret == 0) {
 137                 if (!map->nets[cidr-1]++)
 138                         add_cidr_size(map->cidr, cidr);
 139         }
 140
 141         return ret;
 142 }
 143
 144 #undef KADT_CONDITION
 145 #define KADT_CONDITION                                                  \
 146         struct ip_set_nethash *map = set->data;                         \
 147         uint8_t cidr = map->cidr[0] ? map->cidr[0] : 31;
 148
 149 UADT(nethash, add, req->cidr)
 150 KADT(nethash, add, ipaddr, cidr)
 151
 152 static inline void
 153 __nethash_retry(struct ip_set_nethash *tmp, struct ip_set_nethash *map)
 154 {
 155         memcpy(tmp->cidr, map->cidr, sizeof(tmp->cidr));
 156         memcpy(tmp->nets, map->nets, sizeof(tmp->nets));
 157 }
 158
 159 HASH_RETRY(nethash, ip_set_ip_t)
 160
 161 static inline int
 162 nethash_del(struct ip_set *set, ip_set_ip_t ip, uint8_t cidr)
 163 {
 164         struct ip_set_nethash *map = set->data;
 165         ip_set_ip_t id, *elem;
 166
 167         if (cidr <= 0 || cidr >= 32)
 168                 return -EINVAL;
 169
 170         id = nethash_id_cidr(map, ip, cidr);
 171         if (id == UINT_MAX)
 172                 return -EEXIST;
 173
 174         elem = HARRAY_ELEM(map->members, ip_set_ip_t *, id);
 175         *elem = 0;
 176         map->elements--;
 177         if (!map->nets[cidr-1]--)
 178                 del_cidr_size(map->cidr, cidr);
 179         return 0;
 180 }
 181
 182 UADT(nethash, del, req->cidr)
 183 KADT(nethash, del, ipaddr, cidr)
 184
 185 static inline int
 186 __nethash_create(const struct ip_set_req_nethash_create *req,
 187                  struct ip_set_nethash *map)
 188 {
 189         memset(map->cidr, 0, sizeof(map->cidr));
 190         memset(map->nets, 0, sizeof(map->nets));
 191
 192         return 0;
 193 }
 194
 195 HASH_CREATE(nethash, ip_set_ip_t)
 196 HASH_DESTROY(nethash)
 197
 198 HASH_FLUSH_CIDR(nethash, ip_set_ip_t)
 199
 200 static inline void
 201 __nethash_list_header(const struct ip_set_nethash *map,
 202                       struct ip_set_req_nethash_create *header)
 203 {
 204 }
 205
 206 HASH_LIST_HEADER(nethash)
 207 HASH_LIST_MEMBERS_SIZE(nethash, ip_set_ip_t)
 208 HASH_LIST_MEMBERS(nethash, ip_set_ip_t)
 209
 210 IP_SET_RTYPE(nethash, IPSET_TYPE_IP | IPSET_DATA_SINGLE)
 211
 212 MODULE_LICENSE("GPL");
 213 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
 214 MODULE_DESCRIPTION("nethash type of IP sets");
 215 module_param(limit, int, 0600);
 216 MODULE_PARM_DESC(limit, "maximal number of elements stored in the sets");
 217
 218 REGISTER_MODULE(nethash)