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 net *net,
92 		     const struct nft_set *set, struct nft_bitmap_elem *this,
93 		     u8 genmask)
94 {
95 	const struct nft_bitmap *priv = nft_set_priv(set);
96 	struct nft_bitmap_elem *be;
97 
98 	list_for_each_entry_rcu(be, &priv->list, head,
99 				lockdep_is_held(&nft_pernet(net)->commit_mutex)) {
100 		if (memcmp(nft_set_ext_key(&be->ext),
101 			   nft_set_ext_key(&this->ext), set->klen) ||
102 		    !nft_set_elem_active(&be->ext, genmask))
103 			continue;
104 
105 		return be;
106 	}
107 	return NULL;
108 }
109 
110 static struct nft_elem_priv *
111 nft_bitmap_get(const struct net *net, const struct nft_set *set,
112 	       const struct nft_set_elem *elem, unsigned int flags)
113 {
114 	const struct nft_bitmap *priv = nft_set_priv(set);
115 	u8 genmask = nft_genmask_cur(net);
116 	struct nft_bitmap_elem *be;
117 
118 	list_for_each_entry_rcu(be, &priv->list, head) {
119 		if (memcmp(nft_set_ext_key(&be->ext), elem->key.val.data, set->klen) ||
120 		    !nft_set_elem_active(&be->ext, genmask))
121 			continue;
122 
123 		return &be->priv;
124 	}
125 	return ERR_PTR(-ENOENT);
126 }
127 
128 static int nft_bitmap_insert(const struct net *net, const struct nft_set *set,
129 			     const struct nft_set_elem *elem,
130 			     struct nft_elem_priv **elem_priv)
131 {
132 	struct nft_bitmap_elem *new = nft_elem_priv_cast(elem->priv), *be;
133 	struct nft_bitmap *priv = nft_set_priv(set);
134 	u8 genmask = nft_genmask_next(net);
135 	u32 idx, off;
136 
137 	be = nft_bitmap_elem_find(net, set, new, genmask);
138 	if (be) {
139 		*elem_priv = &be->priv;
140 		return -EEXIST;
141 	}
142 
143 	nft_bitmap_location(set, nft_set_ext_key(&new->ext), &idx, &off);
144 	/* Enter 01 state. */
145 	priv->bitmap[idx] |= (genmask << off);
146 	list_add_tail_rcu(&new->head, &priv->list);
147 
148 	return 0;
149 }
150 
151 static void nft_bitmap_remove(const struct net *net, const struct nft_set *set,
152 			      struct nft_elem_priv *elem_priv)
153 {
154 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
155 	struct nft_bitmap *priv = nft_set_priv(set);
156 	u8 genmask = nft_genmask_next(net);
157 	u32 idx, off;
158 
159 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
160 	/* Enter 00 state. */
161 	priv->bitmap[idx] &= ~(genmask << off);
162 	list_del_rcu(&be->head);
163 }
164 
165 static void nft_bitmap_activate(const struct net *net,
166 				const struct nft_set *set,
167 				struct nft_elem_priv *elem_priv)
168 {
169 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
170 	struct nft_bitmap *priv = nft_set_priv(set);
171 	u8 genmask = nft_genmask_next(net);
172 	u32 idx, off;
173 
174 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
175 	/* Enter 11 state. */
176 	priv->bitmap[idx] |= (genmask << off);
177 	nft_clear(net, &be->ext);
178 }
179 
180 static void nft_bitmap_flush(const struct net *net,
181 			     const struct nft_set *set,
182 			     struct nft_elem_priv *elem_priv)
183 {
184 	struct nft_bitmap_elem *be = nft_elem_priv_cast(elem_priv);
185 	struct nft_bitmap *priv = nft_set_priv(set);
186 	u8 genmask = nft_genmask_next(net);
187 	u32 idx, off;
188 
189 	nft_bitmap_location(set, nft_set_ext_key(&be->ext), &idx, &off);
190 	/* Enter 10 state, similar to deactivation. */
191 	priv->bitmap[idx] &= ~(genmask << off);
192 	nft_set_elem_change_active(net, set, &be->ext);
193 }
194 
195 static struct nft_elem_priv *
196 nft_bitmap_deactivate(const struct net *net, const struct nft_set *set,
197 		      const struct nft_set_elem *elem)
198 {
199 	struct nft_bitmap_elem *this = nft_elem_priv_cast(elem->priv), *be;
200 	struct nft_bitmap *priv = nft_set_priv(set);
201 	u8 genmask = nft_genmask_next(net);
202 	u32 idx, off;
203 
204 	nft_bitmap_location(set, elem->key.val.data, &idx, &off);
205 
206 	be = nft_bitmap_elem_find(net, set, this, genmask);
207 	if (!be)
208 		return NULL;
209 
210 	/* Enter 10 state. */
211 	priv->bitmap[idx] &= ~(genmask << off);
212 	nft_set_elem_change_active(net, set, &be->ext);
213 
214 	return &be->priv;
215 }
216 
217 static void nft_bitmap_walk(const struct nft_ctx *ctx,
218 			    struct nft_set *set,
219 			    struct nft_set_iter *iter)
220 {
221 	const struct nft_bitmap *priv = nft_set_priv(set);
222 	struct nft_bitmap_elem *be;
223 
224 	list_for_each_entry_rcu(be, &priv->list, head) {
225 		if (iter->count < iter->skip)
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