ctree.c 109.5 KB
Newer Older
C
Chris Mason 已提交
1
/*
C
Chris Mason 已提交
2
 * Copyright (C) 2007,2008 Oracle.  All rights reserved.
C
Chris Mason 已提交
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */

19
#include <linux/sched.h>
20 21
#include "ctree.h"
#include "disk-io.h"
22
#include "transaction.h"
23
#include "print-tree.h"
24
#include "locking.h"
25

26 27 28
static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_path *path, int level);
static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
29
		      *root, struct btrfs_key *ins_key,
30
		      struct btrfs_path *path, int data_size, int extend);
31 32
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct extent_buffer *dst,
33
			  struct extent_buffer *src, int empty);
34 35 36 37
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
			      struct extent_buffer *dst_buf,
			      struct extent_buffer *src_buf);
38 39
static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		   struct btrfs_path *path, int level, int slot);
40

C
Chris Mason 已提交
41
struct btrfs_path *btrfs_alloc_path(void)
C
Chris Mason 已提交
42
{
C
Chris Mason 已提交
43
	struct btrfs_path *path;
J
Jeff Mahoney 已提交
44 45
	path = kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
	if (path)
46
		path->reada = 1;
C
Chris Mason 已提交
47
	return path;
C
Chris Mason 已提交
48 49
}

50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
/*
 * set all locked nodes in the path to blocking locks.  This should
 * be done before scheduling
 */
noinline void btrfs_set_path_blocking(struct btrfs_path *p)
{
	int i;
	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
		if (p->nodes[i] && p->locks[i])
			btrfs_set_lock_blocking(p->nodes[i]);
	}
}

/*
 * reset all the locked nodes in the patch to spinning locks.
65 66 67 68 69
 *
 * held is used to keep lockdep happy, when lockdep is enabled
 * we set held to a blocking lock before we go around and
 * retake all the spinlocks in the path.  You can safely use NULL
 * for held
70
 */
71 72
noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
					struct extent_buffer *held)
73 74
{
	int i;
75 76 77 78 79 80 81 82 83 84 85 86 87 88

#ifdef CONFIG_DEBUG_LOCK_ALLOC
	/* lockdep really cares that we take all of these spinlocks
	 * in the right order.  If any of the locks in the path are not
	 * currently blocking, it is going to complain.  So, make really
	 * really sure by forcing the path to blocking before we clear
	 * the path blocking.
	 */
	if (held)
		btrfs_set_lock_blocking(held);
	btrfs_set_path_blocking(p);
#endif

	for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
89 90 91
		if (p->nodes[i] && p->locks[i])
			btrfs_clear_lock_blocking(p->nodes[i]);
	}
92 93 94 95 96

#ifdef CONFIG_DEBUG_LOCK_ALLOC
	if (held)
		btrfs_clear_lock_blocking(held);
#endif
97 98
}

C
Chris Mason 已提交
99
/* this also releases the path */
C
Chris Mason 已提交
100
void btrfs_free_path(struct btrfs_path *p)
101
{
C
Chris Mason 已提交
102 103
	btrfs_release_path(NULL, p);
	kmem_cache_free(btrfs_path_cachep, p);
104 105
}

C
Chris Mason 已提交
106 107 108 109 110 111
/*
 * path release drops references on the extent buffers in the path
 * and it drops any locks held by this path
 *
 * It is safe to call this on paths that no locks or extent buffers held.
 */
C
Chris Mason 已提交
112
noinline void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
113 114
{
	int i;
115

C
Chris Mason 已提交
116
	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
117
		p->slots[i] = 0;
118
		if (!p->nodes[i])
119 120 121 122 123
			continue;
		if (p->locks[i]) {
			btrfs_tree_unlock(p->nodes[i]);
			p->locks[i] = 0;
		}
124
		free_extent_buffer(p->nodes[i]);
125
		p->nodes[i] = NULL;
126 127 128
	}
}

C
Chris Mason 已提交
129 130 131 132 133 134 135 136 137 138
/*
 * safely gets a reference on the root node of a tree.  A lock
 * is not taken, so a concurrent writer may put a different node
 * at the root of the tree.  See btrfs_lock_root_node for the
 * looping required.
 *
 * The extent buffer returned by this has a reference taken, so
 * it won't disappear.  It may stop being the root of the tree
 * at any time because there are no locks held.
 */
139 140 141 142 143 144 145 146 147 148
struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
{
	struct extent_buffer *eb;
	spin_lock(&root->node_lock);
	eb = root->node;
	extent_buffer_get(eb);
	spin_unlock(&root->node_lock);
	return eb;
}

C
Chris Mason 已提交
149 150 151 152
/* loop around taking references on and locking the root node of the
 * tree until you end up with a lock on the root.  A locked buffer
 * is returned, with a reference held.
 */
153 154 155 156
struct extent_buffer *btrfs_lock_root_node(struct btrfs_root *root)
{
	struct extent_buffer *eb;

C
Chris Mason 已提交
157
	while (1) {
158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173
		eb = btrfs_root_node(root);
		btrfs_tree_lock(eb);

		spin_lock(&root->node_lock);
		if (eb == root->node) {
			spin_unlock(&root->node_lock);
			break;
		}
		spin_unlock(&root->node_lock);

		btrfs_tree_unlock(eb);
		free_extent_buffer(eb);
	}
	return eb;
}

C
Chris Mason 已提交
174 175 176 177
/* cowonly root (everything not a reference counted cow subvolume), just get
 * put onto a simple dirty list.  transaction.c walks this to make sure they
 * get properly updated on disk.
 */
178 179 180 181 182 183 184 185
static void add_root_to_dirty_list(struct btrfs_root *root)
{
	if (root->track_dirty && list_empty(&root->dirty_list)) {
		list_add(&root->dirty_list,
			 &root->fs_info->dirty_cowonly_roots);
	}
}

C
Chris Mason 已提交
186 187 188 189 190
/*
 * used by snapshot creation to make a copy of a root for a tree with
 * a given objectid.  The buffer with the new root node is returned in
 * cow_ret, and this func returns zero on success or a negative error code.
 */
191 192 193 194 195 196 197 198 199
int btrfs_copy_root(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root,
		      struct extent_buffer *buf,
		      struct extent_buffer **cow_ret, u64 new_root_objectid)
{
	struct extent_buffer *cow;
	u32 nritems;
	int ret = 0;
	int level;
200
	struct btrfs_disk_key disk_key;
201 202 203 204 205 206 207

	WARN_ON(root->ref_cows && trans->transid !=
		root->fs_info->running_transaction->transid);
	WARN_ON(root->ref_cows && trans->transid != root->last_trans);

	level = btrfs_header_level(buf);
	nritems = btrfs_header_nritems(buf);
208 209 210 211
	if (level == 0)
		btrfs_item_key(buf, &disk_key, 0);
	else
		btrfs_node_key(buf, &disk_key, 0);
Z
Zheng Yan 已提交
212

213 214 215 216
	cow = btrfs_alloc_free_block(trans, root, buf->len, 0,
				     new_root_objectid, &disk_key, level,
				     buf->start, 0);
	if (IS_ERR(cow))
217 218 219 220 221
		return PTR_ERR(cow);

	copy_extent_buffer(cow, buf, 0, 0, cow->len);
	btrfs_set_header_bytenr(cow, cow->start);
	btrfs_set_header_generation(cow, trans->transid);
222 223 224 225 226 227 228
	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
				     BTRFS_HEADER_FLAG_RELOC);
	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
	else
		btrfs_set_header_owner(cow, new_root_objectid);
229

Y
Yan Zheng 已提交
230 231 232 233
	write_extent_buffer(cow, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(cow),
			    BTRFS_FSID_SIZE);

234
	WARN_ON(btrfs_header_generation(buf) > trans->transid);
235 236 237 238
	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
		ret = btrfs_inc_ref(trans, root, cow, 1);
	else
		ret = btrfs_inc_ref(trans, root, cow, 0);
239

240 241 242 243 244 245 246 247
	if (ret)
		return ret;

	btrfs_mark_buffer_dirty(cow);
	*cow_ret = cow;
	return 0;
}

248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
/*
 * check if the tree block can be shared by multiple trees
 */
int btrfs_block_can_be_shared(struct btrfs_root *root,
			      struct extent_buffer *buf)
{
	/*
	 * Tree blocks not in refernece counted trees and tree roots
	 * are never shared. If a block was allocated after the last
	 * snapshot and the block was not allocated by tree relocation,
	 * we know the block is not shared.
	 */
	if (root->ref_cows &&
	    buf != root->node && buf != root->commit_root &&
	    (btrfs_header_generation(buf) <=
	     btrfs_root_last_snapshot(&root->root_item) ||
	     btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
		return 1;
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
	if (root->ref_cows &&
	    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
		return 1;
#endif
	return 0;
}

static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
				       struct btrfs_root *root,
				       struct extent_buffer *buf,
				       struct extent_buffer *cow)
{
	u64 refs;
	u64 owner;
	u64 flags;
	u64 new_flags = 0;
	int ret;

	/*
	 * Backrefs update rules:
	 *
	 * Always use full backrefs for extent pointers in tree block
	 * allocated by tree relocation.
	 *
	 * If a shared tree block is no longer referenced by its owner
	 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
	 * use full backrefs for extent pointers in tree block.
	 *
	 * If a tree block is been relocating
	 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
	 * use full backrefs for extent pointers in tree block.
	 * The reason for this is some operations (such as drop tree)
	 * are only allowed for blocks use full backrefs.
	 */

	if (btrfs_block_can_be_shared(root, buf)) {
		ret = btrfs_lookup_extent_info(trans, root, buf->start,
					       buf->len, &refs, &flags);
		BUG_ON(ret);
		BUG_ON(refs == 0);
	} else {
		refs = 1;
		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
			flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
		else
			flags = 0;
	}

	owner = btrfs_header_owner(buf);
	BUG_ON(owner == BTRFS_TREE_RELOC_OBJECTID &&
	       !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));

	if (refs > 1) {
		if ((owner == root->root_key.objectid ||
		     root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
		    !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
			ret = btrfs_inc_ref(trans, root, buf, 1);
			BUG_ON(ret);

			if (root->root_key.objectid ==
			    BTRFS_TREE_RELOC_OBJECTID) {
				ret = btrfs_dec_ref(trans, root, buf, 0);
				BUG_ON(ret);
				ret = btrfs_inc_ref(trans, root, cow, 1);
				BUG_ON(ret);
			}
			new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
		} else {

			if (root->root_key.objectid ==
			    BTRFS_TREE_RELOC_OBJECTID)
				ret = btrfs_inc_ref(trans, root, cow, 1);
			else
				ret = btrfs_inc_ref(trans, root, cow, 0);
			BUG_ON(ret);
		}
		if (new_flags != 0) {
			ret = btrfs_set_disk_extent_flags(trans, root,
							  buf->start,
							  buf->len,
							  new_flags, 0);
			BUG_ON(ret);
		}
	} else {
		if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
			if (root->root_key.objectid ==
			    BTRFS_TREE_RELOC_OBJECTID)
				ret = btrfs_inc_ref(trans, root, cow, 1);
			else
				ret = btrfs_inc_ref(trans, root, cow, 0);
			BUG_ON(ret);
			ret = btrfs_dec_ref(trans, root, buf, 1);
			BUG_ON(ret);
		}
		clean_tree_block(trans, root, buf);
	}
	return 0;
}

C
Chris Mason 已提交
367
/*
C
Chris Mason 已提交
368 369 370 371
 * does the dirty work in cow of a single block.  The parent block (if
 * supplied) is updated to point to the new cow copy.  The new buffer is marked
 * dirty and returned locked.  If you modify the block it needs to be marked
 * dirty again.
C
Chris Mason 已提交
372 373 374
 *
 * search_start -- an allocation hint for the new block
 *
C
Chris Mason 已提交
375 376 377
 * empty_size -- a hint that you plan on doing more cow.  This is the size in
 * bytes the allocator should try to find free next to the block it returns.
 * This is just a hint and may be ignored by the allocator.
C
Chris Mason 已提交
378
 */
C
Chris Mason 已提交
379
static noinline int __btrfs_cow_block(struct btrfs_trans_handle *trans,
380 381 382 383
			     struct btrfs_root *root,
			     struct extent_buffer *buf,
			     struct extent_buffer *parent, int parent_slot,
			     struct extent_buffer **cow_ret,
384
			     u64 search_start, u64 empty_size)
C
Chris Mason 已提交
385
{
386
	struct btrfs_disk_key disk_key;
387
	struct extent_buffer *cow;
388
	int level;
389
	int unlock_orig = 0;
390
	u64 parent_start;
391

392 393 394
	if (*cow_ret == buf)
		unlock_orig = 1;

395
	btrfs_assert_tree_locked(buf);
396

397 398
	WARN_ON(root->ref_cows && trans->transid !=
		root->fs_info->running_transaction->transid);
399
	WARN_ON(root->ref_cows && trans->transid != root->last_trans);
400

401
	level = btrfs_header_level(buf);
Z
Zheng Yan 已提交
402

403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418
	if (level == 0)
		btrfs_item_key(buf, &disk_key, 0);
	else
		btrfs_node_key(buf, &disk_key, 0);

	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
		if (parent)
			parent_start = parent->start;
		else
			parent_start = 0;
	} else
		parent_start = 0;

	cow = btrfs_alloc_free_block(trans, root, buf->len, parent_start,
				     root->root_key.objectid, &disk_key,
				     level, search_start, empty_size);
419 420
	if (IS_ERR(cow))
		return PTR_ERR(cow);
421

422 423
	/* cow is set to blocking by btrfs_init_new_buffer */

424
	copy_extent_buffer(cow, buf, 0, 0, cow->len);
425
	btrfs_set_header_bytenr(cow, cow->start);
426
	btrfs_set_header_generation(cow, trans->transid);
427 428 429 430 431 432 433
	btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
				     BTRFS_HEADER_FLAG_RELOC);
	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
		btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
	else
		btrfs_set_header_owner(cow, root->root_key.objectid);
434

Y
Yan Zheng 已提交
435 436 437 438
	write_extent_buffer(cow, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(cow),
			    BTRFS_FSID_SIZE);

439
	update_ref_for_cow(trans, root, buf, cow);
Z
Zheng Yan 已提交
440

C
Chris Mason 已提交
441
	if (buf == root->node) {
442
		WARN_ON(parent && parent != buf);
443 444 445 446 447
		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
		    btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
			parent_start = buf->start;
		else
			parent_start = 0;
448 449

		spin_lock(&root->node_lock);
C
Chris Mason 已提交
450
		root->node = cow;
451
		extent_buffer_get(cow);
452 453
		spin_unlock(&root->node_lock);

454 455 456
		btrfs_free_extent(trans, root, buf->start, buf->len,
				  parent_start, root->root_key.objectid,
				  level, 0);
457
		free_extent_buffer(buf);
458
		add_root_to_dirty_list(root);
C
Chris Mason 已提交
459
	} else {
460 461 462 463 464 465
		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
			parent_start = parent->start;
		else
			parent_start = 0;

		WARN_ON(trans->transid != btrfs_header_generation(parent));
466
		btrfs_set_node_blockptr(parent, parent_slot,
467
					cow->start);
468 469
		btrfs_set_node_ptr_generation(parent, parent_slot,
					      trans->transid);
C
Chris Mason 已提交
470
		btrfs_mark_buffer_dirty(parent);
471
		btrfs_free_extent(trans, root, buf->start, buf->len,
472 473
				  parent_start, root->root_key.objectid,
				  level, 0);
C
Chris Mason 已提交
474
	}
475 476
	if (unlock_orig)
		btrfs_tree_unlock(buf);
477
	free_extent_buffer(buf);
C
Chris Mason 已提交
478
	btrfs_mark_buffer_dirty(cow);
C
Chris Mason 已提交
479
	*cow_ret = cow;
C
Chris Mason 已提交
480 481 482
	return 0;
}

483 484 485 486 487 488 489 490 491 492 493 494
static inline int should_cow_block(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct extent_buffer *buf)
{
	if (btrfs_header_generation(buf) == trans->transid &&
	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
	    !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
	      btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
		return 0;
	return 1;
}

C
Chris Mason 已提交
495 496 497 498 499
/*
 * cows a single block, see __btrfs_cow_block for the real work.
 * This version of it has extra checks so that a block isn't cow'd more than
 * once per transaction, as long as it hasn't been written yet
 */
C
Chris Mason 已提交
500
noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
501 502
		    struct btrfs_root *root, struct extent_buffer *buf,
		    struct extent_buffer *parent, int parent_slot,
503
		    struct extent_buffer **cow_ret)
504 505
{
	u64 search_start;
506
	int ret;
C
Chris Mason 已提交
507

508
	if (trans->transaction != root->fs_info->running_transaction) {
C
Chris Mason 已提交
509 510 511
		printk(KERN_CRIT "trans %llu running %llu\n",
		       (unsigned long long)trans->transid,
		       (unsigned long long)
512 513 514 515
		       root->fs_info->running_transaction->transid);
		WARN_ON(1);
	}
	if (trans->transid != root->fs_info->generation) {
C
Chris Mason 已提交
516 517 518
		printk(KERN_CRIT "trans %llu running %llu\n",
		       (unsigned long long)trans->transid,
		       (unsigned long long)root->fs_info->generation);
519 520
		WARN_ON(1);
	}
C
Chris Mason 已提交
521

522
	if (!should_cow_block(trans, root, buf)) {
523 524 525
		*cow_ret = buf;
		return 0;
	}
526

527
	search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
528 529 530 531 532

	if (parent)
		btrfs_set_lock_blocking(parent);
	btrfs_set_lock_blocking(buf);

533
	ret = __btrfs_cow_block(trans, root, buf, parent,
534
				 parent_slot, cow_ret, search_start, 0);
535
	return ret;
536 537
}

C
Chris Mason 已提交
538 539 540 541
/*
 * helper function for defrag to decide if two blocks pointed to by a
 * node are actually close by
 */
542
static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
543
{
544
	if (blocknr < other && other - (blocknr + blocksize) < 32768)
545
		return 1;
546
	if (blocknr > other && blocknr - (other + blocksize) < 32768)
547 548 549 550
		return 1;
	return 0;
}

551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574
/*
 * compare two keys in a memcmp fashion
 */
static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
{
	struct btrfs_key k1;

	btrfs_disk_key_to_cpu(&k1, disk);

	if (k1.objectid > k2->objectid)
		return 1;
	if (k1.objectid < k2->objectid)
		return -1;
	if (k1.type > k2->type)
		return 1;
	if (k1.type < k2->type)
		return -1;
	if (k1.offset > k2->offset)
		return 1;
	if (k1.offset < k2->offset)
		return -1;
	return 0;
}

575 576 577
/*
 * same as comp_keys only with two btrfs_key's
 */
