1 // SPDX-License-Identifier: GPL-2.0-only
2
3 /* PIPAPO: PIle PAcket POlicies: set for arbitrary concatenations of ranges
4 *
5 * Copyright (c) 2019-2020 Red Hat GmbH
6 *
7 * Author: Stefano Brivio <sbrivio@redhat.com>
8 */
9
10 /**
11 * DOC: Theory of Operation
12 *
13 *
14 * Problem
15 * -------
16 *
17 * Match packet bytes against entries composed of ranged or non-ranged packet
18 * field specifiers, mapping them to arbitrary references. For example:
19 *
20 * ::
21 *
22 * --- fields --->
23 * | [net],[port],[net]... => [reference]
24 * entries [net],[port],[net]... => [reference]
25 * | [net],[port],[net]... => [reference]
26 * V ...
27 *
28 * where [net] fields can be IP ranges or netmasks, and [port] fields are port
29 * ranges. Arbitrary packet fields can be matched.
30 *
31 *
32 * Algorithm Overview
33 * ------------------
34 *
35 * This algorithm is loosely inspired by [Ligatti 2010], and fundamentally
36 * relies on the consideration that every contiguous range in a space of b bits
37 * can be converted into b * 2 netmasks, from Theorem 3 in [Rottenstreich 2010],
38 * as also illustrated in Section 9 of [Kogan 2014].
39 *
40 * Classification against a number of entries, that require matching given bits
41 * of a packet field, is performed by grouping those bits in sets of arbitrary
42 * size, and classifying packet bits one group at a time.
43 *
44 * Example:
45 * to match the source port (16 bits) of a packet, we can divide those 16 bits
46 * in 4 groups of 4 bits each. Given the entry:
47 * 0000 0001 0101 1001
48 * and a packet with source port:
49 * 0000 0001 1010 1001
50 * first and second groups match, but the third doesn't. We conclude that the
51 * packet doesn't match the given entry.
52 *
53 * Translate the set to a sequence of lookup tables, one per field. Each table
54 * has two dimensions: bit groups to be matched for a single packet field, and
55 * all the possible values of said groups (buckets). Input entries are
56 * represented as one or more rules, depending on the number of composing
57 * netmasks for the given field specifier, and a group match is indicated as a
58 * set bit, with number corresponding to the rule index, in all the buckets
59 * whose value matches the entry for a given group.
60 *
61 * Rules are mapped between fields through an array of x, n pairs, with each
62 * item mapping a matched rule to one or more rules. The position of the pair in
63 * the array indicates the matched rule to be mapped to the next field, x
64 * indicates the first rule index in the next field, and n the amount of
65 * next-field rules the current rule maps to.
66 *
67 * The mapping array for the last field maps to the desired references.
68 *
69 * To match, we perform table lookups using the values of grouped packet bits,
70 * and use a sequence of bitwise operations to progressively evaluate rule
71 * matching.
72 *
73 * A stand-alone, reference implementation, also including notes about possible
74 * future optimisations, is available at:
75 * https://pipapo.lameexcu.se/
76 *
77 * Insertion
78 * ---------
79 *
80 * - For each packet field:
81 *
82 * - divide the b packet bits we want to classify into groups of size t,
83 * obtaining ceil(b / t) groups
84 *
85 * Example: match on destination IP address, with t = 4: 32 bits, 8 groups
86 * of 4 bits each
87 *
88 * - allocate a lookup table with one column ("bucket") for each possible
89 * value of a group, and with one row for each group
90 *
91 * Example: 8 groups, 2^4 buckets:
92 *
93 * ::
94 *
95 * bucket
96 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
97 * 0
98 * 1
99 * 2
100 * 3
101 * 4
102 * 5
103 * 6
104 * 7
105 *
106 * - map the bits we want to classify for the current field, for a given
107 * entry, to a single rule for non-ranged and netmask set items, and to one
108 * or multiple rules for ranges. Ranges are expanded to composing netmasks
109 * by pipapo_expand().
110 *
111 * Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048
112 * - rule #0: 10.0.0.5
113 * - rule #1: 192.168.1.0/24
114 * - rule #2: 192.168.2.0/31
115 *
116 * - insert references to the rules in the lookup table, selecting buckets
117 * according to bit values of a rule in the given group. This is done by
118 * pipapo_insert().
119 *
120 * Example: given:
121 * - rule #0: 10.0.0.5 mapping to buckets
122 * < 0 10 0 0 0 0 0 5 >
123 * - rule #1: 192.168.1.0/24 mapping to buckets
124 * < 12 0 10 8 0 1 < 0..15 > < 0..15 > >
125 * - rule #2: 192.168.2.0/31 mapping to buckets
126 * < 12 0 10 8 0 2 0 < 0..1 > >
127 *
128 * these bits are set in the lookup table:
129 *
130 * ::
131 *
132 * bucket
133 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
134 * 0 0 1,2
135 * 1 1,2 0
136 * 2 0 1,2
137 * 3 0 1,2
138 * 4 0,1,2
139 * 5 0 1 2
140 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
141 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
142 *
143 * - if this is not the last field in the set, fill a mapping array that maps
144 * rules from the lookup table to rules belonging to the same entry in
145 * the next lookup table, done by pipapo_map().
146 *
147 * Note that as rules map to contiguous ranges of rules, given how netmask
148 * expansion and insertion is performed, &union nft_pipapo_map_bucket stores
149 * this information as pairs of first rule index, rule count.
150 *
151 * Example: 2 entries, 10.0.0.5:1024 and 192.168.1.0-192.168.2.1:2048,
152 * given lookup table #0 for field 0 (see example above):
153 *
154 * ::
155 *
156 * bucket
157 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
158 * 0 0 1,2
159 * 1 1,2 0
160 * 2 0 1,2
161 * 3 0 1,2
162 * 4 0,1,2
163 * 5 0 1 2
164 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
165 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
166 *
167 * and lookup table #1 for field 1 with:
168 * - rule #0: 1024 mapping to buckets
169 * < 0 0 4 0 >
170 * - rule #1: 2048 mapping to buckets
171 * < 0 0 5 0 >
172 *
173 * ::
174 *
175 * bucket
176 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
177 * 0 0,1
178 * 1 0,1
179 * 2 0 1
180 * 3 0,1
181 *
182 * we need to map rules for 10.0.0.5 in lookup table #0 (rule #0) to 1024
183 * in lookup table #1 (rule #0) and rules for 192.168.1.0-192.168.2.1
184 * (rules #1, #2) to 2048 in lookup table #2 (rule #1):
185 *
186 * ::
187 *
188 * rule indices in current field: 0 1 2
189 * map to rules in next field: 0 1 1
190 *
191 * - if this is the last field in the set, fill a mapping array that maps
192 * rules from the last lookup table to element pointers, also done by
193 * pipapo_map().
194 *
195 * Note that, in this implementation, we have two elements (start, end) for
196 * each entry. The pointer to the end element is stored in this array, and
197 * the pointer to the start element is linked from it.
198 *
199 * Example: entry 10.0.0.5:1024 has a corresponding &struct nft_pipapo_elem
200 * pointer, 0x66, and element for 192.168.1.0-192.168.2.1:2048 is at 0x42.
201 * From the rules of lookup table #1 as mapped above:
202 *
203 * ::
204 *
205 * rule indices in last field: 0 1
206 * map to elements: 0x66 0x42
207 *
208 *
209 * Matching
210 * --------
211 *
212 * We use a result bitmap, with the size of a single lookup table bucket, to
213 * represent the matching state that applies at every algorithm step. This is
214 * done by pipapo_lookup().
215 *
216 * - For each packet field:
217 *
218 * - start with an all-ones result bitmap (res_map in pipapo_lookup())
219 *
220 * - perform a lookup into the table corresponding to the current field,
221 * for each group, and at every group, AND the current result bitmap with
222 * the value from the lookup table bucket
223 *
224 * ::
225 *
226 * Example: 192.168.1.5 < 12 0 10 8 0 1 0 5 >, with lookup table from
227 * insertion examples.
228 * Lookup table buckets are at least 3 bits wide, we'll assume 8 bits for
229 * convenience in this example. Initial result bitmap is 0xff, the steps
230 * below show the value of the result bitmap after each group is processed:
231 *
232 * bucket
233 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
234 * 0 0 1,2
235 * result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6
236 *
237 * 1 1,2 0
238 * result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6
239 *
240 * 2 0 1,2
241 * result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6
242 *
243 * 3 0 1,2
244 * result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6
245 *
246 * 4 0,1,2
247 * result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6
248 *
249 * 5 0 1 2
250 * result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2
251 *
252 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
253 * result bitmap is now: 0x2 & 0x7 [bucket 0] = 0x2
254 *
255 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
256 * final result bitmap for this field is: 0x2 & 0x3 [bucket 5] = 0x2
257 *
258 * - at the next field, start with a new, all-zeroes result bitmap. For each
259 * bit set in the previous result bitmap, fill the new result bitmap
260 * (fill_map in pipapo_lookup()) with the rule indices from the
261 * corresponding buckets of the mapping field for this field, done by
262 * pipapo_refill()
263 *
264 * Example: with mapping table from insertion examples, with the current
265 * result bitmap from the previous example, 0x02:
266 *
267 * ::
268 *
269 * rule indices in current field: 0 1 2
270 * map to rules in next field: 0 1 1
271 *
272 * the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
273 * set.
274 *
275 * We can now extend this example to cover the second iteration of the step
276 * above (lookup and AND bitmap): assuming the port field is
277 * 2048 < 0 0 5 0 >, with starting result bitmap 0x2, and lookup table
278 * for "port" field from pre-computation example:
279 *
280 * ::
281 *
282 * bucket
283 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
284 * 0 0,1
285 * 1 0,1
286 * 2 0 1
287 * 3 0,1
288 *
289 * operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
290 * & 0x3 [bucket 0], resulting bitmap is 0x2.
291 *
292 * - if this is the last field in the set, look up the value from the mapping
293 * array corresponding to the final result bitmap
294 *
295 * Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
296 * last field from insertion example:
297 *
298 * ::
299 *
300 * rule indices in last field: 0 1
301 * map to elements: 0x66 0x42
302 *
303 * the matching element is at 0x42.
304 *
305 *
306 * References
307 * ----------
308 *
309 * [Ligatti 2010]
310 * A Packet-classification Algorithm for Arbitrary Bitmask Rules, with
311 * Automatic Time-space Tradeoffs
312 * Jay Ligatti, Josh Kuhn, and Chris Gage.
313 * Proceedings of the IEEE International Conference on Computer
314 * Communication Networks (ICCCN), August 2010.
315 * https://www.cse.usf.edu/~ligatti/papers/grouper-conf.pdf
316 *
317 * [Rottenstreich 2010]
318 * Worst-Case TCAM Rule Expansion
319 * Ori Rottenstreich and Isaac Keslassy.
320 * 2010 Proceedings IEEE INFOCOM, San Diego, CA, 2010.
321 * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.212.4592&rep=rep1&type=pdf
322 *
323 * [Kogan 2014]
324 * SAX-PAC (Scalable And eXpressive PAcket Classification)
325 * Kirill Kogan, Sergey Nikolenko, Ori Rottenstreich, William Culhane,
326 * and Patrick Eugster.
327 * Proceedings of the 2014 ACM conference on SIGCOMM, August 2014.
328 * https://www.sigcomm.org/sites/default/files/ccr/papers/2014/August/2619239-2626294.pdf
329 */
330
331 #include <linux/kernel.h>
332 #include <linux/init.h>
333 #include <linux/module.h>
334 #include <linux/netlink.h>
335 #include <linux/netfilter.h>
336 #include <linux/netfilter/nf_tables.h>
337 #include <net/netfilter/nf_tables_core.h>
338 #include <uapi/linux/netfilter/nf_tables.h>
339 #include <linux/bitmap.h>
340 #include <linux/bitops.h>
341
342 #include "nft_set_pipapo_avx2.h"
343 #include "nft_set_pipapo.h"
344
345 /**
346 * pipapo_refill() - For each set bit, set bits from selected mapping table item
347 * @map: Bitmap to be scanned for set bits
348 * @len: Length of bitmap in longs
349 * @rules: Number of rules in field
350 * @dst: Destination bitmap
351 * @mt: Mapping table containing bit set specifiers
352 * @match_only: Find a single bit and return, don't fill
353 *
354 * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
355 *
356 * For each bit set in map, select the bucket from mapping table with index
357 * corresponding to the position of the bit set. Use start bit and amount of
358 * bits specified in bucket to fill region in dst.
359 *
360 * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
361 */
pipapo_refill(unsigned long * map,int len,int rules,unsigned long * dst,union nft_pipapo_map_bucket * mt,bool match_only)362 int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
363 union nft_pipapo_map_bucket *mt, bool match_only)
364 {
365 unsigned long bitset;
366 int k, ret = -1;
367
368 for (k = 0; k < len; k++) {
369 bitset = map[k];
370 while (bitset) {
371 unsigned long t = bitset & -bitset;
372 int r = __builtin_ctzl(bitset);
373 int i = k * BITS_PER_LONG + r;
374
375 if (unlikely(i >= rules)) {
376 map[k] = 0;
377 return -1;
378 }
379
380 if (match_only) {
381 bitmap_clear(map, i, 1);
382 return i;
383 }
384
385 ret = 0;
386
387 bitmap_set(dst, mt[i].to, mt[i].n);
388
389 bitset ^= t;
390 }
391 map[k] = 0;
392 }
393
394 return ret;
395 }
396
397 /**
398 * nft_pipapo_lookup() - Lookup function
399 * @net: Network namespace
400 * @set: nftables API set representation
401 * @key: nftables API element representation containing key data
402 * @ext: nftables API extension pointer, filled with matching reference
403 *
404 * For more details, see DOC: Theory of Operation.
405 *
406 * Return: true on match, false otherwise.
407 */
nft_pipapo_lookup(const struct net * net,const struct nft_set * set,const u32 * key,const struct nft_set_ext ** ext)408 bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
409 const u32 *key, const struct nft_set_ext **ext)
410 {
411 struct nft_pipapo *priv = nft_set_priv(set);
412 struct nft_pipapo_scratch *scratch;
413 unsigned long *res_map, *fill_map;
414 u8 genmask = nft_genmask_cur(net);
415 const u8 *rp = (const u8 *)key;
416 struct nft_pipapo_match *m;
417 struct nft_pipapo_field *f;
418 bool map_index;
419 int i;
420
421 local_bh_disable();
422
423 m = rcu_dereference(priv->match);
424
425 if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
426 goto out;
427
428 scratch = *raw_cpu_ptr(m->scratch);
429
430 map_index = scratch->map_index;
431
432 res_map = scratch->map + (map_index ? m->bsize_max : 0);
433 fill_map = scratch->map + (map_index ? 0 : m->bsize_max);
434
435 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
436
437 nft_pipapo_for_each_field(f, i, m) {
438 bool last = i == m->field_count - 1;
439 int b;
440
441 /* For each bit group: select lookup table bucket depending on
442 * packet bytes value, then AND bucket value
443 */
444 if (likely(f->bb == 8))
445 pipapo_and_field_buckets_8bit(f, res_map, rp);
446 else
447 pipapo_and_field_buckets_4bit(f, res_map, rp);
448 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
449
450 rp += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f);
451
452 /* Now populate the bitmap for the next field, unless this is
453 * the last field, in which case return the matched 'ext'
454 * pointer if any.
455 *
456 * Now res_map contains the matching bitmap, and fill_map is the
457 * bitmap for the next field.
458 */
459 next_match:
460 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
461 last);
462 if (b < 0) {
463 scratch->map_index = map_index;
464 local_bh_enable();
465
466 return false;
467 }
468
469 if (last) {
470 *ext = &f->mt[b].e->ext;
471 if (unlikely(nft_set_elem_expired(*ext) ||
472 !nft_set_elem_active(*ext, genmask)))
473 goto next_match;
474
475 /* Last field: we're just returning the key without
476 * filling the initial bitmap for the next field, so the
477 * current inactive bitmap is clean and can be reused as
478 * *next* bitmap (not initial) for the next packet.
479 */
480 scratch->map_index = map_index;
481 local_bh_enable();
482
483 return true;
484 }
485
486 /* Swap bitmap indices: res_map is the initial bitmap for the
487 * next field, and fill_map is guaranteed to be all-zeroes at
488 * this point.
489 */
490 map_index = !map_index;
491 swap(res_map, fill_map);
492
493 rp += NFT_PIPAPO_GROUPS_PADDING(f);
494 }
495
496 out:
497 local_bh_enable();
498 return false;
499 }
500
501 /**
502 * pipapo_get() - Get matching element reference given key data
503 * @net: Network namespace
504 * @set: nftables API set representation
505 * @data: Key data to be matched against existing elements
506 * @genmask: If set, check that element is active in given genmask
507 *
508 * This is essentially the same as the lookup function, except that it matches
509 * key data against the uncommitted copy and doesn't use preallocated maps for
510 * bitmap results.
511 *
512 * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
513 */
pipapo_get(const struct net * net,const struct nft_set * set,const u8 * data,u8 genmask)514 static struct nft_pipapo_elem *pipapo_get(const struct net *net,
515 const struct nft_set *set,
516 const u8 *data, u8 genmask)
517 {
518 struct nft_pipapo_elem *ret = ERR_PTR(-ENOENT);
519 struct nft_pipapo *priv = nft_set_priv(set);
520 struct nft_pipapo_match *m = priv->clone;
521 unsigned long *res_map, *fill_map = NULL;
522 struct nft_pipapo_field *f;
523 int i;
524
525 res_map = kmalloc_array(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
526 if (!res_map) {
527 ret = ERR_PTR(-ENOMEM);
528 goto out;
529 }
530
531 fill_map = kcalloc(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
532 if (!fill_map) {
533 ret = ERR_PTR(-ENOMEM);
534 goto out;
535 }
536
537 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
538
539 nft_pipapo_for_each_field(f, i, m) {
540 bool last = i == m->field_count - 1;
541 int b;
542
543 /* For each bit group: select lookup table bucket depending on
544 * packet bytes value, then AND bucket value
545 */
546 if (f->bb == 8)
547 pipapo_and_field_buckets_8bit(f, res_map, data);
548 else if (f->bb == 4)
549 pipapo_and_field_buckets_4bit(f, res_map, data);
550 else
551 BUG();
552
553 data += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f);
554
555 /* Now populate the bitmap for the next field, unless this is
556 * the last field, in which case return the matched 'ext'
557 * pointer if any.
558 *
559 * Now res_map contains the matching bitmap, and fill_map is the
560 * bitmap for the next field.
561 */
562 next_match:
563 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
564 last);
565 if (b < 0)
566 goto out;
567
568 if (last) {
569 if (nft_set_elem_expired(&f->mt[b].e->ext))
570 goto next_match;
571 if ((genmask &&
572 !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
573 goto next_match;
574
575 ret = f->mt[b].e;
576 goto out;
577 }
578
579 data += NFT_PIPAPO_GROUPS_PADDING(f);
580
581 /* Swap bitmap indices: fill_map will be the initial bitmap for
582 * the next field (i.e. the new res_map), and res_map is
583 * guaranteed to be all-zeroes at this point, ready to be filled
584 * according to the next mapping table.
585 */
586 swap(res_map, fill_map);
587 }
588
589 out:
590 kfree(fill_map);
591 kfree(res_map);
592 return ret;
593 }
594
595 /**
596 * nft_pipapo_get() - Get matching element reference given key data
597 * @net: Network namespace
598 * @set: nftables API set representation
599 * @elem: nftables API element representation containing key data
600 * @flags: Unused
601 */
nft_pipapo_get(const struct net * net,const struct nft_set * set,const struct nft_set_elem * elem,unsigned int flags)602 static void *nft_pipapo_get(const struct net *net, const struct nft_set *set,
603 const struct nft_set_elem *elem, unsigned int flags)
604 {
605 return pipapo_get(net, set, (const u8 *)elem->key.val.data,
606 nft_genmask_cur(net));
607 }
608
609 /**
610 * pipapo_resize() - Resize lookup or mapping table, or both
611 * @f: Field containing lookup and mapping tables
612 * @old_rules: Previous amount of rules in field
613 * @rules: New amount of rules
614 *
615 * Increase, decrease or maintain tables size depending on new amount of rules,
616 * and copy data over. In case the new size is smaller, throw away data for
617 * highest-numbered rules.
618 *
619 * Return: 0 on success, -ENOMEM on allocation failure.
620 */
pipapo_resize(struct nft_pipapo_field * f,int old_rules,int rules)621 static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
622 {
623 long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
624 union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
625 size_t new_bucket_size, copy;
626 int group, bucket;
627
628 new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
629 #ifdef NFT_PIPAPO_ALIGN
630 new_bucket_size = roundup(new_bucket_size,
631 NFT_PIPAPO_ALIGN / sizeof(*new_lt));
632 #endif
633
634 if (new_bucket_size == f->bsize)
635 goto mt;
636
637 if (new_bucket_size > f->bsize)
638 copy = f->bsize;
639 else
640 copy = new_bucket_size;
641
642 new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS(f->bb) *
643 new_bucket_size * sizeof(*new_lt) +
644 NFT_PIPAPO_ALIGN_HEADROOM,
645 GFP_KERNEL);
646 if (!new_lt)
647 return -ENOMEM;
648
649 new_p = NFT_PIPAPO_LT_ALIGN(new_lt);
650 old_p = NFT_PIPAPO_LT_ALIGN(old_lt);
651
652 for (group = 0; group < f->groups; group++) {
653 for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS(f->bb); bucket++) {
654 memcpy(new_p, old_p, copy * sizeof(*new_p));
655 new_p += copy;
656 old_p += copy;
657
658 if (new_bucket_size > f->bsize)
659 new_p += new_bucket_size - f->bsize;
660 else
661 old_p += f->bsize - new_bucket_size;
662 }
663 }
664
665 mt:
666 new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
667 if (!new_mt) {
668 kvfree(new_lt);
669 return -ENOMEM;
670 }
671
672 memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
673 if (rules > old_rules) {
674 memset(new_mt + old_rules, 0,
675 (rules - old_rules) * sizeof(*new_mt));
676 }
677
678 if (new_lt) {
679 f->bsize = new_bucket_size;
680 NFT_PIPAPO_LT_ASSIGN(f, new_lt);
681 kvfree(old_lt);
682 }
683
684 f->mt = new_mt;
685 kvfree(old_mt);
686
687 return 0;
688 }
689
690 /**
691 * pipapo_bucket_set() - Set rule bit in bucket given group and group value
692 * @f: Field containing lookup table
693 * @rule: Rule index
694 * @group: Group index
695 * @v: Value of bit group
696 */
pipapo_bucket_set(struct nft_pipapo_field * f,int rule,int group,int v)697 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
698 int v)
699 {
700 unsigned long *pos;
701
702 pos = NFT_PIPAPO_LT_ALIGN(f->lt);
703 pos += f->bsize * NFT_PIPAPO_BUCKETS(f->bb) * group;
704 pos += f->bsize * v;
705
706 __set_bit(rule, pos);
707 }
708
709 /**
710 * pipapo_lt_4b_to_8b() - Switch lookup table group width from 4 bits to 8 bits
711 * @old_groups: Number of current groups
712 * @bsize: Size of one bucket, in longs
713 * @old_lt: Pointer to the current lookup table
714 * @new_lt: Pointer to the new, pre-allocated lookup table
715 *
716 * Each bucket with index b in the new lookup table, belonging to group g, is
717 * filled with the bit intersection between:
718 * - bucket with index given by the upper 4 bits of b, from group g, and
719 * - bucket with index given by the lower 4 bits of b, from group g + 1
720 *
721 * That is, given buckets from the new lookup table N(x, y) and the old lookup
722 * table O(x, y), with x bucket index, and y group index:
723 *
724 * N(b, g) := O(b / 16, g) & O(b % 16, g + 1)
725 *
726 * This ensures equivalence of the matching results on lookup. Two examples in
727 * pictures:
728 *
729 * bucket
730 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... 254 255
731 * 0 ^
732 * 1 | ^
733 * ... ( & ) |
734 * / \ |
735 * / \ .-( & )-.
736 * / bucket \ | |
737 * group 0 / 1 2 3 \ 4 5 6 7 8 9 10 11 12 13 |14 15 |
738 * 0 / \ | |
739 * 1 \ | |
740 * 2 | --'
741 * 3 '-
742 * ...
743 */
pipapo_lt_4b_to_8b(int old_groups,int bsize,unsigned long * old_lt,unsigned long * new_lt)744 static void pipapo_lt_4b_to_8b(int old_groups, int bsize,
745 unsigned long *old_lt, unsigned long *new_lt)
746 {
747 int g, b, i;
748
749 for (g = 0; g < old_groups / 2; g++) {
750 int src_g0 = g * 2, src_g1 = g * 2 + 1;
751
752 for (b = 0; b < NFT_PIPAPO_BUCKETS(8); b++) {
753 int src_b0 = b / NFT_PIPAPO_BUCKETS(4);
754 int src_b1 = b % NFT_PIPAPO_BUCKETS(4);
755 int src_i0 = src_g0 * NFT_PIPAPO_BUCKETS(4) + src_b0;
756 int src_i1 = src_g1 * NFT_PIPAPO_BUCKETS(4) + src_b1;
757
758 for (i = 0; i < bsize; i++) {
759 *new_lt = old_lt[src_i0 * bsize + i] &
760 old_lt[src_i1 * bsize + i];
761 new_lt++;
762 }
763 }
764 }
765 }
766
767 /**
768 * pipapo_lt_8b_to_4b() - Switch lookup table group width from 8 bits to 4 bits
769 * @old_groups: Number of current groups
770 * @bsize: Size of one bucket, in longs
771 * @old_lt: Pointer to the current lookup table
772 * @new_lt: Pointer to the new, pre-allocated lookup table
773 *
774 * Each bucket with index b in the new lookup table, belonging to group g, is
775 * filled with the bit union of:
776 * - all the buckets with index such that the upper four bits of the lower byte
777 * equal b, from group g, with g odd
778 * - all the buckets with index such that the lower four bits equal b, from
779 * group g, with g even
780 *
781 * That is, given buckets from the new lookup table N(x, y) and the old lookup
782 * table O(x, y), with x bucket index, and y group index:
783 *
784 * - with g odd: N(b, g) := U(O(x, g) for each x : x = (b & 0xf0) >> 4)
785 * - with g even: N(b, g) := U(O(x, g) for each x : x = b & 0x0f)
786 *
787 * where U() denotes the arbitrary union operation (binary OR of n terms). This
788 * ensures equivalence of the matching results on lookup.
789 */
pipapo_lt_8b_to_4b(int old_groups,int bsize,unsigned long * old_lt,unsigned long * new_lt)790 static void pipapo_lt_8b_to_4b(int old_groups, int bsize,
791 unsigned long *old_lt, unsigned long *new_lt)
792 {
793 int g, b, bsrc, i;
794
795 memset(new_lt, 0, old_groups * 2 * NFT_PIPAPO_BUCKETS(4) * bsize *
796 sizeof(unsigned long));
797
798 for (g = 0; g < old_groups * 2; g += 2) {
799 int src_g = g / 2;
800
801 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
802 for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
803 bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
804 bsrc++) {
805 if (((bsrc & 0xf0) >> 4) != b)
806 continue;
807
808 for (i = 0; i < bsize; i++)
809 new_lt[i] |= old_lt[bsrc * bsize + i];
810 }
811
812 new_lt += bsize;
813 }
814
815 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
816 for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
817 bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
818 bsrc++) {
819 if ((bsrc & 0x0f) != b)
820 continue;
821
822 for (i = 0; i < bsize; i++)
823 new_lt[i] |= old_lt[bsrc * bsize + i];
824 }
825
826 new_lt += bsize;
827 }
828 }
829 }
830
831 /**
832 * pipapo_lt_bits_adjust() - Adjust group size for lookup table if needed
833 * @f: Field containing lookup table
834 */
pipapo_lt_bits_adjust(struct nft_pipapo_field * f)835 static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
836 {
837 unsigned long *new_lt;
838 int groups, bb;
839 size_t lt_size;
840
841 lt_size = f->groups * NFT_PIPAPO_BUCKETS(f->bb) * f->bsize *
842 sizeof(*f->lt);
843
844 if (f->bb == NFT_PIPAPO_GROUP_BITS_SMALL_SET &&
845 lt_size > NFT_PIPAPO_LT_SIZE_HIGH) {
846 groups = f->groups * 2;
847 bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
848
849 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
850 sizeof(*f->lt);
851 } else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
852 lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
853 groups = f->groups / 2;
854 bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
855
856 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
857 sizeof(*f->lt);
858
859 /* Don't increase group width if the resulting lookup table size
860 * would exceed the upper size threshold for a "small" set.
861 */
862 if (lt_size > NFT_PIPAPO_LT_SIZE_HIGH)
863 return;
864 } else {
865 return;
866 }
867
868 new_lt = kvzalloc(lt_size + NFT_PIPAPO_ALIGN_HEADROOM, GFP_KERNEL);
869 if (!new_lt)
870 return;
871
872 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
873 if (f->bb == 4 && bb == 8) {
874 pipapo_lt_4b_to_8b(f->groups, f->bsize,
875 NFT_PIPAPO_LT_ALIGN(f->lt),
876 NFT_PIPAPO_LT_ALIGN(new_lt));
877 } else if (f->bb == 8 && bb == 4) {
878 pipapo_lt_8b_to_4b(f->groups, f->bsize,
879 NFT_PIPAPO_LT_ALIGN(f->lt),
880 NFT_PIPAPO_LT_ALIGN(new_lt));
881 } else {
882 BUG();
883 }
884
885 f->groups = groups;
886 f->bb = bb;
887 kvfree(f->lt);
888 NFT_PIPAPO_LT_ASSIGN(f, new_lt);
889 }
890
891 /**
892 * pipapo_insert() - Insert new rule in field given input key and mask length
893 * @f: Field containing lookup table
894 * @k: Input key for classification, without nftables padding
895 * @mask_bits: Length of mask; matches field length for non-ranged entry
896 *
897 * Insert a new rule reference in lookup buckets corresponding to k and
898 * mask_bits.
899 *
900 * Return: 1 on success (one rule inserted), negative error code on failure.
901 */
pipapo_insert(struct nft_pipapo_field * f,const uint8_t * k,int mask_bits)902 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
903 int mask_bits)
904 {
905 int rule = f->rules, group, ret, bit_offset = 0;
906
907 ret = pipapo_resize(f, f->rules, f->rules + 1);
908 if (ret)
909 return ret;
910
911 f->rules++;
912
913 for (group = 0; group < f->groups; group++) {
914 int i, v;
915 u8 mask;
916
917 v = k[group / (BITS_PER_BYTE / f->bb)];
918 v &= GENMASK(BITS_PER_BYTE - bit_offset - 1, 0);
919 v >>= (BITS_PER_BYTE - bit_offset) - f->bb;
920
921 bit_offset += f->bb;
922 bit_offset %= BITS_PER_BYTE;
923
924 if (mask_bits >= (group + 1) * f->bb) {
925 /* Not masked */
926 pipapo_bucket_set(f, rule, group, v);
927 } else if (mask_bits <= group * f->bb) {
928 /* Completely masked */
929 for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++)
930 pipapo_bucket_set(f, rule, group, i);
931 } else {
932 /* The mask limit falls on this group */
933 mask = GENMASK(f->bb - 1, 0);
934 mask >>= mask_bits - group * f->bb;
935 for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++) {
936 if ((i & ~mask) == (v & ~mask))
937 pipapo_bucket_set(f, rule, group, i);
938 }
939 }
940 }
941
942 pipapo_lt_bits_adjust(f);
943
944 return 1;
945 }
946
947 /**
948 * pipapo_step_diff() - Check if setting @step bit in netmask would change it
949 * @base: Mask we are expanding
950 * @step: Step bit for given expansion step
951 * @len: Total length of mask space (set and unset bits), bytes
952 *
953 * Convenience function for mask expansion.
954 *
955 * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
956 */
pipapo_step_diff(u8 * base,int step,int len)957 static bool pipapo_step_diff(u8 *base, int step, int len)
958 {
959 /* Network order, byte-addressed */
960 #ifdef __BIG_ENDIAN__
961 return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
962 #else
963 return !(BIT(step % BITS_PER_BYTE) &
964 base[len - 1 - step / BITS_PER_BYTE]);
965 #endif
966 }
967
968 /**
969 * pipapo_step_after_end() - Check if mask exceeds range end with given step
970 * @base: Mask we are expanding
971 * @end: End of range
972 * @step: Step bit for given expansion step, highest bit to be set
973 * @len: Total length of mask space (set and unset bits), bytes
974 *
975 * Convenience function for mask expansion.
976 *
977 * Return: true if mask exceeds range setting step bits, false otherwise.
978 */
pipapo_step_after_end(const u8 * base,const u8 * end,int step,int len)979 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
980 int len)
981 {
982 u8 tmp[NFT_PIPAPO_MAX_BYTES];
983 int i;
984
985 memcpy(tmp, base, len);
986
987 /* Network order, byte-addressed */
988 for (i = 0; i <= step; i++)
989 #ifdef __BIG_ENDIAN__
990 tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
991 #else
992 tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
993 #endif
994
995 return memcmp(tmp, end, len) > 0;
996 }
997
998 /**
999 * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
1000 * @base: Netmask base
1001 * @step: Step bit to sum
1002 * @len: Netmask length, bytes
1003 */
pipapo_base_sum(u8 * base,int step,int len)1004 static void pipapo_base_sum(u8 *base, int step, int len)
1005 {
1006 bool carry = false;
1007 int i;
1008
1009 /* Network order, byte-addressed */
1010 #ifdef __BIG_ENDIAN__
1011 for (i = step / BITS_PER_BYTE; i < len; i++) {
1012 #else
1013 for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
1014 #endif
1015 if (carry)
1016 base[i]++;
1017 else
1018 base[i] += 1 << (step % BITS_PER_BYTE);
1019
1020 if (base[i])
1021 break;
1022
1023 carry = true;
1024 }
1025 }
1026
1027 /**
1028 * pipapo_expand() - Expand to composing netmasks, insert into lookup table
1029 * @f: Field containing lookup table
1030 * @start: Start of range
1031 * @end: End of range
1032 * @len: Length of value in bits
1033 *
1034 * Expand range to composing netmasks and insert corresponding rule references
1035 * in lookup buckets.
1036 *
1037 * Return: number of inserted rules on success, negative error code on failure.
1038 */
1039 static int pipapo_expand(struct nft_pipapo_field *f,
1040 const u8 *start, const u8 *end, int len)
1041 {
1042 int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
1043 u8 base[NFT_PIPAPO_MAX_BYTES];
1044
1045 memcpy(base, start, bytes);
1046 while (memcmp(base, end, bytes) <= 0) {
1047 int err;
1048
1049 step = 0;
1050 while (pipapo_step_diff(base, step, bytes)) {
1051 if (pipapo_step_after_end(base, end, step, bytes))
1052 break;
1053
1054 step++;
1055 if (step >= len) {
1056 if (!masks) {
1057 err = pipapo_insert(f, base, 0);
1058 if (err < 0)
1059 return err;
1060 masks = 1;
1061 }
1062 goto out;
1063 }
1064 }
1065
1066 err = pipapo_insert(f, base, len - step);
1067
1068 if (err < 0)
1069 return err;
1070
1071 masks++;
1072 pipapo_base_sum(base, step, bytes);
1073 }
1074 out:
1075 return masks;
1076 }
1077
1078 /**
1079 * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1080 * @m: Matching data, including mapping table
1081 * @map: Table of rule maps: array of first rule and amount of rules
1082 * in next field a given rule maps to, for each field
1083 * @e: For last field, nft_set_ext pointer matching rules map to
1084 */
1085 static void pipapo_map(struct nft_pipapo_match *m,
1086 union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1087 struct nft_pipapo_elem *e)
1088 {
1089 struct nft_pipapo_field *f;
1090 int i, j;
1091
1092 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1093 for (j = 0; j < map[i].n; j++) {
1094 f->mt[map[i].to + j].to = map[i + 1].to;
1095 f->mt[map[i].to + j].n = map[i + 1].n;
1096 }
1097 }
1098
1099 /* Last field: map to ext instead of mapping to next field */
1100 for (j = 0; j < map[i].n; j++)
1101 f->mt[map[i].to + j].e = e;
1102 }
1103
1104 /**
1105 * pipapo_free_scratch() - Free per-CPU map at original (not aligned) address
1106 * @m: Matching data
1107 * @cpu: CPU number
1108 */
1109 static void pipapo_free_scratch(const struct nft_pipapo_match *m, unsigned int cpu)
1110 {
1111 struct nft_pipapo_scratch *s;
1112 void *mem;
1113
1114 s = *per_cpu_ptr(m->scratch, cpu);
1115 if (!s)
1116 return;
1117
1118 mem = s;
1119 mem -= s->align_off;
1120 kfree(mem);
1121 }
1122
1123 /**
1124 * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1125 * @clone: Copy of matching data with pending insertions and deletions
1126 * @bsize_max: Maximum bucket size, scratch maps cover two buckets
1127 *
1128 * Return: 0 on success, -ENOMEM on failure.
1129 */
1130 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1131 unsigned long bsize_max)
1132 {
1133 int i;
1134
1135 for_each_possible_cpu(i) {
1136 struct nft_pipapo_scratch *scratch;
1137 #ifdef NFT_PIPAPO_ALIGN
1138 void *scratch_aligned;
1139 u32 align_off;
1140 #endif
1141 scratch = kzalloc_node(struct_size(scratch, map,
1142 bsize_max * 2) +
1143 NFT_PIPAPO_ALIGN_HEADROOM,
1144 GFP_KERNEL, cpu_to_node(i));
1145 if (!scratch) {
1146 /* On failure, there's no need to undo previous
1147 * allocations: this means that some scratch maps have
1148 * a bigger allocated size now (this is only called on
1149 * insertion), but the extra space won't be used by any
1150 * CPU as new elements are not inserted and m->bsize_max
1151 * is not updated.
1152 */
1153 return -ENOMEM;
1154 }
1155
1156 pipapo_free_scratch(clone, i);
1157
1158 #ifdef NFT_PIPAPO_ALIGN
1159 /* Align &scratch->map (not the struct itself): the extra
1160 * %NFT_PIPAPO_ALIGN_HEADROOM bytes passed to kzalloc_node()
1161 * above guarantee we can waste up to those bytes in order
1162 * to align the map field regardless of its offset within
1163 * the struct.
1164 */
1165 BUILD_BUG_ON(offsetof(struct nft_pipapo_scratch, map) > NFT_PIPAPO_ALIGN_HEADROOM);
1166
1167 scratch_aligned = NFT_PIPAPO_LT_ALIGN(&scratch->map);
1168 scratch_aligned -= offsetof(struct nft_pipapo_scratch, map);
1169 align_off = scratch_aligned - (void *)scratch;
1170
1171 scratch = scratch_aligned;
1172 scratch->align_off = align_off;
1173 #endif
1174 *per_cpu_ptr(clone->scratch, i) = scratch;
1175 }
1176
1177 return 0;
1178 }
1179
1180 /**
1181 * nft_pipapo_insert() - Validate and insert ranged elements
1182 * @net: Network namespace
1183 * @set: nftables API set representation
1184 * @elem: nftables API element representation containing key data
1185 * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
1186 *
1187 * Return: 0 on success, error pointer on failure.
1188 */
1189 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1190 const struct nft_set_elem *elem,
1191 struct nft_set_ext **ext2)
1192 {
1193 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1194 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1195 const u8 *start = (const u8 *)elem->key.val.data, *end;
1196 struct nft_pipapo_elem *e = elem->priv, *dup;
1197 struct nft_pipapo *priv = nft_set_priv(set);
1198 struct nft_pipapo_match *m = priv->clone;
1199 u8 genmask = nft_genmask_next(net);
1200 struct nft_pipapo_field *f;
1201 const u8 *start_p, *end_p;
1202 int i, bsize_max, err = 0;
1203
1204 if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END))
1205 end = (const u8 *)nft_set_ext_key_end(ext)->data;
1206 else
1207 end = start;
1208
1209 dup = pipapo_get(net, set, start, genmask);
1210 if (!IS_ERR(dup)) {
1211 /* Check if we already have the same exact entry */
1212 const struct nft_data *dup_key, *dup_end;
1213
1214 dup_key = nft_set_ext_key(&dup->ext);
1215 if (nft_set_ext_exists(&dup->ext, NFT_SET_EXT_KEY_END))
1216 dup_end = nft_set_ext_key_end(&dup->ext);
1217 else
1218 dup_end = dup_key;
1219
1220 if (!memcmp(start, dup_key->data, sizeof(*dup_key->data)) &&
1221 !memcmp(end, dup_end->data, sizeof(*dup_end->data))) {
1222 *ext2 = &dup->ext;
1223 return -EEXIST;
1224 }
1225
1226 return -ENOTEMPTY;
1227 }
1228
1229 if (PTR_ERR(dup) == -ENOENT) {
1230 /* Look for partially overlapping entries */
1231 dup = pipapo_get(net, set, end, nft_genmask_next(net));
1232 }
1233
1234 if (PTR_ERR(dup) != -ENOENT) {
1235 if (IS_ERR(dup))
1236 return PTR_ERR(dup);
1237 *ext2 = &dup->ext;
1238 return -ENOTEMPTY;
1239 }
1240
1241 /* Validate */
1242 start_p = start;
1243 end_p = end;
1244 nft_pipapo_for_each_field(f, i, m) {
1245 if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
1246 return -ENOSPC;
1247
1248 if (memcmp(start_p, end_p,
1249 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) > 0)
1250 return -EINVAL;
1251
1252 start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1253 end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1254 }
1255
1256 /* Insert */
1257 priv->dirty = true;
1258
1259 bsize_max = m->bsize_max;
1260
1261 nft_pipapo_for_each_field(f, i, m) {
1262 int ret;
1263
1264 rulemap[i].to = f->rules;
1265
1266 ret = memcmp(start, end,
1267 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1268 if (!ret)
1269 ret = pipapo_insert(f, start, f->groups * f->bb);
1270 else
1271 ret = pipapo_expand(f, start, end, f->groups * f->bb);
1272
1273 if (ret < 0)
1274 return ret;
1275
1276 if (f->bsize > bsize_max)
1277 bsize_max = f->bsize;
1278
1279 rulemap[i].n = ret;
1280
1281 start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1282 end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1283 }
1284
1285 if (!*get_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1286 put_cpu_ptr(m->scratch);
1287
1288 err = pipapo_realloc_scratch(m, bsize_max);
1289 if (err)
1290 return err;
1291
1292 m->bsize_max = bsize_max;
1293 } else {
1294 put_cpu_ptr(m->scratch);
1295 }
1296
1297 *ext2 = &e->ext;
1298
1299 pipapo_map(m, rulemap, e);
1300
1301 return 0;
1302 }
1303
1304 /**
1305 * pipapo_clone() - Clone matching data to create new working copy
1306 * @old: Existing matching data
1307 *
1308 * Return: copy of matching data passed as 'old', error pointer on failure
1309 */
1310 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1311 {
1312 struct nft_pipapo_field *dst, *src;
1313 struct nft_pipapo_match *new;
1314 int i;
1315
1316 new = kmalloc(struct_size(new, f, old->field_count), GFP_KERNEL);
1317 if (!new)
1318 return ERR_PTR(-ENOMEM);
1319
1320 new->field_count = old->field_count;
1321 new->bsize_max = old->bsize_max;
1322
1323 new->scratch = alloc_percpu(*new->scratch);
1324 if (!new->scratch)
1325 goto out_scratch;
1326
1327 for_each_possible_cpu(i)
1328 *per_cpu_ptr(new->scratch, i) = NULL;
1329
1330 if (pipapo_realloc_scratch(new, old->bsize_max))
1331 goto out_scratch_realloc;
1332
1333 rcu_head_init(&new->rcu);
1334
1335 src = old->f;
1336 dst = new->f;
1337
1338 for (i = 0; i < old->field_count; i++) {
1339 unsigned long *new_lt;
1340
1341 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1342
1343 new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) *
1344 src->bsize * sizeof(*dst->lt) +
1345 NFT_PIPAPO_ALIGN_HEADROOM,
1346 GFP_KERNEL);
1347 if (!new_lt)
1348 goto out_lt;
1349
1350 NFT_PIPAPO_LT_ASSIGN(dst, new_lt);
1351
1352 memcpy(NFT_PIPAPO_LT_ALIGN(new_lt),
1353 NFT_PIPAPO_LT_ALIGN(src->lt),
1354 src->bsize * sizeof(*dst->lt) *
1355 src->groups * NFT_PIPAPO_BUCKETS(src->bb));
1356
1357 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
1358 if (!dst->mt)
1359 goto out_mt;
1360
1361 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1362 src++;
1363 dst++;
1364 }
1365
1366 return new;
1367
1368 out_mt:
1369 kvfree(dst->lt);
1370 out_lt:
1371 for (dst--; i > 0; i--) {
1372 kvfree(dst->mt);
1373 kvfree(dst->lt);
1374 dst--;
1375 }
1376 out_scratch_realloc:
1377 for_each_possible_cpu(i)
1378 pipapo_free_scratch(new, i);
1379 out_scratch:
1380 free_percpu(new->scratch);
1381 kfree(new);
1382
1383 return ERR_PTR(-ENOMEM);
1384 }
1385
1386 /**
1387 * pipapo_rules_same_key() - Get number of rules originated from the same entry
1388 * @f: Field containing mapping table
1389 * @first: Index of first rule in set of rules mapping to same entry
1390 *
1391 * Using the fact that all rules in a field that originated from the same entry
1392 * will map to the same set of rules in the next field, or to the same element
1393 * reference, return the cardinality of the set of rules that originated from
1394 * the same entry as the rule with index @first, @first rule included.
1395 *
1396 * In pictures:
1397 * rules
1398 * field #0 0 1 2 3 4
1399 * map to: 0 1 2-4 2-4 5-9
1400 * . . ....... . ...
1401 * | | | | \ \
1402 * | | | | \ \
1403 * | | | | \ \
1404 * ' ' ' ' ' \
1405 * in field #1 0 1 2 3 4 5 ...
1406 *
1407 * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1408 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1409 *
1410 * For the last field in a set, we can rely on associated entries to map to the
1411 * same element references.
1412 *
1413 * Return: Number of rules that originated from the same entry as @first.
1414 */
1415 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
1416 {
1417 struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1418 int r;
1419
1420 for (r = first; r < f->rules; r++) {
1421 if (r != first && e != f->mt[r].e)
1422 return r - first;
1423
1424 e = f->mt[r].e;
1425 }
1426
1427 if (r != first)
1428 return r - first;
1429
1430 return 0;
1431 }
1432
1433 /**
1434 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1435 * @mt: Mapping array
1436 * @rules: Original amount of rules in mapping table
1437 * @start: First rule index to be removed
1438 * @n: Amount of rules to be removed
1439 * @to_offset: First rule index, in next field, this group of rules maps to
1440 * @is_last: If this is the last field, delete reference from mapping array
1441 *
1442 * This is used to unmap rules from the mapping table for a single field,
1443 * maintaining consistency and compactness for the existing ones.
1444 *
1445 * In pictures: let's assume that we want to delete rules 2 and 3 from the
1446 * following mapping array:
1447 *
1448 * rules
1449 * 0 1 2 3 4
1450 * map to: 4-10 4-10 11-15 11-15 16-18
1451 *
1452 * the result will be:
1453 *
1454 * rules
1455 * 0 1 2
1456 * map to: 4-10 4-10 11-13
1457 *
1458 * for fields before the last one. In case this is the mapping table for the
1459 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1460 *
1461 * rules
1462 * 0 1 2 3 4
1463 * element pointers: 0x42 0x42 0x33 0x33 0x44
1464 *
1465 * the result will be:
1466 *
1467 * rules
1468 * 0 1 2
1469 * element pointers: 0x42 0x42 0x44
1470 */
1471 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
1472 int start, int n, int to_offset, bool is_last)
1473 {
1474 int i;
1475
1476 memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1477 memset(mt + rules - n, 0, n * sizeof(*mt));
1478
1479 if (is_last)
1480 return;
1481
1482 for (i = start; i < rules - n; i++)
1483 mt[i].to -= to_offset;
1484 }
1485
1486 /**
1487 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1488 * @m: Matching data
1489 * @rulemap: Table of rule maps, arrays of first rule and amount of rules
1490 * in next field a given entry maps to, for each field
1491 *
1492 * For each rule in lookup table buckets mapping to this set of rules, drop
1493 * all bits set in lookup table mapping. In pictures, assuming we want to drop
1494 * rules 0 and 1 from this lookup table:
1495 *
1496 * bucket
1497 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1498 * 0 0 1,2
1499 * 1 1,2 0
1500 * 2 0 1,2
1501 * 3 0 1,2
1502 * 4 0,1,2
1503 * 5 0 1 2
1504 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1505 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
1506 *
1507 * rule 2 becomes rule 0, and the result will be:
1508 *
1509 * bucket
1510 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1511 * 0 0
1512 * 1 0
1513 * 2 0
1514 * 3 0
1515 * 4 0
1516 * 5 0
1517 * 6 0
1518 * 7 0 0
1519 *
1520 * once this is done, call unmap() to drop all the corresponding rule references
1521 * from mapping tables.
1522 */
1523 static void pipapo_drop(struct nft_pipapo_match *m,
1524 union nft_pipapo_map_bucket rulemap[])
1525 {
1526 struct nft_pipapo_field *f;
1527 int i;
1528
1529 nft_pipapo_for_each_field(f, i, m) {
1530 int g;
1531
1532 for (g = 0; g < f->groups; g++) {
1533 unsigned long *pos;
1534 int b;
1535
1536 pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g *
1537 NFT_PIPAPO_BUCKETS(f->bb) * f->bsize;
1538
1539 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1540 bitmap_cut(pos, pos, rulemap[i].to,
1541 rulemap[i].n,
1542 f->bsize * BITS_PER_LONG);
1543
1544 pos += f->bsize;
1545 }
1546 }
1547
1548 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1549 rulemap[i + 1].n, i == m->field_count - 1);
1550 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1551 /* We can ignore this, a failure to shrink tables down
1552 * doesn't make tables invalid.
1553 */
1554 ;
1555 }
1556 f->rules -= rulemap[i].n;
1557
1558 pipapo_lt_bits_adjust(f);
1559 }
1560 }
1561
1562 static void nft_pipapo_gc_deactivate(struct net *net, struct nft_set *set,
1563 struct nft_pipapo_elem *e)
1564
1565 {
1566 struct nft_set_elem elem = {
1567 .priv = e,
1568 };
1569
1570 nft_setelem_data_deactivate(net, set, &elem);
1571 }
1572
1573 /**
1574 * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1575 * @_set: nftables API set representation
1576 * @m: Matching data
1577 */
1578 static void pipapo_gc(const struct nft_set *_set, struct nft_pipapo_match *m)
1579 {
1580 struct nft_set *set = (struct nft_set *) _set;
1581 struct nft_pipapo *priv = nft_set_priv(set);
1582 struct net *net = read_pnet(&set->net);
1583 int rules_f0, first_rule = 0;
1584 struct nft_pipapo_elem *e;
1585 struct nft_trans_gc *gc;
1586
1587 gc = nft_trans_gc_alloc(set, 0, GFP_KERNEL);
1588 if (!gc)
1589 return;
1590
1591 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1592 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1593 struct nft_pipapo_field *f;
1594 int i, start, rules_fx;
1595
1596 start = first_rule;
1597 rules_fx = rules_f0;
1598
1599 nft_pipapo_for_each_field(f, i, m) {
1600 rulemap[i].to = start;
1601 rulemap[i].n = rules_fx;
1602
1603 if (i < m->field_count - 1) {
1604 rules_fx = f->mt[start].n;
1605 start = f->mt[start].to;
1606 }
1607 }
1608
1609 /* Pick the last field, and its last index */
1610 f--;
1611 i--;
1612 e = f->mt[rulemap[i].to].e;
1613
1614 /* synchronous gc never fails, there is no need to set on
1615 * NFT_SET_ELEM_DEAD_BIT.
1616 */
1617 if (nft_set_elem_expired(&e->ext)) {
1618 priv->dirty = true;
1619
1620 gc = nft_trans_gc_queue_sync(gc, GFP_ATOMIC);
1621 if (!gc)
1622 return;
1623
1624 nft_pipapo_gc_deactivate(net, set, e);
1625 pipapo_drop(m, rulemap);
1626 nft_trans_gc_elem_add(gc, e);
1627
1628 /* And check again current first rule, which is now the
1629 * first we haven't checked.
1630 */
1631 } else {
1632 first_rule += rules_f0;
1633 }
1634 }
1635
1636 gc = nft_trans_gc_catchall_sync(gc);
1637 if (gc) {
1638 nft_trans_gc_queue_sync_done(gc);
1639 priv->last_gc = jiffies;
1640 }
1641 }
1642
1643 /**
1644 * pipapo_free_fields() - Free per-field tables contained in matching data
1645 * @m: Matching data
1646 */
1647 static void pipapo_free_fields(struct nft_pipapo_match *m)
1648 {
1649 struct nft_pipapo_field *f;
1650 int i;
1651
1652 nft_pipapo_for_each_field(f, i, m) {
1653 kvfree(f->lt);
1654 kvfree(f->mt);
1655 }
1656 }
1657
1658 static void pipapo_free_match(struct nft_pipapo_match *m)
1659 {
1660 int i;
1661
1662 for_each_possible_cpu(i)
1663 pipapo_free_scratch(m, i);
1664
1665 free_percpu(m->scratch);
1666 pipapo_free_fields(m);
1667
1668 kfree(m);
1669 }
1670
1671 /**
1672 * pipapo_reclaim_match - RCU callback to free fields from old matching data
1673 * @rcu: RCU head
1674 */
1675 static void pipapo_reclaim_match(struct rcu_head *rcu)
1676 {
1677 struct nft_pipapo_match *m;
1678
1679 m = container_of(rcu, struct nft_pipapo_match, rcu);
1680 pipapo_free_match(m);
1681 }
1682
1683 /**
1684 * nft_pipapo_commit() - Replace lookup data with current working copy
1685 * @set: nftables API set representation
1686 *
1687 * While at it, check if we should perform garbage collection on the working
1688 * copy before committing it for lookup, and don't replace the table if the
1689 * working copy doesn't have pending changes.
1690 *
1691 * We also need to create a new working copy for subsequent insertions and
1692 * deletions.
1693 */
1694 static void nft_pipapo_commit(const struct nft_set *set)
1695 {
1696 struct nft_pipapo *priv = nft_set_priv(set);
1697 struct nft_pipapo_match *new_clone, *old;
1698
1699 if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1700 pipapo_gc(set, priv->clone);
1701
1702 if (!priv->dirty)
1703 return;
1704
1705 new_clone = pipapo_clone(priv->clone);
1706 if (IS_ERR(new_clone))
1707 return;
1708
1709 priv->dirty = false;
1710
1711 old = rcu_access_pointer(priv->match);
1712 rcu_assign_pointer(priv->match, priv->clone);
1713 if (old)
1714 call_rcu(&old->rcu, pipapo_reclaim_match);
1715
1716 priv->clone = new_clone;
1717 }
1718
1719 static bool nft_pipapo_transaction_mutex_held(const struct nft_set *set)
1720 {
1721 #ifdef CONFIG_PROVE_LOCKING
1722 const struct net *net = read_pnet(&set->net);
1723
1724 return lockdep_is_held(&nft_pernet(net)->commit_mutex);
1725 #else
1726 return true;
1727 #endif
1728 }
1729
1730 static void nft_pipapo_abort(const struct nft_set *set)
1731 {
1732 struct nft_pipapo *priv = nft_set_priv(set);
1733 struct nft_pipapo_match *new_clone, *m;
1734
1735 if (!priv->dirty)
1736 return;
1737
1738 m = rcu_dereference_protected(priv->match, nft_pipapo_transaction_mutex_held(set));
1739
1740 new_clone = pipapo_clone(m);
1741 if (IS_ERR(new_clone))
1742 return;
1743
1744 priv->dirty = false;
1745
1746 pipapo_free_match(priv->clone);
1747 priv->clone = new_clone;
1748 }
1749
1750 /**
1751 * nft_pipapo_activate() - Mark element reference as active given key, commit
1752 * @net: Network namespace
1753 * @set: nftables API set representation
1754 * @elem: nftables API element representation containing key data
1755 *
1756 * On insertion, elements are added to a copy of the matching data currently
1757 * in use for lookups, and not directly inserted into current lookup data. Both
1758 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1759 * element, hence we can't purpose either one as a real commit operation.
1760 */
1761 static void nft_pipapo_activate(const struct net *net,
1762 const struct nft_set *set,
1763 const struct nft_set_elem *elem)
1764 {
1765 struct nft_pipapo_elem *e = elem->priv;
1766
1767 nft_set_elem_change_active(net, set, &e->ext);
1768 }
1769
1770 /**
1771 * pipapo_deactivate() - Check that element is in set, mark as inactive
1772 * @net: Network namespace
1773 * @set: nftables API set representation
1774 * @data: Input key data
1775 * @ext: nftables API extension pointer, used to check for end element
1776 *
1777 * This is a convenience function that can be called from both
1778 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1779 * operation.
1780 *
1781 * Return: deactivated element if found, NULL otherwise.
1782 */
1783 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
1784 const u8 *data, const struct nft_set_ext *ext)
1785 {
1786 struct nft_pipapo_elem *e;
1787
1788 e = pipapo_get(net, set, data, nft_genmask_next(net));
1789 if (IS_ERR(e))
1790 return NULL;
1791
1792 nft_set_elem_change_active(net, set, &e->ext);
1793
1794 return e;
1795 }
1796
1797 /**
1798 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1799 * @net: Network namespace
1800 * @set: nftables API set representation
1801 * @elem: nftables API element representation containing key data
1802 *
1803 * Return: deactivated element if found, NULL otherwise.
1804 */
1805 static void *nft_pipapo_deactivate(const struct net *net,
1806 const struct nft_set *set,
1807 const struct nft_set_elem *elem)
1808 {
1809 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1810
1811 return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
1812 }
1813
1814 /**
1815 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1816 * @net: Network namespace
1817 * @set: nftables API set representation
1818 * @elem: nftables API element representation containing key data
1819 *
1820 * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1821 * different interface, and it's also called once for each element in a set
1822 * being flushed, so we can't implement, strictly speaking, a flush operation,
1823 * which would otherwise be as simple as allocating an empty copy of the
1824 * matching data.
1825 *
1826 * Note that we could in theory do that, mark the set as flushed, and ignore
1827 * subsequent calls, but we would leak all the elements after the first one,
1828 * because they wouldn't then be freed as result of API calls.
1829 *
1830 * Return: true if element was found and deactivated.
1831 */
1832 static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1833 void *elem)
1834 {
1835 struct nft_pipapo_elem *e = elem;
1836
1837 return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext),
1838 &e->ext);
1839 }
1840
1841 /**
1842 * pipapo_get_boundaries() - Get byte interval for associated rules
1843 * @f: Field including lookup table
1844 * @first_rule: First rule (lowest index)
1845 * @rule_count: Number of associated rules
1846 * @left: Byte expression for left boundary (start of range)
1847 * @right: Byte expression for right boundary (end of range)
1848 *
1849 * Given the first rule and amount of rules that originated from the same entry,
1850 * build the original range associated with the entry, and calculate the length
1851 * of the originating netmask.
1852 *
1853 * In pictures:
1854 *
1855 * bucket
1856 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1857 * 0 1,2
1858 * 1 1,2
1859 * 2 1,2
1860 * 3 1,2
1861 * 4 1,2
1862 * 5 1 2
1863 * 6 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1864 * 7 1,2 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1865 *
1866 * this is the lookup table corresponding to the IPv4 range
1867 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1868 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1869 *
1870 * This function fills @left and @right with the byte values of the leftmost
1871 * and rightmost bucket indices for the lowest and highest rule indices,
1872 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1873 * nibbles:
1874 * left: < 12, 0, 10, 8, 0, 1, 0, 0 >
1875 * right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1876 * corresponding to bytes:
1877 * left: < 192, 168, 1, 0 >
1878 * right: < 192, 168, 2, 1 >
1879 * with mask length irrelevant here, unused on return, as the range is already
1880 * defined by its start and end points. The mask length is relevant for a single
1881 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1882 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1883 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1884 * between leftmost and rightmost bucket indices for each group, would be 24.
1885 *
1886 * Return: mask length, in bits.
1887 */
1888 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1889 int rule_count, u8 *left, u8 *right)
1890 {
1891 int g, mask_len = 0, bit_offset = 0;
1892 u8 *l = left, *r = right;
1893
1894 for (g = 0; g < f->groups; g++) {
1895 int b, x0, x1;
1896
1897 x0 = -1;
1898 x1 = -1;
1899 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1900 unsigned long *pos;
1901
1902 pos = NFT_PIPAPO_LT_ALIGN(f->lt) +
1903 (g * NFT_PIPAPO_BUCKETS(f->bb) + b) * f->bsize;
1904 if (test_bit(first_rule, pos) && x0 == -1)
1905 x0 = b;
1906 if (test_bit(first_rule + rule_count - 1, pos))
1907 x1 = b;
1908 }
1909
1910 *l |= x0 << (BITS_PER_BYTE - f->bb - bit_offset);
1911 *r |= x1 << (BITS_PER_BYTE - f->bb - bit_offset);
1912
1913 bit_offset += f->bb;
1914 if (bit_offset >= BITS_PER_BYTE) {
1915 bit_offset %= BITS_PER_BYTE;
1916 l++;
1917 r++;
1918 }
1919
1920 if (x1 - x0 == 0)
1921 mask_len += 4;
1922 else if (x1 - x0 == 1)
1923 mask_len += 3;
1924 else if (x1 - x0 == 3)
1925 mask_len += 2;
1926 else if (x1 - x0 == 7)
1927 mask_len += 1;
1928 }
1929
1930 return mask_len;
1931 }
1932
1933 /**
1934 * pipapo_match_field() - Match rules against byte ranges
1935 * @f: Field including the lookup table
1936 * @first_rule: First of associated rules originating from same entry
1937 * @rule_count: Amount of associated rules
1938 * @start: Start of range to be matched
1939 * @end: End of range to be matched
1940 *
1941 * Return: true on match, false otherwise.
1942 */
1943 static bool pipapo_match_field(struct nft_pipapo_field *f,
1944 int first_rule, int rule_count,
1945 const u8 *start, const u8 *end)
1946 {
1947 u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
1948 u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
1949
1950 pipapo_get_boundaries(f, first_rule, rule_count, left, right);
1951
1952 return !memcmp(start, left,
1953 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) &&
1954 !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1955 }
1956
1957 /**
1958 * nft_pipapo_remove() - Remove element given key, commit
1959 * @net: Network namespace
1960 * @set: nftables API set representation
1961 * @elem: nftables API element representation containing key data
1962 *
1963 * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1964 * API, but it's called once per element in the pending transaction, so we can't
1965 * implement this as a single commit operation. Closest we can get is to remove
1966 * the matched element here, if any, and commit the updated matching data.
1967 */
1968 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
1969 const struct nft_set_elem *elem)
1970 {
1971 struct nft_pipapo *priv = nft_set_priv(set);
1972 struct nft_pipapo_match *m = priv->clone;
1973 struct nft_pipapo_elem *e = elem->priv;
1974 int rules_f0, first_rule = 0;
1975 const u8 *data;
1976
1977 data = (const u8 *)nft_set_ext_key(&e->ext);
1978
1979 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1980 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1981 const u8 *match_start, *match_end;
1982 struct nft_pipapo_field *f;
1983 int i, start, rules_fx;
1984
1985 match_start = data;
1986
1987 if (nft_set_ext_exists(&e->ext, NFT_SET_EXT_KEY_END))
1988 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
1989 else
1990 match_end = data;
1991
1992 start = first_rule;
1993 rules_fx = rules_f0;
1994
1995 nft_pipapo_for_each_field(f, i, m) {
1996 bool last = i == m->field_count - 1;
1997
1998 if (!pipapo_match_field(f, start, rules_fx,
1999 match_start, match_end))
2000 break;
2001
2002 rulemap[i].to = start;
2003 rulemap[i].n = rules_fx;
2004
2005 rules_fx = f->mt[start].n;
2006 start = f->mt[start].to;
2007
2008 match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2009 match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2010
2011 if (last && f->mt[rulemap[i].to].e == e) {
2012 priv->dirty = true;
2013 pipapo_drop(m, rulemap);
2014 return;
2015 }
2016 }
2017
2018 first_rule += rules_f0;
2019 }
2020
2021 WARN_ON_ONCE(1); /* elem_priv not found */
2022 }
2023
2024 /**
2025 * nft_pipapo_walk() - Walk over elements
2026 * @ctx: nftables API context
2027 * @set: nftables API set representation
2028 * @iter: Iterator
2029 *
2030 * As elements are referenced in the mapping array for the last field, directly
2031 * scan that array: there's no need to follow rule mappings from the first
2032 * field.
2033 */
2034 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
2035 struct nft_set_iter *iter)
2036 {
2037 struct nft_pipapo *priv = nft_set_priv(set);
2038 struct net *net = read_pnet(&set->net);
2039 struct nft_pipapo_match *m;
2040 struct nft_pipapo_field *f;
2041 int i, r;
2042
2043 rcu_read_lock();
2044 if (iter->genmask == nft_genmask_cur(net))
2045 m = rcu_dereference(priv->match);
2046 else
2047 m = priv->clone;
2048
2049 if (unlikely(!m))
2050 goto out;
2051
2052 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2053 ;
2054
2055 for (r = 0; r < f->rules; r++) {
2056 struct nft_pipapo_elem *e;
2057 struct nft_set_elem elem;
2058
2059 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2060 continue;
2061
2062 if (iter->count < iter->skip)
2063 goto cont;
2064
2065 e = f->mt[r].e;
2066
2067 if (!nft_set_elem_active(&e->ext, iter->genmask))
2068 goto cont;
2069
2070 elem.priv = e;
2071
2072 iter->err = iter->fn(ctx, set, iter, &elem);
2073 if (iter->err < 0)
2074 goto out;
2075
2076 cont:
2077 iter->count++;
2078 }
2079
2080 out:
2081 rcu_read_unlock();
2082 }
2083
2084 /**
2085 * nft_pipapo_privsize() - Return the size of private data for the set
2086 * @nla: netlink attributes, ignored as size doesn't depend on them
2087 * @desc: Set description, ignored as size doesn't depend on it
2088 *
2089 * Return: size of private data for this set implementation, in bytes
2090 */
2091 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
2092 const struct nft_set_desc *desc)
2093 {
2094 return sizeof(struct nft_pipapo);
2095 }
2096
2097 /**
2098 * nft_pipapo_estimate() - Set size, space and lookup complexity
2099 * @desc: Set description, element count and field description used
2100 * @features: Flags: NFT_SET_INTERVAL needs to be there
2101 * @est: Storage for estimation data
2102 *
2103 * Return: true if set description is compatible, false otherwise
2104 */
2105 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
2106 struct nft_set_estimate *est)
2107 {
2108 if (!(features & NFT_SET_INTERVAL) ||
2109 desc->field_count < NFT_PIPAPO_MIN_FIELDS)
2110 return false;
2111
2112 est->size = pipapo_estimate_size(desc);
2113 if (!est->size)
2114 return false;
2115
2116 est->lookup = NFT_SET_CLASS_O_LOG_N;
2117
2118 est->space = NFT_SET_CLASS_O_N;
2119
2120 return true;
2121 }
2122
2123 /**
2124 * nft_pipapo_init() - Initialise data for a set instance
2125 * @set: nftables API set representation
2126 * @desc: Set description
2127 * @nla: netlink attributes
2128 *
2129 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
2130 * attributes, initialise internal set parameters, current instance of matching
2131 * data and a copy for subsequent insertions.
2132 *
2133 * Return: 0 on success, negative error code on failure.
2134 */
2135 static int nft_pipapo_init(const struct nft_set *set,
2136 const struct nft_set_desc *desc,
2137 const struct nlattr * const nla[])
2138 {
2139 struct nft_pipapo *priv = nft_set_priv(set);
2140 struct nft_pipapo_match *m;
2141 struct nft_pipapo_field *f;
2142 int err, i, field_count;
2143
2144 field_count = desc->field_count ? : 1;
2145
2146 if (field_count > NFT_PIPAPO_MAX_FIELDS)
2147 return -EINVAL;
2148
2149 m = kmalloc(struct_size(m, f, field_count), GFP_KERNEL);
2150 if (!m)
2151 return -ENOMEM;
2152
2153 m->field_count = field_count;
2154 m->bsize_max = 0;
2155
2156 m->scratch = alloc_percpu(struct nft_pipapo_scratch *);
2157 if (!m->scratch) {
2158 err = -ENOMEM;
2159 goto out_scratch;
2160 }
2161 for_each_possible_cpu(i)
2162 *per_cpu_ptr(m->scratch, i) = NULL;
2163
2164 rcu_head_init(&m->rcu);
2165
2166 nft_pipapo_for_each_field(f, i, m) {
2167 int len = desc->field_len[i] ? : set->klen;
2168
2169 f->bb = NFT_PIPAPO_GROUP_BITS_INIT;
2170 f->groups = len * NFT_PIPAPO_GROUPS_PER_BYTE(f);
2171
2172 priv->width += round_up(len, sizeof(u32));
2173
2174 f->bsize = 0;
2175 f->rules = 0;
2176 NFT_PIPAPO_LT_ASSIGN(f, NULL);
2177 f->mt = NULL;
2178 }
2179
2180 /* Create an initial clone of matching data for next insertion */
2181 priv->clone = pipapo_clone(m);
2182 if (IS_ERR(priv->clone)) {
2183 err = PTR_ERR(priv->clone);
2184 goto out_free;
2185 }
2186
2187 priv->dirty = false;
2188
2189 rcu_assign_pointer(priv->match, m);
2190
2191 return 0;
2192
2193 out_free:
2194 free_percpu(m->scratch);
2195 out_scratch:
2196 kfree(m);
2197
2198 return err;
2199 }
2200
2201 /**
2202 * nft_set_pipapo_match_destroy() - Destroy elements from key mapping array
2203 * @ctx: context
2204 * @set: nftables API set representation
2205 * @m: matching data pointing to key mapping array
2206 */
2207 static void nft_set_pipapo_match_destroy(const struct nft_ctx *ctx,
2208 const struct nft_set *set,
2209 struct nft_pipapo_match *m)
2210 {
2211 struct nft_pipapo_field *f;
2212 int i, r;
2213
2214 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2215 ;
2216
2217 for (r = 0; r < f->rules; r++) {
2218 struct nft_pipapo_elem *e;
2219
2220 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2221 continue;
2222
2223 e = f->mt[r].e;
2224
2225 nf_tables_set_elem_destroy(ctx, set, e);
2226 }
2227 }
2228
2229 /**
2230 * nft_pipapo_destroy() - Free private data for set and all committed elements
2231 * @ctx: context
2232 * @set: nftables API set representation
2233 */
2234 static void nft_pipapo_destroy(const struct nft_ctx *ctx,
2235 const struct nft_set *set)
2236 {
2237 struct nft_pipapo *priv = nft_set_priv(set);
2238 struct nft_pipapo_match *m;
2239 int cpu;
2240
2241 m = rcu_dereference_protected(priv->match, true);
2242 if (m) {
2243 rcu_barrier();
2244
2245 for_each_possible_cpu(cpu)
2246 pipapo_free_scratch(m, cpu);
2247 free_percpu(m->scratch);
2248 pipapo_free_fields(m);
2249 kfree(m);
2250 priv->match = NULL;
2251 }
2252
2253 if (priv->clone) {
2254 m = priv->clone;
2255
2256 nft_set_pipapo_match_destroy(ctx, set, m);
2257
2258 for_each_possible_cpu(cpu)
2259 pipapo_free_scratch(priv->clone, cpu);
2260 free_percpu(priv->clone->scratch);
2261
2262 pipapo_free_fields(priv->clone);
2263 kfree(priv->clone);
2264 priv->clone = NULL;
2265 }
2266 }
2267
2268 /**
2269 * nft_pipapo_gc_init() - Initialise garbage collection
2270 * @set: nftables API set representation
2271 *
2272 * Instead of actually setting up a periodic work for garbage collection, as
2273 * this operation requires a swap of matching data with the working copy, we'll
2274 * do that opportunistically with other commit operations if the interval is
2275 * elapsed, so we just need to set the current jiffies timestamp here.
2276 */
2277 static void nft_pipapo_gc_init(const struct nft_set *set)
2278 {
2279 struct nft_pipapo *priv = nft_set_priv(set);
2280
2281 priv->last_gc = jiffies;
2282 }
2283
2284 const struct nft_set_type nft_set_pipapo_type = {
2285 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2286 NFT_SET_TIMEOUT,
2287 .ops = {
2288 .lookup = nft_pipapo_lookup,
2289 .insert = nft_pipapo_insert,
2290 .activate = nft_pipapo_activate,
2291 .deactivate = nft_pipapo_deactivate,
2292 .flush = nft_pipapo_flush,
2293 .remove = nft_pipapo_remove,
2294 .walk = nft_pipapo_walk,
2295 .get = nft_pipapo_get,
2296 .privsize = nft_pipapo_privsize,
2297 .estimate = nft_pipapo_estimate,
2298 .init = nft_pipapo_init,
2299 .destroy = nft_pipapo_destroy,
2300 .gc_init = nft_pipapo_gc_init,
2301 .commit = nft_pipapo_commit,
2302 .abort = nft_pipapo_abort,
2303 .elemsize = offsetof(struct nft_pipapo_elem, ext),
2304 },
2305 };
2306
2307 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2308 const struct nft_set_type nft_set_pipapo_avx2_type = {
2309 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2310 NFT_SET_TIMEOUT,
2311 .ops = {
2312 .lookup = nft_pipapo_avx2_lookup,
2313 .insert = nft_pipapo_insert,
2314 .activate = nft_pipapo_activate,
2315 .deactivate = nft_pipapo_deactivate,
2316 .flush = nft_pipapo_flush,
2317 .remove = nft_pipapo_remove,
2318 .walk = nft_pipapo_walk,
2319 .get = nft_pipapo_get,
2320 .privsize = nft_pipapo_privsize,
2321 .estimate = nft_pipapo_avx2_estimate,
2322 .init = nft_pipapo_init,
2323 .destroy = nft_pipapo_destroy,
2324 .gc_init = nft_pipapo_gc_init,
2325 .commit = nft_pipapo_commit,
2326 .abort = nft_pipapo_abort,
2327 .elemsize = offsetof(struct nft_pipapo_elem, ext),
2328 },
2329 };
2330 #endif
2331