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