1 // SPDX-License-Identifier: GPL-2.0-only
3 /* PIPAPO: PIle PAcket POlicies: set for arbitrary concatenations of ranges
5 * Copyright (c) 2019-2020 Red Hat GmbH
7 * Author: Stefano Brivio <sbrivio@redhat.com>
11 * DOC: Theory of Operation
17 * Match packet bytes against entries composed of ranged or non-ranged packet
18 * field specifiers, mapping them to arbitrary references. For example:
23 * | [net],[port],[net]... => [reference]
24 * entries [net],[port],[net]... => [reference]
25 * | [net],[port],[net]... => [reference]
28 * where [net] fields can be IP ranges or netmasks, and [port] fields are port
29 * ranges. Arbitrary packet fields can be matched.
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].
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.
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:
48 * and a packet with source port:
50 * first and second groups match, but the third doesn't. We conclude that the
51 * packet doesn't match the given entry.
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.
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.
67 * The mapping array for the last field maps to the desired references.
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
73 * A stand-alone, reference implementation, also including notes about possible
74 * future optimisations, is available at:
75 * https://pipapo.lameexcu.se/
80 * - For each packet field:
82 * - divide the b packet bits we want to classify into groups of size t,
83 * obtaining ceil(b / t) groups
85 * Example: match on destination IP address, with t = 4: 32 bits, 8 groups
88 * - allocate a lookup table with one column ("bucket") for each possible
89 * value of a group, and with one row for each group
91 * Example: 8 groups, 2^4 buckets:
96 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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().
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
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
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 > >
128 * these bits are set in the lookup table:
133 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
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().
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.
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):
157 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
167 * and lookup table #1 for field 1 with:
168 * - rule #0: 1024 mapping to buckets
170 * - rule #1: 2048 mapping to buckets
176 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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):
188 * rule indices in current field: 0 1 2
189 * map to rules in next field: 0 1 1
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
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.
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:
205 * rule indices in last field: 0 1
206 * map to elements: 0x66 0x42
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().
216 * - For each packet field:
218 * - start with an all-ones result bitmap (res_map in pipapo_lookup())
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
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:
233 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
235 * result bitmap is now: 0xff & 0x6 [bucket 12] = 0x6
238 * result bitmap is now: 0x6 & 0x6 [bucket 0] = 0x6
241 * result bitmap is now: 0x6 & 0x6 [bucket 10] = 0x6
244 * result bitmap is now: 0x6 & 0x6 [bucket 8] = 0x6
247 * result bitmap is now: 0x6 & 0x7 [bucket 0] = 0x6
250 * result bitmap is now: 0x6 & 0x2 [bucket 1] = 0x2
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
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
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
264 * Example: with mapping table from insertion examples, with the current
265 * result bitmap from the previous example, 0x02:
269 * rule indices in current field: 0 1 2
270 * map to rules in next field: 0 1 1
272 * the new result bitmap will be 0x02: rule 1 was set, and rule 1 will be
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:
283 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
289 * operations are: 0x2 & 0x3 [bucket 0] & 0x3 [bucket 0] & 0x2 [bucket 5]
290 * & 0x3 [bucket 0], resulting bitmap is 0x2.
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
295 * Example: 0x2 resulting bitmap from 192.168.1.5:2048, mapping array for
296 * last field from insertion example:
300 * rule indices in last field: 0 1
301 * map to elements: 0x66 0x42
303 * the matching element is at 0x42.
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
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
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
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>
342 #include "nft_set_pipapo_avx2.h"
343 #include "nft_set_pipapo.h"
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
354 * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
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.
360 * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
362 int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
363 const union nft_pipapo_map_bucket *mt, bool match_only)
365 unsigned long bitset;
368 for (k = 0; k < len; k++) {
371 unsigned long t = bitset & -bitset;
372 int r = __builtin_ctzl(bitset);
373 int i = k * BITS_PER_LONG + r;
375 if (unlikely(i >= rules)) {
381 bitmap_clear(map, i, 1);
387 bitmap_set(dst, mt[i].to, mt[i].n);
398 * nft_pipapo_lookup() - Lookup function
399 * @net: Network namespace
400 * @set: nftables API set representation
401 * @key: nftables API element representation containing key data
402 * @ext: nftables API extension pointer, filled with matching reference
404 * For more details, see DOC: Theory of Operation.
406 * Return: true on match, false otherwise.
408 bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
409 const u32 *key, const struct nft_set_ext **ext)
411 struct nft_pipapo *priv = nft_set_priv(set);
412 struct nft_pipapo_scratch *scratch;
413 unsigned long *res_map, *fill_map;
414 u8 genmask = nft_genmask_cur(net);
415 const struct nft_pipapo_match *m;
416 const struct nft_pipapo_field *f;
417 const u8 *rp = (const u8 *)key;
423 m = rcu_dereference(priv->match);
425 if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
428 scratch = *raw_cpu_ptr(m->scratch);
430 map_index = scratch->map_index;
432 res_map = scratch->map + (map_index ? m->bsize_max : 0);
433 fill_map = scratch->map + (map_index ? 0 : m->bsize_max);
435 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
437 nft_pipapo_for_each_field(f, i, m) {
438 bool last = i == m->field_count - 1;
441 /* For each bit group: select lookup table bucket depending on
442 * packet bytes value, then AND bucket value
444 if (likely(f->bb == 8))
445 pipapo_and_field_buckets_8bit(f, res_map, rp);
447 pipapo_and_field_buckets_4bit(f, res_map, rp);
448 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
450 rp += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f);
452 /* Now populate the bitmap for the next field, unless this is
453 * the last field, in which case return the matched 'ext'
456 * Now res_map contains the matching bitmap, and fill_map is the
457 * bitmap for the next field.
460 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
463 scratch->map_index = map_index;
470 *ext = &f->mt[b].e->ext;
471 if (unlikely(nft_set_elem_expired(*ext) ||
472 !nft_set_elem_active(*ext, genmask)))
475 /* Last field: we're just returning the key without
476 * filling the initial bitmap for the next field, so the
477 * current inactive bitmap is clean and can be reused as
478 * *next* bitmap (not initial) for the next packet.
480 scratch->map_index = map_index;
486 /* Swap bitmap indices: res_map is the initial bitmap for the
487 * next field, and fill_map is guaranteed to be all-zeroes at
490 map_index = !map_index;
491 swap(res_map, fill_map);
493 rp += NFT_PIPAPO_GROUPS_PADDING(f);
502 * pipapo_get() - Get matching element reference given key data
503 * @net: Network namespace
504 * @set: nftables API set representation
505 * @data: Key data to be matched against existing elements
506 * @genmask: If set, check that element is active in given genmask
507 * @tstamp: timestamp to check for expired elements
509 * This is essentially the same as the lookup function, except that it matches
510 * key data against the uncommitted copy and doesn't use preallocated maps for
513 * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
515 static struct nft_pipapo_elem *pipapo_get(const struct net *net,
516 const struct nft_set *set,
517 const u8 *data, u8 genmask,
520 struct nft_pipapo_elem *ret = ERR_PTR(-ENOENT);
521 struct nft_pipapo *priv = nft_set_priv(set);
522 unsigned long *res_map, *fill_map = NULL;
523 const struct nft_pipapo_match *m;
524 const struct nft_pipapo_field *f;
529 res_map = kmalloc_array(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
531 ret = ERR_PTR(-ENOMEM);
535 fill_map = kcalloc(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
537 ret = ERR_PTR(-ENOMEM);
541 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
543 nft_pipapo_for_each_field(f, i, m) {
544 bool last = i == m->field_count - 1;
547 /* For each bit group: select lookup table bucket depending on
548 * packet bytes value, then AND bucket value
551 pipapo_and_field_buckets_8bit(f, res_map, data);
553 pipapo_and_field_buckets_4bit(f, res_map, data);
557 data += f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f);
559 /* Now populate the bitmap for the next field, unless this is
560 * the last field, in which case return the matched 'ext'
563 * Now res_map contains the matching bitmap, and fill_map is the
564 * bitmap for the next field.
567 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
573 if (__nft_set_elem_expired(&f->mt[b].e->ext, tstamp))
576 !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
583 data += NFT_PIPAPO_GROUPS_PADDING(f);
585 /* Swap bitmap indices: fill_map will be the initial bitmap for
586 * the next field (i.e. the new res_map), and res_map is
587 * guaranteed to be all-zeroes at this point, ready to be filled
588 * according to the next mapping table.
590 swap(res_map, fill_map);
600 * nft_pipapo_get() - Get matching element reference given key data
601 * @net: Network namespace
602 * @set: nftables API set representation
603 * @elem: nftables API element representation containing key data
606 static struct nft_elem_priv *
607 nft_pipapo_get(const struct net *net, const struct nft_set *set,
608 const struct nft_set_elem *elem, unsigned int flags)
610 struct nft_pipapo_elem *e;
612 e = pipapo_get(net, set, (const u8 *)elem->key.val.data,
613 nft_genmask_cur(net), get_jiffies_64());
621 * pipapo_resize() - Resize lookup or mapping table, or both
622 * @f: Field containing lookup and mapping tables
623 * @old_rules: Previous amount of rules in field
624 * @rules: New amount of rules
626 * Increase, decrease or maintain tables size depending on new amount of rules,
627 * and copy data over. In case the new size is smaller, throw away data for
628 * highest-numbered rules.
630 * Return: 0 on success, -ENOMEM on allocation failure.
632 static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
634 long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
635 union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
636 size_t new_bucket_size, copy;
639 new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
640 #ifdef NFT_PIPAPO_ALIGN
641 new_bucket_size = roundup(new_bucket_size,
642 NFT_PIPAPO_ALIGN / sizeof(*new_lt));
645 if (new_bucket_size == f->bsize)
648 if (new_bucket_size > f->bsize)
651 copy = new_bucket_size;
653 new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS(f->bb) *
654 new_bucket_size * sizeof(*new_lt) +
655 NFT_PIPAPO_ALIGN_HEADROOM,
660 new_p = NFT_PIPAPO_LT_ALIGN(new_lt);
661 old_p = NFT_PIPAPO_LT_ALIGN(old_lt);
663 for (group = 0; group < f->groups; group++) {
664 for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS(f->bb); bucket++) {
665 memcpy(new_p, old_p, copy * sizeof(*new_p));
669 if (new_bucket_size > f->bsize)
670 new_p += new_bucket_size - f->bsize;
672 old_p += f->bsize - new_bucket_size;
677 new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
683 memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
684 if (rules > old_rules) {
685 memset(new_mt + old_rules, 0,
686 (rules - old_rules) * sizeof(*new_mt));
690 f->bsize = new_bucket_size;
691 NFT_PIPAPO_LT_ASSIGN(f, new_lt);
702 * pipapo_bucket_set() - Set rule bit in bucket given group and group value
703 * @f: Field containing lookup table
705 * @group: Group index
706 * @v: Value of bit group
708 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
713 pos = NFT_PIPAPO_LT_ALIGN(f->lt);
714 pos += f->bsize * NFT_PIPAPO_BUCKETS(f->bb) * group;
717 __set_bit(rule, pos);
721 * pipapo_lt_4b_to_8b() - Switch lookup table group width from 4 bits to 8 bits
722 * @old_groups: Number of current groups
723 * @bsize: Size of one bucket, in longs
724 * @old_lt: Pointer to the current lookup table
725 * @new_lt: Pointer to the new, pre-allocated lookup table
727 * Each bucket with index b in the new lookup table, belonging to group g, is
728 * filled with the bit intersection between:
729 * - bucket with index given by the upper 4 bits of b, from group g, and
730 * - bucket with index given by the lower 4 bits of b, from group g + 1
732 * That is, given buckets from the new lookup table N(x, y) and the old lookup
733 * table O(x, y), with x bucket index, and y group index:
735 * N(b, g) := O(b / 16, g) & O(b % 16, g + 1)
737 * This ensures equivalence of the matching results on lookup. Two examples in
741 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... 254 255
748 * group 0 / 1 2 3 \ 4 5 6 7 8 9 10 11 12 13 |14 15 |
755 static void pipapo_lt_4b_to_8b(int old_groups, int bsize,
756 unsigned long *old_lt, unsigned long *new_lt)
760 for (g = 0; g < old_groups / 2; g++) {
761 int src_g0 = g * 2, src_g1 = g * 2 + 1;
763 for (b = 0; b < NFT_PIPAPO_BUCKETS(8); b++) {
764 int src_b0 = b / NFT_PIPAPO_BUCKETS(4);
765 int src_b1 = b % NFT_PIPAPO_BUCKETS(4);
766 int src_i0 = src_g0 * NFT_PIPAPO_BUCKETS(4) + src_b0;
767 int src_i1 = src_g1 * NFT_PIPAPO_BUCKETS(4) + src_b1;
769 for (i = 0; i < bsize; i++) {
770 *new_lt = old_lt[src_i0 * bsize + i] &
771 old_lt[src_i1 * bsize + i];
779 * pipapo_lt_8b_to_4b() - Switch lookup table group width from 8 bits to 4 bits
780 * @old_groups: Number of current groups
781 * @bsize: Size of one bucket, in longs
782 * @old_lt: Pointer to the current lookup table
783 * @new_lt: Pointer to the new, pre-allocated lookup table
785 * Each bucket with index b in the new lookup table, belonging to group g, is
786 * filled with the bit union of:
787 * - all the buckets with index such that the upper four bits of the lower byte
788 * equal b, from group g, with g odd
789 * - all the buckets with index such that the lower four bits equal b, from
790 * group g, with g even
792 * That is, given buckets from the new lookup table N(x, y) and the old lookup
793 * table O(x, y), with x bucket index, and y group index:
795 * - with g odd: N(b, g) := U(O(x, g) for each x : x = (b & 0xf0) >> 4)
796 * - with g even: N(b, g) := U(O(x, g) for each x : x = b & 0x0f)
798 * where U() denotes the arbitrary union operation (binary OR of n terms). This
799 * ensures equivalence of the matching results on lookup.
801 static void pipapo_lt_8b_to_4b(int old_groups, int bsize,
802 unsigned long *old_lt, unsigned long *new_lt)
806 memset(new_lt, 0, old_groups * 2 * NFT_PIPAPO_BUCKETS(4) * bsize *
807 sizeof(unsigned long));
809 for (g = 0; g < old_groups * 2; g += 2) {
812 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
813 for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
814 bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
816 if (((bsrc & 0xf0) >> 4) != b)
819 for (i = 0; i < bsize; i++)
820 new_lt[i] |= old_lt[bsrc * bsize + i];
826 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
827 for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
828 bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
830 if ((bsrc & 0x0f) != b)
833 for (i = 0; i < bsize; i++)
834 new_lt[i] |= old_lt[bsrc * bsize + i];
843 * pipapo_lt_bits_adjust() - Adjust group size for lookup table if needed
844 * @f: Field containing lookup table
846 static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
848 unsigned long *new_lt;
852 lt_size = f->groups * NFT_PIPAPO_BUCKETS(f->bb) * f->bsize *
855 if (f->bb == NFT_PIPAPO_GROUP_BITS_SMALL_SET &&
856 lt_size > NFT_PIPAPO_LT_SIZE_HIGH) {
857 groups = f->groups * 2;
858 bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
860 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
862 } else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
863 lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
864 groups = f->groups / 2;
865 bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
867 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
870 /* Don't increase group width if the resulting lookup table size
871 * would exceed the upper size threshold for a "small" set.
873 if (lt_size > NFT_PIPAPO_LT_SIZE_HIGH)
879 new_lt = kvzalloc(lt_size + NFT_PIPAPO_ALIGN_HEADROOM, GFP_KERNEL);
883 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
884 if (f->bb == 4 && bb == 8) {
885 pipapo_lt_4b_to_8b(f->groups, f->bsize,
886 NFT_PIPAPO_LT_ALIGN(f->lt),
887 NFT_PIPAPO_LT_ALIGN(new_lt));
888 } else if (f->bb == 8 && bb == 4) {
889 pipapo_lt_8b_to_4b(f->groups, f->bsize,
890 NFT_PIPAPO_LT_ALIGN(f->lt),
891 NFT_PIPAPO_LT_ALIGN(new_lt));
899 NFT_PIPAPO_LT_ASSIGN(f, new_lt);
903 * pipapo_insert() - Insert new rule in field given input key and mask length
904 * @f: Field containing lookup table
905 * @k: Input key for classification, without nftables padding
906 * @mask_bits: Length of mask; matches field length for non-ranged entry
908 * Insert a new rule reference in lookup buckets corresponding to k and
911 * Return: 1 on success (one rule inserted), negative error code on failure.
913 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
916 int rule = f->rules, group, ret, bit_offset = 0;
918 ret = pipapo_resize(f, f->rules, f->rules + 1);
924 for (group = 0; group < f->groups; group++) {
928 v = k[group / (BITS_PER_BYTE / f->bb)];
929 v &= GENMASK(BITS_PER_BYTE - bit_offset - 1, 0);
930 v >>= (BITS_PER_BYTE - bit_offset) - f->bb;
933 bit_offset %= BITS_PER_BYTE;
935 if (mask_bits >= (group + 1) * f->bb) {
937 pipapo_bucket_set(f, rule, group, v);
938 } else if (mask_bits <= group * f->bb) {
939 /* Completely masked */
940 for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++)
941 pipapo_bucket_set(f, rule, group, i);
943 /* The mask limit falls on this group */
944 mask = GENMASK(f->bb - 1, 0);
945 mask >>= mask_bits - group * f->bb;
946 for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++) {
947 if ((i & ~mask) == (v & ~mask))
948 pipapo_bucket_set(f, rule, group, i);
953 pipapo_lt_bits_adjust(f);
959 * pipapo_step_diff() - Check if setting @step bit in netmask would change it
960 * @base: Mask we are expanding
961 * @step: Step bit for given expansion step
962 * @len: Total length of mask space (set and unset bits), bytes
964 * Convenience function for mask expansion.
966 * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
968 static bool pipapo_step_diff(u8 *base, int step, int len)
970 /* Network order, byte-addressed */
971 #ifdef __BIG_ENDIAN__
972 return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
974 return !(BIT(step % BITS_PER_BYTE) &
975 base[len - 1 - step / BITS_PER_BYTE]);
980 * pipapo_step_after_end() - Check if mask exceeds range end with given step
981 * @base: Mask we are expanding
983 * @step: Step bit for given expansion step, highest bit to be set
984 * @len: Total length of mask space (set and unset bits), bytes
986 * Convenience function for mask expansion.
988 * Return: true if mask exceeds range setting step bits, false otherwise.
990 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
993 u8 tmp[NFT_PIPAPO_MAX_BYTES];
996 memcpy(tmp, base, len);
998 /* Network order, byte-addressed */
999 for (i = 0; i <= step; i++)
1000 #ifdef __BIG_ENDIAN__
1001 tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
1003 tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
1006 return memcmp(tmp, end, len) > 0;
1010 * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
1011 * @base: Netmask base
1012 * @step: Step bit to sum
1013 * @len: Netmask length, bytes
1015 static void pipapo_base_sum(u8 *base, int step, int len)
1020 /* Network order, byte-addressed */
1021 #ifdef __BIG_ENDIAN__
1022 for (i = step / BITS_PER_BYTE; i < len; i++) {
1024 for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
1029 base[i] += 1 << (step % BITS_PER_BYTE);
1039 * pipapo_expand() - Expand to composing netmasks, insert into lookup table
1040 * @f: Field containing lookup table
1041 * @start: Start of range
1042 * @end: End of range
1043 * @len: Length of value in bits
1045 * Expand range to composing netmasks and insert corresponding rule references
1046 * in lookup buckets.
1048 * Return: number of inserted rules on success, negative error code on failure.
1050 static int pipapo_expand(struct nft_pipapo_field *f,
1051 const u8 *start, const u8 *end, int len)
1053 int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
1054 u8 base[NFT_PIPAPO_MAX_BYTES];
1056 memcpy(base, start, bytes);
1057 while (memcmp(base, end, bytes) <= 0) {
1061 while (pipapo_step_diff(base, step, bytes)) {
1062 if (pipapo_step_after_end(base, end, step, bytes))
1068 err = pipapo_insert(f, base, 0);
1077 err = pipapo_insert(f, base, len - step);
1083 pipapo_base_sum(base, step, bytes);
1090 * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1091 * @m: Matching data, including mapping table
1092 * @map: Table of rule maps: array of first rule and amount of rules
1093 * in next field a given rule maps to, for each field
1094 * @e: For last field, nft_set_ext pointer matching rules map to
1096 static void pipapo_map(struct nft_pipapo_match *m,
1097 union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1098 struct nft_pipapo_elem *e)
1100 struct nft_pipapo_field *f;
1103 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1104 for (j = 0; j < map[i].n; j++) {
1105 f->mt[map[i].to + j].to = map[i + 1].to;
1106 f->mt[map[i].to + j].n = map[i + 1].n;
1110 /* Last field: map to ext instead of mapping to next field */
1111 for (j = 0; j < map[i].n; j++)
1112 f->mt[map[i].to + j].e = e;
1116 * pipapo_free_scratch() - Free per-CPU map at original (not aligned) address
1120 static void pipapo_free_scratch(const struct nft_pipapo_match *m, unsigned int cpu)
1122 struct nft_pipapo_scratch *s;
1125 s = *per_cpu_ptr(m->scratch, cpu);
1130 mem -= s->align_off;
1135 * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1136 * @clone: Copy of matching data with pending insertions and deletions
1137 * @bsize_max: Maximum bucket size, scratch maps cover two buckets
1139 * Return: 0 on success, -ENOMEM on failure.
1141 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1142 unsigned long bsize_max)
1146 for_each_possible_cpu(i) {
1147 struct nft_pipapo_scratch *scratch;
1148 #ifdef NFT_PIPAPO_ALIGN
1149 void *scratch_aligned;
1152 scratch = kzalloc_node(struct_size(scratch, map,
1154 NFT_PIPAPO_ALIGN_HEADROOM,
1155 GFP_KERNEL, cpu_to_node(i));
1157 /* On failure, there's no need to undo previous
1158 * allocations: this means that some scratch maps have
1159 * a bigger allocated size now (this is only called on
1160 * insertion), but the extra space won't be used by any
1161 * CPU as new elements are not inserted and m->bsize_max
1167 pipapo_free_scratch(clone, i);
1169 #ifdef NFT_PIPAPO_ALIGN
1170 /* Align &scratch->map (not the struct itself): the extra
1171 * %NFT_PIPAPO_ALIGN_HEADROOM bytes passed to kzalloc_node()
1172 * above guarantee we can waste up to those bytes in order
1173 * to align the map field regardless of its offset within
1176 BUILD_BUG_ON(offsetof(struct nft_pipapo_scratch, map) > NFT_PIPAPO_ALIGN_HEADROOM);
1178 scratch_aligned = NFT_PIPAPO_LT_ALIGN(&scratch->map);
1179 scratch_aligned -= offsetof(struct nft_pipapo_scratch, map);
1180 align_off = scratch_aligned - (void *)scratch;
1182 scratch = scratch_aligned;
1183 scratch->align_off = align_off;
1185 *per_cpu_ptr(clone->scratch, i) = scratch;
1192 * nft_pipapo_insert() - Validate and insert ranged elements
1193 * @net: Network namespace
1194 * @set: nftables API set representation
1195 * @elem: nftables API element representation containing key data
1196 * @elem_priv: Filled with pointer to &struct nft_set_ext in inserted element
1198 * Return: 0 on success, error pointer on failure.
1200 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1201 const struct nft_set_elem *elem,
1202 struct nft_elem_priv **elem_priv)
1204 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1205 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1206 const u8 *start = (const u8 *)elem->key.val.data, *end;
1207 struct nft_pipapo *priv = nft_set_priv(set);
1208 struct nft_pipapo_match *m = priv->clone;
1209 u8 genmask = nft_genmask_next(net);
1210 struct nft_pipapo_elem *e, *dup;
1211 u64 tstamp = nft_net_tstamp(net);
1212 struct nft_pipapo_field *f;
1213 const u8 *start_p, *end_p;
1214 int i, bsize_max, err = 0;
1216 if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END))
1217 end = (const u8 *)nft_set_ext_key_end(ext)->data;
1221 dup = pipapo_get(net, set, start, genmask, tstamp);
1223 /* Check if we already have the same exact entry */
1224 const struct nft_data *dup_key, *dup_end;
1226 dup_key = nft_set_ext_key(&dup->ext);
1227 if (nft_set_ext_exists(&dup->ext, NFT_SET_EXT_KEY_END))
1228 dup_end = nft_set_ext_key_end(&dup->ext);
1232 if (!memcmp(start, dup_key->data, sizeof(*dup_key->data)) &&
1233 !memcmp(end, dup_end->data, sizeof(*dup_end->data))) {
1234 *elem_priv = &dup->priv;
1241 if (PTR_ERR(dup) == -ENOENT) {
1242 /* Look for partially overlapping entries */
1243 dup = pipapo_get(net, set, end, nft_genmask_next(net), tstamp);
1246 if (PTR_ERR(dup) != -ENOENT) {
1248 return PTR_ERR(dup);
1249 *elem_priv = &dup->priv;
1256 nft_pipapo_for_each_field(f, i, m) {
1257 if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
1260 if (memcmp(start_p, end_p,
1261 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) > 0)
1264 start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1265 end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1271 bsize_max = m->bsize_max;
1273 nft_pipapo_for_each_field(f, i, m) {
1276 rulemap[i].to = f->rules;
1278 ret = memcmp(start, end,
1279 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1281 ret = pipapo_insert(f, start, f->groups * f->bb);
1283 ret = pipapo_expand(f, start, end, f->groups * f->bb);
1288 if (f->bsize > bsize_max)
1289 bsize_max = f->bsize;
1293 start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1294 end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1297 if (!*get_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1298 put_cpu_ptr(m->scratch);
1300 err = pipapo_realloc_scratch(m, bsize_max);
1304 m->bsize_max = bsize_max;
1306 put_cpu_ptr(m->scratch);
1309 e = nft_elem_priv_cast(elem->priv);
1310 *elem_priv = &e->priv;
1312 pipapo_map(m, rulemap, e);
1318 * pipapo_clone() - Clone matching data to create new working copy
1319 * @old: Existing matching data
1321 * Return: copy of matching data passed as 'old', error pointer on failure
1323 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1325 struct nft_pipapo_field *dst, *src;
1326 struct nft_pipapo_match *new;
1329 new = kmalloc(struct_size(new, f, old->field_count), GFP_KERNEL);
1331 return ERR_PTR(-ENOMEM);
1333 new->field_count = old->field_count;
1334 new->bsize_max = old->bsize_max;
1336 new->scratch = alloc_percpu(*new->scratch);
1340 for_each_possible_cpu(i)
1341 *per_cpu_ptr(new->scratch, i) = NULL;
1343 if (pipapo_realloc_scratch(new, old->bsize_max))
1344 goto out_scratch_realloc;
1346 rcu_head_init(&new->rcu);
1351 for (i = 0; i < old->field_count; i++) {
1352 unsigned long *new_lt;
1354 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1356 new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) *
1357 src->bsize * sizeof(*dst->lt) +
1358 NFT_PIPAPO_ALIGN_HEADROOM,
1363 NFT_PIPAPO_LT_ASSIGN(dst, new_lt);
1365 memcpy(NFT_PIPAPO_LT_ALIGN(new_lt),
1366 NFT_PIPAPO_LT_ALIGN(src->lt),
1367 src->bsize * sizeof(*dst->lt) *
1368 src->groups * NFT_PIPAPO_BUCKETS(src->bb));
1370 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
1374 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1384 for (dst--; i > 0; i--) {
1389 out_scratch_realloc:
1390 for_each_possible_cpu(i)
1391 pipapo_free_scratch(new, i);
1393 free_percpu(new->scratch);
1396 return ERR_PTR(-ENOMEM);
1400 * pipapo_rules_same_key() - Get number of rules originated from the same entry
1401 * @f: Field containing mapping table
1402 * @first: Index of first rule in set of rules mapping to same entry
1404 * Using the fact that all rules in a field that originated from the same entry
1405 * will map to the same set of rules in the next field, or to the same element
1406 * reference, return the cardinality of the set of rules that originated from
1407 * the same entry as the rule with index @first, @first rule included.
1411 * field #0 0 1 2 3 4
1412 * map to: 0 1 2-4 2-4 5-9
1418 * in field #1 0 1 2 3 4 5 ...
1420 * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1421 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1423 * For the last field in a set, we can rely on associated entries to map to the
1424 * same element references.
1426 * Return: Number of rules that originated from the same entry as @first.
1428 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
1430 struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1433 for (r = first; r < f->rules; r++) {
1434 if (r != first && e != f->mt[r].e)
1447 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1448 * @mt: Mapping array
1449 * @rules: Original amount of rules in mapping table
1450 * @start: First rule index to be removed
1451 * @n: Amount of rules to be removed
1452 * @to_offset: First rule index, in next field, this group of rules maps to
1453 * @is_last: If this is the last field, delete reference from mapping array
1455 * This is used to unmap rules from the mapping table for a single field,
1456 * maintaining consistency and compactness for the existing ones.
1458 * In pictures: let's assume that we want to delete rules 2 and 3 from the
1459 * following mapping array:
1463 * map to: 4-10 4-10 11-15 11-15 16-18
1465 * the result will be:
1469 * map to: 4-10 4-10 11-13
1471 * for fields before the last one. In case this is the mapping table for the
1472 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1476 * element pointers: 0x42 0x42 0x33 0x33 0x44
1478 * the result will be:
1482 * element pointers: 0x42 0x42 0x44
1484 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
1485 int start, int n, int to_offset, bool is_last)
1489 memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1490 memset(mt + rules - n, 0, n * sizeof(*mt));
1495 for (i = start; i < rules - n; i++)
1496 mt[i].to -= to_offset;
1500 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1502 * @rulemap: Table of rule maps, arrays of first rule and amount of rules
1503 * in next field a given entry maps to, for each field
1505 * For each rule in lookup table buckets mapping to this set of rules, drop
1506 * all bits set in lookup table mapping. In pictures, assuming we want to drop
1507 * rules 0 and 1 from this lookup table:
1510 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1517 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1518 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
1520 * rule 2 becomes rule 0, and the result will be:
1523 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1533 * once this is done, call unmap() to drop all the corresponding rule references
1534 * from mapping tables.
1536 static void pipapo_drop(struct nft_pipapo_match *m,
1537 union nft_pipapo_map_bucket rulemap[])
1539 struct nft_pipapo_field *f;
1542 nft_pipapo_for_each_field(f, i, m) {
1545 for (g = 0; g < f->groups; g++) {
1549 pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g *
1550 NFT_PIPAPO_BUCKETS(f->bb) * f->bsize;
1552 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1553 bitmap_cut(pos, pos, rulemap[i].to,
1555 f->bsize * BITS_PER_LONG);
1561 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1562 rulemap[i + 1].n, i == m->field_count - 1);
1563 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1564 /* We can ignore this, a failure to shrink tables down
1565 * doesn't make tables invalid.
1569 f->rules -= rulemap[i].n;
1571 pipapo_lt_bits_adjust(f);
1575 static void nft_pipapo_gc_deactivate(struct net *net, struct nft_set *set,
1576 struct nft_pipapo_elem *e)
1579 nft_setelem_data_deactivate(net, set, &e->priv);
1583 * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1584 * @set: nftables API set representation
1587 static void pipapo_gc(struct nft_set *set, struct nft_pipapo_match *m)
1589 struct nft_pipapo *priv = nft_set_priv(set);
1590 struct net *net = read_pnet(&set->net);
1591 u64 tstamp = nft_net_tstamp(net);
1592 int rules_f0, first_rule = 0;
1593 struct nft_pipapo_elem *e;
1594 struct nft_trans_gc *gc;
1596 gc = nft_trans_gc_alloc(set, 0, GFP_KERNEL);
1600 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1601 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1602 const struct nft_pipapo_field *f;
1603 int i, start, rules_fx;
1606 rules_fx = rules_f0;
1608 nft_pipapo_for_each_field(f, i, m) {
1609 rulemap[i].to = start;
1610 rulemap[i].n = rules_fx;
1612 if (i < m->field_count - 1) {
1613 rules_fx = f->mt[start].n;
1614 start = f->mt[start].to;
1618 /* Pick the last field, and its last index */
1621 e = f->mt[rulemap[i].to].e;
1623 /* synchronous gc never fails, there is no need to set on
1624 * NFT_SET_ELEM_DEAD_BIT.
1626 if (__nft_set_elem_expired(&e->ext, tstamp)) {
1629 gc = nft_trans_gc_queue_sync(gc, GFP_KERNEL);
1633 nft_pipapo_gc_deactivate(net, set, e);
1634 pipapo_drop(m, rulemap);
1635 nft_trans_gc_elem_add(gc, e);
1637 /* And check again current first rule, which is now the
1638 * first we haven't checked.
1641 first_rule += rules_f0;
1645 gc = nft_trans_gc_catchall_sync(gc);
1647 nft_trans_gc_queue_sync_done(gc);
1648 priv->last_gc = jiffies;
1653 * pipapo_free_fields() - Free per-field tables contained in matching data
1656 static void pipapo_free_fields(struct nft_pipapo_match *m)
1658 struct nft_pipapo_field *f;
1661 nft_pipapo_for_each_field(f, i, m) {
1667 static void pipapo_free_match(struct nft_pipapo_match *m)
1671 for_each_possible_cpu(i)
1672 pipapo_free_scratch(m, i);
1674 free_percpu(m->scratch);
1675 pipapo_free_fields(m);
1681 * pipapo_reclaim_match - RCU callback to free fields from old matching data
1684 static void pipapo_reclaim_match(struct rcu_head *rcu)
1686 struct nft_pipapo_match *m;
1688 m = container_of(rcu, struct nft_pipapo_match, rcu);
1689 pipapo_free_match(m);
1693 * nft_pipapo_commit() - Replace lookup data with current working copy
1694 * @set: nftables API set representation
1696 * While at it, check if we should perform garbage collection on the working
1697 * copy before committing it for lookup, and don't replace the table if the
1698 * working copy doesn't have pending changes.
1700 * We also need to create a new working copy for subsequent insertions and
1703 static void nft_pipapo_commit(struct nft_set *set)
1705 struct nft_pipapo *priv = nft_set_priv(set);
1706 struct nft_pipapo_match *new_clone, *old;
1708 if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1709 pipapo_gc(set, priv->clone);
1714 new_clone = pipapo_clone(priv->clone);
1715 if (IS_ERR(new_clone))
1718 priv->dirty = false;
1720 old = rcu_access_pointer(priv->match);
1721 rcu_assign_pointer(priv->match, priv->clone);
1723 call_rcu(&old->rcu, pipapo_reclaim_match);
1725 priv->clone = new_clone;
1728 static bool nft_pipapo_transaction_mutex_held(const struct nft_set *set)
1730 #ifdef CONFIG_PROVE_LOCKING
1731 const struct net *net = read_pnet(&set->net);
1733 return lockdep_is_held(&nft_pernet(net)->commit_mutex);
1739 static void nft_pipapo_abort(const struct nft_set *set)
1741 struct nft_pipapo *priv = nft_set_priv(set);
1742 struct nft_pipapo_match *new_clone, *m;
1747 m = rcu_dereference_protected(priv->match, nft_pipapo_transaction_mutex_held(set));
1749 new_clone = pipapo_clone(m);
1750 if (IS_ERR(new_clone))
1753 priv->dirty = false;
1755 pipapo_free_match(priv->clone);
1756 priv->clone = new_clone;
1760 * nft_pipapo_activate() - Mark element reference as active given key, commit
1761 * @net: Network namespace
1762 * @set: nftables API set representation
1763 * @elem_priv: nftables API element representation containing key data
1765 * On insertion, elements are added to a copy of the matching data currently
1766 * in use for lookups, and not directly inserted into current lookup data. Both
1767 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1768 * element, hence we can't purpose either one as a real commit operation.
1770 static void nft_pipapo_activate(const struct net *net,
1771 const struct nft_set *set,
1772 struct nft_elem_priv *elem_priv)
1774 struct nft_pipapo_elem *e = nft_elem_priv_cast(elem_priv);
1776 nft_clear(net, &e->ext);
1780 * pipapo_deactivate() - Check that element is in set, mark as inactive
1781 * @net: Network namespace
1782 * @set: nftables API set representation
1783 * @data: Input key data
1784 * @ext: nftables API extension pointer, used to check for end element
1786 * This is a convenience function that can be called from both
1787 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1790 * Return: deactivated element if found, NULL otherwise.
1792 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
1793 const u8 *data, const struct nft_set_ext *ext)
1795 struct nft_pipapo_elem *e;
1797 e = pipapo_get(net, set, data, nft_genmask_next(net), nft_net_tstamp(net));
1801 nft_set_elem_change_active(net, set, &e->ext);
1807 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1808 * @net: Network namespace
1809 * @set: nftables API set representation
1810 * @elem: nftables API element representation containing key data
1812 * Return: deactivated element if found, NULL otherwise.
1814 static struct nft_elem_priv *
1815 nft_pipapo_deactivate(const struct net *net, const struct nft_set *set,
1816 const struct nft_set_elem *elem)
1818 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1820 return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
1824 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1825 * @net: Network namespace
1826 * @set: nftables API set representation
1827 * @elem_priv: nftables API element representation containing key data
1829 * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1830 * different interface, and it's also called once for each element in a set
1831 * being flushed, so we can't implement, strictly speaking, a flush operation,
1832 * which would otherwise be as simple as allocating an empty copy of the
1835 * Note that we could in theory do that, mark the set as flushed, and ignore
1836 * subsequent calls, but we would leak all the elements after the first one,
1837 * because they wouldn't then be freed as result of API calls.
1839 * Return: true if element was found and deactivated.
1841 static void nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1842 struct nft_elem_priv *elem_priv)
1844 struct nft_pipapo_elem *e = nft_elem_priv_cast(elem_priv);
1846 nft_set_elem_change_active(net, set, &e->ext);
1850 * pipapo_get_boundaries() - Get byte interval for associated rules
1851 * @f: Field including lookup table
1852 * @first_rule: First rule (lowest index)
1853 * @rule_count: Number of associated rules
1854 * @left: Byte expression for left boundary (start of range)
1855 * @right: Byte expression for right boundary (end of range)
1857 * Given the first rule and amount of rules that originated from the same entry,
1858 * build the original range associated with the entry, and calculate the length
1859 * of the originating netmask.
1864 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1871 * 6 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1872 * 7 1,2 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1874 * this is the lookup table corresponding to the IPv4 range
1875 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1876 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1878 * This function fills @left and @right with the byte values of the leftmost
1879 * and rightmost bucket indices for the lowest and highest rule indices,
1880 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1882 * left: < 12, 0, 10, 8, 0, 1, 0, 0 >
1883 * right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1884 * corresponding to bytes:
1885 * left: < 192, 168, 1, 0 >
1886 * right: < 192, 168, 2, 1 >
1887 * with mask length irrelevant here, unused on return, as the range is already
1888 * defined by its start and end points. The mask length is relevant for a single
1889 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1890 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1891 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1892 * between leftmost and rightmost bucket indices for each group, would be 24.
1894 * Return: mask length, in bits.
1896 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1897 int rule_count, u8 *left, u8 *right)
1899 int g, mask_len = 0, bit_offset = 0;
1900 u8 *l = left, *r = right;
1902 for (g = 0; g < f->groups; g++) {
1907 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1910 pos = NFT_PIPAPO_LT_ALIGN(f->lt) +
1911 (g * NFT_PIPAPO_BUCKETS(f->bb) + b) * f->bsize;
1912 if (test_bit(first_rule, pos) && x0 == -1)
1914 if (test_bit(first_rule + rule_count - 1, pos))
1918 *l |= x0 << (BITS_PER_BYTE - f->bb - bit_offset);
1919 *r |= x1 << (BITS_PER_BYTE - f->bb - bit_offset);
1921 bit_offset += f->bb;
1922 if (bit_offset >= BITS_PER_BYTE) {
1923 bit_offset %= BITS_PER_BYTE;
1930 else if (x1 - x0 == 1)
1932 else if (x1 - x0 == 3)
1934 else if (x1 - x0 == 7)
1942 * pipapo_match_field() - Match rules against byte ranges
1943 * @f: Field including the lookup table
1944 * @first_rule: First of associated rules originating from same entry
1945 * @rule_count: Amount of associated rules
1946 * @start: Start of range to be matched
1947 * @end: End of range to be matched
1949 * Return: true on match, false otherwise.
1951 static bool pipapo_match_field(struct nft_pipapo_field *f,
1952 int first_rule, int rule_count,
1953 const u8 *start, const u8 *end)
1955 u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
1956 u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
1958 pipapo_get_boundaries(f, first_rule, rule_count, left, right);
1960 return !memcmp(start, left,
1961 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) &&
1962 !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1966 * nft_pipapo_remove() - Remove element given key, commit
1967 * @net: Network namespace
1968 * @set: nftables API set representation
1969 * @elem_priv: nftables API element representation containing key data
1971 * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1972 * API, but it's called once per element in the pending transaction, so we can't
1973 * implement this as a single commit operation. Closest we can get is to remove
1974 * the matched element here, if any, and commit the updated matching data.
1976 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
1977 struct nft_elem_priv *elem_priv)
1979 struct nft_pipapo *priv = nft_set_priv(set);
1980 struct nft_pipapo_match *m = priv->clone;
1981 int rules_f0, first_rule = 0;
1982 struct nft_pipapo_elem *e;
1985 e = nft_elem_priv_cast(elem_priv);
1986 data = (const u8 *)nft_set_ext_key(&e->ext);
1988 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1989 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1990 const u8 *match_start, *match_end;
1991 struct nft_pipapo_field *f;
1992 int i, start, rules_fx;
1996 if (nft_set_ext_exists(&e->ext, NFT_SET_EXT_KEY_END))
1997 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
2002 rules_fx = rules_f0;
2004 nft_pipapo_for_each_field(f, i, m) {
2005 bool last = i == m->field_count - 1;
2007 if (!pipapo_match_field(f, start, rules_fx,
2008 match_start, match_end))
2011 rulemap[i].to = start;
2012 rulemap[i].n = rules_fx;
2014 rules_fx = f->mt[start].n;
2015 start = f->mt[start].to;
2017 match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2018 match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
2020 if (last && f->mt[rulemap[i].to].e == e) {
2022 pipapo_drop(m, rulemap);
2027 first_rule += rules_f0;
2030 WARN_ON_ONCE(1); /* elem_priv not found */
2034 * nft_pipapo_walk() - Walk over elements
2035 * @ctx: nftables API context
2036 * @set: nftables API set representation
2039 * As elements are referenced in the mapping array for the last field, directly
2040 * scan that array: there's no need to follow rule mappings from the first
2043 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
2044 struct nft_set_iter *iter)
2046 struct nft_pipapo *priv = nft_set_priv(set);
2047 const struct nft_pipapo_match *m;
2048 const struct nft_pipapo_field *f;
2051 WARN_ON_ONCE(iter->type != NFT_ITER_READ &&
2052 iter->type != NFT_ITER_UPDATE);
2055 if (iter->type == NFT_ITER_READ)
2056 m = rcu_dereference(priv->match);
2063 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2066 for (r = 0; r < f->rules; r++) {
2067 struct nft_pipapo_elem *e;
2069 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2072 if (iter->count < iter->skip)
2077 iter->err = iter->fn(ctx, set, iter, &e->priv);
2090 * nft_pipapo_privsize() - Return the size of private data for the set
2091 * @nla: netlink attributes, ignored as size doesn't depend on them
2092 * @desc: Set description, ignored as size doesn't depend on it
2094 * Return: size of private data for this set implementation, in bytes
2096 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
2097 const struct nft_set_desc *desc)
2099 return sizeof(struct nft_pipapo);
2103 * nft_pipapo_estimate() - Set size, space and lookup complexity
2104 * @desc: Set description, element count and field description used
2105 * @features: Flags: NFT_SET_INTERVAL needs to be there
2106 * @est: Storage for estimation data
2108 * Return: true if set description is compatible, false otherwise
2110 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
2111 struct nft_set_estimate *est)
2113 if (!(features & NFT_SET_INTERVAL) ||
2114 desc->field_count < NFT_PIPAPO_MIN_FIELDS)
2117 est->size = pipapo_estimate_size(desc);
2121 est->lookup = NFT_SET_CLASS_O_LOG_N;
2123 est->space = NFT_SET_CLASS_O_N;
2129 * nft_pipapo_init() - Initialise data for a set instance
2130 * @set: nftables API set representation
2131 * @desc: Set description
2132 * @nla: netlink attributes
2134 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
2135 * attributes, initialise internal set parameters, current instance of matching
2136 * data and a copy for subsequent insertions.
2138 * Return: 0 on success, negative error code on failure.
2140 static int nft_pipapo_init(const struct nft_set *set,
2141 const struct nft_set_desc *desc,
2142 const struct nlattr * const nla[])
2144 struct nft_pipapo *priv = nft_set_priv(set);
2145 struct nft_pipapo_match *m;
2146 struct nft_pipapo_field *f;
2147 int err, i, field_count;
2149 BUILD_BUG_ON(offsetof(struct nft_pipapo_elem, priv) != 0);
2151 field_count = desc->field_count ? : 1;
2153 if (field_count > NFT_PIPAPO_MAX_FIELDS)
2156 m = kmalloc(struct_size(m, f, field_count), GFP_KERNEL);
2160 m->field_count = field_count;
2163 m->scratch = alloc_percpu(struct nft_pipapo_scratch *);
2168 for_each_possible_cpu(i)
2169 *per_cpu_ptr(m->scratch, i) = NULL;
2171 rcu_head_init(&m->rcu);
2173 nft_pipapo_for_each_field(f, i, m) {
2174 int len = desc->field_len[i] ? : set->klen;
2176 f->bb = NFT_PIPAPO_GROUP_BITS_INIT;
2177 f->groups = len * NFT_PIPAPO_GROUPS_PER_BYTE(f);
2179 priv->width += round_up(len, sizeof(u32));
2183 NFT_PIPAPO_LT_ASSIGN(f, NULL);
2187 /* Create an initial clone of matching data for next insertion */
2188 priv->clone = pipapo_clone(m);
2189 if (IS_ERR(priv->clone)) {
2190 err = PTR_ERR(priv->clone);
2194 priv->dirty = false;
2196 rcu_assign_pointer(priv->match, m);
2201 free_percpu(m->scratch);
2209 * nft_set_pipapo_match_destroy() - Destroy elements from key mapping array
2211 * @set: nftables API set representation
2212 * @m: matching data pointing to key mapping array
2214 static void nft_set_pipapo_match_destroy(const struct nft_ctx *ctx,
2215 const struct nft_set *set,
2216 struct nft_pipapo_match *m)
2218 struct nft_pipapo_field *f;
2221 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2224 for (r = 0; r < f->rules; r++) {
2225 struct nft_pipapo_elem *e;
2227 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2232 nf_tables_set_elem_destroy(ctx, set, &e->priv);
2237 * nft_pipapo_destroy() - Free private data for set and all committed elements
2239 * @set: nftables API set representation
2241 static void nft_pipapo_destroy(const struct nft_ctx *ctx,
2242 const struct nft_set *set)
2244 struct nft_pipapo *priv = nft_set_priv(set);
2245 struct nft_pipapo_match *m;
2248 m = rcu_dereference_protected(priv->match, true);
2252 for_each_possible_cpu(cpu)
2253 pipapo_free_scratch(m, cpu);
2254 free_percpu(m->scratch);
2255 pipapo_free_fields(m);
2263 nft_set_pipapo_match_destroy(ctx, set, m);
2265 for_each_possible_cpu(cpu)
2266 pipapo_free_scratch(priv->clone, cpu);
2267 free_percpu(priv->clone->scratch);
2269 pipapo_free_fields(priv->clone);
2276 * nft_pipapo_gc_init() - Initialise garbage collection
2277 * @set: nftables API set representation
2279 * Instead of actually setting up a periodic work for garbage collection, as
2280 * this operation requires a swap of matching data with the working copy, we'll
2281 * do that opportunistically with other commit operations if the interval is
2282 * elapsed, so we just need to set the current jiffies timestamp here.
2284 static void nft_pipapo_gc_init(const struct nft_set *set)
2286 struct nft_pipapo *priv = nft_set_priv(set);
2288 priv->last_gc = jiffies;
2291 const struct nft_set_type nft_set_pipapo_type = {
2292 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2295 .lookup = nft_pipapo_lookup,
2296 .insert = nft_pipapo_insert,
2297 .activate = nft_pipapo_activate,
2298 .deactivate = nft_pipapo_deactivate,
2299 .flush = nft_pipapo_flush,
2300 .remove = nft_pipapo_remove,
2301 .walk = nft_pipapo_walk,
2302 .get = nft_pipapo_get,
2303 .privsize = nft_pipapo_privsize,
2304 .estimate = nft_pipapo_estimate,
2305 .init = nft_pipapo_init,
2306 .destroy = nft_pipapo_destroy,
2307 .gc_init = nft_pipapo_gc_init,
2308 .commit = nft_pipapo_commit,
2309 .abort = nft_pipapo_abort,
2310 .elemsize = offsetof(struct nft_pipapo_elem, ext),
2314 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2315 const struct nft_set_type nft_set_pipapo_avx2_type = {
2316 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2319 .lookup = nft_pipapo_avx2_lookup,
2320 .insert = nft_pipapo_insert,
2321 .activate = nft_pipapo_activate,
2322 .deactivate = nft_pipapo_deactivate,
2323 .flush = nft_pipapo_flush,
2324 .remove = nft_pipapo_remove,
2325 .walk = nft_pipapo_walk,
2326 .get = nft_pipapo_get,
2327 .privsize = nft_pipapo_privsize,
2328 .estimate = nft_pipapo_avx2_estimate,
2329 .init = nft_pipapo_init,
2330 .destroy = nft_pipapo_destroy,
2331 .gc_init = nft_pipapo_gc_init,
2332 .commit = nft_pipapo_commit,
2333 .abort = nft_pipapo_abort,
2334 .elemsize = offsetof(struct nft_pipapo_elem, ext),