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