aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/ctree.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/ctree.c')
-rw-r--r--fs/btrfs/ctree.c119
1 files changed, 119 insertions, 0 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 4efcd1bd63e5..744fd728e5d9 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -151,6 +151,11 @@ static int check_node(struct btrfs_root *root, struct btrfs_path *path,
151 for (i = 0; nritems > 1 && i < nritems - 2; i++) { 151 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
152 struct btrfs_key cpukey; 152 struct btrfs_key cpukey;
153 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key); 153 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
154if (comp_keys(&node->ptrs[i].key, &cpukey) >= 0) {
155 struct btrfs_key bad;
156 btrfs_disk_key_to_cpu(&bad, &node->ptrs[i].key);
157printk("check_node level %d i is %d bad comp %Lu %u %Lu, %Lu %u %Lu\n",level, i, bad.objectid, bad.flags, bad.offset, cpukey.objectid, cpukey.flags, cpukey.offset);
158}
154 BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0); 159 BUG_ON(comp_keys(&node->ptrs[i].key, &cpukey) >= 0);
155 } 160 }
156 return 0; 161 return 0;
@@ -448,6 +453,111 @@ static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
448 return ret; 453 return ret;
449} 454}
450 455
456/* returns zero if the push worked, non-zero otherwise */
457static int push_nodes_for_insert(struct btrfs_trans_handle *trans,
458 struct btrfs_root *root,
459 struct btrfs_path *path, int level)
460{
461 struct buffer_head *right_buf;
462 struct buffer_head *mid_buf;
463 struct buffer_head *left_buf;
464 struct buffer_head *parent_buf = NULL;
465 struct btrfs_node *right = NULL;
466 struct btrfs_node *mid;
467 struct btrfs_node *left = NULL;
468 struct btrfs_node *parent = NULL;
469 int ret = 0;
470 int wret;
471 int pslot;
472 int orig_slot = path->slots[level];
473 u64 orig_ptr;
474
475 if (level == 0)
476 return 1;
477
478 mid_buf = path->nodes[level];
479 mid = btrfs_buffer_node(mid_buf);
480 orig_ptr = btrfs_node_blockptr(mid, orig_slot);
481
482 if (level < BTRFS_MAX_LEVEL - 1)
483 parent_buf = path->nodes[level + 1];
484 pslot = path->slots[level + 1];
485
486 if (!parent_buf)
487 return 1;
488 parent = btrfs_buffer_node(parent_buf);
489
490 left_buf = read_node_slot(root, parent_buf, pslot - 1);
491
492 /* first, try to make some room in the middle buffer */
493 if (left_buf) {
494 u32 left_nr;
495 btrfs_cow_block(trans, root, left_buf, parent_buf, pslot - 1,
496 &left_buf);
497 left = btrfs_buffer_node(left_buf);
498 left_nr = btrfs_header_nritems(&left->header);
499 wret = push_node_left(trans, root, left_buf, mid_buf);
500 if (wret < 0)
501 ret = wret;
502 if (wret == 0) {
503 orig_slot += left_nr;
504 btrfs_memcpy(root, parent,
505 &parent->ptrs[pslot].key,
506 &mid->ptrs[0].key,
507 sizeof(struct btrfs_disk_key));
508 btrfs_mark_buffer_dirty(parent_buf);
509 if (btrfs_header_nritems(&left->header) > orig_slot) {
510 path->nodes[level] = left_buf;
511 path->slots[level + 1] -= 1;
512 path->slots[level] = orig_slot;
513 btrfs_block_release(root, mid_buf);
514 } else {
515 orig_slot -=
516 btrfs_header_nritems(&left->header);
517 path->slots[level] = orig_slot;
518 btrfs_block_release(root, left_buf);
519 }
520 check_node(root, path, level);
521 return 0;
522 }
523 btrfs_block_release(root, left_buf);
524 }
525 right_buf = read_node_slot(root, parent_buf, pslot + 1);
526
527 /*
528 * then try to empty the right most buffer into the middle
529 */
530 if (right_buf) {
531 btrfs_cow_block(trans, root, right_buf, parent_buf, pslot + 1,
532 &right_buf);
533 right = btrfs_buffer_node(right_buf);
534 wret = balance_node_right(trans, root, right_buf, mid_buf);
535 if (wret < 0)
536 ret = wret;
537 if (wret == 0) {
538 btrfs_memcpy(root, parent,
539 &parent->ptrs[pslot + 1].key,
540 &right->ptrs[0].key,
541 sizeof(struct btrfs_disk_key));
542 btrfs_mark_buffer_dirty(parent_buf);
543 if (btrfs_header_nritems(&mid->header) <= orig_slot) {
544 path->nodes[level] = right_buf;
545 path->slots[level + 1] += 1;
546 path->slots[level] = orig_slot -
547 btrfs_header_nritems(&mid->header);
548 btrfs_block_release(root, mid_buf);
549 } else {
550 btrfs_block_release(root, right_buf);
551 }
552 check_node(root, path, level);
553 return 0;
554 }
555 btrfs_block_release(root, right_buf);
556 }
557 check_node(root, path, level);
558 return 1;
559}
560
451/* 561/*
452 * look for key in the tree. path is filled in with nodes along the way 562 * look for key in the tree. path is filled in with nodes along the way
453 * if key is found, we return zero and you can find the item in the leaf 563 * if key is found, we return zero and you can find the item in the leaf
@@ -774,7 +884,16 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
774 ret = insert_new_root(trans, root, path, level + 1); 884 ret = insert_new_root(trans, root, path, level + 1);
775 if (ret) 885 if (ret)
776 return ret; 886 return ret;
887 } else {
888 ret = push_nodes_for_insert(trans, root, path, level);
889 t = path->nodes[level];
890 c = btrfs_buffer_node(t);
891 if (!ret &&
892 btrfs_header_nritems(&c->header) <
893 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
894 return 0;
777 } 895 }
896
778 c_nritems = btrfs_header_nritems(&c->header); 897 c_nritems = btrfs_header_nritems(&c->header);
779 split_buffer = btrfs_alloc_free_block(trans, root); 898 split_buffer = btrfs_alloc_free_block(trans, root);
780 split = btrfs_buffer_node(split_buffer); 899 split = btrfs_buffer_node(split_buffer);