2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
20 #include "transaction.h"
21 #include "print-tree.h"
24 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
25 *root, struct btrfs_path *path, int level);
26 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
27 *root, struct btrfs_key *ins_key,
28 struct btrfs_path *path, int data_size, int extend);
29 static int push_node_left(struct btrfs_trans_handle *trans,
30 struct btrfs_root *root, struct extent_buffer *dst,
31 struct extent_buffer *src, int empty);
32 static int balance_node_right(struct btrfs_trans_handle *trans,
33 struct btrfs_root *root,
34 struct extent_buffer *dst_buf,
35 struct extent_buffer *src_buf);
37 inline void btrfs_init_path(struct btrfs_path *p)
39 memset(p, 0, sizeof(*p));
42 struct btrfs_path *btrfs_alloc_path(void)
44 struct btrfs_path *path;
45 path = kmalloc(sizeof(struct btrfs_path), GFP_NOFS);
47 btrfs_init_path(path);
53 void btrfs_free_path(struct btrfs_path *p)
55 btrfs_release_path(NULL, p);
59 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
62 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
65 free_extent_buffer(p->nodes[i]);
67 memset(p, 0, sizeof(*p));
70 static void add_root_to_dirty_list(struct btrfs_root *root)
72 if (root->track_dirty && list_empty(&root->dirty_list)) {
73 list_add(&root->dirty_list,
74 &root->fs_info->dirty_cowonly_roots);
78 int btrfs_copy_root(struct btrfs_trans_handle *trans,
79 struct btrfs_root *root,
80 struct extent_buffer *buf,
81 struct extent_buffer **cow_ret, u64 new_root_objectid)
83 struct extent_buffer *cow;
86 struct btrfs_root *new_root;
87 struct btrfs_disk_key disk_key;
89 new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
93 memcpy(new_root, root, sizeof(*new_root));
94 new_root->root_key.objectid = new_root_objectid;
96 WARN_ON(root->ref_cows && trans->transid !=
97 root->fs_info->running_transaction->transid);
98 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
100 level = btrfs_header_level(buf);
102 btrfs_item_key(buf, &disk_key, 0);
104 btrfs_node_key(buf, &disk_key, 0);
105 cow = btrfs_alloc_free_block(trans, new_root, buf->len,
106 new_root_objectid, &disk_key,
107 level, buf->start, 0);
113 copy_extent_buffer(cow, buf, 0, 0, cow->len);
114 btrfs_set_header_bytenr(cow, cow->start);
115 btrfs_set_header_generation(cow, trans->transid);
116 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
117 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
118 BTRFS_HEADER_FLAG_RELOC);
119 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
120 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
122 btrfs_set_header_owner(cow, new_root_objectid);
124 write_extent_buffer(cow, root->fs_info->fsid,
125 (unsigned long)btrfs_header_fsid(cow),
128 WARN_ON(btrfs_header_generation(buf) > trans->transid);
129 ret = btrfs_inc_ref(trans, new_root, cow, 0);
135 btrfs_mark_buffer_dirty(cow);
140 int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
141 struct btrfs_root *root)
143 struct extent_buffer *c;
144 struct extent_buffer *old = root->node;
146 struct btrfs_disk_key disk_key = {0,0,0};
150 c = btrfs_alloc_free_block(trans, root,
151 btrfs_level_size(root, 0),
152 root->root_key.objectid,
153 &disk_key, level, 0, 0);
156 extent_buffer_get(c);
159 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
160 btrfs_set_header_level(c, level);
161 btrfs_set_header_bytenr(c, c->start);
162 btrfs_set_header_generation(c, trans->transid);
163 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
164 btrfs_set_header_owner(c, root->root_key.objectid);
166 write_extent_buffer(c, root->fs_info->fsid,
167 (unsigned long)btrfs_header_fsid(c),
170 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
171 (unsigned long)btrfs_header_chunk_tree_uuid(c),
174 btrfs_mark_buffer_dirty(c);
176 free_extent_buffer(old);
178 add_root_to_dirty_list(root);
183 * check if the tree block can be shared by multiple trees
185 int btrfs_block_can_be_shared(struct btrfs_root *root,
186 struct extent_buffer *buf)
189 * Tree blocks not in refernece counted trees and tree roots
190 * are never shared. If a block was allocated after the last
191 * snapshot and the block was not allocated by tree relocation,
192 * we know the block is not shared.
194 if (root->ref_cows &&
195 buf != root->node && buf != root->commit_root &&
196 (btrfs_header_generation(buf) <=
197 btrfs_root_last_snapshot(&root->root_item) ||
198 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
200 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
201 if (root->ref_cows &&
202 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
208 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
209 struct btrfs_root *root,
210 struct extent_buffer *buf,
211 struct extent_buffer *cow)
220 * Backrefs update rules:
222 * Always use full backrefs for extent pointers in tree block
223 * allocated by tree relocation.
225 * If a shared tree block is no longer referenced by its owner
226 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
227 * use full backrefs for extent pointers in tree block.
229 * If a tree block is been relocating
230 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
231 * use full backrefs for extent pointers in tree block.
232 * The reason for this is some operations (such as drop tree)
233 * are only allowed for blocks use full backrefs.
236 if (btrfs_block_can_be_shared(root, buf)) {
237 ret = btrfs_lookup_extent_info(trans, root, buf->start,
238 btrfs_header_level(buf), 1,
244 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
245 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
246 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
251 owner = btrfs_header_owner(buf);
252 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
253 owner == BTRFS_TREE_RELOC_OBJECTID);
256 if ((owner == root->root_key.objectid ||
257 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
258 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
259 ret = btrfs_inc_ref(trans, root, buf, 1);
262 if (root->root_key.objectid ==
263 BTRFS_TREE_RELOC_OBJECTID) {
264 ret = btrfs_dec_ref(trans, root, buf, 0);
266 ret = btrfs_inc_ref(trans, root, cow, 1);
269 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
272 if (root->root_key.objectid ==
273 BTRFS_TREE_RELOC_OBJECTID)
274 ret = btrfs_inc_ref(trans, root, cow, 1);
276 ret = btrfs_inc_ref(trans, root, cow, 0);
279 if (new_flags != 0) {
280 ret = btrfs_set_block_flags(trans, root, buf->start,
281 btrfs_header_level(buf),
286 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
287 if (root->root_key.objectid ==
288 BTRFS_TREE_RELOC_OBJECTID)
289 ret = btrfs_inc_ref(trans, root, cow, 1);
291 ret = btrfs_inc_ref(trans, root, cow, 0);
293 ret = btrfs_dec_ref(trans, root, buf, 1);
296 clean_tree_block(trans, root, buf);
301 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
302 struct btrfs_root *root,
303 struct extent_buffer *buf,
304 struct extent_buffer *parent, int parent_slot,
305 struct extent_buffer **cow_ret,
306 u64 search_start, u64 empty_size)
308 struct extent_buffer *cow;
309 struct btrfs_disk_key disk_key;
312 WARN_ON(root->ref_cows && trans->transid !=
313 root->fs_info->running_transaction->transid);
314 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
316 level = btrfs_header_level(buf);
319 btrfs_item_key(buf, &disk_key, 0);
321 btrfs_node_key(buf, &disk_key, 0);
323 cow = btrfs_alloc_free_block(trans, root, buf->len,
324 root->root_key.objectid, &disk_key,
325 level, search_start, empty_size);
329 copy_extent_buffer(cow, buf, 0, 0, cow->len);
330 btrfs_set_header_bytenr(cow, cow->start);
331 btrfs_set_header_generation(cow, trans->transid);
332 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
333 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
334 BTRFS_HEADER_FLAG_RELOC);
335 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
336 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
338 btrfs_set_header_owner(cow, root->root_key.objectid);
340 write_extent_buffer(cow, root->fs_info->fsid,
341 (unsigned long)btrfs_header_fsid(cow),
344 WARN_ON(btrfs_header_generation(buf) > trans->transid);
346 update_ref_for_cow(trans, root, buf, cow);
348 if (buf == root->node) {
350 extent_buffer_get(cow);
352 btrfs_free_extent(trans, root, buf->start, buf->len,
353 0, root->root_key.objectid, level, 0);
354 free_extent_buffer(buf);
355 add_root_to_dirty_list(root);
357 btrfs_set_node_blockptr(parent, parent_slot,
359 WARN_ON(trans->transid == 0);
360 btrfs_set_node_ptr_generation(parent, parent_slot,
362 btrfs_mark_buffer_dirty(parent);
363 WARN_ON(btrfs_header_generation(parent) != trans->transid);
365 btrfs_free_extent(trans, root, buf->start, buf->len,
366 0, root->root_key.objectid, level, 1);
368 free_extent_buffer(buf);
369 btrfs_mark_buffer_dirty(cow);
374 static inline int should_cow_block(struct btrfs_trans_handle *trans,
375 struct btrfs_root *root,
376 struct extent_buffer *buf)
378 if (btrfs_header_generation(buf) == trans->transid &&
379 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
380 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
381 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
386 int btrfs_cow_block(struct btrfs_trans_handle *trans,
387 struct btrfs_root *root, struct extent_buffer *buf,
388 struct extent_buffer *parent, int parent_slot,
389 struct extent_buffer **cow_ret)
394 if (trans->transaction != root->fs_info->running_transaction) {
395 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
396 root->fs_info->running_transaction->transid);
400 if (trans->transid != root->fs_info->generation) {
401 printk(KERN_CRIT "trans %llu running %llu\n",
402 (unsigned long long)trans->transid,
403 (unsigned long long)root->fs_info->generation);
406 if (!should_cow_block(trans, root, buf)) {
411 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
412 ret = __btrfs_cow_block(trans, root, buf, parent,
413 parent_slot, cow_ret, search_start, 0);
418 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
420 if (blocknr < other && other - (blocknr + blocksize) < 32768)
422 if (blocknr > other && blocknr - (other + blocksize) < 32768)
429 * compare two keys in a memcmp fashion
431 int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
435 btrfs_disk_key_to_cpu(&k1, disk);
437 if (k1.objectid > k2->objectid)
439 if (k1.objectid < k2->objectid)
441 if (k1.type > k2->type)
443 if (k1.type < k2->type)
445 if (k1.offset > k2->offset)
447 if (k1.offset < k2->offset)
454 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
455 struct btrfs_root *root, struct extent_buffer *parent,
456 int start_slot, int cache_only, u64 *last_ret,
457 struct btrfs_key *progress)
459 struct extent_buffer *cur;
460 struct extent_buffer *tmp;
463 u64 search_start = *last_ret;
473 int progress_passed = 0;
474 struct btrfs_disk_key disk_key;
476 parent_level = btrfs_header_level(parent);
477 if (cache_only && parent_level != 1)
480 if (trans->transaction != root->fs_info->running_transaction) {
481 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
482 root->fs_info->running_transaction->transid);
485 if (trans->transid != root->fs_info->generation) {
486 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
487 root->fs_info->generation);
491 parent_nritems = btrfs_header_nritems(parent);
492 blocksize = btrfs_level_size(root, parent_level - 1);
493 end_slot = parent_nritems;
495 if (parent_nritems == 1)
498 for (i = start_slot; i < end_slot; i++) {
501 if (!parent->map_token) {
502 map_extent_buffer(parent,
503 btrfs_node_key_ptr_offset(i),
504 sizeof(struct btrfs_key_ptr),
505 &parent->map_token, &parent->kaddr,
506 &parent->map_start, &parent->map_len,
509 btrfs_node_key(parent, &disk_key, i);
510 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
514 blocknr = btrfs_node_blockptr(parent, i);
515 gen = btrfs_node_ptr_generation(parent, i);
517 last_block = blocknr;
520 other = btrfs_node_blockptr(parent, i - 1);
521 close = close_blocks(blocknr, other, blocksize);
523 if (close && i < end_slot - 2) {
524 other = btrfs_node_blockptr(parent, i + 1);
525 close = close_blocks(blocknr, other, blocksize);
528 last_block = blocknr;
531 if (parent->map_token) {
532 unmap_extent_buffer(parent, parent->map_token,
534 parent->map_token = NULL;
537 cur = btrfs_find_tree_block(root, blocknr, blocksize);
539 uptodate = btrfs_buffer_uptodate(cur, gen);
542 if (!cur || !uptodate) {
544 free_extent_buffer(cur);
548 cur = read_tree_block(root, blocknr,
550 } else if (!uptodate) {
551 btrfs_read_buffer(cur, gen);
554 if (search_start == 0)
555 search_start = last_block;
557 err = __btrfs_cow_block(trans, root, cur, parent, i,
560 (end_slot - i) * blocksize));
562 free_extent_buffer(cur);
565 search_start = tmp->start;
566 last_block = tmp->start;
567 *last_ret = search_start;
568 if (parent_level == 1)
569 btrfs_clear_buffer_defrag(tmp);
570 free_extent_buffer(tmp);
572 if (parent->map_token) {
573 unmap_extent_buffer(parent, parent->map_token,
575 parent->map_token = NULL;
582 * The leaf data grows from end-to-front in the node.
583 * this returns the address of the start of the last item,
584 * which is the stop of the leaf data stack
586 static inline unsigned int leaf_data_end(struct btrfs_root *root,
587 struct extent_buffer *leaf)
589 u32 nr = btrfs_header_nritems(leaf);
591 return BTRFS_LEAF_DATA_SIZE(root);
592 return btrfs_item_offset_nr(leaf, nr - 1);
595 int btrfs_check_node(struct btrfs_root *root,
596 struct btrfs_disk_key *parent_key,
597 struct extent_buffer *buf)
600 struct btrfs_key cpukey;
601 struct btrfs_disk_key key;
602 u32 nritems = btrfs_header_nritems(buf);
604 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
607 if (parent_key && parent_key->type) {
608 btrfs_node_key(buf, &key, 0);
609 if (memcmp(parent_key, &key, sizeof(key)))
612 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
613 btrfs_node_key(buf, &key, i);
614 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
615 if (btrfs_comp_keys(&key, &cpukey) >= 0)
620 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
622 btrfs_disk_key_to_cpu(&cpukey, parent_key);
624 btrfs_node_key_to_cpu(buf, &cpukey, 0);
625 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
626 buf->start, buf->len,
627 btrfs_header_level(buf));
632 int btrfs_check_leaf(struct btrfs_root *root,
633 struct btrfs_disk_key *parent_key,
634 struct extent_buffer *buf)
637 struct btrfs_key cpukey;
638 struct btrfs_disk_key key;
639 u32 nritems = btrfs_header_nritems(buf);
641 if (btrfs_header_level(buf) != 0) {
642 fprintf(stderr, "leaf is not a leaf %llu\n",
643 (unsigned long long)btrfs_header_bytenr(buf));
646 if (btrfs_leaf_free_space(root, buf) < 0) {
647 fprintf(stderr, "leaf free space incorrect %llu %d\n",
648 (unsigned long long)btrfs_header_bytenr(buf),
649 btrfs_leaf_free_space(root, buf));
656 btrfs_item_key(buf, &key, 0);
657 if (parent_key && parent_key->type &&
658 memcmp(parent_key, &key, sizeof(key))) {
659 fprintf(stderr, "leaf parent key incorrect %llu\n",
660 (unsigned long long)btrfs_header_bytenr(buf));
663 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
664 btrfs_item_key(buf, &key, i);
665 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
666 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
667 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
670 if (btrfs_item_offset_nr(buf, i) !=
671 btrfs_item_end_nr(buf, i + 1)) {
672 fprintf(stderr, "incorrect offsets %u %u\n",
673 btrfs_item_offset_nr(buf, i),
674 btrfs_item_end_nr(buf, i + 1));
677 if (i == 0 && btrfs_item_end_nr(buf, i) !=
678 BTRFS_LEAF_DATA_SIZE(root)) {
679 fprintf(stderr, "bad item end %u wanted %u\n",
680 btrfs_item_end_nr(buf, i),
681 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
687 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
689 btrfs_disk_key_to_cpu(&cpukey, parent_key);
691 btrfs_item_key_to_cpu(buf, &cpukey, 0);
693 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
694 buf->start, buf->len, 0);
699 static int noinline check_block(struct btrfs_root *root,
700 struct btrfs_path *path, int level)
702 struct btrfs_disk_key key;
703 struct btrfs_disk_key *key_ptr = NULL;
704 struct extent_buffer *parent;
706 if (path->nodes[level + 1]) {
707 parent = path->nodes[level + 1];
708 btrfs_node_key(parent, &key, path->slots[level + 1]);
712 return btrfs_check_leaf(root, key_ptr, path->nodes[0]);
713 return btrfs_check_node(root, key_ptr, path->nodes[level]);
717 * search for key in the extent_buffer. The items start at offset p,
718 * and they are item_size apart. There are 'max' items in p.
720 * the slot in the array is returned via slot, and it points to
721 * the place where you would insert key if it is not found in
724 * slot may point to max if the key is bigger than all of the keys
726 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
727 int item_size, struct btrfs_key *key,
734 unsigned long offset;
735 struct btrfs_disk_key *tmp;
738 mid = (low + high) / 2;
739 offset = p + mid * item_size;
741 tmp = (struct btrfs_disk_key *)(eb->data + offset);
742 ret = btrfs_comp_keys(tmp, key);
758 * simple bin_search frontend that does the right thing for
761 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
762 int level, int *slot)
765 return generic_bin_search(eb,
766 offsetof(struct btrfs_leaf, items),
767 sizeof(struct btrfs_item),
768 key, btrfs_header_nritems(eb),
771 return generic_bin_search(eb,
772 offsetof(struct btrfs_node, ptrs),
773 sizeof(struct btrfs_key_ptr),
774 key, btrfs_header_nritems(eb),
780 struct extent_buffer *read_node_slot(struct btrfs_root *root,
781 struct extent_buffer *parent, int slot)
783 int level = btrfs_header_level(parent);
786 if (slot >= btrfs_header_nritems(parent))
791 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
792 btrfs_level_size(root, level - 1),
793 btrfs_node_ptr_generation(parent, slot));
796 static int balance_level(struct btrfs_trans_handle *trans,
797 struct btrfs_root *root,
798 struct btrfs_path *path, int level)
800 struct extent_buffer *right = NULL;
801 struct extent_buffer *mid;
802 struct extent_buffer *left = NULL;
803 struct extent_buffer *parent = NULL;
807 int orig_slot = path->slots[level];
813 mid = path->nodes[level];
814 WARN_ON(btrfs_header_generation(mid) != trans->transid);
816 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
818 if (level < BTRFS_MAX_LEVEL - 1)
819 parent = path->nodes[level + 1];
820 pslot = path->slots[level + 1];
823 * deal with the case where there is only one pointer in the root
824 * by promoting the node below to a root
827 struct extent_buffer *child;
829 if (btrfs_header_nritems(mid) != 1)
832 /* promote the child to a root */
833 child = read_node_slot(root, mid, 0);
835 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
839 add_root_to_dirty_list(root);
840 path->nodes[level] = NULL;
841 clean_tree_block(trans, root, mid);
842 wait_on_tree_block_writeback(root, mid);
843 /* once for the path */
844 free_extent_buffer(mid);
846 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
847 0, root->root_key.objectid,
849 /* once for the root ptr */
850 free_extent_buffer(mid);
853 if (btrfs_header_nritems(mid) >
854 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
857 left = read_node_slot(root, parent, pslot - 1);
859 wret = btrfs_cow_block(trans, root, left,
860 parent, pslot - 1, &left);
866 right = read_node_slot(root, parent, pslot + 1);
868 wret = btrfs_cow_block(trans, root, right,
869 parent, pslot + 1, &right);
876 /* first, try to make some room in the middle buffer */
878 orig_slot += btrfs_header_nritems(left);
879 wret = push_node_left(trans, root, left, mid, 1);
885 * then try to empty the right most buffer into the middle
888 wret = push_node_left(trans, root, mid, right, 1);
889 if (wret < 0 && wret != -ENOSPC)
891 if (btrfs_header_nritems(right) == 0) {
892 u64 bytenr = right->start;
893 u32 blocksize = right->len;
895 clean_tree_block(trans, root, right);
896 wait_on_tree_block_writeback(root, right);
897 free_extent_buffer(right);
899 wret = btrfs_del_ptr(trans, root, path,
900 level + 1, pslot + 1);
903 wret = btrfs_free_extent(trans, root, bytenr,
905 root->root_key.objectid,
910 struct btrfs_disk_key right_key;
911 btrfs_node_key(right, &right_key, 0);
912 btrfs_set_node_key(parent, &right_key, pslot + 1);
913 btrfs_mark_buffer_dirty(parent);
916 if (btrfs_header_nritems(mid) == 1) {
918 * we're not allowed to leave a node with one item in the
919 * tree during a delete. A deletion from lower in the tree
920 * could try to delete the only pointer in this node.
921 * So, pull some keys from the left.
922 * There has to be a left pointer at this point because
923 * otherwise we would have pulled some pointers from the
927 wret = balance_node_right(trans, root, mid, left);
933 wret = push_node_left(trans, root, left, mid, 1);
939 if (btrfs_header_nritems(mid) == 0) {
940 /* we've managed to empty the middle node, drop it */
941 u64 bytenr = mid->start;
942 u32 blocksize = mid->len;
943 clean_tree_block(trans, root, mid);
944 wait_on_tree_block_writeback(root, mid);
945 free_extent_buffer(mid);
947 wret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
950 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
951 0, root->root_key.objectid,
956 /* update the parent key to reflect our changes */
957 struct btrfs_disk_key mid_key;
958 btrfs_node_key(mid, &mid_key, 0);
959 btrfs_set_node_key(parent, &mid_key, pslot);
960 btrfs_mark_buffer_dirty(parent);
963 /* update the path */
965 if (btrfs_header_nritems(left) > orig_slot) {
966 extent_buffer_get(left);
967 path->nodes[level] = left;
968 path->slots[level + 1] -= 1;
969 path->slots[level] = orig_slot;
971 free_extent_buffer(mid);
973 orig_slot -= btrfs_header_nritems(left);
974 path->slots[level] = orig_slot;
977 /* double check we haven't messed things up */
978 check_block(root, path, level);
980 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
984 free_extent_buffer(right);
986 free_extent_buffer(left);
990 /* returns zero if the push worked, non-zero otherwise */
991 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
992 struct btrfs_root *root,
993 struct btrfs_path *path, int level)
995 struct extent_buffer *right = NULL;
996 struct extent_buffer *mid;
997 struct extent_buffer *left = NULL;
998 struct extent_buffer *parent = NULL;
1002 int orig_slot = path->slots[level];
1007 mid = path->nodes[level];
1008 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1010 if (level < BTRFS_MAX_LEVEL - 1)
1011 parent = path->nodes[level + 1];
1012 pslot = path->slots[level + 1];
1017 left = read_node_slot(root, parent, pslot - 1);
1019 /* first, try to make some room in the middle buffer */
1022 left_nr = btrfs_header_nritems(left);
1023 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1026 ret = btrfs_cow_block(trans, root, left, parent,
1031 wret = push_node_left(trans, root,
1038 struct btrfs_disk_key disk_key;
1039 orig_slot += left_nr;
1040 btrfs_node_key(mid, &disk_key, 0);
1041 btrfs_set_node_key(parent, &disk_key, pslot);
1042 btrfs_mark_buffer_dirty(parent);
1043 if (btrfs_header_nritems(left) > orig_slot) {
1044 path->nodes[level] = left;
1045 path->slots[level + 1] -= 1;
1046 path->slots[level] = orig_slot;
1047 free_extent_buffer(mid);
1050 btrfs_header_nritems(left);
1051 path->slots[level] = orig_slot;
1052 free_extent_buffer(left);
1056 free_extent_buffer(left);
1058 right= read_node_slot(root, parent, pslot + 1);
1061 * then try to empty the right most buffer into the middle
1065 right_nr = btrfs_header_nritems(right);
1066 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1069 ret = btrfs_cow_block(trans, root, right,
1075 wret = balance_node_right(trans, root,
1082 struct btrfs_disk_key disk_key;
1084 btrfs_node_key(right, &disk_key, 0);
1085 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1086 btrfs_mark_buffer_dirty(parent);
1088 if (btrfs_header_nritems(mid) <= orig_slot) {
1089 path->nodes[level] = right;
1090 path->slots[level + 1] += 1;
1091 path->slots[level] = orig_slot -
1092 btrfs_header_nritems(mid);
1093 free_extent_buffer(mid);
1095 free_extent_buffer(right);
1099 free_extent_buffer(right);
1105 * readahead one full node of leaves
1107 void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
1108 int level, int slot, u64 objectid)
1110 struct extent_buffer *node;
1111 struct btrfs_disk_key disk_key;
1117 int direction = path->reada;
1118 struct extent_buffer *eb;
1126 if (!path->nodes[level])
1129 node = path->nodes[level];
1130 search = btrfs_node_blockptr(node, slot);
1131 blocksize = btrfs_level_size(root, level - 1);
1132 eb = btrfs_find_tree_block(root, search, blocksize);
1134 free_extent_buffer(eb);
1138 highest_read = search;
1139 lowest_read = search;
1141 nritems = btrfs_header_nritems(node);
1144 if (direction < 0) {
1148 } else if (direction > 0) {
1153 if (path->reada < 0 && objectid) {
1154 btrfs_node_key(node, &disk_key, nr);
1155 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1158 search = btrfs_node_blockptr(node, nr);
1159 if ((search >= lowest_read && search <= highest_read) ||
1160 (search < lowest_read && lowest_read - search <= 32768) ||
1161 (search > highest_read && search - highest_read <= 32768)) {
1162 readahead_tree_block(root, search, blocksize,
1163 btrfs_node_ptr_generation(node, nr));
1167 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1169 if(nread > (1024 * 1024) || nscan > 128)
1172 if (search < lowest_read)
1173 lowest_read = search;
1174 if (search > highest_read)
1175 highest_read = search;
1180 * look for key in the tree. path is filled in with nodes along the way
1181 * if key is found, we return zero and you can find the item in the leaf
1182 * level of the path (level 0)
1184 * If the key isn't found, the path points to the slot where it should
1185 * be inserted, and 1 is returned. If there are other errors during the
1186 * search a negative error number is returned.
1188 * if ins_len > 0, nodes and leaves will be split as we walk down the
1189 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1192 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1193 *root, struct btrfs_key *key, struct btrfs_path *p, int
1196 struct extent_buffer *b;
1200 int should_reada = p->reada;
1201 u8 lowest_level = 0;
1203 lowest_level = p->lowest_level;
1204 WARN_ON(lowest_level && ins_len > 0);
1205 WARN_ON(p->nodes[0] != NULL);
1207 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1211 extent_buffer_get(b);
1213 level = btrfs_header_level(b);
1216 wret = btrfs_cow_block(trans, root, b,
1217 p->nodes[level + 1],
1218 p->slots[level + 1],
1221 free_extent_buffer(b);
1225 BUG_ON(!cow && ins_len);
1226 if (level != btrfs_header_level(b))
1228 level = btrfs_header_level(b);
1229 p->nodes[level] = b;
1230 ret = check_block(root, p, level);
1233 ret = bin_search(b, key, level, &slot);
1235 if (ret && slot > 0)
1237 p->slots[level] = slot;
1238 if ((p->search_for_split || ins_len > 0) &&
1239 btrfs_header_nritems(b) >=
1240 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1241 int sret = split_node(trans, root, p, level);
1245 b = p->nodes[level];
1246 slot = p->slots[level];
1247 } else if (ins_len < 0) {
1248 int sret = balance_level(trans, root, p,
1252 b = p->nodes[level];
1254 btrfs_release_path(NULL, p);
1257 slot = p->slots[level];
1258 BUG_ON(btrfs_header_nritems(b) == 1);
1260 /* this is only true while dropping a snapshot */
1261 if (level == lowest_level)
1265 reada_for_search(root, p, level, slot,
1268 b = read_node_slot(root, b, slot);
1269 if (!extent_buffer_uptodate(b))
1272 p->slots[level] = slot;
1274 ins_len > btrfs_leaf_free_space(root, b)) {
1275 int sret = split_leaf(trans, root, key,
1276 p, ins_len, ret == 0);
1288 * adjust the pointers going up the tree, starting at level
1289 * making sure the right key of each node is points to 'key'.
1290 * This is used after shifting pointers to the left, so it stops
1291 * fixing up pointers when a given leaf/node is not in slot 0 of the
1294 * If this fails to write a tree block, it returns -1, but continues
1295 * fixing up the blocks in ram so the tree is consistent.
1297 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1298 struct btrfs_root *root, struct btrfs_path *path,
1299 struct btrfs_disk_key *key, int level)
1303 struct extent_buffer *t;
1305 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1306 int tslot = path->slots[i];
1307 if (!path->nodes[i])
1310 btrfs_set_node_key(t, key, tslot);
1311 btrfs_mark_buffer_dirty(path->nodes[i]);
1321 * This function isn't completely safe. It's the caller's responsibility
1322 * that the new key won't break the order
1324 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1325 struct btrfs_root *root, struct btrfs_path *path,
1326 struct btrfs_key *new_key)
1328 struct btrfs_disk_key disk_key;
1329 struct extent_buffer *eb;
1332 eb = path->nodes[0];
1333 slot = path->slots[0];
1335 btrfs_item_key(eb, &disk_key, slot - 1);
1336 if (btrfs_comp_keys(&disk_key, new_key) >= 0)
1339 if (slot < btrfs_header_nritems(eb) - 1) {
1340 btrfs_item_key(eb, &disk_key, slot + 1);
1341 if (btrfs_comp_keys(&disk_key, new_key) <= 0)
1345 btrfs_cpu_key_to_disk(&disk_key, new_key);
1346 btrfs_set_item_key(eb, &disk_key, slot);
1347 btrfs_mark_buffer_dirty(eb);
1349 fixup_low_keys(trans, root, path, &disk_key, 1);
1354 * try to push data from one node into the next node left in the
1357 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1358 * error, and > 0 if there was no room in the left hand block.
1360 static int push_node_left(struct btrfs_trans_handle *trans,
1361 struct btrfs_root *root, struct extent_buffer *dst,
1362 struct extent_buffer *src, int empty)
1369 src_nritems = btrfs_header_nritems(src);
1370 dst_nritems = btrfs_header_nritems(dst);
1371 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1372 WARN_ON(btrfs_header_generation(src) != trans->transid);
1373 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1375 if (!empty && src_nritems <= 8)
1378 if (push_items <= 0) {
1383 push_items = min(src_nritems, push_items);
1384 if (push_items < src_nritems) {
1385 /* leave at least 8 pointers in the node if
1386 * we aren't going to empty it
1388 if (src_nritems - push_items < 8) {
1389 if (push_items <= 8)
1395 push_items = min(src_nritems - 8, push_items);
1397 copy_extent_buffer(dst, src,
1398 btrfs_node_key_ptr_offset(dst_nritems),
1399 btrfs_node_key_ptr_offset(0),
1400 push_items * sizeof(struct btrfs_key_ptr));
1402 if (push_items < src_nritems) {
1403 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1404 btrfs_node_key_ptr_offset(push_items),
1405 (src_nritems - push_items) *
1406 sizeof(struct btrfs_key_ptr));
1408 btrfs_set_header_nritems(src, src_nritems - push_items);
1409 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1410 btrfs_mark_buffer_dirty(src);
1411 btrfs_mark_buffer_dirty(dst);
1417 * try to push data from one node into the next node right in the
1420 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1421 * error, and > 0 if there was no room in the right hand block.
1423 * this will only push up to 1/2 the contents of the left node over
1425 static int balance_node_right(struct btrfs_trans_handle *trans,
1426 struct btrfs_root *root,
1427 struct extent_buffer *dst,
1428 struct extent_buffer *src)
1436 WARN_ON(btrfs_header_generation(src) != trans->transid);
1437 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1439 src_nritems = btrfs_header_nritems(src);
1440 dst_nritems = btrfs_header_nritems(dst);
1441 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1442 if (push_items <= 0) {
1446 if (src_nritems < 4) {
1450 max_push = src_nritems / 2 + 1;
1451 /* don't try to empty the node */
1452 if (max_push >= src_nritems) {
1456 if (max_push < push_items)
1457 push_items = max_push;
1459 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1460 btrfs_node_key_ptr_offset(0),
1462 sizeof(struct btrfs_key_ptr));
1464 copy_extent_buffer(dst, src,
1465 btrfs_node_key_ptr_offset(0),
1466 btrfs_node_key_ptr_offset(src_nritems - push_items),
1467 push_items * sizeof(struct btrfs_key_ptr));
1469 btrfs_set_header_nritems(src, src_nritems - push_items);
1470 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1472 btrfs_mark_buffer_dirty(src);
1473 btrfs_mark_buffer_dirty(dst);
1479 * helper function to insert a new root level in the tree.
1480 * A new node is allocated, and a single item is inserted to
1481 * point to the existing root
1483 * returns zero on success or < 0 on failure.
1485 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1486 struct btrfs_root *root,
1487 struct btrfs_path *path, int level)
1490 struct extent_buffer *lower;
1491 struct extent_buffer *c;
1492 struct extent_buffer *old;
1493 struct btrfs_disk_key lower_key;
1495 BUG_ON(path->nodes[level]);
1496 BUG_ON(path->nodes[level-1] != root->node);
1498 lower = path->nodes[level-1];
1500 btrfs_item_key(lower, &lower_key, 0);
1502 btrfs_node_key(lower, &lower_key, 0);
1504 c = btrfs_alloc_free_block(trans, root, root->nodesize,
1505 root->root_key.objectid, &lower_key,
1506 level, root->node->start, 0);
1511 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
1512 btrfs_set_header_nritems(c, 1);
1513 btrfs_set_header_level(c, level);
1514 btrfs_set_header_bytenr(c, c->start);
1515 btrfs_set_header_generation(c, trans->transid);
1516 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
1517 btrfs_set_header_owner(c, root->root_key.objectid);
1519 write_extent_buffer(c, root->fs_info->fsid,
1520 (unsigned long)btrfs_header_fsid(c),
1523 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1524 (unsigned long)btrfs_header_chunk_tree_uuid(c),
1527 btrfs_set_node_key(c, &lower_key, 0);
1528 btrfs_set_node_blockptr(c, 0, lower->start);
1529 lower_gen = btrfs_header_generation(lower);
1530 WARN_ON(lower_gen != trans->transid);
1532 btrfs_set_node_ptr_generation(c, 0, lower_gen);
1534 btrfs_mark_buffer_dirty(c);
1539 /* the super has an extra ref to root->node */
1540 free_extent_buffer(old);
1542 add_root_to_dirty_list(root);
1543 extent_buffer_get(c);
1544 path->nodes[level] = c;
1545 path->slots[level] = 0;
1550 * worker function to insert a single pointer in a node.
1551 * the node should have enough room for the pointer already
1553 * slot and level indicate where you want the key to go, and
1554 * blocknr is the block the key points to.
1556 * returns zero on success and < 0 on any error
1558 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1559 *root, struct btrfs_path *path, struct btrfs_disk_key
1560 *key, u64 bytenr, int slot, int level)
1562 struct extent_buffer *lower;
1565 BUG_ON(!path->nodes[level]);
1566 lower = path->nodes[level];
1567 nritems = btrfs_header_nritems(lower);
1570 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1572 if (slot != nritems) {
1573 memmove_extent_buffer(lower,
1574 btrfs_node_key_ptr_offset(slot + 1),
1575 btrfs_node_key_ptr_offset(slot),
1576 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1578 btrfs_set_node_key(lower, key, slot);
1579 btrfs_set_node_blockptr(lower, slot, bytenr);
1580 WARN_ON(trans->transid == 0);
1581 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1582 btrfs_set_header_nritems(lower, nritems + 1);
1583 btrfs_mark_buffer_dirty(lower);
1588 * split the node at the specified level in path in two.
1589 * The path is corrected to point to the appropriate node after the split
1591 * Before splitting this tries to make some room in the node by pushing
1592 * left and right, if either one works, it returns right away.
1594 * returns 0 on success and < 0 on failure
1596 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1597 *root, struct btrfs_path *path, int level)
1599 struct extent_buffer *c;
1600 struct extent_buffer *split;
1601 struct btrfs_disk_key disk_key;
1607 c = path->nodes[level];
1608 WARN_ON(btrfs_header_generation(c) != trans->transid);
1609 if (c == root->node) {
1610 /* trying to split the root, lets make a new one */
1611 ret = insert_new_root(trans, root, path, level + 1);
1615 ret = push_nodes_for_insert(trans, root, path, level);
1616 c = path->nodes[level];
1617 if (!ret && btrfs_header_nritems(c) <
1618 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
1624 c_nritems = btrfs_header_nritems(c);
1625 mid = (c_nritems + 1) / 2;
1626 btrfs_node_key(c, &disk_key, mid);
1628 split = btrfs_alloc_free_block(trans, root, root->nodesize,
1629 root->root_key.objectid,
1630 &disk_key, level, c->start, 0);
1632 return PTR_ERR(split);
1634 memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
1635 btrfs_set_header_level(split, btrfs_header_level(c));
1636 btrfs_set_header_bytenr(split, split->start);
1637 btrfs_set_header_generation(split, trans->transid);
1638 btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
1639 btrfs_set_header_owner(split, root->root_key.objectid);
1640 write_extent_buffer(split, root->fs_info->fsid,
1641 (unsigned long)btrfs_header_fsid(split),
1643 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
1644 (unsigned long)btrfs_header_chunk_tree_uuid(split),
1648 copy_extent_buffer(split, c,
1649 btrfs_node_key_ptr_offset(0),
1650 btrfs_node_key_ptr_offset(mid),
1651 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1652 btrfs_set_header_nritems(split, c_nritems - mid);
1653 btrfs_set_header_nritems(c, mid);
1656 btrfs_mark_buffer_dirty(c);
1657 btrfs_mark_buffer_dirty(split);
1659 wret = insert_ptr(trans, root, path, &disk_key, split->start,
1660 path->slots[level + 1] + 1,
1665 if (path->slots[level] >= mid) {
1666 path->slots[level] -= mid;
1667 free_extent_buffer(c);
1668 path->nodes[level] = split;
1669 path->slots[level + 1] += 1;
1671 free_extent_buffer(split);
1677 * how many bytes are required to store the items in a leaf. start
1678 * and nr indicate which items in the leaf to check. This totals up the
1679 * space used both by the item structs and the item data
1681 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1684 int nritems = btrfs_header_nritems(l);
1685 int end = min(nritems, start + nr) - 1;
1689 data_len = btrfs_item_end_nr(l, start);
1690 data_len = data_len - btrfs_item_offset_nr(l, end);
1691 data_len += sizeof(struct btrfs_item) * nr;
1692 WARN_ON(data_len < 0);
1697 * The space between the end of the leaf items and
1698 * the start of the leaf data. IOW, how much room
1699 * the leaf has left for both items and data
1701 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1703 int nritems = btrfs_header_nritems(leaf);
1705 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1707 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1708 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1709 leaf_space_used(leaf, 0, nritems), nritems);
1715 * push some data in the path leaf to the right, trying to free up at
1716 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1718 * returns 1 if the push failed because the other node didn't have enough
1719 * room, 0 if everything worked out and < 0 if there were major errors.
1721 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1722 *root, struct btrfs_path *path, int data_size,
1725 struct extent_buffer *left = path->nodes[0];
1726 struct extent_buffer *right;
1727 struct extent_buffer *upper;
1728 struct btrfs_disk_key disk_key;
1734 struct btrfs_item *item;
1742 slot = path->slots[1];
1743 if (!path->nodes[1]) {
1746 upper = path->nodes[1];
1747 if (slot >= btrfs_header_nritems(upper) - 1)
1750 right = read_node_slot(root, upper, slot + 1);
1751 free_space = btrfs_leaf_free_space(root, right);
1752 if (free_space < data_size) {
1753 free_extent_buffer(right);
1757 /* cow and double check */
1758 ret = btrfs_cow_block(trans, root, right, upper,
1761 free_extent_buffer(right);
1764 free_space = btrfs_leaf_free_space(root, right);
1765 if (free_space < data_size) {
1766 free_extent_buffer(right);
1770 left_nritems = btrfs_header_nritems(left);
1771 if (left_nritems == 0) {
1772 free_extent_buffer(right);
1781 i = left_nritems - 1;
1783 item = btrfs_item_nr(left, i);
1785 if (path->slots[0] == i)
1786 push_space += data_size + sizeof(*item);
1788 this_item_size = btrfs_item_size(left, item);
1789 if (this_item_size + sizeof(*item) + push_space > free_space)
1792 push_space += this_item_size + sizeof(*item);
1798 if (push_items == 0) {
1799 free_extent_buffer(right);
1803 if (!empty && push_items == left_nritems)
1806 /* push left to right */
1807 right_nritems = btrfs_header_nritems(right);
1809 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1810 push_space -= leaf_data_end(root, left);
1812 /* make room in the right data area */
1813 data_end = leaf_data_end(root, right);
1814 memmove_extent_buffer(right,
1815 btrfs_leaf_data(right) + data_end - push_space,
1816 btrfs_leaf_data(right) + data_end,
1817 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1819 /* copy from the left data area */
1820 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1821 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1822 btrfs_leaf_data(left) + leaf_data_end(root, left),
1825 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1826 btrfs_item_nr_offset(0),
1827 right_nritems * sizeof(struct btrfs_item));
1829 /* copy the items from left to right */
1830 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1831 btrfs_item_nr_offset(left_nritems - push_items),
1832 push_items * sizeof(struct btrfs_item));
1834 /* update the item pointers */
1835 right_nritems += push_items;
1836 btrfs_set_header_nritems(right, right_nritems);
1837 push_space = BTRFS_LEAF_DATA_SIZE(root);
1838 for (i = 0; i < right_nritems; i++) {
1839 item = btrfs_item_nr(right, i);
1840 push_space -= btrfs_item_size(right, item);
1841 btrfs_set_item_offset(right, item, push_space);
1844 left_nritems -= push_items;
1845 btrfs_set_header_nritems(left, left_nritems);
1848 btrfs_mark_buffer_dirty(left);
1849 btrfs_mark_buffer_dirty(right);
1851 btrfs_item_key(right, &disk_key, 0);
1852 btrfs_set_node_key(upper, &disk_key, slot + 1);
1853 btrfs_mark_buffer_dirty(upper);
1855 /* then fixup the leaf pointer in the path */
1856 if (path->slots[0] >= left_nritems) {
1857 path->slots[0] -= left_nritems;
1858 free_extent_buffer(path->nodes[0]);
1859 path->nodes[0] = right;
1860 path->slots[1] += 1;
1862 free_extent_buffer(right);
1867 * push some data in the path leaf to the left, trying to free up at
1868 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1870 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1871 *root, struct btrfs_path *path, int data_size,
1874 struct btrfs_disk_key disk_key;
1875 struct extent_buffer *right = path->nodes[0];
1876 struct extent_buffer *left;
1882 struct btrfs_item *item;
1883 u32 old_left_nritems;
1889 u32 old_left_item_size;
1891 slot = path->slots[1];
1894 if (!path->nodes[1])
1897 right_nritems = btrfs_header_nritems(right);
1898 if (right_nritems == 0) {
1902 left = read_node_slot(root, path->nodes[1], slot - 1);
1903 free_space = btrfs_leaf_free_space(root, left);
1904 if (free_space < data_size) {
1905 free_extent_buffer(left);
1909 /* cow and double check */
1910 ret = btrfs_cow_block(trans, root, left,
1911 path->nodes[1], slot - 1, &left);
1913 /* we hit -ENOSPC, but it isn't fatal here */
1914 free_extent_buffer(left);
1918 free_space = btrfs_leaf_free_space(root, left);
1919 if (free_space < data_size) {
1920 free_extent_buffer(left);
1927 nr = right_nritems - 1;
1929 for (i = 0; i < nr; i++) {
1930 item = btrfs_item_nr(right, i);
1932 if (path->slots[0] == i)
1933 push_space += data_size + sizeof(*item);
1935 this_item_size = btrfs_item_size(right, item);
1936 if (this_item_size + sizeof(*item) + push_space > free_space)
1940 push_space += this_item_size + sizeof(*item);
1943 if (push_items == 0) {
1944 free_extent_buffer(left);
1947 if (!empty && push_items == btrfs_header_nritems(right))
1950 /* push data from right to left */
1951 copy_extent_buffer(left, right,
1952 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1953 btrfs_item_nr_offset(0),
1954 push_items * sizeof(struct btrfs_item));
1956 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1957 btrfs_item_offset_nr(right, push_items -1);
1959 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1960 leaf_data_end(root, left) - push_space,
1961 btrfs_leaf_data(right) +
1962 btrfs_item_offset_nr(right, push_items - 1),
1964 old_left_nritems = btrfs_header_nritems(left);
1965 BUG_ON(old_left_nritems == 0);
1967 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1968 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1971 item = btrfs_item_nr(left, i);
1972 ioff = btrfs_item_offset(left, item);
1973 btrfs_set_item_offset(left, item,
1974 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1976 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1978 /* fixup right node */
1979 if (push_items > right_nritems) {
1980 printk("push items %d nr %u\n", push_items, right_nritems);
1984 if (push_items < right_nritems) {
1985 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1986 leaf_data_end(root, right);
1987 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1988 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1989 btrfs_leaf_data(right) +
1990 leaf_data_end(root, right), push_space);
1992 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1993 btrfs_item_nr_offset(push_items),
1994 (btrfs_header_nritems(right) - push_items) *
1995 sizeof(struct btrfs_item));
1997 right_nritems -= push_items;
1998 btrfs_set_header_nritems(right, right_nritems);
1999 push_space = BTRFS_LEAF_DATA_SIZE(root);
2000 for (i = 0; i < right_nritems; i++) {
2001 item = btrfs_item_nr(right, i);
2002 push_space = push_space - btrfs_item_size(right, item);
2003 btrfs_set_item_offset(right, item, push_space);
2006 btrfs_mark_buffer_dirty(left);
2008 btrfs_mark_buffer_dirty(right);
2010 btrfs_item_key(right, &disk_key, 0);
2011 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2015 /* then fixup the leaf pointer in the path */
2016 if (path->slots[0] < push_items) {
2017 path->slots[0] += old_left_nritems;
2018 free_extent_buffer(path->nodes[0]);
2019 path->nodes[0] = left;
2020 path->slots[1] -= 1;
2022 free_extent_buffer(left);
2023 path->slots[0] -= push_items;
2025 BUG_ON(path->slots[0] < 0);
2030 * split the path's leaf in two, making sure there is at least data_size
2031 * available for the resulting leaf level of the path.
2033 * returns 0 if all went well and < 0 on failure.
2035 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2036 struct btrfs_root *root,
2037 struct btrfs_path *path,
2038 struct extent_buffer *l,
2039 struct extent_buffer *right,
2040 int slot, int mid, int nritems)
2047 struct btrfs_disk_key disk_key;
2049 nritems = nritems - mid;
2050 btrfs_set_header_nritems(right, nritems);
2051 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2053 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2054 btrfs_item_nr_offset(mid),
2055 nritems * sizeof(struct btrfs_item));
2057 copy_extent_buffer(right, l,
2058 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2059 data_copy_size, btrfs_leaf_data(l) +
2060 leaf_data_end(root, l), data_copy_size);
2062 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2063 btrfs_item_end_nr(l, mid);
2065 for (i = 0; i < nritems; i++) {
2066 struct btrfs_item *item = btrfs_item_nr(right, i);
2067 u32 ioff = btrfs_item_offset(right, item);
2068 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2071 btrfs_set_header_nritems(l, mid);
2073 btrfs_item_key(right, &disk_key, 0);
2074 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2075 path->slots[1] + 1, 1);
2079 btrfs_mark_buffer_dirty(right);
2080 btrfs_mark_buffer_dirty(l);
2081 BUG_ON(path->slots[0] != slot);
2084 free_extent_buffer(path->nodes[0]);
2085 path->nodes[0] = right;
2086 path->slots[0] -= mid;
2087 path->slots[1] += 1;
2089 free_extent_buffer(right);
2092 BUG_ON(path->slots[0] < 0);
2098 * split the path's leaf in two, making sure there is at least data_size
2099 * available for the resulting leaf level of the path.
2101 * returns 0 if all went well and < 0 on failure.
2103 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2104 struct btrfs_root *root,
2105 struct btrfs_key *ins_key,
2106 struct btrfs_path *path, int data_size,
2109 struct btrfs_disk_key disk_key;
2110 struct extent_buffer *l;
2114 struct extent_buffer *right;
2118 int num_doubles = 0;
2120 /* first try to make some room by pushing left and right */
2121 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2122 wret = push_leaf_right(trans, root, path, data_size, 0);
2126 wret = push_leaf_left(trans, root, path, data_size, 0);
2132 /* did the pushes work? */
2133 if (btrfs_leaf_free_space(root, l) >= data_size)
2137 if (!path->nodes[1]) {
2138 ret = insert_new_root(trans, root, path, 1);
2145 slot = path->slots[0];
2146 nritems = btrfs_header_nritems(l);
2147 mid = (nritems + 1) / 2;
2151 leaf_space_used(l, mid, nritems - mid) + data_size >
2152 BTRFS_LEAF_DATA_SIZE(root)) {
2153 if (slot >= nritems) {
2157 if (mid != nritems &&
2158 leaf_space_used(l, mid, nritems - mid) +
2159 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2165 if (leaf_space_used(l, 0, mid) + data_size >
2166 BTRFS_LEAF_DATA_SIZE(root)) {
2167 if (!extend && data_size && slot == 0) {
2169 } else if ((extend || !data_size) && slot == 0) {
2173 if (mid != nritems &&
2174 leaf_space_used(l, mid, nritems - mid) +
2175 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2183 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2185 btrfs_item_key(l, &disk_key, mid);
2187 right = btrfs_alloc_free_block(trans, root, root->leafsize,
2188 root->root_key.objectid,
2189 &disk_key, 0, l->start, 0);
2190 if (IS_ERR(right)) {
2192 return PTR_ERR(right);
2195 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2196 btrfs_set_header_bytenr(right, right->start);
2197 btrfs_set_header_generation(right, trans->transid);
2198 btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
2199 btrfs_set_header_owner(right, root->root_key.objectid);
2200 btrfs_set_header_level(right, 0);
2201 write_extent_buffer(right, root->fs_info->fsid,
2202 (unsigned long)btrfs_header_fsid(right),
2205 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2206 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2211 btrfs_set_header_nritems(right, 0);
2212 wret = insert_ptr(trans, root, path,
2213 &disk_key, right->start,
2214 path->slots[1] + 1, 1);
2218 free_extent_buffer(path->nodes[0]);
2219 path->nodes[0] = right;
2221 path->slots[1] += 1;
2223 btrfs_set_header_nritems(right, 0);
2224 wret = insert_ptr(trans, root, path,
2230 free_extent_buffer(path->nodes[0]);
2231 path->nodes[0] = right;
2233 if (path->slots[1] == 0) {
2234 wret = fixup_low_keys(trans, root,
2235 path, &disk_key, 1);
2240 btrfs_mark_buffer_dirty(right);
2244 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2248 BUG_ON(num_doubles != 0);
2257 * This function splits a single item into two items,
2258 * giving 'new_key' to the new item and splitting the
2259 * old one at split_offset (from the start of the item).
2261 * The path may be released by this operation. After
2262 * the split, the path is pointing to the old item. The
2263 * new item is going to be in the same node as the old one.
2265 * Note, the item being split must be smaller enough to live alone on
2266 * a tree block with room for one extra struct btrfs_item
2268 * This allows us to split the item in place, keeping a lock on the
2269 * leaf the entire time.
2271 int btrfs_split_item(struct btrfs_trans_handle *trans,
2272 struct btrfs_root *root,
2273 struct btrfs_path *path,
2274 struct btrfs_key *new_key,
2275 unsigned long split_offset)
2278 struct extent_buffer *leaf;
2279 struct btrfs_key orig_key;
2280 struct btrfs_item *item;
2281 struct btrfs_item *new_item;
2286 struct btrfs_disk_key disk_key;
2289 leaf = path->nodes[0];
2290 btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
2291 if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
2294 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2295 btrfs_release_path(root, path);
2297 path->search_for_split = 1;
2299 ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
2300 path->search_for_split = 0;
2302 /* if our item isn't there or got smaller, return now */
2303 if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
2308 ret = split_leaf(trans, root, &orig_key, path, 0, 0);
2311 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
2312 leaf = path->nodes[0];
2315 item = btrfs_item_nr(leaf, path->slots[0]);
2316 orig_offset = btrfs_item_offset(leaf, item);
2317 item_size = btrfs_item_size(leaf, item);
2320 buf = kmalloc(item_size, GFP_NOFS);
2321 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
2322 path->slots[0]), item_size);
2323 slot = path->slots[0] + 1;
2324 leaf = path->nodes[0];
2326 nritems = btrfs_header_nritems(leaf);
2328 if (slot != nritems) {
2329 /* shift the items */
2330 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2331 btrfs_item_nr_offset(slot),
2332 (nritems - slot) * sizeof(struct btrfs_item));
2336 btrfs_cpu_key_to_disk(&disk_key, new_key);
2337 btrfs_set_item_key(leaf, &disk_key, slot);
2339 new_item = btrfs_item_nr(leaf, slot);
2341 btrfs_set_item_offset(leaf, new_item, orig_offset);
2342 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
2344 btrfs_set_item_offset(leaf, item,
2345 orig_offset + item_size - split_offset);
2346 btrfs_set_item_size(leaf, item, split_offset);
2348 btrfs_set_header_nritems(leaf, nritems + 1);
2350 /* write the data for the start of the original item */
2351 write_extent_buffer(leaf, buf,
2352 btrfs_item_ptr_offset(leaf, path->slots[0]),
2355 /* write the data for the new item */
2356 write_extent_buffer(leaf, buf + split_offset,
2357 btrfs_item_ptr_offset(leaf, slot),
2358 item_size - split_offset);
2359 btrfs_mark_buffer_dirty(leaf);
2362 if (btrfs_leaf_free_space(root, leaf) < 0) {
2363 btrfs_print_leaf(root, leaf);
2370 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2371 struct btrfs_root *root,
2372 struct btrfs_path *path,
2373 u32 new_size, int from_end)
2377 struct extent_buffer *leaf;
2378 struct btrfs_item *item;
2380 unsigned int data_end;
2381 unsigned int old_data_start;
2382 unsigned int old_size;
2383 unsigned int size_diff;
2386 leaf = path->nodes[0];
2387 slot = path->slots[0];
2389 old_size = btrfs_item_size_nr(leaf, slot);
2390 if (old_size == new_size)
2393 nritems = btrfs_header_nritems(leaf);
2394 data_end = leaf_data_end(root, leaf);
2396 old_data_start = btrfs_item_offset_nr(leaf, slot);
2398 size_diff = old_size - new_size;
2401 BUG_ON(slot >= nritems);
2404 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2406 /* first correct the data pointers */
2407 for (i = slot; i < nritems; i++) {
2409 item = btrfs_item_nr(leaf, i);
2410 ioff = btrfs_item_offset(leaf, item);
2411 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2414 /* shift the data */
2416 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2417 data_end + size_diff, btrfs_leaf_data(leaf) +
2418 data_end, old_data_start + new_size - data_end);
2420 struct btrfs_disk_key disk_key;
2423 btrfs_item_key(leaf, &disk_key, slot);
2425 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2427 struct btrfs_file_extent_item *fi;
2429 fi = btrfs_item_ptr(leaf, slot,
2430 struct btrfs_file_extent_item);
2431 fi = (struct btrfs_file_extent_item *)(
2432 (unsigned long)fi - size_diff);
2434 if (btrfs_file_extent_type(leaf, fi) ==
2435 BTRFS_FILE_EXTENT_INLINE) {
2436 ptr = btrfs_item_ptr_offset(leaf, slot);
2437 memmove_extent_buffer(leaf, ptr,
2439 offsetof(struct btrfs_file_extent_item,
2444 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2445 data_end + size_diff, btrfs_leaf_data(leaf) +
2446 data_end, old_data_start - data_end);
2448 offset = btrfs_disk_key_offset(&disk_key);
2449 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2450 btrfs_set_item_key(leaf, &disk_key, slot);
2452 fixup_low_keys(trans, root, path, &disk_key, 1);
2455 item = btrfs_item_nr(leaf, slot);
2456 btrfs_set_item_size(leaf, item, new_size);
2457 btrfs_mark_buffer_dirty(leaf);
2460 if (btrfs_leaf_free_space(root, leaf) < 0) {
2461 btrfs_print_leaf(root, leaf);
2467 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2468 struct btrfs_root *root, struct btrfs_path *path,
2473 struct extent_buffer *leaf;
2474 struct btrfs_item *item;
2476 unsigned int data_end;
2477 unsigned int old_data;
2478 unsigned int old_size;
2481 leaf = path->nodes[0];
2483 nritems = btrfs_header_nritems(leaf);
2484 data_end = leaf_data_end(root, leaf);
2486 if (btrfs_leaf_free_space(root, leaf) < data_size) {
2487 btrfs_print_leaf(root, leaf);
2490 slot = path->slots[0];
2491 old_data = btrfs_item_end_nr(leaf, slot);
2494 if (slot >= nritems) {
2495 btrfs_print_leaf(root, leaf);
2496 printk("slot %d too large, nritems %d\n", slot, nritems);
2501 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2503 /* first correct the data pointers */
2504 for (i = slot; i < nritems; i++) {
2506 item = btrfs_item_nr(leaf, i);
2507 ioff = btrfs_item_offset(leaf, item);
2508 btrfs_set_item_offset(leaf, item, ioff - data_size);
2511 /* shift the data */
2512 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2513 data_end - data_size, btrfs_leaf_data(leaf) +
2514 data_end, old_data - data_end);
2516 data_end = old_data;
2517 old_size = btrfs_item_size_nr(leaf, slot);
2518 item = btrfs_item_nr(leaf, slot);
2519 btrfs_set_item_size(leaf, item, old_size + data_size);
2520 btrfs_mark_buffer_dirty(leaf);
2523 if (btrfs_leaf_free_space(root, leaf) < 0) {
2524 btrfs_print_leaf(root, leaf);
2531 * Given a key and some data, insert an item into the tree.
2532 * This does all the path init required, making room in the tree if needed.
2534 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2535 struct btrfs_root *root,
2536 struct btrfs_path *path,
2537 struct btrfs_key *cpu_key, u32 *data_size,
2540 struct extent_buffer *leaf;
2541 struct btrfs_item *item;
2548 unsigned int data_end;
2549 struct btrfs_disk_key disk_key;
2551 for (i = 0; i < nr; i++) {
2552 total_data += data_size[i];
2555 /* create a root if there isn't one */
2559 total_size = total_data + nr * sizeof(struct btrfs_item);
2560 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2567 leaf = path->nodes[0];
2569 nritems = btrfs_header_nritems(leaf);
2570 data_end = leaf_data_end(root, leaf);
2572 if (btrfs_leaf_free_space(root, leaf) < total_size) {
2573 btrfs_print_leaf(root, leaf);
2574 printk("not enough freespace need %u have %d\n",
2575 total_size, btrfs_leaf_free_space(root, leaf));
2579 slot = path->slots[0];
2582 if (slot != nritems) {
2584 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2586 if (old_data < data_end) {
2587 btrfs_print_leaf(root, leaf);
2588 printk("slot %d old_data %d data_end %d\n",
2589 slot, old_data, data_end);
2593 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2595 /* first correct the data pointers */
2596 for (i = slot; i < nritems; i++) {
2599 item = btrfs_item_nr(leaf, i);
2600 ioff = btrfs_item_offset(leaf, item);
2601 btrfs_set_item_offset(leaf, item, ioff - total_data);
2604 /* shift the items */
2605 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2606 btrfs_item_nr_offset(slot),
2607 (nritems - slot) * sizeof(struct btrfs_item));
2609 /* shift the data */
2610 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2611 data_end - total_data, btrfs_leaf_data(leaf) +
2612 data_end, old_data - data_end);
2613 data_end = old_data;
2616 /* setup the item for the new data */
2617 for (i = 0; i < nr; i++) {
2618 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2619 btrfs_set_item_key(leaf, &disk_key, slot + i);
2620 item = btrfs_item_nr(leaf, slot + i);
2621 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2622 data_end -= data_size[i];
2623 btrfs_set_item_size(leaf, item, data_size[i]);
2625 btrfs_set_header_nritems(leaf, nritems + nr);
2626 btrfs_mark_buffer_dirty(leaf);
2630 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2631 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2634 if (btrfs_leaf_free_space(root, leaf) < 0) {
2635 btrfs_print_leaf(root, leaf);
2644 * Given a key and some data, insert an item into the tree.
2645 * This does all the path init required, making room in the tree if needed.
2647 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2648 *root, struct btrfs_key *cpu_key, void *data, u32
2652 struct btrfs_path *path;
2653 struct extent_buffer *leaf;
2656 path = btrfs_alloc_path();
2658 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2660 leaf = path->nodes[0];
2661 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2662 write_extent_buffer(leaf, data, ptr, data_size);
2663 btrfs_mark_buffer_dirty(leaf);
2665 btrfs_free_path(path);
2670 * delete the pointer from a given node.
2672 * If the delete empties a node, the node is removed from the tree,
2673 * continuing all the way the root if required. The root is converted into
2674 * a leaf if all the nodes are emptied.
2676 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2677 struct btrfs_path *path, int level, int slot)
2679 struct extent_buffer *parent = path->nodes[level];
2684 nritems = btrfs_header_nritems(parent);
2685 if (slot != nritems -1) {
2686 memmove_extent_buffer(parent,
2687 btrfs_node_key_ptr_offset(slot),
2688 btrfs_node_key_ptr_offset(slot + 1),
2689 sizeof(struct btrfs_key_ptr) *
2690 (nritems - slot - 1));
2693 btrfs_set_header_nritems(parent, nritems);
2694 if (nritems == 0 && parent == root->node) {
2695 BUG_ON(btrfs_header_level(root->node) != 1);
2696 /* just turn the root into a leaf and break */
2697 btrfs_set_header_level(root->node, 0);
2698 } else if (slot == 0) {
2699 struct btrfs_disk_key disk_key;
2701 btrfs_node_key(parent, &disk_key, 0);
2702 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2706 btrfs_mark_buffer_dirty(parent);
2711 * a helper function to delete the leaf pointed to by path->slots[1] and
2714 * This deletes the pointer in path->nodes[1] and frees the leaf
2715 * block extent. zero is returned if it all worked out, < 0 otherwise.
2717 * The path must have already been setup for deleting the leaf, including
2718 * all the proper balancing. path->nodes[1] must be locked.
2720 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
2721 struct btrfs_root *root,
2722 struct btrfs_path *path,
2723 struct extent_buffer *leaf)
2727 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
2728 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
2732 ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
2733 0, root->root_key.objectid, 0, 0);
2738 * delete the item at the leaf level in path. If that empties
2739 * the leaf, remove it from the tree
2741 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2742 struct btrfs_path *path, int slot, int nr)
2744 struct extent_buffer *leaf;
2745 struct btrfs_item *item;
2753 leaf = path->nodes[0];
2754 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2756 for (i = 0; i < nr; i++)
2757 dsize += btrfs_item_size_nr(leaf, slot + i);
2759 nritems = btrfs_header_nritems(leaf);
2761 if (slot + nr != nritems) {
2763 int data_end = leaf_data_end(root, leaf);
2765 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2767 btrfs_leaf_data(leaf) + data_end,
2768 last_off - data_end);
2770 for (i = slot + nr; i < nritems; i++) {
2773 item = btrfs_item_nr(leaf, i);
2774 ioff = btrfs_item_offset(leaf, item);
2775 btrfs_set_item_offset(leaf, item, ioff + dsize);
2778 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2779 btrfs_item_nr_offset(slot + nr),
2780 sizeof(struct btrfs_item) *
2781 (nritems - slot - nr));
2783 btrfs_set_header_nritems(leaf, nritems - nr);
2786 /* delete the leaf if we've emptied it */
2788 if (leaf == root->node) {
2789 btrfs_set_header_level(leaf, 0);
2791 clean_tree_block(trans, root, leaf);
2792 wait_on_tree_block_writeback(root, leaf);
2794 wret = btrfs_del_leaf(trans, root, path, leaf);
2800 int used = leaf_space_used(leaf, 0, nritems);
2802 struct btrfs_disk_key disk_key;
2804 btrfs_item_key(leaf, &disk_key, 0);
2805 wret = fixup_low_keys(trans, root, path,
2811 /* delete the leaf if it is mostly empty */
2812 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2813 /* push_leaf_left fixes the path.
2814 * make sure the path still points to our leaf
2815 * for possible call to del_ptr below
2817 slot = path->slots[1];
2818 extent_buffer_get(leaf);
2820 wret = push_leaf_left(trans, root, path, 1, 1);
2821 if (wret < 0 && wret != -ENOSPC)
2824 if (path->nodes[0] == leaf &&
2825 btrfs_header_nritems(leaf)) {
2826 wret = push_leaf_right(trans, root, path, 1, 1);
2827 if (wret < 0 && wret != -ENOSPC)
2831 if (btrfs_header_nritems(leaf) == 0) {
2832 clean_tree_block(trans, root, leaf);
2833 wait_on_tree_block_writeback(root, leaf);
2835 path->slots[1] = slot;
2836 ret = btrfs_del_leaf(trans, root, path, leaf);
2838 free_extent_buffer(leaf);
2841 btrfs_mark_buffer_dirty(leaf);
2842 free_extent_buffer(leaf);
2845 btrfs_mark_buffer_dirty(leaf);
2852 * walk up the tree as far as required to find the previous leaf.
2853 * returns 0 if it found something or 1 if there are no lesser leaves.
2854 * returns < 0 on io errors.
2856 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2860 struct extent_buffer *c;
2861 struct extent_buffer *next = NULL;
2863 while(level < BTRFS_MAX_LEVEL) {
2864 if (!path->nodes[level])
2867 slot = path->slots[level];
2868 c = path->nodes[level];
2871 if (level == BTRFS_MAX_LEVEL)
2877 next = read_node_slot(root, c, slot);
2880 path->slots[level] = slot;
2883 c = path->nodes[level];
2884 free_extent_buffer(c);
2885 slot = btrfs_header_nritems(next);
2888 path->nodes[level] = next;
2889 path->slots[level] = slot;
2892 next = read_node_slot(root, next, slot);
2898 * walk up the tree as far as required to find the next leaf.
2899 * returns 0 if it found something or 1 if there are no greater leaves.
2900 * returns < 0 on io errors.
2902 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2906 struct extent_buffer *c;
2907 struct extent_buffer *next = NULL;
2909 while(level < BTRFS_MAX_LEVEL) {
2910 if (!path->nodes[level])
2913 slot = path->slots[level] + 1;
2914 c = path->nodes[level];
2915 if (slot >= btrfs_header_nritems(c)) {
2917 if (level == BTRFS_MAX_LEVEL)
2923 reada_for_search(root, path, level, slot, 0);
2925 next = read_node_slot(root, c, slot);
2930 path->slots[level] = slot;
2933 c = path->nodes[level];
2934 free_extent_buffer(c);
2935 path->nodes[level] = next;
2936 path->slots[level] = 0;
2940 reada_for_search(root, path, level, 0, 0);
2941 next = read_node_slot(root, next, 0);
2948 int btrfs_previous_item(struct btrfs_root *root,
2949 struct btrfs_path *path, u64 min_objectid,
2952 struct btrfs_key found_key;
2953 struct extent_buffer *leaf;
2957 if (path->slots[0] == 0) {
2958 ret = btrfs_prev_leaf(root, path);
2964 leaf = path->nodes[0];
2965 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2966 if (found_key.type == type)