ctree.c (f510cfecfc98759d75283823cfccf0cc0d59a4c6) ctree.c (db94535db75e67fab12ccbb7f5ee548e33fed891)
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,

--- 69 unchanged lines hidden (view full) ---

78 u64 search_start, u64 empty_size)
79{
80 struct extent_buffer *cow;
81 int ret = 0;
82 int different_trans = 0;
83
84 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
85
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,

--- 69 unchanged lines hidden (view full) ---

78 u64 search_start, u64 empty_size)
79{
80 struct extent_buffer *cow;
81 int ret = 0;
82 int different_trans = 0;
83
84 WARN_ON(root->ref_cows && trans->transid != root->last_trans);
85
86 cow = btrfs_alloc_free_block(trans, root, search_start, empty_size);
86 cow = btrfs_alloc_free_block(trans, root, buf->len,
87 search_start, empty_size);
87 if (IS_ERR(cow))
88 return PTR_ERR(cow);
89
90 cow->alloc_addr = (unsigned long)__builtin_return_address(0);
88 if (IS_ERR(cow))
89 return PTR_ERR(cow);
90
91 cow->alloc_addr = (unsigned long)__builtin_return_address(0);
91 if (buf->len != root->sectorsize || cow->len != root->sectorsize)
92 WARN_ON(1);
93
94 copy_extent_buffer(cow, buf, 0, 0, cow->len);
92
93 copy_extent_buffer(cow, buf, 0, 0, cow->len);
95 btrfs_set_header_blocknr(cow, extent_buffer_blocknr(cow));
94 btrfs_set_header_bytenr(cow, cow->start);
96 btrfs_set_header_generation(cow, trans->transid);
97 btrfs_set_header_owner(cow, root->root_key.objectid);
98
99 WARN_ON(btrfs_header_generation(buf) > trans->transid);
100 if (btrfs_header_generation(buf) != trans->transid) {
101 different_trans = 1;
102 ret = btrfs_inc_ref(trans, root, buf);
103 if (ret)
104 return ret;
105 } else {
106 clean_tree_block(trans, root, buf);
107 }
108
109 if (buf == root->node) {
110 root->node = cow;
111 extent_buffer_get(cow);
112 if (buf != root->commit_root) {
95 btrfs_set_header_generation(cow, trans->transid);
96 btrfs_set_header_owner(cow, root->root_key.objectid);
97
98 WARN_ON(btrfs_header_generation(buf) > trans->transid);
99 if (btrfs_header_generation(buf) != trans->transid) {
100 different_trans = 1;
101 ret = btrfs_inc_ref(trans, root, buf);
102 if (ret)
103 return ret;
104 } else {
105 clean_tree_block(trans, root, buf);
106 }
107
108 if (buf == root->node) {
109 root->node = cow;
110 extent_buffer_get(cow);
111 if (buf != root->commit_root) {
113 btrfs_free_extent(trans, root,
114 extent_buffer_blocknr(buf), 1, 1);
112 btrfs_free_extent(trans, root, buf->start,
113 buf->len, 1);
115 }
116 free_extent_buffer(buf);
117 } else {
118 btrfs_set_node_blockptr(parent, parent_slot,
114 }
115 free_extent_buffer(buf);
116 } else {
117 btrfs_set_node_blockptr(parent, parent_slot,
119 extent_buffer_blocknr(cow));
118 cow->start);
120 btrfs_mark_buffer_dirty(parent);
121 WARN_ON(btrfs_header_generation(parent) != trans->transid);
119 btrfs_mark_buffer_dirty(parent);
120 WARN_ON(btrfs_header_generation(parent) != trans->transid);
122 btrfs_free_extent(trans, root, extent_buffer_blocknr(buf),1,1);
121 btrfs_free_extent(trans, root, buf->start, buf->len, 1);
123 }
124 free_extent_buffer(buf);
125 btrfs_mark_buffer_dirty(cow);
126 *cow_ret = cow;
127 return 0;
128}
129
130int btrfs_cow_block(struct btrfs_trans_handle *trans,

--- 13 unchanged lines hidden (view full) ---

144 root->fs_info->generation);
145 WARN_ON(1);
146 }
147 if (btrfs_header_generation(buf) == trans->transid) {
148 *cow_ret = buf;
149 return 0;
150 }
151
122 }
123 free_extent_buffer(buf);
124 btrfs_mark_buffer_dirty(cow);
125 *cow_ret = cow;
126 return 0;
127}
128
129int btrfs_cow_block(struct btrfs_trans_handle *trans,

--- 13 unchanged lines hidden (view full) ---

143 root->fs_info->generation);
144 WARN_ON(1);
145 }
146 if (btrfs_header_generation(buf) == trans->transid) {
147 *cow_ret = buf;
148 return 0;
149 }
150
152 search_start = extent_buffer_blocknr(buf) & ~((u64)65535);
151 search_start = buf->start & ~((u64)BTRFS_BLOCK_GROUP_SIZE - 1);
153 ret = __btrfs_cow_block(trans, root, buf, parent,
154 parent_slot, cow_ret, search_start, 0);
155 (*cow_ret)->alloc_addr = (unsigned long)__builtin_return_address(0);
156 return ret;
157}
158
152 ret = __btrfs_cow_block(trans, root, buf, parent,
153 parent_slot, cow_ret, search_start, 0);
154 (*cow_ret)->alloc_addr = (unsigned long)__builtin_return_address(0);
155 return ret;
156}
157
158#if 0
159static int close_blocks(u64 blocknr, u64 other)
160{
161 if (blocknr < other && other - blocknr < 8)
162 return 1;
163 if (blocknr > other && blocknr - other < 8)
164 return 1;
165 return 0;
166}
167
159static int close_blocks(u64 blocknr, u64 other)
160{
161 if (blocknr < other && other - blocknr < 8)
162 return 1;
163 if (blocknr > other && blocknr - other < 8)
164 return 1;
165 return 0;
166}
167
168#if 0
169static int should_defrag_leaf(struct extent_buffer *eb)
170{
171 return 0;
172 struct btrfs_leaf *leaf = btrfs_buffer_leaf(eb);
173 struct btrfs_disk_key *key;
174 u32 nritems;
175
176 if (buffer_defrag(bh))

--- 173 unchanged lines hidden (view full) ---

350 BUG_ON(nritems == 0);
351 if (parent) {
352 parent_slot = path->slots[level + 1];
353 btrfs_node_key(parent, &parent_key, parent_slot);
354 btrfs_node_key(node, &node_key, 0);
355 BUG_ON(memcmp(&parent_key, &node_key,
356 sizeof(struct btrfs_disk_key)));
357 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
168static int should_defrag_leaf(struct extent_buffer *eb)
169{
170 return 0;
171 struct btrfs_leaf *leaf = btrfs_buffer_leaf(eb);
172 struct btrfs_disk_key *key;
173 u32 nritems;
174
175 if (buffer_defrag(bh))

--- 173 unchanged lines hidden (view full) ---

349 BUG_ON(nritems == 0);
350 if (parent) {
351 parent_slot = path->slots[level + 1];
352 btrfs_node_key(parent, &parent_key, parent_slot);
353 btrfs_node_key(node, &node_key, 0);
354 BUG_ON(memcmp(&parent_key, &node_key,
355 sizeof(struct btrfs_disk_key)));
356 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
358 btrfs_header_blocknr(node));
357 btrfs_header_bytenr(node));
359 }
360 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
361 if (slot != 0) {
362 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
363 btrfs_node_key(node, &node_key, slot);
364 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
365 }
366 if (slot < nritems - 1) {

--- 26 unchanged lines hidden (view full) ---

393 if (parent) {
394 parent_slot = path->slots[level + 1];
395 btrfs_node_key(parent, &parent_key, parent_slot);
396 btrfs_item_key(leaf, &leaf_key, 0);
397
398 BUG_ON(memcmp(&parent_key, &leaf_key,
399 sizeof(struct btrfs_disk_key)));
400 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
358 }
359 BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
360 if (slot != 0) {
361 btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
362 btrfs_node_key(node, &node_key, slot);
363 BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
364 }
365 if (slot < nritems - 1) {

--- 26 unchanged lines hidden (view full) ---

392 if (parent) {
393 parent_slot = path->slots[level + 1];
394 btrfs_node_key(parent, &parent_key, parent_slot);
395 btrfs_item_key(leaf, &leaf_key, 0);
396
397 BUG_ON(memcmp(&parent_key, &leaf_key,
398 sizeof(struct btrfs_disk_key)));
399 BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
401 btrfs_header_blocknr(leaf));
400 btrfs_header_bytenr(leaf));
402 }
403#if 0
404 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
405 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
406 btrfs_item_key(leaf, &leaf_key, i);
407 if (comp_keys(&leaf_key, &cpukey) >= 0) {
408 btrfs_print_leaf(root, leaf);
409 printk("slot %d offset bad key\n", i);

--- 52 unchanged lines hidden (view full) ---

462 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
463 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
464 return 0;
465}
466
467static int check_block(struct btrfs_root *root, struct btrfs_path *path,
468 int level)
469{
401 }
402#if 0
403 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
404 btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
405 btrfs_item_key(leaf, &leaf_key, i);
406 if (comp_keys(&leaf_key, &cpukey) >= 0) {
407 btrfs_print_leaf(root, leaf);
408 printk("slot %d offset bad key\n", i);

--- 52 unchanged lines hidden (view full) ---

461 BUG_ON(btrfs_item_offset_nr(leaf, 0) +
462 btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
463 return 0;
464}
465
466static int check_block(struct btrfs_root *root, struct btrfs_path *path,
467 int level)
468{
469#if 0
470 struct extent_buffer *buf = path->nodes[level];
471
472 if (memcmp_extent_buffer(buf, root->fs_info->fsid,
473 (unsigned long)btrfs_header_fsid(buf),
474 BTRFS_FSID_SIZE)) {
475 printk("warning bad block %Lu\n", buf->start);
470 struct extent_buffer *buf = path->nodes[level];
471
472 if (memcmp_extent_buffer(buf, root->fs_info->fsid,
473 (unsigned long)btrfs_header_fsid(buf),
474 BTRFS_FSID_SIZE)) {
475 printk("warning bad block %Lu\n", buf->start);
476 BUG();
476 return 1;
477 }
477 }
478#endif
478 if (level == 0)
479 return check_leaf(root, path, level);
480 return check_node(root, path, level);
481}
482
483/*
484 * search for key in the extent_buffer. The items start at offset p,
485 * and they are item_size apart. There are 'max' items in p.

--- 94 unchanged lines hidden (view full) ---

580
581static struct extent_buffer *read_node_slot(struct btrfs_root *root,
582 struct extent_buffer *parent, int slot)
583{
584 if (slot < 0)
585 return NULL;
586 if (slot >= btrfs_header_nritems(parent))
587 return NULL;
479 if (level == 0)
480 return check_leaf(root, path, level);
481 return check_node(root, path, level);
482}
483
484/*
485 * search for key in the extent_buffer. The items start at offset p,
486 * and they are item_size apart. There are 'max' items in p.

--- 94 unchanged lines hidden (view full) ---

581
582static struct extent_buffer *read_node_slot(struct btrfs_root *root,
583 struct extent_buffer *parent, int slot)
584{
585 if (slot < 0)
586 return NULL;
587 if (slot >= btrfs_header_nritems(parent))
588 return NULL;
588 return read_tree_block(root, btrfs_node_blockptr(parent, slot));
589 return read_tree_block(root, btrfs_node_blockptr(parent, slot),
590 btrfs_level_size(root, btrfs_header_level(parent) - 1));
589}
590
591static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
592 *root, struct btrfs_path *path, int level)
593{
594 struct extent_buffer *right = NULL;
595 struct extent_buffer *mid;
596 struct extent_buffer *left = NULL;

--- 16 unchanged lines hidden (view full) ---

613 pslot = path->slots[level + 1];
614
615 /*
616 * deal with the case where there is only one pointer in the root
617 * by promoting the node below to a root
618 */
619 if (!parent) {
620 struct extent_buffer *child;
591}
592
593static int balance_level(struct btrfs_trans_handle *trans, struct btrfs_root
594 *root, struct btrfs_path *path, int level)
595{
596 struct extent_buffer *right = NULL;
597 struct extent_buffer *mid;
598 struct extent_buffer *left = NULL;

--- 16 unchanged lines hidden (view full) ---

615 pslot = path->slots[level + 1];
616
617 /*
618 * deal with the case where there is only one pointer in the root
619 * by promoting the node below to a root
620 */
621 if (!parent) {
622 struct extent_buffer *child;
621 u64 blocknr = extent_buffer_blocknr(mid);
622
623 if (btrfs_header_nritems(mid) != 1)
624 return 0;
625
626 /* promote the child to a root */
627 child = read_node_slot(root, mid, 0);
628 BUG_ON(!child);
629 root->node = child;
630 path->nodes[level] = NULL;
631 clean_tree_block(trans, root, mid);
632 wait_on_tree_block_writeback(root, mid);
633 /* once for the path */
634 free_extent_buffer(mid);
623
624 if (btrfs_header_nritems(mid) != 1)
625 return 0;
626
627 /* promote the child to a root */
628 child = read_node_slot(root, mid, 0);
629 BUG_ON(!child);
630 root->node = child;
631 path->nodes[level] = NULL;
632 clean_tree_block(trans, root, mid);
633 wait_on_tree_block_writeback(root, mid);
634 /* once for the path */
635 free_extent_buffer(mid);
636 ret = btrfs_free_extent(trans, root, mid->start, mid->len, 1);
635 /* once for the root ptr */
636 free_extent_buffer(mid);
637 /* once for the root ptr */
638 free_extent_buffer(mid);
637 return btrfs_free_extent(trans, root, blocknr, 1, 1);
639 return ret;
638 }
639 if (btrfs_header_nritems(mid) >
640 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
641 return 0;
642
643 if (btrfs_header_nritems(mid) < 2)
644 err_on_enospc = 1;
645

--- 29 unchanged lines hidden (view full) ---

675 /*
676 * then try to empty the right most buffer into the middle
677 */
678 if (right) {
679 wret = push_node_left(trans, root, mid, right);
680 if (wret < 0 && wret != -ENOSPC)
681 ret = wret;
682 if (btrfs_header_nritems(right) == 0) {
640 }
641 if (btrfs_header_nritems(mid) >
642 BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
643 return 0;
644
645 if (btrfs_header_nritems(mid) < 2)
646 err_on_enospc = 1;
647

--- 29 unchanged lines hidden (view full) ---

677 /*
678 * then try to empty the right most buffer into the middle
679 */
680 if (right) {
681 wret = push_node_left(trans, root, mid, right);
682 if (wret < 0 && wret != -ENOSPC)
683 ret = wret;
684 if (btrfs_header_nritems(right) == 0) {
683 u64 blocknr = extent_buffer_blocknr(right);
685 u64 bytenr = right->start;
686 u32 blocksize = right->len;
687
684 clean_tree_block(trans, root, right);
685 wait_on_tree_block_writeback(root, right);
686 free_extent_buffer(right);
687 right = NULL;
688 wret = del_ptr(trans, root, path, level + 1, pslot +
689 1);
690 if (wret)
691 ret = wret;
688 clean_tree_block(trans, root, right);
689 wait_on_tree_block_writeback(root, right);
690 free_extent_buffer(right);
691 right = NULL;
692 wret = del_ptr(trans, root, path, level + 1, pslot +
693 1);
694 if (wret)
695 ret = wret;
692 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
696 wret = btrfs_free_extent(trans, root, bytenr,
697 blocksize, 1);
693 if (wret)
694 ret = wret;
695 } else {
696 struct btrfs_disk_key right_key;
697 btrfs_node_key(right, &right_key, 0);
698 btrfs_set_node_key(parent, &right_key, pslot + 1);
699 btrfs_mark_buffer_dirty(parent);
700 }

--- 13 unchanged lines hidden (view full) ---

714 if (wret < 0) {
715 ret = wret;
716 goto enospc;
717 }
718 BUG_ON(wret == 1);
719 }
720 if (btrfs_header_nritems(mid) == 0) {
721 /* we've managed to empty the middle node, drop it */
698 if (wret)
699 ret = wret;
700 } else {
701 struct btrfs_disk_key right_key;
702 btrfs_node_key(right, &right_key, 0);
703 btrfs_set_node_key(parent, &right_key, pslot + 1);
704 btrfs_mark_buffer_dirty(parent);
705 }

--- 13 unchanged lines hidden (view full) ---

719 if (wret < 0) {
720 ret = wret;
721 goto enospc;
722 }
723 BUG_ON(wret == 1);
724 }
725 if (btrfs_header_nritems(mid) == 0) {
726 /* we've managed to empty the middle node, drop it */
722 u64 blocknr = extent_buffer_blocknr(mid);
727 u64 bytenr = mid->start;
728 u32 blocksize = mid->len;
723 clean_tree_block(trans, root, mid);
724 wait_on_tree_block_writeback(root, mid);
725 free_extent_buffer(mid);
726 mid = NULL;
727 wret = del_ptr(trans, root, path, level + 1, pslot);
728 if (wret)
729 ret = wret;
729 clean_tree_block(trans, root, mid);
730 wait_on_tree_block_writeback(root, mid);
731 free_extent_buffer(mid);
732 mid = NULL;
733 wret = del_ptr(trans, root, path, level + 1, pslot);
734 if (wret)
735 ret = wret;
730 wret = btrfs_free_extent(trans, root, blocknr, 1, 1);
736 wret = btrfs_free_extent(trans, root, bytenr, blocksize, 1);
731 if (wret)
732 ret = wret;
733 } else {
734 /* update the parent key to reflect our changes */
735 struct btrfs_disk_key mid_key;
736 btrfs_node_key(mid, &mid_key, 0);
737 btrfs_set_node_key(parent, &mid_key, pslot);
738 btrfs_mark_buffer_dirty(parent);

--- 86 unchanged lines hidden (view full) ---

825 path->slots[level] = orig_slot;
826 free_extent_buffer(mid);
827 } else {
828 orig_slot -=
829 btrfs_header_nritems(left);
830 path->slots[level] = orig_slot;
831 free_extent_buffer(left);
832 }
737 if (wret)
738 ret = wret;
739 } else {
740 /* update the parent key to reflect our changes */
741 struct btrfs_disk_key mid_key;
742 btrfs_node_key(mid, &mid_key, 0);
743 btrfs_set_node_key(parent, &mid_key, pslot);
744 btrfs_mark_buffer_dirty(parent);

--- 86 unchanged lines hidden (view full) ---

831 path->slots[level] = orig_slot;
832 free_extent_buffer(mid);
833 } else {
834 orig_slot -=
835 btrfs_header_nritems(left);
836 path->slots[level] = orig_slot;
837 free_extent_buffer(left);
838 }
833 check_node(root, path, level);
834 return 0;
835 }
836 free_extent_buffer(left);
837 }
838 right= read_node_slot(root, parent, pslot + 1);
839
840 /*
841 * then try to empty the right most buffer into the middle

--- 27 unchanged lines hidden (view full) ---

869 path->nodes[level] = right;
870 path->slots[level + 1] += 1;
871 path->slots[level] = orig_slot -
872 btrfs_header_nritems(mid);
873 free_extent_buffer(mid);
874 } else {
875 free_extent_buffer(right);
876 }
839 return 0;
840 }
841 free_extent_buffer(left);
842 }
843 right= read_node_slot(root, parent, pslot + 1);
844
845 /*
846 * then try to empty the right most buffer into the middle

--- 27 unchanged lines hidden (view full) ---

874 path->nodes[level] = right;
875 path->slots[level + 1] += 1;
876 path->slots[level] = orig_slot -
877 btrfs_header_nritems(mid);
878 free_extent_buffer(mid);
879 } else {
880 free_extent_buffer(right);
881 }
877 check_node(root, path, level);
878 return 0;
879 }
880 free_extent_buffer(right);
881 }
882 return 0;
883 }
884 free_extent_buffer(right);
885 }
882 check_node(root, path, level);
883 return 1;
884}
885
886/*
887 * readahead one full node of leaves
888 */
889static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
890 int level, int slot)
891{
886 return 1;
887}
888
889/*
890 * readahead one full node of leaves
891 */
892static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
893 int level, int slot)
894{
895 return;
896#if 0
892 struct extent_buffer *node;
893 int i;
894 u32 nritems;
897 struct extent_buffer *node;
898 int i;
899 u32 nritems;
895 u64 blocknr;
900 u64 bytenr;
896 u64 search;
897 u64 cluster_start;
898 int ret;
899 int nread = 0;
900 int direction = path->reada;
901 u64 search;
902 u64 cluster_start;
903 int ret;
904 int nread = 0;
905 int direction = path->reada;
906 int level;
901 struct radix_tree_root found;
902 unsigned long gang[8];
903 struct extent_buffer *eb;
904
907 struct radix_tree_root found;
908 unsigned long gang[8];
909 struct extent_buffer *eb;
910
911
905 if (level == 0)
906 return;
907
908 if (!path->nodes[level])
909 return;
910
911 node = path->nodes[level];
912 search = btrfs_node_blockptr(node, slot);
913 eb = btrfs_find_tree_block(root, search);
914 if (eb) {
915 free_extent_buffer(eb);
916 return;
917 }
918
919 init_bit_radix(&found);
920 nritems = btrfs_header_nritems(node);
912 if (level == 0)
913 return;
914
915 if (!path->nodes[level])
916 return;
917
918 node = path->nodes[level];
919 search = btrfs_node_blockptr(node, slot);
920 eb = btrfs_find_tree_block(root, search);
921 if (eb) {
922 free_extent_buffer(eb);
923 return;
924 }
925
926 init_bit_radix(&found);
927 nritems = btrfs_header_nritems(node);
928 level = btrfs_header_level(node) - 1;
921 for (i = slot; i < nritems; i++) {
929 for (i = slot; i < nritems; i++) {
922 blocknr = btrfs_node_blockptr(node, i);
930 bytenr = btrfs_node_blockptr(node, i);
923 set_radix_bit(&found, blocknr);
924 }
925 if (direction > 0) {
926 cluster_start = search - 4;
927 if (cluster_start > search)
928 cluster_start = 0;
929 } else
930 cluster_start = search + 4;

--- 8 unchanged lines hidden (view full) ---

939 continue;
940 if (close_blocks(cluster_start, blocknr)) {
941 readahead_tree_block(root, blocknr);
942 nread++;
943 cluster_start = blocknr;
944 }
945 }
946 }
931 set_radix_bit(&found, blocknr);
932 }
933 if (direction > 0) {
934 cluster_start = search - 4;
935 if (cluster_start > search)
936 cluster_start = 0;
937 } else
938 cluster_start = search + 4;

