1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2026 Meta. All rights reserved. 4 */ 5 6 #include <linux/sizes.h> 7 #include "btrfs-tests.h" 8 #include "../volumes.h" 9 #include "../disk-io.h" 10 #include "../extent-io-tree.h" 11 12 /* 13 * Tests for chunk allocator pending extent internals. 14 * These two functions form the core of searching the chunk allocation pending 15 * extent bitmap and have relatively easily definable semantics, so unit 16 * testing them can help ensure the correctness of chunk allocation. 17 */ 18 19 /* 20 * Describes the inputs to the system and expected results 21 * when testing btrfs_find_hole_in_pending_extents(). 22 */ 23 struct pending_extent_test_case { 24 const char *name; 25 /* Input range to search. */ 26 u64 hole_start; 27 u64 hole_len; 28 /* The size of hole we are searching for. */ 29 u64 min_hole_size; 30 /* 31 * Pending extents to set up (up to 2 for up to 3 holes) 32 * If len == 0, then it is skipped. 33 */ 34 struct { 35 u64 start; 36 u64 len; 37 } pending_extents[2]; 38 /* Expected outputs. */ 39 bool expected_found; 40 u64 expected_start; 41 u64 expected_len; 42 }; 43 44 static const struct pending_extent_test_case find_hole_tests[] = { 45 { 46 .name = "no pending extents", 47 .hole_start = 0, 48 .hole_len = 10ULL * SZ_1G, 49 .min_hole_size = SZ_1G, 50 .pending_extents = { }, 51 .expected_found = true, 52 .expected_start = 0, 53 .expected_len = 10ULL * SZ_1G, 54 }, 55 { 56 .name = "pending extent at start of range", 57 .hole_start = 0, 58 .hole_len = 10ULL * SZ_1G, 59 .min_hole_size = SZ_1G, 60 .pending_extents = { 61 { .start = 0, .len = SZ_1G }, 62 }, 63 .expected_found = true, 64 .expected_start = SZ_1G, 65 .expected_len = 9ULL * SZ_1G, 66 }, 67 { 68 .name = "pending extent overlapping start of range", 69 .hole_start = SZ_1G, 70 .hole_len = 9ULL * SZ_1G, 71 .min_hole_size = SZ_1G, 72 .pending_extents = { 73 { .start = 0, .len = SZ_2G }, 74 }, 75 .expected_found = true, 76 .expected_start = SZ_2G, 77 .expected_len = 8ULL * SZ_1G, 78 }, 79 { 80 .name = "two holes; first hole is exactly big enough", 81 .hole_start = 0, 82 .hole_len = 10ULL * SZ_1G, 83 .min_hole_size = SZ_1G, 84 .pending_extents = { 85 { .start = SZ_1G, .len = SZ_1G }, 86 }, 87 .expected_found = true, 88 .expected_start = 0, 89 .expected_len = SZ_1G, 90 }, 91 { 92 .name = "two holes; first hole is big enough", 93 .hole_start = 0, 94 .hole_len = 10ULL * SZ_1G, 95 .min_hole_size = SZ_1G, 96 .pending_extents = { 97 { .start = SZ_2G, .len = SZ_1G }, 98 }, 99 .expected_found = true, 100 .expected_start = 0, 101 .expected_len = SZ_2G, 102 }, 103 { 104 .name = "two holes; second hole is big enough", 105 .hole_start = 0, 106 .hole_len = 10ULL * SZ_1G, 107 .min_hole_size = SZ_2G, 108 .pending_extents = { 109 { .start = SZ_1G, .len = SZ_1G }, 110 }, 111 .expected_found = true, 112 .expected_start = SZ_2G, 113 .expected_len = 8ULL * SZ_1G, 114 }, 115 { 116 .name = "three holes; first hole big enough", 117 .hole_start = 0, 118 .hole_len = 10ULL * SZ_1G, 119 .min_hole_size = SZ_2G, 120 .pending_extents = { 121 { .start = SZ_2G, .len = SZ_1G }, 122 { .start = 4ULL * SZ_1G, .len = SZ_1G }, 123 }, 124 .expected_found = true, 125 .expected_start = 0, 126 .expected_len = SZ_2G, 127 }, 128 { 129 .name = "three holes; second hole big enough", 130 .hole_start = 0, 131 .hole_len = 10ULL * SZ_1G, 132 .min_hole_size = SZ_2G, 133 .pending_extents = { 134 { .start = SZ_1G, .len = SZ_1G }, 135 { .start = 5ULL * SZ_1G, .len = SZ_1G }, 136 }, 137 .expected_found = true, 138 .expected_start = SZ_2G, 139 .expected_len = 3ULL * SZ_1G, 140 }, 141 { 142 .name = "three holes; third hole big enough", 143 .hole_start = 0, 144 .hole_len = 10ULL * SZ_1G, 145 .min_hole_size = SZ_2G, 146 .pending_extents = { 147 { .start = SZ_1G, .len = SZ_1G }, 148 { .start = 3ULL * SZ_1G, .len = 5ULL * SZ_1G }, 149 }, 150 .expected_found = true, 151 .expected_start = 8ULL * SZ_1G, 152 .expected_len = SZ_2G, 153 }, 154 { 155 .name = "three holes; all holes too small", 156 .hole_start = 0, 157 .hole_len = 10ULL * SZ_1G, 158 .min_hole_size = SZ_2G, 159 .pending_extents = { 160 { .start = SZ_1G, .len = SZ_1G }, 161 { .start = 3ULL * SZ_1G, .len = 6ULL * SZ_1G }, 162 }, 163 .expected_found = false, 164 .expected_start = 0, 165 .expected_len = SZ_1G, 166 }, 167 { 168 .name = "three holes; all holes too small; first biggest", 169 .hole_start = 0, 170 .hole_len = 10ULL * SZ_1G, 171 .min_hole_size = 3ULL * SZ_1G, 172 .pending_extents = { 173 { .start = SZ_2G, .len = SZ_1G }, 174 { .start = 4ULL * SZ_1G, .len = 5ULL * SZ_1G }, 175 }, 176 .expected_found = false, 177 .expected_start = 0, 178 .expected_len = SZ_2G, 179 }, 180 { 181 .name = "three holes; all holes too small; second biggest", 182 .hole_start = 0, 183 .hole_len = 10ULL * SZ_1G, 184 .min_hole_size = 3ULL * SZ_1G, 185 .pending_extents = { 186 { .start = SZ_1G, .len = SZ_1G }, 187 { .start = 4ULL * SZ_1G, .len = 5ULL * SZ_1G }, 188 }, 189 .expected_found = false, 190 .expected_start = SZ_2G, 191 .expected_len = SZ_2G, 192 }, 193 { 194 .name = "three holes; all holes too small; third biggest", 195 .hole_start = 0, 196 .hole_len = 10ULL * SZ_1G, 197 .min_hole_size = 3ULL * SZ_1G, 198 .pending_extents = { 199 { .start = SZ_1G, .len = SZ_1G }, 200 { .start = 3ULL * SZ_1G, .len = 5ULL * SZ_1G }, 201 }, 202 .expected_found = false, 203 .expected_start = 8ULL * SZ_1G, 204 .expected_len = SZ_2G, 205 }, 206 { 207 .name = "hole entirely allocated by pending", 208 .hole_start = 0, 209 .hole_len = 10ULL * SZ_1G, 210 .min_hole_size = SZ_1G, 211 .pending_extents = { 212 { .start = 0, .len = 10ULL * SZ_1G }, 213 }, 214 .expected_found = false, 215 .expected_start = 10ULL * SZ_1G, 216 .expected_len = 0, 217 }, 218 { 219 .name = "pending extent at end of range", 220 .hole_start = 0, 221 .hole_len = 10ULL * SZ_1G, 222 .min_hole_size = SZ_1G, 223 .pending_extents = { 224 { .start = 9ULL * SZ_1G, .len = SZ_2G }, 225 }, 226 .expected_found = true, 227 .expected_start = 0, 228 .expected_len = 9ULL * SZ_1G, 229 }, 230 { 231 .name = "zero length input", 232 .hole_start = SZ_1G, 233 .hole_len = 0, 234 .min_hole_size = SZ_1G, 235 .pending_extents = { }, 236 .expected_found = false, 237 .expected_start = SZ_1G, 238 .expected_len = 0, 239 }, 240 }; 241 242 static int test_find_hole_in_pending(u32 sectorsize, u32 nodesize) 243 { 244 struct btrfs_fs_info *fs_info; 245 struct btrfs_device *device; 246 int ret = 0; 247 248 test_msg("running find_hole_in_pending_extents tests"); 249 250 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 251 if (!fs_info) { 252 test_std_err(TEST_ALLOC_FS_INFO); 253 return -ENOMEM; 254 } 255 256 device = btrfs_alloc_dummy_device(fs_info); 257 if (IS_ERR(device)) { 258 test_err("failed to allocate dummy device"); 259 ret = PTR_ERR(device); 260 goto out_free_fs_info; 261 } 262 device->fs_info = fs_info; 263 264 for (int i = 0; i < ARRAY_SIZE(find_hole_tests); i++) { 265 const struct pending_extent_test_case *test_case = &find_hole_tests[i]; 266 u64 hole_start = test_case->hole_start; 267 u64 hole_len = test_case->hole_len; 268 bool found; 269 270 for (int j = 0; j < ARRAY_SIZE(test_case->pending_extents); j++) { 271 u64 start = test_case->pending_extents[j].start; 272 u64 len = test_case->pending_extents[j].len; 273 274 if (!len) 275 continue; 276 btrfs_set_extent_bit(&device->alloc_state, 277 start, start + len - 1, 278 CHUNK_ALLOCATED, NULL); 279 } 280 281 mutex_lock(&fs_info->chunk_mutex); 282 found = btrfs_find_hole_in_pending_extents(device, &hole_start, &hole_len, 283 test_case->min_hole_size); 284 mutex_unlock(&fs_info->chunk_mutex); 285 286 if (found != test_case->expected_found) { 287 test_err("%s: expected found=%d, got found=%d", 288 test_case->name, test_case->expected_found, found); 289 ret = -EINVAL; 290 goto out_clear_pending_extents; 291 } 292 if (hole_start != test_case->expected_start || 293 hole_len != test_case->expected_len) { 294 test_err("%s: expected [%llu, %llu), got [%llu, %llu)", 295 test_case->name, test_case->expected_start, 296 test_case->expected_start + 297 test_case->expected_len, 298 hole_start, hole_start + hole_len); 299 ret = -EINVAL; 300 goto out_clear_pending_extents; 301 } 302 out_clear_pending_extents: 303 btrfs_clear_extent_bit(&device->alloc_state, 0, (u64)-1, 304 CHUNK_ALLOCATED, NULL); 305 if (ret) 306 break; 307 } 308 309 out_free_fs_info: 310 btrfs_free_dummy_fs_info(fs_info); 311 return ret; 312 } 313 314 /* 315 * Describes the inputs to the system and expected results 316 * when testing btrfs_first_pending_extent(). 317 */ 318 struct first_pending_test_case { 319 const char *name; 320 /* The range to look for a pending extent in. */ 321 u64 hole_start; 322 u64 hole_len; 323 /* The pending extent to look for. */ 324 struct { 325 u64 start; 326 u64 len; 327 } pending_extent; 328 /* Expected outputs. */ 329 bool expected_found; 330 u64 expected_pending_start; 331 u64 expected_pending_end; 332 }; 333 334 static const struct first_pending_test_case first_pending_tests[] = { 335 { 336 .name = "no pending extent", 337 .hole_start = 0, 338 .hole_len = 10ULL * SZ_1G, 339 .pending_extent = { 0, 0 }, 340 .expected_found = false, 341 }, 342 { 343 .name = "pending extent at search start", 344 .hole_start = SZ_1G, 345 .hole_len = 9ULL * SZ_1G, 346 .pending_extent = { SZ_1G, SZ_1G }, 347 .expected_found = true, 348 .expected_pending_start = SZ_1G, 349 .expected_pending_end = SZ_2G - 1, 350 }, 351 { 352 .name = "pending extent overlapping search start", 353 .hole_start = SZ_1G, 354 .hole_len = 9ULL * SZ_1G, 355 .pending_extent = { 0, SZ_2G }, 356 .expected_found = true, 357 .expected_pending_start = 0, 358 .expected_pending_end = SZ_2G - 1, 359 }, 360 { 361 .name = "pending extent inside search range", 362 .hole_start = 0, 363 .hole_len = 10ULL * SZ_1G, 364 .pending_extent = { SZ_2G, SZ_1G }, 365 .expected_found = true, 366 .expected_pending_start = SZ_2G, 367 .expected_pending_end = 3ULL * SZ_1G - 1, 368 }, 369 { 370 .name = "pending extent outside search range", 371 .hole_start = 0, 372 .hole_len = SZ_1G, 373 .pending_extent = { SZ_2G, SZ_1G }, 374 .expected_found = false, 375 }, 376 { 377 .name = "pending extent overlapping end of search range", 378 .hole_start = 0, 379 .hole_len = SZ_2G, 380 .pending_extent = { SZ_1G, SZ_2G }, 381 .expected_found = true, 382 .expected_pending_start = SZ_1G, 383 .expected_pending_end = 3ULL * SZ_1G - 1, 384 }, 385 }; 386 387 static int test_first_pending_extent(u32 sectorsize, u32 nodesize) 388 { 389 struct btrfs_fs_info *fs_info; 390 struct btrfs_device *device; 391 int ret = 0; 392 393 test_msg("running first_pending_extent tests"); 394 395 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 396 if (!fs_info) { 397 test_std_err(TEST_ALLOC_FS_INFO); 398 return -ENOMEM; 399 } 400 401 device = btrfs_alloc_dummy_device(fs_info); 402 if (IS_ERR(device)) { 403 test_err("failed to allocate dummy device"); 404 ret = PTR_ERR(device); 405 goto out_free_fs_info; 406 } 407 408 device->fs_info = fs_info; 409 410 for (int i = 0; i < ARRAY_SIZE(first_pending_tests); i++) { 411 const struct first_pending_test_case *test_case = &first_pending_tests[i]; 412 u64 start = test_case->pending_extent.start; 413 u64 len = test_case->pending_extent.len; 414 u64 pending_start, pending_end; 415 bool found; 416 417 if (len) { 418 btrfs_set_extent_bit(&device->alloc_state, 419 start, start + len - 1, 420 CHUNK_ALLOCATED, NULL); 421 } 422 423 mutex_lock(&fs_info->chunk_mutex); 424 found = btrfs_first_pending_extent(device, test_case->hole_start, 425 test_case->hole_len, 426 &pending_start, &pending_end); 427 mutex_unlock(&fs_info->chunk_mutex); 428 429 if (found != test_case->expected_found) { 430 test_err("%s: expected found=%d, got found=%d", 431 test_case->name, test_case->expected_found, found); 432 ret = -EINVAL; 433 goto out_clear_pending_extents; 434 } 435 if (!found) 436 goto out_clear_pending_extents; 437 438 if (pending_start != test_case->expected_pending_start || 439 pending_end != test_case->expected_pending_end) { 440 test_err("%s: expected pending [%llu, %llu], got [%llu, %llu]", 441 test_case->name, 442 test_case->expected_pending_start, 443 test_case->expected_pending_end, 444 pending_start, pending_end); 445 ret = -EINVAL; 446 goto out_clear_pending_extents; 447 } 448 449 out_clear_pending_extents: 450 btrfs_clear_extent_bit(&device->alloc_state, 0, (u64)-1, 451 CHUNK_ALLOCATED, NULL); 452 if (ret) 453 break; 454 } 455 456 out_free_fs_info: 457 btrfs_free_dummy_fs_info(fs_info); 458 return ret; 459 } 460 461 int btrfs_test_chunk_allocation(u32 sectorsize, u32 nodesize) 462 { 463 int ret; 464 465 test_msg("running chunk allocation tests"); 466 467 ret = test_first_pending_extent(sectorsize, nodesize); 468 if (ret) 469 return ret; 470 471 ret = test_find_hole_in_pending(sectorsize, nodesize); 472 if (ret) 473 return ret; 474 475 return 0; 476 } 477