Skip to contentSkip to conversation

mm/damon/core: avoid overflow in damon_feed_loop_next_input()

RFC PATCH In review SeongJae Park 2 participants 5 messages Sep 5, 2024 – Nov 1, 2024

Subsystems (2)
lore
Share & tools
lore

SeongJae Park

author maintainer
#0 lore raw

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

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

Fixes 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")

---
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(-)
mm/damon/core.c +27 -6
index 32677f13f437..1d951c2a1d85 100644
@@ -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;
 }
Signature · 1 line
2.39.2
Tested-by on v1 1/1
#1 lore raw
Quoted 7 lines · 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.

Fixes 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")

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.

Thanks,
Guenter

Quoted 54 lines

---
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(-)
mm/damon/core.c +27 -6
index 32677f13f437..1d951c2a1d85 100644
@@ -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 lore raw
In reply to SeongJae Park
Quoted 10 lines · 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.

Fixes 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")

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

author maintainer
#3 lore raw

Hi Guenter,

Quoted 12 lines · On Wed, 30 Oct 2024 21:18:51 -0700 Guenter Roeck <[email protected]> wrote:
Quoted 10 lines · 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.

Fixes 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")

---
As mentioned on the commit message, this is not yet sufficiently tested on 32bit machines. That's why this is RFC.

Quoted 2 lines

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

Quoted 2 lines

Guenter

Tested-by
#4 lore raw

Hi,

Quoted 16 lines · SeongJae Park

Hi Guenter,

Quoted 12 lines · On Wed, 30 Oct 2024 21:18:51 -0700 Guenter Roeck <[email protected]> wrote:
Quoted 10 lines · 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.

Fixes 9294a037c015 ("mm/damon/core: implement goal-oriented feedback-driven quota auto-tuning")

---
As mentioned on the commit message, this is not yet sufficiently tested on 32bit machines. That's why this is RFC.

Quoted 9 lines
Quoted 2 lines

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.

Quoted 5 lines

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.

Quoted 7 lines

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:

Thanks,
Guenter