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