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 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  30                                  btrfs_root *extent_root);
  31 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
  32                        *extent_root);
  33
  34 static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
  35                            u64 owner, u64 owner_offset)
  36 {
  37         u32 high_crc = ~(u32)0;
  38         u32 low_crc = ~(u32)0;
  39         __le64 lenum;
  40
  41         lenum = cpu_to_le64(root_objectid);
  42         high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
  43         lenum = cpu_to_le64(ref_generation);
  44         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
  45
  46 #if 0
  47         lenum = cpu_to_le64(owner);
  48         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
  49         lenum = cpu_to_le64(owner_offset);
  50         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
  51 #endif
  52         return ((u64)high_crc << 32) | (u64)low_crc;
  53 }
  54
  55 static int match_extent_ref(struct btrfs_extent_ref *disk_ref,
  56                             struct btrfs_extent_ref *cpu_ref)
  57 {
  58         int ret = memcmp(cpu_ref, disk_ref, sizeof(*cpu_ref));
  59         return ret == 0;
  60 }
  61
  62 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
  63                                  struct btrfs_root *root,
  64                                  struct btrfs_path *path, u64 bytenr,
  65                                  u64 root_objectid, u64 ref_generation,
  66                                  u64 owner, u64 owner_offset, int del)
  67 {
  68         u64 hash;
  69         struct btrfs_key key;
  70         struct btrfs_key found_key;
  71         struct btrfs_extent_ref ref;
  72         struct btrfs_buffer *leaf;
  73         struct btrfs_extent_ref *disk_ref;
  74         int ret;
  75         int ret2;
  76
  77         btrfs_set_ref_root(&ref, root_objectid);
  78         btrfs_set_ref_generation(&ref, ref_generation);
  79         btrfs_set_ref_objectid(&ref, owner);
  80         btrfs_set_ref_offset(&ref, owner_offset);
  81
  82         hash = hash_extent_ref(root_objectid, ref_generation, owner,
  83                                owner_offset);
  84         key.offset = hash;
  85         key.objectid = bytenr;
  86         key.type = BTRFS_EXTENT_REF_KEY;
  87
  88         while (1) {
  89                 ret = btrfs_search_slot(trans, root, &key, path,
  90                                         del ? -1 : 0, del);
  91                 if (ret < 0)
  92                         goto out;
  93                 leaf = path->nodes[0];
  94                 if (ret != 0) {
  95                         u32 nritems = btrfs_header_nritems(&leaf->node.header);
  96                         if (path->slots[0] >= nritems) {
  97                                 ret2 = btrfs_next_leaf(root, path);
  98                                 if (ret2)
  99                                         goto out;
 100                                 leaf = path->nodes[0];
 101                         }
 102                         btrfs_disk_key_to_cpu(&found_key,
 103                                          &leaf->leaf.items[path->slots[0]].key);
 104                         if (found_key.objectid != bytenr ||
 105                             found_key.type != BTRFS_EXTENT_REF_KEY)
 106                                 goto out;
 107                         key.offset = found_key.offset;
 108                         if (del) {
 109                                 btrfs_release_path(root, path);
 110                                 continue;
 111                         }
 112                 }
 113                 disk_ref = btrfs_item_ptr(&path->nodes[0]->leaf,
 114                                           path->slots[0],
 115                                           struct btrfs_extent_ref);
 116                 if (match_extent_ref(disk_ref, &ref)) {
 117                         ret = 0;
 118                         goto out;
 119                 }
 120                 btrfs_disk_key_to_cpu(&found_key,
 121                                       &leaf->leaf.items[path->slots[0]].key);
 122                 key.offset = found_key.offset + 1;
 123                 btrfs_release_path(root, path);
 124         }
 125 out:
 126         return ret;
 127 }
 128
 129 static int insert_extent_backref(struct btrfs_trans_handle *trans,
 130                                  struct btrfs_root *root,
 131                                  struct btrfs_path *path, u64 bytenr,
 132                                  u64 root_objectid, u64 ref_generation,
 133                                  u64 owner, u64 owner_offset)
 134 {
 135         u64 hash;
 136         struct btrfs_key key;
 137         struct btrfs_extent_ref ref;
 138         struct btrfs_extent_ref *disk_ref;
 139         int ret;
 140
 141         btrfs_set_ref_root(&ref, root_objectid);
 142         btrfs_set_ref_generation(&ref, ref_generation);
 143         btrfs_set_ref_objectid(&ref, owner);
 144         btrfs_set_ref_offset(&ref, owner_offset);
 145
 146         hash = hash_extent_ref(root_objectid, ref_generation, owner,
 147                                owner_offset);
 148         key.offset = hash;
 149         key.objectid = bytenr;
 150         key.type = BTRFS_EXTENT_REF_KEY;
 151
 152         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
 153         while (ret == -EEXIST) {
 154                 disk_ref = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
 155                                           struct btrfs_extent_ref);
 156                 if (match_extent_ref(disk_ref, &ref))
 157                         goto out;
 158                 key.offset++;
 159                 ret = btrfs_insert_empty_item(trans, root, path, &key,
 160                                               sizeof(ref));
 161         }
 162         if (ret)
 163                 goto out;
 164         disk_ref = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
 165                                   struct btrfs_extent_ref);
 166         memcpy(disk_ref, &ref, sizeof(ref));
 167         dirty_tree_block(trans, root, path->nodes[0]);
 168 out:
 169         btrfs_release_path(root, path);
 170         return ret;
 171 }
 172
 173 static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
 174                          *root, u64 bytenr, u32 blocksize,
 175                          u64 root_objectid, u64 ref_generation,
 176                          u64 owner, u64 owner_offset)
 177 {
 178         struct btrfs_path path;
 179         int ret;
 180         struct btrfs_key key;
 181         struct btrfs_leaf *l;
 182         struct btrfs_extent_item *item;
 183         u32 refs;
 184
 185         btrfs_init_path(&path);
 186         key.objectid = bytenr;
 187         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 188         key.offset = blocksize;
 189         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
 190                                 0, 1);
 191         if (ret != 0)
 192                 BUG();
 193         BUG_ON(ret != 0);
 194         l = &path.nodes[0]->leaf;
 195         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
 196         refs = btrfs_extent_refs(item);
 197         btrfs_set_extent_refs(item, refs + 1);
 198
 199         BUG_ON(list_empty(&path.nodes[0]->dirty));
 200         btrfs_release_path(root->fs_info->extent_root, &path);
 201
 202         ret = insert_extent_backref(trans, root->fs_info->extent_root, &path,
 203                                     bytenr, root_objectid, ref_generation,
 204                                     owner, owner_offset);
 205         BUG_ON(ret);
 206
 207         finish_current_insert(trans, root->fs_info->extent_root);
 208         run_pending(trans, root->fs_info->extent_root);
 209         return 0;
 210 }
 211
 212 static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
 213                             *root, u64 bytenr, u32 blocksize, u32 *refs)
 214 {
 215         struct btrfs_path path;
 216         int ret;
 217         struct btrfs_key key;
 218         struct btrfs_leaf *l;
 219         struct btrfs_extent_item *item;
 220
 221         btrfs_init_path(&path);
 222
 223         key.objectid = bytenr;
 224         key.offset = blocksize;
 225         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 226         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
 227                                 0, 0);
 228         if (ret != 0)
 229                 BUG();
 230         l = &path.nodes[0]->leaf;
 231         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
 232         *refs = btrfs_extent_refs(item);
 233         btrfs_release_path(root->fs_info->extent_root, &path);
 234         return 0;
 235 }
 236
 237 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 238                   struct btrfs_buffer *buf)
 239 {
 240         u64 bytenr;
 241         u32 blocksize;
 242         int i;
 243         int level;
 244
 245         if (!root->ref_cows)
 246                 return 0;
 247
 248         level = btrfs_header_level(&buf->node.header) - 1;
 249         blocksize = btrfs_level_size(root, level);
 250
 251         if (btrfs_is_leaf(&buf->node))
 252                 return 0;
 253
 254         for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
 255                 bytenr = btrfs_node_blockptr(&buf->node, i);
 256                 inc_block_ref(trans, root, bytenr, blocksize,
 257                               root->root_key.objectid, trans->transid, 0, 0);
 258         }
 259
 260         return 0;
 261 }
 262
 263 int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
 264                        struct btrfs_root *root, u64 owner_objectid)
 265 {
 266         return inc_block_ref(trans, root, root->node->bytenr,
 267                              root->node->size, owner_objectid,
 268                              trans->transid, 0, 0);
 269 }
 270
 271 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 272                                  struct btrfs_root *root,
 273                                  struct btrfs_path *path,
 274                                  struct btrfs_block_group_cache *cache)
 275 {
 276         int ret;
 277         int pending_ret;
 278         struct btrfs_root *extent_root = root->fs_info->extent_root;
 279         struct btrfs_block_group_item *bi;
 280
 281         ret = btrfs_search_slot(trans, root->fs_info->extent_root,
 282                                 &cache->key, path, 0, 1);
 283         BUG_ON(ret);
 284         bi = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
 285                             struct btrfs_block_group_item);
 286         memcpy(bi, &cache->item, sizeof(*bi));
 287         dirty_tree_block(trans, extent_root, path->nodes[0]);
 288         btrfs_release_path(extent_root, path);
 289         finish_current_insert(trans, root);
 290         pending_ret = run_pending(trans, root);
 291         if (ret)
 292                 return ret;
 293         if (pending_ret)
 294                 return pending_ret;
 295         return 0;
 296
 297 }
 298
 299 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
 300                                     struct btrfs_root *root)
 301 {
 302         struct btrfs_block_group_cache *bg;
 303         struct cache_extent *cache;
 304         int err = 0;
 305         int werr = 0;
 306         struct cache_tree *bg_cache = &root->fs_info->block_group_cache;
 307         struct btrfs_path path;
 308         btrfs_init_path(&path);
 309         u64 start = 0;
 310
 311         while(1) {
 312                 cache = find_first_cache_extent(bg_cache, start);
 313                 if (!cache)
 314                         break;
 315                 bg = container_of(cache, struct btrfs_block_group_cache,
 316                                         cache);
 317                 start = cache->start + cache->size;
 318                 if (bg->dirty) {
 319                         err = write_one_cache_group(trans, root,
 320                                                     &path, bg);
 321                         if (err)
 322                                 werr = err;
 323                 }
 324                 bg->dirty = 0;
 325         }
 326         return werr;
 327 }
 328
 329 static int update_block_group(struct btrfs_trans_handle *trans,
 330                               struct btrfs_root *root,
 331                               u64 bytenr, u64 num, int alloc)
 332 {
 333         struct btrfs_block_group_cache *bg;
 334         struct cache_extent *cache;
 335         struct btrfs_fs_info *info = root->fs_info;
 336         u64 total = num;
 337         u64 old_val;
 338         u64 byte_in_group;
 339
 340         while(total) {
 341                 cache = find_first_cache_extent(&info->block_group_cache,
 342                                                 bytenr);
 343                 if (!cache)
 344                         return -1;
 345                 bg = container_of(cache, struct btrfs_block_group_cache,
 346                                         cache);
 347                 bg->dirty = 1;
 348                 byte_in_group = bytenr - bg->key.objectid;
 349                 old_val = btrfs_block_group_used(&bg->item);
 350                 if (total > bg->key.offset - byte_in_group)
 351                         num = bg->key.offset - byte_in_group;
 352                 else
 353                         num = total;
 354                 total -= num;
 355                 bytenr += num;
 356                 if (alloc)
 357                         old_val += num;
 358                 else
 359                         old_val -= num;
 360                 btrfs_set_block_group_used(&bg->item, old_val);
 361         }
 362         return 0;
 363 }
 364
 365 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
 366                                btrfs_root *root)
 367 {
 368         u64 first = 0;
 369         struct cache_extent *pe;
 370         struct cache_extent *next;
 371
 372         pe = find_first_cache_extent(&root->fs_info->pinned_tree, 0);
 373         if (pe)
 374                 first = pe->start;
 375         while(pe) {
 376                 next = next_cache_extent(pe);
 377                 remove_cache_extent(&root->fs_info->pinned_tree, pe);
 378                 free_cache_extent(pe);
 379                 pe = next;
 380         }
 381         root->fs_info->last_insert.objectid = first;
 382         root->fs_info->last_insert.offset = 0;
 383         return 0;
 384 }
 385
 386 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
 387                                  btrfs_root *extent_root)
 388 {
 389         struct btrfs_key ins;
 390         struct btrfs_extent_item extent_item;
 391         int ret;
 392         struct btrfs_fs_info *info = extent_root->fs_info;
 393         struct cache_extent *pe;
 394         struct cache_extent *next;
 395         struct cache_tree *pending_tree = &info->pending_tree;
 396         struct btrfs_path path;
 397
 398         btrfs_init_path(&path);
 399         btrfs_set_extent_refs(&extent_item, 1);
 400         ins.offset = 1;
 401         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
 402         pe = find_first_cache_extent(pending_tree, 0);
 403         while(pe) {
 404                 ins.offset = pe->size;
 405                 ins.objectid = pe->start;
 406
 407                 remove_cache_extent(pending_tree, pe);
 408                 next = next_cache_extent(pe);
 409                 if (!next)
 410                         next = find_first_cache_extent(pending_tree, 0);
 411
 412                 free_cache_extent(pe);
 413                 pe = next;
 414
 415                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
 416                                         sizeof(extent_item));
 417                 if (ret) {
 418                         btrfs_print_tree(extent_root, extent_root->node);
 419                 }
 420                 BUG_ON(ret);
 421
 422                 ret = insert_extent_backref(trans, extent_root, &path,
 423                                             ins.objectid,
 424                                             extent_root->root_key.objectid,
 425                                             0, 0, 0);
 426                 BUG_ON(ret);
 427         }
 428         return 0;
 429 }
 430
 431 /*
 432  * remove an extent from the root, returns 0 on success
 433  */
 434 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 435                          *root, u64 bytenr, u64 num_bytes,
 436                          u64 root_objectid, u64 ref_generation,
 437                          u64 owner_objectid, u64 owner_offset, int pin)
 438 {
 439         struct btrfs_path path;
 440         struct btrfs_key key;
 441         struct btrfs_fs_info *info = root->fs_info;
 442         struct btrfs_root *extent_root = info->extent_root;
 443         int ret;
 444         struct btrfs_extent_item *ei;
 445         u32 refs;
 446
 447         key.objectid = bytenr;
 448         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 449         key.offset = num_bytes;
 450
 451         btrfs_init_path(&path);
 452
 453         ret = lookup_extent_backref(trans, extent_root, &path,
 454                                     bytenr, root_objectid,
 455                                     ref_generation,
 456                                     owner_objectid, owner_offset, 1);
 457         if (ret == 0) {
 458                 ret = btrfs_del_item(trans, extent_root, &path);
 459         } else {
 460                 // FIXME deal with missing references here
 461         }
 462
 463         btrfs_release_path(extent_root, &path);
 464
 465         ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
 466         if (ret) {
 467                 btrfs_print_tree(extent_root, extent_root->node);
 468                 printf("failed to find %llu\n",
 469                        (unsigned long long)key.objectid);
 470                 BUG();
 471         }
 472         ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 473                             struct btrfs_extent_item);
 474         BUG_ON(ei->refs == 0);
 475         refs = btrfs_extent_refs(ei) - 1;
 476         btrfs_set_extent_refs(ei, refs);
 477         if (refs == 0) {
 478                 u64 super_bytes_used, root_bytes_used;
 479                 if (pin) {
 480                         int err;
 481                         err = insert_cache_extent(&info->pinned_tree,
 482                                                     bytenr, num_bytes);
 483                         BUG_ON(err);
 484                 }
 485                 super_bytes_used = btrfs_super_bytes_used(info->disk_super);
 486                 btrfs_set_super_bytes_used(info->disk_super,
 487                                             super_bytes_used - num_bytes);
 488                 root_bytes_used = btrfs_root_bytes_used(&root->root_item);
 489                 btrfs_set_root_bytes_used(&root->root_item,
 490                                           root_bytes_used - num_bytes);
 491
 492                 ret = btrfs_del_item(trans, extent_root, &path);
 493                 if (!pin && extent_root->fs_info->last_insert.objectid >
 494                     bytenr)
 495                         extent_root->fs_info->last_insert.objectid = bytenr;
 496                 if (ret)
 497                         BUG();
 498                 ret = update_block_group(trans, root, bytenr, num_bytes, 0);
 499                 BUG_ON(ret);
 500         }
 501         btrfs_release_path(extent_root, &path);
 502         finish_current_insert(trans, extent_root);
 503         return ret;
 504 }
 505
 506 /*
 507  * find all the blocks marked as pending in the radix tree and remove
 508  * them from the extent map
 509  */
 510 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
 511                                btrfs_root *extent_root)
 512 {
 513         int ret;
 514         struct cache_extent *pe;
 515         struct cache_extent *next;
 516         struct cache_tree *del_pending = &extent_root->fs_info->del_pending;
 517
 518         pe = find_first_cache_extent(del_pending, 0);
 519         while(pe) {
 520                 remove_cache_extent(del_pending, pe);
 521                 ret = __free_extent(trans, extent_root,
 522                                     pe->start, pe->size,
 523                                     extent_root->root_key.objectid,
 524                                     0, 0, 0, 1);
 525                 BUG_ON(ret);
 526                 next = next_cache_extent(pe);
 527                 if (!next)
 528                         next = find_first_cache_extent(del_pending, 0);
 529                 free_cache_extent(pe);
 530                 pe = next;
 531         }
 532         return 0;
 533 }
 534
 535 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
 536                        *extent_root)
 537 {
 538         del_pending_extents(trans, extent_root);
 539         return 0;
 540 }
 541
 542
 543 /*
 544  * remove an extent from the root, returns 0 on success
 545  */
 546 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 547                       *root, u64 bytenr, u64 num_bytes,
 548                       u64 root_objectid, u64 root_generation,
 549                       u64 owner_objectid, u64 owner_offset, int pin)
 550 {
 551         struct btrfs_root *extent_root = root->fs_info->extent_root;
 552         int pending_ret;
 553         int ret;
 554
 555         if (!root->ref_cows)
 556                 root_generation = 0;
 557
 558         if (root == extent_root) {
 559                 ret = insert_cache_extent(&root->fs_info->del_pending,
 560                                             bytenr, num_bytes);
 561                 BUG_ON(ret);
 562                 return 0;
 563         }
 564         ret = __free_extent(trans, root, bytenr, num_bytes,
 565                             root_objectid, root_generation, owner_objectid,
 566                             owner_offset, pin);
 567         pending_ret = run_pending(trans, root->fs_info->extent_root);
 568         return ret ? ret : pending_ret;
 569 }
 570
 571 static u64 stripe_align(struct btrfs_root *root, u64 val)
 572 {
 573         u64 mask = ((u64)root->stripesize - 1);
 574         u64 ret = (val + mask) & ~mask;
 575         return ret;
 576 }
 577
 578 /*
 579  * walks the btree of allocated extents and find a hole of a given size.
 580  * The key ins is changed to record the hole:
 581  * ins->objectid == block start
 582  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 583  * ins->offset == number of blocks
 584  * Any available blocks before search_start are skipped.
 585  */
 586 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
 587                             *orig_root, u64 total_needed, u64 search_start,
 588                             u64 search_end, struct btrfs_key *ins)
 589 {
 590         struct btrfs_path path;
 591         struct btrfs_key key;
 592         int ret;
 593         u64 hole_size = 0;
 594         int slot = 0;
 595         u64 last_byte = 0;
 596         u64 aligned;
 597         int start_found;
 598         struct btrfs_leaf *l;
 599         struct btrfs_root * root = orig_root->fs_info->extent_root;
 600
 601         if (root->fs_info->last_insert.objectid > search_start)
 602                 search_start = root->fs_info->last_insert.objectid;
 603
 604         search_start = stripe_align(root, search_start);
 605         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
 606
 607 check_failed:
 608         btrfs_init_path(&path);
 609         ins->objectid = search_start;
 610         ins->offset = 0;
 611         start_found = 0;
 612         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
 613         if (ret < 0)
 614                 goto error;
 615
 616         if (path.slots[0] > 0)
 617                 path.slots[0]--;
 618
 619         while (1) {
 620                 l = &path.nodes[0]->leaf;
 621                 slot = path.slots[0];
 622                 if (slot >= btrfs_header_nritems(&l->header)) {
 623                         ret = btrfs_next_leaf(root, &path);
 624                         if (ret == 0)
 625                                 continue;
 626                         if (ret < 0)
 627                                 goto error;
 628                         if (!start_found) {
 629                                 aligned = stripe_align(root, search_start);
 630                                 ins->objectid = aligned;
 631                                 ins->offset = (u64)-1 - aligned;
 632                                 start_found = 1;
 633                                 goto check_pending;
 634                         }
 635                         ins->objectid = stripe_align(root,
 636                                                      last_byte > search_start ?
 637                                                      last_byte : search_start);
 638                         ins->offset = (u64)-1 - ins->objectid;
 639                         goto check_pending;
 640                 }
 641                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
 642                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY)
 643                         goto next;
 644                 if (key.objectid >= search_start) {
 645                         if (start_found) {
 646                                 if (last_byte < search_start)
 647                                         last_byte = search_start;
 648                                 aligned = stripe_align(root, last_byte);
 649                                 hole_size = key.objectid - aligned;
 650                                 if (key.objectid > aligned &&
 651                                     hole_size > total_needed) {
 652                                         ins->objectid = aligned;
 653                                         ins->offset = hole_size;
 654                                         goto check_pending;
 655                                 }
 656                         }
 657                 }
 658                 start_found = 1;
 659                 last_byte = key.objectid + key.offset;
 660 next:
 661                 path.slots[0]++;
 662         }
 663         // FIXME -ENOSPC
 664 check_pending:
 665         /* we have to make sure we didn't find an extent that has already
 666          * been allocated by the map tree or the original allocation
 667          */
 668         btrfs_release_path(root, &path);
 669         BUG_ON(ins->objectid < search_start);
 670         if (find_cache_extent(&root->fs_info->pinned_tree,
 671                                 ins->objectid, total_needed)) {
 672                 search_start = ins->objectid + total_needed;
 673                 goto check_failed;
 674         }
 675         if (find_cache_extent(&root->fs_info->pending_tree,
 676                                 ins->objectid, total_needed)) {
 677                 search_start = ins->objectid + total_needed;
 678                 goto check_failed;
 679         }
 680         root->fs_info->last_insert.objectid = ins->objectid;
 681         ins->offset = total_needed;
 682         return 0;
 683 error:
 684         btrfs_release_path(root, &path);
 685         return ret;
 686 }
 687 /*
 688  * finds a free extent and does all the dirty work required for allocation
 689  * returns the key for the extent through ins, and a tree buffer for
 690  * the first block of the extent through buf.
 691  *
 692  * returns 0 if everything worked, non-zero otherwise.
 693  */
 694 static int alloc_extent(struct btrfs_trans_handle *trans,
 695                         struct btrfs_root *root, u64 num_bytes,
 696                         u64 root_objectid, u64 ref_generation, u64 owner,
 697                         u64 owner_offset, u64 search_start,
 698                         u64 search_end, struct btrfs_key *ins)
 699 {
 700         int ret;
 701         int pending_ret;
 702         u64 super_bytes_used, root_bytes_used;
 703         struct btrfs_fs_info *info = root->fs_info;
 704         struct btrfs_root *extent_root = info->extent_root;
 705         struct btrfs_extent_item extent_item;
 706         struct btrfs_path path;
 707
 708         btrfs_init_path(&path);
 709
 710         btrfs_set_extent_refs(&extent_item, 1);
 711
 712         ret = find_free_extent(trans, root, num_bytes, search_start,
 713                                search_end, ins);
 714         if (ret)
 715                 return ret;
 716
 717         super_bytes_used = btrfs_super_bytes_used(info->disk_super);
 718         btrfs_set_super_bytes_used(info->disk_super, super_bytes_used +
 719                                     num_bytes);
 720         root_bytes_used = btrfs_root_bytes_used(&root->root_item);
 721         btrfs_set_root_bytes_used(&root->root_item, root_bytes_used +
 722                                    num_bytes);
 723         if (root == extent_root) {
 724                 ret = insert_cache_extent(&root->fs_info->pending_tree,
 725                                             ins->objectid, ins->offset);
 726                 BUG_ON(ret);
 727                 goto update_block;
 728         }
 729         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
 730                                 sizeof(extent_item));
 731
 732         BUG_ON(ret);
 733         ret = insert_extent_backref(trans, extent_root, &path, ins->objectid,
 734                                     root_objectid, ref_generation,
 735                                     owner, owner_offset);
 736         BUG_ON(ret);
 737
 738         finish_current_insert(trans, extent_root);
 739         pending_ret = run_pending(trans, extent_root);
 740         if (ret)
 741                 return ret;
 742         if (pending_ret)
 743                 return pending_ret;
 744 update_block:
 745         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1);
 746         BUG_ON(ret);
 747         return 0;
 748 }
 749 /*
 750  * helper function to allocate a block for a given tree
 751  * returns the tree buffer or NULL.
 752  */
 753 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 754                                             struct btrfs_root *root,
 755                                             u32 blocksize)
 756 {
 757         u64 ref_generation;
 758         struct btrfs_key ins;
 759         int ret;
 760         struct btrfs_buffer *buf;
 761
 762         if (root->ref_cows)
 763                 ref_generation = trans->transid;
 764         else
 765                 ref_generation = 0;
 766
 767         ret = alloc_extent(trans, root, blocksize,
 768                            root->root_key.objectid, ref_generation,
 769                            0, 0, 0, (u64)-1, &ins);
 770         if (ret) {
 771                 BUG();
 772                 return NULL;
 773         }
 774         buf = find_tree_block(root, ins.objectid, blocksize);
 775         btrfs_set_header_generation(&buf->node.header, trans->transid);
 776         btrfs_set_header_bytenr(&buf->node.header, buf->bytenr);
 777         memcpy(buf->node.header.fsid, root->fs_info->disk_super->fsid,
 778                sizeof(buf->node.header.fsid));
 779         dirty_tree_block(trans, root, buf);
 780         return buf;
 781
 782 }
 783
 784 /*
 785  * helper function for drop_snapshot, this walks down the tree dropping ref
 786  * counts as it goes.
 787  */
 788 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 789                           *root, struct btrfs_path *path, int *level)
 790 {
 791         struct btrfs_buffer *next;
 792         struct btrfs_buffer *cur;
 793         struct btrfs_buffer *parent;
 794         u64 root_owner;
 795         u64 root_gen;
 796         u64 bytenr;
 797         int ret;
 798         u32 refs;
 799
 800         ret = lookup_block_ref(trans, root, path->nodes[*level]->bytenr,
 801                                btrfs_level_size(root, *level), &refs);
 802         BUG_ON(ret);
 803         if (refs > 1)
 804                 goto out;
 805         /*
 806          * walk down to the last node level and free all the leaves
 807          */
 808         while(*level > 0) {
 809                 u32 size = btrfs_level_size(root, *level - 1);
 810
 811                 cur = path->nodes[*level];
 812                 if (path->slots[*level] >=
 813                     btrfs_header_nritems(&cur->node.header))
 814                         break;
 815                 bytenr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
 816                 ret = lookup_block_ref(trans, root, bytenr, size, &refs);
 817                 if (refs != 1 || *level == 1) {
 818                         parent = path->nodes[*level];
 819                         root_owner = btrfs_header_owner(&parent->node.header);
 820                         root_gen =
 821                                 btrfs_header_generation(&parent->node.header);
 822                         path->slots[*level]++;
 823                         ret = btrfs_free_extent(trans, root, bytenr, size,
 824                                                 root_owner, root_gen, 0, 0, 1);
 825                         BUG_ON(ret);
 826                         continue;
 827                 }
 828                 BUG_ON(ret);
 829                 next = read_tree_block(root, bytenr, size);
 830                 if (path->nodes[*level-1])
 831                         btrfs_block_release(root, path->nodes[*level-1]);
 832                 path->nodes[*level-1] = next;
 833                 *level = btrfs_header_level(&next->node.header);
 834                 path->slots[*level] = 0;
 835         }
 836 out:
 837         if (*level == BTRFS_MAX_LEVEL - 1 || !path->nodes[*level + 1])
 838                 parent = path->nodes[*level];
 839         else
 840                 parent = path->nodes[*level + 1];
 841
 842         root_owner = btrfs_header_owner(&parent->node.header);
 843         root_gen = btrfs_header_generation(&parent->node.header);
 844         ret = btrfs_free_extent(trans, root, path->nodes[*level]->bytenr,
 845                                 btrfs_level_size(root, *level),
 846                                 root_owner, root_gen, 0, 0, 1);
 847         btrfs_block_release(root, path->nodes[*level]);
 848         path->nodes[*level] = NULL;
 849         *level += 1;
 850         BUG_ON(ret);
 851         return 0;
 852 }
 853
 854 /*
 855  * helper for dropping snapshots.  This walks back up the tree in the path
 856  * to find the first node higher up where we haven't yet gone through
 857  * all the slots
 858  */
 859 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 860                         *root, struct btrfs_path *path, int *level)
 861 {
 862         int i;
 863         int slot;
 864         int ret;
 865         u64 root_owner;
 866         u64 root_gen;
 867         struct btrfs_buffer *parent;
 868         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 869                 slot = path->slots[i];
 870                 if (slot <
 871                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
 872                         path->slots[i]++;
 873                         *level = i;
 874                         return 0;
 875                 } else {
 876                         if (path->nodes[*level] == root->node)
 877                                 parent = path->nodes[*level];
 878                         else
 879                                 parent = path->nodes[*level + 1];
 880
 881                         root_owner = btrfs_header_owner(&parent->node.header);
 882                         root_gen =
 883                                 btrfs_header_generation(&parent->node.header);
 884                         ret = btrfs_free_extent(trans, root,
 885                                         path->nodes[*level]->bytenr,
 886                                         btrfs_level_size(root, *level),
 887                                         root_owner, root_gen, 0, 0, 1);
 888                         btrfs_block_release(root, path->nodes[*level]);
 889                         path->nodes[*level] = NULL;
 890                         *level = i + 1;
 891                         BUG_ON(ret);
 892                 }
 893         }
 894         return 1;
 895 }
 896
 897 /*
 898  * drop the reference count on the tree rooted at 'snap'.  This traverses
 899  * the tree freeing any blocks that have a ref count of zero after being
 900  * decremented.
 901  */
 902 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
 903                         *root, struct btrfs_buffer *snap)
 904 {
 905         int ret = 0;
 906         int wret;
 907         int level;
 908         struct btrfs_path path;
 909         int i;
 910         int orig_level;
 911
 912         btrfs_init_path(&path);
 913
 914         level = btrfs_header_level(&snap->node.header);
 915         orig_level = level;
 916         path.nodes[level] = snap;
 917         path.slots[level] = 0;
 918         while(1) {
 919                 wret = walk_down_tree(trans, root, &path, &level);
 920                 if (wret > 0)
 921                         break;
 922                 if (wret < 0)
 923                         ret = wret;
 924
 925                 wret = walk_up_tree(trans, root, &path, &level);
 926                 if (wret > 0)
 927                         break;
 928                 if (wret < 0)
 929                         ret = wret;
 930         }
 931         for (i = 0; i <= orig_level; i++) {
 932                 if (path.nodes[i]) {
 933                         btrfs_block_release(root, path.nodes[i]);
 934                 }
 935         }
 936         return ret;
 937 }
 938
 939 int btrfs_free_block_groups(struct btrfs_fs_info *info)
 940 {
 941         struct btrfs_block_group_cache *bg;
 942         struct cache_extent *cache;
 943
 944         while(1) {
 945                 cache = find_first_cache_extent(&info->block_group_cache, 0);
 946                 if (!cache)
 947                         break;
 948                 bg = container_of(cache, struct btrfs_block_group_cache,
 949                                         cache);
 950                 remove_cache_extent(&info->block_group_cache, cache);
 951                 free(bg);
 952         }
 953         return 0;
 954 }
 955
 956 int btrfs_read_block_groups(struct btrfs_root *root)
 957 {
 958         struct btrfs_path path;
 959         int ret;
 960         int err = 0;
 961         struct btrfs_block_group_item *bi;
 962         struct btrfs_block_group_cache *bg;
 963         struct cache_tree *bg_cache;
 964         struct btrfs_key key;
 965         struct btrfs_key found_key;
 966         struct btrfs_leaf *leaf;
 967         u64 group_size = BTRFS_BLOCK_GROUP_SIZE;
 968
 969         root = root->fs_info->extent_root;
 970         bg_cache = &root->fs_info->block_group_cache;
 971         key.objectid = 0;
 972         key.offset = group_size;
 973         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
 974         btrfs_init_path(&path);
 975
 976         while(1) {
 977                 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 978                                         &key, &path, 0, 0);
 979                 if (ret != 0) {
 980                         err = ret;
 981                         break;
 982                 }
 983                 leaf = &path.nodes[0]->leaf;
 984                 btrfs_disk_key_to_cpu(&found_key,
 985                                       &leaf->items[path.slots[0]].key);
 986                 bg = malloc(sizeof(*bg));
 987                 if (!bg) {
 988                         err = -1;
 989                         break;
 990                 }
 991                 bi = btrfs_item_ptr(leaf, path.slots[0],
 992                                     struct btrfs_block_group_item);
 993                 memcpy(&bg->item, bi, sizeof(*bi));
 994                 memcpy(&bg->key, &found_key, sizeof(found_key));
 995                 key.objectid = found_key.objectid + found_key.offset;
 996                 btrfs_release_path(root, &path);
 997                 bg->cache.start = found_key.objectid;
 998                 bg->cache.size = found_key.offset;
 999                 bg->dirty = 0;
1000                 ret = insert_existing_cache_extent(bg_cache, &bg->cache);
1001                 BUG_ON(ret);
1002                 if (key.objectid >=
1003                     btrfs_super_total_bytes(root->fs_info->disk_super))
1004                         break;
1005         }
1006         btrfs_release_path(root, &path);
1007         return 0;
1008 }
1009
1010 int btrfs_insert_block_group(struct btrfs_trans_handle *trans,
1011                              struct btrfs_root *root,
1012                              struct btrfs_key *key,
1013                              struct btrfs_block_group_item *bi)
1014 {
1015         int ret;
1016         int pending_ret;
1017
1018         root = root->fs_info->extent_root;
1019         ret = btrfs_insert_item(trans, root, key, bi, sizeof(*bi));
1020         finish_current_insert(trans, root);
1021         pending_ret = run_pending(trans, root);
1022         if (ret)
1023                 return ret;
1024         if (pending_ret)
1025                 return pending_ret;
1026         return ret;
1027 }