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 cow
->node
.header
.blocknr
= 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 unsigned int nr
= leaf
->header
.nritems
;
78 return sizeof(leaf
->data
);
79 return leaf
->items
[nr
-1].offset
;
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
= leaf
->header
.nritems
;
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 key
*k1
, struct key
*k2
)
100 if (k1
->objectid
> k2
->objectid
)
102 if (k1
->objectid
< k2
->objectid
)
104 if (k1
->flags
> k2
->flags
)
106 if (k1
->flags
< k2
->flags
)
108 if (k1
->offset
> k2
->offset
)
110 if (k1
->offset
< k2
->offset
)
115 int check_node(struct ctree_path
*path
, int level
)
118 struct node
*parent
= NULL
;
119 struct node
*node
= &path
->nodes
[level
]->node
;
122 if (path
->nodes
[level
+ 1])
123 parent
= &path
->nodes
[level
+ 1]->node
;
124 parent_slot
= path
->slots
[level
+ 1];
125 if (parent
&& node
->header
.nritems
> 0) {
126 struct key
*parent_key
;
127 parent_key
= &parent
->keys
[parent_slot
];
128 BUG_ON(memcmp(parent_key
, node
->keys
, sizeof(struct key
)));
129 BUG_ON(parent
->blockptrs
[parent_slot
] != node
->header
.blocknr
);
131 BUG_ON(node
->header
.nritems
> NODEPTRS_PER_BLOCK
);
132 for (i
= 0; i
< node
->header
.nritems
- 2; i
++) {
133 BUG_ON(comp_keys(&node
->keys
[i
], &node
->keys
[i
+1]) >= 0);
138 int check_leaf(struct ctree_path
*path
, int level
)
141 struct leaf
*leaf
= &path
->nodes
[level
]->leaf
;
142 struct node
*parent
= NULL
;
145 if (path
->nodes
[level
+ 1])
146 parent
= &path
->nodes
[level
+ 1]->node
;
147 parent_slot
= path
->slots
[level
+ 1];
148 if (parent
&& leaf
->header
.nritems
> 0) {
149 struct key
*parent_key
;
150 parent_key
= &parent
->keys
[parent_slot
];
151 BUG_ON(memcmp(parent_key
, &leaf
->items
[0].key
,
152 sizeof(struct key
)));
153 BUG_ON(parent
->blockptrs
[parent_slot
] != leaf
->header
.blocknr
);
155 for (i
= 0; i
< leaf
->header
.nritems
- 2; i
++) {
156 BUG_ON(comp_keys(&leaf
->items
[i
].key
,
157 &leaf
->items
[i
+1].key
) >= 0);
158 BUG_ON(leaf
->items
[i
].offset
!= leaf
->items
[i
+ 1].offset
+
159 leaf
->items
[i
+ 1].size
);
161 BUG_ON(leaf
->items
[i
].offset
+ leaf
->items
[i
].size
!=
165 BUG_ON(leaf_free_space(leaf
) < 0);
169 int check_block(struct ctree_path
*path
, int level
)
172 return check_leaf(path
, level
);
173 return check_node(path
, level
);
177 * search for key in the array p. items p are item_size apart
178 * and there are 'max' items in p
179 * the slot in the array is returned via slot, and it points to
180 * the place where you would insert key if it is not found in
183 * slot may point to max if the key is bigger than all of the keys
185 int generic_bin_search(char *p
, int item_size
, struct key
*key
,
195 mid
= (low
+ high
) / 2;
196 tmp
= (struct key
*)(p
+ mid
* item_size
);
197 ret
= comp_keys(tmp
, key
);
213 * simple bin_search frontend that does the right thing for
216 int bin_search(struct node
*c
, struct key
*key
, int *slot
)
218 if (is_leaf(c
->header
.flags
)) {
219 struct leaf
*l
= (struct leaf
*)c
;
220 return generic_bin_search((void *)l
->items
, sizeof(struct item
),
221 key
, c
->header
.nritems
, slot
);
223 return generic_bin_search((void *)c
->keys
, sizeof(struct key
),
224 key
, c
->header
.nritems
, slot
);
229 struct tree_buffer
*read_node_slot(struct ctree_root
*root
,
230 struct tree_buffer
*parent_buf
,
233 struct node
*node
= &parent_buf
->node
;
236 if (slot
>= node
->header
.nritems
)
238 return read_tree_block(root
, node
->blockptrs
[slot
]);
241 static int balance_level(struct ctree_root
*root
, struct ctree_path
*path
,
244 struct tree_buffer
*right_buf
;
245 struct tree_buffer
*mid_buf
;
246 struct tree_buffer
*left_buf
;
247 struct tree_buffer
*parent_buf
= NULL
;
248 struct node
*right
= NULL
;
250 struct node
*left
= NULL
;
251 struct node
*parent
= NULL
;
255 int orig_slot
= path
->slots
[level
];
261 mid_buf
= path
->nodes
[level
];
262 mid
= &mid_buf
->node
;
263 orig_ptr
= mid
->blockptrs
[orig_slot
];
265 if (level
< MAX_LEVEL
- 1)
266 parent_buf
= path
->nodes
[level
+ 1];
267 pslot
= path
->slots
[level
+ 1];
270 struct tree_buffer
*child
;
271 u64 blocknr
= mid_buf
->blocknr
;
273 if (mid
->header
.nritems
!= 1)
276 /* promote the child to a root */
277 child
= read_node_slot(root
, mid_buf
, 0);
280 path
->nodes
[level
] = NULL
;
281 /* once for the path */
282 tree_block_release(root
, mid_buf
);
283 /* once for the root ptr */
284 tree_block_release(root
, mid_buf
);
285 clean_tree_block(root
, mid_buf
);
286 return free_extent(root
, blocknr
, 1);
288 parent
= &parent_buf
->node
;
290 if (mid
->header
.nritems
> NODEPTRS_PER_BLOCK
/ 4)
293 left_buf
= read_node_slot(root
, parent_buf
, pslot
- 1);
294 right_buf
= read_node_slot(root
, parent_buf
, pslot
+ 1);
296 /* first, try to make some room in the middle buffer */
298 btrfs_cow_block(root
, left_buf
, parent_buf
,
299 pslot
- 1, &left_buf
);
300 left
= &left_buf
->node
;
301 orig_slot
+= left
->header
.nritems
;
302 wret
= push_node_left(root
, left_buf
, mid_buf
);
308 * then try to empty the right most buffer into the middle
311 btrfs_cow_block(root
, right_buf
, parent_buf
,
312 pslot
+ 1, &right_buf
);
313 right
= &right_buf
->node
;
314 wret
= push_node_left(root
, mid_buf
, right_buf
);
317 if (right
->header
.nritems
== 0) {
318 u64 blocknr
= right_buf
->blocknr
;
319 tree_block_release(root
, right_buf
);
320 clean_tree_block(root
, right_buf
);
323 wret
= del_ptr(root
, path
, level
+ 1, pslot
+ 1);
326 wret
= free_extent(root
, blocknr
, 1);
330 memcpy(parent
->keys
+ pslot
+ 1, right
->keys
,
332 BUG_ON(list_empty(&parent_buf
->dirty
));
335 if (mid
->header
.nritems
== 1) {
337 * we're not allowed to leave a node with one item in the
338 * tree during a delete. A deletion from lower in the tree
339 * could try to delete the only pointer in this node.
340 * So, pull some keys from the left.
341 * There has to be a left pointer at this point because
342 * otherwise we would have pulled some pointers from the
346 wret
= balance_node_right(root
, mid_buf
, left_buf
);
351 if (mid
->header
.nritems
== 0) {
352 /* we've managed to empty the middle node, drop it */
353 u64 blocknr
= mid_buf
->blocknr
;
354 tree_block_release(root
, mid_buf
);
355 clean_tree_block(root
, mid_buf
);
358 wret
= del_ptr(root
, path
, level
+ 1, pslot
);
361 wret
= free_extent(root
, blocknr
, 1);
365 /* update the parent key to reflect our changes */
366 memcpy(parent
->keys
+ pslot
, mid
->keys
, sizeof(struct key
));
367 BUG_ON(list_empty(&parent_buf
->dirty
));
370 /* update the path */
372 if (left
->header
.nritems
> orig_slot
) {
373 left_buf
->count
++; // released below
374 path
->nodes
[level
] = left_buf
;
375 path
->slots
[level
+ 1] -= 1;
376 path
->slots
[level
] = orig_slot
;
378 tree_block_release(root
, mid_buf
);
380 orig_slot
-= left
->header
.nritems
;
381 path
->slots
[level
] = orig_slot
;
384 /* double check we haven't messed things up */
385 check_block(path
, level
);
386 if (orig_ptr
!= path
->nodes
[level
]->node
.blockptrs
[path
->slots
[level
]])
390 tree_block_release(root
, right_buf
);
392 tree_block_release(root
, left_buf
);
397 * look for key in the tree. path is filled in with nodes along the way
398 * if key is found, we return zero and you can find the item in the leaf
399 * level of the path (level 0)
401 * If the key isn't found, the path points to the slot where it should
402 * be inserted, and 1 is returned. If there are other errors during the
403 * search a negative error number is returned.
405 * if ins_len > 0, nodes and leaves will be split as we walk down the
406 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
409 int search_slot(struct ctree_root
*root
, struct key
*key
,
410 struct ctree_path
*p
, int ins_len
, int cow
)
412 struct tree_buffer
*b
;
413 struct tree_buffer
*cow_buf
;
423 level
= node_level(b
->node
.header
.flags
);
426 wret
= btrfs_cow_block(root
, b
, p
->nodes
[level
+ 1],
427 p
->slots
[level
+ 1], &cow_buf
);
430 BUG_ON(!cow
&& ins_len
);
433 ret
= check_block(p
, level
);
436 ret
= bin_search(c
, key
, &slot
);
437 if (!is_leaf(c
->header
.flags
)) {
440 p
->slots
[level
] = slot
;
442 c
->header
.nritems
== NODEPTRS_PER_BLOCK
) {
443 int sret
= split_node(root
, p
, level
);
449 slot
= p
->slots
[level
];
450 } else if (ins_len
< 0) {
451 int sret
= balance_level(root
, p
, level
);
458 slot
= p
->slots
[level
];
459 BUG_ON(c
->header
.nritems
== 1);
461 b
= read_tree_block(root
, c
->blockptrs
[slot
]);
463 struct leaf
*l
= (struct leaf
*)c
;
464 p
->slots
[level
] = slot
;
465 if (ins_len
> 0 && leaf_free_space(l
) <
466 sizeof(struct item
) + ins_len
) {
467 int sret
= split_leaf(root
, p
, ins_len
);
472 BUG_ON(root
->node
->count
== 1);
476 BUG_ON(root
->node
->count
== 1);
481 * adjust the pointers going up the tree, starting at level
482 * making sure the right key of each node is points to 'key'.
483 * This is used after shifting pointers to the left, so it stops
484 * fixing up pointers when a given leaf/node is not in slot 0 of the
487 * If this fails to write a tree block, it returns -1, but continues
488 * fixing up the blocks in ram so the tree is consistent.
490 static int fixup_low_keys(struct ctree_root
*root
,
491 struct ctree_path
*path
, struct key
*key
,
496 for (i
= level
; i
< MAX_LEVEL
; i
++) {
498 int tslot
= path
->slots
[i
];
501 t
= &path
->nodes
[i
]->node
;
502 memcpy(t
->keys
+ tslot
, key
, sizeof(*key
));
503 BUG_ON(list_empty(&path
->nodes
[i
]->dirty
));
511 * try to push data from one node into the next node left in the
514 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
515 * error, and > 0 if there was no room in the left hand block.
517 static int push_node_left(struct ctree_root
*root
, struct tree_buffer
*dst_buf
,
518 struct tree_buffer
*src_buf
)
520 struct node
*src
= &src_buf
->node
;
521 struct node
*dst
= &dst_buf
->node
;
527 src_nritems
= src
->header
.nritems
;
528 dst_nritems
= dst
->header
.nritems
;
529 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
530 if (push_items
<= 0) {
534 if (src_nritems
< push_items
)
535 push_items
= src_nritems
;
537 memcpy(dst
->keys
+ dst_nritems
, src
->keys
,
538 push_items
* sizeof(struct key
));
539 memcpy(dst
->blockptrs
+ dst_nritems
, src
->blockptrs
,
540 push_items
* sizeof(u64
));
541 if (push_items
< src_nritems
) {
542 memmove(src
->keys
, src
->keys
+ push_items
,
543 (src_nritems
- push_items
) * sizeof(struct key
));
544 memmove(src
->blockptrs
, src
->blockptrs
+ push_items
,
545 (src_nritems
- push_items
) * sizeof(u64
));
547 src
->header
.nritems
-= push_items
;
548 dst
->header
.nritems
+= push_items
;
550 BUG_ON(list_empty(&src_buf
->dirty
));
551 BUG_ON(list_empty(&dst_buf
->dirty
));
556 * try to push data from one node into the next node right in the
559 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
560 * error, and > 0 if there was no room in the right hand block.
562 * this will only push up to 1/2 the contents of the left node over
564 static int balance_node_right(struct ctree_root
*root
,
565 struct tree_buffer
*dst_buf
,
566 struct tree_buffer
*src_buf
)
568 struct node
*src
= &src_buf
->node
;
569 struct node
*dst
= &dst_buf
->node
;
576 src_nritems
= src
->header
.nritems
;
577 dst_nritems
= dst
->header
.nritems
;
578 push_items
= NODEPTRS_PER_BLOCK
- dst_nritems
;
579 if (push_items
<= 0) {
583 max_push
= src_nritems
/ 2 + 1;
584 /* don't try to empty the node */
585 if (max_push
> src_nritems
)
587 if (max_push
< push_items
)
588 push_items
= max_push
;
590 memmove(dst
->keys
+ push_items
, dst
->keys
,
591 dst_nritems
* sizeof(struct key
));
592 memmove(dst
->blockptrs
+ push_items
, dst
->blockptrs
,
593 dst_nritems
* sizeof(u64
));
594 memcpy(dst
->keys
, src
->keys
+ src_nritems
- push_items
,
595 push_items
* sizeof(struct key
));
596 memcpy(dst
->blockptrs
, src
->blockptrs
+ src_nritems
- push_items
,
597 push_items
* sizeof(u64
));
599 src
->header
.nritems
-= push_items
;
600 dst
->header
.nritems
+= push_items
;
602 BUG_ON(list_empty(&src_buf
->dirty
));
603 BUG_ON(list_empty(&dst_buf
->dirty
));
608 * helper function to insert a new root level in the tree.
609 * A new node is allocated, and a single item is inserted to
610 * point to the existing root
612 * returns zero on success or < 0 on failure.
614 static int insert_new_root(struct ctree_root
*root
,
615 struct ctree_path
*path
, int level
)
617 struct tree_buffer
*t
;
620 struct key
*lower_key
;
622 BUG_ON(path
->nodes
[level
]);
623 BUG_ON(path
->nodes
[level
-1] != root
->node
);
625 t
= alloc_free_block(root
);
627 memset(c
, 0, sizeof(c
));
628 c
->header
.nritems
= 1;
629 c
->header
.flags
= node_level(level
);
630 c
->header
.blocknr
= t
->blocknr
;
631 c
->header
.parentid
= root
->node
->node
.header
.parentid
;
632 lower
= &path
->nodes
[level
-1]->node
;
633 if (is_leaf(lower
->header
.flags
))
634 lower_key
= &((struct leaf
*)lower
)->items
[0].key
;
636 lower_key
= lower
->keys
;
637 memcpy(c
->keys
, lower_key
, sizeof(struct key
));
638 c
->blockptrs
[0] = path
->nodes
[level
-1]->blocknr
;
639 /* the super has an extra ref to root->node */
640 tree_block_release(root
, root
->node
);
643 path
->nodes
[level
] = t
;
644 path
->slots
[level
] = 0;
649 * worker function to insert a single pointer in a node.
650 * the node should have enough room for the pointer already
652 * slot and level indicate where you want the key to go, and
653 * blocknr is the block the key points to.
655 * returns zero on success and < 0 on any error
657 static int insert_ptr(struct ctree_root
*root
,
658 struct ctree_path
*path
, struct key
*key
,
659 u64 blocknr
, int slot
, int level
)
664 BUG_ON(!path
->nodes
[level
]);
665 lower
= &path
->nodes
[level
]->node
;
666 nritems
= lower
->header
.nritems
;
669 if (nritems
== NODEPTRS_PER_BLOCK
)
671 if (slot
!= nritems
) {
672 memmove(lower
->keys
+ slot
+ 1, lower
->keys
+ slot
,
673 (nritems
- slot
) * sizeof(struct key
));
674 memmove(lower
->blockptrs
+ slot
+ 1, lower
->blockptrs
+ slot
,
675 (nritems
- slot
) * sizeof(u64
));
677 memcpy(lower
->keys
+ slot
, key
, sizeof(struct key
));
678 lower
->blockptrs
[slot
] = blocknr
;
679 lower
->header
.nritems
++;
680 if (lower
->keys
[1].objectid
== 0)
682 BUG_ON(list_empty(&path
->nodes
[level
]->dirty
));
687 * split the node at the specified level in path in two.
688 * The path is corrected to point to the appropriate node after the split
690 * Before splitting this tries to make some room in the node by pushing
691 * left and right, if either one works, it returns right away.
693 * returns 0 on success and < 0 on failure
695 static int split_node(struct ctree_root
*root
, struct ctree_path
*path
,
698 struct tree_buffer
*t
;
700 struct tree_buffer
*split_buffer
;
706 t
= path
->nodes
[level
];
708 if (t
== root
->node
) {
709 /* trying to split the root, lets make a new one */
710 ret
= insert_new_root(root
, path
, level
+ 1);
714 split_buffer
= alloc_free_block(root
);
715 split
= &split_buffer
->node
;
716 split
->header
.flags
= c
->header
.flags
;
717 split
->header
.blocknr
= split_buffer
->blocknr
;
718 split
->header
.parentid
= root
->node
->node
.header
.parentid
;
719 mid
= (c
->header
.nritems
+ 1) / 2;
720 memcpy(split
->keys
, c
->keys
+ mid
,
721 (c
->header
.nritems
- mid
) * sizeof(struct key
));
722 memcpy(split
->blockptrs
, c
->blockptrs
+ mid
,
723 (c
->header
.nritems
- mid
) * sizeof(u64
));
724 split
->header
.nritems
= c
->header
.nritems
- mid
;
725 c
->header
.nritems
= mid
;
728 BUG_ON(list_empty(&t
->dirty
));
729 wret
= insert_ptr(root
, path
, split
->keys
, split_buffer
->blocknr
,
730 path
->slots
[level
+ 1] + 1, level
+ 1);
734 if (path
->slots
[level
] >= mid
) {
735 path
->slots
[level
] -= mid
;
736 tree_block_release(root
, t
);
737 path
->nodes
[level
] = split_buffer
;
738 path
->slots
[level
+ 1] += 1;
740 tree_block_release(root
, split_buffer
);
746 * how many bytes are required to store the items in a leaf. start
747 * and nr indicate which items in the leaf to check. This totals up the
748 * space used both by the item structs and the item data
750 static int leaf_space_used(struct leaf
*l
, int start
, int nr
)
753 int end
= start
+ nr
- 1;
757 data_len
= l
->items
[start
].offset
+ l
->items
[start
].size
;
758 data_len
= data_len
- l
->items
[end
].offset
;
759 data_len
+= sizeof(struct item
) * nr
;
764 * push some data in the path leaf to the right, trying to free up at
765 * least data_size bytes. returns zero if the push worked, nonzero otherwise
767 * returns 1 if the push failed because the other node didn't have enough
768 * room, 0 if everything worked out and < 0 if there were major errors.
770 static int push_leaf_right(struct ctree_root
*root
, struct ctree_path
*path
,
773 struct tree_buffer
*left_buf
= path
->nodes
[0];
774 struct leaf
*left
= &left_buf
->leaf
;
776 struct tree_buffer
*right_buf
;
777 struct tree_buffer
*upper
;
785 slot
= path
->slots
[1];
786 if (!path
->nodes
[1]) {
789 upper
= path
->nodes
[1];
790 if (slot
>= upper
->node
.header
.nritems
- 1) {
793 right_buf
= read_tree_block(root
, upper
->node
.blockptrs
[slot
+ 1]);
794 right
= &right_buf
->leaf
;
795 free_space
= leaf_free_space(right
);
796 if (free_space
< data_size
+ sizeof(struct item
)) {
797 tree_block_release(root
, right_buf
);
800 /* cow and double check */
801 btrfs_cow_block(root
, right_buf
, upper
, slot
+ 1, &right_buf
);
802 right
= &right_buf
->leaf
;
803 free_space
= leaf_free_space(right
);
804 if (free_space
< data_size
+ sizeof(struct item
)) {
805 tree_block_release(root
, right_buf
);
809 for (i
= left
->header
.nritems
- 1; i
>= 0; i
--) {
810 item
= left
->items
+ i
;
811 if (path
->slots
[0] == i
)
812 push_space
+= data_size
+ sizeof(*item
);
813 if (item
->size
+ sizeof(*item
) + push_space
> free_space
)
816 push_space
+= item
->size
+ sizeof(*item
);
818 if (push_items
== 0) {
819 tree_block_release(root
, right_buf
);
822 /* push left to right */
823 push_space
= left
->items
[left
->header
.nritems
- push_items
].offset
+
824 left
->items
[left
->header
.nritems
- push_items
].size
;
825 push_space
-= leaf_data_end(left
);
826 /* make room in the right data area */
827 memmove(right
->data
+ leaf_data_end(right
) - push_space
,
828 right
->data
+ leaf_data_end(right
),
829 LEAF_DATA_SIZE
- leaf_data_end(right
));
830 /* copy from the left data area */
831 memcpy(right
->data
+ LEAF_DATA_SIZE
- push_space
,
832 left
->data
+ leaf_data_end(left
),
834 memmove(right
->items
+ push_items
, right
->items
,
835 right
->header
.nritems
* sizeof(struct item
));
836 /* copy the items from left to right */
837 memcpy(right
->items
, left
->items
+ left
->header
.nritems
- push_items
,
838 push_items
* sizeof(struct item
));
840 /* update the item pointers */
841 right
->header
.nritems
+= push_items
;
842 push_space
= LEAF_DATA_SIZE
;
843 for (i
= 0; i
< right
->header
.nritems
; i
++) {
844 right
->items
[i
].offset
= push_space
- right
->items
[i
].size
;
845 push_space
= right
->items
[i
].offset
;
847 left
->header
.nritems
-= push_items
;
849 BUG_ON(list_empty(&left_buf
->dirty
));
850 BUG_ON(list_empty(&right_buf
->dirty
));
851 memcpy(upper
->node
.keys
+ slot
+ 1,
852 &right
->items
[0].key
, sizeof(struct key
));
853 BUG_ON(list_empty(&upper
->dirty
));
855 /* then fixup the leaf pointer in the path */
856 if (path
->slots
[0] >= left
->header
.nritems
) {
857 path
->slots
[0] -= left
->header
.nritems
;
858 tree_block_release(root
, path
->nodes
[0]);
859 path
->nodes
[0] = right_buf
;
862 tree_block_release(root
, right_buf
);
867 * push some data in the path leaf to the left, trying to free up at
868 * least data_size bytes. returns zero if the push worked, nonzero otherwise
870 static int push_leaf_left(struct ctree_root
*root
, struct ctree_path
*path
,
873 struct tree_buffer
*right_buf
= path
->nodes
[0];
874 struct leaf
*right
= &right_buf
->leaf
;
875 struct tree_buffer
*t
;
883 int old_left_nritems
;
887 slot
= path
->slots
[1];
891 if (!path
->nodes
[1]) {
894 t
= read_tree_block(root
, path
->nodes
[1]->node
.blockptrs
[slot
- 1]);
896 free_space
= leaf_free_space(left
);
897 if (free_space
< data_size
+ sizeof(struct item
)) {
898 tree_block_release(root
, t
);
902 /* cow and double check */
903 btrfs_cow_block(root
, t
, path
->nodes
[1], slot
- 1, &t
);
905 free_space
= leaf_free_space(left
);
906 if (free_space
< data_size
+ sizeof(struct item
)) {
907 tree_block_release(root
, t
);
911 for (i
= 0; i
< right
->header
.nritems
; i
++) {
912 item
= right
->items
+ i
;
913 if (path
->slots
[0] == i
)
914 push_space
+= data_size
+ sizeof(*item
);
915 if (item
->size
+ sizeof(*item
) + push_space
> free_space
)
918 push_space
+= item
->size
+ sizeof(*item
);
920 if (push_items
== 0) {
921 tree_block_release(root
, t
);
924 /* push data from right to left */
925 memcpy(left
->items
+ left
->header
.nritems
,
926 right
->items
, push_items
* sizeof(struct item
));
927 push_space
= LEAF_DATA_SIZE
- right
->items
[push_items
-1].offset
;
928 memcpy(left
->data
+ leaf_data_end(left
) - push_space
,
929 right
->data
+ right
->items
[push_items
- 1].offset
,
931 old_left_nritems
= left
->header
.nritems
;
932 BUG_ON(old_left_nritems
< 0);
934 for(i
= old_left_nritems
; i
< old_left_nritems
+ push_items
; i
++) {
935 left
->items
[i
].offset
-= LEAF_DATA_SIZE
-
936 left
->items
[old_left_nritems
-1].offset
;
938 left
->header
.nritems
+= push_items
;
940 /* fixup right node */
941 push_space
= right
->items
[push_items
-1].offset
- leaf_data_end(right
);
942 memmove(right
->data
+ LEAF_DATA_SIZE
- push_space
, right
->data
+
943 leaf_data_end(right
), push_space
);
944 memmove(right
->items
, right
->items
+ push_items
,
945 (right
->header
.nritems
- push_items
) * sizeof(struct item
));
946 right
->header
.nritems
-= push_items
;
947 push_space
= LEAF_DATA_SIZE
;
949 for (i
= 0; i
< right
->header
.nritems
; i
++) {
950 right
->items
[i
].offset
= push_space
- right
->items
[i
].size
;
951 push_space
= right
->items
[i
].offset
;
954 BUG_ON(list_empty(&t
->dirty
));
955 BUG_ON(list_empty(&right_buf
->dirty
));
957 wret
= fixup_low_keys(root
, path
, &right
->items
[0].key
, 1);
961 /* then fixup the leaf pointer in the path */
962 if (path
->slots
[0] < push_items
) {
963 path
->slots
[0] += old_left_nritems
;
964 tree_block_release(root
, path
->nodes
[0]);
968 tree_block_release(root
, t
);
969 path
->slots
[0] -= push_items
;
971 BUG_ON(path
->slots
[0] < 0);
976 * split the path's leaf in two, making sure there is at least data_size
977 * available for the resulting leaf level of the path.
979 * returns 0 if all went well and < 0 on failure.
981 static int split_leaf(struct ctree_root
*root
, struct ctree_path
*path
,
984 struct tree_buffer
*l_buf
;
990 struct tree_buffer
*right_buffer
;
991 int space_needed
= data_size
+ sizeof(struct item
);
998 wret
= push_leaf_left(root
, path
, data_size
);
1002 wret
= push_leaf_right(root
, path
, data_size
);
1007 l_buf
= path
->nodes
[0];
1010 /* did the pushes work? */
1011 if (leaf_free_space(l
) >= sizeof(struct item
) + data_size
)
1014 if (!path
->nodes
[1]) {
1015 ret
= insert_new_root(root
, path
, 1);
1019 slot
= path
->slots
[0];
1020 nritems
= l
->header
.nritems
;
1021 mid
= (nritems
+ 1)/ 2;
1022 right_buffer
= alloc_free_block(root
);
1023 BUG_ON(!right_buffer
);
1024 BUG_ON(mid
== nritems
);
1025 right
= &right_buffer
->leaf
;
1026 memset(right
, 0, sizeof(*right
));
1028 /* FIXME, just alloc a new leaf here */
1029 if (leaf_space_used(l
, mid
, nritems
- mid
) + space_needed
>
1033 /* FIXME, just alloc a new leaf here */
1034 if (leaf_space_used(l
, 0, mid
+ 1) + space_needed
>
1038 right
->header
.nritems
= nritems
- mid
;
1039 right
->header
.blocknr
= right_buffer
->blocknr
;
1040 right
->header
.flags
= node_level(0);
1041 right
->header
.parentid
= root
->node
->node
.header
.parentid
;
1042 data_copy_size
= l
->items
[mid
].offset
+ l
->items
[mid
].size
-
1044 memcpy(right
->items
, l
->items
+ mid
,
1045 (nritems
- mid
) * sizeof(struct item
));
1046 memcpy(right
->data
+ LEAF_DATA_SIZE
- data_copy_size
,
1047 l
->data
+ leaf_data_end(l
), data_copy_size
);
1048 rt_data_off
= LEAF_DATA_SIZE
-
1049 (l
->items
[mid
].offset
+ l
->items
[mid
].size
);
1051 for (i
= 0; i
< right
->header
.nritems
; i
++)
1052 right
->items
[i
].offset
+= rt_data_off
;
1054 l
->header
.nritems
= mid
;
1056 wret
= insert_ptr(root
, path
, &right
->items
[0].key
,
1057 right_buffer
->blocknr
, path
->slots
[1] + 1, 1);
1060 BUG_ON(list_empty(&right_buffer
->dirty
));
1061 BUG_ON(list_empty(&l_buf
->dirty
));
1062 BUG_ON(path
->slots
[0] != slot
);
1064 tree_block_release(root
, path
->nodes
[0]);
1065 path
->nodes
[0] = right_buffer
;
1066 path
->slots
[0] -= mid
;
1067 path
->slots
[1] += 1;
1069 tree_block_release(root
, right_buffer
);
1070 BUG_ON(path
->slots
[0] < 0);
1075 * Given a key and some data, insert an item into the tree.
1076 * This does all the path init required, making room in the tree if needed.
1078 int insert_item(struct ctree_root
*root
, struct key
*key
,
1079 void *data
, int data_size
)
1085 struct tree_buffer
*leaf_buf
;
1086 unsigned int nritems
;
1087 unsigned int data_end
;
1088 struct ctree_path path
;
1090 /* create a root if there isn't one */
1094 ret
= search_slot(root
, key
, &path
, data_size
, 1);
1096 release_path(root
, &path
);
1102 slot_orig
= path
.slots
[0];
1103 leaf_buf
= path
.nodes
[0];
1104 leaf
= &leaf_buf
->leaf
;
1106 nritems
= leaf
->header
.nritems
;
1107 data_end
= leaf_data_end(leaf
);
1109 if (leaf_free_space(leaf
) < sizeof(struct item
) + data_size
)
1112 slot
= path
.slots
[0];
1114 if (slot
!= nritems
) {
1116 unsigned int old_data
= leaf
->items
[slot
].offset
+
1117 leaf
->items
[slot
].size
;
1120 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1122 /* first correct the data pointers */
1123 for (i
= slot
; i
< nritems
; i
++)
1124 leaf
->items
[i
].offset
-= data_size
;
1126 /* shift the items */
1127 memmove(leaf
->items
+ slot
+ 1, leaf
->items
+ slot
,
1128 (nritems
- slot
) * sizeof(struct item
));
1130 /* shift the data */
1131 memmove(leaf
->data
+ data_end
- data_size
, leaf
->data
+
1132 data_end
, old_data
- data_end
);
1133 data_end
= old_data
;
1135 /* copy the new data in */
1136 memcpy(&leaf
->items
[slot
].key
, key
, sizeof(struct key
));
1137 leaf
->items
[slot
].offset
= data_end
- data_size
;
1138 leaf
->items
[slot
].size
= data_size
;
1139 memcpy(leaf
->data
+ data_end
- data_size
, data
, data_size
);
1140 leaf
->header
.nritems
+= 1;
1144 ret
= fixup_low_keys(root
, &path
, key
, 1);
1146 BUG_ON(list_empty(&leaf_buf
->dirty
));
1147 if (leaf_free_space(leaf
) < 0)
1149 check_leaf(&path
, 0);
1151 release_path(root
, &path
);
1156 * delete the pointer from a given node.
1158 * If the delete empties a node, the node is removed from the tree,
1159 * continuing all the way the root if required. The root is converted into
1160 * a leaf if all the nodes are emptied.
1162 static int del_ptr(struct ctree_root
*root
, struct ctree_path
*path
, int level
,
1166 struct tree_buffer
*parent
= path
->nodes
[level
];
1171 node
= &parent
->node
;
1172 nritems
= node
->header
.nritems
;
1173 if (slot
!= nritems
-1) {
1174 memmove(node
->keys
+ slot
, node
->keys
+ slot
+ 1,
1175 sizeof(struct key
) * (nritems
- slot
- 1));
1176 memmove(node
->blockptrs
+ slot
,
1177 node
->blockptrs
+ slot
+ 1,
1178 sizeof(u64
) * (nritems
- slot
- 1));
1180 node
->header
.nritems
--;
1181 if (node
->header
.nritems
== 0 && parent
== root
->node
) {
1182 BUG_ON(node_level(root
->node
->node
.header
.flags
) != 1);
1183 /* just turn the root into a leaf and break */
1184 root
->node
->node
.header
.flags
= node_level(0);
1185 } else if (slot
== 0) {
1186 wret
= fixup_low_keys(root
, path
, node
->keys
, level
+ 1);
1190 BUG_ON(list_empty(&parent
->dirty
));
1195 * delete the item at the leaf level in path. If that empties
1196 * the leaf, remove it from the tree
1198 int del_item(struct ctree_root
*root
, struct ctree_path
*path
)
1202 struct tree_buffer
*leaf_buf
;
1208 leaf_buf
= path
->nodes
[0];
1209 leaf
= &leaf_buf
->leaf
;
1210 slot
= path
->slots
[0];
1211 doff
= leaf
->items
[slot
].offset
;
1212 dsize
= leaf
->items
[slot
].size
;
1214 if (slot
!= leaf
->header
.nritems
- 1) {
1216 int data_end
= leaf_data_end(leaf
);
1217 memmove(leaf
->data
+ data_end
+ dsize
,
1218 leaf
->data
+ data_end
,
1220 for (i
= slot
+ 1; i
< leaf
->header
.nritems
; i
++)
1221 leaf
->items
[i
].offset
+= dsize
;
1222 memmove(leaf
->items
+ slot
, leaf
->items
+ slot
+ 1,
1223 sizeof(struct item
) *
1224 (leaf
->header
.nritems
- slot
- 1));
1226 leaf
->header
.nritems
-= 1;
1227 /* delete the leaf if we've emptied it */
1228 if (leaf
->header
.nritems
== 0) {
1229 if (leaf_buf
== root
->node
) {
1230 leaf
->header
.flags
= node_level(0);
1231 BUG_ON(list_empty(&leaf_buf
->dirty
));
1233 clean_tree_block(root
, leaf_buf
);
1234 wret
= del_ptr(root
, path
, 1, path
->slots
[1]);
1237 wret
= free_extent(root
, leaf_buf
->blocknr
, 1);
1242 int used
= leaf_space_used(leaf
, 0, leaf
->header
.nritems
);
1244 wret
= fixup_low_keys(root
, path
,
1245 &leaf
->items
[0].key
, 1);
1249 BUG_ON(list_empty(&leaf_buf
->dirty
));
1251 /* delete the leaf if it is mostly empty */
1252 if (used
< LEAF_DATA_SIZE
/ 3) {
1253 /* push_leaf_left fixes the path.
1254 * make sure the path still points to our leaf
1255 * for possible call to del_ptr below
1257 slot
= path
->slots
[1];
1259 wret
= push_leaf_left(root
, path
, 1);
1262 if (path
->nodes
[0] == leaf_buf
&&
1263 leaf
->header
.nritems
) {
1264 wret
= push_leaf_right(root
, path
, 1);
1268 if (leaf
->header
.nritems
== 0) {
1269 u64 blocknr
= leaf_buf
->blocknr
;
1270 clean_tree_block(root
, leaf_buf
);
1271 wret
= del_ptr(root
, path
, 1, slot
);
1274 tree_block_release(root
, leaf_buf
);
1275 wret
= free_extent(root
, blocknr
, 1);
1279 tree_block_release(root
, leaf_buf
);
1287 * walk up the tree as far as required to find the next leaf.
1288 * returns 0 if it found something or 1 if there are no greater leaves.
1289 * returns < 0 on io errors.
1291 int next_leaf(struct ctree_root
*root
, struct ctree_path
*path
)
1296 struct tree_buffer
*c
;
1297 struct tree_buffer
*next
= NULL
;
1299 while(level
< MAX_LEVEL
) {
1300 if (!path
->nodes
[level
])
1302 slot
= path
->slots
[level
] + 1;
1303 c
= path
->nodes
[level
];
1304 if (slot
>= c
->node
.header
.nritems
) {
1308 blocknr
= c
->node
.blockptrs
[slot
];
1310 tree_block_release(root
, next
);
1311 next
= read_tree_block(root
, blocknr
);
1314 path
->slots
[level
] = slot
;
1317 c
= path
->nodes
[level
];
1318 tree_block_release(root
, c
);
1319 path
->nodes
[level
] = next
;
1320 path
->slots
[level
] = 0;
1323 next
= read_tree_block(root
, next
->node
.blockptrs
[0]);
This page took 0.060833 seconds and 5 git commands to generate.