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 int btrfs_copy_root(struct btrfs_trans_handle
*trans
,
74 struct btrfs_root
*root
,
75 struct extent_buffer
*buf
,
76 struct extent_buffer
**cow_ret
, u64 new_root_objectid
)
78 struct extent_buffer
*cow
;
82 struct btrfs_key first_key
;
83 struct btrfs_root
*new_root
;
85 new_root
= kmalloc(sizeof(*new_root
), GFP_NOFS
);
89 memcpy(new_root
, root
, sizeof(*new_root
));
90 new_root
->root_key
.objectid
= new_root_objectid
;
92 WARN_ON(root
->ref_cows
&& trans
->transid
!=
93 root
->fs_info
->running_transaction
->transid
);
94 WARN_ON(root
->ref_cows
&& trans
->transid
!= root
->last_trans
);
96 level
= btrfs_header_level(buf
);
97 nritems
= btrfs_header_nritems(buf
);
100 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
102 btrfs_node_key_to_cpu(buf
, &first_key
, 0);
104 first_key
.objectid
= 0;
106 cow
= __btrfs_alloc_free_block(trans
, new_root
, buf
->len
,
108 trans
->transid
, first_key
.objectid
,
109 level
, buf
->start
, 0);
115 copy_extent_buffer(cow
, buf
, 0, 0, cow
->len
);
116 btrfs_set_header_bytenr(cow
, cow
->start
);
117 btrfs_set_header_generation(cow
, trans
->transid
);
118 btrfs_set_header_owner(cow
, new_root_objectid
);
120 WARN_ON(btrfs_header_generation(buf
) > trans
->transid
);
121 ret
= btrfs_inc_ref(trans
, new_root
, buf
);
127 btrfs_mark_buffer_dirty(cow
);
132 int __btrfs_cow_block(struct btrfs_trans_handle
*trans
,
133 struct btrfs_root
*root
,
134 struct extent_buffer
*buf
,
135 struct extent_buffer
*parent
, int parent_slot
,
136 struct extent_buffer
**cow_ret
,
137 u64 search_start
, u64 empty_size
)
140 struct extent_buffer
*cow
;
143 int different_trans
= 0;
145 struct btrfs_key first_key
;
147 if (root
->ref_cows
) {
148 root_gen
= trans
->transid
;
153 WARN_ON(root
->ref_cows
&& trans
->transid
!=
154 root
->fs_info
->running_transaction
->transid
);
155 WARN_ON(root
->ref_cows
&& trans
->transid
!= root
->last_trans
);
157 level
= btrfs_header_level(buf
);
158 nritems
= btrfs_header_nritems(buf
);
161 btrfs_item_key_to_cpu(buf
, &first_key
, 0);
163 btrfs_node_key_to_cpu(buf
, &first_key
, 0);
165 first_key
.objectid
= 0;
167 cow
= __btrfs_alloc_free_block(trans
, root
, buf
->len
,
168 root
->root_key
.objectid
,
169 root_gen
, first_key
.objectid
, level
,
170 search_start
, empty_size
);
174 copy_extent_buffer(cow
, buf
, 0, 0, cow
->len
);
175 btrfs_set_header_bytenr(cow
, cow
->start
);
176 btrfs_set_header_generation(cow
, trans
->transid
);
177 btrfs_set_header_owner(cow
, root
->root_key
.objectid
);
179 WARN_ON(btrfs_header_generation(buf
) > trans
->transid
);
180 if (btrfs_header_generation(buf
) != trans
->transid
) {
182 ret
= btrfs_inc_ref(trans
, root
, buf
);
186 clean_tree_block(trans
, root
, buf
);
189 if (buf
== root
->node
) {
190 root_gen
= btrfs_header_generation(buf
);
192 extent_buffer_get(cow
);
193 if (buf
!= root
->commit_root
) {
194 btrfs_free_extent(trans
, root
, buf
->start
,
195 buf
->len
, root
->root_key
.objectid
,
198 free_extent_buffer(buf
);
200 root_gen
= btrfs_header_generation(parent
);
201 btrfs_set_node_blockptr(parent
, parent_slot
,
203 WARN_ON(trans
->transid
== 0);
204 btrfs_set_node_ptr_generation(parent
, parent_slot
,
206 btrfs_mark_buffer_dirty(parent
);
207 WARN_ON(btrfs_header_generation(parent
) != trans
->transid
);
208 btrfs_free_extent(trans
, root
, buf
->start
, buf
->len
,
209 btrfs_header_owner(parent
), root_gen
,
212 free_extent_buffer(buf
);
213 btrfs_mark_buffer_dirty(cow
);
218 int btrfs_cow_block(struct btrfs_trans_handle
*trans
,
219 struct btrfs_root
*root
, struct extent_buffer
*buf
,
220 struct extent_buffer
*parent
, int parent_slot
,
221 struct extent_buffer
**cow_ret
)
225 if (trans
->transaction
!= root
->fs_info
->running_transaction
) {
226 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
227 root
->fs_info
->running_transaction
->transid
);
230 if (trans
->transid
!= root
->fs_info
->generation
) {
231 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
232 root
->fs_info
->generation
);
235 if (btrfs_header_generation(buf
) == trans
->transid
) {
240 search_start
= buf
->start
& ~((u64
)BTRFS_BLOCK_GROUP_SIZE
- 1);
241 ret
= __btrfs_cow_block(trans
, root
, buf
, parent
,
242 parent_slot
, cow_ret
, search_start
, 0);
246 static int close_blocks(u64 blocknr
, u64 other
, u32 blocksize
)
248 if (blocknr
< other
&& other
- (blocknr
+ blocksize
) < 32768)
250 if (blocknr
> other
&& blocknr
- (other
+ blocksize
) < 32768)
256 * compare two keys in a memcmp fashion
258 static int comp_keys(struct btrfs_disk_key
*disk
, struct btrfs_key
*k2
)
262 btrfs_disk_key_to_cpu(&k1
, disk
);
264 if (k1
.objectid
> k2
->objectid
)
266 if (k1
.objectid
< k2
->objectid
)
268 if (k1
.type
> k2
->type
)
270 if (k1
.type
< k2
->type
)
272 if (k1
.offset
> k2
->offset
)
274 if (k1
.offset
< k2
->offset
)
280 int btrfs_realloc_node(struct btrfs_trans_handle
*trans
,
281 struct btrfs_root
*root
, struct extent_buffer
*parent
,
282 int start_slot
, int cache_only
, u64
*last_ret
,
283 struct btrfs_key
*progress
)
285 struct extent_buffer
*cur
;
286 struct extent_buffer
*tmp
;
288 u64 search_start
= *last_ret
;
298 int progress_passed
= 0;
299 struct btrfs_disk_key disk_key
;
301 parent_level
= btrfs_header_level(parent
);
302 if (cache_only
&& parent_level
!= 1)
305 if (trans
->transaction
!= root
->fs_info
->running_transaction
) {
306 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
307 root
->fs_info
->running_transaction
->transid
);
310 if (trans
->transid
!= root
->fs_info
->generation
) {
311 printk(KERN_CRIT
"trans %Lu running %Lu\n", trans
->transid
,
312 root
->fs_info
->generation
);
316 parent_nritems
= btrfs_header_nritems(parent
);
317 blocksize
= btrfs_level_size(root
, parent_level
- 1);
318 end_slot
= parent_nritems
;
320 if (parent_nritems
== 1)
323 for (i
= start_slot
; i
< end_slot
; i
++) {
326 if (!parent
->map_token
) {
327 map_extent_buffer(parent
,
328 btrfs_node_key_ptr_offset(i
),
329 sizeof(struct btrfs_key_ptr
),
330 &parent
->map_token
, &parent
->kaddr
,
331 &parent
->map_start
, &parent
->map_len
,
334 btrfs_node_key(parent
, &disk_key
, i
);
335 if (!progress_passed
&& comp_keys(&disk_key
, progress
) < 0)
339 blocknr
= btrfs_node_blockptr(parent
, i
);
341 last_block
= blocknr
;
344 other
= btrfs_node_blockptr(parent
, i
- 1);
345 close
= close_blocks(blocknr
, other
, blocksize
);
347 if (close
&& i
< end_slot
- 2) {
348 other
= btrfs_node_blockptr(parent
, i
+ 1);
349 close
= close_blocks(blocknr
, other
, blocksize
);
352 last_block
= blocknr
;
355 if (parent
->map_token
) {
356 unmap_extent_buffer(parent
, parent
->map_token
,
358 parent
->map_token
= NULL
;
361 cur
= btrfs_find_tree_block(root
, blocknr
, blocksize
);
363 uptodate
= btrfs_buffer_uptodate(cur
);
366 if (!cur
|| !uptodate
) {
368 free_extent_buffer(cur
);
372 cur
= read_tree_block(root
, blocknr
,
374 } else if (!uptodate
) {
375 btrfs_read_buffer(cur
);
378 if (search_start
== 0)
379 search_start
= last_block
;
381 err
= __btrfs_cow_block(trans
, root
, cur
, parent
, i
,
384 (end_slot
- i
) * blocksize
));
386 free_extent_buffer(cur
);
389 search_start
= tmp
->start
;
390 last_block
= tmp
->start
;
391 *last_ret
= search_start
;
392 if (parent_level
== 1)
393 btrfs_clear_buffer_defrag(tmp
);
394 free_extent_buffer(tmp
);
396 if (parent
->map_token
) {
397 unmap_extent_buffer(parent
, parent
->map_token
,
399 parent
->map_token
= NULL
;
405 * The leaf data grows from end-to-front in the node.
406 * this returns the address of the start of the last item,
407 * which is the stop of the leaf data stack
409 static inline unsigned int leaf_data_end(struct btrfs_root
*root
,
410 struct extent_buffer
*leaf
)
412 u32 nr
= btrfs_header_nritems(leaf
);
414 return BTRFS_LEAF_DATA_SIZE(root
);
415 return btrfs_item_offset_nr(leaf
, nr
- 1);
418 static int check_node(struct btrfs_root
*root
, struct btrfs_path
*path
,
421 struct extent_buffer
*parent
= NULL
;
422 struct extent_buffer
*node
= path
->nodes
[level
];
423 struct btrfs_disk_key parent_key
;
424 struct btrfs_disk_key node_key
;
427 struct btrfs_key cpukey
;
428 u32 nritems
= btrfs_header_nritems(node
);
430 if (path
->nodes
[level
+ 1])
431 parent
= path
->nodes
[level
+ 1];
433 slot
= path
->slots
[level
];
434 BUG_ON(nritems
== 0);
436 parent_slot
= path
->slots
[level
+ 1];
437 btrfs_node_key(parent
, &parent_key
, parent_slot
);
438 btrfs_node_key(node
, &node_key
, 0);
439 BUG_ON(memcmp(&parent_key
, &node_key
,
440 sizeof(struct btrfs_disk_key
)));
441 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
442 btrfs_header_bytenr(node
));
444 BUG_ON(nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
));
446 btrfs_node_key_to_cpu(node
, &cpukey
, slot
- 1);
447 btrfs_node_key(node
, &node_key
, slot
);
448 BUG_ON(comp_keys(&node_key
, &cpukey
) <= 0);
450 if (slot
< nritems
- 1) {
451 btrfs_node_key_to_cpu(node
, &cpukey
, slot
+ 1);
452 btrfs_node_key(node
, &node_key
, slot
);
453 BUG_ON(comp_keys(&node_key
, &cpukey
) >= 0);
458 static int check_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
,
461 struct extent_buffer
*leaf
= path
->nodes
[level
];
462 struct extent_buffer
*parent
= NULL
;
464 struct btrfs_key cpukey
;
465 struct btrfs_disk_key parent_key
;
466 struct btrfs_disk_key leaf_key
;
467 int slot
= path
->slots
[0];
469 u32 nritems
= btrfs_header_nritems(leaf
);
471 if (path
->nodes
[level
+ 1])
472 parent
= path
->nodes
[level
+ 1];
478 parent_slot
= path
->slots
[level
+ 1];
479 btrfs_node_key(parent
, &parent_key
, parent_slot
);
480 btrfs_item_key(leaf
, &leaf_key
, 0);
482 BUG_ON(memcmp(&parent_key
, &leaf_key
,
483 sizeof(struct btrfs_disk_key
)));
484 BUG_ON(btrfs_node_blockptr(parent
, parent_slot
) !=
485 btrfs_header_bytenr(leaf
));
488 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
489 btrfs_item_key_to_cpu(leaf
, &cpukey
, i
+ 1);
490 btrfs_item_key(leaf
, &leaf_key
, i
);
491 if (comp_keys(&leaf_key
, &cpukey
) >= 0) {
492 btrfs_print_leaf(root
, leaf
);
493 printk("slot %d offset bad key\n", i
);
496 if (btrfs_item_offset_nr(leaf
, i
) !=
497 btrfs_item_end_nr(leaf
, i
+ 1)) {
498 btrfs_print_leaf(root
, leaf
);
499 printk("slot %d offset bad\n", i
);
503 if (btrfs_item_offset_nr(leaf
, i
) +
504 btrfs_item_size_nr(leaf
, i
) !=
505 BTRFS_LEAF_DATA_SIZE(root
)) {
506 btrfs_print_leaf(root
, leaf
);
507 printk("slot %d first offset bad\n", i
);
513 if (btrfs_item_size_nr(leaf
, nritems
- 1) > 4096) {
514 btrfs_print_leaf(root
, leaf
);
515 printk("slot %d bad size \n", nritems
- 1);
520 if (slot
!= 0 && slot
< nritems
- 1) {
521 btrfs_item_key(leaf
, &leaf_key
, slot
);
522 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
- 1);
523 if (comp_keys(&leaf_key
, &cpukey
) <= 0) {
524 btrfs_print_leaf(root
, leaf
);
525 printk("slot %d offset bad key\n", slot
);
528 if (btrfs_item_offset_nr(leaf
, slot
- 1) !=
529 btrfs_item_end_nr(leaf
, slot
)) {
530 btrfs_print_leaf(root
, leaf
);
531 printk("slot %d offset bad\n", slot
);
535 if (slot
< nritems
- 1) {
536 btrfs_item_key(leaf
, &leaf_key
, slot
);
537 btrfs_item_key_to_cpu(leaf
, &cpukey
, slot
+ 1);
538 BUG_ON(comp_keys(&leaf_key
, &cpukey
) >= 0);
539 if (btrfs_item_offset_nr(leaf
, slot
) !=
540 btrfs_item_end_nr(leaf
, slot
+ 1)) {
541 btrfs_print_leaf(root
, leaf
);
542 printk("slot %d offset bad\n", slot
);
546 BUG_ON(btrfs_item_offset_nr(leaf
, 0) +
547 btrfs_item_size_nr(leaf
, 0) != BTRFS_LEAF_DATA_SIZE(root
));
551 static int check_block(struct btrfs_root
*root
, struct btrfs_path
*path
,
556 struct extent_buffer
*buf
= path
->nodes
[level
];
558 if (memcmp_extent_buffer(buf
, root
->fs_info
->fsid
,
559 (unsigned long)btrfs_header_fsid(buf
),
561 printk("warning bad block %Lu\n", buf
->start
);
566 return check_leaf(root
, path
, level
);
567 return check_node(root
, path
, level
);
571 * search for key in the extent_buffer. The items start at offset p,
572 * and they are item_size apart. There are 'max' items in p.
574 * the slot in the array is returned via slot, and it points to
575 * the place where you would insert key if it is not found in
578 * slot may point to max if the key is bigger than all of the keys
580 static int generic_bin_search(struct extent_buffer
*eb
, unsigned long p
,
581 int item_size
, struct btrfs_key
*key
,
588 struct btrfs_disk_key
*tmp
= NULL
;
589 struct btrfs_disk_key unaligned
;
590 unsigned long offset
;
591 char *map_token
= NULL
;
593 unsigned long map_start
= 0;
594 unsigned long map_len
= 0;
598 mid
= (low
+ high
) / 2;
599 offset
= p
+ mid
* item_size
;
601 if (!map_token
|| offset
< map_start
||
602 (offset
+ sizeof(struct btrfs_disk_key
)) >
603 map_start
+ map_len
) {
605 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
608 err
= map_extent_buffer(eb
, offset
,
609 sizeof(struct btrfs_disk_key
),
611 &map_start
, &map_len
, KM_USER0
);
614 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
617 read_extent_buffer(eb
, &unaligned
,
618 offset
, sizeof(unaligned
));
623 tmp
= (struct btrfs_disk_key
*)(kaddr
+ offset
-
626 ret
= comp_keys(tmp
, key
);
635 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
641 unmap_extent_buffer(eb
, map_token
, KM_USER0
);
646 * simple bin_search frontend that does the right thing for
649 static int bin_search(struct extent_buffer
*eb
, struct btrfs_key
*key
,
650 int level
, int *slot
)
653 return generic_bin_search(eb
,
654 offsetof(struct btrfs_leaf
, items
),
655 sizeof(struct btrfs_item
),
656 key
, btrfs_header_nritems(eb
),
659 return generic_bin_search(eb
,
660 offsetof(struct btrfs_node
, ptrs
),
661 sizeof(struct btrfs_key_ptr
),
662 key
, btrfs_header_nritems(eb
),
668 static struct extent_buffer
*read_node_slot(struct btrfs_root
*root
,
669 struct extent_buffer
*parent
, int slot
)
673 if (slot
>= btrfs_header_nritems(parent
))
675 return read_tree_block(root
, btrfs_node_blockptr(parent
, slot
),
676 btrfs_level_size(root
, btrfs_header_level(parent
) - 1));
679 static int balance_level(struct btrfs_trans_handle
*trans
, struct btrfs_root
680 *root
, struct btrfs_path
*path
, int level
)
682 struct extent_buffer
*right
= NULL
;
683 struct extent_buffer
*mid
;
684 struct extent_buffer
*left
= NULL
;
685 struct extent_buffer
*parent
= NULL
;
689 int orig_slot
= path
->slots
[level
];
690 int err_on_enospc
= 0;
696 mid
= path
->nodes
[level
];
697 WARN_ON(btrfs_header_generation(mid
) != trans
->transid
);
699 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
701 if (level
< BTRFS_MAX_LEVEL
- 1)
702 parent
= path
->nodes
[level
+ 1];
703 pslot
= path
->slots
[level
+ 1];
706 * deal with the case where there is only one pointer in the root
707 * by promoting the node below to a root
710 struct extent_buffer
*child
;
712 if (btrfs_header_nritems(mid
) != 1)
715 /* promote the child to a root */
716 child
= read_node_slot(root
, mid
, 0);
719 path
->nodes
[level
] = NULL
;
720 clean_tree_block(trans
, root
, mid
);
721 wait_on_tree_block_writeback(root
, mid
);
722 /* once for the path */
723 free_extent_buffer(mid
);
724 ret
= btrfs_free_extent(trans
, root
, mid
->start
, mid
->len
,
725 root
->root_key
.objectid
,
726 btrfs_header_generation(mid
), 0, 0, 1);
727 /* once for the root ptr */
728 free_extent_buffer(mid
);
731 if (btrfs_header_nritems(mid
) >
732 BTRFS_NODEPTRS_PER_BLOCK(root
) / 4)
735 if (btrfs_header_nritems(mid
) < 2)
738 left
= read_node_slot(root
, parent
, pslot
- 1);
740 wret
= btrfs_cow_block(trans
, root
, left
,
741 parent
, pslot
- 1, &left
);
747 right
= read_node_slot(root
, parent
, pslot
+ 1);
749 wret
= btrfs_cow_block(trans
, root
, right
,
750 parent
, pslot
+ 1, &right
);
757 /* first, try to make some room in the middle buffer */
759 orig_slot
+= btrfs_header_nritems(left
);
760 wret
= push_node_left(trans
, root
, left
, mid
);
763 if (btrfs_header_nritems(mid
) < 2)
768 * then try to empty the right most buffer into the middle
771 wret
= push_node_left(trans
, root
, mid
, right
);
772 if (wret
< 0 && wret
!= -ENOSPC
)
774 if (btrfs_header_nritems(right
) == 0) {
775 u64 bytenr
= right
->start
;
776 u64 generation
= btrfs_header_generation(parent
);
777 u32 blocksize
= right
->len
;
779 clean_tree_block(trans
, root
, right
);
780 wait_on_tree_block_writeback(root
, right
);
781 free_extent_buffer(right
);
783 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
+
787 wret
= btrfs_free_extent(trans
, root
, bytenr
,
789 btrfs_header_owner(parent
),
790 generation
, 0, 0, 1);
794 struct btrfs_disk_key right_key
;
795 btrfs_node_key(right
, &right_key
, 0);
796 btrfs_set_node_key(parent
, &right_key
, pslot
+ 1);
797 btrfs_mark_buffer_dirty(parent
);
800 if (btrfs_header_nritems(mid
) == 1) {
802 * we're not allowed to leave a node with one item in the
803 * tree during a delete. A deletion from lower in the tree
804 * could try to delete the only pointer in this node.
805 * So, pull some keys from the left.
806 * There has to be a left pointer at this point because
807 * otherwise we would have pulled some pointers from the
811 wret
= balance_node_right(trans
, root
, mid
, left
);
818 if (btrfs_header_nritems(mid
) == 0) {
819 /* we've managed to empty the middle node, drop it */
820 u64 root_gen
= btrfs_header_generation(parent
);
821 u64 bytenr
= mid
->start
;
822 u32 blocksize
= mid
->len
;
823 clean_tree_block(trans
, root
, mid
);
824 wait_on_tree_block_writeback(root
, mid
);
825 free_extent_buffer(mid
);
827 wret
= del_ptr(trans
, root
, path
, level
+ 1, pslot
);
830 wret
= btrfs_free_extent(trans
, root
, bytenr
, blocksize
,
831 btrfs_header_owner(parent
),
836 /* update the parent key to reflect our changes */
837 struct btrfs_disk_key mid_key
;
838 btrfs_node_key(mid
, &mid_key
, 0);
839 btrfs_set_node_key(parent
, &mid_key
, pslot
);
840 btrfs_mark_buffer_dirty(parent
);
843 /* update the path */
845 if (btrfs_header_nritems(left
) > orig_slot
) {
846 extent_buffer_get(left
);
847 path
->nodes
[level
] = left
;
848 path
->slots
[level
+ 1] -= 1;
849 path
->slots
[level
] = orig_slot
;
851 free_extent_buffer(mid
);
853 orig_slot
-= btrfs_header_nritems(left
);
854 path
->slots
[level
] = orig_slot
;
857 /* double check we haven't messed things up */
858 check_block(root
, path
, level
);
860 btrfs_node_blockptr(path
->nodes
[level
], path
->slots
[level
]))
864 free_extent_buffer(right
);
866 free_extent_buffer(left
);
870 /* returns zero if the push worked, non-zero otherwise */
871 static int push_nodes_for_insert(struct btrfs_trans_handle
*trans
,
872 struct btrfs_root
*root
,
873 struct btrfs_path
*path
, int level
)
875 struct extent_buffer
*right
= NULL
;
876 struct extent_buffer
*mid
;
877 struct extent_buffer
*left
= NULL
;
878 struct extent_buffer
*parent
= NULL
;
882 int orig_slot
= path
->slots
[level
];
888 mid
= path
->nodes
[level
];
889 WARN_ON(btrfs_header_generation(mid
) != trans
->transid
);
890 orig_ptr
= btrfs_node_blockptr(mid
, orig_slot
);
892 if (level
< BTRFS_MAX_LEVEL
- 1)
893 parent
= path
->nodes
[level
+ 1];
894 pslot
= path
->slots
[level
+ 1];
899 left
= read_node_slot(root
, parent
, pslot
- 1);
901 /* first, try to make some room in the middle buffer */
904 left_nr
= btrfs_header_nritems(left
);
905 if (left_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
908 ret
= btrfs_cow_block(trans
, root
, left
, parent
,
913 wret
= push_node_left(trans
, root
,
920 struct btrfs_disk_key disk_key
;
921 orig_slot
+= left_nr
;
922 btrfs_node_key(mid
, &disk_key
, 0);
923 btrfs_set_node_key(parent
, &disk_key
, pslot
);
924 btrfs_mark_buffer_dirty(parent
);
925 if (btrfs_header_nritems(left
) > orig_slot
) {
926 path
->nodes
[level
] = left
;
927 path
->slots
[level
+ 1] -= 1;
928 path
->slots
[level
] = orig_slot
;
929 free_extent_buffer(mid
);
932 btrfs_header_nritems(left
);
933 path
->slots
[level
] = orig_slot
;
934 free_extent_buffer(left
);
938 free_extent_buffer(left
);
940 right
= read_node_slot(root
, parent
, pslot
+ 1);
943 * then try to empty the right most buffer into the middle
947 right_nr
= btrfs_header_nritems(right
);
948 if (right_nr
>= BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
951 ret
= btrfs_cow_block(trans
, root
, right
,
957 wret
= balance_node_right(trans
, root
,
964 struct btrfs_disk_key disk_key
;
966 btrfs_node_key(right
, &disk_key
, 0);
967 btrfs_set_node_key(parent
, &disk_key
, pslot
+ 1);
968 btrfs_mark_buffer_dirty(parent
);
970 if (btrfs_header_nritems(mid
) <= orig_slot
) {
971 path
->nodes
[level
] = right
;
972 path
->slots
[level
+ 1] += 1;
973 path
->slots
[level
] = orig_slot
-
974 btrfs_header_nritems(mid
);
975 free_extent_buffer(mid
);
977 free_extent_buffer(right
);
981 free_extent_buffer(right
);
987 * readahead one full node of leaves
989 static void reada_for_search(struct btrfs_root
*root
, struct btrfs_path
*path
,
990 int level
, int slot
, u64 objectid
)
992 struct extent_buffer
*node
;
993 struct btrfs_disk_key disk_key
;
999 int direction
= path
->reada
;
1000 struct extent_buffer
*eb
;
1008 if (!path
->nodes
[level
])
1011 node
= path
->nodes
[level
];
1012 search
= btrfs_node_blockptr(node
, slot
);
1013 blocksize
= btrfs_level_size(root
, level
- 1);
1014 eb
= btrfs_find_tree_block(root
, search
, blocksize
);
1016 free_extent_buffer(eb
);
1020 highest_read
= search
;
1021 lowest_read
= search
;
1023 nritems
= btrfs_header_nritems(node
);
1026 if (direction
< 0) {
1030 } else if (direction
> 0) {
1035 if (path
->reada
< 0 && objectid
) {
1036 btrfs_node_key(node
, &disk_key
, nr
);
1037 if (btrfs_disk_key_objectid(&disk_key
) != objectid
)
1040 search
= btrfs_node_blockptr(node
, nr
);
1041 if ((search
>= lowest_read
&& search
<= highest_read
) ||
1042 (search
< lowest_read
&& lowest_read
- search
<= 32768) ||
1043 (search
> highest_read
&& search
- highest_read
<= 32768)) {
1044 readahead_tree_block(root
, search
, blocksize
);
1048 if (path
->reada
< 2 && (nread
> (256 * 1024) || nscan
> 32))
1050 if(nread
> (1024 * 1024) || nscan
> 128)
1053 if (search
< lowest_read
)
1054 lowest_read
= search
;
1055 if (search
> highest_read
)
1056 highest_read
= search
;
1060 * look for key in the tree. path is filled in with nodes along the way
1061 * if key is found, we return zero and you can find the item in the leaf
1062 * level of the path (level 0)
1064 * If the key isn't found, the path points to the slot where it should
1065 * be inserted, and 1 is returned. If there are other errors during the
1066 * search a negative error number is returned.
1068 * if ins_len > 0, nodes and leaves will be split as we walk down the
1069 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1072 int btrfs_search_slot(struct btrfs_trans_handle
*trans
, struct btrfs_root
1073 *root
, struct btrfs_key
*key
, struct btrfs_path
*p
, int
1076 struct extent_buffer
*b
;
1082 int should_reada
= p
->reada
;
1083 u8 lowest_level
= 0;
1085 lowest_level
= p
->lowest_level
;
1086 WARN_ON(lowest_level
&& ins_len
);
1087 WARN_ON(p
->nodes
[0] != NULL
);
1088 WARN_ON(!mutex_is_locked(&root
->fs_info
->fs_mutex
));
1091 extent_buffer_get(b
);
1093 level
= btrfs_header_level(b
);
1096 wret
= btrfs_cow_block(trans
, root
, b
,
1097 p
->nodes
[level
+ 1],
1098 p
->slots
[level
+ 1],
1101 free_extent_buffer(b
);
1105 BUG_ON(!cow
&& ins_len
);
1106 if (level
!= btrfs_header_level(b
))
1108 level
= btrfs_header_level(b
);
1109 p
->nodes
[level
] = b
;
1110 ret
= check_block(root
, p
, level
);
1113 ret
= bin_search(b
, key
, level
, &slot
);
1115 if (ret
&& slot
> 0)
1117 p
->slots
[level
] = slot
;
1118 if (ins_len
> 0 && btrfs_header_nritems(b
) >=
1119 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1) {
1120 int sret
= split_node(trans
, root
, p
, level
);
1124 b
= p
->nodes
[level
];
1125 slot
= p
->slots
[level
];
1126 } else if (ins_len
< 0) {
1127 int sret
= balance_level(trans
, root
, p
,
1131 b
= p
->nodes
[level
];
1133 btrfs_release_path(NULL
, p
);
1136 slot
= p
->slots
[level
];
1137 BUG_ON(btrfs_header_nritems(b
) == 1);
1139 /* this is only true while dropping a snapshot */
1140 if (level
== lowest_level
)
1142 bytenr
= btrfs_node_blockptr(b
, slot
);
1143 ptr_gen
= btrfs_node_ptr_generation(b
, slot
);
1145 reada_for_search(root
, p
, level
, slot
,
1147 b
= read_tree_block(root
, bytenr
,
1148 btrfs_level_size(root
, level
- 1));
1149 if (ptr_gen
!= btrfs_header_generation(b
)) {
1150 printk("block %llu bad gen wanted %llu "
1152 (unsigned long long)b
->start
,
1153 (unsigned long long)ptr_gen
,
1154 (unsigned long long)btrfs_header_generation(b
));
1157 p
->slots
[level
] = slot
;
1158 if (ins_len
> 0 && btrfs_leaf_free_space(root
, b
) <
1159 sizeof(struct btrfs_item
) + ins_len
) {
1160 int sret
= split_leaf(trans
, root
, key
,
1161 p
, ins_len
, ret
== 0);
1173 * adjust the pointers going up the tree, starting at level
1174 * making sure the right key of each node is points to 'key'.
1175 * This is used after shifting pointers to the left, so it stops
1176 * fixing up pointers when a given leaf/node is not in slot 0 of the
1179 * If this fails to write a tree block, it returns -1, but continues
1180 * fixing up the blocks in ram so the tree is consistent.
1182 static int fixup_low_keys(struct btrfs_trans_handle
*trans
,
1183 struct btrfs_root
*root
, struct btrfs_path
*path
,
1184 struct btrfs_disk_key
*key
, int level
)
1188 struct extent_buffer
*t
;
1190 for (i
= level
; i
< BTRFS_MAX_LEVEL
; i
++) {
1191 int tslot
= path
->slots
[i
];
1192 if (!path
->nodes
[i
])
1195 btrfs_set_node_key(t
, key
, tslot
);
1196 btrfs_mark_buffer_dirty(path
->nodes
[i
]);
1204 * try to push data from one node into the next node left in the
1207 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
1208 * error, and > 0 if there was no room in the left hand block.
1210 static int push_node_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
1211 *root
, struct extent_buffer
*dst
,
1212 struct extent_buffer
*src
)
1219 src_nritems
= btrfs_header_nritems(src
);
1220 dst_nritems
= btrfs_header_nritems(dst
);
1221 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
1222 WARN_ON(btrfs_header_generation(src
) != trans
->transid
);
1223 WARN_ON(btrfs_header_generation(dst
) != trans
->transid
);
1225 if (push_items
<= 0) {
1229 if (src_nritems
< push_items
)
1230 push_items
= src_nritems
;
1232 copy_extent_buffer(dst
, src
,
1233 btrfs_node_key_ptr_offset(dst_nritems
),
1234 btrfs_node_key_ptr_offset(0),
1235 push_items
* sizeof(struct btrfs_key_ptr
));
1237 if (push_items
< src_nritems
) {
1238 memmove_extent_buffer(src
, btrfs_node_key_ptr_offset(0),
1239 btrfs_node_key_ptr_offset(push_items
),
1240 (src_nritems
- push_items
) *
1241 sizeof(struct btrfs_key_ptr
));
1243 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
1244 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
1245 btrfs_mark_buffer_dirty(src
);
1246 btrfs_mark_buffer_dirty(dst
);
1251 * try to push data from one node into the next node right in the
1254 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1255 * error, and > 0 if there was no room in the right hand block.
1257 * this will only push up to 1/2 the contents of the left node over
1259 static int balance_node_right(struct btrfs_trans_handle
*trans
,
1260 struct btrfs_root
*root
,
1261 struct extent_buffer
*dst
,
1262 struct extent_buffer
*src
)
1270 WARN_ON(btrfs_header_generation(src
) != trans
->transid
);
1271 WARN_ON(btrfs_header_generation(dst
) != trans
->transid
);
1273 src_nritems
= btrfs_header_nritems(src
);
1274 dst_nritems
= btrfs_header_nritems(dst
);
1275 push_items
= BTRFS_NODEPTRS_PER_BLOCK(root
) - dst_nritems
;
1276 if (push_items
<= 0)
1279 max_push
= src_nritems
/ 2 + 1;
1280 /* don't try to empty the node */
1281 if (max_push
>= src_nritems
)
1284 if (max_push
< push_items
)
1285 push_items
= max_push
;
1287 memmove_extent_buffer(dst
, btrfs_node_key_ptr_offset(push_items
),
1288 btrfs_node_key_ptr_offset(0),
1290 sizeof(struct btrfs_key_ptr
));
1292 copy_extent_buffer(dst
, src
,
1293 btrfs_node_key_ptr_offset(0),
1294 btrfs_node_key_ptr_offset(src_nritems
- push_items
),
1295 push_items
* sizeof(struct btrfs_key_ptr
));
1297 btrfs_set_header_nritems(src
, src_nritems
- push_items
);
1298 btrfs_set_header_nritems(dst
, dst_nritems
+ push_items
);
1300 btrfs_mark_buffer_dirty(src
);
1301 btrfs_mark_buffer_dirty(dst
);
1306 * helper function to insert a new root level in the tree.
1307 * A new node is allocated, and a single item is inserted to
1308 * point to the existing root
1310 * returns zero on success or < 0 on failure.
1312 static int insert_new_root(struct btrfs_trans_handle
*trans
,
1313 struct btrfs_root
*root
,
1314 struct btrfs_path
*path
, int level
)
1318 struct extent_buffer
*lower
;
1319 struct extent_buffer
*c
;
1320 struct btrfs_disk_key lower_key
;
1322 BUG_ON(path
->nodes
[level
]);
1323 BUG_ON(path
->nodes
[level
-1] != root
->node
);
1326 root_gen
= trans
->transid
;
1330 lower
= path
->nodes
[level
-1];
1332 btrfs_item_key(lower
, &lower_key
, 0);
1334 btrfs_node_key(lower
, &lower_key
, 0);
1336 c
= __btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
1337 root
->root_key
.objectid
,
1338 root_gen
, lower_key
.objectid
, level
,
1339 root
->node
->start
, 0);
1342 memset_extent_buffer(c
, 0, 0, root
->nodesize
);
1343 btrfs_set_header_nritems(c
, 1);
1344 btrfs_set_header_level(c
, level
);
1345 btrfs_set_header_bytenr(c
, c
->start
);
1346 btrfs_set_header_generation(c
, trans
->transid
);
1347 btrfs_set_header_owner(c
, root
->root_key
.objectid
);
1349 write_extent_buffer(c
, root
->fs_info
->fsid
,
1350 (unsigned long)btrfs_header_fsid(c
),
1352 btrfs_set_node_key(c
, &lower_key
, 0);
1353 btrfs_set_node_blockptr(c
, 0, lower
->start
);
1354 lower_gen
= btrfs_header_generation(lower
);
1355 WARN_ON(lower_gen
== 0);
1357 btrfs_set_node_ptr_generation(c
, 0, lower_gen
);
1359 btrfs_mark_buffer_dirty(c
);
1361 /* the super has an extra ref to root->node */
1362 free_extent_buffer(root
->node
);
1364 extent_buffer_get(c
);
1365 path
->nodes
[level
] = c
;
1366 path
->slots
[level
] = 0;
1368 if (root
->ref_cows
&& lower_gen
!= trans
->transid
) {
1369 struct btrfs_path
*back_path
= btrfs_alloc_path();
1371 ret
= btrfs_insert_extent_backref(trans
,
1372 root
->fs_info
->extent_root
,
1374 root
->root_key
.objectid
,
1375 trans
->transid
, 0, 0);
1377 btrfs_free_path(back_path
);
1383 * worker function to insert a single pointer in a node.
1384 * the node should have enough room for the pointer already
1386 * slot and level indicate where you want the key to go, and
1387 * blocknr is the block the key points to.
1389 * returns zero on success and < 0 on any error
1391 static int insert_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
1392 *root
, struct btrfs_path
*path
, struct btrfs_disk_key
1393 *key
, u64 bytenr
, int slot
, int level
)
1395 struct extent_buffer
*lower
;
1398 BUG_ON(!path
->nodes
[level
]);
1399 lower
= path
->nodes
[level
];
1400 nritems
= btrfs_header_nritems(lower
);
1403 if (nritems
== BTRFS_NODEPTRS_PER_BLOCK(root
))
1405 if (slot
!= nritems
) {
1406 memmove_extent_buffer(lower
,
1407 btrfs_node_key_ptr_offset(slot
+ 1),
1408 btrfs_node_key_ptr_offset(slot
),
1409 (nritems
- slot
) * sizeof(struct btrfs_key_ptr
));
1411 btrfs_set_node_key(lower
, key
, slot
);
1412 btrfs_set_node_blockptr(lower
, slot
, bytenr
);
1413 WARN_ON(trans
->transid
== 0);
1414 btrfs_set_node_ptr_generation(lower
, slot
, trans
->transid
);
1415 btrfs_set_header_nritems(lower
, nritems
+ 1);
1416 btrfs_mark_buffer_dirty(lower
);
1421 * split the node at the specified level in path in two.
1422 * The path is corrected to point to the appropriate node after the split
1424 * Before splitting this tries to make some room in the node by pushing
1425 * left and right, if either one works, it returns right away.
1427 * returns 0 on success and < 0 on failure
1429 static int split_node(struct btrfs_trans_handle
*trans
, struct btrfs_root
1430 *root
, struct btrfs_path
*path
, int level
)
1433 struct extent_buffer
*c
;
1434 struct extent_buffer
*split
;
1435 struct btrfs_disk_key disk_key
;
1441 c
= path
->nodes
[level
];
1442 WARN_ON(btrfs_header_generation(c
) != trans
->transid
);
1443 if (c
== root
->node
) {
1444 /* trying to split the root, lets make a new one */
1445 ret
= insert_new_root(trans
, root
, path
, level
+ 1);
1449 ret
= push_nodes_for_insert(trans
, root
, path
, level
);
1450 c
= path
->nodes
[level
];
1451 if (!ret
&& btrfs_header_nritems(c
) <
1452 BTRFS_NODEPTRS_PER_BLOCK(root
) - 1)
1458 c_nritems
= btrfs_header_nritems(c
);
1460 root_gen
= trans
->transid
;
1464 btrfs_node_key(c
, &disk_key
, 0);
1465 split
= __btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
1466 root
->root_key
.objectid
,
1468 btrfs_disk_key_objectid(&disk_key
),
1469 level
, c
->start
, 0);
1471 return PTR_ERR(split
);
1473 btrfs_set_header_flags(split
, btrfs_header_flags(c
));
1474 btrfs_set_header_level(split
, btrfs_header_level(c
));
1475 btrfs_set_header_bytenr(split
, split
->start
);
1476 btrfs_set_header_generation(split
, trans
->transid
);
1477 btrfs_set_header_owner(split
, root
->root_key
.objectid
);
1478 write_extent_buffer(split
, root
->fs_info
->fsid
,
1479 (unsigned long)btrfs_header_fsid(split
),
1482 mid
= (c_nritems
+ 1) / 2;
1484 copy_extent_buffer(split
, c
,
1485 btrfs_node_key_ptr_offset(0),
1486 btrfs_node_key_ptr_offset(mid
),
1487 (c_nritems
- mid
) * sizeof(struct btrfs_key_ptr
));
1488 btrfs_set_header_nritems(split
, c_nritems
- mid
);
1489 btrfs_set_header_nritems(c
, mid
);
1492 btrfs_mark_buffer_dirty(c
);
1493 btrfs_mark_buffer_dirty(split
);
1495 btrfs_node_key(split
, &disk_key
, 0);
1496 wret
= insert_ptr(trans
, root
, path
, &disk_key
, split
->start
,
1497 path
->slots
[level
+ 1] + 1,
1502 if (path
->slots
[level
] >= mid
) {
1503 path
->slots
[level
] -= mid
;
1504 free_extent_buffer(c
);
1505 path
->nodes
[level
] = split
;
1506 path
->slots
[level
+ 1] += 1;
1508 free_extent_buffer(split
);
1514 * how many bytes are required to store the items in a leaf. start
1515 * and nr indicate which items in the leaf to check. This totals up the
1516 * space used both by the item structs and the item data
1518 static int leaf_space_used(struct extent_buffer
*l
, int start
, int nr
)
1521 int nritems
= btrfs_header_nritems(l
);
1522 int end
= min(nritems
, start
+ nr
) - 1;
1526 data_len
= btrfs_item_end_nr(l
, start
);
1527 data_len
= data_len
- btrfs_item_offset_nr(l
, end
);
1528 data_len
+= sizeof(struct btrfs_item
) * nr
;
1529 WARN_ON(data_len
< 0);
1534 * The space between the end of the leaf items and
1535 * the start of the leaf data. IOW, how much room
1536 * the leaf has left for both items and data
1538 int btrfs_leaf_free_space(struct btrfs_root
*root
, struct extent_buffer
*leaf
)
1540 int nritems
= btrfs_header_nritems(leaf
);
1542 ret
= BTRFS_LEAF_DATA_SIZE(root
) - leaf_space_used(leaf
, 0, nritems
);
1544 printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
1545 ret
, (unsigned long) BTRFS_LEAF_DATA_SIZE(root
),
1546 leaf_space_used(leaf
, 0, nritems
), nritems
);
1552 * push some data in the path leaf to the right, trying to free up at
1553 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1555 * returns 1 if the push failed because the other node didn't have enough
1556 * room, 0 if everything worked out and < 0 if there were major errors.
1558 static int push_leaf_right(struct btrfs_trans_handle
*trans
, struct btrfs_root
1559 *root
, struct btrfs_path
*path
, int data_size
,
1562 struct extent_buffer
*left
= path
->nodes
[0];
1563 struct extent_buffer
*right
;
1564 struct extent_buffer
*upper
;
1565 struct btrfs_disk_key disk_key
;
1571 struct btrfs_item
*item
;
1579 slot
= path
->slots
[1];
1580 if (!path
->nodes
[1]) {
1583 upper
= path
->nodes
[1];
1584 if (slot
>= btrfs_header_nritems(upper
) - 1)
1587 right
= read_tree_block(root
, btrfs_node_blockptr(upper
, slot
+ 1),
1589 free_space
= btrfs_leaf_free_space(root
, right
);
1590 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1591 free_extent_buffer(right
);
1595 /* cow and double check */
1596 ret
= btrfs_cow_block(trans
, root
, right
, upper
,
1599 free_extent_buffer(right
);
1602 free_space
= btrfs_leaf_free_space(root
, right
);
1603 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1604 free_extent_buffer(right
);
1608 left_nritems
= btrfs_header_nritems(left
);
1609 if (left_nritems
== 0) {
1610 free_extent_buffer(right
);
1619 i
= left_nritems
- 1;
1621 item
= btrfs_item_nr(left
, i
);
1623 if (path
->slots
[0] == i
)
1624 push_space
+= data_size
+ sizeof(*item
);
1626 if (!left
->map_token
) {
1627 map_extent_buffer(left
, (unsigned long)item
,
1628 sizeof(struct btrfs_item
),
1629 &left
->map_token
, &left
->kaddr
,
1630 &left
->map_start
, &left
->map_len
,
1634 this_item_size
= btrfs_item_size(left
, item
);
1635 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
1638 push_space
+= this_item_size
+ sizeof(*item
);
1643 if (left
->map_token
) {
1644 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
1645 left
->map_token
= NULL
;
1648 if (push_items
== 0) {
1649 free_extent_buffer(right
);
1653 if (!empty
&& push_items
== left_nritems
)
1656 /* push left to right */
1657 right_nritems
= btrfs_header_nritems(right
);
1659 push_space
= btrfs_item_end_nr(left
, left_nritems
- push_items
);
1660 push_space
-= leaf_data_end(root
, left
);
1662 /* make room in the right data area */
1663 data_end
= leaf_data_end(root
, right
);
1664 memmove_extent_buffer(right
,
1665 btrfs_leaf_data(right
) + data_end
- push_space
,
1666 btrfs_leaf_data(right
) + data_end
,
1667 BTRFS_LEAF_DATA_SIZE(root
) - data_end
);
1669 /* copy from the left data area */
1670 copy_extent_buffer(right
, left
, btrfs_leaf_data(right
) +
1671 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
1672 btrfs_leaf_data(left
) + leaf_data_end(root
, left
),
1675 memmove_extent_buffer(right
, btrfs_item_nr_offset(push_items
),
1676 btrfs_item_nr_offset(0),
1677 right_nritems
* sizeof(struct btrfs_item
));
1679 /* copy the items from left to right */
1680 copy_extent_buffer(right
, left
, btrfs_item_nr_offset(0),
1681 btrfs_item_nr_offset(left_nritems
- push_items
),
1682 push_items
* sizeof(struct btrfs_item
));
1684 /* update the item pointers */
1685 right_nritems
+= push_items
;
1686 btrfs_set_header_nritems(right
, right_nritems
);
1687 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1688 for (i
= 0; i
< right_nritems
; i
++) {
1689 item
= btrfs_item_nr(right
, i
);
1690 if (!right
->map_token
) {
1691 map_extent_buffer(right
, (unsigned long)item
,
1692 sizeof(struct btrfs_item
),
1693 &right
->map_token
, &right
->kaddr
,
1694 &right
->map_start
, &right
->map_len
,
1697 push_space
-= btrfs_item_size(right
, item
);
1698 btrfs_set_item_offset(right
, item
, push_space
);
1701 if (right
->map_token
) {
1702 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1703 right
->map_token
= NULL
;
1705 left_nritems
-= push_items
;
1706 btrfs_set_header_nritems(left
, left_nritems
);
1709 btrfs_mark_buffer_dirty(left
);
1710 btrfs_mark_buffer_dirty(right
);
1712 btrfs_item_key(right
, &disk_key
, 0);
1713 btrfs_set_node_key(upper
, &disk_key
, slot
+ 1);
1714 btrfs_mark_buffer_dirty(upper
);
1716 /* then fixup the leaf pointer in the path */
1717 if (path
->slots
[0] >= left_nritems
) {
1718 path
->slots
[0] -= left_nritems
;
1719 free_extent_buffer(path
->nodes
[0]);
1720 path
->nodes
[0] = right
;
1721 path
->slots
[1] += 1;
1723 free_extent_buffer(right
);
1728 * push some data in the path leaf to the left, trying to free up at
1729 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1731 static int push_leaf_left(struct btrfs_trans_handle
*trans
, struct btrfs_root
1732 *root
, struct btrfs_path
*path
, int data_size
,
1735 struct btrfs_disk_key disk_key
;
1736 struct extent_buffer
*right
= path
->nodes
[0];
1737 struct extent_buffer
*left
;
1743 struct btrfs_item
*item
;
1744 u32 old_left_nritems
;
1750 u32 old_left_item_size
;
1752 slot
= path
->slots
[1];
1755 if (!path
->nodes
[1])
1758 right_nritems
= btrfs_header_nritems(right
);
1759 if (right_nritems
== 0) {
1763 left
= read_tree_block(root
, btrfs_node_blockptr(path
->nodes
[1],
1764 slot
- 1), root
->leafsize
);
1765 free_space
= btrfs_leaf_free_space(root
, left
);
1766 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1767 free_extent_buffer(left
);
1771 /* cow and double check */
1772 ret
= btrfs_cow_block(trans
, root
, left
,
1773 path
->nodes
[1], slot
- 1, &left
);
1775 /* we hit -ENOSPC, but it isn't fatal here */
1776 free_extent_buffer(left
);
1780 free_space
= btrfs_leaf_free_space(root
, left
);
1781 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
1782 free_extent_buffer(left
);
1789 nr
= right_nritems
- 1;
1791 for (i
= 0; i
< nr
; i
++) {
1792 item
= btrfs_item_nr(right
, i
);
1793 if (!right
->map_token
) {
1794 map_extent_buffer(right
, (unsigned long)item
,
1795 sizeof(struct btrfs_item
),
1796 &right
->map_token
, &right
->kaddr
,
1797 &right
->map_start
, &right
->map_len
,
1801 if (path
->slots
[0] == i
)
1802 push_space
+= data_size
+ sizeof(*item
);
1804 this_item_size
= btrfs_item_size(right
, item
);
1805 if (this_item_size
+ sizeof(*item
) + push_space
> free_space
)
1809 push_space
+= this_item_size
+ sizeof(*item
);
1812 if (right
->map_token
) {
1813 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1814 right
->map_token
= NULL
;
1817 if (push_items
== 0) {
1818 free_extent_buffer(left
);
1821 if (!empty
&& push_items
== btrfs_header_nritems(right
))
1824 /* push data from right to left */
1825 copy_extent_buffer(left
, right
,
1826 btrfs_item_nr_offset(btrfs_header_nritems(left
)),
1827 btrfs_item_nr_offset(0),
1828 push_items
* sizeof(struct btrfs_item
));
1830 push_space
= BTRFS_LEAF_DATA_SIZE(root
) -
1831 btrfs_item_offset_nr(right
, push_items
-1);
1833 copy_extent_buffer(left
, right
, btrfs_leaf_data(left
) +
1834 leaf_data_end(root
, left
) - push_space
,
1835 btrfs_leaf_data(right
) +
1836 btrfs_item_offset_nr(right
, push_items
- 1),
1838 old_left_nritems
= btrfs_header_nritems(left
);
1839 BUG_ON(old_left_nritems
< 0);
1841 old_left_item_size
= btrfs_item_offset_nr(left
, old_left_nritems
- 1);
1842 for (i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
1845 item
= btrfs_item_nr(left
, i
);
1846 if (!left
->map_token
) {
1847 map_extent_buffer(left
, (unsigned long)item
,
1848 sizeof(struct btrfs_item
),
1849 &left
->map_token
, &left
->kaddr
,
1850 &left
->map_start
, &left
->map_len
,
1854 ioff
= btrfs_item_offset(left
, item
);
1855 btrfs_set_item_offset(left
, item
,
1856 ioff
- (BTRFS_LEAF_DATA_SIZE(root
) - old_left_item_size
));
1858 btrfs_set_header_nritems(left
, old_left_nritems
+ push_items
);
1859 if (left
->map_token
) {
1860 unmap_extent_buffer(left
, left
->map_token
, KM_USER1
);
1861 left
->map_token
= NULL
;
1864 /* fixup right node */
1865 if (push_items
> right_nritems
) {
1866 printk("push items %d nr %u\n", push_items
, right_nritems
);
1870 if (push_items
< right_nritems
) {
1871 push_space
= btrfs_item_offset_nr(right
, push_items
- 1) -
1872 leaf_data_end(root
, right
);
1873 memmove_extent_buffer(right
, btrfs_leaf_data(right
) +
1874 BTRFS_LEAF_DATA_SIZE(root
) - push_space
,
1875 btrfs_leaf_data(right
) +
1876 leaf_data_end(root
, right
), push_space
);
1878 memmove_extent_buffer(right
, btrfs_item_nr_offset(0),
1879 btrfs_item_nr_offset(push_items
),
1880 (btrfs_header_nritems(right
) - push_items
) *
1881 sizeof(struct btrfs_item
));
1883 right_nritems
-= push_items
;
1884 btrfs_set_header_nritems(right
, right_nritems
);
1885 push_space
= BTRFS_LEAF_DATA_SIZE(root
);
1886 for (i
= 0; i
< right_nritems
; i
++) {
1887 item
= btrfs_item_nr(right
, i
);
1889 if (!right
->map_token
) {
1890 map_extent_buffer(right
, (unsigned long)item
,
1891 sizeof(struct btrfs_item
),
1892 &right
->map_token
, &right
->kaddr
,
1893 &right
->map_start
, &right
->map_len
,
1897 push_space
= push_space
- btrfs_item_size(right
, item
);
1898 btrfs_set_item_offset(right
, item
, push_space
);
1900 if (right
->map_token
) {
1901 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
1902 right
->map_token
= NULL
;
1905 btrfs_mark_buffer_dirty(left
);
1907 btrfs_mark_buffer_dirty(right
);
1909 btrfs_item_key(right
, &disk_key
, 0);
1910 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
1914 /* then fixup the leaf pointer in the path */
1915 if (path
->slots
[0] < push_items
) {
1916 path
->slots
[0] += old_left_nritems
;
1917 free_extent_buffer(path
->nodes
[0]);
1918 path
->nodes
[0] = left
;
1919 path
->slots
[1] -= 1;
1921 free_extent_buffer(left
);
1922 path
->slots
[0] -= push_items
;
1924 BUG_ON(path
->slots
[0] < 0);
1929 * split the path's leaf in two, making sure there is at least data_size
1930 * available for the resulting leaf level of the path.
1932 * returns 0 if all went well and < 0 on failure.
1934 static int split_leaf(struct btrfs_trans_handle
*trans
, struct btrfs_root
1935 *root
, struct btrfs_key
*ins_key
,
1936 struct btrfs_path
*path
, int data_size
, int extend
)
1939 struct extent_buffer
*l
;
1943 struct extent_buffer
*right
;
1944 int space_needed
= data_size
+ sizeof(struct btrfs_item
);
1951 int num_doubles
= 0;
1952 struct btrfs_disk_key disk_key
;
1955 space_needed
= data_size
;
1958 root_gen
= trans
->transid
;
1962 /* first try to make some room by pushing left and right */
1963 if (ins_key
->type
!= BTRFS_DIR_ITEM_KEY
) {
1964 wret
= push_leaf_right(trans
, root
, path
, data_size
, 0);
1969 wret
= push_leaf_left(trans
, root
, path
, data_size
, 0);
1975 /* did the pushes work? */
1976 if (btrfs_leaf_free_space(root
, l
) >= space_needed
)
1980 if (!path
->nodes
[1]) {
1981 ret
= insert_new_root(trans
, root
, path
, 1);
1988 slot
= path
->slots
[0];
1989 nritems
= btrfs_header_nritems(l
);
1990 mid
= (nritems
+ 1)/ 2;
1992 btrfs_item_key(l
, &disk_key
, 0);
1994 right
= __btrfs_alloc_free_block(trans
, root
, root
->leafsize
,
1995 root
->root_key
.objectid
,
1996 root_gen
, disk_key
.objectid
, 0,
1999 return PTR_ERR(right
);
2001 memset_extent_buffer(right
, 0, 0, sizeof(struct btrfs_header
));
2002 btrfs_set_header_bytenr(right
, right
->start
);
2003 btrfs_set_header_generation(right
, trans
->transid
);
2004 btrfs_set_header_owner(right
, root
->root_key
.objectid
);
2005 btrfs_set_header_level(right
, 0);
2006 write_extent_buffer(right
, root
->fs_info
->fsid
,
2007 (unsigned long)btrfs_header_fsid(right
),
2011 leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
2012 BTRFS_LEAF_DATA_SIZE(root
)) {
2013 if (slot
>= nritems
) {
2014 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
2015 btrfs_set_header_nritems(right
, 0);
2016 wret
= insert_ptr(trans
, root
, path
,
2017 &disk_key
, right
->start
,
2018 path
->slots
[1] + 1, 1);
2021 free_extent_buffer(path
->nodes
[0]);
2022 path
->nodes
[0] = right
;
2024 path
->slots
[1] += 1;
2028 if (mid
!= nritems
&&
2029 leaf_space_used(l
, mid
, nritems
- mid
) +
2030 space_needed
> BTRFS_LEAF_DATA_SIZE(root
)) {
2035 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
2036 BTRFS_LEAF_DATA_SIZE(root
)) {
2037 if (!extend
&& slot
== 0) {
2038 btrfs_cpu_key_to_disk(&disk_key
, ins_key
);
2039 btrfs_set_header_nritems(right
, 0);
2040 wret
= insert_ptr(trans
, root
, path
,
2046 free_extent_buffer(path
->nodes
[0]);
2047 path
->nodes
[0] = right
;
2049 if (path
->slots
[1] == 0) {
2050 wret
= fixup_low_keys(trans
, root
,
2051 path
, &disk_key
, 1);
2056 } else if (extend
&& slot
== 0) {
2060 if (mid
!= nritems
&&
2061 leaf_space_used(l
, mid
, nritems
- mid
) +
2062 space_needed
> BTRFS_LEAF_DATA_SIZE(root
)) {
2068 nritems
= nritems
- mid
;
2069 btrfs_set_header_nritems(right
, nritems
);
2070 data_copy_size
= btrfs_item_end_nr(l
, mid
) - leaf_data_end(root
, l
);
2072 copy_extent_buffer(right
, l
, btrfs_item_nr_offset(0),
2073 btrfs_item_nr_offset(mid
),
2074 nritems
* sizeof(struct btrfs_item
));
2076 copy_extent_buffer(right
, l
,
2077 btrfs_leaf_data(right
) + BTRFS_LEAF_DATA_SIZE(root
) -
2078 data_copy_size
, btrfs_leaf_data(l
) +
2079 leaf_data_end(root
, l
), data_copy_size
);
2081 rt_data_off
= BTRFS_LEAF_DATA_SIZE(root
) -
2082 btrfs_item_end_nr(l
, mid
);
2084 for (i
= 0; i
< nritems
; i
++) {
2085 struct btrfs_item
*item
= btrfs_item_nr(right
, i
);
2088 if (!right
->map_token
) {
2089 map_extent_buffer(right
, (unsigned long)item
,
2090 sizeof(struct btrfs_item
),
2091 &right
->map_token
, &right
->kaddr
,
2092 &right
->map_start
, &right
->map_len
,
2096 ioff
= btrfs_item_offset(right
, item
);
2097 btrfs_set_item_offset(right
, item
, ioff
+ rt_data_off
);
2100 if (right
->map_token
) {
2101 unmap_extent_buffer(right
, right
->map_token
, KM_USER1
);
2102 right
->map_token
= NULL
;
2105 btrfs_set_header_nritems(l
, mid
);
2107 btrfs_item_key(right
, &disk_key
, 0);
2108 wret
= insert_ptr(trans
, root
, path
, &disk_key
, right
->start
,
2109 path
->slots
[1] + 1, 1);
2113 btrfs_mark_buffer_dirty(right
);
2114 btrfs_mark_buffer_dirty(l
);
2115 BUG_ON(path
->slots
[0] != slot
);
2118 free_extent_buffer(path
->nodes
[0]);
2119 path
->nodes
[0] = right
;
2120 path
->slots
[0] -= mid
;
2121 path
->slots
[1] += 1;
2123 free_extent_buffer(right
);
2125 BUG_ON(path
->slots
[0] < 0);
2128 BUG_ON(num_doubles
!= 0);
2135 int btrfs_truncate_item(struct btrfs_trans_handle
*trans
,
2136 struct btrfs_root
*root
,
2137 struct btrfs_path
*path
,
2138 u32 new_size
, int from_end
)
2143 struct extent_buffer
*leaf
;
2144 struct btrfs_item
*item
;
2146 unsigned int data_end
;
2147 unsigned int old_data_start
;
2148 unsigned int old_size
;
2149 unsigned int size_diff
;
2152 slot_orig
= path
->slots
[0];
2153 leaf
= path
->nodes
[0];
2154 slot
= path
->slots
[0];
2156 old_size
= btrfs_item_size_nr(leaf
, slot
);
2157 if (old_size
== new_size
)
2160 nritems
= btrfs_header_nritems(leaf
);
2161 data_end
= leaf_data_end(root
, leaf
);
2163 old_data_start
= btrfs_item_offset_nr(leaf
, slot
);
2165 size_diff
= old_size
- new_size
;
2168 BUG_ON(slot
>= nritems
);
2171 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2173 /* first correct the data pointers */
2174 for (i
= slot
; i
< nritems
; i
++) {
2176 item
= btrfs_item_nr(leaf
, i
);
2178 if (!leaf
->map_token
) {
2179 map_extent_buffer(leaf
, (unsigned long)item
,
2180 sizeof(struct btrfs_item
),
2181 &leaf
->map_token
, &leaf
->kaddr
,
2182 &leaf
->map_start
, &leaf
->map_len
,
2186 ioff
= btrfs_item_offset(leaf
, item
);
2187 btrfs_set_item_offset(leaf
, item
, ioff
+ size_diff
);
2190 if (leaf
->map_token
) {
2191 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2192 leaf
->map_token
= NULL
;
2195 /* shift the data */
2197 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2198 data_end
+ size_diff
, btrfs_leaf_data(leaf
) +
2199 data_end
, old_data_start
+ new_size
- data_end
);
2201 struct btrfs_disk_key disk_key
;
2204 btrfs_item_key(leaf
, &disk_key
, slot
);
2206 if (btrfs_disk_key_type(&disk_key
) == BTRFS_EXTENT_DATA_KEY
) {
2208 struct btrfs_file_extent_item
*fi
;
2210 fi
= btrfs_item_ptr(leaf
, slot
,
2211 struct btrfs_file_extent_item
);
2212 fi
= (struct btrfs_file_extent_item
*)(
2213 (unsigned long)fi
- size_diff
);
2215 if (btrfs_file_extent_type(leaf
, fi
) ==
2216 BTRFS_FILE_EXTENT_INLINE
) {
2217 ptr
= btrfs_item_ptr_offset(leaf
, slot
);
2218 memmove_extent_buffer(leaf
, ptr
,
2220 offsetof(struct btrfs_file_extent_item
,
2225 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2226 data_end
+ size_diff
, btrfs_leaf_data(leaf
) +
2227 data_end
, old_data_start
- data_end
);
2229 offset
= btrfs_disk_key_offset(&disk_key
);
2230 btrfs_set_disk_key_offset(&disk_key
, offset
+ size_diff
);
2231 btrfs_set_item_key(leaf
, &disk_key
, slot
);
2233 fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
2236 item
= btrfs_item_nr(leaf
, slot
);
2237 btrfs_set_item_size(leaf
, item
, new_size
);
2238 btrfs_mark_buffer_dirty(leaf
);
2241 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2242 btrfs_print_leaf(root
, leaf
);
2248 int btrfs_extend_item(struct btrfs_trans_handle
*trans
,
2249 struct btrfs_root
*root
, struct btrfs_path
*path
,
2255 struct extent_buffer
*leaf
;
2256 struct btrfs_item
*item
;
2258 unsigned int data_end
;
2259 unsigned int old_data
;
2260 unsigned int old_size
;
2263 slot_orig
= path
->slots
[0];
2264 leaf
= path
->nodes
[0];
2266 nritems
= btrfs_header_nritems(leaf
);
2267 data_end
= leaf_data_end(root
, leaf
);
2269 if (btrfs_leaf_free_space(root
, leaf
) < data_size
) {
2270 btrfs_print_leaf(root
, leaf
);
2273 slot
= path
->slots
[0];
2274 old_data
= btrfs_item_end_nr(leaf
, slot
);
2277 if (slot
>= nritems
) {
2278 btrfs_print_leaf(root
, leaf
);
2279 printk("slot %d too large, nritems %d\n", slot
, nritems
);
2284 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2286 /* first correct the data pointers */
2287 for (i
= slot
; i
< nritems
; i
++) {
2289 item
= btrfs_item_nr(leaf
, i
);
2291 if (!leaf
->map_token
) {
2292 map_extent_buffer(leaf
, (unsigned long)item
,
2293 sizeof(struct btrfs_item
),
2294 &leaf
->map_token
, &leaf
->kaddr
,
2295 &leaf
->map_start
, &leaf
->map_len
,
2298 ioff
= btrfs_item_offset(leaf
, item
);
2299 btrfs_set_item_offset(leaf
, item
, ioff
- data_size
);
2302 if (leaf
->map_token
) {
2303 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2304 leaf
->map_token
= NULL
;
2307 /* shift the data */
2308 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2309 data_end
- data_size
, btrfs_leaf_data(leaf
) +
2310 data_end
, old_data
- data_end
);
2312 data_end
= old_data
;
2313 old_size
= btrfs_item_size_nr(leaf
, slot
);
2314 item
= btrfs_item_nr(leaf
, slot
);
2315 btrfs_set_item_size(leaf
, item
, old_size
+ data_size
);
2316 btrfs_mark_buffer_dirty(leaf
);
2319 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2320 btrfs_print_leaf(root
, leaf
);
2327 * Given a key and some data, insert an item into the tree.
2328 * This does all the path init required, making room in the tree if needed.
2330 int btrfs_insert_empty_item(struct btrfs_trans_handle
*trans
,
2331 struct btrfs_root
*root
,
2332 struct btrfs_path
*path
,
2333 struct btrfs_key
*cpu_key
, u32 data_size
)
2335 struct extent_buffer
*leaf
;
2336 struct btrfs_item
*item
;
2341 unsigned int data_end
;
2342 struct btrfs_disk_key disk_key
;
2344 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
2346 /* create a root if there isn't one */
2350 ret
= btrfs_search_slot(trans
, root
, cpu_key
, path
, data_size
, 1);
2357 slot_orig
= path
->slots
[0];
2358 leaf
= path
->nodes
[0];
2360 nritems
= btrfs_header_nritems(leaf
);
2361 data_end
= leaf_data_end(root
, leaf
);
2363 if (btrfs_leaf_free_space(root
, leaf
) <
2364 sizeof(struct btrfs_item
) + data_size
) {
2365 btrfs_print_leaf(root
, leaf
);
2366 printk("not enough freespace need %u have %d\n",
2367 data_size
, btrfs_leaf_free_space(root
, leaf
));
2371 slot
= path
->slots
[0];
2374 if (slot
!= nritems
) {
2376 unsigned int old_data
= btrfs_item_end_nr(leaf
, slot
);
2378 if (old_data
< data_end
) {
2379 btrfs_print_leaf(root
, leaf
);
2380 printk("slot %d old_data %d data_end %d\n",
2381 slot
, old_data
, data_end
);
2385 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2387 /* first correct the data pointers */
2388 WARN_ON(leaf
->map_token
);
2389 for (i
= slot
; i
< nritems
; i
++) {
2392 item
= btrfs_item_nr(leaf
, i
);
2393 if (!leaf
->map_token
) {
2394 map_extent_buffer(leaf
, (unsigned long)item
,
2395 sizeof(struct btrfs_item
),
2396 &leaf
->map_token
, &leaf
->kaddr
,
2397 &leaf
->map_start
, &leaf
->map_len
,
2401 ioff
= btrfs_item_offset(leaf
, item
);
2402 btrfs_set_item_offset(leaf
, item
, ioff
- data_size
);
2404 if (leaf
->map_token
) {
2405 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2406 leaf
->map_token
= NULL
;
2409 /* shift the items */
2410 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
+ 1),
2411 btrfs_item_nr_offset(slot
),
2412 (nritems
- slot
) * sizeof(struct btrfs_item
));
2414 /* shift the data */
2415 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2416 data_end
- data_size
, btrfs_leaf_data(leaf
) +
2417 data_end
, old_data
- data_end
);
2418 data_end
= old_data
;
2421 /* setup the item for the new data */
2422 btrfs_set_item_key(leaf
, &disk_key
, slot
);
2423 item
= btrfs_item_nr(leaf
, slot
);
2424 btrfs_set_item_offset(leaf
, item
, data_end
- data_size
);
2425 btrfs_set_item_size(leaf
, item
, data_size
);
2426 btrfs_set_header_nritems(leaf
, nritems
+ 1);
2427 btrfs_mark_buffer_dirty(leaf
);
2431 ret
= fixup_low_keys(trans
, root
, path
, &disk_key
, 1);
2433 if (btrfs_leaf_free_space(root
, leaf
) < 0) {
2434 btrfs_print_leaf(root
, leaf
);
2442 * Given a key and some data, insert an item into the tree.
2443 * This does all the path init required, making room in the tree if needed.
2445 int btrfs_insert_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
2446 *root
, struct btrfs_key
*cpu_key
, void *data
, u32
2450 struct btrfs_path
*path
;
2451 struct extent_buffer
*leaf
;
2454 path
= btrfs_alloc_path();
2456 ret
= btrfs_insert_empty_item(trans
, root
, path
, cpu_key
, data_size
);
2458 leaf
= path
->nodes
[0];
2459 ptr
= btrfs_item_ptr_offset(leaf
, path
->slots
[0]);
2460 write_extent_buffer(leaf
, data
, ptr
, data_size
);
2461 btrfs_mark_buffer_dirty(leaf
);
2463 btrfs_free_path(path
);
2468 * delete the pointer from a given node.
2470 * If the delete empties a node, the node is removed from the tree,
2471 * continuing all the way the root if required. The root is converted into
2472 * a leaf if all the nodes are emptied.
2474 static int del_ptr(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2475 struct btrfs_path
*path
, int level
, int slot
)
2477 struct extent_buffer
*parent
= path
->nodes
[level
];
2482 nritems
= btrfs_header_nritems(parent
);
2483 if (slot
!= nritems
-1) {
2484 memmove_extent_buffer(parent
,
2485 btrfs_node_key_ptr_offset(slot
),
2486 btrfs_node_key_ptr_offset(slot
+ 1),
2487 sizeof(struct btrfs_key_ptr
) *
2488 (nritems
- slot
- 1));
2491 btrfs_set_header_nritems(parent
, nritems
);
2492 if (nritems
== 0 && parent
== root
->node
) {
2493 BUG_ON(btrfs_header_level(root
->node
) != 1);
2494 /* just turn the root into a leaf and break */
2495 btrfs_set_header_level(root
->node
, 0);
2496 } else if (slot
== 0) {
2497 struct btrfs_disk_key disk_key
;
2499 btrfs_node_key(parent
, &disk_key
, 0);
2500 wret
= fixup_low_keys(trans
, root
, path
, &disk_key
, level
+ 1);
2504 btrfs_mark_buffer_dirty(parent
);
2509 * delete the item at the leaf level in path. If that empties
2510 * the leaf, remove it from the tree
2512 int btrfs_del_item(struct btrfs_trans_handle
*trans
, struct btrfs_root
*root
,
2513 struct btrfs_path
*path
)
2516 struct extent_buffer
*leaf
;
2517 struct btrfs_item
*item
;
2524 leaf
= path
->nodes
[0];
2525 slot
= path
->slots
[0];
2526 doff
= btrfs_item_offset_nr(leaf
, slot
);
2527 dsize
= btrfs_item_size_nr(leaf
, slot
);
2528 nritems
= btrfs_header_nritems(leaf
);
2530 if (slot
!= nritems
- 1) {
2532 int data_end
= leaf_data_end(root
, leaf
);
2534 memmove_extent_buffer(leaf
, btrfs_leaf_data(leaf
) +
2536 btrfs_leaf_data(leaf
) + data_end
,
2539 for (i
= slot
+ 1; i
< nritems
; i
++) {
2542 item
= btrfs_item_nr(leaf
, i
);
2543 if (!leaf
->map_token
) {
2544 map_extent_buffer(leaf
, (unsigned long)item
,
2545 sizeof(struct btrfs_item
),
2546 &leaf
->map_token
, &leaf
->kaddr
,
2547 &leaf
->map_start
, &leaf
->map_len
,
2550 ioff
= btrfs_item_offset(leaf
, item
);
2551 btrfs_set_item_offset(leaf
, item
, ioff
+ dsize
);
2554 if (leaf
->map_token
) {
2555 unmap_extent_buffer(leaf
, leaf
->map_token
, KM_USER1
);
2556 leaf
->map_token
= NULL
;
2559 memmove_extent_buffer(leaf
, btrfs_item_nr_offset(slot
),
2560 btrfs_item_nr_offset(slot
+ 1),
2561 sizeof(struct btrfs_item
) *
2562 (nritems
- slot
- 1));
2564 btrfs_set_header_nritems(leaf
, nritems
- 1);
2567 /* delete the leaf if we've emptied it */
2569 if (leaf
== root
->node
) {
2570 btrfs_set_header_level(leaf
, 0);
2572 u64 root_gen
= btrfs_header_generation(path
->nodes
[1]);
2573 clean_tree_block(trans
, root
, leaf
);
2574 wait_on_tree_block_writeback(root
, leaf
);
2575 wret
= del_ptr(trans
, root
, path
, 1, path
->slots
[1]);
2578 wret
= btrfs_free_extent(trans
, root
,
2579 leaf
->start
, leaf
->len
,
2580 btrfs_header_owner(path
->nodes
[1]),
2586 int used
= leaf_space_used(leaf
, 0, nritems
);
2588 struct btrfs_disk_key disk_key
;
2590 btrfs_item_key(leaf
, &disk_key
, 0);
2591 wret
= fixup_low_keys(trans
, root
, path
,
2597 /* delete the leaf if it is mostly empty */
2598 if (used
< BTRFS_LEAF_DATA_SIZE(root
) / 3) {
2599 /* push_leaf_left fixes the path.
2600 * make sure the path still points to our leaf
2601 * for possible call to del_ptr below
2603 slot
= path
->slots
[1];
2604 extent_buffer_get(leaf
);
2606 wret
= push_leaf_right(trans
, root
, path
, 1, 1);
2607 if (wret
< 0 && wret
!= -ENOSPC
)
2610 if (path
->nodes
[0] == leaf
&&
2611 btrfs_header_nritems(leaf
)) {
2612 wret
= push_leaf_left(trans
, root
, path
, 1, 1);
2613 if (wret
< 0 && wret
!= -ENOSPC
)
2617 if (btrfs_header_nritems(leaf
) == 0) {
2619 u64 bytenr
= leaf
->start
;
2620 u32 blocksize
= leaf
->len
;
2622 root_gen
= btrfs_header_generation(
2625 clean_tree_block(trans
, root
, leaf
);
2626 wait_on_tree_block_writeback(root
, leaf
);
2628 wret
= del_ptr(trans
, root
, path
, 1, slot
);
2632 free_extent_buffer(leaf
);
2633 wret
= btrfs_free_extent(trans
, root
, bytenr
,
2635 btrfs_header_owner(path
->nodes
[1]),
2640 btrfs_mark_buffer_dirty(leaf
);
2641 free_extent_buffer(leaf
);
2644 btrfs_mark_buffer_dirty(leaf
);
2651 * walk up the tree as far as required to find the previous leaf.
2652 * returns 0 if it found something or 1 if there are no lesser leaves.
2653 * returns < 0 on io errors.
2655 int btrfs_prev_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
2660 struct extent_buffer
*c
;
2661 struct extent_buffer
*next
= NULL
;
2663 while(level
< BTRFS_MAX_LEVEL
) {
2664 if (!path
->nodes
[level
])
2667 slot
= path
->slots
[level
];
2668 c
= path
->nodes
[level
];
2671 if (level
== BTRFS_MAX_LEVEL
)
2677 bytenr
= btrfs_node_blockptr(c
, slot
);
2679 free_extent_buffer(next
);
2681 next
= read_tree_block(root
, bytenr
,
2682 btrfs_level_size(root
, level
- 1));
2685 path
->slots
[level
] = slot
;
2688 c
= path
->nodes
[level
];
2689 free_extent_buffer(c
);
2690 path
->nodes
[level
] = next
;
2691 path
->slots
[level
] = 0;
2694 next
= read_tree_block(root
, btrfs_node_blockptr(next
, 0),
2695 btrfs_level_size(root
, level
- 1));
2701 * walk up the tree as far as required to find the next leaf.
2702 * returns 0 if it found something or 1 if there are no greater leaves.
2703 * returns < 0 on io errors.
2705 int btrfs_next_leaf(struct btrfs_root
*root
, struct btrfs_path
*path
)
2710 struct extent_buffer
*c
;
2711 struct extent_buffer
*next
= NULL
;
2713 while(level
< BTRFS_MAX_LEVEL
) {
2714 if (!path
->nodes
[level
])
2717 slot
= path
->slots
[level
] + 1;
2718 c
= path
->nodes
[level
];
2719 if (slot
>= btrfs_header_nritems(c
)) {
2721 if (level
== BTRFS_MAX_LEVEL
)
2726 bytenr
= btrfs_node_blockptr(c
, slot
);
2728 free_extent_buffer(next
);
2731 reada_for_search(root
, path
, level
, slot
, 0);
2733 next
= read_tree_block(root
, bytenr
,
2734 btrfs_level_size(root
, level
-1));
2737 path
->slots
[level
] = slot
;
2740 c
= path
->nodes
[level
];
2741 free_extent_buffer(c
);
2742 path
->nodes
[level
] = next
;
2743 path
->slots
[level
] = 0;
2747 reada_for_search(root
, path
, level
, 0, 0);
2748 next
= read_tree_block(root
, btrfs_node_blockptr(next
, 0),
2749 btrfs_level_size(root
, level
- 1));