--- 8 unchanged lines hidden (view full) ---

947 continue;
948 if (close_blocks(cluster_start, blocknr)) {
949 readahead_tree_block(root, blocknr);
950 nread++;
951 cluster_start = blocknr;
952 }
953 }
954 }
955#endif
947}
948/*
949 * look for key in the tree. path is filled in with nodes along the way
950 * if key is found, we return zero and you can find the item in the leaf
951 * level of the path (level 0)
952 *
953 * If the key isn't found, the path points to the slot where it should
954 * be inserted, and 1 is returned. If there are other errors during the
955 * search a negative error number is returned.
956 *
957 * if ins_len > 0, nodes and leaves will be split as we walk down the
958 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
959 * possible)
960 */
961int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
962 *root, struct btrfs_key *key, struct btrfs_path *p, int
963 ins_len, int cow)
964{
965 struct extent_buffer *b;
956}
957/*
958 * look for key in the tree. path is filled in with nodes along the way
959 * if key is found, we return zero and you can find the item in the leaf
960 * level of the path (level 0)
961 *
962 * If the key isn't found, the path points to the slot where it should
963 * be inserted, and 1 is returned. If there are other errors during the
964 * search a negative error number is returned.
965 *
966 * if ins_len > 0, nodes and leaves will be split as we walk down the
967 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
968 * possible)
969 */
970int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
971 *root, struct btrfs_key *key, struct btrfs_path *p, int
972 ins_len, int cow)
973{
974 struct extent_buffer *b;
966 u64 blocknr;
975 u64 bytenr;
967 int slot;
968 int ret;
969 int level;
970 int should_reada = p->reada;
971 u8 lowest_level = 0;
972
973 lowest_level = p->lowest_level;
974 WARN_ON(lowest_level && ins_len);

--- 47 unchanged lines hidden (view full) ---

1022 goto again;
1023 }
1024 slot = p->slots[level];
1025 BUG_ON(btrfs_header_nritems(b) == 1);
1026 }
1027 /* this is only true while dropping a snapshot */
1028 if (level == lowest_level)
1029 break;
976 int slot;
977 int ret;
978 int level;
979 int should_reada = p->reada;
980 u8 lowest_level = 0;
981
982 lowest_level = p->lowest_level;
983 WARN_ON(lowest_level && ins_len);

