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 * http://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 * http://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/log2.h>
334 #include <linux/module.h>
335 #include <linux/netlink.h>
336 #include <linux/netfilter.h>
337 #include <linux/netfilter/nf_tables.h>
338 #include <net/netfilter/nf_tables_core.h>
339 #include <uapi/linux/netfilter/nf_tables.h>
340 #include <net/ipv6.h> /* For the maximum length of a field */
341 #include <linux/bitmap.h>
342 #include <linux/bitops.h>
344 /* Count of concatenated fields depends on count of 32-bit nftables registers */
345 #define NFT_PIPAPO_MAX_FIELDS NFT_REG32_COUNT
347 /* Largest supported field size */
348 #define NFT_PIPAPO_MAX_BYTES (sizeof(struct in6_addr))
349 #define NFT_PIPAPO_MAX_BITS (NFT_PIPAPO_MAX_BYTES * BITS_PER_BYTE)
351 /* Number of bits to be grouped together in lookup table buckets, arbitrary */
352 #define NFT_PIPAPO_GROUP_BITS 4
353 #define NFT_PIPAPO_GROUPS_PER_BYTE (BITS_PER_BYTE / NFT_PIPAPO_GROUP_BITS)
355 /* Fields are padded to 32 bits in input registers */
356 #define NFT_PIPAPO_GROUPS_PADDED_SIZE(x) \
357 (round_up((x) / NFT_PIPAPO_GROUPS_PER_BYTE, sizeof(u32)))
358 #define NFT_PIPAPO_GROUPS_PADDING(x) \
359 (NFT_PIPAPO_GROUPS_PADDED_SIZE((x)) - (x) / NFT_PIPAPO_GROUPS_PER_BYTE)
361 /* Number of buckets, given by 2 ^ n, with n grouped bits */
362 #define NFT_PIPAPO_BUCKETS (1 << NFT_PIPAPO_GROUP_BITS)
364 /* Each n-bit range maps to up to n * 2 rules */
365 #define NFT_PIPAPO_MAP_NBITS (const_ilog2(NFT_PIPAPO_MAX_BITS * 2))
367 /* Use the rest of mapping table buckets for rule indices, but it makes no sense
370 #if BITS_PER_LONG == 64
371 #define NFT_PIPAPO_MAP_TOBITS 32
373 #define NFT_PIPAPO_MAP_TOBITS (BITS_PER_LONG - NFT_PIPAPO_MAP_NBITS)
376 /* ...which gives us the highest allowed index for a rule */
377 #define NFT_PIPAPO_RULE0_MAX ((1UL << (NFT_PIPAPO_MAP_TOBITS - 1)) \
378 - (1UL << NFT_PIPAPO_MAP_NBITS))
380 #define nft_pipapo_for_each_field(field, index, match) \
381 for ((field) = (match)->f, (index) = 0; \
382 (index) < (match)->field_count; \
383 (index)++, (field)++)
386 * union nft_pipapo_map_bucket - Bucket of mapping table
387 * @to: First rule number (in next field) this rule maps to
388 * @n: Number of rules (in next field) this rule maps to
389 * @e: If there's no next field, pointer to element this rule maps to
391 union nft_pipapo_map_bucket {
393 #if BITS_PER_LONG == 64
394 static_assert(NFT_PIPAPO_MAP_TOBITS <= 32);
397 static_assert(NFT_PIPAPO_MAP_NBITS <= 32);
400 unsigned long to:NFT_PIPAPO_MAP_TOBITS;
401 unsigned long n:NFT_PIPAPO_MAP_NBITS;
404 struct nft_pipapo_elem *e;
408 * struct nft_pipapo_field - Lookup, mapping tables and related data for a field
409 * @groups: Amount of 4-bit groups
410 * @rules: Number of inserted rules
411 * @bsize: Size of each bucket in lookup table, in longs
412 * @lt: Lookup table: 'groups' rows of NFT_PIPAPO_BUCKETS buckets
413 * @mt: Mapping table: one bucket per rule
415 struct nft_pipapo_field {
420 union nft_pipapo_map_bucket *mt;
424 * struct nft_pipapo_match - Data used for lookup and matching
425 * @field_count Amount of fields in set
426 * @scratch: Preallocated per-CPU maps for partial matching results
427 * @bsize_max: Maximum lookup table bucket size of all fields, in longs
428 * @rcu Matching data is swapped on commits
429 * @f: Fields, with lookup and mapping tables
431 struct nft_pipapo_match {
433 unsigned long * __percpu *scratch;
436 struct nft_pipapo_field f[0];
439 /* Current working bitmap index, toggled between field matches */
440 static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index);
443 * struct nft_pipapo - Representation of a set
444 * @match: Currently in-use matching data
445 * @clone: Copy where pending insertions and deletions are kept
446 * @groups: Total amount of 4-bit groups for fields in this set
447 * @width: Total bytes to be matched for one packet, including padding
448 * @dirty: Working copy has pending insertions or deletions
449 * @last_gc: Timestamp of last garbage collection run, jiffies
452 struct nft_pipapo_match __rcu *match;
453 struct nft_pipapo_match *clone;
457 unsigned long last_gc;
460 struct nft_pipapo_elem;
463 * struct nft_pipapo_elem - API-facing representation of single set element
464 * @ext: nftables API extensions
466 struct nft_pipapo_elem {
467 struct nft_set_ext ext;
471 * pipapo_refill() - For each set bit, set bits from selected mapping table item
472 * @map: Bitmap to be scanned for set bits
473 * @len: Length of bitmap in longs
474 * @rules: Number of rules in field
475 * @dst: Destination bitmap
476 * @mt: Mapping table containing bit set specifiers
477 * @match_only: Find a single bit and return, don't fill
479 * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
481 * For each bit set in map, select the bucket from mapping table with index
482 * corresponding to the position of the bit set. Use start bit and amount of
483 * bits specified in bucket to fill region in dst.
485 * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
487 static int pipapo_refill(unsigned long *map, int len, int rules,
488 unsigned long *dst, union nft_pipapo_map_bucket *mt,
491 unsigned long bitset;
494 for (k = 0; k < len; k++) {
497 unsigned long t = bitset & -bitset;
498 int r = __builtin_ctzl(bitset);
499 int i = k * BITS_PER_LONG + r;
501 if (unlikely(i >= rules)) {
507 bitmap_clear(map, i, 1);
513 bitmap_set(dst, mt[i].to, mt[i].n);
524 * nft_pipapo_lookup() - Lookup function
525 * @net: Network namespace
526 * @set: nftables API set representation
527 * @elem: nftables API element representation containing key data
528 * @ext: nftables API extension pointer, filled with matching reference
530 * For more details, see DOC: Theory of Operation.
532 * Return: true on match, false otherwise.
534 static bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
535 const u32 *key, const struct nft_set_ext **ext)
537 struct nft_pipapo *priv = nft_set_priv(set);
538 unsigned long *res_map, *fill_map;
539 u8 genmask = nft_genmask_cur(net);
540 const u8 *rp = (const u8 *)key;
541 struct nft_pipapo_match *m;
542 struct nft_pipapo_field *f;
548 map_index = raw_cpu_read(nft_pipapo_scratch_index);
550 m = rcu_dereference(priv->match);
552 if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
555 res_map = *raw_cpu_ptr(m->scratch) + (map_index ? m->bsize_max : 0);
556 fill_map = *raw_cpu_ptr(m->scratch) + (map_index ? 0 : m->bsize_max);
558 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
560 nft_pipapo_for_each_field(f, i, m) {
561 bool last = i == m->field_count - 1;
562 unsigned long *lt = f->lt;
565 /* For each 4-bit group: select lookup table bucket depending on
566 * packet bytes value, then AND bucket value
568 for (group = 0; group < f->groups; group += 2) {
572 __bitmap_and(res_map, res_map, lt + v * f->bsize,
573 f->bsize * BITS_PER_LONG);
574 lt += f->bsize * NFT_PIPAPO_BUCKETS;
578 __bitmap_and(res_map, res_map, lt + v * f->bsize,
579 f->bsize * BITS_PER_LONG);
580 lt += f->bsize * NFT_PIPAPO_BUCKETS;
583 /* Now populate the bitmap for the next field, unless this is
584 * the last field, in which case return the matched 'ext'
587 * Now res_map contains the matching bitmap, and fill_map is the
588 * bitmap for the next field.
591 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
594 raw_cpu_write(nft_pipapo_scratch_index, map_index);
601 *ext = &f->mt[b].e->ext;
602 if (unlikely(nft_set_elem_expired(*ext) ||
603 !nft_set_elem_active(*ext, genmask)))
606 /* Last field: we're just returning the key without
607 * filling the initial bitmap for the next field, so the
608 * current inactive bitmap is clean and can be reused as
609 * *next* bitmap (not initial) for the next packet.
611 raw_cpu_write(nft_pipapo_scratch_index, map_index);
617 /* Swap bitmap indices: res_map is the initial bitmap for the
618 * next field, and fill_map is guaranteed to be all-zeroes at
621 map_index = !map_index;
622 swap(res_map, fill_map);
624 rp += NFT_PIPAPO_GROUPS_PADDING(f->groups);
633 * pipapo_get() - Get matching element reference given key data
634 * @net: Network namespace
635 * @set: nftables API set representation
636 * @data: Key data to be matched against existing elements
637 * @genmask: If set, check that element is active in given genmask
639 * This is essentially the same as the lookup function, except that it matches
640 * key data against the uncommitted copy and doesn't use preallocated maps for
643 * Return: pointer to &struct nft_pipapo_elem on match, error pointer otherwise.
645 static struct nft_pipapo_elem *pipapo_get(const struct net *net,
646 const struct nft_set *set,
647 const u8 *data, u8 genmask)
649 struct nft_pipapo_elem *ret = ERR_PTR(-ENOENT);
650 struct nft_pipapo *priv = nft_set_priv(set);
651 struct nft_pipapo_match *m = priv->clone;
652 unsigned long *res_map, *fill_map = NULL;
653 struct nft_pipapo_field *f;
656 res_map = kmalloc_array(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
658 ret = ERR_PTR(-ENOMEM);
662 fill_map = kcalloc(m->bsize_max, sizeof(*res_map), GFP_ATOMIC);
664 ret = ERR_PTR(-ENOMEM);
668 memset(res_map, 0xff, m->bsize_max * sizeof(*res_map));
670 nft_pipapo_for_each_field(f, i, m) {
671 bool last = i == m->field_count - 1;
672 unsigned long *lt = f->lt;
675 /* For each 4-bit group: select lookup table bucket depending on
676 * packet bytes value, then AND bucket value
678 for (group = 0; group < f->groups; group++) {
687 __bitmap_and(res_map, res_map, lt + v * f->bsize,
688 f->bsize * BITS_PER_LONG);
690 lt += f->bsize * NFT_PIPAPO_BUCKETS;
693 /* Now populate the bitmap for the next field, unless this is
694 * the last field, in which case return the matched 'ext'
697 * Now res_map contains the matching bitmap, and fill_map is the
698 * bitmap for the next field.
701 b = pipapo_refill(res_map, f->bsize, f->rules, fill_map, f->mt,
707 if (nft_set_elem_expired(&f->mt[b].e->ext) ||
709 !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
716 data += NFT_PIPAPO_GROUPS_PADDING(f->groups);
718 /* Swap bitmap indices: fill_map will be the initial bitmap for
719 * the next field (i.e. the new res_map), and res_map is
720 * guaranteed to be all-zeroes at this point, ready to be filled
721 * according to the next mapping table.
723 swap(res_map, fill_map);
733 * nft_pipapo_get() - Get matching element reference given key data
734 * @net: Network namespace
735 * @set: nftables API set representation
736 * @elem: nftables API element representation containing key data
739 void *nft_pipapo_get(const struct net *net, const struct nft_set *set,
740 const struct nft_set_elem *elem, unsigned int flags)
742 return pipapo_get(net, set, (const u8 *)elem->key.val.data,
743 nft_genmask_cur(net));
747 * pipapo_resize() - Resize lookup or mapping table, or both
748 * @f: Field containing lookup and mapping tables
749 * @old_rules: Previous amount of rules in field
750 * @rules: New amount of rules
752 * Increase, decrease or maintain tables size depending on new amount of rules,
753 * and copy data over. In case the new size is smaller, throw away data for
754 * highest-numbered rules.
756 * Return: 0 on success, -ENOMEM on allocation failure.
758 static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
760 long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
761 union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
762 size_t new_bucket_size, copy;
765 new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
767 if (new_bucket_size == f->bsize)
770 if (new_bucket_size > f->bsize)
773 copy = new_bucket_size;
775 new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS * new_bucket_size *
776 sizeof(*new_lt), GFP_KERNEL);
782 for (group = 0; group < f->groups; group++) {
783 for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS; bucket++) {
784 memcpy(new_p, old_p, copy * sizeof(*new_p));
788 if (new_bucket_size > f->bsize)
789 new_p += new_bucket_size - f->bsize;
791 old_p += f->bsize - new_bucket_size;
796 new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
802 memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
803 if (rules > old_rules) {
804 memset(new_mt + old_rules, 0,
805 (rules - old_rules) * sizeof(*new_mt));
809 f->bsize = new_bucket_size;
821 * pipapo_bucket_set() - Set rule bit in bucket given group and group value
822 * @f: Field containing lookup table
824 * @group: Group index
825 * @v: Value of bit group
827 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
832 pos = f->lt + f->bsize * NFT_PIPAPO_BUCKETS * group;
835 __set_bit(rule, pos);
839 * pipapo_insert() - Insert new rule in field given input key and mask length
840 * @f: Field containing lookup table
841 * @k: Input key for classification, without nftables padding
842 * @mask_bits: Length of mask; matches field length for non-ranged entry
844 * Insert a new rule reference in lookup buckets corresponding to k and
847 * Return: 1 on success (one rule inserted), negative error code on failure.
849 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
852 int rule = f->rules++, group, ret;
854 ret = pipapo_resize(f, f->rules - 1, f->rules);
858 for (group = 0; group < f->groups; group++) {
863 v = k[group / 2] & 0x0f;
865 v = k[group / 2] >> 4;
867 if (mask_bits >= (group + 1) * 4) {
869 pipapo_bucket_set(f, rule, group, v);
870 } else if (mask_bits <= group * 4) {
871 /* Completely masked */
872 for (i = 0; i < NFT_PIPAPO_BUCKETS; i++)
873 pipapo_bucket_set(f, rule, group, i);
875 /* The mask limit falls on this group */
876 mask = 0x0f >> (mask_bits - group * 4);
877 for (i = 0; i < NFT_PIPAPO_BUCKETS; i++) {
878 if ((i & ~mask) == (v & ~mask))
879 pipapo_bucket_set(f, rule, group, i);
888 * pipapo_step_diff() - Check if setting @step bit in netmask would change it
889 * @base: Mask we are expanding
890 * @step: Step bit for given expansion step
891 * @len: Total length of mask space (set and unset bits), bytes
893 * Convenience function for mask expansion.
895 * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
897 static bool pipapo_step_diff(u8 *base, int step, int len)
899 /* Network order, byte-addressed */
900 #ifdef __BIG_ENDIAN__
901 return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
903 return !(BIT(step % BITS_PER_BYTE) &
904 base[len - 1 - step / BITS_PER_BYTE]);
909 * pipapo_step_after_end() - Check if mask exceeds range end with given step
910 * @base: Mask we are expanding
912 * @step: Step bit for given expansion step, highest bit to be set
913 * @len: Total length of mask space (set and unset bits), bytes
915 * Convenience function for mask expansion.
917 * Return: true if mask exceeds range setting step bits, false otherwise.
919 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
922 u8 tmp[NFT_PIPAPO_MAX_BYTES];
925 memcpy(tmp, base, len);
927 /* Network order, byte-addressed */
928 for (i = 0; i <= step; i++)
929 #ifdef __BIG_ENDIAN__
930 tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
932 tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
935 return memcmp(tmp, end, len) > 0;
939 * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
940 * @base: Netmask base
941 * @step: Step bit to sum
942 * @len: Netmask length, bytes
944 static void pipapo_base_sum(u8 *base, int step, int len)
949 /* Network order, byte-addressed */
950 #ifdef __BIG_ENDIAN__
951 for (i = step / BITS_PER_BYTE; i < len; i++) {
953 for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
958 base[i] += 1 << (step % BITS_PER_BYTE);
968 * pipapo_expand() - Expand to composing netmasks, insert into lookup table
969 * @f: Field containing lookup table
970 * @start: Start of range
972 * @len: Length of value in bits
974 * Expand range to composing netmasks and insert corresponding rule references
977 * Return: number of inserted rules on success, negative error code on failure.
979 static int pipapo_expand(struct nft_pipapo_field *f,
980 const u8 *start, const u8 *end, int len)
982 int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
983 u8 base[NFT_PIPAPO_MAX_BYTES];
985 memcpy(base, start, bytes);
986 while (memcmp(base, end, bytes) <= 0) {
990 while (pipapo_step_diff(base, step, bytes)) {
991 if (pipapo_step_after_end(base, end, step, bytes))
997 pipapo_insert(f, base, 0);
1004 err = pipapo_insert(f, base, len - step);
1010 pipapo_base_sum(base, step, bytes);
1017 * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1018 * @m: Matching data, including mapping table
1019 * @map: Table of rule maps: array of first rule and amount of rules
1020 * in next field a given rule maps to, for each field
1021 * @ext: For last field, nft_set_ext pointer matching rules map to
1023 static void pipapo_map(struct nft_pipapo_match *m,
1024 union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1025 struct nft_pipapo_elem *e)
1027 struct nft_pipapo_field *f;
1030 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1031 for (j = 0; j < map[i].n; j++) {
1032 f->mt[map[i].to + j].to = map[i + 1].to;
1033 f->mt[map[i].to + j].n = map[i + 1].n;
1037 /* Last field: map to ext instead of mapping to next field */
1038 for (j = 0; j < map[i].n; j++)
1039 f->mt[map[i].to + j].e = e;
1043 * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1044 * @clone: Copy of matching data with pending insertions and deletions
1045 * @bsize_max Maximum bucket size, scratch maps cover two buckets
1047 * Return: 0 on success, -ENOMEM on failure.
1049 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1050 unsigned long bsize_max)
1054 for_each_possible_cpu(i) {
1055 unsigned long *scratch;
1057 scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2,
1058 GFP_KERNEL, cpu_to_node(i));
1060 /* On failure, there's no need to undo previous
1061 * allocations: this means that some scratch maps have
1062 * a bigger allocated size now (this is only called on
1063 * insertion), but the extra space won't be used by any
1064 * CPU as new elements are not inserted and m->bsize_max
1070 kfree(*per_cpu_ptr(clone->scratch, i));
1072 *per_cpu_ptr(clone->scratch, i) = scratch;
1079 * nft_pipapo_insert() - Validate and insert ranged elements
1080 * @net: Network namespace
1081 * @set: nftables API set representation
1082 * @elem: nftables API element representation containing key data
1083 * @ext2: Filled with pointer to &struct nft_set_ext in inserted element
1085 * Return: 0 on success, error pointer on failure.
1087 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1088 const struct nft_set_elem *elem,
1089 struct nft_set_ext **ext2)
1091 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1092 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1093 const u8 *start = (const u8 *)elem->key.val.data, *end;
1094 struct nft_pipapo_elem *e = elem->priv, *dup;
1095 struct nft_pipapo *priv = nft_set_priv(set);
1096 struct nft_pipapo_match *m = priv->clone;
1097 u8 genmask = nft_genmask_next(net);
1098 struct nft_pipapo_field *f;
1099 int i, bsize_max, err = 0;
1101 dup = pipapo_get(net, set, start, genmask);
1102 if (PTR_ERR(dup) == -ENOENT) {
1103 if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END)) {
1104 end = (const u8 *)nft_set_ext_key_end(ext)->data;
1105 dup = pipapo_get(net, set, end, nft_genmask_next(net));
1111 if (PTR_ERR(dup) != -ENOENT) {
1113 return PTR_ERR(dup);
1119 nft_pipapo_for_each_field(f, i, m) {
1120 const u8 *start_p = start, *end_p = end;
1122 if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
1125 if (memcmp(start_p, end_p,
1126 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) > 0)
1129 start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1130 end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1136 bsize_max = m->bsize_max;
1138 nft_pipapo_for_each_field(f, i, m) {
1141 rulemap[i].to = f->rules;
1143 ret = memcmp(start, end,
1144 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
1146 ret = pipapo_insert(f, start,
1147 f->groups * NFT_PIPAPO_GROUP_BITS);
1149 ret = pipapo_expand(f, start, end,
1150 f->groups * NFT_PIPAPO_GROUP_BITS);
1153 if (f->bsize > bsize_max)
1154 bsize_max = f->bsize;
1158 start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1159 end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1162 if (!*this_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1163 err = pipapo_realloc_scratch(m, bsize_max);
1167 this_cpu_write(nft_pipapo_scratch_index, false);
1169 m->bsize_max = bsize_max;
1174 pipapo_map(m, rulemap, e);
1180 * pipapo_clone() - Clone matching data to create new working copy
1181 * @old: Existing matching data
1183 * Return: copy of matching data passed as 'old', error pointer on failure
1185 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1187 struct nft_pipapo_field *dst, *src;
1188 struct nft_pipapo_match *new;
1191 new = kmalloc(sizeof(*new) + sizeof(*dst) * old->field_count,
1194 return ERR_PTR(-ENOMEM);
1196 new->field_count = old->field_count;
1197 new->bsize_max = old->bsize_max;
1199 new->scratch = alloc_percpu(*new->scratch);
1203 rcu_head_init(&new->rcu);
1208 for (i = 0; i < old->field_count; i++) {
1209 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1211 dst->lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS *
1212 src->bsize * sizeof(*dst->lt),
1217 memcpy(dst->lt, src->lt,
1218 src->bsize * sizeof(*dst->lt) *
1219 src->groups * NFT_PIPAPO_BUCKETS);
1221 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
1225 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1235 for (dst--; i > 0; i--) {
1240 free_percpu(new->scratch);
1244 return ERR_PTR(-ENOMEM);
1248 * pipapo_rules_same_key() - Get number of rules originated from the same entry
1249 * @f: Field containing mapping table
1250 * @first: Index of first rule in set of rules mapping to same entry
1252 * Using the fact that all rules in a field that originated from the same entry
1253 * will map to the same set of rules in the next field, or to the same element
1254 * reference, return the cardinality of the set of rules that originated from
1255 * the same entry as the rule with index @first, @first rule included.
1259 * field #0 0 1 2 3 4
1260 * map to: 0 1 2-4 2-4 5-9
1266 * in field #1 0 1 2 3 4 5 ...
1268 * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1269 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1271 * For the last field in a set, we can rely on associated entries to map to the
1272 * same element references.
1274 * Return: Number of rules that originated from the same entry as @first.
1276 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
1278 struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1281 for (r = first; r < f->rules; r++) {
1282 if (r != first && e != f->mt[r].e)
1295 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1296 * @mt: Mapping array
1297 * @rules: Original amount of rules in mapping table
1298 * @start: First rule index to be removed
1299 * @n: Amount of rules to be removed
1300 * @to_offset: First rule index, in next field, this group of rules maps to
1301 * @is_last: If this is the last field, delete reference from mapping array
1303 * This is used to unmap rules from the mapping table for a single field,
1304 * maintaining consistency and compactness for the existing ones.
1306 * In pictures: let's assume that we want to delete rules 2 and 3 from the
1307 * following mapping array:
1311 * map to: 4-10 4-10 11-15 11-15 16-18
1313 * the result will be:
1317 * map to: 4-10 4-10 11-13
1319 * for fields before the last one. In case this is the mapping table for the
1320 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1324 * element pointers: 0x42 0x42 0x33 0x33 0x44
1326 * the result will be:
1330 * element pointers: 0x42 0x42 0x44
1332 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
1333 int start, int n, int to_offset, bool is_last)
1337 memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1338 memset(mt + rules - n, 0, n * sizeof(*mt));
1343 for (i = start; i < rules - n; i++)
1344 mt[i].to -= to_offset;
1348 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1350 * @rulemap Table of rule maps, arrays of first rule and amount of rules
1351 * in next field a given entry maps to, for each field
1353 * For each rule in lookup table buckets mapping to this set of rules, drop
1354 * all bits set in lookup table mapping. In pictures, assuming we want to drop
1355 * rules 0 and 1 from this lookup table:
1358 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1365 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1366 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1
1368 * rule 2 becomes rule 0, and the result will be:
1371 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1381 * once this is done, call unmap() to drop all the corresponding rule references
1382 * from mapping tables.
1384 static void pipapo_drop(struct nft_pipapo_match *m,
1385 union nft_pipapo_map_bucket rulemap[])
1387 struct nft_pipapo_field *f;
1390 nft_pipapo_for_each_field(f, i, m) {
1393 for (g = 0; g < f->groups; g++) {
1397 pos = f->lt + g * NFT_PIPAPO_BUCKETS * f->bsize;
1399 for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
1400 bitmap_cut(pos, pos, rulemap[i].to,
1402 f->bsize * BITS_PER_LONG);
1408 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1409 rulemap[i + 1].n, i == m->field_count - 1);
1410 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1411 /* We can ignore this, a failure to shrink tables down
1412 * doesn't make tables invalid.
1416 f->rules -= rulemap[i].n;
1421 * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1422 * @set: nftables API set representation
1425 static void pipapo_gc(const struct nft_set *set, struct nft_pipapo_match *m)
1427 struct nft_pipapo *priv = nft_set_priv(set);
1428 int rules_f0, first_rule = 0;
1430 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1431 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1432 struct nft_pipapo_field *f;
1433 struct nft_pipapo_elem *e;
1434 int i, start, rules_fx;
1437 rules_fx = rules_f0;
1439 nft_pipapo_for_each_field(f, i, m) {
1440 rulemap[i].to = start;
1441 rulemap[i].n = rules_fx;
1443 if (i < m->field_count - 1) {
1444 rules_fx = f->mt[start].n;
1445 start = f->mt[start].to;
1449 /* Pick the last field, and its last index */
1452 e = f->mt[rulemap[i].to].e;
1453 if (nft_set_elem_expired(&e->ext) &&
1454 !nft_set_elem_mark_busy(&e->ext)) {
1456 pipapo_drop(m, rulemap);
1459 nft_set_elem_destroy(set, e, true);
1461 /* And check again current first rule, which is now the
1462 * first we haven't checked.
1465 first_rule += rules_f0;
1469 priv->last_gc = jiffies;
1473 * pipapo_free_fields() - Free per-field tables contained in matching data
1476 static void pipapo_free_fields(struct nft_pipapo_match *m)
1478 struct nft_pipapo_field *f;
1481 nft_pipapo_for_each_field(f, i, m) {
1488 * pipapo_reclaim_match - RCU callback to free fields from old matching data
1491 static void pipapo_reclaim_match(struct rcu_head *rcu)
1493 struct nft_pipapo_match *m;
1496 m = container_of(rcu, struct nft_pipapo_match, rcu);
1498 for_each_possible_cpu(i)
1499 kfree(*per_cpu_ptr(m->scratch, i));
1501 free_percpu(m->scratch);
1503 pipapo_free_fields(m);
1509 * pipapo_commit() - Replace lookup data with current working copy
1510 * @set: nftables API set representation
1512 * While at it, check if we should perform garbage collection on the working
1513 * copy before committing it for lookup, and don't replace the table if the
1514 * working copy doesn't have pending changes.
1516 * We also need to create a new working copy for subsequent insertions and
1519 static void pipapo_commit(const struct nft_set *set)
1521 struct nft_pipapo *priv = nft_set_priv(set);
1522 struct nft_pipapo_match *new_clone, *old;
1524 if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1525 pipapo_gc(set, priv->clone);
1530 new_clone = pipapo_clone(priv->clone);
1531 if (IS_ERR(new_clone))
1534 priv->dirty = false;
1536 old = rcu_access_pointer(priv->match);
1537 rcu_assign_pointer(priv->match, priv->clone);
1539 call_rcu(&old->rcu, pipapo_reclaim_match);
1541 priv->clone = new_clone;
1545 * nft_pipapo_activate() - Mark element reference as active given key, commit
1546 * @net: Network namespace
1547 * @set: nftables API set representation
1548 * @elem: nftables API element representation containing key data
1550 * On insertion, elements are added to a copy of the matching data currently
1551 * in use for lookups, and not directly inserted into current lookup data, so
1552 * we'll take care of that by calling pipapo_commit() here. Both
1553 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1554 * element, hence we can't purpose either one as a real commit operation.
1556 static void nft_pipapo_activate(const struct net *net,
1557 const struct nft_set *set,
1558 const struct nft_set_elem *elem)
1560 struct nft_pipapo_elem *e;
1562 e = pipapo_get(net, set, (const u8 *)elem->key.val.data, 0);
1566 nft_set_elem_change_active(net, set, &e->ext);
1567 nft_set_elem_clear_busy(&e->ext);
1573 * pipapo_deactivate() - Check that element is in set, mark as inactive
1574 * @net: Network namespace
1575 * @set: nftables API set representation
1576 * @data: Input key data
1577 * @ext: nftables API extension pointer, used to check for end element
1579 * This is a convenience function that can be called from both
1580 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1583 * Return: deactivated element if found, NULL otherwise.
1585 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
1586 const u8 *data, const struct nft_set_ext *ext)
1588 struct nft_pipapo_elem *e;
1590 e = pipapo_get(net, set, data, nft_genmask_next(net));
1594 nft_set_elem_change_active(net, set, &e->ext);
1600 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1601 * @net: Network namespace
1602 * @set: nftables API set representation
1603 * @elem: nftables API element representation containing key data
1605 * Return: deactivated element if found, NULL otherwise.
1607 static void *nft_pipapo_deactivate(const struct net *net,
1608 const struct nft_set *set,
1609 const struct nft_set_elem *elem)
1611 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1613 return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
1617 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1618 * @net: Network namespace
1619 * @set: nftables API set representation
1620 * @elem: nftables API element representation containing key data
1622 * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1623 * different interface, and it's also called once for each element in a set
1624 * being flushed, so we can't implement, strictly speaking, a flush operation,
1625 * which would otherwise be as simple as allocating an empty copy of the
1628 * Note that we could in theory do that, mark the set as flushed, and ignore
1629 * subsequent calls, but we would leak all the elements after the first one,
1630 * because they wouldn't then be freed as result of API calls.
1632 * Return: true if element was found and deactivated.
1634 static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1637 struct nft_pipapo_elem *e = elem;
1639 return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext),
1644 * pipapo_get_boundaries() - Get byte interval for associated rules
1645 * @f: Field including lookup table
1646 * @first_rule: First rule (lowest index)
1647 * @rule_count: Number of associated rules
1648 * @left: Byte expression for left boundary (start of range)
1649 * @right: Byte expression for right boundary (end of range)
1651 * Given the first rule and amount of rules that originated from the same entry,
1652 * build the original range associated with the entry, and calculate the length
1653 * of the originating netmask.
1658 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1665 * 6 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1666 * 7 1,2 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1668 * this is the lookup table corresponding to the IPv4 range
1669 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1670 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1672 * This function fills @left and @right with the byte values of the leftmost
1673 * and rightmost bucket indices for the lowest and highest rule indices,
1674 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1676 * left: < 12, 0, 10, 8, 0, 1, 0, 0 >
1677 * right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1678 * corresponding to bytes:
1679 * left: < 192, 168, 1, 0 >
1680 * right: < 192, 168, 2, 1 >
1681 * with mask length irrelevant here, unused on return, as the range is already
1682 * defined by its start and end points. The mask length is relevant for a single
1683 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1684 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1685 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1686 * between leftmost and rightmost bucket indices for each group, would be 24.
1688 * Return: mask length, in bits.
1690 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1691 int rule_count, u8 *left, u8 *right)
1693 u8 *l = left, *r = right;
1694 int g, mask_len = 0;
1696 for (g = 0; g < f->groups; g++) {
1701 for (b = 0; b < NFT_PIPAPO_BUCKETS; b++) {
1704 pos = f->lt + (g * NFT_PIPAPO_BUCKETS + b) * f->bsize;
1705 if (test_bit(first_rule, pos) && x0 == -1)
1707 if (test_bit(first_rule + rule_count - 1, pos))
1712 *(l++) |= x0 & 0x0f;
1713 *(r++) |= x1 & 0x0f;
1721 else if (x1 - x0 == 1)
1723 else if (x1 - x0 == 3)
1725 else if (x1 - x0 == 7)
1733 * pipapo_match_field() - Match rules against byte ranges
1734 * @f: Field including the lookup table
1735 * @first_rule: First of associated rules originating from same entry
1736 * @rule_count: Amount of associated rules
1737 * @start: Start of range to be matched
1738 * @end: End of range to be matched
1740 * Return: true on match, false otherwise.
1742 static bool pipapo_match_field(struct nft_pipapo_field *f,
1743 int first_rule, int rule_count,
1744 const u8 *start, const u8 *end)
1746 u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
1747 u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
1749 pipapo_get_boundaries(f, first_rule, rule_count, left, right);
1751 return !memcmp(start, left, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE) &&
1752 !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE);
1756 * nft_pipapo_remove() - Remove element given key, commit
1757 * @net: Network namespace
1758 * @set: nftables API set representation
1759 * @elem: nftables API element representation containing key data
1761 * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1762 * API, but it's called once per element in the pending transaction, so we can't
1763 * implement this as a single commit operation. Closest we can get is to remove
1764 * the matched element here, if any, and commit the updated matching data.
1766 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
1767 const struct nft_set_elem *elem)
1769 const u8 *data = (const u8 *)elem->key.val.data;
1770 struct nft_pipapo *priv = nft_set_priv(set);
1771 struct nft_pipapo_match *m = priv->clone;
1772 int rules_f0, first_rule = 0;
1773 struct nft_pipapo_elem *e;
1775 e = pipapo_get(net, set, data, 0);
1779 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1780 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1781 const u8 *match_start, *match_end;
1782 struct nft_pipapo_field *f;
1783 int i, start, rules_fx;
1786 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
1789 rules_fx = rules_f0;
1791 nft_pipapo_for_each_field(f, i, m) {
1792 if (!pipapo_match_field(f, start, rules_fx,
1793 match_start, match_end))
1796 rulemap[i].to = start;
1797 rulemap[i].n = rules_fx;
1799 rules_fx = f->mt[start].n;
1800 start = f->mt[start].to;
1802 match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1803 match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f->groups);
1806 if (i == m->field_count) {
1808 pipapo_drop(m, rulemap);
1813 first_rule += rules_f0;
1818 * nft_pipapo_walk() - Walk over elements
1819 * @ctx: nftables API context
1820 * @set: nftables API set representation
1823 * As elements are referenced in the mapping array for the last field, directly
1824 * scan that array: there's no need to follow rule mappings from the first
1827 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
1828 struct nft_set_iter *iter)
1830 struct nft_pipapo *priv = nft_set_priv(set);
1831 struct nft_pipapo_match *m;
1832 struct nft_pipapo_field *f;
1836 m = rcu_dereference(priv->match);
1841 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
1844 for (r = 0; r < f->rules; r++) {
1845 struct nft_pipapo_elem *e;
1846 struct nft_set_elem elem;
1848 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
1851 if (iter->count < iter->skip)
1855 if (nft_set_elem_expired(&e->ext))
1860 iter->err = iter->fn(ctx, set, iter, &elem);
1873 * nft_pipapo_privsize() - Return the size of private data for the set
1874 * @nla: netlink attributes, ignored as size doesn't depend on them
1875 * @desc: Set description, ignored as size doesn't depend on it
1877 * Return: size of private data for this set implementation, in bytes
1879 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
1880 const struct nft_set_desc *desc)
1882 return sizeof(struct nft_pipapo);
1886 * nft_pipapo_estimate() - Estimate set size, space and lookup complexity
1887 * @desc: Set description, element count and field description used here
1888 * @features: Flags: NFT_SET_INTERVAL needs to be there
1889 * @est: Storage for estimation data
1891 * The size for this set type can vary dramatically, as it depends on the number
1892 * of rules (composing netmasks) the entries expand to. We compute the worst
1895 * In general, for a non-ranged entry or a single composing netmask, we need
1896 * one bit in each of the sixteen NFT_PIPAPO_BUCKETS, for each 4-bit group (that
1897 * is, each input bit needs four bits of matching data), plus a bucket in the
1898 * mapping table for each field.
1900 * Return: true only for compatible range concatenations
1902 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
1903 struct nft_set_estimate *est)
1905 unsigned long entry_size;
1908 if (!(features & NFT_SET_INTERVAL) || desc->field_count <= 1)
1911 for (i = 0, entry_size = 0; i < desc->field_count; i++) {
1912 unsigned long rules;
1914 if (desc->field_len[i] > NFT_PIPAPO_MAX_BYTES)
1917 /* Worst-case ranges for each concatenated field: each n-bit
1918 * field can expand to up to n * 2 rules in each bucket, and
1919 * each rule also needs a mapping bucket.
1921 rules = ilog2(desc->field_len[i] * BITS_PER_BYTE) * 2;
1922 entry_size += rules * NFT_PIPAPO_BUCKETS / BITS_PER_BYTE;
1923 entry_size += rules * sizeof(union nft_pipapo_map_bucket);
1926 /* Rules in lookup and mapping tables are needed for each entry */
1927 est->size = desc->size * entry_size;
1928 if (est->size && div_u64(est->size, desc->size) != entry_size)
1931 est->size += sizeof(struct nft_pipapo) +
1932 sizeof(struct nft_pipapo_match) * 2;
1934 est->size += sizeof(struct nft_pipapo_field) * desc->field_count;
1936 est->lookup = NFT_SET_CLASS_O_LOG_N;
1938 est->space = NFT_SET_CLASS_O_N;
1944 * nft_pipapo_init() - Initialise data for a set instance
1945 * @set: nftables API set representation
1946 * @desc: Set description
1947 * @nla: netlink attributes
1949 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
1950 * attributes, initialise internal set parameters, current instance of matching
1951 * data and a copy for subsequent insertions.
1953 * Return: 0 on success, negative error code on failure.
1955 static int nft_pipapo_init(const struct nft_set *set,
1956 const struct nft_set_desc *desc,
1957 const struct nlattr * const nla[])
1959 struct nft_pipapo *priv = nft_set_priv(set);
1960 struct nft_pipapo_match *m;
1961 struct nft_pipapo_field *f;
1964 if (desc->field_count > NFT_PIPAPO_MAX_FIELDS)
1967 m = kmalloc(sizeof(*priv->match) + sizeof(*f) * desc->field_count,
1972 m->field_count = desc->field_count;
1975 m->scratch = alloc_percpu(unsigned long *);
1980 for_each_possible_cpu(i)
1981 *per_cpu_ptr(m->scratch, i) = NULL;
1983 rcu_head_init(&m->rcu);
1985 nft_pipapo_for_each_field(f, i, m) {
1986 f->groups = desc->field_len[i] * NFT_PIPAPO_GROUPS_PER_BYTE;
1987 priv->groups += f->groups;
1989 priv->width += round_up(desc->field_len[i], sizeof(u32));
1997 /* Create an initial clone of matching data for next insertion */
1998 priv->clone = pipapo_clone(m);
1999 if (IS_ERR(priv->clone)) {
2000 err = PTR_ERR(priv->clone);
2004 priv->dirty = false;
2006 rcu_assign_pointer(priv->match, m);
2011 free_percpu(m->scratch);
2018 * nft_pipapo_destroy() - Free private data for set and all committed elements
2019 * @set: nftables API set representation
2021 static void nft_pipapo_destroy(const struct nft_set *set)
2023 struct nft_pipapo *priv = nft_set_priv(set);
2024 struct nft_pipapo_match *m;
2025 struct nft_pipapo_field *f;
2028 m = rcu_dereference_protected(priv->match, true);
2032 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2035 for (r = 0; r < f->rules; r++) {
2036 struct nft_pipapo_elem *e;
2038 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2043 nft_set_elem_destroy(set, e, true);
2046 for_each_possible_cpu(cpu)
2047 kfree(*per_cpu_ptr(m->scratch, cpu));
2048 free_percpu(m->scratch);
2050 pipapo_free_fields(m);
2056 for_each_possible_cpu(cpu)
2057 kfree(*per_cpu_ptr(priv->clone->scratch, cpu));
2058 free_percpu(priv->clone->scratch);
2060 pipapo_free_fields(priv->clone);
2067 * nft_pipapo_gc_init() - Initialise garbage collection
2068 * @set: nftables API set representation
2070 * Instead of actually setting up a periodic work for garbage collection, as
2071 * this operation requires a swap of matching data with the working copy, we'll
2072 * do that opportunistically with other commit operations if the interval is
2073 * elapsed, so we just need to set the current jiffies timestamp here.
2075 static void nft_pipapo_gc_init(const struct nft_set *set)
2077 struct nft_pipapo *priv = nft_set_priv(set);
2079 priv->last_gc = jiffies;
2082 struct nft_set_type nft_set_pipapo_type __read_mostly = {
2083 .owner = THIS_MODULE,
2084 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2087 .lookup = nft_pipapo_lookup,
2088 .insert = nft_pipapo_insert,
2089 .activate = nft_pipapo_activate,
2090 .deactivate = nft_pipapo_deactivate,
2091 .flush = nft_pipapo_flush,
2092 .remove = nft_pipapo_remove,
2093 .walk = nft_pipapo_walk,
2094 .get = nft_pipapo_get,
2095 .privsize = nft_pipapo_privsize,
2096 .estimate = nft_pipapo_estimate,
2097 .init = nft_pipapo_init,
2098 .destroy = nft_pipapo_destroy,
2099 .gc_init = nft_pipapo_gc_init,
2100 .elemsize = offsetof(struct nft_pipapo_elem, ext),