578
int btrfs_comp_cpu_keys(struct btrfs_key *k1, struct btrfs_key *k2)
579 580 581 582 583 584 585 586 587 588 589 590 591 592 593
{
	if (k1->objectid > k2->objectid)
		return 1;
	if (k1->objectid < k2->objectid)
		return -1;
	if (k1->type > k2->type)
		return 1;
	if (k1->type < k2->type)
		return -1;
	if (k1->offset > k2->offset)
		return 1;
	if (k1->offset < k2->offset)
		return -1;
	return 0;
}
594

C
Chris Mason 已提交
595 596 597 598 599
/*
 * this is used by the defrag code to go through all the
 * leaves pointed to by a node and reallocate them so that
 * disk order is close to key order
 */
600
int btrfs_realloc_node(struct btrfs_trans_handle *trans,
601
		       struct btrfs_root *root, struct extent_buffer *parent,
602 603
		       int start_slot, int cache_only, u64 *last_ret,
		       struct btrfs_key *progress)
604
{
605
	struct extent_buffer *cur;
606
	u64 blocknr;
607
	u64 gen;
608 609
	u64 search_start = *last_ret;
	u64 last_block = 0;
610 611 612 613 614
	u64 other;
	u32 parent_nritems;
	int end_slot;
	int i;
	int err = 0;
615
	int parent_level;
616 617
	int uptodate;
	u32 blocksize;
618 619
	int progress_passed = 0;
	struct btrfs_disk_key disk_key;
620

621 622 623 624
	parent_level = btrfs_header_level(parent);
	if (cache_only && parent_level != 1)
		return 0;

C
Chris Mason 已提交
625
	if (trans->transaction != root->fs_info->running_transaction)
626
		WARN_ON(1);
C
Chris Mason 已提交
627
	if (trans->transid != root->fs_info->generation)
628
		WARN_ON(1);
629

630 631
	parent_nritems = btrfs_header_nritems(parent);
	blocksize = btrfs_level_size(root, parent_level - 1);
632 633 634 635 636
	end_slot = parent_nritems;

	if (parent_nritems == 1)
		return 0;

637 638
	btrfs_set_lock_blocking(parent);

639 640
	for (i = start_slot; i < end_slot; i++) {
		int close = 1;
641

642 643 644 645 646 647 648 649
		if (!parent->map_token) {
			map_extent_buffer(parent,
					btrfs_node_key_ptr_offset(i),
					sizeof(struct btrfs_key_ptr),
					&parent->map_token, &parent->kaddr,
					&parent->map_start, &parent->map_len,
					KM_USER1);
		}
650 651 652 653 654
		btrfs_node_key(parent, &disk_key, i);
		if (!progress_passed && comp_keys(&disk_key, progress) < 0)
			continue;

		progress_passed = 1;
655
		blocknr = btrfs_node_blockptr(parent, i);
656
		gen = btrfs_node_ptr_generation(parent, i);
657 658
		if (last_block == 0)
			last_block = blocknr;
659

660
		if (i > 0) {
661 662
			other = btrfs_node_blockptr(parent, i - 1);
			close = close_blocks(blocknr, other, blocksize);
663
		}
C
Chris Mason 已提交
664
		if (!close && i < end_slot - 2) {
665 666
			other = btrfs_node_blockptr(parent, i + 1);
			close = close_blocks(blocknr, other, blocksize);
667
		}
668 669
		if (close) {
			last_block = blocknr;
670
			continue;
671
		}
672 673 674 675 676
		if (parent->map_token) {
			unmap_extent_buffer(parent, parent->map_token,
					    KM_USER1);
			parent->map_token = NULL;
		}
677

678 679
		cur = btrfs_find_tree_block(root, blocknr, blocksize);
		if (cur)
680
			uptodate = btrfs_buffer_uptodate(cur, gen);
681 682
		else
			uptodate = 0;
683
		if (!cur || !uptodate) {
684
			if (cache_only) {
685
				free_extent_buffer(cur);
686 687
				continue;
			}
688 689
			if (!cur) {
				cur = read_tree_block(root, blocknr,
690
							 blocksize, gen);
691
			} else if (!uptodate) {
692
				btrfs_read_buffer(cur, gen);
693
			}
694
		}
695
		if (search_start == 0)
696
			search_start = last_block;
697

698
		btrfs_tree_lock(cur);
699
		btrfs_set_lock_blocking(cur);
700
		err = __btrfs_cow_block(trans, root, cur, parent, i,
701
					&cur, search_start,
702
					min(16 * blocksize,
703
					    (end_slot - i) * blocksize));
Y
Yan 已提交
704
		if (err) {
705
			btrfs_tree_unlock(cur);
706
			free_extent_buffer(cur);
707
			break;
Y
Yan 已提交
708
		}
709 710
		search_start = cur->start;
		last_block = cur->start;
711
		*last_ret = search_start;
712 713
		btrfs_tree_unlock(cur);
		free_extent_buffer(cur);
714
	}
715 716 717 718 719
	if (parent->map_token) {
		unmap_extent_buffer(parent, parent->map_token,
				    KM_USER1);
		parent->map_token = NULL;
	}
720 721 722
	return err;
}

C
Chris Mason 已提交
723 724 725 726 727
/*
 * The leaf data grows from end-to-front in the node.
 * this returns the address of the start of the last item,
 * which is the stop of the leaf data stack
 */
C
Chris Mason 已提交
728
static inline unsigned int leaf_data_end(struct btrfs_root *root,
729
					 struct extent_buffer *leaf)
730
{
731
	u32 nr = btrfs_header_nritems(leaf);
732
	if (nr == 0)
C
Chris Mason 已提交
733
		return BTRFS_LEAF_DATA_SIZE(root);
734
	return btrfs_item_offset_nr(leaf, nr - 1);
735 736
}

C
Chris Mason 已提交
737 738 739 740
/*
 * extra debugging checks to make sure all the items in a key are
 * well formed and in the proper order
 */
C
Chris Mason 已提交
741 742
static int check_node(struct btrfs_root *root, struct btrfs_path *path,
		      int level)
C
Chris Mason 已提交
743
{
744 745 746 747
	struct extent_buffer *parent = NULL;
	struct extent_buffer *node = path->nodes[level];
	struct btrfs_disk_key parent_key;
	struct btrfs_disk_key node_key;
C
Chris Mason 已提交
748
	int parent_slot;
749 750
	int slot;
	struct btrfs_key cpukey;
751
	u32 nritems = btrfs_header_nritems(node);
C
Chris Mason 已提交
752 753

	if (path->nodes[level + 1])
754
		parent = path->nodes[level + 1];
A
Aneesh 已提交
755

756
	slot = path->slots[level];
757 758
	BUG_ON(nritems == 0);
	if (parent) {
A
Aneesh 已提交
759
		parent_slot = path->slots[level + 1];
760 761 762
		btrfs_node_key(parent, &parent_key, parent_slot);
		btrfs_node_key(node, &node_key, 0);
		BUG_ON(memcmp(&parent_key, &node_key,
C
Chris Mason 已提交
763
			      sizeof(struct btrfs_disk_key)));
764
		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
765
		       btrfs_header_bytenr(node));
C
Chris Mason 已提交
766
	}
C
Chris Mason 已提交
767
	BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
768
	if (slot != 0) {
769 770 771
		btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
		btrfs_node_key(node, &node_key, slot);
		BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
772 773
	}
	if (slot < nritems - 1) {
774 775 776
		btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
		btrfs_node_key(node, &node_key, slot);
		BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
C
Chris Mason 已提交
777 778 779 780
	}
	return 0;
}

C
Chris Mason 已提交
781 782 783 784
/*
 * extra checking to make sure all the items in a leaf are
 * well formed and in the proper order
 */
C
Chris Mason 已提交
785 786
static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
		      int level)
C
Chris Mason 已提交
787
{
788 789
	struct extent_buffer *leaf = path->nodes[level];
	struct extent_buffer *parent = NULL;
C
Chris Mason 已提交
790
	int parent_slot;
791
	struct btrfs_key cpukey;
792 793 794
	struct btrfs_disk_key parent_key;
	struct btrfs_disk_key leaf_key;
	int slot = path->slots[0];
795

796
	u32 nritems = btrfs_header_nritems(leaf);
C
Chris Mason 已提交
797 798

	if (path->nodes[level + 1])
799
		parent = path->nodes[level + 1];
800 801 802 803 804

	if (nritems == 0)
		return 0;

	if (parent) {
A
Aneesh 已提交
805
		parent_slot = path->slots[level + 1];
806 807
		btrfs_node_key(parent, &parent_key, parent_slot);
		btrfs_item_key(leaf, &leaf_key, 0);
808

809
		BUG_ON(memcmp(&parent_key, &leaf_key,
C
Chris Mason 已提交
810
		       sizeof(struct btrfs_disk_key)));
811
		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
812
		       btrfs_header_bytenr(leaf));
813 814 815 816 817 818
	}
	if (slot != 0 && slot < nritems - 1) {
		btrfs_item_key(leaf, &leaf_key, slot);
		btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
		if (comp_keys(&leaf_key, &cpukey) <= 0) {
			btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
819
			printk(KERN_CRIT "slot %d offset bad key\n", slot);
820 821 822 823 824
			BUG_ON(1);
		}
		if (btrfs_item_offset_nr(leaf, slot - 1) !=
		       btrfs_item_end_nr(leaf, slot)) {
			btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
825
			printk(KERN_CRIT "slot %d offset bad\n", slot);
826 827
			BUG_ON(1);
		}
828 829
	}
	if (slot < nritems - 1) {
830 831 832 833 834 835
		btrfs_item_key(leaf, &leaf_key, slot);
		btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
		BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
		if (btrfs_item_offset_nr(leaf, slot) !=
			btrfs_item_end_nr(leaf, slot + 1)) {
			btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
836
			printk(KERN_CRIT "slot %d offset bad\n", slot);
837 838
			BUG_ON(1);
		}
C
Chris Mason 已提交
839
	}
840 841
	BUG_ON(btrfs_item_offset_nr(leaf, 0) +
	       btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
C
Chris Mason 已提交
842 843 844
	return 0;
}

C
Chris Mason 已提交
845
static noinline int check_block(struct btrfs_root *root,
846
				struct btrfs_path *path, int level)
C
Chris Mason 已提交
847
{
848
	return 0;
C
Chris Mason 已提交
849
	if (level == 0)
C
Chris Mason 已提交
850 851
		return check_leaf(root, path, level);
	return check_node(root, path, level);
C
Chris Mason 已提交
852 853
}

C
Chris Mason 已提交
854
/*
855 856 857
 * search for key in the extent_buffer.  The items start at offset p,
 * and they are item_size apart.  There are 'max' items in p.
 *
C
Chris Mason 已提交
858 859 860 861 862 863
 * the slot in the array is returned via slot, and it points to
 * the place where you would insert key if it is not found in
 * the array.
 *
 * slot may point to max if the key is bigger than all of the keys
 */
864 865 866 867
static noinline int generic_bin_search(struct extent_buffer *eb,
				       unsigned long p,
				       int item_size, struct btrfs_key *key,
				       int max, int *slot)
868 869 870 871 872
{
	int low = 0;
	int high = max;
	int mid;
	int ret;
873
	struct btrfs_disk_key *tmp = NULL;
874 875 876 877 878 879
	struct btrfs_disk_key unaligned;
	unsigned long offset;
	char *map_token = NULL;
	char *kaddr = NULL;
	unsigned long map_start = 0;
	unsigned long map_len = 0;
880
	int err;
881

C
Chris Mason 已提交
882
	while (low < high) {
883
		mid = (low + high) / 2;
884 885 886 887 888
		offset = p + mid * item_size;

		if (!map_token || offset < map_start ||
		    (offset + sizeof(struct btrfs_disk_key)) >
		    map_start + map_len) {
889
			if (map_token) {
890
				unmap_extent_buffer(eb, map_token, KM_USER0);
891 892
				map_token = NULL;
			}
893 894

			err = map_private_extent_buffer(eb, offset,
895 896 897 898 899 900 901 902 903 904 905 906
						sizeof(struct btrfs_disk_key),
						&map_token, &kaddr,
						&map_start, &map_len, KM_USER0);

			if (!err) {
				tmp = (struct btrfs_disk_key *)(kaddr + offset -
							map_start);
			} else {
				read_extent_buffer(eb, &unaligned,
						   offset, sizeof(unaligned));
				tmp = &unaligned;
			}
907 908 909 910 911

		} else {
			tmp = (struct btrfs_disk_key *)(kaddr + offset -
							map_start);
		}
912 913 914 915 916 917 918 919
		ret = comp_keys(tmp, key);

		if (ret < 0)
			low = mid + 1;
		else if (ret > 0)
			high = mid;
		else {
			*slot = mid;
920 921
			if (map_token)
				unmap_extent_buffer(eb, map_token, KM_USER0);
922 923 924 925
			return 0;
		}
	}
	*slot = low;
926 927
	if (map_token)
		unmap_extent_buffer(eb, map_token, KM_USER0);
928 929 930
	return 1;
}

C
Chris Mason 已提交
931 932 933 934
/*
 * simple bin_search frontend that does the right thing for
 * leaves vs nodes
 */
935 936
static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
		      int level, int *slot)
937
{
938 939 940
	if (level == 0) {
		return generic_bin_search(eb,
					  offsetof(struct btrfs_leaf, items),
C
Chris Mason 已提交
941
					  sizeof(struct btrfs_item),
942
					  key, btrfs_header_nritems(eb),
943
					  slot);
944
	} else {
945 946
		return generic_bin_search(eb,
					  offsetof(struct btrfs_node, ptrs),
C
Chris Mason 已提交
947
					  sizeof(struct btrfs_key_ptr),
948
					  key, btrfs_header_nritems(eb),
949
					  slot);
950 951 952 953
	}
	return -1;
}

954 955 956 957 958 959
int btrfs_bin_search(struct extent_buffer *eb, struct btrfs_key *key,
		     int level, int *slot)
{
	return bin_search(eb, key, level, slot);
}

C
Chris Mason 已提交
960 961 962 963
/* given a node and slot number, this reads the blocks it points to.  The
 * extent buffer is returned with a reference taken (but unlocked).
 * NULL is returned on error.
 */
964
static noinline struct extent_buffer *read_node_slot(struct btrfs_root *root,
965
				   struct extent_buffer *parent, int slot)
966
{
967
	int level = btrfs_header_level(parent);
968 969
	if (slot < 0)
		return NULL;
970
	if (slot >= btrfs_header_nritems(parent))
971
		return NULL;
972 973 974

	BUG_ON(level == 0);

975
	return read_tree_block(root, btrfs_node_blockptr(parent, slot),
976 977
		       btrfs_level_size(root, level - 1),
		       btrfs_node_ptr_generation(parent, slot));
978 979
}

C
Chris Mason 已提交
980 981 982 983 984
/*
 * node level balancing, used to make sure nodes are in proper order for
 * item deletion.  We balance from the top down, so we have to make sure
 * that a deletion won't leave an node completely empty later on.
 */
985
static noinline int balance_level(struct btrfs_trans_handle *trans,
986 987
			 struct btrfs_root *root,
			 struct btrfs_path *path, int level)