--- 47 unchanged lines hidden (view full) ---

1031 goto again;
1032 }
1033 slot = p->slots[level];
1034 BUG_ON(btrfs_header_nritems(b) == 1);
1035 }
1036 /* this is only true while dropping a snapshot */
1037 if (level == lowest_level)
1038 break;
1030 blocknr = btrfs_node_blockptr(b, slot);
1039 bytenr = btrfs_node_blockptr(b, slot);
1031 if (should_reada)
1032 reada_for_search(root, p, level, slot);
1040 if (should_reada)
1041 reada_for_search(root, p, level, slot);
1033 b = read_tree_block(root, btrfs_node_blockptr(b, slot));
1042 b = read_tree_block(root, bytenr,
1043 btrfs_level_size(root, level - 1));
1034 } else {
1035 p->slots[level] = slot;
1036 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1037 sizeof(struct btrfs_item) + ins_len) {
1038 int sret = split_leaf(trans, root, key,
1039 p, ins_len);
1040 BUG_ON(sret > 0);
1041 if (sret)

--- 146 unchanged lines hidden (view full) ---

1188{
1189 struct extent_buffer *lower;
1190 struct extent_buffer *c;
1191 struct btrfs_disk_key lower_key;
1192
1193 BUG_ON(path->nodes[level]);
1194 BUG_ON(path->nodes[level-1] != root->node);
1195
1044 } else {
1045 p->slots[level] = slot;
1046 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1047 sizeof(struct btrfs_item) + ins_len) {
1048 int sret = split_leaf(trans, root, key,
1049 p, ins_len);
1050 BUG_ON(sret > 0);
1051 if (sret)

--- 146 unchanged lines hidden (view full) ---

1198{
1199 struct extent_buffer *lower;
1200 struct extent_buffer *c;
1201 struct btrfs_disk_key lower_key;
1202
1203 BUG_ON(path->nodes[level]);
1204 BUG_ON(path->nodes[level-1] != root->node);
1205
1196 c = btrfs_alloc_free_block(trans, root,
1197 extent_buffer_blocknr(root->node), 0);
1206 c = btrfs_alloc_free_block(trans, root, root->nodesize,
1207 root->node->start, 0);
1198 if (IS_ERR(c))
1199 return PTR_ERR(c);
1200 memset_extent_buffer(c, 0, 0, root->nodesize);
1201 btrfs_set_header_nritems(c, 1);
1202 btrfs_set_header_level(c, level);
1208 if (IS_ERR(c))
1209 return PTR_ERR(c);
1210 memset_extent_buffer(c, 0, 0, root->nodesize);
1211 btrfs_set_header_nritems(c, 1);
1212 btrfs_set_header_level(c, level);
1203 btrfs_set_header_blocknr(c, extent_buffer_blocknr(c));
1213 btrfs_set_header_bytenr(c, c->start);
1204 btrfs_set_header_generation(c, trans->transid);
1205 btrfs_set_header_owner(c, root->root_key.objectid);
1206 lower = path->nodes[level-1];
1207
1208 write_extent_buffer(c, root->fs_info->fsid,
1209 (unsigned long)btrfs_header_fsid(c),
1210 BTRFS_FSID_SIZE);
1211 if (level == 1)
1212 btrfs_item_key(lower, &lower_key, 0);
1213 else
1214 btrfs_node_key(lower, &lower_key, 0);
1215 btrfs_set_node_key(c, &lower_key, 0);
1214 btrfs_set_header_generation(c, trans->transid);
1215 btrfs_set_header_owner(c, root->root_key.objectid);
1216 lower = path->nodes[level-1];
1217
1218 write_extent_buffer(c, root->fs_info->fsid,
1219 (unsigned long)btrfs_header_fsid(c),
1220 BTRFS_FSID_SIZE);
1221 if (level == 1)
1222 btrfs_item_key(lower, &lower_key, 0);
1223 else
1224 btrfs_node_key(lower, &lower_key, 0);
1225 btrfs_set_node_key(c, &lower_key, 0);
1216 btrfs_set_node_blockptr(c, 0, extent_buffer_blocknr(lower));
1226 btrfs_set_node_blockptr(c, 0, lower->start);
1217
1218 btrfs_mark_buffer_dirty(c);
1219
1220 /* the super has an extra ref to root->node */
1221 free_extent_buffer(root->node);
1222 root->node = c;
1223 extent_buffer_get(c);
1224 path->nodes[level] = c;

--- 7 unchanged lines hidden (view full) ---

1232 *
1233 * slot and level indicate where you want the key to go, and
1234 * blocknr is the block the key points to.
1235 *
1236 * returns zero on success and < 0 on any error
1237 */
1238static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1239 *root, struct btrfs_path *path, struct btrfs_disk_key
1227
1228 btrfs_mark_buffer_dirty(c);
1229
1230 /* the super has an extra ref to root->node */
1231 free_extent_buffer(root->node);
1232 root->node = c;
1233 extent_buffer_get(c);
1234 path->nodes[level] = c;

--- 7 unchanged lines hidden (view full) ---

1242 *
1243 * slot and level indicate where you want the key to go, and
1244 * blocknr is the block the key points to.
1245 *
1246 * returns zero on success and < 0 on any error
1247 */
1248static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
1249 *root, struct btrfs_path *path, struct btrfs_disk_key
1240 *key, u64 blocknr, int slot, int level)
1250 *key, u64 bytenr, int slot, int level)
1241{
1242 struct extent_buffer *lower;
1243 int nritems;
1244
1245 BUG_ON(!path->nodes[level]);
1246 lower = path->nodes[level];
1247 nritems = btrfs_header_nritems(lower);
1248 if (slot > nritems)
1249 BUG();
1250 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1251 BUG();
1252 if (slot != nritems) {
1253 memmove_extent_buffer(lower,
1254 btrfs_node_key_ptr_offset(slot + 1),
1255 btrfs_node_key_ptr_offset(slot),
1256 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1257 }
1258 btrfs_set_node_key(lower, key, slot);
1251{
1252 struct extent_buffer *lower;
1253 int nritems;
1254
1255 BUG_ON(!path->nodes[level]);
1256 lower = path->nodes[level];
1257 nritems = btrfs_header_nritems(lower);
1258 if (slot > nritems)
1259 BUG();
1260 if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
1261 BUG();
1262 if (slot != nritems) {
1263 memmove_extent_buffer(lower,
1264 btrfs_node_key_ptr_offset(slot + 1),
1265 btrfs_node_key_ptr_offset(slot),
1266 (nritems - slot) * sizeof(struct btrfs_key_ptr));
1267 }
1268 btrfs_set_node_key(lower, key, slot);
1259 btrfs_set_node_blockptr(lower, slot, blocknr);
1269 btrfs_set_node_blockptr(lower, slot, bytenr);
1260 btrfs_set_header_nritems(lower, nritems + 1);
1261 btrfs_mark_buffer_dirty(lower);
1270 btrfs_set_header_nritems(lower, nritems + 1);
1271 btrfs_mark_buffer_dirty(lower);
1262 check_node(root, path, level);
1263 return 0;
1264}
1265
1266/*
1267 * split the node at the specified level in path in two.
1268 * The path is corrected to point to the appropriate node after the split
1269 *
1270 * Before splitting this tries to make some room in the node by pushing

--- 24 unchanged lines hidden (view full) ---

1295 if (!ret && btrfs_header_nritems(c) <
1296 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1297 return 0;
1298 if (ret < 0)
1299 return ret;
1300 }
1301
1302 c_nritems = btrfs_header_nritems(c);
1272 return 0;
1273}
1274
1275/*
1276 * split the node at the specified level in path in two.
1277 * The path is corrected to point to the appropriate node after the split
1278 *
1279 * Before splitting this tries to make some room in the node by pushing

--- 24 unchanged lines hidden (view full) ---

1304 if (!ret && btrfs_header_nritems(c) <
1305 BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
1306 return 0;
1307 if (ret < 0)
1308 return ret;
1309 }
1310
1311 c_nritems = btrfs_header_nritems(c);
1303 split = btrfs_alloc_free_block(trans, root,
1304 extent_buffer_blocknr(c), 0);
1312 split = btrfs_alloc_free_block(trans, root, root->nodesize,
1313 c->start, 0);
1305 if (IS_ERR(split))
1306 return PTR_ERR(split);
1307
1308 btrfs_set_header_flags(split, btrfs_header_flags(c));
1309 btrfs_set_header_level(split, btrfs_header_level(c));
1314 if (IS_ERR(split))
1315 return PTR_ERR(split);
1316
1317 btrfs_set_header_flags(split, btrfs_header_flags(c));
1318 btrfs_set_header_level(split, btrfs_header_level(c));
1310 btrfs_set_header_blocknr(split, extent_buffer_blocknr(split));
1319 btrfs_set_header_bytenr(split, split->start);
1311 btrfs_set_header_generation(split, trans->transid);
1312 btrfs_set_header_owner(split, root->root_key.objectid);
1313 write_extent_buffer(split, root->fs_info->fsid,
1314 (unsigned long)btrfs_header_fsid(split),
1315 BTRFS_FSID_SIZE);
1316
1317 mid = (c_nritems + 1) / 2;
1318

--- 4 unchanged lines hidden (view full) ---

1323 btrfs_set_header_nritems(split, c_nritems - mid);
1324 btrfs_set_header_nritems(c, mid);
1325 ret = 0;
1326
1327 btrfs_mark_buffer_dirty(c);
1328 btrfs_mark_buffer_dirty(split);
1329
1330 btrfs_node_key(split, &disk_key, 0);
1320 btrfs_set_header_generation(split, trans->transid);
1321 btrfs_set_header_owner(split, root->root_key.objectid);
1322 write_extent_buffer(split, root->fs_info->fsid,
1323 (unsigned long)btrfs_header_fsid(split),
1324 BTRFS_FSID_SIZE);
1325
1326 mid = (c_nritems + 1) / 2;
1327

--- 4 unchanged lines hidden (view full) ---

1332 btrfs_set_header_nritems(split, c_nritems - mid);
1333 btrfs_set_header_nritems(c, mid);
1334 ret = 0;
1335
1336 btrfs_mark_buffer_dirty(c);
1337 btrfs_mark_buffer_dirty(split);
1338
1339 btrfs_node_key(split, &disk_key, 0);
1331 wret = insert_ptr(trans, root, path, &disk_key,
1332 extent_buffer_blocknr(split),
1340 wret = insert_ptr(trans, root, path, &disk_key, split->start,
1333 path->slots[level + 1] + 1,
1334 level + 1);
1335 if (wret)
1336 ret = wret;
1337
1338 if (path->slots[level] >= mid) {
1339 path->slots[level] -= mid;
1340 free_extent_buffer(c);

--- 61 unchanged lines hidden (view full) ---

1402 int i;
1403 int free_space;
1404 int push_space = 0;
1405 int push_items = 0;
1406 struct btrfs_item *item;
1407 u32 left_nritems;
1408 u32 right_nritems;
1409 u32 data_end;
1341 path->slots[level + 1] + 1,
1342 level + 1);
1343 if (wret)
1344 ret = wret;
1345
1346 if (path->slots[level] >= mid) {
1347 path->slots[level] -= mid;
1348 free_extent_buffer(c);

--- 61 unchanged lines hidden (view full) ---

1410 int i;
1411 int free_space;
1412 int push_space = 0;
1413 int push_items = 0;
1414 struct btrfs_item *item;
1415 u32 left_nritems;
1416 u32 right_nritems;
1417 u32 data_end;
1418 u32 this_item_size;
1410 int ret;
1411
1412 slot = path->slots[1];
1413 if (!path->nodes[1]) {
1414 return 1;
1415 }
1416 upper = path->nodes[1];
1417 if (slot >= btrfs_header_nritems(upper) - 1)
1418 return 1;
1419
1419 int ret;
1420
1421 slot = path->slots[1];
1422 if (!path->nodes[1]) {
1423 return 1;
1424 }
1425 upper = path->nodes[1];
1426 if (slot >= btrfs_header_nritems(upper) - 1)
1427 return 1;
1428
1420 right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1));
1429 right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1),
1430 root->leafsize);
1421 free_space = btrfs_leaf_free_space(root, right);
1422 if (free_space < data_size + sizeof(struct btrfs_item)) {
1423 free_extent_buffer(right);
1424 return 1;
1425 }
1426
1427 /* cow and double check */
1428 ret = btrfs_cow_block(trans, root, right, upper,

--- 11 unchanged lines hidden (view full) ---

1440 left_nritems = btrfs_header_nritems(left);
1441 if (left_nritems == 0) {
1442 free_extent_buffer(right);
1443 return 1;
1444 }
1445
1446 for (i = left_nritems - 1; i >= 1; i--) {
1447 item = btrfs_item_nr(left, i);
1431 free_space = btrfs_leaf_free_space(root, right);
1432 if (free_space < data_size + sizeof(struct btrfs_item)) {
1433 free_extent_buffer(right);
1434 return 1;
1435 }
1436
1437 /* cow and double check */
1438 ret = btrfs_cow_block(trans, root, right, upper,

--- 11 unchanged lines hidden (view full) ---

1450 left_nritems = btrfs_header_nritems(left);
1451 if (left_nritems == 0) {
1452 free_extent_buffer(right);
1453 return 1;
1454 }
1455
1456 for (i = left_nritems - 1; i >= 1; i--) {
1457 item = btrfs_item_nr(left, i);
1458
1448 if (path->slots[0] == i)
1449 push_space += data_size + sizeof(*item);
1459 if (path->slots[0] == i)
1460 push_space += data_size + sizeof(*item);
1450 if (btrfs_item_size(left, item) + sizeof(*item) + push_space >
1451 free_space)
1461
1462 if (!left->map_token) {
1463 map_extent_buffer(left, (unsigned long)item,
1464 sizeof(struct btrfs_item),
1465 &left->map_token, &left->kaddr,
1466 &left->map_start, &left->map_len,
1467 KM_USER1);
1468 }
1469
1470 this_item_size = btrfs_item_size(left, item);
1471 if (this_item_size + sizeof(*item) + push_space > free_space)
1452 break;
1453 push_items++;
1472 break;
1473 push_items++;
1454 push_space += btrfs_item_size(left, item) + sizeof(*item);
1474 push_space += this_item_size + sizeof(*item);
1455 }
1475 }
1476 if (left->map_token) {
1477 unmap_extent_buffer(left, left->map_token, KM_USER1);
1478 left->map_token = NULL;
1479 }
1456
1457 if (push_items == 0) {
1458 free_extent_buffer(right);
1459 return 1;
1460 }
1461
1462 if (push_items == left_nritems)
1463 WARN_ON(1);

--- 24 unchanged lines hidden (view full) ---

1488 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1489 btrfs_item_nr_offset(left_nritems - push_items),
1490 push_items * sizeof(struct btrfs_item));
1491
1492 /* update the item pointers */
1493 right_nritems += push_items;
1494 btrfs_set_header_nritems(right, right_nritems);
1495 push_space = BTRFS_LEAF_DATA_SIZE(root);
1480
1481 if (push_items == 0) {
1482 free_extent_buffer(right);
1483 return 1;
1484 }
1485
1486 if (push_items == left_nritems)
1487 WARN_ON(1);

--- 24 unchanged lines hidden (view full) ---

1512 copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
1513 btrfs_item_nr_offset(left_nritems - push_items),
1514 push_items * sizeof(struct btrfs_item));
1515
1516 /* update the item pointers */
1517 right_nritems += push_items;
1518 btrfs_set_header_nritems(right, right_nritems);
1519 push_space = BTRFS_LEAF_DATA_SIZE(root);
1520
1496 for (i = 0; i < right_nritems; i++) {
1497 item = btrfs_item_nr(right, i);
1521 for (i = 0; i < right_nritems; i++) {
1522 item = btrfs_item_nr(right, i);
1498 btrfs_set_item_offset(right, item, push_space -
1499 btrfs_item_size(right, item));
1500 push_space = btrfs_item_offset(right, item);
1523 if (!right->map_token) {
1524 map_extent_buffer(right, (unsigned long)item,
1525 sizeof(struct btrfs_item),
1526 &right->map_token, &right->kaddr,
1527 &right->map_start, &right->map_len,
1528 KM_USER1);
1529 }
1530 push_space -= btrfs_item_size(right, item);
1531 btrfs_set_item_offset(right, item, push_space);
1501 }
1532 }
1533
1534 if (right->map_token) {
1535 unmap_extent_buffer(right, right->map_token, KM_USER1);
1536 right->map_token = NULL;
1537 }
1502 left_nritems -= push_items;
1503 btrfs_set_header_nritems(left, left_nritems);
1504
1505 btrfs_mark_buffer_dirty(left);
1506 btrfs_mark_buffer_dirty(right);
1507
1508 btrfs_item_key(right, &disk_key, 0);
1509 btrfs_set_node_key(upper, &disk_key, slot + 1);
1510 btrfs_mark_buffer_dirty(upper);
1511
1512 /* then fixup the leaf pointer in the path */
1513 if (path->slots[0] >= left_nritems) {
1514 path->slots[0] -= left_nritems;
1515 free_extent_buffer(path->nodes[0]);
1516 path->nodes[0] = right;
1517 path->slots[1] += 1;
1518 } else {
1519 free_extent_buffer(right);
1520 }
1538 left_nritems -= push_items;
1539 btrfs_set_header_nritems(left, left_nritems);
1540
1541 btrfs_mark_buffer_dirty(left);
1542 btrfs_mark_buffer_dirty(right);
1543
1544 btrfs_item_key(right, &disk_key, 0);
1545 btrfs_set_node_key(upper, &disk_key, slot + 1);
1546 btrfs_mark_buffer_dirty(upper);
1547
1548 /* then fixup the leaf pointer in the path */
1549 if (path->slots[0] >= left_nritems) {
1550 path->slots[0] -= left_nritems;
1551 free_extent_buffer(path->nodes[0]);
1552 path->nodes[0] = right;
1553 path->slots[1] += 1;
1554 } else {
1555 free_extent_buffer(right);
1556 }
1521 if (path->nodes[1])
1522 check_node(root, path, 1);
1523 return 0;
1524}
1525/*
1526 * push some data in the path leaf to the left, trying to free up at
1527 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1528 */
1529static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1530 *root, struct btrfs_path *path, int data_size)

--- 6 unchanged lines hidden (view full) ---

1537 int free_space;
1538 int push_space = 0;
1539 int push_items = 0;
1540 struct btrfs_item *item;
1541 u32 old_left_nritems;
1542 u32 right_nritems;
1543 int ret = 0;
1544 int wret;
1557 return 0;
1558}
1559/*
1560 * push some data in the path leaf to the left, trying to free up at
1561 * least data_size bytes. returns zero if the push worked, nonzero otherwise
1562 */
1563static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
1564 *root, struct btrfs_path *path, int data_size)

