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.
19 #include <linux/sched.h>
22 #include "transaction.h"
23 #include "print-tree.h"
25 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
26 *root, struct btrfs_path *path, int level);
27 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
28 *root, struct btrfs_key *ins_key,
29 struct btrfs_path *path, int data_size, int extend);
30 static int push_node_left(struct btrfs_trans_handle *trans,
31 struct btrfs_root *root, struct extent_buffer *dst,
32 struct extent_buffer *src);
33 static int balance_node_right(struct btrfs_trans_handle *trans,
34 struct btrfs_root *root,
35 struct extent_buffer *dst_buf,
36 struct extent_buffer *src_buf);
37 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
38 struct btrfs_path *path, int level, int slot);
40 inline void btrfs_init_path(struct btrfs_path *p)
42 memset(p, 0, sizeof(*p));
45 struct btrfs_path *btrfs_alloc_path(void)
47 struct btrfs_path *path;
48 path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
50 btrfs_init_path(path);
56 void btrfs_free_path(struct btrfs_path *p)
58 btrfs_release_path(NULL, p);
59 kmem_cache_free(btrfs_path_cachep, p);
62 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
65 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
68 free_extent_buffer(p->nodes[i]);
70 memset(p, 0, sizeof(*p));
73 static void add_root_to_dirty_list(struct btrfs_root *root)
75 if (root->track_dirty && list_empty(&root->dirty_list)) {
76 list_add(&root->dirty_list,
77 &root->fs_info->dirty_cowonly_roots);
81 int btrfs_copy_root(struct btrfs_trans_handle *trans,
82 struct btrfs_root *root,
83 struct extent_buffer *buf,
84 struct extent_buffer **cow_ret, u64 new_root_objectid)
86 struct extent_buffer *cow;
90 struct btrfs_key first_key;
91 struct btrfs_root *new_root;
93 new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
97 memcpy(new_root, root, sizeof(*new_root));
98 new_root->root_key.objectid = new_root_objectid;
100 WARN_ON(root->ref_cows && trans->transid !=
101 root->fs_info->running_transaction->transid);
102 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
104 level = btrfs_header_level(buf);
105 nritems = btrfs_header_nritems(buf);
108 btrfs_item_key_to_cpu(buf, &first_key, 0);
110 btrfs_node_key_to_cpu(buf, &first_key, 0);
112 first_key.objectid = 0;
114 cow = __btrfs_alloc_free_block(trans, new_root, buf->len,
116 trans->transid, first_key.objectid,
117 level, buf->start, 0);
123 copy_extent_buffer(cow, buf, 0, 0, cow->len);
124 btrfs_set_header_bytenr(cow, cow->start);
125 btrfs_set_header_generation(cow, trans->transid);
126 btrfs_set_header_owner(cow, new_root_objectid);
128 WARN_ON(btrfs_header_generation(buf) > trans->transid);
129 ret = btrfs_inc_ref(trans, new_root, buf);
135 btrfs_mark_buffer_dirty(cow);
140 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
141 struct btrfs_root *root,
142 struct extent_buffer *buf,
143 struct extent_buffer *parent, int parent_slot,
144 struct extent_buffer **cow_ret,
145 u64 search_start, u64 empty_size)
148 struct extent_buffer *cow;
151 int different_trans = 0;
153 struct btrfs_key first_key;
155 if (root->ref_cows) {
156 root_gen = trans->transid;
161 WARN_ON(root->ref_cows && trans->transid !=
162 root->fs_info->running_transaction->transid);
163 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
165 level = btrfs_header_level(buf);
166 nritems = btrfs_header_nritems(buf);
169 btrfs_item_key_to_cpu(buf, &first_key, 0);
171 btrfs_node_key_to_cpu(buf, &first_key, 0);
173 first_key.objectid = 0;
175 cow = __btrfs_alloc_free_block(trans, root, buf->len,
176 root->root_key.objectid,
177 root_gen, first_key.objectid, level,
178 search_start, empty_size);
182 copy_extent_buffer(cow, buf, 0, 0, cow->len);
183 btrfs_set_header_bytenr(cow, cow->start);
184 btrfs_set_header_generation(cow, trans->transid);
185 btrfs_set_header_owner(cow, root->root_key.objectid);
187 WARN_ON(btrfs_header_generation(buf) > trans->transid);
188 if (btrfs_header_generation(buf) != trans->transid) {
190 ret = btrfs_inc_ref(trans, root, buf);
194 clean_tree_block(trans, root, buf);
197 if (buf == root->node) {
198 root_gen = btrfs_header_generation(buf);
200 extent_buffer_get(cow);
201 if (buf != root->commit_root) {
202 btrfs_free_extent(trans, root, buf->start,
203 buf->len, root->root_key.objectid,
206 free_extent_buffer(buf);
207 add_root_to_dirty_list(root);
209 root_gen = btrfs_header_generation(parent);
210 btrfs_set_node_blockptr(parent, parent_slot,
212 WARN_ON(trans->transid == 0);
213 btrfs_set_node_ptr_generation(parent, parent_slot,
215 btrfs_mark_buffer_dirty(parent);
216 WARN_ON(btrfs_header_generation(parent) != trans->transid);
217 btrfs_free_extent(trans, root, buf->start, buf->len,
218 btrfs_header_owner(parent), root_gen,
221 free_extent_buffer(buf);
222 btrfs_mark_buffer_dirty(cow);
227 int btrfs_cow_block(struct btrfs_trans_handle *trans,
228 struct btrfs_root *root, struct extent_buffer *buf,
229 struct extent_buffer *parent, int parent_slot,
230 struct extent_buffer **cow_ret)
236 if (trans->transaction != root->fs_info->running_transaction) {
237 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
238 root->fs_info->running_transaction->transid);
241 if (trans->transid != root->fs_info->generation) {
242 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
243 root->fs_info->generation);
247 header_trans = btrfs_header_generation(buf);
248 if (header_trans == trans->transid) {
253 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
254 ret = __btrfs_cow_block(trans, root, buf, parent,
255 parent_slot, cow_ret, search_start, 0);
259 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
261 if (blocknr < other && other - (blocknr + blocksize) < 32768)
263 if (blocknr > other && blocknr - (other + blocksize) < 32768)
269 * compare two keys in a memcmp fashion
271 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
275 btrfs_disk_key_to_cpu(&k1, disk);
277 if (k1.objectid > k2->objectid)
279 if (k1.objectid < k2->objectid)
281 if (k1.type > k2->type)
283 if (k1.type < k2->type)
285 if (k1.offset > k2->offset)
287 if (k1.offset < k2->offset)
293 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
294 struct btrfs_root *root, struct extent_buffer *parent,
295 int start_slot, int cache_only, u64 *last_ret,
296 struct btrfs_key *progress)
298 struct extent_buffer *cur;
299 struct extent_buffer *tmp;
301 u64 search_start = *last_ret;
311 int progress_passed = 0;
312 struct btrfs_disk_key disk_key;
314 parent_level = btrfs_header_level(parent);
315 if (cache_only && parent_level != 1)
318 if (trans->transaction != root->fs_info->running_transaction) {
319 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
320 root->fs_info->running_transaction->transid);
323 if (trans->transid != root->fs_info->generation) {
324 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
325 root->fs_info->generation);
329 parent_nritems = btrfs_header_nritems(parent);
330 blocksize = btrfs_level_size(root, parent_level - 1);
331 end_slot = parent_nritems;
333 if (parent_nritems == 1)
336 for (i = start_slot; i < end_slot; i++) {
339 if (!parent->map_token) {
340 map_extent_buffer(parent,
341 btrfs_node_key_ptr_offset(i),
342 sizeof(struct btrfs_key_ptr),
343 &parent->map_token, &parent->kaddr,
344 &parent->map_start, &parent->map_len,
347 btrfs_node_key(parent, &disk_key, i);
348 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
352 blocknr = btrfs_node_blockptr(parent, i);
354 last_block = blocknr;
357 other = btrfs_node_blockptr(parent, i - 1);
358 close = close_blocks(blocknr, other, blocksize);
360 if (close && i < end_slot - 2) {
361 other = btrfs_node_blockptr(parent, i + 1);
362 close = close_blocks(blocknr, other, blocksize);
365 last_block = blocknr;
368 if (parent->map_token) {
369 unmap_extent_buffer(parent, parent->map_token,
371 parent->map_token = NULL;
374 cur = btrfs_find_tree_block(root, blocknr, blocksize);
376 uptodate = btrfs_buffer_uptodate(cur);
379 if (!cur || !uptodate) {
381 free_extent_buffer(cur);
385 cur = read_tree_block(root, blocknr,
387 } else if (!uptodate) {
388 btrfs_read_buffer(cur);
391 if (search_start == 0)
392 search_start = last_block;
394 err = __btrfs_cow_block(trans, root, cur, parent, i,
397 (end_slot - i) * blocksize));
399 free_extent_buffer(cur);
402 search_start = tmp->start;
403 last_block = tmp->start;
404 *last_ret = search_start;
405 if (parent_level == 1)
406 btrfs_clear_buffer_defrag(tmp);
407 free_extent_buffer(tmp);
409 if (parent->map_token) {
410 unmap_extent_buffer(parent, parent->map_token,
412 parent->map_token = NULL;
418 * The leaf data grows from end-to-front in the node.
419 * this returns the address of the start of the last item,
420 * which is the stop of the leaf data stack
422 static inline unsigned int leaf_data_end(struct btrfs_root *root,
423 struct extent_buffer *leaf)
425 u32 nr = btrfs_header_nritems(leaf);
427 return BTRFS_LEAF_DATA_SIZE(root);
428 return btrfs_item_offset_nr(leaf, nr - 1);
431 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
434 struct extent_buffer *parent = NULL;
435 struct extent_buffer *node = path->nodes[level];
436 struct btrfs_disk_key parent_key;
437 struct btrfs_disk_key node_key;
440 struct btrfs_key cpukey;
441 u32 nritems = btrfs_header_nritems(node);
443 if (path->nodes[level + 1])
444 parent = path->nodes[level + 1];
446 slot = path->slots[level];
447 BUG_ON(nritems == 0);
449 parent_slot = path->slots[level + 1];
450 btrfs_node_key(parent, &parent_key, parent_slot);
451 btrfs_node_key(node, &node_key, 0);
452 BUG_ON(memcmp(&parent_key, &node_key,
453 sizeof(struct btrfs_disk_key)));
454 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
455 btrfs_header_bytenr(node));
457 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
459 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
460 btrfs_node_key(node, &node_key, slot);
461 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
463 if (slot < nritems - 1) {
464 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
465 btrfs_node_key(node, &node_key, slot);
466 BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
471 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
474 struct extent_buffer *leaf = path->nodes[level];
475 struct extent_buffer *parent = NULL;
477 struct btrfs_key cpukey;
478 struct btrfs_disk_key parent_key;
479 struct btrfs_disk_key leaf_key;
480 int slot = path->slots[0];
482 u32 nritems = btrfs_header_nritems(leaf);
484 if (path->nodes[level + 1])
485 parent = path->nodes[level + 1];
491 parent_slot = path->slots[level + 1];
492 btrfs_node_key(parent, &parent_key, parent_slot);
493 btrfs_item_key(leaf, &leaf_key, 0);
495 BUG_ON(memcmp(&parent_key, &leaf_key,
496 sizeof(struct btrfs_disk_key)));
497 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
498 btrfs_header_bytenr(leaf));
501 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
502 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
503 btrfs_item_key(leaf, &leaf_key, i);
504 if (comp_keys(&leaf_key, &cpukey) >= 0) {
505 btrfs_print_leaf(root, leaf);
506 printk("slot %d offset bad key\n", i);
509 if (btrfs_item_offset_nr(leaf, i) !=
510 btrfs_item_end_nr(leaf, i + 1)) {
511 btrfs_print_leaf(root, leaf);
512 printk("slot %d offset bad\n", i);
516 if (btrfs_item_offset_nr(leaf, i) +
517 btrfs_item_size_nr(leaf, i) !=
518 BTRFS_LEAF_DATA_SIZE(root)) {
519 btrfs_print_leaf(root, leaf);
520 printk("slot %d first offset bad\n", i);
526 if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
527 btrfs_print_leaf(root, leaf);
528 printk("slot %d bad size \n", nritems - 1);
533 if (slot != 0 && slot < nritems - 1) {
534 btrfs_item_key(leaf, &leaf_key, slot);
535 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
536 if (comp_keys(&leaf_key, &cpukey) <= 0) {
537 btrfs_print_leaf(root, leaf);
538 printk("slot %d offset bad key\n", slot);
541 if (btrfs_item_offset_nr(leaf, slot - 1) !=
542 btrfs_item_end_nr(leaf, slot)) {
543 btrfs_print_leaf(root, leaf);
544 printk("slot %d offset bad\n", slot);
548 if (slot < nritems - 1) {
549 btrfs_item_key(leaf, &leaf_key, slot);
550 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
551 BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
552 if (btrfs_item_offset_nr(leaf, slot) !=
553 btrfs_item_end_nr(leaf, slot + 1)) {
554 btrfs_print_leaf(root, leaf);
555 printk("slot %d offset bad\n", slot);
559 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
560 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
564 static int noinline check_block(struct btrfs_root *root,
565 struct btrfs_path *path, int level)
569 struct extent_buffer *buf = path->nodes[level];
571 if (memcmp_extent_buffer(buf, root->fs_info->fsid,
572 (unsigned long)btrfs_header_fsid(buf),
574 printk("warning bad block %Lu\n", buf->start);
579 return check_leaf(root, path, level);
580 return check_node(root, path, level);
584 * search for key in the extent_buffer. The items start at offset p,
585 * and they are item_size apart. There are 'max' items in p.
587 * the slot in the array is returned via slot, and it points to
588 * the place where you would insert key if it is not found in
591 * slot may point to max if the key is bigger than all of the keys
593 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
594 int item_size, struct btrfs_key *key,
601 struct btrfs_disk_key *tmp = NULL;
602 struct btrfs_disk_key unaligned;
603 unsigned long offset;
604 char *map_token = NULL;
606 unsigned long map_start = 0;
607 unsigned long map_len = 0;
611 mid = (low + high) / 2;
612 offset = p + mid * item_size;
614 if (!map_token || offset < map_start ||
615 (offset + sizeof(struct btrfs_disk_key)) >
616 map_start + map_len) {
618 unmap_extent_buffer(eb, map_token, KM_USER0);
621 err = map_extent_buffer(eb, offset,
622 sizeof(struct btrfs_disk_key),
624 &map_start, &map_len, KM_USER0);
627 tmp = (struct btrfs_disk_key *)(kaddr + offset -
630 read_extent_buffer(eb, &unaligned,
631 offset, sizeof(unaligned));
636 tmp = (struct btrfs_disk_key *)(kaddr + offset -
639 ret = comp_keys(tmp, key);
648 unmap_extent_buffer(eb, map_token, KM_USER0);
654 unmap_extent_buffer(eb, map_token, KM_USER0);
659 * simple bin_search frontend that does the right thing for
662 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
663 int level, int *slot)
666 return generic_bin_search(eb,
667 offsetof(struct btrfs_leaf, items),
668 sizeof(struct btrfs_item),
669 key, btrfs_header_nritems(eb),
672 return generic_bin_search(eb,
673 offsetof(struct btrfs_node, ptrs),
674 sizeof(struct btrfs_key_ptr),
675 key, btrfs_header_nritems(eb),
681 static struct extent_buffer *read_node_slot(struct btrfs_root *root,
682 struct extent_buffer *parent, int slot)
686 if (slot >= btrfs_header_nritems(parent))
688 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
689 btrfs_level_size(root, btrfs_header_level(parent) - 1));
692 static int balance_level(struct btrfs_trans_handle *trans,
693 struct btrfs_root *root,
694 struct btrfs_path *path, int level)
696 struct extent_buffer *right = NULL;
697 struct extent_buffer *mid;
698 struct extent_buffer *left = NULL;
699 struct extent_buffer *parent = NULL;
703 int orig_slot = path->slots[level];
704 int err_on_enospc = 0;
710 mid = path->nodes[level];
711 WARN_ON(btrfs_header_generation(mid) != trans->transid);
713 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
715 if (level < BTRFS_MAX_LEVEL - 1)
716 parent = path->nodes[level + 1];
717 pslot = path->slots[level + 1];
720 * deal with the case where there is only one pointer in the root
721 * by promoting the node below to a root
724 struct extent_buffer *child;
726 if (btrfs_header_nritems(mid) != 1)
729 /* promote the child to a root */
730 child = read_node_slot(root, mid, 0);
732 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
736 add_root_to_dirty_list(root);
737 path->nodes[level] = NULL;
738 clean_tree_block(trans, root, mid);
739 wait_on_tree_block_writeback(root, mid);
740 /* once for the path */
741 free_extent_buffer(mid);
742 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
743 root->root_key.objectid,
744 btrfs_header_generation(mid), 0, 0, 1);
745 /* once for the root ptr */
746 free_extent_buffer(mid);
749 if (btrfs_header_nritems(mid) >
750 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
753 if (btrfs_header_nritems(mid) < 2)
756 left = read_node_slot(root, parent, pslot - 1);
758 wret = btrfs_cow_block(trans, root, left,
759 parent, pslot - 1, &left);
765 right = read_node_slot(root, parent, pslot + 1);
767 wret = btrfs_cow_block(trans, root, right,
768 parent, pslot + 1, &right);
775 /* first, try to make some room in the middle buffer */
777 orig_slot += btrfs_header_nritems(left);
778 wret = push_node_left(trans, root, left, mid);
781 if (btrfs_header_nritems(mid) < 2)
786 * then try to empty the right most buffer into the middle
789 wret = push_node_left(trans, root, mid, right);
790 if (wret < 0 && wret != -ENOSPC)
792 if (btrfs_header_nritems(right) == 0) {
793 u64 bytenr = right->start;
794 u64 generation = btrfs_header_generation(parent);
795 u32 blocksize = right->len;
797 clean_tree_block(trans, root, right);
798 wait_on_tree_block_writeback(root, right);
799 free_extent_buffer(right);
801 wret = del_ptr(trans, root, path, level + 1, pslot +
805 wret = btrfs_free_extent(trans, root, bytenr,
807 btrfs_header_owner(parent),
808 generation, 0, 0, 1);
812 struct btrfs_disk_key right_key;
813 btrfs_node_key(right, &right_key, 0);
814 btrfs_set_node_key(parent, &right_key, pslot + 1);
815 btrfs_mark_buffer_dirty(parent);
818 if (btrfs_header_nritems(mid) == 1) {
820 * we're not allowed to leave a node with one item in the
821 * tree during a delete. A deletion from lower in the tree
822 * could try to delete the only pointer in this node.
823 * So, pull some keys from the left.
824 * There has to be a left pointer at this point because
825 * otherwise we would have pulled some pointers from the
829 wret = balance_node_right(trans, root, mid, left);
836 if (btrfs_header_nritems(mid) == 0) {
837 /* we've managed to empty the middle node, drop it */
838 u64 root_gen = btrfs_header_generation(parent);
839 u64 bytenr = mid->start;
840 u32 blocksize = mid->len;
841 clean_tree_block(trans, root, mid);
842 wait_on_tree_block_writeback(root, mid);
843 free_extent_buffer(mid);
845 wret = del_ptr(trans, root, path, level + 1, pslot);
848 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
849 btrfs_header_owner(parent),
854 /* update the parent key to reflect our changes */
855 struct btrfs_disk_key mid_key;
856 btrfs_node_key(mid, &mid_key, 0);
857 btrfs_set_node_key(parent, &mid_key, pslot);
858 btrfs_mark_buffer_dirty(parent);
861 /* update the path */
863 if (btrfs_header_nritems(left) > orig_slot) {
864 extent_buffer_get(left);
865 path->nodes[level] = left;
866 path->slots[level + 1] -= 1;
867 path->slots[level] = orig_slot;
869 free_extent_buffer(mid);
871 orig_slot -= btrfs_header_nritems(left);
872 path->slots[level] = orig_slot;
875 /* double check we haven't messed things up */
876 check_block(root, path, level);
878 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
882 free_extent_buffer(right);
884 free_extent_buffer(left);
888 /* returns zero if the push worked, non-zero otherwise */
889 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
890 struct btrfs_root *root,
891 struct btrfs_path *path, int level)
893 struct extent_buffer *right = NULL;
894 struct extent_buffer *mid;
895 struct extent_buffer *left = NULL;
896 struct extent_buffer *parent = NULL;
900 int orig_slot = path->slots[level];
906 mid = path->nodes[level];
907 WARN_ON(btrfs_header_generation(mid) != trans->transid);
908 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
910 if (level < BTRFS_MAX_LEVEL - 1)
911 parent = path->nodes[level + 1];
912 pslot = path->slots[level + 1];
917 left = read_node_slot(root, parent, pslot - 1);
919 /* first, try to make some room in the middle buffer */
922 left_nr = btrfs_header_nritems(left);
923 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
926 ret = btrfs_cow_block(trans, root, left, parent,
931 wret = push_node_left(trans, root,
938 struct btrfs_disk_key disk_key;
939 orig_slot += left_nr;
940 btrfs_node_key(mid, &disk_key, 0);
941 btrfs_set_node_key(parent, &disk_key, pslot);
942 btrfs_mark_buffer_dirty(parent);
943 if (btrfs_header_nritems(left) > orig_slot) {
944 path->nodes[level] = left;
945 path->slots[level + 1] -= 1;
946 path->slots[level] = orig_slot;
947 free_extent_buffer(mid);
950 btrfs_header_nritems(left);
951 path->slots[level] = orig_slot;
952 free_extent_buffer(left);
956 free_extent_buffer(left);
958 right= read_node_slot(root, parent, pslot + 1);
961 * then try to empty the right most buffer into the middle
965 right_nr = btrfs_header_nritems(right);
966 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
969 ret = btrfs_cow_block(trans, root, right,
975 wret = balance_node_right(trans, root,
982 struct btrfs_disk_key disk_key;
984 btrfs_node_key(right, &disk_key, 0);
985 btrfs_set_node_key(parent, &disk_key, pslot + 1);
986 btrfs_mark_buffer_dirty(parent);
988 if (btrfs_header_nritems(mid) <= orig_slot) {
989 path->nodes[level] = right;
990 path->slots[level + 1] += 1;
991 path->slots[level] = orig_slot -
992 btrfs_header_nritems(mid);
993 free_extent_buffer(mid);
995 free_extent_buffer(right);
999 free_extent_buffer(right);
1005 * readahead one full node of leaves
1007 static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
1008 int level, int slot, u64 objectid)
1010 struct extent_buffer *node;
1011 struct btrfs_disk_key disk_key;
1017 int direction = path->reada;
1018 struct extent_buffer *eb;
1026 if (!path->nodes[level])
1029 node = path->nodes[level];
1030 search = btrfs_node_blockptr(node, slot);
1031 blocksize = btrfs_level_size(root, level - 1);
1032 eb = btrfs_find_tree_block(root, search, blocksize);
1034 free_extent_buffer(eb);
1038 highest_read = search;
1039 lowest_read = search;
1041 nritems = btrfs_header_nritems(node);
1044 if (direction < 0) {
1048 } else if (direction > 0) {
1053 if (path->reada < 0 && objectid) {
1054 btrfs_node_key(node, &disk_key, nr);
1055 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1058 search = btrfs_node_blockptr(node, nr);
1059 if ((search >= lowest_read && search <= highest_read) ||
1060 (search < lowest_read && lowest_read - search <= 32768) ||
1061 (search > highest_read && search - highest_read <= 32768)) {
1062 readahead_tree_block(root, search, blocksize);
1066 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1068 if(nread > (1024 * 1024) || nscan > 128)
1071 if (search < lowest_read)
1072 lowest_read = search;
1073 if (search > highest_read)
1074 highest_read = search;
1078 * look for key in the tree. path is filled in with nodes along the way
1079 * if key is found, we return zero and you can find the item in the leaf
1080 * level of the path (level 0)
1082 * If the key isn't found, the path points to the slot where it should
1083 * be inserted, and 1 is returned. If there are other errors during the
1084 * search a negative error number is returned.
1086 * if ins_len > 0, nodes and leaves will be split as we walk down the
1087 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1090 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1091 *root, struct btrfs_key *key, struct btrfs_path *p, int
1094 struct extent_buffer *b;
1100 int should_reada = p->reada;
1101 u8 lowest_level = 0;
1103 lowest_level = p->lowest_level;
1104 WARN_ON(lowest_level && ins_len);
1105 WARN_ON(p->nodes[0] != NULL);
1106 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1109 extent_buffer_get(b);
1111 level = btrfs_header_level(b);
1114 wret = btrfs_cow_block(trans, root, b,
1115 p->nodes[level + 1],
1116 p->slots[level + 1],
1119 free_extent_buffer(b);
1123 BUG_ON(!cow && ins_len);
1124 if (level != btrfs_header_level(b))
1126 level = btrfs_header_level(b);
1127 p->nodes[level] = b;
1128 ret = check_block(root, p, level);
1131 ret = bin_search(b, key, level, &slot);
1133 if (ret && slot > 0)
1135 p->slots[level] = slot;
1136 if (ins_len > 0 && btrfs_header_nritems(b) >=
1137 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1138 int sret = split_node(trans, root, p, level);
1142 b = p->nodes[level];
1143 slot = p->slots[level];
1144 } else if (ins_len < 0) {
1145 int sret = balance_level(trans, root, p,
1149 b = p->nodes[level];
1151 btrfs_release_path(NULL, p);
1154 slot = p->slots[level];
1155 BUG_ON(btrfs_header_nritems(b) == 1);
1157 /* this is only true while dropping a snapshot */
1158 if (level == lowest_level)
1160 bytenr = btrfs_node_blockptr(b, slot);
1161 ptr_gen = btrfs_node_ptr_generation(b, slot);
1163 reada_for_search(root, p, level, slot,
1165 b = read_tree_block(root, bytenr,
1166 btrfs_level_size(root, level - 1));
1167 if (ptr_gen != btrfs_header_generation(b)) {
1168 printk("block %llu bad gen wanted %llu "
1170 (unsigned long long)b->start,
1171 (unsigned long long)ptr_gen,
1172 (unsigned long long)btrfs_header_generation(b));
1175 p->slots[level] = slot;
1176 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1177 sizeof(struct btrfs_item) + ins_len) {
1178 int sret = split_leaf(trans, root, key,
1179 p, ins_len, ret == 0);
1191 * adjust the pointers going up the tree, starting at level
1192 * making sure the right key of each node is points to 'key'.
1193 * This is used after shifting pointers to the left, so it stops
1194 * fixing up pointers when a given leaf/node is not in slot 0 of the
1197 * If this fails to write a tree block, it returns -1, but continues
1198 * fixing up the blocks in ram so the tree is consistent.
1200 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1201 struct btrfs_root *root, struct btrfs_path *path,
1202 struct btrfs_disk_key *key, int level)
1206 struct extent_buffer *t;
1208 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1209 int tslot = path->slots[i];
1210 if (!path->nodes[i])
1213 btrfs_set_node_key(t, key, tslot);
1214 btrfs_mark_buffer_dirty(path->nodes[i]);
1222 * try to push data from one node into the next node left in the
1225 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1226 * error, and > 0 if there was no room in the left hand block.
1228 static int push_node_left(struct btrfs_trans_handle *trans,
1229 struct btrfs_root *root, struct extent_buffer *dst,
1230 struct extent_buffer *src)
1237 src_nritems = btrfs_header_nritems(src);
1238 dst_nritems = btrfs_header_nritems(dst);
1239 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1240 WARN_ON(btrfs_header_generation(src) != trans->transid);
1241 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1243 if (push_items <= 0) {
1247 if (src_nritems < push_items)
1248 push_items = src_nritems;
1250 copy_extent_buffer(dst, src,
1251 btrfs_node_key_ptr_offset(dst_nritems),
1252 btrfs_node_key_ptr_offset(0),
1253 push_items * sizeof(struct btrfs_key_ptr));
1255 if (push_items < src_nritems) {
1256 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1257 btrfs_node_key_ptr_offset(push_items),
1258 (src_nritems - push_items) *
1259 sizeof(struct btrfs_key_ptr));
1261 btrfs_set_header_nritems(src, src_nritems - push_items);
1262 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1263 btrfs_mark_buffer_dirty(src);
1264 btrfs_mark_buffer_dirty(dst);
1269 * try to push data from one node into the next node right in the
1272 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1273 * error, and > 0 if there was no room in the right hand block.
1275 * this will only push up to 1/2 the contents of the left node over
1277 static int balance_node_right(struct btrfs_trans_handle *trans,
1278 struct btrfs_root *root,
1279 struct extent_buffer *dst,
1280 struct extent_buffer *src)
1288 WARN_ON(btrfs_header_generation(src) != trans->transid);
1289 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1291 src_nritems = btrfs_header_nritems(src);
1292 dst_nritems = btrfs_header_nritems(dst);
1293 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1294 if (push_items <= 0)
1297 max_push = src_nritems / 2 + 1;
1298 /* don't try to empty the node */
1299 if (max_push >= src_nritems)
1302 if (max_push < push_items)
1303 push_items = max_push;
1305 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1306 btrfs_node_key_ptr_offset(0),
1308 sizeof(struct btrfs_key_ptr));
1310 copy_extent_buffer(dst, src,
1311 btrfs_node_key_ptr_offset(0),
1312 btrfs_node_key_ptr_offset(src_nritems - push_items),
1313 push_items * sizeof(struct btrfs_key_ptr));
1315 btrfs_set_header_nritems(src, src_nritems - push_items);
1316 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1318 btrfs_mark_buffer_dirty(src);
1319 btrfs_mark_buffer_dirty(dst);
1324 * helper function to insert a new root level in the tree.
1325 * A new node is allocated, and a single item is inserted to
1326 * point to the existing root
1328 * returns zero on success or < 0 on failure.
1330 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1331 struct btrfs_root *root,
1332 struct btrfs_path *path, int level)
1336 struct extent_buffer *lower;
1337 struct extent_buffer *c;
1338 struct btrfs_disk_key lower_key;
1340 BUG_ON(path->nodes[level]);
1341 BUG_ON(path->nodes[level-1] != root->node);
1344 root_gen = trans->transid;
1348 lower = path->nodes[level-1];
1350 btrfs_item_key(lower, &lower_key, 0);
1352 btrfs_node_key(lower, &lower_key, 0);
1354 c = __btrfs_alloc_free_block(trans, root, root->nodesize,
1355 root->root_key.objectid,
1356 root_gen, lower_key.objectid, level,
1357 root->node->start, 0);
1360 memset_extent_buffer(c, 0, 0, root->nodesize);
1361 btrfs_set_header_nritems(c, 1);
1362 btrfs_set_header_level(c, level);
1363 btrfs_set_header_bytenr(c, c->start);
1364 btrfs_set_header_generation(c, trans->transid);
1365 btrfs_set_header_owner(c, root->root_key.objectid);
1367 write_extent_buffer(c, root->fs_info->fsid,
1368 (unsigned long)btrfs_header_fsid(c),
1370 btrfs_set_node_key(c, &lower_key, 0);
1371 btrfs_set_node_blockptr(c, 0, lower->start);
1372 lower_gen = btrfs_header_generation(lower);
1373 WARN_ON(lower_gen == 0);
1375 btrfs_set_node_ptr_generation(c, 0, lower_gen);
1377 btrfs_mark_buffer_dirty(c);
1379 /* the super has an extra ref to root->node */
1380 free_extent_buffer(root->node);
1382 add_root_to_dirty_list(root);
1383 extent_buffer_get(c);
1384 path->nodes[level] = c;
1385 path->slots[level] = 0;
1387 if (root->ref_cows && lower_gen != trans->transid) {
1388 struct btrfs_path *back_path = btrfs_alloc_path();
1390 ret = btrfs_insert_extent_backref(trans,
1391 root->fs_info->extent_root,
1393 root->root_key.objectid,
1394 trans->transid, 0, 0);
1396 btrfs_free_path(back_path);
1402 * worker function to insert a single pointer in a node.
1403 * the node should have enough room for the pointer already
1405 * slot and level indicate where you want the key to go, and
1406 * blocknr is the block the key points to.
1408 * returns zero on success and < 0 on any error
1410 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1411 *root, struct btrfs_path *path, struct btrfs_disk_key
1412 *key, u64 bytenr, int slot, int level)
1414 struct extent_buffer *lower;
1417 BUG_ON(!path->nodes[level]);
1418 lower = path->nodes[level];
1419 nritems = btrfs_header_nritems(lower);
1422 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1424 if (slot != nritems) {
1425 memmove_extent_buffer(lower,
1426 btrfs_node_key_ptr_offset(slot + 1),
1427 btrfs_node_key_ptr_offset(slot),
1428 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1430 btrfs_set_node_key(lower, key, slot);
1431 btrfs_set_node_blockptr(lower, slot, bytenr);
1432 WARN_ON(trans->transid == 0);
1433 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1434 btrfs_set_header_nritems(lower, nritems + 1);
1435 btrfs_mark_buffer_dirty(lower);
1440 * split the node at the specified level in path in two.
1441 * The path is corrected to point to the appropriate node after the split
1443 * Before splitting this tries to make some room in the node by pushing
1444 * left and right, if either one works, it returns right away.
1446 * returns 0 on success and < 0 on failure
1448 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1449 *root, struct btrfs_path *path, int level)
1452 struct extent_buffer *c;
1453 struct extent_buffer *split;
1454 struct btrfs_disk_key disk_key;
1460 c = path->nodes[level];
1461 WARN_ON(btrfs_header_generation(c) != trans->transid);
1462 if (c == root->node) {
1463 /* trying to split the root, lets make a new one */
1464 ret = insert_new_root(trans, root, path, level + 1);
1468 ret = push_nodes_for_insert(trans, root, path, level);
1469 c = path->nodes[level];
1470 if (!ret && btrfs_header_nritems(c) <
1471 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1477 c_nritems = btrfs_header_nritems(c);
1479 root_gen = trans->transid;
1483 btrfs_node_key(c, &disk_key, 0);
1484 split = __btrfs_alloc_free_block(trans, root, root->nodesize,
1485 root->root_key.objectid,
1487 btrfs_disk_key_objectid(&disk_key),
1488 level, c->start, 0);
1490 return PTR_ERR(split);
1492 btrfs_set_header_flags(split, btrfs_header_flags(c));
1493 btrfs_set_header_level(split, btrfs_header_level(c));
1494 btrfs_set_header_bytenr(split, split->start);
1495 btrfs_set_header_generation(split, trans->transid);
1496 btrfs_set_header_owner(split, root->root_key.objectid);
1497 write_extent_buffer(split, root->fs_info->fsid,
1498 (unsigned long)btrfs_header_fsid(split),
1501 mid = (c_nritems + 1) / 2;
1503 copy_extent_buffer(split, c,
1504 btrfs_node_key_ptr_offset(0),
1505 btrfs_node_key_ptr_offset(mid),
1506 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1507 btrfs_set_header_nritems(split, c_nritems - mid);
1508 btrfs_set_header_nritems(c, mid);
1511 btrfs_mark_buffer_dirty(c);
1512 btrfs_mark_buffer_dirty(split);
1514 btrfs_node_key(split, &disk_key, 0);
1515 wret = insert_ptr(trans, root, path, &disk_key, split->start,
1516 path->slots[level + 1] + 1,
1521 if (path->slots[level] >= mid) {
1522 path->slots[level] -= mid;
1523 free_extent_buffer(c);
1524 path->nodes[level] = split;
1525 path->slots[level + 1] += 1;
1527 free_extent_buffer(split);
1533 * how many bytes are required to store the items in a leaf. start
1534 * and nr indicate which items in the leaf to check. This totals up the
1535 * space used both by the item structs and the item data
1537 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1540 int nritems = btrfs_header_nritems(l);
1541 int end = min(nritems, start + nr) - 1;
1545 data_len = btrfs_item_end_nr(l, start);
1546 data_len = data_len - btrfs_item_offset_nr(l, end);
1547 data_len += sizeof(struct btrfs_item) * nr;
1548 WARN_ON(data_len < 0);
1553 * The space between the end of the leaf items and
1554 * the start of the leaf data. IOW, how much room
1555 * the leaf has left for both items and data
1557 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1559 int nritems = btrfs_header_nritems(leaf);
1561 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1563 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1564 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1565 leaf_space_used(leaf, 0, nritems), nritems);
1571 * push some data in the path leaf to the right, trying to free up at
1572 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1574 * returns 1 if the push failed because the other node didn't have enough
1575 * room, 0 if everything worked out and < 0 if there were major errors.
1577 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1578 *root, struct btrfs_path *path, int data_size,
1581 struct extent_buffer *left = path->nodes[0];
1582 struct extent_buffer *right;
1583 struct extent_buffer *upper;
1584 struct btrfs_disk_key disk_key;
1590 struct btrfs_item *item;
1598 slot = path->slots[1];
1599 if (!path->nodes[1]) {
1602 upper = path->nodes[1];
1603 if (slot >= btrfs_header_nritems(upper) - 1)
1606 right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1),
1608 free_space = btrfs_leaf_free_space(root, right);
1609 if (free_space < data_size + sizeof(struct btrfs_item)) {
1610 free_extent_buffer(right);
1614 /* cow and double check */
1615 ret = btrfs_cow_block(trans, root, right, upper,
1618 free_extent_buffer(right);
1621 free_space = btrfs_leaf_free_space(root, right);
1622 if (free_space < data_size + sizeof(struct btrfs_item)) {
1623 free_extent_buffer(right);
1627 left_nritems = btrfs_header_nritems(left);
1628 if (left_nritems == 0) {
1629 free_extent_buffer(right);
1638 i = left_nritems - 1;
1640 item = btrfs_item_nr(left, i);
1642 if (path->slots[0] == i)
1643 push_space += data_size + sizeof(*item);
1645 if (!left->map_token) {
1646 map_extent_buffer(left, (unsigned long)item,
1647 sizeof(struct btrfs_item),
1648 &left->map_token, &left->kaddr,
1649 &left->map_start, &left->map_len,
1653 this_item_size = btrfs_item_size(left, item);
1654 if (this_item_size + sizeof(*item) + push_space > free_space)
1657 push_space += this_item_size + sizeof(*item);
1662 if (left->map_token) {
1663 unmap_extent_buffer(left, left->map_token, KM_USER1);
1664 left->map_token = NULL;
1667 if (push_items == 0) {
1668 free_extent_buffer(right);
1672 if (!empty && push_items == left_nritems)
1675 /* push left to right */
1676 right_nritems = btrfs_header_nritems(right);
1678 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1679 push_space -= leaf_data_end(root, left);
1681 /* make room in the right data area */
1682 data_end = leaf_data_end(root, right);
1683 memmove_extent_buffer(right,
1684 btrfs_leaf_data(right) + data_end - push_space,
1685 btrfs_leaf_data(right) + data_end,
1686 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1688 /* copy from the left data area */
1689 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1690 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1691 btrfs_leaf_data(left) + leaf_data_end(root, left),
1694 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1695 btrfs_item_nr_offset(0),
1696 right_nritems * sizeof(struct btrfs_item));
1698 /* copy the items from left to right */
1699 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1700 btrfs_item_nr_offset(left_nritems - push_items),
1701 push_items * sizeof(struct btrfs_item));
1703 /* update the item pointers */
1704 right_nritems += push_items;
1705 btrfs_set_header_nritems(right, right_nritems);
1706 push_space = BTRFS_LEAF_DATA_SIZE(root);
1707 for (i = 0; i < right_nritems; i++) {
1708 item = btrfs_item_nr(right, i);
1709 if (!right->map_token) {
1710 map_extent_buffer(right, (unsigned long)item,
1711 sizeof(struct btrfs_item),
1712 &right->map_token, &right->kaddr,
1713 &right->map_start, &right->map_len,
1716 push_space -= btrfs_item_size(right, item);
1717 btrfs_set_item_offset(right, item, push_space);
1720 if (right->map_token) {
1721 unmap_extent_buffer(right, right->map_token, KM_USER1);
1722 right->map_token = NULL;
1724 left_nritems -= push_items;
1725 btrfs_set_header_nritems(left, left_nritems);
1728 btrfs_mark_buffer_dirty(left);
1729 btrfs_mark_buffer_dirty(right);
1731 btrfs_item_key(right, &disk_key, 0);
1732 btrfs_set_node_key(upper, &disk_key, slot + 1);
1733 btrfs_mark_buffer_dirty(upper);
1735 /* then fixup the leaf pointer in the path */
1736 if (path->slots[0] >= left_nritems) {
1737 path->slots[0] -= left_nritems;
1738 free_extent_buffer(path->nodes[0]);
1739 path->nodes[0] = right;
1740 path->slots[1] += 1;
1742 free_extent_buffer(right);
1747 * push some data in the path leaf to the left, trying to free up at
1748 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1750 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1751 *root, struct btrfs_path *path, int data_size,
1754 struct btrfs_disk_key disk_key;
1755 struct extent_buffer *right = path->nodes[0];
1756 struct extent_buffer *left;
1762 struct btrfs_item *item;
1763 u32 old_left_nritems;
1769 u32 old_left_item_size;
1771 slot = path->slots[1];
1774 if (!path->nodes[1])
1777 right_nritems = btrfs_header_nritems(right);
1778 if (right_nritems == 0) {
1782 left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1783 slot - 1), root->leafsize);
1784 free_space = btrfs_leaf_free_space(root, left);
1785 if (free_space < data_size + sizeof(struct btrfs_item)) {
1786 free_extent_buffer(left);
1790 /* cow and double check */
1791 ret = btrfs_cow_block(trans, root, left,
1792 path->nodes[1], slot - 1, &left);
1794 /* we hit -ENOSPC, but it isn't fatal here */
1795 free_extent_buffer(left);
1799 free_space = btrfs_leaf_free_space(root, left);
1800 if (free_space < data_size + sizeof(struct btrfs_item)) {
1801 free_extent_buffer(left);
1808 nr = right_nritems - 1;
1810 for (i = 0; i < nr; i++) {
1811 item = btrfs_item_nr(right, i);
1812 if (!right->map_token) {
1813 map_extent_buffer(right, (unsigned long)item,
1814 sizeof(struct btrfs_item),
1815 &right->map_token, &right->kaddr,
1816 &right->map_start, &right->map_len,
1820 if (path->slots[0] == i)
1821 push_space += data_size + sizeof(*item);
1823 this_item_size = btrfs_item_size(right, item);
1824 if (this_item_size + sizeof(*item) + push_space > free_space)
1828 push_space += this_item_size + sizeof(*item);
1831 if (right->map_token) {
1832 unmap_extent_buffer(right, right->map_token, KM_USER1);
1833 right->map_token = NULL;
1836 if (push_items == 0) {
1837 free_extent_buffer(left);
1840 if (!empty && push_items == btrfs_header_nritems(right))
1843 /* push data from right to left */
1844 copy_extent_buffer(left, right,
1845 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1846 btrfs_item_nr_offset(0),
1847 push_items * sizeof(struct btrfs_item));
1849 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1850 btrfs_item_offset_nr(right, push_items -1);
1852 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1853 leaf_data_end(root, left) - push_space,
1854 btrfs_leaf_data(right) +
1855 btrfs_item_offset_nr(right, push_items - 1),
1857 old_left_nritems = btrfs_header_nritems(left);
1858 BUG_ON(old_left_nritems < 0);
1860 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1861 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1864 item = btrfs_item_nr(left, i);
1865 if (!left->map_token) {
1866 map_extent_buffer(left, (unsigned long)item,
1867 sizeof(struct btrfs_item),
1868 &left->map_token, &left->kaddr,
1869 &left->map_start, &left->map_len,
1873 ioff = btrfs_item_offset(left, item);
1874 btrfs_set_item_offset(left, item,
1875 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1877 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1878 if (left->map_token) {
1879 unmap_extent_buffer(left, left->map_token, KM_USER1);
1880 left->map_token = NULL;
1883 /* fixup right node */
1884 if (push_items > right_nritems) {
1885 printk("push items %d nr %u\n", push_items, right_nritems);
1889 if (push_items < right_nritems) {
1890 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1891 leaf_data_end(root, right);
1892 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1893 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1894 btrfs_leaf_data(right) +
1895 leaf_data_end(root, right), push_space);
1897 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
1898 btrfs_item_nr_offset(push_items),
1899 (btrfs_header_nritems(right) - push_items) *
1900 sizeof(struct btrfs_item));
1902 right_nritems -= push_items;
1903 btrfs_set_header_nritems(right, right_nritems);
1904 push_space = BTRFS_LEAF_DATA_SIZE(root);
1905 for (i = 0; i < right_nritems; i++) {
1906 item = btrfs_item_nr(right, i);
1908 if (!right->map_token) {
1909 map_extent_buffer(right, (unsigned long)item,
1910 sizeof(struct btrfs_item),
1911 &right->map_token, &right->kaddr,
1912 &right->map_start, &right->map_len,
1916 push_space = push_space - btrfs_item_size(right, item);
1917 btrfs_set_item_offset(right, item, push_space);
1919 if (right->map_token) {
1920 unmap_extent_buffer(right, right->map_token, KM_USER1);
1921 right->map_token = NULL;
1924 btrfs_mark_buffer_dirty(left);
1926 btrfs_mark_buffer_dirty(right);
1928 btrfs_item_key(right, &disk_key, 0);
1929 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1933 /* then fixup the leaf pointer in the path */
1934 if (path->slots[0] < push_items) {
1935 path->slots[0] += old_left_nritems;
1936 free_extent_buffer(path->nodes[0]);
1937 path->nodes[0] = left;
1938 path->slots[1] -= 1;
1940 free_extent_buffer(left);
1941 path->slots[0] -= push_items;
1943 BUG_ON(path->slots[0] < 0);
1948 * split the path's leaf in two, making sure there is at least data_size
1949 * available for the resulting leaf level of the path.
1951 * returns 0 if all went well and < 0 on failure.
1953 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1954 *root, struct btrfs_key *ins_key,
1955 struct btrfs_path *path, int data_size, int extend)
1958 struct extent_buffer *l;
1962 struct extent_buffer *right;
1963 int space_needed = data_size + sizeof(struct btrfs_item);
1970 int num_doubles = 0;
1971 struct btrfs_disk_key disk_key;
1974 space_needed = data_size;
1977 root_gen = trans->transid;
1981 /* first try to make some room by pushing left and right */
1982 if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
1983 wret = push_leaf_right(trans, root, path, data_size, 0);
1988 wret = push_leaf_left(trans, root, path, data_size, 0);
1994 /* did the pushes work? */
1995 if (btrfs_leaf_free_space(root, l) >= space_needed)
1999 if (!path->nodes[1]) {
2000 ret = insert_new_root(trans, root, path, 1);
2007 slot = path->slots[0];
2008 nritems = btrfs_header_nritems(l);
2009 mid = (nritems + 1)/ 2;
2011 btrfs_item_key(l, &disk_key, 0);
2013 right = __btrfs_alloc_free_block(trans, root, root->leafsize,
2014 root->root_key.objectid,
2015 root_gen, disk_key.objectid, 0,
2018 return PTR_ERR(right);
2020 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2021 btrfs_set_header_bytenr(right, right->start);
2022 btrfs_set_header_generation(right, trans->transid);
2023 btrfs_set_header_owner(right, root->root_key.objectid);
2024 btrfs_set_header_level(right, 0);
2025 write_extent_buffer(right, root->fs_info->fsid,
2026 (unsigned long)btrfs_header_fsid(right),
2030 leaf_space_used(l, mid, nritems - mid) + space_needed >
2031 BTRFS_LEAF_DATA_SIZE(root)) {
2032 if (slot >= nritems) {
2033 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2034 btrfs_set_header_nritems(right, 0);
2035 wret = insert_ptr(trans, root, path,
2036 &disk_key, right->start,
2037 path->slots[1] + 1, 1);
2040 free_extent_buffer(path->nodes[0]);
2041 path->nodes[0] = right;
2043 path->slots[1] += 1;
2047 if (mid != nritems &&
2048 leaf_space_used(l, mid, nritems - mid) +
2049 space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
2054 if (leaf_space_used(l, 0, mid + 1) + space_needed >
2055 BTRFS_LEAF_DATA_SIZE(root)) {
2056 if (!extend && slot == 0) {
2057 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2058 btrfs_set_header_nritems(right, 0);
2059 wret = insert_ptr(trans, root, path,
2065 free_extent_buffer(path->nodes[0]);
2066 path->nodes[0] = right;
2068 if (path->slots[1] == 0) {
2069 wret = fixup_low_keys(trans, root,
2070 path, &disk_key, 1);
2075 } else if (extend && slot == 0) {
2079 if (mid != nritems &&
2080 leaf_space_used(l, mid, nritems - mid) +
2081 space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
2087 nritems = nritems - mid;
2088 btrfs_set_header_nritems(right, nritems);
2089 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2091 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2092 btrfs_item_nr_offset(mid),
2093 nritems * sizeof(struct btrfs_item));
2095 copy_extent_buffer(right, l,
2096 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2097 data_copy_size, btrfs_leaf_data(l) +
2098 leaf_data_end(root, l), data_copy_size);
2100 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2101 btrfs_item_end_nr(l, mid);
2103 for (i = 0; i < nritems; i++) {
2104 struct btrfs_item *item = btrfs_item_nr(right, i);
2107 if (!right->map_token) {
2108 map_extent_buffer(right, (unsigned long)item,
2109 sizeof(struct btrfs_item),
2110 &right->map_token, &right->kaddr,
2111 &right->map_start, &right->map_len,
2115 ioff = btrfs_item_offset(right, item);
2116 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2119 if (right->map_token) {
2120 unmap_extent_buffer(right, right->map_token, KM_USER1);
2121 right->map_token = NULL;
2124 btrfs_set_header_nritems(l, mid);
2126 btrfs_item_key(right, &disk_key, 0);
2127 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2128 path->slots[1] + 1, 1);
2132 btrfs_mark_buffer_dirty(right);
2133 btrfs_mark_buffer_dirty(l);
2134 BUG_ON(path->slots[0] != slot);
2137 free_extent_buffer(path->nodes[0]);
2138 path->nodes[0] = right;
2139 path->slots[0] -= mid;
2140 path->slots[1] += 1;
2142 free_extent_buffer(right);
2144 BUG_ON(path->slots[0] < 0);
2147 BUG_ON(num_doubles != 0);
2154 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2155 struct btrfs_root *root,
2156 struct btrfs_path *path,
2157 u32 new_size, int from_end)
2162 struct extent_buffer *leaf;
2163 struct btrfs_item *item;
2165 unsigned int data_end;
2166 unsigned int old_data_start;
2167 unsigned int old_size;
2168 unsigned int size_diff;
2171 slot_orig = path->slots[0];
2172 leaf = path->nodes[0];
2173 slot = path->slots[0];
2175 old_size = btrfs_item_size_nr(leaf, slot);
2176 if (old_size == new_size)
2179 nritems = btrfs_header_nritems(leaf);
2180 data_end = leaf_data_end(root, leaf);
2182 old_data_start = btrfs_item_offset_nr(leaf, slot);
2184 size_diff = old_size - new_size;
2187 BUG_ON(slot >= nritems);
2190 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2192 /* first correct the data pointers */
2193 for (i = slot; i < nritems; i++) {
2195 item = btrfs_item_nr(leaf, i);
2197 if (!leaf->map_token) {
2198 map_extent_buffer(leaf, (unsigned long)item,
2199 sizeof(struct btrfs_item),
2200 &leaf->map_token, &leaf->kaddr,
2201 &leaf->map_start, &leaf->map_len,
2205 ioff = btrfs_item_offset(leaf, item);
2206 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2209 if (leaf->map_token) {
2210 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2211 leaf->map_token = NULL;
2214 /* shift the data */
2216 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2217 data_end + size_diff, btrfs_leaf_data(leaf) +
2218 data_end, old_data_start + new_size - data_end);
2220 struct btrfs_disk_key disk_key;
2223 btrfs_item_key(leaf, &disk_key, slot);
2225 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2227 struct btrfs_file_extent_item *fi;
2229 fi = btrfs_item_ptr(leaf, slot,
2230 struct btrfs_file_extent_item);
2231 fi = (struct btrfs_file_extent_item *)(
2232 (unsigned long)fi - size_diff);
2234 if (btrfs_file_extent_type(leaf, fi) ==
2235 BTRFS_FILE_EXTENT_INLINE) {
2236 ptr = btrfs_item_ptr_offset(leaf, slot);
2237 memmove_extent_buffer(leaf, ptr,
2239 offsetof(struct btrfs_file_extent_item,
2244 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2245 data_end + size_diff, btrfs_leaf_data(leaf) +
2246 data_end, old_data_start - data_end);
2248 offset = btrfs_disk_key_offset(&disk_key);
2249 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2250 btrfs_set_item_key(leaf, &disk_key, slot);
2252 fixup_low_keys(trans, root, path, &disk_key, 1);
2255 item = btrfs_item_nr(leaf, slot);
2256 btrfs_set_item_size(leaf, item, new_size);
2257 btrfs_mark_buffer_dirty(leaf);
2260 if (btrfs_leaf_free_space(root, leaf) < 0) {
2261 btrfs_print_leaf(root, leaf);
2267 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2268 struct btrfs_root *root, struct btrfs_path *path,
2274 struct extent_buffer *leaf;
2275 struct btrfs_item *item;
2277 unsigned int data_end;
2278 unsigned int old_data;
2279 unsigned int old_size;
2282 slot_orig = path->slots[0];
2283 leaf = path->nodes[0];
2285 nritems = btrfs_header_nritems(leaf);
2286 data_end = leaf_data_end(root, leaf);
2288 if (btrfs_leaf_free_space(root, leaf) < data_size) {
2289 btrfs_print_leaf(root, leaf);
2292 slot = path->slots[0];
2293 old_data = btrfs_item_end_nr(leaf, slot);
2296 if (slot >= nritems) {
2297 btrfs_print_leaf(root, leaf);
2298 printk("slot %d too large, nritems %d\n", slot, nritems);
2303 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2305 /* first correct the data pointers */
2306 for (i = slot; i < nritems; i++) {
2308 item = btrfs_item_nr(leaf, i);
2310 if (!leaf->map_token) {
2311 map_extent_buffer(leaf, (unsigned long)item,
2312 sizeof(struct btrfs_item),
2313 &leaf->map_token, &leaf->kaddr,
2314 &leaf->map_start, &leaf->map_len,
2317 ioff = btrfs_item_offset(leaf, item);
2318 btrfs_set_item_offset(leaf, item, ioff - data_size);
2321 if (leaf->map_token) {
2322 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2323 leaf->map_token = NULL;
2326 /* shift the data */
2327 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2328 data_end - data_size, btrfs_leaf_data(leaf) +
2329 data_end, old_data - data_end);
2331 data_end = old_data;
2332 old_size = btrfs_item_size_nr(leaf, slot);
2333 item = btrfs_item_nr(leaf, slot);
2334 btrfs_set_item_size(leaf, item, old_size + data_size);
2335 btrfs_mark_buffer_dirty(leaf);
2338 if (btrfs_leaf_free_space(root, leaf) < 0) {
2339 btrfs_print_leaf(root, leaf);
2346 * Given a key and some data, insert an item into the tree.
2347 * This does all the path init required, making room in the tree if needed.
2349 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2350 struct btrfs_root *root,
2351 struct btrfs_path *path,
2352 struct btrfs_key *cpu_key, u32 *data_size,
2355 struct extent_buffer *leaf;
2356 struct btrfs_item *item;
2364 unsigned int data_end;
2365 struct btrfs_disk_key disk_key;
2367 for (i = 0; i < nr; i++) {
2368 total_data += data_size[i];
2371 /* create a root if there isn't one */
2375 total_size = total_data + (nr - 1) * sizeof(struct btrfs_item);
2376 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2383 slot_orig = path->slots[0];
2384 leaf = path->nodes[0];
2386 nritems = btrfs_header_nritems(leaf);
2387 data_end = leaf_data_end(root, leaf);
2389 if (btrfs_leaf_free_space(root, leaf) <
2390 sizeof(struct btrfs_item) + total_size) {
2391 btrfs_print_leaf(root, leaf);
2392 printk("not enough freespace need %u have %d\n",
2393 total_size, btrfs_leaf_free_space(root, leaf));
2397 slot = path->slots[0];
2400 if (slot != nritems) {
2402 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2404 if (old_data < data_end) {
2405 btrfs_print_leaf(root, leaf);
2406 printk("slot %d old_data %d data_end %d\n",
2407 slot, old_data, data_end);
2411 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2413 /* first correct the data pointers */
2414 WARN_ON(leaf->map_token);
2415 for (i = slot; i < nritems; i++) {
2418 item = btrfs_item_nr(leaf, i);
2419 if (!leaf->map_token) {
2420 map_extent_buffer(leaf, (unsigned long)item,
2421 sizeof(struct btrfs_item),
2422 &leaf->map_token, &leaf->kaddr,
2423 &leaf->map_start, &leaf->map_len,
2427 ioff = btrfs_item_offset(leaf, item);
2428 btrfs_set_item_offset(leaf, item, ioff - total_data);
2430 if (leaf->map_token) {
2431 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2432 leaf->map_token = NULL;
2435 /* shift the items */
2436 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2437 btrfs_item_nr_offset(slot),
2438 (nritems - slot) * sizeof(struct btrfs_item));
2440 /* shift the data */
2441 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2442 data_end - total_data, btrfs_leaf_data(leaf) +
2443 data_end, old_data - data_end);
2444 data_end = old_data;
2447 /* setup the item for the new data */
2448 for (i = 0; i < nr; i++) {
2449 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2450 btrfs_set_item_key(leaf, &disk_key, slot + i);
2451 item = btrfs_item_nr(leaf, slot + i);
2452 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2453 data_end -= data_size[i];
2454 btrfs_set_item_size(leaf, item, data_size[i]);
2456 btrfs_set_header_nritems(leaf, nritems + nr);
2457 btrfs_mark_buffer_dirty(leaf);
2461 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2462 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2465 if (btrfs_leaf_free_space(root, leaf) < 0) {
2466 btrfs_print_leaf(root, leaf);
2475 * Given a key and some data, insert an item into the tree.
2476 * This does all the path init required, making room in the tree if needed.
2478 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2479 *root, struct btrfs_key *cpu_key, void *data, u32
2483 struct btrfs_path *path;
2484 struct extent_buffer *leaf;
2487 path = btrfs_alloc_path();
2489 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2491 leaf = path->nodes[0];
2492 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2493 write_extent_buffer(leaf, data, ptr, data_size);
2494 btrfs_mark_buffer_dirty(leaf);
2496 btrfs_free_path(path);
2501 * delete the pointer from a given node.
2503 * If the delete empties a node, the node is removed from the tree,
2504 * continuing all the way the root if required. The root is converted into
2505 * a leaf if all the nodes are emptied.
2507 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2508 struct btrfs_path *path, int level, int slot)
2510 struct extent_buffer *parent = path->nodes[level];
2515 nritems = btrfs_header_nritems(parent);
2516 if (slot != nritems -1) {
2517 memmove_extent_buffer(parent,
2518 btrfs_node_key_ptr_offset(slot),
2519 btrfs_node_key_ptr_offset(slot + 1),
2520 sizeof(struct btrfs_key_ptr) *
2521 (nritems - slot - 1));
2524 btrfs_set_header_nritems(parent, nritems);
2525 if (nritems == 0 && parent == root->node) {
2526 BUG_ON(btrfs_header_level(root->node) != 1);
2527 /* just turn the root into a leaf and break */
2528 btrfs_set_header_level(root->node, 0);
2529 } else if (slot == 0) {
2530 struct btrfs_disk_key disk_key;
2532 btrfs_node_key(parent, &disk_key, 0);
2533 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2537 btrfs_mark_buffer_dirty(parent);
2542 * delete the item at the leaf level in path. If that empties
2543 * the leaf, remove it from the tree
2545 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2546 struct btrfs_path *path, int slot, int nr)
2548 struct extent_buffer *leaf;
2549 struct btrfs_item *item;
2557 leaf = path->nodes[0];
2558 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2560 for (i = 0; i < nr; i++)
2561 dsize += btrfs_item_size_nr(leaf, slot + i);
2563 nritems = btrfs_header_nritems(leaf);
2565 if (slot + nr != nritems) {
2567 int data_end = leaf_data_end(root, leaf);
2569 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2571 btrfs_leaf_data(leaf) + data_end,
2572 last_off - data_end);
2574 for (i = slot + nr; i < nritems; i++) {
2577 item = btrfs_item_nr(leaf, i);
2578 if (!leaf->map_token) {
2579 map_extent_buffer(leaf, (unsigned long)item,
2580 sizeof(struct btrfs_item),
2581 &leaf->map_token, &leaf->kaddr,
2582 &leaf->map_start, &leaf->map_len,
2585 ioff = btrfs_item_offset(leaf, item);
2586 btrfs_set_item_offset(leaf, item, ioff + dsize);
2589 if (leaf->map_token) {
2590 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2591 leaf->map_token = NULL;
2594 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2595 btrfs_item_nr_offset(slot + nr),
2596 sizeof(struct btrfs_item) *
2597 (nritems - slot - nr));
2599 btrfs_set_header_nritems(leaf, nritems - nr);
2602 /* delete the leaf if we've emptied it */
2604 if (leaf == root->node) {
2605 btrfs_set_header_level(leaf, 0);
2607 u64 root_gen = btrfs_header_generation(path->nodes[1]);
2608 clean_tree_block(trans, root, leaf);
2609 wait_on_tree_block_writeback(root, leaf);
2610 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2613 wret = btrfs_free_extent(trans, root,
2614 leaf->start, leaf->len,
2615 btrfs_header_owner(path->nodes[1]),
2621 int used = leaf_space_used(leaf, 0, nritems);
2623 struct btrfs_disk_key disk_key;
2625 btrfs_item_key(leaf, &disk_key, 0);
2626 wret = fixup_low_keys(trans, root, path,
2632 /* delete the leaf if it is mostly empty */
2633 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2634 /* push_leaf_left fixes the path.
2635 * make sure the path still points to our leaf
2636 * for possible call to del_ptr below
2638 slot = path->slots[1];
2639 extent_buffer_get(leaf);
2641 wret = push_leaf_left(trans, root, path, 1, 1);
2642 if (wret < 0 && wret != -ENOSPC)
2645 if (path->nodes[0] == leaf &&
2646 btrfs_header_nritems(leaf)) {
2647 wret = push_leaf_right(trans, root, path, 1, 1);
2648 if (wret < 0 && wret != -ENOSPC)
2652 if (btrfs_header_nritems(leaf) == 0) {
2654 u64 bytenr = leaf->start;
2655 u32 blocksize = leaf->len;
2657 root_gen = btrfs_header_generation(
2660 clean_tree_block(trans, root, leaf);
2661 wait_on_tree_block_writeback(root, leaf);
2663 wret = del_ptr(trans, root, path, 1, slot);
2667 free_extent_buffer(leaf);
2668 wret = btrfs_free_extent(trans, root, bytenr,
2670 btrfs_header_owner(path->nodes[1]),
2675 btrfs_mark_buffer_dirty(leaf);
2676 free_extent_buffer(leaf);
2679 btrfs_mark_buffer_dirty(leaf);
2686 * walk up the tree as far as required to find the previous leaf.
2687 * returns 0 if it found something or 1 if there are no lesser leaves.
2688 * returns < 0 on io errors.
2690 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2695 struct extent_buffer *c;
2696 struct extent_buffer *next = NULL;
2698 while(level < BTRFS_MAX_LEVEL) {
2699 if (!path->nodes[level])
2702 slot = path->slots[level];
2703 c = path->nodes[level];
2706 if (level == BTRFS_MAX_LEVEL)
2712 bytenr = btrfs_node_blockptr(c, slot);
2714 free_extent_buffer(next);
2716 next = read_tree_block(root, bytenr,
2717 btrfs_level_size(root, level - 1));
2720 path->slots[level] = slot;
2723 c = path->nodes[level];
2724 free_extent_buffer(c);
2725 slot = btrfs_header_nritems(next);
2728 path->nodes[level] = next;
2729 path->slots[level] = slot;
2732 next = read_tree_block(root, btrfs_node_blockptr(next, slot),
2733 btrfs_level_size(root, level - 1));
2739 * walk up the tree as far as required to find the next leaf.
2740 * returns 0 if it found something or 1 if there are no greater leaves.
2741 * returns < 0 on io errors.
2743 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2748 struct extent_buffer *c;
2749 struct extent_buffer *next = NULL;
2751 while(level < BTRFS_MAX_LEVEL) {
2752 if (!path->nodes[level])
2755 slot = path->slots[level] + 1;
2756 c = path->nodes[level];
2757 if (slot >= btrfs_header_nritems(c)) {
2759 if (level == BTRFS_MAX_LEVEL)
2764 bytenr = btrfs_node_blockptr(c, slot);
2766 free_extent_buffer(next);
2769 reada_for_search(root, path, level, slot, 0);
2771 next = read_tree_block(root, bytenr,
2772 btrfs_level_size(root, level -1));
2775 path->slots[level] = slot;
2778 c = path->nodes[level];
2779 free_extent_buffer(c);
2780 path->nodes[level] = next;
2781 path->slots[level] = 0;
2785 reada_for_search(root, path, level, 0, 0);
2786 next = read_tree_block(root, btrfs_node_blockptr(next, 0),
2787 btrfs_level_size(root, level - 1));
2792 int btrfs_previous_item(struct btrfs_root *root,
2793 struct btrfs_path *path, u64 min_objectid,
2796 struct btrfs_key found_key;
2797 struct extent_buffer *leaf;
2801 if (path->slots[0] == 0) {
2802 ret = btrfs_prev_leaf(root, path);
2808 leaf = path->nodes[0];
2809 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2810 if (found_key.type == type)