linux-master/lib/maple_tree.c

215 static inline unsigned int mt_attr(struct maple_tree *mt)
217 	return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK;
381 static __always_inline bool mt_is_alloc(struct maple_tree *mt)
383 	return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE);
754  * @mt: The maple node type
758 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt)
760 	switch (mt) {
773 static inline bool mt_write_locked(const struct maple_tree *mt)
775 	return mt_external_lock(mt) ? mt_write_lock_is_held(mt) :
776 		lockdep_is_held(&mt->ma_lock);
779 static __always_inline bool mt_locked(const struct maple_tree *mt)
781 	return mt_external_lock(mt) ? mt_lock_is_held(mt) :
782 		lockdep_is_held(&mt->ma_lock);
785 static __always_inline void *mt_slot(const struct maple_tree *mt,
788 	return rcu_dereference_check(slots[offset], mt_locked(mt));
791 static __always_inline void *mt_slot_locked(struct maple_tree *mt,
794 	return rcu_dereference_protected(slots[offset], mt_write_locked(mt));
835 static inline void *mt_root_locked(struct maple_tree *mt)
837 	return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt));
852 					     enum maple_type mt)
854 	switch (mt) {
865  * @mt: The maple node type
869 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt,
872 	struct maple_metadata *meta = ma_meta(mn, mt);
880  * @mt: The maple tree
886 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn,
899 			next = mt_slot_locked(mt, slots,
920  * @mt: The maple node type
923 					enum maple_type mt)
925 	struct maple_metadata *meta = ma_meta(mn, mt);
945 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt,
949 	struct maple_metadata *meta = ma_meta(mn, mt);
976 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1471 	enum maple_type mt;
1479 	mt = mte_node_type(mas->node);
1481 	slots = ma_slots(mn, mt);
1483 	if (unlikely(ma_is_dense(mt))) {
1485 		for (i = 0; i < mt_slots[mt]; i++) {
1503 	pivots = ma_pivots(mn, mt);
1512 	max_piv = ma_data_end(mn, mt, pivots, mas->max) - 1;
1546  * @mt: The maple node type
1554 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt,
1560 	i = offset = ma_meta_end(node, mt);
1582 	enum maple_type mt;
1585 	mt = mte_node_type(mas->node);
1586 	if (ma_is_leaf(mt))
1590 	MAS_BUG_ON(mas, mt != maple_arange_64);
1592 	gaps = ma_gaps(node, mt);
1752 	enum maple_type mt;
1760 	mt = mte_node_type(mas->node);
1762 	slots = ma_slots(node, mt);
1763 	pivots = ma_pivots(node, mt);
1764 	end = ma_data_end(node, mt, pivots, mas->max);
1926 	enum maple_type mt;
1934 	mt = mte_node_type(mas->node);
1935 	pivots = ma_pivots(node, mt);
1943 	piv_end = min(mas_end, mt_pivots[mt]);
1954 		b_node->pivot[j] = mas_safe_pivot(mas, pivots, i, mt);
1959 	slots = ma_slots(node, mt);
1961 	if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) {
1962 		gaps = ma_gaps(node, mt);
1971  * @mt: The maple type
1975 		enum maple_type mt, unsigned char end)
1977 	if (end < mt_slots[mt] - 1)
1978 		ma_set_meta(node, mt, 0, end);
1993 	enum maple_type mt = mte_node_type(mas->node);
1995 	void __rcu **slots = ma_slots(node, mt);
1996 	unsigned long *pivots = ma_pivots(node, mt);
2000 	if (mab_end - mab_start > mt_pivots[mt])
2003 	if (!pivots[mt_pivots[mt] - 1])
2004 		slots[mt_pivots[mt]] = NULL;
2018 	if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) {
2022 		gaps = ma_gaps(node, mt);
2031 		ma_set_meta(node, mt, offset, end);
2033 		mas_leaf_set_meta(node, mt, end);
2041  * @mt: The maple node type
2044 				      enum maple_type mt)
2052 	if (end > mt_min_slots[mt]) {
3017 	enum maple_type mt = mte_node_type(mas->node);
3020 	unsigned char offset, tmp, split = mt_slots[mt] / 2;
3044 	slots = ma_slots(newnode, mt);
3045 	pivs = ma_pivots(newnode, mt);
3047 	l_slots = ma_slots(left, mt);
3048 	l_pivs = ma_pivots(left, mt);
3056 	memcpy(slots + tmp, ma_slots(node, mt), sizeof(void *) * end);
3057 	memcpy(pivs + tmp, ma_pivots(node, mt), sizeof(unsigned long) * end);
3065 		unsigned char max_p = mt_pivots[mt];
3066 		unsigned char max_s = mt_slots[mt];
3072 		if (tmp < mt_slots[mt])
3076 		ma_set_meta(node, mt, 0, tmp - 1);
3084 		ma_set_meta(left, mt, 0, split);
3091 	mas->node = mt_mk_node(newnode, mt);
3092 	ma_set_meta(newnode, mt, 0, tmp);
3096 	mt = mte_node_type(l_mas.node);
3097 	slots = ma_slots(new_left, mt);
3098 	pivs = ma_pivots(new_left, mt);
3101 	ma_set_meta(new_left, mt, 0, split);
3102 	l_mas.node = mt_mk_node(new_left, mt);
3106 	mt = mas_parent_type(&l_mas, l_mas.node);
3108 	slots = ma_slots(parent, mt);
3109 	pivs = ma_pivots(parent, mt);
3114 	eparent = mt_mk_node(parent, mt);
4373 	enum maple_type mt;
4402 	mt = mte_node_type(mas->node);
4405 		slots = ma_slots(node, mt);
4410 		mt = mte_node_type(mas->node);
4412 		pivots = ma_pivots(node, mt);
4413 		offset = ma_data_end(node, mt, pivots, max);
4418 	slots = ma_slots(node, mt);
4420 	pivots = ma_pivots(node, mt);
4546 	enum maple_type mt;
4564 		mt = mte_node_type(mas->node);
4565 		pivots = ma_pivots(node, mt);
4566 		node_end = ma_data_end(node, mt, pivots, mas->max);
4572 	slots = ma_slots(node, mt);
4585 		mt = mte_node_type(mas->node);
4586 		slots = ma_slots(node, mt);
4593 		pivots = ma_pivots(node, mt);
4595 	mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt);
4597 	mt = mte_node_type(enode);
4598 	pivots = ma_pivots(tmp, mt);
4599 	mas->end = ma_data_end(tmp, mt, pivots, mas->max);
5049 	enum maple_type mt;
5082 	mt = mte_node_type(mas->node);
5083 	pivots = ma_pivots(node, mt);
5088 	mas->end = ma_data_end(node, mt, pivots, mas->max);
5165 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt,
5174 		entry = mt_slot(mt, slots, offset);
5261 	struct maple_tree *mt, struct maple_enode *prev, unsigned char offset)
5274 		next = mt_slot_locked(mt, slots, next_offset);
5276 			next = mt_slot_locked(mt, slots, ++next_offset);
5290 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
5303 	slots = mte_destroy_descend(&enode, mt, start, 0);
5310 		node->slot_len = mte_dead_leaves(enode, mt, slots);
5323 		tmp = mt_slot_locked(mt, slots, offset);
5327 			slots = mte_destroy_descend(&enode, mt, parent, offset);
5334 	node->slot_len = mte_dead_leaves(enode, mt, slots);
5342 		mt_clear_meta(mt, node, node->type);
5348  * @mt: the tree to free - needed for node types.
5353 				    struct maple_tree *mt)
5357 	if (mt_in_rcu(mt)) {
5358 		mt_destroy_walk(enode, mt, false);
5361 		mt_destroy_walk(enode, mt, true);
5789  * @mt: The maple tree
5799 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)
5802 	MA_STATE(mas, mt, index, index);
5919  * @mt: The maple tree
5929 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)
5932 	MA_STATE(mas, mt, index, index);
6312  * @mt: The maple tree
6317 void *mtree_load(struct maple_tree *mt, unsigned long index)
6319 	MA_STATE(mas, mt, index, index);
6350  * @mt: The maple tree
6359 int mtree_store_range(struct maple_tree *mt, unsigned long index,
6362 	MA_STATE(mas, mt, index, last);
6372 	mtree_lock(mt);
6378 	mtree_unlock(mt);
6388  * @mt: The maple tree
6396 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry,
6399 	return mtree_store_range(mt, index, index, entry, gfp);
6405  * @mt: The maple tree
6414 int mtree_insert_range(struct maple_tree *mt, unsigned long first,
6417 	MA_STATE(ms, mt, first, last);
6425 	mtree_lock(mt);
6431 	mtree_unlock(mt);
6441  * @mt: The maple tree
6449 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry,
6452 	return mtree_insert_range(mt, index, index, entry, gfp);
6456 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
6462 	MA_STATE(mas, mt, 0, 0);
6463 	if (!mt_is_alloc(mt))
6469 	mtree_lock(mt);
6489 	mtree_unlock(mt);
6496  * @mt: The maple tree.
6504  * Finds an empty entry in @mt after @next, stores the new index into
6507  * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag.
6509  * Context: Any context.  Takes and releases the mt.lock.  May sleep if
6514  * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no
6517 int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp,
6523 	MA_STATE(mas, mt, 0, 0);
6525 	if (!mt_is_alloc(mt))
6529 	mtree_lock(mt);
6532 	mtree_unlock(mt);
6537 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
6543 	MA_STATE(mas, mt, 0, 0);
6544 	if (!mt_is_alloc(mt))
6550 	mtree_lock(mt);
6570 	mtree_unlock(mt);
6577  * @mt: The maple tree
6585 void *mtree_erase(struct maple_tree *mt, unsigned long index)
6589 	MA_STATE(mas, mt, index, index);
6592 	mtree_lock(mt);
6594 	mtree_unlock(mt);
6795  * @mt: The source maple tree
6814 int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
6817 	MA_STATE(mas, mt, 0, 0);
6833  * @mt: The source maple tree
6851 int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)
6854 	MA_STATE(mas, mt, 0, 0);
6874  * @mt: The maple tree
6878 void __mt_destroy(struct maple_tree *mt)
6880 	void *root = mt_root_locked(mt);
6882 	rcu_assign_pointer(mt->ma_root, NULL);
6884 		mte_destroy_walk(root, mt);
6886 	mt->ma_flags = mt_attr(mt);
6892  * @mt: The maple tree
6896 void mtree_destroy(struct maple_tree *mt)
6898 	mtree_lock(mt);
6899 	__mt_destroy(mt);
6900 	mtree_unlock(mt);
6906  * @mt: The maple tree
6920 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)
6922 	MA_STATE(mas, mt, *index, *index);
6958 		if (MT_WARN_ON(mt, (*index) && ((*index) <= copy)))
6970  * @mt: The maple tree
6980 void *mt_find_after(struct maple_tree *mt, unsigned long *index,
6986 	return mt_find(mt, index, max);
7090 static void mt_dump_node(const struct maple_tree *mt, void *entry,
7129 static void mt_dump_range64(const struct maple_tree *mt, void *entry,
7159 			mt_dump_entry(mt_slot(mt, node->slot, i),
7162 			mt_dump_node(mt, mt_slot(mt, node->slot, i),
7182 static void mt_dump_arange64(const struct maple_tree *mt, void *entry,
7222 			mt_dump_entry(mt_slot(mt, node->slot, i),
7225 			mt_dump_node(mt, mt_slot(mt, node->slot, i),
7239 static void mt_dump_node(const struct maple_tree *mt, void *entry,
7257 			mt_dump_entry(mt_slot(mt, node->slot, i),
7263 		mt_dump_range64(mt, entry, min, max, depth, format);
7266 		mt_dump_arange64(mt, entry, min, max, depth, format);
7274 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format)
7276 	void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt));
7279 		 mt, mt->ma_flags, mt_height(mt), entry);
7283 		mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format);
7295 	enum maple_type mt = mte_node_type(mas->node);
7300 	unsigned long *pivots = ma_pivots(node, mt);
7303 	if (ma_is_dense(mt)) {
7316 	gaps = ma_gaps(node, mt);
7318 		p_end = mas_safe_pivot(mas, pivots, i, mt);
7346 	if (mt == maple_arange_64) {
7529 static void mt_validate_nulls(struct maple_tree *mt)
7534 	MA_STATE(mas, mt, 0, 0);
7550 		MT_BUG_ON(mt, !last && !entry);
7571 void mt_validate(struct maple_tree *mt)
7575 	MA_STATE(mas, mt, 0, 0);
7595 		if (mt_is_alloc(mt))
7599 	mt_validate_nulls(mt);