xref: /linux/net/netfilter/nft_set_bitmap.c (revision d642ef71) 
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (c) 2017 Pablo Neira Ayuso <pablo@netfilter.org>
4  */
5 
6 #include <linux/kernel.h>
7 #include <linux/init.h>
8 #include <linux/module.h>
9 #include <linux/list.h>
10 #include <linux/netlink.h>
11 #include <linux/netfilter.h>
12 #include <linux/netfilter/nf_tables.h>
13 #include <net/netfilter/nf_tables_core.h>
14 
15 struct nft_bitmap_elem {
16 	struct nft_elem_priv	priv;
17 	struct list_head	head;
18 	struct nft_set_ext	ext;
19 };
20 
21 /* This bitmap uses two bits to represent one element. These two bits determine
22  * the element state in the current and the future generation.
23  *
24  * An element can be in three states. The generation cursor is represented using
25  * the ^ character, note that this cursor shifts on every successful transaction.
26  * If no transaction is going on, we observe all elements are in the following
27  * state:
28  *
29  * 11 = this element is active in the current generation. In case of no updates,
30  * ^    it stays active in the next generation.
31  * 00 = this element is inactive in the current generation. In case of no
32  * ^    updates, it stays inactive in the next generation.
33  *
34  * On transaction handling, we observe these two temporary states:
35  *
36  * 01 = this element is inactive in the current generation and it becomes active
37  * ^    in the next one. This happens when the element is inserted but commit
38  *      path has not yet been executed yet, so activation is still pending. On
39  *      transaction abortion, the element is removed.
40  * 10 = this element is active in the current generation and it becomes inactive
41  * ^    in the next one. This happens when the element is deactivated but commit
42  *      path has not yet been executed yet, so removal is still pending. On
43  *      transaction abortion, the next generation bit is reset to go back to
44  *      restore its previous state.
45  */
46 struct nft_bitmap {
47 	struct	list_head	list;
48 	u16			bitmap_size;
49 	u8			bitmap[];
50 };
51 
52 static inline void nft_bitmap_location(const struct nft_set *set,
53 				       const void *key,
54 				       u32 *idx, u32 *off)
55 {
56 	u32 k;
57 
58 	if (set->klen == 2)
59 		k = *(u16 *)key;
60 	else
61 		k = *(u8 *)key;
62 	k <<= 1;
63 
64 	*idx = k / BITS_PER_BYTE;
65 	*off = k % BITS_PER_BYTE;
66 }
67 
68 /* Fetch the two bits that represent the element and check if it is active based
69  * on the generation mask.
70  */
71 static inline bool
72 nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
73 {
74 	return (bitmap[idx] & (0x3 << off)) & (genmask << off);
75 }
76 
77 INDIRECT_CALLABLE_SCOPE
78 bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
79 		       const u32 *key, const struct nft_set_ext **ext)
80 {
81 	const struct nft_bitmap *priv = nft_set_priv(set);
82 	u8 genmask = nft_genmask_cur(net);
83 	u32 idx, off;
84 
85 	nft_bitmap_location(set, key, &idx, &off);
86 
87 	return nft_bitmap_active(priv->bitmap, idx, off, genmask);
88 }
89 
90 static struct nft_bitmap_elem *
91 nft_bitmap_elem_find(const struct nft_set *set, struct nft_bitmap_elem *this,
92 		     u8 genmask)
93 {
94 	const struct nft_bitmap *priv = nft_set_priv(set);
95 	struct nft_bitmap_elem *be;
96 
97 	list_for_each_entry_rcu(be, &priv->list, head) {
98 		if (memcmp(nft_set_ext_key(&be->ext),
99 			   nft_set_ext_key(&this->ext), set->klen) ||
100 		    !nft_set_elem_active(&be->ext, genmask))
101 			continue;
102 
103 		return be;
104 	}
105 	return NULL;
106 }
107 
108 static struct nft_elem_priv *
109 nft_bitmap_get(const struct net *net, const struct nft_set *set,
110 	       const struct nft_set_elem *elem, unsigned int flags)
111 {
112 	const struct nft_bitmap *priv = nft_set_priv(set);
113 	u8 genmask = nft_genmask_cur(net);
114 	struct nft_bitmap_elem *be;
115 
116 	list_for_each_entry_rcu(be, &priv->list, head) {
117 		if (memcmp(nft_set_ext_key(&be->ext), elem->key.val.data, set->klen) ||
118 		    !nft_set_elem_active(&be->ext, genmask))
119 			continue;
120 
121 		return &be->priv;
122 	}
123 	return ERR_PTR(-ENOENT);
124 }
125 
126 static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
127 			     const struct nft_set_elem *elem,
128 			     struct nft_elem_priv **elem_priv)
129 {
130 	struct nft_bitmap_elem *new = nft_elem_priv_cast(elem->priv), *be;
131 	struct nft_bitmap *priv = nft_set_priv(set);
132 	u8 genmask = nft_genmask_next(net);
133 	u32 idx, off;
134 
135 	be = nft_bitmap_elem_find(set, new, genmask);
136 	if (be) {
137 		*elem_priv = &be->priv;
138 		return -EEXIST;
139 	}
140 
141 	nft_bitmap_location(set, nft_set_ext_key(&new->ext), &idx, &off);
142 	/* Enter 01 state. */
143 	priv->bitmap[idx] |= (genmask << off);
144 	list_add_tail_rcu(&new->head, &priv->list);
145 
146 	return 0;
147 }
148 
149 static void nft_bitmap_remove(const struct net *net, const struct nft_set *set,
150 			      struct nft_elem_priv *elem_priv)
151 {
152 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
153 	struct nft_bitmap *priv = nft_set_priv(set);
154 	u8 genmask = nft_genmask_next(net);
155 	u32 idx, off;
156 
157 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
158 	/* Enter 00 state. */
159 	priv->bitmap[idx] &= ~(genmask << off);
160 	list_del_rcu(&be->head);
161 }
162 
163 static void nft_bitmap_activate(const struct net *net,
164 				const struct nft_set *set,
165 				struct nft_elem_priv *elem_priv)
166 {
167 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
168 	struct nft_bitmap *priv = nft_set_priv(set);
169 	u8 genmask = nft_genmask_next(net);
170 	u32 idx, off;
171 
172 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
173 	/* Enter 11 state. */
174 	priv->bitmap[idx] |= (genmask << off);
175 	nft_set_elem_change_active(net, set, &be->ext);
176 }
177 
178 static void nft_bitmap_flush(const struct net *net,
179 			     const struct nft_set *set,
180 			     struct nft_elem_priv *elem_priv)
181 {
182 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
183 	struct nft_bitmap *priv = nft_set_priv(set);
184 	u8 genmask = nft_genmask_next(net);
185 	u32 idx, off;
186 
187 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
188 	/* Enter 10 state, similar to deactivation. */
189 	priv->bitmap[idx] &= ~(genmask << off);
190 	nft_set_elem_change_active(net, set, &be->ext);
191 }
192 
193 static struct nft_elem_priv *
194 nft_bitmap_deactivate(const struct net *net, const struct nft_set *set,
195 		      const struct nft_set_elem *elem)
196 {
197 	struct nft_bitmap_elem *this = nft_elem_priv_cast(elem->priv), *be;
198 	struct nft_bitmap *priv = nft_set_priv(set);
199 	u8 genmask = nft_genmask_next(net);
200 	u32 idx, off;
201 
202 	nft_bitmap_location(set, elem->key.val.data, &idx, &off);
203 
204 	be = nft_bitmap_elem_find(set, this, genmask);
205 	if (!be)
206 		return NULL;
207 
208 	/* Enter 10 state. */
209 	priv->bitmap[idx] &= ~(genmask << off);
210 	nft_set_elem_change_active(net, set, &be->ext);
211 
212 	return &be->priv;
213 }
214 
215 static void nft_bitmap_walk(const struct nft_ctx *ctx,
216 			    struct nft_set *set,
217 			    struct nft_set_iter *iter)
218 {
219 	const struct nft_bitmap *priv = nft_set_priv(set);
220 	struct nft_bitmap_elem *be;
221 
222 	list_for_each_entry_rcu(be, &priv->list, head) {
223 		if (iter->count < iter->skip)
224 			goto cont;
225 		if (!nft_set_elem_active(&be->ext, iter->genmask))
226 			goto cont;
227 
228 		iter->err = iter->fn(ctx, set, iter, &be->priv);
229 
230 		if (iter->err < 0)
231 			return;
232 cont:
233 		iter->count++;
234 	}
235 }
236 
237 /* The bitmap size is pow(2, key length in bits) / bits per byte. This is
238  * multiplied by two since each element takes two bits. For 8 bit keys, the
239  * bitmap consumes 66 bytes. For 16 bit keys, 16388 bytes.
240  */
241 static inline u32 nft_bitmap_size(u32 klen)
242 {
243 	return ((2 << ((klen * BITS_PER_BYTE) - 1)) / BITS_PER_BYTE) << 1;
244 }
245 
246 static inline u64 nft_bitmap_total_size(u32 klen)
247 {
248 	return sizeof(struct nft_bitmap) + nft_bitmap_size(klen);
249 }
250 
251 static u64 nft_bitmap_privsize(const struct nlattr * const nla[],
252 			       const struct nft_set_desc *desc)
253 {
254 	u32 klen = ntohl(nla_get_be32(nla[NFTA_SET_KEY_LEN]));
255 
256 	return nft_bitmap_total_size(klen);
257 }
258 
259 static int nft_bitmap_init(const struct nft_set *set,
260 			   const struct nft_set_desc *desc,
261 			   const struct nlattr * const nla[])
262 {
263 	struct nft_bitmap *priv = nft_set_priv(set);
264 
265 	BUILD_BUG_ON(offsetof(struct nft_bitmap_elem, priv) != 0);
266 
267 	INIT_LIST_HEAD(&priv->list);
268 	priv->bitmap_size = nft_bitmap_size(set->klen);
269 
270 	return 0;
271 }
272 
273 static void nft_bitmap_destroy(const struct nft_ctx *ctx,
274 			       const struct nft_set *set)
275 {
276 	struct nft_bitmap *priv = nft_set_priv(set);
277 	struct nft_bitmap_elem *be, *n;
278 
279 	list_for_each_entry_safe(be, n, &priv->list, head)
280 		nf_tables_set_elem_destroy(ctx, set, &be->priv);
281 }
282 
283 static bool nft_bitmap_estimate(const struct nft_set_desc *desc, u32 features,
284 				struct nft_set_estimate *est)
285 {
286 	/* Make sure bitmaps we don't get bitmaps larger than 16 Kbytes. */
287 	if (desc->klen > 2)
288 		return false;
289 	else if (desc->expr)
290 		return false;
291 
292 	est->size   = nft_bitmap_total_size(desc->klen);
293 	est->lookup = NFT_SET_CLASS_O_1;
294 	est->space  = NFT_SET_CLASS_O_1;
295 
296 	return true;
297 }
298 
299 const struct nft_set_type nft_set_bitmap_type = {
300 	.ops		= {
301 		.privsize	= nft_bitmap_privsize,
302 		.elemsize	= offsetof(struct nft_bitmap_elem, ext),
303 		.estimate	= nft_bitmap_estimate,
304 		.init		= nft_bitmap_init,
305 		.destroy	= nft_bitmap_destroy,
306 		.insert		= nft_bitmap_insert,
307 		.remove		= nft_bitmap_remove,
308 		.deactivate	= nft_bitmap_deactivate,
309 		.flush		= nft_bitmap_flush,
310 		.activate	= nft_bitmap_activate,
311 		.lookup		= nft_bitmap_lookup,
312 		.walk		= nft_bitmap_walk,
313 		.get		= nft_bitmap_get,
314 	},
315 };
316