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