Lines Matching refs:mt
176 static void mt_set_height(struct maple_tree *mt, unsigned char height) in mt_set_height() argument
178 unsigned int new_flags = mt->ma_flags; in mt_set_height()
181 MT_BUG_ON(mt, height > MAPLE_HEIGHT_MAX); in mt_set_height()
183 mt->ma_flags = new_flags; in mt_set_height()
191 static inline unsigned int mt_attr(struct maple_tree *mt) in mt_attr() argument
193 return mt->ma_flags & ~MT_FLAGS_HEIGHT_MASK; in mt_attr()
324 const enum maple_type mt) in ma_init_slot() argument
327 RCU_INIT_POINTER(*slot, (void *)mt_mk_node(mn, mt)); in ma_init_slot()
365 static __always_inline bool mt_is_alloc(struct maple_tree *mt) in mt_is_alloc() argument
367 return (mt->ma_flags & MT_FLAGS_ALLOC_RANGE); in mt_is_alloc()
644 static inline void __rcu **ma_slots(struct maple_node *mn, enum maple_type mt) in ma_slots() argument
646 switch (mt) { in ma_slots()
661 static inline bool mt_write_locked(const struct maple_tree *mt) in mt_write_locked() argument
663 return mt_external_lock(mt) ? mt_write_lock_is_held(mt) : in mt_write_locked()
664 lockdep_is_held(&mt->ma_lock); in mt_write_locked()
667 static __always_inline bool mt_locked(const struct maple_tree *mt) in mt_locked() argument
669 return mt_external_lock(mt) ? mt_lock_is_held(mt) : in mt_locked()
670 lockdep_is_held(&mt->ma_lock); in mt_locked()
673 static __always_inline void *mt_slot(const struct maple_tree *mt, in mt_slot() argument
676 return rcu_dereference_check(slots[offset], mt_locked(mt)); in mt_slot()
679 static __always_inline void *mt_slot_locked(struct maple_tree *mt, in mt_slot_locked() argument
682 return rcu_dereference_protected(slots[offset], mt_write_locked(mt)); in mt_slot_locked()
723 static inline void *mt_root_locked(struct maple_tree *mt) in mt_root_locked() argument
725 return rcu_dereference_protected(mt->ma_root, mt_write_locked(mt)); in mt_root_locked()
740 enum maple_type mt) in ma_meta() argument
742 switch (mt) { in ma_meta()
757 static inline void ma_set_meta(struct maple_node *mn, enum maple_type mt, in ma_set_meta() argument
760 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta()
772 static inline void mt_clear_meta(struct maple_tree *mt, struct maple_node *mn, in mt_clear_meta() argument
785 next = mt_slot_locked(mt, slots, in mt_clear_meta()
809 enum maple_type mt) in ma_meta_end() argument
811 struct maple_metadata *meta = ma_meta(mn, mt); in ma_meta_end()
831 static inline void ma_set_meta_gap(struct maple_node *mn, enum maple_type mt, in ma_set_meta_gap() argument
835 struct maple_metadata *meta = ma_meta(mn, mt); in ma_set_meta_gap()
898 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt,
1157 struct maple_tree *mt = mas->tree; in mas_lockdep_map() local
1159 if (mt_external_lock(mt)) in mas_lockdep_map()
1160 return mt->ma_external_lock; in mas_lockdep_map()
1162 return &(mt->ma_lock).dep_map; in mas_lockdep_map()
1378 enum maple_type mt, unsigned long min, unsigned long max, in ma_leaf_max_gap() argument
1386 if (unlikely(ma_is_dense(mt))) { in ma_leaf_max_gap()
1388 for (i = 0; i < mt_slots[mt]; i++) { in ma_leaf_max_gap()
1414 max_piv = ma_data_end(mn, mt, pivots, max) - 1; in ma_leaf_max_gap()
1452 enum maple_type mt; in mas_leaf_max_gap() local
1458 mt = mte_node_type(mas->node); in mas_leaf_max_gap()
1459 slots = ma_slots(mn, mt); in mas_leaf_max_gap()
1460 pivots = ma_pivots(mn, mt); in mas_leaf_max_gap()
1462 return ma_leaf_max_gap(mn, mt, mas->min, mas->max, pivots, slots); in mas_leaf_max_gap()
1477 ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, in ma_max_gap() argument
1483 i = offset = ma_meta_end(node, mt); in ma_max_gap()
1505 enum maple_type mt; in mas_max_gap() local
1508 mt = mte_node_type(mas->node); in mas_max_gap()
1509 if (ma_is_leaf(mt)) in mas_max_gap()
1513 MAS_BUG_ON(mas, mt != maple_arange_64); in mas_max_gap()
1515 gaps = ma_gaps(node, mt); in mas_max_gap()
1679 enum maple_type mt; in mas_find_child() local
1687 mt = mte_node_type(mas->node); in mas_find_child()
1689 slots = ma_slots(node, mt); in mas_find_child()
1690 pivots = ma_pivots(node, mt); in mas_find_child()
1691 end = ma_data_end(node, mt, pivots, mas->max); in mas_find_child()
1713 enum maple_type mt, unsigned char end) in mas_leaf_set_meta() argument
1715 if (end < mt_slots[mt] - 1) in mas_leaf_set_meta()
1716 ma_set_meta(node, mt, 0, end); in mas_leaf_set_meta()
2039 void node_finalise(struct maple_node *node, enum maple_type mt, in node_finalise() argument
2042 unsigned char max_end = mt_slots[mt]; in node_finalise()
2047 gaps = ma_gaps(node, mt); in node_finalise()
2050 memset(ma_slots(node, mt) + end, 0, size * sizeof(void *)); in node_finalise()
2056 memset(ma_pivots(node, mt) + end, 0, size * sizeof(unsigned long)); in node_finalise()
2060 if (gaps && !ma_is_leaf(mt)) { in node_finalise()
2071 if (mt == maple_arange_64) in node_finalise()
2072 ma_set_meta(node, mt, gap_slot, end - 1); in node_finalise()
2074 ma_set_meta(node, mt, gap_slot, end - 1); in node_finalise()
2359 void dst_setup(struct maple_copy *cp, struct ma_state *mas, enum maple_type mt) in dst_setup() argument
2363 if (cp->data <= mt_slots[mt]) { in dst_setup()
2371 if (cp->data < mt_slots[mt] * 2) in dst_setup()
2374 if (cp->data == mt_slots[mt] * 2) { in dst_setup()
2378 if (!ma_is_leaf(mt)) in dst_setup()
2398 if (ma_slots(cp->src[s].node, cp->src[s].mt)[off]) in dst_setup()
2402 if (cp->split < mt_slots[mt]) in dst_setup()
2406 if (cp->data - 2 - cp->split < mt_slots[mt]) in dst_setup()
2417 cp->dst[i].mt = mt; in dst_setup()
2426 enum maple_type mt; in append_mas_cp() local
2431 mt = mte_node_type(mas->node); in append_mas_cp()
2433 cp->src[count].mt = mt; in append_mas_cp()
2437 cp->src[count].max = ma_pivots(node, mt)[end]; in append_mas_cp()
2451 cp->src[count].mt = wr_mas->type; in append_wr_mas_cp()
2465 cp->src[cp->s_count].mt = maple_copy; in init_cp_src()
2530 s_mt = cp->src[s].mt; in cp_data_write()
2531 d_mt = cp->dst[d].mt; in cp_data_write()
2536 d_mt = cp->dst[d].mt; in cp_data_write()
2565 s_mt = cp->src[s].mt; in cp_data_write()
2582 s_mt = cp->src[s].mt; in cp_data_write()
2623 enum maple_type mt = cp->dst[d].mt; in cp_dst_to_slots() local
2632 ma_init_slot(&cp->slot[d], mn, mt); in cp_dst_to_slots()
2635 if (ma_is_leaf(mt)) { in cp_dst_to_slots()
2636 cp->gap[d] = ma_leaf_max_gap(mn, mt, slot_min, in cp_dst_to_slots()
2637 slot_max, ma_pivots(mn, mt), in cp_dst_to_slots()
2638 ma_slots(mn, mt)); in cp_dst_to_slots()
2640 unsigned long *gaps = ma_gaps(mn, mt); in cp_dst_to_slots()
2664 enum maple_type mt = maple_arange_64; in cp_is_new_root() local
2667 mt = maple_range_64; in cp_is_new_root()
2671 dst_setup(cp, mas, mt); in cp_is_new_root()
2674 cp->dst[0].node, 0, mt); in cp_is_new_root()
2675 node_finalise(cp->dst[0].node, mt, cp->end + 1); in cp_is_new_root()
2682 ma_init_slot(&cp->slot[0], cp->dst[0].node, mt); in cp_is_new_root()
3954 enum maple_type mt; in mas_prev_node() local
3983 mt = mte_node_type(mas->node); in mas_prev_node()
3986 slots = ma_slots(node, mt); in mas_prev_node()
3991 mt = mte_node_type(mas->node); in mas_prev_node()
3993 pivots = ma_pivots(node, mt); in mas_prev_node()
3994 offset = ma_data_end(node, mt, pivots, max); in mas_prev_node()
3999 slots = ma_slots(node, mt); in mas_prev_node()
4001 pivots = ma_pivots(node, mt); in mas_prev_node()
4124 enum maple_type mt; in mas_next_node() local
4142 mt = mte_node_type(mas->node); in mas_next_node()
4143 pivots = ma_pivots(node, mt); in mas_next_node()
4144 node_end = ma_data_end(node, mt, pivots, mas->max); in mas_next_node()
4150 slots = ma_slots(node, mt); in mas_next_node()
4163 mt = mte_node_type(mas->node); in mas_next_node()
4164 slots = ma_slots(node, mt); in mas_next_node()
4171 pivots = ma_pivots(node, mt); in mas_next_node()
4173 mas->max = mas_safe_pivot(mas, pivots, mas->offset, mt); in mas_next_node()
4175 mt = mte_node_type(enode); in mas_next_node()
4176 pivots = ma_pivots(tmp, mt); in mas_next_node()
4177 mas->end = ma_data_end(tmp, mt, pivots, mas->max); in mas_next_node()
4598 enum maple_type mt; in mas_empty_area() local
4628 mt = mte_node_type(mas->node); in mas_empty_area()
4629 pivots = ma_pivots(node, mt); in mas_empty_area()
4634 mas->end = ma_data_end(node, mt, pivots, mas->max); in mas_empty_area()
4711 unsigned char mte_dead_leaves(struct maple_enode *enode, struct maple_tree *mt, in mte_dead_leaves() argument
4720 entry = mt_slot(mt, slots, offset); in mte_dead_leaves()
4807 struct maple_tree *mt, struct maple_enode *prev, unsigned char offset) in mte_destroy_descend() argument
4820 next = mt_slot_locked(mt, slots, next_offset); in mte_destroy_descend()
4822 next = mt_slot_locked(mt, slots, ++next_offset); in mte_destroy_descend()
4836 static void mt_destroy_walk(struct maple_enode *enode, struct maple_tree *mt, in mt_destroy_walk() argument
4850 slots = mte_destroy_descend(&enode, mt, start, 0); in mt_destroy_walk()
4857 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
4870 tmp = mt_slot_locked(mt, slots, offset); in mt_destroy_walk()
4874 slots = mte_destroy_descend(&enode, mt, parent, offset); in mt_destroy_walk()
4881 node->slot_len = mte_dead_leaves(enode, mt, slots); in mt_destroy_walk()
4889 mt_clear_meta(mt, node, node->type); in mt_destroy_walk()
4900 struct maple_tree *mt) in mte_destroy_walk() argument
4904 if (mt_in_rcu(mt)) { in mte_destroy_walk()
4905 mt_destroy_walk(enode, mt, false); in mte_destroy_walk()
4908 mt_destroy_walk(enode, mt, true); in mte_destroy_walk()
5219 void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) in mt_next() argument
5222 MA_STATE(mas, mt, index, index); in mt_next()
5351 void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min) in mt_prev() argument
5354 MA_STATE(mas, mt, index, index); in mt_prev()
5803 void *mtree_load(struct maple_tree *mt, unsigned long index) in mtree_load() argument
5805 MA_STATE(mas, mt, index, index); in mtree_load()
5845 int mtree_store_range(struct maple_tree *mt, unsigned long index, in mtree_store_range() argument
5848 MA_STATE(mas, mt, index, last); in mtree_store_range()
5858 mtree_lock(mt); in mtree_store_range()
5860 mtree_unlock(mt); in mtree_store_range()
5876 int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, in mtree_store() argument
5879 return mtree_store_range(mt, index, index, entry, gfp); in mtree_store()
5897 int mtree_insert_range(struct maple_tree *mt, unsigned long first, in mtree_insert_range() argument
5900 MA_STATE(ms, mt, first, last); in mtree_insert_range()
5909 mtree_lock(mt); in mtree_insert_range()
5915 mtree_unlock(mt); in mtree_insert_range()
5934 int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, in mtree_insert() argument
5937 return mtree_insert_range(mt, index, index, entry, gfp); in mtree_insert()
5941 int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_range() argument
5947 MA_STATE(mas, mt, 0, 0); in mtree_alloc_range()
5948 if (!mt_is_alloc(mt)) in mtree_alloc_range()
5954 mtree_lock(mt); in mtree_alloc_range()
5974 mtree_unlock(mt); in mtree_alloc_range()
6003 int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_cyclic() argument
6009 MA_STATE(mas, mt, 0, 0); in mtree_alloc_cyclic()
6011 if (!mt_is_alloc(mt)) in mtree_alloc_cyclic()
6015 mtree_lock(mt); in mtree_alloc_cyclic()
6018 mtree_unlock(mt); in mtree_alloc_cyclic()
6023 int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, in mtree_alloc_rrange() argument
6029 MA_STATE(mas, mt, 0, 0); in mtree_alloc_rrange()
6030 if (!mt_is_alloc(mt)) in mtree_alloc_rrange()
6036 mtree_lock(mt); in mtree_alloc_rrange()
6056 mtree_unlock(mt); in mtree_alloc_rrange()
6076 void *mtree_erase(struct maple_tree *mt, unsigned long index) in mtree_erase() argument
6080 MA_STATE(mas, mt, index, index); in mtree_erase()
6084 mtree_lock(mt); in mtree_erase()
6086 mtree_unlock(mt); in mtree_erase()
6312 int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in __mt_dup() argument
6315 MA_STATE(mas, mt, 0, 0); in __mt_dup()
6349 int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp) in mtree_dup() argument
6352 MA_STATE(mas, mt, 0, 0); in mtree_dup()
6376 void __mt_destroy(struct maple_tree *mt) in __mt_destroy() argument
6378 void *root = mt_root_locked(mt); in __mt_destroy()
6380 rcu_assign_pointer(mt->ma_root, NULL); in __mt_destroy()
6382 mte_destroy_walk(root, mt); in __mt_destroy()
6384 mt->ma_flags = mt_attr(mt); in __mt_destroy()
6394 void mtree_destroy(struct maple_tree *mt) in mtree_destroy() argument
6396 mtree_lock(mt); in mtree_destroy()
6397 __mt_destroy(mt); in mtree_destroy()
6398 mtree_unlock(mt); in mtree_destroy()
6418 void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max) in mt_find() argument
6420 MA_STATE(mas, mt, *index, *index); in mt_find()
6456 if (MT_WARN_ON(mt, (*index) && ((*index) <= copy))) in mt_find()
6478 void *mt_find_after(struct maple_tree *mt, unsigned long *index, in mt_find_after() argument
6484 return mt_find(mt, index, max); in mt_find_after()
6601 static void mt_dump_node(const struct maple_tree *mt, void *entry,
6640 static void mt_dump_range64(const struct maple_tree *mt, void *entry, in mt_dump_range64() argument
6670 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_range64()
6673 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_range64()
6693 static void mt_dump_arange64(const struct maple_tree *mt, void *entry, in mt_dump_arange64() argument
6732 mt_dump_node(mt, mt_slot(mt, node->slot, i), in mt_dump_arange64()
6752 static void mt_dump_node(const struct maple_tree *mt, void *entry, in mt_dump_node() argument
6770 mt_dump_entry(mt_slot(mt, node->slot, i), in mt_dump_node()
6776 mt_dump_range64(mt, entry, min, max, depth, format); in mt_dump_node()
6779 mt_dump_arange64(mt, entry, min, max, depth, format); in mt_dump_node()
6787 void mt_dump(const struct maple_tree *mt, enum mt_dump_format format) in mt_dump() argument
6789 void *entry = rcu_dereference_check(mt->ma_root, mt_locked(mt)); in mt_dump()
6792 mt, mt->ma_flags, mt_height(mt), entry); in mt_dump()
6794 mt_dump_node(mt, entry, 0, mt_node_max(entry), 0, format); in mt_dump()
6810 enum maple_type mt = mte_node_type(mas->node); in mas_validate_gaps() local
6815 unsigned long *pivots = ma_pivots(node, mt); in mas_validate_gaps()
6818 if (ma_is_dense(mt)) { in mas_validate_gaps()
6831 gaps = ma_gaps(node, mt); in mas_validate_gaps()
6833 p_end = mas_safe_pivot(mas, pivots, i, mt); in mas_validate_gaps()
6861 if (mt == maple_arange_64) { in mas_validate_gaps()
7044 static void mt_validate_nulls(struct maple_tree *mt) in mt_validate_nulls() argument
7049 MA_STATE(mas, mt, 0, 0); in mt_validate_nulls()
7065 MT_BUG_ON(mt, !last && !entry); in mt_validate_nulls()
7086 void mt_validate(struct maple_tree *mt) in mt_validate() argument
7091 MA_STATE(mas, mt, 0, 0); in mt_validate()
7111 if (mt_is_alloc(mt)) in mt_validate()
7115 mt_validate_nulls(mt); in mt_validate()