ctree.c 72.3 KB
Newer Older
C
Chris Mason 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * Copyright (C) 2007 Oracle.  All rights reserved.
 *
 * 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

25 26 27
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
28
		      *root, struct btrfs_key *ins_key,
29
		      struct btrfs_path *path, int data_size, int extend);
30 31 32 33 34 35 36
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct extent_buffer *dst,
			  struct extent_buffer *src);
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
			      struct extent_buffer *dst_buf,
			      struct extent_buffer *src_buf);
37 38
static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		   struct btrfs_path *path, int level, int slot);
39

40
inline void btrfs_init_path(struct btrfs_path *p)
41
{
42
	memset(p, 0, sizeof(*p));
43 44
}

45
struct btrfs_path *btrfs_alloc_path(void)
46
{
47 48
	struct btrfs_path *path;
	path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
49
	if (path) {
50
		btrfs_init_path(path);
51 52
		path->reada = 1;
	}
53
	return path;
54 55
}

56
void btrfs_free_path(struct btrfs_path *p)
57
{
58 59
	btrfs_release_path(NULL, p);
	kmem_cache_free(btrfs_path_cachep, p);
60 61
}

62
void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
63 64
{
	int i;
65
	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
66 67
		if (!p->nodes[i])
			break;
68
		free_extent_buffer(p->nodes[i]);
69
	}
C
Chris Mason 已提交
70
	memset(p, 0, sizeof(*p));
71 72
}

73 74 75 76 77 78 79 80
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);
	}
}

81 82 83 84 85 86 87 88 89 90
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;
	struct btrfs_key first_key;
91
	struct btrfs_root *new_root;
92

93 94 95 96 97 98
	new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
	if (!new_root)
		return -ENOMEM;

	memcpy(new_root, root, sizeof(*new_root));
	new_root->root_key.objectid = new_root_objectid;
99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

	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);
	if (nritems) {
		if (level == 0)
			btrfs_item_key_to_cpu(buf, &first_key, 0);
		else
			btrfs_node_key_to_cpu(buf, &first_key, 0);
	} else {
		first_key.objectid = 0;
	}
114
	cow = __btrfs_alloc_free_block(trans, new_root, buf->len,
115 116 117
				       new_root_objectid,
				       trans->transid, first_key.objectid,
				       level, buf->start, 0);
118 119
	if (IS_ERR(cow)) {
		kfree(new_root);
120
		return PTR_ERR(cow);
121
	}
122 123 124 125 126

	copy_extent_buffer(cow, buf, 0, 0, cow->len);
	btrfs_set_header_bytenr(cow, cow->start);
	btrfs_set_header_generation(cow, trans->transid);
	btrfs_set_header_owner(cow, new_root_objectid);
127
	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
128 129

	WARN_ON(btrfs_header_generation(buf) > trans->transid);
130 131 132
	ret = btrfs_inc_ref(trans, new_root, buf);
	kfree(new_root);

133 134 135 136 137 138 139 140 141
	if (ret)
		return ret;

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

int __btrfs_cow_block(struct btrfs_trans_handle *trans,
142 143 144 145 146
			     struct btrfs_root *root,
			     struct extent_buffer *buf,
			     struct extent_buffer *parent, int parent_slot,
			     struct extent_buffer **cow_ret,
			     u64 search_start, u64 empty_size)
147
{
148
	u64 root_gen;
149
	struct extent_buffer *cow;
150
	u32 nritems;
151 152
	int ret = 0;
	int different_trans = 0;
153 154 155 156 157 158 159 160
	int level;
	struct btrfs_key first_key;

	if (root->ref_cows) {
		root_gen = trans->transid;
	} else {
		root_gen = 0;
	}
161 162
	if (!(buf->flags & EXTENT_CSUM))
		WARN_ON(1);
163

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

168 169 170 171 172 173 174 175 176 177 178 179 180
	level = btrfs_header_level(buf);
	nritems = btrfs_header_nritems(buf);
	if (nritems) {
		if (level == 0)
			btrfs_item_key_to_cpu(buf, &first_key, 0);
		else
			btrfs_node_key_to_cpu(buf, &first_key, 0);
	} else {
		first_key.objectid = 0;
	}
	cow = __btrfs_alloc_free_block(trans, root, buf->len,
				     root->root_key.objectid,
				     root_gen, first_key.objectid, level,
181
				     search_start, empty_size);
182 183
	if (IS_ERR(cow))
		return PTR_ERR(cow);
184

185
	copy_extent_buffer(cow, buf, 0, 0, cow->len);
186
	btrfs_set_header_bytenr(cow, cow->start);
187 188
	btrfs_set_header_generation(cow, trans->transid);
	btrfs_set_header_owner(cow, root->root_key.objectid);
189
	btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
190

191 192
	WARN_ON(btrfs_header_generation(buf) > trans->transid);
	if (btrfs_header_generation(buf) != trans->transid) {
193 194 195 196 197 198 199 200
		different_trans = 1;
		ret = btrfs_inc_ref(trans, root, buf);
		if (ret)
			return ret;
	} else {
		clean_tree_block(trans, root, buf);
	}

201
	if (buf == root->node) {
202
		root_gen = btrfs_header_generation(buf);
203
		root->node = cow;
204
		extent_buffer_get(cow);
205
		if (buf != root->commit_root) {
206
			btrfs_free_extent(trans, root, buf->start,
207 208
					  buf->len, root->root_key.objectid,
					  root_gen, 0, 0, 1);
209
		}
210
		free_extent_buffer(buf);
211
		add_root_to_dirty_list(root);
212
	} else {
213
		root_gen = btrfs_header_generation(parent);
214
		btrfs_set_node_blockptr(parent, parent_slot,
215
					cow->start);
216 217 218
		WARN_ON(trans->transid == 0);
		btrfs_set_node_ptr_generation(parent, parent_slot,
					      trans->transid);
219
		btrfs_mark_buffer_dirty(parent);
220
		WARN_ON(btrfs_header_generation(parent) != trans->transid);
221 222 223
		btrfs_free_extent(trans, root, buf->start, buf->len,
				  btrfs_header_owner(parent), root_gen,
				  0, 0, 1);
224
	}
225
	free_extent_buffer(buf);
C
Chris Mason 已提交
226
	btrfs_mark_buffer_dirty(cow);
227
	*cow_ret = cow;
228 229 230
	return 0;
}

231 232 233 234
int btrfs_cow_block(struct btrfs_trans_handle *trans,
		    struct btrfs_root *root, struct extent_buffer *buf,
		    struct extent_buffer *parent, int parent_slot,
		    struct extent_buffer **cow_ret)
235 236
{
	u64 search_start;
237
	u64 header_trans;
238
	int ret;
239

240 241 242 243 244 245 246 247 248 249
	if (trans->transaction != root->fs_info->running_transaction) {
		printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
		       root->fs_info->running_transaction->transid);
		WARN_ON(1);
	}
	if (trans->transid != root->fs_info->generation) {
		printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
		       root->fs_info->generation);
		WARN_ON(1);
	}
250 251
	if (!(buf->flags & EXTENT_CSUM))
		WARN_ON(1);
252 253

	header_trans = btrfs_header_generation(buf);
254 255 256
	spin_lock(&root->fs_info->hash_lock);
	if (header_trans == trans->transid &&
	    !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
257
		*cow_ret = buf;
258
		spin_unlock(&root->fs_info->hash_lock);
259 260
		return 0;
	}
261
	spin_unlock(&root->fs_info->hash_lock);
262
	search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
263
	ret = __btrfs_cow_block(trans, root, buf, parent,
264
				 parent_slot, cow_ret, search_start, 0);
265
	return ret;
266 267
}

268
static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
269
{
270
	if (blocknr < other && other - (blocknr + blocksize) < 32768)
271
		return 1;
272
	if (blocknr > other && blocknr - (other + blocksize) < 32768)
273 274 275 276
		return 1;
	return 0;
}

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
/*
 * 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;
}


302
int btrfs_realloc_node(struct btrfs_trans_handle *trans,
303
		       struct btrfs_root *root, struct extent_buffer *parent,
304 305
		       int start_slot, int cache_only, u64 *last_ret,
		       struct btrfs_key *progress)
306
{
307 308
	struct extent_buffer *cur;
	struct extent_buffer *tmp;
309
	u64 blocknr;
310 311
	u64 search_start = *last_ret;
	u64 last_block = 0;
312 313 314 315 316
	u64 other;
	u32 parent_nritems;
	int end_slot;
	int i;
	int err = 0;
317
	int parent_level;
318 319
	int uptodate;
	u32 blocksize;
320 321
	int progress_passed = 0;
	struct btrfs_disk_key disk_key;
322

323 324 325 326
	parent_level = btrfs_header_level(parent);
	if (cache_only && parent_level != 1)
		return 0;

327 328 329 330 331 332 333 334 335 336
	if (trans->transaction != root->fs_info->running_transaction) {
		printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
		       root->fs_info->running_transaction->transid);
		WARN_ON(1);
	}
	if (trans->transid != root->fs_info->generation) {
		printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
		       root->fs_info->generation);
		WARN_ON(1);
	}
337

338 339
	parent_nritems = btrfs_header_nritems(parent);
	blocksize = btrfs_level_size(root, parent_level - 1);
340 341 342 343 344 345 346
	end_slot = parent_nritems;

	if (parent_nritems == 1)
		return 0;

	for (i = start_slot; i < end_slot; i++) {
		int close = 1;
347

348 349 350 351 352 353 354 355
		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);
		}
356 357 358 359 360
		btrfs_node_key(parent, &disk_key, i);
		if (!progress_passed && comp_keys(&disk_key, progress) < 0)
			continue;

		progress_passed = 1;
361
		blocknr = btrfs_node_blockptr(parent, i);
362 363
		if (last_block == 0)
			last_block = blocknr;
364

365
		if (i > 0) {
366 367
			other = btrfs_node_blockptr(parent, i - 1);
			close = close_blocks(blocknr, other, blocksize);
368
		}
369
		if (close && i < end_slot - 2) {
370 371
			other = btrfs_node_blockptr(parent, i + 1);
			close = close_blocks(blocknr, other, blocksize);
372
		}
373 374
		if (close) {
			last_block = blocknr;
375
			continue;
376
		}
377 378 379 380 381
		if (parent->map_token) {
			unmap_extent_buffer(parent, parent->map_token,
					    KM_USER1);
			parent->map_token = NULL;
		}
382

383 384 385 386 387
		cur = btrfs_find_tree_block(root, blocknr, blocksize);
		if (cur)
			uptodate = btrfs_buffer_uptodate(cur);
		else
			uptodate = 0;
388
		if (!cur || !uptodate) {
389
			if (cache_only) {
390
				free_extent_buffer(cur);
391 392
				continue;
			}
393 394 395 396 397
			if (!cur) {
				cur = read_tree_block(root, blocknr,
							 blocksize);
			} else if (!uptodate) {
				btrfs_read_buffer(cur);
398
			}
399
		}
400
		if (search_start == 0)
401
			search_start = last_block;
402

403
		btrfs_verify_block_csum(root, cur);
404 405 406 407
		err = __btrfs_cow_block(trans, root, cur, parent, i,
					&tmp, search_start,
					min(16 * blocksize,
					    (end_slot - i) * blocksize));
Y
Yan 已提交
408
		if (err) {
409
			free_extent_buffer(cur);
410
			break;
Y
Yan 已提交
411
		}
412
		search_start = tmp->start;
413
		last_block = tmp->start;
414 415
		*last_ret = search_start;
		if (parent_level == 1)
416 417
			btrfs_clear_buffer_defrag(tmp);
		free_extent_buffer(tmp);
418
	}
419 420 421 422 423
	if (parent->map_token) {
		unmap_extent_buffer(parent, parent->map_token,
				    KM_USER1);
		parent->map_token = NULL;
	}
424 425 426
	return err;
}

C
Chris Mason 已提交
427 428 429 430 431
/*
 * 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
 */
