fs/btrfs/ctree.c

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