From 1484a80bcc121272490a78d68f16a4c58b1e2014 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 4 Sep 2020 15:17:57 -0400 Subject: [PATCH] maple_tree: Optimizations on mas_data_end and mas_rev_awalk Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 3 +-- lib/maple_tree.c | 33 ++++++++------------------------- 2 files changed, 9 insertions(+), 27 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index d30038669523..560a5de8fe77 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -37,7 +37,6 @@ #define MAPLE_SPARSE16_SLOTS 24 /* 248 bytes */ #define MAPLE_SPARSE9_SLOTS 27 /* 256 bytes */ #define MAPLE_SPARSE6_SLOTS 30 /* 256 bytes */ -#define MA_NODE_PER_PAGE 16 #else #define MAPLE_NODE_SLOTS 15 /* 128 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 8 /* 128 bytes */ @@ -50,9 +49,9 @@ #define MAPLE_SPARSE16_SLOTS 12 /* 128 bytes */ #define MAPLE_SPARSE9_SLOTS 13 /* 127 bytes */ #define MAPLE_SPARSE6_SLOTS 14 /* 128 bytes */ -#define MA_NODE_PER_PAGE 32 #endif // End NODE256 +#define MA_MAX_ALLOC 127 #else /* Need to do corresponding calculations for 32-bit kernels */ #endif diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9af32117ebc2..a010d1f8fc29 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1131,15 +1131,11 @@ static inline unsigned char mas_data_end(const struct ma_state *mas) enum maple_type type = mte_node_type(mas->node); unsigned long piv = mas->min; - for (; slot < mt_slots[type]; slot++) { + while (slot < mt_slots[type]) { piv = _mas_get_safe_pivot(mas, slot, type); if (piv >= mas->max) break; - - if (!piv && slot) { - slot--; - break; - } + slot++; } return slot; @@ -3913,20 +3909,8 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; - mas_start(mas); - if (mas_is_none(mas)) { - mas_set_offset(mas, MAPLE_NODE_SLOTS); - return; - } - - if (mas_is_ptr(mas)) - return; - if (mas_is_err(mas)) - return; - mas_set_offset(mas, mas_data_end(mas)); - /* There are 4 options: * go to child (descend) * go back to parent (ascend) @@ -4054,9 +4038,9 @@ void mas_set_rev_index(struct ma_state *mas, unsigned long size) mas->index = mas->last - size + 1; } -static void _mas_empty_or_single_empty_area(struct ma_state *mas, - unsigned long min, unsigned long max, unsigned long size, - bool fwd) +static void _mas_sparse_area(struct ma_state *mas, + unsigned long min, unsigned long max, + unsigned long size, bool fwd) { unsigned long start = 0; @@ -4084,7 +4068,7 @@ static inline int _mas_get_empty_area(struct ma_state *mas, // Empty set. if (mas_is_none(mas) || mas_is_ptr(mas)) { - _mas_empty_or_single_empty_area(mas, min, max, size, forward); + _mas_sparse_area(mas, min, max, size, forward); return 0; } @@ -4458,7 +4442,7 @@ static inline struct maple_enode *mas_dup_node(struct ma_state *oldmas, static inline void mas_dup_alloc(struct ma_state *mas, int *node_cnt) { - int alloc_cnt = min(*node_cnt, MA_NODE_PER_PAGE); + int alloc_cnt = min(*node_cnt, MA_MAX_ALLOC); /* Allocate nodes for new tree. Maximum will be 16 ** height */ *node_cnt -= alloc_cnt; mas_node_cnt(mas, alloc_cnt); @@ -4470,10 +4454,9 @@ static inline void mas_dup_children(struct ma_state *mas, int *node_cnt) { struct maple_node *child; struct maple_enode *oldchild, *echild; - unsigned char slot, end; + unsigned char slot, end = mt_slot_count(mas->node); int allocated = mas_get_alloc_cnt(mas); - end = mas_data_end(mas) + 1; if (allocated < end) { mas->span_enode = mas->node; *node_cnt += allocated; -- 2.50.1