432
static inline unsigned int leaf_data_end(struct btrfs_root *root,
433
					 struct extent_buffer *leaf)
434
{
435
	u32 nr = btrfs_header_nritems(leaf);
436
	if (nr == 0)
437
		return BTRFS_LEAF_DATA_SIZE(root);
438
	return btrfs_item_offset_nr(leaf, nr - 1);
439 440
}

441 442
static int check_node(struct btrfs_root *root, struct btrfs_path *path,
		      int level)
C
Chris Mason 已提交
443
{
444 445 446 447
	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 已提交
448
	int parent_slot;
449 450
	int slot;
	struct btrfs_key cpukey;
451
	u32 nritems = btrfs_header_nritems(node);
C
Chris Mason 已提交
452 453

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

456
	slot = path->slots[level];
457 458
	BUG_ON(nritems == 0);
	if (parent) {
A
Aneesh 已提交
459
		parent_slot = path->slots[level + 1];
460 461 462
		btrfs_node_key(parent, &parent_key, parent_slot);
		btrfs_node_key(node, &node_key, 0);
		BUG_ON(memcmp(&parent_key, &node_key,
463
			      sizeof(struct btrfs_disk_key)));
464
		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
465
		       btrfs_header_bytenr(node));
C
Chris Mason 已提交
466
	}
467
	BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
468
	if (slot != 0) {
469 470 471
		btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
		btrfs_node_key(node, &node_key, slot);
		BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
472 473
	}
	if (slot < nritems - 1) {
474 475 476
		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 已提交
477 478 479 480
	}
	return 0;
}

481 482
static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
		      int level)
C
Chris Mason 已提交
483
{
484 485
	struct extent_buffer *leaf = path->nodes[level];
	struct extent_buffer *parent = NULL;
C
Chris Mason 已提交
486
	int parent_slot;
487
	struct btrfs_key cpukey;
488 489 490
	struct btrfs_disk_key parent_key;
	struct btrfs_disk_key leaf_key;
	int slot = path->slots[0];
491

492
	u32 nritems = btrfs_header_nritems(leaf);
C
Chris Mason 已提交
493 494

	if (path->nodes[level + 1])
495
		parent = path->nodes[level + 1];
496 497 498 499 500

	if (nritems == 0)
		return 0;

	if (parent) {
A
Aneesh 已提交
501
		parent_slot = path->slots[level + 1];
502 503
		btrfs_node_key(parent, &parent_key, parent_slot);
		btrfs_item_key(leaf, &leaf_key, 0);
504

505
		BUG_ON(memcmp(&parent_key, &leaf_key,
506
		       sizeof(struct btrfs_disk_key)));
507
		BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
508
		       btrfs_header_bytenr(leaf));
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533
	}
#if 0
	for (i = 0; nritems > 1 && i < nritems - 2; i++) {
		btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
		btrfs_item_key(leaf, &leaf_key, i);
		if (comp_keys(&leaf_key, &cpukey) >= 0) {
			btrfs_print_leaf(root, leaf);
			printk("slot %d offset bad key\n", i);
			BUG_ON(1);
		}
		if (btrfs_item_offset_nr(leaf, i) !=
			btrfs_item_end_nr(leaf, i + 1)) {
			btrfs_print_leaf(root, leaf);
			printk("slot %d offset bad\n", i);
			BUG_ON(1);
		}
		if (i == 0) {
			if (btrfs_item_offset_nr(leaf, i) +
			       btrfs_item_size_nr(leaf, i) !=
			       BTRFS_LEAF_DATA_SIZE(root)) {
				btrfs_print_leaf(root, leaf);
				printk("slot %d first offset bad\n", i);
				BUG_ON(1);
			}
		}
C
Chris Mason 已提交
534
	}
535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556
	if (nritems > 0) {
		if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
				btrfs_print_leaf(root, leaf);
				printk("slot %d bad size \n", nritems - 1);
				BUG_ON(1);
		}
	}
#endif
	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);
			printk("slot %d offset bad key\n", slot);
			BUG_ON(1);
		}
		if (btrfs_item_offset_nr(leaf, slot - 1) !=
		       btrfs_item_end_nr(leaf, slot)) {
			btrfs_print_leaf(root, leaf);
			printk("slot %d offset bad\n", slot);
			BUG_ON(1);
		}
557 558
	}
	if (slot < nritems - 1) {
559 560 561 562 563 564 565 566 567
		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);
			printk("slot %d offset bad\n", slot);
			BUG_ON(1);
		}
C
Chris Mason 已提交
568
	}
569 570
	BUG_ON(btrfs_item_offset_nr(leaf, 0) +
	       btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
C
Chris Mason 已提交
571 572 573
	return 0;
}

574 575
static int noinline check_block(struct btrfs_root *root,
				struct btrfs_path *path, int level)
C
Chris Mason 已提交
576
{
577
	return 0;
578
#if 0
579 580
	struct extent_buffer *buf = path->nodes[level];

581 582 583
	if (memcmp_extent_buffer(buf, root->fs_info->fsid,
				 (unsigned long)btrfs_header_fsid(buf),
				 BTRFS_FSID_SIZE)) {
584
		printk("warning bad block %Lu\n", buf->start);
585
		return 1;
586
	}
587
#endif
C
Chris Mason 已提交
588
	if (level == 0)
589 590
		return check_leaf(root, path, level);
	return check_node(root, path, level);
C
Chris Mason 已提交
591 592
}

C
Chris Mason 已提交
593
/*
594 595 596
 * 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 已提交
597 598 599 600 601 602
 * 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
 */
603 604 605
static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
			      int item_size, struct btrfs_key *key,
			      int max, int *slot)
606 607 608 609 610
{
	int low = 0;
	int high = max;
	int mid;
	int ret;
611
	struct btrfs_disk_key *tmp = NULL;
612 613 614 615 616 617
	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;
618
	int err;
619 620 621

	while(low < high) {
		mid = (low + high) / 2;
622 623 624 625 626
		offset = p + mid * item_size;

		if (!map_token || offset < map_start ||
		    (offset + sizeof(struct btrfs_disk_key)) >
		    map_start + map_len) {
627
			if (map_token) {
628
				unmap_extent_buffer(eb, map_token, KM_USER0);
629 630 631 632 633 634 635 636 637 638 639 640 641 642 643
				map_token = NULL;
			}
			err = map_extent_buffer(eb, offset,
						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;
			}
644 645 646 647 648

		} else {
			tmp = (struct btrfs_disk_key *)(kaddr + offset -
							map_start);
		}
649 650 651 652 653 654 655 656
		ret = comp_keys(tmp, key);

		if (ret < 0)
			low = mid + 1;
		else if (ret > 0)
			high = mid;
		else {
			*slot = mid;
657 658
			if (map_token)
				unmap_extent_buffer(eb, map_token, KM_USER0);
659 660 661 662
			return 0;
		}
	}
	*slot = low;
663 664
	if (map_token)
		unmap_extent_buffer(eb, map_token, KM_USER0);
665 666 667
	return 1;
}

C
Chris Mason 已提交
668 669 670 671
/*
 * simple bin_search frontend that does the right thing for
 * leaves vs nodes
 */
672 673
static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
		      int level, int *slot)
674
{
675 676 677
	if (level == 0) {
		return generic_bin_search(eb,
					  offsetof(struct btrfs_leaf, items),
678
					  sizeof(struct btrfs_item),
679
					  key, btrfs_header_nritems(eb),
680
					  slot);
681
	} else {
682 683
		return generic_bin_search(eb,
					  offsetof(struct btrfs_node, ptrs),
684
					  sizeof(struct btrfs_key_ptr),
685
					  key, btrfs_header_nritems(eb),
686
					  slot);
687 688 689 690
	}
	return -1;
}

691 692
static struct extent_buffer *read_node_slot(struct btrfs_root *root,
				   struct extent_buffer *parent, int slot)
693 694 695
{
	if (slot < 0)
		return NULL;
696
	if (slot >= btrfs_header_nritems(parent))
697
		return NULL;
698 699
	return read_tree_block(root, btrfs_node_blockptr(parent, slot),
		       btrfs_level_size(root, btrfs_header_level(parent) - 1));
700 701
}

702 703 704
static int balance_level(struct btrfs_trans_handle *trans,
			 struct btrfs_root *root,
			 struct btrfs_path *path, int level)
