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: &idx, off: &off); |
86 | |
87 | return nft_bitmap_active(bitmap: 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(p: nft_set_ext_key(ext: &be->ext), |
99 | q: nft_set_ext_key(ext: &this->ext), size: set->klen) || |
100 | !nft_set_elem_active(ext: &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(p: nft_set_ext_key(ext: &be->ext), q: elem->key.val.data, size: set->klen) || |
118 | !nft_set_elem_active(ext: &be->ext, genmask)) |
119 | continue; |
120 | |
121 | return &be->priv; |
122 | } |
123 | return ERR_PTR(error: -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(priv: 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, this: new, genmask); |
136 | if (be) { |
137 | *elem_priv = &be->priv; |
138 | return -EEXIST; |
139 | } |
140 | |
141 | nft_bitmap_location(set, key: nft_set_ext_key(ext: &new->ext), idx: &idx, off: &off); |
142 | /* Enter 01 state. */ |
143 | priv->bitmap[idx] |= (genmask << off); |
144 | list_add_tail_rcu(new: &new->head, 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(priv: 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, key: nft_set_ext_key(ext: &be->ext), idx: &idx, off: &off); |
158 | /* Enter 00 state. */ |
159 | priv->bitmap[idx] &= ~(genmask << off); |
160 | list_del_rcu(entry: &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(priv: 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, key: nft_set_ext_key(ext: &be->ext), idx: &idx, off: &off); |
173 | /* Enter 11 state. */ |
174 | priv->bitmap[idx] |= (genmask << off); |
175 | nft_set_elem_change_active(net, set, ext: &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(priv: 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, key: nft_set_ext_key(ext: &be->ext), idx: &idx, off: &off); |
188 | /* Enter 10 state, similar to deactivation. */ |
189 | priv->bitmap[idx] &= ~(genmask << off); |
190 | nft_set_elem_change_active(net, set, ext: &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(priv: 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, key: elem->key.val.data, idx: &idx, off: &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, ext: &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(ext: &be->ext, genmask: 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(list: &priv->list); |
268 | priv->bitmap_size = nft_bitmap_size(klen: 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, elem_priv: &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(klen: 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 | |