diff mbox series

[v2,01/10] maple_tree: Rework mtree_alloc_{range,rrange}()

Message ID	20230517085809.86522-2-zhangpeng.00@bytedance.com
State	New
Headers	Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20; From: Peng Zhang <zhangpeng.00@bytedance.com> To: Liam.Howlett@oracle.com Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, Peng Zhang <zhangpeng.00@bytedance.com> Subject: [PATCH v2 01/10] maple_tree: Rework mtree_alloc_{range,rrange}() Date: Wed, 17 May 2023 16:58:00 +0800 Message-Id: <20230517085809.86522-2-zhangpeng.00@bytedance.com> In-Reply-To: <20230517085809.86522-1-zhangpeng.00@bytedance.com> References: <20230517085809.86522-1-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Precedence: bulk
Series	Clean ups for maple tree \| [v2,00/10] Clean ups for maple tree [v2,01/10] maple_tree: Rework mtree_alloc_{range,rrange}() [v2,02/10] maple_tree: Drop mas_{rev_}alloc() and mas_fill_gap() [v2,03/10] maple_tree: Fix the arguments to __must_hold() [v2,04/10] maple_tree: Simplify mas_is_span_wr() [v2,05/10] maple_tree: Make the code symmetrical in mas_wr_extend_null() [v2,06/10] maple_tree: Add mas_wr_new_end() to calculate new_end accurately [v2,07/10] maple_tree: Add comments and some minor cleanups to mas_wr_append() [v2,08/10] maple_tree: Rework mas_wr_slot_store() to be cleaner and more efficient. [v2,09/10] maple_tree: Simplify and clean up mas_wr_node_store() [v2,10/10] maple_tree: Relocate the declaration of mas_empty_area_rev().

Commit Message

Peng Zhang May 17, 2023, 8:58 a.m. UTC

  Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
 1 file changed, 32 insertions(+), 31 deletions(-)

Comments

Liam R. Howlett May 17, 2023, 6:17 p.m. UTC | #1

* Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
> Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> ---
>  lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
>  1 file changed, 32 insertions(+), 31 deletions(-)
> 
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 4eb220008f72..e1820e90f167 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, min);
> +	MA_STATE(mas, mt, 0, 0);
>  	if (!mt_is_alloc(mt))
>  		return -EINVAL;
>  
>  	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>  		return -EINVAL;
>  
> -	if (min > max)
> -		return -EINVAL;
> -
> -	if (max < size)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
>  	mtree_lock(mt);
>  retry:
> -	mas.offset = 0;
> -	mas.index = min;
> -	mas.last = max - size + 1;
> -	ret = mas_alloc(&mas, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> +	ret = mas_empty_area(&mas, min, max, size);
> +	if (!ret) {
> +		mas_insert(&mas, entry);
> +		/*
> +		 * mas_nomem() may release the lock, causing the allocated area
> +		 * to be unavailable, so try to allocate a free area again.
> +		 */
> +		if (mas_nomem(&mas, gfp))
> +			goto retry;
> +	}
>  	mtree_unlock(mt);
> +	if (!ret) {

Checking for a mas_is_err() should probably be outside if (!ret)
statement.  If mas_insert() returns something besides ENOMEM, we will
not detect the error.  I'm not sure if this is possible today since this
should never return an -EEXISTS, but having it this way doesn't add much
to the overhead.

> +		if (mas_is_err(&mas))
> +			return xa_err(mas.node);
> +		*startp = mas.index;
> +	}
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_range);
> @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>  {
>  	int ret = 0;
>  
> -	MA_STATE(mas, mt, min, max - size + 1);
> +	MA_STATE(mas, mt, 0, 0);
>  	if (!mt_is_alloc(mt))
>  		return -EINVAL;
>  
>  	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>  		return -EINVAL;
>  
> -	if (min > max)
> -		return -EINVAL;
> -
> -	if (max < size - 1)
> -		return -EINVAL;
> -
> -	if (!size)
> -		return -EINVAL;
> -
>  	mtree_lock(mt);
>  retry:
> -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
> -	if (mas_nomem(&mas, gfp))
> -		goto retry;
> -
> +	ret = mas_empty_area_rev(&mas, min, max, size);
> +	if (!ret) {
> +		mas_insert(&mas, entry);
> +		/*
> +		 * mas_nomem() may release the lock, causing the allocated area
> +		 * to be unavailable, so try to allocate a free area again.
> +		 */
> +		if (mas_nomem(&mas, gfp))
> +			goto retry;
> +	}
>  	mtree_unlock(mt);
> +	if (!ret) {

Same here.

> +		if (mas_is_err(&mas))
> +			return xa_err(mas.node);
> +		*startp = mas.index;
> +	}
>  	return ret;
>  }
>  EXPORT_SYMBOL(mtree_alloc_rrange);
> -- 
> 2.20.1
>