--- 6 unchanged lines hidden (view full) ---

1571 int free_space;
1572 int push_space = 0;
1573 int push_items = 0;
1574 struct btrfs_item *item;
1575 u32 old_left_nritems;
1576 u32 right_nritems;
1577 int ret = 0;
1578 int wret;
1579 u32 this_item_size;
1580 u32 old_left_item_size;
1545
1546 slot = path->slots[1];
1547 if (slot == 0)
1548 return 1;
1549 if (!path->nodes[1])
1550 return 1;
1551
1552 left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1581
1582 slot = path->slots[1];
1583 if (slot == 0)
1584 return 1;
1585 if (!path->nodes[1])
1586 return 1;
1587
1588 left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
1553 slot - 1));
1589 slot - 1), root->leafsize);
1554 free_space = btrfs_leaf_free_space(root, left);
1555 if (free_space < data_size + sizeof(struct btrfs_item)) {
1556 free_extent_buffer(left);
1557 return 1;
1558 }
1559
1560 /* cow and double check */
1561 ret = btrfs_cow_block(trans, root, left,

--- 12 unchanged lines hidden (view full) ---

1574 right_nritems = btrfs_header_nritems(right);
1575 if (right_nritems == 0) {
1576 free_extent_buffer(left);
1577 return 1;
1578 }
1579
1580 for (i = 0; i < right_nritems - 1; i++) {
1581 item = btrfs_item_nr(right, i);
1590 free_space = btrfs_leaf_free_space(root, left);
1591 if (free_space < data_size + sizeof(struct btrfs_item)) {
1592 free_extent_buffer(left);
1593 return 1;
1594 }
1595
1596 /* cow and double check */
1597 ret = btrfs_cow_block(trans, root, left,

--- 12 unchanged lines hidden (view full) ---

1610 right_nritems = btrfs_header_nritems(right);
1611 if (right_nritems == 0) {
1612 free_extent_buffer(left);
1613 return 1;
1614 }
1615
1616 for (i = 0; i < right_nritems - 1; i++) {
1617 item = btrfs_item_nr(right, i);
1618 if (!right->map_token) {
1619 map_extent_buffer(right, (unsigned long)item,
1620 sizeof(struct btrfs_item),
1621 &right->map_token, &right->kaddr,
1622 &right->map_start, &right->map_len,
1623 KM_USER1);
1624 }
1625
1582 if (path->slots[0] == i)
1583 push_space += data_size + sizeof(*item);
1626 if (path->slots[0] == i)
1627 push_space += data_size + sizeof(*item);
1584 if (btrfs_item_size(right, item) + sizeof(*item) + push_space >
1585 free_space)
1628
1629 this_item_size = btrfs_item_size(right, item);
1630 if (this_item_size + sizeof(*item) + push_space > free_space)
1586 break;
1631 break;
1632
1587 push_items++;
1633 push_items++;
1588 push_space += btrfs_item_size(right, item) + sizeof(*item);
1634 push_space += this_item_size + sizeof(*item);
1589 }
1635 }
1636
1637 if (right->map_token) {
1638 unmap_extent_buffer(right, right->map_token, KM_USER1);
1639 right->map_token = NULL;
1640 }
1641
1590 if (push_items == 0) {
1591 free_extent_buffer(left);
1592 return 1;
1593 }
1594 if (push_items == btrfs_header_nritems(right))
1595 WARN_ON(1);
1596
1597 /* push data from right to left */

--- 8 unchanged lines hidden (view full) ---

1606 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1607 leaf_data_end(root, left) - push_space,
1608 btrfs_leaf_data(right) +
1609 btrfs_item_offset_nr(right, push_items - 1),
1610 push_space);
1611 old_left_nritems = btrfs_header_nritems(left);
1612 BUG_ON(old_left_nritems < 0);
1613
1642 if (push_items == 0) {
1643 free_extent_buffer(left);
1644 return 1;
1645 }
1646 if (push_items == btrfs_header_nritems(right))
1647 WARN_ON(1);
1648
1649 /* push data from right to left */

--- 8 unchanged lines hidden (view full) ---

1658 copy_extent_buffer(left, right, btrfs_leaf_data(left) +
1659 leaf_data_end(root, left) - push_space,
1660 btrfs_leaf_data(right) +
1661 btrfs_item_offset_nr(right, push_items - 1),
1662 push_space);
1663 old_left_nritems = btrfs_header_nritems(left);
1664 BUG_ON(old_left_nritems < 0);
1665
1666 old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
1614 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1615 u32 ioff;
1667 for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
1668 u32 ioff;
1669
1616 item = btrfs_item_nr(left, i);
1670 item = btrfs_item_nr(left, i);
1671 if (!left->map_token) {
1672 map_extent_buffer(left, (unsigned long)item,
1673 sizeof(struct btrfs_item),
1674 &left->map_token, &left->kaddr,
1675 &left->map_start, &left->map_len,
1676 KM_USER1);
1677 }
1678
1617 ioff = btrfs_item_offset(left, item);
1618 btrfs_set_item_offset(left, item,
1679 ioff = btrfs_item_offset(left, item);
1680 btrfs_set_item_offset(left, item,
1619 ioff - (BTRFS_LEAF_DATA_SIZE(root) -
1620 btrfs_item_offset_nr(left, old_left_nritems - 1)));
1681 ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
1621 }
1622 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1682 }
1683 btrfs_set_header_nritems(left, old_left_nritems + push_items);
1684 if (left->map_token) {
1685 unmap_extent_buffer(left, left->map_token, KM_USER1);
1686 left->map_token = NULL;
1687 }
1623
1624 /* fixup right node */
1625 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1626 leaf_data_end(root, right);
1627 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1628 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1629 btrfs_leaf_data(right) +
1630 leaf_data_end(root, right), push_space);

