xref: /openbmc/linux/fs/btrfs/ctree.c (revision 81d67439)
1 /*
2  * Copyright (C) 2007,2008 Oracle.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18 
19 #include <linux/sched.h>
20 #include <linux/slab.h>
21 #include "ctree.h"
22 #include "disk-io.h"
23 #include "transaction.h"
24 #include "print-tree.h"
25 #include "locking.h"
26 
27 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
28 		      *root, struct btrfs_path *path, int level);
29 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
30 		      *root, struct btrfs_key *ins_key,
31 		      struct btrfs_path *path, int data_size, int extend);
32 static int push_node_left(struct btrfs_trans_handle *trans,
33 			  struct btrfs_root *root, struct extent_buffer *dst,
34 			  struct extent_buffer *src, int empty);
35 static int balance_node_right(struct btrfs_trans_handle *trans,
36 			      struct btrfs_root *root,
37 			      struct extent_buffer *dst_buf,
38 			      struct extent_buffer *src_buf);
39 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
40 		   struct btrfs_path *path, int level, int slot);
41 
42 struct btrfs_path *btrfs_alloc_path(void)
43 {
44 	struct btrfs_path *path;
45 	path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
46 	return path;
47 }
48 
49 /*
50  * set all locked nodes in the path to blocking locks.  This should
51  * be done before scheduling
52  */
53 noinline void btrfs_set_path_blocking(struct btrfs_path *p)
54 {
55 	int i;
56 	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
57 		if (p->nodes[i] && p->locks[i])
58 			btrfs_set_lock_blocking(p->nodes[i]);
59 	}
60 }
61 
62 /*
63  * reset all the locked nodes in the patch to spinning locks.
64  *
65  * held is used to keep lockdep happy, when lockdep is enabled
66  * we set held to a blocking lock before we go around and
67  * retake all the spinlocks in the path.  You can safely use NULL
68  * for held
69  */
70 noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
71 					struct extent_buffer *held)
72 {
73 	int i;
74 
75 #ifdef CONFIG_DEBUG_LOCK_ALLOC
76 	/* lockdep really cares that we take all of these spinlocks
77 	 * in the right order.  If any of the locks in the path are not
78 	 * currently blocking, it is going to complain.  So, make really
79 	 * really sure by forcing the path to blocking before we clear
80 	 * the path blocking.
81 	 */
82 	if (held)
83 		btrfs_set_lock_blocking(held);
84 	btrfs_set_path_blocking(p);
85 #endif
86 
87 	for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
88 		if (p->nodes[i] && p->locks[i])
89 			btrfs_clear_lock_blocking(p->nodes[i]);
90 	}
91 
92 #ifdef CONFIG_DEBUG_LOCK_ALLOC
93 	if (held)
94 		btrfs_clear_lock_blocking(held);
95 #endif
96 }
97 
98 /* this also releases the path */
99 void btrfs_free_path(struct btrfs_path *p)
100 {
101 	if (!p)
102 		return;
103 	btrfs_release_path(p);
104 	kmem_cache_free(btrfs_path_cachep, p);
105 }
106 
107 /*
108  * path release drops references on the extent buffers in the path
109  * and it drops any locks held by this path
110  *
111  * It is safe to call this on paths that no locks or extent buffers held.
112  */
113 noinline void btrfs_release_path(struct btrfs_path *p)
114 {
115 	int i;
116 
117 	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
118 		p->slots[i] = 0;
119 		if (!p->nodes[i])
120 			continue;
121 		if (p->locks[i]) {
122 			btrfs_tree_unlock(p->nodes[i]);
123 			p->locks[i] = 0;
124 		}
125 		free_extent_buffer(p->nodes[i]);
126 		p->nodes[i] = NULL;
127 	}
128 }
129 
130 /*
131  * safely gets a reference on the root node of a tree.  A lock
132  * is not taken, so a concurrent writer may put a different node
133  * at the root of the tree.  See btrfs_lock_root_node for the
134  * looping required.
135  *
136  * The extent buffer returned by this has a reference taken, so
137  * it won't disappear.  It may stop being the root of the tree
138  * at any time because there are no locks held.
139  */
140 struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
141 {
142 	struct extent_buffer *eb;
143 
144 	rcu_read_lock();
145 	eb = rcu_dereference(root->node);
146 	extent_buffer_get(eb);
147 	rcu_read_unlock();
148 	return eb;
149 }
150 
151 /* loop around taking references on and locking the root node of the
152  * tree until you end up with a lock on the root.  A locked buffer
153  * is returned, with a reference held.
154  */
155 struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
156 {
157 	struct extent_buffer *eb;
158 
159 	while (1) {
160 		eb = btrfs_root_node(root);
161 		btrfs_tree_lock(eb);
162 		if (eb == root->node)
163 			break;
164 		btrfs_tree_unlock(eb);
165 		free_extent_buffer(eb);
166 	}
167 	return eb;
168 }
169 
170 /* cowonly root (everything not a reference counted cow subvolume), just get
171  * put onto a simple dirty list.  transaction.c walks this to make sure they
172  * get properly updated on disk.
173  */
174 static void add_root_to_dirty_list(struct btrfs_root *root)
175 {
176 	if (root->track_dirty && list_empty(&root->dirty_list)) {
177 		list_add(&root->dirty_list,
178 			 &root->fs_info->dirty_cowonly_roots);
179 	}
180 }
181 
182 /*
183  * used by snapshot creation to make a copy of a root for a tree with
184  * a given objectid.  The buffer with the new root node is returned in
185  * cow_ret, and this func returns zero on success or a negative error code.
186  */
187 int btrfs_copy_root(struct btrfs_trans_handle *trans,
188 		      struct btrfs_root *root,
189 		      struct extent_buffer *buf,
190 		      struct extent_buffer **cow_ret, u64 new_root_objectid)
191 {
192 	struct extent_buffer *cow;
193 	int ret = 0;
194 	int level;
195 	struct btrfs_disk_key disk_key;
196 
197 	WARN_ON(root->ref_cows && trans->transid !=
198 		root->fs_info->running_transaction->transid);
199 	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
200 
201 	level = btrfs_header_level(buf);
202 	if (level == 0)
203 		btrfs_item_key(buf, &disk_key, 0);
204 	else
205 		btrfs_node_key(buf, &disk_key, 0);
206 
207 	cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
208 				     new_root_objectid, &disk_key, level,
209 				     buf->start, 0);
210 	if (IS_ERR(cow))
211 		return PTR_ERR(cow);
212 
213 	copy_extent_buffer(cow, buf, 0, 0, cow->len);
214 	btrfs_set_header_bytenr(cow, cow->start);
215 	btrfs_set_header_generation(cow, trans->transid);
216 	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
217 	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
218 				     BTRFS_HEADER_FLAG_RELOC);
219 	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
220 		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
221 	else
222 		btrfs_set_header_owner(cow, new_root_objectid);
223 
224 	write_extent_buffer(cow, root->fs_info->fsid,
225 			    (unsigned long)btrfs_header_fsid(cow),
226 			    BTRFS_FSID_SIZE);
227 
228 	WARN_ON(btrfs_header_generation(buf) > trans->transid);
229 	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
230 		ret = btrfs_inc_ref(trans, root, cow, 1);
231 	else
232 		ret = btrfs_inc_ref(trans, root, cow, 0);
233 
234 	if (ret)
235 		return ret;
236 
237 	btrfs_mark_buffer_dirty(cow);
238 	*cow_ret = cow;
239 	return 0;
240 }
241 
242 /*
243  * check if the tree block can be shared by multiple trees
244  */
245 int btrfs_block_can_be_shared(struct btrfs_root *root,
246 			      struct extent_buffer *buf)
247 {
248 	/*
249 	 * Tree blocks not in refernece counted trees and tree roots
250 	 * are never shared. If a block was allocated after the last
251 	 * snapshot and the block was not allocated by tree relocation,
252 	 * we know the block is not shared.
253 	 */
254 	if (root->ref_cows &&
255 	    buf != root->node && buf != root->commit_root &&
256 	    (btrfs_header_generation(buf) <=
257 	     btrfs_root_last_snapshot(&root->root_item) ||
258 	     btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
259 		return 1;
260 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
261 	if (root->ref_cows &&
262 	    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
263 		return 1;
264 #endif
265 	return 0;
266 }
267 
268 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
269 				       struct btrfs_root *root,
270 				       struct extent_buffer *buf,
271 				       struct extent_buffer *cow,
272 				       int *last_ref)
273 {
274 	u64 refs;
275 	u64 owner;
276 	u64 flags;
277 	u64 new_flags = 0;
278 	int ret;
279 
280 	/*
281 	 * Backrefs update rules:
282 	 *
283 	 * Always use full backrefs for extent pointers in tree block
284 	 * allocated by tree relocation.
285 	 *
286 	 * If a shared tree block is no longer referenced by its owner
287 	 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
288 	 * use full backrefs for extent pointers in tree block.
289 	 *
290 	 * If a tree block is been relocating
291 	 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
292 	 * use full backrefs for extent pointers in tree block.
293 	 * The reason for this is some operations (such as drop tree)
294 	 * are only allowed for blocks use full backrefs.
295 	 */
296 
297 	if (btrfs_block_can_be_shared(root, buf)) {
298 		ret = btrfs_lookup_extent_info(trans, root, buf->start,
299 					       buf->len, &refs, &flags);
300 		BUG_ON(ret);
301 		BUG_ON(refs == 0);
302 	} else {
303 		refs = 1;
304 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
305 		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
306 			flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
307 		else
308 			flags = 0;
309 	}
310 
311 	owner = btrfs_header_owner(buf);
312 	BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
313 	       !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
314 
315 	if (refs > 1) {
316 		if ((owner == root->root_key.objectid ||
317 		     root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
318 		    !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
319 			ret = btrfs_inc_ref(trans, root, buf, 1);
320 			BUG_ON(ret);
321 
322 			if (root->root_key.objectid ==
323 			    BTRFS_TREE_RELOC_OBJECTID) {
324 				ret = btrfs_dec_ref(trans, root, buf, 0);
325 				BUG_ON(ret);
326 				ret = btrfs_inc_ref(trans, root, cow, 1);
327 				BUG_ON(ret);
328 			}
329 			new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
330 		} else {
331 
332 			if (root->root_key.objectid ==
333 			    BTRFS_TREE_RELOC_OBJECTID)
334 				ret = btrfs_inc_ref(trans, root, cow, 1);
335 			else
336 				ret = btrfs_inc_ref(trans, root, cow, 0);
337 			BUG_ON(ret);
338 		}
339 		if (new_flags != 0) {
340 			ret = btrfs_set_disk_extent_flags(trans, root,
341 							  buf->start,
342 							  buf->len,
343 							  new_flags, 0);
344 			BUG_ON(ret);
345 		}
346 	} else {
347 		if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
348 			if (root->root_key.objectid ==
349 			    BTRFS_TREE_RELOC_OBJECTID)
350 				ret = btrfs_inc_ref(trans, root, cow, 1);
351 			else
352 				ret = btrfs_inc_ref(trans, root, cow, 0);
353 			BUG_ON(ret);
354 			ret = btrfs_dec_ref(trans, root, buf, 1);
355 			BUG_ON(ret);
356 		}
357 		clean_tree_block(trans, root, buf);
358 		*last_ref = 1;
359 	}
360 	return 0;
361 }
362 
363 /*
364  * does the dirty work in cow of a single block.  The parent block (if
365  * supplied) is updated to point to the new cow copy.  The new buffer is marked
366  * dirty and returned locked.  If you modify the block it needs to be marked
367  * dirty again.
368  *
369  * search_start -- an allocation hint for the new block
370  *
371  * empty_size -- a hint that you plan on doing more cow.  This is the size in
372  * bytes the allocator should try to find free next to the block it returns.
373  * This is just a hint and may be ignored by the allocator.
374  */
375 static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
376 			     struct btrfs_root *root,
377 			     struct extent_buffer *buf,
378 			     struct extent_buffer *parent, int parent_slot,
379 			     struct extent_buffer **cow_ret,
380 			     u64 search_start, u64 empty_size)
381 {
382 	struct btrfs_disk_key disk_key;
383 	struct extent_buffer *cow;
384 	int level;
385 	int last_ref = 0;
386 	int unlock_orig = 0;
387 	u64 parent_start;
388 
389 	if (*cow_ret == buf)
390 		unlock_orig = 1;
391 
392 	btrfs_assert_tree_locked(buf);
393 
394 	WARN_ON(root->ref_cows && trans->transid !=
395 		root->fs_info->running_transaction->transid);
396 	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
397 
398 	level = btrfs_header_level(buf);
399 
400 	if (level == 0)
401 		btrfs_item_key(buf, &disk_key, 0);
402 	else
403 		btrfs_node_key(buf, &disk_key, 0);
404 
405 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
406 		if (parent)
407 			parent_start = parent->start;
408 		else
409 			parent_start = 0;
410 	} else
411 		parent_start = 0;
412 
413 	cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
414 				     root->root_key.objectid, &disk_key,
415 				     level, search_start, empty_size);
416 	if (IS_ERR(cow))
417 		return PTR_ERR(cow);
418 
419 	/* cow is set to blocking by btrfs_init_new_buffer */
420 
421 	copy_extent_buffer(cow, buf, 0, 0, cow->len);
422 	btrfs_set_header_bytenr(cow, cow->start);
423 	btrfs_set_header_generation(cow, trans->transid);
424 	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
425 	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
426 				     BTRFS_HEADER_FLAG_RELOC);
427 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
428 		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
429 	else
430 		btrfs_set_header_owner(cow, root->root_key.objectid);
431 
432 	write_extent_buffer(cow, root->fs_info->fsid,
433 			    (unsigned long)btrfs_header_fsid(cow),
434 			    BTRFS_FSID_SIZE);
435 
436 	update_ref_for_cow(trans, root, buf, cow, &last_ref);
437 
438 	if (root->ref_cows)
439 		btrfs_reloc_cow_block(trans, root, buf, cow);
440 
441 	if (buf == root->node) {
442 		WARN_ON(parent && parent != buf);
443 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
444 		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
445 			parent_start = buf->start;
446 		else
447 			parent_start = 0;
448 
449 		extent_buffer_get(cow);
450 		rcu_assign_pointer(root->node, cow);
451 
452 		btrfs_free_tree_block(trans, root, buf, parent_start,
453 				      last_ref);
454 		free_extent_buffer(buf);
455 		add_root_to_dirty_list(root);
456 	} else {
457 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
458 			parent_start = parent->start;
459 		else
460 			parent_start = 0;
461 
462 		WARN_ON(trans->transid != btrfs_header_generation(parent));
463 		btrfs_set_node_blockptr(parent, parent_slot,
464 					cow->start);
465 		btrfs_set_node_ptr_generation(parent, parent_slot,
466 					      trans->transid);
467 		btrfs_mark_buffer_dirty(parent);
468 		btrfs_free_tree_block(trans, root, buf, parent_start,
469 				      last_ref);
470 	}
471 	if (unlock_orig)
472 		btrfs_tree_unlock(buf);
473 	free_extent_buffer(buf);
474 	btrfs_mark_buffer_dirty(cow);
475 	*cow_ret = cow;
476 	return 0;
477 }
478 
479 static inline int should_cow_block(struct btrfs_trans_handle *trans,
480 				   struct btrfs_root *root,
481 				   struct extent_buffer *buf)
482 {
483 	if (btrfs_header_generation(buf) == trans->transid &&
484 	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
485 	    !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
486 	      btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
487 		return 0;
488 	return 1;
489 }
490 
491 /*
492  * cows a single block, see __btrfs_cow_block for the real work.
493  * This version of it has extra checks so that a block isn't cow'd more than
494  * once per transaction, as long as it hasn't been written yet
495  */
496 noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
497 		    struct btrfs_root *root, struct extent_buffer *buf,
498 		    struct extent_buffer *parent, int parent_slot,
499 		    struct extent_buffer **cow_ret)
500 {
501 	u64 search_start;
502 	int ret;
503 
504 	if (trans->transaction != root->fs_info->running_transaction) {
505 		printk(KERN_CRIT "trans %llu running %llu\n",
506 		       (unsigned long long)trans->transid,
507 		       (unsigned long long)
508 		       root->fs_info->running_transaction->transid);
509 		WARN_ON(1);
510 	}
511 	if (trans->transid != root->fs_info->generation) {
512 		printk(KERN_CRIT "trans %llu running %llu\n",
513 		       (unsigned long long)trans->transid,
514 		       (unsigned long long)root->fs_info->generation);
515 		WARN_ON(1);
516 	}
517 
518 	if (!should_cow_block(trans, root, buf)) {
519 		*cow_ret = buf;
520 		return 0;
521 	}
522 
523 	search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
524 
525 	if (parent)
526 		btrfs_set_lock_blocking(parent);
527 	btrfs_set_lock_blocking(buf);
528 
529 	ret = __btrfs_cow_block(trans, root, buf, parent,
530 				 parent_slot, cow_ret, search_start, 0);
531 
532 	trace_btrfs_cow_block(root, buf, *cow_ret);
533 
534 	return ret;
535 }
536 
537 /*
538  * helper function for defrag to decide if two blocks pointed to by a
539  * node are actually close by
540  */
541 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
542 {
543 	if (blocknr < other && other - (blocknr + blocksize) < 32768)
544 		return 1;
545 	if (blocknr > other && blocknr - (other + blocksize) < 32768)
546 		return 1;
547 	return 0;
548 }
549 
550 /*
551  * compare two keys in a memcmp fashion
552  */
553 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
554 {
555 	struct btrfs_key k1;
556 
557 	btrfs_disk_key_to_cpu(&k1, disk);
558 
559 	return btrfs_comp_cpu_keys(&k1, k2);
560 }
561 
562 /*
563  * same as comp_keys only with two btrfs_key's
564  */
565 int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
566 {
567 	if (k1->objectid > k2->objectid)
568 		return 1;
569 	if (k1->objectid < k2->objectid)
570 		return -1;
571 	if (k1->type > k2->type)
572 		return 1;
573 	if (k1->type < k2->type)
574 		return -1;
575 	if (k1->offset > k2->offset)
576 		return 1;
577 	if (k1->offset < k2->offset)
578 		return -1;
579 	return 0;
580 }
581 
582 /*
583  * this is used by the defrag code to go through all the
584  * leaves pointed to by a node and reallocate them so that
585  * disk order is close to key order
586  */
587 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
588 		       struct btrfs_root *root, struct extent_buffer *parent,
589 		       int start_slot, int cache_only, u64 *last_ret,
590 		       struct btrfs_key *progress)
591 {
592 	struct extent_buffer *cur;
593 	u64 blocknr;
594 	u64 gen;
595 	u64 search_start = *last_ret;
596 	u64 last_block = 0;
597 	u64 other;
598 	u32 parent_nritems;
599 	int end_slot;
600 	int i;
601 	int err = 0;
602 	int parent_level;
603 	int uptodate;
604 	u32 blocksize;
605 	int progress_passed = 0;
606 	struct btrfs_disk_key disk_key;
607 
608 	parent_level = btrfs_header_level(parent);
609 	if (cache_only && parent_level != 1)
610 		return 0;
611 
612 	if (trans->transaction != root->fs_info->running_transaction)
613 		WARN_ON(1);
614 	if (trans->transid != root->fs_info->generation)
615 		WARN_ON(1);
616 
617 	parent_nritems = btrfs_header_nritems(parent);
618 	blocksize = btrfs_level_size(root, parent_level - 1);
619 	end_slot = parent_nritems;
620 
621 	if (parent_nritems == 1)
622 		return 0;
623 
624 	btrfs_set_lock_blocking(parent);
625 
626 	for (i = start_slot; i < end_slot; i++) {
627 		int close = 1;
628 
629 		if (!parent->map_token) {
630 			map_extent_buffer(parent,
631 					btrfs_node_key_ptr_offset(i),
632 					sizeof(struct btrfs_key_ptr),
633 					&parent->map_token, &parent->kaddr,
634 					&parent->map_start, &parent->map_len,
635 					KM_USER1);
636 		}
637 		btrfs_node_key(parent, &disk_key, i);
638 		if (!progress_passed && comp_keys(&disk_key, progress) < 0)
639 			continue;
640 
641 		progress_passed = 1;
642 		blocknr = btrfs_node_blockptr(parent, i);
643 		gen = btrfs_node_ptr_generation(parent, i);
644 		if (last_block == 0)
645 			last_block = blocknr;
646 
647 		if (i > 0) {
648 			other = btrfs_node_blockptr(parent, i - 1);
649 			close = close_blocks(blocknr, other, blocksize);
650 		}
651 		if (!close && i < end_slot - 2) {
652 			other = btrfs_node_blockptr(parent, i + 1);
653 			close = close_blocks(blocknr, other, blocksize);
654 		}
655 		if (close) {
656 			last_block = blocknr;
657 			continue;
658 		}
659 		if (parent->map_token) {
660 			unmap_extent_buffer(parent, parent->map_token,
661 					    KM_USER1);
662 			parent->map_token = NULL;
663 		}
664 
665 		cur = btrfs_find_tree_block(root, blocknr, blocksize);
666 		if (cur)
667 			uptodate = btrfs_buffer_uptodate(cur, gen);
668 		else
669 			uptodate = 0;
670 		if (!cur || !uptodate) {
671 			if (cache_only) {
672 				free_extent_buffer(cur);
673 				continue;
674 			}
675 			if (!cur) {
676 				cur = read_tree_block(root, blocknr,
677 							 blocksize, gen);
678 				if (!cur)
679 					return -EIO;
680 			} else if (!uptodate) {
681 				btrfs_read_buffer(cur, gen);
682 			}
683 		}
684 		if (search_start == 0)
685 			search_start = last_block;
686 
687 		btrfs_tree_lock(cur);
688 		btrfs_set_lock_blocking(cur);
689 		err = __btrfs_cow_block(trans, root, cur, parent, i,
690 					&cur, search_start,
691 					min(16 * blocksize,
692 					    (end_slot - i) * blocksize));
693 		if (err) {
694 			btrfs_tree_unlock(cur);
695 			free_extent_buffer(cur);
696 			break;
697 		}
698 		search_start = cur->start;
699 		last_block = cur->start;
700 		*last_ret = search_start;
701 		btrfs_tree_unlock(cur);
702 		free_extent_buffer(cur);
703 	}
704 	if (parent->map_token) {
705 		unmap_extent_buffer(parent, parent->map_token,
706 				    KM_USER1);
707 		parent->map_token = NULL;
708 	}
709 	return err;
710 }
711 
712 /*
713  * The leaf data grows from end-to-front in the node.
714  * this returns the address of the start of the last item,
715  * which is the stop of the leaf data stack
716  */
717 static inline unsigned int leaf_data_end(struct btrfs_root *root,
718 					 struct extent_buffer *leaf)
719 {
720 	u32 nr = btrfs_header_nritems(leaf);
721 	if (nr == 0)
722 		return BTRFS_LEAF_DATA_SIZE(root);
723 	return btrfs_item_offset_nr(leaf, nr - 1);
724 }
725 
726 
727 /*
728  * search for key in the extent_buffer.  The items start at offset p,
729  * and they are item_size apart.  There are 'max' items in p.
730  *
731  * the slot in the array is returned via slot, and it points to
732  * the place where you would insert key if it is not found in
733  * the array.
734  *
735  * slot may point to max if the key is bigger than all of the keys
736  */
737 static noinline int generic_bin_search(struct extent_buffer *eb,
738 				       unsigned long p,
739 				       int item_size, struct btrfs_key *key,
740 				       int max, int *slot)
741 {
742 	int low = 0;
743 	int high = max;
744 	int mid;
745 	int ret;
746 	struct btrfs_disk_key *tmp = NULL;
747 	struct btrfs_disk_key unaligned;
748 	unsigned long offset;
749 	char *map_token = NULL;
750 	char *kaddr = NULL;
751 	unsigned long map_start = 0;
752 	unsigned long map_len = 0;
753 	int err;
754 
755 	while (low < high) {
756 		mid = (low + high) / 2;
757 		offset = p + mid * item_size;
758 
759 		if (!map_token || offset < map_start ||
760 		    (offset + sizeof(struct btrfs_disk_key)) >
761 		    map_start + map_len) {
762 			if (map_token) {
763 				unmap_extent_buffer(eb, map_token, KM_USER0);
764 				map_token = NULL;
765 			}
766 
767 			err = map_private_extent_buffer(eb, offset,
768 						sizeof(struct btrfs_disk_key),
769 						&map_token, &kaddr,
770 						&map_start, &map_len, KM_USER0);
771 
772 			if (!err) {
773 				tmp = (struct btrfs_disk_key *)(kaddr + offset -
774 							map_start);
775 			} else {
776 				read_extent_buffer(eb, &unaligned,
777 						   offset, sizeof(unaligned));
778 				tmp = &unaligned;
779 			}
780 
781 		} else {
782 			tmp = (struct btrfs_disk_key *)(kaddr + offset -
783 							map_start);
784 		}
785 		ret = comp_keys(tmp, key);
786 
787 		if (ret < 0)
788 			low = mid + 1;
789 		else if (ret > 0)
790 			high = mid;
791 		else {
792 			*slot = mid;
793 			if (map_token)
794 				unmap_extent_buffer(eb, map_token, KM_USER0);
795 			return 0;
796 		}
797 	}
798 	*slot = low;
799 	if (map_token)
800 		unmap_extent_buffer(eb, map_token, KM_USER0);
801 	return 1;
802 }
803 
804 /*
805  * simple bin_search frontend that does the right thing for
806  * leaves vs nodes
807  */
808 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
809 		      int level, int *slot)
810 {
811 	if (level == 0) {
812 		return generic_bin_search(eb,
813 					  offsetof(struct btrfs_leaf, items),
814 					  sizeof(struct btrfs_item),
815 					  key, btrfs_header_nritems(eb),
816 					  slot);
817 	} else {
818 		return generic_bin_search(eb,
819 					  offsetof(struct btrfs_node, ptrs),
820 					  sizeof(struct btrfs_key_ptr),
821 					  key, btrfs_header_nritems(eb),
822 					  slot);
823 	}
824 	return -1;
825 }
826 
827 int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
828 		     int level, int *slot)
829 {
830 	return bin_search(eb, key, level, slot);
831 }
832 
833 static void root_add_used(struct btrfs_root *root, u32 size)
834 {
835 	spin_lock(&root->accounting_lock);
836 	btrfs_set_root_used(&root->root_item,
837 			    btrfs_root_used(&root->root_item) + size);
838 	spin_unlock(&root->accounting_lock);
839 }
840 
841 static void root_sub_used(struct btrfs_root *root, u32 size)
842 {
843 	spin_lock(&root->accounting_lock);
844 	btrfs_set_root_used(&root->root_item,
845 			    btrfs_root_used(&root->root_item) - size);
846 	spin_unlock(&root->accounting_lock);
847 }
848 
849 /* given a node and slot number, this reads the blocks it points to.  The
850  * extent buffer is returned with a reference taken (but unlocked).
851  * NULL is returned on error.
852  */
853 static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
854 				   struct extent_buffer *parent, int slot)
855 {
856 	int level = btrfs_header_level(parent);
857 	if (slot < 0)
858 		return NULL;
859 	if (slot >= btrfs_header_nritems(parent))
860 		return NULL;
861 
862 	BUG_ON(level == 0);
863 
864 	return read_tree_block(root, btrfs_node_blockptr(parent, slot),
865 		       btrfs_level_size(root, level - 1),
866 		       btrfs_node_ptr_generation(parent, slot));
867 }
868 
869 /*
870  * node level balancing, used to make sure nodes are in proper order for
871  * item deletion.  We balance from the top down, so we have to make sure
872  * that a deletion won't leave an node completely empty later on.
873  */
874 static noinline int balance_level(struct btrfs_trans_handle *trans,
875 			 struct btrfs_root *root,
876 			 struct btrfs_path *path, int level)
877 {
878 	struct extent_buffer *right = NULL;
879 	struct extent_buffer *mid;
880 	struct extent_buffer *left = NULL;
881 	struct extent_buffer *parent = NULL;
882 	int ret = 0;
883 	int wret;
884 	int pslot;
885 	int orig_slot = path->slots[level];
886 	u64 orig_ptr;
887 
888 	if (level == 0)
889 		return 0;
890 
891 	mid = path->nodes[level];
892 
893 	WARN_ON(!path->locks[level]);
894 	WARN_ON(btrfs_header_generation(mid) != trans->transid);
895 
896 	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
897 
898 	if (level < BTRFS_MAX_LEVEL - 1)
899 		parent = path->nodes[level + 1];
900 	pslot = path->slots[level + 1];
901 
902 	/*
903 	 * deal with the case where there is only one pointer in the root
904 	 * by promoting the node below to a root
905 	 */
906 	if (!parent) {
907 		struct extent_buffer *child;
908 
909 		if (btrfs_header_nritems(mid) != 1)
910 			return 0;
911 
912 		/* promote the child to a root */
913 		child = read_node_slot(root, mid, 0);
914 		BUG_ON(!child);
915 		btrfs_tree_lock(child);
916 		btrfs_set_lock_blocking(child);
917 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
918 		if (ret) {
919 			btrfs_tree_unlock(child);
920 			free_extent_buffer(child);
921 			goto enospc;
922 		}
923 
924 		rcu_assign_pointer(root->node, child);
925 
926 		add_root_to_dirty_list(root);
927 		btrfs_tree_unlock(child);
928 
929 		path->locks[level] = 0;
930 		path->nodes[level] = NULL;
931 		clean_tree_block(trans, root, mid);
932 		btrfs_tree_unlock(mid);
933 		/* once for the path */
934 		free_extent_buffer(mid);
935 
936 		root_sub_used(root, mid->len);
937 		btrfs_free_tree_block(trans, root, mid, 0, 1);
938 		/* once for the root ptr */
939 		free_extent_buffer(mid);
940 		return 0;
941 	}
942 	if (btrfs_header_nritems(mid) >
943 	    BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
944 		return 0;
945 
946 	btrfs_header_nritems(mid);
947 
948 	left = read_node_slot(root, parent, pslot - 1);
949 	if (left) {
950 		btrfs_tree_lock(left);
951 		btrfs_set_lock_blocking(left);
952 		wret = btrfs_cow_block(trans, root, left,
953 				       parent, pslot - 1, &left);
954 		if (wret) {
955 			ret = wret;
956 			goto enospc;
957 		}
958 	}
959 	right = read_node_slot(root, parent, pslot + 1);
960 	if (right) {
961 		btrfs_tree_lock(right);
962 		btrfs_set_lock_blocking(right);
963 		wret = btrfs_cow_block(trans, root, right,
964 				       parent, pslot + 1, &right);
965 		if (wret) {
966 			ret = wret;
967 			goto enospc;
968 		}
969 	}
970 
971 	/* first, try to make some room in the middle buffer */
972 	if (left) {
973 		orig_slot += btrfs_header_nritems(left);
974 		wret = push_node_left(trans, root, left, mid, 1);
975 		if (wret < 0)
976 			ret = wret;
977 		btrfs_header_nritems(mid);
978 	}
979 
980 	/*
981 	 * then try to empty the right most buffer into the middle
982 	 */
983 	if (right) {
984 		wret = push_node_left(trans, root, mid, right, 1);
985 		if (wret < 0 && wret != -ENOSPC)
986 			ret = wret;
987 		if (btrfs_header_nritems(right) == 0) {
988 			clean_tree_block(trans, root, right);
989 			btrfs_tree_unlock(right);
990 			wret = del_ptr(trans, root, path, level + 1, pslot +
991 				       1);
992 			if (wret)
993 				ret = wret;
994 			root_sub_used(root, right->len);
995 			btrfs_free_tree_block(trans, root, right, 0, 1);
996 			free_extent_buffer(right);
997 			right = NULL;
998 		} else {
999 			struct btrfs_disk_key right_key;
1000 			btrfs_node_key(right, &right_key, 0);
1001 			btrfs_set_node_key(parent, &right_key, pslot + 1);
1002 			btrfs_mark_buffer_dirty(parent);
1003 		}
1004 	}
1005 	if (btrfs_header_nritems(mid) == 1) {
1006 		/*
1007 		 * we're not allowed to leave a node with one item in the
1008 		 * tree during a delete.  A deletion from lower in the tree
1009 		 * could try to delete the only pointer in this node.
1010 		 * So, pull some keys from the left.
1011 		 * There has to be a left pointer at this point because
1012 		 * otherwise we would have pulled some pointers from the
1013 		 * right
1014 		 */
1015 		BUG_ON(!left);
1016 		wret = balance_node_right(trans, root, mid, left);
1017 		if (wret < 0) {
1018 			ret = wret;
1019 			goto enospc;
1020 		}
1021 		if (wret == 1) {
1022 			wret = push_node_left(trans, root, left, mid, 1);
1023 			if (wret < 0)
1024 				ret = wret;
1025 		}
1026 		BUG_ON(wret == 1);
1027 	}
1028 	if (btrfs_header_nritems(mid) == 0) {
1029 		clean_tree_block(trans, root, mid);
1030 		btrfs_tree_unlock(mid);
1031 		wret = del_ptr(trans, root, path, level + 1, pslot);
1032 		if (wret)
1033 			ret = wret;
1034 		root_sub_used(root, mid->len);
1035 		btrfs_free_tree_block(trans, root, mid, 0, 1);
1036 		free_extent_buffer(mid);
1037 		mid = NULL;
1038 	} else {
1039 		/* update the parent key to reflect our changes */
1040 		struct btrfs_disk_key mid_key;
1041 		btrfs_node_key(mid, &mid_key, 0);
1042 		btrfs_set_node_key(parent, &mid_key, pslot);
1043 		btrfs_mark_buffer_dirty(parent);
1044 	}
1045 
1046 	/* update the path */
1047 	if (left) {
1048 		if (btrfs_header_nritems(left) > orig_slot) {
1049 			extent_buffer_get(left);
1050 			/* left was locked after cow */
1051 			path->nodes[level] = left;
1052 			path->slots[level + 1] -= 1;
1053 			path->slots[level] = orig_slot;
1054 			if (mid) {
1055 				btrfs_tree_unlock(mid);
1056 				free_extent_buffer(mid);
1057 			}
1058 		} else {
1059 			orig_slot -= btrfs_header_nritems(left);
1060 			path->slots[level] = orig_slot;
1061 		}
1062 	}
1063 	/* double check we haven't messed things up */
1064 	if (orig_ptr !=
1065 	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1066 		BUG();
1067 enospc:
1068 	if (right) {
1069 		btrfs_tree_unlock(right);
1070 		free_extent_buffer(right);
1071 	}
1072 	if (left) {
1073 		if (path->nodes[level] != left)
1074 			btrfs_tree_unlock(left);
1075 		free_extent_buffer(left);
1076 	}
1077 	return ret;
1078 }
1079 
1080 /* Node balancing for insertion.  Here we only split or push nodes around
1081  * when they are completely full.  This is also done top down, so we
1082  * have to be pessimistic.
1083  */
1084 static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1085 					  struct btrfs_root *root,
1086 					  struct btrfs_path *path, int level)
1087 {
1088 	struct extent_buffer *right = NULL;
1089 	struct extent_buffer *mid;
1090 	struct extent_buffer *left = NULL;
1091 	struct extent_buffer *parent = NULL;
1092 	int ret = 0;
1093 	int wret;
1094 	int pslot;
1095 	int orig_slot = path->slots[level];
1096 
1097 	if (level == 0)
1098 		return 1;
1099 
1100 	mid = path->nodes[level];
1101 	WARN_ON(btrfs_header_generation(mid) != trans->transid);
1102 
1103 	if (level < BTRFS_MAX_LEVEL - 1)
1104 		parent = path->nodes[level + 1];
1105 	pslot = path->slots[level + 1];
1106 
1107 	if (!parent)
1108 		return 1;
1109 
1110 	left = read_node_slot(root, parent, pslot - 1);
1111 
1112 	/* first, try to make some room in the middle buffer */
1113 	if (left) {
1114 		u32 left_nr;
1115 
1116 		btrfs_tree_lock(left);
1117 		btrfs_set_lock_blocking(left);
1118 
1119 		left_nr = btrfs_header_nritems(left);
1120 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1121 			wret = 1;
1122 		} else {
1123 			ret = btrfs_cow_block(trans, root, left, parent,
1124 					      pslot - 1, &left);
1125 			if (ret)
1126 				wret = 1;
1127 			else {
1128 				wret = push_node_left(trans, root,
1129 						      left, mid, 0);
1130 			}
1131 		}
1132 		if (wret < 0)
1133 			ret = wret;
1134 		if (wret == 0) {
1135 			struct btrfs_disk_key disk_key;
1136 			orig_slot += left_nr;
1137 			btrfs_node_key(mid, &disk_key, 0);
1138 			btrfs_set_node_key(parent, &disk_key, pslot);
1139 			btrfs_mark_buffer_dirty(parent);
1140 			if (btrfs_header_nritems(left) > orig_slot) {
1141 				path->nodes[level] = left;
1142 				path->slots[level + 1] -= 1;
1143 				path->slots[level] = orig_slot;
1144 				btrfs_tree_unlock(mid);
1145 				free_extent_buffer(mid);
1146 			} else {
1147 				orig_slot -=
1148 					btrfs_header_nritems(left);
1149 				path->slots[level] = orig_slot;
1150 				btrfs_tree_unlock(left);
1151 				free_extent_buffer(left);
1152 			}
1153 			return 0;
1154 		}
1155 		btrfs_tree_unlock(left);
1156 		free_extent_buffer(left);
1157 	}
1158 	right = read_node_slot(root, parent, pslot + 1);
1159 
1160 	/*
1161 	 * then try to empty the right most buffer into the middle
1162 	 */
1163 	if (right) {
1164 		u32 right_nr;
1165 
1166 		btrfs_tree_lock(right);
1167 		btrfs_set_lock_blocking(right);
1168 
1169 		right_nr = btrfs_header_nritems(right);
1170 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1171 			wret = 1;
1172 		} else {
1173 			ret = btrfs_cow_block(trans, root, right,
1174 					      parent, pslot + 1,
1175 					      &right);
1176 			if (ret)
1177 				wret = 1;
1178 			else {
1179 				wret = balance_node_right(trans, root,
1180 							  right, mid);
1181 			}
1182 		}
1183 		if (wret < 0)
1184 			ret = wret;
1185 		if (wret == 0) {
1186 			struct btrfs_disk_key disk_key;
1187 
1188 			btrfs_node_key(right, &disk_key, 0);
1189 			btrfs_set_node_key(parent, &disk_key, pslot + 1);
1190 			btrfs_mark_buffer_dirty(parent);
1191 
1192 			if (btrfs_header_nritems(mid) <= orig_slot) {
1193 				path->nodes[level] = right;
1194 				path->slots[level + 1] += 1;
1195 				path->slots[level] = orig_slot -
1196 					btrfs_header_nritems(mid);
1197 				btrfs_tree_unlock(mid);
1198 				free_extent_buffer(mid);
1199 			} else {
1200 				btrfs_tree_unlock(right);
1201 				free_extent_buffer(right);
1202 			}
1203 			return 0;
1204 		}
1205 		btrfs_tree_unlock(right);
1206 		free_extent_buffer(right);
1207 	}
1208 	return 1;
1209 }
1210 
1211 /*
1212  * readahead one full node of leaves, finding things that are close
1213  * to the block in 'slot', and triggering ra on them.
1214  */
1215 static void reada_for_search(struct btrfs_root *root,
1216 			     struct btrfs_path *path,
1217 			     int level, int slot, u64 objectid)
1218 {
1219 	struct extent_buffer *node;
1220 	struct btrfs_disk_key disk_key;
1221 	u32 nritems;
1222 	u64 search;
1223 	u64 target;
1224 	u64 nread = 0;
1225 	u64 gen;
1226 	int direction = path->reada;
1227 	struct extent_buffer *eb;
1228 	u32 nr;
1229 	u32 blocksize;
1230 	u32 nscan = 0;
1231 	bool map = true;
1232 
1233 	if (level != 1)
1234 		return;
1235 
1236 	if (!path->nodes[level])
1237 		return;
1238 
1239 	node = path->nodes[level];
1240 
1241 	search = btrfs_node_blockptr(node, slot);
1242 	blocksize = btrfs_level_size(root, level - 1);
1243 	eb = btrfs_find_tree_block(root, search, blocksize);
1244 	if (eb) {
1245 		free_extent_buffer(eb);
1246 		return;
1247 	}
1248 
1249 	target = search;
1250 
1251 	nritems = btrfs_header_nritems(node);
1252 	nr = slot;
1253 	if (node->map_token || path->skip_locking)
1254 		map = false;
1255 
1256 	while (1) {
1257 		if (map && !node->map_token) {
1258 			unsigned long offset = btrfs_node_key_ptr_offset(nr);
1259 			map_private_extent_buffer(node, offset,
1260 						  sizeof(struct btrfs_key_ptr),
1261 						  &node->map_token,
1262 						  &node->kaddr,
1263 						  &node->map_start,
1264 						  &node->map_len, KM_USER1);
1265 		}
1266 		if (direction < 0) {
1267 			if (nr == 0)
1268 				break;
1269 			nr--;
1270 		} else if (direction > 0) {
1271 			nr++;
1272 			if (nr >= nritems)
1273 				break;
1274 		}
1275 		if (path->reada < 0 && objectid) {
1276 			btrfs_node_key(node, &disk_key, nr);
1277 			if (btrfs_disk_key_objectid(&disk_key) != objectid)
1278 				break;
1279 		}
1280 		search = btrfs_node_blockptr(node, nr);
1281 		if ((search <= target && target - search <= 65536) ||
1282 		    (search > target && search - target <= 65536)) {
1283 			gen = btrfs_node_ptr_generation(node, nr);
1284 			if (map && node->map_token) {
1285 				unmap_extent_buffer(node, node->map_token,
1286 						    KM_USER1);
1287 				node->map_token = NULL;
1288 			}
1289 			readahead_tree_block(root, search, blocksize, gen);
1290 			nread += blocksize;
1291 		}
1292 		nscan++;
1293 		if ((nread > 65536 || nscan > 32))
1294 			break;
1295 	}
1296 	if (map && node->map_token) {
1297 		unmap_extent_buffer(node, node->map_token, KM_USER1);
1298 		node->map_token = NULL;
1299 	}
1300 }
1301 
1302 /*
1303  * returns -EAGAIN if it had to drop the path, or zero if everything was in
1304  * cache
1305  */
1306 static noinline int reada_for_balance(struct btrfs_root *root,
1307 				      struct btrfs_path *path, int level)
1308 {
1309 	int slot;
1310 	int nritems;
1311 	struct extent_buffer *parent;
1312 	struct extent_buffer *eb;
1313 	u64 gen;
1314 	u64 block1 = 0;
1315 	u64 block2 = 0;
1316 	int ret = 0;
1317 	int blocksize;
1318 
1319 	parent = path->nodes[level + 1];
1320 	if (!parent)
1321 		return 0;
1322 
1323 	nritems = btrfs_header_nritems(parent);
1324 	slot = path->slots[level + 1];
1325 	blocksize = btrfs_level_size(root, level);
1326 
1327 	if (slot > 0) {
1328 		block1 = btrfs_node_blockptr(parent, slot - 1);
1329 		gen = btrfs_node_ptr_generation(parent, slot - 1);
1330 		eb = btrfs_find_tree_block(root, block1, blocksize);
1331 		if (eb && btrfs_buffer_uptodate(eb, gen))
1332 			block1 = 0;
1333 		free_extent_buffer(eb);
1334 	}
1335 	if (slot + 1 < nritems) {
1336 		block2 = btrfs_node_blockptr(parent, slot + 1);
1337 		gen = btrfs_node_ptr_generation(parent, slot + 1);
1338 		eb = btrfs_find_tree_block(root, block2, blocksize);
1339 		if (eb && btrfs_buffer_uptodate(eb, gen))
1340 			block2 = 0;
1341 		free_extent_buffer(eb);
1342 	}
1343 	if (block1 || block2) {
1344 		ret = -EAGAIN;
1345 
1346 		/* release the whole path */
1347 		btrfs_release_path(path);
1348 
1349 		/* read the blocks */
1350 		if (block1)
1351 			readahead_tree_block(root, block1, blocksize, 0);
1352 		if (block2)
1353 			readahead_tree_block(root, block2, blocksize, 0);
1354 
1355 		if (block1) {
1356 			eb = read_tree_block(root, block1, blocksize, 0);
1357 			free_extent_buffer(eb);
1358 		}
1359 		if (block2) {
1360 			eb = read_tree_block(root, block2, blocksize, 0);
1361 			free_extent_buffer(eb);
1362 		}
1363 	}
1364 	return ret;
1365 }
1366 
1367 
1368 /*
1369  * when we walk down the tree, it is usually safe to unlock the higher layers
1370  * in the tree.  The exceptions are when our path goes through slot 0, because
1371  * operations on the tree might require changing key pointers higher up in the
1372  * tree.
1373  *
1374  * callers might also have set path->keep_locks, which tells this code to keep
1375  * the lock if the path points to the last slot in the block.  This is part of
1376  * walking through the tree, and selecting the next slot in the higher block.
1377  *
1378  * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
1379  * if lowest_unlock is 1, level 0 won't be unlocked
1380  */
1381 static noinline void unlock_up(struct btrfs_path *path, int level,
1382 			       int lowest_unlock)
1383 {
1384 	int i;
1385 	int skip_level = level;
1386 	int no_skips = 0;
1387 	struct extent_buffer *t;
1388 
1389 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1390 		if (!path->nodes[i])
1391 			break;
1392 		if (!path->locks[i])
1393 			break;
1394 		if (!no_skips && path->slots[i] == 0) {
1395 			skip_level = i + 1;
1396 			continue;
1397 		}
1398 		if (!no_skips && path->keep_locks) {
1399 			u32 nritems;
1400 			t = path->nodes[i];
1401 			nritems = btrfs_header_nritems(t);
1402 			if (nritems < 1 || path->slots[i] >= nritems - 1) {
1403 				skip_level = i + 1;
1404 				continue;
1405 			}
1406 		}
1407 		if (skip_level < i && i >= lowest_unlock)
1408 			no_skips = 1;
1409 
1410 		t = path->nodes[i];
1411 		if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1412 			btrfs_tree_unlock(t);
1413 			path->locks[i] = 0;
1414 		}
1415 	}
1416 }
1417 
1418 /*
1419  * This releases any locks held in the path starting at level and
1420  * going all the way up to the root.
1421  *
1422  * btrfs_search_slot will keep the lock held on higher nodes in a few
1423  * corner cases, such as COW of the block at slot zero in the node.  This
1424  * ignores those rules, and it should only be called when there are no
1425  * more updates to be done higher up in the tree.
1426  */
1427 noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
1428 {
1429 	int i;
1430 
1431 	if (path->keep_locks)
1432 		return;
1433 
1434 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1435 		if (!path->nodes[i])
1436 			continue;
1437 		if (!path->locks[i])
1438 			continue;
1439 		btrfs_tree_unlock(path->nodes[i]);
1440 		path->locks[i] = 0;
1441 	}
1442 }
1443 
1444 /*
1445  * helper function for btrfs_search_slot.  The goal is to find a block
1446  * in cache without setting the path to blocking.  If we find the block
1447  * we return zero and the path is unchanged.
1448  *
1449  * If we can't find the block, we set the path blocking and do some
1450  * reada.  -EAGAIN is returned and the search must be repeated.
1451  */
1452 static int
1453 read_block_for_search(struct btrfs_trans_handle *trans,
1454 		       struct btrfs_root *root, struct btrfs_path *p,
1455 		       struct extent_buffer **eb_ret, int level, int slot,
1456 		       struct btrfs_key *key)
1457 {
1458 	u64 blocknr;
1459 	u64 gen;
1460 	u32 blocksize;
1461 	struct extent_buffer *b = *eb_ret;
1462 	struct extent_buffer *tmp;
1463 	int ret;
1464 
1465 	blocknr = btrfs_node_blockptr(b, slot);
1466 	gen = btrfs_node_ptr_generation(b, slot);
1467 	blocksize = btrfs_level_size(root, level - 1);
1468 
1469 	tmp = btrfs_find_tree_block(root, blocknr, blocksize);
1470 	if (tmp) {
1471 		if (btrfs_buffer_uptodate(tmp, 0)) {
1472 			if (btrfs_buffer_uptodate(tmp, gen)) {
1473 				/*
1474 				 * we found an up to date block without
1475 				 * sleeping, return
1476 				 * right away
1477 				 */
1478 				*eb_ret = tmp;
1479 				return 0;
1480 			}
1481 			/* the pages were up to date, but we failed
1482 			 * the generation number check.  Do a full
1483 			 * read for the generation number that is correct.
1484 			 * We must do this without dropping locks so
1485 			 * we can trust our generation number
1486 			 */
1487 			free_extent_buffer(tmp);
1488 			tmp = read_tree_block(root, blocknr, blocksize, gen);
1489 			if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1490 				*eb_ret = tmp;
1491 				return 0;
1492 			}
1493 			free_extent_buffer(tmp);
1494 			btrfs_release_path(p);
1495 			return -EIO;
1496 		}
1497 	}
1498 
1499 	/*
1500 	 * reduce lock contention at high levels
1501 	 * of the btree by dropping locks before
1502 	 * we read.  Don't release the lock on the current
1503 	 * level because we need to walk this node to figure
1504 	 * out which blocks to read.
1505 	 */
1506 	btrfs_unlock_up_safe(p, level + 1);
1507 	btrfs_set_path_blocking(p);
1508 
1509 	free_extent_buffer(tmp);
1510 	if (p->reada)
1511 		reada_for_search(root, p, level, slot, key->objectid);
1512 
1513 	btrfs_release_path(p);
1514 
1515 	ret = -EAGAIN;
1516 	tmp = read_tree_block(root, blocknr, blocksize, 0);
1517 	if (tmp) {
1518 		/*
1519 		 * If the read above didn't mark this buffer up to date,
1520 		 * it will never end up being up to date.  Set ret to EIO now
1521 		 * and give up so that our caller doesn't loop forever
1522 		 * on our EAGAINs.
1523 		 */
1524 		if (!btrfs_buffer_uptodate(tmp, 0))
1525 			ret = -EIO;
1526 		free_extent_buffer(tmp);
1527 	}
1528 	return ret;
1529 }
1530 
1531 /*
1532  * helper function for btrfs_search_slot.  This does all of the checks
1533  * for node-level blocks and does any balancing required based on
1534  * the ins_len.
1535  *
1536  * If no extra work was required, zero is returned.  If we had to
1537  * drop the path, -EAGAIN is returned and btrfs_search_slot must
1538  * start over
1539  */
1540 static int
1541 setup_nodes_for_search(struct btrfs_trans_handle *trans,
1542 		       struct btrfs_root *root, struct btrfs_path *p,
1543 		       struct extent_buffer *b, int level, int ins_len)
1544 {
1545 	int ret;
1546 	if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
1547 	    BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1548 		int sret;
1549 
1550 		sret = reada_for_balance(root, p, level);
1551 		if (sret)
1552 			goto again;
1553 
1554 		btrfs_set_path_blocking(p);
1555 		sret = split_node(trans, root, p, level);
1556 		btrfs_clear_path_blocking(p, NULL);
1557 
1558 		BUG_ON(sret > 0);
1559 		if (sret) {
1560 			ret = sret;
1561 			goto done;
1562 		}
1563 		b = p->nodes[level];
1564 	} else if (ins_len < 0 && btrfs_header_nritems(b) <
1565 		   BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
1566 		int sret;
1567 
1568 		sret = reada_for_balance(root, p, level);
1569 		if (sret)
1570 			goto again;
1571 
1572 		btrfs_set_path_blocking(p);
1573 		sret = balance_level(trans, root, p, level);
1574 		btrfs_clear_path_blocking(p, NULL);
1575 
1576 		if (sret) {
1577 			ret = sret;
1578 			goto done;
1579 		}
1580 		b = p->nodes[level];
1581 		if (!b) {
1582 			btrfs_release_path(p);
1583 			goto again;
1584 		}
1585 		BUG_ON(btrfs_header_nritems(b) == 1);
1586 	}
1587 	return 0;
1588 
1589 again:
1590 	ret = -EAGAIN;
1591 done:
1592 	return ret;
1593 }
1594 
1595 /*
1596  * look for key in the tree.  path is filled in with nodes along the way
1597  * if key is found, we return zero and you can find the item in the leaf
1598  * level of the path (level 0)
1599  *
1600  * If the key isn't found, the path points to the slot where it should
1601  * be inserted, and 1 is returned.  If there are other errors during the
1602  * search a negative error number is returned.
1603  *
1604  * if ins_len > 0, nodes and leaves will be split as we walk down the
1605  * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
1606  * possible)
1607  */
1608 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1609 		      *root, struct btrfs_key *key, struct btrfs_path *p, int
1610 		      ins_len, int cow)
1611 {
1612 	struct extent_buffer *b;
1613 	int slot;
1614 	int ret;
1615 	int err;
1616 	int level;
1617 	int lowest_unlock = 1;
1618 	u8 lowest_level = 0;
1619 
1620 	lowest_level = p->lowest_level;
1621 	WARN_ON(lowest_level && ins_len > 0);
1622 	WARN_ON(p->nodes[0] != NULL);
1623 
1624 	if (ins_len < 0)
1625 		lowest_unlock = 2;
1626 
1627 again:
1628 	if (p->search_commit_root) {
1629 		b = root->commit_root;
1630 		extent_buffer_get(b);
1631 		if (!p->skip_locking)
1632 			btrfs_tree_lock(b);
1633 	} else {
1634 		if (p->skip_locking)
1635 			b = btrfs_root_node(root);
1636 		else
1637 			b = btrfs_lock_root_node(root);
1638 	}
1639 
1640 	while (b) {
1641 		level = btrfs_header_level(b);
1642 
1643 		/*
1644 		 * setup the path here so we can release it under lock
1645 		 * contention with the cow code
1646 		 */
1647 		p->nodes[level] = b;
1648 		if (!p->skip_locking)
1649 			p->locks[level] = 1;
1650 
1651 		if (cow) {
1652 			/*
1653 			 * if we don't really need to cow this block
1654 			 * then we don't want to set the path blocking,
1655 			 * so we test it here
1656 			 */
1657 			if (!should_cow_block(trans, root, b))
1658 				goto cow_done;
1659 
1660 			btrfs_set_path_blocking(p);
1661 
1662 			err = btrfs_cow_block(trans, root, b,
1663 					      p->nodes[level + 1],
1664 					      p->slots[level + 1], &b);
1665 			if (err) {
1666 				ret = err;
1667 				goto done;
1668 			}
1669 		}
1670 cow_done:
1671 		BUG_ON(!cow && ins_len);
1672 
1673 		p->nodes[level] = b;
1674 		if (!p->skip_locking)
1675 			p->locks[level] = 1;
1676 
1677 		btrfs_clear_path_blocking(p, NULL);
1678 
1679 		/*
1680 		 * we have a lock on b and as long as we aren't changing
1681 		 * the tree, there is no way to for the items in b to change.
1682 		 * It is safe to drop the lock on our parent before we
1683 		 * go through the expensive btree search on b.
1684 		 *
1685 		 * If cow is true, then we might be changing slot zero,
1686 		 * which may require changing the parent.  So, we can't
1687 		 * drop the lock until after we know which slot we're
1688 		 * operating on.
1689 		 */
1690 		if (!cow)
1691 			btrfs_unlock_up_safe(p, level + 1);
1692 
1693 		ret = bin_search(b, key, level, &slot);
1694 
1695 		if (level != 0) {
1696 			int dec = 0;
1697 			if (ret && slot > 0) {
1698 				dec = 1;
1699 				slot -= 1;
1700 			}
1701 			p->slots[level] = slot;
1702 			err = setup_nodes_for_search(trans, root, p, b, level,
1703 						     ins_len);
1704 			if (err == -EAGAIN)
1705 				goto again;
1706 			if (err) {
1707 				ret = err;
1708 				goto done;
1709 			}
1710 			b = p->nodes[level];
1711 			slot = p->slots[level];
1712 
1713 			unlock_up(p, level, lowest_unlock);
1714 
1715 			if (level == lowest_level) {
1716 				if (dec)
1717 					p->slots[level]++;
1718 				goto done;
1719 			}
1720 
1721 			err = read_block_for_search(trans, root, p,
1722 						    &b, level, slot, key);
1723 			if (err == -EAGAIN)
1724 				goto again;
1725 			if (err) {
1726 				ret = err;
1727 				goto done;
1728 			}
1729 
1730 			if (!p->skip_locking) {
1731 				btrfs_clear_path_blocking(p, NULL);
1732 				err = btrfs_try_spin_lock(b);
1733 
1734 				if (!err) {
1735 					btrfs_set_path_blocking(p);
1736 					btrfs_tree_lock(b);
1737 					btrfs_clear_path_blocking(p, b);
1738 				}
1739 			}
1740 		} else {
1741 			p->slots[level] = slot;
1742 			if (ins_len > 0 &&
1743 			    btrfs_leaf_free_space(root, b) < ins_len) {
1744 				btrfs_set_path_blocking(p);
1745 				err = split_leaf(trans, root, key,
1746 						 p, ins_len, ret == 0);
1747 				btrfs_clear_path_blocking(p, NULL);
1748 
1749 				BUG_ON(err > 0);
1750 				if (err) {
1751 					ret = err;
1752 					goto done;
1753 				}
1754 			}
1755 			if (!p->search_for_split)
1756 				unlock_up(p, level, lowest_unlock);
1757 			goto done;
1758 		}
1759 	}
1760 	ret = 1;
1761 done:
1762 	/*
1763 	 * we don't really know what they plan on doing with the path
1764 	 * from here on, so for now just mark it as blocking
1765 	 */
1766 	if (!p->leave_spinning)
1767 		btrfs_set_path_blocking(p);
1768 	if (ret < 0)
1769 		btrfs_release_path(p);
1770 	return ret;
1771 }
1772 
1773 /*
1774  * adjust the pointers going up the tree, starting at level
1775  * making sure the right key of each node is points to 'key'.
1776  * This is used after shifting pointers to the left, so it stops
1777  * fixing up pointers when a given leaf/node is not in slot 0 of the
1778  * higher levels
1779  *
1780  * If this fails to write a tree block, it returns -1, but continues
1781  * fixing up the blocks in ram so the tree is consistent.
1782  */
1783 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1784 			  struct btrfs_root *root, struct btrfs_path *path,
1785 			  struct btrfs_disk_key *key, int level)
1786 {
1787 	int i;
1788 	int ret = 0;
1789 	struct extent_buffer *t;
1790 
1791 	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1792 		int tslot = path->slots[i];
1793 		if (!path->nodes[i])
1794 			break;
1795 		t = path->nodes[i];
1796 		btrfs_set_node_key(t, key, tslot);
1797 		btrfs_mark_buffer_dirty(path->nodes[i]);
1798 		if (tslot != 0)
1799 			break;
1800 	}
1801 	return ret;
1802 }
1803 
1804 /*
1805  * update item key.
1806  *
1807  * This function isn't completely safe. It's the caller's responsibility
1808  * that the new key won't break the order
1809  */
1810 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1811 			    struct btrfs_root *root, struct btrfs_path *path,
1812 			    struct btrfs_key *new_key)
1813 {
1814 	struct btrfs_disk_key disk_key;
1815 	struct extent_buffer *eb;
1816 	int slot;
1817 
1818 	eb = path->nodes[0];
1819 	slot = path->slots[0];
1820 	if (slot > 0) {
1821 		btrfs_item_key(eb, &disk_key, slot - 1);
1822 		if (comp_keys(&disk_key, new_key) >= 0)
1823 			return -1;
1824 	}
1825 	if (slot < btrfs_header_nritems(eb) - 1) {
1826 		btrfs_item_key(eb, &disk_key, slot + 1);
1827 		if (comp_keys(&disk_key, new_key) <= 0)
1828 			return -1;
1829 	}
1830 
1831 	btrfs_cpu_key_to_disk(&disk_key, new_key);
1832 	btrfs_set_item_key(eb, &disk_key, slot);
1833 	btrfs_mark_buffer_dirty(eb);
1834 	if (slot == 0)
1835 		fixup_low_keys(trans, root, path, &disk_key, 1);
1836 	return 0;
1837 }
1838 
1839 /*
1840  * try to push data from one node into the next node left in the
1841  * tree.
1842  *
1843  * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1844  * error, and > 0 if there was no room in the left hand block.
1845  */
1846 static int push_node_left(struct btrfs_trans_handle *trans,
1847 			  struct btrfs_root *root, struct extent_buffer *dst,
1848 			  struct extent_buffer *src, int empty)
1849 {
1850 	int push_items = 0;
1851 	int src_nritems;
1852 	int dst_nritems;
1853 	int ret = 0;
1854 
1855 	src_nritems = btrfs_header_nritems(src);
1856 	dst_nritems = btrfs_header_nritems(dst);
1857 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1858 	WARN_ON(btrfs_header_generation(src) != trans->transid);
1859 	WARN_ON(btrfs_header_generation(dst) != trans->transid);
1860 
1861 	if (!empty && src_nritems <= 8)
1862 		return 1;
1863 
1864 	if (push_items <= 0)
1865 		return 1;
1866 
1867 	if (empty) {
1868 		push_items = min(src_nritems, push_items);
1869 		if (push_items < src_nritems) {
1870 			/* leave at least 8 pointers in the node if
1871 			 * we aren't going to empty it
1872 			 */
1873 			if (src_nritems - push_items < 8) {
1874 				if (push_items <= 8)
1875 					return 1;
1876 				push_items -= 8;
1877 			}
1878 		}
1879 	} else
1880 		push_items = min(src_nritems - 8, push_items);
1881 
1882 	copy_extent_buffer(dst, src,
1883 			   btrfs_node_key_ptr_offset(dst_nritems),
1884 			   btrfs_node_key_ptr_offset(0),
1885 			   push_items * sizeof(struct btrfs_key_ptr));
1886 
1887 	if (push_items < src_nritems) {
1888 		memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1889 				      btrfs_node_key_ptr_offset(push_items),
1890 				      (src_nritems - push_items) *
1891 				      sizeof(struct btrfs_key_ptr));
1892 	}
1893 	btrfs_set_header_nritems(src, src_nritems - push_items);
1894 	btrfs_set_header_nritems(dst, dst_nritems + push_items);
1895 	btrfs_mark_buffer_dirty(src);
1896 	btrfs_mark_buffer_dirty(dst);
1897 
1898 	return ret;
1899 }
1900 
1901 /*
1902  * try to push data from one node into the next node right in the
1903  * tree.
1904  *
1905  * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1906  * error, and > 0 if there was no room in the right hand block.
1907  *
1908  * this will  only push up to 1/2 the contents of the left node over
1909  */
1910 static int balance_node_right(struct btrfs_trans_handle *trans,
1911 			      struct btrfs_root *root,
1912 			      struct extent_buffer *dst,
1913 			      struct extent_buffer *src)
1914 {
1915 	int push_items = 0;
1916 	int max_push;
1917 	int src_nritems;
1918 	int dst_nritems;
1919 	int ret = 0;
1920 
1921 	WARN_ON(btrfs_header_generation(src) != trans->transid);
1922 	WARN_ON(btrfs_header_generation(dst) != trans->transid);
1923 
1924 	src_nritems = btrfs_header_nritems(src);
1925 	dst_nritems = btrfs_header_nritems(dst);
1926 	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1927 	if (push_items <= 0)
1928 		return 1;
1929 
1930 	if (src_nritems < 4)
1931 		return 1;
1932 
1933 	max_push = src_nritems / 2 + 1;
1934 	/* don't try to empty the node */
1935 	if (max_push >= src_nritems)
1936 		return 1;
1937 
1938 	if (max_push < push_items)
1939 		push_items = max_push;
1940 
1941 	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1942 				      btrfs_node_key_ptr_offset(0),
1943 				      (dst_nritems) *
1944 				      sizeof(struct btrfs_key_ptr));
1945 
1946 	copy_extent_buffer(dst, src,
1947 			   btrfs_node_key_ptr_offset(0),
1948 			   btrfs_node_key_ptr_offset(src_nritems - push_items),
1949 			   push_items * sizeof(struct btrfs_key_ptr));
1950 
1951 	btrfs_set_header_nritems(src, src_nritems - push_items);
1952 	btrfs_set_header_nritems(dst, dst_nritems + push_items);
1953 
1954 	btrfs_mark_buffer_dirty(src);
1955 	btrfs_mark_buffer_dirty(dst);
1956 
1957 	return ret;
1958 }
1959 
1960 /*
1961  * helper function to insert a new root level in the tree.
1962  * A new node is allocated, and a single item is inserted to
1963  * point to the existing root
1964  *
1965  * returns zero on success or < 0 on failure.
1966  */
1967 static noinline int insert_new_root(struct btrfs_trans_handle *trans,
1968 			   struct btrfs_root *root,
1969 			   struct btrfs_path *path, int level)
1970 {
1971 	u64 lower_gen;
1972 	struct extent_buffer *lower;
1973 	struct extent_buffer *c;
1974 	struct extent_buffer *old;
1975 	struct btrfs_disk_key lower_key;
1976 
1977 	BUG_ON(path->nodes[level]);
1978 	BUG_ON(path->nodes[level-1] != root->node);
1979 
1980 	lower = path->nodes[level-1];
1981 	if (level == 1)
1982 		btrfs_item_key(lower, &lower_key, 0);
1983 	else
1984 		btrfs_node_key(lower, &lower_key, 0);
1985 
1986 	c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
1987 				   root->root_key.objectid, &lower_key,
1988 				   level, root->node->start, 0);
1989 	if (IS_ERR(c))
1990 		return PTR_ERR(c);
1991 
1992 	root_add_used(root, root->nodesize);
1993 
1994 	memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
1995 	btrfs_set_header_nritems(c, 1);
1996 	btrfs_set_header_level(c, level);
1997 	btrfs_set_header_bytenr(c, c->start);
1998 	btrfs_set_header_generation(c, trans->transid);
1999 	btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
2000 	btrfs_set_header_owner(c, root->root_key.objectid);
2001 
2002 	write_extent_buffer(c, root->fs_info->fsid,
2003 			    (unsigned long)btrfs_header_fsid(c),
2004 			    BTRFS_FSID_SIZE);
2005 
2006 	write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
2007 			    (unsigned long)btrfs_header_chunk_tree_uuid(c),
2008 			    BTRFS_UUID_SIZE);
2009 
2010 	btrfs_set_node_key(c, &lower_key, 0);
2011 	btrfs_set_node_blockptr(c, 0, lower->start);
2012 	lower_gen = btrfs_header_generation(lower);
2013 	WARN_ON(lower_gen != trans->transid);
2014 
2015 	btrfs_set_node_ptr_generation(c, 0, lower_gen);
2016 
2017 	btrfs_mark_buffer_dirty(c);
2018 
2019 	old = root->node;
2020 	rcu_assign_pointer(root->node, c);
2021 
2022 	/* the super has an extra ref to root->node */
2023 	free_extent_buffer(old);
2024 
2025 	add_root_to_dirty_list(root);
2026 	extent_buffer_get(c);
2027 	path->nodes[level] = c;
2028 	path->locks[level] = 1;
2029 	path->slots[level] = 0;
2030 	return 0;
2031 }
2032 
2033 /*
2034  * worker function to insert a single pointer in a node.
2035  * the node should have enough room for the pointer already
2036  *
2037  * slot and level indicate where you want the key to go, and
2038  * blocknr is the block the key points to.
2039  *
2040  * returns zero on success and < 0 on any error
2041  */
2042 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
2043 		      *root, struct btrfs_path *path, struct btrfs_disk_key
2044 		      *key, u64 bytenr, int slot, int level)
2045 {
2046 	struct extent_buffer *lower;
2047 	int nritems;
2048 
2049 	BUG_ON(!path->nodes[level]);
2050 	btrfs_assert_tree_locked(path->nodes[level]);
2051 	lower = path->nodes[level];
2052 	nritems = btrfs_header_nritems(lower);
2053 	BUG_ON(slot > nritems);
2054 	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
2055 		BUG();
2056 	if (slot != nritems) {
2057 		memmove_extent_buffer(lower,
2058 			      btrfs_node_key_ptr_offset(slot + 1),
2059 			      btrfs_node_key_ptr_offset(slot),
2060 			      (nritems - slot) * sizeof(struct btrfs_key_ptr));
2061 	}
2062 	btrfs_set_node_key(lower, key, slot);
2063 	btrfs_set_node_blockptr(lower, slot, bytenr);
2064 	WARN_ON(trans->transid == 0);
2065 	btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2066 	btrfs_set_header_nritems(lower, nritems + 1);
2067 	btrfs_mark_buffer_dirty(lower);
2068 	return 0;
2069 }
2070 
2071 /*
2072  * split the node at the specified level in path in two.
2073  * The path is corrected to point to the appropriate node after the split
2074  *
2075  * Before splitting this tries to make some room in the node by pushing
2076  * left and right, if either one works, it returns right away.
2077  *
2078  * returns 0 on success and < 0 on failure
2079  */
2080 static noinline int split_node(struct btrfs_trans_handle *trans,
2081 			       struct btrfs_root *root,
2082 			       struct btrfs_path *path, int level)
2083 {
2084 	struct extent_buffer *c;
2085 	struct extent_buffer *split;
2086 	struct btrfs_disk_key disk_key;
2087 	int mid;
2088 	int ret;
2089 	int wret;
2090 	u32 c_nritems;
2091 
2092 	c = path->nodes[level];
2093 	WARN_ON(btrfs_header_generation(c) != trans->transid);
2094 	if (c == root->node) {
2095 		/* trying to split the root, lets make a new one */
2096 		ret = insert_new_root(trans, root, path, level + 1);
2097 		if (ret)
2098 			return ret;
2099 	} else {
2100 		ret = push_nodes_for_insert(trans, root, path, level);
2101 		c = path->nodes[level];
2102 		if (!ret && btrfs_header_nritems(c) <
2103 		    BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
2104 			return 0;
2105 		if (ret < 0)
2106 			return ret;
2107 	}
2108 
2109 	c_nritems = btrfs_header_nritems(c);
2110 	mid = (c_nritems + 1) / 2;
2111 	btrfs_node_key(c, &disk_key, mid);
2112 
2113 	split = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
2114 					root->root_key.objectid,
2115 					&disk_key, level, c->start, 0);
2116 	if (IS_ERR(split))
2117 		return PTR_ERR(split);
2118 
2119 	root_add_used(root, root->nodesize);
2120 
2121 	memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
2122 	btrfs_set_header_level(split, btrfs_header_level(c));
2123 	btrfs_set_header_bytenr(split, split->start);
2124 	btrfs_set_header_generation(split, trans->transid);
2125 	btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
2126 	btrfs_set_header_owner(split, root->root_key.objectid);
2127 	write_extent_buffer(split, root->fs_info->fsid,
2128 			    (unsigned long)btrfs_header_fsid(split),
2129 			    BTRFS_FSID_SIZE);
2130 	write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
2131 			    (unsigned long)btrfs_header_chunk_tree_uuid(split),
2132 			    BTRFS_UUID_SIZE);
2133 
2134 
2135 	copy_extent_buffer(split, c,
2136 			   btrfs_node_key_ptr_offset(0),
2137 			   btrfs_node_key_ptr_offset(mid),
2138 			   (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
2139 	btrfs_set_header_nritems(split, c_nritems - mid);
2140 	btrfs_set_header_nritems(c, mid);
2141 	ret = 0;
2142 
2143 	btrfs_mark_buffer_dirty(c);
2144 	btrfs_mark_buffer_dirty(split);
2145 
2146 	wret = insert_ptr(trans, root, path, &disk_key, split->start,
2147 			  path->slots[level + 1] + 1,
2148 			  level + 1);
2149 	if (wret)
2150 		ret = wret;
2151 
2152 	if (path->slots[level] >= mid) {
2153 		path->slots[level] -= mid;
2154 		btrfs_tree_unlock(c);
2155 		free_extent_buffer(c);
2156 		path->nodes[level] = split;
2157 		path->slots[level + 1] += 1;
2158 	} else {
2159 		btrfs_tree_unlock(split);
2160 		free_extent_buffer(split);
2161 	}
2162 	return ret;
2163 }
2164 
2165 /*
2166  * how many bytes are required to store the items in a leaf.  start
2167  * and nr indicate which items in the leaf to check.  This totals up the
2168  * space used both by the item structs and the item data
2169  */
2170 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2171 {
2172 	int data_len;
2173 	int nritems = btrfs_header_nritems(l);
2174 	int end = min(nritems, start + nr) - 1;
2175 
2176 	if (!nr)
2177 		return 0;
2178 	data_len = btrfs_item_end_nr(l, start);
2179 	data_len = data_len - btrfs_item_offset_nr(l, end);
2180 	data_len += sizeof(struct btrfs_item) * nr;
2181 	WARN_ON(data_len < 0);
2182 	return data_len;
2183 }
2184 
2185 /*
2186  * The space between the end of the leaf items and
2187  * the start of the leaf data.  IOW, how much room
2188  * the leaf has left for both items and data
2189  */
2190 noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2191 				   struct extent_buffer *leaf)
2192 {
2193 	int nritems = btrfs_header_nritems(leaf);
2194 	int ret;
2195 	ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
2196 	if (ret < 0) {
2197 		printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
2198 		       "used %d nritems %d\n",
2199 		       ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
2200 		       leaf_space_used(leaf, 0, nritems), nritems);
2201 	}
2202 	return ret;
2203 }
2204 
2205 /*
2206  * min slot controls the lowest index we're willing to push to the
2207  * right.  We'll push up to and including min_slot, but no lower
2208  */
2209 static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
2210 				      struct btrfs_root *root,
2211 				      struct btrfs_path *path,
2212 				      int data_size, int empty,
2213 				      struct extent_buffer *right,
2214 				      int free_space, u32 left_nritems,
2215 				      u32 min_slot)
2216 {
2217 	struct extent_buffer *left = path->nodes[0];
2218 	struct extent_buffer *upper = path->nodes[1];
2219 	struct btrfs_disk_key disk_key;
2220 	int slot;
2221 	u32 i;
2222 	int push_space = 0;
2223 	int push_items = 0;
2224 	struct btrfs_item *item;
2225 	u32 nr;
2226 	u32 right_nritems;
2227 	u32 data_end;
2228 	u32 this_item_size;
2229 
2230 	if (empty)
2231 		nr = 0;
2232 	else
2233 		nr = max_t(u32, 1, min_slot);
2234 
2235 	if (path->slots[0] >= left_nritems)
2236 		push_space += data_size;
2237 
2238 	slot = path->slots[1];
2239 	i = left_nritems - 1;
2240 	while (i >= nr) {
2241 		item = btrfs_item_nr(left, i);
2242 
2243 		if (!empty && push_items > 0) {
2244 			if (path->slots[0] > i)
2245 				break;
2246 			if (path->slots[0] == i) {
2247 				int space = btrfs_leaf_free_space(root, left);
2248 				if (space + push_space * 2 > free_space)
2249 					break;
2250 			}
2251 		}
2252 
2253 		if (path->slots[0] == i)
2254 			push_space += data_size;
2255 
2256 		if (!left->map_token) {
2257 			map_extent_buffer(left, (unsigned long)item,
2258 					sizeof(struct btrfs_item),
2259 					&left->map_token, &left->kaddr,
2260 					&left->map_start, &left->map_len,
2261 					KM_USER1);
2262 		}
2263 
2264 		this_item_size = btrfs_item_size(left, item);
2265 		if (this_item_size + sizeof(*item) + push_space > free_space)
2266 			break;
2267 
2268 		push_items++;
2269 		push_space += this_item_size + sizeof(*item);
2270 		if (i == 0)
2271 			break;
2272 		i--;
2273 	}
2274 	if (left->map_token) {
2275 		unmap_extent_buffer(left, left->map_token, KM_USER1);
2276 		left->map_token = NULL;
2277 	}
2278 
2279 	if (push_items == 0)
2280 		goto out_unlock;
2281 
2282 	if (!empty && push_items == left_nritems)
2283 		WARN_ON(1);
2284 
2285 	/* push left to right */
2286 	right_nritems = btrfs_header_nritems(right);
2287 
2288 	push_space = btrfs_item_end_nr(left, left_nritems - push_items);
2289 	push_space -= leaf_data_end(root, left);
2290 
2291 	/* make room in the right data area */
2292 	data_end = leaf_data_end(root, right);
2293 	memmove_extent_buffer(right,
2294 			      btrfs_leaf_data(right) + data_end - push_space,
2295 			      btrfs_leaf_data(right) + data_end,
2296 			      BTRFS_LEAF_DATA_SIZE(root) - data_end);
2297 
2298 	/* copy from the left data area */
2299 	copy_extent_buffer(right, left, btrfs_leaf_data(right) +
2300 		     BTRFS_LEAF_DATA_SIZE(root) - push_space,
2301 		     btrfs_leaf_data(left) + leaf_data_end(root, left),
2302 		     push_space);
2303 
2304 	memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
2305 			      btrfs_item_nr_offset(0),
2306 			      right_nritems * sizeof(struct btrfs_item));
2307 
2308 	/* copy the items from left to right */
2309 	copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
2310 		   btrfs_item_nr_offset(left_nritems - push_items),
2311 		   push_items * sizeof(struct btrfs_item));
2312 
2313 	/* update the item pointers */
2314 	right_nritems += push_items;
2315 	btrfs_set_header_nritems(right, right_nritems);
2316 	push_space = BTRFS_LEAF_DATA_SIZE(root);
2317 	for (i = 0; i < right_nritems; i++) {
2318 		item = btrfs_item_nr(right, i);
2319 		if (!right->map_token) {
2320 			map_extent_buffer(right, (unsigned long)item,
2321 					sizeof(struct btrfs_item),
2322 					&right->map_token, &right->kaddr,
2323 					&right->map_start, &right->map_len,
2324 					KM_USER1);
2325 		}
2326 		push_space -= btrfs_item_size(right, item);
2327 		btrfs_set_item_offset(right, item, push_space);
2328 	}
2329 
2330 	if (right->map_token) {
2331 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2332 		right->map_token = NULL;
2333 	}
2334 	left_nritems -= push_items;
2335 	btrfs_set_header_nritems(left, left_nritems);
2336 
2337 	if (left_nritems)
2338 		btrfs_mark_buffer_dirty(left);
2339 	else
2340 		clean_tree_block(trans, root, left);
2341 
2342 	btrfs_mark_buffer_dirty(right);
2343 
2344 	btrfs_item_key(right, &disk_key, 0);
2345 	btrfs_set_node_key(upper, &disk_key, slot + 1);
2346 	btrfs_mark_buffer_dirty(upper);
2347 
2348 	/* then fixup the leaf pointer in the path */
2349 	if (path->slots[0] >= left_nritems) {
2350 		path->slots[0] -= left_nritems;
2351 		if (btrfs_header_nritems(path->nodes[0]) == 0)
2352 			clean_tree_block(trans, root, path->nodes[0]);
2353 		btrfs_tree_unlock(path->nodes[0]);
2354 		free_extent_buffer(path->nodes[0]);
2355 		path->nodes[0] = right;
2356 		path->slots[1] += 1;
2357 	} else {
2358 		btrfs_tree_unlock(right);
2359 		free_extent_buffer(right);
2360 	}
2361 	return 0;
2362 
2363 out_unlock:
2364 	btrfs_tree_unlock(right);
2365 	free_extent_buffer(right);
2366 	return 1;
2367 }
2368 
2369 /*
2370  * push some data in the path leaf to the right, trying to free up at
2371  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
2372  *
2373  * returns 1 if the push failed because the other node didn't have enough
2374  * room, 0 if everything worked out and < 0 if there were major errors.
2375  *
2376  * this will push starting from min_slot to the end of the leaf.  It won't
2377  * push any slot lower than min_slot
2378  */
2379 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
2380 			   *root, struct btrfs_path *path,
2381 			   int min_data_size, int data_size,
2382 			   int empty, u32 min_slot)
2383 {
2384 	struct extent_buffer *left = path->nodes[0];
2385 	struct extent_buffer *right;
2386 	struct extent_buffer *upper;
2387 	int slot;
2388 	int free_space;
2389 	u32 left_nritems;
2390 	int ret;
2391 
2392 	if (!path->nodes[1])
2393 		return 1;
2394 
2395 	slot = path->slots[1];
2396 	upper = path->nodes[1];
2397 	if (slot >= btrfs_header_nritems(upper) - 1)
2398 		return 1;
2399 
2400 	btrfs_assert_tree_locked(path->nodes[1]);
2401 
2402 	right = read_node_slot(root, upper, slot + 1);
2403 	if (right == NULL)
2404 		return 1;
2405 
2406 	btrfs_tree_lock(right);
2407 	btrfs_set_lock_blocking(right);
2408 
2409 	free_space = btrfs_leaf_free_space(root, right);
2410 	if (free_space < data_size)
2411 		goto out_unlock;
2412 
2413 	/* cow and double check */
2414 	ret = btrfs_cow_block(trans, root, right, upper,
2415 			      slot + 1, &right);
2416 	if (ret)
2417 		goto out_unlock;
2418 
2419 	free_space = btrfs_leaf_free_space(root, right);
2420 	if (free_space < data_size)
2421 		goto out_unlock;
2422 
2423 	left_nritems = btrfs_header_nritems(left);
2424 	if (left_nritems == 0)
2425 		goto out_unlock;
2426 
2427 	return __push_leaf_right(trans, root, path, min_data_size, empty,
2428 				right, free_space, left_nritems, min_slot);
2429 out_unlock:
2430 	btrfs_tree_unlock(right);
2431 	free_extent_buffer(right);
2432 	return 1;
2433 }
2434 
2435 /*
2436  * push some data in the path leaf to the left, trying to free up at
2437  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
2438  *
2439  * max_slot can put a limit on how far into the leaf we'll push items.  The
2440  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us do all the
2441  * items
2442  */
2443 static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
2444 				     struct btrfs_root *root,
2445 				     struct btrfs_path *path, int data_size,
2446 				     int empty, struct extent_buffer *left,
2447 				     int free_space, u32 right_nritems,
2448 				     u32 max_slot)
2449 {
2450 	struct btrfs_disk_key disk_key;
2451 	struct extent_buffer *right = path->nodes[0];
2452 	int i;
2453 	int push_space = 0;
2454 	int push_items = 0;
2455 	struct btrfs_item *item;
2456 	u32 old_left_nritems;
2457 	u32 nr;
2458 	int ret = 0;
2459 	int wret;
2460 	u32 this_item_size;
2461 	u32 old_left_item_size;
2462 
2463 	if (empty)
2464 		nr = min(right_nritems, max_slot);
2465 	else
2466 		nr = min(right_nritems - 1, max_slot);
2467 
2468 	for (i = 0; i < nr; i++) {
2469 		item = btrfs_item_nr(right, i);
2470 		if (!right->map_token) {
2471 			map_extent_buffer(right, (unsigned long)item,
2472 					sizeof(struct btrfs_item),
2473 					&right->map_token, &right->kaddr,
2474 					&right->map_start, &right->map_len,
2475 					KM_USER1);
2476 		}
2477 
2478 		if (!empty && push_items > 0) {
2479 			if (path->slots[0] < i)
2480 				break;
2481 			if (path->slots[0] == i) {
2482 				int space = btrfs_leaf_free_space(root, right);
2483 				if (space + push_space * 2 > free_space)
2484 					break;
2485 			}
2486 		}
2487 
2488 		if (path->slots[0] == i)
2489 			push_space += data_size;
2490 
2491 		this_item_size = btrfs_item_size(right, item);
2492 		if (this_item_size + sizeof(*item) + push_space > free_space)
2493 			break;
2494 
2495 		push_items++;
2496 		push_space += this_item_size + sizeof(*item);
2497 	}
2498 
2499 	if (right->map_token) {
2500 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2501 		right->map_token = NULL;
2502 	}
2503 
2504 	if (push_items == 0) {
2505 		ret = 1;
2506 		goto out;
2507 	}
2508 	if (!empty && push_items == btrfs_header_nritems(right))
2509 		WARN_ON(1);
2510 
2511 	/* push data from right to left */
2512 	copy_extent_buffer(left, right,
2513 			   btrfs_item_nr_offset(btrfs_header_nritems(left)),
2514 			   btrfs_item_nr_offset(0),
2515 			   push_items * sizeof(struct btrfs_item));
2516 
2517 	push_space = BTRFS_LEAF_DATA_SIZE(root) -
2518 		     btrfs_item_offset_nr(right, push_items - 1);
2519 
2520 	copy_extent_buffer(left, right, btrfs_leaf_data(left) +
2521 		     leaf_data_end(root, left) - push_space,
2522 		     btrfs_leaf_data(right) +
2523 		     btrfs_item_offset_nr(right, push_items - 1),
2524 		     push_space);
2525 	old_left_nritems = btrfs_header_nritems(left);
2526 	BUG_ON(old_left_nritems <= 0);
2527 
2528 	old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
2529 	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
2530 		u32 ioff;
2531 
2532 		item = btrfs_item_nr(left, i);
2533 		if (!left->map_token) {
2534 			map_extent_buffer(left, (unsigned long)item,
2535 					sizeof(struct btrfs_item),
2536 					&left->map_token, &left->kaddr,
2537 					&left->map_start, &left->map_len,
2538 					KM_USER1);
2539 		}
2540 
2541 		ioff = btrfs_item_offset(left, item);
2542 		btrfs_set_item_offset(left, item,
2543 		      ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2544 	}
2545 	btrfs_set_header_nritems(left, old_left_nritems + push_items);
2546 	if (left->map_token) {
2547 		unmap_extent_buffer(left, left->map_token, KM_USER1);
2548 		left->map_token = NULL;
2549 	}
2550 
2551 	/* fixup right node */
2552 	if (push_items > right_nritems) {
2553 		printk(KERN_CRIT "push items %d nr %u\n", push_items,
2554 		       right_nritems);
2555 		WARN_ON(1);
2556 	}
2557 
2558 	if (push_items < right_nritems) {
2559 		push_space = btrfs_item_offset_nr(right, push_items - 1) -
2560 						  leaf_data_end(root, right);
2561 		memmove_extent_buffer(right, btrfs_leaf_data(right) +
2562 				      BTRFS_LEAF_DATA_SIZE(root) - push_space,
2563 				      btrfs_leaf_data(right) +
2564 				      leaf_data_end(root, right), push_space);
2565 
2566 		memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2567 			      btrfs_item_nr_offset(push_items),
2568 			     (btrfs_header_nritems(right) - push_items) *
2569 			     sizeof(struct btrfs_item));
2570 	}
2571 	right_nritems -= push_items;
2572 	btrfs_set_header_nritems(right, right_nritems);
2573 	push_space = BTRFS_LEAF_DATA_SIZE(root);
2574 	for (i = 0; i < right_nritems; i++) {
2575 		item = btrfs_item_nr(right, i);
2576 
2577 		if (!right->map_token) {
2578 			map_extent_buffer(right, (unsigned long)item,
2579 					sizeof(struct btrfs_item),
2580 					&right->map_token, &right->kaddr,
2581 					&right->map_start, &right->map_len,
2582 					KM_USER1);
2583 		}
2584 
2585 		push_space = push_space - btrfs_item_size(right, item);
2586 		btrfs_set_item_offset(right, item, push_space);
2587 	}
2588 	if (right->map_token) {
2589 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2590 		right->map_token = NULL;
2591 	}
2592 
2593 	btrfs_mark_buffer_dirty(left);
2594 	if (right_nritems)
2595 		btrfs_mark_buffer_dirty(right);
2596 	else
2597 		clean_tree_block(trans, root, right);
2598 
2599 	btrfs_item_key(right, &disk_key, 0);
2600 	wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2601 	if (wret)
2602 		ret = wret;
2603 
2604 	/* then fixup the leaf pointer in the path */
2605 	if (path->slots[0] < push_items) {
2606 		path->slots[0] += old_left_nritems;
2607 		btrfs_tree_unlock(path->nodes[0]);
2608 		free_extent_buffer(path->nodes[0]);
2609 		path->nodes[0] = left;
2610 		path->slots[1] -= 1;
2611 	} else {
2612 		btrfs_tree_unlock(left);
2613 		free_extent_buffer(left);
2614 		path->slots[0] -= push_items;
2615 	}
2616 	BUG_ON(path->slots[0] < 0);
2617 	return ret;
2618 out:
2619 	btrfs_tree_unlock(left);
2620 	free_extent_buffer(left);
2621 	return ret;
2622 }
2623 
2624 /*
2625  * push some data in the path leaf to the left, trying to free up at
2626  * least data_size bytes.  returns zero if the push worked, nonzero otherwise
2627  *
2628  * max_slot can put a limit on how far into the leaf we'll push items.  The
2629  * item at 'max_slot' won't be touched.  Use (u32)-1 to make us push all the
2630  * items
2631  */
2632 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
2633 			  *root, struct btrfs_path *path, int min_data_size,
2634 			  int data_size, int empty, u32 max_slot)
2635 {
2636 	struct extent_buffer *right = path->nodes[0];
2637 	struct extent_buffer *left;
2638 	int slot;
2639 	int free_space;
2640 	u32 right_nritems;
2641 	int ret = 0;
2642 
2643 	slot = path->slots[1];
2644 	if (slot == 0)
2645 		return 1;
2646 	if (!path->nodes[1])
2647 		return 1;
2648 
2649 	right_nritems = btrfs_header_nritems(right);
2650 	if (right_nritems == 0)
2651 		return 1;
2652 
2653 	btrfs_assert_tree_locked(path->nodes[1]);
2654 
2655 	left = read_node_slot(root, path->nodes[1], slot - 1);
2656 	if (left == NULL)
2657 		return 1;
2658 
2659 	btrfs_tree_lock(left);
2660 	btrfs_set_lock_blocking(left);
2661 
2662 	free_space = btrfs_leaf_free_space(root, left);
2663 	if (free_space < data_size) {
2664 		ret = 1;
2665 		goto out;
2666 	}
2667 
2668 	/* cow and double check */
2669 	ret = btrfs_cow_block(trans, root, left,
2670 			      path->nodes[1], slot - 1, &left);
2671 	if (ret) {
2672 		/* we hit -ENOSPC, but it isn't fatal here */
2673 		ret = 1;
2674 		goto out;
2675 	}
2676 
2677 	free_space = btrfs_leaf_free_space(root, left);
2678 	if (free_space < data_size) {
2679 		ret = 1;
2680 		goto out;
2681 	}
2682 
2683 	return __push_leaf_left(trans, root, path, min_data_size,
2684 			       empty, left, free_space, right_nritems,
2685 			       max_slot);
2686 out:
2687 	btrfs_tree_unlock(left);
2688 	free_extent_buffer(left);
2689 	return ret;
2690 }
2691 
2692 /*
2693  * split the path's leaf in two, making sure there is at least data_size
2694  * available for the resulting leaf level of the path.
2695  *
2696  * returns 0 if all went well and < 0 on failure.
2697  */
2698 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2699 			       struct btrfs_root *root,
2700 			       struct btrfs_path *path,
2701 			       struct extent_buffer *l,
2702 			       struct extent_buffer *right,
2703 			       int slot, int mid, int nritems)
2704 {
2705 	int data_copy_size;
2706 	int rt_data_off;
2707 	int i;
2708 	int ret = 0;
2709 	int wret;
2710 	struct btrfs_disk_key disk_key;
2711 
2712 	nritems = nritems - mid;
2713 	btrfs_set_header_nritems(right, nritems);
2714 	data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2715 
2716 	copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2717 			   btrfs_item_nr_offset(mid),
2718 			   nritems * sizeof(struct btrfs_item));
2719 
2720 	copy_extent_buffer(right, l,
2721 		     btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2722 		     data_copy_size, btrfs_leaf_data(l) +
2723 		     leaf_data_end(root, l), data_copy_size);
2724 
2725 	rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2726 		      btrfs_item_end_nr(l, mid);
2727 
2728 	for (i = 0; i < nritems; i++) {
2729 		struct btrfs_item *item = btrfs_item_nr(right, i);
2730 		u32 ioff;
2731 
2732 		if (!right->map_token) {
2733 			map_extent_buffer(right, (unsigned long)item,
2734 					sizeof(struct btrfs_item),
2735 					&right->map_token, &right->kaddr,
2736 					&right->map_start, &right->map_len,
2737 					KM_USER1);
2738 		}
2739 
2740 		ioff = btrfs_item_offset(right, item);
2741 		btrfs_set_item_offset(right, item, ioff + rt_data_off);
2742 	}
2743 
2744 	if (right->map_token) {
2745 		unmap_extent_buffer(right, right->map_token, KM_USER1);
2746 		right->map_token = NULL;
2747 	}
2748 
2749 	btrfs_set_header_nritems(l, mid);
2750 	ret = 0;
2751 	btrfs_item_key(right, &disk_key, 0);
2752 	wret = insert_ptr(trans, root, path, &disk_key, right->start,
2753 			  path->slots[1] + 1, 1);
2754 	if (wret)
2755 		ret = wret;
2756 
2757 	btrfs_mark_buffer_dirty(right);
2758 	btrfs_mark_buffer_dirty(l);
2759 	BUG_ON(path->slots[0] != slot);
2760 
2761 	if (mid <= slot) {
2762 		btrfs_tree_unlock(path->nodes[0]);
2763 		free_extent_buffer(path->nodes[0]);
2764 		path->nodes[0] = right;
2765 		path->slots[0] -= mid;
2766 		path->slots[1] += 1;
2767 	} else {
2768 		btrfs_tree_unlock(right);
2769 		free_extent_buffer(right);
2770 	}
2771 
2772 	BUG_ON(path->slots[0] < 0);
2773 
2774 	return ret;
2775 }
2776 
2777 /*
2778  * double splits happen when we need to insert a big item in the middle
2779  * of a leaf.  A double split can leave us with 3 mostly empty leaves:
2780  * leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
2781  *          A                 B                 C
2782  *
2783  * We avoid this by trying to push the items on either side of our target
2784  * into the adjacent leaves.  If all goes well we can avoid the double split
2785  * completely.
2786  */
2787 static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
2788 					  struct btrfs_root *root,
2789 					  struct btrfs_path *path,
2790 					  int data_size)
2791 {
2792 	int ret;
2793 	int progress = 0;
2794 	int slot;
2795 	u32 nritems;
2796 
2797 	slot = path->slots[0];
2798 
2799 	/*
2800 	 * try to push all the items after our slot into the
2801 	 * right leaf
2802 	 */
2803 	ret = push_leaf_right(trans, root, path, 1, data_size, 0, slot);
2804 	if (ret < 0)
2805 		return ret;
2806 
2807 	if (ret == 0)
2808 		progress++;
2809 
2810 	nritems = btrfs_header_nritems(path->nodes[0]);
2811 	/*
2812 	 * our goal is to get our slot at the start or end of a leaf.  If
2813 	 * we've done so we're done
2814 	 */
2815 	if (path->slots[0] == 0 || path->slots[0] == nritems)
2816 		return 0;
2817 
2818 	if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
2819 		return 0;
2820 
2821 	/* try to push all the items before our slot into the next leaf */
2822 	slot = path->slots[0];
2823 	ret = push_leaf_left(trans, root, path, 1, data_size, 0, slot);
2824 	if (ret < 0)
2825 		return ret;
2826 
2827 	if (ret == 0)
2828 		progress++;
2829 
2830 	if (progress)
2831 		return 0;
2832 	return 1;
2833 }
2834 
2835 /*
2836  * split the path's leaf in two, making sure there is at least data_size
2837  * available for the resulting leaf level of the path.
2838  *
2839  * returns 0 if all went well and < 0 on failure.
2840  */
2841 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2842 			       struct btrfs_root *root,
2843 			       struct btrfs_key *ins_key,
2844 			       struct btrfs_path *path, int data_size,
2845 			       int extend)
2846 {
2847 	struct btrfs_disk_key disk_key;
2848 	struct extent_buffer *l;
2849 	u32 nritems;
2850 	int mid;
2851 	int slot;
2852 	struct extent_buffer *right;
2853 	int ret = 0;
2854 	int wret;
2855 	int split;
2856 	int num_doubles = 0;
2857 	int tried_avoid_double = 0;
2858 
2859 	l = path->nodes[0];
2860 	slot = path->slots[0];
2861 	if (extend && data_size + btrfs_item_size_nr(l, slot) +
2862 	    sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(root))
2863 		return -EOVERFLOW;
2864 
2865 	/* first try to make some room by pushing left and right */
2866 	if (data_size) {
2867 		wret = push_leaf_right(trans, root, path, data_size,
2868 				       data_size, 0, 0);
2869 		if (wret < 0)
2870 			return wret;
2871 		if (wret) {
2872 			wret = push_leaf_left(trans, root, path, data_size,
2873 					      data_size, 0, (u32)-1);
2874 			if (wret < 0)
2875 				return wret;
2876 		}
2877 		l = path->nodes[0];
2878 
2879 		/* did the pushes work? */
2880 		if (btrfs_leaf_free_space(root, l) >= data_size)
2881 			return 0;
2882 	}
2883 
2884 	if (!path->nodes[1]) {
2885 		ret = insert_new_root(trans, root, path, 1);
2886 		if (ret)
2887 			return ret;
2888 	}
2889 again:
2890 	split = 1;
2891 	l = path->nodes[0];
2892 	slot = path->slots[0];
2893 	nritems = btrfs_header_nritems(l);
2894 	mid = (nritems + 1) / 2;
2895 
2896 	if (mid <= slot) {
2897 		if (nritems == 1 ||
2898 		    leaf_space_used(l, mid, nritems - mid) + data_size >
2899 			BTRFS_LEAF_DATA_SIZE(root)) {
2900 			if (slot >= nritems) {
2901 				split = 0;
2902 			} else {
2903 				mid = slot;
2904 				if (mid != nritems &&
2905 				    leaf_space_used(l, mid, nritems - mid) +
2906 				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2907 					if (data_size && !tried_avoid_double)
2908 						goto push_for_double;
2909 					split = 2;
2910 				}
2911 			}
2912 		}
2913 	} else {
2914 		if (leaf_space_used(l, 0, mid) + data_size >
2915 			BTRFS_LEAF_DATA_SIZE(root)) {
2916 			if (!extend && data_size && slot == 0) {
2917 				split = 0;
2918 			} else if ((extend || !data_size) && slot == 0) {
2919 				mid = 1;
2920 			} else {
2921 				mid = slot;
2922 				if (mid != nritems &&
2923 				    leaf_space_used(l, mid, nritems - mid) +
2924 				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2925 					if (data_size && !tried_avoid_double)
2926 						goto push_for_double;
2927 					split = 2 ;
2928 				}
2929 			}
2930 		}
2931 	}
2932 
2933 	if (split == 0)
2934 		btrfs_cpu_key_to_disk(&disk_key, ins_key);
2935 	else
2936 		btrfs_item_key(l, &disk_key, mid);
2937 
2938 	right = btrfs_alloc_free_block(trans, root, root->leafsize, 0,
2939 					root->root_key.objectid,
2940 					&disk_key, 0, l->start, 0);
2941 	if (IS_ERR(right))
2942 		return PTR_ERR(right);
2943 
2944 	root_add_used(root, root->leafsize);
2945 
2946 	memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2947 	btrfs_set_header_bytenr(right, right->start);
2948 	btrfs_set_header_generation(right, trans->transid);
2949 	btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
2950 	btrfs_set_header_owner(right, root->root_key.objectid);
2951 	btrfs_set_header_level(right, 0);
2952 	write_extent_buffer(right, root->fs_info->fsid,
2953 			    (unsigned long)btrfs_header_fsid(right),
2954 			    BTRFS_FSID_SIZE);
2955 
2956 	write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2957 			    (unsigned long)btrfs_header_chunk_tree_uuid(right),
2958 			    BTRFS_UUID_SIZE);
2959 
2960 	if (split == 0) {
2961 		if (mid <= slot) {
2962 			btrfs_set_header_nritems(right, 0);
2963 			wret = insert_ptr(trans, root, path,
2964 					  &disk_key, right->start,
2965 					  path->slots[1] + 1, 1);
2966 			if (wret)
2967 				ret = wret;
2968 
2969 			btrfs_tree_unlock(path->nodes[0]);
2970 			free_extent_buffer(path->nodes[0]);
2971 			path->nodes[0] = right;
2972 			path->slots[0] = 0;
2973 			path->slots[1] += 1;
2974 		} else {
2975 			btrfs_set_header_nritems(right, 0);
2976 			wret = insert_ptr(trans, root, path,
2977 					  &disk_key,
2978 					  right->start,
2979 					  path->slots[1], 1);
2980 			if (wret)
2981 				ret = wret;
2982 			btrfs_tree_unlock(path->nodes[0]);
2983 			free_extent_buffer(path->nodes[0]);
2984 			path->nodes[0] = right;
2985 			path->slots[0] = 0;
2986 			if (path->slots[1] == 0) {
2987 				wret = fixup_low_keys(trans, root,
2988 						path, &disk_key, 1);
2989 				if (wret)
2990 					ret = wret;
2991 			}
2992 		}
2993 		btrfs_mark_buffer_dirty(right);
2994 		return ret;
2995 	}
2996 
2997 	ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2998 	BUG_ON(ret);
2999 
3000 	if (split == 2) {
3001 		BUG_ON(num_doubles != 0);
3002 		num_doubles++;
3003 		goto again;
3004 	}
3005 
3006 	return ret;
3007 
3008 push_for_double:
3009 	push_for_double_split(trans, root, path, data_size);
3010 	tried_avoid_double = 1;
3011 	if (btrfs_leaf_free_space(root, path->nodes[0]) >= data_size)
3012 		return 0;
3013 	goto again;
3014 }
3015 
3016 static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3017 					 struct btrfs_root *root,
3018 					 struct btrfs_path *path, int ins_len)
3019 {
3020 	struct btrfs_key key;
3021 	struct extent_buffer *leaf;
3022 	struct btrfs_file_extent_item *fi;
3023 	u64 extent_len = 0;
3024 	u32 item_size;
3025 	int ret;
3026 
3027 	leaf = path->nodes[0];
3028 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3029 
3030 	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3031 	       key.type != BTRFS_EXTENT_CSUM_KEY);
3032 
3033 	if (btrfs_leaf_free_space(root, leaf) >= ins_len)
3034 		return 0;
3035 
3036 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3037 	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3038 		fi = btrfs_item_ptr(leaf, path->slots[0],
3039 				    struct btrfs_file_extent_item);
3040 		extent_len = btrfs_file_extent_num_bytes(leaf, fi);
3041 	}
3042 	btrfs_release_path(path);
3043 
3044 	path->keep_locks = 1;
3045 	path->search_for_split = 1;
3046 	ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3047 	path->search_for_split = 0;
3048 	if (ret < 0)
3049 		goto err;
3050 
3051 	ret = -EAGAIN;
3052 	leaf = path->nodes[0];
3053 	/* if our item isn't there or got smaller, return now */
3054 	if (ret > 0 || item_size != btrfs_item_size_nr(leaf, path->slots[0]))
3055 		goto err;
3056 
3057 	/* the leaf has  changed, it now has room.  return now */
3058 	if (btrfs_leaf_free_space(root, path->nodes[0]) >= ins_len)
3059 		goto err;
3060 
3061 	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3062 		fi = btrfs_item_ptr(leaf, path->slots[0],
3063 				    struct btrfs_file_extent_item);
3064 		if (extent_len != btrfs_file_extent_num_bytes(leaf, fi))
3065 			goto err;
3066 	}
3067 
3068 	btrfs_set_path_blocking(path);
3069 	ret = split_leaf(trans, root, &key, path, ins_len, 1);
3070 	if (ret)
3071 		goto err;
3072 
3073 	path->keep_locks = 0;
3074 	btrfs_unlock_up_safe(path, 1);
3075 	return 0;
3076 err:
3077 	path->keep_locks = 0;
3078 	return ret;
3079 }
3080 
3081 static noinline int split_item(struct btrfs_trans_handle *trans,
3082 			       struct btrfs_root *root,
3083 			       struct btrfs_path *path,
3084 			       struct btrfs_key *new_key,
3085 			       unsigned long split_offset)
3086 {
3087 	struct extent_buffer *leaf;
3088 	struct btrfs_item *item;
3089 	struct btrfs_item *new_item;
3090 	int slot;
3091 	char *buf;
3092 	u32 nritems;
3093 	u32 item_size;
3094 	u32 orig_offset;
3095 	struct btrfs_disk_key disk_key;
3096 
3097 	leaf = path->nodes[0];
3098 	BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
3099 
3100 	btrfs_set_path_blocking(path);
3101 
3102 	item = btrfs_item_nr(leaf, path->slots[0]);
3103 	orig_offset = btrfs_item_offset(leaf, item);
3104 	item_size = btrfs_item_size(leaf, item);
3105 
3106 	buf = kmalloc(item_size, GFP_NOFS);
3107 	if (!buf)
3108 		return -ENOMEM;
3109 
3110 	read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
3111 			    path->slots[0]), item_size);
3112 
3113 	slot = path->slots[0] + 1;
3114 	nritems = btrfs_header_nritems(leaf);
3115 	if (slot != nritems) {
3116 		/* shift the items */
3117 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
3118 				btrfs_item_nr_offset(slot),
3119 				(nritems - slot) * sizeof(struct btrfs_item));
3120 	}
3121 
3122 	btrfs_cpu_key_to_disk(&disk_key, new_key);
3123 	btrfs_set_item_key(leaf, &disk_key, slot);
3124 
3125 	new_item = btrfs_item_nr(leaf, slot);
3126 
3127 	btrfs_set_item_offset(leaf, new_item, orig_offset);
3128 	btrfs_set_item_size(leaf, new_item, item_size - split_offset);
3129 
3130 	btrfs_set_item_offset(leaf, item,
3131 			      orig_offset + item_size - split_offset);
3132 	btrfs_set_item_size(leaf, item, split_offset);
3133 
3134 	btrfs_set_header_nritems(leaf, nritems + 1);
3135 
3136 	/* write the data for the start of the original item */
3137 	write_extent_buffer(leaf, buf,
3138 			    btrfs_item_ptr_offset(leaf, path->slots[0]),
3139 			    split_offset);
3140 
3141 	/* write the data for the new item */
3142 	write_extent_buffer(leaf, buf + split_offset,
3143 			    btrfs_item_ptr_offset(leaf, slot),
3144 			    item_size - split_offset);
3145 	btrfs_mark_buffer_dirty(leaf);
3146 
3147 	BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
3148 	kfree(buf);
3149 	return 0;
3150 }
3151 
3152 /*
3153  * This function splits a single item into two items,
3154  * giving 'new_key' to the new item and splitting the
3155  * old one at split_offset (from the start of the item).
3156  *
3157  * The path may be released by this operation.  After
3158  * the split, the path is pointing to the old item.  The
3159  * new item is going to be in the same node as the old one.
3160  *
3161  * Note, the item being split must be smaller enough to live alone on
3162  * a tree block with room for one extra struct btrfs_item
3163  *
3164  * This allows us to split the item in place, keeping a lock on the
3165  * leaf the entire time.
3166  */
3167 int btrfs_split_item(struct btrfs_trans_handle *trans,
3168 		     struct btrfs_root *root,
3169 		     struct btrfs_path *path,
3170 		     struct btrfs_key *new_key,
3171 		     unsigned long split_offset)
3172 {
3173 	int ret;
3174 	ret = setup_leaf_for_split(trans, root, path,
3175 				   sizeof(struct btrfs_item));
3176 	if (ret)
3177 		return ret;
3178 
3179 	ret = split_item(trans, root, path, new_key, split_offset);
3180 	return ret;
3181 }
3182 
3183 /*
3184  * This function duplicate a item, giving 'new_key' to the new item.
3185  * It guarantees both items live in the same tree leaf and the new item
3186  * is contiguous with the original item.
3187  *
3188  * This allows us to split file extent in place, keeping a lock on the
3189  * leaf the entire time.
3190  */
3191 int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
3192 			 struct btrfs_root *root,
3193 			 struct btrfs_path *path,
3194 			 struct btrfs_key *new_key)
3195 {
3196 	struct extent_buffer *leaf;
3197 	int ret;
3198 	u32 item_size;
3199 
3200 	leaf = path->nodes[0];
3201 	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3202 	ret = setup_leaf_for_split(trans, root, path,
3203 				   item_size + sizeof(struct btrfs_item));
3204 	if (ret)
3205 		return ret;
3206 
3207 	path->slots[0]++;
3208 	ret = setup_items_for_insert(trans, root, path, new_key, &item_size,
3209 				     item_size, item_size +
3210 				     sizeof(struct btrfs_item), 1);
3211 	BUG_ON(ret);
3212 
3213 	leaf = path->nodes[0];
3214 	memcpy_extent_buffer(leaf,
3215 			     btrfs_item_ptr_offset(leaf, path->slots[0]),
3216 			     btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
3217 			     item_size);
3218 	return 0;
3219 }
3220 
3221 /*
3222  * make the item pointed to by the path smaller.  new_size indicates
3223  * how small to make it, and from_end tells us if we just chop bytes
3224  * off the end of the item or if we shift the item to chop bytes off
3225  * the front.
3226  */
3227 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
3228 			struct btrfs_root *root,
3229 			struct btrfs_path *path,
3230 			u32 new_size, int from_end)
3231 {
3232 	int slot;
3233 	struct extent_buffer *leaf;
3234 	struct btrfs_item *item;
3235 	u32 nritems;
3236 	unsigned int data_end;
3237 	unsigned int old_data_start;
3238 	unsigned int old_size;
3239 	unsigned int size_diff;
3240 	int i;
3241 
3242 	leaf = path->nodes[0];
3243 	slot = path->slots[0];
3244 
3245 	old_size = btrfs_item_size_nr(leaf, slot);
3246 	if (old_size == new_size)
3247 		return 0;
3248 
3249 	nritems = btrfs_header_nritems(leaf);
3250 	data_end = leaf_data_end(root, leaf);
3251 
3252 	old_data_start = btrfs_item_offset_nr(leaf, slot);
3253 
3254 	size_diff = old_size - new_size;
3255 
3256 	BUG_ON(slot < 0);
3257 	BUG_ON(slot >= nritems);
3258 
3259 	/*
3260 	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3261 	 */
3262 	/* first correct the data pointers */
3263 	for (i = slot; i < nritems; i++) {
3264 		u32 ioff;
3265 		item = btrfs_item_nr(leaf, i);
3266 
3267 		if (!leaf->map_token) {
3268 			map_extent_buffer(leaf, (unsigned long)item,
3269 					sizeof(struct btrfs_item),
3270 					&leaf->map_token, &leaf->kaddr,
3271 					&leaf->map_start, &leaf->map_len,
3272 					KM_USER1);
3273 		}
3274 
3275 		ioff = btrfs_item_offset(leaf, item);
3276 		btrfs_set_item_offset(leaf, item, ioff + size_diff);
3277 	}
3278 
3279 	if (leaf->map_token) {
3280 		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3281 		leaf->map_token = NULL;
3282 	}
3283 
3284 	/* shift the data */
3285 	if (from_end) {
3286 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3287 			      data_end + size_diff, btrfs_leaf_data(leaf) +
3288 			      data_end, old_data_start + new_size - data_end);
3289 	} else {
3290 		struct btrfs_disk_key disk_key;
3291 		u64 offset;
3292 
3293 		btrfs_item_key(leaf, &disk_key, slot);
3294 
3295 		if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
3296 			unsigned long ptr;
3297 			struct btrfs_file_extent_item *fi;
3298 
3299 			fi = btrfs_item_ptr(leaf, slot,
3300 					    struct btrfs_file_extent_item);
3301 			fi = (struct btrfs_file_extent_item *)(
3302 			     (unsigned long)fi - size_diff);
3303 
3304 			if (btrfs_file_extent_type(leaf, fi) ==
3305 			    BTRFS_FILE_EXTENT_INLINE) {
3306 				ptr = btrfs_item_ptr_offset(leaf, slot);
3307 				memmove_extent_buffer(leaf, ptr,
3308 				      (unsigned long)fi,
3309 				      offsetof(struct btrfs_file_extent_item,
3310 						 disk_bytenr));
3311 			}
3312 		}
3313 
3314 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3315 			      data_end + size_diff, btrfs_leaf_data(leaf) +
3316 			      data_end, old_data_start - data_end);
3317 
3318 		offset = btrfs_disk_key_offset(&disk_key);
3319 		btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
3320 		btrfs_set_item_key(leaf, &disk_key, slot);
3321 		if (slot == 0)
3322 			fixup_low_keys(trans, root, path, &disk_key, 1);
3323 	}
3324 
3325 	item = btrfs_item_nr(leaf, slot);
3326 	btrfs_set_item_size(leaf, item, new_size);
3327 	btrfs_mark_buffer_dirty(leaf);
3328 
3329 	if (btrfs_leaf_free_space(root, leaf) < 0) {
3330 		btrfs_print_leaf(root, leaf);
3331 		BUG();
3332 	}
3333 	return 0;
3334 }
3335 
3336 /*
3337  * make the item pointed to by the path bigger, data_size is the new size.
3338  */
3339 int btrfs_extend_item(struct btrfs_trans_handle *trans,
3340 		      struct btrfs_root *root, struct btrfs_path *path,
3341 		      u32 data_size)
3342 {
3343 	int slot;
3344 	struct extent_buffer *leaf;
3345 	struct btrfs_item *item;
3346 	u32 nritems;
3347 	unsigned int data_end;
3348 	unsigned int old_data;
3349 	unsigned int old_size;
3350 	int i;
3351 
3352 	leaf = path->nodes[0];
3353 
3354 	nritems = btrfs_header_nritems(leaf);
3355 	data_end = leaf_data_end(root, leaf);
3356 
3357 	if (btrfs_leaf_free_space(root, leaf) < data_size) {
3358 		btrfs_print_leaf(root, leaf);
3359 		BUG();
3360 	}
3361 	slot = path->slots[0];
3362 	old_data = btrfs_item_end_nr(leaf, slot);
3363 
3364 	BUG_ON(slot < 0);
3365 	if (slot >= nritems) {
3366 		btrfs_print_leaf(root, leaf);
3367 		printk(KERN_CRIT "slot %d too large, nritems %d\n",
3368 		       slot, nritems);
3369 		BUG_ON(1);
3370 	}
3371 
3372 	/*
3373 	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3374 	 */
3375 	/* first correct the data pointers */
3376 	for (i = slot; i < nritems; i++) {
3377 		u32 ioff;
3378 		item = btrfs_item_nr(leaf, i);
3379 
3380 		if (!leaf->map_token) {
3381 			map_extent_buffer(leaf, (unsigned long)item,
3382 					sizeof(struct btrfs_item),
3383 					&leaf->map_token, &leaf->kaddr,
3384 					&leaf->map_start, &leaf->map_len,
3385 					KM_USER1);
3386 		}
3387 		ioff = btrfs_item_offset(leaf, item);
3388 		btrfs_set_item_offset(leaf, item, ioff - data_size);
3389 	}
3390 
3391 	if (leaf->map_token) {
3392 		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3393 		leaf->map_token = NULL;
3394 	}
3395 
3396 	/* shift the data */
3397 	memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3398 		      data_end - data_size, btrfs_leaf_data(leaf) +
3399 		      data_end, old_data - data_end);
3400 
3401 	data_end = old_data;
3402 	old_size = btrfs_item_size_nr(leaf, slot);
3403 	item = btrfs_item_nr(leaf, slot);
3404 	btrfs_set_item_size(leaf, item, old_size + data_size);
3405 	btrfs_mark_buffer_dirty(leaf);
3406 
3407 	if (btrfs_leaf_free_space(root, leaf) < 0) {
3408 		btrfs_print_leaf(root, leaf);
3409 		BUG();
3410 	}
3411 	return 0;
3412 }
3413 
3414 /*
3415  * Given a key and some data, insert items into the tree.
3416  * This does all the path init required, making room in the tree if needed.
3417  * Returns the number of keys that were inserted.
3418  */
3419 int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
3420 			    struct btrfs_root *root,
3421 			    struct btrfs_path *path,
3422 			    struct btrfs_key *cpu_key, u32 *data_size,
3423 			    int nr)
3424 {
3425 	struct extent_buffer *leaf;
3426 	struct btrfs_item *item;
3427 	int ret = 0;
3428 	int slot;
3429 	int i;
3430 	u32 nritems;
3431 	u32 total_data = 0;
3432 	u32 total_size = 0;
3433 	unsigned int data_end;
3434 	struct btrfs_disk_key disk_key;
3435 	struct btrfs_key found_key;
3436 
3437 	for (i = 0; i < nr; i++) {
3438 		if (total_size + data_size[i] + sizeof(struct btrfs_item) >
3439 		    BTRFS_LEAF_DATA_SIZE(root)) {
3440 			break;
3441 			nr = i;
3442 		}
3443 		total_data += data_size[i];
3444 		total_size += data_size[i] + sizeof(struct btrfs_item);
3445 	}
3446 	BUG_ON(nr == 0);
3447 
3448 	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3449 	if (ret == 0)
3450 		return -EEXIST;
3451 	if (ret < 0)
3452 		goto out;
3453 
3454 	leaf = path->nodes[0];
3455 
3456 	nritems = btrfs_header_nritems(leaf);
3457 	data_end = leaf_data_end(root, leaf);
3458 
3459 	if (btrfs_leaf_free_space(root, leaf) < total_size) {
3460 		for (i = nr; i >= 0; i--) {
3461 			total_data -= data_size[i];
3462 			total_size -= data_size[i] + sizeof(struct btrfs_item);
3463 			if (total_size < btrfs_leaf_free_space(root, leaf))
3464 				break;
3465 		}
3466 		nr = i;
3467 	}
3468 
3469 	slot = path->slots[0];
3470 	BUG_ON(slot < 0);
3471 
3472 	if (slot != nritems) {
3473 		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3474 
3475 		item = btrfs_item_nr(leaf, slot);
3476 		btrfs_item_key_to_cpu(leaf, &found_key, slot);
3477 
3478 		/* figure out how many keys we can insert in here */
3479 		total_data = data_size[0];
3480 		for (i = 1; i < nr; i++) {
3481 			if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3482 				break;
3483 			total_data += data_size[i];
3484 		}
3485 		nr = i;
3486 
3487 		if (old_data < data_end) {
3488 			btrfs_print_leaf(root, leaf);
3489 			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3490 			       slot, old_data, data_end);
3491 			BUG_ON(1);
3492 		}
3493 		/*
3494 		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3495 		 */
3496 		/* first correct the data pointers */
3497 		WARN_ON(leaf->map_token);
3498 		for (i = slot; i < nritems; i++) {
3499 			u32 ioff;
3500 
3501 			item = btrfs_item_nr(leaf, i);
3502 			if (!leaf->map_token) {
3503 				map_extent_buffer(leaf, (unsigned long)item,
3504 					sizeof(struct btrfs_item),
3505 					&leaf->map_token, &leaf->kaddr,
3506 					&leaf->map_start, &leaf->map_len,
3507 					KM_USER1);
3508 			}
3509 
3510 			ioff = btrfs_item_offset(leaf, item);
3511 			btrfs_set_item_offset(leaf, item, ioff - total_data);
3512 		}
3513 		if (leaf->map_token) {
3514 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3515 			leaf->map_token = NULL;
3516 		}
3517 
3518 		/* shift the items */
3519 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3520 			      btrfs_item_nr_offset(slot),
3521 			      (nritems - slot) * sizeof(struct btrfs_item));
3522 
3523 		/* shift the data */
3524 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3525 			      data_end - total_data, btrfs_leaf_data(leaf) +
3526 			      data_end, old_data - data_end);
3527 		data_end = old_data;
3528 	} else {
3529 		/*
3530 		 * this sucks but it has to be done, if we are inserting at
3531 		 * the end of the leaf only insert 1 of the items, since we
3532 		 * have no way of knowing whats on the next leaf and we'd have
3533 		 * to drop our current locks to figure it out
3534 		 */
3535 		nr = 1;
3536 	}
3537 
3538 	/* setup the item for the new data */
3539 	for (i = 0; i < nr; i++) {
3540 		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3541 		btrfs_set_item_key(leaf, &disk_key, slot + i);
3542 		item = btrfs_item_nr(leaf, slot + i);
3543 		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3544 		data_end -= data_size[i];
3545 		btrfs_set_item_size(leaf, item, data_size[i]);
3546 	}
3547 	btrfs_set_header_nritems(leaf, nritems + nr);
3548 	btrfs_mark_buffer_dirty(leaf);
3549 
3550 	ret = 0;
3551 	if (slot == 0) {
3552 		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3553 		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3554 	}
3555 
3556 	if (btrfs_leaf_free_space(root, leaf) < 0) {
3557 		btrfs_print_leaf(root, leaf);
3558 		BUG();
3559 	}
3560 out:
3561 	if (!ret)
3562 		ret = nr;
3563 	return ret;
3564 }
3565 
3566 /*
3567  * this is a helper for btrfs_insert_empty_items, the main goal here is
3568  * to save stack depth by doing the bulk of the work in a function
3569  * that doesn't call btrfs_search_slot
3570  */
3571 int setup_items_for_insert(struct btrfs_trans_handle *trans,
3572 			   struct btrfs_root *root, struct btrfs_path *path,
3573 			   struct btrfs_key *cpu_key, u32 *data_size,
3574 			   u32 total_data, u32 total_size, int nr)
3575 {
3576 	struct btrfs_item *item;
3577 	int i;
3578 	u32 nritems;
3579 	unsigned int data_end;
3580 	struct btrfs_disk_key disk_key;
3581 	int ret;
3582 	struct extent_buffer *leaf;
3583 	int slot;
3584 
3585 	leaf = path->nodes[0];
3586 	slot = path->slots[0];
3587 
3588 	nritems = btrfs_header_nritems(leaf);
3589 	data_end = leaf_data_end(root, leaf);
3590 
3591 	if (btrfs_leaf_free_space(root, leaf) < total_size) {
3592 		btrfs_print_leaf(root, leaf);
3593 		printk(KERN_CRIT "not enough freespace need %u have %d\n",
3594 		       total_size, btrfs_leaf_free_space(root, leaf));
3595 		BUG();
3596 	}
3597 
3598 	if (slot != nritems) {
3599 		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3600 
3601 		if (old_data < data_end) {
3602 			btrfs_print_leaf(root, leaf);
3603 			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3604 			       slot, old_data, data_end);
3605 			BUG_ON(1);
3606 		}
3607 		/*
3608 		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
3609 		 */
3610 		/* first correct the data pointers */
3611 		WARN_ON(leaf->map_token);
3612 		for (i = slot; i < nritems; i++) {
3613 			u32 ioff;
3614 
3615 			item = btrfs_item_nr(leaf, i);
3616 			if (!leaf->map_token) {
3617 				map_extent_buffer(leaf, (unsigned long)item,
3618 					sizeof(struct btrfs_item),
3619 					&leaf->map_token, &leaf->kaddr,
3620 					&leaf->map_start, &leaf->map_len,
3621 					KM_USER1);
3622 			}
3623 
3624 			ioff = btrfs_item_offset(leaf, item);
3625 			btrfs_set_item_offset(leaf, item, ioff - total_data);
3626 		}
3627 		if (leaf->map_token) {
3628 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3629 			leaf->map_token = NULL;
3630 		}
3631 
3632 		/* shift the items */
3633 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3634 			      btrfs_item_nr_offset(slot),
3635 			      (nritems - slot) * sizeof(struct btrfs_item));
3636 
3637 		/* shift the data */
3638 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3639 			      data_end - total_data, btrfs_leaf_data(leaf) +
3640 			      data_end, old_data - data_end);
3641 		data_end = old_data;
3642 	}
3643 
3644 	/* setup the item for the new data */
3645 	for (i = 0; i < nr; i++) {
3646 		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
3647 		btrfs_set_item_key(leaf, &disk_key, slot + i);
3648 		item = btrfs_item_nr(leaf, slot + i);
3649 		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
3650 		data_end -= data_size[i];
3651 		btrfs_set_item_size(leaf, item, data_size[i]);
3652 	}
3653 
3654 	btrfs_set_header_nritems(leaf, nritems + nr);
3655 
3656 	ret = 0;
3657 	if (slot == 0) {
3658 		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3659 		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3660 	}
3661 	btrfs_unlock_up_safe(path, 1);
3662 	btrfs_mark_buffer_dirty(leaf);
3663 
3664 	if (btrfs_leaf_free_space(root, leaf) < 0) {
3665 		btrfs_print_leaf(root, leaf);
3666 		BUG();
3667 	}
3668 	return ret;
3669 }
3670 
3671 /*
3672  * Given a key and some data, insert items into the tree.
3673  * This does all the path init required, making room in the tree if needed.
3674  */
3675 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
3676 			    struct btrfs_root *root,
3677 			    struct btrfs_path *path,
3678 			    struct btrfs_key *cpu_key, u32 *data_size,
3679 			    int nr)
3680 {
3681 	int ret = 0;
3682 	int slot;
3683 	int i;
3684 	u32 total_size = 0;
3685 	u32 total_data = 0;
3686 
3687 	for (i = 0; i < nr; i++)
3688 		total_data += data_size[i];
3689 
3690 	total_size = total_data + (nr * sizeof(struct btrfs_item));
3691 	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
3692 	if (ret == 0)
3693 		return -EEXIST;
3694 	if (ret < 0)
3695 		goto out;
3696 
3697 	slot = path->slots[0];
3698 	BUG_ON(slot < 0);
3699 
3700 	ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
3701 			       total_data, total_size, nr);
3702 
3703 out:
3704 	return ret;
3705 }
3706 
3707 /*
3708  * Given a key and some data, insert an item into the tree.
3709  * This does all the path init required, making room in the tree if needed.
3710  */
3711 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
3712 		      *root, struct btrfs_key *cpu_key, void *data, u32
3713 		      data_size)
3714 {
3715 	int ret = 0;
3716 	struct btrfs_path *path;
3717 	struct extent_buffer *leaf;
3718 	unsigned long ptr;
3719 
3720 	path = btrfs_alloc_path();
3721 	if (!path)
3722 		return -ENOMEM;
3723 	ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
3724 	if (!ret) {
3725 		leaf = path->nodes[0];
3726 		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
3727 		write_extent_buffer(leaf, data, ptr, data_size);
3728 		btrfs_mark_buffer_dirty(leaf);
3729 	}
3730 	btrfs_free_path(path);
3731 	return ret;
3732 }
3733 
3734 /*
3735  * delete the pointer from a given node.
3736  *
3737  * the tree should have been previously balanced so the deletion does not
3738  * empty a node.
3739  */
3740 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3741 		   struct btrfs_path *path, int level, int slot)
3742 {
3743 	struct extent_buffer *parent = path->nodes[level];
3744 	u32 nritems;
3745 	int ret = 0;
3746 	int wret;
3747 
3748 	nritems = btrfs_header_nritems(parent);
3749 	if (slot != nritems - 1) {
3750 		memmove_extent_buffer(parent,
3751 			      btrfs_node_key_ptr_offset(slot),
3752 			      btrfs_node_key_ptr_offset(slot + 1),
3753 			      sizeof(struct btrfs_key_ptr) *
3754 			      (nritems - slot - 1));
3755 	}
3756 	nritems--;
3757 	btrfs_set_header_nritems(parent, nritems);
3758 	if (nritems == 0 && parent == root->node) {
3759 		BUG_ON(btrfs_header_level(root->node) != 1);
3760 		/* just turn the root into a leaf and break */
3761 		btrfs_set_header_level(root->node, 0);
3762 	} else if (slot == 0) {
3763 		struct btrfs_disk_key disk_key;
3764 
3765 		btrfs_node_key(parent, &disk_key, 0);
3766 		wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
3767 		if (wret)
3768 			ret = wret;
3769 	}
3770 	btrfs_mark_buffer_dirty(parent);
3771 	return ret;
3772 }
3773 
3774 /*
3775  * a helper function to delete the leaf pointed to by path->slots[1] and
3776  * path->nodes[1].
3777  *
3778  * This deletes the pointer in path->nodes[1] and frees the leaf
3779  * block extent.  zero is returned if it all worked out, < 0 otherwise.
3780  *
3781  * The path must have already been setup for deleting the leaf, including
3782  * all the proper balancing.  path->nodes[1] must be locked.
3783  */
3784 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
3785 				   struct btrfs_root *root,
3786 				   struct btrfs_path *path,
3787 				   struct extent_buffer *leaf)
3788 {
3789 	int ret;
3790 
3791 	WARN_ON(btrfs_header_generation(leaf) != trans->transid);
3792 	ret = del_ptr(trans, root, path, 1, path->slots[1]);
3793 	if (ret)
3794 		return ret;
3795 
3796 	/*
3797 	 * btrfs_free_extent is expensive, we want to make sure we
3798 	 * aren't holding any locks when we call it
3799 	 */
3800 	btrfs_unlock_up_safe(path, 0);
3801 
3802 	root_sub_used(root, leaf->len);
3803 
3804 	btrfs_free_tree_block(trans, root, leaf, 0, 1);
3805 	return 0;
3806 }
3807 /*
3808  * delete the item at the leaf level in path.  If that empties
3809  * the leaf, remove it from the tree
3810  */
3811 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3812 		    struct btrfs_path *path, int slot, int nr)
3813 {
3814 	struct extent_buffer *leaf;
3815 	struct btrfs_item *item;
3816 	int last_off;
3817 	int dsize = 0;
3818 	int ret = 0;
3819 	int wret;
3820 	int i;
3821 	u32 nritems;
3822 
3823 	leaf = path->nodes[0];
3824 	last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
3825 
3826 	for (i = 0; i < nr; i++)
3827 		dsize += btrfs_item_size_nr(leaf, slot + i);
3828 
3829 	nritems = btrfs_header_nritems(leaf);
3830 
3831 	if (slot + nr != nritems) {
3832 		int data_end = leaf_data_end(root, leaf);
3833 
3834 		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3835 			      data_end + dsize,
3836 			      btrfs_leaf_data(leaf) + data_end,
3837 			      last_off - data_end);
3838 
3839 		for (i = slot + nr; i < nritems; i++) {
3840 			u32 ioff;
3841 
3842 			item = btrfs_item_nr(leaf, i);
3843 			if (!leaf->map_token) {
3844 				map_extent_buffer(leaf, (unsigned long)item,
3845 					sizeof(struct btrfs_item),
3846 					&leaf->map_token, &leaf->kaddr,
3847 					&leaf->map_start, &leaf->map_len,
3848 					KM_USER1);
3849 			}
3850 			ioff = btrfs_item_offset(leaf, item);
3851 			btrfs_set_item_offset(leaf, item, ioff + dsize);
3852 		}
3853 
3854 		if (leaf->map_token) {
3855 			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
3856 			leaf->map_token = NULL;
3857 		}
3858 
3859 		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
3860 			      btrfs_item_nr_offset(slot + nr),
3861 			      sizeof(struct btrfs_item) *
3862 			      (nritems - slot - nr));
3863 	}
3864 	btrfs_set_header_nritems(leaf, nritems - nr);
3865 	nritems -= nr;
3866 
3867 	/* delete the leaf if we've emptied it */
3868 	if (nritems == 0) {
3869 		if (leaf == root->node) {
3870 			btrfs_set_header_level(leaf, 0);
3871 		} else {
3872 			btrfs_set_path_blocking(path);
3873 			clean_tree_block(trans, root, leaf);
3874 			ret = btrfs_del_leaf(trans, root, path, leaf);
3875 			BUG_ON(ret);
3876 		}
3877 	} else {
3878 		int used = leaf_space_used(leaf, 0, nritems);
3879 		if (slot == 0) {
3880 			struct btrfs_disk_key disk_key;
3881 
3882 			btrfs_item_key(leaf, &disk_key, 0);
3883 			wret = fixup_low_keys(trans, root, path,
3884 					      &disk_key, 1);
3885 			if (wret)
3886 				ret = wret;
3887 		}
3888 
3889 		/* delete the leaf if it is mostly empty */
3890 		if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
3891 			/* push_leaf_left fixes the path.
3892 			 * make sure the path still points to our leaf
3893 			 * for possible call to del_ptr below
3894 			 */
3895 			slot = path->slots[1];
3896 			extent_buffer_get(leaf);
3897 
3898 			btrfs_set_path_blocking(path);
3899 			wret = push_leaf_left(trans, root, path, 1, 1,
3900 					      1, (u32)-1);
3901 			if (wret < 0 && wret != -ENOSPC)
3902 				ret = wret;
3903 
3904 			if (path->nodes[0] == leaf &&
3905 			    btrfs_header_nritems(leaf)) {
3906 				wret = push_leaf_right(trans, root, path, 1,
3907 						       1, 1, 0);
3908 				if (wret < 0 && wret != -ENOSPC)
3909 					ret = wret;
3910 			}
3911 
3912 			if (btrfs_header_nritems(leaf) == 0) {
3913 				path->slots[1] = slot;
3914 				ret = btrfs_del_leaf(trans, root, path, leaf);
3915 				BUG_ON(ret);
3916 				free_extent_buffer(leaf);
3917 			} else {
3918 				/* if we're still in the path, make sure
3919 				 * we're dirty.  Otherwise, one of the
3920 				 * push_leaf functions must have already
3921 				 * dirtied this buffer
3922 				 */
3923 				if (path->nodes[0] == leaf)
3924 					btrfs_mark_buffer_dirty(leaf);
3925 				free_extent_buffer(leaf);
3926 			}
3927 		} else {
3928 			btrfs_mark_buffer_dirty(leaf);
3929 		}
3930 	}
3931 	return ret;
3932 }
3933 
3934 /*
3935  * search the tree again to find a leaf with lesser keys
3936  * returns 0 if it found something or 1 if there are no lesser leaves.
3937  * returns < 0 on io errors.
3938  *
3939  * This may release the path, and so you may lose any locks held at the
3940  * time you call it.
3941  */
3942 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
3943 {
3944 	struct btrfs_key key;
3945 	struct btrfs_disk_key found_key;
3946 	int ret;
3947 
3948 	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
3949 
3950 	if (key.offset > 0)
3951 		key.offset--;
3952 	else if (key.type > 0)
3953 		key.type--;
3954 	else if (key.objectid > 0)
3955 		key.objectid--;
3956 	else
3957 		return 1;
3958 
3959 	btrfs_release_path(path);
3960 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3961 	if (ret < 0)
3962 		return ret;
3963 	btrfs_item_key(path->nodes[0], &found_key, 0);
3964 	ret = comp_keys(&found_key, &key);
3965 	if (ret < 0)
3966 		return 0;
3967 	return 1;
3968 }
3969 
3970 /*
3971  * A helper function to walk down the tree starting at min_key, and looking
3972  * for nodes or leaves that are either in cache or have a minimum
3973  * transaction id.  This is used by the btree defrag code, and tree logging
3974  *
3975  * This does not cow, but it does stuff the starting key it finds back
3976  * into min_key, so you can call btrfs_search_slot with cow=1 on the
3977  * key and get a writable path.
3978  *
3979  * This does lock as it descends, and path->keep_locks should be set
3980  * to 1 by the caller.
3981  *
3982  * This honors path->lowest_level to prevent descent past a given level
3983  * of the tree.
3984  *
3985  * min_trans indicates the oldest transaction that you are interested
3986  * in walking through.  Any nodes or leaves older than min_trans are
3987  * skipped over (without reading them).
3988  *
3989  * returns zero if something useful was found, < 0 on error and 1 if there
3990  * was nothing in the tree that matched the search criteria.
3991  */
3992 int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
3993 			 struct btrfs_key *max_key,
3994 			 struct btrfs_path *path, int cache_only,
3995 			 u64 min_trans)
3996 {
3997 	struct extent_buffer *cur;
3998 	struct btrfs_key found_key;
3999 	int slot;
4000 	int sret;
4001 	u32 nritems;
4002 	int level;
4003 	int ret = 1;
4004 
4005 	WARN_ON(!path->keep_locks);
4006 again:
4007 	cur = btrfs_lock_root_node(root);
4008 	level = btrfs_header_level(cur);
4009 	WARN_ON(path->nodes[level]);
4010 	path->nodes[level] = cur;
4011 	path->locks[level] = 1;
4012 
4013 	if (btrfs_header_generation(cur) < min_trans) {
4014 		ret = 1;
4015 		goto out;
4016 	}
4017 	while (1) {
4018 		nritems = btrfs_header_nritems(cur);
4019 		level = btrfs_header_level(cur);
4020 		sret = bin_search(cur, min_key, level, &slot);
4021 
4022 		/* at the lowest level, we're done, setup the path and exit */
4023 		if (level == path->lowest_level) {
4024 			if (slot >= nritems)
4025 				goto find_next_key;
4026 			ret = 0;
4027 			path->slots[level] = slot;
4028 			btrfs_item_key_to_cpu(cur, &found_key, slot);
4029 			goto out;
4030 		}
4031 		if (sret && slot > 0)
4032 			slot--;
4033 		/*
4034 		 * check this node pointer against the cache_only and
4035 		 * min_trans parameters.  If it isn't in cache or is too
4036 		 * old, skip to the next one.
4037 		 */
4038 		while (slot < nritems) {
4039 			u64 blockptr;
4040 			u64 gen;
4041 			struct extent_buffer *tmp;
4042 			struct btrfs_disk_key disk_key;
4043 
4044 			blockptr = btrfs_node_blockptr(cur, slot);
4045 			gen = btrfs_node_ptr_generation(cur, slot);
4046 			if (gen < min_trans) {
4047 				slot++;
4048 				continue;
4049 			}
4050 			if (!cache_only)
4051 				break;
4052 
4053 			if (max_key) {
4054 				btrfs_node_key(cur, &disk_key, slot);
4055 				if (comp_keys(&disk_key, max_key) >= 0) {
4056 					ret = 1;
4057 					goto out;
4058 				}
4059 			}
4060 
4061 			tmp = btrfs_find_tree_block(root, blockptr,
4062 					    btrfs_level_size(root, level - 1));
4063 
4064 			if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
4065 				free_extent_buffer(tmp);
4066 				break;
4067 			}
4068 			if (tmp)
4069 				free_extent_buffer(tmp);
4070 			slot++;
4071 		}
4072 find_next_key:
4073 		/*
4074 		 * we didn't find a candidate key in this node, walk forward
4075 		 * and find another one
4076 		 */
4077 		if (slot >= nritems) {
4078 			path->slots[level] = slot;
4079 			btrfs_set_path_blocking(path);
4080 			sret = btrfs_find_next_key(root, path, min_key, level,
4081 						  cache_only, min_trans);
4082 			if (sret == 0) {
4083 				btrfs_release_path(path);
4084 				goto again;
4085 			} else {
4086 				goto out;
4087 			}
4088 		}
4089 		/* save our key for returning back */
4090 		btrfs_node_key_to_cpu(cur, &found_key, slot);
4091 		path->slots[level] = slot;
4092 		if (level == path->lowest_level) {
4093 			ret = 0;
4094 			unlock_up(path, level, 1);
4095 			goto out;
4096 		}
4097 		btrfs_set_path_blocking(path);
4098 		cur = read_node_slot(root, cur, slot);
4099 		BUG_ON(!cur);
4100 
4101 		btrfs_tree_lock(cur);
4102 
4103 		path->locks[level - 1] = 1;
4104 		path->nodes[level - 1] = cur;
4105 		unlock_up(path, level, 1);
4106 		btrfs_clear_path_blocking(path, NULL);
4107 	}
4108 out:
4109 	if (ret == 0)
4110 		memcpy(min_key, &found_key, sizeof(found_key));
4111 	btrfs_set_path_blocking(path);
4112 	return ret;
4113 }
4114 
4115 /*
4116  * this is similar to btrfs_next_leaf, but does not try to preserve
4117  * and fixup the path.  It looks for and returns the next key in the
4118  * tree based on the current path and the cache_only and min_trans
4119  * parameters.
4120  *
4121  * 0 is returned if another key is found, < 0 if there are any errors
4122  * and 1 is returned if there are no higher keys in the tree
4123  *
4124  * path->keep_locks should be set to 1 on the search made before
4125  * calling this function.
4126  */
4127 int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4128 			struct btrfs_key *key, int level,
4129 			int cache_only, u64 min_trans)
4130 {
4131 	int slot;
4132 	struct extent_buffer *c;
4133 
4134 	WARN_ON(!path->keep_locks);
4135 	while (level < BTRFS_MAX_LEVEL) {
4136 		if (!path->nodes[level])
4137 			return 1;
4138 
4139 		slot = path->slots[level] + 1;
4140 		c = path->nodes[level];
4141 next:
4142 		if (slot >= btrfs_header_nritems(c)) {
4143 			int ret;
4144 			int orig_lowest;
4145 			struct btrfs_key cur_key;
4146 			if (level + 1 >= BTRFS_MAX_LEVEL ||
4147 			    !path->nodes[level + 1])
4148 				return 1;
4149 
4150 			if (path->locks[level + 1]) {
4151 				level++;
4152 				continue;
4153 			}
4154 
4155 			slot = btrfs_header_nritems(c) - 1;
4156 			if (level == 0)
4157 				btrfs_item_key_to_cpu(c, &cur_key, slot);
4158 			else
4159 				btrfs_node_key_to_cpu(c, &cur_key, slot);
4160 
4161 			orig_lowest = path->lowest_level;
4162 			btrfs_release_path(path);
4163 			path->lowest_level = level;
4164 			ret = btrfs_search_slot(NULL, root, &cur_key, path,
4165 						0, 0);
4166 			path->lowest_level = orig_lowest;
4167 			if (ret < 0)
4168 				return ret;
4169 
4170 			c = path->nodes[level];
4171 			slot = path->slots[level];
4172 			if (ret == 0)
4173 				slot++;
4174 			goto next;
4175 		}
4176 
4177 		if (level == 0)
4178 			btrfs_item_key_to_cpu(c, key, slot);
4179 		else {
4180 			u64 blockptr = btrfs_node_blockptr(c, slot);
4181 			u64 gen = btrfs_node_ptr_generation(c, slot);
4182 
4183 			if (cache_only) {
4184 				struct extent_buffer *cur;
4185 				cur = btrfs_find_tree_block(root, blockptr,
4186 					    btrfs_level_size(root, level - 1));
4187 				if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
4188 					slot++;
4189 					if (cur)
4190 						free_extent_buffer(cur);
4191 					goto next;
4192 				}
4193 				free_extent_buffer(cur);
4194 			}
4195 			if (gen < min_trans) {
4196 				slot++;
4197 				goto next;
4198 			}
4199 			btrfs_node_key_to_cpu(c, key, slot);
4200 		}
4201 		return 0;
4202 	}
4203 	return 1;
4204 }
4205 
4206 /*
4207  * search the tree again to find a leaf with greater keys
4208  * returns 0 if it found something or 1 if there are no greater leaves.
4209  * returns < 0 on io errors.
4210  */
4211 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4212 {
4213 	int slot;
4214 	int level;
4215 	struct extent_buffer *c;
4216 	struct extent_buffer *next;
4217 	struct btrfs_key key;
4218 	u32 nritems;
4219 	int ret;
4220 	int old_spinning = path->leave_spinning;
4221 	int force_blocking = 0;
4222 
4223 	nritems = btrfs_header_nritems(path->nodes[0]);
4224 	if (nritems == 0)
4225 		return 1;
4226 
4227 	/*
4228 	 * we take the blocks in an order that upsets lockdep.  Using
4229 	 * blocking mode is the only way around it.
4230 	 */
4231 #ifdef CONFIG_DEBUG_LOCK_ALLOC
4232 	force_blocking = 1;
4233 #endif
4234 
4235 	btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
4236 again:
4237 	level = 1;
4238 	next = NULL;
4239 	btrfs_release_path(path);
4240 
4241 	path->keep_locks = 1;
4242 
4243 	if (!force_blocking)
4244 		path->leave_spinning = 1;
4245 
4246 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4247 	path->keep_locks = 0;
4248 
4249 	if (ret < 0)
4250 		return ret;
4251 
4252 	nritems = btrfs_header_nritems(path->nodes[0]);
4253 	/*
4254 	 * by releasing the path above we dropped all our locks.  A balance
4255 	 * could have added more items next to the key that used to be
4256 	 * at the very end of the block.  So, check again here and
4257 	 * advance the path if there are now more items available.
4258 	 */
4259 	if (nritems > 0 && path->slots[0] < nritems - 1) {
4260 		if (ret == 0)
4261 			path->slots[0]++;
4262 		ret = 0;
4263 		goto done;
4264 	}
4265 
4266 	while (level < BTRFS_MAX_LEVEL) {
4267 		if (!path->nodes[level]) {
4268 			ret = 1;
4269 			goto done;
4270 		}
4271 
4272 		slot = path->slots[level] + 1;
4273 		c = path->nodes[level];
4274 		if (slot >= btrfs_header_nritems(c)) {
4275 			level++;
4276 			if (level == BTRFS_MAX_LEVEL) {
4277 				ret = 1;
4278 				goto done;
4279 			}
4280 			continue;
4281 		}
4282 
4283 		if (next) {
4284 			btrfs_tree_unlock(next);
4285 			free_extent_buffer(next);
4286 		}
4287 
4288 		next = c;
4289 		ret = read_block_for_search(NULL, root, path, &next, level,
4290 					    slot, &key);
4291 		if (ret == -EAGAIN)
4292 			goto again;
4293 
4294 		if (ret < 0) {
4295 			btrfs_release_path(path);
4296 			goto done;
4297 		}
4298 
4299 		if (!path->skip_locking) {
4300 			ret = btrfs_try_spin_lock(next);
4301 			if (!ret) {
4302 				btrfs_set_path_blocking(path);
4303 				btrfs_tree_lock(next);
4304 				if (!force_blocking)
4305 					btrfs_clear_path_blocking(path, next);
4306 			}
4307 			if (force_blocking)
4308 				btrfs_set_lock_blocking(next);
4309 		}
4310 		break;
4311 	}
4312 	path->slots[level] = slot;
4313 	while (1) {
4314 		level--;
4315 		c = path->nodes[level];
4316 		if (path->locks[level])
4317 			btrfs_tree_unlock(c);
4318 
4319 		free_extent_buffer(c);
4320 		path->nodes[level] = next;
4321 		path->slots[level] = 0;
4322 		if (!path->skip_locking)
4323 			path->locks[level] = 1;
4324 
4325 		if (!level)
4326 			break;
4327 
4328 		ret = read_block_for_search(NULL, root, path, &next, level,
4329 					    0, &key);
4330 		if (ret == -EAGAIN)
4331 			goto again;
4332 
4333 		if (ret < 0) {
4334 			btrfs_release_path(path);
4335 			goto done;
4336 		}
4337 
4338 		if (!path->skip_locking) {
4339 			btrfs_assert_tree_locked(path->nodes[level]);
4340 			ret = btrfs_try_spin_lock(next);
4341 			if (!ret) {
4342 				btrfs_set_path_blocking(path);
4343 				btrfs_tree_lock(next);
4344 				if (!force_blocking)
4345 					btrfs_clear_path_blocking(path, next);
4346 			}
4347 			if (force_blocking)
4348 				btrfs_set_lock_blocking(next);
4349 		}
4350 	}
4351 	ret = 0;
4352 done:
4353 	unlock_up(path, 0, 1);
4354 	path->leave_spinning = old_spinning;
4355 	if (!old_spinning)
4356 		btrfs_set_path_blocking(path);
4357 
4358 	return ret;
4359 }
4360 
4361 /*
4362  * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4363  * searching until it gets past min_objectid or finds an item of 'type'
4364  *
4365  * returns 0 if something is found, 1 if nothing was found and < 0 on error
4366  */
4367 int btrfs_previous_item(struct btrfs_root *root,
4368 			struct btrfs_path *path, u64 min_objectid,
4369 			int type)
4370 {
4371 	struct btrfs_key found_key;
4372 	struct extent_buffer *leaf;
4373 	u32 nritems;
4374 	int ret;
4375 
4376 	while (1) {
4377 		if (path->slots[0] == 0) {
4378 			btrfs_set_path_blocking(path);
4379 			ret = btrfs_prev_leaf(root, path);
4380 			if (ret != 0)
4381 				return ret;
4382 		} else {
4383 			path->slots[0]--;
4384 		}
4385 		leaf = path->nodes[0];
4386 		nritems = btrfs_header_nritems(leaf);
4387 		if (nritems == 0)
4388 			return 1;
4389 		if (path->slots[0] == nritems)
4390 			path->slots[0]--;
4391 
4392 		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4393 		if (found_key.objectid < min_objectid)
4394 			break;
4395 		if (found_key.type == type)
4396 			return 0;
4397 		if (found_key.objectid == min_objectid &&
4398 		    found_key.type < type)
4399 			break;
4400 	}
4401 	return 1;
4402 }
4403