19 /* Intermediate node */
49  * lead to more nodes containing more specific matches. Each node also stores
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
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
90  * The child[1] slot of (1) could be filled with another node which has bit #17
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
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
140  * An intermediate node will be turned into a 'real' node on demand. In the
146  * The lookup starts at the root node. If the current node matches and if there
148  * downwards. The last node in the traversal that is a non-intermediate one is
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.
167 			      const struct lpm_trie_node *node,  in __longest_prefix_match()  argument
170 	u32 limit = min(node->prefixlen, key->prefixlen);  in __longest_prefix_match()
182 		u64 diff = be64_to_cpu(*(__be64 *)node->data ^  in __longest_prefix_match()
195 		u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^  in __longest_prefix_match()
207 		u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^  in __longest_prefix_match()
219 		prefixlen += 8 - fls(node->data[i] ^ key->data[i]);  in __longest_prefix_match()
229 				   const struct lpm_trie_node *node,  in longest_prefix_match()  argument
232 	return __longest_prefix_match(trie, node, key);  in longest_prefix_match()
239 	struct lpm_trie_node *node, *found = NULL;  in trie_lookup_elem()  local
245 	/* Start walking the trie from the root node ... */  in trie_lookup_elem()
247 	for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());  in trie_lookup_elem()
248 	     node;) {  in trie_lookup_elem()
252 		/* Determine the longest prefix of @node that matches @key.  in trie_lookup_elem()
256 		matchlen = __longest_prefix_match(trie, node, key);  in trie_lookup_elem()
258 			found = node;  in trie_lookup_elem()
263 		 * length of @node, bail out and return the node we have seen  in trie_lookup_elem()
266 		if (matchlen < node->prefixlen)  in trie_lookup_elem()
269 		/* Consider this node as return candidate unless it is an  in trie_lookup_elem()
272 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_lookup_elem()
273 			found = node;  in trie_lookup_elem()
275 		/* If the node match is fully satisfied, let's see if we can  in trie_lookup_elem()
279 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_lookup_elem()
280 		node = rcu_dereference_check(node->child[next_bit],  in trie_lookup_elem()
293 	struct lpm_trie_node *node;  in lpm_trie_node_alloc()  local
299 	node = bpf_map_kmalloc_node(&trie->map, size, GFP_NOWAIT | __GFP_NOWARN,  in lpm_trie_node_alloc()
301 	if (!node)  in lpm_trie_node_alloc()
304 	node->flags = 0;  in lpm_trie_node_alloc()
307 		memcpy(node->data + trie->data_size, value,  in lpm_trie_node_alloc()
310 	return node;  in lpm_trie_node_alloc()
318 	struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL;  in trie_update_elem()  local
335 	/* Allocate and fill a new node */  in trie_update_elem()
355 	/* Now find a slot to attach the new node. To do that, walk the tree  in trie_update_elem()
356 	 * from the root and match as many bits as possible for each node until  in trie_update_elem()
358 	 * an intermediate node.  in trie_update_elem()
362 	while ((node = rcu_dereference_protected(*slot,  in trie_update_elem()
364 		matchlen = longest_prefix_match(trie, node, key);  in trie_update_elem()
366 		if (node->prefixlen != matchlen ||  in trie_update_elem()
367 		    node->prefixlen == key->prefixlen ||  in trie_update_elem()
368 		    node->prefixlen == trie->max_prefixlen)  in trie_update_elem()
371 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_update_elem()
372 		slot = &node->child[next_bit];  in trie_update_elem()
378 	if (!node) {  in trie_update_elem()
386 	if (node->prefixlen == matchlen) {  in trie_update_elem()
387 		new_node->child[0] = node->child[0];  in trie_update_elem()
388 		new_node->child[1] = node->child[1];  in trie_update_elem()
390 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_update_elem()
394 		free_node = node;  in trie_update_elem()
399 	/* If the new node matches the prefix completely, it must be inserted  in trie_update_elem()
400 	 * as an ancestor. Simply insert it between @node and *@slot.  in trie_update_elem()
403 		next_bit = extract_bit(node->data, matchlen);  in trie_update_elem()
404 		rcu_assign_pointer(new_node->child[next_bit], node);  in trie_update_elem()
417 	memcpy(im_node->data, node->data, trie->data_size);  in trie_update_elem()
421 		rcu_assign_pointer(im_node->child[0], node);  in trie_update_elem()
425 		rcu_assign_pointer(im_node->child[1], node);  in trie_update_elem()
428 	/* Finally, assign the intermediate node to the determined slot */  in trie_update_elem()
453 	struct lpm_trie_node *node, *parent;  in trie_delete_elem()  local
465 	 * track of the path we traverse.  We will need to know the node  in trie_delete_elem()
466 	 * we wish to delete, and the slot that points to the node we want  in trie_delete_elem()
473 	while ((node = rcu_dereference_protected(  in trie_delete_elem()
475 		matchlen = longest_prefix_match(trie, node, key);  in trie_delete_elem()
477 		if (node->prefixlen != matchlen ||  in trie_delete_elem()
478 		    node->prefixlen == key->prefixlen)  in trie_delete_elem()
481 		parent = node;  in trie_delete_elem()
483 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_delete_elem()
484 		trim = &node->child[next_bit];  in trie_delete_elem()
487 	if (!node || node->prefixlen != key->prefixlen ||  in trie_delete_elem()
488 	    node->prefixlen != matchlen ||  in trie_delete_elem()
489 	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {  in trie_delete_elem()
496 	/* If the node we are removing has two children, simply mark it  in trie_delete_elem()
499 	if (rcu_access_pointer(node->child[0]) &&  in trie_delete_elem()
500 	    rcu_access_pointer(node->child[1])) {  in trie_delete_elem()
501 		node->flags |= LPM_TREE_NODE_FLAG_IM;  in trie_delete_elem()
505 	/* If the parent of the node we are about to delete is an intermediate  in trie_delete_elem()
506 	 * node, and the deleted node doesn't have any children, we can delete  in trie_delete_elem()
513 	    !node->child[0] && !node->child[1]) {  in trie_delete_elem()
514 		if (node == rcu_access_pointer(parent->child[0]))  in trie_delete_elem()
521 		free_node = node;  in trie_delete_elem()
525 	/* The node we are removing has either zero or one child. If there  in trie_delete_elem()
526 	 * is a child, move it into the removed node's slot then delete  in trie_delete_elem()
527 	 * the node.  Otherwise just clear the slot and delete the node.  in trie_delete_elem()
529 	if (node->child[0])  in trie_delete_elem()
530 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));  in trie_delete_elem()
531 	else if (node->child[1])  in trie_delete_elem()
532 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));  in trie_delete_elem()
535 	free_node = node;  in trie_delete_elem()
593 	struct lpm_trie_node *node;  in trie_free()  local
595 	/* Always start at the root and walk down to a node that has no  in trie_free()
596 	 * children. Then free that node, nullify its reference in the parent  in trie_free()
604 			node = rcu_dereference_protected(*slot, 1);  in trie_free()
605 			if (!node)  in trie_free()
608 			if (rcu_access_pointer(node->child[0])) {  in trie_free()
609 				slot = &node->child[0];  in trie_free()
613 			if (rcu_access_pointer(node->child[1])) {  in trie_free()
614 				slot = &node->child[1];  in trie_free()
618 			kfree(node);  in trie_free()
630 	struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;  in trie_get_next_key()  local
638 	/* The get_next_key follows postorder. For the 4 node example in  in trie_get_next_key()
654 	/* For invalid key, find the leftmost node in the trie */  in trie_get_next_key()
664 	/* Try to find the exact node for the given key */  in trie_get_next_key()
665 	for (node = search_root; node;) {  in trie_get_next_key()
666 		node_stack[++stack_ptr] = node;  in trie_get_next_key()
667 		matchlen = longest_prefix_match(trie, node, key);  in trie_get_next_key()
668 		if (node->prefixlen != matchlen ||  in trie_get_next_key()
669 		    node->prefixlen == key->prefixlen)  in trie_get_next_key()
672 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_get_next_key()
673 		node = rcu_dereference(node->child[next_bit]);  in trie_get_next_key()
675 	if (!node || node->prefixlen != key->prefixlen ||  in trie_get_next_key()
676 	    (node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_get_next_key()
679 	/* The node with the exactly-matching key has been found,  in trie_get_next_key()
680 	 * find the first node in postorder after the matched node.  in trie_get_next_key()
682 	node = node_stack[stack_ptr];  in trie_get_next_key()
685 		if (rcu_dereference(parent->child[0]) == node) {  in trie_get_next_key()
695 		node = parent;  in trie_get_next_key()
704 	/* Find the leftmost non-intermediate node, all intermediate nodes  in trie_get_next_key()
707 	for (node = search_root; node;) {  in trie_get_next_key()
708 		if (node->flags & LPM_TREE_NODE_FLAG_IM) {  in trie_get_next_key()
709 			node = rcu_dereference(node->child[0]);  in trie_get_next_key()
711 			next_node = node;  in trie_get_next_key()
712 			node = rcu_dereference(node->child[0]);  in trie_get_next_key()
713 			if (!node)  in trie_get_next_key()
714 				node = rcu_dereference(next_node->child[1]);  in trie_get_next_key()