[PATCH] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[PATCH] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[Zheng Yejian]

According to the logic of damon_va_evenly_split_region(), currently at
least following split cases would not meet the expectation:

  Suppose DAMON_MIN_REGION=0x1000,
  Case1: Split [0x0, 0x1100) into 1 pieces, then the result would be
         acutually [0x0, 0x1000), but NOT the expected [0x0, 0x1100) !!!
  Case2: Split [0x0, 0x3000) into 2 pieces, then the result would be
         acutually 3 regions:
           [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
         but NOT the expected 2 regions:
           [0x0, 0x1000), [0x1000, 0x3000) !!!

The root cause is that when calculating size of each split piece in
damon_va_evenly_split_region():

  `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`

both the dividing and the ALIGN_DOWN may cause loss of precision,
then each time split one piece of size 'sz_piece' from origin 'start' to
'end' would cause:
  1. For the above Case1, the 'end' value of the split 1 piece is
     aligned but not updated!!!
  2. For the above Case2, more pieces are split out than expected!!!

To fix it, in this patch:
- As for the expect to split 1 piece, just return 0;
- Count for each piece split and make sure no more than 'nr_pieces';
- Add above two cases into damon_test_split_evenly().

BTW, currently when running kunit test, DAMON_MIN_REGION is redefined
as 1, then above ALIGN_DOWN cases may not be test, since every int
value is ALIGN-ed to 1.

After this patch, damon-operations test passed:

 # ./tools/testing/kunit/kunit.py run damon-operations
 [...]
 ============== damon-operations (6 subtests) ===============
 [PASSED] damon_test_three_regions_in_vmas
 [PASSED] damon_test_apply_three_regions1
 [PASSED] damon_test_apply_three_regions2
 [PASSED] damon_test_apply_three_regions3
 [PASSED] damon_test_apply_three_regions4
 [PASSED] damon_test_split_evenly
 ================ [PASSED] damon-operations =================

Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
---
 mm/damon/tests/vaddr-kunit.h |  2 ++
 mm/damon/vaddr.c             | 13 +++++++++----
 2 files changed, 11 insertions(+), 4 deletions(-)

diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
index a339d117150f..b9a03e4e29e5 100644
--- a/mm/damon/tests/vaddr-kunit.h
+++ b/mm/damon/tests/vaddr-kunit.h
@@ -300,6 +300,8 @@ static void damon_test_split_evenly(struct kunit *test)
 	damon_test_split_evenly_fail(test, 0, 100, 0);
 	damon_test_split_evenly_succ(test, 0, 100, 10);
 	damon_test_split_evenly_succ(test, 5, 59, 5);
+	damon_test_split_evenly_succ(test, 4, 6, 1);
+	damon_test_split_evenly_succ(test, 0, 3, 2);
 	damon_test_split_evenly_fail(test, 5, 6, 2);
 }
 
diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
index 08cfd22b5249..1f3cebd20829 100644
--- a/mm/damon/vaddr.c
+++ b/mm/damon/vaddr.c
@@ -67,10 +67,14 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 	unsigned long sz_orig, sz_piece, orig_end;
 	struct damon_region *n = NULL, *next;
 	unsigned long start;
+	int i;
 
 	if (!r || !nr_pieces)
 		return -EINVAL;
 
+	if (nr_pieces == 1)
+		return 0;
+
 	orig_end = r->ar.end;
 	sz_orig = damon_sz_region(r);
 	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);
@@ -79,9 +83,11 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 		return -EINVAL;
 
 	r->ar.end = r->ar.start + sz_piece;
+	/* origin region will be updated as the first one after splitting */
+	i = 1;
+	n = r;
 	next = damon_next_region(r);
-	for (start = r->ar.end; start + sz_piece <= orig_end;
-			start += sz_piece) {
+	for (start = r->ar.end; i < nr_pieces; start += sz_piece, i++) {
 		n = damon_new_region(start, start + sz_piece);
 		if (!n)
 			return -ENOMEM;
@@ -89,8 +95,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 		r = n;
 	}
 	/* complement last region for possible rounding error */
-	if (n)
-		n->ar.end = orig_end;
+	n->ar.end = orig_end;
 
 	return 0;
 }
-- 
2.25.1

Re: [PATCH] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[SeongJae Park]

Hi Zheng,


Thank you for sharing this nice finding and fix!  I have a few comments below.

On Fri, 18 Oct 2024 11:53:04 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

> According to the logic of damon_va_evenly_split_region(), currently at
> least following split cases would not meet the expectation:
> 
>   Suppose DAMON_MIN_REGION=0x1000,
>   Case1: Split [0x0, 0x1100) into 1 pieces, then the result would be
>          acutually [0x0, 0x1000), but NOT the expected [0x0, 0x1100) !!!

Nice finding!  However, as long as DAMON_MIN_REGION is respected, [0x0, 0x1100]
region could not be created.  So, the problematic case cannot happen in real?
Please let me know if I'm missing something.

And, why would someone call the function with nr_pieces 1?

