515 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Test cases for memcpy(), memmove(), and memset().4 */5#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt6 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 18struct 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 50static 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_OP106}107 108static unsigned char larger_array [2048];109 110static 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 are189 * 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_OP205}206 207static 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_OP293}294 295static u8 large_src[1024];296static u8 large_dst[2048];297static const u8 large_zero[2048];298 299static 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 310static 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 */327static 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 else342 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 366static void memcpy_large_test(struct kunit *test)367{368 copy_large_test(test, false);369}370 371static 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 most378 * sensitive, instead of taking a full step (inc) each iteration,379 * take single index steps for at least the first "inc"-many indexes380 * from the "start" and at least the last "inc"-many indexes before381 * the "end". When in the middle, take full "inc"-wide steps. For382 * example, calling next_step(idx, 1, 15, 3) with idx starting at 0383 * would see the following pattern: 1 2 3 4 7 10 11 12 13 14 15.384 */385static 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 395static 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 458static void memmove_overlap_test(struct kunit *test)459{460 /*461 * Running all possible offset and overlap combinations takes a462 * very long time. Instead, only check up to 128 bytes offset463 * into the destination buffer (which should result in crossing464 * cachelines), with a step size of 1 through 7 to try to skip some465 * 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 496static 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 506static struct kunit_suite memcpy_test_suite = {507 .name = "memcpy",508 .test_cases = memcpy_test_cases,509};510 511kunit_test_suite(memcpy_test_suite);512 513MODULE_DESCRIPTION("test cases for memcpy(), memmove(), and memset()");514MODULE_LICENSE("GPL");515