From 4ee38597e9263fc931ac50f87958ac4382907834 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 26 Nov 2019 13:54:29 -0500 Subject: [PATCH] maple_tree: Add mas_get_unmapped_area and mas_get_unmapped_area_rev This adds an interface which was missing for the drop-in replacement for the mmap code. It also fixes two issues: 1. Range checking for the upper bounds during a forward allocation walk in _awalk 2. Checking if the ma_state is in error state during the loop in awalk prior to calling _awalk. The order was incorrect and could have caused issues. I've exposed mas_prev, and mtree_store_range for the mmap code in this commit as well. I've renamed a few missed ma_state functions to mas_ instead of ma_. I've also reorder the header a bit. Along with the new mas_get_unmapped_area{_rev}, I've added testcases for them. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 41 ++++++++++---- lib/maple_tree.c | 112 ++++++++++++++++++++++++++++++------- lib/test_maple_tree.c | 73 +++++++++++++++++++++++- 3 files changed, 192 insertions(+), 34 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 8fa8a6e0a31f..f3a56d5f9ed2 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -214,6 +214,8 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp); void *mtree_erase(struct maple_tree *mt, unsigned long index); void mtree_destroy(struct maple_tree *mt); +int mtree_store_range(struct maple_tree *mt, unsigned long first, + unsigned long last, void *entry, gfp_t gfp); /** * mtree_empty() - Determine if a tree has any present entries. @@ -302,6 +304,17 @@ bool mas_nomem(struct ma_state *mas, gfp_t gfp); void mas_pause(struct ma_state *mas); void maple_tree_init(void); +void *mas_prev(struct ma_state *mas, unsigned long min); + +/* Finds a sufficient hole */ +int mas_get_unmapped_area(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size); + +/* This finds an unmapped area from the highest address to the lowest. + * AKA "Topdown" version, + */ +int mas_get_unmapped_area_rev(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size); /** * mas_reset() - Reset a Maple Tree operation state. * @mas: Maple Tree operation state. @@ -332,18 +345,6 @@ static inline void mas_reset(struct ma_state *mas) #define mas_for_each(mas, entry, max) \ while ((entry = mas_find(mas, max)) != NULL) -/** - * 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(mt, &index, max, true); \ - entry; entry = mt_find(mt, &index, max, false)) bool mas_retry(struct ma_state *mas, const void *entry); @@ -379,4 +380,20 @@ static inline void mas_set(struct ma_state *mas, unsigned long index) mas_set_range(mas, index, index); } + +void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, + bool start); +/** + * 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(mt, &index, max, true); \ + entry; entry = mt_find(mt, &index, max, false)) + #endif /*_LINUX_MAPLE_TREE_H */ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c85d6d9ba346..b2f846e9f440 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2768,7 +2768,7 @@ static inline void* _mas_prev(struct ma_state *mas, unsigned long limit) * * */ -static inline void *mas_prev(struct ma_state *mas, unsigned long min) +void *mas_prev(struct ma_state *mas, unsigned long min) { void *entry; if (mas->node && !mas_searchable(mas)) @@ -3433,12 +3433,6 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) if (i && !pivot) break; - /* out of upper bounds */ - if (mas->last < pivot) { - mas_set_err(mas, -EBUSY); - return true; - } - /* Not within lower bounds */ if (mas->index > pivot) goto next; @@ -3454,6 +3448,11 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) if (!this_gap) // No entry, pivot = index. this_gap = 1; + /* out of upper bounds */ + if (mas->last + size < pivot - this_gap) { + mas_set_err(mas, -EBUSY); + return true; + } /* Does not fit in this gap or node */ if (mas->last < pivot - this_gap) goto ascend; @@ -3959,15 +3958,13 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) if (mas_is_ptr(mas)) return; - mas_set_slot(mas, 0); - /* There are 4 options: * go to child (descend) * go back to parent (ascend) * no gap found. (return, slot == MAPLE_NODE_SLOTS) * found the gap. (return, slot != MAPLE_NODE_SLOTS) */ - while (!_mas_awalk(mas, size) && !mas_is_err(mas)) { + while (!mas_is_err(mas) && !_mas_awalk(mas, size)) { if (last == mas->node) mas_skip_node(mas); else @@ -4057,8 +4054,87 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, return 0; } +void mas_set_fwd_index(struct ma_state *mas, unsigned long size) +{ + unsigned long min = mas->min; + unsigned char slot = mas_get_slot(mas); + if (slot) + min = mte_get_pivot(mas->node, slot - 1) + 1; + + if (mas->index < min) + mas->index = min; + mas->last = mas->index + size - 1; +} +void mas_set_rev_index(struct ma_state *mas, unsigned long size) +{ + // At this point, mas->node points to the right node and we have a + // slot that has a sufficient gap. + // If the maximum is outside the window we are searching, then use the + // last location in the search. + if (mas->max > mas->last) + mas->index = mas->last; + else + mas->index = mas->max - size + 1; + + mas->last = mas->index + size - 1; +} +static inline int _mas_get_unmapped_area(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size, bool forward) +{ + mas_start(mas); + + // Empty set. + if (mas_is_none(mas)) { + mas->index = 0; + mas->last = size - 1; + return 0; + } + // There is already a single value. + if (mas_is_ptr(mas)) { + mas->index = 1; + mas->last = size; + return 0; + } + + // The start of the window can only be within these values. + mas->index = min; + mas->last = max - size + 1; + + if (forward) + mas_awalk(mas, size); + else + mas_rev_awalk(mas, size); + + if (mas_is_err(mas)) + return xa_err(mas->node); + + if (mas_get_slot(mas) == MAPLE_NODE_SLOTS) + goto no_gap; + + if (forward) + mas_set_fwd_index(mas, size); + else + mas_set_rev_index(mas, size); + + return 0; + +no_gap: + return -EBUSY; + + +} +int mas_get_unmapped_area(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size) +{ + return _mas_get_unmapped_area(mas, min, max, size, true); +} +int mas_get_unmapped_area_rev(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size) +{ + return _mas_get_unmapped_area(mas, min, max, size, false); +} /** Private - * ma_alloc() - Allocate a range. + * mas_alloc() - Allocate a range. * * Give a size, a minimum starting point (mas->index), a maximum (mas->last), * and a size (size), find the lowest location in the min-max window in the @@ -4066,7 +4142,7 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, * * Returns: 0 on success, -ENOMEM if allocation fails, -EBUSY otherwise. */ -static inline int ma_alloc(struct ma_state *mas, void *entry, +static inline int mas_alloc(struct ma_state *mas, void *entry, unsigned long size, unsigned long *index) { unsigned char slot = MAPLE_NODE_SLOTS; @@ -4107,7 +4183,7 @@ no_gap: return -EBUSY; } /** Private - * ma_rev_alloc() - Reverse allocate a range. + * mas_rev_alloc() - Reverse allocate a range. * * Give a size, a minimum value (mas->index), a maximum starting point * (mas->last), and a size (size), find the largest location in the min-max @@ -4115,7 +4191,7 @@ no_gap: * * Returns: 0 on success, -EBUSY otherwise. */ -static inline int ma_rev_alloc(struct ma_state *mas, void *entry, +static inline int mas_rev_alloc(struct ma_state *mas, void *entry, unsigned long size, unsigned long *index) { unsigned char slot = MAPLE_NODE_SLOTS; @@ -4410,9 +4486,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, retry: mas.index = min; mas.last = max - size; - mas.min = 0; - mas.max = mt_max[maple_arange_64]; - ret = ma_alloc(&mas, entry, size, startp); + ret = mas_alloc(&mas, entry, size, startp); if (mas_nomem(&mas, gfp)) goto retry; @@ -4446,9 +4520,7 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, retry: mas.index = min; mas.last = max - size + 1; - mas.min = 0; - mas.max = mt_max[maple_arange_64]; - ret = ma_rev_alloc(&mas, entry, size, startp); + ret = mas_rev_alloc(&mas, entry, size, startp); if (mas_nomem(&mas, gfp)) goto retry; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index e1790a9f5f81..e0407b0fef23 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -384,8 +384,8 @@ static noinline void check_find(struct maple_tree *mt) unsigned long val = 0; unsigned long count = 20; unsigned long max; - unsigned long index = 0; - void *entry; + unsigned long last = 0, index = 0; + void *entry, *entry2; MA_STATE(mas, mt, 0, 0); @@ -490,6 +490,40 @@ static noinline void check_find(struct maple_tree *mt) } mas_unlock(&mas); + /* Find last value. + * 1. get the expected value, leveraging the existence of an end entry + * 2. delete end entry + * 3. find the last value but searching for ULONG_MAX and then using + * prev + * + */ + // First, get the expected result. + mas_lock(&mas); + mas_reset(&mas); + mas.index = ULONG_MAX; // start at max.. + entry = mas_find(&mas, ULONG_MAX); + entry = mas_prev(&mas, 0); + index = mas.index; + last = mas.last; + + // Erase the last entry. + mas_reset(&mas); + mas.index = ULONG_MAX; + mas.last = ULONG_MAX; + mas_erase(&mas); + + // Get the previous value from MAS_START + mas_reset(&mas); + entry2 = mas_prev(&mas, 0); + + // Check results. + MT_BUG_ON(mt, entry != entry2); + MT_BUG_ON(mt, index != mas.index); + MT_BUG_ON(mt, last != mas.last); + mas_unlock(&mas); + + + mtree_destroy(mt); } @@ -816,6 +850,13 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) 0x7fff58791000, 0x7fff58793000, }; + unsigned long holes[] = { + // Start of hole, end of hole, size of hole (+1) + 0x565234afb000, 0x565234afc000, 0x1000, + 0x565234afe000, 0x565235def000, 0x12F1000, + 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, + }; + /* req_range consists of 4 values. * 1. min index * 2. max index @@ -876,6 +917,17 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) mt_validate(mt); } + MA_STATE(mas, mt, 0, 0); + unsigned long min = 0; + for (i = 0; i < ARRAY_SIZE(holes); i+= 3) { + MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, min, + holes[i+1], + holes[i+2])); + MT_BUG_ON(mt, mas.index != holes[i + 1] - holes[i+2] + 1); + min = holes[i+1]; + mas_reset(&mas); + } + for (i = 0; i < req_range_cnt; i += 5) { check_mtree_alloc_rrange(mt, req_range[i] >> 12, // start @@ -924,6 +976,12 @@ static noinline void check_alloc_range(struct maple_tree *mt) 0x7fff5878e000, 0x7fff58791000, 0x7fff58791000, 0x7fff58793000, }; + unsigned long holes[] = { + // Start of hole, end of hole, size of hole (+1) + 0x565234afb000, 0x565234afc000, 0x1000, + 0x565234afe000, 0x565235def000, 0x12F1000, + 0x565235e10000, 0x7f36d4bfd000, 0x28E49EDED000, + }; /* req_range consists of 4 values. * 1. min index @@ -991,6 +1049,17 @@ static noinline void check_alloc_range(struct maple_tree *mt) mt_validate(mt); } + + MA_STATE(mas, mt, 0, 0); + unsigned long min = 0x565234af2000; + for (i = 0; i < ARRAY_SIZE(holes); i+= 3) { + MT_BUG_ON(mt, mas_get_unmapped_area(&mas, min >> 12, + holes[i+1] >> 12, + holes[i+2] >> 12)); + MT_BUG_ON(mt, mas.index != holes[i] >> 12); + min = holes[i+1]; + mas_reset(&mas); + } for (i = 0; i < req_range_cnt; i += 5) { check_mtree_alloc_range(mt, req_range[i] >> 12, // start -- 2.50.1