Lines Matching refs:trie
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(trie->root); node;) { in trie_lookup_elem()
243 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
244 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
273 return found->data + trie->data_size; in trie_lookup_elem()
276 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie, in lpm_trie_node_alloc() argument
280 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; in lpm_trie_node_alloc()
283 size += trie->map.value_size; in lpm_trie_node_alloc()
286 trie->map.numa_node); in lpm_trie_node_alloc()
293 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
294 trie->map.value_size); in lpm_trie_node_alloc()
303 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_update_elem() local
315 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
318 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
322 if (trie->n_entries == trie->map.max_entries) { in trie_update_elem()
327 new_node = lpm_trie_node_alloc(trie, value); in trie_update_elem()
333 trie->n_entries++; in trie_update_elem()
338 memcpy(new_node->data, key->data, trie->data_size); in trie_update_elem()
345 slot = &trie->root; in trie_update_elem()
348 lockdep_is_held(&trie->lock)))) { in trie_update_elem()
349 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
353 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
376 trie->n_entries--; in trie_update_elem()
394 im_node = lpm_trie_node_alloc(trie, NULL); in trie_update_elem()
402 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
419 trie->n_entries--; in trie_update_elem()
425 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
433 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_delete_elem() local
442 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
445 raw_spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
453 trim = &trie->root; in trie_delete_elem()
457 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
458 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
477 trie->n_entries--; in trie_delete_elem()
521 raw_spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
542 struct lpm_trie *trie; in trie_alloc() local
543 u64 cost = sizeof(*trie), cost_per_node; in trie_alloc()
560 trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN); 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()
571 attr->value_size + trie->data_size; in trie_alloc()
574 ret = bpf_map_charge_init(&trie->map.memory, cost); in trie_alloc()
578 raw_spin_lock_init(&trie->lock); in trie_alloc()
580 return &trie->map; in trie_alloc()
582 kfree(trie); in trie_alloc()
588 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_free() local
603 slot = &trie->root; in trie_free()
627 kfree(trie); in trie_free()
633 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_get_next_key() local
652 search_root = rcu_dereference(trie->root); in trie_get_next_key()
657 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
660 node_stack = kmalloc_array(trie->max_prefixlen, in trie_get_next_key()
669 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
722 next_node->data, trie->data_size); in trie_get_next_key()