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_extent_ops *ops = info->extent_ops;
1213         struct btrfs_root *extent_root = info->extent_root;
1214         struct extent_buffer *leaf;
1215         int ret;
1216         struct btrfs_extent_item *ei;
1217         u32 refs;
1218
1219         key.objectid = bytenr;
1220         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1221         key.offset = num_bytes;
1222
1223         path = btrfs_alloc_path();
1224         if (!path)
1225                 return -ENOMEM;
1226
1227         ret = lookup_extent_backref(trans, extent_root, path,
1228                                     bytenr, root_objectid,
1229                                     ref_generation,
1230                                     owner_objectid, owner_offset, 1);
1231         if (ret == 0) {
1232                 ret = btrfs_del_item(trans, extent_root, path);
1233         } else {
1234                 btrfs_print_leaf(extent_root, path->nodes[0]);
1235                 WARN_ON(1);
1236                 printk("Unable to find ref byte nr %Lu root %Lu "
1237                        " gen %Lu owner %Lu offset %Lu\n", bytenr,
1238                        root_objectid, ref_generation, owner_objectid,
1239                        owner_offset);
1240         }
1241         btrfs_release_path(extent_root, path);
1242         ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1243         if (ret < 0)
1244                 return ret;
1245         BUG_ON(ret);
1246
1247         leaf = path->nodes[0];
1248         ei = btrfs_item_ptr(leaf, path->slots[0],
1249                             struct btrfs_extent_item);
1250         refs = btrfs_extent_refs(leaf, ei);
1251         BUG_ON(refs == 0);
1252         refs -= 1;
1253         btrfs_set_extent_refs(leaf, ei, refs);
1254         btrfs_mark_buffer_dirty(leaf);
1255
1256         if (refs == 0) {
1257                 u64 super_used;
1258                 u64 root_used;
1259
1260                 if (pin) {
1261                         ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1262                         if (ret > 0)
1263                                 mark_free = 1;
1264                         BUG_ON(ret < 0);
1265                 }
1266
1267                 /* block accounting for super block */
1268                 super_used = btrfs_super_bytes_used(&info->super_copy);
1269                 btrfs_set_super_bytes_used(&info->super_copy,
1270                                            super_used - num_bytes);
1271
1272                 /* block accounting for root item */
1273                 root_used = btrfs_root_used(&root->root_item);
1274                 btrfs_set_root_used(&root->root_item,
1275                                            root_used - num_bytes);
1276                 ret = btrfs_del_item(trans, extent_root, path);
1277                 if (ret)
1278                         return ret;
1279
1280                 if (ops && ops->free_extent)
1281                         ops->free_extent(root, bytenr, num_bytes);
1282
1283                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1284                                          mark_free, 0);
1285                 BUG_ON(ret);
1286         }
1287         btrfs_free_path(path);
1288         finish_current_insert(trans, extent_root);
1289         return ret;
1290 }
1291
1292 /*
1293  * find all the blocks marked as pending in the radix tree and remove
1294  * them from the extent map
1295  */
1296 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1297                                btrfs_root *extent_root)
1298 {
1299         int ret;
1300         int err = 0;
1301         u64 start;
1302         u64 end;
1303         struct extent_map_tree *pending_del;
1304         struct extent_map_tree *pinned_extents;
1305
1306         pending_del = &extent_root->fs_info->pending_del;
1307         pinned_extents = &extent_root->fs_info->pinned_extents;
1308
1309         while(1) {
1310                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1311                                             EXTENT_LOCKED);
1312                 if (ret)
1313                         break;
1314                 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1315                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1316                                   GFP_NOFS);
1317                 ret = __free_extent(trans, extent_root,
1318                                      start, end + 1 - start,
1319                                      extent_root->root_key.objectid,
1320                                      0, 0, 0, 0, 0);
1321                 if (ret)
1322                         err = ret;
1323         }
1324         return err;
1325 }
1326
1327 /*
1328  * remove an extent from the root, returns 0 on success
1329  */
1330 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1331                       *root, u64 bytenr, u64 num_bytes,
1332                       u64 root_objectid, u64 ref_generation,
1333                       u64 owner_objectid, u64 owner_offset, int pin)
1334 {
1335         struct btrfs_root *extent_root = root->fs_info->extent_root;
1336         int pending_ret;
1337         int ret;
1338
1339         WARN_ON(num_bytes < root->sectorsize);
1340         if (!root->ref_cows)
1341                 ref_generation = 0;
1342
1343         if (root == extent_root) {
1344                 pin_down_bytes(root, bytenr, num_bytes, 1);
1345                 return 0;
1346         }
1347         ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1348                             ref_generation, owner_objectid, owner_offset,
1349                             pin, pin == 0);
1350         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1351         return ret ? ret : pending_ret;
1352 }
1353
1354 static u64 stripe_align(struct btrfs_root *root, u64 val)
1355 {
1356         u64 mask = ((u64)root->stripesize - 1);
1357         u64 ret = (val + mask) & ~mask;
1358         return ret;
1359 }
1360
1361 /*
1362  * walks the btree of allocated extents and find a hole of a given size.
1363  * The key ins is changed to record the hole:
1364  * ins->objectid == block start
1365  * ins->flags = BTRFS_EXTENT_ITEM_KEY
1366  * ins->offset == number of blocks
1367  * Any available blocks before search_start are skipped.
1368  */
1369 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1370                                      struct btrfs_root *orig_root,
1371                                      u64 num_bytes, u64 empty_size,
1372                                      u64 search_start, u64 search_end,
1373                                      u64 hint_byte, struct btrfs_key *ins,
1374                                      u64 exclude_start, u64 exclude_nr,
1375                                      int data)
1376 {
1377         struct btrfs_path *path;
1378         struct btrfs_key key;
1379         u64 hole_size = 0;
1380         u64 aligned;
1381         int ret;
1382         int slot = 0;
1383         u64 last_byte = 0;
1384         u64 orig_search_start = search_start;
1385         int start_found;
1386         struct extent_buffer *l;
1387         struct btrfs_root * root = orig_root->fs_info->extent_root;
1388         struct btrfs_fs_info *info = root->fs_info;
1389         u64 total_needed = num_bytes;
1390         int level;
1391         struct btrfs_block_group_cache *block_group;
1392         int full_scan = 0;
1393         int wrapped = 0;
1394         u64 cached_start;
1395
1396         WARN_ON(num_bytes < root->sectorsize);
1397         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1398
1399         level = btrfs_header_level(root->node);
1400
1401         if (num_bytes >= 32 * 1024 * 1024 && hint_byte) {
1402                 data = BTRFS_BLOCK_GROUP_MIXED;
1403         }
1404
1405         if (search_end == (u64)-1)
1406                 search_end = btrfs_super_total_bytes(&info->super_copy);
1407         if (hint_byte) {
1408                 block_group = btrfs_lookup_block_group(info, hint_byte);
1409                 if (!block_group)
1410                         hint_byte = search_start;
1411                 block_group = btrfs_find_block_group(root, block_group,
1412                                                      hint_byte, data, 1);
1413         } else {
1414                 block_group = btrfs_find_block_group(root,
1415                                                      trans->block_group,
1416                                                      search_start, data, 1);
1417         }
1418
1419         total_needed += empty_size;
1420         path = btrfs_alloc_path();
1421 check_failed:
1422         if (!block_group) {
1423                 block_group = btrfs_lookup_block_group(info, search_start);
1424                 if (!block_group)
1425                         block_group = btrfs_lookup_block_group(info,
1426                                                        orig_search_start);
1427         }
1428         search_start = find_search_start(root, &block_group, search_start,
1429                                          total_needed, data, full_scan);
1430         search_start = stripe_align(root, search_start);
1431         cached_start = search_start;
1432         btrfs_init_path(path);
1433         ins->objectid = search_start;
1434         ins->offset = 0;
1435         start_found = 0;
1436         path->reada = 2;
1437
1438         ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1439         if (ret < 0)
1440                 goto error;
1441
1442         if (path->slots[0] > 0) {
1443                 path->slots[0]--;
1444         }
1445
1446         l = path->nodes[0];
1447         btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1448
1449         /*
1450          * walk backwards to find the first extent item key
1451          */
1452         while(btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1453                 if (path->slots[0] == 0) {
1454                         ret = btrfs_prev_leaf(root, path);
1455                         if (ret != 0) {
1456                                 ret = btrfs_search_slot(trans, root, ins,
1457                                                         path, 0, 0);
1458                                 if (ret < 0)
1459                                         goto error;
1460                                 if (path->slots[0] > 0)
1461                                         path->slots[0]--;
1462                                 break;
1463                         }
1464                 } else {
1465                         path->slots[0]--;
1466                 }
1467                 l = path->nodes[0];
1468                 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1469         }
1470         while (1) {
1471                 l = path->nodes[0];
1472                 slot = path->slots[0];
1473                 if (slot >= btrfs_header_nritems(l)) {
1474                         ret = btrfs_next_leaf(root, path);
1475                         if (ret == 0)
1476                                 continue;
1477                         if (ret < 0)
1478                                 goto error;
1479
1480                         search_start = max(search_start,
1481                                            block_group->key.objectid);
1482                         if (!start_found) {
1483                                 aligned = stripe_align(root, search_start);
1484                                 ins->objectid = aligned;
1485                                 if (aligned >= search_end) {
1486                                         ret = -ENOSPC;
1487                                         goto error;
1488                                 }
1489                                 ins->offset = search_end - aligned;
1490                                 start_found = 1;
1491                                 goto check_pending;
1492                         }
1493                         ins->objectid = stripe_align(root,
1494                                                      last_byte > search_start ?
1495                                                      last_byte : search_start);
1496                         if (search_end <= ins->objectid) {
1497                                 ret = -ENOSPC;
1498                                 goto error;
1499                         }
1500                         ins->offset = search_end - ins->objectid;
1501                         BUG_ON(ins->objectid >= search_end);
1502                         goto check_pending;
1503                 }
1504                 btrfs_item_key_to_cpu(l, &key, slot);
1505
1506                 if (key.objectid >= search_start && key.objectid > last_byte &&
1507                     start_found) {
1508                         if (last_byte < search_start)
1509                                 last_byte = search_start;
1510                         aligned = stripe_align(root, last_byte);
1511                         hole_size = key.objectid - aligned;
1512                         if (key.objectid > aligned && hole_size >= num_bytes) {
1513                                 ins->objectid = aligned;
1514                                 ins->offset = hole_size;
1515                                 goto check_pending;
1516                         }
1517                 }
1518                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1519                         if (!start_found && btrfs_key_type(&key) ==
1520                             BTRFS_BLOCK_GROUP_ITEM_KEY) {
1521                                 last_byte = key.objectid;
1522                                 start_found = 1;
1523                         }
1524                         goto next;
1525                 }
1526
1527
1528                 start_found = 1;
1529                 last_byte = key.objectid + key.offset;
1530
1531                 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1532                     last_byte >= block_group->key.objectid +
1533                     block_group->key.offset) {
1534                         btrfs_release_path(root, path);
1535                         search_start = block_group->key.objectid +
1536                                 block_group->key.offset;
1537                         goto new_group;
1538                 }
1539 next:
1540                 path->slots[0]++;
1541                 cond_resched();
1542         }
1543 check_pending:
1544         /* we have to make sure we didn't find an extent that has already
1545          * been allocated by the map tree or the original allocation
1546          */
1547         btrfs_release_path(root, path);
1548         BUG_ON(ins->objectid < search_start);
1549
1550         if (ins->objectid + num_bytes >= search_end)
1551                 goto enospc;
1552         if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1553             ins->objectid + num_bytes > block_group->
1554             key.objectid + block_group->key.offset) {
1555                 search_start = block_group->key.objectid +
1556                         block_group->key.offset;
1557                 goto new_group;
1558         }
1559         if (test_range_bit(&info->extent_ins, ins->objectid,
1560                            ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1561                 search_start = ins->objectid + num_bytes;
1562                 goto new_group;
1563         }
1564         if (test_range_bit(&info->pinned_extents, ins->objectid,
1565                            ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1566                 search_start = ins->objectid + num_bytes;
1567                 goto new_group;
1568         }
1569         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1570             ins->objectid < exclude_start + exclude_nr)) {
1571                 search_start = exclude_start + exclude_nr;
1572                 goto new_group;
1573         }
1574         if (!data) {
1575                 block_group = btrfs_lookup_block_group(info, ins->objectid);
1576                 if (block_group)
1577                         trans->block_group = block_group;
1578         }
1579         ins->offset = num_bytes;
1580         btrfs_free_path(path);
1581         return 0;
1582
1583 new_group:
1584         if (search_start + num_bytes >= search_end) {
1585 enospc:
1586                 search_start = orig_search_start;
1587                 if (full_scan) {
1588                         ret = -ENOSPC;
1589                         goto error;
1590                 }
1591                 if (wrapped) {
1592                         if (!full_scan)
1593                                 total_needed -= empty_size;
1594                         full_scan = 1;
1595                         data = BTRFS_BLOCK_GROUP_MIXED;
1596                 } else
1597                         wrapped = 1;
1598         }
1599         block_group = btrfs_lookup_block_group(info, search_start);
1600         cond_resched();
1601         block_group = btrfs_find_block_group(root, block_group,
1602                                              search_start, data, 0);
1603         goto check_failed;
1604
1605 error:
1606         btrfs_release_path(root, path);
1607         btrfs_free_path(path);
1608         return ret;
1609 }
1610 /*
1611  * finds a free extent and does all the dirty work required for allocation
1612  * returns the key for the extent through ins, and a tree buffer for
1613  * the first block of the extent through buf.
1614  *
1615  * returns 0 if everything worked, non-zero otherwise.
1616  */
1617 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1618                        struct btrfs_root *root,
1619                        u64 num_bytes, u64 root_objectid, u64 ref_generation,
1620                        u64 owner, u64 owner_offset,
1621                        u64 empty_size, u64 hint_byte,
1622                        u64 search_end, struct btrfs_key *ins, int data)
1623 {
1624         int ret;
1625         int pending_ret;
1626         u64 super_used, root_used;
1627         u64 search_start = 0;
1628         /*
1629         u64 new_hint;
1630         */
1631         struct btrfs_fs_info *info = root->fs_info;
1632         struct btrfs_extent_ops *ops = info->extent_ops;
1633         struct btrfs_root *extent_root = info->extent_root;
1634         struct btrfs_extent_item extent_item;
1635         struct btrfs_path *path;
1636
1637         btrfs_set_stack_extent_refs(&extent_item, 1);
1638
1639         /*
1640         new_hint = max(hint_byte, root->fs_info->alloc_start);
1641         if (new_hint < btrfs_super_total_bytes(&info->super_copy))
1642                 hint_byte = new_hint;
1643         */
1644         WARN_ON(num_bytes < root->sectorsize);
1645         if (ops && ops->alloc_extent) {
1646                 ret = ops->alloc_extent(root, num_bytes, hint_byte, ins);
1647         } else {
1648                 ret = find_free_extent(trans, root, num_bytes, empty_size,
1649                                         search_start, search_end, hint_byte,
1650                                         ins, trans->alloc_exclude_start,
1651                                         trans->alloc_exclude_nr, data);
1652         }
1653         BUG_ON(ret);
1654         if (ret)
1655                 return ret;
1656
1657         /* block accounting for super block */
1658         super_used = btrfs_super_bytes_used(&info->super_copy);
1659         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1660
1661         /* block accounting for root item */
1662         root_used = btrfs_root_used(&root->root_item);
1663         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1664
1665         clear_extent_dirty(&root->fs_info->free_space_cache,
1666                            ins->objectid, ins->objectid + ins->offset - 1,
1667                            GFP_NOFS);
1668
1669         if (root == extent_root) {
1670                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1671                                 ins->objectid + ins->offset - 1,
1672                                 EXTENT_LOCKED, GFP_NOFS);
1673                 WARN_ON(data == 1);
1674                 goto update_block;
1675         }
1676
1677         WARN_ON(trans->alloc_exclude_nr);
1678         trans->alloc_exclude_start = ins->objectid;
1679         trans->alloc_exclude_nr = ins->offset;
1680         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1681                                 sizeof(extent_item));
1682
1683         trans->alloc_exclude_start = 0;
1684         trans->alloc_exclude_nr = 0;
1685         BUG_ON(ret);
1686
1687         path = btrfs_alloc_path();
1688         BUG_ON(!path);
1689         ret = btrfs_insert_extent_backref(trans, extent_root, path,
1690                                           ins->objectid, root_objectid,
1691                                           ref_generation, owner, owner_offset);
1692
1693         BUG_ON(ret);
1694         btrfs_free_path(path);
1695         finish_current_insert(trans, extent_root);
1696         pending_ret = del_pending_extents(trans, extent_root);
1697
1698         if (ret) {
1699                 return ret;
1700         }
1701         if (pending_ret) {
1702                 return pending_ret;
1703         }
1704
1705 update_block:
1706         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1707                                  data);
1708         BUG_ON(ret);
1709         return 0;
1710 }
1711
1712 /*
1713  * helper function to allocate a block for a given tree
1714  * returns the tree buffer or NULL.
1715  */
1716 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1717                                              struct btrfs_root *root,
1718                                              u32 blocksize,
1719                                              u64 root_objectid, u64 hint,
1720                                              u64 empty_size)
1721 {
1722         u64 ref_generation;
1723
1724         if (root->ref_cows)
1725                 ref_generation = trans->transid;
1726         else
1727                 ref_generation = 0;
1728
1729
1730         return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1731                                         ref_generation, 0, 0, hint, empty_size);
1732 }
1733
1734 /*
1735  * helper function to allocate a block for a given tree
1736  * returns the tree buffer or NULL.
1737  */
1738 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1739                                              struct btrfs_root *root,
1740                                              u32 blocksize,
1741                                              u64 root_objectid,
1742                                              u64 ref_generation,
1743                                              u64 first_objectid,
1744                                              int level,
1745                                              u64 hint,
1746                                              u64 empty_size)
1747 {
1748         struct btrfs_key ins;
1749         int ret;
1750         struct extent_buffer *buf;
1751
1752         ret = btrfs_alloc_extent(trans, root, blocksize,
1753                                  root_objectid, ref_generation,
1754                                  level, first_objectid, empty_size, hint,
1755                                  (u64)-1, &ins, 0);
1756         if (ret) {
1757                 BUG_ON(ret > 0);
1758                 return ERR_PTR(ret);
1759         }
1760         buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1761         if (!buf) {
1762                 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1763                                   root->root_key.objectid, ref_generation,
1764                                   0, 0, 0);
1765                 return ERR_PTR(-ENOMEM);
1766         }
1767         btrfs_set_buffer_uptodate(buf);
1768         /*
1769         set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1770                          buf->start + buf->len - 1, GFP_NOFS);
1771         set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
1772                         buf->start, buf->start + buf->len - 1,
1773                         EXTENT_CSUM, GFP_NOFS);
1774         buf->flags |= EXTENT_CSUM;
1775         btrfs_set_buffer_defrag(buf);
1776         */
1777         trans->blocks_used++;
1778         return buf;
1779 }
1780
1781 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1782                                   struct btrfs_root *root,
1783                                   struct extent_buffer *leaf)
1784 {
1785         u64 leaf_owner;
1786         u64 leaf_generation;
1787         struct btrfs_key key;
1788         struct btrfs_file_extent_item *fi;
1789         int i;
1790         int nritems;
1791         int ret;
1792
1793         BUG_ON(!btrfs_is_leaf(leaf));
1794         nritems = btrfs_header_nritems(leaf);
1795         leaf_owner = btrfs_header_owner(leaf);
1796         leaf_generation = btrfs_header_generation(leaf);
1797
1798         for (i = 0; i < nritems; i++) {
1799                 u64 disk_bytenr;
1800
1801                 btrfs_item_key_to_cpu(leaf, &key, i);
1802                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1803                         continue;
1804                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1805                 if (btrfs_file_extent_type(leaf, fi) ==
1806                     BTRFS_FILE_EXTENT_INLINE)
1807                         continue;
1808                 /*
1809                  * FIXME make sure to insert a trans record that
1810                  * repeats the snapshot del on crash
1811                  */
1812                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1813                 if (disk_bytenr == 0)
1814                         continue;
1815                 ret = btrfs_free_extent(trans, root, disk_bytenr,
1816                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
1817                                 leaf_owner, leaf_generation,
1818                                 key.objectid, key.offset, 0);
1819                 BUG_ON(ret);
1820         }
1821         return 0;
1822 }
1823
1824 static void noinline reada_walk_down(struct btrfs_root *root,
1825                                      struct extent_buffer *node)
1826 {
1827         int i;
1828         u32 nritems;
1829         u64 bytenr;
1830         int ret;
1831         u32 refs;
1832         int level;
1833         u32 blocksize;
1834
1835         nritems = btrfs_header_nritems(node);
1836         level = btrfs_header_level(node);
1837         for (i = 0; i < nritems; i++) {
1838                 bytenr = btrfs_node_blockptr(node, i);
1839                 blocksize = btrfs_level_size(root, level - 1);
1840                 ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
1841                 BUG_ON(ret);
1842                 if (refs != 1)
1843                         continue;
1844                 mutex_unlock(&root->fs_info->fs_mutex);
1845                 ret = readahead_tree_block(root, bytenr, blocksize);
1846                 cond_resched();
1847                 mutex_lock(&root->fs_info->fs_mutex);
1848                 if (ret)
1849                         break;
1850         }
1851 }
1852
1853 /*
1854  * helper function for drop_snapshot, this walks down the tree dropping ref
1855  * counts as it goes.
1856  */
1857 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1858                                    struct btrfs_root *root,
1859                                    struct btrfs_path *path, int *level)
1860 {
1861         u64 root_owner;
1862         u64 root_gen;
1863         u64 bytenr;
1864         struct extent_buffer *next;
1865         struct extent_buffer *cur;
1866         struct extent_buffer *parent;
1867         u32 blocksize;
1868         int ret;
1869         u32 refs;
1870
1871         WARN_ON(*level < 0);
1872         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1873         ret = lookup_extent_ref(trans, root,
1874                                 path->nodes[*level]->start,
1875                                 path->nodes[*level]->len, &refs);
1876         BUG_ON(ret);
1877         if (refs > 1)
1878                 goto out;
1879
1880         /*
1881          * walk down to the last node level and free all the leaves
1882          */
1883         while(*level >= 0) {
1884                 WARN_ON(*level < 0);
1885                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1886                 cur = path->nodes[*level];
1887
1888                 if (*level > 0 && path->slots[*level] == 0)
1889                         reada_walk_down(root, cur);
1890
1891                 if (btrfs_header_level(cur) != *level)
1892                         WARN_ON(1);
1893
1894                 if (path->slots[*level] >=
1895                     btrfs_header_nritems(cur))
1896                         break;
1897                 if (*level == 0) {
1898                         ret = drop_leaf_ref(trans, root, cur);
1899                         BUG_ON(ret);
1900                         break;
1901                 }
1902                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1903                 blocksize = btrfs_level_size(root, *level - 1);
1904                 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1905                 BUG_ON(ret);
1906                 if (refs != 1) {
1907                         parent = path->nodes[*level];
1908                         root_owner = btrfs_header_owner(parent);
1909                         root_gen = btrfs_header_generation(parent);
1910                         path->slots[*level]++;
1911                         ret = btrfs_free_extent(trans, root, bytenr,
1912                                                 blocksize, root_owner,
1913                                                 root_gen, 0, 0, 1);
1914                         BUG_ON(ret);
1915                         continue;
1916                 }
1917                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1918                 if (!next || !btrfs_buffer_uptodate(next)) {
1919                         free_extent_buffer(next);
1920                         mutex_unlock(&root->fs_info->fs_mutex);
1921                         next = read_tree_block(root, bytenr, blocksize);
1922                         mutex_lock(&root->fs_info->fs_mutex);
1923
1924                         /* we dropped the lock, check one more time */
1925                         ret = lookup_extent_ref(trans, root, bytenr,
1926                                                 blocksize, &refs);
1927                         BUG_ON(ret);
1928                         if (refs != 1) {
1929                                 parent = path->nodes[*level];
1930                                 root_owner = btrfs_header_owner(parent);
1931                                 root_gen = btrfs_header_generation(parent);
1932
1933                                 path->slots[*level]++;
1934                                 free_extent_buffer(next);
1935                                 ret = btrfs_free_extent(trans, root, bytenr,
1936                                                         blocksize,
1937                                                         root_owner,
1938                                                         root_gen, 0, 0, 1);
1939                                 BUG_ON(ret);
1940                                 continue;
1941                         }
1942                 }
1943                 WARN_ON(*level <= 0);
1944                 if (path->nodes[*level-1])
1945                         free_extent_buffer(path->nodes[*level-1]);
1946                 path->nodes[*level-1] = next;
1947                 *level = btrfs_header_level(next);
1948                 path->slots[*level] = 0;
1949         }
1950 out:
1951         WARN_ON(*level < 0);
1952         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1953
1954         if (path->nodes[*level] == root->node) {
1955                 root_owner = root->root_key.objectid;
1956                 parent = path->nodes[*level];
1957         } else {
1958                 parent = path->nodes[*level + 1];
1959                 root_owner = btrfs_header_owner(parent);
1960         }
1961
1962         root_gen = btrfs_header_generation(parent);
1963         ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
1964                                 path->nodes[*level]->len,
1965                                 root_owner, root_gen, 0, 0, 1);
1966         free_extent_buffer(path->nodes[*level]);
1967         path->nodes[*level] = NULL;
1968         *level += 1;
1969         BUG_ON(ret);
1970         return 0;
1971 }
1972
1973 /*
1974  * helper for dropping snapshots.  This walks back up the tree in the path
1975  * to find the first node higher up where we haven't yet gone through
1976  * all the slots
1977  */
1978 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
1979                                  struct btrfs_root *root,
1980                                  struct btrfs_path *path, int *level)
1981 {
1982         u64 root_owner;
1983         u64 root_gen;
1984         struct btrfs_root_item *root_item = &root->root_item;
1985         int i;
1986         int slot;
1987         int ret;
1988
1989         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1990                 slot = path->slots[i];
1991                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1992                         struct extent_buffer *node;
1993                         struct btrfs_disk_key disk_key;
1994                         node = path->nodes[i];
1995                         path->slots[i]++;
1996                         *level = i;
1997                         WARN_ON(*level == 0);
1998                         btrfs_node_key(node, &disk_key, path->slots[i]);
1999                         memcpy(&root_item->drop_progress,
2000                                &disk_key, sizeof(disk_key));
2001                         root_item->drop_level = i;
2002                         return 0;
2003                 } else {
2004                         if (path->nodes[*level] == root->node) {
2005                                 root_owner = root->root_key.objectid;
2006                                 root_gen =
2007                                    btrfs_header_generation(path->nodes[*level]);
2008                         } else {
2009                                 struct extent_buffer *node;
2010                                 node = path->nodes[*level + 1];
2011                                 root_owner = btrfs_header_owner(node);
2012                                 root_gen = btrfs_header_generation(node);
2013                         }
2014                         ret = btrfs_free_extent(trans, root,
2015                                                 path->nodes[*level]->start,
2016                                                 path->nodes[*level]->len,
2017                                                 root_owner, root_gen, 0, 0, 1);
2018                         BUG_ON(ret);
2019                         free_extent_buffer(path->nodes[*level]);
2020                         path->nodes[*level] = NULL;
2021                         *level = i + 1;
2022                 }
2023         }
2024         return 1;
2025 }
2026
2027 /*
2028  * drop the reference count on the tree rooted at 'snap'.  This traverses
2029  * the tree freeing any blocks that have a ref count of zero after being
2030  * decremented.
2031  */
2032 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2033                         *root)
2034 {
2035         int ret = 0;
2036         int wret;
2037         int level;
2038         struct btrfs_path *path;
2039         int i;
2040         int orig_level;
2041         struct btrfs_root_item *root_item = &root->root_item;
2042
2043         path = btrfs_alloc_path();
2044         BUG_ON(!path);
2045
2046         level = btrfs_header_level(root->node);
2047         orig_level = level;
2048         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2049                 path->nodes[level] = root->node;
2050                 extent_buffer_get(root->node);
2051                 path->slots[level] = 0;
2052         } else {
2053                 struct btrfs_key key;
2054                 struct btrfs_disk_key found_key;
2055                 struct extent_buffer *node;
2056
2057                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2058                 level = root_item->drop_level;
2059                 path->lowest_level = level;
2060                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2061                 if (wret < 0) {
2062                         ret = wret;
2063                         goto out;
2064                 }
2065                 node = path->nodes[level];
2066                 btrfs_node_key(node, &found_key, path->slots[level]);
2067                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2068                                sizeof(found_key)));
2069         }
2070         while(1) {
2071                 wret = walk_down_tree(trans, root, path, &level);
2072                 if (wret < 0)
2073                         ret = wret;
2074                 if (wret != 0)
2075                         break;
2076
2077                 wret = walk_up_tree(trans, root, path, &level);
2078                 if (wret < 0)
2079                         ret = wret;
2080                 if (wret != 0)
2081                         break;
2082                 /*
2083                 ret = -EAGAIN;
2084                 break;
2085                 */
2086         }
2087         for (i = 0; i <= orig_level; i++) {
2088                 if (path->nodes[i]) {
2089                         free_extent_buffer(path->nodes[i]);
2090                         path->nodes[i] = NULL;
2091                 }
2092         }
2093 out:
2094         btrfs_free_path(path);
2095         return ret;
2096 }
2097
2098 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2099 {
2100         u64 start;
2101         u64 end;
2102         u64 ptr;
2103         int ret;
2104         while(1) {
2105                 ret = find_first_extent_bit(&info->block_group_cache, 0,
2106                                             &start, &end, (unsigned int)-1);
2107                 if (ret)
2108                         break;
2109                 ret = get_state_private(&info->block_group_cache, start, &ptr);
2110                 if (!ret)
2111                         kfree((void *)(unsigned long)ptr);
2112                 clear_extent_bits(&info->block_group_cache, start,
2113                                   end, (unsigned int)-1, GFP_NOFS);
2114         }
2115         while(1) {
2116                 ret = find_first_extent_bit(&info->free_space_cache, 0,
2117                                             &start, &end, EXTENT_DIRTY);
2118                 if (ret)
2119                         break;
2120                 clear_extent_dirty(&info->free_space_cache, start,
2121                                    end, GFP_NOFS);
2122         }
2123         return 0;
2124 }
2125
2126 int btrfs_read_block_groups(struct btrfs_root *root)
2127 {
2128         struct btrfs_path *path;
2129         int ret;
2130         int err = 0;
2131         int bit;
2132         struct btrfs_block_group_cache *cache;
2133         struct btrfs_fs_info *info = root->fs_info;
2134         struct extent_map_tree *block_group_cache;
2135         struct btrfs_key key;
2136         struct btrfs_key found_key;
2137         struct extent_buffer *leaf;
2138
2139         block_group_cache = &info->block_group_cache;
2140
2141         root = info->extent_root;
2142         key.objectid = 0;
2143         key.offset = BTRFS_BLOCK_GROUP_SIZE;
2144         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2145
2146         path = btrfs_alloc_path();
2147         if (!path)
2148                 return -ENOMEM;
2149
2150         while(1) {
2151                 ret = btrfs_search_slot(NULL, info->extent_root,
2152                                         &key, path, 0, 0);
2153                 if (ret != 0) {
2154                         err = ret;
2155                         break;
2156                 }
2157                 leaf = path->nodes[0];
2158                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2159                 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2160                 if (!cache) {
2161                         err = -1;
2162                         break;
2163                 }
2164
2165                 read_extent_buffer(leaf, &cache->item,
2166                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
2167                                    sizeof(cache->item));
2168                 memcpy(&cache->key, &found_key, sizeof(found_key));
2169                 cache->cached = 0;
2170                 cache->pinned = 0;
2171                 key.objectid = found_key.objectid + found_key.offset;
2172                 btrfs_release_path(root, path);
2173
2174                 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
2175                         bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
2176                         cache->data = BTRFS_BLOCK_GROUP_MIXED;
2177                 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2178                         bit = BLOCK_GROUP_DATA;
2179                         cache->data = BTRFS_BLOCK_GROUP_DATA;
2180                 } else {
2181                         bit = BLOCK_GROUP_METADATA;
2182                         cache->data = 0;
2183                 }
2184
2185                 /* use EXTENT_LOCKED to prevent merging */
2186                 set_extent_bits(block_group_cache, found_key.objectid,
2187                                 found_key.objectid + found_key.offset - 1,
2188                                 bit | EXTENT_LOCKED, GFP_NOFS);
2189                 set_state_private(block_group_cache, found_key.objectid,
2190                                   (unsigned long)cache);
2191
2192                 if (key.objectid >=
2193                     btrfs_super_total_bytes(&info->super_copy))
2194                         break;
2195         }
2196
2197         btrfs_free_path(path);
2198         return 0;
2199 }
2200
2201 static int btrfs_insert_block_group(struct btrfs_trans_handle *trans,
2202                                     struct btrfs_root *root,
2203                                     struct btrfs_key *key,
2204                                     struct btrfs_block_group_item *bi)
2205 {
2206         int ret;
2207         int pending_ret;
2208         struct btrfs_root *extent_root;
2209
2210         extent_root = root->fs_info->extent_root;
2211         ret = btrfs_insert_item(trans, extent_root, key, bi, sizeof(*bi));
2212         finish_current_insert(trans, extent_root);
2213         pending_ret = del_pending_extents(trans, extent_root);
2214         if (ret)
2215                 return ret;
2216         if (pending_ret)
2217                 return pending_ret;
2218         return 0;
2219 }
2220
2221 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
2222                             struct btrfs_root *root)
2223 {
2224         u64 group_size;
2225         u64 bytes_used;
2226         u64 total_bytes;
2227         u64 cur_start;
2228         u64 nr = 0;
2229         int ret;
2230         int bit;
2231         struct btrfs_root *extent_root;
2232         struct btrfs_block_group_cache *cache;
2233         struct extent_map_tree *block_group_cache;
2234
2235         extent_root = root->fs_info->extent_root;
2236         block_group_cache = &root->fs_info->block_group_cache;
2237         group_size = BTRFS_BLOCK_GROUP_SIZE;
2238         bytes_used = btrfs_super_bytes_used(&root->fs_info->super_copy);
2239         total_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
2240
2241         cur_start = 0;
2242         while (cur_start < total_bytes) {
2243                 cache = malloc(sizeof(*cache));
2244                 BUG_ON(!cache);
2245                 cache->key.objectid = cur_start;
2246                 cache->key.offset = group_size;
2247                 btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2248                 memset(&cache->item, 0, sizeof(cache->item));
2249                 if (nr == 0)
2250                         btrfs_set_block_group_used(&cache->item, bytes_used);
2251                 if (nr++ % 3) {
2252                         bit = BLOCK_GROUP_DATA;
2253                         cache->data = 1;
2254                         cache->item.flags |= BTRFS_BLOCK_GROUP_DATA;
2255                 } else {
2256                         bit = BLOCK_GROUP_METADATA;
2257                         cache->data = 0;
2258                 }
2259
2260                 set_extent_bits(block_group_cache, cur_start,
2261                                 cur_start + group_size - 1,
2262                                 bit | EXTENT_LOCKED, GFP_NOFS);
2263                 set_state_private(block_group_cache, cur_start,
2264                                   (unsigned long)cache);
2265                 cur_start += group_size;
2266         }
2267         /* then insert all the items */
2268         cur_start = 0;
2269         while(cur_start < total_bytes) {
2270                 cache = btrfs_lookup_block_group(root->fs_info, cur_start);
2271                 BUG_ON(!cache);
2272                 ret = btrfs_insert_block_group(trans, root, &cache->key,
2273                                                &cache->item);
2274                 BUG_ON(ret);
2275                 cur_start += group_size;
2276         }
2277         return 0;
2278 }
2279
2280 u64 btrfs_hash_extent_ref(u64 root_objectid, u64 ref_generation,
2281                           u64 owner, u64 owner_offset)
2282 {
2283         return hash_extent_ref(root_objectid, ref_generation,
2284                                owner, owner_offset);
2285 }
2286
2287 int btrfs_update_block_group(struct btrfs_trans_handle *trans,
2288                              struct btrfs_root *root,
2289                              u64 bytenr, u64 num_bytes, int alloc,
2290                              int mark_free, int data)
2291 {
2292         return update_block_group(trans, root, bytenr, num_bytes,
2293                                   alloc, mark_free, data);
2294 }