192095781SDaniel Hill // SPDX-License-Identifier: GPL-2.0 292095781SDaniel Hill #include <kunit/test.h> 392095781SDaniel Hill 492095781SDaniel Hill #include "mean_and_variance.h" 592095781SDaniel Hill 692095781SDaniel Hill #define MAX_SQR (SQRT_U64_MAX*SQRT_U64_MAX) 792095781SDaniel Hill 892095781SDaniel Hill static void mean_and_variance_basic_test(struct kunit *test) 992095781SDaniel Hill { 1092095781SDaniel Hill struct mean_and_variance s = {}; 1192095781SDaniel Hill 1265bc4109SKent Overstreet mean_and_variance_update(&s, 2); 1365bc4109SKent Overstreet mean_and_variance_update(&s, 2); 1492095781SDaniel Hill 1592095781SDaniel Hill KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(s), 2); 1692095781SDaniel Hill KUNIT_EXPECT_EQ(test, mean_and_variance_get_variance(s), 0); 1792095781SDaniel Hill KUNIT_EXPECT_EQ(test, s.n, 2); 1892095781SDaniel Hill 1965bc4109SKent Overstreet mean_and_variance_update(&s, 4); 2065bc4109SKent Overstreet mean_and_variance_update(&s, 4); 2192095781SDaniel Hill 2292095781SDaniel Hill KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(s), 3); 2392095781SDaniel Hill KUNIT_EXPECT_EQ(test, mean_and_variance_get_variance(s), 1); 2492095781SDaniel Hill KUNIT_EXPECT_EQ(test, s.n, 4); 2592095781SDaniel Hill } 2692095781SDaniel Hill 2792095781SDaniel Hill /* 2892095781SDaniel Hill * Test values computed using a spreadsheet from the psuedocode at the bottom: 2992095781SDaniel Hill * https://fanf2.user.srcf.net/hermes/doc/antiforgery/stats.pdf 3092095781SDaniel Hill */ 3192095781SDaniel Hill 3292095781SDaniel Hill static void mean_and_variance_weighted_test(struct kunit *test) 3392095781SDaniel Hill { 344b4f0876SDarrick J. Wong struct mean_and_variance_weighted s = { }; 3592095781SDaniel Hill 364b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, 10, false, 2); 374b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), 10); 384b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 0); 3992095781SDaniel Hill 404b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, 20, true, 2); 414b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), 12); 424b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 18); 4392095781SDaniel Hill 444b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, 30, true, 2); 454b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), 16); 464b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 72); 4792095781SDaniel Hill 484b4f0876SDarrick J. Wong s = (struct mean_and_variance_weighted) { }; 4992095781SDaniel Hill 504b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, -10, false, 2); 514b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), -10); 524b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 0); 5392095781SDaniel Hill 544b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, -20, true, 2); 554b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), -12); 564b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 18); 5792095781SDaniel Hill 584b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, -30, true, 2); 594b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 2), -16); 604b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 2), 72); 6192095781SDaniel Hill } 6292095781SDaniel Hill 6392095781SDaniel Hill static void mean_and_variance_weighted_advanced_test(struct kunit *test) 6492095781SDaniel Hill { 654b4f0876SDarrick J. Wong struct mean_and_variance_weighted s = { }; 664b4f0876SDarrick J. Wong bool initted = false; 6792095781SDaniel Hill s64 i; 6892095781SDaniel Hill 694b4f0876SDarrick J. Wong for (i = 10; i <= 100; i += 10) { 704b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, i, initted, 8); 714b4f0876SDarrick J. Wong initted = true; 724b4f0876SDarrick J. Wong } 7392095781SDaniel Hill 744b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 8), 11); 754b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 8), 107); 7692095781SDaniel Hill 774b4f0876SDarrick J. Wong s = (struct mean_and_variance_weighted) { }; 784b4f0876SDarrick J. Wong initted = false; 7992095781SDaniel Hill 804b4f0876SDarrick J. Wong for (i = -10; i >= -100; i -= 10) { 814b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&s, i, initted, 8); 824b4f0876SDarrick J. Wong initted = true; 834b4f0876SDarrick J. Wong } 8492095781SDaniel Hill 854b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(s, 8), -11); 864b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_variance(s, 8), 107); 8765bc4109SKent Overstreet } 8892095781SDaniel Hill 8965bc4109SKent Overstreet static void do_mean_and_variance_test(struct kunit *test, 9065bc4109SKent Overstreet s64 initial_value, 9165bc4109SKent Overstreet s64 initial_n, 9265bc4109SKent Overstreet s64 n, 9365bc4109SKent Overstreet unsigned weight, 9465bc4109SKent Overstreet s64 *data, 9565bc4109SKent Overstreet s64 *mean, 9665bc4109SKent Overstreet s64 *stddev, 9765bc4109SKent Overstreet s64 *weighted_mean, 9865bc4109SKent Overstreet s64 *weighted_stddev) 9965bc4109SKent Overstreet { 10065bc4109SKent Overstreet struct mean_and_variance mv = {}; 1014b4f0876SDarrick J. Wong struct mean_and_variance_weighted vw = { }; 10265bc4109SKent Overstreet 10365bc4109SKent Overstreet for (unsigned i = 0; i < initial_n; i++) { 10465bc4109SKent Overstreet mean_and_variance_update(&mv, initial_value); 1054b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&vw, initial_value, false, weight); 10665bc4109SKent Overstreet 10765bc4109SKent Overstreet KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(mv), initial_value); 10865bc4109SKent Overstreet KUNIT_EXPECT_EQ(test, mean_and_variance_get_stddev(mv), 0); 1094b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(vw, weight), initial_value); 1104b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_stddev(vw, weight),0); 11165bc4109SKent Overstreet } 11265bc4109SKent Overstreet 11365bc4109SKent Overstreet for (unsigned i = 0; i < n; i++) { 11465bc4109SKent Overstreet mean_and_variance_update(&mv, data[i]); 1154b4f0876SDarrick J. Wong mean_and_variance_weighted_update(&vw, data[i], true, weight); 11665bc4109SKent Overstreet 11765bc4109SKent Overstreet KUNIT_EXPECT_EQ(test, mean_and_variance_get_mean(mv), mean[i]); 11865bc4109SKent Overstreet KUNIT_EXPECT_EQ(test, mean_and_variance_get_stddev(mv), stddev[i]); 1194b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_mean(vw, weight), weighted_mean[i]); 1204b4f0876SDarrick J. Wong KUNIT_EXPECT_EQ(test, mean_and_variance_weighted_get_stddev(vw, weight),weighted_stddev[i]); 12165bc4109SKent Overstreet } 12265bc4109SKent Overstreet 12365bc4109SKent Overstreet KUNIT_EXPECT_EQ(test, mv.n, initial_n + n); 12465bc4109SKent Overstreet } 12565bc4109SKent Overstreet 12665bc4109SKent Overstreet /* Test behaviour with a single outlier, then back to steady state: */ 12765bc4109SKent Overstreet static void mean_and_variance_test_1(struct kunit *test) 12865bc4109SKent Overstreet { 12965bc4109SKent Overstreet s64 d[] = { 100, 10, 10, 10, 10, 10, 10 }; 13065bc4109SKent Overstreet s64 mean[] = { 22, 21, 20, 19, 18, 17, 16 }; 13165bc4109SKent Overstreet s64 stddev[] = { 32, 29, 28, 27, 26, 25, 24 }; 13265bc4109SKent Overstreet s64 weighted_mean[] = { 32, 27, 22, 19, 17, 15, 14 }; 13365bc4109SKent Overstreet s64 weighted_stddev[] = { 38, 35, 31, 27, 24, 21, 18 }; 13465bc4109SKent Overstreet 13565bc4109SKent Overstreet do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, 13665bc4109SKent Overstreet d, mean, stddev, weighted_mean, weighted_stddev); 13765bc4109SKent Overstreet } 13865bc4109SKent Overstreet 13965bc4109SKent Overstreet /* Test behaviour where we switch from one steady state to another: */ 14097ca7c1fSGuenter Roeck static void mean_and_variance_test_2(struct kunit *test) 14165bc4109SKent Overstreet { 14265bc4109SKent Overstreet s64 d[] = { 100, 100, 100, 100, 100 }; 14365bc4109SKent Overstreet s64 mean[] = { 22, 32, 40, 46, 50 }; 14465bc4109SKent Overstreet s64 stddev[] = { 32, 39, 42, 44, 45 }; 14565bc4109SKent Overstreet s64 weighted_mean[] = { 32, 49, 61, 71, 78 }; 14665bc4109SKent Overstreet s64 weighted_stddev[] = { 38, 44, 44, 41, 38 }; 14765bc4109SKent Overstreet 14865bc4109SKent Overstreet do_mean_and_variance_test(test, 10, 6, ARRAY_SIZE(d), 2, 14965bc4109SKent Overstreet d, mean, stddev, weighted_mean, weighted_stddev); 15065bc4109SKent Overstreet } 15165bc4109SKent Overstreet 15292095781SDaniel Hill static void mean_and_variance_fast_divpow2(struct kunit *test) 15392095781SDaniel Hill { 15492095781SDaniel Hill s64 i; 15592095781SDaniel Hill u8 d; 15692095781SDaniel Hill 15792095781SDaniel Hill for (i = 0; i < 100; i++) { 15892095781SDaniel Hill d = 0; 15992095781SDaniel Hill KUNIT_EXPECT_EQ(test, fast_divpow2(i, d), div_u64(i, 1LLU << d)); 16092095781SDaniel Hill KUNIT_EXPECT_EQ(test, abs(fast_divpow2(-i, d)), div_u64(i, 1LLU << d)); 16192095781SDaniel Hill for (d = 1; d < 32; d++) { 16292095781SDaniel Hill KUNIT_EXPECT_EQ_MSG(test, abs(fast_divpow2(i, d)), 16392095781SDaniel Hill div_u64(i, 1 << d), "%lld %u", i, d); 16492095781SDaniel Hill KUNIT_EXPECT_EQ_MSG(test, abs(fast_divpow2(-i, d)), 16592095781SDaniel Hill div_u64(i, 1 << d), "%lld %u", -i, d); 16692095781SDaniel Hill } 16792095781SDaniel Hill } 16892095781SDaniel Hill } 16992095781SDaniel Hill 17092095781SDaniel Hill static void mean_and_variance_u128_basic_test(struct kunit *test) 17192095781SDaniel Hill { 17292095781SDaniel Hill u128_u a = u64s_to_u128(0, U64_MAX); 17392095781SDaniel Hill u128_u a1 = u64s_to_u128(0, 1); 17492095781SDaniel Hill u128_u b = u64s_to_u128(1, 0); 17592095781SDaniel Hill u128_u c = u64s_to_u128(0, 1LLU << 63); 17692095781SDaniel Hill u128_u c2 = u64s_to_u128(U64_MAX, U64_MAX); 17792095781SDaniel Hill 17892095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_add(a, a1)), 1); 17992095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_add(a, a1)), 0); 18092095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_add(a1, a)), 1); 18192095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_add(a1, a)), 0); 18292095781SDaniel Hill 18392095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_sub(b, a1)), U64_MAX); 18492095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_sub(b, a1)), 0); 18592095781SDaniel Hill 18692095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_shl(c, 1)), 1); 18792095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_shl(c, 1)), 0); 18892095781SDaniel Hill 18992095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_square(U64_MAX)), U64_MAX - 1); 19092095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_square(U64_MAX)), 1); 19192095781SDaniel Hill 19292095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_div(b, 2)), 1LLU << 63); 19392095781SDaniel Hill 19492095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_div(c2, 2)), U64_MAX >> 1); 19592095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_div(c2, 2)), U64_MAX); 19692095781SDaniel Hill 19792095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_hi(u128_div(u128_shl(u64_to_u128(U64_MAX), 32), 2)), U32_MAX >> 1); 19892095781SDaniel Hill KUNIT_EXPECT_EQ(test, u128_lo(u128_div(u128_shl(u64_to_u128(U64_MAX), 32), 2)), U64_MAX << 31); 19992095781SDaniel Hill } 20092095781SDaniel Hill 20192095781SDaniel Hill static struct kunit_case mean_and_variance_test_cases[] = { 20292095781SDaniel Hill KUNIT_CASE(mean_and_variance_fast_divpow2), 20392095781SDaniel Hill KUNIT_CASE(mean_and_variance_u128_basic_test), 20492095781SDaniel Hill KUNIT_CASE(mean_and_variance_basic_test), 20592095781SDaniel Hill KUNIT_CASE(mean_and_variance_weighted_test), 20692095781SDaniel Hill KUNIT_CASE(mean_and_variance_weighted_advanced_test), 20765bc4109SKent Overstreet KUNIT_CASE(mean_and_variance_test_1), 20865bc4109SKent Overstreet KUNIT_CASE(mean_and_variance_test_2), 20992095781SDaniel Hill {} 21092095781SDaniel Hill }; 21192095781SDaniel Hill 21292095781SDaniel Hill static struct kunit_suite mean_and_variance_test_suite = { 21392095781SDaniel Hill .name = "mean and variance tests", 21492095781SDaniel Hill .test_cases = mean_and_variance_test_cases 21592095781SDaniel Hill }; 21692095781SDaniel Hill 21792095781SDaniel Hill kunit_test_suite(mean_and_variance_test_suite); 21892095781SDaniel Hill 21992095781SDaniel Hill MODULE_AUTHOR("Daniel B. Hill"); 220*b4131076SJeff Johnson MODULE_DESCRIPTION("bcachefs filesystem mean and variance unit tests"); 22192095781SDaniel Hill MODULE_LICENSE("GPL"); 222