diff mbox series

[28/34] maple_tree: Revise limit checks in mas_empty_area{_rev}()

Message ID 20230425140955.3834476-29-Liam.Howlett@oracle.com (mailing list archive)
State New
Headers show
Series Maple tree mas_{next,prev}_range() and cleanup | expand

Commit Message

Liam R. Howlett April 25, 2023, 2:09 p.m. UTC 
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>
---
 lib/maple_tree.c      | 20 +++++++++++++-------
 lib/test_maple_tree.c | 27 ++++++++++++++++++++-------
 2 files changed, 33 insertions(+), 14 deletions(-)

Comments

Peng Zhang April 28, 2023, 7:06 a.m. UTC | #1 
在 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);
diff mbox series

Patch

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);