Lines Matching refs:node
169 const struct lpm_trie_node *node, in __longest_prefix_match() argument
172 u32 limit = min(node->prefixlen, key->prefixlen); in __longest_prefix_match()
184 u64 diff = be64_to_cpu(*(__be64 *)node->data ^ in __longest_prefix_match()
197 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^ in __longest_prefix_match()
209 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^ in __longest_prefix_match()
221 prefixlen += 8 - fls(node->data[i] ^ key->data[i]); in __longest_prefix_match()
231 const struct lpm_trie_node *node, in longest_prefix_match() argument
234 return __longest_prefix_match(trie, node, key); in longest_prefix_match()
241 struct lpm_trie_node *node, *found = NULL; in trie_lookup_elem() local
249 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
250 node;) { in trie_lookup_elem()
258 matchlen = __longest_prefix_match(trie, node, key); in trie_lookup_elem()
260 found = node; in trie_lookup_elem()
268 if (matchlen < node->prefixlen) in trie_lookup_elem()
274 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_lookup_elem()
275 found = node; in trie_lookup_elem()
281 next_bit = extract_bit(key->data, node->prefixlen); in trie_lookup_elem()
282 node = rcu_dereference_check(node->child[next_bit], in trie_lookup_elem()
295 struct lpm_trie_node *node; in lpm_trie_node_alloc() local
297 node = bpf_mem_cache_alloc(&trie->ma); in lpm_trie_node_alloc()
299 if (!node) in lpm_trie_node_alloc()
302 node->flags = 0; in lpm_trie_node_alloc()
305 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
308 return node; in lpm_trie_node_alloc()
326 struct lpm_trie_node *node, *im_node, *new_node; in trie_update_elem() local
362 while ((node = rcu_dereference(*slot))) { in trie_update_elem()
363 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
365 if (node->prefixlen != matchlen || in trie_update_elem()
366 node->prefixlen == key->prefixlen) in trie_update_elem()
369 next_bit = extract_bit(key->data, node->prefixlen); in trie_update_elem()
370 slot = &node->child[next_bit]; in trie_update_elem()
376 if (!node) { in trie_update_elem()
388 if (node->prefixlen == matchlen) { in trie_update_elem()
389 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_update_elem()
400 new_node->child[0] = node->child[0]; in trie_update_elem()
401 new_node->child[1] = node->child[1]; in trie_update_elem()
404 free_node = node; in trie_update_elem()
417 next_bit = extract_bit(node->data, matchlen); in trie_update_elem()
418 rcu_assign_pointer(new_node->child[next_bit], node); in trie_update_elem()
432 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
436 rcu_assign_pointer(im_node->child[0], node); in trie_update_elem()
440 rcu_assign_pointer(im_node->child[1], node); in trie_update_elem()
463 struct lpm_trie_node *node, *parent; in trie_delete_elem() local
485 while ((node = rcu_dereference(*trim))) { in trie_delete_elem()
486 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
488 if (node->prefixlen != matchlen || in trie_delete_elem()
489 node->prefixlen == key->prefixlen) in trie_delete_elem()
492 parent = node; in trie_delete_elem()
494 next_bit = extract_bit(key->data, node->prefixlen); in trie_delete_elem()
495 trim = &node->child[next_bit]; in trie_delete_elem()
498 if (!node || node->prefixlen != key->prefixlen || in trie_delete_elem()
499 node->prefixlen != matchlen || in trie_delete_elem()
500 (node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_delete_elem()
510 if (rcu_access_pointer(node->child[0]) && in trie_delete_elem()
511 rcu_access_pointer(node->child[1])) { in trie_delete_elem()
512 node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_delete_elem()
524 !node->child[0] && !node->child[1]) { in trie_delete_elem()
525 if (node == rcu_access_pointer(parent->child[0])) in trie_delete_elem()
532 free_node = node; in trie_delete_elem()
540 if (node->child[0]) in trie_delete_elem()
541 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0])); in trie_delete_elem()
542 else if (node->child[1]) in trie_delete_elem()
543 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1])); in trie_delete_elem()
546 free_node = node; in trie_delete_elem()
617 struct lpm_trie_node *node; in trie_free() local
628 node = rcu_dereference_protected(*slot, 1); in trie_free()
629 if (!node) in trie_free()
632 if (rcu_access_pointer(node->child[0])) { in trie_free()
633 slot = &node->child[0]; in trie_free()
637 if (rcu_access_pointer(node->child[1])) { in trie_free()
638 slot = &node->child[1]; in trie_free()
645 bpf_mem_cache_raw_free(node); in trie_free()
658 struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root; in trie_get_next_key() local
693 for (node = search_root; node;) { in trie_get_next_key()
694 node_stack[++stack_ptr] = node; in trie_get_next_key()
695 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
696 if (node->prefixlen != matchlen || in trie_get_next_key()
697 node->prefixlen == key->prefixlen) in trie_get_next_key()
700 next_bit = extract_bit(key->data, node->prefixlen); in trie_get_next_key()
701 node = rcu_dereference(node->child[next_bit]); in trie_get_next_key()
703 if (!node || node->prefixlen != matchlen || in trie_get_next_key()
704 (node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_get_next_key()
710 node = node_stack[stack_ptr]; in trie_get_next_key()
713 if (rcu_dereference(parent->child[0]) == node) { in trie_get_next_key()
723 node = parent; in trie_get_next_key()
735 for (node = search_root; node;) { in trie_get_next_key()
736 if (node->flags & LPM_TREE_NODE_FLAG_IM) { in trie_get_next_key()
737 node = rcu_dereference(node->child[0]); in trie_get_next_key()
739 next_node = node; in trie_get_next_key()
740 node = rcu_dereference(node->child[0]); in trie_get_next_key()
741 if (!node) in trie_get_next_key()
742 node = rcu_dereference(next_node->child[1]); in trie_get_next_key()