fs/btrfs/free-space-cache.c

   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
  37 static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
  38                                                struct btrfs_path *path,
  39                                                u64 offset)
  40 {
  41         struct btrfs_key key;
  42         struct btrfs_key location;
  43         struct btrfs_disk_key disk_key;
  44         struct btrfs_free_space_header *header;
  45         struct extent_buffer *leaf;
  46         struct inode *inode = NULL;
  47         int ret;
  48
  49         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
  50         key.offset = offset;
  51         key.type = 0;
  52
  53         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  54         if (ret < 0)
  55                 return ERR_PTR(ret);
  56         if (ret > 0) {
  57                 btrfs_release_path(path);
  58                 return ERR_PTR(-ENOENT);
  59         }
  60
  61         leaf = path->nodes[0];
  62         header = btrfs_item_ptr(leaf, path->slots[0],
  63                                 struct btrfs_free_space_header);
  64         btrfs_free_space_key(leaf, header, &disk_key);
  65         btrfs_disk_key_to_cpu(&location, &disk_key);
  66         btrfs_release_path(path);
  67
  68         inode = btrfs_iget(root->fs_info->sb, &location, root, NULL);
  69         if (!inode)
  70                 return ERR_PTR(-ENOENT);
  71         if (IS_ERR(inode))
  72                 return inode;
  73         if (is_bad_inode(inode)) {
  74                 iput(inode);
  75                 return ERR_PTR(-ENOENT);
  76         }
  77
  78         inode->i_mapping->flags &= ~__GFP_FS;
  79
  80         return inode;
  81 }
  82
  83 struct inode *lookup_free_space_inode(struct btrfs_root *root,
  84                                       struct btrfs_block_group_cache
  85                                       *block_group, struct btrfs_path *path)
  86 {
  87         struct inode *inode = NULL;
  88
  89         spin_lock(&block_group->lock);
  90         if (block_group->inode)
  91                 inode = igrab(block_group->inode);
  92         spin_unlock(&block_group->lock);
  93         if (inode)
  94                 return inode;
  95
  96         inode = __lookup_free_space_inode(root, path,
  97                                           block_group->key.objectid);
  98         if (IS_ERR(inode))
  99                 return inode;
 100
 101         spin_lock(&block_group->lock);
 102         if (BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM) {
 103                 printk(KERN_INFO "Old style space inode found, converting.\n");
 104                 BTRFS_I(inode)->flags &= ~BTRFS_INODE_NODATASUM;
 105                 block_group->disk_cache_state = BTRFS_DC_CLEAR;
 106         }
 107
 108         if (!block_group->iref) {
 109                 block_group->inode = igrab(inode);
 110                 block_group->iref = 1;
 111         }
 112         spin_unlock(&block_group->lock);
 113
 114         return inode;
 115 }
 116
 117 int __create_free_space_inode(struct btrfs_root *root,
 118                               struct btrfs_trans_handle *trans,
 119                               struct btrfs_path *path, u64 ino, u64 offset)
 120 {
 121         struct btrfs_key key;
 122         struct btrfs_disk_key disk_key;
 123         struct btrfs_free_space_header *header;
 124         struct btrfs_inode_item *inode_item;
 125         struct extent_buffer *leaf;
 126         int ret;
 127
 128         ret = btrfs_insert_empty_inode(trans, root, path, ino);
 129         if (ret)
 130                 return ret;
 131
 132         leaf = path->nodes[0];
 133         inode_item = btrfs_item_ptr(leaf, path->slots[0],
 134                                     struct btrfs_inode_item);
 135         btrfs_item_key(leaf, &disk_key, path->slots[0]);
 136         memset_extent_buffer(leaf, 0, (unsigned long)inode_item,
 137                              sizeof(*inode_item));
 138         btrfs_set_inode_generation(leaf, inode_item, trans->transid);
 139         btrfs_set_inode_size(leaf, inode_item, 0);
 140         btrfs_set_inode_nbytes(leaf, inode_item, 0);
 141         btrfs_set_inode_uid(leaf, inode_item, 0);
 142         btrfs_set_inode_gid(leaf, inode_item, 0);
 143         btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
 144         btrfs_set_inode_flags(leaf, inode_item, BTRFS_INODE_NOCOMPRESS |
 145                               BTRFS_INODE_PREALLOC);
 146         btrfs_set_inode_nlink(leaf, inode_item, 1);
 147         btrfs_set_inode_transid(leaf, inode_item, trans->transid);
 148         btrfs_set_inode_block_group(leaf, inode_item, offset);
 149         btrfs_mark_buffer_dirty(leaf);
 150         btrfs_release_path(path);
 151
 152         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 153         key.offset = offset;
 154         key.type = 0;
 155
 156         ret = btrfs_insert_empty_item(trans, root, path, &key,
 157                                       sizeof(struct btrfs_free_space_header));
 158         if (ret < 0) {
 159                 btrfs_release_path(path);
 160                 return ret;
 161         }
 162         leaf = path->nodes[0];
 163         header = btrfs_item_ptr(leaf, path->slots[0],
 164                                 struct btrfs_free_space_header);
 165         memset_extent_buffer(leaf, 0, (unsigned long)header, sizeof(*header));
 166         btrfs_set_free_space_key(leaf, header, &disk_key);
 167         btrfs_mark_buffer_dirty(leaf);
 168         btrfs_release_path(path);
 169
 170         return 0;
 171 }
 172
 173 int create_free_space_inode(struct btrfs_root *root,
 174                             struct btrfs_trans_handle *trans,
 175                             struct btrfs_block_group_cache *block_group,
 176                             struct btrfs_path *path)
 177 {
 178         int ret;
 179         u64 ino;
 180
 181         ret = btrfs_find_free_objectid(root, &ino);
 182         if (ret < 0)
 183                 return ret;
 184
 185         return __create_free_space_inode(root, trans, path, ino,
 186                                          block_group->key.objectid);
 187 }
 188
 189 int btrfs_truncate_free_space_cache(struct btrfs_root *root,
 190                                     struct btrfs_trans_handle *trans,
 191                                     struct btrfs_path *path,
 192                                     struct inode *inode)
 193 {
 194         struct btrfs_block_rsv *rsv;
 195         loff_t oldsize;
 196         int ret = 0;
 197
 198         rsv = trans->block_rsv;
 199         trans->block_rsv = root->orphan_block_rsv;
 200         ret = btrfs_block_rsv_check(root, root->orphan_block_rsv, 0, 5, 0);
 201         if (ret)
 202                 return ret;
 203
 204         oldsize = i_size_read(inode);
 205         btrfs_i_size_write(inode, 0);
 206         truncate_pagecache(inode, oldsize, 0);
 207
 208         /*
 209          * We don't need an orphan item because truncating the free space cache
 210          * will never be split across transactions.
 211          */
 212         ret = btrfs_truncate_inode_items(trans, root, inode,
 213                                          0, BTRFS_EXTENT_DATA_KEY);
 214
 215         trans->block_rsv = rsv;
 216         if (ret) {
 217                 WARN_ON(1);
 218                 return ret;
 219         }
 220
 221         ret = btrfs_update_inode(trans, root, inode);
 222         return ret;
 223 }
 224
 225 static int readahead_cache(struct inode *inode)
 226 {
 227         struct file_ra_state *ra;
 228         unsigned long last_index;
 229
 230         ra = kzalloc(sizeof(*ra), GFP_NOFS);
 231         if (!ra)
 232                 return -ENOMEM;
 233
 234         file_ra_state_init(ra, inode->i_mapping);
 235         last_index = (i_size_read(inode) - 1) >> PAGE_CACHE_SHIFT;
 236
 237         page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
 238
 239         kfree(ra);
 240
 241         return 0;
 242 }
 243
 244 int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
 245                             struct btrfs_free_space_ctl *ctl,
 246                             struct btrfs_path *path, u64 offset)
 247 {
 248         struct btrfs_free_space_header *header;
 249         struct extent_buffer *leaf;
 250         struct page *page;
 251         struct btrfs_key key;
 252         struct list_head bitmaps;
 253         u64 num_entries;
 254         u64 num_bitmaps;
 255         u64 generation;
 256         pgoff_t index = 0;
 257         gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
 258         int ret = 0;
 259
 260         INIT_LIST_HEAD(&bitmaps);
 261
 262         /* Nothing in the space cache, goodbye */
 263         if (!i_size_read(inode))
 264                 goto out;
 265
 266         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 267         key.offset = offset;
 268         key.type = 0;
 269
 270         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 271         if (ret < 0)
 272                 goto out;
 273         else if (ret > 0) {
 274                 btrfs_release_path(path);
 275                 ret = 0;
 276                 goto out;
 277         }
 278
 279         ret = -1;
 280
 281         leaf = path->nodes[0];
 282         header = btrfs_item_ptr(leaf, path->slots[0],
 283                                 struct btrfs_free_space_header);
 284         num_entries = btrfs_free_space_entries(leaf, header);
 285         num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
 286         generation = btrfs_free_space_generation(leaf, header);
 287         btrfs_release_path(path);
 288
 289         if (BTRFS_I(inode)->generation != generation) {
 290                 printk(KERN_ERR "btrfs: free space inode generation (%llu) did"
 291                        " not match free space cache generation (%llu)\n",
 292                        (unsigned long long)BTRFS_I(inode)->generation,
 293                        (unsigned long long)generation);
 294                 goto out;
 295         }
 296
 297         if (!num_entries)
 298                 goto out;
 299
 300         ret = readahead_cache(inode);
 301         if (ret)
 302                 goto out;
 303
 304         while (1) {
 305                 struct btrfs_free_space_entry *entry;
 306                 struct btrfs_free_space *e;
 307                 void *addr;
 308                 unsigned long offset = 0;
 309                 int need_loop = 0;
 310
 311                 if (!num_entries && !num_bitmaps)
 312                         break;
 313
 314                 page = find_or_create_page(inode->i_mapping, index, mask);
 315                 if (!page)
 316                         goto free_cache;
 317
 318                 if (!PageUptodate(page)) {
 319                         btrfs_readpage(NULL, page);
 320                         lock_page(page);
 321                         if (!PageUptodate(page)) {
 322                                 unlock_page(page);
 323                                 page_cache_release(page);
 324                                 printk(KERN_ERR "btrfs: error reading free "
 325                                        "space cache\n");
 326                                 goto free_cache;
 327                         }
 328                 }
 329                 addr = kmap(page);
 330
 331                 if (index == 0) {
 332                         u64 *gen;
 333
 334                         /*
 335                          * We put a bogus crc in the front of the first page in
 336                          * case old kernels try to mount a fs with the new
 337                          * format to make sure they discard the cache.
 338                          */
 339                         addr += sizeof(u64);
 340                         offset += sizeof(u64);
 341
 342                         gen = addr;
 343                         if (*gen != BTRFS_I(inode)->generation) {
 344                                 printk_ratelimited(KERN_ERR "btrfs: space cache"
 345                                         " generation (%llu) does not match "
 346                                         "inode (%llu)\n",
 347                                         (unsigned long long)*gen,
 348                                         (unsigned long long)
 349                                         BTRFS_I(inode)->generation);
 350                                 kunmap(page);
 351                                 unlock_page(page);
 352                                 page_cache_release(page);
 353                                 goto free_cache;
 354                         }
 355                         addr += sizeof(u64);
 356                         offset += sizeof(u64);
 357                 }
 358                 entry = addr;
 359
 360                 while (1) {
 361                         if (!num_entries)
 362                                 break;
 363
 364                         need_loop = 1;
 365                         e = kmem_cache_zalloc(btrfs_free_space_cachep,
 366                                               GFP_NOFS);
 367                         if (!e) {
 368                                 kunmap(page);
 369                                 unlock_page(page);
 370                                 page_cache_release(page);
 371                                 goto free_cache;
 372                         }
 373
 374                         e->offset = le64_to_cpu(entry->offset);
 375                         e->bytes = le64_to_cpu(entry->bytes);
 376                         if (!e->bytes) {
 377                                 kunmap(page);
 378                                 kmem_cache_free(btrfs_free_space_cachep, e);
 379                                 unlock_page(page);
 380                                 page_cache_release(page);
 381                                 goto free_cache;
 382                         }
 383
 384                         if (entry->type == BTRFS_FREE_SPACE_EXTENT) {
 385                                 spin_lock(&ctl->tree_lock);
 386                                 ret = link_free_space(ctl, e);
 387                                 spin_unlock(&ctl->tree_lock);
 388                                 if (ret) {
 389                                         printk(KERN_ERR "Duplicate entries in "
 390                                                "free space cache, dumping\n");
 391                                         kunmap(page);
 392                                         unlock_page(page);
 393                                         page_cache_release(page);
 394                                         goto free_cache;
 395                                 }
 396                         } else {
 397                                 e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
 398                                 if (!e->bitmap) {
 399                                         kunmap(page);
 400                                         kmem_cache_free(
 401                                                 btrfs_free_space_cachep, e);
 402                                         unlock_page(page);
 403                                         page_cache_release(page);
 404                                         goto free_cache;
 405                                 }
 406                                 spin_lock(&ctl->tree_lock);
 407                                 ret = link_free_space(ctl, e);
 408                                 ctl->total_bitmaps++;
 409                                 ctl->op->recalc_thresholds(ctl);
 410                                 spin_unlock(&ctl->tree_lock);
 411                                 if (ret) {
 412                                         printk(KERN_ERR "Duplicate entries in "
 413                                                "free space cache, dumping\n");
 414                                         kunmap(page);
 415                                         unlock_page(page);
 416                                         page_cache_release(page);
 417                                         goto free_cache;
 418                                 }
 419                                 list_add_tail(&e->list, &bitmaps);
 420                         }
 421
 422                         num_entries--;
 423                         offset += sizeof(struct btrfs_free_space_entry);
 424                         if (offset + sizeof(struct btrfs_free_space_entry) >=
 425                             PAGE_CACHE_SIZE)
 426                                 break;
 427                         entry++;
 428                 }
 429
 430                 /*
 431                  * We read an entry out of this page, we need to move on to the
 432                  * next page.
 433                  */
 434                 if (need_loop) {
 435                         kunmap(page);
 436                         goto next;
 437                 }
 438
 439                 /*
 440                  * We add the bitmaps at the end of the entries in order that
 441                  * the bitmap entries are added to the cache.
 442                  */
 443                 e = list_entry(bitmaps.next, struct btrfs_free_space, list);
 444                 list_del_init(&e->list);
 445                 memcpy(e->bitmap, addr, PAGE_CACHE_SIZE);
 446                 kunmap(page);
 447                 num_bitmaps--;
 448 next:
 449                 unlock_page(page);
 450                 page_cache_release(page);
 451                 index++;
 452         }
 453
 454         ret = 1;
 455 out:
 456         return ret;
 457 free_cache:
 458         __btrfs_remove_free_space_cache(ctl);
 459         goto out;
 460 }
 461
 462 int load_free_space_cache(struct btrfs_fs_info *fs_info,
 463                           struct btrfs_block_group_cache *block_group)
 464 {
 465         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 466         struct btrfs_root *root = fs_info->tree_root;
 467         struct inode *inode;
 468         struct btrfs_path *path;
 469         int ret;
 470         bool matched;
 471         u64 used = btrfs_block_group_used(&block_group->item);
 472
 473         /*
 474          * If we're unmounting then just return, since this does a search on the
 475          * normal root and not the commit root and we could deadlock.
 476          */
 477         if (btrfs_fs_closing(fs_info))
 478                 return 0;
 479
 480         /*
 481          * If this block group has been marked to be cleared for one reason or
 482          * another then we can't trust the on disk cache, so just return.
 483          */
 484         spin_lock(&block_group->lock);
 485         if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
 486                 spin_unlock(&block_group->lock);
 487                 return 0;
 488         }
 489         spin_unlock(&block_group->lock);
 490
 491         path = btrfs_alloc_path();
 492         if (!path)
 493                 return 0;
 494
 495         inode = lookup_free_space_inode(root, block_group, path);
 496         if (IS_ERR(inode)) {
 497                 btrfs_free_path(path);
 498                 return 0;
 499         }
 500
 501         ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
 502                                       path, block_group->key.objectid);
 503         btrfs_free_path(path);
 504         if (ret <= 0)
 505                 goto out;
 506
 507         spin_lock(&ctl->tree_lock);
 508         matched = (ctl->free_space == (block_group->key.offset - used -
 509                                        block_group->bytes_super));
 510         spin_unlock(&ctl->tree_lock);
 511
 512         if (!matched) {
 513                 __btrfs_remove_free_space_cache(ctl);
 514                 printk(KERN_ERR "block group %llu has an wrong amount of free "
 515                        "space\n", block_group->key.objectid);
 516                 ret = -1;
 517         }
 518 out:
 519         if (ret < 0) {
 520                 /* This cache is bogus, make sure it gets cleared */
 521                 spin_lock(&block_group->lock);
 522                 block_group->disk_cache_state = BTRFS_DC_CLEAR;
 523                 spin_unlock(&block_group->lock);
 524                 ret = 0;
 525
 526                 printk(KERN_ERR "btrfs: failed to load free space cache "
 527                        "for block group %llu\n", block_group->key.objectid);
 528         }
 529
 530         iput(inode);
 531         return ret;
 532 }
 533
 534 /**
 535  * __btrfs_write_out_cache - write out cached info to an inode
 536  * @root - the root the inode belongs to
 537  * @ctl - the free space cache we are going to write out
 538  * @block_group - the block_group for this cache if it belongs to a block_group
 539  * @trans - the trans handle
 540  * @path - the path to use
 541  * @offset - the offset for the key we'll insert
 542  *
 543  * This function writes out a free space cache struct to disk for quick recovery
 544  * on mount.  This will return 0 if it was successfull in writing the cache out,
 545  * and -1 if it was not.
 546  */
 547 int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
 548                             struct btrfs_free_space_ctl *ctl,
 549                             struct btrfs_block_group_cache *block_group,
 550                             struct btrfs_trans_handle *trans,
 551                             struct btrfs_path *path, u64 offset)
 552 {
 553         struct btrfs_free_space_header *header;
 554         struct extent_buffer *leaf;
 555         struct rb_node *node;
 556         struct list_head *pos, *n;
 557         struct page **pages;
 558         struct page *page;
 559         struct extent_state *cached_state = NULL;
 560         struct btrfs_free_cluster *cluster = NULL;
 561         struct extent_io_tree *unpin = NULL;
 562         struct list_head bitmap_list;
 563         struct btrfs_key key;
 564         u64 start, end, len;
 565         u64 bytes = 0;
 566         u32 crc = ~(u32)0;
 567         gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
 568         int index = 0, num_pages = 0;
 569         int entries = 0;
 570         int bitmaps = 0;
 571         int ret;
 572         int err = -1;
 573         bool next_page = false;
 574         bool out_of_space = false;
 575
 576         INIT_LIST_HEAD(&bitmap_list);
 577
 578         if (!i_size_read(inode))
 579                 return -1;
 580
 581         num_pages = (i_size_read(inode) + PAGE_CACHE_SIZE - 1) >>
 582                 PAGE_CACHE_SHIFT;
 583
 584         filemap_write_and_wait(inode->i_mapping);
 585         btrfs_wait_ordered_range(inode, inode->i_size &
 586                                  ~(root->sectorsize - 1), (u64)-1);
 587
 588         pages = kzalloc(sizeof(struct page *) * num_pages, GFP_NOFS);
 589         if (!pages)
 590                 return -1;
 591
 592         /* Get the cluster for this block_group if it exists */
 593         if (block_group && !list_empty(&block_group->cluster_list))
 594                 cluster = list_entry(block_group->cluster_list.next,
 595                                      struct btrfs_free_cluster,
 596                                      block_group_list);
 597
 598         /*
 599          * We shouldn't have switched the pinned extents yet so this is the
 600          * right one
 601          */
 602         unpin = root->fs_info->pinned_extents;
 603
 604         /*
 605          * Lock all pages first so we can lock the extent safely.
 606          *
 607          * NOTE: Because we hold the ref the entire time we're going to write to
 608          * the page find_get_page should never fail, so we don't do a check
 609          * after find_get_page at this point.  Just putting this here so people
 610          * know and don't freak out.
 611          */
 612         while (index < num_pages) {
 613                 page = find_or_create_page(inode->i_mapping, index, mask);
 614                 if (!page) {
 615                         int i;
 616
 617                         for (i = 0; i < num_pages; i++) {
 618                                 unlock_page(pages[i]);
 619                                 page_cache_release(pages[i]);
 620                         }
 621                         goto out;
 622                 }
 623                 pages[index] = page;
 624                 index++;
 625         }
 626
 627         index = 0;
 628         lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
 629                          0, &cached_state, GFP_NOFS);
 630
 631         /*
 632          * When searching for pinned extents, we need to start at our start
 633          * offset.
 634          */
 635         if (block_group)
 636                 start = block_group->key.objectid;
 637
 638         node = rb_first(&ctl->free_space_offset);
 639         if (!node && cluster) {
 640                 node = rb_first(&cluster->root);
 641                 cluster = NULL;
 642         }
 643
 644         /* Write out the extent entries */
 645         do {
 646                 struct btrfs_free_space_entry *entry;
 647                 void *addr, *orig;
 648                 unsigned long offset = 0;
 649
 650                 next_page = false;
 651
 652                 if (index >= num_pages) {
 653                         out_of_space = true;
 654                         break;
 655                 }
 656
 657                 page = pages[index];
 658
 659                 orig = addr = kmap(page);
 660                 if (index == 0) {
 661                         u64 *gen;
 662
 663                         /*
 664                          * We're going to put in a bogus crc for this page to
 665                          * make sure that old kernels who aren't aware of this
 666                          * format will be sure to discard the cache.
 667                          */
 668                         addr += sizeof(u64);
 669                         offset += sizeof(u64);
 670
 671                         gen = addr;
 672                         *gen = trans->transid;
 673                         addr += sizeof(u64);
 674                         offset += sizeof(u64);
 675                 }
 676                 entry = addr;
 677
 678                 memset(addr, 0, PAGE_CACHE_SIZE - offset);
 679                 while (node && !next_page) {
 680                         struct btrfs_free_space *e;
 681
 682                         e = rb_entry(node, struct btrfs_free_space, offset_index);
 683                         entries++;
 684
 685                         entry->offset = cpu_to_le64(e->offset);
 686                         entry->bytes = cpu_to_le64(e->bytes);
 687                         if (e->bitmap) {
 688                                 entry->type = BTRFS_FREE_SPACE_BITMAP;
 689                                 list_add_tail(&e->list, &bitmap_list);
 690                                 bitmaps++;
 691                         } else {
 692                                 entry->type = BTRFS_FREE_SPACE_EXTENT;
 693                         }
 694                         node = rb_next(node);
 695                         if (!node && cluster) {
 696                                 node = rb_first(&cluster->root);
 697                                 cluster = NULL;
 698                         }
 699                         offset += sizeof(struct btrfs_free_space_entry);
 700                         if (offset + sizeof(struct btrfs_free_space_entry) >=
 701                             PAGE_CACHE_SIZE)
 702                                 next_page = true;
 703                         entry++;
 704                 }
 705
 706                 /*
 707                  * We want to add any pinned extents to our free space cache
 708                  * so we don't leak the space
 709                  */
 710                 while (block_group && !next_page &&
 711                        (start < block_group->key.objectid +
 712                         block_group->key.offset)) {
 713                         ret = find_first_extent_bit(unpin, start, &start, &end,
 714                                                     EXTENT_DIRTY);
 715                         if (ret) {
 716                                 ret = 0;
 717                                 break;
 718                         }
 719
 720                         /* This pinned extent is out of our range */
 721                         if (start >= block_group->key.objectid +
 722                             block_group->key.offset)
 723                                 break;
 724
 725                         len = block_group->key.objectid +
 726                                 block_group->key.offset - start;
 727                         len = min(len, end + 1 - start);
 728
 729                         entries++;
 730                         entry->offset = cpu_to_le64(start);
 731                         entry->bytes = cpu_to_le64(len);
 732                         entry->type = BTRFS_FREE_SPACE_EXTENT;
 733
 734                         start = end + 1;
 735                         offset += sizeof(struct btrfs_free_space_entry);
 736                         if (offset + sizeof(struct btrfs_free_space_entry) >=
 737                             PAGE_CACHE_SIZE)
 738                                 next_page = true;
 739                         entry++;
 740                 }
 741
 742                 /* Generate bogus crc value */
 743                 if (index == 0) {
 744                         u32 *tmp;
 745                         crc = btrfs_csum_data(root, orig + sizeof(u64), crc,
 746                                               PAGE_CACHE_SIZE - sizeof(u64));
 747                         btrfs_csum_final(crc, (char *)&crc);
 748                         crc++;
 749                         tmp = orig;
 750                         *tmp = crc;
 751                 }
 752
 753                 kunmap(page);
 754
 755                 bytes += PAGE_CACHE_SIZE;
 756
 757                 index++;
 758         } while (node || next_page);
 759
 760         /* Write out the bitmaps */
 761         list_for_each_safe(pos, n, &bitmap_list) {
 762                 void *addr;
 763                 struct btrfs_free_space *entry =
 764                         list_entry(pos, struct btrfs_free_space, list);
 765
 766                 if (index >= num_pages) {
 767                         out_of_space = true;
 768                         break;
 769                 }
 770                 page = pages[index];
 771
 772                 addr = kmap(page);
 773                 memcpy(addr, entry->bitmap, PAGE_CACHE_SIZE);
 774                 kunmap(page);
 775                 bytes += PAGE_CACHE_SIZE;
 776
 777                 list_del_init(&entry->list);
 778                 index++;
 779         }
 780
 781         if (out_of_space) {
 782                 btrfs_drop_pages(pages, num_pages);
 783                 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
 784                                      i_size_read(inode) - 1, &cached_state,
 785                                      GFP_NOFS);
 786                 goto out;
 787         }
 788
 789         /* Zero out the rest of the pages just to make sure */
 790         while (index < num_pages) {
 791                 void *addr;
 792
 793                 page = pages[index];
 794                 addr = kmap(page);
 795                 memset(addr, 0, PAGE_CACHE_SIZE);
 796                 kunmap(page);
 797                 bytes += PAGE_CACHE_SIZE;
 798                 index++;
 799         }
 800
 801         ret = btrfs_dirty_pages(root, inode, pages, num_pages, 0,
 802                                             bytes, &cached_state);
 803         btrfs_drop_pages(pages, num_pages);
 804         unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
 805                              i_size_read(inode) - 1, &cached_state, GFP_NOFS);
 806
 807         if (ret)
 808                 goto out;
 809
 810         BTRFS_I(inode)->generation = trans->transid;
 811
 812         filemap_write_and_wait(inode->i_mapping);
 813
 814         key.objectid = BTRFS_FREE_SPACE_OBJECTID;
 815         key.offset = offset;
 816         key.type = 0;
 817
 818         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 819         if (ret < 0) {
 820                 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, bytes - 1,
 821                                  EXTENT_DIRTY | EXTENT_DELALLOC |
 822                                  EXTENT_DO_ACCOUNTING, 0, 0, NULL, GFP_NOFS);
 823                 goto out;
 824         }
 825         leaf = path->nodes[0];
 826         if (ret > 0) {
 827                 struct btrfs_key found_key;
 828                 BUG_ON(!path->slots[0]);
 829                 path->slots[0]--;
 830                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 831                 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
 832                     found_key.offset != offset) {
 833                         clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, bytes - 1,
 834                                          EXTENT_DIRTY | EXTENT_DELALLOC |
 835                                          EXTENT_DO_ACCOUNTING, 0, 0, NULL,
 836                                          GFP_NOFS);
 837                         btrfs_release_path(path);
 838                         goto out;
 839                 }
 840         }
 841         header = btrfs_item_ptr(leaf, path->slots[0],
 842                                 struct btrfs_free_space_header);
 843         btrfs_set_free_space_entries(leaf, header, entries);
 844         btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
 845         btrfs_set_free_space_generation(leaf, header, trans->transid);
 846         btrfs_mark_buffer_dirty(leaf);
 847         btrfs_release_path(path);
 848
 849         err = 0;
 850 out:
 851         kfree(pages);
 852         if (err) {
 853                 invalidate_inode_pages2_range(inode->i_mapping, 0, index);
 854                 BTRFS_I(inode)->generation = 0;
 855         }
 856         btrfs_update_inode(trans, root, inode);
 857         return err;
 858 }
 859
 860 int btrfs_write_out_cache(struct btrfs_root *root,
 861                           struct btrfs_trans_handle *trans,
 862                           struct btrfs_block_group_cache *block_group,
 863                           struct btrfs_path *path)
 864 {
 865         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
 866         struct inode *inode;
 867         int ret = 0;
 868
 869         root = root->fs_info->tree_root;
 870
 871         spin_lock(&block_group->lock);
 872         if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
 873                 spin_unlock(&block_group->lock);
 874                 return 0;
 875         }
 876         spin_unlock(&block_group->lock);
 877
 878         inode = lookup_free_space_inode(root, block_group, path);
 879         if (IS_ERR(inode))
 880                 return 0;
 881
 882         ret = __btrfs_write_out_cache(root, inode, ctl, block_group, trans,
 883                                       path, block_group->key.objectid);
 884         if (ret) {
 885                 btrfs_delalloc_release_metadata(inode, inode->i_size);
 886                 spin_lock(&block_group->lock);
 887                 block_group->disk_cache_state = BTRFS_DC_ERROR;
 888                 spin_unlock(&block_group->lock);
 889                 ret = 0;
 890 #ifdef DEBUG
 891                 printk(KERN_ERR "btrfs: failed to write free space cace "
 892                        "for block group %llu\n", block_group->key.objectid);
 893 #endif
 894         }
 895
 896         iput(inode);
 897         return ret;
 898 }
 899
 900 static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
 901                                           u64 offset)
 902 {
 903         BUG_ON(offset < bitmap_start);
 904         offset -= bitmap_start;
 905         return (unsigned long)(div_u64(offset, unit));
 906 }
 907
 908 static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
 909 {
 910         return (unsigned long)(div_u64(bytes, unit));
 911 }
 912
 913 static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
 914                                    u64 offset)
 915 {
 916         u64 bitmap_start;
 917         u64 bytes_per_bitmap;
 918
 919         bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
 920         bitmap_start = offset - ctl->start;
 921         bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
 922         bitmap_start *= bytes_per_bitmap;
 923         bitmap_start += ctl->start;
 924
 925         return bitmap_start;
 926 }
 927
 928 static int tree_insert_offset(struct rb_root *root, u64 offset,
 929                               struct rb_node *node, int bitmap)
 930 {
 931         struct rb_node **p = &root->rb_node;
 932         struct rb_node *parent = NULL;
 933         struct btrfs_free_space *info;
 934
 935         while (*p) {
 936                 parent = *p;
 937                 info = rb_entry(parent, struct btrfs_free_space, offset_index);
 938
 939                 if (offset < info->offset) {
 940                         p = &(*p)->rb_left;
 941                 } else if (offset > info->offset) {
 942                         p = &(*p)->rb_right;
 943                 } else {
 944                         /*
 945                          * we could have a bitmap entry and an extent entry
 946                          * share the same offset.  If this is the case, we want
 947                          * the extent entry to always be found first if we do a
 948                          * linear search through the tree, since we want to have
 949                          * the quickest allocation time, and allocating from an
 950                          * extent is faster than allocating from a bitmap.  So
 951                          * if we're inserting a bitmap and we find an entry at
 952                          * this offset, we want to go right, or after this entry
 953                          * logically.  If we are inserting an extent and we've
 954                          * found a bitmap, we want to go left, or before
 955                          * logically.
 956                          */
 957                         if (bitmap) {
 958                                 if (info->bitmap) {
 959                                         WARN_ON_ONCE(1);
 960                                         return -EEXIST;
 961                                 }
 962                                 p = &(*p)->rb_right;
 963                         } else {
 964                                 if (!info->bitmap) {
 965                                         WARN_ON_ONCE(1);
 966                                         return -EEXIST;
 967                                 }
 968                                 p = &(*p)->rb_left;
 969                         }
 970                 }
 971         }
 972
 973         rb_link_node(node, parent, p);
 974         rb_insert_color(node, root);
 975
 976         return 0;
 977 }
 978
 979 /*
 980  * searches the tree for the given offset.
 981  *
 982  * fuzzy - If this is set, then we are trying to make an allocation, and we just
 983  * want a section that has at least bytes size and comes at or after the given
 984  * offset.
 985  */
 986 static struct btrfs_free_space *
 987 tree_search_offset(struct btrfs_free_space_ctl *ctl,
 988                    u64 offset, int bitmap_only, int fuzzy)
 989 {
 990         struct rb_node *n = ctl->free_space_offset.rb_node;
 991         struct btrfs_free_space *entry, *prev = NULL;
 992
 993         /* find entry that is closest to the 'offset' */
 994         while (1) {
 995                 if (!n) {
 996                         entry = NULL;
 997                         break;
 998                 }
 999
1000                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1001                 prev = entry;
1002
1003                 if (offset < entry->offset)
1004                         n = n->rb_left;
1005                 else if (offset > entry->offset)
1006                         n = n->rb_right;
1007                 else
1008                         break;
1009         }
1010
1011         if (bitmap_only) {
1012                 if (!entry)
1013                         return NULL;
1014                 if (entry->bitmap)
1015                         return entry;
1016
1017                 /*
1018                  * bitmap entry and extent entry may share same offset,
1019                  * in that case, bitmap entry comes after extent entry.
1020                  */
1021                 n = rb_next(n);
1022                 if (!n)
1023                         return NULL;
1024                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1025                 if (entry->offset != offset)
1026                         return NULL;
1027
1028                 WARN_ON(!entry->bitmap);
1029                 return entry;
1030         } else if (entry) {
1031                 if (entry->bitmap) {
1032                         /*
1033                          * if previous extent entry covers the offset,
1034                          * we should return it instead of the bitmap entry
1035                          */
1036                         n = &entry->offset_index;
1037                         while (1) {
1038                                 n = rb_prev(n);
1039                                 if (!n)
1040                                         break;
1041                                 prev = rb_entry(n, struct btrfs_free_space,
1042                                                 offset_index);
1043                                 if (!prev->bitmap) {
1044                                         if (prev->offset + prev->bytes > offset)
1045                                                 entry = prev;
1046                                         break;
1047                                 }
1048                         }
1049                 }
1050                 return entry;
1051         }
1052
1053         if (!prev)
1054                 return NULL;
1055
1056         /* find last entry before the 'offset' */
1057         entry = prev;
1058         if (entry->offset > offset) {
1059                 n = rb_prev(&entry->offset_index);
1060                 if (n) {
1061                         entry = rb_entry(n, struct btrfs_free_space,
1062                                         offset_index);
1063                         BUG_ON(entry->offset > offset);
1064                 } else {
1065                         if (fuzzy)
1066                                 return entry;
1067                         else
1068                                 return NULL;
1069                 }
1070         }
1071
1072         if (entry->bitmap) {
1073                 n = &entry->offset_index;
1074                 while (1) {
1075                         n = rb_prev(n);
1076                         if (!n)
1077                                 break;
1078                         prev = rb_entry(n, struct btrfs_free_space,
1079                                         offset_index);
1080                         if (!prev->bitmap) {
1081                                 if (prev->offset + prev->bytes > offset)
1082                                         return prev;
1083                                 break;
1084                         }
1085                 }
1086                 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1087                         return entry;
1088         } else if (entry->offset + entry->bytes > offset)
1089                 return entry;
1090
1091         if (!fuzzy)
1092                 return NULL;
1093
1094         while (1) {
1095                 if (entry->bitmap) {
1096                         if (entry->offset + BITS_PER_BITMAP *
1097                             ctl->unit > offset)
1098                                 break;
1099                 } else {
1100                         if (entry->offset + entry->bytes > offset)
1101                                 break;
1102                 }
1103
1104                 n = rb_next(&entry->offset_index);
1105                 if (!n)
1106                         return NULL;
1107                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1108         }
1109         return entry;
1110 }
1111
1112 static inline void
1113 __unlink_free_space(struct btrfs_free_space_ctl *ctl,
1114                     struct btrfs_free_space *info)
1115 {
1116         rb_erase(&info->offset_index, &ctl->free_space_offset);
1117         ctl->free_extents--;
1118 }
1119
1120 static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1121                               struct btrfs_free_space *info)
1122 {
1123         __unlink_free_space(ctl, info);
1124         ctl->free_space -= info->bytes;
1125 }
1126
1127 static int link_free_space(struct btrfs_free_space_ctl *ctl,
1128                            struct btrfs_free_space *info)
1129 {
1130         int ret = 0;
1131
1132         BUG_ON(!info->bitmap && !info->bytes);
1133         ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1134                                  &info->offset_index, (info->bitmap != NULL));
1135         if (ret)
1136                 return ret;
1137
1138         ctl->free_space += info->bytes;
1139         ctl->free_extents++;
1140         return ret;
1141 }
1142
1143 static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1144 {
1145         struct btrfs_block_group_cache *block_group = ctl->private;
1146         u64 max_bytes;
1147         u64 bitmap_bytes;
1148         u64 extent_bytes;
1149         u64 size = block_group->key.offset;
1150         u64 bytes_per_bg = BITS_PER_BITMAP * block_group->sectorsize;
1151         int max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1152
1153         BUG_ON(ctl->total_bitmaps > max_bitmaps);
1154
1155         /*
1156          * The goal is to keep the total amount of memory used per 1gb of space
1157          * at or below 32k, so we need to adjust how much memory we allow to be
1158          * used by extent based free space tracking
1159          */
1160         if (size < 1024 * 1024 * 1024)
1161                 max_bytes = MAX_CACHE_BYTES_PER_GIG;
1162         else
1163                 max_bytes = MAX_CACHE_BYTES_PER_GIG *
1164                         div64_u64(size, 1024 * 1024 * 1024);
1165
1166         /*
1167          * we want to account for 1 more bitmap than what we have so we can make
1168          * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
1169          * we add more bitmaps.
1170          */
1171         bitmap_bytes = (ctl->total_bitmaps + 1) * PAGE_CACHE_SIZE;
1172
1173         if (bitmap_bytes >= max_bytes) {
1174                 ctl->extents_thresh = 0;
1175                 return;
1176         }
1177
1178         /*
1179          * we want the extent entry threshold to always be at most 1/2 the maxw
1180          * bytes we can have, or whatever is less than that.
1181          */
1182         extent_bytes = max_bytes - bitmap_bytes;
1183         extent_bytes = min_t(u64, extent_bytes, div64_u64(max_bytes, 2));
1184
1185         ctl->extents_thresh =
1186                 div64_u64(extent_bytes, (sizeof(struct btrfs_free_space)));
1187 }
1188
1189 static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1190                                        struct btrfs_free_space *info,
1191                                        u64 offset, u64 bytes)
1192 {
1193         unsigned long start, count;
1194
1195         start = offset_to_bit(info->offset, ctl->unit, offset);
1196         count = bytes_to_bits(bytes, ctl->unit);
1197         BUG_ON(start + count > BITS_PER_BITMAP);
1198
1199         bitmap_clear(info->bitmap, start, count);
1200
1201         info->bytes -= bytes;
1202 }
1203
1204 static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1205                               struct btrfs_free_space *info, u64 offset,
1206                               u64 bytes)
1207 {
1208         __bitmap_clear_bits(ctl, info, offset, bytes);
1209         ctl->free_space -= bytes;
1210 }
1211
1212 static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1213                             struct btrfs_free_space *info, u64 offset,
1214                             u64 bytes)
1215 {
1216         unsigned long start, count;
1217
1218         start = offset_to_bit(info->offset, ctl->unit, offset);
1219         count = bytes_to_bits(bytes, ctl->unit);
1220         BUG_ON(start + count > BITS_PER_BITMAP);
1221
1222         bitmap_set(info->bitmap, start, count);
1223
1224         info->bytes += bytes;
1225         ctl->free_space += bytes;
1226 }
1227
1228 static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1229                          struct btrfs_free_space *bitmap_info, u64 *offset,
1230                          u64 *bytes)
1231 {
1232         unsigned long found_bits = 0;
1233         unsigned long bits, i;
1234         unsigned long next_zero;
1235
1236         i = offset_to_bit(bitmap_info->offset, ctl->unit,
1237                           max_t(u64, *offset, bitmap_info->offset));
1238         bits = bytes_to_bits(*bytes, ctl->unit);
1239
1240         for (i = find_next_bit(bitmap_info->bitmap, BITS_PER_BITMAP, i);
1241              i < BITS_PER_BITMAP;
1242              i = find_next_bit(bitmap_info->bitmap, BITS_PER_BITMAP, i + 1)) {
1243                 next_zero = find_next_zero_bit(bitmap_info->bitmap,
1244                                                BITS_PER_BITMAP, i);
1245                 if ((next_zero - i) >= bits) {
1246                         found_bits = next_zero - i;
1247                         break;
1248                 }
1249                 i = next_zero;
1250         }
1251
1252         if (found_bits) {
1253                 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1254                 *bytes = (u64)(found_bits) * ctl->unit;
1255                 return 0;
1256         }
1257
1258         return -1;
1259 }
1260
1261 static struct btrfs_free_space *
1262 find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes)
1263 {
1264         struct btrfs_free_space *entry;
1265         struct rb_node *node;
1266         int ret;
1267
1268         if (!ctl->free_space_offset.rb_node)
1269                 return NULL;
1270
1271         entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1272         if (!entry)
1273                 return NULL;
1274
1275         for (node = &entry->offset_index; node; node = rb_next(node)) {
1276                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1277                 if (entry->bytes < *bytes)
1278                         continue;
1279
1280                 if (entry->bitmap) {
1281                         ret = search_bitmap(ctl, entry, offset, bytes);
1282                         if (!ret)
1283                                 return entry;
1284                         continue;
1285                 }
1286
1287                 *offset = entry->offset;
1288                 *bytes = entry->bytes;
1289                 return entry;
1290         }
1291
1292         return NULL;
1293 }
1294
1295 static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1296                            struct btrfs_free_space *info, u64 offset)
1297 {
1298         info->offset = offset_to_bitmap(ctl, offset);
1299         info->bytes = 0;
1300         link_free_space(ctl, info);
1301         ctl->total_bitmaps++;
1302
1303         ctl->op->recalc_thresholds(ctl);
1304 }
1305
1306 static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1307                         struct btrfs_free_space *bitmap_info)
1308 {
1309         unlink_free_space(ctl, bitmap_info);
1310         kfree(bitmap_info->bitmap);
1311         kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1312         ctl->total_bitmaps--;
1313         ctl->op->recalc_thresholds(ctl);
1314 }
1315
1316 static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1317                               struct btrfs_free_space *bitmap_info,
1318                               u64 *offset, u64 *bytes)
1319 {
1320         u64 end;
1321         u64 search_start, search_bytes;
1322         int ret;
1323
1324 again:
1325         end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
1326
1327         /*
1328          * XXX - this can go away after a few releases.
1329          *
1330          * since the only user of btrfs_remove_free_space is the tree logging
1331          * stuff, and the only way to test that is under crash conditions, we
1332          * want to have this debug stuff here just in case somethings not
1333          * working.  Search the bitmap for the space we are trying to use to
1334          * make sure its actually there.  If its not there then we need to stop
1335          * because something has gone wrong.
1336          */
1337         search_start = *offset;
1338         search_bytes = *bytes;
1339         search_bytes = min(search_bytes, end - search_start + 1);
1340         ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes);
1341         BUG_ON(ret < 0 || search_start != *offset);
1342
1343         if (*offset > bitmap_info->offset && *offset + *bytes > end) {
1344                 bitmap_clear_bits(ctl, bitmap_info, *offset, end - *offset + 1);
1345                 *bytes -= end - *offset + 1;
1346                 *offset = end + 1;
1347         } else if (*offset >= bitmap_info->offset && *offset + *bytes <= end) {
1348                 bitmap_clear_bits(ctl, bitmap_info, *offset, *bytes);
1349                 *bytes = 0;
1350         }
1351
1352         if (*bytes) {
1353                 struct rb_node *next = rb_next(&bitmap_info->offset_index);
1354                 if (!bitmap_info->bytes)
1355                         free_bitmap(ctl, bitmap_info);
1356
1357                 /*
1358                  * no entry after this bitmap, but we still have bytes to
1359                  * remove, so something has gone wrong.
1360                  */
1361                 if (!next)
1362                         return -EINVAL;
1363
1364                 bitmap_info = rb_entry(next, struct btrfs_free_space,
1365                                        offset_index);
1366
1367                 /*
1368                  * if the next entry isn't a bitmap we need to return to let the
1369                  * extent stuff do its work.
1370                  */
1371                 if (!bitmap_info->bitmap)
1372                         return -EAGAIN;
1373
1374                 /*
1375                  * Ok the next item is a bitmap, but it may not actually hold
1376                  * the information for the rest of this free space stuff, so
1377                  * look for it, and if we don't find it return so we can try
1378                  * everything over again.
1379                  */
1380                 search_start = *offset;
1381                 search_bytes = *bytes;
1382                 ret = search_bitmap(ctl, bitmap_info, &search_start,
1383                                     &search_bytes);
1384                 if (ret < 0 || search_start != *offset)
1385                         return -EAGAIN;
1386
1387                 goto again;
1388         } else if (!bitmap_info->bytes)
1389                 free_bitmap(ctl, bitmap_info);
1390
1391         return 0;
1392 }
1393
1394 static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
1395                                struct btrfs_free_space *info, u64 offset,
1396                                u64 bytes)
1397 {
1398         u64 bytes_to_set = 0;
1399         u64 end;
1400
1401         end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
1402
1403         bytes_to_set = min(end - offset, bytes);
1404
1405         bitmap_set_bits(ctl, info, offset, bytes_to_set);
1406
1407         return bytes_to_set;
1408
1409 }
1410
1411 static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
1412                       struct btrfs_free_space *info)
1413 {
1414         struct btrfs_block_group_cache *block_group = ctl->private;
1415
1416         /*
1417          * If we are below the extents threshold then we can add this as an
1418          * extent, and don't have to deal with the bitmap
1419          */
1420         if (ctl->free_extents < ctl->extents_thresh) {
1421                 /*
1422                  * If this block group has some small extents we don't want to
1423                  * use up all of our free slots in the cache with them, we want
1424                  * to reserve them to larger extents, however if we have plent
1425                  * of cache left then go ahead an dadd them, no sense in adding
1426                  * the overhead of a bitmap if we don't have to.
1427                  */
1428                 if (info->bytes <= block_group->sectorsize * 4) {
1429                         if (ctl->free_extents * 2 <= ctl->extents_thresh)
1430                                 return false;
1431                 } else {
1432                         return false;
1433                 }
1434         }
1435
1436         /*
1437          * some block groups are so tiny they can't be enveloped by a bitmap, so
1438          * don't even bother to create a bitmap for this
1439          */
1440         if (BITS_PER_BITMAP * block_group->sectorsize >
1441             block_group->key.offset)
1442                 return false;
1443
1444         return true;
1445 }
1446
1447 static struct btrfs_free_space_op free_space_op = {
1448         .recalc_thresholds      = recalculate_thresholds,
1449         .use_bitmap             = use_bitmap,
1450 };
1451
1452 static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
1453                               struct btrfs_free_space *info)
1454 {
1455         struct btrfs_free_space *bitmap_info;
1456         struct btrfs_block_group_cache *block_group = NULL;
1457         int added = 0;
1458         u64 bytes, offset, bytes_added;
1459         int ret;
1460
1461         bytes = info->bytes;
1462         offset = info->offset;
1463
1464         if (!ctl->op->use_bitmap(ctl, info))
1465                 return 0;
1466
1467         if (ctl->op == &free_space_op)
1468                 block_group = ctl->private;
1469 again:
1470         /*
1471          * Since we link bitmaps right into the cluster we need to see if we
1472          * have a cluster here, and if so and it has our bitmap we need to add
1473          * the free space to that bitmap.
1474          */
1475         if (block_group && !list_empty(&block_group->cluster_list)) {
1476                 struct btrfs_free_cluster *cluster;
1477                 struct rb_node *node;
1478                 struct btrfs_free_space *entry;
1479
1480                 cluster = list_entry(block_group->cluster_list.next,
1481                                      struct btrfs_free_cluster,
1482                                      block_group_list);
1483                 spin_lock(&cluster->lock);
1484                 node = rb_first(&cluster->root);
1485                 if (!node) {
1486                         spin_unlock(&cluster->lock);
1487                         goto no_cluster_bitmap;
1488                 }
1489
1490                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1491                 if (!entry->bitmap) {
1492                         spin_unlock(&cluster->lock);
1493                         goto no_cluster_bitmap;
1494                 }
1495
1496                 if (entry->offset == offset_to_bitmap(ctl, offset)) {
1497                         bytes_added = add_bytes_to_bitmap(ctl, entry,
1498                                                           offset, bytes);
1499                         bytes -= bytes_added;
1500                         offset += bytes_added;
1501                 }
1502                 spin_unlock(&cluster->lock);
1503                 if (!bytes) {
1504                         ret = 1;
1505                         goto out;
1506                 }
1507         }
1508
1509 no_cluster_bitmap:
1510         bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1511                                          1, 0);
1512         if (!bitmap_info) {
1513                 BUG_ON(added);
1514                 goto new_bitmap;
1515         }
1516
1517         bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
1518         bytes -= bytes_added;
1519         offset += bytes_added;
1520         added = 0;
1521
1522         if (!bytes) {
1523                 ret = 1;
1524                 goto out;
1525         } else
1526                 goto again;
1527
1528 new_bitmap:
1529         if (info && info->bitmap) {
1530                 add_new_bitmap(ctl, info, offset);
1531                 added = 1;
1532                 info = NULL;
1533                 goto again;
1534         } else {
1535                 spin_unlock(&ctl->tree_lock);
1536
1537                 /* no pre-allocated info, allocate a new one */
1538                 if (!info) {
1539                         info = kmem_cache_zalloc(btrfs_free_space_cachep,
1540                                                  GFP_NOFS);
1541                         if (!info) {
1542                                 spin_lock(&ctl->tree_lock);
1543                                 ret = -ENOMEM;
1544                                 goto out;
1545                         }
1546                 }
1547
1548                 /* allocate the bitmap */
1549                 info->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
1550                 spin_lock(&ctl->tree_lock);
1551                 if (!info->bitmap) {
1552                         ret = -ENOMEM;
1553                         goto out;
1554                 }
1555                 goto again;
1556         }
1557
1558 out:
1559         if (info) {
1560                 if (info->bitmap)
1561                         kfree(info->bitmap);
1562                 kmem_cache_free(btrfs_free_space_cachep, info);
1563         }
1564
1565         return ret;
1566 }
1567
1568 static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
1569                           struct btrfs_free_space *info, bool update_stat)
1570 {
1571         struct btrfs_free_space *left_info;
1572         struct btrfs_free_space *right_info;
1573         bool merged = false;
1574         u64 offset = info->offset;
1575         u64 bytes = info->bytes;
1576
1577         /*
1578          * first we want to see if there is free space adjacent to the range we
1579          * are adding, if there is remove that struct and add a new one to
1580          * cover the entire range
1581          */
1582         right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
1583         if (right_info && rb_prev(&right_info->offset_index))
1584                 left_info = rb_entry(rb_prev(&right_info->offset_index),
1585                                      struct btrfs_free_space, offset_index);
1586         else
1587                 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
1588
1589         if (right_info && !right_info->bitmap) {
1590                 if (update_stat)
1591                         unlink_free_space(ctl, right_info);
1592                 else
1593                         __unlink_free_space(ctl, right_info);
1594                 info->bytes += right_info->bytes;
1595                 kmem_cache_free(btrfs_free_space_cachep, right_info);
1596                 merged = true;
1597         }
1598
1599         if (left_info && !left_info->bitmap &&
1600             left_info->offset + left_info->bytes == offset) {
1601                 if (update_stat)
1602                         unlink_free_space(ctl, left_info);
1603                 else
1604                         __unlink_free_space(ctl, left_info);
1605                 info->offset = left_info->offset;
1606                 info->bytes += left_info->bytes;
1607                 kmem_cache_free(btrfs_free_space_cachep, left_info);
1608                 merged = true;
1609         }
1610
1611         return merged;
1612 }
1613
1614 int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl,
1615                            u64 offset, u64 bytes)
1616 {
1617         struct btrfs_free_space *info;
1618         int ret = 0;
1619
1620         info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
1621         if (!info)
1622                 return -ENOMEM;
1623
1624         info->offset = offset;
1625         info->bytes = bytes;
1626
1627         spin_lock(&ctl->tree_lock);
1628
1629         if (try_merge_free_space(ctl, info, true))
1630                 goto link;
1631
1632         /*
1633          * There was no extent directly to the left or right of this new
1634          * extent then we know we're going to have to allocate a new extent, so
1635          * before we do that see if we need to drop this into a bitmap
1636          */
1637         ret = insert_into_bitmap(ctl, info);
1638         if (ret < 0) {
1639                 goto out;
1640         } else if (ret) {
1641                 ret = 0;
1642                 goto out;
1643         }
1644 link:
1645         ret = link_free_space(ctl, info);
1646         if (ret)
1647                 kmem_cache_free(btrfs_free_space_cachep, info);
1648 out:
1649         spin_unlock(&ctl->tree_lock);
1650
1651         if (ret) {
1652                 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
1653                 BUG_ON(ret == -EEXIST);
1654         }
1655
1656         return ret;
1657 }
1658
1659 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
1660                             u64 offset, u64 bytes)
1661 {
1662         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1663         struct btrfs_free_space *info;
1664         struct btrfs_free_space *next_info = NULL;
1665         int ret = 0;
1666
1667         spin_lock(&ctl->tree_lock);
1668
1669 again:
1670         info = tree_search_offset(ctl, offset, 0, 0);
1671         if (!info) {
1672                 /*
1673                  * oops didn't find an extent that matched the space we wanted
1674                  * to remove, look for a bitmap instead
1675                  */
1676                 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1677                                           1, 0);
1678                 if (!info) {
1679                         WARN_ON(1);
1680                         goto out_lock;
1681                 }
1682         }
1683
1684         if (info->bytes < bytes && rb_next(&info->offset_index)) {
1685                 u64 end;
1686                 next_info = rb_entry(rb_next(&info->offset_index),
1687                                              struct btrfs_free_space,
1688                                              offset_index);
1689
1690                 if (next_info->bitmap)
1691                         end = next_info->offset +
1692                               BITS_PER_BITMAP * ctl->unit - 1;
1693                 else
1694                         end = next_info->offset + next_info->bytes;
1695
1696                 if (next_info->bytes < bytes ||
1697                     next_info->offset > offset || offset > end) {
1698                         printk(KERN_CRIT "Found free space at %llu, size %llu,"
1699                               " trying to use %llu\n",
1700                               (unsigned long long)info->offset,
1701                               (unsigned long long)info->bytes,
1702                               (unsigned long long)bytes);
1703                         WARN_ON(1);
1704                         ret = -EINVAL;
1705                         goto out_lock;
1706                 }
1707
1708                 info = next_info;
1709         }
1710
1711         if (info->bytes == bytes) {
1712                 unlink_free_space(ctl, info);
1713                 if (info->bitmap) {
1714                         kfree(info->bitmap);
1715                         ctl->total_bitmaps--;
1716                 }
1717                 kmem_cache_free(btrfs_free_space_cachep, info);
1718                 goto out_lock;
1719         }
1720
1721         if (!info->bitmap && info->offset == offset) {
1722                 unlink_free_space(ctl, info);
1723                 info->offset += bytes;
1724                 info->bytes -= bytes;
1725                 link_free_space(ctl, info);
1726                 goto out_lock;
1727         }
1728
1729         if (!info->bitmap && info->offset <= offset &&
1730             info->offset + info->bytes >= offset + bytes) {
1731                 u64 old_start = info->offset;
1732                 /*
1733                  * we're freeing space in the middle of the info,
1734                  * this can happen during tree log replay
1735                  *
1736                  * first unlink the old info and then
1737                  * insert it again after the hole we're creating
1738                  */
1739                 unlink_free_space(ctl, info);
1740                 if (offset + bytes < info->offset + info->bytes) {
1741                         u64 old_end = info->offset + info->bytes;
1742
1743                         info->offset = offset + bytes;
1744                         info->bytes = old_end - info->offset;
1745                         ret = link_free_space(ctl, info);
1746                         WARN_ON(ret);
1747                         if (ret)
1748                                 goto out_lock;
1749                 } else {
1750                         /* the hole we're creating ends at the end
1751                          * of the info struct, just free the info
1752                          */
1753                         kmem_cache_free(btrfs_free_space_cachep, info);
1754                 }
1755                 spin_unlock(&ctl->tree_lock);
1756
1757                 /* step two, insert a new info struct to cover
1758                  * anything before the hole
1759                  */
1760                 ret = btrfs_add_free_space(block_group, old_start,
1761                                            offset - old_start);
1762                 WARN_ON(ret);
1763                 goto out;
1764         }
1765
1766         ret = remove_from_bitmap(ctl, info, &offset, &bytes);
1767         if (ret == -EAGAIN)
1768                 goto again;
1769         BUG_ON(ret);
1770 out_lock:
1771         spin_unlock(&ctl->tree_lock);
1772 out:
1773         return ret;
1774 }
1775
1776 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
1777                            u64 bytes)
1778 {
1779         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1780         struct btrfs_free_space *info;
1781         struct rb_node *n;
1782         int count = 0;
1783
1784         for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
1785                 info = rb_entry(n, struct btrfs_free_space, offset_index);
1786                 if (info->bytes >= bytes)
1787                         count++;
1788                 printk(KERN_CRIT "entry offset %llu, bytes %llu, bitmap %s\n",
1789                        (unsigned long long)info->offset,
1790                        (unsigned long long)info->bytes,
1791                        (info->bitmap) ? "yes" : "no");
1792         }
1793         printk(KERN_INFO "block group has cluster?: %s\n",
1794                list_empty(&block_group->cluster_list) ? "no" : "yes");
1795         printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
1796                "\n", count);
1797 }
1798
1799 void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
1800 {
1801         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1802
1803         spin_lock_init(&ctl->tree_lock);
1804         ctl->unit = block_group->sectorsize;
1805         ctl->start = block_group->key.objectid;
1806         ctl->private = block_group;
1807         ctl->op = &free_space_op;
1808
1809         /*
1810          * we only want to have 32k of ram per block group for keeping
1811          * track of free space, and if we pass 1/2 of that we want to
1812          * start converting things over to using bitmaps
1813          */
1814         ctl->extents_thresh = ((1024 * 32) / 2) /
1815                                 sizeof(struct btrfs_free_space);
1816 }
1817
1818 /*
1819  * for a given cluster, put all of its extents back into the free
1820  * space cache.  If the block group passed doesn't match the block group
1821  * pointed to by the cluster, someone else raced in and freed the
1822  * cluster already.  In that case, we just return without changing anything
1823  */
1824 static int
1825 __btrfs_return_cluster_to_free_space(
1826                              struct btrfs_block_group_cache *block_group,
1827                              struct btrfs_free_cluster *cluster)
1828 {
1829         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1830         struct btrfs_free_space *entry;
1831         struct rb_node *node;
1832
1833         spin_lock(&cluster->lock);
1834         if (cluster->block_group != block_group)
1835                 goto out;
1836
1837         cluster->block_group = NULL;
1838         cluster->window_start = 0;
1839         list_del_init(&cluster->block_group_list);
1840
1841         node = rb_first(&cluster->root);
1842         while (node) {
1843                 bool bitmap;
1844
1845                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1846                 node = rb_next(&entry->offset_index);
1847                 rb_erase(&entry->offset_index, &cluster->root);
1848
1849                 bitmap = (entry->bitmap != NULL);
1850                 if (!bitmap)
1851                         try_merge_free_space(ctl, entry, false);
1852                 tree_insert_offset(&ctl->free_space_offset,
1853                                    entry->offset, &entry->offset_index, bitmap);
1854         }
1855         cluster->root = RB_ROOT;
1856
1857 out:
1858         spin_unlock(&cluster->lock);
1859         btrfs_put_block_group(block_group);
1860         return 0;
1861 }
1862
1863 void __btrfs_remove_free_space_cache_locked(struct btrfs_free_space_ctl *ctl)
1864 {
1865         struct btrfs_free_space *info;
1866         struct rb_node *node;
1867
1868         while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
1869                 info = rb_entry(node, struct btrfs_free_space, offset_index);
1870                 if (!info->bitmap) {
1871                         unlink_free_space(ctl, info);
1872                         kmem_cache_free(btrfs_free_space_cachep, info);
1873                 } else {
1874                         free_bitmap(ctl, info);
1875                 }
1876                 if (need_resched()) {
1877                         spin_unlock(&ctl->tree_lock);
1878                         cond_resched();
1879                         spin_lock(&ctl->tree_lock);
1880                 }
1881         }
1882 }
1883
1884 void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
1885 {
1886         spin_lock(&ctl->tree_lock);
1887         __btrfs_remove_free_space_cache_locked(ctl);
1888         spin_unlock(&ctl->tree_lock);
1889 }
1890
1891 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
1892 {
1893         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1894         struct btrfs_free_cluster *cluster;
1895         struct list_head *head;
1896
1897         spin_lock(&ctl->tree_lock);
1898         while ((head = block_group->cluster_list.next) !=
1899                &block_group->cluster_list) {
1900                 cluster = list_entry(head, struct btrfs_free_cluster,
1901                                      block_group_list);
1902
1903                 WARN_ON(cluster->block_group != block_group);
1904                 __btrfs_return_cluster_to_free_space(block_group, cluster);
1905                 if (need_resched()) {
1906                         spin_unlock(&ctl->tree_lock);
1907                         cond_resched();
1908                         spin_lock(&ctl->tree_lock);
1909                 }
1910         }
1911         __btrfs_remove_free_space_cache_locked(ctl);
1912         spin_unlock(&ctl->tree_lock);
1913
1914 }
1915
1916 u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
1917                                u64 offset, u64 bytes, u64 empty_size)
1918 {
1919         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1920         struct btrfs_free_space *entry = NULL;
1921         u64 bytes_search = bytes + empty_size;
1922         u64 ret = 0;
1923
1924         spin_lock(&ctl->tree_lock);
1925         entry = find_free_space(ctl, &offset, &bytes_search);
1926         if (!entry)
1927                 goto out;
1928
1929         ret = offset;
1930         if (entry->bitmap) {
1931                 bitmap_clear_bits(ctl, entry, offset, bytes);
1932                 if (!entry->bytes)
1933                         free_bitmap(ctl, entry);
1934         } else {
1935                 unlink_free_space(ctl, entry);
1936                 entry->offset += bytes;
1937                 entry->bytes -= bytes;
1938                 if (!entry->bytes)
1939                         kmem_cache_free(btrfs_free_space_cachep, entry);
1940                 else
1941                         link_free_space(ctl, entry);
1942         }
1943
1944 out:
1945         spin_unlock(&ctl->tree_lock);
1946
1947         return ret;
1948 }
1949
1950 /*
1951  * given a cluster, put all of its extents back into the free space
1952  * cache.  If a block group is passed, this function will only free
1953  * a cluster that belongs to the passed block group.
1954  *
1955  * Otherwise, it'll get a reference on the block group pointed to by the
1956  * cluster and remove the cluster from it.
1957  */
1958 int btrfs_return_cluster_to_free_space(
1959                                struct btrfs_block_group_cache *block_group,
1960                                struct btrfs_free_cluster *cluster)
1961 {
1962         struct btrfs_free_space_ctl *ctl;
1963         int ret;
1964
1965         /* first, get a safe pointer to the block group */
1966         spin_lock(&cluster->lock);
1967         if (!block_group) {
1968                 block_group = cluster->block_group;
1969                 if (!block_group) {
1970                         spin_unlock(&cluster->lock);
1971                         return 0;
1972                 }
1973         } else if (cluster->block_group != block_group) {
1974                 /* someone else has already freed it don't redo their work */
1975                 spin_unlock(&cluster->lock);
1976                 return 0;
1977         }
1978         atomic_inc(&block_group->count);
1979         spin_unlock(&cluster->lock);
1980
1981         ctl = block_group->free_space_ctl;
1982
1983         /* now return any extents the cluster had on it */
1984         spin_lock(&ctl->tree_lock);
1985         ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
1986         spin_unlock(&ctl->tree_lock);
1987
1988         /* finally drop our ref */
1989         btrfs_put_block_group(block_group);
1990         return ret;
1991 }
1992
1993 static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
1994                                    struct btrfs_free_cluster *cluster,
1995                                    struct btrfs_free_space *entry,
1996                                    u64 bytes, u64 min_start)
1997 {
1998         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1999         int err;
2000         u64 search_start = cluster->window_start;
2001         u64 search_bytes = bytes;
2002         u64 ret = 0;
2003
2004         search_start = min_start;
2005         search_bytes = bytes;
2006
2007         err = search_bitmap(ctl, entry, &search_start, &search_bytes);
2008         if (err)
2009                 return 0;
2010
2011         ret = search_start;
2012         __bitmap_clear_bits(ctl, entry, ret, bytes);
2013
2014         return ret;
2015 }
2016
2017 /*
2018  * given a cluster, try to allocate 'bytes' from it, returns 0
2019  * if it couldn't find anything suitably large, or a logical disk offset
2020  * if things worked out
2021  */
2022 u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
2023                              struct btrfs_free_cluster *cluster, u64 bytes,
2024                              u64 min_start)
2025 {
2026         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2027         struct btrfs_free_space *entry = NULL;
2028         struct rb_node *node;
2029         u64 ret = 0;
2030
2031         spin_lock(&cluster->lock);
2032         if (bytes > cluster->max_size)
2033                 goto out;
2034
2035         if (cluster->block_group != block_group)
2036                 goto out;
2037
2038         node = rb_first(&cluster->root);
2039         if (!node)
2040                 goto out;
2041
2042         entry = rb_entry(node, struct btrfs_free_space, offset_index);
2043         while(1) {
2044                 if (entry->bytes < bytes ||
2045                     (!entry->bitmap && entry->offset < min_start)) {
2046                         node = rb_next(&entry->offset_index);
2047                         if (!node)
2048                                 break;
2049                         entry = rb_entry(node, struct btrfs_free_space,
2050                                          offset_index);
2051                         continue;
2052                 }
2053
2054                 if (entry->bitmap) {
2055                         ret = btrfs_alloc_from_bitmap(block_group,
2056                                                       cluster, entry, bytes,
2057                                                       min_start);
2058                         if (ret == 0) {
2059                                 node = rb_next(&entry->offset_index);
2060                                 if (!node)
2061                                         break;
2062                                 entry = rb_entry(node, struct btrfs_free_space,
2063                                                  offset_index);
2064                                 continue;
2065                         }
2066                 } else {
2067                         ret = entry->offset;
2068
2069                         entry->offset += bytes;
2070                         entry->bytes -= bytes;
2071                 }
2072
2073                 if (entry->bytes == 0)
2074                         rb_erase(&entry->offset_index, &cluster->root);
2075                 break;
2076         }
2077 out:
2078         spin_unlock(&cluster->lock);
2079
2080         if (!ret)
2081                 return 0;
2082
2083         spin_lock(&ctl->tree_lock);
2084
2085         ctl->free_space -= bytes;
2086         if (entry->bytes == 0) {
2087                 ctl->free_extents--;
2088                 if (entry->bitmap) {
2089                         kfree(entry->bitmap);
2090                         ctl->total_bitmaps--;
2091                         ctl->op->recalc_thresholds(ctl);
2092                 }
2093                 kmem_cache_free(btrfs_free_space_cachep, entry);
2094         }
2095
2096         spin_unlock(&ctl->tree_lock);
2097
2098         return ret;
2099 }
2100
2101 static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
2102                                 struct btrfs_free_space *entry,
2103                                 struct btrfs_free_cluster *cluster,
2104                                 u64 offset, u64 bytes, u64 min_bytes)
2105 {
2106         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2107         unsigned long next_zero;
2108         unsigned long i;
2109         unsigned long search_bits;
2110         unsigned long total_bits;
2111         unsigned long found_bits;
2112         unsigned long start = 0;
2113         unsigned long total_found = 0;
2114         int ret;
2115         bool found = false;
2116
2117         i = offset_to_bit(entry->offset, block_group->sectorsize,
2118                           max_t(u64, offset, entry->offset));
2119         search_bits = bytes_to_bits(bytes, block_group->sectorsize);
2120         total_bits = bytes_to_bits(min_bytes, block_group->sectorsize);
2121
2122 again:
2123         found_bits = 0;
2124         for (i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i);
2125              i < BITS_PER_BITMAP;
2126              i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, i + 1)) {
2127                 next_zero = find_next_zero_bit(entry->bitmap,
2128                                                BITS_PER_BITMAP, i);
2129                 if (next_zero - i >= search_bits) {
2130                         found_bits = next_zero - i;
2131                         break;
2132                 }
2133                 i = next_zero;
2134         }
2135
2136         if (!found_bits)
2137                 return -ENOSPC;
2138
2139         if (!found) {
2140                 start = i;
2141                 found = true;
2142         }
2143
2144         total_found += found_bits;
2145
2146         if (cluster->max_size < found_bits * block_group->sectorsize)
2147                 cluster->max_size = found_bits * block_group->sectorsize;
2148
2149         if (total_found < total_bits) {
2150                 i = find_next_bit(entry->bitmap, BITS_PER_BITMAP, next_zero);
2151                 if (i - start > total_bits * 2) {
2152                         total_found = 0;
2153                         cluster->max_size = 0;
2154                         found = false;
2155                 }
2156                 goto again;
2157         }
2158
2159         cluster->window_start = start * block_group->sectorsize +
2160                 entry->offset;
2161         rb_erase(&entry->offset_index, &ctl->free_space_offset);
2162         ret = tree_insert_offset(&cluster->root, entry->offset,
2163                                  &entry->offset_index, 1);
2164         BUG_ON(ret);
2165
2166         return 0;
2167 }
2168
2169 /*
2170  * This searches the block group for just extents to fill the cluster with.
2171  */
2172 static noinline int
2173 setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
2174                         struct btrfs_free_cluster *cluster,
2175                         struct list_head *bitmaps, u64 offset, u64 bytes,
2176                         u64 min_bytes)
2177 {
2178         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2179         struct btrfs_free_space *first = NULL;
2180         struct btrfs_free_space *entry = NULL;
2181         struct btrfs_free_space *prev = NULL;
2182         struct btrfs_free_space *last;
2183         struct rb_node *node;
2184         u64 window_start;
2185         u64 window_free;
2186         u64 max_extent;
2187         u64 max_gap = 128 * 1024;
2188
2189         entry = tree_search_offset(ctl, offset, 0, 1);
2190         if (!entry)
2191                 return -ENOSPC;
2192
2193         /*
2194          * We don't want bitmaps, so just move along until we find a normal
2195          * extent entry.
2196          */
2197         while (entry->bitmap) {
2198                 if (list_empty(&entry->list))
2199                         list_add_tail(&entry->list, bitmaps);
2200                 node = rb_next(&entry->offset_index);
2201                 if (!node)
2202                         return -ENOSPC;
2203                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2204         }
2205
2206         window_start = entry->offset;
2207         window_free = entry->bytes;
2208         max_extent = entry->bytes;
2209         first = entry;
2210         last = entry;
2211         prev = entry;
2212
2213         while (window_free <= min_bytes) {
2214                 node = rb_next(&entry->offset_index);
2215                 if (!node)
2216                         return -ENOSPC;
2217                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2218
2219                 if (entry->bitmap) {
2220                         if (list_empty(&entry->list))
2221                                 list_add_tail(&entry->list, bitmaps);
2222                         continue;
2223                 }
2224
2225                 /*
2226                  * we haven't filled the empty size and the window is
2227                  * very large.  reset and try again
2228                  */
2229                 if (entry->offset - (prev->offset + prev->bytes) > max_gap ||
2230                     entry->offset - window_start > (min_bytes * 2)) {
2231                         first = entry;
2232                         window_start = entry->offset;
2233                         window_free = entry->bytes;
2234                         last = entry;
2235                         max_extent = entry->bytes;
2236                 } else {
2237                         last = entry;
2238                         window_free += entry->bytes;
2239                         if (entry->bytes > max_extent)
2240                                 max_extent = entry->bytes;
2241                 }
2242                 prev = entry;
2243         }
2244
2245         cluster->window_start = first->offset;
2246
2247         node = &first->offset_index;
2248
2249         /*
2250          * now we've found our entries, pull them out of the free space
2251          * cache and put them into the cluster rbtree
2252          */
2253         do {
2254                 int ret;
2255
2256                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2257                 node = rb_next(&entry->offset_index);
2258                 if (entry->bitmap)
2259                         continue;
2260
2261                 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2262                 ret = tree_insert_offset(&cluster->root, entry->offset,
2263                                          &entry->offset_index, 0);
2264                 BUG_ON(ret);
2265         } while (node && entry != last);
2266
2267         cluster->max_size = max_extent;
2268
2269         return 0;
2270 }
2271
2272 /*
2273  * This specifically looks for bitmaps that may work in the cluster, we assume
2274  * that we have already failed to find extents that will work.
2275  */
2276 static noinline int
2277 setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
2278                      struct btrfs_free_cluster *cluster,
2279                      struct list_head *bitmaps, u64 offset, u64 bytes,
2280                      u64 min_bytes)
2281 {
2282         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2283         struct btrfs_free_space *entry;
2284         struct rb_node *node;
2285         int ret = -ENOSPC;
2286
2287         if (ctl->total_bitmaps == 0)
2288                 return -ENOSPC;
2289
2290         /*
2291          * First check our cached list of bitmaps and see if there is an entry
2292          * here that will work.
2293          */
2294         list_for_each_entry(entry, bitmaps, list) {
2295                 if (entry->bytes < min_bytes)
2296                         continue;
2297                 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2298                                            bytes, min_bytes);
2299                 if (!ret)
2300                         return 0;
2301         }
2302
2303         /*
2304          * If we do have entries on our list and we are here then we didn't find
2305          * anything, so go ahead and get the next entry after the last entry in
2306          * this list and start the search from there.
2307          */
2308         if (!list_empty(bitmaps)) {
2309                 entry = list_entry(bitmaps->prev, struct btrfs_free_space,
2310                                    list);
2311                 node = rb_next(&entry->offset_index);
2312                 if (!node)
2313                         return -ENOSPC;
2314                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2315                 goto search;
2316         }
2317
2318         entry = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 0, 1);
2319         if (!entry)
2320                 return -ENOSPC;
2321
2322 search:
2323         node = &entry->offset_index;
2324         do {
2325                 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2326                 node = rb_next(&entry->offset_index);
2327                 if (!entry->bitmap)
2328                         continue;
2329                 if (entry->bytes < min_bytes)
2330                         continue;
2331                 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
2332                                            bytes, min_bytes);
2333         } while (ret && node);
2334
2335         return ret;
2336 }
2337
2338 /*
2339  * here we try to find a cluster of blocks in a block group.  The goal
2340  * is to find at least bytes free and up to empty_size + bytes free.
2341  * We might not find them all in one contiguous area.
2342  *
2343  * returns zero and sets up cluster if things worked out, otherwise
2344  * it returns -enospc
2345  */
2346 int btrfs_find_space_cluster(struct btrfs_trans_handle *trans,
2347                              struct btrfs_root *root,
2348                              struct btrfs_block_group_cache *block_group,
2349                              struct btrfs_free_cluster *cluster,
2350                              u64 offset, u64 bytes, u64 empty_size)
2351 {
2352         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2353         struct list_head bitmaps;
2354         struct btrfs_free_space *entry, *tmp;
2355         u64 min_bytes;
2356         int ret;
2357
2358         /* for metadata, allow allocates with more holes */
2359         if (btrfs_test_opt(root, SSD_SPREAD)) {
2360                 min_bytes = bytes + empty_size;
2361         } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
2362                 /*
2363                  * we want to do larger allocations when we are
2364                  * flushing out the delayed refs, it helps prevent
2365                  * making more work as we go along.
2366                  */
2367                 if (trans->transaction->delayed_refs.flushing)
2368                         min_bytes = max(bytes, (bytes + empty_size) >> 1);
2369                 else
2370                         min_bytes = max(bytes, (bytes + empty_size) >> 4);
2371         } else
2372                 min_bytes = max(bytes, (bytes + empty_size) >> 2);
2373
2374         spin_lock(&ctl->tree_lock);
2375
2376         /*
2377          * If we know we don't have enough space to make a cluster don't even
2378          * bother doing all the work to try and find one.
2379          */
2380         if (ctl->free_space < min_bytes) {
2381                 spin_unlock(&ctl->tree_lock);
2382                 return -ENOSPC;
2383         }
2384
2385         spin_lock(&cluster->lock);
2386
2387         /* someone already found a cluster, hooray */
2388         if (cluster->block_group) {
2389                 ret = 0;
2390                 goto out;
2391         }
2392
2393         INIT_LIST_HEAD(&bitmaps);
2394         ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
2395                                       bytes, min_bytes);
2396         if (ret)
2397                 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
2398                                            offset, bytes, min_bytes);
2399
2400         /* Clear our temporary list */
2401         list_for_each_entry_safe(entry, tmp, &bitmaps, list)
2402                 list_del_init(&entry->list);
2403
2404         if (!ret) {
2405                 atomic_inc(&block_group->count);
2406                 list_add_tail(&cluster->block_group_list,
2407                               &block_group->cluster_list);
2408                 cluster->block_group = block_group;
2409         }
2410 out:
2411         spin_unlock(&cluster->lock);
2412         spin_unlock(&ctl->tree_lock);
2413
2414         return ret;
2415 }
2416
2417 /*
2418  * simple code to zero out a cluster
2419  */
2420 void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
2421 {
2422         spin_lock_init(&cluster->lock);
2423         spin_lock_init(&cluster->refill_lock);
2424         cluster->root = RB_ROOT;
2425         cluster->max_size = 0;
2426         INIT_LIST_HEAD(&cluster->block_group_list);
2427         cluster->block_group = NULL;
2428 }
2429
2430 int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
2431                            u64 *trimmed, u64 start, u64 end, u64 minlen)
2432 {
2433         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2434         struct btrfs_free_space *entry = NULL;
2435         struct btrfs_fs_info *fs_info = block_group->fs_info;
2436         u64 bytes = 0;
2437         u64 actually_trimmed;
2438         int ret = 0;
2439
2440         *trimmed = 0;
2441
2442         while (start < end) {
2443                 spin_lock(&ctl->tree_lock);
2444
2445                 if (ctl->free_space < minlen) {
2446                         spin_unlock(&ctl->tree_lock);
2447                         break;
2448                 }
2449
2450                 entry = tree_search_offset(ctl, start, 0, 1);
2451                 if (!entry)
2452                         entry = tree_search_offset(ctl,
2453                                                    offset_to_bitmap(ctl, start),
2454                                                    1, 1);
2455
2456                 if (!entry || entry->offset >= end) {
2457                         spin_unlock(&ctl->tree_lock);
2458                         break;
2459                 }
2460
2461                 if (entry->bitmap) {
2462                         ret = search_bitmap(ctl, entry, &start, &bytes);
2463                         if (!ret) {
2464                                 if (start >= end) {
2465                                         spin_unlock(&ctl->tree_lock);
2466                                         break;
2467                                 }
2468                                 bytes = min(bytes, end - start);
2469                                 bitmap_clear_bits(ctl, entry, start, bytes);
2470                                 if (entry->bytes == 0)
2471                                         free_bitmap(ctl, entry);
2472                         } else {
2473                                 start = entry->offset + BITS_PER_BITMAP *
2474                                         block_group->sectorsize;
2475                                 spin_unlock(&ctl->tree_lock);
2476                                 ret = 0;
2477                                 continue;
2478                         }
2479                 } else {
2480                         start = entry->offset;
2481                         bytes = min(entry->bytes, end - start);
2482                         unlink_free_space(ctl, entry);
2483                         kmem_cache_free(btrfs_free_space_cachep, entry);
2484                 }
2485
2486                 spin_unlock(&ctl->tree_lock);
2487
2488                 if (bytes >= minlen) {
2489                         struct btrfs_space_info *space_info;
2490                         int update = 0;
2491
2492                         space_info = block_group->space_info;
2493                         spin_lock(&space_info->lock);
2494                         spin_lock(&block_group->lock);
2495                         if (!block_group->ro) {
2496                                 block_group->reserved += bytes;
2497                                 space_info->bytes_reserved += bytes;
2498                                 update = 1;
2499                         }
2500                         spin_unlock(&block_group->lock);
2501                         spin_unlock(&space_info->lock);
2502
2503                         ret = btrfs_error_discard_extent(fs_info->extent_root,
2504                                                          start,
2505                                                          bytes,
2506                                                          &actually_trimmed);
2507
2508                         btrfs_add_free_space(block_group, start, bytes);
2509                         if (update) {
2510                                 spin_lock(&space_info->lock);
2511                                 spin_lock(&block_group->lock);
2512                                 if (block_group->ro)
2513                                         space_info->bytes_readonly += bytes;
2514                                 block_group->reserved -= bytes;
2515                                 space_info->bytes_reserved -= bytes;
2516                                 spin_unlock(&space_info->lock);
2517                                 spin_unlock(&block_group->lock);
2518                         }
2519
2520                         if (ret)
2521                                 break;
2522                         *trimmed += actually_trimmed;
2523                 }
2524                 start += bytes;
2525                 bytes = 0;
2526
2527                 if (fatal_signal_pending(current)) {
2528                         ret = -ERESTARTSYS;
2529                         break;
2530                 }
2531
2532                 cond_resched();
2533         }
2534
2535         return ret;
2536 }
2537
2538 /*
2539  * Find the left-most item in the cache tree, and then return the
2540  * smallest inode number in the item.
2541  *
2542  * Note: the returned inode number may not be the smallest one in
2543  * the tree, if the left-most item is a bitmap.
2544  */
2545 u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
2546 {
2547         struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
2548         struct btrfs_free_space *entry = NULL;
2549         u64 ino = 0;
2550
2551         spin_lock(&ctl->tree_lock);
2552
2553         if (RB_EMPTY_ROOT(&ctl->free_space_offset))
2554                 goto out;
2555
2556         entry = rb_entry(rb_first(&ctl->free_space_offset),
2557                          struct btrfs_free_space, offset_index);
2558
2559         if (!entry->bitmap) {
2560                 ino = entry->offset;
2561
2562                 unlink_free_space(ctl, entry);
2563                 entry->offset++;
2564                 entry->bytes--;
2565                 if (!entry->bytes)
2566                         kmem_cache_free(btrfs_free_space_cachep, entry);
2567                 else
2568                         link_free_space(ctl, entry);
2569         } else {
2570                 u64 offset = 0;
2571                 u64 count = 1;
2572                 int ret;
2573
2574                 ret = search_bitmap(ctl, entry, &offset, &count);
2575                 BUG_ON(ret);
2576
2577                 ino = offset;
2578                 bitmap_clear_bits(ctl, entry, offset, 1);
2579                 if (entry->bytes == 0)
2580                         free_bitmap(ctl, entry);
2581         }
2582 out:
2583         spin_unlock(&ctl->tree_lock);
2584
2585         return ino;
2586 }
2587
2588 struct inode *lookup_free_ino_inode(struct btrfs_root *root,
2589                                     struct btrfs_path *path)
2590 {
2591         struct inode *inode = NULL;
2592
2593         spin_lock(&root->cache_lock);
2594         if (root->cache_inode)
2595                 inode = igrab(root->cache_inode);
2596         spin_unlock(&root->cache_lock);
2597         if (inode)
2598                 return inode;
2599
2600         inode = __lookup_free_space_inode(root, path, 0);
2601         if (IS_ERR(inode))
2602                 return inode;
2603
2604         spin_lock(&root->cache_lock);
2605         if (!btrfs_fs_closing(root->fs_info))
2606                 root->cache_inode = igrab(inode);
2607         spin_unlock(&root->cache_lock);
2608
2609         return inode;
2610 }
2611
2612 int create_free_ino_inode(struct btrfs_root *root,
2613                           struct btrfs_trans_handle *trans,
2614                           struct btrfs_path *path)
2615 {
2616         return __create_free_space_inode(root, trans, path,
2617                                          BTRFS_FREE_INO_OBJECTID, 0);
2618 }
2619
2620 int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
2621 {
2622         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
2623         struct btrfs_path *path;
2624         struct inode *inode;
2625         int ret = 0;
2626         u64 root_gen = btrfs_root_generation(&root->root_item);
2627
2628         if (!btrfs_test_opt(root, INODE_MAP_CACHE))
2629                 return 0;
2630
2631         /*
2632          * If we're unmounting then just return, since this does a search on the
2633          * normal root and not the commit root and we could deadlock.
2634          */
2635         if (btrfs_fs_closing(fs_info))
2636                 return 0;
2637
2638         path = btrfs_alloc_path();
2639         if (!path)
2640                 return 0;
2641
2642         inode = lookup_free_ino_inode(root, path);
2643         if (IS_ERR(inode))
2644                 goto out;
2645
2646         if (root_gen != BTRFS_I(inode)->generation)
2647                 goto out_put;
2648
2649         ret = __load_free_space_cache(root, inode, ctl, path, 0);
2650
2651         if (ret < 0)
2652                 printk(KERN_ERR "btrfs: failed to load free ino cache for "
2653                        "root %llu\n", root->root_key.objectid);
2654 out_put:
2655         iput(inode);
2656 out:
2657         btrfs_free_path(path);
2658         return ret;
2659 }
2660
2661 int btrfs_write_out_ino_cache(struct btrfs_root *root,
2662                               struct btrfs_trans_handle *trans,
2663                               struct btrfs_path *path)
2664 {
2665         struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
2666         struct inode *inode;
2667         int ret;
2668
2669         if (!btrfs_test_opt(root, INODE_MAP_CACHE))
2670                 return 0;
2671
2672         inode = lookup_free_ino_inode(root, path);
2673         if (IS_ERR(inode))
2674                 return 0;
2675
2676         ret = __btrfs_write_out_cache(root, inode, ctl, NULL, trans, path, 0);
2677         if (ret) {
2678                 btrfs_delalloc_release_metadata(inode, inode->i_size);
2679 #ifdef DEBUG
2680                 printk(KERN_ERR "btrfs: failed to write free ino cache "
2681                        "for root %llu\n", root->root_key.objectid);
2682 #endif
2683         }
2684
2685         iput(inode);
2686         return ret;
2687 }