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