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