xref: /linux/net/netfilter/nft_set_bitmap.c (revision 44f57d78) 
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.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 static bool nft_bitmap_lookup(const struct net *net, const struct nft_set *set,
77 			      const u32 *key, const struct nft_set_ext **ext)
78 {
79 	const struct nft_bitmap *priv = nft_set_priv(set);
80 	u8 genmask = nft_genmask_cur(net);
81 	u32 idx, off;
82 
83 	nft_bitmap_location(set, key, &idx, &off);
84 
85 	return nft_bitmap_active(priv->bitmap, idx, off, genmask);
86 }
87 
88 static struct nft_bitmap_elem *
89 nft_bitmap_elem_find(const struct nft_set *set, struct nft_bitmap_elem *this,
90 		     u8 genmask)
91 {
92 	const struct nft_bitmap *priv = nft_set_priv(set);
93 	struct nft_bitmap_elem *be;
94 
95 	list_for_each_entry_rcu(be, &priv->list, head) {
96 		if (memcmp(nft_set_ext_key(&be->ext),
97 			   nft_set_ext_key(&this->ext), set->klen) ||
98 		    !nft_set_elem_active(&be->ext, genmask))
99 			continue;
100 
101 		return be;
102 	}
103 	return NULL;
104 }
105 
106 static void *nft_bitmap_get(const struct net *net, const struct nft_set *set,
107 			    const struct nft_set_elem *elem, unsigned int flags)
108 {
109 	const struct nft_bitmap *priv = nft_set_priv(set);
110 	u8 genmask = nft_genmask_cur(net);
111 	struct nft_bitmap_elem *be;
112 
113 	list_for_each_entry_rcu(be, &priv->list, head) {
114 		if (memcmp(nft_set_ext_key(&be->ext), elem->key.val.data, set->klen) ||
115 		    !nft_set_elem_active(&be->ext, genmask))
116 			continue;
117 
118 		return be;
119 	}
120 	return ERR_PTR(-ENOENT);
121 }
122 
123 static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
124 			     const struct nft_set_elem *elem,
125 			     struct nft_set_ext **ext)
126 {
127 	struct nft_bitmap *priv = nft_set_priv(set);
128 	struct nft_bitmap_elem *new = elem->priv, *be;
129 	u8 genmask = nft_genmask_next(net);
130 	u32 idx, off;
131 
132 	be = nft_bitmap_elem_find(set, new, genmask);
133 	if (be) {
134 		*ext = &be->ext;
135 		return -EEXIST;
136 	}
137 
138 	nft_bitmap_location(set, nft_set_ext_key(&new->ext), &idx, &off);
139 	/* Enter 01 state. */
140 	priv->bitmap[idx] |= (genmask << off);
141 	list_add_tail_rcu(&new->head, &priv->list);
142 
143 	return 0;
144 }
145 
146 static void nft_bitmap_remove(const struct net *net,
147 			      const struct nft_set *set,
148 			      const struct nft_set_elem *elem)
149 {
150 	struct nft_bitmap *priv = nft_set_priv(set);
151 	struct nft_bitmap_elem *be = elem->priv;
152 	u8 genmask = nft_genmask_next(net);
153 	u32 idx, off;
154 
155 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
156 	/* Enter 00 state. */
157 	priv->bitmap[idx] &= ~(genmask << off);
158 	list_del_rcu(&be->head);
159 }
160 
161 static void nft_bitmap_activate(const struct net *net,
162 				const struct nft_set *set,
163 				const struct nft_set_elem *elem)
164 {
165 	struct nft_bitmap *priv = nft_set_priv(set);
166 	struct nft_bitmap_elem *be = elem->priv;
167 	u8 genmask = nft_genmask_next(net);
168 	u32 idx, off;
169 
170 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
171 	/* Enter 11 state. */
172 	priv->bitmap[idx] |= (genmask << off);
173 	nft_set_elem_change_active(net, set, &be->ext);
174 }
175 
176 static bool nft_bitmap_flush(const struct net *net,
177 			     const struct nft_set *set, void *_be)
178 {
179 	struct nft_bitmap *priv = nft_set_priv(set);
180 	u8 genmask = nft_genmask_next(net);
181 	struct nft_bitmap_elem *be = _be;
182 	u32 idx, off;
183 
184 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
185 	/* Enter 10 state, similar to deactivation. */
186 	priv->bitmap[idx] &= ~(genmask << off);
187 	nft_set_elem_change_active(net, set, &be->ext);
188 
189 	return true;
190 }
191 
192 static void *nft_bitmap_deactivate(const struct net *net,
193 				   const struct nft_set *set,
194 				   const struct nft_set_elem *elem)
195 {
196 	struct nft_bitmap *priv = nft_set_priv(set);
197 	struct nft_bitmap_elem *this = elem->priv, *be;
198 	u8 genmask = nft_genmask_next(net);
199 	u32 idx, off;
200 
201 	nft_bitmap_location(set, elem->key.val.data, &idx, &off);
202 
203 	be = nft_bitmap_elem_find(set, this, genmask);
204 	if (!be)
205 		return NULL;
206 
207 	/* Enter 10 state. */
208 	priv->bitmap[idx] &= ~(genmask << off);
209 	nft_set_elem_change_active(net, set, &be->ext);
210 
211 	return be;
212 }
213 
214 static void nft_bitmap_walk(const struct nft_ctx *ctx,
215 			    struct nft_set *set,
216 			    struct nft_set_iter *iter)
217 {
218 	const struct nft_bitmap *priv = nft_set_priv(set);
219 	struct nft_bitmap_elem *be;
220 	struct nft_set_elem elem;
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 		elem.priv = be;
229 
230 		iter->err = iter->fn(ctx, set, iter, &elem);
231 
232 		if (iter->err < 0)
233 			return;
234 cont:
235 		iter->count++;
236 	}
237 }
238 
239 /* The bitmap size is pow(2, key length in bits) / bits per byte. This is
240  * multiplied by two since each element takes two bits. For 8 bit keys, the
241  * bitmap consumes 66 bytes. For 16 bit keys, 16388 bytes.
242  */
243 static inline u32 nft_bitmap_size(u32 klen)
244 {
245 	return ((2 << ((klen * BITS_PER_BYTE) - 1)) / BITS_PER_BYTE) << 1;
246 }
247 
248 static inline u64 nft_bitmap_total_size(u32 klen)
249 {
250 	return sizeof(struct nft_bitmap) + nft_bitmap_size(klen);
251 }
252 
253 static u64 nft_bitmap_privsize(const struct nlattr * const nla[],
254 			       const struct nft_set_desc *desc)
255 {
256 	u32 klen = ntohl(nla_get_be32(nla[NFTA_SET_KEY_LEN]));
257 
258 	return nft_bitmap_total_size(klen);
259 }
260 
261 static int nft_bitmap_init(const struct nft_set *set,
262 			 const struct nft_set_desc *desc,
263 			 const struct nlattr * const nla[])
264 {
265 	struct nft_bitmap *priv = nft_set_priv(set);
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_set *set)
274 {
275 	struct nft_bitmap *priv = nft_set_priv(set);
276 	struct nft_bitmap_elem *be, *n;
277 
278 	list_for_each_entry_safe(be, n, &priv->list, head)
279 		nft_set_elem_destroy(set, be, true);
280 }
281 
282 static bool nft_bitmap_estimate(const struct nft_set_desc *desc, u32 features,
283 				struct nft_set_estimate *est)
284 {
285 	/* Make sure bitmaps we don't get bitmaps larger than 16 Kbytes. */
286 	if (desc->klen > 2)
287 		return false;
288 
289 	est->size   = nft_bitmap_total_size(desc->klen);
290 	est->lookup = NFT_SET_CLASS_O_1;
291 	est->space  = NFT_SET_CLASS_O_1;
292 
293 	return true;
294 }
295 
296 struct nft_set_type nft_set_bitmap_type __read_mostly = {
297 	.owner		= THIS_MODULE,
298 	.ops		= {
299 		.privsize	= nft_bitmap_privsize,
300 		.elemsize	= offsetof(struct nft_bitmap_elem, ext),
301 		.estimate	= nft_bitmap_estimate,
302 		.init		= nft_bitmap_init,
303 		.destroy	= nft_bitmap_destroy,
304 		.insert		= nft_bitmap_insert,
305 		.remove		= nft_bitmap_remove,
306 		.deactivate	= nft_bitmap_deactivate,
307 		.flush		= nft_bitmap_flush,
308 		.activate	= nft_bitmap_activate,
309 		.lookup		= nft_bitmap_lookup,
310 		.walk		= nft_bitmap_walk,
311 		.get		= nft_bitmap_get,
312 	},
313 };
314