Release 4.14 net/netfilter/nft_set_rbtree.c

Directory: net/netfilter
/*
 * Copyright (c) 2008-2009 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/rbtree.h>
#include <linux/netlink.h>
#include <linux/netfilter.h>
#include <linux/netfilter/nf_tables.h>
#include <net/netfilter/nf_tables.h>


struct nft_rbtree {
	
struct rb_root		root;
	
rwlock_t		lock;
	
seqcount_t		count;
};


struct nft_rbtree_elem {
	
struct rb_node		node;
	
struct nft_set_ext	ext;
};



static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe)
{
	return nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) &&
	       (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END);
}

Contributors
Person Tokens Prop Commits CommitProp
Pablo Neira Ayuso 36 100.00% 1 100.00%
Total 36 100.00% 1 100.00%



static bool nft_rbtree_equal(const struct nft_set *set, const void *this,
			     const struct nft_rbtree_elem *interval)
{
	return memcmp(this, nft_set_ext_key(&interval->ext), set->klen) == 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Pablo Neira Ayuso 43 100.00% 1 100.00%
Total 43 100.00% 1 100.00%



static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set,
				const u32 *key, const struct nft_set_ext **ext,
				unsigned int seq)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	const struct nft_rbtree_elem *rbe, *interval = NULL;
	u8 genmask = nft_genmask_cur(net);
	const struct rb_node *parent;
	const void *this;
	int d;

	parent = rcu_dereference_raw(priv->root.rb_node);
	while (parent != NULL) {
		if (read_seqcount_retry(&priv->count, seq))
			return false;

		rbe = rb_entry(parent, struct nft_rbtree_elem, node);

		this = nft_set_ext_key(&rbe->ext);
		d = memcmp(this, key, set->klen);
		if (d < 0) {
			parent = rcu_dereference_raw(parent->rb_left);
			if (interval &&
			    nft_rbtree_equal(set, this, interval) &&
			    nft_rbtree_interval_end(this) &&
			    !nft_rbtree_interval_end(interval))
				continue;
			interval = rbe;
		} else if (d > 0)
			parent = rcu_dereference_raw(parent->rb_right);
		else {
			if (!nft_set_elem_active(&rbe->ext, genmask)) {
				parent = rcu_dereference_raw(parent->rb_left);
				continue;
			}
			if (nft_rbtree_interval_end(rbe))
				goto out;

			*ext = &rbe->ext;
			return true;
		}
	}

	if (set->flags & NFT_SET_INTERVAL && interval != NULL &&
	    nft_set_elem_active(&interval->ext, genmask) &&
	    !nft_rbtree_interval_end(interval)) {
		*ext = &interval->ext;
		return true;
	}
out:
	return false;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 192 63.37% 6 50.00%
Pablo Neira Ayuso 75 24.75% 5 41.67%
Florian Westphal 36 11.88% 1 8.33%
Total 303 100.00% 12 100.00%



static bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set,
			      const u32 *key, const struct nft_set_ext **ext)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	unsigned int seq = read_seqcount_begin(&priv->count);
	bool ret;

	ret = __nft_rbtree_lookup(net, set, key, ext, seq);
	if (ret || !read_seqcount_retry(&priv->count, seq))
		return ret;

	read_lock_bh(&priv->lock);
	seq = read_seqcount_begin(&priv->count);
	ret = __nft_rbtree_lookup(net, set, key, ext, seq);
	read_unlock_bh(&priv->lock);

	return ret;
}

Contributors
Person Tokens Prop Commits CommitProp
Florian Westphal 121 91.67% 1 25.00%
Pablo Neira Ayuso 4 3.03% 1 25.00%
Liping Zhang 4 3.03% 1 25.00%
Patrick McHardy 3 2.27% 1 25.00%
Total 132 100.00% 4 100.00%



static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set,
			       struct nft_rbtree_elem *new,
			       struct nft_set_ext **ext)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	u8 genmask = nft_genmask_next(net);
	struct nft_rbtree_elem *rbe;
	struct rb_node *parent, **p;
	int d;

	parent = NULL;
	p = &priv->root.rb_node;
	while (*p != NULL) {
		parent = *p;
		rbe = rb_entry(parent, struct nft_rbtree_elem, node);
		d = memcmp(nft_set_ext_key(&rbe->ext),
			   nft_set_ext_key(&new->ext),
			   set->klen);
		if (d < 0)
			p = &parent->rb_left;
		else if (d > 0)
			p = &parent->rb_right;
		else {
			if (nft_rbtree_interval_end(rbe) &&
			    !nft_rbtree_interval_end(new)) {
				p = &parent->rb_left;
			} else if (!nft_rbtree_interval_end(rbe) &&
				   nft_rbtree_interval_end(new)) {
				p = &parent->rb_right;
			} else if (nft_set_elem_active(&rbe->ext, genmask)) {
				*ext = &rbe->ext;
				return -EEXIST;
			} else {
				p = &parent->rb_left;
			}
		}
	}
	rb_link_node_rcu(&new->node, parent, p);
	rb_insert_color(&new->node, &priv->root);
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 174 64.93% 4 44.44%
Pablo Neira Ayuso 93 34.70% 4 44.44%
Florian Westphal 1 0.37% 1 11.11%
Total 268 100.00% 9 100.00%



static int nft_rbtree_insert(const struct net *net, const struct nft_set *set,
			     const struct nft_set_elem *elem,
			     struct nft_set_ext **ext)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	struct nft_rbtree_elem *rbe = elem->priv;
	int err;

	write_lock_bh(&priv->lock);
	write_seqcount_begin(&priv->count);
	err = __nft_rbtree_insert(net, set, rbe, ext);
	write_seqcount_end(&priv->count);
	write_unlock_bh(&priv->lock);

	return err;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 42 42.00% 2 28.57%
Pablo Neira Ayuso 24 24.00% 3 42.86%
Liping Zhang 18 18.00% 1 14.29%
Florian Westphal 16 16.00% 1 14.29%
Total 100 100.00% 7 100.00%



static void nft_rbtree_remove(const struct net *net,
			      const struct nft_set *set,
			      const struct nft_set_elem *elem)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	struct nft_rbtree_elem *rbe = elem->priv;

	write_lock_bh(&priv->lock);
	write_seqcount_begin(&priv->count);
	rb_erase(&rbe->node, &priv->root);
	write_seqcount_end(&priv->count);
	write_unlock_bh(&priv->lock);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 50 56.82% 2 33.33%
Florian Westphal 16 18.18% 1 16.67%
Pablo Neira Ayuso 14 15.91% 2 33.33%
Liping Zhang 8 9.09% 1 16.67%
Total 88 100.00% 6 100.00%



static void nft_rbtree_activate(const struct net *net,
				const struct nft_set *set,
				const struct nft_set_elem *elem)
{
	struct nft_rbtree_elem *rbe = elem->priv;

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

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 37 82.22% 2 66.67%
Pablo Neira Ayuso 8 17.78% 1 33.33%
Total 45 100.00% 3 100.00%



static bool nft_rbtree_flush(const struct net *net,
			     const struct nft_set *set, void *priv)
{
	struct nft_rbtree_elem *rbe = priv;

	nft_set_elem_change_active(net, set, &rbe->ext);
	return true;
}

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



static void *nft_rbtree_deactivate(const struct net *net,
				   const struct nft_set *set,
				   const struct nft_set_elem *elem)
{
	const struct nft_rbtree *priv = nft_set_priv(set);
	const struct rb_node *parent = priv->root.rb_node;
	struct nft_rbtree_elem *rbe, *this = elem->priv;
	u8 genmask = nft_genmask_next(net);
	int d;

	while (parent != NULL) {
		rbe = rb_entry(parent, struct nft_rbtree_elem, node);

		d = memcmp(nft_set_ext_key(&rbe->ext), &elem->key.val,
					   set->klen);
		if (d < 0)
			parent = parent->rb_left;
		else if (d > 0)
			parent = parent->rb_right;
		else {
			if (!nft_set_elem_active(&rbe->ext, genmask)) {
				parent = parent->rb_left;
				continue;
			}
			if (nft_rbtree_interval_end(rbe) &&
			    !nft_rbtree_interval_end(this)) {
				parent = parent->rb_left;
				continue;
			} else if (!nft_rbtree_interval_end(rbe) &&
				   nft_rbtree_interval_end(this)) {
				parent = parent->rb_right;
				continue;
			}
			nft_rbtree_flush(net, set, rbe);
			return rbe;
		}
	}
	return NULL;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 162 72.00% 5 55.56%
Pablo Neira Ayuso 63 28.00% 4 44.44%
Total 225 100.00% 9 100.00%



static void nft_rbtree_walk(const struct nft_ctx *ctx,
			    struct nft_set *set,
			    struct nft_set_iter *iter)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	struct nft_rbtree_elem *rbe;
	struct nft_set_elem elem;
	struct rb_node *node;

	read_lock_bh(&priv->lock);
	for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) {
		rbe = rb_entry(node, struct nft_rbtree_elem, node);

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

		elem.priv = rbe;

		iter->err = iter->fn(ctx, set, iter, &elem);
		if (iter->err < 0) {
			read_unlock_bh(&priv->lock);
			return;
		}
cont:
		iter->count++;
	}
	read_unlock_bh(&priv->lock);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 152 84.44% 3 50.00%
Pablo Neira Ayuso 16 8.89% 2 33.33%
Liping Zhang 12 6.67% 1 16.67%
Total 180 100.00% 6 100.00%



static unsigned int nft_rbtree_privsize(const struct nlattr * const nla[],
					const struct nft_set_desc *desc)
{
	return sizeof(struct nft_rbtree);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 22 78.57% 1 50.00%
Pablo Neira Ayuso 6 21.43% 1 50.00%
Total 28 100.00% 2 100.00%



static int nft_rbtree_init(const struct nft_set *set,
			   const struct nft_set_desc *desc,
			   const struct nlattr * const nla[])
{
	struct nft_rbtree *priv = nft_set_priv(set);

	rwlock_init(&priv->lock);
	seqcount_init(&priv->count);
	priv->root = RB_ROOT;
	return 0;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 45 73.77% 2 50.00%
Liping Zhang 8 13.11% 1 25.00%
Florian Westphal 8 13.11% 1 25.00%
Total 61 100.00% 4 100.00%



static void nft_rbtree_destroy(const struct nft_set *set)
{
	struct nft_rbtree *priv = nft_set_priv(set);
	struct nft_rbtree_elem *rbe;
	struct rb_node *node;

	while ((node = priv->root.rb_node) != NULL) {
		rb_erase(node, &priv->root);
		rbe = rb_entry(node, struct nft_rbtree_elem, node);
		nft_set_elem_destroy(set, rbe, true);
	}
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 77 97.47% 2 66.67%
Liping Zhang 2 2.53% 1 33.33%
Total 79 100.00% 3 100.00%



static bool nft_rbtree_estimate(const struct nft_set_desc *desc, u32 features,
				struct nft_set_estimate *est)
{
	if (desc->size)
		est->size = sizeof(struct nft_rbtree) +
			    desc->size * sizeof(struct nft_rbtree_elem);
	else
		est->size = ~0;

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

	return true;
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 55 79.71% 1 25.00%
Pablo Neira Ayuso 14 20.29% 3 75.00%
Total 69 100.00% 4 100.00%


static struct nft_set_type nft_rbtree_type;

static struct nft_set_ops nft_rbtree_ops __read_mostly = {
	.type		= &nft_rbtree_type,
	.privsize	= nft_rbtree_privsize,
	.elemsize	= offsetof(struct nft_rbtree_elem, ext),
	.estimate	= nft_rbtree_estimate,
	.init		= nft_rbtree_init,
	.destroy	= nft_rbtree_destroy,
	.insert		= nft_rbtree_insert,
	.remove		= nft_rbtree_remove,
	.deactivate	= nft_rbtree_deactivate,
	.flush		= nft_rbtree_flush,
	.activate	= nft_rbtree_activate,
	.lookup		= nft_rbtree_lookup,
	.walk		= nft_rbtree_walk,
	.features	= NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT,
};


static struct nft_set_type nft_rbtree_type __read_mostly = {
	.ops		= &nft_rbtree_ops,
	.owner		= THIS_MODULE,
};



static int __init nft_rbtree_module_init(void)
{
	return nft_register_set(&nft_rbtree_type);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 15 93.75% 1 50.00%
Pablo Neira Ayuso 1 6.25% 1 50.00%
Total 16 100.00% 2 100.00%



static void __exit nft_rbtree_module_exit(void)
{
	nft_unregister_set(&nft_rbtree_type);
}

Contributors
Person Tokens Prop Commits CommitProp
Patrick McHardy 14 93.33% 1 50.00%
Pablo Neira Ayuso 1 6.67% 1 50.00%
Total 15 100.00% 2 100.00%


module_init(nft_rbtree_module_init);

module_exit(nft_rbtree_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 1194 62.06% 10 30.30%
Pablo Neira Ayuso 474 24.64% 20 60.61%
Florian Westphal 204 10.60% 1 3.03%
Liping Zhang 52 2.70% 2 6.06%
Total 1924 100.00% 33 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
Pablo Neira Ayuso	36	100.00%	1	100.00%
Total	36	100.00%	1	100.00%
cregit-Linux how code gets into the kernel

Release 4.14 net/netfilter/nft_set_rbtree.c

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Contributors

Overall Contributors
