[RFC PATCH 2/3] mm/damon/core: avoid overflows in monitoring results calculations

[DaeMyung Kang <charsyam@gmail.com>]

When monitoring intervals change, DAMON converts region ages and sample
counts for the new intervals.  The conversions overflow before division:

- damon_age_for_new_attrs() multiplies the age by the old aggregation
  interval in unsigned long.  On 32-bit kernels, the default 100 ms
  interval makes this overflow after about 72 minutes.
- The sample ratio conversions multiply unsigned int values.  They can
  overflow on every architecture when an aggregation has more than
  429,496 samples, such as a 1 ms sample interval and a 430 second
  aggregation interval.

The moving sums also use mult_frac() for the fraction of an aggregation
window that remains and for the previous window's contribution.  On
32-bit kernels, both can overflow with long aggregation intervals.  For
example, 500,000 remaining samples of a 600,000-sample window are
8,333 bp, but the first calculation returns 1,175 bp.

Add damon_mult_frac(), which preserves mult_frac() results when its
intermediates fit, calculates larger remainder products in full width,
and saturates results that exceed unsigned long.  Use it for the
conversions and the moving sums.  Saturate the unsigned int conversion
results at UINT_MAX.

Add KUnit coverage for the helper, the conversions, and the moving sums.

The conversion issues were discovered [1] by Sashiko.

[1] https://lore.kernel.org/20260708140944.F26821F000E9@smtp.kernel.org

Fixes: 2f5bef5a590b ("mm/damon/core: update monitoring results for new monitoring attributes")
Fixes: 9f3786d8602f ("mm/damon/core: introduce damon_nr_accesses_mvsum()")
Fixes: 2ec26dd341d1 ("mm/damon/core: introduce damon_probe_hits_mvsum()")
Signed-off-by: DaeMyung Kang <charsyam@gmail.com>
---
 mm/damon/core.c             | 41 +++++++++++++++++---
 mm/damon/tests/core-kunit.h | 74 +++++++++++++++++++++++++++++++++++++
 2 files changed, 109 insertions(+), 6 deletions(-)

diff --git a/mm/damon/core.c b/mm/damon/core.c
index 73b571b429cb..5cd4007cc370 100644
--- a/mm/damon/core.c
+++ b/mm/damon/core.c
@@ -281,6 +281,32 @@ static bool damon_has_probe_weights(struct damon_ctx *c)
 	return false;
 }
 
