Lines Matching +full:- +full:- +full:trim +full:- +full:-
1 // SPDX-License-Identifier: GPL-2.0-only
55 * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will
56 * stick to IP-address notation for readability though.
62 * +----------------+
67 * +----------------+
75 * +----------------+
80 * +----------------+
82 * +----------------+
87 * +----------------+
93 * +----------------+
98 * +----------------+
100 * +----------------+ +------------------+
105 * +----------------+ +------------------+
116 * +----------------+
121 * +----------------+
123 * +----------------+ +------------------+
126 * | value: --- | | value: 3 |
128 * +----------------+ +------------------+
130 * +----------------+ +----------------+
135 * +----------------+ +----------------+
140 * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
147 * downwards. The last node in the traversal that is a non-intermediate one is
153 return !!(data[index / 8] & (1 << (7 - (index % 8)))); in extract_bit()
157 * longest_prefix_match() - determine the longest prefix
168 u32 limit = min(node->prefixlen, key->prefixlen); in longest_prefix_match()
179 if (trie->data_size >= 8) { in longest_prefix_match()
180 u64 diff = be64_to_cpu(*(__be64 *)node->data ^ in longest_prefix_match()
181 *(__be64 *)key->data); in longest_prefix_match()
183 prefixlen = 64 - fls64(diff); in longest_prefix_match()
192 while (trie->data_size >= i + 4) { in longest_prefix_match()
193 u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^ in longest_prefix_match()
194 *(__be32 *)&key->data[i]); in longest_prefix_match()
196 prefixlen += 32 - fls(diff); in longest_prefix_match()
204 if (trie->data_size >= i + 2) { in longest_prefix_match()
205 u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^ in longest_prefix_match()
206 *(__be16 *)&key->data[i]); in longest_prefix_match()
208 prefixlen += 16 - fls(diff); in longest_prefix_match()
216 if (trie->data_size >= i + 1) { in longest_prefix_match()
217 prefixlen += 8 - fls(node->data[i] ^ key->data[i]); in longest_prefix_match()
235 for (node = rcu_dereference(trie->root); node;) { in trie_lookup_elem()
244 if (matchlen == trie->max_prefixlen) { in trie_lookup_elem()
253 if (matchlen < node->prefixlen) in trie_lookup_elem()
259 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_lookup_elem()
266 next_bit = extract_bit(key->data, node->prefixlen); in trie_lookup_elem()
267 node = rcu_dereference(node->child[next_bit]); in trie_lookup_elem()
273 return found->data + trie->data_size; in trie_lookup_elem()
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()
290 node->flags = 0; 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()
313 return -EINVAL; in trie_update_elem()
315 if (key->prefixlen > trie->max_prefixlen) in trie_update_elem()
316 return -EINVAL; in trie_update_elem()
318 spin_lock_irqsave(&trie->lock, irq_flags); in trie_update_elem()
322 if (trie->n_entries == trie->map.max_entries) { in trie_update_elem()
323 ret = -ENOSPC; in trie_update_elem()
329 ret = -ENOMEM; in trie_update_elem()
333 trie->n_entries++; in trie_update_elem()
335 new_node->prefixlen = key->prefixlen; in trie_update_elem()
336 RCU_INIT_POINTER(new_node->child[0], NULL); in trie_update_elem()
337 RCU_INIT_POINTER(new_node->child[1], NULL); 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()
351 if (node->prefixlen != matchlen || in trie_update_elem()
352 node->prefixlen == key->prefixlen || in trie_update_elem()
353 node->prefixlen == trie->max_prefixlen) in trie_update_elem()
356 next_bit = extract_bit(key->data, node->prefixlen); in trie_update_elem()
357 slot = &node->child[next_bit]; in trie_update_elem()
371 if (node->prefixlen == matchlen) { in trie_update_elem()
372 new_node->child[0] = node->child[0]; in trie_update_elem()
373 new_node->child[1] = node->child[1]; in trie_update_elem()
375 if (!(node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_update_elem()
376 trie->n_entries--; in trie_update_elem()
387 if (matchlen == key->prefixlen) { in trie_update_elem()
388 next_bit = extract_bit(node->data, matchlen); in trie_update_elem()
389 rcu_assign_pointer(new_node->child[next_bit], node); in trie_update_elem()
396 ret = -ENOMEM; in trie_update_elem()
400 im_node->prefixlen = matchlen; in trie_update_elem()
401 im_node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_update_elem()
402 memcpy(im_node->data, node->data, trie->data_size); in trie_update_elem()
405 if (extract_bit(key->data, matchlen)) { in trie_update_elem()
406 rcu_assign_pointer(im_node->child[0], node); in trie_update_elem()
407 rcu_assign_pointer(im_node->child[1], new_node); in trie_update_elem()
409 rcu_assign_pointer(im_node->child[0], new_node); in trie_update_elem()
410 rcu_assign_pointer(im_node->child[1], node); in trie_update_elem()
419 trie->n_entries--; in trie_update_elem()
425 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_update_elem()
435 struct lpm_trie_node __rcu **trim, **trim2; in trie_delete_elem() local
442 if (key->prefixlen > trie->max_prefixlen) in trie_delete_elem()
443 return -EINVAL; in trie_delete_elem()
445 spin_lock_irqsave(&trie->lock, irq_flags); in trie_delete_elem()
453 trim = &trie->root; in trie_delete_elem()
454 trim2 = trim; in trie_delete_elem()
457 *trim, lockdep_is_held(&trie->lock)))) { in trie_delete_elem()
460 if (node->prefixlen != matchlen || in trie_delete_elem()
461 node->prefixlen == key->prefixlen) in trie_delete_elem()
465 trim2 = trim; in trie_delete_elem()
466 next_bit = extract_bit(key->data, node->prefixlen); in trie_delete_elem()
467 trim = &node->child[next_bit]; in trie_delete_elem()
470 if (!node || node->prefixlen != key->prefixlen || in trie_delete_elem()
471 node->prefixlen != matchlen || in trie_delete_elem()
472 (node->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_delete_elem()
473 ret = -ENOENT; in trie_delete_elem()
477 trie->n_entries--; in trie_delete_elem()
482 if (rcu_access_pointer(node->child[0]) && in trie_delete_elem()
483 rcu_access_pointer(node->child[1])) { in trie_delete_elem()
484 node->flags |= LPM_TREE_NODE_FLAG_IM; in trie_delete_elem()
495 if (parent && (parent->flags & LPM_TREE_NODE_FLAG_IM) && in trie_delete_elem()
496 !node->child[0] && !node->child[1]) { in trie_delete_elem()
497 if (node == rcu_access_pointer(parent->child[0])) in trie_delete_elem()
499 *trim2, rcu_access_pointer(parent->child[1])); in trie_delete_elem()
502 *trim2, rcu_access_pointer(parent->child[0])); in trie_delete_elem()
512 if (node->child[0]) in trie_delete_elem()
513 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0])); in trie_delete_elem()
514 else if (node->child[1]) in trie_delete_elem()
515 rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1])); in trie_delete_elem()
517 RCU_INIT_POINTER(*trim, NULL); in trie_delete_elem()
521 spin_unlock_irqrestore(&trie->lock, irq_flags); in trie_delete_elem()
529 #define LPM_VAL_SIZE_MAX (KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \
547 return ERR_PTR(-EPERM); in trie_alloc()
550 if (attr->max_entries == 0 || in trie_alloc()
551 !(attr->map_flags & BPF_F_NO_PREALLOC) || in trie_alloc()
552 attr->map_flags & ~LPM_CREATE_FLAG_MASK || in trie_alloc()
553 !bpf_map_flags_access_ok(attr->map_flags) || in trie_alloc()
554 attr->key_size < LPM_KEY_SIZE_MIN || in trie_alloc()
555 attr->key_size > LPM_KEY_SIZE_MAX || in trie_alloc()
556 attr->value_size < LPM_VAL_SIZE_MIN || in trie_alloc()
557 attr->value_size > LPM_VAL_SIZE_MAX) in trie_alloc()
558 return ERR_PTR(-EINVAL); in trie_alloc()
562 return ERR_PTR(-ENOMEM); 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()
572 cost += (u64) attr->max_entries * cost_per_node; in trie_alloc()
574 ret = bpf_map_charge_init(&trie->map.memory, cost); in trie_alloc()
578 spin_lock_init(&trie->lock); in trie_alloc()
580 return &trie->map; in trie_alloc()
598 slot = &trie->root; in trie_free()
605 if (rcu_access_pointer(node->child[0])) { in trie_free()
606 slot = &node->child[0]; in trie_free()
610 if (rcu_access_pointer(node->child[1])) { in trie_free()
611 slot = &node->child[1]; in trie_free()
631 int err = 0, stack_ptr = -1; in trie_get_next_key()
647 search_root = rcu_dereference(trie->root); in trie_get_next_key()
649 return -ENOENT; in trie_get_next_key()
652 if (!key || key->prefixlen > trie->max_prefixlen) in trie_get_next_key()
655 node_stack = kmalloc_array(trie->max_prefixlen, in trie_get_next_key()
659 return -ENOMEM; in trie_get_next_key()
665 if (node->prefixlen != matchlen || in trie_get_next_key()
666 node->prefixlen == key->prefixlen) in trie_get_next_key()
669 next_bit = extract_bit(key->data, node->prefixlen); in trie_get_next_key()
670 node = rcu_dereference(node->child[next_bit]); in trie_get_next_key()
672 if (!node || node->prefixlen != key->prefixlen || in trie_get_next_key()
673 (node->flags & LPM_TREE_NODE_FLAG_IM)) in trie_get_next_key()
676 /* The node with the exactly-matching key has been found, in trie_get_next_key()
681 parent = node_stack[stack_ptr - 1]; in trie_get_next_key()
682 if (rcu_dereference(parent->child[0]) == node) { in trie_get_next_key()
683 search_root = rcu_dereference(parent->child[1]); in trie_get_next_key()
687 if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) { in trie_get_next_key()
693 stack_ptr--; in trie_get_next_key()
697 err = -ENOENT; in trie_get_next_key()
701 /* Find the leftmost non-intermediate node, all intermediate nodes in trie_get_next_key()
705 if (node->flags & LPM_TREE_NODE_FLAG_IM) { in trie_get_next_key()
706 node = rcu_dereference(node->child[0]); in trie_get_next_key()
709 node = rcu_dereference(node->child[0]); in trie_get_next_key()
711 node = rcu_dereference(next_node->child[1]); in trie_get_next_key()
715 next_key->prefixlen = next_node->prefixlen; in trie_get_next_key()
717 next_node->data, trie->data_size); in trie_get_next_key()
729 return BTF_INFO_KIND(key_type->info) != BTF_KIND_STRUCT ? in trie_check_btf()
730 -EINVAL : 0; in trie_check_btf()