1 /* 2 * Copyright (C) 2008 Red Hat. All rights reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public 6 * License v2 as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public 14 * License along with this program; if not, write to the 15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 16 * Boston, MA 021110-1307, USA. 17 */ 18 19 #include <linux/pagemap.h> 20 #include <linux/sched.h> 21 #include <linux/sched/signal.h> 22 #include <linux/slab.h> 23 #include <linux/math64.h> 24 #include <linux/ratelimit.h> 25 #include "ctree.h" 26 #include "free-space-cache.h" 27 #include "transaction.h" 28 #include "disk-io.h" 29 #include "extent_io.h" 30 #include "inode-map.h" 31 #include "volumes.h" 32 33 #define BITS_PER_BITMAP (PAGE_SIZE * 8UL) 34 #define MAX_CACHE_BYTES_PER_GIG SZ_32K 35 36 struct btrfs_trim_range { 37 u64 start; 38 u64 bytes; 39 struct list_head list; 40 }; 41 42 static int link_free_space(struct btrfs_free_space_ctl *ctl, 43 struct btrfs_free_space *info); 44 static void unlink_free_space(struct btrfs_free_space_ctl *ctl, 45 struct btrfs_free_space *info); 46 static int btrfs_wait_cache_io_root(struct btrfs_root *root, 47 struct btrfs_trans_handle *trans, 48 struct btrfs_io_ctl *io_ctl, 49 struct btrfs_path *path); 50 51 static struct inode *__lookup_free_space_inode(struct btrfs_root *root, 52 struct btrfs_path *path, 53 u64 offset) 54 { 55 struct btrfs_fs_info *fs_info = root->fs_info; 56 struct btrfs_key key; 57 struct btrfs_key location; 58 struct btrfs_disk_key disk_key; 59 struct btrfs_free_space_header *header; 60 struct extent_buffer *leaf; 61 struct inode *inode = NULL; 62 int ret; 63 64 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 65 key.offset = offset; 66 key.type = 0; 67 68 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 69 if (ret < 0) 70 return ERR_PTR(ret); 71 if (ret > 0) { 72 btrfs_release_path(path); 73 return ERR_PTR(-ENOENT); 74 } 75 76 leaf = path->nodes[0]; 77 header = btrfs_item_ptr(leaf, path->slots[0], 78 struct btrfs_free_space_header); 79 btrfs_free_space_key(leaf, header, &disk_key); 80 btrfs_disk_key_to_cpu(&location, &disk_key); 81 btrfs_release_path(path); 82 83 inode = btrfs_iget(fs_info->sb, &location, root, NULL); 84 if (IS_ERR(inode)) 85 return inode; 86 if (is_bad_inode(inode)) { 87 iput(inode); 88 return ERR_PTR(-ENOENT); 89 } 90 91 mapping_set_gfp_mask(inode->i_mapping, 92 mapping_gfp_constraint(inode->i_mapping, 93 ~(__GFP_FS | __GFP_HIGHMEM))); 94 95 return inode; 96 } 97 98 struct inode *lookup_free_space_inode(struct btrfs_fs_info *fs_info, 99 struct btrfs_block_group_cache 100 *block_group, struct btrfs_path *path) 101 { 102 struct inode *inode = NULL; 103 u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW; 104 105 spin_lock(&block_group->lock); 106 if (block_group->inode) 107 inode = igrab(block_group->inode); 108 spin_unlock(&block_group->lock); 109 if (inode) 110 return inode; 111 112 inode = __lookup_free_space_inode(fs_info->tree_root, path, 113 block_group->key.objectid); 114 if (IS_ERR(inode)) 115 return inode; 116 117 spin_lock(&block_group->lock); 118 if (!((BTRFS_I(inode)->flags & flags) == flags)) { 119 btrfs_info(fs_info, "Old style space inode found, converting."); 120 BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM | 121 BTRFS_INODE_NODATACOW; 122 block_group->disk_cache_state = BTRFS_DC_CLEAR; 123 } 124 125 if (!block_group->iref) { 126 block_group->inode = igrab(inode); 127 block_group->iref = 1; 128 } 129 spin_unlock(&block_group->lock); 130 131 return inode; 132 } 133 134 static int __create_free_space_inode(struct btrfs_root *root, 135 struct btrfs_trans_handle *trans, 136 struct btrfs_path *path, 137 u64 ino, u64 offset) 138 { 139 struct btrfs_key key; 140 struct btrfs_disk_key disk_key; 141 struct btrfs_free_space_header *header; 142 struct btrfs_inode_item *inode_item; 143 struct extent_buffer *leaf; 144 u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC; 145 int ret; 146 147 ret = btrfs_insert_empty_inode(trans, root, path, ino); 148 if (ret) 149 return ret; 150 151 /* We inline crc's for the free disk space cache */ 152 if (ino != BTRFS_FREE_INO_OBJECTID) 153 flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW; 154 155 leaf = path->nodes[0]; 156 inode_item = btrfs_item_ptr(leaf, path->slots[0], 157 struct btrfs_inode_item); 158 btrfs_item_key(leaf, &disk_key, path->slots[0]); 159 memzero_extent_buffer(leaf, (unsigned long)inode_item, 160 sizeof(*inode_item)); 161 btrfs_set_inode_generation(leaf, inode_item, trans->transid); 162 btrfs_set_inode_size(leaf, inode_item, 0); 163 btrfs_set_inode_nbytes(leaf, inode_item, 0); 164 btrfs_set_inode_uid(leaf, inode_item, 0); 165 btrfs_set_inode_gid(leaf, inode_item, 0); 166 btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600); 167 btrfs_set_inode_flags(leaf, inode_item, flags); 168 btrfs_set_inode_nlink(leaf, inode_item, 1); 169 btrfs_set_inode_transid(leaf, inode_item, trans->transid); 170 btrfs_set_inode_block_group(leaf, inode_item, offset); 171 btrfs_mark_buffer_dirty(leaf); 172 btrfs_release_path(path); 173 174 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 175 key.offset = offset; 176 key.type = 0; 177 ret = btrfs_insert_empty_item(trans, root, path, &key, 178 sizeof(struct btrfs_free_space_header)); 179 if (ret < 0) { 180 btrfs_release_path(path); 181 return ret; 182 } 183 184 leaf = path->nodes[0]; 185 header = btrfs_item_ptr(leaf, path->slots[0], 186 struct btrfs_free_space_header); 187 memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header)); 188 btrfs_set_free_space_key(leaf, header, &disk_key); 189 btrfs_mark_buffer_dirty(leaf); 190 btrfs_release_path(path); 191 192 return 0; 193 } 194 195 int create_free_space_inode(struct btrfs_fs_info *fs_info, 196 struct btrfs_trans_handle *trans, 197 struct btrfs_block_group_cache *block_group, 198 struct btrfs_path *path) 199 { 200 int ret; 201 u64 ino; 202 203 ret = btrfs_find_free_objectid(fs_info->tree_root, &ino); 204 if (ret < 0) 205 return ret; 206 207 return __create_free_space_inode(fs_info->tree_root, trans, path, ino, 208 block_group->key.objectid); 209 } 210 211 int btrfs_check_trunc_cache_free_space(struct btrfs_fs_info *fs_info, 212 struct btrfs_block_rsv *rsv) 213 { 214 u64 needed_bytes; 215 int ret; 216 217 /* 1 for slack space, 1 for updating the inode */ 218 needed_bytes = btrfs_calc_trunc_metadata_size(fs_info, 1) + 219 btrfs_calc_trans_metadata_size(fs_info, 1); 220 221 spin_lock(&rsv->lock); 222 if (rsv->reserved < needed_bytes) 223 ret = -ENOSPC; 224 else 225 ret = 0; 226 spin_unlock(&rsv->lock); 227 return ret; 228 } 229 230 int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans, 231 struct btrfs_block_group_cache *block_group, 232 struct inode *inode) 233 { 234 struct btrfs_root *root = BTRFS_I(inode)->root; 235 int ret = 0; 236 bool locked = false; 237 238 if (block_group) { 239 struct btrfs_path *path = btrfs_alloc_path(); 240 241 if (!path) { 242 ret = -ENOMEM; 243 goto fail; 244 } 245 locked = true; 246 mutex_lock(&trans->transaction->cache_write_mutex); 247 if (!list_empty(&block_group->io_list)) { 248 list_del_init(&block_group->io_list); 249 250 btrfs_wait_cache_io(trans, block_group, path); 251 btrfs_put_block_group(block_group); 252 } 253 254 /* 255 * now that we've truncated the cache away, its no longer 256 * setup or written 257 */ 258 spin_lock(&block_group->lock); 259 block_group->disk_cache_state = BTRFS_DC_CLEAR; 260 spin_unlock(&block_group->lock); 261 btrfs_free_path(path); 262 } 263 264 btrfs_i_size_write(BTRFS_I(inode), 0); 265 truncate_pagecache(inode, 0); 266 267 /* 268 * We don't need an orphan item because truncating the free space cache 269 * will never be split across transactions. 270 * We don't need to check for -EAGAIN because we're a free space 271 * cache inode 272 */ 273 ret = btrfs_truncate_inode_items(trans, root, inode, 274 0, BTRFS_EXTENT_DATA_KEY); 275 if (ret) 276 goto fail; 277 278 ret = btrfs_update_inode(trans, root, inode); 279 280 fail: 281 if (locked) 282 mutex_unlock(&trans->transaction->cache_write_mutex); 283 if (ret) 284 btrfs_abort_transaction(trans, ret); 285 286 return ret; 287 } 288 289 static void readahead_cache(struct inode *inode) 290 { 291 struct file_ra_state *ra; 292 unsigned long last_index; 293 294 ra = kzalloc(sizeof(*ra), GFP_NOFS); 295 if (!ra) 296 return; 297 298 file_ra_state_init(ra, inode->i_mapping); 299 last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT; 300 301 page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index); 302 303 kfree(ra); 304 } 305 306 static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode, 307 int write) 308 { 309 int num_pages; 310 int check_crcs = 0; 311 312 num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE); 313 314 if (btrfs_ino(BTRFS_I(inode)) != BTRFS_FREE_INO_OBJECTID) 315 check_crcs = 1; 316 317 /* Make sure we can fit our crcs into the first page */ 318 if (write && check_crcs && 319 (num_pages * sizeof(u32)) >= PAGE_SIZE) 320 return -ENOSPC; 321 322 memset(io_ctl, 0, sizeof(struct btrfs_io_ctl)); 323 324 io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS); 325 if (!io_ctl->pages) 326 return -ENOMEM; 327 328 io_ctl->num_pages = num_pages; 329 io_ctl->fs_info = btrfs_sb(inode->i_sb); 330 io_ctl->check_crcs = check_crcs; 331 io_ctl->inode = inode; 332 333 return 0; 334 } 335 336 static void io_ctl_free(struct btrfs_io_ctl *io_ctl) 337 { 338 kfree(io_ctl->pages); 339 io_ctl->pages = NULL; 340 } 341 342 static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl) 343 { 344 if (io_ctl->cur) { 345 io_ctl->cur = NULL; 346 io_ctl->orig = NULL; 347 } 348 } 349 350 static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear) 351 { 352 ASSERT(io_ctl->index < io_ctl->num_pages); 353 io_ctl->page = io_ctl->pages[io_ctl->index++]; 354 io_ctl->cur = page_address(io_ctl->page); 355 io_ctl->orig = io_ctl->cur; 356 io_ctl->size = PAGE_SIZE; 357 if (clear) 358 clear_page(io_ctl->cur); 359 } 360 361 static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl) 362 { 363 int i; 364 365 io_ctl_unmap_page(io_ctl); 366 367 for (i = 0; i < io_ctl->num_pages; i++) { 368 if (io_ctl->pages[i]) { 369 ClearPageChecked(io_ctl->pages[i]); 370 unlock_page(io_ctl->pages[i]); 371 put_page(io_ctl->pages[i]); 372 } 373 } 374 } 375 376 static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, struct inode *inode, 377 int uptodate) 378 { 379 struct page *page; 380 gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping); 381 int i; 382 383 for (i = 0; i < io_ctl->num_pages; i++) { 384 page = find_or_create_page(inode->i_mapping, i, mask); 385 if (!page) { 386 io_ctl_drop_pages(io_ctl); 387 return -ENOMEM; 388 } 389 io_ctl->pages[i] = page; 390 if (uptodate && !PageUptodate(page)) { 391 btrfs_readpage(NULL, page); 392 lock_page(page); 393 if (!PageUptodate(page)) { 394 btrfs_err(BTRFS_I(inode)->root->fs_info, 395 "error reading free space cache"); 396 io_ctl_drop_pages(io_ctl); 397 return -EIO; 398 } 399 } 400 } 401 402 for (i = 0; i < io_ctl->num_pages; i++) { 403 clear_page_dirty_for_io(io_ctl->pages[i]); 404 set_page_extent_mapped(io_ctl->pages[i]); 405 } 406 407 return 0; 408 } 409 410 static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation) 411 { 412 __le64 *val; 413 414 io_ctl_map_page(io_ctl, 1); 415 416 /* 417 * Skip the csum areas. If we don't check crcs then we just have a 418 * 64bit chunk at the front of the first page. 419 */ 420 if (io_ctl->check_crcs) { 421 io_ctl->cur += (sizeof(u32) * io_ctl->num_pages); 422 io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages); 423 } else { 424 io_ctl->cur += sizeof(u64); 425 io_ctl->size -= sizeof(u64) * 2; 426 } 427 428 val = io_ctl->cur; 429 *val = cpu_to_le64(generation); 430 io_ctl->cur += sizeof(u64); 431 } 432 433 static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation) 434 { 435 __le64 *gen; 436 437 /* 438 * Skip the crc area. If we don't check crcs then we just have a 64bit 439 * chunk at the front of the first page. 440 */ 441 if (io_ctl->check_crcs) { 442 io_ctl->cur += sizeof(u32) * io_ctl->num_pages; 443 io_ctl->size -= sizeof(u64) + 444 (sizeof(u32) * io_ctl->num_pages); 445 } else { 446 io_ctl->cur += sizeof(u64); 447 io_ctl->size -= sizeof(u64) * 2; 448 } 449 450 gen = io_ctl->cur; 451 if (le64_to_cpu(*gen) != generation) { 452 btrfs_err_rl(io_ctl->fs_info, 453 "space cache generation (%llu) does not match inode (%llu)", 454 *gen, generation); 455 io_ctl_unmap_page(io_ctl); 456 return -EIO; 457 } 458 io_ctl->cur += sizeof(u64); 459 return 0; 460 } 461 462 static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index) 463 { 464 u32 *tmp; 465 u32 crc = ~(u32)0; 466 unsigned offset = 0; 467 468 if (!io_ctl->check_crcs) { 469 io_ctl_unmap_page(io_ctl); 470 return; 471 } 472 473 if (index == 0) 474 offset = sizeof(u32) * io_ctl->num_pages; 475 476 crc = btrfs_csum_data(io_ctl->orig + offset, crc, 477 PAGE_SIZE - offset); 478 btrfs_csum_final(crc, (u8 *)&crc); 479 io_ctl_unmap_page(io_ctl); 480 tmp = page_address(io_ctl->pages[0]); 481 tmp += index; 482 *tmp = crc; 483 } 484 485 static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index) 486 { 487 u32 *tmp, val; 488 u32 crc = ~(u32)0; 489 unsigned offset = 0; 490 491 if (!io_ctl->check_crcs) { 492 io_ctl_map_page(io_ctl, 0); 493 return 0; 494 } 495 496 if (index == 0) 497 offset = sizeof(u32) * io_ctl->num_pages; 498 499 tmp = page_address(io_ctl->pages[0]); 500 tmp += index; 501 val = *tmp; 502 503 io_ctl_map_page(io_ctl, 0); 504 crc = btrfs_csum_data(io_ctl->orig + offset, crc, 505 PAGE_SIZE - offset); 506 btrfs_csum_final(crc, (u8 *)&crc); 507 if (val != crc) { 508 btrfs_err_rl(io_ctl->fs_info, 509 "csum mismatch on free space cache"); 510 io_ctl_unmap_page(io_ctl); 511 return -EIO; 512 } 513 514 return 0; 515 } 516 517 static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes, 518 void *bitmap) 519 { 520 struct btrfs_free_space_entry *entry; 521 522 if (!io_ctl->cur) 523 return -ENOSPC; 524 525 entry = io_ctl->cur; 526 entry->offset = cpu_to_le64(offset); 527 entry->bytes = cpu_to_le64(bytes); 528 entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP : 529 BTRFS_FREE_SPACE_EXTENT; 530 io_ctl->cur += sizeof(struct btrfs_free_space_entry); 531 io_ctl->size -= sizeof(struct btrfs_free_space_entry); 532 533 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry)) 534 return 0; 535 536 io_ctl_set_crc(io_ctl, io_ctl->index - 1); 537 538 /* No more pages to map */ 539 if (io_ctl->index >= io_ctl->num_pages) 540 return 0; 541 542 /* map the next page */ 543 io_ctl_map_page(io_ctl, 1); 544 return 0; 545 } 546 547 static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap) 548 { 549 if (!io_ctl->cur) 550 return -ENOSPC; 551 552 /* 553 * If we aren't at the start of the current page, unmap this one and 554 * map the next one if there is any left. 555 */ 556 if (io_ctl->cur != io_ctl->orig) { 557 io_ctl_set_crc(io_ctl, io_ctl->index - 1); 558 if (io_ctl->index >= io_ctl->num_pages) 559 return -ENOSPC; 560 io_ctl_map_page(io_ctl, 0); 561 } 562 563 memcpy(io_ctl->cur, bitmap, PAGE_SIZE); 564 io_ctl_set_crc(io_ctl, io_ctl->index - 1); 565 if (io_ctl->index < io_ctl->num_pages) 566 io_ctl_map_page(io_ctl, 0); 567 return 0; 568 } 569 570 static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl) 571 { 572 /* 573 * If we're not on the boundary we know we've modified the page and we 574 * need to crc the page. 575 */ 576 if (io_ctl->cur != io_ctl->orig) 577 io_ctl_set_crc(io_ctl, io_ctl->index - 1); 578 else 579 io_ctl_unmap_page(io_ctl); 580 581 while (io_ctl->index < io_ctl->num_pages) { 582 io_ctl_map_page(io_ctl, 1); 583 io_ctl_set_crc(io_ctl, io_ctl->index - 1); 584 } 585 } 586 587 static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl, 588 struct btrfs_free_space *entry, u8 *type) 589 { 590 struct btrfs_free_space_entry *e; 591 int ret; 592 593 if (!io_ctl->cur) { 594 ret = io_ctl_check_crc(io_ctl, io_ctl->index); 595 if (ret) 596 return ret; 597 } 598 599 e = io_ctl->cur; 600 entry->offset = le64_to_cpu(e->offset); 601 entry->bytes = le64_to_cpu(e->bytes); 602 *type = e->type; 603 io_ctl->cur += sizeof(struct btrfs_free_space_entry); 604 io_ctl->size -= sizeof(struct btrfs_free_space_entry); 605 606 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry)) 607 return 0; 608 609 io_ctl_unmap_page(io_ctl); 610 611 return 0; 612 } 613 614 static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl, 615 struct btrfs_free_space *entry) 616 { 617 int ret; 618 619 ret = io_ctl_check_crc(io_ctl, io_ctl->index); 620 if (ret) 621 return ret; 622 623 memcpy(entry->bitmap, io_ctl->cur, PAGE_SIZE); 624 io_ctl_unmap_page(io_ctl); 625 626 return 0; 627 } 628 629 /* 630 * Since we attach pinned extents after the fact we can have contiguous sections 631 * of free space that are split up in entries. This poses a problem with the 632 * tree logging stuff since it could have allocated across what appears to be 2 633 * entries since we would have merged the entries when adding the pinned extents 634 * back to the free space cache. So run through the space cache that we just 635 * loaded and merge contiguous entries. This will make the log replay stuff not 636 * blow up and it will make for nicer allocator behavior. 637 */ 638 static void merge_space_tree(struct btrfs_free_space_ctl *ctl) 639 { 640 struct btrfs_free_space *e, *prev = NULL; 641 struct rb_node *n; 642 643 again: 644 spin_lock(&ctl->tree_lock); 645 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) { 646 e = rb_entry(n, struct btrfs_free_space, offset_index); 647 if (!prev) 648 goto next; 649 if (e->bitmap || prev->bitmap) 650 goto next; 651 if (prev->offset + prev->bytes == e->offset) { 652 unlink_free_space(ctl, prev); 653 unlink_free_space(ctl, e); 654 prev->bytes += e->bytes; 655 kmem_cache_free(btrfs_free_space_cachep, e); 656 link_free_space(ctl, prev); 657 prev = NULL; 658 spin_unlock(&ctl->tree_lock); 659 goto again; 660 } 661 next: 662 prev = e; 663 } 664 spin_unlock(&ctl->tree_lock); 665 } 666 667 static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, 668 struct btrfs_free_space_ctl *ctl, 669 struct btrfs_path *path, u64 offset) 670 { 671 struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb); 672 struct btrfs_free_space_header *header; 673 struct extent_buffer *leaf; 674 struct btrfs_io_ctl io_ctl; 675 struct btrfs_key key; 676 struct btrfs_free_space *e, *n; 677 LIST_HEAD(bitmaps); 678 u64 num_entries; 679 u64 num_bitmaps; 680 u64 generation; 681 u8 type; 682 int ret = 0; 683 684 /* Nothing in the space cache, goodbye */ 685 if (!i_size_read(inode)) 686 return 0; 687 688 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 689 key.offset = offset; 690 key.type = 0; 691 692 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); 693 if (ret < 0) 694 return 0; 695 else if (ret > 0) { 696 btrfs_release_path(path); 697 return 0; 698 } 699 700 ret = -1; 701 702 leaf = path->nodes[0]; 703 header = btrfs_item_ptr(leaf, path->slots[0], 704 struct btrfs_free_space_header); 705 num_entries = btrfs_free_space_entries(leaf, header); 706 num_bitmaps = btrfs_free_space_bitmaps(leaf, header); 707 generation = btrfs_free_space_generation(leaf, header); 708 btrfs_release_path(path); 709 710 if (!BTRFS_I(inode)->generation) { 711 btrfs_info(fs_info, 712 "the free space cache file (%llu) is invalid, skip it", 713 offset); 714 return 0; 715 } 716 717 if (BTRFS_I(inode)->generation != generation) { 718 btrfs_err(fs_info, 719 "free space inode generation (%llu) did not match free space cache generation (%llu)", 720 BTRFS_I(inode)->generation, generation); 721 return 0; 722 } 723 724 if (!num_entries) 725 return 0; 726 727 ret = io_ctl_init(&io_ctl, inode, 0); 728 if (ret) 729 return ret; 730 731 readahead_cache(inode); 732 733 ret = io_ctl_prepare_pages(&io_ctl, inode, 1); 734 if (ret) 735 goto out; 736 737 ret = io_ctl_check_crc(&io_ctl, 0); 738 if (ret) 739 goto free_cache; 740 741 ret = io_ctl_check_generation(&io_ctl, generation); 742 if (ret) 743 goto free_cache; 744 745 while (num_entries) { 746 e = kmem_cache_zalloc(btrfs_free_space_cachep, 747 GFP_NOFS); 748 if (!e) 749 goto free_cache; 750 751 ret = io_ctl_read_entry(&io_ctl, e, &type); 752 if (ret) { 753 kmem_cache_free(btrfs_free_space_cachep, e); 754 goto free_cache; 755 } 756 757 if (!e->bytes) { 758 kmem_cache_free(btrfs_free_space_cachep, e); 759 goto free_cache; 760 } 761 762 if (type == BTRFS_FREE_SPACE_EXTENT) { 763 spin_lock(&ctl->tree_lock); 764 ret = link_free_space(ctl, e); 765 spin_unlock(&ctl->tree_lock); 766 if (ret) { 767 btrfs_err(fs_info, 768 "Duplicate entries in free space cache, dumping"); 769 kmem_cache_free(btrfs_free_space_cachep, e); 770 goto free_cache; 771 } 772 } else { 773 ASSERT(num_bitmaps); 774 num_bitmaps--; 775 e->bitmap = kzalloc(PAGE_SIZE, GFP_NOFS); 776 if (!e->bitmap) { 777 kmem_cache_free( 778 btrfs_free_space_cachep, e); 779 goto free_cache; 780 } 781 spin_lock(&ctl->tree_lock); 782 ret = link_free_space(ctl, e); 783 ctl->total_bitmaps++; 784 ctl->op->recalc_thresholds(ctl); 785 spin_unlock(&ctl->tree_lock); 786 if (ret) { 787 btrfs_err(fs_info, 788 "Duplicate entries in free space cache, dumping"); 789 kmem_cache_free(btrfs_free_space_cachep, e); 790 goto free_cache; 791 } 792 list_add_tail(&e->list, &bitmaps); 793 } 794 795 num_entries--; 796 } 797 798 io_ctl_unmap_page(&io_ctl); 799 800 /* 801 * We add the bitmaps at the end of the entries in order that 802 * the bitmap entries are added to the cache. 803 */ 804 list_for_each_entry_safe(e, n, &bitmaps, list) { 805 list_del_init(&e->list); 806 ret = io_ctl_read_bitmap(&io_ctl, e); 807 if (ret) 808 goto free_cache; 809 } 810 811 io_ctl_drop_pages(&io_ctl); 812 merge_space_tree(ctl); 813 ret = 1; 814 out: 815 io_ctl_free(&io_ctl); 816 return ret; 817 free_cache: 818 io_ctl_drop_pages(&io_ctl); 819 __btrfs_remove_free_space_cache(ctl); 820 goto out; 821 } 822 823 int load_free_space_cache(struct btrfs_fs_info *fs_info, 824 struct btrfs_block_group_cache *block_group) 825 { 826 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 827 struct inode *inode; 828 struct btrfs_path *path; 829 int ret = 0; 830 bool matched; 831 u64 used = btrfs_block_group_used(&block_group->item); 832 833 /* 834 * If this block group has been marked to be cleared for one reason or 835 * another then we can't trust the on disk cache, so just return. 836 */ 837 spin_lock(&block_group->lock); 838 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) { 839 spin_unlock(&block_group->lock); 840 return 0; 841 } 842 spin_unlock(&block_group->lock); 843 844 path = btrfs_alloc_path(); 845 if (!path) 846 return 0; 847 path->search_commit_root = 1; 848 path->skip_locking = 1; 849 850 inode = lookup_free_space_inode(fs_info, block_group, path); 851 if (IS_ERR(inode)) { 852 btrfs_free_path(path); 853 return 0; 854 } 855 856 /* We may have converted the inode and made the cache invalid. */ 857 spin_lock(&block_group->lock); 858 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) { 859 spin_unlock(&block_group->lock); 860 btrfs_free_path(path); 861 goto out; 862 } 863 spin_unlock(&block_group->lock); 864 865 ret = __load_free_space_cache(fs_info->tree_root, inode, ctl, 866 path, block_group->key.objectid); 867 btrfs_free_path(path); 868 if (ret <= 0) 869 goto out; 870 871 spin_lock(&ctl->tree_lock); 872 matched = (ctl->free_space == (block_group->key.offset - used - 873 block_group->bytes_super)); 874 spin_unlock(&ctl->tree_lock); 875 876 if (!matched) { 877 __btrfs_remove_free_space_cache(ctl); 878 btrfs_warn(fs_info, 879 "block group %llu has wrong amount of free space", 880 block_group->key.objectid); 881 ret = -1; 882 } 883 out: 884 if (ret < 0) { 885 /* This cache is bogus, make sure it gets cleared */ 886 spin_lock(&block_group->lock); 887 block_group->disk_cache_state = BTRFS_DC_CLEAR; 888 spin_unlock(&block_group->lock); 889 ret = 0; 890 891 btrfs_warn(fs_info, 892 "failed to load free space cache for block group %llu, rebuilding it now", 893 block_group->key.objectid); 894 } 895 896 iput(inode); 897 return ret; 898 } 899 900 static noinline_for_stack 901 int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl, 902 struct btrfs_free_space_ctl *ctl, 903 struct btrfs_block_group_cache *block_group, 904 int *entries, int *bitmaps, 905 struct list_head *bitmap_list) 906 { 907 int ret; 908 struct btrfs_free_cluster *cluster = NULL; 909 struct btrfs_free_cluster *cluster_locked = NULL; 910 struct rb_node *node = rb_first(&ctl->free_space_offset); 911 struct btrfs_trim_range *trim_entry; 912 913 /* Get the cluster for this block_group if it exists */ 914 if (block_group && !list_empty(&block_group->cluster_list)) { 915 cluster = list_entry(block_group->cluster_list.next, 916 struct btrfs_free_cluster, 917 block_group_list); 918 } 919 920 if (!node && cluster) { 921 cluster_locked = cluster; 922 spin_lock(&cluster_locked->lock); 923 node = rb_first(&cluster->root); 924 cluster = NULL; 925 } 926 927 /* Write out the extent entries */ 928 while (node) { 929 struct btrfs_free_space *e; 930 931 e = rb_entry(node, struct btrfs_free_space, offset_index); 932 *entries += 1; 933 934 ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes, 935 e->bitmap); 936 if (ret) 937 goto fail; 938 939 if (e->bitmap) { 940 list_add_tail(&e->list, bitmap_list); 941 *bitmaps += 1; 942 } 943 node = rb_next(node); 944 if (!node && cluster) { 945 node = rb_first(&cluster->root); 946 cluster_locked = cluster; 947 spin_lock(&cluster_locked->lock); 948 cluster = NULL; 949 } 950 } 951 if (cluster_locked) { 952 spin_unlock(&cluster_locked->lock); 953 cluster_locked = NULL; 954 } 955 956 /* 957 * Make sure we don't miss any range that was removed from our rbtree 958 * because trimming is running. Otherwise after a umount+mount (or crash 959 * after committing the transaction) we would leak free space and get 960 * an inconsistent free space cache report from fsck. 961 */ 962 list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) { 963 ret = io_ctl_add_entry(io_ctl, trim_entry->start, 964 trim_entry->bytes, NULL); 965 if (ret) 966 goto fail; 967 *entries += 1; 968 } 969 970 return 0; 971 fail: 972 if (cluster_locked) 973 spin_unlock(&cluster_locked->lock); 974 return -ENOSPC; 975 } 976 977 static noinline_for_stack int 978 update_cache_item(struct btrfs_trans_handle *trans, 979 struct btrfs_root *root, 980 struct inode *inode, 981 struct btrfs_path *path, u64 offset, 982 int entries, int bitmaps) 983 { 984 struct btrfs_key key; 985 struct btrfs_free_space_header *header; 986 struct extent_buffer *leaf; 987 int ret; 988 989 key.objectid = BTRFS_FREE_SPACE_OBJECTID; 990 key.offset = offset; 991 key.type = 0; 992 993 ret = btrfs_search_slot(trans, root, &key, path, 0, 1); 994 if (ret < 0) { 995 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1, 996 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL, 997 GFP_NOFS); 998 goto fail; 999 } 1000 leaf = path->nodes[0]; 1001 if (ret > 0) { 1002 struct btrfs_key found_key; 1003 ASSERT(path->slots[0]); 1004 path->slots[0]--; 1005 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 1006 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID || 1007 found_key.offset != offset) { 1008 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, 1009 inode->i_size - 1, 1010 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, 1011 NULL, GFP_NOFS); 1012 btrfs_release_path(path); 1013 goto fail; 1014 } 1015 } 1016 1017 BTRFS_I(inode)->generation = trans->transid; 1018 header = btrfs_item_ptr(leaf, path->slots[0], 1019 struct btrfs_free_space_header); 1020 btrfs_set_free_space_entries(leaf, header, entries); 1021 btrfs_set_free_space_bitmaps(leaf, header, bitmaps); 1022 btrfs_set_free_space_generation(leaf, header, trans->transid); 1023 btrfs_mark_buffer_dirty(leaf); 1024 btrfs_release_path(path); 1025 1026 return 0; 1027 1028 fail: 1029 return -1; 1030 } 1031 1032 static noinline_for_stack int 1033 write_pinned_extent_entries(struct btrfs_fs_info *fs_info, 1034 struct btrfs_block_group_cache *block_group, 1035 struct btrfs_io_ctl *io_ctl, 1036 int *entries) 1037 { 1038 u64 start, extent_start, extent_end, len; 1039 struct extent_io_tree *unpin = NULL; 1040 int ret; 1041 1042 if (!block_group) 1043 return 0; 1044 1045 /* 1046 * We want to add any pinned extents to our free space cache 1047 * so we don't leak the space 1048 * 1049 * We shouldn't have switched the pinned extents yet so this is the 1050 * right one 1051 */ 1052 unpin = fs_info->pinned_extents; 1053 1054 start = block_group->key.objectid; 1055 1056 while (start < block_group->key.objectid + block_group->key.offset) { 1057 ret = find_first_extent_bit(unpin, start, 1058 &extent_start, &extent_end, 1059 EXTENT_DIRTY, NULL); 1060 if (ret) 1061 return 0; 1062 1063 /* This pinned extent is out of our range */ 1064 if (extent_start >= block_group->key.objectid + 1065 block_group->key.offset) 1066 return 0; 1067 1068 extent_start = max(extent_start, start); 1069 extent_end = min(block_group->key.objectid + 1070 block_group->key.offset, extent_end + 1); 1071 len = extent_end - extent_start; 1072 1073 *entries += 1; 1074 ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL); 1075 if (ret) 1076 return -ENOSPC; 1077 1078 start = extent_end; 1079 } 1080 1081 return 0; 1082 } 1083 1084 static noinline_for_stack int 1085 write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list) 1086 { 1087 struct btrfs_free_space *entry, *next; 1088 int ret; 1089 1090 /* Write out the bitmaps */ 1091 list_for_each_entry_safe(entry, next, bitmap_list, list) { 1092 ret = io_ctl_add_bitmap(io_ctl, entry->bitmap); 1093 if (ret) 1094 return -ENOSPC; 1095 list_del_init(&entry->list); 1096 } 1097 1098 return 0; 1099 } 1100 1101 static int flush_dirty_cache(struct inode *inode) 1102 { 1103 int ret; 1104 1105 ret = btrfs_wait_ordered_range(inode, 0, (u64)-1); 1106 if (ret) 1107 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1, 1108 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL, 1109 GFP_NOFS); 1110 1111 return ret; 1112 } 1113 1114 static void noinline_for_stack 1115 cleanup_bitmap_list(struct list_head *bitmap_list) 1116 { 1117 struct btrfs_free_space *entry, *next; 1118 1119 list_for_each_entry_safe(entry, next, bitmap_list, list) 1120 list_del_init(&entry->list); 1121 } 1122 1123 static void noinline_for_stack 1124 cleanup_write_cache_enospc(struct inode *inode, 1125 struct btrfs_io_ctl *io_ctl, 1126 struct extent_state **cached_state) 1127 { 1128 io_ctl_drop_pages(io_ctl); 1129 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0, 1130 i_size_read(inode) - 1, cached_state, 1131 GFP_NOFS); 1132 } 1133 1134 static int __btrfs_wait_cache_io(struct btrfs_root *root, 1135 struct btrfs_trans_handle *trans, 1136 struct btrfs_block_group_cache *block_group, 1137 struct btrfs_io_ctl *io_ctl, 1138 struct btrfs_path *path, u64 offset) 1139 { 1140 int ret; 1141 struct inode *inode = io_ctl->inode; 1142 struct btrfs_fs_info *fs_info; 1143 1144 if (!inode) 1145 return 0; 1146 1147 fs_info = btrfs_sb(inode->i_sb); 1148 1149 /* Flush the dirty pages in the cache file. */ 1150 ret = flush_dirty_cache(inode); 1151 if (ret) 1152 goto out; 1153 1154 /* Update the cache item to tell everyone this cache file is valid. */ 1155 ret = update_cache_item(trans, root, inode, path, offset, 1156 io_ctl->entries, io_ctl->bitmaps); 1157 out: 1158 io_ctl_free(io_ctl); 1159 if (ret) { 1160 invalidate_inode_pages2(inode->i_mapping); 1161 BTRFS_I(inode)->generation = 0; 1162 if (block_group) { 1163 #ifdef DEBUG 1164 btrfs_err(fs_info, 1165 "failed to write free space cache for block group %llu", 1166 block_group->key.objectid); 1167 #endif 1168 } 1169 } 1170 btrfs_update_inode(trans, root, inode); 1171 1172 if (block_group) { 1173 /* the dirty list is protected by the dirty_bgs_lock */ 1174 spin_lock(&trans->transaction->dirty_bgs_lock); 1175 1176 /* the disk_cache_state is protected by the block group lock */ 1177 spin_lock(&block_group->lock); 1178 1179 /* 1180 * only mark this as written if we didn't get put back on 1181 * the dirty list while waiting for IO. Otherwise our 1182 * cache state won't be right, and we won't get written again 1183 */ 1184 if (!ret && list_empty(&block_group->dirty_list)) 1185 block_group->disk_cache_state = BTRFS_DC_WRITTEN; 1186 else if (ret) 1187 block_group->disk_cache_state = BTRFS_DC_ERROR; 1188 1189 spin_unlock(&block_group->lock); 1190 spin_unlock(&trans->transaction->dirty_bgs_lock); 1191 io_ctl->inode = NULL; 1192 iput(inode); 1193 } 1194 1195 return ret; 1196 1197 } 1198 1199 static int btrfs_wait_cache_io_root(struct btrfs_root *root, 1200 struct btrfs_trans_handle *trans, 1201 struct btrfs_io_ctl *io_ctl, 1202 struct btrfs_path *path) 1203 { 1204 return __btrfs_wait_cache_io(root, trans, NULL, io_ctl, path, 0); 1205 } 1206 1207 int btrfs_wait_cache_io(struct btrfs_trans_handle *trans, 1208 struct btrfs_block_group_cache *block_group, 1209 struct btrfs_path *path) 1210 { 1211 return __btrfs_wait_cache_io(block_group->fs_info->tree_root, trans, 1212 block_group, &block_group->io_ctl, 1213 path, block_group->key.objectid); 1214 } 1215 1216 /** 1217 * __btrfs_write_out_cache - write out cached info to an inode 1218 * @root - the root the inode belongs to 1219 * @ctl - the free space cache we are going to write out 1220 * @block_group - the block_group for this cache if it belongs to a block_group 1221 * @trans - the trans handle 1222 * 1223 * This function writes out a free space cache struct to disk for quick recovery 1224 * on mount. This will return 0 if it was successful in writing the cache out, 1225 * or an errno if it was not. 1226 */ 1227 static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode, 1228 struct btrfs_free_space_ctl *ctl, 1229 struct btrfs_block_group_cache *block_group, 1230 struct btrfs_io_ctl *io_ctl, 1231 struct btrfs_trans_handle *trans) 1232 { 1233 struct btrfs_fs_info *fs_info = root->fs_info; 1234 struct extent_state *cached_state = NULL; 1235 LIST_HEAD(bitmap_list); 1236 int entries = 0; 1237 int bitmaps = 0; 1238 int ret; 1239 int must_iput = 0; 1240 1241 if (!i_size_read(inode)) 1242 return -EIO; 1243 1244 WARN_ON(io_ctl->pages); 1245 ret = io_ctl_init(io_ctl, inode, 1); 1246 if (ret) 1247 return ret; 1248 1249 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) { 1250 down_write(&block_group->data_rwsem); 1251 spin_lock(&block_group->lock); 1252 if (block_group->delalloc_bytes) { 1253 block_group->disk_cache_state = BTRFS_DC_WRITTEN; 1254 spin_unlock(&block_group->lock); 1255 up_write(&block_group->data_rwsem); 1256 BTRFS_I(inode)->generation = 0; 1257 ret = 0; 1258 must_iput = 1; 1259 goto out; 1260 } 1261 spin_unlock(&block_group->lock); 1262 } 1263 1264 /* Lock all pages first so we can lock the extent safely. */ 1265 ret = io_ctl_prepare_pages(io_ctl, inode, 0); 1266 if (ret) 1267 goto out_unlock; 1268 1269 lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1, 1270 &cached_state); 1271 1272 io_ctl_set_generation(io_ctl, trans->transid); 1273 1274 mutex_lock(&ctl->cache_writeout_mutex); 1275 /* Write out the extent entries in the free space cache */ 1276 spin_lock(&ctl->tree_lock); 1277 ret = write_cache_extent_entries(io_ctl, ctl, 1278 block_group, &entries, &bitmaps, 1279 &bitmap_list); 1280 if (ret) 1281 goto out_nospc_locked; 1282 1283 /* 1284 * Some spaces that are freed in the current transaction are pinned, 1285 * they will be added into free space cache after the transaction is 1286 * committed, we shouldn't lose them. 1287 * 1288 * If this changes while we are working we'll get added back to 1289 * the dirty list and redo it. No locking needed 1290 */ 1291 ret = write_pinned_extent_entries(fs_info, block_group, 1292 io_ctl, &entries); 1293 if (ret) 1294 goto out_nospc_locked; 1295 1296 /* 1297 * At last, we write out all the bitmaps and keep cache_writeout_mutex 1298 * locked while doing it because a concurrent trim can be manipulating 1299 * or freeing the bitmap. 1300 */ 1301 ret = write_bitmap_entries(io_ctl, &bitmap_list); 1302 spin_unlock(&ctl->tree_lock); 1303 mutex_unlock(&ctl->cache_writeout_mutex); 1304 if (ret) 1305 goto out_nospc; 1306 1307 /* Zero out the rest of the pages just to make sure */ 1308 io_ctl_zero_remaining_pages(io_ctl); 1309 1310 /* Everything is written out, now we dirty the pages in the file. */ 1311 ret = btrfs_dirty_pages(inode, io_ctl->pages, io_ctl->num_pages, 0, 1312 i_size_read(inode), &cached_state); 1313 if (ret) 1314 goto out_nospc; 1315 1316 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) 1317 up_write(&block_group->data_rwsem); 1318 /* 1319 * Release the pages and unlock the extent, we will flush 1320 * them out later 1321 */ 1322 io_ctl_drop_pages(io_ctl); 1323 1324 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0, 1325 i_size_read(inode) - 1, &cached_state, GFP_NOFS); 1326 1327 /* 1328 * at this point the pages are under IO and we're happy, 1329 * The caller is responsible for waiting on them and updating the 1330 * the cache and the inode 1331 */ 1332 io_ctl->entries = entries; 1333 io_ctl->bitmaps = bitmaps; 1334 1335 ret = btrfs_fdatawrite_range(inode, 0, (u64)-1); 1336 if (ret) 1337 goto out; 1338 1339 return 0; 1340 1341 out: 1342 io_ctl->inode = NULL; 1343 io_ctl_free(io_ctl); 1344 if (ret) { 1345 invalidate_inode_pages2(inode->i_mapping); 1346 BTRFS_I(inode)->generation = 0; 1347 } 1348 btrfs_update_inode(trans, root, inode); 1349 if (must_iput) 1350 iput(inode); 1351 return ret; 1352 1353 out_nospc_locked: 1354 cleanup_bitmap_list(&bitmap_list); 1355 spin_unlock(&ctl->tree_lock); 1356 mutex_unlock(&ctl->cache_writeout_mutex); 1357 1358 out_nospc: 1359 cleanup_write_cache_enospc(inode, io_ctl, &cached_state); 1360 1361 out_unlock: 1362 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) 1363 up_write(&block_group->data_rwsem); 1364 1365 goto out; 1366 } 1367 1368 int btrfs_write_out_cache(struct btrfs_fs_info *fs_info, 1369 struct btrfs_trans_handle *trans, 1370 struct btrfs_block_group_cache *block_group, 1371 struct btrfs_path *path) 1372 { 1373 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 1374 struct inode *inode; 1375 int ret = 0; 1376 1377 spin_lock(&block_group->lock); 1378 if (block_group->disk_cache_state < BTRFS_DC_SETUP) { 1379 spin_unlock(&block_group->lock); 1380 return 0; 1381 } 1382 spin_unlock(&block_group->lock); 1383 1384 inode = lookup_free_space_inode(fs_info, block_group, path); 1385 if (IS_ERR(inode)) 1386 return 0; 1387 1388 ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl, 1389 block_group, &block_group->io_ctl, trans); 1390 if (ret) { 1391 #ifdef DEBUG 1392 btrfs_err(fs_info, 1393 "failed to write free space cache for block group %llu", 1394 block_group->key.objectid); 1395 #endif 1396 spin_lock(&block_group->lock); 1397 block_group->disk_cache_state = BTRFS_DC_ERROR; 1398 spin_unlock(&block_group->lock); 1399 1400 block_group->io_ctl.inode = NULL; 1401 iput(inode); 1402 } 1403 1404 /* 1405 * if ret == 0 the caller is expected to call btrfs_wait_cache_io 1406 * to wait for IO and put the inode 1407 */ 1408 1409 return ret; 1410 } 1411 1412 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit, 1413 u64 offset) 1414 { 1415 ASSERT(offset >= bitmap_start); 1416 offset -= bitmap_start; 1417 return (unsigned long)(div_u64(offset, unit)); 1418 } 1419 1420 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit) 1421 { 1422 return (unsigned long)(div_u64(bytes, unit)); 1423 } 1424 1425 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl, 1426 u64 offset) 1427 { 1428 u64 bitmap_start; 1429 u64 bytes_per_bitmap; 1430 1431 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit; 1432 bitmap_start = offset - ctl->start; 1433 bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap); 1434 bitmap_start *= bytes_per_bitmap; 1435 bitmap_start += ctl->start; 1436 1437 return bitmap_start; 1438 } 1439 1440 static int tree_insert_offset(struct rb_root *root, u64 offset, 1441 struct rb_node *node, int bitmap) 1442 { 1443 struct rb_node **p = &root->rb_node; 1444 struct rb_node *parent = NULL; 1445 struct btrfs_free_space *info; 1446 1447 while (*p) { 1448 parent = *p; 1449 info = rb_entry(parent, struct btrfs_free_space, offset_index); 1450 1451 if (offset < info->offset) { 1452 p = &(*p)->rb_left; 1453 } else if (offset > info->offset) { 1454 p = &(*p)->rb_right; 1455 } else { 1456 /* 1457 * we could have a bitmap entry and an extent entry 1458 * share the same offset. If this is the case, we want 1459 * the extent entry to always be found first if we do a 1460 * linear search through the tree, since we want to have 1461 * the quickest allocation time, and allocating from an 1462 * extent is faster than allocating from a bitmap. So 1463 * if we're inserting a bitmap and we find an entry at 1464 * this offset, we want to go right, or after this entry 1465 * logically. If we are inserting an extent and we've 1466 * found a bitmap, we want to go left, or before 1467 * logically. 1468 */ 1469 if (bitmap) { 1470 if (info->bitmap) { 1471 WARN_ON_ONCE(1); 1472 return -EEXIST; 1473 } 1474 p = &(*p)->rb_right; 1475 } else { 1476 if (!info->bitmap) { 1477 WARN_ON_ONCE(1); 1478 return -EEXIST; 1479 } 1480 p = &(*p)->rb_left; 1481 } 1482 } 1483 } 1484 1485 rb_link_node(node, parent, p); 1486 rb_insert_color(node, root); 1487 1488 return 0; 1489 } 1490 1491 /* 1492 * searches the tree for the given offset. 1493 * 1494 * fuzzy - If this is set, then we are trying to make an allocation, and we just 1495 * want a section that has at least bytes size and comes at or after the given 1496 * offset. 1497 */ 1498 static struct btrfs_free_space * 1499 tree_search_offset(struct btrfs_free_space_ctl *ctl, 1500 u64 offset, int bitmap_only, int fuzzy) 1501 { 1502 struct rb_node *n = ctl->free_space_offset.rb_node; 1503 struct btrfs_free_space *entry, *prev = NULL; 1504 1505 /* find entry that is closest to the 'offset' */ 1506 while (1) { 1507 if (!n) { 1508 entry = NULL; 1509 break; 1510 } 1511 1512 entry = rb_entry(n, struct btrfs_free_space, offset_index); 1513 prev = entry; 1514 1515 if (offset < entry->offset) 1516 n = n->rb_left; 1517 else if (offset > entry->offset) 1518 n = n->rb_right; 1519 else 1520 break; 1521 } 1522 1523 if (bitmap_only) { 1524 if (!entry) 1525 return NULL; 1526 if (entry->bitmap) 1527 return entry; 1528 1529 /* 1530 * bitmap entry and extent entry may share same offset, 1531 * in that case, bitmap entry comes after extent entry. 1532 */ 1533 n = rb_next(n); 1534 if (!n) 1535 return NULL; 1536 entry = rb_entry(n, struct btrfs_free_space, offset_index); 1537 if (entry->offset != offset) 1538 return NULL; 1539 1540 WARN_ON(!entry->bitmap); 1541 return entry; 1542 } else if (entry) { 1543 if (entry->bitmap) { 1544 /* 1545 * if previous extent entry covers the offset, 1546 * we should return it instead of the bitmap entry 1547 */ 1548 n = rb_prev(&entry->offset_index); 1549 if (n) { 1550 prev = rb_entry(n, struct btrfs_free_space, 1551 offset_index); 1552 if (!prev->bitmap && 1553 prev->offset + prev->bytes > offset) 1554 entry = prev; 1555 } 1556 } 1557 return entry; 1558 } 1559 1560 if (!prev) 1561 return NULL; 1562 1563 /* find last entry before the 'offset' */ 1564 entry = prev; 1565 if (entry->offset > offset) { 1566 n = rb_prev(&entry->offset_index); 1567 if (n) { 1568 entry = rb_entry(n, struct btrfs_free_space, 1569 offset_index); 1570 ASSERT(entry->offset <= offset); 1571 } else { 1572 if (fuzzy) 1573 return entry; 1574 else 1575 return NULL; 1576 } 1577 } 1578 1579 if (entry->bitmap) { 1580 n = rb_prev(&entry->offset_index); 1581 if (n) { 1582 prev = rb_entry(n, struct btrfs_free_space, 1583 offset_index); 1584 if (!prev->bitmap && 1585 prev->offset + prev->bytes > offset) 1586 return prev; 1587 } 1588 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset) 1589 return entry; 1590 } else if (entry->offset + entry->bytes > offset) 1591 return entry; 1592 1593 if (!fuzzy) 1594 return NULL; 1595 1596 while (1) { 1597 if (entry->bitmap) { 1598 if (entry->offset + BITS_PER_BITMAP * 1599 ctl->unit > offset) 1600 break; 1601 } else { 1602 if (entry->offset + entry->bytes > offset) 1603 break; 1604 } 1605 1606 n = rb_next(&entry->offset_index); 1607 if (!n) 1608 return NULL; 1609 entry = rb_entry(n, struct btrfs_free_space, offset_index); 1610 } 1611 return entry; 1612 } 1613 1614 static inline void 1615 __unlink_free_space(struct btrfs_free_space_ctl *ctl, 1616 struct btrfs_free_space *info) 1617 { 1618 rb_erase(&info->offset_index, &ctl->free_space_offset); 1619 ctl->free_extents--; 1620 } 1621 1622 static void unlink_free_space(struct btrfs_free_space_ctl *ctl, 1623 struct btrfs_free_space *info) 1624 { 1625 __unlink_free_space(ctl, info); 1626 ctl->free_space -= info->bytes; 1627 } 1628 1629 static int link_free_space(struct btrfs_free_space_ctl *ctl, 1630 struct btrfs_free_space *info) 1631 { 1632 int ret = 0; 1633 1634 ASSERT(info->bytes || info->bitmap); 1635 ret = tree_insert_offset(&ctl->free_space_offset, info->offset, 1636 &info->offset_index, (info->bitmap != NULL)); 1637 if (ret) 1638 return ret; 1639 1640 ctl->free_space += info->bytes; 1641 ctl->free_extents++; 1642 return ret; 1643 } 1644 1645 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl) 1646 { 1647 struct btrfs_block_group_cache *block_group = ctl->private; 1648 u64 max_bytes; 1649 u64 bitmap_bytes; 1650 u64 extent_bytes; 1651 u64 size = block_group->key.offset; 1652 u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit; 1653 u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg); 1654 1655 max_bitmaps = max_t(u64, max_bitmaps, 1); 1656 1657 ASSERT(ctl->total_bitmaps <= max_bitmaps); 1658 1659 /* 1660 * The goal is to keep the total amount of memory used per 1gb of space 1661 * at or below 32k, so we need to adjust how much memory we allow to be 1662 * used by extent based free space tracking 1663 */ 1664 if (size < SZ_1G) 1665 max_bytes = MAX_CACHE_BYTES_PER_GIG; 1666 else 1667 max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G); 1668 1669 /* 1670 * we want to account for 1 more bitmap than what we have so we can make 1671 * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as 1672 * we add more bitmaps. 1673 */ 1674 bitmap_bytes = (ctl->total_bitmaps + 1) * ctl->unit; 1675 1676 if (bitmap_bytes >= max_bytes) { 1677 ctl->extents_thresh = 0; 1678 return; 1679 } 1680 1681 /* 1682 * we want the extent entry threshold to always be at most 1/2 the max 1683 * bytes we can have, or whatever is less than that. 1684 */ 1685 extent_bytes = max_bytes - bitmap_bytes; 1686 extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1); 1687 1688 ctl->extents_thresh = 1689 div_u64(extent_bytes, sizeof(struct btrfs_free_space)); 1690 } 1691 1692 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, 1693 struct btrfs_free_space *info, 1694 u64 offset, u64 bytes) 1695 { 1696 unsigned long start, count; 1697 1698 start = offset_to_bit(info->offset, ctl->unit, offset); 1699 count = bytes_to_bits(bytes, ctl->unit); 1700 ASSERT(start + count <= BITS_PER_BITMAP); 1701 1702 bitmap_clear(info->bitmap, start, count); 1703 1704 info->bytes -= bytes; 1705 } 1706 1707 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl, 1708 struct btrfs_free_space *info, u64 offset, 1709 u64 bytes) 1710 { 1711 __bitmap_clear_bits(ctl, info, offset, bytes); 1712 ctl->free_space -= bytes; 1713 } 1714 1715 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl, 1716 struct btrfs_free_space *info, u64 offset, 1717 u64 bytes) 1718 { 1719 unsigned long start, count; 1720 1721 start = offset_to_bit(info->offset, ctl->unit, offset); 1722 count = bytes_to_bits(bytes, ctl->unit); 1723 ASSERT(start + count <= BITS_PER_BITMAP); 1724 1725 bitmap_set(info->bitmap, start, count); 1726 1727 info->bytes += bytes; 1728 ctl->free_space += bytes; 1729 } 1730 1731 /* 1732 * If we can not find suitable extent, we will use bytes to record 1733 * the size of the max extent. 1734 */ 1735 static int search_bitmap(struct btrfs_free_space_ctl *ctl, 1736 struct btrfs_free_space *bitmap_info, u64 *offset, 1737 u64 *bytes, bool for_alloc) 1738 { 1739 unsigned long found_bits = 0; 1740 unsigned long max_bits = 0; 1741 unsigned long bits, i; 1742 unsigned long next_zero; 1743 unsigned long extent_bits; 1744 1745 /* 1746 * Skip searching the bitmap if we don't have a contiguous section that 1747 * is large enough for this allocation. 1748 */ 1749 if (for_alloc && 1750 bitmap_info->max_extent_size && 1751 bitmap_info->max_extent_size < *bytes) { 1752 *bytes = bitmap_info->max_extent_size; 1753 return -1; 1754 } 1755 1756 i = offset_to_bit(bitmap_info->offset, ctl->unit, 1757 max_t(u64, *offset, bitmap_info->offset)); 1758 bits = bytes_to_bits(*bytes, ctl->unit); 1759 1760 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) { 1761 if (for_alloc && bits == 1) { 1762 found_bits = 1; 1763 break; 1764 } 1765 next_zero = find_next_zero_bit(bitmap_info->bitmap, 1766 BITS_PER_BITMAP, i); 1767 extent_bits = next_zero - i; 1768 if (extent_bits >= bits) { 1769 found_bits = extent_bits; 1770 break; 1771 } else if (extent_bits > max_bits) { 1772 max_bits = extent_bits; 1773 } 1774 i = next_zero; 1775 } 1776 1777 if (found_bits) { 1778 *offset = (u64)(i * ctl->unit) + bitmap_info->offset; 1779 *bytes = (u64)(found_bits) * ctl->unit; 1780 return 0; 1781 } 1782 1783 *bytes = (u64)(max_bits) * ctl->unit; 1784 bitmap_info->max_extent_size = *bytes; 1785 return -1; 1786 } 1787 1788 /* Cache the size of the max extent in bytes */ 1789 static struct btrfs_free_space * 1790 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes, 1791 unsigned long align, u64 *max_extent_size) 1792 { 1793 struct btrfs_free_space *entry; 1794 struct rb_node *node; 1795 u64 tmp; 1796 u64 align_off; 1797 int ret; 1798 1799 if (!ctl->free_space_offset.rb_node) 1800 goto out; 1801 1802 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1); 1803 if (!entry) 1804 goto out; 1805 1806 for (node = &entry->offset_index; node; node = rb_next(node)) { 1807 entry = rb_entry(node, struct btrfs_free_space, offset_index); 1808 if (entry->bytes < *bytes) { 1809 if (entry->bytes > *max_extent_size) 1810 *max_extent_size = entry->bytes; 1811 continue; 1812 } 1813 1814 /* make sure the space returned is big enough 1815 * to match our requested alignment 1816 */ 1817 if (*bytes >= align) { 1818 tmp = entry->offset - ctl->start + align - 1; 1819 tmp = div64_u64(tmp, align); 1820 tmp = tmp * align + ctl->start; 1821 align_off = tmp - entry->offset; 1822 } else { 1823 align_off = 0; 1824 tmp = entry->offset; 1825 } 1826 1827 if (entry->bytes < *bytes + align_off) { 1828 if (entry->bytes > *max_extent_size) 1829 *max_extent_size = entry->bytes; 1830 continue; 1831 } 1832 1833 if (entry->bitmap) { 1834 u64 size = *bytes; 1835 1836 ret = search_bitmap(ctl, entry, &tmp, &size, true); 1837 if (!ret) { 1838 *offset = tmp; 1839 *bytes = size; 1840 return entry; 1841 } else if (size > *max_extent_size) { 1842 *max_extent_size = size; 1843 } 1844 continue; 1845 } 1846 1847 *offset = tmp; 1848 *bytes = entry->bytes - align_off; 1849 return entry; 1850 } 1851 out: 1852 return NULL; 1853 } 1854 1855 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl, 1856 struct btrfs_free_space *info, u64 offset) 1857 { 1858 info->offset = offset_to_bitmap(ctl, offset); 1859 info->bytes = 0; 1860 INIT_LIST_HEAD(&info->list); 1861 link_free_space(ctl, info); 1862 ctl->total_bitmaps++; 1863 1864 ctl->op->recalc_thresholds(ctl); 1865 } 1866 1867 static void free_bitmap(struct btrfs_free_space_ctl *ctl, 1868 struct btrfs_free_space *bitmap_info) 1869 { 1870 unlink_free_space(ctl, bitmap_info); 1871 kfree(bitmap_info->bitmap); 1872 kmem_cache_free(btrfs_free_space_cachep, bitmap_info); 1873 ctl->total_bitmaps--; 1874 ctl->op->recalc_thresholds(ctl); 1875 } 1876 1877 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl, 1878 struct btrfs_free_space *bitmap_info, 1879 u64 *offset, u64 *bytes) 1880 { 1881 u64 end; 1882 u64 search_start, search_bytes; 1883 int ret; 1884 1885 again: 1886 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1; 1887 1888 /* 1889 * We need to search for bits in this bitmap. We could only cover some 1890 * of the extent in this bitmap thanks to how we add space, so we need 1891 * to search for as much as it as we can and clear that amount, and then 1892 * go searching for the next bit. 1893 */ 1894 search_start = *offset; 1895 search_bytes = ctl->unit; 1896 search_bytes = min(search_bytes, end - search_start + 1); 1897 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes, 1898 false); 1899 if (ret < 0 || search_start != *offset) 1900 return -EINVAL; 1901 1902 /* We may have found more bits than what we need */ 1903 search_bytes = min(search_bytes, *bytes); 1904 1905 /* Cannot clear past the end of the bitmap */ 1906 search_bytes = min(search_bytes, end - search_start + 1); 1907 1908 bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes); 1909 *offset += search_bytes; 1910 *bytes -= search_bytes; 1911 1912 if (*bytes) { 1913 struct rb_node *next = rb_next(&bitmap_info->offset_index); 1914 if (!bitmap_info->bytes) 1915 free_bitmap(ctl, bitmap_info); 1916 1917 /* 1918 * no entry after this bitmap, but we still have bytes to 1919 * remove, so something has gone wrong. 1920 */ 1921 if (!next) 1922 return -EINVAL; 1923 1924 bitmap_info = rb_entry(next, struct btrfs_free_space, 1925 offset_index); 1926 1927 /* 1928 * if the next entry isn't a bitmap we need to return to let the 1929 * extent stuff do its work. 1930 */ 1931 if (!bitmap_info->bitmap) 1932 return -EAGAIN; 1933 1934 /* 1935 * Ok the next item is a bitmap, but it may not actually hold 1936 * the information for the rest of this free space stuff, so 1937 * look for it, and if we don't find it return so we can try 1938 * everything over again. 1939 */ 1940 search_start = *offset; 1941 search_bytes = ctl->unit; 1942 ret = search_bitmap(ctl, bitmap_info, &search_start, 1943 &search_bytes, false); 1944 if (ret < 0 || search_start != *offset) 1945 return -EAGAIN; 1946 1947 goto again; 1948 } else if (!bitmap_info->bytes) 1949 free_bitmap(ctl, bitmap_info); 1950 1951 return 0; 1952 } 1953 1954 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl, 1955 struct btrfs_free_space *info, u64 offset, 1956 u64 bytes) 1957 { 1958 u64 bytes_to_set = 0; 1959 u64 end; 1960 1961 end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit); 1962 1963 bytes_to_set = min(end - offset, bytes); 1964 1965 bitmap_set_bits(ctl, info, offset, bytes_to_set); 1966 1967 /* 1968 * We set some bytes, we have no idea what the max extent size is 1969 * anymore. 1970 */ 1971 info->max_extent_size = 0; 1972 1973 return bytes_to_set; 1974 1975 } 1976 1977 static bool use_bitmap(struct btrfs_free_space_ctl *ctl, 1978 struct btrfs_free_space *info) 1979 { 1980 struct btrfs_block_group_cache *block_group = ctl->private; 1981 struct btrfs_fs_info *fs_info = block_group->fs_info; 1982 bool forced = false; 1983 1984 #ifdef CONFIG_BTRFS_DEBUG 1985 if (btrfs_should_fragment_free_space(block_group)) 1986 forced = true; 1987 #endif 1988 1989 /* 1990 * If we are below the extents threshold then we can add this as an 1991 * extent, and don't have to deal with the bitmap 1992 */ 1993 if (!forced && ctl->free_extents < ctl->extents_thresh) { 1994 /* 1995 * If this block group has some small extents we don't want to 1996 * use up all of our free slots in the cache with them, we want 1997 * to reserve them to larger extents, however if we have plenty 1998 * of cache left then go ahead an dadd them, no sense in adding 1999 * the overhead of a bitmap if we don't have to. 2000 */ 2001 if (info->bytes <= fs_info->sectorsize * 4) { 2002 if (ctl->free_extents * 2 <= ctl->extents_thresh) 2003 return false; 2004 } else { 2005 return false; 2006 } 2007 } 2008 2009 /* 2010 * The original block groups from mkfs can be really small, like 8 2011 * megabytes, so don't bother with a bitmap for those entries. However 2012 * some block groups can be smaller than what a bitmap would cover but 2013 * are still large enough that they could overflow the 32k memory limit, 2014 * so allow those block groups to still be allowed to have a bitmap 2015 * entry. 2016 */ 2017 if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset) 2018 return false; 2019 2020 return true; 2021 } 2022 2023 static const struct btrfs_free_space_op free_space_op = { 2024 .recalc_thresholds = recalculate_thresholds, 2025 .use_bitmap = use_bitmap, 2026 }; 2027 2028 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl, 2029 struct btrfs_free_space *info) 2030 { 2031 struct btrfs_free_space *bitmap_info; 2032 struct btrfs_block_group_cache *block_group = NULL; 2033 int added = 0; 2034 u64 bytes, offset, bytes_added; 2035 int ret; 2036 2037 bytes = info->bytes; 2038 offset = info->offset; 2039 2040 if (!ctl->op->use_bitmap(ctl, info)) 2041 return 0; 2042 2043 if (ctl->op == &free_space_op) 2044 block_group = ctl->private; 2045 again: 2046 /* 2047 * Since we link bitmaps right into the cluster we need to see if we 2048 * have a cluster here, and if so and it has our bitmap we need to add 2049 * the free space to that bitmap. 2050 */ 2051 if (block_group && !list_empty(&block_group->cluster_list)) { 2052 struct btrfs_free_cluster *cluster; 2053 struct rb_node *node; 2054 struct btrfs_free_space *entry; 2055 2056 cluster = list_entry(block_group->cluster_list.next, 2057 struct btrfs_free_cluster, 2058 block_group_list); 2059 spin_lock(&cluster->lock); 2060 node = rb_first(&cluster->root); 2061 if (!node) { 2062 spin_unlock(&cluster->lock); 2063 goto no_cluster_bitmap; 2064 } 2065 2066 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2067 if (!entry->bitmap) { 2068 spin_unlock(&cluster->lock); 2069 goto no_cluster_bitmap; 2070 } 2071 2072 if (entry->offset == offset_to_bitmap(ctl, offset)) { 2073 bytes_added = add_bytes_to_bitmap(ctl, entry, 2074 offset, bytes); 2075 bytes -= bytes_added; 2076 offset += bytes_added; 2077 } 2078 spin_unlock(&cluster->lock); 2079 if (!bytes) { 2080 ret = 1; 2081 goto out; 2082 } 2083 } 2084 2085 no_cluster_bitmap: 2086 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 2087 1, 0); 2088 if (!bitmap_info) { 2089 ASSERT(added == 0); 2090 goto new_bitmap; 2091 } 2092 2093 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes); 2094 bytes -= bytes_added; 2095 offset += bytes_added; 2096 added = 0; 2097 2098 if (!bytes) { 2099 ret = 1; 2100 goto out; 2101 } else 2102 goto again; 2103 2104 new_bitmap: 2105 if (info && info->bitmap) { 2106 add_new_bitmap(ctl, info, offset); 2107 added = 1; 2108 info = NULL; 2109 goto again; 2110 } else { 2111 spin_unlock(&ctl->tree_lock); 2112 2113 /* no pre-allocated info, allocate a new one */ 2114 if (!info) { 2115 info = kmem_cache_zalloc(btrfs_free_space_cachep, 2116 GFP_NOFS); 2117 if (!info) { 2118 spin_lock(&ctl->tree_lock); 2119 ret = -ENOMEM; 2120 goto out; 2121 } 2122 } 2123 2124 /* allocate the bitmap */ 2125 info->bitmap = kzalloc(PAGE_SIZE, GFP_NOFS); 2126 spin_lock(&ctl->tree_lock); 2127 if (!info->bitmap) { 2128 ret = -ENOMEM; 2129 goto out; 2130 } 2131 goto again; 2132 } 2133 2134 out: 2135 if (info) { 2136 if (info->bitmap) 2137 kfree(info->bitmap); 2138 kmem_cache_free(btrfs_free_space_cachep, info); 2139 } 2140 2141 return ret; 2142 } 2143 2144 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl, 2145 struct btrfs_free_space *info, bool update_stat) 2146 { 2147 struct btrfs_free_space *left_info; 2148 struct btrfs_free_space *right_info; 2149 bool merged = false; 2150 u64 offset = info->offset; 2151 u64 bytes = info->bytes; 2152 2153 /* 2154 * first we want to see if there is free space adjacent to the range we 2155 * are adding, if there is remove that struct and add a new one to 2156 * cover the entire range 2157 */ 2158 right_info = tree_search_offset(ctl, offset + bytes, 0, 0); 2159 if (right_info && rb_prev(&right_info->offset_index)) 2160 left_info = rb_entry(rb_prev(&right_info->offset_index), 2161 struct btrfs_free_space, offset_index); 2162 else 2163 left_info = tree_search_offset(ctl, offset - 1, 0, 0); 2164 2165 if (right_info && !right_info->bitmap) { 2166 if (update_stat) 2167 unlink_free_space(ctl, right_info); 2168 else 2169 __unlink_free_space(ctl, right_info); 2170 info->bytes += right_info->bytes; 2171 kmem_cache_free(btrfs_free_space_cachep, right_info); 2172 merged = true; 2173 } 2174 2175 if (left_info && !left_info->bitmap && 2176 left_info->offset + left_info->bytes == offset) { 2177 if (update_stat) 2178 unlink_free_space(ctl, left_info); 2179 else 2180 __unlink_free_space(ctl, left_info); 2181 info->offset = left_info->offset; 2182 info->bytes += left_info->bytes; 2183 kmem_cache_free(btrfs_free_space_cachep, left_info); 2184 merged = true; 2185 } 2186 2187 return merged; 2188 } 2189 2190 static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl, 2191 struct btrfs_free_space *info, 2192 bool update_stat) 2193 { 2194 struct btrfs_free_space *bitmap; 2195 unsigned long i; 2196 unsigned long j; 2197 const u64 end = info->offset + info->bytes; 2198 const u64 bitmap_offset = offset_to_bitmap(ctl, end); 2199 u64 bytes; 2200 2201 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0); 2202 if (!bitmap) 2203 return false; 2204 2205 i = offset_to_bit(bitmap->offset, ctl->unit, end); 2206 j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i); 2207 if (j == i) 2208 return false; 2209 bytes = (j - i) * ctl->unit; 2210 info->bytes += bytes; 2211 2212 if (update_stat) 2213 bitmap_clear_bits(ctl, bitmap, end, bytes); 2214 else 2215 __bitmap_clear_bits(ctl, bitmap, end, bytes); 2216 2217 if (!bitmap->bytes) 2218 free_bitmap(ctl, bitmap); 2219 2220 return true; 2221 } 2222 2223 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl, 2224 struct btrfs_free_space *info, 2225 bool update_stat) 2226 { 2227 struct btrfs_free_space *bitmap; 2228 u64 bitmap_offset; 2229 unsigned long i; 2230 unsigned long j; 2231 unsigned long prev_j; 2232 u64 bytes; 2233 2234 bitmap_offset = offset_to_bitmap(ctl, info->offset); 2235 /* If we're on a boundary, try the previous logical bitmap. */ 2236 if (bitmap_offset == info->offset) { 2237 if (info->offset == 0) 2238 return false; 2239 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1); 2240 } 2241 2242 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0); 2243 if (!bitmap) 2244 return false; 2245 2246 i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1; 2247 j = 0; 2248 prev_j = (unsigned long)-1; 2249 for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) { 2250 if (j > i) 2251 break; 2252 prev_j = j; 2253 } 2254 if (prev_j == i) 2255 return false; 2256 2257 if (prev_j == (unsigned long)-1) 2258 bytes = (i + 1) * ctl->unit; 2259 else 2260 bytes = (i - prev_j) * ctl->unit; 2261 2262 info->offset -= bytes; 2263 info->bytes += bytes; 2264 2265 if (update_stat) 2266 bitmap_clear_bits(ctl, bitmap, info->offset, bytes); 2267 else 2268 __bitmap_clear_bits(ctl, bitmap, info->offset, bytes); 2269 2270 if (!bitmap->bytes) 2271 free_bitmap(ctl, bitmap); 2272 2273 return true; 2274 } 2275 2276 /* 2277 * We prefer always to allocate from extent entries, both for clustered and 2278 * non-clustered allocation requests. So when attempting to add a new extent 2279 * entry, try to see if there's adjacent free space in bitmap entries, and if 2280 * there is, migrate that space from the bitmaps to the extent. 2281 * Like this we get better chances of satisfying space allocation requests 2282 * because we attempt to satisfy them based on a single cache entry, and never 2283 * on 2 or more entries - even if the entries represent a contiguous free space 2284 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry 2285 * ends). 2286 */ 2287 static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl, 2288 struct btrfs_free_space *info, 2289 bool update_stat) 2290 { 2291 /* 2292 * Only work with disconnected entries, as we can change their offset, 2293 * and must be extent entries. 2294 */ 2295 ASSERT(!info->bitmap); 2296 ASSERT(RB_EMPTY_NODE(&info->offset_index)); 2297 2298 if (ctl->total_bitmaps > 0) { 2299 bool stole_end; 2300 bool stole_front = false; 2301 2302 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat); 2303 if (ctl->total_bitmaps > 0) 2304 stole_front = steal_from_bitmap_to_front(ctl, info, 2305 update_stat); 2306 2307 if (stole_end || stole_front) 2308 try_merge_free_space(ctl, info, update_stat); 2309 } 2310 } 2311 2312 int __btrfs_add_free_space(struct btrfs_fs_info *fs_info, 2313 struct btrfs_free_space_ctl *ctl, 2314 u64 offset, u64 bytes) 2315 { 2316 struct btrfs_free_space *info; 2317 int ret = 0; 2318 2319 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); 2320 if (!info) 2321 return -ENOMEM; 2322 2323 info->offset = offset; 2324 info->bytes = bytes; 2325 RB_CLEAR_NODE(&info->offset_index); 2326 2327 spin_lock(&ctl->tree_lock); 2328 2329 if (try_merge_free_space(ctl, info, true)) 2330 goto link; 2331 2332 /* 2333 * There was no extent directly to the left or right of this new 2334 * extent then we know we're going to have to allocate a new extent, so 2335 * before we do that see if we need to drop this into a bitmap 2336 */ 2337 ret = insert_into_bitmap(ctl, info); 2338 if (ret < 0) { 2339 goto out; 2340 } else if (ret) { 2341 ret = 0; 2342 goto out; 2343 } 2344 link: 2345 /* 2346 * Only steal free space from adjacent bitmaps if we're sure we're not 2347 * going to add the new free space to existing bitmap entries - because 2348 * that would mean unnecessary work that would be reverted. Therefore 2349 * attempt to steal space from bitmaps if we're adding an extent entry. 2350 */ 2351 steal_from_bitmap(ctl, info, true); 2352 2353 ret = link_free_space(ctl, info); 2354 if (ret) 2355 kmem_cache_free(btrfs_free_space_cachep, info); 2356 out: 2357 spin_unlock(&ctl->tree_lock); 2358 2359 if (ret) { 2360 btrfs_crit(fs_info, "unable to add free space :%d", ret); 2361 ASSERT(ret != -EEXIST); 2362 } 2363 2364 return ret; 2365 } 2366 2367 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group, 2368 u64 offset, u64 bytes) 2369 { 2370 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2371 struct btrfs_free_space *info; 2372 int ret; 2373 bool re_search = false; 2374 2375 spin_lock(&ctl->tree_lock); 2376 2377 again: 2378 ret = 0; 2379 if (!bytes) 2380 goto out_lock; 2381 2382 info = tree_search_offset(ctl, offset, 0, 0); 2383 if (!info) { 2384 /* 2385 * oops didn't find an extent that matched the space we wanted 2386 * to remove, look for a bitmap instead 2387 */ 2388 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 2389 1, 0); 2390 if (!info) { 2391 /* 2392 * If we found a partial bit of our free space in a 2393 * bitmap but then couldn't find the other part this may 2394 * be a problem, so WARN about it. 2395 */ 2396 WARN_ON(re_search); 2397 goto out_lock; 2398 } 2399 } 2400 2401 re_search = false; 2402 if (!info->bitmap) { 2403 unlink_free_space(ctl, info); 2404 if (offset == info->offset) { 2405 u64 to_free = min(bytes, info->bytes); 2406 2407 info->bytes -= to_free; 2408 info->offset += to_free; 2409 if (info->bytes) { 2410 ret = link_free_space(ctl, info); 2411 WARN_ON(ret); 2412 } else { 2413 kmem_cache_free(btrfs_free_space_cachep, info); 2414 } 2415 2416 offset += to_free; 2417 bytes -= to_free; 2418 goto again; 2419 } else { 2420 u64 old_end = info->bytes + info->offset; 2421 2422 info->bytes = offset - info->offset; 2423 ret = link_free_space(ctl, info); 2424 WARN_ON(ret); 2425 if (ret) 2426 goto out_lock; 2427 2428 /* Not enough bytes in this entry to satisfy us */ 2429 if (old_end < offset + bytes) { 2430 bytes -= old_end - offset; 2431 offset = old_end; 2432 goto again; 2433 } else if (old_end == offset + bytes) { 2434 /* all done */ 2435 goto out_lock; 2436 } 2437 spin_unlock(&ctl->tree_lock); 2438 2439 ret = btrfs_add_free_space(block_group, offset + bytes, 2440 old_end - (offset + bytes)); 2441 WARN_ON(ret); 2442 goto out; 2443 } 2444 } 2445 2446 ret = remove_from_bitmap(ctl, info, &offset, &bytes); 2447 if (ret == -EAGAIN) { 2448 re_search = true; 2449 goto again; 2450 } 2451 out_lock: 2452 spin_unlock(&ctl->tree_lock); 2453 out: 2454 return ret; 2455 } 2456 2457 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group, 2458 u64 bytes) 2459 { 2460 struct btrfs_fs_info *fs_info = block_group->fs_info; 2461 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2462 struct btrfs_free_space *info; 2463 struct rb_node *n; 2464 int count = 0; 2465 2466 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) { 2467 info = rb_entry(n, struct btrfs_free_space, offset_index); 2468 if (info->bytes >= bytes && !block_group->ro) 2469 count++; 2470 btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s", 2471 info->offset, info->bytes, 2472 (info->bitmap) ? "yes" : "no"); 2473 } 2474 btrfs_info(fs_info, "block group has cluster?: %s", 2475 list_empty(&block_group->cluster_list) ? "no" : "yes"); 2476 btrfs_info(fs_info, 2477 "%d blocks of free space at or bigger than bytes is", count); 2478 } 2479 2480 void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group) 2481 { 2482 struct btrfs_fs_info *fs_info = block_group->fs_info; 2483 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2484 2485 spin_lock_init(&ctl->tree_lock); 2486 ctl->unit = fs_info->sectorsize; 2487 ctl->start = block_group->key.objectid; 2488 ctl->private = block_group; 2489 ctl->op = &free_space_op; 2490 INIT_LIST_HEAD(&ctl->trimming_ranges); 2491 mutex_init(&ctl->cache_writeout_mutex); 2492 2493 /* 2494 * we only want to have 32k of ram per block group for keeping 2495 * track of free space, and if we pass 1/2 of that we want to 2496 * start converting things over to using bitmaps 2497 */ 2498 ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space); 2499 } 2500 2501 /* 2502 * for a given cluster, put all of its extents back into the free 2503 * space cache. If the block group passed doesn't match the block group 2504 * pointed to by the cluster, someone else raced in and freed the 2505 * cluster already. In that case, we just return without changing anything 2506 */ 2507 static int 2508 __btrfs_return_cluster_to_free_space( 2509 struct btrfs_block_group_cache *block_group, 2510 struct btrfs_free_cluster *cluster) 2511 { 2512 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2513 struct btrfs_free_space *entry; 2514 struct rb_node *node; 2515 2516 spin_lock(&cluster->lock); 2517 if (cluster->block_group != block_group) 2518 goto out; 2519 2520 cluster->block_group = NULL; 2521 cluster->window_start = 0; 2522 list_del_init(&cluster->block_group_list); 2523 2524 node = rb_first(&cluster->root); 2525 while (node) { 2526 bool bitmap; 2527 2528 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2529 node = rb_next(&entry->offset_index); 2530 rb_erase(&entry->offset_index, &cluster->root); 2531 RB_CLEAR_NODE(&entry->offset_index); 2532 2533 bitmap = (entry->bitmap != NULL); 2534 if (!bitmap) { 2535 try_merge_free_space(ctl, entry, false); 2536 steal_from_bitmap(ctl, entry, false); 2537 } 2538 tree_insert_offset(&ctl->free_space_offset, 2539 entry->offset, &entry->offset_index, bitmap); 2540 } 2541 cluster->root = RB_ROOT; 2542 2543 out: 2544 spin_unlock(&cluster->lock); 2545 btrfs_put_block_group(block_group); 2546 return 0; 2547 } 2548 2549 static void __btrfs_remove_free_space_cache_locked( 2550 struct btrfs_free_space_ctl *ctl) 2551 { 2552 struct btrfs_free_space *info; 2553 struct rb_node *node; 2554 2555 while ((node = rb_last(&ctl->free_space_offset)) != NULL) { 2556 info = rb_entry(node, struct btrfs_free_space, offset_index); 2557 if (!info->bitmap) { 2558 unlink_free_space(ctl, info); 2559 kmem_cache_free(btrfs_free_space_cachep, info); 2560 } else { 2561 free_bitmap(ctl, info); 2562 } 2563 2564 cond_resched_lock(&ctl->tree_lock); 2565 } 2566 } 2567 2568 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl) 2569 { 2570 spin_lock(&ctl->tree_lock); 2571 __btrfs_remove_free_space_cache_locked(ctl); 2572 spin_unlock(&ctl->tree_lock); 2573 } 2574 2575 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) 2576 { 2577 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2578 struct btrfs_free_cluster *cluster; 2579 struct list_head *head; 2580 2581 spin_lock(&ctl->tree_lock); 2582 while ((head = block_group->cluster_list.next) != 2583 &block_group->cluster_list) { 2584 cluster = list_entry(head, struct btrfs_free_cluster, 2585 block_group_list); 2586 2587 WARN_ON(cluster->block_group != block_group); 2588 __btrfs_return_cluster_to_free_space(block_group, cluster); 2589 2590 cond_resched_lock(&ctl->tree_lock); 2591 } 2592 __btrfs_remove_free_space_cache_locked(ctl); 2593 spin_unlock(&ctl->tree_lock); 2594 2595 } 2596 2597 u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, 2598 u64 offset, u64 bytes, u64 empty_size, 2599 u64 *max_extent_size) 2600 { 2601 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2602 struct btrfs_free_space *entry = NULL; 2603 u64 bytes_search = bytes + empty_size; 2604 u64 ret = 0; 2605 u64 align_gap = 0; 2606 u64 align_gap_len = 0; 2607 2608 spin_lock(&ctl->tree_lock); 2609 entry = find_free_space(ctl, &offset, &bytes_search, 2610 block_group->full_stripe_len, max_extent_size); 2611 if (!entry) 2612 goto out; 2613 2614 ret = offset; 2615 if (entry->bitmap) { 2616 bitmap_clear_bits(ctl, entry, offset, bytes); 2617 if (!entry->bytes) 2618 free_bitmap(ctl, entry); 2619 } else { 2620 unlink_free_space(ctl, entry); 2621 align_gap_len = offset - entry->offset; 2622 align_gap = entry->offset; 2623 2624 entry->offset = offset + bytes; 2625 WARN_ON(entry->bytes < bytes + align_gap_len); 2626 2627 entry->bytes -= bytes + align_gap_len; 2628 if (!entry->bytes) 2629 kmem_cache_free(btrfs_free_space_cachep, entry); 2630 else 2631 link_free_space(ctl, entry); 2632 } 2633 out: 2634 spin_unlock(&ctl->tree_lock); 2635 2636 if (align_gap_len) 2637 __btrfs_add_free_space(block_group->fs_info, ctl, 2638 align_gap, align_gap_len); 2639 return ret; 2640 } 2641 2642 /* 2643 * given a cluster, put all of its extents back into the free space 2644 * cache. If a block group is passed, this function will only free 2645 * a cluster that belongs to the passed block group. 2646 * 2647 * Otherwise, it'll get a reference on the block group pointed to by the 2648 * cluster and remove the cluster from it. 2649 */ 2650 int btrfs_return_cluster_to_free_space( 2651 struct btrfs_block_group_cache *block_group, 2652 struct btrfs_free_cluster *cluster) 2653 { 2654 struct btrfs_free_space_ctl *ctl; 2655 int ret; 2656 2657 /* first, get a safe pointer to the block group */ 2658 spin_lock(&cluster->lock); 2659 if (!block_group) { 2660 block_group = cluster->block_group; 2661 if (!block_group) { 2662 spin_unlock(&cluster->lock); 2663 return 0; 2664 } 2665 } else if (cluster->block_group != block_group) { 2666 /* someone else has already freed it don't redo their work */ 2667 spin_unlock(&cluster->lock); 2668 return 0; 2669 } 2670 atomic_inc(&block_group->count); 2671 spin_unlock(&cluster->lock); 2672 2673 ctl = block_group->free_space_ctl; 2674 2675 /* now return any extents the cluster had on it */ 2676 spin_lock(&ctl->tree_lock); 2677 ret = __btrfs_return_cluster_to_free_space(block_group, cluster); 2678 spin_unlock(&ctl->tree_lock); 2679 2680 /* finally drop our ref */ 2681 btrfs_put_block_group(block_group); 2682 return ret; 2683 } 2684 2685 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group, 2686 struct btrfs_free_cluster *cluster, 2687 struct btrfs_free_space *entry, 2688 u64 bytes, u64 min_start, 2689 u64 *max_extent_size) 2690 { 2691 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2692 int err; 2693 u64 search_start = cluster->window_start; 2694 u64 search_bytes = bytes; 2695 u64 ret = 0; 2696 2697 search_start = min_start; 2698 search_bytes = bytes; 2699 2700 err = search_bitmap(ctl, entry, &search_start, &search_bytes, true); 2701 if (err) { 2702 if (search_bytes > *max_extent_size) 2703 *max_extent_size = search_bytes; 2704 return 0; 2705 } 2706 2707 ret = search_start; 2708 __bitmap_clear_bits(ctl, entry, ret, bytes); 2709 2710 return ret; 2711 } 2712 2713 /* 2714 * given a cluster, try to allocate 'bytes' from it, returns 0 2715 * if it couldn't find anything suitably large, or a logical disk offset 2716 * if things worked out 2717 */ 2718 u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, 2719 struct btrfs_free_cluster *cluster, u64 bytes, 2720 u64 min_start, u64 *max_extent_size) 2721 { 2722 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2723 struct btrfs_free_space *entry = NULL; 2724 struct rb_node *node; 2725 u64 ret = 0; 2726 2727 spin_lock(&cluster->lock); 2728 if (bytes > cluster->max_size) 2729 goto out; 2730 2731 if (cluster->block_group != block_group) 2732 goto out; 2733 2734 node = rb_first(&cluster->root); 2735 if (!node) 2736 goto out; 2737 2738 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2739 while (1) { 2740 if (entry->bytes < bytes && entry->bytes > *max_extent_size) 2741 *max_extent_size = entry->bytes; 2742 2743 if (entry->bytes < bytes || 2744 (!entry->bitmap && entry->offset < min_start)) { 2745 node = rb_next(&entry->offset_index); 2746 if (!node) 2747 break; 2748 entry = rb_entry(node, struct btrfs_free_space, 2749 offset_index); 2750 continue; 2751 } 2752 2753 if (entry->bitmap) { 2754 ret = btrfs_alloc_from_bitmap(block_group, 2755 cluster, entry, bytes, 2756 cluster->window_start, 2757 max_extent_size); 2758 if (ret == 0) { 2759 node = rb_next(&entry->offset_index); 2760 if (!node) 2761 break; 2762 entry = rb_entry(node, struct btrfs_free_space, 2763 offset_index); 2764 continue; 2765 } 2766 cluster->window_start += bytes; 2767 } else { 2768 ret = entry->offset; 2769 2770 entry->offset += bytes; 2771 entry->bytes -= bytes; 2772 } 2773 2774 if (entry->bytes == 0) 2775 rb_erase(&entry->offset_index, &cluster->root); 2776 break; 2777 } 2778 out: 2779 spin_unlock(&cluster->lock); 2780 2781 if (!ret) 2782 return 0; 2783 2784 spin_lock(&ctl->tree_lock); 2785 2786 ctl->free_space -= bytes; 2787 if (entry->bytes == 0) { 2788 ctl->free_extents--; 2789 if (entry->bitmap) { 2790 kfree(entry->bitmap); 2791 ctl->total_bitmaps--; 2792 ctl->op->recalc_thresholds(ctl); 2793 } 2794 kmem_cache_free(btrfs_free_space_cachep, entry); 2795 } 2796 2797 spin_unlock(&ctl->tree_lock); 2798 2799 return ret; 2800 } 2801 2802 static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group, 2803 struct btrfs_free_space *entry, 2804 struct btrfs_free_cluster *cluster, 2805 u64 offset, u64 bytes, 2806 u64 cont1_bytes, u64 min_bytes) 2807 { 2808 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2809 unsigned long next_zero; 2810 unsigned long i; 2811 unsigned long want_bits; 2812 unsigned long min_bits; 2813 unsigned long found_bits; 2814 unsigned long max_bits = 0; 2815 unsigned long start = 0; 2816 unsigned long total_found = 0; 2817 int ret; 2818 2819 i = offset_to_bit(entry->offset, ctl->unit, 2820 max_t(u64, offset, entry->offset)); 2821 want_bits = bytes_to_bits(bytes, ctl->unit); 2822 min_bits = bytes_to_bits(min_bytes, ctl->unit); 2823 2824 /* 2825 * Don't bother looking for a cluster in this bitmap if it's heavily 2826 * fragmented. 2827 */ 2828 if (entry->max_extent_size && 2829 entry->max_extent_size < cont1_bytes) 2830 return -ENOSPC; 2831 again: 2832 found_bits = 0; 2833 for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) { 2834 next_zero = find_next_zero_bit(entry->bitmap, 2835 BITS_PER_BITMAP, i); 2836 if (next_zero - i >= min_bits) { 2837 found_bits = next_zero - i; 2838 if (found_bits > max_bits) 2839 max_bits = found_bits; 2840 break; 2841 } 2842 if (next_zero - i > max_bits) 2843 max_bits = next_zero - i; 2844 i = next_zero; 2845 } 2846 2847 if (!found_bits) { 2848 entry->max_extent_size = (u64)max_bits * ctl->unit; 2849 return -ENOSPC; 2850 } 2851 2852 if (!total_found) { 2853 start = i; 2854 cluster->max_size = 0; 2855 } 2856 2857 total_found += found_bits; 2858 2859 if (cluster->max_size < found_bits * ctl->unit) 2860 cluster->max_size = found_bits * ctl->unit; 2861 2862 if (total_found < want_bits || cluster->max_size < cont1_bytes) { 2863 i = next_zero + 1; 2864 goto again; 2865 } 2866 2867 cluster->window_start = start * ctl->unit + entry->offset; 2868 rb_erase(&entry->offset_index, &ctl->free_space_offset); 2869 ret = tree_insert_offset(&cluster->root, entry->offset, 2870 &entry->offset_index, 1); 2871 ASSERT(!ret); /* -EEXIST; Logic error */ 2872 2873 trace_btrfs_setup_cluster(block_group, cluster, 2874 total_found * ctl->unit, 1); 2875 return 0; 2876 } 2877 2878 /* 2879 * This searches the block group for just extents to fill the cluster with. 2880 * Try to find a cluster with at least bytes total bytes, at least one 2881 * extent of cont1_bytes, and other clusters of at least min_bytes. 2882 */ 2883 static noinline int 2884 setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, 2885 struct btrfs_free_cluster *cluster, 2886 struct list_head *bitmaps, u64 offset, u64 bytes, 2887 u64 cont1_bytes, u64 min_bytes) 2888 { 2889 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2890 struct btrfs_free_space *first = NULL; 2891 struct btrfs_free_space *entry = NULL; 2892 struct btrfs_free_space *last; 2893 struct rb_node *node; 2894 u64 window_free; 2895 u64 max_extent; 2896 u64 total_size = 0; 2897 2898 entry = tree_search_offset(ctl, offset, 0, 1); 2899 if (!entry) 2900 return -ENOSPC; 2901 2902 /* 2903 * We don't want bitmaps, so just move along until we find a normal 2904 * extent entry. 2905 */ 2906 while (entry->bitmap || entry->bytes < min_bytes) { 2907 if (entry->bitmap && list_empty(&entry->list)) 2908 list_add_tail(&entry->list, bitmaps); 2909 node = rb_next(&entry->offset_index); 2910 if (!node) 2911 return -ENOSPC; 2912 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2913 } 2914 2915 window_free = entry->bytes; 2916 max_extent = entry->bytes; 2917 first = entry; 2918 last = entry; 2919 2920 for (node = rb_next(&entry->offset_index); node; 2921 node = rb_next(&entry->offset_index)) { 2922 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2923 2924 if (entry->bitmap) { 2925 if (list_empty(&entry->list)) 2926 list_add_tail(&entry->list, bitmaps); 2927 continue; 2928 } 2929 2930 if (entry->bytes < min_bytes) 2931 continue; 2932 2933 last = entry; 2934 window_free += entry->bytes; 2935 if (entry->bytes > max_extent) 2936 max_extent = entry->bytes; 2937 } 2938 2939 if (window_free < bytes || max_extent < cont1_bytes) 2940 return -ENOSPC; 2941 2942 cluster->window_start = first->offset; 2943 2944 node = &first->offset_index; 2945 2946 /* 2947 * now we've found our entries, pull them out of the free space 2948 * cache and put them into the cluster rbtree 2949 */ 2950 do { 2951 int ret; 2952 2953 entry = rb_entry(node, struct btrfs_free_space, offset_index); 2954 node = rb_next(&entry->offset_index); 2955 if (entry->bitmap || entry->bytes < min_bytes) 2956 continue; 2957 2958 rb_erase(&entry->offset_index, &ctl->free_space_offset); 2959 ret = tree_insert_offset(&cluster->root, entry->offset, 2960 &entry->offset_index, 0); 2961 total_size += entry->bytes; 2962 ASSERT(!ret); /* -EEXIST; Logic error */ 2963 } while (node && entry != last); 2964 2965 cluster->max_size = max_extent; 2966 trace_btrfs_setup_cluster(block_group, cluster, total_size, 0); 2967 return 0; 2968 } 2969 2970 /* 2971 * This specifically looks for bitmaps that may work in the cluster, we assume 2972 * that we have already failed to find extents that will work. 2973 */ 2974 static noinline int 2975 setup_cluster_bitmap(struct btrfs_block_group_cache *block_group, 2976 struct btrfs_free_cluster *cluster, 2977 struct list_head *bitmaps, u64 offset, u64 bytes, 2978 u64 cont1_bytes, u64 min_bytes) 2979 { 2980 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 2981 struct btrfs_free_space *entry = NULL; 2982 int ret = -ENOSPC; 2983 u64 bitmap_offset = offset_to_bitmap(ctl, offset); 2984 2985 if (ctl->total_bitmaps == 0) 2986 return -ENOSPC; 2987 2988 /* 2989 * The bitmap that covers offset won't be in the list unless offset 2990 * is just its start offset. 2991 */ 2992 if (!list_empty(bitmaps)) 2993 entry = list_first_entry(bitmaps, struct btrfs_free_space, list); 2994 2995 if (!entry || entry->offset != bitmap_offset) { 2996 entry = tree_search_offset(ctl, bitmap_offset, 1, 0); 2997 if (entry && list_empty(&entry->list)) 2998 list_add(&entry->list, bitmaps); 2999 } 3000 3001 list_for_each_entry(entry, bitmaps, list) { 3002 if (entry->bytes < bytes) 3003 continue; 3004 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset, 3005 bytes, cont1_bytes, min_bytes); 3006 if (!ret) 3007 return 0; 3008 } 3009 3010 /* 3011 * The bitmaps list has all the bitmaps that record free space 3012 * starting after offset, so no more search is required. 3013 */ 3014 return -ENOSPC; 3015 } 3016 3017 /* 3018 * here we try to find a cluster of blocks in a block group. The goal 3019 * is to find at least bytes+empty_size. 3020 * We might not find them all in one contiguous area. 3021 * 3022 * returns zero and sets up cluster if things worked out, otherwise 3023 * it returns -enospc 3024 */ 3025 int btrfs_find_space_cluster(struct btrfs_fs_info *fs_info, 3026 struct btrfs_block_group_cache *block_group, 3027 struct btrfs_free_cluster *cluster, 3028 u64 offset, u64 bytes, u64 empty_size) 3029 { 3030 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 3031 struct btrfs_free_space *entry, *tmp; 3032 LIST_HEAD(bitmaps); 3033 u64 min_bytes; 3034 u64 cont1_bytes; 3035 int ret; 3036 3037 /* 3038 * Choose the minimum extent size we'll require for this 3039 * cluster. For SSD_SPREAD, don't allow any fragmentation. 3040 * For metadata, allow allocates with smaller extents. For 3041 * data, keep it dense. 3042 */ 3043 if (btrfs_test_opt(fs_info, SSD_SPREAD)) { 3044 cont1_bytes = min_bytes = bytes + empty_size; 3045 } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) { 3046 cont1_bytes = bytes; 3047 min_bytes = fs_info->sectorsize; 3048 } else { 3049 cont1_bytes = max(bytes, (bytes + empty_size) >> 2); 3050 min_bytes = fs_info->sectorsize; 3051 } 3052 3053 spin_lock(&ctl->tree_lock); 3054 3055 /* 3056 * If we know we don't have enough space to make a cluster don't even 3057 * bother doing all the work to try and find one. 3058 */ 3059 if (ctl->free_space < bytes) { 3060 spin_unlock(&ctl->tree_lock); 3061 return -ENOSPC; 3062 } 3063 3064 spin_lock(&cluster->lock); 3065 3066 /* someone already found a cluster, hooray */ 3067 if (cluster->block_group) { 3068 ret = 0; 3069 goto out; 3070 } 3071 3072 trace_btrfs_find_cluster(block_group, offset, bytes, empty_size, 3073 min_bytes); 3074 3075 ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset, 3076 bytes + empty_size, 3077 cont1_bytes, min_bytes); 3078 if (ret) 3079 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps, 3080 offset, bytes + empty_size, 3081 cont1_bytes, min_bytes); 3082 3083 /* Clear our temporary list */ 3084 list_for_each_entry_safe(entry, tmp, &bitmaps, list) 3085 list_del_init(&entry->list); 3086 3087 if (!ret) { 3088 atomic_inc(&block_group->count); 3089 list_add_tail(&cluster->block_group_list, 3090 &block_group->cluster_list); 3091 cluster->block_group = block_group; 3092 } else { 3093 trace_btrfs_failed_cluster_setup(block_group); 3094 } 3095 out: 3096 spin_unlock(&cluster->lock); 3097 spin_unlock(&ctl->tree_lock); 3098 3099 return ret; 3100 } 3101 3102 /* 3103 * simple code to zero out a cluster 3104 */ 3105 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster) 3106 { 3107 spin_lock_init(&cluster->lock); 3108 spin_lock_init(&cluster->refill_lock); 3109 cluster->root = RB_ROOT; 3110 cluster->max_size = 0; 3111 cluster->fragmented = false; 3112 INIT_LIST_HEAD(&cluster->block_group_list); 3113 cluster->block_group = NULL; 3114 } 3115 3116 static int do_trimming(struct btrfs_block_group_cache *block_group, 3117 u64 *total_trimmed, u64 start, u64 bytes, 3118 u64 reserved_start, u64 reserved_bytes, 3119 struct btrfs_trim_range *trim_entry) 3120 { 3121 struct btrfs_space_info *space_info = block_group->space_info; 3122 struct btrfs_fs_info *fs_info = block_group->fs_info; 3123 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 3124 int ret; 3125 int update = 0; 3126 u64 trimmed = 0; 3127 3128 spin_lock(&space_info->lock); 3129 spin_lock(&block_group->lock); 3130 if (!block_group->ro) { 3131 block_group->reserved += reserved_bytes; 3132 space_info->bytes_reserved += reserved_bytes; 3133 update = 1; 3134 } 3135 spin_unlock(&block_group->lock); 3136 spin_unlock(&space_info->lock); 3137 3138 ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed); 3139 if (!ret) 3140 *total_trimmed += trimmed; 3141 3142 mutex_lock(&ctl->cache_writeout_mutex); 3143 btrfs_add_free_space(block_group, reserved_start, reserved_bytes); 3144 list_del(&trim_entry->list); 3145 mutex_unlock(&ctl->cache_writeout_mutex); 3146 3147 if (update) { 3148 spin_lock(&space_info->lock); 3149 spin_lock(&block_group->lock); 3150 if (block_group->ro) 3151 space_info->bytes_readonly += reserved_bytes; 3152 block_group->reserved -= reserved_bytes; 3153 space_info->bytes_reserved -= reserved_bytes; 3154 spin_unlock(&space_info->lock); 3155 spin_unlock(&block_group->lock); 3156 } 3157 3158 return ret; 3159 } 3160 3161 static int trim_no_bitmap(struct btrfs_block_group_cache *block_group, 3162 u64 *total_trimmed, u64 start, u64 end, u64 minlen) 3163 { 3164 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 3165 struct btrfs_free_space *entry; 3166 struct rb_node *node; 3167 int ret = 0; 3168 u64 extent_start; 3169 u64 extent_bytes; 3170 u64 bytes; 3171 3172 while (start < end) { 3173 struct btrfs_trim_range trim_entry; 3174 3175 mutex_lock(&ctl->cache_writeout_mutex); 3176 spin_lock(&ctl->tree_lock); 3177 3178 if (ctl->free_space < minlen) { 3179 spin_unlock(&ctl->tree_lock); 3180 mutex_unlock(&ctl->cache_writeout_mutex); 3181 break; 3182 } 3183 3184 entry = tree_search_offset(ctl, start, 0, 1); 3185 if (!entry) { 3186 spin_unlock(&ctl->tree_lock); 3187 mutex_unlock(&ctl->cache_writeout_mutex); 3188 break; 3189 } 3190 3191 /* skip bitmaps */ 3192 while (entry->bitmap) { 3193 node = rb_next(&entry->offset_index); 3194 if (!node) { 3195 spin_unlock(&ctl->tree_lock); 3196 mutex_unlock(&ctl->cache_writeout_mutex); 3197 goto out; 3198 } 3199 entry = rb_entry(node, struct btrfs_free_space, 3200 offset_index); 3201 } 3202 3203 if (entry->offset >= end) { 3204 spin_unlock(&ctl->tree_lock); 3205 mutex_unlock(&ctl->cache_writeout_mutex); 3206 break; 3207 } 3208 3209 extent_start = entry->offset; 3210 extent_bytes = entry->bytes; 3211 start = max(start, extent_start); 3212 bytes = min(extent_start + extent_bytes, end) - start; 3213 if (bytes < minlen) { 3214 spin_unlock(&ctl->tree_lock); 3215 mutex_unlock(&ctl->cache_writeout_mutex); 3216 goto next; 3217 } 3218 3219 unlink_free_space(ctl, entry); 3220 kmem_cache_free(btrfs_free_space_cachep, entry); 3221 3222 spin_unlock(&ctl->tree_lock); 3223 trim_entry.start = extent_start; 3224 trim_entry.bytes = extent_bytes; 3225 list_add_tail(&trim_entry.list, &ctl->trimming_ranges); 3226 mutex_unlock(&ctl->cache_writeout_mutex); 3227 3228 ret = do_trimming(block_group, total_trimmed, start, bytes, 3229 extent_start, extent_bytes, &trim_entry); 3230 if (ret) 3231 break; 3232 next: 3233 start += bytes; 3234 3235 if (fatal_signal_pending(current)) { 3236 ret = -ERESTARTSYS; 3237 break; 3238 } 3239 3240 cond_resched(); 3241 } 3242 out: 3243 return ret; 3244 } 3245 3246 static int trim_bitmaps(struct btrfs_block_group_cache *block_group, 3247 u64 *total_trimmed, u64 start, u64 end, u64 minlen) 3248 { 3249 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; 3250 struct btrfs_free_space *entry; 3251 int ret = 0; 3252 int ret2; 3253 u64 bytes; 3254 u64 offset = offset_to_bitmap(ctl, start); 3255 3256 while (offset < end) { 3257 bool next_bitmap = false; 3258 struct btrfs_trim_range trim_entry; 3259 3260 mutex_lock(&ctl->cache_writeout_mutex); 3261 spin_lock(&ctl->tree_lock); 3262 3263 if (ctl->free_space < minlen) { 3264 spin_unlock(&ctl->tree_lock); 3265 mutex_unlock(&ctl->cache_writeout_mutex); 3266 break; 3267 } 3268 3269 entry = tree_search_offset(ctl, offset, 1, 0); 3270 if (!entry) { 3271 spin_unlock(&ctl->tree_lock); 3272 mutex_unlock(&ctl->cache_writeout_mutex); 3273 next_bitmap = true; 3274 goto next; 3275 } 3276 3277 bytes = minlen; 3278 ret2 = search_bitmap(ctl, entry, &start, &bytes, false); 3279 if (ret2 || start >= end) { 3280 spin_unlock(&ctl->tree_lock); 3281 mutex_unlock(&ctl->cache_writeout_mutex); 3282 next_bitmap = true; 3283 goto next; 3284 } 3285 3286 bytes = min(bytes, end - start); 3287 if (bytes < minlen) { 3288 spin_unlock(&ctl->tree_lock); 3289 mutex_unlock(&ctl->cache_writeout_mutex); 3290 goto next; 3291 } 3292 3293 bitmap_clear_bits(ctl, entry, start, bytes); 3294 if (entry->bytes == 0) 3295 free_bitmap(ctl, entry); 3296 3297 spin_unlock(&ctl->tree_lock); 3298 trim_entry.start = start; 3299 trim_entry.bytes = bytes; 3300 list_add_tail(&trim_entry.list, &ctl->trimming_ranges); 3301 mutex_unlock(&ctl->cache_writeout_mutex); 3302 3303 ret = do_trimming(block_group, total_trimmed, start, bytes, 3304 start, bytes, &trim_entry); 3305 if (ret) 3306 break; 3307 next: 3308 if (next_bitmap) { 3309 offset += BITS_PER_BITMAP * ctl->unit; 3310 } else { 3311 start += bytes; 3312 if (start >= offset + BITS_PER_BITMAP * ctl->unit) 3313 offset += BITS_PER_BITMAP * ctl->unit; 3314 } 3315 3316 if (fatal_signal_pending(current)) { 3317 ret = -ERESTARTSYS; 3318 break; 3319 } 3320 3321 cond_resched(); 3322 } 3323 3324 return ret; 3325 } 3326 3327 void btrfs_get_block_group_trimming(struct btrfs_block_group_cache *cache) 3328 { 3329 atomic_inc(&cache->trimming); 3330 } 3331 3332 void btrfs_put_block_group_trimming(struct btrfs_block_group_cache *block_group) 3333 { 3334 struct btrfs_fs_info *fs_info = block_group->fs_info; 3335 struct extent_map_tree *em_tree; 3336 struct extent_map *em; 3337 bool cleanup; 3338 3339 spin_lock(&block_group->lock); 3340 cleanup = (atomic_dec_and_test(&block_group->trimming) && 3341 block_group->removed); 3342 spin_unlock(&block_group->lock); 3343 3344 if (cleanup) { 3345 mutex_lock(&fs_info->chunk_mutex); 3346 em_tree = &fs_info->mapping_tree.map_tree; 3347 write_lock(&em_tree->lock); 3348 em = lookup_extent_mapping(em_tree, block_group->key.objectid, 3349 1); 3350 BUG_ON(!em); /* logic error, can't happen */ 3351 /* 3352 * remove_extent_mapping() will delete us from the pinned_chunks 3353 * list, which is protected by the chunk mutex. 3354 */ 3355 remove_extent_mapping(em_tree, em); 3356 write_unlock(&em_tree->lock); 3357 mutex_unlock(&fs_info->chunk_mutex); 3358 3359 /* once for us and once for the tree */ 3360 free_extent_map(em); 3361 free_extent_map(em); 3362 3363 /* 3364 * We've left one free space entry and other tasks trimming 3365 * this block group have left 1 entry each one. Free them. 3366 */ 3367 __btrfs_remove_free_space_cache(block_group->free_space_ctl); 3368 } 3369 } 3370 3371 int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group, 3372 u64 *trimmed, u64 start, u64 end, u64 minlen) 3373 { 3374 int ret; 3375 3376 *trimmed = 0; 3377 3378 spin_lock(&block_group->lock); 3379 if (block_group->removed) { 3380 spin_unlock(&block_group->lock); 3381 return 0; 3382 } 3383 btrfs_get_block_group_trimming(block_group); 3384 spin_unlock(&block_group->lock); 3385 3386 ret = trim_no_bitmap(block_group, trimmed, start, end, minlen); 3387 if (ret) 3388 goto out; 3389 3390 ret = trim_bitmaps(block_group, trimmed, start, end, minlen); 3391 out: 3392 btrfs_put_block_group_trimming(block_group); 3393 return ret; 3394 } 3395 3396 /* 3397 * Find the left-most item in the cache tree, and then return the 3398 * smallest inode number in the item. 3399 * 3400 * Note: the returned inode number may not be the smallest one in 3401 * the tree, if the left-most item is a bitmap. 3402 */ 3403 u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root) 3404 { 3405 struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl; 3406 struct btrfs_free_space *entry = NULL; 3407 u64 ino = 0; 3408 3409 spin_lock(&ctl->tree_lock); 3410 3411 if (RB_EMPTY_ROOT(&ctl->free_space_offset)) 3412 goto out; 3413 3414 entry = rb_entry(rb_first(&ctl->free_space_offset), 3415 struct btrfs_free_space, offset_index); 3416 3417 if (!entry->bitmap) { 3418 ino = entry->offset; 3419 3420 unlink_free_space(ctl, entry); 3421 entry->offset++; 3422 entry->bytes--; 3423 if (!entry->bytes) 3424 kmem_cache_free(btrfs_free_space_cachep, entry); 3425 else 3426 link_free_space(ctl, entry); 3427 } else { 3428 u64 offset = 0; 3429 u64 count = 1; 3430 int ret; 3431 3432 ret = search_bitmap(ctl, entry, &offset, &count, true); 3433 /* Logic error; Should be empty if it can't find anything */ 3434 ASSERT(!ret); 3435 3436 ino = offset; 3437 bitmap_clear_bits(ctl, entry, offset, 1); 3438 if (entry->bytes == 0) 3439 free_bitmap(ctl, entry); 3440 } 3441 out: 3442 spin_unlock(&ctl->tree_lock); 3443 3444 return ino; 3445 } 3446 3447 struct inode *lookup_free_ino_inode(struct btrfs_root *root, 3448 struct btrfs_path *path) 3449 { 3450 struct inode *inode = NULL; 3451 3452 spin_lock(&root->ino_cache_lock); 3453 if (root->ino_cache_inode) 3454 inode = igrab(root->ino_cache_inode); 3455 spin_unlock(&root->ino_cache_lock); 3456 if (inode) 3457 return inode; 3458 3459 inode = __lookup_free_space_inode(root, path, 0); 3460 if (IS_ERR(inode)) 3461 return inode; 3462 3463 spin_lock(&root->ino_cache_lock); 3464 if (!btrfs_fs_closing(root->fs_info)) 3465 root->ino_cache_inode = igrab(inode); 3466 spin_unlock(&root->ino_cache_lock); 3467 3468 return inode; 3469 } 3470 3471 int create_free_ino_inode(struct btrfs_root *root, 3472 struct btrfs_trans_handle *trans, 3473 struct btrfs_path *path) 3474 { 3475 return __create_free_space_inode(root, trans, path, 3476 BTRFS_FREE_INO_OBJECTID, 0); 3477 } 3478 3479 int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root) 3480 { 3481 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl; 3482 struct btrfs_path *path; 3483 struct inode *inode; 3484 int ret = 0; 3485 u64 root_gen = btrfs_root_generation(&root->root_item); 3486 3487 if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE)) 3488 return 0; 3489 3490 /* 3491 * If we're unmounting then just return, since this does a search on the 3492 * normal root and not the commit root and we could deadlock. 3493 */ 3494 if (btrfs_fs_closing(fs_info)) 3495 return 0; 3496 3497 path = btrfs_alloc_path(); 3498 if (!path) 3499 return 0; 3500 3501 inode = lookup_free_ino_inode(root, path); 3502 if (IS_ERR(inode)) 3503 goto out; 3504 3505 if (root_gen != BTRFS_I(inode)->generation) 3506 goto out_put; 3507 3508 ret = __load_free_space_cache(root, inode, ctl, path, 0); 3509 3510 if (ret < 0) 3511 btrfs_err(fs_info, 3512 "failed to load free ino cache for root %llu", 3513 root->root_key.objectid); 3514 out_put: 3515 iput(inode); 3516 out: 3517 btrfs_free_path(path); 3518 return ret; 3519 } 3520 3521 int btrfs_write_out_ino_cache(struct btrfs_root *root, 3522 struct btrfs_trans_handle *trans, 3523 struct btrfs_path *path, 3524 struct inode *inode) 3525 { 3526 struct btrfs_fs_info *fs_info = root->fs_info; 3527 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl; 3528 int ret; 3529 struct btrfs_io_ctl io_ctl; 3530 bool release_metadata = true; 3531 3532 if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE)) 3533 return 0; 3534 3535 memset(&io_ctl, 0, sizeof(io_ctl)); 3536 ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl, trans); 3537 if (!ret) { 3538 /* 3539 * At this point writepages() didn't error out, so our metadata 3540 * reservation is released when the writeback finishes, at 3541 * inode.c:btrfs_finish_ordered_io(), regardless of it finishing 3542 * with or without an error. 3543 */ 3544 release_metadata = false; 3545 ret = btrfs_wait_cache_io_root(root, trans, &io_ctl, path); 3546 } 3547 3548 if (ret) { 3549 if (release_metadata) 3550 btrfs_delalloc_release_metadata(BTRFS_I(inode), 3551 inode->i_size); 3552 #ifdef DEBUG 3553 btrfs_err(fs_info, 3554 "failed to write free ino cache for root %llu", 3555 root->root_key.objectid); 3556 #endif 3557 } 3558 3559 return ret; 3560 } 3561 3562 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS 3563 /* 3564 * Use this if you need to make a bitmap or extent entry specifically, it 3565 * doesn't do any of the merging that add_free_space does, this acts a lot like 3566 * how the free space cache loading stuff works, so you can get really weird 3567 * configurations. 3568 */ 3569 int test_add_free_space_entry(struct btrfs_block_group_cache *cache, 3570 u64 offset, u64 bytes, bool bitmap) 3571 { 3572 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl; 3573 struct btrfs_free_space *info = NULL, *bitmap_info; 3574 void *map = NULL; 3575 u64 bytes_added; 3576 int ret; 3577 3578 again: 3579 if (!info) { 3580 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); 3581 if (!info) 3582 return -ENOMEM; 3583 } 3584 3585 if (!bitmap) { 3586 spin_lock(&ctl->tree_lock); 3587 info->offset = offset; 3588 info->bytes = bytes; 3589 info->max_extent_size = 0; 3590 ret = link_free_space(ctl, info); 3591 spin_unlock(&ctl->tree_lock); 3592 if (ret) 3593 kmem_cache_free(btrfs_free_space_cachep, info); 3594 return ret; 3595 } 3596 3597 if (!map) { 3598 map = kzalloc(PAGE_SIZE, GFP_NOFS); 3599 if (!map) { 3600 kmem_cache_free(btrfs_free_space_cachep, info); 3601 return -ENOMEM; 3602 } 3603 } 3604 3605 spin_lock(&ctl->tree_lock); 3606 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 3607 1, 0); 3608 if (!bitmap_info) { 3609 info->bitmap = map; 3610 map = NULL; 3611 add_new_bitmap(ctl, info, offset); 3612 bitmap_info = info; 3613 info = NULL; 3614 } 3615 3616 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes); 3617 3618 bytes -= bytes_added; 3619 offset += bytes_added; 3620 spin_unlock(&ctl->tree_lock); 3621 3622 if (bytes) 3623 goto again; 3624 3625 if (info) 3626 kmem_cache_free(btrfs_free_space_cachep, info); 3627 if (map) 3628 kfree(map); 3629 return 0; 3630 } 3631 3632 /* 3633 * Checks to see if the given range is in the free space cache. This is really 3634 * just used to check the absence of space, so if there is free space in the 3635 * range at all we will return 1. 3636 */ 3637 int test_check_exists(struct btrfs_block_group_cache *cache, 3638 u64 offset, u64 bytes) 3639 { 3640 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl; 3641 struct btrfs_free_space *info; 3642 int ret = 0; 3643 3644 spin_lock(&ctl->tree_lock); 3645 info = tree_search_offset(ctl, offset, 0, 0); 3646 if (!info) { 3647 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 3648 1, 0); 3649 if (!info) 3650 goto out; 3651 } 3652 3653 have_info: 3654 if (info->bitmap) { 3655 u64 bit_off, bit_bytes; 3656 struct rb_node *n; 3657 struct btrfs_free_space *tmp; 3658 3659 bit_off = offset; 3660 bit_bytes = ctl->unit; 3661 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false); 3662 if (!ret) { 3663 if (bit_off == offset) { 3664 ret = 1; 3665 goto out; 3666 } else if (bit_off > offset && 3667 offset + bytes > bit_off) { 3668 ret = 1; 3669 goto out; 3670 } 3671 } 3672 3673 n = rb_prev(&info->offset_index); 3674 while (n) { 3675 tmp = rb_entry(n, struct btrfs_free_space, 3676 offset_index); 3677 if (tmp->offset + tmp->bytes < offset) 3678 break; 3679 if (offset + bytes < tmp->offset) { 3680 n = rb_prev(&tmp->offset_index); 3681 continue; 3682 } 3683 info = tmp; 3684 goto have_info; 3685 } 3686 3687 n = rb_next(&info->offset_index); 3688 while (n) { 3689 tmp = rb_entry(n, struct btrfs_free_space, 3690 offset_index); 3691 if (offset + bytes < tmp->offset) 3692 break; 3693 if (tmp->offset + tmp->bytes < offset) { 3694 n = rb_next(&tmp->offset_index); 3695 continue; 3696 } 3697 info = tmp; 3698 goto have_info; 3699 } 3700 3701 ret = 0; 3702 goto out; 3703 } 3704 3705 if (info->offset == offset) { 3706 ret = 1; 3707 goto out; 3708 } 3709 3710 if (offset > info->offset && offset < info->offset + info->bytes) 3711 ret = 1; 3712 out: 3713 spin_unlock(&ctl->tree_lock); 3714 return ret; 3715 } 3716 #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */ 3717