diff options
-rw-r--r-- | fs/btrfs/ctree.c | 245 | ||||
-rw-r--r-- | fs/btrfs/ctree.h | 13 | ||||
-rw-r--r-- | fs/btrfs/disk-io.c | 90 | ||||
-rw-r--r-- | fs/btrfs/disk-io.h | 2 | ||||
-rw-r--r-- | fs/btrfs/mkfs.c | 37 |
5 files changed, 252 insertions, 135 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c index 1b4e82d8074d..f0abcf1f3939 100644 --- a/fs/btrfs/ctree.c +++ b/fs/btrfs/ctree.c | |||
@@ -8,9 +8,12 @@ | |||
8 | #define SEARCH_READ 0 | 8 | #define SEARCH_READ 0 |
9 | #define SEARCH_WRITE 1 | 9 | #define SEARCH_WRITE 1 |
10 | 10 | ||
11 | static int refill_alloc_extent(struct ctree_root *root); | 11 | #define CTREE_EXTENT_PENDING 0 |
12 | |||
12 | int split_node(struct ctree_root *root, struct ctree_path *path, int level); | 13 | int split_node(struct ctree_root *root, struct ctree_path *path, int level); |
13 | int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size); | 14 | int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size); |
15 | struct tree_buffer *alloc_free_block(struct ctree_root *root); | ||
16 | int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks); | ||
14 | 17 | ||
15 | static inline void init_path(struct ctree_path *p) | 18 | static inline void init_path(struct ctree_path *p) |
16 | { | 19 | { |
@@ -682,8 +685,6 @@ int insert_item(struct ctree_root *root, struct key *key, | |||
682 | unsigned int data_end; | 685 | unsigned int data_end; |
683 | struct ctree_path path; | 686 | struct ctree_path path; |
684 | 687 | ||
685 | refill_alloc_extent(root); | ||
686 | |||
687 | /* create a root if there isn't one */ | 688 | /* create a root if there isn't one */ |
688 | if (!root->node) | 689 | if (!root->node) |
689 | BUG(); | 690 | BUG(); |
@@ -756,6 +757,7 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | |||
756 | struct tree_buffer *t; | 757 | struct tree_buffer *t; |
757 | struct node *node; | 758 | struct node *node; |
758 | int nritems; | 759 | int nritems; |
760 | u64 blocknr; | ||
759 | 761 | ||
760 | while(1) { | 762 | while(1) { |
761 | t = path->nodes[level]; | 763 | t = path->nodes[level]; |
@@ -774,6 +776,7 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | |||
774 | } | 776 | } |
775 | node->header.nritems--; | 777 | node->header.nritems--; |
776 | write_tree_block(root, t); | 778 | write_tree_block(root, t); |
779 | blocknr = t->blocknr; | ||
777 | if (node->header.nritems != 0) { | 780 | if (node->header.nritems != 0) { |
778 | int tslot; | 781 | int tslot; |
779 | if (slot == 0) | 782 | if (slot == 0) |
@@ -799,6 +802,7 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | |||
799 | break; | 802 | break; |
800 | } | 803 | } |
801 | level++; | 804 | level++; |
805 | free_extent(root, blocknr, 1); | ||
802 | if (!path->nodes[level]) | 806 | if (!path->nodes[level]) |
803 | BUG(); | 807 | BUG(); |
804 | } | 808 | } |
@@ -841,8 +845,10 @@ int del_item(struct ctree_root *root, struct ctree_path *path) | |||
841 | if (leaf_buf == root->node) { | 845 | if (leaf_buf == root->node) { |
842 | leaf->header.flags = node_level(0); | 846 | leaf->header.flags = node_level(0); |
843 | write_tree_block(root, leaf_buf); | 847 | write_tree_block(root, leaf_buf); |
844 | } else | 848 | } else { |
845 | del_ptr(root, path, 1); | 849 | del_ptr(root, path, 1); |
850 | free_extent(root, leaf_buf->blocknr, 1); | ||
851 | } | ||
846 | } else { | 852 | } else { |
847 | if (slot == 0) | 853 | if (slot == 0) |
848 | fixup_low_keys(root, path, &leaf->items[0].key, 1); | 854 | fixup_low_keys(root, path, &leaf->items[0].key, 1); |
@@ -867,6 +873,72 @@ int del_item(struct ctree_root *root, struct ctree_path *path) | |||
867 | return 0; | 873 | return 0; |
868 | } | 874 | } |
869 | 875 | ||
876 | static int del_pending_extents(struct ctree_root *extent_root) | ||
877 | { | ||
878 | int ret; | ||
879 | struct key key; | ||
880 | struct tree_buffer *gang[4]; | ||
881 | int i; | ||
882 | struct ctree_path path; | ||
883 | |||
884 | while(1) { | ||
885 | ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix, | ||
886 | (void **)gang, 0, ARRAY_SIZE(gang), | ||
887 | CTREE_EXTENT_PENDING); | ||
888 | if (!ret) | ||
889 | break; | ||
890 | for (i = 0; i < ret; i++) { | ||
891 | key.objectid = gang[i]->blocknr; | ||
892 | key.flags = 0; | ||
893 | key.offset = 1; | ||
894 | init_path(&path); | ||
895 | ret = search_slot(extent_root, &key, &path, 0); | ||
896 | if (ret) { | ||
897 | BUG(); | ||
898 | // FIXME undo it and return sane | ||
899 | return ret; | ||
900 | } | ||
901 | ret = del_item(extent_root, &path); | ||
902 | if (ret) { | ||
903 | BUG(); | ||
904 | return ret; | ||
905 | } | ||
906 | release_path(extent_root, &path); | ||
907 | radix_tree_tag_clear(&extent_root->cache_radix, gang[i]->blocknr, | ||
908 | CTREE_EXTENT_PENDING); | ||
909 | tree_block_release(extent_root, gang[i]); | ||
910 | } | ||
911 | } | ||
912 | return 0; | ||
913 | } | ||
914 | |||
915 | int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks) | ||
916 | { | ||
917 | struct ctree_path path; | ||
918 | struct key key; | ||
919 | struct ctree_root *extent_root = root->extent_root; | ||
920 | struct tree_buffer *t; | ||
921 | int pending_ret; | ||
922 | int ret; | ||
923 | |||
924 | key.objectid = blocknr; | ||
925 | key.flags = 0; | ||
926 | key.offset = num_blocks; | ||
927 | if (root == extent_root) { | ||
928 | t = read_tree_block(root, key.objectid); | ||
929 | radix_tree_tag_set(&root->cache_radix, key.objectid, CTREE_EXTENT_PENDING); | ||
930 | return 0; | ||
931 | } | ||
932 | init_path(&path); | ||
933 | ret = search_slot(extent_root, &key, &path, 0); | ||
934 | if (ret) | ||
935 | BUG(); | ||
936 | ret = del_item(extent_root, &path); | ||
937 | release_path(extent_root, &path); | ||
938 | pending_ret = del_pending_extents(root->extent_root); | ||
939 | return ret ? ret : pending_ret; | ||
940 | } | ||
941 | |||
870 | int next_leaf(struct ctree_root *root, struct ctree_path *path) | 942 | int next_leaf(struct ctree_root *root, struct ctree_path *path) |
871 | { | 943 | { |
872 | int slot; | 944 | int slot; |
@@ -904,8 +976,8 @@ int next_leaf(struct ctree_root *root, struct ctree_path *path) | |||
904 | return 0; | 976 | return 0; |
905 | } | 977 | } |
906 | 978 | ||
907 | int alloc_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, | 979 | int find_free_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, |
908 | u64 search_end, u64 owner, struct key *ins) | 980 | u64 search_end, struct key *ins) |
909 | { | 981 | { |
910 | struct ctree_path path; | 982 | struct ctree_path path; |
911 | struct key *key; | 983 | struct key *key; |
@@ -915,15 +987,13 @@ int alloc_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, | |||
915 | u64 last_block; | 987 | u64 last_block; |
916 | int start_found = 0; | 988 | int start_found = 0; |
917 | struct leaf *l; | 989 | struct leaf *l; |
918 | struct extent_item extent_item; | ||
919 | struct ctree_root * root = orig_root->extent_root; | 990 | struct ctree_root * root = orig_root->extent_root; |
920 | 991 | ||
921 | init_path(&path); | 992 | init_path(&path); |
922 | ins->objectid = search_start; | 993 | ins->objectid = search_start; |
923 | ins->offset = 0; | 994 | ins->offset = 0; |
924 | ins->flags = 0; | 995 | ins->flags = 0; |
925 | 996 | ret = search_slot(root, ins, &path, 0); | |
926 | ret = search_slot(root, ins, &path, sizeof(struct extent_item)); | ||
927 | while (1) { | 997 | while (1) { |
928 | l = &path.nodes[0]->leaf; | 998 | l = &path.nodes[0]->leaf; |
929 | slot = path.slots[0]; | 999 | slot = path.slots[0]; |
@@ -938,6 +1008,7 @@ int alloc_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, | |||
938 | ins->objectid = search_start; | 1008 | ins->objectid = search_start; |
939 | ins->offset = num_blocks; | 1009 | ins->offset = num_blocks; |
940 | hole_size = search_end - search_start; | 1010 | hole_size = search_end - search_start; |
1011 | start_found = 1; | ||
941 | goto insert; | 1012 | goto insert; |
942 | } | 1013 | } |
943 | ins->objectid = last_block; | 1014 | ins->objectid = last_block; |
@@ -956,51 +1027,119 @@ int alloc_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start, | |||
956 | } else | 1027 | } else |
957 | start_found = 1; | 1028 | start_found = 1; |
958 | last_block = key->objectid + key->offset; | 1029 | last_block = key->objectid + key->offset; |
1030 | insert_failed: | ||
959 | path.slots[0]++; | 1031 | path.slots[0]++; |
960 | } | 1032 | } |
961 | // FIXME -ENOSPC | 1033 | // FIXME -ENOSPC |
962 | insert: | 1034 | insert: |
1035 | if (orig_root->extent_root == orig_root) { | ||
1036 | BUG_ON(num_blocks != 1); | ||
1037 | if ((root->current_insert.objectid <= ins->objectid && | ||
1038 | root->current_insert.objectid + root->current_insert.offset > | ||
1039 | ins->objectid) || | ||
1040 | (root->current_insert.objectid > ins->objectid && | ||
1041 | root->current_insert.objectid <= ins->objectid + ins->offset) || | ||
1042 | radix_tree_tag_get(&root->cache_radix, ins->objectid, | ||
1043 | CTREE_EXTENT_PENDING)) { | ||
1044 | last_block = ins->objectid + 1; | ||
1045 | search_start = last_block; | ||
1046 | goto insert_failed; | ||
1047 | } | ||
1048 | } | ||
963 | release_path(root, &path); | 1049 | release_path(root, &path); |
1050 | if (ins->offset != 1) | ||
1051 | BUG(); | ||
1052 | return 0; | ||
1053 | } | ||
1054 | |||
1055 | static int insert_pending_extents(struct ctree_root *extent_root) | ||
1056 | { | ||
1057 | int ret; | ||
1058 | struct key key; | ||
1059 | struct extent_item item; | ||
1060 | struct tree_buffer *gang[4]; | ||
1061 | int i; | ||
1062 | |||
1063 | // FIXME -ENOSPC | ||
1064 | item.refs = 1; | ||
1065 | item.owner = extent_root->node->node.header.parentid; | ||
1066 | while(1) { | ||
1067 | ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix, | ||
1068 | (void **)gang, 0, ARRAY_SIZE(gang), | ||
1069 | CTREE_EXTENT_PENDING); | ||
1070 | if (!ret) | ||
1071 | break; | ||
1072 | for (i = 0; i < ret; i++) { | ||
1073 | key.objectid = gang[i]->blocknr; | ||
1074 | key.flags = 0; | ||
1075 | key.offset = 1; | ||
1076 | ret = insert_item(extent_root, &key, &item, sizeof(item)); | ||
1077 | if (ret) { | ||
1078 | BUG(); | ||
1079 | // FIXME undo it and return sane | ||
1080 | return ret; | ||
1081 | } | ||
1082 | radix_tree_tag_clear(&extent_root->cache_radix, gang[i]->blocknr, | ||
1083 | CTREE_EXTENT_PENDING); | ||
1084 | tree_block_release(extent_root, gang[i]); | ||
1085 | } | ||
1086 | } | ||
1087 | return 0; | ||
1088 | } | ||
1089 | |||
1090 | int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start, | ||
1091 | u64 search_end, u64 owner, struct key *ins, struct tree_buffer **buf) | ||
1092 | { | ||
1093 | int ret; | ||
1094 | int pending_ret; | ||
1095 | struct extent_item extent_item; | ||
1096 | |||
964 | extent_item.refs = 1; | 1097 | extent_item.refs = 1; |
965 | extent_item.owner = owner; | 1098 | extent_item.owner = owner; |
966 | if (root == orig_root && root->reserve_extent->num_blocks == 0) { | 1099 | |
967 | root->reserve_extent->blocknr = ins->objectid; | 1100 | ret = find_free_extent(root, num_blocks, search_start, search_end, ins); |
968 | root->reserve_extent->num_blocks = ins->offset; | 1101 | if (ret) |
969 | root->reserve_extent->num_used = 0; | 1102 | return ret; |
1103 | |||
1104 | if (root != root->extent_root) { | ||
1105 | memcpy(&root->extent_root->current_insert, ins, sizeof(*ins)); | ||
1106 | ret = insert_item(root->extent_root, ins, &extent_item, sizeof(extent_item)); | ||
1107 | memset(&root->extent_root->current_insert, 0, sizeof(struct key)); | ||
1108 | pending_ret = insert_pending_extents(root->extent_root); | ||
1109 | if (ret) | ||
1110 | return ret; | ||
1111 | if (pending_ret) | ||
1112 | return pending_ret; | ||
1113 | *buf = find_tree_block(root, ins->objectid); | ||
1114 | return 0; | ||
970 | } | 1115 | } |
971 | ret = insert_item(root->extent_root, ins, &extent_item, sizeof(extent_item)); | 1116 | /* we're allocating an extent for the extent tree, don't recurse */ |
972 | return ret; | 1117 | BUG_ON(ins->offset != 1); |
1118 | *buf = find_tree_block(root, ins->objectid); | ||
1119 | BUG_ON(!*buf); | ||
1120 | radix_tree_tag_set(&root->cache_radix, ins->objectid, CTREE_EXTENT_PENDING); | ||
1121 | (*buf)->count++; | ||
1122 | return 0; | ||
1123 | |||
973 | } | 1124 | } |
974 | 1125 | ||
975 | static int refill_alloc_extent(struct ctree_root *root) | 1126 | struct tree_buffer *alloc_free_block(struct ctree_root *root) |
976 | { | 1127 | { |
977 | struct alloc_extent *ae = root->alloc_extent; | 1128 | struct key ins; |
978 | struct key key; | ||
979 | int ret; | 1129 | int ret; |
980 | int min_blocks = MAX_LEVEL * 2; | 1130 | struct tree_buffer *buf = NULL; |
981 | 1131 | ||
982 | if (ae->num_blocks > ae->num_used && ae->num_blocks - ae->num_used > | 1132 | ret = alloc_extent(root, 1, 0, (unsigned long)-1, root->node->node.header.parentid, |
983 | min_blocks) | 1133 | &ins, &buf); |
984 | return 0; | 1134 | |
985 | ae = root->reserve_extent; | 1135 | if (ret) { |
986 | if (ae->num_blocks > ae->num_used) { | 1136 | BUG(); |
987 | if (root->alloc_extent->num_blocks == 0) { | 1137 | return NULL; |
988 | /* we should swap reserve/alloc_extent when alloc | ||
989 | * fills up | ||
990 | */ | ||
991 | BUG(); | ||
992 | } | ||
993 | if (ae->num_blocks - ae->num_used < min_blocks) | ||
994 | BUG(); | ||
995 | return 0; | ||
996 | } | 1138 | } |
997 | ret = alloc_extent(root, | 1139 | if (root != root->extent_root) |
998 | min_blocks * 2, 0, (unsigned long)-1, | 1140 | BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix, buf->blocknr, |
999 | root->node->node.header.parentid, &key); | 1141 | CTREE_EXTENT_PENDING)); |
1000 | ae->blocknr = key.objectid; | 1142 | return buf; |
1001 | ae->num_blocks = key.offset; | ||
1002 | ae->num_used = 0; | ||
1003 | return ret; | ||
1004 | } | 1143 | } |
1005 | 1144 | ||
1006 | void print_leaf(struct leaf *l) | 1145 | void print_leaf(struct leaf *l) |
@@ -1096,6 +1235,7 @@ int main() { | |||
1096 | print_tree(root, root->node); | 1235 | print_tree(root, root->node); |
1097 | printf("map tree\n"); | 1236 | printf("map tree\n"); |
1098 | print_tree(root->extent_root, root->extent_root->node); | 1237 | print_tree(root->extent_root, root->extent_root->node); |
1238 | fflush(stdout); | ||
1099 | 1239 | ||
1100 | srand(55); | 1240 | srand(55); |
1101 | for (i = 0; i < run_size; i++) { | 1241 | for (i = 0; i < run_size; i++) { |
@@ -1111,12 +1251,6 @@ int main() { | |||
1111 | if (!ret) | 1251 | if (!ret) |
1112 | tree_size++; | 1252 | tree_size++; |
1113 | } | 1253 | } |
1114 | printf("root used: %lu\n", root->alloc_extent->num_used); | ||
1115 | printf("root tree\n"); | ||
1116 | // print_tree(root, root->node); | ||
1117 | printf("map tree\n"); | ||
1118 | printf("map used: %lu\n", root->extent_root->alloc_extent->num_used); | ||
1119 | // print_tree(root->extent_root, root->extent_root->node); | ||
1120 | write_ctree_super(root, &super); | 1254 | write_ctree_super(root, &super); |
1121 | close_ctree(root); | 1255 | close_ctree(root); |
1122 | 1256 | ||
@@ -1167,12 +1301,27 @@ int main() { | |||
1167 | ret = insert_item(root, &ins, buf, strlen(buf)); | 1301 | ret = insert_item(root, &ins, buf, strlen(buf)); |
1168 | if (!ret) | 1302 | if (!ret) |
1169 | tree_size++; | 1303 | tree_size++; |
1304 | if (i >= 5) { | ||
1305 | struct key ugh; | ||
1306 | ugh.objectid = 5; | ||
1307 | ugh.flags = 0; | ||
1308 | ugh.offset = 0; | ||
1309 | init_path(&path); | ||
1310 | ret = search_slot(root, &ugh, &path, 0); | ||
1311 | if (ret) { | ||
1312 | print_tree(root, root->node); | ||
1313 | printf("unable to find 5 %d\n", num); | ||
1314 | exit(1); | ||
1315 | } | ||
1316 | release_path(root, &path); | ||
1317 | |||
1318 | } | ||
1170 | } | 1319 | } |
1171 | write_ctree_super(root, &super); | 1320 | write_ctree_super(root, &super); |
1172 | close_ctree(root); | 1321 | close_ctree(root); |
1173 | root = open_ctree("dbfile", &super); | 1322 | root = open_ctree("dbfile", &super); |
1174 | printf("starting search2\n"); | ||
1175 | srand(128); | 1323 | srand(128); |
1324 | printf("starting search2\n"); | ||
1176 | for (i = 0; i < run_size; i++) { | 1325 | for (i = 0; i < run_size; i++) { |
1177 | num = next_key(i, max_key); | 1326 | num = next_key(i, max_key); |
1178 | ins.objectid = num; | 1327 | ins.objectid = num; |
@@ -1219,5 +1368,7 @@ int main() { | |||
1219 | write_ctree_super(root, &super); | 1368 | write_ctree_super(root, &super); |
1220 | close_ctree(root); | 1369 | close_ctree(root); |
1221 | printf("tree size is now %d\n", tree_size); | 1370 | printf("tree size is now %d\n", tree_size); |
1371 | printf("map tree\n"); | ||
1372 | print_tree(root->extent_root, root->extent_root->node); | ||
1222 | return 0; | 1373 | return 0; |
1223 | } | 1374 | } |
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index 78407d32db78..8c32c0e9267d 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h | |||
@@ -28,21 +28,12 @@ struct header { | |||
28 | 28 | ||
29 | struct tree_buffer; | 29 | struct tree_buffer; |
30 | 30 | ||
31 | struct alloc_extent { | ||
32 | u64 blocknr; | ||
33 | u64 num_blocks; | ||
34 | u64 num_used; | ||
35 | } __attribute__ ((__packed__)); | ||
36 | |||
37 | struct ctree_root { | 31 | struct ctree_root { |
38 | struct tree_buffer *node; | 32 | struct tree_buffer *node; |
39 | struct ctree_root *extent_root; | 33 | struct ctree_root *extent_root; |
40 | struct alloc_extent *alloc_extent; | 34 | struct key current_insert; |
41 | struct alloc_extent *reserve_extent; | ||
42 | int fp; | 35 | int fp; |
43 | struct radix_tree_root cache_radix; | 36 | struct radix_tree_root cache_radix; |
44 | struct alloc_extent ai1; | ||
45 | struct alloc_extent ai2; | ||
46 | }; | 37 | }; |
47 | 38 | ||
48 | struct ctree_root_info { | 39 | struct ctree_root_info { |
@@ -52,8 +43,6 @@ struct ctree_root_info { | |||
52 | u64 tree_root; /* the tree root */ | 43 | u64 tree_root; /* the tree root */ |
53 | u32 csum; | 44 | u32 csum; |
54 | u32 ham; | 45 | u32 ham; |
55 | struct alloc_extent alloc_extent; | ||
56 | struct alloc_extent reserve_extent; | ||
57 | u64 snapuuid[2]; /* root specific uuid */ | 46 | u64 snapuuid[2]; /* root specific uuid */ |
58 | } __attribute__ ((__packed__)); | 47 | } __attribute__ ((__packed__)); |
59 | 48 | ||
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c index a696a4278ac5..14955e440773 100644 --- a/fs/btrfs/disk-io.c +++ b/fs/btrfs/disk-io.c | |||
@@ -12,33 +12,13 @@ | |||
12 | 12 | ||
13 | static int allocated_blocks = 0; | 13 | static int allocated_blocks = 0; |
14 | 14 | ||
15 | static int get_free_block(struct ctree_root *root, u64 *block) | 15 | static int check_tree_block(struct ctree_root *root, struct tree_buffer *buf) |
16 | { | 16 | { |
17 | struct stat st; | 17 | if (buf->blocknr != buf->node.header.blocknr) |
18 | int ret = 0; | 18 | BUG(); |
19 | 19 | if (root->node && buf->node.header.parentid != root->node->node.header.parentid) | |
20 | if (root->alloc_extent->num_used >= root->alloc_extent->num_blocks) | 20 | BUG(); |
21 | return -1; | 21 | return 0; |
22 | |||
23 | *block = root->alloc_extent->blocknr + root->alloc_extent->num_used; | ||
24 | root->alloc_extent->num_used += 1; | ||
25 | if (root->alloc_extent->num_used >= root->alloc_extent->num_blocks) { | ||
26 | struct alloc_extent *ae = root->alloc_extent; | ||
27 | root->alloc_extent = root->reserve_extent; | ||
28 | root->reserve_extent = ae; | ||
29 | ae->num_blocks = 0; | ||
30 | } | ||
31 | st.st_size = 0; | ||
32 | ret = fstat(root->fp, &st); | ||
33 | if (st.st_size < (*block + 1) * CTREE_BLOCKSIZE) { | ||
34 | ret = ftruncate(root->fp, | ||
35 | (*block + 1) * CTREE_BLOCKSIZE); | ||
36 | if (ret) { | ||
37 | perror("ftruncate"); | ||
38 | exit(1); | ||
39 | } | ||
40 | } | ||
41 | return ret; | ||
42 | } | 22 | } |
43 | 23 | ||
44 | struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) | 24 | struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) |
@@ -61,22 +41,23 @@ struct tree_buffer *alloc_tree_block(struct ctree_root *root, u64 blocknr) | |||
61 | return buf; | 41 | return buf; |
62 | } | 42 | } |
63 | 43 | ||
64 | struct tree_buffer *alloc_free_block(struct ctree_root *root) | 44 | struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr) |
65 | { | 45 | { |
66 | u64 free_block; | 46 | struct tree_buffer *buf; |
67 | int ret; | 47 | buf = radix_tree_lookup(&root->cache_radix, blocknr); |
68 | struct tree_buffer * buf; | 48 | if (buf) { |
69 | ret = get_free_block(root, &free_block); | 49 | buf->count++; |
70 | if (ret) { | 50 | } else { |
71 | BUG(); | 51 | buf = alloc_tree_block(root, blocknr); |
72 | return NULL; | 52 | if (!buf) { |
53 | BUG(); | ||
54 | return NULL; | ||
55 | } | ||
73 | } | 56 | } |
74 | buf = alloc_tree_block(root, free_block); | ||
75 | if (!buf) | ||
76 | BUG(); | ||
77 | return buf; | 57 | return buf; |
78 | } | 58 | } |
79 | 59 | ||
60 | |||
80 | struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) | 61 | struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) |
81 | { | 62 | { |
82 | loff_t offset = blocknr * CTREE_BLOCKSIZE; | 63 | loff_t offset = blocknr * CTREE_BLOCKSIZE; |
@@ -86,20 +67,17 @@ struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr) | |||
86 | buf = radix_tree_lookup(&root->cache_radix, blocknr); | 67 | buf = radix_tree_lookup(&root->cache_radix, blocknr); |
87 | if (buf) { | 68 | if (buf) { |
88 | buf->count++; | 69 | buf->count++; |
89 | goto test; | 70 | } else { |
90 | } | 71 | buf = alloc_tree_block(root, blocknr); |
91 | buf = alloc_tree_block(root, blocknr); | 72 | if (!buf) |
92 | if (!buf) | 73 | return NULL; |
93 | return NULL; | 74 | ret = pread(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); |
94 | ret = pread(root->fp, &buf->node, CTREE_BLOCKSIZE, offset); | 75 | if (ret != CTREE_BLOCKSIZE) { |
95 | if (ret != CTREE_BLOCKSIZE) { | 76 | free(buf); |
96 | free(buf); | 77 | return NULL; |
97 | return NULL; | 78 | } |
98 | } | 79 | } |
99 | test: | 80 | if (check_tree_block(root, buf)) |
100 | if (buf->blocknr != buf->node.header.blocknr) | ||
101 | BUG(); | ||
102 | if (root->node && buf->node.header.parentid != root->node->node.header.parentid) | ||
103 | BUG(); | 81 | BUG(); |
104 | return buf; | 82 | return buf; |
105 | } | 83 | } |
@@ -121,17 +99,10 @@ int write_tree_block(struct ctree_root *root, struct tree_buffer *buf) | |||
121 | static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root, | 99 | static int __setup_root(struct ctree_root *root, struct ctree_root *extent_root, |
122 | struct ctree_root_info *info, int fp) | 100 | struct ctree_root_info *info, int fp) |
123 | { | 101 | { |
124 | INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL); | ||
125 | root->fp = fp; | 102 | root->fp = fp; |
126 | root->node = NULL; | 103 | root->node = NULL; |
127 | root->node = read_tree_block(root, info->tree_root); | 104 | root->node = read_tree_block(root, info->tree_root); |
128 | root->extent_root = extent_root; | 105 | root->extent_root = extent_root; |
129 | memcpy(&root->ai1, &info->alloc_extent, sizeof(info->alloc_extent)); | ||
130 | memcpy(&root->ai2, &info->reserve_extent, sizeof(info->reserve_extent)); | ||
131 | root->alloc_extent = &root->ai1; | ||
132 | root->reserve_extent = &root->ai2; | ||
133 | printf("setup done reading root %p, used %lu available %lu\n", root, root->alloc_extent->num_used, root->alloc_extent->num_blocks); | ||
134 | printf("setup done reading root %p, reserve used %lu available %lu\n", root, root->reserve_extent->num_used, root->reserve_extent->num_blocks); | ||
135 | return 0; | 106 | return 0; |
136 | } | 107 | } |
137 | 108 | ||
@@ -147,6 +118,8 @@ struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super) | |||
147 | free(root); | 118 | free(root); |
148 | return NULL; | 119 | return NULL; |
149 | } | 120 | } |
121 | INIT_RADIX_TREE(&root->cache_radix, GFP_KERNEL); | ||
122 | INIT_RADIX_TREE(&extent_root->cache_radix, GFP_KERNEL); | ||
150 | ret = pread(fp, super, sizeof(struct ctree_super_block), | 123 | ret = pread(fp, super, sizeof(struct ctree_super_block), |
151 | CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); | 124 | CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); |
152 | if (ret == 0 || super->root_info.tree_root == 0) { | 125 | if (ret == 0 || super->root_info.tree_root == 0) { |
@@ -168,8 +141,6 @@ struct ctree_root *open_ctree(char *filename, struct ctree_super_block *super) | |||
168 | static int __update_root(struct ctree_root *root, struct ctree_root_info *info) | 141 | static int __update_root(struct ctree_root *root, struct ctree_root_info *info) |
169 | { | 142 | { |
170 | info->tree_root = root->node->blocknr; | 143 | info->tree_root = root->node->blocknr; |
171 | memcpy(&info->alloc_extent, root->alloc_extent, sizeof(struct alloc_extent)); | ||
172 | memcpy(&info->reserve_extent, root->reserve_extent, sizeof(struct alloc_extent)); | ||
173 | return 0; | 144 | return 0; |
174 | } | 145 | } |
175 | 146 | ||
@@ -201,6 +172,7 @@ int close_ctree(struct ctree_root *root) | |||
201 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf) | 172 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf) |
202 | { | 173 | { |
203 | buf->count--; | 174 | buf->count--; |
175 | write_tree_block(root, buf); | ||
204 | if (buf->count < 0) | 176 | if (buf->count < 0) |
205 | BUG(); | 177 | BUG(); |
206 | if (buf->count == 0) { | 178 | if (buf->count == 0) { |
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h index e288fe883b9a..2729b757ddc1 100644 --- a/fs/btrfs/disk-io.h +++ b/fs/btrfs/disk-io.h | |||
@@ -11,11 +11,11 @@ struct tree_buffer { | |||
11 | }; | 11 | }; |
12 | 12 | ||
13 | struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr); | 13 | struct tree_buffer *read_tree_block(struct ctree_root *root, u64 blocknr); |
14 | struct tree_buffer *find_tree_block(struct ctree_root *root, u64 blocknr); | ||
14 | int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); | 15 | int write_tree_block(struct ctree_root *root, struct tree_buffer *buf); |
15 | struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); | 16 | struct ctree_root *open_ctree(char *filename, struct ctree_super_block *s); |
16 | int close_ctree(struct ctree_root *root); | 17 | int close_ctree(struct ctree_root *root); |
17 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); | 18 | void tree_block_release(struct ctree_root *root, struct tree_buffer *buf); |
18 | struct tree_buffer *alloc_free_block(struct ctree_root *root); | ||
19 | int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s); | 19 | int write_ctree_super(struct ctree_root *root, struct ctree_super_block *s); |
20 | int mkfs(int fd); | 20 | int mkfs(int fd); |
21 | 21 | ||
diff --git a/fs/btrfs/mkfs.c b/fs/btrfs/mkfs.c index 584aba44e801..fd4e5dea7e1b 100644 --- a/fs/btrfs/mkfs.c +++ b/fs/btrfs/mkfs.c | |||
@@ -23,17 +23,10 @@ int mkfs(int fd) | |||
23 | info[0].blocknr = 16; | 23 | info[0].blocknr = 16; |
24 | info[0].objectid = 1; | 24 | info[0].objectid = 1; |
25 | info[0].tree_root = 17; | 25 | info[0].tree_root = 17; |
26 | info[0].alloc_extent.blocknr = 0; | ||
27 | info[0].alloc_extent.num_blocks = 64; | ||
28 | /* 0-17 are used (inclusive) */ | ||
29 | info[0].alloc_extent.num_used = 18; | ||
30 | 26 | ||
31 | info[1].blocknr = 16; | 27 | info[1].blocknr = 16; |
32 | info[1].objectid = 2; | 28 | info[1].objectid = 2; |
33 | info[1].tree_root = 64; | 29 | info[1].tree_root = 18; |
34 | info[1].alloc_extent.blocknr = 64; | ||
35 | info[1].alloc_extent.num_blocks = 64; | ||
36 | info[1].alloc_extent.num_used = 1; | ||
37 | ret = pwrite(fd, info, sizeof(info), | 30 | ret = pwrite(fd, info, sizeof(info), |
38 | CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); | 31 | CTREE_SUPER_INFO_OFFSET(CTREE_BLOCKSIZE)); |
39 | if (ret != sizeof(info)) | 32 | if (ret != sizeof(info)) |
@@ -48,24 +41,36 @@ int mkfs(int fd) | |||
48 | return -1; | 41 | return -1; |
49 | 42 | ||
50 | empty_leaf.header.parentid = 2; | 43 | empty_leaf.header.parentid = 2; |
51 | empty_leaf.header.blocknr = 64; | 44 | empty_leaf.header.blocknr = 18; |
52 | empty_leaf.header.nritems = 2; | 45 | empty_leaf.header.nritems = 3; |
46 | |||
47 | /* item1, reserve blocks 0-16 */ | ||
53 | item.key.objectid = 0; | 48 | item.key.objectid = 0; |
54 | item.key.offset = 64; | 49 | item.key.offset = 17; |
55 | item.key.flags = 0; | 50 | item.key.flags = 0; |
56 | item.offset = LEAF_DATA_SIZE - sizeof(struct extent_item); | 51 | item.offset = LEAF_DATA_SIZE - sizeof(struct extent_item); |
57 | item.size = sizeof(struct extent_item); | 52 | item.size = sizeof(struct extent_item); |
58 | extent_item.refs = 1; | 53 | extent_item.refs = 1; |
59 | extent_item.owner = 1; | 54 | extent_item.owner = 0; |
60 | memcpy(empty_leaf.items, &item, sizeof(item)); | 55 | memcpy(empty_leaf.items, &item, sizeof(item)); |
61 | memcpy(empty_leaf.data + item.offset, &extent_item, item.size); | 56 | memcpy(empty_leaf.data + item.offset, &extent_item, item.size); |
62 | item.key.objectid = 64; | 57 | |
63 | item.key.offset = 64; | 58 | /* item2, give block 17 to the root */ |
59 | item.key.objectid = 17; | ||
60 | item.key.offset = 1; | ||
64 | item.offset = LEAF_DATA_SIZE - sizeof(struct extent_item) * 2; | 61 | item.offset = LEAF_DATA_SIZE - sizeof(struct extent_item) * 2; |
65 | extent_item.owner = 2; | 62 | extent_item.owner = 1; |
66 | memcpy(empty_leaf.items + 1, &item, sizeof(item)); | 63 | memcpy(empty_leaf.items + 1, &item, sizeof(item)); |
67 | memcpy(empty_leaf.data + item.offset, &extent_item, item.size); | 64 | memcpy(empty_leaf.data + item.offset, &extent_item, item.size); |
68 | ret = pwrite(fd, &empty_leaf, sizeof(empty_leaf), 64 * CTREE_BLOCKSIZE); | 65 | |
66 | /* item3, give block 18 for the extent root */ | ||
67 | item.key.objectid = 18; | ||
68 | item.key.offset = 1; | ||
69 | item.offset = LEAF_DATA_SIZE - sizeof(struct extent_item) * 3; | ||
70 | extent_item.owner = 2; | ||
71 | memcpy(empty_leaf.items + 2, &item, sizeof(item)); | ||
72 | memcpy(empty_leaf.data + item.offset, &extent_item, item.size); | ||
73 | ret = pwrite(fd, &empty_leaf, sizeof(empty_leaf), 18 * CTREE_BLOCKSIZE); | ||
69 | if (ret != sizeof(empty_leaf)) | 74 | if (ret != sizeof(empty_leaf)) |
70 | return -1; | 75 | return -1; |
71 | return 0; | 76 | return 0; |