705
{
706 707 708 709
	struct extent_buffer *right = NULL;
	struct extent_buffer *mid;
	struct extent_buffer *left = NULL;
	struct extent_buffer *parent = NULL;
710 711 712 713
	int ret = 0;
	int wret;
	int pslot;
	int orig_slot = path->slots[level];
714
	int err_on_enospc = 0;
715
	u64 orig_ptr;
716 717 718 719

	if (level == 0)
		return 0;

720
	mid = path->nodes[level];
721 722
	WARN_ON(btrfs_header_generation(mid) != trans->transid);

723
	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
724

725
	if (level < BTRFS_MAX_LEVEL - 1)
726
		parent = path->nodes[level + 1];
727 728
	pslot = path->slots[level + 1];

C
Chris Mason 已提交
729 730 731 732
	/*
	 * deal with the case where there is only one pointer in the root
	 * by promoting the node below to a root
	 */
733 734
	if (!parent) {
		struct extent_buffer *child;
735

736
		if (btrfs_header_nritems(mid) != 1)
737 738 739
			return 0;

		/* promote the child to a root */
740
		child = read_node_slot(root, mid, 0);
741
		BUG_ON(!child);
742 743 744
		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
		BUG_ON(ret);

745
		root->node = child;
746
		add_root_to_dirty_list(root);
747
		path->nodes[level] = NULL;
748 749
		clean_tree_block(trans, root, mid);
		wait_on_tree_block_writeback(root, mid);
750
		/* once for the path */
751
		free_extent_buffer(mid);
752 753 754
		ret = btrfs_free_extent(trans, root, mid->start, mid->len,
					root->root_key.objectid,
					btrfs_header_generation(mid), 0, 0, 1);
755
		/* once for the root ptr */
756
		free_extent_buffer(mid);
757
		return ret;
758
	}
759
	if (btrfs_header_nritems(mid) >
760
	    BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
761 762
		return 0;

763
	if (btrfs_header_nritems(mid) < 2)
764 765
		err_on_enospc = 1;

766 767 768 769
	left = read_node_slot(root, parent, pslot - 1);
	if (left) {
		wret = btrfs_cow_block(trans, root, left,
				       parent, pslot - 1, &left);
770 771 772 773
		if (wret) {
			ret = wret;
			goto enospc;
		}
774
	}
775 776 777 778
	right = read_node_slot(root, parent, pslot + 1);
	if (right) {
		wret = btrfs_cow_block(trans, root, right,
				       parent, pslot + 1, &right);
779 780 781 782 783 784 785
		if (wret) {
			ret = wret;
			goto enospc;
		}
	}

	/* first, try to make some room in the middle buffer */
786 787 788
	if (left) {
		orig_slot += btrfs_header_nritems(left);
		wret = push_node_left(trans, root, left, mid);
789 790
		if (wret < 0)
			ret = wret;
791
		if (btrfs_header_nritems(mid) < 2)
792
			err_on_enospc = 1;
793
	}
794 795 796 797

	/*
	 * then try to empty the right most buffer into the middle
	 */
798 799
	if (right) {
		wret = push_node_left(trans, root, mid, right);
800
		if (wret < 0 && wret != -ENOSPC)
801
			ret = wret;
802
		if (btrfs_header_nritems(right) == 0) {
803
			u64 bytenr = right->start;
804
			u64 generation = btrfs_header_generation(parent);
805 806
			u32 blocksize = right->len;

807 808 809
			clean_tree_block(trans, root, right);
			wait_on_tree_block_writeback(root, right);
			free_extent_buffer(right);
810
			right = NULL;
811 812
			wret = del_ptr(trans, root, path, level + 1, pslot +
				       1);
813 814
			if (wret)
				ret = wret;
815
			wret = btrfs_free_extent(trans, root, bytenr,
816 817 818
						 blocksize,
						 btrfs_header_owner(parent),
						 generation, 0, 0, 1);
819 820 821
			if (wret)
				ret = wret;
		} else {
822 823 824 825
			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);
826 827
		}
	}
828
	if (btrfs_header_nritems(mid) == 1) {
829 830 831 832 833 834 835 836 837
		/*
		 * 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
		 */
838 839
		BUG_ON(!left);
		wret = balance_node_right(trans, root, mid, left);
840
		if (wret < 0) {
841
			ret = wret;
842 843
			goto enospc;
		}
844 845
		BUG_ON(wret == 1);
	}
846
	if (btrfs_header_nritems(mid) == 0) {
847
		/* we've managed to empty the middle node, drop it */
848
		u64 root_gen = btrfs_header_generation(parent);
849 850
		u64 bytenr = mid->start;
		u32 blocksize = mid->len;
851 852 853
		clean_tree_block(trans, root, mid);
		wait_on_tree_block_writeback(root, mid);
		free_extent_buffer(mid);
854
		mid = NULL;
855
		wret = del_ptr(trans, root, path, level + 1, pslot);
856 857
		if (wret)
			ret = wret;
858 859 860
		wret = btrfs_free_extent(trans, root, bytenr, blocksize,
					 btrfs_header_owner(parent),
					 root_gen, 0, 0, 1);
861 862
		if (wret)
			ret = wret;
863 864
	} else {
		/* update the parent key to reflect our changes */
865 866 867 868
		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);
869
	}
870

871
	/* update the path */
872 873 874 875
	if (left) {
		if (btrfs_header_nritems(left) > orig_slot) {
			extent_buffer_get(left);
			path->nodes[level] = left;
876 877
			path->slots[level + 1] -= 1;
			path->slots[level] = orig_slot;
878 879
			if (mid)
				free_extent_buffer(mid);
880
		} else {
881
			orig_slot -= btrfs_header_nritems(left);
882 883 884
			path->slots[level] = orig_slot;
		}
	}
885
	/* double check we haven't messed things up */
886
	check_block(root, path, level);
887
	if (orig_ptr !=
888
	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
889
		BUG();
890
enospc:
891 892 893 894
	if (right)
		free_extent_buffer(right);
	if (left)
		free_extent_buffer(left);
895 896 897
	return ret;
}

898
/* returns zero if the push worked, non-zero otherwise */
899 900 901
static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
					  struct btrfs_root *root,
					  struct btrfs_path *path, int level)
902
{
903 904 905 906
	struct extent_buffer *right = NULL;
	struct extent_buffer *mid;
	struct extent_buffer *left = NULL;
	struct extent_buffer *parent = NULL;
907 908 909 910 911 912 913 914 915
	int ret = 0;
	int wret;
	int pslot;
	int orig_slot = path->slots[level];
	u64 orig_ptr;

	if (level == 0)
		return 1;

916
	mid = path->nodes[level];
917
	WARN_ON(btrfs_header_generation(mid) != trans->transid);
918 919 920
	orig_ptr = btrfs_node_blockptr(mid, orig_slot);

	if (level < BTRFS_MAX_LEVEL - 1)
921
		parent = path->nodes[level + 1];
922 923
	pslot = path->slots[level + 1];

924
	if (!parent)
925 926
		return 1;

927
	left = read_node_slot(root, parent, pslot - 1);
928 929

	/* first, try to make some room in the middle buffer */
930
	if (left) {
931
		u32 left_nr;
932
		left_nr = btrfs_header_nritems(left);
933 934 935
		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
			wret = 1;
		} else {
936 937
			ret = btrfs_cow_block(trans, root, left, parent,
					      pslot - 1, &left);
938 939 940 941
			if (ret)
				wret = 1;
			else {
				wret = push_node_left(trans, root,
942
						      left, mid);
943
			}
944
		}
945 946 947
		if (wret < 0)
			ret = wret;
		if (wret == 0) {
948
			struct btrfs_disk_key disk_key;
949
			orig_slot += left_nr;
950 951 952 953 954
			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;
955 956
				path->slots[level + 1] -= 1;
				path->slots[level] = orig_slot;
957
				free_extent_buffer(mid);
958 959
			} else {
				orig_slot -=
960
					btrfs_header_nritems(left);
961
				path->slots[level] = orig_slot;
962
				free_extent_buffer(left);
963 964 965
			}
			return 0;
		}
966
		free_extent_buffer(left);
967
	}
968
	right= read_node_slot(root, parent, pslot + 1);
969 970 971 972

	/*
	 * then try to empty the right most buffer into the middle
	 */
973
	if (right) {
974
		u32 right_nr;
975
		right_nr = btrfs_header_nritems(right);
976 977 978
		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
			wret = 1;
		} else {
979 980 981
			ret = btrfs_cow_block(trans, root, right,
					      parent, pslot + 1,
					      &right);
982 983 984 985
			if (ret)
				wret = 1;
			else {
				wret = balance_node_right(trans, root,
986
							  right, mid);
987
			}
988
		}
989 990 991
		if (wret < 0)
			ret = wret;
		if (wret == 0) {
992 993 994 995 996 997 998 999
			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;
1000 1001
				path->slots[level + 1] += 1;
				path->slots[level] = orig_slot -
1002 1003
					btrfs_header_nritems(mid);
				free_extent_buffer(mid);
1004
			} else {
1005
				free_extent_buffer(right);
1006 1007 1008
			}
			return 0;
		}
1009
		free_extent_buffer(right);
1010 1011 1012 1013
	}
	return 1;
}

1014 1015 1016 1017
/*
 * readahead one full node of leaves
 */
static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
1018
			     int level, int slot, u64 objectid)
1019
{
1020
	struct extent_buffer *node;
1021
	struct btrfs_disk_key disk_key;
1022 1023
	u32 nritems;
	u64 search;
1024 1025 1026
	u64 lowest_read;
	u64 highest_read;
	u64 nread = 0;
1027
	int direction = path->reada;
1028
	struct extent_buffer *eb;
1029 1030 1031
	u32 nr;
	u32 blocksize;
	u32 nscan = 0;
1032

1033
	if (level != 1)
1034 1035 1036
		return;

	if (!path->nodes[level])
1037 1038
		return;

1039
	node = path->nodes[level];
1040
	search = btrfs_node_blockptr(node, slot);
1041 1042
	blocksize = btrfs_level_size(root, level - 1);
	eb = btrfs_find_tree_block(root, search, blocksize);
1043 1044
	if (eb) {
		free_extent_buffer(eb);
1045 1046 1047
		return;
	}

1048 1049 1050
	highest_read = search;
	lowest_read = search;

1051
	nritems = btrfs_header_nritems(node);
1052
	nr = slot;
1053
	while(1) {
1054 1055 1056 1057 1058 1059 1060 1061
		if (direction < 0) {
			if (nr == 0)
				break;
			nr--;
		} else if (direction > 0) {
			nr++;
			if (nr >= nritems)
				break;
1062
		}
1063 1064 1065 1066 1067
		if (path->reada < 0 && objectid) {
			btrfs_node_key(node, &disk_key, nr);
			if (btrfs_disk_key_objectid(&disk_key) != objectid)
				break;
		}
1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084
		search = btrfs_node_blockptr(node, nr);
		if ((search >= lowest_read && search <= highest_read) ||
		    (search < lowest_read && lowest_read - search <= 32768) ||
		    (search > highest_read && search - highest_read <= 32768)) {
			readahead_tree_block(root, search, blocksize);
			nread += blocksize;
		}
		nscan++;
		if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
			break;
		if(nread > (1024 * 1024) || nscan > 128)
			break;

		if (search < lowest_read)
			lowest_read = search;
		if (search > highest_read)
			highest_read = search;
1085 1086
	}
}
C
Chris Mason 已提交
1087 1088 1089 1090 1091 1092
/*
 * 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 已提交
1093 1094
 * be inserted, and 1 is returned.  If there are other errors during the
 * search a negative error number is returned.
C
Chris Mason 已提交
1095 1096 1097 1098
 *
 * 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 已提交
1099
 */
