aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/btrfs/Makefile16
-rw-r--r--fs/btrfs/ctree.c446
-rw-r--r--fs/btrfs/ctree.h12
-rw-r--r--fs/btrfs/disk-io.c1
-rw-r--r--fs/btrfs/print-tree.c72
-rw-r--r--fs/btrfs/print-tree.h3
6 files changed, 176 insertions, 374 deletions
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index df065dd2dce7..fe73ab9d81d6 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -1,12 +1,16 @@
1 1
2CFLAGS= -g -Wall 2CFLAGS = -g -Wall
3headers = radix-tree.h ctree.h disk-io.h kerncompat.h print-tree.h
4objects = ctree.o disk-io.o radix-tree.o mkfs.o extent-tree.o print-tree.o
3 5
4.c.o: 6#.c.o:
5 $(CC) $(CFLAGS) -c $< 7# $(CC) $(CFLAGS) -c $<
6 8
7ctree: ctree.o disk-io.h ctree.h disk-io.o radix-tree.o radix-tree.h mkfs.o 9ctree : $(objects)
8 gcc $(CFLAGS) -o ctree ctree.o disk-io.o radix-tree.o mkfs.o 10 gcc $(CFLAGS) -o ctree $(objects)
9 11
10clean: 12$(objects) : $(headers)
13
14clean :
11 rm ctree *.o 15 rm ctree *.o
12 16
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index f0abcf1f3939..e497fd963118 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -4,23 +4,21 @@
4#include "radix-tree.h" 4#include "radix-tree.h"
5#include "ctree.h" 5#include "ctree.h"
6#include "disk-io.h" 6#include "disk-io.h"
7 7#include "print-tree.h"
8#define SEARCH_READ 0
9#define SEARCH_WRITE 1
10
11#define CTREE_EXTENT_PENDING 0
12 8
13int split_node(struct ctree_root *root, struct ctree_path *path, int level); 9int split_node(struct ctree_root *root, struct ctree_path *path, int level);
14int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size); 10int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size);
15struct tree_buffer *alloc_free_block(struct ctree_root *root); 11int push_node_left(struct ctree_root *root, struct ctree_path *path, int level);
16int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks); 12int push_node_right(struct ctree_root *root,
13 struct ctree_path *path, int level);
14int del_ptr(struct ctree_root *root, struct ctree_path *path, int level);
17 15
18static inline void init_path(struct ctree_path *p) 16inline void init_path(struct ctree_path *p)
19{ 17{
20 memset(p, 0, sizeof(*p)); 18 memset(p, 0, sizeof(*p));
21} 19}
22 20
23static void release_path(struct ctree_root *root, struct ctree_path *p) 21void release_path(struct ctree_root *root, struct ctree_path *p)
24{ 22{
25 int i; 23 int i;
26 for (i = 0; i < MAX_LEVEL; i++) { 24 for (i = 0; i < MAX_LEVEL; i++) {
@@ -48,7 +46,7 @@ static inline unsigned int leaf_data_end(struct leaf *leaf)
48 * the start of the leaf data. IOW, how much room 46 * the start of the leaf data. IOW, how much room
49 * the leaf has left for both items and data 47 * the leaf has left for both items and data
50 */ 48 */
51static inline int leaf_free_space(struct leaf *leaf) 49int leaf_free_space(struct leaf *leaf)
52{ 50{
53 int data_end = leaf_data_end(leaf); 51 int data_end = leaf_data_end(leaf);
54 int nritems = leaf->header.nritems; 52 int nritems = leaf->header.nritems;
@@ -133,7 +131,8 @@ int bin_search(struct node *c, struct key *key, int *slot)
133 * If the key isn't found, the path points to the slot where it should 131 * If the key isn't found, the path points to the slot where it should
134 * be inserted. 132 * be inserted.
135 */ 133 */
136int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p, int ins_len) 134int search_slot(struct ctree_root *root, struct key *key,
135 struct ctree_path *p, int ins_len)
137{ 136{
138 struct tree_buffer *b = root->node; 137 struct tree_buffer *b = root->node;
139 struct node *c; 138 struct node *c;
@@ -151,7 +150,8 @@ int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p,
151 if (ret && slot > 0) 150 if (ret && slot > 0)
152 slot -= 1; 151 slot -= 1;
153 p->slots[level] = slot; 152 p->slots[level] = slot;
154 if (ins_len && c->header.nritems == NODEPTRS_PER_BLOCK) { 153 if (ins_len > 0 &&
154 c->header.nritems == NODEPTRS_PER_BLOCK) {
155 int sret = split_node(root, p, level); 155 int sret = split_node(root, p, level);
156 BUG_ON(sret > 0); 156 BUG_ON(sret > 0);
157 if (sret) 157 if (sret)
@@ -159,13 +159,37 @@ int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p,
159 b = p->nodes[level]; 159 b = p->nodes[level];
160 c = &b->node; 160 c = &b->node;
161 slot = p->slots[level]; 161 slot = p->slots[level];
162 } else if (ins_len < 0 &&
163 c->header.nritems <= NODEPTRS_PER_BLOCK/4) {
164 u64 blocknr = b->blocknr;
165 slot = p->slots[level +1];
166 b->count++;
167 if (push_node_left(root, p, level))
168 push_node_right(root, p, level);
169 if (c->header.nritems == 0 &&
170 level < MAX_LEVEL - 1 &&
171 p->nodes[level + 1]) {
172 int tslot = p->slots[level + 1];
173
174 p->slots[level + 1] = slot;
175 del_ptr(root, p, level + 1);
176 p->slots[level + 1] = tslot;
177 tree_block_release(root, b);
178 free_extent(root, blocknr, 1);
179 } else {
180 tree_block_release(root, b);
181 }
182 b = p->nodes[level];
183 c = &b->node;
184 slot = p->slots[level];
162 } 185 }
163 b = read_tree_block(root, c->blockptrs[slot]); 186 b = read_tree_block(root, c->blockptrs[slot]);
164 continue; 187 continue;
165 } else { 188 } else {
166 struct leaf *l = (struct leaf *)c; 189 struct leaf *l = (struct leaf *)c;
167 p->slots[level] = slot; 190 p->slots[level] = slot;
168 if (ins_len && leaf_free_space(l) < sizeof(struct item) + ins_len) { 191 if (ins_len > 0 && leaf_free_space(l) <
192 sizeof(struct item) + ins_len) {
169 int sret = split_leaf(root, p, ins_len); 193 int sret = split_leaf(root, p, ins_len);
170 BUG_ON(sret > 0); 194 BUG_ON(sret > 0);
171 if (sret) 195 if (sret)
@@ -355,7 +379,8 @@ int push_node_right(struct ctree_root *root, struct ctree_path *path, int level)
355 return 0; 379 return 0;
356} 380}
357 381
358static int insert_new_root(struct ctree_root *root, struct ctree_path *path, int level) 382static int insert_new_root(struct ctree_root *root,
383 struct ctree_path *path, int level)
359{ 384{
360 struct tree_buffer *t; 385 struct tree_buffer *t;
361 struct node *lower; 386 struct node *lower;
@@ -463,7 +488,7 @@ int split_node(struct ctree_root *root, struct ctree_path *path, int level)
463 write_tree_block(root, split_buffer); 488 write_tree_block(root, split_buffer);
464 insert_ptr(root, path, split->keys, split_buffer->blocknr, 489 insert_ptr(root, path, split->keys, split_buffer->blocknr,
465 path->slots[level + 1] + 1, level + 1); 490 path->slots[level + 1] + 1, level + 1);
466 if (path->slots[level] > mid) { 491 if (path->slots[level] >= mid) {
467 path->slots[level] -= mid; 492 path->slots[level] -= mid;
468 tree_block_release(root, t); 493 tree_block_release(root, t);
469 path->nodes[level] = split_buffer; 494 path->nodes[level] = split_buffer;
@@ -744,8 +769,7 @@ int insert_item(struct ctree_root *root, struct key *key,
744} 769}
745 770
746/* 771/*
747 * delete the pointer from a given level in the path. The path is not 772 * delete the pointer from a given node.
748 * fixed up, so after calling this it is not valid at that level.
749 * 773 *
750 * If the delete empties a node, the node is removed from the tree, 774 * If the delete empties a node, the node is removed from the tree,
751 * continuing all the way the root if required. The root is converted into 775 * continuing all the way the root if required. The root is converted into
@@ -778,22 +802,10 @@ int del_ptr(struct ctree_root *root, struct ctree_path *path, int level)
778 write_tree_block(root, t); 802 write_tree_block(root, t);
779 blocknr = t->blocknr; 803 blocknr = t->blocknr;
780 if (node->header.nritems != 0) { 804 if (node->header.nritems != 0) {
781 int tslot;
782 if (slot == 0) 805 if (slot == 0)
783 fixup_low_keys(root, path, node->keys, 806 fixup_low_keys(root, path, node->keys,
784 level + 1); 807 level + 1);
785 tslot = path->slots[level+1]; 808 break;
786 t->count++;
787 push_node_left(root, path, level);
788 if (node->header.nritems) {
789 push_node_right(root, path, level);
790 }
791 if (node->header.nritems) {
792 tree_block_release(root, t);
793 break;
794 }
795 tree_block_release(root, t);
796 path->slots[level+1] = tslot;
797 } 809 }
798 if (t == root->node) { 810 if (t == root->node) {
799 /* just turn the root into a leaf and break */ 811 /* just turn the root into a leaf and break */
@@ -850,12 +862,12 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
850 free_extent(root, leaf_buf->blocknr, 1); 862 free_extent(root, leaf_buf->blocknr, 1);
851 } 863 }
852 } else { 864 } else {
865 int used = leaf_space_used(leaf, 0, leaf->header.nritems);
853 if (slot == 0) 866 if (slot == 0)
854 fixup_low_keys(root, path, &leaf->items[0].key, 1); 867 fixup_low_keys(root, path, &leaf->items[0].key, 1);
855 write_tree_block(root, leaf_buf); 868 write_tree_block(root, leaf_buf);
856 /* delete the leaf if it is mostly empty */ 869 /* delete the leaf if it is mostly empty */
857 if (leaf_space_used(leaf, 0, leaf->header.nritems) < 870 if (used < LEAF_DATA_SIZE / 3) {
858 LEAF_DATA_SIZE / 4) {
859 /* push_leaf_left fixes the path. 871 /* push_leaf_left fixes the path.
860 * make sure the path still points to our leaf 872 * make sure the path still points to our leaf
861 * for possible call to del_ptr below 873 * for possible call to del_ptr below
@@ -864,81 +876,19 @@ int del_item(struct ctree_root *root, struct ctree_path *path)
864 leaf_buf->count++; 876 leaf_buf->count++;
865 push_leaf_left(root, path, 1); 877 push_leaf_left(root, path, 1);
866 if (leaf->header.nritems == 0) { 878 if (leaf->header.nritems == 0) {
879 u64 blocknr = leaf_buf->blocknr;
867 path->slots[1] = slot; 880 path->slots[1] = slot;
868 del_ptr(root, path, 1); 881 del_ptr(root, path, 1);
882 tree_block_release(root, leaf_buf);
883 free_extent(root, blocknr, 1);
884 } else {
885 tree_block_release(root, leaf_buf);
869 } 886 }
870 tree_block_release(root, leaf_buf);
871 } 887 }
872 } 888 }
873 return 0; 889 return 0;
874} 890}
875 891
876static 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
915int 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
942int next_leaf(struct ctree_root *root, struct ctree_path *path) 892int next_leaf(struct ctree_root *root, struct ctree_path *path)
943{ 893{
944 int slot; 894 int slot;
@@ -976,241 +926,10 @@ int next_leaf(struct ctree_root *root, struct ctree_path *path)
976 return 0; 926 return 0;
977} 927}
978 928
979int find_free_extent(struct ctree_root *orig_root, u64 num_blocks, u64 search_start,
980 u64 search_end, struct key *ins)
981{
982 struct ctree_path path;
983 struct key *key;
984 int ret;
985 u64 hole_size = 0;
986 int slot = 0;
987 u64 last_block;
988 int start_found = 0;
989 struct leaf *l;
990 struct ctree_root * root = orig_root->extent_root;
991
992 init_path(&path);
993 ins->objectid = search_start;
994 ins->offset = 0;
995 ins->flags = 0;
996 ret = search_slot(root, ins, &path, 0);
997 while (1) {
998 l = &path.nodes[0]->leaf;
999 slot = path.slots[0];
1000 if (!l) {
1001 // FIXME allocate root
1002 }
1003 if (slot >= l->header.nritems) {
1004 ret = next_leaf(root, &path);
1005 if (ret == 0)
1006 continue;
1007 if (!start_found) {
1008 ins->objectid = search_start;
1009 ins->offset = num_blocks;
1010 hole_size = search_end - search_start;
1011 start_found = 1;
1012 goto insert;
1013 }
1014 ins->objectid = last_block;
1015 ins->offset = num_blocks;
1016 hole_size = search_end - last_block;
1017 goto insert;
1018 }
1019 key = &l->items[slot].key;
1020 if (start_found) {
1021 hole_size = key->objectid - last_block;
1022 if (hole_size > num_blocks) {
1023 ins->objectid = last_block;
1024 ins->offset = num_blocks;
1025 goto insert;
1026 }
1027 } else
1028 start_found = 1;
1029 last_block = key->objectid + key->offset;
1030insert_failed:
1031 path.slots[0]++;
1032 }
1033 // FIXME -ENOSPC
1034insert:
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 }
1049 release_path(root, &path);
1050 if (ins->offset != 1)
1051 BUG();
1052 return 0;
1053}
1054
1055static 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
1090int 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
1097 extent_item.refs = 1;
1098 extent_item.owner = owner;
1099
1100 ret = find_free_extent(root, num_blocks, search_start, search_end, ins);
1101 if (ret)
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;
1115 }
1116 /* we're allocating an extent for the extent tree, don't recurse */
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
1124}
1125
1126struct tree_buffer *alloc_free_block(struct ctree_root *root)
1127{
1128 struct key ins;
1129 int ret;
1130 struct tree_buffer *buf = NULL;
1131
1132 ret = alloc_extent(root, 1, 0, (unsigned long)-1, root->node->node.header.parentid,
1133 &ins, &buf);
1134
1135 if (ret) {
1136 BUG();
1137 return NULL;
1138 }
1139 if (root != root->extent_root)
1140 BUG_ON(radix_tree_tag_get(&root->extent_root->cache_radix, buf->blocknr,
1141 CTREE_EXTENT_PENDING));
1142 return buf;
1143}
1144
1145void print_leaf(struct leaf *l)
1146{
1147 int i;
1148 int nr = l->header.nritems;
1149 struct item *item;
1150 struct extent_item *ei;
1151 printf("leaf %lu total ptrs %d free space %d\n", l->header.blocknr, nr,
1152 leaf_free_space(l));
1153 fflush(stdout);
1154 for (i = 0 ; i < nr ; i++) {
1155 item = l->items + i;
1156 printf("\titem %d key (%lu %u %lu) itemoff %d itemsize %d\n",
1157 i,
1158 item->key.objectid, item->key.flags, item->key.offset,
1159 item->offset, item->size);
1160 fflush(stdout);
1161 printf("\t\titem data %.*s\n", item->size, l->data+item->offset);
1162 ei = (struct extent_item *)(l->data + item->offset);
1163 printf("\t\textent data %u %lu\n", ei->refs, ei->owner);
1164 fflush(stdout);
1165 }
1166}
1167void print_tree(struct ctree_root *root, struct tree_buffer *t)
1168{
1169 int i;
1170 int nr;
1171 struct node *c;
1172
1173 if (!t)
1174 return;
1175 c = &t->node;
1176 nr = c->header.nritems;
1177 if (c->header.blocknr != t->blocknr)
1178 BUG();
1179 if (is_leaf(c->header.flags)) {
1180 print_leaf((struct leaf *)c);
1181 return;
1182 }
1183 printf("node %lu level %d total ptrs %d free spc %lu\n", t->blocknr,
1184 node_level(c->header.flags), c->header.nritems,
1185 NODEPTRS_PER_BLOCK - c->header.nritems);
1186 fflush(stdout);
1187 for (i = 0; i < nr; i++) {
1188 printf("\tkey %d (%lu %u %lu) block %lu\n",
1189 i,
1190 c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset,
1191 c->blockptrs[i]);
1192 fflush(stdout);
1193 }
1194 for (i = 0; i < nr; i++) {
1195 struct tree_buffer *next_buf = read_tree_block(root,
1196 c->blockptrs[i]);
1197 struct node *next = &next_buf->node;
1198 if (is_leaf(next->header.flags) &&
1199 node_level(c->header.flags) != 1)
1200 BUG();
1201 if (node_level(next->header.flags) !=
1202 node_level(c->header.flags) - 1)
1203 BUG();
1204 print_tree(root, next_buf);
1205 tree_block_release(root, next_buf);
1206 }
1207
1208}
1209
1210/* for testing only */ 929/* for testing only */
1211int next_key(int i, int max_key) { 930int next_key(int i, int max_key) {
1212 // return rand() % max_key; 931 return rand() % max_key;
1213 return i; 932 // return i;
1214} 933}
1215 934
1216int main() { 935int main() {
@@ -1221,8 +940,8 @@ int main() {
1221 int i; 940 int i;
1222 int num; 941 int num;
1223 int ret; 942 int ret;
1224 int run_size = 10000; 943 int run_size = 20000000;
1225 int max_key = 100000000; 944 int max_key = 100000000;
1226 int tree_size = 0; 945 int tree_size = 0;
1227 struct ctree_path path; 946 struct ctree_path path;
1228 struct ctree_super_block super; 947 struct ctree_super_block super;
@@ -1231,11 +950,6 @@ int main() {
1231 950
1232 951
1233 root = open_ctree("dbfile", &super); 952 root = open_ctree("dbfile", &super);
1234 printf("root tree\n");
1235 print_tree(root, root->node);
1236 printf("map tree\n");
1237 print_tree(root->extent_root, root->extent_root->node);
1238 fflush(stdout);
1239 953
1240 srand(55); 954 srand(55);
1241 for (i = 0; i < run_size; i++) { 955 for (i = 0; i < run_size; i++) {
@@ -1243,13 +957,15 @@ int main() {
1243 num = next_key(i, max_key); 957 num = next_key(i, max_key);
1244 // num = i; 958 // num = i;
1245 sprintf(buf, "string-%d", num); 959 sprintf(buf, "string-%d", num);
1246 // printf("insert %d\n", num); 960 if (i % 10000 == 0)
961 printf("insert %d:%d\n", num, i);
1247 ins.objectid = num; 962 ins.objectid = num;
1248 ins.offset = 0; 963 ins.offset = 0;
1249 ins.flags = 0; 964 ins.flags = 0;
1250 ret = insert_item(root, &ins, buf, strlen(buf)); 965 ret = insert_item(root, &ins, buf, strlen(buf));
1251 if (!ret) 966 if (!ret)
1252 tree_size++; 967 tree_size++;
968 free(buf);
1253 } 969 }
1254 write_ctree_super(root, &super); 970 write_ctree_super(root, &super);
1255 close_ctree(root); 971 close_ctree(root);
@@ -1261,6 +977,8 @@ int main() {
1261 num = next_key(i, max_key); 977 num = next_key(i, max_key);
1262 ins.objectid = num; 978 ins.objectid = num;
1263 init_path(&path); 979 init_path(&path);
980 if (i % 10000 == 0)
981 printf("search %d:%d\n", num, i);
1264 ret = search_slot(root, &ins, &path, 0); 982 ret = search_slot(root, &ins, &path, 0);
1265 if (ret) { 983 if (ret) {
1266 print_tree(root, root->node); 984 print_tree(root, root->node);
@@ -1283,39 +1001,32 @@ int main() {
1283 num = next_key(i, max_key); 1001 num = next_key(i, max_key);
1284 ins.objectid = num; 1002 ins.objectid = num;
1285 init_path(&path); 1003 init_path(&path);
1286 ret = search_slot(root, &ins, &path, 0); 1004 ret = search_slot(root, &ins, &path, -1);
1287 if (ret) 1005 if (!ret) {
1288 continue; 1006 if (i % 10000 == 0)
1289 ret = del_item(root, &path); 1007 printf("del %d:%d\n", num, i);
1290 if (ret != 0) 1008 ret = del_item(root, &path);
1291 BUG(); 1009 if (ret != 0)
1010 BUG();
1011 tree_size--;
1012 }
1292 release_path(root, &path); 1013 release_path(root, &path);
1293 tree_size--;
1294 } 1014 }
1015 write_ctree_super(root, &super);
1016 close_ctree(root);
1017 root = open_ctree("dbfile", &super);
1295 srand(128); 1018 srand(128);
1296 for (i = 0; i < run_size; i++) { 1019 for (i = 0; i < run_size; i++) {
1297 buf = malloc(64); 1020 buf = malloc(64);
1298 num = next_key(i, max_key); 1021 num = next_key(i, max_key);
1299 sprintf(buf, "string-%d", num); 1022 sprintf(buf, "string-%d", num);
1300 ins.objectid = num; 1023 ins.objectid = num;
1024 if (i % 10000 == 0)
1025 printf("insert %d:%d\n", num, i);
1301 ret = insert_item(root, &ins, buf, strlen(buf)); 1026 ret = insert_item(root, &ins, buf, strlen(buf));
1302 if (!ret) 1027 if (!ret)
1303 tree_size++; 1028 tree_size++;
1304 if (i >= 5) { 1029 free(buf);
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 }
1319 } 1030 }
1320 write_ctree_super(root, &super); 1031 write_ctree_super(root, &super);
1321 close_ctree(root); 1032 close_ctree(root);
@@ -1326,6 +1037,8 @@ int main() {
1326 num = next_key(i, max_key); 1037 num = next_key(i, max_key);
1327 ins.objectid = num; 1038 ins.objectid = num;
1328 init_path(&path); 1039 init_path(&path);
1040 if (i % 10000 == 0)
1041 printf("search %d:%d\n", num, i);
1329 ret = search_slot(root, &ins, &path, 0); 1042 ret = search_slot(root, &ins, &path, 0);
1330 if (ret) { 1043 if (ret) {
1331 print_tree(root, root->node); 1044 print_tree(root, root->node);
@@ -1340,7 +1053,7 @@ int main() {
1340 int slot; 1053 int slot;
1341 ins.objectid = (u64)-1; 1054 ins.objectid = (u64)-1;
1342 init_path(&path); 1055 init_path(&path);
1343 ret = search_slot(root, &ins, &path, 0); 1056 ret = search_slot(root, &ins, &path, -1);
1344 if (ret == 0) 1057 if (ret == 0)
1345 BUG(); 1058 BUG();
1346 1059
@@ -1356,6 +1069,8 @@ int main() {
1356 if (comp_keys(&last, &leaf->items[slot].key) <= 0) 1069 if (comp_keys(&last, &leaf->items[slot].key) <= 0)
1357 BUG(); 1070 BUG();
1358 memcpy(&last, &leaf->items[slot].key, sizeof(last)); 1071 memcpy(&last, &leaf->items[slot].key, sizeof(last));
1072 if (tree_size % 10000 == 0)
1073 printf("big del %d:%d\n", tree_size, i);
1359 ret = del_item(root, &path); 1074 ret = del_item(root, &path);
1360 if (ret != 0) { 1075 if (ret != 0) {
1361 printf("del_item returned %d\n", ret); 1076 printf("del_item returned %d\n", ret);
@@ -1365,10 +1080,9 @@ int main() {
1365 } 1080 }
1366 release_path(root, &path); 1081 release_path(root, &path);
1367 } 1082 }
1368 write_ctree_super(root, &super);
1369 close_ctree(root);
1370 printf("tree size is now %d\n", tree_size); 1083 printf("tree size is now %d\n", tree_size);
1371 printf("map tree\n"); 1084 printf("map tree\n");
1372 print_tree(root->extent_root, root->extent_root->node); 1085 write_ctree_super(root, &super);
1086 close_ctree(root);
1373 return 0; 1087 return 0;
1374} 1088}
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 8c32c0e9267d..b92fbbb5ecd7 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1,7 +1,7 @@
1#ifndef __CTREE__ 1#ifndef __CTREE__
2#define __CTREE__ 2#define __CTREE__
3 3
4#define CTREE_BLOCKSIZE 256 4#define CTREE_BLOCKSIZE 4096
5 5
6struct key { 6struct key {
7 u64 objectid; 7 u64 objectid;
@@ -81,4 +81,14 @@ struct ctree_path {
81 struct tree_buffer *nodes[MAX_LEVEL]; 81 struct tree_buffer *nodes[MAX_LEVEL];
82 int slots[MAX_LEVEL]; 82 int slots[MAX_LEVEL];
83}; 83};
84
85struct tree_buffer *alloc_free_block(struct ctree_root *root);
86int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks);
87int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p, int ins_len);
88void release_path(struct ctree_root *root, struct ctree_path *p);
89void init_path(struct ctree_path *p);
90int del_item(struct ctree_root *root, struct ctree_path *path);
91int insert_item(struct ctree_root *root, struct key *key, void *data, int data_size);
92int next_leaf(struct ctree_root *root, struct ctree_path *path);
93int leaf_free_space(struct leaf *leaf);
84#endif 94#endif
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 14955e440773..f4c6ff202ba9 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -172,7 +172,6 @@ int close_ctree(struct ctree_root *root)
172void tree_block_release(struct ctree_root *root, struct tree_buffer *buf) 172void tree_block_release(struct ctree_root *root, struct tree_buffer *buf)
173{ 173{
174 buf->count--; 174 buf->count--;
175 write_tree_block(root, buf);
176 if (buf->count < 0) 175 if (buf->count < 0)
177 BUG(); 176 BUG();
178 if (buf->count == 0) { 177 if (buf->count == 0) {
diff --git a/fs/btrfs/print-tree.c b/fs/btrfs/print-tree.c
new file mode 100644
index 000000000000..594d23b5b24c
--- /dev/null
+++ b/fs/btrfs/print-tree.c
@@ -0,0 +1,72 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4#include "radix-tree.h"
5#include "ctree.h"
6#include "disk-io.h"
7
8void print_leaf(struct leaf *l)
9{
10 int i;
11 int nr = l->header.nritems;
12 struct item *item;
13 struct extent_item *ei;
14 printf("leaf %lu total ptrs %d free space %d\n", l->header.blocknr, nr,
15 leaf_free_space(l));
16 fflush(stdout);
17 for (i = 0 ; i < nr ; i++) {
18 item = l->items + i;
19 printf("\titem %d key (%lu %u %lu) itemoff %d itemsize %d\n",
20 i,
21 item->key.objectid, item->key.flags, item->key.offset,
22 item->offset, item->size);
23 fflush(stdout);
24 printf("\t\titem data %.*s\n", item->size, l->data+item->offset);
25 ei = (struct extent_item *)(l->data + item->offset);
26 printf("\t\textent data %u %lu\n", ei->refs, ei->owner);
27 fflush(stdout);
28 }
29}
30void print_tree(struct ctree_root *root, struct tree_buffer *t)
31{
32 int i;
33 int nr;
34 struct node *c;
35
36 if (!t)
37 return;
38 c = &t->node;
39 nr = c->header.nritems;
40 if (c->header.blocknr != t->blocknr)
41 BUG();
42 if (is_leaf(c->header.flags)) {
43 print_leaf((struct leaf *)c);
44 return;
45 }
46 printf("node %lu level %d total ptrs %d free spc %lu\n", t->blocknr,
47 node_level(c->header.flags), c->header.nritems,
48 NODEPTRS_PER_BLOCK - c->header.nritems);
49 fflush(stdout);
50 for (i = 0; i < nr; i++) {
51 printf("\tkey %d (%lu %u %lu) block %lu\n",
52 i,
53 c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset,
54 c->blockptrs[i]);
55 fflush(stdout);
56 }
57 for (i = 0; i < nr; i++) {
58 struct tree_buffer *next_buf = read_tree_block(root,
59 c->blockptrs[i]);
60 struct node *next = &next_buf->node;
61 if (is_leaf(next->header.flags) &&
62 node_level(c->header.flags) != 1)
63 BUG();
64 if (node_level(next->header.flags) !=
65 node_level(c->header.flags) - 1)
66 BUG();
67 print_tree(root, next_buf);
68 tree_block_release(root, next_buf);
69 }
70
71}
72
diff --git a/fs/btrfs/print-tree.h b/fs/btrfs/print-tree.h
new file mode 100644
index 000000000000..3c1e9a3e0260
--- /dev/null
+++ b/fs/btrfs/print-tree.h
@@ -0,0 +1,3 @@
1
2void print_leaf(struct leaf *l);
3void print_tree(struct ctree_root *root, struct tree_buffer *t);
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-18 12:16:56 -0500