>   Case2: Split [0x0, 0x3000) into 2 pieces, then the result would be
>          acutually 3 regions:
>            [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
>          but NOT the expected 2 regions:
>            [0x0, 0x1000), [0x1000, 0x3000) !!!

Nice finding!

> 
> The root cause is that when calculating size of each split piece in
> damon_va_evenly_split_region():
> 
>   `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`
> 
> both the dividing and the ALIGN_DOWN may cause loss of precision,
> then each time split one piece of size 'sz_piece' from origin 'start' to
> 'end' would cause:
>   1. For the above Case1, the 'end' value of the split 1 piece is
>      aligned but not updated!!!
>   2. For the above Case2, more pieces are split out than expected!!!
> 
> To fix it, in this patch:
> - As for the expect to split 1 piece, just return 0;

As mentioned above, I think this is not needed, since the problematic case is
unreal.

> - Count for each piece split and make sure no more than 'nr_pieces';
> - Add above two cases into damon_test_split_evenly().

Thank you for adding tests!

> 
> BTW, currently when running kunit test, DAMON_MIN_REGION is redefined
> as 1, then above ALIGN_DOWN cases may not be test, since every int
> value is ALIGN-ed to 1.
> 
> After this patch, damon-operations test passed:
> 
>  # ./tools/testing/kunit/kunit.py run damon-operations
>  [...]
>  ============== damon-operations (6 subtests) ===============
>  [PASSED] damon_test_three_regions_in_vmas
>  [PASSED] damon_test_apply_three_regions1
>  [PASSED] damon_test_apply_three_regions2
>  [PASSED] damon_test_apply_three_regions3
>  [PASSED] damon_test_apply_three_regions4
>  [PASSED] damon_test_split_evenly
>  ================ [PASSED] damon-operations =================
> 
> Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
> ---
>  mm/damon/tests/vaddr-kunit.h |  2 ++
>  mm/damon/vaddr.c             | 13 +++++++++----
>  2 files changed, 11 insertions(+), 4 deletions(-)
> 
> diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
> index a339d117150f..b9a03e4e29e5 100644
> --- a/mm/damon/tests/vaddr-kunit.h
> +++ b/mm/damon/tests/vaddr-kunit.h
> @@ -300,6 +300,8 @@ static void damon_test_split_evenly(struct kunit *test)
>  	damon_test_split_evenly_fail(test, 0, 100, 0);
>  	damon_test_split_evenly_succ(test, 0, 100, 10);
>  	damon_test_split_evenly_succ(test, 5, 59, 5);
> +	damon_test_split_evenly_succ(test, 4, 6, 1);

If my above assumption (the first problem is unreal) is not wrong, maybe this
test is not needed?

> +	damon_test_split_evenly_succ(test, 0, 3, 2);

Nice.

>  	damon_test_split_evenly_fail(test, 5, 6, 2);
>  }
>  
> diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
> index 08cfd22b5249..1f3cebd20829 100644
> --- a/mm/damon/vaddr.c
> +++ b/mm/damon/vaddr.c
> @@ -67,10 +67,14 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>  	unsigned long sz_orig, sz_piece, orig_end;
>  	struct damon_region *n = NULL, *next;
>  	unsigned long start;
> +	int i;

Purpose of this variable is counting the number of splitted regions, and
comparing it against 'nr_pieces', right?  Because nr_pieces is 'unsigned int',
let's make this 'unsigned int' type, too.

>  
>  	if (!r || !nr_pieces)
>  		return -EINVAL;
>  
> +	if (nr_pieces == 1)
> +		return 0;
> +

As mentioned above, I don't think this is not needed.

>  	orig_end = r->ar.end;
>  	sz_orig = damon_sz_region(r);
>  	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);
> @@ -79,9 +83,11 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>  		return -EINVAL;
>  
>  	r->ar.end = r->ar.start + sz_piece;
> +	/* origin region will be updated as the first one after splitting */

I don't think this comment is easy to understand.  Let's just remove it.

> +	i = 1;
> +	n = r;

Why we need this? for 'nr_pieces == 1' case?  If so, I don't think we need to
take care about the case for the above mentioned reason.  Please let me know if
I'm missing something.

>  	next = damon_next_region(r);
> -	for (start = r->ar.end; start + sz_piece <= orig_end;
> -			start += sz_piece) {
> +	for (start = r->ar.end; i < nr_pieces; start += sz_piece, i++) {
>  		n = damon_new_region(start, start + sz_piece);
>  		if (!n)
>  			return -ENOMEM;
> @@ -89,8 +95,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>  		r = n;
>  	}
>  	/* complement last region for possible rounding error */
> -	if (n)
> -		n->ar.end = orig_end;
> +	n->ar.end = orig_end;

Maybe this change is related with the above 'n = r' line?  But, I don't think
we need that, as commented there.

>  
>  	return 0;
>  }
> -- 
> 2.25.1


Thanks,
SJ

Re: [PATCH] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[Zheng Yejian]

On 2024/10/19 02:33, SeongJae Park wrote:
> Hi Zheng,
> 
> 
> Thank you for sharing this nice finding and fix!  I have a few comments below.
> 

Thanks for your review!

