Release 4.11 net/netfilter/nft_set_hash.c

Directory: net/netfilter
/*
 * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
 *
 * 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.
 *
 * Development of this code funded by Astaro AG (http://www.astaro.com/)
 */

#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/module.h>
#include <linux/list.h>
#include <linux/log2.h>
#include <linux/jhash.h>
#include <linux/netlink.h>
#include <linux/workqueue.h>
#include <linux/rhashtable.h>
#include <linux/netfilter.h>
#include <linux/netfilter/nf_tables.h>
#include <net/netfilter/nf_tables.h>

/* We target a hash table size of 4, element hint is 75% of final size */

#define NFT_HASH_ELEMENT_HINT 3


struct nft_hash {
	
struct rhashtable		ht;
	
struct delayed_work		gc_work;
};


struct nft_hash_elem {
	
struct rhash_head		node;
	
struct nft_set_ext		ext;
};


struct nft_hash_cmp_arg {
	
const struct nft_set		*set;
	
const u32			*key;
	
u8				genmask;
};


static const struct rhashtable_params nft_hash_params;



static inline u32 nft_hash_key(const void *data, u32 len, u32 seed)
{
	const struct nft_hash_cmp_arg *arg = data;

	return jhash(arg->key, len, seed);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 38 100.00% 1 100.00%
Total 38 100.00% 1 100.00%



static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed)
{
	const struct nft_hash_elem *he = data;

	return jhash(nft_set_ext_key(&he->ext), len, seed);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 42 100.00% 2 100.00%
Total 42 100.00% 2 100.00%



static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg,
			       const void *ptr)
{
	const struct nft_hash_cmp_arg *x = arg->key;
	const struct nft_hash_elem *he = ptr;

	if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
		return 1;
	if (nft_set_elem_expired(&he->ext))
		return 1;
	if (!nft_set_elem_active(&he->ext, x->genmask))
		return 1;
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 95 100.00% 5 100.00%
Total 95 100.00% 5 100.00%



static bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
			    const u32 *key, const struct nft_set_ext **ext)
{
	struct nft_hash *priv = nft_set_priv(set);
	const struct nft_hash_elem *he;
	struct nft_hash_cmp_arg arg = {
		.genmask = nft_genmask_cur(net),
		.set	 = set,
		.key	 = key,
        };

	he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
	if (he != NULL)
		*ext = &he->ext;

	return !!he;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 73 70.19% 7 70.00%
Thomas Graf 21 20.19% 1 10.00%
Pablo Neira Ayuso 7 6.73% 1 10.00%
Herbert Xu 3 2.88% 1 10.00%
Total 104 100.00% 10 100.00%



static bool nft_hash_update(struct nft_set *set, const u32 *key,
			    void *(*new)(struct nft_set *,
					 const struct nft_expr *,
					 struct nft_regs *regs),
			    const struct nft_expr *expr,
			    struct nft_regs *regs,
			    const struct nft_set_ext **ext)
{
	struct nft_hash *priv = nft_set_priv(set);
	struct nft_hash_elem *he, *prev;
	struct nft_hash_cmp_arg arg = {
		.genmask = NFT_GENMASK_ANY,
		.set	 = set,
		.key	 = key,
        };

	he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
	if (he != NULL)
		goto out;

	he = new(set, expr, regs);
	if (he == NULL)
		goto err1;

	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
						nft_hash_params);
	if (IS_ERR(prev))
		goto err2;

	/* Another cpu may race to insert the element with the same key */
	if (prev) {
		nft_set_elem_destroy(set, he, true);
		he = prev;
	}

out:
	*ext = &he->ext;
	return true;

err2:
	nft_set_elem_destroy(set, he, true);
err1:
	return false;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 183 83.94% 3 60.00%
Liping Zhang 35 16.06% 2 40.00%
Total 218 100.00% 5 100.00%



static int nft_hash_insert(const struct net *net, const struct nft_set *set,
			   const struct nft_set_elem *elem,
			   struct nft_set_ext **ext)
{
	struct nft_hash *priv = nft_set_priv(set);
	struct nft_hash_elem *he = elem->priv;
	struct nft_hash_cmp_arg arg = {
		.genmask = nft_genmask_next(net),
		.set	 = set,
		.key	 = elem->key.val.data,
        };
	struct nft_hash_elem *prev;

	prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
					       nft_hash_params);
	if (IS_ERR(prev))
		return PTR_ERR(prev);
	if (prev) {
		*ext = &prev->ext;
		return -EEXIST;
	}
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 77 55.80% 7 63.64%
Pablo Neira Ayuso 55 39.86% 2 18.18%
Thomas Graf 3 2.17% 1 9.09%
Herbert Xu 3 2.17% 1 9.09%
Total 138 100.00% 11 100.00%



static void nft_hash_activate(const struct net *net, const struct nft_set *set,
			      const struct nft_set_elem *elem)
{
	struct nft_hash_elem *he = elem->priv;

	nft_set_elem_change_active(net, set, &he->ext);
	nft_set_elem_clear_busy(&he->ext);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 44 83.02% 5 71.43%
Pablo Neira Ayuso 8 15.09% 1 14.29%
Thomas Graf 1 1.89% 1 14.29%
Total 53 100.00% 7 100.00%



static bool nft_hash_flush(const struct net *net,
			   const struct nft_set *set, void *priv)
{
	struct nft_hash_elem *he = priv;

	if (!nft_set_elem_mark_busy(&he->ext) ||
	    !nft_is_active(net, &he->ext)) {
		nft_set_elem_change_active(net, set, &he->ext);
		return true;
	}
	return false;
}

Contributors
Person Tokens Prop Commits CommitProp
Pablo Neira Ayuso 71 100.00% 2 100.00%
Total 71 100.00% 2 100.00%



static void *nft_hash_deactivate(const struct net *net,
				 const struct nft_set *set,
				 const struct nft_set_elem *elem)
{
	struct nft_hash *priv = nft_set_priv(set);
	struct nft_hash_elem *he;
	struct nft_hash_cmp_arg arg = {
		.genmask = nft_genmask_next(net),
		.set	 = set,
		.key	 = elem->key.val.data,
        };

	rcu_read_lock();
	he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
	if (he != NULL &&
	    !nft_hash_flush(net, set, he))
		he = NULL;

	rcu_read_unlock();

	return he;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 81 71.05% 9 64.29%
Herbert Xu 21 18.42% 1 7.14%
Pablo Neira Ayuso 12 10.53% 4 28.57%
Total 114 100.00% 14 100.00%



static void nft_hash_remove(const struct net *net,
			    const struct nft_set *set,
			    const struct nft_set_elem *elem)
{
	struct nft_hash *priv = nft_set_priv(set);
	struct nft_hash_elem *he = elem->priv;

	rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 50 86.21% 4 66.67%
Pablo Neira Ayuso 6 10.34% 1 16.67%
Thomas Graf 2 3.45% 1 16.67%
Total 58 100.00% 6 100.00%



static void nft_hash_walk(const struct nft_ctx *ctx, struct nft_set *set,
			  struct nft_set_iter *iter)
{
	struct nft_hash *priv = nft_set_priv(set);
	struct nft_hash_elem *he;
	struct rhashtable_iter hti;
	struct nft_set_elem elem;
	int err;

	err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL);
	iter->err = err;
	if (err)
		return;

	err = rhashtable_walk_start(&hti);
	if (err && err != -EAGAIN) {
		iter->err = err;
		goto out;
	}

	while ((he = rhashtable_walk_next(&hti))) {
		if (IS_ERR(he)) {
			err = PTR_ERR(he);
			if (err != -EAGAIN) {
				iter->err = err;
				goto out;
			}

			continue;
		}

		if (iter->count < iter->skip)
			goto cont;
		if (nft_set_elem_expired(&he->ext))
			goto cont;
		if (!nft_set_elem_active(&he->ext, iter->genmask))
			goto cont;

		elem.priv = he;

		iter->err = iter->fn(ctx, set, iter, &elem);
		if (iter->err < 0)
			goto out;

cont:
		iter->count++;
	}

out:
	rhashtable_walk_stop(&hti);
	rhashtable_walk_exit(&hti);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 134 53.39% 6 54.55%
Herbert Xu 107 42.63% 2 18.18%
Thomas Graf 6 2.39% 1 9.09%
Bob Copeland 2 0.80% 1 9.09%
Pablo Neira Ayuso 2 0.80% 1 9.09%
Total 251 100.00% 11 100.00%



static void nft_hash_gc(struct work_struct *work)
{
	struct nft_set *set;
	struct nft_hash_elem *he;
	struct nft_hash *priv;
	struct nft_set_gc_batch *gcb = NULL;
	struct rhashtable_iter hti;
	int err;

	priv = container_of(work, struct nft_hash, gc_work.work);
	set  = nft_set_container_of(priv);

	err = rhashtable_walk_init(&priv->ht, &hti, GFP_KERNEL);
	if (err)
		goto schedule;

	err = rhashtable_walk_start(&hti);
	if (err && err != -EAGAIN)
		goto out;

	while ((he = rhashtable_walk_next(&hti))) {
		if (IS_ERR(he)) {
			if (PTR_ERR(he) != -EAGAIN)
				goto out;
			continue;
		}

		if (!nft_set_elem_expired(&he->ext))
			continue;
		if (nft_set_elem_mark_busy(&he->ext))
			continue;

		gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC);
		if (gcb == NULL)
			goto out;
		rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
		atomic_dec(&set->nelems);
		nft_set_gc_batch_add(gcb, he);
	}
out:
	rhashtable_walk_stop(&hti);
	rhashtable_walk_exit(&hti);

	nft_set_gc_batch_complete(gcb);
schedule:
	queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
			   nft_set_gc_interval(set));
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 247 99.20% 2 66.67%
Bob Copeland 2 0.80% 1 33.33%
Total 249 100.00% 3 100.00%



static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
{
	return sizeof(struct nft_hash);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 19 86.36% 3 75.00%
Thomas Graf 3 13.64% 1 25.00%
Total 22 100.00% 4 100.00%


static const struct rhashtable_params nft_hash_params = {
	.head_offset		= offsetof(struct nft_hash_elem, node),
	.hashfn			= nft_hash_key,
	.obj_hashfn		= nft_hash_obj,
	.obj_cmpfn		= nft_hash_cmp,
	.automatic_shrinking	= true,
};



static int nft_hash_init(const struct nft_set *set,
			 const struct nft_set_desc *desc,
			 const struct nlattr * const tb[])
{
	struct nft_hash *priv = nft_set_priv(set);
	struct rhashtable_params params = nft_hash_params;
	int err;

	params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT;
	params.key_len	  = set->klen;

	err = rhashtable_init(&priv->ht, &params);
	if (err < 0)
		return err;

	INIT_DEFERRABLE_WORK(&priv->gc_work, nft_hash_gc);
	if (set->flags & NFT_SET_TIMEOUT)
		queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
				   nft_set_gc_interval(set));
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 99 81.15% 6 75.00%
Thomas Graf 15 12.30% 1 12.50%
Herbert Xu 8 6.56% 1 12.50%
Total 122 100.00% 8 100.00%



static void nft_hash_elem_destroy(void *ptr, void *arg)
{
	nft_set_elem_destroy((const struct nft_set *)arg, ptr, true);
}

Contributors
Person Tokens Prop Commits CommitProp
Thomas Graf 25 86.21% 1 33.33%
Patrick McHardy 2 6.90% 1 33.33%
Liping Zhang 2 6.90% 1 33.33%
Total 29 100.00% 3 100.00%



static void nft_hash_destroy(const struct nft_set *set)
{
	struct nft_hash *priv = nft_set_priv(set);

	cancel_delayed_work_sync(&priv->gc_work);
	rhashtable_free_and_destroy(&priv->ht, nft_hash_elem_destroy,
				    (void *)set);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 40 86.96% 5 62.50%
Thomas Graf 6 13.04% 3 37.50%
Total 46 100.00% 8 100.00%



static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
			      struct nft_set_estimate *est)
{
	unsigned int esize;

	esize = sizeof(struct nft_hash_elem);
	if (desc->size) {
		est->size = sizeof(struct nft_hash) +
			    roundup_pow_of_two(desc->size * 4 / 3) *
			    sizeof(struct nft_hash_elem *) +
			    desc->size * esize;
	} else {
		/* Resizing happens when the load drops below 30% or goes
                 * above 75%. The average of 52.5% load (approximated by 50%)
                 * is used for the size estimation of the hash buckets,
                 * meaning we calculate two buckets per element.
                 */
		est->size = esize + 2 * sizeof(struct nft_hash_elem *);
	}

	est->lookup = NFT_SET_CLASS_O_1;
	est->space  = NFT_SET_CLASS_O_N;

	return true;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 96 88.89% 2 40.00%
Pablo Neira Ayuso 7 6.48% 2 40.00%
Thomas Graf 5 4.63% 1 20.00%
Total 108 100.00% 5 100.00%


static struct nft_set_ops nft_hash_ops __read_mostly = {
	.privsize       = nft_hash_privsize,
	.elemsize	= offsetof(struct nft_hash_elem, ext),
	.estimate	= nft_hash_estimate,
	.init		= nft_hash_init,
	.destroy	= nft_hash_destroy,
	.insert		= nft_hash_insert,
	.activate	= nft_hash_activate,
	.deactivate	= nft_hash_deactivate,
	.flush		= nft_hash_flush,
	.remove		= nft_hash_remove,
	.lookup		= nft_hash_lookup,
	.update		= nft_hash_update,
	.walk		= nft_hash_walk,
	.features	= NFT_SET_MAP | NFT_SET_OBJECT | NFT_SET_TIMEOUT,
	.owner		= THIS_MODULE,
};



static int __init nft_hash_module_init(void)
{
	return nft_register_set(&nft_hash_ops);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 16 100.00% 2 100.00%
Total 16 100.00% 2 100.00%



static void __exit nft_hash_module_exit(void)
{
	nft_unregister_set(&nft_hash_ops);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 15 100.00% 2 100.00%
Total 15 100.00% 2 100.00%


module_init(nft_hash_module_init);

module_exit(nft_hash_module_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
MODULE_ALIAS_NFT_SET();
Overall Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 1539 75.55% 17 41.46%
Pablo Neira Ayuso 175 8.59% 11 26.83%
Herbert Xu 173 8.49% 3 7.32%
Thomas Graf 107 5.25% 6 14.63%
Liping Zhang 37 1.82% 2 4.88%
Bob Copeland 4 0.20% 1 2.44%
David S. Miller 2 0.10% 1 2.44%
Total 2037 100.00% 41 100.00%
Directory: net/netfilter

Information contained on this website is for historical information purposes only and does not indicate or represent copyright ownership.
Created with cregit.
Person	Tokens	Prop	Commits	CommitProp
Patrick McHardy	38	100.00%	1	100.00%
Total	38	100.00%	1	100.00%
cregit-Linux how code gets into the kernel

Release 4.11 net/netfilter/nft_set_hash.c

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Overall Contributors
