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