From 4d997da227ad61bf27c4f68d5e558601e9a70ca3 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 31 Oct 2019 10:42:09 -0400 Subject: [PATCH] maple_tree: Remove mas_walk in favour of mas_load. mas_walk was called in a single place for loading the value. Rename the function and clean it up. Add retry on dead node detection and retry entries. Note that this can return the zero entry. Also fix comments for _mas_walk Also update limits on _mas_walk so that the maple state can be used for checking the range limit of a search result. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 70 +++++++++++++++++++++++++----------------------- 1 file changed, 37 insertions(+), 33 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index af014df6908f5..bc8f63c422c78 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3332,6 +3332,11 @@ ascend: /* * Private: Returns true if mas->node is a leaf + * + * + * Will not point to a skip entry. + * May point to a deleted or retry entry. + * */ static inline bool __mas_walk(struct ma_state *mas) { @@ -3378,6 +3383,7 @@ skip_entry: case maple_dense: // Linear node. i = mas->index - mas->min; + mas->min = mas->max = mas->index; goto done; } @@ -3387,12 +3393,12 @@ skip_entry: goto skip_entry; } - if (mt_is_empty(next)) // Not found. - goto done; - // Traverse. mas->max = max; mas->min = min; + if (mt_is_empty(next)) // Not found. + goto done; + mas->node = next; } done: @@ -3403,6 +3409,7 @@ done: static inline bool _mas_walk(struct ma_state *mas) { void *entry = mas_start(mas); + if (entry) return true; @@ -3463,14 +3470,6 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) return 1; } -void *mas_load(struct ma_state *mas) -{ - void *entry = mas_walk(mas); - if (xa_is_zero(entry) || mt_is_empty(entry)) - return NULL; - - return entry; -} /** * mas_find - Find the first entry that overlaps the range. * If mas->node is root, finds mas->index and returns the value. If the @@ -4079,42 +4078,44 @@ no_gap: return -EBUSY; } -/* - * Private +/** * * Must hold rcu_read_lock or the write lock. * * Find where ms->index is located and return the entry. - * ms->node will point to the node containing the entry. + * mas->node will point to the node containing the entry. * * */ -void *mas_walk(struct ma_state *mas) +void *mas_load(struct ma_state *mas) { void *entry = NULL; - unsigned char slot = MAPLE_NODE_SLOTS; - bool leaf = false; - void *root = rcu_dereference(mas->tree->ma_root); - if (root == NULL) +retry: + if (_mas_walk(mas)) { + unsigned char slot = MAPLE_NODE_SLOTS; + + if (mas_is_ptr(mas) && mas->last == 0) + return mte_safe_root(mas->tree->ma_root); + + slot = mas_get_slot(mas); + if (slot >= MAPLE_NODE_SLOTS) + return NULL; + + entry = mte_get_rcu_slot(mas->node, slot); + if (mte_dead_node(mas->node)) + goto retry; + + } + + if (mas_is_none(mas)) return NULL; - if (!xa_is_node(root)) { - if (mas->last == 0) - return root; + if (!entry || xa_is_deleted(entry)) return NULL; - } - leaf = _mas_walk(mas); - slot = mas_get_slot(mas); - if (leaf == true) { - if (slot == MAPLE_NODE_SLOTS) { - if (mas->index == 0) - return root; - } else { - entry = mte_get_rcu_slot(mas->node, slot); - } - } + if (xa_is_retry(entry)) + goto retry; return entry; } @@ -4221,6 +4222,9 @@ void *mtree_load(struct maple_tree *mt, unsigned long index) rcu_read_lock(); entry = mas_load(&mas); rcu_read_unlock(); + if (xa_is_zero(entry)) + return NULL; + return entry; } EXPORT_SYMBOL(mtree_load); -- 2.50.1