xref: /linux/net/netfilter/nft_set_pipapo.c (revision 07fdad3a93756b872da7b53647715c48d0f4a2d0)
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  */
362 int pipapo_refill(unsigned long *map, unsigned int len, unsigned int rules,
363 		  unsigned long *dst,
364 		  const union nft_pipapo_map_bucket *mt, bool match_only)
365 {
366 	unsigned long bitset;
367 	unsigned int k;
368 	int ret = -1;
369 
370 	for (k = 0; k < len; k++) {
371 		bitset = map[k];
372 		while (bitset) {
373 			unsigned long t = bitset & -bitset;
374 			int r = __builtin_ctzl(bitset);
375 			int i = k * BITS_PER_LONG + r;
376 
377 			if (unlikely(i >= rules)) {
378 				map[k] = 0;
379 				return -1;
380 			}
381 
382 			if (match_only) {
383 				bitmap_clear(map, i, 1);
384 				return i;
385 			}
386 
387 			ret = 0;
388 
389 			bitmap_set(dst, mt[i].to, mt[i].n);
390 
391 			bitset ^= t;
392 		}
393 		map[k] = 0;
394 	}
395 
396 	return ret;
397 }
398 
399 /**
400  * pipapo_get_slow() - Get matching element reference given key data
401  * @m:		storage containing the set elements
402  * @data:	Key data to be matched against existing elements
403  * @genmask:	If set, check that element is active in given genmask
404  * @tstamp:	timestamp to check for expired elements
405  *
406  * For more details, see DOC: Theory of Operation.
407  *
408  * This is the main lookup function.  It matches key data against either
409  * the working match set or the uncommitted copy, depending on what the
410  * caller passed to us.
411  * nft_pipapo_get (lookup from userspace/control plane) and nft_pipapo_lookup
412  * (datapath lookup) pass the active copy.
413  * The insertion path will pass the uncommitted working copy.
414  *
415  * Return: pointer to &struct nft_pipapo_elem on match, NULL otherwise.
416  */
417 static struct nft_pipapo_elem *pipapo_get_slow(const struct nft_pipapo_match *m,
418 					       const u8 *data, u8 genmask,
419 					       u64 tstamp)
420 {
421 	unsigned long *res_map, *fill_map, *map;
422 	struct nft_pipapo_scratch *scratch;
423 	const struct nft_pipapo_field *f;
424 	bool map_index;
425 	int i;
426 
427 	local_bh_disable();
428 
429 	scratch = *raw_cpu_ptr(m->scratch);
430 	if (unlikely(!scratch))
431 		goto out;
432 	__local_lock_nested_bh(&scratch->bh_lock);
433 
434 	map_index = scratch->map_index;
435 
436 	map = NFT_PIPAPO_LT_ALIGN(&scratch->__map[0]);
437 	res_map  = map + (map_index ? m->bsize_max : 0);
438 	fill_map = map + (map_index ? 0 : m->bsize_max);
439 
440 	pipapo_resmap_init(m, res_map);
441 
442 	nft_pipapo_for_each_field(f, i, m) {
443 		bool last = i == m->field_count - 1;
444 		int b;
445 
446 		/* For each bit group: select lookup table bucket depending on
447 		 * packet bytes value, then AND bucket value
448 		 */
449 		if (likely(f->bb == 8))
450 			pipapo_and_field_buckets_8bit(f, res_map, data);
451 		else
452 			pipapo_and_field_buckets_4bit(f, res_map, data);
453 		NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
454 
455 		data += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f);
456 
457 		/* Now populate the bitmap for the next field, unless this is
458 		 * the last field, in which case return the matched 'ext'
459 		 * pointer if any.
460 		 *
461 		 * Now res_map contains the matching bitmap, and fill_map is the
462 		 * bitmap for the next field.
463 		 */
464 next_match:
465 		b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
466 				  last);
467 		if (b < 0) {
468 			scratch->map_index = map_index;
469 			__local_unlock_nested_bh(&scratch->bh_lock);
470 			local_bh_enable();
471 
472 			return NULL;
473 		}
474 
475 		if (last) {
476 			struct nft_pipapo_elem *e;
477 
478 			e = f->mt[b].e;
479 			if (unlikely(__nft_set_elem_expired(&e->ext, tstamp) ||
480 				     !nft_set_elem_active(&e->ext, genmask)))
481 				goto next_match;
482 
483 			/* Last field: we're just returning the key without
484 			 * filling the initial bitmap for the next field, so the
485 			 * current inactive bitmap is clean and can be reused as
486 			 * *next* bitmap (not initial) for the next packet.
487 			 */
488 			scratch->map_index = map_index;
489 			__local_unlock_nested_bh(&scratch->bh_lock);
490 			local_bh_enable();
491 			return e;
492 		}
493 
494 		/* Swap bitmap indices: res_map is the initial bitmap for the
495 		 * next field, and fill_map is guaranteed to be all-zeroes at
496 		 * this point.
497 		 */
498 		map_index = !map_index;
499 		swap(res_map, fill_map);
500 
501 		data += NFT_PIPAPO_GROUPS_PADDING(f);
502 	}
503 
504 	__local_unlock_nested_bh(&scratch->bh_lock);
505 out:
506 	local_bh_enable();
507 	return NULL;
508 }
509 
510 /**
511  * pipapo_get() - Get matching element reference given key data
512  * @m:		Storage containing the set elements
513  * @data:	Key data to be matched against existing elements
514  * @genmask:	If set, check that element is active in given genmask
515  * @tstamp:	Timestamp to check for expired elements
516  *
517  * This is a dispatcher function, either calling out the generic C
518  * implementation or, if available, the AVX2 one.
519  * This helper is only called from the control plane, with either RCU
520  * read lock or transaction mutex held.
521  *
522  * Return: pointer to &struct nft_pipapo_elem on match, NULL otherwise.
523  */
524 static struct nft_pipapo_elem *pipapo_get(const struct nft_pipapo_match *m,
525 					  const u8 *data, u8 genmask,
526 					  u64 tstamp)
527 {
528 	struct nft_pipapo_elem *e;
529 
530 	local_bh_disable();
531 
532 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
533 	if (boot_cpu_has(X86_FEATURE_AVX2) && irq_fpu_usable()) {
534 		e = pipapo_get_avx2(m, data, genmask, tstamp);
535 		local_bh_enable();
536 		return e;
537 	}
538 #endif
539 	e = pipapo_get_slow(m, data, genmask, tstamp);
540 	local_bh_enable();
541 	return e;
542 }
543 
544 /**
545  * nft_pipapo_lookup() - Dataplane fronted for main lookup function
546  * @net:	Network namespace
547  * @set:	nftables API set representation
548  * @key:	pointer to nft registers containing key data
549  *
550  * This function is called from the data path.  It will search for
551  * an element matching the given key in the current active copy.
552  * Unlike other set types, this uses 0 instead of nft_genmask_cur().
553  *
554  * This is because new (future) elements are not reachable from
555  * priv->match, they get added to priv->clone instead.
556  * When the commit phase flips the generation bitmask, the
557  * 'now old' entries are skipped but without the 'now current'
558  * elements becoming visible. Using nft_genmask_cur() thus creates
559  * inconsistent state: matching old entries get skipped but thew
560  * newly matching entries are unreachable.
561  *
562  * GENMASK_ANY doesn't work for the same reason: old-gen entries get
563  * skipped, new-gen entries are only reachable from priv->clone.
564  *
565  * nft_pipapo_commit swaps ->clone and ->match shortly after the
566  * genbit flip.  As ->clone doesn't contain the old entries in the first
567  * place, lookup will only find the now-current ones.
568  *
569  * Return: ntables API extension pointer or NULL if no match.
570  */
571 const struct nft_set_ext *
572 nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
573 		  const u32 *key)
574 {
575 	struct nft_pipapo *priv = nft_set_priv(set);
576 	const struct nft_pipapo_match *m;
577 	const struct nft_pipapo_elem *e;
578 
579 	m = rcu_dereference(priv->match);
580 	e = pipapo_get_slow(m, (const u8 *)key, 0, get_jiffies_64());
581 
582 	return e ? &e->ext : NULL;
583 }
584 
585 /**
586  * nft_pipapo_get() - Get matching element reference given key data
587  * @net:	Network namespace
588  * @set:	nftables API set representation
589  * @elem:	nftables API element representation containing key data
590  * @flags:	Unused
591  *
592  * This function is called from the control plane path under
593  * RCU read lock.
594  *
595  * Return: set element private pointer or ERR_PTR(-ENOENT).
596  */
597 static struct nft_elem_priv *
598 nft_pipapo_get(const struct net *net, const struct nft_set *set,
599 	       const struct nft_set_elem *elem, unsigned int flags)
600 {
601 	struct nft_pipapo *priv = nft_set_priv(set);
602 	struct nft_pipapo_match *m = rcu_dereference(priv->match);
603 	struct nft_pipapo_elem *e;
604 
605 	e = pipapo_get(m, (const u8 *)elem->key.val.data,
606 		       nft_genmask_cur(net), get_jiffies_64());
607 	if (!e)
608 		return ERR_PTR(-ENOENT);
609 
610 	return &e->priv;
611 }
612 
613 /**
614  * pipapo_realloc_mt() - Reallocate mapping table if needed upon resize
615  * @f:		Field containing mapping table
616  * @old_rules:	Amount of existing mapped rules
617  * @rules:	Amount of new rules to map
618  *
619  * Return: 0 on success, negative error code on failure.
620  */
621 static int pipapo_realloc_mt(struct nft_pipapo_field *f,
622 			     unsigned int old_rules, unsigned int rules)
623 {
624 	union nft_pipapo_map_bucket *new_mt = NULL, *old_mt = f->mt;
625 	const unsigned int extra = PAGE_SIZE / sizeof(*new_mt);
626 	unsigned int rules_alloc = rules;
627 
628 	might_sleep();
629 
630 	if (unlikely(rules == 0))
631 		goto out_free;
632 
633 	/* growing and enough space left, no action needed */
634 	if (rules > old_rules && f->rules_alloc > rules)
635 		return 0;
636 
637 	/* downsize and extra slack has not grown too large */
638 	if (rules < old_rules) {
639 		unsigned int remove = f->rules_alloc - rules;
640 
641 		if (remove < (2u * extra))
642 			return 0;
643 	}
644 
645 	/* If set needs more than one page of memory for rules then
646 	 * allocate another extra page to avoid frequent reallocation.
647 	 */
648 	if (rules > extra &&
649 	    check_add_overflow(rules, extra, &rules_alloc))
650 		return -EOVERFLOW;
651 
652 	if (rules_alloc > (INT_MAX / sizeof(*new_mt)))
653 		return -ENOMEM;
654 
655 	new_mt = kvmalloc_array(rules_alloc, sizeof(*new_mt), GFP_KERNEL_ACCOUNT);
656 	if (!new_mt)
657 		return -ENOMEM;
658 
659 	if (old_mt)
660 		memcpy(new_mt, old_mt, min(old_rules, rules) * sizeof(*new_mt));
661 
662 	if (rules > old_rules) {
663 		memset(new_mt + old_rules, 0,
664 		       (rules - old_rules) * sizeof(*new_mt));
665 	}
666 out_free:
667 	f->rules_alloc = rules_alloc;
668 	f->mt = new_mt;
669 
670 	kvfree(old_mt);
671 
672 	return 0;
673 }
674 
675 
676 /**
677  * lt_calculate_size() - Get storage size for lookup table with overflow check
678  * @groups:	Amount of bit groups
679  * @bb:		Number of bits grouped together in lookup table buckets
680  * @bsize:	Size of each bucket in lookup table, in longs
681  *
682  * Return: allocation size including alignment overhead, negative on overflow
683  */
684 static ssize_t lt_calculate_size(unsigned int groups, unsigned int bb,
685 				 unsigned int bsize)
686 {
687 	ssize_t ret = groups * NFT_PIPAPO_BUCKETS(bb) * sizeof(long);
688 
689 	if (check_mul_overflow(ret, bsize, &ret))
690 		return -1;
691 	if (check_add_overflow(ret, NFT_PIPAPO_ALIGN_HEADROOM, &ret))
692 		return -1;
693 	if (ret > INT_MAX)
694 		return -1;
695 
696 	return ret;
697 }
698 
699 /**
700  * pipapo_resize() - Resize lookup or mapping table, or both
701  * @f:		Field containing lookup and mapping tables
702  * @old_rules:	Previous amount of rules in field
703  * @rules:	New amount of rules
704  *
705  * Increase, decrease or maintain tables size depending on new amount of rules,
706  * and copy data over. In case the new size is smaller, throw away data for
707  * highest-numbered rules.
708  *
709  * Return: 0 on success, -ENOMEM on allocation failure.
710  */
711 static int pipapo_resize(struct nft_pipapo_field *f,
712 			 unsigned int old_rules, unsigned int rules)
713 {
714 	long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
715 	unsigned int new_bucket_size, copy;
716 	int group, bucket, err;
717 	ssize_t lt_size;
718 
719 	if (rules >= NFT_PIPAPO_RULE0_MAX)
720 		return -ENOSPC;
721 
722 	new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
723 #ifdef NFT_PIPAPO_ALIGN
724 	new_bucket_size = roundup(new_bucket_size,
725 				  NFT_PIPAPO_ALIGN / sizeof(*new_lt));
726 #endif
727 
728 	if (new_bucket_size == f->bsize)
729 		goto mt;
730 
731 	if (new_bucket_size > f->bsize)
732 		copy = f->bsize;
733 	else
734 		copy = new_bucket_size;
735 
736 	lt_size = lt_calculate_size(f->groups, f->bb, new_bucket_size);
737 	if (lt_size < 0)
738 		return -ENOMEM;
739 
740 	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
741 	if (!new_lt)
742 		return -ENOMEM;
743 
744 	new_p = NFT_PIPAPO_LT_ALIGN(new_lt);
745 	old_p = NFT_PIPAPO_LT_ALIGN(old_lt);
746 
747 	for (group = 0; group < f->groups; group++) {
748 		for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS(f->bb); bucket++) {
749 			memcpy(new_p, old_p, copy * sizeof(*new_p));
750 			new_p += copy;
751 			old_p += copy;
752 
753 			if (new_bucket_size > f->bsize)
754 				new_p += new_bucket_size - f->bsize;
755 			else
756 				old_p += f->bsize - new_bucket_size;
757 		}
758 	}
759 
760 mt:
761 	err = pipapo_realloc_mt(f, old_rules, rules);
762 	if (err) {
763 		kvfree(new_lt);
764 		return err;
765 	}
766 
767 	if (new_lt) {
768 		f->bsize = new_bucket_size;
769 		f->lt = new_lt;
770 		kvfree(old_lt);
771 	}
772 
773 	return 0;
774 }
775 
776 /**
777  * pipapo_bucket_set() - Set rule bit in bucket given group and group value
778  * @f:		Field containing lookup table
779  * @rule:	Rule index
780  * @group:	Group index
781  * @v:		Value of bit group
782  */
783 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
784 			      int v)
785 {
786 	unsigned long *pos;
787 
788 	pos = NFT_PIPAPO_LT_ALIGN(f->lt);
789 	pos += f->bsize * NFT_PIPAPO_BUCKETS(f->bb) * group;
790 	pos += f->bsize * v;
791 
792 	__set_bit(rule, pos);
793 }
794 
795 /**
796  * pipapo_lt_4b_to_8b() - Switch lookup table group width from 4 bits to 8 bits
797  * @old_groups:	Number of current groups
798  * @bsize:	Size of one bucket, in longs
799  * @old_lt:	Pointer to the current lookup table
800  * @new_lt:	Pointer to the new, pre-allocated lookup table
801  *
802  * Each bucket with index b in the new lookup table, belonging to group g, is
803  * filled with the bit intersection between:
804  * - bucket with index given by the upper 4 bits of b, from group g, and
805  * - bucket with index given by the lower 4 bits of b, from group g + 1
806  *
807  * That is, given buckets from the new lookup table N(x, y) and the old lookup
808  * table O(x, y), with x bucket index, and y group index:
809  *
810  *	N(b, g) := O(b / 16, g) & O(b % 16, g + 1)
811  *
812  * This ensures equivalence of the matching results on lookup. Two examples in
813  * pictures:
814  *
815  *              bucket
816  *  group  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 ... 254 255
817  *    0                ^
818  *    1                |                                                 ^
819  *   ...             ( & )                                               |
820  *                  /     \                                              |
821  *                 /       \                                         .-( & )-.
822  *                /  bucket \                                        |       |
823  *      group  0 / 1   2   3 \ 4   5   6   7   8   9  10  11  12  13 |14  15 |
824  *        0     /             \                                      |       |
825  *        1                    \                                     |       |
826  *        2                                                          |     --'
827  *        3                                                          '-
828  *       ...
829  */
830 static void pipapo_lt_4b_to_8b(int old_groups, int bsize,
831 			       unsigned long *old_lt, unsigned long *new_lt)
832 {
833 	int g, b, i;
834 
835 	for (g = 0; g < old_groups / 2; g++) {
836 		int src_g0 = g * 2, src_g1 = g * 2 + 1;
837 
838 		for (b = 0; b < NFT_PIPAPO_BUCKETS(8); b++) {
839 			int src_b0 = b / NFT_PIPAPO_BUCKETS(4);
840 			int src_b1 = b % NFT_PIPAPO_BUCKETS(4);
841 			int src_i0 = src_g0 * NFT_PIPAPO_BUCKETS(4) + src_b0;
842 			int src_i1 = src_g1 * NFT_PIPAPO_BUCKETS(4) + src_b1;
843 
844 			for (i = 0; i < bsize; i++) {
845 				*new_lt = old_lt[src_i0 * bsize + i] &
846 					  old_lt[src_i1 * bsize + i];
847 				new_lt++;
848 			}
849 		}
850 	}
851 }
852 
853 /**
854  * pipapo_lt_8b_to_4b() - Switch lookup table group width from 8 bits to 4 bits
855  * @old_groups:	Number of current groups
856  * @bsize:	Size of one bucket, in longs
857  * @old_lt:	Pointer to the current lookup table
858  * @new_lt:	Pointer to the new, pre-allocated lookup table
859  *
860  * Each bucket with index b in the new lookup table, belonging to group g, is
861  * filled with the bit union of:
862  * - all the buckets with index such that the upper four bits of the lower byte
863  *   equal b, from group g, with g odd
864  * - all the buckets with index such that the lower four bits equal b, from
865  *   group g, with g even
866  *
867  * That is, given buckets from the new lookup table N(x, y) and the old lookup
868  * table O(x, y), with x bucket index, and y group index:
869  *
870  *	- with g odd:  N(b, g) := U(O(x, g) for each x : x = (b & 0xf0) >> 4)
871  *	- with g even: N(b, g) := U(O(x, g) for each x : x = b & 0x0f)
872  *
873  * where U() denotes the arbitrary union operation (binary OR of n terms). This
874  * ensures equivalence of the matching results on lookup.
875  */
876 static void pipapo_lt_8b_to_4b(int old_groups, int bsize,
877 			       unsigned long *old_lt, unsigned long *new_lt)
878 {
879 	int g, b, bsrc, i;
880 
881 	memset(new_lt, 0, old_groups * 2 * NFT_PIPAPO_BUCKETS(4) * bsize *
882 			  sizeof(unsigned long));
883 
884 	for (g = 0; g < old_groups * 2; g += 2) {
885 		int src_g = g / 2;
886 
887 		for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
888 			for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
889 			     bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
890 			     bsrc++) {
891 				if (((bsrc & 0xf0) >> 4) != b)
892 					continue;
893 
894 				for (i = 0; i < bsize; i++)
895 					new_lt[i] |= old_lt[bsrc * bsize + i];
896 			}
897 
898 			new_lt += bsize;
899 		}
900 
901 		for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
902 			for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
903 			     bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
904 			     bsrc++) {
905 				if ((bsrc & 0x0f) != b)
906 					continue;
907 
908 				for (i = 0; i < bsize; i++)
909 					new_lt[i] |= old_lt[bsrc * bsize + i];
910 			}
911 
912 			new_lt += bsize;
913 		}
914 	}
915 }
916 
917 /**
918  * pipapo_lt_bits_adjust() - Adjust group size for lookup table if needed
919  * @f:		Field containing lookup table
920  */
921 static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
922 {
923 	unsigned int groups, bb;
924 	unsigned long *new_lt;
925 	ssize_t lt_size;
926 
927 	lt_size = f->groups * NFT_PIPAPO_BUCKETS(f->bb) * f->bsize *
928 		  sizeof(*f->lt);
929 
930 	if (f->bb == NFT_PIPAPO_GROUP_BITS_SMALL_SET &&
931 	    lt_size > NFT_PIPAPO_LT_SIZE_HIGH) {
932 		groups = f->groups * 2;
933 		bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
934 
935 		lt_size = lt_calculate_size(groups, bb, f->bsize);
936 		if (lt_size < 0)
937 			return;
938 	} else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
939 		   lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
940 		groups = f->groups / 2;
941 		bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
942 
943 		lt_size = lt_calculate_size(groups, bb, f->bsize);
944 		if (lt_size < 0)
945 			return;
946 
947 		/* Don't increase group width if the resulting lookup table size
948 		 * would exceed the upper size threshold for a "small" set.
949 		 */
950 		if (lt_size > NFT_PIPAPO_LT_SIZE_HIGH)
951 			return;
952 	} else {
953 		return;
954 	}
955 
956 	new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
957 	if (!new_lt)
958 		return;
959 
960 	NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
961 	if (f->bb == 4 && bb == 8) {
962 		pipapo_lt_4b_to_8b(f->groups, f->bsize,
963 				   NFT_PIPAPO_LT_ALIGN(f->lt),
964 				   NFT_PIPAPO_LT_ALIGN(new_lt));
965 	} else if (f->bb == 8 && bb == 4) {
966 		pipapo_lt_8b_to_4b(f->groups, f->bsize,
967 				   NFT_PIPAPO_LT_ALIGN(f->lt),
968 				   NFT_PIPAPO_LT_ALIGN(new_lt));
969 	} else {
970 		BUG();
971 	}
972 
973 	f->groups = groups;
974 	f->bb = bb;
975 	kvfree(f->lt);
976 	f->lt = new_lt;
977 }
978 
979 /**
980  * pipapo_insert() - Insert new rule in field given input key and mask length
981  * @f:		Field containing lookup table
982  * @k:		Input key for classification, without nftables padding
983  * @mask_bits:	Length of mask; matches field length for non-ranged entry
984  *
985  * Insert a new rule reference in lookup buckets corresponding to k and
986  * mask_bits.
987  *
988  * Return: 1 on success (one rule inserted), negative error code on failure.
989  */
990 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
991 			 int mask_bits)
992 {
993 	unsigned int rule = f->rules, group, ret, bit_offset = 0;
994 
995 	ret = pipapo_resize(f, f->rules, f->rules + 1);
996 	if (ret)
997 		return ret;
998 
999 	f->rules++;
1000 
1001 	for (group = 0; group < f->groups; group++) {
1002 		int i, v;
1003 		u8 mask;
1004 
1005 		v = k[group / (BITS_PER_BYTE / f->bb)];
1006 		v &= GENMASK(BITS_PER_BYTE - bit_offset - 1, 0);
1007 		v >>= (BITS_PER_BYTE - bit_offset) - f->bb;
1008 
1009 		bit_offset += f->bb;
1010 		bit_offset %= BITS_PER_BYTE;
1011 
1012 		if (mask_bits >= (group + 1) * f->bb) {
1013 			/* Not masked */
1014 			pipapo_bucket_set(f, rule, group, v);
1015 		} else if (mask_bits <= group * f->bb) {
1016 			/* Completely masked */
1017 			for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++)
1018 				pipapo_bucket_set(f, rule, group, i);
1019 		} else {
1020 			/* The mask limit falls on this group */
1021 			mask = GENMASK(f->bb - 1, 0);
1022 			mask >>= mask_bits - group * f->bb;
1023 			for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++) {
1024 				if ((i & ~mask) == (v & ~mask))
1025 					pipapo_bucket_set(f, rule, group, i);
1026 			}
1027 		}
1028 	}
1029 
1030 	pipapo_lt_bits_adjust(f);
1031 
1032 	return 1;
1033 }
1034 
1035 /**
1036  * pipapo_step_diff() - Check if setting @step bit in netmask would change it
1037  * @base:	Mask we are expanding
1038  * @step:	Step bit for given expansion step
1039  * @len:	Total length of mask space (set and unset bits), bytes
1040  *
1041  * Convenience function for mask expansion.
1042  *
1043  * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
1044  */
1045 static bool pipapo_step_diff(u8 *base, int step, int len)
1046 {
1047 	/* Network order, byte-addressed */
1048 #ifdef __BIG_ENDIAN__
1049 	return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
1050 #else
1051 	return !(BIT(step % BITS_PER_BYTE) &
1052 		 base[len - 1 - step / BITS_PER_BYTE]);
1053 #endif
1054 }
1055 
1056 /**
1057  * pipapo_step_after_end() - Check if mask exceeds range end with given step
1058  * @base:	Mask we are expanding
1059  * @end:	End of range
1060  * @step:	Step bit for given expansion step, highest bit to be set
1061  * @len:	Total length of mask space (set and unset bits), bytes
1062  *
1063  * Convenience function for mask expansion.
1064  *
1065  * Return: true if mask exceeds range setting step bits, false otherwise.
1066  */
1067 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
1068 				  int len)
1069 {
1070 	u8 tmp[NFT_PIPAPO_MAX_BYTES];
1071 	int i;
1072 
1073 	memcpy(tmp, base, len);
1074 
1075 	/* Network order, byte-addressed */
1076 	for (i = 0; i <= step; i++)
1077 #ifdef __BIG_ENDIAN__
1078 		tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
1079 #else
1080 		tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
1081 #endif
1082 
1083 	return memcmp(tmp, end, len) > 0;
1084 }
1085 
1086 /**
1087  * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
1088  * @base:	Netmask base
1089  * @step:	Step bit to sum
1090  * @len:	Netmask length, bytes
1091  */
1092 static void pipapo_base_sum(u8 *base, int step, int len)
1093 {
1094 	bool carry = false;
1095 	int i;
1096 
1097 	/* Network order, byte-addressed */
1098 #ifdef __BIG_ENDIAN__
1099 	for (i = step / BITS_PER_BYTE; i < len; i++) {
1100 #else
1101 	for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
1102 #endif
1103 		if (carry)
1104 			base[i]++;
1105 		else
1106 			base[i] += 1 << (step % BITS_PER_BYTE);
1107 
1108 		if (base[i])
1109 			break;
1110 
1111 		carry = true;
1112 	}
1113 }
1114 
1115 /**
1116  * pipapo_expand() - Expand to composing netmasks, insert into lookup table
1117  * @f:		Field containing lookup table
1118  * @start:	Start of range
1119  * @end:	End of range
1120  * @len:	Length of value in bits
1121  *
1122  * Expand range to composing netmasks and insert corresponding rule references
1123  * in lookup buckets.
1124  *
1125  * Return: number of inserted rules on success, negative error code on failure.
1126  */
1127 static int pipapo_expand(struct nft_pipapo_field *f,
1128 			 const u8 *start, const u8 *end, int len)
1129 {
1130 	int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
1131 	u8 base[NFT_PIPAPO_MAX_BYTES];
1132 
1133 	memcpy(base, start, bytes);
1134 	while (memcmp(base, end, bytes) <= 0) {
1135 		int err;
1136 
1137 		step = 0;
1138 		while (pipapo_step_diff(base, step, bytes)) {
1139 			if (pipapo_step_after_end(base, end, step, bytes))
1140 				break;
1141 
1142 			step++;
1143 			if (step >= len) {
1144 				if (!masks) {
1145 					err = pipapo_insert(f, base, 0);
1146 					if (err < 0)
1147 						return err;
1148 					masks = 1;
1149 				}
1150 				goto out;
1151 			}
1152 		}
1153 
1154 		err = pipapo_insert(f, base, len - step);
1155 
1156 		if (err < 0)
1157 			return err;
1158 
1159 		masks++;
1160 		pipapo_base_sum(base, step, bytes);
1161 	}
1162 out:
1163 	return masks;
1164 }
1165 
1166 /**
1167  * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1168  * @m:		Matching data, including mapping table
1169  * @map:	Table of rule maps: array of first rule and amount of rules
1170  *		in next field a given rule maps to, for each field
1171  * @e:		For last field, nft_set_ext pointer matching rules map to
1172  */
1173 static void pipapo_map(struct nft_pipapo_match *m,
1174 		       union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1175 		       struct nft_pipapo_elem *e)
1176 {
1177 	struct nft_pipapo_field *f;
1178 	int i, j;
1179 
1180 	for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1181 		for (j = 0; j < map[i].n; j++) {
1182 			f->mt[map[i].to + j].to = map[i + 1].to;
1183 			f->mt[map[i].to + j].n = map[i + 1].n;
1184 		}
1185 	}
1186 
1187 	/* Last field: map to ext instead of mapping to next field */
1188 	for (j = 0; j < map[i].n; j++)
1189 		f->mt[map[i].to + j].e = e;
1190 }
1191 
1192 /**
1193  * pipapo_free_scratch() - Free per-CPU map at original address
1194  * @m:		Matching data
1195  * @cpu:	CPU number
1196  */
1197 static void pipapo_free_scratch(const struct nft_pipapo_match *m, unsigned int cpu)
1198 {
1199 	struct nft_pipapo_scratch *s;
1200 
1201 	s = *per_cpu_ptr(m->scratch, cpu);
1202 
1203 	kvfree(s);
1204 }
1205 
1206 /**
1207  * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1208  * @clone:	Copy of matching data with pending insertions and deletions
1209  * @bsize_max:	Maximum bucket size, scratch maps cover two buckets
1210  *
1211  * Return: 0 on success, -ENOMEM on failure.
1212  */
1213 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1214 				  unsigned long bsize_max)
1215 {
1216 	int i;
1217 
1218 	for_each_possible_cpu(i) {
1219 		struct nft_pipapo_scratch *scratch;
1220 
1221 		scratch = kvzalloc_node(struct_size(scratch, __map, bsize_max * 2) +
1222 					NFT_PIPAPO_ALIGN_HEADROOM,
1223 					GFP_KERNEL_ACCOUNT, cpu_to_node(i));
1224 		if (!scratch) {
1225 			/* On failure, there's no need to undo previous
1226 			 * allocations: this means that some scratch maps have
1227 			 * a bigger allocated size now (this is only called on
1228 			 * insertion), but the extra space won't be used by any
1229 			 * CPU as new elements are not inserted and m->bsize_max
1230 			 * is not updated.
1231 			 */
1232 			return -ENOMEM;
1233 		}
1234 
1235 		pipapo_free_scratch(clone, i);
1236 		local_lock_init(&scratch->bh_lock);
1237 		*per_cpu_ptr(clone->scratch, i) = scratch;
1238 	}
1239 
1240 	return 0;
1241 }
1242 
1243 static bool nft_pipapo_transaction_mutex_held(const struct nft_set *set)
1244 {
1245 #ifdef CONFIG_PROVE_LOCKING
1246 	const struct net *net = read_pnet(&set->net);
1247 
1248 	return lockdep_is_held(&nft_pernet(net)->commit_mutex);
1249 #else
1250 	return true;
1251 #endif
1252 }
1253 
1254 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old);
1255 
1256 /**
1257  * pipapo_maybe_clone() - Build clone for pending data changes, if not existing
1258  * @set:	nftables API set representation
1259  *
1260  * Return: newly created or existing clone, if any. NULL on allocation failure
1261  */
1262 static struct nft_pipapo_match *pipapo_maybe_clone(const struct nft_set *set)
1263 {
1264 	struct nft_pipapo *priv = nft_set_priv(set);
1265 	struct nft_pipapo_match *m;
1266 
1267 	if (priv->clone)
1268 		return priv->clone;
1269 
1270 	m = rcu_dereference_protected(priv->match,
1271 				      nft_pipapo_transaction_mutex_held(set));
1272 	priv->clone = pipapo_clone(m);
1273 
1274 	return priv->clone;
1275 }
1276 
1277 /**
1278  * nft_pipapo_insert() - Validate and insert ranged elements
1279  * @net:	Network namespace
1280  * @set:	nftables API set representation
1281  * @elem:	nftables API element representation containing key data
1282  * @elem_priv:	Filled with pointer to &struct nft_set_ext in inserted element
1283  *
1284  * Return: 0 on success, error pointer on failure.
1285  */
1286 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1287 			     const struct nft_set_elem *elem,
1288 			     struct nft_elem_priv **elem_priv)
1289 {
1290 	const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1291 	union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1292 	const u8 *start = (const u8 *)elem->key.val.data, *end;
1293 	struct nft_pipapo_match *m = pipapo_maybe_clone(set);
1294 	u8 genmask = nft_genmask_next(net);
1295 	struct nft_pipapo_elem *e, *dup;
1296 	u64 tstamp = nft_net_tstamp(net);
1297 	struct nft_pipapo_field *f;
1298 	const u8 *start_p, *end_p;
1299 	int i, bsize_max, err = 0;
1300 
1301 	if (!m)
1302 		return -ENOMEM;
1303 
1304 	if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END))
1305 		end = (const u8 *)nft_set_ext_key_end(ext)->data;
1306 	else
1307 		end = start;
1308 
1309 	dup = pipapo_get(m, start, genmask, tstamp);
1310 	if (dup) {
1311 		/* Check if we already have the same exact entry */
1312 		const struct nft_data *dup_key, *dup_end;
1313 
1314 		dup_key = nft_set_ext_key(&dup->ext);
1315 		if (nft_set_ext_exists(&dup->ext, NFT_SET_EXT_KEY_END))
1316 			dup_end = nft_set_ext_key_end(&dup->ext);
1317 		else
1318 			dup_end = dup_key;
1319 
1320 		if (!memcmp(start, dup_key->data, sizeof(*dup_key->data)) &&
1321 		    !memcmp(end, dup_end->data, sizeof(*dup_end->data))) {
1322 			*elem_priv = &dup->priv;
1323 			return -EEXIST;
1324 		}
1325 
1326 		return -ENOTEMPTY;
1327 	}
1328 
1329 	/* Look for partially overlapping entries */
1330 	dup = pipapo_get(m, end, nft_genmask_next(net), tstamp);
1331 	if (dup) {
1332 		*elem_priv = &dup->priv;
1333 		return -ENOTEMPTY;
1334 	}
1335 
1336 	/* Validate */
1337 	start_p = start;
1338 	end_p = end;
1339 
1340 	/* some helpers return -1, or 0 >= for valid rule pos,
1341 	 * so we cannot support more than INT_MAX rules at this time.
1342 	 */
1343 	BUILD_BUG_ON(NFT_PIPAPO_RULE0_MAX > INT_MAX);
1344 
1345 	nft_pipapo_for_each_field(f, i, m) {
1346 		if (f->rules >= NFT_PIPAPO_RULE0_MAX)
1347 			return -ENOSPC;
1348 
1349 		if (memcmp(start_p, end_p,
1350 			   f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) > 0)
1351 			return -EINVAL;
1352 
1353 		start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1354 		end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1355 	}
1356 
1357 	/* Insert */
1358 	bsize_max = m->bsize_max;
1359 
1360 	nft_pipapo_for_each_field(f, i, m) {
1361 		int ret;
1362 
1363 		rulemap[i].to = f->rules;
1364 
1365 		ret = memcmp(start, end,
1366 			     f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1367 		if (!ret)
1368 			ret = pipapo_insert(f, start, f->groups * f->bb);
1369 		else
1370 			ret = pipapo_expand(f, start, end, f->groups * f->bb);
1371 
1372 		if (ret < 0)
1373 			return ret;
1374 
1375 		if (f->bsize > bsize_max)
1376 			bsize_max = f->bsize;
1377 
1378 		rulemap[i].n = ret;
1379 
1380 		start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1381 		end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1382 	}
1383 
1384 	if (!*get_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1385 		put_cpu_ptr(m->scratch);
1386 
1387 		err = pipapo_realloc_scratch(m, bsize_max);
1388 		if (err)
1389 			return err;
1390 
1391 		m->bsize_max = bsize_max;
1392 	} else {
1393 		put_cpu_ptr(m->scratch);
1394 	}
1395 
1396 	e = nft_elem_priv_cast(elem->priv);
1397 	*elem_priv = &e->priv;
1398 
1399 	pipapo_map(m, rulemap, e);
1400 
1401 	return 0;
1402 }
1403 
1404 /**
1405  * pipapo_clone() - Clone matching data to create new working copy
1406  * @old:	Existing matching data
1407  *
1408  * Return: copy of matching data passed as 'old' or NULL.
1409  */
1410 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1411 {
1412 	struct nft_pipapo_field *dst, *src;
1413 	struct nft_pipapo_match *new;
1414 	int i;
1415 
1416 	new = kmalloc(struct_size(new, f, old->field_count), GFP_KERNEL_ACCOUNT);
1417 	if (!new)
1418 		return NULL;
1419 
1420 	new->field_count = old->field_count;
1421 	new->bsize_max = old->bsize_max;
1422 
1423 	new->scratch = alloc_percpu(*new->scratch);
1424 	if (!new->scratch)
1425 		goto out_scratch;
1426 
1427 	for_each_possible_cpu(i)
1428 		*per_cpu_ptr(new->scratch, i) = NULL;
1429 
1430 	if (pipapo_realloc_scratch(new, old->bsize_max))
1431 		goto out_scratch_realloc;
1432 
1433 	rcu_head_init(&new->rcu);
1434 
1435 	src = old->f;
1436 	dst = new->f;
1437 
1438 	for (i = 0; i < old->field_count; i++) {
1439 		unsigned long *new_lt;
1440 		ssize_t lt_size;
1441 
1442 		memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1443 
1444 		lt_size = lt_calculate_size(src->groups, src->bb, src->bsize);
1445 		if (lt_size < 0)
1446 			goto out_lt;
1447 
1448 		new_lt = kvzalloc(lt_size, GFP_KERNEL_ACCOUNT);
1449 		if (!new_lt)
1450 			goto out_lt;
1451 
1452 		dst->lt = new_lt;
1453 
1454 		memcpy(NFT_PIPAPO_LT_ALIGN(new_lt),
1455 		       NFT_PIPAPO_LT_ALIGN(src->lt),
1456 		       src->bsize * sizeof(*dst->lt) *
1457 		       src->groups * NFT_PIPAPO_BUCKETS(src->bb));
1458 
1459 		if (src->rules > 0) {
1460 			if (src->rules_alloc > (INT_MAX / sizeof(*src->mt)))
1461 				goto out_mt;
1462 
1463 			dst->mt = kvmalloc_array(src->rules_alloc,
1464 						 sizeof(*src->mt),
1465 						 GFP_KERNEL_ACCOUNT);
1466 			if (!dst->mt)
1467 				goto out_mt;
1468 
1469 			memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1470 		} else {
1471 			dst->mt = NULL;
1472 			dst->rules_alloc = 0;
1473 		}
1474 
1475 		src++;
1476 		dst++;
1477 	}
1478 
1479 	return new;
1480 
1481 out_mt:
1482 	kvfree(dst->lt);
1483 out_lt:
1484 	for (dst--; i > 0; i--) {
1485 		kvfree(dst->mt);
1486 		kvfree(dst->lt);
1487 		dst--;
1488 	}
1489 out_scratch_realloc:
1490 	for_each_possible_cpu(i)
1491 		pipapo_free_scratch(new, i);
1492 out_scratch:
1493 	free_percpu(new->scratch);
1494 	kfree(new);
1495 
1496 	return NULL;
1497 }
1498 
1499 /**
1500  * pipapo_rules_same_key() - Get number of rules originated from the same entry
1501  * @f:		Field containing mapping table
1502  * @first:	Index of first rule in set of rules mapping to same entry
1503  *
1504  * Using the fact that all rules in a field that originated from the same entry
1505  * will map to the same set of rules in the next field, or to the same element
1506  * reference, return the cardinality of the set of rules that originated from
1507  * the same entry as the rule with index @first, @first rule included.
1508  *
1509  * In pictures:
1510  *				rules
1511  *	field #0		0    1    2    3    4
1512  *		map to:		0    1   2-4  2-4  5-9
1513  *				.    .    .......   . ...
1514  *				|    |    |    | \   \
1515  *				|    |    |    |  \   \
1516  *				|    |    |    |   \   \
1517  *				'    '    '    '    '   \
1518  *	in field #1		0    1    2    3    4    5 ...
1519  *
1520  * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1521  * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1522  *
1523  * For the last field in a set, we can rely on associated entries to map to the
1524  * same element references.
1525  *
1526  * Return: Number of rules that originated from the same entry as @first.
1527  */
1528 static unsigned int pipapo_rules_same_key(struct nft_pipapo_field *f, unsigned int first)
1529 {
1530 	struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1531 	unsigned int r;
1532 
1533 	for (r = first; r < f->rules; r++) {
1534 		if (r != first && e != f->mt[r].e)
1535 			return r - first;
1536 
1537 		e = f->mt[r].e;
1538 	}
1539 
1540 	if (r != first)
1541 		return r - first;
1542 
1543 	return 0;
1544 }
1545 
1546 /**
1547  * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1548  * @mt:		Mapping array
1549  * @rules:	Original amount of rules in mapping table
1550  * @start:	First rule index to be removed
1551  * @n:		Amount of rules to be removed
1552  * @to_offset:	First rule index, in next field, this group of rules maps to
1553  * @is_last:	If this is the last field, delete reference from mapping array
1554  *
1555  * This is used to unmap rules from the mapping table for a single field,
1556  * maintaining consistency and compactness for the existing ones.
1557  *
1558  * In pictures: let's assume that we want to delete rules 2 and 3 from the
1559  * following mapping array:
1560  *
1561  *                 rules
1562  *               0      1      2      3      4
1563  *      map to:  4-10   4-10   11-15  11-15  16-18
1564  *
1565  * the result will be:
1566  *
1567  *                 rules
1568  *               0      1      2
1569  *      map to:  4-10   4-10   11-13
1570  *
1571  * for fields before the last one. In case this is the mapping table for the
1572  * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1573  *
1574  *                      rules
1575  *                        0      1      2      3      4
1576  *  element pointers:  0x42   0x42   0x33   0x33   0x44
1577  *
1578  * the result will be:
1579  *
1580  *                      rules
1581  *                        0      1      2
1582  *  element pointers:  0x42   0x42   0x44
1583  */
1584 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, unsigned int rules,
1585 			 unsigned int start, unsigned int n,
1586 			 unsigned int to_offset, bool is_last)
1587 {
1588 	int i;
1589 
1590 	memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1591 	memset(mt + rules - n, 0, n * sizeof(*mt));
1592 
1593 	if (is_last)
1594 		return;
1595 
1596 	for (i = start; i < rules - n; i++)
1597 		mt[i].to -= to_offset;
1598 }
1599 
1600 /**
1601  * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1602  * @m:		Matching data
1603  * @rulemap:	Table of rule maps, arrays of first rule and amount of rules
1604  *		in next field a given entry maps to, for each field
1605  *
1606  * For each rule in lookup table buckets mapping to this set of rules, drop
1607  * all bits set in lookup table mapping. In pictures, assuming we want to drop
1608  * rules 0 and 1 from this lookup table:
1609  *
1610  *                     bucket
1611  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1612  *        0    0                                              1,2
1613  *        1   1,2                                      0
1614  *        2    0                                      1,2
1615  *        3    0                              1,2
1616  *        4  0,1,2
1617  *        5    0   1   2
1618  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1619  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
1620  *
1621  * rule 2 becomes rule 0, and the result will be:
1622  *
1623  *                     bucket
1624  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1625  *        0                                                    0
1626  *        1    0
1627  *        2                                            0
1628  *        3                                    0
1629  *        4    0
1630  *        5            0
1631  *        6    0
1632  *        7    0   0
1633  *
1634  * once this is done, call unmap() to drop all the corresponding rule references
1635  * from mapping tables.
1636  */
1637 static void pipapo_drop(struct nft_pipapo_match *m,
1638 			union nft_pipapo_map_bucket rulemap[])
1639 {
1640 	struct nft_pipapo_field *f;
1641 	int i;
1642 
1643 	nft_pipapo_for_each_field(f, i, m) {
1644 		int g;
1645 
1646 		for (g = 0; g < f->groups; g++) {
1647 			unsigned long *pos;
1648 			int b;
1649 
1650 			pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g *
1651 			      NFT_PIPAPO_BUCKETS(f->bb) * f->bsize;
1652 
1653 			for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1654 				bitmap_cut(pos, pos, rulemap[i].to,
1655 					   rulemap[i].n,
1656 					   f->bsize * BITS_PER_LONG);
1657 
1658 				pos += f->bsize;
1659 			}
1660 		}
1661 
1662 		pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1663 			     rulemap[i + 1].n, i == m->field_count - 1);
1664 		if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1665 			/* We can ignore this, a failure to shrink tables down
1666 			 * doesn't make tables invalid.
1667 			 */
1668 			;
1669 		}
1670 		f->rules -= rulemap[i].n;
1671 
1672 		pipapo_lt_bits_adjust(f);
1673 	}
1674 }
1675 
1676 static void nft_pipapo_gc_deactivate(struct net *net, struct nft_set *set,
1677 				     struct nft_pipapo_elem *e)
1678 
1679 {
1680 	nft_setelem_data_deactivate(net, set, &e->priv);
1681 }
1682 
1683 /**
1684  * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1685  * @set:	nftables API set representation
1686  * @m:		Matching data
1687  */
1688 static void pipapo_gc(struct nft_set *set, struct nft_pipapo_match *m)
1689 {
1690 	struct nft_pipapo *priv = nft_set_priv(set);
1691 	struct net *net = read_pnet(&set->net);
1692 	unsigned int rules_f0, first_rule = 0;
1693 	u64 tstamp = nft_net_tstamp(net);
1694 	struct nft_pipapo_elem *e;
1695 	struct nft_trans_gc *gc;
1696 
1697 	gc = nft_trans_gc_alloc(set, 0, GFP_KERNEL);
1698 	if (!gc)
1699 		return;
1700 
1701 	while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1702 		union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1703 		const struct nft_pipapo_field *f;
1704 		unsigned int i, start, rules_fx;
1705 
1706 		start = first_rule;
1707 		rules_fx = rules_f0;
1708 
1709 		nft_pipapo_for_each_field(f, i, m) {
1710 			rulemap[i].to = start;
1711 			rulemap[i].n = rules_fx;
1712 
1713 			if (i < m->field_count - 1) {
1714 				rules_fx = f->mt[start].n;
1715 				start = f->mt[start].to;
1716 			}
1717 		}
1718 
1719 		/* Pick the last field, and its last index */
1720 		f--;
1721 		i--;
1722 		e = f->mt[rulemap[i].to].e;
1723 
1724 		/* synchronous gc never fails, there is no need to set on
1725 		 * NFT_SET_ELEM_DEAD_BIT.
1726 		 */
1727 		if (__nft_set_elem_expired(&e->ext, tstamp)) {
1728 			gc = nft_trans_gc_queue_sync(gc, GFP_KERNEL);
1729 			if (!gc)
1730 				return;
1731 
1732 			nft_pipapo_gc_deactivate(net, set, e);
1733 			pipapo_drop(m, rulemap);
1734 			nft_trans_gc_elem_add(gc, e);
1735 
1736 			/* And check again current first rule, which is now the
1737 			 * first we haven't checked.
1738 			 */
1739 		} else {
1740 			first_rule += rules_f0;
1741 		}
1742 	}
1743 
1744 	gc = nft_trans_gc_catchall_sync(gc);
1745 	if (gc) {
1746 		nft_trans_gc_queue_sync_done(gc);
1747 		priv->last_gc = jiffies;
1748 	}
1749 }
1750 
1751 /**
1752  * pipapo_free_fields() - Free per-field tables contained in matching data
1753  * @m:		Matching data
1754  */
1755 static void pipapo_free_fields(struct nft_pipapo_match *m)
1756 {
1757 	struct nft_pipapo_field *f;
1758 	int i;
1759 
1760 	nft_pipapo_for_each_field(f, i, m) {
1761 		kvfree(f->lt);
1762 		kvfree(f->mt);
1763 	}
1764 }
1765 
1766 static void pipapo_free_match(struct nft_pipapo_match *m)
1767 {
1768 	int i;
1769 
1770 	for_each_possible_cpu(i)
1771 		pipapo_free_scratch(m, i);
1772 
1773 	free_percpu(m->scratch);
1774 	pipapo_free_fields(m);
1775 
1776 	kfree(m);
1777 }
1778 
1779 /**
1780  * pipapo_reclaim_match - RCU callback to free fields from old matching data
1781  * @rcu:	RCU head
1782  */
1783 static void pipapo_reclaim_match(struct rcu_head *rcu)
1784 {
1785 	struct nft_pipapo_match *m;
1786 
1787 	m = container_of(rcu, struct nft_pipapo_match, rcu);
1788 	pipapo_free_match(m);
1789 }
1790 
1791 /**
1792  * nft_pipapo_commit() - Replace lookup data with current working copy
1793  * @set:	nftables API set representation
1794  *
1795  * While at it, check if we should perform garbage collection on the working
1796  * copy before committing it for lookup, and don't replace the table if the
1797  * working copy doesn't have pending changes.
1798  *
1799  * We also need to create a new working copy for subsequent insertions and
1800  * deletions.
1801  */
1802 static void nft_pipapo_commit(struct nft_set *set)
1803 {
1804 	struct nft_pipapo *priv = nft_set_priv(set);
1805 	struct nft_pipapo_match *old;
1806 
1807 	if (!priv->clone)
1808 		return;
1809 
1810 	if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1811 		pipapo_gc(set, priv->clone);
1812 
1813 	old = rcu_replace_pointer(priv->match, priv->clone,
1814 				  nft_pipapo_transaction_mutex_held(set));
1815 	priv->clone = NULL;
1816 
1817 	if (old)
1818 		call_rcu(&old->rcu, pipapo_reclaim_match);
1819 }
1820 
1821 static void nft_pipapo_abort(const struct nft_set *set)
1822 {
1823 	struct nft_pipapo *priv = nft_set_priv(set);
1824 
1825 	if (!priv->clone)
1826 		return;
1827 	pipapo_free_match(priv->clone);
1828 	priv->clone = NULL;
1829 }
1830 
1831 /**
1832  * nft_pipapo_activate() - Mark element reference as active given key, commit
1833  * @net:	Network namespace
1834  * @set:	nftables API set representation
1835  * @elem_priv:	nftables API element representation containing key data
1836  *
1837  * On insertion, elements are added to a copy of the matching data currently
1838  * in use for lookups, and not directly inserted into current lookup data. Both
1839  * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1840  * element, hence we can't purpose either one as a real commit operation.
1841  */
1842 static void nft_pipapo_activate(const struct net *net,
1843 				const struct nft_set *set,
1844 				struct nft_elem_priv *elem_priv)
1845 {
1846 	struct nft_pipapo_elem *e = nft_elem_priv_cast(elem_priv);
1847 
1848 	nft_clear(net, &e->ext);
1849 }
1850 
1851 /**
1852  * nft_pipapo_deactivate() - Search for element and make it inactive
1853  * @net:	Network namespace
1854  * @set:	nftables API set representation
1855  * @elem:	nftables API element representation containing key data
1856  *
1857  * Return: deactivated element if found, NULL otherwise.
1858  */
1859 static struct nft_elem_priv *
1860 nft_pipapo_deactivate(const struct net *net, const struct nft_set *set,
1861 		      const struct nft_set_elem *elem)
1862 {
1863 	struct nft_pipapo_match *m = pipapo_maybe_clone(set);
1864 	struct nft_pipapo_elem *e;
1865 
1866 	/* removal must occur on priv->clone, if we are low on memory
1867 	 * we have no choice and must fail the removal request.
1868 	 */
1869 	if (!m)
1870 		return NULL;
1871 
1872 	e = pipapo_get(m, (const u8 *)elem->key.val.data,
1873 		       nft_genmask_next(net), nft_net_tstamp(net));
1874 	if (!e)
1875 		return NULL;
1876 
1877 	nft_set_elem_change_active(net, set, &e->ext);
1878 
1879 	return &e->priv;
1880 }
1881 
1882 /**
1883  * nft_pipapo_flush() - make element inactive
1884  * @net:	Network namespace
1885  * @set:	nftables API set representation
1886  * @elem_priv:	nftables API element representation containing key data
1887  *
1888  * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1889  * different interface, and it's also called once for each element in a set
1890  * being flushed, so we can't implement, strictly speaking, a flush operation,
1891  * which would otherwise be as simple as allocating an empty copy of the
1892  * matching data.
1893  *
1894  * Note that we could in theory do that, mark the set as flushed, and ignore
1895  * subsequent calls, but we would leak all the elements after the first one,
1896  * because they wouldn't then be freed as result of API calls.
1897  *
1898  * Return: true if element was found and deactivated.
1899  */
1900 static void nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1901 			     struct nft_elem_priv *elem_priv)
1902 {
1903 	struct nft_pipapo_elem *e = nft_elem_priv_cast(elem_priv);
1904 
1905 	nft_set_elem_change_active(net, set, &e->ext);
1906 }
1907 
1908 /**
1909  * pipapo_get_boundaries() - Get byte interval for associated rules
1910  * @f:		Field including lookup table
1911  * @first_rule:	First rule (lowest index)
1912  * @rule_count:	Number of associated rules
1913  * @left:	Byte expression for left boundary (start of range)
1914  * @right:	Byte expression for right boundary (end of range)
1915  *
1916  * Given the first rule and amount of rules that originated from the same entry,
1917  * build the original range associated with the entry, and calculate the length
1918  * of the originating netmask.
1919  *
1920  * In pictures:
1921  *
1922  *                     bucket
1923  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1924  *        0                                                   1,2
1925  *        1   1,2
1926  *        2                                           1,2
1927  *        3                                   1,2
1928  *        4   1,2
1929  *        5        1   2
1930  *        6   1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1931  *        7   1,2 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
1932  *
1933  * this is the lookup table corresponding to the IPv4 range
1934  * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1935  * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1936  *
1937  * This function fills @left and @right with the byte values of the leftmost
1938  * and rightmost bucket indices for the lowest and highest rule indices,
1939  * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1940  * nibbles:
1941  *   left:  < 12, 0, 10, 8, 0, 1, 0, 0 >
1942  *   right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1943  * corresponding to bytes:
1944  *   left:  < 192, 168, 1, 0 >
1945  *   right: < 192, 168, 2, 1 >
1946  * with mask length irrelevant here, unused on return, as the range is already
1947  * defined by its start and end points. The mask length is relevant for a single
1948  * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1949  * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1950  * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1951  * between leftmost and rightmost bucket indices for each group, would be 24.
1952  *
1953  * Return: mask length, in bits.
1954  */
1955 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1956 				 int rule_count, u8 *left, u8 *right)
1957 {
1958 	int g, mask_len = 0, bit_offset = 0;
1959 	u8 *l = left, *r = right;
1960 
1961 	for (g = 0; g < f->groups; g++) {
1962 		int b, x0, x1;
1963 
1964 		x0 = -1;
1965 		x1 = -1;
1966 		for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1967 			unsigned long *pos;
1968 
1969 			pos = NFT_PIPAPO_LT_ALIGN(f->lt) +
1970 			      (g * NFT_PIPAPO_BUCKETS(f->bb) + b) * f->bsize;
1971 			if (test_bit(first_rule, pos) && x0 == -1)
1972 				x0 = b;
1973 			if (test_bit(first_rule + rule_count - 1, pos))
1974 				x1 = b;
1975 		}
1976 
1977 		*l |= x0 << (BITS_PER_BYTE - f->bb - bit_offset);
1978 		*r |= x1 << (BITS_PER_BYTE - f->bb - bit_offset);
1979 
1980 		bit_offset += f->bb;
1981 		if (bit_offset >= BITS_PER_BYTE) {
1982 			bit_offset %= BITS_PER_BYTE;
1983 			l++;
1984 			r++;
1985 		}
1986 
1987 		if (x1 - x0 == 0)
1988 			mask_len += 4;
1989 		else if (x1 - x0 == 1)
1990 			mask_len += 3;
1991 		else if (x1 - x0 == 3)
1992 			mask_len += 2;
1993 		else if (x1 - x0 == 7)
1994 			mask_len += 1;
1995 	}
1996 
1997 	return mask_len;
1998 }
1999 
2000 /**
2001  * pipapo_match_field() - Match rules against byte ranges
2002  * @f:		Field including the lookup table
2003  * @first_rule:	First of associated rules originating from same entry
2004  * @rule_count:	Amount of associated rules
2005  * @start:	Start of range to be matched
2006  * @end:	End of range to be matched
2007  *
2008  * Return: true on match, false otherwise.
2009  */
2010 static bool pipapo_match_field(struct nft_pipapo_field *f,
2011 			       int first_rule, int rule_count,
2012 			       const u8 *start, const u8 *end)
2013 {
2014 	u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
2015 	u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
2016 
2017 	pipapo_get_boundaries(f, first_rule, rule_count, left, right);
2018 
2019 	return !memcmp(start, left,
2020 		       f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) &&
2021 	       !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
2022 }
2023 
2024 /**
2025  * nft_pipapo_remove() - Remove element given key, commit
2026  * @net:	Network namespace
2027  * @set:	nftables API set representation
2028  * @elem_priv:	nftables API element representation containing key data
2029  *
2030  * Similarly to nft_pipapo_activate(), this is used as commit operation by the
2031  * API, but it's called once per element in the pending transaction, so we can't
2032  * implement this as a single commit operation. Closest we can get is to remove
2033  * the matched element here, if any, and commit the updated matching data.
2034  */
2035 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
2036 			      struct nft_elem_priv *elem_priv)
2037 {
2038 	struct nft_pipapo *priv = nft_set_priv(set);
2039 	struct nft_pipapo_match *m = priv->clone;
2040 	unsigned int rules_f0, first_rule = 0;
2041 	struct nft_pipapo_elem *e;
2042 	const u8 *data;
2043 
2044 	e = nft_elem_priv_cast(elem_priv);
2045 	data = (const u8 *)nft_set_ext_key(&e->ext);
2046 
2047 	while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
2048 		union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
2049 		const u8 *match_start, *match_end;
2050 		struct nft_pipapo_field *f;
2051 		int i, start, rules_fx;
2052 
2053 		match_start = data;
2054 
2055 		if (nft_set_ext_exists(&e->ext, NFT_SET_EXT_KEY_END))
2056 			match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
2057 		else
2058 			match_end = data;
2059 
2060 		start = first_rule;
2061 		rules_fx = rules_f0;
2062 
2063 		nft_pipapo_for_each_field(f, i, m) {
2064 			bool last = i == m->field_count - 1;
2065 
2066 			if (!pipapo_match_field(f, start, rules_fx,
2067 						match_start, match_end))
2068 				break;
2069 
2070 			rulemap[i].to = start;
2071 			rulemap[i].n = rules_fx;
2072 
2073 			rules_fx = f->mt[start].n;
2074 			start = f->mt[start].to;
2075 
2076 			match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2077 			match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2078 
2079 			if (last && f->mt[rulemap[i].to].e == e) {
2080 				pipapo_drop(m, rulemap);
2081 				return;
2082 			}
2083 		}
2084 
2085 		first_rule += rules_f0;
2086 	}
2087 
2088 	WARN_ON_ONCE(1); /* elem_priv not found */
2089 }
2090 
2091 /**
2092  * nft_pipapo_do_walk() - Walk over elements in m
2093  * @ctx:	nftables API context
2094  * @set:	nftables API set representation
2095  * @m:		matching data pointing to key mapping array
2096  * @iter:	Iterator
2097  *
2098  * As elements are referenced in the mapping array for the last field, directly
2099  * scan that array: there's no need to follow rule mappings from the first
2100  * field. @m is protected either by RCU read lock or by transaction mutex.
2101  */
2102 static void nft_pipapo_do_walk(const struct nft_ctx *ctx, struct nft_set *set,
2103 			       const struct nft_pipapo_match *m,
2104 			       struct nft_set_iter *iter)
2105 {
2106 	const struct nft_pipapo_field *f;
2107 	unsigned int i, r;
2108 
2109 	for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2110 		;
2111 
2112 	for (r = 0; r < f->rules; r++) {
2113 		struct nft_pipapo_elem *e;
2114 
2115 		if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2116 			continue;
2117 
2118 		if (iter->count < iter->skip)
2119 			goto cont;
2120 
2121 		e = f->mt[r].e;
2122 
2123 		iter->err = iter->fn(ctx, set, iter, &e->priv);
2124 		if (iter->err < 0)
2125 			return;
2126 
2127 cont:
2128 		iter->count++;
2129 	}
2130 }
2131 
2132 /**
2133  * nft_pipapo_walk() - Walk over elements
2134  * @ctx:	nftables API context
2135  * @set:	nftables API set representation
2136  * @iter:	Iterator
2137  *
2138  * Test if destructive action is needed or not, clone active backend if needed
2139  * and call the real function to work on the data.
2140  */
2141 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
2142 			    struct nft_set_iter *iter)
2143 {
2144 	struct nft_pipapo *priv = nft_set_priv(set);
2145 	const struct nft_pipapo_match *m;
2146 
2147 	switch (iter->type) {
2148 	case NFT_ITER_UPDATE:
2149 		m = pipapo_maybe_clone(set);
2150 		if (!m) {
2151 			iter->err = -ENOMEM;
2152 			return;
2153 		}
2154 
2155 		nft_pipapo_do_walk(ctx, set, m, iter);
2156 		break;
2157 	case NFT_ITER_READ:
2158 		rcu_read_lock();
2159 		m = rcu_dereference(priv->match);
2160 		nft_pipapo_do_walk(ctx, set, m, iter);
2161 		rcu_read_unlock();
2162 		break;
2163 	default:
2164 		iter->err = -EINVAL;
2165 		WARN_ON_ONCE(1);
2166 		break;
2167 	}
2168 }
2169 
2170 /**
2171  * nft_pipapo_privsize() - Return the size of private data for the set
2172  * @nla:	netlink attributes, ignored as size doesn't depend on them
2173  * @desc:	Set description, ignored as size doesn't depend on it
2174  *
2175  * Return: size of private data for this set implementation, in bytes
2176  */
2177 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
2178 			       const struct nft_set_desc *desc)
2179 {
2180 	return sizeof(struct nft_pipapo);
2181 }
2182 
2183 /**
2184  * nft_pipapo_estimate() - Set size, space and lookup complexity
2185  * @desc:	Set description, element count and field description used
2186  * @features:	Flags: NFT_SET_INTERVAL needs to be there
2187  * @est:	Storage for estimation data
2188  *
2189  * Return: true if set description is compatible, false otherwise
2190  */
2191 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
2192 				struct nft_set_estimate *est)
2193 {
2194 	if (!(features & NFT_SET_INTERVAL) ||
2195 	    desc->field_count < NFT_PIPAPO_MIN_FIELDS)
2196 		return false;
2197 
2198 	est->size = pipapo_estimate_size(desc);
2199 	if (!est->size)
2200 		return false;
2201 
2202 	est->lookup = NFT_SET_CLASS_O_LOG_N;
2203 
2204 	est->space = NFT_SET_CLASS_O_N;
2205 
2206 	return true;
2207 }
2208 
2209 /**
2210  * nft_pipapo_init() - Initialise data for a set instance
2211  * @set:	nftables API set representation
2212  * @desc:	Set description
2213  * @nla:	netlink attributes
2214  *
2215  * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
2216  * attributes, initialise internal set parameters, current instance of matching
2217  * data and a copy for subsequent insertions.
2218  *
2219  * Return: 0 on success, negative error code on failure.
2220  */
2221 static int nft_pipapo_init(const struct nft_set *set,
2222 			   const struct nft_set_desc *desc,
2223 			   const struct nlattr * const nla[])
2224 {
2225 	struct nft_pipapo *priv = nft_set_priv(set);
2226 	struct nft_pipapo_match *m;
2227 	struct nft_pipapo_field *f;
2228 	int err, i, field_count;
2229 
2230 	BUILD_BUG_ON(offsetof(struct nft_pipapo_elem, priv) != 0);
2231 
2232 	field_count = desc->field_count ? : 1;
2233 
2234 	BUILD_BUG_ON(NFT_PIPAPO_MAX_FIELDS > 255);
2235 	BUILD_BUG_ON(NFT_PIPAPO_MAX_FIELDS != NFT_REG32_COUNT);
2236 
2237 	if (field_count > NFT_PIPAPO_MAX_FIELDS)
2238 		return -EINVAL;
2239 
2240 	m = kmalloc(struct_size(m, f, field_count), GFP_KERNEL);
2241 	if (!m)
2242 		return -ENOMEM;
2243 
2244 	m->field_count = field_count;
2245 	m->bsize_max = 0;
2246 
2247 	m->scratch = alloc_percpu(struct nft_pipapo_scratch *);
2248 	if (!m->scratch) {
2249 		err = -ENOMEM;
2250 		goto out_scratch;
2251 	}
2252 	for_each_possible_cpu(i)
2253 		*per_cpu_ptr(m->scratch, i) = NULL;
2254 
2255 	rcu_head_init(&m->rcu);
2256 
2257 	nft_pipapo_for_each_field(f, i, m) {
2258 		unsigned int len = desc->field_len[i] ? : set->klen;
2259 
2260 		/* f->groups is u8 */
2261 		BUILD_BUG_ON((NFT_PIPAPO_MAX_BYTES *
2262 			      BITS_PER_BYTE / NFT_PIPAPO_GROUP_BITS_LARGE_SET) >= 256);
2263 
2264 		f->bb = NFT_PIPAPO_GROUP_BITS_INIT;
2265 		f->groups = len * NFT_PIPAPO_GROUPS_PER_BYTE(f);
2266 
2267 		priv->width += round_up(len, sizeof(u32));
2268 
2269 		f->bsize = 0;
2270 		f->rules = 0;
2271 		f->rules_alloc = 0;
2272 		f->lt = NULL;
2273 		f->mt = NULL;
2274 	}
2275 
2276 	rcu_assign_pointer(priv->match, m);
2277 
2278 	return 0;
2279 
2280 out_scratch:
2281 	kfree(m);
2282 
2283 	return err;
2284 }
2285 
2286 /**
2287  * nft_set_pipapo_match_destroy() - Destroy elements from key mapping array
2288  * @ctx:	context
2289  * @set:	nftables API set representation
2290  * @m:		matching data pointing to key mapping array
2291  */
2292 static void nft_set_pipapo_match_destroy(const struct nft_ctx *ctx,
2293 					 const struct nft_set *set,
2294 					 struct nft_pipapo_match *m)
2295 {
2296 	struct nft_pipapo_field *f;
2297 	unsigned int i, r;
2298 
2299 	for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2300 		;
2301 
2302 	for (r = 0; r < f->rules; r++) {
2303 		struct nft_pipapo_elem *e;
2304 
2305 		if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2306 			continue;
2307 
2308 		e = f->mt[r].e;
2309 
2310 		nf_tables_set_elem_destroy(ctx, set, &e->priv);
2311 	}
2312 }
2313 
2314 /**
2315  * nft_pipapo_destroy() - Free private data for set and all committed elements
2316  * @ctx:	context
2317  * @set:	nftables API set representation
2318  */
2319 static void nft_pipapo_destroy(const struct nft_ctx *ctx,
2320 			       const struct nft_set *set)
2321 {
2322 	struct nft_pipapo *priv = nft_set_priv(set);
2323 	struct nft_pipapo_match *m;
2324 
2325 	m = rcu_dereference_protected(priv->match, true);
2326 
2327 	if (priv->clone) {
2328 		nft_set_pipapo_match_destroy(ctx, set, priv->clone);
2329 		pipapo_free_match(priv->clone);
2330 		priv->clone = NULL;
2331 	} else {
2332 		nft_set_pipapo_match_destroy(ctx, set, m);
2333 	}
2334 
2335 	pipapo_free_match(m);
2336 }
2337 
2338 /**
2339  * nft_pipapo_gc_init() - Initialise garbage collection
2340  * @set:	nftables API set representation
2341  *
2342  * Instead of actually setting up a periodic work for garbage collection, as
2343  * this operation requires a swap of matching data with the working copy, we'll
2344  * do that opportunistically with other commit operations if the interval is
2345  * elapsed, so we just need to set the current jiffies timestamp here.
2346  */
2347 static void nft_pipapo_gc_init(const struct nft_set *set)
2348 {
2349 	struct nft_pipapo *priv = nft_set_priv(set);
2350 
2351 	priv->last_gc = jiffies;
2352 }
2353 
2354 const struct nft_set_type nft_set_pipapo_type = {
2355 	.features	= NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2356 			  NFT_SET_TIMEOUT,
2357 	.ops		= {
2358 		.lookup		= nft_pipapo_lookup,
2359 		.insert		= nft_pipapo_insert,
2360 		.activate	= nft_pipapo_activate,
2361 		.deactivate	= nft_pipapo_deactivate,
2362 		.flush		= nft_pipapo_flush,
2363 		.remove		= nft_pipapo_remove,
2364 		.walk		= nft_pipapo_walk,
2365 		.get		= nft_pipapo_get,
2366 		.privsize	= nft_pipapo_privsize,
2367 		.estimate	= nft_pipapo_estimate,
2368 		.init		= nft_pipapo_init,
2369 		.destroy	= nft_pipapo_destroy,
2370 		.gc_init	= nft_pipapo_gc_init,
2371 		.commit		= nft_pipapo_commit,
2372 		.abort		= nft_pipapo_abort,
2373 		.elemsize	= offsetof(struct nft_pipapo_elem, ext),
2374 	},
2375 };
2376 
2377 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2378 const struct nft_set_type nft_set_pipapo_avx2_type = {
2379 	.features	= NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2380 			  NFT_SET_TIMEOUT,
2381 	.ops		= {
2382 		.lookup		= nft_pipapo_avx2_lookup,
2383 		.insert		= nft_pipapo_insert,
2384 		.activate	= nft_pipapo_activate,
2385 		.deactivate	= nft_pipapo_deactivate,
2386 		.flush		= nft_pipapo_flush,
2387 		.remove		= nft_pipapo_remove,
2388 		.walk		= nft_pipapo_walk,
2389 		.get		= nft_pipapo_get,
2390 		.privsize	= nft_pipapo_privsize,
2391 		.estimate	= nft_pipapo_avx2_estimate,
2392 		.init		= nft_pipapo_init,
2393 		.destroy	= nft_pipapo_destroy,
2394 		.gc_init	= nft_pipapo_gc_init,
2395 		.commit		= nft_pipapo_commit,
2396 		.abort		= nft_pipapo_abort,
2397 		.elemsize	= offsetof(struct nft_pipapo_elem, ext),
2398 	},
2399 };
2400 #endif
2401