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         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 958                 if (parent > 0)
 959                         return BTRFS_SHARED_BLOCK_REF_KEY;
 960                 else
 961                         return BTRFS_TREE_BLOCK_REF_KEY;
 962         } else {
 963                 if (parent > 0)
 964                         return BTRFS_SHARED_DATA_REF_KEY;
 965                 else
 966                         return BTRFS_EXTENT_DATA_REF_KEY;
 967         }
 968 }
 969
 970 static int find_next_key(struct btrfs_path *path, struct btrfs_key *key)
 971
 972 {
 973         int level;
 974         for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
 975                 if (!path->nodes[level])
 976                         break;
 977                 if (path->slots[level] + 1 >=
 978                     btrfs_header_nritems(path->nodes[level]))
 979                         continue;
 980                 if (level == 0)
 981                         btrfs_item_key_to_cpu(path->nodes[level], key,
 982                                               path->slots[level] + 1);
 983                 else
 984                         btrfs_node_key_to_cpu(path->nodes[level], key,
 985                                               path->slots[level] + 1);
 986                 return 0;
 987         }
 988         return 1;
 989 }
 990
 991 static int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
 992                                  struct btrfs_root *root,
 993                                  struct btrfs_path *path,
 994                                  struct btrfs_extent_inline_ref **ref_ret,
 995                                  u64 bytenr, u64 num_bytes,
 996                                  u64 parent, u64 root_objectid,
 997                                  u64 owner, u64 offset, int insert)
 998 {
 999         struct btrfs_key key;
1000         struct extent_buffer *leaf;
1001         struct btrfs_extent_item *ei;
1002         struct btrfs_extent_inline_ref *iref;
1003         u64 flags;
1004         u32 item_size;
1005         unsigned long ptr;
1006         unsigned long end;
1007         int extra_size;
1008         int type;
1009         int want;
1010         int ret;
1011         int err = 0;
1012         int skinny_metadata =
1013                 btrfs_fs_incompat(root->fs_info,
1014                                   BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
1015
1016         key.objectid = bytenr;
1017         key.type = BTRFS_EXTENT_ITEM_KEY;
1018         key.offset = num_bytes;
1019
1020         want = extent_ref_type(parent, owner);
1021         if (insert)
1022                 extra_size = btrfs_extent_inline_ref_size(want);
1023         else
1024                 extra_size = -1;
1025
1026         if (owner < BTRFS_FIRST_FREE_OBJECTID && skinny_metadata) {
1027                 skinny_metadata = 1;
1028                 key.type = BTRFS_METADATA_ITEM_KEY;
1029                 key.offset = owner;
1030         } else if (skinny_metadata) {
1031                 skinny_metadata = 0;
1032         }
1033
1034 again:
1035         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1036         if (ret < 0) {
1037                 err = ret;
1038                 goto out;
1039         }
1040
1041         /*
1042          * We may be a newly converted file system which still has the old fat
1043          * extent entries for metadata, so try and see if we have one of those.
1044          */
1045         if (ret > 0 && skinny_metadata) {
1046                 skinny_metadata = 0;
1047                 if (path->slots[0]) {
1048                         path->slots[0]--;
1049                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1050                                               path->slots[0]);
1051                         if (key.objectid == bytenr &&
1052                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1053                             key.offset == num_bytes)
1054                                 ret = 0;
1055                 }
1056                 if (ret) {
1057                         key.type = BTRFS_EXTENT_ITEM_KEY;
1058                         key.offset = num_bytes;
1059                         goto again;
1060                 }
1061         }
1062
1063         if (ret) {
1064                 printf("Failed to find [%llu, %u, %llu]\n", key.objectid, key.type, key.offset);
1065                 return -ENOENT;
1066         }
1067
1068         BUG_ON(ret);
1069
1070         leaf = path->nodes[0];
1071         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1072 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1073         if (item_size < sizeof(*ei)) {
1074                 if (!insert) {
1075                         err = -ENOENT;
1076                         goto out;
1077                 }
1078                 ret = convert_extent_item_v0(trans, root, path, owner,
1079                                              extra_size);
1080                 if (ret < 0) {
1081                         err = ret;
1082                         goto out;
1083                 }
1084                 leaf = path->nodes[0];
1085                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1086         }
1087 #endif
1088         if (item_size < sizeof(*ei)) {
1089                 printf("Size is %u, needs to be %u, slot %d\n",
1090                        (unsigned)item_size,
1091                        (unsigned)sizeof(*ei), path->slots[0]);
1092                 btrfs_print_leaf(root, leaf);
1093                 return -EINVAL;
1094         }
1095         BUG_ON(item_size < sizeof(*ei));
1096
1097         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1098         flags = btrfs_extent_flags(leaf, ei);
1099
1100         ptr = (unsigned long)(ei + 1);
1101         end = (unsigned long)ei + item_size;
1102
1103         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
1104                 ptr += sizeof(struct btrfs_tree_block_info);
1105                 BUG_ON(ptr > end);
1106         } else if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
1107                 if (!(flags & BTRFS_EXTENT_FLAG_DATA)) {
1108                         return -EIO;
1109                 }
1110         }
1111
1112         err = -ENOENT;
1113         while (1) {
1114                 if (ptr >= end) {
1115                         WARN_ON(ptr > end);
1116                         break;
1117                 }
1118                 iref = (struct btrfs_extent_inline_ref *)ptr;
1119                 type = btrfs_extent_inline_ref_type(leaf, iref);
1120                 if (want < type)
1121                         break;
1122                 if (want > type) {
1123                         ptr += btrfs_extent_inline_ref_size(type);
1124                         continue;
1125                 }
1126
1127                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1128                         struct btrfs_extent_data_ref *dref;
1129                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1130                         if (match_extent_data_ref(leaf, dref, root_objectid,
1131                                                   owner, offset)) {
1132                                 err = 0;
1133                                 break;
1134                         }
1135                         if (hash_extent_data_ref_item(leaf, dref) <
1136                             hash_extent_data_ref(root_objectid, owner, offset))
1137                                 break;
1138                 } else {
1139                         u64 ref_offset;
1140                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1141                         if (parent > 0) {
1142                                 if (parent == ref_offset) {
1143                                         err = 0;
1144                                         break;
1145                                 }
1146                                 if (ref_offset < parent)
1147                                         break;
1148                         } else {
1149                                 if (root_objectid == ref_offset) {
1150                                         err = 0;
1151                                         break;
1152                                 }
1153                                 if (ref_offset < root_objectid)
1154                                         break;
1155                         }
1156                 }
1157                 ptr += btrfs_extent_inline_ref_size(type);
1158         }
1159         if (err == -ENOENT && insert) {
1160                 if (item_size + extra_size >=
1161                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1162                         err = -EAGAIN;
1163                         goto out;
1164                 }
1165                 /*
1166                  * To add new inline back ref, we have to make sure
1167                  * there is no corresponding back ref item.
1168                  * For simplicity, we just do not add new inline back
1169                  * ref if there is any back ref item.
1170                  */
1171                 if (find_next_key(path, &key) == 0 && key.objectid == bytenr &&
1172                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1173                         err = -EAGAIN;
1174                         goto out;
1175                 }
1176         }
1177         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1178 out:
1179         return err;
1180 }
1181
1182 static int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1183                                 struct btrfs_root *root,
1184                                 struct btrfs_path *path,
1185                                 struct btrfs_extent_inline_ref *iref,
1186                                 u64 parent, u64 root_objectid,
1187                                 u64 owner, u64 offset, int refs_to_add)
1188 {
1189         struct extent_buffer *leaf;
1190         struct btrfs_extent_item *ei;
1191         unsigned long ptr;
1192         unsigned long end;
1193         unsigned long item_offset;
1194         u64 refs;
1195         int size;
1196         int type;
1197         int ret;
1198
1199         leaf = path->nodes[0];
1200         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1201         item_offset = (unsigned long)iref - (unsigned long)ei;
1202
1203         type = extent_ref_type(parent, owner);
1204         size = btrfs_extent_inline_ref_size(type);
1205
1206         ret = btrfs_extend_item(trans, root, path, size);
1207         BUG_ON(ret);
1208
1209         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1210         refs = btrfs_extent_refs(leaf, ei);
1211         refs += refs_to_add;
1212         btrfs_set_extent_refs(leaf, ei, refs);
1213
1214         ptr = (unsigned long)ei + item_offset;
1215         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1216         if (ptr < end - size)
1217                 memmove_extent_buffer(leaf, ptr + size, ptr,
1218                                       end - size - ptr);
1219
1220         iref = (struct btrfs_extent_inline_ref *)ptr;
1221         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1222         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1223                 struct btrfs_extent_data_ref *dref;
1224                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1225                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1226                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1227                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1228                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1229         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1230                 struct btrfs_shared_data_ref *sref;
1231                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1232                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1233                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1234         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1235                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1236         } else {
1237                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1238         }
1239         btrfs_mark_buffer_dirty(leaf);
1240         return 0;
1241 }
1242
1243 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1244                                  struct btrfs_root *root,
1245                                  struct btrfs_path *path,
1246                                  struct btrfs_extent_inline_ref **ref_ret,
1247                                  u64 bytenr, u64 num_bytes, u64 parent,
1248                                  u64 root_objectid, u64 owner, u64 offset)
1249 {
1250         int ret;
1251
1252         ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1253                                            bytenr, num_bytes, parent,
1254                                            root_objectid, owner, offset, 0);
1255         if (ret != -ENOENT)
1256                 return ret;
1257
1258         btrfs_release_path(root, path);
1259         *ref_ret = NULL;
1260
1261         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1262                 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1263                                             root_objectid);
1264         } else {
1265                 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1266                                              root_objectid, owner, offset);
1267         }
1268         return ret;
1269 }
1270
1271 static int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1272                                  struct btrfs_root *root,
1273                                  struct btrfs_path *path,
1274                                  struct btrfs_extent_inline_ref *iref,
1275                                  int refs_to_mod)
1276 {
1277         struct extent_buffer *leaf;
1278         struct btrfs_extent_item *ei;
1279         struct btrfs_extent_data_ref *dref = NULL;
1280         struct btrfs_shared_data_ref *sref = NULL;
1281         unsigned long ptr;
1282         unsigned long end;
1283         u32 item_size;
1284         int size;
1285         int type;
1286         int ret;
1287         u64 refs;
1288
1289         leaf = path->nodes[0];
1290         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1291         refs = btrfs_extent_refs(leaf, ei);
1292         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1293         refs += refs_to_mod;
1294         btrfs_set_extent_refs(leaf, ei, refs);
1295
1296         type = btrfs_extent_inline_ref_type(leaf, iref);
1297
1298         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1299                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1300                 refs = btrfs_extent_data_ref_count(leaf, dref);
1301         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1302                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1303                 refs = btrfs_shared_data_ref_count(leaf, sref);
1304         } else {
1305                 refs = 1;
1306                 BUG_ON(refs_to_mod != -1);
1307         }
1308
1309         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1310         refs += refs_to_mod;
1311
1312         if (refs > 0) {
1313                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1314                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1315                 else
1316                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1317         } else {
1318                 size =  btrfs_extent_inline_ref_size(type);
1319                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1320                 ptr = (unsigned long)iref;
1321                 end = (unsigned long)ei + item_size;
1322                 if (ptr + size < end)
1323                         memmove_extent_buffer(leaf, ptr, ptr + size,
1324                                               end - ptr - size);
1325                 item_size -= size;
1326                 ret = btrfs_truncate_item(trans, root, path, item_size, 1);
1327                 BUG_ON(ret);
1328         }
1329         btrfs_mark_buffer_dirty(leaf);
1330         return 0;
1331 }
1332
1333 static int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1334                                  struct btrfs_root *root,
1335                                  struct btrfs_path *path,
1336                                  u64 bytenr, u64 num_bytes, u64 parent,
1337                                  u64 root_objectid, u64 owner,
1338                                  u64 offset, int refs_to_add)
1339 {
1340         struct btrfs_extent_inline_ref *iref;
1341         int ret;
1342
1343         ret = lookup_inline_extent_backref(trans, root, path, &iref,
1344                                            bytenr, num_bytes, parent,
1345                                            root_objectid, owner, offset, 1);
1346         if (ret == 0) {
1347                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1348                 ret = update_inline_extent_backref(trans, root, path, iref,
1349                                                    refs_to_add);
1350         } else if (ret == -ENOENT) {
1351                 ret = setup_inline_extent_backref(trans, root, path, iref,
1352                                                   parent, root_objectid,
1353                                                   owner, offset, refs_to_add);
1354         }
1355         return ret;
1356 }
1357
1358 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1359                                  struct btrfs_root *root,
1360                                  struct btrfs_path *path,
1361                                  u64 bytenr, u64 parent, u64 root_objectid,
1362                                  u64 owner, u64 offset, int refs_to_add)
1363 {
1364         int ret;
1365
1366         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
1367                 ret = insert_extent_data_ref(trans, root, path, bytenr,
1368                                              parent, root_objectid,
1369                                              owner, offset, refs_to_add);
1370         } else {
1371                 BUG_ON(refs_to_add != 1);
1372                 ret = insert_tree_block_ref(trans, root, path, bytenr,
1373                                             parent, root_objectid);
1374         }
1375         return ret;
1376 }
1377
1378 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1379                                  struct btrfs_root *root,
1380                                  struct btrfs_path *path,
1381                                  struct btrfs_extent_inline_ref *iref,
1382                                  int refs_to_drop, int is_data)
1383 {
1384         int ret;
1385
1386         BUG_ON(!is_data && refs_to_drop != 1);
1387         if (iref) {
1388                 ret = update_inline_extent_backref(trans, root, path, iref,
1389                                                    -refs_to_drop);
1390         } else if (is_data) {
1391                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1392         } else {
1393                 ret = btrfs_del_item(trans, root, path);
1394         }
1395         return ret;
1396 }
1397
1398 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1399                          struct btrfs_root *root,
1400                          u64 bytenr, u64 num_bytes, u64 parent,
1401                          u64 root_objectid, u64 owner, u64 offset)
1402 {
1403         struct btrfs_path *path;
1404         struct extent_buffer *leaf;
1405         struct btrfs_extent_item *item;
1406         u64 refs;
1407         int ret;
1408         int err = 0;
1409
1410         path = btrfs_alloc_path();
1411         if (!path)
1412                 return -ENOMEM;
1413
1414         path->reada = 1;
1415         path->leave_spinning = 1;
1416
1417         ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1418                                            path, bytenr, num_bytes, parent,
1419                                            root_objectid, owner, offset, 1);
1420         if (ret == 0)
1421                 goto out;
1422
1423         if (ret != -EAGAIN) {
1424                 err = ret;
1425                 goto out;
1426         }
1427
1428         leaf = path->nodes[0];
1429         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1430         refs = btrfs_extent_refs(leaf, item);
1431         btrfs_set_extent_refs(leaf, item, refs + 1);
1432
1433         btrfs_mark_buffer_dirty(leaf);
1434         btrfs_release_path(root->fs_info->extent_root, path);
1435
1436         path->reada = 1;
1437         path->leave_spinning = 1;
1438
1439         /* now insert the actual backref */
1440         ret = insert_extent_backref(trans, root->fs_info->extent_root,
1441                                     path, bytenr, parent, root_objectid,
1442                                     owner, offset, 1);
1443         if (ret)
1444                 err = ret;
1445 out:
1446         btrfs_free_path(path);
1447         finish_current_insert(trans, root->fs_info->extent_root);
1448         del_pending_extents(trans, root->fs_info->extent_root);
1449         BUG_ON(err);
1450         return err;
1451 }
1452
1453 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
1454                          struct btrfs_root *root)
1455 {
1456         finish_current_insert(trans, root->fs_info->extent_root);
1457         del_pending_extents(trans, root->fs_info->extent_root);
1458         return 0;
1459 }
1460
1461 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
1462                              struct btrfs_root *root, u64 bytenr,
1463                              u64 offset, int metadata, u64 *refs, u64 *flags)
1464 {
1465         struct btrfs_path *path;
1466         int ret;
1467         struct btrfs_key key;
1468         struct extent_buffer *l;
1469         struct btrfs_extent_item *item;
1470         u32 item_size;
1471         u64 num_refs;
1472         u64 extent_flags;
1473
1474         if (metadata &&
1475             !btrfs_fs_incompat(root->fs_info,
1476                                BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA)) {
1477                 offset = root->leafsize;
1478                 metadata = 0;
1479         }
1480
1481         path = btrfs_alloc_path();
1482         path->reada = 1;
1483
1484         key.objectid = bytenr;
1485         key.offset = offset;
1486         if (metadata)
1487                 key.type = BTRFS_METADATA_ITEM_KEY;
1488         else
1489                 key.type = BTRFS_EXTENT_ITEM_KEY;
1490
1491 again:
1492         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1493                                 0, 0);
1494         if (ret < 0)
1495                 goto out;
1496
1497         /*
1498          * Deal with the fact that we may have mixed SKINNY and normal refs.  If
1499          * we didn't find what we wanted check and see if we have a normal ref
1500          * right next to us, or re-search if we are on the edge of the leaf just
1501          * to make sure.
1502          */
1503         if (ret > 0 && metadata) {
1504                 if (path->slots) {
1505                         path->slots[0]--;
1506                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1507                                               path->slots[0]);
1508                         if (key.objectid == bytenr &&
1509                             key.type == BTRFS_METADATA_ITEM_KEY)
1510                                 ret = 0;
1511                 }
1512
1513                 if (ret) {
1514                         btrfs_release_path(root, path);
1515                         key.type = BTRFS_EXTENT_ITEM_KEY;
1516                         key.offset = root->leafsize;
1517                         metadata = 0;
1518                         goto again;
1519                 }
1520         }
1521
1522         if (ret != 0) {
1523                 ret = -EIO;
1524                 goto out;
1525         }
1526
1527         l = path->nodes[0];
1528         item_size = btrfs_item_size_nr(l, path->slots[0]);
1529         if (item_size >= sizeof(*item)) {
1530                 item = btrfs_item_ptr(l, path->slots[0],
1531                                       struct btrfs_extent_item);
1532                 num_refs = btrfs_extent_refs(l, item);
1533                 extent_flags = btrfs_extent_flags(l, item);
1534         } else {
1535 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1536                         struct btrfs_extent_item_v0 *ei0;
1537                         BUG_ON(item_size != sizeof(*ei0));
1538                         ei0 = btrfs_item_ptr(l, path->slots[0],
1539                                              struct btrfs_extent_item_v0);
1540                         num_refs = btrfs_extent_refs_v0(l, ei0);
1541                         /* FIXME: this isn't correct for data */
1542                         extent_flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
1543 #else
1544                         BUG();
1545 #endif
1546         }
1547         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1548         if (refs)
1549                 *refs = num_refs;
1550         if (flags)
1551                 *flags = extent_flags;
1552 out:
1553         btrfs_free_path(path);
1554         return 0;
1555 }
1556
1557 int btrfs_set_block_flags(struct btrfs_trans_handle *trans,
1558                           struct btrfs_root *root,
1559                           u64 bytenr, int level, u64 flags)
1560 {
1561         struct btrfs_path *path;
1562         int ret;
1563         struct btrfs_key key;
1564         struct extent_buffer *l;
1565         struct btrfs_extent_item *item;
1566         u32 item_size;
1567         int skinny_metadata =
1568                 btrfs_fs_incompat(root->fs_info,
1569                                   BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
1570
1571         path = btrfs_alloc_path();
1572         path->reada = 1;
1573
1574         key.objectid = bytenr;
1575         if (skinny_metadata) {
1576                 key.offset = level;
1577                 key.type = BTRFS_METADATA_ITEM_KEY;
1578         } else {
1579                 key.offset = root->leafsize;
1580                 key.type = BTRFS_EXTENT_ITEM_KEY;
1581         }
1582
1583 again:
1584         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
1585                                 0, 0);
1586         if (ret < 0)
1587                 goto out;
1588
1589         if (ret > 0 && skinny_metadata) {
1590                 skinny_metadata = 0;
1591                 if (path->slots[0]--) {
1592                         path->slots[0]--;
1593                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1594                                               path->slots[0]);
1595                         if (key.objectid == bytenr &&
1596                             key.offset == root->leafsize &&
1597                             key.type == BTRFS_EXTENT_ITEM_KEY)
1598                                 ret = 0;
1599                 }
1600                 if (ret) {
1601                         btrfs_release_path(root, path);
1602                         key.offset = root->leafsize;
1603                         key.type = BTRFS_EXTENT_ITEM_KEY;
1604                         goto again;
1605                 }
1606         }
1607
1608         if (ret != 0) {
1609                 btrfs_print_leaf(root, path->nodes[0]);
1610                 printk("failed to find block number %Lu\n",
1611                         (unsigned long long)bytenr);
1612                 BUG();
1613         }
1614         l = path->nodes[0];
1615         item_size = btrfs_item_size_nr(l, path->slots[0]);
1616 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1617         if (item_size < sizeof(*item)) {
1618                 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1619                                              path, (u64)-1, 0);
1620                 if (ret < 0)
1621                         goto out;
1622
1623                 l = path->nodes[0];
1624                 item_size = btrfs_item_size_nr(l, path->slots[0]);
1625         }
1626 #endif
1627         BUG_ON(item_size < sizeof(*item));
1628         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
1629         flags |= btrfs_extent_flags(l, item);
1630         btrfs_set_extent_flags(l, item, flags);
1631 out:
1632         btrfs_free_path(path);
1633         finish_current_insert(trans, root->fs_info->extent_root);
1634         del_pending_extents(trans, root->fs_info->extent_root);
1635         return ret;
1636 }
1637
1638 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
1639                            struct btrfs_root *root,
1640                            struct extent_buffer *buf,
1641                            int record_parent, int inc)
1642 {
1643         u64 bytenr;
1644         u64 num_bytes;
1645         u64 parent;
1646         u64 ref_root;
1647         u32 nritems;
1648         struct btrfs_key key;
1649         struct btrfs_file_extent_item *fi;
1650         int i;
1651         int level;
1652         int ret = 0;
1653         int (*process_func)(struct btrfs_trans_handle *trans,
1654                             struct btrfs_root *root,
1655                             u64, u64, u64, u64, u64, u64);
1656
1657         ref_root = btrfs_header_owner(buf);
1658         nritems = btrfs_header_nritems(buf);
1659         level = btrfs_header_level(buf);
1660
1661         if (!root->ref_cows && level == 0)
1662                 return 0;
1663
1664         if (inc)
1665                 process_func = btrfs_inc_extent_ref;
1666         else
1667                 process_func = btrfs_free_extent;
1668
1669         if (record_parent)
1670                 parent = buf->start;
1671         else
1672                 parent = 0;
1673
1674         for (i = 0; i < nritems; i++) {
1675                 cond_resched();
1676                 if (level == 0) {
1677                         btrfs_item_key_to_cpu(buf, &key, i);
1678                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1679                                 continue;
1680                         fi = btrfs_item_ptr(buf, i,
1681                                             struct btrfs_file_extent_item);
1682                         if (btrfs_file_extent_type(buf, fi) ==
1683                             BTRFS_FILE_EXTENT_INLINE)
1684                                 continue;
1685                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1686                         if (bytenr == 0)
1687                                 continue;
1688
1689                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
1690                         key.offset -= btrfs_file_extent_offset(buf, fi);
1691                         ret = process_func(trans, root, bytenr, num_bytes,
1692                                            parent, ref_root, key.objectid,
1693                                            key.offset);
1694                         if (ret) {
1695                                 WARN_ON(1);
1696                                 goto fail;
1697                         }
1698                 } else {
1699                         bytenr = btrfs_node_blockptr(buf, i);
1700                         num_bytes = btrfs_level_size(root, level - 1);
1701                         ret = process_func(trans, root, bytenr, num_bytes,
1702                                            parent, ref_root, level - 1, 0);
1703                         if (ret) {
1704                                 WARN_ON(1);
1705                                 goto fail;
1706                         }
1707                 }
1708         }
1709         return 0;
1710 fail:
1711         WARN_ON(1);
1712         return ret;
1713 }
1714
1715 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1716                   struct extent_buffer *buf, int record_parent)
1717 {
1718         return __btrfs_mod_ref(trans, root, buf, record_parent, 1);
1719 }
1720
1721 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1722                   struct extent_buffer *buf, int record_parent)
1723 {
1724         return __btrfs_mod_ref(trans, root, buf, record_parent, 0);
1725 }
1726
1727 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1728                                  struct btrfs_root *root,
1729                                  struct btrfs_path *path,
1730                                  struct btrfs_block_group_cache *cache)
1731 {
1732         int ret;
1733         int pending_ret;
1734         struct btrfs_root *extent_root = root->fs_info->extent_root;
1735         unsigned long bi;
1736         struct extent_buffer *leaf;
1737
1738         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1739         if (ret < 0)
1740                 goto fail;
1741         BUG_ON(ret);
1742
1743         leaf = path->nodes[0];
1744         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1745         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1746         btrfs_mark_buffer_dirty(leaf);
1747         btrfs_release_path(extent_root, path);
1748 fail:
1749         finish_current_insert(trans, extent_root);
1750         pending_ret = del_pending_extents(trans, extent_root);
1751         if (ret)
1752                 return ret;
1753         if (pending_ret)
1754                 return pending_ret;
1755         return 0;
1756
1757 }
1758
1759 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1760                                    struct btrfs_root *root)
1761 {
1762         struct extent_io_tree *block_group_cache;
1763         struct btrfs_block_group_cache *cache;
1764         int ret;
1765         struct btrfs_path *path;
1766         u64 last = 0;
1767         u64 start;
1768         u64 end;
1769         u64 ptr;
1770
1771         block_group_cache = &root->fs_info->block_group_cache;
1772         path = btrfs_alloc_path();
1773         if (!path)
1774                 return -ENOMEM;
1775
1776         while(1) {
1777                 ret = find_first_extent_bit(block_group_cache, last,
1778                                             &start, &end, BLOCK_GROUP_DIRTY);
1779                 if (ret) {
1780                         if (last == 0)
1781                                 break;
1782                         last = 0;
1783                         continue;
1784                 }
1785
1786                 last = end + 1;
1787                 ret = get_state_private(block_group_cache, start, &ptr);
1788                 BUG_ON(ret);
1789
1790                 clear_extent_bits(block_group_cache, start, end,
1791                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
1792
1793                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
1794                 ret = write_one_cache_group(trans, root, path, cache);
1795         }
1796         btrfs_free_path(path);
1797         return 0;
1798 }
1799
1800 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1801                                                   u64 flags)
1802 {
1803         struct list_head *head = &info->space_info;
1804         struct list_head *cur;
1805         struct btrfs_space_info *found;
1806         list_for_each(cur, head) {
1807                 found = list_entry(cur, struct btrfs_space_info, list);
1808                 if (found->flags & flags)
1809                         return found;
1810         }
1811         return NULL;
1812
1813 }
1814
1815 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1816                              u64 total_bytes, u64 bytes_used,
1817                              struct btrfs_space_info **space_info)
1818 {
1819         struct btrfs_space_info *found;
1820
1821         found = __find_space_info(info, flags);
1822         if (found) {
1823                 found->total_bytes += total_bytes;
1824                 found->bytes_used += bytes_used;
1825                 if (found->total_bytes < found->bytes_used) {
1826                         fprintf(stderr, "warning, bad space info total_bytes "
1827                                 "%llu used %llu\n",
1828                                (unsigned long long)found->total_bytes,
1829                                (unsigned long long)found->bytes_used);
1830                 }
1831                 *space_info = found;
1832                 return 0;
1833         }
1834         found = kmalloc(sizeof(*found), GFP_NOFS);
1835         if (!found)
1836                 return -ENOMEM;
1837
1838         list_add(&found->list, &info->space_info);
1839         found->flags = flags;
1840         found->total_bytes = total_bytes;
1841         found->bytes_used = bytes_used;
1842         found->bytes_pinned = 0;
1843         found->full = 0;
1844         *space_info = found;
1845         return 0;
1846 }
1847
1848
1849 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1850 {
1851         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1852                                    BTRFS_BLOCK_GROUP_RAID1 |
1853                                    BTRFS_BLOCK_GROUP_RAID10 |
1854                                    BTRFS_BLOCK_GROUP_RAID5 |
1855                                    BTRFS_BLOCK_GROUP_RAID6 |
1856                                    BTRFS_BLOCK_GROUP_DUP);
1857         if (extra_flags) {
1858                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1859                         fs_info->avail_data_alloc_bits |= extra_flags;
1860                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1861                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1862                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1863                         fs_info->avail_system_alloc_bits |= extra_flags;
1864         }
1865 }
1866
1867 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1868                           struct btrfs_root *extent_root, u64 alloc_bytes,
1869                           u64 flags)
1870 {
1871         struct btrfs_space_info *space_info;
1872         u64 thresh;
1873         u64 start;
1874         u64 num_bytes;
1875         int ret;
1876
1877         space_info = __find_space_info(extent_root->fs_info, flags);
1878         if (!space_info) {
1879                 ret = update_space_info(extent_root->fs_info, flags,
1880                                         0, 0, &space_info);
1881                 BUG_ON(ret);
1882         }
1883         BUG_ON(!space_info);
1884
1885         if (space_info->full)
1886                 return 0;
1887
1888         thresh = div_factor(space_info->total_bytes, 7);
1889         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1890             thresh)
1891                 return 0;
1892
1893         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes,
1894                                 space_info->flags);
1895         if (ret == -ENOSPC) {
1896                 space_info->full = 1;
1897                 return 0;
1898         }
1899
1900         BUG_ON(ret);
1901
1902         ret = btrfs_make_block_group(trans, extent_root, 0, space_info->flags,
1903                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1904         BUG_ON(ret);
1905         return 0;
1906 }
1907
1908 static int update_block_group(struct btrfs_trans_handle *trans,
1909                               struct btrfs_root *root,
1910                               u64 bytenr, u64 num_bytes, int alloc,
1911                               int mark_free)
1912 {
1913         struct btrfs_block_group_cache *cache;
1914         struct btrfs_fs_info *info = root->fs_info;
1915         u64 total = num_bytes;
1916         u64 old_val;
1917         u64 byte_in_group;
1918         u64 start;
1919         u64 end;
1920
1921         /* block accounting for super block */
1922         old_val = btrfs_super_bytes_used(info->super_copy);
1923         if (alloc)
1924                 old_val += num_bytes;
1925         else
1926                 old_val -= num_bytes;
1927         btrfs_set_super_bytes_used(info->super_copy, old_val);
1928
1929         /* block accounting for root item */
1930         old_val = btrfs_root_used(&root->root_item);
1931         if (alloc)
1932                 old_val += num_bytes;
1933         else
1934                 old_val -= num_bytes;
1935         btrfs_set_root_used(&root->root_item, old_val);
1936
1937         while(total) {
1938                 cache = btrfs_lookup_block_group(info, bytenr);
1939                 if (!cache) {
1940                         return -1;
1941                 }
1942                 byte_in_group = bytenr - cache->key.objectid;
1943                 WARN_ON(byte_in_group > cache->key.offset);
1944                 start = cache->key.objectid;
1945                 end = start + cache->key.offset - 1;
1946                 set_extent_bits(&info->block_group_cache, start, end,
1947                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1948
1949                 old_val = btrfs_block_group_used(&cache->item);
1950                 num_bytes = min(total, cache->key.offset - byte_in_group);
1951
1952                 if (alloc) {
1953                         old_val += num_bytes;
1954                         cache->space_info->bytes_used += num_bytes;
1955                 } else {
1956                         old_val -= num_bytes;
1957                         cache->space_info->bytes_used -= num_bytes;
1958                         if (mark_free) {
1959                                 set_extent_dirty(&info->free_space_cache,
1960                                                  bytenr, bytenr + num_bytes - 1,
1961                                                  GFP_NOFS);
1962                         }
1963                 }
1964                 btrfs_set_block_group_used(&cache->item, old_val);
1965                 total -= num_bytes;
1966                 bytenr += num_bytes;
1967         }
1968         return 0;
1969 }
1970
1971 static int update_pinned_extents(struct btrfs_root *root,
1972                                 u64 bytenr, u64 num, int pin)
1973 {
1974         u64 len;
1975         struct btrfs_block_group_cache *cache;
1976         struct btrfs_fs_info *fs_info = root->fs_info;
1977
1978         if (pin) {
1979                 set_extent_dirty(&fs_info->pinned_extents,
1980                                 bytenr, bytenr + num - 1, GFP_NOFS);
1981         } else {
1982                 clear_extent_dirty(&fs_info->pinned_extents,
1983                                 bytenr, bytenr + num - 1, GFP_NOFS);
1984         }
1985         while (num > 0) {
1986                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1987                 if (!cache) {
1988                         len = min((u64)root->sectorsize, num);
1989                         goto next;
1990                 }
1991                 WARN_ON(!cache);
1992                 len = min(num, cache->key.offset -
1993                           (bytenr - cache->key.objectid));
1994                 if (pin) {
1995                         cache->pinned += len;
1996                         cache->space_info->bytes_pinned += len;
1997                         fs_info->total_pinned += len;
1998                 } else {
1999                         cache->pinned -= len;
2000                         cache->space_info->bytes_pinned -= len;
2001                         fs_info->total_pinned -= len;
2002                 }
2003 next:
2004                 bytenr += len;
2005                 num -= len;
2006         }
2007         return 0;
2008 }
2009
2010 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
2011 {
2012         u64 last = 0;
2013         u64 start;
2014         u64 end;
2015         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
2016         int ret;
2017
2018         while(1) {
2019                 ret = find_first_extent_bit(pinned_extents, last,
2020                                             &start, &end, EXTENT_DIRTY);
2021                 if (ret)
2022                         break;
2023                 set_extent_dirty(copy, start, end, GFP_NOFS);
2024                 last = end + 1;
2025         }
2026         return 0;
2027 }
2028
2029 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
2030                                struct btrfs_root *root,
2031                                struct extent_io_tree *unpin)
2032 {
2033         u64 start;
2034         u64 end;
2035         int ret;
2036         struct extent_io_tree *free_space_cache;
2037         free_space_cache = &root->fs_info->free_space_cache;
2038
2039         while(1) {
2040                 ret = find_first_extent_bit(unpin, 0, &start, &end,
2041                                             EXTENT_DIRTY);
2042                 if (ret)
2043                         break;
2044                 update_pinned_extents(root, start, end + 1 - start, 0);
2045                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
2046                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
2047         }
2048         return 0;
2049 }
2050
2051 static int extent_root_pending_ops(struct btrfs_fs_info *info)
2052 {
2053         u64 start;
2054         u64 end;
2055         int ret;
2056
2057         ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2058                                     &end, EXTENT_LOCKED);
2059         if (!ret) {
2060                 ret = find_first_extent_bit(&info->pending_del, 0, &start, &end,
2061                                             EXTENT_LOCKED);
2062         }
2063         return ret == 0;
2064
2065 }
2066 static int finish_current_insert(struct btrfs_trans_handle *trans,
2067                                  struct btrfs_root *extent_root)
2068 {
2069         u64 start;
2070         u64 end;
2071         u64 priv;
2072         struct btrfs_fs_info *info = extent_root->fs_info;
2073         struct btrfs_path *path;
2074         struct pending_extent_op *extent_op;
2075         struct btrfs_key key;
2076         int ret;
2077         int skinny_metadata =
2078                 btrfs_fs_incompat(extent_root->fs_info,
2079                                   BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
2080
2081         path = btrfs_alloc_path();
2082
2083         while(1) {
2084                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
2085                                             &end, EXTENT_LOCKED);
2086                 if (ret)
2087                         break;
2088
2089                 ret = get_state_private(&info->extent_ins, start, &priv);
2090                 BUG_ON(ret);
2091                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2092
2093                 if (extent_op->type == PENDING_EXTENT_INSERT) {
2094                         key.objectid = start;
2095                         if (skinny_metadata) {
2096                                 key.offset = extent_op->level;
2097                                 key.type = BTRFS_METADATA_ITEM_KEY;
2098                         } else {
2099                                 key.offset = extent_op->num_bytes;
2100                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2101                         }
2102                         ret = alloc_reserved_tree_block(trans, extent_root,
2103                                                 extent_root->root_key.objectid,
2104                                                 trans->transid,
2105                                                 extent_op->flags,
2106                                                 &extent_op->key,
2107                                                 extent_op->level, &key);
2108                 } else {
2109                         BUG_ON(1);
2110                 }
2111
2112                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
2113                                   GFP_NOFS);
2114                 kfree(extent_op);
2115         }
2116         btrfs_free_path(path);
2117         return 0;
2118 }
2119
2120 static int pin_down_bytes(struct btrfs_trans_handle *trans,
2121                           struct btrfs_root *root,
2122                           u64 bytenr, u64 num_bytes, int is_data)
2123 {
2124         int err = 0;
2125         struct extent_buffer *buf;
2126
2127         if (is_data)
2128                 goto pinit;
2129
2130         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
2131         if (!buf)
2132                 goto pinit;
2133
2134         /* we can reuse a block if it hasn't been written
2135          * and it is from this transaction.  We can't
2136          * reuse anything from the tree log root because
2137          * it has tiny sub-transactions.
2138          */
2139         if (btrfs_buffer_uptodate(buf, 0)) {
2140                 u64 header_owner = btrfs_header_owner(buf);
2141                 u64 header_transid = btrfs_header_generation(buf);
2142                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
2143                     header_transid == trans->transid &&
2144                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
2145                         clean_tree_block(NULL, root, buf);
2146                         free_extent_buffer(buf);
2147                         return 1;
2148                 }
2149         }
2150         free_extent_buffer(buf);
2151 pinit:
2152         update_pinned_extents(root, bytenr, num_bytes, 1);
2153
2154         BUG_ON(err < 0);
2155         return 0;
2156 }
2157
2158 void btrfs_pin_extent(struct btrfs_fs_info *fs_info,
2159                        u64 bytenr, u64 num_bytes)
2160 {
2161         update_pinned_extents(fs_info->extent_root, bytenr, num_bytes, 1);
2162 }
2163
2164 void btrfs_unpin_extent(struct btrfs_fs_info *fs_info,
2165                         u64 bytenr, u64 num_bytes)
2166 {
2167         update_pinned_extents(fs_info->extent_root, bytenr, num_bytes, 0);
2168 }
2169
2170 /*
2171  * remove an extent from the root, returns 0 on success
2172  */
2173 static int __free_extent(struct btrfs_trans_handle *trans,
2174                          struct btrfs_root *root,
2175                          u64 bytenr, u64 num_bytes, u64 parent,
2176                          u64 root_objectid, u64 owner_objectid,
2177                          u64 owner_offset, int refs_to_drop)
2178 {
2179
2180         struct btrfs_key key;
2181         struct btrfs_path *path;
2182         struct btrfs_extent_ops *ops = root->fs_info->extent_ops;
2183         struct btrfs_root *extent_root = root->fs_info->extent_root;
2184         struct extent_buffer *leaf;
2185         struct btrfs_extent_item *ei;
2186         struct btrfs_extent_inline_ref *iref;
2187         int ret;
2188         int is_data;
2189         int extent_slot = 0;
2190         int found_extent = 0;
2191         int num_to_del = 1;
2192         u32 item_size;
2193         u64 refs;
2194         int skinny_metadata =
2195                 btrfs_fs_incompat(extent_root->fs_info,
2196                                   BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
2197
2198         if (root->fs_info->free_extent_hook) {
2199                 root->fs_info->free_extent_hook(trans, root, bytenr, num_bytes,
2200                                                 parent, root_objectid, owner_objectid,
2201                                                 owner_offset, refs_to_drop);
2202
2203         }
2204         path = btrfs_alloc_path();
2205         if (!path)
2206                 return -ENOMEM;
2207
2208         path->reada = 1;
2209         path->leave_spinning = 1;
2210
2211         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
2212         if (is_data)
2213                 skinny_metadata = 0;
2214         BUG_ON(!is_data && refs_to_drop != 1);
2215
2216         ret = lookup_extent_backref(trans, extent_root, path, &iref,
2217                                     bytenr, num_bytes, parent,
2218                                     root_objectid, owner_objectid,
2219                                     owner_offset);
2220         if (ret == 0) {
2221                 extent_slot = path->slots[0];
2222                 while (extent_slot >= 0) {
2223                         btrfs_item_key_to_cpu(path->nodes[0], &key,
2224                                               extent_slot);
2225                         if (key.objectid != bytenr)
2226                                 break;
2227                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
2228                             key.offset == num_bytes) {
2229                                 found_extent = 1;
2230                                 break;
2231                         }
2232                         if (key.type == BTRFS_METADATA_ITEM_KEY &&
2233                             key.offset == owner_objectid) {
2234                                 found_extent = 1;
2235                                 break;
2236                         }
2237                         if (path->slots[0] - extent_slot > 5)
2238                                 break;
2239                         extent_slot--;
2240                 }
2241 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2242                 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
2243                 if (found_extent && item_size < sizeof(*ei))
2244                         found_extent = 0;
2245 #endif
2246                 if (!found_extent) {
2247                         BUG_ON(iref);
2248                         ret = remove_extent_backref(trans, extent_root, path,
2249                                                     NULL, refs_to_drop,
2250                                                     is_data);
2251                         BUG_ON(ret);
2252                         btrfs_release_path(extent_root, path);
2253                         path->leave_spinning = 1;
2254
2255                         key.objectid = bytenr;
2256
2257                         if (skinny_metadata) {
2258                                 key.type = BTRFS_METADATA_ITEM_KEY;
2259                                 key.offset = owner_objectid;
2260                         } else {
2261                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2262                                 key.offset = num_bytes;
2263                         }
2264
2265                         ret = btrfs_search_slot(trans, extent_root,
2266                                                 &key, path, -1, 1);
2267                         if (ret > 0 && skinny_metadata && path->slots[0]) {
2268                                 path->slots[0]--;
2269                                 btrfs_item_key_to_cpu(path->nodes[0],
2270                                                       &key,
2271                                                       path->slots[0]);
2272                                 if (key.objectid == bytenr &&
2273                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
2274                                     key.offset == num_bytes)
2275                                         ret = 0;
2276                         }
2277
2278                         if (ret > 0 && skinny_metadata) {
2279                                 skinny_metadata = 0;
2280                                 btrfs_release_path(extent_root, path);
2281                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2282                                 key.offset = num_bytes;
2283                                 ret = btrfs_search_slot(trans, extent_root,
2284                                                         &key, path, -1, 1);
2285                         }
2286
2287                         if (ret) {
2288                                 printk(KERN_ERR "umm, got %d back from search"
2289                                        ", was looking for %llu\n", ret,
2290                                        (unsigned long long)bytenr);
2291                                 btrfs_print_leaf(extent_root, path->nodes[0]);
2292                         }
2293                         BUG_ON(ret);
2294                         extent_slot = path->slots[0];
2295                 }
2296         } else {
2297                 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
2298                        "parent %llu root %llu  owner %llu offset %llu\n",
2299                        (unsigned long long)bytenr,
2300                        (unsigned long long)parent,
2301                        (unsigned long long)root_objectid,
2302                        (unsigned long long)owner_objectid,
2303                        (unsigned long long)owner_offset);
2304                 ret = -EIO;
2305                 goto fail;
2306         }
2307
2308         leaf = path->nodes[0];
2309         item_size = btrfs_item_size_nr(leaf, extent_slot);
2310 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2311         if (item_size < sizeof(*ei)) {
2312                 BUG_ON(found_extent || extent_slot != path->slots[0]);
2313                 ret = convert_extent_item_v0(trans, extent_root, path,
2314                                              owner_objectid, 0);
2315                 BUG_ON(ret < 0);
2316
2317                 btrfs_release_path(extent_root, path);
2318                 path->leave_spinning = 1;
2319
2320                 key.objectid = bytenr;
2321                 key.type = BTRFS_EXTENT_ITEM_KEY;
2322                 key.offset = num_bytes;
2323
2324                 ret = btrfs_search_slot(trans, extent_root, &key, path,
2325                                         -1, 1);
2326                 if (ret) {
2327                         printk(KERN_ERR "umm, got %d back from search"
2328                                ", was looking for %llu\n", ret,
2329                                (unsigned long long)bytenr);
2330                         btrfs_print_leaf(extent_root, path->nodes[0]);
2331                 }
2332                 BUG_ON(ret);
2333                 extent_slot = path->slots[0];
2334                 leaf = path->nodes[0];
2335                 item_size = btrfs_item_size_nr(leaf, extent_slot);
2336         }
2337 #endif
2338         BUG_ON(item_size < sizeof(*ei));
2339         ei = btrfs_item_ptr(leaf, extent_slot,
2340                             struct btrfs_extent_item);
2341         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
2342             key.type == BTRFS_EXTENT_ITEM_KEY) {
2343                 struct btrfs_tree_block_info *bi;
2344                 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
2345                 bi = (struct btrfs_tree_block_info *)(ei + 1);
2346                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
2347         }
2348
2349         refs = btrfs_extent_refs(leaf, ei);
2350         BUG_ON(refs < refs_to_drop);
2351         refs -= refs_to_drop;
2352
2353         if (refs > 0) {
2354                 /*
2355                  * In the case of inline back ref, reference count will
2356                  * be updated by remove_extent_backref
2357                  */
2358                 if (iref) {
2359                         BUG_ON(!found_extent);
2360                 } else {
2361                         btrfs_set_extent_refs(leaf, ei, refs);
2362                         btrfs_mark_buffer_dirty(leaf);
2363                 }
2364                 if (found_extent) {
2365                         ret = remove_extent_backref(trans, extent_root, path,
2366                                                     iref, refs_to_drop,
2367                                                     is_data);
2368                         BUG_ON(ret);
2369                 }
2370         } else {
2371                 int mark_free = 0;
2372                 int pin = 1;
2373
2374                 if (found_extent) {
2375                         BUG_ON(is_data && refs_to_drop !=
2376                                extent_data_ref_count(root, path, iref));
2377                         if (iref) {
2378                                 BUG_ON(path->slots[0] != extent_slot);
2379                         } else {
2380                                 BUG_ON(path->slots[0] != extent_slot + 1);
2381                                 path->slots[0] = extent_slot;
2382                                 num_to_del = 2;
2383                         }
2384                 }
2385
2386                 if (ops && ops->free_extent) {
2387                         ret = ops->free_extent(root, bytenr, num_bytes);
2388                         if (ret > 0) {
2389                                 pin = 0;
2390                                 mark_free = 0;
2391                         }
2392                 }
2393
2394                 if (pin) {
2395                         ret = pin_down_bytes(trans, root, bytenr, num_bytes,
2396                                              is_data);
2397                         if (ret > 0)
2398                                 mark_free = 1;
2399                         BUG_ON(ret < 0);
2400                 }
2401
2402                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2403                                       num_to_del);
2404                 BUG_ON(ret);
2405                 btrfs_release_path(extent_root, path);
2406
2407                 if (is_data) {
2408                         ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
2409                         BUG_ON(ret);
2410                 }
2411
2412                 update_block_group(trans, root, bytenr, num_bytes, 0, mark_free);
2413         }
2414 fail:
2415         btrfs_free_path(path);
2416         finish_current_insert(trans, extent_root);
2417         return ret;
2418 }
2419
2420 /*
2421  * find all the blocks marked as pending in the radix tree and remove
2422  * them from the extent map
2423  */
2424 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
2425                                btrfs_root *extent_root)
2426 {
2427         int ret;
2428         int err = 0;
2429         u64 start;
2430         u64 end;
2431         u64 priv;
2432         struct extent_io_tree *pending_del;
2433         struct extent_io_tree *extent_ins;
2434         struct pending_extent_op *extent_op;
2435
2436         extent_ins = &extent_root->fs_info->extent_ins;
2437         pending_del = &extent_root->fs_info->pending_del;
2438
2439         while(1) {
2440                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
2441                                             EXTENT_LOCKED);
2442                 if (ret)
2443                         break;
2444
2445                 ret = get_state_private(pending_del, start, &priv);
2446                 BUG_ON(ret);
2447                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2448
2449                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
2450                                   GFP_NOFS);
2451
2452                 if (!test_range_bit(extent_ins, start, end,
2453                                     EXTENT_LOCKED, 0)) {
2454                         ret = __free_extent(trans, extent_root,
2455                                             start, end + 1 - start, 0,
2456                                             extent_root->root_key.objectid,
2457                                             extent_op->level, 0, 1);
2458                         kfree(extent_op);
2459                 } else {
2460                         kfree(extent_op);
2461                         ret = get_state_private(extent_ins, start, &priv);
2462                         BUG_ON(ret);
2463                         extent_op = (struct pending_extent_op *)
2464                                                         (unsigned long)priv;
2465
2466                         clear_extent_bits(extent_ins, start, end,
2467                                           EXTENT_LOCKED, GFP_NOFS);
2468
2469                         if (extent_op->type == PENDING_BACKREF_UPDATE)
2470                                 BUG_ON(1);
2471
2472                         kfree(extent_op);
2473                 }
2474                 if (ret)
2475                         err = ret;
2476         }
2477         return err;
2478 }
2479
2480 /*
2481  * remove an extent from the root, returns 0 on success
2482  */
2483
2484 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2485                       struct btrfs_root *root,
2486                       u64 bytenr, u64 num_bytes, u64 parent,
2487                       u64 root_objectid, u64 owner, u64 offset)
2488 {
2489         struct btrfs_root *extent_root = root->fs_info->extent_root;
2490         int pending_ret;
2491         int ret;
2492
2493         WARN_ON(num_bytes < root->sectorsize);
2494         if (root == extent_root) {
2495                 struct pending_extent_op *extent_op;
2496
2497                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2498                 BUG_ON(!extent_op);
2499
2500                 extent_op->type = PENDING_EXTENT_DELETE;
2501                 extent_op->bytenr = bytenr;
2502                 extent_op->num_bytes = num_bytes;
2503                 extent_op->level = (int)owner;
2504
2505                 set_extent_bits(&root->fs_info->pending_del,
2506                                 bytenr, bytenr + num_bytes - 1,
2507                                 EXTENT_LOCKED, GFP_NOFS);
2508                 set_state_private(&root->fs_info->pending_del,
2509                                   bytenr, (unsigned long)extent_op);
2510                 return 0;
2511         }
2512         ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2513                             root_objectid, owner, offset, 1);
2514         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2515         return ret ? ret : pending_ret;
2516 }
2517
2518 static u64 stripe_align(struct btrfs_root *root, u64 val)
2519 {
2520         u64 mask = ((u64)root->stripesize - 1);
2521         u64 ret = (val + mask) & ~mask;
2522         return ret;
2523 }
2524
2525 /*
2526  * walks the btree of allocated extents and find a hole of a given size.
2527  * The key ins is changed to record the hole:
2528  * ins->objectid == block start
2529  * ins->flags = BTRFS_EXTENT_ITEM_KEY
2530  * ins->offset == number of blocks
2531  * Any available blocks before search_start are skipped.
2532  */
2533 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
2534                                      struct btrfs_root *orig_root,
2535                                      u64 num_bytes, u64 empty_size,
2536                                      u64 search_start, u64 search_end,
2537                                      u64 hint_byte, struct btrfs_key *ins,
2538                                      u64 exclude_start, u64 exclude_nr,
2539                                      int data)
2540 {
2541         int ret;
2542         u64 orig_search_start = search_start;
2543         struct btrfs_root * root = orig_root->fs_info->extent_root;
2544         struct btrfs_fs_info *info = root->fs_info;
2545         u64 total_needed = num_bytes;
2546         struct btrfs_block_group_cache *block_group;
2547         int full_scan = 0;
2548         int wrapped = 0;
2549
2550         WARN_ON(num_bytes < root->sectorsize);
2551         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
2552
2553         search_start = stripe_align(root, search_start);
2554
2555         if (hint_byte) {
2556                 block_group = btrfs_lookup_first_block_group(info, hint_byte);
2557                 if (!block_group)
2558                         hint_byte = search_start;
2559                 block_group = btrfs_find_block_group(root, block_group,
2560                                                      hint_byte, data, 1);
2561         } else {
2562                 block_group = btrfs_find_block_group(root,
2563                                                      trans->block_group,
2564                                                      search_start, data, 1);
2565         }
2566
2567         total_needed += empty_size;
2568
2569 check_failed:
2570         search_start = stripe_align(root, search_start);
2571         if (!block_group) {
2572                 block_group = btrfs_lookup_first_block_group(info,
2573                                                              search_start);
2574                 if (!block_group)
2575                         block_group = btrfs_lookup_first_block_group(info,
2576                                                        orig_search_start);
2577         }
2578         ret = find_search_start(root, &block_group, &search_start,
2579                                 total_needed, data);
2580         if (ret)
2581                 goto new_group;
2582
2583         ins->objectid = search_start;
2584         ins->offset = num_bytes;
2585
2586         if (ins->objectid + num_bytes >
2587             block_group->key.objectid + block_group->key.offset) {
2588                 search_start = block_group->key.objectid +
2589                         block_group->key.offset;
2590                 goto new_group;
2591         }
2592
2593         if (test_range_bit(&info->extent_ins, ins->objectid,
2594                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
2595                 search_start = ins->objectid + num_bytes;
2596                 goto new_group;
2597         }
2598
2599         if (test_range_bit(&info->pinned_extents, ins->objectid,
2600                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
2601                 search_start = ins->objectid + num_bytes;
2602                 goto new_group;
2603         }
2604
2605         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2606             ins->objectid < exclude_start + exclude_nr)) {
2607                 search_start = exclude_start + exclude_nr;
2608                 goto new_group;
2609         }
2610
2611         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
2612                 block_group = btrfs_lookup_block_group(info, ins->objectid);
2613                 if (block_group)
2614                         trans->block_group = block_group;
2615         }
2616         ins->offset = num_bytes;
2617         return 0;
2618
2619 new_group:
2620         block_group = btrfs_lookup_first_block_group(info, search_start);
2621         if (!block_group) {
2622                 search_start = orig_search_start;
2623                 if (full_scan) {
2624                         ret = -ENOSPC;
2625                         goto error;
2626                 }
2627                 if (wrapped) {
2628                         if (!full_scan)
2629                                 total_needed -= empty_size;
2630                         full_scan = 1;
2631                 } else
2632                         wrapped = 1;
2633         }
2634         cond_resched();
2635         block_group = btrfs_find_block_group(root, block_group,
2636                                              search_start, data, 0);
2637         goto check_failed;
2638
2639 error:
2640         return ret;
2641 }
2642
2643 static int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2644                                 struct btrfs_root *root,
2645                                 u64 num_bytes, u64 empty_size,
2646                                 u64 hint_byte, u64 search_end,
2647                                 struct btrfs_key *ins, int data)
2648 {
2649         int ret;
2650         u64 search_start = 0;
2651         u64 alloc_profile;
2652         struct btrfs_fs_info *info = root->fs_info;
2653
2654         if (info->extent_ops) {
2655                 struct btrfs_extent_ops *ops = info->extent_ops;
2656                 ret = ops->alloc_extent(root, num_bytes, hint_byte, ins);
2657                 BUG_ON(ret);
2658                 goto found;
2659         }
2660
2661         if (data) {
2662                 alloc_profile = info->avail_data_alloc_bits &
2663                                 info->data_alloc_profile;
2664                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2665         } else if ((info->system_allocs > 0 || root == info->chunk_root) &&
2666                    info->system_allocs >= 0) {
2667                 alloc_profile = info->avail_system_alloc_bits &
2668                                 info->system_alloc_profile;
2669                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2670         } else {
2671                 alloc_profile = info->avail_metadata_alloc_bits &
2672                                 info->metadata_alloc_profile;
2673                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2674         }
2675
2676         if (root->ref_cows) {
2677                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2678                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2679                                              num_bytes,
2680                                              BTRFS_BLOCK_GROUP_METADATA);
2681                         BUG_ON(ret);
2682                 }
2683                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2684                                      num_bytes + 2 * 1024 * 1024, data);
2685                 BUG_ON(ret);
2686         }
2687
2688         WARN_ON(num_bytes < root->sectorsize);
2689         ret = find_free_extent(trans, root, num_bytes, empty_size,
2690                                search_start, search_end, hint_byte, ins,
2691                                trans->alloc_exclude_start,
2692                                trans->alloc_exclude_nr, data);
2693         BUG_ON(ret);
2694 found:
2695         clear_extent_dirty(&root->fs_info->free_space_cache,
2696                            ins->objectid, ins->objectid + ins->offset - 1,
2697                            GFP_NOFS);
2698         return ret;
2699 }
2700
2701 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
2702                                      struct btrfs_root *root,
2703                                      u64 root_objectid, u64 generation,
2704                                      u64 flags, struct btrfs_disk_key *key,
2705                                      int level, struct btrfs_key *ins)
2706 {
2707         int ret;
2708         struct btrfs_fs_info *fs_info = root->fs_info;
2709         struct btrfs_extent_item *extent_item;
2710         struct btrfs_tree_block_info *block_info;
2711         struct btrfs_extent_inline_ref *iref;
2712         struct btrfs_path *path;
2713         struct extent_buffer *leaf;
2714         u32 size = sizeof(*extent_item) + sizeof(*iref);
2715         int skinny_metadata =
2716                 btrfs_fs_incompat(fs_info,
2717                                   BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA);
2718
2719         if (!skinny_metadata)
2720                 size += sizeof(*block_info);
2721
2722         path = btrfs_alloc_path();
2723         BUG_ON(!path);
2724
2725         path->leave_spinning = 1;
2726         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
2727                                       ins, size);
2728         BUG_ON(ret);
2729
2730         leaf = path->nodes[0];
2731         extent_item = btrfs_item_ptr(leaf, path->slots[0],
2732                                      struct btrfs_extent_item);
2733         btrfs_set_extent_refs(leaf, extent_item, 1);
2734         btrfs_set_extent_generation(leaf, extent_item, generation);
2735         btrfs_set_extent_flags(leaf, extent_item,
2736                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
2737
2738         if (skinny_metadata) {
2739                 iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
2740         } else {
2741                 block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
2742                 btrfs_set_tree_block_key(leaf, block_info, key);
2743                 btrfs_set_tree_block_level(leaf, block_info, level);
2744                 iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
2745         }
2746
2747         btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY);
2748         btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
2749
2750         btrfs_mark_buffer_dirty(leaf);
2751         btrfs_free_path(path);
2752
2753         ret = update_block_group(trans, root, ins->objectid, root->leafsize,
2754                                  1, 0);
2755         return 0;
2756 }
2757
2758 static int alloc_tree_block(struct btrfs_trans_handle *trans,
2759                             struct btrfs_root *root, u64 num_bytes,
2760                             u64 root_objectid, u64 generation,
2761                             u64 flags, struct btrfs_disk_key *key,
2762                             int level, u64 empty_size, u64 hint_byte,
2763                             u64 search_end, struct btrfs_key *ins)
2764 {
2765         int ret;
2766         ret = btrfs_reserve_extent(trans, root, num_bytes, empty_size,
2767                                    hint_byte, search_end, ins, 0);
2768         BUG_ON(ret);
2769
2770         if (root_objectid == BTRFS_EXTENT_TREE_OBJECTID) {
2771                 struct pending_extent_op *extent_op;
2772
2773                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2774                 BUG_ON(!extent_op);
2775
2776                 extent_op->type = PENDING_EXTENT_INSERT;
2777                 extent_op->bytenr = ins->objectid;
2778                 extent_op->num_bytes = ins->offset;
2779                 extent_op->level = level;
2780                 extent_op->flags = flags;
2781                 memcpy(&extent_op->key, key, sizeof(*key));
2782
2783                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2784                                 ins->objectid + ins->offset - 1,
2785                                 EXTENT_LOCKED, GFP_NOFS);
2786                 set_state_private(&root->fs_info->extent_ins,
2787                                   ins->objectid, (unsigned long)extent_op);
2788         } else {
2789                 if (btrfs_fs_incompat(root->fs_info,
2790                                 BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA)) {
2791                         ins->offset = level;
2792                         ins->type = BTRFS_METADATA_ITEM_KEY;
2793                 }
2794                 ret = alloc_reserved_tree_block(trans, root, root_objectid,
2795                                                 generation, flags,
2796                                                 key, level, ins);
2797                 finish_current_insert(trans, root->fs_info->extent_root);
2798                 del_pending_extents(trans, root->fs_info->extent_root);
2799         }
2800         return ret;
2801 }
2802
2803 /*
2804  * helper function to allocate a block for a given tree
2805  * returns the tree buffer or NULL.
2806  */
2807 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2808                                         struct btrfs_root *root,
2809                                         u32 blocksize, u64 root_objectid,
2810                                         struct btrfs_disk_key *key, int level,
2811                                         u64 hint, u64 empty_size)
2812 {
2813         struct btrfs_key ins;
2814         int ret;
2815         struct extent_buffer *buf;
2816
2817         ret = alloc_tree_block(trans, root, blocksize, root_objectid,
2818                                trans->transid, 0, key, level,
2819                                empty_size, hint, (u64)-1, &ins);
2820         if (ret) {
2821                 BUG_ON(ret > 0);
2822                 return ERR_PTR(ret);
2823         }
2824
2825         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
2826         if (!buf) {
2827                 btrfs_free_extent(trans, root, ins.objectid, ins.offset,
2828                                   0, root->root_key.objectid, level, 0);
2829                 BUG_ON(1);
2830                 return ERR_PTR(-ENOMEM);
2831         }
2832         btrfs_set_buffer_uptodate(buf);
2833         trans->blocks_used++;
2834
2835         return buf;
2836 }
2837
2838 #if 0
2839
2840 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2841                                   struct btrfs_root *root,
2842                                   struct extent_buffer *leaf)
2843 {
2844         u64 leaf_owner;
2845         u64 leaf_generation;
2846         struct btrfs_key key;
2847         struct btrfs_file_extent_item *fi;
2848         int i;
2849         int nritems;
2850         int ret;
2851
2852         BUG_ON(!btrfs_is_leaf(leaf));
2853         nritems = btrfs_header_nritems(leaf);
2854         leaf_owner = btrfs_header_owner(leaf);
2855         leaf_generation = btrfs_header_generation(leaf);
2856
2857         for (i = 0; i < nritems; i++) {
2858                 u64 disk_bytenr;
2859
2860                 btrfs_item_key_to_cpu(leaf, &key, i);
2861                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2862                         continue;
2863                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2864                 if (btrfs_file_extent_type(leaf, fi) ==
2865                     BTRFS_FILE_EXTENT_INLINE)
2866                         continue;
2867                 /*
2868                  * FIXME make sure to insert a trans record that
2869                  * repeats the snapshot del on crash
2870                  */
2871                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2872                 if (disk_bytenr == 0)
2873                         continue;
2874                 ret = btrfs_free_extent(trans, root, disk_bytenr,
2875                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2876                                 leaf->start, leaf_owner, leaf_generation,
2877                                 key.objectid, 0);
2878                 BUG_ON(ret);
2879         }
2880         return 0;
2881 }
2882
2883 static void noinline reada_walk_down(struct btrfs_root *root,
2884                                      struct extent_buffer *node,
2885                                      int slot)
2886 {
2887         u64 bytenr;
2888         u64 last = 0;
2889         u32 nritems;
2890         u32 refs;
2891         u32 blocksize;
2892         int ret;
2893         int i;
2894         int level;
2895         int skipped = 0;
2896
2897         nritems = btrfs_header_nritems(node);
2898         level = btrfs_header_level(node);
2899         if (level)
2900                 return;
2901
2902         for (i = slot; i < nritems && skipped < 32; i++) {
2903                 bytenr = btrfs_node_blockptr(node, i);
2904                 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
2905                              (last > bytenr && last - bytenr > 32 * 1024))) {
2906                         skipped++;
2907                         continue;
2908                 }
2909                 blocksize = btrfs_level_size(root, level - 1);
2910                 if (i != slot) {
2911                         ret = btrfs_lookup_extent_ref(NULL, root, bytenr,
2912                                                       blocksize, &refs);
2913                         BUG_ON(ret);
2914                         if (refs != 1) {
2915                                 skipped++;
2916                                 continue;
2917                         }
2918                 }
2919                 mutex_unlock(&root->fs_info->fs_mutex);
2920                 ret = readahead_tree_block(root, bytenr, blocksize,
2921                                            btrfs_node_ptr_generation(node, i));
2922                 last = bytenr + blocksize;
2923                 cond_resched();
2924                 mutex_lock(&root->fs_info->fs_mutex);
2925                 if (ret)
2926                         break;
2927         }
2928 }
2929
2930 /*
2931  * helper function for drop_snapshot, this walks down the tree dropping ref
2932  * counts as it goes.
2933  */
2934 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2935                                    struct btrfs_root *root,
2936                                    struct btrfs_path *path, int *level)
2937 {
2938         u64 root_owner;
2939         u64 root_gen;
2940         u64 bytenr;
2941         u64 ptr_gen;
2942         struct extent_buffer *next;
2943         struct extent_buffer *cur;
2944         struct extent_buffer *parent;
2945         u32 blocksize;
2946         int ret;
2947         u32 refs;
2948
2949         WARN_ON(*level < 0);
2950         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2951         ret = btrfs_lookup_extent_ref(trans, root,
2952                                       path->nodes[*level]->start,
2953                                       path->nodes[*level]->len, &refs);
2954         BUG_ON(ret);
2955         if (refs > 1)
2956                 goto out;
2957
2958         /*
2959          * walk down to the last node level and free all the leaves
2960          */
2961         while(*level >= 0) {
2962                 WARN_ON(*level < 0);
2963                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2964                 cur = path->nodes[*level];
2965
2966                 if (btrfs_header_level(cur) != *level)
2967                         WARN_ON(1);
2968
2969                 if (path->slots[*level] >=
2970                     btrfs_header_nritems(cur))
2971                         break;
2972                 if (*level == 0) {
2973                         ret = drop_leaf_ref(trans, root, cur);
2974                         BUG_ON(ret);
2975                         break;
2976                 }
2977                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2978                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2979                 blocksize = btrfs_level_size(root, *level - 1);
2980                 ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
2981                                               &refs);
2982                 BUG_ON(ret);
2983                 if (refs != 1) {
2984                         parent = path->nodes[*level];
2985                         root_owner = btrfs_header_owner(parent);
2986                         root_gen = btrfs_header_generation(parent);
2987                         path->slots[*level]++;
2988                         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
2989                                                 parent->start, root_owner,
2990                                                 root_gen, *level - 1, 1);
2991                         BUG_ON(ret);
2992                         continue;
2993                 }
2994                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2995                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2996                         free_extent_buffer(next);
2997                         reada_walk_down(root, cur, path->slots[*level]);
2998                         mutex_unlock(&root->fs_info->fs_mutex);
2999                         next = read_tree_block(root, bytenr, blocksize,
3000                                                ptr_gen);
3001                         mutex_lock(&root->fs_info->fs_mutex);
3002                 }
3003                 WARN_ON(*level <= 0);
3004                 if (path->nodes[*level-1])
3005                         free_extent_buffer(path->nodes[*level-1]);
3006                 path->nodes[*level-1] = next;
3007                 *level = btrfs_header_level(next);
3008                 path->slots[*level] = 0;
3009         }
3010 out:
3011         WARN_ON(*level < 0);
3012         WARN_ON(*level >= BTRFS_MAX_LEVEL);
3013
3014         if (path->nodes[*level] == root->node) {
3015                 root_owner = root->root_key.objectid;
3016                 parent = path->nodes[*level];
3017         } else {
3018                 parent = path->nodes[*level + 1];
3019                 root_owner = btrfs_header_owner(parent);
3020         }
3021
3022         root_gen = btrfs_header_generation(parent);
3023         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
3024                                 path->nodes[*level]->len, parent->start,
3025                                 root_owner, root_gen, *level, 1);
3026         free_extent_buffer(path->nodes[*level]);
3027         path->nodes[*level] = NULL;
3028         *level += 1;
3029         BUG_ON(ret);
3030         return 0;
3031 }
3032
3033 /*
3034  * helper for dropping snapshots.  This walks back up the tree in the path
3035  * to find the first node higher up where we haven't yet gone through
3036  * all the slots
3037  */
3038 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
3039                                  struct btrfs_root *root,
3040                                  struct btrfs_path *path, int *level)
3041 {
3042         u64 root_owner;
3043         u64 root_gen;
3044         struct btrfs_root_item *root_item = &root->root_item;
3045         int i;
3046         int slot;
3047         int ret;
3048
3049         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
3050                 slot = path->slots[i];
3051                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3052                         struct extent_buffer *node;
3053                         struct btrfs_disk_key disk_key;
3054                         node = path->nodes[i];
3055                         path->slots[i]++;
3056                         *level = i;
3057                         WARN_ON(*level == 0);
3058                         btrfs_node_key(node, &disk_key, path->slots[i]);
3059                         memcpy(&root_item->drop_progress,
3060                                &disk_key, sizeof(disk_key));
3061                         root_item->drop_level = i;
3062                         return 0;
3063                 } else {
3064                         struct extent_buffer *parent;
3065                         if (path->nodes[*level] == root->node)
3066                                 parent = path->nodes[*level];
3067                         else
3068                                 parent = path->nodes[*level + 1];
3069
3070                         root_owner = btrfs_header_owner(parent);
3071                         root_gen = btrfs_header_generation(parent);
3072                         ret = btrfs_free_extent(trans, root,
3073                                                 path->nodes[*level]->start,
3074                                                 path->nodes[*level]->len,
3075                                                 parent->start, root_owner,
3076                                                 root_gen, *level, 1);
3077                         BUG_ON(ret);
3078                         free_extent_buffer(path->nodes[*level]);
3079                         path->nodes[*level] = NULL;
3080                         *level = i + 1;
3081                 }
3082         }
3083         return 1;
3084 }
3085
3086 #endif
3087
3088 int btrfs_free_block_groups(struct btrfs_fs_info *info)
3089 {
3090         struct btrfs_space_info *sinfo;
3091         struct btrfs_block_group_cache *cache;
3092         u64 start;
3093         u64 end;
3094         u64 ptr;
3095         int ret;
3096
3097         while(1) {
3098                 ret = find_first_extent_bit(&info->block_group_cache, 0,
3099                                             &start, &end, (unsigned int)-1);
3100                 if (ret)
3101                         break;
3102                 ret = get_state_private(&info->block_group_cache, start, &ptr);
3103                 if (!ret) {
3104                         cache = (struct btrfs_block_group_cache *)ptr;
3105                         if (cache->free_space_ctl) {
3106                                 btrfs_remove_free_space_cache(cache);
3107                                 kfree(cache->free_space_ctl);
3108                         }
3109                         kfree(cache);
3110                 }
3111                 clear_extent_bits(&info->block_group_cache, start,
3112                                   end, (unsigned int)-1, GFP_NOFS);
3113         }
3114         while(1) {
3115                 ret = find_first_extent_bit(&info->free_space_cache, 0,
3116                                             &start, &end, EXTENT_DIRTY);
3117                 if (ret)
3118                         break;
3119                 clear_extent_dirty(&info->free_space_cache, start,
3120                                    end, GFP_NOFS);
3121         }
3122
3123         while (!list_empty(&info->space_info)) {
3124                 sinfo = list_entry(info->space_info.next,
3125                                    struct btrfs_space_info, list);
3126                 list_del_init(&sinfo->list);
3127                 kfree(sinfo);
3128         }
3129         return 0;
3130 }
3131
3132 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
3133                            struct btrfs_key *key)
3134 {
3135         int ret;
3136         struct btrfs_key found_key;
3137         struct extent_buffer *leaf;
3138         int slot;
3139
3140         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
3141         if (ret < 0)
3142                 return ret;
3143         while(1) {
3144                 slot = path->slots[0];
3145                 leaf = path->nodes[0];
3146                 if (slot >= btrfs_header_nritems(leaf)) {
3147                         ret = btrfs_next_leaf(root, path);
3148                         if (ret == 0)
3149                                 continue;
3150                         if (ret < 0)
3151                                 goto error;
3152                         break;
3153                 }
3154                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3155
3156                 if (found_key.objectid >= key->objectid &&
3157                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
3158                         return 0;
3159                 path->slots[0]++;
3160         }
3161         ret = -ENOENT;
3162 error:
3163         return ret;
3164 }
3165
3166 int btrfs_read_block_groups(struct btrfs_root *root)
3167 {
3168         struct btrfs_path *path;
3169         int ret;
3170         int bit;
3171         struct btrfs_block_group_cache *cache;
3172         struct btrfs_fs_info *info = root->fs_info;
3173         struct btrfs_space_info *space_info;
3174         struct extent_io_tree *block_group_cache;
3175         struct btrfs_key key;
3176         struct btrfs_key found_key;
3177         struct extent_buffer *leaf;
3178
3179         block_group_cache = &info->block_group_cache;
3180
3181         root = info->extent_root;
3182         key.objectid = 0;
3183         key.offset = 0;
3184         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
3185         path = btrfs_alloc_path();
3186         if (!path)
3187                 return -ENOMEM;
3188
3189         while(1) {
3190                 ret = find_first_block_group(root, path, &key);
3191                 if (ret > 0) {
3192                         ret = 0;
3193                         goto error;
3194                 }
3195                 if (ret != 0) {
3196                         goto error;
3197                 }
3198                 leaf = path->nodes[0];
3199                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3200                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3201                 if (!cache) {
3202                         ret = -ENOMEM;
3203                         break;
3204                 }
3205
3206                 read_extent_buffer(leaf, &cache->item,
3207                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
3208                                    sizeof(cache->item));
3209                 memcpy(&cache->key, &found_key, sizeof(found_key));
3210                 cache->cached = 0;
3211                 cache->pinned = 0;
3212                 key.objectid = found_key.objectid + found_key.offset;
3213                 btrfs_release_path(root, path);
3214                 cache->flags = btrfs_block_group_flags(&cache->item);
3215                 bit = 0;
3216                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
3217                         bit = BLOCK_GROUP_DATA;
3218                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
3219                         bit = BLOCK_GROUP_SYSTEM;
3220                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
3221                         bit = BLOCK_GROUP_METADATA;
3222                 }
3223                 set_avail_alloc_bits(info, cache->flags);
3224                 if (btrfs_chunk_readonly(root, cache->key.objectid))
3225                         cache->ro = 1;
3226
3227                 ret = update_space_info(info, cache->flags, found_key.offset,
3228                                         btrfs_block_group_used(&cache->item),
3229                                         &space_info);
3230                 BUG_ON(ret);
3231                 cache->space_info = space_info;
3232
3233                 /* use EXTENT_LOCKED to prevent merging */
3234                 set_extent_bits(block_group_cache, found_key.objectid,
3235                                 found_key.objectid + found_key.offset - 1,
3236                                 bit | EXTENT_LOCKED, GFP_NOFS);
3237                 set_state_private(block_group_cache, found_key.objectid,
3238                                   (unsigned long)cache);
3239         }
3240         ret = 0;
3241 error:
3242         btrfs_free_path(path);
3243         return ret;
3244 }
3245
3246 struct btrfs_block_group_cache *
3247 btrfs_add_block_group(struct btrfs_fs_info *fs_info, u64 bytes_used, u64 type,
3248                       u64 chunk_objectid, u64 chunk_offset, u64 size)
3249 {
3250         int ret;
3251         int bit = 0;
3252         struct btrfs_block_group_cache *cache;
3253         struct extent_io_tree *block_group_cache;
3254
3255         block_group_cache = &fs_info->block_group_cache;
3256
3257         cache = kzalloc(sizeof(*cache), GFP_NOFS);
3258         BUG_ON(!cache);
3259         cache->key.objectid = chunk_offset;
3260         cache->key.offset = size;
3261
3262         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
3263         btrfs_set_block_group_used(&cache->item, bytes_used);
3264         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
3265         cache->flags = type;
3266         btrfs_set_block_group_flags(&cache->item, type);
3267
3268         ret = update_space_info(fs_info, cache->flags, size, bytes_used,
3269                                 &cache->space_info);
3270         BUG_ON(ret);
3271
3272         bit = block_group_state_bits(type);
3273         set_extent_bits(block_group_cache, chunk_offset,
3274                         chunk_offset + size - 1,
3275                         bit | EXTENT_LOCKED, GFP_NOFS);
3276
3277         set_state_private(block_group_cache, chunk_offset,
3278                           (unsigned long)cache);
3279         set_avail_alloc_bits(fs_info, type);
3280
3281         return cache;
3282 }
3283
3284 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
3285                            struct btrfs_root *root, u64 bytes_used,
3286                            u64 type, u64 chunk_objectid, u64 chunk_offset,
3287                            u64 size)
3288 {
3289         int ret;
3290         struct btrfs_root *extent_root;
3291         struct btrfs_block_group_cache *cache;
3292
3293         cache = btrfs_add_block_group(root->fs_info, bytes_used, type,
3294                                       chunk_objectid, chunk_offset, size);
3295         extent_root = root->fs_info->extent_root;
3296         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3297                                 sizeof(cache->item));
3298         BUG_ON(ret);
3299
3300         finish_current_insert(trans, extent_root);
3301         ret = del_pending_extents(trans, extent_root);
3302         return 0;
3303 }
3304
3305 /*
3306  * This is for converter use only.
3307  *
3308  * In that case, we don't know where are free blocks located.
3309  * Therefore all block group cache entries must be setup properly
3310  * before doing any block allocation.
3311  */
3312 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
3313                             struct btrfs_root *root)
3314 {
3315         u64 total_bytes;
3316         u64 cur_start;
3317         u64 group_type;
3318         u64 group_size;
3319         u64 group_align;
3320         u64 total_data = 0;
3321         u64 total_metadata = 0;
3322         u64 chunk_objectid;
3323         int ret;
3324         int bit;
3325         struct btrfs_root *extent_root;
3326         struct btrfs_block_group_cache *cache;
3327         struct extent_io_tree *block_group_cache;
3328
3329         extent_root = root->fs_info->extent_root;
3330         block_group_cache = &root->fs_info->block_group_cache;
3331         chunk_objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
3332         total_bytes = btrfs_super_total_bytes(root->fs_info->super_copy);
3333         group_align = 64 * root->sectorsize;
3334
3335         cur_start = 0;
3336         while (cur_start < total_bytes) {
3337                 group_size = total_bytes / 12;
3338                 group_size = min_t(u64, group_size, total_bytes - cur_start);
3339                 if (cur_start == 0) {
3340                         bit = BLOCK_GROUP_SYSTEM;
3341                         group_type = BTRFS_BLOCK_GROUP_SYSTEM;
3342                         group_size /= 4;
3343                         group_size &= ~(group_align - 1);
3344                         group_size = max_t(u64, group_size, 8 * 1024 * 1024);
3345                         group_size = min_t(u64, group_size, 32 * 1024 * 1024);
3346                 } else {
3347                         group_size &= ~(group_align - 1);
3348                         if (total_data >= total_metadata * 2) {
3349                                 group_type = BTRFS_BLOCK_GROUP_METADATA;
3350                                 group_size = min_t(u64, group_size,
3351                                                    1ULL * 1024 * 1024 * 1024);
3352                                 total_metadata += group_size;
3353                         } else {
3354                                 group_type = BTRFS_BLOCK_GROUP_DATA;
3355                                 group_size = min_t(u64, group_size,
3356                                                    5ULL * 1024 * 1024 * 1024);
3357                                 total_data += group_size;
3358                         }
3359                         if ((total_bytes - cur_start) * 4 < group_size * 5)
3360                                 group_size = total_bytes - cur_start;
3361                 }
3362
3363                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
3364                 BUG_ON(!cache);
3365
3366                 cache->key.objectid = cur_start;
3367                 cache->key.offset = group_size;
3368                 btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
3369
3370                 btrfs_set_block_group_used(&cache->item, 0);
3371                 btrfs_set_block_group_chunk_objectid(&cache->item,
3372                                                      chunk_objectid);
3373                 btrfs_set_block_group_flags(&cache->item, group_type);
3374
3375                 cache->flags = group_type;
3376
3377                 ret = update_space_info(root->fs_info, group_type, group_size,
3378                                         0, &cache->space_info);
3379                 BUG_ON(ret);
3380                 set_avail_alloc_bits(extent_root->fs_info, group_type);
3381
3382                 set_extent_bits(block_group_cache, cur_start,
3383                                 cur_start + group_size - 1,
3384                                 bit | EXTENT_LOCKED, GFP_NOFS);
3385                 set_state_private(block_group_cache, cur_start,
3386                                   (unsigned long)cache);
3387                 cur_start += group_size;
3388         }
3389         /* then insert all the items */
3390         cur_start = 0;
3391         while(cur_start < total_bytes) {
3392                 cache = btrfs_lookup_block_group(root->fs_info, cur_start);
3393                 BUG_ON(!cache);
3394
3395                 ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3396                                         sizeof(cache->item));
3397                 BUG_ON(ret);
3398
3399                 finish_current_insert(trans, extent_root);
3400                 ret = del_pending_extents(trans, extent_root);
3401                 BUG_ON(ret);
3402
3403                 cur_start = cache->key.objectid + cache->key.offset;
3404         }
3405         return 0;
3406 }
3407
3408 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
3409                              struct btrfs_root *root,
3410                              u64 bytenr, u64 num_bytes, int alloc,
3411                              int mark_free)
3412 {
3413         return update_block_group(trans, root, bytenr, num_bytes,
3414                                   alloc, mark_free);
3415 }
3416
3417 static int btrfs_count_extents_in_block_group(struct btrfs_root *root,
3418                                               struct btrfs_path *path, u64 start,
3419                                               u64 len,
3420                                               u64 *total)
3421 {
3422         struct btrfs_key key;
3423         struct extent_buffer *leaf;
3424         u64 bytes_used = 0;
3425         int ret;
3426         int slot;
3427
3428         key.offset = 0;
3429         key.objectid = start;
3430         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
3431         ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
3432                                 &key, path, 0, 0);
3433         if (ret < 0)
3434                 return ret;
3435         while(1) {
3436                 leaf = path->nodes[0];
3437                 slot = path->slots[0];
3438                 if (slot >= btrfs_header_nritems(leaf)) {
3439                         ret = btrfs_next_leaf(root, path);
3440                         if (ret < 0)
3441                                 return ret;
3442                         if (ret > 0)
3443                                 break;
3444                         leaf = path->nodes[0];
3445                         slot = path->slots[0];
3446                 }
3447                 btrfs_item_key_to_cpu(leaf, &key, slot);
3448                 if (key.objectid > start + len)
3449                         break;
3450                 if (key.type == BTRFS_EXTENT_ITEM_KEY)
3451                         bytes_used += key.offset;
3452                 if (key.type == BTRFS_METADATA_ITEM_KEY)
3453                         bytes_used += root->leafsize;
3454                 path->slots[0]++;
3455         }
3456         *total = bytes_used;
3457         btrfs_release_path(root, path);
3458         return 0;
3459 }
3460
3461 int btrfs_check_block_accounting(struct btrfs_root *root)
3462 {
3463         int ret;
3464         u64 start = 0;
3465         u64 bytes_used = 0;
3466         struct btrfs_path path;
3467         struct btrfs_block_group_cache *cache;
3468         struct btrfs_fs_info *fs_info = root->fs_info;
3469
3470         btrfs_init_path(&path);
3471
3472         while(1) {
3473                 cache = btrfs_lookup_block_group(fs_info, start);
3474                 if (!cache)
3475                         break;
3476
3477                 ret = btrfs_count_extents_in_block_group(root, &path,
3478                                                          cache->key.objectid,
3479                                                          cache->key.offset,
3480                                                          &bytes_used);
3481
3482                 if (ret == 0) {
3483                         u64 on_disk = btrfs_block_group_used(&cache->item);
3484                         if (on_disk != bytes_used) {
3485                                 fprintf(stderr, "bad block group accounting found %llu "
3486                                         "expected %llu block group %llu\n",
3487                                         (unsigned long long)bytes_used,
3488                                         (unsigned long long)on_disk,
3489                                         (unsigned long long)cache->key.objectid);
3490                         }
3491                 }
3492                 start = cache->key.objectid + cache->key.offset;
3493
3494                 cache->space_info->bytes_used = 0;
3495         }
3496         return 0;
3497 }
3498
3499 /*
3500  * Fixup block accounting. The initial block accounting created by
3501  * make_block_groups isn't accuracy in this case.
3502  */
3503 int btrfs_fix_block_accounting(struct btrfs_trans_handle *trans,
3504                                struct btrfs_root *root)
3505 {
3506         int ret;
3507         int slot;
3508         u64 start = 0;
3509         u64 bytes_used = 0;
3510         struct btrfs_path path;
3511         struct btrfs_key key;
3512         struct extent_buffer *leaf;
3513         struct btrfs_block_group_cache *cache;
3514         struct btrfs_fs_info *fs_info = root->fs_info;
3515
3516         root = root->fs_info->extent_root;
3517
3518         while(extent_root_pending_ops(fs_info)) {
3519                 ret = finish_current_insert(trans, root);
3520                 if (ret)
3521                         return ret;
3522                 ret = del_pending_extents(trans, root);
3523                 if (ret)
3524                         return ret;
3525         }
3526
3527         while(1) {
3528                 cache = btrfs_lookup_first_block_group(fs_info, start);
3529                 if (!cache)
3530                         break;
3531                 start = cache->key.objectid + cache->key.offset;
3532                 btrfs_set_block_group_used(&cache->item, 0);
3533                 cache->space_info->bytes_used = 0;
3534                 set_extent_bits(&root->fs_info->block_group_cache,
3535                                 cache->key.objectid,
3536                                 cache->key.objectid + cache->key.offset -1,
3537                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
3538         }
3539
3540         btrfs_init_path(&path);
3541         key.offset = 0;
3542         key.objectid = 0;
3543         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
3544         ret = btrfs_search_slot(trans, root->fs_info->extent_root,
3545                                 &key, &path, 0, 0);
3546         if (ret < 0)
3547                 return ret;
3548         while(1) {
3549                 leaf = path.nodes[0];
3550                 slot = path.slots[0];
3551                 if (slot >= btrfs_header_nritems(leaf)) {
3552                         ret = btrfs_next_leaf(root, &path);
3553                         if (ret < 0)
3554                                 return ret;
3555                         if (ret > 0)
3556                                 break;
3557                         leaf = path.nodes[0];
3558                         slot = path.slots[0];
3559                 }
3560                 btrfs_item_key_to_cpu(leaf, &key, slot);
3561                 if (key.type == BTRFS_EXTENT_ITEM_KEY) {
3562                         bytes_used += key.offset;
3563                         ret = btrfs_update_block_group(trans, root,
3564                                   key.objectid, key.offset, 1, 0);
3565                         BUG_ON(ret);
3566                 } else if (key.type == BTRFS_METADATA_ITEM_KEY) {
3567                         bytes_used += root->leafsize;
3568                         ret = btrfs_update_block_group(trans, root,
3569                                   key.objectid, root->leafsize, 1, 0);
3570                         BUG_ON(ret);
3571                 }
3572                 path.slots[0]++;
3573         }
3574         btrfs_set_super_bytes_used(root->fs_info->super_copy, bytes_used);
3575         btrfs_release_path(root, &path);
3576         return 0;
3577 }