Peng Zhang May 18, 2023, 6:10 a.m. UTC | #2

在 2023/5/18 02:17, Liam R. Howlett 写道:
> * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
>> Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
>>
>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>> ---
>>   lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
>>   1 file changed, 32 insertions(+), 31 deletions(-)
>>
>> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
>> index 4eb220008f72..e1820e90f167 100644
>> --- a/lib/maple_tree.c
>> +++ b/lib/maple_tree.c
>> @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, min);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	if (!mt_is_alloc(mt))
>>   		return -EINVAL;
>>   
>>   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>>   		return -EINVAL;
>>   
>> -	if (min > max)
>> -		return -EINVAL;
>> -
>> -	if (max < size)
>> -		return -EINVAL;
>> -
>> -	if (!size)
>> -		return -EINVAL;
>> -
>>   	mtree_lock(mt);
>>   retry:
>> -	mas.offset = 0;
>> -	mas.index = min;
>> -	mas.last = max - size + 1;
>> -	ret = mas_alloc(&mas, entry, size, startp);
>> -	if (mas_nomem(&mas, gfp))
>> -		goto retry;
>> -
>> +	ret = mas_empty_area(&mas, min, max, size);
>> +	if (!ret) {
>> +		mas_insert(&mas, entry);
>> +		/*
>> +		 * mas_nomem() may release the lock, causing the allocated area
>> +		 * to be unavailable, so try to allocate a free area again.
>> +		 */
>> +		if (mas_nomem(&mas, gfp))
>> +			goto retry;
>> +	}
>>   	mtree_unlock(mt);
>> +	if (!ret) {
> 
> Checking for a mas_is_err() should probably be outside if (!ret)
> statement.  If mas_insert() returns something besides ENOMEM, we will
> not detect the error.  I'm not sure if this is possible today since this
> should never return an -EEXISTS, but having it this way doesn't add much
> to the overhead.
I don't think there will be error that can't be detected here.
In fact, there are two sources of errors:

1. mas_empty_area(), the error number is in the variable ret,
    and may also be in mas->node, but ret must contain all errors.

2. mas_insert(), the error number is in mas->node

When we check errors, we should first check errors from
mas_empty_area(). If there is no error in mas_empty_area(), we
will check errors from mas_insert().
So, mas_is_err() is inside the if (!ret) statement, no problem here.

Of course, even if mas_insert() returns -EEXISTS, it can be detected
under the current encoding, because "if (!ret)" is true in this case.
But I don't think this can happen, if it happens, it's a bug of maple
tree.

I don't think it's good to put mas_is_err() outside, because the error
number stored in mas->node may come from mas_empty_area(). We should use
the ret variable to detect the error from mas_empty_area() first.
> 
>> +		if (mas_is_err(&mas))
>> +			return xa_err(mas.node);
>> +		*startp = mas.index;
>> +	}
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_range);
>> @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
>>   {
>>   	int ret = 0;
>>   
>> -	MA_STATE(mas, mt, min, max - size + 1);
>> +	MA_STATE(mas, mt, 0, 0);
>>   	if (!mt_is_alloc(mt))
>>   		return -EINVAL;
>>   
>>   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
>>   		return -EINVAL;
>>   
>> -	if (min > max)
>> -		return -EINVAL;
>> -
>> -	if (max < size - 1)
>> -		return -EINVAL;
>> -
>> -	if (!size)
>> -		return -EINVAL;
>> -
>>   	mtree_lock(mt);
>>   retry:
>> -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
>> -	if (mas_nomem(&mas, gfp))
>> -		goto retry;
>> -
>> +	ret = mas_empty_area_rev(&mas, min, max, size);
>> +	if (!ret) {
>> +		mas_insert(&mas, entry);
>> +		/*
>> +		 * mas_nomem() may release the lock, causing the allocated area
>> +		 * to be unavailable, so try to allocate a free area again.
>> +		 */
>> +		if (mas_nomem(&mas, gfp))
>> +			goto retry;
>> +	}
>>   	mtree_unlock(mt);
>> +	if (!ret) {
> 
> Same here.
> 
>> +		if (mas_is_err(&mas))
>> +			return xa_err(mas.node);
>> +		*startp = mas.index;
>> +	}
>>   	return ret;
>>   }
>>   EXPORT_SYMBOL(mtree_alloc_rrange);
>> -- 
>> 2.20.1
>>

