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