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