Lines Matching refs:trie
40 /* This trie implements a longest prefix match algorithm that can be used to
52 * For instance, let's start with a trie that was created with a prefix length
58 * As the trie is empty initially, the new node (1) will be places as root
140 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
142 * A fully populated trie would have a height of 32 nodes, as the trie was
146 * is a child that can be used to become more specific, the trie is traversed
158 * @trie: The trie to get internal sizes from
164 static size_t longest_prefix_match(const struct lpm_trie *trie,
179 if (trie->data_size >= 8) {
192 while (trie->data_size >= i + 4) {
204 if (trie->data_size >= i + 2) {
216 if (trie->data_size >= i + 1) {
229 struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
233 if (key->prefixlen > trie->max_prefixlen)
236 /* Start walking the trie from the root node ... */
238 for (node = rcu_dereference(trie->root); node;) {
243 * If it's the maximum possible prefix for this trie, we have
246 matchlen = longest_prefix_match(trie, node, key);
247 if (matchlen == trie->max_prefixlen) {
276 return found->data + trie->data_size;
279 static struct lpm_trie_node *lpm_trie_node_alloc(const struct lpm_trie *trie,
283 size_t size = sizeof(struct lpm_trie_node) + trie->data_size;
286 size += trie->map.value_size;
289 trie->map.numa_node);
296 memcpy(node->data + trie->data_size, value,
297 trie->map.value_size);
306 struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
318 if (key->prefixlen > trie->max_prefixlen)
321 spin_lock_irqsave(&trie->lock, irq_flags);
325 if (trie->n_entries == trie->map.max_entries) {
330 new_node = lpm_trie_node_alloc(trie, value);
336 trie->n_entries++;
341 memcpy(new_node->data, key->data, trie->data_size);
348 slot = &trie->root;
351 lockdep_is_held(&trie->lock)))) {
352 matchlen = longest_prefix_match(trie, node, key);
356 node->prefixlen == trie->max_prefixlen)
379 trie->n_entries--;
397 im_node = lpm_trie_node_alloc(trie, NULL);
405 memcpy(im_node->data, node->data, trie->data_size);
422 trie->n_entries--;
428 spin_unlock_irqrestore(&trie->lock, irq_flags);
436 struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
445 if (key->prefixlen > trie->max_prefixlen)
448 spin_lock_irqsave(&trie->lock, irq_flags);
456 trim = &trie->root;
460 *trim, lockdep_is_held(&trie->lock)))) {
461 matchlen = longest_prefix_match(trie, node, key);
480 trie->n_entries--;
524 spin_unlock_irqrestore(&trie->lock, irq_flags);
545 struct lpm_trie *trie;
546 u64 cost = sizeof(*trie), cost_per_node;
563 trie = kzalloc(sizeof(*trie), GFP_USER | __GFP_NOWARN);
564 if (!trie)
568 bpf_map_init_from_attr(&trie->map, attr);
569 trie->data_size = attr->key_size -
571 trie->max_prefixlen = trie->data_size * 8;
574 attr->value_size + trie->data_size;
577 ret = bpf_map_charge_init(&trie->map.memory, cost);
581 spin_lock_init(&trie->lock);
583 return &trie->map;
585 kfree(trie);
591 struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
601 slot = &trie->root;
625 kfree(trie);
631 struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
649 /* Empty trie */
650 search_root = rcu_dereference(trie->root);
654 /* For invalid key, find the leftmost node in the trie */
655 if (!key || key->prefixlen > trie->max_prefixlen)
658 node_stack = kmalloc_array(trie->max_prefixlen,
667 matchlen = longest_prefix_match(trie, node, key);
720 next_node->data, trie->data_size);