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, start: i, nbits: 1);
384	return i;
385	}
386
387	ret = 0;
388
389	bitmap_set(map: dst, start: mt[i].to, nbits: 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, dst: res_map, data);
451	else
452	pipapo_and_field_buckets_4bit(f, dst: 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(map: res_map, len: f->bsize, rules: f->rules, dst: fill_map, mt: f->mt,
466	match_only: 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, data: (const u8 *)key, genmask: 0, tstamp: 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, data: (const u8 *)elem->key.val.data,
606	genmask: nft_genmask_cur(net), tstamp: get_jiffies_64());
607	if (!e)
608	return ERR_PTR(error: -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(addr: 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(groups: f->groups, bb: f->bb, bsize: 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(addr: new_lt);
764	return err;
765	}
766
767	if (new_lt) {
768	f->bsize = new_bucket_size;
769	f->lt = new_lt;
770	kvfree(addr: 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, bsize: 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, bsize: 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(old_groups: f->groups, bsize: 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(old_groups: f->groups, bsize: 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(addr: 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, old_rules: f->rules, 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, v: 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, v: 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(p: tmp, q: end, size: 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(p: base, q: end, size: bytes) <= 0) {
1135	int err;
1136
1137	step = 0;
1138	while (pipapo_step_diff(base, step, len: bytes)) {
1139	if (pipapo_step_after_end(base, end, step, len: bytes))
1140	break;
1141
1142	step++;
1143	if (step >= len) {
1144	if (!masks) {
1145	err = pipapo_insert(f, k: base, mask_bits: 0);
1146	if (err < 0)
1147	return err;
1148	masks = 1;
1149	}
1150	goto out;
1151	}
1152	}
1153
1154	err = pipapo_insert(f, k: base, mask_bits: len - step);
1155
1156	if (err < 0)
1157	return err;
1158
1159	masks++;
1160	pipapo_base_sum(base, step, len: 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(addr: 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(m: clone, cpu: 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(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(old: 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: 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, id: 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, data: 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(ext: &dup->ext);
1315	if (nft_set_ext_exists(ext: &dup->ext, id: NFT_SET_EXT_KEY_END))
1316	dup_end = nft_set_ext_key_end(ext: &dup->ext);
1317	else
1318	dup_end = dup_key;
1319
1320	if (!memcmp(p: start, q: dup_key->data, size: set->klen) &&
1321	!memcmp(p: end, q: dup_end->data, size: set->klen)) {
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, data: end, genmask: 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(p: start_p, q: end_p,
1350	size: 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(p: start, q: end,
1366	size: f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1367	if (!ret)
1368	ret = pipapo_insert(f, k: start, mask_bits: f->groups * f->bb);
1369	else
1370	ret = pipapo_expand(f, start, end, len: 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(clone: 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(priv: elem->priv);
1397	*elem_priv = &e->priv;
1398
1399	pipapo_map(m, map: 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(clone: new, bsize_max: old->bsize_max))
1431	goto out_scratch_realloc;
1432
1433	rcu_head_init(rhp: &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(groups: src->groups, bb: src->bb, bsize: 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(addr: dst->lt);
1483	out_lt:
1484	for (dst--; i > 0; i--) {
1485	kvfree(addr: dst->mt);
1486	kvfree(addr: dst->lt);
1487	dst--;
1488	}
1489	out_scratch_realloc:
1490	for_each_possible_cpu(i)
1491	pipapo_free_scratch(m: new, cpu: i);
1492	out_scratch:
1493	free_percpu(pdata: new->scratch);
1494	kfree(objp: 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(dst: pos, src: pos, first: rulemap[i].to,
1655	cut: rulemap[i].n,
1656	nbits: f->bsize * BITS_PER_LONG);
1657
1658	pos += f->bsize;
1659	}
1660	}
1661
1662	pipapo_unmap(mt: f->mt, rules: f->rules, start: rulemap[i].to, n: rulemap[i].n,
1663	to_offset: rulemap[i + 1].n, is_last: i == m->field_count - 1);
1664	if (pipapo_resize(f, old_rules: f->rules, 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, elem_priv: &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(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, gc_seq: 0, GFP_KERNEL);
1698	if (!gc)
1699	return;
1700
1701	while ((rules_f0 = pipapo_rules_same_key(f: m->f, first: 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(ext: &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, priv: 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(trans: 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(addr: f->lt);
1762	kvfree(addr: 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, cpu: i);
1772
1773	free_percpu(pdata: m->scratch);
1774	pipapo_free_fields(m);
1775
1776	kfree(objp: 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, m: 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(head: &old->rcu, func: 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(m: 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(priv: 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, data: (const u8 *)elem->key.val.data,
1873	genmask: nft_genmask_next(net), tstamp: nft_net_tstamp(net));
1874	if (!e)
1875	return NULL;
1876
1877	nft_set_elem_change_active(net, set, ext: &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(priv: elem_priv);
1904
1905	nft_set_elem_change_active(net, set, ext: &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(p: start, q: left,
2020	size: f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) &&
2021	!memcmp(p: end, q: right, size: 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(priv: elem_priv);
2045	data = (const u8 *)nft_set_ext_key(ext: &e->ext);
2046
2047	while ((rules_f0 = pipapo_rules_same_key(f: m->f, first: 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(ext: &e->ext, id: NFT_SET_EXT_KEY_END))
2056	match_end = (const u8 *)nft_set_ext_key_end(ext: &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, first_rule: start, rule_count: rules_fx,
2067	start: match_start, end: 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(rhp: &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(objp: 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, elem_priv: &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, m: priv->clone);
2329	pipapo_free_match(m: 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