1 // SPDX-License-Identifier: GPL-2.0-only
26 	struct lpm_trie_node __rcu	*child[2];  member
56  * [0xc0, 0xa8, 0x00, 0x00] in big-endian notation. This documentation will
57  * stick to IP-address notation for readability though.
61  * child pointers are %NULL.
63  *              +----------------+
68  *              +----------------+
72  * node (2) will become a child of (1). In child index depends on the next bit
74  * child[0] of (1):
76  *              +----------------+
81  *              +----------------+
83  *    +----------------+
88  *    +----------------+
90  * The child[1] slot of (1) could be filled with another node which has bit #17
94  *              +----------------+
99  *              +----------------+
101  *    +----------------+  +------------------+
106  *    +----------------+  +------------------+
110  * above (bit #17 is 0), it would normally be attached to (1) as child[0].
117  *                      +----------------+
122  *                      +----------------+
124  *            +----------------+  +------------------+
127  *            |    value: ---  |  |     value: 3     |
129  *            +----------------+  +------------------+
131  *  +----------------+  +----------------+
136  *  +----------------+  +----------------+
138  * 192.168.1.1/32 would be a child of (5) etc.
141  * example above, (4) would be re-used if 192.168.0.0/23 is added to the trie.
147  * is a child that can be used to become more specific, the trie is traversed
148  * downwards. The last node in the traversal that is a non-intermediate one is
154 	return !!(data[index / 8] & (1 << (7 - (index % 8))));  in extract_bit()
158  * longest_prefix_match() - determine the longest prefix
169 	u32 limit = min(node->prefixlen, key->prefixlen);  in longest_prefix_match()
180 	if (trie->data_size >= 8) {  in longest_prefix_match()
181 		u64 diff = be64_to_cpu(*(__be64 *)node->data ^  in longest_prefix_match()
182 				       *(__be64 *)key->data);  in longest_prefix_match()
184 		prefixlen = 64 - fls64(diff);  in longest_prefix_match()
193 	while (trie->data_size >= i + 4) {  in longest_prefix_match()
194 		u32 diff = be32_to_cpu(*(__be32 *)&node->data[i] ^  in longest_prefix_match()
195 				       *(__be32 *)&key->data[i]);  in longest_prefix_match()
197 		prefixlen += 32 - fls(diff);  in longest_prefix_match()
205 	if (trie->data_size >= i + 2) {  in longest_prefix_match()
206 		u16 diff = be16_to_cpu(*(__be16 *)&node->data[i] ^  in longest_prefix_match()
207 				       *(__be16 *)&key->data[i]);  in longest_prefix_match()
209 		prefixlen += 16 - fls(diff);  in longest_prefix_match()
217 	if (trie->data_size >= i + 1) {  in longest_prefix_match()
218 		prefixlen += 8 - fls(node->data[i] ^ key->data[i]);  in longest_prefix_match()
236 	for (node = rcu_dereference_check(trie->root, rcu_read_lock_bh_held());  in trie_lookup_elem()
246 		if (matchlen == trie->max_prefixlen) {  in trie_lookup_elem()
253 		 * last in the traversal (ie, the parent).  in trie_lookup_elem()
255 		if (matchlen < node->prefixlen)  in trie_lookup_elem()
261 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_lookup_elem()
268 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_lookup_elem()
269 		node = rcu_dereference_check(node->child[next_bit],  in trie_lookup_elem()
276 	return found->data + trie->data_size;  in trie_lookup_elem()
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()
293 	node->flags = 0;  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()
316 		return -EINVAL;  in trie_update_elem()
318 	if (key->prefixlen > trie->max_prefixlen)  in trie_update_elem()
319 		return -EINVAL;  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()
326 		ret = -ENOSPC;  in trie_update_elem()
332 		ret = -ENOMEM;  in trie_update_elem()
336 	trie->n_entries++;  in trie_update_elem()
338 	new_node->prefixlen = key->prefixlen;  in trie_update_elem()
339 	RCU_INIT_POINTER(new_node->child[0], NULL);  in trie_update_elem()
340 	RCU_INIT_POINTER(new_node->child[1], NULL);  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()
354 		if (node->prefixlen != matchlen ||  in trie_update_elem()
355 		    node->prefixlen == key->prefixlen ||  in trie_update_elem()
356 		    node->prefixlen == trie->max_prefixlen)  in trie_update_elem()
359 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_update_elem()
360 		slot = &node->child[next_bit];  in trie_update_elem()
363 	/* If the slot is empty (a free child pointer or an empty root),  in trie_update_elem()
374 	if (node->prefixlen == matchlen) {  in trie_update_elem()
375 		new_node->child[0] = node->child[0];  in trie_update_elem()
376 		new_node->child[1] = node->child[1];  in trie_update_elem()
378 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_update_elem()
379 			trie->n_entries--;  in trie_update_elem()
390 	if (matchlen == key->prefixlen) {  in trie_update_elem()
391 		next_bit = extract_bit(node->data, matchlen);  in trie_update_elem()
392 		rcu_assign_pointer(new_node->child[next_bit], node);  in trie_update_elem()
399 		ret = -ENOMEM;  in trie_update_elem()
403 	im_node->prefixlen = matchlen;  in trie_update_elem()
404 	im_node->flags |= LPM_TREE_NODE_FLAG_IM;  in trie_update_elem()
405 	memcpy(im_node->data, node->data, trie->data_size);  in trie_update_elem()
407 	/* Now determine which child to install in which slot */  in trie_update_elem()
408 	if (extract_bit(key->data, matchlen)) {  in trie_update_elem()
409 		rcu_assign_pointer(im_node->child[0], node);  in trie_update_elem()
410 		rcu_assign_pointer(im_node->child[1], new_node);  in trie_update_elem()
412 		rcu_assign_pointer(im_node->child[0], new_node);  in trie_update_elem()
413 		rcu_assign_pointer(im_node->child[1], node);  in trie_update_elem()
422 			trie->n_entries--;  in trie_update_elem()
428 	spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_update_elem()
439 	struct lpm_trie_node *node, *parent;  in trie_delete_elem()  local
445 	if (key->prefixlen > trie->max_prefixlen)  in trie_delete_elem()
446 		return -EINVAL;  in trie_delete_elem()
448 	spin_lock_irqsave(&trie->lock, irq_flags);  in trie_delete_elem()
453 	 * to delete.  We may also need to know the nodes parent and the  in trie_delete_elem()
456 	trim = &trie->root;  in trie_delete_elem()
458 	parent = NULL;  in trie_delete_elem()
460 		       *trim, lockdep_is_held(&trie->lock)))) {  in trie_delete_elem()
463 		if (node->prefixlen != matchlen ||  in trie_delete_elem()
464 		    node->prefixlen == key->prefixlen)  in trie_delete_elem()
467 		parent = node;  in trie_delete_elem()
469 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_delete_elem()
470 		trim = &node->child[next_bit];  in trie_delete_elem()
473 	if (!node || node->prefixlen != key->prefixlen ||  in trie_delete_elem()
474 	    node->prefixlen != matchlen ||  in trie_delete_elem()
475 	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {  in trie_delete_elem()
476 		ret = -ENOENT;  in trie_delete_elem()
480 	trie->n_entries--;  in trie_delete_elem()
485 	if (rcu_access_pointer(node->child[0]) &&  in trie_delete_elem()
486 	    rcu_access_pointer(node->child[1])) {  in trie_delete_elem()
487 		node->flags |= LPM_TREE_NODE_FLAG_IM;  in trie_delete_elem()
491 	/* If the parent of the node we are about to delete is an intermediate  in trie_delete_elem()
493 	 * the intermediate parent as well and promote its other child  in trie_delete_elem()
498 	if (parent && (parent->flags & LPM_TREE_NODE_FLAG_IM) &&  in trie_delete_elem()
499 	    !node->child[0] && !node->child[1]) {  in trie_delete_elem()
500 		if (node == rcu_access_pointer(parent->child[0]))  in trie_delete_elem()
502 				*trim2, rcu_access_pointer(parent->child[1]));  in trie_delete_elem()
505 				*trim2, rcu_access_pointer(parent->child[0]));  in trie_delete_elem()
506 		kfree_rcu(parent, rcu);  in trie_delete_elem()
511 	/* The node we are removing has either zero or one child. If there  in trie_delete_elem()
512 	 * is a child, move it into the removed node's slot then delete  in trie_delete_elem()
515 	if (node->child[0])  in trie_delete_elem()
516 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[0]));  in trie_delete_elem()
517 	else if (node->child[1])  in trie_delete_elem()
518 		rcu_assign_pointer(*trim, rcu_access_pointer(node->child[1]));  in trie_delete_elem()
524 	spin_unlock_irqrestore(&trie->lock, irq_flags);  in trie_delete_elem()
532 #define LPM_VAL_SIZE_MAX	(KMALLOC_MAX_SIZE - LPM_DATA_SIZE_MAX - \
548 		return ERR_PTR(-EPERM);  in trie_alloc()
551 	if (attr->max_entries == 0 ||  in trie_alloc()
552 	    !(attr->map_flags & BPF_F_NO_PREALLOC) ||  in trie_alloc()
553 	    attr->map_flags & ~LPM_CREATE_FLAG_MASK ||  in trie_alloc()
554 	    !bpf_map_flags_access_ok(attr->map_flags) ||  in trie_alloc()
555 	    attr->key_size < LPM_KEY_SIZE_MIN ||  in trie_alloc()
556 	    attr->key_size > LPM_KEY_SIZE_MAX ||  in trie_alloc()
557 	    attr->value_size < LPM_VAL_SIZE_MIN ||  in trie_alloc()
558 	    attr->value_size > LPM_VAL_SIZE_MAX)  in trie_alloc()
559 		return ERR_PTR(-EINVAL);  in trie_alloc()
563 		return ERR_PTR(-ENOMEM);  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()
583 	 * children. Then free that node, nullify its reference in the parent  in trie_free()
588 		slot = &trie->root;  in trie_free()
595 			if (rcu_access_pointer(node->child[0])) {  in trie_free()
596 				slot = &node->child[0];  in trie_free()
600 			if (rcu_access_pointer(node->child[1])) {  in trie_free()
601 				slot = &node->child[1];  in trie_free()
617 	struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;  in trie_get_next_key()  local
621 	int err = 0, stack_ptr = -1;  in trie_get_next_key()
637 	search_root = rcu_dereference(trie->root);  in trie_get_next_key()
639 		return -ENOENT;  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()
649 		return -ENOMEM;  in trie_get_next_key()
655 		if (node->prefixlen != matchlen ||  in trie_get_next_key()
656 		    node->prefixlen == key->prefixlen)  in trie_get_next_key()
659 		next_bit = extract_bit(key->data, node->prefixlen);  in trie_get_next_key()
660 		node = rcu_dereference(node->child[next_bit]);  in trie_get_next_key()
662 	if (!node || node->prefixlen != key->prefixlen ||  in trie_get_next_key()
663 	    (node->flags & LPM_TREE_NODE_FLAG_IM))  in trie_get_next_key()
666 	/* The node with the exactly-matching key has been found,  in trie_get_next_key()
671 		parent = node_stack[stack_ptr - 1];  in trie_get_next_key()
672 		if (rcu_dereference(parent->child[0]) == node) {  in trie_get_next_key()
673 			search_root = rcu_dereference(parent->child[1]);  in trie_get_next_key()
677 		if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {  in trie_get_next_key()
678 			next_node = parent;  in trie_get_next_key()
682 		node = parent;  in trie_get_next_key()
683 		stack_ptr--;  in trie_get_next_key()
687 	err = -ENOENT;  in trie_get_next_key()
691 	/* Find the leftmost non-intermediate node, all intermediate nodes  in trie_get_next_key()
695 		if (node->flags & LPM_TREE_NODE_FLAG_IM) {  in trie_get_next_key()
696 			node = rcu_dereference(node->child[0]);  in trie_get_next_key()
699 			node = rcu_dereference(node->child[0]);  in trie_get_next_key()
701 				node = rcu_dereference(next_node->child[1]);  in trie_get_next_key()
705 	next_key->prefixlen = next_node->prefixlen;  in trie_get_next_key()
707 	       next_node->data, trie->data_size);  in trie_get_next_key()
719 	return BTF_INFO_KIND(key_type->info) != BTF_KIND_STRUCT ?  in trie_check_btf()
720 	       -EINVAL : 0;  in trie_check_btf()