Lines Matching refs:trie
165 static size_t longest_prefix_match(const struct lpm_trie *trie, in longest_prefix_match() argument
180 if (trie->data_size >= 8) { in longest_prefix_match()
193 while (trie->data_size >= i + 4) { in longest_prefix_match()
205 if (trie->data_size >= i + 2) { in longest_prefix_match()
217 if (trie->data_size >= i + 1) { in longest_prefix_match()
230 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_lookup_elem() local
236 for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held()); in trie_lookup_elem()
245 matchlen = longest_prefix_match(trie, node, key); in trie_lookup_elem()
246 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
276 return found->data + trie->data_size; in trie_lookup_elem()
279 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie, in lpm_trie_node_alloc() argument
283 size_t size = sizeof(struct lpm_trie_node) + trie->data_size; in lpm_trie_node_alloc()
286 size += trie->map.value_size; in lpm_trie_node_alloc()
288 node = bpf_map_kmalloc_node(&trie->map, size, GFP_NOWAIT | __GFP_NOWARN, in lpm_trie_node_alloc()
289 trie->map.numa_node); in lpm_trie_node_alloc()
296 memcpy(node->data + trie->data_size, value, in lpm_trie_node_alloc()
297 trie->map.value_size); in lpm_trie_node_alloc()
306 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_update_elem() local
318 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
321 spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
325 if (trie->n_entries == trie->map.max_entries) { in trie_update_elem()
330 new_node = lpm_trie_node_alloc(trie, value); in trie_update_elem()
336 trie->n_entries++; in trie_update_elem()
341 memcpy(new_node->data, key->data, trie->data_size); in trie_update_elem()
348 slot = &trie->root; in trie_update_elem()
351 lockdep_is_held(&trie->lock)))) { in trie_update_elem()
352 matchlen = longest_prefix_match(trie, node, key); in trie_update_elem()
356 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
379 trie->n_entries--; in trie_update_elem()
397 im_node = lpm_trie_node_alloc(trie, NULL); in trie_update_elem()
405 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
422 trie->n_entries--; in trie_update_elem()
428 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
436 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_delete_elem() local
445 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
448 spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
456 trim = &trie->root; in trie_delete_elem()
460 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
461 matchlen = longest_prefix_match(trie, node, key); in trie_delete_elem()
480 trie->n_entries--; in trie_delete_elem()
524 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
545 struct lpm_trie *trie; in trie_alloc() local
561 trie = bpf_map_area_alloc(sizeof(*trie), NUMA_NO_NODE); in trie_alloc()
562 if (!trie) in trie_alloc()
566 bpf_map_init_from_attr(&trie->map, attr); in trie_alloc()
567 trie->data_size = attr->key_size - in trie_alloc()
569 trie->max_prefixlen = trie->data_size * 8; in trie_alloc()
571 spin_lock_init(&trie->lock); in trie_alloc()
573 return &trie->map; in trie_alloc()
578 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_free() local
588 slot = &trie->root; in trie_free()
612 bpf_map_area_free(trie); in trie_free()
618 struct lpm_trie *trie = container_of(map, struct lpm_trie, map); in trie_get_next_key() local
637 search_root = rcu_dereference(trie->root); in trie_get_next_key()
642 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
645 node_stack = kmalloc_array(trie->max_prefixlen, in trie_get_next_key()
654 matchlen = longest_prefix_match(trie, node, key); in trie_get_next_key()
707 next_node->data, trie->data_size); in trie_get_next_key()