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"
345 /* Current working bitmap index, toggled between field matches */
346 static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index
);
349 * pipapo_refill() - For each set bit, set bits from selected mapping table item
350 * @map: Bitmap to be scanned for set bits
351 * @len: Length of bitmap in longs
352 * @rules: Number of rules in field
353 * @dst: Destination bitmap
354 * @mt: Mapping table containing bit set specifiers
355 * @match_only: Find a single bit and return, don't fill
357 * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
359 * For each bit set in map, select the bucket from mapping table with index
360 * corresponding to the position of the bit set. Use start bit and amount of
361 * bits specified in bucket to fill region in dst.
363 * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
365 int pipapo_refill(unsigned long *map
, int len
, int rules
, unsigned long *dst
,
366 union nft_pipapo_map_bucket
*mt
, bool match_only
)
368 unsigned long bitset
;
371 for (k
= 0; k
< len
; k
++) {
374 unsigned long t
= bitset
& -bitset
;
375 int r
= __builtin_ctzl(bitset
);
376 int i
= k
* BITS_PER_LONG
+ r
;
378 if (unlikely(i
>= rules
)) {
384 bitmap_clear(map
, i
, 1);
390 bitmap_set(dst
, mt
[i
].to
, mt
[i
].n
);
401 * nft_pipapo_lookup() - Lookup function
402 * @net: Network namespace
403 * @set: nftables API set representation
404 * @key: nftables API element representation containing key data
405 * @ext: nftables API extension pointer, filled with matching reference
407 * For more details, see DOC: Theory of Operation.
409 * Return: true on match, false otherwise.
411 static bool nft_pipapo_lookup(const struct net
*net
, const struct nft_set
*set
,
412 const u32
*key
, const struct nft_set_ext
**ext
)
414 struct nft_pipapo
*priv
= nft_set_priv(set
);
415 unsigned long *res_map
, *fill_map
;
416 u8 genmask
= nft_genmask_cur(net
);
417 const u8
*rp
= (const u8
*)key
;
418 struct nft_pipapo_match
*m
;
419 struct nft_pipapo_field
*f
;
425 map_index
= raw_cpu_read(nft_pipapo_scratch_index
);
427 m
= rcu_dereference(priv
->match
);
429 if (unlikely(!m
|| !*raw_cpu_ptr(m
->scratch
)))
432 res_map
= *raw_cpu_ptr(m
->scratch
) + (map_index
? m
->bsize_max
: 0);
433 fill_map
= *raw_cpu_ptr(m
->scratch
) + (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 raw_cpu_write(nft_pipapo_scratch_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 raw_cpu_write(nft_pipapo_scratch_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
508 * This is essentially the same as the lookup function, except that it matches
509 * key data against the uncommitted copy and doesn't use preallocated maps for
512 * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
514 static struct nft_pipapo_elem
*pipapo_get(const struct net
*net
,
515 const struct nft_set
*set
,
516 const u8
*data
, u8 genmask
)
518 struct nft_pipapo_elem
*ret
= ERR_PTR(-ENOENT
);
519 struct nft_pipapo
*priv
= nft_set_priv(set
);
520 struct nft_pipapo_match
*m
= priv
->clone
;
521 unsigned long *res_map
, *fill_map
= NULL
;
522 struct nft_pipapo_field
*f
;
525 res_map
= kmalloc_array(m
->bsize_max
, sizeof(*res_map
), GFP_ATOMIC
);
527 ret
= ERR_PTR(-ENOMEM
);
531 fill_map
= kcalloc(m
->bsize_max
, sizeof(*res_map
), GFP_ATOMIC
);
533 ret
= ERR_PTR(-ENOMEM
);
537 memset(res_map
, 0xff, m
->bsize_max
* sizeof(*res_map
));
539 nft_pipapo_for_each_field(f
, i
, m
) {
540 bool last
= i
== m
->field_count
- 1;
543 /* For each bit group: select lookup table bucket depending on
544 * packet bytes value, then AND bucket value
547 pipapo_and_field_buckets_8bit(f
, res_map
, data
);
549 pipapo_and_field_buckets_4bit(f
, res_map
, data
);
553 data
+= f
->groups
/ NFT_PIPAPO_GROUPS_PER_BYTE(f
);
555 /* Now populate the bitmap for the next field, unless this is
556 * the last field, in which case return the matched 'ext'
559 * Now res_map contains the matching bitmap, and fill_map is the
560 * bitmap for the next field.
563 b
= pipapo_refill(res_map
, f
->bsize
, f
->rules
, fill_map
, f
->mt
,
569 if (nft_set_elem_expired(&f
->mt
[b
].e
->ext
) ||
571 !nft_set_elem_active(&f
->mt
[b
].e
->ext
, genmask
)))
578 data
+= NFT_PIPAPO_GROUPS_PADDING(f
);
580 /* Swap bitmap indices: fill_map will be the initial bitmap for
581 * the next field (i.e. the new res_map), and res_map is
582 * guaranteed to be all-zeroes at this point, ready to be filled
583 * according to the next mapping table.
585 swap(res_map
, fill_map
);
595 * nft_pipapo_get() - Get matching element reference given key data
596 * @net: Network namespace
597 * @set: nftables API set representation
598 * @elem: nftables API element representation containing key data
601 static void *nft_pipapo_get(const struct net
*net
, const struct nft_set
*set
,
602 const struct nft_set_elem
*elem
, unsigned int flags
)
604 return pipapo_get(net
, set
, (const u8
*)elem
->key
.val
.data
,
605 nft_genmask_cur(net
));
609 * pipapo_resize() - Resize lookup or mapping table, or both
610 * @f: Field containing lookup and mapping tables
611 * @old_rules: Previous amount of rules in field
612 * @rules: New amount of rules
614 * Increase, decrease or maintain tables size depending on new amount of rules,
615 * and copy data over. In case the new size is smaller, throw away data for
616 * highest-numbered rules.
618 * Return: 0 on success, -ENOMEM on allocation failure.
620 static int pipapo_resize(struct nft_pipapo_field
*f
, int old_rules
, int rules
)
622 long *new_lt
= NULL
, *new_p
, *old_lt
= f
->lt
, *old_p
;
623 union nft_pipapo_map_bucket
*new_mt
, *old_mt
= f
->mt
;
624 size_t new_bucket_size
, copy
;
627 new_bucket_size
= DIV_ROUND_UP(rules
, BITS_PER_LONG
);
628 #ifdef NFT_PIPAPO_ALIGN
629 new_bucket_size
= roundup(new_bucket_size
,
630 NFT_PIPAPO_ALIGN
/ sizeof(*new_lt
));
633 if (new_bucket_size
== f
->bsize
)
636 if (new_bucket_size
> f
->bsize
)
639 copy
= new_bucket_size
;
641 new_lt
= kvzalloc(f
->groups
* NFT_PIPAPO_BUCKETS(f
->bb
) *
642 new_bucket_size
* sizeof(*new_lt
) +
643 NFT_PIPAPO_ALIGN_HEADROOM
,
648 new_p
= NFT_PIPAPO_LT_ALIGN(new_lt
);
649 old_p
= NFT_PIPAPO_LT_ALIGN(old_lt
);
651 for (group
= 0; group
< f
->groups
; group
++) {
652 for (bucket
= 0; bucket
< NFT_PIPAPO_BUCKETS(f
->bb
); bucket
++) {
653 memcpy(new_p
, old_p
, copy
* sizeof(*new_p
));
657 if (new_bucket_size
> f
->bsize
)
658 new_p
+= new_bucket_size
- f
->bsize
;
660 old_p
+= f
->bsize
- new_bucket_size
;
665 new_mt
= kvmalloc(rules
* sizeof(*new_mt
), GFP_KERNEL
);
671 memcpy(new_mt
, f
->mt
, min(old_rules
, rules
) * sizeof(*new_mt
));
672 if (rules
> old_rules
) {
673 memset(new_mt
+ old_rules
, 0,
674 (rules
- old_rules
) * sizeof(*new_mt
));
678 f
->bsize
= new_bucket_size
;
679 NFT_PIPAPO_LT_ASSIGN(f
, new_lt
);
690 * pipapo_bucket_set() - Set rule bit in bucket given group and group value
691 * @f: Field containing lookup table
693 * @group: Group index
694 * @v: Value of bit group
696 static void pipapo_bucket_set(struct nft_pipapo_field
*f
, int rule
, int group
,
701 pos
= NFT_PIPAPO_LT_ALIGN(f
->lt
);
702 pos
+= f
->bsize
* NFT_PIPAPO_BUCKETS(f
->bb
) * group
;
705 __set_bit(rule
, pos
);
709 * pipapo_lt_4b_to_8b() - Switch lookup table group width from 4 bits to 8 bits
710 * @old_groups: Number of current groups
711 * @bsize: Size of one bucket, in longs
712 * @old_lt: Pointer to the current lookup table
713 * @new_lt: Pointer to the new, pre-allocated lookup table
715 * Each bucket with index b in the new lookup table, belonging to group g, is
716 * filled with the bit intersection between:
717 * - bucket with index given by the upper 4 bits of b, from group g, and
718 * - bucket with index given by the lower 4 bits of b, from group g + 1
720 * That is, given buckets from the new lookup table N(x, y) and the old lookup
721 * table O(x, y), with x bucket index, and y group index:
723 * N(b, g) := O(b / 16, g) & O(b % 16, g + 1)
725 * This ensures equivalence of the matching results on lookup. Two examples in
729 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ... 254 255
736 * group 0 / 1 2 3 \ 4 5 6 7 8 9 10 11 12 13 |14 15 |
743 static void pipapo_lt_4b_to_8b(int old_groups
, int bsize
,
744 unsigned long *old_lt
, unsigned long *new_lt
)
748 for (g
= 0; g
< old_groups
/ 2; g
++) {
749 int src_g0
= g
* 2, src_g1
= g
* 2 + 1;
751 for (b
= 0; b
< NFT_PIPAPO_BUCKETS(8); b
++) {
752 int src_b0
= b
/ NFT_PIPAPO_BUCKETS(4);
753 int src_b1
= b
% NFT_PIPAPO_BUCKETS(4);
754 int src_i0
= src_g0
* NFT_PIPAPO_BUCKETS(4) + src_b0
;
755 int src_i1
= src_g1
* NFT_PIPAPO_BUCKETS(4) + src_b1
;
757 for (i
= 0; i
< bsize
; i
++) {
758 *new_lt
= old_lt
[src_i0
* bsize
+ i
] &
759 old_lt
[src_i1
* bsize
+ i
];
767 * pipapo_lt_8b_to_4b() - Switch lookup table group width from 8 bits to 4 bits
768 * @old_groups: Number of current groups
769 * @bsize: Size of one bucket, in longs
770 * @old_lt: Pointer to the current lookup table
771 * @new_lt: Pointer to the new, pre-allocated lookup table
773 * Each bucket with index b in the new lookup table, belonging to group g, is
774 * filled with the bit union of:
775 * - all the buckets with index such that the upper four bits of the lower byte
776 * equal b, from group g, with g odd
777 * - all the buckets with index such that the lower four bits equal b, from
778 * group g, with g even
780 * That is, given buckets from the new lookup table N(x, y) and the old lookup
781 * table O(x, y), with x bucket index, and y group index:
783 * - with g odd: N(b, g) := U(O(x, g) for each x : x = (b & 0xf0) >> 4)
784 * - with g even: N(b, g) := U(O(x, g) for each x : x = b & 0x0f)
786 * where U() denotes the arbitrary union operation (binary OR of n terms). This
787 * ensures equivalence of the matching results on lookup.
789 static void pipapo_lt_8b_to_4b(int old_groups
, int bsize
,
790 unsigned long *old_lt
, unsigned long *new_lt
)
794 memset(new_lt
, 0, old_groups
* 2 * NFT_PIPAPO_BUCKETS(4) * bsize
*
795 sizeof(unsigned long));
797 for (g
= 0; g
< old_groups
* 2; g
+= 2) {
800 for (b
= 0; b
< NFT_PIPAPO_BUCKETS(4); b
++) {
801 for (bsrc
= NFT_PIPAPO_BUCKETS(8) * src_g
;
802 bsrc
< NFT_PIPAPO_BUCKETS(8) * (src_g
+ 1);
804 if (((bsrc
& 0xf0) >> 4) != b
)
807 for (i
= 0; i
< bsize
; i
++)
808 new_lt
[i
] |= old_lt
[bsrc
* bsize
+ i
];
814 for (b
= 0; b
< NFT_PIPAPO_BUCKETS(4); b
++) {
815 for (bsrc
= NFT_PIPAPO_BUCKETS(8) * src_g
;
816 bsrc
< NFT_PIPAPO_BUCKETS(8) * (src_g
+ 1);
818 if ((bsrc
& 0x0f) != b
)
821 for (i
= 0; i
< bsize
; i
++)
822 new_lt
[i
] |= old_lt
[bsrc
* bsize
+ i
];
831 * pipapo_lt_bits_adjust() - Adjust group size for lookup table if needed
832 * @f: Field containing lookup table
834 static void pipapo_lt_bits_adjust(struct nft_pipapo_field
*f
)
836 unsigned long *new_lt
;
840 lt_size
= f
->groups
* NFT_PIPAPO_BUCKETS(f
->bb
) * f
->bsize
*
843 if (f
->bb
== NFT_PIPAPO_GROUP_BITS_SMALL_SET
&&
844 lt_size
> NFT_PIPAPO_LT_SIZE_HIGH
) {
845 groups
= f
->groups
* 2;
846 bb
= NFT_PIPAPO_GROUP_BITS_LARGE_SET
;
848 lt_size
= groups
* NFT_PIPAPO_BUCKETS(bb
) * f
->bsize
*
850 } else if (f
->bb
== NFT_PIPAPO_GROUP_BITS_LARGE_SET
&&
851 lt_size
< NFT_PIPAPO_LT_SIZE_LOW
) {
852 groups
= f
->groups
/ 2;
853 bb
= NFT_PIPAPO_GROUP_BITS_SMALL_SET
;
855 lt_size
= groups
* NFT_PIPAPO_BUCKETS(bb
) * f
->bsize
*
858 /* Don't increase group width if the resulting lookup table size
859 * would exceed the upper size threshold for a "small" set.
861 if (lt_size
> NFT_PIPAPO_LT_SIZE_HIGH
)
867 new_lt
= kvzalloc(lt_size
+ NFT_PIPAPO_ALIGN_HEADROOM
, GFP_KERNEL
);
871 NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4
;
872 if (f
->bb
== 4 && bb
== 8) {
873 pipapo_lt_4b_to_8b(f
->groups
, f
->bsize
,
874 NFT_PIPAPO_LT_ALIGN(f
->lt
),
875 NFT_PIPAPO_LT_ALIGN(new_lt
));
876 } else if (f
->bb
== 8 && bb
== 4) {
877 pipapo_lt_8b_to_4b(f
->groups
, f
->bsize
,
878 NFT_PIPAPO_LT_ALIGN(f
->lt
),
879 NFT_PIPAPO_LT_ALIGN(new_lt
));
887 NFT_PIPAPO_LT_ASSIGN(f
, new_lt
);
891 * pipapo_insert() - Insert new rule in field given input key and mask length
892 * @f: Field containing lookup table
893 * @k: Input key for classification, without nftables padding
894 * @mask_bits: Length of mask; matches field length for non-ranged entry
896 * Insert a new rule reference in lookup buckets corresponding to k and
899 * Return: 1 on success (one rule inserted), negative error code on failure.
901 static int pipapo_insert(struct nft_pipapo_field
*f
, const uint8_t *k
,
904 int rule
= f
->rules
++, group
, ret
, bit_offset
= 0;
906 ret
= pipapo_resize(f
, f
->rules
- 1, f
->rules
);
910 for (group
= 0; group
< f
->groups
; group
++) {
914 v
= k
[group
/ (BITS_PER_BYTE
/ f
->bb
)];
915 v
&= GENMASK(BITS_PER_BYTE
- bit_offset
- 1, 0);
916 v
>>= (BITS_PER_BYTE
- bit_offset
) - f
->bb
;
919 bit_offset
%= BITS_PER_BYTE
;
921 if (mask_bits
>= (group
+ 1) * f
->bb
) {
923 pipapo_bucket_set(f
, rule
, group
, v
);
924 } else if (mask_bits
<= group
* f
->bb
) {
925 /* Completely masked */
926 for (i
= 0; i
< NFT_PIPAPO_BUCKETS(f
->bb
); i
++)
927 pipapo_bucket_set(f
, rule
, group
, i
);
929 /* The mask limit falls on this group */
930 mask
= GENMASK(f
->bb
- 1, 0);
931 mask
>>= mask_bits
- group
* f
->bb
;
932 for (i
= 0; i
< NFT_PIPAPO_BUCKETS(f
->bb
); i
++) {
933 if ((i
& ~mask
) == (v
& ~mask
))
934 pipapo_bucket_set(f
, rule
, group
, i
);
939 pipapo_lt_bits_adjust(f
);
945 * pipapo_step_diff() - Check if setting @step bit in netmask would change it
946 * @base: Mask we are expanding
947 * @step: Step bit for given expansion step
948 * @len: Total length of mask space (set and unset bits), bytes
950 * Convenience function for mask expansion.
952 * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
954 static bool pipapo_step_diff(u8
*base
, int step
, int len
)
956 /* Network order, byte-addressed */
957 #ifdef __BIG_ENDIAN__
958 return !(BIT(step
% BITS_PER_BYTE
) & base
[step
/ BITS_PER_BYTE
]);
960 return !(BIT(step
% BITS_PER_BYTE
) &
961 base
[len
- 1 - step
/ BITS_PER_BYTE
]);
966 * pipapo_step_after_end() - Check if mask exceeds range end with given step
967 * @base: Mask we are expanding
969 * @step: Step bit for given expansion step, highest bit to be set
970 * @len: Total length of mask space (set and unset bits), bytes
972 * Convenience function for mask expansion.
974 * Return: true if mask exceeds range setting step bits, false otherwise.
976 static bool pipapo_step_after_end(const u8
*base
, const u8
*end
, int step
,
979 u8 tmp
[NFT_PIPAPO_MAX_BYTES
];
982 memcpy(tmp
, base
, len
);
984 /* Network order, byte-addressed */
985 for (i
= 0; i
<= step
; i
++)
986 #ifdef __BIG_ENDIAN__
987 tmp
[i
/ BITS_PER_BYTE
] |= BIT(i
% BITS_PER_BYTE
);
989 tmp
[len
- 1 - i
/ BITS_PER_BYTE
] |= BIT(i
% BITS_PER_BYTE
);
992 return memcmp(tmp
, end
, len
) > 0;
996 * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
997 * @base: Netmask base
998 * @step: Step bit to sum
999 * @len: Netmask length, bytes
1001 static void pipapo_base_sum(u8
*base
, int step
, int len
)
1006 /* Network order, byte-addressed */
1007 #ifdef __BIG_ENDIAN__
1008 for (i
= step
/ BITS_PER_BYTE
; i
< len
; i
++) {
1010 for (i
= len
- 1 - step
/ BITS_PER_BYTE
; i
>= 0; i
--) {
1015 base
[i
] += 1 << (step
% BITS_PER_BYTE
);
1025 * pipapo_expand() - Expand to composing netmasks, insert into lookup table
1026 * @f: Field containing lookup table
1027 * @start: Start of range
1028 * @end: End of range
1029 * @len: Length of value in bits
1031 * Expand range to composing netmasks and insert corresponding rule references
1032 * in lookup buckets.
1034 * Return: number of inserted rules on success, negative error code on failure.
1036 static int pipapo_expand(struct nft_pipapo_field
*f
,
1037 const u8
*start
, const u8
*end
, int len
)
1039 int step
, masks
= 0, bytes
= DIV_ROUND_UP(len
, BITS_PER_BYTE
);
1040 u8 base
[NFT_PIPAPO_MAX_BYTES
];
1042 memcpy(base
, start
, bytes
);
1043 while (memcmp(base
, end
, bytes
) <= 0) {
1047 while (pipapo_step_diff(base
, step
, bytes
)) {
1048 if (pipapo_step_after_end(base
, end
, step
, bytes
))
1054 pipapo_insert(f
, base
, 0);
1061 err
= pipapo_insert(f
, base
, len
- step
);
1067 pipapo_base_sum(base
, step
, bytes
);
1074 * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1075 * @m: Matching data, including mapping table
1076 * @map: Table of rule maps: array of first rule and amount of rules
1077 * in next field a given rule maps to, for each field
1078 * @e: For last field, nft_set_ext pointer matching rules map to
1080 static void pipapo_map(struct nft_pipapo_match
*m
,
1081 union nft_pipapo_map_bucket map
[NFT_PIPAPO_MAX_FIELDS
],
1082 struct nft_pipapo_elem
*e
)
1084 struct nft_pipapo_field
*f
;
1087 for (i
= 0, f
= m
->f
; i
< m
->field_count
- 1; i
++, f
++) {
1088 for (j
= 0; j
< map
[i
].n
; j
++) {
1089 f
->mt
[map
[i
].to
+ j
].to
= map
[i
+ 1].to
;
1090 f
->mt
[map
[i
].to
+ j
].n
= map
[i
+ 1].n
;
1094 /* Last field: map to ext instead of mapping to next field */
1095 for (j
= 0; j
< map
[i
].n
; j
++)
1096 f
->mt
[map
[i
].to
+ j
].e
= e
;
1100 * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1101 * @clone: Copy of matching data with pending insertions and deletions
1102 * @bsize_max: Maximum bucket size, scratch maps cover two buckets
1104 * Return: 0 on success, -ENOMEM on failure.
1106 static int pipapo_realloc_scratch(struct nft_pipapo_match
*clone
,
1107 unsigned long bsize_max
)
1111 for_each_possible_cpu(i
) {
1112 unsigned long *scratch
;
1113 #ifdef NFT_PIPAPO_ALIGN
1114 unsigned long *scratch_aligned
;
1117 scratch
= kzalloc_node(bsize_max
* sizeof(*scratch
) * 2 +
1118 NFT_PIPAPO_ALIGN_HEADROOM
,
1119 GFP_KERNEL
, cpu_to_node(i
));
1121 /* On failure, there's no need to undo previous
1122 * allocations: this means that some scratch maps have
1123 * a bigger allocated size now (this is only called on
1124 * insertion), but the extra space won't be used by any
1125 * CPU as new elements are not inserted and m->bsize_max
1131 kfree(*per_cpu_ptr(clone
->scratch
, i
));
1133 *per_cpu_ptr(clone
->scratch
, i
) = scratch
;
1135 #ifdef NFT_PIPAPO_ALIGN
1136 scratch_aligned
= NFT_PIPAPO_LT_ALIGN(scratch
);
1137 *per_cpu_ptr(clone
->scratch_aligned
, i
) = scratch_aligned
;
1145 * nft_pipapo_insert() - Validate and insert ranged elements
1146 * @net: Network namespace
1147 * @set: nftables API set representation
1148 * @elem: nftables API element representation containing key data
1149 * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
1151 * Return: 0 on success, error pointer on failure.
1153 static int nft_pipapo_insert(const struct net
*net
, const struct nft_set
*set
,
1154 const struct nft_set_elem
*elem
,
1155 struct nft_set_ext
**ext2
)
1157 const struct nft_set_ext
*ext
= nft_set_elem_ext(set
, elem
->priv
);
1158 union nft_pipapo_map_bucket rulemap
[NFT_PIPAPO_MAX_FIELDS
];
1159 const u8
*start
= (const u8
*)elem
->key
.val
.data
, *end
;
1160 struct nft_pipapo_elem
*e
= elem
->priv
, *dup
;
1161 struct nft_pipapo
*priv
= nft_set_priv(set
);
1162 struct nft_pipapo_match
*m
= priv
->clone
;
1163 u8 genmask
= nft_genmask_next(net
);
1164 struct nft_pipapo_field
*f
;
1165 int i
, bsize_max
, err
= 0;
1167 if (nft_set_ext_exists(ext
, NFT_SET_EXT_KEY_END
))
1168 end
= (const u8
*)nft_set_ext_key_end(ext
)->data
;
1172 dup
= pipapo_get(net
, set
, start
, genmask
);
1174 /* Check if we already have the same exact entry */
1175 const struct nft_data
*dup_key
, *dup_end
;
1177 dup_key
= nft_set_ext_key(&dup
->ext
);
1178 if (nft_set_ext_exists(&dup
->ext
, NFT_SET_EXT_KEY_END
))
1179 dup_end
= nft_set_ext_key_end(&dup
->ext
);
1183 if (!memcmp(start
, dup_key
->data
, sizeof(*dup_key
->data
)) &&
1184 !memcmp(end
, dup_end
->data
, sizeof(*dup_end
->data
))) {
1192 if (PTR_ERR(dup
) == -ENOENT
) {
1193 /* Look for partially overlapping entries */
1194 dup
= pipapo_get(net
, set
, end
, nft_genmask_next(net
));
1197 if (PTR_ERR(dup
) != -ENOENT
) {
1199 return PTR_ERR(dup
);
1205 nft_pipapo_for_each_field(f
, i
, m
) {
1206 const u8
*start_p
= start
, *end_p
= end
;
1208 if (f
->rules
>= (unsigned long)NFT_PIPAPO_RULE0_MAX
)
1211 if (memcmp(start_p
, end_p
,
1212 f
->groups
/ NFT_PIPAPO_GROUPS_PER_BYTE(f
)) > 0)
1215 start_p
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1216 end_p
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1222 bsize_max
= m
->bsize_max
;
1224 nft_pipapo_for_each_field(f
, i
, m
) {
1227 rulemap
[i
].to
= f
->rules
;
1229 ret
= memcmp(start
, end
,
1230 f
->groups
/ NFT_PIPAPO_GROUPS_PER_BYTE(f
));
1232 ret
= pipapo_insert(f
, start
, f
->groups
* f
->bb
);
1234 ret
= pipapo_expand(f
, start
, end
, f
->groups
* f
->bb
);
1236 if (f
->bsize
> bsize_max
)
1237 bsize_max
= f
->bsize
;
1241 start
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1242 end
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1245 if (!*get_cpu_ptr(m
->scratch
) || bsize_max
> m
->bsize_max
) {
1246 put_cpu_ptr(m
->scratch
);
1248 err
= pipapo_realloc_scratch(m
, bsize_max
);
1252 m
->bsize_max
= bsize_max
;
1254 put_cpu_ptr(m
->scratch
);
1259 pipapo_map(m
, rulemap
, e
);
1265 * pipapo_clone() - Clone matching data to create new working copy
1266 * @old: Existing matching data
1268 * Return: copy of matching data passed as 'old', error pointer on failure
1270 static struct nft_pipapo_match
*pipapo_clone(struct nft_pipapo_match
*old
)
1272 struct nft_pipapo_field
*dst
, *src
;
1273 struct nft_pipapo_match
*new;
1276 new = kmalloc(sizeof(*new) + sizeof(*dst
) * old
->field_count
,
1279 return ERR_PTR(-ENOMEM
);
1281 new->field_count
= old
->field_count
;
1282 new->bsize_max
= old
->bsize_max
;
1284 new->scratch
= alloc_percpu(*new->scratch
);
1288 #ifdef NFT_PIPAPO_ALIGN
1289 new->scratch_aligned
= alloc_percpu(*new->scratch_aligned
);
1290 if (!new->scratch_aligned
)
1294 rcu_head_init(&new->rcu
);
1299 for (i
= 0; i
< old
->field_count
; i
++) {
1300 unsigned long *new_lt
;
1302 memcpy(dst
, src
, offsetof(struct nft_pipapo_field
, lt
));
1304 new_lt
= kvzalloc(src
->groups
* NFT_PIPAPO_BUCKETS(src
->bb
) *
1305 src
->bsize
* sizeof(*dst
->lt
) +
1306 NFT_PIPAPO_ALIGN_HEADROOM
,
1311 NFT_PIPAPO_LT_ASSIGN(dst
, new_lt
);
1313 memcpy(NFT_PIPAPO_LT_ALIGN(new_lt
),
1314 NFT_PIPAPO_LT_ALIGN(src
->lt
),
1315 src
->bsize
* sizeof(*dst
->lt
) *
1316 src
->groups
* NFT_PIPAPO_BUCKETS(src
->bb
));
1318 dst
->mt
= kvmalloc(src
->rules
* sizeof(*src
->mt
), GFP_KERNEL
);
1322 memcpy(dst
->mt
, src
->mt
, src
->rules
* sizeof(*src
->mt
));
1332 for (dst
--; i
> 0; i
--) {
1337 #ifdef NFT_PIPAPO_ALIGN
1338 free_percpu(new->scratch_aligned
);
1341 free_percpu(new->scratch
);
1344 return ERR_PTR(-ENOMEM
);
1348 * pipapo_rules_same_key() - Get number of rules originated from the same entry
1349 * @f: Field containing mapping table
1350 * @first: Index of first rule in set of rules mapping to same entry
1352 * Using the fact that all rules in a field that originated from the same entry
1353 * will map to the same set of rules in the next field, or to the same element
1354 * reference, return the cardinality of the set of rules that originated from
1355 * the same entry as the rule with index @first, @first rule included.
1359 * field #0 0 1 2 3 4
1360 * map to: 0 1 2-4 2-4 5-9
1366 * in field #1 0 1 2 3 4 5 ...
1368 * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1369 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1371 * For the last field in a set, we can rely on associated entries to map to the
1372 * same element references.
1374 * Return: Number of rules that originated from the same entry as @first.
1376 static int pipapo_rules_same_key(struct nft_pipapo_field
*f
, int first
)
1378 struct nft_pipapo_elem
*e
= NULL
; /* Keep gcc happy */
1381 for (r
= first
; r
< f
->rules
; r
++) {
1382 if (r
!= first
&& e
!= f
->mt
[r
].e
)
1395 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1396 * @mt: Mapping array
1397 * @rules: Original amount of rules in mapping table
1398 * @start: First rule index to be removed
1399 * @n: Amount of rules to be removed
1400 * @to_offset: First rule index, in next field, this group of rules maps to
1401 * @is_last: If this is the last field, delete reference from mapping array
1403 * This is used to unmap rules from the mapping table for a single field,
1404 * maintaining consistency and compactness for the existing ones.
1406 * In pictures: let's assume that we want to delete rules 2 and 3 from the
1407 * following mapping array:
1411 * map to: 4-10 4-10 11-15 11-15 16-18
1413 * the result will be:
1417 * map to: 4-10 4-10 11-13
1419 * for fields before the last one. In case this is the mapping table for the
1420 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1424 * element pointers: 0x42 0x42 0x33 0x33 0x44
1426 * the result will be:
1430 * element pointers: 0x42 0x42 0x44
1432 static void pipapo_unmap(union nft_pipapo_map_bucket
*mt
, int rules
,
1433 int start
, int n
, int to_offset
, bool is_last
)
1437 memmove(mt
+ start
, mt
+ start
+ n
, (rules
- start
- n
) * sizeof(*mt
));
1438 memset(mt
+ rules
- n
, 0, n
* sizeof(*mt
));
1443 for (i
= start
; i
< rules
- n
; i
++)
1444 mt
[i
].to
-= to_offset
;
1448 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1450 * @rulemap: Table of rule maps, arrays of first rule and amount of rules
1451 * in next field a given entry maps to, for each field
1453 * For each rule in lookup table buckets mapping to this set of rules, drop
1454 * all bits set in lookup table mapping. In pictures, assuming we want to drop
1455 * rules 0 and 1 from this lookup table:
1458 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1465 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1466 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
1468 * rule 2 becomes rule 0, and the result will be:
1471 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1481 * once this is done, call unmap() to drop all the corresponding rule references
1482 * from mapping tables.
1484 static void pipapo_drop(struct nft_pipapo_match
*m
,
1485 union nft_pipapo_map_bucket rulemap
[])
1487 struct nft_pipapo_field
*f
;
1490 nft_pipapo_for_each_field(f
, i
, m
) {
1493 for (g
= 0; g
< f
->groups
; g
++) {
1497 pos
= NFT_PIPAPO_LT_ALIGN(f
->lt
) + g
*
1498 NFT_PIPAPO_BUCKETS(f
->bb
) * f
->bsize
;
1500 for (b
= 0; b
< NFT_PIPAPO_BUCKETS(f
->bb
); b
++) {
1501 bitmap_cut(pos
, pos
, rulemap
[i
].to
,
1503 f
->bsize
* BITS_PER_LONG
);
1509 pipapo_unmap(f
->mt
, f
->rules
, rulemap
[i
].to
, rulemap
[i
].n
,
1510 rulemap
[i
+ 1].n
, i
== m
->field_count
- 1);
1511 if (pipapo_resize(f
, f
->rules
, f
->rules
- rulemap
[i
].n
)) {
1512 /* We can ignore this, a failure to shrink tables down
1513 * doesn't make tables invalid.
1517 f
->rules
-= rulemap
[i
].n
;
1519 pipapo_lt_bits_adjust(f
);
1524 * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1525 * @set: nftables API set representation
1528 static void pipapo_gc(const struct nft_set
*set
, struct nft_pipapo_match
*m
)
1530 struct nft_pipapo
*priv
= nft_set_priv(set
);
1531 int rules_f0
, first_rule
= 0;
1533 while ((rules_f0
= pipapo_rules_same_key(m
->f
, first_rule
))) {
1534 union nft_pipapo_map_bucket rulemap
[NFT_PIPAPO_MAX_FIELDS
];
1535 struct nft_pipapo_field
*f
;
1536 struct nft_pipapo_elem
*e
;
1537 int i
, start
, rules_fx
;
1540 rules_fx
= rules_f0
;
1542 nft_pipapo_for_each_field(f
, i
, m
) {
1543 rulemap
[i
].to
= start
;
1544 rulemap
[i
].n
= rules_fx
;
1546 if (i
< m
->field_count
- 1) {
1547 rules_fx
= f
->mt
[start
].n
;
1548 start
= f
->mt
[start
].to
;
1552 /* Pick the last field, and its last index */
1555 e
= f
->mt
[rulemap
[i
].to
].e
;
1556 if (nft_set_elem_expired(&e
->ext
) &&
1557 !nft_set_elem_mark_busy(&e
->ext
)) {
1559 pipapo_drop(m
, rulemap
);
1562 nft_set_elem_destroy(set
, e
, true);
1564 /* And check again current first rule, which is now the
1565 * first we haven't checked.
1568 first_rule
+= rules_f0
;
1572 priv
->last_gc
= jiffies
;
1576 * pipapo_free_fields() - Free per-field tables contained in matching data
1579 static void pipapo_free_fields(struct nft_pipapo_match
*m
)
1581 struct nft_pipapo_field
*f
;
1584 nft_pipapo_for_each_field(f
, i
, m
) {
1591 * pipapo_reclaim_match - RCU callback to free fields from old matching data
1594 static void pipapo_reclaim_match(struct rcu_head
*rcu
)
1596 struct nft_pipapo_match
*m
;
1599 m
= container_of(rcu
, struct nft_pipapo_match
, rcu
);
1601 for_each_possible_cpu(i
)
1602 kfree(*per_cpu_ptr(m
->scratch
, i
));
1604 #ifdef NFT_PIPAPO_ALIGN
1605 free_percpu(m
->scratch_aligned
);
1607 free_percpu(m
->scratch
);
1609 pipapo_free_fields(m
);
1615 * pipapo_commit() - Replace lookup data with current working copy
1616 * @set: nftables API set representation
1618 * While at it, check if we should perform garbage collection on the working
1619 * copy before committing it for lookup, and don't replace the table if the
1620 * working copy doesn't have pending changes.
1622 * We also need to create a new working copy for subsequent insertions and
1625 static void pipapo_commit(const struct nft_set
*set
)
1627 struct nft_pipapo
*priv
= nft_set_priv(set
);
1628 struct nft_pipapo_match
*new_clone
, *old
;
1630 if (time_after_eq(jiffies
, priv
->last_gc
+ nft_set_gc_interval(set
)))
1631 pipapo_gc(set
, priv
->clone
);
1636 new_clone
= pipapo_clone(priv
->clone
);
1637 if (IS_ERR(new_clone
))
1640 priv
->dirty
= false;
1642 old
= rcu_access_pointer(priv
->match
);
1643 rcu_assign_pointer(priv
->match
, priv
->clone
);
1645 call_rcu(&old
->rcu
, pipapo_reclaim_match
);
1647 priv
->clone
= new_clone
;
1651 * nft_pipapo_activate() - Mark element reference as active given key, commit
1652 * @net: Network namespace
1653 * @set: nftables API set representation
1654 * @elem: nftables API element representation containing key data
1656 * On insertion, elements are added to a copy of the matching data currently
1657 * in use for lookups, and not directly inserted into current lookup data, so
1658 * we'll take care of that by calling pipapo_commit() here. Both
1659 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1660 * element, hence we can't purpose either one as a real commit operation.
1662 static void nft_pipapo_activate(const struct net
*net
,
1663 const struct nft_set
*set
,
1664 const struct nft_set_elem
*elem
)
1666 struct nft_pipapo_elem
*e
;
1668 e
= pipapo_get(net
, set
, (const u8
*)elem
->key
.val
.data
, 0);
1672 nft_set_elem_change_active(net
, set
, &e
->ext
);
1673 nft_set_elem_clear_busy(&e
->ext
);
1679 * pipapo_deactivate() - Check that element is in set, mark as inactive
1680 * @net: Network namespace
1681 * @set: nftables API set representation
1682 * @data: Input key data
1683 * @ext: nftables API extension pointer, used to check for end element
1685 * This is a convenience function that can be called from both
1686 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1689 * Return: deactivated element if found, NULL otherwise.
1691 static void *pipapo_deactivate(const struct net
*net
, const struct nft_set
*set
,
1692 const u8
*data
, const struct nft_set_ext
*ext
)
1694 struct nft_pipapo_elem
*e
;
1696 e
= pipapo_get(net
, set
, data
, nft_genmask_next(net
));
1700 nft_set_elem_change_active(net
, set
, &e
->ext
);
1706 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1707 * @net: Network namespace
1708 * @set: nftables API set representation
1709 * @elem: nftables API element representation containing key data
1711 * Return: deactivated element if found, NULL otherwise.
1713 static void *nft_pipapo_deactivate(const struct net
*net
,
1714 const struct nft_set
*set
,
1715 const struct nft_set_elem
*elem
)
1717 const struct nft_set_ext
*ext
= nft_set_elem_ext(set
, elem
->priv
);
1719 return pipapo_deactivate(net
, set
, (const u8
*)elem
->key
.val
.data
, ext
);
1723 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1724 * @net: Network namespace
1725 * @set: nftables API set representation
1726 * @elem: nftables API element representation containing key data
1728 * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1729 * different interface, and it's also called once for each element in a set
1730 * being flushed, so we can't implement, strictly speaking, a flush operation,
1731 * which would otherwise be as simple as allocating an empty copy of the
1734 * Note that we could in theory do that, mark the set as flushed, and ignore
1735 * subsequent calls, but we would leak all the elements after the first one,
1736 * because they wouldn't then be freed as result of API calls.
1738 * Return: true if element was found and deactivated.
1740 static bool nft_pipapo_flush(const struct net
*net
, const struct nft_set
*set
,
1743 struct nft_pipapo_elem
*e
= elem
;
1745 return pipapo_deactivate(net
, set
, (const u8
*)nft_set_ext_key(&e
->ext
),
1750 * pipapo_get_boundaries() - Get byte interval for associated rules
1751 * @f: Field including lookup table
1752 * @first_rule: First rule (lowest index)
1753 * @rule_count: Number of associated rules
1754 * @left: Byte expression for left boundary (start of range)
1755 * @right: Byte expression for right boundary (end of range)
1757 * Given the first rule and amount of rules that originated from the same entry,
1758 * build the original range associated with the entry, and calculate the length
1759 * of the originating netmask.
1764 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1771 * 6 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1772 * 7 1,2 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1774 * this is the lookup table corresponding to the IPv4 range
1775 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1776 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1778 * This function fills @left and @right with the byte values of the leftmost
1779 * and rightmost bucket indices for the lowest and highest rule indices,
1780 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1782 * left: < 12, 0, 10, 8, 0, 1, 0, 0 >
1783 * right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1784 * corresponding to bytes:
1785 * left: < 192, 168, 1, 0 >
1786 * right: < 192, 168, 2, 1 >
1787 * with mask length irrelevant here, unused on return, as the range is already
1788 * defined by its start and end points. The mask length is relevant for a single
1789 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1790 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1791 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1792 * between leftmost and rightmost bucket indices for each group, would be 24.
1794 * Return: mask length, in bits.
1796 static int pipapo_get_boundaries(struct nft_pipapo_field
*f
, int first_rule
,
1797 int rule_count
, u8
*left
, u8
*right
)
1799 int g
, mask_len
= 0, bit_offset
= 0;
1800 u8
*l
= left
, *r
= right
;
1802 for (g
= 0; g
< f
->groups
; g
++) {
1807 for (b
= 0; b
< NFT_PIPAPO_BUCKETS(f
->bb
); b
++) {
1810 pos
= NFT_PIPAPO_LT_ALIGN(f
->lt
) +
1811 (g
* NFT_PIPAPO_BUCKETS(f
->bb
) + b
) * f
->bsize
;
1812 if (test_bit(first_rule
, pos
) && x0
== -1)
1814 if (test_bit(first_rule
+ rule_count
- 1, pos
))
1818 *l
|= x0
<< (BITS_PER_BYTE
- f
->bb
- bit_offset
);
1819 *r
|= x1
<< (BITS_PER_BYTE
- f
->bb
- bit_offset
);
1821 bit_offset
+= f
->bb
;
1822 if (bit_offset
>= BITS_PER_BYTE
) {
1823 bit_offset
%= BITS_PER_BYTE
;
1830 else if (x1
- x0
== 1)
1832 else if (x1
- x0
== 3)
1834 else if (x1
- x0
== 7)
1842 * pipapo_match_field() - Match rules against byte ranges
1843 * @f: Field including the lookup table
1844 * @first_rule: First of associated rules originating from same entry
1845 * @rule_count: Amount of associated rules
1846 * @start: Start of range to be matched
1847 * @end: End of range to be matched
1849 * Return: true on match, false otherwise.
1851 static bool pipapo_match_field(struct nft_pipapo_field
*f
,
1852 int first_rule
, int rule_count
,
1853 const u8
*start
, const u8
*end
)
1855 u8 right
[NFT_PIPAPO_MAX_BYTES
] = { 0 };
1856 u8 left
[NFT_PIPAPO_MAX_BYTES
] = { 0 };
1858 pipapo_get_boundaries(f
, first_rule
, rule_count
, left
, right
);
1860 return !memcmp(start
, left
,
1861 f
->groups
/ NFT_PIPAPO_GROUPS_PER_BYTE(f
)) &&
1862 !memcmp(end
, right
, f
->groups
/ NFT_PIPAPO_GROUPS_PER_BYTE(f
));
1866 * nft_pipapo_remove() - Remove element given key, commit
1867 * @net: Network namespace
1868 * @set: nftables API set representation
1869 * @elem: nftables API element representation containing key data
1871 * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1872 * API, but it's called once per element in the pending transaction, so we can't
1873 * implement this as a single commit operation. Closest we can get is to remove
1874 * the matched element here, if any, and commit the updated matching data.
1876 static void nft_pipapo_remove(const struct net
*net
, const struct nft_set
*set
,
1877 const struct nft_set_elem
*elem
)
1879 struct nft_pipapo
*priv
= nft_set_priv(set
);
1880 struct nft_pipapo_match
*m
= priv
->clone
;
1881 struct nft_pipapo_elem
*e
= elem
->priv
;
1882 int rules_f0
, first_rule
= 0;
1885 data
= (const u8
*)nft_set_ext_key(&e
->ext
);
1887 e
= pipapo_get(net
, set
, data
, 0);
1891 while ((rules_f0
= pipapo_rules_same_key(m
->f
, first_rule
))) {
1892 union nft_pipapo_map_bucket rulemap
[NFT_PIPAPO_MAX_FIELDS
];
1893 const u8
*match_start
, *match_end
;
1894 struct nft_pipapo_field
*f
;
1895 int i
, start
, rules_fx
;
1898 match_end
= (const u8
*)nft_set_ext_key_end(&e
->ext
)->data
;
1901 rules_fx
= rules_f0
;
1903 nft_pipapo_for_each_field(f
, i
, m
) {
1904 if (!pipapo_match_field(f
, start
, rules_fx
,
1905 match_start
, match_end
))
1908 rulemap
[i
].to
= start
;
1909 rulemap
[i
].n
= rules_fx
;
1911 rules_fx
= f
->mt
[start
].n
;
1912 start
= f
->mt
[start
].to
;
1914 match_start
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1915 match_end
+= NFT_PIPAPO_GROUPS_PADDED_SIZE(f
);
1918 if (i
== m
->field_count
) {
1920 pipapo_drop(m
, rulemap
);
1925 first_rule
+= rules_f0
;
1930 * nft_pipapo_walk() - Walk over elements
1931 * @ctx: nftables API context
1932 * @set: nftables API set representation
1935 * As elements are referenced in the mapping array for the last field, directly
1936 * scan that array: there's no need to follow rule mappings from the first
1939 static void nft_pipapo_walk(const struct nft_ctx
*ctx
, struct nft_set
*set
,
1940 struct nft_set_iter
*iter
)
1942 struct nft_pipapo
*priv
= nft_set_priv(set
);
1943 struct nft_pipapo_match
*m
;
1944 struct nft_pipapo_field
*f
;
1948 m
= rcu_dereference(priv
->match
);
1953 for (i
= 0, f
= m
->f
; i
< m
->field_count
- 1; i
++, f
++)
1956 for (r
= 0; r
< f
->rules
; r
++) {
1957 struct nft_pipapo_elem
*e
;
1958 struct nft_set_elem elem
;
1960 if (r
< f
->rules
- 1 && f
->mt
[r
+ 1].e
== f
->mt
[r
].e
)
1963 if (iter
->count
< iter
->skip
)
1967 if (nft_set_elem_expired(&e
->ext
))
1972 iter
->err
= iter
->fn(ctx
, set
, iter
, &elem
);
1985 * nft_pipapo_privsize() - Return the size of private data for the set
1986 * @nla: netlink attributes, ignored as size doesn't depend on them
1987 * @desc: Set description, ignored as size doesn't depend on it
1989 * Return: size of private data for this set implementation, in bytes
1991 static u64
nft_pipapo_privsize(const struct nlattr
* const nla
[],
1992 const struct nft_set_desc
*desc
)
1994 return sizeof(struct nft_pipapo
);
1998 * nft_pipapo_estimate() - Set size, space and lookup complexity
1999 * @desc: Set description, element count and field description used
2000 * @features: Flags: NFT_SET_INTERVAL needs to be there
2001 * @est: Storage for estimation data
2003 * Return: true if set description is compatible, false otherwise
2005 static bool nft_pipapo_estimate(const struct nft_set_desc
*desc
, u32 features
,
2006 struct nft_set_estimate
*est
)
2008 if (!(features
& NFT_SET_INTERVAL
) ||
2009 desc
->field_count
< NFT_PIPAPO_MIN_FIELDS
)
2012 est
->size
= pipapo_estimate_size(desc
);
2016 est
->lookup
= NFT_SET_CLASS_O_LOG_N
;
2018 est
->space
= NFT_SET_CLASS_O_N
;
2024 * nft_pipapo_init() - Initialise data for a set instance
2025 * @set: nftables API set representation
2026 * @desc: Set description
2027 * @nla: netlink attributes
2029 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
2030 * attributes, initialise internal set parameters, current instance of matching
2031 * data and a copy for subsequent insertions.
2033 * Return: 0 on success, negative error code on failure.
2035 static int nft_pipapo_init(const struct nft_set
*set
,
2036 const struct nft_set_desc
*desc
,
2037 const struct nlattr
* const nla
[])
2039 struct nft_pipapo
*priv
= nft_set_priv(set
);
2040 struct nft_pipapo_match
*m
;
2041 struct nft_pipapo_field
*f
;
2042 int err
, i
, field_count
;
2044 field_count
= desc
->field_count
? : 1;
2046 if (field_count
> NFT_PIPAPO_MAX_FIELDS
)
2049 m
= kmalloc(sizeof(*priv
->match
) + sizeof(*f
) * field_count
,
2054 m
->field_count
= field_count
;
2057 m
->scratch
= alloc_percpu(unsigned long *);
2062 for_each_possible_cpu(i
)
2063 *per_cpu_ptr(m
->scratch
, i
) = NULL
;
2065 #ifdef NFT_PIPAPO_ALIGN
2066 m
->scratch_aligned
= alloc_percpu(unsigned long *);
2067 if (!m
->scratch_aligned
) {
2071 for_each_possible_cpu(i
)
2072 *per_cpu_ptr(m
->scratch_aligned
, i
) = NULL
;
2075 rcu_head_init(&m
->rcu
);
2077 nft_pipapo_for_each_field(f
, i
, m
) {
2078 int len
= desc
->field_len
[i
] ? : set
->klen
;
2080 f
->bb
= NFT_PIPAPO_GROUP_BITS_INIT
;
2081 f
->groups
= len
* NFT_PIPAPO_GROUPS_PER_BYTE(f
);
2083 priv
->width
+= round_up(len
, sizeof(u32
));
2087 NFT_PIPAPO_LT_ASSIGN(f
, NULL
);
2091 /* Create an initial clone of matching data for next insertion */
2092 priv
->clone
= pipapo_clone(m
);
2093 if (IS_ERR(priv
->clone
)) {
2094 err
= PTR_ERR(priv
->clone
);
2098 priv
->dirty
= false;
2100 rcu_assign_pointer(priv
->match
, m
);
2105 #ifdef NFT_PIPAPO_ALIGN
2106 free_percpu(m
->scratch_aligned
);
2108 free_percpu(m
->scratch
);
2116 * nft_pipapo_destroy() - Free private data for set and all committed elements
2117 * @set: nftables API set representation
2119 static void nft_pipapo_destroy(const struct nft_set
*set
)
2121 struct nft_pipapo
*priv
= nft_set_priv(set
);
2122 struct nft_pipapo_match
*m
;
2123 struct nft_pipapo_field
*f
;
2126 m
= rcu_dereference_protected(priv
->match
, true);
2130 for (i
= 0, f
= m
->f
; i
< m
->field_count
- 1; i
++, f
++)
2133 for (r
= 0; r
< f
->rules
; r
++) {
2134 struct nft_pipapo_elem
*e
;
2136 if (r
< f
->rules
- 1 && f
->mt
[r
+ 1].e
== f
->mt
[r
].e
)
2141 nft_set_elem_destroy(set
, e
, true);
2144 #ifdef NFT_PIPAPO_ALIGN
2145 free_percpu(m
->scratch_aligned
);
2147 for_each_possible_cpu(cpu
)
2148 kfree(*per_cpu_ptr(m
->scratch
, cpu
));
2149 free_percpu(m
->scratch
);
2150 pipapo_free_fields(m
);
2156 #ifdef NFT_PIPAPO_ALIGN
2157 free_percpu(priv
->clone
->scratch_aligned
);
2159 for_each_possible_cpu(cpu
)
2160 kfree(*per_cpu_ptr(priv
->clone
->scratch
, cpu
));
2161 free_percpu(priv
->clone
->scratch
);
2163 pipapo_free_fields(priv
->clone
);
2170 * nft_pipapo_gc_init() - Initialise garbage collection
2171 * @set: nftables API set representation
2173 * Instead of actually setting up a periodic work for garbage collection, as
2174 * this operation requires a swap of matching data with the working copy, we'll
2175 * do that opportunistically with other commit operations if the interval is
2176 * elapsed, so we just need to set the current jiffies timestamp here.
2178 static void nft_pipapo_gc_init(const struct nft_set
*set
)
2180 struct nft_pipapo
*priv
= nft_set_priv(set
);
2182 priv
->last_gc
= jiffies
;
2185 const struct nft_set_type nft_set_pipapo_type
= {
2186 .features
= NFT_SET_INTERVAL
| NFT_SET_MAP
| NFT_SET_OBJECT
|
2189 .lookup
= nft_pipapo_lookup
,
2190 .insert
= nft_pipapo_insert
,
2191 .activate
= nft_pipapo_activate
,
2192 .deactivate
= nft_pipapo_deactivate
,
2193 .flush
= nft_pipapo_flush
,
2194 .remove
= nft_pipapo_remove
,
2195 .walk
= nft_pipapo_walk
,
2196 .get
= nft_pipapo_get
,
2197 .privsize
= nft_pipapo_privsize
,
2198 .estimate
= nft_pipapo_estimate
,
2199 .init
= nft_pipapo_init
,
2200 .destroy
= nft_pipapo_destroy
,
2201 .gc_init
= nft_pipapo_gc_init
,
2202 .elemsize
= offsetof(struct nft_pipapo_elem
, ext
),
2206 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2207 const struct nft_set_type nft_set_pipapo_avx2_type
= {
2208 .features
= NFT_SET_INTERVAL
| NFT_SET_MAP
| NFT_SET_OBJECT
|
2211 .lookup
= nft_pipapo_avx2_lookup
,
2212 .insert
= nft_pipapo_insert
,
2213 .activate
= nft_pipapo_activate
,
2214 .deactivate
= nft_pipapo_deactivate
,
2215 .flush
= nft_pipapo_flush
,
2216 .remove
= nft_pipapo_remove
,
2217 .walk
= nft_pipapo_walk
,
2218 .get
= nft_pipapo_get
,
2219 .privsize
= nft_pipapo_privsize
,
2220 .estimate
= nft_pipapo_avx2_estimate
,
2221 .init
= nft_pipapo_init
,
2222 .destroy
= nft_pipapo_destroy
,
2223 .gc_init
= nft_pipapo_gc_init
,
2224 .elemsize
= offsetof(struct nft_pipapo_elem
, ext
),