3 #include "kerncompat.h"
4 #include "radix-tree.h"
7 #include "print-tree.h"
9 static int split_node(struct ctree_root
*root
, struct ctree_path
*path
,
11 static int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
,
13 static int push_node_left(struct ctree_root
*root
, struct tree_buffer
*dst
,
14 struct tree_buffer
*src
);
15 static int balance_node_right(struct ctree_root
*root
,
16 struct tree_buffer
*dst_buf
,
17 struct tree_buffer
*src_buf
);
18 static int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
,
21 inline void init_path(struct ctree_path
*p
)
23 memset(p
, 0, sizeof(*p
));
26 void release_path(struct ctree_root
*root
, struct ctree_path
*p
)
29 for (i
= 0; i
< MAX_LEVEL
; i
++) {
32 tree_block_release(root
, p
->nodes
[i
]);
34 memset(p
, 0, sizeof(*p
));
37 int btrfs_cow_block(struct ctree_root
*root
,
38 struct tree_buffer
*buf
,
39 struct tree_buffer
*parent
,
41 struct tree_buffer
**cow_ret
)
43 struct tree_buffer
*cow
;
45 if (!list_empty(&buf
->dirty
)) {
49 cow
= alloc_free_block(root
);
50 memcpy(&cow
->node
, &buf
->node
, sizeof(buf
->node
));
51 btrfs_set_header_blocknr(&cow
->node
.header
, cow
->blocknr
);
53 btrfs_inc_ref(root
, buf
);
54 if (buf
== root
->node
) {
57 if (buf
!= root
->commit_root
)
58 free_extent(root
, buf
->blocknr
, 1);
59 tree_block_release(root
, buf
);
61 parent
->node
.blockptrs
[parent_slot
] = cow
->blocknr
;
62 BUG_ON(list_empty(&parent
->dirty
));
63 free_extent(root
, buf
->blocknr
, 1);
65 tree_block_release(root
, buf
);
70 * The leaf data grows from end-to-front in the node.
71 * this returns the address of the start of the last item,
72 * which is the stop of the leaf data stack
74 static inline unsigned int leaf_data_end(struct leaf
*leaf
)
76 u32 nr
= btrfs_header_nritems(&leaf
->header
);
78 return sizeof(leaf
->data
);
79 return btrfs_item_offset(leaf
->items
+ nr
- 1);
83 * The space between the end of the leaf items and
84 * the start of the leaf data. IOW, how much room
85 * the leaf has left for both items and data
87 int leaf_free_space(struct leaf
*leaf
)
89 int data_end
= leaf_data_end(leaf
);
90 int nritems
= btrfs_header_nritems(&leaf
->header
);
91 char *items_end
= (char *)(leaf
->items
+ nritems
+ 1);
92 return (char *)(leaf
->data
+ data_end
) - (char *)items_end
;
96 * compare two keys in a memcmp fashion
98 int comp_keys(struct btrfs_disk_key
*disk
, struct btrfs_key
*k2
)
102 btrfs_disk_key_to_cpu(&k1
, disk
);
104 if (k1
.objectid
> k2
->objectid
)
106 if (k1
.objectid
< k2
->objectid
)
108 if (k1
.flags
> k2
->flags
)
110 if (k1
.flags
< k2
->flags
)
112 if (k1
.offset
> k2
->offset
)
114 if (k1
.offset
< k2
->offset
)
119 int check_node(struct ctree_path
*path
, int level
)
122 struct node
*parent
= NULL
;
123 struct node
*node
= &path
->nodes
[level
]->node
;
125 u32 nritems
= btrfs_header_nritems(&node
->header
);
127 if (path
->nodes
[level
+ 1])
128 parent
= &path
->nodes
[level
+ 1]->node
;
129 parent_slot
= path
->slots
[level
+ 1];
130 BUG_ON(nritems
== 0);
132 struct btrfs_disk_key
*parent_key
;
133 parent_key
= &parent
->keys
[parent_slot
];
134 BUG_ON(memcmp(parent_key
, node
->keys
,
135 sizeof(struct btrfs_disk_key
)));
136 BUG_ON(parent
->blockptrs
[parent_slot
] !=
137 btrfs_header_blocknr(&node
->header
));
139 BUG_ON(nritems
> NODEPTRS_PER_BLOCK
);
140 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
141 struct btrfs_key cpukey
;
142 btrfs_disk_key_to_cpu(&cpukey
, &node
->keys
[i
+ 1]);
143 BUG_ON(comp_keys(&node
->keys
[i
], &cpukey
) >= 0);
148 int check_leaf(struct ctree_path
*path
, int level
)
151 struct leaf
*leaf
= &path
->nodes
[level
]->leaf
;
152 struct node
*parent
= NULL
;
154 u32 nritems
= btrfs_header_nritems(&leaf
->header
);
156 if (path
->nodes
[level
+ 1])
157 parent
= &path
->nodes
[level
+ 1]->node
;
158 parent_slot
= path
->slots
[level
+ 1];
159 BUG_ON(leaf_free_space(leaf
) < 0);
165 struct btrfs_disk_key
*parent_key
;
166 parent_key
= &parent
->keys
[parent_slot
];
167 BUG_ON(memcmp(parent_key
, &leaf
->items
[0].key
,
168 sizeof(struct btrfs_disk_key
)));
169 BUG_ON(parent
->blockptrs
[parent_slot
] !=
170 btrfs_header_blocknr(&leaf
->header
));
172 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
173 struct btrfs_key cpukey
;
174 btrfs_disk_key_to_cpu(&cpukey
, &leaf
->items
[i
+ 1].key
);
175 BUG_ON(comp_keys(&leaf
->items
[i
].key
,
177 BUG_ON(btrfs_item_offset(leaf
->items
+ i
) !=
178 btrfs_item_end(leaf
->items
+ i
+ 1));
180 BUG_ON(btrfs_item_offset(leaf
->items
+ i
) +
181 btrfs_item_size(leaf
->items
+ i
) !=
188 int check_block(struct ctree_path
*path
, int level
)
191 return check_leaf(path
, level
);
192 return check_node(path
, level
);
196 * search for key in the array p. items p are item_size apart
197 * and there are 'max' items in p
198 * the slot in the array is returned via slot, and it points to
199 * the place where you would insert key if it is not found in
202 * slot may point to max if the key is bigger than all of the keys
204 int generic_bin_search(char *p
, int item_size
, struct btrfs_key
*key
,
211 struct btrfs_disk_key
*tmp
;
214 mid
= (low
+ high
) / 2;
215 tmp
= (struct btrfs_disk_key
*)(p
+ mid
* item_size
);
216 ret
= comp_keys(tmp
, key
);
232 * simple bin_search frontend that does the right thing for
235 int bin_search(struct node
*c
, struct btrfs_key
*key
, int *slot
)
237 if (btrfs_is_leaf(c
)) {
238 struct leaf
*l
= (struct leaf
*)c
;
239 return generic_bin_search((void *)l
->items
,
240 sizeof(struct btrfs_item
),
241 key
, btrfs_header_nritems(&c
->header
),
244 return generic_bin_search((void *)c
->keys
,
245 sizeof(struct btrfs_disk_key
),
246 key
, btrfs_header_nritems(&c
->header
),
252 struct tree_buffer
*read_node_slot(struct ctree_root
*root
,
253 struct tree_buffer
*parent_buf
,
256 struct node
*node
= &parent_buf
->node
;
259 if (slot
>= btrfs_header_nritems(&node
->header
))
261 return read_tree_block(root
, node
->blockptrs
[slot
]);
264 static int balance_level(struct ctree_root
*root
, struct ctree_path
*path
,
267 struct tree_buffer
*right_buf
;
268 struct tree_buffer
*mid_buf
;
269 struct tree_buffer
*left_buf
;
270 struct tree_buffer
*parent_buf
= NULL
;
271 struct node
*right
= NULL
;
273 struct node
*left
= NULL
;
274 struct node
*parent
= NULL
;
278 int orig_slot
= path
->slots
[level
];
284 mid_buf
= path
->nodes
[level
];
285 mid
= &mid_buf
->node
;
286 orig_ptr
= mid
->blockptrs
[orig_slot
];
288 if (level
< MAX_LEVEL
- 1)
289 parent_buf
= path
->nodes
[level
+ 1];
290 pslot
= path
->slots
[level
+ 1];
293 struct tree_buffer
*child
;
294 u64 blocknr
= mid_buf
->blocknr
;
296 if (btrfs_header_nritems(&mid
->header
) != 1)
299 /* promote the child to a root */
300 child
= read_node_slot(root
, mid_buf
, 0);
303 path
->nodes
[level
] = NULL
;
304 /* once for the path */
305 tree_block_release(root
, mid_buf
);
306 /* once for the root ptr */
307 tree_block_release(root
, mid_buf
);
308 clean_tree_block(root
, mid_buf
);
309 return free_extent(root
, blocknr
, 1);
311 parent
= &parent_buf
->node
;
313 if (btrfs_header_nritems(&mid
->header
) > NODEPTRS_PER_BLOCK
/ 4)
316 left_buf
= read_node_slot(root
, parent_buf
, pslot
- 1);
317 right_buf
= read_node_slot(root
, parent_buf
, pslot
+ 1);
319 /* first, try to make some room in the middle buffer */
321 btrfs_cow_block(root
, left_buf
, parent_buf
,
322 pslot
- 1, &left_buf
);
323 left
= &left_buf
->node
;
324 orig_slot
+= btrfs_header_nritems(&left
->header
);
325 wret
= push_node_left(root
, left_buf
, mid_buf
);
331 * then try to empty the right most buffer into the middle
334 btrfs_cow_block(root
, right_buf
, parent_buf
,
335 pslot
+ 1, &right_buf
);
336 right
= &right_buf
->node
;
337 wret
= push_node_left(root
, mid_buf
, right_buf
);
340 if (btrfs_header_nritems(&right
->header
) == 0) {
341 u64 blocknr
= right_buf
->blocknr
;
342 tree_block_release(root
, right_buf
);
343 clean_tree_block(root
, right_buf
);
346 wret
= del_ptr(root
, path
, level
+ 1, pslot
+ 1);
349 wret
= free_extent(root
, blocknr
, 1);
353 memcpy(parent
->keys
+ pslot
+ 1, right
->keys
,
354 sizeof(struct btrfs_disk_key
));
355 BUG_ON(list_empty(&parent_buf
->dirty
));
358 if (btrfs_header_nritems(&mid
->header
) == 1) {
360 * we're not allowed to leave a node with one item in the
361 * tree during a delete. A deletion from lower in the tree
362 * could try to delete the only pointer in this node.
363 * So, pull some keys from the left.
364 * There has to be a left pointer at this point because
365 * otherwise we would have pulled some pointers from the
369 wret
= balance_node_right(root
, mid_buf
, left_buf
);
374 if (btrfs_header_nritems(&mid
->header
) == 0) {
375 /* we've managed to empty the middle node, drop it */
376 u64 blocknr
= mid_buf
->blocknr
;
377 tree_block_release(root
, mid_buf
);
378 clean_tree_block(root
, mid_buf
);
381 wret
= del_ptr(root
, path
, level
+ 1, pslot
);
384 wret
= free_extent(root
, blocknr
, 1);
388 /* update the parent key to reflect our changes */
389 memcpy(parent
->keys
+ pslot
, mid
->keys
,
390 sizeof(struct btrfs_disk_key
));
391 BUG_ON(list_empty(&parent_buf
->dirty
));
394 /* update the path */
396 if (btrfs_header_nritems(&left
->header
) > orig_slot
) {
397 left_buf
->count
++; // released below
398 path
->nodes
[level
] = left_buf
;
399 path
->slots
[level
+ 1] -= 1;
400 path
->slots
[level
] = orig_slot
;
402 tree_block_release(root
, mid_buf
);
404 orig_slot
-= btrfs_header_nritems(&left
->header
);
405 path
->slots
[level
] = orig_slot
;
408 /* double check we haven't messed things up */
409 check_block(path
, level
);
410 if (orig_ptr
!= path
->nodes
[level
]->node
.blockptrs
[path
->slots
[level
]])
414 tree_block_release(root
, right_buf
);
416 tree_block_release(root
, left_buf
);
421 * look for key in the tree. path is filled in with nodes along the way
422 * if key is found, we return zero and you can find the item in the leaf
423 * level of the path (level 0)
425 * If the key isn't found, the path points to the slot where it should
426 * be inserted, and 1 is returned. If there are other errors during the
427 * search a negative error number is returned.
429 * if ins_len > 0, nodes and leaves will be split as we walk down the
430 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
433 int search_slot(struct ctree_root
*root
, struct btrfs_key
*key
,
434 struct ctree_path
*p
, int ins_len
, int cow
)
436 struct tree_buffer
*b
;
437 struct tree_buffer
*cow_buf
;
447 level
= btrfs_header_level(&b
->node
.header
);
450 wret
= btrfs_cow_block(root
, b
, p
->nodes
[level
+ 1],
451 p
->slots
[level
+ 1], &cow_buf
);
454 BUG_ON(!cow
&& ins_len
);
457 ret
= check_block(p
, level
);
460 ret
= bin_search(c
, key
, &slot
);
461 if (!btrfs_is_leaf(c
)) {
464 p
->slots
[level
] = slot
;
465 if (ins_len
> 0 && btrfs_header_nritems(&c
->header
) ==
466 NODEPTRS_PER_BLOCK
) {
467 int sret
= split_node(root
, p
, level
);
473 slot
= p
->slots
[level
];
474 } else if (ins_len
< 0) {
475 int sret
= balance_level(root
, p
, level
);
482 slot
= p
->slots
[level
];
483 BUG_ON(btrfs_header_nritems(&c
->header
) == 1);
485 b
= read_tree_block(root
, c
->blockptrs
[slot
]);
487 struct leaf
*l
= (struct leaf
*)c
;
488 p
->slots
[level
] = slot
;
489 if (ins_len
> 0 && leaf_free_space(l
) <
490 sizeof(struct btrfs_item
) + ins_len
) {
491 int sret
= split_leaf(root
, p
, ins_len
);
496 BUG_ON(root
->node
->count
== 1);
500 BUG_ON(root
->node
->count
== 1);
505 * adjust the pointers going up the tree, starting at level
506 * making sure the right key of each node is points to 'key'.
507 * This is used after shifting pointers to the left, so it stops
508 * fixing up pointers when a given leaf/node is not in slot 0 of the
511 * If this fails to write a tree block, it returns -1, but continues
512 * fixing up the blocks in ram so the tree is consistent.
514 static int fixup_low_keys(struct ctree_root
*root
,
515 struct ctree_path
*path
, struct btrfs_disk_key
*key
,
520 for (i
= level
; i
< MAX_LEVEL
; i
++) {
522 int tslot
= path
->slots
[i
];
525 t
= &path
->nodes
[i
]->node
;
526 memcpy(t
->keys
+ tslot
, key
, sizeof(*key
));
527 BUG_ON(list_empty(&path
->nodes
[i
]->dirty
));
535 * try to push data from one node into the next node left in the
538 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
539 * error, and > 0 if there was no room in the left hand block.
541 static int push_node_left(struct ctree_root
*root
, struct tree_buffer
*dst_buf
,
542 struct tree_buffer
*src_buf
)
544 struct node
*src
= &src_buf
->node
;
545 struct node
*dst
= &dst_buf
->node
;
551 src_nritems
= btrfs_header_nritems(&src
->header
);
552 dst_nritems
= btrfs_header_nritems(&dst
->header
);
553 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
554 if (push_items
<= 0) {
558 if (src_nritems
< push_items
)
559 push_items
= src_nritems
;
561 memcpy(dst
->keys
+ dst_nritems
, src
->keys
,
562 push_items
* sizeof(struct btrfs_disk_key
));
563 memcpy(dst
->blockptrs
+ dst_nritems
, src
->blockptrs
,
564 push_items
* sizeof(u64
));
565 if (push_items
< src_nritems
) {
566 memmove(src
->keys
, src
->keys
+ push_items
,
567 (src_nritems
- push_items
) *
568 sizeof(struct btrfs_disk_key
));
569 memmove(src
->blockptrs
, src
->blockptrs
+ push_items
,
570 (src_nritems
- push_items
) * sizeof(u64
));
572 btrfs_set_header_nritems(&src
->header
, src_nritems
- push_items
);
573 btrfs_set_header_nritems(&dst
->header
, dst_nritems
+ push_items
);
574 BUG_ON(list_empty(&src_buf
->dirty
));
575 BUG_ON(list_empty(&dst_buf
->dirty
));
580 * try to push data from one node into the next node right in the
583 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
584 * error, and > 0 if there was no room in the right hand block.
586 * this will only push up to 1/2 the contents of the left node over
588 static int balance_node_right(struct ctree_root
*root
,
589 struct tree_buffer
*dst_buf
,
590 struct tree_buffer
*src_buf
)
592 struct node
*src
= &src_buf
->node
;
593 struct node
*dst
= &dst_buf
->node
;
600 src_nritems
= btrfs_header_nritems(&src
->header
);
601 dst_nritems
= btrfs_header_nritems(&dst
->header
);
602 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
603 if (push_items
<= 0) {
607 max_push
= src_nritems
/ 2 + 1;
608 /* don't try to empty the node */
609 if (max_push
> src_nritems
)
611 if (max_push
< push_items
)
612 push_items
= max_push
;
614 memmove(dst
->keys
+ push_items
, dst
->keys
,
615 dst_nritems
* sizeof(struct btrfs_disk_key
));
616 memmove(dst
->blockptrs
+ push_items
, dst
->blockptrs
,
617 dst_nritems
* sizeof(u64
));
618 memcpy(dst
->keys
, src
->keys
+ src_nritems
- push_items
,
619 push_items
* sizeof(struct btrfs_disk_key
));
620 memcpy(dst
->blockptrs
, src
->blockptrs
+ src_nritems
- push_items
,
621 push_items
* sizeof(u64
));
623 btrfs_set_header_nritems(&src
->header
, src_nritems
- push_items
);
624 btrfs_set_header_nritems(&dst
->header
, dst_nritems
+ push_items
);
626 BUG_ON(list_empty(&src_buf
->dirty
));
627 BUG_ON(list_empty(&dst_buf
->dirty
));
632 * helper function to insert a new root level in the tree.
633 * A new node is allocated, and a single item is inserted to
634 * point to the existing root
636 * returns zero on success or < 0 on failure.
638 static int insert_new_root(struct ctree_root
*root
,
639 struct ctree_path
*path
, int level
)
641 struct tree_buffer
*t
;
644 struct btrfs_disk_key
*lower_key
;
646 BUG_ON(path
->nodes
[level
]);
647 BUG_ON(path
->nodes
[level
-1] != root
->node
);
649 t
= alloc_free_block(root
);
651 memset(c
, 0, sizeof(c
));
652 btrfs_set_header_nritems(&c
->header
, 1);
653 btrfs_set_header_level(&c
->header
, level
);
654 btrfs_set_header_blocknr(&c
->header
, t
->blocknr
);
655 btrfs_set_header_parentid(&c
->header
,
656 btrfs_header_parentid(&root
->node
->node
.header
));
657 lower
= &path
->nodes
[level
-1]->node
;
658 if (btrfs_is_leaf(lower
))
659 lower_key
= &((struct leaf
*)lower
)->items
[0].key
;
661 lower_key
= lower
->keys
;
662 memcpy(c
->keys
, lower_key
, sizeof(struct btrfs_disk_key
));
663 c
->blockptrs
[0] = path
->nodes
[level
-1]->blocknr
;
664 /* the super has an extra ref to root->node */
665 tree_block_release(root
, root
->node
);
668 path
->nodes
[level
] = t
;
669 path
->slots
[level
] = 0;
674 * worker function to insert a single pointer in a node.
675 * the node should have enough room for the pointer already
677 * slot and level indicate where you want the key to go, and
678 * blocknr is the block the key points to.
680 * returns zero on success and < 0 on any error
682 static int insert_ptr(struct ctree_root
*root
,
683 struct ctree_path
*path
, struct btrfs_disk_key
*key
,
684 u64 blocknr
, int slot
, int level
)
689 BUG_ON(!path
->nodes
[level
]);
690 lower
= &path
->nodes
[level
]->node
;
691 nritems
= btrfs_header_nritems(&lower
->header
);
694 if (nritems
== NODEPTRS_PER_BLOCK
)
696 if (slot
!= nritems
) {
697 memmove(lower
->keys
+ slot
+ 1, lower
->keys
+ slot
,
698 (nritems
- slot
) * sizeof(struct btrfs_disk_key
));
699 memmove(lower
->blockptrs
+ slot
+ 1, lower
->blockptrs
+ slot
,
700 (nritems
- slot
) * sizeof(u64
));
702 memcpy(lower
->keys
+ slot
, key
, sizeof(struct btrfs_disk_key
));
703 lower
->blockptrs
[slot
] = blocknr
;
704 btrfs_set_header_nritems(&lower
->header
, nritems
+ 1);
705 if (lower
->keys
[1].objectid
== 0)
707 BUG_ON(list_empty(&path
->nodes
[level
]->dirty
));
712 * split the node at the specified level in path in two.
713 * The path is corrected to point to the appropriate node after the split
715 * Before splitting this tries to make some room in the node by pushing
716 * left and right, if either one works, it returns right away.
718 * returns 0 on success and < 0 on failure
720 static int split_node(struct ctree_root
*root
, struct ctree_path
*path
,
723 struct tree_buffer
*t
;
725 struct tree_buffer
*split_buffer
;
732 t
= path
->nodes
[level
];
734 if (t
== root
->node
) {
735 /* trying to split the root, lets make a new one */
736 ret
= insert_new_root(root
, path
, level
+ 1);
740 c_nritems
= btrfs_header_nritems(&c
->header
);
741 split_buffer
= alloc_free_block(root
);
742 split
= &split_buffer
->node
;
743 btrfs_set_header_flags(&split
->header
, btrfs_header_flags(&c
->header
));
744 btrfs_set_header_blocknr(&split
->header
, split_buffer
->blocknr
);
745 btrfs_set_header_parentid(&split
->header
,
746 btrfs_header_parentid(&root
->node
->node
.header
));
747 mid
= (c_nritems
+ 1) / 2;
748 memcpy(split
->keys
, c
->keys
+ mid
,
749 (c_nritems
- mid
) * sizeof(struct btrfs_disk_key
));
750 memcpy(split
->blockptrs
, c
->blockptrs
+ mid
,
751 (c_nritems
- mid
) * sizeof(u64
));
752 btrfs_set_header_nritems(&split
->header
, c_nritems
- mid
);
753 btrfs_set_header_nritems(&c
->header
, mid
);
756 BUG_ON(list_empty(&t
->dirty
));
757 wret
= insert_ptr(root
, path
, split
->keys
, split_buffer
->blocknr
,
758 path
->slots
[level
+ 1] + 1, level
+ 1);
762 if (path
->slots
[level
] >= mid
) {
763 path
->slots
[level
] -= mid
;
764 tree_block_release(root
, t
);
765 path
->nodes
[level
] = split_buffer
;
766 path
->slots
[level
+ 1] += 1;
768 tree_block_release(root
, split_buffer
);
774 * how many bytes are required to store the items in a leaf. start
775 * and nr indicate which items in the leaf to check. This totals up the
776 * space used both by the item structs and the item data
778 static int leaf_space_used(struct leaf
*l
, int start
, int nr
)
781 int end
= start
+ nr
- 1;
785 data_len
= btrfs_item_end(l
->items
+ start
);
786 data_len
= data_len
- btrfs_item_offset(l
->items
+ end
);
787 data_len
+= sizeof(struct btrfs_item
) * nr
;
792 * push some data in the path leaf to the right, trying to free up at
793 * least data_size bytes. returns zero if the push worked, nonzero otherwise
795 * returns 1 if the push failed because the other node didn't have enough
796 * room, 0 if everything worked out and < 0 if there were major errors.
798 static int push_leaf_right(struct ctree_root
*root
, struct ctree_path
*path
,
801 struct tree_buffer
*left_buf
= path
->nodes
[0];
802 struct leaf
*left
= &left_buf
->leaf
;
804 struct tree_buffer
*right_buf
;
805 struct tree_buffer
*upper
;
811 struct btrfs_item
*item
;
815 slot
= path
->slots
[1];
816 if (!path
->nodes
[1]) {
819 upper
= path
->nodes
[1];
820 if (slot
>= btrfs_header_nritems(&upper
->node
.header
) - 1) {
823 right_buf
= read_tree_block(root
, upper
->node
.blockptrs
[slot
+ 1]);
824 right
= &right_buf
->leaf
;
825 free_space
= leaf_free_space(right
);
826 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
827 tree_block_release(root
, right_buf
);
830 /* cow and double check */
831 btrfs_cow_block(root
, right_buf
, upper
, slot
+ 1, &right_buf
);
832 right
= &right_buf
->leaf
;
833 free_space
= leaf_free_space(right
);
834 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
835 tree_block_release(root
, right_buf
);
839 left_nritems
= btrfs_header_nritems(&left
->header
);
840 for (i
= left_nritems
- 1; i
>= 0; i
--) {
841 item
= left
->items
+ i
;
842 if (path
->slots
[0] == i
)
843 push_space
+= data_size
+ sizeof(*item
);
844 if (btrfs_item_size(item
) + sizeof(*item
) + push_space
>
848 push_space
+= btrfs_item_size(item
) + sizeof(*item
);
850 if (push_items
== 0) {
851 tree_block_release(root
, right_buf
);
854 right_nritems
= btrfs_header_nritems(&right
->header
);
855 /* push left to right */
856 push_space
= btrfs_item_end(left
->items
+ left_nritems
- push_items
);
857 push_space
-= leaf_data_end(left
);
858 /* make room in the right data area */
859 memmove(right
->data
+ leaf_data_end(right
) - push_space
,
860 right
->data
+ leaf_data_end(right
),
861 LEAF_DATA_SIZE
- leaf_data_end(right
));
862 /* copy from the left data area */
863 memcpy(right
->data
+ LEAF_DATA_SIZE
- push_space
,
864 left
->data
+ leaf_data_end(left
),
866 memmove(right
->items
+ push_items
, right
->items
,
867 right_nritems
* sizeof(struct btrfs_item
));
868 /* copy the items from left to right */
869 memcpy(right
->items
, left
->items
+ left_nritems
- push_items
,
870 push_items
* sizeof(struct btrfs_item
));
872 /* update the item pointers */
873 right_nritems
+= push_items
;
874 btrfs_set_header_nritems(&right
->header
, right_nritems
);
875 push_space
= LEAF_DATA_SIZE
;
876 for (i
= 0; i
< right_nritems
; i
++) {
877 btrfs_set_item_offset(right
->items
+ i
, push_space
-
878 btrfs_item_size(right
->items
+ i
));
879 push_space
= btrfs_item_offset(right
->items
+ i
);
881 left_nritems
-= push_items
;
882 btrfs_set_header_nritems(&left
->header
, left_nritems
);
884 BUG_ON(list_empty(&left_buf
->dirty
));
885 BUG_ON(list_empty(&right_buf
->dirty
));
886 memcpy(upper
->node
.keys
+ slot
+ 1,
887 &right
->items
[0].key
, sizeof(struct btrfs_disk_key
));
888 BUG_ON(list_empty(&upper
->dirty
));
890 /* then fixup the leaf pointer in the path */
891 if (path
->slots
[0] >= left_nritems
) {
892 path
->slots
[0] -= left_nritems
;
893 tree_block_release(root
, path
->nodes
[0]);
894 path
->nodes
[0] = right_buf
;
897 tree_block_release(root
, right_buf
);
902 * push some data in the path leaf to the left, trying to free up at
903 * least data_size bytes. returns zero if the push worked, nonzero otherwise
905 static int push_leaf_left(struct ctree_root
*root
, struct ctree_path
*path
,
908 struct tree_buffer
*right_buf
= path
->nodes
[0];
909 struct leaf
*right
= &right_buf
->leaf
;
910 struct tree_buffer
*t
;
917 struct btrfs_item
*item
;
918 u32 old_left_nritems
;
922 slot
= path
->slots
[1];
926 if (!path
->nodes
[1]) {
929 t
= read_tree_block(root
, path
->nodes
[1]->node
.blockptrs
[slot
- 1]);
931 free_space
= leaf_free_space(left
);
932 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
933 tree_block_release(root
, t
);
937 /* cow and double check */
938 btrfs_cow_block(root
, t
, path
->nodes
[1], slot
- 1, &t
);
940 free_space
= leaf_free_space(left
);
941 if (free_space
< data_size
+ sizeof(struct btrfs_item
)) {
942 tree_block_release(root
, t
);
946 for (i
= 0; i
< btrfs_header_nritems(&right
->header
); i
++) {
947 item
= right
->items
+ i
;
948 if (path
->slots
[0] == i
)
949 push_space
+= data_size
+ sizeof(*item
);
950 if (btrfs_item_size(item
) + sizeof(*item
) + push_space
>
954 push_space
+= btrfs_item_size(item
) + sizeof(*item
);
956 if (push_items
== 0) {
957 tree_block_release(root
, t
);
960 /* push data from right to left */
961 memcpy(left
->items
+ btrfs_header_nritems(&left
->header
),
962 right
->items
, push_items
* sizeof(struct btrfs_item
));
963 push_space
= LEAF_DATA_SIZE
-
964 btrfs_item_offset(right
->items
+ push_items
-1);
965 memcpy(left
->data
+ leaf_data_end(left
) - push_space
,
966 right
->data
+ btrfs_item_offset(right
->items
+ push_items
- 1),
968 old_left_nritems
= btrfs_header_nritems(&left
->header
);
969 BUG_ON(old_left_nritems
< 0);
971 for (i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
972 u16 ioff
= btrfs_item_offset(left
->items
+ i
);
973 btrfs_set_item_offset(left
->items
+ i
, ioff
- (LEAF_DATA_SIZE
-
974 btrfs_item_offset(left
->items
+
975 old_left_nritems
- 1)));
977 btrfs_set_header_nritems(&left
->header
, old_left_nritems
+ push_items
);
979 /* fixup right node */
980 push_space
= btrfs_item_offset(right
->items
+ push_items
- 1) -
981 leaf_data_end(right
);
982 memmove(right
->data
+ LEAF_DATA_SIZE
- push_space
, right
->data
+
983 leaf_data_end(right
), push_space
);
984 memmove(right
->items
, right
->items
+ push_items
,
985 (btrfs_header_nritems(&right
->header
) - push_items
) *
986 sizeof(struct btrfs_item
));
987 btrfs_set_header_nritems(&right
->header
,
988 btrfs_header_nritems(&right
->header
) -
990 push_space
= LEAF_DATA_SIZE
;
992 for (i
= 0; i
< btrfs_header_nritems(&right
->header
); i
++) {
993 btrfs_set_item_offset(right
->items
+ i
, push_space
-
994 btrfs_item_size(right
->items
+ i
));
995 push_space
= btrfs_item_offset(right
->items
+ i
);
998 BUG_ON(list_empty(&t
->dirty
));
999 BUG_ON(list_empty(&right_buf
->dirty
));
1001 wret
= fixup_low_keys(root
, path
, &right
->items
[0].key
, 1);
1005 /* then fixup the leaf pointer in the path */
1006 if (path
->slots
[0] < push_items
) {
1007 path
->slots
[0] += old_left_nritems
;
1008 tree_block_release(root
, path
->nodes
[0]);
1010 path
->slots
[1] -= 1;
1012 tree_block_release(root
, t
);
1013 path
->slots
[0] -= push_items
;
1015 BUG_ON(path
->slots
[0] < 0);
1020 * split the path's leaf in two, making sure there is at least data_size
1021 * available for the resulting leaf level of the path.
1023 * returns 0 if all went well and < 0 on failure.
1025 static int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
,
1028 struct tree_buffer
*l_buf
;
1034 struct tree_buffer
*right_buffer
;
1035 int space_needed
= data_size
+ sizeof(struct btrfs_item
);
1042 l_buf
= path
->nodes
[0];
1045 /* did the pushes work? */
1046 if (leaf_free_space(l
) >= sizeof(struct btrfs_item
) + data_size
)
1049 if (!path
->nodes
[1]) {
1050 ret
= insert_new_root(root
, path
, 1);
1054 slot
= path
->slots
[0];
1055 nritems
= btrfs_header_nritems(&l
->header
);
1056 mid
= (nritems
+ 1)/ 2;
1057 right_buffer
= alloc_free_block(root
);
1058 BUG_ON(!right_buffer
);
1059 BUG_ON(mid
== nritems
);
1060 right
= &right_buffer
->leaf
;
1061 memset(right
, 0, sizeof(*right
));
1063 /* FIXME, just alloc a new leaf here */
1064 if (leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
1068 /* FIXME, just alloc a new leaf here */
1069 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
1073 btrfs_set_header_nritems(&right
->header
, nritems
- mid
);
1074 btrfs_set_header_blocknr(&right
->header
, right_buffer
->blocknr
);
1075 btrfs_set_header_level(&right
->header
, 0);
1076 btrfs_set_header_parentid(&right
->header
,
1077 btrfs_header_parentid(&root
->node
->node
.header
));
1078 data_copy_size
= btrfs_item_end(l
->items
+ mid
) - leaf_data_end(l
);
1079 memcpy(right
->items
, l
->items
+ mid
,
1080 (nritems
- mid
) * sizeof(struct btrfs_item
));
1081 memcpy(right
->data
+ LEAF_DATA_SIZE
- data_copy_size
,
1082 l
->data
+ leaf_data_end(l
), data_copy_size
);
1083 rt_data_off
= LEAF_DATA_SIZE
- btrfs_item_end(l
->items
+ mid
);
1085 for (i
= 0; i
< btrfs_header_nritems(&right
->header
); i
++) {
1086 u16 ioff
= btrfs_item_offset(right
->items
+ i
);
1087 btrfs_set_item_offset(right
->items
+ i
, ioff
+ rt_data_off
);
1090 btrfs_set_header_nritems(&l
->header
, mid
);
1092 wret
= insert_ptr(root
, path
, &right
->items
[0].key
,
1093 right_buffer
->blocknr
, path
->slots
[1] + 1, 1);
1096 BUG_ON(list_empty(&right_buffer
->dirty
));
1097 BUG_ON(list_empty(&l_buf
->dirty
));
1098 BUG_ON(path
->slots
[0] != slot
);
1100 tree_block_release(root
, path
->nodes
[0]);
1101 path
->nodes
[0] = right_buffer
;
1102 path
->slots
[0] -= mid
;
1103 path
->slots
[1] += 1;
1105 tree_block_release(root
, right_buffer
);
1106 BUG_ON(path
->slots
[0] < 0);
1111 * Given a key and some data, insert an item into the tree.
1112 * This does all the path init required, making room in the tree if needed.
1114 int insert_item(struct ctree_root
*root
, struct btrfs_key
*cpu_key
,
1115 void *data
, int data_size
)
1121 struct tree_buffer
*leaf_buf
;
1123 unsigned int data_end
;
1124 struct ctree_path path
;
1125 struct btrfs_disk_key disk_key
;
1127 btrfs_cpu_key_to_disk(&disk_key
, cpu_key
);
1129 /* create a root if there isn't one */
1133 ret
= search_slot(root
, cpu_key
, &path
, data_size
, 1);
1135 release_path(root
, &path
);
1141 slot_orig
= path
.slots
[0];
1142 leaf_buf
= path
.nodes
[0];
1143 leaf
= &leaf_buf
->leaf
;
1145 nritems
= btrfs_header_nritems(&leaf
->header
);
1146 data_end
= leaf_data_end(leaf
);
1148 if (leaf_free_space(leaf
) < sizeof(struct btrfs_item
) + data_size
)
1151 slot
= path
.slots
[0];
1153 if (slot
!= nritems
) {
1155 unsigned int old_data
= btrfs_item_end(leaf
->items
+ slot
);
1158 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1160 /* first correct the data pointers */
1161 for (i
= slot
; i
< nritems
; i
++) {
1162 u16 ioff
= btrfs_item_offset(leaf
->items
+ i
);
1163 btrfs_set_item_offset(leaf
->items
+ i
,
1167 /* shift the items */
1168 memmove(leaf
->items
+ slot
+ 1, leaf
->items
+ slot
,
1169 (nritems
- slot
) * sizeof(struct btrfs_item
));
1171 /* shift the data */
1172 memmove(leaf
->data
+ data_end
- data_size
, leaf
->data
+
1173 data_end
, old_data
- data_end
);
1174 data_end
= old_data
;
1176 /* copy the new data in */
1177 memcpy(&leaf
->items
[slot
].key
, &disk_key
,
1178 sizeof(struct btrfs_disk_key
));
1179 btrfs_set_item_offset(leaf
->items
+ slot
, data_end
- data_size
);
1180 btrfs_set_item_size(leaf
->items
+ slot
, data_size
);
1181 memcpy(leaf
->data
+ data_end
- data_size
, data
, data_size
);
1182 btrfs_set_header_nritems(&leaf
->header
, nritems
+ 1);
1186 ret
= fixup_low_keys(root
, &path
, &disk_key
, 1);
1188 BUG_ON(list_empty(&leaf_buf
->dirty
));
1189 if (leaf_free_space(leaf
) < 0)
1191 check_leaf(&path
, 0);
1193 release_path(root
, &path
);
1198 * delete the pointer from a given node.
1200 * If the delete empties a node, the node is removed from the tree,
1201 * continuing all the way the root if required. The root is converted into
1202 * a leaf if all the nodes are emptied.
1204 static int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
,
1208 struct tree_buffer
*parent
= path
->nodes
[level
];
1213 node
= &parent
->node
;
1214 nritems
= btrfs_header_nritems(&node
->header
);
1215 if (slot
!= nritems
-1) {
1216 memmove(node
->keys
+ slot
, node
->keys
+ slot
+ 1,
1217 sizeof(struct btrfs_disk_key
) * (nritems
- slot
- 1));
1218 memmove(node
->blockptrs
+ slot
,
1219 node
->blockptrs
+ slot
+ 1,
1220 sizeof(u64
) * (nritems
- slot
- 1));
1223 btrfs_set_header_nritems(&node
->header
, nritems
);
1224 if (nritems
== 0 && parent
== root
->node
) {
1225 BUG_ON(btrfs_header_level(&root
->node
->node
.header
) != 1);
1226 /* just turn the root into a leaf and break */
1227 btrfs_set_header_level(&root
->node
->node
.header
, 0);
1228 } else if (slot
== 0) {
1229 wret
= fixup_low_keys(root
, path
, node
->keys
, level
+ 1);
1233 BUG_ON(list_empty(&parent
->dirty
));
1238 * delete the item at the leaf level in path. If that empties
1239 * the leaf, remove it from the tree
1241 int del_item(struct ctree_root
*root
, struct ctree_path
*path
)
1245 struct tree_buffer
*leaf_buf
;
1252 leaf_buf
= path
->nodes
[0];
1253 leaf
= &leaf_buf
->leaf
;
1254 slot
= path
->slots
[0];
1255 doff
= btrfs_item_offset(leaf
->items
+ slot
);
1256 dsize
= btrfs_item_size(leaf
->items
+ slot
);
1257 nritems
= btrfs_header_nritems(&leaf
->header
);
1259 if (slot
!= nritems
- 1) {
1261 int data_end
= leaf_data_end(leaf
);
1262 memmove(leaf
->data
+ data_end
+ dsize
,
1263 leaf
->data
+ data_end
,
1265 for (i
= slot
+ 1; i
< nritems
; i
++) {
1266 u16 ioff
= btrfs_item_offset(leaf
->items
+ i
);
1267 btrfs_set_item_offset(leaf
->items
+ i
, ioff
+ dsize
);
1269 memmove(leaf
->items
+ slot
, leaf
->items
+ slot
+ 1,
1270 sizeof(struct btrfs_item
) *
1271 (nritems
- slot
- 1));
1273 btrfs_set_header_nritems(&leaf
->header
, nritems
- 1);
1275 /* delete the leaf if we've emptied it */
1277 if (leaf_buf
== root
->node
) {
1278 btrfs_set_header_level(&leaf
->header
, 0);
1279 BUG_ON(list_empty(&leaf_buf
->dirty
));
1281 clean_tree_block(root
, leaf_buf
);
1282 wret
= del_ptr(root
, path
, 1, path
->slots
[1]);
1285 wret
= free_extent(root
, leaf_buf
->blocknr
, 1);
1290 int used
= leaf_space_used(leaf
, 0, nritems
);
1292 wret
= fixup_low_keys(root
, path
,
1293 &leaf
->items
[0].key
, 1);
1297 BUG_ON(list_empty(&leaf_buf
->dirty
));
1299 /* delete the leaf if it is mostly empty */
1300 if (used
< LEAF_DATA_SIZE
/ 3) {
1301 /* push_leaf_left fixes the path.
1302 * make sure the path still points to our leaf
1303 * for possible call to del_ptr below
1305 slot
= path
->slots
[1];
1307 wret
= push_leaf_left(root
, path
, 1);
1310 if (path
->nodes
[0] == leaf_buf
&&
1311 btrfs_header_nritems(&leaf
->header
)) {
1312 wret
= push_leaf_right(root
, path
, 1);
1316 if (btrfs_header_nritems(&leaf
->header
) == 0) {
1317 u64 blocknr
= leaf_buf
->blocknr
;
1318 clean_tree_block(root
, leaf_buf
);
1319 wret
= del_ptr(root
, path
, 1, slot
);
1322 tree_block_release(root
, leaf_buf
);
1323 wret
= free_extent(root
, blocknr
, 1);
1327 tree_block_release(root
, leaf_buf
);
1335 * walk up the tree as far as required to find the next leaf.
1336 * returns 0 if it found something or 1 if there are no greater leaves.
1337 * returns < 0 on io errors.
1339 int next_leaf(struct ctree_root
*root
, struct ctree_path
*path
)
1344 struct tree_buffer
*c
;
1345 struct tree_buffer
*next
= NULL
;
1347 while(level
< MAX_LEVEL
) {
1348 if (!path
->nodes
[level
])
1350 slot
= path
->slots
[level
] + 1;
1351 c
= path
->nodes
[level
];
1352 if (slot
>= btrfs_header_nritems(&c
->node
.header
)) {
1356 blocknr
= c
->node
.blockptrs
[slot
];
1358 tree_block_release(root
, next
);
1359 next
= read_tree_block(root
, blocknr
);
1362 path
->slots
[level
] = slot
;
1365 c
= path
->nodes
[level
];
1366 tree_block_release(root
, c
);
1367 path
->nodes
[level
] = next
;
1368 path
->slots
[level
] = 0;
1371 next
= read_tree_block(root
, next
->node
.blockptrs
[0]);
This page took 0.065969 seconds and 6 git commands to generate.