Lines Matching +full:child +full:- +full:node
1 // SPDX-License-Identifier: GPL-2.0-only
19 /* Intermediate node */
26 struct lpm_trie_node __rcu *child[2]; member
49 * lead to more nodes containing more specific matches. Each node also stores
56 * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will
57 * stick to IP-address notation for readability though.
59 * As the trie is empty initially, the new node (1) will be places as root
60 * node, denoted as (R) in the example below. As there are no other node, both
61 * child pointers are %NULL.
63 * +----------------+
68 * +----------------+
70 * Next, let's add a new node (2) matching 192.168.0.0/24. As there is already
71 * a node with the same data and a smaller prefix (ie, a less specific one),
72 * node (2) will become a child of (1). In child index depends on the next bit
74 * child[0] of (1):
76 * +----------------+
81 * +----------------+
83 * +----------------+
88 * +----------------+
90 * The child[1] slot of (1) could be filled with another node which has bit #17
94 * +----------------+
99 * +----------------+
101 * +----------------+ +------------------+
106 * +----------------+ +------------------+
108 * Let's add another node (4) to the game for 192.168.1.0/24. In order to place
109 * it, node (1) is looked at first, and because (4) of the semantics laid out
110 * above (bit #17 is 0), it would normally be attached to (1) as child[0].
111 * However, that slot is already allocated, so a new node is needed in between.
112 * That node does not have a value attached to it and it will never be
117 * +----------------+
122 * +----------------+
124 * +----------------+ +------------------+
127 * | value: --- | | value: 3 |
129 * +----------------+ +------------------+
131 * +----------------+ +----------------+
136 * +----------------+ +----------------+
138 * 192.168.1.1/32 would be a child of (5) etc.
140 * An intermediate node will be turned into a 'real' node on demand. In the
141 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
146 * The lookup starts at the root node. If the current node matches and if there
147 * is a child that can be used to become more specific, the trie is traversed
148 * downwards. The last node in the traversal that is a non-intermediate one is
154 return !!(data[index / 8] & (1 << (7 - (index % 8)))); in extract_bit()
158 * longest_prefix_match() - determine the longest prefix
160 * @node: The node to operate on
161 * @key: The key to compare to @node
163 * Determine the longest prefix of @node that matches the bits in @key.
166 const struct lpm_trie_node *node, in longest_prefix_match() argument
169 u32 limit = min(node->prefixlen, key->prefixlen); in longest_prefix_match()
180 if (trie->data_size >= 8) { in longest_prefix_match()
181 u64 diff = be64_to_cpu(*(__be64 *)node->data ^ in longest_prefix_match()
182 *(__be64 *)key->data); in longest_prefix_match()
184 prefixlen = 64 - fls64(diff); in longest_prefix_match()
193 while (trie->data_size >= i + 4) { in longest_prefix_match()
194 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^ in longest_prefix_match()
195 *(__be32 *)&key->data[i]); in longest_prefix_match()
197 prefixlen += 32 - fls(diff); in longest_prefix_match()
205 if (trie->data_size >= i + 2) { in longest_prefix_match()
206 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^ in longest_prefix_match()
207 *(__be16 *)&key->data[i]); in longest_prefix_match()
209 prefixlen += 16 - fls(diff); in longest_prefix_match()
217 if (trie->data_size >= i + 1) { in longest_prefix_match()
218 prefixlen += 8 - fls(node->data[i] ^ key->data[i]); in longest_prefix_match()
231 struct lpm_trie_node *node, *found = NULL; in trie_lookup_elem() local
234 /* Start walking the trie from the root node ... */ in trie_lookup_elem()
236 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
237 node;) { in trie_lookup_elem()
241 /* Determine the longest prefix of @node that matches @key. in trie_lookup_elem()
245 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
246 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
247 found = node; in trie_lookup_elem()
252 * length of @node, bail out and return the node we have seen in trie_lookup_elem()
255 if (matchlen < node->prefixlen) in trie_lookup_elem()
258 /* Consider this node as return candidate unless it is an in trie_lookup_elem()
261 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_lookup_elem()
262 found = node; in trie_lookup_elem()
264 /* If the node match is fully satisfied, let's see if we can in trie_lookup_elem()
268 next_bit = extract_bit(key->data, node->prefixlen); in trie_lookup_elem()
269 node = rcu_dereference_check(node->child[next_bit], in trie_lookup_elem()
276 return found->data + trie->data_size; in trie_lookup_elem()
282 struct lpm_trie_node *node; in lpm_trie_node_alloc() local
283 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; in lpm_trie_node_alloc()
286 size += trie->map.value_size; in lpm_trie_node_alloc()
288 node = bpf_map_kmalloc_node(&trie->map, size, GFP_NOWAIT | __GFP_NOWARN, in lpm_trie_node_alloc()
289 trie->map.numa_node); in lpm_trie_node_alloc()
290 if (!node) in lpm_trie_node_alloc()
293 node->flags = 0; in lpm_trie_node_alloc()
296 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
297 trie->map.value_size); in lpm_trie_node_alloc()
299 return node; in lpm_trie_node_alloc()
307 struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL; in trie_update_elem() local
316 return -EINVAL; in trie_update_elem()
318 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
319 return -EINVAL; in trie_update_elem()
321 spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
323 /* Allocate and fill a new node */ in trie_update_elem()
325 if (trie->n_entries == trie->map.max_entries) { in trie_update_elem()
326 ret = -ENOSPC; in trie_update_elem()
332 ret = -ENOMEM; in trie_update_elem()
336 trie->n_entries++; in trie_update_elem()
338 new_node->prefixlen = key->prefixlen; in trie_update_elem()
339 RCU_INIT_POINTER(new_node->child[0], NULL); in trie_update_elem()
340 RCU_INIT_POINTER(new_node->child[1], NULL); in trie_update_elem()
341 memcpy(new_node->data, key->data, trie->data_size); in trie_update_elem()
343 /* Now find a slot to attach the new node. To do that, walk the tree in trie_update_elem()
344 * from the root and match as many bits as possible for each node until in trie_update_elem()
346 * an intermediate node. in trie_update_elem()
348 slot = &trie->root; in trie_update_elem()
350 while ((node = rcu_dereference_protected(*slot, in trie_update_elem()
351 lockdep_is_held(&trie->lock)))) { in trie_update_elem()
352 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
354 if (node->prefixlen != matchlen || in trie_update_elem()
355 node->prefixlen == key->prefixlen || in trie_update_elem()
356 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
359 next_bit = extract_bit(key->data, node->prefixlen); in trie_update_elem()
360 slot = &node->child[next_bit]; in trie_update_elem()
363 /* If the slot is empty (a free child pointer or an empty root), in trie_update_elem()
366 if (!node) { in trie_update_elem()
374 if (node->prefixlen == matchlen) { in trie_update_elem()
375 new_node->child[0] = node->child[0]; in trie_update_elem()
376 new_node->child[1] = node->child[1]; in trie_update_elem()
378 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_update_elem()
379 trie->n_entries--; in trie_update_elem()
382 kfree_rcu(node, rcu); in trie_update_elem()
387 /* If the new node matches the prefix completely, it must be inserted in trie_update_elem()
388 * as an ancestor. Simply insert it between @node and *@slot. in trie_update_elem()
390 if (matchlen == key->prefixlen) { in trie_update_elem()
391 next_bit = extract_bit(node->data, matchlen); in trie_update_elem()
392 rcu_assign_pointer(new_node->child[next_bit], node); in trie_update_elem()
399 ret = -ENOMEM; in trie_update_elem()
403 im_node->prefixlen = matchlen; in trie_update_elem()
404 im_node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_update_elem()
405 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
407 /* Now determine which child to install in which slot */ in trie_update_elem()
408 if (extract_bit(key->data, matchlen)) { in trie_update_elem()
409 rcu_assign_pointer(im_node->child[0], node); in trie_update_elem()
410 rcu_assign_pointer(im_node->child[1], new_node); in trie_update_elem()
412 rcu_assign_pointer(im_node->child[0], new_node); in trie_update_elem()
413 rcu_assign_pointer(im_node->child[1], node); in trie_update_elem()
416 /* Finally, assign the intermediate node to the determined slot */ in trie_update_elem()
422 trie->n_entries--; in trie_update_elem()
428 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
439 struct lpm_trie_node *node, *parent; in trie_delete_elem() local
445 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
446 return -EINVAL; in trie_delete_elem()
448 spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
451 * track of the path we traverse. We will need to know the node in trie_delete_elem()
452 * we wish to delete, and the slot that points to the node we want in trie_delete_elem()
456 trim = &trie->root; in trie_delete_elem()
459 while ((node = rcu_dereference_protected( in trie_delete_elem()
460 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
461 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
463 if (node->prefixlen != matchlen || in trie_delete_elem()
464 node->prefixlen == key->prefixlen) in trie_delete_elem()
467 parent = node; in trie_delete_elem()
469 next_bit = extract_bit(key->data, node->prefixlen); in trie_delete_elem()
470 trim = &node->child[next_bit]; in trie_delete_elem()
473 if (!node || node->prefixlen != key->prefixlen || in trie_delete_elem()
474 node->prefixlen != matchlen || in trie_delete_elem()
475 (node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_delete_elem()
476 ret = -ENOENT; in trie_delete_elem()
480 trie->n_entries--; in trie_delete_elem()
482 /* If the node we are removing has two children, simply mark it in trie_delete_elem()
485 if (rcu_access_pointer(node->child[0]) && in trie_delete_elem()
486 rcu_access_pointer(node->child[1])) { in trie_delete_elem()
487 node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_delete_elem()
491 /* If the parent of the node we are about to delete is an intermediate in trie_delete_elem()
492 * node, and the deleted node doesn't have any children, we can delete in trie_delete_elem()
493 * the intermediate parent as well and promote its other child in trie_delete_elem()
498 if (parent && (parent->flags & LPM_TREE_NODE_FLAG_IM) && in trie_delete_elem()
499 !node->child[0] && !node->child[1]) { in trie_delete_elem()
500 if (node == rcu_access_pointer(parent->child[0])) in trie_delete_elem()
502 *trim2, rcu_access_pointer(parent->child[1])); in trie_delete_elem()
505 *trim2, rcu_access_pointer(parent->child[0])); in trie_delete_elem()
507 kfree_rcu(node, rcu); in trie_delete_elem()
511 /* The node we are removing has either zero or one child. If there in trie_delete_elem()
512 * is a child, move it into the removed node's slot then delete in trie_delete_elem()
513 * the node. Otherwise just clear the slot and delete the node. in trie_delete_elem()
515 if (node->child[0]) in trie_delete_elem()
516 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0])); in trie_delete_elem()
517 else if (node->child[1]) in trie_delete_elem()
518 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1])); in trie_delete_elem()
521 kfree_rcu(node, rcu); in trie_delete_elem()
524 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
532 #define LPM_VAL_SIZE_MAX (KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \
548 if (attr->max_entries == 0 || in trie_alloc()
549 !(attr->map_flags & BPF_F_NO_PREALLOC) || in trie_alloc()
550 attr->map_flags & ~LPM_CREATE_FLAG_MASK || in trie_alloc()
551 !bpf_map_flags_access_ok(attr->map_flags) || in trie_alloc()
552 attr->key_size < LPM_KEY_SIZE_MIN || in trie_alloc()
553 attr->key_size > LPM_KEY_SIZE_MAX || in trie_alloc()
554 attr->value_size < LPM_VAL_SIZE_MIN || in trie_alloc()
555 attr->value_size > LPM_VAL_SIZE_MAX) in trie_alloc()
556 return ERR_PTR(-EINVAL); in trie_alloc()
560 return ERR_PTR(-ENOMEM); in trie_alloc()
563 bpf_map_init_from_attr(&trie->map, attr); in trie_alloc()
564 trie->data_size = attr->key_size - in trie_alloc()
566 trie->max_prefixlen = trie->data_size * 8; in trie_alloc()
568 spin_lock_init(&trie->lock); in trie_alloc()
570 return &trie->map; in trie_alloc()
577 struct lpm_trie_node *node; in trie_free() local
579 /* Always start at the root and walk down to a node that has no in trie_free()
580 * children. Then free that node, nullify its reference in the parent in trie_free()
585 slot = &trie->root; in trie_free()
588 node = rcu_dereference_protected(*slot, 1); in trie_free()
589 if (!node) in trie_free()
592 if (rcu_access_pointer(node->child[0])) { in trie_free()
593 slot = &node->child[0]; in trie_free()
597 if (rcu_access_pointer(node->child[1])) { in trie_free()
598 slot = &node->child[1]; in trie_free()
602 kfree(node); in trie_free()
614 struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root; in trie_get_next_key() local
618 int err = 0, stack_ptr = -1; in trie_get_next_key()
622 /* The get_next_key follows postorder. For the 4 node example in in trie_get_next_key()
634 search_root = rcu_dereference(trie->root); in trie_get_next_key()
636 return -ENOENT; in trie_get_next_key()
638 /* For invalid key, find the leftmost node in the trie */ in trie_get_next_key()
639 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
642 node_stack = kmalloc_array(trie->max_prefixlen, in trie_get_next_key()
646 return -ENOMEM; in trie_get_next_key()
648 /* Try to find the exact node for the given key */ in trie_get_next_key()
649 for (node = search_root; node;) { in trie_get_next_key()
650 node_stack[++stack_ptr] = node; in trie_get_next_key()
651 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
652 if (node->prefixlen != matchlen || in trie_get_next_key()
653 node->prefixlen == key->prefixlen) in trie_get_next_key()
656 next_bit = extract_bit(key->data, node->prefixlen); in trie_get_next_key()
657 node = rcu_dereference(node->child[next_bit]); in trie_get_next_key()
659 if (!node || node->prefixlen != key->prefixlen || in trie_get_next_key()
660 (node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_get_next_key()
663 /* The node with the exactly-matching key has been found, in trie_get_next_key()
664 * find the first node in postorder after the matched node. in trie_get_next_key()
666 node = node_stack[stack_ptr]; in trie_get_next_key()
668 parent = node_stack[stack_ptr - 1]; in trie_get_next_key()
669 if (rcu_dereference(parent->child[0]) == node) { in trie_get_next_key()
670 search_root = rcu_dereference(parent->child[1]); in trie_get_next_key()
674 if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_get_next_key()
679 node = parent; in trie_get_next_key()
680 stack_ptr--; in trie_get_next_key()
684 err = -ENOENT; in trie_get_next_key()
688 /* Find the leftmost non-intermediate node, all intermediate nodes in trie_get_next_key()
691 for (node = search_root; node;) { in trie_get_next_key()
692 if (node->flags & LPM_TREE_NODE_FLAG_IM) { in trie_get_next_key()
693 node = rcu_dereference(node->child[0]); in trie_get_next_key()
695 next_node = node; in trie_get_next_key()
696 node = rcu_dereference(node->child[0]); in trie_get_next_key()
697 if (!node) in trie_get_next_key()
698 node = rcu_dereference(next_node->child[1]); in trie_get_next_key()
702 next_key->prefixlen = next_node->prefixlen; in trie_get_next_key()
704 next_node->data, trie->data_size); in trie_get_next_key()
716 return BTF_INFO_KIND(key_type->info) != BTF_KIND_STRUCT ? in trie_check_btf()
717 -EINVAL : 0; in trie_check_btf()
725 elem_size = sizeof(struct lpm_trie_node) + trie->data_size + in trie_mem_usage()
726 trie->map.value_size; in trie_mem_usage()
727 return elem_size * READ_ONCE(trie->n_entries); in trie_mem_usage()