fs/btrfs/free-space-tree.c

   1 /*
   2  * Copyright (C) 2015 Facebook.  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/kernel.h>
  20 #include <linux/vmalloc.h>
  21 #include "ctree.h"
  22 #include "disk-io.h"
  23 #include "locking.h"
  24 #include "free-space-tree.h"
  25 #include "transaction.h"
  26
  27 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
  28                                         struct btrfs_fs_info *fs_info,
  29                                         struct btrfs_block_group_cache *block_group,
  30                                         struct btrfs_path *path);
  31
  32 void set_free_space_tree_thresholds(struct btrfs_block_group_cache *cache)
  33 {
  34         u32 bitmap_range;
  35         size_t bitmap_size;
  36         u64 num_bitmaps, total_bitmap_size;
  37
  38         /*
  39          * We convert to bitmaps when the disk space required for using extents
  40          * exceeds that required for using bitmaps.
  41          */
  42         bitmap_range = cache->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
  43         num_bitmaps = div_u64(cache->key.offset + bitmap_range - 1,
  44                               bitmap_range);
  45         bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
  46         total_bitmap_size = num_bitmaps * bitmap_size;
  47         cache->bitmap_high_thresh = div_u64(total_bitmap_size,
  48                                             sizeof(struct btrfs_item));
  49
  50         /*
  51          * We allow for a small buffer between the high threshold and low
  52          * threshold to avoid thrashing back and forth between the two formats.
  53          */
  54         if (cache->bitmap_high_thresh > 100)
  55                 cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
  56         else
  57                 cache->bitmap_low_thresh = 0;
  58 }
  59
  60 static int add_new_free_space_info(struct btrfs_trans_handle *trans,
  61                                    struct btrfs_fs_info *fs_info,
  62                                    struct btrfs_block_group_cache *block_group,
  63                                    struct btrfs_path *path)
  64 {
  65         struct btrfs_root *root = fs_info->free_space_root;
  66         struct btrfs_free_space_info *info;
  67         struct btrfs_key key;
  68         struct extent_buffer *leaf;
  69         int ret;
  70
  71         key.objectid = block_group->key.objectid;
  72         key.type = BTRFS_FREE_SPACE_INFO_KEY;
  73         key.offset = block_group->key.offset;
  74
  75         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
  76         if (ret)
  77                 goto out;
  78
  79         leaf = path->nodes[0];
  80         info = btrfs_item_ptr(leaf, path->slots[0],
  81                               struct btrfs_free_space_info);
  82         btrfs_set_free_space_extent_count(leaf, info, 0);
  83         btrfs_set_free_space_flags(leaf, info, 0);
  84         btrfs_mark_buffer_dirty(leaf);
  85
  86         ret = 0;
  87 out:
  88         btrfs_release_path(path);
  89         return ret;
  90 }
  91
  92 struct btrfs_free_space_info *
  93 search_free_space_info(struct btrfs_trans_handle *trans,
  94                        struct btrfs_fs_info *fs_info,
  95                        struct btrfs_block_group_cache *block_group,
  96                        struct btrfs_path *path, int cow)
  97 {
  98         struct btrfs_root *root = fs_info->free_space_root;
  99         struct btrfs_key key;
 100         int ret;
 101
 102         key.objectid = block_group->key.objectid;
 103         key.type = BTRFS_FREE_SPACE_INFO_KEY;
 104         key.offset = block_group->key.offset;
 105
 106         ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
 107         if (ret < 0)
 108                 return ERR_PTR(ret);
 109         if (ret != 0) {
 110                 btrfs_warn(fs_info, "missing free space info for %llu\n",
 111                            block_group->key.objectid);
 112                 ASSERT(0);
 113                 return ERR_PTR(-ENOENT);
 114         }
 115
 116         return btrfs_item_ptr(path->nodes[0], path->slots[0],
 117                               struct btrfs_free_space_info);
 118 }
 119
 120 /*
 121  * btrfs_search_slot() but we're looking for the greatest key less than the
 122  * passed key.
 123  */
 124 static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
 125                                   struct btrfs_root *root,
 126                                   struct btrfs_key *key, struct btrfs_path *p,
 127                                   int ins_len, int cow)
 128 {
 129         int ret;
 130
 131         ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
 132         if (ret < 0)
 133                 return ret;
 134
 135         if (ret == 0) {
 136                 ASSERT(0);
 137                 return -EIO;
 138         }
 139
 140         if (p->slots[0] == 0) {
 141                 ASSERT(0);
 142                 return -EIO;
 143         }
 144         p->slots[0]--;
 145
 146         return 0;
 147 }
 148
 149 static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize)
 150 {
 151         return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE);
 152 }
 153
 154 static u8 *alloc_bitmap(u32 bitmap_size)
 155 {
 156         void *mem;
 157
 158         /*
 159          * The allocation size varies, observed numbers were < 4K up to 16K.
 160          * Using vmalloc unconditionally would be too heavy, we'll try
 161          * contiguous allocations first.
 162          */
 163         if  (bitmap_size <= PAGE_SIZE)
 164                 return kzalloc(bitmap_size, GFP_NOFS);
 165
 166         mem = kzalloc(bitmap_size, GFP_NOFS | __GFP_NOWARN);
 167         if (mem)
 168                 return mem;
 169
 170         return __vmalloc(bitmap_size, GFP_NOFS | __GFP_HIGHMEM | __GFP_ZERO,
 171                          PAGE_KERNEL);
 172 }
 173
 174 int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
 175                                   struct btrfs_fs_info *fs_info,
 176                                   struct btrfs_block_group_cache *block_group,
 177                                   struct btrfs_path *path)
 178 {
 179         struct btrfs_root *root = fs_info->free_space_root;
 180         struct btrfs_free_space_info *info;
 181         struct btrfs_key key, found_key;
 182         struct extent_buffer *leaf;
 183         u8 *bitmap, *bitmap_cursor;
 184         u64 start, end;
 185         u64 bitmap_range, i;
 186         u32 bitmap_size, flags, expected_extent_count;
 187         u32 extent_count = 0;
 188         int done = 0, nr;
 189         int ret;
 190
 191         bitmap_size = free_space_bitmap_size(block_group->key.offset,
 192                                              block_group->sectorsize);
 193         bitmap = alloc_bitmap(bitmap_size);
 194         if (!bitmap) {
 195                 ret = -ENOMEM;
 196                 goto out;
 197         }
 198
 199         start = block_group->key.objectid;
 200         end = block_group->key.objectid + block_group->key.offset;
 201
 202         key.objectid = end - 1;
 203         key.type = (u8)-1;
 204         key.offset = (u64)-1;
 205
 206         while (!done) {
 207                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 208                 if (ret)
 209                         goto out;
 210
 211                 leaf = path->nodes[0];
 212                 nr = 0;
 213                 path->slots[0]++;
 214                 while (path->slots[0] > 0) {
 215                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
 216
 217                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
 218                                 ASSERT(found_key.objectid == block_group->key.objectid);
 219                                 ASSERT(found_key.offset == block_group->key.offset);
 220                                 done = 1;
 221                                 break;
 222                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
 223                                 u64 first, last;
 224
 225                                 ASSERT(found_key.objectid >= start);
 226                                 ASSERT(found_key.objectid < end);
 227                                 ASSERT(found_key.objectid + found_key.offset <= end);
 228
 229                                 first = div_u64(found_key.objectid - start,
 230                                                 block_group->sectorsize);
 231                                 last = div_u64(found_key.objectid + found_key.offset - start,
 232                                                block_group->sectorsize);
 233                                 le_bitmap_set(bitmap, first, last - first);
 234
 235                                 extent_count++;
 236                                 nr++;
 237                                 path->slots[0]--;
 238                         } else {
 239                                 ASSERT(0);
 240                         }
 241                 }
 242
 243                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
 244                 if (ret)
 245                         goto out;
 246                 btrfs_release_path(path);
 247         }
 248
 249         info = search_free_space_info(trans, fs_info, block_group, path, 1);
 250         if (IS_ERR(info)) {
 251                 ret = PTR_ERR(info);
 252                 goto out;
 253         }
 254         leaf = path->nodes[0];
 255         flags = btrfs_free_space_flags(leaf, info);
 256         flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
 257         btrfs_set_free_space_flags(leaf, info, flags);
 258         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
 259         btrfs_mark_buffer_dirty(leaf);
 260         btrfs_release_path(path);
 261
 262         if (extent_count != expected_extent_count) {
 263                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
 264                           block_group->key.objectid, extent_count,
 265                           expected_extent_count);
 266                 ASSERT(0);
 267                 ret = -EIO;
 268                 goto out;
 269         }
 270
 271         bitmap_cursor = bitmap;
 272         bitmap_range = block_group->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
 273         i = start;
 274         while (i < end) {
 275                 unsigned long ptr;
 276                 u64 extent_size;
 277                 u32 data_size;
 278
 279                 extent_size = min(end - i, bitmap_range);
 280                 data_size = free_space_bitmap_size(extent_size,
 281                                                    block_group->sectorsize);
 282
 283                 key.objectid = i;
 284                 key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
 285                 key.offset = extent_size;
 286
 287                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 288                                               data_size);
 289                 if (ret)
 290                         goto out;
 291
 292                 leaf = path->nodes[0];
 293                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
 294                 write_extent_buffer(leaf, bitmap_cursor, ptr,
 295                                     data_size);
 296                 btrfs_mark_buffer_dirty(leaf);
 297                 btrfs_release_path(path);
 298
 299                 i += extent_size;
 300                 bitmap_cursor += data_size;
 301         }
 302
 303         ret = 0;
 304 out:
 305         kvfree(bitmap);
 306         if (ret)
 307                 btrfs_abort_transaction(trans, ret);
 308         return ret;
 309 }
 310
 311 int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
 312                                   struct btrfs_fs_info *fs_info,
 313                                   struct btrfs_block_group_cache *block_group,
 314                                   struct btrfs_path *path)
 315 {
 316         struct btrfs_root *root = fs_info->free_space_root;
 317         struct btrfs_free_space_info *info;
 318         struct btrfs_key key, found_key;
 319         struct extent_buffer *leaf;
 320         u8 *bitmap;
 321         u64 start, end;
 322         /* Initialize to silence GCC. */
 323         u64 extent_start = 0;
 324         u64 offset;
 325         u32 bitmap_size, flags, expected_extent_count;
 326         int prev_bit = 0, bit, bitnr;
 327         u32 extent_count = 0;
 328         int done = 0, nr;
 329         int ret;
 330
 331         bitmap_size = free_space_bitmap_size(block_group->key.offset,
 332                                              block_group->sectorsize);
 333         bitmap = alloc_bitmap(bitmap_size);
 334         if (!bitmap) {
 335                 ret = -ENOMEM;
 336                 goto out;
 337         }
 338
 339         start = block_group->key.objectid;
 340         end = block_group->key.objectid + block_group->key.offset;
 341
 342         key.objectid = end - 1;
 343         key.type = (u8)-1;
 344         key.offset = (u64)-1;
 345
 346         while (!done) {
 347                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 348                 if (ret)
 349                         goto out;
 350
 351                 leaf = path->nodes[0];
 352                 nr = 0;
 353                 path->slots[0]++;
 354                 while (path->slots[0] > 0) {
 355                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
 356
 357                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
 358                                 ASSERT(found_key.objectid == block_group->key.objectid);
 359                                 ASSERT(found_key.offset == block_group->key.offset);
 360                                 done = 1;
 361                                 break;
 362                         } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
 363                                 unsigned long ptr;
 364                                 u8 *bitmap_cursor;
 365                                 u32 bitmap_pos, data_size;
 366
 367                                 ASSERT(found_key.objectid >= start);
 368                                 ASSERT(found_key.objectid < end);
 369                                 ASSERT(found_key.objectid + found_key.offset <= end);
 370
 371                                 bitmap_pos = div_u64(found_key.objectid - start,
 372                                                      block_group->sectorsize *
 373                                                      BITS_PER_BYTE);
 374                                 bitmap_cursor = bitmap + bitmap_pos;
 375                                 data_size = free_space_bitmap_size(found_key.offset,
 376                                                                    block_group->sectorsize);
 377
 378                                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
 379                                 read_extent_buffer(leaf, bitmap_cursor, ptr,
 380                                                    data_size);
 381
 382                                 nr++;
 383                                 path->slots[0]--;
 384                         } else {
 385                                 ASSERT(0);
 386                         }
 387                 }
 388
 389                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
 390                 if (ret)
 391                         goto out;
 392                 btrfs_release_path(path);
 393         }
 394
 395         info = search_free_space_info(trans, fs_info, block_group, path, 1);
 396         if (IS_ERR(info)) {
 397                 ret = PTR_ERR(info);
 398                 goto out;
 399         }
 400         leaf = path->nodes[0];
 401         flags = btrfs_free_space_flags(leaf, info);
 402         flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
 403         btrfs_set_free_space_flags(leaf, info, flags);
 404         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
 405         btrfs_mark_buffer_dirty(leaf);
 406         btrfs_release_path(path);
 407
 408         offset = start;
 409         bitnr = 0;
 410         while (offset < end) {
 411                 bit = !!le_test_bit(bitnr, bitmap);
 412                 if (prev_bit == 0 && bit == 1) {
 413                         extent_start = offset;
 414                 } else if (prev_bit == 1 && bit == 0) {
 415                         key.objectid = extent_start;
 416                         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 417                         key.offset = offset - extent_start;
 418
 419                         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 420                         if (ret)
 421                                 goto out;
 422                         btrfs_release_path(path);
 423
 424                         extent_count++;
 425                 }
 426                 prev_bit = bit;
 427                 offset += block_group->sectorsize;
 428                 bitnr++;
 429         }
 430         if (prev_bit == 1) {
 431                 key.objectid = extent_start;
 432                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 433                 key.offset = end - extent_start;
 434
 435                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 436                 if (ret)
 437                         goto out;
 438                 btrfs_release_path(path);
 439
 440                 extent_count++;
 441         }
 442
 443         if (extent_count != expected_extent_count) {
 444                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
 445                           block_group->key.objectid, extent_count,
 446                           expected_extent_count);
 447                 ASSERT(0);
 448                 ret = -EIO;
 449                 goto out;
 450         }
 451
 452         ret = 0;
 453 out:
 454         kvfree(bitmap);
 455         if (ret)
 456                 btrfs_abort_transaction(trans, ret);
 457         return ret;
 458 }
 459
 460 static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
 461                                           struct btrfs_fs_info *fs_info,
 462                                           struct btrfs_block_group_cache *block_group,
 463                                           struct btrfs_path *path,
 464                                           int new_extents)
 465 {
 466         struct btrfs_free_space_info *info;
 467         u32 flags;
 468         u32 extent_count;
 469         int ret = 0;
 470
 471         if (new_extents == 0)
 472                 return 0;
 473
 474         info = search_free_space_info(trans, fs_info, block_group, path, 1);
 475         if (IS_ERR(info)) {
 476                 ret = PTR_ERR(info);
 477                 goto out;
 478         }
 479         flags = btrfs_free_space_flags(path->nodes[0], info);
 480         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
 481
 482         extent_count += new_extents;
 483         btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
 484         btrfs_mark_buffer_dirty(path->nodes[0]);
 485         btrfs_release_path(path);
 486
 487         if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
 488             extent_count > block_group->bitmap_high_thresh) {
 489                 ret = convert_free_space_to_bitmaps(trans, fs_info, block_group,
 490                                                     path);
 491         } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
 492                    extent_count < block_group->bitmap_low_thresh) {
 493                 ret = convert_free_space_to_extents(trans, fs_info, block_group,
 494                                                     path);
 495         }
 496
 497 out:
 498         return ret;
 499 }
 500
 501 int free_space_test_bit(struct btrfs_block_group_cache *block_group,
 502                         struct btrfs_path *path, u64 offset)
 503 {
 504         struct extent_buffer *leaf;
 505         struct btrfs_key key;
 506         u64 found_start, found_end;
 507         unsigned long ptr, i;
 508
 509         leaf = path->nodes[0];
 510         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 511         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
 512
 513         found_start = key.objectid;
 514         found_end = key.objectid + key.offset;
 515         ASSERT(offset >= found_start && offset < found_end);
 516
 517         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
 518         i = div_u64(offset - found_start, block_group->sectorsize);
 519         return !!extent_buffer_test_bit(leaf, ptr, i);
 520 }
 521
 522 static void free_space_set_bits(struct btrfs_block_group_cache *block_group,
 523                                 struct btrfs_path *path, u64 *start, u64 *size,
 524                                 int bit)
 525 {
 526         struct extent_buffer *leaf;
 527         struct btrfs_key key;
 528         u64 end = *start + *size;
 529         u64 found_start, found_end;
 530         unsigned long ptr, first, last;
 531
 532         leaf = path->nodes[0];
 533         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 534         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
 535
 536         found_start = key.objectid;
 537         found_end = key.objectid + key.offset;
 538         ASSERT(*start >= found_start && *start < found_end);
 539         ASSERT(end > found_start);
 540
 541         if (end > found_end)
 542                 end = found_end;
 543
 544         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
 545         first = div_u64(*start - found_start, block_group->sectorsize);
 546         last = div_u64(end - found_start, block_group->sectorsize);
 547         if (bit)
 548                 extent_buffer_bitmap_set(leaf, ptr, first, last - first);
 549         else
 550                 extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
 551         btrfs_mark_buffer_dirty(leaf);
 552
 553         *size -= end - *start;
 554         *start = end;
 555 }
 556
 557 /*
 558  * We can't use btrfs_next_item() in modify_free_space_bitmap() because
 559  * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
 560  * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
 561  * looking for.
 562  */
 563 static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
 564                                   struct btrfs_root *root, struct btrfs_path *p)
 565 {
 566         struct btrfs_key key;
 567
 568         if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
 569                 p->slots[0]++;
 570                 return 0;
 571         }
 572
 573         btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
 574         btrfs_release_path(p);
 575
 576         key.objectid += key.offset;
 577         key.type = (u8)-1;
 578         key.offset = (u64)-1;
 579
 580         return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
 581 }
 582
 583 /*
 584  * If remove is 1, then we are removing free space, thus clearing bits in the
 585  * bitmap. If remove is 0, then we are adding free space, thus setting bits in
 586  * the bitmap.
 587  */
 588 static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
 589                                     struct btrfs_fs_info *fs_info,
 590                                     struct btrfs_block_group_cache *block_group,
 591                                     struct btrfs_path *path,
 592                                     u64 start, u64 size, int remove)
 593 {
 594         struct btrfs_root *root = fs_info->free_space_root;
 595         struct btrfs_key key;
 596         u64 end = start + size;
 597         u64 cur_start, cur_size;
 598         int prev_bit, next_bit;
 599         int new_extents;
 600         int ret;
 601
 602         /*
 603          * Read the bit for the block immediately before the extent of space if
 604          * that block is within the block group.
 605          */
 606         if (start > block_group->key.objectid) {
 607                 u64 prev_block = start - block_group->sectorsize;
 608
 609                 key.objectid = prev_block;
 610                 key.type = (u8)-1;
 611                 key.offset = (u64)-1;
 612
 613                 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
 614                 if (ret)
 615                         goto out;
 616
 617                 prev_bit = free_space_test_bit(block_group, path, prev_block);
 618
 619                 /* The previous block may have been in the previous bitmap. */
 620                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 621                 if (start >= key.objectid + key.offset) {
 622                         ret = free_space_next_bitmap(trans, root, path);
 623                         if (ret)
 624                                 goto out;
 625                 }
 626         } else {
 627                 key.objectid = start;
 628                 key.type = (u8)-1;
 629                 key.offset = (u64)-1;
 630
 631                 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
 632                 if (ret)
 633                         goto out;
 634
 635                 prev_bit = -1;
 636         }
 637
 638         /*
 639          * Iterate over all of the bitmaps overlapped by the extent of space,
 640          * clearing/setting bits as required.
 641          */
 642         cur_start = start;
 643         cur_size = size;
 644         while (1) {
 645                 free_space_set_bits(block_group, path, &cur_start, &cur_size,
 646                                     !remove);
 647                 if (cur_size == 0)
 648                         break;
 649                 ret = free_space_next_bitmap(trans, root, path);
 650                 if (ret)
 651                         goto out;
 652         }
 653
 654         /*
 655          * Read the bit for the block immediately after the extent of space if
 656          * that block is within the block group.
 657          */
 658         if (end < block_group->key.objectid + block_group->key.offset) {
 659                 /* The next block may be in the next bitmap. */
 660                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 661                 if (end >= key.objectid + key.offset) {
 662                         ret = free_space_next_bitmap(trans, root, path);
 663                         if (ret)
 664                                 goto out;
 665                 }
 666
 667                 next_bit = free_space_test_bit(block_group, path, end);
 668         } else {
 669                 next_bit = -1;
 670         }
 671
 672         if (remove) {
 673                 new_extents = -1;
 674                 if (prev_bit == 1) {
 675                         /* Leftover on the left. */
 676                         new_extents++;
 677                 }
 678                 if (next_bit == 1) {
 679                         /* Leftover on the right. */
 680                         new_extents++;
 681                 }
 682         } else {
 683                 new_extents = 1;
 684                 if (prev_bit == 1) {
 685                         /* Merging with neighbor on the left. */
 686                         new_extents--;
 687                 }
 688                 if (next_bit == 1) {
 689                         /* Merging with neighbor on the right. */
 690                         new_extents--;
 691                 }
 692         }
 693
 694         btrfs_release_path(path);
 695         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
 696                                              new_extents);
 697
 698 out:
 699         return ret;
 700 }
 701
 702 static int remove_free_space_extent(struct btrfs_trans_handle *trans,
 703                                     struct btrfs_fs_info *fs_info,
 704                                     struct btrfs_block_group_cache *block_group,
 705                                     struct btrfs_path *path,
 706                                     u64 start, u64 size)
 707 {
 708         struct btrfs_root *root = fs_info->free_space_root;
 709         struct btrfs_key key;
 710         u64 found_start, found_end;
 711         u64 end = start + size;
 712         int new_extents = -1;
 713         int ret;
 714
 715         key.objectid = start;
 716         key.type = (u8)-1;
 717         key.offset = (u64)-1;
 718
 719         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 720         if (ret)
 721                 goto out;
 722
 723         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 724
 725         ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
 726
 727         found_start = key.objectid;
 728         found_end = key.objectid + key.offset;
 729         ASSERT(start >= found_start && end <= found_end);
 730
 731         /*
 732          * Okay, now that we've found the free space extent which contains the
 733          * free space that we are removing, there are four cases:
 734          *
 735          * 1. We're using the whole extent: delete the key we found and
 736          * decrement the free space extent count.
 737          * 2. We are using part of the extent starting at the beginning: delete
 738          * the key we found and insert a new key representing the leftover at
 739          * the end. There is no net change in the number of extents.
 740          * 3. We are using part of the extent ending at the end: delete the key
 741          * we found and insert a new key representing the leftover at the
 742          * beginning. There is no net change in the number of extents.
 743          * 4. We are using part of the extent in the middle: delete the key we
 744          * found and insert two new keys representing the leftovers on each
 745          * side. Where we used to have one extent, we now have two, so increment
 746          * the extent count. We may need to convert the block group to bitmaps
 747          * as a result.
 748          */
 749
 750         /* Delete the existing key (cases 1-4). */
 751         ret = btrfs_del_item(trans, root, path);
 752         if (ret)
 753                 goto out;
 754
 755         /* Add a key for leftovers at the beginning (cases 3 and 4). */
 756         if (start > found_start) {
 757                 key.objectid = found_start;
 758                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 759                 key.offset = start - found_start;
 760
 761                 btrfs_release_path(path);
 762                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 763                 if (ret)
 764                         goto out;
 765                 new_extents++;
 766         }
 767
 768         /* Add a key for leftovers at the end (cases 2 and 4). */
 769         if (end < found_end) {
 770                 key.objectid = end;
 771                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 772                 key.offset = found_end - end;
 773
 774                 btrfs_release_path(path);
 775                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 776                 if (ret)
 777                         goto out;
 778                 new_extents++;
 779         }
 780
 781         btrfs_release_path(path);
 782         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
 783                                              new_extents);
 784
 785 out:
 786         return ret;
 787 }
 788
 789 int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
 790                                   struct btrfs_fs_info *fs_info,
 791                                   struct btrfs_block_group_cache *block_group,
 792                                   struct btrfs_path *path, u64 start, u64 size)
 793 {
 794         struct btrfs_free_space_info *info;
 795         u32 flags;
 796         int ret;
 797
 798         if (block_group->needs_free_space) {
 799                 ret = __add_block_group_free_space(trans, fs_info, block_group,
 800                                                    path);
 801                 if (ret)
 802                         return ret;
 803         }
 804
 805         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
 806         if (IS_ERR(info))
 807                 return PTR_ERR(info);
 808         flags = btrfs_free_space_flags(path->nodes[0], info);
 809         btrfs_release_path(path);
 810
 811         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
 812                 return modify_free_space_bitmap(trans, fs_info, block_group,
 813                                                 path, start, size, 1);
 814         } else {
 815                 return remove_free_space_extent(trans, fs_info, block_group,
 816                                                 path, start, size);
 817         }
 818 }
 819
 820 int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
 821                                 struct btrfs_fs_info *fs_info,
 822                                 u64 start, u64 size)
 823 {
 824         struct btrfs_block_group_cache *block_group;
 825         struct btrfs_path *path;
 826         int ret;
 827
 828         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
 829                 return 0;
 830
 831         path = btrfs_alloc_path();
 832         if (!path) {
 833                 ret = -ENOMEM;
 834                 goto out;
 835         }
 836
 837         block_group = btrfs_lookup_block_group(fs_info, start);
 838         if (!block_group) {
 839                 ASSERT(0);
 840                 ret = -ENOENT;
 841                 goto out;
 842         }
 843
 844         mutex_lock(&block_group->free_space_lock);
 845         ret = __remove_from_free_space_tree(trans, fs_info, block_group, path,
 846                                             start, size);
 847         mutex_unlock(&block_group->free_space_lock);
 848
 849         btrfs_put_block_group(block_group);
 850 out:
 851         btrfs_free_path(path);
 852         if (ret)
 853                 btrfs_abort_transaction(trans, ret);
 854         return ret;
 855 }
 856
 857 static int add_free_space_extent(struct btrfs_trans_handle *trans,
 858                                  struct btrfs_fs_info *fs_info,
 859                                  struct btrfs_block_group_cache *block_group,
 860                                  struct btrfs_path *path,
 861                                  u64 start, u64 size)
 862 {
 863         struct btrfs_root *root = fs_info->free_space_root;
 864         struct btrfs_key key, new_key;
 865         u64 found_start, found_end;
 866         u64 end = start + size;
 867         int new_extents = 1;
 868         int ret;
 869
 870         /*
 871          * We are adding a new extent of free space, but we need to merge
 872          * extents. There are four cases here:
 873          *
 874          * 1. The new extent does not have any immediate neighbors to merge
 875          * with: add the new key and increment the free space extent count. We
 876          * may need to convert the block group to bitmaps as a result.
 877          * 2. The new extent has an immediate neighbor before it: remove the
 878          * previous key and insert a new key combining both of them. There is no
 879          * net change in the number of extents.
 880          * 3. The new extent has an immediate neighbor after it: remove the next
 881          * key and insert a new key combining both of them. There is no net
 882          * change in the number of extents.
 883          * 4. The new extent has immediate neighbors on both sides: remove both
 884          * of the keys and insert a new key combining all of them. Where we used
 885          * to have two extents, we now have one, so decrement the extent count.
 886          */
 887
 888         new_key.objectid = start;
 889         new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 890         new_key.offset = size;
 891
 892         /* Search for a neighbor on the left. */
 893         if (start == block_group->key.objectid)
 894                 goto right;
 895         key.objectid = start - 1;
 896         key.type = (u8)-1;
 897         key.offset = (u64)-1;
 898
 899         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 900         if (ret)
 901                 goto out;
 902
 903         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 904
 905         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
 906                 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
 907                 btrfs_release_path(path);
 908                 goto right;
 909         }
 910
 911         found_start = key.objectid;
 912         found_end = key.objectid + key.offset;
 913         ASSERT(found_start >= block_group->key.objectid &&
 914                found_end > block_group->key.objectid);
 915         ASSERT(found_start < start && found_end <= start);
 916
 917         /*
 918          * Delete the neighbor on the left and absorb it into the new key (cases
 919          * 2 and 4).
 920          */
 921         if (found_end == start) {
 922                 ret = btrfs_del_item(trans, root, path);
 923                 if (ret)
 924                         goto out;
 925                 new_key.objectid = found_start;
 926                 new_key.offset += key.offset;
 927                 new_extents--;
 928         }
 929         btrfs_release_path(path);
 930
 931 right:
 932         /* Search for a neighbor on the right. */
 933         if (end == block_group->key.objectid + block_group->key.offset)
 934                 goto insert;
 935         key.objectid = end;
 936         key.type = (u8)-1;
 937         key.offset = (u64)-1;
 938
 939         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 940         if (ret)
 941                 goto out;
 942
 943         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 944
 945         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
 946                 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
 947                 btrfs_release_path(path);
 948                 goto insert;
 949         }
 950
 951         found_start = key.objectid;
 952         found_end = key.objectid + key.offset;
 953         ASSERT(found_start >= block_group->key.objectid &&
 954                found_end > block_group->key.objectid);
 955         ASSERT((found_start < start && found_end <= start) ||
 956                (found_start >= end && found_end > end));
 957
 958         /*
 959          * Delete the neighbor on the right and absorb it into the new key
 960          * (cases 3 and 4).
 961          */
 962         if (found_start == end) {
 963                 ret = btrfs_del_item(trans, root, path);
 964                 if (ret)
 965                         goto out;
 966                 new_key.offset += key.offset;
 967                 new_extents--;
 968         }
 969         btrfs_release_path(path);
 970
 971 insert:
 972         /* Insert the new key (cases 1-4). */
 973         ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
 974         if (ret)
 975                 goto out;
 976
 977         btrfs_release_path(path);
 978         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
 979                                              new_extents);
 980
 981 out:
 982         return ret;
 983 }
 984
 985 int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
 986                              struct btrfs_fs_info *fs_info,
 987                              struct btrfs_block_group_cache *block_group,
 988                              struct btrfs_path *path, u64 start, u64 size)
 989 {
 990         struct btrfs_free_space_info *info;
 991         u32 flags;
 992         int ret;
 993
 994         if (block_group->needs_free_space) {
 995                 ret = __add_block_group_free_space(trans, fs_info, block_group,
 996                                                    path);
 997                 if (ret)
 998                         return ret;
 999         }
1000
1001         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
1002         if (IS_ERR(info))
1003                 return PTR_ERR(info);
1004         flags = btrfs_free_space_flags(path->nodes[0], info);
1005         btrfs_release_path(path);
1006
1007         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
1008                 return modify_free_space_bitmap(trans, fs_info, block_group,
1009                                                 path, start, size, 0);
1010         } else {
1011                 return add_free_space_extent(trans, fs_info, block_group, path,
1012                                              start, size);
1013         }
1014 }
1015
1016 int add_to_free_space_tree(struct btrfs_trans_handle *trans,
1017                            struct btrfs_fs_info *fs_info,
1018                            u64 start, u64 size)
1019 {
1020         struct btrfs_block_group_cache *block_group;
1021         struct btrfs_path *path;
1022         int ret;
1023
1024         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1025                 return 0;
1026
1027         path = btrfs_alloc_path();
1028         if (!path) {
1029                 ret = -ENOMEM;
1030                 goto out;
1031         }
1032
1033         block_group = btrfs_lookup_block_group(fs_info, start);
1034         if (!block_group) {
1035                 ASSERT(0);
1036                 ret = -ENOENT;
1037                 goto out;
1038         }
1039
1040         mutex_lock(&block_group->free_space_lock);
1041         ret = __add_to_free_space_tree(trans, fs_info, block_group, path, start,
1042                                        size);
1043         mutex_unlock(&block_group->free_space_lock);
1044
1045         btrfs_put_block_group(block_group);
1046 out:
1047         btrfs_free_path(path);
1048         if (ret)
1049                 btrfs_abort_transaction(trans, ret);
1050         return ret;
1051 }
1052
1053 /*
1054  * Populate the free space tree by walking the extent tree. Operations on the
1055  * extent tree that happen as a result of writes to the free space tree will go
1056  * through the normal add/remove hooks.
1057  */
1058 static int populate_free_space_tree(struct btrfs_trans_handle *trans,
1059                                     struct btrfs_fs_info *fs_info,
1060                                     struct btrfs_block_group_cache *block_group)
1061 {
1062         struct btrfs_root *extent_root = fs_info->extent_root;
1063         struct btrfs_path *path, *path2;
1064         struct btrfs_key key;
1065         u64 start, end;
1066         int ret;
1067
1068         path = btrfs_alloc_path();
1069         if (!path)
1070                 return -ENOMEM;
1071         path->reada = 1;
1072
1073         path2 = btrfs_alloc_path();
1074         if (!path2) {
1075                 btrfs_free_path(path);
1076                 return -ENOMEM;
1077         }
1078
1079         ret = add_new_free_space_info(trans, fs_info, block_group, path2);
1080         if (ret)
1081                 goto out;
1082
1083         mutex_lock(&block_group->free_space_lock);
1084
1085         /*
1086          * Iterate through all of the extent and metadata items in this block
1087          * group, adding the free space between them and the free space at the
1088          * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
1089          * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
1090          * contained in.
1091          */
1092         key.objectid = block_group->key.objectid;
1093         key.type = BTRFS_EXTENT_ITEM_KEY;
1094         key.offset = 0;
1095
1096         ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
1097         if (ret < 0)
1098                 goto out_locked;
1099         ASSERT(ret == 0);
1100
1101         start = block_group->key.objectid;
1102         end = block_group->key.objectid + block_group->key.offset;
1103         while (1) {
1104                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1105
1106                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1107                     key.type == BTRFS_METADATA_ITEM_KEY) {
1108                         if (key.objectid >= end)
1109                                 break;
1110
1111                         if (start < key.objectid) {
1112                                 ret = __add_to_free_space_tree(trans, fs_info,
1113                                                                block_group,
1114                                                                path2, start,
1115                                                                key.objectid -
1116                                                                start);
1117                                 if (ret)
1118                                         goto out_locked;
1119                         }
1120                         start = key.objectid;
1121                         if (key.type == BTRFS_METADATA_ITEM_KEY)
1122                                 start += fs_info->tree_root->nodesize;
1123                         else
1124                                 start += key.offset;
1125                 } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1126                         if (key.objectid != block_group->key.objectid)
1127                                 break;
1128                 }
1129
1130                 ret = btrfs_next_item(extent_root, path);
1131                 if (ret < 0)
1132                         goto out_locked;
1133                 if (ret)
1134                         break;
1135         }
1136         if (start < end) {
1137                 ret = __add_to_free_space_tree(trans, fs_info, block_group,
1138                                                path2, start, end - start);
1139                 if (ret)
1140                         goto out_locked;
1141         }
1142
1143         ret = 0;
1144 out_locked:
1145         mutex_unlock(&block_group->free_space_lock);
1146 out:
1147         btrfs_free_path(path2);
1148         btrfs_free_path(path);
1149         return ret;
1150 }
1151
1152 int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
1153 {
1154         struct btrfs_trans_handle *trans;
1155         struct btrfs_root *tree_root = fs_info->tree_root;
1156         struct btrfs_root *free_space_root;
1157         struct btrfs_block_group_cache *block_group;
1158         struct rb_node *node;
1159         int ret;
1160
1161         trans = btrfs_start_transaction(tree_root, 0);
1162         if (IS_ERR(trans))
1163                 return PTR_ERR(trans);
1164
1165         fs_info->creating_free_space_tree = 1;
1166         free_space_root = btrfs_create_tree(trans, fs_info,
1167                                             BTRFS_FREE_SPACE_TREE_OBJECTID);
1168         if (IS_ERR(free_space_root)) {
1169                 ret = PTR_ERR(free_space_root);
1170                 goto abort;
1171         }
1172         fs_info->free_space_root = free_space_root;
1173
1174         node = rb_first(&fs_info->block_group_cache_tree);
1175         while (node) {
1176                 block_group = rb_entry(node, struct btrfs_block_group_cache,
1177                                        cache_node);
1178                 ret = populate_free_space_tree(trans, fs_info, block_group);
1179                 if (ret)
1180                         goto abort;
1181                 node = rb_next(node);
1182         }
1183
1184         btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1185         fs_info->creating_free_space_tree = 0;
1186
1187         ret = btrfs_commit_transaction(trans, tree_root);
1188         if (ret)
1189                 return ret;
1190
1191         return 0;
1192
1193 abort:
1194         fs_info->creating_free_space_tree = 0;
1195         btrfs_abort_transaction(trans, ret);
1196         btrfs_end_transaction(trans, tree_root);
1197         return ret;
1198 }
1199
1200 static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1201                                  struct btrfs_root *root)
1202 {
1203         struct btrfs_path *path;
1204         struct btrfs_key key;
1205         int nr;
1206         int ret;
1207
1208         path = btrfs_alloc_path();
1209         if (!path)
1210                 return -ENOMEM;
1211
1212         path->leave_spinning = 1;
1213
1214         key.objectid = 0;
1215         key.type = 0;
1216         key.offset = 0;
1217
1218         while (1) {
1219                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1220                 if (ret < 0)
1221                         goto out;
1222
1223                 nr = btrfs_header_nritems(path->nodes[0]);
1224                 if (!nr)
1225                         break;
1226
1227                 path->slots[0] = 0;
1228                 ret = btrfs_del_items(trans, root, path, 0, nr);
1229                 if (ret)
1230                         goto out;
1231
1232                 btrfs_release_path(path);
1233         }
1234
1235         ret = 0;
1236 out:
1237         btrfs_free_path(path);
1238         return ret;
1239 }
1240
1241 int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
1242 {
1243         struct btrfs_trans_handle *trans;
1244         struct btrfs_root *tree_root = fs_info->tree_root;
1245         struct btrfs_root *free_space_root = fs_info->free_space_root;
1246         int ret;
1247
1248         trans = btrfs_start_transaction(tree_root, 0);
1249         if (IS_ERR(trans))
1250                 return PTR_ERR(trans);
1251
1252         btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1253         fs_info->free_space_root = NULL;
1254
1255         ret = clear_free_space_tree(trans, free_space_root);
1256         if (ret)
1257                 goto abort;
1258
1259         ret = btrfs_del_root(trans, tree_root, &free_space_root->root_key);
1260         if (ret)
1261                 goto abort;
1262
1263         list_del(&free_space_root->dirty_list);
1264
1265         btrfs_tree_lock(free_space_root->node);
1266         clean_tree_block(trans, tree_root->fs_info, free_space_root->node);
1267         btrfs_tree_unlock(free_space_root->node);
1268         btrfs_free_tree_block(trans, free_space_root, free_space_root->node,
1269                               0, 1);
1270
1271         free_extent_buffer(free_space_root->node);
1272         free_extent_buffer(free_space_root->commit_root);
1273         kfree(free_space_root);
1274
1275         ret = btrfs_commit_transaction(trans, tree_root);
1276         if (ret)
1277                 return ret;
1278
1279         return 0;
1280
1281 abort:
1282         btrfs_abort_transaction(trans, ret);
1283         btrfs_end_transaction(trans, tree_root);
1284         return ret;
1285 }
1286
1287 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
1288                                         struct btrfs_fs_info *fs_info,
1289                                         struct btrfs_block_group_cache *block_group,
1290                                         struct btrfs_path *path)
1291 {
1292         u64 start, end;
1293         int ret;
1294
1295         start = block_group->key.objectid;
1296         end = block_group->key.objectid + block_group->key.offset;
1297
1298         block_group->needs_free_space = 0;
1299
1300         ret = add_new_free_space_info(trans, fs_info, block_group, path);
1301         if (ret)
1302                 return ret;
1303
1304         return __add_to_free_space_tree(trans, fs_info, block_group, path,
1305                                         block_group->key.objectid,
1306                                         block_group->key.offset);
1307 }
1308
1309 int add_block_group_free_space(struct btrfs_trans_handle *trans,
1310                                struct btrfs_fs_info *fs_info,
1311                                struct btrfs_block_group_cache *block_group)
1312 {
1313         struct btrfs_path *path = NULL;
1314         int ret = 0;
1315
1316         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1317                 return 0;
1318
1319         mutex_lock(&block_group->free_space_lock);
1320         if (!block_group->needs_free_space)
1321                 goto out;
1322
1323         path = btrfs_alloc_path();
1324         if (!path) {
1325                 ret = -ENOMEM;
1326                 goto out;
1327         }
1328
1329         ret = __add_block_group_free_space(trans, fs_info, block_group, path);
1330
1331 out:
1332         btrfs_free_path(path);
1333         mutex_unlock(&block_group->free_space_lock);
1334         if (ret)
1335                 btrfs_abort_transaction(trans, ret);
1336         return ret;
1337 }
1338
1339 int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1340                                   struct btrfs_fs_info *fs_info,
1341                                   struct btrfs_block_group_cache *block_group)
1342 {
1343         struct btrfs_root *root = fs_info->free_space_root;
1344         struct btrfs_path *path;
1345         struct btrfs_key key, found_key;
1346         struct extent_buffer *leaf;
1347         u64 start, end;
1348         int done = 0, nr;
1349         int ret;
1350
1351         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1352                 return 0;
1353
1354         if (block_group->needs_free_space) {
1355                 /* We never added this block group to the free space tree. */
1356                 return 0;
1357         }
1358
1359         path = btrfs_alloc_path();
1360         if (!path) {
1361                 ret = -ENOMEM;
1362                 goto out;
1363         }
1364
1365         start = block_group->key.objectid;
1366         end = block_group->key.objectid + block_group->key.offset;
1367
1368         key.objectid = end - 1;
1369         key.type = (u8)-1;
1370         key.offset = (u64)-1;
1371
1372         while (!done) {
1373                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1374                 if (ret)
1375                         goto out;
1376
1377                 leaf = path->nodes[0];
1378                 nr = 0;
1379                 path->slots[0]++;
1380                 while (path->slots[0] > 0) {
1381                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1382
1383                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1384                                 ASSERT(found_key.objectid == block_group->key.objectid);
1385                                 ASSERT(found_key.offset == block_group->key.offset);
1386                                 done = 1;
1387                                 nr++;
1388                                 path->slots[0]--;
1389                                 break;
1390                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1391                                    found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1392                                 ASSERT(found_key.objectid >= start);
1393                                 ASSERT(found_key.objectid < end);
1394                                 ASSERT(found_key.objectid + found_key.offset <= end);
1395                                 nr++;
1396                                 path->slots[0]--;
1397                         } else {
1398                                 ASSERT(0);
1399                         }
1400                 }
1401
1402                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1403                 if (ret)
1404                         goto out;
1405                 btrfs_release_path(path);
1406         }
1407
1408         ret = 0;
1409 out:
1410         btrfs_free_path(path);
1411         if (ret)
1412                 btrfs_abort_transaction(trans, ret);
1413         return ret;
1414 }
1415
1416 static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1417                                    struct btrfs_path *path,
1418                                    u32 expected_extent_count)
1419 {
1420         struct btrfs_block_group_cache *block_group;
1421         struct btrfs_fs_info *fs_info;
1422         struct btrfs_root *root;
1423         struct btrfs_key key;
1424         int prev_bit = 0, bit;
1425         /* Initialize to silence GCC. */
1426         u64 extent_start = 0;
1427         u64 end, offset;
1428         u64 total_found = 0;
1429         u32 extent_count = 0;
1430         int ret;
1431
1432         block_group = caching_ctl->block_group;
1433         fs_info = block_group->fs_info;
1434         root = fs_info->free_space_root;
1435
1436         end = block_group->key.objectid + block_group->key.offset;
1437
1438         while (1) {
1439                 ret = btrfs_next_item(root, path);
1440                 if (ret < 0)
1441                         goto out;
1442                 if (ret)
1443                         break;
1444
1445                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1446
1447                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1448                         break;
1449
1450                 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1451                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1452
1453                 caching_ctl->progress = key.objectid;
1454
1455                 offset = key.objectid;
1456                 while (offset < key.objectid + key.offset) {
1457                         bit = free_space_test_bit(block_group, path, offset);
1458                         if (prev_bit == 0 && bit == 1) {
1459                                 extent_start = offset;
1460                         } else if (prev_bit == 1 && bit == 0) {
1461                                 total_found += add_new_free_space(block_group,
1462                                                                   fs_info,
1463                                                                   extent_start,
1464                                                                   offset);
1465                                 if (total_found > CACHING_CTL_WAKE_UP) {
1466                                         total_found = 0;
1467                                         wake_up(&caching_ctl->wait);
1468                                 }
1469                                 extent_count++;
1470                         }
1471                         prev_bit = bit;
1472                         offset += block_group->sectorsize;
1473                 }
1474         }
1475         if (prev_bit == 1) {
1476                 total_found += add_new_free_space(block_group, fs_info,
1477                                                   extent_start, end);
1478                 extent_count++;
1479         }
1480
1481         if (extent_count != expected_extent_count) {
1482                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
1483                           block_group->key.objectid, extent_count,
1484                           expected_extent_count);
1485                 ASSERT(0);
1486                 ret = -EIO;
1487                 goto out;
1488         }
1489
1490         caching_ctl->progress = (u64)-1;
1491
1492         ret = 0;
1493 out:
1494         return ret;
1495 }
1496
1497 static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1498                                    struct btrfs_path *path,
1499                                    u32 expected_extent_count)
1500 {
1501         struct btrfs_block_group_cache *block_group;
1502         struct btrfs_fs_info *fs_info;
1503         struct btrfs_root *root;
1504         struct btrfs_key key;
1505         u64 end;
1506         u64 total_found = 0;
1507         u32 extent_count = 0;
1508         int ret;
1509
1510         block_group = caching_ctl->block_group;
1511         fs_info = block_group->fs_info;
1512         root = fs_info->free_space_root;
1513
1514         end = block_group->key.objectid + block_group->key.offset;
1515
1516         while (1) {
1517                 ret = btrfs_next_item(root, path);
1518                 if (ret < 0)
1519                         goto out;
1520                 if (ret)
1521                         break;
1522
1523                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1524
1525                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1526                         break;
1527
1528                 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1529                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1530
1531                 caching_ctl->progress = key.objectid;
1532
1533                 total_found += add_new_free_space(block_group, fs_info,
1534                                                   key.objectid,
1535                                                   key.objectid + key.offset);
1536                 if (total_found > CACHING_CTL_WAKE_UP) {
1537                         total_found = 0;
1538                         wake_up(&caching_ctl->wait);
1539                 }
1540                 extent_count++;
1541         }
1542
1543         if (extent_count != expected_extent_count) {
1544                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
1545                           block_group->key.objectid, extent_count,
1546                           expected_extent_count);
1547                 ASSERT(0);
1548                 ret = -EIO;
1549                 goto out;
1550         }
1551
1552         caching_ctl->progress = (u64)-1;
1553
1554         ret = 0;
1555 out:
1556         return ret;
1557 }
1558
1559 int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1560 {
1561         struct btrfs_block_group_cache *block_group;
1562         struct btrfs_fs_info *fs_info;
1563         struct btrfs_free_space_info *info;
1564         struct btrfs_path *path;
1565         u32 extent_count, flags;
1566         int ret;
1567
1568         block_group = caching_ctl->block_group;
1569         fs_info = block_group->fs_info;
1570
1571         path = btrfs_alloc_path();
1572         if (!path)
1573                 return -ENOMEM;
1574
1575         /*
1576          * Just like caching_thread() doesn't want to deadlock on the extent
1577          * tree, we don't want to deadlock on the free space tree.
1578          */
1579         path->skip_locking = 1;
1580         path->search_commit_root = 1;
1581         path->reada = 1;
1582
1583         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
1584         if (IS_ERR(info)) {
1585                 ret = PTR_ERR(info);
1586                 goto out;
1587         }
1588         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1589         flags = btrfs_free_space_flags(path->nodes[0], info);
1590
1591         /*
1592          * We left path pointing to the free space info item, so now
1593          * load_free_space_foo can just iterate through the free space tree from
1594          * there.
1595          */
1596         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1597                 ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1598         else
1599                 ret = load_free_space_extents(caching_ctl, path, extent_count);
1600
1601 out:
1602         btrfs_free_path(path);
1603         return ret;
1604 }