1100 1101 1102
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)
1103
{
1104
	struct extent_buffer *b;
1105
	u64 bytenr;
1106
	u64 ptr_gen;
1107 1108 1109
	int slot;
	int ret;
	int level;
1110
	int should_reada = p->reada;
1111 1112
	u8 lowest_level = 0;

1113 1114
	lowest_level = p->lowest_level;
	WARN_ON(lowest_level && ins_len);
1115 1116
	WARN_ON(p->nodes[0] != NULL);
	WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1117 1118
again:
	b = root->node;
1119
	extent_buffer_get(b);
1120
	while (b) {
1121
		level = btrfs_header_level(b);
1122 1123
		if (cow) {
			int wret;
1124 1125 1126
			wret = btrfs_cow_block(trans, root, b,
					       p->nodes[level + 1],
					       p->slots[level + 1],
Y
Yan 已提交
1127
					       &b);
1128
			if (wret) {
1129
				free_extent_buffer(b);
1130 1131
				return wret;
			}
1132 1133
		}
		BUG_ON(!cow && ins_len);
1134
		if (level != btrfs_header_level(b))
1135
			WARN_ON(1);
1136
		level = btrfs_header_level(b);
1137
		p->nodes[level] = b;
1138
		ret = check_block(root, p, level);
C
Chris Mason 已提交
1139 1140
		if (ret)
			return -1;
1141 1142
		ret = bin_search(b, key, level, &slot);
		if (level != 0) {
1143 1144 1145
			if (ret && slot > 0)
				slot -= 1;
			p->slots[level] = slot;
1146
			if (ins_len > 0 && btrfs_header_nritems(b) >=
1147
			    BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1148
				int sret = split_node(trans, root, p, level);
1149 1150 1151 1152 1153
				BUG_ON(sret > 0);
				if (sret)
					return sret;
				b = p->nodes[level];
				slot = p->slots[level];
1154
			} else if (ins_len < 0) {
1155 1156
				int sret = balance_level(trans, root, p,
							 level);
1157 1158 1159
				if (sret)
					return sret;
				b = p->nodes[level];
1160 1161
				if (!b) {
					btrfs_release_path(NULL, p);
1162
					goto again;
1163
				}
1164
				slot = p->slots[level];
1165
				BUG_ON(btrfs_header_nritems(b) == 1);
1166
			}
1167 1168 1169
			/* this is only true while dropping a snapshot */
			if (level == lowest_level)
				break;
1170
			bytenr = btrfs_node_blockptr(b, slot);
1171
			ptr_gen = btrfs_node_ptr_generation(b, slot);
1172
			if (should_reada)
1173 1174
				reada_for_search(root, p, level, slot,
						 key->objectid);
1175 1176
			b = read_tree_block(root, bytenr,
					    btrfs_level_size(root, level - 1));
1177 1178 1179 1180 1181 1182 1183
			if (ptr_gen != btrfs_header_generation(b)) {
				printk("block %llu bad gen wanted %llu "
				       "found %llu\n",
			        (unsigned long long)b->start,
				(unsigned long long)ptr_gen,
			        (unsigned long long)btrfs_header_generation(b));
			}
1184 1185
		} else {
			p->slots[level] = slot;
1186
			if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1187
			    sizeof(struct btrfs_item) + ins_len) {
1188
				int sret = split_leaf(trans, root, key,
1189
						      p, ins_len, ret == 0);
1190 1191 1192 1193
				BUG_ON(sret > 0);
				if (sret)
					return sret;
			}
1194 1195 1196
			return ret;
		}
	}
C
Chris Mason 已提交
1197
	return 1;
1198 1199
}

C
Chris Mason 已提交
1200 1201 1202 1203 1204 1205
/*
 * 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 已提交
1206 1207 1208
 *
 * 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 已提交
1209
 */
1210 1211 1212
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)
1213 1214
{
	int i;
C
Chris Mason 已提交
1215
	int ret = 0;
1216 1217
	struct extent_buffer *t;

1218
	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1219
		int tslot = path->slots[i];
1220
		if (!path->nodes[i])
1221
			break;
1222 1223
		t = path->nodes[i];
		btrfs_set_node_key(t, key, tslot);
1224
		btrfs_mark_buffer_dirty(path->nodes[i]);
1225 1226 1227
		if (tslot != 0)
			break;
	}
C
Chris Mason 已提交
1228
	return ret;
1229 1230
}

C
Chris Mason 已提交
1231 1232
/*
 * try to push data from one node into the next node left in the
1233
 * tree.
C
Chris Mason 已提交
1234 1235 1236
 *
 * 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 已提交
1237
 */
1238 1239
static int push_node_left(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct extent_buffer *dst,
1240
			  struct extent_buffer *src)
1241 1242
{
	int push_items = 0;
1243 1244
	int src_nritems;
	int dst_nritems;
C
Chris Mason 已提交
1245
	int ret = 0;
1246

1247 1248
	src_nritems = btrfs_header_nritems(src);
	dst_nritems = btrfs_header_nritems(dst);
1249
	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1250 1251
	WARN_ON(btrfs_header_generation(src) != trans->transid);
	WARN_ON(btrfs_header_generation(dst) != trans->transid);
1252

1253
	if (push_items <= 0) {
1254
		return 1;
1255
	}
1256

1257
	if (src_nritems < push_items)
1258 1259
		push_items = src_nritems;

1260 1261 1262 1263 1264
	copy_extent_buffer(dst, src,
			   btrfs_node_key_ptr_offset(dst_nritems),
			   btrfs_node_key_ptr_offset(0),
		           push_items * sizeof(struct btrfs_key_ptr));

1265
	if (push_items < src_nritems) {
1266 1267 1268 1269 1270 1271 1272 1273 1274
		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);
1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286
	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
 */
1287 1288 1289 1290
static int balance_node_right(struct btrfs_trans_handle *trans,
			      struct btrfs_root *root,
			      struct extent_buffer *dst,
			      struct extent_buffer *src)
1291 1292 1293 1294 1295 1296 1297
{
	int push_items = 0;
	int max_push;
	int src_nritems;
	int dst_nritems;
	int ret = 0;

1298 1299 1300
	WARN_ON(btrfs_header_generation(src) != trans->transid);
	WARN_ON(btrfs_header_generation(dst) != trans->transid);

1301 1302
	src_nritems = btrfs_header_nritems(src);
	dst_nritems = btrfs_header_nritems(dst);
1303
	push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1304
	if (push_items <= 0)
1305 1306 1307 1308
		return 1;

	max_push = src_nritems / 2 + 1;
	/* don't try to empty the node */
Y
Yan 已提交
1309
	if (max_push >= src_nritems)
1310
		return 1;
Y
Yan 已提交
1311

1312 1313 1314
	if (max_push < push_items)
		push_items = max_push;

1315 1316 1317 1318
	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
				      btrfs_node_key_ptr_offset(0),
				      (dst_nritems) *
				      sizeof(struct btrfs_key_ptr));
1319

1320 1321 1322 1323
	copy_extent_buffer(dst, src,
			   btrfs_node_key_ptr_offset(0),
			   btrfs_node_key_ptr_offset(src_nritems - push_items),
		           push_items * sizeof(struct btrfs_key_ptr));
1324

1325 1326
	btrfs_set_header_nritems(src, src_nritems - push_items);
	btrfs_set_header_nritems(dst, dst_nritems + push_items);
1327

1328 1329
	btrfs_mark_buffer_dirty(src);
	btrfs_mark_buffer_dirty(dst);
C
Chris Mason 已提交
1330
	return ret;
1331 1332
}

C
Chris Mason 已提交
1333 1334 1335 1336
/*
 * 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 已提交
1337 1338
 *
 * returns zero on success or < 0 on failure.
C
Chris Mason 已提交
1339
 */
1340
static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1341 1342
			   struct btrfs_root *root,
			   struct btrfs_path *path, int level)
1343
{
1344 1345
	u64 root_gen;
	u64 lower_gen;
1346 1347 1348
	struct extent_buffer *lower;
	struct extent_buffer *c;
	struct btrfs_disk_key lower_key;
1349 1350 1351 1352

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

1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366
	if (root->ref_cows)
		root_gen = trans->transid;
	else
		root_gen = 0;

	lower = path->nodes[level-1];
	if (level == 1)
		btrfs_item_key(lower, &lower_key, 0);
	else
		btrfs_node_key(lower, &lower_key, 0);

	c = __btrfs_alloc_free_block(trans, root, root->nodesize,
				   root->root_key.objectid,
				   root_gen, lower_key.objectid, level,
1367
				   root->node->start, 0);
1368 1369 1370 1371 1372
	if (IS_ERR(c))
		return PTR_ERR(c);
	memset_extent_buffer(c, 0, 0, root->nodesize);
	btrfs_set_header_nritems(c, 1);
	btrfs_set_header_level(c, level);
1373
	btrfs_set_header_bytenr(c, c->start);
1374 1375 1376 1377 1378 1379 1380
	btrfs_set_header_generation(c, trans->transid);
	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);
	btrfs_set_node_key(c, &lower_key, 0);
1381
	btrfs_set_node_blockptr(c, 0, lower->start);
1382 1383 1384 1385
	lower_gen = btrfs_header_generation(lower);
	WARN_ON(lower_gen == 0);

	btrfs_set_node_ptr_generation(c, 0, lower_gen);
1386

1387
	btrfs_mark_buffer_dirty(c);
1388

1389
	/* the super has an extra ref to root->node */
1390 1391
	free_extent_buffer(root->node);
	root->node = c;
1392
	add_root_to_dirty_list(root);
1393 1394
	extent_buffer_get(c);
	path->nodes[level] = c;
1395
	path->slots[level] = 0;
1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407

	if (root->ref_cows && lower_gen != trans->transid) {
		struct btrfs_path *back_path = btrfs_alloc_path();
		int ret;
		ret = btrfs_insert_extent_backref(trans,
						  root->fs_info->extent_root,
						  path, lower->start,
						  root->root_key.objectid,
						  trans->transid, 0, 0);
		BUG_ON(ret);
		btrfs_free_path(back_path);
	}
1408 1409 1410
	return 0;
}

C
Chris Mason 已提交
1411 1412 1413
/*
 * worker function to insert a single pointer in a node.
 * the node should have enough room for the pointer already
C
Chris Mason 已提交
1414
 *
C
Chris Mason 已提交
1415 1416
 * slot and level indicate where you want the key to go, and
 * blocknr is the block the key points to.
C
Chris Mason 已提交
1417 1418
 *
 * returns zero on success and < 0 on any error
C
Chris Mason 已提交
1419
 */