Liam R. Howlett May 18, 2023, 1:47 p.m. UTC | #3

* Peng Zhang <zhangpeng.00@bytedance.com> [230518 02:10]:
> 
> 
> 在 2023/5/18 02:17, Liam R. Howlett 写道:
> > * Peng Zhang <zhangpeng.00@bytedance.com> [230517 04:58]:
> > > Use mas_empty_area{_rev}() to refactor mtree_alloc_{range,rrange}()
> > > 
> > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > ---
> > >   lib/maple_tree.c | 63 ++++++++++++++++++++++++------------------------
> > >   1 file changed, 32 insertions(+), 31 deletions(-)
> > > 
> > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > index 4eb220008f72..e1820e90f167 100644
> > > --- a/lib/maple_tree.c
> > > +++ b/lib/maple_tree.c
> > > @@ -6493,32 +6493,31 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, min);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	if (!mt_is_alloc(mt))
> > >   		return -EINVAL;
> > >   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> > >   		return -EINVAL;
> > > -	if (min > max)
> > > -		return -EINVAL;
> > > -
> > > -	if (max < size)
> > > -		return -EINVAL;
> > > -
> > > -	if (!size)
> > > -		return -EINVAL;
> > > -
> > >   	mtree_lock(mt);
> > >   retry:
> > > -	mas.offset = 0;
> > > -	mas.index = min;
> > > -	mas.last = max - size + 1;
> > > -	ret = mas_alloc(&mas, entry, size, startp);
> > > -	if (mas_nomem(&mas, gfp))
> > > -		goto retry;
> > > -
> > > +	ret = mas_empty_area(&mas, min, max, size);
> > > +	if (!ret) {
> > > +		mas_insert(&mas, entry);
> > > +		/*
> > > +		 * mas_nomem() may release the lock, causing the allocated area
> > > +		 * to be unavailable, so try to allocate a free area again.
> > > +		 */
> > > +		if (mas_nomem(&mas, gfp))
> > > +			goto retry;
> > > +	}
> > >   	mtree_unlock(mt);
> > > +	if (!ret) {
> > 
> > Checking for a mas_is_err() should probably be outside if (!ret)
> > statement.  If mas_insert() returns something besides ENOMEM, we will
> > not detect the error.  I'm not sure if this is possible today since this
> > should never return an -EEXISTS, but having it this way doesn't add much
> > to the overhead.
> I don't think there will be error that can't be detected here.
> In fact, there are two sources of errors:
> 
> 1. mas_empty_area(), the error number is in the variable ret,
>    and may also be in mas->node, but ret must contain all errors.
> 
> 2. mas_insert(), the error number is in mas->node
> 
> When we check errors, we should first check errors from
> mas_empty_area(). If there is no error in mas_empty_area(), we
> will check errors from mas_insert().
> So, mas_is_err() is inside the if (!ret) statement, no problem here.
> 
> Of course, even if mas_insert() returns -EEXISTS, it can be detected
> under the current encoding, because "if (!ret)" is true in this case.
> But I don't think this can happen, if it happens, it's a bug of maple
> tree.

Right, thanks.

> 
> I don't think it's good to put mas_is_err() outside, because the error
> number stored in mas->node may come from mas_empty_area(). We should use
> the ret variable to detect the error from mas_empty_area() first.

Yeah, I would structure it as a 'goto' to undo the locking to avoid the
if (!ret) nesting, and move the unlock to just before the return:

if (ret)
	goto unlock;

...
	*startp = mas.index;

unlock:
	mtree_unlock(mt);
	return ret;

mas_empty_area() is an external interface and so already decodes the
error in the node using mas_is_err(), so this can be dropped completely.

I don't think holding the lock for the one extra assignment will make a
difference.

> > 
> > > +		if (mas_is_err(&mas))
> > > +			return xa_err(mas.node);
> > > +		*startp = mas.index;
> > > +	}
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_range);
> > > @@ -6529,29 +6528,31 @@ int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
> > >   {
> > >   	int ret = 0;
> > > -	MA_STATE(mas, mt, min, max - size + 1);
> > > +	MA_STATE(mas, mt, 0, 0);
> > >   	if (!mt_is_alloc(mt))
> > >   		return -EINVAL;
> > >   	if (WARN_ON_ONCE(mt_is_reserved(entry)))
> > >   		return -EINVAL;
> > > -	if (min > max)
> > > -		return -EINVAL;
> > > -
> > > -	if (max < size - 1)
> > > -		return -EINVAL;
> > > -
> > > -	if (!size)
> > > -		return -EINVAL;
> > > -
> > >   	mtree_lock(mt);
> > >   retry:
> > > -	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
> > > -	if (mas_nomem(&mas, gfp))
> > > -		goto retry;
> > > -
> > > +	ret = mas_empty_area_rev(&mas, min, max, size);
> > > +	if (!ret) {
> > > +		mas_insert(&mas, entry);
> > > +		/*
> > > +		 * mas_nomem() may release the lock, causing the allocated area
> > > +		 * to be unavailable, so try to allocate a free area again.
> > > +		 */
> > > +		if (mas_nomem(&mas, gfp))
> > > +			goto retry;
> > > +	}
> > >   	mtree_unlock(mt);
> > > +	if (!ret) {
> > 
> > Same here.
> > 
> > > +		if (mas_is_err(&mas))
> > > +			return xa_err(mas.node);
> > > +		*startp = mas.index;
> > > +	}
> > >   	return ret;
> > >   }
> > >   EXPORT_SYMBOL(mtree_alloc_rrange);
> > > -- 
> > > 2.20.1
> > >