> On Fri, 18 Oct 2024 11:53:04 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:
> 
>> According to the logic of damon_va_evenly_split_region(), currently at
>> least following split cases would not meet the expectation:
>>
>>    Suppose DAMON_MIN_REGION=0x1000,
>>    Case1: Split [0x0, 0x1100) into 1 pieces, then the result would be
>>           acutually [0x0, 0x1000), but NOT the expected [0x0, 0x1100) !!!
> 
> Nice finding!  However, as long as DAMON_MIN_REGION is respected, [0x0, 0x1100]
> region could not be created.  So, the problematic case cannot happen in real?
> Please let me know if I'm missing something.

Currently when DAMON_MIN_REGION is defined as PAGE_SIZE, and both vm start
and end are commonly page-aligned, then the [0x, 0x1100) could not be created,
but I'm not sure either.

> 
> And, why would someone call the function with nr_pieces 1?
> 

damon_va_evenly_split_region() is called in __damon_va_init_regions(), and nr_pieces
is calculated by:

   `nr_pieces = (regions[i].end - regions[i].start) / sz;`

Above regions[i].start/regions[i].end/sz is determine at runtime, and sz can beaffected
by minimum number of regions, user can change that, am I right? Then nr_pieces can be 1 !
On the other hand, I think damon_va_evenly_split_region() itself should handle
the 'nr_pieces == 1' case, or if we make sure that case is unreal, would it be better to
add some assertion?

>>    Case2: Split [0x0, 0x3000) into 2 pieces, then the result would be
>>           acutually 3 regions:
>>             [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
>>           but NOT the expected 2 regions:
>>             [0x0, 0x1000), [0x1000, 0x3000) !!!
> 
> Nice finding!
> 
>>
>> The root cause is that when calculating size of each split piece in
>> damon_va_evenly_split_region():
>>
>>    `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`
>>
>> both the dividing and the ALIGN_DOWN may cause loss of precision,
>> then each time split one piece of size 'sz_piece' from origin 'start' to
>> 'end' would cause:
>>    1. For the above Case1, the 'end' value of the split 1 piece is
>>       aligned but not updated!!!
>>    2. For the above Case2, more pieces are split out than expected!!!
>>
>> To fix it, in this patch:
>> - As for the expect to split 1 piece, just return 0;
> 
> As mentioned above, I think this is not needed, since the problematic case is
> unreal.

I think this case exists, as above reply.

> 
>> - Count for each piece split and make sure no more than 'nr_pieces';
>> - Add above two cases into damon_test_split_evenly().
> 
> Thank you for adding tests!
> 
>>
>> BTW, currently when running kunit test, DAMON_MIN_REGION is redefined
>> as 1, then above ALIGN_DOWN cases may not be test, since every int
>> value is ALIGN-ed to 1.
>>
>> After this patch, damon-operations test passed:
>>
>>   # ./tools/testing/kunit/kunit.py run damon-operations
>>   [...]
>>   ============== damon-operations (6 subtests) ===============
>>   [PASSED] damon_test_three_regions_in_vmas
>>   [PASSED] damon_test_apply_three_regions1
>>   [PASSED] damon_test_apply_three_regions2
>>   [PASSED] damon_test_apply_three_regions3
>>   [PASSED] damon_test_apply_three_regions4
>>   [PASSED] damon_test_split_evenly
>>   ================ [PASSED] damon-operations =================
>>
>> Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
>> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
>> ---
>>   mm/damon/tests/vaddr-kunit.h |  2 ++
>>   mm/damon/vaddr.c             | 13 +++++++++----
>>   2 files changed, 11 insertions(+), 4 deletions(-)
>>
>> diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
>> index a339d117150f..b9a03e4e29e5 100644
>> --- a/mm/damon/tests/vaddr-kunit.h
>> +++ b/mm/damon/tests/vaddr-kunit.h
>> @@ -300,6 +300,8 @@ static void damon_test_split_evenly(struct kunit *test)
>>   	damon_test_split_evenly_fail(test, 0, 100, 0);
>>   	damon_test_split_evenly_succ(test, 0, 100, 10);
>>   	damon_test_split_evenly_succ(test, 5, 59, 5);
>> +	damon_test_split_evenly_succ(test, 4, 6, 1);
> 
> If my above assumption (the first problem is unreal) is not wrong, maybe this
> test is not needed?
> 

As an unit test, damon_va_evenly_split_region() itself should be able
to handle the 'nr_pieces == 1' case, right? I think this testcase can
be added in case something goes wrong one day.

>> +	damon_test_split_evenly_succ(test, 0, 3, 2);
> 
> Nice.
> 
>>   	damon_test_split_evenly_fail(test, 5, 6, 2);
>>   }
>>   
>> diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
>> index 08cfd22b5249..1f3cebd20829 100644
>> --- a/mm/damon/vaddr.c
>> +++ b/mm/damon/vaddr.c
>> @@ -67,10 +67,14 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>>   	unsigned long sz_orig, sz_piece, orig_end;
>>   	struct damon_region *n = NULL, *next;
>>   	unsigned long start;
>> +	int i;
> 
> Purpose of this variable is counting the number of splitted regions, and
> comparing it against 'nr_pieces', right?  Because nr_pieces is 'unsigned int',
> let's make this 'unsigned int' type, too.
> 

Well, yes, I'll do it in v2 after all the discussions for this version are complete!

>>   
>>   	if (!r || !nr_pieces)
>>   		return -EINVAL;
>>   
>> +	if (nr_pieces == 1)
>> +		return 0;
>> +
> 
> As mentioned above, I don't think this is not needed.
> 



>>   	orig_end = r->ar.end;
>>   	sz_orig = damon_sz_region(r);
>>   	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);
>> @@ -79,9 +83,11 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>>   		return -EINVAL;
>>   
>>   	r->ar.end = r->ar.start + sz_piece;
>> +	/* origin region will be updated as the first one after splitting */
> 
> I don't think this comment is easy to understand.  Let's just remove it.
> 

Thanks, I'll remove it in next version!

>> +	i = 1;
>> +	n = r;
> 
> Why we need this? for 'nr_pieces == 1' case?  If so, I don't think we need to
> take care about the case for the above mentioned reason.  Please let me know if
> I'm missing something.

Yes, this is for 'nr_pieces == 1' case, and if we have above `if (nr_pieces == 1) return 0;` line,
then this is not needed since nr_pieces > 1, and following loop will at least two times

> 
>>   	next = damon_next_region(r);
>> -	for (start = r->ar.end; start + sz_piece <= orig_end;
>> -			start += sz_piece) {
>> +	for (start = r->ar.end; i < nr_pieces; start += sz_piece, i++) {
>>   		n = damon_new_region(start, start + sz_piece);
>>   		if (!n)
>>   			return -ENOMEM;
>> @@ -89,8 +95,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
>>   		r = n;
>>   	}
>>   	/* complement last region for possible rounding error */
>> -	if (n)
>> -		n->ar.end = orig_end;
>> +	n->ar.end = orig_end;
> 
> Maybe this change is related with the above 'n = r' line?  But, I don't think
> we need that, as commented there.

Yes, they related.

> 
>>   
>>   	return 0;
>>   }
>> -- 
>> 2.25.1
> 
> 
> Thanks,
> SJ

-- 
Thanks,
Zheng Yejian

Re: [PATCH] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[SeongJae Park]

On Mon, 21 Oct 2024 11:56:04 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

> On 2024/10/19 02:33, SeongJae Park wrote:
> > Hi Zheng,
> > 
> > 
> > Thank you for sharing this nice finding and fix!  I have a few comments below.
> > 
> 
> Thanks for your review!
> 
> > On Fri, 18 Oct 2024 11:53:04 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:
> > 
> >> According to the logic of damon_va_evenly_split_region(), currently at
> >> least following split cases would not meet the expectation:
> >>
> >>    Suppose DAMON_MIN_REGION=0x1000,
> >>    Case1: Split [0x0, 0x1100) into 1 pieces, then the result would be
> >>           acutually [0x0, 0x1000), but NOT the expected [0x0, 0x1100) !!!
> > 
> > Nice finding!  However, as long as DAMON_MIN_REGION is respected, [0x0, 0x1100]
> > region could not be created.  So, the problematic case cannot happen in real?
> > Please let me know if I'm missing something.
> 
> Currently when DAMON_MIN_REGION is defined as PAGE_SIZE, and both vm start
> and end are commonly page-aligned, then the [0x, 0x1100) could not be created,
> but I'm not sure either.

Thank you for confirming.  If there is a way that DAMON could generate
[0x, 0x1100], that's a bug that deserves its own fix.  So let's assume it
cannot happen for now.

> 
> > 
> > And, why would someone call the function with nr_pieces 1?
> > 
> 
> damon_va_evenly_split_region() is called in __damon_va_init_regions(), and nr_pieces
> is calculated by:
> 
>    `nr_pieces = (regions[i].end - regions[i].start) / sz;`
> 
> Above regions[i].start/regions[i].end/sz is determine at runtime, and sz can
> beaffected by minimum number of regions, user can change that, am I right?
> Then nr_pieces can be 1 !

You're right, thank you.

Now, the next question would be, could that ('damon_va_evenly_split_region()'
being called with 1 'nr_pieces') trigger some issues?  Based on the code, I
don't think so.  Please let me know if I'm missing some corner cases.

> On the other hand, I think damon_va_evenly_split_region() itself should
> handle the 'nr_pieces == 1' case, or if we make sure that case is unreal,
> would it be better to add some assertion?

Nice suggestion, thanks.  I agree that making it be handled is better in terms
of maintenance.  It would make the code much easier to read.

It wouldn't be for a fix of a bug, but for making the code easier to read.  So
I think posting it as a separate patch is better.  If you don't mind, please
post a patch.

