[RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[SeongJae Park]

damon_feed_loop_next_input() is fragile to overflows.  Rewrite code to
avoid overflows.  This is not yet well tested on 32bit archs.

Reported-by: Guenter Roeck <linux@roeck-us.net>
Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net
Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")
Signed-off-by: SeongJae Park <sj@kernel.org>
---
As mentioned on the commit message, this is not yet sufficiently tested
on 32bit machines.  That's why this is RFC.

 mm/damon/core.c | 33 +++++++++++++++++++++++++++------
 1 file changed, 27 insertions(+), 6 deletions(-)

diff --git a/mm/damon/core.c b/mm/damon/core.c
index 32677f13f437..1d951c2a1d85 100644
--- a/mm/damon/core.c
+++ b/mm/damon/core.c
@@ -1494,15 +1494,36 @@ static unsigned long damon_feed_loop_next_input(unsigned long last_input,
 		unsigned long score)
 {
 	const unsigned long goal = 10000;
-	unsigned long score_goal_diff = max(goal, score) - min(goal, score);
-	unsigned long score_goal_diff_bp = score_goal_diff * 10000 / goal;
-	unsigned long compensation = last_input * score_goal_diff_bp / 10000;
 	/* Set minimum input as 10000 to avoid compensation be zero */
 	const unsigned long min_input = 10000;
+	unsigned long score_goal_diff;
+	unsigned long compensation;
+
+	if (score == goal)
+		return last_input;
+
+	/* last_input, score <= ULONG_MAX */
+	if (score < goal) {
+		score_goal_diff = goal - score;
+	} else {
+		/* if score_goal_diff > goal, will return min_input anyway */
+		score_goal_diff = min(score - goal, goal);
+	}
+
+	if (last_input < ULONG_MAX / score_goal_diff)
+		compensation = last_input * score_goal_diff / goal;
+	else
+		compensation = last_input / goal * score_goal_diff;
+
+	/* compensation <= last_input <= ULONG_MAX */
+
+	if (goal > score) {
+		if (last_input < ULONG_MAX - compensation)
+			return last_input + compensation;
+		return ULONG_MAX;
+	}
 
-	if (goal > score)
-		return last_input + compensation;
-	if (last_input > compensation + min_input)
+	if (last_input - compensation > min_input)
 		return last_input - compensation;
 	return min_input;
 }
-- 
2.39.2

Re: [RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[Guenter Roeck]

On 9/5/24 10:24, SeongJae Park wrote:
> damon_feed_loop_next_input() is fragile to overflows.  Rewrite code to
> avoid overflows.  This is not yet well tested on 32bit archs.
> 
> Reported-by: Guenter Roeck <linux@roeck-us.net>
> Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net
> Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")
> Signed-off-by: SeongJae Park <sj@kernel.org>

Passes all my testing except for

Failed unit tests:
	arm:mps2-an385:damon_test_ops_registration
	arm:mps2-an385:damon
	xtensa:de212:damon_test_ops_registration
	xtensa:de212:damon

which unrelated and not surprising since those are nommu systems.

Tested-by: Guenter Roeck <linux@roeck-us.net>

Thanks,
Guenter

> ---
> As mentioned on the commit message, this is not yet sufficiently tested
> on 32bit machines.  That's why this is RFC.
> 
>   mm/damon/core.c | 33 +++++++++++++++++++++++++++------
>   1 file changed, 27 insertions(+), 6 deletions(-)
> 
> diff --git a/mm/damon/core.c b/mm/damon/core.c
> index 32677f13f437..1d951c2a1d85 100644
> --- a/mm/damon/core.c
> +++ b/mm/damon/core.c
> @@ -1494,15 +1494,36 @@ static unsigned long damon_feed_loop_next_input(unsigned long last_input,
>   		unsigned long score)
>   {
>   	const unsigned long goal = 10000;
> -	unsigned long score_goal_diff = max(goal, score) - min(goal, score);
> -	unsigned long score_goal_diff_bp = score_goal_diff * 10000 / goal;
> -	unsigned long compensation = last_input * score_goal_diff_bp / 10000;
>   	/* Set minimum input as 10000 to avoid compensation be zero */
>   	const unsigned long min_input = 10000;
> +	unsigned long score_goal_diff;
> +	unsigned long compensation;
> +
> +	if (score == goal)
> +		return last_input;
> +
> +	/* last_input, score <= ULONG_MAX */
> +	if (score < goal) {
> +		score_goal_diff = goal - score;
> +	} else {
> +		/* if score_goal_diff > goal, will return min_input anyway */
> +		score_goal_diff = min(score - goal, goal);
> +	}
> +
> +	if (last_input < ULONG_MAX / score_goal_diff)
> +		compensation = last_input * score_goal_diff / goal;
> +	else
> +		compensation = last_input / goal * score_goal_diff;
> +
> +	/* compensation <= last_input <= ULONG_MAX */
> +
> +	if (goal > score) {
> +		if (last_input < ULONG_MAX - compensation)
> +			return last_input + compensation;
> +		return ULONG_MAX;
> +	}
>   
> -	if (goal > score)
> -		return last_input + compensation;
> -	if (last_input > compensation + min_input)
> +	if (last_input - compensation > min_input)
>   		return last_input - compensation;
>   	return min_input;
>   }

Re: [RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[Guenter Roeck]

On Thu, Sep 05, 2024 at 10:24:05AM -0700, SeongJae Park wrote:
> damon_feed_loop_next_input() is fragile to overflows.  Rewrite code to
> avoid overflows.  This is not yet well tested on 32bit archs.
> 
> Reported-by: Guenter Roeck <linux@roeck-us.net>
> Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net
> Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")
> Signed-off-by: SeongJae Park <sj@kernel.org>
> ---
> As mentioned on the commit message, this is not yet sufficiently tested
> on 32bit machines.  That's why this is RFC.

Is that patch going anywhere ? I have been testing it on a lot of 32-bit architectures,
and I do not see any failures.

Guenter

Re: [RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[SeongJae Park]

Hi Guenter,

On Wed, 30 Oct 2024 21:18:51 -0700 Guenter Roeck <linux@roeck-us.net> wrote:

> On Thu, Sep 05, 2024 at 10:24:05AM -0700, SeongJae Park wrote:
> > damon_feed_loop_next_input() is fragile to overflows.  Rewrite code to
> > avoid overflows.  This is not yet well tested on 32bit archs.
> > 
> > Reported-by: Guenter Roeck <linux@roeck-us.net>
> > Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net
> > Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")
> > Signed-off-by: SeongJae Park <sj@kernel.org>
> > ---
> > As mentioned on the commit message, this is not yet sufficiently tested
> > on 32bit machines.  That's why this is RFC.
> 
> Is that patch going anywhere ? I have been testing it on a lot of 32-bit architectures,
> and I do not see any failures.

Thank you for this nice reminder with the grateful test results, Guenter!

I was recently cleaning up the code and commit message, and testing on my own
with test setup.  I should confess that it took more than I expected in the
last RFC posting.  Sorry for the delay, and thank you for your patience.

I believe the patch is now in good form, but I was waiting just a couple of
more days before posting it, for a case that I find any mistake on it.  So
unless I find something wrong on the patch by Tomorrow morning (Pacific Time),
I will post it after dropping the RFC tag.

The current version of the patch to be posted is available at my patches
queue[1].  Please let me know if you find anything suspicious on it.

Thank you again for your patience and nice reminder!

[1] https://git.kernel.org/pub/scm/linux/kernel/git/sj/damon-hack.git/tree/patches/next/mm-damon-core-avoid-overflow-in-damon_feed_loop_next.patch?id=fb13d053bfdd5249bebdd1c253417f97cd41471e


Thanks,
SJ

> 
> Guenter

Re: [RFC PATCH] mm/damon/core: avoid overflow in damon_feed_loop_next_input()

[Guenter Roeck]

Hi,

On 10/30/24 22:21, SeongJae Park wrote:
> Hi Guenter,
> 
> On Wed, 30 Oct 2024 21:18:51 -0700 Guenter Roeck <linux@roeck-us.net> wrote:
> 
>> On Thu, Sep 05, 2024 at 10:24:05AM -0700, SeongJae Park wrote:
>>> damon_feed_loop_next_input() is fragile to overflows.  Rewrite code to
>>> avoid overflows.  This is not yet well tested on 32bit archs.
>>>
>>> Reported-by: Guenter Roeck <linux@roeck-us.net>
>>> Closes: https://lore.kernel.org/944f3d5b-9177-48e7-8ec9-7f1331a3fea3@roeck-us.net
>>> Fixes: 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")
>>> Signed-off-by: SeongJae Park <sj@kernel.org>
>>> ---
>>> As mentioned on the commit message, this is not yet sufficiently tested
>>> on 32bit machines.  That's why this is RFC.
>>
>> Is that patch going anywhere ? I have been testing it on a lot of 32-bit architectures,
>> and I do not see any failures.
> 
> Thank you for this nice reminder with the grateful test results, Guenter!
> 
> I was recently cleaning up the code and commit message, and testing on my own
> with test setup.  I should confess that it took more than I expected in the
> last RFC posting.  Sorry for the delay, and thank you for your patience.
> 
No worries; I just didn't want it to get lost.

> I believe the patch is now in good form, but I was waiting just a couple of
> more days before posting it, for a case that I find any mistake on it.  So
> unless I find something wrong on the patch by Tomorrow morning (Pacific Time),
> I will post it after dropping the RFC tag.
> 
> The current version of the patch to be posted is available at my patches
> queue[1].  Please let me know if you find anything suspicious on it.
> 
> Thank you again for your patience and nice reminder!
> 
> [1] https://git.kernel.org/pub/scm/linux/kernel/git/sj/damon-hack.git/tree/patches/next/mm-damon-core-avoid-overflow-in-damon_feed_loop_next.patch?id=fb13d053bfdd5249bebdd1c253417f97cd41471e
> 

I already got that version of the patch per e-mail yesterday. I re-tested it
in my testbed last night, and it (still) works as expected. So, again, for
the record:

Tested-by: Guenter Roeck <linux@roeck-us.net>

Thanks,
Guenter