1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Test cases for memcpy(), memmove(), and memset(). 4 */ 5 #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt 6 7 #include <kunit/test.h> 8 #include <linux/device.h> 9 #include <linux/init.h> 10 #include <linux/kernel.h> 11 #include <linux/mm.h> 12 #include <linux/module.h> 13 #include <linux/overflow.h> 14 #include <linux/slab.h> 15 #include <linux/types.h> 16 #include <linux/vmalloc.h> 17 18 struct some_bytes { 19 union { 20 u8 data[32]; 21 struct { 22 u32 one; 23 u16 two; 24 u8 three; 25 /* 1 byte hole */ 26 u32 four[4]; 27 }; 28 }; 29 }; 30 31 #define check(instance, v) do { \ 32 BUILD_BUG_ON(sizeof(instance.data) != 32); \ 33 for (size_t i = 0; i < sizeof(instance.data); i++) { \ 34 KUNIT_ASSERT_EQ_MSG(test, instance.data[i], v, \ 35 "line %d: '%s' not initialized to 0x%02x @ %zu (saw 0x%02x)\n", \ 36 __LINE__, #instance, v, i, instance.data[i]); \ 37 } \ 38 } while (0) 39 40 #define compare(name, one, two) do { \ 41 BUILD_BUG_ON(sizeof(one) != sizeof(two)); \ 42 for (size_t i = 0; i < sizeof(one); i++) { \ 43 KUNIT_EXPECT_EQ_MSG(test, one.data[i], two.data[i], \ 44 "line %d: %s.data[%zu] (0x%02x) != %s.data[%zu] (0x%02x)\n", \ 45 __LINE__, #one, i, one.data[i], #two, i, two.data[i]); \ 46 } \ 47 kunit_info(test, "ok: " TEST_OP "() " name "\n"); \ 48 } while (0) 49 50 static void memcpy_test(struct kunit *test) 51 { 52 #define TEST_OP "memcpy" 53 struct some_bytes control = { 54 .data = { 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 55 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 56 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 57 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 58 }, 59 }; 60 struct some_bytes zero = { }; 61 struct some_bytes middle = { 62 .data = { 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 63 0x20, 0x20, 0x20, 0x20, 0x00, 0x00, 0x00, 0x00, 64 0x00, 0x00, 0x00, 0x20, 0x20, 0x20, 0x20, 0x20, 65 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 66 }, 67 }; 68 struct some_bytes three = { 69 .data = { 0x00, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 70 0x20, 0x00, 0x00, 0x20, 0x20, 0x20, 0x20, 0x20, 71 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 72 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 73 }, 74 }; 75 struct some_bytes dest = { }; 76 int count; 77 u8 *ptr; 78 79 /* Verify static initializers. */ 80 check(control, 0x20); 81 check(zero, 0); 82 compare("static initializers", dest, zero); 83 84 /* Verify assignment. */ 85 dest = control; 86 compare("direct assignment", dest, control); 87 88 /* Verify complete overwrite. */ 89 memcpy(dest.data, zero.data, sizeof(dest.data)); 90 compare("complete overwrite", dest, zero); 91 92 /* Verify middle overwrite. */ 93 dest = control; 94 memcpy(dest.data + 12, zero.data, 7); 95 compare("middle overwrite", dest, middle); 96 97 /* Verify argument side-effects aren't repeated. */ 98 dest = control; 99 ptr = dest.data; 100 count = 1; 101 memcpy(ptr++, zero.data, count++); 102 ptr += 8; 103 memcpy(ptr++, zero.data, count++); 104 compare("argument side-effects", dest, three); 105 #undef TEST_OP 106 } 107 108 static unsigned char larger_array [2048]; 109 110 static void memmove_test(struct kunit *test) 111 { 112 #define TEST_OP "memmove" 113 struct some_bytes control = { 114 .data = { 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 115 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 116 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 117 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 118 }, 119 }; 120 struct some_bytes zero = { }; 121 struct some_bytes middle = { 122 .data = { 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 123 0x99, 0x99, 0x99, 0x99, 0x00, 0x00, 0x00, 0x00, 124 0x00, 0x00, 0x00, 0x99, 0x99, 0x99, 0x99, 0x99, 125 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 126 }, 127 }; 128 struct some_bytes five = { 129 .data = { 0x00, 0x00, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 130 0x99, 0x99, 0x00, 0x00, 0x00, 0x99, 0x99, 0x99, 131 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 132 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 133 }, 134 }; 135 struct some_bytes overlap = { 136 .data = { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 137 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 138 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 139 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 140 }, 141 }; 142 struct some_bytes overlap_expected = { 143 .data = { 0x00, 0x01, 0x00, 0x01, 0x02, 0x03, 0x04, 0x07, 144 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 145 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 146 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 0x99, 147 }, 148 }; 149 struct some_bytes dest = { }; 150 int count; 151 u8 *ptr; 152 153 /* Verify static initializers. */ 154 check(control, 0x99); 155 check(zero, 0); 156 compare("static initializers", zero, dest); 157 158 /* Verify assignment. */ 159 dest = control; 160 compare("direct assignment", dest, control); 161 162 /* Verify complete overwrite. */ 163 memmove(dest.data, zero.data, sizeof(dest.data)); 164 compare("complete overwrite", dest, zero); 165 166 /* Verify middle overwrite. */ 167 dest = control; 168 memmove(dest.data + 12, zero.data, 7); 169 compare("middle overwrite", dest, middle); 170 171 /* Verify argument side-effects aren't repeated. */ 172 dest = control; 173 ptr = dest.data; 174 count = 2; 175 memmove(ptr++, zero.data, count++); 176 ptr += 9; 177 memmove(ptr++, zero.data, count++); 178 compare("argument side-effects", dest, five); 179 180 /* Verify overlapping overwrite is correct. */ 181 ptr = &overlap.data[2]; 182 memmove(ptr, overlap.data, 5); 183 compare("overlapping write", overlap, overlap_expected); 184 185 /* Verify larger overlapping moves. */ 186 larger_array[256] = 0xAAu; 187 /* 188 * Test a backwards overlapping memmove first. 256 and 1024 are 189 * important for i386 to use rep movsl. 190 */ 191 memmove(larger_array, larger_array + 256, 1024); 192 KUNIT_ASSERT_EQ(test, larger_array[0], 0xAAu); 193 KUNIT_ASSERT_EQ(test, larger_array[256], 0x00); 194 KUNIT_ASSERT_NULL(test, 195 memchr(larger_array + 1, 0xaa, ARRAY_SIZE(larger_array) - 1)); 196 /* Test a forwards overlapping memmove. */ 197 larger_array[0] = 0xBBu; 198 memmove(larger_array + 256, larger_array, 1024); 199 KUNIT_ASSERT_EQ(test, larger_array[0], 0xBBu); 200 KUNIT_ASSERT_EQ(test, larger_array[256], 0xBBu); 201 KUNIT_ASSERT_NULL(test, memchr(larger_array + 1, 0xBBu, 256 - 1)); 202 KUNIT_ASSERT_NULL(test, 203 memchr(larger_array + 257, 0xBBu, ARRAY_SIZE(larger_array) - 257)); 204 #undef TEST_OP 205 } 206 207 static void memset_test(struct kunit *test) 208 { 209 #define TEST_OP "memset" 210 struct some_bytes control = { 211 .data = { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 212 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 213 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 214 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 215 }, 216 }; 217 struct some_bytes complete = { 218 .data = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 219 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 220 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 221 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 222 }, 223 }; 224 struct some_bytes middle = { 225 .data = { 0x30, 0x30, 0x30, 0x30, 0x31, 0x31, 0x31, 0x31, 226 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 0x31, 227 0x31, 0x31, 0x31, 0x31, 0x30, 0x30, 0x30, 0x30, 228 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 229 }, 230 }; 231 struct some_bytes three = { 232 .data = { 0x60, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 233 0x30, 0x61, 0x61, 0x30, 0x30, 0x30, 0x30, 0x30, 234 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 235 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 236 }, 237 }; 238 struct some_bytes after = { 239 .data = { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x72, 240 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 241 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 242 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 0x72, 243 }, 244 }; 245 struct some_bytes startat = { 246 .data = { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 247 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 248 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 249 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 0x79, 250 }, 251 }; 252 struct some_bytes dest = { }; 253 int count, value; 254 u8 *ptr; 255 256 /* Verify static initializers. */ 257 check(control, 0x30); 258 check(dest, 0); 259 260 /* Verify assignment. */ 261 dest = control; 262 compare("direct assignment", dest, control); 263 264 /* Verify complete overwrite. */ 265 memset(dest.data, 0xff, sizeof(dest.data)); 266 compare("complete overwrite", dest, complete); 267 268 /* Verify middle overwrite. */ 269 dest = control; 270 memset(dest.data + 4, 0x31, 16); 271 compare("middle overwrite", dest, middle); 272 273 /* Verify argument side-effects aren't repeated. */ 274 dest = control; 275 ptr = dest.data; 276 value = 0x60; 277 count = 1; 278 memset(ptr++, value++, count++); 279 ptr += 8; 280 memset(ptr++, value++, count++); 281 compare("argument side-effects", dest, three); 282 283 /* Verify memset_after() */ 284 dest = control; 285 memset_after(&dest, 0x72, three); 286 compare("memset_after()", dest, after); 287 288 /* Verify memset_startat() */ 289 dest = control; 290 memset_startat(&dest, 0x79, four); 291 compare("memset_startat()", dest, startat); 292 #undef TEST_OP 293 } 294 295 static u8 large_src[1024]; 296 static u8 large_dst[2048]; 297 static const u8 large_zero[2048]; 298 299 static void set_random_nonzero(struct kunit *test, u8 *byte) 300 { 301 int failed_rng = 0; 302 303 while (*byte == 0) { 304 get_random_bytes(byte, 1); 305 KUNIT_ASSERT_LT_MSG(test, failed_rng++, 100, 306 "Is the RNG broken?"); 307 } 308 } 309 310 static void init_large(struct kunit *test) 311 { 312 /* Get many bit patterns. */ 313 get_random_bytes(large_src, ARRAY_SIZE(large_src)); 314 315 /* Make sure we have non-zero edges. */ 316 set_random_nonzero(test, &large_src[0]); 317 set_random_nonzero(test, &large_src[ARRAY_SIZE(large_src) - 1]); 318 319 /* Explicitly zero the entire destination. */ 320 memset(large_dst, 0, ARRAY_SIZE(large_dst)); 321 } 322 323 /* 324 * Instead of an indirect function call for "copy" or a giant macro, 325 * use a bool to pick memcpy or memmove. 326 */ 327 static void copy_large_test(struct kunit *test, bool use_memmove) 328 { 329 init_large(test); 330 331 /* Copy a growing number of non-overlapping bytes ... */ 332 for (int bytes = 1; bytes <= ARRAY_SIZE(large_src); bytes++) { 333 /* Over a shifting destination window ... */ 334 for (int offset = 0; offset < ARRAY_SIZE(large_src); offset++) { 335 int right_zero_pos = offset + bytes; 336 int right_zero_size = ARRAY_SIZE(large_dst) - right_zero_pos; 337 338 /* Copy! */ 339 if (use_memmove) 340 memmove(large_dst + offset, large_src, bytes); 341 else 342 memcpy(large_dst + offset, large_src, bytes); 343 344 /* Did we touch anything before the copy area? */ 345 KUNIT_ASSERT_EQ_MSG(test, 346 memcmp(large_dst, large_zero, offset), 0, 347 "with size %d at offset %d", bytes, offset); 348 /* Did we touch anything after the copy area? */ 349 KUNIT_ASSERT_EQ_MSG(test, 350 memcmp(&large_dst[right_zero_pos], large_zero, right_zero_size), 0, 351 "with size %d at offset %d", bytes, offset); 352 353 /* Are we byte-for-byte exact across the copy? */ 354 KUNIT_ASSERT_EQ_MSG(test, 355 memcmp(large_dst + offset, large_src, bytes), 0, 356 "with size %d at offset %d", bytes, offset); 357 358 /* Zero out what we copied for the next cycle. */ 359 memset(large_dst + offset, 0, bytes); 360 } 361 /* Avoid stall warnings if this loop gets slow. */ 362 cond_resched(); 363 } 364 } 365 366 static void memcpy_large_test(struct kunit *test) 367 { 368 copy_large_test(test, false); 369 } 370 371 static void memmove_large_test(struct kunit *test) 372 { 373 copy_large_test(test, true); 374 } 375 376 /* 377 * On the assumption that boundary conditions are going to be the most 378 * sensitive, instead of taking a full step (inc) each iteration, 379 * take single index steps for at least the first "inc"-many indexes 380 * from the "start" and at least the last "inc"-many indexes before 381 * the "end". When in the middle, take full "inc"-wide steps. For 382 * example, calling next_step(idx, 1, 15, 3) with idx starting at 0 383 * would see the following pattern: 1 2 3 4 7 10 11 12 13 14 15. 384 */ 385 static int next_step(int idx, int start, int end, int inc) 386 { 387 start += inc; 388 end -= inc; 389 390 if (idx < start || idx + inc > end) 391 inc = 1; 392 return idx + inc; 393 } 394 395 static void inner_loop(struct kunit *test, int bytes, int d_off, int s_off) 396 { 397 int left_zero_pos, left_zero_size; 398 int right_zero_pos, right_zero_size; 399 int src_pos, src_orig_pos, src_size; 400 int pos; 401 402 /* Place the source in the destination buffer. */ 403 memcpy(&large_dst[s_off], large_src, bytes); 404 405 /* Copy to destination offset. */ 406 memmove(&large_dst[d_off], &large_dst[s_off], bytes); 407 408 /* Make sure destination entirely matches. */ 409 KUNIT_ASSERT_EQ_MSG(test, memcmp(&large_dst[d_off], large_src, bytes), 0, 410 "with size %d at src offset %d and dest offset %d", 411 bytes, s_off, d_off); 412 413 /* Calculate the expected zero spans. */ 414 if (s_off < d_off) { 415 left_zero_pos = 0; 416 left_zero_size = s_off; 417 418 right_zero_pos = d_off + bytes; 419 right_zero_size = ARRAY_SIZE(large_dst) - right_zero_pos; 420 421 src_pos = s_off; 422 src_orig_pos = 0; 423 src_size = d_off - s_off; 424 } else { 425 left_zero_pos = 0; 426 left_zero_size = d_off; 427 428 right_zero_pos = s_off + bytes; 429 right_zero_size = ARRAY_SIZE(large_dst) - right_zero_pos; 430 431 src_pos = d_off + bytes; 432 src_orig_pos = src_pos - s_off; 433 src_size = right_zero_pos - src_pos; 434 } 435 436 /* Check non-overlapping source is unchanged.*/ 437 KUNIT_ASSERT_EQ_MSG(test, 438 memcmp(&large_dst[src_pos], &large_src[src_orig_pos], src_size), 0, 439 "with size %d at src offset %d and dest offset %d", 440 bytes, s_off, d_off); 441 442 /* Check leading buffer contents are zero. */ 443 KUNIT_ASSERT_EQ_MSG(test, 444 memcmp(&large_dst[left_zero_pos], large_zero, left_zero_size), 0, 445 "with size %d at src offset %d and dest offset %d", 446 bytes, s_off, d_off); 447 /* Check trailing buffer contents are zero. */ 448 KUNIT_ASSERT_EQ_MSG(test, 449 memcmp(&large_dst[right_zero_pos], large_zero, right_zero_size), 0, 450 "with size %d at src offset %d and dest offset %d", 451 bytes, s_off, d_off); 452 453 /* Zero out everything not already zeroed.*/ 454 pos = left_zero_pos + left_zero_size; 455 memset(&large_dst[pos], 0, right_zero_pos - pos); 456 } 457 458 static void memmove_overlap_test(struct kunit *test) 459 { 460 /* 461 * Running all possible offset and overlap combinations takes a 462 * very long time. Instead, only check up to 128 bytes offset 463 * into the destination buffer (which should result in crossing 464 * cachelines), with a step size of 1 through 7 to try to skip some 465 * redundancy. 466 */ 467 static const int offset_max = 128; /* less than ARRAY_SIZE(large_src); */ 468 static const int bytes_step = 7; 469 static const int window_step = 7; 470 471 static const int bytes_start = 1; 472 static const int bytes_end = ARRAY_SIZE(large_src) + 1; 473 474 init_large(test); 475 476 /* Copy a growing number of overlapping bytes ... */ 477 for (int bytes = bytes_start; bytes < bytes_end; 478 bytes = next_step(bytes, bytes_start, bytes_end, bytes_step)) { 479 480 /* Over a shifting destination window ... */ 481 for (int d_off = 0; d_off < offset_max; d_off++) { 482 int s_start = max(d_off - bytes, 0); 483 int s_end = min_t(int, d_off + bytes, ARRAY_SIZE(large_src)); 484 485 /* Over a shifting source window ... */ 486 for (int s_off = s_start; s_off < s_end; 487 s_off = next_step(s_off, s_start, s_end, window_step)) 488 inner_loop(test, bytes, d_off, s_off); 489 490 /* Avoid stall warnings. */ 491 cond_resched(); 492 } 493 } 494 } 495 496 static struct kunit_case memcpy_test_cases[] = { 497 KUNIT_CASE(memset_test), 498 KUNIT_CASE(memcpy_test), 499 KUNIT_CASE_SLOW(memcpy_large_test), 500 KUNIT_CASE_SLOW(memmove_test), 501 KUNIT_CASE_SLOW(memmove_large_test), 502 KUNIT_CASE_SLOW(memmove_overlap_test), 503 {} 504 }; 505 506 static struct kunit_suite memcpy_test_suite = { 507 .name = "memcpy", 508 .test_cases = memcpy_test_cases, 509 }; 510 511 kunit_test_suite(memcpy_test_suite); 512 513 MODULE_DESCRIPTION("test cases for memcpy(), memmove(), and memset()"); 514 MODULE_LICENSE("GPL"); 515