~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/netfilter/nft_set_pipapo.c

Version: ~ [ linux-5.19-rc8 ] ~ [ linux-5.18.14 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.57 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.133 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.207 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.253 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.289 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.324 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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 /* Current working bitmap index, toggled between field matches */
346 static DEFINE_PER_CPU(bool, nft_pipapo_scratch_index);
347 
348 /**
349  * pipapo_refill() - For each set bit, set bits from selected mapping table item
350  * @map:        Bitmap to be scanned for set bits
351  * @len:        Length of bitmap in longs
352  * @rules:      Number of rules in field
353  * @dst:        Destination bitmap
354  * @mt:         Mapping table containing bit set specifiers
355  * @match_only: Find a single bit and return, don't fill
356  *
357  * Iteration over set bits with __builtin_ctzl(): Daniel Lemire, public domain.
358  *
359  * For each bit set in map, select the bucket from mapping table with index
360  * corresponding to the position of the bit set. Use start bit and amount of
361  * bits specified in bucket to fill region in dst.
362  *
363  * Return: -1 on no match, bit position on 'match_only', 0 otherwise.
364  */
365 int pipapo_refill(unsigned long *map, int len, int rules, unsigned long *dst,
366                   union nft_pipapo_map_bucket *mt, bool match_only)
367 {
368         unsigned long bitset;
369         int k, ret = -1;
370 
371         for (k = 0; k < len; k++) {
372                 bitset = map[k];
373                 while (bitset) {
374                         unsigned long t = bitset & -bitset;
375                         int r = __builtin_ctzl(bitset);
376                         int i = k * BITS_PER_LONG + r;
377 
378                         if (unlikely(i >= rules)) {
379                                 map[k] = 0;
380                                 return -1;
381                         }
382 
383                         if (match_only) {
384                                 bitmap_clear(map, i, 1);
385                                 return i;
386                         }
387 
388                         ret = 0;
389 
390                         bitmap_set(dst, mt[i].to, mt[i].n);
391 
392                         bitset ^= t;
393                 }
394                 map[k] = 0;
395         }
396 
397         return ret;
398 }
399 
400 /**
401  * nft_pipapo_lookup() - Lookup function
402  * @net:        Network namespace
403  * @set:        nftables API set representation
404  * @key:        nftables API element representation containing key data
405  * @ext:        nftables API extension pointer, filled with matching reference
406  *
407  * For more details, see DOC: Theory of Operation.
408  *
409  * Return: true on match, false otherwise.
410  */
411 bool nft_pipapo_lookup(const struct net *net, const struct nft_set *set,
412                        const u32 *key, const struct nft_set_ext **ext)
413 {
414         struct nft_pipapo *priv = nft_set_priv(set);
415         unsigned long *res_map, *fill_map;
416         u8 genmask = nft_genmask_cur(net);
417         const u8 *rp = (const u8 *)key;
418         struct nft_pipapo_match *m;
419         struct nft_pipapo_field *f;
420         bool map_index;
421         int i;
422 
423         local_bh_disable();
424 
425         map_index = raw_cpu_read(nft_pipapo_scratch_index);
426 
427         m = rcu_dereference(priv->match);
428 
429         if (unlikely(!m || !*raw_cpu_ptr(m->scratch)))
430                 goto out;
431 
432         res_map  = *raw_cpu_ptr(m->scratch) + (map_index ? m->bsize_max : 0);
433         fill_map = *raw_cpu_ptr(m->scratch) + (map_index ? 0 : m->bsize_max);
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                         raw_cpu_write(nft_pipapo_scratch_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                         raw_cpu_write(nft_pipapo_scratch_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                             (genmask &&
571                              !nft_set_elem_active(&f->mt[b].e->ext, genmask)))
572                                 goto next_match;
573 
574                         ret = f->mt[b].e;
575                         goto out;
576                 }
577 
578                 data += NFT_PIPAPO_GROUPS_PADDING(f);
579 
580                 /* Swap bitmap indices: fill_map will be the initial bitmap for
581                  * the next field (i.e. the new res_map), and res_map is
582                  * guaranteed to be all-zeroes at this point, ready to be filled
583                  * according to the next mapping table.
584                  */
585                 swap(res_map, fill_map);
586         }
587 
588 out:
589         kfree(fill_map);
590         kfree(res_map);
591         return ret;
592 }
593 
594 /**
595  * nft_pipapo_get() - Get matching element reference given key data
596  * @net:        Network namespace
597  * @set:        nftables API set representation
598  * @elem:       nftables API element representation containing key data
599  * @flags:      Unused
600  */
601 static void *nft_pipapo_get(const struct net *net, const struct nft_set *set,
602                             const struct nft_set_elem *elem, unsigned int flags)
603 {
604         return pipapo_get(net, set, (const u8 *)elem->key.val.data,
605                           nft_genmask_cur(net));
606 }
607 
608 /**
609  * pipapo_resize() - Resize lookup or mapping table, or both
610  * @f:          Field containing lookup and mapping tables
611  * @old_rules:  Previous amount of rules in field
612  * @rules:      New amount of rules
613  *
614  * Increase, decrease or maintain tables size depending on new amount of rules,
615  * and copy data over. In case the new size is smaller, throw away data for
616  * highest-numbered rules.
617  *
618  * Return: 0 on success, -ENOMEM on allocation failure.
619  */
620 static int pipapo_resize(struct nft_pipapo_field *f, int old_rules, int rules)
621 {
622         long *new_lt = NULL, *new_p, *old_lt = f->lt, *old_p;
623         union nft_pipapo_map_bucket *new_mt, *old_mt = f->mt;
624         size_t new_bucket_size, copy;
625         int group, bucket;
626 
627         new_bucket_size = DIV_ROUND_UP(rules, BITS_PER_LONG);
628 #ifdef NFT_PIPAPO_ALIGN
629         new_bucket_size = roundup(new_bucket_size,
630                                   NFT_PIPAPO_ALIGN / sizeof(*new_lt));
631 #endif
632 
633         if (new_bucket_size == f->bsize)
634                 goto mt;
635 
636         if (new_bucket_size > f->bsize)
637                 copy = f->bsize;
638         else
639                 copy = new_bucket_size;
640 
641         new_lt = kvzalloc(f->groups * NFT_PIPAPO_BUCKETS(f->bb) *
642                           new_bucket_size * sizeof(*new_lt) +
643                           NFT_PIPAPO_ALIGN_HEADROOM,
644                           GFP_KERNEL);
645         if (!new_lt)
646                 return -ENOMEM;
647 
648         new_p = NFT_PIPAPO_LT_ALIGN(new_lt);
649         old_p = NFT_PIPAPO_LT_ALIGN(old_lt);
650 
651         for (group = 0; group < f->groups; group++) {
652                 for (bucket = 0; bucket < NFT_PIPAPO_BUCKETS(f->bb); bucket++) {
653                         memcpy(new_p, old_p, copy * sizeof(*new_p));
654                         new_p += copy;
655                         old_p += copy;
656 
657                         if (new_bucket_size > f->bsize)
658                                 new_p += new_bucket_size - f->bsize;
659                         else
660                                 old_p += f->bsize - new_bucket_size;
661                 }
662         }
663 
664 mt:
665         new_mt = kvmalloc(rules * sizeof(*new_mt), GFP_KERNEL);
666         if (!new_mt) {
667                 kvfree(new_lt);
668                 return -ENOMEM;
669         }
670 
671         memcpy(new_mt, f->mt, min(old_rules, rules) * sizeof(*new_mt));
672         if (rules > old_rules) {
673                 memset(new_mt + old_rules, 0,
674                        (rules - old_rules) * sizeof(*new_mt));
675         }
676 
677         if (new_lt) {
678                 f->bsize = new_bucket_size;
679                 NFT_PIPAPO_LT_ASSIGN(f, new_lt);
680                 kvfree(old_lt);
681         }
682 
683         f->mt = new_mt;
684         kvfree(old_mt);
685 
686         return 0;
687 }
688 
689 /**
690  * pipapo_bucket_set() - Set rule bit in bucket given group and group value
691  * @f:          Field containing lookup table
692  * @rule:       Rule index
693  * @group:      Group index
694  * @v:          Value of bit group
695  */
696 static void pipapo_bucket_set(struct nft_pipapo_field *f, int rule, int group,
697                               int v)
698 {
699         unsigned long *pos;
700 
701         pos = NFT_PIPAPO_LT_ALIGN(f->lt);
702         pos += f->bsize * NFT_PIPAPO_BUCKETS(f->bb) * group;
703         pos += f->bsize * v;
704 
705         __set_bit(rule, pos);
706 }
707 
708 /**
709  * pipapo_lt_4b_to_8b() - Switch lookup table group width from 4 bits to 8 bits
710  * @old_groups: Number of current groups
711  * @bsize:      Size of one bucket, in longs
712  * @old_lt:     Pointer to the current lookup table
713  * @new_lt:     Pointer to the new, pre-allocated lookup table
714  *
715  * Each bucket with index b in the new lookup table, belonging to group g, is
716  * filled with the bit intersection between:
717  * - bucket with index given by the upper 4 bits of b, from group g, and
718  * - bucket with index given by the lower 4 bits of b, from group g + 1
719  *
720  * That is, given buckets from the new lookup table N(x, y) and the old lookup
721  * table O(x, y), with x bucket index, and y group index:
722  *
723  *      N(b, g) := O(b / 16, g) & O(b % 16, g + 1)
724  *
725  * This ensures equivalence of the matching results on lookup. Two examples in
726  * pictures:
727  *
728  *              bucket
729  *  group  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 ... 254 255
730  *    0                ^
731  *    1                |                                                 ^
732  *   ...             ( & )                                               |
733  *                  /     \                                              |
734  *                 /       \                                         .-( & )-.
735  *                /  bucket \                                        |       |
736  *      group  0 / 1   2   3 \ 4   5   6   7   8   9  10  11  12  13 |14  15 |
737  *        0     /             \                                      |       |
738  *        1                    \                                     |       |
739  *        2                                                          |     --'
740  *        3                                                          '-
741  *       ...
742  */
743 static void pipapo_lt_4b_to_8b(int old_groups, int bsize,
744                                unsigned long *old_lt, unsigned long *new_lt)
745 {
746         int g, b, i;
747 
748         for (g = 0; g < old_groups / 2; g++) {
749                 int src_g0 = g * 2, src_g1 = g * 2 + 1;
750 
751                 for (b = 0; b < NFT_PIPAPO_BUCKETS(8); b++) {
752                         int src_b0 = b / NFT_PIPAPO_BUCKETS(4);
753                         int src_b1 = b % NFT_PIPAPO_BUCKETS(4);
754                         int src_i0 = src_g0 * NFT_PIPAPO_BUCKETS(4) + src_b0;
755                         int src_i1 = src_g1 * NFT_PIPAPO_BUCKETS(4) + src_b1;
756 
757                         for (i = 0; i < bsize; i++) {
758                                 *new_lt = old_lt[src_i0 * bsize + i] &
759                                           old_lt[src_i1 * bsize + i];
760                                 new_lt++;
761                         }
762                 }
763         }
764 }
765 
766 /**
767  * pipapo_lt_8b_to_4b() - Switch lookup table group width from 8 bits to 4 bits
768  * @old_groups: Number of current groups
769  * @bsize:      Size of one bucket, in longs
770  * @old_lt:     Pointer to the current lookup table
771  * @new_lt:     Pointer to the new, pre-allocated lookup table
772  *
773  * Each bucket with index b in the new lookup table, belonging to group g, is
774  * filled with the bit union of:
775  * - all the buckets with index such that the upper four bits of the lower byte
776  *   equal b, from group g, with g odd
777  * - all the buckets with index such that the lower four bits equal b, from
778  *   group g, with g even
779  *
780  * That is, given buckets from the new lookup table N(x, y) and the old lookup
781  * table O(x, y), with x bucket index, and y group index:
782  *
783  *      - with g odd:  N(b, g) := U(O(x, g) for each x : x = (b & 0xf0) >> 4)
784  *      - with g even: N(b, g) := U(O(x, g) for each x : x = b & 0x0f)
785  *
786  * where U() denotes the arbitrary union operation (binary OR of n terms). This
787  * ensures equivalence of the matching results on lookup.
788  */
789 static void pipapo_lt_8b_to_4b(int old_groups, int bsize,
790                                unsigned long *old_lt, unsigned long *new_lt)
791 {
792         int g, b, bsrc, i;
793 
794         memset(new_lt, 0, old_groups * 2 * NFT_PIPAPO_BUCKETS(4) * bsize *
795                           sizeof(unsigned long));
796 
797         for (g = 0; g < old_groups * 2; g += 2) {
798                 int src_g = g / 2;
799 
800                 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
801                         for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
802                              bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
803                              bsrc++) {
804                                 if (((bsrc & 0xf0) >> 4) != b)
805                                         continue;
806 
807                                 for (i = 0; i < bsize; i++)
808                                         new_lt[i] |= old_lt[bsrc * bsize + i];
809                         }
810 
811                         new_lt += bsize;
812                 }
813 
814                 for (b = 0; b < NFT_PIPAPO_BUCKETS(4); b++) {
815                         for (bsrc = NFT_PIPAPO_BUCKETS(8) * src_g;
816                              bsrc < NFT_PIPAPO_BUCKETS(8) * (src_g + 1);
817                              bsrc++) {
818                                 if ((bsrc & 0x0f) != b)
819                                         continue;
820 
821                                 for (i = 0; i < bsize; i++)
822                                         new_lt[i] |= old_lt[bsrc * bsize + i];
823                         }
824 
825                         new_lt += bsize;
826                 }
827         }
828 }
829 
830 /**
831  * pipapo_lt_bits_adjust() - Adjust group size for lookup table if needed
832  * @f:          Field containing lookup table
833  */
834 static void pipapo_lt_bits_adjust(struct nft_pipapo_field *f)
835 {
836         unsigned long *new_lt;
837         int groups, bb;
838         size_t lt_size;
839 
840         lt_size = f->groups * NFT_PIPAPO_BUCKETS(f->bb) * f->bsize *
841                   sizeof(*f->lt);
842 
843         if (f->bb == NFT_PIPAPO_GROUP_BITS_SMALL_SET &&
844             lt_size > NFT_PIPAPO_LT_SIZE_HIGH) {
845                 groups = f->groups * 2;
846                 bb = NFT_PIPAPO_GROUP_BITS_LARGE_SET;
847 
848                 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
849                           sizeof(*f->lt);
850         } else if (f->bb == NFT_PIPAPO_GROUP_BITS_LARGE_SET &&
851                    lt_size < NFT_PIPAPO_LT_SIZE_LOW) {
852                 groups = f->groups / 2;
853                 bb = NFT_PIPAPO_GROUP_BITS_SMALL_SET;
854 
855                 lt_size = groups * NFT_PIPAPO_BUCKETS(bb) * f->bsize *
856                           sizeof(*f->lt);
857 
858                 /* Don't increase group width if the resulting lookup table size
859                  * would exceed the upper size threshold for a "small" set.
860                  */
861                 if (lt_size > NFT_PIPAPO_LT_SIZE_HIGH)
862                         return;
863         } else {
864                 return;
865         }
866 
867         new_lt = kvzalloc(lt_size + NFT_PIPAPO_ALIGN_HEADROOM, GFP_KERNEL);
868         if (!new_lt)
869                 return;
870 
871         NFT_PIPAPO_GROUP_BITS_ARE_8_OR_4;
872         if (f->bb == 4 && bb == 8) {
873                 pipapo_lt_4b_to_8b(f->groups, f->bsize,
874                                    NFT_PIPAPO_LT_ALIGN(f->lt),
875                                    NFT_PIPAPO_LT_ALIGN(new_lt));
876         } else if (f->bb == 8 && bb == 4) {
877                 pipapo_lt_8b_to_4b(f->groups, f->bsize,
878                                    NFT_PIPAPO_LT_ALIGN(f->lt),
879                                    NFT_PIPAPO_LT_ALIGN(new_lt));
880         } else {
881                 BUG();
882         }
883 
884         f->groups = groups;
885         f->bb = bb;
886         kvfree(f->lt);
887         NFT_PIPAPO_LT_ASSIGN(f, new_lt);
888 }
889 
890 /**
891  * pipapo_insert() - Insert new rule in field given input key and mask length
892  * @f:          Field containing lookup table
893  * @k:          Input key for classification, without nftables padding
894  * @mask_bits:  Length of mask; matches field length for non-ranged entry
895  *
896  * Insert a new rule reference in lookup buckets corresponding to k and
897  * mask_bits.
898  *
899  * Return: 1 on success (one rule inserted), negative error code on failure.
900  */
901 static int pipapo_insert(struct nft_pipapo_field *f, const uint8_t *k,
902                          int mask_bits)
903 {
904         int rule = f->rules++, group, ret, bit_offset = 0;
905 
906         ret = pipapo_resize(f, f->rules - 1, f->rules);
907         if (ret)
908                 return ret;
909 
910         for (group = 0; group < f->groups; group++) {
911                 int i, v;
912                 u8 mask;
913 
914                 v = k[group / (BITS_PER_BYTE / f->bb)];
915                 v &= GENMASK(BITS_PER_BYTE - bit_offset - 1, 0);
916                 v >>= (BITS_PER_BYTE - bit_offset) - f->bb;
917 
918                 bit_offset += f->bb;
919                 bit_offset %= BITS_PER_BYTE;
920 
921                 if (mask_bits >= (group + 1) * f->bb) {
922                         /* Not masked */
923                         pipapo_bucket_set(f, rule, group, v);
924                 } else if (mask_bits <= group * f->bb) {
925                         /* Completely masked */
926                         for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++)
927                                 pipapo_bucket_set(f, rule, group, i);
928                 } else {
929                         /* The mask limit falls on this group */
930                         mask = GENMASK(f->bb - 1, 0);
931                         mask >>= mask_bits - group * f->bb;
932                         for (i = 0; i < NFT_PIPAPO_BUCKETS(f->bb); i++) {
933                                 if ((i & ~mask) == (v & ~mask))
934                                         pipapo_bucket_set(f, rule, group, i);
935                         }
936                 }
937         }
938 
939         pipapo_lt_bits_adjust(f);
940 
941         return 1;
942 }
943 
944 /**
945  * pipapo_step_diff() - Check if setting @step bit in netmask would change it
946  * @base:       Mask we are expanding
947  * @step:       Step bit for given expansion step
948  * @len:        Total length of mask space (set and unset bits), bytes
949  *
950  * Convenience function for mask expansion.
951  *
952  * Return: true if step bit changes mask (i.e. isn't set), false otherwise.
953  */
954 static bool pipapo_step_diff(u8 *base, int step, int len)
955 {
956         /* Network order, byte-addressed */
957 #ifdef __BIG_ENDIAN__
958         return !(BIT(step % BITS_PER_BYTE) & base[step / BITS_PER_BYTE]);
959 #else
960         return !(BIT(step % BITS_PER_BYTE) &
961                  base[len - 1 - step / BITS_PER_BYTE]);
962 #endif
963 }
964 
965 /**
966  * pipapo_step_after_end() - Check if mask exceeds range end with given step
967  * @base:       Mask we are expanding
968  * @end:        End of range
969  * @step:       Step bit for given expansion step, highest bit to be set
970  * @len:        Total length of mask space (set and unset bits), bytes
971  *
972  * Convenience function for mask expansion.
973  *
974  * Return: true if mask exceeds range setting step bits, false otherwise.
975  */
976 static bool pipapo_step_after_end(const u8 *base, const u8 *end, int step,
977                                   int len)
978 {
979         u8 tmp[NFT_PIPAPO_MAX_BYTES];
980         int i;
981 
982         memcpy(tmp, base, len);
983 
984         /* Network order, byte-addressed */
985         for (i = 0; i <= step; i++)
986 #ifdef __BIG_ENDIAN__
987                 tmp[i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
988 #else
989                 tmp[len - 1 - i / BITS_PER_BYTE] |= BIT(i % BITS_PER_BYTE);
990 #endif
991 
992         return memcmp(tmp, end, len) > 0;
993 }
994 
995 /**
996  * pipapo_base_sum() - Sum step bit to given len-sized netmask base with carry
997  * @base:       Netmask base
998  * @step:       Step bit to sum
999  * @len:        Netmask length, bytes
1000  */
1001 static void pipapo_base_sum(u8 *base, int step, int len)
1002 {
1003         bool carry = false;
1004         int i;
1005 
1006         /* Network order, byte-addressed */
1007 #ifdef __BIG_ENDIAN__
1008         for (i = step / BITS_PER_BYTE; i < len; i++) {
1009 #else
1010         for (i = len - 1 - step / BITS_PER_BYTE; i >= 0; i--) {
1011 #endif
1012                 if (carry)
1013                         base[i]++;
1014                 else
1015                         base[i] += 1 << (step % BITS_PER_BYTE);
1016 
1017                 if (base[i])
1018                         break;
1019 
1020                 carry = true;
1021         }
1022 }
1023 
1024 /**
1025  * pipapo_expand() - Expand to composing netmasks, insert into lookup table
1026  * @f:          Field containing lookup table
1027  * @start:      Start of range
1028  * @end:        End of range
1029  * @len:        Length of value in bits
1030  *
1031  * Expand range to composing netmasks and insert corresponding rule references
1032  * in lookup buckets.
1033  *
1034  * Return: number of inserted rules on success, negative error code on failure.
1035  */
1036 static int pipapo_expand(struct nft_pipapo_field *f,
1037                          const u8 *start, const u8 *end, int len)
1038 {
1039         int step, masks = 0, bytes = DIV_ROUND_UP(len, BITS_PER_BYTE);
1040         u8 base[NFT_PIPAPO_MAX_BYTES];
1041 
1042         memcpy(base, start, bytes);
1043         while (memcmp(base, end, bytes) <= 0) {
1044                 int err;
1045 
1046                 step = 0;
1047                 while (pipapo_step_diff(base, step, bytes)) {
1048                         if (pipapo_step_after_end(base, end, step, bytes))
1049                                 break;
1050 
1051                         step++;
1052                         if (step >= len) {
1053                                 if (!masks) {
1054                                         pipapo_insert(f, base, 0);
1055                                         masks = 1;
1056                                 }
1057                                 goto out;
1058                         }
1059                 }
1060 
1061                 err = pipapo_insert(f, base, len - step);
1062 
1063                 if (err < 0)
1064                         return err;
1065 
1066                 masks++;
1067                 pipapo_base_sum(base, step, bytes);
1068         }
1069 out:
1070         return masks;
1071 }
1072 
1073 /**
1074  * pipapo_map() - Insert rules in mapping tables, mapping them between fields
1075  * @m:          Matching data, including mapping table
1076  * @map:        Table of rule maps: array of first rule and amount of rules
1077  *              in next field a given rule maps to, for each field
1078  * @e:          For last field, nft_set_ext pointer matching rules map to
1079  */
1080 static void pipapo_map(struct nft_pipapo_match *m,
1081                        union nft_pipapo_map_bucket map[NFT_PIPAPO_MAX_FIELDS],
1082                        struct nft_pipapo_elem *e)
1083 {
1084         struct nft_pipapo_field *f;
1085         int i, j;
1086 
1087         for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) {
1088                 for (j = 0; j < map[i].n; j++) {
1089                         f->mt[map[i].to + j].to = map[i + 1].to;
1090                         f->mt[map[i].to + j].n = map[i + 1].n;
1091                 }
1092         }
1093 
1094         /* Last field: map to ext instead of mapping to next field */
1095         for (j = 0; j < map[i].n; j++)
1096                 f->mt[map[i].to + j].e = e;
1097 }
1098 
1099 /**
1100  * pipapo_realloc_scratch() - Reallocate scratch maps for partial match results
1101  * @clone:      Copy of matching data with pending insertions and deletions
1102  * @bsize_max:  Maximum bucket size, scratch maps cover two buckets
1103  *
1104  * Return: 0 on success, -ENOMEM on failure.
1105  */
1106 static int pipapo_realloc_scratch(struct nft_pipapo_match *clone,
1107                                   unsigned long bsize_max)
1108 {
1109         int i;
1110 
1111         for_each_possible_cpu(i) {
1112                 unsigned long *scratch;
1113 #ifdef NFT_PIPAPO_ALIGN
1114                 unsigned long *scratch_aligned;
1115 #endif
1116 
1117                 scratch = kzalloc_node(bsize_max * sizeof(*scratch) * 2 +
1118                                        NFT_PIPAPO_ALIGN_HEADROOM,
1119                                        GFP_KERNEL, cpu_to_node(i));
1120                 if (!scratch) {
1121                         /* On failure, there's no need to undo previous
1122                          * allocations: this means that some scratch maps have
1123                          * a bigger allocated size now (this is only called on
1124                          * insertion), but the extra space won't be used by any
1125                          * CPU as new elements are not inserted and m->bsize_max
1126                          * is not updated.
1127                          */
1128                         return -ENOMEM;
1129                 }
1130 
1131                 kfree(*per_cpu_ptr(clone->scratch, i));
1132 
1133                 *per_cpu_ptr(clone->scratch, i) = scratch;
1134 
1135 #ifdef NFT_PIPAPO_ALIGN
1136                 scratch_aligned = NFT_PIPAPO_LT_ALIGN(scratch);
1137                 *per_cpu_ptr(clone->scratch_aligned, i) = scratch_aligned;
1138 #endif
1139         }
1140 
1141         return 0;
1142 }
1143 
1144 /**
1145  * nft_pipapo_insert() - Validate and insert ranged elements
1146  * @net:        Network namespace
1147  * @set:        nftables API set representation
1148  * @elem:       nftables API element representation containing key data
1149  * @ext2:       Filled with pointer to &struct nft_set_ext in inserted element
1150  *
1151  * Return: 0 on success, error pointer on failure.
1152  */
1153 static int nft_pipapo_insert(const struct net *net, const struct nft_set *set,
1154                              const struct nft_set_elem *elem,
1155                              struct nft_set_ext **ext2)
1156 {
1157         const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1158         union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1159         const u8 *start = (const u8 *)elem->key.val.data, *end;
1160         struct nft_pipapo_elem *e = elem->priv, *dup;
1161         struct nft_pipapo *priv = nft_set_priv(set);
1162         struct nft_pipapo_match *m = priv->clone;
1163         u8 genmask = nft_genmask_next(net);
1164         struct nft_pipapo_field *f;
1165         int i, bsize_max, err = 0;
1166 
1167         if (nft_set_ext_exists(ext, NFT_SET_EXT_KEY_END))
1168                 end = (const u8 *)nft_set_ext_key_end(ext)->data;
1169         else
1170                 end = start;
1171 
1172         dup = pipapo_get(net, set, start, genmask);
1173         if (!IS_ERR(dup)) {
1174                 /* Check if we already have the same exact entry */
1175                 const struct nft_data *dup_key, *dup_end;
1176 
1177                 dup_key = nft_set_ext_key(&dup->ext);
1178                 if (nft_set_ext_exists(&dup->ext, NFT_SET_EXT_KEY_END))
1179                         dup_end = nft_set_ext_key_end(&dup->ext);
1180                 else
1181                         dup_end = dup_key;
1182 
1183                 if (!memcmp(start, dup_key->data, sizeof(*dup_key->data)) &&
1184                     !memcmp(end, dup_end->data, sizeof(*dup_end->data))) {
1185                         *ext2 = &dup->ext;
1186                         return -EEXIST;
1187                 }
1188 
1189                 return -ENOTEMPTY;
1190         }
1191 
1192         if (PTR_ERR(dup) == -ENOENT) {
1193                 /* Look for partially overlapping entries */
1194                 dup = pipapo_get(net, set, end, nft_genmask_next(net));
1195         }
1196 
1197         if (PTR_ERR(dup) != -ENOENT) {
1198                 if (IS_ERR(dup))
1199                         return PTR_ERR(dup);
1200                 *ext2 = &dup->ext;
1201                 return -ENOTEMPTY;
1202         }
1203 
1204         /* Validate */
1205         nft_pipapo_for_each_field(f, i, m) {
1206                 const u8 *start_p = start, *end_p = end;
1207 
1208                 if (f->rules >= (unsigned long)NFT_PIPAPO_RULE0_MAX)
1209                         return -ENOSPC;
1210 
1211                 if (memcmp(start_p, end_p,
1212                            f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) > 0)
1213                         return -EINVAL;
1214 
1215                 start_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1216                 end_p += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1217         }
1218 
1219         /* Insert */
1220         priv->dirty = true;
1221 
1222         bsize_max = m->bsize_max;
1223 
1224         nft_pipapo_for_each_field(f, i, m) {
1225                 int ret;
1226 
1227                 rulemap[i].to = f->rules;
1228 
1229                 ret = memcmp(start, end,
1230                              f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1231                 if (!ret)
1232                         ret = pipapo_insert(f, start, f->groups * f->bb);
1233                 else
1234                         ret = pipapo_expand(f, start, end, f->groups * f->bb);
1235 
1236                 if (f->bsize > bsize_max)
1237                         bsize_max = f->bsize;
1238 
1239                 rulemap[i].n = ret;
1240 
1241                 start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1242                 end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1243         }
1244 
1245         if (!*get_cpu_ptr(m->scratch) || bsize_max > m->bsize_max) {
1246                 put_cpu_ptr(m->scratch);
1247 
1248                 err = pipapo_realloc_scratch(m, bsize_max);
1249                 if (err)
1250                         return err;
1251 
1252                 m->bsize_max = bsize_max;
1253         } else {
1254                 put_cpu_ptr(m->scratch);
1255         }
1256 
1257         *ext2 = &e->ext;
1258 
1259         pipapo_map(m, rulemap, e);
1260 
1261         return 0;
1262 }
1263 
1264 /**
1265  * pipapo_clone() - Clone matching data to create new working copy
1266  * @old:        Existing matching data
1267  *
1268  * Return: copy of matching data passed as 'old', error pointer on failure
1269  */
1270 static struct nft_pipapo_match *pipapo_clone(struct nft_pipapo_match *old)
1271 {
1272         struct nft_pipapo_field *dst, *src;
1273         struct nft_pipapo_match *new;
1274         int i;
1275 
1276         new = kmalloc(sizeof(*new) + sizeof(*dst) * old->field_count,
1277                       GFP_KERNEL);
1278         if (!new)
1279                 return ERR_PTR(-ENOMEM);
1280 
1281         new->field_count = old->field_count;
1282         new->bsize_max = old->bsize_max;
1283 
1284         new->scratch = alloc_percpu(*new->scratch);
1285         if (!new->scratch)
1286                 goto out_scratch;
1287 
1288 #ifdef NFT_PIPAPO_ALIGN
1289         new->scratch_aligned = alloc_percpu(*new->scratch_aligned);
1290         if (!new->scratch_aligned)
1291                 goto out_scratch;
1292 #endif
1293 
1294         rcu_head_init(&new->rcu);
1295 
1296         src = old->f;
1297         dst = new->f;
1298 
1299         for (i = 0; i < old->field_count; i++) {
1300                 unsigned long *new_lt;
1301 
1302                 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt));
1303 
1304                 new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) *
1305                                   src->bsize * sizeof(*dst->lt) +
1306                                   NFT_PIPAPO_ALIGN_HEADROOM,
1307                                   GFP_KERNEL);
1308                 if (!new_lt)
1309                         goto out_lt;
1310 
1311                 NFT_PIPAPO_LT_ASSIGN(dst, new_lt);
1312 
1313                 memcpy(NFT_PIPAPO_LT_ALIGN(new_lt),
1314                        NFT_PIPAPO_LT_ALIGN(src->lt),
1315                        src->bsize * sizeof(*dst->lt) *
1316                        src->groups * NFT_PIPAPO_BUCKETS(src->bb));
1317 
1318                 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL);
1319                 if (!dst->mt)
1320                         goto out_mt;
1321 
1322                 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt));
1323                 src++;
1324                 dst++;
1325         }
1326 
1327         return new;
1328 
1329 out_mt:
1330         kvfree(dst->lt);
1331 out_lt:
1332         for (dst--; i > 0; i--) {
1333                 kvfree(dst->mt);
1334                 kvfree(dst->lt);
1335                 dst--;
1336         }
1337 #ifdef NFT_PIPAPO_ALIGN
1338         free_percpu(new->scratch_aligned);
1339 #endif
1340 out_scratch:
1341         free_percpu(new->scratch);
1342         kfree(new);
1343 
1344         return ERR_PTR(-ENOMEM);
1345 }
1346 
1347 /**
1348  * pipapo_rules_same_key() - Get number of rules originated from the same entry
1349  * @f:          Field containing mapping table
1350  * @first:      Index of first rule in set of rules mapping to same entry
1351  *
1352  * Using the fact that all rules in a field that originated from the same entry
1353  * will map to the same set of rules in the next field, or to the same element
1354  * reference, return the cardinality of the set of rules that originated from
1355  * the same entry as the rule with index @first, @first rule included.
1356  *
1357  * In pictures:
1358  *                              rules
1359  *      field #0                0    1    2    3    4
1360  *              map to:         0    1   2-4  2-4  5-9
1361  *                              .    .    .......   . ...
1362  *                              |    |    |    | \   \
1363  *                              |    |    |    |  \   \
1364  *                              |    |    |    |   \   \
1365  *                              '    '    '    '    '   \
1366  *      in field #1             0    1    2    3    4    5 ...
1367  *
1368  * if this is called for rule 2 on field #0, it will return 3, as also rules 2
1369  * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field.
1370  *
1371  * For the last field in a set, we can rely on associated entries to map to the
1372  * same element references.
1373  *
1374  * Return: Number of rules that originated from the same entry as @first.
1375  */
1376 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first)
1377 {
1378         struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */
1379         int r;
1380 
1381         for (r = first; r < f->rules; r++) {
1382                 if (r != first && e != f->mt[r].e)
1383                         return r - first;
1384 
1385                 e = f->mt[r].e;
1386         }
1387 
1388         if (r != first)
1389                 return r - first;
1390 
1391         return 0;
1392 }
1393 
1394 /**
1395  * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones
1396  * @mt:         Mapping array
1397  * @rules:      Original amount of rules in mapping table
1398  * @start:      First rule index to be removed
1399  * @n:          Amount of rules to be removed
1400  * @to_offset:  First rule index, in next field, this group of rules maps to
1401  * @is_last:    If this is the last field, delete reference from mapping array
1402  *
1403  * This is used to unmap rules from the mapping table for a single field,
1404  * maintaining consistency and compactness for the existing ones.
1405  *
1406  * In pictures: let's assume that we want to delete rules 2 and 3 from the
1407  * following mapping array:
1408  *
1409  *                 rules
1410  *               0      1      2      3      4
1411  *      map to:  4-10   4-10   11-15  11-15  16-18
1412  *
1413  * the result will be:
1414  *
1415  *                 rules
1416  *               0      1      2
1417  *      map to:  4-10   4-10   11-13
1418  *
1419  * for fields before the last one. In case this is the mapping table for the
1420  * last field in a set, and rules map to pointers to &struct nft_pipapo_elem:
1421  *
1422  *                      rules
1423  *                        0      1      2      3      4
1424  *  element pointers:  0x42   0x42   0x33   0x33   0x44
1425  *
1426  * the result will be:
1427  *
1428  *                      rules
1429  *                        0      1      2
1430  *  element pointers:  0x42   0x42   0x44
1431  */
1432 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules,
1433                          int start, int n, int to_offset, bool is_last)
1434 {
1435         int i;
1436 
1437         memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt));
1438         memset(mt + rules - n, 0, n * sizeof(*mt));
1439 
1440         if (is_last)
1441                 return;
1442 
1443         for (i = start; i < rules - n; i++)
1444                 mt[i].to -= to_offset;
1445 }
1446 
1447 /**
1448  * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map
1449  * @m:          Matching data
1450  * @rulemap:    Table of rule maps, arrays of first rule and amount of rules
1451  *              in next field a given entry maps to, for each field
1452  *
1453  * For each rule in lookup table buckets mapping to this set of rules, drop
1454  * all bits set in lookup table mapping. In pictures, assuming we want to drop
1455  * rules 0 and 1 from this lookup table:
1456  *
1457  *                     bucket
1458  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1459  *        0    0                                              1,2
1460  *        1   1,2                                      0
1461  *        2    0                                      1,2
1462  *        3    0                              1,2
1463  *        4  0,1,2
1464  *        5    0   1   2
1465  *        6  0,1,2 1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1466  *        7   1,2 1,2  1   1   1  0,1  1   1   1   1   1   1   1   1   1   1
1467  *
1468  * rule 2 becomes rule 0, and the result will be:
1469  *
1470  *                     bucket
1471  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1472  *        0                                                    0
1473  *        1    0
1474  *        2                                            0
1475  *        3                                    0
1476  *        4    0
1477  *        5            0
1478  *        6    0
1479  *        7    0   0
1480  *
1481  * once this is done, call unmap() to drop all the corresponding rule references
1482  * from mapping tables.
1483  */
1484 static void pipapo_drop(struct nft_pipapo_match *m,
1485                         union nft_pipapo_map_bucket rulemap[])
1486 {
1487         struct nft_pipapo_field *f;
1488         int i;
1489 
1490         nft_pipapo_for_each_field(f, i, m) {
1491                 int g;
1492 
1493                 for (g = 0; g < f->groups; g++) {
1494                         unsigned long *pos;
1495                         int b;
1496 
1497                         pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g *
1498                               NFT_PIPAPO_BUCKETS(f->bb) * f->bsize;
1499 
1500                         for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1501                                 bitmap_cut(pos, pos, rulemap[i].to,
1502                                            rulemap[i].n,
1503                                            f->bsize * BITS_PER_LONG);
1504 
1505                                 pos += f->bsize;
1506                         }
1507                 }
1508 
1509                 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n,
1510                              rulemap[i + 1].n, i == m->field_count - 1);
1511                 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) {
1512                         /* We can ignore this, a failure to shrink tables down
1513                          * doesn't make tables invalid.
1514                          */
1515                         ;
1516                 }
1517                 f->rules -= rulemap[i].n;
1518 
1519                 pipapo_lt_bits_adjust(f);
1520         }
1521 }
1522 
1523 /**
1524  * pipapo_gc() - Drop expired entries from set, destroy start and end elements
1525  * @set:        nftables API set representation
1526  * @m:          Matching data
1527  */
1528 static void pipapo_gc(const struct nft_set *set, struct nft_pipapo_match *m)
1529 {
1530         struct nft_pipapo *priv = nft_set_priv(set);
1531         int rules_f0, first_rule = 0;
1532         struct nft_pipapo_elem *e;
1533 
1534         while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1535                 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1536                 struct nft_pipapo_field *f;
1537                 int i, start, rules_fx;
1538 
1539                 start = first_rule;
1540                 rules_fx = rules_f0;
1541 
1542                 nft_pipapo_for_each_field(f, i, m) {
1543                         rulemap[i].to = start;
1544                         rulemap[i].n = rules_fx;
1545 
1546                         if (i < m->field_count - 1) {
1547                                 rules_fx = f->mt[start].n;
1548                                 start = f->mt[start].to;
1549                         }
1550                 }
1551 
1552                 /* Pick the last field, and its last index */
1553                 f--;
1554                 i--;
1555                 e = f->mt[rulemap[i].to].e;
1556                 if (nft_set_elem_expired(&e->ext) &&
1557                     !nft_set_elem_mark_busy(&e->ext)) {
1558                         priv->dirty = true;
1559                         pipapo_drop(m, rulemap);
1560 
1561                         rcu_barrier();
1562                         nft_set_elem_destroy(set, e, true);
1563 
1564                         /* And check again current first rule, which is now the
1565                          * first we haven't checked.
1566                          */
1567                 } else {
1568                         first_rule += rules_f0;
1569                 }
1570         }
1571 
1572         e = nft_set_catchall_gc(set);
1573         if (e)
1574                 nft_set_elem_destroy(set, e, true);
1575 
1576         priv->last_gc = jiffies;
1577 }
1578 
1579 /**
1580  * pipapo_free_fields() - Free per-field tables contained in matching data
1581  * @m:          Matching data
1582  */
1583 static void pipapo_free_fields(struct nft_pipapo_match *m)
1584 {
1585         struct nft_pipapo_field *f;
1586         int i;
1587 
1588         nft_pipapo_for_each_field(f, i, m) {
1589                 kvfree(f->lt);
1590                 kvfree(f->mt);
1591         }
1592 }
1593 
1594 /**
1595  * pipapo_reclaim_match - RCU callback to free fields from old matching data
1596  * @rcu:        RCU head
1597  */
1598 static void pipapo_reclaim_match(struct rcu_head *rcu)
1599 {
1600         struct nft_pipapo_match *m;
1601         int i;
1602 
1603         m = container_of(rcu, struct nft_pipapo_match, rcu);
1604 
1605         for_each_possible_cpu(i)
1606                 kfree(*per_cpu_ptr(m->scratch, i));
1607 
1608 #ifdef NFT_PIPAPO_ALIGN
1609         free_percpu(m->scratch_aligned);
1610 #endif
1611         free_percpu(m->scratch);
1612 
1613         pipapo_free_fields(m);
1614 
1615         kfree(m);
1616 }
1617 
1618 /**
1619  * pipapo_commit() - Replace lookup data with current working copy
1620  * @set:        nftables API set representation
1621  *
1622  * While at it, check if we should perform garbage collection on the working
1623  * copy before committing it for lookup, and don't replace the table if the
1624  * working copy doesn't have pending changes.
1625  *
1626  * We also need to create a new working copy for subsequent insertions and
1627  * deletions.
1628  */
1629 static void pipapo_commit(const struct nft_set *set)
1630 {
1631         struct nft_pipapo *priv = nft_set_priv(set);
1632         struct nft_pipapo_match *new_clone, *old;
1633 
1634         if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set)))
1635                 pipapo_gc(set, priv->clone);
1636 
1637         if (!priv->dirty)
1638                 return;
1639 
1640         new_clone = pipapo_clone(priv->clone);
1641         if (IS_ERR(new_clone))
1642                 return;
1643 
1644         priv->dirty = false;
1645 
1646         old = rcu_access_pointer(priv->match);
1647         rcu_assign_pointer(priv->match, priv->clone);
1648         if (old)
1649                 call_rcu(&old->rcu, pipapo_reclaim_match);
1650 
1651         priv->clone = new_clone;
1652 }
1653 
1654 /**
1655  * nft_pipapo_activate() - Mark element reference as active given key, commit
1656  * @net:        Network namespace
1657  * @set:        nftables API set representation
1658  * @elem:       nftables API element representation containing key data
1659  *
1660  * On insertion, elements are added to a copy of the matching data currently
1661  * in use for lookups, and not directly inserted into current lookup data, so
1662  * we'll take care of that by calling pipapo_commit() here. Both
1663  * nft_pipapo_insert() and nft_pipapo_activate() are called once for each
1664  * element, hence we can't purpose either one as a real commit operation.
1665  */
1666 static void nft_pipapo_activate(const struct net *net,
1667                                 const struct nft_set *set,
1668                                 const struct nft_set_elem *elem)
1669 {
1670         struct nft_pipapo_elem *e;
1671 
1672         e = pipapo_get(net, set, (const u8 *)elem->key.val.data, 0);
1673         if (IS_ERR(e))
1674                 return;
1675 
1676         nft_set_elem_change_active(net, set, &e->ext);
1677         nft_set_elem_clear_busy(&e->ext);
1678 
1679         pipapo_commit(set);
1680 }
1681 
1682 /**
1683  * pipapo_deactivate() - Check that element is in set, mark as inactive
1684  * @net:        Network namespace
1685  * @set:        nftables API set representation
1686  * @data:       Input key data
1687  * @ext:        nftables API extension pointer, used to check for end element
1688  *
1689  * This is a convenience function that can be called from both
1690  * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same
1691  * operation.
1692  *
1693  * Return: deactivated element if found, NULL otherwise.
1694  */
1695 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set,
1696                                const u8 *data, const struct nft_set_ext *ext)
1697 {
1698         struct nft_pipapo_elem *e;
1699 
1700         e = pipapo_get(net, set, data, nft_genmask_next(net));
1701         if (IS_ERR(e))
1702                 return NULL;
1703 
1704         nft_set_elem_change_active(net, set, &e->ext);
1705 
1706         return e;
1707 }
1708 
1709 /**
1710  * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive
1711  * @net:        Network namespace
1712  * @set:        nftables API set representation
1713  * @elem:       nftables API element representation containing key data
1714  *
1715  * Return: deactivated element if found, NULL otherwise.
1716  */
1717 static void *nft_pipapo_deactivate(const struct net *net,
1718                                    const struct nft_set *set,
1719                                    const struct nft_set_elem *elem)
1720 {
1721         const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv);
1722 
1723         return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext);
1724 }
1725 
1726 /**
1727  * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive
1728  * @net:        Network namespace
1729  * @set:        nftables API set representation
1730  * @elem:       nftables API element representation containing key data
1731  *
1732  * This is functionally the same as nft_pipapo_deactivate(), with a slightly
1733  * different interface, and it's also called once for each element in a set
1734  * being flushed, so we can't implement, strictly speaking, a flush operation,
1735  * which would otherwise be as simple as allocating an empty copy of the
1736  * matching data.
1737  *
1738  * Note that we could in theory do that, mark the set as flushed, and ignore
1739  * subsequent calls, but we would leak all the elements after the first one,
1740  * because they wouldn't then be freed as result of API calls.
1741  *
1742  * Return: true if element was found and deactivated.
1743  */
1744 static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set,
1745                              void *elem)
1746 {
1747         struct nft_pipapo_elem *e = elem;
1748 
1749         return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext),
1750                                  &e->ext);
1751 }
1752 
1753 /**
1754  * pipapo_get_boundaries() - Get byte interval for associated rules
1755  * @f:          Field including lookup table
1756  * @first_rule: First rule (lowest index)
1757  * @rule_count: Number of associated rules
1758  * @left:       Byte expression for left boundary (start of range)
1759  * @right:      Byte expression for right boundary (end of range)
1760  *
1761  * Given the first rule and amount of rules that originated from the same entry,
1762  * build the original range associated with the entry, and calculate the length
1763  * of the originating netmask.
1764  *
1765  * In pictures:
1766  *
1767  *                     bucket
1768  *      group  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
1769  *        0                                                   1,2
1770  *        1   1,2
1771  *        2                                           1,2
1772  *        3                                   1,2
1773  *        4   1,2
1774  *        5        1   2
1775  *        6   1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
1776  *        7   1,2 1,2  1   1   1   1   1   1   1   1   1   1   1   1   1   1
1777  *
1778  * this is the lookup table corresponding to the IPv4 range
1779  * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks,
1780  * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31.
1781  *
1782  * This function fills @left and @right with the byte values of the leftmost
1783  * and rightmost bucket indices for the lowest and highest rule indices,
1784  * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in
1785  * nibbles:
1786  *   left:  < 12, 0, 10, 8, 0, 1, 0, 0 >
1787  *   right: < 12, 0, 10, 8, 0, 2, 2, 1 >
1788  * corresponding to bytes:
1789  *   left:  < 192, 168, 1, 0 >
1790  *   right: < 192, 168, 2, 1 >
1791  * with mask length irrelevant here, unused on return, as the range is already
1792  * defined by its start and end points. The mask length is relevant for a single
1793  * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore
1794  * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes
1795  * < 192, 168, 1, 255 >, and the mask length, calculated from the distances
1796  * between leftmost and rightmost bucket indices for each group, would be 24.
1797  *
1798  * Return: mask length, in bits.
1799  */
1800 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule,
1801                                  int rule_count, u8 *left, u8 *right)
1802 {
1803         int g, mask_len = 0, bit_offset = 0;
1804         u8 *l = left, *r = right;
1805 
1806         for (g = 0; g < f->groups; g++) {
1807                 int b, x0, x1;
1808 
1809                 x0 = -1;
1810                 x1 = -1;
1811                 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) {
1812                         unsigned long *pos;
1813 
1814                         pos = NFT_PIPAPO_LT_ALIGN(f->lt) +
1815                               (g * NFT_PIPAPO_BUCKETS(f->bb) + b) * f->bsize;
1816                         if (test_bit(first_rule, pos) && x0 == -1)
1817                                 x0 = b;
1818                         if (test_bit(first_rule + rule_count - 1, pos))
1819                                 x1 = b;
1820                 }
1821 
1822                 *l |= x0 << (BITS_PER_BYTE - f->bb - bit_offset);
1823                 *r |= x1 << (BITS_PER_BYTE - f->bb - bit_offset);
1824 
1825                 bit_offset += f->bb;
1826                 if (bit_offset >= BITS_PER_BYTE) {
1827                         bit_offset %= BITS_PER_BYTE;
1828                         l++;
1829                         r++;
1830                 }
1831 
1832                 if (x1 - x0 == 0)
1833                         mask_len += 4;
1834                 else if (x1 - x0 == 1)
1835                         mask_len += 3;
1836                 else if (x1 - x0 == 3)
1837                         mask_len += 2;
1838                 else if (x1 - x0 == 7)
1839                         mask_len += 1;
1840         }
1841 
1842         return mask_len;
1843 }
1844 
1845 /**
1846  * pipapo_match_field() - Match rules against byte ranges
1847  * @f:          Field including the lookup table
1848  * @first_rule: First of associated rules originating from same entry
1849  * @rule_count: Amount of associated rules
1850  * @start:      Start of range to be matched
1851  * @end:        End of range to be matched
1852  *
1853  * Return: true on match, false otherwise.
1854  */
1855 static bool pipapo_match_field(struct nft_pipapo_field *f,
1856                                int first_rule, int rule_count,
1857                                const u8 *start, const u8 *end)
1858 {
1859         u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 };
1860         u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 };
1861 
1862         pipapo_get_boundaries(f, first_rule, rule_count, left, right);
1863 
1864         return !memcmp(start, left,
1865                        f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) &&
1866                !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f));
1867 }
1868 
1869 /**
1870  * nft_pipapo_remove() - Remove element given key, commit
1871  * @net:        Network namespace
1872  * @set:        nftables API set representation
1873  * @elem:       nftables API element representation containing key data
1874  *
1875  * Similarly to nft_pipapo_activate(), this is used as commit operation by the
1876  * API, but it's called once per element in the pending transaction, so we can't
1877  * implement this as a single commit operation. Closest we can get is to remove
1878  * the matched element here, if any, and commit the updated matching data.
1879  */
1880 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set,
1881                               const struct nft_set_elem *elem)
1882 {
1883         struct nft_pipapo *priv = nft_set_priv(set);
1884         struct nft_pipapo_match *m = priv->clone;
1885         struct nft_pipapo_elem *e = elem->priv;
1886         int rules_f0, first_rule = 0;
1887         const u8 *data;
1888 
1889         data = (const u8 *)nft_set_ext_key(&e->ext);
1890 
1891         e = pipapo_get(net, set, data, 0);
1892         if (IS_ERR(e))
1893                 return;
1894 
1895         while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) {
1896                 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS];
1897                 const u8 *match_start, *match_end;
1898                 struct nft_pipapo_field *f;
1899                 int i, start, rules_fx;
1900 
1901                 match_start = data;
1902                 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data;
1903 
1904                 start = first_rule;
1905                 rules_fx = rules_f0;
1906 
1907                 nft_pipapo_for_each_field(f, i, m) {
1908                         if (!pipapo_match_field(f, start, rules_fx,
1909                                                 match_start, match_end))
1910                                 break;
1911 
1912                         rulemap[i].to = start;
1913                         rulemap[i].n = rules_fx;
1914 
1915                         rules_fx = f->mt[start].n;
1916                         start = f->mt[start].to;
1917 
1918                         match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1919                         match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f);
1920                 }
1921 
1922                 if (i == m->field_count) {
1923                         priv->dirty = true;
1924                         pipapo_drop(m, rulemap);
1925                         pipapo_commit(set);
1926                         return;
1927                 }
1928 
1929                 first_rule += rules_f0;
1930         }
1931 }
1932 
1933 /**
1934  * nft_pipapo_walk() - Walk over elements
1935  * @ctx:        nftables API context
1936  * @set:        nftables API set representation
1937  * @iter:       Iterator
1938  *
1939  * As elements are referenced in the mapping array for the last field, directly
1940  * scan that array: there's no need to follow rule mappings from the first
1941  * field.
1942  */
1943 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set,
1944                             struct nft_set_iter *iter)
1945 {
1946         struct nft_pipapo *priv = nft_set_priv(set);
1947         struct nft_pipapo_match *m;
1948         struct nft_pipapo_field *f;
1949         int i, r;
1950 
1951         rcu_read_lock();
1952         m = rcu_dereference(priv->match);
1953 
1954         if (unlikely(!m))
1955                 goto out;
1956 
1957         for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
1958                 ;
1959 
1960         for (r = 0; r < f->rules; r++) {
1961                 struct nft_pipapo_elem *e;
1962                 struct nft_set_elem elem;
1963 
1964                 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
1965                         continue;
1966 
1967                 if (iter->count < iter->skip)
1968                         goto cont;
1969 
1970                 e = f->mt[r].e;
1971                 if (nft_set_elem_expired(&e->ext))
1972                         goto cont;
1973 
1974                 elem.priv = e;
1975 
1976                 iter->err = iter->fn(ctx, set, iter, &elem);
1977                 if (iter->err < 0)
1978                         goto out;
1979 
1980 cont:
1981                 iter->count++;
1982         }
1983 
1984 out:
1985         rcu_read_unlock();
1986 }
1987 
1988 /**
1989  * nft_pipapo_privsize() - Return the size of private data for the set
1990  * @nla:        netlink attributes, ignored as size doesn't depend on them
1991  * @desc:       Set description, ignored as size doesn't depend on it
1992  *
1993  * Return: size of private data for this set implementation, in bytes
1994  */
1995 static u64 nft_pipapo_privsize(const struct nlattr * const nla[],
1996                                const struct nft_set_desc *desc)
1997 {
1998         return sizeof(struct nft_pipapo);
1999 }
2000 
2001 /**
2002  * nft_pipapo_estimate() - Set size, space and lookup complexity
2003  * @desc:       Set description, element count and field description used
2004  * @features:   Flags: NFT_SET_INTERVAL needs to be there
2005  * @est:        Storage for estimation data
2006  *
2007  * Return: true if set description is compatible, false otherwise
2008  */
2009 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features,
2010                                 struct nft_set_estimate *est)
2011 {
2012         if (!(features & NFT_SET_INTERVAL) ||
2013             desc->field_count < NFT_PIPAPO_MIN_FIELDS)
2014                 return false;
2015 
2016         est->size = pipapo_estimate_size(desc);
2017         if (!est->size)
2018                 return false;
2019 
2020         est->lookup = NFT_SET_CLASS_O_LOG_N;
2021 
2022         est->space = NFT_SET_CLASS_O_N;
2023 
2024         return true;
2025 }
2026 
2027 /**
2028  * nft_pipapo_init() - Initialise data for a set instance
2029  * @set:        nftables API set representation
2030  * @desc:       Set description
2031  * @nla:        netlink attributes
2032  *
2033  * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink
2034  * attributes, initialise internal set parameters, current instance of matching
2035  * data and a copy for subsequent insertions.
2036  *
2037  * Return: 0 on success, negative error code on failure.
2038  */
2039 static int nft_pipapo_init(const struct nft_set *set,
2040                            const struct nft_set_desc *desc,
2041                            const struct nlattr * const nla[])
2042 {
2043         struct nft_pipapo *priv = nft_set_priv(set);
2044         struct nft_pipapo_match *m;
2045         struct nft_pipapo_field *f;
2046         int err, i, field_count;
2047 
2048         field_count = desc->field_count ? : 1;
2049 
2050         if (field_count > NFT_PIPAPO_MAX_FIELDS)
2051                 return -EINVAL;
2052 
2053         m = kmalloc(sizeof(*priv->match) + sizeof(*f) * field_count,
2054                     GFP_KERNEL);
2055         if (!m)
2056                 return -ENOMEM;
2057 
2058         m->field_count = field_count;
2059         m->bsize_max = 0;
2060 
2061         m->scratch = alloc_percpu(unsigned long *);
2062         if (!m->scratch) {
2063                 err = -ENOMEM;
2064                 goto out_scratch;
2065         }
2066         for_each_possible_cpu(i)
2067                 *per_cpu_ptr(m->scratch, i) = NULL;
2068 
2069 #ifdef NFT_PIPAPO_ALIGN
2070         m->scratch_aligned = alloc_percpu(unsigned long *);
2071         if (!m->scratch_aligned) {
2072                 err = -ENOMEM;
2073                 goto out_free;
2074         }
2075         for_each_possible_cpu(i)
2076                 *per_cpu_ptr(m->scratch_aligned, i) = NULL;
2077 #endif
2078 
2079         rcu_head_init(&m->rcu);
2080 
2081         nft_pipapo_for_each_field(f, i, m) {
2082                 int len = desc->field_len[i] ? : set->klen;
2083 
2084                 f->bb = NFT_PIPAPO_GROUP_BITS_INIT;
2085                 f->groups = len * NFT_PIPAPO_GROUPS_PER_BYTE(f);
2086 
2087                 priv->width += round_up(len, sizeof(u32));
2088 
2089                 f->bsize = 0;
2090                 f->rules = 0;
2091                 NFT_PIPAPO_LT_ASSIGN(f, NULL);
2092                 f->mt = NULL;
2093         }
2094 
2095         /* Create an initial clone of matching data for next insertion */
2096         priv->clone = pipapo_clone(m);
2097         if (IS_ERR(priv->clone)) {
2098                 err = PTR_ERR(priv->clone);
2099                 goto out_free;
2100         }
2101 
2102         priv->dirty = false;
2103 
2104         rcu_assign_pointer(priv->match, m);
2105 
2106         return 0;
2107 
2108 out_free:
2109 #ifdef NFT_PIPAPO_ALIGN
2110         free_percpu(m->scratch_aligned);
2111 #endif
2112         free_percpu(m->scratch);
2113 out_scratch:
2114         kfree(m);
2115 
2116         return err;
2117 }
2118 
2119 /**
2120  * nft_pipapo_destroy() - Free private data for set and all committed elements
2121  * @set:        nftables API set representation
2122  */
2123 static void nft_pipapo_destroy(const struct nft_set *set)
2124 {
2125         struct nft_pipapo *priv = nft_set_priv(set);
2126         struct nft_pipapo_match *m;
2127         struct nft_pipapo_field *f;
2128         int i, r, cpu;
2129 
2130         m = rcu_dereference_protected(priv->match, true);
2131         if (m) {
2132                 rcu_barrier();
2133 
2134                 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++)
2135                         ;
2136 
2137                 for (r = 0; r < f->rules; r++) {
2138                         struct nft_pipapo_elem *e;
2139 
2140                         if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e)
2141                                 continue;
2142 
2143                         e = f->mt[r].e;
2144 
2145                         nft_set_elem_destroy(set, e, true);
2146                 }
2147 
2148 #ifdef NFT_PIPAPO_ALIGN
2149                 free_percpu(m->scratch_aligned);
2150 #endif
2151                 for_each_possible_cpu(cpu)
2152                         kfree(*per_cpu_ptr(m->scratch, cpu));
2153                 free_percpu(m->scratch);
2154                 pipapo_free_fields(m);
2155                 kfree(m);
2156                 priv->match = NULL;
2157         }
2158 
2159         if (priv->clone) {
2160 #ifdef NFT_PIPAPO_ALIGN
2161                 free_percpu(priv->clone->scratch_aligned);
2162 #endif
2163                 for_each_possible_cpu(cpu)
2164                         kfree(*per_cpu_ptr(priv->clone->scratch, cpu));
2165                 free_percpu(priv->clone->scratch);
2166 
2167                 pipapo_free_fields(priv->clone);
2168                 kfree(priv->clone);
2169                 priv->clone = NULL;
2170         }
2171 }
2172 
2173 /**
2174  * nft_pipapo_gc_init() - Initialise garbage collection
2175  * @set:        nftables API set representation
2176  *
2177  * Instead of actually setting up a periodic work for garbage collection, as
2178  * this operation requires a swap of matching data with the working copy, we'll
2179  * do that opportunistically with other commit operations if the interval is
2180  * elapsed, so we just need to set the current jiffies timestamp here.
2181  */
2182 static void nft_pipapo_gc_init(const struct nft_set *set)
2183 {
2184         struct nft_pipapo *priv = nft_set_priv(set);
2185 
2186         priv->last_gc = jiffies;
2187 }
2188 
2189 const struct nft_set_type nft_set_pipapo_type = {
2190         .features       = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2191                           NFT_SET_TIMEOUT,
2192         .ops            = {
2193                 .lookup         = nft_pipapo_lookup,
2194                 .insert         = nft_pipapo_insert,
2195                 .activate       = nft_pipapo_activate,
2196                 .deactivate     = nft_pipapo_deactivate,
2197                 .flush          = nft_pipapo_flush,
2198                 .remove         = nft_pipapo_remove,
2199                 .walk           = nft_pipapo_walk,
2200                 .get            = nft_pipapo_get,
2201                 .privsize       = nft_pipapo_privsize,
2202                 .estimate       = nft_pipapo_estimate,
2203                 .init           = nft_pipapo_init,
2204                 .destroy        = nft_pipapo_destroy,
2205                 .gc_init        = nft_pipapo_gc_init,
2206                 .elemsize       = offsetof(struct nft_pipapo_elem, ext),
2207         },
2208 };
2209 
2210 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML)
2211 const struct nft_set_type nft_set_pipapo_avx2_type = {
2212         .features       = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT |
2213                           NFT_SET_TIMEOUT,
2214         .ops            = {
2215                 .lookup         = nft_pipapo_avx2_lookup,
2216                 .insert         = nft_pipapo_insert,
2217                 .activate       = nft_pipapo_activate,
2218                 .deactivate     = nft_pipapo_deactivate,
2219                 .flush          = nft_pipapo_flush,
2220                 .remove         = nft_pipapo_remove,
2221                 .walk           = nft_pipapo_walk,
2222                 .get            = nft_pipapo_get,
2223                 .privsize       = nft_pipapo_privsize,
2224                 .estimate       = nft_pipapo_avx2_estimate,
2225                 .init           = nft_pipapo_init,
2226                 .destroy        = nft_pipapo_destroy,
2227                 .gc_init        = nft_pipapo_gc_init,
2228                 .elemsize       = offsetof(struct nft_pipapo_elem, ext),
2229         },
2230 };
2231 #endif
2232 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp