168 				   const struct lpm_trie_node *node,  in longest_prefix_match()  argument
177 		b = 8 - fls(node->data[i] ^ key->data[i]);  in longest_prefix_match()
180 		if (prefixlen >= node->prefixlen || prefixlen >= key->prefixlen)  in longest_prefix_match()
181 			return min(node->prefixlen, key->prefixlen);  in longest_prefix_match()
194 	struct lpm_trie_node *node, *found = NULL;  in trie_lookup_elem()  local
199 	for (node = rcu_dereference(trie->root); node;) {  in trie_lookup_elem()
207 		matchlen = longest_prefix_match(trie, node, key);  in trie_lookup_elem()
209 			found = node;  in trie_lookup_elem()
217 		if (matchlen < node->prefixlen)  in trie_lookup_elem()
223 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_lookup_elem()
224 			found = node;  in trie_lookup_elem()
230 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_lookup_elem()
231 		node = rcu_dereference(node->child[next_bit]);  in trie_lookup_elem()
243 	struct lpm_trie_node *node;  in lpm_trie_node_alloc()  local
249 	node = kmalloc_node(size, GFP_ATOMIC | __GFP_NOWARN,  in lpm_trie_node_alloc()
251 	if (!node)  in lpm_trie_node_alloc()
254 	node->flags = 0;  in lpm_trie_node_alloc()
257 		memcpy(node->data + trie->data_size, value,  in lpm_trie_node_alloc()
260 	return node;  in lpm_trie_node_alloc()
268 	struct lpm_trie_node *node, *im_node = NULL, *new_node = NULL;  in trie_update_elem()  local
311 	while ((node = rcu_dereference_protected(*slot,  in trie_update_elem()
313 		matchlen = longest_prefix_match(trie, node, key);  in trie_update_elem()
315 		if (node->prefixlen != matchlen ||  in trie_update_elem()
316 		    node->prefixlen == key->prefixlen ||  in trie_update_elem()
317 		    node->prefixlen == trie->max_prefixlen)  in trie_update_elem()
320 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_update_elem()
321 		slot = &node->child[next_bit];  in trie_update_elem()
327 	if (!node) {  in trie_update_elem()
335 	if (node->prefixlen == matchlen) {  in trie_update_elem()
336 		new_node->child[0] = node->child[0];  in trie_update_elem()
337 		new_node->child[1] = node->child[1];  in trie_update_elem()
339 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_update_elem()
343 		kfree_rcu(node, rcu);  in trie_update_elem()
352 		next_bit = extract_bit(node->data, matchlen);  in trie_update_elem()
353 		rcu_assign_pointer(new_node->child[next_bit], node);  in trie_update_elem()
366 	memcpy(im_node->data, node->data, trie->data_size);  in trie_update_elem()
370 		rcu_assign_pointer(im_node->child[0], node);  in trie_update_elem()
374 		rcu_assign_pointer(im_node->child[1], node);  in trie_update_elem()
400 	struct lpm_trie_node *node, *parent;  in trie_delete_elem()  local
420 	while ((node = rcu_dereference_protected(  in trie_delete_elem()
422 		matchlen = longest_prefix_match(trie, node, key);  in trie_delete_elem()
424 		if (node->prefixlen != matchlen ||  in trie_delete_elem()
425 		    node->prefixlen == key->prefixlen)  in trie_delete_elem()
428 		parent = node;  in trie_delete_elem()
430 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_delete_elem()
431 		trim = &node->child[next_bit];  in trie_delete_elem()
434 	if (!node || node->prefixlen != key->prefixlen ||  in trie_delete_elem()
435 	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {  in trie_delete_elem()
445 	if (rcu_access_pointer(node->child[0]) &&  in trie_delete_elem()
446 	    rcu_access_pointer(node->child[1])) {  in trie_delete_elem()
447 		node->flags |= LPM_TREE_NODE_FLAG_IM;  in trie_delete_elem()
459 	    !node->child[0] && !node->child[1]) {  in trie_delete_elem()
460 		if (node == rcu_access_pointer(parent->child[0]))  in trie_delete_elem()
467 		kfree_rcu(node, rcu);  in trie_delete_elem()
475 	if (node->child[0])  in trie_delete_elem()
476 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));  in trie_delete_elem()
477 	else if (node->child[1])  in trie_delete_elem()
478 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));  in trie_delete_elem()
481 	kfree_rcu(node, rcu);  in trie_delete_elem()
558 	struct lpm_trie_node *node;  in trie_free()  local
574 			node = rcu_dereference_protected(*slot, 1);  in trie_free()
575 			if (!node)  in trie_free()
578 			if (rcu_access_pointer(node->child[0])) {  in trie_free()
579 				slot = &node->child[0];  in trie_free()
583 			if (rcu_access_pointer(node->child[1])) {  in trie_free()
584 				slot = &node->child[1];  in trie_free()
588 			kfree(node);  in trie_free()
600 	struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;  in trie_get_next_key()  local
635 	for (node = search_root; node;) {  in trie_get_next_key()
636 		node_stack[++stack_ptr] = node;  in trie_get_next_key()
637 		matchlen = longest_prefix_match(trie, node, key);  in trie_get_next_key()
638 		if (node->prefixlen != matchlen ||  in trie_get_next_key()
639 		    node->prefixlen == key->prefixlen)  in trie_get_next_key()
642 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_get_next_key()
643 		node = rcu_dereference(node->child[next_bit]);  in trie_get_next_key()
645 	if (!node || node->prefixlen != key->prefixlen ||  in trie_get_next_key()
646 	    (node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_get_next_key()
652 	node = node_stack[stack_ptr];  in trie_get_next_key()
655 		if (rcu_dereference(parent->child[0]) == node) {  in trie_get_next_key()
665 		node = parent;  in trie_get_next_key()
677 	for (node = search_root; node;) {  in trie_get_next_key()
678 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_get_next_key()
679 			next_node = node;  in trie_get_next_key()
680 		node = rcu_dereference(node->child[0]);  in trie_get_next_key()