988
{
989 990 991 992
	struct extent_buffer *right = NULL;
	struct extent_buffer *mid;
	struct extent_buffer *left = NULL;
	struct extent_buffer *parent = NULL;
993 994 995 996
	int ret = 0;
	int wret;
	int pslot;
	int orig_slot = path->slots[level];
997
	int err_on_enospc = 0;
998
	u64 orig_ptr;
999 1000 1001 1002

	if (level == 0)
		return 0;

1003
	mid = path->nodes[level];
1004

1005
	WARN_ON(!path->locks[level]);
1006 1007
	WARN_ON(btrfs_header_generation(mid) != trans->transid);

1008
	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
1009

C
Chris Mason 已提交
1010
	if (level < BTRFS_MAX_LEVEL - 1)
1011
		parent = path->nodes[level + 1];
1012 1013
	pslot = path->slots[level + 1];

C
Chris Mason 已提交
1014 1015 1016 1017
	/*
	 * deal with the case where there is only one pointer in the root
	 * by promoting the node below to a root
	 */
1018 1019
	if (!parent) {
		struct extent_buffer *child;
1020

1021
		if (btrfs_header_nritems(mid) != 1)
1022 1023 1024
			return 0;

		/* promote the child to a root */
1025
		child = read_node_slot(root, mid, 0);
1026
		BUG_ON(!child);
1027
		btrfs_tree_lock(child);
1028
		btrfs_set_lock_blocking(child);
1029
		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
1030 1031
		BUG_ON(ret);

1032
		spin_lock(&root->node_lock);
1033
		root->node = child;
1034 1035
		spin_unlock(&root->node_lock);

1036
		add_root_to_dirty_list(root);
1037
		btrfs_tree_unlock(child);
1038

1039
		path->locks[level] = 0;
1040
		path->nodes[level] = NULL;
1041
		clean_tree_block(trans, root, mid);
1042
		btrfs_tree_unlock(mid);
1043
		/* once for the path */
1044
		free_extent_buffer(mid);
1045
		ret = btrfs_free_extent(trans, root, mid->start, mid->len,
1046
					0, root->root_key.objectid, level, 1);
1047
		/* once for the root ptr */
1048
		free_extent_buffer(mid);
1049
		return ret;
1050
	}
1051
	if (btrfs_header_nritems(mid) >
C
Chris Mason 已提交
1052
	    BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
1053 1054
		return 0;

1055
	if (btrfs_header_nritems(mid) > 2)
1056 1057
		return 0;

1058
	if (btrfs_header_nritems(mid) < 2)
1059 1060
		err_on_enospc = 1;

1061 1062
	left = read_node_slot(root, parent, pslot - 1);
	if (left) {
1063
		btrfs_tree_lock(left);
1064
		btrfs_set_lock_blocking(left);
1065
		wret = btrfs_cow_block(trans, root, left,
1066
				       parent, pslot - 1, &left);
1067 1068 1069 1070
		if (wret) {
			ret = wret;
			goto enospc;
		}
1071
	}
1072 1073
	right = read_node_slot(root, parent, pslot + 1);
	if (right) {
1074
		btrfs_tree_lock(right);
1075
		btrfs_set_lock_blocking(right);
1076
		wret = btrfs_cow_block(trans, root, right,
1077
				       parent, pslot + 1, &right);
1078 1079 1080 1081 1082 1083 1084
		if (wret) {
			ret = wret;
			goto enospc;
		}
	}

	/* first, try to make some room in the middle buffer */
1085 1086
	if (left) {
		orig_slot += btrfs_header_nritems(left);
1087
		wret = push_node_left(trans, root, left, mid, 1);
1088 1089
		if (wret < 0)
			ret = wret;
1090
		if (btrfs_header_nritems(mid) < 2)
1091
			err_on_enospc = 1;
1092
	}
1093 1094 1095 1096

	/*
	 * then try to empty the right most buffer into the middle
	 */
1097
	if (right) {
1098
		wret = push_node_left(trans, root, mid, right, 1);
1099
		if (wret < 0 && wret != -ENOSPC)
1100
			ret = wret;
1101
		if (btrfs_header_nritems(right) == 0) {
1102 1103 1104
			u64 bytenr = right->start;
			u32 blocksize = right->len;

1105
			clean_tree_block(trans, root, right);
1106
			btrfs_tree_unlock(right);
1107
			free_extent_buffer(right);
1108
			right = NULL;
1109 1110
			wret = del_ptr(trans, root, path, level + 1, pslot +
				       1);
1111 1112
			if (wret)
				ret = wret;
1113
			wret = btrfs_free_extent(trans, root, bytenr,
1114 1115 1116
						 blocksize, 0,
						 root->root_key.objectid,
						 level, 0);
1117 1118 1119
			if (wret)
				ret = wret;
		} else {
1120 1121 1122 1123
			struct btrfs_disk_key right_key;
			btrfs_node_key(right, &right_key, 0);
			btrfs_set_node_key(parent, &right_key, pslot + 1);
			btrfs_mark_buffer_dirty(parent);
1124 1125
		}
	}
1126
	if (btrfs_header_nritems(mid) == 1) {
1127 1128 1129 1130 1131 1132 1133 1134 1135
		/*
		 * we're not allowed to leave a node with one item in the
		 * tree during a delete.  A deletion from lower in the tree
		 * could try to delete the only pointer in this node.
		 * So, pull some keys from the left.
		 * There has to be a left pointer at this point because
		 * otherwise we would have pulled some pointers from the
		 * right
		 */
1136 1137
		BUG_ON(!left);
		wret = balance_node_right(trans, root, mid, left);
1138
		if (wret < 0) {
1139
			ret = wret;
1140 1141
			goto enospc;
		}
1142 1143 1144 1145 1146
		if (wret == 1) {
			wret = push_node_left(trans, root, left, mid, 1);
			if (wret < 0)
				ret = wret;
		}
1147 1148
		BUG_ON(wret == 1);
	}
1149
	if (btrfs_header_nritems(mid) == 0) {
1150
		/* we've managed to empty the middle node, drop it */
1151 1152
		u64 bytenr = mid->start;
		u32 blocksize = mid->len;
1153

1154
		clean_tree_block(trans, root, mid);
1155
		btrfs_tree_unlock(mid);
1156
		free_extent_buffer(mid);
1157
		mid = NULL;
1158
		wret = del_ptr(trans, root, path, level + 1, pslot);
1159 1160
		if (wret)
			ret = wret;
1161
		wret = btrfs_free_extent(trans, root, bytenr, blocksize,
1162 1163
					 0, root->root_key.objectid,
					 level, 0);
1164 1165
		if (wret)
			ret = wret;
1166 1167
	} else {
		/* update the parent key to reflect our changes */
1168 1169 1170 1171
		struct btrfs_disk_key mid_key;
		btrfs_node_key(mid, &mid_key, 0);
		btrfs_set_node_key(parent, &mid_key, pslot);
		btrfs_mark_buffer_dirty(parent);
1172
	}
1173

1174
	/* update the path */
1175 1176 1177
	if (left) {
		if (btrfs_header_nritems(left) > orig_slot) {
			extent_buffer_get(left);
1178
			/* left was locked after cow */
1179
			path->nodes[level] = left;
1180 1181
			path->slots[level + 1] -= 1;
			path->slots[level] = orig_slot;
1182 1183
			if (mid) {
				btrfs_tree_unlock(mid);
1184
				free_extent_buffer(mid);
1185
			}
1186
		} else {
1187
			orig_slot -= btrfs_header_nritems(left);
1188 1189 1190
			path->slots[level] = orig_slot;
		}
	}
1191
	/* double check we haven't messed things up */
C
Chris Mason 已提交
1192
	check_block(root, path, level);
C
Chris Mason 已提交
1193
	if (orig_ptr !=
1194
	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1195
		BUG();
1196
enospc:
1197 1198
	if (right) {
		btrfs_tree_unlock(right);
1199
		free_extent_buffer(right);
1200 1201 1202 1203
	}
	if (left) {
		if (path->nodes[level] != left)
			btrfs_tree_unlock(left);
1204
		free_extent_buffer(left);
1205
	}
1206 1207 1208
	return ret;
}

C
Chris Mason 已提交
1209 1210 1211 1212
/* Node balancing for insertion.  Here we only split or push nodes around
 * when they are completely full.  This is also done top down, so we
 * have to be pessimistic.
 */
C
Chris Mason 已提交
1213
static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1214 1215
					  struct btrfs_root *root,
					  struct btrfs_path *path, int level)
1216
{
1217 1218 1219 1220
	struct extent_buffer *right = NULL;
	struct extent_buffer *mid;
	struct extent_buffer *left = NULL;
	struct extent_buffer *parent = NULL;
1221 1222 1223 1224 1225 1226 1227 1228 1229
	int ret = 0;
	int wret;
	int pslot;
	int orig_slot = path->slots[level];
	u64 orig_ptr;

	if (level == 0)
		return 1;

1230
	mid = path->nodes[level];
1231
	WARN_ON(btrfs_header_generation(mid) != trans->transid);
1232 1233 1234
	orig_ptr = btrfs_node_blockptr(mid, orig_slot);

	if (level < BTRFS_MAX_LEVEL - 1)
1235
		parent = path->nodes[level + 1];
1236 1237
	pslot = path->slots[level + 1];

1238
	if (!parent)
1239 1240
		return 1;

1241
	left = read_node_slot(root, parent, pslot - 1);
1242 1243

	/* first, try to make some room in the middle buffer */
1244
	if (left) {
1245
		u32 left_nr;
1246 1247

		btrfs_tree_lock(left);
1248 1249
		btrfs_set_lock_blocking(left);

1250
		left_nr = btrfs_header_nritems(left);
C
Chris Mason 已提交
1251 1252 1253
		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
			wret = 1;
		} else {
1254
			ret = btrfs_cow_block(trans, root, left, parent,
1255
					      pslot - 1, &left);
1256 1257 1258 1259
			if (ret)
				wret = 1;
			else {
				wret = push_node_left(trans, root,
1260
						      left, mid, 0);
1261
			}
C
Chris Mason 已提交
1262
		}
1263 1264 1265
		if (wret < 0)
			ret = wret;
		if (wret == 0) {
1266
			struct btrfs_disk_key disk_key;
1267
			orig_slot += left_nr;
1268 1269 1270 1271 1272
			btrfs_node_key(mid, &disk_key, 0);
			btrfs_set_node_key(parent, &disk_key, pslot);
			btrfs_mark_buffer_dirty(parent);
			if (btrfs_header_nritems(left) > orig_slot) {
				path->nodes[level] = left;
1273 1274
				path->slots[level + 1] -= 1;
				path->slots[level] = orig_slot;
1275
				btrfs_tree_unlock(mid);
1276
				free_extent_buffer(mid);
1277 1278
			} else {
				orig_slot -=
1279
					btrfs_header_nritems(left);
1280
				path->slots[level] = orig_slot;
1281
				btrfs_tree_unlock(left);
1282
				free_extent_buffer(left);
1283 1284 1285
			}
			return 0;
		}
1286
		btrfs_tree_unlock(left);
1287
		free_extent_buffer(left);
1288
	}
1289
	right = read_node_slot(root, parent, pslot + 1);
1290 1291 1292 1293

	/*
	 * then try to empty the right most buffer into the middle
	 */
1294
	if (right) {
C
Chris Mason 已提交
1295
		u32 right_nr;
1296

1297
		btrfs_tree_lock(right);
1298 1299
		btrfs_set_lock_blocking(right);

1300
		right_nr = btrfs_header_nritems(right);
C
Chris Mason 已提交
1301 1302 1303
		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
			wret = 1;
		} else {
1304 1305
			ret = btrfs_cow_block(trans, root, right,
					      parent, pslot + 1,
1306
					      &right);
1307 1308 1309 1310
			if (ret)
				wret = 1;
			else {
				wret = balance_node_right(trans, root,
1311
							  right, mid);
1312
			}
C
Chris Mason 已提交
1313
		}
1314 1315 1316
		if (wret < 0)
			ret = wret;
		if (wret == 0) {
1317 1318 1319 1320 1321 1322 1323 1324
			struct btrfs_disk_key disk_key;

			btrfs_node_key(right, &disk_key, 0);
			btrfs_set_node_key(parent, &disk_key, pslot + 1);
			btrfs_mark_buffer_dirty(parent);

			if (btrfs_header_nritems(mid) <= orig_slot) {
				path->nodes[level] = right;
1325 1326
				path->slots[level + 1] += 1;
				path->slots[level] = orig_slot -
1327
					btrfs_header_nritems(mid);
1328
				btrfs_tree_unlock(mid);
1329
				free_extent_buffer(mid);
1330
			} else {
1331
				btrfs_tree_unlock(right);
1332
				free_extent_buffer(right);
1333 1334 1335
			}
			return 0;
		}
1336
		btrfs_tree_unlock(right);
1337
		free_extent_buffer(right);
1338 1339 1340 1341
	}
	return 1;
}

1342
/*
C
Chris Mason 已提交
1343 1344
 * readahead one full node of leaves, finding things that are close
 * to the block in 'slot', and triggering ra on them.
1345
 */
1346 1347 1348
static void reada_for_search(struct btrfs_root *root,
			     struct btrfs_path *path,
			     int level, int slot, u64 objectid)
1349
{
1350
	struct extent_buffer *node;
1351
	struct btrfs_disk_key disk_key;
1352 1353
	u32 nritems;
	u64 search;
1354
	u64 target;
1355
	u64 nread = 0;
1356
	int direction = path->reada;
1357
	struct extent_buffer *eb;
1358 1359 1360
	u32 nr;
	u32 blocksize;
	u32 nscan = 0;
1361

1362
	if (level != 1)
1363 1364 1365
		return;

	if (!path->nodes[level])
1366 1367
		return;

1368
	node = path->nodes[level];
1369

1370
	search = btrfs_node_blockptr(node, slot);
1371 1372
	blocksize = btrfs_level_size(root, level - 1);
	eb = btrfs_find_tree_block(root, search, blocksize);
1373 1374
	if (eb) {
		free_extent_buffer(eb);
1375 1376 1377
		return;
	}

1378
	target = search;
1379

1380
	nritems = btrfs_header_nritems(node);
1381
	nr = slot;
C
Chris Mason 已提交
1382
	while (1) {
1383 1384 1385 1386 1387 1388 1389 1390
		if (direction < 0) {
			if (nr == 0)
				break;
			nr--;
		} else if (direction > 0) {
			nr++;
			if (nr >= nritems)
				break;
1391
		}
1392 1393 1394 1395 1396
		if (path->reada < 0 && objectid) {
			btrfs_node_key(node, &disk_key, nr);
			if (btrfs_disk_key_objectid(&disk_key) != objectid)
				break;
		}
1397
		search = btrfs_node_blockptr(node, nr);
1398 1399
		if ((search <= target && target - search <= 65536) ||
		    (search > target && search - target <= 65536)) {
1400 1401
			readahead_tree_block(root, search, blocksize,
				     btrfs_node_ptr_generation(node, nr));
1402 1403 1404
			nread += blocksize;
		}
		nscan++;
1405
		if ((nread > 65536 || nscan > 32))
1406
			break;
1407 1408
	}
}
1409

1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426
/*
 * returns -EAGAIN if it had to drop the path, or zero if everything was in
 * cache
 */
static noinline int reada_for_balance(struct btrfs_root *root,
				      struct btrfs_path *path, int level)
{
	int slot;
	int nritems;
	struct extent_buffer *parent;
	struct extent_buffer *eb;
	u64 gen;
	u64 block1 = 0;
	u64 block2 = 0;
	int ret = 0;
	int blocksize;

1427
	parent = path->nodes[level + 1];
1428 1429 1430 1431
	if (!parent)
		return 0;

	nritems = btrfs_header_nritems(parent);
1432
	slot = path->slots[level + 1];
1433 1434 1435 1436 1437 1438 1439 1440 1441 1442
	blocksize = btrfs_level_size(root, level);

	if (slot > 0) {
		block1 = btrfs_node_blockptr(parent, slot - 1);
		gen = btrfs_node_ptr_generation(parent, slot - 1);
		eb = btrfs_find_tree_block(root, block1, blocksize);
		if (eb && btrfs_buffer_uptodate(eb, gen))
			block1 = 0;
		free_extent_buffer(eb);
	}
1443
	if (slot + 1 < nritems) {
1444 1445 1446 1447 1448 1449 1450 1451 1452
		block2 = btrfs_node_blockptr(parent, slot + 1);
		gen = btrfs_node_ptr_generation(parent, slot + 1);
		eb = btrfs_find_tree_block(root, block2, blocksize);
		if (eb && btrfs_buffer_uptodate(eb, gen))
			block2 = 0;
		free_extent_buffer(eb);
	}
	if (block1 || block2) {
		ret = -EAGAIN;
1453 1454

		/* release the whole path */
1455
		btrfs_release_path(root, path);
1456 1457

		/* read the blocks */
1458 1459 1460 1461 1462 1463 1464 1465 1466
		if (block1)
			readahead_tree_block(root, block1, blocksize, 0);
		if (block2)
			readahead_tree_block(root, block2, blocksize, 0);

		if (block1) {
			eb = read_tree_block(root, block1, blocksize, 0);
			free_extent_buffer(eb);
		}
1467
		if (block2) {
1468 1469 1470 1471 1472 1473 1474 1475
			eb = read_tree_block(root, block2, blocksize, 0);
			free_extent_buffer(eb);
		}
	}
	return ret;
}


C
Chris Mason 已提交
1476
/*
C
Chris Mason 已提交
1477 1478 1479 1480
 * when we walk down the tree, it is usually safe to unlock the higher layers
 * in the tree.  The exceptions are when our path goes through slot 0, because
 * operations on the tree might require changing key pointers higher up in the
 * tree.
C
Chris Mason 已提交
1481
 *
C
Chris Mason 已提交
1482 1483 1484
 * callers might also have set path->keep_locks, which tells this code to keep
 * the lock if the path points to the last slot in the block.  This is part of
 * walking through the tree, and selecting the next slot in the higher block.
C
Chris Mason 已提交
1485
 *
C
Chris Mason 已提交
1486 1487
 * lowest_unlock sets the lowest level in the tree we're allowed to unlock.  so
 * if lowest_unlock is 1, level 0 won't be unlocked
C
Chris Mason 已提交
1488
 */
1489 1490
static noinline void unlock_up(struct btrfs_path *path, int level,
			       int lowest_unlock)
1491 1492 1493
{
	int i;
	int skip_level = level;
1494
	int no_skips = 0;
1495 1496 1497 1498 1499 1500 1501
	struct extent_buffer *t;

	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
		if (!path->nodes[i])
			break;
		if (!path->locks[i])
			break;
1502
		if (!no_skips && path->slots[i] == 0) {
1503 1504 1505
			skip_level = i + 1;
			continue;
		}
1506
		if (!no_skips && path->keep_locks) {
1507 1508 1509
			u32 nritems;
			t = path->nodes[i];
			nritems = btrfs_header_nritems(t);
1510
			if (nritems < 1 || path->slots[i] >= nritems - 1) {
1511 1512 1513 1514
				skip_level = i + 1;
				continue;
			}
		}
1515 1516 1517
		if (skip_level < i && i >= lowest_unlock)
			no_skips = 1;

1518 1519 1520 1521 1522 1523 1524 1525
		t = path->nodes[i];
		if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
			btrfs_tree_unlock(t);
			path->locks[i] = 0;
		}
	}
}

1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538
/*
 * This releases any locks held in the path starting at level and
 * going all the way up to the root.
 *
 * btrfs_search_slot will keep the lock held on higher nodes in a few
 * corner cases, such as COW of the block at slot zero in the node.  This
 * ignores those rules, and it should only be called when there are no
 * more updates to be done higher up in the tree.
 */
noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
{
	int i;

1539
	if (path->keep_locks)
1540 1541 1542 1543
		return;

	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
		if (!path->nodes[i])
1544
			continue;
1545
		if (!path->locks[i])
1546
			continue;
1547 1548 1549 1550 1551
		btrfs_tree_unlock(path->nodes[i]);
		path->locks[i] = 0;
	}
}

1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570
/*
 * helper function for btrfs_search_slot.  The goal is to find a block
 * in cache without setting the path to blocking.  If we find the block
 * we return zero and the path is unchanged.
 *
 * If we can't find the block, we set the path blocking and do some
 * reada.  -EAGAIN is returned and the search must be repeated.
 */
static int
read_block_for_search(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, struct btrfs_path *p,
		       struct extent_buffer **eb_ret, int level, int slot,
		       struct btrfs_key *key)
{
	u64 blocknr;
	u64 gen;
	u32 blocksize;
	struct extent_buffer *b = *eb_ret;
	struct extent_buffer *tmp;
1571
	int ret;
1572 1573 1574 1575 1576 1577 1578

	blocknr = btrfs_node_blockptr(b, slot);
	gen = btrfs_node_ptr_generation(b, slot);
	blocksize = btrfs_level_size(root, level - 1);

	tmp = btrfs_find_tree_block(root, blocknr, blocksize);
	if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
1579 1580 1581 1582
		/*
		 * we found an up to date block without sleeping, return
		 * right away
		 */
1583 1584 1585 1586 1587 1588 1589
		*eb_ret = tmp;
		return 0;
	}

	/*
	 * reduce lock contention at high levels
	 * of the btree by dropping locks before
1590 1591 1592
	 * we read.  Don't release the lock on the current
	 * level because we need to walk this node to figure
	 * out which blocks to read.
1593
	 */
1594 1595 1596
	btrfs_unlock_up_safe(p, level + 1);
	btrfs_set_path_blocking(p);

1597 1598 1599 1600 1601
	if (tmp)
		free_extent_buffer(tmp);
	if (p->reada)
		reada_for_search(root, p, level, slot, key->objectid);

1602
	btrfs_release_path(NULL, p);
1603 1604

	ret = -EAGAIN;
1605
	tmp = read_tree_block(root, blocknr, blocksize, gen);
1606 1607 1608 1609 1610 1611 1612 1613 1614
	if (tmp) {
		/*
		 * If the read above didn't mark this buffer up to date,
		 * it will never end up being up to date.  Set ret to EIO now
		 * and give up so that our caller doesn't loop forever
		 * on our EAGAINs.
		 */
		if (!btrfs_buffer_uptodate(tmp, 0))
			ret = -EIO;
1615
		free_extent_buffer(tmp);
1616 1617
	}
	return ret;
