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(struct_size(new, f, old->field_count), GFP_KERNEL); 1317 if (!new) 1318 return ERR_PTR(-ENOMEM); 1319 1320 new->field_count = old->field_count; 1321 new->bsize_max = old->bsize_max; 1322 1323 new->scratch = alloc_percpu(*new->scratch); 1324 if (!new->scratch) 1325 goto out_scratch; 1326 1327 for_each_possible_cpu(i) 1328 *per_cpu_ptr(new->scratch, i) = NULL; 1329 1330 if (pipapo_realloc_scratch(new, old->bsize_max)) 1331 goto out_scratch_realloc; 1332 1333 rcu_head_init(&new->rcu); 1334 1335 src = old->f; 1336 dst = new->f; 1337 1338 for (i = 0; i < old->field_count; i++) { 1339 unsigned long *new_lt; 1340 1341 memcpy(dst, src, offsetof(struct nft_pipapo_field, lt)); 1342 1343 new_lt = kvzalloc(src->groups * NFT_PIPAPO_BUCKETS(src->bb) * 1344 src->bsize * sizeof(*dst->lt) + 1345 NFT_PIPAPO_ALIGN_HEADROOM, 1346 GFP_KERNEL); 1347 if (!new_lt) 1348 goto out_lt; 1349 1350 NFT_PIPAPO_LT_ASSIGN(dst, new_lt); 1351 1352 memcpy(NFT_PIPAPO_LT_ALIGN(new_lt), 1353 NFT_PIPAPO_LT_ALIGN(src->lt), 1354 src->bsize * sizeof(*dst->lt) * 1355 src->groups * NFT_PIPAPO_BUCKETS(src->bb)); 1356 1357 dst->mt = kvmalloc(src->rules * sizeof(*src->mt), GFP_KERNEL); 1358 if (!dst->mt) 1359 goto out_mt; 1360 1361 memcpy(dst->mt, src->mt, src->rules * sizeof(*src->mt)); 1362 src++; 1363 dst++; 1364 } 1365 1366 return new; 1367 1368 out_mt: 1369 kvfree(dst->lt); 1370 out_lt: 1371 for (dst--; i > 0; i--) { 1372 kvfree(dst->mt); 1373 kvfree(dst->lt); 1374 dst--; 1375 } 1376 out_scratch_realloc: 1377 for_each_possible_cpu(i) 1378 pipapo_free_scratch(new, i); 1379 out_scratch: 1380 free_percpu(new->scratch); 1381 kfree(new); 1382 1383 return ERR_PTR(-ENOMEM); 1384 } 1385 1386 /** 1387 * pipapo_rules_same_key() - Get number of rules originated from the same entry 1388 * @f: Field containing mapping table 1389 * @first: Index of first rule in set of rules mapping to same entry 1390 * 1391 * Using the fact that all rules in a field that originated from the same entry 1392 * will map to the same set of rules in the next field, or to the same element 1393 * reference, return the cardinality of the set of rules that originated from 1394 * the same entry as the rule with index @first, @first rule included. 1395 * 1396 * In pictures: 1397 * rules 1398 * field #0 0 1 2 3 4 1399 * map to: 0 1 2-4 2-4 5-9 1400 * . . ....... . ... 1401 * | | | | \ \ 1402 * | | | | \ \ 1403 * | | | | \ \ 1404 * ' ' ' ' ' \ 1405 * in field #1 0 1 2 3 4 5 ... 1406 * 1407 * if this is called for rule 2 on field #0, it will return 3, as also rules 2 1408 * and 3 in field 0 map to the same set of rules (2, 3, 4) in the next field. 1409 * 1410 * For the last field in a set, we can rely on associated entries to map to the 1411 * same element references. 1412 * 1413 * Return: Number of rules that originated from the same entry as @first. 1414 */ 1415 static int pipapo_rules_same_key(struct nft_pipapo_field *f, int first) 1416 { 1417 struct nft_pipapo_elem *e = NULL; /* Keep gcc happy */ 1418 int r; 1419 1420 for (r = first; r < f->rules; r++) { 1421 if (r != first && e != f->mt[r].e) 1422 return r - first; 1423 1424 e = f->mt[r].e; 1425 } 1426 1427 if (r != first) 1428 return r - first; 1429 1430 return 0; 1431 } 1432 1433 /** 1434 * pipapo_unmap() - Remove rules from mapping tables, renumber remaining ones 1435 * @mt: Mapping array 1436 * @rules: Original amount of rules in mapping table 1437 * @start: First rule index to be removed 1438 * @n: Amount of rules to be removed 1439 * @to_offset: First rule index, in next field, this group of rules maps to 1440 * @is_last: If this is the last field, delete reference from mapping array 1441 * 1442 * This is used to unmap rules from the mapping table for a single field, 1443 * maintaining consistency and compactness for the existing ones. 1444 * 1445 * In pictures: let's assume that we want to delete rules 2 and 3 from the 1446 * following mapping array: 1447 * 1448 * rules 1449 * 0 1 2 3 4 1450 * map to: 4-10 4-10 11-15 11-15 16-18 1451 * 1452 * the result will be: 1453 * 1454 * rules 1455 * 0 1 2 1456 * map to: 4-10 4-10 11-13 1457 * 1458 * for fields before the last one. In case this is the mapping table for the 1459 * last field in a set, and rules map to pointers to &struct nft_pipapo_elem: 1460 * 1461 * rules 1462 * 0 1 2 3 4 1463 * element pointers: 0x42 0x42 0x33 0x33 0x44 1464 * 1465 * the result will be: 1466 * 1467 * rules 1468 * 0 1 2 1469 * element pointers: 0x42 0x42 0x44 1470 */ 1471 static void pipapo_unmap(union nft_pipapo_map_bucket *mt, int rules, 1472 int start, int n, int to_offset, bool is_last) 1473 { 1474 int i; 1475 1476 memmove(mt + start, mt + start + n, (rules - start - n) * sizeof(*mt)); 1477 memset(mt + rules - n, 0, n * sizeof(*mt)); 1478 1479 if (is_last) 1480 return; 1481 1482 for (i = start; i < rules - n; i++) 1483 mt[i].to -= to_offset; 1484 } 1485 1486 /** 1487 * pipapo_drop() - Delete entry from lookup and mapping tables, given rule map 1488 * @m: Matching data 1489 * @rulemap: Table of rule maps, arrays of first rule and amount of rules 1490 * in next field a given entry maps to, for each field 1491 * 1492 * For each rule in lookup table buckets mapping to this set of rules, drop 1493 * all bits set in lookup table mapping. In pictures, assuming we want to drop 1494 * rules 0 and 1 from this lookup table: 1495 * 1496 * bucket 1497 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1498 * 0 0 1,2 1499 * 1 1,2 0 1500 * 2 0 1,2 1501 * 3 0 1,2 1502 * 4 0,1,2 1503 * 5 0 1 2 1504 * 6 0,1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1505 * 7 1,2 1,2 1 1 1 0,1 1 1 1 1 1 1 1 1 1 1 1506 * 1507 * rule 2 becomes rule 0, and the result will be: 1508 * 1509 * bucket 1510 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1511 * 0 0 1512 * 1 0 1513 * 2 0 1514 * 3 0 1515 * 4 0 1516 * 5 0 1517 * 6 0 1518 * 7 0 0 1519 * 1520 * once this is done, call unmap() to drop all the corresponding rule references 1521 * from mapping tables. 1522 */ 1523 static void pipapo_drop(struct nft_pipapo_match *m, 1524 union nft_pipapo_map_bucket rulemap[]) 1525 { 1526 struct nft_pipapo_field *f; 1527 int i; 1528 1529 nft_pipapo_for_each_field(f, i, m) { 1530 int g; 1531 1532 for (g = 0; g < f->groups; g++) { 1533 unsigned long *pos; 1534 int b; 1535 1536 pos = NFT_PIPAPO_LT_ALIGN(f->lt) + g * 1537 NFT_PIPAPO_BUCKETS(f->bb) * f->bsize; 1538 1539 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) { 1540 bitmap_cut(pos, pos, rulemap[i].to, 1541 rulemap[i].n, 1542 f->bsize * BITS_PER_LONG); 1543 1544 pos += f->bsize; 1545 } 1546 } 1547 1548 pipapo_unmap(f->mt, f->rules, rulemap[i].to, rulemap[i].n, 1549 rulemap[i + 1].n, i == m->field_count - 1); 1550 if (pipapo_resize(f, f->rules, f->rules - rulemap[i].n)) { 1551 /* We can ignore this, a failure to shrink tables down 1552 * doesn't make tables invalid. 1553 */ 1554 ; 1555 } 1556 f->rules -= rulemap[i].n; 1557 1558 pipapo_lt_bits_adjust(f); 1559 } 1560 } 1561 1562 static void nft_pipapo_gc_deactivate(struct net *net, struct nft_set *set, 1563 struct nft_pipapo_elem *e) 1564 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_pipapo_elem *e; 1585 struct nft_trans_gc *gc; 1586 1587 gc = nft_trans_gc_alloc(set, 0, GFP_KERNEL); 1588 if (!gc) 1589 return; 1590 1591 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) { 1592 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS]; 1593 struct nft_pipapo_field *f; 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 1614 /* synchronous gc never fails, there is no need to set on 1615 * NFT_SET_ELEM_DEAD_BIT. 1616 */ 1617 if (nft_set_elem_expired(&e->ext)) { 1618 priv->dirty = true; 1619 1620 gc = nft_trans_gc_queue_sync(gc, GFP_ATOMIC); 1621 if (!gc) 1622 return; 1623 1624 nft_pipapo_gc_deactivate(net, set, e); 1625 pipapo_drop(m, rulemap); 1626 nft_trans_gc_elem_add(gc, e); 1627 1628 /* And check again current first rule, which is now the 1629 * first we haven't checked. 1630 */ 1631 } else { 1632 first_rule += rules_f0; 1633 } 1634 } 1635 1636 gc = nft_trans_gc_catchall_sync(gc); 1637 if (gc) { 1638 nft_trans_gc_queue_sync_done(gc); 1639 priv->last_gc = jiffies; 1640 } 1641 } 1642 1643 /** 1644 * pipapo_free_fields() - Free per-field tables contained in matching data 1645 * @m: Matching data 1646 */ 1647 static void pipapo_free_fields(struct nft_pipapo_match *m) 1648 { 1649 struct nft_pipapo_field *f; 1650 int i; 1651 1652 nft_pipapo_for_each_field(f, i, m) { 1653 kvfree(f->lt); 1654 kvfree(f->mt); 1655 } 1656 } 1657 1658 static void pipapo_free_match(struct nft_pipapo_match *m) 1659 { 1660 int i; 1661 1662 for_each_possible_cpu(i) 1663 pipapo_free_scratch(m, i); 1664 1665 free_percpu(m->scratch); 1666 pipapo_free_fields(m); 1667 1668 kfree(m); 1669 } 1670 1671 /** 1672 * pipapo_reclaim_match - RCU callback to free fields from old matching data 1673 * @rcu: RCU head 1674 */ 1675 static void pipapo_reclaim_match(struct rcu_head *rcu) 1676 { 1677 struct nft_pipapo_match *m; 1678 1679 m = container_of(rcu, struct nft_pipapo_match, rcu); 1680 pipapo_free_match(m); 1681 } 1682 1683 /** 1684 * nft_pipapo_commit() - Replace lookup data with current working copy 1685 * @set: nftables API set representation 1686 * 1687 * While at it, check if we should perform garbage collection on the working 1688 * copy before committing it for lookup, and don't replace the table if the 1689 * working copy doesn't have pending changes. 1690 * 1691 * We also need to create a new working copy for subsequent insertions and 1692 * deletions. 1693 */ 1694 static void nft_pipapo_commit(const struct nft_set *set) 1695 { 1696 struct nft_pipapo *priv = nft_set_priv(set); 1697 struct nft_pipapo_match *new_clone, *old; 1698 1699 if (time_after_eq(jiffies, priv->last_gc + nft_set_gc_interval(set))) 1700 pipapo_gc(set, priv->clone); 1701 1702 if (!priv->dirty) 1703 return; 1704 1705 new_clone = pipapo_clone(priv->clone); 1706 if (IS_ERR(new_clone)) 1707 return; 1708 1709 priv->dirty = false; 1710 1711 old = rcu_access_pointer(priv->match); 1712 rcu_assign_pointer(priv->match, priv->clone); 1713 if (old) 1714 call_rcu(&old->rcu, pipapo_reclaim_match); 1715 1716 priv->clone = new_clone; 1717 } 1718 1719 static bool nft_pipapo_transaction_mutex_held(const struct nft_set *set) 1720 { 1721 #ifdef CONFIG_PROVE_LOCKING 1722 const struct net *net = read_pnet(&set->net); 1723 1724 return lockdep_is_held(&nft_pernet(net)->commit_mutex); 1725 #else 1726 return true; 1727 #endif 1728 } 1729 1730 static void nft_pipapo_abort(const struct nft_set *set) 1731 { 1732 struct nft_pipapo *priv = nft_set_priv(set); 1733 struct nft_pipapo_match *new_clone, *m; 1734 1735 if (!priv->dirty) 1736 return; 1737 1738 m = rcu_dereference_protected(priv->match, nft_pipapo_transaction_mutex_held(set)); 1739 1740 new_clone = pipapo_clone(m); 1741 if (IS_ERR(new_clone)) 1742 return; 1743 1744 priv->dirty = false; 1745 1746 pipapo_free_match(priv->clone); 1747 priv->clone = new_clone; 1748 } 1749 1750 /** 1751 * nft_pipapo_activate() - Mark element reference as active given key, commit 1752 * @net: Network namespace 1753 * @set: nftables API set representation 1754 * @elem: nftables API element representation containing key data 1755 * 1756 * On insertion, elements are added to a copy of the matching data currently 1757 * in use for lookups, and not directly inserted into current lookup data. Both 1758 * nft_pipapo_insert() and nft_pipapo_activate() are called once for each 1759 * element, hence we can't purpose either one as a real commit operation. 1760 */ 1761 static void nft_pipapo_activate(const struct net *net, 1762 const struct nft_set *set, 1763 const struct nft_set_elem *elem) 1764 { 1765 struct nft_pipapo_elem *e = elem->priv; 1766 1767 nft_set_elem_change_active(net, set, &e->ext); 1768 } 1769 1770 /** 1771 * pipapo_deactivate() - Check that element is in set, mark as inactive 1772 * @net: Network namespace 1773 * @set: nftables API set representation 1774 * @data: Input key data 1775 * @ext: nftables API extension pointer, used to check for end element 1776 * 1777 * This is a convenience function that can be called from both 1778 * nft_pipapo_deactivate() and nft_pipapo_flush(), as they are in fact the same 1779 * operation. 1780 * 1781 * Return: deactivated element if found, NULL otherwise. 1782 */ 1783 static void *pipapo_deactivate(const struct net *net, const struct nft_set *set, 1784 const u8 *data, const struct nft_set_ext *ext) 1785 { 1786 struct nft_pipapo_elem *e; 1787 1788 e = pipapo_get(net, set, data, nft_genmask_next(net)); 1789 if (IS_ERR(e)) 1790 return NULL; 1791 1792 nft_set_elem_change_active(net, set, &e->ext); 1793 1794 return e; 1795 } 1796 1797 /** 1798 * nft_pipapo_deactivate() - Call pipapo_deactivate() to make element inactive 1799 * @net: Network namespace 1800 * @set: nftables API set representation 1801 * @elem: nftables API element representation containing key data 1802 * 1803 * Return: deactivated element if found, NULL otherwise. 1804 */ 1805 static void *nft_pipapo_deactivate(const struct net *net, 1806 const struct nft_set *set, 1807 const struct nft_set_elem *elem) 1808 { 1809 const struct nft_set_ext *ext = nft_set_elem_ext(set, elem->priv); 1810 1811 return pipapo_deactivate(net, set, (const u8 *)elem->key.val.data, ext); 1812 } 1813 1814 /** 1815 * nft_pipapo_flush() - Call pipapo_deactivate() to make element inactive 1816 * @net: Network namespace 1817 * @set: nftables API set representation 1818 * @elem: nftables API element representation containing key data 1819 * 1820 * This is functionally the same as nft_pipapo_deactivate(), with a slightly 1821 * different interface, and it's also called once for each element in a set 1822 * being flushed, so we can't implement, strictly speaking, a flush operation, 1823 * which would otherwise be as simple as allocating an empty copy of the 1824 * matching data. 1825 * 1826 * Note that we could in theory do that, mark the set as flushed, and ignore 1827 * subsequent calls, but we would leak all the elements after the first one, 1828 * because they wouldn't then be freed as result of API calls. 1829 * 1830 * Return: true if element was found and deactivated. 1831 */ 1832 static bool nft_pipapo_flush(const struct net *net, const struct nft_set *set, 1833 void *elem) 1834 { 1835 struct nft_pipapo_elem *e = elem; 1836 1837 return pipapo_deactivate(net, set, (const u8 *)nft_set_ext_key(&e->ext), 1838 &e->ext); 1839 } 1840 1841 /** 1842 * pipapo_get_boundaries() - Get byte interval for associated rules 1843 * @f: Field including lookup table 1844 * @first_rule: First rule (lowest index) 1845 * @rule_count: Number of associated rules 1846 * @left: Byte expression for left boundary (start of range) 1847 * @right: Byte expression for right boundary (end of range) 1848 * 1849 * Given the first rule and amount of rules that originated from the same entry, 1850 * build the original range associated with the entry, and calculate the length 1851 * of the originating netmask. 1852 * 1853 * In pictures: 1854 * 1855 * bucket 1856 * group 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1857 * 0 1,2 1858 * 1 1,2 1859 * 2 1,2 1860 * 3 1,2 1861 * 4 1,2 1862 * 5 1 2 1863 * 6 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1864 * 7 1,2 1,2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1865 * 1866 * this is the lookup table corresponding to the IPv4 range 1867 * 192.168.1.0-192.168.2.1, which was expanded to the two composing netmasks, 1868 * rule #1: 192.168.1.0/24, and rule #2: 192.168.2.0/31. 1869 * 1870 * This function fills @left and @right with the byte values of the leftmost 1871 * and rightmost bucket indices for the lowest and highest rule indices, 1872 * respectively. If @first_rule is 1 and @rule_count is 2, we obtain, in 1873 * nibbles: 1874 * left: < 12, 0, 10, 8, 0, 1, 0, 0 > 1875 * right: < 12, 0, 10, 8, 0, 2, 2, 1 > 1876 * corresponding to bytes: 1877 * left: < 192, 168, 1, 0 > 1878 * right: < 192, 168, 2, 1 > 1879 * with mask length irrelevant here, unused on return, as the range is already 1880 * defined by its start and end points. The mask length is relevant for a single 1881 * ranged entry instead: if @first_rule is 1 and @rule_count is 1, we ignore 1882 * rule 2 above: @left becomes < 192, 168, 1, 0 >, @right becomes 1883 * < 192, 168, 1, 255 >, and the mask length, calculated from the distances 1884 * between leftmost and rightmost bucket indices for each group, would be 24. 1885 * 1886 * Return: mask length, in bits. 1887 */ 1888 static int pipapo_get_boundaries(struct nft_pipapo_field *f, int first_rule, 1889 int rule_count, u8 *left, u8 *right) 1890 { 1891 int g, mask_len = 0, bit_offset = 0; 1892 u8 *l = left, *r = right; 1893 1894 for (g = 0; g < f->groups; g++) { 1895 int b, x0, x1; 1896 1897 x0 = -1; 1898 x1 = -1; 1899 for (b = 0; b < NFT_PIPAPO_BUCKETS(f->bb); b++) { 1900 unsigned long *pos; 1901 1902 pos = NFT_PIPAPO_LT_ALIGN(f->lt) + 1903 (g * NFT_PIPAPO_BUCKETS(f->bb) + b) * f->bsize; 1904 if (test_bit(first_rule, pos) && x0 == -1) 1905 x0 = b; 1906 if (test_bit(first_rule + rule_count - 1, pos)) 1907 x1 = b; 1908 } 1909 1910 *l |= x0 << (BITS_PER_BYTE - f->bb - bit_offset); 1911 *r |= x1 << (BITS_PER_BYTE - f->bb - bit_offset); 1912 1913 bit_offset += f->bb; 1914 if (bit_offset >= BITS_PER_BYTE) { 1915 bit_offset %= BITS_PER_BYTE; 1916 l++; 1917 r++; 1918 } 1919 1920 if (x1 - x0 == 0) 1921 mask_len += 4; 1922 else if (x1 - x0 == 1) 1923 mask_len += 3; 1924 else if (x1 - x0 == 3) 1925 mask_len += 2; 1926 else if (x1 - x0 == 7) 1927 mask_len += 1; 1928 } 1929 1930 return mask_len; 1931 } 1932 1933 /** 1934 * pipapo_match_field() - Match rules against byte ranges 1935 * @f: Field including the lookup table 1936 * @first_rule: First of associated rules originating from same entry 1937 * @rule_count: Amount of associated rules 1938 * @start: Start of range to be matched 1939 * @end: End of range to be matched 1940 * 1941 * Return: true on match, false otherwise. 1942 */ 1943 static bool pipapo_match_field(struct nft_pipapo_field *f, 1944 int first_rule, int rule_count, 1945 const u8 *start, const u8 *end) 1946 { 1947 u8 right[NFT_PIPAPO_MAX_BYTES] = { 0 }; 1948 u8 left[NFT_PIPAPO_MAX_BYTES] = { 0 }; 1949 1950 pipapo_get_boundaries(f, first_rule, rule_count, left, right); 1951 1952 return !memcmp(start, left, 1953 f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)) && 1954 !memcmp(end, right, f->groups / NFT_PIPAPO_GROUPS_PER_BYTE(f)); 1955 } 1956 1957 /** 1958 * nft_pipapo_remove() - Remove element given key, commit 1959 * @net: Network namespace 1960 * @set: nftables API set representation 1961 * @elem: nftables API element representation containing key data 1962 * 1963 * Similarly to nft_pipapo_activate(), this is used as commit operation by the 1964 * API, but it's called once per element in the pending transaction, so we can't 1965 * implement this as a single commit operation. Closest we can get is to remove 1966 * the matched element here, if any, and commit the updated matching data. 1967 */ 1968 static void nft_pipapo_remove(const struct net *net, const struct nft_set *set, 1969 const struct nft_set_elem *elem) 1970 { 1971 struct nft_pipapo *priv = nft_set_priv(set); 1972 struct nft_pipapo_match *m = priv->clone; 1973 struct nft_pipapo_elem *e = elem->priv; 1974 int rules_f0, first_rule = 0; 1975 const u8 *data; 1976 1977 data = (const u8 *)nft_set_ext_key(&e->ext); 1978 1979 while ((rules_f0 = pipapo_rules_same_key(m->f, first_rule))) { 1980 union nft_pipapo_map_bucket rulemap[NFT_PIPAPO_MAX_FIELDS]; 1981 const u8 *match_start, *match_end; 1982 struct nft_pipapo_field *f; 1983 int i, start, rules_fx; 1984 1985 match_start = data; 1986 1987 if (nft_set_ext_exists(&e->ext, NFT_SET_EXT_KEY_END)) 1988 match_end = (const u8 *)nft_set_ext_key_end(&e->ext)->data; 1989 else 1990 match_end = data; 1991 1992 start = first_rule; 1993 rules_fx = rules_f0; 1994 1995 nft_pipapo_for_each_field(f, i, m) { 1996 bool last = i == m->field_count - 1; 1997 1998 if (!pipapo_match_field(f, start, rules_fx, 1999 match_start, match_end)) 2000 break; 2001 2002 rulemap[i].to = start; 2003 rulemap[i].n = rules_fx; 2004 2005 rules_fx = f->mt[start].n; 2006 start = f->mt[start].to; 2007 2008 match_start += NFT_PIPAPO_GROUPS_PADDED_SIZE(f); 2009 match_end += NFT_PIPAPO_GROUPS_PADDED_SIZE(f); 2010 2011 if (last && f->mt[rulemap[i].to].e == e) { 2012 priv->dirty = true; 2013 pipapo_drop(m, rulemap); 2014 return; 2015 } 2016 } 2017 2018 first_rule += rules_f0; 2019 } 2020 2021 WARN_ON_ONCE(1); /* elem_priv not found */ 2022 } 2023 2024 /** 2025 * nft_pipapo_walk() - Walk over elements 2026 * @ctx: nftables API context 2027 * @set: nftables API set representation 2028 * @iter: Iterator 2029 * 2030 * As elements are referenced in the mapping array for the last field, directly 2031 * scan that array: there's no need to follow rule mappings from the first 2032 * field. 2033 */ 2034 static void nft_pipapo_walk(const struct nft_ctx *ctx, struct nft_set *set, 2035 struct nft_set_iter *iter) 2036 { 2037 struct nft_pipapo *priv = nft_set_priv(set); 2038 struct net *net = read_pnet(&set->net); 2039 struct nft_pipapo_match *m; 2040 struct nft_pipapo_field *f; 2041 int i, r; 2042 2043 rcu_read_lock(); 2044 if (iter->genmask == nft_genmask_cur(net)) 2045 m = rcu_dereference(priv->match); 2046 else 2047 m = priv->clone; 2048 2049 if (unlikely(!m)) 2050 goto out; 2051 2052 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) 2053 ; 2054 2055 for (r = 0; r < f->rules; r++) { 2056 struct nft_pipapo_elem *e; 2057 struct nft_set_elem elem; 2058 2059 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e) 2060 continue; 2061 2062 if (iter->count < iter->skip) 2063 goto cont; 2064 2065 e = f->mt[r].e; 2066 2067 if (!nft_set_elem_active(&e->ext, iter->genmask)) 2068 goto cont; 2069 2070 elem.priv = e; 2071 2072 iter->err = iter->fn(ctx, set, iter, &elem); 2073 if (iter->err < 0) 2074 goto out; 2075 2076 cont: 2077 iter->count++; 2078 } 2079 2080 out: 2081 rcu_read_unlock(); 2082 } 2083 2084 /** 2085 * nft_pipapo_privsize() - Return the size of private data for the set 2086 * @nla: netlink attributes, ignored as size doesn't depend on them 2087 * @desc: Set description, ignored as size doesn't depend on it 2088 * 2089 * Return: size of private data for this set implementation, in bytes 2090 */ 2091 static u64 nft_pipapo_privsize(const struct nlattr * const nla[], 2092 const struct nft_set_desc *desc) 2093 { 2094 return sizeof(struct nft_pipapo); 2095 } 2096 2097 /** 2098 * nft_pipapo_estimate() - Set size, space and lookup complexity 2099 * @desc: Set description, element count and field description used 2100 * @features: Flags: NFT_SET_INTERVAL needs to be there 2101 * @est: Storage for estimation data 2102 * 2103 * Return: true if set description is compatible, false otherwise 2104 */ 2105 static bool nft_pipapo_estimate(const struct nft_set_desc *desc, u32 features, 2106 struct nft_set_estimate *est) 2107 { 2108 if (!(features & NFT_SET_INTERVAL) || 2109 desc->field_count < NFT_PIPAPO_MIN_FIELDS) 2110 return false; 2111 2112 est->size = pipapo_estimate_size(desc); 2113 if (!est->size) 2114 return false; 2115 2116 est->lookup = NFT_SET_CLASS_O_LOG_N; 2117 2118 est->space = NFT_SET_CLASS_O_N; 2119 2120 return true; 2121 } 2122 2123 /** 2124 * nft_pipapo_init() - Initialise data for a set instance 2125 * @set: nftables API set representation 2126 * @desc: Set description 2127 * @nla: netlink attributes 2128 * 2129 * Validate number and size of fields passed as NFTA_SET_DESC_CONCAT netlink 2130 * attributes, initialise internal set parameters, current instance of matching 2131 * data and a copy for subsequent insertions. 2132 * 2133 * Return: 0 on success, negative error code on failure. 2134 */ 2135 static int nft_pipapo_init(const struct nft_set *set, 2136 const struct nft_set_desc *desc, 2137 const struct nlattr * const nla[]) 2138 { 2139 struct nft_pipapo *priv = nft_set_priv(set); 2140 struct nft_pipapo_match *m; 2141 struct nft_pipapo_field *f; 2142 int err, i, field_count; 2143 2144 field_count = desc->field_count ? : 1; 2145 2146 if (field_count > NFT_PIPAPO_MAX_FIELDS) 2147 return -EINVAL; 2148 2149 m = kmalloc(struct_size(m, f, field_count), GFP_KERNEL); 2150 if (!m) 2151 return -ENOMEM; 2152 2153 m->field_count = field_count; 2154 m->bsize_max = 0; 2155 2156 m->scratch = alloc_percpu(struct nft_pipapo_scratch *); 2157 if (!m->scratch) { 2158 err = -ENOMEM; 2159 goto out_scratch; 2160 } 2161 for_each_possible_cpu(i) 2162 *per_cpu_ptr(m->scratch, i) = NULL; 2163 2164 rcu_head_init(&m->rcu); 2165 2166 nft_pipapo_for_each_field(f, i, m) { 2167 int len = desc->field_len[i] ? : set->klen; 2168 2169 f->bb = NFT_PIPAPO_GROUP_BITS_INIT; 2170 f->groups = len * NFT_PIPAPO_GROUPS_PER_BYTE(f); 2171 2172 priv->width += round_up(len, sizeof(u32)); 2173 2174 f->bsize = 0; 2175 f->rules = 0; 2176 NFT_PIPAPO_LT_ASSIGN(f, NULL); 2177 f->mt = NULL; 2178 } 2179 2180 /* Create an initial clone of matching data for next insertion */ 2181 priv->clone = pipapo_clone(m); 2182 if (IS_ERR(priv->clone)) { 2183 err = PTR_ERR(priv->clone); 2184 goto out_free; 2185 } 2186 2187 priv->dirty = false; 2188 2189 rcu_assign_pointer(priv->match, m); 2190 2191 return 0; 2192 2193 out_free: 2194 free_percpu(m->scratch); 2195 out_scratch: 2196 kfree(m); 2197 2198 return err; 2199 } 2200 2201 /** 2202 * nft_set_pipapo_match_destroy() - Destroy elements from key mapping array 2203 * @ctx: context 2204 * @set: nftables API set representation 2205 * @m: matching data pointing to key mapping array 2206 */ 2207 static void nft_set_pipapo_match_destroy(const struct nft_ctx *ctx, 2208 const struct nft_set *set, 2209 struct nft_pipapo_match *m) 2210 { 2211 struct nft_pipapo_field *f; 2212 int i, r; 2213 2214 for (i = 0, f = m->f; i < m->field_count - 1; i++, f++) 2215 ; 2216 2217 for (r = 0; r < f->rules; r++) { 2218 struct nft_pipapo_elem *e; 2219 2220 if (r < f->rules - 1 && f->mt[r + 1].e == f->mt[r].e) 2221 continue; 2222 2223 e = f->mt[r].e; 2224 2225 nf_tables_set_elem_destroy(ctx, set, e); 2226 } 2227 } 2228 2229 /** 2230 * nft_pipapo_destroy() - Free private data for set and all committed elements 2231 * @ctx: context 2232 * @set: nftables API set representation 2233 */ 2234 static void nft_pipapo_destroy(const struct nft_ctx *ctx, 2235 const struct nft_set *set) 2236 { 2237 struct nft_pipapo *priv = nft_set_priv(set); 2238 struct nft_pipapo_match *m; 2239 int cpu; 2240 2241 m = rcu_dereference_protected(priv->match, true); 2242 if (m) { 2243 rcu_barrier(); 2244 2245 for_each_possible_cpu(cpu) 2246 pipapo_free_scratch(m, cpu); 2247 free_percpu(m->scratch); 2248 pipapo_free_fields(m); 2249 kfree(m); 2250 priv->match = NULL; 2251 } 2252 2253 if (priv->clone) { 2254 m = priv->clone; 2255 2256 nft_set_pipapo_match_destroy(ctx, set, m); 2257 2258 for_each_possible_cpu(cpu) 2259 pipapo_free_scratch(priv->clone, cpu); 2260 free_percpu(priv->clone->scratch); 2261 2262 pipapo_free_fields(priv->clone); 2263 kfree(priv->clone); 2264 priv->clone = NULL; 2265 } 2266 } 2267 2268 /** 2269 * nft_pipapo_gc_init() - Initialise garbage collection 2270 * @set: nftables API set representation 2271 * 2272 * Instead of actually setting up a periodic work for garbage collection, as 2273 * this operation requires a swap of matching data with the working copy, we'll 2274 * do that opportunistically with other commit operations if the interval is 2275 * elapsed, so we just need to set the current jiffies timestamp here. 2276 */ 2277 static void nft_pipapo_gc_init(const struct nft_set *set) 2278 { 2279 struct nft_pipapo *priv = nft_set_priv(set); 2280 2281 priv->last_gc = jiffies; 2282 } 2283 2284 const struct nft_set_type nft_set_pipapo_type = { 2285 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT | 2286 NFT_SET_TIMEOUT, 2287 .ops = { 2288 .lookup = nft_pipapo_lookup, 2289 .insert = nft_pipapo_insert, 2290 .activate = nft_pipapo_activate, 2291 .deactivate = nft_pipapo_deactivate, 2292 .flush = nft_pipapo_flush, 2293 .remove = nft_pipapo_remove, 2294 .walk = nft_pipapo_walk, 2295 .get = nft_pipapo_get, 2296 .privsize = nft_pipapo_privsize, 2297 .estimate = nft_pipapo_estimate, 2298 .init = nft_pipapo_init, 2299 .destroy = nft_pipapo_destroy, 2300 .gc_init = nft_pipapo_gc_init, 2301 .commit = nft_pipapo_commit, 2302 .abort = nft_pipapo_abort, 2303 .elemsize = offsetof(struct nft_pipapo_elem, ext), 2304 }, 2305 }; 2306 2307 #if defined(CONFIG_X86_64) && !defined(CONFIG_UML) 2308 const struct nft_set_type nft_set_pipapo_avx2_type = { 2309 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT | 2310 NFT_SET_TIMEOUT, 2311 .ops = { 2312 .lookup = nft_pipapo_avx2_lookup, 2313 .insert = nft_pipapo_insert, 2314 .activate = nft_pipapo_activate, 2315 .deactivate = nft_pipapo_deactivate, 2316 .flush = nft_pipapo_flush, 2317 .remove = nft_pipapo_remove, 2318 .walk = nft_pipapo_walk, 2319 .get = nft_pipapo_get, 2320 .privsize = nft_pipapo_privsize, 2321 .estimate = nft_pipapo_avx2_estimate, 2322 .init = nft_pipapo_init, 2323 .destroy = nft_pipapo_destroy, 2324 .gc_init = nft_pipapo_gc_init, 2325 .commit = nft_pipapo_commit, 2326 .abort = nft_pipapo_abort, 2327 .elemsize = offsetof(struct nft_pipapo_elem, ext), 2328 }, 2329 }; 2330 #endif 2331