--- 4 unchanged lines hidden (view full) ---

1635 sizeof(struct btrfs_item));
1636
1637 right_nritems = btrfs_header_nritems(right) - push_items;
1638 btrfs_set_header_nritems(right, right_nritems);
1639 push_space = BTRFS_LEAF_DATA_SIZE(root);
1640
1641 for (i = 0; i < right_nritems; i++) {
1642 item = btrfs_item_nr(right, i);
1688
1689 /* fixup right node */
1690 push_space = btrfs_item_offset_nr(right, push_items - 1) -
1691 leaf_data_end(root, right);
1692 memmove_extent_buffer(right, btrfs_leaf_data(right) +
1693 BTRFS_LEAF_DATA_SIZE(root) - push_space,
1694 btrfs_leaf_data(right) +
1695 leaf_data_end(root, right), push_space);

--- 4 unchanged lines hidden (view full) ---

1700 sizeof(struct btrfs_item));
1701
1702 right_nritems = btrfs_header_nritems(right) - push_items;
1703 btrfs_set_header_nritems(right, right_nritems);
1704 push_space = BTRFS_LEAF_DATA_SIZE(root);
1705
1706 for (i = 0; i < right_nritems; i++) {
1707 item = btrfs_item_nr(right, i);
1643 btrfs_set_item_offset(right, item, push_space -
1644 btrfs_item_size(right, item));
1645 push_space = btrfs_item_offset(right, item);
1708
1709 if (!right->map_token) {
1710 map_extent_buffer(right, (unsigned long)item,
1711 sizeof(struct btrfs_item),
1712 &right->map_token, &right->kaddr,
1713 &right->map_start, &right->map_len,
1714 KM_USER1);
1715 }
1716
1717 push_space = push_space - btrfs_item_size(right, item);
1718 btrfs_set_item_offset(right, item, push_space);
1646 }
1719 }
1720 if (right->map_token) {
1721 unmap_extent_buffer(right, right->map_token, KM_USER1);
1722 right->map_token = NULL;
1723 }
1647
1648 btrfs_mark_buffer_dirty(left);
1649 btrfs_mark_buffer_dirty(right);
1650
1651 btrfs_item_key(right, &disk_key, 0);
1652 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1653 if (wret)
1654 ret = wret;

