From 178d4a86655d32bbcb95ae41d1c2830801403ee5 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 26 Jul 2019 20:31:30 -0400 Subject: [PATCH] maple_tree: mas_next_node/mas_prev_node restarts added on dead node detection. Also required reordering some functions. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 414 ++++++++++++++++++++++++----------------------- 1 file changed, 213 insertions(+), 201 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 66cc6ff3da66..5abe5e5eec30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -16,7 +16,6 @@ #define ma_mnode_ptr(x) ((struct maple_node*)(x)) #define ma_enode_ptr(x) ((struct maple_enode*)(x)) - static struct kmem_cache *maple_node_cache; unsigned long mt_max[] = { @@ -320,6 +319,13 @@ static inline struct maple_node *mt_parent(const struct maple_enode *node) } +static inline bool mt_dead_node(const struct maple_enode *enode) +{ + struct maple_node *parent, *node = mt_to_node(enode); + parent = mt_parent(enode); + return (parent == node); +} + static inline struct maple_node *ma_get_alloc(const struct ma_state *ms) { return (struct maple_node *)((unsigned long)ms->alloc & ~0x7F); @@ -509,7 +515,7 @@ static inline struct maple_enode *_ma_get_rcu_slot( { struct maple_enode *p = __ma_get_rcu_slot(mn, slot, type); - if ((void*)mt_parent(mn) == mn) // dead node. + if (mt_dead_node(mn)) return NULL; return p; } @@ -1171,152 +1177,6 @@ static inline void ma_update_gap(struct ma_state *mas) ma_parent_gap(mas, pslot, max_gap); } -/* - * Find the prev non-null entry at the same level in the tree. The prev value - * will be mas->node[ma_get_slot(mas)] or MAS_NONE. - * - * - * FIXME: Restart from top with dead node, mas_walk to mas->min - 1. - */ -static inline void mas_prev_node (struct ma_state *mas, unsigned long min) -{ - int level = 0; - unsigned char slot = ma_get_slot(mas); - - if (ma_is_root(mas->node)) - goto no_entry; - - while (1) { - unsigned char count; - - ma_encoded_parent(mas); - level++; - - if (!slot) - goto ascend; - - slot--; - count = mt_slot_count(mas->node); - do { - struct maple_enode *mn; - unsigned long pivot; - unsigned long last_pivot; - - if (slot >= count - 1) - pivot = mas->max; - else - pivot = ma_get_pivot(mas->node, slot); - - if (pivot < min) - goto no_entry; - - if (slot != 0 && pivot == 0) - break; - - mn = ma_get_rcu_slot(mas->node, slot); - if (!mn) - continue; - - if (level == 1) { - ma_set_slot(mas, slot); - if (!mt_is_leaf(mas->node)) { - mas->node = mn; - } - return; - } - - level--; - mas->node = mn; - slot = ma_data_end(mas, mt_node_type(mn), &last_pivot); - count = mt_slot_count(mas->node); - } while(slot-- > 0); - -ascend: - if (ma_is_root(mas->node)) - goto no_entry; - - slot = mt_parent_slot(mas->node); - } - -no_entry: - mas->node = MAS_NONE; -} - -/* - * Find the next non-null entry at the same level in the tree. The next value - * will be mas->node[ma_get_slot(mas)] or MAS_NONE. - * - * FIXME: Restart from top with dead node, mas_walk to mas->max - 1. - */ -static inline unsigned long -mas_next_node (struct ma_state *mas, unsigned long max) -{ - int level = 0; - - while (1) { - unsigned char count, slot; - struct maple_enode *mn; - unsigned long prev_piv; - - mn = mas->node; - slot = ma_get_slot(mas); - level++; - if (!ma_is_root(mas->node)) - ma_encoded_parent(mas); - - if (mas->node == mn) // Dead node. - goto restart; - - count = mt_slot_count(mas->node); - - prev_piv = ma_get_safe_pivot(mas, slot); - - while (++slot < count) { - unsigned long pivot = mas->max; - - if (slot < count - 1) - pivot = ma_get_pivot(mas->node, slot); - - if (prev_piv > max) - goto no_entry; - - if (slot != 0 && pivot == 0) - break; - - mn = ma_get_rcu_slot(mas->node, slot); - if (!mn) { - prev_piv = pivot; - continue; - } - - mas->min = prev_piv + 1; - mas->max = pivot; - - if (level == 1) { - ma_set_slot(mas, slot); - mas->node = mn; - return pivot; - } - - level--; - mas->node = mn; - slot = -1; - count = mt_slot_count(mas->node); - } - - if (ma_is_root(mas->node)) - goto no_entry; - } - -no_entry: - mas->node = MAS_NONE; - return mas->max; -restart: - /* FIXME */ - mas->node = MAS_NONE; - return mas->max; - -} // First non-null entry in mas->node static inline unsigned long @@ -1367,59 +1227,6 @@ mas_first_entry (struct ma_state *mas, unsigned long max) } } -// Next node entry or return 0 on none. -static inline unsigned long -mas_next_nentry (struct ma_state *mas, unsigned long max) -{ - unsigned long pivot = 0; - unsigned char slot = ma_get_slot(mas); - unsigned char count = mt_slot_count(mas->node); - void *entry; - - while (slot++ < count) { - pivot = mas->max; - if (slot < count - 1) - pivot = ma_get_pivot(mas->node, slot); - - if (pivot > max) - goto no_entry; - - if (slot != 0 && pivot == 0) - goto no_entry; - - entry = ma_get_rcu_slot(mas->node, slot); - if (entry) - break; - } - ma_set_slot(mas, slot); - return pivot; - -no_entry: - return 0; -} -static inline unsigned long -mas_next_entry (struct ma_state *mas, unsigned long max) -{ - unsigned long pivot = max; - - if (mas->node == MAS_NONE) - return max; - - if (!mt_is_leaf(mas->node)) - pivot = mas_first_entry(mas, max); - else { - while (mas->node != MAS_NONE) { - unsigned char p_slot; - pivot = mas_next_nentry(mas, max); - if (pivot) - break; - p_slot = mt_parent_slot(mas->node); - ma_set_slot(mas, p_slot); - mas_next_node(mas, max); - } - } - return pivot; -} static inline void mas_prev_entry (struct ma_state *mas) { } @@ -2575,6 +2382,211 @@ static inline bool _mas_walk(struct ma_state *mas) ma_set_slot(mas, 0); return __mas_walk(mas); } +static inline int mas_dead_node(struct ma_state *mas, unsigned long index) +{ + if (!mt_dead_node(mas->node)) + return 0; + + mas->index = index; + _mas_walk(mas); + return 1; +} +/* + * Find the prev non-null entry at the same level in the tree. The prev value + * will be mas->node[ma_get_slot(mas)] or MAS_NONE. + * + */ +static inline void mas_prev_node (struct ma_state *mas, unsigned long min) +{ + int level; + unsigned char slot; + unsigned long start_piv; + +restart_prev_node: + level = 0; + slot = ma_get_slot(mas); + start_piv = ma_get_safe_pivot(mas, slot); + if (ma_is_root(mas->node)) + goto no_entry; + + while (1) { + ma_encoded_parent(mas); + level++; + + if (mas_dead_node(mas, start_piv)) + goto restart_prev_node; + + if (!slot) + goto ascend; + + slot--; + do { + struct maple_enode *mn; + unsigned long last_pivot; + unsigned long pivot = ma_get_safe_pivot(mas, slot); + + if (pivot < min) + goto no_entry; + + if (slot != 0 && pivot == 0) + break; + + mn = ma_get_rcu_slot(mas->node, slot); + if (!mn) + continue; + + if (level == 1) { + ma_set_slot(mas, slot); + mas->node = mn; + if (mas_dead_node(mas, start_piv)) + goto restart_prev_node; + return; + } + + level--; + mas->node = mn; + slot = ma_data_end(mas, mt_node_type(mn), &last_pivot); + } while(slot-- > 0); + +ascend: + if (ma_is_root(mas->node)) + goto no_entry; + + slot = mt_parent_slot(mas->node); + } + +no_entry: + mas->node = MAS_NONE; + return; +} + +/* + * Find the next non-null entry at the same level in the tree. The next value + * will be mas->node[ma_get_slot(mas)] or MAS_NONE. + * + */ +static inline unsigned long +mas_next_node (struct ma_state *mas, unsigned long max) +{ + int level; + unsigned long start_piv; + +restart_next_node: + level = 0; + while (1) { + unsigned char count, slot; + struct maple_enode *mn; + unsigned long prev_piv; + + mn = mas->node; + slot = ma_get_slot(mas); + start_piv = ma_get_safe_pivot(mas, slot); + level++; + if (!ma_is_root(mas->node)) + ma_encoded_parent(mas); + + if (mas_dead_node(mas, start_piv)) + goto restart_next_node; + + count = mt_slot_count(mas->node); + + prev_piv = ma_get_safe_pivot(mas, slot); + + while (++slot < count) { + unsigned long pivot = ma_get_safe_pivot(mas, slot); + + if (prev_piv > max) + goto no_entry; + + if (slot != 0 && pivot == 0) + break; + + mn = ma_get_rcu_slot(mas->node, slot); + if (!mn) { + prev_piv = pivot; + continue; + } + + mas->min = prev_piv + 1; + mas->max = pivot; + + if (level == 1) { + ma_set_slot(mas, slot); + mas->node = mn; + if (mas_dead_node(mas, start_piv)) + goto restart_next_node; + return pivot; + } + + level--; + mas->node = mn; + slot = -1; + count = mt_slot_count(mas->node); + } + + if (ma_is_root(mas->node)) + goto no_entry; + } + +no_entry: + mas->node = MAS_NONE; + return mas->max; + +} + +// Next node entry or return 0 on none. +static inline unsigned long +mas_next_nentry (struct ma_state *mas, unsigned long max) +{ + unsigned long pivot = 0; + unsigned char slot = ma_get_slot(mas); + unsigned char count = mt_slot_count(mas->node); + void *entry; + + while (slot++ < count) { + pivot = mas->max; + if (slot < count - 1) + pivot = ma_get_pivot(mas->node, slot); + + if (pivot > max) + goto no_entry; + + if (slot != 0 && pivot == 0) + goto no_entry; + + entry = ma_get_rcu_slot(mas->node, slot); + if (entry) + break; + } + ma_set_slot(mas, slot); + return pivot; + +no_entry: + return 0; +} +static inline unsigned long +mas_next_entry (struct ma_state *mas, unsigned long max) +{ + unsigned long pivot = max; + + if (mas->node == MAS_NONE) + return max; + + if (!mt_is_leaf(mas->node)) + pivot = mas_first_entry(mas, max); + else { + while (mas->node != MAS_NONE) { + unsigned char p_slot; + pivot = mas_next_nentry(mas, max); + if (pivot) + break; + p_slot = mt_parent_slot(mas->node); + ma_set_slot(mas, p_slot); + mas_next_node(mas, max); + } + } + return pivot; +} static inline void ma_inactive_insert(struct ma_state *mas, void *entry); static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) { -- 2.50.1