diff options
Diffstat (limited to 'fs/btrfs/free-space-cache.c')
-rw-r--r-- | fs/btrfs/free-space-cache.c | 112 |
1 files changed, 49 insertions, 63 deletions
diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index b3cbb8939fa..6c7887a7770 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c | |||
@@ -2289,23 +2289,23 @@ out: | |||
2289 | static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group, | 2289 | static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group, |
2290 | struct btrfs_free_space *entry, | 2290 | struct btrfs_free_space *entry, |
2291 | struct btrfs_free_cluster *cluster, | 2291 | struct btrfs_free_cluster *cluster, |
2292 | u64 offset, u64 bytes, u64 min_bytes) | 2292 | u64 offset, u64 bytes, |
2293 | u64 cont1_bytes, u64 min_bytes) | ||
2293 | { | 2294 | { |
2294 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; | 2295 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; |
2295 | unsigned long next_zero; | 2296 | unsigned long next_zero; |
2296 | unsigned long i; | 2297 | unsigned long i; |
2297 | unsigned long search_bits; | 2298 | unsigned long want_bits; |
2298 | unsigned long total_bits; | 2299 | unsigned long min_bits; |
2299 | unsigned long found_bits; | 2300 | unsigned long found_bits; |
2300 | unsigned long start = 0; | 2301 | unsigned long start = 0; |
2301 | unsigned long total_found = 0; | 2302 | unsigned long total_found = 0; |
2302 | int ret; | 2303 | int ret; |
2303 | bool found = false; | ||
2304 | 2304 | ||
2305 | i = offset_to_bit(entry->offset, block_group->sectorsize, | 2305 | i = offset_to_bit(entry->offset, block_group->sectorsize, |
2306 | max_t(u64, offset, entry->offset)); | 2306 | max_t(u64, offset, entry->offset)); |
2307 | search_bits = bytes_to_bits(bytes, block_group->sectorsize); | 2307 | want_bits = bytes_to_bits(bytes, block_group->sectorsize); |
2308 | total_bits = bytes_to_bits(min_bytes, block_group->sectorsize); | 2308 | min_bits = bytes_to_bits(min_bytes, block_group->sectorsize); |
2309 | 2309 | ||
2310 | again: | 2310 | again: |
2311 | found_bits = 0; | 2311 | found_bits = 0; |
@@ -2314,7 +2314,7 @@ again: | |||
2314 | i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i + 1)) { | 2314 | i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i + 1)) { |
2315 | next_zero = find_next_zero_bit(entry->bitmap, | 2315 | next_zero = find_next_zero_bit(entry->bitmap, |
2316 | BITS_PER_BITMAP, i); | 2316 | BITS_PER_BITMAP, i); |
2317 | if (next_zero - i >= search_bits) { | 2317 | if (next_zero - i >= min_bits) { |
2318 | found_bits = next_zero - i; | 2318 | found_bits = next_zero - i; |
2319 | break; | 2319 | break; |
2320 | } | 2320 | } |
@@ -2324,10 +2324,9 @@ again: | |||
2324 | if (!found_bits) | 2324 | if (!found_bits) |
2325 | return -ENOSPC; | 2325 | return -ENOSPC; |
2326 | 2326 | ||
2327 | if (!found) { | 2327 | if (!total_found) { |
2328 | start = i; | 2328 | start = i; |
2329 | cluster->max_size = 0; | 2329 | cluster->max_size = 0; |
2330 | found = true; | ||
2331 | } | 2330 | } |
2332 | 2331 | ||
2333 | total_found += found_bits; | 2332 | total_found += found_bits; |
@@ -2335,13 +2334,8 @@ again: | |||
2335 | if (cluster->max_size < found_bits * block_group->sectorsize) | 2334 | if (cluster->max_size < found_bits * block_group->sectorsize) |
2336 | cluster->max_size = found_bits * block_group->sectorsize; | 2335 | cluster->max_size = found_bits * block_group->sectorsize; |
2337 | 2336 | ||
2338 | if (total_found < total_bits) { | 2337 | if (total_found < want_bits || cluster->max_size < cont1_bytes) { |
2339 | i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, next_zero); | 2338 | i = next_zero + 1; |
2340 | if (i - start > total_bits * 2) { | ||
2341 | total_found = 0; | ||
2342 | cluster->max_size = 0; | ||
2343 | found = false; | ||
2344 | } | ||
2345 | goto again; | 2339 | goto again; |
2346 | } | 2340 | } |
2347 | 2341 | ||
@@ -2357,23 +2351,23 @@ again: | |||
2357 | 2351 | ||
2358 | /* | 2352 | /* |
2359 | * This searches the block group for just extents to fill the cluster with. | 2353 | * This searches the block group for just extents to fill the cluster with. |
2354 | * Try to find a cluster with at least bytes total bytes, at least one | ||
2355 | * extent of cont1_bytes, and other clusters of at least min_bytes. | ||
2360 | */ | 2356 | */ |
2361 | static noinline int | 2357 | static noinline int |
2362 | setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, | 2358 | setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, |
2363 | struct btrfs_free_cluster *cluster, | 2359 | struct btrfs_free_cluster *cluster, |
2364 | struct list_head *bitmaps, u64 offset, u64 bytes, | 2360 | struct list_head *bitmaps, u64 offset, u64 bytes, |
2365 | u64 min_bytes) | 2361 | u64 cont1_bytes, u64 min_bytes) |
2366 | { | 2362 | { |
2367 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; | 2363 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; |
2368 | struct btrfs_free_space *first = NULL; | 2364 | struct btrfs_free_space *first = NULL; |
2369 | struct btrfs_free_space *entry = NULL; | 2365 | struct btrfs_free_space *entry = NULL; |
2370 | struct btrfs_free_space *prev = NULL; | ||
2371 | struct btrfs_free_space *last; | 2366 | struct btrfs_free_space *last; |
2372 | struct rb_node *node; | 2367 | struct rb_node *node; |
2373 | u64 window_start; | 2368 | u64 window_start; |
2374 | u64 window_free; | 2369 | u64 window_free; |
2375 | u64 max_extent; | 2370 | u64 max_extent; |
2376 | u64 max_gap = 128 * 1024; | ||
2377 | 2371 | ||
2378 | entry = tree_search_offset(ctl, offset, 0, 1); | 2372 | entry = tree_search_offset(ctl, offset, 0, 1); |
2379 | if (!entry) | 2373 | if (!entry) |
@@ -2383,8 +2377,8 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, | |||
2383 | * We don't want bitmaps, so just move along until we find a normal | 2377 | * We don't want bitmaps, so just move along until we find a normal |
2384 | * extent entry. | 2378 | * extent entry. |
2385 | */ | 2379 | */ |
2386 | while (entry->bitmap) { | 2380 | while (entry->bitmap || entry->bytes < min_bytes) { |
2387 | if (list_empty(&entry->list)) | 2381 | if (entry->bitmap && list_empty(&entry->list)) |
2388 | list_add_tail(&entry->list, bitmaps); | 2382 | list_add_tail(&entry->list, bitmaps); |
2389 | node = rb_next(&entry->offset_index); | 2383 | node = rb_next(&entry->offset_index); |
2390 | if (!node) | 2384 | if (!node) |
@@ -2397,12 +2391,9 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, | |||
2397 | max_extent = entry->bytes; | 2391 | max_extent = entry->bytes; |
2398 | first = entry; | 2392 | first = entry; |
2399 | last = entry; | 2393 | last = entry; |
2400 | prev = entry; | ||
2401 | 2394 | ||
2402 | while (window_free <= min_bytes) { | 2395 | for (node = rb_next(&entry->offset_index); node; |
2403 | node = rb_next(&entry->offset_index); | 2396 | node = rb_next(&entry->offset_index)) { |
2404 | if (!node) | ||
2405 | return -ENOSPC; | ||
2406 | entry = rb_entry(node, struct btrfs_free_space, offset_index); | 2397 | entry = rb_entry(node, struct btrfs_free_space, offset_index); |
2407 | 2398 | ||
2408 | if (entry->bitmap) { | 2399 | if (entry->bitmap) { |
@@ -2411,26 +2402,18 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, | |||
2411 | continue; | 2402 | continue; |
2412 | } | 2403 | } |
2413 | 2404 | ||
2414 | /* | 2405 | if (entry->bytes < min_bytes) |
2415 | * we haven't filled the empty size and the window is | 2406 | continue; |
2416 | * very large. reset and try again | 2407 | |
2417 | */ | 2408 | last = entry; |
2418 | if (entry->offset - (prev->offset + prev->bytes) > max_gap || | 2409 | window_free += entry->bytes; |
2419 | entry->offset - window_start > (min_bytes * 2)) { | 2410 | if (entry->bytes > max_extent) |
2420 | first = entry; | ||
2421 | window_start = entry->offset; | ||
2422 | window_free = entry->bytes; | ||
2423 | last = entry; | ||
2424 | max_extent = entry->bytes; | 2411 | max_extent = entry->bytes; |
2425 | } else { | ||
2426 | last = entry; | ||
2427 | window_free += entry->bytes; | ||
2428 | if (entry->bytes > max_extent) | ||
2429 | max_extent = entry->bytes; | ||
2430 | } | ||
2431 | prev = entry; | ||
2432 | } | 2412 | } |
2433 | 2413 | ||
2414 | if (window_free < bytes || max_extent < cont1_bytes) | ||
2415 | return -ENOSPC; | ||
2416 | |||
2434 | cluster->window_start = first->offset; | 2417 | cluster->window_start = first->offset; |
2435 | 2418 | ||
2436 | node = &first->offset_index; | 2419 | node = &first->offset_index; |
@@ -2444,7 +2427,7 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, | |||
2444 | 2427 | ||
2445 | entry = rb_entry(node, struct btrfs_free_space, offset_index); | 2428 | entry = rb_entry(node, struct btrfs_free_space, offset_index); |
2446 | node = rb_next(&entry->offset_index); | 2429 | node = rb_next(&entry->offset_index); |
2447 | if (entry->bitmap) | 2430 | if (entry->bitmap || entry->bytes < min_bytes) |
2448 | continue; | 2431 | continue; |
2449 | 2432 | ||
2450 | rb_erase(&entry->offset_index, &ctl->free_space_offset); | 2433 | rb_erase(&entry->offset_index, &ctl->free_space_offset); |
@@ -2466,7 +2449,7 @@ static noinline int | |||
2466 | setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, | 2449 | setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, |
2467 | struct btrfs_free_cluster *cluster, | 2450 | struct btrfs_free_cluster *cluster, |
2468 | struct list_head *bitmaps, u64 offset, u64 bytes, | 2451 | struct list_head *bitmaps, u64 offset, u64 bytes, |
2469 | u64 min_bytes) | 2452 | u64 cont1_bytes, u64 min_bytes) |
2470 | { | 2453 | { |
2471 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; | 2454 | struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; |
2472 | struct btrfs_free_space *entry; | 2455 | struct btrfs_free_space *entry; |
@@ -2491,7 +2474,7 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, | |||
2491 | if (entry->bytes < min_bytes) | 2474 | if (entry->bytes < min_bytes) |
2492 | continue; | 2475 | continue; |
2493 | ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset, | 2476 | ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset, |
2494 | bytes, min_bytes); | 2477 | bytes, cont1_bytes, min_bytes); |
2495 | if (!ret) | 2478 | if (!ret) |
2496 | return 0; | 2479 | return 0; |
2497 | } | 2480 | } |
@@ -2505,7 +2488,7 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, | |||
2505 | 2488 | ||
2506 | /* | 2489 | /* |
2507 | * here we try to find a cluster of blocks in a block group. The goal | 2490 | * here we try to find a cluster of blocks in a block group. The goal |
2508 | * is to find at least bytes free and up to empty_size + bytes free. | 2491 | * is to find at least bytes+empty_size. |
2509 | * We might not find them all in one contiguous area. | 2492 | * We might not find them all in one contiguous area. |
2510 | * | 2493 | * |
2511 | * returns zero and sets up cluster if things worked out, otherwise | 2494 | * returns zero and sets up cluster if things worked out, otherwise |
@@ -2521,23 +2504,24 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, | |||
2521 | struct btrfs_free_space *entry, *tmp; | 2504 | struct btrfs_free_space *entry, *tmp; |
2522 | LIST_HEAD(bitmaps); | 2505 | LIST_HEAD(bitmaps); |
2523 | u64 min_bytes; | 2506 | u64 min_bytes; |
2507 | u64 cont1_bytes; | ||
2524 | int ret; | 2508 | int ret; |
2525 | 2509 | ||
2526 | /* for metadata, allow allocates with more holes */ | 2510 | /* |
2511 | * Choose the minimum extent size we'll require for this | ||
2512 | * cluster. For SSD_SPREAD, don't allow any fragmentation. | ||
2513 | * For metadata, allow allocates with smaller extents. For | ||
2514 | * data, keep it dense. | ||
2515 | */ | ||
2527 | if (btrfs_test_opt(root, SSD_SPREAD)) { | 2516 | if (btrfs_test_opt(root, SSD_SPREAD)) { |
2528 | min_bytes = bytes + empty_size; | 2517 | cont1_bytes = min_bytes = bytes + empty_size; |
2529 | } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) { | 2518 | } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) { |
2530 | /* | 2519 | cont1_bytes = bytes; |
2531 | * we want to do larger allocations when we are | 2520 | min_bytes = block_group->sectorsize; |
2532 | * flushing out the delayed refs, it helps prevent | 2521 | } else { |
2533 | * making more work as we go along. | 2522 | cont1_bytes = max(bytes, (bytes + empty_size) >> 2); |
2534 | */ | 2523 | min_bytes = block_group->sectorsize; |
2535 | if (trans->transaction->delayed_refs.flushing) | 2524 | } |
2536 | min_bytes = max(bytes, (bytes + empty_size) >> 1); | ||
2537 | else | ||
2538 | min_bytes = max(bytes, (bytes + empty_size) >> 4); | ||
2539 | } else | ||
2540 | min_bytes = max(bytes, (bytes + empty_size) >> 2); | ||
2541 | 2525 | ||
2542 | spin_lock(&ctl->tree_lock); | 2526 | spin_lock(&ctl->tree_lock); |
2543 | 2527 | ||
@@ -2545,7 +2529,7 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, | |||
2545 | * If we know we don't have enough space to make a cluster don't even | 2529 | * If we know we don't have enough space to make a cluster don't even |
2546 | * bother doing all the work to try and find one. | 2530 | * bother doing all the work to try and find one. |
2547 | */ | 2531 | */ |
2548 | if (ctl->free_space < min_bytes) { | 2532 | if (ctl->free_space < bytes) { |
2549 | spin_unlock(&ctl->tree_lock); | 2533 | spin_unlock(&ctl->tree_lock); |
2550 | return -ENOSPC; | 2534 | return -ENOSPC; |
2551 | } | 2535 | } |
@@ -2559,10 +2543,12 @@ int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, | |||
2559 | } | 2543 | } |
2560 | 2544 | ||
2561 | ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset, | 2545 | ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset, |
2562 | bytes, min_bytes); | 2546 | bytes + empty_size, |
2547 | cont1_bytes, min_bytes); | ||
2563 | if (ret) | 2548 | if (ret) |
2564 | ret = setup_cluster_bitmap(block_group, cluster, &bitmaps, | 2549 | ret = setup_cluster_bitmap(block_group, cluster, &bitmaps, |
2565 | offset, bytes, min_bytes); | 2550 | offset, bytes + empty_size, |
2551 | cont1_bytes, min_bytes); | ||
2566 | 2552 | ||
2567 | /* Clear our temporary list */ | 2553 | /* Clear our temporary list */ |
2568 | list_for_each_entry_safe(entry, tmp, &bitmaps, list) | 2554 | list_for_each_entry_safe(entry, tmp, &bitmaps, list) |