xref: /openbmc/linux/fs/btrfs/ctree.c (revision 3fd0a558)
16cbd5570SChris Mason /*
2d352ac68SChris Mason  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
36cbd5570SChris Mason  *
46cbd5570SChris Mason  * This program is free software; you can redistribute it and/or
56cbd5570SChris Mason  * modify it under the terms of the GNU General Public
66cbd5570SChris Mason  * License v2 as published by the Free Software Foundation.
76cbd5570SChris Mason  *
86cbd5570SChris Mason  * This program is distributed in the hope that it will be useful,
96cbd5570SChris Mason  * but WITHOUT ANY WARRANTY; without even the implied warranty of
106cbd5570SChris Mason  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
116cbd5570SChris Mason  * General Public License for more details.
126cbd5570SChris Mason  *
136cbd5570SChris Mason  * You should have received a copy of the GNU General Public
146cbd5570SChris Mason  * License along with this program; if not, write to the
156cbd5570SChris Mason  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
166cbd5570SChris Mason  * Boston, MA 021110-1307, USA.
176cbd5570SChris Mason  */
186cbd5570SChris Mason 
19a6b6e75eSChris Mason #include <linux/sched.h>
205a0e3ad6STejun Heo #include <linux/slab.h>
21eb60ceacSChris Mason #include "ctree.h"
22eb60ceacSChris Mason #include "disk-io.h"
237f5c1516SChris Mason #include "transaction.h"
245f39d397SChris Mason #include "print-tree.h"
25925baeddSChris Mason #include "locking.h"
269a8dd150SChris Mason 
27e089f05cSChris Mason static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
28e089f05cSChris Mason 		      *root, struct btrfs_path *path, int level);
29e089f05cSChris Mason static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
30d4dbff95SChris Mason 		      *root, struct btrfs_key *ins_key,
31cc0c5538SChris Mason 		      struct btrfs_path *path, int data_size, int extend);
325f39d397SChris Mason static int push_node_left(struct btrfs_trans_handle *trans,
335f39d397SChris Mason 			  struct btrfs_root *root, struct extent_buffer *dst,
34971a1f66SChris Mason 			  struct extent_buffer *src, int empty);
355f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans,
365f39d397SChris Mason 			      struct btrfs_root *root,
375f39d397SChris Mason 			      struct extent_buffer *dst_buf,
385f39d397SChris Mason 			      struct extent_buffer *src_buf);
39e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
40e089f05cSChris Mason 		   struct btrfs_path *path, int level, int slot);
41ad48fd75SYan, Zheng static int setup_items_for_insert(struct btrfs_trans_handle *trans,
42ad48fd75SYan, Zheng 			struct btrfs_root *root, struct btrfs_path *path,
43ad48fd75SYan, Zheng 			struct btrfs_key *cpu_key, u32 *data_size,
44ad48fd75SYan, Zheng 			u32 total_data, u32 total_size, int nr);
45ad48fd75SYan, Zheng 
46d97e63b6SChris Mason 
472c90e5d6SChris Mason struct btrfs_path *btrfs_alloc_path(void)
482c90e5d6SChris Mason {
49df24a2b9SChris Mason 	struct btrfs_path *path;
50e00f7308SJeff Mahoney 	path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
51e00f7308SJeff Mahoney 	if (path)
522cc58cf2SChris Mason 		path->reada = 1;
53df24a2b9SChris Mason 	return path;
542c90e5d6SChris Mason }
552c90e5d6SChris Mason 
56b4ce94deSChris Mason /*
57b4ce94deSChris Mason  * set all locked nodes in the path to blocking locks.  This should
58b4ce94deSChris Mason  * be done before scheduling
59b4ce94deSChris Mason  */
60b4ce94deSChris Mason noinline void btrfs_set_path_blocking(struct btrfs_path *p)
61b4ce94deSChris Mason {
62b4ce94deSChris Mason 	int i;
63b4ce94deSChris Mason 	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
64b4ce94deSChris Mason 		if (p->nodes[i] && p->locks[i])
65b4ce94deSChris Mason 			btrfs_set_lock_blocking(p->nodes[i]);
66b4ce94deSChris Mason 	}
67b4ce94deSChris Mason }
68b4ce94deSChris Mason 
69b4ce94deSChris Mason /*
70b4ce94deSChris Mason  * reset all the locked nodes in the patch to spinning locks.
714008c04aSChris Mason  *
724008c04aSChris Mason  * held is used to keep lockdep happy, when lockdep is enabled
734008c04aSChris Mason  * we set held to a blocking lock before we go around and
744008c04aSChris Mason  * retake all the spinlocks in the path.  You can safely use NULL
754008c04aSChris Mason  * for held
76b4ce94deSChris Mason  */
774008c04aSChris Mason noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
784008c04aSChris Mason 					struct extent_buffer *held)
79b4ce94deSChris Mason {
80b4ce94deSChris Mason 	int i;
814008c04aSChris Mason 
824008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC
834008c04aSChris Mason 	/* lockdep really cares that we take all of these spinlocks
844008c04aSChris Mason 	 * in the right order.  If any of the locks in the path are not
854008c04aSChris Mason 	 * currently blocking, it is going to complain.  So, make really
864008c04aSChris Mason 	 * really sure by forcing the path to blocking before we clear
874008c04aSChris Mason 	 * the path blocking.
884008c04aSChris Mason 	 */
894008c04aSChris Mason 	if (held)
904008c04aSChris Mason 		btrfs_set_lock_blocking(held);
914008c04aSChris Mason 	btrfs_set_path_blocking(p);
924008c04aSChris Mason #endif
934008c04aSChris Mason 
944008c04aSChris Mason 	for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
95b4ce94deSChris Mason 		if (p->nodes[i] && p->locks[i])
96b4ce94deSChris Mason 			btrfs_clear_lock_blocking(p->nodes[i]);
97b4ce94deSChris Mason 	}
984008c04aSChris Mason 
994008c04aSChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC
1004008c04aSChris Mason 	if (held)
1014008c04aSChris Mason 		btrfs_clear_lock_blocking(held);
1024008c04aSChris Mason #endif
103b4ce94deSChris Mason }
104b4ce94deSChris Mason 
105d352ac68SChris Mason /* this also releases the path */
1062c90e5d6SChris Mason void btrfs_free_path(struct btrfs_path *p)
1072c90e5d6SChris Mason {
108df24a2b9SChris Mason 	btrfs_release_path(NULL, p);
1092c90e5d6SChris Mason 	kmem_cache_free(btrfs_path_cachep, p);
1102c90e5d6SChris Mason }
1112c90e5d6SChris Mason 
112d352ac68SChris Mason /*
113d352ac68SChris Mason  * path release drops references on the extent buffers in the path
114d352ac68SChris Mason  * and it drops any locks held by this path
115d352ac68SChris Mason  *
116d352ac68SChris Mason  * It is safe to call this on paths that no locks or extent buffers held.
117d352ac68SChris Mason  */
118d397712bSChris Mason noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
119eb60ceacSChris Mason {
120eb60ceacSChris Mason 	int i;
121a2135011SChris Mason 
122234b63a0SChris Mason 	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
1233f157a2fSChris Mason 		p->slots[i] = 0;
124eb60ceacSChris Mason 		if (!p->nodes[i])
125925baeddSChris Mason 			continue;
126925baeddSChris Mason 		if (p->locks[i]) {
127925baeddSChris Mason 			btrfs_tree_unlock(p->nodes[i]);
128925baeddSChris Mason 			p->locks[i] = 0;
129925baeddSChris Mason 		}
1305f39d397SChris Mason 		free_extent_buffer(p->nodes[i]);
1313f157a2fSChris Mason 		p->nodes[i] = NULL;
132eb60ceacSChris Mason 	}
133eb60ceacSChris Mason }
134eb60ceacSChris Mason 
135d352ac68SChris Mason /*
136d352ac68SChris Mason  * safely gets a reference on the root node of a tree.  A lock
137d352ac68SChris Mason  * is not taken, so a concurrent writer may put a different node
138d352ac68SChris Mason  * at the root of the tree.  See btrfs_lock_root_node for the
139d352ac68SChris Mason  * looping required.
140d352ac68SChris Mason  *
141d352ac68SChris Mason  * The extent buffer returned by this has a reference taken, so
142d352ac68SChris Mason  * it won't disappear.  It may stop being the root of the tree
143d352ac68SChris Mason  * at any time because there are no locks held.
144d352ac68SChris Mason  */
145925baeddSChris Mason struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
146925baeddSChris Mason {
147925baeddSChris Mason 	struct extent_buffer *eb;
148925baeddSChris Mason 	spin_lock(&root->node_lock);
149925baeddSChris Mason 	eb = root->node;
150925baeddSChris Mason 	extent_buffer_get(eb);
151925baeddSChris Mason 	spin_unlock(&root->node_lock);
152925baeddSChris Mason 	return eb;
153925baeddSChris Mason }
154925baeddSChris Mason 
155d352ac68SChris Mason /* loop around taking references on and locking the root node of the
156d352ac68SChris Mason  * tree until you end up with a lock on the root.  A locked buffer
157d352ac68SChris Mason  * is returned, with a reference held.
158d352ac68SChris Mason  */
159925baeddSChris Mason struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
160925baeddSChris Mason {
161925baeddSChris Mason 	struct extent_buffer *eb;
162925baeddSChris Mason 
163925baeddSChris Mason 	while (1) {
164925baeddSChris Mason 		eb = btrfs_root_node(root);
165925baeddSChris Mason 		btrfs_tree_lock(eb);
166925baeddSChris Mason 
167925baeddSChris Mason 		spin_lock(&root->node_lock);
168925baeddSChris Mason 		if (eb == root->node) {
169925baeddSChris Mason 			spin_unlock(&root->node_lock);
170925baeddSChris Mason 			break;
171925baeddSChris Mason 		}
172925baeddSChris Mason 		spin_unlock(&root->node_lock);
173925baeddSChris Mason 
174925baeddSChris Mason 		btrfs_tree_unlock(eb);
175925baeddSChris Mason 		free_extent_buffer(eb);
176925baeddSChris Mason 	}
177925baeddSChris Mason 	return eb;
178925baeddSChris Mason }
179925baeddSChris Mason 
180d352ac68SChris Mason /* cowonly root (everything not a reference counted cow subvolume), just get
181d352ac68SChris Mason  * put onto a simple dirty list.  transaction.c walks this to make sure they
182d352ac68SChris Mason  * get properly updated on disk.
183d352ac68SChris Mason  */
1840b86a832SChris Mason static void add_root_to_dirty_list(struct btrfs_root *root)
1850b86a832SChris Mason {
1860b86a832SChris Mason 	if (root->track_dirty && list_empty(&root->dirty_list)) {
1870b86a832SChris Mason 		list_add(&root->dirty_list,
1880b86a832SChris Mason 			 &root->fs_info->dirty_cowonly_roots);
1890b86a832SChris Mason 	}
1900b86a832SChris Mason }
1910b86a832SChris Mason 
192d352ac68SChris Mason /*
193d352ac68SChris Mason  * used by snapshot creation to make a copy of a root for a tree with
194d352ac68SChris Mason  * a given objectid.  The buffer with the new root node is returned in
195d352ac68SChris Mason  * cow_ret, and this func returns zero on success or a negative error code.
196d352ac68SChris Mason  */
197be20aa9dSChris Mason int btrfs_copy_root(struct btrfs_trans_handle *trans,
198be20aa9dSChris Mason 		      struct btrfs_root *root,
199be20aa9dSChris Mason 		      struct extent_buffer *buf,
200be20aa9dSChris Mason 		      struct extent_buffer **cow_ret, u64 new_root_objectid)
201be20aa9dSChris Mason {
202be20aa9dSChris Mason 	struct extent_buffer *cow;
203be20aa9dSChris Mason 	u32 nritems;
204be20aa9dSChris Mason 	int ret = 0;
205be20aa9dSChris Mason 	int level;
2065d4f98a2SYan Zheng 	struct btrfs_disk_key disk_key;
207be20aa9dSChris Mason 
208be20aa9dSChris Mason 	WARN_ON(root->ref_cows && trans->transid !=
209be20aa9dSChris Mason 		root->fs_info->running_transaction->transid);
210be20aa9dSChris Mason 	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
211be20aa9dSChris Mason 
212be20aa9dSChris Mason 	level = btrfs_header_level(buf);
213be20aa9dSChris Mason 	nritems = btrfs_header_nritems(buf);
2145d4f98a2SYan Zheng 	if (level == 0)
2155d4f98a2SYan Zheng 		btrfs_item_key(buf, &disk_key, 0);
2165d4f98a2SYan Zheng 	else
2175d4f98a2SYan Zheng 		btrfs_node_key(buf, &disk_key, 0);
21831840ae1SZheng Yan 
2195d4f98a2SYan Zheng 	cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
2205d4f98a2SYan Zheng 				     new_root_objectid, &disk_key, level,
2215d4f98a2SYan Zheng 				     buf->start, 0);
2225d4f98a2SYan Zheng 	if (IS_ERR(cow))
223be20aa9dSChris Mason 		return PTR_ERR(cow);
224be20aa9dSChris Mason 
225be20aa9dSChris Mason 	copy_extent_buffer(cow, buf, 0, 0, cow->len);
226be20aa9dSChris Mason 	btrfs_set_header_bytenr(cow, cow->start);
227be20aa9dSChris Mason 	btrfs_set_header_generation(cow, trans->transid);
2285d4f98a2SYan Zheng 	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
2295d4f98a2SYan Zheng 	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
2305d4f98a2SYan Zheng 				     BTRFS_HEADER_FLAG_RELOC);
2315d4f98a2SYan Zheng 	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
2325d4f98a2SYan Zheng 		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
2335d4f98a2SYan Zheng 	else
234be20aa9dSChris Mason 		btrfs_set_header_owner(cow, new_root_objectid);
235be20aa9dSChris Mason 
2362b82032cSYan Zheng 	write_extent_buffer(cow, root->fs_info->fsid,
2372b82032cSYan Zheng 			    (unsigned long)btrfs_header_fsid(cow),
2382b82032cSYan Zheng 			    BTRFS_FSID_SIZE);
2392b82032cSYan Zheng 
240be20aa9dSChris Mason 	WARN_ON(btrfs_header_generation(buf) > trans->transid);
2415d4f98a2SYan Zheng 	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
2425d4f98a2SYan Zheng 		ret = btrfs_inc_ref(trans, root, cow, 1);
2435d4f98a2SYan Zheng 	else
2445d4f98a2SYan Zheng 		ret = btrfs_inc_ref(trans, root, cow, 0);
2454aec2b52SChris Mason 
246be20aa9dSChris Mason 	if (ret)
247be20aa9dSChris Mason 		return ret;
248be20aa9dSChris Mason 
249be20aa9dSChris Mason 	btrfs_mark_buffer_dirty(cow);
250be20aa9dSChris Mason 	*cow_ret = cow;
251be20aa9dSChris Mason 	return 0;
252be20aa9dSChris Mason }
253be20aa9dSChris Mason 
254d352ac68SChris Mason /*
2555d4f98a2SYan Zheng  * check if the tree block can be shared by multiple trees
2565d4f98a2SYan Zheng  */
2575d4f98a2SYan Zheng int btrfs_block_can_be_shared(struct btrfs_root *root,
2585d4f98a2SYan Zheng 			      struct extent_buffer *buf)
2595d4f98a2SYan Zheng {
2605d4f98a2SYan Zheng 	/*
2615d4f98a2SYan Zheng 	 * Tree blocks not in refernece counted trees and tree roots
2625d4f98a2SYan Zheng 	 * are never shared. If a block was allocated after the last
2635d4f98a2SYan Zheng 	 * snapshot and the block was not allocated by tree relocation,
2645d4f98a2SYan Zheng 	 * we know the block is not shared.
2655d4f98a2SYan Zheng 	 */
2665d4f98a2SYan Zheng 	if (root->ref_cows &&
2675d4f98a2SYan Zheng 	    buf != root->node && buf != root->commit_root &&
2685d4f98a2SYan Zheng 	    (btrfs_header_generation(buf) <=
2695d4f98a2SYan Zheng 	     btrfs_root_last_snapshot(&root->root_item) ||
2705d4f98a2SYan Zheng 	     btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
2715d4f98a2SYan Zheng 		return 1;
2725d4f98a2SYan Zheng #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2735d4f98a2SYan Zheng 	if (root->ref_cows &&
2745d4f98a2SYan Zheng 	    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2755d4f98a2SYan Zheng 		return 1;
2765d4f98a2SYan Zheng #endif
2775d4f98a2SYan Zheng 	return 0;
2785d4f98a2SYan Zheng }
2795d4f98a2SYan Zheng 
2805d4f98a2SYan Zheng static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
2815d4f98a2SYan Zheng 				       struct btrfs_root *root,
2825d4f98a2SYan Zheng 				       struct extent_buffer *buf,
283f0486c68SYan, Zheng 				       struct extent_buffer *cow,
284f0486c68SYan, Zheng 				       int *last_ref)
2855d4f98a2SYan Zheng {
2865d4f98a2SYan Zheng 	u64 refs;
2875d4f98a2SYan Zheng 	u64 owner;
2885d4f98a2SYan Zheng 	u64 flags;
2895d4f98a2SYan Zheng 	u64 new_flags = 0;
2905d4f98a2SYan Zheng 	int ret;
2915d4f98a2SYan Zheng 
2925d4f98a2SYan Zheng 	/*
2935d4f98a2SYan Zheng 	 * Backrefs update rules:
2945d4f98a2SYan Zheng 	 *
2955d4f98a2SYan Zheng 	 * Always use full backrefs for extent pointers in tree block
2965d4f98a2SYan Zheng 	 * allocated by tree relocation.
2975d4f98a2SYan Zheng 	 *
2985d4f98a2SYan Zheng 	 * If a shared tree block is no longer referenced by its owner
2995d4f98a2SYan Zheng 	 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
3005d4f98a2SYan Zheng 	 * use full backrefs for extent pointers in tree block.
3015d4f98a2SYan Zheng 	 *
3025d4f98a2SYan Zheng 	 * If a tree block is been relocating
3035d4f98a2SYan Zheng 	 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
3045d4f98a2SYan Zheng 	 * use full backrefs for extent pointers in tree block.
3055d4f98a2SYan Zheng 	 * The reason for this is some operations (such as drop tree)
3065d4f98a2SYan Zheng 	 * are only allowed for blocks use full backrefs.
3075d4f98a2SYan Zheng 	 */
3085d4f98a2SYan Zheng 
3095d4f98a2SYan Zheng 	if (btrfs_block_can_be_shared(root, buf)) {
3105d4f98a2SYan Zheng 		ret = btrfs_lookup_extent_info(trans, root, buf->start,
3115d4f98a2SYan Zheng 					       buf->len, &refs, &flags);
3125d4f98a2SYan Zheng 		BUG_ON(ret);
3135d4f98a2SYan Zheng 		BUG_ON(refs == 0);
3145d4f98a2SYan Zheng 	} else {
3155d4f98a2SYan Zheng 		refs = 1;
3165d4f98a2SYan Zheng 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
3175d4f98a2SYan Zheng 		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
3185d4f98a2SYan Zheng 			flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
3195d4f98a2SYan Zheng 		else
3205d4f98a2SYan Zheng 			flags = 0;
3215d4f98a2SYan Zheng 	}
3225d4f98a2SYan Zheng 
3235d4f98a2SYan Zheng 	owner = btrfs_header_owner(buf);
3245d4f98a2SYan Zheng 	BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
3255d4f98a2SYan Zheng 	       !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
3265d4f98a2SYan Zheng 
3275d4f98a2SYan Zheng 	if (refs > 1) {
3285d4f98a2SYan Zheng 		if ((owner == root->root_key.objectid ||
3295d4f98a2SYan Zheng 		     root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
3305d4f98a2SYan Zheng 		    !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
3315d4f98a2SYan Zheng 			ret = btrfs_inc_ref(trans, root, buf, 1);
3325d4f98a2SYan Zheng 			BUG_ON(ret);
3335d4f98a2SYan Zheng 
3345d4f98a2SYan Zheng 			if (root->root_key.objectid ==
3355d4f98a2SYan Zheng 			    BTRFS_TREE_RELOC_OBJECTID) {
3365d4f98a2SYan Zheng 				ret = btrfs_dec_ref(trans, root, buf, 0);
3375d4f98a2SYan Zheng 				BUG_ON(ret);
3385d4f98a2SYan Zheng 				ret = btrfs_inc_ref(trans, root, cow, 1);
3395d4f98a2SYan Zheng 				BUG_ON(ret);
3405d4f98a2SYan Zheng 			}
3415d4f98a2SYan Zheng 			new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
3425d4f98a2SYan Zheng 		} else {
3435d4f98a2SYan Zheng 
3445d4f98a2SYan Zheng 			if (root->root_key.objectid ==
3455d4f98a2SYan Zheng 			    BTRFS_TREE_RELOC_OBJECTID)
3465d4f98a2SYan Zheng 				ret = btrfs_inc_ref(trans, root, cow, 1);
3475d4f98a2SYan Zheng 			else
3485d4f98a2SYan Zheng 				ret = btrfs_inc_ref(trans, root, cow, 0);
3495d4f98a2SYan Zheng 			BUG_ON(ret);
3505d4f98a2SYan Zheng 		}
3515d4f98a2SYan Zheng 		if (new_flags != 0) {
3525d4f98a2SYan Zheng 			ret = btrfs_set_disk_extent_flags(trans, root,
3535d4f98a2SYan Zheng 							  buf->start,
3545d4f98a2SYan Zheng 							  buf->len,
3555d4f98a2SYan Zheng 							  new_flags, 0);
3565d4f98a2SYan Zheng 			BUG_ON(ret);
3575d4f98a2SYan Zheng 		}
3585d4f98a2SYan Zheng 	} else {
3595d4f98a2SYan Zheng 		if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
3605d4f98a2SYan Zheng 			if (root->root_key.objectid ==
3615d4f98a2SYan Zheng 			    BTRFS_TREE_RELOC_OBJECTID)
3625d4f98a2SYan Zheng 				ret = btrfs_inc_ref(trans, root, cow, 1);
3635d4f98a2SYan Zheng 			else
3645d4f98a2SYan Zheng 				ret = btrfs_inc_ref(trans, root, cow, 0);
3655d4f98a2SYan Zheng 			BUG_ON(ret);
3665d4f98a2SYan Zheng 			ret = btrfs_dec_ref(trans, root, buf, 1);
3675d4f98a2SYan Zheng 			BUG_ON(ret);
3685d4f98a2SYan Zheng 		}
3695d4f98a2SYan Zheng 		clean_tree_block(trans, root, buf);
370f0486c68SYan, Zheng 		*last_ref = 1;
3715d4f98a2SYan Zheng 	}
3725d4f98a2SYan Zheng 	return 0;
3735d4f98a2SYan Zheng }
3745d4f98a2SYan Zheng 
3755d4f98a2SYan Zheng /*
376d397712bSChris Mason  * does the dirty work in cow of a single block.  The parent block (if
377d397712bSChris Mason  * supplied) is updated to point to the new cow copy.  The new buffer is marked
378d397712bSChris Mason  * dirty and returned locked.  If you modify the block it needs to be marked
379d397712bSChris Mason  * dirty again.
380d352ac68SChris Mason  *
381d352ac68SChris Mason  * search_start -- an allocation hint for the new block
382d352ac68SChris Mason  *
383d397712bSChris Mason  * empty_size -- a hint that you plan on doing more cow.  This is the size in
384d397712bSChris Mason  * bytes the allocator should try to find free next to the block it returns.
385d397712bSChris Mason  * This is just a hint and may be ignored by the allocator.
386d352ac68SChris Mason  */
387d397712bSChris Mason static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
3885f39d397SChris Mason 			     struct btrfs_root *root,
3895f39d397SChris Mason 			     struct extent_buffer *buf,
3905f39d397SChris Mason 			     struct extent_buffer *parent, int parent_slot,
3915f39d397SChris Mason 			     struct extent_buffer **cow_ret,
3929fa8cfe7SChris Mason 			     u64 search_start, u64 empty_size)
3936702ed49SChris Mason {
3945d4f98a2SYan Zheng 	struct btrfs_disk_key disk_key;
3955f39d397SChris Mason 	struct extent_buffer *cow;
3967bb86316SChris Mason 	int level;
397f0486c68SYan, Zheng 	int last_ref = 0;
398925baeddSChris Mason 	int unlock_orig = 0;
3995d4f98a2SYan Zheng 	u64 parent_start;
4006702ed49SChris Mason 
401925baeddSChris Mason 	if (*cow_ret == buf)
402925baeddSChris Mason 		unlock_orig = 1;
403925baeddSChris Mason 
404b9447ef8SChris Mason 	btrfs_assert_tree_locked(buf);
405925baeddSChris Mason 
4067bb86316SChris Mason 	WARN_ON(root->ref_cows && trans->transid !=
4077bb86316SChris Mason 		root->fs_info->running_transaction->transid);
4086702ed49SChris Mason 	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
4095f39d397SChris Mason 
4107bb86316SChris Mason 	level = btrfs_header_level(buf);
41131840ae1SZheng Yan 
4125d4f98a2SYan Zheng 	if (level == 0)
4135d4f98a2SYan Zheng 		btrfs_item_key(buf, &disk_key, 0);
4145d4f98a2SYan Zheng 	else
4155d4f98a2SYan Zheng 		btrfs_node_key(buf, &disk_key, 0);
4165d4f98a2SYan Zheng 
4175d4f98a2SYan Zheng 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
4185d4f98a2SYan Zheng 		if (parent)
4195d4f98a2SYan Zheng 			parent_start = parent->start;
4205d4f98a2SYan Zheng 		else
4215d4f98a2SYan Zheng 			parent_start = 0;
4225d4f98a2SYan Zheng 	} else
4235d4f98a2SYan Zheng 		parent_start = 0;
4245d4f98a2SYan Zheng 
4255d4f98a2SYan Zheng 	cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
4265d4f98a2SYan Zheng 				     root->root_key.objectid, &disk_key,
4275d4f98a2SYan Zheng 				     level, search_start, empty_size);
4286702ed49SChris Mason 	if (IS_ERR(cow))
4296702ed49SChris Mason 		return PTR_ERR(cow);
4306702ed49SChris Mason 
431b4ce94deSChris Mason 	/* cow is set to blocking by btrfs_init_new_buffer */
432b4ce94deSChris Mason 
4335f39d397SChris Mason 	copy_extent_buffer(cow, buf, 0, 0, cow->len);
434db94535dSChris Mason 	btrfs_set_header_bytenr(cow, cow->start);
4355f39d397SChris Mason 	btrfs_set_header_generation(cow, trans->transid);
4365d4f98a2SYan Zheng 	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
4375d4f98a2SYan Zheng 	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
4385d4f98a2SYan Zheng 				     BTRFS_HEADER_FLAG_RELOC);
4395d4f98a2SYan Zheng 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4405d4f98a2SYan Zheng 		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
4415d4f98a2SYan Zheng 	else
4425f39d397SChris Mason 		btrfs_set_header_owner(cow, root->root_key.objectid);
4436702ed49SChris Mason 
4442b82032cSYan Zheng 	write_extent_buffer(cow, root->fs_info->fsid,
4452b82032cSYan Zheng 			    (unsigned long)btrfs_header_fsid(cow),
4462b82032cSYan Zheng 			    BTRFS_FSID_SIZE);
4472b82032cSYan Zheng 
448f0486c68SYan, Zheng 	update_ref_for_cow(trans, root, buf, cow, &last_ref);
4491a40e23bSZheng Yan 
4503fd0a558SYan, Zheng 	if (root->ref_cows)
4513fd0a558SYan, Zheng 		btrfs_reloc_cow_block(trans, root, buf, cow);
4523fd0a558SYan, Zheng 
4536702ed49SChris Mason 	if (buf == root->node) {
454925baeddSChris Mason 		WARN_ON(parent && parent != buf);
4555d4f98a2SYan Zheng 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
4565d4f98a2SYan Zheng 		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
4575d4f98a2SYan Zheng 			parent_start = buf->start;
4585d4f98a2SYan Zheng 		else
4595d4f98a2SYan Zheng 			parent_start = 0;
460925baeddSChris Mason 
461925baeddSChris Mason 		spin_lock(&root->node_lock);
4626702ed49SChris Mason 		root->node = cow;
4635f39d397SChris Mason 		extent_buffer_get(cow);
464925baeddSChris Mason 		spin_unlock(&root->node_lock);
465925baeddSChris Mason 
466f0486c68SYan, Zheng 		btrfs_free_tree_block(trans, root, buf, parent_start,
467f0486c68SYan, Zheng 				      last_ref);
4685f39d397SChris Mason 		free_extent_buffer(buf);
4690b86a832SChris Mason 		add_root_to_dirty_list(root);
4706702ed49SChris Mason 	} else {
4715d4f98a2SYan Zheng 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
4725d4f98a2SYan Zheng 			parent_start = parent->start;
4735d4f98a2SYan Zheng 		else
4745d4f98a2SYan Zheng 			parent_start = 0;
4755d4f98a2SYan Zheng 
4765d4f98a2SYan Zheng 		WARN_ON(trans->transid != btrfs_header_generation(parent));
4775f39d397SChris Mason 		btrfs_set_node_blockptr(parent, parent_slot,
478db94535dSChris Mason 					cow->start);
47974493f7aSChris Mason 		btrfs_set_node_ptr_generation(parent, parent_slot,
48074493f7aSChris Mason 					      trans->transid);
4816702ed49SChris Mason 		btrfs_mark_buffer_dirty(parent);
482f0486c68SYan, Zheng 		btrfs_free_tree_block(trans, root, buf, parent_start,
483f0486c68SYan, Zheng 				      last_ref);
4846702ed49SChris Mason 	}
485925baeddSChris Mason 	if (unlock_orig)
486925baeddSChris Mason 		btrfs_tree_unlock(buf);
4875f39d397SChris Mason 	free_extent_buffer(buf);
4886702ed49SChris Mason 	btrfs_mark_buffer_dirty(cow);
4896702ed49SChris Mason 	*cow_ret = cow;
4906702ed49SChris Mason 	return 0;
4916702ed49SChris Mason }
4926702ed49SChris Mason 
4935d4f98a2SYan Zheng static inline int should_cow_block(struct btrfs_trans_handle *trans,
4945d4f98a2SYan Zheng 				   struct btrfs_root *root,
4955d4f98a2SYan Zheng 				   struct extent_buffer *buf)
4965d4f98a2SYan Zheng {
4975d4f98a2SYan Zheng 	if (btrfs_header_generation(buf) == trans->transid &&
4985d4f98a2SYan Zheng 	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
4995d4f98a2SYan Zheng 	    !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
5005d4f98a2SYan Zheng 	      btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
5015d4f98a2SYan Zheng 		return 0;
5025d4f98a2SYan Zheng 	return 1;
5035d4f98a2SYan Zheng }
5045d4f98a2SYan Zheng 
505d352ac68SChris Mason /*
506d352ac68SChris Mason  * cows a single block, see __btrfs_cow_block for the real work.
507d352ac68SChris Mason  * This version of it has extra checks so that a block isn't cow'd more than
508d352ac68SChris Mason  * once per transaction, as long as it hasn't been written yet
509d352ac68SChris Mason  */
510d397712bSChris Mason noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
5115f39d397SChris Mason 		    struct btrfs_root *root, struct extent_buffer *buf,
5125f39d397SChris Mason 		    struct extent_buffer *parent, int parent_slot,
5139fa8cfe7SChris Mason 		    struct extent_buffer **cow_ret)
51402217ed2SChris Mason {
5156702ed49SChris Mason 	u64 search_start;
516f510cfecSChris Mason 	int ret;
517dc17ff8fSChris Mason 
518ccd467d6SChris Mason 	if (trans->transaction != root->fs_info->running_transaction) {
519d397712bSChris Mason 		printk(KERN_CRIT "trans %llu running %llu\n",
520d397712bSChris Mason 		       (unsigned long long)trans->transid,
521d397712bSChris Mason 		       (unsigned long long)
522ccd467d6SChris Mason 		       root->fs_info->running_transaction->transid);
523ccd467d6SChris Mason 		WARN_ON(1);
524ccd467d6SChris Mason 	}
525ccd467d6SChris Mason 	if (trans->transid != root->fs_info->generation) {
526d397712bSChris Mason 		printk(KERN_CRIT "trans %llu running %llu\n",
527d397712bSChris Mason 		       (unsigned long long)trans->transid,
528d397712bSChris Mason 		       (unsigned long long)root->fs_info->generation);
529ccd467d6SChris Mason 		WARN_ON(1);
530ccd467d6SChris Mason 	}
531dc17ff8fSChris Mason 
5325d4f98a2SYan Zheng 	if (!should_cow_block(trans, root, buf)) {
53302217ed2SChris Mason 		*cow_ret = buf;
53402217ed2SChris Mason 		return 0;
53502217ed2SChris Mason 	}
536c487685dSChris Mason 
5370b86a832SChris Mason 	search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
538b4ce94deSChris Mason 
539b4ce94deSChris Mason 	if (parent)
540b4ce94deSChris Mason 		btrfs_set_lock_blocking(parent);
541b4ce94deSChris Mason 	btrfs_set_lock_blocking(buf);
542b4ce94deSChris Mason 
543f510cfecSChris Mason 	ret = __btrfs_cow_block(trans, root, buf, parent,
5449fa8cfe7SChris Mason 				 parent_slot, cow_ret, search_start, 0);
545f510cfecSChris Mason 	return ret;
5462c90e5d6SChris Mason }
5476702ed49SChris Mason 
548d352ac68SChris Mason /*
549d352ac68SChris Mason  * helper function for defrag to decide if two blocks pointed to by a
550d352ac68SChris Mason  * node are actually close by
551d352ac68SChris Mason  */
5526b80053dSChris Mason static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
5536702ed49SChris Mason {
5546b80053dSChris Mason 	if (blocknr < other && other - (blocknr + blocksize) < 32768)
5556702ed49SChris Mason 		return 1;
5566b80053dSChris Mason 	if (blocknr > other && blocknr - (other + blocksize) < 32768)
5576702ed49SChris Mason 		return 1;
55802217ed2SChris Mason 	return 0;
55902217ed2SChris Mason }
56002217ed2SChris Mason 
561081e9573SChris Mason /*
562081e9573SChris Mason  * compare two keys in a memcmp fashion
563081e9573SChris Mason  */
564081e9573SChris Mason static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
565081e9573SChris Mason {
566081e9573SChris Mason 	struct btrfs_key k1;
567081e9573SChris Mason 
568081e9573SChris Mason 	btrfs_disk_key_to_cpu(&k1, disk);
569081e9573SChris Mason 
57020736abaSDiego Calleja 	return btrfs_comp_cpu_keys(&k1, k2);
571081e9573SChris Mason }
572081e9573SChris Mason 
573f3465ca4SJosef Bacik /*
574f3465ca4SJosef Bacik  * same as comp_keys only with two btrfs_key's
575f3465ca4SJosef Bacik  */
5765d4f98a2SYan Zheng int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
577f3465ca4SJosef Bacik {
578f3465ca4SJosef Bacik 	if (k1->objectid > k2->objectid)
579f3465ca4SJosef Bacik 		return 1;
580f3465ca4SJosef Bacik 	if (k1->objectid < k2->objectid)
581f3465ca4SJosef Bacik 		return -1;
582f3465ca4SJosef Bacik 	if (k1->type > k2->type)
583f3465ca4SJosef Bacik 		return 1;
584f3465ca4SJosef Bacik 	if (k1->type < k2->type)
585f3465ca4SJosef Bacik 		return -1;
586f3465ca4SJosef Bacik 	if (k1->offset > k2->offset)
587f3465ca4SJosef Bacik 		return 1;
588f3465ca4SJosef Bacik 	if (k1->offset < k2->offset)
589f3465ca4SJosef Bacik 		return -1;
590f3465ca4SJosef Bacik 	return 0;
591f3465ca4SJosef Bacik }
592081e9573SChris Mason 
593d352ac68SChris Mason /*
594d352ac68SChris Mason  * this is used by the defrag code to go through all the
595d352ac68SChris Mason  * leaves pointed to by a node and reallocate them so that
596d352ac68SChris Mason  * disk order is close to key order
597d352ac68SChris Mason  */
5986702ed49SChris Mason int btrfs_realloc_node(struct btrfs_trans_handle *trans,
5995f39d397SChris Mason 		       struct btrfs_root *root, struct extent_buffer *parent,
600a6b6e75eSChris Mason 		       int start_slot, int cache_only, u64 *last_ret,
601a6b6e75eSChris Mason 		       struct btrfs_key *progress)
6026702ed49SChris Mason {
6036b80053dSChris Mason 	struct extent_buffer *cur;
6046702ed49SChris Mason 	u64 blocknr;
605ca7a79adSChris Mason 	u64 gen;
606e9d0b13bSChris Mason 	u64 search_start = *last_ret;
607e9d0b13bSChris Mason 	u64 last_block = 0;
6086702ed49SChris Mason 	u64 other;
6096702ed49SChris Mason 	u32 parent_nritems;
6106702ed49SChris Mason 	int end_slot;
6116702ed49SChris Mason 	int i;
6126702ed49SChris Mason 	int err = 0;
613f2183bdeSChris Mason 	int parent_level;
6146b80053dSChris Mason 	int uptodate;
6156b80053dSChris Mason 	u32 blocksize;
616081e9573SChris Mason 	int progress_passed = 0;
617081e9573SChris Mason 	struct btrfs_disk_key disk_key;
6186702ed49SChris Mason 
6195708b959SChris Mason 	parent_level = btrfs_header_level(parent);
6205708b959SChris Mason 	if (cache_only && parent_level != 1)
6215708b959SChris Mason 		return 0;
6225708b959SChris Mason 
623d397712bSChris Mason 	if (trans->transaction != root->fs_info->running_transaction)
6246702ed49SChris Mason 		WARN_ON(1);
625d397712bSChris Mason 	if (trans->transid != root->fs_info->generation)
6266702ed49SChris Mason 		WARN_ON(1);
62786479a04SChris Mason 
6286b80053dSChris Mason 	parent_nritems = btrfs_header_nritems(parent);
6296b80053dSChris Mason 	blocksize = btrfs_level_size(root, parent_level - 1);
6306702ed49SChris Mason 	end_slot = parent_nritems;
6316702ed49SChris Mason 
6326702ed49SChris Mason 	if (parent_nritems == 1)
6336702ed49SChris Mason 		return 0;
6346702ed49SChris Mason 
635b4ce94deSChris Mason 	btrfs_set_lock_blocking(parent);
636b4ce94deSChris Mason 
6376702ed49SChris Mason 	for (i = start_slot; i < end_slot; i++) {
6386702ed49SChris Mason 		int close = 1;
639a6b6e75eSChris Mason 
6405708b959SChris Mason 		if (!parent->map_token) {
6415708b959SChris Mason 			map_extent_buffer(parent,
6425708b959SChris Mason 					btrfs_node_key_ptr_offset(i),
6435708b959SChris Mason 					sizeof(struct btrfs_key_ptr),
6445708b959SChris Mason 					&parent->map_token, &parent->kaddr,
6455708b959SChris Mason 					&parent->map_start, &parent->map_len,
6465708b959SChris Mason 					KM_USER1);
6475708b959SChris Mason 		}
648081e9573SChris Mason 		btrfs_node_key(parent, &disk_key, i);
649081e9573SChris Mason 		if (!progress_passed && comp_keys(&disk_key, progress) < 0)
650081e9573SChris Mason 			continue;
651081e9573SChris Mason 
652081e9573SChris Mason 		progress_passed = 1;
6536b80053dSChris Mason 		blocknr = btrfs_node_blockptr(parent, i);
654ca7a79adSChris Mason 		gen = btrfs_node_ptr_generation(parent, i);
655e9d0b13bSChris Mason 		if (last_block == 0)
656e9d0b13bSChris Mason 			last_block = blocknr;
6575708b959SChris Mason 
6586702ed49SChris Mason 		if (i > 0) {
6596b80053dSChris Mason 			other = btrfs_node_blockptr(parent, i - 1);
6606b80053dSChris Mason 			close = close_blocks(blocknr, other, blocksize);
6616702ed49SChris Mason 		}
6620ef3e66bSChris Mason 		if (!close && i < end_slot - 2) {
6636b80053dSChris Mason 			other = btrfs_node_blockptr(parent, i + 1);
6646b80053dSChris Mason 			close = close_blocks(blocknr, other, blocksize);
6656702ed49SChris Mason 		}
666e9d0b13bSChris Mason 		if (close) {
667e9d0b13bSChris Mason 			last_block = blocknr;
6686702ed49SChris Mason 			continue;
669e9d0b13bSChris Mason 		}
6705708b959SChris Mason 		if (parent->map_token) {
6715708b959SChris Mason 			unmap_extent_buffer(parent, parent->map_token,
6725708b959SChris Mason 					    KM_USER1);
6735708b959SChris Mason 			parent->map_token = NULL;
6745708b959SChris Mason 		}
6756702ed49SChris Mason 
6766b80053dSChris Mason 		cur = btrfs_find_tree_block(root, blocknr, blocksize);
6776b80053dSChris Mason 		if (cur)
6781259ab75SChris Mason 			uptodate = btrfs_buffer_uptodate(cur, gen);
6796b80053dSChris Mason 		else
6806b80053dSChris Mason 			uptodate = 0;
6815708b959SChris Mason 		if (!cur || !uptodate) {
6826702ed49SChris Mason 			if (cache_only) {
6836b80053dSChris Mason 				free_extent_buffer(cur);
6846702ed49SChris Mason 				continue;
6856702ed49SChris Mason 			}
6866b80053dSChris Mason 			if (!cur) {
6876b80053dSChris Mason 				cur = read_tree_block(root, blocknr,
688ca7a79adSChris Mason 							 blocksize, gen);
6896b80053dSChris Mason 			} else if (!uptodate) {
690ca7a79adSChris Mason 				btrfs_read_buffer(cur, gen);
6916702ed49SChris Mason 			}
692f2183bdeSChris Mason 		}
693e9d0b13bSChris Mason 		if (search_start == 0)
6946b80053dSChris Mason 			search_start = last_block;
695e9d0b13bSChris Mason 
696e7a84565SChris Mason 		btrfs_tree_lock(cur);
697b4ce94deSChris Mason 		btrfs_set_lock_blocking(cur);
6986b80053dSChris Mason 		err = __btrfs_cow_block(trans, root, cur, parent, i,
699e7a84565SChris Mason 					&cur, search_start,
7006b80053dSChris Mason 					min(16 * blocksize,
7019fa8cfe7SChris Mason 					    (end_slot - i) * blocksize));
702252c38f0SYan 		if (err) {
703e7a84565SChris Mason 			btrfs_tree_unlock(cur);
7046b80053dSChris Mason 			free_extent_buffer(cur);
7056702ed49SChris Mason 			break;
706252c38f0SYan 		}
707e7a84565SChris Mason 		search_start = cur->start;
708e7a84565SChris Mason 		last_block = cur->start;
709f2183bdeSChris Mason 		*last_ret = search_start;
710e7a84565SChris Mason 		btrfs_tree_unlock(cur);
711e7a84565SChris Mason 		free_extent_buffer(cur);
7126702ed49SChris Mason 	}
7135708b959SChris Mason 	if (parent->map_token) {
7145708b959SChris Mason 		unmap_extent_buffer(parent, parent->map_token,
7155708b959SChris Mason 				    KM_USER1);
7165708b959SChris Mason 		parent->map_token = NULL;
7175708b959SChris Mason 	}
7186702ed49SChris Mason 	return err;
7196702ed49SChris Mason }
7206702ed49SChris Mason 
72174123bd7SChris Mason /*
72274123bd7SChris Mason  * The leaf data grows from end-to-front in the node.
72374123bd7SChris Mason  * this returns the address of the start of the last item,
72474123bd7SChris Mason  * which is the stop of the leaf data stack
72574123bd7SChris Mason  */
726123abc88SChris Mason static inline unsigned int leaf_data_end(struct btrfs_root *root,
7275f39d397SChris Mason 					 struct extent_buffer *leaf)
728be0e5c09SChris Mason {
7295f39d397SChris Mason 	u32 nr = btrfs_header_nritems(leaf);
730be0e5c09SChris Mason 	if (nr == 0)
731123abc88SChris Mason 		return BTRFS_LEAF_DATA_SIZE(root);
7325f39d397SChris Mason 	return btrfs_item_offset_nr(leaf, nr - 1);
733be0e5c09SChris Mason }
734be0e5c09SChris Mason 
735d352ac68SChris Mason /*
736d352ac68SChris Mason  * extra debugging checks to make sure all the items in a key are
737d352ac68SChris Mason  * well formed and in the proper order
738d352ac68SChris Mason  */
739123abc88SChris Mason static int check_node(struct btrfs_root *root, struct btrfs_path *path,
740123abc88SChris Mason 		      int level)
741aa5d6bedSChris Mason {
7425f39d397SChris Mason 	struct extent_buffer *parent = NULL;
7435f39d397SChris Mason 	struct extent_buffer *node = path->nodes[level];
7445f39d397SChris Mason 	struct btrfs_disk_key parent_key;
7455f39d397SChris Mason 	struct btrfs_disk_key node_key;
746aa5d6bedSChris Mason 	int parent_slot;
7478d7be552SChris Mason 	int slot;
7488d7be552SChris Mason 	struct btrfs_key cpukey;
7495f39d397SChris Mason 	u32 nritems = btrfs_header_nritems(node);
750aa5d6bedSChris Mason 
751aa5d6bedSChris Mason 	if (path->nodes[level + 1])
7525f39d397SChris Mason 		parent = path->nodes[level + 1];
753a1f39630SAneesh 
7548d7be552SChris Mason 	slot = path->slots[level];
7557518a238SChris Mason 	BUG_ON(nritems == 0);
7567518a238SChris Mason 	if (parent) {
757a1f39630SAneesh 		parent_slot = path->slots[level + 1];
7585f39d397SChris Mason 		btrfs_node_key(parent, &parent_key, parent_slot);
7595f39d397SChris Mason 		btrfs_node_key(node, &node_key, 0);
7605f39d397SChris Mason 		BUG_ON(memcmp(&parent_key, &node_key,
761e2fa7227SChris Mason 			      sizeof(struct btrfs_disk_key)));
7621d4f8a0cSChris Mason 		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
763db94535dSChris Mason 		       btrfs_header_bytenr(node));
764aa5d6bedSChris Mason 	}
765123abc88SChris Mason 	BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
7668d7be552SChris Mason 	if (slot != 0) {
7675f39d397SChris Mason 		btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
7685f39d397SChris Mason 		btrfs_node_key(node, &node_key, slot);
7695f39d397SChris Mason 		BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
7708d7be552SChris Mason 	}
7718d7be552SChris Mason 	if (slot < nritems - 1) {
7725f39d397SChris Mason 		btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
7735f39d397SChris Mason 		btrfs_node_key(node, &node_key, slot);
7745f39d397SChris Mason 		BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
775aa5d6bedSChris Mason 	}
776aa5d6bedSChris Mason 	return 0;
777aa5d6bedSChris Mason }
778aa5d6bedSChris Mason 
779d352ac68SChris Mason /*
780d352ac68SChris Mason  * extra checking to make sure all the items in a leaf are
781d352ac68SChris Mason  * well formed and in the proper order
782d352ac68SChris Mason  */
783123abc88SChris Mason static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
784123abc88SChris Mason 		      int level)
785aa5d6bedSChris Mason {
7865f39d397SChris Mason 	struct extent_buffer *leaf = path->nodes[level];
7875f39d397SChris Mason 	struct extent_buffer *parent = NULL;
788aa5d6bedSChris Mason 	int parent_slot;
7898d7be552SChris Mason 	struct btrfs_key cpukey;
7905f39d397SChris Mason 	struct btrfs_disk_key parent_key;
7915f39d397SChris Mason 	struct btrfs_disk_key leaf_key;
7925f39d397SChris Mason 	int slot = path->slots[0];
7938d7be552SChris Mason 
7945f39d397SChris Mason 	u32 nritems = btrfs_header_nritems(leaf);
795aa5d6bedSChris Mason 
796aa5d6bedSChris Mason 	if (path->nodes[level + 1])
7975f39d397SChris Mason 		parent = path->nodes[level + 1];
7987518a238SChris Mason 
7997518a238SChris Mason 	if (nritems == 0)
8007518a238SChris Mason 		return 0;
8017518a238SChris Mason 
8027518a238SChris Mason 	if (parent) {
803a1f39630SAneesh 		parent_slot = path->slots[level + 1];
8045f39d397SChris Mason 		btrfs_node_key(parent, &parent_key, parent_slot);
8055f39d397SChris Mason 		btrfs_item_key(leaf, &leaf_key, 0);
8066702ed49SChris Mason 
8075f39d397SChris Mason 		BUG_ON(memcmp(&parent_key, &leaf_key,
808e2fa7227SChris Mason 		       sizeof(struct btrfs_disk_key)));
8091d4f8a0cSChris Mason 		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
810db94535dSChris Mason 		       btrfs_header_bytenr(leaf));
811aa5d6bedSChris Mason 	}
8125f39d397SChris Mason 	if (slot != 0 && slot < nritems - 1) {
8135f39d397SChris Mason 		btrfs_item_key(leaf, &leaf_key, slot);
8145f39d397SChris Mason 		btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
8155f39d397SChris Mason 		if (comp_keys(&leaf_key, &cpukey) <= 0) {
8165f39d397SChris Mason 			btrfs_print_leaf(root, leaf);
817d397712bSChris Mason 			printk(KERN_CRIT "slot %d offset bad key\n", slot);
8185f39d397SChris Mason 			BUG_ON(1);
8195f39d397SChris Mason 		}
8205f39d397SChris Mason 		if (btrfs_item_offset_nr(leaf, slot - 1) !=
8215f39d397SChris Mason 		       btrfs_item_end_nr(leaf, slot)) {
8225f39d397SChris Mason 			btrfs_print_leaf(root, leaf);
823d397712bSChris Mason 			printk(KERN_CRIT "slot %d offset bad\n", slot);
8245f39d397SChris Mason 			BUG_ON(1);
8255f39d397SChris Mason 		}
826aa5d6bedSChris Mason 	}
8278d7be552SChris Mason 	if (slot < nritems - 1) {
8285f39d397SChris Mason 		btrfs_item_key(leaf, &leaf_key, slot);
8295f39d397SChris Mason 		btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
8305f39d397SChris Mason 		BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
8315f39d397SChris Mason 		if (btrfs_item_offset_nr(leaf, slot) !=
8325f39d397SChris Mason 			btrfs_item_end_nr(leaf, slot + 1)) {
8335f39d397SChris Mason 			btrfs_print_leaf(root, leaf);
834d397712bSChris Mason 			printk(KERN_CRIT "slot %d offset bad\n", slot);
8355f39d397SChris Mason 			BUG_ON(1);
836aa5d6bedSChris Mason 		}
8375f39d397SChris Mason 	}
8385f39d397SChris Mason 	BUG_ON(btrfs_item_offset_nr(leaf, 0) +
8395f39d397SChris Mason 	       btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
840aa5d6bedSChris Mason 	return 0;
841aa5d6bedSChris Mason }
842aa5d6bedSChris Mason 
843d397712bSChris Mason static noinline int check_block(struct btrfs_root *root,
84498ed5174SChris Mason 				struct btrfs_path *path, int level)
845aa5d6bedSChris Mason {
84685d824c4SChris Mason 	return 0;
847aa5d6bedSChris Mason 	if (level == 0)
848123abc88SChris Mason 		return check_leaf(root, path, level);
849123abc88SChris Mason 	return check_node(root, path, level);
850aa5d6bedSChris Mason }
851aa5d6bedSChris Mason 
85274123bd7SChris Mason /*
8535f39d397SChris Mason  * search for key in the extent_buffer.  The items start at offset p,
8545f39d397SChris Mason  * and they are item_size apart.  There are 'max' items in p.
8555f39d397SChris Mason  *
85674123bd7SChris Mason  * the slot in the array is returned via slot, and it points to
85774123bd7SChris Mason  * the place where you would insert key if it is not found in
85874123bd7SChris Mason  * the array.
85974123bd7SChris Mason  *
86074123bd7SChris Mason  * slot may point to max if the key is bigger than all of the keys
86174123bd7SChris Mason  */
862e02119d5SChris Mason static noinline int generic_bin_search(struct extent_buffer *eb,
863e02119d5SChris Mason 				       unsigned long p,
8645f39d397SChris Mason 				       int item_size, struct btrfs_key *key,
865be0e5c09SChris Mason 				       int max, int *slot)
866be0e5c09SChris Mason {
867be0e5c09SChris Mason 	int low = 0;
868be0e5c09SChris Mason 	int high = max;
869be0e5c09SChris Mason 	int mid;
870be0e5c09SChris Mason 	int ret;
871479965d6SChris Mason 	struct btrfs_disk_key *tmp = NULL;
8725f39d397SChris Mason 	struct btrfs_disk_key unaligned;
8735f39d397SChris Mason 	unsigned long offset;
8745f39d397SChris Mason 	char *map_token = NULL;
8755f39d397SChris Mason 	char *kaddr = NULL;
8765f39d397SChris Mason 	unsigned long map_start = 0;
8775f39d397SChris Mason 	unsigned long map_len = 0;
878479965d6SChris Mason 	int err;
879be0e5c09SChris Mason 
880be0e5c09SChris Mason 	while (low < high) {
881be0e5c09SChris Mason 		mid = (low + high) / 2;
8825f39d397SChris Mason 		offset = p + mid * item_size;
8835f39d397SChris Mason 
8845f39d397SChris Mason 		if (!map_token || offset < map_start ||
8855f39d397SChris Mason 		    (offset + sizeof(struct btrfs_disk_key)) >
8865f39d397SChris Mason 		    map_start + map_len) {
887479965d6SChris Mason 			if (map_token) {
8885f39d397SChris Mason 				unmap_extent_buffer(eb, map_token, KM_USER0);
889479965d6SChris Mason 				map_token = NULL;
890479965d6SChris Mason 			}
891934d375bSChris Mason 
892934d375bSChris Mason 			err = map_private_extent_buffer(eb, offset,
893479965d6SChris Mason 						sizeof(struct btrfs_disk_key),
894479965d6SChris Mason 						&map_token, &kaddr,
8955f39d397SChris Mason 						&map_start, &map_len, KM_USER0);
8965f39d397SChris Mason 
897479965d6SChris Mason 			if (!err) {
898479965d6SChris Mason 				tmp = (struct btrfs_disk_key *)(kaddr + offset -
899479965d6SChris Mason 							map_start);
900479965d6SChris Mason 			} else {
9015f39d397SChris Mason 				read_extent_buffer(eb, &unaligned,
9025f39d397SChris Mason 						   offset, sizeof(unaligned));
9035f39d397SChris Mason 				tmp = &unaligned;
904479965d6SChris Mason 			}
905479965d6SChris Mason 
9065f39d397SChris Mason 		} else {
9075f39d397SChris Mason 			tmp = (struct btrfs_disk_key *)(kaddr + offset -
9085f39d397SChris Mason 							map_start);
9095f39d397SChris Mason 		}
910be0e5c09SChris Mason 		ret = comp_keys(tmp, key);
911be0e5c09SChris Mason 
912be0e5c09SChris Mason 		if (ret < 0)
913be0e5c09SChris Mason 			low = mid + 1;
914be0e5c09SChris Mason 		else if (ret > 0)
915be0e5c09SChris Mason 			high = mid;
916be0e5c09SChris Mason 		else {
917be0e5c09SChris Mason 			*slot = mid;
918479965d6SChris Mason 			if (map_token)
9195f39d397SChris Mason 				unmap_extent_buffer(eb, map_token, KM_USER0);
920be0e5c09SChris Mason 			return 0;
921be0e5c09SChris Mason 		}
922be0e5c09SChris Mason 	}
923be0e5c09SChris Mason 	*slot = low;
9245f39d397SChris Mason 	if (map_token)
9255f39d397SChris Mason 		unmap_extent_buffer(eb, map_token, KM_USER0);
926be0e5c09SChris Mason 	return 1;
927be0e5c09SChris Mason }
928be0e5c09SChris Mason 
92997571fd0SChris Mason /*
93097571fd0SChris Mason  * simple bin_search frontend that does the right thing for
93197571fd0SChris Mason  * leaves vs nodes
93297571fd0SChris Mason  */
9335f39d397SChris Mason static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
9345f39d397SChris Mason 		      int level, int *slot)
935be0e5c09SChris Mason {
9365f39d397SChris Mason 	if (level == 0) {
9375f39d397SChris Mason 		return generic_bin_search(eb,
9385f39d397SChris Mason 					  offsetof(struct btrfs_leaf, items),
9390783fcfcSChris Mason 					  sizeof(struct btrfs_item),
9405f39d397SChris Mason 					  key, btrfs_header_nritems(eb),
9417518a238SChris Mason 					  slot);
942be0e5c09SChris Mason 	} else {
9435f39d397SChris Mason 		return generic_bin_search(eb,
9445f39d397SChris Mason 					  offsetof(struct btrfs_node, ptrs),
945123abc88SChris Mason 					  sizeof(struct btrfs_key_ptr),
9465f39d397SChris Mason 					  key, btrfs_header_nritems(eb),
9477518a238SChris Mason 					  slot);
948be0e5c09SChris Mason 	}
949be0e5c09SChris Mason 	return -1;
950be0e5c09SChris Mason }
951be0e5c09SChris Mason 
9525d4f98a2SYan Zheng int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
9535d4f98a2SYan Zheng 		     int level, int *slot)
9545d4f98a2SYan Zheng {
9555d4f98a2SYan Zheng 	return bin_search(eb, key, level, slot);
9565d4f98a2SYan Zheng }
9575d4f98a2SYan Zheng 
958f0486c68SYan, Zheng static void root_add_used(struct btrfs_root *root, u32 size)
959f0486c68SYan, Zheng {
960f0486c68SYan, Zheng 	spin_lock(&root->accounting_lock);
961f0486c68SYan, Zheng 	btrfs_set_root_used(&root->root_item,
962f0486c68SYan, Zheng 			    btrfs_root_used(&root->root_item) + size);
963f0486c68SYan, Zheng 	spin_unlock(&root->accounting_lock);
964f0486c68SYan, Zheng }
965f0486c68SYan, Zheng 
966f0486c68SYan, Zheng static void root_sub_used(struct btrfs_root *root, u32 size)
967f0486c68SYan, Zheng {
968f0486c68SYan, Zheng 	spin_lock(&root->accounting_lock);
969f0486c68SYan, Zheng 	btrfs_set_root_used(&root->root_item,
970f0486c68SYan, Zheng 			    btrfs_root_used(&root->root_item) - size);
971f0486c68SYan, Zheng 	spin_unlock(&root->accounting_lock);
972f0486c68SYan, Zheng }
973f0486c68SYan, Zheng 
974d352ac68SChris Mason /* given a node and slot number, this reads the blocks it points to.  The
975d352ac68SChris Mason  * extent buffer is returned with a reference taken (but unlocked).
976d352ac68SChris Mason  * NULL is returned on error.
977d352ac68SChris Mason  */
978e02119d5SChris Mason static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
9795f39d397SChris Mason 				   struct extent_buffer *parent, int slot)
980bb803951SChris Mason {
981ca7a79adSChris Mason 	int level = btrfs_header_level(parent);
982bb803951SChris Mason 	if (slot < 0)
983bb803951SChris Mason 		return NULL;
9845f39d397SChris Mason 	if (slot >= btrfs_header_nritems(parent))
985bb803951SChris Mason 		return NULL;
986ca7a79adSChris Mason 
987ca7a79adSChris Mason 	BUG_ON(level == 0);
988ca7a79adSChris Mason 
989db94535dSChris Mason 	return read_tree_block(root, btrfs_node_blockptr(parent, slot),
990ca7a79adSChris Mason 		       btrfs_level_size(root, level - 1),
991ca7a79adSChris Mason 		       btrfs_node_ptr_generation(parent, slot));
992bb803951SChris Mason }
993bb803951SChris Mason 
994d352ac68SChris Mason /*
995d352ac68SChris Mason  * node level balancing, used to make sure nodes are in proper order for
996d352ac68SChris Mason  * item deletion.  We balance from the top down, so we have to make sure
997d352ac68SChris Mason  * that a deletion won't leave an node completely empty later on.
998d352ac68SChris Mason  */
999e02119d5SChris Mason static noinline int balance_level(struct btrfs_trans_handle *trans,
100098ed5174SChris Mason 			 struct btrfs_root *root,
100198ed5174SChris Mason 			 struct btrfs_path *path, int level)
1002bb803951SChris Mason {
10035f39d397SChris Mason 	struct extent_buffer *right = NULL;
10045f39d397SChris Mason 	struct extent_buffer *mid;
10055f39d397SChris Mason 	struct extent_buffer *left = NULL;
10065f39d397SChris Mason 	struct extent_buffer *parent = NULL;
1007bb803951SChris Mason 	int ret = 0;
1008bb803951SChris Mason 	int wret;
1009bb803951SChris Mason 	int pslot;
1010bb803951SChris Mason 	int orig_slot = path->slots[level];
101154aa1f4dSChris Mason 	int err_on_enospc = 0;
101279f95c82SChris Mason 	u64 orig_ptr;
1013bb803951SChris Mason 
1014bb803951SChris Mason 	if (level == 0)
1015bb803951SChris Mason 		return 0;
1016bb803951SChris Mason 
10175f39d397SChris Mason 	mid = path->nodes[level];
1018b4ce94deSChris Mason 
1019925baeddSChris Mason 	WARN_ON(!path->locks[level]);
10207bb86316SChris Mason 	WARN_ON(btrfs_header_generation(mid) != trans->transid);
10217bb86316SChris Mason 
10221d4f8a0cSChris Mason 	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
102379f95c82SChris Mason 
1024234b63a0SChris Mason 	if (level < BTRFS_MAX_LEVEL - 1)
10255f39d397SChris Mason 		parent = path->nodes[level + 1];
1026bb803951SChris Mason 	pslot = path->slots[level + 1];
1027bb803951SChris Mason 
102840689478SChris Mason 	/*
102940689478SChris Mason 	 * deal with the case where there is only one pointer in the root
103040689478SChris Mason 	 * by promoting the node below to a root
103140689478SChris Mason 	 */
10325f39d397SChris Mason 	if (!parent) {
10335f39d397SChris Mason 		struct extent_buffer *child;
1034bb803951SChris Mason 
10355f39d397SChris Mason 		if (btrfs_header_nritems(mid) != 1)
1036bb803951SChris Mason 			return 0;
1037bb803951SChris Mason 
1038bb803951SChris Mason 		/* promote the child to a root */
10395f39d397SChris Mason 		child = read_node_slot(root, mid, 0);
10407951f3ceSJeff Mahoney 		BUG_ON(!child);
1041925baeddSChris Mason 		btrfs_tree_lock(child);
1042b4ce94deSChris Mason 		btrfs_set_lock_blocking(child);
10439fa8cfe7SChris Mason 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
1044f0486c68SYan, Zheng 		if (ret) {
1045f0486c68SYan, Zheng 			btrfs_tree_unlock(child);
1046f0486c68SYan, Zheng 			free_extent_buffer(child);
1047f0486c68SYan, Zheng 			goto enospc;
1048f0486c68SYan, Zheng 		}
10492f375ab9SYan 
1050925baeddSChris Mason 		spin_lock(&root->node_lock);
1051bb803951SChris Mason 		root->node = child;
1052925baeddSChris Mason 		spin_unlock(&root->node_lock);
1053925baeddSChris Mason 
10540b86a832SChris Mason 		add_root_to_dirty_list(root);
1055925baeddSChris Mason 		btrfs_tree_unlock(child);
1056b4ce94deSChris Mason 
1057925baeddSChris Mason 		path->locks[level] = 0;
1058bb803951SChris Mason 		path->nodes[level] = NULL;
10595f39d397SChris Mason 		clean_tree_block(trans, root, mid);
1060925baeddSChris Mason 		btrfs_tree_unlock(mid);
1061bb803951SChris Mason 		/* once for the path */
10625f39d397SChris Mason 		free_extent_buffer(mid);
1063f0486c68SYan, Zheng 
1064f0486c68SYan, Zheng 		root_sub_used(root, mid->len);
1065f0486c68SYan, Zheng 		btrfs_free_tree_block(trans, root, mid, 0, 1);
1066bb803951SChris Mason 		/* once for the root ptr */
10675f39d397SChris Mason 		free_extent_buffer(mid);
1068f0486c68SYan, Zheng 		return 0;
1069bb803951SChris Mason 	}
10705f39d397SChris Mason 	if (btrfs_header_nritems(mid) >
1071123abc88SChris Mason 	    BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
1072bb803951SChris Mason 		return 0;
1073bb803951SChris Mason 
10745f39d397SChris Mason 	if (btrfs_header_nritems(mid) < 2)
107554aa1f4dSChris Mason 		err_on_enospc = 1;
107654aa1f4dSChris Mason 
10775f39d397SChris Mason 	left = read_node_slot(root, parent, pslot - 1);
10785f39d397SChris Mason 	if (left) {
1079925baeddSChris Mason 		btrfs_tree_lock(left);
1080b4ce94deSChris Mason 		btrfs_set_lock_blocking(left);
10815f39d397SChris Mason 		wret = btrfs_cow_block(trans, root, left,
10829fa8cfe7SChris Mason 				       parent, pslot - 1, &left);
108354aa1f4dSChris Mason 		if (wret) {
108454aa1f4dSChris Mason 			ret = wret;
108554aa1f4dSChris Mason 			goto enospc;
108654aa1f4dSChris Mason 		}
10872cc58cf2SChris Mason 	}
10885f39d397SChris Mason 	right = read_node_slot(root, parent, pslot + 1);
10895f39d397SChris Mason 	if (right) {
1090925baeddSChris Mason 		btrfs_tree_lock(right);
1091b4ce94deSChris Mason 		btrfs_set_lock_blocking(right);
10925f39d397SChris Mason 		wret = btrfs_cow_block(trans, root, right,
10939fa8cfe7SChris Mason 				       parent, pslot + 1, &right);
10942cc58cf2SChris Mason 		if (wret) {
10952cc58cf2SChris Mason 			ret = wret;
10962cc58cf2SChris Mason 			goto enospc;
10972cc58cf2SChris Mason 		}
10982cc58cf2SChris Mason 	}
10992cc58cf2SChris Mason 
11002cc58cf2SChris Mason 	/* first, try to make some room in the middle buffer */
11015f39d397SChris Mason 	if (left) {
11025f39d397SChris Mason 		orig_slot += btrfs_header_nritems(left);
1103bce4eae9SChris Mason 		wret = push_node_left(trans, root, left, mid, 1);
110479f95c82SChris Mason 		if (wret < 0)
110579f95c82SChris Mason 			ret = wret;
11065f39d397SChris Mason 		if (btrfs_header_nritems(mid) < 2)
110754aa1f4dSChris Mason 			err_on_enospc = 1;
1108bb803951SChris Mason 	}
110979f95c82SChris Mason 
111079f95c82SChris Mason 	/*
111179f95c82SChris Mason 	 * then try to empty the right most buffer into the middle
111279f95c82SChris Mason 	 */
11135f39d397SChris Mason 	if (right) {
1114971a1f66SChris Mason 		wret = push_node_left(trans, root, mid, right, 1);
111554aa1f4dSChris Mason 		if (wret < 0 && wret != -ENOSPC)
111679f95c82SChris Mason 			ret = wret;
11175f39d397SChris Mason 		if (btrfs_header_nritems(right) == 0) {
11185f39d397SChris Mason 			clean_tree_block(trans, root, right);
1119925baeddSChris Mason 			btrfs_tree_unlock(right);
1120e089f05cSChris Mason 			wret = del_ptr(trans, root, path, level + 1, pslot +
1121e089f05cSChris Mason 				       1);
1122bb803951SChris Mason 			if (wret)
1123bb803951SChris Mason 				ret = wret;
1124f0486c68SYan, Zheng 			root_sub_used(root, right->len);
1125f0486c68SYan, Zheng 			btrfs_free_tree_block(trans, root, right, 0, 1);
1126f0486c68SYan, Zheng 			free_extent_buffer(right);
1127f0486c68SYan, Zheng 			right = NULL;
1128bb803951SChris Mason 		} else {
11295f39d397SChris Mason 			struct btrfs_disk_key right_key;
11305f39d397SChris Mason 			btrfs_node_key(right, &right_key, 0);
11315f39d397SChris Mason 			btrfs_set_node_key(parent, &right_key, pslot + 1);
11325f39d397SChris Mason 			btrfs_mark_buffer_dirty(parent);
1133bb803951SChris Mason 		}
1134bb803951SChris Mason 	}
11355f39d397SChris Mason 	if (btrfs_header_nritems(mid) == 1) {
113679f95c82SChris Mason 		/*
113779f95c82SChris Mason 		 * we're not allowed to leave a node with one item in the
113879f95c82SChris Mason 		 * tree during a delete.  A deletion from lower in the tree
113979f95c82SChris Mason 		 * could try to delete the only pointer in this node.
114079f95c82SChris Mason 		 * So, pull some keys from the left.
114179f95c82SChris Mason 		 * There has to be a left pointer at this point because
114279f95c82SChris Mason 		 * otherwise we would have pulled some pointers from the
114379f95c82SChris Mason 		 * right
114479f95c82SChris Mason 		 */
11455f39d397SChris Mason 		BUG_ON(!left);
11465f39d397SChris Mason 		wret = balance_node_right(trans, root, mid, left);
114754aa1f4dSChris Mason 		if (wret < 0) {
114879f95c82SChris Mason 			ret = wret;
114954aa1f4dSChris Mason 			goto enospc;
115054aa1f4dSChris Mason 		}
1151bce4eae9SChris Mason 		if (wret == 1) {
1152bce4eae9SChris Mason 			wret = push_node_left(trans, root, left, mid, 1);
1153bce4eae9SChris Mason 			if (wret < 0)
1154bce4eae9SChris Mason 				ret = wret;
1155bce4eae9SChris Mason 		}
115679f95c82SChris Mason 		BUG_ON(wret == 1);
115779f95c82SChris Mason 	}
11585f39d397SChris Mason 	if (btrfs_header_nritems(mid) == 0) {
11595f39d397SChris Mason 		clean_tree_block(trans, root, mid);
1160925baeddSChris Mason 		btrfs_tree_unlock(mid);
1161e089f05cSChris Mason 		wret = del_ptr(trans, root, path, level + 1, pslot);
1162bb803951SChris Mason 		if (wret)
1163bb803951SChris Mason 			ret = wret;
1164f0486c68SYan, Zheng 		root_sub_used(root, mid->len);
1165f0486c68SYan, Zheng 		btrfs_free_tree_block(trans, root, mid, 0, 1);
1166f0486c68SYan, Zheng 		free_extent_buffer(mid);
1167f0486c68SYan, Zheng 		mid = NULL;
116879f95c82SChris Mason 	} else {
116979f95c82SChris Mason 		/* update the parent key to reflect our changes */
11705f39d397SChris Mason 		struct btrfs_disk_key mid_key;
11715f39d397SChris Mason 		btrfs_node_key(mid, &mid_key, 0);
11725f39d397SChris Mason 		btrfs_set_node_key(parent, &mid_key, pslot);
11735f39d397SChris Mason 		btrfs_mark_buffer_dirty(parent);
117479f95c82SChris Mason 	}
1175bb803951SChris Mason 
117679f95c82SChris Mason 	/* update the path */
11775f39d397SChris Mason 	if (left) {
11785f39d397SChris Mason 		if (btrfs_header_nritems(left) > orig_slot) {
11795f39d397SChris Mason 			extent_buffer_get(left);
1180925baeddSChris Mason 			/* left was locked after cow */
11815f39d397SChris Mason 			path->nodes[level] = left;
1182bb803951SChris Mason 			path->slots[level + 1] -= 1;
1183bb803951SChris Mason 			path->slots[level] = orig_slot;
1184925baeddSChris Mason 			if (mid) {
1185925baeddSChris Mason 				btrfs_tree_unlock(mid);
11865f39d397SChris Mason 				free_extent_buffer(mid);
1187925baeddSChris Mason 			}
1188bb803951SChris Mason 		} else {
11895f39d397SChris Mason 			orig_slot -= btrfs_header_nritems(left);
1190bb803951SChris Mason 			path->slots[level] = orig_slot;
1191bb803951SChris Mason 		}
1192bb803951SChris Mason 	}
119379f95c82SChris Mason 	/* double check we haven't messed things up */
1194123abc88SChris Mason 	check_block(root, path, level);
1195e20d96d6SChris Mason 	if (orig_ptr !=
11965f39d397SChris Mason 	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
119779f95c82SChris Mason 		BUG();
119854aa1f4dSChris Mason enospc:
1199925baeddSChris Mason 	if (right) {
1200925baeddSChris Mason 		btrfs_tree_unlock(right);
12015f39d397SChris Mason 		free_extent_buffer(right);
1202925baeddSChris Mason 	}
1203925baeddSChris Mason 	if (left) {
1204925baeddSChris Mason 		if (path->nodes[level] != left)
1205925baeddSChris Mason 			btrfs_tree_unlock(left);
12065f39d397SChris Mason 		free_extent_buffer(left);
1207925baeddSChris Mason 	}
1208bb803951SChris Mason 	return ret;
1209bb803951SChris Mason }
1210bb803951SChris Mason 
1211d352ac68SChris Mason /* Node balancing for insertion.  Here we only split or push nodes around
1212d352ac68SChris Mason  * when they are completely full.  This is also done top down, so we
1213d352ac68SChris Mason  * have to be pessimistic.
1214d352ac68SChris Mason  */
1215d397712bSChris Mason static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1216e66f709bSChris Mason 					  struct btrfs_root *root,
1217e66f709bSChris Mason 					  struct btrfs_path *path, int level)
1218e66f709bSChris Mason {
12195f39d397SChris Mason 	struct extent_buffer *right = NULL;
12205f39d397SChris Mason 	struct extent_buffer *mid;
12215f39d397SChris Mason 	struct extent_buffer *left = NULL;
12225f39d397SChris Mason 	struct extent_buffer *parent = NULL;
1223e66f709bSChris Mason 	int ret = 0;
1224e66f709bSChris Mason 	int wret;
1225e66f709bSChris Mason 	int pslot;
1226e66f709bSChris Mason 	int orig_slot = path->slots[level];
1227e66f709bSChris Mason 	u64 orig_ptr;
1228e66f709bSChris Mason 
1229e66f709bSChris Mason 	if (level == 0)
1230e66f709bSChris Mason 		return 1;
1231e66f709bSChris Mason 
12325f39d397SChris Mason 	mid = path->nodes[level];
12337bb86316SChris Mason 	WARN_ON(btrfs_header_generation(mid) != trans->transid);
1234e66f709bSChris Mason 	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1235e66f709bSChris Mason 
1236e66f709bSChris Mason 	if (level < BTRFS_MAX_LEVEL - 1)
12375f39d397SChris Mason 		parent = path->nodes[level + 1];
1238e66f709bSChris Mason 	pslot = path->slots[level + 1];
1239e66f709bSChris Mason 
12405f39d397SChris Mason 	if (!parent)
1241e66f709bSChris Mason 		return 1;
1242e66f709bSChris Mason 
12435f39d397SChris Mason 	left = read_node_slot(root, parent, pslot - 1);
1244e66f709bSChris Mason 
1245e66f709bSChris Mason 	/* first, try to make some room in the middle buffer */
12465f39d397SChris Mason 	if (left) {
1247e66f709bSChris Mason 		u32 left_nr;
1248925baeddSChris Mason 
1249925baeddSChris Mason 		btrfs_tree_lock(left);
1250b4ce94deSChris Mason 		btrfs_set_lock_blocking(left);
1251b4ce94deSChris Mason 
12525f39d397SChris Mason 		left_nr = btrfs_header_nritems(left);
125333ade1f8SChris Mason 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
125433ade1f8SChris Mason 			wret = 1;
125533ade1f8SChris Mason 		} else {
12565f39d397SChris Mason 			ret = btrfs_cow_block(trans, root, left, parent,
12579fa8cfe7SChris Mason 					      pslot - 1, &left);
125854aa1f4dSChris Mason 			if (ret)
125954aa1f4dSChris Mason 				wret = 1;
126054aa1f4dSChris Mason 			else {
126154aa1f4dSChris Mason 				wret = push_node_left(trans, root,
1262971a1f66SChris Mason 						      left, mid, 0);
126354aa1f4dSChris Mason 			}
126433ade1f8SChris Mason 		}
1265e66f709bSChris Mason 		if (wret < 0)
1266e66f709bSChris Mason 			ret = wret;
1267e66f709bSChris Mason 		if (wret == 0) {
12685f39d397SChris Mason 			struct btrfs_disk_key disk_key;
1269e66f709bSChris Mason 			orig_slot += left_nr;
12705f39d397SChris Mason 			btrfs_node_key(mid, &disk_key, 0);
12715f39d397SChris Mason 			btrfs_set_node_key(parent, &disk_key, pslot);
12725f39d397SChris Mason 			btrfs_mark_buffer_dirty(parent);
12735f39d397SChris Mason 			if (btrfs_header_nritems(left) > orig_slot) {
12745f39d397SChris Mason 				path->nodes[level] = left;
1275e66f709bSChris Mason 				path->slots[level + 1] -= 1;
1276e66f709bSChris Mason 				path->slots[level] = orig_slot;
1277925baeddSChris Mason 				btrfs_tree_unlock(mid);
12785f39d397SChris Mason 				free_extent_buffer(mid);
1279e66f709bSChris Mason 			} else {
1280e66f709bSChris Mason 				orig_slot -=
12815f39d397SChris Mason 					btrfs_header_nritems(left);
1282e66f709bSChris Mason 				path->slots[level] = orig_slot;
1283925baeddSChris Mason 				btrfs_tree_unlock(left);
12845f39d397SChris Mason 				free_extent_buffer(left);
1285e66f709bSChris Mason 			}
1286e66f709bSChris Mason 			return 0;
1287e66f709bSChris Mason 		}
1288925baeddSChris Mason 		btrfs_tree_unlock(left);
12895f39d397SChris Mason 		free_extent_buffer(left);
1290e66f709bSChris Mason 	}
12915f39d397SChris Mason 	right = read_node_slot(root, parent, pslot + 1);
1292e66f709bSChris Mason 
1293e66f709bSChris Mason 	/*
1294e66f709bSChris Mason 	 * then try to empty the right most buffer into the middle
1295e66f709bSChris Mason 	 */
12965f39d397SChris Mason 	if (right) {
129733ade1f8SChris Mason 		u32 right_nr;
1298b4ce94deSChris Mason 
1299925baeddSChris Mason 		btrfs_tree_lock(right);
1300b4ce94deSChris Mason 		btrfs_set_lock_blocking(right);
1301b4ce94deSChris Mason 
13025f39d397SChris Mason 		right_nr = btrfs_header_nritems(right);
130333ade1f8SChris Mason 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
130433ade1f8SChris Mason 			wret = 1;
130533ade1f8SChris Mason 		} else {
13065f39d397SChris Mason 			ret = btrfs_cow_block(trans, root, right,
13075f39d397SChris Mason 					      parent, pslot + 1,
13089fa8cfe7SChris Mason 					      &right);
130954aa1f4dSChris Mason 			if (ret)
131054aa1f4dSChris Mason 				wret = 1;
131154aa1f4dSChris Mason 			else {
131233ade1f8SChris Mason 				wret = balance_node_right(trans, root,
13135f39d397SChris Mason 							  right, mid);
131433ade1f8SChris Mason 			}
131554aa1f4dSChris Mason 		}
1316e66f709bSChris Mason 		if (wret < 0)
1317e66f709bSChris Mason 			ret = wret;
1318e66f709bSChris Mason 		if (wret == 0) {
13195f39d397SChris Mason 			struct btrfs_disk_key disk_key;
13205f39d397SChris Mason 
13215f39d397SChris Mason 			btrfs_node_key(right, &disk_key, 0);
13225f39d397SChris Mason 			btrfs_set_node_key(parent, &disk_key, pslot + 1);
13235f39d397SChris Mason 			btrfs_mark_buffer_dirty(parent);
13245f39d397SChris Mason 
13255f39d397SChris Mason 			if (btrfs_header_nritems(mid) <= orig_slot) {
13265f39d397SChris Mason 				path->nodes[level] = right;
1327e66f709bSChris Mason 				path->slots[level + 1] += 1;
1328e66f709bSChris Mason 				path->slots[level] = orig_slot -
13295f39d397SChris Mason 					btrfs_header_nritems(mid);
1330925baeddSChris Mason 				btrfs_tree_unlock(mid);
13315f39d397SChris Mason 				free_extent_buffer(mid);
1332e66f709bSChris Mason 			} else {
1333925baeddSChris Mason 				btrfs_tree_unlock(right);
13345f39d397SChris Mason 				free_extent_buffer(right);
1335e66f709bSChris Mason 			}
1336e66f709bSChris Mason 			return 0;
1337e66f709bSChris Mason 		}
1338925baeddSChris Mason 		btrfs_tree_unlock(right);
13395f39d397SChris Mason 		free_extent_buffer(right);
1340e66f709bSChris Mason 	}
1341e66f709bSChris Mason 	return 1;
1342e66f709bSChris Mason }
1343e66f709bSChris Mason 
134474123bd7SChris Mason /*
1345d352ac68SChris Mason  * readahead one full node of leaves, finding things that are close
1346d352ac68SChris Mason  * to the block in 'slot', and triggering ra on them.
13473c69faecSChris Mason  */
1348c8c42864SChris Mason static void reada_for_search(struct btrfs_root *root,
1349e02119d5SChris Mason 			     struct btrfs_path *path,
135001f46658SChris Mason 			     int level, int slot, u64 objectid)
13513c69faecSChris Mason {
13525f39d397SChris Mason 	struct extent_buffer *node;
135301f46658SChris Mason 	struct btrfs_disk_key disk_key;
13543c69faecSChris Mason 	u32 nritems;
13553c69faecSChris Mason 	u64 search;
1356a7175319SChris Mason 	u64 target;
13576b80053dSChris Mason 	u64 nread = 0;
13583c69faecSChris Mason 	int direction = path->reada;
13595f39d397SChris Mason 	struct extent_buffer *eb;
13606b80053dSChris Mason 	u32 nr;
13616b80053dSChris Mason 	u32 blocksize;
13626b80053dSChris Mason 	u32 nscan = 0;
1363db94535dSChris Mason 
1364a6b6e75eSChris Mason 	if (level != 1)
13653c69faecSChris Mason 		return;
13663c69faecSChris Mason 
13676702ed49SChris Mason 	if (!path->nodes[level])
13686702ed49SChris Mason 		return;
13696702ed49SChris Mason 
13705f39d397SChris Mason 	node = path->nodes[level];
1371925baeddSChris Mason 
13723c69faecSChris Mason 	search = btrfs_node_blockptr(node, slot);
13736b80053dSChris Mason 	blocksize = btrfs_level_size(root, level - 1);
13746b80053dSChris Mason 	eb = btrfs_find_tree_block(root, search, blocksize);
13755f39d397SChris Mason 	if (eb) {
13765f39d397SChris Mason 		free_extent_buffer(eb);
13773c69faecSChris Mason 		return;
13783c69faecSChris Mason 	}
13793c69faecSChris Mason 
1380a7175319SChris Mason 	target = search;
13816b80053dSChris Mason 
13825f39d397SChris Mason 	nritems = btrfs_header_nritems(node);
13836b80053dSChris Mason 	nr = slot;
13843c69faecSChris Mason 	while (1) {
13856b80053dSChris Mason 		if (direction < 0) {
13866b80053dSChris Mason 			if (nr == 0)
13873c69faecSChris Mason 				break;
13886b80053dSChris Mason 			nr--;
13896b80053dSChris Mason 		} else if (direction > 0) {
13906b80053dSChris Mason 			nr++;
13916b80053dSChris Mason 			if (nr >= nritems)
13926b80053dSChris Mason 				break;
13933c69faecSChris Mason 		}
139401f46658SChris Mason 		if (path->reada < 0 && objectid) {
139501f46658SChris Mason 			btrfs_node_key(node, &disk_key, nr);
139601f46658SChris Mason 			if (btrfs_disk_key_objectid(&disk_key) != objectid)
139701f46658SChris Mason 				break;
139801f46658SChris Mason 		}
13996b80053dSChris Mason 		search = btrfs_node_blockptr(node, nr);
1400a7175319SChris Mason 		if ((search <= target && target - search <= 65536) ||
1401a7175319SChris Mason 		    (search > target && search - target <= 65536)) {
1402ca7a79adSChris Mason 			readahead_tree_block(root, search, blocksize,
1403ca7a79adSChris Mason 				     btrfs_node_ptr_generation(node, nr));
14046b80053dSChris Mason 			nread += blocksize;
14053c69faecSChris Mason 		}
14066b80053dSChris Mason 		nscan++;
1407a7175319SChris Mason 		if ((nread > 65536 || nscan > 32))
14086b80053dSChris Mason 			break;
14093c69faecSChris Mason 	}
14103c69faecSChris Mason }
1411925baeddSChris Mason 
1412d352ac68SChris Mason /*
1413b4ce94deSChris Mason  * returns -EAGAIN if it had to drop the path, or zero if everything was in
1414b4ce94deSChris Mason  * cache
1415b4ce94deSChris Mason  */
1416b4ce94deSChris Mason static noinline int reada_for_balance(struct btrfs_root *root,
1417b4ce94deSChris Mason 				      struct btrfs_path *path, int level)
1418b4ce94deSChris Mason {
1419b4ce94deSChris Mason 	int slot;
1420b4ce94deSChris Mason 	int nritems;
1421b4ce94deSChris Mason 	struct extent_buffer *parent;
1422b4ce94deSChris Mason 	struct extent_buffer *eb;
1423b4ce94deSChris Mason 	u64 gen;
1424b4ce94deSChris Mason 	u64 block1 = 0;
1425b4ce94deSChris Mason 	u64 block2 = 0;
1426b4ce94deSChris Mason 	int ret = 0;
1427b4ce94deSChris Mason 	int blocksize;
1428b4ce94deSChris Mason 
14298c594ea8SChris Mason 	parent = path->nodes[level + 1];
1430b4ce94deSChris Mason 	if (!parent)
1431b4ce94deSChris Mason 		return 0;
1432b4ce94deSChris Mason 
1433b4ce94deSChris Mason 	nritems = btrfs_header_nritems(parent);
14348c594ea8SChris Mason 	slot = path->slots[level + 1];
1435b4ce94deSChris Mason 	blocksize = btrfs_level_size(root, level);
1436b4ce94deSChris Mason 
1437b4ce94deSChris Mason 	if (slot > 0) {
1438b4ce94deSChris Mason 		block1 = btrfs_node_blockptr(parent, slot - 1);
1439b4ce94deSChris Mason 		gen = btrfs_node_ptr_generation(parent, slot - 1);
1440b4ce94deSChris Mason 		eb = btrfs_find_tree_block(root, block1, blocksize);
1441b4ce94deSChris Mason 		if (eb && btrfs_buffer_uptodate(eb, gen))
1442b4ce94deSChris Mason 			block1 = 0;
1443b4ce94deSChris Mason 		free_extent_buffer(eb);
1444b4ce94deSChris Mason 	}
14458c594ea8SChris Mason 	if (slot + 1 < nritems) {
1446b4ce94deSChris Mason 		block2 = btrfs_node_blockptr(parent, slot + 1);
1447b4ce94deSChris Mason 		gen = btrfs_node_ptr_generation(parent, slot + 1);
1448b4ce94deSChris Mason 		eb = btrfs_find_tree_block(root, block2, blocksize);
1449b4ce94deSChris Mason 		if (eb && btrfs_buffer_uptodate(eb, gen))
1450b4ce94deSChris Mason 			block2 = 0;
1451b4ce94deSChris Mason 		free_extent_buffer(eb);
1452b4ce94deSChris Mason 	}
1453b4ce94deSChris Mason 	if (block1 || block2) {
1454b4ce94deSChris Mason 		ret = -EAGAIN;
14558c594ea8SChris Mason 
14568c594ea8SChris Mason 		/* release the whole path */
1457b4ce94deSChris Mason 		btrfs_release_path(root, path);
14588c594ea8SChris Mason 
14598c594ea8SChris Mason 		/* read the blocks */
1460b4ce94deSChris Mason 		if (block1)
1461b4ce94deSChris Mason 			readahead_tree_block(root, block1, blocksize, 0);
1462b4ce94deSChris Mason 		if (block2)
1463b4ce94deSChris Mason 			readahead_tree_block(root, block2, blocksize, 0);
1464b4ce94deSChris Mason 
1465b4ce94deSChris Mason 		if (block1) {
1466b4ce94deSChris Mason 			eb = read_tree_block(root, block1, blocksize, 0);
1467b4ce94deSChris Mason 			free_extent_buffer(eb);
1468b4ce94deSChris Mason 		}
14698c594ea8SChris Mason 		if (block2) {
1470b4ce94deSChris Mason 			eb = read_tree_block(root, block2, blocksize, 0);
1471b4ce94deSChris Mason 			free_extent_buffer(eb);
1472b4ce94deSChris Mason 		}
1473b4ce94deSChris Mason 	}
1474b4ce94deSChris Mason 	return ret;
1475b4ce94deSChris Mason }
1476b4ce94deSChris Mason 
1477b4ce94deSChris Mason 
1478b4ce94deSChris Mason /*
1479d397712bSChris Mason  * when we walk down the tree, it is usually safe to unlock the higher layers
1480d397712bSChris Mason  * in the tree.  The exceptions are when our path goes through slot 0, because
1481d397712bSChris Mason  * operations on the tree might require changing key pointers higher up in the
1482d397712bSChris Mason  * tree.
1483d352ac68SChris Mason  *
1484d397712bSChris Mason  * callers might also have set path->keep_locks, which tells this code to keep
1485d397712bSChris Mason  * the lock if the path points to the last slot in the block.  This is part of
1486d397712bSChris Mason  * walking through the tree, and selecting the next slot in the higher block.
1487d352ac68SChris Mason  *
1488d397712bSChris Mason  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
1489d397712bSChris Mason  * if lowest_unlock is 1, level 0 won't be unlocked
1490d352ac68SChris Mason  */
1491e02119d5SChris Mason static noinline void unlock_up(struct btrfs_path *path, int level,
1492e02119d5SChris Mason 			       int lowest_unlock)
1493925baeddSChris Mason {
1494925baeddSChris Mason 	int i;
1495925baeddSChris Mason 	int skip_level = level;
1496051e1b9fSChris Mason 	int no_skips = 0;
1497925baeddSChris Mason 	struct extent_buffer *t;
1498925baeddSChris Mason 
1499925baeddSChris Mason 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1500925baeddSChris Mason 		if (!path->nodes[i])
1501925baeddSChris Mason 			break;
1502925baeddSChris Mason 		if (!path->locks[i])
1503925baeddSChris Mason 			break;
1504051e1b9fSChris Mason 		if (!no_skips && path->slots[i] == 0) {
1505925baeddSChris Mason 			skip_level = i + 1;
1506925baeddSChris Mason 			continue;
1507925baeddSChris Mason 		}
1508051e1b9fSChris Mason 		if (!no_skips && path->keep_locks) {
1509925baeddSChris Mason 			u32 nritems;
1510925baeddSChris Mason 			t = path->nodes[i];
1511925baeddSChris Mason 			nritems = btrfs_header_nritems(t);
1512051e1b9fSChris Mason 			if (nritems < 1 || path->slots[i] >= nritems - 1) {
1513925baeddSChris Mason 				skip_level = i + 1;
1514925baeddSChris Mason 				continue;
1515925baeddSChris Mason 			}
1516925baeddSChris Mason 		}
1517051e1b9fSChris Mason 		if (skip_level < i && i >= lowest_unlock)
1518051e1b9fSChris Mason 			no_skips = 1;
1519051e1b9fSChris Mason 
1520925baeddSChris Mason 		t = path->nodes[i];
1521925baeddSChris Mason 		if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1522925baeddSChris Mason 			btrfs_tree_unlock(t);
1523925baeddSChris Mason 			path->locks[i] = 0;
1524925baeddSChris Mason 		}
1525925baeddSChris Mason 	}
1526925baeddSChris Mason }
1527925baeddSChris Mason 
15283c69faecSChris Mason /*
1529b4ce94deSChris Mason  * This releases any locks held in the path starting at level and
1530b4ce94deSChris Mason  * going all the way up to the root.
1531b4ce94deSChris Mason  *
1532b4ce94deSChris Mason  * btrfs_search_slot will keep the lock held on higher nodes in a few
1533b4ce94deSChris Mason  * corner cases, such as COW of the block at slot zero in the node.  This
1534b4ce94deSChris Mason  * ignores those rules, and it should only be called when there are no
1535b4ce94deSChris Mason  * more updates to be done higher up in the tree.
1536b4ce94deSChris Mason  */
1537b4ce94deSChris Mason noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1538b4ce94deSChris Mason {
1539b4ce94deSChris Mason 	int i;
1540b4ce94deSChris Mason 
15415d4f98a2SYan Zheng 	if (path->keep_locks)
1542b4ce94deSChris Mason 		return;
1543b4ce94deSChris Mason 
1544b4ce94deSChris Mason 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1545b4ce94deSChris Mason 		if (!path->nodes[i])
154612f4daccSChris Mason 			continue;
1547b4ce94deSChris Mason 		if (!path->locks[i])
154812f4daccSChris Mason 			continue;
1549b4ce94deSChris Mason 		btrfs_tree_unlock(path->nodes[i]);
1550b4ce94deSChris Mason 		path->locks[i] = 0;
1551b4ce94deSChris Mason 	}
1552b4ce94deSChris Mason }
1553b4ce94deSChris Mason 
1554b4ce94deSChris Mason /*
1555c8c42864SChris Mason  * helper function for btrfs_search_slot.  The goal is to find a block
1556c8c42864SChris Mason  * in cache without setting the path to blocking.  If we find the block
1557c8c42864SChris Mason  * we return zero and the path is unchanged.
1558c8c42864SChris Mason  *
1559c8c42864SChris Mason  * If we can't find the block, we set the path blocking and do some
1560c8c42864SChris Mason  * reada.  -EAGAIN is returned and the search must be repeated.
1561c8c42864SChris Mason  */
1562c8c42864SChris Mason static int
1563c8c42864SChris Mason read_block_for_search(struct btrfs_trans_handle *trans,
1564c8c42864SChris Mason 		       struct btrfs_root *root, struct btrfs_path *p,
1565c8c42864SChris Mason 		       struct extent_buffer **eb_ret, int level, int slot,
1566c8c42864SChris Mason 		       struct btrfs_key *key)
1567c8c42864SChris Mason {
1568c8c42864SChris Mason 	u64 blocknr;
1569c8c42864SChris Mason 	u64 gen;
1570c8c42864SChris Mason 	u32 blocksize;
1571c8c42864SChris Mason 	struct extent_buffer *b = *eb_ret;
1572c8c42864SChris Mason 	struct extent_buffer *tmp;
157376a05b35SChris Mason 	int ret;
1574c8c42864SChris Mason 
1575c8c42864SChris Mason 	blocknr = btrfs_node_blockptr(b, slot);
1576c8c42864SChris Mason 	gen = btrfs_node_ptr_generation(b, slot);
1577c8c42864SChris Mason 	blocksize = btrfs_level_size(root, level - 1);
1578c8c42864SChris Mason 
1579c8c42864SChris Mason 	tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1580c8c42864SChris Mason 	if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
158176a05b35SChris Mason 		/*
158276a05b35SChris Mason 		 * we found an up to date block without sleeping, return
158376a05b35SChris Mason 		 * right away
158476a05b35SChris Mason 		 */
1585c8c42864SChris Mason 		*eb_ret = tmp;
1586c8c42864SChris Mason 		return 0;
1587c8c42864SChris Mason 	}
1588c8c42864SChris Mason 
1589c8c42864SChris Mason 	/*
1590c8c42864SChris Mason 	 * reduce lock contention at high levels
1591c8c42864SChris Mason 	 * of the btree by dropping locks before
159276a05b35SChris Mason 	 * we read.  Don't release the lock on the current
159376a05b35SChris Mason 	 * level because we need to walk this node to figure
159476a05b35SChris Mason 	 * out which blocks to read.
1595c8c42864SChris Mason 	 */
15968c594ea8SChris Mason 	btrfs_unlock_up_safe(p, level + 1);
15978c594ea8SChris Mason 	btrfs_set_path_blocking(p);
15988c594ea8SChris Mason 
1599c8c42864SChris Mason 	if (tmp)
1600c8c42864SChris Mason 		free_extent_buffer(tmp);
1601c8c42864SChris Mason 	if (p->reada)
1602c8c42864SChris Mason 		reada_for_search(root, p, level, slot, key->objectid);
1603c8c42864SChris Mason 
16048c594ea8SChris Mason 	btrfs_release_path(NULL, p);
160576a05b35SChris Mason 
160676a05b35SChris Mason 	ret = -EAGAIN;
1607c8c42864SChris Mason 	tmp = read_tree_block(root, blocknr, blocksize, gen);
160876a05b35SChris Mason 	if (tmp) {
160976a05b35SChris Mason 		/*
161076a05b35SChris Mason 		 * If the read above didn't mark this buffer up to date,
161176a05b35SChris Mason 		 * it will never end up being up to date.  Set ret to EIO now
161276a05b35SChris Mason 		 * and give up so that our caller doesn't loop forever
161376a05b35SChris Mason 		 * on our EAGAINs.
161476a05b35SChris Mason 		 */
161576a05b35SChris Mason 		if (!btrfs_buffer_uptodate(tmp, 0))
161676a05b35SChris Mason 			ret = -EIO;
1617c8c42864SChris Mason 		free_extent_buffer(tmp);
161876a05b35SChris Mason 	}
161976a05b35SChris Mason 	return ret;
1620c8c42864SChris Mason }
1621c8c42864SChris Mason 
1622c8c42864SChris Mason /*
1623c8c42864SChris Mason  * helper function for btrfs_search_slot.  This does all of the checks
1624c8c42864SChris Mason  * for node-level blocks and does any balancing required based on
1625c8c42864SChris Mason  * the ins_len.
1626c8c42864SChris Mason  *
1627c8c42864SChris Mason  * If no extra work was required, zero is returned.  If we had to
1628c8c42864SChris Mason  * drop the path, -EAGAIN is returned and btrfs_search_slot must
1629c8c42864SChris Mason  * start over
1630c8c42864SChris Mason  */
1631c8c42864SChris Mason static int
1632c8c42864SChris Mason setup_nodes_for_search(struct btrfs_trans_handle *trans,
1633c8c42864SChris Mason 		       struct btrfs_root *root, struct btrfs_path *p,
1634c8c42864SChris Mason 		       struct extent_buffer *b, int level, int ins_len)
1635c8c42864SChris Mason {
1636c8c42864SChris Mason 	int ret;
1637c8c42864SChris Mason 	if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1638c8c42864SChris Mason 	    BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1639c8c42864SChris Mason 		int sret;
1640c8c42864SChris Mason 
1641c8c42864SChris Mason 		sret = reada_for_balance(root, p, level);
1642c8c42864SChris Mason 		if (sret)
1643c8c42864SChris Mason 			goto again;
1644c8c42864SChris Mason 
1645c8c42864SChris Mason 		btrfs_set_path_blocking(p);
1646c8c42864SChris Mason 		sret = split_node(trans, root, p, level);
1647c8c42864SChris Mason 		btrfs_clear_path_blocking(p, NULL);
1648c8c42864SChris Mason 
1649c8c42864SChris Mason 		BUG_ON(sret > 0);
1650c8c42864SChris Mason 		if (sret) {
1651c8c42864SChris Mason 			ret = sret;
1652c8c42864SChris Mason 			goto done;
1653c8c42864SChris Mason 		}
1654c8c42864SChris Mason 		b = p->nodes[level];
1655c8c42864SChris Mason 	} else if (ins_len < 0 && btrfs_header_nritems(b) <
1656cfbb9308SChris Mason 		   BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
1657c8c42864SChris Mason 		int sret;
1658c8c42864SChris Mason 
1659c8c42864SChris Mason 		sret = reada_for_balance(root, p, level);
1660c8c42864SChris Mason 		if (sret)
1661c8c42864SChris Mason 			goto again;
1662c8c42864SChris Mason 
1663c8c42864SChris Mason 		btrfs_set_path_blocking(p);
1664c8c42864SChris Mason 		sret = balance_level(trans, root, p, level);
1665c8c42864SChris Mason 		btrfs_clear_path_blocking(p, NULL);
1666c8c42864SChris Mason 
1667c8c42864SChris Mason 		if (sret) {
1668c8c42864SChris Mason 			ret = sret;
1669c8c42864SChris Mason 			goto done;
1670c8c42864SChris Mason 		}
1671c8c42864SChris Mason 		b = p->nodes[level];
1672c8c42864SChris Mason 		if (!b) {
1673c8c42864SChris Mason 			btrfs_release_path(NULL, p);
1674c8c42864SChris Mason 			goto again;
1675c8c42864SChris Mason 		}
1676c8c42864SChris Mason 		BUG_ON(btrfs_header_nritems(b) == 1);
1677c8c42864SChris Mason 	}
1678c8c42864SChris Mason 	return 0;
1679c8c42864SChris Mason 
1680c8c42864SChris Mason again:
1681c8c42864SChris Mason 	ret = -EAGAIN;
1682c8c42864SChris Mason done:
1683c8c42864SChris Mason 	return ret;
1684c8c42864SChris Mason }
1685c8c42864SChris Mason 
1686c8c42864SChris Mason /*
168774123bd7SChris Mason  * look for key in the tree.  path is filled in with nodes along the way
168874123bd7SChris Mason  * if key is found, we return zero and you can find the item in the leaf
168974123bd7SChris Mason  * level of the path (level 0)
169074123bd7SChris Mason  *
169174123bd7SChris Mason  * If the key isn't found, the path points to the slot where it should
1692aa5d6bedSChris Mason  * be inserted, and 1 is returned.  If there are other errors during the
1693aa5d6bedSChris Mason  * search a negative error number is returned.
169497571fd0SChris Mason  *
169597571fd0SChris Mason  * if ins_len > 0, nodes and leaves will be split as we walk down the
169697571fd0SChris Mason  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
169797571fd0SChris Mason  * possible)
169874123bd7SChris Mason  */
1699e089f05cSChris Mason int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1700e089f05cSChris Mason 		      *root, struct btrfs_key *key, struct btrfs_path *p, int
1701e089f05cSChris Mason 		      ins_len, int cow)
1702be0e5c09SChris Mason {
17035f39d397SChris Mason 	struct extent_buffer *b;
1704be0e5c09SChris Mason 	int slot;
1705be0e5c09SChris Mason 	int ret;
170633c66f43SYan Zheng 	int err;
1707be0e5c09SChris Mason 	int level;
1708925baeddSChris Mason 	int lowest_unlock = 1;
17099f3a7427SChris Mason 	u8 lowest_level = 0;
17109f3a7427SChris Mason 
17116702ed49SChris Mason 	lowest_level = p->lowest_level;
1712323ac95bSChris Mason 	WARN_ON(lowest_level && ins_len > 0);
171322b0ebdaSChris Mason 	WARN_ON(p->nodes[0] != NULL);
171425179201SJosef Bacik 
1715925baeddSChris Mason 	if (ins_len < 0)
1716925baeddSChris Mason 		lowest_unlock = 2;
171765b51a00SChris Mason 
1718bb803951SChris Mason again:
17195d4f98a2SYan Zheng 	if (p->search_commit_root) {
17205d4f98a2SYan Zheng 		b = root->commit_root;
17215d4f98a2SYan Zheng 		extent_buffer_get(b);
17225d4f98a2SYan Zheng 		if (!p->skip_locking)
17235d4f98a2SYan Zheng 			btrfs_tree_lock(b);
17245d4f98a2SYan Zheng 	} else {
17255cd57b2cSChris Mason 		if (p->skip_locking)
17265cd57b2cSChris Mason 			b = btrfs_root_node(root);
17275cd57b2cSChris Mason 		else
1728925baeddSChris Mason 			b = btrfs_lock_root_node(root);
17295d4f98a2SYan Zheng 	}
1730925baeddSChris Mason 
1731eb60ceacSChris Mason 	while (b) {
17325f39d397SChris Mason 		level = btrfs_header_level(b);
173365b51a00SChris Mason 
173465b51a00SChris Mason 		/*
173565b51a00SChris Mason 		 * setup the path here so we can release it under lock
173665b51a00SChris Mason 		 * contention with the cow code
173765b51a00SChris Mason 		 */
173865b51a00SChris Mason 		p->nodes[level] = b;
173965b51a00SChris Mason 		if (!p->skip_locking)
174065b51a00SChris Mason 			p->locks[level] = 1;
174165b51a00SChris Mason 
174202217ed2SChris Mason 		if (cow) {
1743c8c42864SChris Mason 			/*
1744c8c42864SChris Mason 			 * if we don't really need to cow this block
1745c8c42864SChris Mason 			 * then we don't want to set the path blocking,
1746c8c42864SChris Mason 			 * so we test it here
1747c8c42864SChris Mason 			 */
17485d4f98a2SYan Zheng 			if (!should_cow_block(trans, root, b))
174965b51a00SChris Mason 				goto cow_done;
17505d4f98a2SYan Zheng 
1751b4ce94deSChris Mason 			btrfs_set_path_blocking(p);
1752b4ce94deSChris Mason 
175333c66f43SYan Zheng 			err = btrfs_cow_block(trans, root, b,
1754e20d96d6SChris Mason 					      p->nodes[level + 1],
17559fa8cfe7SChris Mason 					      p->slots[level + 1], &b);
175633c66f43SYan Zheng 			if (err) {
175733c66f43SYan Zheng 				ret = err;
175865b51a00SChris Mason 				goto done;
175954aa1f4dSChris Mason 			}
176002217ed2SChris Mason 		}
176165b51a00SChris Mason cow_done:
176202217ed2SChris Mason 		BUG_ON(!cow && ins_len);
17635f39d397SChris Mason 		if (level != btrfs_header_level(b))
17642c90e5d6SChris Mason 			WARN_ON(1);
17655f39d397SChris Mason 		level = btrfs_header_level(b);
176665b51a00SChris Mason 
1767eb60ceacSChris Mason 		p->nodes[level] = b;
17685cd57b2cSChris Mason 		if (!p->skip_locking)
1769925baeddSChris Mason 			p->locks[level] = 1;
177065b51a00SChris Mason 
17714008c04aSChris Mason 		btrfs_clear_path_blocking(p, NULL);
1772b4ce94deSChris Mason 
1773b4ce94deSChris Mason 		/*
1774b4ce94deSChris Mason 		 * we have a lock on b and as long as we aren't changing
1775b4ce94deSChris Mason 		 * the tree, there is no way to for the items in b to change.
1776b4ce94deSChris Mason 		 * It is safe to drop the lock on our parent before we
1777b4ce94deSChris Mason 		 * go through the expensive btree search on b.
1778b4ce94deSChris Mason 		 *
1779b4ce94deSChris Mason 		 * If cow is true, then we might be changing slot zero,
1780b4ce94deSChris Mason 		 * which may require changing the parent.  So, we can't
1781b4ce94deSChris Mason 		 * drop the lock until after we know which slot we're
1782b4ce94deSChris Mason 		 * operating on.
1783b4ce94deSChris Mason 		 */
1784b4ce94deSChris Mason 		if (!cow)
1785b4ce94deSChris Mason 			btrfs_unlock_up_safe(p, level + 1);
1786b4ce94deSChris Mason 
1787123abc88SChris Mason 		ret = check_block(root, p, level);
178865b51a00SChris Mason 		if (ret) {
178965b51a00SChris Mason 			ret = -1;
179065b51a00SChris Mason 			goto done;
179165b51a00SChris Mason 		}
1792925baeddSChris Mason 
17935f39d397SChris Mason 		ret = bin_search(b, key, level, &slot);
1794b4ce94deSChris Mason 
17955f39d397SChris Mason 		if (level != 0) {
179633c66f43SYan Zheng 			int dec = 0;
179733c66f43SYan Zheng 			if (ret && slot > 0) {
179833c66f43SYan Zheng 				dec = 1;
1799be0e5c09SChris Mason 				slot -= 1;
180033c66f43SYan Zheng 			}
1801be0e5c09SChris Mason 			p->slots[level] = slot;
180233c66f43SYan Zheng 			err = setup_nodes_for_search(trans, root, p, b, level,
1803c8c42864SChris Mason 						     ins_len);
180433c66f43SYan Zheng 			if (err == -EAGAIN)
1805b4ce94deSChris Mason 				goto again;
180633c66f43SYan Zheng 			if (err) {
180733c66f43SYan Zheng 				ret = err;
180865b51a00SChris Mason 				goto done;
180933c66f43SYan Zheng 			}
18105c680ed6SChris Mason 			b = p->nodes[level];
18115c680ed6SChris Mason 			slot = p->slots[level];
1812b4ce94deSChris Mason 
1813f9efa9c7SChris Mason 			unlock_up(p, level, lowest_unlock);
1814f9efa9c7SChris Mason 
1815925baeddSChris Mason 			if (level == lowest_level) {
181633c66f43SYan Zheng 				if (dec)
181733c66f43SYan Zheng 					p->slots[level]++;
18185b21f2edSZheng Yan 				goto done;
1819925baeddSChris Mason 			}
1820ca7a79adSChris Mason 
182133c66f43SYan Zheng 			err = read_block_for_search(trans, root, p,
1822c8c42864SChris Mason 						    &b, level, slot, key);
182333c66f43SYan Zheng 			if (err == -EAGAIN)
1824051e1b9fSChris Mason 				goto again;
182533c66f43SYan Zheng 			if (err) {
182633c66f43SYan Zheng 				ret = err;
182776a05b35SChris Mason 				goto done;
182833c66f43SYan Zheng 			}
182976a05b35SChris Mason 
1830b4ce94deSChris Mason 			if (!p->skip_locking) {
18314008c04aSChris Mason 				btrfs_clear_path_blocking(p, NULL);
183233c66f43SYan Zheng 				err = btrfs_try_spin_lock(b);
1833b4ce94deSChris Mason 
183433c66f43SYan Zheng 				if (!err) {
1835b4ce94deSChris Mason 					btrfs_set_path_blocking(p);
1836925baeddSChris Mason 					btrfs_tree_lock(b);
18374008c04aSChris Mason 					btrfs_clear_path_blocking(p, b);
1838b4ce94deSChris Mason 				}
1839b4ce94deSChris Mason 			}
1840be0e5c09SChris Mason 		} else {
1841be0e5c09SChris Mason 			p->slots[level] = slot;
184287b29b20SYan Zheng 			if (ins_len > 0 &&
184387b29b20SYan Zheng 			    btrfs_leaf_free_space(root, b) < ins_len) {
1844b4ce94deSChris Mason 				btrfs_set_path_blocking(p);
184533c66f43SYan Zheng 				err = split_leaf(trans, root, key,
1846cc0c5538SChris Mason 						 p, ins_len, ret == 0);
18474008c04aSChris Mason 				btrfs_clear_path_blocking(p, NULL);
1848b4ce94deSChris Mason 
184933c66f43SYan Zheng 				BUG_ON(err > 0);
185033c66f43SYan Zheng 				if (err) {
185133c66f43SYan Zheng 					ret = err;
185265b51a00SChris Mason 					goto done;
185365b51a00SChris Mason 				}
18545c680ed6SChris Mason 			}
1855459931ecSChris Mason 			if (!p->search_for_split)
1856925baeddSChris Mason 				unlock_up(p, level, lowest_unlock);
185765b51a00SChris Mason 			goto done;
185865b51a00SChris Mason 		}
185965b51a00SChris Mason 	}
186065b51a00SChris Mason 	ret = 1;
186165b51a00SChris Mason done:
1862b4ce94deSChris Mason 	/*
1863b4ce94deSChris Mason 	 * we don't really know what they plan on doing with the path
1864b4ce94deSChris Mason 	 * from here on, so for now just mark it as blocking
1865b4ce94deSChris Mason 	 */
1866b9473439SChris Mason 	if (!p->leave_spinning)
1867b4ce94deSChris Mason 		btrfs_set_path_blocking(p);
186876a05b35SChris Mason 	if (ret < 0)
186976a05b35SChris Mason 		btrfs_release_path(root, p);
1870be0e5c09SChris Mason 	return ret;
1871be0e5c09SChris Mason }
1872be0e5c09SChris Mason 
187374123bd7SChris Mason /*
187474123bd7SChris Mason  * adjust the pointers going up the tree, starting at level
187574123bd7SChris Mason  * making sure the right key of each node is points to 'key'.
187674123bd7SChris Mason  * This is used after shifting pointers to the left, so it stops
187774123bd7SChris Mason  * fixing up pointers when a given leaf/node is not in slot 0 of the
187874123bd7SChris Mason  * higher levels
1879aa5d6bedSChris Mason  *
1880aa5d6bedSChris Mason  * If this fails to write a tree block, it returns -1, but continues
1881aa5d6bedSChris Mason  * fixing up the blocks in ram so the tree is consistent.
188274123bd7SChris Mason  */
18835f39d397SChris Mason static int fixup_low_keys(struct btrfs_trans_handle *trans,
18845f39d397SChris Mason 			  struct btrfs_root *root, struct btrfs_path *path,
18855f39d397SChris Mason 			  struct btrfs_disk_key *key, int level)
1886be0e5c09SChris Mason {
1887be0e5c09SChris Mason 	int i;
1888aa5d6bedSChris Mason 	int ret = 0;
18895f39d397SChris Mason 	struct extent_buffer *t;
18905f39d397SChris Mason 
1891234b63a0SChris Mason 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1892be0e5c09SChris Mason 		int tslot = path->slots[i];
1893eb60ceacSChris Mason 		if (!path->nodes[i])
1894be0e5c09SChris Mason 			break;
18955f39d397SChris Mason 		t = path->nodes[i];
18965f39d397SChris Mason 		btrfs_set_node_key(t, key, tslot);
1897d6025579SChris Mason 		btrfs_mark_buffer_dirty(path->nodes[i]);
1898be0e5c09SChris Mason 		if (tslot != 0)
1899be0e5c09SChris Mason 			break;
1900be0e5c09SChris Mason 	}
1901aa5d6bedSChris Mason 	return ret;
1902be0e5c09SChris Mason }
1903be0e5c09SChris Mason 
190474123bd7SChris Mason /*
190531840ae1SZheng Yan  * update item key.
190631840ae1SZheng Yan  *
190731840ae1SZheng Yan  * This function isn't completely safe. It's the caller's responsibility
190831840ae1SZheng Yan  * that the new key won't break the order
190931840ae1SZheng Yan  */
191031840ae1SZheng Yan int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
191131840ae1SZheng Yan 			    struct btrfs_root *root, struct btrfs_path *path,
191231840ae1SZheng Yan 			    struct btrfs_key *new_key)
191331840ae1SZheng Yan {
191431840ae1SZheng Yan 	struct btrfs_disk_key disk_key;
191531840ae1SZheng Yan 	struct extent_buffer *eb;
191631840ae1SZheng Yan 	int slot;
191731840ae1SZheng Yan 
191831840ae1SZheng Yan 	eb = path->nodes[0];
191931840ae1SZheng Yan 	slot = path->slots[0];
192031840ae1SZheng Yan 	if (slot > 0) {
192131840ae1SZheng Yan 		btrfs_item_key(eb, &disk_key, slot - 1);
192231840ae1SZheng Yan 		if (comp_keys(&disk_key, new_key) >= 0)
192331840ae1SZheng Yan 			return -1;
192431840ae1SZheng Yan 	}
192531840ae1SZheng Yan 	if (slot < btrfs_header_nritems(eb) - 1) {
192631840ae1SZheng Yan 		btrfs_item_key(eb, &disk_key, slot + 1);
192731840ae1SZheng Yan 		if (comp_keys(&disk_key, new_key) <= 0)
192831840ae1SZheng Yan 			return -1;
192931840ae1SZheng Yan 	}
193031840ae1SZheng Yan 
193131840ae1SZheng Yan 	btrfs_cpu_key_to_disk(&disk_key, new_key);
193231840ae1SZheng Yan 	btrfs_set_item_key(eb, &disk_key, slot);
193331840ae1SZheng Yan 	btrfs_mark_buffer_dirty(eb);
193431840ae1SZheng Yan 	if (slot == 0)
193531840ae1SZheng Yan 		fixup_low_keys(trans, root, path, &disk_key, 1);
193631840ae1SZheng Yan 	return 0;
193731840ae1SZheng Yan }
193831840ae1SZheng Yan 
193931840ae1SZheng Yan /*
194074123bd7SChris Mason  * try to push data from one node into the next node left in the
194179f95c82SChris Mason  * tree.
1942aa5d6bedSChris Mason  *
1943aa5d6bedSChris Mason  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1944aa5d6bedSChris Mason  * error, and > 0 if there was no room in the left hand block.
194574123bd7SChris Mason  */
194698ed5174SChris Mason static int push_node_left(struct btrfs_trans_handle *trans,
194798ed5174SChris Mason 			  struct btrfs_root *root, struct extent_buffer *dst,
1948971a1f66SChris Mason 			  struct extent_buffer *src, int empty)
1949be0e5c09SChris Mason {
1950be0e5c09SChris Mason 	int push_items = 0;
1951bb803951SChris Mason 	int src_nritems;
1952bb803951SChris Mason 	int dst_nritems;
1953aa5d6bedSChris Mason 	int ret = 0;
1954be0e5c09SChris Mason 
19555f39d397SChris Mason 	src_nritems = btrfs_header_nritems(src);
19565f39d397SChris Mason 	dst_nritems = btrfs_header_nritems(dst);
1957123abc88SChris Mason 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
19587bb86316SChris Mason 	WARN_ON(btrfs_header_generation(src) != trans->transid);
19597bb86316SChris Mason 	WARN_ON(btrfs_header_generation(dst) != trans->transid);
196054aa1f4dSChris Mason 
1961bce4eae9SChris Mason 	if (!empty && src_nritems <= 8)
1962971a1f66SChris Mason 		return 1;
1963971a1f66SChris Mason 
1964d397712bSChris Mason 	if (push_items <= 0)
1965be0e5c09SChris Mason 		return 1;
1966be0e5c09SChris Mason 
1967bce4eae9SChris Mason 	if (empty) {
1968971a1f66SChris Mason 		push_items = min(src_nritems, push_items);
1969bce4eae9SChris Mason 		if (push_items < src_nritems) {
1970bce4eae9SChris Mason 			/* leave at least 8 pointers in the node if
1971bce4eae9SChris Mason 			 * we aren't going to empty it
1972bce4eae9SChris Mason 			 */
1973bce4eae9SChris Mason 			if (src_nritems - push_items < 8) {
1974bce4eae9SChris Mason 				if (push_items <= 8)
1975bce4eae9SChris Mason 					return 1;
1976bce4eae9SChris Mason 				push_items -= 8;
1977bce4eae9SChris Mason 			}
1978bce4eae9SChris Mason 		}
1979bce4eae9SChris Mason 	} else
1980bce4eae9SChris Mason 		push_items = min(src_nritems - 8, push_items);
198179f95c82SChris Mason 
19825f39d397SChris Mason 	copy_extent_buffer(dst, src,
19835f39d397SChris Mason 			   btrfs_node_key_ptr_offset(dst_nritems),
19845f39d397SChris Mason 			   btrfs_node_key_ptr_offset(0),
1985123abc88SChris Mason 			   push_items * sizeof(struct btrfs_key_ptr));
19865f39d397SChris Mason 
1987bb803951SChris Mason 	if (push_items < src_nritems) {
19885f39d397SChris Mason 		memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
19895f39d397SChris Mason 				      btrfs_node_key_ptr_offset(push_items),
1990e2fa7227SChris Mason 				      (src_nritems - push_items) *
1991123abc88SChris Mason 				      sizeof(struct btrfs_key_ptr));
1992bb803951SChris Mason 	}
19935f39d397SChris Mason 	btrfs_set_header_nritems(src, src_nritems - push_items);
19945f39d397SChris Mason 	btrfs_set_header_nritems(dst, dst_nritems + push_items);
19955f39d397SChris Mason 	btrfs_mark_buffer_dirty(src);
19965f39d397SChris Mason 	btrfs_mark_buffer_dirty(dst);
199731840ae1SZheng Yan 
1998bb803951SChris Mason 	return ret;
1999be0e5c09SChris Mason }
2000be0e5c09SChris Mason 
200197571fd0SChris Mason /*
200279f95c82SChris Mason  * try to push data from one node into the next node right in the
200379f95c82SChris Mason  * tree.
200479f95c82SChris Mason  *
200579f95c82SChris Mason  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
200679f95c82SChris Mason  * error, and > 0 if there was no room in the right hand block.
200779f95c82SChris Mason  *
200879f95c82SChris Mason  * this will  only push up to 1/2 the contents of the left node over
200979f95c82SChris Mason  */
20105f39d397SChris Mason static int balance_node_right(struct btrfs_trans_handle *trans,
20115f39d397SChris Mason 			      struct btrfs_root *root,
20125f39d397SChris Mason 			      struct extent_buffer *dst,
20135f39d397SChris Mason 			      struct extent_buffer *src)
201479f95c82SChris Mason {
201579f95c82SChris Mason 	int push_items = 0;
201679f95c82SChris Mason 	int max_push;
201779f95c82SChris Mason 	int src_nritems;
201879f95c82SChris Mason 	int dst_nritems;
201979f95c82SChris Mason 	int ret = 0;
202079f95c82SChris Mason 
20217bb86316SChris Mason 	WARN_ON(btrfs_header_generation(src) != trans->transid);
20227bb86316SChris Mason 	WARN_ON(btrfs_header_generation(dst) != trans->transid);
20237bb86316SChris Mason 
20245f39d397SChris Mason 	src_nritems = btrfs_header_nritems(src);
20255f39d397SChris Mason 	dst_nritems = btrfs_header_nritems(dst);
2026123abc88SChris Mason 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
2027d397712bSChris Mason 	if (push_items <= 0)
202879f95c82SChris Mason 		return 1;
2029bce4eae9SChris Mason 
2030d397712bSChris Mason 	if (src_nritems < 4)
2031bce4eae9SChris Mason 		return 1;
203279f95c82SChris Mason 
203379f95c82SChris Mason 	max_push = src_nritems / 2 + 1;
203479f95c82SChris Mason 	/* don't try to empty the node */
2035d397712bSChris Mason 	if (max_push >= src_nritems)
203679f95c82SChris Mason 		return 1;
2037252c38f0SYan 
203879f95c82SChris Mason 	if (max_push < push_items)
203979f95c82SChris Mason 		push_items = max_push;
204079f95c82SChris Mason 
20415f39d397SChris Mason 	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
20425f39d397SChris Mason 				      btrfs_node_key_ptr_offset(0),
20435f39d397SChris Mason 				      (dst_nritems) *
20445f39d397SChris Mason 				      sizeof(struct btrfs_key_ptr));
2045d6025579SChris Mason 
20465f39d397SChris Mason 	copy_extent_buffer(dst, src,
20475f39d397SChris Mason 			   btrfs_node_key_ptr_offset(0),
20485f39d397SChris Mason 			   btrfs_node_key_ptr_offset(src_nritems - push_items),
2049123abc88SChris Mason 			   push_items * sizeof(struct btrfs_key_ptr));
205079f95c82SChris Mason 
20515f39d397SChris Mason 	btrfs_set_header_nritems(src, src_nritems - push_items);
20525f39d397SChris Mason 	btrfs_set_header_nritems(dst, dst_nritems + push_items);
205379f95c82SChris Mason 
20545f39d397SChris Mason 	btrfs_mark_buffer_dirty(src);
20555f39d397SChris Mason 	btrfs_mark_buffer_dirty(dst);
205631840ae1SZheng Yan 
205779f95c82SChris Mason 	return ret;
205879f95c82SChris Mason }
205979f95c82SChris Mason 
206079f95c82SChris Mason /*
206197571fd0SChris Mason  * helper function to insert a new root level in the tree.
206297571fd0SChris Mason  * A new node is allocated, and a single item is inserted to
206397571fd0SChris Mason  * point to the existing root
2064aa5d6bedSChris Mason  *
2065aa5d6bedSChris Mason  * returns zero on success or < 0 on failure.
206697571fd0SChris Mason  */
2067d397712bSChris Mason static noinline int insert_new_root(struct btrfs_trans_handle *trans,
20685f39d397SChris Mason 			   struct btrfs_root *root,
20695f39d397SChris Mason 			   struct btrfs_path *path, int level)
207074123bd7SChris Mason {
20717bb86316SChris Mason 	u64 lower_gen;
20725f39d397SChris Mason 	struct extent_buffer *lower;
20735f39d397SChris Mason 	struct extent_buffer *c;
2074925baeddSChris Mason 	struct extent_buffer *old;
20755f39d397SChris Mason 	struct btrfs_disk_key lower_key;
20765c680ed6SChris Mason 
20775c680ed6SChris Mason 	BUG_ON(path->nodes[level]);
20785c680ed6SChris Mason 	BUG_ON(path->nodes[level-1] != root->node);
20795c680ed6SChris Mason 
20807bb86316SChris Mason 	lower = path->nodes[level-1];
20817bb86316SChris Mason 	if (level == 1)
20827bb86316SChris Mason 		btrfs_item_key(lower, &lower_key, 0);
20837bb86316SChris Mason 	else
20847bb86316SChris Mason 		btrfs_node_key(lower, &lower_key, 0);
20857bb86316SChris Mason 
208631840ae1SZheng Yan 	c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
20875d4f98a2SYan Zheng 				   root->root_key.objectid, &lower_key,
2088ad3d81baSChristoph Hellwig 				   level, root->node->start, 0);
20895f39d397SChris Mason 	if (IS_ERR(c))
20905f39d397SChris Mason 		return PTR_ERR(c);
2091925baeddSChris Mason 
2092f0486c68SYan, Zheng 	root_add_used(root, root->nodesize);
2093f0486c68SYan, Zheng 
20945d4f98a2SYan Zheng 	memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
20955f39d397SChris Mason 	btrfs_set_header_nritems(c, 1);
20965f39d397SChris Mason 	btrfs_set_header_level(c, level);
2097db94535dSChris Mason 	btrfs_set_header_bytenr(c, c->start);
20985f39d397SChris Mason 	btrfs_set_header_generation(c, trans->transid);
20995d4f98a2SYan Zheng 	btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
21005f39d397SChris Mason 	btrfs_set_header_owner(c, root->root_key.objectid);
2101d5719762SChris Mason 
21025f39d397SChris Mason 	write_extent_buffer(c, root->fs_info->fsid,
21035f39d397SChris Mason 			    (unsigned long)btrfs_header_fsid(c),
21045f39d397SChris Mason 			    BTRFS_FSID_SIZE);
2105e17cade2SChris Mason 
2106e17cade2SChris Mason 	write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
2107e17cade2SChris Mason 			    (unsigned long)btrfs_header_chunk_tree_uuid(c),
2108e17cade2SChris Mason 			    BTRFS_UUID_SIZE);
2109e17cade2SChris Mason 
21105f39d397SChris Mason 	btrfs_set_node_key(c, &lower_key, 0);
2111db94535dSChris Mason 	btrfs_set_node_blockptr(c, 0, lower->start);
21127bb86316SChris Mason 	lower_gen = btrfs_header_generation(lower);
211331840ae1SZheng Yan 	WARN_ON(lower_gen != trans->transid);
21147bb86316SChris Mason 
21157bb86316SChris Mason 	btrfs_set_node_ptr_generation(c, 0, lower_gen);
21165f39d397SChris Mason 
21175f39d397SChris Mason 	btrfs_mark_buffer_dirty(c);
2118d5719762SChris Mason 
2119925baeddSChris Mason 	spin_lock(&root->node_lock);
2120925baeddSChris Mason 	old = root->node;
21215f39d397SChris Mason 	root->node = c;
2122925baeddSChris Mason 	spin_unlock(&root->node_lock);
2123925baeddSChris Mason 
2124925baeddSChris Mason 	/* the super has an extra ref to root->node */
2125925baeddSChris Mason 	free_extent_buffer(old);
2126925baeddSChris Mason 
21270b86a832SChris Mason 	add_root_to_dirty_list(root);
21285f39d397SChris Mason 	extent_buffer_get(c);
21295f39d397SChris Mason 	path->nodes[level] = c;
2130925baeddSChris Mason 	path->locks[level] = 1;
213174123bd7SChris Mason 	path->slots[level] = 0;
213274123bd7SChris Mason 	return 0;
213374123bd7SChris Mason }
21345c680ed6SChris Mason 
21355c680ed6SChris Mason /*
21365c680ed6SChris Mason  * worker function to insert a single pointer in a node.
21375c680ed6SChris Mason  * the node should have enough room for the pointer already
213897571fd0SChris Mason  *
21395c680ed6SChris Mason  * slot and level indicate where you want the key to go, and
21405c680ed6SChris Mason  * blocknr is the block the key points to.
2141aa5d6bedSChris Mason  *
2142aa5d6bedSChris Mason  * returns zero on success and < 0 on any error
21435c680ed6SChris Mason  */
2144e089f05cSChris Mason static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2145e089f05cSChris Mason 		      *root, struct btrfs_path *path, struct btrfs_disk_key
2146db94535dSChris Mason 		      *key, u64 bytenr, int slot, int level)
21475c680ed6SChris Mason {
21485f39d397SChris Mason 	struct extent_buffer *lower;
21495c680ed6SChris Mason 	int nritems;
21505c680ed6SChris Mason 
21515c680ed6SChris Mason 	BUG_ON(!path->nodes[level]);
2152f0486c68SYan, Zheng 	btrfs_assert_tree_locked(path->nodes[level]);
21535f39d397SChris Mason 	lower = path->nodes[level];
21545f39d397SChris Mason 	nritems = btrfs_header_nritems(lower);
2155c293498bSStoyan Gaydarov 	BUG_ON(slot > nritems);
2156123abc88SChris Mason 	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
215774123bd7SChris Mason 		BUG();
215874123bd7SChris Mason 	if (slot != nritems) {
21595f39d397SChris Mason 		memmove_extent_buffer(lower,
21605f39d397SChris Mason 			      btrfs_node_key_ptr_offset(slot + 1),
21615f39d397SChris Mason 			      btrfs_node_key_ptr_offset(slot),
2162123abc88SChris Mason 			      (nritems - slot) * sizeof(struct btrfs_key_ptr));
216374123bd7SChris Mason 	}
21645f39d397SChris Mason 	btrfs_set_node_key(lower, key, slot);
2165db94535dSChris Mason 	btrfs_set_node_blockptr(lower, slot, bytenr);
216674493f7aSChris Mason 	WARN_ON(trans->transid == 0);
216774493f7aSChris Mason 	btrfs_set_node_ptr_generation(lower, slot, trans->transid);
21685f39d397SChris Mason 	btrfs_set_header_nritems(lower, nritems + 1);
21695f39d397SChris Mason 	btrfs_mark_buffer_dirty(lower);
217074123bd7SChris Mason 	return 0;
217174123bd7SChris Mason }
217274123bd7SChris Mason 
217397571fd0SChris Mason /*
217497571fd0SChris Mason  * split the node at the specified level in path in two.
217597571fd0SChris Mason  * The path is corrected to point to the appropriate node after the split
217697571fd0SChris Mason  *
217797571fd0SChris Mason  * Before splitting this tries to make some room in the node by pushing
217897571fd0SChris Mason  * left and right, if either one works, it returns right away.
2179aa5d6bedSChris Mason  *
2180aa5d6bedSChris Mason  * returns 0 on success and < 0 on failure
218197571fd0SChris Mason  */
2182e02119d5SChris Mason static noinline int split_node(struct btrfs_trans_handle *trans,
2183e02119d5SChris Mason 			       struct btrfs_root *root,
2184e02119d5SChris Mason 			       struct btrfs_path *path, int level)
2185be0e5c09SChris Mason {
21865f39d397SChris Mason 	struct extent_buffer *c;
21875f39d397SChris Mason 	struct extent_buffer *split;
21885f39d397SChris Mason 	struct btrfs_disk_key disk_key;
2189be0e5c09SChris Mason 	int mid;
21905c680ed6SChris Mason 	int ret;
2191aa5d6bedSChris Mason 	int wret;
21927518a238SChris Mason 	u32 c_nritems;
2193be0e5c09SChris Mason 
21945f39d397SChris Mason 	c = path->nodes[level];
21957bb86316SChris Mason 	WARN_ON(btrfs_header_generation(c) != trans->transid);
21965f39d397SChris Mason 	if (c == root->node) {
21975c680ed6SChris Mason 		/* trying to split the root, lets make a new one */
2198e089f05cSChris Mason 		ret = insert_new_root(trans, root, path, level + 1);
21995c680ed6SChris Mason 		if (ret)
22005c680ed6SChris Mason 			return ret;
2201b3612421SChris Mason 	} else {
2202e66f709bSChris Mason 		ret = push_nodes_for_insert(trans, root, path, level);
22035f39d397SChris Mason 		c = path->nodes[level];
22045f39d397SChris Mason 		if (!ret && btrfs_header_nritems(c) <
2205c448acf0SChris Mason 		    BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
2206e66f709bSChris Mason 			return 0;
220754aa1f4dSChris Mason 		if (ret < 0)
220854aa1f4dSChris Mason 			return ret;
22095c680ed6SChris Mason 	}
2210e66f709bSChris Mason 
22115f39d397SChris Mason 	c_nritems = btrfs_header_nritems(c);
22125d4f98a2SYan Zheng 	mid = (c_nritems + 1) / 2;
22135d4f98a2SYan Zheng 	btrfs_node_key(c, &disk_key, mid);
22147bb86316SChris Mason 
22155d4f98a2SYan Zheng 	split = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
22167bb86316SChris Mason 					root->root_key.objectid,
22175d4f98a2SYan Zheng 					&disk_key, level, c->start, 0);
22185f39d397SChris Mason 	if (IS_ERR(split))
22195f39d397SChris Mason 		return PTR_ERR(split);
222054aa1f4dSChris Mason 
2221f0486c68SYan, Zheng 	root_add_used(root, root->nodesize);
2222f0486c68SYan, Zheng 
22235d4f98a2SYan Zheng 	memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
22245f39d397SChris Mason 	btrfs_set_header_level(split, btrfs_header_level(c));
2225db94535dSChris Mason 	btrfs_set_header_bytenr(split, split->start);
22265f39d397SChris Mason 	btrfs_set_header_generation(split, trans->transid);
22275d4f98a2SYan Zheng 	btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
22285f39d397SChris Mason 	btrfs_set_header_owner(split, root->root_key.objectid);
22295f39d397SChris Mason 	write_extent_buffer(split, root->fs_info->fsid,
22305f39d397SChris Mason 			    (unsigned long)btrfs_header_fsid(split),
22315f39d397SChris Mason 			    BTRFS_FSID_SIZE);
2232e17cade2SChris Mason 	write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2233e17cade2SChris Mason 			    (unsigned long)btrfs_header_chunk_tree_uuid(split),
2234e17cade2SChris Mason 			    BTRFS_UUID_SIZE);
22355f39d397SChris Mason 
22365f39d397SChris Mason 
22375f39d397SChris Mason 	copy_extent_buffer(split, c,
22385f39d397SChris Mason 			   btrfs_node_key_ptr_offset(0),
22395f39d397SChris Mason 			   btrfs_node_key_ptr_offset(mid),
2240123abc88SChris Mason 			   (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
22415f39d397SChris Mason 	btrfs_set_header_nritems(split, c_nritems - mid);
22425f39d397SChris Mason 	btrfs_set_header_nritems(c, mid);
2243aa5d6bedSChris Mason 	ret = 0;
2244aa5d6bedSChris Mason 
22455f39d397SChris Mason 	btrfs_mark_buffer_dirty(c);
22465f39d397SChris Mason 	btrfs_mark_buffer_dirty(split);
22475f39d397SChris Mason 
2248db94535dSChris Mason 	wret = insert_ptr(trans, root, path, &disk_key, split->start,
22495f39d397SChris Mason 			  path->slots[level + 1] + 1,
2250123abc88SChris Mason 			  level + 1);
2251aa5d6bedSChris Mason 	if (wret)
2252aa5d6bedSChris Mason 		ret = wret;
2253aa5d6bedSChris Mason 
22545de08d7dSChris Mason 	if (path->slots[level] >= mid) {
22555c680ed6SChris Mason 		path->slots[level] -= mid;
2256925baeddSChris Mason 		btrfs_tree_unlock(c);
22575f39d397SChris Mason 		free_extent_buffer(c);
22585f39d397SChris Mason 		path->nodes[level] = split;
22595c680ed6SChris Mason 		path->slots[level + 1] += 1;
2260eb60ceacSChris Mason 	} else {
2261925baeddSChris Mason 		btrfs_tree_unlock(split);
22625f39d397SChris Mason 		free_extent_buffer(split);
2263be0e5c09SChris Mason 	}
2264aa5d6bedSChris Mason 	return ret;
2265be0e5c09SChris Mason }
2266be0e5c09SChris Mason 
226774123bd7SChris Mason /*
226874123bd7SChris Mason  * how many bytes are required to store the items in a leaf.  start
226974123bd7SChris Mason  * and nr indicate which items in the leaf to check.  This totals up the
227074123bd7SChris Mason  * space used both by the item structs and the item data
227174123bd7SChris Mason  */
22725f39d397SChris Mason static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2273be0e5c09SChris Mason {
2274be0e5c09SChris Mason 	int data_len;
22755f39d397SChris Mason 	int nritems = btrfs_header_nritems(l);
2276d4dbff95SChris Mason 	int end = min(nritems, start + nr) - 1;
2277be0e5c09SChris Mason 
2278be0e5c09SChris Mason 	if (!nr)
2279be0e5c09SChris Mason 		return 0;
22805f39d397SChris Mason 	data_len = btrfs_item_end_nr(l, start);
22815f39d397SChris Mason 	data_len = data_len - btrfs_item_offset_nr(l, end);
22820783fcfcSChris Mason 	data_len += sizeof(struct btrfs_item) * nr;
2283d4dbff95SChris Mason 	WARN_ON(data_len < 0);
2284be0e5c09SChris Mason 	return data_len;
2285be0e5c09SChris Mason }
2286be0e5c09SChris Mason 
228774123bd7SChris Mason /*
2288d4dbff95SChris Mason  * The space between the end of the leaf items and
2289d4dbff95SChris Mason  * the start of the leaf data.  IOW, how much room
2290d4dbff95SChris Mason  * the leaf has left for both items and data
2291d4dbff95SChris Mason  */
2292d397712bSChris Mason noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2293e02119d5SChris Mason 				   struct extent_buffer *leaf)
2294d4dbff95SChris Mason {
22955f39d397SChris Mason 	int nritems = btrfs_header_nritems(leaf);
22965f39d397SChris Mason 	int ret;
22975f39d397SChris Mason 	ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
22985f39d397SChris Mason 	if (ret < 0) {
2299d397712bSChris Mason 		printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2300d397712bSChris Mason 		       "used %d nritems %d\n",
2301ae2f5411SJens Axboe 		       ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
23025f39d397SChris Mason 		       leaf_space_used(leaf, 0, nritems), nritems);
23035f39d397SChris Mason 	}
23045f39d397SChris Mason 	return ret;
2305d4dbff95SChris Mason }
2306d4dbff95SChris Mason 
230744871b1bSChris Mason static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
230844871b1bSChris Mason 				      struct btrfs_root *root,
230944871b1bSChris Mason 				      struct btrfs_path *path,
231044871b1bSChris Mason 				      int data_size, int empty,
231144871b1bSChris Mason 				      struct extent_buffer *right,
231244871b1bSChris Mason 				      int free_space, u32 left_nritems)
231300ec4c51SChris Mason {
23145f39d397SChris Mason 	struct extent_buffer *left = path->nodes[0];
231544871b1bSChris Mason 	struct extent_buffer *upper = path->nodes[1];
23165f39d397SChris Mason 	struct btrfs_disk_key disk_key;
231700ec4c51SChris Mason 	int slot;
231834a38218SChris Mason 	u32 i;
231900ec4c51SChris Mason 	int push_space = 0;
232000ec4c51SChris Mason 	int push_items = 0;
23210783fcfcSChris Mason 	struct btrfs_item *item;
232234a38218SChris Mason 	u32 nr;
23237518a238SChris Mason 	u32 right_nritems;
23245f39d397SChris Mason 	u32 data_end;
2325db94535dSChris Mason 	u32 this_item_size;
232600ec4c51SChris Mason 
232734a38218SChris Mason 	if (empty)
232834a38218SChris Mason 		nr = 0;
232934a38218SChris Mason 	else
233034a38218SChris Mason 		nr = 1;
233134a38218SChris Mason 
233231840ae1SZheng Yan 	if (path->slots[0] >= left_nritems)
233387b29b20SYan Zheng 		push_space += data_size;
233431840ae1SZheng Yan 
233544871b1bSChris Mason 	slot = path->slots[1];
233634a38218SChris Mason 	i = left_nritems - 1;
233734a38218SChris Mason 	while (i >= nr) {
23385f39d397SChris Mason 		item = btrfs_item_nr(left, i);
2339db94535dSChris Mason 
234031840ae1SZheng Yan 		if (!empty && push_items > 0) {
234131840ae1SZheng Yan 			if (path->slots[0] > i)
234231840ae1SZheng Yan 				break;
234331840ae1SZheng Yan 			if (path->slots[0] == i) {
234431840ae1SZheng Yan 				int space = btrfs_leaf_free_space(root, left);
234531840ae1SZheng Yan 				if (space + push_space * 2 > free_space)
234631840ae1SZheng Yan 					break;
234731840ae1SZheng Yan 			}
234831840ae1SZheng Yan 		}
234931840ae1SZheng Yan 
235000ec4c51SChris Mason 		if (path->slots[0] == i)
235187b29b20SYan Zheng 			push_space += data_size;
2352db94535dSChris Mason 
2353db94535dSChris Mason 		if (!left->map_token) {
2354db94535dSChris Mason 			map_extent_buffer(left, (unsigned long)item,
2355db94535dSChris Mason 					sizeof(struct btrfs_item),
2356db94535dSChris Mason 					&left->map_token, &left->kaddr,
2357db94535dSChris Mason 					&left->map_start, &left->map_len,
2358db94535dSChris Mason 					KM_USER1);
2359db94535dSChris Mason 		}
2360db94535dSChris Mason 
2361db94535dSChris Mason 		this_item_size = btrfs_item_size(left, item);
2362db94535dSChris Mason 		if (this_item_size + sizeof(*item) + push_space > free_space)
236300ec4c51SChris Mason 			break;
236431840ae1SZheng Yan 
236500ec4c51SChris Mason 		push_items++;
2366db94535dSChris Mason 		push_space += this_item_size + sizeof(*item);
236734a38218SChris Mason 		if (i == 0)
236834a38218SChris Mason 			break;
236934a38218SChris Mason 		i--;
2370db94535dSChris Mason 	}
2371db94535dSChris Mason 	if (left->map_token) {
2372db94535dSChris Mason 		unmap_extent_buffer(left, left->map_token, KM_USER1);
2373db94535dSChris Mason 		left->map_token = NULL;
237400ec4c51SChris Mason 	}
23755f39d397SChris Mason 
2376925baeddSChris Mason 	if (push_items == 0)
2377925baeddSChris Mason 		goto out_unlock;
23785f39d397SChris Mason 
237934a38218SChris Mason 	if (!empty && push_items == left_nritems)
2380a429e513SChris Mason 		WARN_ON(1);
23815f39d397SChris Mason 
238200ec4c51SChris Mason 	/* push left to right */
23835f39d397SChris Mason 	right_nritems = btrfs_header_nritems(right);
238434a38218SChris Mason 
23855f39d397SChris Mason 	push_space = btrfs_item_end_nr(left, left_nritems - push_items);
2386123abc88SChris Mason 	push_space -= leaf_data_end(root, left);
23875f39d397SChris Mason 
238800ec4c51SChris Mason 	/* make room in the right data area */
23895f39d397SChris Mason 	data_end = leaf_data_end(root, right);
23905f39d397SChris Mason 	memmove_extent_buffer(right,
23915f39d397SChris Mason 			      btrfs_leaf_data(right) + data_end - push_space,
23925f39d397SChris Mason 			      btrfs_leaf_data(right) + data_end,
23935f39d397SChris Mason 			      BTRFS_LEAF_DATA_SIZE(root) - data_end);
23945f39d397SChris Mason 
239500ec4c51SChris Mason 	/* copy from the left data area */
23965f39d397SChris Mason 	copy_extent_buffer(right, left, btrfs_leaf_data(right) +
2397d6025579SChris Mason 		     BTRFS_LEAF_DATA_SIZE(root) - push_space,
2398d6025579SChris Mason 		     btrfs_leaf_data(left) + leaf_data_end(root, left),
2399d6025579SChris Mason 		     push_space);
24005f39d397SChris Mason 
24015f39d397SChris Mason 	memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
24025f39d397SChris Mason 			      btrfs_item_nr_offset(0),
24030783fcfcSChris Mason 			      right_nritems * sizeof(struct btrfs_item));
24045f39d397SChris Mason 
240500ec4c51SChris Mason 	/* copy the items from left to right */
24065f39d397SChris Mason 	copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
24075f39d397SChris Mason 		   btrfs_item_nr_offset(left_nritems - push_items),
24080783fcfcSChris Mason 		   push_items * sizeof(struct btrfs_item));
240900ec4c51SChris Mason 
241000ec4c51SChris Mason 	/* update the item pointers */
24117518a238SChris Mason 	right_nritems += push_items;
24125f39d397SChris Mason 	btrfs_set_header_nritems(right, right_nritems);
2413123abc88SChris Mason 	push_space = BTRFS_LEAF_DATA_SIZE(root);
24147518a238SChris Mason 	for (i = 0; i < right_nritems; i++) {
24155f39d397SChris Mason 		item = btrfs_item_nr(right, i);
2416db94535dSChris Mason 		if (!right->map_token) {
2417db94535dSChris Mason 			map_extent_buffer(right, (unsigned long)item,
2418db94535dSChris Mason 					sizeof(struct btrfs_item),
2419db94535dSChris Mason 					&right->map_token, &right->kaddr,
2420db94535dSChris Mason 					&right->map_start, &right->map_len,
2421db94535dSChris Mason 					KM_USER1);
2422db94535dSChris Mason 		}
2423db94535dSChris Mason 		push_space -= btrfs_item_size(right, item);
2424db94535dSChris Mason 		btrfs_set_item_offset(right, item, push_space);
2425db94535dSChris Mason 	}
2426db94535dSChris Mason 
2427db94535dSChris Mason 	if (right->map_token) {
2428db94535dSChris Mason 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2429db94535dSChris Mason 		right->map_token = NULL;
243000ec4c51SChris Mason 	}
24317518a238SChris Mason 	left_nritems -= push_items;
24325f39d397SChris Mason 	btrfs_set_header_nritems(left, left_nritems);
243300ec4c51SChris Mason 
243434a38218SChris Mason 	if (left_nritems)
24355f39d397SChris Mason 		btrfs_mark_buffer_dirty(left);
2436f0486c68SYan, Zheng 	else
2437f0486c68SYan, Zheng 		clean_tree_block(trans, root, left);
2438f0486c68SYan, Zheng 
24395f39d397SChris Mason 	btrfs_mark_buffer_dirty(right);
2440a429e513SChris Mason 
24415f39d397SChris Mason 	btrfs_item_key(right, &disk_key, 0);
24425f39d397SChris Mason 	btrfs_set_node_key(upper, &disk_key, slot + 1);
2443d6025579SChris Mason 	btrfs_mark_buffer_dirty(upper);
244402217ed2SChris Mason 
244500ec4c51SChris Mason 	/* then fixup the leaf pointer in the path */
24467518a238SChris Mason 	if (path->slots[0] >= left_nritems) {
24477518a238SChris Mason 		path->slots[0] -= left_nritems;
2448925baeddSChris Mason 		if (btrfs_header_nritems(path->nodes[0]) == 0)
2449925baeddSChris Mason 			clean_tree_block(trans, root, path->nodes[0]);
2450925baeddSChris Mason 		btrfs_tree_unlock(path->nodes[0]);
24515f39d397SChris Mason 		free_extent_buffer(path->nodes[0]);
24525f39d397SChris Mason 		path->nodes[0] = right;
245300ec4c51SChris Mason 		path->slots[1] += 1;
245400ec4c51SChris Mason 	} else {
2455925baeddSChris Mason 		btrfs_tree_unlock(right);
24565f39d397SChris Mason 		free_extent_buffer(right);
245700ec4c51SChris Mason 	}
245800ec4c51SChris Mason 	return 0;
2459925baeddSChris Mason 
2460925baeddSChris Mason out_unlock:
2461925baeddSChris Mason 	btrfs_tree_unlock(right);
2462925baeddSChris Mason 	free_extent_buffer(right);
2463925baeddSChris Mason 	return 1;
246400ec4c51SChris Mason }
2465925baeddSChris Mason 
246600ec4c51SChris Mason /*
246744871b1bSChris Mason  * push some data in the path leaf to the right, trying to free up at
246874123bd7SChris Mason  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
246944871b1bSChris Mason  *
247044871b1bSChris Mason  * returns 1 if the push failed because the other node didn't have enough
247144871b1bSChris Mason  * room, 0 if everything worked out and < 0 if there were major errors.
247274123bd7SChris Mason  */
247344871b1bSChris Mason static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
247434a38218SChris Mason 			   *root, struct btrfs_path *path, int data_size,
247534a38218SChris Mason 			   int empty)
2476be0e5c09SChris Mason {
247744871b1bSChris Mason 	struct extent_buffer *left = path->nodes[0];
247844871b1bSChris Mason 	struct extent_buffer *right;
247944871b1bSChris Mason 	struct extent_buffer *upper;
248044871b1bSChris Mason 	int slot;
248144871b1bSChris Mason 	int free_space;
248244871b1bSChris Mason 	u32 left_nritems;
248344871b1bSChris Mason 	int ret;
248444871b1bSChris Mason 
248544871b1bSChris Mason 	if (!path->nodes[1])
248644871b1bSChris Mason 		return 1;
248744871b1bSChris Mason 
248844871b1bSChris Mason 	slot = path->slots[1];
248944871b1bSChris Mason 	upper = path->nodes[1];
249044871b1bSChris Mason 	if (slot >= btrfs_header_nritems(upper) - 1)
249144871b1bSChris Mason 		return 1;
249244871b1bSChris Mason 
249344871b1bSChris Mason 	btrfs_assert_tree_locked(path->nodes[1]);
249444871b1bSChris Mason 
249544871b1bSChris Mason 	right = read_node_slot(root, upper, slot + 1);
249644871b1bSChris Mason 	btrfs_tree_lock(right);
249744871b1bSChris Mason 	btrfs_set_lock_blocking(right);
249844871b1bSChris Mason 
249944871b1bSChris Mason 	free_space = btrfs_leaf_free_space(root, right);
250044871b1bSChris Mason 	if (free_space < data_size)
250144871b1bSChris Mason 		goto out_unlock;
250244871b1bSChris Mason 
250344871b1bSChris Mason 	/* cow and double check */
250444871b1bSChris Mason 	ret = btrfs_cow_block(trans, root, right, upper,
250544871b1bSChris Mason 			      slot + 1, &right);
250644871b1bSChris Mason 	if (ret)
250744871b1bSChris Mason 		goto out_unlock;
250844871b1bSChris Mason 
250944871b1bSChris Mason 	free_space = btrfs_leaf_free_space(root, right);
251044871b1bSChris Mason 	if (free_space < data_size)
251144871b1bSChris Mason 		goto out_unlock;
251244871b1bSChris Mason 
251344871b1bSChris Mason 	left_nritems = btrfs_header_nritems(left);
251444871b1bSChris Mason 	if (left_nritems == 0)
251544871b1bSChris Mason 		goto out_unlock;
251644871b1bSChris Mason 
251744871b1bSChris Mason 	return __push_leaf_right(trans, root, path, data_size, empty,
251844871b1bSChris Mason 				right, free_space, left_nritems);
251944871b1bSChris Mason out_unlock:
252044871b1bSChris Mason 	btrfs_tree_unlock(right);
252144871b1bSChris Mason 	free_extent_buffer(right);
252244871b1bSChris Mason 	return 1;
252344871b1bSChris Mason }
252444871b1bSChris Mason 
252544871b1bSChris Mason /*
252644871b1bSChris Mason  * push some data in the path leaf to the left, trying to free up at
252744871b1bSChris Mason  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
252844871b1bSChris Mason  */
252944871b1bSChris Mason static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
253044871b1bSChris Mason 				     struct btrfs_root *root,
253144871b1bSChris Mason 				     struct btrfs_path *path, int data_size,
253244871b1bSChris Mason 				     int empty, struct extent_buffer *left,
253344871b1bSChris Mason 				     int free_space, int right_nritems)
253444871b1bSChris Mason {
25355f39d397SChris Mason 	struct btrfs_disk_key disk_key;
25365f39d397SChris Mason 	struct extent_buffer *right = path->nodes[0];
2537be0e5c09SChris Mason 	int slot;
2538be0e5c09SChris Mason 	int i;
2539be0e5c09SChris Mason 	int push_space = 0;
2540be0e5c09SChris Mason 	int push_items = 0;
25410783fcfcSChris Mason 	struct btrfs_item *item;
25427518a238SChris Mason 	u32 old_left_nritems;
254334a38218SChris Mason 	u32 nr;
2544aa5d6bedSChris Mason 	int ret = 0;
2545aa5d6bedSChris Mason 	int wret;
2546db94535dSChris Mason 	u32 this_item_size;
2547db94535dSChris Mason 	u32 old_left_item_size;
2548be0e5c09SChris Mason 
2549be0e5c09SChris Mason 	slot = path->slots[1];
255002217ed2SChris Mason 
255134a38218SChris Mason 	if (empty)
255234a38218SChris Mason 		nr = right_nritems;
255334a38218SChris Mason 	else
255434a38218SChris Mason 		nr = right_nritems - 1;
255534a38218SChris Mason 
255634a38218SChris Mason 	for (i = 0; i < nr; i++) {
25575f39d397SChris Mason 		item = btrfs_item_nr(right, i);
2558db94535dSChris Mason 		if (!right->map_token) {
2559db94535dSChris Mason 			map_extent_buffer(right, (unsigned long)item,
2560db94535dSChris Mason 					sizeof(struct btrfs_item),
2561db94535dSChris Mason 					&right->map_token, &right->kaddr,
2562db94535dSChris Mason 					&right->map_start, &right->map_len,
2563db94535dSChris Mason 					KM_USER1);
2564db94535dSChris Mason 		}
2565db94535dSChris Mason 
256631840ae1SZheng Yan 		if (!empty && push_items > 0) {
256731840ae1SZheng Yan 			if (path->slots[0] < i)
256831840ae1SZheng Yan 				break;
256931840ae1SZheng Yan 			if (path->slots[0] == i) {
257031840ae1SZheng Yan 				int space = btrfs_leaf_free_space(root, right);
257131840ae1SZheng Yan 				if (space + push_space * 2 > free_space)
257231840ae1SZheng Yan 					break;
257331840ae1SZheng Yan 			}
257431840ae1SZheng Yan 		}
257531840ae1SZheng Yan 
2576be0e5c09SChris Mason 		if (path->slots[0] == i)
257787b29b20SYan Zheng 			push_space += data_size;
2578db94535dSChris Mason 
2579db94535dSChris Mason 		this_item_size = btrfs_item_size(right, item);
2580db94535dSChris Mason 		if (this_item_size + sizeof(*item) + push_space > free_space)
2581be0e5c09SChris Mason 			break;
2582db94535dSChris Mason 
2583be0e5c09SChris Mason 		push_items++;
2584db94535dSChris Mason 		push_space += this_item_size + sizeof(*item);
2585be0e5c09SChris Mason 	}
2586db94535dSChris Mason 
2587db94535dSChris Mason 	if (right->map_token) {
2588db94535dSChris Mason 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2589db94535dSChris Mason 		right->map_token = NULL;
2590db94535dSChris Mason 	}
2591db94535dSChris Mason 
2592be0e5c09SChris Mason 	if (push_items == 0) {
2593925baeddSChris Mason 		ret = 1;
2594925baeddSChris Mason 		goto out;
2595be0e5c09SChris Mason 	}
259634a38218SChris Mason 	if (!empty && push_items == btrfs_header_nritems(right))
2597a429e513SChris Mason 		WARN_ON(1);
25985f39d397SChris Mason 
2599be0e5c09SChris Mason 	/* push data from right to left */
26005f39d397SChris Mason 	copy_extent_buffer(left, right,
26015f39d397SChris Mason 			   btrfs_item_nr_offset(btrfs_header_nritems(left)),
26025f39d397SChris Mason 			   btrfs_item_nr_offset(0),
26035f39d397SChris Mason 			   push_items * sizeof(struct btrfs_item));
26045f39d397SChris Mason 
2605123abc88SChris Mason 	push_space = BTRFS_LEAF_DATA_SIZE(root) -
26065f39d397SChris Mason 		     btrfs_item_offset_nr(right, push_items - 1);
26075f39d397SChris Mason 
26085f39d397SChris Mason 	copy_extent_buffer(left, right, btrfs_leaf_data(left) +
2609d6025579SChris Mason 		     leaf_data_end(root, left) - push_space,
2610123abc88SChris Mason 		     btrfs_leaf_data(right) +
26115f39d397SChris Mason 		     btrfs_item_offset_nr(right, push_items - 1),
2612be0e5c09SChris Mason 		     push_space);
26135f39d397SChris Mason 	old_left_nritems = btrfs_header_nritems(left);
261487b29b20SYan Zheng 	BUG_ON(old_left_nritems <= 0);
2615eb60ceacSChris Mason 
2616db94535dSChris Mason 	old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
2617be0e5c09SChris Mason 	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
26185f39d397SChris Mason 		u32 ioff;
2619db94535dSChris Mason 
26205f39d397SChris Mason 		item = btrfs_item_nr(left, i);
2621db94535dSChris Mason 		if (!left->map_token) {
2622db94535dSChris Mason 			map_extent_buffer(left, (unsigned long)item,
2623db94535dSChris Mason 					sizeof(struct btrfs_item),
2624db94535dSChris Mason 					&left->map_token, &left->kaddr,
2625db94535dSChris Mason 					&left->map_start, &left->map_len,
2626db94535dSChris Mason 					KM_USER1);
2627db94535dSChris Mason 		}
2628db94535dSChris Mason 
26295f39d397SChris Mason 		ioff = btrfs_item_offset(left, item);
26305f39d397SChris Mason 		btrfs_set_item_offset(left, item,
2631db94535dSChris Mason 		      ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2632be0e5c09SChris Mason 	}
26335f39d397SChris Mason 	btrfs_set_header_nritems(left, old_left_nritems + push_items);
2634db94535dSChris Mason 	if (left->map_token) {
2635db94535dSChris Mason 		unmap_extent_buffer(left, left->map_token, KM_USER1);
2636db94535dSChris Mason 		left->map_token = NULL;
2637db94535dSChris Mason 	}
2638be0e5c09SChris Mason 
2639be0e5c09SChris Mason 	/* fixup right node */
264034a38218SChris Mason 	if (push_items > right_nritems) {
2641d397712bSChris Mason 		printk(KERN_CRIT "push items %d nr %u\n", push_items,
2642d397712bSChris Mason 		       right_nritems);
264334a38218SChris Mason 		WARN_ON(1);
264434a38218SChris Mason 	}
264534a38218SChris Mason 
264634a38218SChris Mason 	if (push_items < right_nritems) {
26475f39d397SChris Mason 		push_space = btrfs_item_offset_nr(right, push_items - 1) -
2648123abc88SChris Mason 						  leaf_data_end(root, right);
26495f39d397SChris Mason 		memmove_extent_buffer(right, btrfs_leaf_data(right) +
2650d6025579SChris Mason 				      BTRFS_LEAF_DATA_SIZE(root) - push_space,
2651d6025579SChris Mason 				      btrfs_leaf_data(right) +
2652123abc88SChris Mason 				      leaf_data_end(root, right), push_space);
26535f39d397SChris Mason 
26545f39d397SChris Mason 		memmove_extent_buffer(right, btrfs_item_nr_offset(0),
26555f39d397SChris Mason 			      btrfs_item_nr_offset(push_items),
26565f39d397SChris Mason 			     (btrfs_header_nritems(right) - push_items) *
26570783fcfcSChris Mason 			     sizeof(struct btrfs_item));
265834a38218SChris Mason 	}
2659eef1c494SYan 	right_nritems -= push_items;
2660eef1c494SYan 	btrfs_set_header_nritems(right, right_nritems);
2661123abc88SChris Mason 	push_space = BTRFS_LEAF_DATA_SIZE(root);
26625f39d397SChris Mason 	for (i = 0; i < right_nritems; i++) {
26635f39d397SChris Mason 		item = btrfs_item_nr(right, i);
2664db94535dSChris Mason 
2665db94535dSChris Mason 		if (!right->map_token) {
2666db94535dSChris Mason 			map_extent_buffer(right, (unsigned long)item,
2667db94535dSChris Mason 					sizeof(struct btrfs_item),
2668db94535dSChris Mason 					&right->map_token, &right->kaddr,
2669db94535dSChris Mason 					&right->map_start, &right->map_len,
2670db94535dSChris Mason 					KM_USER1);
2671db94535dSChris Mason 		}
2672db94535dSChris Mason 
2673db94535dSChris Mason 		push_space = push_space - btrfs_item_size(right, item);
2674db94535dSChris Mason 		btrfs_set_item_offset(right, item, push_space);
2675db94535dSChris Mason 	}
2676db94535dSChris Mason 	if (right->map_token) {
2677db94535dSChris Mason 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2678db94535dSChris Mason 		right->map_token = NULL;
2679be0e5c09SChris Mason 	}
2680eb60ceacSChris Mason 
26815f39d397SChris Mason 	btrfs_mark_buffer_dirty(left);
268234a38218SChris Mason 	if (right_nritems)
26835f39d397SChris Mason 		btrfs_mark_buffer_dirty(right);
2684f0486c68SYan, Zheng 	else
2685f0486c68SYan, Zheng 		clean_tree_block(trans, root, right);
2686098f59c2SChris Mason 
26875f39d397SChris Mason 	btrfs_item_key(right, &disk_key, 0);
26885f39d397SChris Mason 	wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2689aa5d6bedSChris Mason 	if (wret)
2690aa5d6bedSChris Mason 		ret = wret;
2691be0e5c09SChris Mason 
2692be0e5c09SChris Mason 	/* then fixup the leaf pointer in the path */
2693be0e5c09SChris Mason 	if (path->slots[0] < push_items) {
2694be0e5c09SChris Mason 		path->slots[0] += old_left_nritems;
2695925baeddSChris Mason 		btrfs_tree_unlock(path->nodes[0]);
26965f39d397SChris Mason 		free_extent_buffer(path->nodes[0]);
26975f39d397SChris Mason 		path->nodes[0] = left;
2698be0e5c09SChris Mason 		path->slots[1] -= 1;
2699be0e5c09SChris Mason 	} else {
2700925baeddSChris Mason 		btrfs_tree_unlock(left);
27015f39d397SChris Mason 		free_extent_buffer(left);
2702be0e5c09SChris Mason 		path->slots[0] -= push_items;
2703be0e5c09SChris Mason 	}
2704eb60ceacSChris Mason 	BUG_ON(path->slots[0] < 0);
2705aa5d6bedSChris Mason 	return ret;
2706925baeddSChris Mason out:
2707925baeddSChris Mason 	btrfs_tree_unlock(left);
2708925baeddSChris Mason 	free_extent_buffer(left);
2709925baeddSChris Mason 	return ret;
2710be0e5c09SChris Mason }
2711be0e5c09SChris Mason 
271274123bd7SChris Mason /*
271344871b1bSChris Mason  * push some data in the path leaf to the left, trying to free up at
271444871b1bSChris Mason  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
271544871b1bSChris Mason  */
271644871b1bSChris Mason static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
271744871b1bSChris Mason 			  *root, struct btrfs_path *path, int data_size,
271844871b1bSChris Mason 			  int empty)
271944871b1bSChris Mason {
272044871b1bSChris Mason 	struct extent_buffer *right = path->nodes[0];
272144871b1bSChris Mason 	struct extent_buffer *left;
272244871b1bSChris Mason 	int slot;
272344871b1bSChris Mason 	int free_space;
272444871b1bSChris Mason 	u32 right_nritems;
272544871b1bSChris Mason 	int ret = 0;
272644871b1bSChris Mason 
272744871b1bSChris Mason 	slot = path->slots[1];
272844871b1bSChris Mason 	if (slot == 0)
272944871b1bSChris Mason 		return 1;
273044871b1bSChris Mason 	if (!path->nodes[1])
273144871b1bSChris Mason 		return 1;
273244871b1bSChris Mason 
273344871b1bSChris Mason 	right_nritems = btrfs_header_nritems(right);
273444871b1bSChris Mason 	if (right_nritems == 0)
273544871b1bSChris Mason 		return 1;
273644871b1bSChris Mason 
273744871b1bSChris Mason 	btrfs_assert_tree_locked(path->nodes[1]);
273844871b1bSChris Mason 
273944871b1bSChris Mason 	left = read_node_slot(root, path->nodes[1], slot - 1);
274044871b1bSChris Mason 	btrfs_tree_lock(left);
274144871b1bSChris Mason 	btrfs_set_lock_blocking(left);
274244871b1bSChris Mason 
274344871b1bSChris Mason 	free_space = btrfs_leaf_free_space(root, left);
274444871b1bSChris Mason 	if (free_space < data_size) {
274544871b1bSChris Mason 		ret = 1;
274644871b1bSChris Mason 		goto out;
274744871b1bSChris Mason 	}
274844871b1bSChris Mason 
274944871b1bSChris Mason 	/* cow and double check */
275044871b1bSChris Mason 	ret = btrfs_cow_block(trans, root, left,
275144871b1bSChris Mason 			      path->nodes[1], slot - 1, &left);
275244871b1bSChris Mason 	if (ret) {
275344871b1bSChris Mason 		/* we hit -ENOSPC, but it isn't fatal here */
275444871b1bSChris Mason 		ret = 1;
275544871b1bSChris Mason 		goto out;
275644871b1bSChris Mason 	}
275744871b1bSChris Mason 
275844871b1bSChris Mason 	free_space = btrfs_leaf_free_space(root, left);
275944871b1bSChris Mason 	if (free_space < data_size) {
276044871b1bSChris Mason 		ret = 1;
276144871b1bSChris Mason 		goto out;
276244871b1bSChris Mason 	}
276344871b1bSChris Mason 
276444871b1bSChris Mason 	return __push_leaf_left(trans, root, path, data_size,
276544871b1bSChris Mason 			       empty, left, free_space, right_nritems);
276644871b1bSChris Mason out:
276744871b1bSChris Mason 	btrfs_tree_unlock(left);
276844871b1bSChris Mason 	free_extent_buffer(left);
276944871b1bSChris Mason 	return ret;
277044871b1bSChris Mason }
277144871b1bSChris Mason 
277244871b1bSChris Mason /*
277374123bd7SChris Mason  * split the path's leaf in two, making sure there is at least data_size
277474123bd7SChris Mason  * available for the resulting leaf level of the path.
2775aa5d6bedSChris Mason  *
2776aa5d6bedSChris Mason  * returns 0 if all went well and < 0 on failure.
277774123bd7SChris Mason  */
277844871b1bSChris Mason static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2779e02119d5SChris Mason 			       struct btrfs_root *root,
278044871b1bSChris Mason 			       struct btrfs_path *path,
278144871b1bSChris Mason 			       struct extent_buffer *l,
278244871b1bSChris Mason 			       struct extent_buffer *right,
278344871b1bSChris Mason 			       int slot, int mid, int nritems)
2784be0e5c09SChris Mason {
2785be0e5c09SChris Mason 	int data_copy_size;
2786be0e5c09SChris Mason 	int rt_data_off;
2787be0e5c09SChris Mason 	int i;
2788d4dbff95SChris Mason 	int ret = 0;
2789aa5d6bedSChris Mason 	int wret;
2790d4dbff95SChris Mason 	struct btrfs_disk_key disk_key;
2791be0e5c09SChris Mason 
27925f39d397SChris Mason 	nritems = nritems - mid;
27935f39d397SChris Mason 	btrfs_set_header_nritems(right, nritems);
27945f39d397SChris Mason 	data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
27955f39d397SChris Mason 
27965f39d397SChris Mason 	copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
27975f39d397SChris Mason 			   btrfs_item_nr_offset(mid),
27985f39d397SChris Mason 			   nritems * sizeof(struct btrfs_item));
27995f39d397SChris Mason 
28005f39d397SChris Mason 	copy_extent_buffer(right, l,
2801d6025579SChris Mason 		     btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2802123abc88SChris Mason 		     data_copy_size, btrfs_leaf_data(l) +
2803123abc88SChris Mason 		     leaf_data_end(root, l), data_copy_size);
280474123bd7SChris Mason 
28055f39d397SChris Mason 	rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
28065f39d397SChris Mason 		      btrfs_item_end_nr(l, mid);
28075f39d397SChris Mason 
28085f39d397SChris Mason 	for (i = 0; i < nritems; i++) {
28095f39d397SChris Mason 		struct btrfs_item *item = btrfs_item_nr(right, i);
2810db94535dSChris Mason 		u32 ioff;
2811db94535dSChris Mason 
2812db94535dSChris Mason 		if (!right->map_token) {
2813db94535dSChris Mason 			map_extent_buffer(right, (unsigned long)item,
2814db94535dSChris Mason 					sizeof(struct btrfs_item),
2815db94535dSChris Mason 					&right->map_token, &right->kaddr,
2816db94535dSChris Mason 					&right->map_start, &right->map_len,
2817db94535dSChris Mason 					KM_USER1);
2818db94535dSChris Mason 		}
2819db94535dSChris Mason 
2820db94535dSChris Mason 		ioff = btrfs_item_offset(right, item);
28215f39d397SChris Mason 		btrfs_set_item_offset(right, item, ioff + rt_data_off);
28220783fcfcSChris Mason 	}
282374123bd7SChris Mason 
2824db94535dSChris Mason 	if (right->map_token) {
2825db94535dSChris Mason 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2826db94535dSChris Mason 		right->map_token = NULL;
2827db94535dSChris Mason 	}
2828db94535dSChris Mason 
28295f39d397SChris Mason 	btrfs_set_header_nritems(l, mid);
2830aa5d6bedSChris Mason 	ret = 0;
28315f39d397SChris Mason 	btrfs_item_key(right, &disk_key, 0);
2832db94535dSChris Mason 	wret = insert_ptr(trans, root, path, &disk_key, right->start,
2833db94535dSChris Mason 			  path->slots[1] + 1, 1);
2834aa5d6bedSChris Mason 	if (wret)
2835aa5d6bedSChris Mason 		ret = wret;
28365f39d397SChris Mason 
28375f39d397SChris Mason 	btrfs_mark_buffer_dirty(right);
28385f39d397SChris Mason 	btrfs_mark_buffer_dirty(l);
2839eb60ceacSChris Mason 	BUG_ON(path->slots[0] != slot);
28405f39d397SChris Mason 
2841be0e5c09SChris Mason 	if (mid <= slot) {
2842925baeddSChris Mason 		btrfs_tree_unlock(path->nodes[0]);
28435f39d397SChris Mason 		free_extent_buffer(path->nodes[0]);
28445f39d397SChris Mason 		path->nodes[0] = right;
2845be0e5c09SChris Mason 		path->slots[0] -= mid;
2846be0e5c09SChris Mason 		path->slots[1] += 1;
2847925baeddSChris Mason 	} else {
2848925baeddSChris Mason 		btrfs_tree_unlock(right);
28495f39d397SChris Mason 		free_extent_buffer(right);
2850925baeddSChris Mason 	}
28515f39d397SChris Mason 
2852eb60ceacSChris Mason 	BUG_ON(path->slots[0] < 0);
2853d4dbff95SChris Mason 
285444871b1bSChris Mason 	return ret;
285544871b1bSChris Mason }
285644871b1bSChris Mason 
285744871b1bSChris Mason /*
285844871b1bSChris Mason  * split the path's leaf in two, making sure there is at least data_size
285944871b1bSChris Mason  * available for the resulting leaf level of the path.
286044871b1bSChris Mason  *
286144871b1bSChris Mason  * returns 0 if all went well and < 0 on failure.
286244871b1bSChris Mason  */
286344871b1bSChris Mason static noinline int split_leaf(struct btrfs_trans_handle *trans,
286444871b1bSChris Mason 			       struct btrfs_root *root,
286544871b1bSChris Mason 			       struct btrfs_key *ins_key,
286644871b1bSChris Mason 			       struct btrfs_path *path, int data_size,
286744871b1bSChris Mason 			       int extend)
286844871b1bSChris Mason {
28695d4f98a2SYan Zheng 	struct btrfs_disk_key disk_key;
287044871b1bSChris Mason 	struct extent_buffer *l;
287144871b1bSChris Mason 	u32 nritems;
287244871b1bSChris Mason 	int mid;
287344871b1bSChris Mason 	int slot;
287444871b1bSChris Mason 	struct extent_buffer *right;
287544871b1bSChris Mason 	int ret = 0;
287644871b1bSChris Mason 	int wret;
28775d4f98a2SYan Zheng 	int split;
287844871b1bSChris Mason 	int num_doubles = 0;
287944871b1bSChris Mason 
2880a5719521SYan, Zheng 	l = path->nodes[0];
2881a5719521SYan, Zheng 	slot = path->slots[0];
2882a5719521SYan, Zheng 	if (extend && data_size + btrfs_item_size_nr(l, slot) +
2883a5719521SYan, Zheng 	    sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
2884a5719521SYan, Zheng 		return -EOVERFLOW;
2885a5719521SYan, Zheng 
288644871b1bSChris Mason 	/* first try to make some room by pushing left and right */
2887b3612421SChris Mason 	if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
288844871b1bSChris Mason 		wret = push_leaf_right(trans, root, path, data_size, 0);
288944871b1bSChris Mason 		if (wret < 0)
289044871b1bSChris Mason 			return wret;
289144871b1bSChris Mason 		if (wret) {
289244871b1bSChris Mason 			wret = push_leaf_left(trans, root, path, data_size, 0);
289344871b1bSChris Mason 			if (wret < 0)
289444871b1bSChris Mason 				return wret;
289544871b1bSChris Mason 		}
289644871b1bSChris Mason 		l = path->nodes[0];
289744871b1bSChris Mason 
289844871b1bSChris Mason 		/* did the pushes work? */
289944871b1bSChris Mason 		if (btrfs_leaf_free_space(root, l) >= data_size)
290044871b1bSChris Mason 			return 0;
290144871b1bSChris Mason 	}
290244871b1bSChris Mason 
290344871b1bSChris Mason 	if (!path->nodes[1]) {
290444871b1bSChris Mason 		ret = insert_new_root(trans, root, path, 1);
290544871b1bSChris Mason 		if (ret)
290644871b1bSChris Mason 			return ret;
290744871b1bSChris Mason 	}
290844871b1bSChris Mason again:
29095d4f98a2SYan Zheng 	split = 1;
291044871b1bSChris Mason 	l = path->nodes[0];
291144871b1bSChris Mason 	slot = path->slots[0];
291244871b1bSChris Mason 	nritems = btrfs_header_nritems(l);
291344871b1bSChris Mason 	mid = (nritems + 1) / 2;
291444871b1bSChris Mason 
29155d4f98a2SYan Zheng 	if (mid <= slot) {
29165d4f98a2SYan Zheng 		if (nritems == 1 ||
29175d4f98a2SYan Zheng 		    leaf_space_used(l, mid, nritems - mid) + data_size >
29185d4f98a2SYan Zheng 			BTRFS_LEAF_DATA_SIZE(root)) {
29195d4f98a2SYan Zheng 			if (slot >= nritems) {
29205d4f98a2SYan Zheng 				split = 0;
29215d4f98a2SYan Zheng 			} else {
29225d4f98a2SYan Zheng 				mid = slot;
29235d4f98a2SYan Zheng 				if (mid != nritems &&
29245d4f98a2SYan Zheng 				    leaf_space_used(l, mid, nritems - mid) +
29255d4f98a2SYan Zheng 				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
29265d4f98a2SYan Zheng 					split = 2;
29275d4f98a2SYan Zheng 				}
29285d4f98a2SYan Zheng 			}
29295d4f98a2SYan Zheng 		}
29305d4f98a2SYan Zheng 	} else {
29315d4f98a2SYan Zheng 		if (leaf_space_used(l, 0, mid) + data_size >
29325d4f98a2SYan Zheng 			BTRFS_LEAF_DATA_SIZE(root)) {
29335d4f98a2SYan Zheng 			if (!extend && data_size && slot == 0) {
29345d4f98a2SYan Zheng 				split = 0;
29355d4f98a2SYan Zheng 			} else if ((extend || !data_size) && slot == 0) {
29365d4f98a2SYan Zheng 				mid = 1;
29375d4f98a2SYan Zheng 			} else {
29385d4f98a2SYan Zheng 				mid = slot;
29395d4f98a2SYan Zheng 				if (mid != nritems &&
29405d4f98a2SYan Zheng 				    leaf_space_used(l, mid, nritems - mid) +
29415d4f98a2SYan Zheng 				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
29425d4f98a2SYan Zheng 					split = 2 ;
29435d4f98a2SYan Zheng 				}
29445d4f98a2SYan Zheng 			}
29455d4f98a2SYan Zheng 		}
29465d4f98a2SYan Zheng 	}
29475d4f98a2SYan Zheng 
29485d4f98a2SYan Zheng 	if (split == 0)
29495d4f98a2SYan Zheng 		btrfs_cpu_key_to_disk(&disk_key, ins_key);
29505d4f98a2SYan Zheng 	else
29515d4f98a2SYan Zheng 		btrfs_item_key(l, &disk_key, mid);
29525d4f98a2SYan Zheng 
29535d4f98a2SYan Zheng 	right = btrfs_alloc_free_block(trans, root, root->leafsize, 0,
295444871b1bSChris Mason 					root->root_key.objectid,
29555d4f98a2SYan Zheng 					&disk_key, 0, l->start, 0);
2956f0486c68SYan, Zheng 	if (IS_ERR(right))
295744871b1bSChris Mason 		return PTR_ERR(right);
2958f0486c68SYan, Zheng 
2959f0486c68SYan, Zheng 	root_add_used(root, root->leafsize);
296044871b1bSChris Mason 
296144871b1bSChris Mason 	memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
296244871b1bSChris Mason 	btrfs_set_header_bytenr(right, right->start);
296344871b1bSChris Mason 	btrfs_set_header_generation(right, trans->transid);
29645d4f98a2SYan Zheng 	btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
296544871b1bSChris Mason 	btrfs_set_header_owner(right, root->root_key.objectid);
296644871b1bSChris Mason 	btrfs_set_header_level(right, 0);
296744871b1bSChris Mason 	write_extent_buffer(right, root->fs_info->fsid,
296844871b1bSChris Mason 			    (unsigned long)btrfs_header_fsid(right),
296944871b1bSChris Mason 			    BTRFS_FSID_SIZE);
297044871b1bSChris Mason 
297144871b1bSChris Mason 	write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
297244871b1bSChris Mason 			    (unsigned long)btrfs_header_chunk_tree_uuid(right),
297344871b1bSChris Mason 			    BTRFS_UUID_SIZE);
297444871b1bSChris Mason 
29755d4f98a2SYan Zheng 	if (split == 0) {
297644871b1bSChris Mason 		if (mid <= slot) {
297744871b1bSChris Mason 			btrfs_set_header_nritems(right, 0);
297844871b1bSChris Mason 			wret = insert_ptr(trans, root, path,
297944871b1bSChris Mason 					  &disk_key, right->start,
298044871b1bSChris Mason 					  path->slots[1] + 1, 1);
298144871b1bSChris Mason 			if (wret)
298244871b1bSChris Mason 				ret = wret;
298344871b1bSChris Mason 
298444871b1bSChris Mason 			btrfs_tree_unlock(path->nodes[0]);
298544871b1bSChris Mason 			free_extent_buffer(path->nodes[0]);
298644871b1bSChris Mason 			path->nodes[0] = right;
298744871b1bSChris Mason 			path->slots[0] = 0;
298844871b1bSChris Mason 			path->slots[1] += 1;
298944871b1bSChris Mason 		} else {
299044871b1bSChris Mason 			btrfs_set_header_nritems(right, 0);
299144871b1bSChris Mason 			wret = insert_ptr(trans, root, path,
299244871b1bSChris Mason 					  &disk_key,
299344871b1bSChris Mason 					  right->start,
299444871b1bSChris Mason 					  path->slots[1], 1);
299544871b1bSChris Mason 			if (wret)
299644871b1bSChris Mason 				ret = wret;
299744871b1bSChris Mason 			btrfs_tree_unlock(path->nodes[0]);
299844871b1bSChris Mason 			free_extent_buffer(path->nodes[0]);
299944871b1bSChris Mason 			path->nodes[0] = right;
300044871b1bSChris Mason 			path->slots[0] = 0;
300144871b1bSChris Mason 			if (path->slots[1] == 0) {
300244871b1bSChris Mason 				wret = fixup_low_keys(trans, root,
300344871b1bSChris Mason 						path, &disk_key, 1);
300444871b1bSChris Mason 				if (wret)
300544871b1bSChris Mason 					ret = wret;
300644871b1bSChris Mason 			}
30075d4f98a2SYan Zheng 		}
300844871b1bSChris Mason 		btrfs_mark_buffer_dirty(right);
300944871b1bSChris Mason 		return ret;
301044871b1bSChris Mason 	}
301144871b1bSChris Mason 
301244871b1bSChris Mason 	ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
301344871b1bSChris Mason 	BUG_ON(ret);
301444871b1bSChris Mason 
30155d4f98a2SYan Zheng 	if (split == 2) {
3016cc0c5538SChris Mason 		BUG_ON(num_doubles != 0);
3017cc0c5538SChris Mason 		num_doubles++;
3018cc0c5538SChris Mason 		goto again;
30193326d1b0SChris Mason 	}
302044871b1bSChris Mason 
3021be0e5c09SChris Mason 	return ret;
3022be0e5c09SChris Mason }
3023be0e5c09SChris Mason 
3024ad48fd75SYan, Zheng static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3025ad48fd75SYan, Zheng 					 struct btrfs_root *root,
3026ad48fd75SYan, Zheng 					 struct btrfs_path *path, int ins_len)
3027ad48fd75SYan, Zheng {
3028ad48fd75SYan, Zheng 	struct btrfs_key key;
3029ad48fd75SYan, Zheng 	struct extent_buffer *leaf;
3030ad48fd75SYan, Zheng 	struct btrfs_file_extent_item *fi;
3031ad48fd75SYan, Zheng 	u64 extent_len = 0;
3032ad48fd75SYan, Zheng 	u32 item_size;
3033ad48fd75SYan, Zheng 	int ret;
3034ad48fd75SYan, Zheng 
3035ad48fd75SYan, Zheng 	leaf = path->nodes[0];
3036ad48fd75SYan, Zheng 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3037ad48fd75SYan, Zheng 
3038ad48fd75SYan, Zheng 	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3039ad48fd75SYan, Zheng 	       key.type != BTRFS_EXTENT_CSUM_KEY);
3040ad48fd75SYan, Zheng 
3041ad48fd75SYan, Zheng 	if (btrfs_leaf_free_space(root, leaf) >= ins_len)
3042ad48fd75SYan, Zheng 		return 0;
3043ad48fd75SYan, Zheng 
3044ad48fd75SYan, Zheng 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3045ad48fd75SYan, Zheng 	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3046ad48fd75SYan, Zheng 		fi = btrfs_item_ptr(leaf, path->slots[0],
3047ad48fd75SYan, Zheng 				    struct btrfs_file_extent_item);
3048ad48fd75SYan, Zheng 		extent_len = btrfs_file_extent_num_bytes(leaf, fi);
3049ad48fd75SYan, Zheng 	}
3050ad48fd75SYan, Zheng 	btrfs_release_path(root, path);
3051ad48fd75SYan, Zheng 
3052ad48fd75SYan, Zheng 	path->keep_locks = 1;
3053ad48fd75SYan, Zheng 	path->search_for_split = 1;
3054ad48fd75SYan, Zheng 	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3055ad48fd75SYan, Zheng 	path->search_for_split = 0;
3056ad48fd75SYan, Zheng 	if (ret < 0)
3057ad48fd75SYan, Zheng 		goto err;
3058ad48fd75SYan, Zheng 
3059ad48fd75SYan, Zheng 	ret = -EAGAIN;
3060ad48fd75SYan, Zheng 	leaf = path->nodes[0];
3061ad48fd75SYan, Zheng 	/* if our item isn't there or got smaller, return now */
3062ad48fd75SYan, Zheng 	if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0]))
3063ad48fd75SYan, Zheng 		goto err;
3064ad48fd75SYan, Zheng 
3065109f6aefSChris Mason 	/* the leaf has  changed, it now has room.  return now */
3066109f6aefSChris Mason 	if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len)
3067109f6aefSChris Mason 		goto err;
3068109f6aefSChris Mason 
3069ad48fd75SYan, Zheng 	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3070ad48fd75SYan, Zheng 		fi = btrfs_item_ptr(leaf, path->slots[0],
3071ad48fd75SYan, Zheng 				    struct btrfs_file_extent_item);
3072ad48fd75SYan, Zheng 		if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
3073ad48fd75SYan, Zheng 			goto err;
3074ad48fd75SYan, Zheng 	}
3075ad48fd75SYan, Zheng 
3076ad48fd75SYan, Zheng 	btrfs_set_path_blocking(path);
3077ad48fd75SYan, Zheng 	ret = split_leaf(trans, root, &key, path, ins_len, 1);
3078f0486c68SYan, Zheng 	if (ret)
3079f0486c68SYan, Zheng 		goto err;
3080ad48fd75SYan, Zheng 
3081ad48fd75SYan, Zheng 	path->keep_locks = 0;
3082ad48fd75SYan, Zheng 	btrfs_unlock_up_safe(path, 1);
3083ad48fd75SYan, Zheng 	return 0;
3084ad48fd75SYan, Zheng err:
3085ad48fd75SYan, Zheng 	path->keep_locks = 0;
3086ad48fd75SYan, Zheng 	return ret;
3087ad48fd75SYan, Zheng }
3088ad48fd75SYan, Zheng 
3089ad48fd75SYan, Zheng static noinline int split_item(struct btrfs_trans_handle *trans,
3090459931ecSChris Mason 			       struct btrfs_root *root,
3091459931ecSChris Mason 			       struct btrfs_path *path,
3092459931ecSChris Mason 			       struct btrfs_key *new_key,
3093459931ecSChris Mason 			       unsigned long split_offset)
3094459931ecSChris Mason {
3095459931ecSChris Mason 	struct extent_buffer *leaf;
3096459931ecSChris Mason 	struct btrfs_item *item;
3097459931ecSChris Mason 	struct btrfs_item *new_item;
3098459931ecSChris Mason 	int slot;
3099ad48fd75SYan, Zheng 	char *buf;
3100459931ecSChris Mason 	u32 nritems;
3101ad48fd75SYan, Zheng 	u32 item_size;
3102459931ecSChris Mason 	u32 orig_offset;
3103459931ecSChris Mason 	struct btrfs_disk_key disk_key;
3104459931ecSChris Mason 
3105459931ecSChris Mason 	leaf = path->nodes[0];
3106b9473439SChris Mason 	BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3107b9473439SChris Mason 
3108b4ce94deSChris Mason 	btrfs_set_path_blocking(path);
3109b4ce94deSChris Mason 
3110459931ecSChris Mason 	item = btrfs_item_nr(leaf, path->slots[0]);
3111459931ecSChris Mason 	orig_offset = btrfs_item_offset(leaf, item);
3112459931ecSChris Mason 	item_size = btrfs_item_size(leaf, item);
3113459931ecSChris Mason 
3114459931ecSChris Mason 	buf = kmalloc(item_size, GFP_NOFS);
3115ad48fd75SYan, Zheng 	if (!buf)
3116ad48fd75SYan, Zheng 		return -ENOMEM;
3117ad48fd75SYan, Zheng 
3118459931ecSChris Mason 	read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3119459931ecSChris Mason 			    path->slots[0]), item_size);
3120ad48fd75SYan, Zheng 
3121459931ecSChris Mason 	slot = path->slots[0] + 1;
3122459931ecSChris Mason 	nritems = btrfs_header_nritems(leaf);
3123459931ecSChris Mason 	if (slot != nritems) {
3124459931ecSChris Mason 		/* shift the items */
3125459931ecSChris Mason 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3126459931ecSChris Mason 				btrfs_item_nr_offset(slot),
3127459931ecSChris Mason 				(nritems - slot) * sizeof(struct btrfs_item));
3128459931ecSChris Mason 	}
3129459931ecSChris Mason 
3130459931ecSChris Mason 	btrfs_cpu_key_to_disk(&disk_key, new_key);
3131459931ecSChris Mason 	btrfs_set_item_key(leaf, &disk_key, slot);
3132459931ecSChris Mason 
3133459931ecSChris Mason 	new_item = btrfs_item_nr(leaf, slot);
3134459931ecSChris Mason 
3135459931ecSChris Mason 	btrfs_set_item_offset(leaf, new_item, orig_offset);
3136459931ecSChris Mason 	btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3137459931ecSChris Mason 
3138459931ecSChris Mason 	btrfs_set_item_offset(leaf, item,
3139459931ecSChris Mason 			      orig_offset + item_size - split_offset);
3140459931ecSChris Mason 	btrfs_set_item_size(leaf, item, split_offset);
3141459931ecSChris Mason 
3142459931ecSChris Mason 	btrfs_set_header_nritems(leaf, nritems + 1);
3143459931ecSChris Mason 
3144459931ecSChris Mason 	/* write the data for the start of the original item */
3145459931ecSChris Mason 	write_extent_buffer(leaf, buf,
3146459931ecSChris Mason 			    btrfs_item_ptr_offset(leaf, path->slots[0]),
3147459931ecSChris Mason 			    split_offset);
3148459931ecSChris Mason 
3149459931ecSChris Mason 	/* write the data for the new item */
3150459931ecSChris Mason 	write_extent_buffer(leaf, buf + split_offset,
3151459931ecSChris Mason 			    btrfs_item_ptr_offset(leaf, slot),
3152459931ecSChris Mason 			    item_size - split_offset);
3153459931ecSChris Mason 	btrfs_mark_buffer_dirty(leaf);
3154459931ecSChris Mason 
3155ad48fd75SYan, Zheng 	BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
3156459931ecSChris Mason 	kfree(buf);
3157ad48fd75SYan, Zheng 	return 0;
3158ad48fd75SYan, Zheng }
3159ad48fd75SYan, Zheng 
3160ad48fd75SYan, Zheng /*
3161ad48fd75SYan, Zheng  * This function splits a single item into two items,
3162ad48fd75SYan, Zheng  * giving 'new_key' to the new item and splitting the
3163ad48fd75SYan, Zheng  * old one at split_offset (from the start of the item).
3164ad48fd75SYan, Zheng  *
3165ad48fd75SYan, Zheng  * The path may be released by this operation.  After
3166ad48fd75SYan, Zheng  * the split, the path is pointing to the old item.  The
3167ad48fd75SYan, Zheng  * new item is going to be in the same node as the old one.
3168ad48fd75SYan, Zheng  *
3169ad48fd75SYan, Zheng  * Note, the item being split must be smaller enough to live alone on
3170ad48fd75SYan, Zheng  * a tree block with room for one extra struct btrfs_item
3171ad48fd75SYan, Zheng  *
3172ad48fd75SYan, Zheng  * This allows us to split the item in place, keeping a lock on the
3173ad48fd75SYan, Zheng  * leaf the entire time.
3174ad48fd75SYan, Zheng  */
3175ad48fd75SYan, Zheng int btrfs_split_item(struct btrfs_trans_handle *trans,
3176ad48fd75SYan, Zheng 		     struct btrfs_root *root,
3177ad48fd75SYan, Zheng 		     struct btrfs_path *path,
3178ad48fd75SYan, Zheng 		     struct btrfs_key *new_key,
3179ad48fd75SYan, Zheng 		     unsigned long split_offset)
3180ad48fd75SYan, Zheng {
3181ad48fd75SYan, Zheng 	int ret;
3182ad48fd75SYan, Zheng 	ret = setup_leaf_for_split(trans, root, path,
3183ad48fd75SYan, Zheng 				   sizeof(struct btrfs_item));
3184ad48fd75SYan, Zheng 	if (ret)
3185459931ecSChris Mason 		return ret;
3186ad48fd75SYan, Zheng 
3187ad48fd75SYan, Zheng 	ret = split_item(trans, root, path, new_key, split_offset);
3188ad48fd75SYan, Zheng 	return ret;
3189ad48fd75SYan, Zheng }
3190ad48fd75SYan, Zheng 
3191ad48fd75SYan, Zheng /*
3192ad48fd75SYan, Zheng  * This function duplicate a item, giving 'new_key' to the new item.
3193ad48fd75SYan, Zheng  * It guarantees both items live in the same tree leaf and the new item
3194ad48fd75SYan, Zheng  * is contiguous with the original item.
3195ad48fd75SYan, Zheng  *
3196ad48fd75SYan, Zheng  * This allows us to split file extent in place, keeping a lock on the
3197ad48fd75SYan, Zheng  * leaf the entire time.
3198ad48fd75SYan, Zheng  */
3199ad48fd75SYan, Zheng int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
3200ad48fd75SYan, Zheng 			 struct btrfs_root *root,
3201ad48fd75SYan, Zheng 			 struct btrfs_path *path,
3202ad48fd75SYan, Zheng 			 struct btrfs_key *new_key)
3203ad48fd75SYan, Zheng {
3204ad48fd75SYan, Zheng 	struct extent_buffer *leaf;
3205ad48fd75SYan, Zheng 	int ret;
3206ad48fd75SYan, Zheng 	u32 item_size;
3207ad48fd75SYan, Zheng 
3208ad48fd75SYan, Zheng 	leaf = path->nodes[0];
3209ad48fd75SYan, Zheng 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3210ad48fd75SYan, Zheng 	ret = setup_leaf_for_split(trans, root, path,
3211ad48fd75SYan, Zheng 				   item_size + sizeof(struct btrfs_item));
3212ad48fd75SYan, Zheng 	if (ret)
3213ad48fd75SYan, Zheng 		return ret;
3214ad48fd75SYan, Zheng 
3215ad48fd75SYan, Zheng 	path->slots[0]++;
3216ad48fd75SYan, Zheng 	ret = setup_items_for_insert(trans, root, path, new_key, &item_size,
3217ad48fd75SYan, Zheng 				     item_size, item_size +
3218ad48fd75SYan, Zheng 				     sizeof(struct btrfs_item), 1);
3219ad48fd75SYan, Zheng 	BUG_ON(ret);
3220ad48fd75SYan, Zheng 
3221ad48fd75SYan, Zheng 	leaf = path->nodes[0];
3222ad48fd75SYan, Zheng 	memcpy_extent_buffer(leaf,
3223ad48fd75SYan, Zheng 			     btrfs_item_ptr_offset(leaf, path->slots[0]),
3224ad48fd75SYan, Zheng 			     btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
3225ad48fd75SYan, Zheng 			     item_size);
3226ad48fd75SYan, Zheng 	return 0;
3227459931ecSChris Mason }
3228459931ecSChris Mason 
3229459931ecSChris Mason /*
3230d352ac68SChris Mason  * make the item pointed to by the path smaller.  new_size indicates
3231d352ac68SChris Mason  * how small to make it, and from_end tells us if we just chop bytes
3232d352ac68SChris Mason  * off the end of the item or if we shift the item to chop bytes off
3233d352ac68SChris Mason  * the front.
3234d352ac68SChris Mason  */
3235b18c6685SChris Mason int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3236b18c6685SChris Mason 			struct btrfs_root *root,
3237b18c6685SChris Mason 			struct btrfs_path *path,
3238179e29e4SChris Mason 			u32 new_size, int from_end)
3239b18c6685SChris Mason {
3240b18c6685SChris Mason 	int ret = 0;
3241b18c6685SChris Mason 	int slot;
3242b18c6685SChris Mason 	int slot_orig;
32435f39d397SChris Mason 	struct extent_buffer *leaf;
32445f39d397SChris Mason 	struct btrfs_item *item;
3245b18c6685SChris Mason 	u32 nritems;
3246b18c6685SChris Mason 	unsigned int data_end;
3247b18c6685SChris Mason 	unsigned int old_data_start;
3248b18c6685SChris Mason 	unsigned int old_size;
3249b18c6685SChris Mason 	unsigned int size_diff;
3250b18c6685SChris Mason 	int i;
3251b18c6685SChris Mason 
3252b18c6685SChris Mason 	slot_orig = path->slots[0];
32535f39d397SChris Mason 	leaf = path->nodes[0];
3254179e29e4SChris Mason 	slot = path->slots[0];
3255179e29e4SChris Mason 
3256179e29e4SChris Mason 	old_size = btrfs_item_size_nr(leaf, slot);
3257179e29e4SChris Mason 	if (old_size == new_size)
3258179e29e4SChris Mason 		return 0;
3259b18c6685SChris Mason 
32605f39d397SChris Mason 	nritems = btrfs_header_nritems(leaf);
3261b18c6685SChris Mason 	data_end = leaf_data_end(root, leaf);
3262b18c6685SChris Mason 
32635f39d397SChris Mason 	old_data_start = btrfs_item_offset_nr(leaf, slot);
3264179e29e4SChris Mason 
3265b18c6685SChris Mason 	size_diff = old_size - new_size;
3266b18c6685SChris Mason 
3267b18c6685SChris Mason 	BUG_ON(slot < 0);
3268b18c6685SChris Mason 	BUG_ON(slot >= nritems);
3269b18c6685SChris Mason 
3270b18c6685SChris Mason 	/*
3271b18c6685SChris Mason 	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3272b18c6685SChris Mason 	 */
3273b18c6685SChris Mason 	/* first correct the data pointers */
3274b18c6685SChris Mason 	for (i = slot; i < nritems; i++) {
32755f39d397SChris Mason 		u32 ioff;
32765f39d397SChris Mason 		item = btrfs_item_nr(leaf, i);
3277db94535dSChris Mason 
3278db94535dSChris Mason 		if (!leaf->map_token) {
3279db94535dSChris Mason 			map_extent_buffer(leaf, (unsigned long)item,
3280db94535dSChris Mason 					sizeof(struct btrfs_item),
3281db94535dSChris Mason 					&leaf->map_token, &leaf->kaddr,
3282db94535dSChris Mason 					&leaf->map_start, &leaf->map_len,
3283db94535dSChris Mason 					KM_USER1);
3284db94535dSChris Mason 		}
3285db94535dSChris Mason 
32865f39d397SChris Mason 		ioff = btrfs_item_offset(leaf, item);
32875f39d397SChris Mason 		btrfs_set_item_offset(leaf, item, ioff + size_diff);
3288b18c6685SChris Mason 	}
3289db94535dSChris Mason 
3290db94535dSChris Mason 	if (leaf->map_token) {
3291db94535dSChris Mason 		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3292db94535dSChris Mason 		leaf->map_token = NULL;
3293db94535dSChris Mason 	}
3294db94535dSChris Mason 
3295b18c6685SChris Mason 	/* shift the data */
3296179e29e4SChris Mason 	if (from_end) {
32975f39d397SChris Mason 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3298b18c6685SChris Mason 			      data_end + size_diff, btrfs_leaf_data(leaf) +
3299b18c6685SChris Mason 			      data_end, old_data_start + new_size - data_end);
3300179e29e4SChris Mason 	} else {
3301179e29e4SChris Mason 		struct btrfs_disk_key disk_key;
3302179e29e4SChris Mason 		u64 offset;
3303179e29e4SChris Mason 
3304179e29e4SChris Mason 		btrfs_item_key(leaf, &disk_key, slot);
3305179e29e4SChris Mason 
3306179e29e4SChris Mason 		if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3307179e29e4SChris Mason 			unsigned long ptr;
3308179e29e4SChris Mason 			struct btrfs_file_extent_item *fi;
3309179e29e4SChris Mason 
3310179e29e4SChris Mason 			fi = btrfs_item_ptr(leaf, slot,
3311179e29e4SChris Mason 					    struct btrfs_file_extent_item);
3312179e29e4SChris Mason 			fi = (struct btrfs_file_extent_item *)(
3313179e29e4SChris Mason 			     (unsigned long)fi - size_diff);
3314179e29e4SChris Mason 
3315179e29e4SChris Mason 			if (btrfs_file_extent_type(leaf, fi) ==
3316179e29e4SChris Mason 			    BTRFS_FILE_EXTENT_INLINE) {
3317179e29e4SChris Mason 				ptr = btrfs_item_ptr_offset(leaf, slot);
3318179e29e4SChris Mason 				memmove_extent_buffer(leaf, ptr,
3319179e29e4SChris Mason 				      (unsigned long)fi,
3320179e29e4SChris Mason 				      offsetof(struct btrfs_file_extent_item,
3321179e29e4SChris Mason 						 disk_bytenr));
3322179e29e4SChris Mason 			}
3323179e29e4SChris Mason 		}
3324179e29e4SChris Mason 
3325179e29e4SChris Mason 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3326179e29e4SChris Mason 			      data_end + size_diff, btrfs_leaf_data(leaf) +
3327179e29e4SChris Mason 			      data_end, old_data_start - data_end);
3328179e29e4SChris Mason 
3329179e29e4SChris Mason 		offset = btrfs_disk_key_offset(&disk_key);
3330179e29e4SChris Mason 		btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3331179e29e4SChris Mason 		btrfs_set_item_key(leaf, &disk_key, slot);
3332179e29e4SChris Mason 		if (slot == 0)
3333179e29e4SChris Mason 			fixup_low_keys(trans, root, path, &disk_key, 1);
3334179e29e4SChris Mason 	}
33355f39d397SChris Mason 
33365f39d397SChris Mason 	item = btrfs_item_nr(leaf, slot);
33375f39d397SChris Mason 	btrfs_set_item_size(leaf, item, new_size);
33385f39d397SChris Mason 	btrfs_mark_buffer_dirty(leaf);
3339b18c6685SChris Mason 
3340b18c6685SChris Mason 	ret = 0;
33415f39d397SChris Mason 	if (btrfs_leaf_free_space(root, leaf) < 0) {
33425f39d397SChris Mason 		btrfs_print_leaf(root, leaf);
3343b18c6685SChris Mason 		BUG();
33445f39d397SChris Mason 	}
3345b18c6685SChris Mason 	return ret;
3346b18c6685SChris Mason }
3347b18c6685SChris Mason 
3348d352ac68SChris Mason /*
3349d352ac68SChris Mason  * make the item pointed to by the path bigger, data_size is the new size.
3350d352ac68SChris Mason  */
33515f39d397SChris Mason int btrfs_extend_item(struct btrfs_trans_handle *trans,
33525f39d397SChris Mason 		      struct btrfs_root *root, struct btrfs_path *path,
33535f39d397SChris Mason 		      u32 data_size)
33546567e837SChris Mason {
33556567e837SChris Mason 	int ret = 0;
33566567e837SChris Mason 	int slot;
33576567e837SChris Mason 	int slot_orig;
33585f39d397SChris Mason 	struct extent_buffer *leaf;
33595f39d397SChris Mason 	struct btrfs_item *item;
33606567e837SChris Mason 	u32 nritems;
33616567e837SChris Mason 	unsigned int data_end;
33626567e837SChris Mason 	unsigned int old_data;
33636567e837SChris Mason 	unsigned int old_size;
33646567e837SChris Mason 	int i;
33656567e837SChris Mason 
33666567e837SChris Mason 	slot_orig = path->slots[0];
33675f39d397SChris Mason 	leaf = path->nodes[0];
33686567e837SChris Mason 
33695f39d397SChris Mason 	nritems = btrfs_header_nritems(leaf);
33706567e837SChris Mason 	data_end = leaf_data_end(root, leaf);
33716567e837SChris Mason 
33725f39d397SChris Mason 	if (btrfs_leaf_free_space(root, leaf) < data_size) {
33735f39d397SChris Mason 		btrfs_print_leaf(root, leaf);
33746567e837SChris Mason 		BUG();
33755f39d397SChris Mason 	}
33766567e837SChris Mason 	slot = path->slots[0];
33775f39d397SChris Mason 	old_data = btrfs_item_end_nr(leaf, slot);
33786567e837SChris Mason 
33796567e837SChris Mason 	BUG_ON(slot < 0);
33803326d1b0SChris Mason 	if (slot >= nritems) {
33813326d1b0SChris Mason 		btrfs_print_leaf(root, leaf);
3382d397712bSChris Mason 		printk(KERN_CRIT "slot %d too large, nritems %d\n",
3383d397712bSChris Mason 		       slot, nritems);
33843326d1b0SChris Mason 		BUG_ON(1);
33853326d1b0SChris Mason 	}
33866567e837SChris Mason 
33876567e837SChris Mason 	/*
33886567e837SChris Mason 	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
33896567e837SChris Mason 	 */
33906567e837SChris Mason 	/* first correct the data pointers */
33916567e837SChris Mason 	for (i = slot; i < nritems; i++) {
33925f39d397SChris Mason 		u32 ioff;
33935f39d397SChris Mason 		item = btrfs_item_nr(leaf, i);
3394db94535dSChris Mason 
3395db94535dSChris Mason 		if (!leaf->map_token) {
3396db94535dSChris Mason 			map_extent_buffer(leaf, (unsigned long)item,
3397db94535dSChris Mason 					sizeof(struct btrfs_item),
3398db94535dSChris Mason 					&leaf->map_token, &leaf->kaddr,
3399db94535dSChris Mason 					&leaf->map_start, &leaf->map_len,
3400db94535dSChris Mason 					KM_USER1);
3401db94535dSChris Mason 		}
34025f39d397SChris Mason 		ioff = btrfs_item_offset(leaf, item);
34035f39d397SChris Mason 		btrfs_set_item_offset(leaf, item, ioff - data_size);
34046567e837SChris Mason 	}
34055f39d397SChris Mason 
3406db94535dSChris Mason 	if (leaf->map_token) {
3407db94535dSChris Mason 		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3408db94535dSChris Mason 		leaf->map_token = NULL;
3409db94535dSChris Mason 	}
3410db94535dSChris Mason 
34116567e837SChris Mason 	/* shift the data */
34125f39d397SChris Mason 	memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
34136567e837SChris Mason 		      data_end - data_size, btrfs_leaf_data(leaf) +
34146567e837SChris Mason 		      data_end, old_data - data_end);
34155f39d397SChris Mason 
34166567e837SChris Mason 	data_end = old_data;
34175f39d397SChris Mason 	old_size = btrfs_item_size_nr(leaf, slot);
34185f39d397SChris Mason 	item = btrfs_item_nr(leaf, slot);
34195f39d397SChris Mason 	btrfs_set_item_size(leaf, item, old_size + data_size);
34205f39d397SChris Mason 	btrfs_mark_buffer_dirty(leaf);
34216567e837SChris Mason 
34226567e837SChris Mason 	ret = 0;
34235f39d397SChris Mason 	if (btrfs_leaf_free_space(root, leaf) < 0) {
34245f39d397SChris Mason 		btrfs_print_leaf(root, leaf);
34256567e837SChris Mason 		BUG();
34265f39d397SChris Mason 	}
34276567e837SChris Mason 	return ret;
34286567e837SChris Mason }
34296567e837SChris Mason 
343074123bd7SChris Mason /*
3431d352ac68SChris Mason  * Given a key and some data, insert items into the tree.
343274123bd7SChris Mason  * This does all the path init required, making room in the tree if needed.
3433f3465ca4SJosef Bacik  * Returns the number of keys that were inserted.
3434f3465ca4SJosef Bacik  */
3435f3465ca4SJosef Bacik int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3436f3465ca4SJosef Bacik 			    struct btrfs_root *root,
3437f3465ca4SJosef Bacik 			    struct btrfs_path *path,
3438f3465ca4SJosef Bacik 			    struct btrfs_key *cpu_key, u32 *data_size,
3439f3465ca4SJosef Bacik 			    int nr)
3440f3465ca4SJosef Bacik {
3441f3465ca4SJosef Bacik 	struct extent_buffer *leaf;
3442f3465ca4SJosef Bacik 	struct btrfs_item *item;
3443f3465ca4SJosef Bacik 	int ret = 0;
3444f3465ca4SJosef Bacik 	int slot;
3445f3465ca4SJosef Bacik 	int i;
3446f3465ca4SJosef Bacik 	u32 nritems;
3447f3465ca4SJosef Bacik 	u32 total_data = 0;
3448f3465ca4SJosef Bacik 	u32 total_size = 0;
3449f3465ca4SJosef Bacik 	unsigned int data_end;
3450f3465ca4SJosef Bacik 	struct btrfs_disk_key disk_key;
3451f3465ca4SJosef Bacik 	struct btrfs_key found_key;
3452f3465ca4SJosef Bacik 
345387b29b20SYan Zheng 	for (i = 0; i < nr; i++) {
345487b29b20SYan Zheng 		if (total_size + data_size[i] + sizeof(struct btrfs_item) >
345587b29b20SYan Zheng 		    BTRFS_LEAF_DATA_SIZE(root)) {
345687b29b20SYan Zheng 			break;
345787b29b20SYan Zheng 			nr = i;
345887b29b20SYan Zheng 		}
3459f3465ca4SJosef Bacik 		total_data += data_size[i];
346087b29b20SYan Zheng 		total_size += data_size[i] + sizeof(struct btrfs_item);
346187b29b20SYan Zheng 	}
346287b29b20SYan Zheng 	BUG_ON(nr == 0);
3463f3465ca4SJosef Bacik 
3464f3465ca4SJosef Bacik 	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3465f3465ca4SJosef Bacik 	if (ret == 0)
3466f3465ca4SJosef Bacik 		return -EEXIST;
3467f3465ca4SJosef Bacik 	if (ret < 0)
3468f3465ca4SJosef Bacik 		goto out;
3469f3465ca4SJosef Bacik 
3470f3465ca4SJosef Bacik 	leaf = path->nodes[0];
3471f3465ca4SJosef Bacik 
3472f3465ca4SJosef Bacik 	nritems = btrfs_header_nritems(leaf);
3473f3465ca4SJosef Bacik 	data_end = leaf_data_end(root, leaf);
3474f3465ca4SJosef Bacik 
3475f3465ca4SJosef Bacik 	if (btrfs_leaf_free_space(root, leaf) < total_size) {
3476f3465ca4SJosef Bacik 		for (i = nr; i >= 0; i--) {
3477f3465ca4SJosef Bacik 			total_data -= data_size[i];
3478f3465ca4SJosef Bacik 			total_size -= data_size[i] + sizeof(struct btrfs_item);
3479f3465ca4SJosef Bacik 			if (total_size < btrfs_leaf_free_space(root, leaf))
3480f3465ca4SJosef Bacik 				break;
3481f3465ca4SJosef Bacik 		}
3482f3465ca4SJosef Bacik 		nr = i;
3483f3465ca4SJosef Bacik 	}
3484f3465ca4SJosef Bacik 
3485f3465ca4SJosef Bacik 	slot = path->slots[0];
3486f3465ca4SJosef Bacik 	BUG_ON(slot < 0);
3487f3465ca4SJosef Bacik 
3488f3465ca4SJosef Bacik 	if (slot != nritems) {
3489f3465ca4SJosef Bacik 		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3490f3465ca4SJosef Bacik 
3491f3465ca4SJosef Bacik 		item = btrfs_item_nr(leaf, slot);
3492f3465ca4SJosef Bacik 		btrfs_item_key_to_cpu(leaf, &found_key, slot);
3493f3465ca4SJosef Bacik 
3494f3465ca4SJosef Bacik 		/* figure out how many keys we can insert in here */
3495f3465ca4SJosef Bacik 		total_data = data_size[0];
3496f3465ca4SJosef Bacik 		for (i = 1; i < nr; i++) {
34975d4f98a2SYan Zheng 			if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3498f3465ca4SJosef Bacik 				break;
3499f3465ca4SJosef Bacik 			total_data += data_size[i];
3500f3465ca4SJosef Bacik 		}
3501f3465ca4SJosef Bacik 		nr = i;
3502f3465ca4SJosef Bacik 
3503f3465ca4SJosef Bacik 		if (old_data < data_end) {
3504f3465ca4SJosef Bacik 			btrfs_print_leaf(root, leaf);
3505d397712bSChris Mason 			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3506f3465ca4SJosef Bacik 			       slot, old_data, data_end);
3507f3465ca4SJosef Bacik 			BUG_ON(1);
3508f3465ca4SJosef Bacik 		}
3509f3465ca4SJosef Bacik 		/*
3510f3465ca4SJosef Bacik 		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3511f3465ca4SJosef Bacik 		 */
3512f3465ca4SJosef Bacik 		/* first correct the data pointers */
3513f3465ca4SJosef Bacik 		WARN_ON(leaf->map_token);
3514f3465ca4SJosef Bacik 		for (i = slot; i < nritems; i++) {
3515f3465ca4SJosef Bacik 			u32 ioff;
3516f3465ca4SJosef Bacik 
3517f3465ca4SJosef Bacik 			item = btrfs_item_nr(leaf, i);
3518f3465ca4SJosef Bacik 			if (!leaf->map_token) {
3519f3465ca4SJosef Bacik 				map_extent_buffer(leaf, (unsigned long)item,
3520f3465ca4SJosef Bacik 					sizeof(struct btrfs_item),
3521f3465ca4SJosef Bacik 					&leaf->map_token, &leaf->kaddr,
3522f3465ca4SJosef Bacik 					&leaf->map_start, &leaf->map_len,
3523f3465ca4SJosef Bacik 					KM_USER1);
3524f3465ca4SJosef Bacik 			}
3525f3465ca4SJosef Bacik 
3526f3465ca4SJosef Bacik 			ioff = btrfs_item_offset(leaf, item);
3527f3465ca4SJosef Bacik 			btrfs_set_item_offset(leaf, item, ioff - total_data);
3528f3465ca4SJosef Bacik 		}
3529f3465ca4SJosef Bacik 		if (leaf->map_token) {
3530f3465ca4SJosef Bacik 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3531f3465ca4SJosef Bacik 			leaf->map_token = NULL;
3532f3465ca4SJosef Bacik 		}
3533f3465ca4SJosef Bacik 
3534f3465ca4SJosef Bacik 		/* shift the items */
3535f3465ca4SJosef Bacik 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3536f3465ca4SJosef Bacik 			      btrfs_item_nr_offset(slot),
3537f3465ca4SJosef Bacik 			      (nritems - slot) * sizeof(struct btrfs_item));
3538f3465ca4SJosef Bacik 
3539f3465ca4SJosef Bacik 		/* shift the data */
3540f3465ca4SJosef Bacik 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3541f3465ca4SJosef Bacik 			      data_end - total_data, btrfs_leaf_data(leaf) +
3542f3465ca4SJosef Bacik 			      data_end, old_data - data_end);
3543f3465ca4SJosef Bacik 		data_end = old_data;
3544f3465ca4SJosef Bacik 	} else {
3545f3465ca4SJosef Bacik 		/*
3546f3465ca4SJosef Bacik 		 * this sucks but it has to be done, if we are inserting at
3547f3465ca4SJosef Bacik 		 * the end of the leaf only insert 1 of the items, since we
3548f3465ca4SJosef Bacik 		 * have no way of knowing whats on the next leaf and we'd have
3549f3465ca4SJosef Bacik 		 * to drop our current locks to figure it out
3550f3465ca4SJosef Bacik 		 */
3551f3465ca4SJosef Bacik 		nr = 1;
3552f3465ca4SJosef Bacik 	}
3553f3465ca4SJosef Bacik 
3554f3465ca4SJosef Bacik 	/* setup the item for the new data */
3555f3465ca4SJosef Bacik 	for (i = 0; i < nr; i++) {
3556f3465ca4SJosef Bacik 		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3557f3465ca4SJosef Bacik 		btrfs_set_item_key(leaf, &disk_key, slot + i);
3558f3465ca4SJosef Bacik 		item = btrfs_item_nr(leaf, slot + i);
3559f3465ca4SJosef Bacik 		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3560f3465ca4SJosef Bacik 		data_end -= data_size[i];
3561f3465ca4SJosef Bacik 		btrfs_set_item_size(leaf, item, data_size[i]);
3562f3465ca4SJosef Bacik 	}
3563f3465ca4SJosef Bacik 	btrfs_set_header_nritems(leaf, nritems + nr);
3564f3465ca4SJosef Bacik 	btrfs_mark_buffer_dirty(leaf);
3565f3465ca4SJosef Bacik 
3566f3465ca4SJosef Bacik 	ret = 0;
3567f3465ca4SJosef Bacik 	if (slot == 0) {
3568f3465ca4SJosef Bacik 		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3569f3465ca4SJosef Bacik 		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3570f3465ca4SJosef Bacik 	}
3571f3465ca4SJosef Bacik 
3572f3465ca4SJosef Bacik 	if (btrfs_leaf_free_space(root, leaf) < 0) {
3573f3465ca4SJosef Bacik 		btrfs_print_leaf(root, leaf);
3574f3465ca4SJosef Bacik 		BUG();
3575f3465ca4SJosef Bacik 	}
3576f3465ca4SJosef Bacik out:
3577f3465ca4SJosef Bacik 	if (!ret)
3578f3465ca4SJosef Bacik 		ret = nr;
3579f3465ca4SJosef Bacik 	return ret;
3580f3465ca4SJosef Bacik }
3581f3465ca4SJosef Bacik 
3582f3465ca4SJosef Bacik /*
358344871b1bSChris Mason  * this is a helper for btrfs_insert_empty_items, the main goal here is
358444871b1bSChris Mason  * to save stack depth by doing the bulk of the work in a function
358544871b1bSChris Mason  * that doesn't call btrfs_search_slot
358674123bd7SChris Mason  */
358744871b1bSChris Mason static noinline_for_stack int
358844871b1bSChris Mason setup_items_for_insert(struct btrfs_trans_handle *trans,
358944871b1bSChris Mason 		      struct btrfs_root *root, struct btrfs_path *path,
35909c58309dSChris Mason 		      struct btrfs_key *cpu_key, u32 *data_size,
359144871b1bSChris Mason 		      u32 total_data, u32 total_size, int nr)
3592be0e5c09SChris Mason {
35935f39d397SChris Mason 	struct btrfs_item *item;
35949c58309dSChris Mason 	int i;
35957518a238SChris Mason 	u32 nritems;
3596be0e5c09SChris Mason 	unsigned int data_end;
3597e2fa7227SChris Mason 	struct btrfs_disk_key disk_key;
359844871b1bSChris Mason 	int ret;
359944871b1bSChris Mason 	struct extent_buffer *leaf;
360044871b1bSChris Mason 	int slot;
3601e2fa7227SChris Mason 
36025f39d397SChris Mason 	leaf = path->nodes[0];
360344871b1bSChris Mason 	slot = path->slots[0];
360474123bd7SChris Mason 
36055f39d397SChris Mason 	nritems = btrfs_header_nritems(leaf);
3606123abc88SChris Mason 	data_end = leaf_data_end(root, leaf);
3607eb60ceacSChris Mason 
3608f25956ccSChris Mason 	if (btrfs_leaf_free_space(root, leaf) < total_size) {
36093326d1b0SChris Mason 		btrfs_print_leaf(root, leaf);
3610d397712bSChris Mason 		printk(KERN_CRIT "not enough freespace need %u have %d\n",
36119c58309dSChris Mason 		       total_size, btrfs_leaf_free_space(root, leaf));
3612be0e5c09SChris Mason 		BUG();
3613d4dbff95SChris Mason 	}
36145f39d397SChris Mason 
3615be0e5c09SChris Mason 	if (slot != nritems) {
36165f39d397SChris Mason 		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3617be0e5c09SChris Mason 
36185f39d397SChris Mason 		if (old_data < data_end) {
36195f39d397SChris Mason 			btrfs_print_leaf(root, leaf);
3620d397712bSChris Mason 			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
36215f39d397SChris Mason 			       slot, old_data, data_end);
36225f39d397SChris Mason 			BUG_ON(1);
36235f39d397SChris Mason 		}
3624be0e5c09SChris Mason 		/*
3625be0e5c09SChris Mason 		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3626be0e5c09SChris Mason 		 */
3627be0e5c09SChris Mason 		/* first correct the data pointers */
3628db94535dSChris Mason 		WARN_ON(leaf->map_token);
36290783fcfcSChris Mason 		for (i = slot; i < nritems; i++) {
36305f39d397SChris Mason 			u32 ioff;
3631db94535dSChris Mason 
36325f39d397SChris Mason 			item = btrfs_item_nr(leaf, i);
3633db94535dSChris Mason 			if (!leaf->map_token) {
3634db94535dSChris Mason 				map_extent_buffer(leaf, (unsigned long)item,
3635db94535dSChris Mason 					sizeof(struct btrfs_item),
3636db94535dSChris Mason 					&leaf->map_token, &leaf->kaddr,
3637db94535dSChris Mason 					&leaf->map_start, &leaf->map_len,
3638db94535dSChris Mason 					KM_USER1);
3639db94535dSChris Mason 			}
3640db94535dSChris Mason 
36415f39d397SChris Mason 			ioff = btrfs_item_offset(leaf, item);
36429c58309dSChris Mason 			btrfs_set_item_offset(leaf, item, ioff - total_data);
36430783fcfcSChris Mason 		}
3644db94535dSChris Mason 		if (leaf->map_token) {
3645db94535dSChris Mason 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3646db94535dSChris Mason 			leaf->map_token = NULL;
3647db94535dSChris Mason 		}
3648be0e5c09SChris Mason 
3649be0e5c09SChris Mason 		/* shift the items */
36509c58309dSChris Mason 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
36515f39d397SChris Mason 			      btrfs_item_nr_offset(slot),
36520783fcfcSChris Mason 			      (nritems - slot) * sizeof(struct btrfs_item));
3653be0e5c09SChris Mason 
3654be0e5c09SChris Mason 		/* shift the data */
36555f39d397SChris Mason 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
36569c58309dSChris Mason 			      data_end - total_data, btrfs_leaf_data(leaf) +
3657be0e5c09SChris Mason 			      data_end, old_data - data_end);
3658be0e5c09SChris Mason 		data_end = old_data;
3659be0e5c09SChris Mason 	}
36605f39d397SChris Mason 
366162e2749eSChris Mason 	/* setup the item for the new data */
36629c58309dSChris Mason 	for (i = 0; i < nr; i++) {
36639c58309dSChris Mason 		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
36649c58309dSChris Mason 		btrfs_set_item_key(leaf, &disk_key, slot + i);
36659c58309dSChris Mason 		item = btrfs_item_nr(leaf, slot + i);
36669c58309dSChris Mason 		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
36679c58309dSChris Mason 		data_end -= data_size[i];
36689c58309dSChris Mason 		btrfs_set_item_size(leaf, item, data_size[i]);
36699c58309dSChris Mason 	}
367044871b1bSChris Mason 
36719c58309dSChris Mason 	btrfs_set_header_nritems(leaf, nritems + nr);
3672aa5d6bedSChris Mason 
3673aa5d6bedSChris Mason 	ret = 0;
36745a01a2e3SChris Mason 	if (slot == 0) {
367544871b1bSChris Mason 		struct btrfs_disk_key disk_key;
36765a01a2e3SChris Mason 		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3677e089f05cSChris Mason 		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
36785a01a2e3SChris Mason 	}
3679b9473439SChris Mason 	btrfs_unlock_up_safe(path, 1);
3680b9473439SChris Mason 	btrfs_mark_buffer_dirty(leaf);
3681aa5d6bedSChris Mason 
36825f39d397SChris Mason 	if (btrfs_leaf_free_space(root, leaf) < 0) {
36835f39d397SChris Mason 		btrfs_print_leaf(root, leaf);
3684be0e5c09SChris Mason 		BUG();
36855f39d397SChris Mason 	}
368644871b1bSChris Mason 	return ret;
368744871b1bSChris Mason }
368844871b1bSChris Mason 
368944871b1bSChris Mason /*
369044871b1bSChris Mason  * Given a key and some data, insert items into the tree.
369144871b1bSChris Mason  * This does all the path init required, making room in the tree if needed.
369244871b1bSChris Mason  */
369344871b1bSChris Mason int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
369444871b1bSChris Mason 			    struct btrfs_root *root,
369544871b1bSChris Mason 			    struct btrfs_path *path,
369644871b1bSChris Mason 			    struct btrfs_key *cpu_key, u32 *data_size,
369744871b1bSChris Mason 			    int nr)
369844871b1bSChris Mason {
369944871b1bSChris Mason 	struct extent_buffer *leaf;
370044871b1bSChris Mason 	int ret = 0;
370144871b1bSChris Mason 	int slot;
370244871b1bSChris Mason 	int i;
370344871b1bSChris Mason 	u32 total_size = 0;
370444871b1bSChris Mason 	u32 total_data = 0;
370544871b1bSChris Mason 
370644871b1bSChris Mason 	for (i = 0; i < nr; i++)
370744871b1bSChris Mason 		total_data += data_size[i];
370844871b1bSChris Mason 
370944871b1bSChris Mason 	total_size = total_data + (nr * sizeof(struct btrfs_item));
371044871b1bSChris Mason 	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
371144871b1bSChris Mason 	if (ret == 0)
371244871b1bSChris Mason 		return -EEXIST;
371344871b1bSChris Mason 	if (ret < 0)
371444871b1bSChris Mason 		goto out;
371544871b1bSChris Mason 
371644871b1bSChris Mason 	leaf = path->nodes[0];
371744871b1bSChris Mason 	slot = path->slots[0];
371844871b1bSChris Mason 	BUG_ON(slot < 0);
371944871b1bSChris Mason 
372044871b1bSChris Mason 	ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
372144871b1bSChris Mason 			       total_data, total_size, nr);
372244871b1bSChris Mason 
3723ed2ff2cbSChris Mason out:
372462e2749eSChris Mason 	return ret;
372562e2749eSChris Mason }
372662e2749eSChris Mason 
372762e2749eSChris Mason /*
372862e2749eSChris Mason  * Given a key and some data, insert an item into the tree.
372962e2749eSChris Mason  * This does all the path init required, making room in the tree if needed.
373062e2749eSChris Mason  */
3731e089f05cSChris Mason int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3732e089f05cSChris Mason 		      *root, struct btrfs_key *cpu_key, void *data, u32
3733e089f05cSChris Mason 		      data_size)
373462e2749eSChris Mason {
373562e2749eSChris Mason 	int ret = 0;
37362c90e5d6SChris Mason 	struct btrfs_path *path;
37375f39d397SChris Mason 	struct extent_buffer *leaf;
37385f39d397SChris Mason 	unsigned long ptr;
373962e2749eSChris Mason 
37402c90e5d6SChris Mason 	path = btrfs_alloc_path();
37412c90e5d6SChris Mason 	BUG_ON(!path);
37422c90e5d6SChris Mason 	ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
374362e2749eSChris Mason 	if (!ret) {
37445f39d397SChris Mason 		leaf = path->nodes[0];
37455f39d397SChris Mason 		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
37465f39d397SChris Mason 		write_extent_buffer(leaf, data, ptr, data_size);
37475f39d397SChris Mason 		btrfs_mark_buffer_dirty(leaf);
374862e2749eSChris Mason 	}
37492c90e5d6SChris Mason 	btrfs_free_path(path);
3750aa5d6bedSChris Mason 	return ret;
3751be0e5c09SChris Mason }
3752be0e5c09SChris Mason 
375374123bd7SChris Mason /*
37545de08d7dSChris Mason  * delete the pointer from a given node.
375574123bd7SChris Mason  *
3756d352ac68SChris Mason  * the tree should have been previously balanced so the deletion does not
3757d352ac68SChris Mason  * empty a node.
375874123bd7SChris Mason  */
3759e089f05cSChris Mason static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3760e089f05cSChris Mason 		   struct btrfs_path *path, int level, int slot)
3761be0e5c09SChris Mason {
37625f39d397SChris Mason 	struct extent_buffer *parent = path->nodes[level];
37637518a238SChris Mason 	u32 nritems;
3764aa5d6bedSChris Mason 	int ret = 0;
3765bb803951SChris Mason 	int wret;
3766be0e5c09SChris Mason 
37675f39d397SChris Mason 	nritems = btrfs_header_nritems(parent);
3768be0e5c09SChris Mason 	if (slot != nritems - 1) {
37695f39d397SChris Mason 		memmove_extent_buffer(parent,
37705f39d397SChris Mason 			      btrfs_node_key_ptr_offset(slot),
37715f39d397SChris Mason 			      btrfs_node_key_ptr_offset(slot + 1),
3772d6025579SChris Mason 			      sizeof(struct btrfs_key_ptr) *
3773d6025579SChris Mason 			      (nritems - slot - 1));
3774be0e5c09SChris Mason 	}
37757518a238SChris Mason 	nritems--;
37765f39d397SChris Mason 	btrfs_set_header_nritems(parent, nritems);
37777518a238SChris Mason 	if (nritems == 0 && parent == root->node) {
37785f39d397SChris Mason 		BUG_ON(btrfs_header_level(root->node) != 1);
3779eb60ceacSChris Mason 		/* just turn the root into a leaf and break */
37805f39d397SChris Mason 		btrfs_set_header_level(root->node, 0);
3781bb803951SChris Mason 	} else if (slot == 0) {
37825f39d397SChris Mason 		struct btrfs_disk_key disk_key;
37835f39d397SChris Mason 
37845f39d397SChris Mason 		btrfs_node_key(parent, &disk_key, 0);
37855f39d397SChris Mason 		wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
37860f70abe2SChris Mason 		if (wret)
37870f70abe2SChris Mason 			ret = wret;
3788be0e5c09SChris Mason 	}
3789d6025579SChris Mason 	btrfs_mark_buffer_dirty(parent);
3790aa5d6bedSChris Mason 	return ret;
3791be0e5c09SChris Mason }
3792be0e5c09SChris Mason 
379374123bd7SChris Mason /*
3794323ac95bSChris Mason  * a helper function to delete the leaf pointed to by path->slots[1] and
37955d4f98a2SYan Zheng  * path->nodes[1].
3796323ac95bSChris Mason  *
3797323ac95bSChris Mason  * This deletes the pointer in path->nodes[1] and frees the leaf
3798323ac95bSChris Mason  * block extent.  zero is returned if it all worked out, < 0 otherwise.
3799323ac95bSChris Mason  *
3800323ac95bSChris Mason  * The path must have already been setup for deleting the leaf, including
3801323ac95bSChris Mason  * all the proper balancing.  path->nodes[1] must be locked.
3802323ac95bSChris Mason  */
38035d4f98a2SYan Zheng static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3804323ac95bSChris Mason 				   struct btrfs_root *root,
38055d4f98a2SYan Zheng 				   struct btrfs_path *path,
38065d4f98a2SYan Zheng 				   struct extent_buffer *leaf)
3807323ac95bSChris Mason {
3808323ac95bSChris Mason 	int ret;
3809323ac95bSChris Mason 
38105d4f98a2SYan Zheng 	WARN_ON(btrfs_header_generation(leaf) != trans->transid);
3811323ac95bSChris Mason 	ret = del_ptr(trans, root, path, 1, path->slots[1]);
3812323ac95bSChris Mason 	if (ret)
3813323ac95bSChris Mason 		return ret;
3814323ac95bSChris Mason 
38154d081c41SChris Mason 	/*
38164d081c41SChris Mason 	 * btrfs_free_extent is expensive, we want to make sure we
38174d081c41SChris Mason 	 * aren't holding any locks when we call it
38184d081c41SChris Mason 	 */
38194d081c41SChris Mason 	btrfs_unlock_up_safe(path, 0);
38204d081c41SChris Mason 
3821f0486c68SYan, Zheng 	root_sub_used(root, leaf->len);
3822f0486c68SYan, Zheng 
3823f0486c68SYan, Zheng 	btrfs_free_tree_block(trans, root, leaf, 0, 1);
3824f0486c68SYan, Zheng 	return 0;
3825323ac95bSChris Mason }
3826323ac95bSChris Mason /*
382774123bd7SChris Mason  * delete the item at the leaf level in path.  If that empties
382874123bd7SChris Mason  * the leaf, remove it from the tree
382974123bd7SChris Mason  */
383085e21bacSChris Mason int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
383185e21bacSChris Mason 		    struct btrfs_path *path, int slot, int nr)
3832be0e5c09SChris Mason {
38335f39d397SChris Mason 	struct extent_buffer *leaf;
38345f39d397SChris Mason 	struct btrfs_item *item;
383585e21bacSChris Mason 	int last_off;
383685e21bacSChris Mason 	int dsize = 0;
3837aa5d6bedSChris Mason 	int ret = 0;
3838aa5d6bedSChris Mason 	int wret;
383985e21bacSChris Mason 	int i;
38407518a238SChris Mason 	u32 nritems;
3841be0e5c09SChris Mason 
38425f39d397SChris Mason 	leaf = path->nodes[0];
384385e21bacSChris Mason 	last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
384485e21bacSChris Mason 
384585e21bacSChris Mason 	for (i = 0; i < nr; i++)
384685e21bacSChris Mason 		dsize += btrfs_item_size_nr(leaf, slot + i);
384785e21bacSChris Mason 
38485f39d397SChris Mason 	nritems = btrfs_header_nritems(leaf);
3849be0e5c09SChris Mason 
385085e21bacSChris Mason 	if (slot + nr != nritems) {
3851123abc88SChris Mason 		int data_end = leaf_data_end(root, leaf);
38525f39d397SChris Mason 
38535f39d397SChris Mason 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3854d6025579SChris Mason 			      data_end + dsize,
3855123abc88SChris Mason 			      btrfs_leaf_data(leaf) + data_end,
385685e21bacSChris Mason 			      last_off - data_end);
38575f39d397SChris Mason 
385885e21bacSChris Mason 		for (i = slot + nr; i < nritems; i++) {
38595f39d397SChris Mason 			u32 ioff;
3860db94535dSChris Mason 
38615f39d397SChris Mason 			item = btrfs_item_nr(leaf, i);
3862db94535dSChris Mason 			if (!leaf->map_token) {
3863db94535dSChris Mason 				map_extent_buffer(leaf, (unsigned long)item,
3864db94535dSChris Mason 					sizeof(struct btrfs_item),
3865db94535dSChris Mason 					&leaf->map_token, &leaf->kaddr,
3866db94535dSChris Mason 					&leaf->map_start, &leaf->map_len,
3867db94535dSChris Mason 					KM_USER1);
3868db94535dSChris Mason 			}
38695f39d397SChris Mason 			ioff = btrfs_item_offset(leaf, item);
38705f39d397SChris Mason 			btrfs_set_item_offset(leaf, item, ioff + dsize);
38710783fcfcSChris Mason 		}
3872db94535dSChris Mason 
3873db94535dSChris Mason 		if (leaf->map_token) {
3874db94535dSChris Mason 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3875db94535dSChris Mason 			leaf->map_token = NULL;
3876db94535dSChris Mason 		}
3877db94535dSChris Mason 
38785f39d397SChris Mason 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
387985e21bacSChris Mason 			      btrfs_item_nr_offset(slot + nr),
38800783fcfcSChris Mason 			      sizeof(struct btrfs_item) *
388185e21bacSChris Mason 			      (nritems - slot - nr));
3882be0e5c09SChris Mason 	}
388385e21bacSChris Mason 	btrfs_set_header_nritems(leaf, nritems - nr);
388485e21bacSChris Mason 	nritems -= nr;
38855f39d397SChris Mason 
388674123bd7SChris Mason 	/* delete the leaf if we've emptied it */
38877518a238SChris Mason 	if (nritems == 0) {
38885f39d397SChris Mason 		if (leaf == root->node) {
38895f39d397SChris Mason 			btrfs_set_header_level(leaf, 0);
38909a8dd150SChris Mason 		} else {
3891f0486c68SYan, Zheng 			btrfs_set_path_blocking(path);
3892f0486c68SYan, Zheng 			clean_tree_block(trans, root, leaf);
38935d4f98a2SYan Zheng 			ret = btrfs_del_leaf(trans, root, path, leaf);
3894323ac95bSChris Mason 			BUG_ON(ret);
38959a8dd150SChris Mason 		}
3896be0e5c09SChris Mason 	} else {
38977518a238SChris Mason 		int used = leaf_space_used(leaf, 0, nritems);
3898aa5d6bedSChris Mason 		if (slot == 0) {
38995f39d397SChris Mason 			struct btrfs_disk_key disk_key;
39005f39d397SChris Mason 
39015f39d397SChris Mason 			btrfs_item_key(leaf, &disk_key, 0);
3902e089f05cSChris Mason 			wret = fixup_low_keys(trans, root, path,
39035f39d397SChris Mason 					      &disk_key, 1);
3904aa5d6bedSChris Mason 			if (wret)
3905aa5d6bedSChris Mason 				ret = wret;
3906aa5d6bedSChris Mason 		}
3907aa5d6bedSChris Mason 
390874123bd7SChris Mason 		/* delete the leaf if it is mostly empty */
3909d717aa1dSYan Zheng 		if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
3910be0e5c09SChris Mason 			/* push_leaf_left fixes the path.
3911be0e5c09SChris Mason 			 * make sure the path still points to our leaf
3912be0e5c09SChris Mason 			 * for possible call to del_ptr below
3913be0e5c09SChris Mason 			 */
39144920c9acSChris Mason 			slot = path->slots[1];
39155f39d397SChris Mason 			extent_buffer_get(leaf);
39165f39d397SChris Mason 
3917b9473439SChris Mason 			btrfs_set_path_blocking(path);
391885e21bacSChris Mason 			wret = push_leaf_left(trans, root, path, 1, 1);
391954aa1f4dSChris Mason 			if (wret < 0 && wret != -ENOSPC)
3920aa5d6bedSChris Mason 				ret = wret;
39215f39d397SChris Mason 
39225f39d397SChris Mason 			if (path->nodes[0] == leaf &&
39235f39d397SChris Mason 			    btrfs_header_nritems(leaf)) {
392485e21bacSChris Mason 				wret = push_leaf_right(trans, root, path, 1, 1);
392554aa1f4dSChris Mason 				if (wret < 0 && wret != -ENOSPC)
3926aa5d6bedSChris Mason 					ret = wret;
3927aa5d6bedSChris Mason 			}
39285f39d397SChris Mason 
39295f39d397SChris Mason 			if (btrfs_header_nritems(leaf) == 0) {
3930323ac95bSChris Mason 				path->slots[1] = slot;
39315d4f98a2SYan Zheng 				ret = btrfs_del_leaf(trans, root, path, leaf);
3932323ac95bSChris Mason 				BUG_ON(ret);
39335f39d397SChris Mason 				free_extent_buffer(leaf);
39345de08d7dSChris Mason 			} else {
3935925baeddSChris Mason 				/* if we're still in the path, make sure
3936925baeddSChris Mason 				 * we're dirty.  Otherwise, one of the
3937925baeddSChris Mason 				 * push_leaf functions must have already
3938925baeddSChris Mason 				 * dirtied this buffer
3939925baeddSChris Mason 				 */
3940925baeddSChris Mason 				if (path->nodes[0] == leaf)
39415f39d397SChris Mason 					btrfs_mark_buffer_dirty(leaf);
39425f39d397SChris Mason 				free_extent_buffer(leaf);
3943be0e5c09SChris Mason 			}
3944d5719762SChris Mason 		} else {
39455f39d397SChris Mason 			btrfs_mark_buffer_dirty(leaf);
3946be0e5c09SChris Mason 		}
39479a8dd150SChris Mason 	}
3948aa5d6bedSChris Mason 	return ret;
39499a8dd150SChris Mason }
39509a8dd150SChris Mason 
395197571fd0SChris Mason /*
3952925baeddSChris Mason  * search the tree again to find a leaf with lesser keys
39537bb86316SChris Mason  * returns 0 if it found something or 1 if there are no lesser leaves.
39547bb86316SChris Mason  * returns < 0 on io errors.
3955d352ac68SChris Mason  *
3956d352ac68SChris Mason  * This may release the path, and so you may lose any locks held at the
3957d352ac68SChris Mason  * time you call it.
39587bb86316SChris Mason  */
39597bb86316SChris Mason int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
39607bb86316SChris Mason {
3961925baeddSChris Mason 	struct btrfs_key key;
3962925baeddSChris Mason 	struct btrfs_disk_key found_key;
3963925baeddSChris Mason 	int ret;
39647bb86316SChris Mason 
3965925baeddSChris Mason 	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
3966925baeddSChris Mason 
3967925baeddSChris Mason 	if (key.offset > 0)
3968925baeddSChris Mason 		key.offset--;
3969925baeddSChris Mason 	else if (key.type > 0)
3970925baeddSChris Mason 		key.type--;
3971925baeddSChris Mason 	else if (key.objectid > 0)
3972925baeddSChris Mason 		key.objectid--;
3973925baeddSChris Mason 	else
39747bb86316SChris Mason 		return 1;
39757bb86316SChris Mason 
3976925baeddSChris Mason 	btrfs_release_path(root, path);
3977925baeddSChris Mason 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3978925baeddSChris Mason 	if (ret < 0)
3979925baeddSChris Mason 		return ret;
3980925baeddSChris Mason 	btrfs_item_key(path->nodes[0], &found_key, 0);
3981925baeddSChris Mason 	ret = comp_keys(&found_key, &key);
3982925baeddSChris Mason 	if (ret < 0)
39837bb86316SChris Mason 		return 0;
3984925baeddSChris Mason 	return 1;
39857bb86316SChris Mason }
39867bb86316SChris Mason 
39873f157a2fSChris Mason /*
39883f157a2fSChris Mason  * A helper function to walk down the tree starting at min_key, and looking
39893f157a2fSChris Mason  * for nodes or leaves that are either in cache or have a minimum
3990d352ac68SChris Mason  * transaction id.  This is used by the btree defrag code, and tree logging
39913f157a2fSChris Mason  *
39923f157a2fSChris Mason  * This does not cow, but it does stuff the starting key it finds back
39933f157a2fSChris Mason  * into min_key, so you can call btrfs_search_slot with cow=1 on the
39943f157a2fSChris Mason  * key and get a writable path.
39953f157a2fSChris Mason  *
39963f157a2fSChris Mason  * This does lock as it descends, and path->keep_locks should be set
39973f157a2fSChris Mason  * to 1 by the caller.
39983f157a2fSChris Mason  *
39993f157a2fSChris Mason  * This honors path->lowest_level to prevent descent past a given level
40003f157a2fSChris Mason  * of the tree.
40013f157a2fSChris Mason  *
4002d352ac68SChris Mason  * min_trans indicates the oldest transaction that you are interested
4003d352ac68SChris Mason  * in walking through.  Any nodes or leaves older than min_trans are
4004d352ac68SChris Mason  * skipped over (without reading them).
4005d352ac68SChris Mason  *
40063f157a2fSChris Mason  * returns zero if something useful was found, < 0 on error and 1 if there
40073f157a2fSChris Mason  * was nothing in the tree that matched the search criteria.
40083f157a2fSChris Mason  */
40093f157a2fSChris Mason int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
4010e02119d5SChris Mason 			 struct btrfs_key *max_key,
40113f157a2fSChris Mason 			 struct btrfs_path *path, int cache_only,
40123f157a2fSChris Mason 			 u64 min_trans)
40133f157a2fSChris Mason {
40143f157a2fSChris Mason 	struct extent_buffer *cur;
40153f157a2fSChris Mason 	struct btrfs_key found_key;
40163f157a2fSChris Mason 	int slot;
40179652480bSYan 	int sret;
40183f157a2fSChris Mason 	u32 nritems;
40193f157a2fSChris Mason 	int level;
40203f157a2fSChris Mason 	int ret = 1;
40213f157a2fSChris Mason 
4022934d375bSChris Mason 	WARN_ON(!path->keep_locks);
40233f157a2fSChris Mason again:
40243f157a2fSChris Mason 	cur = btrfs_lock_root_node(root);
40253f157a2fSChris Mason 	level = btrfs_header_level(cur);
4026e02119d5SChris Mason 	WARN_ON(path->nodes[level]);
40273f157a2fSChris Mason 	path->nodes[level] = cur;
40283f157a2fSChris Mason 	path->locks[level] = 1;
40293f157a2fSChris Mason 
40303f157a2fSChris Mason 	if (btrfs_header_generation(cur) < min_trans) {
40313f157a2fSChris Mason 		ret = 1;
40323f157a2fSChris Mason 		goto out;
40333f157a2fSChris Mason 	}
40343f157a2fSChris Mason 	while (1) {
40353f157a2fSChris Mason 		nritems = btrfs_header_nritems(cur);
40363f157a2fSChris Mason 		level = btrfs_header_level(cur);
40379652480bSYan 		sret = bin_search(cur, min_key, level, &slot);
40383f157a2fSChris Mason 
4039323ac95bSChris Mason 		/* at the lowest level, we're done, setup the path and exit */
4040323ac95bSChris Mason 		if (level == path->lowest_level) {
4041e02119d5SChris Mason 			if (slot >= nritems)
4042e02119d5SChris Mason 				goto find_next_key;
40433f157a2fSChris Mason 			ret = 0;
40443f157a2fSChris Mason 			path->slots[level] = slot;
40453f157a2fSChris Mason 			btrfs_item_key_to_cpu(cur, &found_key, slot);
40463f157a2fSChris Mason 			goto out;
40473f157a2fSChris Mason 		}
40489652480bSYan 		if (sret && slot > 0)
40499652480bSYan 			slot--;
40503f157a2fSChris Mason 		/*
40513f157a2fSChris Mason 		 * check this node pointer against the cache_only and
40523f157a2fSChris Mason 		 * min_trans parameters.  If it isn't in cache or is too
40533f157a2fSChris Mason 		 * old, skip to the next one.
40543f157a2fSChris Mason 		 */
40553f157a2fSChris Mason 		while (slot < nritems) {
40563f157a2fSChris Mason 			u64 blockptr;
40573f157a2fSChris Mason 			u64 gen;
40583f157a2fSChris Mason 			struct extent_buffer *tmp;
4059e02119d5SChris Mason 			struct btrfs_disk_key disk_key;
4060e02119d5SChris Mason 
40613f157a2fSChris Mason 			blockptr = btrfs_node_blockptr(cur, slot);
40623f157a2fSChris Mason 			gen = btrfs_node_ptr_generation(cur, slot);
40633f157a2fSChris Mason 			if (gen < min_trans) {
40643f157a2fSChris Mason 				slot++;
40653f157a2fSChris Mason 				continue;
40663f157a2fSChris Mason 			}
40673f157a2fSChris Mason 			if (!cache_only)
40683f157a2fSChris Mason 				break;
40693f157a2fSChris Mason 
4070e02119d5SChris Mason 			if (max_key) {
4071e02119d5SChris Mason 				btrfs_node_key(cur, &disk_key, slot);
4072e02119d5SChris Mason 				if (comp_keys(&disk_key, max_key) >= 0) {
4073e02119d5SChris Mason 					ret = 1;
4074e02119d5SChris Mason 					goto out;
4075e02119d5SChris Mason 				}
4076e02119d5SChris Mason 			}
4077e02119d5SChris Mason 
40783f157a2fSChris Mason 			tmp = btrfs_find_tree_block(root, blockptr,
40793f157a2fSChris Mason 					    btrfs_level_size(root, level - 1));
40803f157a2fSChris Mason 
40813f157a2fSChris Mason 			if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
40823f157a2fSChris Mason 				free_extent_buffer(tmp);
40833f157a2fSChris Mason 				break;
40843f157a2fSChris Mason 			}
40853f157a2fSChris Mason 			if (tmp)
40863f157a2fSChris Mason 				free_extent_buffer(tmp);
40873f157a2fSChris Mason 			slot++;
40883f157a2fSChris Mason 		}
4089e02119d5SChris Mason find_next_key:
40903f157a2fSChris Mason 		/*
40913f157a2fSChris Mason 		 * we didn't find a candidate key in this node, walk forward
40923f157a2fSChris Mason 		 * and find another one
40933f157a2fSChris Mason 		 */
40943f157a2fSChris Mason 		if (slot >= nritems) {
4095e02119d5SChris Mason 			path->slots[level] = slot;
4096b4ce94deSChris Mason 			btrfs_set_path_blocking(path);
4097e02119d5SChris Mason 			sret = btrfs_find_next_key(root, path, min_key, level,
40983f157a2fSChris Mason 						  cache_only, min_trans);
4099e02119d5SChris Mason 			if (sret == 0) {
41003f157a2fSChris Mason 				btrfs_release_path(root, path);
41013f157a2fSChris Mason 				goto again;
41023f157a2fSChris Mason 			} else {
41033f157a2fSChris Mason 				goto out;
41043f157a2fSChris Mason 			}
41053f157a2fSChris Mason 		}
41063f157a2fSChris Mason 		/* save our key for returning back */
41073f157a2fSChris Mason 		btrfs_node_key_to_cpu(cur, &found_key, slot);
41083f157a2fSChris Mason 		path->slots[level] = slot;
41093f157a2fSChris Mason 		if (level == path->lowest_level) {
41103f157a2fSChris Mason 			ret = 0;
41113f157a2fSChris Mason 			unlock_up(path, level, 1);
41123f157a2fSChris Mason 			goto out;
41133f157a2fSChris Mason 		}
4114b4ce94deSChris Mason 		btrfs_set_path_blocking(path);
41153f157a2fSChris Mason 		cur = read_node_slot(root, cur, slot);
41163f157a2fSChris Mason 
41173f157a2fSChris Mason 		btrfs_tree_lock(cur);
4118b4ce94deSChris Mason 
41193f157a2fSChris Mason 		path->locks[level - 1] = 1;
41203f157a2fSChris Mason 		path->nodes[level - 1] = cur;
41213f157a2fSChris Mason 		unlock_up(path, level, 1);
41224008c04aSChris Mason 		btrfs_clear_path_blocking(path, NULL);
41233f157a2fSChris Mason 	}
41243f157a2fSChris Mason out:
41253f157a2fSChris Mason 	if (ret == 0)
41263f157a2fSChris Mason 		memcpy(min_key, &found_key, sizeof(found_key));
4127b4ce94deSChris Mason 	btrfs_set_path_blocking(path);
41283f157a2fSChris Mason 	return ret;
41293f157a2fSChris Mason }
41303f157a2fSChris Mason 
41313f157a2fSChris Mason /*
41323f157a2fSChris Mason  * this is similar to btrfs_next_leaf, but does not try to preserve
41333f157a2fSChris Mason  * and fixup the path.  It looks for and returns the next key in the
41343f157a2fSChris Mason  * tree based on the current path and the cache_only and min_trans
41353f157a2fSChris Mason  * parameters.
41363f157a2fSChris Mason  *
41373f157a2fSChris Mason  * 0 is returned if another key is found, < 0 if there are any errors
41383f157a2fSChris Mason  * and 1 is returned if there are no higher keys in the tree
41393f157a2fSChris Mason  *
41403f157a2fSChris Mason  * path->keep_locks should be set to 1 on the search made before
41413f157a2fSChris Mason  * calling this function.
41423f157a2fSChris Mason  */
4143e7a84565SChris Mason int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
414433c66f43SYan Zheng 			struct btrfs_key *key, int level,
41453f157a2fSChris Mason 			int cache_only, u64 min_trans)
4146e7a84565SChris Mason {
4147e7a84565SChris Mason 	int slot;
4148e7a84565SChris Mason 	struct extent_buffer *c;
4149e7a84565SChris Mason 
4150934d375bSChris Mason 	WARN_ON(!path->keep_locks);
4151e7a84565SChris Mason 	while (level < BTRFS_MAX_LEVEL) {
4152e7a84565SChris Mason 		if (!path->nodes[level])
4153e7a84565SChris Mason 			return 1;
4154e7a84565SChris Mason 
4155e7a84565SChris Mason 		slot = path->slots[level] + 1;
4156e7a84565SChris Mason 		c = path->nodes[level];
41573f157a2fSChris Mason next:
4158e7a84565SChris Mason 		if (slot >= btrfs_header_nritems(c)) {
415933c66f43SYan Zheng 			int ret;
416033c66f43SYan Zheng 			int orig_lowest;
416133c66f43SYan Zheng 			struct btrfs_key cur_key;
416233c66f43SYan Zheng 			if (level + 1 >= BTRFS_MAX_LEVEL ||
416333c66f43SYan Zheng 			    !path->nodes[level + 1])
4164e7a84565SChris Mason 				return 1;
416533c66f43SYan Zheng 
416633c66f43SYan Zheng 			if (path->locks[level + 1]) {
416733c66f43SYan Zheng 				level++;
4168e7a84565SChris Mason 				continue;
4169e7a84565SChris Mason 			}
417033c66f43SYan Zheng 
417133c66f43SYan Zheng 			slot = btrfs_header_nritems(c) - 1;
417233c66f43SYan Zheng 			if (level == 0)
417333c66f43SYan Zheng 				btrfs_item_key_to_cpu(c, &cur_key, slot);
417433c66f43SYan Zheng 			else
417533c66f43SYan Zheng 				btrfs_node_key_to_cpu(c, &cur_key, slot);
417633c66f43SYan Zheng 
417733c66f43SYan Zheng 			orig_lowest = path->lowest_level;
417833c66f43SYan Zheng 			btrfs_release_path(root, path);
417933c66f43SYan Zheng 			path->lowest_level = level;
418033c66f43SYan Zheng 			ret = btrfs_search_slot(NULL, root, &cur_key, path,
418133c66f43SYan Zheng 						0, 0);
418233c66f43SYan Zheng 			path->lowest_level = orig_lowest;
418333c66f43SYan Zheng 			if (ret < 0)
418433c66f43SYan Zheng 				return ret;
418533c66f43SYan Zheng 
418633c66f43SYan Zheng 			c = path->nodes[level];
418733c66f43SYan Zheng 			slot = path->slots[level];
418833c66f43SYan Zheng 			if (ret == 0)
418933c66f43SYan Zheng 				slot++;
419033c66f43SYan Zheng 			goto next;
419133c66f43SYan Zheng 		}
419233c66f43SYan Zheng 
4193e7a84565SChris Mason 		if (level == 0)
4194e7a84565SChris Mason 			btrfs_item_key_to_cpu(c, key, slot);
41953f157a2fSChris Mason 		else {
41963f157a2fSChris Mason 			u64 blockptr = btrfs_node_blockptr(c, slot);
41973f157a2fSChris Mason 			u64 gen = btrfs_node_ptr_generation(c, slot);
41983f157a2fSChris Mason 
41993f157a2fSChris Mason 			if (cache_only) {
42003f157a2fSChris Mason 				struct extent_buffer *cur;
42013f157a2fSChris Mason 				cur = btrfs_find_tree_block(root, blockptr,
42023f157a2fSChris Mason 					    btrfs_level_size(root, level - 1));
42033f157a2fSChris Mason 				if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
42043f157a2fSChris Mason 					slot++;
42053f157a2fSChris Mason 					if (cur)
42063f157a2fSChris Mason 						free_extent_buffer(cur);
42073f157a2fSChris Mason 					goto next;
42083f157a2fSChris Mason 				}
42093f157a2fSChris Mason 				free_extent_buffer(cur);
42103f157a2fSChris Mason 			}
42113f157a2fSChris Mason 			if (gen < min_trans) {
42123f157a2fSChris Mason 				slot++;
42133f157a2fSChris Mason 				goto next;
42143f157a2fSChris Mason 			}
4215e7a84565SChris Mason 			btrfs_node_key_to_cpu(c, key, slot);
42163f157a2fSChris Mason 		}
4217e7a84565SChris Mason 		return 0;
4218e7a84565SChris Mason 	}
4219e7a84565SChris Mason 	return 1;
4220e7a84565SChris Mason }
4221e7a84565SChris Mason 
42227bb86316SChris Mason /*
4223925baeddSChris Mason  * search the tree again to find a leaf with greater keys
42240f70abe2SChris Mason  * returns 0 if it found something or 1 if there are no greater leaves.
42250f70abe2SChris Mason  * returns < 0 on io errors.
422697571fd0SChris Mason  */
4227234b63a0SChris Mason int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4228d97e63b6SChris Mason {
4229d97e63b6SChris Mason 	int slot;
42308e73f275SChris Mason 	int level;
42315f39d397SChris Mason 	struct extent_buffer *c;
42328e73f275SChris Mason 	struct extent_buffer *next;
4233925baeddSChris Mason 	struct btrfs_key key;
4234925baeddSChris Mason 	u32 nritems;
4235925baeddSChris Mason 	int ret;
42368e73f275SChris Mason 	int old_spinning = path->leave_spinning;
42378e73f275SChris Mason 	int force_blocking = 0;
4238925baeddSChris Mason 
4239925baeddSChris Mason 	nritems = btrfs_header_nritems(path->nodes[0]);
4240d397712bSChris Mason 	if (nritems == 0)
4241925baeddSChris Mason 		return 1;
4242925baeddSChris Mason 
42438e73f275SChris Mason 	/*
42448e73f275SChris Mason 	 * we take the blocks in an order that upsets lockdep.  Using
42458e73f275SChris Mason 	 * blocking mode is the only way around it.
42468e73f275SChris Mason 	 */
42478e73f275SChris Mason #ifdef CONFIG_DEBUG_LOCK_ALLOC
42488e73f275SChris Mason 	force_blocking = 1;
42498e73f275SChris Mason #endif
4250925baeddSChris Mason 
42518e73f275SChris Mason 	btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
42528e73f275SChris Mason again:
42538e73f275SChris Mason 	level = 1;
42548e73f275SChris Mason 	next = NULL;
4255925baeddSChris Mason 	btrfs_release_path(root, path);
42568e73f275SChris Mason 
4257a2135011SChris Mason 	path->keep_locks = 1;
42588e73f275SChris Mason 
42598e73f275SChris Mason 	if (!force_blocking)
42608e73f275SChris Mason 		path->leave_spinning = 1;
42618e73f275SChris Mason 
4262925baeddSChris Mason 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4263925baeddSChris Mason 	path->keep_locks = 0;
4264925baeddSChris Mason 
4265925baeddSChris Mason 	if (ret < 0)
4266925baeddSChris Mason 		return ret;
4267925baeddSChris Mason 
4268a2135011SChris Mason 	nritems = btrfs_header_nritems(path->nodes[0]);
4269168fd7d2SChris Mason 	/*
4270168fd7d2SChris Mason 	 * by releasing the path above we dropped all our locks.  A balance
4271168fd7d2SChris Mason 	 * could have added more items next to the key that used to be
4272168fd7d2SChris Mason 	 * at the very end of the block.  So, check again here and
4273168fd7d2SChris Mason 	 * advance the path if there are now more items available.
4274168fd7d2SChris Mason 	 */
4275a2135011SChris Mason 	if (nritems > 0 && path->slots[0] < nritems - 1) {
4276e457afecSYan Zheng 		if (ret == 0)
4277168fd7d2SChris Mason 			path->slots[0]++;
42788e73f275SChris Mason 		ret = 0;
4279925baeddSChris Mason 		goto done;
4280925baeddSChris Mason 	}
4281d97e63b6SChris Mason 
4282234b63a0SChris Mason 	while (level < BTRFS_MAX_LEVEL) {
42838e73f275SChris Mason 		if (!path->nodes[level]) {
42848e73f275SChris Mason 			ret = 1;
42858e73f275SChris Mason 			goto done;
42868e73f275SChris Mason 		}
42875f39d397SChris Mason 
4288d97e63b6SChris Mason 		slot = path->slots[level] + 1;
4289d97e63b6SChris Mason 		c = path->nodes[level];
42905f39d397SChris Mason 		if (slot >= btrfs_header_nritems(c)) {
4291d97e63b6SChris Mason 			level++;
42928e73f275SChris Mason 			if (level == BTRFS_MAX_LEVEL) {
42938e73f275SChris Mason 				ret = 1;
42948e73f275SChris Mason 				goto done;
42958e73f275SChris Mason 			}
4296d97e63b6SChris Mason 			continue;
4297d97e63b6SChris Mason 		}
42985f39d397SChris Mason 
4299925baeddSChris Mason 		if (next) {
4300925baeddSChris Mason 			btrfs_tree_unlock(next);
43015f39d397SChris Mason 			free_extent_buffer(next);
4302925baeddSChris Mason 		}
43035f39d397SChris Mason 
43048e73f275SChris Mason 		next = c;
43058e73f275SChris Mason 		ret = read_block_for_search(NULL, root, path, &next, level,
43068e73f275SChris Mason 					    slot, &key);
43078e73f275SChris Mason 		if (ret == -EAGAIN)
43088e73f275SChris Mason 			goto again;
43095f39d397SChris Mason 
431076a05b35SChris Mason 		if (ret < 0) {
431176a05b35SChris Mason 			btrfs_release_path(root, path);
431276a05b35SChris Mason 			goto done;
431376a05b35SChris Mason 		}
431476a05b35SChris Mason 
43155cd57b2cSChris Mason 		if (!path->skip_locking) {
43168e73f275SChris Mason 			ret = btrfs_try_spin_lock(next);
43178e73f275SChris Mason 			if (!ret) {
43188e73f275SChris Mason 				btrfs_set_path_blocking(path);
4319925baeddSChris Mason 				btrfs_tree_lock(next);
43208e73f275SChris Mason 				if (!force_blocking)
43218e73f275SChris Mason 					btrfs_clear_path_blocking(path, next);
43228e73f275SChris Mason 			}
43238e73f275SChris Mason 			if (force_blocking)
4324b4ce94deSChris Mason 				btrfs_set_lock_blocking(next);
43255cd57b2cSChris Mason 		}
4326d97e63b6SChris Mason 		break;
4327d97e63b6SChris Mason 	}
4328d97e63b6SChris Mason 	path->slots[level] = slot;
4329d97e63b6SChris Mason 	while (1) {
4330d97e63b6SChris Mason 		level--;
4331d97e63b6SChris Mason 		c = path->nodes[level];
4332925baeddSChris Mason 		if (path->locks[level])
4333925baeddSChris Mason 			btrfs_tree_unlock(c);
43348e73f275SChris Mason 
43355f39d397SChris Mason 		free_extent_buffer(c);
4336d97e63b6SChris Mason 		path->nodes[level] = next;
4337d97e63b6SChris Mason 		path->slots[level] = 0;
4338a74a4b97SChris Mason 		if (!path->skip_locking)
4339925baeddSChris Mason 			path->locks[level] = 1;
43408e73f275SChris Mason 
4341d97e63b6SChris Mason 		if (!level)
4342d97e63b6SChris Mason 			break;
4343b4ce94deSChris Mason 
43448e73f275SChris Mason 		ret = read_block_for_search(NULL, root, path, &next, level,
43458e73f275SChris Mason 					    0, &key);
43468e73f275SChris Mason 		if (ret == -EAGAIN)
43478e73f275SChris Mason 			goto again;
43488e73f275SChris Mason 
434976a05b35SChris Mason 		if (ret < 0) {
435076a05b35SChris Mason 			btrfs_release_path(root, path);
435176a05b35SChris Mason 			goto done;
435276a05b35SChris Mason 		}
435376a05b35SChris Mason 
43545cd57b2cSChris Mason 		if (!path->skip_locking) {
4355b9447ef8SChris Mason 			btrfs_assert_tree_locked(path->nodes[level]);
43568e73f275SChris Mason 			ret = btrfs_try_spin_lock(next);
43578e73f275SChris Mason 			if (!ret) {
43588e73f275SChris Mason 				btrfs_set_path_blocking(path);
4359925baeddSChris Mason 				btrfs_tree_lock(next);
43608e73f275SChris Mason 				if (!force_blocking)
43618e73f275SChris Mason 					btrfs_clear_path_blocking(path, next);
43628e73f275SChris Mason 			}
43638e73f275SChris Mason 			if (force_blocking)
4364b4ce94deSChris Mason 				btrfs_set_lock_blocking(next);
4365d97e63b6SChris Mason 		}
43665cd57b2cSChris Mason 	}
43678e73f275SChris Mason 	ret = 0;
4368925baeddSChris Mason done:
4369925baeddSChris Mason 	unlock_up(path, 0, 1);
43708e73f275SChris Mason 	path->leave_spinning = old_spinning;
43718e73f275SChris Mason 	if (!old_spinning)
43728e73f275SChris Mason 		btrfs_set_path_blocking(path);
43738e73f275SChris Mason 
43748e73f275SChris Mason 	return ret;
4375d97e63b6SChris Mason }
43760b86a832SChris Mason 
43773f157a2fSChris Mason /*
43783f157a2fSChris Mason  * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
43793f157a2fSChris Mason  * searching until it gets past min_objectid or finds an item of 'type'
43803f157a2fSChris Mason  *
43813f157a2fSChris Mason  * returns 0 if something is found, 1 if nothing was found and < 0 on error
43823f157a2fSChris Mason  */
43830b86a832SChris Mason int btrfs_previous_item(struct btrfs_root *root,
43840b86a832SChris Mason 			struct btrfs_path *path, u64 min_objectid,
43850b86a832SChris Mason 			int type)
43860b86a832SChris Mason {
43870b86a832SChris Mason 	struct btrfs_key found_key;
43880b86a832SChris Mason 	struct extent_buffer *leaf;
4389e02119d5SChris Mason 	u32 nritems;
43900b86a832SChris Mason 	int ret;
43910b86a832SChris Mason 
43920b86a832SChris Mason 	while (1) {
43930b86a832SChris Mason 		if (path->slots[0] == 0) {
4394b4ce94deSChris Mason 			btrfs_set_path_blocking(path);
43950b86a832SChris Mason 			ret = btrfs_prev_leaf(root, path);
43960b86a832SChris Mason 			if (ret != 0)
43970b86a832SChris Mason 				return ret;
43980b86a832SChris Mason 		} else {
43990b86a832SChris Mason 			path->slots[0]--;
44000b86a832SChris Mason 		}
44010b86a832SChris Mason 		leaf = path->nodes[0];
4402e02119d5SChris Mason 		nritems = btrfs_header_nritems(leaf);
4403e02119d5SChris Mason 		if (nritems == 0)
4404e02119d5SChris Mason 			return 1;
4405e02119d5SChris Mason 		if (path->slots[0] == nritems)
4406e02119d5SChris Mason 			path->slots[0]--;
4407e02119d5SChris Mason 
44080b86a832SChris Mason 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4409e02119d5SChris Mason 		if (found_key.objectid < min_objectid)
4410e02119d5SChris Mason 			break;
44110a4eefbbSYan Zheng 		if (found_key.type == type)
44120a4eefbbSYan Zheng 			return 0;
4413e02119d5SChris Mason 		if (found_key.objectid == min_objectid &&
4414e02119d5SChris Mason 		    found_key.type < type)
4415e02119d5SChris Mason 			break;
44160b86a832SChris Mason 	}
44170b86a832SChris Mason 	return 1;
44180b86a832SChris Mason }
4419