1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright (c) 2008-2009 Patrick McHardy <kaber@trash.net> 4 * 5 * Development of this code funded by Astaro AG (http://www.astaro.com/) 6 */ 7 8 #include <linux/kernel.h> 9 #include <linux/init.h> 10 #include <linux/module.h> 11 #include <linux/list.h> 12 #include <linux/rbtree.h> 13 #include <linux/netlink.h> 14 #include <linux/netfilter.h> 15 #include <linux/netfilter/nf_tables.h> 16 #include <net/netfilter/nf_tables_core.h> 17 18 struct nft_rbtree { 19 struct rb_root root; 20 rwlock_t lock; 21 seqcount_rwlock_t count; 22 struct delayed_work gc_work; 23 }; 24 25 struct nft_rbtree_elem { 26 struct rb_node node; 27 struct nft_set_ext ext; 28 }; 29 30 static bool nft_rbtree_interval_end(const struct nft_rbtree_elem *rbe) 31 { 32 return nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) && 33 (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END); 34 } 35 36 static bool nft_rbtree_interval_start(const struct nft_rbtree_elem *rbe) 37 { 38 return !nft_rbtree_interval_end(rbe); 39 } 40 41 static int nft_rbtree_cmp(const struct nft_set *set, 42 const struct nft_rbtree_elem *e1, 43 const struct nft_rbtree_elem *e2) 44 { 45 return memcmp(nft_set_ext_key(&e1->ext), nft_set_ext_key(&e2->ext), 46 set->klen); 47 } 48 49 static bool __nft_rbtree_lookup(const struct net *net, const struct nft_set *set, 50 const u32 *key, const struct nft_set_ext **ext, 51 unsigned int seq) 52 { 53 struct nft_rbtree *priv = nft_set_priv(set); 54 const struct nft_rbtree_elem *rbe, *interval = NULL; 55 u8 genmask = nft_genmask_cur(net); 56 const struct rb_node *parent; 57 int d; 58 59 parent = rcu_dereference_raw(priv->root.rb_node); 60 while (parent != NULL) { 61 if (read_seqcount_retry(&priv->count, seq)) 62 return false; 63 64 rbe = rb_entry(parent, struct nft_rbtree_elem, node); 65 66 d = memcmp(nft_set_ext_key(&rbe->ext), key, set->klen); 67 if (d < 0) { 68 parent = rcu_dereference_raw(parent->rb_left); 69 if (interval && 70 !nft_rbtree_cmp(set, rbe, interval) && 71 nft_rbtree_interval_end(rbe) && 72 nft_rbtree_interval_start(interval)) 73 continue; 74 interval = rbe; 75 } else if (d > 0) 76 parent = rcu_dereference_raw(parent->rb_right); 77 else { 78 if (!nft_set_elem_active(&rbe->ext, genmask)) { 79 parent = rcu_dereference_raw(parent->rb_left); 80 continue; 81 } 82 83 if (nft_set_elem_expired(&rbe->ext)) 84 return false; 85 86 if (nft_rbtree_interval_end(rbe)) { 87 if (nft_set_is_anonymous(set)) 88 return false; 89 parent = rcu_dereference_raw(parent->rb_left); 90 interval = NULL; 91 continue; 92 } 93 94 *ext = &rbe->ext; 95 return true; 96 } 97 } 98 99 if (set->flags & NFT_SET_INTERVAL && interval != NULL && 100 nft_set_elem_active(&interval->ext, genmask) && 101 !nft_set_elem_expired(&interval->ext) && 102 nft_rbtree_interval_start(interval)) { 103 *ext = &interval->ext; 104 return true; 105 } 106 107 return false; 108 } 109 110 INDIRECT_CALLABLE_SCOPE 111 bool nft_rbtree_lookup(const struct net *net, const struct nft_set *set, 112 const u32 *key, const struct nft_set_ext **ext) 113 { 114 struct nft_rbtree *priv = nft_set_priv(set); 115 unsigned int seq = read_seqcount_begin(&priv->count); 116 bool ret; 117 118 ret = __nft_rbtree_lookup(net, set, key, ext, seq); 119 if (ret || !read_seqcount_retry(&priv->count, seq)) 120 return ret; 121 122 read_lock_bh(&priv->lock); 123 seq = read_seqcount_begin(&priv->count); 124 ret = __nft_rbtree_lookup(net, set, key, ext, seq); 125 read_unlock_bh(&priv->lock); 126 127 return ret; 128 } 129 130 static bool __nft_rbtree_get(const struct net *net, const struct nft_set *set, 131 const u32 *key, struct nft_rbtree_elem **elem, 132 unsigned int seq, unsigned int flags, u8 genmask) 133 { 134 struct nft_rbtree_elem *rbe, *interval = NULL; 135 struct nft_rbtree *priv = nft_set_priv(set); 136 const struct rb_node *parent; 137 const void *this; 138 int d; 139 140 parent = rcu_dereference_raw(priv->root.rb_node); 141 while (parent != NULL) { 142 if (read_seqcount_retry(&priv->count, seq)) 143 return false; 144 145 rbe = rb_entry(parent, struct nft_rbtree_elem, node); 146 147 this = nft_set_ext_key(&rbe->ext); 148 d = memcmp(this, key, set->klen); 149 if (d < 0) { 150 parent = rcu_dereference_raw(parent->rb_left); 151 if (!(flags & NFT_SET_ELEM_INTERVAL_END)) 152 interval = rbe; 153 } else if (d > 0) { 154 parent = rcu_dereference_raw(parent->rb_right); 155 if (flags & NFT_SET_ELEM_INTERVAL_END) 156 interval = rbe; 157 } else { 158 if (!nft_set_elem_active(&rbe->ext, genmask)) { 159 parent = rcu_dereference_raw(parent->rb_left); 160 continue; 161 } 162 163 if (nft_set_elem_expired(&rbe->ext)) 164 return false; 165 166 if (!nft_set_ext_exists(&rbe->ext, NFT_SET_EXT_FLAGS) || 167 (*nft_set_ext_flags(&rbe->ext) & NFT_SET_ELEM_INTERVAL_END) == 168 (flags & NFT_SET_ELEM_INTERVAL_END)) { 169 *elem = rbe; 170 return true; 171 } 172 173 if (nft_rbtree_interval_end(rbe)) 174 interval = NULL; 175 176 parent = rcu_dereference_raw(parent->rb_left); 177 } 178 } 179 180 if (set->flags & NFT_SET_INTERVAL && interval != NULL && 181 nft_set_elem_active(&interval->ext, genmask) && 182 !nft_set_elem_expired(&interval->ext) && 183 ((!nft_rbtree_interval_end(interval) && 184 !(flags & NFT_SET_ELEM_INTERVAL_END)) || 185 (nft_rbtree_interval_end(interval) && 186 (flags & NFT_SET_ELEM_INTERVAL_END)))) { 187 *elem = interval; 188 return true; 189 } 190 191 return false; 192 } 193 194 static void *nft_rbtree_get(const struct net *net, const struct nft_set *set, 195 const struct nft_set_elem *elem, unsigned int flags) 196 { 197 struct nft_rbtree *priv = nft_set_priv(set); 198 unsigned int seq = read_seqcount_begin(&priv->count); 199 struct nft_rbtree_elem *rbe = ERR_PTR(-ENOENT); 200 const u32 *key = (const u32 *)&elem->key.val; 201 u8 genmask = nft_genmask_cur(net); 202 bool ret; 203 204 ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); 205 if (ret || !read_seqcount_retry(&priv->count, seq)) 206 return rbe; 207 208 read_lock_bh(&priv->lock); 209 seq = read_seqcount_begin(&priv->count); 210 ret = __nft_rbtree_get(net, set, key, &rbe, seq, flags, genmask); 211 if (!ret) 212 rbe = ERR_PTR(-ENOENT); 213 read_unlock_bh(&priv->lock); 214 215 return rbe; 216 } 217 218 static int nft_rbtree_gc_elem(const struct nft_set *__set, 219 struct nft_rbtree *priv, 220 struct nft_rbtree_elem *rbe) 221 { 222 struct nft_set *set = (struct nft_set *)__set; 223 struct rb_node *prev = rb_prev(&rbe->node); 224 struct nft_rbtree_elem *rbe_prev; 225 struct nft_set_gc_batch *gcb; 226 227 gcb = nft_set_gc_batch_check(set, NULL, GFP_ATOMIC); 228 if (!gcb) 229 return -ENOMEM; 230 231 /* search for expired end interval coming before this element. */ 232 do { 233 rbe_prev = rb_entry(prev, struct nft_rbtree_elem, node); 234 if (nft_rbtree_interval_end(rbe_prev)) 235 break; 236 237 prev = rb_prev(prev); 238 } while (prev != NULL); 239 240 rb_erase(&rbe_prev->node, &priv->root); 241 rb_erase(&rbe->node, &priv->root); 242 atomic_sub(2, &set->nelems); 243 244 nft_set_gc_batch_add(gcb, rbe); 245 nft_set_gc_batch_complete(gcb); 246 247 return 0; 248 } 249 250 static bool nft_rbtree_update_first(const struct nft_set *set, 251 struct nft_rbtree_elem *rbe, 252 struct rb_node *first) 253 { 254 struct nft_rbtree_elem *first_elem; 255 256 first_elem = rb_entry(first, struct nft_rbtree_elem, node); 257 /* this element is closest to where the new element is to be inserted: 258 * update the first element for the node list path. 259 */ 260 if (nft_rbtree_cmp(set, rbe, first_elem) < 0) 261 return true; 262 263 return false; 264 } 265 266 static int __nft_rbtree_insert(const struct net *net, const struct nft_set *set, 267 struct nft_rbtree_elem *new, 268 struct nft_set_ext **ext) 269 { 270 struct nft_rbtree_elem *rbe, *rbe_le = NULL, *rbe_ge = NULL; 271 struct rb_node *node, *parent, **p, *first = NULL; 272 struct nft_rbtree *priv = nft_set_priv(set); 273 u8 genmask = nft_genmask_next(net); 274 int d, err; 275 276 /* Descend the tree to search for an existing element greater than the 277 * key value to insert that is greater than the new element. This is the 278 * first element to walk the ordered elements to find possible overlap. 279 */ 280 parent = NULL; 281 p = &priv->root.rb_node; 282 while (*p != NULL) { 283 parent = *p; 284 rbe = rb_entry(parent, struct nft_rbtree_elem, node); 285 d = nft_rbtree_cmp(set, rbe, new); 286 287 if (d < 0) { 288 p = &parent->rb_left; 289 } else if (d > 0) { 290 if (!first || 291 nft_rbtree_update_first(set, rbe, first)) 292 first = &rbe->node; 293 294 p = &parent->rb_right; 295 } else { 296 if (nft_rbtree_interval_end(rbe)) 297 p = &parent->rb_left; 298 else 299 p = &parent->rb_right; 300 } 301 } 302 303 if (!first) 304 first = rb_first(&priv->root); 305 306 /* Detect overlap by going through the list of valid tree nodes. 307 * Values stored in the tree are in reversed order, starting from 308 * highest to lowest value. 309 */ 310 for (node = first; node != NULL; node = rb_next(node)) { 311 rbe = rb_entry(node, struct nft_rbtree_elem, node); 312 313 if (!nft_set_elem_active(&rbe->ext, genmask)) 314 continue; 315 316 /* perform garbage collection to avoid bogus overlap reports. */ 317 if (nft_set_elem_expired(&rbe->ext)) { 318 err = nft_rbtree_gc_elem(set, priv, rbe); 319 if (err < 0) 320 return err; 321 322 continue; 323 } 324 325 d = nft_rbtree_cmp(set, rbe, new); 326 if (d == 0) { 327 /* Matching end element: no need to look for an 328 * overlapping greater or equal element. 329 */ 330 if (nft_rbtree_interval_end(rbe)) { 331 rbe_le = rbe; 332 break; 333 } 334 335 /* first element that is greater or equal to key value. */ 336 if (!rbe_ge) { 337 rbe_ge = rbe; 338 continue; 339 } 340 341 /* this is a closer more or equal element, update it. */ 342 if (nft_rbtree_cmp(set, rbe_ge, new) != 0) { 343 rbe_ge = rbe; 344 continue; 345 } 346 347 /* element is equal to key value, make sure flags are 348 * the same, an existing more or equal start element 349 * must not be replaced by more or equal end element. 350 */ 351 if ((nft_rbtree_interval_start(new) && 352 nft_rbtree_interval_start(rbe_ge)) || 353 (nft_rbtree_interval_end(new) && 354 nft_rbtree_interval_end(rbe_ge))) { 355 rbe_ge = rbe; 356 continue; 357 } 358 } else if (d > 0) { 359 /* annotate element greater than the new element. */ 360 rbe_ge = rbe; 361 continue; 362 } else if (d < 0) { 363 /* annotate element less than the new element. */ 364 rbe_le = rbe; 365 break; 366 } 367 } 368 369 /* - new start element matching existing start element: full overlap 370 * reported as -EEXIST, cleared by caller if NLM_F_EXCL is not given. 371 */ 372 if (rbe_ge && !nft_rbtree_cmp(set, new, rbe_ge) && 373 nft_rbtree_interval_start(rbe_ge) == nft_rbtree_interval_start(new)) { 374 *ext = &rbe_ge->ext; 375 return -EEXIST; 376 } 377 378 /* - new end element matching existing end element: full overlap 379 * reported as -EEXIST, cleared by caller if NLM_F_EXCL is not given. 380 */ 381 if (rbe_le && !nft_rbtree_cmp(set, new, rbe_le) && 382 nft_rbtree_interval_end(rbe_le) == nft_rbtree_interval_end(new)) { 383 *ext = &rbe_le->ext; 384 return -EEXIST; 385 } 386 387 /* - new start element with existing closest, less or equal key value 388 * being a start element: partial overlap, reported as -ENOTEMPTY. 389 * Anonymous sets allow for two consecutive start element since they 390 * are constant, skip them to avoid bogus overlap reports. 391 */ 392 if (!nft_set_is_anonymous(set) && rbe_le && 393 nft_rbtree_interval_start(rbe_le) && nft_rbtree_interval_start(new)) 394 return -ENOTEMPTY; 395 396 /* - new end element with existing closest, less or equal key value 397 * being a end element: partial overlap, reported as -ENOTEMPTY. 398 */ 399 if (rbe_le && 400 nft_rbtree_interval_end(rbe_le) && nft_rbtree_interval_end(new)) 401 return -ENOTEMPTY; 402 403 /* - new end element with existing closest, greater or equal key value 404 * being an end element: partial overlap, reported as -ENOTEMPTY 405 */ 406 if (rbe_ge && 407 nft_rbtree_interval_end(rbe_ge) && nft_rbtree_interval_end(new)) 408 return -ENOTEMPTY; 409 410 /* Accepted element: pick insertion point depending on key value */ 411 parent = NULL; 412 p = &priv->root.rb_node; 413 while (*p != NULL) { 414 parent = *p; 415 rbe = rb_entry(parent, struct nft_rbtree_elem, node); 416 d = nft_rbtree_cmp(set, rbe, new); 417 418 if (d < 0) 419 p = &parent->rb_left; 420 else if (d > 0) 421 p = &parent->rb_right; 422 else if (nft_rbtree_interval_end(rbe)) 423 p = &parent->rb_left; 424 else 425 p = &parent->rb_right; 426 } 427 428 rb_link_node_rcu(&new->node, parent, p); 429 rb_insert_color(&new->node, &priv->root); 430 return 0; 431 } 432 433 static int nft_rbtree_insert(const struct net *net, const struct nft_set *set, 434 const struct nft_set_elem *elem, 435 struct nft_set_ext **ext) 436 { 437 struct nft_rbtree *priv = nft_set_priv(set); 438 struct nft_rbtree_elem *rbe = elem->priv; 439 int err; 440 441 write_lock_bh(&priv->lock); 442 write_seqcount_begin(&priv->count); 443 err = __nft_rbtree_insert(net, set, rbe, ext); 444 write_seqcount_end(&priv->count); 445 write_unlock_bh(&priv->lock); 446 447 return err; 448 } 449 450 static void nft_rbtree_remove(const struct net *net, 451 const struct nft_set *set, 452 const struct nft_set_elem *elem) 453 { 454 struct nft_rbtree *priv = nft_set_priv(set); 455 struct nft_rbtree_elem *rbe = elem->priv; 456 457 write_lock_bh(&priv->lock); 458 write_seqcount_begin(&priv->count); 459 rb_erase(&rbe->node, &priv->root); 460 write_seqcount_end(&priv->count); 461 write_unlock_bh(&priv->lock); 462 } 463 464 static void nft_rbtree_activate(const struct net *net, 465 const struct nft_set *set, 466 const struct nft_set_elem *elem) 467 { 468 struct nft_rbtree_elem *rbe = elem->priv; 469 470 nft_set_elem_change_active(net, set, &rbe->ext); 471 nft_set_elem_clear_busy(&rbe->ext); 472 } 473 474 static bool nft_rbtree_flush(const struct net *net, 475 const struct nft_set *set, void *priv) 476 { 477 struct nft_rbtree_elem *rbe = priv; 478 479 if (!nft_set_elem_mark_busy(&rbe->ext) || 480 !nft_is_active(net, &rbe->ext)) { 481 nft_set_elem_change_active(net, set, &rbe->ext); 482 return true; 483 } 484 return false; 485 } 486 487 static void *nft_rbtree_deactivate(const struct net *net, 488 const struct nft_set *set, 489 const struct nft_set_elem *elem) 490 { 491 const struct nft_rbtree *priv = nft_set_priv(set); 492 const struct rb_node *parent = priv->root.rb_node; 493 struct nft_rbtree_elem *rbe, *this = elem->priv; 494 u8 genmask = nft_genmask_next(net); 495 int d; 496 497 while (parent != NULL) { 498 rbe = rb_entry(parent, struct nft_rbtree_elem, node); 499 500 d = memcmp(nft_set_ext_key(&rbe->ext), &elem->key.val, 501 set->klen); 502 if (d < 0) 503 parent = parent->rb_left; 504 else if (d > 0) 505 parent = parent->rb_right; 506 else { 507 if (nft_rbtree_interval_end(rbe) && 508 nft_rbtree_interval_start(this)) { 509 parent = parent->rb_left; 510 continue; 511 } else if (nft_rbtree_interval_start(rbe) && 512 nft_rbtree_interval_end(this)) { 513 parent = parent->rb_right; 514 continue; 515 } else if (!nft_set_elem_active(&rbe->ext, genmask)) { 516 parent = parent->rb_left; 517 continue; 518 } 519 nft_rbtree_flush(net, set, rbe); 520 return rbe; 521 } 522 } 523 return NULL; 524 } 525 526 static void nft_rbtree_walk(const struct nft_ctx *ctx, 527 struct nft_set *set, 528 struct nft_set_iter *iter) 529 { 530 struct nft_rbtree *priv = nft_set_priv(set); 531 struct nft_rbtree_elem *rbe; 532 struct nft_set_elem elem; 533 struct rb_node *node; 534 535 read_lock_bh(&priv->lock); 536 for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) { 537 rbe = rb_entry(node, struct nft_rbtree_elem, node); 538 539 if (iter->count < iter->skip) 540 goto cont; 541 if (nft_set_elem_expired(&rbe->ext)) 542 goto cont; 543 if (!nft_set_elem_active(&rbe->ext, iter->genmask)) 544 goto cont; 545 546 elem.priv = rbe; 547 548 iter->err = iter->fn(ctx, set, iter, &elem); 549 if (iter->err < 0) { 550 read_unlock_bh(&priv->lock); 551 return; 552 } 553 cont: 554 iter->count++; 555 } 556 read_unlock_bh(&priv->lock); 557 } 558 559 static void nft_rbtree_gc(struct work_struct *work) 560 { 561 struct nft_rbtree_elem *rbe, *rbe_end = NULL, *rbe_prev = NULL; 562 struct nft_set_gc_batch *gcb = NULL; 563 struct nft_rbtree *priv; 564 struct rb_node *node; 565 struct nft_set *set; 566 struct net *net; 567 u8 genmask; 568 569 priv = container_of(work, struct nft_rbtree, gc_work.work); 570 set = nft_set_container_of(priv); 571 net = read_pnet(&set->net); 572 genmask = nft_genmask_cur(net); 573 574 write_lock_bh(&priv->lock); 575 write_seqcount_begin(&priv->count); 576 for (node = rb_first(&priv->root); node != NULL; node = rb_next(node)) { 577 rbe = rb_entry(node, struct nft_rbtree_elem, node); 578 579 if (!nft_set_elem_active(&rbe->ext, genmask)) 580 continue; 581 582 /* elements are reversed in the rbtree for historical reasons, 583 * from highest to lowest value, that is why end element is 584 * always visited before the start element. 585 */ 586 if (nft_rbtree_interval_end(rbe)) { 587 rbe_end = rbe; 588 continue; 589 } 590 if (!nft_set_elem_expired(&rbe->ext)) 591 continue; 592 593 if (nft_set_elem_mark_busy(&rbe->ext)) { 594 rbe_end = NULL; 595 continue; 596 } 597 598 if (rbe_prev) { 599 rb_erase(&rbe_prev->node, &priv->root); 600 rbe_prev = NULL; 601 } 602 gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC); 603 if (!gcb) 604 break; 605 606 atomic_dec(&set->nelems); 607 nft_set_gc_batch_add(gcb, rbe); 608 rbe_prev = rbe; 609 610 if (rbe_end) { 611 atomic_dec(&set->nelems); 612 nft_set_gc_batch_add(gcb, rbe_end); 613 rb_erase(&rbe_end->node, &priv->root); 614 rbe_end = NULL; 615 } 616 node = rb_next(node); 617 if (!node) 618 break; 619 } 620 if (rbe_prev) 621 rb_erase(&rbe_prev->node, &priv->root); 622 write_seqcount_end(&priv->count); 623 write_unlock_bh(&priv->lock); 624 625 rbe = nft_set_catchall_gc(set); 626 if (rbe) { 627 gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC); 628 if (gcb) 629 nft_set_gc_batch_add(gcb, rbe); 630 } 631 nft_set_gc_batch_complete(gcb); 632 633 queue_delayed_work(system_power_efficient_wq, &priv->gc_work, 634 nft_set_gc_interval(set)); 635 } 636 637 static u64 nft_rbtree_privsize(const struct nlattr * const nla[], 638 const struct nft_set_desc *desc) 639 { 640 return sizeof(struct nft_rbtree); 641 } 642 643 static int nft_rbtree_init(const struct nft_set *set, 644 const struct nft_set_desc *desc, 645 const struct nlattr * const nla[]) 646 { 647 struct nft_rbtree *priv = nft_set_priv(set); 648 649 rwlock_init(&priv->lock); 650 seqcount_rwlock_init(&priv->count, &priv->lock); 651 priv->root = RB_ROOT; 652 653 INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rbtree_gc); 654 if (set->flags & NFT_SET_TIMEOUT) 655 queue_delayed_work(system_power_efficient_wq, &priv->gc_work, 656 nft_set_gc_interval(set)); 657 658 return 0; 659 } 660 661 static void nft_rbtree_destroy(const struct nft_set *set) 662 { 663 struct nft_rbtree *priv = nft_set_priv(set); 664 struct nft_rbtree_elem *rbe; 665 struct rb_node *node; 666 667 cancel_delayed_work_sync(&priv->gc_work); 668 rcu_barrier(); 669 while ((node = priv->root.rb_node) != NULL) { 670 rb_erase(node, &priv->root); 671 rbe = rb_entry(node, struct nft_rbtree_elem, node); 672 nft_set_elem_destroy(set, rbe, true); 673 } 674 } 675 676 static bool nft_rbtree_estimate(const struct nft_set_desc *desc, u32 features, 677 struct nft_set_estimate *est) 678 { 679 if (desc->field_count > 1) 680 return false; 681 682 if (desc->size) 683 est->size = sizeof(struct nft_rbtree) + 684 desc->size * sizeof(struct nft_rbtree_elem); 685 else 686 est->size = ~0; 687 688 est->lookup = NFT_SET_CLASS_O_LOG_N; 689 est->space = NFT_SET_CLASS_O_N; 690 691 return true; 692 } 693 694 const struct nft_set_type nft_set_rbtree_type = { 695 .features = NFT_SET_INTERVAL | NFT_SET_MAP | NFT_SET_OBJECT | NFT_SET_TIMEOUT, 696 .ops = { 697 .privsize = nft_rbtree_privsize, 698 .elemsize = offsetof(struct nft_rbtree_elem, ext), 699 .estimate = nft_rbtree_estimate, 700 .init = nft_rbtree_init, 701 .destroy = nft_rbtree_destroy, 702 .insert = nft_rbtree_insert, 703 .remove = nft_rbtree_remove, 704 .deactivate = nft_rbtree_deactivate, 705 .flush = nft_rbtree_flush, 706 .activate = nft_rbtree_activate, 707 .lookup = nft_rbtree_lookup, 708 .walk = nft_rbtree_walk, 709 .get = nft_rbtree_get, 710 }, 711 }; 712