extent-tree.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include "kerncompat.h"
  22 #include "radix-tree.h"
  23 #include "ctree.h"
  24 #include "disk-io.h"
  25 #include "print-tree.h"
  26 #include "transaction.h"
  27 #include "crc32c.h"
  28 #include "volumes.h"
  29
  30 #define BLOCK_GROUP_DATA     EXTENT_WRITEBACK
  31 #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  32 #define BLOCK_GROUP_SYSTEM   EXTENT_NEW
  33
  34 #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  35
  36 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  37                                  btrfs_root *extent_root);
  38 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  39                                btrfs_root *extent_root);
  40 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
  41                            struct btrfs_root *root, u64 bytes_used,
  42                            u64 type, u64 chunk_tree, u64 chunk_objectid,
  43                            u64 size);
  44
  45 static int cache_block_group(struct btrfs_root *root,
  46                              struct btrfs_block_group_cache *block_group)
  47 {
  48         struct btrfs_path *path;
  49         int ret;
  50         struct btrfs_key key;
  51         struct extent_buffer *leaf;
  52         struct extent_io_tree *free_space_cache;
  53         int slot;
  54         u64 last = 0;
  55         u64 hole_size;
  56         u64 first_free;
  57         int found = 0;
  58
  59         if (!block_group)
  60                 return 0;
  61
  62         root = root->fs_info->extent_root;
  63         free_space_cache = &root->fs_info->free_space_cache;
  64
  65         if (block_group->cached)
  66                 return 0;
  67
  68         path = btrfs_alloc_path();
  69         if (!path)
  70                 return -ENOMEM;
  71
  72         path->reada = 2;
  73         first_free = block_group->key.objectid;
  74         key.objectid = block_group->key.objectid;
  75         key.offset = 0;
  76         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  77         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  78         if (ret < 0)
  79                 return ret;
  80         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  81         if (ret < 0)
  82                 return ret;
  83         if (ret == 0) {
  84                 leaf = path->nodes[0];
  85                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  86                 if (key.objectid + key.offset > first_free)
  87                         first_free = key.objectid + key.offset;
  88         }
  89         while(1) {
  90                 leaf = path->nodes[0];
  91                 slot = path->slots[0];
  92                 if (slot >= btrfs_header_nritems(leaf)) {
  93                         ret = btrfs_next_leaf(root, path);
  94                         if (ret < 0)
  95                                 goto err;
  96                         if (ret == 0) {
  97                                 continue;
  98                         } else {
  99                                 break;
 100                         }
 101                 }
 102                 btrfs_item_key_to_cpu(leaf, &key, slot);
 103                 if (key.objectid < block_group->key.objectid) {
 104                         goto next;
 105                 }
 106                 if (key.objectid >= block_group->key.objectid +
 107                     block_group->key.offset) {
 108                         break;
 109                 }
 110
 111                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 112                         if (!found) {
 113                                 last = first_free;
 114                                 found = 1;
 115                         }
 116                         if (key.objectid > last) {
 117                                 hole_size = key.objectid - last;
 118                                 set_extent_dirty(free_space_cache, last,
 119                                                  last + hole_size - 1,
 120                                                  GFP_NOFS);
 121                         }
 122                         last = key.objectid + key.offset;
 123                 }
 124 next:
 125                 path->slots[0]++;
 126         }
 127
 128         if (!found)
 129                 last = first_free;
 130         if (block_group->key.objectid +
 131             block_group->key.offset > last) {
 132                 hole_size = block_group->key.objectid +
 133                         block_group->key.offset - last;
 134                 set_extent_dirty(free_space_cache, last,
 135                                  last + hole_size - 1, GFP_NOFS);
 136         }
 137         block_group->cached = 1;
 138 err:
 139         btrfs_free_path(path);
 140         return 0;
 141 }
 142
 143 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 144                                                          btrfs_fs_info *info,
 145                                                          u64 bytenr)
 146 {
 147         struct extent_io_tree *block_group_cache;
 148         struct btrfs_block_group_cache *block_group = NULL;
 149         u64 ptr;
 150         u64 start;
 151         u64 end;
 152         int ret;
 153
 154         block_group_cache = &info->block_group_cache;
 155         ret = find_first_extent_bit(block_group_cache,
 156                                     bytenr, &start, &end,
 157                                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
 158                                     BLOCK_GROUP_SYSTEM);
 159         if (ret) {
 160                 return NULL;
 161         }
 162         ret = get_state_private(block_group_cache, start, &ptr);
 163         if (ret)
 164                 return NULL;
 165
 166         block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 167         if (block_group->key.objectid <= bytenr && bytenr <
 168             block_group->key.objectid + block_group->key.offset)
 169                 return block_group;
 170         return NULL;
 171 }
 172
 173 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 174 {
 175         return (cache->flags & bits);
 176 }
 177
 178 static int noinline find_search_start(struct btrfs_root *root,
 179                               struct btrfs_block_group_cache **cache_ret,
 180                               u64 *start_ret, int num, int data)
 181 {
 182         int ret;
 183         struct btrfs_block_group_cache *cache = *cache_ret;
 184         u64 last;
 185         u64 start = 0;
 186         u64 end = 0;
 187         u64 cache_miss = 0;
 188         u64 search_start = *start_ret;
 189         int wrapped = 0;
 190
 191         if (!cache) {
 192                 goto out;
 193         }
 194 again:
 195         ret = cache_block_group(root, cache);
 196         if (ret)
 197                 goto out;
 198
 199         last = max(search_start, cache->key.objectid);
 200         if (!block_group_bits(cache, data)) {
 201                 goto new_group;
 202         }
 203
 204         while(1) {
 205                 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
 206                                             last, &start, &end, EXTENT_DIRTY);
 207                 if (ret) {
 208                         if (!cache_miss)
 209                                 cache_miss = last;
 210                         goto new_group;
 211                 }
 212
 213                 start = max(last, start);
 214                 last = end + 1;
 215                 if (last - start < num) {
 216                         if (last == cache->key.objectid + cache->key.offset)
 217                                 cache_miss = start;
 218                         continue;
 219                 }
 220                 if (start + num > cache->key.objectid + cache->key.offset)
 221                         goto new_group;
 222                 *start_ret = start;
 223                 return 0;
 224         }
 225 out:
 226         cache = btrfs_lookup_block_group(root->fs_info, search_start);
 227         if (!cache) {
 228                 printk("Unable to find block group for %llu\n",
 229                         (unsigned long long)search_start);
 230                 WARN_ON(1);
 231         }
 232         return -ENOSPC;
 233
 234 new_group:
 235         last = cache->key.objectid + cache->key.offset;
 236 wrapped:
 237         cache = btrfs_lookup_block_group(root->fs_info, last);
 238         if (!cache) {
 239 no_cache:
 240                 if (!wrapped) {
 241                         wrapped = 1;
 242                         last = search_start;
 243                         goto wrapped;
 244                 }
 245                 goto out;
 246         }
 247         if (cache_miss && !cache->cached) {
 248                 cache_block_group(root, cache);
 249                 last = cache_miss;
 250                 cache = btrfs_lookup_block_group(root->fs_info, last);
 251         }
 252         cache = btrfs_find_block_group(root, cache, last, data, 0);
 253         if (!cache)
 254                 goto no_cache;
 255         *cache_ret = cache;
 256         cache_miss = 0;
 257         goto again;
 258 }
 259
 260 static u64 div_factor(u64 num, int factor)
 261 {
 262         if (factor == 10)
 263                 return num;
 264         num *= factor;
 265         num /= 10;
 266         return num;
 267 }
 268
 269 static int block_group_state_bits(u64 flags)
 270 {
 271         int bits = 0;
 272         if (flags & BTRFS_BLOCK_GROUP_DATA)
 273                 bits |= BLOCK_GROUP_DATA;
 274         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 275                 bits |= BLOCK_GROUP_METADATA;
 276         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 277                 bits |= BLOCK_GROUP_SYSTEM;
 278         return bits;
 279 }
 280
 281 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 282                                                  struct btrfs_block_group_cache
 283                                                  *hint, u64 search_start,
 284                                                  int data, int owner)
 285 {
 286         struct btrfs_block_group_cache *cache;
 287         struct extent_io_tree *block_group_cache;
 288         struct btrfs_block_group_cache *found_group = NULL;
 289         struct btrfs_fs_info *info = root->fs_info;
 290         u64 used;
 291         u64 last = 0;
 292         u64 hint_last;
 293         u64 start;
 294         u64 end;
 295         u64 free_check;
 296         u64 ptr;
 297         int bit;
 298         int ret;
 299         int full_search = 0;
 300         int factor = 8;
 301
 302         block_group_cache = &info->block_group_cache;
 303
 304         if (!owner)
 305                 factor = 8;
 306
 307         bit = block_group_state_bits(data);
 308
 309         if (search_start) {
 310                 struct btrfs_block_group_cache *shint;
 311                 shint = btrfs_lookup_block_group(info, search_start);
 312                 if (shint && block_group_bits(shint, data)) {
 313                         used = btrfs_block_group_used(&shint->item);
 314                         if (used + shint->pinned <
 315                             div_factor(shint->key.offset, factor)) {
 316                                 return shint;
 317                         }
 318                 }
 319         }
 320         if (hint && block_group_bits(hint, data)) {
 321                 used = btrfs_block_group_used(&hint->item);
 322                 if (used + hint->pinned <
 323                     div_factor(hint->key.offset, factor)) {
 324                         return hint;
 325                 }
 326                 last = hint->key.objectid + hint->key.offset;
 327                 hint_last = last;
 328         } else {
 329                 if (hint)
 330                         hint_last = max(hint->key.objectid, search_start);
 331                 else
 332                         hint_last = search_start;
 333
 334                 last = hint_last;
 335         }
 336 again:
 337         while(1) {
 338                 ret = find_first_extent_bit(block_group_cache, last,
 339                                             &start, &end, bit);
 340                 if (ret)
 341                         break;
 342
 343                 ret = get_state_private(block_group_cache, start, &ptr);
 344                 if (ret)
 345                         break;
 346
 347                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 348                 last = cache->key.objectid + cache->key.offset;
 349                 used = btrfs_block_group_used(&cache->item);
 350
 351                 if (full_search)
 352                         free_check = cache->key.offset;
 353                 else
 354                         free_check = div_factor(cache->key.offset, factor);
 355
 356                 if (used + cache->pinned < free_check) {
 357                         found_group = cache;
 358                         goto found;
 359                 }
 360                 cond_resched();
 361         }
 362         if (!full_search) {
 363                 last = search_start;
 364                 full_search = 1;
 365                 goto again;
 366         }
 367 found:
 368         return found_group;
 369 }
 370
 371 static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
 372                            u64 owner, u64 owner_offset)
 373 {
 374         u32 high_crc = ~(u32)0;
 375         u32 low_crc = ~(u32)0;
 376         __le64 lenum;
 377
 378         lenum = cpu_to_le64(root_objectid);
 379         high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
 380         lenum = cpu_to_le64(ref_generation);
 381         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 382         if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
 383                 lenum = cpu_to_le64(owner);
 384                 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 385                 lenum = cpu_to_le64(owner_offset);
 386                 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 387         }
 388         return ((u64)high_crc << 32) | (u64)low_crc;
 389 }
 390
 391 static int match_extent_ref(struct extent_buffer *leaf,
 392                             struct btrfs_extent_ref *disk_ref,
 393                             struct btrfs_extent_ref *cpu_ref)
 394 {
 395         int ret;
 396         int len;
 397
 398         if (cpu_ref->objectid)
 399                 len = sizeof(*cpu_ref);
 400         else
 401                 len = 2 * sizeof(u64);
 402         ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
 403                                    len);
 404         return ret == 0;
 405 }
 406
 407 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
 408                                           struct btrfs_root *root,
 409                                           struct btrfs_path *path, u64 bytenr,
 410                                           u64 root_objectid,
 411                                           u64 ref_generation, u64 owner,
 412                                           u64 owner_offset, int del)
 413 {
 414         u64 hash;
 415         struct btrfs_key key;
 416         struct btrfs_key found_key;
 417         struct btrfs_extent_ref ref;
 418         struct extent_buffer *leaf;
 419         struct btrfs_extent_ref *disk_ref;
 420         int ret;
 421         int ret2;
 422
 423         btrfs_set_stack_ref_root(&ref, root_objectid);
 424         btrfs_set_stack_ref_generation(&ref, ref_generation);
 425         btrfs_set_stack_ref_objectid(&ref, owner);
 426         btrfs_set_stack_ref_offset(&ref, owner_offset);
 427
 428         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 429                                owner_offset);
 430         key.offset = hash;
 431         key.objectid = bytenr;
 432         key.type = BTRFS_EXTENT_REF_KEY;
 433
 434         while (1) {
 435                 ret = btrfs_search_slot(trans, root, &key, path,
 436                                         del ? -1 : 0, del);
 437                 if (ret < 0)
 438                         goto out;
 439                 leaf = path->nodes[0];
 440                 if (ret != 0) {
 441                         u32 nritems = btrfs_header_nritems(leaf);
 442                         if (path->slots[0] >= nritems) {
 443                                 ret2 = btrfs_next_leaf(root, path);
 444                                 if (ret2)
 445                                         goto out;
 446                                 leaf = path->nodes[0];
 447                         }
 448                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 449                         if (found_key.objectid != bytenr ||
 450                             found_key.type != BTRFS_EXTENT_REF_KEY)
 451                                 goto out;
 452                         key.offset = found_key.offset;
 453                         if (del) {
 454                                 btrfs_release_path(root, path);
 455                                 continue;
 456                         }
 457                 }
 458                 disk_ref = btrfs_item_ptr(path->nodes[0],
 459                                           path->slots[0],
 460                                           struct btrfs_extent_ref);
 461                 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
 462                         ret = 0;
 463                         goto out;
 464                 }
 465                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 466                 key.offset = found_key.offset + 1;
 467                 btrfs_release_path(root, path);
 468         }
 469 out:
 470         return ret;
 471 }
 472
 473 /*
 474  * Back reference rules.  Back refs have three main goals:
 475  *
 476  * 1) differentiate between all holders of references to an extent so that
 477  *    when a reference is dropped we can make sure it was a valid reference
 478  *    before freeing the extent.
 479  *
 480  * 2) Provide enough information to quickly find the holders of an extent
 481  *    if we notice a given block is corrupted or bad.
 482  *
 483  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 484  *    maintenance.  This is actually the same as #2, but with a slightly
 485  *    different use case.
 486  *
 487  * File extents can be referenced by:
 488  *
 489  * - multiple snapshots, subvolumes, or different generations in one subvol
 490  * - different files inside a single subvolume (in theory, not implemented yet)
 491  * - different offsets inside a file (bookend extents in file.c)
 492  *
 493  * The extent ref structure has fields for:
 494  *
 495  * - Objectid of the subvolume root
 496  * - Generation number of the tree holding the reference
 497  * - objectid of the file holding the reference
 498  * - offset in the file corresponding to the key holding the reference
 499  *
 500  * When a file extent is allocated the fields are filled in:
 501  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 502  *
 503  * When a leaf is cow'd new references are added for every file extent found
 504  * in the leaf.  It looks the same as the create case, but trans->transid
 505  * will be different when the block is cow'd.
 506  *
 507  *     (root_key.objectid, trans->transid, inode objectid, offset in file)
 508  *
 509  * When a file extent is removed either during snapshot deletion or file
 510  * truncation, the corresponding back reference is found
 511  * by searching for:
 512  *
 513  *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 514  *      inode objectid, offset in file)
 515  *
 516  * Btree extents can be referenced by:
 517  *
 518  * - Different subvolumes
 519  * - Different generations of the same subvolume
 520  *
 521  * Storing sufficient information for a full reverse mapping of a btree
 522  * block would require storing the lowest key of the block in the backref,
 523  * and it would require updating that lowest key either before write out or
 524  * every time it changed.  Instead, the objectid of the lowest key is stored
 525  * along with the level of the tree block.  This provides a hint
 526  * about where in the btree the block can be found.  Searches through the
 527  * btree only need to look for a pointer to that block, so they stop one
 528  * level higher than the level recorded in the backref.
 529  *
 530  * Some btrees do not do reference counting on their extents.  These
 531  * include the extent tree and the tree of tree roots.  Backrefs for these
 532  * trees always have a generation of zero.
 533  *
 534  * When a tree block is created, back references are inserted:
 535  *
 536  * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
 537  *
 538  * When a tree block is cow'd in a reference counted root,
 539  * new back references are added for all the blocks it points to.
 540  * These are of the form (trans->transid will have increased since creation):
 541  *
 542  * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
 543  *
 544  * Because the lowest_key_objectid and the level are just hints
 545  * they are not used when backrefs are deleted.  When a backref is deleted:
 546  *
 547  * if backref was for a tree root:
 548  *     root_objectid = root->root_key.objectid
 549  * else
 550  *     root_objectid = btrfs_header_owner(parent)
 551  *
 552  * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
 553  *
 554  * Back Reference Key hashing:
 555  *
 556  * Back references have four fields, each 64 bits long.  Unfortunately,
 557  * This is hashed into a single 64 bit number and placed into the key offset.
 558  * The key objectid corresponds to the first byte in the extent, and the
 559  * key type is set to BTRFS_EXTENT_REF_KEY
 560  */
 561 int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
 562                                  struct btrfs_root *root,
 563                                  struct btrfs_path *path, u64 bytenr,
 564                                  u64 root_objectid, u64 ref_generation,
 565                                  u64 owner, u64 owner_offset)
 566 {
 567         u64 hash;
 568         struct btrfs_key key;
 569         struct btrfs_extent_ref ref;
 570         struct btrfs_extent_ref *disk_ref;
 571         int ret;
 572
 573         btrfs_set_stack_ref_root(&ref, root_objectid);
 574         btrfs_set_stack_ref_generation(&ref, ref_generation);
 575         btrfs_set_stack_ref_objectid(&ref, owner);
 576         btrfs_set_stack_ref_offset(&ref, owner_offset);
 577
 578         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 579                                owner_offset);
 580         key.offset = hash;
 581         key.objectid = bytenr;
 582         key.type = BTRFS_EXTENT_REF_KEY;
 583
 584         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
 585         while (ret == -EEXIST) {
 586                 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 587                                           struct btrfs_extent_ref);
 588                 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
 589                         goto out;
 590                 key.offset++;
 591                 btrfs_release_path(root, path);
 592                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 593                                               sizeof(ref));
 594         }
 595         if (ret)
 596                 goto out;
 597         disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
 598                                   struct btrfs_extent_ref);
 599         write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
 600                             sizeof(ref));
 601         btrfs_mark_buffer_dirty(path->nodes[0]);
 602 out:
 603         btrfs_release_path(root, path);
 604         return ret;
 605 }
 606
 607 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 608                                 struct btrfs_root *root,
 609                                 u64 bytenr, u64 num_bytes,
 610                                 u64 root_objectid, u64 ref_generation,
 611                                 u64 owner, u64 owner_offset)
 612 {
 613         struct btrfs_path *path;
 614         int ret;
 615         struct btrfs_key key;
 616         struct extent_buffer *l;
 617         struct btrfs_extent_item *item;
 618         u32 refs;
 619
 620         WARN_ON(num_bytes < root->sectorsize);
 621         path = btrfs_alloc_path();
 622         if (!path)
 623                 return -ENOMEM;
 624
 625         key.objectid = bytenr;
 626         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 627         key.offset = num_bytes;
 628         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 629                                 0, 1);
 630         if (ret < 0)
 631                 return ret;
 632         if (ret != 0) {
 633                 BUG();
 634         }
 635         BUG_ON(ret != 0);
 636         l = path->nodes[0];
 637         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 638         refs = btrfs_extent_refs(l, item);
 639         btrfs_set_extent_refs(l, item, refs + 1);
 640         btrfs_mark_buffer_dirty(path->nodes[0]);
 641
 642         btrfs_release_path(root->fs_info->extent_root, path);
 643
 644         ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
 645                                           path, bytenr, root_objectid,
 646                                           ref_generation, owner, owner_offset);
 647         BUG_ON(ret);
 648         finish_current_insert(trans, root->fs_info->extent_root);
 649         del_pending_extents(trans, root->fs_info->extent_root);
 650
 651         btrfs_free_path(path);
 652         return 0;
 653 }
 654
 655 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 656                          struct btrfs_root *root)
 657 {
 658         finish_current_insert(trans, root->fs_info->extent_root);
 659         del_pending_extents(trans, root->fs_info->extent_root);
 660         return 0;
 661 }
 662
 663 static int lookup_extent_ref(struct btrfs_trans_handle *trans,
 664                              struct btrfs_root *root, u64 bytenr,
 665                              u64 num_bytes, u32 *refs)
 666 {
 667         struct btrfs_path *path;
 668         int ret;
 669         struct btrfs_key key;
 670         struct extent_buffer *l;
 671         struct btrfs_extent_item *item;
 672
 673         WARN_ON(num_bytes < root->sectorsize);
 674         path = btrfs_alloc_path();
 675         key.objectid = bytenr;
 676         key.offset = num_bytes;
 677         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 678         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 679                                 0, 0);
 680         if (ret < 0)
 681                 goto out;
 682         if (ret != 0) {
 683                 btrfs_print_leaf(root, path->nodes[0]);
 684                 printk("failed to find block number %llu\n",
 685                         (unsigned long long)bytenr);
 686                 BUG();
 687         }
 688         l = path->nodes[0];
 689         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 690         *refs = btrfs_extent_refs(l, item);
 691 out:
 692         btrfs_free_path(path);
 693         return 0;
 694 }
 695
 696 u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
 697                                   struct btrfs_path *count_path,
 698                                   u64 first_extent)
 699 {
 700         struct btrfs_root *extent_root = root->fs_info->extent_root;
 701         struct btrfs_path *path;
 702         u64 bytenr;
 703         u64 found_objectid;
 704         u64 root_objectid = root->root_key.objectid;
 705         u32 total_count = 0;
 706         u32 cur_count;
 707         u32 refs;
 708         u32 nritems;
 709         int ret;
 710         struct btrfs_key key;
 711         struct btrfs_key found_key;
 712         struct extent_buffer *l;
 713         struct btrfs_extent_item *item;
 714         struct btrfs_extent_ref *ref_item;
 715         int level = -1;
 716
 717         path = btrfs_alloc_path();
 718 again:
 719         if (level == -1)
 720                 bytenr = first_extent;
 721         else
 722                 bytenr = count_path->nodes[level]->start;
 723
 724         cur_count = 0;
 725         key.objectid = bytenr;
 726         key.offset = 0;
 727
 728         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 729         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 730         if (ret < 0)
 731                 goto out;
 732         BUG_ON(ret == 0);
 733
 734         l = path->nodes[0];
 735         btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
 736
 737         if (found_key.objectid != bytenr ||
 738             found_key.type != BTRFS_EXTENT_ITEM_KEY) {
 739                 goto out;
 740         }
 741
 742         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 743         refs = btrfs_extent_refs(l, item);
 744         while (1) {
 745                 nritems = btrfs_header_nritems(l);
 746                 if (path->slots[0] >= nritems) {
 747                         ret = btrfs_next_leaf(extent_root, path);
 748                         if (ret == 0)
 749                                 continue;
 750                         break;
 751                 }
 752                 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
 753                 if (found_key.objectid != bytenr)
 754                         break;
 755                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
 756                         path->slots[0]++;
 757                         continue;
 758                 }
 759
 760                 cur_count++;
 761                 ref_item = btrfs_item_ptr(l, path->slots[0],
 762                                           struct btrfs_extent_ref);
 763                 found_objectid = btrfs_ref_root(l, ref_item);
 764
 765                 if (found_objectid != root_objectid) {
 766                         total_count = 2;
 767                         goto out;
 768                 }
 769                 total_count = 1;
 770                 path->slots[0]++;
 771         }
 772         if (cur_count == 0) {
 773                 total_count = 0;
 774                 goto out;
 775         }
 776         if (level >= 0 && root->node == count_path->nodes[level])
 777                 goto out;
 778         level++;
 779         btrfs_release_path(root, path);
 780         goto again;
 781
 782 out:
 783         btrfs_free_path(path);
 784         return total_count;
 785 }
 786 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 787                        struct btrfs_root *root, u64 owner_objectid)
 788 {
 789         u64 generation;
 790         u64 key_objectid;
 791         u64 level;
 792         u32 nritems;
 793         struct btrfs_disk_key disk_key;
 794
 795         level = btrfs_header_level(root->node);
 796         generation = trans->transid;
 797         nritems = btrfs_header_nritems(root->node);
 798         if (nritems > 0) {
 799                 if (level == 0)
 800                         btrfs_item_key(root->node, &disk_key, 0);
 801                 else
 802                         btrfs_node_key(root->node, &disk_key, 0);
 803                 key_objectid = btrfs_disk_key_objectid(&disk_key);
 804         } else {
 805                 key_objectid = 0;
 806         }
 807         return btrfs_inc_extent_ref(trans, root, root->node->start,
 808                                     root->node->len, owner_objectid,
 809                                     generation, level, key_objectid);
 810 }
 811
 812 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 813                   struct extent_buffer *buf)
 814 {
 815         u64 bytenr;
 816         u32 nritems;
 817         struct btrfs_key key;
 818         struct btrfs_file_extent_item *fi;
 819         int i;
 820         int level;
 821         int ret;
 822         int faili;
 823
 824         if (!root->ref_cows)
 825                 return 0;
 826
 827         level = btrfs_header_level(buf);
 828         nritems = btrfs_header_nritems(buf);
 829         for (i = 0; i < nritems; i++) {
 830                 if (level == 0) {
 831                         u64 disk_bytenr;
 832                         btrfs_item_key_to_cpu(buf, &key, i);
 833                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 834                                 continue;
 835                         fi = btrfs_item_ptr(buf, i,
 836                                             struct btrfs_file_extent_item);
 837                         if (btrfs_file_extent_type(buf, fi) ==
 838                             BTRFS_FILE_EXTENT_INLINE)
 839                                 continue;
 840                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 841                         if (disk_bytenr == 0)
 842                                 continue;
 843                         ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
 844                                     btrfs_file_extent_disk_num_bytes(buf, fi),
 845                                     root->root_key.objectid, trans->transid,
 846                                     key.objectid, key.offset);
 847                         if (ret) {
 848                                 faili = i;
 849                                 goto fail;
 850                         }
 851                 } else {
 852                         bytenr = btrfs_node_blockptr(buf, i);
 853                         btrfs_node_key_to_cpu(buf, &key, i);
 854                         ret = btrfs_inc_extent_ref(trans, root, bytenr,
 855                                            btrfs_level_size(root, level - 1),
 856                                            root->root_key.objectid,
 857                                            trans->transid,
 858                                            level - 1, key.objectid);
 859                         if (ret) {
 860                                 faili = i;
 861                                 goto fail;
 862                         }
 863                 }
 864         }
 865         return 0;
 866 fail:
 867         WARN_ON(1);
 868 #if 0
 869         for (i =0; i < faili; i++) {
 870                 if (level == 0) {
 871                         u64 disk_bytenr;
 872                         btrfs_item_key_to_cpu(buf, &key, i);
 873                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
 874                                 continue;
 875                         fi = btrfs_item_ptr(buf, i,
 876                                             struct btrfs_file_extent_item);
 877                         if (btrfs_file_extent_type(buf, fi) ==
 878                             BTRFS_FILE_EXTENT_INLINE)
 879                                 continue;
 880                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 881                         if (disk_bytenr == 0)
 882                                 continue;
 883                         err = btrfs_free_extent(trans, root, disk_bytenr,
 884                                     btrfs_file_extent_disk_num_bytes(buf,
 885                                                                       fi), 0);
 886                         BUG_ON(err);
 887                 } else {
 888                         bytenr = btrfs_node_blockptr(buf, i);
 889                         err = btrfs_free_extent(trans, root, bytenr,
 890                                         btrfs_level_size(root, level - 1), 0);
 891                         BUG_ON(err);
 892                 }
 893         }
 894 #endif
 895         return ret;
 896 }
 897
 898 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 899                                  struct btrfs_root *root,
 900                                  struct btrfs_path *path,
 901                                  struct btrfs_block_group_cache *cache)
 902 {
 903         int ret;
 904         int pending_ret;
 905         struct btrfs_root *extent_root = root->fs_info->extent_root;
 906         unsigned long bi;
 907         struct extent_buffer *leaf;
 908
 909         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 910         if (ret < 0)
 911                 goto fail;
 912         BUG_ON(ret);
 913
 914         leaf = path->nodes[0];
 915         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
 916         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
 917         btrfs_mark_buffer_dirty(leaf);
 918         btrfs_release_path(extent_root, path);
 919 fail:
 920         finish_current_insert(trans, extent_root);
 921         pending_ret = del_pending_extents(trans, extent_root);
 922         if (ret)
 923                 return ret;
 924         if (pending_ret)
 925                 return pending_ret;
 926         return 0;
 927
 928 }
 929
 930 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 931                                    struct btrfs_root *root)
 932 {
 933         struct extent_io_tree *block_group_cache;
 934         struct btrfs_block_group_cache *cache;
 935         int ret;
 936         int err = 0;
 937         int werr = 0;
 938         struct btrfs_path *path;
 939         u64 last = 0;
 940         u64 start;
 941         u64 end;
 942         u64 ptr;
 943
 944         block_group_cache = &root->fs_info->block_group_cache;
 945         path = btrfs_alloc_path();
 946         if (!path)
 947                 return -ENOMEM;
 948
 949         while(1) {
 950                 ret = find_first_extent_bit(block_group_cache, last,
 951                                             &start, &end, BLOCK_GROUP_DIRTY);
 952                 if (ret)
 953                         break;
 954
 955                 last = end + 1;
 956                 ret = get_state_private(block_group_cache, start, &ptr);
 957                 if (ret)
 958                         break;
 959
 960                 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 961                 err = write_one_cache_group(trans, root,
 962                                             path, cache);
 963                 /*
 964                  * if we fail to write the cache group, we want
 965                  * to keep it marked dirty in hopes that a later
 966                  * write will work
 967                  */
 968                 if (err) {
 969                         werr = err;
 970                         continue;
 971                 }
 972                 clear_extent_bits(block_group_cache, start, end,
 973                                   BLOCK_GROUP_DIRTY, GFP_NOFS);
 974         }
 975         btrfs_free_path(path);
 976         return werr;
 977 }
 978
 979 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 980                                                   u64 flags)
 981 {
 982         struct list_head *head = &info->space_info;
 983         struct list_head *cur;
 984         struct btrfs_space_info *found;
 985         list_for_each(cur, head) {
 986                 found = list_entry(cur, struct btrfs_space_info, list);
 987                 if (found->flags == flags)
 988                         return found;
 989         }
 990         return NULL;
 991
 992 }
 993
 994 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
 995                              u64 total_bytes, u64 bytes_used,
 996                              struct btrfs_space_info **space_info)
 997 {
 998         struct btrfs_space_info *found;
 999
1000         found = __find_space_info(info, flags);
1001         if (found) {
1002                 found->total_bytes += total_bytes;
1003                 found->bytes_used += bytes_used;
1004                 WARN_ON(found->total_bytes < found->bytes_used);
1005                 *space_info = found;
1006                 return 0;
1007         }
1008         found = kmalloc(sizeof(*found), GFP_NOFS);
1009         if (!found)
1010                 return -ENOMEM;
1011
1012         list_add(&found->list, &info->space_info);
1013         found->flags = flags;
1014         found->total_bytes = total_bytes;
1015         found->bytes_used = bytes_used;
1016         found->bytes_pinned = 0;
1017         found->full = 0;
1018         *space_info = found;
1019         return 0;
1020 }
1021
1022
1023 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1024                           struct btrfs_root *extent_root, u64 alloc_bytes,
1025                           u64 flags)
1026 {
1027         struct btrfs_space_info *space_info;
1028         u64 thresh;
1029         u64 start;
1030         u64 num_bytes;
1031         int ret;
1032
1033         space_info = __find_space_info(extent_root->fs_info, flags);
1034         if (!space_info) {
1035                 ret = update_space_info(extent_root->fs_info, flags,
1036                                         0, 0, &space_info);
1037                 BUG_ON(ret);
1038         }
1039         BUG_ON(!space_info);
1040
1041         if (space_info->full)
1042                 return 0;
1043
1044         thresh = div_factor(space_info->total_bytes, 7);
1045         if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
1046             thresh)
1047                 return 0;
1048
1049         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1050         if (ret == -ENOSPC) {
1051 printk("space info full %llu\n", (unsigned long long)flags);
1052                 space_info->full = 1;
1053                 return 0;
1054         }
1055
1056         BUG_ON(ret);
1057
1058         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1059                      extent_root->fs_info->chunk_root->root_key.objectid,
1060                      start, num_bytes);
1061         BUG_ON(ret);
1062         return 0;
1063 }
1064
1065 static int update_block_group(struct btrfs_trans_handle *trans,
1066                               struct btrfs_root *root,
1067                               u64 bytenr, u64 num_bytes, int alloc,
1068                               int mark_free)
1069 {
1070         struct btrfs_block_group_cache *cache;
1071         struct btrfs_fs_info *info = root->fs_info;
1072         u64 total = num_bytes;
1073         u64 old_val;
1074         u64 byte_in_group;
1075         u64 start;
1076         u64 end;
1077
1078         while(total) {
1079                 cache = btrfs_lookup_block_group(info, bytenr);
1080                 if (!cache) {
1081                         return -1;
1082                 }
1083                 byte_in_group = bytenr - cache->key.objectid;
1084                 WARN_ON(byte_in_group > cache->key.offset);
1085                 start = cache->key.objectid;
1086                 end = start + cache->key.offset - 1;
1087                 set_extent_bits(&info->block_group_cache, start, end,
1088                                 BLOCK_GROUP_DIRTY, GFP_NOFS);
1089
1090                 old_val = btrfs_block_group_used(&cache->item);
1091                 num_bytes = min(total, cache->key.offset - byte_in_group);
1092                 if (alloc) {
1093                         old_val += num_bytes;
1094                         cache->space_info->bytes_used += num_bytes;
1095                 } else {
1096                         old_val -= num_bytes;
1097                         cache->space_info->bytes_used -= num_bytes;
1098                         if (mark_free) {
1099                                 set_extent_dirty(&info->free_space_cache,
1100                                                  bytenr, bytenr + num_bytes - 1,
1101                                                  GFP_NOFS);
1102                         }
1103                 }
1104                 btrfs_set_block_group_used(&cache->item, old_val);
1105                 total -= num_bytes;
1106                 bytenr += num_bytes;
1107         }
1108         return 0;
1109 }
1110
1111 static int update_pinned_extents(struct btrfs_root *root,
1112                                 u64 bytenr, u64 num, int pin)
1113 {
1114         u64 len;
1115         struct btrfs_block_group_cache *cache;
1116         struct btrfs_fs_info *fs_info = root->fs_info;
1117
1118         if (pin) {
1119                 set_extent_dirty(&fs_info->pinned_extents,
1120                                 bytenr, bytenr + num - 1, GFP_NOFS);
1121         } else {
1122                 clear_extent_dirty(&fs_info->pinned_extents,
1123                                 bytenr, bytenr + num - 1, GFP_NOFS);
1124         }
1125         while (num > 0) {
1126                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1127                 WARN_ON(!cache);
1128                 len = min(num, cache->key.offset -
1129                           (bytenr - cache->key.objectid));
1130                 if (pin) {
1131                         cache->pinned += len;
1132                         cache->space_info->bytes_pinned += len;
1133                         fs_info->total_pinned += len;
1134                 } else {
1135                         cache->pinned -= len;
1136                         cache->space_info->bytes_pinned -= len;
1137                         fs_info->total_pinned -= len;
1138                 }
1139                 bytenr += len;
1140                 num -= len;
1141         }
1142         return 0;
1143 }
1144
1145 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1146 {
1147         u64 last = 0;
1148         u64 start;
1149         u64 end;
1150         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1151         int ret;
1152
1153         while(1) {
1154                 ret = find_first_extent_bit(pinned_extents, last,
1155                                             &start, &end, EXTENT_DIRTY);
1156                 if (ret)
1157                         break;
1158                 set_extent_dirty(copy, start, end, GFP_NOFS);
1159                 last = end + 1;
1160         }
1161         return 0;
1162 }
1163
1164 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1165                                struct btrfs_root *root,
1166                                struct extent_io_tree *unpin)
1167 {
1168         u64 start;
1169         u64 end;
1170         int ret;
1171         struct extent_io_tree *free_space_cache;
1172         free_space_cache = &root->fs_info->free_space_cache;
1173
1174         while(1) {
1175                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1176                                             EXTENT_DIRTY);
1177                 if (ret)
1178                         break;
1179                 update_pinned_extents(root, start, end + 1 - start, 0);
1180                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1181                 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1182         }
1183         return 0;
1184 }
1185
1186 static int finish_current_insert(struct btrfs_trans_handle *trans,
1187                                  struct btrfs_root *extent_root)
1188 {
1189         u64 start;
1190         u64 end;
1191         struct btrfs_fs_info *info = extent_root->fs_info;
1192         struct extent_buffer *eb;
1193         struct btrfs_path *path;
1194         struct btrfs_key ins;
1195         struct btrfs_disk_key first;
1196         struct btrfs_extent_item extent_item;
1197         int ret;
1198         int level;
1199         int err = 0;
1200
1201         btrfs_set_stack_extent_refs(&extent_item, 1);
1202         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1203         path = btrfs_alloc_path();
1204
1205         while(1) {
1206                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1207                                             &end, EXTENT_LOCKED);
1208                 if (ret)
1209                         break;
1210
1211                 ins.objectid = start;
1212                 ins.offset = end + 1 - start;
1213                 err = btrfs_insert_item(trans, extent_root, &ins,
1214                                         &extent_item, sizeof(extent_item));
1215                 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1216                                   GFP_NOFS);
1217                 eb = read_tree_block(extent_root, ins.objectid, ins.offset);
1218                 level = btrfs_header_level(eb);
1219                 if (level == 0) {
1220                         btrfs_item_key(eb, &first, 0);
1221                 } else {
1222                         btrfs_node_key(eb, &first, 0);
1223                 }
1224                 err = btrfs_insert_extent_backref(trans, extent_root, path,
1225                                           start, extent_root->root_key.objectid,
1226                                           0, level,
1227                                           btrfs_disk_key_objectid(&first));
1228                 BUG_ON(err);
1229                 free_extent_buffer(eb);
1230         }
1231         btrfs_free_path(path);
1232         return 0;
1233 }
1234
1235 static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1236                           int pending)
1237 {
1238         int err = 0;
1239         struct extent_buffer *buf;
1240
1241         if (!pending) {
1242                 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1243                 if (buf) {
1244                         if (btrfs_buffer_uptodate(buf)) {
1245                                 u64 transid =
1246                                     root->fs_info->running_transaction->transid;
1247                                 if (btrfs_header_generation(buf) == transid) {
1248                                         free_extent_buffer(buf);
1249                                         return 1;
1250                                 }
1251                         }
1252                         free_extent_buffer(buf);
1253                 }
1254                 update_pinned_extents(root, bytenr, num_bytes, 1);
1255         } else {
1256                 set_extent_bits(&root->fs_info->pending_del,
1257                                 bytenr, bytenr + num_bytes - 1,
1258                                 EXTENT_LOCKED, GFP_NOFS);
1259         }
1260         BUG_ON(err < 0);
1261         return 0;
1262 }
1263
1264 /*
1265  * remove an extent from the root, returns 0 on success
1266  */
1267 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1268                          *root, u64 bytenr, u64 num_bytes,
1269                          u64 root_objectid, u64 ref_generation,
1270                          u64 owner_objectid, u64 owner_offset, int pin,
1271                          int mark_free)
1272 {
1273         struct btrfs_path *path;
1274         struct btrfs_key key;
1275         struct btrfs_fs_info *info = root->fs_info;
1276         struct btrfs_extent_ops *ops = info->extent_ops;
1277         struct btrfs_root *extent_root = info->extent_root;
1278         struct extent_buffer *leaf;
1279         int ret;
1280         int extent_slot = 0;
1281         int found_extent = 0;
1282         int num_to_del = 1;
1283         struct btrfs_extent_item *ei;
1284         u32 refs;
1285
1286         key.objectid = bytenr;
1287         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1288         key.offset = num_bytes;
1289
1290         path = btrfs_alloc_path();
1291         if (!path)
1292                 return -ENOMEM;
1293
1294         ret = lookup_extent_backref(trans, extent_root, path,
1295                                     bytenr, root_objectid,
1296                                     ref_generation,
1297                                     owner_objectid, owner_offset, 1);
1298         if (ret == 0) {
1299                 struct btrfs_key found_key;
1300                 extent_slot = path->slots[0];
1301                 while(extent_slot > 0) {
1302                         extent_slot--;
1303                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1304                                               extent_slot);
1305                         if (found_key.objectid != bytenr)
1306                                 break;
1307                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1308                             found_key.offset == num_bytes) {
1309                                 found_extent = 1;
1310                                 break;
1311                         }
1312                         if (path->slots[0] - extent_slot > 5)
1313                                 break;
1314                 }
1315                 if (!found_extent)
1316                         ret = btrfs_del_item(trans, extent_root, path);
1317         } else {
1318                 btrfs_print_leaf(extent_root, path->nodes[0]);
1319                 WARN_ON(1);
1320                 printk("Unable to find ref byte nr %llu root %llu "
1321                        " gen %llu owner %llu offset %llu\n",
1322                        (unsigned long long)bytenr,
1323                        (unsigned long long)root_objectid,
1324                        (unsigned long long)ref_generation,
1325                        (unsigned long long)owner_objectid,
1326                        (unsigned long long)owner_offset);
1327         }
1328         if (!found_extent) {
1329                 btrfs_release_path(extent_root, path);
1330                 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1331                 if (ret < 0)
1332                         return ret;
1333                 BUG_ON(ret);
1334                 extent_slot = path->slots[0];
1335         }
1336
1337         leaf = path->nodes[0];
1338         ei = btrfs_item_ptr(leaf, extent_slot,
1339                             struct btrfs_extent_item);
1340         refs = btrfs_extent_refs(leaf, ei);
1341         BUG_ON(refs == 0);
1342         refs -= 1;
1343         btrfs_set_extent_refs(leaf, ei, refs);
1344
1345         btrfs_mark_buffer_dirty(leaf);
1346
1347         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1348                 /* if the back ref and the extent are next to each other
1349                  * they get deleted below in one shot
1350                  */
1351                 path->slots[0] = extent_slot;
1352                 num_to_del = 2;
1353         } else if (found_extent) {
1354                 /* otherwise delete the extent back ref */
1355                 ret = btrfs_del_item(trans, extent_root, path);
1356                 BUG_ON(ret);
1357                 /* if refs are 0, we need to setup the path for deletion */
1358                 if (refs == 0) {
1359                         btrfs_release_path(extent_root, path);
1360                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1361                                                 -1, 1);
1362                         if (ret < 0)
1363                                 return ret;
1364                         BUG_ON(ret);
1365                 }
1366         }
1367
1368         if (refs == 0) {
1369                 u64 super_used;
1370                 u64 root_used;
1371
1372                 if (pin) {
1373                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1374                         if (ret > 0)
1375                                 mark_free = 1;
1376                         BUG_ON(ret < 0);
1377                 }
1378
1379                 /* block accounting for super block */
1380                 super_used = btrfs_super_bytes_used(&info->super_copy);
1381                 btrfs_set_super_bytes_used(&info->super_copy,
1382                                            super_used - num_bytes);
1383
1384                 /* block accounting for root item */
1385                 root_used = btrfs_root_used(&root->root_item);
1386                 btrfs_set_root_used(&root->root_item,
1387                                            root_used - num_bytes);
1388                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1389                                       num_to_del);
1390                 if (ret)
1391                         return ret;
1392
1393                 if (ops && ops->free_extent)
1394                         ops->free_extent(root, bytenr, num_bytes);
1395
1396                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1397                                          mark_free);
1398                 BUG_ON(ret);
1399         }
1400         btrfs_free_path(path);
1401         finish_current_insert(trans, extent_root);
1402         return ret;
1403 }
1404
1405 /*
1406  * find all the blocks marked as pending in the radix tree and remove
1407  * them from the extent map
1408  */
1409 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1410                                btrfs_root *extent_root)
1411 {
1412         int ret;
1413         int err = 0;
1414         u64 start;
1415         u64 end;
1416         struct extent_io_tree *pending_del;
1417         struct extent_io_tree *pinned_extents;
1418
1419         pending_del = &extent_root->fs_info->pending_del;
1420         pinned_extents = &extent_root->fs_info->pinned_extents;
1421
1422         while(1) {
1423                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1424                                             EXTENT_LOCKED);
1425                 if (ret)
1426                         break;
1427                 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1428                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1429                                   GFP_NOFS);
1430                 ret = __free_extent(trans, extent_root,
1431                                      start, end + 1 - start,
1432                                      extent_root->root_key.objectid,
1433                                      0, 0, 0, 0, 0);
1434                 if (ret)
1435                         err = ret;
1436         }
1437         return err;
1438 }
1439
1440 /*
1441  * remove an extent from the root, returns 0 on success
1442  */
1443 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1444                       *root, u64 bytenr, u64 num_bytes,
1445                       u64 root_objectid, u64 ref_generation,
1446                       u64 owner_objectid, u64 owner_offset, int pin)
1447 {
1448         struct btrfs_root *extent_root = root->fs_info->extent_root;
1449         int pending_ret;
1450         int ret;
1451
1452         WARN_ON(num_bytes < root->sectorsize);
1453         if (!root->ref_cows)
1454                 ref_generation = 0;
1455
1456         if (root == extent_root) {
1457                 pin_down_bytes(root, bytenr, num_bytes, 1);
1458                 return 0;
1459         }
1460         ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1461                             ref_generation, owner_objectid, owner_offset,
1462                             pin, pin == 0);
1463         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1464         return ret ? ret : pending_ret;
1465 }
1466
1467 static u64 stripe_align(struct btrfs_root *root, u64 val)
1468 {
1469         u64 mask = ((u64)root->stripesize - 1);
1470         u64 ret = (val + mask) & ~mask;
1471         return ret;
1472 }
1473
1474 /*
1475  * walks the btree of allocated extents and find a hole of a given size.
1476  * The key ins is changed to record the hole:
1477  * ins->objectid == block start
1478  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1479  * ins->offset == number of blocks
1480  * Any available blocks before search_start are skipped.
1481  */
1482 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1483                                      struct btrfs_root *orig_root,
1484                                      u64 num_bytes, u64 empty_size,
1485                                      u64 search_start, u64 search_end,
1486                                      u64 hint_byte, struct btrfs_key *ins,
1487                                      u64 exclude_start, u64 exclude_nr,
1488                                      int data)
1489 {
1490         int ret;
1491         u64 orig_search_start = search_start;
1492         struct btrfs_root * root = orig_root->fs_info->extent_root;
1493         struct btrfs_fs_info *info = root->fs_info;
1494         u64 total_needed = num_bytes;
1495         struct btrfs_block_group_cache *block_group;
1496         int full_scan = 0;
1497         int wrapped = 0;
1498
1499         WARN_ON(num_bytes < root->sectorsize);
1500         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1501
1502         if (search_end == (u64)-1)
1503                 search_end = btrfs_super_total_bytes(&info->super_copy);
1504
1505         if (hint_byte) {
1506                 block_group = btrfs_lookup_block_group(info, hint_byte);
1507                 if (!block_group)
1508                         hint_byte = search_start;
1509                 block_group = btrfs_find_block_group(root, block_group,
1510                                                      hint_byte, data, 1);
1511         } else {
1512                 block_group = btrfs_find_block_group(root,
1513                                                      trans->block_group,
1514                                                      search_start, data, 1);
1515         }
1516
1517         total_needed += empty_size;
1518
1519 check_failed:
1520         if (!block_group) {
1521                 block_group = btrfs_lookup_block_group(info, search_start);
1522                 if (!block_group)
1523                         block_group = btrfs_lookup_block_group(info,
1524                                                        orig_search_start);
1525         }
1526         ret = find_search_start(root, &block_group, &search_start,
1527                                 total_needed, data);
1528         if (ret)
1529                 goto error;
1530
1531         search_start = stripe_align(root, search_start);
1532         ins->objectid = search_start;
1533         ins->offset = num_bytes;
1534
1535         if (ins->objectid + num_bytes >= search_end)
1536                 goto enospc;
1537
1538         if (ins->objectid + num_bytes >
1539             block_group->key.objectid + block_group->key.offset) {
1540                 search_start = block_group->key.objectid +
1541                         block_group->key.offset;
1542                 goto new_group;
1543         }
1544
1545         if (test_range_bit(&info->extent_ins, ins->objectid,
1546                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1547                 search_start = ins->objectid + num_bytes;
1548                 goto new_group;
1549         }
1550
1551         if (test_range_bit(&info->pinned_extents, ins->objectid,
1552                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1553                 search_start = ins->objectid + num_bytes;
1554                 goto new_group;
1555         }
1556
1557         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1558             ins->objectid < exclude_start + exclude_nr)) {
1559                 search_start = exclude_start + exclude_nr;
1560                 goto new_group;
1561         }
1562
1563         if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
1564                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1565                 if (block_group)
1566                         trans->block_group = block_group;
1567         }
1568         ins->offset = num_bytes;
1569         return 0;
1570
1571 new_group:
1572         if (search_start + num_bytes >= search_end) {
1573 enospc:
1574                 search_start = orig_search_start;
1575                 if (full_scan) {
1576                         ret = -ENOSPC;
1577                         goto error;
1578                 }
1579                 if (wrapped) {
1580                         if (!full_scan)
1581                                 total_needed -= empty_size;
1582                         full_scan = 1;
1583                 } else
1584                         wrapped = 1;
1585         }
1586         block_group = btrfs_lookup_block_group(info, search_start);
1587         cond_resched();
1588         block_group = btrfs_find_block_group(root, block_group,
1589                                              search_start, data, 0);
1590         goto check_failed;
1591
1592 error:
1593         return ret;
1594 }
1595 /*
1596  * finds a free extent and does all the dirty work required for allocation
1597  * returns the key for the extent through ins, and a tree buffer for
1598  * the first block of the extent through buf.
1599  *
1600  * returns 0 if everything worked, non-zero otherwise.
1601  */
1602 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1603                        struct btrfs_root *root,
1604                        u64 num_bytes, u64 root_objectid, u64 ref_generation,
1605                        u64 owner, u64 owner_offset,
1606                        u64 empty_size, u64 hint_byte,
1607                        u64 search_end, struct btrfs_key *ins, int data)
1608 {
1609         int ret;
1610         int pending_ret;
1611         u64 super_used, root_used;
1612         u64 search_start = 0;
1613         struct btrfs_fs_info *info = root->fs_info;
1614         struct btrfs_extent_ops *ops = info->extent_ops;
1615         u32 sizes[2];
1616         struct btrfs_root *extent_root = info->extent_root;
1617         struct btrfs_path *path;
1618         struct btrfs_extent_item *extent_item;
1619         struct btrfs_extent_ref *ref;
1620         struct btrfs_key keys[2];
1621         int extra_alloc_flags = 0;
1622
1623         if (btrfs_super_num_devices(&info->super_copy) > 1)
1624                 extra_alloc_flags = BTRFS_BLOCK_GROUP_RAID0;
1625
1626         if (data) {
1627                 data = BTRFS_BLOCK_GROUP_DATA | extra_alloc_flags;
1628         } else if (root == root->fs_info->chunk_root ||
1629                    info->force_system_allocs) {
1630                 data = BTRFS_BLOCK_GROUP_SYSTEM;
1631         } else {
1632                 data = BTRFS_BLOCK_GROUP_METADATA | extra_alloc_flags;
1633         }
1634
1635         if (root->ref_cows) {
1636                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
1637                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1638                                              num_bytes,
1639                                              BTRFS_BLOCK_GROUP_METADATA |
1640                                              extra_alloc_flags);
1641                         BUG_ON(ret);
1642                 }
1643                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
1644                                      num_bytes + 2 * 1024 * 1024, data);
1645                 BUG_ON(ret);
1646         }
1647
1648         WARN_ON(num_bytes < root->sectorsize);
1649         if (ops && ops->alloc_extent) {
1650                 ret = ops->alloc_extent(root, num_bytes, hint_byte, ins);
1651         } else {
1652                 ret = find_free_extent(trans, root, num_bytes, empty_size,
1653                                         search_start, search_end, hint_byte,
1654                                         ins, trans->alloc_exclude_start,
1655                                         trans->alloc_exclude_nr, data);
1656         }
1657         BUG_ON(ret);
1658         if (ret)
1659                 return ret;
1660
1661         /* block accounting for super block */
1662         super_used = btrfs_super_bytes_used(&info->super_copy);
1663         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1664
1665         /* block accounting for root item */
1666         root_used = btrfs_root_used(&root->root_item);
1667         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1668
1669         clear_extent_dirty(&root->fs_info->free_space_cache,
1670                            ins->objectid, ins->objectid + ins->offset - 1,
1671                            GFP_NOFS);
1672
1673         if (root == extent_root) {
1674                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1675                                 ins->objectid + ins->offset - 1,
1676                                 EXTENT_LOCKED, GFP_NOFS);
1677                 goto update_block;
1678         }
1679
1680         WARN_ON(trans->alloc_exclude_nr);
1681         trans->alloc_exclude_start = ins->objectid;
1682         trans->alloc_exclude_nr = ins->offset;
1683
1684         memcpy(&keys[0], ins, sizeof(*ins));
1685         keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1686                                          owner, owner_offset);
1687         keys[1].objectid = ins->objectid;
1688         keys[1].type = BTRFS_EXTENT_REF_KEY;
1689         sizes[0] = sizeof(*extent_item);
1690         sizes[1] = sizeof(*ref);
1691
1692         path = btrfs_alloc_path();
1693         BUG_ON(!path);
1694
1695         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
1696                                        sizes, 2);
1697
1698         BUG_ON(ret);
1699         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1700                                      struct btrfs_extent_item);
1701         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
1702         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
1703                              struct btrfs_extent_ref);
1704
1705         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
1706         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
1707         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
1708         btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
1709
1710         btrfs_mark_buffer_dirty(path->nodes[0]);
1711
1712         trans->alloc_exclude_start = 0;
1713         trans->alloc_exclude_nr = 0;
1714         btrfs_free_path(path);
1715         finish_current_insert(trans, extent_root);
1716         pending_ret = del_pending_extents(trans, extent_root);
1717
1718         if (ret) {
1719                 return ret;
1720         }
1721         if (pending_ret) {
1722                 return pending_ret;
1723         }
1724
1725 update_block:
1726         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
1727         if (ret) {
1728                 printk("update block group failed for %llu %llu\n",
1729                        (unsigned long long)ins->objectid,
1730                        (unsigned long long)ins->offset);
1731                 BUG();
1732         }
1733         return 0;
1734 }
1735
1736 /*
1737  * helper function to allocate a block for a given tree
1738  * returns the tree buffer or NULL.
1739  */
1740 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1741                                              struct btrfs_root *root,
1742                                              u32 blocksize,
1743                                              u64 root_objectid, u64 hint,
1744                                              u64 empty_size)
1745 {
1746         u64 ref_generation;
1747
1748         if (root->ref_cows)
1749                 ref_generation = trans->transid;
1750         else
1751                 ref_generation = 0;
1752
1753
1754         return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1755                                         ref_generation, 0, 0, hint, empty_size);
1756 }
1757
1758 /*
1759  * helper function to allocate a block for a given tree
1760  * returns the tree buffer or NULL.
1761  */
1762 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1763                                              struct btrfs_root *root,
1764                                              u32 blocksize,
1765                                              u64 root_objectid,
1766                                              u64 ref_generation,
1767                                              u64 first_objectid,
1768                                              int level,
1769                                              u64 hint,
1770                                              u64 empty_size)
1771 {
1772         struct btrfs_key ins;
1773         int ret;
1774         struct extent_buffer *buf;
1775
1776         ret = btrfs_alloc_extent(trans, root, blocksize,
1777                                  root_objectid, ref_generation,
1778                                  level, first_objectid, empty_size, hint,
1779                                  (u64)-1, &ins, 0);
1780         if (ret) {
1781                 BUG_ON(ret > 0);
1782                 return ERR_PTR(ret);
1783         }
1784         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1785         if (!buf) {
1786                 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1787                                   root->root_key.objectid, ref_generation,
1788                                   0, 0, 0);
1789                 BUG_ON(1);
1790                 return ERR_PTR(-ENOMEM);
1791         }
1792         btrfs_set_buffer_uptodate(buf);
1793         trans->blocks_used++;
1794         return buf;
1795 }
1796
1797 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1798                                   struct btrfs_root *root,
1799                                   struct extent_buffer *leaf)
1800 {
1801         u64 leaf_owner;
1802         u64 leaf_generation;
1803         struct btrfs_key key;
1804         struct btrfs_file_extent_item *fi;
1805         int i;
1806         int nritems;
1807         int ret;
1808
1809         BUG_ON(!btrfs_is_leaf(leaf));
1810         nritems = btrfs_header_nritems(leaf);
1811         leaf_owner = btrfs_header_owner(leaf);
1812         leaf_generation = btrfs_header_generation(leaf);
1813
1814         for (i = 0; i < nritems; i++) {
1815                 u64 disk_bytenr;
1816
1817                 btrfs_item_key_to_cpu(leaf, &key, i);
1818                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1819                         continue;
1820                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1821                 if (btrfs_file_extent_type(leaf, fi) ==
1822                     BTRFS_FILE_EXTENT_INLINE)
1823                         continue;
1824                 /*
1825                  * FIXME make sure to insert a trans record that
1826                  * repeats the snapshot del on crash
1827                  */
1828                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1829                 if (disk_bytenr == 0)
1830                         continue;
1831                 ret = btrfs_free_extent(trans, root, disk_bytenr,
1832                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
1833                                 leaf_owner, leaf_generation,
1834                                 key.objectid, key.offset, 0);
1835                 BUG_ON(ret);
1836         }
1837         return 0;
1838 }
1839
1840 static void noinline reada_walk_down(struct btrfs_root *root,
1841                                      struct extent_buffer *node,
1842                                      int slot)
1843 {
1844         u64 bytenr;
1845         u64 last = 0;
1846         u32 nritems;
1847         u32 refs;
1848         u32 blocksize;
1849         int ret;
1850         int i;
1851         int level;
1852         int skipped = 0;
1853
1854         nritems = btrfs_header_nritems(node);
1855         level = btrfs_header_level(node);
1856         if (level)
1857                 return;
1858
1859         for (i = slot; i < nritems && skipped < 32; i++) {
1860                 bytenr = btrfs_node_blockptr(node, i);
1861                 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1862                              (last > bytenr && last - bytenr > 32 * 1024))) {
1863                         skipped++;
1864                         continue;
1865                 }
1866                 blocksize = btrfs_level_size(root, level - 1);
1867                 if (i != slot) {
1868                         ret = lookup_extent_ref(NULL, root, bytenr,
1869                                                 blocksize, &refs);
1870                         BUG_ON(ret);
1871                         if (refs != 1) {
1872                                 skipped++;
1873                                 continue;
1874                         }
1875                 }
1876                 mutex_unlock(&root->fs_info->fs_mutex);
1877                 ret = readahead_tree_block(root, bytenr, blocksize);
1878                 last = bytenr + blocksize;
1879                 cond_resched();
1880                 mutex_lock(&root->fs_info->fs_mutex);
1881                 if (ret)
1882                         break;
1883         }
1884 }
1885
1886 /*
1887  * helper function for drop_snapshot, this walks down the tree dropping ref
1888  * counts as it goes.
1889  */
1890 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1891                                    struct btrfs_root *root,
1892                                    struct btrfs_path *path, int *level)
1893 {
1894         u64 root_owner;
1895         u64 root_gen;
1896         u64 bytenr;
1897         struct extent_buffer *next;
1898         struct extent_buffer *cur;
1899         struct extent_buffer *parent;
1900         u32 blocksize;
1901         int ret;
1902         u32 refs;
1903
1904         WARN_ON(*level < 0);
1905         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1906         ret = lookup_extent_ref(trans, root,
1907                                 path->nodes[*level]->start,
1908                                 path->nodes[*level]->len, &refs);
1909         BUG_ON(ret);
1910         if (refs > 1)
1911                 goto out;
1912
1913         /*
1914          * walk down to the last node level and free all the leaves
1915          */
1916         while(*level >= 0) {
1917                 WARN_ON(*level < 0);
1918                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1919                 cur = path->nodes[*level];
1920
1921                 if (btrfs_header_level(cur) != *level)
1922                         WARN_ON(1);
1923
1924                 if (path->slots[*level] >=
1925                     btrfs_header_nritems(cur))
1926                         break;
1927                 if (*level == 0) {
1928                         ret = drop_leaf_ref(trans, root, cur);
1929                         BUG_ON(ret);
1930                         break;
1931                 }
1932                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1933                 blocksize = btrfs_level_size(root, *level - 1);
1934                 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1935                 BUG_ON(ret);
1936                 if (refs != 1) {
1937                         parent = path->nodes[*level];
1938                         root_owner = btrfs_header_owner(parent);
1939                         root_gen = btrfs_header_generation(parent);
1940                         path->slots[*level]++;
1941                         ret = btrfs_free_extent(trans, root, bytenr,
1942                                                 blocksize, root_owner,
1943                                                 root_gen, 0, 0, 1);
1944                         BUG_ON(ret);
1945                         continue;
1946                 }
1947                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1948                 if (!next || !btrfs_buffer_uptodate(next)) {
1949                         free_extent_buffer(next);
1950                         reada_walk_down(root, cur, path->slots[*level]);
1951                         mutex_unlock(&root->fs_info->fs_mutex);
1952                         next = read_tree_block(root, bytenr, blocksize);
1953                         mutex_lock(&root->fs_info->fs_mutex);
1954
1955                         /* we dropped the lock, check one more time */
1956                         ret = lookup_extent_ref(trans, root, bytenr,
1957                                                 blocksize, &refs);
1958                         BUG_ON(ret);
1959                         if (refs != 1) {
1960                                 parent = path->nodes[*level];
1961                                 root_owner = btrfs_header_owner(parent);
1962                                 root_gen = btrfs_header_generation(parent);
1963
1964                                 path->slots[*level]++;
1965                                 free_extent_buffer(next);
1966                                 ret = btrfs_free_extent(trans, root, bytenr,
1967                                                         blocksize,
1968                                                         root_owner,
1969                                                         root_gen, 0, 0, 1);
1970                                 BUG_ON(ret);
1971                                 continue;
1972                         }
1973                 }
1974                 WARN_ON(*level <= 0);
1975                 if (path->nodes[*level-1])
1976                         free_extent_buffer(path->nodes[*level-1]);
1977                 path->nodes[*level-1] = next;
1978                 *level = btrfs_header_level(next);
1979                 path->slots[*level] = 0;
1980         }
1981 out:
1982         WARN_ON(*level < 0);
1983         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1984
1985         if (path->nodes[*level] == root->node) {
1986                 root_owner = root->root_key.objectid;
1987                 parent = path->nodes[*level];
1988         } else {
1989                 parent = path->nodes[*level + 1];
1990                 root_owner = btrfs_header_owner(parent);
1991         }
1992
1993         root_gen = btrfs_header_generation(parent);
1994         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1995                                 path->nodes[*level]->len,
1996                                 root_owner, root_gen, 0, 0, 1);
1997         free_extent_buffer(path->nodes[*level]);
1998         path->nodes[*level] = NULL;
1999         *level += 1;
2000         BUG_ON(ret);
2001         return 0;
2002 }
2003
2004 /*
2005  * helper for dropping snapshots.  This walks back up the tree in the path
2006  * to find the first node higher up where we haven't yet gone through
2007  * all the slots
2008  */
2009 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2010                                  struct btrfs_root *root,
2011                                  struct btrfs_path *path, int *level)
2012 {
2013         u64 root_owner;
2014         u64 root_gen;
2015         struct btrfs_root_item *root_item = &root->root_item;
2016         int i;
2017         int slot;
2018         int ret;
2019
2020         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2021                 slot = path->slots[i];
2022                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2023                         struct extent_buffer *node;
2024                         struct btrfs_disk_key disk_key;
2025                         node = path->nodes[i];
2026                         path->slots[i]++;
2027                         *level = i;
2028                         WARN_ON(*level == 0);
2029                         btrfs_node_key(node, &disk_key, path->slots[i]);
2030                         memcpy(&root_item->drop_progress,
2031                                &disk_key, sizeof(disk_key));
2032                         root_item->drop_level = i;
2033                         return 0;
2034                 } else {
2035                         if (path->nodes[*level] == root->node) {
2036                                 root_owner = root->root_key.objectid;
2037                                 root_gen =
2038                                    btrfs_header_generation(path->nodes[*level]);
2039                         } else {
2040                                 struct extent_buffer *node;
2041                                 node = path->nodes[*level + 1];
2042                                 root_owner = btrfs_header_owner(node);
2043                                 root_gen = btrfs_header_generation(node);
2044                         }
2045                         ret = btrfs_free_extent(trans, root,
2046                                                 path->nodes[*level]->start,
2047                                                 path->nodes[*level]->len,
2048                                                 root_owner, root_gen, 0, 0, 1);
2049                         BUG_ON(ret);
2050                         free_extent_buffer(path->nodes[*level]);
2051                         path->nodes[*level] = NULL;
2052                         *level = i + 1;
2053                 }
2054         }
2055         return 1;
2056 }
2057
2058 /*
2059  * drop the reference count on the tree rooted at 'snap'.  This traverses
2060  * the tree freeing any blocks that have a ref count of zero after being
2061  * decremented.
2062  */
2063 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2064                         *root)
2065 {
2066         int ret = 0;
2067         int wret;
2068         int level;
2069         struct btrfs_path *path;
2070         int i;
2071         int orig_level;
2072         struct btrfs_root_item *root_item = &root->root_item;
2073
2074         path = btrfs_alloc_path();
2075         BUG_ON(!path);
2076
2077         level = btrfs_header_level(root->node);
2078         orig_level = level;
2079         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2080                 path->nodes[level] = root->node;
2081                 extent_buffer_get(root->node);
2082                 path->slots[level] = 0;
2083         } else {
2084                 struct btrfs_key key;
2085                 struct btrfs_disk_key found_key;
2086                 struct extent_buffer *node;
2087
2088                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2089                 level = root_item->drop_level;
2090                 path->lowest_level = level;
2091                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2092                 if (wret < 0) {
2093                         ret = wret;
2094                         goto out;
2095                 }
2096                 node = path->nodes[level];
2097                 btrfs_node_key(node, &found_key, path->slots[level]);
2098                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2099                                sizeof(found_key)));
2100         }
2101         while(1) {
2102                 wret = walk_down_tree(trans, root, path, &level);
2103                 if (wret < 0)
2104                         ret = wret;
2105                 if (wret != 0)
2106                         break;
2107
2108                 wret = walk_up_tree(trans, root, path, &level);
2109                 if (wret < 0)
2110                         ret = wret;
2111                 if (wret != 0)
2112                         break;
2113                 /*
2114                 ret = -EAGAIN;
2115                 break;
2116                 */
2117         }
2118         for (i = 0; i <= orig_level; i++) {
2119                 if (path->nodes[i]) {
2120                         free_extent_buffer(path->nodes[i]);
2121                         path->nodes[i] = NULL;
2122                 }
2123         }
2124 out:
2125         btrfs_free_path(path);
2126         return ret;
2127 }
2128
2129 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2130 {
2131         u64 start;
2132         u64 end;
2133         u64 ptr;
2134         int ret;
2135         while(1) {
2136                 ret = find_first_extent_bit(&info->block_group_cache, 0,
2137                                             &start, &end, (unsigned int)-1);
2138                 if (ret)
2139                         break;
2140                 ret = get_state_private(&info->block_group_cache, start, &ptr);
2141                 if (!ret)
2142                         kfree((void *)(unsigned long)ptr);
2143                 clear_extent_bits(&info->block_group_cache, start,
2144                                   end, (unsigned int)-1, GFP_NOFS);
2145         }
2146         while(1) {
2147                 ret = find_first_extent_bit(&info->free_space_cache, 0,
2148                                             &start, &end, EXTENT_DIRTY);
2149                 if (ret)
2150                         break;
2151                 clear_extent_dirty(&info->free_space_cache, start,
2152                                    end, GFP_NOFS);
2153         }
2154         return 0;
2155 }
2156
2157 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
2158                            struct btrfs_key *key)
2159 {
2160         int ret;
2161         struct btrfs_key found_key;
2162         struct extent_buffer *leaf;
2163         int slot;
2164
2165         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
2166         if (ret < 0)
2167                 return ret;
2168         while(1) {
2169                 slot = path->slots[0];
2170                 leaf = path->nodes[0];
2171                 if (slot >= btrfs_header_nritems(leaf)) {
2172                         ret = btrfs_next_leaf(root, path);
2173                         if (ret == 0)
2174                                 continue;
2175                         if (ret < 0)
2176                                 goto error;
2177                         break;
2178                 }
2179                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2180
2181                 if (found_key.objectid >= key->objectid &&
2182                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
2183                         return 0;
2184                 path->slots[0]++;
2185         }
2186         ret = -ENOENT;
2187 error:
2188         return ret;
2189 }
2190
2191 int btrfs_read_block_groups(struct btrfs_root *root)
2192 {
2193         struct btrfs_path *path;
2194         int ret;
2195         int bit;
2196         struct btrfs_block_group_cache *cache;
2197         struct btrfs_fs_info *info = root->fs_info;
2198         struct btrfs_space_info *space_info;
2199         struct extent_io_tree *block_group_cache;
2200         struct btrfs_key key;
2201         struct btrfs_key found_key;
2202         struct extent_buffer *leaf;
2203
2204         block_group_cache = &info->block_group_cache;
2205
2206         root = info->extent_root;
2207         key.objectid = 0;
2208         key.offset = 0;
2209         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2210         path = btrfs_alloc_path();
2211         if (!path)
2212                 return -ENOMEM;
2213
2214         while(1) {
2215                 ret = find_first_block_group(root, path, &key);
2216                 if (ret > 0) {
2217                         ret = 0;
2218                         goto error;
2219                 }
2220                 if (ret != 0) {
2221                         goto error;
2222                 }
2223                 leaf = path->nodes[0];
2224                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2225                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2226                 if (!cache) {
2227                         ret = -ENOMEM;
2228                         break;
2229                 }
2230
2231                 read_extent_buffer(leaf, &cache->item,
2232                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
2233                                    sizeof(cache->item));
2234                 memcpy(&cache->key, &found_key, sizeof(found_key));
2235                 cache->cached = 0;
2236                 cache->pinned = 0;
2237                 key.objectid = found_key.objectid + found_key.offset;
2238                 btrfs_release_path(root, path);
2239                 cache->flags = btrfs_block_group_flags(&cache->item);
2240                 bit = 0;
2241                 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
2242                         bit = BLOCK_GROUP_DATA;
2243                 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
2244                         bit = BLOCK_GROUP_SYSTEM;
2245                 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
2246                         bit = BLOCK_GROUP_METADATA;
2247                 }
2248
2249                 ret = update_space_info(info, cache->flags, found_key.offset,
2250                                         btrfs_block_group_used(&cache->item),
2251                                         &space_info);
2252                 BUG_ON(ret);
2253                 cache->space_info = space_info;
2254
2255                 /* use EXTENT_LOCKED to prevent merging */
2256                 set_extent_bits(block_group_cache, found_key.objectid,
2257                                 found_key.objectid + found_key.offset - 1,
2258                                 bit | EXTENT_LOCKED, GFP_NOFS);
2259                 set_state_private(block_group_cache, found_key.objectid,
2260                                   (unsigned long)cache);
2261
2262                 if (key.objectid >=
2263                     btrfs_super_total_bytes(&info->super_copy))
2264                         break;
2265         }
2266         ret = 0;
2267 error:
2268         btrfs_free_path(path);
2269         return ret;
2270 }
2271
2272 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
2273                            struct btrfs_root *root, u64 bytes_used,
2274                            u64 type, u64 chunk_tree, u64 chunk_objectid,
2275                            u64 size)
2276 {
2277         int ret;
2278         int bit = 0;
2279         struct btrfs_root *extent_root;
2280         struct btrfs_block_group_cache *cache;
2281         struct extent_io_tree *block_group_cache;
2282
2283         extent_root = root->fs_info->extent_root;
2284         block_group_cache = &root->fs_info->block_group_cache;
2285
2286         cache = kmalloc(sizeof(*cache), GFP_NOFS);
2287         BUG_ON(!cache);
2288         cache->key.objectid = chunk_objectid;
2289         cache->key.offset = size;
2290         cache->cached = 0;
2291         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2292         memset(&cache->item, 0, sizeof(cache->item));
2293         btrfs_set_block_group_used(&cache->item, bytes_used);
2294         btrfs_set_block_group_chunk_tree(&cache->item, chunk_tree);
2295         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
2296         cache->flags = type;
2297         btrfs_set_block_group_flags(&cache->item, type);
2298
2299         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
2300                                 &cache->space_info);
2301         BUG_ON(ret);
2302
2303         if (type & BTRFS_BLOCK_GROUP_DATA) {
2304                 bit = BLOCK_GROUP_DATA;
2305         } else if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
2306                 bit = BLOCK_GROUP_SYSTEM;
2307         } else if (type & BTRFS_BLOCK_GROUP_METADATA) {
2308                 bit = BLOCK_GROUP_METADATA;
2309         }
2310         set_extent_bits(block_group_cache, chunk_objectid,
2311                         chunk_objectid + size - 1,
2312                         bit | EXTENT_LOCKED, GFP_NOFS);
2313         set_state_private(block_group_cache, chunk_objectid,
2314                           (unsigned long)cache);
2315
2316         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
2317                                 sizeof(cache->item));
2318         BUG_ON(ret);
2319
2320         finish_current_insert(trans, extent_root);
2321         ret = del_pending_extents(trans, extent_root);
2322         BUG_ON(ret);
2323         return 0;
2324 }
2325
2326 u64 btrfs_hash_extent_ref(u64 root_objectid, u64 ref_generation,
2327                           u64 owner, u64 owner_offset)
2328 {
2329         return hash_extent_ref(root_objectid, ref_generation,
2330                                owner, owner_offset);
2331 }
2332
2333 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
2334                              struct btrfs_root *root,
2335                              u64 bytenr, u64 num_bytes, int alloc,
2336                              int mark_free)
2337 {
2338         return update_block_group(trans, root, bytenr, num_bytes,
2339                                   alloc, mark_free);
2340 }