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