--- 4 unchanged lines hidden (view full) ---

1659 free_extent_buffer(path->nodes[0]);
1660 path->nodes[0] = left;
1661 path->slots[1] -= 1;
1662 } else {
1663 free_extent_buffer(left);
1664 path->slots[0] -= push_items;
1665 }
1666 BUG_ON(path->slots[0] < 0);
1724
1725 btrfs_mark_buffer_dirty(left);
1726 btrfs_mark_buffer_dirty(right);
1727
1728 btrfs_item_key(right, &disk_key, 0);
1729 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1730 if (wret)
1731 ret = wret;

--- 4 unchanged lines hidden (view full) ---

1736 free_extent_buffer(path->nodes[0]);
1737 path->nodes[0] = left;
1738 path->slots[1] -= 1;
1739 } else {
1740 free_extent_buffer(left);
1741 path->slots[0] -= push_items;
1742 }
1743 BUG_ON(path->slots[0] < 0);
1667 if (path->nodes[1])
1668 check_node(root, path, 1);
1669 return ret;
1670}
1671
1672/*
1673 * split the path's leaf in two, making sure there is at least data_size
1674 * available for the resulting leaf level of the path.
1675 *
1676 * returns 0 if all went well and < 0 on failure.

--- 36 unchanged lines hidden (view full) ---

1713 ret = insert_new_root(trans, root, path, 1);
1714 if (ret)
1715 return ret;
1716 }
1717 slot = path->slots[0];
1718 nritems = btrfs_header_nritems(l);
1719 mid = (nritems + 1)/ 2;
1720
1744 return ret;
1745}
1746
1747/*
1748 * split the path's leaf in two, making sure there is at least data_size
1749 * available for the resulting leaf level of the path.
1750 *
1751 * returns 0 if all went well and < 0 on failure.

--- 36 unchanged lines hidden (view full) ---

1788 ret = insert_new_root(trans, root, path, 1);
1789 if (ret)
1790 return ret;
1791 }
1792 slot = path->slots[0];
1793 nritems = btrfs_header_nritems(l);
1794 mid = (nritems + 1)/ 2;
1795
1721 right = btrfs_alloc_free_block(trans, root,
1722 extent_buffer_blocknr(l), 0);
1796 right = btrfs_alloc_free_block(trans, root, root->leafsize,
1797 l->start, 0);
1723 if (IS_ERR(right))
1724 return PTR_ERR(right);
1725
1726 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1798 if (IS_ERR(right))
1799 return PTR_ERR(right);
1800
1801 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1727 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1802 btrfs_set_header_bytenr(right, right->start);
1728 btrfs_set_header_generation(right, trans->transid);
1729 btrfs_set_header_owner(right, root->root_key.objectid);
1730 btrfs_set_header_level(right, 0);
1731 write_extent_buffer(right, root->fs_info->fsid,
1732 (unsigned long)btrfs_header_fsid(right),
1733 BTRFS_FSID_SIZE);
1734
1735 if (mid <= slot) {
1736 if (nritems == 1 ||
1737 leaf_space_used(l, mid, nritems - mid) + space_needed >
1738 BTRFS_LEAF_DATA_SIZE(root)) {
1739 if (slot >= nritems) {
1740 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1741 btrfs_set_header_nritems(right, 0);
1742 wret = insert_ptr(trans, root, path,
1803 btrfs_set_header_generation(right, trans->transid);
1804 btrfs_set_header_owner(right, root->root_key.objectid);
1805 btrfs_set_header_level(right, 0);
1806 write_extent_buffer(right, root->fs_info->fsid,
1807 (unsigned long)btrfs_header_fsid(right),
1808 BTRFS_FSID_SIZE);
1809
1810 if (mid <= slot) {
1811 if (nritems == 1 ||
1812 leaf_space_used(l, mid, nritems - mid) + space_needed >
1813 BTRFS_LEAF_DATA_SIZE(root)) {
1814 if (slot >= nritems) {
1815 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1816 btrfs_set_header_nritems(right, 0);
1817 wret = insert_ptr(trans, root, path,
1743 &disk_key,
1744 extent_buffer_blocknr(right),
1818 &disk_key, right->start,
1745 path->slots[1] + 1, 1);
1746 if (wret)
1747 ret = wret;
1748 free_extent_buffer(path->nodes[0]);
1749 path->nodes[0] = right;
1750 path->slots[0] = 0;
1751 path->slots[1] += 1;
1752 return ret;

--- 4 unchanged lines hidden (view full) ---

1757 } else {
1758 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1759 BTRFS_LEAF_DATA_SIZE(root)) {
1760 if (slot == 0) {
1761 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1762 btrfs_set_header_nritems(right, 0);
1763 wret = insert_ptr(trans, root, path,
1764 &disk_key,
1819 path->slots[1] + 1, 1);
1820 if (wret)
1821 ret = wret;
1822 free_extent_buffer(path->nodes[0]);
1823 path->nodes[0] = right;
1824 path->slots[0] = 0;
1825 path->slots[1] += 1;
1826 return ret;

--- 4 unchanged lines hidden (view full) ---

1831 } else {
1832 if (leaf_space_used(l, 0, mid + 1) + space_needed >
1833 BTRFS_LEAF_DATA_SIZE(root)) {
1834 if (slot == 0) {
1835 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1836 btrfs_set_header_nritems(right, 0);
1837 wret = insert_ptr(trans, root, path,
1838 &disk_key,
1765 extent_buffer_blocknr(right),
1839 right->start,
1766 path->slots[1], 1);
1767 if (wret)
1768 ret = wret;
1769 free_extent_buffer(path->nodes[0]);
1770 path->nodes[0] = right;
1771 path->slots[0] = 0;
1772 if (path->slots[1] == 0) {
1773 wret = fixup_low_keys(trans, root,

--- 20 unchanged lines hidden (view full) ---

1794 data_copy_size, btrfs_leaf_data(l) +
1795 leaf_data_end(root, l), data_copy_size);
1796
1797 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1798 btrfs_item_end_nr(l, mid);
1799
1800 for (i = 0; i < nritems; i++) {
1801 struct btrfs_item *item = btrfs_item_nr(right, i);
1840 path->slots[1], 1);
1841 if (wret)
1842 ret = wret;
1843 free_extent_buffer(path->nodes[0]);
1844 path->nodes[0] = right;
1845 path->slots[0] = 0;
1846 if (path->slots[1] == 0) {
1847 wret = fixup_low_keys(trans, root,

--- 20 unchanged lines hidden (view full) ---

1868 data_copy_size, btrfs_leaf_data(l) +
1869 leaf_data_end(root, l), data_copy_size);
1870
1871 rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
1872 btrfs_item_end_nr(l, mid);
1873
1874 for (i = 0; i < nritems; i++) {
1875 struct btrfs_item *item = btrfs_item_nr(right, i);
1802 u32 ioff = btrfs_item_offset(right, item);
1876 u32 ioff;
1877
1878 if (!right->map_token) {
1879 map_extent_buffer(right, (unsigned long)item,
1880 sizeof(struct btrfs_item),
1881 &right->map_token, &right->kaddr,
1882 &right->map_start, &right->map_len,
1883 KM_USER1);
1884 }
1885
1886 ioff = btrfs_item_offset(right, item);
1803 btrfs_set_item_offset(right, item, ioff + rt_data_off);
1804 }
1805
1887 btrfs_set_item_offset(right, item, ioff + rt_data_off);
1888 }
1889
1890 if (right->map_token) {
1891 unmap_extent_buffer(right, right->map_token, KM_USER1);
1892 right->map_token = NULL;
1893 }
1894
1806 btrfs_set_header_nritems(l, mid);
1807 ret = 0;
1808 btrfs_item_key(right, &disk_key, 0);
1895 btrfs_set_header_nritems(l, mid);
1896 ret = 0;
1897 btrfs_item_key(right, &disk_key, 0);
1809 wret = insert_ptr(trans, root, path, &disk_key,
1810 extent_buffer_blocknr(right), path->slots[1] + 1, 1);
1898 wret = insert_ptr(trans, root, path, &disk_key, right->start,
1899 path->slots[1] + 1, 1);
1811 if (wret)
1812 ret = wret;
1813
1814 btrfs_mark_buffer_dirty(right);
1815 btrfs_mark_buffer_dirty(l);
1816 BUG_ON(path->slots[0] != slot);
1817
1818 if (mid <= slot) {
1819 free_extent_buffer(path->nodes[0]);
1820 path->nodes[0] = right;
1821 path->slots[0] -= mid;
1822 path->slots[1] += 1;
1823 } else
1824 free_extent_buffer(right);
1825
1826 BUG_ON(path->slots[0] < 0);
1900 if (wret)
1901 ret = wret;
1902
1903 btrfs_mark_buffer_dirty(right);
1904 btrfs_mark_buffer_dirty(l);
1905 BUG_ON(path->slots[0] != slot);
1906
1907 if (mid <= slot) {
1908 free_extent_buffer(path->nodes[0]);
1909 path->nodes[0] = right;
1910 path->slots[0] -= mid;
1911 path->slots[1] += 1;
1912 } else
1913 free_extent_buffer(right);
1914
1915 BUG_ON(path->slots[0] < 0);
1827 check_node(root, path, 1);
1828 check_leaf(root, path, 0);
1829
1830 if (!double_split)
1831 return ret;
1832
1916
1917 if (!double_split)
1918 return ret;
1919
1833 right = btrfs_alloc_free_block(trans, root,
1834 extent_buffer_blocknr(l), 0);
1920 right = btrfs_alloc_free_block(trans, root, root->leafsize,
1921 l->start, 0);
1835 if (IS_ERR(right))
1836 return PTR_ERR(right);
1837
1838 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1922 if (IS_ERR(right))
1923 return PTR_ERR(right);
1924
1925 memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
1839 btrfs_set_header_blocknr(right, extent_buffer_blocknr(right));
1926 btrfs_set_header_bytenr(right, right->start);
1840 btrfs_set_header_generation(right, trans->transid);
1841 btrfs_set_header_owner(right, root->root_key.objectid);
1842 btrfs_set_header_level(right, 0);
1843 write_extent_buffer(right, root->fs_info->fsid,
1844 (unsigned long)btrfs_header_fsid(right),
1845 BTRFS_FSID_SIZE);
1846
1847 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1848 btrfs_set_header_nritems(right, 0);
1849 wret = insert_ptr(trans, root, path,
1927 btrfs_set_header_generation(right, trans->transid);
1928 btrfs_set_header_owner(right, root->root_key.objectid);
1929 btrfs_set_header_level(right, 0);
1930 write_extent_buffer(right, root->fs_info->fsid,
1931 (unsigned long)btrfs_header_fsid(right),
1932 BTRFS_FSID_SIZE);
1933
1934 btrfs_cpu_key_to_disk(&disk_key, ins_key);
1935 btrfs_set_header_nritems(right, 0);
1936 wret = insert_ptr(trans, root, path,
1850 &disk_key,
1851 extent_buffer_blocknr(right),
1937 &disk_key, right->start,
1852 path->slots[1], 1);
1853 if (wret)
1854 ret = wret;
1855 if (path->slots[1] == 0) {
1856 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1857 if (wret)
1858 ret = wret;
1859 }
1860 free_extent_buffer(path->nodes[0]);
1861 path->nodes[0] = right;
1862 path->slots[0] = 0;
1938 path->slots[1], 1);
1939 if (wret)
1940 ret = wret;
1941 if (path->slots[1] == 0) {
1942 wret = fixup_low_keys(trans, root, path, &disk_key, 1);
1943 if (wret)
1944 ret = wret;
1945 }
1946 free_extent_buffer(path->nodes[0]);
1947 path->nodes[0] = right;
1948 path->slots[0] = 0;
1863 check_node(root, path, 1);
1864 check_leaf(root, path, 0);
1865 return ret;
1866}
1867
1868int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1869 struct btrfs_root *root,
1870 struct btrfs_path *path,
1871 u32 new_size)
1872{

--- 26 unchanged lines hidden (view full) ---

1899
1900 /*
1901 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1902 */
1903 /* first correct the data pointers */
1904 for (i = slot; i < nritems; i++) {
1905 u32 ioff;
1906 item = btrfs_item_nr(leaf, i);
1949 return ret;
1950}
1951
1952int btrfs_truncate_item(struct btrfs_trans_handle *trans,
1953 struct btrfs_root *root,
1954 struct btrfs_path *path,
1955 u32 new_size)
1956{

--- 26 unchanged lines hidden (view full) ---

1983
1984 /*
1985 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1986 */
1987 /* first correct the data pointers */
1988 for (i = slot; i < nritems; i++) {
1989 u32 ioff;
1990 item = btrfs_item_nr(leaf, i);
1991
1992 if (!leaf->map_token) {
1993 map_extent_buffer(leaf, (unsigned long)item,
1994 sizeof(struct btrfs_item),
1995 &leaf->map_token, &leaf->kaddr,
1996 &leaf->map_start, &leaf->map_len,
1997 KM_USER1);
1998 }
1999
1907 ioff = btrfs_item_offset(leaf, item);
1908 btrfs_set_item_offset(leaf, item, ioff + size_diff);
1909 }
2000 ioff = btrfs_item_offset(leaf, item);
2001 btrfs_set_item_offset(leaf, item, ioff + size_diff);
2002 }
2003
2004 if (leaf->map_token) {
2005 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2006 leaf->map_token = NULL;
2007 }
2008
1910 /* shift the data */
1911 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1912 data_end + size_diff, btrfs_leaf_data(leaf) +
1913 data_end, old_data_start + new_size - data_end);
1914
1915 item = btrfs_item_nr(leaf, slot);
1916 btrfs_set_item_size(leaf, item, new_size);
1917 btrfs_mark_buffer_dirty(leaf);
1918
1919 ret = 0;
1920 if (btrfs_leaf_free_space(root, leaf) < 0) {
1921 btrfs_print_leaf(root, leaf);
1922 BUG();
1923 }
2009 /* shift the data */
2010 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2011 data_end + size_diff, btrfs_leaf_data(leaf) +
2012 data_end, old_data_start + new_size - data_end);
2013
2014 item = btrfs_item_nr(leaf, slot);
2015 btrfs_set_item_size(leaf, item, new_size);
2016 btrfs_mark_buffer_dirty(leaf);
2017
2018 ret = 0;
2019 if (btrfs_leaf_free_space(root, leaf) < 0) {
2020 btrfs_print_leaf(root, leaf);
2021 BUG();
2022 }
1924 check_leaf(root, path, 0);
1925 return ret;
1926}
1927
1928int btrfs_extend_item(struct btrfs_trans_handle *trans,
1929 struct btrfs_root *root, struct btrfs_path *path,
1930 u32 data_size)
1931{
1932 int ret = 0;

--- 25 unchanged lines hidden (view full) ---

1958
1959 /*
1960 * item0..itemN ... dataN.offset..dataN.size .. data0.size
1961 */
1962 /* first correct the data pointers */
1963 for (i = slot; i < nritems; i++) {
1964 u32 ioff;
1965 item = btrfs_item_nr(leaf, i);
2023 return ret;
2024}
2025
2026int btrfs_extend_item(struct btrfs_trans_handle *trans,
2027 struct btrfs_root *root, struct btrfs_path *path,
2028 u32 data_size)
2029{
2030 int ret = 0;

--- 25 unchanged lines hidden (view full) ---

2056
2057 /*
2058 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2059 */
2060 /* first correct the data pointers */
2061 for (i = slot; i < nritems; i++) {
2062 u32 ioff;
2063 item = btrfs_item_nr(leaf, i);
2064
2065 if (!leaf->map_token) {
2066 map_extent_buffer(leaf, (unsigned long)item,
2067 sizeof(struct btrfs_item),
2068 &leaf->map_token, &leaf->kaddr,
2069 &leaf->map_start, &leaf->map_len,
2070 KM_USER1);
2071 }
1966 ioff = btrfs_item_offset(leaf, item);
1967 btrfs_set_item_offset(leaf, item, ioff - data_size);
1968 }
1969
2072 ioff = btrfs_item_offset(leaf, item);
2073 btrfs_set_item_offset(leaf, item, ioff - data_size);
2074 }
2075
2076 if (leaf->map_token) {
2077 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2078 leaf->map_token = NULL;
2079 }
2080
1970 /* shift the data */
1971 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
1972 data_end - data_size, btrfs_leaf_data(leaf) +
1973 data_end, old_data - data_end);
1974
1975 data_end = old_data;
1976 old_size = btrfs_item_size_nr(leaf, slot);
1977 item = btrfs_item_nr(leaf, slot);
1978 btrfs_set_item_size(leaf, item, old_size + data_size);
1979 btrfs_mark_buffer_dirty(leaf);
1980
1981 ret = 0;
1982 if (btrfs_leaf_free_space(root, leaf) < 0) {
1983 btrfs_print_leaf(root, leaf);
1984 BUG();
1985 }
2081 /* shift the data */
2082 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2083 data_end - data_size, btrfs_leaf_data(leaf) +
2084 data_end, old_data - data_end);
2085
2086 data_end = old_data;
2087 old_size = btrfs_item_size_nr(leaf, slot);
2088 item = btrfs_item_nr(leaf, slot);
2089 btrfs_set_item_size(leaf, item, old_size + data_size);
2090 btrfs_mark_buffer_dirty(leaf);
2091
2092 ret = 0;
2093 if (btrfs_leaf_free_space(root, leaf) < 0) {
2094 btrfs_print_leaf(root, leaf);
2095 BUG();
2096 }
1986 check_leaf(root, path, 0);
1987 return ret;
1988}
1989
1990/*
1991 * Given a key and some data, insert an item into the tree.
1992 * This does all the path init required, making room in the tree if needed.
1993 */
1994int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,

