Lines Matching refs:trie
167 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
174 for (i = 0; i < trie->data_size; i++) { in longest_prefix_match()
193 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); 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()
208 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
237 return found->data + trie->data_size; in trie_lookup_elem()
240 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie, in lpm_trie_node_alloc() argument
244 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; in lpm_trie_node_alloc()
247 size += trie->map.value_size; in lpm_trie_node_alloc()
250 trie->map.numa_node); in lpm_trie_node_alloc()
257 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
258 trie->map.value_size); in lpm_trie_node_alloc()
267 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_update_elem() local
279 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
282 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
286 if (trie->n_entries == trie->map.max_entries) { in trie_update_elem()
291 new_node = lpm_trie_node_alloc(trie, value); in trie_update_elem()
297 trie->n_entries++; in trie_update_elem()
302 memcpy(new_node->data, key->data, trie->data_size); in trie_update_elem()
309 slot = &trie->root; in trie_update_elem()
312 lockdep_is_held(&trie->lock)))) { in trie_update_elem()
313 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
317 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
340 trie->n_entries--; in trie_update_elem()
358 im_node = lpm_trie_node_alloc(trie, NULL); in trie_update_elem()
366 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
383 trie->n_entries--; in trie_update_elem()
389 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
397 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_delete_elem() local
406 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
409 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
417 trim = &trie->root; in trie_delete_elem()
421 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
422 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
440 trie->n_entries--; in trie_delete_elem()
484 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
505 struct lpm_trie *trie; in trie_alloc() local
506 u64 cost = sizeof(*trie), cost_per_node; in trie_alloc()
522 trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN); in trie_alloc()
523 if (!trie) in trie_alloc()
527 bpf_map_init_from_attr(&trie->map, attr); in trie_alloc()
528 trie->data_size = attr->key_size - in trie_alloc()
530 trie->max_prefixlen = trie->data_size * 8; in trie_alloc()
533 attr->value_size + trie->data_size; in trie_alloc()
540 trie->map.pages = round_up(cost, PAGE_SIZE) >> PAGE_SHIFT; in trie_alloc()
542 ret = bpf_map_precharge_memlock(trie->map.pages); in trie_alloc()
546 raw_spin_lock_init(&trie->lock); in trie_alloc()
548 return &trie->map; in trie_alloc()
550 kfree(trie); in trie_alloc()
556 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_free() local
571 slot = &trie->root; in trie_free()
595 kfree(trie); in trie_free()
601 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_get_next_key() local
620 search_root = rcu_dereference(trie->root); in trie_get_next_key()
625 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
628 node_stack = kmalloc_array(trie->max_prefixlen, in trie_get_next_key()
637 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
685 next_node->data, trie->data_size); in trie_get_next_key()