168 size_t __longest_prefix_match(const struct lpm_trie *trie,  in __longest_prefix_match()  argument
183 	if (trie->data_size >= 8) {  in __longest_prefix_match()
196 	while (trie->data_size >= i + 4) {  in __longest_prefix_match()
208 	if (trie->data_size >= i + 2) {  in __longest_prefix_match()
220 	if (trie->data_size >= i + 1) {  in __longest_prefix_match()
230 static size_t longest_prefix_match(const struct lpm_trie *trie,  in longest_prefix_match()  argument
234 	return __longest_prefix_match(trie, node, key);  in longest_prefix_match()
240 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_lookup_elem()  local
244 	if (key->prefixlen > trie->max_prefixlen)  in trie_lookup_elem()
249 	for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());  in trie_lookup_elem()
258 		matchlen = __longest_prefix_match(trie, node, key);  in trie_lookup_elem()
259 		if (matchlen == trie->max_prefixlen) {  in trie_lookup_elem()
289 	return found->data + trie->data_size;  in trie_lookup_elem()
292 static struct lpm_trie_node *lpm_trie_node_alloc(struct lpm_trie *trie,  in lpm_trie_node_alloc()  argument
297 	node = bpf_mem_cache_alloc(&trie->ma);  in lpm_trie_node_alloc()
305 		memcpy(node->data + trie->data_size, value,  in lpm_trie_node_alloc()
306 		       trie->map.value_size);  in lpm_trie_node_alloc()
311 static int trie_check_add_elem(struct lpm_trie *trie, u64 flags)  in trie_check_add_elem()  argument
315 	if (trie->n_entries == trie->map.max_entries)  in trie_check_add_elem()
317 	trie->n_entries++;  in trie_check_add_elem()
325 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_update_elem()  local
338 	if (key->prefixlen > trie->max_prefixlen)  in trie_update_elem()
342 	new_node = lpm_trie_node_alloc(trie, value);  in trie_update_elem()
346 	ret = raw_res_spin_lock_irqsave(&trie->lock, irq_flags);  in trie_update_elem()
353 	memcpy(new_node->data, key->data, trie->data_size);  in trie_update_elem()
360 	slot = &trie->root;  in trie_update_elem()
363 		matchlen = longest_prefix_match(trie, node, key);  in trie_update_elem()
377 		ret = trie_check_add_elem(trie, flags);  in trie_update_elem()
395 			ret = trie_check_add_elem(trie, flags);  in trie_update_elem()
409 	ret = trie_check_add_elem(trie, flags);  in trie_update_elem()
423 	im_node = lpm_trie_node_alloc(trie, NULL);  in trie_update_elem()
425 		trie->n_entries--;  in trie_update_elem()
432 	memcpy(im_node->data, node->data, trie->data_size);  in trie_update_elem()
447 	raw_res_spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_update_elem()
450 		bpf_mem_cache_free(&trie->ma, new_node);  in trie_update_elem()
451 	bpf_mem_cache_free_rcu(&trie->ma, free_node);  in trie_update_elem()
459 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_delete_elem()  local
469 	if (key->prefixlen > trie->max_prefixlen)  in trie_delete_elem()
472 	ret = raw_res_spin_lock_irqsave(&trie->lock, irq_flags);  in trie_delete_elem()
482 	trim = &trie->root;  in trie_delete_elem()
486 		matchlen = longest_prefix_match(trie, node, key);  in trie_delete_elem()
505 	trie->n_entries--;  in trie_delete_elem()
549 	raw_res_spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_delete_elem()
551 	bpf_mem_cache_free_rcu(&trie->ma, free_parent);  in trie_delete_elem()
552 	bpf_mem_cache_free_rcu(&trie->ma, free_node);  in trie_delete_elem()
573 	struct lpm_trie *trie;  in trie_alloc()  local
588 	trie = bpf_map_area_alloc(sizeof(*trie), NUMA_NO_NODE);  in trie_alloc()
589 	if (!trie)  in trie_alloc()
593 	bpf_map_init_from_attr(&trie->map, attr);  in trie_alloc()
594 	trie->data_size = attr->key_size -  in trie_alloc()
596 	trie->max_prefixlen = trie->data_size * 8;  in trie_alloc()
598 	raw_res_spin_lock_init(&trie->lock);  in trie_alloc()
601 	leaf_size = sizeof(struct lpm_trie_node) + trie->data_size +  in trie_alloc()
602 		    trie->map.value_size;  in trie_alloc()
603 	err = bpf_mem_alloc_init(&trie->ma, leaf_size, false);  in trie_alloc()
606 	return &trie->map;  in trie_alloc()
609 	bpf_map_area_free(trie);  in trie_alloc()
615 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_free()  local
625 		slot = &trie->root;  in trie_free()
652 	bpf_mem_alloc_destroy(&trie->ma);  in trie_free()
653 	bpf_map_area_free(trie);  in trie_free()
659 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_get_next_key()  local
678 	search_root = rcu_dereference(trie->root);  in trie_get_next_key()
683 	if (!key || key->prefixlen > trie->max_prefixlen)  in trie_get_next_key()
687 				  trie->max_prefixlen + 1,  in trie_get_next_key()
695 		matchlen = longest_prefix_match(trie, node, key);  in trie_get_next_key()
748 	       next_node->data, trie->data_size);  in trie_get_next_key()
766 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_mem_usage()  local
769 	elem_size = sizeof(struct lpm_trie_node) + trie->data_size +  in trie_mem_usage()
770 			    trie->map.value_size;  in trie_mem_usage()
771 	return elem_size * READ_ONCE(trie->n_entries);  in trie_mem_usage()