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