From 6c955ea985213319a4db9735724bd0bb02f8dcf4 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Sep 2020 21:35:50 -0400 Subject: [PATCH] maple_tree: Add mas_dup_store for quicker forking Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 5 +-- lib/maple_tree.c | 74 ++++++++++++++++++++++---------------- lib/test_maple_tree.c | 7 ++++ 3 files changed, 52 insertions(+), 34 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 812e4be382ba..a3264f6e8272 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -259,6 +259,7 @@ static inline bool mas_is_none(struct ma_state *mas) } void mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas); +void mas_dup_store(struct ma_state *mas, void *entry); /* This finds an empty area from the highest address to the lowest. * AKA "Topdown" version, */ @@ -395,11 +396,7 @@ void *_mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, /** * mt_for_each - Searches for an entry starting at index until max. * - * - * * Note: Will not return the zero entry. - * - * */ #define mt_for_each(tree, entry, index, max) \ for (entry = _mt_find(tree, &index, max, true); \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index a425b298c190..66fb2a429be4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2861,7 +2861,7 @@ static inline bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min, return ret; } -static inline unsigned char mas_extend_null(struct ma_state *l_mas, +static inline void mas_extend_null(struct ma_state *l_mas, struct ma_state *r_mas) { unsigned char l_slot = mas_offset(l_mas); @@ -2907,8 +2907,6 @@ static inline unsigned char mas_extend_null(struct ma_state *l_mas, if (l_mas != r_mas) mas_set_offset(r_mas, cp_r_slot); - - return r_slot; } /* @@ -3057,14 +3055,14 @@ static inline bool mas_can_append(struct ma_state *mas, static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite) { unsigned long r_max, r_min; - unsigned char end, slot; + unsigned char end, offset; unsigned char slot_cnt; void *content = NULL; struct maple_big_node b_node; int ret = 0; - if (mas_start(mas) || (mas_is_none(mas) || mas->node == MAS_ROOT)) { + if (mas_start(mas) || mas_is_none(mas) || mas->node == MAS_ROOT) { ret = ma_root_ptr(mas, entry, content, overwrite); if (mas_is_err(mas)) return NULL; @@ -3086,34 +3084,31 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite /* At this point, we are at the leaf node that needs to be altered. */ /* Calculate needed space */ - slot = mas_offset(mas); - slot_cnt = mt_slot_count(mas->node); - content = mas_get_slot(mas, slot); + offset = mas_offset(mas); + content = mas_get_slot(mas, offset); if (!overwrite && ((mas->last > r_max) || content)) { mas_set_err(mas, -EEXIST); - goto exists; + return content; } - if (!entry) { + if (!entry) mas_extend_null(mas, mas); - slot = mas_offset(mas); - } memset(&b_node, 0, sizeof(struct maple_big_node)); - mas_set_offset(mas, slot); b_node.b_end = mas_store_b_node(mas, &b_node, entry); b_node.min = mas->min; b_node.type = mte_node_type(mas->node); // Check if this is an append operation. end = mas_data_end(mas); + slot_cnt = mt_slot_count(mas->node); if (mas_can_append(mas, &b_node, slot_cnt, end)) { - slot = b_node.b_end; + offset = b_node.b_end; do { - mte_set_slot(mas->node, slot, b_node.slot[slot]); - if (slot < slot_cnt - 1) - mte_set_pivot(mas->node, slot, b_node.pivot[slot]); - } while(slot && slot-- >= end); + mte_set_slot(mas->node, offset, b_node.slot[offset]); + if (offset < slot_cnt - 1) + mte_set_pivot(mas->node, offset, b_node.pivot[offset]); + } while(offset && offset-- >= end); mas_update_gap(mas); goto append; } @@ -3132,7 +3127,6 @@ complete_at_root: return NULL; append: spanning_store: -exists: return content; } @@ -3441,10 +3435,8 @@ retry: if (mas_next_nentry(mas, limit, range_start)) break; - if (*range_start > limit) { -// mas->node = MAS_NONE; + if (*range_start > limit) return NULL; - } next_node: mas_next_node(mas, limit); @@ -4337,6 +4329,24 @@ static inline void mas_dup_alloc(struct ma_state *mas, int *node_cnt) return; } +void mas_dup_pause(struct ma_state *mas) +{ + mas->span_enode = mas->node; +} + +bool mas_dup_is_paused(struct ma_state *mas) +{ + if (mas->span_enode) + return true; + return false; +} + +void mas_dup_resume(struct ma_state *mas) +{ + mas->node = mas->span_enode; + mas->span_enode = NULL; +} + static inline void mas_dup_children(struct ma_state *mas, int *node_cnt) { struct maple_node *child; @@ -4347,14 +4357,14 @@ static inline void mas_dup_children(struct ma_state *mas, int *node_cnt) mte_node_type(mas->node)); if (allocated < end) { - mas->span_enode = mas->node; + mas_dup_pause(mas); *node_cnt += allocated; mas_dup_alloc(mas, node_cnt); if (mas_is_err(mas)) return; - mas->span_enode = NULL; - } + mas_dup_resume(mas); + } for(offset = 0; offset < end; offset++) { oldchild = slots[offset]; @@ -4431,10 +4441,9 @@ void _mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas, int *node_cnt) return; } - if (mas->span_enode) { - mas->node = mas->span_enode; - mas->span_enode= NULL; - goto retry_dup_children; + if (mas_dup_is_paused(mas)) { + mas_dup_resume(mas); + goto continue_dup; } if (mas_is_start(mas)) @@ -4450,7 +4459,7 @@ void _mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas, int *node_cnt) if (mte_is_leaf(oldmas->node)) continue; -retry_dup_children: +continue_dup: mas_dup_children(mas, node_cnt); if (mas_is_err(mas)) return; @@ -4475,6 +4484,11 @@ retry: mtree_unlock(mas->tree); } +void mas_dup_store(struct ma_state *mas, void *entry) { + mas_next(mas, ULONG_MAX); + mte_set_slot(mas->node, mas_offset(mas), entry); +} + static inline unsigned char mas_dead_leaves(struct ma_state *mas, void **slots) { struct maple_node *node; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 87b42c4c29f9..25846872432b 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -32453,6 +32453,13 @@ static void check_dup_tree(struct maple_tree *oldmt) check_index_load(&mt, i); check_load(&mt, max + 1, NULL); + mas_reset(&mas); + for (i = 0; i <= max; i++) + mas_dup_store(&mas, xa_mk_value(i+100)); + + for (i = 0; i <= max; i++) + check_load(&mt, i, xa_mk_value(i+100)); + mtree_destroy(&mt); } -- 2.50.1