1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653
}

/*
 * helper function for btrfs_search_slot.  This does all of the checks
 * for node-level blocks and does any balancing required based on
 * the ins_len.
 *
 * If no extra work was required, zero is returned.  If we had to
 * drop the path, -EAGAIN is returned and btrfs_search_slot must
 * start over
 */
static int
setup_nodes_for_search(struct btrfs_trans_handle *trans,
		       struct btrfs_root *root, struct btrfs_path *p,
		       struct extent_buffer *b, int level, int ins_len)
{
	int ret;
	if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(b) >=
	    BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
		int sret;

		sret = reada_for_balance(root, p, level);
		if (sret)
			goto again;

		btrfs_set_path_blocking(p);
		sret = split_node(trans, root, p, level);
		btrfs_clear_path_blocking(p, NULL);

		BUG_ON(sret > 0);
		if (sret) {
			ret = sret;
			goto done;
		}
		b = p->nodes[level];
	} else if (ins_len < 0 && btrfs_header_nritems(b) <
C
Chris Mason 已提交
1654
		   BTRFS_NODEPTRS_PER_BLOCK(root) / 2) {
1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683
		int sret;

		sret = reada_for_balance(root, p, level);
		if (sret)
			goto again;

		btrfs_set_path_blocking(p);
		sret = balance_level(trans, root, p, level);
		btrfs_clear_path_blocking(p, NULL);

		if (sret) {
			ret = sret;
			goto done;
		}
		b = p->nodes[level];
		if (!b) {
			btrfs_release_path(NULL, p);
			goto again;
		}
		BUG_ON(btrfs_header_nritems(b) == 1);
	}
	return 0;

again:
	ret = -EAGAIN;
done:
	return ret;
}

C
Chris Mason 已提交
1684 1685 1686 1687 1688 1689
/*
 * look for key in the tree.  path is filled in with nodes along the way
 * if key is found, we return zero and you can find the item in the leaf
 * level of the path (level 0)
 *
 * If the key isn't found, the path points to the slot where it should
C
Chris Mason 已提交
1690 1691
 * be inserted, and 1 is returned.  If there are other errors during the
 * search a negative error number is returned.
C
Chris Mason 已提交
1692 1693 1694 1695
 *
 * if ins_len > 0, nodes and leaves will be split as we walk down the
 * tree.  if ins_len < 0, nodes will be merged as we walk down the tree (if
 * possible)
C
Chris Mason 已提交
1696
 */
1697 1698 1699
int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_key *key, struct btrfs_path *p, int
		      ins_len, int cow)
1700
{
1701
	struct extent_buffer *b;
1702 1703
	int slot;
	int ret;
1704
	int err;
1705
	int level;
1706
	int lowest_unlock = 1;
1707 1708
	u8 lowest_level = 0;

1709
	lowest_level = p->lowest_level;
1710
	WARN_ON(lowest_level && ins_len > 0);
C
Chris Mason 已提交
1711
	WARN_ON(p->nodes[0] != NULL);
1712

1713 1714
	if (ins_len < 0)
		lowest_unlock = 2;
1715

1716
again:
1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727
	if (p->search_commit_root) {
		b = root->commit_root;
		extent_buffer_get(b);
		if (!p->skip_locking)
			btrfs_tree_lock(b);
	} else {
		if (p->skip_locking)
			b = btrfs_root_node(root);
		else
			b = btrfs_lock_root_node(root);
	}
1728

1729
	while (b) {
1730
		level = btrfs_header_level(b);
1731 1732 1733 1734 1735 1736 1737 1738 1739

		/*
		 * setup the path here so we can release it under lock
		 * contention with the cow code
		 */
		p->nodes[level] = b;
		if (!p->skip_locking)
			p->locks[level] = 1;

C
Chris Mason 已提交
1740
		if (cow) {
1741 1742 1743 1744 1745
			/*
			 * if we don't really need to cow this block
			 * then we don't want to set the path blocking,
			 * so we test it here
			 */
1746
			if (!should_cow_block(trans, root, b))
1747
				goto cow_done;
1748

1749 1750
			btrfs_set_path_blocking(p);

1751 1752 1753 1754
			err = btrfs_cow_block(trans, root, b,
					      p->nodes[level + 1],
					      p->slots[level + 1], &b);
			if (err) {
1755
				free_extent_buffer(b);
1756
				ret = err;
1757
				goto done;
1758
			}
C
Chris Mason 已提交
1759
		}
1760
cow_done:
C
Chris Mason 已提交
1761
		BUG_ON(!cow && ins_len);
1762
		if (level != btrfs_header_level(b))
C
Chris Mason 已提交
1763
			WARN_ON(1);
1764
		level = btrfs_header_level(b);
1765

1766
		p->nodes[level] = b;
1767 1768
		if (!p->skip_locking)
			p->locks[level] = 1;
1769

1770
		btrfs_clear_path_blocking(p, NULL);
1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 1784 1785

		/*
		 * we have a lock on b and as long as we aren't changing
		 * the tree, there is no way to for the items in b to change.
		 * It is safe to drop the lock on our parent before we
		 * go through the expensive btree search on b.
		 *
		 * If cow is true, then we might be changing slot zero,
		 * which may require changing the parent.  So, we can't
		 * drop the lock until after we know which slot we're
		 * operating on.
		 */
		if (!cow)
			btrfs_unlock_up_safe(p, level + 1);

C
Chris Mason 已提交
1786
		ret = check_block(root, p, level);
1787 1788 1789 1790
		if (ret) {
			ret = -1;
			goto done;
		}
1791

1792
		ret = bin_search(b, key, level, &slot);
1793

1794
		if (level != 0) {
1795 1796 1797
			int dec = 0;
			if (ret && slot > 0) {
				dec = 1;
1798
				slot -= 1;
1799
			}
1800
			p->slots[level] = slot;
1801
			err = setup_nodes_for_search(trans, root, p, b, level,
1802
						     ins_len);
1803
			if (err == -EAGAIN)
1804
				goto again;
1805 1806
			if (err) {
				ret = err;
1807
				goto done;
1808
			}
1809 1810
			b = p->nodes[level];
			slot = p->slots[level];
1811

1812 1813
			unlock_up(p, level, lowest_unlock);

1814
			if (level == lowest_level) {
1815 1816
				if (dec)
					p->slots[level]++;
1817
				goto done;
1818
			}
1819

1820
			err = read_block_for_search(trans, root, p,
1821
						    &b, level, slot, key);
1822
			if (err == -EAGAIN)
1823
				goto again;
1824 1825
			if (err) {
				ret = err;
1826
				goto done;
1827
			}
1828

1829
			if (!p->skip_locking) {
1830
				btrfs_clear_path_blocking(p, NULL);
1831
				err = btrfs_try_spin_lock(b);
1832

1833
				if (!err) {
1834 1835
					btrfs_set_path_blocking(p);
					btrfs_tree_lock(b);
1836
					btrfs_clear_path_blocking(p, b);
1837 1838
				}
			}
1839 1840
		} else {
			p->slots[level] = slot;
1841 1842
			if (ins_len > 0 &&
			    btrfs_leaf_free_space(root, b) < ins_len) {
1843
				btrfs_set_path_blocking(p);
1844 1845
				err = split_leaf(trans, root, key,
						 p, ins_len, ret == 0);
1846
				btrfs_clear_path_blocking(p, NULL);
1847

1848 1849 1850
				BUG_ON(err > 0);
				if (err) {
					ret = err;
1851 1852
					goto done;
				}
C
Chris Mason 已提交
1853
			}
1854 1855
			if (!p->search_for_split)
				unlock_up(p, level, lowest_unlock);
1856
			goto done;
1857 1858
		}
	}
1859 1860
	ret = 1;
done:
1861 1862 1863 1864
	/*
	 * we don't really know what they plan on doing with the path
	 * from here on, so for now just mark it as blocking
	 */
1865 1866
	if (!p->leave_spinning)
		btrfs_set_path_blocking(p);
1867 1868
	if (ret < 0)
		btrfs_release_path(root, p);
1869
	return ret;
1870 1871
}

C
Chris Mason 已提交
1872 1873 1874 1875 1876 1877
/*
 * adjust the pointers going up the tree, starting at level
 * making sure the right key of each node is points to 'key'.
 * This is used after shifting pointers to the left, so it stops
 * fixing up pointers when a given leaf/node is not in slot 0 of the
 * higher levels
C
Chris Mason 已提交
1878 1879 1880
 *
 * If this fails to write a tree block, it returns -1, but continues
 * fixing up the blocks in ram so the tree is consistent.
C
Chris Mason 已提交
1881
 */
1882 1883 1884
static int fixup_low_keys(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct btrfs_path *path,
			  struct btrfs_disk_key *key, int level)
1885 1886
{
	int i;
C
Chris Mason 已提交
1887
	int ret = 0;
1888 1889
	struct extent_buffer *t;

C
Chris Mason 已提交
1890
	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1891
		int tslot = path->slots[i];
1892
		if (!path->nodes[i])
1893
			break;
1894 1895
		t = path->nodes[i];
		btrfs_set_node_key(t, key, tslot);
C
Chris Mason 已提交
1896
		btrfs_mark_buffer_dirty(path->nodes[i]);
1897 1898 1899
		if (tslot != 0)
			break;
	}
C
Chris Mason 已提交
1900
	return ret;
1901 1902
}

Z
Zheng Yan 已提交
1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937
/*
 * update item key.
 *
 * This function isn't completely safe. It's the caller's responsibility
 * that the new key won't break the order
 */
int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root, struct btrfs_path *path,
			    struct btrfs_key *new_key)
{
	struct btrfs_disk_key disk_key;
	struct extent_buffer *eb;
	int slot;

	eb = path->nodes[0];
	slot = path->slots[0];
	if (slot > 0) {
		btrfs_item_key(eb, &disk_key, slot - 1);
		if (comp_keys(&disk_key, new_key) >= 0)
			return -1;
	}
	if (slot < btrfs_header_nritems(eb) - 1) {
		btrfs_item_key(eb, &disk_key, slot + 1);
		if (comp_keys(&disk_key, new_key) <= 0)
			return -1;
	}

	btrfs_cpu_key_to_disk(&disk_key, new_key);
	btrfs_set_item_key(eb, &disk_key, slot);
	btrfs_mark_buffer_dirty(eb);
	if (slot == 0)
		fixup_low_keys(trans, root, path, &disk_key, 1);
	return 0;
}

C
Chris Mason 已提交
1938 1939
/*
 * try to push data from one node into the next node left in the
1940
 * tree.
C
Chris Mason 已提交
1941 1942 1943
 *
 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
 * error, and > 0 if there was no room in the left hand block.
C
Chris Mason 已提交
1944
 */
1945 1946
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct extent_buffer *dst,
1947
			  struct extent_buffer *src, int empty)
1948 1949
{
	int push_items = 0;
1950 1951
	int src_nritems;
	int dst_nritems;
C
Chris Mason 已提交
1952
	int ret = 0;
1953

1954 1955
	src_nritems = btrfs_header_nritems(src);
	dst_nritems = btrfs_header_nritems(dst);
C
Chris Mason 已提交
1956
	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1957 1958
	WARN_ON(btrfs_header_generation(src) != trans->transid);
	WARN_ON(btrfs_header_generation(dst) != trans->transid);
1959

1960
	if (!empty && src_nritems <= 8)
1961 1962
		return 1;

C
Chris Mason 已提交
1963
	if (push_items <= 0)
1964 1965
		return 1;

1966
	if (empty) {
1967
		push_items = min(src_nritems, push_items);
1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979
		if (push_items < src_nritems) {
			/* leave at least 8 pointers in the node if
			 * we aren't going to empty it
			 */
			if (src_nritems - push_items < 8) {
				if (push_items <= 8)
					return 1;
				push_items -= 8;
			}
		}
	} else
		push_items = min(src_nritems - 8, push_items);
1980

1981 1982 1983
	copy_extent_buffer(dst, src,
			   btrfs_node_key_ptr_offset(dst_nritems),
			   btrfs_node_key_ptr_offset(0),
C
Chris Mason 已提交
1984
			   push_items * sizeof(struct btrfs_key_ptr));
1985

1986
	if (push_items < src_nritems) {
1987 1988 1989 1990 1991 1992 1993 1994 1995
		memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
				      btrfs_node_key_ptr_offset(push_items),
				      (src_nritems - push_items) *
				      sizeof(struct btrfs_key_ptr));
	}
	btrfs_set_header_nritems(src, src_nritems - push_items);
	btrfs_set_header_nritems(dst, dst_nritems + push_items);
	btrfs_mark_buffer_dirty(src);
	btrfs_mark_buffer_dirty(dst);
Z
Zheng Yan 已提交
1996

1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008
	return ret;
}

/*
 * try to push data from one node into the next node right in the
 * tree.
 *
 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
 * error, and > 0 if there was no room in the right hand block.
 *
 * this will  only push up to 1/2 the contents of the left node over
 */
2009 2010 2011 2012
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
			      struct extent_buffer *dst,
			      struct extent_buffer *src)
2013 2014 2015 2016 2017 2018 2019
{
	int push_items = 0;
	int max_push;
	int src_nritems;
	int dst_nritems;
	int ret = 0;

2020 2021 2022
	WARN_ON(btrfs_header_generation(src) != trans->transid);
	WARN_ON(btrfs_header_generation(dst) != trans->transid);

2023 2024
	src_nritems = btrfs_header_nritems(src);
	dst_nritems = btrfs_header_nritems(dst);
C
Chris Mason 已提交
2025
	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
C
Chris Mason 已提交
2026
	if (push_items <= 0)
2027
		return 1;
2028

C
Chris Mason 已提交
2029
	if (src_nritems < 4)
2030
		return 1;
2031 2032 2033

	max_push = src_nritems / 2 + 1;
	/* don't try to empty the node */
C
Chris Mason 已提交
2034
	if (max_push >= src_nritems)
2035
		return 1;
Y
Yan 已提交
2036

2037 2038 2039
	if (max_push < push_items)
		push_items = max_push;

2040 2041 2042 2043
	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
				      btrfs_node_key_ptr_offset(0),
				      (dst_nritems) *
				      sizeof(struct btrfs_key_ptr));
C
Chris Mason 已提交
2044

2045 2046 2047
	copy_extent_buffer(dst, src,
			   btrfs_node_key_ptr_offset(0),
			   btrfs_node_key_ptr_offset(src_nritems - push_items),
C
Chris Mason 已提交
2048
			   push_items * sizeof(struct btrfs_key_ptr));
2049

2050 2051
	btrfs_set_header_nritems(src, src_nritems - push_items);
	btrfs_set_header_nritems(dst, dst_nritems + push_items);
2052

2053 2054
	btrfs_mark_buffer_dirty(src);
	btrfs_mark_buffer_dirty(dst);
Z
Zheng Yan 已提交
2055

C
Chris Mason 已提交
2056
	return ret;
2057 2058
}

C
Chris Mason 已提交
2059 2060 2061 2062
/*
 * helper function to insert a new root level in the tree.
 * A new node is allocated, and a single item is inserted to
 * point to the existing root
C
Chris Mason 已提交
2063 2064
 *
 * returns zero on success or < 0 on failure.
C
Chris Mason 已提交
2065
 */
C
Chris Mason 已提交
2066
static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2067 2068
			   struct btrfs_root *root,
			   struct btrfs_path *path, int level)
C
Chris Mason 已提交
2069
{
2070
	u64 lower_gen;
2071 2072
	struct extent_buffer *lower;
	struct extent_buffer *c;
2073
	struct extent_buffer *old;
2074
	struct btrfs_disk_key lower_key;
C
Chris Mason 已提交
2075 2076 2077 2078

	BUG_ON(path->nodes[level]);
	BUG_ON(path->nodes[level-1] != root->node);

2079 2080 2081 2082 2083 2084
	lower = path->nodes[level-1];
	if (level == 1)
		btrfs_item_key(lower, &lower_key, 0);
	else
		btrfs_node_key(lower, &lower_key, 0);

Z
Zheng Yan 已提交
2085
	c = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
2086
				   root->root_key.objectid, &lower_key,
2087
				   level, root->node->start, 0);
2088 2089
	if (IS_ERR(c))
		return PTR_ERR(c);
2090

2091
	memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
2092 2093
	btrfs_set_header_nritems(c, 1);
	btrfs_set_header_level(c, level);
2094
	btrfs_set_header_bytenr(c, c->start);
2095
	btrfs_set_header_generation(c, trans->transid);
2096
	btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
2097 2098 2099 2100 2101
	btrfs_set_header_owner(c, root->root_key.objectid);

	write_extent_buffer(c, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(c),
			    BTRFS_FSID_SIZE);
2102 2103 2104 2105 2106

	write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
			    (unsigned long)btrfs_header_chunk_tree_uuid(c),
			    BTRFS_UUID_SIZE);

2107
	btrfs_set_node_key(c, &lower_key, 0);
2108
	btrfs_set_node_blockptr(c, 0, lower->start);
2109
	lower_gen = btrfs_header_generation(lower);
Z
Zheng Yan 已提交
2110
	WARN_ON(lower_gen != trans->transid);
2111 2112

	btrfs_set_node_ptr_generation(c, 0, lower_gen);
2113

2114
	btrfs_mark_buffer_dirty(c);
2115

2116 2117
	spin_lock(&root->node_lock);
	old = root->node;
2118
	root->node = c;
2119 2120 2121 2122 2123
	spin_unlock(&root->node_lock);

	/* the super has an extra ref to root->node */
	free_extent_buffer(old);

2124
	add_root_to_dirty_list(root);
2125 2126
	extent_buffer_get(c);
	path->nodes[level] = c;
2127
	path->locks[level] = 1;
C
Chris Mason 已提交
2128 2129 2130 2131
	path->slots[level] = 0;
	return 0;
}

C
Chris Mason 已提交
2132 2133 2134
/*
 * worker function to insert a single pointer in a node.
 * the node should have enough room for the pointer already
C
Chris Mason 已提交
2135
 *
C
Chris Mason 已提交
2136 2137
 * slot and level indicate where you want the key to go, and
 * blocknr is the block the key points to.
C
Chris Mason 已提交
2138 2139
 *
 * returns zero on success and < 0 on any error
C
Chris Mason 已提交
2140
 */
2141 2142
static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_path *path, struct btrfs_disk_key
2143
		      *key, u64 bytenr, int slot, int level)
