From a8355cd44e5668cd58a51577a7c779eb7455e069 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 17 Jul 2020 17:04:07 -0400 Subject: [PATCH] maple_tree: Comments. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 136 +++++++++++++++++++++++++++++++---------------- 1 file changed, 91 insertions(+), 45 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index aa80bae43718..be68f2890701 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -164,7 +164,7 @@ static inline bool mte_is_leaf(const struct maple_enode *entry) return ma_is_leaf(mte_node_type(entry)); } -/* Private +/** Private * We also reserve values with the bottom two bits set to '10' which are * below 4096 */ @@ -316,7 +316,7 @@ static inline enum maple_type mas_parent_enum(struct ma_state *mas, return mte_parent_range_enum(parent); } -/* Private +/** Private * * Type is encoded in the node->parent * bit 0: 1 = root, 0 otherwise @@ -993,7 +993,7 @@ void mas_empty_alloc(struct ma_state *mas) ma_free_alloc(node); mas->alloc = NULL; } -/* Private +/** Private * Check if there was an error allocating and do the allocation if necessary * If there are allocations, then free them. */ @@ -1215,7 +1215,7 @@ ascend: slot = mte_parent_slot(gaps.node); goto ascend; } -/* Private +/** Private * mas_update_gap() - Update a nodes gaps and propagate up if necessary. * * @mas - the maple state. @@ -1246,7 +1246,7 @@ static inline void mas_update_gap(struct ma_state *mas) } -/* Private +/** Private * mas_first_node() - Finds the first node in mas->node and returns the pivot, * mas->max if no node is found. Node is returned as mas->node which may be * MAS_NONE. @@ -1607,6 +1607,14 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, } } +/** Private + * mas_descend_adopt() - Descend through a sub-tree and adopt children who do + * not have the correct parents set. Follow the parents which have the correct + * parents as they are the new entries which need to be followed to find other + * incorrectly set parents. + * + * @mas: the maple state with the maple encoded node of the sub-tree. + */ static inline void mas_descend_adopt(struct ma_state *mas) { struct maple_enode *l_enode, *r_enode; @@ -1617,12 +1625,6 @@ static inline void mas_descend_adopt(struct ma_state *mas) mas_dup_state(&l_mas, mas); mas_dup_state(&r_mas, mas); - /* The new nodes have the correct parent set, so follow the child with - * the correct parent on each split. If there is no child with the - * correct parent, then the other side of the split will have two - * children with the correct parent. Once the new children are found, - * then set the correct parent in all of of the parent's children. - */ while (!mte_is_leaf(l_mas.node)) { if (!(l_enode = mas_find_l_split(&l_mas))) { mas_adopt_children(&l_mas, l_mas.node); @@ -1648,7 +1650,15 @@ static inline void mas_descend_adopt(struct ma_state *mas) } } - +/** Private + * mas_store_b_node() - Store an @entry into the b_node while also copying the + * data from a maple encoded node. + * + * @mas: the maple state + * @b_node: the maple_big_node to fill with data + * @entry: the data to store. + * Returns: The actual end of the data stored in @b_node + */ static inline unsigned char mas_store_b_node(struct ma_state *mas, struct maple_big_node *b_node, void *entry) @@ -1704,6 +1714,12 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, static inline bool mas_node_walk(struct ma_state *mas, enum maple_type type, unsigned long *range_min, unsigned long *range_max); +/** Private + * mas_prev_sibling() - Find the previous node with the same parent. + * + * @mas: the maple state + * Returns: True if there is a previous sibling, false otherwise. + */ static inline bool mas_prev_sibling(struct ma_state *mas) { unsigned p_slot = mte_parent_slot(mas->node); @@ -1719,7 +1735,12 @@ static inline bool mas_prev_sibling(struct ma_state *mas) mas_descend(mas); return true; } + /** Private + * mas_next_sibling() - Find the next node with the same parent. + * + * @mas: the maple state + * Returns true if there is a next sibling, false otherwise. */ static inline bool mas_next_sibling(struct ma_state *mas) { @@ -1741,8 +1762,12 @@ static inline bool mas_next_sibling(struct ma_state *mas) mas_descend(mas); return true; } -/* mast_topiary() - Add the portions of the tree which will be replaced by the - * operation to the removal list; either to be @free or @discard (destroy walk). + +/** Private + * mast_topiary() - Add the portions of the tree to the removal list; either to + * be freed or discarded (destroy walk). + * + * @mast: The maple_subtree_state. */ static inline void mast_topiary(struct maple_subtree_state *mast) { @@ -1776,6 +1801,12 @@ static inline void mast_topiary(struct maple_subtree_state *mast) mat_add(mast->destroy, mas_get_rcu_slot(mast->orig_r, slot)); } +/** Private + * mast_rebalance_from_siblings() - Rebalance from nodes with the same parents. + * Check the right side, then the left. Data is copied into the @mast->bn. + * + * @mast: The maple_subtree_state. + */ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast) { unsigned char end; @@ -1794,9 +1825,7 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast if (mas_prev_sibling(mast->orig_l)) { unsigned char b_end = mast->bn->b_end; end = mas_data_end(mast->orig_l); - // shift mast->bn by prev size mab_shift_right(mast->bn, end + 1); - // copy in prev. mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); mat_add(mast->free, left); if (right == left) @@ -1813,6 +1842,12 @@ static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast static inline void mas_prev_node(struct ma_state *mas, unsigned long limit); static inline unsigned long mas_next_node(struct ma_state *mas, unsigned long max); +/** Private + * mast_rebalance_from_cousins() - Rebalance from nodes with different parents. + * Check the right side, then the left. Data is copied into the @mast->bn. + * + * @mast: The maple_subtree_state. + */ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) { unsigned char end, b_end; @@ -1831,14 +1866,11 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) mast->orig_l->node = mast->orig_r->node; return true; } - // Put left into right. mas_dup_state(mast->orig_r, mast->orig_l); mas_dup_state(mast->r, mast->l); - // Use prev for left. mas_prev_node(mast->orig_l, 0); if (mas_is_none(mast->orig_l)) { - // This is going to be a new root of - // only what is in mast->bn + // This is going to be a new root with the contents of mast->bn mas_dup_state(mast->orig_l, mast->orig_r); mast->bn->b_end--; return false; @@ -1852,21 +1884,19 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) mast->orig_l->index = mast->orig_l->min; end = mas_data_end(mast->orig_l); b_end = mast->bn->b_end; - // shift mast->bn mab_shift_right(mast->bn, end + 1); - // copy in prev. mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); mast->l->min = mast->orig_l->min; mast->bn->b_end = b_end + end + 1; mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); return true; } -/* Private - * mast_ascend_free() - ascend orig_l and orig_r and add the child nodes to the - * free list. Set the slots to point to the correct location in the parents of - * those children. +/** Private + * mast_ascend_free() - ascend the original left and right sides and add the + * previous nodes to the free list. Set the slots to point to the correct location + * in the new nodes. * - * @mast - the maple subtree state. + * @mast: the maple subtree state. */ static inline void mast_ascend_free(struct maple_subtree_state *mast) @@ -1901,22 +1931,29 @@ mast_ascend_free(struct maple_subtree_state *mast) &range_min, &range_max); } +/** Private + * mas_new_ma_node() - Create and return a new maple node. Helper function. + * + * @mas: the maple state with the allocations. + * @b_node: the maple_big_node with the type encoding. + * Returns: A new maple encoded node + */ static inline struct maple_enode *mas_new_ma_node(struct ma_state *mas, struct maple_big_node *b_node) { return mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), b_node->type); } -/* Private +/** Private * mas_mab_to_node() - Set up right and middle nodes * - * @mas - the maple state that contains the allocations. - * @b_node - the node which contains the data. - * @left - The pointer which will have the left node - * @right - The pointer which may have the right node - * @middle - the pointer which may have the middle node (rare) - * @mid_split - the split location for the middle node + * @mas: the maple state that contains the allocations. + * @b_node: the node which contains the data. + * @left: The pointer which will have the left node + * @right: The pointer which may have the right node + * @middle: the pointer which may have the middle node (rare) + * @mid_split: the split location for the middle node * - * returns the split of left. + * Returns: the split of left. */ static inline unsigned char mas_mab_to_node(struct ma_state *mas, struct maple_big_node *b_node, @@ -1947,7 +1984,7 @@ static inline unsigned char mas_mab_to_node(struct ma_state *mas, } -/* Private +/** Private * mab_set_b_end() - Add entry to b_node at b_node->b_end and increment the end * pointer. * @b_node - the big node to add the entry @@ -1967,7 +2004,7 @@ static inline void mab_set_b_end(struct maple_big_node *b_node, b_node->pivot[b_node->b_end++] = mas->max; } -/* Private +/** Private * mas_set_split_parent() - combine_separate helper function. Sets the parent * of @mas->node to either @left or @right, depending on @slot and @split * @@ -1993,6 +2030,15 @@ static inline void mas_set_split_parent(struct ma_state *mas, (*slot)++; } +/** Private + * mast_set_split_parents() - Helper function to set three nodes parents. Slot + * is taken from @mast->l. + * + * @mast - the maple subtree state + * @left - the left node + * @right - the right node + * @split - the split location. + */ static inline void mast_set_split_parents(struct maple_subtree_state *mast, struct maple_enode *left, struct maple_enode *right, @@ -2125,7 +2171,7 @@ static inline void mast_setup_bnode_for_split(struct maple_subtree_state *mast) mast->bn->type = mte_node_type(mast->orig_l->node); } -/* Private +/** Private * * mas_combine_separate() - Follow the tree upwards from @l_mas and @r_mas for * @count, or until the root is hit. First @b_node is split into two entries @@ -2493,7 +2539,7 @@ exists: mas_set_err(mas, -EEXIST); return 0; } -/* Private +/** Private * * mas_is_span_() - Set span_enode if there is no value already and the * entry being written spans this nodes slot or touches the end of this slot and @@ -2599,7 +2645,7 @@ static inline void mas_cnt_empty(struct ma_state *mas) else mas->full_cnt--; } -/* Private +/** Private * * mas_wr_walk(): Walk the tree for a write. Tracks extra information which * is used in special cases of a write. @@ -2742,7 +2788,7 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, } return ret; } -/* Private +/** Private * * mas_spanning_store() - Create a subtree with the store operation completed * and new nodes where necessary, then place the sub-tree in the actual tree. @@ -3289,7 +3335,7 @@ found: mas_set_slot(mas, slot); return true; } -/* Private +/** Private * * Returns the pivot which points to the entry with the highest index. * @mas slot is set to the entry location. @@ -3390,7 +3436,7 @@ next_node: return entry; } -/* Private +/** Private * * _mas_prev() - Find the previous entry from the current ma state. * @mas the current maple state (must have a valid slot) @@ -4171,7 +4217,7 @@ void *mas_load(struct ma_state *mas) return mas_range_load(mas, &range_min, &range_max, true); } -/* Private +/** Private * * _mas_next() - Finds the next entry, sets index to the start of the range. * @@ -4282,7 +4328,7 @@ void *mas_next(struct ma_state *mas, unsigned long max) return _mas_next(mas, max, &index); } EXPORT_SYMBOL_GPL(mas_next); -/* Private +/** Private * mas_erase() - Find the range in which index resides and erase the entire * range. * -- 2.50.1