1420 1421
static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_path *path, struct btrfs_disk_key
1422
		      *key, u64 bytenr, int slot, int level)
C
Chris Mason 已提交
1423
{
1424
	struct extent_buffer *lower;
C
Chris Mason 已提交
1425
	int nritems;
1426 1427

	BUG_ON(!path->nodes[level]);
1428 1429
	lower = path->nodes[level];
	nritems = btrfs_header_nritems(lower);
C
Chris Mason 已提交
1430 1431
	if (slot > nritems)
		BUG();
1432
	if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
C
Chris Mason 已提交
1433 1434
		BUG();
	if (slot != nritems) {
1435 1436 1437
		memmove_extent_buffer(lower,
			      btrfs_node_key_ptr_offset(slot + 1),
			      btrfs_node_key_ptr_offset(slot),
1438
			      (nritems - slot) * sizeof(struct btrfs_key_ptr));
C
Chris Mason 已提交
1439
	}
1440
	btrfs_set_node_key(lower, key, slot);
1441
	btrfs_set_node_blockptr(lower, slot, bytenr);
1442 1443
	WARN_ON(trans->transid == 0);
	btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1444 1445
	btrfs_set_header_nritems(lower, nritems + 1);
	btrfs_mark_buffer_dirty(lower);
C
Chris Mason 已提交
1446 1447 1448
	return 0;
}

C
Chris Mason 已提交
1449 1450 1451 1452 1453 1454
/*
 * 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 已提交
1455 1456
 *
 * returns 0 on success and < 0 on failure
C
Chris Mason 已提交
1457
 */
1458 1459
static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_path *path, int level)
1460
{
1461
	u64 root_gen;
1462 1463 1464
	struct extent_buffer *c;
	struct extent_buffer *split;
	struct btrfs_disk_key disk_key;
1465
	int mid;
1466
	int ret;
C
Chris Mason 已提交
1467
	int wret;
1468
	u32 c_nritems;
1469

1470
	c = path->nodes[level];
1471
	WARN_ON(btrfs_header_generation(c) != trans->transid);
1472
	if (c == root->node) {
1473
		/* trying to split the root, lets make a new one */
1474
		ret = insert_new_root(trans, root, path, level + 1);
1475 1476
		if (ret)
			return ret;
1477 1478
	} else {
		ret = push_nodes_for_insert(trans, root, path, level);
1479 1480
		c = path->nodes[level];
		if (!ret && btrfs_header_nritems(c) <
1481 1482
		    BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
			return 0;
1483 1484
		if (ret < 0)
			return ret;
1485
	}
1486

1487
	c_nritems = btrfs_header_nritems(c);
1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498
	if (root->ref_cows)
		root_gen = trans->transid;
	else
		root_gen = 0;

	btrfs_node_key(c, &disk_key, 0);
	split = __btrfs_alloc_free_block(trans, root, root->nodesize,
					 root->root_key.objectid,
					 root_gen,
					 btrfs_disk_key_objectid(&disk_key),
					 level, c->start, 0);
1499 1500 1501 1502 1503
	if (IS_ERR(split))
		return PTR_ERR(split);

	btrfs_set_header_flags(split, btrfs_header_flags(c));
	btrfs_set_header_level(split, btrfs_header_level(c));
1504
	btrfs_set_header_bytenr(split, split->start);
1505 1506
	btrfs_set_header_generation(split, trans->transid);
	btrfs_set_header_owner(split, root->root_key.objectid);
1507
	btrfs_set_header_flags(split, 0);
1508 1509 1510
	write_extent_buffer(split, root->fs_info->fsid,
			    (unsigned long)btrfs_header_fsid(split),
			    BTRFS_FSID_SIZE);
1511

1512
	mid = (c_nritems + 1) / 2;
1513 1514 1515 1516 1517 1518 1519

	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 已提交
1520 1521
	ret = 0;

1522 1523 1524 1525
	btrfs_mark_buffer_dirty(c);
	btrfs_mark_buffer_dirty(split);

	btrfs_node_key(split, &disk_key, 0);
1526
	wret = insert_ptr(trans, root, path, &disk_key, split->start,
1527
			  path->slots[level + 1] + 1,
1528
			  level + 1);
C
Chris Mason 已提交
1529 1530 1531
	if (wret)
		ret = wret;

1532
	if (path->slots[level] >= mid) {
1533
		path->slots[level] -= mid;
1534 1535
		free_extent_buffer(c);
		path->nodes[level] = split;
1536 1537
		path->slots[level + 1] += 1;
	} else {
1538
		free_extent_buffer(split);
1539
	}
C
Chris Mason 已提交
1540
	return ret;
1541 1542
}

C
Chris Mason 已提交
1543 1544 1545 1546 1547
/*
 * 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
 */
1548
static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1549 1550
{
	int data_len;
1551
	int nritems = btrfs_header_nritems(l);
1552
	int end = min(nritems, start + nr) - 1;
1553 1554 1555

	if (!nr)
		return 0;
1556 1557
	data_len = btrfs_item_end_nr(l, start);
	data_len = data_len - btrfs_item_offset_nr(l, end);
1558
	data_len += sizeof(struct btrfs_item) * nr;
1559
	WARN_ON(data_len < 0);
1560 1561 1562
	return data_len;
}

1563 1564 1565 1566 1567
/*
 * 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
 */
1568
int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1569
{
1570 1571 1572 1573 1574
	int nritems = btrfs_header_nritems(leaf);
	int ret;
	ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
	if (ret < 0) {
		printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
J
Jens Axboe 已提交
1575
		       ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1576 1577 1578
		       leaf_space_used(leaf, 0, nritems), nritems);
	}
	return ret;
1579 1580
}

C
Chris Mason 已提交
1581 1582 1583
/*
 * 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
C
Chris Mason 已提交
1584 1585 1586
 *
 * 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.
C
Chris Mason 已提交
1587
 */
1588
static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1589 1590
			   *root, struct btrfs_path *path, int data_size,
			   int empty)
C
Chris Mason 已提交
1591
{
1592 1593 1594 1595
	struct extent_buffer *left = path->nodes[0];
	struct extent_buffer *right;
	struct extent_buffer *upper;
	struct btrfs_disk_key disk_key;
C
Chris Mason 已提交
1596
	int slot;
1597
	u32 i;
C
Chris Mason 已提交
1598 1599 1600
	int free_space;
	int push_space = 0;
	int push_items = 0;
1601
	struct btrfs_item *item;
1602
	u32 left_nritems;
1603
	u32 nr;
1604
	u32 right_nritems;
1605
	u32 data_end;
1606
	u32 this_item_size;
1607
	int ret;
C
Chris Mason 已提交
1608 1609 1610 1611 1612 1613

	slot = path->slots[1];
	if (!path->nodes[1]) {
		return 1;
	}
	upper = path->nodes[1];
1614
	if (slot >= btrfs_header_nritems(upper) - 1)
C
Chris Mason 已提交
1615
		return 1;
1616

1617 1618
	right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1),
				root->leafsize);
1619
	free_space = btrfs_leaf_free_space(root, right);
1620
	if (free_space < data_size + sizeof(struct btrfs_item)) {
1621
		free_extent_buffer(right);
C
Chris Mason 已提交
1622 1623
		return 1;
	}
1624

1625
	/* cow and double check */
1626 1627
	ret = btrfs_cow_block(trans, root, right, upper,
			      slot + 1, &right);
1628
	if (ret) {
1629
		free_extent_buffer(right);
1630 1631
		return 1;
	}
1632
	free_space = btrfs_leaf_free_space(root, right);
1633
	if (free_space < data_size + sizeof(struct btrfs_item)) {
1634
		free_extent_buffer(right);
1635 1636 1637
		return 1;
	}

1638
	left_nritems = btrfs_header_nritems(left);
1639
	if (left_nritems == 0) {
1640
		free_extent_buffer(right);
1641 1642
		return 1;
	}
1643

1644 1645 1646 1647 1648 1649 1650
	if (empty)
		nr = 0;
	else
		nr = 1;

	i = left_nritems - 1;
	while (i >= nr) {
1651
		item = btrfs_item_nr(left, i);
1652

C
Chris Mason 已提交
1653 1654
		if (path->slots[0] == i)
			push_space += data_size + sizeof(*item);
1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665

		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 已提交
1666 1667
			break;
		push_items++;
1668
		push_space += this_item_size + sizeof(*item);
1669 1670 1671
		if (i == 0)
			break;
		i--;
1672 1673 1674 1675
	}
	if (left->map_token) {
		unmap_extent_buffer(left, left->map_token, KM_USER1);
		left->map_token = NULL;
C
Chris Mason 已提交
1676
	}
1677

C
Chris Mason 已提交
1678
	if (push_items == 0) {
1679
		free_extent_buffer(right);
C
Chris Mason 已提交
1680 1681
		return 1;
	}
1682

1683
	if (!empty && push_items == left_nritems)
1684
		WARN_ON(1);
1685

C
Chris Mason 已提交
1686
	/* push left to right */
1687
	right_nritems = btrfs_header_nritems(right);
1688

1689
	push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1690
	push_space -= leaf_data_end(root, left);
1691

C
Chris Mason 已提交
1692
	/* make room in the right data area */
1693 1694 1695 1696 1697 1698
	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 已提交
1699
	/* copy from the left data area */
1700
	copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1701 1702 1703
		     BTRFS_LEAF_DATA_SIZE(root) - push_space,
		     btrfs_leaf_data(left) + leaf_data_end(root, left),
		     push_space);
1704 1705 1706 1707 1708

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

C
Chris Mason 已提交
1709
	/* copy the items from left to right */
1710 1711 1712
	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 已提交
1713 1714

	/* update the item pointers */
1715
	right_nritems += push_items;
1716
	btrfs_set_header_nritems(right, right_nritems);
1717
	push_space = BTRFS_LEAF_DATA_SIZE(root);
1718
	for (i = 0; i < right_nritems; i++) {
1719
		item = btrfs_item_nr(right, i);
1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733
		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 已提交
1734
	}
1735
	left_nritems -= push_items;
1736
	btrfs_set_header_nritems(left, left_nritems);
C
Chris Mason 已提交
1737

1738 1739
	if (left_nritems)
		btrfs_mark_buffer_dirty(left);
1740
	btrfs_mark_buffer_dirty(right);
1741

1742 1743
	btrfs_item_key(right, &disk_key, 0);
	btrfs_set_node_key(upper, &disk_key, slot + 1);
1744
	btrfs_mark_buffer_dirty(upper);
