extent-tree.c

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