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 extent_io_tree *free_space_cache;
  73
  74         free_space_cache = &root->fs_info->free_space_cache;
  75         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
  76                 bytenr = btrfs_sb_offset(i);
  77                 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
  78                                        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, GFP_NOFS);
  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                                                  GFP_NOFS);
 154                         }
 155                         if (key.type == BTRFS_METADATA_ITEM_KEY)
 156                                 last = key.objectid + root->nodesize;
 157                         else
 158                                 last = key.objectid + key.offset;
 159                 }
 160 next:
 161                 path->slots[0]++;
 162         }
 163
 164         if (block_group->key.objectid +
 165             block_group->key.offset > last) {
 166                 hole_size = block_group->key.objectid +
 167                         block_group->key.offset - last;
 168                 set_extent_dirty(free_space_cache, last,
 169                                  last + hole_size - 1, GFP_NOFS);
 170         }
 171         remove_sb_from_cache(root, block_group);
 172         block_group->cached = 1;
 173 err:
 174         btrfs_free_path(path);
 175         return 0;
 176 }
 177
 178 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
 179                                                        btrfs_fs_info *info,
 180                                                        u64 bytenr)
 181 {
 182         struct extent_io_tree *block_group_cache;
 183         struct btrfs_block_group_cache *block_group = NULL;
 184         u64 ptr;
 185         u64 start;
 186         u64 end;
 187         int ret;
 188
 189         bytenr = max_t(u64, bytenr,
 190                        BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 191         block_group_cache = &info->block_group_cache;
 192         ret = find_first_extent_bit(block_group_cache,
 193                                     bytenr, &start, &end,
 194                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 195                                     BLOCK_GROUP_SYSTEM);
 196         if (ret) {
 197                 return NULL;
 198         }
 199         ret = get_state_private(block_group_cache, start, &ptr);
 200         if (ret)
 201                 return NULL;
 202
 203         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 204         return block_group;
 205 }
 206
 207 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 208                                                          btrfs_fs_info *info,
 209                                                          u64 bytenr)
 210 {
 211         struct extent_io_tree *block_group_cache;
 212         struct btrfs_block_group_cache *block_group = NULL;
 213         u64 ptr;
 214         u64 start;
 215         u64 end;
 216         int ret;
 217
 218         block_group_cache = &info->block_group_cache;
 219         ret = find_first_extent_bit(block_group_cache,
 220                                     bytenr, &start, &end,
 221                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 222                                     BLOCK_GROUP_SYSTEM);
 223         if (ret) {
 224                 return NULL;
 225         }
 226         ret = get_state_private(block_group_cache, start, &ptr);
 227         if (ret)
 228                 return NULL;
 229
 230         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 231         if (block_group->key.objectid <= bytenr && bytenr <
 232             block_group->key.objectid + block_group->key.offset)
 233                 return block_group;
 234         return NULL;
 235 }
 236
 237 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 238 {
 239         return (cache->flags & bits) == bits;
 240 }
 241
 242 static int noinline find_search_start(struct btrfs_root *root,
 243                               struct btrfs_block_group_cache **cache_ret,
 244                               u64 *start_ret, int num, int data)
 245 {
 246         int ret;
 247         struct btrfs_block_group_cache *cache = *cache_ret;
 248         u64 last = *start_ret;
 249         u64 start = 0;
 250         u64 end = 0;
 251         u64 search_start = *start_ret;
 252         int wrapped = 0;
 253
 254         if (!cache)
 255                 goto out;
 256 again:
 257         ret = cache_block_group(root, cache);
 258         if (ret)
 259                 goto out;
 260
 261         last = max(search_start, cache->key.objectid);
 262         if (cache->ro || !block_group_bits(cache, data))
 263                 goto new_group;
 264
 265         while(1) {
 266                 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
 267                                             last, &start, &end, EXTENT_DIRTY);
 268                 if (ret) {
 269                         goto new_group;
 270                 }
 271
 272                 start = max(last, start);
 273                 last = end + 1;
 274                 if (last - start < num) {
 275                         continue;
 276                 }
 277                 if (start + num > cache->key.objectid + cache->key.offset) {
 278                         goto new_group;
 279                 }
 280                 *start_ret = start;
 281                 return 0;
 282         }
 283 out:
 284         *start_ret = last;
 285         cache = btrfs_lookup_block_group(root->fs_info, search_start);
 286         if (!cache) {
 287                 printk("Unable to find block group for %llu\n",
 288                         (unsigned long long)search_start);
 289                 WARN_ON(1);
 290         }
 291         return -ENOSPC;
 292
 293 new_group:
 294         last = cache->key.objectid + cache->key.offset;
 295 wrapped:
 296         cache = btrfs_lookup_first_block_group(root->fs_info, last);
 297         if (!cache) {
 298                 if (!wrapped) {
 299                         wrapped = 1;
 300                         last = search_start;
 301                         goto wrapped;
 302                 }
 303                 goto out;
 304         }
 305         *cache_ret = cache;
 306         goto again;
 307 }
 308
 309 static int block_group_state_bits(u64 flags)
 310 {
 311         int bits = 0;
 312         if (flags & BTRFS_BLOCK_GROUP_DATA)
 313                 bits |= BLOCK_GROUP_DATA;
 314         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 315                 bits |= BLOCK_GROUP_METADATA;
 316         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 317                 bits |= BLOCK_GROUP_SYSTEM;
 318         return bits;
 319 }
 320
 321 static struct btrfs_block_group_cache *
 322 btrfs_find_block_group(struct btrfs_root *root, struct btrfs_block_group_cache
 323                        *hint, u64 search_start, int data, int owner)
 324 {
 325         struct btrfs_block_group_cache *cache;
 326         struct extent_io_tree *block_group_cache;
 327         struct btrfs_block_group_cache *found_group = NULL;
 328         struct btrfs_fs_info *info = root->fs_info;
 329         u64 used;
 330         u64 last = 0;
 331         u64 hint_last;
 332         u64 start;
 333         u64 end;
 334         u64 free_check;
 335         u64 ptr;
 336         int bit;
 337         int ret;
 338         int full_search = 0;
 339         int factor = 10;
 340
 341         block_group_cache = &info->block_group_cache;
 342
 343         if (!owner)
 344                 factor = 10;
 345
 346         bit = block_group_state_bits(data);
 347
 348         if (search_start) {
 349                 struct btrfs_block_group_cache *shint;
 350                 shint = btrfs_lookup_block_group(info, search_start);
 351                 if (shint && !shint->ro && block_group_bits(shint, data)) {
 352                         used = btrfs_block_group_used(&shint->item);
 353                         if (used + shint->pinned <
 354                             div_factor(shint->key.offset, factor)) {
 355                                 return shint;
 356                         }
 357                 }
 358         }
 359         if (hint && !hint->ro && block_group_bits(hint, data)) {
 360                 used = btrfs_block_group_used(&hint->item);
 361                 if (used + hint->pinned <
 362                     div_factor(hint->key.offset, factor)) {
 363                         return hint;
 364                 }
 365                 last = hint->key.objectid + hint->key.offset;
 366                 hint_last = last;
 367         } else {
 368                 if (hint)
 369                         hint_last = max(hint->key.objectid, search_start);
 370                 else
 371                         hint_last = search_start;
 372
 373                 last = hint_last;
 374         }
 375 again:
 376         while(1) {
 377                 ret = find_first_extent_bit(block_group_cache, last,
 378                                             &start, &end, bit);
 379                 if (ret)
 380                         break;
 381
 382                 ret = get_state_private(block_group_cache, start, &ptr);
 383                 if (ret)
 384                         break;
 385
 386                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 387                 last = cache->key.objectid + cache->key.offset;
 388                 used = btrfs_block_group_used(&cache->item);
 389
 390                 if (!cache->ro && block_group_bits(cache, data)) {
 391                         if (full_search)
 392                                 free_check = cache->key.offset;
 393                         else
 394                                 free_check = div_factor(cache->key.offset,
 395                                                         factor);
 396
 397                         if (used + cache->pinned < free_check) {
 398                                 found_group = cache;
 399                                 goto found;
 400                         }
 401                 }
 402                 cond_resched();
 403         }
 404         if (!full_search) {
 405                 last = search_start;
 406                 full_search = 1;
 407                 goto again;
 408         }
 409 found:
 410         return found_group;
 411 }
 412
 413 /*
 414  * Back reference rules.  Back refs have three main goals:
 415  *
 416  * 1) differentiate between all holders of references to an extent so that
 417  *    when a reference is dropped we can make sure it was a valid reference
 418  *    before freeing the extent.
 419  *
 420  * 2) Provide enough information to quickly find the holders of an extent
 421  *    if we notice a given block is corrupted or bad.
 422  *
 423  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 424  *    maintenance.  This is actually the same as #2, but with a slightly
 425  *    different use case.
 426  *
 427  * There are two kinds of back refs. The implicit back refs is optimized
 428  * for pointers in non-shared tree blocks. For a given pointer in a block,
 429  * back refs of this kind provide information about the block's owner tree
 430  * and the pointer's key. These information allow us to find the block by
 431  * b-tree searching. The full back refs is for pointers in tree blocks not
 432  * referenced by their owner trees. The location of tree block is recorded
 433  * in the back refs. Actually the full back refs is generic, and can be
 434  * used in all cases the implicit back refs is used. The major shortcoming
 435  * of the full back refs is its overhead. Every time a tree block gets
 436  * COWed, we have to update back refs entry for all pointers in it.
 437  *
 438  * For a newly allocated tree block, we use implicit back refs for
 439  * pointers in it. This means most tree related operations only involve
 440  * implicit back refs. For a tree block created in old transaction, the
 441  * only way to drop a reference to it is COW it. So we can detect the
 442  * event that tree block loses its owner tree's reference and do the
 443  * back refs conversion.
 444  *
 445  * When a tree block is COW'd through a tree, there are four cases:
 446  *
 447  * The reference count of the block is one and the tree is the block's
 448  * owner tree. Nothing to do in this case.
 449  *
 450  * The reference count of the block is one and the tree is not the
 451  * block's owner tree. In this case, full back refs is used for pointers
 452  * in the block. Remove these full back refs, add implicit back refs for
 453  * every pointers in the new block.
 454  *
 455  * The reference count of the block is greater than one and the tree is
 456  * the block's owner tree. In this case, implicit back refs is used for
 457  * pointers in the block. Add full back refs for every pointers in the
 458  * block, increase lower level extents' reference counts. The original
 459  * implicit back refs are entailed to the new block.
 460  *
 461  * The reference count of the block is greater than one and the tree is
 462  * not the block's owner tree. Add implicit back refs for every pointer in
 463  * the new block, increase lower level extents' reference count.
 464  *
 465  * Back Reference Key composing:
 466  *
 467  * The key objectid corresponds to the first byte in the extent,
 468  * The key type is used to differentiate between types of back refs.
 469  * There are different meanings of the key offset for different types
 470  * of back refs.
 471  *
 472  * File extents can be referenced by:
 473  *
 474  * - multiple snapshots, subvolumes, or different generations in one subvol
 475  * - different files inside a single subvolume
 476  * - different offsets inside a file (bookend extents in file.c)
 477  *
 478  * The extent ref structure for the implicit back refs has fields for:
 479  *
 480  * - Objectid of the subvolume root
 481  * - objectid of the file holding the reference
 482  * - original offset in the file
 483  * - how many bookend extents
 484  *
 485  * The key offset for the implicit back refs is hash of the first
 486  * three fields.
 487  *
 488  * The extent ref structure for the full back refs has field for:
 489  *
 490  * - number of pointers in the tree leaf
 491  *
 492  * The key offset for the implicit back refs is the first byte of
 493  * the tree leaf
 494  *
 495  * When a file extent is allocated, The implicit back refs is used.
 496  * the fields are filled in:
 497  *
 498  *     (root_key.objectid, inode objectid, offset in file, 1)
 499  *
 500  * When a file extent is removed file truncation, we find the
 501  * corresponding implicit back refs and check the following fields:
 502  *
 503  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 504  *
 505  * Btree extents can be referenced by:
 506  *
 507  * - Different subvolumes
 508  *
 509  * Both the implicit back refs and the full back refs for tree blocks
 510  * only consist of key. The key offset for the implicit back refs is
 511  * objectid of block's owner tree. The key offset for the full back refs
 512  * is the first byte of parent block.
 513  *
 514  * When implicit back refs is used, information about the lowest key and
 515  * level of the tree block are required. These information are stored in
 516  * tree block info structure.
 517  */
 518
 519 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 520 static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 521                                   struct btrfs_root *root,
 522                                   struct btrfs_path *path,
 523                                   u64 owner, u32 extra_size)
 524 {
 525         struct btrfs_extent_item *item;
 526         struct btrfs_extent_item_v0 *ei0;
 527         struct btrfs_extent_ref_v0 *ref0;
 528         struct btrfs_tree_block_info *bi;
 529         struct extent_buffer *leaf;
 530         struct btrfs_key key;
 531         struct btrfs_key found_key;
 532         u32 new_size = sizeof(*item);
 533         u64 refs;
 534         int ret;
 535
 536         leaf = path->nodes[0];
 537         BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
 538
 539         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 540         ei0 = btrfs_item_ptr(leaf, path->slots[0],
 541                              struct btrfs_extent_item_v0);
 542         refs = btrfs_extent_refs_v0(leaf, ei0);
 543
 544         if (owner == (u64)-1) {
 545                 while (1) {
 546                         if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 547                                 ret = btrfs_next_leaf(root, path);
 548                                 if (ret < 0)
 549                                         return ret;
 550                                 BUG_ON(ret > 0);
 551                                 leaf = path->nodes[0];
 552                         }
 553                         btrfs_item_key_to_cpu(leaf, &found_key,
 554                                               path->slots[0]);
 555                         BUG_ON(key.objectid != found_key.objectid);
 556                         if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
 557                                 path->slots[0]++;
 558                                 continue;
 559                         }
 560                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 561                                               struct btrfs_extent_ref_v0);
 562                         owner = btrfs_ref_objectid_v0(leaf, ref0);
 563                         break;
 564                 }
 565         }
 566         btrfs_release_path(path);
 567
 568         if (owner < BTRFS_FIRST_FREE_OBJECTID)
 569                 new_size += sizeof(*bi);
 570
 571         new_size -= sizeof(*ei0);
 572         ret = btrfs_search_slot(trans, root, &key, path, new_size, 1);
 573         if (ret < 0)
 574                 return ret;
 575         BUG_ON(ret);
 576
 577         ret = btrfs_extend_item(trans, root, path, new_size);
 578         BUG_ON(ret);
 579
 580         leaf = path->nodes[0];
 581         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 582         btrfs_set_extent_refs(leaf, item, refs);
 583         /* FIXME: get real generation */
 584         btrfs_set_extent_generation(leaf, item, 0);
 585         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 586                 btrfs_set_extent_flags(leaf, item,
 587                                        BTRFS_EXTENT_FLAG_TREE_BLOCK |
 588                                        BTRFS_BLOCK_FLAG_FULL_BACKREF);
 589                 bi = (struct btrfs_tree_block_info *)(item + 1);
 590                 /* FIXME: get first key of the block */
 591                 memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
 592                 btrfs_set_tree_block_level(leaf, bi, (int)owner);
 593         } else {
 594                 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
 595         }
 596         btrfs_mark_buffer_dirty(leaf);
 597         return 0;
 598 }
 599 #endif
 600
 601 u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 602 {
 603         u32 high_crc = ~(u32)0;
 604         u32 low_crc = ~(u32)0;
 605         __le64 lenum;
 606
 607         lenum = cpu_to_le64(root_objectid);
 608         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 609         lenum = cpu_to_le64(owner);
 610         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 611         lenum = cpu_to_le64(offset);
 612         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 613
 614         return ((u64)high_crc << 31) ^ (u64)low_crc;
 615 }
 616
 617 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
 618                                      struct btrfs_extent_data_ref *ref)
 619 {
 620         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
 621                                     btrfs_extent_data_ref_objectid(leaf, ref),
 622                                     btrfs_extent_data_ref_offset(leaf, ref));
 623 }
 624
 625 static int match_extent_data_ref(struct extent_buffer *leaf,
 626                                  struct btrfs_extent_data_ref *ref,
 627                                  u64 root_objectid, u64 owner, u64 offset)
 628 {
 629         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
 630             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
 631             btrfs_extent_data_ref_offset(leaf, ref) != offset)
 632                 return 0;
 633         return 1;
 634 }
 635
 636 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
 637                                            struct btrfs_root *root,
 638                                            struct btrfs_path *path,
 639                                            u64 bytenr, u64 parent,
 640                                            u64 root_objectid,
 641                                            u64 owner, u64 offset)
 642 {
 643         struct btrfs_key key;
 644         struct btrfs_extent_data_ref *ref;
 645         struct extent_buffer *leaf;
 646         u32 nritems;
 647         int ret;
 648         int recow;
 649         int err = -ENOENT;
 650
 651         key.objectid = bytenr;
 652         if (parent) {
 653                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 654                 key.offset = parent;
 655         } else {
 656                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 657                 key.offset = hash_extent_data_ref(root_objectid,
 658                                                   owner, offset);
 659         }
 660 again:
 661         recow = 0;
 662         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 663         if (ret < 0) {
 664                 err = ret;
 665                 goto fail;
 666         }
 667
 668         if (parent) {
 669                 if (!ret)
 670                         return 0;
 671 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 672                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 673                 btrfs_release_path(path);
 674                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 675                 if (ret < 0) {
 676                         err = ret;
 677                         goto fail;
 678                 }
 679                 if (!ret)
 680                         return 0;
 681 #endif
 682                 goto fail;
 683         }
 684
 685         leaf = path->nodes[0];
 686         nritems = btrfs_header_nritems(leaf);
 687         while (1) {
 688                 if (path->slots[0] >= nritems) {
 689                         ret = btrfs_next_leaf(root, path);
 690                         if (ret < 0)
 691                                 err = ret;
 692                         if (ret)
 693                                 goto fail;
 694
 695                         leaf = path->nodes[0];
 696                         nritems = btrfs_header_nritems(leaf);
 697                         recow = 1;
 698                 }
 699
 700                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 701                 if (key.objectid != bytenr ||
 702                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
 703                         goto fail;
 704
 705                 ref = btrfs_item_ptr(leaf, path->slots[0],
 706                                      struct btrfs_extent_data_ref);
 707
 708                 if (match_extent_data_ref(leaf, ref, root_objectid,
 709                                           owner, offset)) {
 710                         if (recow) {
 711                                 btrfs_release_path(path);
 712                                 goto again;
 713                         }
 714                         err = 0;
 715                         break;
 716                 }
 717                 path->slots[0]++;
 718         }
 719 fail:
 720         return err;
 721 }
 722
 723 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
 724                                            struct btrfs_root *root,
 725                                            struct btrfs_path *path,
 726                                            u64 bytenr, u64 parent,
 727                                            u64 root_objectid, u64 owner,
 728                                            u64 offset, int refs_to_add)
 729 {
 730         struct btrfs_key key;
 731         struct extent_buffer *leaf;
 732         u32 size;
 733         u32 num_refs;
 734         int ret;
 735
 736         key.objectid = bytenr;
 737         if (parent) {
 738                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 739                 key.offset = parent;
 740                 size = sizeof(struct btrfs_shared_data_ref);
 741         } else {
 742                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 743                 key.offset = hash_extent_data_ref(root_objectid,
 744                                                   owner, offset);
 745                 size = sizeof(struct btrfs_extent_data_ref);
 746         }
 747
 748         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 749         if (ret && ret != -EEXIST)
 750                 goto fail;
 751
 752         leaf = path->nodes[0];
 753         if (parent) {
 754                 struct btrfs_shared_data_ref *ref;
 755                 ref = btrfs_item_ptr(leaf, path->slots[0],
 756                                      struct btrfs_shared_data_ref);
 757                 if (ret == 0) {
 758                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
 759                 } else {
 760                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
 761                         num_refs += refs_to_add;
 762                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
 763                 }
 764         } else {
 765                 struct btrfs_extent_data_ref *ref;
 766                 while (ret == -EEXIST) {
 767                         ref = btrfs_item_ptr(leaf, path->slots[0],
 768                                              struct btrfs_extent_data_ref);
 769                         if (match_extent_data_ref(leaf, ref, root_objectid,
 770                                                   owner, offset))
 771                                 break;
 772                         btrfs_release_path(path);
 773
 774                         key.offset++;
 775                         ret = btrfs_insert_empty_item(trans, root, path, &key,
 776                                                       size);
 777                         if (ret && ret != -EEXIST)
 778                                 goto fail;
 779
 780                         leaf = path->nodes[0];
 781                 }
 782                 ref = btrfs_item_ptr(leaf, path->slots[0],
 783                                      struct btrfs_extent_data_ref);
 784                 if (ret == 0) {
 785                         btrfs_set_extent_data_ref_root(leaf, ref,
 786                                                        root_objectid);
 787                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
 788                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
 789                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
 790                 } else {
 791                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
 792                         num_refs += refs_to_add;
 793                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
 794                 }
 795         }
 796         btrfs_mark_buffer_dirty(leaf);
 797         ret = 0;
 798 fail:
 799         btrfs_release_path(path);
 800         return ret;
 801 }
 802
 803 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
 804                                            struct btrfs_root *root,
 805                                            struct btrfs_path *path,
 806                                            int refs_to_drop)
 807 {
 808         struct btrfs_key key;
 809         struct btrfs_extent_data_ref *ref1 = NULL;
 810         struct btrfs_shared_data_ref *ref2 = NULL;
 811         struct extent_buffer *leaf;
 812         u32 num_refs = 0;
 813         int ret = 0;
 814
 815         leaf = path->nodes[0];
 816         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 817
 818         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 819                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 820                                       struct btrfs_extent_data_ref);
 821                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 822         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 823                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 824                                       struct btrfs_shared_data_ref);
 825                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 826 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 827         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 828                 struct btrfs_extent_ref_v0 *ref0;
 829                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 830                                       struct btrfs_extent_ref_v0);
 831                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 832 #endif
 833         } else {
 834                 BUG();
 835         }
 836
 837         BUG_ON(num_refs < refs_to_drop);
 838         num_refs -= refs_to_drop;
 839
 840         if (num_refs == 0) {
 841                 ret = btrfs_del_item(trans, root, path);
 842         } else {
 843                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
 844                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
 845                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
 846                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 847 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 848                 else {
 849                         struct btrfs_extent_ref_v0 *ref0;
 850                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 851                                         struct btrfs_extent_ref_v0);
 852                         btrfs_set_ref_count_v0(leaf, ref0, num_refs);
 853                 }
 854 #endif
 855                 btrfs_mark_buffer_dirty(leaf);
 856         }
 857         return ret;
 858 }
 859
 860 static noinline u32 extent_data_ref_count(struct btrfs_root *root,
 861                                           struct btrfs_path *path,
 862                                           struct btrfs_extent_inline_ref *iref)
 863 {
 864         struct btrfs_key key;
 865         struct extent_buffer *leaf;
 866         struct btrfs_extent_data_ref *ref1;
 867         struct btrfs_shared_data_ref *ref2;
 868         u32 num_refs = 0;
 869
 870         leaf = path->nodes[0];
 871         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 872         if (iref) {
 873                 if (btrfs_extent_inline_ref_type(leaf, iref) ==
 874                     BTRFS_EXTENT_DATA_REF_KEY) {
 875                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
 876                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 877                 } else {
 878                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
 879                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 880                 }
 881         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 882                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 883                                       struct btrfs_extent_data_ref);
 884                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 885         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 886                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 887                                       struct btrfs_shared_data_ref);
 888                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 889 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 890         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 891                 struct btrfs_extent_ref_v0 *ref0;
 892                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 893                                       struct btrfs_extent_ref_v0);
 894                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 895 #endif
 896         } else {
 897                 BUG();
 898         }
 899         return num_refs;
 900 }
 901
 902 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
 903                                           struct btrfs_root *root,
 904                                           struct btrfs_path *path,
 905                                           u64 bytenr, u64 parent,
 906                                           u64 root_objectid)
 907 {
 908         struct btrfs_key key;
 909         int ret;
 910
 911         key.objectid = bytenr;
 912         if (parent) {
 913                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 914                 key.offset = parent;
 915         } else {
 916                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 917                 key.offset = root_objectid;
 918         }
 919
 920         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 921         if (ret > 0)
 922                 ret = -ENOENT;
 923 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 924         if (ret == -ENOENT && parent) {
 925                 btrfs_release_path(path);
 926                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 927                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 928                 if (ret > 0)
 929                         ret = -ENOENT;
 930         }
 931 #endif
 932         return ret;
 933 }
 934
 935 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
 936                                           struct btrfs_root *root,
 937                                           struct btrfs_path *path,
 938                                           u64 bytenr, u64 parent,
 939                                           u64 root_objectid)
 940 {
 941         struct btrfs_key key;
 942         int ret;
 943
 944         key.objectid = bytenr;
 945         if (parent) {
 946                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 947                 key.offset = parent;
 948         } else {
 949                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 950                 key.offset = root_objectid;
 951         }
 952
 953         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 954
 955         btrfs_release_path(path);
 956         return ret;
 957 }
 958
 959 static inline int extent_ref_type(u64 parent, u64 owner)
 960 {
 961         int type;
 962         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 963                 if (parent > 0)
 964                         type = BTRFS_SHARED_BLOCK_REF_KEY;
 965                 else
 966                         type = BTRFS_TREE_BLOCK_REF_KEY;
 967         } else {
 968                 if (parent > 0)
 969                         type = BTRFS_SHARED_DATA_REF_KEY;
 970                 else
 971                         type = BTRFS_EXTENT_DATA_REF_KEY;
 972         }
 973         return type;
 974 }
 975
 976 static int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
 977                                  struct btrfs_root *root,
 978                                  struct btrfs_path *path,
 979                                  struct btrfs_extent_inline_ref **ref_ret,
 980                                  u64 bytenr, u64 num_bytes,
 981                                  u64 parent, u64 root_objectid,
 982                                  u64 owner, u64 offset, int insert)
 983 {
 984         struct btrfs_key key;
 985         struct extent_buffer *leaf;
 986         struct btrfs_extent_item *ei;
 987         struct btrfs_extent_inline_ref *iref;
 988         u64 flags;
 989         u32 item_size;
 990         unsigned long ptr;
 991         unsigned long end;
 992         int extra_size;
 993         int type;
 994         int want;
 995         int ret;
 996         int err = 0;
 997         int skinny_metadata =
 998                 btrfs_fs_incompat(root->fs_info, SKINNY_METADATA);
 999
1000         key.objectid = bytenr;
1001         key.type = BTRFS_EXTENT_ITEM_KEY;
1002         key.offset = num_bytes;
1003
1004         want = extent_ref_type(parent, owner);
1005         if (insert)
1006                 extra_size = btrfs_extent_inline_ref_size(want);
1007         else
1008                 extra_size = -1;
1009
1010         if (owner < BTRFS_FIRST_FREE_OBJECTID && skinny_metadata) {
1011                 skinny_metadata = 1;
1012                 key.type = BTRFS_METADATA_ITEM_KEY;
1013                 key.offset = owner;
1014         } else if (skinny_metadata) {
1015                 skinny_metadata = 0;
1016         }
1017
1018 again:
1019         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1020         if (ret < 0) {
1021                 err = ret;
1022                 goto out;
1023         }
1024
1025         /*
1026          * We may be a newly converted file system which still has the old fat
1027          * extent entries for metadata, so try and see if we have one of those.
1028          */
1029         if (ret > 0 && skinny_metadata) {
1030                 skinny_metadata = 0;
1031                 if (path->slots[0]) {
1032                         path->slots[0]--;
1033                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1034                                               path->slots[0]);
1035                         if (key.objectid == bytenr &&
1036                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1037                             key.offset == num_bytes)
1038                                 ret = 0;
1039                 }
1040                 if (ret) {
1041                         key.type = BTRFS_EXTENT_ITEM_KEY;
1042                         key.offset = num_bytes;
1043                         btrfs_release_path(path);
1044                         goto again;
1045                 }
1046         }
1047
1048         if (ret) {
1049                 printf("Failed to find [%llu, %u, %llu]\n", key.objectid, key.type, key.offset);
1050                 return -ENOENT;
1051         }
1052
1053         BUG_ON(ret);
1054
1055         leaf = path->nodes[0];
1056         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1057 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1058         if (item_size < sizeof(*ei)) {
1059                 if (!insert) {
1060                         err = -ENOENT;
1061                         goto out;
1062                 }
1063                 ret = convert_extent_item_v0(trans, root, path, owner,
1064                                              extra_size);
1065                 if (ret < 0) {
1066                         err = ret;
1067                         goto out;
1068                 }
1069                 leaf = path->nodes[0];
1070                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1071         }
1072 #endif
1073         if (item_size < sizeof(*ei)) {
1074                 printf("Size is %u, needs to be %u, slot %d\n",
1075                        (unsigned)item_size,
1076                        (unsigned)sizeof(*ei), path->slots[0]);
1077                 btrfs_print_leaf(root, leaf);
1078                 return -EINVAL;
1079         }
1080         BUG_ON(item_size < sizeof(*ei));
1081
1082         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1083         flags = btrfs_extent_flags(leaf, ei);
1084
1085         ptr = (unsigned long)(ei + 1);
1086         end = (unsigned long)ei + item_size;
1087
1088         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
1089                 ptr += sizeof(struct btrfs_tree_block_info);
1090                 BUG_ON(ptr > end);
1091         } else if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
1092                 if (!(flags & BTRFS_EXTENT_FLAG_DATA)) {
1093                         return -EIO;
1094                 }
1095         }
1096
1097         err = -ENOENT;
1098         while (1) {
1099                 if (ptr >= end) {
1100                         WARN_ON(ptr > end);
1101                         break;
1102                 }
1103                 iref = (struct btrfs_extent_inline_ref *)ptr;
1104                 type = btrfs_extent_inline_ref_type(leaf, iref);
1105                 if (want < type)
1106                         break;
1107                 if (want > type) {
1108                         ptr += btrfs_extent_inline_ref_size(type);
1109                         continue;
1110                 }
1111
1112                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1113                         struct btrfs_extent_data_ref *dref;
1114                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1115                         if (match_extent_data_ref(leaf, dref, root_objectid,
1116                                                   owner, offset)) {
1117                                 err = 0;
1118                                 break;
1119                         }
1120                         if (hash_extent_data_ref_item(leaf, dref) <
1121                             hash_extent_data_ref(root_objectid, owner, offset))
1122                                 break;
1123                 } else {
1124                         u64 ref_offset;
1125                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1126                         if (parent > 0) {
1127                                 if (parent == ref_offset) {
1128                                         err = 0;
1129                                         break;
1130                                 }
1131                                 if (ref_offset < parent)
1132                                         break;
1133                         } else {
1134                                 if (root_objectid == ref_offset) {
1135                                         err = 0;
1136                                         break;
1137                                 }
1138                                 if (ref_offset < root_objectid)
1139                                         break;
1140                         }
1141                 }
1142                 ptr += btrfs_extent_inline_ref_size(type);
1143         }
1144         if (err == -ENOENT && insert) {
1145                 if (item_size + extra_size >=
1146                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1147                         err = -EAGAIN;
1148                         goto out;
1149                 }
1150                 /*
1151                  * To add new inline back ref, we have to make sure
1152                  * there is no corresponding back ref item.
1153                  * For simplicity, we just do not add new inline back
1154                  * ref if there is any back ref item.
1155                  */
1156                 if (find_next_key(path, &key) == 0 && key.objectid == bytenr &&
1157                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1158                         err = -EAGAIN;
1159                         goto out;
1160                 }
1161         }
1162         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1163 out:
1164         return err;
1165 }
1166
1167 static int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1168                                 struct btrfs_root *root,
1169                                 struct btrfs_path *path,
1170                                 struct btrfs_extent_inline_ref *iref,
1171                                 u64 parent, u64 root_objectid,
1172                                 u64 owner, u64 offset, int refs_to_add)
1173 {
1174         struct extent_buffer *leaf;
1175         struct btrfs_extent_item *ei;
1176         unsigned long ptr;
1177         unsigned long end;
1178         unsigned long item_offset;
1179         u64 refs;
1180         int size;
1181         int type;
1182         int ret;
1183
1184         leaf = path->nodes[0];
1185         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1186         item_offset = (unsigned long)iref - (unsigned long)ei;
1187
1188         type = extent_ref_type(parent, owner);
1189         size = btrfs_extent_inline_ref_size(type);
1190
1191         ret = btrfs_extend_item(trans, root, path, size);
1192         BUG_ON(ret);
1193
1194         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1195         refs = btrfs_extent_refs(leaf, ei);
1196         refs += refs_to_add;
1197         btrfs_set_extent_refs(leaf, ei, refs);
1198
1199         ptr = (unsigned long)ei + item_offset;
1200         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1201         if (ptr < end - size)
1202                 memmove_extent_buffer(leaf, ptr + size, ptr,
1203                                       end - size - ptr);
1204
1205         iref = (struct btrfs_extent_inline_ref *)ptr;
1206         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1207         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1208                 struct btrfs_extent_data_ref *dref;
1209                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1210                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1211                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1212                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1213                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1214         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1215                 struct btrfs_shared_data_ref *sref;
1216                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1217                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1218                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1219         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1220                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1221         } else {
1222                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1223         }
1224         btrfs_mark_buffer_dirty(leaf);
1225         return 0;
1226 }
1227
1228 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1229                                  struct btrfs_root *root,
1230                                  struct btrfs_path *path,
1231                                  struct btrfs_extent_inline_ref **ref_ret,
1232                                  u64 bytenr, u64 num_bytes, u64 parent,
1233                                  u64 root_objectid, u64 owner, u64 offset)
1234 {
1235         int ret;
1236
1237         ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1238                                            bytenr, num_bytes, parent,
1239                                            root_objectid, owner, offset, 0);
1240         if (ret != -ENOENT)
1241                 return ret;
1242
1243         btrfs_release_path(path);
1244         *ref_ret = NULL;
1245
1246         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1247                 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1248                                             root_objectid);
1249         } else {
1250                 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1251                                              root_objectid, owner, offset);
1252         }
1253         return ret;
1254 }
1255
1256 static int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1257                                  struct btrfs_root *root,
1258                                  struct btrfs_path *path,
1259                                  struct btrfs_extent_inline_ref *iref,
1260                                  int refs_to_mod)
1261 {
1262         struct extent_buffer *leaf;
1263         struct btrfs_extent_item *ei;
1264         struct btrfs_extent_data_ref *dref = NULL;
1265         struct btrfs_shared_data_ref *sref = NULL;
1266         unsigned long ptr;
1267         unsigned long end;
1268         u32 item_size;
1269         int size;
1270         int type;
1271         int ret;
1272         u64 refs;
1273
1274         leaf = path->nodes[0];
1275         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1276         refs = btrfs_extent_refs(leaf, ei);
1277         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1278         refs += refs_to_mod;
1279         btrfs_set_extent_refs(leaf, ei, refs);
1280
1281         type = btrfs_extent_inline_ref_type(leaf, iref);
1282
1283         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1284                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1285                 refs = btrfs_extent_data_ref_count(leaf, dref);
1286         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1287                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1288                 refs = btrfs_shared_data_ref_count(leaf, sref);
1289         } else {
1290                 refs = 1;
1291                 BUG_ON(refs_to_mod != -1);
1292         }
1293
1294         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1295         refs += refs_to_mod;
1296
1297         if (refs > 0) {
1298                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1299                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1300                 else
1301                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1302         } else {
1303                 size =  btrfs_extent_inline_ref_size(type);
1304                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1305                 ptr = (unsigned long)iref;
1306                 end = (unsigned long)ei + item_size;
1307                 if (ptr + size < end)
1308                         memmove_extent_buffer(leaf, ptr, ptr + size,
1309                                               end - ptr - size);
1310                 item_size -= size;
1311                 ret = btrfs_truncate_item(trans, root, path, item_size, 1);
1312                 BUG_ON(ret);
1313         }
1314         btrfs_mark_buffer_dirty(leaf);
1315         return 0;
1316 }
1317
1318 static int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1319                                  struct btrfs_root *root,
1320                                  struct btrfs_path *path,
1321                                  u64 bytenr, u64 num_bytes, u64 parent,
1322                                  u64 root_objectid, u64 owner,
1323                                  u64 offset, int refs_to_add)
1324 {
1325         struct btrfs_extent_inline_ref *iref;
1326         int ret;
1327
1328         ret = lookup_inline_extent_backref(trans, root, path, &iref,
1329                                            bytenr, num_bytes, parent,
1330                                            root_objectid, owner, offset, 1);
1331         if (ret == 0) {
1332                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1333                 ret = update_inline_extent_backref(trans, root, path, iref,
1334                                                    refs_to_add);
1335         } else if (ret == -ENOENT) {
1336                 ret = setup_inline_extent_backref(trans, root, path, iref,
1337                                                   parent, root_objectid,
1338                                                   owner, offset, refs_to_add);
1339         }
1340         return ret;
1341 }
1342
1343 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1344                                  struct btrfs_root *root,
1345                                  struct btrfs_path *path,
1346                                  u64 bytenr, u64 parent, u64 root_objectid,
1347                                  u64 owner, u64 offset, int refs_to_add)
1348 {
1349         int ret;
1350
1351         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
1352                 ret = insert_extent_data_ref(trans, root, path, bytenr,
1353                                              parent, root_objectid,
1354                                              owner, offset, refs_to_add);
1355         } else {
1356                 BUG_ON(refs_to_add != 1);
1357                 ret = insert_tree_block_ref(trans, root, path, bytenr,
1358                                             parent, root_objectid);
1359         }
1360         return ret;
1361 }
1362
1363 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1364                                  struct btrfs_root *root,
1365                                  struct btrfs_path *path,
1366                                  struct btrfs_extent_inline_ref *iref,
1367                                  int refs_to_drop, int is_data)
1368 {
1369         int ret;
1370
1371         BUG_ON(!is_data && refs_to_drop != 1);
1372         if (iref) {
1373                 ret = update_inline_extent_backref(trans, root, path, iref,
1374                                                    -refs_to_drop);
1375         } else if (is_data) {
1376                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1377         } else {
1378                 ret = btrfs_del_item(trans, root, path);
1379         }
1380         return ret;
1381 }
1382
1383 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1384                          struct btrfs_root *root,
1385                          u64 bytenr, u64 num_bytes, u64 parent,
1386                          u64 root_objectid, u64 owner, u64 offset)
1387 {
1388         struct btrfs_path *path;
1389         struct extent_buffer *leaf;
1390         struct btrfs_extent_item *item;
1391         u64 refs;
1392         int ret;
1393         int err = 0;
1394
1395         path = btrfs_alloc_path();
1396         if (!path)
1397                 return -ENOMEM;
1398
1399         path->reada = 1;
1400
1401         ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1402                                            path, bytenr, num_bytes, parent,
1403                                            root_objectid, owner, offset, 1);
1404         if (ret == 0)
1405                 goto out;
1406
1407         if (ret != -EAGAIN) {
1408                 err = ret;
1409                 goto out;
1410         }
1411
1412         leaf = path->nodes[0];
1413         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1414         refs = btrfs_extent_refs(leaf, item);
1415         btrfs_set_extent_refs(leaf, item, refs + 1);
1416
1417         btrfs_mark_buffer_dirty(leaf);
1418         btrfs_release_path(path);
1419
1420         path->reada = 1;
1421
1422         /* now insert the actual backref */
1423         ret = insert_extent_backref(trans, root->fs_info->extent_root,
1424                                     path, bytenr, parent, root_objectid,
1425                                     owner, offset, 1);
1426         if (ret)
1427                 err = ret;
1428 out:
1429         btrfs_free_path(path);
1430         finish_current_insert(trans, root->fs_info->extent_root);
1431         del_pending_extents(trans, root->fs_info->extent_root);
1432         BUG_ON(err);
1433         return err;
1434 }
1435
1436 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
1437                          struct btrfs_root *root)
1438 {
1439         finish_current_insert(trans, root->fs_info->extent_root);
1440         del_pending_extents(trans, root->fs_info->extent_root);
1441         return 0;
1442 }
1443
1444 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
1445                              struct btrfs_root *root, u64 bytenr,
1446                              u64 offset, int metadata, u64 *refs, u64 *flags)
1447 {
1448         struct btrfs_path *path;
1449         int ret;
1450         struct btrfs_key key;
1451         struct extent_buffer *l;
1452         struct btrfs_extent_item *item;
1453         u32 item_size;
1454         u64 num_refs;
1455         u64 extent_flags;
1456
1457         if (metadata &&
1458             !btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) {
1459                 offset = root->nodesize;
1460                 metadata = 0;
1461         }
1462
1463         path = btrfs_alloc_path();
1464         if (!path)
1465                 return -ENOMEM;
1466         path->reada = 1;
1467
1468         key.objectid = bytenr;
1469         key.offset = offset;
1470         if (metadata)
1471                 key.type = BTRFS_METADATA_ITEM_KEY;
1472         else
1473                 key.type = BTRFS_EXTENT_ITEM_KEY;
1474
1475 again:
1476         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1477                                 0, 0);
1478         if (ret < 0)
1479                 goto out;
1480
1481         /*
1482          * Deal with the fact that we may have mixed SKINNY and normal refs.  If
1483          * we didn't find what we wanted check and see if we have a normal ref
1484          * right next to us, or re-search if we are on the edge of the leaf just
1485          * to make sure.
1486          */
1487         if (ret > 0 && metadata) {
1488                 if (path->slots[0]) {
1489                         path->slots[0]--;
1490                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1491                                               path->slots[0]);
1492                         if (key.objectid == bytenr &&
1493                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1494                             key.offset == root->nodesize)
1495                                 ret = 0;
1496                 }
1497
1498                 if (ret) {
1499                         btrfs_release_path(path);
1500                         key.type = BTRFS_EXTENT_ITEM_KEY;
1501                         key.offset = root->nodesize;
1502                         metadata = 0;
1503                         goto again;
1504                 }
1505         }
1506
1507         if (ret != 0) {
1508                 ret = -EIO;
1509                 goto out;
1510         }
1511
1512         l = path->nodes[0];
1513         item_size = btrfs_item_size_nr(l, path->slots[0]);
1514         if (item_size >= sizeof(*item)) {
1515                 item = btrfs_item_ptr(l, path->slots[0],
1516                                       struct btrfs_extent_item);
1517                 num_refs = btrfs_extent_refs(l, item);
1518                 extent_flags = btrfs_extent_flags(l, item);
1519         } else {
1520 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1521                         struct btrfs_extent_item_v0 *ei0;
1522                         BUG_ON(item_size != sizeof(*ei0));
1523                         ei0 = btrfs_item_ptr(l, path->slots[0],
1524                                              struct btrfs_extent_item_v0);
1525                         num_refs = btrfs_extent_refs_v0(l, ei0);
1526                         /* FIXME: this isn't correct for data */
1527                         extent_flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
1528 #else
1529                         BUG();
1530 #endif
1531         }
1532         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1533         if (refs)
1534                 *refs = num_refs;
1535         if (flags)
1536                 *flags = extent_flags;
1537 out:
1538         btrfs_free_path(path);
1539         return ret;
1540 }
1541
1542 int btrfs_set_block_flags(struct btrfs_trans_handle *trans,
1543                           struct btrfs_root *root,
1544                           u64 bytenr, int level, u64 flags)
1545 {
1546         struct btrfs_path *path;
1547         int ret;
1548         struct btrfs_key key;
1549         struct extent_buffer *l;
1550         struct btrfs_extent_item *item;
1551         u32 item_size;
1552         int skinny_metadata =
1553                 btrfs_fs_incompat(root->fs_info, SKINNY_METADATA);
1554
1555         path = btrfs_alloc_path();
1556         if (!path)
1557                 return -ENOMEM;
1558         path->reada = 1;
1559
1560         key.objectid = bytenr;
1561         if (skinny_metadata) {
1562                 key.offset = level;
1563                 key.type = BTRFS_METADATA_ITEM_KEY;
1564         } else {
1565                 key.offset = root->nodesize;
1566                 key.type = BTRFS_EXTENT_ITEM_KEY;
1567         }
1568
1569 again:
1570         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1571                                 0, 0);
1572         if (ret < 0)
1573                 goto out;
1574
1575         if (ret > 0 && skinny_metadata) {
1576                 skinny_metadata = 0;
1577                 if (path->slots[0]) {
1578                         path->slots[0]--;
1579                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1580                                               path->slots[0]);
1581                         if (key.objectid == bytenr &&
1582                             key.offset == root->nodesize &&
1583                             key.type == BTRFS_EXTENT_ITEM_KEY)
1584                                 ret = 0;
1585                 }
1586                 if (ret) {
1587                         btrfs_release_path(path);
1588                         key.offset = root->nodesize;
1589                         key.type = BTRFS_EXTENT_ITEM_KEY;
1590                         goto again;
1591                 }
1592         }
1593
1594         if (ret != 0) {
1595                 btrfs_print_leaf(root, path->nodes[0]);
1596                 printk("failed to find block number %Lu\n",
1597                         (unsigned long long)bytenr);
1598                 BUG();
1599         }
1600         l = path->nodes[0];
1601         item_size = btrfs_item_size_nr(l, path->slots[0]);
1602 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1603         if (item_size < sizeof(*item)) {
1604                 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1605                                              path, (u64)-1, 0);
1606                 if (ret < 0)
1607                         goto out;
1608
1609                 l = path->nodes[0];
1610                 item_size = btrfs_item_size_nr(l, path->slots[0]);
1611         }
1612 #endif
1613         BUG_ON(item_size < sizeof(*item));
1614         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1615         flags |= btrfs_extent_flags(l, item);
1616         btrfs_set_extent_flags(l, item, flags);
1617 out:
1618         btrfs_free_path(path);
1619         finish_current_insert(trans, root->fs_info->extent_root);
1620         del_pending_extents(trans, root->fs_info->extent_root);
1621         return ret;
1622 }
1623
1624 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
1625                            struct btrfs_root *root,
1626                            struct extent_buffer *buf,
1627                            int record_parent, int inc)
1628 {
1629         u64 bytenr;
1630         u64 num_bytes;
1631         u64 parent;
1632         u64 ref_root;
1633         u32 nritems;
1634         struct btrfs_key key;
1635         struct btrfs_file_extent_item *fi;
1636         int i;
1637         int level;
1638         int ret = 0;
1639         int (*process_func)(struct btrfs_trans_handle *trans,
1640                             struct btrfs_root *root,
1641                             u64, u64, u64, u64, u64, u64);
1642
1643         ref_root = btrfs_header_owner(buf);
1644         nritems = btrfs_header_nritems(buf);
1645         level = btrfs_header_level(buf);
1646
1647         if (!root->ref_cows && level == 0)
1648                 return 0;
1649
1650         if (inc)
1651                 process_func = btrfs_inc_extent_ref;
1652         else
1653                 process_func = btrfs_free_extent;
1654
1655         if (record_parent)
1656                 parent = buf->start;
1657         else
1658                 parent = 0;
1659
1660         for (i = 0; i < nritems; i++) {
1661                 cond_resched();
1662                 if (level == 0) {
1663                         btrfs_item_key_to_cpu(buf, &key, i);
1664                         if (key.type != BTRFS_EXTENT_DATA_KEY)
1665                                 continue;
1666                         fi = btrfs_item_ptr(buf, i,
1667                                             struct btrfs_file_extent_item);
1668                         if (btrfs_file_extent_type(buf, fi) ==
1669                             BTRFS_FILE_EXTENT_INLINE)
1670                                 continue;
1671                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1672                         if (bytenr == 0)
1673                                 continue;
1674
1675                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
1676                         key.offset -= btrfs_file_extent_offset(buf, fi);
1677                         ret = process_func(trans, root, bytenr, num_bytes,
1678                                            parent, ref_root, key.objectid,
1679                                            key.offset);
1680                         if (ret) {
1681                                 WARN_ON(1);
1682                                 goto fail;
1683                         }
1684                 } else {
1685                         bytenr = btrfs_node_blockptr(buf, i);
1686                         num_bytes = root->nodesize;
1687                         ret = process_func(trans, root, bytenr, num_bytes,
1688                                            parent, ref_root, level - 1, 0);
1689                         if (ret) {
1690                                 WARN_ON(1);
1691                                 goto fail;
1692                         }
1693                 }
1694         }
1695         return 0;
1696 fail:
1697         WARN_ON(1);
1698         return ret;
1699 }
1700
1701 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1702                   struct extent_buffer *buf, int record_parent)
1703 {
1704         return __btrfs_mod_ref(trans, root, buf, record_parent, 1);
1705 }
1706
1707 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1708                   struct extent_buffer *buf, int record_parent)
1709 {
1710         return __btrfs_mod_ref(trans, root, buf, record_parent, 0);
1711 }
1712
1713 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1714                                  struct btrfs_root *root,
1715                                  struct btrfs_path *path,
1716                                  struct btrfs_block_group_cache *cache)
1717 {
1718         int ret;
1719         int pending_ret;
1720         struct btrfs_root *extent_root = root->fs_info->extent_root;
1721         unsigned long bi;
1722         struct extent_buffer *leaf;
1723
1724         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1725         if (ret < 0)
1726                 goto fail;
1727         BUG_ON(ret);
1728
1729         leaf = path->nodes[0];
1730         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1731         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1732         btrfs_mark_buffer_dirty(leaf);
1733         btrfs_release_path(path);
1734 fail:
1735         finish_current_insert(trans, extent_root);
1736         pending_ret = del_pending_extents(trans, extent_root);
1737         if (ret)
1738                 return ret;
1739         if (pending_ret)
1740                 return pending_ret;
1741         return 0;
1742
1743 }
1744
1745 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1746                                    struct btrfs_root *root)
1747 {
1748         struct extent_io_tree *block_group_cache;
1749         struct btrfs_block_group_cache *cache;
1750         int ret;
1751         struct btrfs_path *path;
1752         u64 last = 0;
1753         u64 start;
1754         u64 end;
1755         u64 ptr;
1756
1757         block_group_cache = &root->fs_info->block_group_cache;
1758         path = btrfs_alloc_path();
1759         if (!path)
1760                 return -ENOMEM;
1761
1762         while(1) {
1763                 ret = find_first_extent_bit(block_group_cache, last,
1764                                             &start, &end, BLOCK_GROUP_DIRTY);
1765                 if (ret) {
1766                         if (last == 0)
1767                                 break;
1768                         last = 0;
1769                         continue;
1770                 }
1771
1772                 last = end + 1;
1773                 ret = get_state_private(block_group_cache, start, &ptr);
1774                 BUG_ON(ret);
1775
1776                 clear_extent_bits(block_group_cache, start, end,
1777                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
1778
1779                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1780                 ret = write_one_cache_group(trans, root, path, cache);
1781         }
1782         btrfs_free_path(path);
1783         return 0;
1784 }
1785
1786 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1787                                                   u64 flags)
1788 {
1789         struct btrfs_space_info *found;
1790
1791         flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
1792
1793         list_for_each_entry(found, &info->space_info, list) {
1794                 if (found->flags & flags)
1795                         return found;
1796         }
1797         return NULL;
1798
1799 }
1800
1801 static int free_space_info(struct btrfs_fs_info *fs_info, u64 flags,
1802                           u64 total_bytes, u64 bytes_used,
1803                           struct btrfs_space_info **space_info)
1804 {
1805         struct btrfs_space_info *found;
1806
1807         /* only support free block group which is empty */
1808         if (bytes_used)
1809                 return -ENOTEMPTY;
1810
1811         found = __find_space_info(fs_info, flags);
1812         if (!found)
1813                 return -ENOENT;
1814         if (found->total_bytes < total_bytes) {
1815                 fprintf(stderr,
1816                         "WARNING: bad space info to free %llu only have %llu\n",
1817                         total_bytes, found->total_bytes);
1818                 return -EINVAL;
1819         }
1820         found->total_bytes -= total_bytes;
1821         if (space_info)
1822                 *space_info = found;
1823         return 0;
1824 }
1825
1826 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1827                              u64 total_bytes, u64 bytes_used,
1828                              struct btrfs_space_info **space_info)
1829 {
1830         struct btrfs_space_info *found;
1831
1832         found = __find_space_info(info, flags);
1833         if (found) {
1834                 found->total_bytes += total_bytes;
1835                 found->bytes_used += bytes_used;
1836                 if (found->total_bytes < found->bytes_used) {
1837                         fprintf(stderr, "warning, bad space info total_bytes "
1838                                 "%llu used %llu\n",
1839                                (unsigned long long)found->total_bytes,
1840                                (unsigned long long)found->bytes_used);
1841                 }
1842                 *space_info = found;
1843                 return 0;
1844         }
1845         found = kmalloc(sizeof(*found), GFP_NOFS);
1846         if (!found)
1847                 return -ENOMEM;
1848
1849         list_add(&found->list, &info->space_info);
1850         found->flags = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
1851         found->total_bytes = total_bytes;
1852         found->bytes_used = bytes_used;
1853         found->bytes_pinned = 0;
1854         found->full = 0;
1855         *space_info = found;
1856         return 0;
1857 }
1858
1859
1860 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1861 {
1862         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1863                                    BTRFS_BLOCK_GROUP_RAID1 |
1864                                    BTRFS_BLOCK_GROUP_RAID10 |
1865                                    BTRFS_BLOCK_GROUP_RAID5 |
1866                                    BTRFS_BLOCK_GROUP_RAID6 |
1867                                    BTRFS_BLOCK_GROUP_DUP);
1868         if (extra_flags) {
1869                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1870                         fs_info->avail_data_alloc_bits |= extra_flags;
1871                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1872                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1873                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1874                         fs_info->avail_system_alloc_bits |= extra_flags;
1875         }
1876 }
1877
1878 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1879                           struct btrfs_root *extent_root, u64 alloc_bytes,
1880                           u64 flags)
1881 {
1882         struct btrfs_space_info *space_info;
1883         u64 thresh;
1884         u64 start;
1885         u64 num_bytes;
1886         int ret;
1887
1888         space_info = __find_space_info(extent_root->fs_info, flags);
1889         if (!space_info) {
1890                 ret = update_space_info(extent_root->fs_info, flags,
1891                                         0, 0, &space_info);
1892                 BUG_ON(ret);
1893         }
1894         BUG_ON(!space_info);
1895
1896         if (space_info->full)
1897                 return 0;
1898
1899         thresh = div_factor(space_info->total_bytes, 7);
1900         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1901             thresh)
1902                 return 0;
1903
1904         /*
1905          * Avoid allocating given chunk type
1906          */
1907         if (extent_root->fs_info->avoid_meta_chunk_alloc &&
1908             (flags & BTRFS_BLOCK_GROUP_METADATA))
1909                 return 0;
1910         if (extent_root->fs_info->avoid_sys_chunk_alloc &&
1911             (flags & BTRFS_BLOCK_GROUP_SYSTEM))
1912                 return 0;
1913
1914         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes,
1915                                 space_info->flags);
1916         if (ret == -ENOSPC) {
1917                 space_info->full = 1;
1918                 return 0;
1919         }
1920
1921         BUG_ON(ret);
1922
1923         ret = btrfs_make_block_group(trans, extent_root, 0, space_info->flags,
1924                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1925         BUG_ON(ret);
1926         return 0;
1927 }
1928
1929 static int update_block_group(struct btrfs_trans_handle *trans,
1930                               struct btrfs_root *root,
1931                               u64 bytenr, u64 num_bytes, int alloc,
1932                               int mark_free)
1933 {
1934         struct btrfs_block_group_cache *cache;
1935         struct btrfs_fs_info *info = root->fs_info;
1936         u64 total = num_bytes;
1937         u64 old_val;
1938         u64 byte_in_group;
1939         u64 start;
1940         u64 end;
1941
1942         /* block accounting for super block */
1943         old_val = btrfs_super_bytes_used(info->super_copy);
1944         if (alloc)
1945                 old_val += num_bytes;
1946         else
1947                 old_val -= num_bytes;
1948         btrfs_set_super_bytes_used(info->super_copy, old_val);
1949
1950         /* block accounting for root item */
1951         old_val = btrfs_root_used(&root->root_item);
1952         if (alloc)
1953                 old_val += num_bytes;
1954         else
1955                 old_val -= num_bytes;
1956         btrfs_set_root_used(&root->root_item, old_val);
1957
1958         while(total) {
1959                 cache = btrfs_lookup_block_group(info, bytenr);
1960                 if (!cache) {
1961                         return -1;
1962                 }
1963                 byte_in_group = bytenr - cache->key.objectid;
1964                 WARN_ON(byte_in_group > cache->key.offset);
1965                 start = cache->key.objectid;
1966                 end = start + cache->key.offset - 1;
1967                 set_extent_bits(&info->block_group_cache, start, end,
1968                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1969
1970                 old_val = btrfs_block_group_used(&cache->item);
1971                 num_bytes = min(total, cache->key.offset - byte_in_group);
1972
1973                 if (alloc) {
1974                         old_val += num_bytes;
1975                         cache->space_info->bytes_used += num_bytes;
1976                 } else {
1977                         old_val -= num_bytes;
1978                         cache->space_info->bytes_used -= num_bytes;
1979                         if (mark_free) {
1980                                 set_extent_dirty(&info->free_space_cache,
1981                                                  bytenr, bytenr + num_bytes - 1,
1982                                                  GFP_NOFS);
1983                         }
1984                 }
1985                 btrfs_set_block_group_used(&cache->item, old_val);
1986                 total -= num_bytes;
1987                 bytenr += num_bytes;
1988         }
1989         return 0;
1990 }
1991
1992 static int update_pinned_extents(struct btrfs_root *root,
1993                                 u64 bytenr, u64 num, int pin)
1994 {
1995         u64 len;
1996         struct btrfs_block_group_cache *cache;
1997         struct btrfs_fs_info *fs_info = root->fs_info;
1998
1999         if (pin) {
2000                 set_extent_dirty(&fs_info->pinned_extents,
2001                                 bytenr, bytenr + num - 1, GFP_NOFS);
2002         } else {
2003                 clear_extent_dirty(&fs_info->pinned_extents,
2004                                 bytenr, bytenr + num - 1, GFP_NOFS);
2005         }
2006         while (num > 0) {
2007                 cache = btrfs_lookup_block_group(fs_info, bytenr);
2008                 if (!cache) {
2009                         len = min((u64)root->sectorsize, num);
2010                         goto next;
2011                 }
2012                 WARN_ON(!cache);
2013                 len = min(num, cache->key.offset -
2014                           (bytenr - cache->key.objectid));
2015                 if (pin) {
2016                         cache->pinned += len;
2017                         cache->space_info->bytes_pinned += len;
2018                         fs_info->total_pinned += len;
2019                 } else {
2020                         cache->pinned -= len;
2021                         cache->space_info->bytes_pinned -= len;
2022                         fs_info->total_pinned -= len;
2023                 }
2024 next:
2025                 bytenr += len;
2026                 num -= len;
2027         }
2028         return 0;
2029 }
2030
2031 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
2032                                struct btrfs_root *root,
2033                                struct extent_io_tree *unpin)
2034 {
2035         u64 start;
2036         u64 end;
2037         int ret;
2038         struct extent_io_tree *free_space_cache;
2039         free_space_cache = &root->fs_info->free_space_cache;
2040
2041         while(1) {
2042                 ret = find_first_extent_bit(unpin, 0, &start, &end,
2043                                             EXTENT_DIRTY);
2044                 if (ret)
2045                         break;
2046                 update_pinned_extents(root, start, end + 1 - start, 0);
2047                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
2048                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
2049         }
2050         return 0;
2051 }
2052
2053 static int extent_root_pending_ops(struct btrfs_fs_info *info)
2054 {
2055         u64 start;
2056         u64 end;
2057         int ret;
2058
2059         ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2060                                     &end, EXTENT_LOCKED);
2061         if (!ret) {
2062                 ret = find_first_extent_bit(&info->pending_del, 0, &start, &end,
2063                                             EXTENT_LOCKED);
2064         }
2065         return ret == 0;
2066
2067 }
2068 static int finish_current_insert(struct btrfs_trans_handle *trans,
2069                                  struct btrfs_root *extent_root)
2070 {
2071         u64 start;
2072         u64 end;
2073         u64 priv;
2074         struct btrfs_fs_info *info = extent_root->fs_info;
2075         struct pending_extent_op *extent_op;
2076         struct btrfs_key key;
2077         int ret;
2078         int skinny_metadata =
2079                 btrfs_fs_incompat(extent_root->fs_info, SKINNY_METADATA);
2080
2081         while(1) {
2082                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2083                                             &end, EXTENT_LOCKED);
2084                 if (ret)
2085                         break;
2086
2087                 ret = get_state_private(&info->extent_ins, start, &priv);
2088                 BUG_ON(ret);
2089                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2090
2091                 if (extent_op->type == PENDING_EXTENT_INSERT) {
2092                         key.objectid = start;
2093                         if (skinny_metadata) {
2094                                 key.offset = extent_op->level;
2095                                 key.type = BTRFS_METADATA_ITEM_KEY;
2096                         } else {
2097                                 key.offset = extent_op->num_bytes;
2098                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2099                         }
2100                         ret = alloc_reserved_tree_block(trans, extent_root,
2101                                                 extent_root->root_key.objectid,
2102                                                 trans->transid,
2103                                                 extent_op->flags,
2104                                                 &extent_op->key,
2105                                                 extent_op->level, &key);
2106                         BUG_ON(ret);
2107                 } else {
2108                         BUG_ON(1);
2109                 }
2110
2111                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
2112                                   GFP_NOFS);
2113                 kfree(extent_op);
2114         }
2115         return 0;
2116 }
2117
2118 static int pin_down_bytes(struct btrfs_trans_handle *trans,
2119                           struct btrfs_root *root,
2120                           u64 bytenr, u64 num_bytes, int is_data)
2121 {
2122         int err = 0;
2123         struct extent_buffer *buf;
2124
2125         if (is_data)
2126                 goto pinit;
2127
2128         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
2129         if (!buf)
2130                 goto pinit;
2131
2132         /* we can reuse a block if it hasn't been written
2133          * and it is from this transaction.  We can't
2134          * reuse anything from the tree log root because
2135          * it has tiny sub-transactions.
2136          */
2137         if (btrfs_buffer_uptodate(buf, 0)) {
2138                 u64 header_owner = btrfs_header_owner(buf);
2139                 u64 header_transid = btrfs_header_generation(buf);
2140                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
2141                     header_transid == trans->transid &&
2142                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
2143                         clean_tree_block(NULL, root, buf);
2144                         free_extent_buffer(buf);
2145                         return 1;
2146                 }
2147         }
2148         free_extent_buffer(buf);
2149 pinit:
2150         update_pinned_extents(root, bytenr, num_bytes, 1);
2151
2152         BUG_ON(err < 0);
2153         return 0;
2154 }
2155
2156 void btrfs_pin_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, 1);
2160 }
2161
2162 void btrfs_unpin_extent(struct btrfs_fs_info *fs_info,
2163                         u64 bytenr, u64 num_bytes)
2164 {
2165         update_pinned_extents(fs_info->extent_root, bytenr, num_bytes, 0);
2166 }
2167
2168 /*
2169  * remove an extent from the root, returns 0 on success
2170  */
2171 static int __free_extent(struct btrfs_trans_handle *trans,
2172                          struct btrfs_root *root,
2173                          u64 bytenr, u64 num_bytes, u64 parent,
2174                          u64 root_objectid, u64 owner_objectid,
2175                          u64 owner_offset, int refs_to_drop)
2176 {
2177
2178         struct btrfs_key key;
2179         struct btrfs_path *path;
2180         struct btrfs_root *extent_root = root->fs_info->extent_root;
2181         struct extent_buffer *leaf;
2182         struct btrfs_extent_item *ei;
2183         struct btrfs_extent_inline_ref *iref;
2184         int ret;
2185         int is_data;
2186         int extent_slot = 0;
2187         int found_extent = 0;
2188         int num_to_del = 1;
2189         u32 item_size;
2190         u64 refs;
2191         int skinny_metadata =
2192                 btrfs_fs_incompat(extent_root->fs_info, SKINNY_METADATA);
2193
2194         if (root->fs_info->free_extent_hook) {
2195                 root->fs_info->free_extent_hook(trans, root, bytenr, num_bytes,
2196                                                 parent, root_objectid, owner_objectid,
2197                                                 owner_offset, refs_to_drop);
2198
2199         }
2200         path = btrfs_alloc_path();
2201         if (!path)
2202                 return -ENOMEM;
2203
2204         path->reada = 1;
2205
2206         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
2207         if (is_data)
2208                 skinny_metadata = 0;
2209         BUG_ON(!is_data && refs_to_drop != 1);
2210
2211         ret = lookup_extent_backref(trans, extent_root, path, &iref,
2212                                     bytenr, num_bytes, parent,
2213                                     root_objectid, owner_objectid,
2214                                     owner_offset);
2215         if (ret == 0) {
2216                 extent_slot = path->slots[0];
2217                 while (extent_slot >= 0) {
2218                         btrfs_item_key_to_cpu(path->nodes[0], &key,
2219                                               extent_slot);
2220                         if (key.objectid != bytenr)
2221                                 break;
2222                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
2223                             key.offset == num_bytes) {
2224                                 found_extent = 1;
2225                                 break;
2226                         }
2227                         if (key.type == BTRFS_METADATA_ITEM_KEY &&
2228                             key.offset == owner_objectid) {
2229                                 found_extent = 1;
2230                                 break;
2231                         }
2232                         if (path->slots[0] - extent_slot > 5)
2233                                 break;
2234                         extent_slot--;
2235                 }
2236 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2237                 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
2238                 if (found_extent && item_size < sizeof(*ei))
2239                         found_extent = 0;
2240 #endif
2241                 if (!found_extent) {
2242                         BUG_ON(iref);
2243                         ret = remove_extent_backref(trans, extent_root, path,
2244                                                     NULL, refs_to_drop,
2245                                                     is_data);
2246                         BUG_ON(ret);
2247                         btrfs_release_path(path);
2248
2249                         key.objectid = bytenr;
2250
2251                         if (skinny_metadata) {
2252                                 key.type = BTRFS_METADATA_ITEM_KEY;
2253                                 key.offset = owner_objectid;
2254                         } else {
2255                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2256                                 key.offset = num_bytes;
2257                         }
2258
2259                         ret = btrfs_search_slot(trans, extent_root,
2260                                                 &key, path, -1, 1);
2261                         if (ret > 0 && skinny_metadata && path->slots[0]) {
2262                                 path->slots[0]--;
2263                                 btrfs_item_key_to_cpu(path->nodes[0],
2264                                                       &key,
2265                                                       path->slots[0]);
2266                                 if (key.objectid == bytenr &&
2267                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
2268                                     key.offset == num_bytes)
2269                                         ret = 0;
2270                         }
2271
2272                         if (ret > 0 && skinny_metadata) {
2273                                 skinny_metadata = 0;
2274                                 btrfs_release_path(path);
2275                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2276                                 key.offset = num_bytes;
2277                                 ret = btrfs_search_slot(trans, extent_root,
2278                                                         &key, path, -1, 1);
2279                         }
2280
2281                         if (ret) {
2282                                 printk(KERN_ERR "umm, got %d back from search"
2283                                        ", was looking for %llu\n", ret,
2284                                        (unsigned long long)bytenr);
2285                                 btrfs_print_leaf(extent_root, path->nodes[0]);
2286                         }
2287                         BUG_ON(ret);
2288                         extent_slot = path->slots[0];
2289                 }
2290         } else {
2291                 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
2292                        "parent %llu root %llu  owner %llu offset %llu\n",
2293                        (unsigned long long)bytenr,
2294                        (unsigned long long)parent,
2295                        (unsigned long long)root_objectid,
2296                        (unsigned long long)owner_objectid,
2297                        (unsigned long long)owner_offset);
2298                 ret = -EIO;
2299                 goto fail;
2300         }
2301
2302         leaf = path->nodes[0];
2303         item_size = btrfs_item_size_nr(leaf, extent_slot);
2304 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2305         if (item_size < sizeof(*ei)) {
2306                 BUG_ON(found_extent || extent_slot != path->slots[0]);
2307                 ret = convert_extent_item_v0(trans, extent_root, path,
2308                                              owner_objectid, 0);
2309                 BUG_ON(ret < 0);
2310
2311                 btrfs_release_path(path);
2312
2313                 key.objectid = bytenr;
2314                 key.type = BTRFS_EXTENT_ITEM_KEY;
2315                 key.offset = num_bytes;
2316
2317                 ret = btrfs_search_slot(trans, extent_root, &key, path,
2318                                         -1, 1);
2319                 if (ret) {
2320                         printk(KERN_ERR "umm, got %d back from search"
2321                                ", was looking for %llu\n", ret,
2322                                (unsigned long long)bytenr);
2323                         btrfs_print_leaf(extent_root, path->nodes[0]);
2324                 }
2325                 BUG_ON(ret);
2326                 extent_slot = path->slots[0];
2327                 leaf = path->nodes[0];
2328                 item_size = btrfs_item_size_nr(leaf, extent_slot);
2329         }
2330 #endif
2331         BUG_ON(item_size < sizeof(*ei));
2332         ei = btrfs_item_ptr(leaf, extent_slot,
2333                             struct btrfs_extent_item);
2334         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
2335             key.type == BTRFS_EXTENT_ITEM_KEY) {
2336                 struct btrfs_tree_block_info *bi;
2337                 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
2338                 bi = (struct btrfs_tree_block_info *)(ei + 1);
2339                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
2340         }
2341
2342         refs = btrfs_extent_refs(leaf, ei);
2343         BUG_ON(refs < refs_to_drop);
2344         refs -= refs_to_drop;
2345
2346         if (refs > 0) {
2347                 /*
2348                  * In the case of inline back ref, reference count will
2349                  * be updated by remove_extent_backref
2350                  */
2351                 if (iref) {
2352                         BUG_ON(!found_extent);
2353                 } else {
2354                         btrfs_set_extent_refs(leaf, ei, refs);
2355                         btrfs_mark_buffer_dirty(leaf);
2356                 }
2357                 if (found_extent) {
2358                         ret = remove_extent_backref(trans, extent_root, path,
2359                                                     iref, refs_to_drop,
2360                                                     is_data);
2361                         BUG_ON(ret);
2362                 }
2363         } else {
2364                 int mark_free = 0;
2365                 int pin = 1;
2366
2367                 if (found_extent) {
2368                         BUG_ON(is_data && refs_to_drop !=
2369                                extent_data_ref_count(root, path, iref));
2370                         if (iref) {
2371                                 BUG_ON(path->slots[0] != extent_slot);
2372                         } else {
2373                                 BUG_ON(path->slots[0] != extent_slot + 1);
2374                                 path->slots[0] = extent_slot;
2375                                 num_to_del = 2;
2376                         }
2377                 }
2378
2379                 if (pin) {
2380                         ret = pin_down_bytes(trans, root, bytenr, num_bytes,
2381                                              is_data);
2382                         if (ret > 0)
2383                                 mark_free = 1;
2384                         BUG_ON(ret < 0);
2385                 }
2386
2387                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2388                                       num_to_del);
2389                 BUG_ON(ret);
2390                 btrfs_release_path(path);
2391
2392                 if (is_data) {
2393                         ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
2394                         BUG_ON(ret);
2395                 }
2396
2397                 update_block_group(trans, root, bytenr, num_bytes, 0, mark_free);
2398         }
2399 fail:
2400         btrfs_free_path(path);
2401         finish_current_insert(trans, extent_root);
2402         return ret;
2403 }
2404
2405 /*
2406  * find all the blocks marked as pending in the radix tree and remove
2407  * them from the extent map
2408  */
2409 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
2410                                btrfs_root *extent_root)
2411 {
2412         int ret;
2413         int err = 0;
2414         u64 start;
2415         u64 end;
2416         u64 priv;
2417         struct extent_io_tree *pending_del;
2418         struct extent_io_tree *extent_ins;
2419         struct pending_extent_op *extent_op;
2420
2421         extent_ins = &extent_root->fs_info->extent_ins;
2422         pending_del = &extent_root->fs_info->pending_del;
2423
2424         while(1) {
2425                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
2426                                             EXTENT_LOCKED);
2427                 if (ret)
2428                         break;
2429
2430                 ret = get_state_private(pending_del, start, &priv);
2431                 BUG_ON(ret);
2432                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2433
2434                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
2435                                   GFP_NOFS);
2436
2437                 if (!test_range_bit(extent_ins, start, end,
2438                                     EXTENT_LOCKED, 0)) {
2439                         ret = __free_extent(trans, extent_root,
2440                                             start, end + 1 - start, 0,
2441                                             extent_root->root_key.objectid,
2442                                             extent_op->level, 0, 1);
2443                         kfree(extent_op);
2444                 } else {
2445                         kfree(extent_op);
2446                         ret = get_state_private(extent_ins, start, &priv);
2447                         BUG_ON(ret);
2448                         extent_op = (struct pending_extent_op *)
2449                                                         (unsigned long)priv;
2450
2451                         clear_extent_bits(extent_ins, start, end,
2452                                           EXTENT_LOCKED, GFP_NOFS);
2453
2454                         if (extent_op->type == PENDING_BACKREF_UPDATE)
2455                                 BUG_ON(1);
2456
2457                         kfree(extent_op);
2458                 }
2459                 if (ret)
2460                         err = ret;
2461         }
2462         return err;
2463 }
2464
2465
2466 int btrfs_free_tree_block(struct btrfs_trans_handle *trans,
2467                           struct btrfs_root *root,
2468                           struct extent_buffer *buf,
2469                           u64 parent, int last_ref)
2470 {
2471         return btrfs_free_extent(trans, root, buf->start, buf->len, parent,
2472                                  root->root_key.objectid,
2473                                  btrfs_header_level(buf), 0);
2474 }
2475
2476 /*
2477  * remove an extent from the root, returns 0 on success
2478  */
2479
2480 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2481                       struct btrfs_root *root,
2482                       u64 bytenr, u64 num_bytes, u64 parent,
2483                       u64 root_objectid, u64 owner, u64 offset)
2484 {
2485         struct btrfs_root *extent_root = root->fs_info->extent_root;
2486         int pending_ret;
2487         int ret;
2488
2489         WARN_ON(num_bytes < root->sectorsize);
2490         if (root == extent_root) {
2491                 struct pending_extent_op *extent_op;
2492
2493                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2494                 BUG_ON(!extent_op);
2495
2496                 extent_op->type = PENDING_EXTENT_DELETE;
2497                 extent_op->bytenr = bytenr;
2498                 extent_op->num_bytes = num_bytes;
2499                 extent_op->level = (int)owner;
2500
2501                 set_extent_bits(&root->fs_info->pending_del,
2502                                 bytenr, bytenr + num_bytes - 1,
2503                                 EXTENT_LOCKED, GFP_NOFS);
2504                 set_state_private(&root->fs_info->pending_del,
2505                                   bytenr, (unsigned long)extent_op);
2506                 return 0;
2507         }
2508         ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2509                             root_objectid, owner, offset, 1);
2510         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2511         return ret ? ret : pending_ret;
2512 }
2513
2514 static u64 stripe_align(struct btrfs_root *root, u64 val)
2515 {
2516         u64 mask = ((u64)root->stripesize - 1);
2517         u64 ret = (val + mask) & ~mask;
2518         return ret;
2519 }
2520
2521 /*
2522  * walks the btree of allocated extents and find a hole of a given size.
2523  * The key ins is changed to record the hole:
2524  * ins->objectid == block start
2525  * ins->flags = BTRFS_EXTENT_ITEM_KEY
2526  * ins->offset == number of blocks
2527  * Any available blocks before search_start are skipped.
2528  */
2529 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
2530                                      struct btrfs_root *orig_root,
2531                                      u64 num_bytes, u64 empty_size,
2532                                      u64 search_start, u64 search_end,
2533                                      u64 hint_byte, struct btrfs_key *ins,
2534                                      u64 exclude_start, u64 exclude_nr,
2535                                      int data)
2536 {
2537         int ret;
2538         u64 orig_search_start = search_start;
2539         struct btrfs_root * root = orig_root->fs_info->extent_root;
2540         struct btrfs_fs_info *info = root->fs_info;
2541         u64 total_needed = num_bytes;
2542         struct btrfs_block_group_cache *block_group;
2543         int full_scan = 0;
2544         int wrapped = 0;
2545
2546         WARN_ON(num_bytes < root->sectorsize);
2547         ins->type = BTRFS_EXTENT_ITEM_KEY;
2548
2549         search_start = stripe_align(root, search_start);
2550
2551         if (hint_byte) {
2552                 block_group = btrfs_lookup_first_block_group(info, hint_byte);
2553                 if (!block_group)
2554                         hint_byte = search_start;
2555                 block_group = btrfs_find_block_group(root, block_group,
2556                                                      hint_byte, data, 1);
2557         } else {
2558                 block_group = btrfs_find_block_group(root,
2559                                                      trans->block_group,
2560                                                      search_start, data, 1);
2561         }
2562
2563         total_needed += empty_size;
2564
2565 check_failed:
2566         search_start = stripe_align(root, search_start);
2567         if (!block_group) {
2568                 block_group = btrfs_lookup_first_block_group(info,
2569                                                              search_start);
2570                 if (!block_group)
2571                         block_group = btrfs_lookup_first_block_group(info,
2572                                                        orig_search_start);
2573         }
2574         ret = find_search_start(root, &block_group, &search_start,
2575                                 total_needed, data);
2576         if (ret)
2577                 goto new_group;
2578
2579         ins->objectid = search_start;
2580         ins->offset = num_bytes;
2581
2582         if (ins->objectid + num_bytes >
2583             block_group->key.objectid + block_group->key.offset) {
2584                 search_start = block_group->key.objectid +
2585                         block_group->key.offset;
2586                 goto new_group;
2587         }
2588
2589         if (test_range_bit(&info->extent_ins, ins->objectid,
2590                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
2591                 search_start = ins->objectid + num_bytes;
2592                 goto new_group;
2593         }
2594
2595         if (test_range_bit(&info->pinned_extents, ins->objectid,
2596                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2597                 search_start = ins->objectid + num_bytes;
2598                 goto new_group;
2599         }
2600
2601         if (info->excluded_extents &&
2602             test_range_bit(info->excluded_extents, ins->objectid,
2603                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2604                 search_start = ins->objectid + num_bytes;
2605                 goto new_group;
2606         }
2607
2608         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2609             ins->objectid < exclude_start + exclude_nr)) {
2610                 search_start = exclude_start + exclude_nr;
2611                 goto new_group;
2612         }
2613
2614         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
2615                 if (check_crossing_stripes(info, ins->objectid, num_bytes)) {
2616                         struct btrfs_block_group_cache *bg_cache;
2617                         u64 bg_offset;
2618
2619                         bg_cache = btrfs_lookup_block_group(info, ins->objectid);
2620                         if (!bg_cache)
2621                                 goto no_bg_cache;
2622                         bg_offset = ins->objectid - bg_cache->key.objectid;
2623
2624                         search_start = round_up(bg_offset + num_bytes,
2625                                                 BTRFS_STRIPE_LEN) + bg_offset;
2626                         goto new_group;
2627                 }
2628 no_bg_cache:
2629                 block_group = btrfs_lookup_block_group(info, ins->objectid);
2630                 if (block_group)
2631                         trans->block_group = block_group;
2632         }
2633         ins->offset = num_bytes;
2634         return 0;
2635
2636 new_group:
2637         block_group = btrfs_lookup_first_block_group(info, search_start);
2638         if (!block_group) {
2639                 search_start = orig_search_start;
2640                 if (full_scan) {
2641                         ret = -ENOSPC;
2642                         goto error;
2643                 }
2644                 if (wrapped) {
2645                         if (!full_scan)
2646                                 total_needed -= empty_size;
2647                         full_scan = 1;
2648                 } else
2649                         wrapped = 1;
2650         }
2651         cond_resched();
2652         block_group = btrfs_find_block_group(root, block_group,
2653                                              search_start, data, 0);
2654         goto check_failed;
2655
2656 error:
2657         return ret;
2658 }
2659
2660 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2661                          struct btrfs_root *root,
2662                          u64 num_bytes, u64 empty_size,
2663                          u64 hint_byte, u64 search_end,
2664                          struct btrfs_key *ins, int data)
2665 {
2666         int ret;
2667         u64 search_start = 0;
2668         u64 alloc_profile;
2669         struct btrfs_fs_info *info = root->fs_info;
2670
2671         if (data) {
2672                 alloc_profile = info->avail_data_alloc_bits &
2673                                 info->data_alloc_profile;
2674                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2675         } else if ((info->system_allocs > 0 || root == info->chunk_root) &&
2676                    info->system_allocs >= 0) {
2677                 alloc_profile = info->avail_system_alloc_bits &
2678                                 info->system_alloc_profile;
2679                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2680         } else {
2681                 alloc_profile = info->avail_metadata_alloc_bits &
2682                                 info->metadata_alloc_profile;
2683                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2684         }
2685
2686         if (root->ref_cows) {
2687                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2688                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2689                                              num_bytes,
2690                                              BTRFS_BLOCK_GROUP_METADATA);
2691                         BUG_ON(ret);
2692                 }
2693                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2694                                      num_bytes + 2 * 1024 * 1024, data);
2695                 BUG_ON(ret);
2696         }
2697
2698         WARN_ON(num_bytes < root->sectorsize);
2699         ret = find_free_extent(trans, root, num_bytes, empty_size,
2700                                search_start, search_end, hint_byte, ins,
2701                                trans->alloc_exclude_start,
2702                                trans->alloc_exclude_nr, data);
2703         BUG_ON(ret);
2704         clear_extent_dirty(&root->fs_info->free_space_cache,
2705                            ins->objectid, ins->objectid + ins->offset - 1,
2706                            GFP_NOFS);
2707         return ret;
2708 }
2709
2710 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
2711                                      struct btrfs_root *root,
2712                                      u64 root_objectid, u64 generation,
2713                                      u64 flags, struct btrfs_disk_key *key,
2714                                      int level, struct btrfs_key *ins)
2715 {
2716         int ret;
2717         struct btrfs_fs_info *fs_info = root->fs_info;
2718         struct btrfs_extent_item *extent_item;
2719         struct btrfs_tree_block_info *block_info;
2720         struct btrfs_extent_inline_ref *iref;
2721         struct btrfs_path *path;
2722         struct extent_buffer *leaf;
2723         u32 size = sizeof(*extent_item) + sizeof(*iref);
2724         int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
2725
2726         if (!skinny_metadata)
2727                 size += sizeof(*block_info);
2728
2729         path = btrfs_alloc_path();
2730         if (!path)
2731                 return -ENOMEM;
2732
2733         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
2734                                       ins, size);
2735         BUG_ON(ret);
2736
2737         leaf = path->nodes[0];
2738         extent_item = btrfs_item_ptr(leaf, path->slots[0],
2739                                      struct btrfs_extent_item);
2740         btrfs_set_extent_refs(leaf, extent_item, 1);
2741         btrfs_set_extent_generation(leaf, extent_item, generation);
2742         btrfs_set_extent_flags(leaf, extent_item,
2743                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
2744
2745         if (skinny_metadata) {
2746                 iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
2747         } else {
2748                 block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
2749                 btrfs_set_tree_block_key(leaf, block_info, key);
2750                 btrfs_set_tree_block_level(leaf, block_info, level);
2751                 iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
2752         }
2753
2754         btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY);
2755         btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
2756
2757         btrfs_mark_buffer_dirty(leaf);
2758         btrfs_free_path(path);
2759
2760         ret = update_block_group(trans, root, ins->objectid, root->nodesize,
2761                                  1, 0);
2762         return ret;
2763 }
2764
2765 static int alloc_tree_block(struct btrfs_trans_handle *trans,
2766                             struct btrfs_root *root, u64 num_bytes,
2767                             u64 root_objectid, u64 generation,
2768                             u64 flags, struct btrfs_disk_key *key,
2769                             int level, u64 empty_size, u64 hint_byte,
2770                             u64 search_end, struct btrfs_key *ins)
2771 {
2772         int ret;
2773         ret = btrfs_reserve_extent(trans, root, num_bytes, empty_size,
2774                                    hint_byte, search_end, ins, 0);
2775         BUG_ON(ret);
2776
2777         if (root_objectid == BTRFS_EXTENT_TREE_OBJECTID) {
2778                 struct pending_extent_op *extent_op;
2779
2780                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2781                 BUG_ON(!extent_op);
2782
2783                 extent_op->type = PENDING_EXTENT_INSERT;
2784                 extent_op->bytenr = ins->objectid;
2785                 extent_op->num_bytes = ins->offset;
2786                 extent_op->level = level;
2787                 extent_op->flags = flags;
2788                 memcpy(&extent_op->key, key, sizeof(*key));
2789
2790                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2791                                 ins->objectid + ins->offset - 1,
2792                                 EXTENT_LOCKED, GFP_NOFS);
2793                 set_state_private(&root->fs_info->extent_ins,
2794                                   ins->objectid, (unsigned long)extent_op);
2795         } else {
2796                 if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) {
2797                         ins->offset = level;
2798                         ins->type = BTRFS_METADATA_ITEM_KEY;
2799                 }
2800                 ret = alloc_reserved_tree_block(trans, root, root_objectid,
2801                                                 generation, flags,
2802                                                 key, level, ins);
2803                 finish_current_insert(trans, root->fs_info->extent_root);
2804                 del_pending_extents(trans, root->fs_info->extent_root);
2805         }
2806         return ret;
2807 }
2808
2809 /*
2810  * helper function to allocate a block for a given tree
2811  * returns the tree buffer or NULL.
2812  */
2813 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2814                                         struct btrfs_root *root,
2815                                         u32 blocksize, u64 root_objectid,
2816                                         struct btrfs_disk_key *key, int level,
2817                                         u64 hint, u64 empty_size)
2818 {
2819         struct btrfs_key ins;
2820         int ret;
2821         struct extent_buffer *buf;
2822
2823         ret = alloc_tree_block(trans, root, blocksize, root_objectid,
2824                                trans->transid, 0, key, level,
2825                                empty_size, hint, (u64)-1, &ins);
2826         if (ret) {
2827                 BUG_ON(ret > 0);
2828                 return ERR_PTR(ret);
2829         }
2830
2831         buf = btrfs_find_create_tree_block(root->fs_info, ins.objectid,
2832                                            blocksize);
2833         if (!buf) {
2834                 btrfs_free_extent(trans, root, ins.objectid, ins.offset,
2835                                   0, root->root_key.objectid, level, 0);
2836                 BUG_ON(1);
2837                 return ERR_PTR(-ENOMEM);
2838         }
2839         btrfs_set_buffer_uptodate(buf);
2840         trans->blocks_used++;
2841
2842         return buf;
2843 }
2844
2845 #if 0
2846
2847 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2848                                   struct btrfs_root *root,
2849                                   struct extent_buffer *leaf)
2850 {
2851         u64 leaf_owner;
2852         u64 leaf_generation;
2853         struct btrfs_key key;
2854         struct btrfs_file_extent_item *fi;
2855         int i;
2856         int nritems;
2857         int ret;
2858
2859         BUG_ON(!btrfs_is_leaf(leaf));
2860         nritems = btrfs_header_nritems(leaf);
2861         leaf_owner = btrfs_header_owner(leaf);
2862         leaf_generation = btrfs_header_generation(leaf);
2863
2864         for (i = 0; i < nritems; i++) {
2865                 u64 disk_bytenr;
2866
2867                 btrfs_item_key_to_cpu(leaf, &key, i);
2868                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2869                         continue;
2870                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2871                 if (btrfs_file_extent_type(leaf, fi) ==
2872                     BTRFS_FILE_EXTENT_INLINE)
2873                         continue;
2874                 /*
2875                  * FIXME make sure to insert a trans record that
2876                  * repeats the snapshot del on crash
2877                  */
2878                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2879                 if (disk_bytenr == 0)
2880                         continue;
2881                 ret = btrfs_free_extent(trans, root, disk_bytenr,
2882                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2883                                 leaf->start, leaf_owner, leaf_generation,
2884                                 key.objectid, 0);
2885                 BUG_ON(ret);
2886         }
2887         return 0;
2888 }
2889
2890 static void noinline reada_walk_down(struct btrfs_root *root,
2891                                      struct extent_buffer *node,
2892                                      int slot)
2893 {
2894         u64 bytenr;
2895         u64 last = 0;
2896         u32 nritems;
2897         u32 refs;
2898         u32 blocksize;
2899         int ret;
2900         int i;
2901         int level;
2902         int skipped = 0;
2903
2904         nritems = btrfs_header_nritems(node);
2905         level = btrfs_header_level(node);
2906         if (level)
2907                 return;
2908
2909         for (i = slot; i < nritems && skipped < 32; i++) {
2910                 bytenr = btrfs_node_blockptr(node, i);
2911                 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
2912                              (last > bytenr && last - bytenr > 32 * 1024))) {
2913                         skipped++;
2914                         continue;
2915                 }
2916                 blocksize = btrfs_level_size(root, level - 1);
2917                 if (i != slot) {
2918                         ret = btrfs_lookup_extent_ref(NULL, root, bytenr,
2919                                                       blocksize, &refs);
2920                         BUG_ON(ret);
2921                         if (refs != 1) {
2922                                 skipped++;
2923                                 continue;
2924                         }
2925                 }
2926                 mutex_unlock(&root->fs_info->fs_mutex);
2927                 ret = readahead_tree_block(root, bytenr, blocksize,
2928                                            btrfs_node_ptr_generation(node, i));
2929                 last = bytenr + blocksize;
2930                 cond_resched();
2931                 mutex_lock(&root->fs_info->fs_mutex);
2932                 if (ret)
2933                         break;
2934         }
2935 }
2936
2937 /*
2938  * helper function for drop_snapshot, this walks down the tree dropping ref
2939  * counts as it goes.
2940  */
2941 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2942                                    struct btrfs_root *root,
2943                                    struct btrfs_path *path, int *level)
2944 {
2945         u64 root_owner;
2946         u64 root_gen;
2947         u64 bytenr;
2948         u64 ptr_gen;
2949         struct extent_buffer *next;
2950         struct extent_buffer *cur;
2951         struct extent_buffer *parent;
2952         u32 blocksize;
2953         int ret;
2954         u32 refs;
2955
2956         WARN_ON(*level < 0);
2957         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2958         ret = btrfs_lookup_extent_ref(trans, root,
2959                                       path->nodes[*level]->start,
2960                                       path->nodes[*level]->len, &refs);
2961         BUG_ON(ret);
2962         if (refs > 1)
2963                 goto out;
2964
2965         /*
2966          * walk down to the last node level and free all the leaves
2967          */
2968         while(*level >= 0) {
2969                 WARN_ON(*level < 0);
2970                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2971                 cur = path->nodes[*level];
2972
2973                 if (btrfs_header_level(cur) != *level)
2974                         WARN_ON(1);
2975
2976                 if (path->slots[*level] >=
2977                     btrfs_header_nritems(cur))
2978                         break;
2979                 if (*level == 0) {
2980                         ret = drop_leaf_ref(trans, root, cur);
2981                         BUG_ON(ret);
2982                         break;
2983                 }
2984                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2985                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2986                 blocksize = btrfs_level_size(root, *level - 1);
2987                 ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
2988                                               &refs);
2989                 BUG_ON(ret);
2990                 if (refs != 1) {
2991                         parent = path->nodes[*level];
2992                         root_owner = btrfs_header_owner(parent);
2993                         root_gen = btrfs_header_generation(parent);
2994                         path->slots[*level]++;
2995                         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
2996                                                 parent->start, root_owner,
2997                                                 root_gen, *level - 1, 1);
2998                         BUG_ON(ret);
2999                         continue;
3000                 }
3001                 next = btrfs_find_tree_block(root, bytenr, blocksize);
3002                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
3003                         free_extent_buffer(next);
3004                         reada_walk_down(root, cur, path->slots[*level]);
3005                         mutex_unlock(&root->fs_info->fs_mutex);
3006                         next = read_tree_block(root, bytenr, blocksize,
3007                                                ptr_gen);
3008                         mutex_lock(&root->fs_info->fs_mutex);
3009                         if (!extent_buffer_uptodate(next)) {
3010                                 if (IS_ERR(next))
3011                                         ret = PTR_ERR(next);
3012                                 else
3013                                         ret = -EIO;
3014                                 break;
3015                         }
3016                 }
3017                 WARN_ON(*level <= 0);
3018                 if (path->nodes[*level-1])
3019                         free_extent_buffer(path->nodes[*level-1]);
3020                 path->nodes[*level-1] = next;
3021                 *level = btrfs_header_level(next);
3022                 path->slots[*level] = 0;
3023         }
3024 out:
3025         WARN_ON(*level < 0);
3026         WARN_ON(*level >= BTRFS_MAX_LEVEL);
3027
3028         if (path->nodes[*level] == root->node) {
3029                 root_owner = root->root_key.objectid;
3030                 parent = path->nodes[*level];
3031         } else {
3032                 parent = path->nodes[*level + 1];
3033                 root_owner = btrfs_header_owner(parent);
3034         }
3035
3036         root_gen = btrfs_header_generation(parent);
3037         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
3038                                 path->nodes[*level]->len, parent->start,
3039                                 root_owner, root_gen, *level, 1);
3040         free_extent_buffer(path->nodes[*level]);
3041         path->nodes[*level] = NULL;
3042         *level += 1;
3043         BUG_ON(ret);
3044         return 0;
3045 }
3046
3047 /*
3048  * helper for dropping snapshots.  This walks back up the tree in the path
3049  * to find the first node higher up where we haven't yet gone through
3050  * all the slots
3051  */
3052 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
3053                                  struct btrfs_root *root,
3054                                  struct btrfs_path *path, int *level)
3055 {
3056         u64 root_owner;
3057         u64 root_gen;
3058         struct btrfs_root_item *root_item = &root->root_item;
3059         int i;
3060         int slot;
3061         int ret;
3062
3063         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
3064                 slot = path->slots[i];
3065                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3066                         struct extent_buffer *node;
3067                         struct btrfs_disk_key disk_key;
3068                         node = path->nodes[i];
3069                         path->slots[i]++;
3070                         *level = i;
3071                         WARN_ON(*level == 0);
3072                         btrfs_node_key(node, &disk_key, path->slots[i]);
3073                         memcpy(&root_item->drop_progress,
3074                                &disk_key, sizeof(disk_key));
3075                         root_item->drop_level = i;
3076                         return 0;
3077                 } else {
3078                         struct extent_buffer *parent;
3079                         if (path->nodes[*level] == root->node)
3080                                 parent = path->nodes[*level];
3081                         else
3082                                 parent = path->nodes[*level + 1];
3083
3084                         root_owner = btrfs_header_owner(parent);
3085                         root_gen = btrfs_header_generation(parent);
3086                         ret = btrfs_free_extent(trans, root,
3087                                                 path->nodes[*level]->start,
3088                                                 path->nodes[*level]->len,
3089                                                 parent->start, root_owner,
3090                                                 root_gen, *level, 1);
3091                         BUG_ON(ret);
3092                         free_extent_buffer(path->nodes[*level]);
3093                         path->nodes[*level] = NULL;
3094                         *level = i + 1;
3095                 }
3096         }
3097         return 1;
3098 }
3099
3100 #endif
3101
3102 int btrfs_free_block_groups(struct btrfs_fs_info *info)
3103 {
3104         struct btrfs_space_info *sinfo;
3105         struct btrfs_block_group_cache *cache;
3106         u64 start;
3107         u64 end;
3108         u64 ptr;
3109         int ret;
3110
3111         while(1) {
3112                 ret = find_first_extent_bit(&info->block_group_cache, 0,
3113                                             &start, &end, (unsigned int)-1);
3114                 if (ret)
3115                         break;
3116                 ret = get_state_private(&info->block_group_cache, start, &ptr);
3117                 if (!ret) {
3118                         cache = u64_to_ptr(ptr);
3119                         if (cache->free_space_ctl) {
3120                                 btrfs_remove_free_space_cache(cache);
3121                                 kfree(cache->free_space_ctl);
3122                         }
3123                         kfree(cache);
3124                 }
3125                 clear_extent_bits(&info->block_group_cache, start,
3126                                   end, (unsigned int)-1, GFP_NOFS);
3127         }
3128         while(1) {
3129                 ret = find_first_extent_bit(&info->free_space_cache, 0,
3130                                             &start, &end, EXTENT_DIRTY);
3131                 if (ret)
3132                         break;
3133                 clear_extent_dirty(&info->free_space_cache, start,
3134                                    end, GFP_NOFS);
3135         }
3136
3137         while (!list_empty(&info->space_info)) {
3138                 sinfo = list_entry(info->space_info.next,
3139                                    struct btrfs_space_info, list);
3140                 list_del_init(&sinfo->list);
3141                 kfree(sinfo);
3142         }
3143         return 0;
3144 }
3145
3146 static int find_first_block_group(struct btrfs_root *root,
3147                 struct btrfs_path *path, struct btrfs_key *key)
3148 {
3149         int ret;
3150         struct btrfs_key found_key;
3151         struct extent_buffer *leaf;
3152         int slot;
3153
3154         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
3155         if (ret < 0)
3156                 return ret;
3157         while(1) {
3158                 slot = path->slots[0];
3159                 leaf = path->nodes[0];
3160                 if (slot >= btrfs_header_nritems(leaf)) {
3161                         ret = btrfs_next_leaf(root, path);
3162                         if (ret == 0)
3163                                 continue;
3164                         if (ret < 0)
3165                                 goto error;
3166                         break;
3167                 }
3168                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3169
3170                 if (found_key.objectid >= key->objectid &&
3171                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
3172                         return 0;
3173                 path->slots[0]++;
3174         }
3175         ret = -ENOENT;
3176 error:
3177         return ret;
3178 }
3179
3180 static void account_super_bytes(struct btrfs_fs_info *fs_info,
3181                                 struct btrfs_block_group_cache *cache)
3182 {
3183         u64 bytenr;
3184         u64 *logical;
3185         int stripe_len;
3186         int i, nr, ret;
3187
3188         if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
3189                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
3190                 cache->bytes_super += stripe_len;
3191         }
3192
3193         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
3194                 bytenr = btrfs_sb_offset(i);
3195                 ret = btrfs_rmap_block(&fs_info->mapping_tree,
3196                                        cache->key.objectid, bytenr,
3197                                        0, &logical, &nr, &stripe_len);
3198                 if (ret)
3199                         return;
3200
3201                 while (nr--) {
3202                         u64 start, len;
3203
3204                         if (logical[nr] > cache->key.objectid +
3205                             cache->key.offset)
3206                                 continue;
3207
3208                         if (logical[nr] + stripe_len <= cache->key.objectid)
3209                                 continue;
3210
3211                         start = logical[nr];
3212                         if (start < cache->key.objectid) {
3213                                 start = cache->key.objectid;
3214                                 len = (logical[nr] + stripe_len) - start;
3215                         } else {
3216                                 len = min_t(u64, stripe_len,
3217                                             cache->key.objectid +
3218                                             cache->key.offset - start);
3219                         }
3220
3221                         cache->bytes_super += len;
3222                 }
3223
3224                 kfree(logical);
3225         }
3226 }
3227
3228 int btrfs_read_block_groups(struct btrfs_root *root)
3229 {
3230         struct btrfs_path *path;
3231         int ret;
3232         int bit;
3233         struct btrfs_block_group_cache *cache;
3234         struct btrfs_fs_info *info = root->fs_info;
3235         struct btrfs_space_info *space_info;
3236         struct extent_io_tree *block_group_cache;
3237         struct btrfs_key key;
3238         struct btrfs_key found_key;
3239         struct extent_buffer *leaf;
3240
3241         block_group_cache = &info->block_group_cache;
3242
3243         root = info->extent_root;
3244         key.objectid = 0;
3245         key.offset = 0;
3246         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3247         path = btrfs_alloc_path();
3248         if (!path)
3249                 return -ENOMEM;
3250
3251         while(1) {
3252                 ret = find_first_block_group(root, path, &key);
3253                 if (ret > 0) {
3254                         ret = 0;
3255                         goto error;
3256                 }
3257                 if (ret != 0) {
3258                         goto error;
3259                 }
3260                 leaf = path->nodes[0];
3261                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3262                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3263                 if (!cache) {
3264                         ret = -ENOMEM;
3265                         goto error;
3266                 }
3267
3268                 read_extent_buffer(leaf, &cache->item,
3269                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
3270                                    sizeof(cache->item));
3271                 memcpy(&cache->key, &found_key, sizeof(found_key));
3272                 cache->cached = 0;
3273                 cache->pinned = 0;
3274                 key.objectid = found_key.objectid + found_key.offset;
3275                 if (found_key.offset == 0)
3276                         key.objectid++;
3277                 btrfs_release_path(path);
3278                 cache->flags = btrfs_block_group_flags(&cache->item);
3279                 bit = 0;
3280                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3281                         bit = BLOCK_GROUP_DATA;
3282                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
3283                         bit = BLOCK_GROUP_SYSTEM;
3284                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3285                         bit = BLOCK_GROUP_METADATA;
3286                 }
3287                 set_avail_alloc_bits(info, cache->flags);
3288                 if (btrfs_chunk_readonly(root, cache->key.objectid))
3289                         cache->ro = 1;
3290
3291                 account_super_bytes(info, cache);
3292
3293                 ret = update_space_info(info, cache->flags, found_key.offset,
3294                                         btrfs_block_group_used(&cache->item),
3295                                         &space_info);
3296                 BUG_ON(ret);
3297                 cache->space_info = space_info;
3298
3299                 /* use EXTENT_LOCKED to prevent merging */
3300                 set_extent_bits(block_group_cache, found_key.objectid,
3301                                 found_key.objectid + found_key.offset - 1,
3302                                 bit | EXTENT_LOCKED, GFP_NOFS);
3303                 set_state_private(block_group_cache, found_key.objectid,
3304                                   (unsigned long)cache);
3305         }
3306         ret = 0;
3307 error:
3308         btrfs_free_path(path);
3309         return ret;
3310 }
3311
3312 struct btrfs_block_group_cache *
3313 btrfs_add_block_group(struct btrfs_fs_info *fs_info, u64 bytes_used, u64 type,
3314                       u64 chunk_objectid, u64 chunk_offset, u64 size)
3315 {
3316         int ret;
3317         int bit = 0;
3318         struct btrfs_block_group_cache *cache;
3319         struct extent_io_tree *block_group_cache;
3320
3321         block_group_cache = &fs_info->block_group_cache;
3322
3323         cache = kzalloc(sizeof(*cache), GFP_NOFS);
3324         BUG_ON(!cache);
3325         cache->key.objectid = chunk_offset;
3326         cache->key.offset = size;
3327
3328         cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3329         btrfs_set_block_group_used(&cache->item, bytes_used);
3330         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
3331         cache->flags = type;
3332         btrfs_set_block_group_flags(&cache->item, type);
3333
3334         account_super_bytes(fs_info, cache);
3335         ret = update_space_info(fs_info, cache->flags, size, bytes_used,
3336                                 &cache->space_info);
3337         BUG_ON(ret);
3338
3339         bit = block_group_state_bits(type);
3340         ret = set_extent_bits(block_group_cache, chunk_offset,
3341                               chunk_offset + size - 1,
3342                               bit | EXTENT_LOCKED, GFP_NOFS);
3343         BUG_ON(ret);
3344
3345         ret = set_state_private(block_group_cache, chunk_offset,
3346                                 (unsigned long)cache);
3347         BUG_ON(ret);
3348         set_avail_alloc_bits(fs_info, type);
3349
3350         return cache;
3351 }
3352
3353 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
3354                            struct btrfs_root *root, u64 bytes_used,
3355                            u64 type, u64 chunk_objectid, u64 chunk_offset,
3356                            u64 size)
3357 {
3358         int ret;
3359         struct btrfs_root *extent_root;
3360         struct btrfs_block_group_cache *cache;
3361
3362         cache = btrfs_add_block_group(root->fs_info, bytes_used, type,
3363                                       chunk_objectid, chunk_offset, size);
3364         extent_root = root->fs_info->extent_root;
3365         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3366                                 sizeof(cache->item));
3367         BUG_ON(ret);
3368
3369         ret = finish_current_insert(trans, extent_root);
3370         BUG_ON(ret);
3371         ret = del_pending_extents(trans, extent_root);
3372         BUG_ON(ret);
3373
3374         return 0;
3375 }
3376
3377 /*
3378  * This is for converter use only.
3379  *
3380  * In that case, we don't know where are free blocks located.
3381  * Therefore all block group cache entries must be setup properly
3382  * before doing any block allocation.
3383  */
3384 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
3385                             struct btrfs_root *root)
3386 {
3387         u64 total_bytes;
3388         u64 cur_start;
3389         u64 group_type;
3390         u64 group_size;
3391         u64 group_align;
3392         u64 total_data = 0;
3393         u64 total_metadata = 0;
3394         u64 chunk_objectid;
3395         int ret;
3396         int bit;
3397         struct btrfs_root *extent_root;
3398         struct btrfs_block_group_cache *cache;
3399         struct extent_io_tree *block_group_cache;
3400
3401         extent_root = root->fs_info->extent_root;
3402         block_group_cache = &root->fs_info->block_group_cache;
3403         chunk_objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3404         total_bytes = btrfs_super_total_bytes(root->fs_info->super_copy);
3405         group_align = 64 * root->sectorsize;
3406
3407         cur_start = 0;
3408         while (cur_start < total_bytes) {
3409                 group_size = total_bytes / 12;
3410                 group_size = min_t(u64, group_size, total_bytes - cur_start);
3411                 if (cur_start == 0) {
3412                         bit = BLOCK_GROUP_SYSTEM;
3413                         group_type = BTRFS_BLOCK_GROUP_SYSTEM;
3414                         group_size /= 4;
3415                         group_size &= ~(group_align - 1);
3416                         group_size = max_t(u64, group_size, 8 * 1024 * 1024);
3417                         group_size = min_t(u64, group_size, 32 * 1024 * 1024);
3418                 } else {
3419                         group_size &= ~(group_align - 1);
3420                         if (total_data >= total_metadata * 2) {
3421                                 group_type = BTRFS_BLOCK_GROUP_METADATA;
3422                                 group_size = min_t(u64, group_size,
3423                                                    1ULL * 1024 * 1024 * 1024);
3424                                 total_metadata += group_size;
3425                         } else {
3426                                 group_type = BTRFS_BLOCK_GROUP_DATA;
3427                                 group_size = min_t(u64, group_size,
3428                                                    5ULL * 1024 * 1024 * 1024);
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, GFP_NOFS);
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, u64 len)
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, GFP_NOFS);
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, len);
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, GFP_NOFS);
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 += root->nodesize;
3909                         ret = btrfs_update_block_group(trans, root,
3910                                   key.objectid, root->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->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, GFP_NOFS);
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, GFP_NOFS);
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->mapping_tree,
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 }