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"
23 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
24 *root, struct btrfs_path *path, int level);
25 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
26 *root, struct btrfs_key *ins_key,
27 struct btrfs_path *path, int data_size, int extend);
28 static int push_node_left(struct btrfs_trans_handle *trans,
29 struct btrfs_root *root, struct extent_buffer *dst,
30 struct extent_buffer *src, int empty);
31 static int balance_node_right(struct btrfs_trans_handle *trans,
32 struct btrfs_root *root,
33 struct extent_buffer *dst_buf,
34 struct extent_buffer *src_buf);
35 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
36 struct btrfs_path *path, int level, int slot);
38 inline void btrfs_init_path(struct btrfs_path *p)
40 memset(p, 0, sizeof(*p));
43 struct btrfs_path *btrfs_alloc_path(void)
45 struct btrfs_path *path;
46 path = kmalloc(sizeof(struct btrfs_path), GFP_NOFS);
48 btrfs_init_path(path);
54 void btrfs_free_path(struct btrfs_path *p)
56 btrfs_release_path(NULL, p);
60 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
63 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
66 free_extent_buffer(p->nodes[i]);
68 memset(p, 0, sizeof(*p));
71 static void add_root_to_dirty_list(struct btrfs_root *root)
73 if (root->track_dirty && list_empty(&root->dirty_list)) {
74 list_add(&root->dirty_list,
75 &root->fs_info->dirty_cowonly_roots);
79 int btrfs_copy_root(struct btrfs_trans_handle *trans,
80 struct btrfs_root *root,
81 struct extent_buffer *buf,
82 struct extent_buffer **cow_ret, u64 new_root_objectid)
84 struct extent_buffer *cow;
87 struct btrfs_root *new_root;
88 struct btrfs_disk_key disk_key;
90 new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
94 memcpy(new_root, root, sizeof(*new_root));
95 new_root->root_key.objectid = new_root_objectid;
97 WARN_ON(root->ref_cows && trans->transid !=
98 root->fs_info->running_transaction->transid);
99 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
101 level = btrfs_header_level(buf);
103 btrfs_item_key(buf, &disk_key, 0);
105 btrfs_node_key(buf, &disk_key, 0);
106 cow = btrfs_alloc_free_block(trans, new_root, buf->len,
107 new_root_objectid, &disk_key,
108 level, buf->start, 0);
114 copy_extent_buffer(cow, buf, 0, 0, cow->len);
115 btrfs_set_header_bytenr(cow, cow->start);
116 btrfs_set_header_generation(cow, trans->transid);
117 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
118 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
119 BTRFS_HEADER_FLAG_RELOC);
120 if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
121 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
123 btrfs_set_header_owner(cow, new_root_objectid);
125 write_extent_buffer(cow, root->fs_info->fsid,
126 (unsigned long)btrfs_header_fsid(cow),
129 WARN_ON(btrfs_header_generation(buf) > trans->transid);
130 ret = btrfs_inc_ref(trans, new_root, cow, 0);
136 btrfs_mark_buffer_dirty(cow);
141 int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
142 struct btrfs_root *root)
144 struct extent_buffer *c;
145 struct extent_buffer *old = root->node;
147 struct btrfs_disk_key disk_key = {0,0,0};
151 c = btrfs_alloc_free_block(trans, root,
152 btrfs_level_size(root, 0),
153 root->root_key.objectid,
154 &disk_key, level, 0, 0);
158 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
159 btrfs_set_header_level(c, level);
160 btrfs_set_header_bytenr(c, c->start);
161 btrfs_set_header_generation(c, trans->transid);
162 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
163 btrfs_set_header_owner(c, root->root_key.objectid);
165 write_extent_buffer(c, root->fs_info->fsid,
166 (unsigned long)btrfs_header_fsid(c),
169 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
170 (unsigned long)btrfs_header_chunk_tree_uuid(c),
173 btrfs_mark_buffer_dirty(c);
175 free_extent_buffer(old);
177 add_root_to_dirty_list(root);
182 * check if the tree block can be shared by multiple trees
184 int btrfs_block_can_be_shared(struct btrfs_root *root,
185 struct extent_buffer *buf)
188 * Tree blocks not in refernece counted trees and tree roots
189 * are never shared. If a block was allocated after the last
190 * snapshot and the block was not allocated by tree relocation,
191 * we know the block is not shared.
193 if (root->ref_cows &&
194 buf != root->node && buf != root->commit_root &&
195 (btrfs_header_generation(buf) <=
196 btrfs_root_last_snapshot(&root->root_item) ||
197 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
199 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
200 if (root->ref_cows &&
201 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
207 static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
208 struct btrfs_root *root,
209 struct extent_buffer *buf,
210 struct extent_buffer *cow)
219 * Backrefs update rules:
221 * Always use full backrefs for extent pointers in tree block
222 * allocated by tree relocation.
224 * If a shared tree block is no longer referenced by its owner
225 * tree (btrfs_header_owner(buf) == root->root_key.objectid),
226 * use full backrefs for extent pointers in tree block.
228 * If a tree block is been relocating
229 * (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
230 * use full backrefs for extent pointers in tree block.
231 * The reason for this is some operations (such as drop tree)
232 * are only allowed for blocks use full backrefs.
235 if (btrfs_block_can_be_shared(root, buf)) {
236 ret = btrfs_lookup_extent_info(trans, root, buf->start,
237 buf->len, &refs, &flags);
242 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
243 btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
244 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
249 owner = btrfs_header_owner(buf);
250 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
251 owner == BTRFS_TREE_RELOC_OBJECTID);
254 if ((owner == root->root_key.objectid ||
255 root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) &&
256 !(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
257 ret = btrfs_inc_ref(trans, root, buf, 1);
260 if (root->root_key.objectid ==
261 BTRFS_TREE_RELOC_OBJECTID) {
262 ret = btrfs_dec_ref(trans, root, buf, 0);
264 ret = btrfs_inc_ref(trans, root, cow, 1);
267 new_flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
270 if (root->root_key.objectid ==
271 BTRFS_TREE_RELOC_OBJECTID)
272 ret = btrfs_inc_ref(trans, root, cow, 1);
274 ret = btrfs_inc_ref(trans, root, cow, 0);
277 if (new_flags != 0) {
278 ret = btrfs_set_block_flags(trans, root, buf->start,
279 buf->len, new_flags);
283 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
284 if (root->root_key.objectid ==
285 BTRFS_TREE_RELOC_OBJECTID)
286 ret = btrfs_inc_ref(trans, root, cow, 1);
288 ret = btrfs_inc_ref(trans, root, cow, 0);
290 ret = btrfs_dec_ref(trans, root, buf, 1);
293 clean_tree_block(trans, root, buf);
298 int __btrfs_cow_block(struct btrfs_trans_handle *trans,
299 struct btrfs_root *root,
300 struct extent_buffer *buf,
301 struct extent_buffer *parent, int parent_slot,
302 struct extent_buffer **cow_ret,
303 u64 search_start, u64 empty_size)
305 struct extent_buffer *cow;
306 struct btrfs_disk_key disk_key;
309 WARN_ON(root->ref_cows && trans->transid !=
310 root->fs_info->running_transaction->transid);
311 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
313 level = btrfs_header_level(buf);
316 btrfs_item_key(buf, &disk_key, 0);
318 btrfs_node_key(buf, &disk_key, 0);
320 cow = btrfs_alloc_free_block(trans, root, buf->len,
321 root->root_key.objectid, &disk_key,
322 level, search_start, empty_size);
326 copy_extent_buffer(cow, buf, 0, 0, cow->len);
327 btrfs_set_header_bytenr(cow, cow->start);
328 btrfs_set_header_generation(cow, trans->transid);
329 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
330 btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN |
331 BTRFS_HEADER_FLAG_RELOC);
332 if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
333 btrfs_set_header_flag(cow, BTRFS_HEADER_FLAG_RELOC);
335 btrfs_set_header_owner(cow, root->root_key.objectid);
337 write_extent_buffer(cow, root->fs_info->fsid,
338 (unsigned long)btrfs_header_fsid(cow),
341 WARN_ON(btrfs_header_generation(buf) > trans->transid);
343 update_ref_for_cow(trans, root, buf, cow);
345 if (buf == root->node) {
347 extent_buffer_get(cow);
349 btrfs_free_extent(trans, root, buf->start, buf->len,
350 0, root->root_key.objectid, level, 0);
351 free_extent_buffer(buf);
352 add_root_to_dirty_list(root);
354 btrfs_set_node_blockptr(parent, parent_slot,
356 WARN_ON(trans->transid == 0);
357 btrfs_set_node_ptr_generation(parent, parent_slot,
359 btrfs_mark_buffer_dirty(parent);
360 WARN_ON(btrfs_header_generation(parent) != trans->transid);
362 btrfs_free_extent(trans, root, buf->start, buf->len,
363 0, root->root_key.objectid, level, 1);
365 free_extent_buffer(buf);
366 btrfs_mark_buffer_dirty(cow);
371 static inline int should_cow_block(struct btrfs_trans_handle *trans,
372 struct btrfs_root *root,
373 struct extent_buffer *buf)
375 if (btrfs_header_generation(buf) == trans->transid &&
376 !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN) &&
377 !(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
378 btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC)))
383 int btrfs_cow_block(struct btrfs_trans_handle *trans,
384 struct btrfs_root *root, struct extent_buffer *buf,
385 struct extent_buffer *parent, int parent_slot,
386 struct extent_buffer **cow_ret)
391 if (trans->transaction != root->fs_info->running_transaction) {
392 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
393 root->fs_info->running_transaction->transid);
397 if (trans->transid != root->fs_info->generation) {
398 printk(KERN_CRIT "trans %llu running %llu\n",
399 (unsigned long long)trans->transid,
400 (unsigned long long)root->fs_info->generation);
403 if (!should_cow_block(trans, root, buf)) {
408 search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
409 ret = __btrfs_cow_block(trans, root, buf, parent,
410 parent_slot, cow_ret, search_start, 0);
415 static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
417 if (blocknr < other && other - (blocknr + blocksize) < 32768)
419 if (blocknr > other && blocknr - (other + blocksize) < 32768)
426 * compare two keys in a memcmp fashion
428 int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
432 btrfs_disk_key_to_cpu(&k1, disk);
434 if (k1.objectid > k2->objectid)
436 if (k1.objectid < k2->objectid)
438 if (k1.type > k2->type)
440 if (k1.type < k2->type)
442 if (k1.offset > k2->offset)
444 if (k1.offset < k2->offset)
451 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
452 struct btrfs_root *root, struct extent_buffer *parent,
453 int start_slot, int cache_only, u64 *last_ret,
454 struct btrfs_key *progress)
456 struct extent_buffer *cur;
457 struct extent_buffer *tmp;
460 u64 search_start = *last_ret;
470 int progress_passed = 0;
471 struct btrfs_disk_key disk_key;
473 parent_level = btrfs_header_level(parent);
474 if (cache_only && parent_level != 1)
477 if (trans->transaction != root->fs_info->running_transaction) {
478 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
479 root->fs_info->running_transaction->transid);
482 if (trans->transid != root->fs_info->generation) {
483 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
484 root->fs_info->generation);
488 parent_nritems = btrfs_header_nritems(parent);
489 blocksize = btrfs_level_size(root, parent_level - 1);
490 end_slot = parent_nritems;
492 if (parent_nritems == 1)
495 for (i = start_slot; i < end_slot; i++) {
498 if (!parent->map_token) {
499 map_extent_buffer(parent,
500 btrfs_node_key_ptr_offset(i),
501 sizeof(struct btrfs_key_ptr),
502 &parent->map_token, &parent->kaddr,
503 &parent->map_start, &parent->map_len,
506 btrfs_node_key(parent, &disk_key, i);
507 if (!progress_passed && comp_keys(&disk_key, progress) < 0)
511 blocknr = btrfs_node_blockptr(parent, i);
512 gen = btrfs_node_ptr_generation(parent, i);
514 last_block = blocknr;
517 other = btrfs_node_blockptr(parent, i - 1);
518 close = close_blocks(blocknr, other, blocksize);
520 if (close && i < end_slot - 2) {
521 other = btrfs_node_blockptr(parent, i + 1);
522 close = close_blocks(blocknr, other, blocksize);
525 last_block = blocknr;
528 if (parent->map_token) {
529 unmap_extent_buffer(parent, parent->map_token,
531 parent->map_token = NULL;
534 cur = btrfs_find_tree_block(root, blocknr, blocksize);
536 uptodate = btrfs_buffer_uptodate(cur, gen);
539 if (!cur || !uptodate) {
541 free_extent_buffer(cur);
545 cur = read_tree_block(root, blocknr,
547 } else if (!uptodate) {
548 btrfs_read_buffer(cur, gen);
551 if (search_start == 0)
552 search_start = last_block;
554 err = __btrfs_cow_block(trans, root, cur, parent, i,
557 (end_slot - i) * blocksize));
559 free_extent_buffer(cur);
562 search_start = tmp->start;
563 last_block = tmp->start;
564 *last_ret = search_start;
565 if (parent_level == 1)
566 btrfs_clear_buffer_defrag(tmp);
567 free_extent_buffer(tmp);
569 if (parent->map_token) {
570 unmap_extent_buffer(parent, parent->map_token,
572 parent->map_token = NULL;
579 * The leaf data grows from end-to-front in the node.
580 * this returns the address of the start of the last item,
581 * which is the stop of the leaf data stack
583 static inline unsigned int leaf_data_end(struct btrfs_root *root,
584 struct extent_buffer *leaf)
586 u32 nr = btrfs_header_nritems(leaf);
588 return BTRFS_LEAF_DATA_SIZE(root);
589 return btrfs_item_offset_nr(leaf, nr - 1);
592 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
595 struct extent_buffer *parent = NULL;
596 struct extent_buffer *node = path->nodes[level];
597 struct btrfs_disk_key parent_key;
598 struct btrfs_disk_key node_key;
601 struct btrfs_key cpukey;
602 u32 nritems = btrfs_header_nritems(node);
604 if (path->nodes[level + 1])
605 parent = path->nodes[level + 1];
607 slot = path->slots[level];
608 BUG_ON(nritems == 0);
610 parent_slot = path->slots[level + 1];
611 btrfs_node_key(parent, &parent_key, parent_slot);
612 btrfs_node_key(node, &node_key, 0);
613 BUG_ON(memcmp(&parent_key, &node_key,
614 sizeof(struct btrfs_disk_key)));
615 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
616 btrfs_header_bytenr(node));
618 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
620 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
621 btrfs_node_key(node, &node_key, slot);
622 BUG_ON(btrfs_comp_keys(&node_key, &cpukey) <= 0);
624 if (slot < nritems - 1) {
625 btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
626 btrfs_node_key(node, &node_key, slot);
627 BUG_ON(btrfs_comp_keys(&node_key, &cpukey) >= 0);
632 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
635 struct extent_buffer *leaf = path->nodes[level];
636 struct extent_buffer *parent = NULL;
638 struct btrfs_key cpukey;
639 struct btrfs_disk_key parent_key;
640 struct btrfs_disk_key leaf_key;
641 int slot = path->slots[0];
643 u32 nritems = btrfs_header_nritems(leaf);
645 if (path->nodes[level + 1])
646 parent = path->nodes[level + 1];
652 parent_slot = path->slots[level + 1];
653 btrfs_node_key(parent, &parent_key, parent_slot);
654 btrfs_item_key(leaf, &leaf_key, 0);
656 BUG_ON(memcmp(&parent_key, &leaf_key,
657 sizeof(struct btrfs_disk_key)));
658 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
659 btrfs_header_bytenr(leaf));
662 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
663 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
664 btrfs_item_key(leaf, &leaf_key, i);
665 if (comp_keys(&leaf_key, &cpukey) >= 0) {
666 btrfs_print_leaf(root, leaf);
667 printk("slot %d offset bad key\n", i);
670 if (btrfs_item_offset_nr(leaf, i) !=
671 btrfs_item_end_nr(leaf, i + 1)) {
672 btrfs_print_leaf(root, leaf);
673 printk("slot %d offset bad\n", i);
677 if (btrfs_item_offset_nr(leaf, i) +
678 btrfs_item_size_nr(leaf, i) !=
679 BTRFS_LEAF_DATA_SIZE(root)) {
680 btrfs_print_leaf(root, leaf);
681 printk("slot %d first offset bad\n", i);
687 if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
688 btrfs_print_leaf(root, leaf);
689 printk("slot %d bad size \n", nritems - 1);
694 if (slot != 0 && slot < nritems - 1) {
695 btrfs_item_key(leaf, &leaf_key, slot);
696 btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
697 if (btrfs_comp_keys(&leaf_key, &cpukey) <= 0) {
698 btrfs_print_leaf(root, leaf);
699 printk("slot %d offset bad key\n", slot);
702 if (btrfs_item_offset_nr(leaf, slot - 1) !=
703 btrfs_item_end_nr(leaf, slot)) {
704 btrfs_print_leaf(root, leaf);
705 printk("slot %d offset bad\n", slot);
709 if (slot < nritems - 1) {
710 btrfs_item_key(leaf, &leaf_key, slot);
711 btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
712 BUG_ON(btrfs_comp_keys(&leaf_key, &cpukey) >= 0);
713 if (btrfs_item_offset_nr(leaf, slot) !=
714 btrfs_item_end_nr(leaf, slot + 1)) {
715 btrfs_print_leaf(root, leaf);
716 printk("slot %d offset bad\n", slot);
720 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
721 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
725 static int noinline check_block(struct btrfs_root *root,
726 struct btrfs_path *path, int level)
730 struct extent_buffer *buf = path->nodes[level];
732 if (memcmp_extent_buffer(buf, root->fs_info->fsid,
733 (unsigned long)btrfs_header_fsid(buf),
735 printk("warning bad block %Lu\n", buf->start);
740 return check_leaf(root, path, level);
741 return check_node(root, path, level);
745 * search for key in the extent_buffer. The items start at offset p,
746 * and they are item_size apart. There are 'max' items in p.
748 * the slot in the array is returned via slot, and it points to
749 * the place where you would insert key if it is not found in
752 * slot may point to max if the key is bigger than all of the keys
754 static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
755 int item_size, struct btrfs_key *key,
762 unsigned long offset;
763 struct btrfs_disk_key *tmp;
766 mid = (low + high) / 2;
767 offset = p + mid * item_size;
769 tmp = (struct btrfs_disk_key *)(eb->data + offset);
770 ret = btrfs_comp_keys(tmp, key);
786 * simple bin_search frontend that does the right thing for
789 static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
790 int level, int *slot)
793 return generic_bin_search(eb,
794 offsetof(struct btrfs_leaf, items),
795 sizeof(struct btrfs_item),
796 key, btrfs_header_nritems(eb),
799 return generic_bin_search(eb,
800 offsetof(struct btrfs_node, ptrs),
801 sizeof(struct btrfs_key_ptr),
802 key, btrfs_header_nritems(eb),
808 struct extent_buffer *read_node_slot(struct btrfs_root *root,
809 struct extent_buffer *parent, int slot)
811 int level = btrfs_header_level(parent);
814 if (slot >= btrfs_header_nritems(parent))
819 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
820 btrfs_level_size(root, level - 1),
821 btrfs_node_ptr_generation(parent, slot));
824 static int balance_level(struct btrfs_trans_handle *trans,
825 struct btrfs_root *root,
826 struct btrfs_path *path, int level)
828 struct extent_buffer *right = NULL;
829 struct extent_buffer *mid;
830 struct extent_buffer *left = NULL;
831 struct extent_buffer *parent = NULL;
835 int orig_slot = path->slots[level];
841 mid = path->nodes[level];
842 WARN_ON(btrfs_header_generation(mid) != trans->transid);
844 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
846 if (level < BTRFS_MAX_LEVEL - 1)
847 parent = path->nodes[level + 1];
848 pslot = path->slots[level + 1];
851 * deal with the case where there is only one pointer in the root
852 * by promoting the node below to a root
855 struct extent_buffer *child;
857 if (btrfs_header_nritems(mid) != 1)
860 /* promote the child to a root */
861 child = read_node_slot(root, mid, 0);
863 ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
867 add_root_to_dirty_list(root);
868 path->nodes[level] = NULL;
869 clean_tree_block(trans, root, mid);
870 wait_on_tree_block_writeback(root, mid);
871 /* once for the path */
872 free_extent_buffer(mid);
874 ret = btrfs_free_extent(trans, root, mid->start, mid->len,
875 0, root->root_key.objectid,
877 /* once for the root ptr */
878 free_extent_buffer(mid);
881 if (btrfs_header_nritems(mid) >
882 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
885 left = read_node_slot(root, parent, pslot - 1);
887 wret = btrfs_cow_block(trans, root, left,
888 parent, pslot - 1, &left);
894 right = read_node_slot(root, parent, pslot + 1);
896 wret = btrfs_cow_block(trans, root, right,
897 parent, pslot + 1, &right);
904 /* first, try to make some room in the middle buffer */
906 orig_slot += btrfs_header_nritems(left);
907 wret = push_node_left(trans, root, left, mid, 1);
913 * then try to empty the right most buffer into the middle
916 wret = push_node_left(trans, root, mid, right, 1);
917 if (wret < 0 && wret != -ENOSPC)
919 if (btrfs_header_nritems(right) == 0) {
920 u64 bytenr = right->start;
921 u32 blocksize = right->len;
923 clean_tree_block(trans, root, right);
924 wait_on_tree_block_writeback(root, right);
925 free_extent_buffer(right);
927 wret = del_ptr(trans, root, path, level + 1, pslot +
931 wret = btrfs_free_extent(trans, root, bytenr,
933 root->root_key.objectid,
938 struct btrfs_disk_key right_key;
939 btrfs_node_key(right, &right_key, 0);
940 btrfs_set_node_key(parent, &right_key, pslot + 1);
941 btrfs_mark_buffer_dirty(parent);
944 if (btrfs_header_nritems(mid) == 1) {
946 * we're not allowed to leave a node with one item in the
947 * tree during a delete. A deletion from lower in the tree
948 * could try to delete the only pointer in this node.
949 * So, pull some keys from the left.
950 * There has to be a left pointer at this point because
951 * otherwise we would have pulled some pointers from the
955 wret = balance_node_right(trans, root, mid, left);
961 wret = push_node_left(trans, root, left, mid, 1);
967 if (btrfs_header_nritems(mid) == 0) {
968 /* we've managed to empty the middle node, drop it */
969 u64 bytenr = mid->start;
970 u32 blocksize = mid->len;
971 clean_tree_block(trans, root, mid);
972 wait_on_tree_block_writeback(root, mid);
973 free_extent_buffer(mid);
975 wret = del_ptr(trans, root, path, level + 1, pslot);
978 wret = btrfs_free_extent(trans, root, bytenr, blocksize,
979 0, root->root_key.objectid,
984 /* update the parent key to reflect our changes */
985 struct btrfs_disk_key mid_key;
986 btrfs_node_key(mid, &mid_key, 0);
987 btrfs_set_node_key(parent, &mid_key, pslot);
988 btrfs_mark_buffer_dirty(parent);
991 /* update the path */
993 if (btrfs_header_nritems(left) > orig_slot) {
994 extent_buffer_get(left);
995 path->nodes[level] = left;
996 path->slots[level + 1] -= 1;
997 path->slots[level] = orig_slot;
999 free_extent_buffer(mid);
1001 orig_slot -= btrfs_header_nritems(left);
1002 path->slots[level] = orig_slot;
1005 /* double check we haven't messed things up */
1006 check_block(root, path, level);
1008 btrfs_node_blockptr(path->nodes[level], path->slots[level]))
1012 free_extent_buffer(right);
1014 free_extent_buffer(left);
1018 /* returns zero if the push worked, non-zero otherwise */
1019 static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
1020 struct btrfs_root *root,
1021 struct btrfs_path *path, int level)
1023 struct extent_buffer *right = NULL;
1024 struct extent_buffer *mid;
1025 struct extent_buffer *left = NULL;
1026 struct extent_buffer *parent = NULL;
1030 int orig_slot = path->slots[level];
1035 mid = path->nodes[level];
1036 WARN_ON(btrfs_header_generation(mid) != trans->transid);
1038 if (level < BTRFS_MAX_LEVEL - 1)
1039 parent = path->nodes[level + 1];
1040 pslot = path->slots[level + 1];
1045 left = read_node_slot(root, parent, pslot - 1);
1047 /* first, try to make some room in the middle buffer */
1050 left_nr = btrfs_header_nritems(left);
1051 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1054 ret = btrfs_cow_block(trans, root, left, parent,
1059 wret = push_node_left(trans, root,
1066 struct btrfs_disk_key disk_key;
1067 orig_slot += left_nr;
1068 btrfs_node_key(mid, &disk_key, 0);
1069 btrfs_set_node_key(parent, &disk_key, pslot);
1070 btrfs_mark_buffer_dirty(parent);
1071 if (btrfs_header_nritems(left) > orig_slot) {
1072 path->nodes[level] = left;
1073 path->slots[level + 1] -= 1;
1074 path->slots[level] = orig_slot;
1075 free_extent_buffer(mid);
1078 btrfs_header_nritems(left);
1079 path->slots[level] = orig_slot;
1080 free_extent_buffer(left);
1084 free_extent_buffer(left);
1086 right= read_node_slot(root, parent, pslot + 1);
1089 * then try to empty the right most buffer into the middle
1093 right_nr = btrfs_header_nritems(right);
1094 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
1097 ret = btrfs_cow_block(trans, root, right,
1103 wret = balance_node_right(trans, root,
1110 struct btrfs_disk_key disk_key;
1112 btrfs_node_key(right, &disk_key, 0);
1113 btrfs_set_node_key(parent, &disk_key, pslot + 1);
1114 btrfs_mark_buffer_dirty(parent);
1116 if (btrfs_header_nritems(mid) <= orig_slot) {
1117 path->nodes[level] = right;
1118 path->slots[level + 1] += 1;
1119 path->slots[level] = orig_slot -
1120 btrfs_header_nritems(mid);
1121 free_extent_buffer(mid);
1123 free_extent_buffer(right);
1127 free_extent_buffer(right);
1133 * readahead one full node of leaves
1135 void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
1136 int level, int slot, u64 objectid)
1138 struct extent_buffer *node;
1139 struct btrfs_disk_key disk_key;
1145 int direction = path->reada;
1146 struct extent_buffer *eb;
1154 if (!path->nodes[level])
1157 node = path->nodes[level];
1158 search = btrfs_node_blockptr(node, slot);
1159 blocksize = btrfs_level_size(root, level - 1);
1160 eb = btrfs_find_tree_block(root, search, blocksize);
1162 free_extent_buffer(eb);
1166 highest_read = search;
1167 lowest_read = search;
1169 nritems = btrfs_header_nritems(node);
1172 if (direction < 0) {
1176 } else if (direction > 0) {
1181 if (path->reada < 0 && objectid) {
1182 btrfs_node_key(node, &disk_key, nr);
1183 if (btrfs_disk_key_objectid(&disk_key) != objectid)
1186 search = btrfs_node_blockptr(node, nr);
1187 if ((search >= lowest_read && search <= highest_read) ||
1188 (search < lowest_read && lowest_read - search <= 32768) ||
1189 (search > highest_read && search - highest_read <= 32768)) {
1190 readahead_tree_block(root, search, blocksize,
1191 btrfs_node_ptr_generation(node, nr));
1195 if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
1197 if(nread > (1024 * 1024) || nscan > 128)
1200 if (search < lowest_read)
1201 lowest_read = search;
1202 if (search > highest_read)
1203 highest_read = search;
1208 * look for key in the tree. path is filled in with nodes along the way
1209 * if key is found, we return zero and you can find the item in the leaf
1210 * level of the path (level 0)
1212 * If the key isn't found, the path points to the slot where it should
1213 * be inserted, and 1 is returned. If there are other errors during the
1214 * search a negative error number is returned.
1216 * if ins_len > 0, nodes and leaves will be split as we walk down the
1217 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1220 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1221 *root, struct btrfs_key *key, struct btrfs_path *p, int
1224 struct extent_buffer *b;
1228 int should_reada = p->reada;
1229 u8 lowest_level = 0;
1231 lowest_level = p->lowest_level;
1232 WARN_ON(lowest_level && ins_len > 0);
1233 WARN_ON(p->nodes[0] != NULL);
1235 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
1239 extent_buffer_get(b);
1241 level = btrfs_header_level(b);
1244 wret = btrfs_cow_block(trans, root, b,
1245 p->nodes[level + 1],
1246 p->slots[level + 1],
1249 free_extent_buffer(b);
1253 BUG_ON(!cow && ins_len);
1254 if (level != btrfs_header_level(b))
1256 level = btrfs_header_level(b);
1257 p->nodes[level] = b;
1258 ret = check_block(root, p, level);
1261 ret = bin_search(b, key, level, &slot);
1263 if (ret && slot > 0)
1265 p->slots[level] = slot;
1266 if ((p->search_for_split || ins_len > 0) &&
1267 btrfs_header_nritems(b) >=
1268 BTRFS_NODEPTRS_PER_BLOCK(root) - 3) {
1269 int sret = split_node(trans, root, p, level);
1273 b = p->nodes[level];
1274 slot = p->slots[level];
1275 } else if (ins_len < 0) {
1276 int sret = balance_level(trans, root, p,
1280 b = p->nodes[level];
1282 btrfs_release_path(NULL, p);
1285 slot = p->slots[level];
1286 BUG_ON(btrfs_header_nritems(b) == 1);
1288 /* this is only true while dropping a snapshot */
1289 if (level == lowest_level)
1293 reada_for_search(root, p, level, slot,
1296 b = read_node_slot(root, b, slot);
1298 p->slots[level] = slot;
1300 ins_len > btrfs_leaf_free_space(root, b)) {
1301 int sret = split_leaf(trans, root, key,
1302 p, ins_len, ret == 0);
1314 * adjust the pointers going up the tree, starting at level
1315 * making sure the right key of each node is points to 'key'.
1316 * This is used after shifting pointers to the left, so it stops
1317 * fixing up pointers when a given leaf/node is not in slot 0 of the
1320 * If this fails to write a tree block, it returns -1, but continues
1321 * fixing up the blocks in ram so the tree is consistent.
1323 static int fixup_low_keys(struct btrfs_trans_handle *trans,
1324 struct btrfs_root *root, struct btrfs_path *path,
1325 struct btrfs_disk_key *key, int level)
1329 struct extent_buffer *t;
1331 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1332 int tslot = path->slots[i];
1333 if (!path->nodes[i])
1336 btrfs_set_node_key(t, key, tslot);
1337 btrfs_mark_buffer_dirty(path->nodes[i]);
1347 * This function isn't completely safe. It's the caller's responsibility
1348 * that the new key won't break the order
1350 int btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
1351 struct btrfs_root *root, struct btrfs_path *path,
1352 struct btrfs_key *new_key)
1354 struct btrfs_disk_key disk_key;
1355 struct extent_buffer *eb;
1358 eb = path->nodes[0];
1359 slot = path->slots[0];
1361 btrfs_item_key(eb, &disk_key, slot - 1);
1362 if (btrfs_comp_keys(&disk_key, new_key) >= 0)
1365 if (slot < btrfs_header_nritems(eb) - 1) {
1366 btrfs_item_key(eb, &disk_key, slot + 1);
1367 if (btrfs_comp_keys(&disk_key, new_key) <= 0)
1371 btrfs_cpu_key_to_disk(&disk_key, new_key);
1372 btrfs_set_item_key(eb, &disk_key, slot);
1373 btrfs_mark_buffer_dirty(eb);
1375 fixup_low_keys(trans, root, path, &disk_key, 1);
1380 * try to push data from one node into the next node left in the
1383 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1384 * error, and > 0 if there was no room in the left hand block.
1386 static int push_node_left(struct btrfs_trans_handle *trans,
1387 struct btrfs_root *root, struct extent_buffer *dst,
1388 struct extent_buffer *src, int empty)
1395 src_nritems = btrfs_header_nritems(src);
1396 dst_nritems = btrfs_header_nritems(dst);
1397 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1398 WARN_ON(btrfs_header_generation(src) != trans->transid);
1399 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1401 if (!empty && src_nritems <= 8)
1404 if (push_items <= 0) {
1409 push_items = min(src_nritems, push_items);
1410 if (push_items < src_nritems) {
1411 /* leave at least 8 pointers in the node if
1412 * we aren't going to empty it
1414 if (src_nritems - push_items < 8) {
1415 if (push_items <= 8)
1421 push_items = min(src_nritems - 8, push_items);
1423 copy_extent_buffer(dst, src,
1424 btrfs_node_key_ptr_offset(dst_nritems),
1425 btrfs_node_key_ptr_offset(0),
1426 push_items * sizeof(struct btrfs_key_ptr));
1428 if (push_items < src_nritems) {
1429 memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
1430 btrfs_node_key_ptr_offset(push_items),
1431 (src_nritems - push_items) *
1432 sizeof(struct btrfs_key_ptr));
1434 btrfs_set_header_nritems(src, src_nritems - push_items);
1435 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1436 btrfs_mark_buffer_dirty(src);
1437 btrfs_mark_buffer_dirty(dst);
1443 * try to push data from one node into the next node right in the
1446 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1447 * error, and > 0 if there was no room in the right hand block.
1449 * this will only push up to 1/2 the contents of the left node over
1451 static int balance_node_right(struct btrfs_trans_handle *trans,
1452 struct btrfs_root *root,
1453 struct extent_buffer *dst,
1454 struct extent_buffer *src)
1462 WARN_ON(btrfs_header_generation(src) != trans->transid);
1463 WARN_ON(btrfs_header_generation(dst) != trans->transid);
1465 src_nritems = btrfs_header_nritems(src);
1466 dst_nritems = btrfs_header_nritems(dst);
1467 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1468 if (push_items <= 0) {
1472 if (src_nritems < 4) {
1476 max_push = src_nritems / 2 + 1;
1477 /* don't try to empty the node */
1478 if (max_push >= src_nritems) {
1482 if (max_push < push_items)
1483 push_items = max_push;
1485 memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
1486 btrfs_node_key_ptr_offset(0),
1488 sizeof(struct btrfs_key_ptr));
1490 copy_extent_buffer(dst, src,
1491 btrfs_node_key_ptr_offset(0),
1492 btrfs_node_key_ptr_offset(src_nritems - push_items),
1493 push_items * sizeof(struct btrfs_key_ptr));
1495 btrfs_set_header_nritems(src, src_nritems - push_items);
1496 btrfs_set_header_nritems(dst, dst_nritems + push_items);
1498 btrfs_mark_buffer_dirty(src);
1499 btrfs_mark_buffer_dirty(dst);
1505 * helper function to insert a new root level in the tree.
1506 * A new node is allocated, and a single item is inserted to
1507 * point to the existing root
1509 * returns zero on success or < 0 on failure.
1511 static int noinline insert_new_root(struct btrfs_trans_handle *trans,
1512 struct btrfs_root *root,
1513 struct btrfs_path *path, int level)
1516 struct extent_buffer *lower;
1517 struct extent_buffer *c;
1518 struct extent_buffer *old;
1519 struct btrfs_disk_key lower_key;
1521 BUG_ON(path->nodes[level]);
1522 BUG_ON(path->nodes[level-1] != root->node);
1524 lower = path->nodes[level-1];
1526 btrfs_item_key(lower, &lower_key, 0);
1528 btrfs_node_key(lower, &lower_key, 0);
1530 c = btrfs_alloc_free_block(trans, root, root->nodesize,
1531 root->root_key.objectid, &lower_key,
1532 level, root->node->start, 0);
1537 memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
1538 btrfs_set_header_nritems(c, 1);
1539 btrfs_set_header_level(c, level);
1540 btrfs_set_header_bytenr(c, c->start);
1541 btrfs_set_header_generation(c, trans->transid);
1542 btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
1543 btrfs_set_header_owner(c, root->root_key.objectid);
1545 write_extent_buffer(c, root->fs_info->fsid,
1546 (unsigned long)btrfs_header_fsid(c),
1549 write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
1550 (unsigned long)btrfs_header_chunk_tree_uuid(c),
1553 btrfs_set_node_key(c, &lower_key, 0);
1554 btrfs_set_node_blockptr(c, 0, lower->start);
1555 lower_gen = btrfs_header_generation(lower);
1556 WARN_ON(lower_gen != trans->transid);
1558 btrfs_set_node_ptr_generation(c, 0, lower_gen);
1560 btrfs_mark_buffer_dirty(c);
1565 /* the super has an extra ref to root->node */
1566 free_extent_buffer(old);
1568 add_root_to_dirty_list(root);
1569 extent_buffer_get(c);
1570 path->nodes[level] = c;
1571 path->slots[level] = 0;
1576 * worker function to insert a single pointer in a node.
1577 * the node should have enough room for the pointer already
1579 * slot and level indicate where you want the key to go, and
1580 * blocknr is the block the key points to.
1582 * returns zero on success and < 0 on any error
1584 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1585 *root, struct btrfs_path *path, struct btrfs_disk_key
1586 *key, u64 bytenr, int slot, int level)
1588 struct extent_buffer *lower;
1591 BUG_ON(!path->nodes[level]);
1592 lower = path->nodes[level];
1593 nritems = btrfs_header_nritems(lower);
1596 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1598 if (slot != nritems) {
1599 memmove_extent_buffer(lower,
1600 btrfs_node_key_ptr_offset(slot + 1),
1601 btrfs_node_key_ptr_offset(slot),
1602 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1604 btrfs_set_node_key(lower, key, slot);
1605 btrfs_set_node_blockptr(lower, slot, bytenr);
1606 WARN_ON(trans->transid == 0);
1607 btrfs_set_node_ptr_generation(lower, slot, trans->transid);
1608 btrfs_set_header_nritems(lower, nritems + 1);
1609 btrfs_mark_buffer_dirty(lower);
1614 * split the node at the specified level in path in two.
1615 * The path is corrected to point to the appropriate node after the split
1617 * Before splitting this tries to make some room in the node by pushing
1618 * left and right, if either one works, it returns right away.
1620 * returns 0 on success and < 0 on failure
1622 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1623 *root, struct btrfs_path *path, int level)
1625 struct extent_buffer *c;
1626 struct extent_buffer *split;
1627 struct btrfs_disk_key disk_key;
1633 c = path->nodes[level];
1634 WARN_ON(btrfs_header_generation(c) != trans->transid);
1635 if (c == root->node) {
1636 /* trying to split the root, lets make a new one */
1637 ret = insert_new_root(trans, root, path, level + 1);
1641 ret = push_nodes_for_insert(trans, root, path, level);
1642 c = path->nodes[level];
1643 if (!ret && btrfs_header_nritems(c) <
1644 BTRFS_NODEPTRS_PER_BLOCK(root) - 3)
1650 c_nritems = btrfs_header_nritems(c);
1651 mid = (c_nritems + 1) / 2;
1652 btrfs_node_key(c, &disk_key, mid);
1654 split = btrfs_alloc_free_block(trans, root, root->nodesize,
1655 root->root_key.objectid,
1656 &disk_key, level, c->start, 0);
1658 return PTR_ERR(split);
1660 memset_extent_buffer(split, 0, 0, sizeof(struct btrfs_header));
1661 btrfs_set_header_level(split, btrfs_header_level(c));
1662 btrfs_set_header_bytenr(split, split->start);
1663 btrfs_set_header_generation(split, trans->transid);
1664 btrfs_set_header_backref_rev(split, BTRFS_MIXED_BACKREF_REV);
1665 btrfs_set_header_owner(split, root->root_key.objectid);
1666 write_extent_buffer(split, root->fs_info->fsid,
1667 (unsigned long)btrfs_header_fsid(split),
1669 write_extent_buffer(split, root->fs_info->chunk_tree_uuid,
1670 (unsigned long)btrfs_header_chunk_tree_uuid(split),
1674 copy_extent_buffer(split, c,
1675 btrfs_node_key_ptr_offset(0),
1676 btrfs_node_key_ptr_offset(mid),
1677 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1678 btrfs_set_header_nritems(split, c_nritems - mid);
1679 btrfs_set_header_nritems(c, mid);
1682 btrfs_mark_buffer_dirty(c);
1683 btrfs_mark_buffer_dirty(split);
1685 wret = insert_ptr(trans, root, path, &disk_key, split->start,
1686 path->slots[level + 1] + 1,
1691 if (path->slots[level] >= mid) {
1692 path->slots[level] -= mid;
1693 free_extent_buffer(c);
1694 path->nodes[level] = split;
1695 path->slots[level + 1] += 1;
1697 free_extent_buffer(split);
1703 * how many bytes are required to store the items in a leaf. start
1704 * and nr indicate which items in the leaf to check. This totals up the
1705 * space used both by the item structs and the item data
1707 static int leaf_space_used(struct extent_buffer *l, int start, int nr)
1710 int nritems = btrfs_header_nritems(l);
1711 int end = min(nritems, start + nr) - 1;
1715 data_len = btrfs_item_end_nr(l, start);
1716 data_len = data_len - btrfs_item_offset_nr(l, end);
1717 data_len += sizeof(struct btrfs_item) * nr;
1718 WARN_ON(data_len < 0);
1723 * The space between the end of the leaf items and
1724 * the start of the leaf data. IOW, how much room
1725 * the leaf has left for both items and data
1727 int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
1729 int nritems = btrfs_header_nritems(leaf);
1731 ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1733 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1734 ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
1735 leaf_space_used(leaf, 0, nritems), nritems);
1741 * push some data in the path leaf to the right, trying to free up at
1742 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1744 * returns 1 if the push failed because the other node didn't have enough
1745 * room, 0 if everything worked out and < 0 if there were major errors.
1747 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1748 *root, struct btrfs_path *path, int data_size,
1751 struct extent_buffer *left = path->nodes[0];
1752 struct extent_buffer *right;
1753 struct extent_buffer *upper;
1754 struct btrfs_disk_key disk_key;
1760 struct btrfs_item *item;
1768 slot = path->slots[1];
1769 if (!path->nodes[1]) {
1772 upper = path->nodes[1];
1773 if (slot >= btrfs_header_nritems(upper) - 1)
1776 right = read_node_slot(root, upper, slot + 1);
1777 free_space = btrfs_leaf_free_space(root, right);
1778 if (free_space < data_size) {
1779 free_extent_buffer(right);
1783 /* cow and double check */
1784 ret = btrfs_cow_block(trans, root, right, upper,
1787 free_extent_buffer(right);
1790 free_space = btrfs_leaf_free_space(root, right);
1791 if (free_space < data_size) {
1792 free_extent_buffer(right);
1796 left_nritems = btrfs_header_nritems(left);
1797 if (left_nritems == 0) {
1798 free_extent_buffer(right);
1807 i = left_nritems - 1;
1809 item = btrfs_item_nr(left, i);
1811 if (path->slots[0] == i)
1812 push_space += data_size + sizeof(*item);
1814 this_item_size = btrfs_item_size(left, item);
1815 if (this_item_size + sizeof(*item) + push_space > free_space)
1818 push_space += this_item_size + sizeof(*item);
1824 if (push_items == 0) {
1825 free_extent_buffer(right);
1829 if (!empty && push_items == left_nritems)
1832 /* push left to right */
1833 right_nritems = btrfs_header_nritems(right);
1835 push_space = btrfs_item_end_nr(left, left_nritems - push_items);
1836 push_space -= leaf_data_end(root, left);
1838 /* make room in the right data area */
1839 data_end = leaf_data_end(root, right);
1840 memmove_extent_buffer(right,
1841 btrfs_leaf_data(right) + data_end - push_space,
1842 btrfs_leaf_data(right) + data_end,
1843 BTRFS_LEAF_DATA_SIZE(root) - data_end);
1845 /* copy from the left data area */
1846 copy_extent_buffer(right, left, btrfs_leaf_data(right) +
1847 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1848 btrfs_leaf_data(left) + leaf_data_end(root, left),
1851 memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
1852 btrfs_item_nr_offset(0),
1853 right_nritems * sizeof(struct btrfs_item));
1855 /* copy the items from left to right */
1856 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1857 btrfs_item_nr_offset(left_nritems - push_items),
1858 push_items * sizeof(struct btrfs_item));
1860 /* update the item pointers */
1861 right_nritems += push_items;
1862 btrfs_set_header_nritems(right, right_nritems);
1863 push_space = BTRFS_LEAF_DATA_SIZE(root);
1864 for (i = 0; i < right_nritems; i++) {
1865 item = btrfs_item_nr(right, i);
1866 push_space -= btrfs_item_size(right, item);
1867 btrfs_set_item_offset(right, item, push_space);
1870 left_nritems -= push_items;
1871 btrfs_set_header_nritems(left, left_nritems);
1874 btrfs_mark_buffer_dirty(left);
1875 btrfs_mark_buffer_dirty(right);
1877 btrfs_item_key(right, &disk_key, 0);
1878 btrfs_set_node_key(upper, &disk_key, slot + 1);
1879 btrfs_mark_buffer_dirty(upper);
1881 /* then fixup the leaf pointer in the path */
1882 if (path->slots[0] >= left_nritems) {
1883 path->slots[0] -= left_nritems;
1884 free_extent_buffer(path->nodes[0]);
1885 path->nodes[0] = right;
1886 path->slots[1] += 1;
1888 free_extent_buffer(right);
1893 * push some data in the path leaf to the left, trying to free up at
1894 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1896 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1897 *root, struct btrfs_path *path, int data_size,
1900 struct btrfs_disk_key disk_key;
1901 struct extent_buffer *right = path->nodes[0];
1902 struct extent_buffer *left;
1908 struct btrfs_item *item;
1909 u32 old_left_nritems;
1915 u32 old_left_item_size;
1917 slot = path->slots[1];
1920 if (!path->nodes[1])
1923 right_nritems = btrfs_header_nritems(right);
1924 if (right_nritems == 0) {
1928 left = read_node_slot(root, path->nodes[1], slot - 1);
1929 free_space = btrfs_leaf_free_space(root, left);
1930 if (free_space < data_size) {
1931 free_extent_buffer(left);
1935 /* cow and double check */
1936 ret = btrfs_cow_block(trans, root, left,
1937 path->nodes[1], slot - 1, &left);
1939 /* we hit -ENOSPC, but it isn't fatal here */
1940 free_extent_buffer(left);
1944 free_space = btrfs_leaf_free_space(root, left);
1945 if (free_space < data_size) {
1946 free_extent_buffer(left);
1953 nr = right_nritems - 1;
1955 for (i = 0; i < nr; i++) {
1956 item = btrfs_item_nr(right, i);
1958 if (path->slots[0] == i)
1959 push_space += data_size + sizeof(*item);
1961 this_item_size = btrfs_item_size(right, item);
1962 if (this_item_size + sizeof(*item) + push_space > free_space)
1966 push_space += this_item_size + sizeof(*item);
1969 if (push_items == 0) {
1970 free_extent_buffer(left);
1973 if (!empty && push_items == btrfs_header_nritems(right))
1976 /* push data from right to left */
1977 copy_extent_buffer(left, right,
1978 btrfs_item_nr_offset(btrfs_header_nritems(left)),
1979 btrfs_item_nr_offset(0),
1980 push_items * sizeof(struct btrfs_item));
1982 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1983 btrfs_item_offset_nr(right, push_items -1);
1985 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1986 leaf_data_end(root, left) - push_space,
1987 btrfs_leaf_data(right) +
1988 btrfs_item_offset_nr(right, push_items - 1),
1990 old_left_nritems = btrfs_header_nritems(left);
1991 BUG_ON(old_left_nritems < 0);
1993 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1994 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1997 item = btrfs_item_nr(left, i);
1998 ioff = btrfs_item_offset(left, item);
1999 btrfs_set_item_offset(left, item,
2000 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
2002 btrfs_set_header_nritems(left, old_left_nritems + push_items);
2004 /* fixup right node */
2005 if (push_items > right_nritems) {
2006 printk("push items %d nr %u\n", push_items, right_nritems);
2010 if (push_items < right_nritems) {
2011 push_space = btrfs_item_offset_nr(right, push_items - 1) -
2012 leaf_data_end(root, right);
2013 memmove_extent_buffer(right, btrfs_leaf_data(right) +
2014 BTRFS_LEAF_DATA_SIZE(root) - push_space,
2015 btrfs_leaf_data(right) +
2016 leaf_data_end(root, right), push_space);
2018 memmove_extent_buffer(right, btrfs_item_nr_offset(0),
2019 btrfs_item_nr_offset(push_items),
2020 (btrfs_header_nritems(right) - push_items) *
2021 sizeof(struct btrfs_item));
2023 right_nritems -= push_items;
2024 btrfs_set_header_nritems(right, right_nritems);
2025 push_space = BTRFS_LEAF_DATA_SIZE(root);
2026 for (i = 0; i < right_nritems; i++) {
2027 item = btrfs_item_nr(right, i);
2028 push_space = push_space - btrfs_item_size(right, item);
2029 btrfs_set_item_offset(right, item, push_space);
2032 btrfs_mark_buffer_dirty(left);
2034 btrfs_mark_buffer_dirty(right);
2036 btrfs_item_key(right, &disk_key, 0);
2037 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
2041 /* then fixup the leaf pointer in the path */
2042 if (path->slots[0] < push_items) {
2043 path->slots[0] += old_left_nritems;
2044 free_extent_buffer(path->nodes[0]);
2045 path->nodes[0] = left;
2046 path->slots[1] -= 1;
2048 free_extent_buffer(left);
2049 path->slots[0] -= push_items;
2051 BUG_ON(path->slots[0] < 0);
2056 * split the path's leaf in two, making sure there is at least data_size
2057 * available for the resulting leaf level of the path.
2059 * returns 0 if all went well and < 0 on failure.
2061 static noinline int copy_for_split(struct btrfs_trans_handle *trans,
2062 struct btrfs_root *root,
2063 struct btrfs_path *path,
2064 struct extent_buffer *l,
2065 struct extent_buffer *right,
2066 int slot, int mid, int nritems)
2073 struct btrfs_disk_key disk_key;
2075 nritems = nritems - mid;
2076 btrfs_set_header_nritems(right, nritems);
2077 data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
2079 copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
2080 btrfs_item_nr_offset(mid),
2081 nritems * sizeof(struct btrfs_item));
2083 copy_extent_buffer(right, l,
2084 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
2085 data_copy_size, btrfs_leaf_data(l) +
2086 leaf_data_end(root, l), data_copy_size);
2088 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
2089 btrfs_item_end_nr(l, mid);
2091 for (i = 0; i < nritems; i++) {
2092 struct btrfs_item *item = btrfs_item_nr(right, i);
2093 u32 ioff = btrfs_item_offset(right, item);
2094 btrfs_set_item_offset(right, item, ioff + rt_data_off);
2097 btrfs_set_header_nritems(l, mid);
2099 btrfs_item_key(right, &disk_key, 0);
2100 wret = insert_ptr(trans, root, path, &disk_key, right->start,
2101 path->slots[1] + 1, 1);
2105 btrfs_mark_buffer_dirty(right);
2106 btrfs_mark_buffer_dirty(l);
2107 BUG_ON(path->slots[0] != slot);
2110 free_extent_buffer(path->nodes[0]);
2111 path->nodes[0] = right;
2112 path->slots[0] -= mid;
2113 path->slots[1] += 1;
2115 free_extent_buffer(right);
2118 BUG_ON(path->slots[0] < 0);
2124 * split the path's leaf in two, making sure there is at least data_size
2125 * available for the resulting leaf level of the path.
2127 * returns 0 if all went well and < 0 on failure.
2129 static noinline int split_leaf(struct btrfs_trans_handle *trans,
2130 struct btrfs_root *root,
2131 struct btrfs_key *ins_key,
2132 struct btrfs_path *path, int data_size,
2135 struct btrfs_disk_key disk_key;
2136 struct extent_buffer *l;
2140 struct extent_buffer *right;
2144 int num_doubles = 0;
2146 /* first try to make some room by pushing left and right */
2147 if (data_size && ins_key->type != BTRFS_DIR_ITEM_KEY) {
2148 wret = push_leaf_right(trans, root, path, data_size, 0);
2152 wret = push_leaf_left(trans, root, path, data_size, 0);
2158 /* did the pushes work? */
2159 if (btrfs_leaf_free_space(root, l) >= data_size)
2163 if (!path->nodes[1]) {
2164 ret = insert_new_root(trans, root, path, 1);
2171 slot = path->slots[0];
2172 nritems = btrfs_header_nritems(l);
2173 mid = (nritems + 1) / 2;
2177 leaf_space_used(l, mid, nritems - mid) + data_size >
2178 BTRFS_LEAF_DATA_SIZE(root)) {
2179 if (slot >= nritems) {
2183 if (mid != nritems &&
2184 leaf_space_used(l, mid, nritems - mid) +
2185 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2191 if (leaf_space_used(l, 0, mid) + data_size >
2192 BTRFS_LEAF_DATA_SIZE(root)) {
2193 if (!extend && data_size && slot == 0) {
2195 } else if ((extend || !data_size) && slot == 0) {
2199 if (mid != nritems &&
2200 leaf_space_used(l, mid, nritems - mid) +
2201 data_size > BTRFS_LEAF_DATA_SIZE(root)) {
2209 btrfs_cpu_key_to_disk(&disk_key, ins_key);
2211 btrfs_item_key(l, &disk_key, mid);
2213 right = btrfs_alloc_free_block(trans, root, root->leafsize,
2214 root->root_key.objectid,
2215 &disk_key, 0, l->start, 0);
2216 if (IS_ERR(right)) {
2218 return PTR_ERR(right);
2221 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
2222 btrfs_set_header_bytenr(right, right->start);
2223 btrfs_set_header_generation(right, trans->transid);
2224 btrfs_set_header_backref_rev(right, BTRFS_MIXED_BACKREF_REV);
2225 btrfs_set_header_owner(right, root->root_key.objectid);
2226 btrfs_set_header_level(right, 0);
2227 write_extent_buffer(right, root->fs_info->fsid,
2228 (unsigned long)btrfs_header_fsid(right),
2231 write_extent_buffer(right, root->fs_info->chunk_tree_uuid,
2232 (unsigned long)btrfs_header_chunk_tree_uuid(right),
2237 btrfs_set_header_nritems(right, 0);
2238 wret = insert_ptr(trans, root, path,
2239 &disk_key, right->start,
2240 path->slots[1] + 1, 1);
2244 free_extent_buffer(path->nodes[0]);
2245 path->nodes[0] = right;
2247 path->slots[1] += 1;
2249 btrfs_set_header_nritems(right, 0);
2250 wret = insert_ptr(trans, root, path,
2256 free_extent_buffer(path->nodes[0]);
2257 path->nodes[0] = right;
2259 if (path->slots[1] == 0) {
2260 wret = fixup_low_keys(trans, root,
2261 path, &disk_key, 1);
2266 btrfs_mark_buffer_dirty(right);
2270 ret = copy_for_split(trans, root, path, l, right, slot, mid, nritems);
2274 BUG_ON(num_doubles != 0);
2283 * This function splits a single item into two items,
2284 * giving 'new_key' to the new item and splitting the
2285 * old one at split_offset (from the start of the item).
2287 * The path may be released by this operation. After
2288 * the split, the path is pointing to the old item. The
2289 * new item is going to be in the same node as the old one.
2291 * Note, the item being split must be smaller enough to live alone on
2292 * a tree block with room for one extra struct btrfs_item
2294 * This allows us to split the item in place, keeping a lock on the
2295 * leaf the entire time.
2297 int btrfs_split_item(struct btrfs_trans_handle *trans,
2298 struct btrfs_root *root,
2299 struct btrfs_path *path,
2300 struct btrfs_key *new_key,
2301 unsigned long split_offset)
2304 struct extent_buffer *leaf;
2305 struct btrfs_key orig_key;
2306 struct btrfs_item *item;
2307 struct btrfs_item *new_item;
2312 struct btrfs_disk_key disk_key;
2315 leaf = path->nodes[0];
2316 btrfs_item_key_to_cpu(leaf, &orig_key, path->slots[0]);
2317 if (btrfs_leaf_free_space(root, leaf) >= sizeof(struct btrfs_item))
2320 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2321 btrfs_release_path(root, path);
2323 path->search_for_split = 1;
2325 ret = btrfs_search_slot(trans, root, &orig_key, path, 0, 1);
2326 path->search_for_split = 0;
2328 /* if our item isn't there or got smaller, return now */
2329 if (ret != 0 || item_size != btrfs_item_size_nr(path->nodes[0],
2334 ret = split_leaf(trans, root, &orig_key, path, 0, 0);
2337 BUG_ON(btrfs_leaf_free_space(root, leaf) < sizeof(struct btrfs_item));
2338 leaf = path->nodes[0];
2341 item = btrfs_item_nr(leaf, path->slots[0]);
2342 orig_offset = btrfs_item_offset(leaf, item);
2343 item_size = btrfs_item_size(leaf, item);
2346 buf = kmalloc(item_size, GFP_NOFS);
2347 read_extent_buffer(leaf, buf, btrfs_item_ptr_offset(leaf,
2348 path->slots[0]), item_size);
2349 slot = path->slots[0] + 1;
2350 leaf = path->nodes[0];
2352 nritems = btrfs_header_nritems(leaf);
2354 if (slot != nritems) {
2355 /* shift the items */
2356 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2357 btrfs_item_nr_offset(slot),
2358 (nritems - slot) * sizeof(struct btrfs_item));
2362 btrfs_cpu_key_to_disk(&disk_key, new_key);
2363 btrfs_set_item_key(leaf, &disk_key, slot);
2365 new_item = btrfs_item_nr(leaf, slot);
2367 btrfs_set_item_offset(leaf, new_item, orig_offset);
2368 btrfs_set_item_size(leaf, new_item, item_size - split_offset);
2370 btrfs_set_item_offset(leaf, item,
2371 orig_offset + item_size - split_offset);
2372 btrfs_set_item_size(leaf, item, split_offset);
2374 btrfs_set_header_nritems(leaf, nritems + 1);
2376 /* write the data for the start of the original item */
2377 write_extent_buffer(leaf, buf,
2378 btrfs_item_ptr_offset(leaf, path->slots[0]),
2381 /* write the data for the new item */
2382 write_extent_buffer(leaf, buf + split_offset,
2383 btrfs_item_ptr_offset(leaf, slot),
2384 item_size - split_offset);
2385 btrfs_mark_buffer_dirty(leaf);
2388 if (btrfs_leaf_free_space(root, leaf) < 0) {
2389 btrfs_print_leaf(root, leaf);
2396 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
2397 struct btrfs_root *root,
2398 struct btrfs_path *path,
2399 u32 new_size, int from_end)
2403 struct extent_buffer *leaf;
2404 struct btrfs_item *item;
2406 unsigned int data_end;
2407 unsigned int old_data_start;
2408 unsigned int old_size;
2409 unsigned int size_diff;
2412 leaf = path->nodes[0];
2413 slot = path->slots[0];
2415 old_size = btrfs_item_size_nr(leaf, slot);
2416 if (old_size == new_size)
2419 nritems = btrfs_header_nritems(leaf);
2420 data_end = leaf_data_end(root, leaf);
2422 old_data_start = btrfs_item_offset_nr(leaf, slot);
2424 size_diff = old_size - new_size;
2427 BUG_ON(slot >= nritems);
2430 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2432 /* first correct the data pointers */
2433 for (i = slot; i < nritems; i++) {
2435 item = btrfs_item_nr(leaf, i);
2436 ioff = btrfs_item_offset(leaf, item);
2437 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2440 /* shift the data */
2442 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2443 data_end + size_diff, btrfs_leaf_data(leaf) +
2444 data_end, old_data_start + new_size - data_end);
2446 struct btrfs_disk_key disk_key;
2449 btrfs_item_key(leaf, &disk_key, slot);
2451 if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
2453 struct btrfs_file_extent_item *fi;
2455 fi = btrfs_item_ptr(leaf, slot,
2456 struct btrfs_file_extent_item);
2457 fi = (struct btrfs_file_extent_item *)(
2458 (unsigned long)fi - size_diff);
2460 if (btrfs_file_extent_type(leaf, fi) ==
2461 BTRFS_FILE_EXTENT_INLINE) {
2462 ptr = btrfs_item_ptr_offset(leaf, slot);
2463 memmove_extent_buffer(leaf, ptr,
2465 offsetof(struct btrfs_file_extent_item,
2470 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2471 data_end + size_diff, btrfs_leaf_data(leaf) +
2472 data_end, old_data_start - data_end);
2474 offset = btrfs_disk_key_offset(&disk_key);
2475 btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
2476 btrfs_set_item_key(leaf, &disk_key, slot);
2478 fixup_low_keys(trans, root, path, &disk_key, 1);
2481 item = btrfs_item_nr(leaf, slot);
2482 btrfs_set_item_size(leaf, item, new_size);
2483 btrfs_mark_buffer_dirty(leaf);
2486 if (btrfs_leaf_free_space(root, leaf) < 0) {
2487 btrfs_print_leaf(root, leaf);
2493 int btrfs_extend_item(struct btrfs_trans_handle *trans,
2494 struct btrfs_root *root, struct btrfs_path *path,
2499 struct extent_buffer *leaf;
2500 struct btrfs_item *item;
2502 unsigned int data_end;
2503 unsigned int old_data;
2504 unsigned int old_size;
2507 leaf = path->nodes[0];
2509 nritems = btrfs_header_nritems(leaf);
2510 data_end = leaf_data_end(root, leaf);
2512 if (btrfs_leaf_free_space(root, leaf) < data_size) {
2513 btrfs_print_leaf(root, leaf);
2516 slot = path->slots[0];
2517 old_data = btrfs_item_end_nr(leaf, slot);
2520 if (slot >= nritems) {
2521 btrfs_print_leaf(root, leaf);
2522 printk("slot %d too large, nritems %d\n", slot, nritems);
2527 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2529 /* first correct the data pointers */
2530 for (i = slot; i < nritems; i++) {
2532 item = btrfs_item_nr(leaf, i);
2533 ioff = btrfs_item_offset(leaf, item);
2534 btrfs_set_item_offset(leaf, item, ioff - data_size);
2537 /* shift the data */
2538 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2539 data_end - data_size, btrfs_leaf_data(leaf) +
2540 data_end, old_data - data_end);
2542 data_end = old_data;
2543 old_size = btrfs_item_size_nr(leaf, slot);
2544 item = btrfs_item_nr(leaf, slot);
2545 btrfs_set_item_size(leaf, item, old_size + data_size);
2546 btrfs_mark_buffer_dirty(leaf);
2549 if (btrfs_leaf_free_space(root, leaf) < 0) {
2550 btrfs_print_leaf(root, leaf);
2557 * Given a key and some data, insert an item into the tree.
2558 * This does all the path init required, making room in the tree if needed.
2560 int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
2561 struct btrfs_root *root,
2562 struct btrfs_path *path,
2563 struct btrfs_key *cpu_key, u32 *data_size,
2566 struct extent_buffer *leaf;
2567 struct btrfs_item *item;
2574 unsigned int data_end;
2575 struct btrfs_disk_key disk_key;
2577 for (i = 0; i < nr; i++) {
2578 total_data += data_size[i];
2581 /* create a root if there isn't one */
2585 total_size = total_data + nr * sizeof(struct btrfs_item);
2586 ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
2593 leaf = path->nodes[0];
2595 nritems = btrfs_header_nritems(leaf);
2596 data_end = leaf_data_end(root, leaf);
2598 if (btrfs_leaf_free_space(root, leaf) < total_size) {
2599 btrfs_print_leaf(root, leaf);
2600 printk("not enough freespace need %u have %d\n",
2601 total_size, btrfs_leaf_free_space(root, leaf));
2605 slot = path->slots[0];
2608 if (slot != nritems) {
2610 unsigned int old_data = btrfs_item_end_nr(leaf, slot);
2612 if (old_data < data_end) {
2613 btrfs_print_leaf(root, leaf);
2614 printk("slot %d old_data %d data_end %d\n",
2615 slot, old_data, data_end);
2619 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2621 /* first correct the data pointers */
2622 for (i = slot; i < nritems; i++) {
2625 item = btrfs_item_nr(leaf, i);
2626 ioff = btrfs_item_offset(leaf, item);
2627 btrfs_set_item_offset(leaf, item, ioff - total_data);
2630 /* shift the items */
2631 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
2632 btrfs_item_nr_offset(slot),
2633 (nritems - slot) * sizeof(struct btrfs_item));
2635 /* shift the data */
2636 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2637 data_end - total_data, btrfs_leaf_data(leaf) +
2638 data_end, old_data - data_end);
2639 data_end = old_data;
2642 /* setup the item for the new data */
2643 for (i = 0; i < nr; i++) {
2644 btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
2645 btrfs_set_item_key(leaf, &disk_key, slot + i);
2646 item = btrfs_item_nr(leaf, slot + i);
2647 btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
2648 data_end -= data_size[i];
2649 btrfs_set_item_size(leaf, item, data_size[i]);
2651 btrfs_set_header_nritems(leaf, nritems + nr);
2652 btrfs_mark_buffer_dirty(leaf);
2656 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
2657 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2660 if (btrfs_leaf_free_space(root, leaf) < 0) {
2661 btrfs_print_leaf(root, leaf);
2670 * Given a key and some data, insert an item into the tree.
2671 * This does all the path init required, making room in the tree if needed.
2673 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
2674 *root, struct btrfs_key *cpu_key, void *data, u32
2678 struct btrfs_path *path;
2679 struct extent_buffer *leaf;
2682 path = btrfs_alloc_path();
2684 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
2686 leaf = path->nodes[0];
2687 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
2688 write_extent_buffer(leaf, data, ptr, data_size);
2689 btrfs_mark_buffer_dirty(leaf);
2691 btrfs_free_path(path);
2696 * delete the pointer from a given node.
2698 * If the delete empties a node, the node is removed from the tree,
2699 * continuing all the way the root if required. The root is converted into
2700 * a leaf if all the nodes are emptied.
2702 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2703 struct btrfs_path *path, int level, int slot)
2705 struct extent_buffer *parent = path->nodes[level];
2710 nritems = btrfs_header_nritems(parent);
2711 if (slot != nritems -1) {
2712 memmove_extent_buffer(parent,
2713 btrfs_node_key_ptr_offset(slot),
2714 btrfs_node_key_ptr_offset(slot + 1),
2715 sizeof(struct btrfs_key_ptr) *
2716 (nritems - slot - 1));
2719 btrfs_set_header_nritems(parent, nritems);
2720 if (nritems == 0 && parent == root->node) {
2721 BUG_ON(btrfs_header_level(root->node) != 1);
2722 /* just turn the root into a leaf and break */
2723 btrfs_set_header_level(root->node, 0);
2724 } else if (slot == 0) {
2725 struct btrfs_disk_key disk_key;
2727 btrfs_node_key(parent, &disk_key, 0);
2728 wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
2732 btrfs_mark_buffer_dirty(parent);
2737 * a helper function to delete the leaf pointed to by path->slots[1] and
2740 * This deletes the pointer in path->nodes[1] and frees the leaf
2741 * block extent. zero is returned if it all worked out, < 0 otherwise.
2743 * The path must have already been setup for deleting the leaf, including
2744 * all the proper balancing. path->nodes[1] must be locked.
2746 static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
2747 struct btrfs_root *root,
2748 struct btrfs_path *path,
2749 struct extent_buffer *leaf)
2753 WARN_ON(btrfs_header_generation(leaf) != trans->transid);
2754 ret = del_ptr(trans, root, path, 1, path->slots[1]);
2758 ret = btrfs_free_extent(trans, root, leaf->start, leaf->len,
2759 0, root->root_key.objectid, 0, 0);
2764 * delete the item at the leaf level in path. If that empties
2765 * the leaf, remove it from the tree
2767 int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2768 struct btrfs_path *path, int slot, int nr)
2770 struct extent_buffer *leaf;
2771 struct btrfs_item *item;
2779 leaf = path->nodes[0];
2780 last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
2782 for (i = 0; i < nr; i++)
2783 dsize += btrfs_item_size_nr(leaf, slot + i);
2785 nritems = btrfs_header_nritems(leaf);
2787 if (slot + nr != nritems) {
2789 int data_end = leaf_data_end(root, leaf);
2791 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2793 btrfs_leaf_data(leaf) + data_end,
2794 last_off - data_end);
2796 for (i = slot + nr; i < nritems; i++) {
2799 item = btrfs_item_nr(leaf, i);
2800 ioff = btrfs_item_offset(leaf, item);
2801 btrfs_set_item_offset(leaf, item, ioff + dsize);
2804 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2805 btrfs_item_nr_offset(slot + nr),
2806 sizeof(struct btrfs_item) *
2807 (nritems - slot - nr));
2809 btrfs_set_header_nritems(leaf, nritems - nr);
2812 /* delete the leaf if we've emptied it */
2814 if (leaf == root->node) {
2815 btrfs_set_header_level(leaf, 0);
2817 clean_tree_block(trans, root, leaf);
2818 wait_on_tree_block_writeback(root, leaf);
2820 wret = btrfs_del_leaf(trans, root, path, leaf);
2826 int used = leaf_space_used(leaf, 0, nritems);
2828 struct btrfs_disk_key disk_key;
2830 btrfs_item_key(leaf, &disk_key, 0);
2831 wret = fixup_low_keys(trans, root, path,
2837 /* delete the leaf if it is mostly empty */
2838 if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
2839 /* push_leaf_left fixes the path.
2840 * make sure the path still points to our leaf
2841 * for possible call to del_ptr below
2843 slot = path->slots[1];
2844 extent_buffer_get(leaf);
2846 wret = push_leaf_left(trans, root, path, 1, 1);
2847 if (wret < 0 && wret != -ENOSPC)
2850 if (path->nodes[0] == leaf &&
2851 btrfs_header_nritems(leaf)) {
2852 wret = push_leaf_right(trans, root, path, 1, 1);
2853 if (wret < 0 && wret != -ENOSPC)
2857 if (btrfs_header_nritems(leaf) == 0) {
2858 clean_tree_block(trans, root, leaf);
2859 wait_on_tree_block_writeback(root, leaf);
2861 path->slots[1] = slot;
2862 ret = btrfs_del_leaf(trans, root, path, leaf);
2864 free_extent_buffer(leaf);
2867 btrfs_mark_buffer_dirty(leaf);
2868 free_extent_buffer(leaf);
2871 btrfs_mark_buffer_dirty(leaf);
2878 * walk up the tree as far as required to find the previous leaf.
2879 * returns 0 if it found something or 1 if there are no lesser leaves.
2880 * returns < 0 on io errors.
2882 int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2886 struct extent_buffer *c;
2887 struct extent_buffer *next = NULL;
2889 while(level < BTRFS_MAX_LEVEL) {
2890 if (!path->nodes[level])
2893 slot = path->slots[level];
2894 c = path->nodes[level];
2897 if (level == BTRFS_MAX_LEVEL)
2904 free_extent_buffer(next);
2906 next = read_node_slot(root, c, slot);
2909 path->slots[level] = slot;
2912 c = path->nodes[level];
2913 free_extent_buffer(c);
2914 slot = btrfs_header_nritems(next);
2917 path->nodes[level] = next;
2918 path->slots[level] = slot;
2921 next = read_node_slot(root, next, slot);
2927 * walk up the tree as far as required to find the next leaf.
2928 * returns 0 if it found something or 1 if there are no greater leaves.
2929 * returns < 0 on io errors.
2931 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2935 struct extent_buffer *c;
2936 struct extent_buffer *next = NULL;
2938 while(level < BTRFS_MAX_LEVEL) {
2939 if (!path->nodes[level])
2942 slot = path->slots[level] + 1;
2943 c = path->nodes[level];
2944 if (slot >= btrfs_header_nritems(c)) {
2946 if (level == BTRFS_MAX_LEVEL)
2952 free_extent_buffer(next);
2955 reada_for_search(root, path, level, slot, 0);
2957 next = read_node_slot(root, c, slot);
2962 path->slots[level] = slot;
2965 c = path->nodes[level];
2966 free_extent_buffer(c);
2967 path->nodes[level] = next;
2968 path->slots[level] = 0;
2972 reada_for_search(root, path, level, 0, 0);
2973 next = read_node_slot(root, next, 0);
2980 int btrfs_previous_item(struct btrfs_root *root,
2981 struct btrfs_path *path, u64 min_objectid,
2984 struct btrfs_key found_key;
2985 struct extent_buffer *leaf;
2989 if (path->slots[0] == 0) {
2990 ret = btrfs_prev_leaf(root, path);
2996 leaf = path->nodes[0];
2997 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2998 if (found_key.type == type)