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