lkml.org 
[lkml]   [2023]   [Apr]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
SubjectRe: [PATCH 28/34] maple_tree: Revise limit checks in mas_empty_area{_rev}()
From


在 2023/4/25 22:09, Liam R. Howlett 写道:
> Since the maple tree is inclusive in range, ensure that a range of 1
> (min = max) works for searching for a gap in either direction, and make
> sure the size is at least 1 but not larger than the delta between min
> and max.
>
> This commit also updates the testing. Unfortunately there isn't a way
> to safely update the tests and code without a test failure.
>
> Suggested-by: Peng Zhang <zhangpeng.00@bytedance.com>
> Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Reviewed-by: Peng Zhang <zhangpeng.00@bytedance.com>
Except test code.
> ---
> lib/maple_tree.c | 20 +++++++++++++-------
> lib/test_maple_tree.c | 27 ++++++++++++++++++++-------
> 2 files changed, 33 insertions(+), 14 deletions(-)
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index fe6c9da6f2bd5..7370d7c12fe3b 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -5248,7 +5248,10 @@ int mas_empty_area(struct ma_state *mas, unsigned long min,
> unsigned long *pivots;
> enum maple_type mt;
>
> - if (min >= max)
> + if (min > max)
> + return -EINVAL;
> +
> + if (size == 0 || max - min < size - 1)
> return -EINVAL;
>
> if (mas_is_start(mas))
> @@ -5303,7 +5306,10 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
> {
> struct maple_enode *last = mas->node;
>
> - if (min >= max)
> + if (min > max)
> + return -EINVAL;
> +
> + if (size == 0 || max - min < size - 1)
> return -EINVAL;
>
> if (mas_is_start(mas)) {
> @@ -5339,7 +5345,7 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min,
> return -EBUSY;
>
> /* Trim the upper limit to the max. */
> - if (max <= mas->last)
> + if (max < mas->last)
> mas->last = max;
>
> mas->index = mas->last - size + 1;
> @@ -6375,7 +6381,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> {
> int ret = 0;
>
> - MA_STATE(mas, mt, min, max - size);
> + MA_STATE(mas, mt, min, min);
> if (!mt_is_alloc(mt))
> return -EINVAL;
>
> @@ -6395,7 +6401,7 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> retry:
> mas.offset = 0;
> mas.index = min;
> - mas.last = max - size;
> + mas.last = max - size + 1;
> ret = mas_alloc(&mas, entry, size, startp);
> if (mas_nomem(&mas, gfp))
> goto retry;
> @@ -6411,14 +6417,14 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> {
> int ret = 0;
>
> - MA_STATE(mas, mt, min, max - size);
> + MA_STATE(mas, mt, min, max - size + 1);
> if (!mt_is_alloc(mt))
> return -EINVAL;
>
> if (WARN_ON_ONCE(mt_is_reserved(entry)))
> return -EINVAL;
>
> - if (min >= max)
> + if (min > max)
> return -EINVAL;
>
> if (max < size - 1)
> diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
> index 345eef526d8b0..7b2d19ad5934d 100644
> --- a/lib/test_maple_tree.c
> +++ b/lib/test_maple_tree.c
> @@ -105,7 +105,7 @@ static noinline void __init check_mtree_alloc_rrange(struct maple_tree *mt,
> unsigned long result = expected + 1;
> int ret;
>
> - ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end - 1,
> + ret = mtree_alloc_rrange(mt, &result, ptr, size, start, end,
> GFP_KERNEL);
> MT_BUG_ON(mt, ret != eret);
> if (ret)
> @@ -683,7 +683,7 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
> 0, /* Return value success. */
>
> 0x0, /* Min */
> - 0x565234AF1 << 12, /* Max */
> + 0x565234AF0 << 12, /* Max */
> 0x3000, /* Size */
> 0x565234AEE << 12, /* max - 3. */
> 0, /* Return value success. */
> @@ -695,14 +695,14 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
> 0, /* Return value success. */
>
> 0x0, /* Min */
> - 0x7F36D510A << 12, /* Max */
> + 0x7F36D5109 << 12, /* Max */
> 0x4000, /* Size */
> 0x7F36D5106 << 12, /* First rev hole of size 0x4000 */
> 0, /* Return value success. */
>
> /* Ascend test. */
> 0x0,
> - 34148798629 << 12,
> + 34148798628 << 12,
> 19 << 12,
> 34148797418 << 12,
> 0x0,
> @@ -714,6 +714,12 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
> 0x0,
> -EBUSY,
>
> + /* Single space test. */
> + 34148798725 << 12,
> + 34148798725 << 12,
> + 1 << 12,
> + 34148798725 << 12,
> + 0,
> };
>
> int i, range_count = ARRAY_SIZE(range);
> @@ -762,9 +768,9 @@ static noinline void __init check_alloc_rev_range(struct maple_tree *mt)
> mas_unlock(&mas);
> for (i = 0; i < req_range_count; i += 5) {
> #if DEBUG_REV_RANGE
> - pr_debug("\tReverse request between %lu-%lu size %lu, should get %lu\n",
> - req_range[i] >> 12,
> - (req_range[i + 1] >> 12) - 1,
> + pr_debug("\tReverse request %d between %lu-%lu size %lu, should get %lu\n",
> + i, req_range[i] >> 12,
> + (req_range[i + 1] >> 12),
> req_range[i+2] >> 12,
> req_range[i+3] >> 12);
> #endif
> @@ -883,6 +889,13 @@ static noinline void __init check_alloc_range(struct maple_tree *mt)
> 4503599618982063UL << 12, /* Size */
> 34359052178 << 12, /* Expected location */
> -EBUSY, /* Return failure. */
> +
> + /* Test a single entry */
> + 34148798648 << 12, /* Min */
> + 34148798648 << 12, /* Max */
> + 4096, /* Size of 1 */
> + 34148798648 << 12, /* Location is the same as min/max */
> + 0, /* Success */
> };
> int i, range_count = ARRAY_SIZE(range);
> int req_range_count = ARRAY_SIZE(req_range);

\
 
 \ /
  Last update: 2023-04-28 09:07    [W:0.643 / U:0.460 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site