?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
32 bit compile fixes
[btrfs-progs-unstable.git] / ctree.c
blobc6dcba7032a1bba0bd613b3ebc7f5ac07b4f5763
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "kerncompat.h"
4 #include "radix-tree.h"
5 #include "ctree.h"
6 #include "disk-io.h"
7 #include "print-tree.h"
8
9 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
10 *root, struct btrfs_path *path, int level);
11 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
12 *root, struct btrfs_path *path, int data_size);
13 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
14 *root, struct btrfs_buffer *dst, struct btrfs_buffer
15 *src);
16 static int balance_node_right(struct btrfs_trans_handle *trans, struct
17 btrfs_root *root, struct btrfs_buffer *dst_buf,
18 struct btrfs_buffer *src_buf);
19 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
20 struct btrfs_path *path, int level, int slot);
21
22 inline void btrfs_init_path(struct btrfs_path *p)
23 {
24 memset(p, 0, sizeof(*p));
25 }
26
27 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
28 {
29 int i;
30 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
31 if (!p->nodes[i])
32 break;
33 btrfs_block_release(root, p->nodes[i]);
34 }
35 memset(p, 0, sizeof(*p));
36 }
37
38 static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
39 *root, struct btrfs_buffer *buf, struct btrfs_buffer
40 *parent, int parent_slot, struct btrfs_buffer
41 **cow_ret)
42 {
43 struct btrfs_buffer *cow;
44
45 if (!list_empty(&buf->dirty)) {
46 *cow_ret = buf;
47 return 0;
48 }
49 cow = btrfs_alloc_free_block(trans, root);
50 memcpy(&cow->node, &buf->node, root->blocksize);
51 btrfs_set_header_blocknr(&cow->node.header, cow->blocknr);
52 btrfs_set_header_owner(&cow->node.header, root->root_key.objectid);
53 *cow_ret = cow;
54 btrfs_inc_ref(trans, root, buf);
55 if (buf == root->node) {
56 root->node = cow;
57 cow->count++;
58 if (buf != root->commit_root)
59 btrfs_free_extent(trans, root, buf->blocknr, 1, 1);
60 btrfs_block_release(root, buf);
61 } else {
62 btrfs_set_node_blockptr(&parent->node, parent_slot,
63 cow->blocknr);
64 BUG_ON(list_empty(&parent->dirty));
65 btrfs_free_extent(trans, root, buf->blocknr, 1, 1);
66 }
67 btrfs_block_release(root, buf);
68 return 0;
69 }
70
71 /*
72 * The leaf data grows from end-to-front in the node.
73 * this returns the address of the start of the last item,
74 * which is the stop of the leaf data stack
75 */
76 static inline unsigned int leaf_data_end(struct btrfs_root *root,
77 struct btrfs_leaf *leaf)
78 {
79 u32 nr = btrfs_header_nritems(&leaf->header);
80 if (nr == 0)
81 return BTRFS_LEAF_DATA_SIZE(root);
82 return btrfs_item_offset(leaf->items + nr - 1);
83 }
84
85 /*
86 * how many bytes are required to store the items in a leaf. start
87 * and nr indicate which items in the leaf to check. This totals up the
88 * space used both by the item structs and the item data
89 */
90 static int leaf_space_used(struct btrfs_leaf *l, int start, int nr)
91 {
92 int data_len;
93 int nritems = btrfs_header_nritems(&l->header);
94 int end;
95
96 if (nritems < start + nr)
97 end = nritems - 1;
98 else
99 end = start + nr - 1;
100
101 if (!nr)
102 return 0;
103 data_len = btrfs_item_end(l->items + start);
104 data_len = data_len - btrfs_item_offset(l->items + end);
105 data_len += sizeof(struct btrfs_item) * nr;
106 return data_len;
107 }
108
109 /*
110 * The space between the end of the leaf items and
111 * the start of the leaf data. IOW, how much room
112 * the leaf has left for both items and data
113 */
114 int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
115 {
116 int nritems = btrfs_header_nritems(&leaf->header);
117 return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
118 }
119
120 /*
121 * compare two keys in a memcmp fashion
122 */
123 int btrfs_comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
124 {
125 struct btrfs_key k1;
126
127 btrfs_disk_key_to_cpu(&k1, disk);
128
129 if (k1.objectid > k2->objectid)
130 return 1;
131 if (k1.objectid < k2->objectid)
132 return -1;
133 if (k1.flags > k2->flags)
134 return 1;
135 if (k1.flags < k2->flags)
136 return -1;
137 if (k1.offset > k2->offset)
138 return 1;
139 if (k1.offset < k2->offset)
140 return -1;
141 return 0;
142 }
143
144 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
145 int level)
146 {
147 int i;
148 struct btrfs_node *parent = NULL;
149 struct btrfs_node *node = &path->nodes[level]->node;
150 int parent_slot;
151 u32 nritems = btrfs_header_nritems(&node->header);
152
153 if (path->nodes[level + 1])
154 parent = &path->nodes[level + 1]->node;
155 parent_slot = path->slots[level + 1];
156 BUG_ON(nritems == 0);
157 if (parent) {
158 struct btrfs_disk_key *parent_key;
159 parent_key = &parent->ptrs[parent_slot].key;
160 BUG_ON(memcmp(parent_key, &node->ptrs[0].key,
161 sizeof(struct btrfs_disk_key)));
162 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
163 btrfs_header_blocknr(&node->header));
164 }
165 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
166 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
167 struct btrfs_key cpukey;
168 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
169 BUG_ON(btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0);
170 }
171 return 0;
172 }
173
174 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
175 int level)
176 {
177 int i;
178 struct btrfs_leaf *leaf = &path->nodes[level]->leaf;
179 struct btrfs_node *parent = NULL;
180 int parent_slot;
181 u32 nritems = btrfs_header_nritems(&leaf->header);
182
183 if (path->nodes[level + 1])
184 parent = &path->nodes[level + 1]->node;
185 parent_slot = path->slots[level + 1];
186 BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
187
188 if (nritems == 0)
189 return 0;
190
191 if (parent) {
192 struct btrfs_disk_key *parent_key;
193 parent_key = &parent->ptrs[parent_slot].key;
194 BUG_ON(memcmp(parent_key, &leaf->items[0].key,
195 sizeof(struct btrfs_disk_key)));
196 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
197 btrfs_header_blocknr(&leaf->header));
198 }
199 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
200 struct btrfs_key cpukey;
201 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
202 BUG_ON(btrfs_comp_keys(&leaf->items[i].key,
203 &cpukey) >= 0);
204 BUG_ON(btrfs_item_offset(leaf->items + i) !=
205 btrfs_item_end(leaf->items + i + 1));
206 if (i == 0) {
207 BUG_ON(btrfs_item_offset(leaf->items + i) +
208 btrfs_item_size(leaf->items + i) !=
209 BTRFS_LEAF_DATA_SIZE(root));
210 }
211 }
212 return 0;
213 }
214
215 static int check_block(struct btrfs_root *root, struct btrfs_path *path,
216 int level)
217 {
218 if (level == 0)
219 return check_leaf(root, path, level);
220 return check_node(root, path, level);
221 }
222
223 /*
224 * search for key in the array p. items p are item_size apart
225 * and there are 'max' items in p
226 * the slot in the array is returned via slot, and it points to
227 * the place where you would insert key if it is not found in
228 * the array.
229 *
230 * slot may point to max if the key is bigger than all of the keys
231 */
232 static int generic_bin_search(char *p, int item_size, struct btrfs_key *key,
233 int max, int *slot)
234 {
235 int low = 0;
236 int high = max;
237 int mid;
238 int ret;
239 struct btrfs_disk_key *tmp;
240
241 while(low < high) {
242 mid = (low + high) / 2;
243 tmp = (struct btrfs_disk_key *)(p + mid * item_size);
244 ret = btrfs_comp_keys(tmp, key);
245
246 if (ret < 0)
247 low = mid + 1;
248 else if (ret > 0)
249 high = mid;
250 else {
251 *slot = mid;
252 return 0;
253 }
254 }
255 *slot = low;
256 return 1;
257 }
258
259 /*
260 * simple bin_search frontend that does the right thing for
261 * leaves vs nodes
262 */
263 static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot)
264 {
265 if (btrfs_is_leaf(c)) {
266 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
267 return generic_bin_search((void *)l->items,
268 sizeof(struct btrfs_item),
269 key, btrfs_header_nritems(&c->header),
270 slot);
271 } else {
272 return generic_bin_search((void *)c->ptrs,
273 sizeof(struct btrfs_key_ptr),
274 key, btrfs_header_nritems(&c->header),
275 slot);
276 }
277 return -1;
278 }
279
280 static struct btrfs_buffer *read_node_slot(struct btrfs_root *root,
281 struct btrfs_buffer *parent_buf,
282 int slot)
283 {
284 struct btrfs_node *node = &parent_buf->node;
285 if (slot < 0)
286 return NULL;
287 if (slot >= btrfs_header_nritems(&node->header))
288 return NULL;
289 return read_tree_block(root, btrfs_node_blockptr(node, slot));
290 }
291
292 static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
293 *root, struct btrfs_path *path, int level)
294 {
295 struct btrfs_buffer *right_buf;
296 struct btrfs_buffer *mid_buf;
297 struct btrfs_buffer *left_buf;
298 struct btrfs_buffer *parent_buf = NULL;
299 struct btrfs_node *right = NULL;
300 struct btrfs_node *mid;
301 struct btrfs_node *left = NULL;
302 struct btrfs_node *parent = NULL;
303 int ret = 0;
304 int wret;
305 int pslot;
306 int orig_slot = path->slots[level];
307 u64 orig_ptr;
308
309 if (level == 0)
310 return 0;
311
312 mid_buf = path->nodes[level];
313 mid = &mid_buf->node;
314 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
315
316 if (level < BTRFS_MAX_LEVEL - 1)
317 parent_buf = path->nodes[level + 1];
318 pslot = path->slots[level + 1];
319
320 /*
321 * deal with the case where there is only one pointer in the root
322 * by promoting the node below to a root
323 */
324 if (!parent_buf) {
325 struct btrfs_buffer *child;
326 u64 blocknr = mid_buf->blocknr;
327
328 if (btrfs_header_nritems(&mid->header) != 1)
329 return 0;
330
331 /* promote the child to a root */
332 child = read_node_slot(root, mid_buf, 0);
333 BUG_ON(!child);
334 root->node = child;
335 path->nodes[level] = NULL;
336 /* once for the path */
337 btrfs_block_release(root, mid_buf);
338 /* once for the root ptr */
339 btrfs_block_release(root, mid_buf);
340 clean_tree_block(trans, root, mid_buf);
341 return btrfs_free_extent(trans, root, blocknr, 1, 1);
342 }
343 parent = &parent_buf->node;
344
345 if (btrfs_header_nritems(&mid->header) >
346 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
347 return 0;
348
349 left_buf = read_node_slot(root, parent_buf, pslot - 1);
350 right_buf = read_node_slot(root, parent_buf, pslot + 1);
351
352 /* first, try to make some room in the middle buffer */
353 if (left_buf) {
354 btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1,
355 &left_buf);
356 left = &left_buf->node;
357 orig_slot += btrfs_header_nritems(&left->header);
358 wret = push_node_left(trans, root, left_buf, mid_buf);
359 if (wret < 0)
360 ret = wret;
361 }
362
363 /*
364 * then try to empty the right most buffer into the middle
365 */
366 if (right_buf) {
367 btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1,
368 &right_buf);
369 right = &right_buf->node;
370 wret = push_node_left(trans, root, mid_buf, right_buf);
371 if (wret < 0)
372 ret = wret;
373 if (btrfs_header_nritems(&right->header) == 0) {
374 u64 blocknr = right_buf->blocknr;
375 btrfs_block_release(root, right_buf);
376 clean_tree_block(trans, root, right_buf);
377 right_buf = NULL;
378 right = NULL;
379 wret = del_ptr(trans, root, path, level + 1, pslot +
380 1);
381 if (wret)
382 ret = wret;
383 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
384 if (wret)
385 ret = wret;
386 } else {
387 memcpy(&parent->ptrs[pslot + 1].key,
388 &right->ptrs[0].key,
389 sizeof(struct btrfs_disk_key));
390 BUG_ON(list_empty(&parent_buf->dirty));
391 }
392 }
393 if (btrfs_header_nritems(&mid->header) == 1) {
394 /*
395 * we're not allowed to leave a node with one item in the
396 * tree during a delete. A deletion from lower in the tree
397 * could try to delete the only pointer in this node.
398 * So, pull some keys from the left.
399 * There has to be a left pointer at this point because
400 * otherwise we would have pulled some pointers from the
401 * right
402 */
403 BUG_ON(!left_buf);
404 wret = balance_node_right(trans, root, mid_buf, left_buf);
405 if (wret < 0)
406 ret = wret;
407 BUG_ON(wret == 1);
408 }
409 if (btrfs_header_nritems(&mid->header) == 0) {
410 /* we've managed to empty the middle node, drop it */
411 u64 blocknr = mid_buf->blocknr;
412 btrfs_block_release(root, mid_buf);
413 clean_tree_block(trans, root, mid_buf);
414 mid_buf = NULL;
415 mid = NULL;
416 wret = del_ptr(trans, root, path, level + 1, pslot);
417 if (wret)
418 ret = wret;
419 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
420 if (wret)
421 ret = wret;
422 } else {
423 /* update the parent key to reflect our changes */
424 memcpy(&parent->ptrs[pslot].key, &mid->ptrs[0].key,
425 sizeof(struct btrfs_disk_key));
426 BUG_ON(list_empty(&parent_buf->dirty));
427 }
428
429 /* update the path */
430 if (left_buf) {
431 if (btrfs_header_nritems(&left->header) > orig_slot) {
432 left_buf->count++; // released below
433 path->nodes[level] = left_buf;
434 path->slots[level + 1] -= 1;
435 path->slots[level] = orig_slot;
436 if (mid_buf)
437 btrfs_block_release(root, mid_buf);
438 } else {
439 orig_slot -= btrfs_header_nritems(&left->header);
440 path->slots[level] = orig_slot;
441 }
442 }
443 /* double check we haven't messed things up */
444 check_block(root, path, level);
445 if (orig_ptr != btrfs_node_blockptr(&path->nodes[level]->node,
446 path->slots[level]))
447 BUG();
448
449 if (right_buf)
450 btrfs_block_release(root, right_buf);
451 if (left_buf)
452 btrfs_block_release(root, left_buf);
453 return ret;
454 }
455
456 /*
457 * look for key in the tree. path is filled in with nodes along the way
458 * if key is found, we return zero and you can find the item in the leaf
459 * level of the path (level 0)
460 *
461 * If the key isn't found, the path points to the slot where it should
462 * be inserted, and 1 is returned. If there are other errors during the
463 * search a negative error number is returned.
464 *
465 * if ins_len > 0, nodes and leaves will be split as we walk down the
466 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
467 * possible)
468 */
469 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
470 *root, struct btrfs_key *key, struct btrfs_path *p, int
471 ins_len, int cow)
472 {
473 struct btrfs_buffer *b;
474 struct btrfs_buffer *cow_buf;
475 struct btrfs_node *c;
476 int slot;
477 int ret;
478 int level;
479
480 again:
481 b = root->node;
482 b->count++;
483 while (b) {
484 level = btrfs_header_level(&b->node.header);
485 if (cow) {
486 int wret;
487 wret = btrfs_cow_block(trans, root, b, p->nodes[level +
488 1], p->slots[level + 1],
489 &cow_buf);
490 b = cow_buf;
491 }
492 BUG_ON(!cow && ins_len);
493 c = &b->node;
494 p->nodes[level] = b;
495 ret = check_block(root, p, level);
496 if (ret)
497 return -1;
498 ret = bin_search(c, key, &slot);
499 if (!btrfs_is_leaf(c)) {
500 if (ret && slot > 0)
501 slot -= 1;
502 p->slots[level] = slot;
503 if (ins_len > 0 && btrfs_header_nritems(&c->header) ==
504 BTRFS_NODEPTRS_PER_BLOCK(root)) {
505 int sret = split_node(trans, root, p, level);
506 BUG_ON(sret > 0);
507 if (sret)
508 return sret;
509 b = p->nodes[level];
510 c = &b->node;
511 slot = p->slots[level];
512 } else if (ins_len < 0) {
513 int sret = balance_level(trans, root, p,
514 level);
515 if (sret)
516 return sret;
517 b = p->nodes[level];
518 if (!b)
519 goto again;
520 c = &b->node;
521 slot = p->slots[level];
522 BUG_ON(btrfs_header_nritems(&c->header) == 1);
523 }
524 b = read_tree_block(root, btrfs_node_blockptr(c, slot));
525 } else {
526 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
527 p->slots[level] = slot;
528 if (ins_len > 0 && btrfs_leaf_free_space(root, l) <
529 sizeof(struct btrfs_item) + ins_len) {
530 int sret = split_leaf(trans, root, p, ins_len);
531 BUG_ON(sret > 0);
532 if (sret)
533 return sret;
534 }
535 BUG_ON(root->node->count == 1);
536 return ret;
537 }
538 }
539 BUG_ON(root->node->count == 1);
540 return 1;
541 }
542
543 /*
544 * adjust the pointers going up the tree, starting at level
545 * making sure the right key of each node is points to 'key'.
546 * This is used after shifting pointers to the left, so it stops
547 * fixing up pointers when a given leaf/node is not in slot 0 of the
548 * higher levels
549 *
550 * If this fails to write a tree block, it returns -1, but continues
551 * fixing up the blocks in ram so the tree is consistent.
552 */
553 static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root
554 *root, struct btrfs_path *path, struct btrfs_disk_key
555 *key, int level)
556 {
557 int i;
558 int ret = 0;
559 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
560 struct btrfs_node *t;
561 int tslot = path->slots[i];
562 if (!path->nodes[i])
563 break;
564 t = &path->nodes[i]->node;
565 memcpy(&t->ptrs[tslot].key, key, sizeof(*key));
566 BUG_ON(list_empty(&path->nodes[i]->dirty));
567 if (tslot != 0)
568 break;
569 }
570 return ret;
571 }
572
573 /*
574 * try to push data from one node into the next node left in the
575 * tree.
576 *
577 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
578 * error, and > 0 if there was no room in the left hand block.
579 */
580 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
581 *root, struct btrfs_buffer *dst_buf, struct
582 btrfs_buffer *src_buf)
583 {
584 struct btrfs_node *src = &src_buf->node;
585 struct btrfs_node *dst = &dst_buf->node;
586 int push_items = 0;
587 int src_nritems;
588 int dst_nritems;
589 int ret = 0;
590
591 src_nritems = btrfs_header_nritems(&src->header);
592 dst_nritems = btrfs_header_nritems(&dst->header);
593 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
594 if (push_items <= 0) {
595 return 1;
596 }
597
598 if (src_nritems < push_items)
599 push_items = src_nritems;
600
601 memcpy(dst->ptrs + dst_nritems, src->ptrs,
602 push_items * sizeof(struct btrfs_key_ptr));
603 if (push_items < src_nritems) {
604 memmove(src->ptrs, src->ptrs + push_items,
605 (src_nritems - push_items) *
606 sizeof(struct btrfs_key_ptr));
607 }
608 btrfs_set_header_nritems(&src->header, src_nritems - push_items);
609 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
610 BUG_ON(list_empty(&src_buf->dirty));
611 BUG_ON(list_empty(&dst_buf->dirty));
612 return ret;
613 }
614
615 /*
616 * try to push data from one node into the next node right in the
617 * tree.
618 *
619 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
620 * error, and > 0 if there was no room in the right hand block.
621 *
622 * this will only push up to 1/2 the contents of the left node over
623 */
624 static int balance_node_right(struct btrfs_trans_handle *trans, struct
625 btrfs_root *root, struct btrfs_buffer *dst_buf,
626 struct btrfs_buffer *src_buf)
627 {
628 struct btrfs_node *src = &src_buf->node;
629 struct btrfs_node *dst = &dst_buf->node;
630 int push_items = 0;
631 int max_push;
632 int src_nritems;
633 int dst_nritems;
634 int ret = 0;
635
636 src_nritems = btrfs_header_nritems(&src->header);
637 dst_nritems = btrfs_header_nritems(&dst->header);
638 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
639 if (push_items <= 0) {
640 return 1;
641 }
642
643 max_push = src_nritems / 2 + 1;
644 /* don't try to empty the node */
645 if (max_push > src_nritems)
646 return 1;
647 if (max_push < push_items)
648 push_items = max_push;
649
650 memmove(dst->ptrs + push_items, dst->ptrs,
651 dst_nritems * sizeof(struct btrfs_key_ptr));
652 memcpy(dst->ptrs, src->ptrs + src_nritems - push_items,
653 push_items * sizeof(struct btrfs_key_ptr));
654
655 btrfs_set_header_nritems(&src->header, src_nritems - push_items);
656 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
657
658 BUG_ON(list_empty(&src_buf->dirty));
659 BUG_ON(list_empty(&dst_buf->dirty));
660 return ret;
661 }
662
663 /*
664 * helper function to insert a new root level in the tree.
665 * A new node is allocated, and a single item is inserted to
666 * point to the existing root
667 *
668 * returns zero on success or < 0 on failure.
669 */
670 static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root
671 *root, struct btrfs_path *path, int level)
672 {
673 struct btrfs_buffer *t;
674 struct btrfs_node *lower;
675 struct btrfs_node *c;
676 struct btrfs_disk_key *lower_key;
677
678 BUG_ON(path->nodes[level]);
679 BUG_ON(path->nodes[level-1] != root->node);
680
681 t = btrfs_alloc_free_block(trans, root);
682 c = &t->node;
683 memset(c, 0, root->blocksize);
684 btrfs_set_header_nritems(&c->header, 1);
685 btrfs_set_header_level(&c->header, level);
686 btrfs_set_header_blocknr(&c->header, t->blocknr);
687 btrfs_set_header_owner(&c->header, root->root_key.objectid);
688 memcpy(c->header.fsid, root->fs_info->disk_super->fsid,
689 sizeof(c->header.fsid));
690 lower = &path->nodes[level-1]->node;
691 if (btrfs_is_leaf(lower))
692 lower_key = &((struct btrfs_leaf *)lower)->items[0].key;
693 else
694 lower_key = &lower->ptrs[0].key;
695 memcpy(&c->ptrs[0].key, lower_key, sizeof(struct btrfs_disk_key));
696 btrfs_set_node_blockptr(c, 0, path->nodes[level - 1]->blocknr);
697 /* the super has an extra ref to root->node */
698 btrfs_block_release(root, root->node);
699 root->node = t;
700 t->count++;
701 path->nodes[level] = t;
702 path->slots[level] = 0;
703 return 0;
704 }
705
706 /*
707 * worker function to insert a single pointer in a node.
708 * the node should have enough room for the pointer already
709 *
710 * slot and level indicate where you want the key to go, and
711 * blocknr is the block the key points to.
712 *
713 * returns zero on success and < 0 on any error
714 */
715 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
716 *root, struct btrfs_path *path, struct btrfs_disk_key
717 *key, u64 blocknr, int slot, int level)
718 {
719 struct btrfs_node *lower;
720 int nritems;
721
722 BUG_ON(!path->nodes[level]);
723 lower = &path->nodes[level]->node;
724 nritems = btrfs_header_nritems(&lower->header);
725 if (slot > nritems)
726 BUG();
727 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
728 BUG();
729 if (slot != nritems) {
730 memmove(lower->ptrs + slot + 1, lower->ptrs + slot,
731 (nritems - slot) * sizeof(struct btrfs_key_ptr));
732 }
733 memcpy(&lower->ptrs[slot].key, key, sizeof(struct btrfs_disk_key));
734 btrfs_set_node_blockptr(lower, slot, blocknr);
735 btrfs_set_header_nritems(&lower->header, nritems + 1);
736 BUG_ON(list_empty(&path->nodes[level]->dirty));
737 return 0;
738 }
739
740 /*
741 * split the node at the specified level in path in two.
742 * The path is corrected to point to the appropriate node after the split
743 *
744 * Before splitting this tries to make some room in the node by pushing
745 * left and right, if either one works, it returns right away.
746 *
747 * returns 0 on success and < 0 on failure
748 */
749 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
750 *root, struct btrfs_path *path, int level)
751 {
752 struct btrfs_buffer *t;
753 struct btrfs_node *c;
754 struct btrfs_buffer *split_buffer;
755 struct btrfs_node *split;
756 int mid;
757 int ret;
758 int wret;
759 u32 c_nritems;
760
761 t = path->nodes[level];
762 c = &t->node;
763 if (t == root->node) {
764 /* trying to split the root, lets make a new one */
765 ret = insert_new_root(trans, root, path, level + 1);
766 if (ret)
767 return ret;
768 }
769 c_nritems = btrfs_header_nritems(&c->header);
770 split_buffer = btrfs_alloc_free_block(trans, root);
771 split = &split_buffer->node;
772 btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
773 btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
774 btrfs_set_header_blocknr(&split->header, split_buffer->blocknr);
775 btrfs_set_header_owner(&split->header, root->root_key.objectid);
776 memcpy(split->header.fsid, root->fs_info->disk_super->fsid,
777 sizeof(split->header.fsid));
778 mid = (c_nritems + 1) / 2;
779 memcpy(split->ptrs, c->ptrs + mid,
780 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
781 btrfs_set_header_nritems(&split->header, c_nritems - mid);
782 btrfs_set_header_nritems(&c->header, mid);
783 ret = 0;
784
785 BUG_ON(list_empty(&t->dirty));
786 wret = insert_ptr(trans, root, path, &split->ptrs[0].key,
787 split_buffer->blocknr, path->slots[level + 1] + 1,
788 level + 1);
789 if (wret)
790 ret = wret;
791
792 if (path->slots[level] >= mid) {
793 path->slots[level] -= mid;
794 btrfs_block_release(root, t);
795 path->nodes[level] = split_buffer;
796 path->slots[level + 1] += 1;
797 } else {
798 btrfs_block_release(root, split_buffer);
799 }
800 return ret;
801 }
802
803 /*
804 * push some data in the path leaf to the right, trying to free up at
805 * least data_size bytes. returns zero if the push worked, nonzero otherwise
806 *
807 * returns 1 if the push failed because the other node didn't have enough
808 * room, 0 if everything worked out and < 0 if there were major errors.
809 */
810 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
811 *root, struct btrfs_path *path, int data_size)
812 {
813 struct btrfs_buffer *left_buf = path->nodes[0];
814 struct btrfs_leaf *left = &left_buf->leaf;
815 struct btrfs_leaf *right;
816 struct btrfs_buffer *right_buf;
817 struct btrfs_buffer *upper;
818 int slot;
819 int i;
820 int free_space;
821 int push_space = 0;
822 int push_items = 0;
823 struct btrfs_item *item;
824 u32 left_nritems;
825 u32 right_nritems;
826
827 slot = path->slots[1];
828 if (!path->nodes[1]) {
829 return 1;
830 }
831 upper = path->nodes[1];
832 if (slot >= btrfs_header_nritems(&upper->node.header) - 1) {
833 return 1;
834 }
835 right_buf = read_tree_block(root, btrfs_node_blockptr(&upper->node,
836 slot + 1));
837 right = &right_buf->leaf;
838 free_space = btrfs_leaf_free_space(root, right);
839 if (free_space < data_size + sizeof(struct btrfs_item)) {
840 btrfs_block_release(root, right_buf);
841 return 1;
842 }
843 /* cow and double check */
844 btrfs_cow_block(trans, root, right_buf, upper, slot + 1, &right_buf);
845 right = &right_buf->leaf;
846 free_space = btrfs_leaf_free_space(root, right);
847 if (free_space < data_size + sizeof(struct btrfs_item)) {
848 btrfs_block_release(root, right_buf);
849 return 1;
850 }
851
852 left_nritems = btrfs_header_nritems(&left->header);
853 for (i = left_nritems - 1; i >= 0; i--) {
854 item = left->items + i;
855 if (path->slots[0] == i)
856 push_space += data_size + sizeof(*item);
857 if (btrfs_item_size(item) + sizeof(*item) + push_space >
858 free_space)
859 break;
860 push_items++;
861 push_space += btrfs_item_size(item) + sizeof(*item);
862 }
863 if (push_items == 0) {
864 btrfs_block_release(root, right_buf);
865 return 1;
866 }
867 right_nritems = btrfs_header_nritems(&right->header);
868 /* push left to right */
869 push_space = btrfs_item_end(left->items + left_nritems - push_items);
870 push_space -= leaf_data_end(root, left);
871 /* make room in the right data area */
872 memmove(btrfs_leaf_data(right) + leaf_data_end(root, right) -
873 push_space, btrfs_leaf_data(right) + leaf_data_end(root, right),
874 BTRFS_LEAF_DATA_SIZE(root) - leaf_data_end(root, right));
875 /* copy from the left data area */
876 memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) - push_space,
877 btrfs_leaf_data(left) + leaf_data_end(root, left), push_space);
878 memmove(right->items + push_items, right->items,
879 right_nritems * sizeof(struct btrfs_item));
880 /* copy the items from left to right */
881 memcpy(right->items, left->items + left_nritems - push_items,
882 push_items * sizeof(struct btrfs_item));
883
884 /* update the item pointers */
885 right_nritems += push_items;
886 btrfs_set_header_nritems(&right->header, right_nritems);
887 push_space = BTRFS_LEAF_DATA_SIZE(root);
888 for (i = 0; i < right_nritems; i++) {
889 btrfs_set_item_offset(right->items + i, push_space -
890 btrfs_item_size(right->items + i));
891 push_space = btrfs_item_offset(right->items + i);
892 }
893 left_nritems -= push_items;
894 btrfs_set_header_nritems(&left->header, left_nritems);
895
896 BUG_ON(list_empty(&left_buf->dirty));
897 BUG_ON(list_empty(&right_buf->dirty));
898 memcpy(&upper->node.ptrs[slot + 1].key,
899 &right->items[0].key, sizeof(struct btrfs_disk_key));
900 BUG_ON(list_empty(&upper->dirty));
901
902 /* then fixup the leaf pointer in the path */
903 if (path->slots[0] >= left_nritems) {
904 path->slots[0] -= left_nritems;
905 btrfs_block_release(root, path->nodes[0]);
906 path->nodes[0] = right_buf;
907 path->slots[1] += 1;
908 } else {
909 btrfs_block_release(root, right_buf);
910 }
911 return 0;
912 }
913 /*
914 * push some data in the path leaf to the left, trying to free up at
915 * least data_size bytes. returns zero if the push worked, nonzero otherwise
916 */
917 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
918 *root, struct btrfs_path *path, int data_size)
919 {
920 struct btrfs_buffer *right_buf = path->nodes[0];
921 struct btrfs_leaf *right = &right_buf->leaf;
922 struct btrfs_buffer *t;
923 struct btrfs_leaf *left;
924 int slot;
925 int i;
926 int free_space;
927 int push_space = 0;
928 int push_items = 0;
929 struct btrfs_item *item;
930 u32 old_left_nritems;
931 int ret = 0;
932 int wret;
933
934 slot = path->slots[1];
935 if (slot == 0) {
936 return 1;
937 }
938 if (!path->nodes[1]) {
939 return 1;
940 }
941 t = read_tree_block(root, btrfs_node_blockptr(&path->nodes[1]->node,
942 slot - 1));
943 left = &t->leaf;
944 free_space = btrfs_leaf_free_space(root, left);
945 if (free_space < data_size + sizeof(struct btrfs_item)) {
946 btrfs_block_release(root, t);
947 return 1;
948 }
949
950 /* cow and double check */
951 btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t);
952 left = &t->leaf;
953 free_space = btrfs_leaf_free_space(root, left);
954 if (free_space < data_size + sizeof(struct btrfs_item)) {
955 btrfs_block_release(root, t);
956 return 1;
957 }
958
959 for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
960 item = right->items + i;
961 if (path->slots[0] == i)
962 push_space += data_size + sizeof(*item);
963 if (btrfs_item_size(item) + sizeof(*item) + push_space >
964 free_space)
965 break;
966 push_items++;
967 push_space += btrfs_item_size(item) + sizeof(*item);
968 }
969 if (push_items == 0) {
970 btrfs_block_release(root, t);
971 return 1;
972 }
973 /* push data from right to left */
974 memcpy(left->items + btrfs_header_nritems(&left->header),
975 right->items, push_items * sizeof(struct btrfs_item));
976 push_space = BTRFS_LEAF_DATA_SIZE(root) -
977 btrfs_item_offset(right->items + push_items -1);
978 memcpy(btrfs_leaf_data(left) + leaf_data_end(root, left) - push_space,
979 btrfs_leaf_data(right) +
980 btrfs_item_offset(right->items + push_items - 1),
981 push_space);
982 old_left_nritems = btrfs_header_nritems(&left->header);
983 BUG_ON(old_left_nritems < 0);
984
985 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
986 u32 ioff = btrfs_item_offset(left->items + i);
987 btrfs_set_item_offset(left->items + i, ioff -
988 (BTRFS_LEAF_DATA_SIZE(root) -
989 btrfs_item_offset(left->items +
990 old_left_nritems - 1)));
991 }
992 btrfs_set_header_nritems(&left->header, old_left_nritems + push_items);
993
994 /* fixup right node */
995 push_space = btrfs_item_offset(right->items + push_items - 1) -
996 leaf_data_end(root, right);
997 memmove(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
998 push_space, btrfs_leaf_data(right) +
999 leaf_data_end(root, right), push_space);
1000 memmove(right->items, right->items + push_items,
1001 (btrfs_header_nritems(&right->header) - push_items) *
1002 sizeof(struct btrfs_item));
1003 btrfs_set_header_nritems(&right->header,
1004 btrfs_header_nritems(&right->header) -
1005 push_items);
1006 push_space = BTRFS_LEAF_DATA_SIZE(root);
1007
1008 for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1009 btrfs_set_item_offset(right->items + i, push_space -
1010 btrfs_item_size(right->items + i));
1011 push_space = btrfs_item_offset(right->items + i);
1012 }
1013
1014 BUG_ON(list_empty(&t->dirty));
1015 BUG_ON(list_empty(&right_buf->dirty));
1016
1017 wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1);
1018 if (wret)
1019 ret = wret;
1020
1021 /* then fixup the leaf pointer in the path */
1022 if (path->slots[0] < push_items) {
1023 path->slots[0] += old_left_nritems;
1024 btrfs_block_release(root, path->nodes[0]);
1025 path->nodes[0] = t;
1026 path->slots[1] -= 1;
1027 } else {
1028 btrfs_block_release(root, t);
1029 path->slots[0] -= push_items;
1030 }
1031 BUG_ON(path->slots[0] < 0);
1032 return ret;
1033 }
1034
1035 /*
1036 * split the path's leaf in two, making sure there is at least data_size
1037 * available for the resulting leaf level of the path.
1038 *
1039 * returns 0 if all went well and < 0 on failure.
1040 */
1041 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1042 *root, struct btrfs_path *path, int data_size)
1043 {
1044 struct btrfs_buffer *l_buf;
1045 struct btrfs_leaf *l;
1046 u32 nritems;
1047 int mid;
1048 int slot;
1049 struct btrfs_leaf *right;
1050 struct btrfs_buffer *right_buffer;
1051 int space_needed = data_size + sizeof(struct btrfs_item);
1052 int data_copy_size;
1053 int rt_data_off;
1054 int i;
1055 int ret;
1056 int wret;
1057
1058 /* first try to make some room by pushing left and right */
1059 wret = push_leaf_left(trans, root, path, data_size);
1060 if (wret < 0)
1061 return wret;
1062 if (wret) {
1063 wret = push_leaf_right(trans, root, path, data_size);
1064 if (wret < 0)
1065 return wret;
1066 }
1067 l_buf = path->nodes[0];
1068 l = &l_buf->leaf;
1069
1070 /* did the pushes work? */
1071 if (btrfs_leaf_free_space(root, l) >=
1072 sizeof(struct btrfs_item) + data_size)
1073 return 0;
1074
1075 if (!path->nodes[1]) {
1076 ret = insert_new_root(trans, root, path, 1);
1077 if (ret)
1078 return ret;
1079 }
1080 slot = path->slots[0];
1081 nritems = btrfs_header_nritems(&l->header);
1082 mid = (nritems + 1)/ 2;
1083 right_buffer = btrfs_alloc_free_block(trans, root);
1084 BUG_ON(!right_buffer);
1085 BUG_ON(mid == nritems);
1086 right = &right_buffer->leaf;
1087 memset(&right->header, 0, sizeof(right->header));
1088 if (mid <= slot) {
1089 /* FIXME, just alloc a new leaf here */
1090 if (leaf_space_used(l, mid, nritems - mid) + space_needed >
1091 BTRFS_LEAF_DATA_SIZE(root))
1092 BUG();
1093 } else {
1094 /* FIXME, just alloc a new leaf here */
1095 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1096 BTRFS_LEAF_DATA_SIZE(root))
1097 BUG();
1098 }
1099 btrfs_set_header_nritems(&right->header, nritems - mid);
1100 btrfs_set_header_blocknr(&right->header, right_buffer->blocknr);
1101 btrfs_set_header_level(&right->header, 0);
1102 btrfs_set_header_owner(&right->header, root->root_key.objectid);
1103 memcpy(right->header.fsid, root->fs_info->disk_super->fsid,
1104 sizeof(right->header.fsid));
1105 data_copy_size = btrfs_item_end(l->items + mid) -
1106 leaf_data_end(root, l);
1107 memcpy(right->items, l->items + mid,
1108 (nritems - mid) * sizeof(struct btrfs_item));
1109 memcpy(btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1110 data_copy_size, btrfs_leaf_data(l) +
1111 leaf_data_end(root, l), data_copy_size);
1112 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1113 btrfs_item_end(l->items + mid);
1114
1115 for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1116 u32 ioff = btrfs_item_offset(right->items + i);
1117 btrfs_set_item_offset(right->items + i, ioff + rt_data_off);
1118 }
1119
1120 btrfs_set_header_nritems(&l->header, mid);
1121 ret = 0;
1122 wret = insert_ptr(trans, root, path, &right->items[0].key,
1123 right_buffer->blocknr, path->slots[1] + 1, 1);
1124 if (wret)
1125 ret = wret;
1126 BUG_ON(list_empty(&right_buffer->dirty));
1127 BUG_ON(list_empty(&l_buf->dirty));
1128 BUG_ON(path->slots[0] != slot);
1129 if (mid <= slot) {
1130 btrfs_block_release(root, path->nodes[0]);
1131 path->nodes[0] = right_buffer;
1132 path->slots[0] -= mid;
1133 path->slots[1] += 1;
1134 } else
1135 btrfs_block_release(root, right_buffer);
1136 BUG_ON(path->slots[0] < 0);
1137 return ret;
1138 }
1139
1140 /*
1141 * Given a key and some data, insert an item into the tree.
1142 * This does all the path init required, making room in the tree if needed.
1143 */
1144 int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1145 *root, struct btrfs_path *path, struct btrfs_key
1146 *cpu_key, u32 data_size)
1147 {
1148 int ret = 0;
1149 int slot;
1150 int slot_orig;
1151 struct btrfs_leaf *leaf;
1152 struct btrfs_buffer *leaf_buf;
1153 u32 nritems;
1154 unsigned int data_end;
1155 struct btrfs_disk_key disk_key;
1156
1157 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
1158
1159 /* create a root if there isn't one */
1160 if (!root->node)
1161 BUG();
1162 ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
1163 if (ret == 0) {
1164 return -EEXIST;
1165 }
1166 if (ret < 0)
1167 goto out;
1168
1169 slot_orig = path->slots[0];
1170 leaf_buf = path->nodes[0];
1171 leaf = &leaf_buf->leaf;
1172
1173 nritems = btrfs_header_nritems(&leaf->header);
1174 data_end = leaf_data_end(root, leaf);
1175
1176 if (btrfs_leaf_free_space(root, leaf) <
1177 sizeof(struct btrfs_item) + data_size)
1178 BUG();
1179
1180 slot = path->slots[0];
1181 BUG_ON(slot < 0);
1182 if (slot != nritems) {
1183 int i;
1184 unsigned int old_data = btrfs_item_end(leaf->items + slot);
1185
1186 /*
1187 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1188 */
1189 /* first correct the data pointers */
1190 for (i = slot; i < nritems; i++) {
1191 u32 ioff = btrfs_item_offset(leaf->items + i);
1192 btrfs_set_item_offset(leaf->items + i,
1193 ioff - data_size);
1194 }
1195
1196 /* shift the items */
1197 memmove(leaf->items + slot + 1, leaf->items + slot,
1198 (nritems - slot) * sizeof(struct btrfs_item));
1199
1200 /* shift the data */
1201 memmove(btrfs_leaf_data(leaf) + data_end - data_size,
1202 btrfs_leaf_data(leaf) +
1203 data_end, old_data - data_end);
1204 data_end = old_data;
1205 }
1206 /* setup the item for the new data */
1207 memcpy(&leaf->items[slot].key, &disk_key,
1208 sizeof(struct btrfs_disk_key));
1209 btrfs_set_item_offset(leaf->items + slot, data_end - data_size);
1210 btrfs_set_item_size(leaf->items + slot, data_size);
1211 btrfs_set_header_nritems(&leaf->header, nritems + 1);
1212
1213 ret = 0;
1214 if (slot == 0)
1215 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
1216
1217 BUG_ON(list_empty(&leaf_buf->dirty));
1218 if (btrfs_leaf_free_space(root, leaf) < 0)
1219 BUG();
1220 check_leaf(root, path, 0);
1221 out:
1222 return ret;
1223 }
1224
1225 /*
1226 * Given a key and some data, insert an item into the tree.
1227 * This does all the path init required, making room in the tree if needed.
1228 */
1229 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1230 *root, struct btrfs_key *cpu_key, void *data, u32
1231 data_size)
1232 {
1233 int ret = 0;
1234 struct btrfs_path path;
1235 u8 *ptr;
1236
1237 btrfs_init_path(&path);
1238 ret = btrfs_insert_empty_item(trans, root, &path, cpu_key, data_size);
1239 if (!ret) {
1240 ptr = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0], u8);
1241 memcpy(ptr, data, data_size);
1242 }
1243 btrfs_release_path(root, &path);
1244 return ret;
1245 }
1246
1247 /*
1248 * delete the pointer from a given node.
1249 *
1250 * If the delete empties a node, the node is removed from the tree,
1251 * continuing all the way the root if required. The root is converted into
1252 * a leaf if all the nodes are emptied.
1253 */
1254 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1255 struct btrfs_path *path, int level, int slot)
1256 {
1257 struct btrfs_node *node;
1258 struct btrfs_buffer *parent = path->nodes[level];
1259 u32 nritems;
1260 int ret = 0;
1261 int wret;
1262
1263 node = &parent->node;
1264 nritems = btrfs_header_nritems(&node->header);
1265 if (slot != nritems -1) {
1266 memmove(node->ptrs + slot, node->ptrs + slot + 1,
1267 sizeof(struct btrfs_key_ptr) * (nritems - slot - 1));
1268 }
1269 nritems--;
1270 btrfs_set_header_nritems(&node->header, nritems);
1271 if (nritems == 0 && parent == root->node) {
1272 BUG_ON(btrfs_header_level(&root->node->node.header) != 1);
1273 /* just turn the root into a leaf and break */
1274 btrfs_set_header_level(&root->node->node.header, 0);
1275 } else if (slot == 0) {
1276 wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key,
1277 level + 1);
1278 if (wret)
1279 ret = wret;
1280 }
1281 BUG_ON(list_empty(&parent->dirty));
1282 return ret;
1283 }
1284
1285 /*
1286 * delete the item at the leaf level in path. If that empties
1287 * the leaf, remove it from the tree
1288 */
1289 int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1290 struct btrfs_path *path)
1291 {
1292 int slot;
1293 struct btrfs_leaf *leaf;
1294 struct btrfs_buffer *leaf_buf;
1295 int doff;
1296 int dsize;
1297 int ret = 0;
1298 int wret;
1299 u32 nritems;
1300
1301 leaf_buf = path->nodes[0];
1302 leaf = &leaf_buf->leaf;
1303 slot = path->slots[0];
1304 doff = btrfs_item_offset(leaf->items + slot);
1305 dsize = btrfs_item_size(leaf->items + slot);
1306 nritems = btrfs_header_nritems(&leaf->header);
1307
1308 if (slot != nritems - 1) {
1309 int i;
1310 int data_end = leaf_data_end(root, leaf);
1311 memmove(btrfs_leaf_data(leaf) + data_end + dsize,
1312 btrfs_leaf_data(leaf) + data_end,
1313 doff - data_end);
1314 for (i = slot + 1; i < nritems; i++) {
1315 u32 ioff = btrfs_item_offset(leaf->items + i);
1316 btrfs_set_item_offset(leaf->items + i, ioff + dsize);
1317 }
1318 memmove(leaf->items + slot, leaf->items + slot + 1,
1319 sizeof(struct btrfs_item) *
1320 (nritems - slot - 1));
1321 }
1322 btrfs_set_header_nritems(&leaf->header, nritems - 1);
1323 nritems--;
1324 /* delete the leaf if we've emptied it */
1325 if (nritems == 0) {
1326 if (leaf_buf == root->node) {
1327 btrfs_set_header_level(&leaf->header, 0);
1328 BUG_ON(list_empty(&leaf_buf->dirty));
1329 } else {
1330 clean_tree_block(trans, root, leaf_buf);
1331 wret = del_ptr(trans, root, path, 1, path->slots[1]);
1332 if (wret)
1333 ret = wret;
1334 wret = btrfs_free_extent(trans, root,
1335 leaf_buf->blocknr, 1, 1);
1336 if (wret)
1337 ret = wret;
1338 }
1339 } else {
1340 int used = leaf_space_used(leaf, 0, nritems);
1341 if (slot == 0) {
1342 wret = fixup_low_keys(trans, root, path,
1343 &leaf->items[0].key, 1);
1344 if (wret)
1345 ret = wret;
1346 }
1347 BUG_ON(list_empty(&leaf_buf->dirty));
1348
1349 /* delete the leaf if it is mostly empty */
1350 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
1351 /* push_leaf_left fixes the path.
1352 * make sure the path still points to our leaf
1353 * for possible call to del_ptr below
1354 */
1355 slot = path->slots[1];
1356 leaf_buf->count++;
1357 wret = push_leaf_left(trans, root, path, 1);
1358 if (wret < 0)
1359 ret = wret;
1360 if (path->nodes[0] == leaf_buf &&
1361 btrfs_header_nritems(&leaf->header)) {
1362 wret = push_leaf_right(trans, root, path, 1);
1363 if (wret < 0)
1364 ret = wret;
1365 }
1366 if (btrfs_header_nritems(&leaf->header) == 0) {
1367 u64 blocknr = leaf_buf->blocknr;
1368 clean_tree_block(trans, root, leaf_buf);
1369 wret = del_ptr(trans, root, path, 1, slot);
1370 if (wret)
1371 ret = wret;
1372 btrfs_block_release(root, leaf_buf);
1373 wret = btrfs_free_extent(trans, root, blocknr,
1374 1, 1);
1375 if (wret)
1376 ret = wret;
1377 } else {
1378 btrfs_block_release(root, leaf_buf);
1379 }
1380 }
1381 }
1382 return ret;
1383 }
1384
1385 int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1386 *root, struct btrfs_path *path, u32 data_size)
1387 {
1388 int ret = 0;
1389 int slot;
1390 int slot_orig;
1391 struct btrfs_leaf *leaf;
1392 struct btrfs_buffer *leaf_buf;
1393 u32 nritems;
1394 unsigned int data_end;
1395 unsigned int old_data;
1396 unsigned int old_size;
1397 int i;
1398
1399 slot_orig = path->slots[0];
1400 leaf_buf = path->nodes[0];
1401 leaf = &leaf_buf->leaf;
1402
1403 nritems = btrfs_header_nritems(&leaf->header);
1404 data_end = leaf_data_end(root, leaf);
1405
1406 if (btrfs_leaf_free_space(root, leaf) < data_size)
1407 BUG();
1408 slot = path->slots[0];
1409 old_data = btrfs_item_end(leaf->items + slot);
1410
1411 BUG_ON(slot < 0);
1412 BUG_ON(slot >= nritems);
1413
1414 /*
1415 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1416 */
1417 /* first correct the data pointers */
1418 for (i = slot; i < nritems; i++) {
1419 u32 ioff = btrfs_item_offset(leaf->items + i);
1420 btrfs_set_item_offset(leaf->items + i,
1421 ioff - data_size);
1422 }
1423 /* shift the data */
1424 memmove(btrfs_leaf_data(leaf) + data_end - data_size,
1425 btrfs_leaf_data(leaf) + data_end, old_data - data_end);
1426 data_end = old_data;
1427 old_size = btrfs_item_size(leaf->items + slot);
1428 btrfs_set_item_size(leaf->items + slot, old_size + data_size);
1429
1430 ret = 0;
1431 if (btrfs_leaf_free_space(root, leaf) < 0)
1432 BUG();
1433 check_leaf(root, path, 0);
1434 return ret;
1435 }
1436
1437 /*
1438 * walk up the tree as far as required to find the next leaf.
1439 * returns 0 if it found something or 1 if there are no greater leaves.
1440 * returns < 0 on io errors.
1441 */
1442 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
1443 {
1444 int slot;
1445 int level = 1;
1446 u64 blocknr;
1447 struct btrfs_buffer *c;
1448 struct btrfs_buffer *next = NULL;
1449
1450 while(level < BTRFS_MAX_LEVEL) {
1451 if (!path->nodes[level])
1452 return 1;
1453 slot = path->slots[level] + 1;
1454 c = path->nodes[level];
1455 if (slot >= btrfs_header_nritems(&c->node.header)) {
1456 level++;
1457 continue;
1458 }
1459 blocknr = btrfs_node_blockptr(&c->node, slot);
1460 if (next)
1461 btrfs_block_release(root, next);
1462 next = read_tree_block(root, blocknr);
1463 break;
1464 }
1465 path->slots[level] = slot;
1466 while(1) {
1467 level--;
1468 c = path->nodes[level];
1469 btrfs_block_release(root, c);
1470 path->nodes[level] = next;
1471 path->slots[level] = 0;
1472 if (!level)
1473 break;
1474 next = read_tree_block(root,
1475 btrfs_node_blockptr(&next->node, 0));
1476 }
1477 return 0;
1478 }
Btrfs-progs-unstable mirror