diff options
| -rw-r--r-- | Makefile | 27 | ||||
| -rw-r--r-- | bit-radix.c | 194 | ||||
| -rw-r--r-- | btrfsck.c | 168 | ||||
| -rw-r--r-- | ctree.c | 4 | ||||
| -rw-r--r-- | ctree.h | 38 | ||||
| -rw-r--r-- | disk-io.c | 1 | ||||
| -rw-r--r-- | extent-tree.c | 8 | ||||
| -rw-r--r-- | kerncompat.h | 45 | ||||
| -rw-r--r-- | mkfs.c | 1 | ||||
| -rw-r--r-- | print-tree.c | 16 |
10 files changed, 469 insertions, 33 deletions
@@ -8,7 +8,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ # # if you don't have sparse installed, use ls instead CHECKFLAGS=-D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise \ - -Wcontext -Wcast-truncate -Wuninitialized -Wshadow -Wundef + -Wuninitialized -Wshadow -Wundef check=sparse $(CHECKFLAGS) #check=ls @@ -16,32 +16,33 @@ check=sparse $(CHECKFLAGS) $(check) $< $(CC) $(CFLAGS) -c $< -all: bit-radix-test tester debug-tree quick-test dir-test tags mkfs.btrfs \ - btrfsctl +all: tester debug-tree quick-test dir-test mkfs.btrfs \ + btrfsctl btrfsck -btrfsctl: ioctl.h btrfsctl.o +btrfsctl: ioctl.h btrfsctl.o $(headers) gcc $(CFLAGS) -o btrfsctl btrfsctl.o -mkfs.btrfs: $(objects) mkfs.o +btrfsck: btrfsck.o $(headers) bit-radix.o + gcc $(CFLAGS) -o btrfsck btrfsck.o $(objects) bit-radix.o + +mkfs.btrfs: $(objects) mkfs.o $(headers) gcc $(CFLAGS) -o mkfs.btrfs $(objects) mkfs.o -luuid -bit-radix-test: $(objects) bit-radix.o +bit-radix-test: $(objects) bit-radix.o $(headers) gcc $(CFLAGS) -o bit-radix-test $(objects) bit-radix.o -debug-tree: $(objects) debug-tree.o +debug-tree: $(objects) debug-tree.o $(headers) gcc $(CFLAGS) -o debug-tree $(objects) debug-tree.o -luuid -tester: $(objects) random-test.o +tester: $(objects) random-test.o $(headers) gcc $(CFLAGS) -o tester $(objects) random-test.o -dir-test: $(objects) dir-test.o +dir-test: $(objects) dir-test.o $(headers) gcc $(CFLAGS) -o dir-test $(objects) dir-test.o -quick-test: $(objects) quick-test.o +quick-test: $(objects) quick-test.o $(headers) gcc $(CFLAGS) -o quick-test $(objects) quick-test.o -$(objects): $(headers) - clean : - rm debug-tree mkfs.btrfs btrfsctl *.o + rm debug-tree mkfs.btrfs btrfsctl btrfsck *.o diff --git a/bit-radix.c b/bit-radix.c new file mode 100644 index 00000000..cd5913ad --- /dev/null +++ b/bit-radix.c @@ -0,0 +1,194 @@ +#include "kerncompat.h" +#include "radix-tree.h" + +#define BIT_ARRAY_BYTES 256 +#define BIT_RADIX_BITS_PER_ARRAY ((BIT_ARRAY_BYTES - sizeof(unsigned long)) * 8) + +int set_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + int ret; + + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) { + bits = malloc(BIT_ARRAY_BYTES); + if (!bits) + return -ENOMEM; + memset(bits + 1, 0, BIT_ARRAY_BYTES - sizeof(unsigned long)); + bits[0] = slot; + radix_tree_preload(GFP_NOFS); + ret = radix_tree_insert(radix, slot, bits); + radix_tree_preload_end(); + if (ret) + return ret; + } + __set_bit(bit_slot, bits + 1); + return 0; +} + +int test_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) + return 0; + return test_bit(bit_slot, bits + 1); +} + +int clear_radix_bit(struct radix_tree_root *radix, unsigned long bit) +{ + unsigned long *bits; + unsigned long slot; + int bit_slot; + int i; + int empty = 1; + slot = bit / BIT_RADIX_BITS_PER_ARRAY; + bit_slot = bit % BIT_RADIX_BITS_PER_ARRAY; + + bits = radix_tree_lookup(radix, slot); + if (!bits) + return 0; + __clear_bit(bit_slot, bits + 1); + for (i = 1; i < BIT_ARRAY_BYTES / sizeof(unsigned long); i++) { + if (bits[i]) { + empty = 0; + break; + } + } + if (empty) { + bits = radix_tree_delete(radix, slot); + BUG_ON(!bits); + free(bits); + } + return 0; +} + +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/** + * __ffs - find first bit in word. + * @word: The word to search + * + * Undefined if no bit exists, so code should check against 0 first. + */ +static unsigned long __ffs(unsigned long word) +{ + int num = 0; + +#if BITS_PER_LONG == 64 + if ((word & 0xffffffff) == 0) { + num += 32; + word >>= 32; + } +#endif + if ((word & 0xffff) == 0) { + num += 16; + word >>= 16; + } + if ((word & 0xff) == 0) { + num += 8; + word >>= 8; + } + if ((word & 0xf) == 0) { + num += 4; + word >>= 4; + } + if ((word & 0x3) == 0) { + num += 2; + word >>= 2; + } + if ((word & 0x1) == 0) + num += 1; + return num; +} + +/** + * find_next_bit - find the next set bit in a memory region + * @addr: The address to base the search on + * @offset: The bitnumber to start searching at + * @size: The maximum size to search + */ +unsigned long find_next_bit(const unsigned long *addr, unsigned long size, + unsigned long offset) +{ + const unsigned long *p = addr + BITOP_WORD(offset); + unsigned long result = offset & ~(BITS_PER_LONG-1); + unsigned long tmp; + + if (offset >= size) + return size; + size -= result; + offset %= BITS_PER_LONG; + if (offset) { + tmp = *(p++); + tmp &= (~0UL << offset); + if (size < BITS_PER_LONG) + goto found_first; + if (tmp) + goto found_middle; + size -= BITS_PER_LONG; + result += BITS_PER_LONG; + } + while (size & ~(BITS_PER_LONG-1)) { + if ((tmp = *(p++))) + goto found_middle; + result += BITS_PER_LONG; + size -= BITS_PER_LONG; + } + if (!size) + return result; + tmp = *p; + +found_first: + tmp &= (~0UL >> (BITS_PER_LONG - size)); + if (tmp == 0UL) /* Are any bits set? */ + return result + size; /* Nope. */ +found_middle: + return result + __ffs(tmp); +} + +int find_first_radix_bit(struct radix_tree_root *radix, unsigned long *retbits, + unsigned long start, int nr) +{ + unsigned long *bits; + unsigned long *gang[4]; + int found; + int ret; + int i; + int total_found = 0; + unsigned long slot; + + slot = start / BIT_RADIX_BITS_PER_ARRAY; + ret = radix_tree_gang_lookup(radix, (void **)gang, slot, + ARRAY_SIZE(gang)); + for (i = 0; i < ret && nr > 0; i++) { + found = 0; + bits = gang[i]; + while(nr > 0) { + found = find_next_bit(bits + 1, + BIT_RADIX_BITS_PER_ARRAY, + found); + if (found < BIT_RADIX_BITS_PER_ARRAY) { + *retbits = bits[0] * + BIT_RADIX_BITS_PER_ARRAY + found; + retbits++; + nr--; + total_found++; + found++; + } else + break; + } + } + return total_found; +} diff --git a/btrfsck.c b/btrfsck.c new file mode 100644 index 00000000..2f8630ff --- /dev/null +++ b/btrfsck.c @@ -0,0 +1,168 @@ +#include <stdio.h> +#include <stdlib.h> +#include "kerncompat.h" +#include "radix-tree.h" +#include "ctree.h" +#include "disk-io.h" +#include "print-tree.h" +#include "transaction.h" +#include "bit-radix.h" + +u64 blocks_used = 0; +struct extent_record { + u64 start; + u64 nr; + u64 owner; + u32 refs; + u8 type; +}; + +static int add_extent_rec(struct radix_tree_root *extent_radix, + u64 ref, u64 start, u64 nr, u64 owner, u8 type) +{ + struct extent_record *rec; + int ret = 0; + rec = radix_tree_lookup(extent_radix, start); + if (rec) { + rec->refs++; + if (owner != rec->owner) { + fprintf(stderr, "warning, owner mismatch %Lu\n", start); + ret = 1; + } + if (start != rec->start) { + fprintf(stderr, "warning, start mismatch %Lu %Lu\n", + rec->start, start); + ret = 1; + } + if (type != rec->type) { + fprintf(stderr, "type mismatch block %Lu %d %d\n", + start, type, type); + ret = 1; + } + return ret; + } + rec = malloc(sizeof(*rec)); + rec->start = start; + rec->nr = nr; + rec->owner = owner; + rec->type = type; + ret = radix_tree_insert(extent_radix, start, rec); + BUG_ON(ret); + blocks_used += nr; + return ret; +} + +static int add_pending(struct radix_tree_root *pending, + struct radix_tree_root *seen, u64 blocknr) +{ + if (test_radix_bit(seen, blocknr)) + return -EEXIST; + set_radix_bit(pending, blocknr); + set_radix_bit(seen, blocknr); + return 0; +} + +static int run_next_block(struct btrfs_root *root, + u64 *last, + struct radix_tree_root *pending, + struct radix_tree_root *seen, + struct radix_tree_root *extent_radix) +{ + struct btrfs_buffer *buf; + u64 blocknr; + int ret; + int i; + int nritems; + struct btrfs_leaf *leaf; + struct btrfs_node *node; + unsigned long bits; + + ret = find_first_radix_bit(pending, &bits, *last, 1); + if (ret == 0) { + ret = find_first_radix_bit(pending, &bits, 0, 1); + if (ret == 0) + return 1; + } + *last = bits; + blocknr = bits; + clear_radix_bit(pending, blocknr); + buf = read_tree_block(root, blocknr); + nritems = btrfs_header_nritems(&buf->node.header); + if (btrfs_is_leaf(&buf->node)) { + leaf = &buf->leaf; + for (i = 0; i < nritems; i++) { + struct btrfs_file_extent_item *fi; + if (btrfs_disk_key_type(&leaf->items[i].key) != + BTRFS_EXTENT_DATA_KEY) + continue; + fi = btrfs_item_ptr(leaf, i, + struct btrfs_file_extent_item); + if (btrfs_file_extent_type(fi) != + BTRFS_FILE_EXTENT_REG) + continue; + ret = add_extent_rec(extent_radix, blocknr, + btrfs_file_extent_disk_blocknr(fi), + btrfs_file_extent_disk_num_blocks(fi), + btrfs_disk_key_objectid(&leaf->items[i].key), + BTRFS_EXTENT_FILE); + BUG_ON(ret); + } + } else { + node = &buf->node; + for (i = 0; i < nritems; i++) { + u64 ptr = btrfs_node_blockptr(node, i); + ret = add_extent_rec(extent_radix, blocknr, ptr, 1, + btrfs_header_owner(&node->header), + BTRFS_EXTENT_TREE); + BUG_ON(ret); + add_pending(pending, seen, ptr); + } + } + btrfs_block_release(root, buf); + return 0; +} + +static int add_root_to_pending(struct btrfs_root *root, + struct radix_tree_root *extent_radix, + struct radix_tree_root *pending, + struct radix_tree_root *seen) +{ + add_pending(pending, seen, root->node->blocknr); + add_extent_rec(extent_radix, 0, root->node->blocknr, 1, + btrfs_header_owner(&root->node->node.header), + BTRFS_EXTENT_TREE); + return 0; +} +int main(int ac, char **av) { + struct btrfs_super_block super; + struct btrfs_root *root; + struct radix_tree_root extent_radix; + struct radix_tree_root seen; + struct radix_tree_root pending; + int ret; + u64 last = 0; + + radix_tree_init(); + + INIT_RADIX_TREE(&extent_radix, GFP_NOFS); + init_bit_radix(&seen); + init_bit_radix(&pending); + + root = open_ctree(av[1], &super); + add_root_to_pending(root, &extent_radix, &pending, &seen); + add_root_to_pending(root->fs_info->tree_root,&extent_radix, + &pending, &seen); + add_root_to_pending(root->fs_info->dev_root, &extent_radix, + &pending, &seen); + add_root_to_pending(root->fs_info->extent_root, &extent_radix, + &pending, &seen); + while(1) { + ret = run_next_block(root, &last, &pending, + &seen, &extent_radix); + if (ret != 0) + break; + } + close_ctree(root, &super); + printf("found %Lu blocks used\n", blocks_used); + return 0; +} @@ -49,6 +49,7 @@ static int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root cow = btrfs_alloc_free_block(trans, root); memcpy(&cow->node, &buf->node, root->blocksize); btrfs_set_header_blocknr(&cow->node.header, cow->blocknr); + btrfs_set_header_owner(&cow->node.header, root->root_key.objectid); *cow_ret = cow; btrfs_inc_ref(trans, root, buf); if (buf == root->node) { @@ -661,6 +662,7 @@ static int insert_new_root(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_header_nritems(&c->header, 1); btrfs_set_header_level(&c->header, level); btrfs_set_header_blocknr(&c->header, t->blocknr); + btrfs_set_header_owner(&c->header, root->root_key.objectid); lower = &path->nodes[level-1]->node; if (btrfs_is_leaf(lower)) lower_key = &((struct btrfs_leaf *)lower)->items[0].key; @@ -746,6 +748,7 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_header_flags(&split->header, btrfs_header_flags(&c->header)); btrfs_set_header_level(&split->header, btrfs_header_level(&c->header)); btrfs_set_header_blocknr(&split->header, split_buffer->blocknr); + btrfs_set_header_owner(&split->header, root->root_key.objectid); mid = (c_nritems + 1) / 2; memcpy(split->ptrs, c->ptrs + mid, (c_nritems - mid) * sizeof(struct btrfs_key_ptr)); @@ -1088,6 +1091,7 @@ static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_header_nritems(&right->header, nritems - mid); btrfs_set_header_blocknr(&right->header, right_buffer->blocknr); btrfs_set_header_level(&right->header, 0); + btrfs_set_header_owner(&right->header, root->root_key.objectid); data_copy_size = btrfs_item_end(l->items + mid) - leaf_data_end(root, l); memcpy(right->items, l->items + mid, @@ -58,6 +58,7 @@ struct btrfs_header { u8 fsid[16]; /* FS specific uuid */ __le64 blocknr; /* which block this node is supposed to live in */ __le64 generation; + __le64 owner; __le16 nritems; __le16 flags; u8 level; @@ -144,12 +145,17 @@ struct btrfs_path { int slots[BTRFS_MAX_LEVEL]; }; +/* values for the type field in btrfs_extent_item */ +#define BTRFS_EXTENT_TREE 1 +#define BTRFS_EXTENT_FILE 2 /* * items in the extent btree are used to record the objectid of the * owner of the block and the number of references */ struct btrfs_extent_item { __le32 refs; + __le64 owner; + u8 type; } __attribute__ ((__packed__)); struct btrfs_inode_timespec { @@ -461,11 +467,32 @@ static inline void btrfs_set_extent_refs(struct btrfs_extent_item *ei, u32 val) ei->refs = cpu_to_le32(val); } +static inline u64 btrfs_extent_owner(struct btrfs_extent_item *ei) +{ + return le64_to_cpu(ei->owner); +} + +static inline void btrfs_set_extent_owner(struct btrfs_extent_item *ei, u64 val) +{ + ei->owner = cpu_to_le64(val); +} + +static inline u8 btrfs_extent_type(struct btrfs_extent_item *ei) +{ + return ei->type; +} + +static inline void btrfs_set_extent_type(struct btrfs_extent_item *ei, u8 val) +{ + ei->type = val; +} + static inline u64 btrfs_node_blockptr(struct btrfs_node *n, int nr) { return le64_to_cpu(n->ptrs[nr].blockptr); } + static inline void btrfs_set_node_blockptr(struct btrfs_node *n, int nr, u64 val) { @@ -624,6 +651,17 @@ static inline void btrfs_set_header_generation(struct btrfs_header *h, h->generation = cpu_to_le64(val); } +static inline u64 btrfs_header_owner(struct btrfs_header *h) +{ + return le64_to_cpu(h->owner); +} + +static inline void btrfs_set_header_owner(struct btrfs_header *h, + u64 val) +{ + h->owner = cpu_to_le64(val); +} + static inline u16 btrfs_header_nritems(struct btrfs_header *h) { return le16_to_cpu(h->nritems); @@ -294,6 +294,7 @@ static int __setup_root(struct btrfs_super_block *super, root->fs_info = fs_info; memset(&root->root_key, 0, sizeof(root->root_key)); memset(&root->root_item, 0, sizeof(root->root_item)); + root->root_key.objectid = objectid; return 0; } diff --git a/extent-tree.c b/extent-tree.c index 0dc2ee42..a0fc1772 100644 --- a/extent-tree.c +++ b/extent-tree.c @@ -394,7 +394,8 @@ error: * returns 0 if everything worked, non-zero otherwise. */ static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root - *root, u64 num_blocks, u64 search_start, u64 + *root, u64 owner, u8 type, u64 num_blocks, + u64 search_start, u64 search_end, struct btrfs_key *ins) { int ret; @@ -405,6 +406,8 @@ static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root struct btrfs_extent_item extent_item; btrfs_set_extent_refs(&extent_item, 1); + btrfs_set_extent_owner(&extent_item, owner); + btrfs_set_extent_type(&extent_item, type); if (root == extent_root) { BUG_ON(extent_root->fs_info->current_insert.offset == 0); @@ -447,7 +450,8 @@ struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans, int ret; struct btrfs_buffer *buf; - ret = alloc_extent(trans, root, 1, 0, (unsigned long)-1, &ins); + ret = alloc_extent(trans, root, root->root_key.objectid, + BTRFS_EXTENT_TREE, 1, 0, (unsigned long)-1, &ins); if (ret) { BUG(); return NULL; diff --git a/kerncompat.h b/kerncompat.h index 647d38e9..c706f551 100644 --- a/kerncompat.h +++ b/kerncompat.h @@ -48,23 +48,44 @@ struct page { static inline void preempt_enable(void) { do {; } while(0);} static inline void preempt_disable(void) { do {; } while(0);} -static inline void __set_bit(int bit, unsigned long *map) { - unsigned long *p = map + bit / BITS_PER_LONG; - bit = bit & (BITS_PER_LONG -1); - *p |= 1UL << bit; +#define BITOP_MASK(nr) (1UL << ((nr) % BITS_PER_LONG)) +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG) + +/** + * __set_bit - Set a bit in memory + * @nr: the bit to set + * @addr: the address to start counting from + * + * Unlike set_bit(), this function is non-atomic and may be reordered. + * If it's called on the same region of memory simultaneously, the effect + * may be that only one operation succeeds. + */ +static inline void __set_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BITOP_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + + *p |= mask; } -static inline int test_bit(int bit, unsigned long *map) { - unsigned long *p = map + bit / BITS_PER_LONG; - bit = bit & (BITS_PER_LONG -1); - return *p & (1UL << bit) ? 1 : 0; +static inline void __clear_bit(int nr, volatile unsigned long *addr) +{ + unsigned long mask = BITOP_MASK(nr); + unsigned long *p = ((unsigned long *)addr) + BITOP_WORD(nr); + + *p &= ~mask; } -static inline void __clear_bit(int bit, unsigned long *map) { - unsigned long *p = map + bit / BITS_PER_LONG; - bit = bit & (BITS_PER_LONG -1); - *p &= ~(1UL << bit); +/** + * test_bit - Determine whether a bit is set + * @nr: bit number to test + * @addr: Address to start counting from + */ +static inline int test_bit(int nr, const volatile unsigned long *addr) +{ + return 1UL & (addr[BITOP_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); } + #define BUG_ON(c) do { if (c) abort(); } while (0) #define container_of(ptr, type, member) ({ \ @@ -141,6 +141,7 @@ int mkfs(int fd, char *pathname, u64 num_blocks, u32 blocksize) btrfs_set_header_blocknr(&empty_leaf->header, start_block + 1); btrfs_set_header_nritems(&empty_leaf->header, 2); btrfs_set_header_generation(&empty_leaf->header, 0); + btrfs_set_header_owner(&empty_leaf->header, BTRFS_ROOT_TREE_OBJECTID); memcpy(empty_leaf->header.fsid, super.fsid, sizeof(empty_leaf->header.fsid)); diff --git a/print-tree.c b/print-tree.c index 17724b2b..86fccd56 100644 --- a/print-tree.c +++ b/print-tree.c @@ -40,10 +40,11 @@ void btrfs_print_leaf(struct btrfs_root *root, struct btrfs_leaf *l) char *p; u32 type; - printf("leaf %Lu ptrs %d free space %d generation %Lu\n", + printf("leaf %Lu ptrs %d free space %d generation %Lu owner %Lu\n", btrfs_header_blocknr(&l->header), nr, btrfs_leaf_free_space(root, l), - btrfs_header_generation(&l->header)); + btrfs_header_generation(&l->header), + btrfs_header_owner(&l->header)); fflush(stdout); for (i = 0 ; i < nr ; i++) { item = l->items + i; @@ -84,8 +85,10 @@ void btrfs_print_leaf(struct btrfs_root *root, struct btrfs_leaf *l) break; case BTRFS_EXTENT_ITEM_KEY: ei = btrfs_item_ptr(l, i, struct btrfs_extent_item); - printf("\t\textent data refs %u\n", - btrfs_extent_refs(ei)); + printf("\t\textent data refs %u type %d owner %Lu\n", + btrfs_extent_refs(ei), + btrfs_extent_type(ei), + btrfs_extent_owner(ei)); break; case BTRFS_CSUM_ITEM_KEY: ci = btrfs_item_ptr(l, i, @@ -138,11 +141,12 @@ void btrfs_print_tree(struct btrfs_root *root, struct btrfs_buffer *t) btrfs_print_leaf(root, (struct btrfs_leaf *)c); return; } - printf("node %Lu level %d ptrs %d free %u generation %Lu\n", + printf("node %Lu level %d ptrs %d free %u generation %Lu owner %Lu\n", t->blocknr, btrfs_header_level(&c->header), nr, (u32)BTRFS_NODEPTRS_PER_BLOCK(root) - nr, - btrfs_header_generation(&c->header)); + btrfs_header_generation(&c->header), + btrfs_header_owner(&c->header)); fflush(stdout); for (i = 0; i < nr; i++) { printf("\tkey %d (%Lu %x %Lu) block %Lu\n", |