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