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