+/*
+ * damon_mult_frac() - calculate @x * @n / @d without overflowing.
+ *
+ * Same as mult_frac(), but the intermediate product of the remainder does not
+ * overflow, and a result that does not fit in unsigned long is saturated to
+ * ULONG_MAX.  Returns the same value as mult_frac() when mult_frac() does not
+ * overflow.  @d must not be zero.
+ */
+static unsigned long damon_mult_frac(unsigned long x, unsigned long n,
+		unsigned long d)
+{
+	unsigned long q = x / d, r = x % d;
+	unsigned long frac;
+
+	if (n && q > ULONG_MAX / n)
+		return ULONG_MAX;
+	if (!n || r <= ULONG_MAX / n)
+		frac = r * n / d;
+	else
+		/* r < d, so the quotient is smaller than n */
+		frac = mul_u64_u64_div_u64(r, n, d);
+	if (frac > ULONG_MAX - q * n)
+		return ULONG_MAX;
+	return q * n + frac;
+}
+
 /*
  * damon_mvsum() - Returns pseudo moving sum value for a time window.
  * @current_nr:		The value of the current aggregation window.
@@ -305,7 +331,7 @@ static bool damon_has_probe_weights(struct damon_ctx *c)
 static unsigned long damon_mvsum(unsigned long current_nr,
 		unsigned long last_nr, unsigned long left_window_bp)
 {
-	return current_nr + mult_frac(last_nr, left_window_bp, 10000);
+	return current_nr + damon_mult_frac(last_nr, left_window_bp, 10000);
 }
 
 /**
@@ -337,7 +363,7 @@ unsigned int damon_nr_accesses_mvsum(struct damon_region *r,
 	else
 		left_window = ctx->next_aggregation_sis -
 			ctx->passed_sample_intervals;
-	left_window_bp = mult_frac(left_window, 10000, window_len);
+	left_window_bp = damon_mult_frac(left_window, 10000, window_len);
 
 	if (left_window_bp == 10000)
 		return r->last_nr_accesses;
@@ -361,7 +387,7 @@ unsigned char damon_probe_hits_mvsum(int probe_idx, struct damon_region *r,
 	else
 		left_window = ctx->next_aggregation_sis -
 			ctx->passed_sample_intervals;
-	left_window_bp = mult_frac(left_window, 10000, window_len);
+	left_window_bp = damon_mult_frac(left_window, 10000, window_len);
 
 	if (left_window_bp == 10000)
 		return r->last_probe_hits[probe_idx];
@@ -990,21 +1016,24 @@ static bool damon_attrs_equals(const struct damon_attrs *attrs1,
 static unsigned int damon_age_for_new_attrs(unsigned int age,
 		struct damon_attrs *old_attrs, struct damon_attrs *new_attrs)
 {
-	return age * old_attrs->aggr_interval / new_attrs->aggr_interval;
+	return min(damon_mult_frac(age, old_attrs->aggr_interval,
+				new_attrs->aggr_interval), UINT_MAX);
 }
 
 /* convert sample ratio in bp (per 10,000) to count */
 static unsigned int damon_sample_bp_to_count(
 		unsigned int bp, struct damon_attrs *attrs)
 {
-	return bp * damon_nr_samples_per_aggr(attrs) / 10000;
+	return min(damon_mult_frac(bp, damon_nr_samples_per_aggr(attrs),
+				10000), UINT_MAX);
 }
 
 /* convert sample count to ratio in bp (per 10,000) */
 static unsigned int damon_sample_count_to_bp(
 		unsigned int count, struct damon_attrs *attrs)
 {
-	return mult_frac(count, 10000, damon_nr_samples_per_aggr(attrs));
+	return min(damon_mult_frac(count, 10000,
+				damon_nr_samples_per_aggr(attrs)), UINT_MAX);
 }
 
 static unsigned int damon_nr_samples_for_new_attrs(unsigned int nr,
diff --git a/mm/damon/tests/core-kunit.h b/mm/damon/tests/core-kunit.h
index 43e2f950f8ff..e71e60d59400 100644
--- a/mm/damon/tests/core-kunit.h
+++ b/mm/damon/tests/core-kunit.h
@@ -698,6 +698,64 @@ static void damon_test_update_monitoring_result(struct kunit *test)
 	damon_destroy_ctx(ctx);
 }
 