C
Chris Mason 已提交
2144
{
2145
	struct extent_buffer *lower;
C
Chris Mason 已提交
2146
	int nritems;
C
Chris Mason 已提交
2147 2148

	BUG_ON(!path->nodes[level]);
2149 2150
	lower = path->nodes[level];
	nritems = btrfs_header_nritems(lower);
S
Stoyan Gaydarov 已提交
2151
	BUG_ON(slot > nritems);
C
Chris Mason 已提交
2152
	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
C
Chris Mason 已提交
2153 2154
		BUG();
	if (slot != nritems) {
2155 2156 2157
		memmove_extent_buffer(lower,
			      btrfs_node_key_ptr_offset(slot + 1),
			      btrfs_node_key_ptr_offset(slot),
C
Chris Mason 已提交
2158
			      (nritems - slot) * sizeof(struct btrfs_key_ptr));
C
Chris Mason 已提交
2159
	}
2160
	btrfs_set_node_key(lower, key, slot);
2161
	btrfs_set_node_blockptr(lower, slot, bytenr);
2162 2163
	WARN_ON(trans->transid == 0);
	btrfs_set_node_ptr_generation(lower, slot, trans->transid);
2164 2165
	btrfs_set_header_nritems(lower, nritems + 1);
	btrfs_mark_buffer_dirty(lower);
C
Chris Mason 已提交
2166 2167 2168
	return 0;
}

C
Chris Mason 已提交
2169 2170 2171 2172 2173 2174
/*
 * split the node at the specified level in path in two.
 * The path is corrected to point to the appropriate node after the split
 *
 * Before splitting this tries to make some room in the node by pushing
 * left and right, if either one works, it returns right away.
C
Chris Mason 已提交
2175 2176
 *
 * returns 0 on success and < 0 on failure
C
Chris Mason 已提交
2177
 */
2178 2179 2180
static noinline int split_node(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct btrfs_path *path, int level)
2181
{
2182 2183 2184
	struct extent_buffer *c;
	struct extent_buffer *split;
	struct btrfs_disk_key disk_key;
2185
	int mid;
C
Chris Mason 已提交
2186
	int ret;
C
Chris Mason 已提交
2187
	int wret;
2188
	u32 c_nritems;
2189

2190
	c = path->nodes[level];
2191
	WARN_ON(btrfs_header_generation(c) != trans->transid);
2192
	if (c == root->node) {
C
Chris Mason 已提交
2193
		/* trying to split the root, lets make a new one */
2194
		ret = insert_new_root(trans, root, path, level + 1);
C
Chris Mason 已提交
2195 2196
		if (ret)
			return ret;
2197
	} else {
2198
		ret = push_nodes_for_insert(trans, root, path, level);
2199 2200
		c = path->nodes[level];
		if (!ret && btrfs_header_nritems(c) <
2201
		    BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
2202
			return 0;
2203 2204
		if (ret < 0)
			return ret;
2205
	}
2206

2207
	c_nritems = btrfs_header_nritems(c);
2208 2209
	mid = (c_nritems + 1) / 2;
	btrfs_node_key(c, &disk_key, mid);
2210

2211
	split = btrfs_alloc_free_block(trans, root, root->nodesize, 0,
Z
Zheng Yan 已提交
2212
					root->root_key.objectid,
2213
					&disk_key, level, c->start, 0);
2214 2215 2216
	if (IS_ERR(split))
		return PTR_ERR(split);

2217
	memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
2218
	btrfs_set_header_level(split, btrfs_header_level(c));
2219
	btrfs_set_header_bytenr(split, split->start);
2220
	btrfs_set_header_generation(split, trans->transid);
2221
	btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
2222 2223 2224 2225
	btrfs_set_header_owner(split, root->root_key.objectid);
	write_extent_buffer(split, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(split),
			    BTRFS_FSID_SIZE);
2226 2227 2228
	write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
			    (unsigned long)btrfs_header_chunk_tree_uuid(split),
			    BTRFS_UUID_SIZE);
2229

2230 2231 2232 2233 2234 2235 2236

	copy_extent_buffer(split, c,
			   btrfs_node_key_ptr_offset(0),
			   btrfs_node_key_ptr_offset(mid),
			   (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
	btrfs_set_header_nritems(split, c_nritems - mid);
	btrfs_set_header_nritems(c, mid);
C
Chris Mason 已提交
2237 2238
	ret = 0;

2239 2240 2241
	btrfs_mark_buffer_dirty(c);
	btrfs_mark_buffer_dirty(split);

2242
	wret = insert_ptr(trans, root, path, &disk_key, split->start,
2243
			  path->slots[level + 1] + 1,
C
Chris Mason 已提交
2244
			  level + 1);
C
Chris Mason 已提交
2245 2246 2247
	if (wret)
		ret = wret;

C
Chris Mason 已提交
2248
	if (path->slots[level] >= mid) {
C
Chris Mason 已提交
2249
		path->slots[level] -= mid;
2250
		btrfs_tree_unlock(c);
2251 2252
		free_extent_buffer(c);
		path->nodes[level] = split;
C
Chris Mason 已提交
2253 2254
		path->slots[level + 1] += 1;
	} else {
2255
		btrfs_tree_unlock(split);
2256
		free_extent_buffer(split);
2257
	}
C
Chris Mason 已提交
2258
	return ret;
2259 2260
}

C
Chris Mason 已提交
2261 2262 2263 2264 2265
/*
 * how many bytes are required to store the items in a leaf.  start
 * and nr indicate which items in the leaf to check.  This totals up the
 * space used both by the item structs and the item data
 */
2266
static int leaf_space_used(struct extent_buffer *l, int start, int nr)
2267 2268
{
	int data_len;
2269
	int nritems = btrfs_header_nritems(l);
2270
	int end = min(nritems, start + nr) - 1;
2271 2272 2273

	if (!nr)
		return 0;
2274 2275
	data_len = btrfs_item_end_nr(l, start);
	data_len = data_len - btrfs_item_offset_nr(l, end);
C
Chris Mason 已提交
2276
	data_len += sizeof(struct btrfs_item) * nr;
2277
	WARN_ON(data_len < 0);
2278 2279 2280
	return data_len;
}

2281 2282 2283 2284 2285
/*
 * The space between the end of the leaf items and
 * the start of the leaf data.  IOW, how much room
 * the leaf has left for both items and data
 */
C
Chris Mason 已提交
2286
noinline int btrfs_leaf_free_space(struct btrfs_root *root,
2287
				   struct extent_buffer *leaf)
2288
{
2289 2290 2291 2292
	int nritems = btrfs_header_nritems(leaf);
	int ret;
	ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
	if (ret < 0) {
C
Chris Mason 已提交
2293 2294
		printk(KERN_CRIT "leaf free space ret %d, leaf data size %lu, "
		       "used %d nritems %d\n",
J
Jens Axboe 已提交
2295
		       ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
2296 2297 2298
		       leaf_space_used(leaf, 0, nritems), nritems);
	}
	return ret;
2299 2300
}

2301 2302 2303 2304 2305 2306
static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
				      struct btrfs_root *root,
				      struct btrfs_path *path,
				      int data_size, int empty,
				      struct extent_buffer *right,
				      int free_space, u32 left_nritems)
C
Chris Mason 已提交
2307
{
2308
	struct extent_buffer *left = path->nodes[0];
2309
	struct extent_buffer *upper = path->nodes[1];
2310
	struct btrfs_disk_key disk_key;
C
Chris Mason 已提交
2311
	int slot;
2312
	u32 i;
C
Chris Mason 已提交
2313 2314
	int push_space = 0;
	int push_items = 0;
C
Chris Mason 已提交
2315
	struct btrfs_item *item;
2316
	u32 nr;
2317
	u32 right_nritems;
2318
	u32 data_end;
2319
	u32 this_item_size;
C
Chris Mason 已提交
2320

2321 2322 2323 2324 2325
	if (empty)
		nr = 0;
	else
		nr = 1;

Z
Zheng Yan 已提交
2326
	if (path->slots[0] >= left_nritems)
2327
		push_space += data_size;
Z
Zheng Yan 已提交
2328

2329
	slot = path->slots[1];
2330 2331
	i = left_nritems - 1;
	while (i >= nr) {
2332
		item = btrfs_item_nr(left, i);
2333

Z
Zheng Yan 已提交
2334 2335 2336 2337 2338 2339 2340 2341 2342 2343
		if (!empty && push_items > 0) {
			if (path->slots[0] > i)
				break;
			if (path->slots[0] == i) {
				int space = btrfs_leaf_free_space(root, left);
				if (space + push_space * 2 > free_space)
					break;
			}
		}

C
Chris Mason 已提交
2344
		if (path->slots[0] == i)
2345
			push_space += data_size;
2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356

		if (!left->map_token) {
			map_extent_buffer(left, (unsigned long)item,
					sizeof(struct btrfs_item),
					&left->map_token, &left->kaddr,
					&left->map_start, &left->map_len,
					KM_USER1);
		}

		this_item_size = btrfs_item_size(left, item);
		if (this_item_size + sizeof(*item) + push_space > free_space)
C
Chris Mason 已提交
2357
			break;
Z
Zheng Yan 已提交
2358

C
Chris Mason 已提交
2359
		push_items++;
2360
		push_space += this_item_size + sizeof(*item);
2361 2362 2363
		if (i == 0)
			break;
		i--;
2364 2365 2366 2367
	}
	if (left->map_token) {
		unmap_extent_buffer(left, left->map_token, KM_USER1);
		left->map_token = NULL;
C
Chris Mason 已提交
2368
	}
2369

2370 2371
	if (push_items == 0)
		goto out_unlock;
2372

2373
	if (!empty && push_items == left_nritems)
2374
		WARN_ON(1);
2375

C
Chris Mason 已提交
2376
	/* push left to right */
2377
	right_nritems = btrfs_header_nritems(right);
2378

2379
	push_space = btrfs_item_end_nr(left, left_nritems - push_items);
C
Chris Mason 已提交
2380
	push_space -= leaf_data_end(root, left);
2381

C
Chris Mason 已提交
2382
	/* make room in the right data area */
2383 2384 2385 2386 2387 2388
	data_end = leaf_data_end(root, right);
	memmove_extent_buffer(right,
			      btrfs_leaf_data(right) + data_end - push_space,
			      btrfs_leaf_data(right) + data_end,
			      BTRFS_LEAF_DATA_SIZE(root) - data_end);

C
Chris Mason 已提交
2389
	/* copy from the left data area */
2390
	copy_extent_buffer(right, left, btrfs_leaf_data(right) +
C
Chris Mason 已提交
2391 2392 2393
		     BTRFS_LEAF_DATA_SIZE(root) - push_space,
		     btrfs_leaf_data(left) + leaf_data_end(root, left),
		     push_space);
2394 2395 2396 2397 2398

	memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
			      btrfs_item_nr_offset(0),
			      right_nritems * sizeof(struct btrfs_item));

C
Chris Mason 已提交
2399
	/* copy the items from left to right */
2400 2401 2402
	copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
		   btrfs_item_nr_offset(left_nritems - push_items),
		   push_items * sizeof(struct btrfs_item));
C
Chris Mason 已提交
2403 2404

	/* update the item pointers */
2405
	right_nritems += push_items;
2406
	btrfs_set_header_nritems(right, right_nritems);
C
Chris Mason 已提交
2407
	push_space = BTRFS_LEAF_DATA_SIZE(root);
2408
	for (i = 0; i < right_nritems; i++) {
2409
		item = btrfs_item_nr(right, i);
2410 2411 2412 2413 2414 2415 2416 2417 2418 2419 2420 2421 2422 2423
		if (!right->map_token) {
			map_extent_buffer(right, (unsigned long)item,
					sizeof(struct btrfs_item),
					&right->map_token, &right->kaddr,
					&right->map_start, &right->map_len,
					KM_USER1);
		}
		push_space -= btrfs_item_size(right, item);
		btrfs_set_item_offset(right, item, push_space);
	}

	if (right->map_token) {
		unmap_extent_buffer(right, right->map_token, KM_USER1);
		right->map_token = NULL;
C
Chris Mason 已提交
2424
	}
2425
	left_nritems -= push_items;
2426
	btrfs_set_header_nritems(left, left_nritems);
C
Chris Mason 已提交
2427

2428 2429
	if (left_nritems)
		btrfs_mark_buffer_dirty(left);
2430
	btrfs_mark_buffer_dirty(right);
2431

2432 2433
	btrfs_item_key(right, &disk_key, 0);
	btrfs_set_node_key(upper, &disk_key, slot + 1);
C
Chris Mason 已提交
2434
	btrfs_mark_buffer_dirty(upper);
C
Chris Mason 已提交
2435

C
Chris Mason 已提交
2436
	/* then fixup the leaf pointer in the path */
2437 2438
	if (path->slots[0] >= left_nritems) {
		path->slots[0] -= left_nritems;
2439 2440 2441
		if (btrfs_header_nritems(path->nodes[0]) == 0)
			clean_tree_block(trans, root, path->nodes[0]);
		btrfs_tree_unlock(path->nodes[0]);
2442 2443
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = right;
C
Chris Mason 已提交
2444 2445
		path->slots[1] += 1;
	} else {
2446
		btrfs_tree_unlock(right);
2447
		free_extent_buffer(right);
C
Chris Mason 已提交
2448 2449
	}
	return 0;
2450 2451 2452 2453 2454

out_unlock:
	btrfs_tree_unlock(right);
	free_extent_buffer(right);
	return 1;
C
Chris Mason 已提交
2455
}
2456

2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515
/*
 * push some data in the path leaf to the right, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 *
 * returns 1 if the push failed because the other node didn't have enough
 * room, 0 if everything worked out and < 0 if there were major errors.
 */
static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
			   *root, struct btrfs_path *path, int data_size,
			   int empty)
{
	struct extent_buffer *left = path->nodes[0];
	struct extent_buffer *right;
	struct extent_buffer *upper;
	int slot;
	int free_space;
	u32 left_nritems;
	int ret;

	if (!path->nodes[1])
		return 1;

	slot = path->slots[1];
	upper = path->nodes[1];
	if (slot >= btrfs_header_nritems(upper) - 1)
		return 1;

	btrfs_assert_tree_locked(path->nodes[1]);

	right = read_node_slot(root, upper, slot + 1);
	btrfs_tree_lock(right);
	btrfs_set_lock_blocking(right);

	free_space = btrfs_leaf_free_space(root, right);
	if (free_space < data_size)
		goto out_unlock;

	/* cow and double check */
	ret = btrfs_cow_block(trans, root, right, upper,
			      slot + 1, &right);
	if (ret)
		goto out_unlock;

	free_space = btrfs_leaf_free_space(root, right);
	if (free_space < data_size)
		goto out_unlock;

	left_nritems = btrfs_header_nritems(left);
	if (left_nritems == 0)
		goto out_unlock;

	return __push_leaf_right(trans, root, path, data_size, empty,
				right, free_space, left_nritems);
out_unlock:
	btrfs_tree_unlock(right);
	free_extent_buffer(right);
	return 1;
}

C
Chris Mason 已提交
2516 2517 2518 2519
/*
 * push some data in the path leaf to the left, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 */
2520 2521 2522 2523 2524
static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
				     struct btrfs_root *root,
				     struct btrfs_path *path, int data_size,
				     int empty, struct extent_buffer *left,
				     int free_space, int right_nritems)
2525
{
2526 2527
	struct btrfs_disk_key disk_key;
	struct extent_buffer *right = path->nodes[0];
2528 2529 2530 2531
	int slot;
	int i;
	int push_space = 0;
	int push_items = 0;
C
Chris Mason 已提交
2532
	struct btrfs_item *item;
2533
	u32 old_left_nritems;
2534
	u32 nr;
C
Chris Mason 已提交
2535 2536
	int ret = 0;
	int wret;
2537 2538
	u32 this_item_size;
	u32 old_left_item_size;
2539 2540

	slot = path->slots[1];
C
Chris Mason 已提交
2541

2542 2543 2544 2545 2546 2547
	if (empty)
		nr = right_nritems;
	else
		nr = right_nritems - 1;

	for (i = 0; i < nr; i++) {
2548
		item = btrfs_item_nr(right, i);
2549 2550 2551 2552 2553 2554 2555 2556
		if (!right->map_token) {
			map_extent_buffer(right, (unsigned long)item,
					sizeof(struct btrfs_item),
					&right->map_token, &right->kaddr,
					&right->map_start, &right->map_len,
					KM_USER1);
		}

Z
Zheng Yan 已提交
2557 2558 2559 2560 2561 2562 2563 2564 2565 2566
		if (!empty && push_items > 0) {
			if (path->slots[0] < i)
				break;
			if (path->slots[0] == i) {
				int space = btrfs_leaf_free_space(root, right);
				if (space + push_space * 2 > free_space)
					break;
			}
		}

2567
		if (path->slots[0] == i)
2568
			push_space += data_size;
2569 2570 2571

		this_item_size = btrfs_item_size(right, item);
		if (this_item_size + sizeof(*item) + push_space > free_space)
2572
			break;
2573

2574
		push_items++;
2575 2576 2577 2578 2579 2580
		push_space += this_item_size + sizeof(*item);
	}

	if (right->map_token) {
		unmap_extent_buffer(right, right->map_token, KM_USER1);
		right->map_token = NULL;
2581
	}
2582

2583
	if (push_items == 0) {
2584 2585
		ret = 1;
		goto out;
2586
	}
2587
	if (!empty && push_items == btrfs_header_nritems(right))
2588
		WARN_ON(1);
2589

2590
	/* push data from right to left */
2591 2592 2593 2594 2595
	copy_extent_buffer(left, right,
			   btrfs_item_nr_offset(btrfs_header_nritems(left)),
			   btrfs_item_nr_offset(0),
			   push_items * sizeof(struct btrfs_item));

C
Chris Mason 已提交
2596
	push_space = BTRFS_LEAF_DATA_SIZE(root) -
C
Chris Mason 已提交
2597
		     btrfs_item_offset_nr(right, push_items - 1);
2598 2599

	copy_extent_buffer(left, right, btrfs_leaf_data(left) +
C
Chris Mason 已提交
2600 2601
		     leaf_data_end(root, left) - push_space,
		     btrfs_leaf_data(right) +
2602
		     btrfs_item_offset_nr(right, push_items - 1),
C
Chris Mason 已提交
2603
		     push_space);
2604
	old_left_nritems = btrfs_header_nritems(left);
2605
	BUG_ON(old_left_nritems <= 0);
2606

2607
	old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
C
Chris Mason 已提交
2608
	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
2609
		u32 ioff;
2610

2611
		item = btrfs_item_nr(left, i);
2612 2613 2614 2615 2616 2617 2618 2619
		if (!left->map_token) {
			map_extent_buffer(left, (unsigned long)item,
					sizeof(struct btrfs_item),
					&left->map_token, &left->kaddr,
					&left->map_start, &left->map_len,
					KM_USER1);
		}

2620 2621
		ioff = btrfs_item_offset(left, item);
		btrfs_set_item_offset(left, item,
2622
		      ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2623
	}
2624
	btrfs_set_header_nritems(left, old_left_nritems + push_items);
2625 2626 2627 2628
	if (left->map_token) {
		unmap_extent_buffer(left, left->map_token, KM_USER1);
		left->map_token = NULL;
	}
2629 2630

	/* fixup right node */
2631
	if (push_items > right_nritems) {
C
Chris Mason 已提交
2632 2633
		printk(KERN_CRIT "push items %d nr %u\n", push_items,
		       right_nritems);
2634 2635 2636 2637 2638 2639 2640 2641 2642 2643 2644 2645
		WARN_ON(1);
	}

	if (push_items < right_nritems) {
		push_space = btrfs_item_offset_nr(right, push_items - 1) -
						  leaf_data_end(root, right);
		memmove_extent_buffer(right, btrfs_leaf_data(right) +
				      BTRFS_LEAF_DATA_SIZE(root) - push_space,
				      btrfs_leaf_data(right) +
				      leaf_data_end(root, right), push_space);

		memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2646 2647 2648
			      btrfs_item_nr_offset(push_items),
			     (btrfs_header_nritems(right) - push_items) *
			     sizeof(struct btrfs_item));
2649
	}
