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