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