2650 2651
	right_nritems -= push_items;
	btrfs_set_header_nritems(right, right_nritems);
C
Chris Mason 已提交
2652
	push_space = BTRFS_LEAF_DATA_SIZE(root);
2653 2654
	for (i = 0; i < right_nritems; i++) {
		item = btrfs_item_nr(right, i);
2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669

		if (!right->map_token) {
			map_extent_buffer(right, (unsigned long)item,
					sizeof(struct btrfs_item),
					&right->map_token, &right->kaddr,
					&right->map_start, &right->map_len,
					KM_USER1);
		}

		push_space = push_space - btrfs_item_size(right, item);
		btrfs_set_item_offset(right, item, push_space);
	}
	if (right->map_token) {
		unmap_extent_buffer(right, right->map_token, KM_USER1);
		right->map_token = NULL;
2670
	}
2671

2672
	btrfs_mark_buffer_dirty(left);
2673 2674
	if (right_nritems)
		btrfs_mark_buffer_dirty(right);
2675

2676 2677
	btrfs_item_key(right, &disk_key, 0);
	wret = fixup_low_keys(trans, root, path, &disk_key, 1);
C
Chris Mason 已提交
2678 2679
	if (wret)
		ret = wret;
2680 2681 2682 2683

	/* then fixup the leaf pointer in the path */
	if (path->slots[0] < push_items) {
		path->slots[0] += old_left_nritems;
2684 2685 2686
		if (btrfs_header_nritems(path->nodes[0]) == 0)
			clean_tree_block(trans, root, path->nodes[0]);
		btrfs_tree_unlock(path->nodes[0]);
2687 2688
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = left;
2689 2690
		path->slots[1] -= 1;
	} else {
2691
		btrfs_tree_unlock(left);
2692
		free_extent_buffer(left);
2693 2694
		path->slots[0] -= push_items;
	}
2695
	BUG_ON(path->slots[0] < 0);
C
Chris Mason 已提交
2696
	return ret;
2697 2698 2699 2700
out:
	btrfs_tree_unlock(left);
	free_extent_buffer(left);
	return ret;
2701 2702
}

2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795 2796 2797 2798 2799 2800 2801 2802 2803 2804 2805 2806 2807 2808 2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847
/*
 * push some data in the path leaf to the left, trying to free up at
 * least data_size bytes.  returns zero if the push worked, nonzero otherwise
 */
static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
			  *root, struct btrfs_path *path, int data_size,
			  int empty)
{
	struct extent_buffer *right = path->nodes[0];
	struct extent_buffer *left;
	int slot;
	int free_space;
	u32 right_nritems;
	int ret = 0;

	slot = path->slots[1];
	if (slot == 0)
		return 1;
	if (!path->nodes[1])
		return 1;

	right_nritems = btrfs_header_nritems(right);
	if (right_nritems == 0)
		return 1;

	btrfs_assert_tree_locked(path->nodes[1]);

	left = read_node_slot(root, path->nodes[1], slot - 1);
	btrfs_tree_lock(left);
	btrfs_set_lock_blocking(left);

	free_space = btrfs_leaf_free_space(root, left);
	if (free_space < data_size) {
		ret = 1;
		goto out;
	}

	/* cow and double check */
	ret = btrfs_cow_block(trans, root, left,
			      path->nodes[1], slot - 1, &left);
	if (ret) {
		/* we hit -ENOSPC, but it isn't fatal here */
		ret = 1;
		goto out;
	}

	free_space = btrfs_leaf_free_space(root, left);
	if (free_space < data_size) {
		ret = 1;
		goto out;
	}

	return __push_leaf_left(trans, root, path, data_size,
			       empty, left, free_space, right_nritems);
out:
	btrfs_tree_unlock(left);
	free_extent_buffer(left);
	return ret;
}

/*
 * split the path's leaf in two, making sure there is at least data_size
 * available for the resulting leaf level of the path.
 *
 * returns 0 if all went well and < 0 on failure.
 */
static noinline int copy_for_split(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct btrfs_path *path,
			       struct extent_buffer *l,
			       struct extent_buffer *right,
			       int slot, int mid, int nritems)
{
	int data_copy_size;
	int rt_data_off;
	int i;
	int ret = 0;
	int wret;
	struct btrfs_disk_key disk_key;

	nritems = nritems - mid;
	btrfs_set_header_nritems(right, nritems);
	data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);

	copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
			   btrfs_item_nr_offset(mid),
			   nritems * sizeof(struct btrfs_item));

	copy_extent_buffer(right, l,
		     btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
		     data_copy_size, btrfs_leaf_data(l) +
		     leaf_data_end(root, l), data_copy_size);

	rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
		      btrfs_item_end_nr(l, mid);

	for (i = 0; i < nritems; i++) {
		struct btrfs_item *item = btrfs_item_nr(right, i);
		u32 ioff;

		if (!right->map_token) {
			map_extent_buffer(right, (unsigned long)item,
					sizeof(struct btrfs_item),
					&right->map_token, &right->kaddr,
					&right->map_start, &right->map_len,
					KM_USER1);
		}

		ioff = btrfs_item_offset(right, item);
		btrfs_set_item_offset(right, item, ioff + rt_data_off);
	}

	if (right->map_token) {
		unmap_extent_buffer(right, right->map_token, KM_USER1);
		right->map_token = NULL;
	}

	btrfs_set_header_nritems(l, mid);
	ret = 0;
	btrfs_item_key(right, &disk_key, 0);
	wret = insert_ptr(trans, root, path, &disk_key, right->start,
			  path->slots[1] + 1, 1);
	if (wret)
		ret = wret;

	btrfs_mark_buffer_dirty(right);
	btrfs_mark_buffer_dirty(l);
	BUG_ON(path->slots[0] != slot);

	if (mid <= slot) {
		btrfs_tree_unlock(path->nodes[0]);
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = right;
		path->slots[0] -= mid;
		path->slots[1] += 1;
	} else {
		btrfs_tree_unlock(right);
		free_extent_buffer(right);
	}

	BUG_ON(path->slots[0] < 0);

	return ret;
}

C
Chris Mason 已提交
2848 2849 2850
/*
 * split the path's leaf in two, making sure there is at least data_size
 * available for the resulting leaf level of the path.
C
Chris Mason 已提交
2851 2852
 *
 * returns 0 if all went well and < 0 on failure.
C
Chris Mason 已提交
2853
 */
2854 2855 2856 2857 2858
static noinline int split_leaf(struct btrfs_trans_handle *trans,
			       struct btrfs_root *root,
			       struct btrfs_key *ins_key,
			       struct btrfs_path *path, int data_size,
			       int extend)
2859
{
2860
	struct btrfs_disk_key disk_key;
2861
	struct extent_buffer *l;
2862
	u32 nritems;
2863 2864
	int mid;
	int slot;
2865
	struct extent_buffer *right;
2866
	int ret = 0;
C
Chris Mason 已提交
2867
	int wret;
2868
	int split;
2869
	int num_doubles = 0;
C
Chris Mason 已提交
2870

C
Chris Mason 已提交
2871
	/* first try to make some room by pushing left and right */
2872
	if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2873
		wret = push_leaf_right(trans, root, path, data_size, 0);
C
Chris Mason 已提交
2874
		if (wret < 0)
C
Chris Mason 已提交
2875
			return wret;
2876
		if (wret) {
2877
			wret = push_leaf_left(trans, root, path, data_size, 0);
2878 2879 2880 2881
			if (wret < 0)
				return wret;
		}
		l = path->nodes[0];
C
Chris Mason 已提交
2882

2883
		/* did the pushes work? */
2884
		if (btrfs_leaf_free_space(root, l) >= data_size)
2885
			return 0;
2886
	}
C
Chris Mason 已提交
2887

C
Chris Mason 已提交
2888
	if (!path->nodes[1]) {
2889
		ret = insert_new_root(trans, root, path, 1);
C
Chris Mason 已提交
2890 2891 2892
		if (ret)
			return ret;
	}
2893
again:
2894
	split = 1;
2895
	l = path->nodes[0];
2896
	slot = path->slots[0];
2897
	nritems = btrfs_header_nritems(l);
C
Chris Mason 已提交
2898
	mid = (nritems + 1) / 2;
2899

2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938
	if (mid <= slot) {
		if (nritems == 1 ||
		    leaf_space_used(l, mid, nritems - mid) + data_size >
			BTRFS_LEAF_DATA_SIZE(root)) {
			if (slot >= nritems) {
				split = 0;
			} else {
				mid = slot;
				if (mid != nritems &&
				    leaf_space_used(l, mid, nritems - mid) +
				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
					split = 2;
				}
			}
		}
	} else {
		if (leaf_space_used(l, 0, mid) + data_size >
			BTRFS_LEAF_DATA_SIZE(root)) {
			if (!extend && data_size && slot == 0) {
				split = 0;
			} else if ((extend || !data_size) && slot == 0) {
				mid = 1;
			} else {
				mid = slot;
				if (mid != nritems &&
				    leaf_space_used(l, mid, nritems - mid) +
				    data_size > BTRFS_LEAF_DATA_SIZE(root)) {
					split = 2 ;
				}
			}
		}
	}

	if (split == 0)
		btrfs_cpu_key_to_disk(&disk_key, ins_key);
	else
		btrfs_item_key(l, &disk_key, mid);

	right = btrfs_alloc_free_block(trans, root, root->leafsize, 0,
Z
Zheng Yan 已提交
2939
					root->root_key.objectid,
2940
					&disk_key, 0, l->start, 0);
2941 2942
	if (IS_ERR(right)) {
		BUG_ON(1);
2943
		return PTR_ERR(right);
2944
	}
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 2951 2952 2953 2954
	btrfs_set_header_owner(right, root->root_key.objectid);
	btrfs_set_header_level(right, 0);
	write_extent_buffer(right, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(right),
			    BTRFS_FSID_SIZE);
2955 2956 2957 2958

	write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
			    (unsigned long)btrfs_header_chunk_tree_uuid(right),
			    BTRFS_UUID_SIZE);
2959

2960 2961 2962 2963 2964 2965 2966 2967
	if (split == 0) {
		if (mid <= slot) {
			btrfs_set_header_nritems(right, 0);
			wret = insert_ptr(trans, root, path,
					  &disk_key, right->start,
					  path->slots[1] + 1, 1);
			if (wret)
				ret = wret;
2968

2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988
			btrfs_tree_unlock(path->nodes[0]);
			free_extent_buffer(path->nodes[0]);
			path->nodes[0] = right;
			path->slots[0] = 0;
			path->slots[1] += 1;
		} else {
			btrfs_set_header_nritems(right, 0);
			wret = insert_ptr(trans, root, path,
					  &disk_key,
					  right->start,
					  path->slots[1], 1);
			if (wret)
				ret = wret;
			btrfs_tree_unlock(path->nodes[0]);
			free_extent_buffer(path->nodes[0]);
			path->nodes[0] = right;
			path->slots[0] = 0;
			if (path->slots[1] == 0) {
				wret = fixup_low_keys(trans, root,
						path, &disk_key, 1);
2989 2990
				if (wret)
					ret = wret;
2991
			}
2992
		}
2993 2994
		btrfs_mark_buffer_dirty(right);
		return ret;
2995
	}
C
Chris Mason 已提交
2996

2997
	ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
Z
Zheng Yan 已提交
2998 2999
	BUG_ON(ret);

3000
	if (split == 2) {
3001 3002 3003
		BUG_ON(num_doubles != 0);
		num_doubles++;
		goto again;
3004
	}
3005

3006 3007 3008
	return ret;
}

3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062
/*
 * This function splits a single item into two items,
 * giving 'new_key' to the new item and splitting the
 * old one at split_offset (from the start of the item).
 *
 * The path may be released by this operation.  After
 * the split, the path is pointing to the old item.  The
 * new item is going to be in the same node as the old one.
 *
 * Note, the item being split must be smaller enough to live alone on
 * a tree block with room for one extra struct btrfs_item
 *
 * This allows us to split the item in place, keeping a lock on the
 * leaf the entire time.
 */
int btrfs_split_item(struct btrfs_trans_handle *trans,
		     struct btrfs_root *root,
		     struct btrfs_path *path,
		     struct btrfs_key *new_key,
		     unsigned long split_offset)
{
	u32 item_size;
	struct extent_buffer *leaf;
	struct btrfs_key orig_key;
	struct btrfs_item *item;
	struct btrfs_item *new_item;
	int ret = 0;
	int slot;
	u32 nritems;
	u32 orig_offset;
	struct btrfs_disk_key disk_key;
	char *buf;

	leaf = path->nodes[0];
	btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
	if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
		goto split;

	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
	btrfs_release_path(root, path);

	path->search_for_split = 1;
	path->keep_locks = 1;

	ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
	path->search_for_split = 0;

	/* if our item isn't there or got smaller, return now */
	if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
							path->slots[0])) {
		path->keep_locks = 0;
		return -EAGAIN;
	}

3063
	btrfs_set_path_blocking(path);
3064 3065
	ret = split_leaf(trans, root, &orig_key, path,
			 sizeof(struct btrfs_item), 1);
3066 3067 3068
	path->keep_locks = 0;
	BUG_ON(ret);

3069 3070 3071 3072 3073
	btrfs_unlock_up_safe(path, 1);
	leaf = path->nodes[0];
	BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));

split:
3074 3075 3076 3077 3078 3079
	/*
	 * make sure any changes to the path from split_leaf leave it
	 * in a blocking state
	 */
	btrfs_set_path_blocking(path);

3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133
	item = btrfs_item_nr(leaf, path->slots[0]);
	orig_offset = btrfs_item_offset(leaf, item);
	item_size = btrfs_item_size(leaf, item);

	buf = kmalloc(item_size, GFP_NOFS);
	read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
			    path->slots[0]), item_size);
	slot = path->slots[0] + 1;
	leaf = path->nodes[0];

	nritems = btrfs_header_nritems(leaf);

	if (slot != nritems) {
		/* shift the items */
		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
			      btrfs_item_nr_offset(slot),
			      (nritems - slot) * sizeof(struct btrfs_item));

	}

	btrfs_cpu_key_to_disk(&disk_key, new_key);
	btrfs_set_item_key(leaf, &disk_key, slot);

	new_item = btrfs_item_nr(leaf, slot);

	btrfs_set_item_offset(leaf, new_item, orig_offset);
	btrfs_set_item_size(leaf, new_item, item_size - split_offset);

	btrfs_set_item_offset(leaf, item,
			      orig_offset + item_size - split_offset);
	btrfs_set_item_size(leaf, item, split_offset);

	btrfs_set_header_nritems(leaf, nritems + 1);

	/* write the data for the start of the original item */
	write_extent_buffer(leaf, buf,
			    btrfs_item_ptr_offset(leaf, path->slots[0]),
			    split_offset);

	/* write the data for the new item */
	write_extent_buffer(leaf, buf + split_offset,
			    btrfs_item_ptr_offset(leaf, slot),
			    item_size - split_offset);
	btrfs_mark_buffer_dirty(leaf);

	ret = 0;
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
		BUG();
	}
	kfree(buf);
	return ret;
}

C
Chris Mason 已提交
3134 3135 3136 3137 3138 3139
/*
 * make the item pointed to by the path smaller.  new_size indicates
 * how small to make it, and from_end tells us if we just chop bytes
 * off the end of the item or if we shift the item to chop bytes off
 * the front.
 */
C
Chris Mason 已提交
3140 3141 3142
int btrfs_truncate_item(struct btrfs_trans_handle *trans,
			struct btrfs_root *root,
			struct btrfs_path *path,
3143
			u32 new_size, int from_end)
C
Chris Mason 已提交
3144 3145 3146 3147
{
	int ret = 0;
	int slot;
	int slot_orig;
3148 3149
	struct extent_buffer *leaf;
	struct btrfs_item *item;
C
Chris Mason 已提交
3150 3151 3152 3153 3154 3155 3156 3157
	u32 nritems;
	unsigned int data_end;
	unsigned int old_data_start;
	unsigned int old_size;
	unsigned int size_diff;
	int i;

	slot_orig = path->slots[0];
3158
	leaf = path->nodes[0];
3159 3160 3161 3162 3163
	slot = path->slots[0];

	old_size = btrfs_item_size_nr(leaf, slot);
	if (old_size == new_size)
		return 0;
C
Chris Mason 已提交
3164

3165
	nritems = btrfs_header_nritems(leaf);
C
Chris Mason 已提交
3166 3167
	data_end = leaf_data_end(root, leaf);

3168
	old_data_start = btrfs_item_offset_nr(leaf, slot);
3169

C
Chris Mason 已提交
3170 3171 3172 3173 3174 3175 3176 3177 3178 3179
	size_diff = old_size - new_size;

	BUG_ON(slot < 0);
	BUG_ON(slot >= nritems);

	/*
	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
	 */
	/* first correct the data pointers */
	for (i = slot; i < nritems; i++) {
3180 3181
		u32 ioff;
		item = btrfs_item_nr(leaf, i);
3182 3183 3184 3185 3186 3187 3188 3189 3190

		if (!leaf->map_token) {
			map_extent_buffer(leaf, (unsigned long)item,
					sizeof(struct btrfs_item),
					&leaf->map_token, &leaf->kaddr,
					&leaf->map_start, &leaf->map_len,
					KM_USER1);
		}

3191 3192
		ioff = btrfs_item_offset(leaf, item);
		btrfs_set_item_offset(leaf, item, ioff + size_diff);
C
Chris Mason 已提交
3193
	}
3194 3195 3196 3197 3198 3199

	if (leaf->map_token) {
		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
		leaf->map_token = NULL;
	}

C
Chris Mason 已提交
3200
	/* shift the data */
3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223
	if (from_end) {
		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
			      data_end + size_diff, btrfs_leaf_data(leaf) +
			      data_end, old_data_start + new_size - data_end);
	} else {
		struct btrfs_disk_key disk_key;
		u64 offset;

		btrfs_item_key(leaf, &disk_key, slot);

		if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
			unsigned long ptr;
			struct btrfs_file_extent_item *fi;

			fi = btrfs_item_ptr(leaf, slot,
					    struct btrfs_file_extent_item);
			fi = (struct btrfs_file_extent_item *)(
			     (unsigned long)fi - size_diff);

			if (btrfs_file_extent_type(leaf, fi) ==
			    BTRFS_FILE_EXTENT_INLINE) {
				ptr = btrfs_item_ptr_offset(leaf, slot);
				memmove_extent_buffer(leaf, ptr,
C
Chris Mason 已提交
3224 3225
				      (unsigned long)fi,
				      offsetof(struct btrfs_file_extent_item,
3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239
						 disk_bytenr));
			}
		}

		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
			      data_end + size_diff, btrfs_leaf_data(leaf) +
			      data_end, old_data_start - data_end);

		offset = btrfs_disk_key_offset(&disk_key);
		btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
		btrfs_set_item_key(leaf, &disk_key, slot);
		if (slot == 0)
			fixup_low_keys(trans, root, path, &disk_key, 1);
	}