+static void damon_test_mult_frac(struct kunit *test)
+{
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(7, 3, 2), 10ul);
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(ULONG_MAX, 0, 1), 0ul);
+	/* the remainder product overflows on 32-bit */
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(524288, 10000, 786432), 6666ul);
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(500000, 10000, 1000000), 5000ul);
+	/* the remainder product overflows even on 64-bit */
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(ULONG_MAX - 1, ULONG_MAX,
+				ULONG_MAX), ULONG_MAX - 1);
+	/* the quotient product overflows */
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(ULONG_MAX, 10000, 1), ULONG_MAX);
+	/* the largest representable result, and one beyond it */
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(ULONG_MAX - ULONG_MAX / 10000,
+				10000, 9999), ULONG_MAX);
+	KUNIT_EXPECT_EQ(test, damon_mult_frac(ULONG_MAX - ULONG_MAX / 10000 + 1,
+				10000, 9999), ULONG_MAX);
+}
+
+static void damon_test_age_for_new_attrs_large_value(struct kunit *test)
+{
+	struct damon_attrs old_attrs = {.aggr_interval = 100000};
+	struct damon_attrs new_attrs = {.aggr_interval = 50000};
+	unsigned int age;
+
+	age = damon_age_for_new_attrs(50000, &old_attrs, &new_attrs);
+	KUNIT_EXPECT_EQ(test, age, 100000u);
+
+	new_attrs.aggr_interval = 1;
+	age = damon_age_for_new_attrs(UINT_MAX, &old_attrs, &new_attrs);
+	KUNIT_EXPECT_EQ(test, age, UINT_MAX);
+
+	old_attrs.aggr_interval = ULONG_MAX;
+	age = damon_age_for_new_attrs(UINT_MAX, &old_attrs, &new_attrs);
+	KUNIT_EXPECT_EQ(test, age, UINT_MAX);
+}
+
+static void damon_test_sample_ratio_large_value(struct kunit *test)
+{
+	struct damon_attrs attrs = {
+		.sample_interval = 1000,
+		.aggr_interval = 600000000,
+	};
+
+	KUNIT_EXPECT_EQ(test, damon_sample_bp_to_count(10000, &attrs),
+			600000u);
+	KUNIT_EXPECT_EQ(test, damon_sample_count_to_bp(600000, &attrs),
+			10000u);
+	KUNIT_EXPECT_EQ(test, damon_sample_count_to_bp(500000, &attrs),
+			8333u);
+	KUNIT_EXPECT_EQ(test, damon_sample_bp_to_count(UINT_MAX, &attrs),
+			UINT_MAX);
+
+	attrs.aggr_interval = attrs.sample_interval;
+	KUNIT_EXPECT_EQ(test, damon_sample_count_to_bp(UINT_MAX, &attrs),
+			UINT_MAX);
+}
+
 static void damon_test_set_attrs(struct kunit *test)
 {
 	struct damon_ctx *c = damon_new_ctx();
@@ -735,6 +793,7 @@ static void damon_test_mvsum(struct kunit *test)
 		3, 10, 5000, 8,		/* 3 + 10 * 0.5 */
 		32, 100, 1000, 42,	/* 32 + 100 * 0.1 */
 		42, 49, 0, 42,		/* 42 + 49 * 0 */
+		0, 600000, 8333, 499980, /* 32-bit remainder product overflow */
 	};
 
 	int i;
@@ -794,6 +853,18 @@ static void damon_test_nr_accesses_mvsum(struct kunit *test)
 				damon_nr_accesses_mvsum(r, c));
 	}
 
+	c->attrs.sample_interval = 1000;
+	c->attrs.aggr_interval = 600000000;
+	c->passed_sample_intervals = 100000;
+	c->next_aggregation_sis = 600000;
+	r->nr_accesses = 100000;
+	r->last_nr_accesses = 600000;
+	KUNIT_EXPECT_EQ(test, damon_nr_accesses_mvsum(r, c), 599980u);
+
+	r->probe_hits[0] = 0;
+	r->last_probe_hits[0] = 100;
+	KUNIT_EXPECT_EQ(test, damon_probe_hits_mvsum(0, r, c), 83);
+
 	damon_free_region(r);
 	damon_destroy_ctx(c);
 }
@@ -2494,6 +2565,9 @@ static struct kunit_case damon_test_cases[] = {
 	KUNIT_CASE(damon_test_set_regions),
 	KUNIT_CASE(damon_test_nr_samples_per_aggr),
 	KUNIT_CASE(damon_test_update_monitoring_result),
+	KUNIT_CASE(damon_test_mult_frac),
+	KUNIT_CASE(damon_test_age_for_new_attrs_large_value),
+	KUNIT_CASE(damon_test_sample_ratio_large_value),
 	KUNIT_CASE(damon_test_set_attrs),
 	KUNIT_CASE(damon_test_mvsum),
 	KUNIT_CASE(damon_test_nr_accesses_mvsum),
-- 
2.43.0