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 #include "sysfs.h"
  27
  28 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
  29                                         struct btrfs_fs_info *fs_info,
  30                                         struct btrfs_block_group_cache *block_group,
  31                                         struct btrfs_path *path);
  32
  33 void set_free_space_tree_thresholds(struct btrfs_block_group_cache *cache)
  34 {
  35         u32 bitmap_range;
  36         size_t bitmap_size;
  37         u64 num_bitmaps, total_bitmap_size;
  38
  39         /*
  40          * We convert to bitmaps when the disk space required for using extents
  41          * exceeds that required for using bitmaps.
  42          */
  43         bitmap_range = cache->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
  44         num_bitmaps = div_u64(cache->key.offset + bitmap_range - 1,
  45                               bitmap_range);
  46         bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
  47         total_bitmap_size = num_bitmaps * bitmap_size;
  48         cache->bitmap_high_thresh = div_u64(total_bitmap_size,
  49                                             sizeof(struct btrfs_item));
  50
  51         /*
  52          * We allow for a small buffer between the high threshold and low
  53          * threshold to avoid thrashing back and forth between the two formats.
  54          */
  55         if (cache->bitmap_high_thresh > 100)
  56                 cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
  57         else
  58                 cache->bitmap_low_thresh = 0;
  59 }
  60
  61 static int add_new_free_space_info(struct btrfs_trans_handle *trans,
  62                                    struct btrfs_fs_info *fs_info,
  63                                    struct btrfs_block_group_cache *block_group,
  64                                    struct btrfs_path *path)
  65 {
  66         struct btrfs_root *root = fs_info->free_space_root;
  67         struct btrfs_free_space_info *info;
  68         struct btrfs_key key;
  69         struct extent_buffer *leaf;
  70         int ret;
  71
  72         key.objectid = block_group->key.objectid;
  73         key.type = BTRFS_FREE_SPACE_INFO_KEY;
  74         key.offset = block_group->key.offset;
  75
  76         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
  77         if (ret)
  78                 goto out;
  79
  80         leaf = path->nodes[0];
  81         info = btrfs_item_ptr(leaf, path->slots[0],
  82                               struct btrfs_free_space_info);
  83         btrfs_set_free_space_extent_count(leaf, info, 0);
  84         btrfs_set_free_space_flags(leaf, info, 0);
  85         btrfs_mark_buffer_dirty(leaf);
  86
  87         ret = 0;
  88 out:
  89         btrfs_release_path(path);
  90         return ret;
  91 }
  92
  93 struct btrfs_free_space_info *
  94 search_free_space_info(struct btrfs_trans_handle *trans,
  95                        struct btrfs_fs_info *fs_info,
  96                        struct btrfs_block_group_cache *block_group,
  97                        struct btrfs_path *path, int cow)
  98 {
  99         struct btrfs_root *root = fs_info->free_space_root;
 100         struct btrfs_key key;
 101         int ret;
 102
 103         key.objectid = block_group->key.objectid;
 104         key.type = BTRFS_FREE_SPACE_INFO_KEY;
 105         key.offset = block_group->key.offset;
 106
 107         ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
 108         if (ret < 0)
 109                 return ERR_PTR(ret);
 110         if (ret != 0) {
 111                 btrfs_warn(fs_info, "missing free space info for %llu\n",
 112                            block_group->key.objectid);
 113                 ASSERT(0);
 114                 return ERR_PTR(-ENOENT);
 115         }
 116
 117         return btrfs_item_ptr(path->nodes[0], path->slots[0],
 118                               struct btrfs_free_space_info);
 119 }
 120
 121 /*
 122  * btrfs_search_slot() but we're looking for the greatest key less than the
 123  * passed key.
 124  */
 125 static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
 126                                   struct btrfs_root *root,
 127                                   struct btrfs_key *key, struct btrfs_path *p,
 128                                   int ins_len, int cow)
 129 {
 130         int ret;
 131
 132         ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
 133         if (ret < 0)
 134                 return ret;
 135
 136         if (ret == 0) {
 137                 ASSERT(0);
 138                 return -EIO;
 139         }
 140
 141         if (p->slots[0] == 0) {
 142                 ASSERT(0);
 143                 return -EIO;
 144         }
 145         p->slots[0]--;
 146
 147         return 0;
 148 }
 149
 150 static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize)
 151 {
 152         return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE);
 153 }
 154
 155 static unsigned long *alloc_bitmap(u32 bitmap_size)
 156 {
 157         void *mem;
 158
 159         /*
 160          * The allocation size varies, observed numbers were < 4K up to 16K.
 161          * Using vmalloc unconditionally would be too heavy, we'll try
 162          * contiguous allocations first.
 163          */
 164         if  (bitmap_size <= PAGE_SIZE)
 165                 return kzalloc(bitmap_size, GFP_NOFS);
 166
 167         mem = kzalloc(bitmap_size, GFP_NOFS | __GFP_NOWARN);
 168         if (mem)
 169                 return mem;
 170
 171         return __vmalloc(bitmap_size, GFP_NOFS | __GFP_HIGHMEM | __GFP_ZERO,
 172                          PAGE_KERNEL);
 173 }
 174
 175 int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
 176                                   struct btrfs_fs_info *fs_info,
 177                                   struct btrfs_block_group_cache *block_group,
 178                                   struct btrfs_path *path)
 179 {
 180         struct btrfs_root *root = fs_info->free_space_root;
 181         struct btrfs_free_space_info *info;
 182         struct btrfs_key key, found_key;
 183         struct extent_buffer *leaf;
 184         unsigned long *bitmap;
 185         char *bitmap_cursor;
 186         u64 start, end;
 187         u64 bitmap_range, i;
 188         u32 bitmap_size, flags, expected_extent_count;
 189         u32 extent_count = 0;
 190         int done = 0, nr;
 191         int ret;
 192
 193         bitmap_size = free_space_bitmap_size(block_group->key.offset,
 194                                              block_group->sectorsize);
 195         bitmap = alloc_bitmap(bitmap_size);
 196         if (!bitmap) {
 197                 ret = -ENOMEM;
 198                 goto out;
 199         }
 200
 201         start = block_group->key.objectid;
 202         end = block_group->key.objectid + block_group->key.offset;
 203
 204         key.objectid = end - 1;
 205         key.type = (u8)-1;
 206         key.offset = (u64)-1;
 207
 208         while (!done) {
 209                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 210                 if (ret)
 211                         goto out;
 212
 213                 leaf = path->nodes[0];
 214                 nr = 0;
 215                 path->slots[0]++;
 216                 while (path->slots[0] > 0) {
 217                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
 218
 219                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
 220                                 ASSERT(found_key.objectid == block_group->key.objectid);
 221                                 ASSERT(found_key.offset == block_group->key.offset);
 222                                 done = 1;
 223                                 break;
 224                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
 225                                 u64 first, last;
 226
 227                                 ASSERT(found_key.objectid >= start);
 228                                 ASSERT(found_key.objectid < end);
 229                                 ASSERT(found_key.objectid + found_key.offset <= end);
 230
 231                                 first = div_u64(found_key.objectid - start,
 232                                                 block_group->sectorsize);
 233                                 last = div_u64(found_key.objectid + found_key.offset - start,
 234                                                block_group->sectorsize);
 235                                 bitmap_set(bitmap, first, last - first);
 236
 237                                 extent_count++;
 238                                 nr++;
 239                                 path->slots[0]--;
 240                         } else {
 241                                 ASSERT(0);
 242                         }
 243                 }
 244
 245                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
 246                 if (ret)
 247                         goto out;
 248                 btrfs_release_path(path);
 249         }
 250
 251         info = search_free_space_info(trans, fs_info, block_group, path, 1);
 252         if (IS_ERR(info)) {
 253                 ret = PTR_ERR(info);
 254                 goto out;
 255         }
 256         leaf = path->nodes[0];
 257         flags = btrfs_free_space_flags(leaf, info);
 258         flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
 259         btrfs_set_free_space_flags(leaf, info, flags);
 260         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
 261         btrfs_mark_buffer_dirty(leaf);
 262         btrfs_release_path(path);
 263
 264         if (extent_count != expected_extent_count) {
 265                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
 266                           block_group->key.objectid, extent_count,
 267                           expected_extent_count);
 268                 ASSERT(0);
 269                 ret = -EIO;
 270                 goto out;
 271         }
 272
 273         bitmap_cursor = (char *)bitmap;
 274         bitmap_range = block_group->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
 275         i = start;
 276         while (i < end) {
 277                 unsigned long ptr;
 278                 u64 extent_size;
 279                 u32 data_size;
 280
 281                 extent_size = min(end - i, bitmap_range);
 282                 data_size = free_space_bitmap_size(extent_size,
 283                                                    block_group->sectorsize);
 284
 285                 key.objectid = i;
 286                 key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
 287                 key.offset = extent_size;
 288
 289                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 290                                               data_size);
 291                 if (ret)
 292                         goto out;
 293
 294                 leaf = path->nodes[0];
 295                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
 296                 write_extent_buffer(leaf, bitmap_cursor, ptr,
 297                                     data_size);
 298                 btrfs_mark_buffer_dirty(leaf);
 299                 btrfs_release_path(path);
 300
 301                 i += extent_size;
 302                 bitmap_cursor += data_size;
 303         }
 304
 305         ret = 0;
 306 out:
 307         kvfree(bitmap);
 308         if (ret)
 309                 btrfs_abort_transaction(trans, root, ret);
 310         return ret;
 311 }
 312
 313 int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
 314                                   struct btrfs_fs_info *fs_info,
 315                                   struct btrfs_block_group_cache *block_group,
 316                                   struct btrfs_path *path)
 317 {
 318         struct btrfs_root *root = fs_info->free_space_root;
 319         struct btrfs_free_space_info *info;
 320         struct btrfs_key key, found_key;
 321         struct extent_buffer *leaf;
 322         unsigned long *bitmap;
 323         u64 start, end;
 324         /* Initialize to silence GCC. */
 325         u64 extent_start = 0;
 326         u64 offset;
 327         u32 bitmap_size, flags, expected_extent_count;
 328         int prev_bit = 0, bit, bitnr;
 329         u32 extent_count = 0;
 330         int done = 0, nr;
 331         int ret;
 332
 333         bitmap_size = free_space_bitmap_size(block_group->key.offset,
 334                                              block_group->sectorsize);
 335         bitmap = alloc_bitmap(bitmap_size);
 336         if (!bitmap) {
 337                 ret = -ENOMEM;
 338                 goto out;
 339         }
 340
 341         start = block_group->key.objectid;
 342         end = block_group->key.objectid + block_group->key.offset;
 343
 344         key.objectid = end - 1;
 345         key.type = (u8)-1;
 346         key.offset = (u64)-1;
 347
 348         while (!done) {
 349                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
 350                 if (ret)
 351                         goto out;
 352
 353                 leaf = path->nodes[0];
 354                 nr = 0;
 355                 path->slots[0]++;
 356                 while (path->slots[0] > 0) {
 357                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
 358
 359                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
 360                                 ASSERT(found_key.objectid == block_group->key.objectid);
 361                                 ASSERT(found_key.offset == block_group->key.offset);
 362                                 done = 1;
 363                                 break;
 364                         } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
 365                                 unsigned long ptr;
 366                                 char *bitmap_cursor;
 367                                 u32 bitmap_pos, data_size;
 368
 369                                 ASSERT(found_key.objectid >= start);
 370                                 ASSERT(found_key.objectid < end);
 371                                 ASSERT(found_key.objectid + found_key.offset <= end);
 372
 373                                 bitmap_pos = div_u64(found_key.objectid - start,
 374                                                      block_group->sectorsize *
 375                                                      BITS_PER_BYTE);
 376                                 bitmap_cursor = ((char *)bitmap) + bitmap_pos;
 377                                 data_size = free_space_bitmap_size(found_key.offset,
 378                                                                    block_group->sectorsize);
 379
 380                                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
 381                                 read_extent_buffer(leaf, bitmap_cursor, ptr,
 382                                                    data_size);
 383
 384                                 nr++;
 385                                 path->slots[0]--;
 386                         } else {
 387                                 ASSERT(0);
 388                         }
 389                 }
 390
 391                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
 392                 if (ret)
 393                         goto out;
 394                 btrfs_release_path(path);
 395         }
 396
 397         info = search_free_space_info(trans, fs_info, block_group, path, 1);
 398         if (IS_ERR(info)) {
 399                 ret = PTR_ERR(info);
 400                 goto out;
 401         }
 402         leaf = path->nodes[0];
 403         flags = btrfs_free_space_flags(leaf, info);
 404         flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
 405         btrfs_set_free_space_flags(leaf, info, flags);
 406         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
 407         btrfs_mark_buffer_dirty(leaf);
 408         btrfs_release_path(path);
 409
 410         offset = start;
 411         bitnr = 0;
 412         while (offset < end) {
 413                 bit = !!test_bit(bitnr, bitmap);
 414                 if (prev_bit == 0 && bit == 1) {
 415                         extent_start = offset;
 416                 } else if (prev_bit == 1 && bit == 0) {
 417                         key.objectid = extent_start;
 418                         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 419                         key.offset = offset - extent_start;
 420
 421                         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 422                         if (ret)
 423                                 goto out;
 424                         btrfs_release_path(path);
 425
 426                         extent_count++;
 427                 }
 428                 prev_bit = bit;
 429                 offset += block_group->sectorsize;
 430                 bitnr++;
 431         }
 432         if (prev_bit == 1) {
 433                 key.objectid = extent_start;
 434                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
 435                 key.offset = end - extent_start;
 436
 437                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 438                 if (ret)
 439                         goto out;
 440                 btrfs_release_path(path);
 441
 442                 extent_count++;
 443         }
 444
 445         if (extent_count != expected_extent_count) {
 446                 btrfs_err(fs_info, "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, root, 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, fs_info->free_space_root, 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, fs_info->free_space_root, 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         fs_info->creating_free_space_tree = 1;
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_sysfs_feature_update(fs_info,
1188                 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE, FEAT_COMPAT_RO);
1189
1190         fs_info->creating_free_space_tree = 0;
1191
1192         ret = btrfs_commit_transaction(trans, tree_root);
1193         if (ret)
1194                 return ret;
1195
1196         return 0;
1197
1198 abort:
1199         fs_info->creating_free_space_tree = 0;
1200         btrfs_abort_transaction(trans, tree_root, ret);
1201         btrfs_end_transaction(trans, tree_root);
1202         return ret;
1203 }
1204
1205 static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1206                                  struct btrfs_root *root)
1207 {
1208         struct btrfs_path *path;
1209         struct btrfs_key key;
1210         int nr;
1211         int ret;
1212
1213         path = btrfs_alloc_path();
1214         if (!path)
1215                 return -ENOMEM;
1216
1217         path->leave_spinning = 1;
1218
1219         key.objectid = 0;
1220         key.type = 0;
1221         key.offset = 0;
1222
1223         while (1) {
1224                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1225                 if (ret < 0)
1226                         goto out;
1227
1228                 nr = btrfs_header_nritems(path->nodes[0]);
1229                 if (!nr)
1230                         break;
1231
1232                 path->slots[0] = 0;
1233                 ret = btrfs_del_items(trans, root, path, 0, nr);
1234                 if (ret)
1235                         goto out;
1236
1237                 btrfs_release_path(path);
1238         }
1239
1240         ret = 0;
1241 out:
1242         btrfs_free_path(path);
1243         return ret;
1244 }
1245
1246 int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
1247 {
1248         struct btrfs_trans_handle *trans;
1249         struct btrfs_root *tree_root = fs_info->tree_root;
1250         struct btrfs_root *free_space_root = fs_info->free_space_root;
1251         int ret;
1252
1253         trans = btrfs_start_transaction(tree_root, 0);
1254         if (IS_ERR(trans))
1255                 return PTR_ERR(trans);
1256
1257         btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1258         btrfs_sysfs_feature_update(fs_info,
1259                 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE, FEAT_COMPAT_RO);
1260
1261         fs_info->free_space_root = NULL;
1262
1263         ret = clear_free_space_tree(trans, free_space_root);
1264         if (ret)
1265                 goto abort;
1266
1267         ret = btrfs_del_root(trans, tree_root, &free_space_root->root_key);
1268         if (ret)
1269                 goto abort;
1270
1271         list_del(&free_space_root->dirty_list);
1272
1273         btrfs_tree_lock(free_space_root->node);
1274         clean_tree_block(trans, tree_root->fs_info, free_space_root->node);
1275         btrfs_tree_unlock(free_space_root->node);
1276         btrfs_free_tree_block(trans, free_space_root, free_space_root->node,
1277                               0, 1);
1278
1279         free_extent_buffer(free_space_root->node);
1280         free_extent_buffer(free_space_root->commit_root);
1281         kfree(free_space_root);
1282
1283         ret = btrfs_commit_transaction(trans, tree_root);
1284         if (ret)
1285                 return ret;
1286
1287         return 0;
1288
1289 abort:
1290         btrfs_abort_transaction(trans, tree_root, ret);
1291         btrfs_end_transaction(trans, tree_root);
1292         return ret;
1293 }
1294
1295 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
1296                                         struct btrfs_fs_info *fs_info,
1297                                         struct btrfs_block_group_cache *block_group,
1298                                         struct btrfs_path *path)
1299 {
1300         u64 start, end;
1301         int ret;
1302
1303         start = block_group->key.objectid;
1304         end = block_group->key.objectid + block_group->key.offset;
1305
1306         block_group->needs_free_space = 0;
1307
1308         ret = add_new_free_space_info(trans, fs_info, block_group, path);
1309         if (ret)
1310                 return ret;
1311
1312         return __add_to_free_space_tree(trans, fs_info, block_group, path,
1313                                         block_group->key.objectid,
1314                                         block_group->key.offset);
1315 }
1316
1317 int add_block_group_free_space(struct btrfs_trans_handle *trans,
1318                                struct btrfs_fs_info *fs_info,
1319                                struct btrfs_block_group_cache *block_group)
1320 {
1321         struct btrfs_path *path = NULL;
1322         int ret = 0;
1323
1324         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1325                 return 0;
1326
1327         mutex_lock(&block_group->free_space_lock);
1328         if (!block_group->needs_free_space)
1329                 goto out;
1330
1331         path = btrfs_alloc_path();
1332         if (!path) {
1333                 ret = -ENOMEM;
1334                 goto out;
1335         }
1336
1337         ret = __add_block_group_free_space(trans, fs_info, block_group, path);
1338
1339 out:
1340         btrfs_free_path(path);
1341         mutex_unlock(&block_group->free_space_lock);
1342         if (ret)
1343                 btrfs_abort_transaction(trans, fs_info->free_space_root, ret);
1344         return ret;
1345 }
1346
1347 int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1348                                   struct btrfs_fs_info *fs_info,
1349                                   struct btrfs_block_group_cache *block_group)
1350 {
1351         struct btrfs_root *root = fs_info->free_space_root;
1352         struct btrfs_path *path;
1353         struct btrfs_key key, found_key;
1354         struct extent_buffer *leaf;
1355         u64 start, end;
1356         int done = 0, nr;
1357         int ret;
1358
1359         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1360                 return 0;
1361
1362         if (block_group->needs_free_space) {
1363                 /* We never added this block group to the free space tree. */
1364                 return 0;
1365         }
1366
1367         path = btrfs_alloc_path();
1368         if (!path) {
1369                 ret = -ENOMEM;
1370                 goto out;
1371         }
1372
1373         start = block_group->key.objectid;
1374         end = block_group->key.objectid + block_group->key.offset;
1375
1376         key.objectid = end - 1;
1377         key.type = (u8)-1;
1378         key.offset = (u64)-1;
1379
1380         while (!done) {
1381                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1382                 if (ret)
1383                         goto out;
1384
1385                 leaf = path->nodes[0];
1386                 nr = 0;
1387                 path->slots[0]++;
1388                 while (path->slots[0] > 0) {
1389                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1390
1391                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1392                                 ASSERT(found_key.objectid == block_group->key.objectid);
1393                                 ASSERT(found_key.offset == block_group->key.offset);
1394                                 done = 1;
1395                                 nr++;
1396                                 path->slots[0]--;
1397                                 break;
1398                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1399                                    found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1400                                 ASSERT(found_key.objectid >= start);
1401                                 ASSERT(found_key.objectid < end);
1402                                 ASSERT(found_key.objectid + found_key.offset <= end);
1403                                 nr++;
1404                                 path->slots[0]--;
1405                         } else {
1406                                 ASSERT(0);
1407                         }
1408                 }
1409
1410                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1411                 if (ret)
1412                         goto out;
1413                 btrfs_release_path(path);
1414         }
1415
1416         ret = 0;
1417 out:
1418         btrfs_free_path(path);
1419         if (ret)
1420                 btrfs_abort_transaction(trans, root, ret);
1421         return ret;
1422 }
1423
1424 static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1425                                    struct btrfs_path *path,
1426                                    u32 expected_extent_count)
1427 {
1428         struct btrfs_block_group_cache *block_group;
1429         struct btrfs_fs_info *fs_info;
1430         struct btrfs_root *root;
1431         struct btrfs_key key;
1432         int prev_bit = 0, bit;
1433         /* Initialize to silence GCC. */
1434         u64 extent_start = 0;
1435         u64 end, offset;
1436         u64 total_found = 0;
1437         u32 extent_count = 0;
1438         int ret;
1439
1440         block_group = caching_ctl->block_group;
1441         fs_info = block_group->fs_info;
1442         root = fs_info->free_space_root;
1443
1444         end = block_group->key.objectid + block_group->key.offset;
1445
1446         while (1) {
1447                 ret = btrfs_next_item(root, path);
1448                 if (ret < 0)
1449                         goto out;
1450                 if (ret)
1451                         break;
1452
1453                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1454
1455                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1456                         break;
1457
1458                 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1459                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1460
1461                 caching_ctl->progress = key.objectid;
1462
1463                 offset = key.objectid;
1464                 while (offset < key.objectid + key.offset) {
1465                         bit = free_space_test_bit(block_group, path, offset);
1466                         if (prev_bit == 0 && bit == 1) {
1467                                 extent_start = offset;
1468                         } else if (prev_bit == 1 && bit == 0) {
1469                                 total_found += add_new_free_space(block_group,
1470                                                                   fs_info,
1471                                                                   extent_start,
1472                                                                   offset);
1473                                 if (total_found > CACHING_CTL_WAKE_UP) {
1474                                         total_found = 0;
1475                                         wake_up(&caching_ctl->wait);
1476                                 }
1477                                 extent_count++;
1478                         }
1479                         prev_bit = bit;
1480                         offset += block_group->sectorsize;
1481                 }
1482         }
1483         if (prev_bit == 1) {
1484                 total_found += add_new_free_space(block_group, fs_info,
1485                                                   extent_start, end);
1486                 extent_count++;
1487         }
1488
1489         if (extent_count != expected_extent_count) {
1490                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
1491                           block_group->key.objectid, extent_count,
1492                           expected_extent_count);
1493                 ASSERT(0);
1494                 ret = -EIO;
1495                 goto out;
1496         }
1497
1498         caching_ctl->progress = (u64)-1;
1499
1500         ret = 0;
1501 out:
1502         return ret;
1503 }
1504
1505 static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1506                                    struct btrfs_path *path,
1507                                    u32 expected_extent_count)
1508 {
1509         struct btrfs_block_group_cache *block_group;
1510         struct btrfs_fs_info *fs_info;
1511         struct btrfs_root *root;
1512         struct btrfs_key key;
1513         u64 end;
1514         u64 total_found = 0;
1515         u32 extent_count = 0;
1516         int ret;
1517
1518         block_group = caching_ctl->block_group;
1519         fs_info = block_group->fs_info;
1520         root = fs_info->free_space_root;
1521
1522         end = block_group->key.objectid + block_group->key.offset;
1523
1524         while (1) {
1525                 ret = btrfs_next_item(root, path);
1526                 if (ret < 0)
1527                         goto out;
1528                 if (ret)
1529                         break;
1530
1531                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1532
1533                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1534                         break;
1535
1536                 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1537                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1538
1539                 caching_ctl->progress = key.objectid;
1540
1541                 total_found += add_new_free_space(block_group, fs_info,
1542                                                   key.objectid,
1543                                                   key.objectid + key.offset);
1544                 if (total_found > CACHING_CTL_WAKE_UP) {
1545                         total_found = 0;
1546                         wake_up(&caching_ctl->wait);
1547                 }
1548                 extent_count++;
1549         }
1550
1551         if (extent_count != expected_extent_count) {
1552                 btrfs_err(fs_info, "incorrect extent count for %llu; counted %u, expected %u",
1553                           block_group->key.objectid, extent_count,
1554                           expected_extent_count);
1555                 ASSERT(0);
1556                 ret = -EIO;
1557                 goto out;
1558         }
1559
1560         caching_ctl->progress = (u64)-1;
1561
1562         ret = 0;
1563 out:
1564         return ret;
1565 }
1566
1567 int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1568 {
1569         struct btrfs_block_group_cache *block_group;
1570         struct btrfs_fs_info *fs_info;
1571         struct btrfs_free_space_info *info;
1572         struct btrfs_path *path;
1573         u32 extent_count, flags;
1574         int ret;
1575
1576         block_group = caching_ctl->block_group;
1577         fs_info = block_group->fs_info;
1578
1579         path = btrfs_alloc_path();
1580         if (!path)
1581                 return -ENOMEM;
1582
1583         /*
1584          * Just like caching_thread() doesn't want to deadlock on the extent
1585          * tree, we don't want to deadlock on the free space tree.
1586          */
1587         path->skip_locking = 1;
1588         path->search_commit_root = 1;
1589         path->reada = 1;
1590
1591         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
1592         if (IS_ERR(info)) {
1593                 ret = PTR_ERR(info);
1594                 goto out;
1595         }
1596         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1597         flags = btrfs_free_space_flags(path->nodes[0], info);
1598
1599         /*
1600          * We left path pointing to the free space info item, so now
1601          * load_free_space_foo can just iterate through the free space tree from
1602          * there.
1603          */
1604         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1605                 ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1606         else
1607                 ret = load_free_space_extents(caching_ctl, path, extent_count);
1608
1609 out:
1610         btrfs_free_path(path);
1611         return ret;
1612 }