3240 3241 3242 3243

	item = btrfs_item_nr(leaf, slot);
	btrfs_set_item_size(leaf, item, new_size);
	btrfs_mark_buffer_dirty(leaf);
C
Chris Mason 已提交
3244 3245

	ret = 0;
3246 3247
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
3248
		BUG();
3249
	}
C
Chris Mason 已提交
3250 3251 3252
	return ret;
}

C
Chris Mason 已提交
3253 3254 3255
/*
 * make the item pointed to by the path bigger, data_size is the new size.
 */
3256 3257 3258
int btrfs_extend_item(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root, struct btrfs_path *path,
		      u32 data_size)
3259 3260 3261 3262
{
	int ret = 0;
	int slot;
	int slot_orig;
3263 3264
	struct extent_buffer *leaf;
	struct btrfs_item *item;
3265 3266 3267 3268 3269 3270 3271
	u32 nritems;
	unsigned int data_end;
	unsigned int old_data;
	unsigned int old_size;
	int i;

	slot_orig = path->slots[0];
3272
	leaf = path->nodes[0];
3273

3274
	nritems = btrfs_header_nritems(leaf);
3275 3276
	data_end = leaf_data_end(root, leaf);

3277 3278
	if (btrfs_leaf_free_space(root, leaf) < data_size) {
		btrfs_print_leaf(root, leaf);
3279
		BUG();
3280
	}
3281
	slot = path->slots[0];
3282
	old_data = btrfs_item_end_nr(leaf, slot);
3283 3284

	BUG_ON(slot < 0);
3285 3286
	if (slot >= nritems) {
		btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
3287 3288
		printk(KERN_CRIT "slot %d too large, nritems %d\n",
		       slot, nritems);
3289 3290
		BUG_ON(1);
	}
3291 3292 3293 3294 3295 3296

	/*
	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
	 */
	/* first correct the data pointers */
	for (i = slot; i < nritems; i++) {
3297 3298
		u32 ioff;
		item = btrfs_item_nr(leaf, i);
3299 3300 3301 3302 3303 3304 3305 3306

		if (!leaf->map_token) {
			map_extent_buffer(leaf, (unsigned long)item,
					sizeof(struct btrfs_item),
					&leaf->map_token, &leaf->kaddr,
					&leaf->map_start, &leaf->map_len,
					KM_USER1);
		}
3307 3308
		ioff = btrfs_item_offset(leaf, item);
		btrfs_set_item_offset(leaf, item, ioff - data_size);
3309
	}
3310

3311 3312 3313 3314 3315
	if (leaf->map_token) {
		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
		leaf->map_token = NULL;
	}

3316
	/* shift the data */
3317
	memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3318 3319
		      data_end - data_size, btrfs_leaf_data(leaf) +
		      data_end, old_data - data_end);
3320

3321
	data_end = old_data;
3322 3323 3324 3325
	old_size = btrfs_item_size_nr(leaf, slot);
	item = btrfs_item_nr(leaf, slot);
	btrfs_set_item_size(leaf, item, old_size + data_size);
	btrfs_mark_buffer_dirty(leaf);
3326 3327

	ret = 0;
3328 3329
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
3330
		BUG();
3331
	}
3332 3333 3334
	return ret;
}

3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357
/*
 * Given a key and some data, insert items into the tree.
 * This does all the path init required, making room in the tree if needed.
 * Returns the number of keys that were inserted.
 */
int btrfs_insert_some_items(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root,
			    struct btrfs_path *path,
			    struct btrfs_key *cpu_key, u32 *data_size,
			    int nr)
{
	struct extent_buffer *leaf;
	struct btrfs_item *item;
	int ret = 0;
	int slot;
	int i;
	u32 nritems;
	u32 total_data = 0;
	u32 total_size = 0;
	unsigned int data_end;
	struct btrfs_disk_key disk_key;
	struct btrfs_key found_key;

3358 3359 3360 3361 3362 3363
	for (i = 0; i < nr; i++) {
		if (total_size + data_size[i] + sizeof(struct btrfs_item) >
		    BTRFS_LEAF_DATA_SIZE(root)) {
			break;
			nr = i;
		}
3364
		total_data += data_size[i];
3365 3366 3367
		total_size += data_size[i] + sizeof(struct btrfs_item);
	}
	BUG_ON(nr == 0);
3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401

	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
	if (ret == 0)
		return -EEXIST;
	if (ret < 0)
		goto out;

	leaf = path->nodes[0];

	nritems = btrfs_header_nritems(leaf);
	data_end = leaf_data_end(root, leaf);

	if (btrfs_leaf_free_space(root, leaf) < total_size) {
		for (i = nr; i >= 0; i--) {
			total_data -= data_size[i];
			total_size -= data_size[i] + sizeof(struct btrfs_item);
			if (total_size < btrfs_leaf_free_space(root, leaf))
				break;
		}
		nr = i;
	}

	slot = path->slots[0];
	BUG_ON(slot < 0);

	if (slot != nritems) {
		unsigned int old_data = btrfs_item_end_nr(leaf, slot);

		item = btrfs_item_nr(leaf, slot);
		btrfs_item_key_to_cpu(leaf, &found_key, slot);

		/* figure out how many keys we can insert in here */
		total_data = data_size[0];
		for (i = 1; i < nr; i++) {
3402
			if (btrfs_comp_cpu_keys(&found_key, cpu_key + i) <= 0)
3403 3404 3405 3406 3407 3408 3409
				break;
			total_data += data_size[i];
		}
		nr = i;

		if (old_data < data_end) {
			btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
3410
			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486
			       slot, old_data, data_end);
			BUG_ON(1);
		}
		/*
		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
		 */
		/* first correct the data pointers */
		WARN_ON(leaf->map_token);
		for (i = slot; i < nritems; i++) {
			u32 ioff;

			item = btrfs_item_nr(leaf, i);
			if (!leaf->map_token) {
				map_extent_buffer(leaf, (unsigned long)item,
					sizeof(struct btrfs_item),
					&leaf->map_token, &leaf->kaddr,
					&leaf->map_start, &leaf->map_len,
					KM_USER1);
			}

			ioff = btrfs_item_offset(leaf, item);
			btrfs_set_item_offset(leaf, item, ioff - total_data);
		}
		if (leaf->map_token) {
			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
			leaf->map_token = NULL;
		}

		/* shift the items */
		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
			      btrfs_item_nr_offset(slot),
			      (nritems - slot) * sizeof(struct btrfs_item));

		/* shift the data */
		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
			      data_end - total_data, btrfs_leaf_data(leaf) +
			      data_end, old_data - data_end);
		data_end = old_data;
	} else {
		/*
		 * this sucks but it has to be done, if we are inserting at
		 * the end of the leaf only insert 1 of the items, since we
		 * have no way of knowing whats on the next leaf and we'd have
		 * to drop our current locks to figure it out
		 */
		nr = 1;
	}

	/* setup the item for the new data */
	for (i = 0; i < nr; i++) {
		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
		btrfs_set_item_key(leaf, &disk_key, slot + i);
		item = btrfs_item_nr(leaf, slot + i);
		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
		data_end -= data_size[i];
		btrfs_set_item_size(leaf, item, data_size[i]);
	}
	btrfs_set_header_nritems(leaf, nritems + nr);
	btrfs_mark_buffer_dirty(leaf);

	ret = 0;
	if (slot == 0) {
		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
	}

	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
		BUG();
	}
out:
	if (!ret)
		ret = nr;
	return ret;
}

C
Chris Mason 已提交
3487
/*
3488 3489 3490
 * this is a helper for btrfs_insert_empty_items, the main goal here is
 * to save stack depth by doing the bulk of the work in a function
 * that doesn't call btrfs_search_slot
C
Chris Mason 已提交
3491
 */
3492 3493 3494 3495 3496
static noinline_for_stack int
setup_items_for_insert(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root, struct btrfs_path *path,
		      struct btrfs_key *cpu_key, u32 *data_size,
		      u32 total_data, u32 total_size, int nr)
3497
{
3498
	struct btrfs_item *item;
3499
	int i;
3500
	u32 nritems;
3501
	unsigned int data_end;
C
Chris Mason 已提交
3502
	struct btrfs_disk_key disk_key;
3503 3504 3505
	int ret;
	struct extent_buffer *leaf;
	int slot;
C
Chris Mason 已提交
3506

3507
	leaf = path->nodes[0];
3508
	slot = path->slots[0];
C
Chris Mason 已提交
3509

3510
	nritems = btrfs_header_nritems(leaf);
C
Chris Mason 已提交
3511
	data_end = leaf_data_end(root, leaf);
3512

3513
	if (btrfs_leaf_free_space(root, leaf) < total_size) {
3514
		btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
3515
		printk(KERN_CRIT "not enough freespace need %u have %d\n",
3516
		       total_size, btrfs_leaf_free_space(root, leaf));
3517
		BUG();
3518
	}
3519

3520
	if (slot != nritems) {
3521
		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
3522

3523 3524
		if (old_data < data_end) {
			btrfs_print_leaf(root, leaf);
C
Chris Mason 已提交
3525
			printk(KERN_CRIT "slot %d old_data %d data_end %d\n",
3526 3527 3528
			       slot, old_data, data_end);
			BUG_ON(1);
		}
3529 3530 3531 3532
		/*
		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
		 */
		/* first correct the data pointers */
3533
		WARN_ON(leaf->map_token);
C
Chris Mason 已提交
3534
		for (i = slot; i < nritems; i++) {
3535
			u32 ioff;
3536

3537
			item = btrfs_item_nr(leaf, i);
3538 3539 3540 3541 3542 3543 3544 3545
			if (!leaf->map_token) {
				map_extent_buffer(leaf, (unsigned long)item,
					sizeof(struct btrfs_item),
					&leaf->map_token, &leaf->kaddr,
					&leaf->map_start, &leaf->map_len,
					KM_USER1);
			}

3546
			ioff = btrfs_item_offset(leaf, item);
3547
			btrfs_set_item_offset(leaf, item, ioff - total_data);
C
Chris Mason 已提交
3548
		}
3549 3550 3551 3552
		if (leaf->map_token) {
			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
			leaf->map_token = NULL;
		}
3553 3554

		/* shift the items */
3555
		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
3556
			      btrfs_item_nr_offset(slot),
C
Chris Mason 已提交
3557
			      (nritems - slot) * sizeof(struct btrfs_item));
3558 3559

		/* shift the data */
3560
		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
3561
			      data_end - total_data, btrfs_leaf_data(leaf) +
C
Chris Mason 已提交
3562
			      data_end, old_data - data_end);
3563 3564
		data_end = old_data;
	}
3565

3566
	/* setup the item for the new data */
3567 3568 3569 3570 3571 3572 3573 3574
	for (i = 0; i < nr; i++) {
		btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
		btrfs_set_item_key(leaf, &disk_key, slot + i);
		item = btrfs_item_nr(leaf, slot + i);
		btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
		data_end -= data_size[i];
		btrfs_set_item_size(leaf, item, data_size[i]);
	}
3575

3576
	btrfs_set_header_nritems(leaf, nritems + nr);
C
Chris Mason 已提交
3577 3578

	ret = 0;
3579
	if (slot == 0) {
3580
		struct btrfs_disk_key disk_key;
3581
		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
3582
		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
3583
	}
3584 3585
	btrfs_unlock_up_safe(path, 1);
	btrfs_mark_buffer_dirty(leaf);
C
Chris Mason 已提交
3586

3587 3588
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
3589
		BUG();
3590
	}
3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627
	return ret;
}

/*
 * Given a key and some data, insert items into the tree.
 * This does all the path init required, making room in the tree if needed.
 */
int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root,
			    struct btrfs_path *path,
			    struct btrfs_key *cpu_key, u32 *data_size,
			    int nr)
{
	struct extent_buffer *leaf;
	int ret = 0;
	int slot;
	int i;
	u32 total_size = 0;
	u32 total_data = 0;

	for (i = 0; i < nr; i++)
		total_data += data_size[i];

	total_size = total_data + (nr * sizeof(struct btrfs_item));
	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
	if (ret == 0)
		return -EEXIST;
	if (ret < 0)
		goto out;

	leaf = path->nodes[0];
	slot = path->slots[0];
	BUG_ON(slot < 0);

	ret = setup_items_for_insert(trans, root, path, cpu_key, data_size,
			       total_data, total_size, nr);

3628
out:
3629 3630 3631 3632 3633 3634 3635
	return ret;
}

/*
 * Given a key and some data, insert an item into the tree.
 * This does all the path init required, making room in the tree if needed.
 */
3636 3637 3638
int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_key *cpu_key, void *data, u32
		      data_size)
3639 3640
{
	int ret = 0;
C
Chris Mason 已提交
3641
	struct btrfs_path *path;
3642 3643
	struct extent_buffer *leaf;
	unsigned long ptr;
3644

C
Chris Mason 已提交
3645 3646 3647
	path = btrfs_alloc_path();
	BUG_ON(!path);
	ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
3648
	if (!ret) {
3649 3650 3651 3652
		leaf = path->nodes[0];
		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
		write_extent_buffer(leaf, data, ptr, data_size);
		btrfs_mark_buffer_dirty(leaf);
3653
	}
C
Chris Mason 已提交
3654
	btrfs_free_path(path);
C
Chris Mason 已提交
3655
	return ret;
3656 3657
}

C
Chris Mason 已提交
3658
/*
C
Chris Mason 已提交
3659
 * delete the pointer from a given node.
C
Chris Mason 已提交
3660
 *
C
Chris Mason 已提交
3661 3662
 * the tree should have been previously balanced so the deletion does not
 * empty a node.
C
Chris Mason 已提交
3663
 */
3664 3665
static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		   struct btrfs_path *path, int level, int slot)
3666
{
3667
	struct extent_buffer *parent = path->nodes[level];
3668
	u32 nritems;
C
Chris Mason 已提交
3669
	int ret = 0;
3670
	int wret;
3671

3672
	nritems = btrfs_header_nritems(parent);
C
Chris Mason 已提交
3673
	if (slot != nritems - 1) {
3674 3675 3676
		memmove_extent_buffer(parent,
			      btrfs_node_key_ptr_offset(slot),
			      btrfs_node_key_ptr_offset(slot + 1),
C
Chris Mason 已提交
3677 3678
			      sizeof(struct btrfs_key_ptr) *
			      (nritems - slot - 1));
3679
	}
3680
	nritems--;
3681
	btrfs_set_header_nritems(parent, nritems);
3682
	if (nritems == 0 && parent == root->node) {
3683
		BUG_ON(btrfs_header_level(root->node) != 1);
3684
		/* just turn the root into a leaf and break */
3685
		btrfs_set_header_level(root->node, 0);
3686
	} else if (slot == 0) {
3687 3688 3689 3690
		struct btrfs_disk_key disk_key;

		btrfs_node_key(parent, &disk_key, 0);
		wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
C
Chris Mason 已提交
3691 3692
		if (wret)
			ret = wret;
3693
	}
C
Chris Mason 已提交
3694
	btrfs_mark_buffer_dirty(parent);
C
Chris Mason 已提交
3695
	return ret;
3696 3697
}

3698 3699
/*
 * a helper function to delete the leaf pointed to by path->slots[1] and
3700
 * path->nodes[1].
3701 3702 3703 3704 3705 3706 3707
 *
 * This deletes the pointer in path->nodes[1] and frees the leaf
 * block extent.  zero is returned if it all worked out, < 0 otherwise.
 *
 * The path must have already been setup for deleting the leaf, including
 * all the proper balancing.  path->nodes[1] must be locked.
 */
3708 3709 3710 3711
static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
				   struct btrfs_root *root,
				   struct btrfs_path *path,
				   struct extent_buffer *leaf)
3712 3713 3714
{
	int ret;

3715
	WARN_ON(btrfs_header_generation(leaf) != trans->transid);
3716 3717 3718 3719
	ret = del_ptr(trans, root, path, 1, path->slots[1]);
	if (ret)
		return ret;

3720 3721 3722 3723 3724 3725
	/*
	 * btrfs_free_extent is expensive, we want to make sure we
	 * aren't holding any locks when we call it
	 */
	btrfs_unlock_up_safe(path, 0);

3726 3727
	ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
				0, root->root_key.objectid, 0, 0);
3728 3729
	return ret;
}
C
Chris Mason 已提交
3730 3731 3732 3733
/*
 * delete the item at the leaf level in path.  If that empties
 * the leaf, remove it from the tree
 */
3734 3735
int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		    struct btrfs_path *path, int slot, int nr)
3736
{
3737 3738
	struct extent_buffer *leaf;
	struct btrfs_item *item;
3739 3740
	int last_off;
	int dsize = 0;
C
Chris Mason 已提交
3741 3742
	int ret = 0;
	int wret;
3743
	int i;
3744
	u32 nritems;
3745

3746
	leaf = path->nodes[0];
3747 3748 3749 3750 3751
	last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);

	for (i = 0; i < nr; i++)
		dsize += btrfs_item_size_nr(leaf, slot + i);

3752
	nritems = btrfs_header_nritems(leaf);
3753

3754
	if (slot + nr != nritems) {
C
Chris Mason 已提交
3755
		int data_end = leaf_data_end(root, leaf);
3756 3757

		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
C
Chris Mason 已提交
3758 3759
			      data_end + dsize,
			      btrfs_leaf_data(leaf) + data_end,
3760
			      last_off - data_end);
3761

