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/rhashtable.h>
19#include <linux/netfilter.h>
20#include <linux/netfilter/nf_tables.h>
21#include <net/netfilter/nf_tables.h>
22
23/* We target a hash table size of 4, element hint is 75% of final size */
24#define NFT_HASH_ELEMENT_HINT 3
25
26struct nft_hash_elem {
27	struct rhash_head		node;
28	struct nft_data			key;
29	struct nft_data			data[];
30};
31
32static bool nft_hash_lookup(const struct nft_set *set,
33			    const struct nft_data *key,
34			    struct nft_data *data)
35{
36	const struct rhashtable *priv = nft_set_priv(set);
37	const struct nft_hash_elem *he;
38
39	he = rhashtable_lookup(priv, key);
40	if (he && set->flags & NFT_SET_MAP)
41		nft_data_copy(data, he->data);
42
43	return !!he;
44}
45
46static int nft_hash_insert(const struct nft_set *set,
47			   const struct nft_set_elem *elem)
48{
49	struct rhashtable *priv = nft_set_priv(set);
50	struct nft_hash_elem *he;
51	unsigned int size;
52
53	if (elem->flags != 0)
54		return -EINVAL;
55
56	size = sizeof(*he);
57	if (set->flags & NFT_SET_MAP)
58		size += sizeof(he->data[0]);
59
60	he = kzalloc(size, GFP_KERNEL);
61	if (he == NULL)
62		return -ENOMEM;
63
64	nft_data_copy(&he->key, &elem->key);
65	if (set->flags & NFT_SET_MAP)
66		nft_data_copy(he->data, &elem->data);
67
68	rhashtable_insert(priv, &he->node, GFP_KERNEL);
69
70	return 0;
71}
72
73static void nft_hash_elem_destroy(const struct nft_set *set,
74				  struct nft_hash_elem *he)
75{
76	nft_data_uninit(&he->key, NFT_DATA_VALUE);
77	if (set->flags & NFT_SET_MAP)
78		nft_data_uninit(he->data, set->dtype);
79	kfree(he);
80}
81
82static void nft_hash_remove(const struct nft_set *set,
83			    const struct nft_set_elem *elem)
84{
85	struct rhashtable *priv = nft_set_priv(set);
86	struct rhash_head *he, __rcu **pprev;
87
88	pprev = elem->cookie;
89	he = rht_dereference((*pprev), priv);
90
91	rhashtable_remove_pprev(priv, he, pprev, GFP_KERNEL);
92
93	synchronize_rcu();
94	kfree(he);
95}
96
97static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem)
98{
99	const struct rhashtable *priv = nft_set_priv(set);
100	const struct bucket_table *tbl = rht_dereference_rcu(priv->tbl, priv);
101	struct rhash_head __rcu * const *pprev;
102	struct nft_hash_elem *he;
103	u32 h;
104
105	h = rhashtable_hashfn(priv, &elem->key, set->klen);
106	pprev = &tbl->buckets[h];
107	rht_for_each_entry_rcu(he, tbl->buckets[h], node) {
108		if (nft_data_cmp(&he->key, &elem->key, set->klen)) {
109			pprev = &he->node.next;
110			continue;
111		}
112
113		elem->cookie = (void *)pprev;
114		elem->flags = 0;
115		if (set->flags & NFT_SET_MAP)
116			nft_data_copy(&elem->data, he->data);
117		return 0;
118	}
119	return -ENOENT;
120}
121
122static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
123			  struct nft_set_iter *iter)
124{
125	const struct rhashtable *priv = nft_set_priv(set);
126	const struct bucket_table *tbl;
127	const struct nft_hash_elem *he;
128	struct nft_set_elem elem;
129	unsigned int i;
130
131	tbl = rht_dereference_rcu(priv->tbl, priv);
132	for (i = 0; i < tbl->size; i++) {
133		rht_for_each_entry_rcu(he, tbl->buckets[i], node) {
134			if (iter->count < iter->skip)
135				goto cont;
136
137			memcpy(&elem.key, &he->key, sizeof(elem.key));
138			if (set->flags & NFT_SET_MAP)
139				memcpy(&elem.data, he->data, sizeof(elem.data));
140			elem.flags = 0;
141
142			iter->err = iter->fn(ctx, set, iter, &elem);
143			if (iter->err < 0)
144				return;
145cont:
146			iter->count++;
147		}
148	}
149}
150
151static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
152{
153	return sizeof(struct rhashtable);
154}
155
156static int lockdep_nfnl_lock_is_held(void)
157{
158	return lockdep_nfnl_is_held(NFNL_SUBSYS_NFTABLES);
159}
160
161static int nft_hash_init(const struct nft_set *set,
162			 const struct nft_set_desc *desc,
163			 const struct nlattr * const tb[])
164{
165	struct rhashtable *priv = nft_set_priv(set);
166	struct rhashtable_params params = {
167		.nelem_hint = desc->size ? : NFT_HASH_ELEMENT_HINT,
168		.head_offset = offsetof(struct nft_hash_elem, node),
169		.key_offset = offsetof(struct nft_hash_elem, key),
170		.key_len = set->klen,
171		.hashfn = jhash,
172		.grow_decision = rht_grow_above_75,
173		.shrink_decision = rht_shrink_below_30,
174		.mutex_is_held = lockdep_nfnl_lock_is_held,
175	};
176
177	return rhashtable_init(priv, &params);
178}
179
180static void nft_hash_destroy(const struct nft_set *set)
181{
182	const struct rhashtable *priv = nft_set_priv(set);
183	const struct bucket_table *tbl = priv->tbl;
184	struct nft_hash_elem *he, *next;
185	unsigned int i;
186
187	for (i = 0; i < tbl->size; i++) {
188		for (he = rht_entry(tbl->buckets[i], struct nft_hash_elem, node);
189		     he != NULL; he = next) {
190			next = rht_entry(he->node.next, struct nft_hash_elem, node);
191			nft_hash_elem_destroy(set, he);
192		}
193	}
194	rhashtable_destroy(priv);
195}
196
197static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
198			      struct nft_set_estimate *est)
199{
200	unsigned int esize;
201
202	esize = sizeof(struct nft_hash_elem);
203	if (features & NFT_SET_MAP)
204		esize += FIELD_SIZEOF(struct nft_hash_elem, data[0]);
205
206	if (desc->size) {
207		est->size = sizeof(struct rhashtable) +
208			    roundup_pow_of_two(desc->size * 4 / 3) *
209			    sizeof(struct nft_hash_elem *) +
210			    desc->size * esize;
211	} else {
212		/* Resizing happens when the load drops below 30% or goes
213		 * above 75%. The average of 52.5% load (approximated by 50%)
214		 * is used for the size estimation of the hash buckets,
215		 * meaning we calculate two buckets per element.
216		 */
217		est->size = esize + 2 * sizeof(struct nft_hash_elem *);
218	}
219
220	est->class = NFT_SET_CLASS_O_1;
221
222	return true;
223}
224
225static struct nft_set_ops nft_hash_ops __read_mostly = {
226	.privsize       = nft_hash_privsize,
227	.estimate	= nft_hash_estimate,
228	.init		= nft_hash_init,
229	.destroy	= nft_hash_destroy,
230	.get		= nft_hash_get,
231	.insert		= nft_hash_insert,
232	.remove		= nft_hash_remove,
233	.lookup		= nft_hash_lookup,
234	.walk		= nft_hash_walk,
235	.features	= NFT_SET_MAP,
236	.owner		= THIS_MODULE,
237};
238
239static int __init nft_hash_module_init(void)
240{
241	return nft_register_set(&nft_hash_ops);
242}
243
244static void __exit nft_hash_module_exit(void)
245{
246	nft_unregister_set(&nft_hash_ops);
247}
248
249module_init(nft_hash_module_init);
250module_exit(nft_hash_module_exit);
251
252MODULE_LICENSE("GPL");
253MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
254MODULE_ALIAS_NFT_SET();
255