diff mbox series

Patch

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 4eb220008f72..e1820e90f167 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -6493,32 +6493,31 @@  int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, min);
+	MA_STATE(mas, mt, 0, 0);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
 	if (WARN_ON_ONCE(mt_is_reserved(entry)))
 		return -EINVAL;
 
-	if (min > max)
-		return -EINVAL;
-
-	if (max < size)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
 	mtree_lock(mt);
 retry:
-	mas.offset = 0;
-	mas.index = min;
-	mas.last = max - size + 1;
-	ret = mas_alloc(&mas, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
+	ret = mas_empty_area(&mas, min, max, size);
+	if (!ret) {
+		mas_insert(&mas, entry);
+		/*
+		 * mas_nomem() may release the lock, causing the allocated area
+		 * to be unavailable, so try to allocate a free area again.
+		 */
+		if (mas_nomem(&mas, gfp))
+			goto retry;
+	}
 	mtree_unlock(mt);
+	if (!ret) {
+		if (mas_is_err(&mas))
+			return xa_err(mas.node);
+		*startp = mas.index;
+	}
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_range);
@@ -6529,29 +6528,31 @@  int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp,
 {
 	int ret = 0;
 
-	MA_STATE(mas, mt, min, max - size + 1);
+	MA_STATE(mas, mt, 0, 0);
 	if (!mt_is_alloc(mt))
 		return -EINVAL;
 
 	if (WARN_ON_ONCE(mt_is_reserved(entry)))
 		return -EINVAL;
 
-	if (min > max)
-		return -EINVAL;
-
-	if (max < size - 1)
-		return -EINVAL;
-
-	if (!size)
-		return -EINVAL;
-
 	mtree_lock(mt);
 retry:
-	ret = mas_rev_alloc(&mas, min, max, entry, size, startp);
-	if (mas_nomem(&mas, gfp))
-		goto retry;
-
+	ret = mas_empty_area_rev(&mas, min, max, size);
+	if (!ret) {
+		mas_insert(&mas, entry);
+		/*
+		 * mas_nomem() may release the lock, causing the allocated area
+		 * to be unavailable, so try to allocate a free area again.
+		 */
+		if (mas_nomem(&mas, gfp))
+			goto retry;
+	}
 	mtree_unlock(mt);
+	if (!ret) {
+		if (mas_is_err(&mas))
+			return xa_err(mas.node);
+		*startp = mas.index;
+	}
 	return ret;
 }
 EXPORT_SYMBOL(mtree_alloc_rrange);