1745

C
Chris Mason 已提交
1746
	/* then fixup the leaf pointer in the path */
1747 1748
	if (path->slots[0] >= left_nritems) {
		path->slots[0] -= left_nritems;
1749 1750
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = right;
C
Chris Mason 已提交
1751 1752
		path->slots[1] += 1;
	} else {
1753
		free_extent_buffer(right);
C
Chris Mason 已提交
1754 1755 1756
	}
	return 0;
}
C
Chris Mason 已提交
1757 1758 1759 1760
/*
 * 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
 */
1761
static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1762 1763
			  *root, struct btrfs_path *path, int data_size,
			  int empty)
1764
{
1765 1766 1767
	struct btrfs_disk_key disk_key;
	struct extent_buffer *right = path->nodes[0];
	struct extent_buffer *left;
1768 1769 1770 1771 1772
	int slot;
	int i;
	int free_space;
	int push_space = 0;
	int push_items = 0;
1773
	struct btrfs_item *item;
1774
	u32 old_left_nritems;
1775
	u32 right_nritems;
1776
	u32 nr;
C
Chris Mason 已提交
1777 1778
	int ret = 0;
	int wret;
1779 1780
	u32 this_item_size;
	u32 old_left_item_size;
1781 1782

	slot = path->slots[1];
1783
	if (slot == 0)
1784
		return 1;
1785
	if (!path->nodes[1])
1786
		return 1;
1787

1788 1789 1790 1791 1792
	right_nritems = btrfs_header_nritems(right);
	if (right_nritems == 0) {
		return 1;
	}

1793
	left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1794
			       slot - 1), root->leafsize);
1795
	free_space = btrfs_leaf_free_space(root, left);
1796
	if (free_space < data_size + sizeof(struct btrfs_item)) {
1797
		free_extent_buffer(left);
1798 1799
		return 1;
	}
1800 1801

	/* cow and double check */
1802 1803
	ret = btrfs_cow_block(trans, root, left,
			      path->nodes[1], slot - 1, &left);
1804 1805
	if (ret) {
		/* we hit -ENOSPC, but it isn't fatal here */
1806
		free_extent_buffer(left);
1807 1808
		return 1;
	}
1809

1810
	free_space = btrfs_leaf_free_space(root, left);
1811
	if (free_space < data_size + sizeof(struct btrfs_item)) {
1812
		free_extent_buffer(left);
1813 1814 1815
		return 1;
	}

1816 1817 1818 1819 1820 1821
	if (empty)
		nr = right_nritems;
	else
		nr = right_nritems - 1;

	for (i = 0; i < nr; i++) {
1822
		item = btrfs_item_nr(right, i);
1823 1824 1825 1826 1827 1828 1829 1830
		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);
		}

1831 1832
		if (path->slots[0] == i)
			push_space += data_size + sizeof(*item);
1833 1834 1835

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

1838
		push_items++;
1839 1840 1841 1842 1843 1844
		push_space += this_item_size + sizeof(*item);
	}

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

1847
	if (push_items == 0) {
1848
		free_extent_buffer(left);
1849 1850
		return 1;
	}
1851
	if (!empty && push_items == btrfs_header_nritems(right))
1852
		WARN_ON(1);
1853

1854
	/* push data from right to left */
1855 1856 1857 1858 1859
	copy_extent_buffer(left, right,
			   btrfs_item_nr_offset(btrfs_header_nritems(left)),
			   btrfs_item_nr_offset(0),
			   push_items * sizeof(struct btrfs_item));

1860
	push_space = BTRFS_LEAF_DATA_SIZE(root) -
1861 1862 1863
		     btrfs_item_offset_nr(right, push_items -1);

	copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1864 1865
		     leaf_data_end(root, left) - push_space,
		     btrfs_leaf_data(right) +
1866
		     btrfs_item_offset_nr(right, push_items - 1),
1867
		     push_space);
1868
	old_left_nritems = btrfs_header_nritems(left);
1869 1870
	BUG_ON(old_left_nritems < 0);

1871
	old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1872
	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1873
		u32 ioff;
1874

1875
		item = btrfs_item_nr(left, i);
1876 1877 1878 1879 1880 1881 1882 1883
		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);
		}

1884 1885
		ioff = btrfs_item_offset(left, item);
		btrfs_set_item_offset(left, item,
1886
		      ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1887
	}
1888
	btrfs_set_header_nritems(left, old_left_nritems + push_items);
1889 1890 1891 1892
	if (left->map_token) {
		unmap_extent_buffer(left, left->map_token, KM_USER1);
		left->map_token = NULL;
	}
1893 1894

	/* fixup right node */
1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908
	if (push_items > right_nritems) {
		printk("push items %d nr %u\n", push_items, right_nritems);
		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),
1909 1910 1911
			      btrfs_item_nr_offset(push_items),
			     (btrfs_header_nritems(right) - push_items) *
			     sizeof(struct btrfs_item));
1912
	}
1913 1914
	right_nritems -= push_items;
	btrfs_set_header_nritems(right, right_nritems);
1915
	push_space = BTRFS_LEAF_DATA_SIZE(root);
1916 1917
	for (i = 0; i < right_nritems; i++) {
		item = btrfs_item_nr(right, i);
1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932

		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;
1933
	}
1934

1935
	btrfs_mark_buffer_dirty(left);
1936 1937
	if (right_nritems)
		btrfs_mark_buffer_dirty(right);
1938

1939 1940
	btrfs_item_key(right, &disk_key, 0);
	wret = fixup_low_keys(trans, root, path, &disk_key, 1);
C
Chris Mason 已提交
1941 1942
	if (wret)
		ret = wret;
1943 1944 1945 1946

	/* then fixup the leaf pointer in the path */
	if (path->slots[0] < push_items) {
		path->slots[0] += old_left_nritems;
1947 1948
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = left;
1949 1950
		path->slots[1] -= 1;
	} else {
1951
		free_extent_buffer(left);
1952 1953
		path->slots[0] -= push_items;
	}
1954
	BUG_ON(path->slots[0] < 0);
C
Chris Mason 已提交
1955
	return ret;
1956 1957
}

C
Chris Mason 已提交
1958 1959 1960
/*
 * 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 已提交
1961 1962
 *
 * returns 0 if all went well and < 0 on failure.
C
Chris Mason 已提交
1963
 */
1964
static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1965
		      *root, struct btrfs_key *ins_key,
1966
		      struct btrfs_path *path, int data_size, int extend)
1967
{
1968
	u64 root_gen;
1969
	struct extent_buffer *l;
1970
	u32 nritems;
1971 1972
	int mid;
	int slot;
1973
	struct extent_buffer *right;
1974
	int space_needed = data_size + sizeof(struct btrfs_item);
1975 1976 1977
	int data_copy_size;
	int rt_data_off;
	int i;
1978
	int ret = 0;
C
Chris Mason 已提交
1979
	int wret;
1980 1981
	int double_split;
	int num_doubles = 0;
1982
	struct btrfs_disk_key disk_key;
C
Chris Mason 已提交
1983

1984 1985 1986
	if (extend)
		space_needed = data_size;

1987 1988 1989 1990 1991
	if (root->ref_cows)
		root_gen = trans->transid;
	else
		root_gen = 0;

C
Chris Mason 已提交
1992
	/* first try to make some room by pushing left and right */
1993
	if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
1994
		wret = push_leaf_right(trans, root, path, data_size, 0);
1995
		if (wret < 0) {
1996
			return wret;
1997 1998
		}
		if (wret) {
1999
			wret = push_leaf_left(trans, root, path, data_size, 0);
2000 2001 2002 2003
			if (wret < 0)
				return wret;
		}
		l = path->nodes[0];
C
Chris Mason 已提交
2004

2005
		/* did the pushes work? */
2006
		if (btrfs_leaf_free_space(root, l) >= space_needed)
2007
			return 0;
2008
	}
C
Chris Mason 已提交
2009

2010
	if (!path->nodes[1]) {
2011
		ret = insert_new_root(trans, root, path, 1);
2012 2013 2014
		if (ret)
			return ret;
	}
2015 2016 2017
again:
	double_split = 0;
	l = path->nodes[0];
2018
	slot = path->slots[0];
2019
	nritems = btrfs_header_nritems(l);
2020
	mid = (nritems + 1)/ 2;
2021

2022 2023 2024 2025 2026 2027
	btrfs_item_key(l, &disk_key, 0);

	right = __btrfs_alloc_free_block(trans, root, root->leafsize,
					 root->root_key.objectid,
					 root_gen, disk_key.objectid, 0,
					 l->start, 0);
2028 2029
	if (IS_ERR(right)) {
		BUG_ON(1);
2030
		return PTR_ERR(right);
2031
	}
2032 2033

	memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2034
	btrfs_set_header_bytenr(right, right->start);
2035 2036 2037 2038 2039 2040
	btrfs_set_header_generation(right, trans->transid);
	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);
2041 2042 2043 2044 2045 2046
	if (mid <= slot) {
		if (nritems == 1 ||
		    leaf_space_used(l, mid, nritems - mid) + space_needed >
			BTRFS_LEAF_DATA_SIZE(root)) {
			if (slot >= nritems) {
				btrfs_cpu_key_to_disk(&disk_key, ins_key);
2047
				btrfs_set_header_nritems(right, 0);
2048
				wret = insert_ptr(trans, root, path,
2049
						  &disk_key, right->start,
2050 2051 2052
						  path->slots[1] + 1, 1);
				if (wret)
					ret = wret;
2053 2054
				free_extent_buffer(path->nodes[0]);
				path->nodes[0] = right;
2055 2056
				path->slots[0] = 0;
				path->slots[1] += 1;
2057
				btrfs_mark_buffer_dirty(right);
2058 2059 2060
				return ret;
			}
			mid = slot;
2061 2062 2063 2064 2065
			if (mid != nritems &&
			    leaf_space_used(l, mid, nritems - mid) +
			    space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
				double_split = 1;
			}
2066 2067 2068 2069
		}
	} else {
		if (leaf_space_used(l, 0, mid + 1) + space_needed >
			BTRFS_LEAF_DATA_SIZE(root)) {
2070
			if (!extend && slot == 0) {
2071
				btrfs_cpu_key_to_disk(&disk_key, ins_key);
2072
				btrfs_set_header_nritems(right, 0);
2073 2074
				wret = insert_ptr(trans, root, path,
						  &disk_key,
2075
						  right->start,
2076
						  path->slots[1], 1);
2077 2078
				if (wret)
					ret = wret;
2079 2080
				free_extent_buffer(path->nodes[0]);
				path->nodes[0] = right;
2081
				path->slots[0] = 0;
2082 2083 2084 2085 2086 2087
				if (path->slots[1] == 0) {
					wret = fixup_low_keys(trans, root,
					           path, &disk_key, 1);
					if (wret)
						ret = wret;
				}
2088
				btrfs_mark_buffer_dirty(right);
2089
				return ret;
2090 2091 2092 2093 2094 2095 2096 2097 2098
			} else if (extend && slot == 0) {
				mid = 1;
			} else {
				mid = slot;
				if (mid != nritems &&
				    leaf_space_used(l, mid, nritems - mid) +
				    space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
					double_split = 1;
				}
2099
			}
2100 2101
		}
	}
