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