3762
		for (i = slot + nr; i < nritems; i++) {
3763
			u32 ioff;
3764

3765
			item = btrfs_item_nr(leaf, i);
3766 3767 3768 3769 3770 3771 3772
			if (!leaf->map_token) {
				map_extent_buffer(leaf, (unsigned long)item,
					sizeof(struct btrfs_item),
					&leaf->map_token, &leaf->kaddr,
					&leaf->map_start, &leaf->map_len,
					KM_USER1);
			}
3773 3774
			ioff = btrfs_item_offset(leaf, item);
			btrfs_set_item_offset(leaf, item, ioff + dsize);
C
Chris Mason 已提交
3775
		}
3776 3777 3778 3779 3780 3781

		if (leaf->map_token) {
			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
			leaf->map_token = NULL;
		}

3782
		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
3783
			      btrfs_item_nr_offset(slot + nr),
C
Chris Mason 已提交
3784
			      sizeof(struct btrfs_item) *
3785
			      (nritems - slot - nr));
3786
	}
3787 3788
	btrfs_set_header_nritems(leaf, nritems - nr);
	nritems -= nr;
3789

C
Chris Mason 已提交
3790
	/* delete the leaf if we've emptied it */
3791
	if (nritems == 0) {
3792 3793
		if (leaf == root->node) {
			btrfs_set_header_level(leaf, 0);
3794
		} else {
3795
			ret = btrfs_del_leaf(trans, root, path, leaf);
3796
			BUG_ON(ret);
3797
		}
3798
	} else {
3799
		int used = leaf_space_used(leaf, 0, nritems);
C
Chris Mason 已提交
3800
		if (slot == 0) {
3801 3802 3803
			struct btrfs_disk_key disk_key;

			btrfs_item_key(leaf, &disk_key, 0);
3804
			wret = fixup_low_keys(trans, root, path,
3805
					      &disk_key, 1);
C
Chris Mason 已提交
3806 3807 3808 3809
			if (wret)
				ret = wret;
		}

C
Chris Mason 已提交
3810
		/* delete the leaf if it is mostly empty */
C
Chris Mason 已提交
3811
		if (used < BTRFS_LEAF_DATA_SIZE(root) / 2) {
3812 3813 3814 3815
			/* push_leaf_left fixes the path.
			 * make sure the path still points to our leaf
			 * for possible call to del_ptr below
			 */
3816
			slot = path->slots[1];
3817 3818
			extent_buffer_get(leaf);

3819
			btrfs_set_path_blocking(path);
3820
			wret = push_leaf_left(trans, root, path, 1, 1);
3821
			if (wret < 0 && wret != -ENOSPC)
C
Chris Mason 已提交
3822
				ret = wret;
3823 3824 3825

			if (path->nodes[0] == leaf &&
			    btrfs_header_nritems(leaf)) {
3826
				wret = push_leaf_right(trans, root, path, 1, 1);
3827
				if (wret < 0 && wret != -ENOSPC)
C
Chris Mason 已提交
3828 3829
					ret = wret;
			}
3830 3831

			if (btrfs_header_nritems(leaf) == 0) {
3832
				path->slots[1] = slot;
3833
				ret = btrfs_del_leaf(trans, root, path, leaf);
3834
				BUG_ON(ret);
3835
				free_extent_buffer(leaf);
C
Chris Mason 已提交
3836
			} else {
3837 3838 3839 3840 3841 3842 3843
				/* if we're still in the path, make sure
				 * we're dirty.  Otherwise, one of the
				 * push_leaf functions must have already
				 * dirtied this buffer
				 */
				if (path->nodes[0] == leaf)
					btrfs_mark_buffer_dirty(leaf);
3844
				free_extent_buffer(leaf);
3845
			}
3846
		} else {
3847
			btrfs_mark_buffer_dirty(leaf);
3848 3849
		}
	}
C
Chris Mason 已提交
3850
	return ret;
3851 3852
}

3853
/*
3854
 * search the tree again to find a leaf with lesser keys
3855 3856
 * returns 0 if it found something or 1 if there are no lesser leaves.
 * returns < 0 on io errors.
C
Chris Mason 已提交
3857 3858 3859
 *
 * This may release the path, and so you may lose any locks held at the
 * time you call it.
3860 3861 3862
 */
int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
{
3863 3864 3865
	struct btrfs_key key;
	struct btrfs_disk_key found_key;
	int ret;
3866

3867
	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
3868

3869 3870 3871 3872 3873 3874 3875 3876
	if (key.offset > 0)
		key.offset--;
	else if (key.type > 0)
		key.type--;
	else if (key.objectid > 0)
		key.objectid--;
	else
		return 1;
3877

3878 3879 3880 3881 3882 3883 3884 3885 3886
	btrfs_release_path(root, path);
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ret;
	btrfs_item_key(path->nodes[0], &found_key, 0);
	ret = comp_keys(&found_key, &key);
	if (ret < 0)
		return 0;
	return 1;
3887 3888
}

3889 3890 3891
/*
 * A helper function to walk down the tree starting at min_key, and looking
 * for nodes or leaves that are either in cache or have a minimum
C
Chris Mason 已提交
3892
 * transaction id.  This is used by the btree defrag code, and tree logging
3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903
 *
 * This does not cow, but it does stuff the starting key it finds back
 * into min_key, so you can call btrfs_search_slot with cow=1 on the
 * key and get a writable path.
 *
 * This does lock as it descends, and path->keep_locks should be set
 * to 1 by the caller.
 *
 * This honors path->lowest_level to prevent descent past a given level
 * of the tree.
 *
C
Chris Mason 已提交
3904 3905 3906 3907
 * min_trans indicates the oldest transaction that you are interested
 * in walking through.  Any nodes or leaves older than min_trans are
 * skipped over (without reading them).
 *
3908 3909 3910 3911
 * returns zero if something useful was found, < 0 on error and 1 if there
 * was nothing in the tree that matched the search criteria.
 */
int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
3912
			 struct btrfs_key *max_key,
3913 3914 3915 3916 3917 3918
			 struct btrfs_path *path, int cache_only,
			 u64 min_trans)
{
	struct extent_buffer *cur;
	struct btrfs_key found_key;
	int slot;
3919
	int sret;
3920 3921 3922 3923
	u32 nritems;
	int level;
	int ret = 1;

3924
	WARN_ON(!path->keep_locks);
3925 3926 3927
again:
	cur = btrfs_lock_root_node(root);
	level = btrfs_header_level(cur);
3928
	WARN_ON(path->nodes[level]);
3929 3930 3931 3932 3933 3934 3935
	path->nodes[level] = cur;
	path->locks[level] = 1;

	if (btrfs_header_generation(cur) < min_trans) {
		ret = 1;
		goto out;
	}
C
Chris Mason 已提交
3936
	while (1) {
3937 3938
		nritems = btrfs_header_nritems(cur);
		level = btrfs_header_level(cur);
3939
		sret = bin_search(cur, min_key, level, &slot);
3940

3941 3942
		/* at the lowest level, we're done, setup the path and exit */
		if (level == path->lowest_level) {
3943 3944
			if (slot >= nritems)
				goto find_next_key;
3945 3946 3947 3948 3949
			ret = 0;
			path->slots[level] = slot;
			btrfs_item_key_to_cpu(cur, &found_key, slot);
			goto out;
		}
3950 3951
		if (sret && slot > 0)
			slot--;
3952 3953 3954 3955 3956
		/*
		 * check this node pointer against the cache_only and
		 * min_trans parameters.  If it isn't in cache or is too
		 * old, skip to the next one.
		 */
C
Chris Mason 已提交
3957
		while (slot < nritems) {
3958 3959 3960
			u64 blockptr;
			u64 gen;
			struct extent_buffer *tmp;
3961 3962
			struct btrfs_disk_key disk_key;

3963 3964 3965 3966 3967 3968 3969 3970 3971
			blockptr = btrfs_node_blockptr(cur, slot);
			gen = btrfs_node_ptr_generation(cur, slot);
			if (gen < min_trans) {
				slot++;
				continue;
			}
			if (!cache_only)
				break;

3972 3973 3974 3975 3976 3977 3978 3979
			if (max_key) {
				btrfs_node_key(cur, &disk_key, slot);
				if (comp_keys(&disk_key, max_key) >= 0) {
					ret = 1;
					goto out;
				}
			}

3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990
			tmp = btrfs_find_tree_block(root, blockptr,
					    btrfs_level_size(root, level - 1));

			if (tmp && btrfs_buffer_uptodate(tmp, gen)) {
				free_extent_buffer(tmp);
				break;
			}
			if (tmp)
				free_extent_buffer(tmp);
			slot++;
		}
3991
find_next_key:
3992 3993 3994 3995 3996
		/*
		 * we didn't find a candidate key in this node, walk forward
		 * and find another one
		 */
		if (slot >= nritems) {
3997
			path->slots[level] = slot;
3998
			btrfs_set_path_blocking(path);
3999
			sret = btrfs_find_next_key(root, path, min_key, level,
4000
						  cache_only, min_trans);
4001
			if (sret == 0) {
4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015
				btrfs_release_path(root, path);
				goto again;
			} else {
				goto out;
			}
		}
		/* save our key for returning back */
		btrfs_node_key_to_cpu(cur, &found_key, slot);
		path->slots[level] = slot;
		if (level == path->lowest_level) {
			ret = 0;
			unlock_up(path, level, 1);
			goto out;
		}
4016
		btrfs_set_path_blocking(path);
4017 4018 4019
		cur = read_node_slot(root, cur, slot);

		btrfs_tree_lock(cur);
4020

4021 4022 4023
		path->locks[level - 1] = 1;
		path->nodes[level - 1] = cur;
		unlock_up(path, level, 1);
4024
		btrfs_clear_path_blocking(path, NULL);
4025 4026 4027 4028
	}
out:
	if (ret == 0)
		memcpy(min_key, &found_key, sizeof(found_key));
4029
	btrfs_set_path_blocking(path);
4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044
	return ret;
}

/*
 * this is similar to btrfs_next_leaf, but does not try to preserve
 * and fixup the path.  It looks for and returns the next key in the
 * tree based on the current path and the cache_only and min_trans
 * parameters.
 *
 * 0 is returned if another key is found, < 0 if there are any errors
 * and 1 is returned if there are no higher keys in the tree
 *
 * path->keep_locks should be set to 1 on the search made before
 * calling this function.
 */
4045
int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4046
			struct btrfs_key *key, int level,
4047
			int cache_only, u64 min_trans)
4048 4049 4050 4051
{
	int slot;
	struct extent_buffer *c;

4052
	WARN_ON(!path->keep_locks);
C
Chris Mason 已提交
4053
	while (level < BTRFS_MAX_LEVEL) {
4054 4055 4056 4057 4058
		if (!path->nodes[level])
			return 1;

		slot = path->slots[level] + 1;
		c = path->nodes[level];
4059
next:
4060
		if (slot >= btrfs_header_nritems(c)) {
4061 4062 4063 4064 4065
			int ret;
			int orig_lowest;
			struct btrfs_key cur_key;
			if (level + 1 >= BTRFS_MAX_LEVEL ||
			    !path->nodes[level + 1])
4066
				return 1;
4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092

			if (path->locks[level + 1]) {
				level++;
				continue;
			}

			slot = btrfs_header_nritems(c) - 1;
			if (level == 0)
				btrfs_item_key_to_cpu(c, &cur_key, slot);
			else
				btrfs_node_key_to_cpu(c, &cur_key, slot);

			orig_lowest = path->lowest_level;
			btrfs_release_path(root, path);
			path->lowest_level = level;
			ret = btrfs_search_slot(NULL, root, &cur_key, path,
						0, 0);
			path->lowest_level = orig_lowest;
			if (ret < 0)
				return ret;

			c = path->nodes[level];
			slot = path->slots[level];
			if (ret == 0)
				slot++;
			goto next;
4093
		}
4094

4095 4096
		if (level == 0)
			btrfs_item_key_to_cpu(c, key, slot);
4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116
		else {
			u64 blockptr = btrfs_node_blockptr(c, slot);
			u64 gen = btrfs_node_ptr_generation(c, slot);

			if (cache_only) {
				struct extent_buffer *cur;
				cur = btrfs_find_tree_block(root, blockptr,
					    btrfs_level_size(root, level - 1));
				if (!cur || !btrfs_buffer_uptodate(cur, gen)) {
					slot++;
					if (cur)
						free_extent_buffer(cur);
					goto next;
				}
				free_extent_buffer(cur);
			}
			if (gen < min_trans) {
				slot++;
				goto next;
			}
4117
			btrfs_node_key_to_cpu(c, key, slot);
4118
		}
4119 4120 4121 4122 4123
		return 0;
	}
	return 1;
}

C
Chris Mason 已提交
4124
/*
4125
 * search the tree again to find a leaf with greater keys
C
Chris Mason 已提交
4126 4127
 * returns 0 if it found something or 1 if there are no greater leaves.
 * returns < 0 on io errors.
C
Chris Mason 已提交
4128
 */
C
Chris Mason 已提交
4129
int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
4130 4131
{
	int slot;
4132
	int level;
4133
	struct extent_buffer *c;
4134
	struct extent_buffer *next;
4135 4136 4137
	struct btrfs_key key;
	u32 nritems;
	int ret;
4138 4139
	int old_spinning = path->leave_spinning;
	int force_blocking = 0;
4140 4141

	nritems = btrfs_header_nritems(path->nodes[0]);
C
Chris Mason 已提交
4142
	if (nritems == 0)
4143 4144
		return 1;

4145 4146 4147 4148 4149 4150 4151
	/*
	 * we take the blocks in an order that upsets lockdep.  Using
	 * blocking mode is the only way around it.
	 */
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	force_blocking = 1;
#endif
4152

4153 4154 4155 4156
	btrfs_item_key_to_cpu(path->nodes[0], &key, nritems - 1);
again:
	level = 1;
	next = NULL;
4157
	btrfs_release_path(root, path);
4158

4159
	path->keep_locks = 1;
4160 4161 4162 4163

	if (!force_blocking)
		path->leave_spinning = 1;

4164 4165 4166 4167 4168 4169
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	path->keep_locks = 0;

	if (ret < 0)
		return ret;

4170
	nritems = btrfs_header_nritems(path->nodes[0]);
4171 4172 4173 4174 4175 4176
	/*
	 * by releasing the path above we dropped all our locks.  A balance
	 * could have added more items next to the key that used to be
	 * at the very end of the block.  So, check again here and
	 * advance the path if there are now more items available.
	 */
4177
	if (nritems > 0 && path->slots[0] < nritems - 1) {
4178 4179
		if (ret == 0)
			path->slots[0]++;
4180
		ret = 0;
4181 4182
		goto done;
	}
4183

C
Chris Mason 已提交
4184
	while (level < BTRFS_MAX_LEVEL) {
4185 4186 4187 4188
		if (!path->nodes[level]) {
			ret = 1;
			goto done;
		}
4189

4190 4191
		slot = path->slots[level] + 1;
		c = path->nodes[level];
4192
		if (slot >= btrfs_header_nritems(c)) {
4193
			level++;
4194 4195 4196 4197
			if (level == BTRFS_MAX_LEVEL) {
				ret = 1;
				goto done;
			}
4198 4199
			continue;
		}
4200

4201 4202
		if (next) {
			btrfs_tree_unlock(next);
4203
			free_extent_buffer(next);
4204
		}
4205

4206 4207 4208 4209 4210
		next = c;
		ret = read_block_for_search(NULL, root, path, &next, level,
					    slot, &key);
		if (ret == -EAGAIN)
			goto again;
4211

4212 4213 4214 4215 4216
		if (ret < 0) {
			btrfs_release_path(root, path);
			goto done;
		}

4217
		if (!path->skip_locking) {
4218 4219 4220 4221 4222 4223 4224 4225 4226
			ret = btrfs_try_spin_lock(next);
			if (!ret) {
				btrfs_set_path_blocking(path);
				btrfs_tree_lock(next);
				if (!force_blocking)
					btrfs_clear_path_blocking(path, next);
			}
			if (force_blocking)
				btrfs_set_lock_blocking(next);
4227
		}
4228 4229 4230
		break;
	}
	path->slots[level] = slot;
C
Chris Mason 已提交
4231
	while (1) {
4232 4233
		level--;
		c = path->nodes[level];
4234 4235
		if (path->locks[level])
			btrfs_tree_unlock(c);
4236

4237
		free_extent_buffer(c);
4238 4239
		path->nodes[level] = next;
		path->slots[level] = 0;
4240 4241
		if (!path->skip_locking)
			path->locks[level] = 1;
4242

4243 4244
		if (!level)
			break;
4245

4246 4247 4248 4249 4250
		ret = read_block_for_search(NULL, root, path, &next, level,
					    0, &key);
		if (ret == -EAGAIN)
			goto again;

4251 4252 4253 4254 4255
		if (ret < 0) {
			btrfs_release_path(root, path);
			goto done;
		}

4256
		if (!path->skip_locking) {
4257
			btrfs_assert_tree_locked(path->nodes[level]);
4258 4259 4260 4261 4262 4263 4264 4265 4266
			ret = btrfs_try_spin_lock(next);
			if (!ret) {
				btrfs_set_path_blocking(path);
				btrfs_tree_lock(next);
				if (!force_blocking)
					btrfs_clear_path_blocking(path, next);
			}
			if (force_blocking)
				btrfs_set_lock_blocking(next);
4267
		}
4268
	}
4269
	ret = 0;
4270 4271
done:
	unlock_up(path, 0, 1);
4272 4273 4274 4275 4276
	path->leave_spinning = old_spinning;
	if (!old_spinning)
		btrfs_set_path_blocking(path);

	return ret;
4277
}
4278

4279 4280 4281 4282 4283 4284
/*
 * this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
 * searching until it gets past min_objectid or finds an item of 'type'
 *
 * returns 0 if something is found, 1 if nothing was found and < 0 on error
 */
4285 4286 4287 4288 4289 4290
int btrfs_previous_item(struct btrfs_root *root,
			struct btrfs_path *path, u64 min_objectid,
			int type)
{
	struct btrfs_key found_key;
	struct extent_buffer *leaf;
4291
	u32 nritems;
4292 4293
	int ret;

C
Chris Mason 已提交
4294
	while (1) {
4295
		if (path->slots[0] == 0) {
4296
			btrfs_set_path_blocking(path);
4297 4298 4299 4300 4301 4302 4303
			ret = btrfs_prev_leaf(root, path);
			if (ret != 0)
				return ret;
		} else {
			path->slots[0]--;
		}
		leaf = path->nodes[0];
4304 4305 4306 4307 4308 4309
		nritems = btrfs_header_nritems(leaf);
		if (nritems == 0)
			return 1;
		if (path->slots[0] == nritems)
			path->slots[0]--;

4310 4311 4312
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.type == type)
			return 0;
4313 4314 4315 4316 4317
		if (found_key.objectid < min_objectid)
			break;
		if (found_key.objectid == min_objectid &&
		    found_key.type < type)
			break;
4318 4319 4320
	}
	return 1;
}