fs/btrfs/free-space-tree.c

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