1 // SPDX-License-Identifier: GPL-2.0-or-later 2 /* 3 * Unit test the XOR library functions. 4 * 5 * Copyright 2024 Google LLC 6 * Copyright 2026 Christoph Hellwig 7 * 8 * Based on the CRC tests by Eric Biggers <ebiggers@google.com>. 9 */ 10 #include <kunit/test.h> 11 #include <linux/prandom.h> 12 #include <linux/string_choices.h> 13 #include <linux/vmalloc.h> 14 #include <linux/raid/xor.h> 15 16 #define XOR_KUNIT_SEED 42 17 #define XOR_KUNIT_MAX_BYTES 16384 18 #define XOR_KUNIT_MAX_BUFFERS 64 19 #define XOR_KUNIT_NUM_TEST_ITERS 1000 20 21 static struct rnd_state rng; 22 static void *test_buffers[XOR_KUNIT_MAX_BUFFERS]; 23 static void *test_dest; 24 static void *test_ref; 25 static size_t test_buflen; 26 27 static u32 rand32(void) 28 { 29 return prandom_u32_state(&rng); 30 } 31 32 /* Reference implementation using dumb byte-wise XOR */ 33 static void xor_ref(void *dest, void **srcs, unsigned int src_cnt, 34 unsigned int bytes) 35 { 36 unsigned int off, idx; 37 u8 *d = dest; 38 39 for (off = 0; off < bytes; off++) { 40 for (idx = 0; idx < src_cnt; idx++) { 41 u8 *src = srcs[idx]; 42 43 d[off] ^= src[off]; 44 } 45 } 46 } 47 48 /* Generate a random length that is a multiple of 512. */ 49 static unsigned int random_length(unsigned int max_length) 50 { 51 return round_up((rand32() % max_length) + 1, 512); 52 } 53 54 /* Generate a random alignment that is a multiple of 64. */ 55 static unsigned int random_alignment(unsigned int max_alignment) 56 { 57 return ((rand32() % max_alignment) + 1) & ~63; 58 } 59 60 static void xor_generate_random_data(void) 61 { 62 int i; 63 64 prandom_bytes_state(&rng, test_dest, test_buflen); 65 memcpy(test_ref, test_dest, test_buflen); 66 for (i = 0; i < XOR_KUNIT_MAX_BUFFERS; i++) 67 prandom_bytes_state(&rng, test_buffers[i], test_buflen); 68 } 69 70 /* Test that xor_gen gives the same result as a reference implementation. */ 71 static void xor_test(struct kunit *test) 72 { 73 void *aligned_buffers[XOR_KUNIT_MAX_BUFFERS]; 74 size_t i; 75 76 for (i = 0; i < XOR_KUNIT_NUM_TEST_ITERS; i++) { 77 unsigned int nr_buffers = 78 (rand32() % XOR_KUNIT_MAX_BUFFERS) + 1; 79 unsigned int len = random_length(XOR_KUNIT_MAX_BYTES); 80 unsigned int max_alignment, align = 0; 81 void *buffers; 82 83 if (rand32() % 8 == 0) 84 /* Refresh the data occasionally. */ 85 xor_generate_random_data(); 86 87 /* 88 * If we're not using the entire buffer size, inject randomized 89 * alignment into the buffer. 90 */ 91 max_alignment = XOR_KUNIT_MAX_BYTES - len; 92 if (max_alignment == 0) { 93 buffers = test_buffers; 94 } else if (rand32() % 2 == 0) { 95 /* Use random alignments mod 64 */ 96 int j; 97 98 for (j = 0; j < nr_buffers; j++) 99 aligned_buffers[j] = test_buffers[j] + 100 random_alignment(max_alignment); 101 buffers = aligned_buffers; 102 align = random_alignment(max_alignment); 103 } else { 104 /* Go up to the guard page, to catch buffer overreads */ 105 int j; 106 107 align = test_buflen - len; 108 for (j = 0; j < nr_buffers; j++) 109 aligned_buffers[j] = test_buffers[j] + align; 110 buffers = aligned_buffers; 111 } 112 113 /* 114 * Compute the XOR, and verify that it equals the XOR computed 115 * by a simple byte-at-a-time reference implementation. 116 */ 117 xor_ref(test_ref + align, buffers, nr_buffers, len); 118 xor_gen(test_dest + align, buffers, nr_buffers, len); 119 KUNIT_EXPECT_MEMEQ_MSG(test, test_ref + align, 120 test_dest + align, len, 121 "Wrong result with buffers=%u, len=%u, unaligned=%s, at_end=%s", 122 nr_buffers, len, 123 str_yes_no(max_alignment), 124 str_yes_no(align + len == test_buflen)); 125 } 126 } 127 128 static void xor_benchmark(struct kunit *test) 129 { 130 static const unsigned int nr_to_test[] = { 131 4, 5, 6, 7, 8, 10, 12, 15, 16, 32, 132 }; 133 static const unsigned int len_to_test[] = { 134 SZ_4K, SZ_16K, 135 }; 136 unsigned int i, j, l; 137 u64 t; 138 139 if (!IS_ENABLED(CONFIG_XOR_BENCHMARK)) 140 kunit_skip(test, "not enabled"); 141 142 /* warm-up */ 143 for (i = 0; i < ARRAY_SIZE(nr_to_test); i++) { 144 for (j = 0; j < ARRAY_SIZE(len_to_test); j++) { 145 for (l = 0; l < 10; l++) { 146 xor_gen(test_dest, test_buffers, nr_to_test[i], 147 len_to_test[j]); 148 } 149 } 150 } 151 152 /* 153 * Preferably this would be a loop over len_to_test, but the kunit 154 * logging always adds a newline to each logged format string. 155 */ 156 static_assert(ARRAY_SIZE(len_to_test) == 2); 157 kunit_info(test, " \t%5u bytes\t%5u bytes\n", 158 len_to_test[0], len_to_test[1]); 159 160 for (i = 0; i < ARRAY_SIZE(nr_to_test); i++) { 161 unsigned int nr = nr_to_test[i]; 162 u64 speed[ARRAY_SIZE(len_to_test)]; 163 164 KUNIT_ASSERT_LE(test, nr, XOR_KUNIT_MAX_BUFFERS); 165 166 for (j = 0; j < ARRAY_SIZE(len_to_test); j++) { 167 unsigned int len = len_to_test[j]; 168 const unsigned long num_iters = 1000; 169 170 KUNIT_ASSERT_GT(test, len, 0); 171 KUNIT_ASSERT_LE(test, len, XOR_KUNIT_MAX_BYTES); 172 173 preempt_disable(); 174 t = ktime_get_ns(); 175 for (l = 0; l < num_iters; l++) 176 xor_gen(test_dest, test_buffers, nr, len); 177 t = max(ktime_get_ns() - t, 1); 178 preempt_enable(); 179 180 speed[j] = div64_u64((u64)len * num_iters * nr, t); 181 } 182 183 static_assert(ARRAY_SIZE(len_to_test) == 2); 184 kunit_info(test, "%3u disks:\t%5llu GB/s\t%5llu GB/s\n", 185 nr, speed[0], speed[1]); 186 } 187 } 188 189 static struct kunit_case xor_test_cases[] = { 190 KUNIT_CASE(xor_test), 191 KUNIT_CASE(xor_benchmark), 192 {}, 193 }; 194 195 static int xor_suite_init(struct kunit_suite *suite) 196 { 197 int i; 198 199 /* 200 * Allocate the test buffer using vmalloc() with a page-aligned length 201 * so that it is immediately followed by a guard page. This allows 202 * buffer overreads to be detected, even in assembly code. 203 */ 204 test_buflen = round_up(XOR_KUNIT_MAX_BYTES, PAGE_SIZE); 205 test_ref = vmalloc(test_buflen); 206 if (!test_ref) 207 return -ENOMEM; 208 test_dest = vmalloc(test_buflen); 209 if (!test_dest) 210 goto out_free_ref; 211 for (i = 0; i < XOR_KUNIT_MAX_BUFFERS; i++) { 212 test_buffers[i] = vmalloc(test_buflen); 213 if (!test_buffers[i]) 214 goto out_free_buffers; 215 } 216 217 prandom_seed_state(&rng, XOR_KUNIT_SEED); 218 xor_generate_random_data(); 219 return 0; 220 221 out_free_buffers: 222 while (--i >= 0) 223 vfree(test_buffers[i]); 224 vfree(test_dest); 225 out_free_ref: 226 vfree(test_ref); 227 return -ENOMEM; 228 } 229 230 static void xor_suite_exit(struct kunit_suite *suite) 231 { 232 int i; 233 234 vfree(test_ref); 235 vfree(test_dest); 236 for (i = 0; i < XOR_KUNIT_MAX_BUFFERS; i++) 237 vfree(test_buffers[i]); 238 } 239 240 static struct kunit_suite xor_test_suite = { 241 .name = "xor", 242 .test_cases = xor_test_cases, 243 .suite_init = xor_suite_init, 244 .suite_exit = xor_suite_exit, 245 }; 246 kunit_test_suite(xor_test_suite); 247 248 MODULE_DESCRIPTION("Unit test for the XOR library functions"); 249 MODULE_LICENSE("GPL"); 250