164 static size_t longest_prefix_match(const struct lpm_trie *trie,  in longest_prefix_match()  argument
179 	if (trie->data_size >= 8) {  in longest_prefix_match()
192 	while (trie->data_size >= i + 4) {  in longest_prefix_match()
204 	if (trie->data_size >= i + 2) {  in longest_prefix_match()
216 	if (trie->data_size >= i + 1) {  in longest_prefix_match()
229 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_lookup_elem()  local
235 	for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());  in trie_lookup_elem()
244 		matchlen = longest_prefix_match(trie, node, key);  in trie_lookup_elem()
245 		if (matchlen == trie->max_prefixlen) {  in trie_lookup_elem()
275 	return found->data + trie->data_size;  in trie_lookup_elem()
278 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,  in lpm_trie_node_alloc()  argument
282 	size_t size = sizeof(struct lpm_trie_node) + trie->data_size;  in lpm_trie_node_alloc()
285 		size += trie->map.value_size;  in lpm_trie_node_alloc()
287 	node = bpf_map_kmalloc_node(&trie->map, size, GFP_ATOMIC | __GFP_NOWARN,  in lpm_trie_node_alloc()
288 				    trie->map.numa_node);  in lpm_trie_node_alloc()
295 		memcpy(node->data + trie->data_size, value,  in lpm_trie_node_alloc()
296 		       trie->map.value_size);  in lpm_trie_node_alloc()
305 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_update_elem()  local
317 	if (key->prefixlen > trie->max_prefixlen)  in trie_update_elem()
320 	spin_lock_irqsave(&trie->lock, irq_flags);  in trie_update_elem()
324 	if (trie->n_entries == trie->map.max_entries) {  in trie_update_elem()
329 	new_node = lpm_trie_node_alloc(trie, value);  in trie_update_elem()
335 	trie->n_entries++;  in trie_update_elem()
340 	memcpy(new_node->data, key->data, trie->data_size);  in trie_update_elem()
347 	slot = &trie->root;  in trie_update_elem()
350 					lockdep_is_held(&trie->lock)))) {  in trie_update_elem()
351 		matchlen = longest_prefix_match(trie, node, key);  in trie_update_elem()
355 		    node->prefixlen == trie->max_prefixlen)  in trie_update_elem()
378 			trie->n_entries--;  in trie_update_elem()
396 	im_node = lpm_trie_node_alloc(trie, NULL);  in trie_update_elem()
404 	memcpy(im_node->data, node->data, trie->data_size);  in trie_update_elem()
421 			trie->n_entries--;  in trie_update_elem()
427 	spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_update_elem()
435 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_delete_elem()  local
444 	if (key->prefixlen > trie->max_prefixlen)  in trie_delete_elem()
447 	spin_lock_irqsave(&trie->lock, irq_flags);  in trie_delete_elem()
455 	trim = &trie->root;  in trie_delete_elem()
459 		       *trim, lockdep_is_held(&trie->lock)))) {  in trie_delete_elem()
460 		matchlen = longest_prefix_match(trie, node, key);  in trie_delete_elem()
479 	trie->n_entries--;  in trie_delete_elem()
523 	spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_delete_elem()
544 	struct lpm_trie *trie;  in trie_alloc()  local
560 	trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN | __GFP_ACCOUNT);  in trie_alloc()
561 	if (!trie)  in trie_alloc()
565 	bpf_map_init_from_attr(&trie->map, attr);  in trie_alloc()
566 	trie->data_size = attr->key_size -  in trie_alloc()
568 	trie->max_prefixlen = trie->data_size * 8;  in trie_alloc()
570 	spin_lock_init(&trie->lock);  in trie_alloc()
572 	return &trie->map;  in trie_alloc()
577 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_free()  local
587 		slot = &trie->root;  in trie_free()
611 	kfree(trie);  in trie_free()
617 	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);  in trie_get_next_key()  local
636 	search_root = rcu_dereference(trie->root);  in trie_get_next_key()
641 	if (!key || key->prefixlen > trie->max_prefixlen)  in trie_get_next_key()
644 	node_stack = kmalloc_array(trie->max_prefixlen,  in trie_get_next_key()
653 		matchlen = longest_prefix_match(trie, node, key);  in trie_get_next_key()
706 	       next_node->data, trie->data_size);  in trie_get_next_key()