1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * KUnit test of ext4 multiblocks allocation. 4 */ 5 6 #include <kunit/test.h> 7 #include <kunit/static_stub.h> 8 #include <linux/random.h> 9 10 #include "ext4.h" 11 12 struct mbt_grp_ctx { 13 struct buffer_head bitmap_bh; 14 /* desc and gd_bh are just the place holders for now */ 15 struct ext4_group_desc desc; 16 struct buffer_head gd_bh; 17 }; 18 19 struct mbt_ctx { 20 struct mbt_grp_ctx *grp_ctx; 21 }; 22 23 struct mbt_ext4_super_block { 24 struct ext4_super_block es; 25 struct ext4_sb_info sbi; 26 struct mbt_ctx mbt_ctx; 27 }; 28 29 #define MBT_SB(_sb) (container_of((_sb)->s_fs_info, struct mbt_ext4_super_block, sbi)) 30 #define MBT_CTX(_sb) (&MBT_SB(_sb)->mbt_ctx) 31 #define MBT_GRP_CTX(_sb, _group) (&MBT_CTX(_sb)->grp_ctx[_group]) 32 33 static const struct super_operations mbt_sops = { 34 }; 35 36 static void mbt_kill_sb(struct super_block *sb) 37 { 38 generic_shutdown_super(sb); 39 } 40 41 static struct file_system_type mbt_fs_type = { 42 .name = "mballoc test", 43 .kill_sb = mbt_kill_sb, 44 }; 45 46 static int mbt_mb_init(struct super_block *sb) 47 { 48 ext4_fsblk_t block; 49 int ret; 50 51 /* needed by ext4_mb_init->bdev_nonrot(sb->s_bdev) */ 52 sb->s_bdev = kzalloc(sizeof(*sb->s_bdev), GFP_KERNEL); 53 if (sb->s_bdev == NULL) 54 return -ENOMEM; 55 56 sb->s_bdev->bd_queue = kzalloc(sizeof(struct request_queue), GFP_KERNEL); 57 if (sb->s_bdev->bd_queue == NULL) { 58 kfree(sb->s_bdev); 59 return -ENOMEM; 60 } 61 62 /* 63 * needed by ext4_mb_init->ext4_mb_init_backend-> sbi->s_buddy_cache = 64 * new_inode(sb); 65 */ 66 INIT_LIST_HEAD(&sb->s_inodes); 67 sb->s_op = &mbt_sops; 68 69 ret = ext4_mb_init(sb); 70 if (ret != 0) 71 goto err_out; 72 73 block = ext4_count_free_clusters(sb); 74 ret = percpu_counter_init(&EXT4_SB(sb)->s_freeclusters_counter, block, 75 GFP_KERNEL); 76 if (ret != 0) 77 goto err_mb_release; 78 79 ret = percpu_counter_init(&EXT4_SB(sb)->s_dirtyclusters_counter, 0, 80 GFP_KERNEL); 81 if (ret != 0) 82 goto err_freeclusters; 83 84 return 0; 85 86 err_freeclusters: 87 percpu_counter_destroy(&EXT4_SB(sb)->s_freeclusters_counter); 88 err_mb_release: 89 ext4_mb_release(sb); 90 err_out: 91 kfree(sb->s_bdev->bd_queue); 92 kfree(sb->s_bdev); 93 return ret; 94 } 95 96 static void mbt_mb_release(struct super_block *sb) 97 { 98 percpu_counter_destroy(&EXT4_SB(sb)->s_dirtyclusters_counter); 99 percpu_counter_destroy(&EXT4_SB(sb)->s_freeclusters_counter); 100 ext4_mb_release(sb); 101 kfree(sb->s_bdev->bd_queue); 102 kfree(sb->s_bdev); 103 } 104 105 static int mbt_set(struct super_block *sb, void *data) 106 { 107 return 0; 108 } 109 110 static struct super_block *mbt_ext4_alloc_super_block(void) 111 { 112 struct mbt_ext4_super_block *fsb; 113 struct super_block *sb; 114 struct ext4_sb_info *sbi; 115 116 fsb = kzalloc(sizeof(*fsb), GFP_KERNEL); 117 if (fsb == NULL) 118 return NULL; 119 120 sb = sget(&mbt_fs_type, NULL, mbt_set, 0, NULL); 121 if (IS_ERR(sb)) 122 goto out; 123 124 sbi = &fsb->sbi; 125 126 sbi->s_blockgroup_lock = 127 kzalloc(sizeof(struct blockgroup_lock), GFP_KERNEL); 128 if (!sbi->s_blockgroup_lock) 129 goto out_deactivate; 130 131 bgl_lock_init(sbi->s_blockgroup_lock); 132 133 sbi->s_es = &fsb->es; 134 sb->s_fs_info = sbi; 135 136 up_write(&sb->s_umount); 137 return sb; 138 139 out_deactivate: 140 deactivate_locked_super(sb); 141 out: 142 kfree(fsb); 143 return NULL; 144 } 145 146 static void mbt_ext4_free_super_block(struct super_block *sb) 147 { 148 struct mbt_ext4_super_block *fsb = MBT_SB(sb); 149 struct ext4_sb_info *sbi = EXT4_SB(sb); 150 151 kfree(sbi->s_blockgroup_lock); 152 deactivate_super(sb); 153 kfree(fsb); 154 } 155 156 struct mbt_ext4_block_layout { 157 unsigned char blocksize_bits; 158 unsigned int cluster_bits; 159 uint32_t blocks_per_group; 160 ext4_group_t group_count; 161 uint16_t desc_size; 162 }; 163 164 static void mbt_init_sb_layout(struct super_block *sb, 165 struct mbt_ext4_block_layout *layout) 166 { 167 struct ext4_sb_info *sbi = EXT4_SB(sb); 168 struct ext4_super_block *es = sbi->s_es; 169 170 sb->s_blocksize = 1UL << layout->blocksize_bits; 171 sb->s_blocksize_bits = layout->blocksize_bits; 172 173 sbi->s_groups_count = layout->group_count; 174 sbi->s_blocks_per_group = layout->blocks_per_group; 175 sbi->s_cluster_bits = layout->cluster_bits; 176 sbi->s_cluster_ratio = 1U << layout->cluster_bits; 177 sbi->s_clusters_per_group = layout->blocks_per_group >> 178 layout->cluster_bits; 179 sbi->s_desc_size = layout->desc_size; 180 sbi->s_desc_per_block_bits = 181 sb->s_blocksize_bits - (fls(layout->desc_size) - 1); 182 sbi->s_desc_per_block = 1 << sbi->s_desc_per_block_bits; 183 184 es->s_first_data_block = cpu_to_le32(0); 185 es->s_blocks_count_lo = cpu_to_le32(layout->blocks_per_group * 186 layout->group_count); 187 } 188 189 static int mbt_grp_ctx_init(struct super_block *sb, 190 struct mbt_grp_ctx *grp_ctx) 191 { 192 ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb); 193 194 grp_ctx->bitmap_bh.b_data = kzalloc(EXT4_BLOCK_SIZE(sb), GFP_KERNEL); 195 if (grp_ctx->bitmap_bh.b_data == NULL) 196 return -ENOMEM; 197 mb_set_bits(grp_ctx->bitmap_bh.b_data, max, sb->s_blocksize * 8 - max); 198 ext4_free_group_clusters_set(sb, &grp_ctx->desc, max); 199 200 return 0; 201 } 202 203 static void mbt_grp_ctx_release(struct mbt_grp_ctx *grp_ctx) 204 { 205 kfree(grp_ctx->bitmap_bh.b_data); 206 grp_ctx->bitmap_bh.b_data = NULL; 207 } 208 209 static void mbt_ctx_mark_used(struct super_block *sb, ext4_group_t group, 210 unsigned int start, unsigned int len) 211 { 212 struct mbt_grp_ctx *grp_ctx = MBT_GRP_CTX(sb, group); 213 214 mb_set_bits(grp_ctx->bitmap_bh.b_data, start, len); 215 } 216 217 static void *mbt_ctx_bitmap(struct super_block *sb, ext4_group_t group) 218 { 219 struct mbt_grp_ctx *grp_ctx = MBT_GRP_CTX(sb, group); 220 221 return grp_ctx->bitmap_bh.b_data; 222 } 223 224 /* called after mbt_init_sb_layout */ 225 static int mbt_ctx_init(struct super_block *sb) 226 { 227 struct mbt_ctx *ctx = MBT_CTX(sb); 228 ext4_group_t i, ngroups = ext4_get_groups_count(sb); 229 230 ctx->grp_ctx = kcalloc(ngroups, sizeof(struct mbt_grp_ctx), 231 GFP_KERNEL); 232 if (ctx->grp_ctx == NULL) 233 return -ENOMEM; 234 235 for (i = 0; i < ngroups; i++) 236 if (mbt_grp_ctx_init(sb, &ctx->grp_ctx[i])) 237 goto out; 238 239 /* 240 * first data block(first cluster in first group) is used by 241 * metadata, mark it used to avoid to alloc data block at first 242 * block which will fail ext4_sb_block_valid check. 243 */ 244 mb_set_bits(ctx->grp_ctx[0].bitmap_bh.b_data, 0, 1); 245 ext4_free_group_clusters_set(sb, &ctx->grp_ctx[0].desc, 246 EXT4_CLUSTERS_PER_GROUP(sb) - 1); 247 248 return 0; 249 out: 250 while (i-- > 0) 251 mbt_grp_ctx_release(&ctx->grp_ctx[i]); 252 kfree(ctx->grp_ctx); 253 return -ENOMEM; 254 } 255 256 static void mbt_ctx_release(struct super_block *sb) 257 { 258 struct mbt_ctx *ctx = MBT_CTX(sb); 259 ext4_group_t i, ngroups = ext4_get_groups_count(sb); 260 261 for (i = 0; i < ngroups; i++) 262 mbt_grp_ctx_release(&ctx->grp_ctx[i]); 263 kfree(ctx->grp_ctx); 264 } 265 266 static struct buffer_head * 267 ext4_read_block_bitmap_nowait_stub(struct super_block *sb, ext4_group_t block_group, 268 bool ignore_locked) 269 { 270 struct mbt_grp_ctx *grp_ctx = MBT_GRP_CTX(sb, block_group); 271 272 /* paired with brelse from caller of ext4_read_block_bitmap_nowait */ 273 get_bh(&grp_ctx->bitmap_bh); 274 return &grp_ctx->bitmap_bh; 275 } 276 277 static int ext4_wait_block_bitmap_stub(struct super_block *sb, 278 ext4_group_t block_group, 279 struct buffer_head *bh) 280 { 281 /* 282 * real ext4_wait_block_bitmap will set these flags and 283 * functions like ext4_mb_init_cache will verify the flags. 284 */ 285 set_buffer_uptodate(bh); 286 set_bitmap_uptodate(bh); 287 set_buffer_verified(bh); 288 return 0; 289 } 290 291 static struct ext4_group_desc * 292 ext4_get_group_desc_stub(struct super_block *sb, ext4_group_t block_group, 293 struct buffer_head **bh) 294 { 295 struct mbt_grp_ctx *grp_ctx = MBT_GRP_CTX(sb, block_group); 296 297 if (bh != NULL) 298 *bh = &grp_ctx->gd_bh; 299 300 return &grp_ctx->desc; 301 } 302 303 static int 304 ext4_mb_mark_context_stub(handle_t *handle, struct super_block *sb, bool state, 305 ext4_group_t group, ext4_grpblk_t blkoff, 306 ext4_grpblk_t len, int flags, 307 ext4_grpblk_t *ret_changed) 308 { 309 struct mbt_grp_ctx *grp_ctx = MBT_GRP_CTX(sb, group); 310 struct buffer_head *bitmap_bh = &grp_ctx->bitmap_bh; 311 312 if (state) 313 mb_set_bits(bitmap_bh->b_data, blkoff, len); 314 else 315 mb_clear_bits(bitmap_bh->b_data, blkoff, len); 316 317 return 0; 318 } 319 320 #define TEST_GOAL_GROUP 1 321 static int mbt_kunit_init(struct kunit *test) 322 { 323 struct mbt_ext4_block_layout *layout = 324 (struct mbt_ext4_block_layout *)(test->param_value); 325 struct super_block *sb; 326 int ret; 327 328 sb = mbt_ext4_alloc_super_block(); 329 if (sb == NULL) 330 return -ENOMEM; 331 332 mbt_init_sb_layout(sb, layout); 333 334 ret = mbt_ctx_init(sb); 335 if (ret != 0) { 336 mbt_ext4_free_super_block(sb); 337 return ret; 338 } 339 340 test->priv = sb; 341 kunit_activate_static_stub(test, 342 ext4_read_block_bitmap_nowait, 343 ext4_read_block_bitmap_nowait_stub); 344 kunit_activate_static_stub(test, 345 ext4_wait_block_bitmap, 346 ext4_wait_block_bitmap_stub); 347 kunit_activate_static_stub(test, 348 ext4_get_group_desc, 349 ext4_get_group_desc_stub); 350 kunit_activate_static_stub(test, 351 ext4_mb_mark_context, 352 ext4_mb_mark_context_stub); 353 354 /* stub function will be called in mbt_mb_init->ext4_mb_init */ 355 if (mbt_mb_init(sb) != 0) { 356 mbt_ctx_release(sb); 357 mbt_ext4_free_super_block(sb); 358 return -ENOMEM; 359 } 360 361 return 0; 362 } 363 364 static void mbt_kunit_exit(struct kunit *test) 365 { 366 struct super_block *sb = (struct super_block *)test->priv; 367 368 mbt_mb_release(sb); 369 mbt_ctx_release(sb); 370 mbt_ext4_free_super_block(sb); 371 } 372 373 static void test_new_blocks_simple(struct kunit *test) 374 { 375 struct super_block *sb = (struct super_block *)test->priv; 376 struct inode *inode; 377 struct ext4_allocation_request ar; 378 ext4_group_t i, goal_group = TEST_GOAL_GROUP; 379 int err = 0; 380 ext4_fsblk_t found; 381 struct ext4_sb_info *sbi = EXT4_SB(sb); 382 383 inode = kunit_kzalloc(test, sizeof(*inode), GFP_KERNEL); 384 if (!inode) 385 return; 386 387 inode->i_sb = sb; 388 ar.inode = inode; 389 390 /* get block at goal */ 391 ar.goal = ext4_group_first_block_no(sb, goal_group); 392 found = ext4_mb_new_blocks_simple(&ar, &err); 393 KUNIT_ASSERT_EQ_MSG(test, ar.goal, found, 394 "failed to alloc block at goal, expected %llu found %llu", 395 ar.goal, found); 396 397 /* get block after goal in goal group */ 398 ar.goal = ext4_group_first_block_no(sb, goal_group); 399 found = ext4_mb_new_blocks_simple(&ar, &err); 400 KUNIT_ASSERT_EQ_MSG(test, ar.goal + EXT4_C2B(sbi, 1), found, 401 "failed to alloc block after goal in goal group, expected %llu found %llu", 402 ar.goal + 1, found); 403 404 /* get block after goal group */ 405 mbt_ctx_mark_used(sb, goal_group, 0, EXT4_CLUSTERS_PER_GROUP(sb)); 406 ar.goal = ext4_group_first_block_no(sb, goal_group); 407 found = ext4_mb_new_blocks_simple(&ar, &err); 408 KUNIT_ASSERT_EQ_MSG(test, 409 ext4_group_first_block_no(sb, goal_group + 1), found, 410 "failed to alloc block after goal group, expected %llu found %llu", 411 ext4_group_first_block_no(sb, goal_group + 1), found); 412 413 /* get block before goal group */ 414 for (i = goal_group; i < ext4_get_groups_count(sb); i++) 415 mbt_ctx_mark_used(sb, i, 0, EXT4_CLUSTERS_PER_GROUP(sb)); 416 ar.goal = ext4_group_first_block_no(sb, goal_group); 417 found = ext4_mb_new_blocks_simple(&ar, &err); 418 KUNIT_ASSERT_EQ_MSG(test, 419 ext4_group_first_block_no(sb, 0) + EXT4_C2B(sbi, 1), found, 420 "failed to alloc block before goal group, expected %llu found %llu", 421 ext4_group_first_block_no(sb, 0 + EXT4_C2B(sbi, 1)), found); 422 423 /* no block available, fail to allocate block */ 424 for (i = 0; i < ext4_get_groups_count(sb); i++) 425 mbt_ctx_mark_used(sb, i, 0, EXT4_CLUSTERS_PER_GROUP(sb)); 426 ar.goal = ext4_group_first_block_no(sb, goal_group); 427 found = ext4_mb_new_blocks_simple(&ar, &err); 428 KUNIT_ASSERT_NE_MSG(test, err, 0, 429 "unexpectedly get block when no block is available"); 430 } 431 432 #define TEST_RANGE_COUNT 8 433 434 struct test_range { 435 ext4_grpblk_t start; 436 ext4_grpblk_t len; 437 }; 438 439 static void 440 mbt_generate_test_ranges(struct super_block *sb, struct test_range *ranges, 441 int count) 442 { 443 ext4_grpblk_t start, len, max; 444 int i; 445 446 max = EXT4_CLUSTERS_PER_GROUP(sb) / count; 447 for (i = 0; i < count; i++) { 448 start = get_random_u32() % max; 449 len = get_random_u32() % max; 450 len = min(len, max - start); 451 452 ranges[i].start = start + i * max; 453 ranges[i].len = len; 454 } 455 } 456 457 static void 458 validate_free_blocks_simple(struct kunit *test, struct super_block *sb, 459 ext4_group_t goal_group, ext4_grpblk_t start, 460 ext4_grpblk_t len) 461 { 462 void *bitmap; 463 ext4_grpblk_t bit, max = EXT4_CLUSTERS_PER_GROUP(sb); 464 ext4_group_t i; 465 466 for (i = 0; i < ext4_get_groups_count(sb); i++) { 467 if (i == goal_group) 468 continue; 469 470 bitmap = mbt_ctx_bitmap(sb, i); 471 bit = mb_find_next_zero_bit(bitmap, max, 0); 472 KUNIT_ASSERT_EQ_MSG(test, bit, max, 473 "free block on unexpected group %d", i); 474 } 475 476 bitmap = mbt_ctx_bitmap(sb, goal_group); 477 bit = mb_find_next_zero_bit(bitmap, max, 0); 478 KUNIT_ASSERT_EQ(test, bit, start); 479 480 bit = mb_find_next_bit(bitmap, max, bit + 1); 481 KUNIT_ASSERT_EQ(test, bit, start + len); 482 } 483 484 static void 485 test_free_blocks_simple_range(struct kunit *test, ext4_group_t goal_group, 486 ext4_grpblk_t start, ext4_grpblk_t len) 487 { 488 struct super_block *sb = (struct super_block *)test->priv; 489 struct ext4_sb_info *sbi = EXT4_SB(sb); 490 struct inode *inode; 491 ext4_fsblk_t block; 492 493 inode = kunit_kzalloc(test, sizeof(*inode), GFP_KERNEL); 494 if (!inode) 495 return; 496 inode->i_sb = sb; 497 498 if (len == 0) 499 return; 500 501 block = ext4_group_first_block_no(sb, goal_group) + 502 EXT4_C2B(sbi, start); 503 ext4_free_blocks_simple(inode, block, len); 504 validate_free_blocks_simple(test, sb, goal_group, start, len); 505 mbt_ctx_mark_used(sb, goal_group, 0, EXT4_CLUSTERS_PER_GROUP(sb)); 506 } 507 508 static void test_free_blocks_simple(struct kunit *test) 509 { 510 struct super_block *sb = (struct super_block *)test->priv; 511 ext4_grpblk_t max = EXT4_CLUSTERS_PER_GROUP(sb); 512 ext4_group_t i; 513 struct test_range ranges[TEST_RANGE_COUNT]; 514 515 for (i = 0; i < ext4_get_groups_count(sb); i++) 516 mbt_ctx_mark_used(sb, i, 0, max); 517 518 mbt_generate_test_ranges(sb, ranges, TEST_RANGE_COUNT); 519 for (i = 0; i < TEST_RANGE_COUNT; i++) 520 test_free_blocks_simple_range(test, TEST_GOAL_GROUP, 521 ranges[i].start, ranges[i].len); 522 } 523 524 static void 525 test_mark_diskspace_used_range(struct kunit *test, 526 struct ext4_allocation_context *ac, 527 ext4_grpblk_t start, 528 ext4_grpblk_t len) 529 { 530 struct super_block *sb = (struct super_block *)test->priv; 531 int ret; 532 void *bitmap; 533 ext4_grpblk_t i, max; 534 535 /* ext4_mb_mark_diskspace_used will BUG if len is 0 */ 536 if (len == 0) 537 return; 538 539 ac->ac_b_ex.fe_group = TEST_GOAL_GROUP; 540 ac->ac_b_ex.fe_start = start; 541 ac->ac_b_ex.fe_len = len; 542 543 bitmap = mbt_ctx_bitmap(sb, TEST_GOAL_GROUP); 544 memset(bitmap, 0, sb->s_blocksize); 545 ret = ext4_mb_mark_diskspace_used(ac, NULL, 0); 546 KUNIT_ASSERT_EQ(test, ret, 0); 547 548 max = EXT4_CLUSTERS_PER_GROUP(sb); 549 i = mb_find_next_bit(bitmap, max, 0); 550 KUNIT_ASSERT_EQ(test, i, start); 551 i = mb_find_next_zero_bit(bitmap, max, i + 1); 552 KUNIT_ASSERT_EQ(test, i, start + len); 553 i = mb_find_next_bit(bitmap, max, i + 1); 554 KUNIT_ASSERT_EQ(test, max, i); 555 } 556 557 static void test_mark_diskspace_used(struct kunit *test) 558 { 559 struct super_block *sb = (struct super_block *)test->priv; 560 struct inode *inode; 561 struct ext4_allocation_context ac; 562 struct test_range ranges[TEST_RANGE_COUNT]; 563 int i; 564 565 mbt_generate_test_ranges(sb, ranges, TEST_RANGE_COUNT); 566 567 inode = kunit_kzalloc(test, sizeof(*inode), GFP_KERNEL); 568 if (!inode) 569 return; 570 inode->i_sb = sb; 571 572 ac.ac_status = AC_STATUS_FOUND; 573 ac.ac_sb = sb; 574 ac.ac_inode = inode; 575 for (i = 0; i < TEST_RANGE_COUNT; i++) 576 test_mark_diskspace_used_range(test, &ac, ranges[i].start, 577 ranges[i].len); 578 } 579 580 static void mbt_generate_buddy(struct super_block *sb, void *buddy, 581 void *bitmap, struct ext4_group_info *grp) 582 { 583 struct ext4_sb_info *sbi = EXT4_SB(sb); 584 uint32_t order, off; 585 void *bb, *bb_h; 586 int max; 587 588 memset(buddy, 0xff, sb->s_blocksize); 589 memset(grp, 0, offsetof(struct ext4_group_info, 590 bb_counters[MB_NUM_ORDERS(sb)])); 591 592 bb = bitmap; 593 max = EXT4_CLUSTERS_PER_GROUP(sb); 594 bb_h = buddy + sbi->s_mb_offsets[1]; 595 596 off = mb_find_next_zero_bit(bb, max, 0); 597 grp->bb_first_free = off; 598 while (off < max) { 599 grp->bb_counters[0]++; 600 grp->bb_free++; 601 602 if (!(off & 1) && !mb_test_bit(off + 1, bb)) { 603 grp->bb_free++; 604 grp->bb_counters[0]--; 605 mb_clear_bit(off >> 1, bb_h); 606 grp->bb_counters[1]++; 607 grp->bb_largest_free_order = 1; 608 off++; 609 } 610 611 off = mb_find_next_zero_bit(bb, max, off + 1); 612 } 613 614 for (order = 1; order < MB_NUM_ORDERS(sb) - 1; order++) { 615 bb = buddy + sbi->s_mb_offsets[order]; 616 bb_h = buddy + sbi->s_mb_offsets[order + 1]; 617 max = max >> 1; 618 off = mb_find_next_zero_bit(bb, max, 0); 619 620 while (off < max) { 621 if (!(off & 1) && !mb_test_bit(off + 1, bb)) { 622 mb_set_bits(bb, off, 2); 623 grp->bb_counters[order] -= 2; 624 mb_clear_bit(off >> 1, bb_h); 625 grp->bb_counters[order + 1]++; 626 grp->bb_largest_free_order = order + 1; 627 off++; 628 } 629 630 off = mb_find_next_zero_bit(bb, max, off + 1); 631 } 632 } 633 634 max = EXT4_CLUSTERS_PER_GROUP(sb); 635 off = mb_find_next_zero_bit(bitmap, max, 0); 636 while (off < max) { 637 grp->bb_fragments++; 638 639 off = mb_find_next_bit(bitmap, max, off + 1); 640 if (off + 1 >= max) 641 break; 642 643 off = mb_find_next_zero_bit(bitmap, max, off + 1); 644 } 645 } 646 647 static void 648 mbt_validate_group_info(struct kunit *test, struct ext4_group_info *grp1, 649 struct ext4_group_info *grp2) 650 { 651 struct super_block *sb = (struct super_block *)test->priv; 652 int i; 653 654 KUNIT_ASSERT_EQ(test, grp1->bb_first_free, 655 grp2->bb_first_free); 656 KUNIT_ASSERT_EQ(test, grp1->bb_fragments, 657 grp2->bb_fragments); 658 KUNIT_ASSERT_EQ(test, grp1->bb_free, grp2->bb_free); 659 KUNIT_ASSERT_EQ(test, grp1->bb_largest_free_order, 660 grp2->bb_largest_free_order); 661 662 for (i = 1; i < MB_NUM_ORDERS(sb); i++) { 663 KUNIT_ASSERT_EQ_MSG(test, grp1->bb_counters[i], 664 grp2->bb_counters[i], 665 "bb_counters[%d] diffs, expected %d, generated %d", 666 i, grp1->bb_counters[i], 667 grp2->bb_counters[i]); 668 } 669 } 670 671 static void 672 do_test_generate_buddy(struct kunit *test, struct super_block *sb, void *bitmap, 673 void *mbt_buddy, struct ext4_group_info *mbt_grp, 674 void *ext4_buddy, struct ext4_group_info *ext4_grp) 675 { 676 int i; 677 678 mbt_generate_buddy(sb, mbt_buddy, bitmap, mbt_grp); 679 680 for (i = 0; i < MB_NUM_ORDERS(sb); i++) 681 ext4_grp->bb_counters[i] = 0; 682 /* needed by validation in ext4_mb_generate_buddy */ 683 ext4_grp->bb_free = mbt_grp->bb_free; 684 memset(ext4_buddy, 0xff, sb->s_blocksize); 685 ext4_mb_generate_buddy(sb, ext4_buddy, bitmap, TEST_GOAL_GROUP, 686 ext4_grp); 687 688 KUNIT_ASSERT_EQ(test, memcmp(mbt_buddy, ext4_buddy, sb->s_blocksize), 689 0); 690 mbt_validate_group_info(test, mbt_grp, ext4_grp); 691 } 692 693 static void test_mb_generate_buddy(struct kunit *test) 694 { 695 struct super_block *sb = (struct super_block *)test->priv; 696 void *bitmap, *expected_bb, *generate_bb; 697 struct ext4_group_info *expected_grp, *generate_grp; 698 struct test_range ranges[TEST_RANGE_COUNT]; 699 int i; 700 701 bitmap = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 702 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, bitmap); 703 expected_bb = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 704 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, expected_bb); 705 generate_bb = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 706 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, generate_bb); 707 expected_grp = kunit_kzalloc(test, offsetof(struct ext4_group_info, 708 bb_counters[MB_NUM_ORDERS(sb)]), GFP_KERNEL); 709 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, expected_grp); 710 generate_grp = ext4_get_group_info(sb, TEST_GOAL_GROUP); 711 KUNIT_ASSERT_NOT_NULL(test, generate_grp); 712 713 mbt_generate_test_ranges(sb, ranges, TEST_RANGE_COUNT); 714 for (i = 0; i < TEST_RANGE_COUNT; i++) { 715 mb_set_bits(bitmap, ranges[i].start, ranges[i].len); 716 do_test_generate_buddy(test, sb, bitmap, expected_bb, 717 expected_grp, generate_bb, generate_grp); 718 } 719 } 720 721 static void 722 test_mb_mark_used_range(struct kunit *test, struct ext4_buddy *e4b, 723 ext4_grpblk_t start, ext4_grpblk_t len, void *bitmap, 724 void *buddy, struct ext4_group_info *grp) 725 { 726 struct super_block *sb = (struct super_block *)test->priv; 727 struct ext4_free_extent ex; 728 int i; 729 730 /* mb_mark_used only accepts non-zero len */ 731 if (len == 0) 732 return; 733 734 ex.fe_start = start; 735 ex.fe_len = len; 736 ex.fe_group = TEST_GOAL_GROUP; 737 738 ext4_lock_group(sb, TEST_GOAL_GROUP); 739 mb_mark_used(e4b, &ex); 740 ext4_unlock_group(sb, TEST_GOAL_GROUP); 741 742 mb_set_bits(bitmap, start, len); 743 /* bypass bb_free validatoin in ext4_mb_generate_buddy */ 744 grp->bb_free -= len; 745 memset(buddy, 0xff, sb->s_blocksize); 746 for (i = 0; i < MB_NUM_ORDERS(sb); i++) 747 grp->bb_counters[i] = 0; 748 ext4_mb_generate_buddy(sb, buddy, bitmap, 0, grp); 749 750 KUNIT_ASSERT_EQ(test, memcmp(buddy, e4b->bd_buddy, sb->s_blocksize), 751 0); 752 mbt_validate_group_info(test, grp, e4b->bd_info); 753 } 754 755 static void test_mb_mark_used(struct kunit *test) 756 { 757 struct ext4_buddy e4b; 758 struct super_block *sb = (struct super_block *)test->priv; 759 void *bitmap, *buddy; 760 struct ext4_group_info *grp; 761 int ret; 762 struct test_range ranges[TEST_RANGE_COUNT]; 763 int i; 764 765 /* buddy cache assumes that each page contains at least one block */ 766 if (sb->s_blocksize > PAGE_SIZE) 767 kunit_skip(test, "blocksize exceeds pagesize"); 768 769 bitmap = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 770 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, bitmap); 771 buddy = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 772 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buddy); 773 grp = kunit_kzalloc(test, offsetof(struct ext4_group_info, 774 bb_counters[MB_NUM_ORDERS(sb)]), GFP_KERNEL); 775 776 ret = ext4_mb_load_buddy(sb, TEST_GOAL_GROUP, &e4b); 777 KUNIT_ASSERT_EQ(test, ret, 0); 778 779 grp->bb_free = EXT4_CLUSTERS_PER_GROUP(sb); 780 mbt_generate_test_ranges(sb, ranges, TEST_RANGE_COUNT); 781 for (i = 0; i < TEST_RANGE_COUNT; i++) 782 test_mb_mark_used_range(test, &e4b, ranges[i].start, 783 ranges[i].len, bitmap, buddy, grp); 784 785 ext4_mb_unload_buddy(&e4b); 786 } 787 788 static void 789 test_mb_free_blocks_range(struct kunit *test, struct ext4_buddy *e4b, 790 ext4_grpblk_t start, ext4_grpblk_t len, void *bitmap, 791 void *buddy, struct ext4_group_info *grp) 792 { 793 struct super_block *sb = (struct super_block *)test->priv; 794 int i; 795 796 /* mb_free_blocks will WARN if len is 0 */ 797 if (len == 0) 798 return; 799 800 ext4_lock_group(sb, e4b->bd_group); 801 mb_free_blocks(NULL, e4b, start, len); 802 ext4_unlock_group(sb, e4b->bd_group); 803 804 mb_clear_bits(bitmap, start, len); 805 /* bypass bb_free validatoin in ext4_mb_generate_buddy */ 806 grp->bb_free += len; 807 memset(buddy, 0xff, sb->s_blocksize); 808 for (i = 0; i < MB_NUM_ORDERS(sb); i++) 809 grp->bb_counters[i] = 0; 810 ext4_mb_generate_buddy(sb, buddy, bitmap, 0, grp); 811 812 KUNIT_ASSERT_EQ(test, memcmp(buddy, e4b->bd_buddy, sb->s_blocksize), 813 0); 814 mbt_validate_group_info(test, grp, e4b->bd_info); 815 816 } 817 818 static void test_mb_free_blocks(struct kunit *test) 819 { 820 struct ext4_buddy e4b; 821 struct super_block *sb = (struct super_block *)test->priv; 822 void *bitmap, *buddy; 823 struct ext4_group_info *grp; 824 struct ext4_free_extent ex; 825 int ret; 826 int i; 827 struct test_range ranges[TEST_RANGE_COUNT]; 828 829 /* buddy cache assumes that each page contains at least one block */ 830 if (sb->s_blocksize > PAGE_SIZE) 831 kunit_skip(test, "blocksize exceeds pagesize"); 832 833 bitmap = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 834 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, bitmap); 835 buddy = kunit_kzalloc(test, sb->s_blocksize, GFP_KERNEL); 836 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, buddy); 837 grp = kunit_kzalloc(test, offsetof(struct ext4_group_info, 838 bb_counters[MB_NUM_ORDERS(sb)]), GFP_KERNEL); 839 840 ret = ext4_mb_load_buddy(sb, TEST_GOAL_GROUP, &e4b); 841 KUNIT_ASSERT_EQ(test, ret, 0); 842 843 ex.fe_start = 0; 844 ex.fe_len = EXT4_CLUSTERS_PER_GROUP(sb); 845 ex.fe_group = TEST_GOAL_GROUP; 846 847 ext4_lock_group(sb, TEST_GOAL_GROUP); 848 mb_mark_used(&e4b, &ex); 849 ext4_unlock_group(sb, TEST_GOAL_GROUP); 850 851 grp->bb_free = 0; 852 memset(bitmap, 0xff, sb->s_blocksize); 853 854 mbt_generate_test_ranges(sb, ranges, TEST_RANGE_COUNT); 855 for (i = 0; i < TEST_RANGE_COUNT; i++) 856 test_mb_free_blocks_range(test, &e4b, ranges[i].start, 857 ranges[i].len, bitmap, buddy, grp); 858 859 ext4_mb_unload_buddy(&e4b); 860 } 861 862 static const struct mbt_ext4_block_layout mbt_test_layouts[] = { 863 { 864 .blocksize_bits = 10, 865 .cluster_bits = 3, 866 .blocks_per_group = 8192, 867 .group_count = 4, 868 .desc_size = 64, 869 }, 870 { 871 .blocksize_bits = 12, 872 .cluster_bits = 3, 873 .blocks_per_group = 8192, 874 .group_count = 4, 875 .desc_size = 64, 876 }, 877 { 878 .blocksize_bits = 16, 879 .cluster_bits = 3, 880 .blocks_per_group = 8192, 881 .group_count = 4, 882 .desc_size = 64, 883 }, 884 }; 885 886 static void mbt_show_layout(const struct mbt_ext4_block_layout *layout, 887 char *desc) 888 { 889 snprintf(desc, KUNIT_PARAM_DESC_SIZE, "block_bits=%d cluster_bits=%d " 890 "blocks_per_group=%d group_count=%d desc_size=%d\n", 891 layout->blocksize_bits, layout->cluster_bits, 892 layout->blocks_per_group, layout->group_count, 893 layout->desc_size); 894 } 895 KUNIT_ARRAY_PARAM(mbt_layouts, mbt_test_layouts, mbt_show_layout); 896 897 static struct kunit_case mbt_test_cases[] = { 898 KUNIT_CASE_PARAM(test_new_blocks_simple, mbt_layouts_gen_params), 899 KUNIT_CASE_PARAM(test_free_blocks_simple, mbt_layouts_gen_params), 900 KUNIT_CASE_PARAM(test_mb_generate_buddy, mbt_layouts_gen_params), 901 KUNIT_CASE_PARAM(test_mb_mark_used, mbt_layouts_gen_params), 902 KUNIT_CASE_PARAM(test_mb_free_blocks, mbt_layouts_gen_params), 903 KUNIT_CASE_PARAM(test_mark_diskspace_used, mbt_layouts_gen_params), 904 {} 905 }; 906 907 static struct kunit_suite mbt_test_suite = { 908 .name = "ext4_mballoc_test", 909 .init = mbt_kunit_init, 910 .exit = mbt_kunit_exit, 911 .test_cases = mbt_test_cases, 912 }; 913 914 kunit_test_suites(&mbt_test_suite); 915 916 MODULE_LICENSE("GPL"); 917