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