2102 2103 2104 2105 2106 2107 2108 2109 2110
	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,
2111 2112 2113
		     btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
		     data_copy_size, btrfs_leaf_data(l) +
		     leaf_data_end(root, l), data_copy_size);
2114

2115
	rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2116
		      btrfs_item_end_nr(l, mid);
C
Chris Mason 已提交
2117

2118 2119
	for (i = 0; i < nritems; i++) {
		struct btrfs_item *item = btrfs_item_nr(right, i);
2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130
		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);
2131
		btrfs_set_item_offset(right, item, ioff + rt_data_off);
2132
	}
C
Chris Mason 已提交
2133

2134 2135 2136 2137 2138
	if (right->map_token) {
		unmap_extent_buffer(right, right->map_token, KM_USER1);
		right->map_token = NULL;
	}

2139
	btrfs_set_header_nritems(l, mid);
C
Chris Mason 已提交
2140
	ret = 0;
2141
	btrfs_item_key(right, &disk_key, 0);
2142 2143
	wret = insert_ptr(trans, root, path, &disk_key, right->start,
			  path->slots[1] + 1, 1);
C
Chris Mason 已提交
2144 2145
	if (wret)
		ret = wret;
2146 2147 2148

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

2151
	if (mid <= slot) {
2152 2153
		free_extent_buffer(path->nodes[0]);
		path->nodes[0] = right;
2154 2155
		path->slots[0] -= mid;
		path->slots[1] += 1;
2156
	} else
2157 2158
		free_extent_buffer(right);

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

2161 2162 2163 2164
	if (double_split) {
		BUG_ON(num_doubles != 0);
		num_doubles++;
		goto again;
2165
	}
2166 2167 2168
	return ret;
}

2169 2170 2171
int btrfs_truncate_item(struct btrfs_trans_handle *trans,
			struct btrfs_root *root,
			struct btrfs_path *path,
2172
			u32 new_size, int from_end)
2173 2174 2175 2176
{
	int ret = 0;
	int slot;
	int slot_orig;
2177 2178
	struct extent_buffer *leaf;
	struct btrfs_item *item;
2179 2180 2181 2182 2183 2184 2185 2186
	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];
2187
	leaf = path->nodes[0];
2188 2189 2190 2191 2192
	slot = path->slots[0];

	old_size = btrfs_item_size_nr(leaf, slot);
	if (old_size == new_size)
		return 0;
2193

2194
	nritems = btrfs_header_nritems(leaf);
2195 2196
	data_end = leaf_data_end(root, leaf);

2197
	old_data_start = btrfs_item_offset_nr(leaf, slot);
2198

2199 2200 2201 2202 2203 2204 2205 2206 2207 2208
	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++) {
2209 2210
		u32 ioff;
		item = btrfs_item_nr(leaf, i);
2211 2212 2213 2214 2215 2216 2217 2218 2219

		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);
		}

2220 2221
		ioff = btrfs_item_offset(leaf, item);
		btrfs_set_item_offset(leaf, item, ioff + size_diff);
2222
	}
2223 2224 2225 2226 2227 2228

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

2229
	/* shift the data */
2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268
	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,
				        (unsigned long)fi,
				        offsetof(struct btrfs_file_extent_item,
						 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);
	}
2269 2270 2271 2272

	item = btrfs_item_nr(leaf, slot);
	btrfs_set_item_size(leaf, item, new_size);
	btrfs_mark_buffer_dirty(leaf);
2273 2274

	ret = 0;
2275 2276
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
2277
		BUG();
2278
	}
2279 2280 2281
	return ret;
}

2282 2283 2284
int btrfs_extend_item(struct btrfs_trans_handle *trans,
		      struct btrfs_root *root, struct btrfs_path *path,
		      u32 data_size)
2285 2286 2287 2288
{
	int ret = 0;
	int slot;
	int slot_orig;
2289 2290
	struct extent_buffer *leaf;
	struct btrfs_item *item;
2291 2292 2293 2294 2295 2296 2297
	u32 nritems;
	unsigned int data_end;
	unsigned int old_data;
	unsigned int old_size;
	int i;

	slot_orig = path->slots[0];
2298
	leaf = path->nodes[0];
2299

2300
	nritems = btrfs_header_nritems(leaf);
2301 2302
	data_end = leaf_data_end(root, leaf);

2303 2304
	if (btrfs_leaf_free_space(root, leaf) < data_size) {
		btrfs_print_leaf(root, leaf);
2305
		BUG();
2306
	}
2307
	slot = path->slots[0];
2308
	old_data = btrfs_item_end_nr(leaf, slot);
2309 2310

	BUG_ON(slot < 0);
2311 2312 2313 2314 2315
	if (slot >= nritems) {
		btrfs_print_leaf(root, leaf);
		printk("slot %d too large, nritems %d\n", slot, nritems);
		BUG_ON(1);
	}
2316 2317 2318 2319 2320 2321

	/*
	 * item0..itemN ... dataN.offset..dataN.size .. data0.size
	 */
	/* first correct the data pointers */
	for (i = slot; i < nritems; i++) {
2322 2323
		u32 ioff;
		item = btrfs_item_nr(leaf, i);
2324 2325 2326 2327 2328 2329 2330 2331

		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);
		}
2332 2333
		ioff = btrfs_item_offset(leaf, item);
		btrfs_set_item_offset(leaf, item, ioff - data_size);
2334
	}
2335

2336 2337 2338 2339 2340
	if (leaf->map_token) {
		unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
		leaf->map_token = NULL;
	}

2341
	/* shift the data */
2342
	memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2343 2344
		      data_end - data_size, btrfs_leaf_data(leaf) +
		      data_end, old_data - data_end);
2345

2346
	data_end = old_data;
2347 2348 2349 2350
	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);
2351 2352

	ret = 0;
2353 2354
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
2355
		BUG();
2356
	}
2357 2358 2359
	return ret;
}

C
Chris Mason 已提交
2360 2361 2362 2363
/*
 * 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.
 */
2364
int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2365 2366
			    struct btrfs_root *root,
			    struct btrfs_path *path,
2367 2368
			    struct btrfs_key *cpu_key, u32 *data_size,
			    int nr)
2369
{
2370 2371
	struct extent_buffer *leaf;
	struct btrfs_item *item;
C
Chris Mason 已提交
2372
	int ret = 0;
2373
	int slot;
2374
	int slot_orig;
2375
	int i;
2376
	u32 nritems;
2377 2378
	u32 total_size = 0;
	u32 total_data = 0;
2379
	unsigned int data_end;
2380 2381
	struct btrfs_disk_key disk_key;

2382 2383 2384
	for (i = 0; i < nr; i++) {
		total_data += data_size[i];
	}
2385

C
Chris Mason 已提交
2386
	/* create a root if there isn't one */
2387
	if (!root->node)
C
Chris Mason 已提交
2388
		BUG();
2389

2390 2391
	total_size = total_data + (nr - 1) * sizeof(struct btrfs_item);
	ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2392
	if (ret == 0) {
2393
		return -EEXIST;
C
Chris Mason 已提交
2394
	}
2395 2396
	if (ret < 0)
		goto out;
2397

2398
	slot_orig = path->slots[0];
2399
	leaf = path->nodes[0];
C
Chris Mason 已提交
2400

2401
	nritems = btrfs_header_nritems(leaf);
2402
	data_end = leaf_data_end(root, leaf);
2403

2404
	if (btrfs_leaf_free_space(root, leaf) <
2405
	    sizeof(struct btrfs_item) + total_size) {
2406 2407
		btrfs_print_leaf(root, leaf);
		printk("not enough freespace need %u have %d\n",
2408
		       total_size, btrfs_leaf_free_space(root, leaf));
2409
		BUG();
2410
	}
2411

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

2415 2416
	if (slot != nritems) {
		int i;
2417
		unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2418

2419 2420 2421 2422 2423 2424
		if (old_data < data_end) {
			btrfs_print_leaf(root, leaf);
			printk("slot %d old_data %d data_end %d\n",
			       slot, old_data, data_end);
			BUG_ON(1);
		}
2425 2426 2427 2428
		/*
		 * item0..itemN ... dataN.offset..dataN.size .. data0.size
		 */
		/* first correct the data pointers */
2429
		WARN_ON(leaf->map_token);
2430
		for (i = slot; i < nritems; i++) {
2431
			u32 ioff;
2432

2433
			item = btrfs_item_nr(leaf, i);
2434 2435 2436 2437 2438 2439 2440 2441
			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);
			}

2442
			ioff = btrfs_item_offset(leaf, item);
2443
			btrfs_set_item_offset(leaf, item, ioff - total_data);
2444
		}
2445 2446 2447 2448
		if (leaf->map_token) {
			unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
			leaf->map_token = NULL;
		}
2449 2450

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

		/* shift the data */
2456
		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2457
			      data_end - total_data, btrfs_leaf_data(leaf) +
2458
			      data_end, old_data - data_end);
2459 2460
		data_end = old_data;
	}
2461

2462
	/* setup the item for the new data */
2463 2464 2465 2466 2467 2468 2469 2470 2471
	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);
2472
	btrfs_mark_buffer_dirty(leaf);
C
Chris Mason 已提交
2473 2474

	ret = 0;
2475 2476
	if (slot == 0) {
		btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2477
		ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2478
	}
C
Chris Mason 已提交
2479

2480 2481
	if (btrfs_leaf_free_space(root, leaf) < 0) {
		btrfs_print_leaf(root, leaf);
2482
		BUG();
2483
	}
2484

2485
out:
2486 2487 2488 2489 2490 2491 2492
	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.
 */
2493 2494 2495
int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
		      *root, struct btrfs_key *cpu_key, void *data, u32
		      data_size)
2496 2497
{
	int ret = 0;
2498
	struct btrfs_path *path;
2499 2500
	struct extent_buffer *leaf;
	unsigned long ptr;
2501

2502 2503 2504
	path = btrfs_alloc_path();
	BUG_ON(!path);
	ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2505
	if (!ret) {
2506 2507 2508 2509
		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);
2510
	}