--- 46 unchanged lines hidden (view full) ---

2041 printk("slot %d old_data %d data_end %d\n",
2042 slot, old_data, data_end);
2043 BUG_ON(1);
2044 }
2045 /*
2046 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2047 */
2048 /* first correct the data pointers */
2097 return ret;
2098}
2099
2100/*
2101 * Given a key and some data, insert an item into the tree.
2102 * This does all the path init required, making room in the tree if needed.
2103 */
2104int btrfs_insert_empty_item(struct btrfs_trans_handle *trans,

--- 46 unchanged lines hidden (view full) ---

2151 printk("slot %d old_data %d data_end %d\n",
2152 slot, old_data, data_end);
2153 BUG_ON(1);
2154 }
2155 /*
2156 * item0..itemN ... dataN.offset..dataN.size .. data0.size
2157 */
2158 /* first correct the data pointers */
2159 WARN_ON(leaf->map_token);
2049 for (i = slot; i < nritems; i++) {
2050 u32 ioff;
2160 for (i = slot; i < nritems; i++) {
2161 u32 ioff;
2162
2051 item = btrfs_item_nr(leaf, i);
2163 item = btrfs_item_nr(leaf, i);
2164 if (!leaf->map_token) {
2165 map_extent_buffer(leaf, (unsigned long)item,
2166 sizeof(struct btrfs_item),
2167 &leaf->map_token, &leaf->kaddr,
2168 &leaf->map_start, &leaf->map_len,
2169 KM_USER1);
2170 }
2171
2052 ioff = btrfs_item_offset(leaf, item);
2053 btrfs_set_item_offset(leaf, item, ioff - data_size);
2054 }
2172 ioff = btrfs_item_offset(leaf, item);
2173 btrfs_set_item_offset(leaf, item, ioff - data_size);
2174 }
2175 if (leaf->map_token) {
2176 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2177 leaf->map_token = NULL;
2178 }
2055
2056 /* shift the items */
2057 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2058 btrfs_item_nr_offset(slot),
2059 (nritems - slot) * sizeof(struct btrfs_item));
2060
2061 /* shift the data */
2062 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +

