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 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);
141 * check if the tree block can be shared by multiple trees
143 int btrfs_block_can_be_shared(struct btrfs_root *root,
144 struct extent_buffer *buf)
147 * Tree blocks not in refernece counted trees and tree roots
148 * are never shared. If a block was allocated after the last
149 * snapshot and the block was not allocated by tree relocation,
150 * we know the block is not shared.
152 if (root->ref_cows &&
153 buf != root->node && buf != root->commit_root &&
154 (btrfs_header_generation(buf) <=
155 btrfs_root_last_snapshot(&root->root_item) ||
156 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
158 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
159 if (root->ref_cows &&
160 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
166 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
167 struct btrfs_root *root,
168 struct extent_buffer *buf,
169 struct extent_buffer *cow)
178 * Backrefs update rules:
180 * Always use full backrefs for extent pointers in tree block
181 * allocated by tree relocation.
183 * If a shared tree block is no longer referenced by its owner
184 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
185 * use full backrefs for extent pointers in tree block.
187 * If a tree block is been relocating
188 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
189 * use full backrefs for extent pointers in tree block.
190 * The reason for this is some operations (such as drop tree)
191 * are only allowed for blocks use full backrefs.
194 if (btrfs_block_can_be_shared(root, buf)) {
195 ret = btrfs_lookup_extent_info(trans, root, buf->start,
196 btrfs_header_level(buf), 1,
202 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
203 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
204 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
209 owner = btrfs_header_owner(buf);
210 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
211 owner == BTRFS_TREE_RELOC_OBJECTID);
214 if ((owner == root->root_key.objectid ||
215 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
216 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
217 ret = btrfs_inc_ref(trans, root, buf, 1);
220 if (root->root_key.objectid ==
221 BTRFS_TREE_RELOC_OBJECTID) {
222 ret = btrfs_dec_ref(trans, root, buf, 0);
224 ret = btrfs_inc_ref(trans, root, cow, 1);
227 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
230 if (root->root_key.objectid ==
231 BTRFS_TREE_RELOC_OBJECTID)
232 ret = btrfs_inc_ref(trans, root, cow, 1);
234 ret = btrfs_inc_ref(trans, root, cow, 0);
237 if (new_flags != 0) {
238 ret = btrfs_set_block_flags(trans, root, buf->start,
239 btrfs_header_level(buf),
244 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
245 if (root->root_key.objectid ==
246 BTRFS_TREE_RELOC_OBJECTID)
247 ret = btrfs_inc_ref(trans, root, cow, 1);
249 ret = btrfs_inc_ref(trans, root, cow, 0);
251 ret = btrfs_dec_ref(trans, root, buf, 1);
254 clean_tree_block(trans, root, buf);
259 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
260 struct btrfs_root *root,
261 struct extent_buffer *buf,
262 struct extent_buffer *parent, int parent_slot,
263 struct extent_buffer **cow_ret,
264 u64 search_start, u64 empty_size)
266 struct extent_buffer *cow;
267 struct btrfs_disk_key disk_key;
270 WARN_ON(root->ref_cows && trans->transid !=
271 root->fs_info->running_transaction->transid);
272 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
274 level = btrfs_header_level(buf);
277 btrfs_item_key(buf, &disk_key, 0);
279 btrfs_node_key(buf, &disk_key, 0);
281 cow = btrfs_alloc_free_block(trans, root, buf->len,
282 root->root_key.objectid, &disk_key,
283 level, search_start, empty_size);
287 copy_extent_buffer(cow, buf, 0, 0, cow->len);
288 btrfs_set_header_bytenr(cow, cow->start);
289 btrfs_set_header_generation(cow, trans->transid);
290 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
291 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
292 BTRFS_HEADER_FLAG_RELOC);
293 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
294 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
296 btrfs_set_header_owner(cow, root->root_key.objectid);
298 write_extent_buffer(cow, root->fs_info->fsid,
299 (unsigned long)btrfs_header_fsid(cow),
302 WARN_ON(btrfs_header_generation(buf) > trans->transid);
304 update_ref_for_cow(trans, root, buf, cow);
306 if (buf == root->node) {
308 extent_buffer_get(cow);
310 btrfs_free_extent(trans, root, buf->start, buf->len,
311 0, root->root_key.objectid, level, 0);
312 free_extent_buffer(buf);
313 add_root_to_dirty_list(root);
315 btrfs_set_node_blockptr(parent, parent_slot,
317 WARN_ON(trans->transid == 0);
318 btrfs_set_node_ptr_generation(parent, parent_slot,
320 btrfs_mark_buffer_dirty(parent);
321 WARN_ON(btrfs_header_generation(parent) != trans->transid);
323 btrfs_free_extent(trans, root, buf->start, buf->len,
324 0, root->root_key.objectid, level, 1);
326 free_extent_buffer(buf);
327 btrfs_mark_buffer_dirty(cow);
332 static inline int should_cow_block(struct btrfs_trans_handle *trans,
333 struct btrfs_root *root,
334 struct extent_buffer *buf)
336 if (btrfs_header_generation(buf) == trans->transid &&
337 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
338 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
339 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
344 int btrfs_cow_block(struct btrfs_trans_handle *trans,
345 struct btrfs_root *root, struct extent_buffer *buf,
346 struct extent_buffer *parent, int parent_slot,
347 struct extent_buffer **cow_ret)
352 if (trans->transaction != root->fs_info->running_transaction) {
353 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
354 root->fs_info->running_transaction->transid);
358 if (trans->transid != root->fs_info->generation) {
359 printk(KERN_CRIT "trans %llu running %llu\n",
360 (unsigned long long)trans->transid,
361 (unsigned long long)root->fs_info->generation);
364 if (!should_cow_block(trans, root, buf)) {
369 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
370 ret = __btrfs_cow_block(trans, root, buf, parent,
371 parent_slot, cow_ret, search_start, 0);
376 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
378 if (blocknr < other && other - (blocknr + blocksize) < 32768)
380 if (blocknr > other && blocknr - (other + blocksize) < 32768)
387 * compare two keys in a memcmp fashion
389 int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
393 btrfs_disk_key_to_cpu(&k1, disk);
395 if (k1.objectid > k2->objectid)
397 if (k1.objectid < k2->objectid)
399 if (k1.type > k2->type)
401 if (k1.type < k2->type)
403 if (k1.offset > k2->offset)
405 if (k1.offset < k2->offset)
412 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
413 struct btrfs_root *root, struct extent_buffer *parent,
414 int start_slot, int cache_only, u64 *last_ret,
415 struct btrfs_key *progress)
417 struct extent_buffer *cur;
418 struct extent_buffer *tmp;
421 u64 search_start = *last_ret;
431 int progress_passed = 0;
432 struct btrfs_disk_key disk_key;
434 parent_level = btrfs_header_level(parent);
435 if (cache_only && parent_level != 1)
438 if (trans->transaction != root->fs_info->running_transaction) {
439 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
440 root->fs_info->running_transaction->transid);
443 if (trans->transid != root->fs_info->generation) {
444 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
445 root->fs_info->generation);
449 parent_nritems = btrfs_header_nritems(parent);
450 blocksize = btrfs_level_size(root, parent_level - 1);
451 end_slot = parent_nritems;
453 if (parent_nritems == 1)
456 for (i = start_slot; i < end_slot; i++) {
459 if (!parent->map_token) {
460 map_extent_buffer(parent,
461 btrfs_node_key_ptr_offset(i),
462 sizeof(struct btrfs_key_ptr),
463 &parent->map_token, &parent->kaddr,
464 &parent->map_start, &parent->map_len,
467 btrfs_node_key(parent, &disk_key, i);
468 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
472 blocknr = btrfs_node_blockptr(parent, i);
473 gen = btrfs_node_ptr_generation(parent, i);
475 last_block = blocknr;
478 other = btrfs_node_blockptr(parent, i - 1);
479 close = close_blocks(blocknr, other, blocksize);
481 if (close && i < end_slot - 2) {
482 other = btrfs_node_blockptr(parent, i + 1);
483 close = close_blocks(blocknr, other, blocksize);
486 last_block = blocknr;
489 if (parent->map_token) {
490 unmap_extent_buffer(parent, parent->map_token,
492 parent->map_token = NULL;
495 cur = btrfs_find_tree_block(root, blocknr, blocksize);
497 uptodate = btrfs_buffer_uptodate(cur, gen);
500 if (!cur || !uptodate) {
502 free_extent_buffer(cur);
506 cur = read_tree_block(root, blocknr,
508 } else if (!uptodate) {
509 btrfs_read_buffer(cur, gen);
512 if (search_start == 0)
513 search_start = last_block;
515 err = __btrfs_cow_block(trans, root, cur, parent, i,
518 (end_slot - i) * blocksize));
520 free_extent_buffer(cur);
523 search_start = tmp->start;
524 last_block = tmp->start;
525 *last_ret = search_start;
526 if (parent_level == 1)
527 btrfs_clear_buffer_defrag(tmp);
528 free_extent_buffer(tmp);
530 if (parent->map_token) {
531 unmap_extent_buffer(parent, parent->map_token,
533 parent->map_token = NULL;
540 * The leaf data grows from end-to-front in the node.
541 * this returns the address of the start of the last item,
542 * which is the stop of the leaf data stack
544 static inline unsigned int leaf_data_end(struct btrfs_root *root,
545 struct extent_buffer *leaf)
547 u32 nr = btrfs_header_nritems(leaf);
549 return BTRFS_LEAF_DATA_SIZE(root);
550 return btrfs_item_offset_nr(leaf, nr - 1);
553 int btrfs_check_node(struct btrfs_root *root,
554 struct btrfs_disk_key *parent_key,
555 struct extent_buffer *buf)
558 struct btrfs_key cpukey;
559 struct btrfs_disk_key key;
560 u32 nritems = btrfs_header_nritems(buf);
562 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
565 if (parent_key && parent_key->type) {
566 btrfs_node_key(buf, &key, 0);
567 if (memcmp(parent_key, &key, sizeof(key)))
570 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
571 btrfs_node_key(buf, &key, i);
572 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
573 if (btrfs_comp_keys(&key, &cpukey) >= 0)
578 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
580 btrfs_disk_key_to_cpu(&cpukey, parent_key);
582 btrfs_node_key_to_cpu(buf, &cpukey, 0);
583 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
584 buf->start, buf->len,
585 btrfs_header_level(buf));
590 int btrfs_check_leaf(struct btrfs_root *root,
591 struct btrfs_disk_key *parent_key,
592 struct extent_buffer *buf)
595 struct btrfs_key cpukey;
596 struct btrfs_disk_key key;
597 u32 nritems = btrfs_header_nritems(buf);
599 if (nritems * sizeof(struct btrfs_item) > buf->len) {
600 fprintf(stderr, "invalid number of items %llu\n",
601 (unsigned long long)buf->start);
605 if (btrfs_header_level(buf) != 0) {
606 fprintf(stderr, "leaf is not a leaf %llu\n",
607 (unsigned long long)btrfs_header_bytenr(buf));
610 if (btrfs_leaf_free_space(root, buf) < 0) {
611 fprintf(stderr, "leaf free space incorrect %llu %d\n",
612 (unsigned long long)btrfs_header_bytenr(buf),
613 btrfs_leaf_free_space(root, buf));
620 btrfs_item_key(buf, &key, 0);
621 if (parent_key && parent_key->type &&
622 memcmp(parent_key, &key, sizeof(key))) {
623 fprintf(stderr, "leaf parent key incorrect %llu\n",
624 (unsigned long long)btrfs_header_bytenr(buf));
627 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
628 btrfs_item_key(buf, &key, i);
629 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
630 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
631 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
634 if (btrfs_item_offset_nr(buf, i) !=
635 btrfs_item_end_nr(buf, i + 1)) {
636 fprintf(stderr, "incorrect offsets %u %u\n",
637 btrfs_item_offset_nr(buf, i),
638 btrfs_item_end_nr(buf, i + 1));
641 if (i == 0 && btrfs_item_end_nr(buf, i) !=
642 BTRFS_LEAF_DATA_SIZE(root)) {
643 fprintf(stderr, "bad item end %u wanted %u\n",
644 btrfs_item_end_nr(buf, i),
645 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
651 if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID) {
653 btrfs_disk_key_to_cpu(&cpukey, parent_key);
655 btrfs_item_key_to_cpu(buf, &cpukey, 0);
657 btrfs_add_corrupt_extent_record(root->fs_info, &cpukey,
658 buf->start, buf->len, 0);
663 static int noinline check_block(struct btrfs_root *root,
664 struct btrfs_path *path, int level)
666 struct btrfs_disk_key key;
667 struct btrfs_disk_key *key_ptr = NULL;
668 struct extent_buffer *parent;
670 if (path->nodes[level + 1]) {
671 parent = path->nodes[level + 1];
672 btrfs_node_key(parent, &key, path->slots[level + 1]);
676 return btrfs_check_leaf(root, key_ptr, path->nodes[0]);
677 return btrfs_check_node(root, key_ptr, path->nodes[level]);
681 * search for key in the extent_buffer. The items start at offset p,
682 * and they are item_size apart. There are 'max' items in p.
684 * the slot in the array is returned via slot, and it points to
685 * the place where you would insert key if it is not found in
688 * slot may point to max if the key is bigger than all of the keys
690 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
691 int item_size, struct btrfs_key *key,
698 unsigned long offset;
699 struct btrfs_disk_key *tmp;
702 mid = (low + high) / 2;
703 offset = p + mid * item_size;
705 tmp = (struct btrfs_disk_key *)(eb->data + offset);
706 ret = btrfs_comp_keys(tmp, key);
722 * simple bin_search frontend that does the right thing for
725 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
726 int level, int *slot)
729 return generic_bin_search(eb,
730 offsetof(struct btrfs_leaf, items),
731 sizeof(struct btrfs_item),
732 key, btrfs_header_nritems(eb),
735 return generic_bin_search(eb,
736 offsetof(struct btrfs_node, ptrs),
737 sizeof(struct btrfs_key_ptr),
738 key, btrfs_header_nritems(eb),
744 struct extent_buffer *read_node_slot(struct btrfs_root *root,
745 struct extent_buffer *parent, int slot)
747 int level = btrfs_header_level(parent);
750 if (slot >= btrfs_header_nritems(parent))
756 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
757 btrfs_level_size(root, level - 1),
758 btrfs_node_ptr_generation(parent, slot));
761 static int balance_level(struct btrfs_trans_handle *trans,
762 struct btrfs_root *root,
763 struct btrfs_path *path, int level)
765 struct extent_buffer *right = NULL;
766 struct extent_buffer *mid;
767 struct extent_buffer *left = NULL;
768 struct extent_buffer *parent = NULL;
772 int orig_slot = path->slots[level];
778 mid = path->nodes[level];
779 WARN_ON(btrfs_header_generation(mid) != trans->transid);
781 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
783 if (level < BTRFS_MAX_LEVEL - 1) {
784 parent = path->nodes[level + 1];
785 pslot = path->slots[level + 1];
789 * deal with the case where there is only one pointer in the root
790 * by promoting the node below to a root
793 struct extent_buffer *child;
795 if (btrfs_header_nritems(mid) != 1)
798 /* promote the child to a root */
799 child = read_node_slot(root, mid, 0);
801 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
805 add_root_to_dirty_list(root);
806 path->nodes[level] = NULL;
807 clean_tree_block(trans, root, mid);
808 wait_on_tree_block_writeback(root, mid);
809 /* once for the path */
810 free_extent_buffer(mid);
812 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
813 0, root->root_key.objectid,
815 /* once for the root ptr */
816 free_extent_buffer(mid);
819 if (btrfs_header_nritems(mid) >
820 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
823 left = read_node_slot(root, parent, pslot - 1);
825 wret = btrfs_cow_block(trans, root, left,
826 parent, pslot - 1, &left);
832 right = read_node_slot(root, parent, pslot + 1);
834 wret = btrfs_cow_block(trans, root, right,
835 parent, pslot + 1, &right);
842 /* first, try to make some room in the middle buffer */
844 orig_slot += btrfs_header_nritems(left);
845 wret = push_node_left(trans, root, left, mid, 1);
851 * then try to empty the right most buffer into the middle
854 wret = push_node_left(trans, root, mid, right, 1);
855 if (wret < 0 && wret != -ENOSPC)
857 if (btrfs_header_nritems(right) == 0) {
858 u64 bytenr = right->start;
859 u32 blocksize = right->len;
861 clean_tree_block(trans, root, right);
862 wait_on_tree_block_writeback(root, right);
863 free_extent_buffer(right);
865 wret = btrfs_del_ptr(trans, root, path,
866 level + 1, pslot + 1);
869 wret = btrfs_free_extent(trans, root, bytenr,
871 root->root_key.objectid,
876 struct btrfs_disk_key right_key;
877 btrfs_node_key(right, &right_key, 0);
878 btrfs_set_node_key(parent, &right_key, pslot + 1);
879 btrfs_mark_buffer_dirty(parent);
882 if (btrfs_header_nritems(mid) == 1) {
884 * we're not allowed to leave a node with one item in the
885 * tree during a delete. A deletion from lower in the tree
886 * could try to delete the only pointer in this node.
887 * So, pull some keys from the left.
888 * There has to be a left pointer at this point because
889 * otherwise we would have pulled some pointers from the
893 wret = balance_node_right(trans, root, mid, left);
899 wret = push_node_left(trans, root, left, mid, 1);
905 if (btrfs_header_nritems(mid) == 0) {
906 /* we've managed to empty the middle node, drop it */
907 u64 bytenr = mid->start;
908 u32 blocksize = mid->len;
909 clean_tree_block(trans, root, mid);
910 wait_on_tree_block_writeback(root, mid);
911 free_extent_buffer(mid);
913 wret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
916 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
917 0, root->root_key.objectid,
922 /* update the parent key to reflect our changes */
923 struct btrfs_disk_key mid_key;
924 btrfs_node_key(mid, &mid_key, 0);
925 btrfs_set_node_key(parent, &mid_key, pslot);
926 btrfs_mark_buffer_dirty(parent);
929 /* update the path */
931 if (btrfs_header_nritems(left) > orig_slot) {
932 extent_buffer_get(left);
933 path->nodes[level] = left;
934 path->slots[level + 1] -= 1;
935 path->slots[level] = orig_slot;
937 free_extent_buffer(mid);
939 orig_slot -= btrfs_header_nritems(left);
940 path->slots[level] = orig_slot;
943 /* double check we haven't messed things up */
944 check_block(root, path, level);
946 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
950 free_extent_buffer(right);
952 free_extent_buffer(left);
956 /* returns zero if the push worked, non-zero otherwise */
957 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
958 struct btrfs_root *root,
959 struct btrfs_path *path, int level)
961 struct extent_buffer *right = NULL;
962 struct extent_buffer *mid;
963 struct extent_buffer *left = NULL;
964 struct extent_buffer *parent = NULL;
968 int orig_slot = path->slots[level];
973 mid = path->nodes[level];
974 WARN_ON(btrfs_header_generation(mid) != trans->transid);
976 if (level < BTRFS_MAX_LEVEL - 1) {
977 parent = path->nodes[level + 1];
978 pslot = path->slots[level + 1];
984 left = read_node_slot(root, parent, pslot - 1);
986 /* first, try to make some room in the middle buffer */
989 left_nr = btrfs_header_nritems(left);
990 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
993 ret = btrfs_cow_block(trans, root, left, parent,
998 wret = push_node_left(trans, root,
1005 struct btrfs_disk_key disk_key;
1006 orig_slot += left_nr;
1007 btrfs_node_key(mid, &disk_key, 0);
1008 btrfs_set_node_key(parent, &disk_key, pslot);
1009 btrfs_mark_buffer_dirty(parent);
1010 if (btrfs_header_nritems(left) > orig_slot) {
1011 path->nodes[level] = left;
1012 path->slots[level + 1] -= 1;
1013 path->slots[level] = orig_slot;
1014 free_extent_buffer(mid);
1017 btrfs_header_nritems(left);
1018 path->slots[level] = orig_slot;
1019 free_extent_buffer(left);
1023 free_extent_buffer(left);
1025 right= read_node_slot(root, parent, pslot + 1);
1028 * then try to empty the right most buffer into the middle
1032 right_nr = btrfs_header_nritems(right);
1033 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1036 ret = btrfs_cow_block(trans, root, right,
1042 wret = balance_node_right(trans, root,
1049 struct btrfs_disk_key disk_key;
1051 btrfs_node_key(right, &disk_key, 0);
1052 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1053 btrfs_mark_buffer_dirty(parent);
1055 if (btrfs_header_nritems(mid) <= orig_slot) {
1056 path->nodes[level] = right;
1057 path->slots[level + 1] += 1;
1058 path->slots[level] = orig_slot -
1059 btrfs_header_nritems(mid);
1060 free_extent_buffer(mid);
1062 free_extent_buffer(right);
1066 free_extent_buffer(right);
1072 * readahead one full node of leaves
1074 void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
1075 int level, int slot, u64 objectid)
1077 struct extent_buffer *node;
1078 struct btrfs_disk_key disk_key;
1084 int direction = path->reada;
1085 struct extent_buffer *eb;
1093 if (!path->nodes[level])
1096 node = path->nodes[level];
1097 search = btrfs_node_blockptr(node, slot);
1098 blocksize = btrfs_level_size(root, level - 1);
1099 eb = btrfs_find_tree_block(root, search, blocksize);
1101 free_extent_buffer(eb);
1105 highest_read = search;
1106 lowest_read = search;
1108 nritems = btrfs_header_nritems(node);
1111 if (direction < 0) {
1115 } else if (direction > 0) {
1120 if (path->reada < 0 && objectid) {
1121 btrfs_node_key(node, &disk_key, nr);
1122 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1125 search = btrfs_node_blockptr(node, nr);
1126 if ((search >= lowest_read && search <= highest_read) ||
1127 (search < lowest_read && lowest_read - search <= 32768) ||
1128 (search > highest_read && search - highest_read <= 32768)) {
1129 readahead_tree_block(root, search, blocksize,
1130 btrfs_node_ptr_generation(node, nr));
1134 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1136 if(nread > (1024 * 1024) || nscan > 128)
1139 if (search < lowest_read)
1140 lowest_read = search;
1141 if (search > highest_read)
1142 highest_read = search;
1147 * look for key in the tree. path is filled in with nodes along the way
1148 * if key is found, we return zero and you can find the item in the leaf
1149 * level of the path (level 0)
1151 * If the key isn't found, the path points to the slot where it should
1152 * be inserted, and 1 is returned. If there are other errors during the
1153 * search a negative error number is returned.
1155 * if ins_len > 0, nodes and leaves will be split as we walk down the
1156 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1159 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1160 *root, struct btrfs_key *key, struct btrfs_path *p, int
1163 struct extent_buffer *b;
1167 int should_reada = p->reada;
1168 u8 lowest_level = 0;
1170 lowest_level = p->lowest_level;
1171 WARN_ON(lowest_level && ins_len > 0);
1172 WARN_ON(p->nodes[0] != NULL);
1174 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1178 extent_buffer_get(b);
1180 level = btrfs_header_level(b);
1183 wret = btrfs_cow_block(trans, root, b,
1184 p->nodes[level + 1],
1185 p->slots[level + 1],
1188 free_extent_buffer(b);
1192 BUG_ON(!cow && ins_len);
1193 if (level != btrfs_header_level(b))
1195 level = btrfs_header_level(b);
1196 p->nodes[level] = b;
1197 ret = check_block(root, p, level);
1200 ret = bin_search(b, key, level, &slot);
1202 if (ret && slot > 0)
1204 p->slots[level] = slot;
1205 if ((p->search_for_split || ins_len > 0) &&
1206 btrfs_header_nritems(b) >=
1207 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1208 int sret = split_node(trans, root, p, level);
1212 b = p->nodes[level];
1213 slot = p->slots[level];
1214 } else if (ins_len < 0) {
1215 int sret = balance_level(trans, root, p,
1219 b = p->nodes[level];
1221 btrfs_release_path(NULL, p);
1224 slot = p->slots[level];
1225 BUG_ON(btrfs_header_nritems(b) == 1);
1227 /* this is only true while dropping a snapshot */
1228 if (level == lowest_level)
1232 reada_for_search(root, p, level, slot,
1235 b = read_node_slot(root, b, slot);
1236 if (!extent_buffer_uptodate(b))
1239 p->slots[level] = slot;
1241 ins_len > btrfs_leaf_free_space(root, b)) {
1242 int sret = split_leaf(trans, root, key,
1243 p, ins_len, ret == 0);
1255 * adjust the pointers going up the tree, starting at level
1256 * making sure the right key of each node is points to 'key'.
1257 * This is used after shifting pointers to the left, so it stops
1258 * fixing up pointers when a given leaf/node is not in slot 0 of the
1261 * If this fails to write a tree block, it returns -1, but continues
1262 * fixing up the blocks in ram so the tree is consistent.
1264 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1265 struct btrfs_root *root, struct btrfs_path *path,
1266 struct btrfs_disk_key *key, int level)
1270 struct extent_buffer *t;
1272 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1273 int tslot = path->slots[i];
1274 if (!path->nodes[i])
1277 btrfs_set_node_key(t, key, tslot);
1278 btrfs_mark_buffer_dirty(path->nodes[i]);
1288 * This function isn't completely safe. It's the caller's responsibility
1289 * that the new key won't break the order
1291 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1292 struct btrfs_root *root, struct btrfs_path *path,
1293 struct btrfs_key *new_key)
1295 struct btrfs_disk_key disk_key;
1296 struct extent_buffer *eb;
1299 eb = path->nodes[0];
1300 slot = path->slots[0];
1302 btrfs_item_key(eb, &disk_key, slot - 1);
1303 if (btrfs_comp_keys(&disk_key, new_key) >= 0)
1306 if (slot < btrfs_header_nritems(eb) - 1) {
1307 btrfs_item_key(eb, &disk_key, slot + 1);
1308 if (btrfs_comp_keys(&disk_key, new_key) <= 0)
1312 btrfs_cpu_key_to_disk(&disk_key, new_key);
1313 btrfs_set_item_key(eb, &disk_key, slot);
1314 btrfs_mark_buffer_dirty(eb);
1316 fixup_low_keys(trans, root, path, &disk_key, 1);
1321 * try to push data from one node into the next node left in the
1324 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1325 * error, and > 0 if there was no room in the left hand block.
1327 static int push_node_left(struct btrfs_trans_handle *trans,
1328 struct btrfs_root *root, struct extent_buffer *dst,
1329 struct extent_buffer *src, int empty)
1336 src_nritems = btrfs_header_nritems(src);
1337 dst_nritems = btrfs_header_nritems(dst);
1338 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1339 WARN_ON(btrfs_header_generation(src) != trans->transid);
1340 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1342 if (!empty && src_nritems <= 8)
1345 if (push_items <= 0) {
1350 push_items = min(src_nritems, push_items);
1351 if (push_items < src_nritems) {
1352 /* leave at least 8 pointers in the node if
1353 * we aren't going to empty it
1355 if (src_nritems - push_items < 8) {
1356 if (push_items <= 8)
1362 push_items = min(src_nritems - 8, push_items);
1364 copy_extent_buffer(dst, src,
1365 btrfs_node_key_ptr_offset(dst_nritems),
1366 btrfs_node_key_ptr_offset(0),
1367 push_items * sizeof(struct btrfs_key_ptr));
1369 if (push_items < src_nritems) {
1370 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1371 btrfs_node_key_ptr_offset(push_items),
1372 (src_nritems - push_items) *
1373 sizeof(struct btrfs_key_ptr));
1375 btrfs_set_header_nritems(src, src_nritems - push_items);
1376 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1377 btrfs_mark_buffer_dirty(src);
1378 btrfs_mark_buffer_dirty(dst);
1384 * try to push data from one node into the next node right in the
1387 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1388 * error, and > 0 if there was no room in the right hand block.
1390 * this will only push up to 1/2 the contents of the left node over
1392 static int balance_node_right(struct btrfs_trans_handle *trans,
1393 struct btrfs_root *root,
1394 struct extent_buffer *dst,
1395 struct extent_buffer *src)
1403 WARN_ON(btrfs_header_generation(src) != trans->transid);
1404 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1406 src_nritems = btrfs_header_nritems(src);
1407 dst_nritems = btrfs_header_nritems(dst);
1408 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1409 if (push_items <= 0) {
1413 if (src_nritems < 4) {
1417 max_push = src_nritems / 2 + 1;
1418 /* don't try to empty the node */
1419 if (max_push >= src_nritems) {
1423 if (max_push < push_items)
1424 push_items = max_push;
1426 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1427 btrfs_node_key_ptr_offset(0),
1429 sizeof(struct btrfs_key_ptr));
1431 copy_extent_buffer(dst, src,
1432 btrfs_node_key_ptr_offset(0),
1433 btrfs_node_key_ptr_offset(src_nritems - push_items),
1434 push_items * sizeof(struct btrfs_key_ptr));
1436 btrfs_set_header_nritems(src, src_nritems - push_items);
1437 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1439 btrfs_mark_buffer_dirty(src);
1440 btrfs_mark_buffer_dirty(dst);
1446 * helper function to insert a new root level in the tree.
1447 * A new node is allocated, and a single item is inserted to
1448 * point to the existing root
1450 * returns zero on success or < 0 on failure.
1452 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1453 struct btrfs_root *root,
1454 struct btrfs_path *path, int level)
1457 struct extent_buffer *lower;
1458 struct extent_buffer *c;
1459 struct extent_buffer *old;
1460 struct btrfs_disk_key lower_key;
1462 BUG_ON(path->nodes[level]);
1463 BUG_ON(path->nodes[level-1] != root->node);
1465 lower = path->nodes[level-1];
1467 btrfs_item_key(lower, &lower_key, 0);
1469 btrfs_node_key(lower, &lower_key, 0);
1471 c = btrfs_alloc_free_block(trans, root, root->nodesize,
1472 root->root_key.objectid, &lower_key,
1473 level, root->node->start, 0);
1478 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
1479 btrfs_set_header_nritems(c, 1);
1480 btrfs_set_header_level(c, level);
1481 btrfs_set_header_bytenr(c, c->start);
1482 btrfs_set_header_generation(c, trans->transid);
1483 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
1484 btrfs_set_header_owner(c, root->root_key.objectid);
1486 write_extent_buffer(c, root->fs_info->fsid,
1487 (unsigned long)btrfs_header_fsid(c),
1490 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1491 (unsigned long)btrfs_header_chunk_tree_uuid(c),
1494 btrfs_set_node_key(c, &lower_key, 0);
1495 btrfs_set_node_blockptr(c, 0, lower->start);
1496 lower_gen = btrfs_header_generation(lower);
1497 WARN_ON(lower_gen != trans->transid);
1499 btrfs_set_node_ptr_generation(c, 0, lower_gen);
1501 btrfs_mark_buffer_dirty(c);
1506 /* the super has an extra ref to root->node */
1507 free_extent_buffer(old);
1509 add_root_to_dirty_list(root);
1510 extent_buffer_get(c);
1511 path->nodes[level] = c;
1512 path->slots[level] = 0;
1517 * worker function to insert a single pointer in a node.
1518 * the node should have enough room for the pointer already
1520 * slot and level indicate where you want the key to go, and
1521 * blocknr is the block the key points to.
1523 * returns zero on success and < 0 on any error
1525 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1526 *root, struct btrfs_path *path, struct btrfs_disk_key
1527 *key, u64 bytenr, int slot, int level)
1529 struct extent_buffer *lower;
1532 BUG_ON(!path->nodes[level]);
1533 lower = path->nodes[level];
1534 nritems = btrfs_header_nritems(lower);
1537 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1539 if (slot != nritems) {
1540 memmove_extent_buffer(lower,
1541 btrfs_node_key_ptr_offset(slot + 1),
1542 btrfs_node_key_ptr_offset(slot),
1543 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1545 btrfs_set_node_key(lower, key, slot);
1546 btrfs_set_node_blockptr(lower, slot, bytenr);
1547 WARN_ON(trans->transid == 0);
1548 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1549 btrfs_set_header_nritems(lower, nritems + 1);
1550 btrfs_mark_buffer_dirty(lower);
1555 * split the node at the specified level in path in two.
1556 * The path is corrected to point to the appropriate node after the split
1558 * Before splitting this tries to make some room in the node by pushing
1559 * left and right, if either one works, it returns right away.
1561 * returns 0 on success and < 0 on failure
1563 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1564 *root, struct btrfs_path *path, int level)
1566 struct extent_buffer *c;
1567 struct extent_buffer *split;
1568 struct btrfs_disk_key disk_key;
1574 c = path->nodes[level];
1575 WARN_ON(btrfs_header_generation(c) != trans->transid);
1576 if (c == root->node) {
1577 /* trying to split the root, lets make a new one */
1578 ret = insert_new_root(trans, root, path, level + 1);
1582 ret = push_nodes_for_insert(trans, root, path, level);
1583 c = path->nodes[level];
1584 if (!ret && btrfs_header_nritems(c) <
1585 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
1591 c_nritems = btrfs_header_nritems(c);
1592 mid = (c_nritems + 1) / 2;
1593 btrfs_node_key(c, &disk_key, mid);
1595 split = btrfs_alloc_free_block(trans, root, root->nodesize,
1596 root->root_key.objectid,
1597 &disk_key, level, c->start, 0);
1599 return PTR_ERR(split);
1601 memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
1602 btrfs_set_header_level(split, btrfs_header_level(c));
1603 btrfs_set_header_bytenr(split, split->start);
1604 btrfs_set_header_generation(split, trans->transid);
1605 btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
1606 btrfs_set_header_owner(split, root->root_key.objectid);
1607 write_extent_buffer(split, root->fs_info->fsid,
1608 (unsigned long)btrfs_header_fsid(split),
1610 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
1611 (unsigned long)btrfs_header_chunk_tree_uuid(split),
1615 copy_extent_buffer(split, c,
1616 btrfs_node_key_ptr_offset(0),
1617 btrfs_node_key_ptr_offset(mid),
1618 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1619 btrfs_set_header_nritems(split, c_nritems - mid);
1620 btrfs_set_header_nritems(c, mid);
1623 btrfs_mark_buffer_dirty(c);
1624 btrfs_mark_buffer_dirty(split);
1626 wret = insert_ptr(trans, root, path, &disk_key, split->start,
1627 path->slots[level + 1] + 1,
1632 if (path->slots[level] >= mid) {
1633 path->slots[level] -= mid;
1634 free_extent_buffer(c);
1635 path->nodes[level] = split;
1636 path->slots[level + 1] += 1;
1638 free_extent_buffer(split);
1644 * how many bytes are required to store the items in a leaf. start
1645 * and nr indicate which items in the leaf to check. This totals up the
1646 * space used both by the item structs and the item data
1648 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1651 int nritems = btrfs_header_nritems(l);
1652 int end = min(nritems, start + nr) - 1;
1656 data_len = btrfs_item_end_nr(l, start);
1657 data_len = data_len - btrfs_item_offset_nr(l, end);
1658 data_len += sizeof(struct btrfs_item) * nr;
1659 WARN_ON(data_len < 0);
1664 * The space between the end of the leaf items and
1665 * the start of the leaf data. IOW, how much room
1666 * the leaf has left for both items and data
1668 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1670 int nritems = btrfs_header_nritems(leaf);
1672 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1674 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1675 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1676 leaf_space_used(leaf, 0, nritems), nritems);
1682 * push some data in the path leaf to the right, trying to free up at
1683 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1685 * returns 1 if the push failed because the other node didn't have enough
1686 * room, 0 if everything worked out and < 0 if there were major errors.
1688 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1689 *root, struct btrfs_path *path, int data_size,
1692 struct extent_buffer *left = path->nodes[0];
1693 struct extent_buffer *right;
1694 struct extent_buffer *upper;
1695 struct btrfs_disk_key disk_key;
1701 struct btrfs_item *item;
1709 slot = path->slots[1];
1710 if (!path->nodes[1]) {
1713 upper = path->nodes[1];
1714 if (slot >= btrfs_header_nritems(upper) - 1)
1717 right = read_node_slot(root, upper, slot + 1);
1718 free_space = btrfs_leaf_free_space(root, right);
1719 if (free_space < data_size) {
1720 free_extent_buffer(right);
1724 /* cow and double check */
1725 ret = btrfs_cow_block(trans, root, right, upper,
1728 free_extent_buffer(right);
1731 free_space = btrfs_leaf_free_space(root, right);
1732 if (free_space < data_size) {
1733 free_extent_buffer(right);
1737 left_nritems = btrfs_header_nritems(left);
1738 if (left_nritems == 0) {
1739 free_extent_buffer(right);
1748 i = left_nritems - 1;
1750 item = btrfs_item_nr(left, i);
1752 if (path->slots[0] == i)
1753 push_space += data_size + sizeof(*item);
1755 this_item_size = btrfs_item_size(left, item);
1756 if (this_item_size + sizeof(*item) + push_space > free_space)
1759 push_space += this_item_size + sizeof(*item);
1765 if (push_items == 0) {
1766 free_extent_buffer(right);
1770 if (!empty && push_items == left_nritems)
1773 /* push left to right */
1774 right_nritems = btrfs_header_nritems(right);
1776 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1777 push_space -= leaf_data_end(root, left);
1779 /* make room in the right data area */
1780 data_end = leaf_data_end(root, right);
1781 memmove_extent_buffer(right,
1782 btrfs_leaf_data(right) + data_end - push_space,
1783 btrfs_leaf_data(right) + data_end,
1784 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1786 /* copy from the left data area */
1787 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1788 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1789 btrfs_leaf_data(left) + leaf_data_end(root, left),
1792 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1793 btrfs_item_nr_offset(0),
1794 right_nritems * sizeof(struct btrfs_item));
1796 /* copy the items from left to right */
1797 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1798 btrfs_item_nr_offset(left_nritems - push_items),
1799 push_items * sizeof(struct btrfs_item));
1801 /* update the item pointers */
1802 right_nritems += push_items;
1803 btrfs_set_header_nritems(right, right_nritems);
1804 push_space = BTRFS_LEAF_DATA_SIZE(root);
1805 for (i = 0; i < right_nritems; i++) {
1806 item = btrfs_item_nr(right, i);
1807 push_space -= btrfs_item_size(right, item);
1808 btrfs_set_item_offset(right, item, push_space);
1811 left_nritems -= push_items;
1812 btrfs_set_header_nritems(left, left_nritems);
1815 btrfs_mark_buffer_dirty(left);
1816 btrfs_mark_buffer_dirty(right);
1818 btrfs_item_key(right, &disk_key, 0);
1819 btrfs_set_node_key(upper, &disk_key, slot + 1);
1820 btrfs_mark_buffer_dirty(upper);
1822 /* then fixup the leaf pointer in the path */
1823 if (path->slots[0] >= left_nritems) {
1824 path->slots[0] -= left_nritems;
1825 free_extent_buffer(path->nodes[0]);
1826 path->nodes[0] = right;
1827 path->slots[1] += 1;
1829 free_extent_buffer(right);
1834 * push some data in the path leaf to the left, trying to free up at
1835 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1837 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1838 *root, struct btrfs_path *path, int data_size,
1841 struct btrfs_disk_key disk_key;
1842 struct extent_buffer *right = path->nodes[0];
1843 struct extent_buffer *left;
1849 struct btrfs_item *item;
1850 u32 old_left_nritems;
1856 u32 old_left_item_size;
1858 slot = path->slots[1];
1861 if (!path->nodes[1])
1864 right_nritems = btrfs_header_nritems(right);
1865 if (right_nritems == 0) {
1869 left = read_node_slot(root, path->nodes[1], slot - 1);
1870 free_space = btrfs_leaf_free_space(root, left);
1871 if (free_space < data_size) {
1872 free_extent_buffer(left);
1876 /* cow and double check */
1877 ret = btrfs_cow_block(trans, root, left,
1878 path->nodes[1], slot - 1, &left);
1880 /* we hit -ENOSPC, but it isn't fatal here */
1881 free_extent_buffer(left);
1885 free_space = btrfs_leaf_free_space(root, left);
1886 if (free_space < data_size) {
1887 free_extent_buffer(left);
1894 nr = right_nritems - 1;
1896 for (i = 0; i < nr; i++) {
1897 item = btrfs_item_nr(right, i);
1899 if (path->slots[0] == i)
1900 push_space += data_size + sizeof(*item);
1902 this_item_size = btrfs_item_size(right, item);
1903 if (this_item_size + sizeof(*item) + push_space > free_space)
1907 push_space += this_item_size + sizeof(*item);
1910 if (push_items == 0) {
1911 free_extent_buffer(left);
1914 if (!empty && push_items == btrfs_header_nritems(right))
1917 /* push data from right to left */
1918 copy_extent_buffer(left, right,
1919 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1920 btrfs_item_nr_offset(0),
1921 push_items * sizeof(struct btrfs_item));
1923 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1924 btrfs_item_offset_nr(right, push_items -1);
1926 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1927 leaf_data_end(root, left) - push_space,
1928 btrfs_leaf_data(right) +
1929 btrfs_item_offset_nr(right, push_items - 1),
1931 old_left_nritems = btrfs_header_nritems(left);
1932 BUG_ON(old_left_nritems == 0);
1934 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1935 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1938 item = btrfs_item_nr(left, i);
1939 ioff = btrfs_item_offset(left, item);
1940 btrfs_set_item_offset(left, item,
1941 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1943 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1945 /* fixup right node */
1946 if (push_items > right_nritems) {
1947 printk("push items %d nr %u\n", push_items, right_nritems);
1951 if (push_items < right_nritems) {
1952 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1953 leaf_data_end(root, right);
1954 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1955 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1956 btrfs_leaf_data(right) +
1957 leaf_data_end(root, right), push_space);
1959 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1960 btrfs_item_nr_offset(push_items),
1961 (btrfs_header_nritems(right) - push_items) *
1962 sizeof(struct btrfs_item));
1964 right_nritems -= push_items;
1965 btrfs_set_header_nritems(right, right_nritems);
1966 push_space = BTRFS_LEAF_DATA_SIZE(root);
1967 for (i = 0; i < right_nritems; i++) {
1968 item = btrfs_item_nr(right, i);
1969 push_space = push_space - btrfs_item_size(right, item);
1970 btrfs_set_item_offset(right, item, push_space);
1973 btrfs_mark_buffer_dirty(left);
1975 btrfs_mark_buffer_dirty(right);
1977 btrfs_item_key(right, &disk_key, 0);
1978 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1982 /* then fixup the leaf pointer in the path */
1983 if (path->slots[0] < push_items) {
1984 path->slots[0] += old_left_nritems;
1985 free_extent_buffer(path->nodes[0]);
1986 path->nodes[0] = left;
1987 path->slots[1] -= 1;
1989 free_extent_buffer(left);
1990 path->slots[0] -= push_items;
1992 BUG_ON(path->slots[0] < 0);
1997 * split the path's leaf in two, making sure there is at least data_size
1998 * available for the resulting leaf level of the path.
2000 * returns 0 if all went well and < 0 on failure.
2002 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2003 struct btrfs_root *root,
2004 struct btrfs_path *path,
2005 struct extent_buffer *l,
2006 struct extent_buffer *right,
2007 int slot, int mid, int nritems)
2014 struct btrfs_disk_key disk_key;
2016 nritems = nritems - mid;
2017 btrfs_set_header_nritems(right, nritems);
2018 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2020 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2021 btrfs_item_nr_offset(mid),
2022 nritems * sizeof(struct btrfs_item));
2024 copy_extent_buffer(right, l,
2025 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2026 data_copy_size, btrfs_leaf_data(l) +
2027 leaf_data_end(root, l), data_copy_size);
2029 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2030 btrfs_item_end_nr(l, mid);
2032 for (i = 0; i < nritems; i++) {
2033 struct btrfs_item *item = btrfs_item_nr(right, i);
2034 u32 ioff = btrfs_item_offset(right, item);
2035 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2038 btrfs_set_header_nritems(l, mid);
2040 btrfs_item_key(right, &disk_key, 0);
2041 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2042 path->slots[1] + 1, 1);
2046 btrfs_mark_buffer_dirty(right);
2047 btrfs_mark_buffer_dirty(l);
2048 BUG_ON(path->slots[0] != slot);
2051 free_extent_buffer(path->nodes[0]);
2052 path->nodes[0] = right;
2053 path->slots[0] -= mid;
2054 path->slots[1] += 1;
2056 free_extent_buffer(right);
2059 BUG_ON(path->slots[0] < 0);
2065 * split the path's leaf in two, making sure there is at least data_size
2066 * available for the resulting leaf level of the path.
2068 * returns 0 if all went well and < 0 on failure.
2070 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2071 struct btrfs_root *root,
2072 struct btrfs_key *ins_key,
2073 struct btrfs_path *path, int data_size,
2076 struct btrfs_disk_key disk_key;
2077 struct extent_buffer *l;
2081 struct extent_buffer *right;
2085 int num_doubles = 0;
2087 /* first try to make some room by pushing left and right */
2088 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2089 wret = push_leaf_right(trans, root, path, data_size, 0);
2093 wret = push_leaf_left(trans, root, path, data_size, 0);
2099 /* did the pushes work? */
2100 if (btrfs_leaf_free_space(root, l) >= data_size)
2104 if (!path->nodes[1]) {
2105 ret = insert_new_root(trans, root, path, 1);
2112 slot = path->slots[0];
2113 nritems = btrfs_header_nritems(l);
2114 mid = (nritems + 1) / 2;
2118 leaf_space_used(l, mid, nritems - mid) + data_size >
2119 BTRFS_LEAF_DATA_SIZE(root)) {
2120 if (slot >= nritems) {
2124 if (mid != nritems &&
2125 leaf_space_used(l, mid, nritems - mid) +
2126 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2132 if (leaf_space_used(l, 0, mid) + data_size >
2133 BTRFS_LEAF_DATA_SIZE(root)) {
2134 if (!extend && data_size && slot == 0) {
2136 } else if ((extend || !data_size) && slot == 0) {
2140 if (mid != nritems &&
2141 leaf_space_used(l, mid, nritems - mid) +
2142 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2150 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2152 btrfs_item_key(l, &disk_key, mid);
2154 right = btrfs_alloc_free_block(trans, root, root->leafsize,
2155 root->root_key.objectid,
2156 &disk_key, 0, l->start, 0);
2157 if (IS_ERR(right)) {
2159 return PTR_ERR(right);
2162 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2163 btrfs_set_header_bytenr(right, right->start);
2164 btrfs_set_header_generation(right, trans->transid);
2165 btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
2166 btrfs_set_header_owner(right, root->root_key.objectid);
2167 btrfs_set_header_level(right, 0);
2168 write_extent_buffer(right, root->fs_info->fsid,
2169 (unsigned long)btrfs_header_fsid(right),
2172 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2173 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2178 btrfs_set_header_nritems(right, 0);
2179 wret = insert_ptr(trans, root, path,
2180 &disk_key, right->start,
2181 path->slots[1] + 1, 1);
2185 free_extent_buffer(path->nodes[0]);
2186 path->nodes[0] = right;
2188 path->slots[1] += 1;
2190 btrfs_set_header_nritems(right, 0);
2191 wret = insert_ptr(trans, root, path,
2197 free_extent_buffer(path->nodes[0]);
2198 path->nodes[0] = right;
2200 if (path->slots[1] == 0) {
2201 wret = fixup_low_keys(trans, root,
2202 path, &disk_key, 1);
2207 btrfs_mark_buffer_dirty(right);
2211 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2215 BUG_ON(num_doubles != 0);
2224 * This function splits a single item into two items,
2225 * giving 'new_key' to the new item and splitting the
2226 * old one at split_offset (from the start of the item).
2228 * The path may be released by this operation. After
2229 * the split, the path is pointing to the old item. The
2230 * new item is going to be in the same node as the old one.
2232 * Note, the item being split must be smaller enough to live alone on
2233 * a tree block with room for one extra struct btrfs_item
2235 * This allows us to split the item in place, keeping a lock on the
2236 * leaf the entire time.
2238 int btrfs_split_item(struct btrfs_trans_handle *trans,
2239 struct btrfs_root *root,
2240 struct btrfs_path *path,
2241 struct btrfs_key *new_key,
2242 unsigned long split_offset)
2245 struct extent_buffer *leaf;
2246 struct btrfs_key orig_key;
2247 struct btrfs_item *item;
2248 struct btrfs_item *new_item;
2253 struct btrfs_disk_key disk_key;
2256 leaf = path->nodes[0];
2257 btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
2258 if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
2261 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2262 btrfs_release_path(root, path);
2264 path->search_for_split = 1;
2266 ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
2267 path->search_for_split = 0;
2269 /* if our item isn't there or got smaller, return now */
2270 if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
2275 ret = split_leaf(trans, root, &orig_key, path, 0, 0);
2278 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
2279 leaf = path->nodes[0];
2282 item = btrfs_item_nr(leaf, path->slots[0]);
2283 orig_offset = btrfs_item_offset(leaf, item);
2284 item_size = btrfs_item_size(leaf, item);
2287 buf = kmalloc(item_size, GFP_NOFS);
2288 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
2289 path->slots[0]), item_size);
2290 slot = path->slots[0] + 1;
2291 leaf = path->nodes[0];
2293 nritems = btrfs_header_nritems(leaf);
2295 if (slot != nritems) {
2296 /* shift the items */
2297 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2298 btrfs_item_nr_offset(slot),
2299 (nritems - slot) * sizeof(struct btrfs_item));
2303 btrfs_cpu_key_to_disk(&disk_key, new_key);
2304 btrfs_set_item_key(leaf, &disk_key, slot);
2306 new_item = btrfs_item_nr(leaf, slot);
2308 btrfs_set_item_offset(leaf, new_item, orig_offset);
2309 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
2311 btrfs_set_item_offset(leaf, item,
2312 orig_offset + item_size - split_offset);
2313 btrfs_set_item_size(leaf, item, split_offset);
2315 btrfs_set_header_nritems(leaf, nritems + 1);
2317 /* write the data for the start of the original item */
2318 write_extent_buffer(leaf, buf,
2319 btrfs_item_ptr_offset(leaf, path->slots[0]),
2322 /* write the data for the new item */
2323 write_extent_buffer(leaf, buf + split_offset,
2324 btrfs_item_ptr_offset(leaf, slot),
2325 item_size - split_offset);
2326 btrfs_mark_buffer_dirty(leaf);
2329 if (btrfs_leaf_free_space(root, leaf) < 0) {
2330 btrfs_print_leaf(root, leaf);
2337 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2338 struct btrfs_root *root,
2339 struct btrfs_path *path,
2340 u32 new_size, int from_end)
2344 struct extent_buffer *leaf;
2345 struct btrfs_item *item;
2347 unsigned int data_end;
2348 unsigned int old_data_start;
2349 unsigned int old_size;
2350 unsigned int size_diff;
2353 leaf = path->nodes[0];
2354 slot = path->slots[0];
2356 old_size = btrfs_item_size_nr(leaf, slot);
2357 if (old_size == new_size)
2360 nritems = btrfs_header_nritems(leaf);
2361 data_end = leaf_data_end(root, leaf);
2363 old_data_start = btrfs_item_offset_nr(leaf, slot);
2365 size_diff = old_size - new_size;
2368 BUG_ON(slot >= nritems);
2371 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2373 /* first correct the data pointers */
2374 for (i = slot; i < nritems; i++) {
2376 item = btrfs_item_nr(leaf, i);
2377 ioff = btrfs_item_offset(leaf, item);
2378 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2381 /* shift the data */
2383 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2384 data_end + size_diff, btrfs_leaf_data(leaf) +
2385 data_end, old_data_start + new_size - data_end);
2387 struct btrfs_disk_key disk_key;
2390 btrfs_item_key(leaf, &disk_key, slot);
2392 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2394 struct btrfs_file_extent_item *fi;
2396 fi = btrfs_item_ptr(leaf, slot,
2397 struct btrfs_file_extent_item);
2398 fi = (struct btrfs_file_extent_item *)(
2399 (unsigned long)fi - size_diff);
2401 if (btrfs_file_extent_type(leaf, fi) ==
2402 BTRFS_FILE_EXTENT_INLINE) {
2403 ptr = btrfs_item_ptr_offset(leaf, slot);
2404 memmove_extent_buffer(leaf, ptr,
2406 offsetof(struct btrfs_file_extent_item,
2411 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2412 data_end + size_diff, btrfs_leaf_data(leaf) +
2413 data_end, old_data_start - data_end);
2415 offset = btrfs_disk_key_offset(&disk_key);
2416 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2417 btrfs_set_item_key(leaf, &disk_key, slot);
2419 fixup_low_keys(trans, root, path, &disk_key, 1);
2422 item = btrfs_item_nr(leaf, slot);
2423 btrfs_set_item_size(leaf, item, new_size);
2424 btrfs_mark_buffer_dirty(leaf);
2427 if (btrfs_leaf_free_space(root, leaf) < 0) {
2428 btrfs_print_leaf(root, leaf);
2434 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2435 struct btrfs_root *root, struct btrfs_path *path,
2440 struct extent_buffer *leaf;
2441 struct btrfs_item *item;
2443 unsigned int data_end;
2444 unsigned int old_data;
2445 unsigned int old_size;
2448 leaf = path->nodes[0];
2450 nritems = btrfs_header_nritems(leaf);
2451 data_end = leaf_data_end(root, leaf);
2453 if (btrfs_leaf_free_space(root, leaf) < data_size) {
2454 btrfs_print_leaf(root, leaf);
2457 slot = path->slots[0];
2458 old_data = btrfs_item_end_nr(leaf, slot);
2461 if (slot >= nritems) {
2462 btrfs_print_leaf(root, leaf);
2463 printk("slot %d too large, nritems %d\n", slot, nritems);
2468 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2470 /* first correct the data pointers */
2471 for (i = slot; i < nritems; i++) {
2473 item = btrfs_item_nr(leaf, i);
2474 ioff = btrfs_item_offset(leaf, item);
2475 btrfs_set_item_offset(leaf, item, ioff - data_size);
2478 /* shift the data */
2479 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2480 data_end - data_size, btrfs_leaf_data(leaf) +
2481 data_end, old_data - data_end);
2483 data_end = old_data;
2484 old_size = btrfs_item_size_nr(leaf, slot);
2485 item = btrfs_item_nr(leaf, slot);
2486 btrfs_set_item_size(leaf, item, old_size + data_size);
2487 btrfs_mark_buffer_dirty(leaf);
2490 if (btrfs_leaf_free_space(root, leaf) < 0) {
2491 btrfs_print_leaf(root, leaf);
2498 * Given a key and some data, insert an item into the tree.
2499 * This does all the path init required, making room in the tree if needed.
2501 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2502 struct btrfs_root *root,
2503 struct btrfs_path *path,
2504 struct btrfs_key *cpu_key, u32 *data_size,
2507 struct extent_buffer *leaf;
2508 struct btrfs_item *item;
2515 unsigned int data_end;
2516 struct btrfs_disk_key disk_key;
2518 for (i = 0; i < nr; i++) {
2519 total_data += data_size[i];
2522 /* create a root if there isn't one */
2526 total_size = total_data + nr * sizeof(struct btrfs_item);
2527 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2534 leaf = path->nodes[0];
2536 nritems = btrfs_header_nritems(leaf);
2537 data_end = leaf_data_end(root, leaf);
2539 if (btrfs_leaf_free_space(root, leaf) < total_size) {
2540 btrfs_print_leaf(root, leaf);
2541 printk("not enough freespace need %u have %d\n",
2542 total_size, btrfs_leaf_free_space(root, leaf));
2546 slot = path->slots[0];
2549 if (slot != nritems) {
2551 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2553 if (old_data < data_end) {
2554 btrfs_print_leaf(root, leaf);
2555 printk("slot %d old_data %d data_end %d\n",
2556 slot, old_data, data_end);
2560 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2562 /* first correct the data pointers */
2563 for (i = slot; i < nritems; i++) {
2566 item = btrfs_item_nr(leaf, i);
2567 ioff = btrfs_item_offset(leaf, item);
2568 btrfs_set_item_offset(leaf, item, ioff - total_data);
2571 /* shift the items */
2572 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2573 btrfs_item_nr_offset(slot),
2574 (nritems - slot) * sizeof(struct btrfs_item));
2576 /* shift the data */
2577 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2578 data_end - total_data, btrfs_leaf_data(leaf) +
2579 data_end, old_data - data_end);
2580 data_end = old_data;
2583 /* setup the item for the new data */
2584 for (i = 0; i < nr; i++) {
2585 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2586 btrfs_set_item_key(leaf, &disk_key, slot + i);
2587 item = btrfs_item_nr(leaf, slot + i);
2588 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2589 data_end -= data_size[i];
2590 btrfs_set_item_size(leaf, item, data_size[i]);
2592 btrfs_set_header_nritems(leaf, nritems + nr);
2593 btrfs_mark_buffer_dirty(leaf);
2597 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2598 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2601 if (btrfs_leaf_free_space(root, leaf) < 0) {
2602 btrfs_print_leaf(root, leaf);
2611 * Given a key and some data, insert an item into the tree.
2612 * This does all the path init required, making room in the tree if needed.
2614 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2615 *root, struct btrfs_key *cpu_key, void *data, u32
2619 struct btrfs_path *path;
2620 struct extent_buffer *leaf;
2623 path = btrfs_alloc_path();
2625 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2627 leaf = path->nodes[0];
2628 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2629 write_extent_buffer(leaf, data, ptr, data_size);
2630 btrfs_mark_buffer_dirty(leaf);
2632 btrfs_free_path(path);
2637 * delete the pointer from a given node.
2639 * If the delete empties a node, the node is removed from the tree,
2640 * continuing all the way the root if required. The root is converted into
2641 * a leaf if all the nodes are emptied.
2643 int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2644 struct btrfs_path *path, int level, int slot)
2646 struct extent_buffer *parent = path->nodes[level];
2651 nritems = btrfs_header_nritems(parent);
2652 if (slot != nritems -1) {
2653 memmove_extent_buffer(parent,
2654 btrfs_node_key_ptr_offset(slot),
2655 btrfs_node_key_ptr_offset(slot + 1),
2656 sizeof(struct btrfs_key_ptr) *
2657 (nritems - slot - 1));
2660 btrfs_set_header_nritems(parent, nritems);
2661 if (nritems == 0 && parent == root->node) {
2662 BUG_ON(btrfs_header_level(root->node) != 1);
2663 /* just turn the root into a leaf and break */
2664 btrfs_set_header_level(root->node, 0);
2665 } else if (slot == 0) {
2666 struct btrfs_disk_key disk_key;
2668 btrfs_node_key(parent, &disk_key, 0);
2669 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2673 btrfs_mark_buffer_dirty(parent);
2678 * a helper function to delete the leaf pointed to by path->slots[1] and
2681 * This deletes the pointer in path->nodes[1] and frees the leaf
2682 * block extent. zero is returned if it all worked out, < 0 otherwise.
2684 * The path must have already been setup for deleting the leaf, including
2685 * all the proper balancing. path->nodes[1] must be locked.
2687 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
2688 struct btrfs_root *root,
2689 struct btrfs_path *path,
2690 struct extent_buffer *leaf)
2694 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
2695 ret = btrfs_del_ptr(trans, root, path, 1, path->slots[1]);
2699 ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
2700 0, root->root_key.objectid, 0, 0);
2705 * delete the item at the leaf level in path. If that empties
2706 * the leaf, remove it from the tree
2708 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2709 struct btrfs_path *path, int slot, int nr)
2711 struct extent_buffer *leaf;
2712 struct btrfs_item *item;
2720 leaf = path->nodes[0];
2721 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2723 for (i = 0; i < nr; i++)
2724 dsize += btrfs_item_size_nr(leaf, slot + i);
2726 nritems = btrfs_header_nritems(leaf);
2728 if (slot + nr != nritems) {
2730 int data_end = leaf_data_end(root, leaf);
2732 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2734 btrfs_leaf_data(leaf) + data_end,
2735 last_off - data_end);
2737 for (i = slot + nr; i < nritems; i++) {
2740 item = btrfs_item_nr(leaf, i);
2741 ioff = btrfs_item_offset(leaf, item);
2742 btrfs_set_item_offset(leaf, item, ioff + dsize);
2745 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2746 btrfs_item_nr_offset(slot + nr),
2747 sizeof(struct btrfs_item) *
2748 (nritems - slot - nr));
2750 btrfs_set_header_nritems(leaf, nritems - nr);
2753 /* delete the leaf if we've emptied it */
2755 if (leaf == root->node) {
2756 btrfs_set_header_level(leaf, 0);
2758 clean_tree_block(trans, root, leaf);
2759 wait_on_tree_block_writeback(root, leaf);
2761 wret = btrfs_del_leaf(trans, root, path, leaf);
2767 int used = leaf_space_used(leaf, 0, nritems);
2769 struct btrfs_disk_key disk_key;
2771 btrfs_item_key(leaf, &disk_key, 0);
2772 wret = fixup_low_keys(trans, root, path,
2778 /* delete the leaf if it is mostly empty */
2779 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2780 /* push_leaf_left fixes the path.
2781 * make sure the path still points to our leaf
2782 * for possible call to del_ptr below
2784 slot = path->slots[1];
2785 extent_buffer_get(leaf);
2787 wret = push_leaf_left(trans, root, path, 1, 1);
2788 if (wret < 0 && wret != -ENOSPC)
2791 if (path->nodes[0] == leaf &&
2792 btrfs_header_nritems(leaf)) {
2793 wret = push_leaf_right(trans, root, path, 1, 1);
2794 if (wret < 0 && wret != -ENOSPC)
2798 if (btrfs_header_nritems(leaf) == 0) {
2799 clean_tree_block(trans, root, leaf);
2800 wait_on_tree_block_writeback(root, leaf);
2802 path->slots[1] = slot;
2803 ret = btrfs_del_leaf(trans, root, path, leaf);
2805 free_extent_buffer(leaf);
2808 btrfs_mark_buffer_dirty(leaf);
2809 free_extent_buffer(leaf);
2812 btrfs_mark_buffer_dirty(leaf);
2819 * walk up the tree as far as required to find the previous leaf.
2820 * returns 0 if it found something or 1 if there are no lesser leaves.
2821 * returns < 0 on io errors.
2823 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2827 struct extent_buffer *c;
2828 struct extent_buffer *next = NULL;
2830 while(level < BTRFS_MAX_LEVEL) {
2831 if (!path->nodes[level])
2834 slot = path->slots[level];
2835 c = path->nodes[level];
2838 if (level == BTRFS_MAX_LEVEL)
2844 next = read_node_slot(root, c, slot);
2847 path->slots[level] = slot;
2850 c = path->nodes[level];
2851 free_extent_buffer(c);
2852 slot = btrfs_header_nritems(next);
2855 path->nodes[level] = next;
2856 path->slots[level] = slot;
2859 next = read_node_slot(root, next, slot);
2865 * walk up the tree as far as required to find the next leaf.
2866 * returns 0 if it found something or 1 if there are no greater leaves.
2867 * returns < 0 on io errors.
2869 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2873 struct extent_buffer *c;
2874 struct extent_buffer *next = NULL;
2876 while(level < BTRFS_MAX_LEVEL) {
2877 if (!path->nodes[level])
2880 slot = path->slots[level] + 1;
2881 c = path->nodes[level];
2882 if (slot >= btrfs_header_nritems(c)) {
2884 if (level == BTRFS_MAX_LEVEL)
2890 reada_for_search(root, path, level, slot, 0);
2892 next = read_node_slot(root, c, slot);
2897 path->slots[level] = slot;
2900 c = path->nodes[level];
2901 free_extent_buffer(c);
2902 path->nodes[level] = next;
2903 path->slots[level] = 0;
2907 reada_for_search(root, path, level, 0, 0);
2908 next = read_node_slot(root, next, 0);
2915 int btrfs_previous_item(struct btrfs_root *root,
2916 struct btrfs_path *path, u64 min_objectid,
2919 struct btrfs_key found_key;
2920 struct extent_buffer *leaf;
2924 if (path->slots[0] == 0) {
2925 ret = btrfs_prev_leaf(root, path);
2931 leaf = path->nodes[0];
2932 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2933 if (found_key.type == type)