// SPDX-License-Identifier: GPL-2.0+/* * maple_tree.c: Userspace testing for maple tree test-suite * Copyright (c) 2018-2022 Oracle Corporation * Author: Liam R. Howlett <liam@infradead.org> * * Any tests that require internal knowledge of the tree or threads and other * difficult to handle in kernel tests. */ #define module_init(x)#define module_exit(x)#define MODULE_AUTHOR(x)#define MODULE_DESCRIPTION(X)#define MODULE_LICENSE(x)#define dump_stack() assert(0) #include "test.h" #include "../shared/maple-shim.c"#include "../../../lib/test_maple_tree.c" #define RCU_RANGE_COUNT 1000#define RCU_MT_BUG_ON(test, y) {if (y) { test->stop = true; } MT_BUG_ON(test->mt, y); } struct rcu_test_struct2 { struct maple_tree *mt; bool start; bool stop; unsigned int thread_count; unsigned int seen_toggle; unsigned int seen_added; unsigned int seen_modified; unsigned int seen_deleted; int pause; unsigned long index[RCU_RANGE_COUNT]; unsigned long last[RCU_RANGE_COUNT]; pthread_mutex_t dump;}; struct rcu_test_struct3 { struct maple_tree *mt; unsigned long index; unsigned long last; bool stop;}; struct rcu_reader_struct { unsigned int id; int mod; int del; int flip; int add; int next; struct rcu_test_struct2 *test;}; /* * Check erasing including RCU. */static noinline void __init check_erase(struct maple_tree *mt, unsigned long index, void *ptr){ MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr);} #define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2])#define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2])#define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2]) static noinline void __init check_erase_testset(struct maple_tree *mt){ static const unsigned long set[] = { 5015, 5014, 5017, 25, 1000, 1001, 1002, 1003, 1005, 0, 6003, 6002, 6008, 6012, 6015, 7003, 7002, 7008, 7012, 7015, 8003, 8002, 8008, 8012, 8015, 9003, 9002, 9008, 9012, 9015, 10003, 10002, 10008, 10012, 10015, 11003, 11002, 11008, 11012, 11015, 12003, 12002, 12008, 12012, 12015, 13003, 13002, 13008, 13012, 13015, 14003, 14002, 14008, 14012, 14015, 15003, 15002, 15008, 15012, 15015, }; void *ptr = &check_erase_testset; void *entry[2] = { ptr, mt }; void *root_node; rcu_register_thread(); mt_set_in_rcu(mt); for (int i = 0; i < 4; i++) erase_check_insert(mt, i); for (int i = 0; i < 4; i++) erase_check_load(mt, i); mt_set_non_kernel(2); erase_check_erase(mt, 1); erase_check_load(mt, 0); check_load(mt, set[1], NULL); for (int i = 2; i < 4; i++) erase_check_load(mt, i); erase_check_erase(mt, 2); erase_check_load(mt, 0); check_load(mt, set[1], NULL); check_load(mt, set[2], NULL); erase_check_insert(mt, 1); erase_check_insert(mt, 2); for (int i = 0; i < 4; i++) erase_check_load(mt, i); /* Check erase and load without an allocation. */ erase_check_load(mt, 3); erase_check_erase(mt, 1); erase_check_load(mt, 0); check_load(mt, set[1], NULL); for (int i = 2; i < 4; i++) erase_check_load(mt, i); /* * Set the newly erased node. This will produce a different allocated * node to avoid busy slots. */ root_node = mt->ma_root; erase_check_insert(mt, 1); erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); erase_check_load(mt, 2); check_load(mt, 5018, NULL); erase_check_load(mt, 3); erase_check_erase(mt, 2); /* erase 5017 to check append */ erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); check_load(mt, set[2], NULL); check_load(mt, 5018, NULL); erase_check_load(mt, 3); root_node = mt->ma_root; erase_check_insert(mt, 2); erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); erase_check_load(mt, 2); check_load(mt, 5018, NULL); erase_check_load(mt, 3); mt_set_non_kernel(1); erase_check_erase(mt, 2); /* erase 5017 to check append */ erase_check_load(mt, 0); check_load(mt, 5016, NULL); check_load(mt, set[2], NULL); erase_check_erase(mt, 0); /* erase 5015 to check append */ check_load(mt, set[0], NULL); check_load(mt, 5016, NULL); erase_check_insert(mt, 4); /* 1000 < Should not split. */ check_load(mt, set[0], NULL); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); check_load(mt, set[2], NULL); check_load(mt, 5018, NULL); erase_check_load(mt, 4); check_load(mt, 999, NULL); check_load(mt, 1001, NULL); erase_check_load(mt, 4); if (mt_in_rcu(mt)) MT_BUG_ON(mt, root_node == mt->ma_root); else MT_BUG_ON(mt, root_node != mt->ma_root); /* Should not have split. */ MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root)); /* Coalesce testing */ erase_check_insert(mt, 0); erase_check_insert(mt, 2); for (int i = 5; i < 25; i++) { erase_check_insert(mt, i); for (int j = i; j >= 0; j--) erase_check_load(mt, j); } erase_check_erase(mt, 14); /*6015 */ for (int i = 0; i < 25; i++) { if (i == 14) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 16); /*7002 */ for (int i = 0; i < 25; i++) { if (i == 16 || i == 14) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(1); erase_check_erase(mt, 13); /*6012 */ for (int i = 0; i < 25; i++) { if (i == 16 || i == 14 || i == 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 15); /*7003 */ for (int i = 0; i < 25; i++) { if (i <= 16 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */ for (int i = 0; i < 25; i++) { if (i <= 17 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 18); /*7012 */ for (int i = 0; i < 25; i++) { if (i <= 18 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 19); /*7015 */ for (int i = 0; i < 25; i++) { if (i <= 19 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 20); /*8003 */ for (int i = 0; i < 25; i++) { if (i <= 20 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 21); /*8002 */ for (int i = 0; i < 25; i++) { if (i <= 21 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 22); /*8008 */ for (int i = 0; i < 25; i++) { if (i <= 22 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } for (int i = 23; i < 25; i++) erase_check_erase(mt, i); for (int i = 0; i < 25; i++) { if (i <= 25 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } /* Shrinking tree test. */ for (int i = 13; i < ARRAY_SIZE(set); i++) erase_check_insert(mt, i); mt_set_non_kernel(99); for (int i = 18; i < ARRAY_SIZE(set); i++) { erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { if (j < 18 || j > i) erase_check_load(mt, j); else check_load(mt, set[j], NULL); } } mt_set_non_kernel(35); for (int i = 0; i < 18; i++) { erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { if (j < 18 && j > i) erase_check_load(mt, j); else check_load(mt, set[j], NULL); } } erase_check_insert(mt, 8); erase_check_insert(mt, 9); erase_check_erase(mt, 8); rcu_unregister_thread();} /* End of erase testing */ /* VM Generated Crashes - uses its own tree walk for verification */#define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \ a[(i)], a[(i + 1)], ptr)#define STORE 1#define SNULL 2#define ERASE 3#define ec_type_str(x) \ (((x) == STORE) ? \ "STORE" : \ (((x) == SNULL) ? \ "SNULL" : "ERASE") \ )#define check_erase2_debug 0 /* Calculate the overwritten entries. */int mas_ce2_over_count(struct ma_state *mas_start, struct ma_state *mas_end, void *s_entry, unsigned long s_min, void *e_entry, unsigned long e_max, const unsigned long *set, int i, bool null_entry){ int count = 0, span = 0; unsigned long retry = 0; void *entry; struct ma_state tmp; /* count slots */ memcpy(&tmp, mas_start, sizeof(tmp)); entry = mas_next(&tmp, mas_end->last); while (entry) { BUG_ON(retry > 50); /* stop infinite retry on testing. */ if (xa_is_zero(s_entry)) { retry++; continue; } count++; span++; entry = mas_next(&tmp, mas_end->last); } if (null_entry) { /* Check splitting end. */ if (e_entry && (e_max > mas_end->last)) count--; /* check overwrite of entire start */ if (s_entry && (s_min == mas_start->index)) count++; } else { /* !null_entry (store) */ bool esplit = e_max > mas_end->last; bool ssplit = s_min != mas_start->index; if (s_entry && e_entry) { if (esplit && ssplit) count--; else if (ssplit) count--; else if (esplit) { if (span) count--; } } else if (s_entry && !e_entry) { if (ssplit) count--; } else if (!s_entry && e_entry) { if (esplit) count--; count--; } else { count--; } } return count;} /* * mas_node_walk() - Walk a maple node to offset of the index. * @mas: The maple state * @type: The maple node type * @*range_min: Pointer to store the minimum range of the offset * @*range_max: Pointer to store the maximum range of the offset * * The offset will be stored in the maple state. * */static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node, enum maple_type type, unsigned long *range_min, unsigned long *range_max) { unsigned long *pivots; unsigned char count; unsigned long prev, max; unsigned char offset; unsigned long index; if (unlikely(ma_is_dense(type))) { (*range_max) = (*range_min) = mas->index; if (unlikely(ma_dead_node(node))) return; mas->offset = mas->index = mas->min; return; } pivots = ma_pivots(node, type); max = pivots[0]; if (unlikely(ma_dead_node(node))) return; offset = 0; prev = mas->min; index = mas->index; if (unlikely(index <= max)) goto offset_zero; count = mt_pivots[type]; while (++offset < count) { prev = max; max = pivots[offset]; if (unlikely(ma_dead_node(node))) return; if (index <= max) goto offset_found; else if (unlikely(!max)) goto mas_max; } prev = max;mas_max: max = mas->max;offset_found: prev++;offset_zero: mas->offset = offset; if (ma_is_leaf(type)) { *range_max = max; *range_min = prev; } else { mas->max = max; mas->min = prev; }} /* * mas_descend_walk(): Locates a value and sets the mas->node and slot * accordingly. range_min and range_max are set to the range which the entry is * valid. * @mas: The maple state * @*range_min: A pointer to store the minimum of the range * @*range_max: A pointer to store the maximum of the range * * Check mas->node is still valid on return of any value. * * Return: true if pointing to a valid node and offset. False otherwise. */static inline bool mas_descend_walk(struct ma_state *mas, unsigned long *range_min, unsigned long *range_max){ struct maple_enode *next; struct maple_node *node; enum maple_type type; next = mas->node; while (true) { node = mte_to_node(next); type = mte_node_type(next); mas_node_walk(mas, node, type, range_min, range_max); next = mas_slot(mas, ma_slots(node, type), mas->offset); if (unlikely(ma_dead_node(node)))Lines 1–500 of 36517. Load more
// SPDX-License-Identifier: GPL-2.0+ /* * maple_tree.c: Userspace testing for maple tree test-suite * Copyright (c) 2018-2022 Oracle Corporation * Author: Liam R. Howlett <liam@infradead.org> * * Any tests that require internal knowledge of the tree or threads and other * difficult to handle in kernel tests. */ #define module_init(x) #define module_exit(x) #define MODULE_AUTHOR(x) #define MODULE_DESCRIPTION(X) #define MODULE_LICENSE(x) #define dump_stack() assert(0) #include "test.h" #include "../shared/maple-shim.c" #include "../../../lib/test_maple_tree.c" #define RCU_RANGE_COUNT 1000 #define RCU_MT_BUG_ON(test, y) {if (y) { test->stop = true; } MT_BUG_ON(test->mt, y); } struct rcu_test_struct2 { struct maple_tree *mt; bool start; bool stop; unsigned int thread_count; unsigned int seen_toggle; unsigned int seen_added; unsigned int seen_modified; unsigned int seen_deleted; int pause; unsigned long index[RCU_RANGE_COUNT]; unsigned long last[RCU_RANGE_COUNT]; pthread_mutex_t dump; }; struct rcu_test_struct3 { struct maple_tree *mt; unsigned long index; unsigned long last; bool stop; }; struct rcu_reader_struct { unsigned int id; int mod; int del; int flip; int add; int next; struct rcu_test_struct2 *test; }; /* * Check erasing including RCU. */ static noinline void __init check_erase(struct maple_tree *mt, unsigned long index, void *ptr) { MT_BUG_ON(mt, mtree_test_erase(mt, index) != ptr); } #define erase_check_load(mt, i) check_load(mt, set[i], entry[i%2]) #define erase_check_insert(mt, i) check_insert(mt, set[i], entry[i%2]) #define erase_check_erase(mt, i) check_erase(mt, set[i], entry[i%2]) static noinline void __init check_erase_testset(struct maple_tree *mt) { static const unsigned long set[] = { 5015, 5014, 5017, 25, 1000, 1001, 1002, 1003, 1005, 0, 6003, 6002, 6008, 6012, 6015, 7003, 7002, 7008, 7012, 7015, 8003, 8002, 8008, 8012, 8015, 9003, 9002, 9008, 9012, 9015, 10003, 10002, 10008, 10012, 10015, 11003, 11002, 11008, 11012, 11015, 12003, 12002, 12008, 12012, 12015, 13003, 13002, 13008, 13012, 13015, 14003, 14002, 14008, 14012, 14015, 15003, 15002, 15008, 15012, 15015, }; void *ptr = &check_erase_testset; void *entry[2] = { ptr, mt }; void *root_node; rcu_register_thread(); mt_set_in_rcu(mt); for (int i = 0; i < 4; i++) erase_check_insert(mt, i); for (int i = 0; i < 4; i++) erase_check_load(mt, i); mt_set_non_kernel(2); erase_check_erase(mt, 1); erase_check_load(mt, 0); check_load(mt, set[1], NULL); for (int i = 2; i < 4; i++) erase_check_load(mt, i); erase_check_erase(mt, 2); erase_check_load(mt, 0); check_load(mt, set[1], NULL); check_load(mt, set[2], NULL); erase_check_insert(mt, 1); erase_check_insert(mt, 2); for (int i = 0; i < 4; i++) erase_check_load(mt, i); /* Check erase and load without an allocation. */ erase_check_load(mt, 3); erase_check_erase(mt, 1); erase_check_load(mt, 0); check_load(mt, set[1], NULL); for (int i = 2; i < 4; i++) erase_check_load(mt, i); /* * Set the newly erased node. This will produce a different allocated * node to avoid busy slots. */ root_node = mt->ma_root; erase_check_insert(mt, 1); erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); erase_check_load(mt, 2); check_load(mt, 5018, NULL); erase_check_load(mt, 3); erase_check_erase(mt, 2); /* erase 5017 to check append */ erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); check_load(mt, set[2], NULL); check_load(mt, 5018, NULL); erase_check_load(mt, 3); root_node = mt->ma_root; erase_check_insert(mt, 2); erase_check_load(mt, 0); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); erase_check_load(mt, 2); check_load(mt, 5018, NULL); erase_check_load(mt, 3); mt_set_non_kernel(1); erase_check_erase(mt, 2); /* erase 5017 to check append */ erase_check_load(mt, 0); check_load(mt, 5016, NULL); check_load(mt, set[2], NULL); erase_check_erase(mt, 0); /* erase 5015 to check append */ check_load(mt, set[0], NULL); check_load(mt, 5016, NULL); erase_check_insert(mt, 4); /* 1000 < Should not split. */ check_load(mt, set[0], NULL); check_load(mt, 5016, NULL); erase_check_load(mt, 1); check_load(mt, 5013, NULL); check_load(mt, set[2], NULL); check_load(mt, 5018, NULL); erase_check_load(mt, 4); check_load(mt, 999, NULL); check_load(mt, 1001, NULL); erase_check_load(mt, 4); if (mt_in_rcu(mt)) MT_BUG_ON(mt, root_node == mt->ma_root); else MT_BUG_ON(mt, root_node != mt->ma_root); /* Should not have split. */ MT_BUG_ON(mt, !mte_is_leaf(mt->ma_root)); /* Coalesce testing */ erase_check_insert(mt, 0); erase_check_insert(mt, 2); for (int i = 5; i < 25; i++) { erase_check_insert(mt, i); for (int j = i; j >= 0; j--) erase_check_load(mt, j); } erase_check_erase(mt, 14); /*6015 */ for (int i = 0; i < 25; i++) { if (i == 14) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 16); /*7002 */ for (int i = 0; i < 25; i++) { if (i == 16 || i == 14) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(1); erase_check_erase(mt, 13); /*6012 */ for (int i = 0; i < 25; i++) { if (i == 16 || i == 14 || i == 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 15); /*7003 */ for (int i = 0; i < 25; i++) { if (i <= 16 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 17); /*7008 *should* cause coalesce. */ for (int i = 0; i < 25; i++) { if (i <= 17 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 18); /*7012 */ for (int i = 0; i < 25; i++) { if (i <= 18 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 19); /*7015 */ for (int i = 0; i < 25; i++) { if (i <= 19 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 20); /*8003 */ for (int i = 0; i < 25; i++) { if (i <= 20 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } erase_check_erase(mt, 21); /*8002 */ for (int i = 0; i < 25; i++) { if (i <= 21 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } mt_set_non_kernel(2); erase_check_erase(mt, 22); /*8008 */ for (int i = 0; i < 25; i++) { if (i <= 22 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } for (int i = 23; i < 25; i++) erase_check_erase(mt, i); for (int i = 0; i < 25; i++) { if (i <= 25 && i >= 13) check_load(mt, set[i], NULL); else erase_check_load(mt, i); } /* Shrinking tree test. */ for (int i = 13; i < ARRAY_SIZE(set); i++) erase_check_insert(mt, i); mt_set_non_kernel(99); for (int i = 18; i < ARRAY_SIZE(set); i++) { erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { if (j < 18 || j > i) erase_check_load(mt, j); else check_load(mt, set[j], NULL); } } mt_set_non_kernel(35); for (int i = 0; i < 18; i++) { erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { if (j < 18 && j > i) erase_check_load(mt, j); else check_load(mt, set[j], NULL); } } erase_check_insert(mt, 8); erase_check_insert(mt, 9); erase_check_erase(mt, 8); rcu_unregister_thread(); } /* End of erase testing */ /* VM Generated Crashes - uses its own tree walk for verification */ #define erase_check_store_range(mt, a, i, ptr) mtree_test_store_range(mt, \ a[(i)], a[(i + 1)], ptr) #define STORE 1 #define SNULL 2 #define ERASE 3 #define ec_type_str(x) \ (((x) == STORE) ? \ "STORE" : \ (((x) == SNULL) ? \ "SNULL" : "ERASE") \ ) #define check_erase2_debug 0 /* Calculate the overwritten entries. */ int mas_ce2_over_count(struct ma_state *mas_start, struct ma_state *mas_end, void *s_entry, unsigned long s_min, void *e_entry, unsigned long e_max, const unsigned long *set, int i, bool null_entry) { int count = 0, span = 0; unsigned long retry = 0; void *entry; struct ma_state tmp; /* count slots */ memcpy(&tmp, mas_start, sizeof(tmp)); entry = mas_next(&tmp, mas_end->last); while (entry) { BUG_ON(retry > 50); /* stop infinite retry on testing. */ if (xa_is_zero(s_entry)) { retry++; continue; } count++; span++; entry = mas_next(&tmp, mas_end->last); } if (null_entry) { /* Check splitting end. */ if (e_entry && (e_max > mas_end->last)) count--; /* check overwrite of entire start */ if (s_entry && (s_min == mas_start->index)) count++; } else { /* !null_entry (store) */ bool esplit = e_max > mas_end->last; bool ssplit = s_min != mas_start->index; if (s_entry && e_entry) { if (esplit && ssplit) count--; else if (ssplit) count--; else if (esplit) { if (span) count--; } } else if (s_entry && !e_entry) { if (ssplit) count--; } else if (!s_entry && e_entry) { if (esplit) count--; count--; } else { count--; } } return count; } /* * mas_node_walk() - Walk a maple node to offset of the index. * @mas: The maple state * @type: The maple node type * @*range_min: Pointer to store the minimum range of the offset * @*range_max: Pointer to store the maximum range of the offset * * The offset will be stored in the maple state. * */ static inline void mas_node_walk(struct ma_state *mas, struct maple_node *node, enum maple_type type, unsigned long *range_min, unsigned long *range_max) { unsigned long *pivots; unsigned char count; unsigned long prev, max; unsigned char offset; unsigned long index; if (unlikely(ma_is_dense(type))) { (*range_max) = (*range_min) = mas->index; if (unlikely(ma_dead_node(node))) return; mas->offset = mas->index = mas->min; return; } pivots = ma_pivots(node, type); max = pivots[0]; if (unlikely(ma_dead_node(node))) return; offset = 0; prev = mas->min; index = mas->index; if (unlikely(index <= max)) goto offset_zero; count = mt_pivots[type]; while (++offset < count) { prev = max; max = pivots[offset]; if (unlikely(ma_dead_node(node))) return; if (index <= max) goto offset_found; else if (unlikely(!max)) goto mas_max; } prev = max; mas_max: max = mas->max; offset_found: prev++; offset_zero: mas->offset = offset; if (ma_is_leaf(type)) { *range_max = max; *range_min = prev; } else { mas->max = max; mas->min = prev; } } /* * mas_descend_walk(): Locates a value and sets the mas->node and slot * accordingly. range_min and range_max are set to the range which the entry is * valid. * @mas: The maple state * @*range_min: A pointer to store the minimum of the range * @*range_max: A pointer to store the maximum of the range * * Check mas->node is still valid on return of any value. * * Return: true if pointing to a valid node and offset. False otherwise. */ static inline bool mas_descend_walk(struct ma_state *mas, unsigned long *range_min, unsigned long *range_max) { struct maple_enode *next; struct maple_node *node; enum maple_type type; next = mas->node; while (true) { node = mte_to_node(next); type = mte_node_type(next); mas_node_walk(mas, node, type, range_min, range_max); next = mas_slot(mas, ma_slots(node, type), mas->offset); if (unlikely(ma_dead_node(node)))