1 /* 2 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net> 3 * 4 * This program is free software; you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License version 2 as 6 * published by the Free Software Foundation. 7 * 8 * Development of this code funded by Astaro AG (http://www.astaro.com/) 9 */ 10 11 #include <linux/kernel.h> 12 #include <linux/init.h> 13 #include <linux/module.h> 14 #include <linux/list.h> 15 #include <linux/log2.h> 16 #include <linux/jhash.h> 17 #include <linux/netlink.h> 18 #include <linux/workqueue.h> 19 #include <linux/rhashtable.h> 20 #include <linux/netfilter.h> 21 #include <linux/netfilter/nf_tables.h> 22 #include <net/netfilter/nf_tables.h> 23 24 /* We target a hash table size of 4, element hint is 75% of final size */ 25 #define NFT_HASH_ELEMENT_HINT 3 26 27 struct nft_hash { 28 struct rhashtable ht; 29 struct delayed_work gc_work; 30 }; 31 32 struct nft_hash_elem { 33 struct rhash_head node; 34 struct nft_set_ext ext; 35 }; 36 37 struct nft_hash_cmp_arg { 38 const struct nft_set *set; 39 const u32 *key; 40 u8 genmask; 41 }; 42 43 static const struct rhashtable_params nft_hash_params; 44 45 static inline u32 nft_hash_key(const void *data, u32 len, u32 seed) 46 { 47 const struct nft_hash_cmp_arg *arg = data; 48 49 return jhash(arg->key, len, seed); 50 } 51 52 static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed) 53 { 54 const struct nft_hash_elem *he = data; 55 56 return jhash(nft_set_ext_key(&he->ext), len, seed); 57 } 58 59 static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg, 60 const void *ptr) 61 { 62 const struct nft_hash_cmp_arg *x = arg->key; 63 const struct nft_hash_elem *he = ptr; 64 65 if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen)) 66 return 1; 67 if (nft_set_elem_expired(&he->ext)) 68 return 1; 69 if (!nft_set_elem_active(&he->ext, x->genmask)) 70 return 1; 71 return 0; 72 } 73 74 static bool nft_hash_lookup(const struct nft_set *set, const u32 *key, 75 const struct nft_set_ext **ext) 76 { 77 struct nft_hash *priv = nft_set_priv(set); 78 const struct nft_hash_elem *he; 79 struct nft_hash_cmp_arg arg = { 80 .genmask = nft_genmask_cur(read_pnet(&set->pnet)), 81 .set = set, 82 .key = key, 83 }; 84 85 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); 86 if (he != NULL) 87 *ext = &he->ext; 88 89 return !!he; 90 } 91 92 static bool nft_hash_update(struct nft_set *set, const u32 *key, 93 void *(*new)(struct nft_set *, 94 const struct nft_expr *, 95 struct nft_regs *regs), 96 const struct nft_expr *expr, 97 struct nft_regs *regs, 98 const struct nft_set_ext **ext) 99 { 100 struct nft_hash *priv = nft_set_priv(set); 101 struct nft_hash_elem *he; 102 struct nft_hash_cmp_arg arg = { 103 .genmask = NFT_GENMASK_ANY, 104 .set = set, 105 .key = key, 106 }; 107 108 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); 109 if (he != NULL) 110 goto out; 111 112 he = new(set, expr, regs); 113 if (he == NULL) 114 goto err1; 115 if (rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node, 116 nft_hash_params)) 117 goto err2; 118 out: 119 *ext = &he->ext; 120 return true; 121 122 err2: 123 nft_set_elem_destroy(set, he); 124 err1: 125 return false; 126 } 127 128 static int nft_hash_insert(const struct nft_set *set, 129 const struct nft_set_elem *elem) 130 { 131 struct nft_hash *priv = nft_set_priv(set); 132 struct nft_hash_elem *he = elem->priv; 133 struct nft_hash_cmp_arg arg = { 134 .genmask = nft_genmask_next(read_pnet(&set->pnet)), 135 .set = set, 136 .key = elem->key.val.data, 137 }; 138 139 return rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node, 140 nft_hash_params); 141 } 142 143 static void nft_hash_activate(const struct nft_set *set, 144 const struct nft_set_elem *elem) 145 { 146 struct nft_hash_elem *he = elem->priv; 147 148 nft_set_elem_change_active(set, &he->ext); 149 nft_set_elem_clear_busy(&he->ext); 150 } 151 152 static void *nft_hash_deactivate(const struct nft_set *set, 153 const struct nft_set_elem *elem) 154 { 155 struct nft_hash *priv = nft_set_priv(set); 156 struct nft_hash_elem *he; 157 struct nft_hash_cmp_arg arg = { 158 .genmask = nft_genmask_next(read_pnet(&set->pnet)), 159 .set = set, 160 .key = elem->key.val.data, 161 }; 162 163 rcu_read_lock(); 164 he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params); 165 if (he != NULL) { 166 if (!nft_set_elem_mark_busy(&he->ext)) 167 nft_set_elem_change_active(set, &he->ext); 168 else 169 he = NULL; 170 } 171 rcu_read_unlock(); 172 173 return he; 174 } 175 176 static void nft_hash_remove(const struct nft_set *set, 177 const struct nft_set_elem *elem) 178 { 179 struct nft_hash *priv = nft_set_priv(set); 180 struct nft_hash_elem *he = elem->priv; 181 182 rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params); 183 } 184 185 static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set, 186 struct nft_set_iter *iter) 187 { 188 struct nft_hash *priv = nft_set_priv(set); 189 struct nft_hash_elem *he; 190 struct rhashtable_iter hti; 191 struct nft_set_elem elem; 192 int err; 193 194 err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL); 195 iter->err = err; 196 if (err) 197 return; 198 199 err = rhashtable_walk_start(&hti); 200 if (err && err != -EAGAIN) { 201 iter->err = err; 202 goto out; 203 } 204 205 while ((he = rhashtable_walk_next(&hti))) { 206 if (IS_ERR(he)) { 207 err = PTR_ERR(he); 208 if (err != -EAGAIN) { 209 iter->err = err; 210 goto out; 211 } 212 213 continue; 214 } 215 216 if (iter->count < iter->skip) 217 goto cont; 218 if (nft_set_elem_expired(&he->ext)) 219 goto cont; 220 if (!nft_set_elem_active(&he->ext, iter->genmask)) 221 goto cont; 222 223 elem.priv = he; 224 225 iter->err = iter->fn(ctx, set, iter, &elem); 226 if (iter->err < 0) 227 goto out; 228 229 cont: 230 iter->count++; 231 } 232 233 out: 234 rhashtable_walk_stop(&hti); 235 rhashtable_walk_exit(&hti); 236 } 237 238 static void nft_hash_gc(struct work_struct *work) 239 { 240 struct nft_set *set; 241 struct nft_hash_elem *he; 242 struct nft_hash *priv; 243 struct nft_set_gc_batch *gcb = NULL; 244 struct rhashtable_iter hti; 245 int err; 246 247 priv = container_of(work, struct nft_hash, gc_work.work); 248 set = nft_set_container_of(priv); 249 250 err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL); 251 if (err) 252 goto schedule; 253 254 err = rhashtable_walk_start(&hti); 255 if (err && err != -EAGAIN) 256 goto out; 257 258 while ((he = rhashtable_walk_next(&hti))) { 259 if (IS_ERR(he)) { 260 if (PTR_ERR(he) != -EAGAIN) 261 goto out; 262 continue; 263 } 264 265 if (!nft_set_elem_expired(&he->ext)) 266 continue; 267 if (nft_set_elem_mark_busy(&he->ext)) 268 continue; 269 270 gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC); 271 if (gcb == NULL) 272 goto out; 273 rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params); 274 atomic_dec(&set->nelems); 275 nft_set_gc_batch_add(gcb, he); 276 } 277 out: 278 rhashtable_walk_stop(&hti); 279 rhashtable_walk_exit(&hti); 280 281 nft_set_gc_batch_complete(gcb); 282 schedule: 283 queue_delayed_work(system_power_efficient_wq, &priv->gc_work, 284 nft_set_gc_interval(set)); 285 } 286 287 static unsigned int nft_hash_privsize(const struct nlattr * const nla[]) 288 { 289 return sizeof(struct nft_hash); 290 } 291 292 static const struct rhashtable_params nft_hash_params = { 293 .head_offset = offsetof(struct nft_hash_elem, node), 294 .hashfn = nft_hash_key, 295 .obj_hashfn = nft_hash_obj, 296 .obj_cmpfn = nft_hash_cmp, 297 .automatic_shrinking = true, 298 }; 299 300 static int nft_hash_init(const struct nft_set *set, 301 const struct nft_set_desc *desc, 302 const struct nlattr * const tb[]) 303 { 304 struct nft_hash *priv = nft_set_priv(set); 305 struct rhashtable_params params = nft_hash_params; 306 int err; 307 308 params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT; 309 params.key_len = set->klen; 310 311 err = rhashtable_init(&priv->ht, ¶ms); 312 if (err < 0) 313 return err; 314 315 INIT_DEFERRABLE_WORK(&priv->gc_work, nft_hash_gc); 316 if (set->flags & NFT_SET_TIMEOUT) 317 queue_delayed_work(system_power_efficient_wq, &priv->gc_work, 318 nft_set_gc_interval(set)); 319 return 0; 320 } 321 322 static void nft_hash_elem_destroy(void *ptr, void *arg) 323 { 324 nft_set_elem_destroy((const struct nft_set *)arg, ptr); 325 } 326 327 static void nft_hash_destroy(const struct nft_set *set) 328 { 329 struct nft_hash *priv = nft_set_priv(set); 330 331 cancel_delayed_work_sync(&priv->gc_work); 332 rhashtable_free_and_destroy(&priv->ht, nft_hash_elem_destroy, 333 (void *)set); 334 } 335 336 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features, 337 struct nft_set_estimate *est) 338 { 339 unsigned int esize; 340 341 esize = sizeof(struct nft_hash_elem); 342 if (desc->size) { 343 est->size = sizeof(struct nft_hash) + 344 roundup_pow_of_two(desc->size * 4 / 3) * 345 sizeof(struct nft_hash_elem *) + 346 desc->size * esize; 347 } else { 348 /* Resizing happens when the load drops below 30% or goes 349 * above 75%. The average of 52.5% load (approximated by 50%) 350 * is used for the size estimation of the hash buckets, 351 * meaning we calculate two buckets per element. 352 */ 353 est->size = esize + 2 * sizeof(struct nft_hash_elem *); 354 } 355 356 est->class = NFT_SET_CLASS_O_1; 357 358 return true; 359 } 360 361 static struct nft_set_ops nft_hash_ops __read_mostly = { 362 .privsize = nft_hash_privsize, 363 .elemsize = offsetof(struct nft_hash_elem, ext), 364 .estimate = nft_hash_estimate, 365 .init = nft_hash_init, 366 .destroy = nft_hash_destroy, 367 .insert = nft_hash_insert, 368 .activate = nft_hash_activate, 369 .deactivate = nft_hash_deactivate, 370 .remove = nft_hash_remove, 371 .lookup = nft_hash_lookup, 372 .update = nft_hash_update, 373 .walk = nft_hash_walk, 374 .features = NFT_SET_MAP | NFT_SET_TIMEOUT, 375 .owner = THIS_MODULE, 376 }; 377 378 static int __init nft_hash_module_init(void) 379 { 380 return nft_register_set(&nft_hash_ops); 381 } 382 383 static void __exit nft_hash_module_exit(void) 384 { 385 nft_unregister_set(&nft_hash_ops); 386 } 387 388 module_init(nft_hash_module_init); 389 module_exit(nft_hash_module_exit); 390 391 MODULE_LICENSE("GPL"); 392 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>"); 393 MODULE_ALIAS_NFT_SET(); 394