--- 13 unchanged lines hidden (view full) ---

2076 ret = 0;
2077 if (slot == 0)
2078 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2079
2080 if (btrfs_leaf_free_space(root, leaf) < 0) {
2081 btrfs_print_leaf(root, leaf);
2082 BUG();
2083 }
2179
2180 /* shift the items */
2181 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + 1),
2182 btrfs_item_nr_offset(slot),
2183 (nritems - slot) * sizeof(struct btrfs_item));
2184
2185 /* shift the data */
2186 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +

--- 13 unchanged lines hidden (view full) ---

2200 ret = 0;
2201 if (slot == 0)
2202 ret = fixup_low_keys(trans, root, path, &disk_key, 1);
2203
2204 if (btrfs_leaf_free_space(root, leaf) < 0) {
2205 btrfs_print_leaf(root, leaf);
2206 BUG();
2207 }
2084 check_leaf(root, path, 0);
2085out:
2086 return ret;
2087}
2088
2089/*
2090 * Given a key and some data, insert an item into the tree.
2091 * This does all the path init required, making room in the tree if needed.
2092 */

--- 88 unchanged lines hidden (view full) ---

2181
2182 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2183 data_end + dsize,
2184 btrfs_leaf_data(leaf) + data_end,
2185 doff - data_end);
2186
2187 for (i = slot + 1; i < nritems; i++) {
2188 u32 ioff;
2208out:
2209 return ret;
2210}
2211
2212/*
2213 * Given a key and some data, insert an item into the tree.
2214 * This does all the path init required, making room in the tree if needed.
2215 */

--- 88 unchanged lines hidden (view full) ---

2304
2305 memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
2306 data_end + dsize,
2307 btrfs_leaf_data(leaf) + data_end,
2308 doff - data_end);
2309
2310 for (i = slot + 1; i < nritems; i++) {
2311 u32 ioff;
2312
2189 item = btrfs_item_nr(leaf, i);
2313 item = btrfs_item_nr(leaf, i);
2314 if (!leaf->map_token) {
2315 map_extent_buffer(leaf, (unsigned long)item,
2316 sizeof(struct btrfs_item),
2317 &leaf->map_token, &leaf->kaddr,
2318 &leaf->map_start, &leaf->map_len,
2319 KM_USER1);
2320 }
2190 ioff = btrfs_item_offset(leaf, item);
2191 btrfs_set_item_offset(leaf, item, ioff + dsize);
2192 }
2321 ioff = btrfs_item_offset(leaf, item);
2322 btrfs_set_item_offset(leaf, item, ioff + dsize);
2323 }
2324
2325 if (leaf->map_token) {
2326 unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
2327 leaf->map_token = NULL;
2328 }
2329
2193 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2194 btrfs_item_nr_offset(slot + 1),
2195 sizeof(struct btrfs_item) *
2196 (nritems - slot - 1));
2197 }
2198 btrfs_set_header_nritems(leaf, nritems - 1);
2199 nritems--;
2200
2201 /* delete the leaf if we've emptied it */
2202 if (nritems == 0) {
2203 if (leaf == root->node) {
2204 btrfs_set_header_level(leaf, 0);
2205 } else {
2206 clean_tree_block(trans, root, leaf);
2207 wait_on_tree_block_writeback(root, leaf);
2208 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2209 if (wret)
2210 ret = wret;
2211 wret = btrfs_free_extent(trans, root,
2330 memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
2331 btrfs_item_nr_offset(slot + 1),
2332 sizeof(struct btrfs_item) *
2333 (nritems - slot - 1));
2334 }
2335 btrfs_set_header_nritems(leaf, nritems - 1);
2336 nritems--;
2337
2338 /* delete the leaf if we've emptied it */
2339 if (nritems == 0) {
2340 if (leaf == root->node) {
2341 btrfs_set_header_level(leaf, 0);
2342 } else {
2343 clean_tree_block(trans, root, leaf);
2344 wait_on_tree_block_writeback(root, leaf);
2345 wret = del_ptr(trans, root, path, 1, path->slots[1]);
2346 if (wret)
2347 ret = wret;
2348 wret = btrfs_free_extent(trans, root,
2212 extent_buffer_blocknr(leaf),
2213 1, 1);
2349 leaf->start, leaf->len, 1);
2214 if (wret)
2215 ret = wret;
2216 }
2217 } else {
2218 int used = leaf_space_used(leaf, 0, nritems);
2219 if (slot == 0) {
2220 struct btrfs_disk_key disk_key;
2221

--- 20 unchanged lines hidden (view full) ---

2242 if (path->nodes[0] == leaf &&
2243 btrfs_header_nritems(leaf)) {
2244 wret = push_leaf_right(trans, root, path, 1);
2245 if (wret < 0 && wret != -ENOSPC)
2246 ret = wret;
2247 }
2248
2249 if (btrfs_header_nritems(leaf) == 0) {
2350 if (wret)
2351 ret = wret;
2352 }
2353 } else {
2354 int used = leaf_space_used(leaf, 0, nritems);
2355 if (slot == 0) {
2356 struct btrfs_disk_key disk_key;
2357

--- 20 unchanged lines hidden (view full) ---

2378 if (path->nodes[0] == leaf &&
2379 btrfs_header_nritems(leaf)) {
2380 wret = push_leaf_right(trans, root, path, 1);
2381 if (wret < 0 && wret != -ENOSPC)
2382 ret = wret;
2383 }
2384
2385 if (btrfs_header_nritems(leaf) == 0) {
2250 u64 blocknr = extent_buffer_blocknr(leaf);
2386 u64 bytenr = leaf->start;
2387 u32 blocksize = leaf->len;
2251
2252 clean_tree_block(trans, root, leaf);
2253 wait_on_tree_block_writeback(root, leaf);
2254
2255 wret = del_ptr(trans, root, path, 1, slot);
2256 if (wret)
2257 ret = wret;
2258
2259 free_extent_buffer(leaf);
2388
2389 clean_tree_block(trans, root, leaf);
2390 wait_on_tree_block_writeback(root, leaf);
2391
2392 wret = del_ptr(trans, root, path, 1, slot);
2393 if (wret)
2394 ret = wret;
2395
2396 free_extent_buffer(leaf);
2260 wret = btrfs_free_extent(trans, root, blocknr,
2261 1, 1);
2397 wret = btrfs_free_extent(trans, root, bytenr,
2398 blocksize, 1);
2262 if (wret)
2263 ret = wret;
2264 } else {
2265 btrfs_mark_buffer_dirty(leaf);
2266 free_extent_buffer(leaf);
2267 }
2268 } else {
2269 btrfs_mark_buffer_dirty(leaf);

--- 6 unchanged lines hidden (view full) ---

2276 * walk up the tree as far as required to find the next leaf.
2277 * returns 0 if it found something or 1 if there are no greater leaves.
2278 * returns < 0 on io errors.
2279 */
2280int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2281{
2282 int slot;
2283 int level = 1;
2399 if (wret)
2400 ret = wret;
2401 } else {
2402 btrfs_mark_buffer_dirty(leaf);
2403 free_extent_buffer(leaf);
2404 }
2405 } else {
2406 btrfs_mark_buffer_dirty(leaf);

--- 6 unchanged lines hidden (view full) ---

2413 * walk up the tree as far as required to find the next leaf.
2414 * returns 0 if it found something or 1 if there are no greater leaves.
2415 * returns < 0 on io errors.
2416 */
2417int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
2418{
2419 int slot;
2420 int level = 1;
2284 u64 blocknr;
2421 u64 bytenr;
2285 struct extent_buffer *c;
2286 struct extent_buffer *next = NULL;
2287
2288 while(level < BTRFS_MAX_LEVEL) {
2289 if (!path->nodes[level])
2290 return 1;
2291
2292 slot = path->slots[level] + 1;
2293 c = path->nodes[level];
2294 if (slot >= btrfs_header_nritems(c)) {
2295 level++;
2296 continue;
2297 }
2298
2422 struct extent_buffer *c;
2423 struct extent_buffer *next = NULL;
2424
2425 while(level < BTRFS_MAX_LEVEL) {
2426 if (!path->nodes[level])
2427 return 1;
2428
2429 slot = path->slots[level] + 1;
2430 c = path->nodes[level];
2431 if (slot >= btrfs_header_nritems(c)) {
2432 level++;
2433 continue;
2434 }
2435
2299 blocknr = btrfs_node_blockptr(c, slot);
2436 bytenr = btrfs_node_blockptr(c, slot);
2300 if (next)
2301 free_extent_buffer(next);
2302
2303 if (path->reada)
2304 reada_for_search(root, path, level, slot);
2305
2437 if (next)
2438 free_extent_buffer(next);
2439
2440 if (path->reada)
2441 reada_for_search(root, path, level, slot);
2442
2306 next = read_tree_block(root, blocknr);
2443 next = read_tree_block(root, bytenr,
2444 btrfs_level_size(root, level -1));
2307 break;
2308 }
2309 path->slots[level] = slot;
2310 while(1) {
2311 level--;
2312 c = path->nodes[level];
2313 free_extent_buffer(c);
2314 path->nodes[level] = next;
2315 path->slots[level] = 0;
2316 if (!level)
2317 break;
2318 if (path->reada)
2319 reada_for_search(root, path, level, 0);
2445 break;
2446 }
2447 path->slots[level] = slot;
2448 while(1) {
2449 level--;
2450 c = path->nodes[level];
2451 free_extent_buffer(c);
2452 path->nodes[level] = next;
2453 path->slots[level] = 0;
2454 if (!level)
2455 break;
2456 if (path->reada)
2457 reada_for_search(root, path, level, 0);
2320 next = read_tree_block(root, btrfs_node_blockptr(next, 0));
2458 next = read_tree_block(root, btrfs_node_blockptr(next, 0),
2459 btrfs_level_size(root, level - 1));
2321 }
2322 return 0;
2323}
2460 }
2461 return 0;
2462}