> 
> >>    Case2: Split [0x0, 0x3000) into 2 pieces, then the result would be
> >>           acutually 3 regions:
> >>             [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
> >>           but NOT the expected 2 regions:
> >>             [0x0, 0x1000), [0x1000, 0x3000) !!!
> > 
> > Nice finding!
> > 
> >>
> >> The root cause is that when calculating size of each split piece in
> >> damon_va_evenly_split_region():
> >>
> >>    `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`
> >>
> >> both the dividing and the ALIGN_DOWN may cause loss of precision,
> >> then each time split one piece of size 'sz_piece' from origin 'start' to
> >> 'end' would cause:
> >>    1. For the above Case1, the 'end' value of the split 1 piece is
> >>       aligned but not updated!!!
> >>    2. For the above Case2, more pieces are split out than expected!!!
> >>
> >> To fix it, in this patch:
> >> - As for the expect to split 1 piece, just return 0;
> > 
> > As mentioned above, I think this is not needed, since the problematic case is
> > unreal.
> 
> I think this case exists, as above reply.

A case that damon_va_evenly_split_region() is called with nr_pieces of value 1
exists.

A case that the function is called with DAMON_MIN_REGION un-aligned region
doesn't exist (unless there is a bug).

I was saying about the second case.  I still agree doing the nr_pieces check is
good for readability, so please post a patch if you don't mind.

> 
> > 
> >> - Count for each piece split and make sure no more than 'nr_pieces';
> >> - Add above two cases into damon_test_split_evenly().
> > 
> > Thank you for adding tests!
> > 
> >>
> >> BTW, currently when running kunit test, DAMON_MIN_REGION is redefined
> >> as 1, then above ALIGN_DOWN cases may not be test, since every int
> >> value is ALIGN-ed to 1.
> >>
> >> After this patch, damon-operations test passed:
> >>
> >>   # ./tools/testing/kunit/kunit.py run damon-operations
> >>   [...]
> >>   ============== damon-operations (6 subtests) ===============
> >>   [PASSED] damon_test_three_regions_in_vmas
> >>   [PASSED] damon_test_apply_three_regions1
> >>   [PASSED] damon_test_apply_three_regions2
> >>   [PASSED] damon_test_apply_three_regions3
> >>   [PASSED] damon_test_apply_three_regions4
> >>   [PASSED] damon_test_split_evenly
> >>   ================ [PASSED] damon-operations =================
> >>
> >> Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
> >> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
> >> ---
> >>   mm/damon/tests/vaddr-kunit.h |  2 ++
> >>   mm/damon/vaddr.c             | 13 +++++++++----
> >>   2 files changed, 11 insertions(+), 4 deletions(-)
> >>
> >> diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
> >> index a339d117150f..b9a03e4e29e5 100644
> >> --- a/mm/damon/tests/vaddr-kunit.h
> >> +++ b/mm/damon/tests/vaddr-kunit.h
> >> @@ -300,6 +300,8 @@ static void damon_test_split_evenly(struct kunit *test)
> >>   	damon_test_split_evenly_fail(test, 0, 100, 0);
> >>   	damon_test_split_evenly_succ(test, 0, 100, 10);
> >>   	damon_test_split_evenly_succ(test, 5, 59, 5);
> >> +	damon_test_split_evenly_succ(test, 4, 6, 1);
> > 
> > If my above assumption (the first problem is unreal) is not wrong, maybe this
> > test is not needed?
> > 
> 
> As an unit test, damon_va_evenly_split_region() itself should be able
> to handle the 'nr_pieces == 1' case, right? I think this testcase can
> be added in case something goes wrong one day.

I agree.  Nonetheless, let's make it be separated with the real bug fix.

> 
> >> +	damon_test_split_evenly_succ(test, 0, 3, 2);
> > 
> > Nice.
> > 
> >>   	damon_test_split_evenly_fail(test, 5, 6, 2);
> >>   }
> >>   
> >> diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
> >> index 08cfd22b5249..1f3cebd20829 100644
> >> --- a/mm/damon/vaddr.c
> >> +++ b/mm/damon/vaddr.c
> >> @@ -67,10 +67,14 @@ static int damon_va_evenly_split_region(struct damon_target *t,
> >>   	unsigned long sz_orig, sz_piece, orig_end;
> >>   	struct damon_region *n = NULL, *next;
> >>   	unsigned long start;
> >> +	int i;
> > 
> > Purpose of this variable is counting the number of splitted regions, and
> > comparing it against 'nr_pieces', right?  Because nr_pieces is 'unsigned int',
> > let's make this 'unsigned int' type, too.
> > 
> 
> Well, yes, I'll do it in v2 after all the discussions for this version are complete!

Thanks :)

> 
> >>   
> >>   	if (!r || !nr_pieces)
> >>   		return -EINVAL;
> >>   
> >> +	if (nr_pieces == 1)
> >> +		return 0;
> >> +
> > 
> > As mentioned above, I don't think this is not needed.

As mentioned above, now I think having this is good for readability, but let's
make it an individual change that separated from the real bug fix.

> > 
> 
> 
> 
> >>   	orig_end = r->ar.end;
> >>   	sz_orig = damon_sz_region(r);
> >>   	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);
> >> @@ -79,9 +83,11 @@ static int damon_va_evenly_split_region(struct damon_target *t,
> >>   		return -EINVAL;
> >>   
> >>   	r->ar.end = r->ar.start + sz_piece;
> >> +	/* origin region will be updated as the first one after splitting */
> > 
> > I don't think this comment is easy to understand.  Let's just remove it.
> > 
> 
> Thanks, I'll remove it in next version!
> 
> >> +	i = 1;
> >> +	n = r;
> > 
> > Why we need this? for 'nr_pieces == 1' case?  If so, I don't think we need to
> > take care about the case for the above mentioned reason.  Please let me know if
> > I'm missing something.
> 
> Yes, this is for 'nr_pieces == 1' case, and if we have above `if (nr_pieces == 1) return 0;` line,
> then this is not needed since nr_pieces > 1, and following loop will at least two times
> 
> > 
> >>   	next = damon_next_region(r);
> >> -	for (start = r->ar.end; start + sz_piece <= orig_end;
> >> -			start += sz_piece) {
> >> +	for (start = r->ar.end; i < nr_pieces; start += sz_piece, i++) {
> >>   		n = damon_new_region(start, start + sz_piece);
> >>   		if (!n)
> >>   			return -ENOMEM;
> >> @@ -89,8 +95,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
> >>   		r = n;
> >>   	}
> >>   	/* complement last region for possible rounding error */
> >> -	if (n)
> >> -		n->ar.end = orig_end;
> >> +	n->ar.end = orig_end;
> > 
> > Maybe this change is related with the above 'n = r' line?  But, I don't think
> > we need that, as commented there.
> 
> Yes, they related.

Thank you for confirming.

> 
> > 
> >>   
> >>   	return 0;
> >>   }
> >> -- 
> >> 2.25.1
> > 
> > 
> > Thanks,
> > SJ
> 
> -- 
> Thanks,
> Zheng Yejian

So, let's add the 'nr_pieces == 1' check, but as a change that separated from
the real bug fix.  I'm looking forward to your next posts, Zheng :)

Nonetheless, please note that the real bug is not somewhat critical for users.
It only has a potential to slightly degrade the best-effort accuracy of DAMON
in corner cases.


Thanks,
SJ

[PATCH v2 0/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[Zheng Yejian]

According to the logic of damon_va_evenly_split_region(), currently
following split case would not meet the expectation:

  Suppose DAMON_MIN_REGION=0x1000,
  Case: Split [0x0, 0x3000) into 2 pieces, then the result would be
        acutually 3 regions:
          [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
        but NOT the expected 2 regions:
          [0x0, 0x1000), [0x1000, 0x3000) !!!

The root cause is that when calculating size of each split piece in
damon_va_evenly_split_region():

  `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`

both the dividing and the ALIGN_DOWN may cause loss of precision,
then each time split one piece of size 'sz_piece' from origin 'start' to
'end' would cause more pieces are split out than expected!!!

To fix it, count for each piece split and make sure no more than
'nr_pieces'. In addition, add above case into damon_test_split_evenly().

And add 'nr_piece == 1' check in damon_va_evenly_split_region()
for better code readability and add a corresponding kunit testcase.

Zheng Yejian (2):
  mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()
  mm/damon/vaddr: Check 'nr_piece == 1' case in
    damon_va_evenly_split_region()

 mm/damon/tests/vaddr-kunit.h | 2 ++
 mm/damon/vaddr.c             | 7 +++++--
 2 files changed, 7 insertions(+), 2 deletions(-)

-- 
2.25.1

[PATCH v2 1/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[Zheng Yejian]

According to the logic of damon_va_evenly_split_region(), currently
following split case would not meet the expectation:

  Suppose DAMON_MIN_REGION=0x1000,
  Case: Split [0x0, 0x3000) into 2 pieces, then the result would be
        acutually 3 regions:
          [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
        but NOT the expected 2 regions:
          [0x0, 0x1000), [0x1000, 0x3000) !!!

The root cause is that when calculating size of each split piece in
damon_va_evenly_split_region():

  `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`

both the dividing and the ALIGN_DOWN may cause loss of precision,
then each time split one piece of size 'sz_piece' from origin 'start' to
'end' would cause more pieces are split out than expected!!!

To fix it, count for each piece split and make sure no more than
'nr_pieces'. In addition, add above case into damon_test_split_evenly().

After this patch, damon-operations test passed:

 # ./tools/testing/kunit/kunit.py run damon-operations
 [...]
 ============== damon-operations (6 subtests) ===============
 [PASSED] damon_test_three_regions_in_vmas
 [PASSED] damon_test_apply_three_regions1
 [PASSED] damon_test_apply_three_regions2
 [PASSED] damon_test_apply_three_regions3
 [PASSED] damon_test_apply_three_regions4
 [PASSED] damon_test_split_evenly
 ================ [PASSED] damon-operations =================

Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
---

v1 -> v2:
- Move 'nr_pieces == 1' check into separate patch and update commit messages;
- Change type of variable 'i' to be 'unsigned int';
- Remove a puzzling comment;

v1: https://lore.kernel.org/all/20241018035304.1050135-1-zhengyejian@huaweicloud.com/

 mm/damon/tests/vaddr-kunit.h | 1 +
 mm/damon/vaddr.c             | 4 ++--
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
index a339d117150f..a149e354bb26 100644
--- a/mm/damon/tests/vaddr-kunit.h
+++ b/mm/damon/tests/vaddr-kunit.h
@@ -300,6 +300,7 @@ static void damon_test_split_evenly(struct kunit *test)
 	damon_test_split_evenly_fail(test, 0, 100, 0);
 	damon_test_split_evenly_succ(test, 0, 100, 10);
 	damon_test_split_evenly_succ(test, 5, 59, 5);
+	damon_test_split_evenly_succ(test, 0, 3, 2);
 	damon_test_split_evenly_fail(test, 5, 6, 2);
 }
 
diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
index 08cfd22b5249..dba3b2f4d758 100644
--- a/mm/damon/vaddr.c
+++ b/mm/damon/vaddr.c
@@ -67,6 +67,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 	unsigned long sz_orig, sz_piece, orig_end;
 	struct damon_region *n = NULL, *next;
 	unsigned long start;
+	unsigned int i;
 
 	if (!r || !nr_pieces)
 		return -EINVAL;
@@ -80,8 +81,7 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 
 	r->ar.end = r->ar.start + sz_piece;
 	next = damon_next_region(r);
-	for (start = r->ar.end; start + sz_piece <= orig_end;
-			start += sz_piece) {
+	for (start = r->ar.end, i = 1; i < nr_pieces; start += sz_piece, i++) {
 		n = damon_new_region(start, start + sz_piece);
 		if (!n)
 			return -ENOMEM;
-- 
2.25.1

Re: [PATCH v2 1/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[SeongJae Park]

Hi Zheng,


We Cc kunit folks for any DAMON kunit test changes, so I Cc-ed them.

On Tue, 22 Oct 2024 16:39:26 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

> According to the logic of damon_va_evenly_split_region(), currently
> following split case would not meet the expectation:
> 
>   Suppose DAMON_MIN_REGION=0x1000,
>   Case: Split [0x0, 0x3000) into 2 pieces, then the result would be
>         acutually 3 regions:
>           [0x0, 0x1000), [0x1000, 0x2000), [0x2000, 0x3000)
>         but NOT the expected 2 regions:
>           [0x0, 0x1000), [0x1000, 0x3000) !!!
> 
> The root cause is that when calculating size of each split piece in
> damon_va_evenly_split_region():
> 
>   `sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);`
> 
> both the dividing and the ALIGN_DOWN may cause loss of precision,
> then each time split one piece of size 'sz_piece' from origin 'start' to
> 'end' would cause more pieces are split out than expected!!!
> 
> To fix it, count for each piece split and make sure no more than
> 'nr_pieces'. In addition, add above case into damon_test_split_evenly().
> 
> After this patch, damon-operations test passed:

Just for a clarification.  damon-operations test doesn't fail without this
patch.  This patch introduces two changes.  A new kunit test, and a bug fix.
Without the bug fix, the new kunit test fails.

I usually prefer separating test changes from fixes (introduc a fix first, and
then the test for it, to avoid unnecessary test failures).  But, given the
small size and the simplicity of the kunit change for this patch, I think
introducing it together with the fix is ok.

> 
>  # ./tools/testing/kunit/kunit.py run damon-operations
>  [...]
>  ============== damon-operations (6 subtests) ===============
>  [PASSED] damon_test_three_regions_in_vmas
>  [PASSED] damon_test_apply_three_regions1
>  [PASSED] damon_test_apply_three_regions2
>  [PASSED] damon_test_apply_three_regions3
>  [PASSED] damon_test_apply_three_regions4
>  [PASSED] damon_test_split_evenly
>  ================ [PASSED] damon-operations =================
> 
> Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>

Reviewed-by: SeongJae Park <sj@kernel.org>


Thanks,
SJ

[...]

Re: [PATCH v2 1/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[SeongJae Park]

On Tue, 22 Oct 2024 16:39:26 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

[...]
> Fixes: 3f49584b262c ("mm/damon: implement primitives for the virtual memory address spaces")
> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
> ---
> 
> v1 -> v2:
> - Move 'nr_pieces == 1' check into separate patch and update commit messages;
> - Change type of variable 'i' to be 'unsigned int';
> - Remove a puzzling comment;
> 
> v1: https://lore.kernel.org/all/20241018035304.1050135-1-zhengyejian@huaweicloud.com/

Nit.  If the patch series has a cover letter, we usually put this kind of
revision history on the cover letter.


Thanks,
SJ

[...]

[PATCH v2 2/2] mm/damon/vaddr: Add 'nr_piece == 1' check in damon_va_evenly_split_region()

[Zheng Yejian]

As discussed in [1], damon_va_evenly_split_region() is called to
size-evenly split a region into 'nr_pieces' small regions,
when nr_pieces == 1, no actual split is required. Check that case
for better code readability and add a simple kunit testcase.

[1] https://lore.kernel.org/all/20241021163316.12443-1-sj@kernel.org/

Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>
---
 mm/damon/tests/vaddr-kunit.h | 1 +
 mm/damon/vaddr.c             | 3 +++
 2 files changed, 4 insertions(+)

diff --git a/mm/damon/tests/vaddr-kunit.h b/mm/damon/tests/vaddr-kunit.h
index a149e354bb26..b9a03e4e29e5 100644
--- a/mm/damon/tests/vaddr-kunit.h
+++ b/mm/damon/tests/vaddr-kunit.h
@@ -300,6 +300,7 @@ static void damon_test_split_evenly(struct kunit *test)
 	damon_test_split_evenly_fail(test, 0, 100, 0);
 	damon_test_split_evenly_succ(test, 0, 100, 10);
 	damon_test_split_evenly_succ(test, 5, 59, 5);
+	damon_test_split_evenly_succ(test, 4, 6, 1);
 	damon_test_split_evenly_succ(test, 0, 3, 2);
 	damon_test_split_evenly_fail(test, 5, 6, 2);
 }
diff --git a/mm/damon/vaddr.c b/mm/damon/vaddr.c
index dba3b2f4d758..25db0a582c27 100644
--- a/mm/damon/vaddr.c
+++ b/mm/damon/vaddr.c
@@ -72,6 +72,9 @@ static int damon_va_evenly_split_region(struct damon_target *t,
 	if (!r || !nr_pieces)
 		return -EINVAL;
 
+	if (nr_pieces == 1)
+		return 0;
+
 	orig_end = r->ar.end;
 	sz_orig = damon_sz_region(r);
 	sz_piece = ALIGN_DOWN(sz_orig / nr_pieces, DAMON_MIN_REGION);
-- 
2.25.1

Re: [PATCH v2 2/2] mm/damon/vaddr: Add 'nr_piece == 1' check in damon_va_evenly_split_region()

[SeongJae Park]

Hi Zheng,


Cc-ed kunit folks, as we usually do for DAMON kunit test changes.

On Tue, 22 Oct 2024 16:39:27 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

> As discussed in [1], damon_va_evenly_split_region() is called to
> size-evenly split a region into 'nr_pieces' small regions,
> when nr_pieces == 1, no actual split is required. Check that case
> for better code readability and add a simple kunit testcase.
> 
> [1] https://lore.kernel.org/all/20241021163316.12443-1-sj@kernel.org/
> 
> Signed-off-by: Zheng Yejian <zhengyejian@huaweicloud.com>

Reviewed-by: SeongJae Park <sj@kernel.org>


Thanks,
SJ

[...]

Re: [PATCH v2 0/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[SeongJae Park]

Hi Zheng,

On Tue, 22 Oct 2024 16:39:25 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:

[...]
> To fix it, count for each piece split and make sure no more than
> 'nr_pieces'. In addition, add above case into damon_test_split_evenly().
> 
> And add 'nr_piece == 1' check in damon_va_evenly_split_region()
> for better code readability and add a corresponding kunit testcase.
> 
> Zheng Yejian (2):
>   mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()
>   mm/damon/vaddr: Check 'nr_piece == 1' case in
>     damon_va_evenly_split_region()
> 
>  mm/damon/tests/vaddr-kunit.h | 2 ++
>  mm/damon/vaddr.c             | 7 +++++--
>  2 files changed, 7 insertions(+), 2 deletions(-)

Thank you for addressing my comments and posting this new patch series.  I
added my Reviewed-by: tags with some trivial comments to the patches.

Btw, at least on DAMON mailing list, we usually post new revisions as new
threads, rather than as a reply to the previous revision.  If you want to make
sure involved people aware of the new series, you can send the lore link for
the new series as a reply to the previous revision.


Thanks,
SJ

Re: [PATCH v2 0/2] mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()

[Zheng Yejian]

On 2024/10/23 02:05, SeongJae Park wrote:
> Hi Zheng,
> 
> On Tue, 22 Oct 2024 16:39:25 +0800 Zheng Yejian <zhengyejian@huaweicloud.com> wrote:
> 
> [...]
>> To fix it, count for each piece split and make sure no more than
>> 'nr_pieces'. In addition, add above case into damon_test_split_evenly().
>>
>> And add 'nr_piece == 1' check in damon_va_evenly_split_region()
>> for better code readability and add a corresponding kunit testcase.
>>
>> Zheng Yejian (2):
>>    mm/damon/vaddr: Fix issue in damon_va_evenly_split_region()
>>    mm/damon/vaddr: Check 'nr_piece == 1' case in
>>      damon_va_evenly_split_region()
>>
>>   mm/damon/tests/vaddr-kunit.h | 2 ++
>>   mm/damon/vaddr.c             | 7 +++++--
>>   2 files changed, 7 insertions(+), 2 deletions(-)
> 
> Thank you for addressing my comments and posting this new patch series.  I
> added my Reviewed-by: tags with some trivial comments to the patches.
> 

Thanks for your review and comments !

> Btw, at least on DAMON mailing list, we usually post new revisions as new
> threads, rather than as a reply to the previous revision.  If you want to make
> sure involved people aware of the new series, you can send the lore link for
> the new series as a reply to the previous revision.
> 

Got it :)

> 
> Thanks,
> SJ

-- 
Thanks,
Zheng Yejian