2511
	btrfs_free_path(path);
C
Chris Mason 已提交
2512
	return ret;
2513 2514
}

C
Chris Mason 已提交
2515
/*
2516
 * delete the pointer from a given node.
C
Chris Mason 已提交
2517 2518 2519 2520 2521
 *
 * If the delete empties a node, the node is removed from the tree,
 * continuing all the way the root if required.  The root is converted into
 * a leaf if all the nodes are emptied.
 */
2522 2523
static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		   struct btrfs_path *path, int level, int slot)
2524
{
2525
	struct extent_buffer *parent = path->nodes[level];
2526
	u32 nritems;
C
Chris Mason 已提交
2527
	int ret = 0;
2528
	int wret;
2529

2530
	nritems = btrfs_header_nritems(parent);
2531
	if (slot != nritems -1) {
2532 2533 2534
		memmove_extent_buffer(parent,
			      btrfs_node_key_ptr_offset(slot),
			      btrfs_node_key_ptr_offset(slot + 1),
2535 2536
			      sizeof(struct btrfs_key_ptr) *
			      (nritems - slot - 1));
2537
	}
2538
	nritems--;
2539
	btrfs_set_header_nritems(parent, nritems);
2540
	if (nritems == 0 && parent == root->node) {
2541
		BUG_ON(btrfs_header_level(root->node) != 1);
2542
		/* just turn the root into a leaf and break */
2543
		btrfs_set_header_level(root->node, 0);
2544
	} else if (slot == 0) {
2545 2546 2547 2548
		struct btrfs_disk_key disk_key;

		btrfs_node_key(parent, &disk_key, 0);
		wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2549 2550
		if (wret)
			ret = wret;
2551
	}
2552
	btrfs_mark_buffer_dirty(parent);
C
Chris Mason 已提交
2553
	return ret;
2554 2555
}

C
Chris Mason 已提交
2556 2557 2558 2559
/*
 * delete the item at the leaf level in path.  If that empties
 * the leaf, remove it from the tree
 */
2560 2561
int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
		    struct btrfs_path *path, int slot, int nr)
2562
{
2563 2564
	struct extent_buffer *leaf;
	struct btrfs_item *item;
2565 2566
	int last_off;
	int dsize = 0;
C
Chris Mason 已提交
2567 2568
	int ret = 0;
	int wret;
2569
	int i;
2570
	u32 nritems;
2571

2572
	leaf = path->nodes[0];
2573 2574 2575 2576 2577
	last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);

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

2578
	nritems = btrfs_header_nritems(leaf);
2579

2580
	if (slot + nr != nritems) {
2581
		int i;
2582
		int data_end = leaf_data_end(root, leaf);
2583 2584

		memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2585 2586
			      data_end + dsize,
			      btrfs_leaf_data(leaf) + data_end,
2587
			      last_off - data_end);
2588

2589
		for (i = slot + nr; i < nritems; i++) {
2590
			u32 ioff;
2591

2592
			item = btrfs_item_nr(leaf, i);
2593 2594 2595 2596 2597 2598 2599
			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);
			}
2600 2601
			ioff = btrfs_item_offset(leaf, item);
			btrfs_set_item_offset(leaf, item, ioff + dsize);
2602
		}
2603 2604 2605 2606 2607 2608

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

2609
		memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2610
			      btrfs_item_nr_offset(slot + nr),
2611
			      sizeof(struct btrfs_item) *
2612
			      (nritems - slot - nr));
2613
	}
2614 2615
	btrfs_set_header_nritems(leaf, nritems - nr);
	nritems -= nr;
2616

C
Chris Mason 已提交
2617
	/* delete the leaf if we've emptied it */
2618
	if (nritems == 0) {
2619 2620
		if (leaf == root->node) {
			btrfs_set_header_level(leaf, 0);
2621
		} else {
2622
			u64 root_gen = btrfs_header_generation(path->nodes[1]);
2623 2624
			clean_tree_block(trans, root, leaf);
			wait_on_tree_block_writeback(root, leaf);
2625
			wret = del_ptr(trans, root, path, 1, path->slots[1]);
C
Chris Mason 已提交
2626 2627
			if (wret)
				ret = wret;
2628
			wret = btrfs_free_extent(trans, root,
2629 2630 2631
					 leaf->start, leaf->len,
					 btrfs_header_owner(path->nodes[1]),
					 root_gen, 0, 0, 1);
2632 2633
			if (wret)
				ret = wret;
2634
		}
2635
	} else {
2636
		int used = leaf_space_used(leaf, 0, nritems);
C
Chris Mason 已提交
2637
		if (slot == 0) {
2638 2639 2640
			struct btrfs_disk_key disk_key;

			btrfs_item_key(leaf, &disk_key, 0);
2641
			wret = fixup_low_keys(trans, root, path,
2642
					      &disk_key, 1);
C
Chris Mason 已提交
2643 2644 2645 2646
			if (wret)
				ret = wret;
		}

C
Chris Mason 已提交
2647
		/* delete the leaf if it is mostly empty */
2648
		if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2649 2650 2651 2652
			/* push_leaf_left fixes the path.
			 * make sure the path still points to our leaf
			 * for possible call to del_ptr below
			 */
2653
			slot = path->slots[1];
2654 2655
			extent_buffer_get(leaf);

2656
			wret = push_leaf_left(trans, root, path, 1, 1);
2657
			if (wret < 0 && wret != -ENOSPC)
C
Chris Mason 已提交
2658
				ret = wret;
2659 2660 2661

			if (path->nodes[0] == leaf &&
			    btrfs_header_nritems(leaf)) {
2662
				wret = push_leaf_right(trans, root, path, 1, 1);
2663
				if (wret < 0 && wret != -ENOSPC)
C
Chris Mason 已提交
2664 2665
					ret = wret;
			}
2666 2667

			if (btrfs_header_nritems(leaf) == 0) {
2668
				u64 root_gen;
2669 2670
				u64 bytenr = leaf->start;
				u32 blocksize = leaf->len;
2671

2672 2673 2674
				root_gen = btrfs_header_generation(
							   path->nodes[1]);

2675 2676 2677
				clean_tree_block(trans, root, leaf);
				wait_on_tree_block_writeback(root, leaf);

2678
				wret = del_ptr(trans, root, path, 1, slot);
C
Chris Mason 已提交
2679 2680
				if (wret)
					ret = wret;
2681 2682

				free_extent_buffer(leaf);
2683
				wret = btrfs_free_extent(trans, root, bytenr,
2684 2685 2686
					     blocksize,
					     btrfs_header_owner(path->nodes[1]),
					     root_gen, 0, 0, 1);
2687 2688
				if (wret)
					ret = wret;
2689
			} else {
2690 2691
				btrfs_mark_buffer_dirty(leaf);
				free_extent_buffer(leaf);
2692
			}
2693
		} else {
2694
			btrfs_mark_buffer_dirty(leaf);
2695 2696
		}
	}
C
Chris Mason 已提交
2697
	return ret;
2698 2699
}

2700 2701 2702 2703 2704 2705 2706
/*
 * walk up the tree as far as required to find the previous leaf.
 * returns 0 if it found something or 1 if there are no lesser leaves.
 * returns < 0 on io errors.
 */
int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
{
2707
	u64 bytenr;
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
	int slot;
	int level = 1;
	struct extent_buffer *c;
	struct extent_buffer *next = NULL;

	while(level < BTRFS_MAX_LEVEL) {
		if (!path->nodes[level])
			return 1;

		slot = path->slots[level];
		c = path->nodes[level];
		if (slot == 0) {
			level++;
			if (level == BTRFS_MAX_LEVEL)
				return 1;
			continue;
		}
		slot--;

		bytenr = btrfs_node_blockptr(c, slot);
		if (next)
			free_extent_buffer(next);

		next = read_tree_block(root, bytenr,
				       btrfs_level_size(root, level - 1));
		break;
	}
	path->slots[level] = slot;
	while(1) {
		level--;
		c = path->nodes[level];
		free_extent_buffer(c);
2740 2741 2742
		slot = btrfs_header_nritems(next);
		if (slot != 0)
			slot--;
2743
		path->nodes[level] = next;
2744
		path->slots[level] = slot;
2745 2746
		if (!level)
			break;
2747
		next = read_tree_block(root, btrfs_node_blockptr(next, slot),
2748 2749 2750 2751 2752
				       btrfs_level_size(root, level - 1));
	}
	return 0;
}

C
Chris Mason 已提交
2753 2754
/*
 * walk up the tree as far as required to find the next leaf.
2755 2756
 * returns 0 if it found something or 1 if there are no greater leaves.
 * returns < 0 on io errors.
C
Chris Mason 已提交
2757
 */
2758
int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2759 2760 2761
{
	int slot;
	int level = 1;
2762
	u64 bytenr;
2763 2764
	struct extent_buffer *c;
	struct extent_buffer *next = NULL;
2765

2766
	while(level < BTRFS_MAX_LEVEL) {
2767
		if (!path->nodes[level])
2768
			return 1;
2769

2770 2771
		slot = path->slots[level] + 1;
		c = path->nodes[level];
2772
		if (slot >= btrfs_header_nritems(c)) {
2773
			level++;
2774 2775
			if (level == BTRFS_MAX_LEVEL)
				return 1;
2776 2777
			continue;
		}
2778

2779
		bytenr = btrfs_node_blockptr(c, slot);
C
Chris Mason 已提交
2780
		if (next)
2781 2782
			free_extent_buffer(next);

2783
		if (path->reada)
2784
			reada_for_search(root, path, level, slot, 0);
2785

2786 2787
		next = read_tree_block(root, bytenr,
				       btrfs_level_size(root, level -1));
2788 2789 2790 2791 2792 2793
		break;
	}
	path->slots[level] = slot;
	while(1) {
		level--;
		c = path->nodes[level];
2794
		free_extent_buffer(c);
2795 2796 2797 2798
		path->nodes[level] = next;
		path->slots[level] = 0;
		if (!level)
			break;
2799
		if (path->reada)
2800
			reada_for_search(root, path, level, 0, 0);
2801 2802
		next = read_tree_block(root, btrfs_node_blockptr(next, 0),
				       btrfs_level_size(root, level - 1));
2803 2804 2805
	}
	return 0;
}
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

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;
	int ret;

	while(1) {
		if (path->slots[0] == 0) {
			ret = btrfs_prev_leaf(root, path);
			if (ret != 0)
				return ret;
		} else {
			path->slots[0]--;
		}
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
		if (found_key.type == type)
			return 0;
	}
	return 1;
}
反馈
建议
客服 返回
顶部