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