Lines Matching +full:child +full:- +full:nodes
1 // SPDX-License-Identifier: GPL-2.0-only
26 struct lpm_trie_node __rcu *child[2]; member
50 * lead to more nodes containing more specific matches. Each node also stores
57 * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will
58 * stick to IP-address notation for readability though.
62 * child pointers are %NULL.
64 * +----------------+
69 * +----------------+
73 * node (2) will become a child of (1). In child index depends on the next bit
75 * child[0] of (1):
77 * +----------------+
82 * +----------------+
84 * +----------------+
89 * +----------------+
91 * The child[1] slot of (1) could be filled with another node which has bit #17
95 * +----------------+
100 * +----------------+
102 * +----------------+ +------------------+
107 * +----------------+ +------------------+
111 * above (bit #17 is 0), it would normally be attached to (1) as child[0].
118 * +----------------+
123 * +----------------+
125 * +----------------+ +------------------+
128 * | value: --- | | value: 3 |
130 * +----------------+ +------------------+
132 * +----------------+ +----------------+
137 * +----------------+ +----------------+
139 * 192.168.1.1/32 would be a child of (5) etc.
142 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
144 * A fully populated trie would have a height of 32 nodes, as the trie was
148 * is a child that can be used to become more specific, the trie is traversed
149 * downwards. The last node in the traversal that is a non-intermediate one is
155 return !!(data[index / 8] & (1 << (7 - (index % 8)))); in extract_bit()
159 * __longest_prefix_match() - determine the longest prefix
171 u32 limit = min(node->prefixlen, key->prefixlen); in __longest_prefix_match()
182 if (trie->data_size >= 8) { in __longest_prefix_match()
183 u64 diff = be64_to_cpu(*(__be64 *)node->data ^ in __longest_prefix_match()
184 *(__be64 *)key->data); in __longest_prefix_match()
186 prefixlen = 64 - fls64(diff); in __longest_prefix_match()
195 while (trie->data_size >= i + 4) { in __longest_prefix_match()
196 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^ in __longest_prefix_match()
197 *(__be32 *)&key->data[i]); in __longest_prefix_match()
199 prefixlen += 32 - fls(diff); in __longest_prefix_match()
207 if (trie->data_size >= i + 2) { in __longest_prefix_match()
208 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^ in __longest_prefix_match()
209 *(__be16 *)&key->data[i]); in __longest_prefix_match()
211 prefixlen += 16 - fls(diff); in __longest_prefix_match()
219 if (trie->data_size >= i + 1) { in __longest_prefix_match()
220 prefixlen += 8 - fls(node->data[i] ^ key->data[i]); in __longest_prefix_match()
243 if (key->prefixlen > trie->max_prefixlen) in trie_lookup_elem()
248 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
258 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
267 if (matchlen < node->prefixlen) in trie_lookup_elem()
273 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_lookup_elem()
280 next_bit = extract_bit(key->data, node->prefixlen); in trie_lookup_elem()
281 node = rcu_dereference_check(node->child[next_bit], in trie_lookup_elem()
288 return found->data + trie->data_size; in trie_lookup_elem()
296 node = bpf_mem_cache_alloc(&trie->ma); in lpm_trie_node_alloc()
301 node->flags = 0; in lpm_trie_node_alloc()
304 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
305 trie->map.value_size); in lpm_trie_node_alloc()
313 return -ENOENT; in trie_check_add_elem()
314 if (trie->n_entries == trie->map.max_entries) in trie_check_add_elem()
315 return -ENOSPC; in trie_check_add_elem()
316 trie->n_entries++; in trie_check_add_elem()
335 return -EINVAL; in trie_update_elem()
337 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
338 return -EINVAL; in trie_update_elem()
343 return -ENOMEM; in trie_update_elem()
345 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
347 new_node->prefixlen = key->prefixlen; in trie_update_elem()
348 RCU_INIT_POINTER(new_node->child[0], NULL); in trie_update_elem()
349 RCU_INIT_POINTER(new_node->child[1], NULL); in trie_update_elem()
350 memcpy(new_node->data, key->data, trie->data_size); in trie_update_elem()
357 slot = &trie->root; in trie_update_elem()
360 lockdep_is_held(&trie->lock)))) { in trie_update_elem()
363 if (node->prefixlen != matchlen || in trie_update_elem()
364 node->prefixlen == key->prefixlen) in trie_update_elem()
367 next_bit = extract_bit(key->data, node->prefixlen); in trie_update_elem()
368 slot = &node->child[next_bit]; in trie_update_elem()
371 /* If the slot is empty (a free child pointer or an empty root), in trie_update_elem()
386 if (node->prefixlen == matchlen) { in trie_update_elem()
387 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_update_elem()
389 ret = -EEXIST; in trie_update_elem()
398 new_node->child[0] = node->child[0]; in trie_update_elem()
399 new_node->child[1] = node->child[1]; in trie_update_elem()
414 if (matchlen == key->prefixlen) { in trie_update_elem()
415 next_bit = extract_bit(node->data, matchlen); in trie_update_elem()
416 rcu_assign_pointer(new_node->child[next_bit], node); in trie_update_elem()
423 trie->n_entries--; in trie_update_elem()
424 ret = -ENOMEM; in trie_update_elem()
428 im_node->prefixlen = matchlen; in trie_update_elem()
429 im_node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_update_elem()
430 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
432 /* Now determine which child to install in which slot */ in trie_update_elem()
433 if (extract_bit(key->data, matchlen)) { in trie_update_elem()
434 rcu_assign_pointer(im_node->child[0], node); in trie_update_elem()
435 rcu_assign_pointer(im_node->child[1], new_node); in trie_update_elem()
437 rcu_assign_pointer(im_node->child[0], new_node); in trie_update_elem()
438 rcu_assign_pointer(im_node->child[1], node); in trie_update_elem()
445 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
448 bpf_mem_cache_free(&trie->ma, new_node); in trie_update_elem()
449 bpf_mem_cache_free_rcu(&trie->ma, free_node); in trie_update_elem()
467 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
468 return -EINVAL; in trie_delete_elem()
470 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
475 * to delete. We may also need to know the nodes parent and the in trie_delete_elem()
478 trim = &trie->root; in trie_delete_elem()
482 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
485 if (node->prefixlen != matchlen || in trie_delete_elem()
486 node->prefixlen == key->prefixlen) in trie_delete_elem()
491 next_bit = extract_bit(key->data, node->prefixlen); in trie_delete_elem()
492 trim = &node->child[next_bit]; in trie_delete_elem()
495 if (!node || node->prefixlen != key->prefixlen || in trie_delete_elem()
496 node->prefixlen != matchlen || in trie_delete_elem()
497 (node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_delete_elem()
498 ret = -ENOENT; in trie_delete_elem()
502 trie->n_entries--; in trie_delete_elem()
507 if (rcu_access_pointer(node->child[0]) && in trie_delete_elem()
508 rcu_access_pointer(node->child[1])) { in trie_delete_elem()
509 node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_delete_elem()
515 * the intermediate parent as well and promote its other child in trie_delete_elem()
517 * intermediate nodes have exactly 2 children and that there are no in trie_delete_elem()
518 * unnecessary intermediate nodes in the tree. in trie_delete_elem()
520 if (parent && (parent->flags & LPM_TREE_NODE_FLAG_IM) && in trie_delete_elem()
521 !node->child[0] && !node->child[1]) { in trie_delete_elem()
522 if (node == rcu_access_pointer(parent->child[0])) in trie_delete_elem()
524 *trim2, rcu_access_pointer(parent->child[1])); in trie_delete_elem()
527 *trim2, rcu_access_pointer(parent->child[0])); in trie_delete_elem()
533 /* The node we are removing has either zero or one child. If there in trie_delete_elem()
534 * is a child, move it into the removed node's slot then delete in trie_delete_elem()
537 if (node->child[0]) in trie_delete_elem()
538 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0])); in trie_delete_elem()
539 else if (node->child[1]) in trie_delete_elem()
540 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1])); in trie_delete_elem()
546 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
548 bpf_mem_cache_free_rcu(&trie->ma, free_parent); in trie_delete_elem()
549 bpf_mem_cache_free_rcu(&trie->ma, free_node); in trie_delete_elem()
557 #define LPM_VAL_SIZE_MAX (KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \
575 if (attr->max_entries == 0 || in trie_alloc()
576 !(attr->map_flags & BPF_F_NO_PREALLOC) || in trie_alloc()
577 attr->map_flags & ~LPM_CREATE_FLAG_MASK || in trie_alloc()
578 !bpf_map_flags_access_ok(attr->map_flags) || in trie_alloc()
579 attr->key_size < LPM_KEY_SIZE_MIN || in trie_alloc()
580 attr->key_size > LPM_KEY_SIZE_MAX || in trie_alloc()
581 attr->value_size < LPM_VAL_SIZE_MIN || in trie_alloc()
582 attr->value_size > LPM_VAL_SIZE_MAX) in trie_alloc()
583 return ERR_PTR(-EINVAL); in trie_alloc()
587 return ERR_PTR(-ENOMEM); in trie_alloc()
590 bpf_map_init_from_attr(&trie->map, attr); in trie_alloc()
591 trie->data_size = attr->key_size - in trie_alloc()
593 trie->max_prefixlen = trie->data_size * 8; in trie_alloc()
595 raw_spin_lock_init(&trie->lock); in trie_alloc()
597 /* Allocate intermediate and leaf nodes from the same allocator */ in trie_alloc()
598 leaf_size = sizeof(struct lpm_trie_node) + trie->data_size + in trie_alloc()
599 trie->map.value_size; in trie_alloc()
600 err = bpf_mem_alloc_init(&trie->ma, leaf_size, false); in trie_alloc()
603 return &trie->map; in trie_alloc()
622 slot = &trie->root; in trie_free()
629 if (rcu_access_pointer(node->child[0])) { in trie_free()
630 slot = &node->child[0]; in trie_free()
634 if (rcu_access_pointer(node->child[1])) { in trie_free()
635 slot = &node->child[1]; in trie_free()
649 bpf_mem_alloc_destroy(&trie->ma); in trie_free()
659 int err = 0, stack_ptr = -1; in trie_get_next_key()
675 search_root = rcu_dereference(trie->root); in trie_get_next_key()
677 return -ENOENT; in trie_get_next_key()
680 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
683 node_stack = kmalloc_array(trie->max_prefixlen + 1, in trie_get_next_key()
687 return -ENOMEM; in trie_get_next_key()
693 if (node->prefixlen != matchlen || in trie_get_next_key()
694 node->prefixlen == key->prefixlen) in trie_get_next_key()
697 next_bit = extract_bit(key->data, node->prefixlen); in trie_get_next_key()
698 node = rcu_dereference(node->child[next_bit]); in trie_get_next_key()
700 if (!node || node->prefixlen != matchlen || in trie_get_next_key()
701 (node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_get_next_key()
704 /* The node with the exactly-matching key has been found, in trie_get_next_key()
709 parent = node_stack[stack_ptr - 1]; in trie_get_next_key()
710 if (rcu_dereference(parent->child[0]) == node) { in trie_get_next_key()
711 search_root = rcu_dereference(parent->child[1]); in trie_get_next_key()
715 if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_get_next_key()
721 stack_ptr--; in trie_get_next_key()
725 err = -ENOENT; in trie_get_next_key()
729 /* Find the leftmost non-intermediate node, all intermediate nodes in trie_get_next_key()
733 if (node->flags & LPM_TREE_NODE_FLAG_IM) { in trie_get_next_key()
734 node = rcu_dereference(node->child[0]); in trie_get_next_key()
737 node = rcu_dereference(node->child[0]); in trie_get_next_key()
739 node = rcu_dereference(next_node->child[1]); in trie_get_next_key()
743 next_key->prefixlen = next_node->prefixlen; in trie_get_next_key()
745 next_node->data, trie->data_size); in trie_get_next_key()
757 return BTF_INFO_KIND(key_type->info) != BTF_KIND_STRUCT ? in trie_check_btf()
758 -EINVAL : 0; in trie_check_btf()
766 elem_size = sizeof(struct lpm_trie_node) + trie->data_size + in trie_mem_usage()
767 trie->map.value_size; in trie_mem_usage()
768 return elem_size * READ_ONCE(trie->n_entries); in trie_mem_usage()