extent-tree.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  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 <stdio.h>
  20 #include <stdlib.h>
  21 #include <stdint.h>
  22 #include <math.h>
  23 #include "kerncompat.h"
  24 #include "radix-tree.h"
  25 #include "ctree.h"
  26 #include "disk-io.h"
  27 #include "print-tree.h"
  28 #include "transaction.h"
  29 #include "crc32c.h"
  30 #include "volumes.h"
  31 #include "free-space-cache.h"
  32 #include "utils.h"
  33
  34 #define PENDING_EXTENT_INSERT 0
  35 #define PENDING_EXTENT_DELETE 1
  36 #define PENDING_BACKREF_UPDATE 2
  37
  38 struct pending_extent_op {
  39         int type;
  40         u64 bytenr;
  41         u64 num_bytes;
  42         u64 flags;
  43         struct btrfs_disk_key key;
  44         int level;
  45 };
  46
  47 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  48                                      struct btrfs_root *root,
  49                                      u64 root_objectid, u64 generation,
  50                                      u64 flags, struct btrfs_disk_key *key,
  51                                      int level, struct btrfs_key *ins);
  52 static int __free_extent(struct btrfs_trans_handle *trans,
  53                          struct btrfs_root *root,
  54                          u64 bytenr, u64 num_bytes, u64 parent,
  55                          u64 root_objectid, u64 owner_objectid,
  56                          u64 owner_offset, int refs_to_drop);
  57 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  58                                  btrfs_root *extent_root);
  59 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  60                                btrfs_root *extent_root);
  61 static struct btrfs_block_group_cache *
  62 btrfs_find_block_group(struct btrfs_root *root, struct btrfs_block_group_cache
  63                        *hint, u64 search_start, int data, int owner);
  64
  65 static int remove_sb_from_cache(struct btrfs_root *root,
  66                                 struct btrfs_block_group_cache *cache)
  67 {
  68         u64 bytenr;
  69         u64 *logical;
  70         int stripe_len;
  71         int i, nr, ret;
  72         struct btrfs_fs_info *fs_info = root->fs_info;
  73         struct extent_io_tree *free_space_cache;
  74
  75         free_space_cache = &fs_info->free_space_cache;
  76         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
  77                 bytenr = btrfs_sb_offset(i);
  78                 ret = btrfs_rmap_block(fs_info, cache->key.objectid, bytenr, 0,
  79                                        &logical, &nr, &stripe_len);
  80                 BUG_ON(ret);
  81                 while (nr--) {
  82                         clear_extent_dirty(free_space_cache, logical[nr],
  83                                 logical[nr] + stripe_len - 1);
  84                 }
  85                 kfree(logical);
  86         }
  87         return 0;
  88 }
  89
  90 static int cache_block_group(struct btrfs_root *root,
  91                              struct btrfs_block_group_cache *block_group)
  92 {
  93         struct btrfs_path *path;
  94         int ret;
  95         struct btrfs_key key;
  96         struct extent_buffer *leaf;
  97         struct extent_io_tree *free_space_cache;
  98         int slot;
  99         u64 last;
 100         u64 hole_size;
 101
 102         if (!block_group)
 103                 return 0;
 104
 105         root = root->fs_info->extent_root;
 106         free_space_cache = &root->fs_info->free_space_cache;
 107
 108         if (block_group->cached)
 109                 return 0;
 110
 111         path = btrfs_alloc_path();
 112         if (!path)
 113                 return -ENOMEM;
 114
 115         path->reada = 2;
 116         last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
 117         key.objectid = last;
 118         key.offset = 0;
 119         key.type = 0;
 120
 121         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 122         if (ret < 0)
 123                 goto err;
 124
 125         while(1) {
 126                 leaf = path->nodes[0];
 127                 slot = path->slots[0];
 128                 if (slot >= btrfs_header_nritems(leaf)) {
 129                         ret = btrfs_next_leaf(root, path);
 130                         if (ret < 0)
 131                                 goto err;
 132                         if (ret == 0) {
 133                                 continue;
 134                         } else {
 135                                 break;
 136                         }
 137                 }
 138                 btrfs_item_key_to_cpu(leaf, &key, slot);
 139                 if (key.objectid < block_group->key.objectid) {
 140                         goto next;
 141                 }
 142                 if (key.objectid >= block_group->key.objectid +
 143                     block_group->key.offset) {
 144                         break;
 145                 }
 146
 147                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
 148                     key.type == BTRFS_METADATA_ITEM_KEY) {
 149                         if (key.objectid > last) {
 150                                 hole_size = key.objectid - last;
 151                                 set_extent_dirty(free_space_cache, last,
 152                                                  last + hole_size - 1);
 153                         }
 154                         if (key.type == BTRFS_METADATA_ITEM_KEY)
 155                                 last = key.objectid + root->fs_info->nodesize;
 156                         else
 157                                 last = key.objectid + key.offset;
 158                 }
 159 next:
 160                 path->slots[0]++;
 161         }
 162
 163         if (block_group->key.objectid +
 164             block_group->key.offset > last) {
 165                 hole_size = block_group->key.objectid +
 166                         block_group->key.offset - last;
 167                 set_extent_dirty(free_space_cache, last, last + hole_size - 1);
 168         }
 169         remove_sb_from_cache(root, block_group);
 170         block_group->cached = 1;
 171 err:
 172         btrfs_free_path(path);
 173         return 0;
 174 }
 175
 176 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
 177                                                        btrfs_fs_info *info,
 178                                                        u64 bytenr)
 179 {
 180         struct extent_io_tree *block_group_cache;
 181         struct btrfs_block_group_cache *block_group = NULL;
 182         u64 ptr;
 183         u64 start;
 184         u64 end;
 185         int ret;
 186
 187         bytenr = max_t(u64, bytenr,
 188                        BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 189         block_group_cache = &info->block_group_cache;
 190         ret = find_first_extent_bit(block_group_cache,
 191                                     bytenr, &start, &end,
 192                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 193                                     BLOCK_GROUP_SYSTEM);
 194         if (ret) {
 195                 return NULL;
 196         }
 197         ret = get_state_private(block_group_cache, start, &ptr);
 198         if (ret)
 199                 return NULL;
 200
 201         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 202         return block_group;
 203 }
 204
 205 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 206                                                          btrfs_fs_info *info,
 207                                                          u64 bytenr)
 208 {
 209         struct extent_io_tree *block_group_cache;
 210         struct btrfs_block_group_cache *block_group = NULL;
 211         u64 ptr;
 212         u64 start;
 213         u64 end;
 214         int ret;
 215
 216         block_group_cache = &info->block_group_cache;
 217         ret = find_first_extent_bit(block_group_cache,
 218                                     bytenr, &start, &end,
 219                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 220                                     BLOCK_GROUP_SYSTEM);
 221         if (ret) {
 222                 return NULL;
 223         }
 224         ret = get_state_private(block_group_cache, start, &ptr);
 225         if (ret)
 226                 return NULL;
 227
 228         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 229         if (block_group->key.objectid <= bytenr && bytenr <
 230             block_group->key.objectid + block_group->key.offset)
 231                 return block_group;
 232         return NULL;
 233 }
 234
 235 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 236 {
 237         return (cache->flags & bits) == bits;
 238 }
 239
 240 static int noinline find_search_start(struct btrfs_root *root,
 241                               struct btrfs_block_group_cache **cache_ret,
 242                               u64 *start_ret, int num, int data)
 243 {
 244         int ret;
 245         struct btrfs_block_group_cache *cache = *cache_ret;
 246         u64 last = *start_ret;
 247         u64 start = 0;
 248         u64 end = 0;
 249         u64 search_start = *start_ret;
 250         int wrapped = 0;
 251
 252         if (!cache)
 253                 goto out;
 254 again:
 255         ret = cache_block_group(root, cache);
 256         if (ret)
 257                 goto out;
 258
 259         last = max(search_start, cache->key.objectid);
 260         if (cache->ro || !block_group_bits(cache, data))
 261                 goto new_group;
 262
 263         while(1) {
 264                 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
 265                                             last, &start, &end, EXTENT_DIRTY);
 266                 if (ret) {
 267                         goto new_group;
 268                 }
 269
 270                 start = max(last, start);
 271                 last = end + 1;
 272                 if (last - start < num) {
 273                         continue;
 274                 }
 275                 if (start + num > cache->key.objectid + cache->key.offset) {
 276                         goto new_group;
 277                 }
 278                 *start_ret = start;
 279                 return 0;
 280         }
 281 out:
 282         *start_ret = last;
 283         cache = btrfs_lookup_block_group(root->fs_info, search_start);
 284         if (!cache) {
 285                 printk("Unable to find block group for %llu\n",
 286                         (unsigned long long)search_start);
 287                 WARN_ON(1);
 288         }
 289         return -ENOSPC;
 290
 291 new_group:
 292         last = cache->key.objectid + cache->key.offset;
 293 wrapped:
 294         cache = btrfs_lookup_first_block_group(root->fs_info, last);
 295         if (!cache) {
 296                 if (!wrapped) {
 297                         wrapped = 1;
 298                         last = search_start;
 299                         goto wrapped;
 300                 }
 301                 goto out;
 302         }
 303         *cache_ret = cache;
 304         goto again;
 305 }
 306
 307 static int block_group_state_bits(u64 flags)
 308 {
 309         int bits = 0;
 310         if (flags & BTRFS_BLOCK_GROUP_DATA)
 311                 bits |= BLOCK_GROUP_DATA;
 312         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 313                 bits |= BLOCK_GROUP_METADATA;
 314         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 315                 bits |= BLOCK_GROUP_SYSTEM;
 316         return bits;
 317 }
 318
 319 static struct btrfs_block_group_cache *
 320 btrfs_find_block_group(struct btrfs_root *root, struct btrfs_block_group_cache
 321                        *hint, u64 search_start, int data, int owner)
 322 {
 323         struct btrfs_block_group_cache *cache;
 324         struct extent_io_tree *block_group_cache;
 325         struct btrfs_block_group_cache *found_group = NULL;
 326         struct btrfs_fs_info *info = root->fs_info;
 327         u64 used;
 328         u64 last = 0;
 329         u64 hint_last;
 330         u64 start;
 331         u64 end;
 332         u64 free_check;
 333         u64 ptr;
 334         int bit;
 335         int ret;
 336         int full_search = 0;
 337         int factor = 10;
 338
 339         block_group_cache = &info->block_group_cache;
 340
 341         if (!owner)
 342                 factor = 10;
 343
 344         bit = block_group_state_bits(data);
 345
 346         if (search_start) {
 347                 struct btrfs_block_group_cache *shint;
 348                 shint = btrfs_lookup_block_group(info, search_start);
 349                 if (shint && !shint->ro && block_group_bits(shint, data)) {
 350                         used = btrfs_block_group_used(&shint->item);
 351                         if (used + shint->pinned <
 352                             div_factor(shint->key.offset, factor)) {
 353                                 return shint;
 354                         }
 355                 }
 356         }
 357         if (hint && !hint->ro && block_group_bits(hint, data)) {
 358                 used = btrfs_block_group_used(&hint->item);
 359                 if (used + hint->pinned <
 360                     div_factor(hint->key.offset, factor)) {
 361                         return hint;
 362                 }
 363                 last = hint->key.objectid + hint->key.offset;
 364                 hint_last = last;
 365         } else {
 366                 if (hint)
 367                         hint_last = max(hint->key.objectid, search_start);
 368                 else
 369                         hint_last = search_start;
 370
 371                 last = hint_last;
 372         }
 373 again:
 374         while(1) {
 375                 ret = find_first_extent_bit(block_group_cache, last,
 376                                             &start, &end, bit);
 377                 if (ret)
 378                         break;
 379
 380                 ret = get_state_private(block_group_cache, start, &ptr);
 381                 if (ret)
 382                         break;
 383
 384                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 385                 last = cache->key.objectid + cache->key.offset;
 386                 used = btrfs_block_group_used(&cache->item);
 387
 388                 if (!cache->ro && block_group_bits(cache, data)) {
 389                         if (full_search)
 390                                 free_check = cache->key.offset;
 391                         else
 392                                 free_check = div_factor(cache->key.offset,
 393                                                         factor);
 394
 395                         if (used + cache->pinned < free_check) {
 396                                 found_group = cache;
 397                                 goto found;
 398                         }
 399                 }
 400                 cond_resched();
 401         }
 402         if (!full_search) {
 403                 last = search_start;
 404                 full_search = 1;
 405                 goto again;
 406         }
 407 found:
 408         return found_group;
 409 }
 410
 411 /*
 412  * Back reference rules.  Back refs have three main goals:
 413  *
 414  * 1) differentiate between all holders of references to an extent so that
 415  *    when a reference is dropped we can make sure it was a valid reference
 416  *    before freeing the extent.
 417  *
 418  * 2) Provide enough information to quickly find the holders of an extent
 419  *    if we notice a given block is corrupted or bad.
 420  *
 421  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 422  *    maintenance.  This is actually the same as #2, but with a slightly
 423  *    different use case.
 424  *
 425  * There are two kinds of back refs. The implicit back refs is optimized
 426  * for pointers in non-shared tree blocks. For a given pointer in a block,
 427  * back refs of this kind provide information about the block's owner tree
 428  * and the pointer's key. These information allow us to find the block by
 429  * b-tree searching. The full back refs is for pointers in tree blocks not
 430  * referenced by their owner trees. The location of tree block is recorded
 431  * in the back refs. Actually the full back refs is generic, and can be
 432  * used in all cases the implicit back refs is used. The major shortcoming
 433  * of the full back refs is its overhead. Every time a tree block gets
 434  * COWed, we have to update back refs entry for all pointers in it.
 435  *
 436  * For a newly allocated tree block, we use implicit back refs for
 437  * pointers in it. This means most tree related operations only involve
 438  * implicit back refs. For a tree block created in old transaction, the
 439  * only way to drop a reference to it is COW it. So we can detect the
 440  * event that tree block loses its owner tree's reference and do the
 441  * back refs conversion.
 442  *
 443  * When a tree block is COW'd through a tree, there are four cases:
 444  *
 445  * The reference count of the block is one and the tree is the block's
 446  * owner tree. Nothing to do in this case.
 447  *
 448  * The reference count of the block is one and the tree is not the
 449  * block's owner tree. In this case, full back refs is used for pointers
 450  * in the block. Remove these full back refs, add implicit back refs for
 451  * every pointers in the new block.
 452  *
 453  * The reference count of the block is greater than one and the tree is
 454  * the block's owner tree. In this case, implicit back refs is used for
 455  * pointers in the block. Add full back refs for every pointers in the
 456  * block, increase lower level extents' reference counts. The original
 457  * implicit back refs are entailed to the new block.
 458  *
 459  * The reference count of the block is greater than one and the tree is
 460  * not the block's owner tree. Add implicit back refs for every pointer in
 461  * the new block, increase lower level extents' reference count.
 462  *
 463  * Back Reference Key composing:
 464  *
 465  * The key objectid corresponds to the first byte in the extent,
 466  * The key type is used to differentiate between types of back refs.
 467  * There are different meanings of the key offset for different types
 468  * of back refs.
 469  *
 470  * File extents can be referenced by:
 471  *
 472  * - multiple snapshots, subvolumes, or different generations in one subvol
 473  * - different files inside a single subvolume
 474  * - different offsets inside a file (bookend extents in file.c)
 475  *
 476  * The extent ref structure for the implicit back refs has fields for:
 477  *
 478  * - Objectid of the subvolume root
 479  * - objectid of the file holding the reference
 480  * - original offset in the file
 481  * - how many bookend extents
 482  *
 483  * The key offset for the implicit back refs is hash of the first
 484  * three fields.
 485  *
 486  * The extent ref structure for the full back refs has field for:
 487  *
 488  * - number of pointers in the tree leaf
 489  *
 490  * The key offset for the implicit back refs is the first byte of
 491  * the tree leaf
 492  *
 493  * When a file extent is allocated, The implicit back refs is used.
 494  * the fields are filled in:
 495  *
 496  *     (root_key.objectid, inode objectid, offset in file, 1)
 497  *
 498  * When a file extent is removed file truncation, we find the
 499  * corresponding implicit back refs and check the following fields:
 500  *
 501  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 502  *
 503  * Btree extents can be referenced by:
 504  *
 505  * - Different subvolumes
 506  *
 507  * Both the implicit back refs and the full back refs for tree blocks
 508  * only consist of key. The key offset for the implicit back refs is
 509  * objectid of block's owner tree. The key offset for the full back refs
 510  * is the first byte of parent block.
 511  *
 512  * When implicit back refs is used, information about the lowest key and
 513  * level of the tree block are required. These information are stored in
 514  * tree block info structure.
 515  */
 516
 517 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 518 static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 519                                   struct btrfs_root *root,
 520                                   struct btrfs_path *path,
 521                                   u64 owner, u32 extra_size)
 522 {
 523         struct btrfs_extent_item *item;
 524         struct btrfs_extent_item_v0 *ei0;
 525         struct btrfs_extent_ref_v0 *ref0;
 526         struct btrfs_tree_block_info *bi;
 527         struct extent_buffer *leaf;
 528         struct btrfs_key key;
 529         struct btrfs_key found_key;
 530         u32 new_size = sizeof(*item);
 531         u64 refs;
 532         int ret;
 533
 534         leaf = path->nodes[0];
 535         BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
 536
 537         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 538         ei0 = btrfs_item_ptr(leaf, path->slots[0],
 539                              struct btrfs_extent_item_v0);
 540         refs = btrfs_extent_refs_v0(leaf, ei0);
 541
 542         if (owner == (u64)-1) {
 543                 while (1) {
 544                         if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 545                                 ret = btrfs_next_leaf(root, path);
 546                                 if (ret < 0)
 547                                         return ret;
 548                                 BUG_ON(ret > 0);
 549                                 leaf = path->nodes[0];
 550                         }
 551                         btrfs_item_key_to_cpu(leaf, &found_key,
 552                                               path->slots[0]);
 553                         BUG_ON(key.objectid != found_key.objectid);
 554                         if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
 555                                 path->slots[0]++;
 556                                 continue;
 557                         }
 558                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 559                                               struct btrfs_extent_ref_v0);
 560                         owner = btrfs_ref_objectid_v0(leaf, ref0);
 561                         break;
 562                 }
 563         }
 564         btrfs_release_path(path);
 565
 566         if (owner < BTRFS_FIRST_FREE_OBJECTID)
 567                 new_size += sizeof(*bi);
 568
 569         new_size -= sizeof(*ei0);
 570         ret = btrfs_search_slot(trans, root, &key, path, new_size, 1);
 571         if (ret < 0)
 572                 return ret;
 573         BUG_ON(ret);
 574
 575         ret = btrfs_extend_item(root, path, new_size);
 576         BUG_ON(ret);
 577
 578         leaf = path->nodes[0];
 579         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 580         btrfs_set_extent_refs(leaf, item, refs);
 581         /* FIXME: get real generation */
 582         btrfs_set_extent_generation(leaf, item, 0);
 583         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 584                 btrfs_set_extent_flags(leaf, item,
 585                                        BTRFS_EXTENT_FLAG_TREE_BLOCK |
 586                                        BTRFS_BLOCK_FLAG_FULL_BACKREF);
 587                 bi = (struct btrfs_tree_block_info *)(item + 1);
 588                 /* FIXME: get first key of the block */
 589                 memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
 590                 btrfs_set_tree_block_level(leaf, bi, (int)owner);
 591         } else {
 592                 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
 593         }
 594         btrfs_mark_buffer_dirty(leaf);
 595         return 0;
 596 }
 597 #endif
 598
 599 u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 600 {
 601         u32 high_crc = ~(u32)0;
 602         u32 low_crc = ~(u32)0;
 603         __le64 lenum;
 604
 605         lenum = cpu_to_le64(root_objectid);
 606         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 607         lenum = cpu_to_le64(owner);
 608         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 609         lenum = cpu_to_le64(offset);
 610         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 611
 612         return ((u64)high_crc << 31) ^ (u64)low_crc;
 613 }
 614
 615 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
 616                                      struct btrfs_extent_data_ref *ref)
 617 {
 618         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
 619                                     btrfs_extent_data_ref_objectid(leaf, ref),
 620                                     btrfs_extent_data_ref_offset(leaf, ref));
 621 }
 622
 623 static int match_extent_data_ref(struct extent_buffer *leaf,
 624                                  struct btrfs_extent_data_ref *ref,
 625                                  u64 root_objectid, u64 owner, u64 offset)
 626 {
 627         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
 628             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
 629             btrfs_extent_data_ref_offset(leaf, ref) != offset)
 630                 return 0;
 631         return 1;
 632 }
 633
 634 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
 635                                            struct btrfs_root *root,
 636                                            struct btrfs_path *path,
 637                                            u64 bytenr, u64 parent,
 638                                            u64 root_objectid,
 639                                            u64 owner, u64 offset)
 640 {
 641         struct btrfs_key key;
 642         struct btrfs_extent_data_ref *ref;
 643         struct extent_buffer *leaf;
 644         u32 nritems;
 645         int ret;
 646         int recow;
 647         int err = -ENOENT;
 648
 649         key.objectid = bytenr;
 650         if (parent) {
 651                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 652                 key.offset = parent;
 653         } else {
 654                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 655                 key.offset = hash_extent_data_ref(root_objectid,
 656                                                   owner, offset);
 657         }
 658 again:
 659         recow = 0;
 660         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 661         if (ret < 0) {
 662                 err = ret;
 663                 goto fail;
 664         }
 665
 666         if (parent) {
 667                 if (!ret)
 668                         return 0;
 669 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 670                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 671                 btrfs_release_path(path);
 672                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 673                 if (ret < 0) {
 674                         err = ret;
 675                         goto fail;
 676                 }
 677                 if (!ret)
 678                         return 0;
 679 #endif
 680                 goto fail;
 681         }
 682
 683         leaf = path->nodes[0];
 684         nritems = btrfs_header_nritems(leaf);
 685         while (1) {
 686                 if (path->slots[0] >= nritems) {
 687                         ret = btrfs_next_leaf(root, path);
 688                         if (ret < 0)
 689                                 err = ret;
 690                         if (ret)
 691                                 goto fail;
 692
 693                         leaf = path->nodes[0];
 694                         nritems = btrfs_header_nritems(leaf);
 695                         recow = 1;
 696                 }
 697
 698                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 699                 if (key.objectid != bytenr ||
 700                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
 701                         goto fail;
 702
 703                 ref = btrfs_item_ptr(leaf, path->slots[0],
 704                                      struct btrfs_extent_data_ref);
 705
 706                 if (match_extent_data_ref(leaf, ref, root_objectid,
 707                                           owner, offset)) {
 708                         if (recow) {
 709                                 btrfs_release_path(path);
 710                                 goto again;
 711                         }
 712                         err = 0;
 713                         break;
 714                 }
 715                 path->slots[0]++;
 716         }
 717 fail:
 718         return err;
 719 }
 720
 721 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
 722                                            struct btrfs_root *root,
 723                                            struct btrfs_path *path,
 724                                            u64 bytenr, u64 parent,
 725                                            u64 root_objectid, u64 owner,
 726                                            u64 offset, int refs_to_add)
 727 {
 728         struct btrfs_key key;
 729         struct extent_buffer *leaf;
 730         u32 size;
 731         u32 num_refs;
 732         int ret;
 733
 734         key.objectid = bytenr;
 735         if (parent) {
 736                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 737                 key.offset = parent;
 738                 size = sizeof(struct btrfs_shared_data_ref);
 739         } else {
 740                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 741                 key.offset = hash_extent_data_ref(root_objectid,
 742                                                   owner, offset);
 743                 size = sizeof(struct btrfs_extent_data_ref);
 744         }
 745
 746         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 747         if (ret && ret != -EEXIST)
 748                 goto fail;
 749
 750         leaf = path->nodes[0];
 751         if (parent) {
 752                 struct btrfs_shared_data_ref *ref;
 753                 ref = btrfs_item_ptr(leaf, path->slots[0],
 754                                      struct btrfs_shared_data_ref);
 755                 if (ret == 0) {
 756                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
 757                 } else {
 758                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
 759                         num_refs += refs_to_add;
 760                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
 761                 }
 762         } else {
 763                 struct btrfs_extent_data_ref *ref;
 764                 while (ret == -EEXIST) {
 765                         ref = btrfs_item_ptr(leaf, path->slots[0],
 766                                              struct btrfs_extent_data_ref);
 767                         if (match_extent_data_ref(leaf, ref, root_objectid,
 768                                                   owner, offset))
 769                                 break;
 770                         btrfs_release_path(path);
 771
 772                         key.offset++;
 773                         ret = btrfs_insert_empty_item(trans, root, path, &key,
 774                                                       size);
 775                         if (ret && ret != -EEXIST)
 776                                 goto fail;
 777
 778                         leaf = path->nodes[0];
 779                 }
 780                 ref = btrfs_item_ptr(leaf, path->slots[0],
 781                                      struct btrfs_extent_data_ref);
 782                 if (ret == 0) {
 783                         btrfs_set_extent_data_ref_root(leaf, ref,
 784                                                        root_objectid);
 785                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
 786                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
 787                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
 788                 } else {
 789                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
 790                         num_refs += refs_to_add;
 791                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
 792                 }
 793         }
 794         btrfs_mark_buffer_dirty(leaf);
 795         ret = 0;
 796 fail:
 797         btrfs_release_path(path);
 798         return ret;
 799 }
 800
 801 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
 802                                            struct btrfs_root *root,
 803                                            struct btrfs_path *path,
 804                                            int refs_to_drop)
 805 {
 806         struct btrfs_key key;
 807         struct btrfs_extent_data_ref *ref1 = NULL;
 808         struct btrfs_shared_data_ref *ref2 = NULL;
 809         struct extent_buffer *leaf;
 810         u32 num_refs = 0;
 811         int ret = 0;
 812
 813         leaf = path->nodes[0];
 814         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 815
 816         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 817                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 818                                       struct btrfs_extent_data_ref);
 819                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 820         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 821                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 822                                       struct btrfs_shared_data_ref);
 823                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 824 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 825         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 826                 struct btrfs_extent_ref_v0 *ref0;
 827                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 828                                       struct btrfs_extent_ref_v0);
 829                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 830 #endif
 831         } else {
 832                 BUG();
 833         }
 834
 835         BUG_ON(num_refs < refs_to_drop);
 836         num_refs -= refs_to_drop;
 837
 838         if (num_refs == 0) {
 839                 ret = btrfs_del_item(trans, root, path);
 840         } else {
 841                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
 842                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
 843                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
 844                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 845 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 846                 else {
 847                         struct btrfs_extent_ref_v0 *ref0;
 848                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 849                                         struct btrfs_extent_ref_v0);
 850                         btrfs_set_ref_count_v0(leaf, ref0, num_refs);
 851                 }
 852 #endif
 853                 btrfs_mark_buffer_dirty(leaf);
 854         }
 855         return ret;
 856 }
 857
 858 static noinline u32 extent_data_ref_count(struct btrfs_path *path,
 859                                           struct btrfs_extent_inline_ref *iref)
 860 {
 861         struct btrfs_key key;
 862         struct extent_buffer *leaf;
 863         struct btrfs_extent_data_ref *ref1;
 864         struct btrfs_shared_data_ref *ref2;
 865         u32 num_refs = 0;
 866
 867         leaf = path->nodes[0];
 868         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 869         if (iref) {
 870                 if (btrfs_extent_inline_ref_type(leaf, iref) ==
 871                     BTRFS_EXTENT_DATA_REF_KEY) {
 872                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
 873                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 874                 } else {
 875                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
 876                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 877                 }
 878         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 879                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 880                                       struct btrfs_extent_data_ref);
 881                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 882         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 883                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 884                                       struct btrfs_shared_data_ref);
 885                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 886 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 887         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 888                 struct btrfs_extent_ref_v0 *ref0;
 889                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 890                                       struct btrfs_extent_ref_v0);
 891                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 892 #endif
 893         } else {
 894                 BUG();
 895         }
 896         return num_refs;
 897 }
 898
 899 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
 900                                           struct btrfs_root *root,
 901                                           struct btrfs_path *path,
 902                                           u64 bytenr, u64 parent,
 903                                           u64 root_objectid)
 904 {
 905         struct btrfs_key key;
 906         int ret;
 907
 908         key.objectid = bytenr;
 909         if (parent) {
 910                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 911                 key.offset = parent;
 912         } else {
 913                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 914                 key.offset = root_objectid;
 915         }
 916
 917         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 918         if (ret > 0)
 919                 ret = -ENOENT;
 920 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 921         if (ret == -ENOENT && parent) {
 922                 btrfs_release_path(path);
 923                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 924                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 925                 if (ret > 0)
 926                         ret = -ENOENT;
 927         }
 928 #endif
 929         return ret;
 930 }
 931
 932 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
 933                                           struct btrfs_root *root,
 934                                           struct btrfs_path *path,
 935                                           u64 bytenr, u64 parent,
 936                                           u64 root_objectid)
 937 {
 938         struct btrfs_key key;
 939         int ret;
 940
 941         key.objectid = bytenr;
 942         if (parent) {
 943                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 944                 key.offset = parent;
 945         } else {
 946                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 947                 key.offset = root_objectid;
 948         }
 949
 950         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 951
 952         btrfs_release_path(path);
 953         return ret;
 954 }
 955
 956 static inline int extent_ref_type(u64 parent, u64 owner)
 957 {
 958         int type;
 959         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 960                 if (parent > 0)
 961                         type = BTRFS_SHARED_BLOCK_REF_KEY;
 962                 else
 963                         type = BTRFS_TREE_BLOCK_REF_KEY;
 964         } else {
 965                 if (parent > 0)
 966                         type = BTRFS_SHARED_DATA_REF_KEY;
 967                 else
 968                         type = BTRFS_EXTENT_DATA_REF_KEY;
 969         }
 970         return type;
 971 }
 972
 973 static int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
 974                                  struct btrfs_root *root,
 975                                  struct btrfs_path *path,
 976                                  struct btrfs_extent_inline_ref **ref_ret,
 977                                  u64 bytenr, u64 num_bytes,
 978                                  u64 parent, u64 root_objectid,
 979                                  u64 owner, u64 offset, int insert)
 980 {
 981         struct btrfs_key key;
 982         struct extent_buffer *leaf;
 983         struct btrfs_extent_item *ei;
 984         struct btrfs_extent_inline_ref *iref;
 985         u64 flags;
 986         u32 item_size;
 987         unsigned long ptr;
 988         unsigned long end;
 989         int extra_size;
 990         int type;
 991         int want;
 992         int ret;
 993         int err = 0;
 994         int skinny_metadata =
 995                 btrfs_fs_incompat(root->fs_info, SKINNY_METADATA);
 996
 997         key.objectid = bytenr;
 998         key.type = BTRFS_EXTENT_ITEM_KEY;
 999         key.offset = num_bytes;
1000
1001         want = extent_ref_type(parent, owner);
1002         if (insert)
1003                 extra_size = btrfs_extent_inline_ref_size(want);
1004         else
1005                 extra_size = -1;
1006
1007         if (owner < BTRFS_FIRST_FREE_OBJECTID && skinny_metadata) {
1008                 skinny_metadata = 1;
1009                 key.type = BTRFS_METADATA_ITEM_KEY;
1010                 key.offset = owner;
1011         } else if (skinny_metadata) {
1012                 skinny_metadata = 0;
1013         }
1014
1015 again:
1016         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1017         if (ret < 0) {
1018                 err = ret;
1019                 goto out;
1020         }
1021
1022         /*
1023          * We may be a newly converted file system which still has the old fat
1024          * extent entries for metadata, so try and see if we have one of those.
1025          */
1026         if (ret > 0 && skinny_metadata) {
1027                 skinny_metadata = 0;
1028                 if (path->slots[0]) {
1029                         path->slots[0]--;
1030                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1031                                               path->slots[0]);
1032                         if (key.objectid == bytenr &&
1033                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1034                             key.offset == num_bytes)
1035                                 ret = 0;
1036                 }
1037                 if (ret) {
1038                         key.type = BTRFS_EXTENT_ITEM_KEY;
1039                         key.offset = num_bytes;
1040                         btrfs_release_path(path);
1041                         goto again;
1042                 }
1043         }
1044
1045         if (ret) {
1046                 printf("Failed to find [%llu, %u, %llu]\n", key.objectid, key.type, key.offset);
1047                 return -ENOENT;
1048         }
1049
1050         BUG_ON(ret);
1051
1052         leaf = path->nodes[0];
1053         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1054 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1055         if (item_size < sizeof(*ei)) {
1056                 if (!insert) {
1057                         err = -ENOENT;
1058                         goto out;
1059                 }
1060                 ret = convert_extent_item_v0(trans, root, path, owner,
1061                                              extra_size);
1062                 if (ret < 0) {
1063                         err = ret;
1064                         goto out;
1065                 }
1066                 leaf = path->nodes[0];
1067                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1068         }
1069 #endif
1070         if (item_size < sizeof(*ei)) {
1071                 printf("Size is %u, needs to be %u, slot %d\n",
1072                        (unsigned)item_size,
1073                        (unsigned)sizeof(*ei), path->slots[0]);
1074                 btrfs_print_leaf(root, leaf);
1075                 return -EINVAL;
1076         }
1077         BUG_ON(item_size < sizeof(*ei));
1078
1079         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1080         flags = btrfs_extent_flags(leaf, ei);
1081
1082         ptr = (unsigned long)(ei + 1);
1083         end = (unsigned long)ei + item_size;
1084
1085         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
1086                 ptr += sizeof(struct btrfs_tree_block_info);
1087                 BUG_ON(ptr > end);
1088         } else if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
1089                 if (!(flags & BTRFS_EXTENT_FLAG_DATA)) {
1090                         return -EIO;
1091                 }
1092         }
1093
1094         err = -ENOENT;
1095         while (1) {
1096                 if (ptr >= end) {
1097                         WARN_ON(ptr > end);
1098                         break;
1099                 }
1100                 iref = (struct btrfs_extent_inline_ref *)ptr;
1101                 type = btrfs_extent_inline_ref_type(leaf, iref);
1102                 if (want < type)
1103                         break;
1104                 if (want > type) {
1105                         ptr += btrfs_extent_inline_ref_size(type);
1106                         continue;
1107                 }
1108
1109                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1110                         struct btrfs_extent_data_ref *dref;
1111                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1112                         if (match_extent_data_ref(leaf, dref, root_objectid,
1113                                                   owner, offset)) {
1114                                 err = 0;
1115                                 break;
1116                         }
1117                         if (hash_extent_data_ref_item(leaf, dref) <
1118                             hash_extent_data_ref(root_objectid, owner, offset))
1119                                 break;
1120                 } else {
1121                         u64 ref_offset;
1122                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1123                         if (parent > 0) {
1124                                 if (parent == ref_offset) {
1125                                         err = 0;
1126                                         break;
1127                                 }
1128                                 if (ref_offset < parent)
1129                                         break;
1130                         } else {
1131                                 if (root_objectid == ref_offset) {
1132                                         err = 0;
1133                                         break;
1134                                 }
1135                                 if (ref_offset < root_objectid)
1136                                         break;
1137                         }
1138                 }
1139                 ptr += btrfs_extent_inline_ref_size(type);
1140         }
1141         if (err == -ENOENT && insert) {
1142                 if (item_size + extra_size >=
1143                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1144                         err = -EAGAIN;
1145                         goto out;
1146                 }
1147                 /*
1148                  * To add new inline back ref, we have to make sure
1149                  * there is no corresponding back ref item.
1150                  * For simplicity, we just do not add new inline back
1151                  * ref if there is any back ref item.
1152                  */
1153                 if (find_next_key(path, &key) == 0 && key.objectid == bytenr &&
1154                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1155                         err = -EAGAIN;
1156                         goto out;
1157                 }
1158         }
1159         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1160 out:
1161         return err;
1162 }
1163
1164 static int setup_inline_extent_backref(struct btrfs_root *root,
1165                                 struct btrfs_path *path,
1166                                 struct btrfs_extent_inline_ref *iref,
1167                                 u64 parent, u64 root_objectid,
1168                                 u64 owner, u64 offset, int refs_to_add)
1169 {
1170         struct extent_buffer *leaf;
1171         struct btrfs_extent_item *ei;
1172         unsigned long ptr;
1173         unsigned long end;
1174         unsigned long item_offset;
1175         u64 refs;
1176         int size;
1177         int type;
1178         int ret;
1179
1180         leaf = path->nodes[0];
1181         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1182         item_offset = (unsigned long)iref - (unsigned long)ei;
1183
1184         type = extent_ref_type(parent, owner);
1185         size = btrfs_extent_inline_ref_size(type);
1186
1187         ret = btrfs_extend_item(root, path, size);
1188         BUG_ON(ret);
1189
1190         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1191         refs = btrfs_extent_refs(leaf, ei);
1192         refs += refs_to_add;
1193         btrfs_set_extent_refs(leaf, ei, refs);
1194
1195         ptr = (unsigned long)ei + item_offset;
1196         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1197         if (ptr < end - size)
1198                 memmove_extent_buffer(leaf, ptr + size, ptr,
1199                                       end - size - ptr);
1200
1201         iref = (struct btrfs_extent_inline_ref *)ptr;
1202         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1203         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1204                 struct btrfs_extent_data_ref *dref;
1205                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1206                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1207                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1208                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1209                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1210         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1211                 struct btrfs_shared_data_ref *sref;
1212                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1213                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1214                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1215         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1216                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1217         } else {
1218                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1219         }
1220         btrfs_mark_buffer_dirty(leaf);
1221         return 0;
1222 }
1223
1224 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1225                                  struct btrfs_root *root,
1226                                  struct btrfs_path *path,
1227                                  struct btrfs_extent_inline_ref **ref_ret,
1228                                  u64 bytenr, u64 num_bytes, u64 parent,
1229                                  u64 root_objectid, u64 owner, u64 offset)
1230 {
1231         int ret;
1232
1233         ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1234                                            bytenr, num_bytes, parent,
1235                                            root_objectid, owner, offset, 0);
1236         if (ret != -ENOENT)
1237                 return ret;
1238
1239         btrfs_release_path(path);
1240         *ref_ret = NULL;
1241
1242         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1243                 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1244                                             root_objectid);
1245         } else {
1246                 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1247                                              root_objectid, owner, offset);
1248         }
1249         return ret;
1250 }
1251
1252 static int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1253                                  struct btrfs_root *root,
1254                                  struct btrfs_path *path,
1255                                  struct btrfs_extent_inline_ref *iref,
1256                                  int refs_to_mod)
1257 {
1258         struct extent_buffer *leaf;
1259         struct btrfs_extent_item *ei;
1260         struct btrfs_extent_data_ref *dref = NULL;
1261         struct btrfs_shared_data_ref *sref = NULL;
1262         unsigned long ptr;
1263         unsigned long end;
1264         u32 item_size;
1265         int size;
1266         int type;
1267         int ret;
1268         u64 refs;
1269
1270         leaf = path->nodes[0];
1271         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1272         refs = btrfs_extent_refs(leaf, ei);
1273         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1274         refs += refs_to_mod;
1275         btrfs_set_extent_refs(leaf, ei, refs);
1276
1277         type = btrfs_extent_inline_ref_type(leaf, iref);
1278
1279         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1280                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1281                 refs = btrfs_extent_data_ref_count(leaf, dref);
1282         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1283                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1284                 refs = btrfs_shared_data_ref_count(leaf, sref);
1285         } else {
1286                 refs = 1;
1287                 BUG_ON(refs_to_mod != -1);
1288         }
1289
1290         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1291         refs += refs_to_mod;
1292
1293         if (refs > 0) {
1294                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1295                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1296                 else
1297                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1298         } else {
1299                 size =  btrfs_extent_inline_ref_size(type);
1300                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1301                 ptr = (unsigned long)iref;
1302                 end = (unsigned long)ei + item_size;
1303                 if (ptr + size < end)
1304                         memmove_extent_buffer(leaf, ptr, ptr + size,
1305                                               end - ptr - size);
1306                 item_size -= size;
1307                 ret = btrfs_truncate_item(root, path, item_size, 1);
1308                 BUG_ON(ret);
1309         }
1310         btrfs_mark_buffer_dirty(leaf);
1311         return 0;
1312 }
1313
1314 static int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1315                                  struct btrfs_root *root,
1316                                  struct btrfs_path *path,
1317                                  u64 bytenr, u64 num_bytes, u64 parent,
1318                                  u64 root_objectid, u64 owner,
1319                                  u64 offset, int refs_to_add)
1320 {
1321         struct btrfs_extent_inline_ref *iref;
1322         int ret;
1323
1324         ret = lookup_inline_extent_backref(trans, root, path, &iref,
1325                                            bytenr, num_bytes, parent,
1326                                            root_objectid, owner, offset, 1);
1327         if (ret == 0) {
1328                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1329                 ret = update_inline_extent_backref(trans, root, path, iref,
1330                                                    refs_to_add);
1331         } else if (ret == -ENOENT) {
1332                 ret = setup_inline_extent_backref(root, path, iref,
1333                                                   parent, root_objectid,
1334                                                   owner, offset, refs_to_add);
1335         }
1336         return ret;
1337 }
1338
1339 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1340                                  struct btrfs_root *root,
1341                                  struct btrfs_path *path,
1342                                  u64 bytenr, u64 parent, u64 root_objectid,
1343                                  u64 owner, u64 offset, int refs_to_add)
1344 {
1345         int ret;
1346
1347         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
1348                 ret = insert_extent_data_ref(trans, root, path, bytenr,
1349                                              parent, root_objectid,
1350                                              owner, offset, refs_to_add);
1351         } else {
1352                 BUG_ON(refs_to_add != 1);
1353                 ret = insert_tree_block_ref(trans, root, path, bytenr,
1354                                             parent, root_objectid);
1355         }
1356         return ret;
1357 }
1358
1359 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1360                                  struct btrfs_root *root,
1361                                  struct btrfs_path *path,
1362                                  struct btrfs_extent_inline_ref *iref,
1363                                  int refs_to_drop, int is_data)
1364 {
1365         int ret;
1366
1367         BUG_ON(!is_data && refs_to_drop != 1);
1368         if (iref) {
1369                 ret = update_inline_extent_backref(trans, root, path, iref,
1370                                                    -refs_to_drop);
1371         } else if (is_data) {
1372                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1373         } else {
1374                 ret = btrfs_del_item(trans, root, path);
1375         }
1376         return ret;
1377 }
1378
1379 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1380                          struct btrfs_root *root,
1381                          u64 bytenr, u64 num_bytes, u64 parent,
1382                          u64 root_objectid, u64 owner, u64 offset)
1383 {
1384         struct btrfs_path *path;
1385         struct extent_buffer *leaf;
1386         struct btrfs_extent_item *item;
1387         u64 refs;
1388         int ret;
1389         int err = 0;
1390
1391         path = btrfs_alloc_path();
1392         if (!path)
1393                 return -ENOMEM;
1394
1395         path->reada = 1;
1396
1397         ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1398                                            path, bytenr, num_bytes, parent,
1399                                            root_objectid, owner, offset, 1);
1400         if (ret == 0)
1401                 goto out;
1402
1403         if (ret != -EAGAIN) {
1404                 err = ret;
1405                 goto out;
1406         }
1407
1408         leaf = path->nodes[0];
1409         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1410         refs = btrfs_extent_refs(leaf, item);
1411         btrfs_set_extent_refs(leaf, item, refs + 1);
1412
1413         btrfs_mark_buffer_dirty(leaf);
1414         btrfs_release_path(path);
1415
1416         path->reada = 1;
1417
1418         /* now insert the actual backref */
1419         ret = insert_extent_backref(trans, root->fs_info->extent_root,
1420                                     path, bytenr, parent, root_objectid,
1421                                     owner, offset, 1);
1422         if (ret)
1423                 err = ret;
1424 out:
1425         btrfs_free_path(path);
1426         finish_current_insert(trans, root->fs_info->extent_root);
1427         del_pending_extents(trans, root->fs_info->extent_root);
1428         BUG_ON(err);
1429         return err;
1430 }
1431
1432 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
1433                          struct btrfs_root *root)
1434 {
1435         finish_current_insert(trans, root->fs_info->extent_root);
1436         del_pending_extents(trans, root->fs_info->extent_root);
1437         return 0;
1438 }
1439
1440 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
1441                              struct btrfs_root *root, u64 bytenr,
1442                              u64 offset, int metadata, u64 *refs, u64 *flags)
1443 {
1444         struct btrfs_path *path;
1445         int ret;
1446         struct btrfs_key key;
1447         struct extent_buffer *l;
1448         struct btrfs_extent_item *item;
1449         u32 item_size;
1450         u64 num_refs;
1451         u64 extent_flags;
1452
1453         if (metadata &&
1454             !btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) {
1455                 offset = root->fs_info->nodesize;
1456                 metadata = 0;
1457         }
1458
1459         path = btrfs_alloc_path();
1460         if (!path)
1461                 return -ENOMEM;
1462         path->reada = 1;
1463
1464         key.objectid = bytenr;
1465         key.offset = offset;
1466         if (metadata)
1467                 key.type = BTRFS_METADATA_ITEM_KEY;
1468         else
1469                 key.type = BTRFS_EXTENT_ITEM_KEY;
1470
1471 again:
1472         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1473                                 0, 0);
1474         if (ret < 0)
1475                 goto out;
1476
1477         /*
1478          * Deal with the fact that we may have mixed SKINNY and normal refs.  If
1479          * we didn't find what we wanted check and see if we have a normal ref
1480          * right next to us, or re-search if we are on the edge of the leaf just
1481          * to make sure.
1482          */
1483         if (ret > 0 && metadata) {
1484                 if (path->slots[0]) {
1485                         path->slots[0]--;
1486                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1487                                               path->slots[0]);
1488                         if (key.objectid == bytenr &&
1489                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1490                             key.offset == root->fs_info->nodesize)
1491                                 ret = 0;
1492                 }
1493
1494                 if (ret) {
1495                         btrfs_release_path(path);
1496                         key.type = BTRFS_EXTENT_ITEM_KEY;
1497                         key.offset = root->fs_info->nodesize;
1498                         metadata = 0;
1499                         goto again;
1500                 }
1501         }
1502
1503         if (ret != 0) {
1504                 ret = -EIO;
1505                 goto out;
1506         }
1507
1508         l = path->nodes[0];
1509         item_size = btrfs_item_size_nr(l, path->slots[0]);
1510         if (item_size >= sizeof(*item)) {
1511                 item = btrfs_item_ptr(l, path->slots[0],
1512                                       struct btrfs_extent_item);
1513                 num_refs = btrfs_extent_refs(l, item);
1514                 extent_flags = btrfs_extent_flags(l, item);
1515         } else {
1516 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1517                         struct btrfs_extent_item_v0 *ei0;
1518                         BUG_ON(item_size != sizeof(*ei0));
1519                         ei0 = btrfs_item_ptr(l, path->slots[0],
1520                                              struct btrfs_extent_item_v0);
1521                         num_refs = btrfs_extent_refs_v0(l, ei0);
1522                         /* FIXME: this isn't correct for data */
1523                         extent_flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
1524 #else
1525                         BUG();
1526 #endif
1527         }
1528         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1529         if (refs)
1530                 *refs = num_refs;
1531         if (flags)
1532                 *flags = extent_flags;
1533 out:
1534         btrfs_free_path(path);
1535         return ret;
1536 }
1537
1538 int btrfs_set_block_flags(struct btrfs_trans_handle *trans,
1539                           struct btrfs_root *root,
1540                           u64 bytenr, int level, u64 flags)
1541 {
1542         struct btrfs_path *path;
1543         int ret;
1544         struct btrfs_key key;
1545         struct extent_buffer *l;
1546         struct btrfs_extent_item *item;
1547         u32 item_size;
1548         int skinny_metadata =
1549                 btrfs_fs_incompat(root->fs_info, SKINNY_METADATA);
1550
1551         path = btrfs_alloc_path();
1552         if (!path)
1553                 return -ENOMEM;
1554         path->reada = 1;
1555
1556         key.objectid = bytenr;
1557         if (skinny_metadata) {
1558                 key.offset = level;
1559                 key.type = BTRFS_METADATA_ITEM_KEY;
1560         } else {
1561                 key.offset = root->fs_info->nodesize;
1562                 key.type = BTRFS_EXTENT_ITEM_KEY;
1563         }
1564
1565 again:
1566         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1567                                 0, 0);
1568         if (ret < 0)
1569                 goto out;
1570
1571         if (ret > 0 && skinny_metadata) {
1572                 skinny_metadata = 0;
1573                 if (path->slots[0]) {
1574                         path->slots[0]--;
1575                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1576                                               path->slots[0]);
1577                         if (key.objectid == bytenr &&
1578                             key.offset == root->fs_info->nodesize &&
1579                             key.type == BTRFS_EXTENT_ITEM_KEY)
1580                                 ret = 0;
1581                 }
1582                 if (ret) {
1583                         btrfs_release_path(path);
1584                         key.offset = root->fs_info->nodesize;
1585                         key.type = BTRFS_EXTENT_ITEM_KEY;
1586                         goto again;
1587                 }
1588         }
1589
1590         if (ret != 0) {
1591                 btrfs_print_leaf(root, path->nodes[0]);
1592                 printk("failed to find block number %Lu\n",
1593                         (unsigned long long)bytenr);
1594                 BUG();
1595         }
1596         l = path->nodes[0];
1597         item_size = btrfs_item_size_nr(l, path->slots[0]);
1598 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1599         if (item_size < sizeof(*item)) {
1600                 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1601                                              path, (u64)-1, 0);
1602                 if (ret < 0)
1603                         goto out;
1604
1605                 l = path->nodes[0];
1606                 item_size = btrfs_item_size_nr(l, path->slots[0]);
1607         }
1608 #endif
1609         BUG_ON(item_size < sizeof(*item));
1610         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1611         flags |= btrfs_extent_flags(l, item);
1612         btrfs_set_extent_flags(l, item, flags);
1613 out:
1614         btrfs_free_path(path);
1615         finish_current_insert(trans, root->fs_info->extent_root);
1616         del_pending_extents(trans, root->fs_info->extent_root);
1617         return ret;
1618 }
1619
1620 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
1621                            struct btrfs_root *root,
1622                            struct extent_buffer *buf,
1623                            int record_parent, int inc)
1624 {
1625         u64 bytenr;
1626         u64 num_bytes;
1627         u64 parent;
1628         u64 ref_root;
1629         u32 nritems;
1630         struct btrfs_key key;
1631         struct btrfs_file_extent_item *fi;
1632         int i;
1633         int level;
1634         int ret = 0;
1635         int (*process_func)(struct btrfs_trans_handle *trans,
1636                             struct btrfs_root *root,
1637                             u64, u64, u64, u64, u64, u64);
1638
1639         ref_root = btrfs_header_owner(buf);
1640         nritems = btrfs_header_nritems(buf);
1641         level = btrfs_header_level(buf);
1642
1643         if (!root->ref_cows && level == 0)
1644                 return 0;
1645
1646         if (inc)
1647                 process_func = btrfs_inc_extent_ref;
1648         else
1649                 process_func = btrfs_free_extent;
1650
1651         if (record_parent)
1652                 parent = buf->start;
1653         else
1654                 parent = 0;
1655
1656         for (i = 0; i < nritems; i++) {
1657                 cond_resched();
1658                 if (level == 0) {
1659                         btrfs_item_key_to_cpu(buf, &key, i);
1660                         if (key.type != BTRFS_EXTENT_DATA_KEY)
1661                                 continue;
1662                         fi = btrfs_item_ptr(buf, i,
1663                                             struct btrfs_file_extent_item);
1664                         if (btrfs_file_extent_type(buf, fi) ==
1665                             BTRFS_FILE_EXTENT_INLINE)
1666                                 continue;
1667                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1668                         if (bytenr == 0)
1669                                 continue;
1670
1671                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
1672                         key.offset -= btrfs_file_extent_offset(buf, fi);
1673                         ret = process_func(trans, root, bytenr, num_bytes,
1674                                            parent, ref_root, key.objectid,
1675                                            key.offset);
1676                         if (ret) {
1677                                 WARN_ON(1);
1678                                 goto fail;
1679                         }
1680                 } else {
1681                         bytenr = btrfs_node_blockptr(buf, i);
1682                         num_bytes = root->fs_info->nodesize;
1683                         ret = process_func(trans, root, bytenr, num_bytes,
1684                                            parent, ref_root, level - 1, 0);
1685                         if (ret) {
1686                                 WARN_ON(1);
1687                                 goto fail;
1688                         }
1689                 }
1690         }
1691         return 0;
1692 fail:
1693         WARN_ON(1);
1694         return ret;
1695 }
1696
1697 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1698                   struct extent_buffer *buf, int record_parent)
1699 {
1700         return __btrfs_mod_ref(trans, root, buf, record_parent, 1);
1701 }
1702
1703 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1704                   struct extent_buffer *buf, int record_parent)
1705 {
1706         return __btrfs_mod_ref(trans, root, buf, record_parent, 0);
1707 }
1708
1709 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1710                                  struct btrfs_root *root,
1711                                  struct btrfs_path *path,
1712                                  struct btrfs_block_group_cache *cache)
1713 {
1714         int ret;
1715         int pending_ret;
1716         struct btrfs_root *extent_root = root->fs_info->extent_root;
1717         unsigned long bi;
1718         struct extent_buffer *leaf;
1719
1720         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1721         if (ret < 0)
1722                 goto fail;
1723         BUG_ON(ret);
1724
1725         leaf = path->nodes[0];
1726         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1727         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1728         btrfs_mark_buffer_dirty(leaf);
1729         btrfs_release_path(path);
1730 fail:
1731         finish_current_insert(trans, extent_root);
1732         pending_ret = del_pending_extents(trans, extent_root);
1733         if (ret)
1734                 return ret;
1735         if (pending_ret)
1736                 return pending_ret;
1737         return 0;
1738
1739 }
1740
1741 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1742                                    struct btrfs_root *root)
1743 {
1744         struct extent_io_tree *block_group_cache;
1745         struct btrfs_block_group_cache *cache;
1746         int ret;
1747         struct btrfs_path *path;
1748         u64 last = 0;
1749         u64 start;
1750         u64 end;
1751         u64 ptr;
1752
1753         block_group_cache = &root->fs_info->block_group_cache;
1754         path = btrfs_alloc_path();
1755         if (!path)
1756                 return -ENOMEM;
1757
1758         while(1) {
1759                 ret = find_first_extent_bit(block_group_cache, last,
1760                                             &start, &end, BLOCK_GROUP_DIRTY);
1761                 if (ret) {
1762                         if (last == 0)
1763                                 break;
1764                         last = 0;
1765                         continue;
1766                 }
1767
1768                 last = end + 1;
1769                 ret = get_state_private(block_group_cache, start, &ptr);
1770                 BUG_ON(ret);
1771
1772                 clear_extent_bits(block_group_cache, start, end,
1773                                   BLOCK_GROUP_DIRTY);
1774
1775                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1776                 ret = write_one_cache_group(trans, root, path, cache);
1777         }
1778         btrfs_free_path(path);
1779         return 0;
1780 }
1781
1782 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1783                                                   u64 flags)
1784 {
1785         struct btrfs_space_info *found;
1786
1787         flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
1788
1789         list_for_each_entry(found, &info->space_info, list) {
1790                 if (found->flags & flags)
1791                         return found;
1792         }
1793         return NULL;
1794
1795 }
1796
1797 static int free_space_info(struct btrfs_fs_info *fs_info, u64 flags,
1798                           u64 total_bytes, u64 bytes_used,
1799                           struct btrfs_space_info **space_info)
1800 {
1801         struct btrfs_space_info *found;
1802
1803         /* only support free block group which is empty */
1804         if (bytes_used)
1805                 return -ENOTEMPTY;
1806
1807         found = __find_space_info(fs_info, flags);
1808         if (!found)
1809                 return -ENOENT;
1810         if (found->total_bytes < total_bytes) {
1811                 fprintf(stderr,
1812                         "WARNING: bad space info to free %llu only have %llu\n",
1813                         total_bytes, found->total_bytes);
1814                 return -EINVAL;
1815         }
1816         found->total_bytes -= total_bytes;
1817         if (space_info)
1818                 *space_info = found;
1819         return 0;
1820 }
1821
1822 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1823                              u64 total_bytes, u64 bytes_used,
1824                              struct btrfs_space_info **space_info)
1825 {
1826         struct btrfs_space_info *found;
1827
1828         found = __find_space_info(info, flags);
1829         if (found) {
1830                 found->total_bytes += total_bytes;
1831                 found->bytes_used += bytes_used;
1832                 if (found->total_bytes < found->bytes_used) {
1833                         fprintf(stderr, "warning, bad space info total_bytes "
1834                                 "%llu used %llu\n",
1835                                (unsigned long long)found->total_bytes,
1836                                (unsigned long long)found->bytes_used);
1837                 }
1838                 *space_info = found;
1839                 return 0;
1840         }
1841         found = kmalloc(sizeof(*found), GFP_NOFS);
1842         if (!found)
1843                 return -ENOMEM;
1844
1845         list_add(&found->list, &info->space_info);
1846         found->flags = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
1847         found->total_bytes = total_bytes;
1848         found->bytes_used = bytes_used;
1849         found->bytes_pinned = 0;
1850         found->full = 0;
1851         *space_info = found;
1852         return 0;
1853 }
1854
1855
1856 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1857 {
1858         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1859                                    BTRFS_BLOCK_GROUP_RAID1 |
1860                                    BTRFS_BLOCK_GROUP_RAID10 |
1861                                    BTRFS_BLOCK_GROUP_RAID5 |
1862                                    BTRFS_BLOCK_GROUP_RAID6 |
1863                                    BTRFS_BLOCK_GROUP_DUP);
1864         if (extra_flags) {
1865                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1866                         fs_info->avail_data_alloc_bits |= extra_flags;
1867                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1868                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1869                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1870                         fs_info->avail_system_alloc_bits |= extra_flags;
1871         }
1872 }
1873
1874 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1875                           struct btrfs_root *extent_root, u64 alloc_bytes,
1876                           u64 flags)
1877 {
1878         struct btrfs_space_info *space_info;
1879         u64 thresh;
1880         u64 start;
1881         u64 num_bytes;
1882         int ret;
1883
1884         space_info = __find_space_info(extent_root->fs_info, flags);
1885         if (!space_info) {
1886                 ret = update_space_info(extent_root->fs_info, flags,
1887                                         0, 0, &space_info);
1888                 BUG_ON(ret);
1889         }
1890         BUG_ON(!space_info);
1891
1892         if (space_info->full)
1893                 return 0;
1894
1895         thresh = div_factor(space_info->total_bytes, 7);
1896         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1897             thresh)
1898                 return 0;
1899
1900         /*
1901          * Avoid allocating given chunk type
1902          */
1903         if (extent_root->fs_info->avoid_meta_chunk_alloc &&
1904             (flags & BTRFS_BLOCK_GROUP_METADATA))
1905                 return 0;
1906         if (extent_root->fs_info->avoid_sys_chunk_alloc &&
1907             (flags & BTRFS_BLOCK_GROUP_SYSTEM))
1908                 return 0;
1909
1910         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes,
1911                                 space_info->flags);
1912         if (ret == -ENOSPC) {
1913                 space_info->full = 1;
1914                 return 0;
1915         }
1916
1917         BUG_ON(ret);
1918
1919         ret = btrfs_make_block_group(trans, extent_root, 0, space_info->flags,
1920                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1921         BUG_ON(ret);
1922         return 0;
1923 }
1924
1925 static int update_block_group(struct btrfs_trans_handle *trans,
1926                               struct btrfs_root *root,
1927                               u64 bytenr, u64 num_bytes, int alloc,
1928                               int mark_free)
1929 {
1930         struct btrfs_block_group_cache *cache;
1931         struct btrfs_fs_info *info = root->fs_info;
1932         u64 total = num_bytes;
1933         u64 old_val;
1934         u64 byte_in_group;
1935         u64 start;
1936         u64 end;
1937
1938         /* block accounting for super block */
1939         old_val = btrfs_super_bytes_used(info->super_copy);
1940         if (alloc)
1941                 old_val += num_bytes;
1942         else
1943                 old_val -= num_bytes;
1944         btrfs_set_super_bytes_used(info->super_copy, old_val);
1945
1946         /* block accounting for root item */
1947         old_val = btrfs_root_used(&root->root_item);
1948         if (alloc)
1949                 old_val += num_bytes;
1950         else
1951                 old_val -= num_bytes;
1952         btrfs_set_root_used(&root->root_item, old_val);
1953
1954         while(total) {
1955                 cache = btrfs_lookup_block_group(info, bytenr);
1956                 if (!cache) {
1957                         return -1;
1958                 }
1959                 byte_in_group = bytenr - cache->key.objectid;
1960                 WARN_ON(byte_in_group > cache->key.offset);
1961                 start = cache->key.objectid;
1962                 end = start + cache->key.offset - 1;
1963                 set_extent_bits(&info->block_group_cache, start, end,
1964                                 BLOCK_GROUP_DIRTY);
1965
1966                 old_val = btrfs_block_group_used(&cache->item);
1967                 num_bytes = min(total, cache->key.offset - byte_in_group);
1968
1969                 if (alloc) {
1970                         old_val += num_bytes;
1971                         cache->space_info->bytes_used += num_bytes;
1972                 } else {
1973                         old_val -= num_bytes;
1974                         cache->space_info->bytes_used -= num_bytes;
1975                         if (mark_free) {
1976                                 set_extent_dirty(&info->free_space_cache,
1977                                                 bytenr, bytenr + num_bytes - 1);
1978                         }
1979                 }
1980                 btrfs_set_block_group_used(&cache->item, old_val);
1981                 total -= num_bytes;
1982                 bytenr += num_bytes;
1983         }
1984         return 0;
1985 }
1986
1987 static int update_pinned_extents(struct btrfs_root *root,
1988                                 u64 bytenr, u64 num, int pin)
1989 {
1990         u64 len;
1991         struct btrfs_block_group_cache *cache;
1992         struct btrfs_fs_info *fs_info = root->fs_info;
1993
1994         if (pin) {
1995                 set_extent_dirty(&fs_info->pinned_extents,
1996                                 bytenr, bytenr + num - 1);
1997         } else {
1998                 clear_extent_dirty(&fs_info->pinned_extents,
1999                                 bytenr, bytenr + num - 1);
2000         }
2001         while (num > 0) {
2002                 cache = btrfs_lookup_block_group(fs_info, bytenr);
2003                 if (!cache) {
2004                         len = min((u64)fs_info->sectorsize, num);
2005                         goto next;
2006                 }
2007                 WARN_ON(!cache);
2008                 len = min(num, cache->key.offset -
2009                           (bytenr - cache->key.objectid));
2010                 if (pin) {
2011                         cache->pinned += len;
2012                         cache->space_info->bytes_pinned += len;
2013                         fs_info->total_pinned += len;
2014                 } else {
2015                         cache->pinned -= len;
2016                         cache->space_info->bytes_pinned -= len;
2017                         fs_info->total_pinned -= len;
2018                 }
2019 next:
2020                 bytenr += len;
2021                 num -= len;
2022         }
2023         return 0;
2024 }
2025
2026 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
2027                                struct btrfs_root *root,
2028                                struct extent_io_tree *unpin)
2029 {
2030         u64 start;
2031         u64 end;
2032         int ret;
2033         struct extent_io_tree *free_space_cache;
2034         free_space_cache = &root->fs_info->free_space_cache;
2035
2036         while(1) {
2037                 ret = find_first_extent_bit(unpin, 0, &start, &end,
2038                                             EXTENT_DIRTY);
2039                 if (ret)
2040                         break;
2041                 update_pinned_extents(root, start, end + 1 - start, 0);
2042                 clear_extent_dirty(unpin, start, end);
2043                 set_extent_dirty(free_space_cache, start, end);
2044         }
2045         return 0;
2046 }
2047
2048 static int extent_root_pending_ops(struct btrfs_fs_info *info)
2049 {
2050         u64 start;
2051         u64 end;
2052         int ret;
2053
2054         ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2055                                     &end, EXTENT_LOCKED);
2056         if (!ret) {
2057                 ret = find_first_extent_bit(&info->pending_del, 0, &start, &end,
2058                                             EXTENT_LOCKED);
2059         }
2060         return ret == 0;
2061
2062 }
2063 static int finish_current_insert(struct btrfs_trans_handle *trans,
2064                                  struct btrfs_root *extent_root)
2065 {
2066         u64 start;
2067         u64 end;
2068         u64 priv;
2069         struct btrfs_fs_info *info = extent_root->fs_info;
2070         struct pending_extent_op *extent_op;
2071         struct btrfs_key key;
2072         int ret;
2073         int skinny_metadata =
2074                 btrfs_fs_incompat(extent_root->fs_info, SKINNY_METADATA);
2075
2076         while(1) {
2077                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2078                                             &end, EXTENT_LOCKED);
2079                 if (ret)
2080                         break;
2081
2082                 ret = get_state_private(&info->extent_ins, start, &priv);
2083                 BUG_ON(ret);
2084                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2085
2086                 if (extent_op->type == PENDING_EXTENT_INSERT) {
2087                         key.objectid = start;
2088                         if (skinny_metadata) {
2089                                 key.offset = extent_op->level;
2090                                 key.type = BTRFS_METADATA_ITEM_KEY;
2091                         } else {
2092                                 key.offset = extent_op->num_bytes;
2093                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2094                         }
2095                         ret = alloc_reserved_tree_block(trans, extent_root,
2096                                                 extent_root->root_key.objectid,
2097                                                 trans->transid,
2098                                                 extent_op->flags,
2099                                                 &extent_op->key,
2100                                                 extent_op->level, &key);
2101                         BUG_ON(ret);
2102                 } else {
2103                         BUG_ON(1);
2104                 }
2105
2106                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED);
2107                 kfree(extent_op);
2108         }
2109         return 0;
2110 }
2111
2112 static int pin_down_bytes(struct btrfs_trans_handle *trans,
2113                           struct btrfs_root *root,
2114                           u64 bytenr, u64 num_bytes, int is_data)
2115 {
2116         int err = 0;
2117         struct extent_buffer *buf;
2118
2119         if (is_data)
2120                 goto pinit;
2121
2122         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
2123         if (!buf)
2124                 goto pinit;
2125
2126         /* we can reuse a block if it hasn't been written
2127          * and it is from this transaction.  We can't
2128          * reuse anything from the tree log root because
2129          * it has tiny sub-transactions.
2130          */
2131         if (btrfs_buffer_uptodate(buf, 0)) {
2132                 u64 header_owner = btrfs_header_owner(buf);
2133                 u64 header_transid = btrfs_header_generation(buf);
2134                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
2135                     header_transid == trans->transid &&
2136                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
2137                         clean_tree_block(NULL, root, buf);
2138                         free_extent_buffer(buf);
2139                         return 1;
2140                 }
2141         }
2142         free_extent_buffer(buf);
2143 pinit:
2144         update_pinned_extents(root, bytenr, num_bytes, 1);
2145
2146         BUG_ON(err < 0);
2147         return 0;
2148 }
2149
2150 void btrfs_pin_extent(struct btrfs_fs_info *fs_info,
2151                        u64 bytenr, u64 num_bytes)
2152 {
2153         update_pinned_extents(fs_info->extent_root, bytenr, num_bytes, 1);
2154 }
2155
2156 void btrfs_unpin_extent(struct btrfs_fs_info *fs_info,
2157                         u64 bytenr, u64 num_bytes)
2158 {
2159         update_pinned_extents(fs_info->extent_root, bytenr, num_bytes, 0);
2160 }
2161
2162 /*
2163  * remove an extent from the root, returns 0 on success
2164  */
2165 static int __free_extent(struct btrfs_trans_handle *trans,
2166                          struct btrfs_root *root,
2167                          u64 bytenr, u64 num_bytes, u64 parent,
2168                          u64 root_objectid, u64 owner_objectid,
2169                          u64 owner_offset, int refs_to_drop)
2170 {
2171
2172         struct btrfs_key key;
2173         struct btrfs_path *path;
2174         struct btrfs_root *extent_root = root->fs_info->extent_root;
2175         struct extent_buffer *leaf;
2176         struct btrfs_extent_item *ei;
2177         struct btrfs_extent_inline_ref *iref;
2178         int ret;
2179         int is_data;
2180         int extent_slot = 0;
2181         int found_extent = 0;
2182         int num_to_del = 1;
2183         u32 item_size;
2184         u64 refs;
2185         int skinny_metadata =
2186                 btrfs_fs_incompat(extent_root->fs_info, SKINNY_METADATA);
2187
2188         if (root->fs_info->free_extent_hook) {
2189                 root->fs_info->free_extent_hook(trans, root, bytenr, num_bytes,
2190                                                 parent, root_objectid, owner_objectid,
2191                                                 owner_offset, refs_to_drop);
2192
2193         }
2194         path = btrfs_alloc_path();
2195         if (!path)
2196                 return -ENOMEM;
2197
2198         path->reada = 1;
2199
2200         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
2201         if (is_data)
2202                 skinny_metadata = 0;
2203         BUG_ON(!is_data && refs_to_drop != 1);
2204
2205         ret = lookup_extent_backref(trans, extent_root, path, &iref,
2206                                     bytenr, num_bytes, parent,
2207                                     root_objectid, owner_objectid,
2208                                     owner_offset);
2209         if (ret == 0) {
2210                 extent_slot = path->slots[0];
2211                 while (extent_slot >= 0) {
2212                         btrfs_item_key_to_cpu(path->nodes[0], &key,
2213                                               extent_slot);
2214                         if (key.objectid != bytenr)
2215                                 break;
2216                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
2217                             key.offset == num_bytes) {
2218                                 found_extent = 1;
2219                                 break;
2220                         }
2221                         if (key.type == BTRFS_METADATA_ITEM_KEY &&
2222                             key.offset == owner_objectid) {
2223                                 found_extent = 1;
2224                                 break;
2225                         }
2226                         if (path->slots[0] - extent_slot > 5)
2227                                 break;
2228                         extent_slot--;
2229                 }
2230 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2231                 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
2232                 if (found_extent && item_size < sizeof(*ei))
2233                         found_extent = 0;
2234 #endif
2235                 if (!found_extent) {
2236                         BUG_ON(iref);
2237                         ret = remove_extent_backref(trans, extent_root, path,
2238                                                     NULL, refs_to_drop,
2239                                                     is_data);
2240                         BUG_ON(ret);
2241                         btrfs_release_path(path);
2242
2243                         key.objectid = bytenr;
2244
2245                         if (skinny_metadata) {
2246                                 key.type = BTRFS_METADATA_ITEM_KEY;
2247                                 key.offset = owner_objectid;
2248                         } else {
2249                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2250                                 key.offset = num_bytes;
2251                         }
2252
2253                         ret = btrfs_search_slot(trans, extent_root,
2254                                                 &key, path, -1, 1);
2255                         if (ret > 0 && skinny_metadata && path->slots[0]) {
2256                                 path->slots[0]--;
2257                                 btrfs_item_key_to_cpu(path->nodes[0],
2258                                                       &key,
2259                                                       path->slots[0]);
2260                                 if (key.objectid == bytenr &&
2261                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
2262                                     key.offset == num_bytes)
2263                                         ret = 0;
2264                         }
2265
2266                         if (ret > 0 && skinny_metadata) {
2267                                 skinny_metadata = 0;
2268                                 btrfs_release_path(path);
2269                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2270                                 key.offset = num_bytes;
2271                                 ret = btrfs_search_slot(trans, extent_root,
2272                                                         &key, path, -1, 1);
2273                         }
2274
2275                         if (ret) {
2276                                 printk(KERN_ERR "umm, got %d back from search"
2277                                        ", was looking for %llu\n", ret,
2278                                        (unsigned long long)bytenr);
2279                                 btrfs_print_leaf(extent_root, path->nodes[0]);
2280                         }
2281                         BUG_ON(ret);
2282                         extent_slot = path->slots[0];
2283                 }
2284         } else {
2285                 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
2286                        "parent %llu root %llu  owner %llu offset %llu\n",
2287                        (unsigned long long)bytenr,
2288                        (unsigned long long)parent,
2289                        (unsigned long long)root_objectid,
2290                        (unsigned long long)owner_objectid,
2291                        (unsigned long long)owner_offset);
2292                 ret = -EIO;
2293                 goto fail;
2294         }
2295
2296         leaf = path->nodes[0];
2297         item_size = btrfs_item_size_nr(leaf, extent_slot);
2298 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2299         if (item_size < sizeof(*ei)) {
2300                 BUG_ON(found_extent || extent_slot != path->slots[0]);
2301                 ret = convert_extent_item_v0(trans, extent_root, path,
2302                                              owner_objectid, 0);
2303                 BUG_ON(ret < 0);
2304
2305                 btrfs_release_path(path);
2306
2307                 key.objectid = bytenr;
2308                 key.type = BTRFS_EXTENT_ITEM_KEY;
2309                 key.offset = num_bytes;
2310
2311                 ret = btrfs_search_slot(trans, extent_root, &key, path,
2312                                         -1, 1);
2313                 if (ret) {
2314                         printk(KERN_ERR "umm, got %d back from search"
2315                                ", was looking for %llu\n", ret,
2316                                (unsigned long long)bytenr);
2317                         btrfs_print_leaf(extent_root, path->nodes[0]);
2318                 }
2319                 BUG_ON(ret);
2320                 extent_slot = path->slots[0];
2321                 leaf = path->nodes[0];
2322                 item_size = btrfs_item_size_nr(leaf, extent_slot);
2323         }
2324 #endif
2325         BUG_ON(item_size < sizeof(*ei));
2326         ei = btrfs_item_ptr(leaf, extent_slot,
2327                             struct btrfs_extent_item);
2328         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
2329             key.type == BTRFS_EXTENT_ITEM_KEY) {
2330                 struct btrfs_tree_block_info *bi;
2331                 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
2332                 bi = (struct btrfs_tree_block_info *)(ei + 1);
2333                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
2334         }
2335
2336         refs = btrfs_extent_refs(leaf, ei);
2337         BUG_ON(refs < refs_to_drop);
2338         refs -= refs_to_drop;
2339
2340         if (refs > 0) {
2341                 /*
2342                  * In the case of inline back ref, reference count will
2343                  * be updated by remove_extent_backref
2344                  */
2345                 if (iref) {
2346                         BUG_ON(!found_extent);
2347                 } else {
2348                         btrfs_set_extent_refs(leaf, ei, refs);
2349                         btrfs_mark_buffer_dirty(leaf);
2350                 }
2351                 if (found_extent) {
2352                         ret = remove_extent_backref(trans, extent_root, path,
2353                                                     iref, refs_to_drop,
2354                                                     is_data);
2355                         BUG_ON(ret);
2356                 }
2357         } else {
2358                 int mark_free = 0;
2359                 int pin = 1;
2360
2361                 if (found_extent) {
2362                         BUG_ON(is_data && refs_to_drop !=
2363                                extent_data_ref_count(path, iref));
2364                         if (iref) {
2365                                 BUG_ON(path->slots[0] != extent_slot);
2366                         } else {
2367                                 BUG_ON(path->slots[0] != extent_slot + 1);
2368                                 path->slots[0] = extent_slot;
2369                                 num_to_del = 2;
2370                         }
2371                 }
2372
2373                 if (pin) {
2374                         ret = pin_down_bytes(trans, root, bytenr, num_bytes,
2375                                              is_data);
2376                         if (ret > 0)
2377                                 mark_free = 1;
2378                         BUG_ON(ret < 0);
2379                 }
2380
2381                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2382                                       num_to_del);
2383                 BUG_ON(ret);
2384                 btrfs_release_path(path);
2385
2386                 if (is_data) {
2387                         ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
2388                         BUG_ON(ret);
2389                 }
2390
2391                 update_block_group(trans, root, bytenr, num_bytes, 0, mark_free);
2392         }
2393 fail:
2394         btrfs_free_path(path);
2395         finish_current_insert(trans, extent_root);
2396         return ret;
2397 }
2398
2399 /*
2400  * find all the blocks marked as pending in the radix tree and remove
2401  * them from the extent map
2402  */
2403 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
2404                                btrfs_root *extent_root)
2405 {
2406         int ret;
2407         int err = 0;
2408         u64 start;
2409         u64 end;
2410         u64 priv;
2411         struct extent_io_tree *pending_del;
2412         struct extent_io_tree *extent_ins;
2413         struct pending_extent_op *extent_op;
2414
2415         extent_ins = &extent_root->fs_info->extent_ins;
2416         pending_del = &extent_root->fs_info->pending_del;
2417
2418         while(1) {
2419                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
2420                                             EXTENT_LOCKED);
2421                 if (ret)
2422                         break;
2423
2424                 ret = get_state_private(pending_del, start, &priv);
2425                 BUG_ON(ret);
2426                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2427
2428                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED);
2429
2430                 if (!test_range_bit(extent_ins, start, end,
2431                                     EXTENT_LOCKED, 0)) {
2432                         ret = __free_extent(trans, extent_root,
2433                                             start, end + 1 - start, 0,
2434                                             extent_root->root_key.objectid,
2435                                             extent_op->level, 0, 1);
2436                         kfree(extent_op);
2437                 } else {
2438                         kfree(extent_op);
2439                         ret = get_state_private(extent_ins, start, &priv);
2440                         BUG_ON(ret);
2441                         extent_op = (struct pending_extent_op *)
2442                                                         (unsigned long)priv;
2443
2444                         clear_extent_bits(extent_ins, start, end,
2445                                           EXTENT_LOCKED);
2446
2447                         if (extent_op->type == PENDING_BACKREF_UPDATE)
2448                                 BUG_ON(1);
2449
2450                         kfree(extent_op);
2451                 }
2452                 if (ret)
2453                         err = ret;
2454         }
2455         return err;
2456 }
2457
2458
2459 int btrfs_free_tree_block(struct btrfs_trans_handle *trans,
2460                           struct btrfs_root *root,
2461                           struct extent_buffer *buf,
2462                           u64 parent, int last_ref)
2463 {
2464         return btrfs_free_extent(trans, root, buf->start, buf->len, parent,
2465                                  root->root_key.objectid,
2466                                  btrfs_header_level(buf), 0);
2467 }
2468
2469 /*
2470  * remove an extent from the root, returns 0 on success
2471  */
2472
2473 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2474                       struct btrfs_root *root,
2475                       u64 bytenr, u64 num_bytes, u64 parent,
2476                       u64 root_objectid, u64 owner, u64 offset)
2477 {
2478         struct btrfs_root *extent_root = root->fs_info->extent_root;
2479         int pending_ret;
2480         int ret;
2481
2482         WARN_ON(num_bytes < root->fs_info->sectorsize);
2483         if (root == extent_root) {
2484                 struct pending_extent_op *extent_op;
2485
2486                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2487                 BUG_ON(!extent_op);
2488
2489                 extent_op->type = PENDING_EXTENT_DELETE;
2490                 extent_op->bytenr = bytenr;
2491                 extent_op->num_bytes = num_bytes;
2492                 extent_op->level = (int)owner;
2493
2494                 set_extent_bits(&root->fs_info->pending_del,
2495                                 bytenr, bytenr + num_bytes - 1,
2496                                 EXTENT_LOCKED);
2497                 set_state_private(&root->fs_info->pending_del,
2498                                   bytenr, (unsigned long)extent_op);
2499                 return 0;
2500         }
2501         ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2502                             root_objectid, owner, offset, 1);
2503         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2504         return ret ? ret : pending_ret;
2505 }
2506
2507 static u64 stripe_align(struct btrfs_root *root, u64 val)
2508 {
2509         return round_up(val, (u64)root->fs_info->stripesize);
2510 }
2511
2512 /*
2513  * walks the btree of allocated extents and find a hole of a given size.
2514  * The key ins is changed to record the hole:
2515  * ins->objectid == block start
2516  * ins->flags = BTRFS_EXTENT_ITEM_KEY
2517  * ins->offset == number of blocks
2518  * Any available blocks before search_start are skipped.
2519  */
2520 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
2521                                      struct btrfs_root *orig_root,
2522                                      u64 num_bytes, u64 empty_size,
2523                                      u64 search_start, u64 search_end,
2524                                      u64 hint_byte, struct btrfs_key *ins,
2525                                      u64 exclude_start, u64 exclude_nr,
2526                                      int data)
2527 {
2528         int ret;
2529         u64 orig_search_start = search_start;
2530         struct btrfs_root * root = orig_root->fs_info->extent_root;
2531         struct btrfs_fs_info *info = root->fs_info;
2532         u64 total_needed = num_bytes;
2533         struct btrfs_block_group_cache *block_group;
2534         int full_scan = 0;
2535         int wrapped = 0;
2536
2537         WARN_ON(num_bytes < info->sectorsize);
2538         ins->type = BTRFS_EXTENT_ITEM_KEY;
2539
2540         search_start = stripe_align(root, search_start);
2541
2542         if (hint_byte) {
2543                 block_group = btrfs_lookup_first_block_group(info, hint_byte);
2544                 if (!block_group)
2545                         hint_byte = search_start;
2546                 block_group = btrfs_find_block_group(root, block_group,
2547                                                      hint_byte, data, 1);
2548         } else {
2549                 block_group = btrfs_find_block_group(root,
2550                                                      trans->block_group,
2551                                                      search_start, data, 1);
2552         }
2553
2554         total_needed += empty_size;
2555
2556 check_failed:
2557         search_start = stripe_align(root, search_start);
2558         if (!block_group) {
2559                 block_group = btrfs_lookup_first_block_group(info,
2560                                                              search_start);
2561                 if (!block_group)
2562                         block_group = btrfs_lookup_first_block_group(info,
2563                                                        orig_search_start);
2564         }
2565         ret = find_search_start(root, &block_group, &search_start,
2566                                 total_needed, data);
2567         if (ret)
2568                 goto new_group;
2569
2570         ins->objectid = search_start;
2571         ins->offset = num_bytes;
2572
2573         if (ins->objectid + num_bytes >
2574             block_group->key.objectid + block_group->key.offset) {
2575                 search_start = block_group->key.objectid +
2576                         block_group->key.offset;
2577                 goto new_group;
2578         }
2579
2580         if (test_range_bit(&info->extent_ins, ins->objectid,
2581                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
2582                 search_start = ins->objectid + num_bytes;
2583                 goto new_group;
2584         }
2585
2586         if (test_range_bit(&info->pinned_extents, ins->objectid,
2587                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2588                 search_start = ins->objectid + num_bytes;
2589                 goto new_group;
2590         }
2591
2592         if (info->excluded_extents &&
2593             test_range_bit(info->excluded_extents, ins->objectid,
2594                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2595                 search_start = ins->objectid + num_bytes;
2596                 goto new_group;
2597         }
2598
2599         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2600             ins->objectid < exclude_start + exclude_nr)) {
2601                 search_start = exclude_start + exclude_nr;
2602                 goto new_group;
2603         }
2604
2605         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
2606                 if (check_crossing_stripes(info, ins->objectid, num_bytes)) {
2607                         struct btrfs_block_group_cache *bg_cache;
2608                         u64 bg_offset;
2609
2610                         bg_cache = btrfs_lookup_block_group(info, ins->objectid);
2611                         if (!bg_cache)
2612                                 goto no_bg_cache;
2613                         bg_offset = ins->objectid - bg_cache->key.objectid;
2614
2615                         search_start = round_up(bg_offset + num_bytes,
2616                                                 BTRFS_STRIPE_LEN) + bg_offset;
2617                         goto new_group;
2618                 }
2619 no_bg_cache:
2620                 block_group = btrfs_lookup_block_group(info, ins->objectid);
2621                 if (block_group)
2622                         trans->block_group = block_group;
2623         }
2624         ins->offset = num_bytes;
2625         return 0;
2626
2627 new_group:
2628         block_group = btrfs_lookup_first_block_group(info, search_start);
2629         if (!block_group) {
2630                 search_start = orig_search_start;
2631                 if (full_scan) {
2632                         ret = -ENOSPC;
2633                         goto error;
2634                 }
2635                 if (wrapped) {
2636                         if (!full_scan)
2637                                 total_needed -= empty_size;
2638                         full_scan = 1;
2639                 } else
2640                         wrapped = 1;
2641         }
2642         cond_resched();
2643         block_group = btrfs_find_block_group(root, block_group,
2644                                              search_start, data, 0);
2645         goto check_failed;
2646
2647 error:
2648         return ret;
2649 }
2650
2651 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2652                          struct btrfs_root *root,
2653                          u64 num_bytes, u64 empty_size,
2654                          u64 hint_byte, u64 search_end,
2655                          struct btrfs_key *ins, int data)
2656 {
2657         int ret;
2658         u64 search_start = 0;
2659         u64 alloc_profile;
2660         struct btrfs_fs_info *info = root->fs_info;
2661
2662         if (data) {
2663                 alloc_profile = info->avail_data_alloc_bits &
2664                                 info->data_alloc_profile;
2665                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2666         } else if ((info->system_allocs > 0 || root == info->chunk_root) &&
2667                    info->system_allocs >= 0) {
2668                 alloc_profile = info->avail_system_alloc_bits &
2669                                 info->system_alloc_profile;
2670                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2671         } else {
2672                 alloc_profile = info->avail_metadata_alloc_bits &
2673                                 info->metadata_alloc_profile;
2674                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2675         }
2676
2677         if (root->ref_cows) {
2678                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2679                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2680                                              num_bytes,
2681                                              BTRFS_BLOCK_GROUP_METADATA);
2682                         BUG_ON(ret);
2683                 }
2684                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2685                                      num_bytes + SZ_2M, data);
2686                 BUG_ON(ret);
2687         }
2688
2689         WARN_ON(num_bytes < info->sectorsize);
2690         ret = find_free_extent(trans, root, num_bytes, empty_size,
2691                                search_start, search_end, hint_byte, ins,
2692                                trans->alloc_exclude_start,
2693                                trans->alloc_exclude_nr, data);
2694         BUG_ON(ret);
2695         clear_extent_dirty(&root->fs_info->free_space_cache,
2696                            ins->objectid, ins->objectid + ins->offset - 1);
2697         return ret;
2698 }
2699
2700 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
2701                                      struct btrfs_root *root,
2702                                      u64 root_objectid, u64 generation,
2703                                      u64 flags, struct btrfs_disk_key *key,
2704                                      int level, struct btrfs_key *ins)
2705 {
2706         int ret;
2707         struct btrfs_fs_info *fs_info = root->fs_info;
2708         struct btrfs_extent_item *extent_item;
2709         struct btrfs_tree_block_info *block_info;
2710         struct btrfs_extent_inline_ref *iref;
2711         struct btrfs_path *path;
2712         struct extent_buffer *leaf;
2713         u32 size = sizeof(*extent_item) + sizeof(*iref);
2714         int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
2715
2716         if (!skinny_metadata)
2717                 size += sizeof(*block_info);
2718
2719         path = btrfs_alloc_path();
2720         if (!path)
2721                 return -ENOMEM;
2722
2723         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
2724                                       ins, size);
2725         BUG_ON(ret);
2726
2727         leaf = path->nodes[0];
2728         extent_item = btrfs_item_ptr(leaf, path->slots[0],
2729                                      struct btrfs_extent_item);
2730         btrfs_set_extent_refs(leaf, extent_item, 1);
2731         btrfs_set_extent_generation(leaf, extent_item, generation);
2732         btrfs_set_extent_flags(leaf, extent_item,
2733                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
2734
2735         if (skinny_metadata) {
2736                 iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
2737         } else {
2738                 block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
2739                 btrfs_set_tree_block_key(leaf, block_info, key);
2740                 btrfs_set_tree_block_level(leaf, block_info, level);
2741                 iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
2742         }
2743
2744         btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY);
2745         btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
2746
2747         btrfs_mark_buffer_dirty(leaf);
2748         btrfs_free_path(path);
2749
2750         ret = update_block_group(trans, root, ins->objectid, fs_info->nodesize,
2751                                  1, 0);
2752         return ret;
2753 }
2754
2755 static int alloc_tree_block(struct btrfs_trans_handle *trans,
2756                             struct btrfs_root *root, u64 num_bytes,
2757                             u64 root_objectid, u64 generation,
2758                             u64 flags, struct btrfs_disk_key *key,
2759                             int level, u64 empty_size, u64 hint_byte,
2760                             u64 search_end, struct btrfs_key *ins)
2761 {
2762         int ret;
2763         ret = btrfs_reserve_extent(trans, root, num_bytes, empty_size,
2764                                    hint_byte, search_end, ins, 0);
2765         BUG_ON(ret);
2766
2767         if (root_objectid == BTRFS_EXTENT_TREE_OBJECTID) {
2768                 struct pending_extent_op *extent_op;
2769
2770                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2771                 BUG_ON(!extent_op);
2772
2773                 extent_op->type = PENDING_EXTENT_INSERT;
2774                 extent_op->bytenr = ins->objectid;
2775                 extent_op->num_bytes = ins->offset;
2776                 extent_op->level = level;
2777                 extent_op->flags = flags;
2778                 memcpy(&extent_op->key, key, sizeof(*key));
2779
2780                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2781                                 ins->objectid + ins->offset - 1,
2782                                 EXTENT_LOCKED);
2783                 set_state_private(&root->fs_info->extent_ins,
2784                                   ins->objectid, (unsigned long)extent_op);
2785         } else {
2786                 if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) {
2787                         ins->offset = level;
2788                         ins->type = BTRFS_METADATA_ITEM_KEY;
2789                 }
2790                 ret = alloc_reserved_tree_block(trans, root, root_objectid,
2791                                                 generation, flags,
2792                                                 key, level, ins);
2793                 finish_current_insert(trans, root->fs_info->extent_root);
2794                 del_pending_extents(trans, root->fs_info->extent_root);
2795         }
2796         return ret;
2797 }
2798
2799 /*
2800  * helper function to allocate a block for a given tree
2801  * returns the tree buffer or NULL.
2802  */
2803 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2804                                         struct btrfs_root *root,
2805                                         u32 blocksize, u64 root_objectid,
2806                                         struct btrfs_disk_key *key, int level,
2807                                         u64 hint, u64 empty_size)
2808 {
2809         struct btrfs_key ins;
2810         int ret;
2811         struct extent_buffer *buf;
2812
2813         ret = alloc_tree_block(trans, root, blocksize, root_objectid,
2814                                trans->transid, 0, key, level,
2815                                empty_size, hint, (u64)-1, &ins);
2816         if (ret) {
2817                 BUG_ON(ret > 0);
2818                 return ERR_PTR(ret);
2819         }
2820
2821         buf = btrfs_find_create_tree_block(root->fs_info, ins.objectid,
2822                                            blocksize);
2823         if (!buf) {
2824                 btrfs_free_extent(trans, root, ins.objectid, ins.offset,
2825                                   0, root->root_key.objectid, level, 0);
2826                 BUG_ON(1);
2827                 return ERR_PTR(-ENOMEM);
2828         }
2829         btrfs_set_buffer_uptodate(buf);
2830         trans->blocks_used++;
2831
2832         return buf;
2833 }
2834
2835 #if 0
2836
2837 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2838                                   struct btrfs_root *root,
2839                                   struct extent_buffer *leaf)
2840 {
2841         u64 leaf_owner;
2842         u64 leaf_generation;
2843         struct btrfs_key key;
2844         struct btrfs_file_extent_item *fi;
2845         int i;
2846         int nritems;
2847         int ret;
2848
2849         BUG_ON(!btrfs_is_leaf(leaf));
2850         nritems = btrfs_header_nritems(leaf);
2851         leaf_owner = btrfs_header_owner(leaf);
2852         leaf_generation = btrfs_header_generation(leaf);
2853
2854         for (i = 0; i < nritems; i++) {
2855                 u64 disk_bytenr;
2856
2857                 btrfs_item_key_to_cpu(leaf, &key, i);
2858                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2859                         continue;
2860                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2861                 if (btrfs_file_extent_type(leaf, fi) ==
2862                     BTRFS_FILE_EXTENT_INLINE)
2863                         continue;
2864                 /*
2865                  * FIXME make sure to insert a trans record that
2866                  * repeats the snapshot del on crash
2867                  */
2868                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2869                 if (disk_bytenr == 0)
2870                         continue;
2871                 ret = btrfs_free_extent(trans, root, disk_bytenr,
2872                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2873                                 leaf->start, leaf_owner, leaf_generation,
2874                                 key.objectid, 0);
2875                 BUG_ON(ret);
2876         }
2877         return 0;
2878 }
2879
2880 static void noinline reada_walk_down(struct btrfs_root *root,
2881                                      struct extent_buffer *node,
2882                                      int slot)
2883 {
2884         u64 bytenr;
2885         u64 last = 0;
2886         u32 nritems;
2887         u32 refs;
2888         u32 blocksize;
2889         int ret;
2890         int i;
2891         int level;
2892         int skipped = 0;
2893
2894         nritems = btrfs_header_nritems(node);
2895         level = btrfs_header_level(node);
2896         if (level)
2897                 return;
2898
2899         for (i = slot; i < nritems && skipped < 32; i++) {
2900                 bytenr = btrfs_node_blockptr(node, i);
2901                 if (last && ((bytenr > last && bytenr - last > SZ_32K) ||
2902                              (last > bytenr && last - bytenr > SZ_32K))) {
2903                         skipped++;
2904                         continue;
2905                 }
2906                 blocksize = btrfs_level_size(root, level - 1);
2907                 if (i != slot) {
2908                         ret = btrfs_lookup_extent_ref(NULL, root, bytenr,
2909                                                       blocksize, &refs);
2910                         BUG_ON(ret);
2911                         if (refs != 1) {
2912                                 skipped++;
2913                                 continue;
2914                         }
2915                 }
2916                 mutex_unlock(&root->fs_info->fs_mutex);
2917                 ret = readahead_tree_block(root, bytenr, blocksize,
2918                                            btrfs_node_ptr_generation(node, i));
2919                 last = bytenr + blocksize;
2920                 cond_resched();
2921                 mutex_lock(&root->fs_info->fs_mutex);
2922                 if (ret)
2923                         break;
2924         }
2925 }
2926
2927 /*
2928  * helper function for drop_snapshot, this walks down the tree dropping ref
2929  * counts as it goes.
2930  */
2931 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2932                                    struct btrfs_root *root,
2933                                    struct btrfs_path *path, int *level)
2934 {
2935         u64 root_owner;
2936         u64 root_gen;
2937         u64 bytenr;
2938         u64 ptr_gen;
2939         struct extent_buffer *next;
2940         struct extent_buffer *cur;
2941         struct extent_buffer *parent;
2942         u32 blocksize;
2943         int ret;
2944         u32 refs;
2945
2946         WARN_ON(*level < 0);
2947         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2948         ret = btrfs_lookup_extent_ref(trans, root,
2949                                       path->nodes[*level]->start,
2950                                       path->nodes[*level]->len, &refs);
2951         BUG_ON(ret);
2952         if (refs > 1)
2953                 goto out;
2954
2955         /*
2956          * walk down to the last node level and free all the leaves
2957          */
2958         while(*level >= 0) {
2959                 WARN_ON(*level < 0);
2960                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2961                 cur = path->nodes[*level];
2962
2963                 if (btrfs_header_level(cur) != *level)
2964                         WARN_ON(1);
2965
2966                 if (path->slots[*level] >=
2967                     btrfs_header_nritems(cur))
2968                         break;
2969                 if (*level == 0) {
2970                         ret = drop_leaf_ref(trans, root, cur);
2971                         BUG_ON(ret);
2972                         break;
2973                 }
2974                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2975                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2976                 blocksize = btrfs_level_size(root, *level - 1);
2977                 ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
2978                                               &refs);
2979                 BUG_ON(ret);
2980                 if (refs != 1) {
2981                         parent = path->nodes[*level];
2982                         root_owner = btrfs_header_owner(parent);
2983                         root_gen = btrfs_header_generation(parent);
2984                         path->slots[*level]++;
2985                         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
2986                                                 parent->start, root_owner,
2987                                                 root_gen, *level - 1, 1);
2988                         BUG_ON(ret);
2989                         continue;
2990                 }
2991                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2992                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2993                         free_extent_buffer(next);
2994                         reada_walk_down(root, cur, path->slots[*level]);
2995                         mutex_unlock(&root->fs_info->fs_mutex);
2996                         next = read_tree_block(root, bytenr, blocksize,
2997                                                ptr_gen);
2998                         mutex_lock(&root->fs_info->fs_mutex);
2999                         if (!extent_buffer_uptodate(next)) {
3000                                 if (IS_ERR(next))
3001                                         ret = PTR_ERR(next);
3002                                 else
3003                                         ret = -EIO;
3004                                 break;
3005                         }
3006                 }
3007                 WARN_ON(*level <= 0);
3008                 if (path->nodes[*level-1])
3009                         free_extent_buffer(path->nodes[*level-1]);
3010                 path->nodes[*level-1] = next;
3011                 *level = btrfs_header_level(next);
3012                 path->slots[*level] = 0;
3013         }
3014 out:
3015         WARN_ON(*level < 0);
3016         WARN_ON(*level >= BTRFS_MAX_LEVEL);
3017
3018         if (path->nodes[*level] == root->node) {
3019                 root_owner = root->root_key.objectid;
3020                 parent = path->nodes[*level];
3021         } else {
3022                 parent = path->nodes[*level + 1];
3023                 root_owner = btrfs_header_owner(parent);
3024         }
3025
3026         root_gen = btrfs_header_generation(parent);
3027         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
3028                                 path->nodes[*level]->len, parent->start,
3029                                 root_owner, root_gen, *level, 1);
3030         free_extent_buffer(path->nodes[*level]);
3031         path->nodes[*level] = NULL;
3032         *level += 1;
3033         BUG_ON(ret);
3034         return 0;
3035 }
3036
3037 /*
3038  * helper for dropping snapshots.  This walks back up the tree in the path
3039  * to find the first node higher up where we haven't yet gone through
3040  * all the slots
3041  */
3042 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
3043                                  struct btrfs_root *root,
3044                                  struct btrfs_path *path, int *level)
3045 {
3046         u64 root_owner;
3047         u64 root_gen;
3048         struct btrfs_root_item *root_item = &root->root_item;
3049         int i;
3050         int slot;
3051         int ret;
3052
3053         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
3054                 slot = path->slots[i];
3055                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3056                         struct extent_buffer *node;
3057                         struct btrfs_disk_key disk_key;
3058                         node = path->nodes[i];
3059                         path->slots[i]++;
3060                         *level = i;
3061                         WARN_ON(*level == 0);
3062                         btrfs_node_key(node, &disk_key, path->slots[i]);
3063                         memcpy(&root_item->drop_progress,
3064                                &disk_key, sizeof(disk_key));
3065                         root_item->drop_level = i;
3066                         return 0;
3067                 } else {
3068                         struct extent_buffer *parent;
3069                         if (path->nodes[*level] == root->node)
3070                                 parent = path->nodes[*level];
3071                         else
3072                                 parent = path->nodes[*level + 1];
3073
3074                         root_owner = btrfs_header_owner(parent);
3075                         root_gen = btrfs_header_generation(parent);
3076                         ret = btrfs_free_extent(trans, root,
3077                                                 path->nodes[*level]->start,
3078                                                 path->nodes[*level]->len,
3079                                                 parent->start, root_owner,
3080                                                 root_gen, *level, 1);
3081                         BUG_ON(ret);
3082                         free_extent_buffer(path->nodes[*level]);
3083                         path->nodes[*level] = NULL;
3084                         *level = i + 1;
3085                 }
3086         }
3087         return 1;
3088 }
3089
3090 #endif
3091
3092 int btrfs_free_block_groups(struct btrfs_fs_info *info)
3093 {
3094         struct btrfs_space_info *sinfo;
3095         struct btrfs_block_group_cache *cache;
3096         u64 start;
3097         u64 end;
3098         u64 ptr;
3099         int ret;
3100
3101         while(1) {
3102                 ret = find_first_extent_bit(&info->block_group_cache, 0,
3103                                             &start, &end, (unsigned int)-1);
3104                 if (ret)
3105                         break;
3106                 ret = get_state_private(&info->block_group_cache, start, &ptr);
3107                 if (!ret) {
3108                         cache = u64_to_ptr(ptr);
3109                         if (cache->free_space_ctl) {
3110                                 btrfs_remove_free_space_cache(cache);
3111                                 kfree(cache->free_space_ctl);
3112                         }
3113                         kfree(cache);
3114                 }
3115                 clear_extent_bits(&info->block_group_cache, start,
3116                                   end, (unsigned int)-1);
3117         }
3118         while(1) {
3119                 ret = find_first_extent_bit(&info->free_space_cache, 0,
3120                                             &start, &end, EXTENT_DIRTY);
3121                 if (ret)
3122                         break;
3123                 clear_extent_dirty(&info->free_space_cache, start, end);
3124         }
3125
3126         while (!list_empty(&info->space_info)) {
3127                 sinfo = list_entry(info->space_info.next,
3128                                    struct btrfs_space_info, list);
3129                 list_del_init(&sinfo->list);
3130                 kfree(sinfo);
3131         }
3132         return 0;
3133 }
3134
3135 static int find_first_block_group(struct btrfs_root *root,
3136                 struct btrfs_path *path, struct btrfs_key *key)
3137 {
3138         int ret;
3139         struct btrfs_key found_key;
3140         struct extent_buffer *leaf;
3141         int slot;
3142
3143         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
3144         if (ret < 0)
3145                 return ret;
3146         while(1) {
3147                 slot = path->slots[0];
3148                 leaf = path->nodes[0];
3149                 if (slot >= btrfs_header_nritems(leaf)) {
3150                         ret = btrfs_next_leaf(root, path);
3151                         if (ret == 0)
3152                                 continue;
3153                         if (ret < 0)
3154                                 goto error;
3155                         break;
3156                 }
3157                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3158
3159                 if (found_key.objectid >= key->objectid &&
3160                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
3161                         return 0;
3162                 path->slots[0]++;
3163         }
3164         ret = -ENOENT;
3165 error:
3166         return ret;
3167 }
3168
3169 static void account_super_bytes(struct btrfs_fs_info *fs_info,
3170                                 struct btrfs_block_group_cache *cache)
3171 {
3172         u64 bytenr;
3173         u64 *logical;
3174         int stripe_len;
3175         int i, nr, ret;
3176
3177         if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
3178                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
3179                 cache->bytes_super += stripe_len;
3180         }
3181
3182         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
3183                 bytenr = btrfs_sb_offset(i);
3184                 ret = btrfs_rmap_block(fs_info,
3185                                        cache->key.objectid, bytenr,
3186                                        0, &logical, &nr, &stripe_len);
3187                 if (ret)
3188                         return;
3189
3190                 while (nr--) {
3191                         u64 start, len;
3192
3193                         if (logical[nr] > cache->key.objectid +
3194                             cache->key.offset)
3195                                 continue;
3196
3197                         if (logical[nr] + stripe_len <= cache->key.objectid)
3198                                 continue;
3199
3200                         start = logical[nr];
3201                         if (start < cache->key.objectid) {
3202                                 start = cache->key.objectid;
3203                                 len = (logical[nr] + stripe_len) - start;
3204                         } else {
3205                                 len = min_t(u64, stripe_len,
3206                                             cache->key.objectid +
3207                                             cache->key.offset - start);
3208                         }
3209
3210                         cache->bytes_super += len;
3211                 }
3212
3213                 kfree(logical);
3214         }
3215 }
3216
3217 int btrfs_read_block_groups(struct btrfs_root *root)
3218 {
3219         struct btrfs_path *path;
3220         int ret;
3221         int bit;
3222         struct btrfs_block_group_cache *cache;
3223         struct btrfs_fs_info *info = root->fs_info;
3224         struct btrfs_space_info *space_info;
3225         struct extent_io_tree *block_group_cache;
3226         struct btrfs_key key;
3227         struct btrfs_key found_key;
3228         struct extent_buffer *leaf;
3229
3230         block_group_cache = &info->block_group_cache;
3231
3232         root = info->extent_root;
3233         key.objectid = 0;
3234         key.offset = 0;
3235         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3236         path = btrfs_alloc_path();
3237         if (!path)
3238                 return -ENOMEM;
3239
3240         while(1) {
3241                 ret = find_first_block_group(root, path, &key);
3242                 if (ret > 0) {
3243                         ret = 0;
3244                         goto error;
3245                 }
3246                 if (ret != 0) {
3247                         goto error;
3248                 }
3249                 leaf = path->nodes[0];
3250                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3251
3252                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3253                 if (!cache) {
3254                         ret = -ENOMEM;
3255                         goto error;
3256                 }
3257
3258                 read_extent_buffer(leaf, &cache->item,
3259                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
3260                                    sizeof(cache->item));
3261                 memcpy(&cache->key, &found_key, sizeof(found_key));
3262                 cache->cached = 0;
3263                 cache->pinned = 0;
3264                 key.objectid = found_key.objectid + found_key.offset;
3265                 if (found_key.offset == 0)
3266                         key.objectid++;
3267                 btrfs_release_path(path);
3268
3269                 /*
3270                  * Skip 0 sized block group, don't insert them into block
3271                  * group cache tree, as its length is 0, it won't get
3272                  * freed at close_ctree() time.
3273                  */
3274                 if (found_key.offset == 0) {
3275                         free(cache);
3276                         continue;
3277                 }
3278
3279                 cache->flags = btrfs_block_group_flags(&cache->item);
3280                 bit = 0;
3281                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3282                         bit = BLOCK_GROUP_DATA;
3283                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
3284                         bit = BLOCK_GROUP_SYSTEM;
3285                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3286                         bit = BLOCK_GROUP_METADATA;
3287                 }
3288                 set_avail_alloc_bits(info, cache->flags);
3289                 if (btrfs_chunk_readonly(root, cache->key.objectid))
3290                         cache->ro = 1;
3291
3292                 account_super_bytes(info, cache);
3293
3294                 ret = update_space_info(info, cache->flags, found_key.offset,
3295                                         btrfs_block_group_used(&cache->item),
3296                                         &space_info);
3297                 BUG_ON(ret);
3298                 cache->space_info = space_info;
3299
3300                 /* use EXTENT_LOCKED to prevent merging */
3301                 set_extent_bits(block_group_cache, found_key.objectid,
3302                                 found_key.objectid + found_key.offset - 1,
3303                                 bit | EXTENT_LOCKED);
3304                 set_state_private(block_group_cache, found_key.objectid,
3305                                   (unsigned long)cache);
3306         }
3307         ret = 0;
3308 error:
3309         btrfs_free_path(path);
3310         return ret;
3311 }
3312
3313 struct btrfs_block_group_cache *
3314 btrfs_add_block_group(struct btrfs_fs_info *fs_info, u64 bytes_used, u64 type,
3315                       u64 chunk_objectid, u64 chunk_offset, u64 size)
3316 {
3317         int ret;
3318         int bit = 0;
3319         struct btrfs_block_group_cache *cache;
3320         struct extent_io_tree *block_group_cache;
3321
3322         block_group_cache = &fs_info->block_group_cache;
3323
3324         cache = kzalloc(sizeof(*cache), GFP_NOFS);
3325         BUG_ON(!cache);
3326         cache->key.objectid = chunk_offset;
3327         cache->key.offset = size;
3328
3329         cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3330         btrfs_set_block_group_used(&cache->item, bytes_used);
3331         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
3332         cache->flags = type;
3333         btrfs_set_block_group_flags(&cache->item, type);
3334
3335         account_super_bytes(fs_info, cache);
3336         ret = update_space_info(fs_info, cache->flags, size, bytes_used,
3337                                 &cache->space_info);
3338         BUG_ON(ret);
3339
3340         bit = block_group_state_bits(type);
3341         ret = set_extent_bits(block_group_cache, chunk_offset,
3342                               chunk_offset + size - 1,
3343                               bit | EXTENT_LOCKED);
3344         BUG_ON(ret);
3345
3346         ret = set_state_private(block_group_cache, chunk_offset,
3347                                 (unsigned long)cache);
3348         BUG_ON(ret);
3349         set_avail_alloc_bits(fs_info, type);
3350
3351         return cache;
3352 }
3353
3354 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
3355                            struct btrfs_root *root, u64 bytes_used,
3356                            u64 type, u64 chunk_objectid, u64 chunk_offset,
3357                            u64 size)
3358 {
3359         int ret;
3360         struct btrfs_root *extent_root;
3361         struct btrfs_block_group_cache *cache;
3362
3363         cache = btrfs_add_block_group(root->fs_info, bytes_used, type,
3364                                       chunk_objectid, chunk_offset, size);
3365         extent_root = root->fs_info->extent_root;
3366         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3367                                 sizeof(cache->item));
3368         BUG_ON(ret);
3369
3370         ret = finish_current_insert(trans, extent_root);
3371         BUG_ON(ret);
3372         ret = del_pending_extents(trans, extent_root);
3373         BUG_ON(ret);
3374
3375         return 0;
3376 }
3377
3378 /*
3379  * This is for converter use only.
3380  *
3381  * In that case, we don't know where are free blocks located.
3382  * Therefore all block group cache entries must be setup properly
3383  * before doing any block allocation.
3384  */
3385 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
3386                             struct btrfs_root *root)
3387 {
3388         u64 total_bytes;
3389         u64 cur_start;
3390         u64 group_type;
3391         u64 group_size;
3392         u64 group_align;
3393         u64 total_data = 0;
3394         u64 total_metadata = 0;
3395         u64 chunk_objectid;
3396         int ret;
3397         int bit;
3398         struct btrfs_root *extent_root;
3399         struct btrfs_block_group_cache *cache;
3400         struct extent_io_tree *block_group_cache;
3401
3402         extent_root = root->fs_info->extent_root;
3403         block_group_cache = &root->fs_info->block_group_cache;
3404         chunk_objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3405         total_bytes = btrfs_super_total_bytes(root->fs_info->super_copy);
3406         group_align = 64 * root->fs_info->sectorsize;
3407
3408         cur_start = 0;
3409         while (cur_start < total_bytes) {
3410                 group_size = total_bytes / 12;
3411                 group_size = min_t(u64, group_size, total_bytes - cur_start);
3412                 if (cur_start == 0) {
3413                         bit = BLOCK_GROUP_SYSTEM;
3414                         group_type = BTRFS_BLOCK_GROUP_SYSTEM;
3415                         group_size /= 4;
3416                         group_size &= ~(group_align - 1);
3417                         group_size = max_t(u64, group_size, SZ_8M);
3418                         group_size = min_t(u64, group_size, SZ_32M);
3419                 } else {
3420                         group_size &= ~(group_align - 1);
3421                         if (total_data >= total_metadata * 2) {
3422                                 group_type = BTRFS_BLOCK_GROUP_METADATA;
3423                                 group_size = min_t(u64, group_size, SZ_1G);
3424                                 total_metadata += group_size;
3425                         } else {
3426                                 group_type = BTRFS_BLOCK_GROUP_DATA;
3427                                 group_size = min_t(u64, group_size,
3428                                                    5ULL * SZ_1G);
3429                                 total_data += group_size;
3430                         }
3431                         if ((total_bytes - cur_start) * 4 < group_size * 5)
3432                                 group_size = total_bytes - cur_start;
3433                 }
3434
3435                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3436                 BUG_ON(!cache);
3437
3438                 cache->key.objectid = cur_start;
3439                 cache->key.offset = group_size;
3440                 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3441
3442                 btrfs_set_block_group_used(&cache->item, 0);
3443                 btrfs_set_block_group_chunk_objectid(&cache->item,
3444                                                      chunk_objectid);
3445                 btrfs_set_block_group_flags(&cache->item, group_type);
3446
3447                 cache->flags = group_type;
3448
3449                 ret = update_space_info(root->fs_info, group_type, group_size,
3450                                         0, &cache->space_info);
3451                 BUG_ON(ret);
3452                 set_avail_alloc_bits(extent_root->fs_info, group_type);
3453
3454                 set_extent_bits(block_group_cache, cur_start,
3455                                 cur_start + group_size - 1,
3456                                 bit | EXTENT_LOCKED);
3457                 set_state_private(block_group_cache, cur_start,
3458                                   (unsigned long)cache);
3459                 cur_start += group_size;
3460         }
3461         /* then insert all the items */
3462         cur_start = 0;
3463         while(cur_start < total_bytes) {
3464                 cache = btrfs_lookup_block_group(root->fs_info, cur_start);
3465                 BUG_ON(!cache);
3466
3467                 ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3468                                         sizeof(cache->item));
3469                 BUG_ON(ret);
3470
3471                 finish_current_insert(trans, extent_root);
3472                 ret = del_pending_extents(trans, extent_root);
3473                 BUG_ON(ret);
3474
3475                 cur_start = cache->key.objectid + cache->key.offset;
3476         }
3477         return 0;
3478 }
3479
3480 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
3481                              struct btrfs_root *root,
3482                              u64 bytenr, u64 num_bytes, int alloc,
3483                              int mark_free)
3484 {
3485         return update_block_group(trans, root, bytenr, num_bytes,
3486                                   alloc, mark_free);
3487 }
3488
3489 /*
3490  * Just remove a block group item in extent tree
3491  * Caller should ensure the block group is empty and all space is pinned.
3492  * Or new tree block/data may be allocated into it.
3493  */
3494 static int free_block_group_item(struct btrfs_trans_handle *trans,
3495                                  struct btrfs_fs_info *fs_info,
3496                                  u64 bytenr, u64 len)
3497 {
3498         struct btrfs_path *path;
3499         struct btrfs_key key;
3500         struct btrfs_root *root = fs_info->extent_root;
3501         int ret = 0;
3502
3503         key.objectid = bytenr;
3504         key.offset = len;
3505         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3506
3507         path = btrfs_alloc_path();
3508         if (!path)
3509                 return -ENOMEM;
3510
3511         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3512         if (ret > 0) {
3513                 ret = -ENOENT;
3514                 goto out;
3515         }
3516         if (ret < 0)
3517                 goto out;
3518
3519         ret = btrfs_del_item(trans, root, path);
3520 out:
3521         btrfs_free_path(path);
3522         return ret;
3523 }
3524
3525 static int free_dev_extent_item(struct btrfs_trans_handle *trans,
3526                                 struct btrfs_fs_info *fs_info,
3527                                 u64 devid, u64 dev_offset)
3528 {
3529         struct btrfs_root *root = fs_info->dev_root;
3530         struct btrfs_path *path;
3531         struct btrfs_key key;
3532         int ret;
3533
3534         path = btrfs_alloc_path();
3535         if (!path)
3536                 return -ENOMEM;
3537
3538         key.objectid = devid;
3539         key.type = BTRFS_DEV_EXTENT_KEY;
3540         key.offset = dev_offset;
3541
3542         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3543         if (ret < 0)
3544                 goto out;
3545         if (ret > 0) {
3546                 ret = -ENOENT;
3547                 goto out;
3548         }
3549
3550         ret = btrfs_del_item(trans, root, path);
3551 out:
3552         btrfs_free_path(path);
3553         return ret;
3554 }
3555
3556 static int free_chunk_dev_extent_items(struct btrfs_trans_handle *trans,
3557                                        struct btrfs_fs_info *fs_info,
3558                                        u64 chunk_offset)
3559 {
3560         struct btrfs_chunk *chunk = NULL;
3561         struct btrfs_root *root= fs_info->chunk_root;
3562         struct btrfs_path *path;
3563         struct btrfs_key key;
3564         u16 num_stripes;
3565         int i;
3566         int ret;
3567
3568         path = btrfs_alloc_path();
3569         if (!path)
3570                 return -ENOMEM;
3571
3572         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3573         key.type = BTRFS_CHUNK_ITEM_KEY;
3574         key.offset = chunk_offset;
3575
3576         ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
3577         if (ret < 0)
3578                 goto out;
3579         if (ret > 0) {
3580                 ret = -ENOENT;
3581                 goto out;
3582         }
3583         chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
3584                                struct btrfs_chunk);
3585         num_stripes = btrfs_chunk_num_stripes(path->nodes[0], chunk);
3586         for (i = 0; i < num_stripes; i++) {
3587                 ret = free_dev_extent_item(trans, fs_info,
3588                         btrfs_stripe_devid_nr(path->nodes[0], chunk, i),
3589                         btrfs_stripe_offset_nr(path->nodes[0], chunk, i));
3590                 if (ret < 0)
3591                         goto out;
3592         }
3593 out:
3594         btrfs_free_path(path);
3595         return ret;
3596 }
3597
3598 static int free_system_chunk_item(struct btrfs_super_block *super,
3599                                   struct btrfs_key *key)
3600 {
3601         struct btrfs_disk_key *disk_key;
3602         struct btrfs_key cpu_key;
3603         u32 array_size = btrfs_super_sys_array_size(super);
3604         char *ptr = (char *)super->sys_chunk_array;
3605         int cur = 0;
3606         int ret = -ENOENT;
3607
3608         while (cur < btrfs_super_sys_array_size(super)) {
3609                 struct btrfs_chunk *chunk;
3610                 u32 num_stripes;
3611                 u32 chunk_len;
3612
3613                 disk_key = (struct btrfs_disk_key *)(ptr + cur);
3614                 btrfs_disk_key_to_cpu(&cpu_key, disk_key);
3615                 if (cpu_key.type != BTRFS_CHUNK_ITEM_KEY) {
3616                         /* just in case */
3617                         ret = -EIO;
3618                         goto out;
3619                 }
3620
3621                 chunk = (struct btrfs_chunk *)(ptr + cur + sizeof(*disk_key));
3622                 num_stripes = btrfs_stack_chunk_num_stripes(chunk);
3623                 chunk_len = btrfs_chunk_item_size(num_stripes) +
3624                             sizeof(*disk_key);
3625
3626                 if (key->objectid == cpu_key.objectid &&
3627                     key->offset == cpu_key.offset &&
3628                     key->type == cpu_key.type) {
3629                         memmove(ptr + cur, ptr + cur + chunk_len,
3630                                 array_size - cur - chunk_len);
3631                         array_size -= chunk_len;
3632                         btrfs_set_super_sys_array_size(super, array_size);
3633                         ret = 0;
3634                         goto out;
3635                 }
3636
3637                 cur += chunk_len;
3638         }
3639 out:
3640         return ret;
3641 }
3642
3643 static int free_chunk_item(struct btrfs_trans_handle *trans,
3644                            struct btrfs_fs_info *fs_info,
3645                            u64 bytenr)
3646 {
3647         struct btrfs_path *path;
3648         struct btrfs_key key;
3649         struct btrfs_root *root = fs_info->chunk_root;
3650         struct btrfs_chunk *chunk;
3651         u64 chunk_type;
3652         int ret;
3653
3654         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3655         key.offset = bytenr;
3656         key.type = BTRFS_CHUNK_ITEM_KEY;
3657
3658         path = btrfs_alloc_path();
3659         if (!path)
3660                 return -ENOMEM;
3661
3662         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3663         if (ret > 0) {
3664                 ret = -ENOENT;
3665                 goto out;
3666         }
3667         if (ret < 0)
3668                 goto out;
3669         chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
3670                                struct btrfs_chunk);
3671         chunk_type = btrfs_chunk_type(path->nodes[0], chunk);
3672
3673         ret = btrfs_del_item(trans, root, path);
3674         if (ret < 0)
3675                 goto out;
3676
3677         if (chunk_type & BTRFS_BLOCK_GROUP_SYSTEM)
3678                 ret = free_system_chunk_item(fs_info->super_copy, &key);
3679 out:
3680         btrfs_free_path(path);
3681         return ret;
3682 }
3683
3684 static u64 get_dev_extent_len(struct map_lookup *map)
3685 {
3686         int div;
3687
3688         switch (map->type & BTRFS_BLOCK_GROUP_PROFILE_MASK) {
3689         case 0: /* Single */
3690         case BTRFS_BLOCK_GROUP_DUP:
3691         case BTRFS_BLOCK_GROUP_RAID1:
3692                 div = 1;
3693                 break;
3694         case BTRFS_BLOCK_GROUP_RAID5:
3695                 div = (map->num_stripes - 1);
3696                 break;
3697         case BTRFS_BLOCK_GROUP_RAID6:
3698                 div = (map->num_stripes - 2);
3699                 break;
3700         case BTRFS_BLOCK_GROUP_RAID10:
3701                 div = (map->num_stripes / map->sub_stripes);
3702                 break;
3703         default:
3704                 /* normally, read chunk security hook should handled it */
3705                 BUG_ON(1);
3706         }
3707         return map->ce.size / div;
3708 }
3709
3710 /* free block group/chunk related caches */
3711 static int free_block_group_cache(struct btrfs_trans_handle *trans,
3712                                   struct btrfs_fs_info *fs_info,
3713                                   u64 bytenr, u64 len)
3714 {
3715         struct btrfs_block_group_cache *cache;
3716         struct cache_extent *ce;
3717         struct map_lookup *map;
3718         int ret;
3719         int i;
3720         u64 flags;
3721
3722         /* Free block group cache first */
3723         cache = btrfs_lookup_block_group(fs_info, bytenr);
3724         if (!cache)
3725                 return -ENOENT;
3726         flags = cache->flags;
3727         if (cache->free_space_ctl) {
3728                 btrfs_remove_free_space_cache(cache);
3729                 kfree(cache->free_space_ctl);
3730         }
3731         clear_extent_bits(&fs_info->block_group_cache, bytenr, bytenr + len,
3732                           (unsigned int)-1);
3733         ret = free_space_info(fs_info, flags, len, 0, NULL);
3734         if (ret < 0)
3735                 goto out;
3736         kfree(cache);
3737
3738         /* Then free mapping info and dev usage info */
3739         ce = search_cache_extent(&fs_info->mapping_tree.cache_tree, bytenr);
3740         if (!ce || ce->start != bytenr) {
3741                 ret = -ENOENT;
3742                 goto out;
3743         }
3744         map = container_of(ce, struct map_lookup, ce);
3745         for (i = 0; i < map->num_stripes; i++) {
3746                 struct btrfs_device *device;
3747
3748                 device = map->stripes[i].dev;
3749                 device->bytes_used -= get_dev_extent_len(map);
3750                 ret = btrfs_update_device(trans, device);
3751                 if (ret < 0)
3752                         goto out;
3753         }
3754         remove_cache_extent(&fs_info->mapping_tree.cache_tree, ce);
3755         free(map);
3756 out:
3757         return ret;
3758 }
3759
3760 int btrfs_free_block_group(struct btrfs_trans_handle *trans,
3761                            struct btrfs_fs_info *fs_info, u64 bytenr, u64 len)
3762 {
3763         struct btrfs_root *extent_root = fs_info->extent_root;
3764         struct btrfs_path *path;
3765         struct btrfs_block_group_item *bgi;
3766         struct btrfs_key key;
3767         int ret = 0;
3768
3769         path = btrfs_alloc_path();
3770         if (!path)
3771                 return -ENOMEM;
3772
3773         key.objectid = bytenr;
3774         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3775         key.offset = len;
3776
3777         /* Double check the block group to ensure it's empty */
3778         ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
3779         if (ret > 0) {
3780                 ret = -ENONET;
3781                 goto out;
3782         }
3783         if (ret < 0)
3784                 goto out;
3785
3786         bgi = btrfs_item_ptr(path->nodes[0], path->slots[0],
3787                              struct btrfs_block_group_item);
3788         if (btrfs_disk_block_group_used(path->nodes[0], bgi)) {
3789                 fprintf(stderr,
3790                         "WARNING: block group [%llu,%llu) is not empty\n",
3791                         bytenr, bytenr + len);
3792                 ret = -EINVAL;
3793                 goto out;
3794         }
3795         btrfs_release_path(path);
3796
3797         /*
3798          * Now pin all space in the block group, to prevent further transaction
3799          * allocate space from it.
3800          * Every operation needs a transaction must be in the range.
3801          */
3802         btrfs_pin_extent(fs_info, bytenr, len);
3803
3804         /* delete block group item and chunk item */
3805         ret = free_block_group_item(trans, fs_info, bytenr, len);
3806         if (ret < 0) {
3807                 fprintf(stderr,
3808                         "failed to free block group item for [%llu,%llu)\n",
3809                         bytenr, bytenr + len);
3810                 btrfs_unpin_extent(fs_info, bytenr, len);
3811                 goto out;
3812         }
3813
3814         ret = free_chunk_dev_extent_items(trans, fs_info, bytenr);
3815         if (ret < 0) {
3816                 fprintf(stderr,
3817                         "failed to dev extents belongs to [%llu,%llu)\n",
3818                         bytenr, bytenr + len);
3819                 btrfs_unpin_extent(fs_info, bytenr, len);
3820                 goto out;
3821         }
3822         ret = free_chunk_item(trans, fs_info, bytenr);
3823         if (ret < 0) {
3824                 fprintf(stderr,
3825                         "failed to free chunk for [%llu,%llu)\n",
3826                         bytenr, bytenr + len);
3827                 btrfs_unpin_extent(fs_info, bytenr, len);
3828                 goto out;
3829         }
3830
3831         /* Now release the block_group_cache */
3832         ret = free_block_group_cache(trans, fs_info, bytenr, len);
3833         btrfs_unpin_extent(fs_info, bytenr, len);
3834
3835 out:
3836         btrfs_free_path(path);
3837         return ret;
3838 }
3839
3840 /*
3841  * Fixup block accounting. The initial block accounting created by
3842  * make_block_groups isn't accuracy in this case.
3843  */
3844 int btrfs_fix_block_accounting(struct btrfs_trans_handle *trans,
3845                                struct btrfs_root *root)
3846 {
3847         int ret;
3848         int slot;
3849         u64 start = 0;
3850         u64 bytes_used = 0;
3851         struct btrfs_path path;
3852         struct btrfs_key key;
3853         struct extent_buffer *leaf;
3854         struct btrfs_block_group_cache *cache;
3855         struct btrfs_fs_info *fs_info = root->fs_info;
3856
3857         root = root->fs_info->extent_root;
3858
3859         while(extent_root_pending_ops(fs_info)) {
3860                 ret = finish_current_insert(trans, root);
3861                 if (ret)
3862                         return ret;
3863                 ret = del_pending_extents(trans, root);
3864                 if (ret)
3865                         return ret;
3866         }
3867
3868         while(1) {
3869                 cache = btrfs_lookup_first_block_group(fs_info, start);
3870                 if (!cache)
3871                         break;
3872                 start = cache->key.objectid + cache->key.offset;
3873                 btrfs_set_block_group_used(&cache->item, 0);
3874                 cache->space_info->bytes_used = 0;
3875                 set_extent_bits(&root->fs_info->block_group_cache,
3876                                 cache->key.objectid,
3877                                 cache->key.objectid + cache->key.offset -1,
3878                                 BLOCK_GROUP_DIRTY);
3879         }
3880
3881         btrfs_init_path(&path);
3882         key.offset = 0;
3883         key.objectid = 0;
3884         key.type = BTRFS_EXTENT_ITEM_KEY;
3885         ret = btrfs_search_slot(trans, root->fs_info->extent_root,
3886                                 &key, &path, 0, 0);
3887         if (ret < 0)
3888                 return ret;
3889         while(1) {
3890                 leaf = path.nodes[0];
3891                 slot = path.slots[0];
3892                 if (slot >= btrfs_header_nritems(leaf)) {
3893                         ret = btrfs_next_leaf(root, &path);
3894                         if (ret < 0)
3895                                 return ret;
3896                         if (ret > 0)
3897                                 break;
3898                         leaf = path.nodes[0];
3899                         slot = path.slots[0];
3900                 }
3901                 btrfs_item_key_to_cpu(leaf, &key, slot);
3902                 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
3903                         bytes_used += key.offset;
3904                         ret = btrfs_update_block_group(trans, root,
3905                                   key.objectid, key.offset, 1, 0);
3906                         BUG_ON(ret);
3907                 } else if (key.type == BTRFS_METADATA_ITEM_KEY) {
3908                         bytes_used += fs_info->nodesize;
3909                         ret = btrfs_update_block_group(trans, root,
3910                                   key.objectid, fs_info->nodesize, 1, 0);
3911                         BUG_ON(ret);
3912                 }
3913                 path.slots[0]++;
3914         }
3915         btrfs_set_super_bytes_used(root->fs_info->super_copy, bytes_used);
3916         btrfs_release_path(&path);
3917         return 0;
3918 }
3919
3920 static void __get_extent_size(struct btrfs_root *root, struct btrfs_path *path,
3921                               u64 *start, u64 *len)
3922 {
3923         struct btrfs_key key;
3924
3925         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
3926         BUG_ON(!(key.type == BTRFS_EXTENT_ITEM_KEY ||
3927                  key.type == BTRFS_METADATA_ITEM_KEY));
3928         *start = key.objectid;
3929         if (key.type == BTRFS_EXTENT_ITEM_KEY)
3930                 *len = key.offset;
3931         else
3932                 *len = root->fs_info->nodesize;
3933 }
3934
3935 /*
3936  * Find first overlap extent for range [bytenr, bytenr + len)
3937  * Return 0 for found and point path to it.
3938  * Return >0 for not found.
3939  * Return <0 for err
3940  */
3941 int btrfs_search_overlap_extent(struct btrfs_root *root,
3942                                 struct btrfs_path *path, u64 bytenr, u64 len)
3943 {
3944         struct btrfs_key key;
3945         u64 cur_start;
3946         u64 cur_len;
3947         int ret;
3948
3949         key.objectid = bytenr;
3950         key.type = BTRFS_EXTENT_DATA_KEY;
3951         key.offset = (u64)-1;
3952
3953         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3954         if (ret < 0)
3955                 return ret;
3956         BUG_ON(ret == 0);
3957
3958         ret = btrfs_previous_extent_item(root, path, 0);
3959         if (ret < 0)
3960                 return ret;
3961         /* no previous, check next extent */
3962         if (ret > 0)
3963                 goto next;
3964         __get_extent_size(root, path, &cur_start, &cur_len);
3965         /* Tail overlap */
3966         if (cur_start + cur_len > bytenr)
3967                 return 1;
3968
3969 next:
3970         ret = btrfs_next_extent_item(root, path, bytenr + len);
3971         if (ret < 0)
3972                 return ret;
3973         /* No next, prev already checked, no overlap */
3974         if (ret > 0)
3975                 return 0;
3976         __get_extent_size(root, path, &cur_start, &cur_len);
3977         /* head overlap*/
3978         if (cur_start < bytenr + len)
3979                 return 1;
3980         return 0;
3981 }
3982
3983 static int __btrfs_record_file_extent(struct btrfs_trans_handle *trans,
3984                                       struct btrfs_root *root, u64 objectid,
3985                                       struct btrfs_inode_item *inode,
3986                                       u64 file_pos, u64 disk_bytenr,
3987                                       u64 *ret_num_bytes)
3988 {
3989         int ret;
3990         struct btrfs_fs_info *info = root->fs_info;
3991         struct btrfs_root *extent_root = info->extent_root;
3992         struct extent_buffer *leaf;
3993         struct btrfs_file_extent_item *fi;
3994         struct btrfs_key ins_key;
3995         struct btrfs_path *path;
3996         struct btrfs_extent_item *ei;
3997         u64 nbytes;
3998         u64 extent_num_bytes;
3999         u64 extent_bytenr;
4000         u64 extent_offset;
4001         u64 num_bytes = *ret_num_bytes;
4002
4003         /*
4004          * All supported file system should not use its 0 extent.
4005          * As it's for hole
4006          *
4007          * And hole extent has no size limit, no need to loop.
4008          */
4009         if (disk_bytenr == 0) {
4010                 ret = btrfs_insert_file_extent(trans, root, objectid,
4011                                                 file_pos, disk_bytenr,
4012                                                 num_bytes, num_bytes);
4013                 return ret;
4014         }
4015         num_bytes = min_t(u64, num_bytes, BTRFS_MAX_EXTENT_SIZE);
4016
4017         path = btrfs_alloc_path();
4018         if (!path)
4019                 return -ENOMEM;
4020
4021         /* First to check extent overlap */
4022         ret = btrfs_search_overlap_extent(extent_root, path, disk_bytenr,
4023                                           num_bytes);
4024         if (ret < 0)
4025                 goto fail;
4026         if (ret > 0) {
4027                 /* Found overlap */
4028                 u64 cur_start;
4029                 u64 cur_len;
4030
4031                 __get_extent_size(extent_root, path, &cur_start, &cur_len);
4032                 /*
4033                  * For convert case, this extent should be a subset of
4034                  * existing one.
4035                  */
4036                 BUG_ON(disk_bytenr < cur_start);
4037
4038                 extent_bytenr = cur_start;
4039                 extent_num_bytes = cur_len;
4040                 extent_offset = disk_bytenr - extent_bytenr;
4041         } else {
4042                 /* No overlap, create new extent */
4043                 btrfs_release_path(path);
4044                 ins_key.objectid = disk_bytenr;
4045                 ins_key.offset = num_bytes;
4046                 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
4047
4048                 ret = btrfs_insert_empty_item(trans, extent_root, path,
4049                                               &ins_key, sizeof(*ei));
4050                 if (ret == 0) {
4051                         leaf = path->nodes[0];
4052                         ei = btrfs_item_ptr(leaf, path->slots[0],
4053                                             struct btrfs_extent_item);
4054
4055                         btrfs_set_extent_refs(leaf, ei, 0);
4056                         btrfs_set_extent_generation(leaf, ei, 0);
4057                         btrfs_set_extent_flags(leaf, ei,
4058                                                BTRFS_EXTENT_FLAG_DATA);
4059                         btrfs_mark_buffer_dirty(leaf);
4060
4061                         ret = btrfs_update_block_group(trans, root, disk_bytenr,
4062                                                        num_bytes, 1, 0);
4063                         if (ret)
4064                                 goto fail;
4065                 } else if (ret != -EEXIST) {
4066                         goto fail;
4067                 }
4068                 btrfs_extent_post_op(trans, extent_root);
4069                 extent_bytenr = disk_bytenr;
4070                 extent_num_bytes = num_bytes;
4071                 extent_offset = 0;
4072         }
4073         btrfs_release_path(path);
4074         ins_key.objectid = objectid;
4075         ins_key.offset = file_pos;
4076         ins_key.type = BTRFS_EXTENT_DATA_KEY;
4077         ret = btrfs_insert_empty_item(trans, root, path, &ins_key,
4078                                       sizeof(*fi));
4079         if (ret)
4080                 goto fail;
4081         leaf = path->nodes[0];
4082         fi = btrfs_item_ptr(leaf, path->slots[0],
4083                             struct btrfs_file_extent_item);
4084         btrfs_set_file_extent_generation(leaf, fi, trans->transid);
4085         btrfs_set_file_extent_type(leaf, fi, BTRFS_FILE_EXTENT_REG);
4086         btrfs_set_file_extent_disk_bytenr(leaf, fi, extent_bytenr);
4087         btrfs_set_file_extent_disk_num_bytes(leaf, fi, extent_num_bytes);
4088         btrfs_set_file_extent_offset(leaf, fi, extent_offset);
4089         btrfs_set_file_extent_num_bytes(leaf, fi, num_bytes);
4090         btrfs_set_file_extent_ram_bytes(leaf, fi, extent_num_bytes);
4091         btrfs_set_file_extent_compression(leaf, fi, 0);
4092         btrfs_set_file_extent_encryption(leaf, fi, 0);
4093         btrfs_set_file_extent_other_encoding(leaf, fi, 0);
4094         btrfs_mark_buffer_dirty(leaf);
4095
4096         nbytes = btrfs_stack_inode_nbytes(inode) + num_bytes;
4097         btrfs_set_stack_inode_nbytes(inode, nbytes);
4098         btrfs_release_path(path);
4099
4100         ret = btrfs_inc_extent_ref(trans, root, extent_bytenr, extent_num_bytes,
4101                                    0, root->root_key.objectid, objectid,
4102                                    file_pos - extent_offset);
4103         if (ret)
4104                 goto fail;
4105         ret = 0;
4106         *ret_num_bytes = min(extent_num_bytes - extent_offset, num_bytes);
4107 fail:
4108         btrfs_free_path(path);
4109         return ret;
4110 }
4111
4112 /*
4113  * Record a file extent. Do all the required works, such as inserting
4114  * file extent item, inserting extent item and backref item into extent
4115  * tree and updating block accounting.
4116  */
4117 int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
4118                               struct btrfs_root *root, u64 objectid,
4119                               struct btrfs_inode_item *inode,
4120                               u64 file_pos, u64 disk_bytenr,
4121                               u64 num_bytes)
4122 {
4123         u64 cur_disk_bytenr = disk_bytenr;
4124         u64 cur_file_pos = file_pos;
4125         u64 cur_num_bytes = num_bytes;
4126         int ret = 0;
4127
4128         while (num_bytes > 0) {
4129                 ret = __btrfs_record_file_extent(trans, root, objectid,
4130                                                  inode, cur_file_pos,
4131                                                  cur_disk_bytenr,
4132                                                  &cur_num_bytes);
4133                 if (ret < 0)
4134                         break;
4135                 cur_disk_bytenr += cur_num_bytes;
4136                 cur_file_pos += cur_num_bytes;
4137                 num_bytes -= cur_num_bytes;
4138         }
4139         return ret;
4140 }
4141
4142
4143 static int add_excluded_extent(struct btrfs_root *root,
4144                                u64 start, u64 num_bytes)
4145 {
4146         u64 end = start + num_bytes - 1;
4147         set_extent_bits(&root->fs_info->pinned_extents,
4148                         start, end, EXTENT_UPTODATE);
4149         return 0;
4150 }
4151
4152 void free_excluded_extents(struct btrfs_root *root,
4153                            struct btrfs_block_group_cache *cache)
4154 {
4155         u64 start, end;
4156
4157         start = cache->key.objectid;
4158         end = start + cache->key.offset - 1;
4159
4160         clear_extent_bits(&root->fs_info->pinned_extents,
4161                           start, end, EXTENT_UPTODATE);
4162 }
4163
4164 int exclude_super_stripes(struct btrfs_root *root,
4165                           struct btrfs_block_group_cache *cache)
4166 {
4167         u64 bytenr;
4168         u64 *logical;
4169         int stripe_len;
4170         int i, nr, ret;
4171
4172         if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
4173                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
4174                 cache->bytes_super += stripe_len;
4175                 ret = add_excluded_extent(root, cache->key.objectid,
4176                                           stripe_len);
4177                 if (ret)
4178                         return ret;
4179         }
4180
4181         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
4182                 bytenr = btrfs_sb_offset(i);
4183                 ret = btrfs_rmap_block(root->fs_info,
4184                                        cache->key.objectid, bytenr,
4185                                        0, &logical, &nr, &stripe_len);
4186                 if (ret)
4187                         return ret;
4188
4189                 while (nr--) {
4190                         u64 start, len;
4191
4192                         if (logical[nr] > cache->key.objectid +
4193                             cache->key.offset)
4194                                 continue;
4195
4196                         if (logical[nr] + stripe_len <= cache->key.objectid)
4197                                 continue;
4198
4199                         start = logical[nr];
4200                         if (start < cache->key.objectid) {
4201                                 start = cache->key.objectid;
4202                                 len = (logical[nr] + stripe_len) - start;
4203                         } else {
4204                                 len = min_t(u64, stripe_len,
4205                                             cache->key.objectid +
4206                                             cache->key.offset - start);
4207                         }
4208
4209                         cache->bytes_super += len;
4210                         ret = add_excluded_extent(root, start, len);
4211                         if (ret) {
4212                                 kfree(logical);
4213                                 return ret;
4214                         }
4215                 }
4216
4217                 kfree(logical);
4218         }
4219         return 0;
4220 }
4221
4222 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
4223                        struct btrfs_fs_info *info, u64 start, u64 end)
4224 {
4225         u64 extent_start, extent_end, size, total_added = 0;
4226         int ret;
4227
4228         while (start < end) {
4229                 ret = find_first_extent_bit(&info->pinned_extents, start,
4230                                             &extent_start, &extent_end,
4231                                             EXTENT_DIRTY | EXTENT_UPTODATE);
4232                 if (ret)
4233                         break;
4234
4235                 if (extent_start <= start) {
4236                         start = extent_end + 1;
4237                 } else if (extent_start > start && extent_start < end) {
4238                         size = extent_start - start;
4239                         total_added += size;
4240                         ret = btrfs_add_free_space(block_group->free_space_ctl,
4241                                                    start, size);
4242                         BUG_ON(ret); /* -ENOMEM or logic error */
4243                         start = extent_end + 1;
4244                 } else {
4245                         break;
4246                 }
4247         }
4248
4249         if (start < end) {
4250                 size = end - start;
4251                 total_added += size;
4252                 ret = btrfs_add_free_space(block_group->free_space_ctl, start,
4253                                            size);
4254                 BUG_ON(ret); /* -ENOMEM or logic error */
4255         }
4256
4257         return total_added;
4258 }