fs/btrfs/ctree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
   4  */
   5
   6 #include <linux/sched.h>
   7 #include <linux/slab.h>
   8 #include <linux/rbtree.h>
   9 #include <linux/mm.h>
  10 #include "ctree.h"
  11 #include "disk-io.h"
  12 #include "transaction.h"
  13 #include "print-tree.h"
  14 #include "locking.h"
  15 #include "volumes.h"
  16 #include "qgroup.h"
  17
  18 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  19                       *root, struct btrfs_path *path, int level);
  20 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  21                       const struct btrfs_key *ins_key, struct btrfs_path *path,
  22                       int data_size, int extend);
  23 static int push_node_left(struct btrfs_trans_handle *trans,
  24                           struct btrfs_fs_info *fs_info,
  25                           struct extent_buffer *dst,
  26                           struct extent_buffer *src, int empty);
  27 static int balance_node_right(struct btrfs_trans_handle *trans,
  28                               struct btrfs_fs_info *fs_info,
  29                               struct extent_buffer *dst_buf,
  30                               struct extent_buffer *src_buf);
  31 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
  32                     int level, int slot);
  33
  34 struct btrfs_path *btrfs_alloc_path(void)
  35 {
  36         return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
  37 }
  38
  39 /*
  40  * set all locked nodes in the path to blocking locks.  This should
  41  * be done before scheduling
  42  */
  43 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
  44 {
  45         int i;
  46         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  47                 if (!p->nodes[i] || !p->locks[i])
  48                         continue;
  49                 /*
  50                  * If we currently have a spinning reader or writer lock this
  51                  * will bump the count of blocking holders and drop the
  52                  * spinlock.
  53                  */
  54                 if (p->locks[i] == BTRFS_READ_LOCK) {
  55                         btrfs_set_lock_blocking_read(p->nodes[i]);
  56                         p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
  57                 } else if (p->locks[i] == BTRFS_WRITE_LOCK) {
  58                         btrfs_set_lock_blocking_write(p->nodes[i]);
  59                         p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;
  60                 }
  61         }
  62 }
  63
  64 /* this also releases the path */
  65 void btrfs_free_path(struct btrfs_path *p)
  66 {
  67         if (!p)
  68                 return;
  69         btrfs_release_path(p);
  70         kmem_cache_free(btrfs_path_cachep, p);
  71 }
  72
  73 /*
  74  * path release drops references on the extent buffers in the path
  75  * and it drops any locks held by this path
  76  *
  77  * It is safe to call this on paths that no locks or extent buffers held.
  78  */
  79 noinline void btrfs_release_path(struct btrfs_path *p)
  80 {
  81         int i;
  82
  83         for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  84                 p->slots[i] = 0;
  85                 if (!p->nodes[i])
  86                         continue;
  87                 if (p->locks[i]) {
  88                         btrfs_tree_unlock_rw(p->nodes[i], p->locks[i]);
  89                         p->locks[i] = 0;
  90                 }
  91                 free_extent_buffer(p->nodes[i]);
  92                 p->nodes[i] = NULL;
  93         }
  94 }
  95
  96 /*
  97  * safely gets a reference on the root node of a tree.  A lock
  98  * is not taken, so a concurrent writer may put a different node
  99  * at the root of the tree.  See btrfs_lock_root_node for the
 100  * looping required.
 101  *
 102  * The extent buffer returned by this has a reference taken, so
 103  * it won't disappear.  It may stop being the root of the tree
 104  * at any time because there are no locks held.
 105  */
 106 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
 107 {
 108         struct extent_buffer *eb;
 109
 110         while (1) {
 111                 rcu_read_lock();
 112                 eb = rcu_dereference(root->node);
 113
 114                 /*
 115                  * RCU really hurts here, we could free up the root node because
 116                  * it was COWed but we may not get the new root node yet so do
 117                  * the inc_not_zero dance and if it doesn't work then
 118                  * synchronize_rcu and try again.
 119                  */
 120                 if (atomic_inc_not_zero(&eb->refs)) {
 121                         rcu_read_unlock();
 122                         break;
 123                 }
 124                 rcu_read_unlock();
 125                 synchronize_rcu();
 126         }
 127         return eb;
 128 }
 129
 130 /* loop around taking references on and locking the root node of the
 131  * tree until you end up with a lock on the root.  A locked buffer
 132  * is returned, with a reference held.
 133  */
 134 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
 135 {
 136         struct extent_buffer *eb;
 137
 138         while (1) {
 139                 eb = btrfs_root_node(root);
 140                 btrfs_tree_lock(eb);
 141                 if (eb == root->node)
 142                         break;
 143                 btrfs_tree_unlock(eb);
 144                 free_extent_buffer(eb);
 145         }
 146         return eb;
 147 }
 148
 149 /* loop around taking references on and locking the root node of the
 150  * tree until you end up with a lock on the root.  A locked buffer
 151  * is returned, with a reference held.
 152  */
 153 struct extent_buffer *btrfs_read_lock_root_node(struct btrfs_root *root)
 154 {
 155         struct extent_buffer *eb;
 156
 157         while (1) {
 158                 eb = btrfs_root_node(root);
 159                 btrfs_tree_read_lock(eb);
 160                 if (eb == root->node)
 161                         break;
 162                 btrfs_tree_read_unlock(eb);
 163                 free_extent_buffer(eb);
 164         }
 165         return eb;
 166 }
 167
 168 /* cowonly root (everything not a reference counted cow subvolume), just get
 169  * put onto a simple dirty list.  transaction.c walks this to make sure they
 170  * get properly updated on disk.
 171  */
 172 static void add_root_to_dirty_list(struct btrfs_root *root)
 173 {
 174         struct btrfs_fs_info *fs_info = root->fs_info;
 175
 176         if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
 177             !test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
 178                 return;
 179
 180         spin_lock(&fs_info->trans_lock);
 181         if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
 182                 /* Want the extent tree to be the last on the list */
 183                 if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID)
 184                         list_move_tail(&root->dirty_list,
 185                                        &fs_info->dirty_cowonly_roots);
 186                 else
 187                         list_move(&root->dirty_list,
 188                                   &fs_info->dirty_cowonly_roots);
 189         }
 190         spin_unlock(&fs_info->trans_lock);
 191 }
 192
 193 /*
 194  * used by snapshot creation to make a copy of a root for a tree with
 195  * a given objectid.  The buffer with the new root node is returned in
 196  * cow_ret, and this func returns zero on success or a negative error code.
 197  */
 198 int btrfs_copy_root(struct btrfs_trans_handle *trans,
 199                       struct btrfs_root *root,
 200                       struct extent_buffer *buf,
 201                       struct extent_buffer **cow_ret, u64 new_root_objectid)
 202 {
 203         struct btrfs_fs_info *fs_info = root->fs_info;
 204         struct extent_buffer *cow;
 205         int ret = 0;
 206         int level;
 207         struct btrfs_disk_key disk_key;
 208
 209         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 210                 trans->transid != fs_info->running_transaction->transid);
 211         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 212                 trans->transid != root->last_trans);
 213
 214         level = btrfs_header_level(buf);
 215         if (level == 0)
 216                 btrfs_item_key(buf, &disk_key, 0);
 217         else
 218                 btrfs_node_key(buf, &disk_key, 0);
 219
 220         cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
 221                         &disk_key, level, buf->start, 0);
 222         if (IS_ERR(cow))
 223                 return PTR_ERR(cow);
 224
 225         copy_extent_buffer_full(cow, buf);
 226         btrfs_set_header_bytenr(cow, cow->start);
 227         btrfs_set_header_generation(cow, trans->transid);
 228         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
 229         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
 230                                      BTRFS_HEADER_FLAG_RELOC);
 231         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 232                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
 233         else
 234                 btrfs_set_header_owner(cow, new_root_objectid);
 235
 236         write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
 237
 238         WARN_ON(btrfs_header_generation(buf) > trans->transid);
 239         if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
 240                 ret = btrfs_inc_ref(trans, root, cow, 1);
 241         else
 242                 ret = btrfs_inc_ref(trans, root, cow, 0);
 243
 244         if (ret)
 245                 return ret;
 246
 247         btrfs_mark_buffer_dirty(cow);
 248         *cow_ret = cow;
 249         return 0;
 250 }
 251
 252 enum mod_log_op {
 253         MOD_LOG_KEY_REPLACE,
 254         MOD_LOG_KEY_ADD,
 255         MOD_LOG_KEY_REMOVE,
 256         MOD_LOG_KEY_REMOVE_WHILE_FREEING,
 257         MOD_LOG_KEY_REMOVE_WHILE_MOVING,
 258         MOD_LOG_MOVE_KEYS,
 259         MOD_LOG_ROOT_REPLACE,
 260 };
 261
 262 struct tree_mod_root {
 263         u64 logical;
 264         u8 level;
 265 };
 266
 267 struct tree_mod_elem {
 268         struct rb_node node;
 269         u64 logical;
 270         u64 seq;
 271         enum mod_log_op op;
 272
 273         /* this is used for MOD_LOG_KEY_* and MOD_LOG_MOVE_KEYS operations */
 274         int slot;
 275
 276         /* this is used for MOD_LOG_KEY* and MOD_LOG_ROOT_REPLACE */
 277         u64 generation;
 278
 279         /* those are used for op == MOD_LOG_KEY_{REPLACE,REMOVE} */
 280         struct btrfs_disk_key key;
 281         u64 blockptr;
 282
 283         /* this is used for op == MOD_LOG_MOVE_KEYS */
 284         struct {
 285                 int dst_slot;
 286                 int nr_items;
 287         } move;
 288
 289         /* this is used for op == MOD_LOG_ROOT_REPLACE */
 290         struct tree_mod_root old_root;
 291 };
 292
 293 /*
 294  * Pull a new tree mod seq number for our operation.
 295  */
 296 static inline u64 btrfs_inc_tree_mod_seq(struct btrfs_fs_info *fs_info)
 297 {
 298         return atomic64_inc_return(&fs_info->tree_mod_seq);
 299 }
 300
 301 /*
 302  * This adds a new blocker to the tree mod log's blocker list if the @elem
 303  * passed does not already have a sequence number set. So when a caller expects
 304  * to record tree modifications, it should ensure to set elem->seq to zero
 305  * before calling btrfs_get_tree_mod_seq.
 306  * Returns a fresh, unused tree log modification sequence number, even if no new
 307  * blocker was added.
 308  */
 309 u64 btrfs_get_tree_mod_seq(struct btrfs_fs_info *fs_info,
 310                            struct seq_list *elem)
 311 {
 312         write_lock(&fs_info->tree_mod_log_lock);
 313         spin_lock(&fs_info->tree_mod_seq_lock);
 314         if (!elem->seq) {
 315                 elem->seq = btrfs_inc_tree_mod_seq(fs_info);
 316                 list_add_tail(&elem->list, &fs_info->tree_mod_seq_list);
 317         }
 318         spin_unlock(&fs_info->tree_mod_seq_lock);
 319         write_unlock(&fs_info->tree_mod_log_lock);
 320
 321         return elem->seq;
 322 }
 323
 324 void btrfs_put_tree_mod_seq(struct btrfs_fs_info *fs_info,
 325                             struct seq_list *elem)
 326 {
 327         struct rb_root *tm_root;
 328         struct rb_node *node;
 329         struct rb_node *next;
 330         struct seq_list *cur_elem;
 331         struct tree_mod_elem *tm;
 332         u64 min_seq = (u64)-1;
 333         u64 seq_putting = elem->seq;
 334
 335         if (!seq_putting)
 336                 return;
 337
 338         spin_lock(&fs_info->tree_mod_seq_lock);
 339         list_del(&elem->list);
 340         elem->seq = 0;
 341
 342         list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) {
 343                 if (cur_elem->seq < min_seq) {
 344                         if (seq_putting > cur_elem->seq) {
 345                                 /*
 346                                  * blocker with lower sequence number exists, we
 347                                  * cannot remove anything from the log
 348                                  */
 349                                 spin_unlock(&fs_info->tree_mod_seq_lock);
 350                                 return;
 351                         }
 352                         min_seq = cur_elem->seq;
 353                 }
 354         }
 355         spin_unlock(&fs_info->tree_mod_seq_lock);
 356
 357         /*
 358          * anything that's lower than the lowest existing (read: blocked)
 359          * sequence number can be removed from the tree.
 360          */
 361         write_lock(&fs_info->tree_mod_log_lock);
 362         tm_root = &fs_info->tree_mod_log;
 363         for (node = rb_first(tm_root); node; node = next) {
 364                 next = rb_next(node);
 365                 tm = rb_entry(node, struct tree_mod_elem, node);
 366                 if (tm->seq > min_seq)
 367                         continue;
 368                 rb_erase(node, tm_root);
 369                 kfree(tm);
 370         }
 371         write_unlock(&fs_info->tree_mod_log_lock);
 372 }
 373
 374 /*
 375  * key order of the log:
 376  *       node/leaf start address -> sequence
 377  *
 378  * The 'start address' is the logical address of the *new* root node
 379  * for root replace operations, or the logical address of the affected
 380  * block for all other operations.
 381  *
 382  * Note: must be called with write lock for fs_info::tree_mod_log_lock.
 383  */
 384 static noinline int
 385 __tree_mod_log_insert(struct btrfs_fs_info *fs_info, struct tree_mod_elem *tm)
 386 {
 387         struct rb_root *tm_root;
 388         struct rb_node **new;
 389         struct rb_node *parent = NULL;
 390         struct tree_mod_elem *cur;
 391
 392         tm->seq = btrfs_inc_tree_mod_seq(fs_info);
 393
 394         tm_root = &fs_info->tree_mod_log;
 395         new = &tm_root->rb_node;
 396         while (*new) {
 397                 cur = rb_entry(*new, struct tree_mod_elem, node);
 398                 parent = *new;
 399                 if (cur->logical < tm->logical)
 400                         new = &((*new)->rb_left);
 401                 else if (cur->logical > tm->logical)
 402                         new = &((*new)->rb_right);
 403                 else if (cur->seq < tm->seq)
 404                         new = &((*new)->rb_left);
 405                 else if (cur->seq > tm->seq)
 406                         new = &((*new)->rb_right);
 407                 else
 408                         return -EEXIST;
 409         }
 410
 411         rb_link_node(&tm->node, parent, new);
 412         rb_insert_color(&tm->node, tm_root);
 413         return 0;
 414 }
 415
 416 /*
 417  * Determines if logging can be omitted. Returns 1 if it can. Otherwise, it
 418  * returns zero with the tree_mod_log_lock acquired. The caller must hold
 419  * this until all tree mod log insertions are recorded in the rb tree and then
 420  * write unlock fs_info::tree_mod_log_lock.
 421  */
 422 static inline int tree_mod_dont_log(struct btrfs_fs_info *fs_info,
 423                                     struct extent_buffer *eb) {
 424         smp_mb();
 425         if (list_empty(&(fs_info)->tree_mod_seq_list))
 426                 return 1;
 427         if (eb && btrfs_header_level(eb) == 0)
 428                 return 1;
 429
 430         write_lock(&fs_info->tree_mod_log_lock);
 431         if (list_empty(&(fs_info)->tree_mod_seq_list)) {
 432                 write_unlock(&fs_info->tree_mod_log_lock);
 433                 return 1;
 434         }
 435
 436         return 0;
 437 }
 438
 439 /* Similar to tree_mod_dont_log, but doesn't acquire any locks. */
 440 static inline int tree_mod_need_log(const struct btrfs_fs_info *fs_info,
 441                                     struct extent_buffer *eb)
 442 {
 443         smp_mb();
 444         if (list_empty(&(fs_info)->tree_mod_seq_list))
 445                 return 0;
 446         if (eb && btrfs_header_level(eb) == 0)
 447                 return 0;
 448
 449         return 1;
 450 }
 451
 452 static struct tree_mod_elem *
 453 alloc_tree_mod_elem(struct extent_buffer *eb, int slot,
 454                     enum mod_log_op op, gfp_t flags)
 455 {
 456         struct tree_mod_elem *tm;
 457
 458         tm = kzalloc(sizeof(*tm), flags);
 459         if (!tm)
 460                 return NULL;
 461
 462         tm->logical = eb->start;
 463         if (op != MOD_LOG_KEY_ADD) {
 464                 btrfs_node_key(eb, &tm->key, slot);
 465                 tm->blockptr = btrfs_node_blockptr(eb, slot);
 466         }
 467         tm->op = op;
 468         tm->slot = slot;
 469         tm->generation = btrfs_node_ptr_generation(eb, slot);
 470         RB_CLEAR_NODE(&tm->node);
 471
 472         return tm;
 473 }
 474
 475 static noinline int tree_mod_log_insert_key(struct extent_buffer *eb, int slot,
 476                 enum mod_log_op op, gfp_t flags)
 477 {
 478         struct tree_mod_elem *tm;
 479         int ret;
 480
 481         if (!tree_mod_need_log(eb->fs_info, eb))
 482                 return 0;
 483
 484         tm = alloc_tree_mod_elem(eb, slot, op, flags);
 485         if (!tm)
 486                 return -ENOMEM;
 487
 488         if (tree_mod_dont_log(eb->fs_info, eb)) {
 489                 kfree(tm);
 490                 return 0;
 491         }
 492
 493         ret = __tree_mod_log_insert(eb->fs_info, tm);
 494         write_unlock(&eb->fs_info->tree_mod_log_lock);
 495         if (ret)
 496                 kfree(tm);
 497
 498         return ret;
 499 }
 500
 501 static noinline int tree_mod_log_insert_move(struct extent_buffer *eb,
 502                 int dst_slot, int src_slot, int nr_items)
 503 {
 504         struct tree_mod_elem *tm = NULL;
 505         struct tree_mod_elem **tm_list = NULL;
 506         int ret = 0;
 507         int i;
 508         int locked = 0;
 509
 510         if (!tree_mod_need_log(eb->fs_info, eb))
 511                 return 0;
 512
 513         tm_list = kcalloc(nr_items, sizeof(struct tree_mod_elem *), GFP_NOFS);
 514         if (!tm_list)
 515                 return -ENOMEM;
 516
 517         tm = kzalloc(sizeof(*tm), GFP_NOFS);
 518         if (!tm) {
 519                 ret = -ENOMEM;
 520                 goto free_tms;
 521         }
 522
 523         tm->logical = eb->start;
 524         tm->slot = src_slot;
 525         tm->move.dst_slot = dst_slot;
 526         tm->move.nr_items = nr_items;
 527         tm->op = MOD_LOG_MOVE_KEYS;
 528
 529         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 530                 tm_list[i] = alloc_tree_mod_elem(eb, i + dst_slot,
 531                     MOD_LOG_KEY_REMOVE_WHILE_MOVING, GFP_NOFS);
 532                 if (!tm_list[i]) {
 533                         ret = -ENOMEM;
 534                         goto free_tms;
 535                 }
 536         }
 537
 538         if (tree_mod_dont_log(eb->fs_info, eb))
 539                 goto free_tms;
 540         locked = 1;
 541
 542         /*
 543          * When we override something during the move, we log these removals.
 544          * This can only happen when we move towards the beginning of the
 545          * buffer, i.e. dst_slot < src_slot.
 546          */
 547         for (i = 0; i + dst_slot < src_slot && i < nr_items; i++) {
 548                 ret = __tree_mod_log_insert(eb->fs_info, tm_list[i]);
 549                 if (ret)
 550                         goto free_tms;
 551         }
 552
 553         ret = __tree_mod_log_insert(eb->fs_info, tm);
 554         if (ret)
 555                 goto free_tms;
 556         write_unlock(&eb->fs_info->tree_mod_log_lock);
 557         kfree(tm_list);
 558
 559         return 0;
 560 free_tms:
 561         for (i = 0; i < nr_items; i++) {
 562                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 563                         rb_erase(&tm_list[i]->node, &eb->fs_info->tree_mod_log);
 564                 kfree(tm_list[i]);
 565         }
 566         if (locked)
 567                 write_unlock(&eb->fs_info->tree_mod_log_lock);
 568         kfree(tm_list);
 569         kfree(tm);
 570
 571         return ret;
 572 }
 573
 574 static inline int
 575 __tree_mod_log_free_eb(struct btrfs_fs_info *fs_info,
 576                        struct tree_mod_elem **tm_list,
 577                        int nritems)
 578 {
 579         int i, j;
 580         int ret;
 581
 582         for (i = nritems - 1; i >= 0; i--) {
 583                 ret = __tree_mod_log_insert(fs_info, tm_list[i]);
 584                 if (ret) {
 585                         for (j = nritems - 1; j > i; j--)
 586                                 rb_erase(&tm_list[j]->node,
 587                                          &fs_info->tree_mod_log);
 588                         return ret;
 589                 }
 590         }
 591
 592         return 0;
 593 }
 594
 595 static noinline int tree_mod_log_insert_root(struct extent_buffer *old_root,
 596                          struct extent_buffer *new_root, int log_removal)
 597 {
 598         struct btrfs_fs_info *fs_info = old_root->fs_info;
 599         struct tree_mod_elem *tm = NULL;
 600         struct tree_mod_elem **tm_list = NULL;
 601         int nritems = 0;
 602         int ret = 0;
 603         int i;
 604
 605         if (!tree_mod_need_log(fs_info, NULL))
 606                 return 0;
 607
 608         if (log_removal && btrfs_header_level(old_root) > 0) {
 609                 nritems = btrfs_header_nritems(old_root);
 610                 tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *),
 611                                   GFP_NOFS);
 612                 if (!tm_list) {
 613                         ret = -ENOMEM;
 614                         goto free_tms;
 615                 }
 616                 for (i = 0; i < nritems; i++) {
 617                         tm_list[i] = alloc_tree_mod_elem(old_root, i,
 618                             MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
 619                         if (!tm_list[i]) {
 620                                 ret = -ENOMEM;
 621                                 goto free_tms;
 622                         }
 623                 }
 624         }
 625
 626         tm = kzalloc(sizeof(*tm), GFP_NOFS);
 627         if (!tm) {
 628                 ret = -ENOMEM;
 629                 goto free_tms;
 630         }
 631
 632         tm->logical = new_root->start;
 633         tm->old_root.logical = old_root->start;
 634         tm->old_root.level = btrfs_header_level(old_root);
 635         tm->generation = btrfs_header_generation(old_root);
 636         tm->op = MOD_LOG_ROOT_REPLACE;
 637
 638         if (tree_mod_dont_log(fs_info, NULL))
 639                 goto free_tms;
 640
 641         if (tm_list)
 642                 ret = __tree_mod_log_free_eb(fs_info, tm_list, nritems);
 643         if (!ret)
 644                 ret = __tree_mod_log_insert(fs_info, tm);
 645
 646         write_unlock(&fs_info->tree_mod_log_lock);
 647         if (ret)
 648                 goto free_tms;
 649         kfree(tm_list);
 650
 651         return ret;
 652
 653 free_tms:
 654         if (tm_list) {
 655                 for (i = 0; i < nritems; i++)
 656                         kfree(tm_list[i]);
 657                 kfree(tm_list);
 658         }
 659         kfree(tm);
 660
 661         return ret;
 662 }
 663
 664 static struct tree_mod_elem *
 665 __tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq,
 666                       int smallest)
 667 {
 668         struct rb_root *tm_root;
 669         struct rb_node *node;
 670         struct tree_mod_elem *cur = NULL;
 671         struct tree_mod_elem *found = NULL;
 672
 673         read_lock(&fs_info->tree_mod_log_lock);
 674         tm_root = &fs_info->tree_mod_log;
 675         node = tm_root->rb_node;
 676         while (node) {
 677                 cur = rb_entry(node, struct tree_mod_elem, node);
 678                 if (cur->logical < start) {
 679                         node = node->rb_left;
 680                 } else if (cur->logical > start) {
 681                         node = node->rb_right;
 682                 } else if (cur->seq < min_seq) {
 683                         node = node->rb_left;
 684                 } else if (!smallest) {
 685                         /* we want the node with the highest seq */
 686                         if (found)
 687                                 BUG_ON(found->seq > cur->seq);
 688                         found = cur;
 689                         node = node->rb_left;
 690                 } else if (cur->seq > min_seq) {
 691                         /* we want the node with the smallest seq */
 692                         if (found)
 693                                 BUG_ON(found->seq < cur->seq);
 694                         found = cur;
 695                         node = node->rb_right;
 696                 } else {
 697                         found = cur;
 698                         break;
 699                 }
 700         }
 701         read_unlock(&fs_info->tree_mod_log_lock);
 702
 703         return found;
 704 }
 705
 706 /*
 707  * this returns the element from the log with the smallest time sequence
 708  * value that's in the log (the oldest log item). any element with a time
 709  * sequence lower than min_seq will be ignored.
 710  */
 711 static struct tree_mod_elem *
 712 tree_mod_log_search_oldest(struct btrfs_fs_info *fs_info, u64 start,
 713                            u64 min_seq)
 714 {
 715         return __tree_mod_log_search(fs_info, start, min_seq, 1);
 716 }
 717
 718 /*
 719  * this returns the element from the log with the largest time sequence
 720  * value that's in the log (the most recent log item). any element with
 721  * a time sequence lower than min_seq will be ignored.
 722  */
 723 static struct tree_mod_elem *
 724 tree_mod_log_search(struct btrfs_fs_info *fs_info, u64 start, u64 min_seq)
 725 {
 726         return __tree_mod_log_search(fs_info, start, min_seq, 0);
 727 }
 728
 729 static noinline int
 730 tree_mod_log_eb_copy(struct btrfs_fs_info *fs_info, struct extent_buffer *dst,
 731                      struct extent_buffer *src, unsigned long dst_offset,
 732                      unsigned long src_offset, int nr_items)
 733 {
 734         int ret = 0;
 735         struct tree_mod_elem **tm_list = NULL;
 736         struct tree_mod_elem **tm_list_add, **tm_list_rem;
 737         int i;
 738         int locked = 0;
 739
 740         if (!tree_mod_need_log(fs_info, NULL))
 741                 return 0;
 742
 743         if (btrfs_header_level(dst) == 0 && btrfs_header_level(src) == 0)
 744                 return 0;
 745
 746         tm_list = kcalloc(nr_items * 2, sizeof(struct tree_mod_elem *),
 747                           GFP_NOFS);
 748         if (!tm_list)
 749                 return -ENOMEM;
 750
 751         tm_list_add = tm_list;
 752         tm_list_rem = tm_list + nr_items;
 753         for (i = 0; i < nr_items; i++) {
 754                 tm_list_rem[i] = alloc_tree_mod_elem(src, i + src_offset,
 755                     MOD_LOG_KEY_REMOVE, GFP_NOFS);
 756                 if (!tm_list_rem[i]) {
 757                         ret = -ENOMEM;
 758                         goto free_tms;
 759                 }
 760
 761                 tm_list_add[i] = alloc_tree_mod_elem(dst, i + dst_offset,
 762                     MOD_LOG_KEY_ADD, GFP_NOFS);
 763                 if (!tm_list_add[i]) {
 764                         ret = -ENOMEM;
 765                         goto free_tms;
 766                 }
 767         }
 768
 769         if (tree_mod_dont_log(fs_info, NULL))
 770                 goto free_tms;
 771         locked = 1;
 772
 773         for (i = 0; i < nr_items; i++) {
 774                 ret = __tree_mod_log_insert(fs_info, tm_list_rem[i]);
 775                 if (ret)
 776                         goto free_tms;
 777                 ret = __tree_mod_log_insert(fs_info, tm_list_add[i]);
 778                 if (ret)
 779                         goto free_tms;
 780         }
 781
 782         write_unlock(&fs_info->tree_mod_log_lock);
 783         kfree(tm_list);
 784
 785         return 0;
 786
 787 free_tms:
 788         for (i = 0; i < nr_items * 2; i++) {
 789                 if (tm_list[i] && !RB_EMPTY_NODE(&tm_list[i]->node))
 790                         rb_erase(&tm_list[i]->node, &fs_info->tree_mod_log);
 791                 kfree(tm_list[i]);
 792         }
 793         if (locked)
 794                 write_unlock(&fs_info->tree_mod_log_lock);
 795         kfree(tm_list);
 796
 797         return ret;
 798 }
 799
 800 static noinline int tree_mod_log_free_eb(struct extent_buffer *eb)
 801 {
 802         struct tree_mod_elem **tm_list = NULL;
 803         int nritems = 0;
 804         int i;
 805         int ret = 0;
 806
 807         if (btrfs_header_level(eb) == 0)
 808                 return 0;
 809
 810         if (!tree_mod_need_log(eb->fs_info, NULL))
 811                 return 0;
 812
 813         nritems = btrfs_header_nritems(eb);
 814         tm_list = kcalloc(nritems, sizeof(struct tree_mod_elem *), GFP_NOFS);
 815         if (!tm_list)
 816                 return -ENOMEM;
 817
 818         for (i = 0; i < nritems; i++) {
 819                 tm_list[i] = alloc_tree_mod_elem(eb, i,
 820                     MOD_LOG_KEY_REMOVE_WHILE_FREEING, GFP_NOFS);
 821                 if (!tm_list[i]) {
 822                         ret = -ENOMEM;
 823                         goto free_tms;
 824                 }
 825         }
 826
 827         if (tree_mod_dont_log(eb->fs_info, eb))
 828                 goto free_tms;
 829
 830         ret = __tree_mod_log_free_eb(eb->fs_info, tm_list, nritems);
 831         write_unlock(&eb->fs_info->tree_mod_log_lock);
 832         if (ret)
 833                 goto free_tms;
 834         kfree(tm_list);
 835
 836         return 0;
 837
 838 free_tms:
 839         for (i = 0; i < nritems; i++)
 840                 kfree(tm_list[i]);
 841         kfree(tm_list);
 842
 843         return ret;
 844 }
 845
 846 /*
 847  * check if the tree block can be shared by multiple trees
 848  */
 849 int btrfs_block_can_be_shared(struct btrfs_root *root,
 850                               struct extent_buffer *buf)
 851 {
 852         /*
 853          * Tree blocks not in reference counted trees and tree roots
 854          * are never shared. If a block was allocated after the last
 855          * snapshot and the block was not allocated by tree relocation,
 856          * we know the block is not shared.
 857          */
 858         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
 859             buf != root->node && buf != root->commit_root &&
 860             (btrfs_header_generation(buf) <=
 861              btrfs_root_last_snapshot(&root->root_item) ||
 862              btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
 863                 return 1;
 864
 865         return 0;
 866 }
 867
 868 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
 869                                        struct btrfs_root *root,
 870                                        struct extent_buffer *buf,
 871                                        struct extent_buffer *cow,
 872                                        int *last_ref)
 873 {
 874         struct btrfs_fs_info *fs_info = root->fs_info;
 875         u64 refs;
 876         u64 owner;
 877         u64 flags;
 878         u64 new_flags = 0;
 879         int ret;
 880
 881         /*
 882          * Backrefs update rules:
 883          *
 884          * Always use full backrefs for extent pointers in tree block
 885          * allocated by tree relocation.
 886          *
 887          * If a shared tree block is no longer referenced by its owner
 888          * tree (btrfs_header_owner(buf) == root->root_key.objectid),
 889          * use full backrefs for extent pointers in tree block.
 890          *
 891          * If a tree block is been relocating
 892          * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
 893          * use full backrefs for extent pointers in tree block.
 894          * The reason for this is some operations (such as drop tree)
 895          * are only allowed for blocks use full backrefs.
 896          */
 897
 898         if (btrfs_block_can_be_shared(root, buf)) {
 899                 ret = btrfs_lookup_extent_info(trans, fs_info, buf->start,
 900                                                btrfs_header_level(buf), 1,
 901                                                &refs, &flags);
 902                 if (ret)
 903                         return ret;
 904                 if (refs == 0) {
 905                         ret = -EROFS;
 906                         btrfs_handle_fs_error(fs_info, ret, NULL);
 907                         return ret;
 908                 }
 909         } else {
 910                 refs = 1;
 911                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
 912                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
 913                         flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
 914                 else
 915                         flags = 0;
 916         }
 917
 918         owner = btrfs_header_owner(buf);
 919         BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
 920                !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
 921
 922         if (refs > 1) {
 923                 if ((owner == root->root_key.objectid ||
 924                      root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
 925                     !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
 926                         ret = btrfs_inc_ref(trans, root, buf, 1);
 927                         if (ret)
 928                                 return ret;
 929
 930                         if (root->root_key.objectid ==
 931                             BTRFS_TREE_RELOC_OBJECTID) {
 932                                 ret = btrfs_dec_ref(trans, root, buf, 0);
 933                                 if (ret)
 934                                         return ret;
 935                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 936                                 if (ret)
 937                                         return ret;
 938                         }
 939                         new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
 940                 } else {
 941
 942                         if (root->root_key.objectid ==
 943                             BTRFS_TREE_RELOC_OBJECTID)
 944                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 945                         else
 946                                 ret = btrfs_inc_ref(trans, root, cow, 0);
 947                         if (ret)
 948                                 return ret;
 949                 }
 950                 if (new_flags != 0) {
 951                         int level = btrfs_header_level(buf);
 952
 953                         ret = btrfs_set_disk_extent_flags(trans, fs_info,
 954                                                           buf->start,
 955                                                           buf->len,
 956                                                           new_flags, level, 0);
 957                         if (ret)
 958                                 return ret;
 959                 }
 960         } else {
 961                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
 962                         if (root->root_key.objectid ==
 963                             BTRFS_TREE_RELOC_OBJECTID)
 964                                 ret = btrfs_inc_ref(trans, root, cow, 1);
 965                         else
 966                                 ret = btrfs_inc_ref(trans, root, cow, 0);
 967                         if (ret)
 968                                 return ret;
 969                         ret = btrfs_dec_ref(trans, root, buf, 1);
 970                         if (ret)
 971                                 return ret;
 972                 }
 973                 clean_tree_block(fs_info, buf);
 974                 *last_ref = 1;
 975         }
 976         return 0;
 977 }
 978
 979 static struct extent_buffer *alloc_tree_block_no_bg_flush(
 980                                           struct btrfs_trans_handle *trans,
 981                                           struct btrfs_root *root,
 982                                           u64 parent_start,
 983                                           const struct btrfs_disk_key *disk_key,
 984                                           int level,
 985                                           u64 hint,
 986                                           u64 empty_size)
 987 {
 988         struct btrfs_fs_info *fs_info = root->fs_info;
 989         struct extent_buffer *ret;
 990
 991         /*
 992          * If we are COWing a node/leaf from the extent, chunk, device or free
 993          * space trees, make sure that we do not finish block group creation of
 994          * pending block groups. We do this to avoid a deadlock.
 995          * COWing can result in allocation of a new chunk, and flushing pending
 996          * block groups (btrfs_create_pending_block_groups()) can be triggered
 997          * when finishing allocation of a new chunk. Creation of a pending block
 998          * group modifies the extent, chunk, device and free space trees,
 999          * therefore we could deadlock with ourselves since we are holding a
1000          * lock on an extent buffer that btrfs_create_pending_block_groups() may
1001          * try to COW later.
1002          * For similar reasons, we also need to delay flushing pending block
1003          * groups when splitting a leaf or node, from one of those trees, since
1004          * we are holding a write lock on it and its parent or when inserting a
1005          * new root node for one of those trees.
1006          */
1007         if (root == fs_info->extent_root ||
1008             root == fs_info->chunk_root ||
1009             root == fs_info->dev_root ||
1010             root == fs_info->free_space_root)
1011                 trans->can_flush_pending_bgs = false;
1012
1013         ret = btrfs_alloc_tree_block(trans, root, parent_start,
1014                                      root->root_key.objectid, disk_key, level,
1015                                      hint, empty_size);
1016         trans->can_flush_pending_bgs = true;
1017
1018         return ret;
1019 }
1020
1021 /*
1022  * does the dirty work in cow of a single block.  The parent block (if
1023  * supplied) is updated to point to the new cow copy.  The new buffer is marked
1024  * dirty and returned locked.  If you modify the block it needs to be marked
1025  * dirty again.
1026  *
1027  * search_start -- an allocation hint for the new block
1028  *
1029  * empty_size -- a hint that you plan on doing more cow.  This is the size in
1030  * bytes the allocator should try to find free next to the block it returns.
1031  * This is just a hint and may be ignored by the allocator.
1032  */
1033 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
1034                              struct btrfs_root *root,
1035                              struct extent_buffer *buf,
1036                              struct extent_buffer *parent, int parent_slot,
1037                              struct extent_buffer **cow_ret,
1038                              u64 search_start, u64 empty_size)
1039 {
1040         struct btrfs_fs_info *fs_info = root->fs_info;
1041         struct btrfs_disk_key disk_key;
1042         struct extent_buffer *cow;
1043         int level, ret;
1044         int last_ref = 0;
1045         int unlock_orig = 0;
1046         u64 parent_start = 0;
1047
1048         if (*cow_ret == buf)
1049                 unlock_orig = 1;
1050
1051         btrfs_assert_tree_locked(buf);
1052
1053         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1054                 trans->transid != fs_info->running_transaction->transid);
1055         WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
1056                 trans->transid != root->last_trans);
1057
1058         level = btrfs_header_level(buf);
1059
1060         if (level == 0)
1061                 btrfs_item_key(buf, &disk_key, 0);
1062         else
1063                 btrfs_node_key(buf, &disk_key, 0);
1064
1065         if ((root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) && parent)
1066                 parent_start = parent->start;
1067
1068         cow = alloc_tree_block_no_bg_flush(trans, root, parent_start, &disk_key,
1069                                            level, search_start, empty_size);
1070         if (IS_ERR(cow))
1071                 return PTR_ERR(cow);
1072
1073         /* cow is set to blocking by btrfs_init_new_buffer */
1074
1075         copy_extent_buffer_full(cow, buf);
1076         btrfs_set_header_bytenr(cow, cow->start);
1077         btrfs_set_header_generation(cow, trans->transid);
1078         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1079         btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
1080                                      BTRFS_HEADER_FLAG_RELOC);
1081         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1082                 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
1083         else
1084                 btrfs_set_header_owner(cow, root->root_key.objectid);
1085
1086         write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
1087
1088         ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
1089         if (ret) {
1090                 btrfs_abort_transaction(trans, ret);
1091                 return ret;
1092         }
1093
1094         if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
1095                 ret = btrfs_reloc_cow_block(trans, root, buf, cow);
1096                 if (ret) {
1097                         btrfs_abort_transaction(trans, ret);
1098                         return ret;
1099                 }
1100         }
1101
1102         if (buf == root->node) {
1103                 WARN_ON(parent && parent != buf);
1104                 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
1105                     btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1106                         parent_start = buf->start;
1107
1108                 extent_buffer_get(cow);
1109                 ret = tree_mod_log_insert_root(root->node, cow, 1);
1110                 BUG_ON(ret < 0);
1111                 rcu_assign_pointer(root->node, cow);
1112
1113                 btrfs_free_tree_block(trans, root, buf, parent_start,
1114                                       last_ref);
1115                 free_extent_buffer(buf);
1116                 add_root_to_dirty_list(root);
1117         } else {
1118                 WARN_ON(trans->transid != btrfs_header_generation(parent));
1119                 tree_mod_log_insert_key(parent, parent_slot,
1120                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
1121                 btrfs_set_node_blockptr(parent, parent_slot,
1122                                         cow->start);
1123                 btrfs_set_node_ptr_generation(parent, parent_slot,
1124                                               trans->transid);
1125                 btrfs_mark_buffer_dirty(parent);
1126                 if (last_ref) {
1127                         ret = tree_mod_log_free_eb(buf);
1128                         if (ret) {
1129                                 btrfs_abort_transaction(trans, ret);
1130                                 return ret;
1131                         }
1132                 }
1133                 btrfs_free_tree_block(trans, root, buf, parent_start,
1134                                       last_ref);
1135         }
1136         if (unlock_orig)
1137                 btrfs_tree_unlock(buf);
1138         free_extent_buffer_stale(buf);
1139         btrfs_mark_buffer_dirty(cow);
1140         *cow_ret = cow;
1141         return 0;
1142 }
1143
1144 /*
1145  * returns the logical address of the oldest predecessor of the given root.
1146  * entries older than time_seq are ignored.
1147  */
1148 static struct tree_mod_elem *__tree_mod_log_oldest_root(
1149                 struct extent_buffer *eb_root, u64 time_seq)
1150 {
1151         struct tree_mod_elem *tm;
1152         struct tree_mod_elem *found = NULL;
1153         u64 root_logical = eb_root->start;
1154         int looped = 0;
1155
1156         if (!time_seq)
1157                 return NULL;
1158
1159         /*
1160          * the very last operation that's logged for a root is the
1161          * replacement operation (if it is replaced at all). this has
1162          * the logical address of the *new* root, making it the very
1163          * first operation that's logged for this root.
1164          */
1165         while (1) {
1166                 tm = tree_mod_log_search_oldest(eb_root->fs_info, root_logical,
1167                                                 time_seq);
1168                 if (!looped && !tm)
1169                         return NULL;
1170                 /*
1171                  * if there are no tree operation for the oldest root, we simply
1172                  * return it. this should only happen if that (old) root is at
1173                  * level 0.
1174                  */
1175                 if (!tm)
1176                         break;
1177
1178                 /*
1179                  * if there's an operation that's not a root replacement, we
1180                  * found the oldest version of our root. normally, we'll find a
1181                  * MOD_LOG_KEY_REMOVE_WHILE_FREEING operation here.
1182                  */
1183                 if (tm->op != MOD_LOG_ROOT_REPLACE)
1184                         break;
1185
1186                 found = tm;
1187                 root_logical = tm->old_root.logical;
1188                 looped = 1;
1189         }
1190
1191         /* if there's no old root to return, return what we found instead */
1192         if (!found)
1193                 found = tm;
1194
1195         return found;
1196 }
1197
1198 /*
1199  * tm is a pointer to the first operation to rewind within eb. then, all
1200  * previous operations will be rewound (until we reach something older than
1201  * time_seq).
1202  */
1203 static void
1204 __tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct extent_buffer *eb,
1205                       u64 time_seq, struct tree_mod_elem *first_tm)
1206 {
1207         u32 n;
1208         struct rb_node *next;
1209         struct tree_mod_elem *tm = first_tm;
1210         unsigned long o_dst;
1211         unsigned long o_src;
1212         unsigned long p_size = sizeof(struct btrfs_key_ptr);
1213
1214         n = btrfs_header_nritems(eb);
1215         read_lock(&fs_info->tree_mod_log_lock);
1216         while (tm && tm->seq >= time_seq) {
1217                 /*
1218                  * all the operations are recorded with the operator used for
1219                  * the modification. as we're going backwards, we do the
1220                  * opposite of each operation here.
1221                  */
1222                 switch (tm->op) {
1223                 case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
1224                         BUG_ON(tm->slot < n);
1225                         /* Fallthrough */
1226                 case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
1227                 case MOD_LOG_KEY_REMOVE:
1228                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1229                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1230                         btrfs_set_node_ptr_generation(eb, tm->slot,
1231                                                       tm->generation);
1232                         n++;
1233                         break;
1234                 case MOD_LOG_KEY_REPLACE:
1235                         BUG_ON(tm->slot >= n);
1236                         btrfs_set_node_key(eb, &tm->key, tm->slot);
1237                         btrfs_set_node_blockptr(eb, tm->slot, tm->blockptr);
1238                         btrfs_set_node_ptr_generation(eb, tm->slot,
1239                                                       tm->generation);
1240                         break;
1241                 case MOD_LOG_KEY_ADD:
1242                         /* if a move operation is needed it's in the log */
1243                         n--;
1244                         break;
1245                 case MOD_LOG_MOVE_KEYS:
1246                         o_dst = btrfs_node_key_ptr_offset(tm->slot);
1247                         o_src = btrfs_node_key_ptr_offset(tm->move.dst_slot);
1248                         memmove_extent_buffer(eb, o_dst, o_src,
1249                                               tm->move.nr_items * p_size);
1250                         break;
1251                 case MOD_LOG_ROOT_REPLACE:
1252                         /*
1253                          * this operation is special. for roots, this must be
1254                          * handled explicitly before rewinding.
1255                          * for non-roots, this operation may exist if the node
1256                          * was a root: root A -> child B; then A gets empty and
1257                          * B is promoted to the new root. in the mod log, we'll
1258                          * have a root-replace operation for B, a tree block
1259                          * that is no root. we simply ignore that operation.
1260                          */
1261                         break;
1262                 }
1263                 next = rb_next(&tm->node);
1264                 if (!next)
1265                         break;
1266                 tm = rb_entry(next, struct tree_mod_elem, node);
1267                 if (tm->logical != first_tm->logical)
1268                         break;
1269         }
1270         read_unlock(&fs_info->tree_mod_log_lock);
1271         btrfs_set_header_nritems(eb, n);
1272 }
1273
1274 /*
1275  * Called with eb read locked. If the buffer cannot be rewound, the same buffer
1276  * is returned. If rewind operations happen, a fresh buffer is returned. The
1277  * returned buffer is always read-locked. If the returned buffer is not the
1278  * input buffer, the lock on the input buffer is released and the input buffer
1279  * is freed (its refcount is decremented).
1280  */
1281 static struct extent_buffer *
1282 tree_mod_log_rewind(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
1283                     struct extent_buffer *eb, u64 time_seq)
1284 {
1285         struct extent_buffer *eb_rewin;
1286         struct tree_mod_elem *tm;
1287
1288         if (!time_seq)
1289                 return eb;
1290
1291         if (btrfs_header_level(eb) == 0)
1292                 return eb;
1293
1294         tm = tree_mod_log_search(fs_info, eb->start, time_seq);
1295         if (!tm)
1296                 return eb;
1297
1298         btrfs_set_path_blocking(path);
1299         btrfs_set_lock_blocking_read(eb);
1300
1301         if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1302                 BUG_ON(tm->slot != 0);
1303                 eb_rewin = alloc_dummy_extent_buffer(fs_info, eb->start);
1304                 if (!eb_rewin) {
1305                         btrfs_tree_read_unlock_blocking(eb);
1306                         free_extent_buffer(eb);
1307                         return NULL;
1308                 }
1309                 btrfs_set_header_bytenr(eb_rewin, eb->start);
1310                 btrfs_set_header_backref_rev(eb_rewin,
1311                                              btrfs_header_backref_rev(eb));
1312                 btrfs_set_header_owner(eb_rewin, btrfs_header_owner(eb));
1313                 btrfs_set_header_level(eb_rewin, btrfs_header_level(eb));
1314         } else {
1315                 eb_rewin = btrfs_clone_extent_buffer(eb);
1316                 if (!eb_rewin) {
1317                         btrfs_tree_read_unlock_blocking(eb);
1318                         free_extent_buffer(eb);
1319                         return NULL;
1320                 }
1321         }
1322
1323         btrfs_tree_read_unlock_blocking(eb);
1324         free_extent_buffer(eb);
1325
1326         btrfs_tree_read_lock(eb_rewin);
1327         __tree_mod_log_rewind(fs_info, eb_rewin, time_seq, tm);
1328         WARN_ON(btrfs_header_nritems(eb_rewin) >
1329                 BTRFS_NODEPTRS_PER_BLOCK(fs_info));
1330
1331         return eb_rewin;
1332 }
1333
1334 /*
1335  * get_old_root() rewinds the state of @root's root node to the given @time_seq
1336  * value. If there are no changes, the current root->root_node is returned. If
1337  * anything changed in between, there's a fresh buffer allocated on which the
1338  * rewind operations are done. In any case, the returned buffer is read locked.
1339  * Returns NULL on error (with no locks held).
1340  */
1341 static inline struct extent_buffer *
1342 get_old_root(struct btrfs_root *root, u64 time_seq)
1343 {
1344         struct btrfs_fs_info *fs_info = root->fs_info;
1345         struct tree_mod_elem *tm;
1346         struct extent_buffer *eb = NULL;
1347         struct extent_buffer *eb_root;
1348         struct extent_buffer *old;
1349         struct tree_mod_root *old_root = NULL;
1350         u64 old_generation = 0;
1351         u64 logical;
1352         int level;
1353
1354         eb_root = btrfs_read_lock_root_node(root);
1355         tm = __tree_mod_log_oldest_root(eb_root, time_seq);
1356         if (!tm)
1357                 return eb_root;
1358
1359         if (tm->op == MOD_LOG_ROOT_REPLACE) {
1360                 old_root = &tm->old_root;
1361                 old_generation = tm->generation;
1362                 logical = old_root->logical;
1363                 level = old_root->level;
1364         } else {
1365                 logical = eb_root->start;
1366                 level = btrfs_header_level(eb_root);
1367         }
1368
1369         tm = tree_mod_log_search(fs_info, logical, time_seq);
1370         if (old_root && tm && tm->op != MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1371                 btrfs_tree_read_unlock(eb_root);
1372                 free_extent_buffer(eb_root);
1373                 old = read_tree_block(fs_info, logical, 0, level, NULL);
1374                 if (WARN_ON(IS_ERR(old) || !extent_buffer_uptodate(old))) {
1375                         if (!IS_ERR(old))
1376                                 free_extent_buffer(old);
1377                         btrfs_warn(fs_info,
1378                                    "failed to read tree block %llu from get_old_root",
1379                                    logical);
1380                 } else {
1381                         eb = btrfs_clone_extent_buffer(old);
1382                         free_extent_buffer(old);
1383                 }
1384         } else if (old_root) {
1385                 btrfs_tree_read_unlock(eb_root);
1386                 free_extent_buffer(eb_root);
1387                 eb = alloc_dummy_extent_buffer(fs_info, logical);
1388         } else {
1389                 btrfs_set_lock_blocking_read(eb_root);
1390                 eb = btrfs_clone_extent_buffer(eb_root);
1391                 btrfs_tree_read_unlock_blocking(eb_root);
1392                 free_extent_buffer(eb_root);
1393         }
1394
1395         if (!eb)
1396                 return NULL;
1397         btrfs_tree_read_lock(eb);
1398         if (old_root) {
1399                 btrfs_set_header_bytenr(eb, eb->start);
1400                 btrfs_set_header_backref_rev(eb, BTRFS_MIXED_BACKREF_REV);
1401                 btrfs_set_header_owner(eb, btrfs_header_owner(eb_root));
1402                 btrfs_set_header_level(eb, old_root->level);
1403                 btrfs_set_header_generation(eb, old_generation);
1404         }
1405         if (tm)
1406                 __tree_mod_log_rewind(fs_info, eb, time_seq, tm);
1407         else
1408                 WARN_ON(btrfs_header_level(eb) != 0);
1409         WARN_ON(btrfs_header_nritems(eb) > BTRFS_NODEPTRS_PER_BLOCK(fs_info));
1410
1411         return eb;
1412 }
1413
1414 int btrfs_old_root_level(struct btrfs_root *root, u64 time_seq)
1415 {
1416         struct tree_mod_elem *tm;
1417         int level;
1418         struct extent_buffer *eb_root = btrfs_root_node(root);
1419
1420         tm = __tree_mod_log_oldest_root(eb_root, time_seq);
1421         if (tm && tm->op == MOD_LOG_ROOT_REPLACE) {
1422                 level = tm->old_root.level;
1423         } else {
1424                 level = btrfs_header_level(eb_root);
1425         }
1426         free_extent_buffer(eb_root);
1427
1428         return level;
1429 }
1430
1431 static inline int should_cow_block(struct btrfs_trans_handle *trans,
1432                                    struct btrfs_root *root,
1433                                    struct extent_buffer *buf)
1434 {
1435         if (btrfs_is_testing(root->fs_info))
1436                 return 0;
1437
1438         /* Ensure we can see the FORCE_COW bit */
1439         smp_mb__before_atomic();
1440
1441         /*
1442          * We do not need to cow a block if
1443          * 1) this block is not created or changed in this transaction;
1444          * 2) this block does not belong to TREE_RELOC tree;
1445          * 3) the root is not forced COW.
1446          *
1447          * What is forced COW:
1448          *    when we create snapshot during committing the transaction,
1449          *    after we've finished copying src root, we must COW the shared
1450          *    block to ensure the metadata consistency.
1451          */
1452         if (btrfs_header_generation(buf) == trans->transid &&
1453             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
1454             !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
1455               btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)) &&
1456             !test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
1457                 return 0;
1458         return 1;
1459 }
1460
1461 /*
1462  * cows a single block, see __btrfs_cow_block for the real work.
1463  * This version of it has extra checks so that a block isn't COWed more than
1464  * once per transaction, as long as it hasn't been written yet
1465  */
1466 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
1467                     struct btrfs_root *root, struct extent_buffer *buf,
1468                     struct extent_buffer *parent, int parent_slot,
1469                     struct extent_buffer **cow_ret)
1470 {
1471         struct btrfs_fs_info *fs_info = root->fs_info;
1472         u64 search_start;
1473         int ret;
1474
1475         if (test_bit(BTRFS_ROOT_DELETING, &root->state))
1476                 btrfs_err(fs_info,
1477                         "COW'ing blocks on a fs root that's being dropped");
1478
1479         if (trans->transaction != fs_info->running_transaction)
1480                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1481                        trans->transid,
1482                        fs_info->running_transaction->transid);
1483
1484         if (trans->transid != fs_info->generation)
1485                 WARN(1, KERN_CRIT "trans %llu running %llu\n",
1486                        trans->transid, fs_info->generation);
1487
1488         if (!should_cow_block(trans, root, buf)) {
1489                 trans->dirty = true;
1490                 *cow_ret = buf;
1491                 return 0;
1492         }
1493
1494         search_start = buf->start & ~((u64)SZ_1G - 1);
1495
1496         if (parent)
1497                 btrfs_set_lock_blocking_write(parent);
1498         btrfs_set_lock_blocking_write(buf);
1499
1500         /*
1501          * Before CoWing this block for later modification, check if it's
1502          * the subtree root and do the delayed subtree trace if needed.
1503          *
1504          * Also We don't care about the error, as it's handled internally.
1505          */
1506         btrfs_qgroup_trace_subtree_after_cow(trans, root, buf);
1507         ret = __btrfs_cow_block(trans, root, buf, parent,
1508                                  parent_slot, cow_ret, search_start, 0);
1509
1510         trace_btrfs_cow_block(root, buf, *cow_ret);
1511
1512         return ret;
1513 }
1514
1515 /*
1516  * helper function for defrag to decide if two blocks pointed to by a
1517  * node are actually close by
1518  */
1519 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
1520 {
1521         if (blocknr < other && other - (blocknr + blocksize) < 32768)
1522                 return 1;
1523         if (blocknr > other && blocknr - (other + blocksize) < 32768)
1524                 return 1;
1525         return 0;
1526 }
1527
1528 /*
1529  * compare two keys in a memcmp fashion
1530  */
1531 static int comp_keys(const struct btrfs_disk_key *disk,
1532                      const struct btrfs_key *k2)
1533 {
1534         struct btrfs_key k1;
1535
1536         btrfs_disk_key_to_cpu(&k1, disk);
1537
1538         return btrfs_comp_cpu_keys(&k1, k2);
1539 }
1540
1541 /*
1542  * same as comp_keys only with two btrfs_key's
1543  */
1544 int btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
1545 {
1546         if (k1->objectid > k2->objectid)
1547                 return 1;
1548         if (k1->objectid < k2->objectid)
1549                 return -1;
1550         if (k1->type > k2->type)
1551                 return 1;
1552         if (k1->type < k2->type)
1553                 return -1;
1554         if (k1->offset > k2->offset)
1555                 return 1;
1556         if (k1->offset < k2->offset)
1557                 return -1;
1558         return 0;
1559 }
1560
1561 /*
1562  * this is used by the defrag code to go through all the
1563  * leaves pointed to by a node and reallocate them so that
1564  * disk order is close to key order
1565  */
1566 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
1567                        struct btrfs_root *root, struct extent_buffer *parent,
1568                        int start_slot, u64 *last_ret,
1569                        struct btrfs_key *progress)
1570 {
1571         struct btrfs_fs_info *fs_info = root->fs_info;
1572         struct extent_buffer *cur;
1573         u64 blocknr;
1574         u64 gen;
1575         u64 search_start = *last_ret;
1576         u64 last_block = 0;
1577         u64 other;
1578         u32 parent_nritems;
1579         int end_slot;
1580         int i;
1581         int err = 0;
1582         int parent_level;
1583         int uptodate;
1584         u32 blocksize;
1585         int progress_passed = 0;
1586         struct btrfs_disk_key disk_key;
1587
1588         parent_level = btrfs_header_level(parent);
1589
1590         WARN_ON(trans->transaction != fs_info->running_transaction);
1591         WARN_ON(trans->transid != fs_info->generation);
1592
1593         parent_nritems = btrfs_header_nritems(parent);
1594         blocksize = fs_info->nodesize;
1595         end_slot = parent_nritems - 1;
1596
1597         if (parent_nritems <= 1)
1598                 return 0;
1599
1600         btrfs_set_lock_blocking_write(parent);
1601
1602         for (i = start_slot; i <= end_slot; i++) {
1603                 struct btrfs_key first_key;
1604                 int close = 1;
1605
1606                 btrfs_node_key(parent, &disk_key, i);
1607                 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
1608                         continue;
1609
1610                 progress_passed = 1;
1611                 blocknr = btrfs_node_blockptr(parent, i);
1612                 gen = btrfs_node_ptr_generation(parent, i);
1613                 btrfs_node_key_to_cpu(parent, &first_key, i);
1614                 if (last_block == 0)
1615                         last_block = blocknr;
1616
1617                 if (i > 0) {
1618                         other = btrfs_node_blockptr(parent, i - 1);
1619                         close = close_blocks(blocknr, other, blocksize);
1620                 }
1621                 if (!close && i < end_slot) {
1622                         other = btrfs_node_blockptr(parent, i + 1);
1623                         close = close_blocks(blocknr, other, blocksize);
1624                 }
1625                 if (close) {
1626                         last_block = blocknr;
1627                         continue;
1628                 }
1629
1630                 cur = find_extent_buffer(fs_info, blocknr);
1631                 if (cur)
1632                         uptodate = btrfs_buffer_uptodate(cur, gen, 0);
1633                 else
1634                         uptodate = 0;
1635                 if (!cur || !uptodate) {
1636                         if (!cur) {
1637                                 cur = read_tree_block(fs_info, blocknr, gen,
1638                                                       parent_level - 1,
1639                                                       &first_key);
1640                                 if (IS_ERR(cur)) {
1641                                         return PTR_ERR(cur);
1642                                 } else if (!extent_buffer_uptodate(cur)) {
1643                                         free_extent_buffer(cur);
1644                                         return -EIO;
1645                                 }
1646                         } else if (!uptodate) {
1647                                 err = btrfs_read_buffer(cur, gen,
1648                                                 parent_level - 1,&first_key);
1649                                 if (err) {
1650                                         free_extent_buffer(cur);
1651                                         return err;
1652                                 }
1653                         }
1654                 }
1655                 if (search_start == 0)
1656                         search_start = last_block;
1657
1658                 btrfs_tree_lock(cur);
1659                 btrfs_set_lock_blocking_write(cur);
1660                 err = __btrfs_cow_block(trans, root, cur, parent, i,
1661                                         &cur, search_start,
1662                                         min(16 * blocksize,
1663                                             (end_slot - i) * blocksize));
1664                 if (err) {
1665                         btrfs_tree_unlock(cur);
1666                         free_extent_buffer(cur);
1667                         break;
1668                 }
1669                 search_start = cur->start;
1670                 last_block = cur->start;
1671                 *last_ret = search_start;
1672                 btrfs_tree_unlock(cur);
1673                 free_extent_buffer(cur);
1674         }
1675         return err;
1676 }
1677
1678 /*
1679  * search for key in the extent_buffer.  The items start at offset p,
1680  * and they are item_size apart.  There are 'max' items in p.
1681  *
1682  * the slot in the array is returned via slot, and it points to
1683  * the place where you would insert key if it is not found in
1684  * the array.
1685  *
1686  * slot may point to max if the key is bigger than all of the keys
1687  */
1688 static noinline int generic_bin_search(struct extent_buffer *eb,
1689                                        unsigned long p, int item_size,
1690                                        const struct btrfs_key *key,
1691                                        int max, int *slot)
1692 {
1693         int low = 0;
1694         int high = max;
1695         int mid;
1696         int ret;
1697         struct btrfs_disk_key *tmp = NULL;
1698         struct btrfs_disk_key unaligned;
1699         unsigned long offset;
1700         char *kaddr = NULL;
1701         unsigned long map_start = 0;
1702         unsigned long map_len = 0;
1703         int err;
1704
1705         if (low > high) {
1706                 btrfs_err(eb->fs_info,
1707                  "%s: low (%d) > high (%d) eb %llu owner %llu level %d",
1708                           __func__, low, high, eb->start,
1709                           btrfs_header_owner(eb), btrfs_header_level(eb));
1710                 return -EINVAL;
1711         }
1712
1713         while (low < high) {
1714                 mid = (low + high) / 2;
1715                 offset = p + mid * item_size;
1716
1717                 if (!kaddr || offset < map_start ||
1718                     (offset + sizeof(struct btrfs_disk_key)) >
1719                     map_start + map_len) {
1720
1721                         err = map_private_extent_buffer(eb, offset,
1722                                                 sizeof(struct btrfs_disk_key),
1723                                                 &kaddr, &map_start, &map_len);
1724
1725                         if (!err) {
1726                                 tmp = (struct btrfs_disk_key *)(kaddr + offset -
1727                                                         map_start);
1728                         } else if (err == 1) {
1729                                 read_extent_buffer(eb, &unaligned,
1730                                                    offset, sizeof(unaligned));
1731                                 tmp = &unaligned;
1732                         } else {
1733                                 return err;
1734                         }
1735
1736                 } else {
1737                         tmp = (struct btrfs_disk_key *)(kaddr + offset -
1738                                                         map_start);
1739                 }
1740                 ret = comp_keys(tmp, key);
1741
1742                 if (ret < 0)
1743                         low = mid + 1;
1744                 else if (ret > 0)
1745                         high = mid;
1746                 else {
1747                         *slot = mid;
1748                         return 0;
1749                 }
1750         }
1751         *slot = low;
1752         return 1;
1753 }
1754
1755 /*
1756  * simple bin_search frontend that does the right thing for
1757  * leaves vs nodes
1758  */
1759 int btrfs_bin_search(struct extent_buffer *eb, const struct btrfs_key *key,
1760                      int level, int *slot)
1761 {
1762         if (level == 0)
1763                 return generic_bin_search(eb,
1764                                           offsetof(struct btrfs_leaf, items),
1765                                           sizeof(struct btrfs_item),
1766                                           key, btrfs_header_nritems(eb),
1767                                           slot);
1768         else
1769                 return generic_bin_search(eb,
1770                                           offsetof(struct btrfs_node, ptrs),
1771                                           sizeof(struct btrfs_key_ptr),
1772                                           key, btrfs_header_nritems(eb),
1773                                           slot);
1774 }
1775
1776 static void root_add_used(struct btrfs_root *root, u32 size)
1777 {
1778         spin_lock(&root->accounting_lock);
1779         btrfs_set_root_used(&root->root_item,
1780                             btrfs_root_used(&root->root_item) + size);
1781         spin_unlock(&root->accounting_lock);
1782 }
1783
1784 static void root_sub_used(struct btrfs_root *root, u32 size)
1785 {
1786         spin_lock(&root->accounting_lock);
1787         btrfs_set_root_used(&root->root_item,
1788                             btrfs_root_used(&root->root_item) - size);
1789         spin_unlock(&root->accounting_lock);
1790 }
1791
1792 /* given a node and slot number, this reads the blocks it points to.  The
1793  * extent buffer is returned with a reference taken (but unlocked).
1794  */
1795 static noinline struct extent_buffer *
1796 read_node_slot(struct btrfs_fs_info *fs_info, struct extent_buffer *parent,
1797                int slot)
1798 {
1799         int level = btrfs_header_level(parent);
1800         struct extent_buffer *eb;
1801         struct btrfs_key first_key;
1802
1803         if (slot < 0 || slot >= btrfs_header_nritems(parent))
1804                 return ERR_PTR(-ENOENT);
1805
1806         BUG_ON(level == 0);
1807
1808         btrfs_node_key_to_cpu(parent, &first_key, slot);
1809         eb = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot),
1810                              btrfs_node_ptr_generation(parent, slot),
1811                              level - 1, &first_key);
1812         if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) {
1813                 free_extent_buffer(eb);
1814                 eb = ERR_PTR(-EIO);
1815         }
1816
1817         return eb;
1818 }
1819
1820 /*
1821  * node level balancing, used to make sure nodes are in proper order for
1822  * item deletion.  We balance from the top down, so we have to make sure
1823  * that a deletion won't leave an node completely empty later on.
1824  */
1825 static noinline int balance_level(struct btrfs_trans_handle *trans,
1826                          struct btrfs_root *root,
1827                          struct btrfs_path *path, int level)
1828 {
1829         struct btrfs_fs_info *fs_info = root->fs_info;
1830         struct extent_buffer *right = NULL;
1831         struct extent_buffer *mid;
1832         struct extent_buffer *left = NULL;
1833         struct extent_buffer *parent = NULL;
1834         int ret = 0;
1835         int wret;
1836         int pslot;
1837         int orig_slot = path->slots[level];
1838         u64 orig_ptr;
1839
1840         ASSERT(level > 0);
1841
1842         mid = path->nodes[level];
1843
1844         WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK &&
1845                 path->locks[level] != BTRFS_WRITE_LOCK_BLOCKING);
1846         WARN_ON(btrfs_header_generation(mid) != trans->transid);
1847
1848         orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1849
1850         if (level < BTRFS_MAX_LEVEL - 1) {
1851                 parent = path->nodes[level + 1];
1852                 pslot = path->slots[level + 1];
1853         }
1854
1855         /*
1856          * deal with the case where there is only one pointer in the root
1857          * by promoting the node below to a root
1858          */
1859         if (!parent) {
1860                 struct extent_buffer *child;
1861
1862                 if (btrfs_header_nritems(mid) != 1)
1863                         return 0;
1864
1865                 /* promote the child to a root */
1866                 child = read_node_slot(fs_info, mid, 0);
1867                 if (IS_ERR(child)) {
1868                         ret = PTR_ERR(child);
1869                         btrfs_handle_fs_error(fs_info, ret, NULL);
1870                         goto enospc;
1871                 }
1872
1873                 btrfs_tree_lock(child);
1874                 btrfs_set_lock_blocking_write(child);
1875                 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
1876                 if (ret) {
1877                         btrfs_tree_unlock(child);
1878                         free_extent_buffer(child);
1879                         goto enospc;
1880                 }
1881
1882                 ret = tree_mod_log_insert_root(root->node, child, 1);
1883                 BUG_ON(ret < 0);
1884                 rcu_assign_pointer(root->node, child);
1885
1886                 add_root_to_dirty_list(root);
1887                 btrfs_tree_unlock(child);
1888
1889                 path->locks[level] = 0;
1890                 path->nodes[level] = NULL;
1891                 clean_tree_block(fs_info, mid);
1892                 btrfs_tree_unlock(mid);
1893                 /* once for the path */
1894                 free_extent_buffer(mid);
1895
1896                 root_sub_used(root, mid->len);
1897                 btrfs_free_tree_block(trans, root, mid, 0, 1);
1898                 /* once for the root ptr */
1899                 free_extent_buffer_stale(mid);
1900                 return 0;
1901         }
1902         if (btrfs_header_nritems(mid) >
1903             BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
1904                 return 0;
1905
1906         left = read_node_slot(fs_info, parent, pslot - 1);
1907         if (IS_ERR(left))
1908                 left = NULL;
1909
1910         if (left) {
1911                 btrfs_tree_lock(left);
1912                 btrfs_set_lock_blocking_write(left);
1913                 wret = btrfs_cow_block(trans, root, left,
1914                                        parent, pslot - 1, &left);
1915                 if (wret) {
1916                         ret = wret;
1917                         goto enospc;
1918                 }
1919         }
1920
1921         right = read_node_slot(fs_info, parent, pslot + 1);
1922         if (IS_ERR(right))
1923                 right = NULL;
1924
1925         if (right) {
1926                 btrfs_tree_lock(right);
1927                 btrfs_set_lock_blocking_write(right);
1928                 wret = btrfs_cow_block(trans, root, right,
1929                                        parent, pslot + 1, &right);
1930                 if (wret) {
1931                         ret = wret;
1932                         goto enospc;
1933                 }
1934         }
1935
1936         /* first, try to make some room in the middle buffer */
1937         if (left) {
1938                 orig_slot += btrfs_header_nritems(left);
1939                 wret = push_node_left(trans, fs_info, left, mid, 1);
1940                 if (wret < 0)
1941                         ret = wret;
1942         }
1943
1944         /*
1945          * then try to empty the right most buffer into the middle
1946          */
1947         if (right) {
1948                 wret = push_node_left(trans, fs_info, mid, right, 1);
1949                 if (wret < 0 && wret != -ENOSPC)
1950                         ret = wret;
1951                 if (btrfs_header_nritems(right) == 0) {
1952                         clean_tree_block(fs_info, right);
1953                         btrfs_tree_unlock(right);
1954                         del_ptr(root, path, level + 1, pslot + 1);
1955                         root_sub_used(root, right->len);
1956                         btrfs_free_tree_block(trans, root, right, 0, 1);
1957                         free_extent_buffer_stale(right);
1958                         right = NULL;
1959                 } else {
1960                         struct btrfs_disk_key right_key;
1961                         btrfs_node_key(right, &right_key, 0);
1962                         ret = tree_mod_log_insert_key(parent, pslot + 1,
1963                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
1964                         BUG_ON(ret < 0);
1965                         btrfs_set_node_key(parent, &right_key, pslot + 1);
1966                         btrfs_mark_buffer_dirty(parent);
1967                 }
1968         }
1969         if (btrfs_header_nritems(mid) == 1) {
1970                 /*
1971                  * we're not allowed to leave a node with one item in the
1972                  * tree during a delete.  A deletion from lower in the tree
1973                  * could try to delete the only pointer in this node.
1974                  * So, pull some keys from the left.
1975                  * There has to be a left pointer at this point because
1976                  * otherwise we would have pulled some pointers from the
1977                  * right
1978                  */
1979                 if (!left) {
1980                         ret = -EROFS;
1981                         btrfs_handle_fs_error(fs_info, ret, NULL);
1982                         goto enospc;
1983                 }
1984                 wret = balance_node_right(trans, fs_info, mid, left);
1985                 if (wret < 0) {
1986                         ret = wret;
1987                         goto enospc;
1988                 }
1989                 if (wret == 1) {
1990                         wret = push_node_left(trans, fs_info, left, mid, 1);
1991                         if (wret < 0)
1992                                 ret = wret;
1993                 }
1994                 BUG_ON(wret == 1);
1995         }
1996         if (btrfs_header_nritems(mid) == 0) {
1997                 clean_tree_block(fs_info, mid);
1998                 btrfs_tree_unlock(mid);
1999                 del_ptr(root, path, level + 1, pslot);
2000                 root_sub_used(root, mid->len);
2001                 btrfs_free_tree_block(trans, root, mid, 0, 1);
2002                 free_extent_buffer_stale(mid);
2003                 mid = NULL;
2004         } else {
2005                 /* update the parent key to reflect our changes */
2006                 struct btrfs_disk_key mid_key;
2007                 btrfs_node_key(mid, &mid_key, 0);
2008                 ret = tree_mod_log_insert_key(parent, pslot,
2009                                 MOD_LOG_KEY_REPLACE, GFP_NOFS);
2010                 BUG_ON(ret < 0);
2011                 btrfs_set_node_key(parent, &mid_key, pslot);
2012                 btrfs_mark_buffer_dirty(parent);
2013         }
2014
2015         /* update the path */
2016         if (left) {
2017                 if (btrfs_header_nritems(left) > orig_slot) {
2018                         extent_buffer_get(left);
2019                         /* left was locked after cow */
2020                         path->nodes[level] = left;
2021                         path->slots[level + 1] -= 1;
2022                         path->slots[level] = orig_slot;
2023                         if (mid) {
2024                                 btrfs_tree_unlock(mid);
2025                                 free_extent_buffer(mid);
2026                         }
2027                 } else {
2028                         orig_slot -= btrfs_header_nritems(left);
2029                         path->slots[level] = orig_slot;
2030                 }
2031         }
2032         /* double check we haven't messed things up */
2033         if (orig_ptr !=
2034             btrfs_node_blockptr(path->nodes[level], path->slots[level]))
2035                 BUG();
2036 enospc:
2037         if (right) {
2038                 btrfs_tree_unlock(right);
2039                 free_extent_buffer(right);
2040         }
2041         if (left) {
2042                 if (path->nodes[level] != left)
2043                         btrfs_tree_unlock(left);
2044                 free_extent_buffer(left);
2045         }
2046         return ret;
2047 }
2048
2049 /* Node balancing for insertion.  Here we only split or push nodes around
2050  * when they are completely full.  This is also done top down, so we
2051  * have to be pessimistic.
2052  */
2053 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
2054                                           struct btrfs_root *root,
2055                                           struct btrfs_path *path, int level)
2056 {
2057         struct btrfs_fs_info *fs_info = root->fs_info;
2058         struct extent_buffer *right = NULL;
2059         struct extent_buffer *mid;
2060         struct extent_buffer *left = NULL;
2061         struct extent_buffer *parent = NULL;
2062         int ret = 0;
2063         int wret;
2064         int pslot;
2065         int orig_slot = path->slots[level];
2066
2067         if (level == 0)
2068                 return 1;
2069
2070         mid = path->nodes[level];
2071         WARN_ON(btrfs_header_generation(mid) != trans->transid);
2072
2073         if (level < BTRFS_MAX_LEVEL - 1) {
2074                 parent = path->nodes[level + 1];
2075                 pslot = path->slots[level + 1];
2076         }
2077
2078         if (!parent)
2079                 return 1;
2080
2081         left = read_node_slot(fs_info, parent, pslot - 1);
2082         if (IS_ERR(left))
2083                 left = NULL;
2084
2085         /* first, try to make some room in the middle buffer */
2086         if (left) {
2087                 u32 left_nr;
2088
2089                 btrfs_tree_lock(left);
2090                 btrfs_set_lock_blocking_write(left);
2091
2092                 left_nr = btrfs_header_nritems(left);
2093                 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
2094                         wret = 1;
2095                 } else {
2096                         ret = btrfs_cow_block(trans, root, left, parent,
2097                                               pslot - 1, &left);
2098                         if (ret)
2099                                 wret = 1;
2100                         else {
2101                                 wret = push_node_left(trans, fs_info,
2102                                                       left, mid, 0);
2103                         }
2104                 }
2105                 if (wret < 0)
2106                         ret = wret;
2107                 if (wret == 0) {
2108                         struct btrfs_disk_key disk_key;
2109                         orig_slot += left_nr;
2110                         btrfs_node_key(mid, &disk_key, 0);
2111                         ret = tree_mod_log_insert_key(parent, pslot,
2112                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
2113                         BUG_ON(ret < 0);
2114                         btrfs_set_node_key(parent, &disk_key, pslot);
2115                         btrfs_mark_buffer_dirty(parent);
2116                         if (btrfs_header_nritems(left) > orig_slot) {
2117                                 path->nodes[level] = left;
2118                                 path->slots[level + 1] -= 1;
2119                                 path->slots[level] = orig_slot;
2120                                 btrfs_tree_unlock(mid);
2121                                 free_extent_buffer(mid);
2122                         } else {
2123                                 orig_slot -=
2124                                         btrfs_header_nritems(left);
2125                                 path->slots[level] = orig_slot;
2126                                 btrfs_tree_unlock(left);
2127                                 free_extent_buffer(left);
2128                         }
2129                         return 0;
2130                 }
2131                 btrfs_tree_unlock(left);
2132                 free_extent_buffer(left);
2133         }
2134         right = read_node_slot(fs_info, parent, pslot + 1);
2135         if (IS_ERR(right))
2136                 right = NULL;
2137
2138         /*
2139          * then try to empty the right most buffer into the middle
2140          */
2141         if (right) {
2142                 u32 right_nr;
2143
2144                 btrfs_tree_lock(right);
2145                 btrfs_set_lock_blocking_write(right);
2146
2147                 right_nr = btrfs_header_nritems(right);
2148                 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
2149                         wret = 1;
2150                 } else {
2151                         ret = btrfs_cow_block(trans, root, right,
2152                                               parent, pslot + 1,
2153                                               &right);
2154                         if (ret)
2155                                 wret = 1;
2156                         else {
2157                                 wret = balance_node_right(trans, fs_info,
2158                                                           right, mid);
2159                         }
2160                 }
2161                 if (wret < 0)
2162                         ret = wret;
2163                 if (wret == 0) {
2164                         struct btrfs_disk_key disk_key;
2165
2166                         btrfs_node_key(right, &disk_key, 0);
2167                         ret = tree_mod_log_insert_key(parent, pslot + 1,
2168                                         MOD_LOG_KEY_REPLACE, GFP_NOFS);
2169                         BUG_ON(ret < 0);
2170                         btrfs_set_node_key(parent, &disk_key, pslot + 1);
2171                         btrfs_mark_buffer_dirty(parent);
2172
2173                         if (btrfs_header_nritems(mid) <= orig_slot) {
2174                                 path->nodes[level] = right;
2175                                 path->slots[level + 1] += 1;
2176                                 path->slots[level] = orig_slot -
2177                                         btrfs_header_nritems(mid);
2178                                 btrfs_tree_unlock(mid);
2179                                 free_extent_buffer(mid);
2180                         } else {
2181                                 btrfs_tree_unlock(right);
2182                                 free_extent_buffer(right);
2183                         }
2184                         return 0;
2185                 }
2186                 btrfs_tree_unlock(right);
2187                 free_extent_buffer(right);
2188         }
2189         return 1;
2190 }
2191
2192 /*
2193  * readahead one full node of leaves, finding things that are close
2194  * to the block in 'slot', and triggering ra on them.
2195  */
2196 static void reada_for_search(struct btrfs_fs_info *fs_info,
2197                              struct btrfs_path *path,
2198                              int level, int slot, u64 objectid)
2199 {
2200         struct extent_buffer *node;
2201         struct btrfs_disk_key disk_key;
2202         u32 nritems;
2203         u64 search;
2204         u64 target;
2205         u64 nread = 0;
2206         struct extent_buffer *eb;
2207         u32 nr;
2208         u32 blocksize;
2209         u32 nscan = 0;
2210
2211         if (level != 1)
2212                 return;
2213
2214         if (!path->nodes[level])
2215                 return;
2216
2217         node = path->nodes[level];
2218
2219         search = btrfs_node_blockptr(node, slot);
2220         blocksize = fs_info->nodesize;
2221         eb = find_extent_buffer(fs_info, search);
2222         if (eb) {
2223                 free_extent_buffer(eb);
2224                 return;
2225         }
2226
2227         target = search;
2228
2229         nritems = btrfs_header_nritems(node);
2230         nr = slot;
2231
2232         while (1) {
2233                 if (path->reada == READA_BACK) {
2234                         if (nr == 0)
2235                                 break;
2236                         nr--;
2237                 } else if (path->reada == READA_FORWARD) {
2238                         nr++;
2239                         if (nr >= nritems)
2240                                 break;
2241                 }
2242                 if (path->reada == READA_BACK && objectid) {
2243                         btrfs_node_key(node, &disk_key, nr);
2244                         if (btrfs_disk_key_objectid(&disk_key) != objectid)
2245                                 break;
2246                 }
2247                 search = btrfs_node_blockptr(node, nr);
2248                 if ((search <= target && target - search <= 65536) ||
2249                     (search > target && search - target <= 65536)) {
2250                         readahead_tree_block(fs_info, search);
2251                         nread += blocksize;
2252                 }
2253                 nscan++;
2254                 if ((nread > 65536 || nscan > 32))
2255                         break;
2256         }
2257 }
2258
2259 static noinline void reada_for_balance(struct btrfs_fs_info *fs_info,
2260                                        struct btrfs_path *path, int level)
2261 {
2262         int slot;
2263         int nritems;
2264         struct extent_buffer *parent;
2265         struct extent_buffer *eb;
2266         u64 gen;
2267         u64 block1 = 0;
2268         u64 block2 = 0;
2269
2270         parent = path->nodes[level + 1];
2271         if (!parent)
2272                 return;
2273
2274         nritems = btrfs_header_nritems(parent);
2275         slot = path->slots[level + 1];
2276
2277         if (slot > 0) {
2278                 block1 = btrfs_node_blockptr(parent, slot - 1);
2279                 gen = btrfs_node_ptr_generation(parent, slot - 1);
2280                 eb = find_extent_buffer(fs_info, block1);
2281                 /*
2282                  * if we get -eagain from btrfs_buffer_uptodate, we
2283                  * don't want to return eagain here.  That will loop
2284                  * forever
2285                  */
2286                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2287                         block1 = 0;
2288                 free_extent_buffer(eb);
2289         }
2290         if (slot + 1 < nritems) {
2291                 block2 = btrfs_node_blockptr(parent, slot + 1);
2292                 gen = btrfs_node_ptr_generation(parent, slot + 1);
2293                 eb = find_extent_buffer(fs_info, block2);
2294                 if (eb && btrfs_buffer_uptodate(eb, gen, 1) != 0)
2295                         block2 = 0;
2296                 free_extent_buffer(eb);
2297         }
2298
2299         if (block1)
2300                 readahead_tree_block(fs_info, block1);
2301         if (block2)
2302                 readahead_tree_block(fs_info, block2);
2303 }
2304
2305
2306 /*
2307  * when we walk down the tree, it is usually safe to unlock the higher layers
2308  * in the tree.  The exceptions are when our path goes through slot 0, because
2309  * operations on the tree might require changing key pointers higher up in the
2310  * tree.
2311  *
2312  * callers might also have set path->keep_locks, which tells this code to keep
2313  * the lock if the path points to the last slot in the block.  This is part of
2314  * walking through the tree, and selecting the next slot in the higher block.
2315  *
2316  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
2317  * if lowest_unlock is 1, level 0 won't be unlocked
2318  */
2319 static noinline void unlock_up(struct btrfs_path *path, int level,
2320                                int lowest_unlock, int min_write_lock_level,
2321                                int *write_lock_level)
2322 {
2323         int i;
2324         int skip_level = level;
2325         int no_skips = 0;
2326         struct extent_buffer *t;
2327
2328         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2329                 if (!path->nodes[i])
2330                         break;
2331                 if (!path->locks[i])
2332                         break;
2333                 if (!no_skips && path->slots[i] == 0) {
2334                         skip_level = i + 1;
2335                         continue;
2336                 }
2337                 if (!no_skips && path->keep_locks) {
2338                         u32 nritems;
2339                         t = path->nodes[i];
2340                         nritems = btrfs_header_nritems(t);
2341                         if (nritems < 1 || path->slots[i] >= nritems - 1) {
2342                                 skip_level = i + 1;
2343                                 continue;
2344                         }
2345                 }
2346                 if (skip_level < i && i >= lowest_unlock)
2347                         no_skips = 1;
2348
2349                 t = path->nodes[i];
2350                 if (i >= lowest_unlock && i > skip_level) {
2351                         btrfs_tree_unlock_rw(t, path->locks[i]);
2352                         path->locks[i] = 0;
2353                         if (write_lock_level &&
2354                             i > min_write_lock_level &&
2355                             i <= *write_lock_level) {
2356                                 *write_lock_level = i - 1;
2357                         }
2358                 }
2359         }
2360 }
2361
2362 /*
2363  * This releases any locks held in the path starting at level and
2364  * going all the way up to the root.
2365  *
2366  * btrfs_search_slot will keep the lock held on higher nodes in a few
2367  * corner cases, such as COW of the block at slot zero in the node.  This
2368  * ignores those rules, and it should only be called when there are no
2369  * more updates to be done higher up in the tree.
2370  */
2371 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
2372 {
2373         int i;
2374
2375         if (path->keep_locks)
2376                 return;
2377
2378         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2379                 if (!path->nodes[i])
2380                         continue;
2381                 if (!path->locks[i])
2382                         continue;
2383                 btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
2384                 path->locks[i] = 0;
2385         }
2386 }
2387
2388 /*
2389  * helper function for btrfs_search_slot.  The goal is to find a block
2390  * in cache without setting the path to blocking.  If we find the block
2391  * we return zero and the path is unchanged.
2392  *
2393  * If we can't find the block, we set the path blocking and do some
2394  * reada.  -EAGAIN is returned and the search must be repeated.
2395  */
2396 static int
2397 read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
2398                       struct extent_buffer **eb_ret, int level, int slot,
2399                       const struct btrfs_key *key)
2400 {
2401         struct btrfs_fs_info *fs_info = root->fs_info;
2402         u64 blocknr;
2403         u64 gen;
2404         struct extent_buffer *b = *eb_ret;
2405         struct extent_buffer *tmp;
2406         struct btrfs_key first_key;
2407         int ret;
2408         int parent_level;
2409
2410         blocknr = btrfs_node_blockptr(b, slot);
2411         gen = btrfs_node_ptr_generation(b, slot);
2412         parent_level = btrfs_header_level(b);
2413         btrfs_node_key_to_cpu(b, &first_key, slot);
2414
2415         tmp = find_extent_buffer(fs_info, blocknr);
2416         if (tmp) {
2417                 /* first we do an atomic uptodate check */
2418                 if (btrfs_buffer_uptodate(tmp, gen, 1) > 0) {
2419                         *eb_ret = tmp;
2420                         return 0;
2421                 }
2422
2423                 /* the pages were up to date, but we failed
2424                  * the generation number check.  Do a full
2425                  * read for the generation number that is correct.
2426                  * We must do this without dropping locks so
2427                  * we can trust our generation number
2428                  */
2429                 btrfs_set_path_blocking(p);
2430
2431                 /* now we're allowed to do a blocking uptodate check */
2432                 ret = btrfs_read_buffer(tmp, gen, parent_level - 1, &first_key);
2433                 if (!ret) {
2434                         *eb_ret = tmp;
2435                         return 0;
2436                 }
2437                 free_extent_buffer(tmp);
2438                 btrfs_release_path(p);
2439                 return -EIO;
2440         }
2441
2442         /*
2443          * reduce lock contention at high levels
2444          * of the btree by dropping locks before
2445          * we read.  Don't release the lock on the current
2446          * level because we need to walk this node to figure
2447          * out which blocks to read.
2448          */
2449         btrfs_unlock_up_safe(p, level + 1);
2450         btrfs_set_path_blocking(p);
2451
2452         if (p->reada != READA_NONE)
2453                 reada_for_search(fs_info, p, level, slot, key->objectid);
2454
2455         ret = -EAGAIN;
2456         tmp = read_tree_block(fs_info, blocknr, gen, parent_level - 1,
2457                               &first_key);
2458         if (!IS_ERR(tmp)) {
2459                 /*
2460                  * If the read above didn't mark this buffer up to date,
2461                  * it will never end up being up to date.  Set ret to EIO now
2462                  * and give up so that our caller doesn't loop forever
2463                  * on our EAGAINs.
2464                  */
2465                 if (!extent_buffer_uptodate(tmp))
2466                         ret = -EIO;
2467                 free_extent_buffer(tmp);
2468         } else {
2469                 ret = PTR_ERR(tmp);
2470         }
2471
2472         btrfs_release_path(p);
2473         return ret;
2474 }
2475
2476 /*
2477  * helper function for btrfs_search_slot.  This does all of the checks
2478  * for node-level blocks and does any balancing required based on
2479  * the ins_len.
2480  *
2481  * If no extra work was required, zero is returned.  If we had to
2482  * drop the path, -EAGAIN is returned and btrfs_search_slot must
2483  * start over
2484  */
2485 static int
2486 setup_nodes_for_search(struct btrfs_trans_handle *trans,
2487                        struct btrfs_root *root, struct btrfs_path *p,
2488                        struct extent_buffer *b, int level, int ins_len,
2489                        int *write_lock_level)
2490 {
2491         struct btrfs_fs_info *fs_info = root->fs_info;
2492         int ret;
2493
2494         if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
2495             BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3) {
2496                 int sret;
2497
2498                 if (*write_lock_level < level + 1) {
2499                         *write_lock_level = level + 1;
2500                         btrfs_release_path(p);
2501                         goto again;
2502                 }
2503
2504                 btrfs_set_path_blocking(p);
2505                 reada_for_balance(fs_info, p, level);
2506                 sret = split_node(trans, root, p, level);
2507
2508                 BUG_ON(sret > 0);
2509                 if (sret) {
2510                         ret = sret;
2511                         goto done;
2512                 }
2513                 b = p->nodes[level];
2514         } else if (ins_len < 0 && btrfs_header_nritems(b) <
2515                    BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) {
2516                 int sret;
2517
2518                 if (*write_lock_level < level + 1) {
2519                         *write_lock_level = level + 1;
2520                         btrfs_release_path(p);
2521                         goto again;
2522                 }
2523
2524                 btrfs_set_path_blocking(p);
2525                 reada_for_balance(fs_info, p, level);
2526                 sret = balance_level(trans, root, p, level);
2527
2528                 if (sret) {
2529                         ret = sret;
2530                         goto done;
2531                 }
2532                 b = p->nodes[level];
2533                 if (!b) {
2534                         btrfs_release_path(p);
2535                         goto again;
2536                 }
2537                 BUG_ON(btrfs_header_nritems(b) == 1);
2538         }
2539         return 0;
2540
2541 again:
2542         ret = -EAGAIN;
2543 done:
2544         return ret;
2545 }
2546
2547 static void key_search_validate(struct extent_buffer *b,
2548                                 const struct btrfs_key *key,
2549                                 int level)
2550 {
2551 #ifdef CONFIG_BTRFS_ASSERT
2552         struct btrfs_disk_key disk_key;
2553
2554         btrfs_cpu_key_to_disk(&disk_key, key);
2555
2556         if (level == 0)
2557                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2558                     offsetof(struct btrfs_leaf, items[0].key),
2559                     sizeof(disk_key)));
2560         else
2561                 ASSERT(!memcmp_extent_buffer(b, &disk_key,
2562                     offsetof(struct btrfs_node, ptrs[0].key),
2563                     sizeof(disk_key)));
2564 #endif
2565 }
2566
2567 static int key_search(struct extent_buffer *b, const struct btrfs_key *key,
2568                       int level, int *prev_cmp, int *slot)
2569 {
2570         if (*prev_cmp != 0) {
2571                 *prev_cmp = btrfs_bin_search(b, key, level, slot);
2572                 return *prev_cmp;
2573         }
2574
2575         key_search_validate(b, key, level);
2576         *slot = 0;
2577
2578         return 0;
2579 }
2580
2581 int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
2582                 u64 iobjectid, u64 ioff, u8 key_type,
2583                 struct btrfs_key *found_key)
2584 {
2585         int ret;
2586         struct btrfs_key key;
2587         struct extent_buffer *eb;
2588
2589         ASSERT(path);
2590         ASSERT(found_key);
2591
2592         key.type = key_type;
2593         key.objectid = iobjectid;
2594         key.offset = ioff;
2595
2596         ret = btrfs_search_slot(NULL, fs_root, &key, path, 0, 0);
2597         if (ret < 0)
2598                 return ret;
2599
2600         eb = path->nodes[0];
2601         if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
2602                 ret = btrfs_next_leaf(fs_root, path);
2603                 if (ret)
2604                         return ret;
2605                 eb = path->nodes[0];
2606         }
2607
2608         btrfs_item_key_to_cpu(eb, found_key, path->slots[0]);
2609         if (found_key->type != key.type ||
2610                         found_key->objectid != key.objectid)
2611                 return 1;
2612
2613         return 0;
2614 }
2615
2616 static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
2617                                                         struct btrfs_path *p,
2618                                                         int write_lock_level)
2619 {
2620         struct btrfs_fs_info *fs_info = root->fs_info;
2621         struct extent_buffer *b;
2622         int root_lock;
2623         int level = 0;
2624
2625         /* We try very hard to do read locks on the root */
2626         root_lock = BTRFS_READ_LOCK;
2627
2628         if (p->search_commit_root) {
2629                 /*
2630                  * The commit roots are read only so we always do read locks,
2631                  * and we always must hold the commit_root_sem when doing
2632                  * searches on them, the only exception is send where we don't
2633                  * want to block transaction commits for a long time, so
2634                  * we need to clone the commit root in order to avoid races
2635                  * with transaction commits that create a snapshot of one of
2636                  * the roots used by a send operation.
2637                  */
2638                 if (p->need_commit_sem) {
2639                         down_read(&fs_info->commit_root_sem);
2640                         b = btrfs_clone_extent_buffer(root->commit_root);
2641                         up_read(&fs_info->commit_root_sem);
2642                         if (!b)
2643                                 return ERR_PTR(-ENOMEM);
2644
2645                 } else {
2646                         b = root->commit_root;
2647                         extent_buffer_get(b);
2648                 }
2649                 level = btrfs_header_level(b);
2650                 /*
2651                  * Ensure that all callers have set skip_locking when
2652                  * p->search_commit_root = 1.
2653                  */
2654                 ASSERT(p->skip_locking == 1);
2655
2656                 goto out;
2657         }
2658
2659         if (p->skip_locking) {
2660                 b = btrfs_root_node(root);
2661                 level = btrfs_header_level(b);
2662                 goto out;
2663         }
2664
2665         /*
2666          * If the level is set to maximum, we can skip trying to get the read
2667          * lock.
2668          */
2669         if (write_lock_level < BTRFS_MAX_LEVEL) {
2670                 /*
2671                  * We don't know the level of the root node until we actually
2672                  * have it read locked
2673                  */
2674                 b = btrfs_read_lock_root_node(root);
2675                 level = btrfs_header_level(b);
2676                 if (level > write_lock_level)
2677                         goto out;
2678
2679                 /* Whoops, must trade for write lock */
2680                 btrfs_tree_read_unlock(b);
2681                 free_extent_buffer(b);
2682         }
2683
2684         b = btrfs_lock_root_node(root);
2685         root_lock = BTRFS_WRITE_LOCK;
2686
2687         /* The level might have changed, check again */
2688         level = btrfs_header_level(b);
2689
2690 out:
2691         p->nodes[level] = b;
2692         if (!p->skip_locking)
2693                 p->locks[level] = root_lock;
2694         /*
2695          * Callers are responsible for dropping b's references.
2696          */
2697         return b;
2698 }
2699
2700
2701 /*
2702  * btrfs_search_slot - look for a key in a tree and perform necessary
2703  * modifications to preserve tree invariants.
2704  *
2705  * @trans:      Handle of transaction, used when modifying the tree
2706  * @p:          Holds all btree nodes along the search path
2707  * @root:       The root node of the tree
2708  * @key:        The key we are looking for
2709  * @ins_len:    Indicates purpose of search, for inserts it is 1, for
2710  *              deletions it's -1. 0 for plain searches
2711  * @cow:        boolean should CoW operations be performed. Must always be 1
2712  *              when modifying the tree.
2713  *
2714  * If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
2715  * If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
2716  *
2717  * If @key is found, 0 is returned and you can find the item in the leaf level
2718  * of the path (level 0)
2719  *
2720  * If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2721  * points to the slot where it should be inserted
2722  *
2723  * If an error is encountered while searching the tree a negative error number
2724  * is returned
2725  */
2726 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2727                       const struct btrfs_key *key, struct btrfs_path *p,
2728                       int ins_len, int cow)
2729 {
2730         struct btrfs_fs_info *fs_info = root->fs_info;
2731         struct extent_buffer *b;
2732         int slot;
2733         int ret;
2734         int err;
2735         int level;
2736         int lowest_unlock = 1;
2737         /* everything at write_lock_level or lower must be write locked */
2738         int write_lock_level = 0;
2739         u8 lowest_level = 0;
2740         int min_write_lock_level;
2741         int prev_cmp;
2742
2743         lowest_level = p->lowest_level;
2744         WARN_ON(lowest_level && ins_len > 0);
2745         WARN_ON(p->nodes[0] != NULL);
2746         BUG_ON(!cow && ins_len);
2747
2748         if (ins_len < 0) {
2749                 lowest_unlock = 2;
2750
2751                 /* when we are removing items, we might have to go up to level
2752                  * two as we update tree pointers  Make sure we keep write
2753                  * for those levels as well
2754                  */
2755                 write_lock_level = 2;
2756         } else if (ins_len > 0) {
2757                 /*
2758                  * for inserting items, make sure we have a write lock on
2759                  * level 1 so we can update keys
2760                  */
2761                 write_lock_level = 1;
2762         }
2763
2764         if (!cow)
2765                 write_lock_level = -1;
2766
2767         if (cow && (p->keep_locks || p->lowest_level))
2768                 write_lock_level = BTRFS_MAX_LEVEL;
2769
2770         min_write_lock_level = write_lock_level;
2771
2772 again:
2773         prev_cmp = -1;
2774         b = btrfs_search_slot_get_root(root, p, write_lock_level);
2775         if (IS_ERR(b)) {
2776                 ret = PTR_ERR(b);
2777                 goto done;
2778         }
2779
2780         while (b) {
2781                 level = btrfs_header_level(b);
2782
2783                 /*
2784                  * setup the path here so we can release it under lock
2785                  * contention with the cow code
2786                  */
2787                 if (cow) {
2788                         bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
2789
2790                         /*
2791                          * if we don't really need to cow this block
2792                          * then we don't want to set the path blocking,
2793                          * so we test it here
2794                          */
2795                         if (!should_cow_block(trans, root, b)) {
2796                                 trans->dirty = true;
2797                                 goto cow_done;
2798                         }
2799
2800                         /*
2801                          * must have write locks on this node and the
2802                          * parent
2803                          */
2804                         if (level > write_lock_level ||
2805                             (level + 1 > write_lock_level &&
2806                             level + 1 < BTRFS_MAX_LEVEL &&
2807                             p->nodes[level + 1])) {
2808                                 write_lock_level = level + 1;
2809                                 btrfs_release_path(p);
2810                                 goto again;
2811                         }
2812
2813                         btrfs_set_path_blocking(p);
2814                         if (last_level)
2815                                 err = btrfs_cow_block(trans, root, b, NULL, 0,
2816                                                       &b);
2817                         else
2818                                 err = btrfs_cow_block(trans, root, b,
2819                                                       p->nodes[level + 1],
2820                                                       p->slots[level + 1], &b);
2821                         if (err) {
2822                                 ret = err;
2823                                 goto done;
2824                         }
2825                 }
2826 cow_done:
2827                 p->nodes[level] = b;
2828                 /*
2829                  * Leave path with blocking locks to avoid massive
2830                  * lock context switch, this is made on purpose.
2831                  */
2832
2833                 /*
2834                  * we have a lock on b and as long as we aren't changing
2835                  * the tree, there is no way to for the items in b to change.
2836                  * It is safe to drop the lock on our parent before we
2837                  * go through the expensive btree search on b.
2838                  *
2839                  * If we're inserting or deleting (ins_len != 0), then we might
2840                  * be changing slot zero, which may require changing the parent.
2841                  * So, we can't drop the lock until after we know which slot
2842                  * we're operating on.
2843                  */
2844                 if (!ins_len && !p->keep_locks) {
2845                         int u = level + 1;
2846
2847                         if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2848                                 btrfs_tree_unlock_rw(p->nodes[u], p->locks[u]);
2849                                 p->locks[u] = 0;
2850                         }
2851                 }
2852
2853                 ret = key_search(b, key, level, &prev_cmp, &slot);
2854                 if (ret < 0)
2855                         goto done;
2856
2857                 if (level != 0) {
2858                         int dec = 0;
2859                         if (ret && slot > 0) {
2860                                 dec = 1;
2861                                 slot -= 1;
2862                         }
2863                         p->slots[level] = slot;
2864                         err = setup_nodes_for_search(trans, root, p, b, level,
2865                                              ins_len, &write_lock_level);
2866                         if (err == -EAGAIN)
2867                                 goto again;
2868                         if (err) {
2869                                 ret = err;
2870                                 goto done;
2871                         }
2872                         b = p->nodes[level];
2873                         slot = p->slots[level];
2874
2875                         /*
2876                          * slot 0 is special, if we change the key
2877                          * we have to update the parent pointer
2878                          * which means we must have a write lock
2879                          * on the parent
2880                          */
2881                         if (slot == 0 && ins_len &&
2882                             write_lock_level < level + 1) {
2883                                 write_lock_level = level + 1;
2884                                 btrfs_release_path(p);
2885                                 goto again;
2886                         }
2887
2888                         unlock_up(p, level, lowest_unlock,
2889                                   min_write_lock_level, &write_lock_level);
2890
2891                         if (level == lowest_level) {
2892                                 if (dec)
2893                                         p->slots[level]++;
2894                                 goto done;
2895                         }
2896
2897                         err = read_block_for_search(root, p, &b, level,
2898                                                     slot, key);
2899                         if (err == -EAGAIN)
2900                                 goto again;
2901                         if (err) {
2902                                 ret = err;
2903                                 goto done;
2904                         }
2905
2906                         if (!p->skip_locking) {
2907                                 level = btrfs_header_level(b);
2908                                 if (level <= write_lock_level) {
2909                                         err = btrfs_try_tree_write_lock(b);
2910                                         if (!err) {
2911                                                 btrfs_set_path_blocking(p);
2912                                                 btrfs_tree_lock(b);
2913                                         }
2914                                         p->locks[level] = BTRFS_WRITE_LOCK;
2915                                 } else {
2916                                         err = btrfs_tree_read_lock_atomic(b);
2917                                         if (!err) {
2918                                                 btrfs_set_path_blocking(p);
2919                                                 btrfs_tree_read_lock(b);
2920                                         }
2921                                         p->locks[level] = BTRFS_READ_LOCK;
2922                                 }
2923                                 p->nodes[level] = b;
2924                         }
2925                 } else {
2926                         p->slots[level] = slot;
2927                         if (ins_len > 0 &&
2928                             btrfs_leaf_free_space(fs_info, b) < ins_len) {
2929                                 if (write_lock_level < 1) {
2930                                         write_lock_level = 1;
2931                                         btrfs_release_path(p);
2932                                         goto again;
2933                                 }
2934
2935                                 btrfs_set_path_blocking(p);
2936                                 err = split_leaf(trans, root, key,
2937                                                  p, ins_len, ret == 0);
2938
2939                                 BUG_ON(err > 0);
2940                                 if (err) {
2941                                         ret = err;
2942                                         goto done;
2943                                 }
2944                         }
2945                         if (!p->search_for_split)
2946                                 unlock_up(p, level, lowest_unlock,
2947                                           min_write_lock_level, NULL);
2948                         goto done;
2949                 }
2950         }
2951         ret = 1;
2952 done:
2953         /*
2954          * we don't really know what they plan on doing with the path
2955          * from here on, so for now just mark it as blocking
2956          */
2957         if (!p->leave_spinning)
2958                 btrfs_set_path_blocking(p);
2959         if (ret < 0 && !p->skip_release_on_error)
2960                 btrfs_release_path(p);
2961         return ret;
2962 }
2963
2964 /*
2965  * Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2966  * current state of the tree together with the operations recorded in the tree
2967  * modification log to search for the key in a previous version of this tree, as
2968  * denoted by the time_seq parameter.
2969  *
2970  * Naturally, there is no support for insert, delete or cow operations.
2971  *
2972  * The resulting path and return value will be set up as if we called
2973  * btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2974  */
2975 int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
2976                           struct btrfs_path *p, u64 time_seq)
2977 {
2978         struct btrfs_fs_info *fs_info = root->fs_info;
2979         struct extent_buffer *b;
2980         int slot;
2981         int ret;
2982         int err;
2983         int level;
2984         int lowest_unlock = 1;
2985         u8 lowest_level = 0;
2986         int prev_cmp = -1;
2987
2988         lowest_level = p->lowest_level;
2989         WARN_ON(p->nodes[0] != NULL);
2990
2991         if (p->search_commit_root) {
2992                 BUG_ON(time_seq);
2993                 return btrfs_search_slot(NULL, root, key, p, 0, 0);
2994         }
2995
2996 again:
2997         b = get_old_root(root, time_seq);
2998         if (!b) {
2999                 ret = -EIO;
3000                 goto done;
3001         }
3002         level = btrfs_header_level(b);
3003         p->locks[level] = BTRFS_READ_LOCK;
3004
3005         while (b) {
3006                 level = btrfs_header_level(b);
3007                 p->nodes[level] = b;
3008
3009                 /*
3010                  * we have a lock on b and as long as we aren't changing
3011                  * the tree, there is no way to for the items in b to change.
3012                  * It is safe to drop the lock on our parent before we
3013                  * go through the expensive btree search on b.
3014                  */
3015                 btrfs_unlock_up_safe(p, level + 1);
3016
3017                 /*
3018                  * Since we can unwind ebs we want to do a real search every
3019                  * time.
3020                  */
3021                 prev_cmp = -1;
3022                 ret = key_search(b, key, level, &prev_cmp, &slot);
3023
3024                 if (level != 0) {
3025                         int dec = 0;
3026                         if (ret && slot > 0) {
3027                                 dec = 1;
3028                                 slot -= 1;
3029                         }
3030                         p->slots[level] = slot;
3031                         unlock_up(p, level, lowest_unlock, 0, NULL);
3032
3033                         if (level == lowest_level) {
3034                                 if (dec)
3035                                         p->slots[level]++;
3036                                 goto done;
3037                         }
3038
3039                         err = read_block_for_search(root, p, &b, level,
3040                                                     slot, key);
3041                         if (err == -EAGAIN)
3042                                 goto again;
3043                         if (err) {
3044                                 ret = err;
3045                                 goto done;
3046                         }
3047
3048                         level = btrfs_header_level(b);
3049                         err = btrfs_tree_read_lock_atomic(b);
3050                         if (!err) {
3051                                 btrfs_set_path_blocking(p);
3052                                 btrfs_tree_read_lock(b);
3053                         }
3054                         b = tree_mod_log_rewind(fs_info, p, b, time_seq);
3055                         if (!b) {
3056                                 ret = -ENOMEM;
3057                                 goto done;
3058                         }
3059                         p->locks[level] = BTRFS_READ_LOCK;
3060                         p->nodes[level] = b;
3061                 } else {
3062                         p->slots[level] = slot;
3063                         unlock_up(p, level, lowest_unlock, 0, NULL);
3064                         goto done;
3065                 }
3066         }
3067         ret = 1;
3068 done:
3069         if (!p->leave_spinning)
3070                 btrfs_set_path_blocking(p);
3071         if (ret < 0)
3072                 btrfs_release_path(p);
3073
3074         return ret;
3075 }
3076
3077 /*
3078  * helper to use instead of search slot if no exact match is needed but
3079  * instead the next or previous item should be returned.
3080  * When find_higher is true, the next higher item is returned, the next lower
3081  * otherwise.
3082  * When return_any and find_higher are both true, and no higher item is found,
3083  * return the next lower instead.
3084  * When return_any is true and find_higher is false, and no lower item is found,
3085  * return the next higher instead.
3086  * It returns 0 if any item is found, 1 if none is found (tree empty), and
3087  * < 0 on error
3088  */
3089 int btrfs_search_slot_for_read(struct btrfs_root *root,
3090                                const struct btrfs_key *key,
3091                                struct btrfs_path *p, int find_higher,
3092                                int return_any)
3093 {
3094         int ret;
3095         struct extent_buffer *leaf;
3096
3097 again:
3098         ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
3099         if (ret <= 0)
3100                 return ret;
3101         /*
3102          * a return value of 1 means the path is at the position where the
3103          * item should be inserted. Normally this is the next bigger item,
3104          * but in case the previous item is the last in a leaf, path points
3105          * to the first free slot in the previous leaf, i.e. at an invalid
3106          * item.
3107          */
3108         leaf = p->nodes[0];
3109
3110         if (find_higher) {
3111                 if (p->slots[0] >= btrfs_header_nritems(leaf)) {
3112                         ret = btrfs_next_leaf(root, p);
3113                         if (ret <= 0)
3114                                 return ret;
3115                         if (!return_any)
3116                                 return 1;
3117                         /*
3118                          * no higher item found, return the next
3119                          * lower instead
3120                          */
3121                         return_any = 0;
3122                         find_higher = 0;
3123                         btrfs_release_path(p);
3124                         goto again;
3125                 }
3126         } else {
3127                 if (p->slots[0] == 0) {
3128                         ret = btrfs_prev_leaf(root, p);
3129                         if (ret < 0)
3130                                 return ret;
3131                         if (!ret) {
3132                                 leaf = p->nodes[0];
3133                                 if (p->slots[0] == btrfs_header_nritems(leaf))
3134                                         p->slots[0]--;
3135                                 return 0;
3136                         }
3137                         if (!return_any)
3138                                 return 1;
3139                         /*
3140                          * no lower item found, return the next
3141                          * higher instead
3142                          */
3143                         return_any = 0;
3144                         find_higher = 1;
3145                         btrfs_release_path(p);
3146                         goto again;
3147                 } else {
3148                         --p->slots[0];
3149                 }
3150         }
3151         return 0;
3152 }
3153
3154 /*
3155  * adjust the pointers going up the tree, starting at level
3156  * making sure the right key of each node is points to 'key'.
3157  * This is used after shifting pointers to the left, so it stops
3158  * fixing up pointers when a given leaf/node is not in slot 0 of the
3159  * higher levels
3160  *
3161  */
3162 static void fixup_low_keys(struct btrfs_path *path,
3163                            struct btrfs_disk_key *key, int level)
3164 {
3165         int i;
3166         struct extent_buffer *t;
3167         int ret;
3168
3169         for (i = level; i < BTRFS_MAX_LEVEL; i++) {
3170                 int tslot = path->slots[i];
3171
3172                 if (!path->nodes[i])
3173                         break;
3174                 t = path->nodes[i];
3175                 ret = tree_mod_log_insert_key(t, tslot, MOD_LOG_KEY_REPLACE,
3176                                 GFP_ATOMIC);
3177                 BUG_ON(ret < 0);
3178                 btrfs_set_node_key(t, key, tslot);
3179                 btrfs_mark_buffer_dirty(path->nodes[i]);
3180                 if (tslot != 0)
3181                         break;
3182         }
3183 }
3184
3185 /*
3186  * update item key.
3187  *
3188  * This function isn't completely safe. It's the caller's responsibility
3189  * that the new key won't break the order
3190  */
3191 void btrfs_set_item_key_safe(struct btrfs_fs_info *fs_info,
3192                              struct btrfs_path *path,
3193                              const struct btrfs_key *new_key)
3194 {
3195         struct btrfs_disk_key disk_key;
3196         struct extent_buffer *eb;
3197         int slot;
3198
3199         eb = path->nodes[0];
3200         slot = path->slots[0];
3201         if (slot > 0) {
3202                 btrfs_item_key(eb, &disk_key, slot - 1);
3203                 BUG_ON(comp_keys(&disk_key, new_key) >= 0);
3204         }
3205         if (slot < btrfs_header_nritems(eb) - 1) {
3206                 btrfs_item_key(eb, &disk_key, slot + 1);
3207                 BUG_ON(comp_keys(&disk_key, new_key) <= 0);
3208         }
3209
3210         btrfs_cpu_key_to_disk(&disk_key, new_key);
3211         btrfs_set_item_key(eb, &disk_key, slot);
3212         btrfs_mark_buffer_dirty(eb);
3213         if (slot == 0)
3214                 fixup_low_keys(path, &disk_key, 1);
3215 }
3216
3217 /*
3218  * try to push data from one node into the next node left in the
3219  * tree.
3220  *
3221  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
3222  * error, and > 0 if there was no room in the left hand block.
3223  */
3224 static int push_node_left(struct btrfs_trans_handle *trans,
3225                           struct btrfs_fs_info *fs_info,
3226                           struct extent_buffer *dst,
3227                           struct extent_buffer *src, int empty)
3228 {
3229         int push_items = 0;
3230         int src_nritems;
3231         int dst_nritems;
3232         int ret = 0;
3233
3234         src_nritems = btrfs_header_nritems(src);
3235         dst_nritems = btrfs_header_nritems(dst);
3236         push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
3237         WARN_ON(btrfs_header_generation(src) != trans->transid);
3238         WARN_ON(btrfs_header_generation(dst) != trans->transid);
3239
3240         if (!empty && src_nritems <= 8)
3241                 return 1;
3242
3243         if (push_items <= 0)
3244                 return 1;
3245
3246         if (empty) {
3247                 push_items = min(src_nritems, push_items);
3248                 if (push_items < src_nritems) {
3249                         /* leave at least 8 pointers in the node if
3250                          * we aren't going to empty it
3251                          */
3252                         if (src_nritems - push_items < 8) {
3253                                 if (push_items <= 8)
3254                                         return 1;
3255                                 push_items -= 8;
3256                         }
3257                 }
3258         } else
3259                 push_items = min(src_nritems - 8, push_items);
3260
3261         ret = tree_mod_log_eb_copy(fs_info, dst, src, dst_nritems, 0,
3262                                    push_items);
3263         if (ret) {
3264                 btrfs_abort_transaction(trans, ret);
3265                 return ret;
3266         }
3267         copy_extent_buffer(dst, src,
3268                            btrfs_node_key_ptr_offset(dst_nritems),
3269                            btrfs_node_key_ptr_offset(0),
3270                            push_items * sizeof(struct btrfs_key_ptr));
3271
3272         if (push_items < src_nritems) {
3273                 /*
3274                  * Don't call tree_mod_log_insert_move here, key removal was
3275                  * already fully logged by tree_mod_log_eb_copy above.
3276                  */
3277                 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
3278                                       btrfs_node_key_ptr_offset(push_items),
3279                                       (src_nritems - push_items) *
3280                                       sizeof(struct btrfs_key_ptr));
3281         }
3282         btrfs_set_header_nritems(src, src_nritems - push_items);
3283         btrfs_set_header_nritems(dst, dst_nritems + push_items);
3284         btrfs_mark_buffer_dirty(src);
3285         btrfs_mark_buffer_dirty(dst);
3286
3287         return ret;
3288 }
3289
3290 /*
3291  * try to push data from one node into the next node right in the
3292  * tree.
3293  *
3294  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
3295  * error, and > 0 if there was no room in the right hand block.
3296  *
3297  * this will  only push up to 1/2 the contents of the left node over
3298  */
3299 static int balance_node_right(struct btrfs_trans_handle *trans,
3300                               struct btrfs_fs_info *fs_info,
3301                               struct extent_buffer *dst,
3302                               struct extent_buffer *src)
3303 {
3304         int push_items = 0;
3305         int max_push;
3306         int src_nritems;
3307         int dst_nritems;
3308         int ret = 0;
3309
3310         WARN_ON(btrfs_header_generation(src) != trans->transid);
3311         WARN_ON(btrfs_header_generation(dst) != trans->transid);
3312
3313         src_nritems = btrfs_header_nritems(src);
3314         dst_nritems = btrfs_header_nritems(dst);
3315         push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
3316         if (push_items <= 0)
3317                 return 1;
3318
3319         if (src_nritems < 4)
3320                 return 1;
3321
3322         max_push = src_nritems / 2 + 1;
3323         /* don't try to empty the node */
3324         if (max_push >= src_nritems)
3325                 return 1;
3326
3327         if (max_push < push_items)
3328                 push_items = max_push;
3329
3330         ret = tree_mod_log_insert_move(dst, push_items, 0, dst_nritems);
3331         BUG_ON(ret < 0);
3332         memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
3333                                       btrfs_node_key_ptr_offset(0),
3334                                       (dst_nritems) *
3335                                       sizeof(struct btrfs_key_ptr));
3336
3337         ret = tree_mod_log_eb_copy(fs_info, dst, src, 0,
3338                                    src_nritems - push_items, push_items);
3339         if (ret) {
3340                 btrfs_abort_transaction(trans, ret);
3341                 return ret;
3342         }
3343         copy_extent_buffer(dst, src,
3344                            btrfs_node_key_ptr_offset(0),
3345                            btrfs_node_key_ptr_offset(src_nritems - push_items),
3346                            push_items * sizeof(struct btrfs_key_ptr));
3347
3348         btrfs_set_header_nritems(src, src_nritems - push_items);
3349         btrfs_set_header_nritems(dst, dst_nritems + push_items);
3350
3351         btrfs_mark_buffer_dirty(src);
3352         btrfs_mark_buffer_dirty(dst);
3353
3354         return ret;
3355 }
3356
3357 /*
3358  * helper function to insert a new root level in the tree.
3359  * A new node is allocated, and a single item is inserted to
3360  * point to the existing root
3361  *
3362  * returns zero on success or < 0 on failure.
3363  */
3364 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
3365                            struct btrfs_root *root,
3366                            struct btrfs_path *path, int level)
3367 {
3368         struct btrfs_fs_info *fs_info = root->fs_info;
3369         u64 lower_gen;
3370         struct extent_buffer *lower;
3371         struct extent_buffer *c;
3372         struct extent_buffer *old;
3373         struct btrfs_disk_key lower_key;
3374         int ret;
3375
3376         BUG_ON(path->nodes[level]);
3377         BUG_ON(path->nodes[level-1] != root->node);
3378
3379         lower = path->nodes[level-1];
3380         if (level == 1)
3381                 btrfs_item_key(lower, &lower_key, 0);
3382         else
3383                 btrfs_node_key(lower, &lower_key, 0);
3384
3385         c = alloc_tree_block_no_bg_flush(trans, root, 0, &lower_key, level,
3386                                          root->node->start, 0);
3387         if (IS_ERR(c))
3388                 return PTR_ERR(c);
3389
3390         root_add_used(root, fs_info->nodesize);
3391
3392         btrfs_set_header_nritems(c, 1);
3393         btrfs_set_node_key(c, &lower_key, 0);
3394         btrfs_set_node_blockptr(c, 0, lower->start);
3395         lower_gen = btrfs_header_generation(lower);
3396         WARN_ON(lower_gen != trans->transid);
3397
3398         btrfs_set_node_ptr_generation(c, 0, lower_gen);
3399
3400         btrfs_mark_buffer_dirty(c);
3401
3402         old = root->node;
3403         ret = tree_mod_log_insert_root(root->node, c, 0);
3404         BUG_ON(ret < 0);
3405         rcu_assign_pointer(root->node, c);
3406
3407         /* the super has an extra ref to root->node */
3408         free_extent_buffer(old);
3409
3410         add_root_to_dirty_list(root);
3411         extent_buffer_get(c);
3412         path->nodes[level] = c;
3413         path->locks[level] = BTRFS_WRITE_LOCK_BLOCKING;
3414         path->slots[level] = 0;
3415         return 0;
3416 }
3417
3418 /*
3419  * worker function to insert a single pointer in a node.
3420  * the node should have enough room for the pointer already
3421  *
3422  * slot and level indicate where you want the key to go, and
3423  * blocknr is the block the key points to.
3424  */
3425 static void insert_ptr(struct btrfs_trans_handle *trans,
3426                        struct btrfs_fs_info *fs_info, struct btrfs_path *path,
3427                        struct btrfs_disk_key *key, u64 bytenr,
3428                        int slot, int level)
3429 {
3430         struct extent_buffer *lower;
3431         int nritems;
3432         int ret;
3433
3434         BUG_ON(!path->nodes[level]);
3435         btrfs_assert_tree_locked(path->nodes[level]);
3436         lower = path->nodes[level];
3437         nritems = btrfs_header_nritems(lower);
3438         BUG_ON(slot > nritems);
3439         BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(fs_info));
3440         if (slot != nritems) {
3441                 if (level) {
3442                         ret = tree_mod_log_insert_move(lower, slot + 1, slot,
3443                                         nritems - slot);
3444                         BUG_ON(ret < 0);
3445                 }
3446                 memmove_extent_buffer(lower,
3447                               btrfs_node_key_ptr_offset(slot + 1),
3448                               btrfs_node_key_ptr_offset(slot),
3449                               (nritems - slot) * sizeof(struct btrfs_key_ptr));
3450         }
3451         if (level) {
3452                 ret = tree_mod_log_insert_key(lower, slot, MOD_LOG_KEY_ADD,
3453                                 GFP_NOFS);
3454                 BUG_ON(ret < 0);
3455         }
3456         btrfs_set_node_key(lower, key, slot);
3457         btrfs_set_node_blockptr(lower, slot, bytenr);
3458         WARN_ON(trans->transid == 0);
3459         btrfs_set_node_ptr_generation(lower, slot, trans->transid);
3460         btrfs_set_header_nritems(lower, nritems + 1);
3461         btrfs_mark_buffer_dirty(lower);
3462 }
3463
3464 /*
3465  * split the node at the specified level in path in two.
3466  * The path is corrected to point to the appropriate node after the split
3467  *
3468  * Before splitting this tries to make some room in the node by pushing
3469  * left and right, if either one works, it returns right away.
3470  *
3471  * returns 0 on success and < 0 on failure
3472  */
3473 static noinline int split_node(struct btrfs_trans_handle *trans,
3474                                struct btrfs_root *root,
3475                                struct btrfs_path *path, int level)
3476 {
3477         struct btrfs_fs_info *fs_info = root->fs_info;
3478         struct extent_buffer *c;
3479         struct extent_buffer *split;
3480         struct btrfs_disk_key disk_key;
3481         int mid;
3482         int ret;
3483         u32 c_nritems;
3484
3485         c = path->nodes[level];
3486         WARN_ON(btrfs_header_generation(c) != trans->transid);
3487         if (c == root->node) {
3488                 /*
3489                  * trying to split the root, lets make a new one
3490                  *
3491                  * tree mod log: We don't log_removal old root in
3492                  * insert_new_root, because that root buffer will be kept as a
3493                  * normal node. We are going to log removal of half of the
3494                  * elements below with tree_mod_log_eb_copy. We're holding a
3495                  * tree lock on the buffer, which is why we cannot race with
3496                  * other tree_mod_log users.
3497                  */
3498                 ret = insert_new_root(trans, root, path, level + 1);
3499                 if (ret)
3500                         return ret;
3501         } else {
3502                 ret = push_nodes_for_insert(trans, root, path, level);
3503                 c = path->nodes[level];
3504                 if (!ret && btrfs_header_nritems(c) <
3505                     BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 3)
3506                         return 0;
3507                 if (ret < 0)
3508                         return ret;
3509         }
3510
3511         c_nritems = btrfs_header_nritems(c);
3512         mid = (c_nritems + 1) / 2;
3513         btrfs_node_key(c, &disk_key, mid);
3514
3515         split = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, level,
3516                                              c->start, 0);
3517         if (IS_ERR(split))
3518                 return PTR_ERR(split);
3519
3520         root_add_used(root, fs_info->nodesize);
3521         ASSERT(btrfs_header_level(c) == level);
3522
3523         ret = tree_mod_log_eb_copy(fs_info, split, c, 0, mid, c_nritems - mid);
3524         if (ret) {
3525                 btrfs_abort_transaction(trans, ret);
3526                 return ret;
3527         }
3528         copy_extent_buffer(split, c,
3529                            btrfs_node_key_ptr_offset(0),
3530                            btrfs_node_key_ptr_offset(mid),
3531                            (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3532         btrfs_set_header_nritems(split, c_nritems - mid);
3533         btrfs_set_header_nritems(c, mid);
3534         ret = 0;
3535
3536         btrfs_mark_buffer_dirty(c);
3537         btrfs_mark_buffer_dirty(split);
3538
3539         insert_ptr(trans, fs_info, path, &disk_key, split->start,
3540                    path->slots[level + 1] + 1, level + 1);
3541
3542         if (path->slots[level] >= mid) {
3543                 path->slots[level] -= mid;
3544                 btrfs_tree_unlock(c);
3545                 free_extent_buffer(c);
3546                 path->nodes[level] = split;
3547                 path->slots[level + 1] += 1;
3548         } else {
3549                 btrfs_tree_unlock(split);
3550                 free_extent_buffer(split);
3551         }
3552         return ret;
3553 }
3554
3555 /*
3556  * how many bytes are required to store the items in a leaf.  start
3557  * and nr indicate which items in the leaf to check.  This totals up the
3558  * space used both by the item structs and the item data
3559  */
3560 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
3561 {
3562         struct btrfs_item *start_item;
3563         struct btrfs_item *end_item;
3564         struct btrfs_map_token token;
3565         int data_len;
3566         int nritems = btrfs_header_nritems(l);
3567         int end = min(nritems, start + nr) - 1;
3568
3569         if (!nr)
3570                 return 0;
3571         btrfs_init_map_token(&token);
3572         start_item = btrfs_item_nr(start);
3573         end_item = btrfs_item_nr(end);
3574         data_len = btrfs_token_item_offset(l, start_item, &token) +
3575                 btrfs_token_item_size(l, start_item, &token);
3576         data_len = data_len - btrfs_token_item_offset(l, end_item, &token);
3577         data_len += sizeof(struct btrfs_item) * nr;
3578         WARN_ON(data_len < 0);
3579         return data_len;
3580 }
3581
3582 /*
3583  * The space between the end of the leaf items and
3584  * the start of the leaf data.  IOW, how much room
3585  * the leaf has left for both items and data
3586  */
3587 noinline int btrfs_leaf_free_space(struct btrfs_fs_info *fs_info,
3588                                    struct extent_buffer *leaf)
3589 {
3590         int nritems = btrfs_header_nritems(leaf);
3591         int ret;
3592
3593         ret = BTRFS_LEAF_DATA_SIZE(fs_info) - leaf_space_used(leaf, 0, nritems);
3594         if (ret < 0) {
3595                 btrfs_crit(fs_info,
3596                            "leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3597                            ret,
3598                            (unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info),
3599                            leaf_space_used(leaf, 0, nritems), nritems);
3600         }
3601         return ret;
3602 }
3603
3604 /*
3605  * min slot controls the lowest index we're willing to push to the
3606  * right.  We'll push up to and including min_slot, but no lower
3607  */
3608 static noinline int __push_leaf_right(struct btrfs_fs_info *fs_info,
3609                                       struct btrfs_path *path,
3610                                       int data_size, int empty,
3611                                       struct extent_buffer *right,
3612                                       int free_space, u32 left_nritems,
3613                                       u32 min_slot)
3614 {
3615         struct extent_buffer *left = path->nodes[0];
3616         struct extent_buffer *upper = path->nodes[1];
3617         struct btrfs_map_token token;
3618         struct btrfs_disk_key disk_key;
3619         int slot;
3620         u32 i;
3621         int push_space = 0;
3622         int push_items = 0;
3623         struct btrfs_item *item;
3624         u32 nr;
3625         u32 right_nritems;
3626         u32 data_end;
3627         u32 this_item_size;
3628
3629         btrfs_init_map_token(&token);
3630
3631         if (empty)
3632                 nr = 0;
3633         else
3634                 nr = max_t(u32, 1, min_slot);
3635
3636         if (path->slots[0] >= left_nritems)
3637                 push_space += data_size;
3638
3639         slot = path->slots[1];
3640         i = left_nritems - 1;
3641         while (i >= nr) {
3642                 item = btrfs_item_nr(i);
3643
3644                 if (!empty && push_items > 0) {
3645                         if (path->slots[0] > i)
3646                                 break;
3647                         if (path->slots[0] == i) {
3648                                 int space = btrfs_leaf_free_space(fs_info, left);
3649                                 if (space + push_space * 2 > free_space)
3650                                         break;
3651                         }
3652                 }
3653
3654                 if (path->slots[0] == i)
3655                         push_space += data_size;
3656
3657                 this_item_size = btrfs_item_size(left, item);
3658                 if (this_item_size + sizeof(*item) + push_space > free_space)
3659                         break;
3660
3661                 push_items++;
3662                 push_space += this_item_size + sizeof(*item);
3663                 if (i == 0)
3664                         break;
3665                 i--;
3666         }
3667
3668         if (push_items == 0)
3669                 goto out_unlock;
3670
3671         WARN_ON(!empty && push_items == left_nritems);
3672
3673         /* push left to right */
3674         right_nritems = btrfs_header_nritems(right);
3675
3676         push_space = btrfs_item_end_nr(left, left_nritems - push_items);
3677         push_space -= leaf_data_end(fs_info, left);
3678
3679         /* make room in the right data area */
3680         data_end = leaf_data_end(fs_info, right);
3681         memmove_extent_buffer(right,
3682                               BTRFS_LEAF_DATA_OFFSET + data_end - push_space,
3683                               BTRFS_LEAF_DATA_OFFSET + data_end,
3684                               BTRFS_LEAF_DATA_SIZE(fs_info) - data_end);
3685
3686         /* copy from the left data area */
3687         copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET +
3688                      BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
3689                      BTRFS_LEAF_DATA_OFFSET + leaf_data_end(fs_info, left),
3690                      push_space);
3691
3692         memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
3693                               btrfs_item_nr_offset(0),
3694                               right_nritems * sizeof(struct btrfs_item));
3695
3696         /* copy the items from left to right */
3697         copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
3698                    btrfs_item_nr_offset(left_nritems - push_items),
3699                    push_items * sizeof(struct btrfs_item));
3700
3701         /* update the item pointers */
3702         right_nritems += push_items;
3703         btrfs_set_header_nritems(right, right_nritems);
3704         push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
3705         for (i = 0; i < right_nritems; i++) {
3706                 item = btrfs_item_nr(i);
3707                 push_space -= btrfs_token_item_size(right, item, &token);
3708                 btrfs_set_token_item_offset(right, item, push_space, &token);
3709         }
3710
3711         left_nritems -= push_items;
3712         btrfs_set_header_nritems(left, left_nritems);
3713
3714         if (left_nritems)
3715                 btrfs_mark_buffer_dirty(left);
3716         else
3717                 clean_tree_block(fs_info, left);
3718
3719         btrfs_mark_buffer_dirty(right);
3720
3721         btrfs_item_key(right, &disk_key, 0);
3722         btrfs_set_node_key(upper, &disk_key, slot + 1);
3723         btrfs_mark_buffer_dirty(upper);
3724
3725         /* then fixup the leaf pointer in the path */
3726         if (path->slots[0] >= left_nritems) {
3727                 path->slots[0] -= left_nritems;
3728                 if (btrfs_header_nritems(path->nodes[0]) == 0)
3729                         clean_tree_block(fs_info, path->nodes[0]);
3730                 btrfs_tree_unlock(path->nodes[0]);
3731                 free_extent_buffer(path->nodes[0]);
3732                 path->nodes[0] = right;
3733                 path->slots[1] += 1;
3734         } else {
3735                 btrfs_tree_unlock(right);
3736                 free_extent_buffer(right);
3737         }
3738         return 0;
3739
3740 out_unlock:
3741         btrfs_tree_unlock(right);
3742         free_extent_buffer(right);
3743         return 1;
3744 }
3745
3746 /*
3747  * push some data in the path leaf to the right, trying to free up at
3748  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3749  *
3750  * returns 1 if the push failed because the other node didn't have enough
3751  * room, 0 if everything worked out and < 0 if there were major errors.
3752  *
3753  * this will push starting from min_slot to the end of the leaf.  It won't
3754  * push any slot lower than min_slot
3755  */
3756 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
3757                            *root, struct btrfs_path *path,
3758                            int min_data_size, int data_size,
3759                            int empty, u32 min_slot)
3760 {
3761         struct btrfs_fs_info *fs_info = root->fs_info;
3762         struct extent_buffer *left = path->nodes[0];
3763         struct extent_buffer *right;
3764         struct extent_buffer *upper;
3765         int slot;
3766         int free_space;
3767         u32 left_nritems;
3768         int ret;
3769
3770         if (!path->nodes[1])
3771                 return 1;
3772
3773         slot = path->slots[1];
3774         upper = path->nodes[1];
3775         if (slot >= btrfs_header_nritems(upper) - 1)
3776                 return 1;
3777
3778         btrfs_assert_tree_locked(path->nodes[1]);
3779
3780         right = read_node_slot(fs_info, upper, slot + 1);
3781         /*
3782          * slot + 1 is not valid or we fail to read the right node,
3783          * no big deal, just return.
3784          */
3785         if (IS_ERR(right))
3786                 return 1;
3787
3788         btrfs_tree_lock(right);
3789         btrfs_set_lock_blocking_write(right);
3790
3791         free_space = btrfs_leaf_free_space(fs_info, right);
3792         if (free_space < data_size)
3793                 goto out_unlock;
3794
3795         /* cow and double check */
3796         ret = btrfs_cow_block(trans, root, right, upper,
3797                               slot + 1, &right);
3798         if (ret)
3799                 goto out_unlock;
3800
3801         free_space = btrfs_leaf_free_space(fs_info, right);
3802         if (free_space < data_size)
3803                 goto out_unlock;
3804
3805         left_nritems = btrfs_header_nritems(left);
3806         if (left_nritems == 0)
3807                 goto out_unlock;
3808
3809         if (path->slots[0] == left_nritems && !empty) {
3810                 /* Key greater than all keys in the leaf, right neighbor has
3811                  * enough room for it and we're not emptying our leaf to delete
3812                  * it, therefore use right neighbor to insert the new item and
3813                  * no need to touch/dirty our left leaf. */
3814                 btrfs_tree_unlock(left);
3815                 free_extent_buffer(left);
3816                 path->nodes[0] = right;
3817                 path->slots[0] = 0;
3818                 path->slots[1]++;
3819                 return 0;
3820         }
3821
3822         return __push_leaf_right(fs_info, path, min_data_size, empty,
3823                                 right, free_space, left_nritems, min_slot);
3824 out_unlock:
3825         btrfs_tree_unlock(right);
3826         free_extent_buffer(right);
3827         return 1;
3828 }
3829
3830 /*
3831  * push some data in the path leaf to the left, trying to free up at
3832  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3833  *
3834  * max_slot can put a limit on how far into the leaf we'll push items.  The
3835  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us do all the
3836  * items
3837  */
3838 static noinline int __push_leaf_left(struct btrfs_fs_info *fs_info,
3839                                      struct btrfs_path *path, int data_size,
3840                                      int empty, struct extent_buffer *left,
3841                                      int free_space, u32 right_nritems,
3842                                      u32 max_slot)
3843 {
3844         struct btrfs_disk_key disk_key;
3845         struct extent_buffer *right = path->nodes[0];
3846         int i;
3847         int push_space = 0;
3848         int push_items = 0;
3849         struct btrfs_item *item;
3850         u32 old_left_nritems;
3851         u32 nr;
3852         int ret = 0;
3853         u32 this_item_size;
3854         u32 old_left_item_size;
3855         struct btrfs_map_token token;
3856
3857         btrfs_init_map_token(&token);
3858
3859         if (empty)
3860                 nr = min(right_nritems, max_slot);
3861         else
3862                 nr = min(right_nritems - 1, max_slot);
3863
3864         for (i = 0; i < nr; i++) {
3865                 item = btrfs_item_nr(i);
3866
3867                 if (!empty && push_items > 0) {
3868                         if (path->slots[0] < i)
3869                                 break;
3870                         if (path->slots[0] == i) {
3871                                 int space = btrfs_leaf_free_space(fs_info, right);
3872                                 if (space + push_space * 2 > free_space)
3873                                         break;
3874                         }
3875                 }
3876
3877                 if (path->slots[0] == i)
3878                         push_space += data_size;
3879
3880                 this_item_size = btrfs_item_size(right, item);
3881                 if (this_item_size + sizeof(*item) + push_space > free_space)
3882                         break;
3883
3884                 push_items++;
3885                 push_space += this_item_size + sizeof(*item);
3886         }
3887
3888         if (push_items == 0) {
3889                 ret = 1;
3890                 goto out;
3891         }
3892         WARN_ON(!empty && push_items == btrfs_header_nritems(right));
3893
3894         /* push data from right to left */
3895         copy_extent_buffer(left, right,
3896                            btrfs_item_nr_offset(btrfs_header_nritems(left)),
3897                            btrfs_item_nr_offset(0),
3898                            push_items * sizeof(struct btrfs_item));
3899
3900         push_space = BTRFS_LEAF_DATA_SIZE(fs_info) -
3901                      btrfs_item_offset_nr(right, push_items - 1);
3902
3903         copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET +
3904                      leaf_data_end(fs_info, left) - push_space,
3905                      BTRFS_LEAF_DATA_OFFSET +
3906                      btrfs_item_offset_nr(right, push_items - 1),
3907                      push_space);
3908         old_left_nritems = btrfs_header_nritems(left);
3909         BUG_ON(old_left_nritems <= 0);
3910
3911         old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
3912         for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
3913                 u32 ioff;
3914
3915                 item = btrfs_item_nr(i);
3916
3917                 ioff = btrfs_token_item_offset(left, item, &token);
3918                 btrfs_set_token_item_offset(left, item,
3919                       ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size),
3920                       &token);
3921         }
3922         btrfs_set_header_nritems(left, old_left_nritems + push_items);
3923
3924         /* fixup right node */
3925         if (push_items > right_nritems)
3926                 WARN(1, KERN_CRIT "push items %d nr %u\n", push_items,
3927                        right_nritems);
3928
3929         if (push_items < right_nritems) {
3930                 push_space = btrfs_item_offset_nr(right, push_items - 1) -
3931                                                   leaf_data_end(fs_info, right);
3932                 memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET +
3933                                       BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
3934                                       BTRFS_LEAF_DATA_OFFSET +
3935                                       leaf_data_end(fs_info, right), push_space);
3936
3937                 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
3938                               btrfs_item_nr_offset(push_items),
3939                              (btrfs_header_nritems(right) - push_items) *
3940                              sizeof(struct btrfs_item));
3941         }
3942         right_nritems -= push_items;
3943         btrfs_set_header_nritems(right, right_nritems);
3944         push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
3945         for (i = 0; i < right_nritems; i++) {
3946                 item = btrfs_item_nr(i);
3947
3948                 push_space = push_space - btrfs_token_item_size(right,
3949                                                                 item, &token);
3950                 btrfs_set_token_item_offset(right, item, push_space, &token);
3951         }
3952
3953         btrfs_mark_buffer_dirty(left);
3954         if (right_nritems)
3955                 btrfs_mark_buffer_dirty(right);
3956         else
3957                 clean_tree_block(fs_info, right);
3958
3959         btrfs_item_key(right, &disk_key, 0);
3960         fixup_low_keys(path, &disk_key, 1);
3961
3962         /* then fixup the leaf pointer in the path */
3963         if (path->slots[0] < push_items) {
3964                 path->slots[0] += old_left_nritems;
3965                 btrfs_tree_unlock(path->nodes[0]);
3966                 free_extent_buffer(path->nodes[0]);
3967                 path->nodes[0] = left;
3968                 path->slots[1] -= 1;
3969         } else {
3970                 btrfs_tree_unlock(left);
3971                 free_extent_buffer(left);
3972                 path->slots[0] -= push_items;
3973         }
3974         BUG_ON(path->slots[0] < 0);
3975         return ret;
3976 out:
3977         btrfs_tree_unlock(left);
3978         free_extent_buffer(left);
3979         return ret;
3980 }
3981
3982 /*
3983  * push some data in the path leaf to the left, trying to free up at
3984  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
3985  *
3986  * max_slot can put a limit on how far into the leaf we'll push items.  The
3987  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us push all the
3988  * items
3989  */
3990 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
3991                           *root, struct btrfs_path *path, int min_data_size,
3992                           int data_size, int empty, u32 max_slot)
3993 {
3994         struct btrfs_fs_info *fs_info = root->fs_info;
3995         struct extent_buffer *right = path->nodes[0];
3996         struct extent_buffer *left;
3997         int slot;
3998         int free_space;
3999         u32 right_nritems;
4000         int ret = 0;
4001
4002         slot = path->slots[1];
4003         if (slot == 0)
4004                 return 1;
4005         if (!path->nodes[1])
4006                 return 1;
4007
4008         right_nritems = btrfs_header_nritems(right);
4009         if (right_nritems == 0)
4010                 return 1;
4011
4012         btrfs_assert_tree_locked(path->nodes[1]);
4013
4014         left = read_node_slot(fs_info, path->nodes[1], slot - 1);
4015         /*
4016          * slot - 1 is not valid or we fail to read the left node,
4017          * no big deal, just return.
4018          */
4019         if (IS_ERR(left))
4020                 return 1;
4021
4022         btrfs_tree_lock(left);
4023         btrfs_set_lock_blocking_write(left);
4024
4025         free_space = btrfs_leaf_free_space(fs_info, left);
4026         if (free_space < data_size) {
4027                 ret = 1;
4028                 goto out;
4029         }
4030
4031         /* cow and double check */
4032         ret = btrfs_cow_block(trans, root, left,
4033                               path->nodes[1], slot - 1, &left);
4034         if (ret) {
4035                 /* we hit -ENOSPC, but it isn't fatal here */
4036                 if (ret == -ENOSPC)
4037                         ret = 1;
4038                 goto out;
4039         }
4040
4041         free_space = btrfs_leaf_free_space(fs_info, left);
4042         if (free_space < data_size) {
4043                 ret = 1;
4044                 goto out;
4045         }
4046
4047         return __push_leaf_left(fs_info, path, min_data_size,
4048                                empty, left, free_space, right_nritems,
4049                                max_slot);
4050 out:
4051         btrfs_tree_unlock(left);
4052         free_extent_buffer(left);
4053         return ret;
4054 }
4055
4056 /*
4057  * split the path's leaf in two, making sure there is at least data_size
4058  * available for the resulting leaf level of the path.
4059  */
4060 static noinline void copy_for_split(struct btrfs_trans_handle *trans,
4061                                     struct btrfs_fs_info *fs_info,
4062                                     struct btrfs_path *path,
4063                                     struct extent_buffer *l,
4064                                     struct extent_buffer *right,
4065                                     int slot, int mid, int nritems)
4066 {
4067         int data_copy_size;
4068         int rt_data_off;
4069         int i;
4070         struct btrfs_disk_key disk_key;
4071         struct btrfs_map_token token;
4072
4073         btrfs_init_map_token(&token);
4074
4075         nritems = nritems - mid;
4076         btrfs_set_header_nritems(right, nritems);
4077         data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(fs_info, l);
4078
4079         copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
4080                            btrfs_item_nr_offset(mid),
4081                            nritems * sizeof(struct btrfs_item));
4082
4083         copy_extent_buffer(right, l,
4084                      BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) -
4085                      data_copy_size, BTRFS_LEAF_DATA_OFFSET +
4086                      leaf_data_end(fs_info, l), data_copy_size);
4087
4088         rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_end_nr(l, mid);
4089
4090         for (i = 0; i < nritems; i++) {
4091                 struct btrfs_item *item = btrfs_item_nr(i);
4092                 u32 ioff;
4093
4094                 ioff = btrfs_token_item_offset(right, item, &token);
4095                 btrfs_set_token_item_offset(right, item,
4096                                             ioff + rt_data_off, &token);
4097         }
4098
4099         btrfs_set_header_nritems(l, mid);
4100         btrfs_item_key(right, &disk_key, 0);
4101         insert_ptr(trans, fs_info, path, &disk_key, right->start,
4102                    path->slots[1] + 1, 1);
4103
4104         btrfs_mark_buffer_dirty(right);
4105         btrfs_mark_buffer_dirty(l);
4106         BUG_ON(path->slots[0] != slot);
4107
4108         if (mid <= slot) {
4109                 btrfs_tree_unlock(path->nodes[0]);
4110                 free_extent_buffer(path->nodes[0]);
4111                 path->nodes[0] = right;
4112                 path->slots[0] -= mid;
4113                 path->slots[1] += 1;
4114         } else {
4115                 btrfs_tree_unlock(right);
4116                 free_extent_buffer(right);
4117         }
4118
4119         BUG_ON(path->slots[0] < 0);
4120 }
4121
4122 /*
4123  * double splits happen when we need to insert a big item in the middle
4124  * of a leaf.  A double split can leave us with 3 mostly empty leaves:
4125  * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
4126  *          A                 B                 C
4127  *
4128  * We avoid this by trying to push the items on either side of our target
4129  * into the adjacent leaves.  If all goes well we can avoid the double split
4130  * completely.
4131  */
4132 static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
4133                                           struct btrfs_root *root,
4134                                           struct btrfs_path *path,
4135                                           int data_size)
4136 {
4137         struct btrfs_fs_info *fs_info = root->fs_info;
4138         int ret;
4139         int progress = 0;
4140         int slot;
4141         u32 nritems;
4142         int space_needed = data_size;
4143
4144         slot = path->slots[0];
4145         if (slot < btrfs_header_nritems(path->nodes[0]))
4146                 space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
4147
4148         /*
4149          * try to push all the items after our slot into the
4150          * right leaf
4151          */
4152         ret = push_leaf_right(trans, root, path, 1, space_needed, 0, slot);
4153         if (ret < 0)
4154                 return ret;
4155
4156         if (ret == 0)
4157                 progress++;
4158
4159         nritems = btrfs_header_nritems(path->nodes[0]);
4160         /*
4161          * our goal is to get our slot at the start or end of a leaf.  If
4162          * we've done so we're done
4163          */
4164         if (path->slots[0] == 0 || path->slots[0] == nritems)
4165                 return 0;
4166
4167         if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= data_size)
4168                 return 0;
4169
4170         /* try to push all the items before our slot into the next leaf */
4171         slot = path->slots[0];
4172         space_needed = data_size;
4173         if (slot > 0)
4174                 space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
4175         ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
4176         if (ret < 0)
4177                 return ret;
4178
4179         if (ret == 0)
4180                 progress++;
4181
4182         if (progress)
4183                 return 0;
4184         return 1;
4185 }
4186
4187 /*
4188  * split the path's leaf in two, making sure there is at least data_size
4189  * available for the resulting leaf level of the path.
4190  *
4191  * returns 0 if all went well and < 0 on failure.
4192  */
4193 static noinline int split_leaf(struct btrfs_trans_handle *trans,
4194                                struct btrfs_root *root,
4195                                const struct btrfs_key *ins_key,
4196                                struct btrfs_path *path, int data_size,
4197                                int extend)
4198 {
4199         struct btrfs_disk_key disk_key;
4200         struct extent_buffer *l;
4201         u32 nritems;
4202         int mid;
4203         int slot;
4204         struct extent_buffer *right;
4205         struct btrfs_fs_info *fs_info = root->fs_info;
4206         int ret = 0;
4207         int wret;
4208         int split;
4209         int num_doubles = 0;
4210         int tried_avoid_double = 0;
4211
4212         l = path->nodes[0];
4213         slot = path->slots[0];
4214         if (extend && data_size + btrfs_item_size_nr(l, slot) +
4215             sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(fs_info))
4216                 return -EOVERFLOW;
4217
4218         /* first try to make some room by pushing left and right */
4219         if (data_size && path->nodes[1]) {
4220                 int space_needed = data_size;
4221
4222                 if (slot < btrfs_header_nritems(l))
4223                         space_needed -= btrfs_leaf_free_space(fs_info, l);
4224
4225                 wret = push_leaf_right(trans, root, path, space_needed,
4226                                        space_needed, 0, 0);
4227                 if (wret < 0)
4228                         return wret;
4229                 if (wret) {
4230                         space_needed = data_size;
4231                         if (slot > 0)
4232                                 space_needed -= btrfs_leaf_free_space(fs_info,
4233                                                                       l);
4234                         wret = push_leaf_left(trans, root, path, space_needed,
4235                                               space_needed, 0, (u32)-1);
4236                         if (wret < 0)
4237                                 return wret;
4238                 }
4239                 l = path->nodes[0];
4240
4241                 /* did the pushes work? */
4242                 if (btrfs_leaf_free_space(fs_info, l) >= data_size)
4243                         return 0;
4244         }
4245
4246         if (!path->nodes[1]) {
4247                 ret = insert_new_root(trans, root, path, 1);
4248                 if (ret)
4249                         return ret;
4250         }
4251 again:
4252         split = 1;
4253         l = path->nodes[0];
4254         slot = path->slots[0];
4255         nritems = btrfs_header_nritems(l);
4256         mid = (nritems + 1) / 2;
4257
4258         if (mid <= slot) {
4259                 if (nritems == 1 ||
4260                     leaf_space_used(l, mid, nritems - mid) + data_size >
4261                         BTRFS_LEAF_DATA_SIZE(fs_info)) {
4262                         if (slot >= nritems) {
4263                                 split = 0;
4264                         } else {
4265                                 mid = slot;
4266                                 if (mid != nritems &&
4267                                     leaf_space_used(l, mid, nritems - mid) +
4268                                     data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
4269                                         if (data_size && !tried_avoid_double)
4270                                                 goto push_for_double;
4271                                         split = 2;
4272                                 }
4273                         }
4274                 }
4275         } else {
4276                 if (leaf_space_used(l, 0, mid) + data_size >
4277                         BTRFS_LEAF_DATA_SIZE(fs_info)) {
4278                         if (!extend && data_size && slot == 0) {
4279                                 split = 0;
4280                         } else if ((extend || !data_size) && slot == 0) {
4281                                 mid = 1;
4282                         } else {
4283                                 mid = slot;
4284                                 if (mid != nritems &&
4285                                     leaf_space_used(l, mid, nritems - mid) +
4286                                     data_size > BTRFS_LEAF_DATA_SIZE(fs_info)) {
4287                                         if (data_size && !tried_avoid_double)
4288                                                 goto push_for_double;
4289                                         split = 2;
4290                                 }
4291                         }
4292                 }
4293         }
4294
4295         if (split == 0)
4296                 btrfs_cpu_key_to_disk(&disk_key, ins_key);
4297         else
4298                 btrfs_item_key(l, &disk_key, mid);
4299
4300         right = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, 0,
4301                                              l->start, 0);
4302         if (IS_ERR(right))
4303                 return PTR_ERR(right);
4304
4305         root_add_used(root, fs_info->nodesize);
4306
4307         if (split == 0) {
4308                 if (mid <= slot) {
4309                         btrfs_set_header_nritems(right, 0);
4310                         insert_ptr(trans, fs_info, path, &disk_key,
4311                                    right->start, path->slots[1] + 1, 1);
4312                         btrfs_tree_unlock(path->nodes[0]);
4313                         free_extent_buffer(path->nodes[0]);
4314                         path->nodes[0] = right;
4315                         path->slots[0] = 0;
4316                         path->slots[1] += 1;
4317                 } else {
4318                         btrfs_set_header_nritems(right, 0);
4319                         insert_ptr(trans, fs_info, path, &disk_key,
4320                                    right->start, path->slots[1], 1);
4321                         btrfs_tree_unlock(path->nodes[0]);
4322                         free_extent_buffer(path->nodes[0]);
4323                         path->nodes[0] = right;
4324                         path->slots[0] = 0;
4325                         if (path->slots[1] == 0)
4326                                 fixup_low_keys(path, &disk_key, 1);
4327                 }
4328                 /*
4329                  * We create a new leaf 'right' for the required ins_len and
4330                  * we'll do btrfs_mark_buffer_dirty() on this leaf after copying
4331                  * the content of ins_len to 'right'.
4332                  */
4333                 return ret;
4334         }
4335
4336         copy_for_split(trans, fs_info, path, l, right, slot, mid, nritems);
4337
4338         if (split == 2) {
4339                 BUG_ON(num_doubles != 0);
4340                 num_doubles++;
4341                 goto again;
4342         }
4343
4344         return 0;
4345
4346 push_for_double:
4347         push_for_double_split(trans, root, path, data_size);
4348         tried_avoid_double = 1;
4349         if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= data_size)
4350                 return 0;
4351         goto again;
4352 }
4353
4354 static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
4355                                          struct btrfs_root *root,
4356                                          struct btrfs_path *path, int ins_len)
4357 {
4358         struct btrfs_fs_info *fs_info = root->fs_info;
4359         struct btrfs_key key;
4360         struct extent_buffer *leaf;
4361         struct btrfs_file_extent_item *fi;
4362         u64 extent_len = 0;
4363         u32 item_size;
4364         int ret;
4365
4366         leaf = path->nodes[0];
4367         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4368
4369         BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
4370                key.type != BTRFS_EXTENT_CSUM_KEY);
4371
4372         if (btrfs_leaf_free_space(fs_info, leaf) >= ins_len)
4373                 return 0;
4374
4375         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4376         if (key.type == BTRFS_EXTENT_DATA_KEY) {
4377                 fi = btrfs_item_ptr(leaf, path->slots[0],
4378                                     struct btrfs_file_extent_item);
4379                 extent_len = btrfs_file_extent_num_bytes(leaf, fi);
4380         }
4381         btrfs_release_path(path);
4382
4383         path->keep_locks = 1;
4384         path->search_for_split = 1;
4385         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
4386         path->search_for_split = 0;
4387         if (ret > 0)
4388                 ret = -EAGAIN;
4389         if (ret < 0)
4390                 goto err;
4391
4392         ret = -EAGAIN;
4393         leaf = path->nodes[0];
4394         /* if our item isn't there, return now */
4395         if (item_size != btrfs_item_size_nr(leaf, path->slots[0]))
4396                 goto err;
4397
4398         /* the leaf has  changed, it now has room.  return now */
4399         if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= ins_len)
4400                 goto err;
4401
4402         if (key.type == BTRFS_EXTENT_DATA_KEY) {
4403                 fi = btrfs_item_ptr(leaf, path->slots[0],
4404                                     struct btrfs_file_extent_item);
4405                 if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
4406                         goto err;
4407         }
4408
4409         btrfs_set_path_blocking(path);
4410         ret = split_leaf(trans, root, &key, path, ins_len, 1);
4411         if (ret)
4412                 goto err;
4413
4414         path->keep_locks = 0;
4415         btrfs_unlock_up_safe(path, 1);
4416         return 0;
4417 err:
4418         path->keep_locks = 0;
4419         return ret;
4420 }
4421
4422 static noinline int split_item(struct btrfs_fs_info *fs_info,
4423                                struct btrfs_path *path,
4424                                const struct btrfs_key *new_key,
4425                                unsigned long split_offset)
4426 {
4427         struct extent_buffer *leaf;
4428         struct btrfs_item *item;
4429         struct btrfs_item *new_item;
4430         int slot;
4431         char *buf;
4432         u32 nritems;
4433         u32 item_size;
4434         u32 orig_offset;
4435         struct btrfs_disk_key disk_key;
4436
4437         leaf = path->nodes[0];
4438         BUG_ON(btrfs_leaf_free_space(fs_info, leaf) < sizeof(struct btrfs_item));
4439
4440         btrfs_set_path_blocking(path);
4441
4442         item = btrfs_item_nr(path->slots[0]);
4443         orig_offset = btrfs_item_offset(leaf, item);
4444         item_size = btrfs_item_size(leaf, item);
4445
4446         buf = kmalloc(item_size, GFP_NOFS);
4447         if (!buf)
4448                 return -ENOMEM;
4449
4450         read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
4451                             path->slots[0]), item_size);
4452
4453         slot = path->slots[0] + 1;
4454         nritems = btrfs_header_nritems(leaf);
4455         if (slot != nritems) {
4456                 /* shift the items */
4457                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
4458                                 btrfs_item_nr_offset(slot),
4459                                 (nritems - slot) * sizeof(struct btrfs_item));
4460         }
4461
4462         btrfs_cpu_key_to_disk(&disk_key, new_key);
4463         btrfs_set_item_key(leaf, &disk_key, slot);
4464
4465         new_item = btrfs_item_nr(slot);
4466
4467         btrfs_set_item_offset(leaf, new_item, orig_offset);
4468         btrfs_set_item_size(leaf, new_item, item_size - split_offset);
4469
4470         btrfs_set_item_offset(leaf, item,
4471                               orig_offset + item_size - split_offset);
4472         btrfs_set_item_size(leaf, item, split_offset);
4473
4474         btrfs_set_header_nritems(leaf, nritems + 1);
4475
4476         /* write the data for the start of the original item */
4477         write_extent_buffer(leaf, buf,
4478                             btrfs_item_ptr_offset(leaf, path->slots[0]),
4479                             split_offset);
4480
4481         /* write the data for the new item */
4482         write_extent_buffer(leaf, buf + split_offset,
4483                             btrfs_item_ptr_offset(leaf, slot),
4484                             item_size - split_offset);
4485         btrfs_mark_buffer_dirty(leaf);
4486
4487         BUG_ON(btrfs_leaf_free_space(fs_info, leaf) < 0);
4488         kfree(buf);
4489         return 0;
4490 }
4491
4492 /*
4493  * This function splits a single item into two items,
4494  * giving 'new_key' to the new item and splitting the
4495  * old one at split_offset (from the start of the item).
4496  *
4497  * The path may be released by this operation.  After
4498  * the split, the path is pointing to the old item.  The
4499  * new item is going to be in the same node as the old one.
4500  *
4501  * Note, the item being split must be smaller enough to live alone on
4502  * a tree block with room for one extra struct btrfs_item
4503  *
4504  * This allows us to split the item in place, keeping a lock on the
4505  * leaf the entire time.
4506  */
4507 int btrfs_split_item(struct btrfs_trans_handle *trans,
4508                      struct btrfs_root *root,
4509                      struct btrfs_path *path,
4510                      const struct btrfs_key *new_key,
4511                      unsigned long split_offset)
4512 {
4513         int ret;
4514         ret = setup_leaf_for_split(trans, root, path,
4515                                    sizeof(struct btrfs_item));
4516         if (ret)
4517                 return ret;
4518
4519         ret = split_item(root->fs_info, path, new_key, split_offset);
4520         return ret;
4521 }
4522
4523 /*
4524  * This function duplicate a item, giving 'new_key' to the new item.
4525  * It guarantees both items live in the same tree leaf and the new item
4526  * is contiguous with the original item.
4527  *
4528  * This allows us to split file extent in place, keeping a lock on the
4529  * leaf the entire time.
4530  */
4531 int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
4532                          struct btrfs_root *root,
4533                          struct btrfs_path *path,
4534                          const struct btrfs_key *new_key)
4535 {
4536         struct extent_buffer *leaf;
4537         int ret;
4538         u32 item_size;
4539
4540         leaf = path->nodes[0];
4541         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
4542         ret = setup_leaf_for_split(trans, root, path,
4543                                    item_size + sizeof(struct btrfs_item));
4544         if (ret)
4545                 return ret;
4546
4547         path->slots[0]++;
4548         setup_items_for_insert(root, path, new_key, &item_size,
4549                                item_size, item_size +
4550                                sizeof(struct btrfs_item), 1);
4551         leaf = path->nodes[0];
4552         memcpy_extent_buffer(leaf,
4553                              btrfs_item_ptr_offset(leaf, path->slots[0]),
4554                              btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4555                              item_size);
4556         return 0;
4557 }
4558
4559 /*
4560  * make the item pointed to by the path smaller.  new_size indicates
4561  * how small to make it, and from_end tells us if we just chop bytes
4562  * off the end of the item or if we shift the item to chop bytes off
4563  * the front.
4564  */
4565 void btrfs_truncate_item(struct btrfs_fs_info *fs_info,
4566                          struct btrfs_path *path, u32 new_size, int from_end)
4567 {
4568         int slot;
4569         struct extent_buffer *leaf;
4570         struct btrfs_item *item;
4571         u32 nritems;
4572         unsigned int data_end;
4573         unsigned int old_data_start;
4574         unsigned int old_size;
4575         unsigned int size_diff;
4576         int i;
4577         struct btrfs_map_token token;
4578
4579         btrfs_init_map_token(&token);
4580
4581         leaf = path->nodes[0];
4582         slot = path->slots[0];
4583
4584         old_size = btrfs_item_size_nr(leaf, slot);
4585         if (old_size == new_size)
4586                 return;
4587
4588         nritems = btrfs_header_nritems(leaf);
4589         data_end = leaf_data_end(fs_info, leaf);
4590
4591         old_data_start = btrfs_item_offset_nr(leaf, slot);
4592
4593         size_diff = old_size - new_size;
4594
4595         BUG_ON(slot < 0);
4596         BUG_ON(slot >= nritems);
4597
4598         /*
4599          * item0..itemN ... dataN.offset..dataN.size .. data0.size
4600          */
4601         /* first correct the data pointers */
4602         for (i = slot; i < nritems; i++) {
4603                 u32 ioff;
4604                 item = btrfs_item_nr(i);
4605
4606                 ioff = btrfs_token_item_offset(leaf, item, &token);
4607                 btrfs_set_token_item_offset(leaf, item,
4608                                             ioff + size_diff, &token);
4609         }
4610
4611         /* shift the data */
4612         if (from_end) {
4613                 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4614                               data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
4615                               data_end, old_data_start + new_size - data_end);
4616         } else {
4617                 struct btrfs_disk_key disk_key;
4618                 u64 offset;
4619
4620                 btrfs_item_key(leaf, &disk_key, slot);
4621
4622                 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
4623                         unsigned long ptr;
4624                         struct btrfs_file_extent_item *fi;
4625
4626                         fi = btrfs_item_ptr(leaf, slot,
4627                                             struct btrfs_file_extent_item);
4628                         fi = (struct btrfs_file_extent_item *)(
4629                              (unsigned long)fi - size_diff);
4630
4631                         if (btrfs_file_extent_type(leaf, fi) ==
4632                             BTRFS_FILE_EXTENT_INLINE) {
4633                                 ptr = btrfs_item_ptr_offset(leaf, slot);
4634                                 memmove_extent_buffer(leaf, ptr,
4635                                       (unsigned long)fi,
4636                                       BTRFS_FILE_EXTENT_INLINE_DATA_START);
4637                         }
4638                 }
4639
4640                 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4641                               data_end + size_diff, BTRFS_LEAF_DATA_OFFSET +
4642                               data_end, old_data_start - data_end);
4643
4644                 offset = btrfs_disk_key_offset(&disk_key);
4645                 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
4646                 btrfs_set_item_key(leaf, &disk_key, slot);
4647                 if (slot == 0)
4648                         fixup_low_keys(path, &disk_key, 1);
4649         }
4650
4651         item = btrfs_item_nr(slot);
4652         btrfs_set_item_size(leaf, item, new_size);
4653         btrfs_mark_buffer_dirty(leaf);
4654
4655         if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
4656                 btrfs_print_leaf(leaf);
4657                 BUG();
4658         }
4659 }
4660
4661 /*
4662  * make the item pointed to by the path bigger, data_size is the added size.
4663  */
4664 void btrfs_extend_item(struct btrfs_fs_info *fs_info, struct btrfs_path *path,
4665                        u32 data_size)
4666 {
4667         int slot;
4668         struct extent_buffer *leaf;
4669         struct btrfs_item *item;
4670         u32 nritems;
4671         unsigned int data_end;
4672         unsigned int old_data;
4673         unsigned int old_size;
4674         int i;
4675         struct btrfs_map_token token;
4676
4677         btrfs_init_map_token(&token);
4678
4679         leaf = path->nodes[0];
4680
4681         nritems = btrfs_header_nritems(leaf);
4682         data_end = leaf_data_end(fs_info, leaf);
4683
4684         if (btrfs_leaf_free_space(fs_info, leaf) < data_size) {
4685                 btrfs_print_leaf(leaf);
4686                 BUG();
4687         }
4688         slot = path->slots[0];
4689         old_data = btrfs_item_end_nr(leaf, slot);
4690
4691         BUG_ON(slot < 0);
4692         if (slot >= nritems) {
4693                 btrfs_print_leaf(leaf);
4694                 btrfs_crit(fs_info, "slot %d too large, nritems %d",
4695                            slot, nritems);
4696                 BUG_ON(1);
4697         }
4698
4699         /*
4700          * item0..itemN ... dataN.offset..dataN.size .. data0.size
4701          */
4702         /* first correct the data pointers */
4703         for (i = slot; i < nritems; i++) {
4704                 u32 ioff;
4705                 item = btrfs_item_nr(i);
4706
4707                 ioff = btrfs_token_item_offset(leaf, item, &token);
4708                 btrfs_set_token_item_offset(leaf, item,
4709                                             ioff - data_size, &token);
4710         }
4711
4712         /* shift the data */
4713         memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4714                       data_end - data_size, BTRFS_LEAF_DATA_OFFSET +
4715                       data_end, old_data - data_end);
4716
4717         data_end = old_data;
4718         old_size = btrfs_item_size_nr(leaf, slot);
4719         item = btrfs_item_nr(slot);
4720         btrfs_set_item_size(leaf, item, old_size + data_size);
4721         btrfs_mark_buffer_dirty(leaf);
4722
4723         if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
4724                 btrfs_print_leaf(leaf);
4725                 BUG();
4726         }
4727 }
4728
4729 /*
4730  * this is a helper for btrfs_insert_empty_items, the main goal here is
4731  * to save stack depth by doing the bulk of the work in a function
4732  * that doesn't call btrfs_search_slot
4733  */
4734 void setup_items_for_insert(struct btrfs_root *root, struct btrfs_path *path,
4735                             const struct btrfs_key *cpu_key, u32 *data_size,
4736                             u32 total_data, u32 total_size, int nr)
4737 {
4738         struct btrfs_fs_info *fs_info = root->fs_info;
4739         struct btrfs_item *item;
4740         int i;
4741         u32 nritems;
4742         unsigned int data_end;
4743         struct btrfs_disk_key disk_key;
4744         struct extent_buffer *leaf;
4745         int slot;
4746         struct btrfs_map_token token;
4747
4748         if (path->slots[0] == 0) {
4749                 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
4750                 fixup_low_keys(path, &disk_key, 1);
4751         }
4752         btrfs_unlock_up_safe(path, 1);
4753
4754         btrfs_init_map_token(&token);
4755
4756         leaf = path->nodes[0];
4757         slot = path->slots[0];
4758
4759         nritems = btrfs_header_nritems(leaf);
4760         data_end = leaf_data_end(fs_info, leaf);
4761
4762         if (btrfs_leaf_free_space(fs_info, leaf) < total_size) {
4763                 btrfs_print_leaf(leaf);
4764                 btrfs_crit(fs_info, "not enough freespace need %u have %d",
4765                            total_size, btrfs_leaf_free_space(fs_info, leaf));
4766                 BUG();
4767         }
4768
4769         if (slot != nritems) {
4770                 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
4771
4772                 if (old_data < data_end) {
4773                         btrfs_print_leaf(leaf);
4774                         btrfs_crit(fs_info, "slot %d old_data %d data_end %d",
4775                                    slot, old_data, data_end);
4776                         BUG_ON(1);
4777                 }
4778                 /*
4779                  * item0..itemN ... dataN.offset..dataN.size .. data0.size
4780                  */
4781                 /* first correct the data pointers */
4782                 for (i = slot; i < nritems; i++) {
4783                         u32 ioff;
4784
4785                         item = btrfs_item_nr(i);
4786                         ioff = btrfs_token_item_offset(leaf, item, &token);
4787                         btrfs_set_token_item_offset(leaf, item,
4788                                                     ioff - total_data, &token);
4789                 }
4790                 /* shift the items */
4791                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
4792                               btrfs_item_nr_offset(slot),
4793                               (nritems - slot) * sizeof(struct btrfs_item));
4794
4795                 /* shift the data */
4796                 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4797                               data_end - total_data, BTRFS_LEAF_DATA_OFFSET +
4798                               data_end, old_data - data_end);
4799                 data_end = old_data;
4800         }
4801
4802         /* setup the item for the new data */
4803         for (i = 0; i < nr; i++) {
4804                 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
4805                 btrfs_set_item_key(leaf, &disk_key, slot + i);
4806                 item = btrfs_item_nr(slot + i);
4807                 btrfs_set_token_item_offset(leaf, item,
4808                                             data_end - data_size[i], &token);
4809                 data_end -= data_size[i];
4810                 btrfs_set_token_item_size(leaf, item, data_size[i], &token);
4811         }
4812
4813         btrfs_set_header_nritems(leaf, nritems + nr);
4814         btrfs_mark_buffer_dirty(leaf);
4815
4816         if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
4817                 btrfs_print_leaf(leaf);
4818                 BUG();
4819         }
4820 }
4821
4822 /*
4823  * Given a key and some data, insert items into the tree.
4824  * This does all the path init required, making room in the tree if needed.
4825  */
4826 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
4827                             struct btrfs_root *root,
4828                             struct btrfs_path *path,
4829                             const struct btrfs_key *cpu_key, u32 *data_size,
4830                             int nr)
4831 {
4832         int ret = 0;
4833         int slot;
4834         int i;
4835         u32 total_size = 0;
4836         u32 total_data = 0;
4837
4838         for (i = 0; i < nr; i++)
4839                 total_data += data_size[i];
4840
4841         total_size = total_data + (nr * sizeof(struct btrfs_item));
4842         ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
4843         if (ret == 0)
4844                 return -EEXIST;
4845         if (ret < 0)
4846                 return ret;
4847
4848         slot = path->slots[0];
4849         BUG_ON(slot < 0);
4850
4851         setup_items_for_insert(root, path, cpu_key, data_size,
4852                                total_data, total_size, nr);
4853         return 0;
4854 }
4855
4856 /*
4857  * Given a key and some data, insert an item into the tree.
4858  * This does all the path init required, making room in the tree if needed.
4859  */
4860 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4861                       const struct btrfs_key *cpu_key, void *data,
4862                       u32 data_size)
4863 {
4864         int ret = 0;
4865         struct btrfs_path *path;
4866         struct extent_buffer *leaf;
4867         unsigned long ptr;
4868
4869         path = btrfs_alloc_path();
4870         if (!path)
4871                 return -ENOMEM;
4872         ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
4873         if (!ret) {
4874                 leaf = path->nodes[0];
4875                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4876                 write_extent_buffer(leaf, data, ptr, data_size);
4877                 btrfs_mark_buffer_dirty(leaf);
4878         }
4879         btrfs_free_path(path);
4880         return ret;
4881 }
4882
4883 /*
4884  * delete the pointer from a given node.
4885  *
4886  * the tree should have been previously balanced so the deletion does not
4887  * empty a node.
4888  */
4889 static void del_ptr(struct btrfs_root *root, struct btrfs_path *path,
4890                     int level, int slot)
4891 {
4892         struct extent_buffer *parent = path->nodes[level];
4893         u32 nritems;
4894         int ret;
4895
4896         nritems = btrfs_header_nritems(parent);
4897         if (slot != nritems - 1) {
4898                 if (level) {
4899                         ret = tree_mod_log_insert_move(parent, slot, slot + 1,
4900                                         nritems - slot - 1);
4901                         BUG_ON(ret < 0);
4902                 }
4903                 memmove_extent_buffer(parent,
4904                               btrfs_node_key_ptr_offset(slot),
4905                               btrfs_node_key_ptr_offset(slot + 1),
4906                               sizeof(struct btrfs_key_ptr) *
4907                               (nritems - slot - 1));
4908         } else if (level) {
4909                 ret = tree_mod_log_insert_key(parent, slot, MOD_LOG_KEY_REMOVE,
4910                                 GFP_NOFS);
4911                 BUG_ON(ret < 0);
4912         }
4913
4914         nritems--;
4915         btrfs_set_header_nritems(parent, nritems);
4916         if (nritems == 0 && parent == root->node) {
4917                 BUG_ON(btrfs_header_level(root->node) != 1);
4918                 /* just turn the root into a leaf and break */
4919                 btrfs_set_header_level(root->node, 0);
4920         } else if (slot == 0) {
4921                 struct btrfs_disk_key disk_key;
4922
4923                 btrfs_node_key(parent, &disk_key, 0);
4924                 fixup_low_keys(path, &disk_key, level + 1);
4925         }
4926         btrfs_mark_buffer_dirty(parent);
4927 }
4928
4929 /*
4930  * a helper function to delete the leaf pointed to by path->slots[1] and
4931  * path->nodes[1].
4932  *
4933  * This deletes the pointer in path->nodes[1] and frees the leaf
4934  * block extent.  zero is returned if it all worked out, < 0 otherwise.
4935  *
4936  * The path must have already been setup for deleting the leaf, including
4937  * all the proper balancing.  path->nodes[1] must be locked.
4938  */
4939 static noinline void btrfs_del_leaf(struct btrfs_trans_handle *trans,
4940                                     struct btrfs_root *root,
4941                                     struct btrfs_path *path,
4942                                     struct extent_buffer *leaf)
4943 {
4944         WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4945         del_ptr(root, path, 1, path->slots[1]);
4946
4947         /*
4948          * btrfs_free_extent is expensive, we want to make sure we
4949          * aren't holding any locks when we call it
4950          */
4951         btrfs_unlock_up_safe(path, 0);
4952
4953         root_sub_used(root, leaf->len);
4954
4955         extent_buffer_get(leaf);
4956         btrfs_free_tree_block(trans, root, leaf, 0, 1);
4957         free_extent_buffer_stale(leaf);
4958 }
4959 /*
4960  * delete the item at the leaf level in path.  If that empties
4961  * the leaf, remove it from the tree
4962  */
4963 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4964                     struct btrfs_path *path, int slot, int nr)
4965 {
4966         struct btrfs_fs_info *fs_info = root->fs_info;
4967         struct extent_buffer *leaf;
4968         struct btrfs_item *item;
4969         u32 last_off;
4970         u32 dsize = 0;
4971         int ret = 0;
4972         int wret;
4973         int i;
4974         u32 nritems;
4975         struct btrfs_map_token token;
4976
4977         btrfs_init_map_token(&token);
4978
4979         leaf = path->nodes[0];
4980         last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
4981
4982         for (i = 0; i < nr; i++)
4983                 dsize += btrfs_item_size_nr(leaf, slot + i);
4984
4985         nritems = btrfs_header_nritems(leaf);
4986
4987         if (slot + nr != nritems) {
4988                 int data_end = leaf_data_end(fs_info, leaf);
4989
4990                 memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
4991                               data_end + dsize,
4992                               BTRFS_LEAF_DATA_OFFSET + data_end,
4993                               last_off - data_end);
4994
4995                 for (i = slot + nr; i < nritems; i++) {
4996                         u32 ioff;
4997
4998                         item = btrfs_item_nr(i);
4999                         ioff = btrfs_token_item_offset(leaf, item, &token);
5000                         btrfs_set_token_item_offset(leaf, item,
5001                                                     ioff + dsize, &token);
5002                 }
5003
5004                 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
5005                               btrfs_item_nr_offset(slot + nr),
5006                               sizeof(struct btrfs_item) *
5007                               (nritems - slot - nr));
5008         }
5009         btrfs_set_header_nritems(leaf, nritems - nr);
5010         nritems -= nr;
5011
5012         /* delete the leaf if we've emptied it */
5013         if (nritems == 0) {
5014                 if (leaf == root->node) {
5015                         btrfs_set_header_level(leaf, 0);
5016                 } else {
5017                         btrfs_set_path_blocking(path);
5018                         clean_tree_block(fs_info, leaf);
5019                         btrfs_del_leaf(trans, root, path, leaf);
5020                 }
5021         } else {
5022                 int used = leaf_space_used(leaf, 0, nritems);
5023                 if (slot == 0) {
5024                         struct btrfs_disk_key disk_key;
5025
5026                         btrfs_item_key(leaf, &disk_key, 0);
5027                         fixup_low_keys(path, &disk_key, 1);
5028                 }
5029
5030                 /* delete the leaf if it is mostly empty */
5031                 if (used < BTRFS_LEAF_DATA_SIZE(fs_info) / 3) {
5032                         /* push_leaf_left fixes the path.
5033                          * make sure the path still points to our leaf
5034                          * for possible call to del_ptr below
5035                          */
5036                         slot = path->slots[1];
5037                         extent_buffer_get(leaf);
5038
5039                         btrfs_set_path_blocking(path);
5040                         wret = push_leaf_left(trans, root, path, 1, 1,
5041                                               1, (u32)-1);
5042                         if (wret < 0 && wret != -ENOSPC)
5043                                 ret = wret;
5044
5045                         if (path->nodes[0] == leaf &&
5046                             btrfs_header_nritems(leaf)) {
5047                                 wret = push_leaf_right(trans, root, path, 1,
5048                                                        1, 1, 0);
5049                                 if (wret < 0 && wret != -ENOSPC)
5050                                         ret = wret;
5051                         }
5052
5053                         if (btrfs_header_nritems(leaf) == 0) {
5054                                 path->slots[1] = slot;
5055                                 btrfs_del_leaf(trans, root, path, leaf);
5056                                 free_extent_buffer(leaf);
5057                                 ret = 0;
5058                         } else {
5059                                 /* if we're still in the path, make sure
5060                                  * we're dirty.  Otherwise, one of the
5061                                  * push_leaf functions must have already
5062                                  * dirtied this buffer
5063                                  */
5064                                 if (path->nodes[0] == leaf)
5065                                         btrfs_mark_buffer_dirty(leaf);
5066                                 free_extent_buffer(leaf);
5067                         }
5068                 } else {
5069                         btrfs_mark_buffer_dirty(leaf);
5070                 }
5071         }
5072         return ret;
5073 }
5074
5075 /*
5076  * search the tree again to find a leaf with lesser keys
5077  * returns 0 if it found something or 1 if there are no lesser leaves.
5078  * returns < 0 on io errors.
5079  *
5080  * This may release the path, and so you may lose any locks held at the
5081  * time you call it.
5082  */
5083 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
5084 {
5085         struct btrfs_key key;
5086         struct btrfs_disk_key found_key;
5087         int ret;
5088
5089         btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
5090
5091         if (key.offset > 0) {
5092                 key.offset--;
5093         } else if (key.type > 0) {
5094                 key.type--;
5095                 key.offset = (u64)-1;
5096         } else if (key.objectid > 0) {
5097                 key.objectid--;
5098                 key.type = (u8)-1;
5099                 key.offset = (u64)-1;
5100         } else {
5101                 return 1;
5102         }
5103
5104         btrfs_release_path(path);
5105         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5106         if (ret < 0)
5107                 return ret;
5108         btrfs_item_key(path->nodes[0], &found_key, 0);
5109         ret = comp_keys(&found_key, &key);
5110         /*
5111          * We might have had an item with the previous key in the tree right
5112          * before we released our path. And after we released our path, that
5113          * item might have been pushed to the first slot (0) of the leaf we
5114          * were holding due to a tree balance. Alternatively, an item with the
5115          * previous key can exist as the only element of a leaf (big fat item).
5116          * Therefore account for these 2 cases, so that our callers (like
5117          * btrfs_previous_item) don't miss an existing item with a key matching
5118          * the previous key we computed above.
5119          */
5120         if (ret <= 0)
5121                 return 0;
5122         return 1;
5123 }
5124
5125 /*
5126  * A helper function to walk down the tree starting at min_key, and looking
5127  * for nodes or leaves that are have a minimum transaction id.
5128  * This is used by the btree defrag code, and tree logging
5129  *
5130  * This does not cow, but it does stuff the starting key it finds back
5131  * into min_key, so you can call btrfs_search_slot with cow=1 on the
5132  * key and get a writable path.
5133  *
5134  * This honors path->lowest_level to prevent descent past a given level
5135  * of the tree.
5136  *
5137  * min_trans indicates the oldest transaction that you are interested
5138  * in walking through.  Any nodes or leaves older than min_trans are
5139  * skipped over (without reading them).
5140  *
5141  * returns zero if something useful was found, < 0 on error and 1 if there
5142  * was nothing in the tree that matched the search criteria.
5143  */
5144 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
5145                          struct btrfs_path *path,
5146                          u64 min_trans)
5147 {
5148         struct btrfs_fs_info *fs_info = root->fs_info;
5149         struct extent_buffer *cur;
5150         struct btrfs_key found_key;
5151         int slot;
5152         int sret;
5153         u32 nritems;
5154         int level;
5155         int ret = 1;
5156         int keep_locks = path->keep_locks;
5157
5158         path->keep_locks = 1;
5159 again:
5160         cur = btrfs_read_lock_root_node(root);
5161         level = btrfs_header_level(cur);
5162         WARN_ON(path->nodes[level]);
5163         path->nodes[level] = cur;
5164         path->locks[level] = BTRFS_READ_LOCK;
5165
5166         if (btrfs_header_generation(cur) < min_trans) {
5167                 ret = 1;
5168                 goto out;
5169         }
5170         while (1) {
5171                 nritems = btrfs_header_nritems(cur);
5172                 level = btrfs_header_level(cur);
5173                 sret = btrfs_bin_search(cur, min_key, level, &slot);
5174
5175                 /* at the lowest level, we're done, setup the path and exit */
5176                 if (level == path->lowest_level) {
5177                         if (slot >= nritems)
5178                                 goto find_next_key;
5179                         ret = 0;
5180                         path->slots[level] = slot;
5181                         btrfs_item_key_to_cpu(cur, &found_key, slot);
5182                         goto out;
5183                 }
5184                 if (sret && slot > 0)
5185                         slot--;
5186                 /*
5187                  * check this node pointer against the min_trans parameters.
5188                  * If it is too old, old, skip to the next one.
5189                  */
5190                 while (slot < nritems) {
5191                         u64 gen;
5192
5193                         gen = btrfs_node_ptr_generation(cur, slot);
5194                         if (gen < min_trans) {
5195                                 slot++;
5196                                 continue;
5197                         }
5198                         break;
5199                 }
5200 find_next_key:
5201                 /*
5202                  * we didn't find a candidate key in this node, walk forward
5203                  * and find another one
5204                  */
5205                 if (slot >= nritems) {
5206                         path->slots[level] = slot;
5207                         btrfs_set_path_blocking(path);
5208                         sret = btrfs_find_next_key(root, path, min_key, level,
5209                                                   min_trans);
5210                         if (sret == 0) {
5211                                 btrfs_release_path(path);
5212                                 goto again;
5213                         } else {
5214                                 goto out;
5215                         }
5216                 }
5217                 /* save our key for returning back */
5218                 btrfs_node_key_to_cpu(cur, &found_key, slot);
5219                 path->slots[level] = slot;
5220                 if (level == path->lowest_level) {
5221                         ret = 0;
5222                         goto out;
5223                 }
5224                 btrfs_set_path_blocking(path);
5225                 cur = read_node_slot(fs_info, cur, slot);
5226                 if (IS_ERR(cur)) {
5227                         ret = PTR_ERR(cur);
5228                         goto out;
5229                 }
5230
5231                 btrfs_tree_read_lock(cur);
5232
5233                 path->locks[level - 1] = BTRFS_READ_LOCK;
5234                 path->nodes[level - 1] = cur;
5235                 unlock_up(path, level, 1, 0, NULL);
5236         }
5237 out:
5238         path->keep_locks = keep_locks;
5239         if (ret == 0) {
5240                 btrfs_unlock_up_safe(path, path->lowest_level + 1);
5241                 btrfs_set_path_blocking(path);
5242                 memcpy(min_key, &found_key, sizeof(found_key));
5243         }
5244         return ret;
5245 }
5246
5247 static int tree_move_down(struct btrfs_fs_info *fs_info,
5248                            struct btrfs_path *path,
5249                            int *level)
5250 {
5251         struct extent_buffer *eb;
5252
5253         BUG_ON(*level == 0);
5254         eb = read_node_slot(fs_info, path->nodes[*level], path->slots[*level]);
5255         if (IS_ERR(eb))
5256                 return PTR_ERR(eb);
5257
5258         path->nodes[*level - 1] = eb;
5259         path->slots[*level - 1] = 0;
5260         (*level)--;
5261         return 0;
5262 }
5263
5264 static int tree_move_next_or_upnext(struct btrfs_path *path,
5265                                     int *level, int root_level)
5266 {
5267         int ret = 0;
5268         int nritems;
5269         nritems = btrfs_header_nritems(path->nodes[*level]);
5270
5271         path->slots[*level]++;
5272
5273         while (path->slots[*level] >= nritems) {
5274                 if (*level == root_level)
5275                         return -1;
5276
5277                 /* move upnext */
5278                 path->slots[*level] = 0;
5279                 free_extent_buffer(path->nodes[*level]);
5280                 path->nodes[*level] = NULL;
5281                 (*level)++;
5282                 path->slots[*level]++;
5283
5284                 nritems = btrfs_header_nritems(path->nodes[*level]);
5285                 ret = 1;
5286         }
5287         return ret;
5288 }
5289
5290 /*
5291  * Returns 1 if it had to move up and next. 0 is returned if it moved only next
5292  * or down.
5293  */
5294 static int tree_advance(struct btrfs_fs_info *fs_info,
5295                         struct btrfs_path *path,
5296                         int *level, int root_level,
5297                         int allow_down,
5298                         struct btrfs_key *key)
5299 {
5300         int ret;
5301
5302         if (*level == 0 || !allow_down) {
5303                 ret = tree_move_next_or_upnext(path, level, root_level);
5304         } else {
5305                 ret = tree_move_down(fs_info, path, level);
5306         }
5307         if (ret >= 0) {
5308                 if (*level == 0)
5309                         btrfs_item_key_to_cpu(path->nodes[*level], key,
5310                                         path->slots[*level]);
5311                 else
5312                         btrfs_node_key_to_cpu(path->nodes[*level], key,
5313                                         path->slots[*level]);
5314         }
5315         return ret;
5316 }
5317
5318 static int tree_compare_item(struct btrfs_path *left_path,
5319                              struct btrfs_path *right_path,
5320                              char *tmp_buf)
5321 {
5322         int cmp;
5323         int len1, len2;
5324         unsigned long off1, off2;
5325
5326         len1 = btrfs_item_size_nr(left_path->nodes[0], left_path->slots[0]);
5327         len2 = btrfs_item_size_nr(right_path->nodes[0], right_path->slots[0]);
5328         if (len1 != len2)
5329                 return 1;
5330
5331         off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
5332         off2 = btrfs_item_ptr_offset(right_path->nodes[0],
5333                                 right_path->slots[0]);
5334
5335         read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
5336
5337         cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
5338         if (cmp)
5339                 return 1;
5340         return 0;
5341 }
5342
5343 #define ADVANCE 1
5344 #define ADVANCE_ONLY_NEXT -1
5345
5346 /*
5347  * This function compares two trees and calls the provided callback for
5348  * every changed/new/deleted item it finds.
5349  * If shared tree blocks are encountered, whole subtrees are skipped, making
5350  * the compare pretty fast on snapshotted subvolumes.
5351  *
5352  * This currently works on commit roots only. As commit roots are read only,
5353  * we don't do any locking. The commit roots are protected with transactions.
5354  * Transactions are ended and rejoined when a commit is tried in between.
5355  *
5356  * This function checks for modifications done to the trees while comparing.
5357  * If it detects a change, it aborts immediately.
5358  */
5359 int btrfs_compare_trees(struct btrfs_root *left_root,
5360                         struct btrfs_root *right_root,
5361                         btrfs_changed_cb_t changed_cb, void *ctx)
5362 {
5363         struct btrfs_fs_info *fs_info = left_root->fs_info;
5364         int ret;
5365         int cmp;
5366         struct btrfs_path *left_path = NULL;
5367         struct btrfs_path *right_path = NULL;
5368         struct btrfs_key left_key;
5369         struct btrfs_key right_key;
5370         char *tmp_buf = NULL;
5371         int left_root_level;
5372         int right_root_level;
5373         int left_level;
5374         int right_level;
5375         int left_end_reached;
5376         int right_end_reached;
5377         int advance_left;
5378         int advance_right;
5379         u64 left_blockptr;
5380         u64 right_blockptr;
5381         u64 left_gen;
5382         u64 right_gen;
5383
5384         left_path = btrfs_alloc_path();
5385         if (!left_path) {
5386                 ret = -ENOMEM;
5387                 goto out;
5388         }
5389         right_path = btrfs_alloc_path();
5390         if (!right_path) {
5391                 ret = -ENOMEM;
5392                 goto out;
5393         }
5394
5395         tmp_buf = kvmalloc(fs_info->nodesize, GFP_KERNEL);
5396         if (!tmp_buf) {
5397                 ret = -ENOMEM;
5398                 goto out;
5399         }
5400
5401         left_path->search_commit_root = 1;
5402         left_path->skip_locking = 1;
5403         right_path->search_commit_root = 1;
5404         right_path->skip_locking = 1;
5405
5406         /*
5407          * Strategy: Go to the first items of both trees. Then do
5408          *
5409          * If both trees are at level 0
5410          *   Compare keys of current items
5411          *     If left < right treat left item as new, advance left tree
5412          *       and repeat
5413          *     If left > right treat right item as deleted, advance right tree
5414          *       and repeat
5415          *     If left == right do deep compare of items, treat as changed if
5416          *       needed, advance both trees and repeat
5417          * If both trees are at the same level but not at level 0
5418          *   Compare keys of current nodes/leafs
5419          *     If left < right advance left tree and repeat
5420          *     If left > right advance right tree and repeat
5421          *     If left == right compare blockptrs of the next nodes/leafs
5422          *       If they match advance both trees but stay at the same level
5423          *         and repeat
5424          *       If they don't match advance both trees while allowing to go
5425          *         deeper and repeat
5426          * If tree levels are different
5427          *   Advance the tree that needs it and repeat
5428          *
5429          * Advancing a tree means:
5430          *   If we are at level 0, try to go to the next slot. If that's not
5431          *   possible, go one level up and repeat. Stop when we found a level
5432          *   where we could go to the next slot. We may at this point be on a
5433          *   node or a leaf.
5434          *
5435          *   If we are not at level 0 and not on shared tree blocks, go one
5436          *   level deeper.
5437          *
5438          *   If we are not at level 0 and on shared tree blocks, go one slot to
5439          *   the right if possible or go up and right.
5440          */
5441
5442         down_read(&fs_info->commit_root_sem);
5443         left_level = btrfs_header_level(left_root->commit_root);
5444         left_root_level = left_level;
5445         left_path->nodes[left_level] =
5446                         btrfs_clone_extent_buffer(left_root->commit_root);
5447         if (!left_path->nodes[left_level]) {
5448                 up_read(&fs_info->commit_root_sem);
5449                 ret = -ENOMEM;
5450                 goto out;
5451         }
5452
5453         right_level = btrfs_header_level(right_root->commit_root);
5454         right_root_level = right_level;
5455         right_path->nodes[right_level] =
5456                         btrfs_clone_extent_buffer(right_root->commit_root);
5457         if (!right_path->nodes[right_level]) {
5458                 up_read(&fs_info->commit_root_sem);
5459                 ret = -ENOMEM;
5460                 goto out;
5461         }
5462         up_read(&fs_info->commit_root_sem);
5463
5464         if (left_level == 0)
5465                 btrfs_item_key_to_cpu(left_path->nodes[left_level],
5466                                 &left_key, left_path->slots[left_level]);
5467         else
5468                 btrfs_node_key_to_cpu(left_path->nodes[left_level],
5469                                 &left_key, left_path->slots[left_level]);
5470         if (right_level == 0)
5471                 btrfs_item_key_to_cpu(right_path->nodes[right_level],
5472                                 &right_key, right_path->slots[right_level]);
5473         else
5474                 btrfs_node_key_to_cpu(right_path->nodes[right_level],
5475                                 &right_key, right_path->slots[right_level]);
5476
5477         left_end_reached = right_end_reached = 0;
5478         advance_left = advance_right = 0;
5479
5480         while (1) {
5481                 if (advance_left && !left_end_reached) {
5482                         ret = tree_advance(fs_info, left_path, &left_level,
5483                                         left_root_level,
5484                                         advance_left != ADVANCE_ONLY_NEXT,
5485                                         &left_key);
5486                         if (ret == -1)
5487                                 left_end_reached = ADVANCE;
5488                         else if (ret < 0)
5489                                 goto out;
5490                         advance_left = 0;
5491                 }
5492                 if (advance_right && !right_end_reached) {
5493                         ret = tree_advance(fs_info, right_path, &right_level,
5494                                         right_root_level,
5495                                         advance_right != ADVANCE_ONLY_NEXT,
5496                                         &right_key);
5497                         if (ret == -1)
5498                                 right_end_reached = ADVANCE;
5499                         else if (ret < 0)
5500                                 goto out;
5501                         advance_right = 0;
5502                 }
5503
5504                 if (left_end_reached && right_end_reached) {
5505                         ret = 0;
5506                         goto out;
5507                 } else if (left_end_reached) {
5508                         if (right_level == 0) {
5509                                 ret = changed_cb(left_path, right_path,
5510                                                 &right_key,
5511                                                 BTRFS_COMPARE_TREE_DELETED,
5512                                                 ctx);
5513                                 if (ret < 0)
5514                                         goto out;
5515                         }
5516                         advance_right = ADVANCE;
5517                         continue;
5518                 } else if (right_end_reached) {
5519                         if (left_level == 0) {
5520                                 ret = changed_cb(left_path, right_path,
5521                                                 &left_key,
5522                                                 BTRFS_COMPARE_TREE_NEW,
5523                                                 ctx);
5524                                 if (ret < 0)
5525                                         goto out;
5526                         }
5527                         advance_left = ADVANCE;
5528                         continue;
5529                 }
5530
5531                 if (left_level == 0 && right_level == 0) {
5532                         cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5533                         if (cmp < 0) {
5534                                 ret = changed_cb(left_path, right_path,
5535                                                 &left_key,
5536                                                 BTRFS_COMPARE_TREE_NEW,
5537                                                 ctx);
5538                                 if (ret < 0)
5539                                         goto out;
5540                                 advance_left = ADVANCE;
5541                         } else if (cmp > 0) {
5542                                 ret = changed_cb(left_path, right_path,
5543                                                 &right_key,
5544                                                 BTRFS_COMPARE_TREE_DELETED,
5545                                                 ctx);
5546                                 if (ret < 0)
5547                                         goto out;
5548                                 advance_right = ADVANCE;
5549                         } else {
5550                                 enum btrfs_compare_tree_result result;
5551
5552                                 WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));
5553                                 ret = tree_compare_item(left_path, right_path,
5554                                                         tmp_buf);
5555                                 if (ret)
5556                                         result = BTRFS_COMPARE_TREE_CHANGED;
5557                                 else
5558                                         result = BTRFS_COMPARE_TREE_SAME;
5559                                 ret = changed_cb(left_path, right_path,
5560                                                  &left_key, result, ctx);
5561                                 if (ret < 0)
5562                                         goto out;
5563                                 advance_left = ADVANCE;
5564                                 advance_right = ADVANCE;
5565                         }
5566                 } else if (left_level == right_level) {
5567                         cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5568                         if (cmp < 0) {
5569                                 advance_left = ADVANCE;
5570                         } else if (cmp > 0) {
5571                                 advance_right = ADVANCE;
5572                         } else {
5573                                 left_blockptr = btrfs_node_blockptr(
5574                                                 left_path->nodes[left_level],
5575                                                 left_path->slots[left_level]);
5576                                 right_blockptr = btrfs_node_blockptr(
5577                                                 right_path->nodes[right_level],
5578                                                 right_path->slots[right_level]);
5579                                 left_gen = btrfs_node_ptr_generation(
5580                                                 left_path->nodes[left_level],
5581                                                 left_path->slots[left_level]);
5582                                 right_gen = btrfs_node_ptr_generation(
5583                                                 right_path->nodes[right_level],
5584                                                 right_path->slots[right_level]);
5585                                 if (left_blockptr == right_blockptr &&
5586                                     left_gen == right_gen) {
5587                                         /*
5588                                          * As we're on a shared block, don't
5589                                          * allow to go deeper.
5590                                          */
5591                                         advance_left = ADVANCE_ONLY_NEXT;
5592                                         advance_right = ADVANCE_ONLY_NEXT;
5593                                 } else {
5594                                         advance_left = ADVANCE;
5595                                         advance_right = ADVANCE;
5596                                 }
5597                         }
5598                 } else if (left_level < right_level) {
5599                         advance_right = ADVANCE;
5600                 } else {
5601                         advance_left = ADVANCE;
5602                 }
5603         }
5604
5605 out:
5606         btrfs_free_path(left_path);
5607         btrfs_free_path(right_path);
5608         kvfree(tmp_buf);
5609         return ret;
5610 }
5611
5612 /*
5613  * this is similar to btrfs_next_leaf, but does not try to preserve
5614  * and fixup the path.  It looks for and returns the next key in the
5615  * tree based on the current path and the min_trans parameters.
5616  *
5617  * 0 is returned if another key is found, < 0 if there are any errors
5618  * and 1 is returned if there are no higher keys in the tree
5619  *
5620  * path->keep_locks should be set to 1 on the search made before
5621  * calling this function.
5622  */
5623 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
5624                         struct btrfs_key *key, int level, u64 min_trans)
5625 {
5626         int slot;
5627         struct extent_buffer *c;
5628
5629         WARN_ON(!path->keep_locks);
5630         while (level < BTRFS_MAX_LEVEL) {
5631                 if (!path->nodes[level])
5632                         return 1;
5633
5634                 slot = path->slots[level] + 1;
5635                 c = path->nodes[level];
5636 next:
5637                 if (slot >= btrfs_header_nritems(c)) {
5638                         int ret;
5639                         int orig_lowest;
5640                         struct btrfs_key cur_key;
5641                         if (level + 1 >= BTRFS_MAX_LEVEL ||
5642                             !path->nodes[level + 1])
5643                                 return 1;
5644
5645                         if (path->locks[level + 1]) {
5646                                 level++;
5647                                 continue;
5648                         }
5649
5650                         slot = btrfs_header_nritems(c) - 1;
5651                         if (level == 0)
5652                                 btrfs_item_key_to_cpu(c, &cur_key, slot);
5653                         else
5654                                 btrfs_node_key_to_cpu(c, &cur_key, slot);
5655
5656                         orig_lowest = path->lowest_level;
5657                         btrfs_release_path(path);
5658                         path->lowest_level = level;
5659                         ret = btrfs_search_slot(NULL, root, &cur_key, path,
5660                                                 0, 0);
5661                         path->lowest_level = orig_lowest;
5662                         if (ret < 0)
5663                                 return ret;
5664
5665                         c = path->nodes[level];
5666                         slot = path->slots[level];
5667                         if (ret == 0)
5668                                 slot++;
5669                         goto next;
5670                 }
5671
5672                 if (level == 0)
5673                         btrfs_item_key_to_cpu(c, key, slot);
5674                 else {
5675                         u64 gen = btrfs_node_ptr_generation(c, slot);
5676
5677                         if (gen < min_trans) {
5678                                 slot++;
5679                                 goto next;
5680                         }
5681                         btrfs_node_key_to_cpu(c, key, slot);
5682                 }
5683                 return 0;
5684         }
5685         return 1;
5686 }
5687
5688 /*
5689  * search the tree again to find a leaf with greater keys
5690  * returns 0 if it found something or 1 if there are no greater leaves.
5691  * returns < 0 on io errors.
5692  */
5693 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
5694 {
5695         return btrfs_next_old_leaf(root, path, 0);
5696 }
5697
5698 int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
5699                         u64 time_seq)
5700 {
5701         int slot;
5702         int level;
5703         struct extent_buffer *c;
5704         struct extent_buffer *next;
5705         struct btrfs_key key;
5706         u32 nritems;
5707         int ret;
5708         int old_spinning = path->leave_spinning;
5709         int next_rw_lock = 0;
5710
5711         nritems = btrfs_header_nritems(path->nodes[0]);
5712         if (nritems == 0)
5713                 return 1;
5714
5715         btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
5716 again:
5717         level = 1;
5718         next = NULL;
5719         next_rw_lock = 0;
5720         btrfs_release_path(path);
5721
5722         path->keep_locks = 1;
5723         path->leave_spinning = 1;
5724
5725         if (time_seq)
5726                 ret = btrfs_search_old_slot(root, &key, path, time_seq);
5727         else
5728                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5729         path->keep_locks = 0;
5730
5731         if (ret < 0)
5732                 return ret;
5733
5734         nritems = btrfs_header_nritems(path->nodes[0]);
5735         /*
5736          * by releasing the path above we dropped all our locks.  A balance
5737          * could have added more items next to the key that used to be
5738          * at the very end of the block.  So, check again here and
5739          * advance the path if there are now more items available.
5740          */
5741         if (nritems > 0 && path->slots[0] < nritems - 1) {
5742                 if (ret == 0)
5743                         path->slots[0]++;
5744                 ret = 0;
5745                 goto done;
5746         }
5747         /*
5748          * So the above check misses one case:
5749          * - after releasing the path above, someone has removed the item that
5750          *   used to be at the very end of the block, and balance between leafs
5751          *   gets another one with bigger key.offset to replace it.
5752          *
5753          * This one should be returned as well, or we can get leaf corruption
5754          * later(esp. in __btrfs_drop_extents()).
5755          *
5756          * And a bit more explanation about this check,
5757          * with ret > 0, the key isn't found, the path points to the slot
5758          * where it should be inserted, so the path->slots[0] item must be the
5759          * bigger one.
5760          */
5761         if (nritems > 0 && ret > 0 && path->slots[0] == nritems - 1) {
5762                 ret = 0;
5763                 goto done;
5764         }
5765
5766         while (level < BTRFS_MAX_LEVEL) {
5767                 if (!path->nodes[level]) {
5768                         ret = 1;
5769                         goto done;
5770                 }
5771
5772                 slot = path->slots[level] + 1;
5773                 c = path->nodes[level];
5774                 if (slot >= btrfs_header_nritems(c)) {
5775                         level++;
5776                         if (level == BTRFS_MAX_LEVEL) {
5777                                 ret = 1;
5778                                 goto done;
5779                         }
5780                         continue;
5781                 }
5782
5783                 if (next) {
5784                         btrfs_tree_unlock_rw(next, next_rw_lock);
5785                         free_extent_buffer(next);
5786                 }
5787
5788                 next = c;
5789                 next_rw_lock = path->locks[level];
5790                 ret = read_block_for_search(root, path, &next, level,
5791                                             slot, &key);
5792                 if (ret == -EAGAIN)
5793                         goto again;
5794
5795                 if (ret < 0) {
5796                         btrfs_release_path(path);
5797                         goto done;
5798                 }
5799
5800                 if (!path->skip_locking) {
5801                         ret = btrfs_try_tree_read_lock(next);
5802                         if (!ret && time_seq) {
5803                                 /*
5804                                  * If we don't get the lock, we may be racing
5805                                  * with push_leaf_left, holding that lock while
5806                                  * itself waiting for the leaf we've currently
5807                                  * locked. To solve this situation, we give up
5808                                  * on our lock and cycle.
5809                                  */
5810                                 free_extent_buffer(next);
5811                                 btrfs_release_path(path);
5812                                 cond_resched();
5813                                 goto again;
5814                         }
5815                         if (!ret) {
5816                                 btrfs_set_path_blocking(path);
5817                                 btrfs_tree_read_lock(next);
5818                         }
5819                         next_rw_lock = BTRFS_READ_LOCK;
5820                 }
5821                 break;
5822         }
5823         path->slots[level] = slot;
5824         while (1) {
5825                 level--;
5826                 c = path->nodes[level];
5827                 if (path->locks[level])
5828                         btrfs_tree_unlock_rw(c, path->locks[level]);
5829
5830                 free_extent_buffer(c);
5831                 path->nodes[level] = next;
5832                 path->slots[level] = 0;
5833                 if (!path->skip_locking)
5834                         path->locks[level] = next_rw_lock;
5835                 if (!level)
5836                         break;
5837
5838                 ret = read_block_for_search(root, path, &next, level,
5839                                             0, &key);
5840                 if (ret == -EAGAIN)
5841                         goto again;
5842
5843                 if (ret < 0) {
5844                         btrfs_release_path(path);
5845                         goto done;
5846                 }
5847
5848                 if (!path->skip_locking) {
5849                         ret = btrfs_try_tree_read_lock(next);
5850                         if (!ret) {
5851                                 btrfs_set_path_blocking(path);
5852                                 btrfs_tree_read_lock(next);
5853                         }
5854                         next_rw_lock = BTRFS_READ_LOCK;
5855                 }
5856         }
5857         ret = 0;
5858 done:
5859         unlock_up(path, 0, 1, 0, NULL);
5860         path->leave_spinning = old_spinning;
5861         if (!old_spinning)
5862                 btrfs_set_path_blocking(path);
5863
5864         return ret;
5865 }
5866
5867 /*
5868  * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
5869  * searching until it gets past min_objectid or finds an item of 'type'
5870  *
5871  * returns 0 if something is found, 1 if nothing was found and < 0 on error
5872  */
5873 int btrfs_previous_item(struct btrfs_root *root,
5874                         struct btrfs_path *path, u64 min_objectid,
5875                         int type)
5876 {
5877         struct btrfs_key found_key;
5878         struct extent_buffer *leaf;
5879         u32 nritems;
5880         int ret;
5881
5882         while (1) {
5883                 if (path->slots[0] == 0) {
5884                         btrfs_set_path_blocking(path);
5885                         ret = btrfs_prev_leaf(root, path);
5886                         if (ret != 0)
5887                                 return ret;
5888                 } else {
5889                         path->slots[0]--;
5890                 }
5891                 leaf = path->nodes[0];
5892                 nritems = btrfs_header_nritems(leaf);
5893                 if (nritems == 0)
5894                         return 1;
5895                 if (path->slots[0] == nritems)
5896                         path->slots[0]--;
5897
5898                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5899                 if (found_key.objectid < min_objectid)
5900                         break;
5901                 if (found_key.type == type)
5902                         return 0;
5903                 if (found_key.objectid == min_objectid &&
5904                     found_key.type < type)
5905                         break;
5906         }
5907         return 1;
5908 }
5909
5910 /*
5911  * search in extent tree to find a previous Metadata/Data extent item with
5912  * min objecitd.
5913  *
5914  * returns 0 if something is found, 1 if nothing was found and < 0 on error
5915  */
5916 int btrfs_previous_extent_item(struct btrfs_root *root,
5917                         struct btrfs_path *path, u64 min_objectid)
5918 {
5919         struct btrfs_key found_key;
5920         struct extent_buffer *leaf;
5921         u32 nritems;
5922         int ret;
5923
5924         while (1) {
5925                 if (path->slots[0] == 0) {
5926                         btrfs_set_path_blocking(path);
5927                         ret = btrfs_prev_leaf(root, path);
5928                         if (ret != 0)
5929                                 return ret;
5930                 } else {
5931                         path->slots[0]--;
5932                 }
5933                 leaf = path->nodes[0];
5934                 nritems = btrfs_header_nritems(leaf);
5935                 if (nritems == 0)
5936                         return 1;
5937                 if (path->slots[0] == nritems)
5938                         path->slots[0]--;
5939
5940                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5941                 if (found_key.objectid < min_objectid)
5942                         break;
5943                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
5944                     found_key.type == BTRFS_METADATA_ITEM_KEY)
5945                         return 0;
5946                 if (found_key.objectid == min_objectid &&
5947                     found_key.type < BTRFS_EXTENT_ITEM_KEY)
5948                         break;
5949         }
5950         return 1;
5951 }