215 static inline unsigned int mt_attr(struct maple_tree *mt)  in mt_attr()  argument
217 	return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK;  in mt_attr()
381 static __always_inline bool mt_is_alloc(struct maple_tree *mt)  in mt_is_alloc()  argument
383 	return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);  in mt_is_alloc()
755  * @mt: The maple node type
759 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)  in ma_slots()  argument
761 	switch (mt) {  in ma_slots()
774 static inline bool mt_write_locked(const struct maple_tree *mt)  in mt_write_locked()  argument
776 	return mt_external_lock(mt) ? mt_write_lock_is_held(mt) :  in mt_write_locked()
777 		lockdep_is_held(&mt->ma_lock);  in mt_write_locked()
780 static __always_inline bool mt_locked(const struct maple_tree *mt)  in mt_locked()  argument
782 	return mt_external_lock(mt) ? mt_lock_is_held(mt) :  in mt_locked()
783 		lockdep_is_held(&mt->ma_lock);  in mt_locked()
786 static __always_inline void *mt_slot(const struct maple_tree *mt,  in mt_slot()  argument
789 	return rcu_dereference_check(slots[offset], mt_locked(mt));  in mt_slot()
792 static __always_inline void *mt_slot_locked(struct maple_tree *mt,  in mt_slot_locked()  argument
795 	return rcu_dereference_protected(slots[offset], mt_write_locked(mt));  in mt_slot_locked()
836 static inline void *mt_root_locked(struct maple_tree *mt)  in mt_root_locked()  argument
838 	return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt));  in mt_root_locked()
853 					     enum maple_type mt)  in ma_meta()  argument
855 	switch (mt) {  in ma_meta()
866  * @mt: The maple node type
870 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,  in ma_set_meta()  argument
873 	struct maple_metadata *meta = ma_meta(mn, mt);  in ma_set_meta()
881  * @mt: The maple tree
885 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,  in mt_clear_meta()  argument
898 			next = mt_slot_locked(mt, slots,  in mt_clear_meta()
919  * @mt: The maple node type
922 					enum maple_type mt)  in ma_meta_end()  argument
924 	struct maple_metadata *meta = ma_meta(mn, mt);  in ma_meta_end()
941  * @mt: The maple node type
944 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,  in ma_set_meta_gap()  argument
948 	struct maple_metadata *meta = ma_meta(mn, mt);  in ma_set_meta_gap()
975 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1470 	enum maple_type mt;  in mas_leaf_max_gap()  local
1478 	mt = mte_node_type(mas->node);  in mas_leaf_max_gap()
1480 	slots = ma_slots(mn, mt);  in mas_leaf_max_gap()
1482 	if (unlikely(ma_is_dense(mt))) {  in mas_leaf_max_gap()
1484 		for (i = 0; i < mt_slots[mt]; i++) {  in mas_leaf_max_gap()
1502 	pivots = ma_pivots(mn, mt);  in mas_leaf_max_gap()
1511 	max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1;  in mas_leaf_max_gap()
1545  * @mt: The maple node type
1553 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,  in ma_max_gap()  argument
1559 	i = offset = ma_meta_end(node, mt);  in ma_max_gap()
1581 	enum maple_type mt;  in mas_max_gap()  local
1584 	mt = mte_node_type(mas->node);  in mas_max_gap()
1585 	if (ma_is_leaf(mt))  in mas_max_gap()
1589 	MAS_BUG_ON(mas, mt != maple_arange_64);  in mas_max_gap()
1591 	gaps = ma_gaps(node, mt);  in mas_max_gap()
1751 	enum maple_type mt;  in mas_find_child()  local
1759 	mt = mte_node_type(mas->node);  in mas_find_child()
1761 	slots = ma_slots(node, mt);  in mas_find_child()
1762 	pivots = ma_pivots(node, mt);  in mas_find_child()
1763 	end = ma_data_end(node, mt, pivots, mas->max);  in mas_find_child()
1925 	enum maple_type mt;  in mas_mab_cp()  local
1933 	mt = mte_node_type(mas->node);  in mas_mab_cp()
1934 	pivots = ma_pivots(node, mt);  in mas_mab_cp()
1942 	piv_end = min(mas_end, mt_pivots[mt]);  in mas_mab_cp()
1953 		b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);  in mas_mab_cp()
1958 	slots = ma_slots(node, mt);  in mas_mab_cp()
1960 	if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) {  in mas_mab_cp()
1961 		gaps = ma_gaps(node, mt);  in mas_mab_cp()
1970  * @mt: The maple type
1974 		enum maple_type mt, unsigned char end)  in mas_leaf_set_meta()  argument
1976 	if (end < mt_slots[mt] - 1)  in mas_leaf_set_meta()
1977 		ma_set_meta(node, mt, 0, end);  in mas_leaf_set_meta()
1992 	enum maple_type mt = mte_node_type(mas->node);  in mab_mas_cp()  local
1994 	void __rcu **slots = ma_slots(node, mt);  in mab_mas_cp()
1995 	unsigned long *pivots = ma_pivots(node, mt);  in mab_mas_cp()
1999 	if (mab_end - mab_start > mt_pivots[mt])  in mab_mas_cp()
2002 	if (!pivots[mt_pivots[mt] - 1])  in mab_mas_cp()
2003 		slots[mt_pivots[mt]] = NULL;  in mab_mas_cp()
2017 	if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {  in mab_mas_cp()
2021 		gaps = ma_gaps(node, mt);  in mab_mas_cp()
2030 		ma_set_meta(node, mt, offset, end);  in mab_mas_cp()
2032 		mas_leaf_set_meta(node, mt, end);  in mab_mas_cp()
2040  * @mt: The maple node type
2043 				      enum maple_type mt)  in mas_bulk_rebalance()  argument
2051 	if (end > mt_min_slots[mt]) {  in mas_bulk_rebalance()
3009 	enum maple_type mt = mte_node_type(mas->node);  in mas_destroy_rebalance()  local
3012 	unsigned char offset, tmp, split = mt_slots[mt] / 2;  in mas_destroy_rebalance()
3031 	slots = ma_slots(newnode, mt);  in mas_destroy_rebalance()
3032 	pivs = ma_pivots(newnode, mt);  in mas_destroy_rebalance()
3034 	l_slots = ma_slots(left, mt);  in mas_destroy_rebalance()
3035 	l_pivs = ma_pivots(left, mt);  in mas_destroy_rebalance()
3043 	memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end);  in mas_destroy_rebalance()
3044 	memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end);  in mas_destroy_rebalance()
3052 		unsigned char max_p = mt_pivots[mt];  in mas_destroy_rebalance()
3053 		unsigned char max_s = mt_slots[mt];  in mas_destroy_rebalance()
3059 		if (tmp < mt_slots[mt])  in mas_destroy_rebalance()
3063 		ma_set_meta(node, mt, 0, tmp - 1);  in mas_destroy_rebalance()
3071 		ma_set_meta(left, mt, 0, split);  in mas_destroy_rebalance()
3078 	mas->node = mt_mk_node(newnode, mt);  in mas_destroy_rebalance()
3079 	ma_set_meta(newnode, mt, 0, tmp);  in mas_destroy_rebalance()
3083 	mt = mte_node_type(l_mas.node);  in mas_destroy_rebalance()
3084 	slots = ma_slots(new_left, mt);  in mas_destroy_rebalance()
3085 	pivs = ma_pivots(new_left, mt);  in mas_destroy_rebalance()
3088 	ma_set_meta(new_left, mt, 0, split);  in mas_destroy_rebalance()
3089 	l_mas.node = mt_mk_node(new_left, mt);  in mas_destroy_rebalance()
3093 	mt = mas_parent_type(&l_mas, l_mas.node);  in mas_destroy_rebalance()
3095 	slots = ma_slots(parent, mt);  in mas_destroy_rebalance()
3096 	pivs = ma_pivots(parent, mt);  in mas_destroy_rebalance()
3101 	eparent = mt_mk_node(parent, mt);  in mas_destroy_rebalance()
4414 	enum maple_type mt;  in mas_prev_node()  local
4443 	mt = mte_node_type(mas->node);  in mas_prev_node()
4446 		slots = ma_slots(node, mt);  in mas_prev_node()
4451 		mt = mte_node_type(mas->node);  in mas_prev_node()
4453 		pivots = ma_pivots(node, mt);  in mas_prev_node()
4454 		offset = ma_data_end(node, mt, pivots, max);  in mas_prev_node()
4459 	slots = ma_slots(node, mt);  in mas_prev_node()
4461 	pivots = ma_pivots(node, mt);  in mas_prev_node()
4587 	enum maple_type mt;  in mas_next_node()  local
4605 		mt = mte_node_type(mas->node);  in mas_next_node()
4606 		pivots = ma_pivots(node, mt);  in mas_next_node()
4607 		node_end = ma_data_end(node, mt, pivots, mas->max);  in mas_next_node()
4613 	slots = ma_slots(node, mt);  in mas_next_node()
4626 		mt = mte_node_type(mas->node);  in mas_next_node()
4627 		slots = ma_slots(node, mt);  in mas_next_node()
4634 		pivots = ma_pivots(node, mt);  in mas_next_node()
4636 	mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);  in mas_next_node()
4638 	mt = mte_node_type(enode);  in mas_next_node()
4639 	pivots = ma_pivots(tmp, mt);  in mas_next_node()
4640 	mas->end = ma_data_end(tmp, mt, pivots, mas->max);  in mas_next_node()
5088 	enum maple_type mt;  in mas_empty_area()  local
5121 	mt = mte_node_type(mas->node);  in mas_empty_area()
5122 	pivots = ma_pivots(node, mt);  in mas_empty_area()
5127 	mas->end = ma_data_end(node, mt, pivots, mas->max);  in mas_empty_area()
5196  * @mt: the maple tree
5204 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt,  in mte_dead_leaves()  argument
5213 		entry = mt_slot(mt, slots, offset);  in mte_dead_leaves()
5300 	struct maple_tree *mt, struct maple_enode *prev, unsigned char offset)  in mte_destroy_descend()  argument
5313 		next = mt_slot_locked(mt, slots, next_offset);  in mte_destroy_descend()
5315 			next = mt_slot_locked(mt, slots, ++next_offset);  in mte_destroy_descend()
5329 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,  in mt_destroy_walk()  argument
5342 	slots = mte_destroy_descend(&enode, mt, start, 0);  in mt_destroy_walk()
5349 		node->slot_len = mte_dead_leaves(enode, mt, slots);  in mt_destroy_walk()
5362 		tmp = mt_slot_locked(mt, slots, offset);  in mt_destroy_walk()
5366 			slots = mte_destroy_descend(&enode, mt, parent, offset);  in mt_destroy_walk()
5373 	node->slot_len = mte_dead_leaves(enode, mt, slots);  in mt_destroy_walk()
5381 		mt_clear_meta(mt, node, node->type);  in mt_destroy_walk()
5387  * @mt: the tree to free - needed for node types.
5392 				    struct maple_tree *mt)  in mte_destroy_walk()  argument
5396 	if (mt_in_rcu(mt)) {  in mte_destroy_walk()
5397 		mt_destroy_walk(enode, mt, false);  in mte_destroy_walk()
5400 		mt_destroy_walk(enode, mt, true);  in mte_destroy_walk()
5780  * @mt: The maple tree
5790 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)  in mt_next()  argument
5793 	MA_STATE(mas, mt, index, index);  in mt_next()
5910  * @mt: The maple tree
5920 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)  in mt_prev()  argument
5923 	MA_STATE(mas, mt, index, index);  in mt_prev()
6309  * @mt: The maple tree
6314 void *mtree_load(struct maple_tree *mt, unsigned long index)  in mtree_load()  argument
6316 	MA_STATE(mas, mt, index, index);  in mtree_load()
6347  * @mt: The maple tree
6356 int mtree_store_range(struct maple_tree *mt, unsigned long index,  in mtree_store_range()  argument
6359 	MA_STATE(mas, mt, index, last);  in mtree_store_range()
6369 	mtree_lock(mt);  in mtree_store_range()
6371 	mtree_unlock(mt);  in mtree_store_range()
6379  * @mt: The maple tree
6387 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry,  in mtree_store()  argument
6390 	return mtree_store_range(mt, index, index, entry, gfp);  in mtree_store()
6396  * @mt: The maple tree
6405 int mtree_insert_range(struct maple_tree *mt, unsigned long first,  in mtree_insert_range()  argument
6408 	MA_STATE(ms, mt, first, last);  in mtree_insert_range()
6417 	mtree_lock(mt);  in mtree_insert_range()
6423 	mtree_unlock(mt);  in mtree_insert_range()
6434  * @mt: The maple tree
6442 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,  in mtree_insert()  argument
6445 	return mtree_insert_range(mt, index, index, entry, gfp);  in mtree_insert()
6449 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,  in mtree_alloc_range()  argument
6455 	MA_STATE(mas, mt, 0, 0);  in mtree_alloc_range()
6456 	if (!mt_is_alloc(mt))  in mtree_alloc_range()
6462 	mtree_lock(mt);  in mtree_alloc_range()
6482 	mtree_unlock(mt);  in mtree_alloc_range()
6490  * @mt: The maple tree.
6498  * Finds an empty entry in @mt after @next, stores the new index into
6501  * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag.
6503  * Context: Any context.  Takes and releases the mt.lock.  May sleep if
6508  * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no
6511 int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp,  in mtree_alloc_cyclic()  argument
6517 	MA_STATE(mas, mt, 0, 0);  in mtree_alloc_cyclic()
6519 	if (!mt_is_alloc(mt))  in mtree_alloc_cyclic()
6523 	mtree_lock(mt);  in mtree_alloc_cyclic()
6526 	mtree_unlock(mt);  in mtree_alloc_cyclic()
6531 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,  in mtree_alloc_rrange()  argument
6537 	MA_STATE(mas, mt, 0, 0);  in mtree_alloc_rrange()
6538 	if (!mt_is_alloc(mt))  in mtree_alloc_rrange()
6544 	mtree_lock(mt);  in mtree_alloc_rrange()
6564 	mtree_unlock(mt);  in mtree_alloc_rrange()
6572  * @mt: The maple tree
6580 void *mtree_erase(struct maple_tree *mt, unsigned long index)  in mtree_erase()  argument
6584 	MA_STATE(mas, mt, index, index);  in mtree_erase()
6587 	mtree_lock(mt);  in mtree_erase()
6589 	mtree_unlock(mt);  in mtree_erase()
6790  * @mt: The source maple tree
6809 int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)  in __mt_dup()  argument
6812 	MA_STATE(mas, mt, 0, 0);  in __mt_dup()
6828  * @mt: The source maple tree
6846 int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)  in mtree_dup()  argument
6849 	MA_STATE(mas, mt, 0, 0);  in mtree_dup()
6869  * @mt: The maple tree
6873 void __mt_destroy(struct maple_tree *mt)  in __mt_destroy()  argument
6875 	void *root = mt_root_locked(mt);  in __mt_destroy()
6877 	rcu_assign_pointer(mt->ma_root, NULL);  in __mt_destroy()
6879 		mte_destroy_walk(root, mt);  in __mt_destroy()
6881 	mt->ma_flags = mt_attr(mt);  in __mt_destroy()
6887  * @mt: The maple tree
6891 void mtree_destroy(struct maple_tree *mt)  in mtree_destroy()  argument
6893 	mtree_lock(mt);  in mtree_destroy()
6894 	__mt_destroy(mt);  in mtree_destroy()
6895 	mtree_unlock(mt);  in mtree_destroy()
6901  * @mt: The maple tree
6915 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)  in mt_find()  argument
6917 	MA_STATE(mas, mt, *index, *index);  in mt_find()
6953 		if (MT_WARN_ON(mt, (*index) && ((*index) <= copy)))  in mt_find()
6965  * @mt: The maple tree
6975 void *mt_find_after(struct maple_tree *mt, unsigned long *index,  in mt_find_after()  argument
6981 	return mt_find(mt, index, max);  in mt_find_after()
7098 static void mt_dump_node(const struct maple_tree *mt, void *entry,
7137 static void mt_dump_range64(const struct maple_tree *mt, void *entry,  in mt_dump_range64()  argument
7167 			mt_dump_entry(mt_slot(mt, node->slot, i),  in mt_dump_range64()
7170 			mt_dump_node(mt, mt_slot(mt, node->slot, i),  in mt_dump_range64()
7190 static void mt_dump_arange64(const struct maple_tree *mt, void *entry,  in mt_dump_arange64()  argument
7229 			mt_dump_node(mt, mt_slot(mt, node->slot, i),  in mt_dump_arange64()
7249 static void mt_dump_node(const struct maple_tree *mt, void *entry,  in mt_dump_node()  argument
7267 			mt_dump_entry(mt_slot(mt, node->slot, i),  in mt_dump_node()
7273 		mt_dump_range64(mt, entry, min, max, depth, format);  in mt_dump_node()
7276 		mt_dump_arange64(mt, entry, min, max, depth, format);  in mt_dump_node()
7284 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)  in mt_dump()  argument
7286 	void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));  in mt_dump()
7289 		 mt, mt->ma_flags, mt_height(mt), entry);  in mt_dump()
7293 		mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format);  in mt_dump()
7305 	enum maple_type mt = mte_node_type(mas->node);  in mas_validate_gaps()  local
7310 	unsigned long *pivots = ma_pivots(node, mt);  in mas_validate_gaps()
7313 	if (ma_is_dense(mt)) {  in mas_validate_gaps()
7326 	gaps = ma_gaps(node, mt);  in mas_validate_gaps()
7328 		p_end = mas_safe_pivot(mas, pivots, i, mt);  in mas_validate_gaps()
7356 	if (mt == maple_arange_64) {  in mas_validate_gaps()
7539 static void mt_validate_nulls(struct maple_tree *mt)  in mt_validate_nulls()  argument
7544 	MA_STATE(mas, mt, 0, 0);  in mt_validate_nulls()
7560 		MT_BUG_ON(mt, !last && !entry);  in mt_validate_nulls()
7581 void mt_validate(struct maple_tree *mt)  in mt_validate()  argument
7586 	MA_STATE(mas, mt, 0, 0);  in mt_validate()
7605 		if (mt_is_alloc(mt))  in mt_validate()
7609 	mt_validate_nulls(mt);  in mt_validate()