projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Btrfs: Btree defrag on the extent-mapping tree as well
[deliverable/linux.git] / fs / btrfs / ctree.c
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 "ctree.h"
20 #include "disk-io.h"
21 #include "transaction.h"
22
23 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
24 *root, struct btrfs_path *path, int level);
25 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
26 *root, struct btrfs_key *ins_key,
27 struct btrfs_path *path, int data_size);
28 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
29 *root, struct buffer_head *dst, struct buffer_head
30 *src);
31 static int balance_node_right(struct btrfs_trans_handle *trans, struct
32 btrfs_root *root, struct buffer_head *dst_buf,
33 struct buffer_head *src_buf);
34 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
35 struct btrfs_path *path, int level, int slot);
36
37 inline void btrfs_init_path(struct btrfs_path *p)
38 {
39 memset(p, 0, sizeof(*p));
40 }
41
42 struct btrfs_path *btrfs_alloc_path(void)
43 {
44 struct btrfs_path *path;
45 path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
46 if (path)
47 btrfs_init_path(path);
48 return path;
49 }
50
51 void btrfs_free_path(struct btrfs_path *p)
52 {
53 btrfs_release_path(NULL, p);
54 kmem_cache_free(btrfs_path_cachep, p);
55 }
56
57 void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
58 {
59 int i;
60 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
61 if (!p->nodes[i])
62 break;
63 btrfs_block_release(root, p->nodes[i]);
64 }
65 memset(p, 0, sizeof(*p));
66 }
67
68 static int __btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
69 *root, struct buffer_head *buf, struct buffer_head
70 *parent, int parent_slot, struct buffer_head
71 **cow_ret, u64 search_start, u64 empty_size)
72 {
73 struct buffer_head *cow;
74 struct btrfs_node *cow_node;
75 int ret = 0;
76 int different_trans = 0;
77
78 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
79 WARN_ON(!buffer_uptodate(buf));
80 cow = btrfs_alloc_free_block(trans, root, search_start, empty_size);
81 if (IS_ERR(cow))
82 return PTR_ERR(cow);
83
84 cow_node = btrfs_buffer_node(cow);
85 if (buf->b_size != root->blocksize || cow->b_size != root->blocksize)
86 WARN_ON(1);
87
88 memcpy(cow_node, btrfs_buffer_node(buf), root->blocksize);
89 btrfs_set_header_blocknr(&cow_node->header, bh_blocknr(cow));
90 btrfs_set_header_generation(&cow_node->header, trans->transid);
91 btrfs_set_header_owner(&cow_node->header, root->root_key.objectid);
92
93 WARN_ON(btrfs_header_generation(btrfs_buffer_header(buf)) >
94 trans->transid);
95 if (btrfs_header_generation(btrfs_buffer_header(buf)) !=
96 trans->transid) {
97 different_trans = 1;
98 ret = btrfs_inc_ref(trans, root, buf);
99 if (ret)
100 return ret;
101 } else {
102 clean_tree_block(trans, root, buf);
103 }
104
105 if (buf == root->node) {
106 root->node = cow;
107 get_bh(cow);
108 if (buf != root->commit_root) {
109 btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1);
110 }
111 btrfs_block_release(root, buf);
112 } else {
113 btrfs_set_node_blockptr(btrfs_buffer_node(parent), parent_slot,
114 bh_blocknr(cow));
115 btrfs_mark_buffer_dirty(parent);
116 WARN_ON(btrfs_header_generation(btrfs_buffer_header(parent)) !=
117 trans->transid);
118 btrfs_free_extent(trans, root, bh_blocknr(buf), 1, 1);
119 }
120 btrfs_block_release(root, buf);
121 btrfs_mark_buffer_dirty(cow);
122 *cow_ret = cow;
123 return 0;
124 }
125
126 int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root
127 *root, struct buffer_head *buf, struct buffer_head
128 *parent, int parent_slot, struct buffer_head
129 **cow_ret)
130 {
131 u64 search_start;
132 if (trans->transaction != root->fs_info->running_transaction) {
133 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
134 root->fs_info->running_transaction->transid);
135 WARN_ON(1);
136 }
137 if (trans->transid != root->fs_info->generation) {
138 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
139 root->fs_info->generation);
140 WARN_ON(1);
141 }
142 if (btrfs_header_generation(btrfs_buffer_header(buf)) ==
143 trans->transid) {
144 *cow_ret = buf;
145 return 0;
146 }
147
148 search_start = bh_blocknr(buf) & ~((u64)65535);
149 return __btrfs_cow_block(trans, root, buf, parent,
150 parent_slot, cow_ret, search_start, 0);
151 }
152
153 static int close_blocks(u64 blocknr, u64 other)
154 {
155 if (blocknr < other && other - blocknr < 8)
156 return 1;
157 if (blocknr > other && blocknr - other < 8)
158 return 1;
159 return 0;
160 }
161
162 int btrfs_realloc_node(struct btrfs_trans_handle *trans,
163 struct btrfs_root *root, struct buffer_head *parent,
164 int cache_only, u64 *last_ret)
165 {
166 struct btrfs_node *parent_node;
167 struct buffer_head *cur_bh;
168 struct buffer_head *tmp_bh;
169 u64 blocknr;
170 u64 search_start = *last_ret;
171 u64 last_block = 0;
172 u64 other;
173 u32 parent_nritems;
174 int start_slot;
175 int end_slot;
176 int i;
177 int err = 0;
178
179 if (trans->transaction != root->fs_info->running_transaction) {
180 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
181 root->fs_info->running_transaction->transid);
182 WARN_ON(1);
183 }
184 if (trans->transid != root->fs_info->generation) {
185 printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
186 root->fs_info->generation);
187 WARN_ON(1);
188 }
189 parent_node = btrfs_buffer_node(parent);
190 parent_nritems = btrfs_header_nritems(&parent_node->header);
191
192 start_slot = 0;
193 end_slot = parent_nritems;
194
195 if (parent_nritems == 1)
196 return 0;
197
198 for (i = start_slot; i < end_slot; i++) {
199 int close = 1;
200 blocknr = btrfs_node_blockptr(parent_node, i);
201 if (last_block == 0)
202 last_block = blocknr;
203 if (i > 0) {
204 other = btrfs_node_blockptr(parent_node, i - 1);
205 close = close_blocks(blocknr, other);
206 }
207 if (close && i < end_slot - 1) {
208 other = btrfs_node_blockptr(parent_node, i + 1);
209 close = close_blocks(blocknr, other);
210 }
211 if (close) {
212 last_block = blocknr;
213 continue;
214 }
215
216 cur_bh = btrfs_find_tree_block(root, blocknr);
217 if (!cur_bh || !buffer_uptodate(cur_bh) ||
218 buffer_locked(cur_bh)) {
219 if (cache_only) {
220 brelse(cur_bh);
221 continue;
222 }
223 brelse(cur_bh);
224 cur_bh = read_tree_block(root, blocknr);
225 }
226 if (search_start == 0)
227 search_start = last_block & ~((u64)65535);
228
229 err = __btrfs_cow_block(trans, root, cur_bh, parent, i,
230 &tmp_bh, search_start,
231 min(8, end_slot - i));
232 if (err)
233 break;
234 search_start = bh_blocknr(tmp_bh);
235 brelse(tmp_bh);
236 }
237 return err;
238 }
239
240 /*
241 * The leaf data grows from end-to-front in the node.
242 * this returns the address of the start of the last item,
243 * which is the stop of the leaf data stack
244 */
245 static inline unsigned int leaf_data_end(struct btrfs_root *root,
246 struct btrfs_leaf *leaf)
247 {
248 u32 nr = btrfs_header_nritems(&leaf->header);
249 if (nr == 0)
250 return BTRFS_LEAF_DATA_SIZE(root);
251 return btrfs_item_offset(leaf->items + nr - 1);
252 }
253
254 /*
255 * compare two keys in a memcmp fashion
256 */
257 static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
258 {
259 struct btrfs_key k1;
260
261 btrfs_disk_key_to_cpu(&k1, disk);
262
263 if (k1.objectid > k2->objectid)
264 return 1;
265 if (k1.objectid < k2->objectid)
266 return -1;
267 if (k1.flags > k2->flags)
268 return 1;
269 if (k1.flags < k2->flags)
270 return -1;
271 if (k1.offset > k2->offset)
272 return 1;
273 if (k1.offset < k2->offset)
274 return -1;
275 return 0;
276 }
277
278 static int check_node(struct btrfs_root *root, struct btrfs_path *path,
279 int level)
280 {
281 struct btrfs_node *parent = NULL;
282 struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]);
283 int parent_slot;
284 int slot;
285 struct btrfs_key cpukey;
286 u32 nritems = btrfs_header_nritems(&node->header);
287
288 if (path->nodes[level + 1])
289 parent = btrfs_buffer_node(path->nodes[level + 1]);
290
291 slot = path->slots[level];
292 BUG_ON(nritems == 0);
293 if (parent) {
294 struct btrfs_disk_key *parent_key;
295
296 parent_slot = path->slots[level + 1];
297 parent_key = &parent->ptrs[parent_slot].key;
298 BUG_ON(memcmp(parent_key, &node->ptrs[0].key,
299 sizeof(struct btrfs_disk_key)));
300 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
301 btrfs_header_blocknr(&node->header));
302 }
303 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
304 if (slot != 0) {
305 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot - 1].key);
306 BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) <= 0);
307 }
308 if (slot < nritems - 1) {
309 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[slot + 1].key);
310 BUG_ON(comp_keys(&node->ptrs[slot].key, &cpukey) >= 0);
311 }
312 return 0;
313 }
314
315 static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
316 int level)
317 {
318 struct btrfs_leaf *leaf = btrfs_buffer_leaf(path->nodes[level]);
319 struct btrfs_node *parent = NULL;
320 int parent_slot;
321 int slot = path->slots[0];
322 struct btrfs_key cpukey;
323
324 u32 nritems = btrfs_header_nritems(&leaf->header);
325
326 if (path->nodes[level + 1])
327 parent = btrfs_buffer_node(path->nodes[level + 1]);
328
329 BUG_ON(btrfs_leaf_free_space(root, leaf) < 0);
330
331 if (nritems == 0)
332 return 0;
333
334 if (parent) {
335 struct btrfs_disk_key *parent_key;
336
337 parent_slot = path->slots[level + 1];
338 parent_key = &parent->ptrs[parent_slot].key;
339
340 BUG_ON(memcmp(parent_key, &leaf->items[0].key,
341 sizeof(struct btrfs_disk_key)));
342 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
343 btrfs_header_blocknr(&leaf->header));
344 }
345 if (slot != 0) {
346 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot - 1].key);
347 BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) <= 0);
348 BUG_ON(btrfs_item_offset(leaf->items + slot - 1) !=
349 btrfs_item_end(leaf->items + slot));
350 }
351 if (slot < nritems - 1) {
352 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[slot + 1].key);
353 BUG_ON(comp_keys(&leaf->items[slot].key, &cpukey) >= 0);
354 BUG_ON(btrfs_item_offset(leaf->items + slot) !=
355 btrfs_item_end(leaf->items + slot + 1));
356 }
357 BUG_ON(btrfs_item_offset(leaf->items) +
358 btrfs_item_size(leaf->items) != BTRFS_LEAF_DATA_SIZE(root));
359 return 0;
360 }
361
362 static int check_block(struct btrfs_root *root, struct btrfs_path *path,
363 int level)
364 {
365 struct btrfs_node *node = btrfs_buffer_node(path->nodes[level]);
366 if (memcmp(node->header.fsid, root->fs_info->disk_super->fsid,
367 sizeof(node->header.fsid)))
368 BUG();
369 if (level == 0)
370 return check_leaf(root, path, level);
371 return check_node(root, path, level);
372 }
373
374 /*
375 * search for key in the array p. items p are item_size apart
376 * and there are 'max' items in p
377 * the slot in the array is returned via slot, and it points to
378 * the place where you would insert key if it is not found in
379 * the array.
380 *
381 * slot may point to max if the key is bigger than all of the keys
382 */
383 static int generic_bin_search(char *p, int item_size, struct btrfs_key *key,
384 int max, int *slot)
385 {
386 int low = 0;
387 int high = max;
388 int mid;
389 int ret;
390 struct btrfs_disk_key *tmp;
391
392 while(low < high) {
393 mid = (low + high) / 2;
394 tmp = (struct btrfs_disk_key *)(p + mid * item_size);
395 ret = comp_keys(tmp, key);
396
397 if (ret < 0)
398 low = mid + 1;
399 else if (ret > 0)
400 high = mid;
401 else {
402 *slot = mid;
403 return 0;
404 }
405 }
406 *slot = low;
407 return 1;
408 }
409
410 /*
411 * simple bin_search frontend that does the right thing for
412 * leaves vs nodes
413 */
414 static int bin_search(struct btrfs_node *c, struct btrfs_key *key, int *slot)
415 {
416 if (btrfs_is_leaf(c)) {
417 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
418 return generic_bin_search((void *)l->items,
419 sizeof(struct btrfs_item),
420 key, btrfs_header_nritems(&c->header),
421 slot);
422 } else {
423 return generic_bin_search((void *)c->ptrs,
424 sizeof(struct btrfs_key_ptr),
425 key, btrfs_header_nritems(&c->header),
426 slot);
427 }
428 return -1;
429 }
430
431 static struct buffer_head *read_node_slot(struct btrfs_root *root,
432 struct buffer_head *parent_buf,
433 int slot)
434 {
435 struct btrfs_node *node = btrfs_buffer_node(parent_buf);
436 if (slot < 0)
437 return NULL;
438 if (slot >= btrfs_header_nritems(&node->header))
439 return NULL;
440 return read_tree_block(root, btrfs_node_blockptr(node, slot));
441 }
442
443 static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
444 *root, struct btrfs_path *path, int level)
445 {
446 struct buffer_head *right_buf;
447 struct buffer_head *mid_buf;
448 struct buffer_head *left_buf;
449 struct buffer_head *parent_buf = NULL;
450 struct btrfs_node *right = NULL;
451 struct btrfs_node *mid;
452 struct btrfs_node *left = NULL;
453 struct btrfs_node *parent = NULL;
454 int ret = 0;
455 int wret;
456 int pslot;
457 int orig_slot = path->slots[level];
458 int err_on_enospc = 0;
459 u64 orig_ptr;
460
461 if (level == 0)
462 return 0;
463
464 mid_buf = path->nodes[level];
465 mid = btrfs_buffer_node(mid_buf);
466 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
467
468 if (level < BTRFS_MAX_LEVEL - 1)
469 parent_buf = path->nodes[level + 1];
470 pslot = path->slots[level + 1];
471
472 /*
473 * deal with the case where there is only one pointer in the root
474 * by promoting the node below to a root
475 */
476 if (!parent_buf) {
477 struct buffer_head *child;
478 u64 blocknr = bh_blocknr(mid_buf);
479
480 if (btrfs_header_nritems(&mid->header) != 1)
481 return 0;
482
483 /* promote the child to a root */
484 child = read_node_slot(root, mid_buf, 0);
485 BUG_ON(!child);
486 root->node = child;
487 path->nodes[level] = NULL;
488 clean_tree_block(trans, root, mid_buf);
489 wait_on_buffer(mid_buf);
490 /* once for the path */
491 btrfs_block_release(root, mid_buf);
492 /* once for the root ptr */
493 btrfs_block_release(root, mid_buf);
494 return btrfs_free_extent(trans, root, blocknr, 1, 1);
495 }
496 parent = btrfs_buffer_node(parent_buf);
497
498 if (btrfs_header_nritems(&mid->header) >
499 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
500 return 0;
501
502 if (btrfs_header_nritems(&mid->header) < 2)
503 err_on_enospc = 1;
504
505 left_buf = read_node_slot(root, parent_buf, pslot - 1);
506 right_buf = read_node_slot(root, parent_buf, pslot + 1);
507
508 /* first, try to make some room in the middle buffer */
509 if (left_buf) {
510 wret = btrfs_cow_block(trans, root, left_buf,
511 parent_buf, pslot - 1, &left_buf);
512 if (wret) {
513 ret = wret;
514 goto enospc;
515 }
516 left = btrfs_buffer_node(left_buf);
517 orig_slot += btrfs_header_nritems(&left->header);
518 wret = push_node_left(trans, root, left_buf, mid_buf);
519 if (wret < 0)
520 ret = wret;
521 if (btrfs_header_nritems(&mid->header) < 2)
522 err_on_enospc = 1;
523 }
524
525 /*
526 * then try to empty the right most buffer into the middle
527 */
528 if (right_buf) {
529 wret = btrfs_cow_block(trans, root, right_buf,
530 parent_buf, pslot + 1, &right_buf);
531 if (wret) {
532 ret = wret;
533 goto enospc;
534 }
535
536 right = btrfs_buffer_node(right_buf);
537 wret = push_node_left(trans, root, mid_buf, right_buf);
538 if (wret < 0 && wret != -ENOSPC)
539 ret = wret;
540 if (btrfs_header_nritems(&right->header) == 0) {
541 u64 blocknr = bh_blocknr(right_buf);
542 clean_tree_block(trans, root, right_buf);
543 wait_on_buffer(right_buf);
544 btrfs_block_release(root, right_buf);
545 right_buf = NULL;
546 right = NULL;
547 wret = del_ptr(trans, root, path, level + 1, pslot +
548 1);
549 if (wret)
550 ret = wret;
551 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
552 if (wret)
553 ret = wret;
554 } else {
555 btrfs_memcpy(root, parent,
556 &parent->ptrs[pslot + 1].key,
557 &right->ptrs[0].key,
558 sizeof(struct btrfs_disk_key));
559 btrfs_mark_buffer_dirty(parent_buf);
560 }
561 }
562 if (btrfs_header_nritems(&mid->header) == 1) {
563 /*
564 * we're not allowed to leave a node with one item in the
565 * tree during a delete. A deletion from lower in the tree
566 * could try to delete the only pointer in this node.
567 * So, pull some keys from the left.
568 * There has to be a left pointer at this point because
569 * otherwise we would have pulled some pointers from the
570 * right
571 */
572 BUG_ON(!left_buf);
573 wret = balance_node_right(trans, root, mid_buf, left_buf);
574 if (wret < 0) {
575 ret = wret;
576 goto enospc;
577 }
578 BUG_ON(wret == 1);
579 }
580 if (btrfs_header_nritems(&mid->header) == 0) {
581 /* we've managed to empty the middle node, drop it */
582 u64 blocknr = bh_blocknr(mid_buf);
583 clean_tree_block(trans, root, mid_buf);
584 wait_on_buffer(mid_buf);
585 btrfs_block_release(root, mid_buf);
586 mid_buf = NULL;
587 mid = NULL;
588 wret = del_ptr(trans, root, path, level + 1, pslot);
589 if (wret)
590 ret = wret;
591 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
592 if (wret)
593 ret = wret;
594 } else {
595 /* update the parent key to reflect our changes */
596 btrfs_memcpy(root, parent,
597 &parent->ptrs[pslot].key, &mid->ptrs[0].key,
598 sizeof(struct btrfs_disk_key));
599 btrfs_mark_buffer_dirty(parent_buf);
600 }
601
602 /* update the path */
603 if (left_buf) {
604 if (btrfs_header_nritems(&left->header) > orig_slot) {
605 get_bh(left_buf);
606 path->nodes[level] = left_buf;
607 path->slots[level + 1] -= 1;
608 path->slots[level] = orig_slot;
609 if (mid_buf)
610 btrfs_block_release(root, mid_buf);
611 } else {
612 orig_slot -= btrfs_header_nritems(&left->header);
613 path->slots[level] = orig_slot;
614 }
615 }
616 /* double check we haven't messed things up */
617 check_block(root, path, level);
618 if (orig_ptr !=
619 btrfs_node_blockptr(btrfs_buffer_node(path->nodes[level]),
620 path->slots[level]))
621 BUG();
622 enospc:
623 if (right_buf)
624 btrfs_block_release(root, right_buf);
625 if (left_buf)
626 btrfs_block_release(root, left_buf);
627 return ret;
628 }
629
630 /* returns zero if the push worked, non-zero otherwise */
631 static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
632 struct btrfs_root *root,
633 struct btrfs_path *path, int level)
634 {
635 struct buffer_head *right_buf;
636 struct buffer_head *mid_buf;
637 struct buffer_head *left_buf;
638 struct buffer_head *parent_buf = NULL;
639 struct btrfs_node *right = NULL;
640 struct btrfs_node *mid;
641 struct btrfs_node *left = NULL;
642 struct btrfs_node *parent = NULL;
643 int ret = 0;
644 int wret;
645 int pslot;
646 int orig_slot = path->slots[level];
647 u64 orig_ptr;
648
649 if (level == 0)
650 return 1;
651
652 mid_buf = path->nodes[level];
653 mid = btrfs_buffer_node(mid_buf);
654 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
655
656 if (level < BTRFS_MAX_LEVEL - 1)
657 parent_buf = path->nodes[level + 1];
658 pslot = path->slots[level + 1];
659
660 if (!parent_buf)
661 return 1;
662 parent = btrfs_buffer_node(parent_buf);
663
664 left_buf = read_node_slot(root, parent_buf, pslot - 1);
665
666 /* first, try to make some room in the middle buffer */
667 if (left_buf) {
668 u32 left_nr;
669 left = btrfs_buffer_node(left_buf);
670 left_nr = btrfs_header_nritems(&left->header);
671 if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
672 wret = 1;
673 } else {
674 ret = btrfs_cow_block(trans, root, left_buf, parent_buf,
675 pslot - 1, &left_buf);
676 if (ret)
677 wret = 1;
678 else {
679 left = btrfs_buffer_node(left_buf);
680 wret = push_node_left(trans, root,
681 left_buf, mid_buf);
682 }
683 }
684 if (wret < 0)
685 ret = wret;
686 if (wret == 0) {
687 orig_slot += left_nr;
688 btrfs_memcpy(root, parent,
689 &parent->ptrs[pslot].key,
690 &mid->ptrs[0].key,
691 sizeof(struct btrfs_disk_key));
692 btrfs_mark_buffer_dirty(parent_buf);
693 if (btrfs_header_nritems(&left->header) > orig_slot) {
694 path->nodes[level] = left_buf;
695 path->slots[level + 1] -= 1;
696 path->slots[level] = orig_slot;
697 btrfs_block_release(root, mid_buf);
698 } else {
699 orig_slot -=
700 btrfs_header_nritems(&left->header);
701 path->slots[level] = orig_slot;
702 btrfs_block_release(root, left_buf);
703 }
704 check_node(root, path, level);
705 return 0;
706 }
707 btrfs_block_release(root, left_buf);
708 }
709 right_buf = read_node_slot(root, parent_buf, pslot + 1);
710
711 /*
712 * then try to empty the right most buffer into the middle
713 */
714 if (right_buf) {
715 u32 right_nr;
716 right = btrfs_buffer_node(right_buf);
717 right_nr = btrfs_header_nritems(&right->header);
718 if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
719 wret = 1;
720 } else {
721 ret = btrfs_cow_block(trans, root, right_buf,
722 parent_buf, pslot + 1,
723 &right_buf);
724 if (ret)
725 wret = 1;
726 else {
727 right = btrfs_buffer_node(right_buf);
728 wret = balance_node_right(trans, root,
729 right_buf, mid_buf);
730 }
731 }
732 if (wret < 0)
733 ret = wret;
734 if (wret == 0) {
735 btrfs_memcpy(root, parent,
736 &parent->ptrs[pslot + 1].key,
737 &right->ptrs[0].key,
738 sizeof(struct btrfs_disk_key));
739 btrfs_mark_buffer_dirty(parent_buf);
740 if (btrfs_header_nritems(&mid->header) <= orig_slot) {
741 path->nodes[level] = right_buf;
742 path->slots[level + 1] += 1;
743 path->slots[level] = orig_slot -
744 btrfs_header_nritems(&mid->header);
745 btrfs_block_release(root, mid_buf);
746 } else {
747 btrfs_block_release(root, right_buf);
748 }
749 check_node(root, path, level);
750 return 0;
751 }
752 btrfs_block_release(root, right_buf);
753 }
754 check_node(root, path, level);
755 return 1;
756 }
757
758 /*
759 * readahead one full node of leaves
760 */
761 static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
762 int level, int slot)
763 {
764 struct btrfs_node *node;
765 int i;
766 u32 nritems;
767 u64 item_objectid;
768 u64 blocknr;
769 u64 search;
770 u64 cluster_start;
771 int ret;
772 int nread = 0;
773 int direction = path->reada;
774 struct radix_tree_root found;
775 unsigned long gang[8];
776 struct buffer_head *bh;
777
778 if (level == 0)
779 return;
780
781 if (!path->nodes[level])
782 return;
783
784 node = btrfs_buffer_node(path->nodes[level]);
785 search = btrfs_node_blockptr(node, slot);
786 bh = btrfs_find_tree_block(root, search);
787 if (bh) {
788 brelse(bh);
789 return;
790 }
791
792 init_bit_radix(&found);
793 nritems = btrfs_header_nritems(&node->header);
794 for (i = slot; i < nritems; i++) {
795 item_objectid = btrfs_disk_key_objectid(&node->ptrs[i].key);
796 blocknr = btrfs_node_blockptr(node, i);
797 set_radix_bit(&found, blocknr);
798 }
799 if (direction > 0) {
800 cluster_start = search - 4;
801 if (cluster_start > search)
802 cluster_start = 0;
803 } else
804 cluster_start = search + 4;
805 while(1) {
806 ret = find_first_radix_bit(&found, gang, 0, ARRAY_SIZE(gang));
807 if (!ret)
808 break;
809 for (i = 0; i < ret; i++) {
810 blocknr = gang[i];
811 clear_radix_bit(&found, blocknr);
812 if (nread > 32)
813 continue;
814 if (direction > 0 && cluster_start <= blocknr &&
815 cluster_start + 8 > blocknr) {
816 cluster_start = blocknr;
817 readahead_tree_block(root, blocknr);
818 nread++;
819 } else if (direction < 0 && cluster_start >= blocknr &&
820 blocknr + 8 > cluster_start) {
821 cluster_start = blocknr;
822 readahead_tree_block(root, blocknr);
823 nread++;
824 }
825 }
826 }
827 }
828 /*
829 * look for key in the tree. path is filled in with nodes along the way
830 * if key is found, we return zero and you can find the item in the leaf
831 * level of the path (level 0)
832 *
833 * If the key isn't found, the path points to the slot where it should
834 * be inserted, and 1 is returned. If there are other errors during the
835 * search a negative error number is returned.
836 *
837 * if ins_len > 0, nodes and leaves will be split as we walk down the
838 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
839 * possible)
840 */
841 int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
842 *root, struct btrfs_key *key, struct btrfs_path *p, int
843 ins_len, int cow)
844 {
845 struct buffer_head *b;
846 struct buffer_head *cow_buf;
847 struct btrfs_node *c;
848 u64 blocknr;
849 int slot;
850 int ret;
851 int level;
852 int should_reada = p->reada;
853 u8 lowest_level = 0;
854
855 lowest_level = p->lowest_level;
856 WARN_ON(lowest_level && ins_len);
857 WARN_ON(p->nodes[0] != NULL);
858 WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
859 again:
860 b = root->node;
861 get_bh(b);
862 while (b) {
863 c = btrfs_buffer_node(b);
864 level = btrfs_header_level(&c->header);
865 if (cow) {
866 int wret;
867 wret = btrfs_cow_block(trans, root, b,
868 p->nodes[level + 1],
869 p->slots[level + 1],
870 &cow_buf);
871 if (wret) {
872 btrfs_block_release(root, cow_buf);
873 return wret;
874 }
875 b = cow_buf;
876 c = btrfs_buffer_node(b);
877 }
878 BUG_ON(!cow && ins_len);
879 if (level != btrfs_header_level(&c->header))
880 WARN_ON(1);
881 level = btrfs_header_level(&c->header);
882 p->nodes[level] = b;
883 ret = check_block(root, p, level);
884 if (ret)
885 return -1;
886 ret = bin_search(c, key, &slot);
887 if (!btrfs_is_leaf(c)) {
888 if (ret && slot > 0)
889 slot -= 1;
890 p->slots[level] = slot;
891 if (ins_len > 0 && btrfs_header_nritems(&c->header) >=
892 BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
893 int sret = split_node(trans, root, p, level);
894 BUG_ON(sret > 0);
895 if (sret)
896 return sret;
897 b = p->nodes[level];
898 c = btrfs_buffer_node(b);
899 slot = p->slots[level];
900 } else if (ins_len < 0) {
901 int sret = balance_level(trans, root, p,
902 level);
903 if (sret)
904 return sret;
905 b = p->nodes[level];
906 if (!b)
907 goto again;
908 c = btrfs_buffer_node(b);
909 slot = p->slots[level];
910 BUG_ON(btrfs_header_nritems(&c->header) == 1);
911 }
912 /* this is only true while dropping a snapshot */
913 if (level == lowest_level)
914 break;
915 blocknr = btrfs_node_blockptr(c, slot);
916 if (should_reada)
917 reada_for_search(root, p, level, slot);
918 b = read_tree_block(root, btrfs_node_blockptr(c, slot));
919
920 } else {
921 struct btrfs_leaf *l = (struct btrfs_leaf *)c;
922 p->slots[level] = slot;
923 if (ins_len > 0 && btrfs_leaf_free_space(root, l) <
924 sizeof(struct btrfs_item) + ins_len) {
925 int sret = split_leaf(trans, root, key,
926 p, ins_len);
927 BUG_ON(sret > 0);
928 if (sret)
929 return sret;
930 }
931 return ret;
932 }
933 }
934 return 1;
935 }
936
937 /*
938 * adjust the pointers going up the tree, starting at level
939 * making sure the right key of each node is points to 'key'.
940 * This is used after shifting pointers to the left, so it stops
941 * fixing up pointers when a given leaf/node is not in slot 0 of the
942 * higher levels
943 *
944 * If this fails to write a tree block, it returns -1, but continues
945 * fixing up the blocks in ram so the tree is consistent.
946 */
947 static int fixup_low_keys(struct btrfs_trans_handle *trans, struct btrfs_root
948 *root, struct btrfs_path *path, struct btrfs_disk_key
949 *key, int level)
950 {
951 int i;
952 int ret = 0;
953 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
954 struct btrfs_node *t;
955 int tslot = path->slots[i];
956 if (!path->nodes[i])
957 break;
958 t = btrfs_buffer_node(path->nodes[i]);
959 btrfs_memcpy(root, t, &t->ptrs[tslot].key, key, sizeof(*key));
960 btrfs_mark_buffer_dirty(path->nodes[i]);
961 if (tslot != 0)
962 break;
963 }
964 return ret;
965 }
966
967 /*
968 * try to push data from one node into the next node left in the
969 * tree.
970 *
971 * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
972 * error, and > 0 if there was no room in the left hand block.
973 */
974 static int push_node_left(struct btrfs_trans_handle *trans, struct btrfs_root
975 *root, struct buffer_head *dst_buf, struct
976 buffer_head *src_buf)
977 {
978 struct btrfs_node *src = btrfs_buffer_node(src_buf);
979 struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
980 int push_items = 0;
981 int src_nritems;
982 int dst_nritems;
983 int ret = 0;
984
985 src_nritems = btrfs_header_nritems(&src->header);
986 dst_nritems = btrfs_header_nritems(&dst->header);
987 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
988
989 if (push_items <= 0) {
990 return 1;
991 }
992
993 if (src_nritems < push_items)
994 push_items = src_nritems;
995
996 btrfs_memcpy(root, dst, dst->ptrs + dst_nritems, src->ptrs,
997 push_items * sizeof(struct btrfs_key_ptr));
998 if (push_items < src_nritems) {
999 btrfs_memmove(root, src, src->ptrs, src->ptrs + push_items,
1000 (src_nritems - push_items) *
1001 sizeof(struct btrfs_key_ptr));
1002 }
1003 btrfs_set_header_nritems(&src->header, src_nritems - push_items);
1004 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
1005 btrfs_mark_buffer_dirty(src_buf);
1006 btrfs_mark_buffer_dirty(dst_buf);
1007 return ret;
1008 }
1009
1010 /*
1011 * try to push data from one node into the next node right in the
1012 * tree.
1013 *
1014 * returns 0 if some ptrs were pushed, < 0 if there was some horrible
1015 * error, and > 0 if there was no room in the right hand block.
1016 *
1017 * this will only push up to 1/2 the contents of the left node over
1018 */
1019 static int balance_node_right(struct btrfs_trans_handle *trans, struct
1020 btrfs_root *root, struct buffer_head *dst_buf,
1021 struct buffer_head *src_buf)
1022 {
1023 struct btrfs_node *src = btrfs_buffer_node(src_buf);
1024 struct btrfs_node *dst = btrfs_buffer_node(dst_buf);
1025 int push_items = 0;
1026 int max_push;
1027 int src_nritems;
1028 int dst_nritems;
1029 int ret = 0;
1030
1031 src_nritems = btrfs_header_nritems(&src->header);
1032 dst_nritems = btrfs_header_nritems(&dst->header);
1033 push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
1034 if (push_items <= 0) {
1035 return 1;
1036 }
1037
1038 max_push = src_nritems / 2 + 1;
1039 /* don't try to empty the node */
1040 if (max_push > src_nritems)
1041 return 1;
1042 if (max_push < push_items)
1043 push_items = max_push;
1044
1045 btrfs_memmove(root, dst, dst->ptrs + push_items, dst->ptrs,
1046 dst_nritems * sizeof(struct btrfs_key_ptr));
1047
1048 btrfs_memcpy(root, dst, dst->ptrs,
1049 src->ptrs + src_nritems - push_items,
1050 push_items * sizeof(struct btrfs_key_ptr));
1051
1052 btrfs_set_header_nritems(&src->header, src_nritems - push_items);
1053 btrfs_set_header_nritems(&dst->header, dst_nritems + push_items);
1054
1055 btrfs_mark_buffer_dirty(src_buf);
1056 btrfs_mark_buffer_dirty(dst_buf);
1057 return ret;
1058 }
1059
1060 /*
1061 * helper function to insert a new root level in the tree.
1062 * A new node is allocated, and a single item is inserted to
1063 * point to the existing root
1064 *
1065 * returns zero on success or < 0 on failure.
1066 */
1067 static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root
1068 *root, struct btrfs_path *path, int level)
1069 {
1070 struct buffer_head *t;
1071 struct btrfs_node *lower;
1072 struct btrfs_node *c;
1073 struct btrfs_disk_key *lower_key;
1074
1075 BUG_ON(path->nodes[level]);
1076 BUG_ON(path->nodes[level-1] != root->node);
1077
1078 t = btrfs_alloc_free_block(trans, root, root->node->b_blocknr, 0);
1079 if (IS_ERR(t))
1080 return PTR_ERR(t);
1081 c = btrfs_buffer_node(t);
1082 memset(c, 0, root->blocksize);
1083 btrfs_set_header_nritems(&c->header, 1);
1084 btrfs_set_header_level(&c->header, level);
1085 btrfs_set_header_blocknr(&c->header, bh_blocknr(t));
1086 btrfs_set_header_generation(&c->header, trans->transid);
1087 btrfs_set_header_owner(&c->header, root->root_key.objectid);
1088 lower = btrfs_buffer_node(path->nodes[level-1]);
1089 memcpy(c->header.fsid, root->fs_info->disk_super->fsid,
1090 sizeof(c->header.fsid));
1091 if (btrfs_is_leaf(lower))
1092 lower_key = &((struct btrfs_leaf *)lower)->items[0].key;
1093 else
1094 lower_key = &lower->ptrs[0].key;
1095 btrfs_memcpy(root, c, &c->ptrs[0].key, lower_key,
1096 sizeof(struct btrfs_disk_key));
1097 btrfs_set_node_blockptr(c, 0, bh_blocknr(path->nodes[level - 1]));
1098
1099 btrfs_mark_buffer_dirty(t);
1100
1101 /* the super has an extra ref to root->node */
1102 btrfs_block_release(root, root->node);
1103 root->node = t;
1104 get_bh(t);
1105 path->nodes[level] = t;
1106 path->slots[level] = 0;
1107 return 0;
1108 }
1109
1110 /*
1111 * worker function to insert a single pointer in a node.
1112 * the node should have enough room for the pointer already
1113 *
1114 * slot and level indicate where you want the key to go, and
1115 * blocknr is the block the key points to.
1116 *
1117 * returns zero on success and < 0 on any error
1118 */
1119 static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1120 *root, struct btrfs_path *path, struct btrfs_disk_key
1121 *key, u64 blocknr, int slot, int level)
1122 {
1123 struct btrfs_node *lower;
1124 int nritems;
1125
1126 BUG_ON(!path->nodes[level]);
1127 lower = btrfs_buffer_node(path->nodes[level]);
1128 nritems = btrfs_header_nritems(&lower->header);
1129 if (slot > nritems)
1130 BUG();
1131 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1132 BUG();
1133 if (slot != nritems) {
1134 btrfs_memmove(root, lower, lower->ptrs + slot + 1,
1135 lower->ptrs + slot,
1136 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1137 }
1138 btrfs_memcpy(root, lower, &lower->ptrs[slot].key,
1139 key, sizeof(struct btrfs_disk_key));
1140 btrfs_set_node_blockptr(lower, slot, blocknr);
1141 btrfs_set_header_nritems(&lower->header, nritems + 1);
1142 btrfs_mark_buffer_dirty(path->nodes[level]);
1143 check_node(root, path, level);
1144 return 0;
1145 }
1146
1147 /*
1148 * split the node at the specified level in path in two.
1149 * The path is corrected to point to the appropriate node after the split
1150 *
1151 * Before splitting this tries to make some room in the node by pushing
1152 * left and right, if either one works, it returns right away.
1153 *
1154 * returns 0 on success and < 0 on failure
1155 */
1156 static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
1157 *root, struct btrfs_path *path, int level)
1158 {
1159 struct buffer_head *t;
1160 struct btrfs_node *c;
1161 struct buffer_head *split_buffer;
1162 struct btrfs_node *split;
1163 int mid;
1164 int ret;
1165 int wret;
1166 u32 c_nritems;
1167
1168 t = path->nodes[level];
1169 c = btrfs_buffer_node(t);
1170 if (t == root->node) {
1171 /* trying to split the root, lets make a new one */
1172 ret = insert_new_root(trans, root, path, level + 1);
1173 if (ret)
1174 return ret;
1175 } else {
1176 ret = push_nodes_for_insert(trans, root, path, level);
1177 t = path->nodes[level];
1178 c = btrfs_buffer_node(t);
1179 if (!ret &&
1180 btrfs_header_nritems(&c->header) <
1181 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1182 return 0;
1183 if (ret < 0)
1184 return ret;
1185 }
1186
1187 c_nritems = btrfs_header_nritems(&c->header);
1188 split_buffer = btrfs_alloc_free_block(trans, root, t->b_blocknr, 0);
1189 if (IS_ERR(split_buffer))
1190 return PTR_ERR(split_buffer);
1191
1192 split = btrfs_buffer_node(split_buffer);
1193 btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header));
1194 btrfs_set_header_level(&split->header, btrfs_header_level(&c->header));
1195 btrfs_set_header_blocknr(&split->header, bh_blocknr(split_buffer));
1196 btrfs_set_header_generation(&split->header, trans->transid);
1197 btrfs_set_header_owner(&split->header, root->root_key.objectid);
1198 memcpy(split->header.fsid, root->fs_info->disk_super->fsid,
1199 sizeof(split->header.fsid));
1200 mid = (c_nritems + 1) / 2;
1201 btrfs_memcpy(root, split, split->ptrs, c->ptrs + mid,
1202 (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
1203 btrfs_set_header_nritems(&split->header, c_nritems - mid);
1204 btrfs_set_header_nritems(&c->header, mid);
1205 ret = 0;
1206
1207 btrfs_mark_buffer_dirty(t);
1208 btrfs_mark_buffer_dirty(split_buffer);
1209 wret = insert_ptr(trans, root, path, &split->ptrs[0].key,
1210 bh_blocknr(split_buffer), path->slots[level + 1] + 1,
1211 level + 1);
1212 if (wret)
1213 ret = wret;
1214
1215 if (path->slots[level] >= mid) {
1216 path->slots[level] -= mid;
1217 btrfs_block_release(root, t);
1218 path->nodes[level] = split_buffer;
1219 path->slots[level + 1] += 1;
1220 } else {
1221 btrfs_block_release(root, split_buffer);
1222 }
1223 return ret;
1224 }
1225
1226 /*
1227 * how many bytes are required to store the items in a leaf. start
1228 * and nr indicate which items in the leaf to check. This totals up the
1229 * space used both by the item structs and the item data
1230 */
1231 static int leaf_space_used(struct btrfs_leaf *l, int start, int nr)
1232 {
1233 int data_len;
1234 int nritems = btrfs_header_nritems(&l->header);
1235 int end = min(nritems, start + nr) - 1;
1236
1237 if (!nr)
1238 return 0;
1239 data_len = btrfs_item_end(l->items + start);
1240 data_len = data_len - btrfs_item_offset(l->items + end);
1241 data_len += sizeof(struct btrfs_item) * nr;
1242 WARN_ON(data_len < 0);
1243 return data_len;
1244 }
1245
1246 /*
1247 * The space between the end of the leaf items and
1248 * the start of the leaf data. IOW, how much room
1249 * the leaf has left for both items and data
1250 */
1251 int btrfs_leaf_free_space(struct btrfs_root *root, struct btrfs_leaf *leaf)
1252 {
1253 int nritems = btrfs_header_nritems(&leaf->header);
1254 return BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
1255 }
1256
1257 /*
1258 * push some data in the path leaf to the right, trying to free up at
1259 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1260 *
1261 * returns 1 if the push failed because the other node didn't have enough
1262 * room, 0 if everything worked out and < 0 if there were major errors.
1263 */
1264 static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
1265 *root, struct btrfs_path *path, int data_size)
1266 {
1267 struct buffer_head *left_buf = path->nodes[0];
1268 struct btrfs_leaf *left = btrfs_buffer_leaf(left_buf);
1269 struct btrfs_leaf *right;
1270 struct buffer_head *right_buf;
1271 struct buffer_head *upper;
1272 struct btrfs_node *upper_node;
1273 int slot;
1274 int i;
1275 int free_space;
1276 int push_space = 0;
1277 int push_items = 0;
1278 struct btrfs_item *item;
1279 u32 left_nritems;
1280 u32 right_nritems;
1281 int ret;
1282
1283 slot = path->slots[1];
1284 if (!path->nodes[1]) {
1285 return 1;
1286 }
1287 upper = path->nodes[1];
1288 upper_node = btrfs_buffer_node(upper);
1289 if (slot >= btrfs_header_nritems(&upper_node->header) - 1) {
1290 return 1;
1291 }
1292 right_buf = read_tree_block(root,
1293 btrfs_node_blockptr(btrfs_buffer_node(upper), slot + 1));
1294 right = btrfs_buffer_leaf(right_buf);
1295 free_space = btrfs_leaf_free_space(root, right);
1296 if (free_space < data_size + sizeof(struct btrfs_item)) {
1297 btrfs_block_release(root, right_buf);
1298 return 1;
1299 }
1300 /* cow and double check */
1301 ret = btrfs_cow_block(trans, root, right_buf, upper,
1302 slot + 1, &right_buf);
1303 if (ret) {
1304 btrfs_block_release(root, right_buf);
1305 return 1;
1306 }
1307 right = btrfs_buffer_leaf(right_buf);
1308 free_space = btrfs_leaf_free_space(root, right);
1309 if (free_space < data_size + sizeof(struct btrfs_item)) {
1310 btrfs_block_release(root, right_buf);
1311 return 1;
1312 }
1313
1314 left_nritems = btrfs_header_nritems(&left->header);
1315 if (left_nritems == 0) {
1316 btrfs_block_release(root, right_buf);
1317 return 1;
1318 }
1319 for (i = left_nritems - 1; i >= 1; i--) {
1320 item = left->items + i;
1321 if (path->slots[0] == i)
1322 push_space += data_size + sizeof(*item);
1323 if (btrfs_item_size(item) + sizeof(*item) + push_space >
1324 free_space)
1325 break;
1326 push_items++;
1327 push_space += btrfs_item_size(item) + sizeof(*item);
1328 }
1329 if (push_items == 0) {
1330 btrfs_block_release(root, right_buf);
1331 return 1;
1332 }
1333 if (push_items == left_nritems)
1334 WARN_ON(1);
1335 right_nritems = btrfs_header_nritems(&right->header);
1336 /* push left to right */
1337 push_space = btrfs_item_end(left->items + left_nritems - push_items);
1338 push_space -= leaf_data_end(root, left);
1339 /* make room in the right data area */
1340 btrfs_memmove(root, right, btrfs_leaf_data(right) +
1341 leaf_data_end(root, right) - push_space,
1342 btrfs_leaf_data(right) +
1343 leaf_data_end(root, right), BTRFS_LEAF_DATA_SIZE(root) -
1344 leaf_data_end(root, right));
1345 /* copy from the left data area */
1346 btrfs_memcpy(root, right, btrfs_leaf_data(right) +
1347 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1348 btrfs_leaf_data(left) + leaf_data_end(root, left),
1349 push_space);
1350 btrfs_memmove(root, right, right->items + push_items, right->items,
1351 right_nritems * sizeof(struct btrfs_item));
1352 /* copy the items from left to right */
1353 btrfs_memcpy(root, right, right->items, left->items +
1354 left_nritems - push_items,
1355 push_items * sizeof(struct btrfs_item));
1356
1357 /* update the item pointers */
1358 right_nritems += push_items;
1359 btrfs_set_header_nritems(&right->header, right_nritems);
1360 push_space = BTRFS_LEAF_DATA_SIZE(root);
1361 for (i = 0; i < right_nritems; i++) {
1362 btrfs_set_item_offset(right->items + i, push_space -
1363 btrfs_item_size(right->items + i));
1364 push_space = btrfs_item_offset(right->items + i);
1365 }
1366 left_nritems -= push_items;
1367 btrfs_set_header_nritems(&left->header, left_nritems);
1368
1369 btrfs_mark_buffer_dirty(left_buf);
1370 btrfs_mark_buffer_dirty(right_buf);
1371
1372 btrfs_memcpy(root, upper_node, &upper_node->ptrs[slot + 1].key,
1373 &right->items[0].key, sizeof(struct btrfs_disk_key));
1374 btrfs_mark_buffer_dirty(upper);
1375
1376 /* then fixup the leaf pointer in the path */
1377 if (path->slots[0] >= left_nritems) {
1378 path->slots[0] -= left_nritems;
1379 btrfs_block_release(root, path->nodes[0]);
1380 path->nodes[0] = right_buf;
1381 path->slots[1] += 1;
1382 } else {
1383 btrfs_block_release(root, right_buf);
1384 }
1385 if (path->nodes[1])
1386 check_node(root, path, 1);
1387 return 0;
1388 }
1389 /*
1390 * push some data in the path leaf to the left, trying to free up at
1391 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1392 */
1393 static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1394 *root, struct btrfs_path *path, int data_size)
1395 {
1396 struct buffer_head *right_buf = path->nodes[0];
1397 struct btrfs_leaf *right = btrfs_buffer_leaf(right_buf);
1398 struct buffer_head *t;
1399 struct btrfs_leaf *left;
1400 int slot;
1401 int i;
1402 int free_space;
1403 int push_space = 0;
1404 int push_items = 0;
1405 struct btrfs_item *item;
1406 u32 old_left_nritems;
1407 int ret = 0;
1408 int wret;
1409
1410 slot = path->slots[1];
1411 if (slot == 0) {
1412 return 1;
1413 }
1414 if (!path->nodes[1]) {
1415 return 1;
1416 }
1417 t = read_tree_block(root,
1418 btrfs_node_blockptr(btrfs_buffer_node(path->nodes[1]), slot - 1));
1419 left = btrfs_buffer_leaf(t);
1420 free_space = btrfs_leaf_free_space(root, left);
1421 if (free_space < data_size + sizeof(struct btrfs_item)) {
1422 btrfs_block_release(root, t);
1423 return 1;
1424 }
1425
1426 /* cow and double check */
1427 ret = btrfs_cow_block(trans, root, t, path->nodes[1], slot - 1, &t);
1428 if (ret) {
1429 /* we hit -ENOSPC, but it isn't fatal here */
1430 return 1;
1431 }
1432 left = btrfs_buffer_leaf(t);
1433 free_space = btrfs_leaf_free_space(root, left);
1434 if (free_space < data_size + sizeof(struct btrfs_item)) {
1435 btrfs_block_release(root, t);
1436 return 1;
1437 }
1438
1439 if (btrfs_header_nritems(&right->header) == 0) {
1440 btrfs_block_release(root, t);
1441 return 1;
1442 }
1443
1444 for (i = 0; i < btrfs_header_nritems(&right->header) - 1; i++) {
1445 item = right->items + i;
1446 if (path->slots[0] == i)
1447 push_space += data_size + sizeof(*item);
1448 if (btrfs_item_size(item) + sizeof(*item) + push_space >
1449 free_space)
1450 break;
1451 push_items++;
1452 push_space += btrfs_item_size(item) + sizeof(*item);
1453 }
1454 if (push_items == 0) {
1455 btrfs_block_release(root, t);
1456 return 1;
1457 }
1458 if (push_items == btrfs_header_nritems(&right->header))
1459 WARN_ON(1);
1460 /* push data from right to left */
1461 btrfs_memcpy(root, left, left->items +
1462 btrfs_header_nritems(&left->header),
1463 right->items, push_items * sizeof(struct btrfs_item));
1464 push_space = BTRFS_LEAF_DATA_SIZE(root) -
1465 btrfs_item_offset(right->items + push_items -1);
1466 btrfs_memcpy(root, left, btrfs_leaf_data(left) +
1467 leaf_data_end(root, left) - push_space,
1468 btrfs_leaf_data(right) +
1469 btrfs_item_offset(right->items + push_items - 1),
1470 push_space);
1471 old_left_nritems = btrfs_header_nritems(&left->header);
1472 BUG_ON(old_left_nritems < 0);
1473
1474 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1475 u32 ioff = btrfs_item_offset(left->items + i);
1476 btrfs_set_item_offset(left->items + i, ioff -
1477 (BTRFS_LEAF_DATA_SIZE(root) -
1478 btrfs_item_offset(left->items +
1479 old_left_nritems - 1)));
1480 }
1481 btrfs_set_header_nritems(&left->header, old_left_nritems + push_items);
1482
1483 /* fixup right node */
1484 push_space = btrfs_item_offset(right->items + push_items - 1) -
1485 leaf_data_end(root, right);
1486 btrfs_memmove(root, right, btrfs_leaf_data(right) +
1487 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1488 btrfs_leaf_data(right) +
1489 leaf_data_end(root, right), push_space);
1490 btrfs_memmove(root, right, right->items, right->items + push_items,
1491 (btrfs_header_nritems(&right->header) - push_items) *
1492 sizeof(struct btrfs_item));
1493 btrfs_set_header_nritems(&right->header,
1494 btrfs_header_nritems(&right->header) -
1495 push_items);
1496 push_space = BTRFS_LEAF_DATA_SIZE(root);
1497
1498 for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1499 btrfs_set_item_offset(right->items + i, push_space -
1500 btrfs_item_size(right->items + i));
1501 push_space = btrfs_item_offset(right->items + i);
1502 }
1503
1504 btrfs_mark_buffer_dirty(t);
1505 btrfs_mark_buffer_dirty(right_buf);
1506
1507 wret = fixup_low_keys(trans, root, path, &right->items[0].key, 1);
1508 if (wret)
1509 ret = wret;
1510
1511 /* then fixup the leaf pointer in the path */
1512 if (path->slots[0] < push_items) {
1513 path->slots[0] += old_left_nritems;
1514 btrfs_block_release(root, path->nodes[0]);
1515 path->nodes[0] = t;
1516 path->slots[1] -= 1;
1517 } else {
1518 btrfs_block_release(root, t);
1519 path->slots[0] -= push_items;
1520 }
1521 BUG_ON(path->slots[0] < 0);
1522 if (path->nodes[1])
1523 check_node(root, path, 1);
1524 return ret;
1525 }
1526
1527 /*
1528 * split the path's leaf in two, making sure there is at least data_size
1529 * available for the resulting leaf level of the path.
1530 *
1531 * returns 0 if all went well and < 0 on failure.
1532 */
1533 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
1534 *root, struct btrfs_key *ins_key,
1535 struct btrfs_path *path, int data_size)
1536 {
1537 struct buffer_head *l_buf;
1538 struct btrfs_leaf *l;
1539 u32 nritems;
1540 int mid;
1541 int slot;
1542 struct btrfs_leaf *right;
1543 struct buffer_head *right_buffer;
1544 int space_needed = data_size + sizeof(struct btrfs_item);
1545 int data_copy_size;
1546 int rt_data_off;
1547 int i;
1548 int ret = 0;
1549 int wret;
1550 int double_split = 0;
1551 struct btrfs_disk_key disk_key;
1552
1553 /* first try to make some room by pushing left and right */
1554 wret = push_leaf_left(trans, root, path, data_size);
1555 if (wret < 0)
1556 return wret;
1557 if (wret) {
1558 wret = push_leaf_right(trans, root, path, data_size);
1559 if (wret < 0)
1560 return wret;
1561 }
1562 l_buf = path->nodes[0];
1563 l = btrfs_buffer_leaf(l_buf);
1564
1565 /* did the pushes work? */
1566 if (btrfs_leaf_free_space(root, l) >=
1567 sizeof(struct btrfs_item) + data_size)
1568 return 0;
1569
1570 if (!path->nodes[1]) {
1571 ret = insert_new_root(trans, root, path, 1);
1572 if (ret)
1573 return ret;
1574 }
1575 slot = path->slots[0];
1576 nritems = btrfs_header_nritems(&l->header);
1577 mid = (nritems + 1)/ 2;
1578
1579 right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0);
1580 if (IS_ERR(right_buffer))
1581 return PTR_ERR(right_buffer);
1582
1583 right = btrfs_buffer_leaf(right_buffer);
1584 memset(&right->header, 0, sizeof(right->header));
1585 btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer));
1586 btrfs_set_header_generation(&right->header, trans->transid);
1587 btrfs_set_header_owner(&right->header, root->root_key.objectid);
1588 btrfs_set_header_level(&right->header, 0);
1589 memcpy(right->header.fsid, root->fs_info->disk_super->fsid,
1590 sizeof(right->header.fsid));
1591 if (mid <= slot) {
1592 if (nritems == 1 ||
1593 leaf_space_used(l, mid, nritems - mid) + space_needed >
1594 BTRFS_LEAF_DATA_SIZE(root)) {
1595 if (slot >= nritems) {
1596 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1597 btrfs_set_header_nritems(&right->header, 0);
1598 wret = insert_ptr(trans, root, path,
1599 &disk_key,
1600 bh_blocknr(right_buffer),
1601 path->slots[1] + 1, 1);
1602 if (wret)
1603 ret = wret;
1604 btrfs_block_release(root, path->nodes[0]);
1605 path->nodes[0] = right_buffer;
1606 path->slots[0] = 0;
1607 path->slots[1] += 1;
1608 return ret;
1609 }
1610 mid = slot;
1611 double_split = 1;
1612 }
1613 } else {
1614 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1615 BTRFS_LEAF_DATA_SIZE(root)) {
1616 if (slot == 0) {
1617 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1618 btrfs_set_header_nritems(&right->header, 0);
1619 wret = insert_ptr(trans, root, path,
1620 &disk_key,
1621 bh_blocknr(right_buffer),
1622 path->slots[1], 1);
1623 if (wret)
1624 ret = wret;
1625 btrfs_block_release(root, path->nodes[0]);
1626 path->nodes[0] = right_buffer;
1627 path->slots[0] = 0;
1628 if (path->slots[1] == 0) {
1629 wret = fixup_low_keys(trans, root,
1630 path, &disk_key, 1);
1631 if (wret)
1632 ret = wret;
1633 }
1634 return ret;
1635 }
1636 mid = slot;
1637 double_split = 1;
1638 }
1639 }
1640 btrfs_set_header_nritems(&right->header, nritems - mid);
1641 data_copy_size = btrfs_item_end(l->items + mid) -
1642 leaf_data_end(root, l);
1643 btrfs_memcpy(root, right, right->items, l->items + mid,
1644 (nritems - mid) * sizeof(struct btrfs_item));
1645 btrfs_memcpy(root, right,
1646 btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
1647 data_copy_size, btrfs_leaf_data(l) +
1648 leaf_data_end(root, l), data_copy_size);
1649 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1650 btrfs_item_end(l->items + mid);
1651
1652 for (i = 0; i < btrfs_header_nritems(&right->header); i++) {
1653 u32 ioff = btrfs_item_offset(right->items + i);
1654 btrfs_set_item_offset(right->items + i, ioff + rt_data_off);
1655 }
1656
1657 btrfs_set_header_nritems(&l->header, mid);
1658 ret = 0;
1659 wret = insert_ptr(trans, root, path, &right->items[0].key,
1660 bh_blocknr(right_buffer), path->slots[1] + 1, 1);
1661 if (wret)
1662 ret = wret;
1663 btrfs_mark_buffer_dirty(right_buffer);
1664 btrfs_mark_buffer_dirty(l_buf);
1665 BUG_ON(path->slots[0] != slot);
1666 if (mid <= slot) {
1667 btrfs_block_release(root, path->nodes[0]);
1668 path->nodes[0] = right_buffer;
1669 path->slots[0] -= mid;
1670 path->slots[1] += 1;
1671 } else
1672 btrfs_block_release(root, right_buffer);
1673 BUG_ON(path->slots[0] < 0);
1674 check_node(root, path, 1);
1675
1676 if (!double_split)
1677 return ret;
1678 right_buffer = btrfs_alloc_free_block(trans, root, l_buf->b_blocknr, 0);
1679 if (IS_ERR(right_buffer))
1680 return PTR_ERR(right_buffer);
1681
1682 right = btrfs_buffer_leaf(right_buffer);
1683 memset(&right->header, 0, sizeof(right->header));
1684 btrfs_set_header_blocknr(&right->header, bh_blocknr(right_buffer));
1685 btrfs_set_header_generation(&right->header, trans->transid);
1686 btrfs_set_header_owner(&right->header, root->root_key.objectid);
1687 btrfs_set_header_level(&right->header, 0);
1688 memcpy(right->header.fsid, root->fs_info->disk_super->fsid,
1689 sizeof(right->header.fsid));
1690 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1691 btrfs_set_header_nritems(&right->header, 0);
1692 wret = insert_ptr(trans, root, path,
1693 &disk_key,
1694 bh_blocknr(right_buffer),
1695 path->slots[1], 1);
1696 if (wret)
1697 ret = wret;
1698 if (path->slots[1] == 0) {
1699 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1700 if (wret)
1701 ret = wret;
1702 }
1703 btrfs_block_release(root, path->nodes[0]);
1704 path->nodes[0] = right_buffer;
1705 path->slots[0] = 0;
1706 check_node(root, path, 1);
1707 check_leaf(root, path, 0);
1708 return ret;
1709 }
1710
1711 int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1712 struct btrfs_root *root,
1713 struct btrfs_path *path,
1714 u32 new_size)
1715 {
1716 int ret = 0;
1717 int slot;
1718 int slot_orig;
1719 struct btrfs_leaf *leaf;
1720 struct buffer_head *leaf_buf;
1721 u32 nritems;
1722 unsigned int data_end;
1723 unsigned int old_data_start;
1724 unsigned int old_size;
1725 unsigned int size_diff;
1726 int i;
1727
1728 slot_orig = path->slots[0];
1729 leaf_buf = path->nodes[0];
1730 leaf = btrfs_buffer_leaf(leaf_buf);
1731
1732 nritems = btrfs_header_nritems(&leaf->header);
1733 data_end = leaf_data_end(root, leaf);
1734
1735 slot = path->slots[0];
1736 old_data_start = btrfs_item_offset(leaf->items + slot);
1737 old_size = btrfs_item_size(leaf->items + slot);
1738 BUG_ON(old_size <= new_size);
1739 size_diff = old_size - new_size;
1740
1741 BUG_ON(slot < 0);
1742 BUG_ON(slot >= nritems);
1743
1744 /*
1745 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1746 */
1747 /* first correct the data pointers */
1748 for (i = slot; i < nritems; i++) {
1749 u32 ioff = btrfs_item_offset(leaf->items + i);
1750 btrfs_set_item_offset(leaf->items + i,
1751 ioff + size_diff);
1752 }
1753 /* shift the data */
1754 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
1755 data_end + size_diff, btrfs_leaf_data(leaf) +
1756 data_end, old_data_start + new_size - data_end);
1757 btrfs_set_item_size(leaf->items + slot, new_size);
1758 btrfs_mark_buffer_dirty(leaf_buf);
1759
1760 ret = 0;
1761 if (btrfs_leaf_free_space(root, leaf) < 0)
1762 BUG();
1763 check_leaf(root, path, 0);
1764 return ret;
1765 }
1766
1767 int btrfs_extend_item(struct btrfs_trans_handle *trans, struct btrfs_root
1768 *root, struct btrfs_path *path, u32 data_size)
1769 {
1770 int ret = 0;
1771 int slot;
1772 int slot_orig;
1773 struct btrfs_leaf *leaf;
1774 struct buffer_head *leaf_buf;
1775 u32 nritems;
1776 unsigned int data_end;
1777 unsigned int old_data;
1778 unsigned int old_size;
1779 int i;
1780
1781 slot_orig = path->slots[0];
1782 leaf_buf = path->nodes[0];
1783 leaf = btrfs_buffer_leaf(leaf_buf);
1784
1785 nritems = btrfs_header_nritems(&leaf->header);
1786 data_end = leaf_data_end(root, leaf);
1787
1788 if (btrfs_leaf_free_space(root, leaf) < data_size)
1789 BUG();
1790 slot = path->slots[0];
1791 old_data = btrfs_item_end(leaf->items + slot);
1792
1793 BUG_ON(slot < 0);
1794 BUG_ON(slot >= nritems);
1795
1796 /*
1797 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1798 */
1799 /* first correct the data pointers */
1800 for (i = slot; i < nritems; i++) {
1801 u32 ioff = btrfs_item_offset(leaf->items + i);
1802 btrfs_set_item_offset(leaf->items + i,
1803 ioff - data_size);
1804 }
1805 /* shift the data */
1806 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
1807 data_end - data_size, btrfs_leaf_data(leaf) +
1808 data_end, old_data - data_end);
1809 data_end = old_data;
1810 old_size = btrfs_item_size(leaf->items + slot);
1811 btrfs_set_item_size(leaf->items + slot, old_size + data_size);
1812 btrfs_mark_buffer_dirty(leaf_buf);
1813
1814 ret = 0;
1815 if (btrfs_leaf_free_space(root, leaf) < 0)
1816 BUG();
1817 check_leaf(root, path, 0);
1818 return ret;
1819 }
1820
1821 /*
1822 * Given a key and some data, insert an item into the tree.
1823 * This does all the path init required, making room in the tree if needed.
1824 */
1825 int btrfs_insert_empty_item(struct btrfs_trans_handle *trans, struct btrfs_root
1826 *root, struct btrfs_path *path, struct btrfs_key
1827 *cpu_key, u32 data_size)
1828 {
1829 int ret = 0;
1830 int slot;
1831 int slot_orig;
1832 struct btrfs_leaf *leaf;
1833 struct buffer_head *leaf_buf;
1834 u32 nritems;
1835 unsigned int data_end;
1836 struct btrfs_disk_key disk_key;
1837
1838 btrfs_cpu_key_to_disk(&disk_key, cpu_key);
1839
1840 /* create a root if there isn't one */
1841 if (!root->node)
1842 BUG();
1843 ret = btrfs_search_slot(trans, root, cpu_key, path, data_size, 1);
1844 if (ret == 0) {
1845 return -EEXIST;
1846 }
1847 if (ret < 0)
1848 goto out;
1849
1850 slot_orig = path->slots[0];
1851 leaf_buf = path->nodes[0];
1852 leaf = btrfs_buffer_leaf(leaf_buf);
1853
1854 nritems = btrfs_header_nritems(&leaf->header);
1855 data_end = leaf_data_end(root, leaf);
1856
1857 if (btrfs_leaf_free_space(root, leaf) <
1858 sizeof(struct btrfs_item) + data_size) {
1859 BUG();
1860 }
1861 slot = path->slots[0];
1862 BUG_ON(slot < 0);
1863 if (slot != nritems) {
1864 int i;
1865 unsigned int old_data = btrfs_item_end(leaf->items + slot);
1866
1867 /*
1868 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1869 */
1870 /* first correct the data pointers */
1871 for (i = slot; i < nritems; i++) {
1872 u32 ioff = btrfs_item_offset(leaf->items + i);
1873 btrfs_set_item_offset(leaf->items + i,
1874 ioff - data_size);
1875 }
1876
1877 /* shift the items */
1878 btrfs_memmove(root, leaf, leaf->items + slot + 1,
1879 leaf->items + slot,
1880 (nritems - slot) * sizeof(struct btrfs_item));
1881
1882 /* shift the data */
1883 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
1884 data_end - data_size, btrfs_leaf_data(leaf) +
1885 data_end, old_data - data_end);
1886 data_end = old_data;
1887 }
1888 /* setup the item for the new data */
1889 btrfs_memcpy(root, leaf, &leaf->items[slot].key, &disk_key,
1890 sizeof(struct btrfs_disk_key));
1891 btrfs_set_item_offset(leaf->items + slot, data_end - data_size);
1892 btrfs_set_item_size(leaf->items + slot, data_size);
1893 btrfs_set_header_nritems(&leaf->header, nritems + 1);
1894 btrfs_mark_buffer_dirty(leaf_buf);
1895
1896 ret = 0;
1897 if (slot == 0)
1898 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
1899
1900 if (btrfs_leaf_free_space(root, leaf) < 0)
1901 BUG();
1902 check_leaf(root, path, 0);
1903 out:
1904 return ret;
1905 }
1906
1907 /*
1908 * Given a key and some data, insert an item into the tree.
1909 * This does all the path init required, making room in the tree if needed.
1910 */
1911 int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
1912 *root, struct btrfs_key *cpu_key, void *data, u32
1913 data_size)
1914 {
1915 int ret = 0;
1916 struct btrfs_path *path;
1917 u8 *ptr;
1918
1919 path = btrfs_alloc_path();
1920 BUG_ON(!path);
1921 ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
1922 if (!ret) {
1923 ptr = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]),
1924 path->slots[0], u8);
1925 btrfs_memcpy(root, path->nodes[0]->b_data,
1926 ptr, data, data_size);
1927 btrfs_mark_buffer_dirty(path->nodes[0]);
1928 }
1929 btrfs_free_path(path);
1930 return ret;
1931 }
1932
1933 /*
1934 * delete the pointer from a given node.
1935 *
1936 * If the delete empties a node, the node is removed from the tree,
1937 * continuing all the way the root if required. The root is converted into
1938 * a leaf if all the nodes are emptied.
1939 */
1940 static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1941 struct btrfs_path *path, int level, int slot)
1942 {
1943 struct btrfs_node *node;
1944 struct buffer_head *parent = path->nodes[level];
1945 u32 nritems;
1946 int ret = 0;
1947 int wret;
1948
1949 node = btrfs_buffer_node(parent);
1950 nritems = btrfs_header_nritems(&node->header);
1951 if (slot != nritems -1) {
1952 btrfs_memmove(root, node, node->ptrs + slot,
1953 node->ptrs + slot + 1,
1954 sizeof(struct btrfs_key_ptr) *
1955 (nritems - slot - 1));
1956 }
1957 nritems--;
1958 btrfs_set_header_nritems(&node->header, nritems);
1959 if (nritems == 0 && parent == root->node) {
1960 struct btrfs_header *header = btrfs_buffer_header(root->node);
1961 BUG_ON(btrfs_header_level(header) != 1);
1962 /* just turn the root into a leaf and break */
1963 btrfs_set_header_level(header, 0);
1964 } else if (slot == 0) {
1965 wret = fixup_low_keys(trans, root, path, &node->ptrs[0].key,
1966 level + 1);
1967 if (wret)
1968 ret = wret;
1969 }
1970 btrfs_mark_buffer_dirty(parent);
1971 return ret;
1972 }
1973
1974 /*
1975 * delete the item at the leaf level in path. If that empties
1976 * the leaf, remove it from the tree
1977 */
1978 int btrfs_del_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1979 struct btrfs_path *path)
1980 {
1981 int slot;
1982 struct btrfs_leaf *leaf;
1983 struct buffer_head *leaf_buf;
1984 int doff;
1985 int dsize;
1986 int ret = 0;
1987 int wret;
1988 u32 nritems;
1989
1990 leaf_buf = path->nodes[0];
1991 leaf = btrfs_buffer_leaf(leaf_buf);
1992 slot = path->slots[0];
1993 doff = btrfs_item_offset(leaf->items + slot);
1994 dsize = btrfs_item_size(leaf->items + slot);
1995 nritems = btrfs_header_nritems(&leaf->header);
1996
1997 if (slot != nritems - 1) {
1998 int i;
1999 int data_end = leaf_data_end(root, leaf);
2000 btrfs_memmove(root, leaf, btrfs_leaf_data(leaf) +
2001 data_end + dsize,
2002 btrfs_leaf_data(leaf) + data_end,
2003 doff - data_end);
2004 for (i = slot + 1; i < nritems; i++) {
2005 u32 ioff = btrfs_item_offset(leaf->items + i);
2006 btrfs_set_item_offset(leaf->items + i, ioff + dsize);
2007 }
2008 btrfs_memmove(root, leaf, leaf->items + slot,
2009 leaf->items + slot + 1,
2010 sizeof(struct btrfs_item) *
2011 (nritems - slot - 1));
2012 }
2013 btrfs_set_header_nritems(&leaf->header, nritems - 1);
2014 nritems--;
2015 /* delete the leaf if we've emptied it */
2016 if (nritems == 0) {
2017 if (leaf_buf == root->node) {
2018 btrfs_set_header_level(&leaf->header, 0);
2019 } else {
2020 clean_tree_block(trans, root, leaf_buf);
2021 wait_on_buffer(leaf_buf);
2022 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2023 if (wret)
2024 ret = wret;
2025 wret = btrfs_free_extent(trans, root,
2026 bh_blocknr(leaf_buf), 1, 1);
2027 if (wret)
2028 ret = wret;
2029 }
2030 } else {
2031 int used = leaf_space_used(leaf, 0, nritems);
2032 if (slot == 0) {
2033 wret = fixup_low_keys(trans, root, path,
2034 &leaf->items[0].key, 1);
2035 if (wret)
2036 ret = wret;
2037 }
2038
2039 /* delete the leaf if it is mostly empty */
2040 if (used < BTRFS_LEAF_DATA_SIZE(root) / 3) {
2041 /* push_leaf_left fixes the path.
2042 * make sure the path still points to our leaf
2043 * for possible call to del_ptr below
2044 */
2045 slot = path->slots[1];
2046 get_bh(leaf_buf);
2047 wret = push_leaf_left(trans, root, path, 1);
2048 if (wret < 0 && wret != -ENOSPC)
2049 ret = wret;
2050 if (path->nodes[0] == leaf_buf &&
2051 btrfs_header_nritems(&leaf->header)) {
2052 wret = push_leaf_right(trans, root, path, 1);
2053 if (wret < 0 && wret != -ENOSPC)
2054 ret = wret;
2055 }
2056 if (btrfs_header_nritems(&leaf->header) == 0) {
2057 u64 blocknr = bh_blocknr(leaf_buf);
2058 clean_tree_block(trans, root, leaf_buf);
2059 wait_on_buffer(leaf_buf);
2060 wret = del_ptr(trans, root, path, 1, slot);
2061 if (wret)
2062 ret = wret;
2063 btrfs_block_release(root, leaf_buf);
2064 wret = btrfs_free_extent(trans, root, blocknr,
2065 1, 1);
2066 if (wret)
2067 ret = wret;
2068 } else {
2069 btrfs_mark_buffer_dirty(leaf_buf);
2070 btrfs_block_release(root, leaf_buf);
2071 }
2072 } else {
2073 btrfs_mark_buffer_dirty(leaf_buf);
2074 }
2075 }
2076 return ret;
2077 }
2078
2079 /*
2080 * walk up the tree as far as required to find the next leaf.
2081 * returns 0 if it found something or 1 if there are no greater leaves.
2082 * returns < 0 on io errors.
2083 */
2084 int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2085 {
2086 int slot;
2087 int level = 1;
2088 u64 blocknr;
2089 struct buffer_head *c;
2090 struct btrfs_node *c_node;
2091 struct buffer_head *next = NULL;
2092
2093 while(level < BTRFS_MAX_LEVEL) {
2094 if (!path->nodes[level])
2095 return 1;
2096 slot = path->slots[level] + 1;
2097 c = path->nodes[level];
2098 c_node = btrfs_buffer_node(c);
2099 if (slot >= btrfs_header_nritems(&c_node->header)) {
2100 level++;
2101 continue;
2102 }
2103 blocknr = btrfs_node_blockptr(c_node, slot);
2104 if (next)
2105 btrfs_block_release(root, next);
2106 if (path->reada)
2107 reada_for_search(root, path, level, slot);
2108 next = read_tree_block(root, blocknr);
2109 break;
2110 }
2111 path->slots[level] = slot;
2112 while(1) {
2113 level--;
2114 c = path->nodes[level];
2115 btrfs_block_release(root, c);
2116 path->nodes[level] = next;
2117 path->slots[level] = 0;
2118 if (!level)
2119 break;
2120 if (path->reada)
2121 reada_for_search(root, path, level, slot);
2122 next = read_tree_block(root,
2123 btrfs_node_blockptr(btrfs_buffer_node(next), 0));
2124 }
2125 return 0;
2126 }
Linux kernel - Deliverables
This page took 0.07578 seconds and 6 git commands to generate.