extent-tree.c

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