xref: /linux/net/netfilter/nft_set_bitmap.c (revision 164666fa66669d437bdcc8d5f1744a2aee73be41) 
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 list_head	head;
17 	struct nft_set_ext	ext;
18 };
19 
20 /* This bitmap uses two bits to represent one element. These two bits determine
21  * the element state in the current and the future generation.
22  *
23  * An element can be in three states. The generation cursor is represented using
24  * the ^ character, note that this cursor shifts on every succesful transaction.
25  * If no transaction is going on, we observe all elements are in the following
26  * state:
27  *
28  * 11 = this element is active in the current generation. In case of no updates,
29  * ^    it stays active in the next generation.
30  * 00 = this element is inactive in the current generation. In case of no
31  * ^    updates, it stays inactive in the next generation.
32  *
33  * On transaction handling, we observe these two temporary states:
34  *
35  * 01 = this element is inactive in the current generation and it becomes active
36  * ^    in the next one. This happens when the element is inserted but commit
37  *      path has not yet been executed yet, so activation is still pending. On
38  *      transaction abortion, the element is removed.
39  * 10 = this element is active in the current generation and it becomes inactive
40  * ^    in the next one. This happens when the element is deactivated but commit
41  *      path has not yet been executed yet, so removal is still pending. On
42  *      transation abortion, the next generation bit is reset to go back to
43  *      restore its previous state.
44  */
45 struct nft_bitmap {
46 	struct	list_head	list;
47 	u16			bitmap_size;
48 	u8			bitmap[];
49 };
50 
51 static inline void nft_bitmap_location(const struct nft_set *set,
52 				       const void *key,
53 				       u32 *idx, u32 *off)
54 {
55 	u32 k;
56 
57 	if (set->klen == 2)
58 		k = *(u16 *)key;
59 	else
60 		k = *(u8 *)key;
61 	k <<= 1;
62 
63 	*idx = k / BITS_PER_BYTE;
64 	*off = k % BITS_PER_BYTE;
65 }
66 
67 /* Fetch the two bits that represent the element and check if it is active based
68  * on the generation mask.
69  */
70 static inline bool
71 nft_bitmap_active(const u8 *bitmap, u32 idx, u32 off, u8 genmask)
72 {
73 	return (bitmap[idx] & (0x3 << off)) & (genmask << off);
74 }
75 
76 INDIRECT_CALLABLE_SCOPE
77 bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
78 		       const u32 *key, const struct nft_set_ext **ext)
79 {
80 	const struct nft_bitmap *priv = nft_set_priv(set);
81 	u8 genmask = nft_genmask_cur(net);
82 	u32 idx, off;
83 
84 	nft_bitmap_location(set, key, &idx, &off);
85 
86 	return nft_bitmap_active(priv->bitmap, idx, off, genmask);
87 }
88 
89 static struct nft_bitmap_elem *
90 nft_bitmap_elem_find(const struct nft_set *set, struct nft_bitmap_elem *this,
91 		     u8 genmask)
92 {
93 	const struct nft_bitmap *priv = nft_set_priv(set);
94 	struct nft_bitmap_elem *be;
95 
96 	list_for_each_entry_rcu(be, &priv->list, head) {
97 		if (memcmp(nft_set_ext_key(&be->ext),
98 			   nft_set_ext_key(&this->ext), set->klen) ||
99 		    !nft_set_elem_active(&be->ext, genmask))
100 			continue;
101 
102 		return be;
103 	}
104 	return NULL;
105 }
106 
107 static void *nft_bitmap_get(const struct net *net, const struct nft_set *set,
108 			    const struct nft_set_elem *elem, unsigned int flags)
109 {
110 	const struct nft_bitmap *priv = nft_set_priv(set);
111 	u8 genmask = nft_genmask_cur(net);
112 	struct nft_bitmap_elem *be;
113 
114 	list_for_each_entry_rcu(be, &priv->list, head) {
115 		if (memcmp(nft_set_ext_key(&be->ext), elem->key.val.data, set->klen) ||
116 		    !nft_set_elem_active(&be->ext, genmask))
117 			continue;
118 
119 		return be;
120 	}
121 	return ERR_PTR(-ENOENT);
122 }
123 
124 static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
125 			     const struct nft_set_elem *elem,
126 			     struct nft_set_ext **ext)
127 {
128 	struct nft_bitmap *priv = nft_set_priv(set);
129 	struct nft_bitmap_elem *new = elem->priv, *be;
130 	u8 genmask = nft_genmask_next(net);
131 	u32 idx, off;
132 
133 	be = nft_bitmap_elem_find(set, new, genmask);
134 	if (be) {
135 		*ext = &be->ext;
136 		return -EEXIST;
137 	}
138 
139 	nft_bitmap_location(set, nft_set_ext_key(&new->ext), &idx, &off);
140 	/* Enter 01 state. */
141 	priv->bitmap[idx] |= (genmask << off);
142 	list_add_tail_rcu(&new->head, &priv->list);
143 
144 	return 0;
145 }
146 
147 static void nft_bitmap_remove(const struct net *net,
148 			      const struct nft_set *set,
149 			      const struct nft_set_elem *elem)
150 {
151 	struct nft_bitmap *priv = nft_set_priv(set);
152 	struct nft_bitmap_elem *be = elem->priv;
153 	u8 genmask = nft_genmask_next(net);
154 	u32 idx, off;
155 
156 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
157 	/* Enter 00 state. */
158 	priv->bitmap[idx] &= ~(genmask << off);
159 	list_del_rcu(&be->head);
160 }
161 
162 static void nft_bitmap_activate(const struct net *net,
163 				const struct nft_set *set,
164 				const struct nft_set_elem *elem)
165 {
166 	struct nft_bitmap *priv = nft_set_priv(set);
167 	struct nft_bitmap_elem *be = elem->priv;
168 	u8 genmask = nft_genmask_next(net);
169 	u32 idx, off;
170 
171 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
172 	/* Enter 11 state. */
173 	priv->bitmap[idx] |= (genmask << off);
174 	nft_set_elem_change_active(net, set, &be->ext);
175 }
176 
177 static bool nft_bitmap_flush(const struct net *net,
178 			     const struct nft_set *set, void *_be)
179 {
180 	struct nft_bitmap *priv = nft_set_priv(set);
181 	u8 genmask = nft_genmask_next(net);
182 	struct nft_bitmap_elem *be = _be;
183 	u32 idx, off;
184 
185 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
186 	/* Enter 10 state, similar to deactivation. */
187 	priv->bitmap[idx] &= ~(genmask << off);
188 	nft_set_elem_change_active(net, set, &be->ext);
189 
190 	return true;
191 }
192 
193 static void *nft_bitmap_deactivate(const struct net *net,
194 				   const struct nft_set *set,
195 				   const struct nft_set_elem *elem)
196 {
197 	struct nft_bitmap *priv = nft_set_priv(set);
198 	struct nft_bitmap_elem *this = elem->priv, *be;
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;
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 	struct nft_set_elem elem;
222 
223 	list_for_each_entry_rcu(be, &priv->list, head) {
224 		if (iter->count < iter->skip)
225 			goto cont;
226 		if (!nft_set_elem_active(&be->ext, iter->genmask))
227 			goto cont;
228 
229 		elem.priv = be;
230 
231 		iter->err = iter->fn(ctx, set, iter, &elem);
232 
233 		if (iter->err < 0)
234 			return;
235 cont:
236 		iter->count++;
237 	}
238 }
239 
240 /* The bitmap size is pow(2, key length in bits) / bits per byte. This is
241  * multiplied by two since each element takes two bits. For 8 bit keys, the
242  * bitmap consumes 66 bytes. For 16 bit keys, 16388 bytes.
243  */
244 static inline u32 nft_bitmap_size(u32 klen)
245 {
246 	return ((2 << ((klen * BITS_PER_BYTE) - 1)) / BITS_PER_BYTE) << 1;
247 }
248 
249 static inline u64 nft_bitmap_total_size(u32 klen)
250 {
251 	return sizeof(struct nft_bitmap) + nft_bitmap_size(klen);
252 }
253 
254 static u64 nft_bitmap_privsize(const struct nlattr * const nla[],
255 			       const struct nft_set_desc *desc)
256 {
257 	u32 klen = ntohl(nla_get_be32(nla[NFTA_SET_KEY_LEN]));
258 
259 	return nft_bitmap_total_size(klen);
260 }
261 
262 static int nft_bitmap_init(const struct nft_set *set,
263 			   const struct nft_set_desc *desc,
264 			   const struct nlattr * const nla[])
265 {
266 	struct nft_bitmap *priv = nft_set_priv(set);
267 
268 	INIT_LIST_HEAD(&priv->list);
269 	priv->bitmap_size = nft_bitmap_size(set->klen);
270 
271 	return 0;
272 }
273 
274 static void nft_bitmap_destroy(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 		nft_set_elem_destroy(set, be, true);
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