Chen Yang
2012-Aug-08 03:06 UTC
[RFC][PATCH V2] Btrfs-progs, btrfsck: add block group check function
From: Chen Yang <chenyang.fnst@cn.fujitsu.com>
This patch adds the function to check correspondence
between block group, chunk and device extent.
Signed-off-by: Cheng Yang <chenyang.fnst@cn.fujitsu.com>
---
v1->v2: optimaze the checking process:
* Remove the checking traversal of block group RB tree.
* Mark block group item which matched with chunk item.
* Output the unmarked block group item error infomaton.
when releasing RB tree.
* Merge some relevant flows into one.
---
Makefile | 2 +-
btrfsck.c | 517 +++++++++++++++++++++++++++++++++++++++++++++++++++-
dev-extent-cache.c | 188 +++++++++++++++++++
dev-extent-cache.h | 60 ++++++
4 files changed, 760 insertions(+), 7 deletions(-)
create mode 100644 dev-extent-cache.c
create mode 100644 dev-extent-cache.h
diff --git a/Makefile b/Makefile
index 9694444..75eced8 100644
--- a/Makefile
+++ b/Makefile
@@ -4,7 +4,7 @@ CFLAGS = -g -O0
objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \
root-tree.o dir-item.o file-item.o inode-item.o \
inode-map.o crc32c.o rbtree.o extent-cache.o extent_io.o \
- volumes.o utils.o btrfs-list.o btrfslabel.o repair.o
+ volumes.o utils.o btrfs-list.o btrfslabel.o repair.o dev-extent-cache.o
cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
cmds-inspect.o cmds-balance.o
diff --git a/btrfsck.c b/btrfsck.c
index 088b9f4..437aee9 100644
--- a/btrfsck.c
+++ b/btrfsck.c
@@ -34,6 +34,66 @@
#include "list.h"
#include "version.h"
#include "utils.h"
+#include "dev-extent-cache.h"
+
+#define REC_UNCHECKED 0
+#define REC_CHECKED 1
+
+struct block_group_record {
+ struct cache_extent cache;
+ int state;
+
+ u64 objectid;
+ u8 type;
+ u64 offset;
+
+ u64 flags;
+};
+
+struct dev_record {
+ struct cache_extent cache;
+ int state;
+
+ u64 objectid;
+ u8 type;
+ u64 offset;
+
+ u64 devid;
+ u64 total_byte;
+ u64 byte_used;
+};
+
+struct stripe {
+ u64 devid;
+ u64 offset;
+};
+
+struct chunk_record {
+ struct cache_extent cache;
+ int state;
+
+ u64 objectid;
+ u8 type;
+ u64 offset;
+
+ u64 length;
+ u64 type_flags;
+ u16 num_stripes;
+ struct stripe stripes[0];
+};
+
+struct dev_extent_record {
+ struct cache_dev_extent cache;
+ int state;
+
+ u64 objectid;
+ u8 type;
+ u64 offset;
+
+ u64 chunk_objecteid;
+ u64 chunk_offset;
+ u64 length;
+};
static u64 bytes_used = 0;
static u64 total_csum_bytes = 0;
@@ -1852,7 +1912,7 @@ static int all_backpointers_checked(struct extent_record
*rec, int print_errs)
(unsigned long long)rec->start,
back->full_backref ?
"parent" : "root",
- back->full_backref ?
+ back->full_backref ?
(unsigned long long)dback->parent:
(unsigned long long)dback->root,
(unsigned long long)dback->owner,
@@ -2440,6 +2500,153 @@ static int process_extent_ref_v0(struct cache_tree
*extent_cache,
}
#endif
+static int process_chunk_item(struct cache_tree *chunk_cache,
+ struct btrfs_key *key, struct extent_buffer *eb, int slot)
+{
+ struct btrfs_chunk *ptr;
+ struct chunk_record *rec;
+ int num_stripes, i;
+ int ret = 0;
+
+ ptr = btrfs_item_ptr(eb,
+ slot, struct btrfs_chunk);
+
+ num_stripes = btrfs_chunk_num_stripes(eb, ptr);
+
+ rec = malloc(sizeof(*rec) +
+ num_stripes * sizeof(*rec->stripes));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ rec->cache.start = key->offset;
+ rec->cache.size = 1;
+ rec->state = REC_UNCHECKED;
+
+ rec->objectid = key->objectid;
+ rec->type = key->type;
+ rec->offset = key->offset;
+
+ rec->length = btrfs_chunk_length(eb, ptr);
+ rec->type = btrfs_chunk_type(eb, ptr);
+ rec->num_stripes = num_stripes;
+
+ for (i = 0; i < rec->num_stripes; ++i) {
+ rec->stripes[i].devid + btrfs_stripe_devid_nr(eb, ptr, i);
+ rec->stripes[i].offset + btrfs_stripe_offset_nr(eb, ptr, i);
+ }
+
+ ret = insert_existing_cache_extent(
+ chunk_cache, &rec->cache);
+
+ return ret;
+}
+
+static int process_dev_item(struct cache_tree *dev_cache,
+ struct btrfs_key *key, struct extent_buffer *eb, int slot)
+{
+ struct btrfs_dev_item *ptr;
+ struct dev_record *rec;
+ int ret = 0;
+
+ ptr = btrfs_item_ptr(eb,
+ slot, struct btrfs_dev_item);
+
+ rec = malloc(sizeof(*rec));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ rec->cache.start = key->offset;
+ rec->cache.size = 1;
+ rec->state = REC_UNCHECKED;
+
+ rec->objectid = key->objectid;
+ rec->type = key->type;
+ rec->offset = key->offset;
+
+ rec->devid = btrfs_device_id(eb, ptr);
+ rec->total_byte = btrfs_device_total_bytes(eb, ptr);
+ rec->byte_used = btrfs_device_bytes_used(eb, ptr);
+
+ ret = insert_existing_cache_extent(
+ dev_cache, &rec->cache);
+
+ return ret;
+}
+
+static int process_block_group_item(struct cache_tree *block_group_cache,
+ struct btrfs_key *key, struct extent_buffer *eb, int slot)
+{
+ struct btrfs_block_group_item *ptr;
+ struct block_group_record *rec;
+ int ret = 0;
+
+ ptr = btrfs_item_ptr(eb, slot,
+ struct btrfs_block_group_item);
+
+ rec = malloc(sizeof(*rec));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ rec->cache.start = key->objectid;
+ rec->cache.size = 1;
+ rec->state = REC_UNCHECKED;
+
+ rec->objectid = key->objectid;
+ rec->type = key->type;
+ rec->offset = key->offset;
+ rec->flags = btrfs_disk_block_group_flags(eb, ptr);
+
+ ret = insert_existing_cache_extent(
+ block_group_cache, &rec->cache);
+
+ return ret;
+}
+
+static int process_dev_extent_item(struct dev_extent_tree *dev_extent_cache,
+ struct btrfs_key *key, struct extent_buffer *eb, int slot)
+{
+ int ret = 0;
+
+ struct btrfs_dev_extent *ptr;
+ struct dev_extent_record *rec;
+
+ ptr = btrfs_item_ptr(eb,
+ slot, struct btrfs_dev_extent);
+
+ rec = malloc(sizeof(*rec));
+ if (!rec) {
+ fprintf(stderr, "memory allocation failed\n");
+ return -ENOMEM;
+ }
+
+ rec->cache.devno = key->objectid;
+ rec->cache.offset = key->offset;
+ rec->state = REC_UNCHECKED;
+
+ rec->objectid = key->objectid;
+ rec->type = key->type;
+ rec->offset = key->offset;
+
+ rec->chunk_objecteid + btrfs_dev_extent_chunk_objectid(eb, ptr);
+ rec->chunk_offset + btrfs_dev_extent_chunk_offset(eb, ptr);
+ rec->length = btrfs_dev_extent_length(eb, ptr);
+
+ ret = insert_existing_cache_dev_extent(
+ dev_extent_cache, &rec->cache);
+
+ return ret;
+}
+
static int process_extent_item(struct cache_tree *extent_cache,
struct extent_buffer *eb, int slot)
{
@@ -2531,7 +2738,11 @@ static int run_next_block(struct btrfs_root *root,
struct cache_tree *seen,
struct cache_tree *reada,
struct cache_tree *nodes,
- struct cache_tree *extent_cache)
+ struct cache_tree *extent_cache,
+ struct cache_tree *chunk_cache,
+ struct cache_tree *dev_cache,
+ struct cache_tree *block_group_cache,
+ struct dev_extent_tree *dev_extent_cache)
{
struct extent_buffer *buf;
u64 bytenr;
@@ -2622,8 +2833,24 @@ static int run_next_block(struct btrfs_root *root,
btrfs_item_size_nr(buf, i);
continue;
}
+ if (key.type == BTRFS_CHUNK_ITEM_KEY) {
+ process_chunk_item(chunk_cache, &key, buf, i);
+ continue;
+ }
+ if (key.type == BTRFS_DEV_ITEM_KEY) {
+ process_dev_item(dev_cache, &key, buf, i);
+ continue;
+ }
if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
+ process_block_group_item(block_group_cache,
+ &key, buf, i);
+ continue;
+ }
+ if (key.type == BTRFS_DEV_EXTENT_KEY) {
+ process_dev_extent_item(dev_extent_cache,
+ &key, buf, i);
continue;
+
}
if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
@@ -2663,7 +2890,7 @@ static int run_next_block(struct btrfs_root *root,
ref = btrfs_item_ptr(buf, i,
struct btrfs_shared_data_ref);
add_data_backref(extent_cache,
- key.objectid, key.offset, 0, 0, 0,
+ key.objectid, key.offset, 0, 0, 0,
btrfs_shared_data_ref_count(buf, ref),
0, root->sectorsize);
continue;
@@ -3366,9 +3593,260 @@ repair_abort:
return err;
}
+static void free_chunk_cache(struct cache_tree *chunk_cache)
+{
+ struct cache_extent *cache;
+ while (1) {
+ struct chunk_record *rec;
+
+ cache = find_first_cache_extent(chunk_cache, 0);
+ if (!cache)
+ break;
+ rec = container_of(cache, struct chunk_record, cache);
+ if (rec->state == REC_UNCHECKED) {
+ fprintf(stderr,
+ "Chunk[%llu, %u, %llu] "
+ "is not referred by any others\n",
+ rec->objectid,
+ rec->type,
+ rec->offset);
+ }
+
+ remove_cache_extent(chunk_cache, &rec->cache);
+ free(rec);
+ }
+}
+
+static void free_dev_cache(struct cache_tree *dev_cache)
+{
+ struct cache_extent *cache;
+ while (1) {
+ struct dev_record *rec;
+
+ cache = find_first_cache_extent(dev_cache, 0);
+ if (!cache)
+ break;
+ rec = container_of(cache, struct dev_record, cache);
+ if (rec->state == REC_UNCHECKED) {
+ fprintf(stderr,
+ "Dev[%llu, %u, %llu] "
+ "is not referred by any others\n",
+ rec->objectid,
+ rec->type,
+ rec->offset);
+ }
+
+ remove_cache_extent(dev_cache, &rec->cache);
+ free(rec);
+ }
+}
+
+static void free_block_group_cache(struct cache_tree *block_group_cache)
+{
+ struct cache_extent *cache;
+ while (1) {
+ struct block_group_record *rec;
+
+ cache = find_first_cache_extent(block_group_cache, 0);
+ if (!cache)
+ break;
+ rec = container_of(cache, struct block_group_record, cache);
+ if (rec->state == REC_UNCHECKED) {
+ fprintf(stderr,
+ "Block group[%llu, %u, %llu] "
+ "is not referred by any others\n",
+ rec->objectid,
+ rec->type,
+ rec->offset);
+ }
+
+ remove_cache_extent(block_group_cache, &rec->cache);
+ free(rec);
+ }
+}
+
+static void free_dev_extent_cache(struct dev_extent_tree *dev_extent_cache)
+{
+ struct cache_dev_extent *cache;
+ while (1) {
+ struct dev_extent_record *rec;
+
+ cache = find_first_cache_dev_extent(dev_extent_cache, 0);
+ if (!cache)
+ break;
+ rec = container_of(cache, struct dev_extent_record, cache);
+ if (rec->state == REC_UNCHECKED) {
+ fprintf(stderr,
+ "Dev extent[%llu, %u, %llu] "
+ "is not referred by any others\n",
+ rec->objectid,
+ rec->type,
+ rec->offset);
+ }
+
+ remove_cache_dev_extent(dev_extent_cache, &rec->cache);
+ free(rec);
+ }
+}
+
+/* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
+static int check_chunk_refs(struct cache_tree *chunk_cache,
+ struct cache_tree *block_group_cache,
+ struct dev_extent_tree *dev_extent_cache)
+{
+ struct cache_extent *chunk_item;
+ struct chunk_record *chunk_rec;
+ int err = 0;
+
+ chunk_item = find_first_cache_extent(chunk_cache, 0);
+ while (chunk_item) {
+ struct cache_extent *block_group_item;
+ struct block_group_record *block_group_rec;
+
+ struct cache_dev_extent *dev_extent_item;
+ struct dev_extent_record *dev_extent_rec;
+ int i;
+
+ chunk_rec = container_of(
+ chunk_item, struct chunk_record, cache);
+
+ block_group_item = find_cache_extent(block_group_cache,
+ chunk_rec->offset, 1);
+ if (block_group_item) {
+ block_group_rec = container_of(block_group_item,
+ struct block_group_record, cache);
+
+ if (chunk_rec->length != block_group_rec->offset)
+ err = -2;
+ if (chunk_rec->offset != block_group_rec->objectid)
+ err = -2;
+ if (chunk_rec->type != block_group_rec->flags)
+ err = -2;
+
+ if (err != 0) {
+ BUG_ON(1);
+ fprintf(stderr,
+ "Chunk[%llu, %u, %llu]: "
+ "length(%llu), offset(%llu), type(%llu) "
+ "mismatch with block group[%llu, %u, %llu]: "
+ "offset(%llu), objectid(%llu), flags(%llu)\n",
+ chunk_rec->objectid,
+ chunk_rec->type,
+ chunk_rec->offset,
+ chunk_rec->length,
+ chunk_rec->offset,
+ chunk_rec->type_flags,
+ block_group_rec->objectid,
+ block_group_rec->type,
+ block_group_rec->offset,
+ block_group_rec->offset,
+ block_group_rec->objectid,
+ block_group_rec->flags);
+ }
+
+ block_group_rec->state = REC_CHECKED;
+ chunk_rec->state = REC_CHECKED;
+ } else {
+ fprintf(stderr,
+ "Chunk[%llu, %u, %llu]: "
+ "length(%llu), offset(%llu), type(%llu) "
+ "is not found in block group\n",
+ chunk_rec->objectid,
+ chunk_rec->type,
+ chunk_rec->offset,
+ chunk_rec->length,
+ chunk_rec->offset,
+ chunk_rec->type_flags);
+ err = -1;
+ }
+
+ for (i = 0; i < chunk_rec->num_stripes; ++i) {
+ dev_extent_item = find_cache_dev_extent(
+ dev_extent_cache,
+ chunk_rec->stripes[i].devid,
+ chunk_rec->stripes[i].offset);
+ if (dev_extent_item) {
+ dev_extent_rec = container_of(dev_extent_item,
+ struct dev_extent_record, cache);
+ dev_extent_rec->state = REC_CHECKED;
+ chunk_rec->state = REC_CHECKED;
+ } else {
+ fprintf(stderr,
+ "Chunk[%llu, %u, %llu] stripe[%llu, %llu]"
+ "is not found in dev extent\n",
+ chunk_rec->objectid,
+ chunk_rec->type,
+ chunk_rec->offset,
+ chunk_rec->stripes[i].devid,
+ chunk_rec->stripes[i].offset);
+ err = -1;
+ }
+ }
+
+ chunk_item = next_cache_extent(chunk_item);
+ }
+ return err;
+}
+
+/* check btrfs_dev_item -> btrfs_dev_extent */
+static int check_dev_refs(struct cache_tree *dev_cache,
+ struct dev_extent_tree *dev_extent_cache)
+{
+ struct cache_extent *dev_item;
+ struct dev_record *dev_rec;
+ int err = 0;
+
+ dev_item = find_first_cache_extent(dev_cache, 0);
+ while (dev_item) {
+ struct cache_dev_extent *dev_extent_item;
+ struct dev_extent_record *dev_extent_rec;
+ u64 total_byte = 0;
+
+ dev_rec = container_of(dev_item, struct dev_record, cache);
+
+ dev_extent_item = find_first_cache_dev_extent(
+ dev_extent_cache, 0);
+ while (dev_extent_item) {
+ dev_extent_rec = container_of(dev_extent_item,
+ struct dev_extent_record, cache);
+
+ if (dev_extent_rec->objectid == dev_rec->devid)
+ total_byte += dev_extent_rec->length;
+
+ dev_extent_item = next_cache_dev_extent(
+ dev_extent_item);
+ }
+
+ if (total_byte != dev_rec->byte_used) {
+ err = -2;
+
+ BUG_ON(1);
+ fprintf(stderr,
+ "Dev extent''s total-byte(%llu)"
+ "is not equal to byte-used(%llu) in"
+ "dev[%llu, %u, %llu]\n",
+ total_byte,
+ dev_rec->byte_used,
+ dev_rec->objectid,
+ dev_rec->type,
+ dev_rec->offset);
+ }
+
+ dev_rec->state = REC_CHECKED;
+
+ dev_item = next_cache_extent(dev_item);
+ }
+ return err;
+}
+
static int check_extents(struct btrfs_trans_handle *trans,
struct btrfs_root *root, int repair)
{
+ struct cache_tree dev_cache;
+ struct cache_tree chunk_cache;
+ struct cache_tree block_group_cache;
+ struct dev_extent_tree dev_extent_cache;
+
struct cache_tree extent_cache;
struct cache_tree seen;
struct cache_tree pending;
@@ -3378,7 +3856,7 @@ static int check_extents(struct btrfs_trans_handle *trans,
struct btrfs_path path;
struct btrfs_key key;
struct btrfs_key found_key;
- int ret;
+ int ret, err = 0;
u64 last = 0;
struct block_info *bits;
int bits_nr;
@@ -3386,6 +3864,11 @@ static int check_extents(struct btrfs_trans_handle
*trans,
int slot;
struct btrfs_root_item ri;
+ cache_tree_init(&dev_cache);
+ cache_tree_init(&chunk_cache);
+ cache_tree_init(&block_group_cache);
+ dev_extent_tree_init(&dev_extent_cache);
+
cache_tree_init(&extent_cache);
cache_tree_init(&seen);
cache_tree_init(&pending);
@@ -3452,11 +3935,28 @@ static int check_extents(struct btrfs_trans_handle
*trans,
btrfs_release_path(root, &path);
while(1) {
ret = run_next_block(root, bits, bits_nr, &last, &pending,
- &seen, &reada, &nodes, &extent_cache);
+ &seen, &reada, &nodes, &extent_cache,
+ &chunk_cache, &dev_cache,
+ &block_group_cache, &dev_extent_cache);
if (ret != 0)
break;
}
ret = check_extent_refs(trans, root, &extent_cache, repair);
+ if (ret) {
+ err = 1;
+ fprintf(stderr, "Errors found in extent checking\n");
+ }
+ ret = check_chunk_refs(&chunk_cache,
+ &block_group_cache, &dev_extent_cache);
+ if (ret) {
+ err = 1;
+ fprintf(stderr, "Errors found in chunk refs checking\n");
+ }
+ ret = check_dev_refs(&dev_cache, &dev_extent_cache);
+ if (ret) {
+ err = 1;
+ fprintf(stderr, "Errors found in dev refs checking\n");
+ }
if (repair) {
free_corrupt_blocks(root->fs_info);
@@ -3465,7 +3965,12 @@ static int check_extents(struct btrfs_trans_handle
*trans,
root->fs_info->corrupt_blocks = NULL;
}
- return ret;
+ free_chunk_cache(&chunk_cache);
+ free_dev_cache(&dev_cache);
+ free_block_group_cache(&block_group_cache);
+ free_dev_extent_cache(&dev_extent_cache);
+
+ return err;
}
static void print_usage(void)
diff --git a/dev-extent-cache.c b/dev-extent-cache.c
new file mode 100644
index 0000000..1f0d047
--- /dev/null
+++ b/dev-extent-cache.c
@@ -0,0 +1,188 @@
+/*
+ * Copyright (C) 2012 Fujitsu. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+#include <stdio.h>
+#include <stdlib.h>
+#include "kerncompat.h"
+#include "dev-extent-cache.h"
+
+void dev_extent_tree_init(struct dev_extent_tree *tree)
+{
+ tree->root.rb_node = NULL;
+}
+
+static struct rb_node *tree_insert(struct rb_root *root, u64 devno,
+ u64 offset, struct rb_node *node)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct cache_dev_extent *entry;
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct cache_dev_extent, rb_node);
+
+ if (devno == entry->devno) {
+ if (offset < entry->offset)
+ p = &(*p)->rb_left;
+ else if (offset > entry->offset)
+ p = &(*p)->rb_right;
+ else
+ return parent;
+ } else {
+ if (devno < entry->devno)
+ p = &(*p)->rb_left;
+ else if (devno > entry->devno)
+ p = &(*p)->rb_right;
+ else
+ return parent;
+ }
+ }
+
+ entry = rb_entry(parent, struct cache_dev_extent, rb_node);
+ rb_link_node(node, parent, p);
+ rb_insert_color(node, root);
+ return NULL;
+}
+
+static struct rb_node *__tree_search(struct rb_root *root, u64 devno,
+ u64 offset, struct rb_node **prev_ret)
+{
+ struct rb_node *n = root->rb_node;
+ struct rb_node *prev = NULL;
+ struct cache_dev_extent *entry;
+ struct cache_dev_extent *prev_entry = NULL;
+
+ while (n) {
+ entry = rb_entry(n, struct cache_dev_extent, rb_node);
+ prev = n;
+ prev_entry = entry;
+
+ if (devno == entry->devno) {
+ if (offset < entry->offset)
+ n = n->rb_left;
+ else if (offset > entry->offset)
+ n = n->rb_right;
+ else
+ return n;
+ } else {
+ if (devno < entry->devno)
+ n = n->rb_left;
+ else if (devno > entry->devno)
+ n = n->rb_right;
+ else
+ return n;
+ }
+ }
+ if (!prev_ret)
+ return NULL;
+
+ while (prev && devno >= prev_entry->devno +
prev_entry->offset) {
+ prev = rb_next(prev);
+ prev_entry = rb_entry(prev, struct cache_dev_extent, rb_node);
+ }
+ *prev_ret = prev;
+ return NULL;
+}
+
+struct cache_dev_extent *alloc_cache_dev_extent(u64 devno, u64 offset)
+{
+ struct cache_dev_extent *pe = malloc(sizeof(*pe));
+
+ if (!pe)
+ return pe;
+ pe->devno = devno;
+ pe->offset = offset;
+ return pe;
+}
+
+int insert_existing_cache_dev_extent(struct dev_extent_tree *tree,
+ struct cache_dev_extent *pe)
+{
+ struct rb_node *found;
+
+ found = tree_insert(&tree->root, pe->devno, pe->offset,
&pe->rb_node);
+ if (found)
+ return -EEXIST;
+
+ return 0;
+}
+
+int insert_cache_dev_extent(struct dev_extent_tree *tree, u64 devno, u64
offset)
+{
+ struct cache_dev_extent *pe = alloc_cache_dev_extent(devno, offset);
+ int ret;
+ ret = insert_existing_cache_dev_extent(tree, pe);
+ if (ret)
+ free(pe);
+ return ret;
+}
+
+struct cache_dev_extent *find_cache_dev_extent(struct dev_extent_tree *tree,
+ u64 devno, u64 offset)
+{
+ struct rb_node *prev;
+ struct rb_node *ret;
+ struct cache_dev_extent *entry;
+ ret = __tree_search(&tree->root, devno, offset, &prev);
+ if (!ret)
+ return NULL;
+
+ entry = rb_entry(ret, struct cache_dev_extent, rb_node);
+ return entry;
+}
+
+struct cache_dev_extent *find_first_cache_dev_extent(
+ struct dev_extent_tree *tree, u64 devno)
+{
+ struct rb_node *prev;
+ struct rb_node *ret;
+ struct cache_dev_extent *entry;
+
+ ret = __tree_search(&tree->root, devno, 1, &prev);
+ if (!ret)
+ ret = prev;
+ if (!ret)
+ return NULL;
+ entry = rb_entry(ret, struct cache_dev_extent, rb_node);
+ return entry;
+}
+
+struct cache_dev_extent *prev_cache_dev_extent(struct cache_dev_extent *pe)
+{
+ struct rb_node *node = rb_prev(&pe->rb_node);
+
+ if (!node)
+ return NULL;
+ return rb_entry(node, struct cache_dev_extent, rb_node);
+}
+
+struct cache_dev_extent *next_cache_dev_extent(struct cache_dev_extent *pe)
+{
+ struct rb_node *node = rb_next(&pe->rb_node);
+
+ if (!node)
+ return NULL;
+ return rb_entry(node, struct cache_dev_extent, rb_node);
+}
+
+void remove_cache_dev_extent(struct dev_extent_tree *tree,
+ struct cache_dev_extent *pe)
+{
+ rb_erase(&pe->rb_node, &tree->root);
+}
+
diff --git a/dev-extent-cache.h b/dev-extent-cache.h
new file mode 100644
index 0000000..9be2e2f
--- /dev/null
+++ b/dev-extent-cache.h
@@ -0,0 +1,60 @@
+/*
+ * Copyright (C) 2012 Fujitsu. All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+
+#ifndef __PENDING_DEV_EXTENT__
+#define __PENDING_DEV_EXTENT__
+#include "kerncompat.h"
+#include "rbtree.h"
+
+struct dev_extent_tree {
+ struct rb_root root;
+};
+
+struct cache_dev_extent {
+ struct rb_node rb_node;
+ u64 devno;
+ u64 offset;
+};
+
+void dev_extent_tree_init(struct dev_extent_tree *tree);
+void remove_cache_dev_extent(struct dev_extent_tree *tree,
+ struct cache_dev_extent *pe);
+struct cache_dev_extent *find_first_cache_dev_extent(
+ struct dev_extent_tree *tree, u64 devno);
+struct cache_dev_extent *prev_cache_dev_extent(struct cache_dev_extent *pe);
+struct cache_dev_extent *next_cache_dev_extent(struct cache_dev_extent *pe);
+struct cache_dev_extent *find_cache_dev_extent(struct dev_extent_tree *tree,
+ u64 devno, u64 offset);
+int insert_cache_dev_extent(struct dev_extent_tree *tree,
+ u64 devno, u64 offset);
+int insert_existing_cache_dev_extent(struct dev_extent_tree *tree,
+ struct cache_dev_extent *pe);
+
+static inline int dev_extent_tree_empty(struct dev_extent_tree *tree)
+{
+ return RB_EMPTY_ROOT(&tree->root);
+}
+
+static inline void free_cache_dev_extent(struct cache_dev_extent *pe)
+{
+ free(pe);
+}
+
+struct cache_dev_extent *alloc_pending_dev_extent(u64 devno, u64 offset);
+
+#endif
--
1.7.7
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs"
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Chen Yang
2012-Sep-24 03:21 UTC
Re: [RFC][PATCH V2] Btrfs-progs, btrfsck: add block group check function
Any comments ? δΊ 2012-8-8 11:06, Chen Yang ει:> From: Chen Yang <chenyang.fnst@cn.fujitsu.com> > > This patch adds the function to check correspondence > between block group, chunk and device extent. > > Signed-off-by: Cheng Yang <chenyang.fnst@cn.fujitsu.com> > --- > v1->v2: optimaze the checking process: > * Remove the checking traversal of block group RB tree. > * Mark block group item which matched with chunk item. > * Output the unmarked block group item error infomaton. > when releasing RB tree. > * Merge some relevant flows into one. > --- > Makefile | 2 +- > btrfsck.c | 517 +++++++++++++++++++++++++++++++++++++++++++++++++++- > dev-extent-cache.c | 188 +++++++++++++++++++ > dev-extent-cache.h | 60 ++++++ > 4 files changed, 760 insertions(+), 7 deletions(-) > create mode 100644 dev-extent-cache.c > create mode 100644 dev-extent-cache.h > > diff --git a/Makefile b/Makefile > index 9694444..75eced8 100644 > --- a/Makefile > +++ b/Makefile > @@ -4,7 +4,7 @@ CFLAGS = -g -O0 > objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ > root-tree.o dir-item.o file-item.o inode-item.o \ > inode-map.o crc32c.o rbtree.o extent-cache.o extent_io.o \ > - volumes.o utils.o btrfs-list.o btrfslabel.o repair.o > + volumes.o utils.o btrfs-list.o btrfslabel.o repair.o dev-extent-cache.o > cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ > cmds-inspect.o cmds-balance.o > > diff --git a/btrfsck.c b/btrfsck.c > index 088b9f4..437aee9 100644 > --- a/btrfsck.c > +++ b/btrfsck.c > @@ -34,6 +34,66 @@ > #include "list.h" > #include "version.h" > #include "utils.h" > +#include "dev-extent-cache.h" > + > +#define REC_UNCHECKED 0 > +#define REC_CHECKED 1 > + > +struct block_group_record { > + struct cache_extent cache; > + int state; > + > + u64 objectid; > + u8 type; > + u64 offset; > + > + u64 flags; > +}; > + > +struct dev_record { > + struct cache_extent cache; > + int state; > + > + u64 objectid; > + u8 type; > + u64 offset; > + > + u64 devid; > + u64 total_byte; > + u64 byte_used; > +}; > + > +struct stripe { > + u64 devid; > + u64 offset; > +}; > + > +struct chunk_record { > + struct cache_extent cache; > + int state; > + > + u64 objectid; > + u8 type; > + u64 offset; > + > + u64 length; > + u64 type_flags; > + u16 num_stripes; > + struct stripe stripes[0]; > +}; > + > +struct dev_extent_record { > + struct cache_dev_extent cache; > + int state; > + > + u64 objectid; > + u8 type; > + u64 offset; > + > + u64 chunk_objecteid; > + u64 chunk_offset; > + u64 length; > +}; > > static u64 bytes_used = 0; > static u64 total_csum_bytes = 0; > @@ -1852,7 +1912,7 @@ static int all_backpointers_checked(struct extent_record *rec, int print_errs) > (unsigned long long)rec->start, > back->full_backref ? > "parent" : "root", > - back->full_backref ? > + back->full_backref ? > (unsigned long long)dback->parent: > (unsigned long long)dback->root, > (unsigned long long)dback->owner, > @@ -2440,6 +2500,153 @@ static int process_extent_ref_v0(struct cache_tree *extent_cache, > } > #endif > > +static int process_chunk_item(struct cache_tree *chunk_cache, > + struct btrfs_key *key, struct extent_buffer *eb, int slot) > +{ > + struct btrfs_chunk *ptr; > + struct chunk_record *rec; > + int num_stripes, i; > + int ret = 0; > + > + ptr = btrfs_item_ptr(eb, > + slot, struct btrfs_chunk); > + > + num_stripes = btrfs_chunk_num_stripes(eb, ptr); > + > + rec = malloc(sizeof(*rec) + > + num_stripes * sizeof(*rec->stripes)); > + if (!rec) { > + fprintf(stderr, "memory allocation failed\n"); > + return -ENOMEM; > + } > + > + rec->cache.start = key->offset; > + rec->cache.size = 1; > + rec->state = REC_UNCHECKED; > + > + rec->objectid = key->objectid; > + rec->type = key->type; > + rec->offset = key->offset; > + > + rec->length = btrfs_chunk_length(eb, ptr); > + rec->type = btrfs_chunk_type(eb, ptr); > + rec->num_stripes = num_stripes; > + > + for (i = 0; i < rec->num_stripes; ++i) { > + rec->stripes[i].devid > + btrfs_stripe_devid_nr(eb, ptr, i); > + rec->stripes[i].offset > + btrfs_stripe_offset_nr(eb, ptr, i); > + } > + > + ret = insert_existing_cache_extent( > + chunk_cache, &rec->cache); > + > + return ret; > +} > + > +static int process_dev_item(struct cache_tree *dev_cache, > + struct btrfs_key *key, struct extent_buffer *eb, int slot) > +{ > + struct btrfs_dev_item *ptr; > + struct dev_record *rec; > + int ret = 0; > + > + ptr = btrfs_item_ptr(eb, > + slot, struct btrfs_dev_item); > + > + rec = malloc(sizeof(*rec)); > + if (!rec) { > + fprintf(stderr, "memory allocation failed\n"); > + return -ENOMEM; > + } > + > + rec->cache.start = key->offset; > + rec->cache.size = 1; > + rec->state = REC_UNCHECKED; > + > + rec->objectid = key->objectid; > + rec->type = key->type; > + rec->offset = key->offset; > + > + rec->devid = btrfs_device_id(eb, ptr); > + rec->total_byte = btrfs_device_total_bytes(eb, ptr); > + rec->byte_used = btrfs_device_bytes_used(eb, ptr); > + > + ret = insert_existing_cache_extent( > + dev_cache, &rec->cache); > + > + return ret; > +} > + > +static int process_block_group_item(struct cache_tree *block_group_cache, > + struct btrfs_key *key, struct extent_buffer *eb, int slot) > +{ > + struct btrfs_block_group_item *ptr; > + struct block_group_record *rec; > + int ret = 0; > + > + ptr = btrfs_item_ptr(eb, slot, > + struct btrfs_block_group_item); > + > + rec = malloc(sizeof(*rec)); > + if (!rec) { > + fprintf(stderr, "memory allocation failed\n"); > + return -ENOMEM; > + } > + > + rec->cache.start = key->objectid; > + rec->cache.size = 1; > + rec->state = REC_UNCHECKED; > + > + rec->objectid = key->objectid; > + rec->type = key->type; > + rec->offset = key->offset; > + rec->flags = btrfs_disk_block_group_flags(eb, ptr); > + > + ret = insert_existing_cache_extent( > + block_group_cache, &rec->cache); > + > + return ret; > +} > + > +static int process_dev_extent_item(struct dev_extent_tree *dev_extent_cache, > + struct btrfs_key *key, struct extent_buffer *eb, int slot) > +{ > + int ret = 0; > + > + struct btrfs_dev_extent *ptr; > + struct dev_extent_record *rec; > + > + ptr = btrfs_item_ptr(eb, > + slot, struct btrfs_dev_extent); > + > + rec = malloc(sizeof(*rec)); > + if (!rec) { > + fprintf(stderr, "memory allocation failed\n"); > + return -ENOMEM; > + } > + > + rec->cache.devno = key->objectid; > + rec->cache.offset = key->offset; > + rec->state = REC_UNCHECKED; > + > + rec->objectid = key->objectid; > + rec->type = key->type; > + rec->offset = key->offset; > + > + rec->chunk_objecteid > + btrfs_dev_extent_chunk_objectid(eb, ptr); > + rec->chunk_offset > + btrfs_dev_extent_chunk_offset(eb, ptr); > + rec->length = btrfs_dev_extent_length(eb, ptr); > + > + ret = insert_existing_cache_dev_extent( > + dev_extent_cache, &rec->cache); > + > + return ret; > +} > + > static int process_extent_item(struct cache_tree *extent_cache, > struct extent_buffer *eb, int slot) > { > @@ -2531,7 +2738,11 @@ static int run_next_block(struct btrfs_root *root, > struct cache_tree *seen, > struct cache_tree *reada, > struct cache_tree *nodes, > - struct cache_tree *extent_cache) > + struct cache_tree *extent_cache, > + struct cache_tree *chunk_cache, > + struct cache_tree *dev_cache, > + struct cache_tree *block_group_cache, > + struct dev_extent_tree *dev_extent_cache) > { > struct extent_buffer *buf; > u64 bytenr; > @@ -2622,8 +2833,24 @@ static int run_next_block(struct btrfs_root *root, > btrfs_item_size_nr(buf, i); > continue; > } > + if (key.type == BTRFS_CHUNK_ITEM_KEY) { > + process_chunk_item(chunk_cache, &key, buf, i); > + continue; > + } > + if (key.type == BTRFS_DEV_ITEM_KEY) { > + process_dev_item(dev_cache, &key, buf, i); > + continue; > + } > if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) { > + process_block_group_item(block_group_cache, > + &key, buf, i); > + continue; > + } > + if (key.type == BTRFS_DEV_EXTENT_KEY) { > + process_dev_extent_item(dev_extent_cache, > + &key, buf, i); > continue; > + > } > if (key.type == BTRFS_EXTENT_REF_V0_KEY) { > #ifdef BTRFS_COMPAT_EXTENT_TREE_V0 > @@ -2663,7 +2890,7 @@ static int run_next_block(struct btrfs_root *root, > ref = btrfs_item_ptr(buf, i, > struct btrfs_shared_data_ref); > add_data_backref(extent_cache, > - key.objectid, key.offset, 0, 0, 0, > + key.objectid, key.offset, 0, 0, 0, > btrfs_shared_data_ref_count(buf, ref), > 0, root->sectorsize); > continue; > @@ -3366,9 +3593,260 @@ repair_abort: > return err; > } > > +static void free_chunk_cache(struct cache_tree *chunk_cache) > +{ > + struct cache_extent *cache; > + while (1) { > + struct chunk_record *rec; > + > + cache = find_first_cache_extent(chunk_cache, 0); > + if (!cache) > + break; > + rec = container_of(cache, struct chunk_record, cache); > + if (rec->state == REC_UNCHECKED) { > + fprintf(stderr, > + "Chunk[%llu, %u, %llu] " > + "is not referred by any others\n", > + rec->objectid, > + rec->type, > + rec->offset); > + } > + > + remove_cache_extent(chunk_cache, &rec->cache); > + free(rec); > + } > +} > + > +static void free_dev_cache(struct cache_tree *dev_cache) > +{ > + struct cache_extent *cache; > + while (1) { > + struct dev_record *rec; > + > + cache = find_first_cache_extent(dev_cache, 0); > + if (!cache) > + break; > + rec = container_of(cache, struct dev_record, cache); > + if (rec->state == REC_UNCHECKED) { > + fprintf(stderr, > + "Dev[%llu, %u, %llu] " > + "is not referred by any others\n", > + rec->objectid, > + rec->type, > + rec->offset); > + } > + > + remove_cache_extent(dev_cache, &rec->cache); > + free(rec); > + } > +} > + > +static void free_block_group_cache(struct cache_tree *block_group_cache) > +{ > + struct cache_extent *cache; > + while (1) { > + struct block_group_record *rec; > + > + cache = find_first_cache_extent(block_group_cache, 0); > + if (!cache) > + break; > + rec = container_of(cache, struct block_group_record, cache); > + if (rec->state == REC_UNCHECKED) { > + fprintf(stderr, > + "Block group[%llu, %u, %llu] " > + "is not referred by any others\n", > + rec->objectid, > + rec->type, > + rec->offset); > + } > + > + remove_cache_extent(block_group_cache, &rec->cache); > + free(rec); > + } > +} > + > +static void free_dev_extent_cache(struct dev_extent_tree *dev_extent_cache) > +{ > + struct cache_dev_extent *cache; > + while (1) { > + struct dev_extent_record *rec; > + > + cache = find_first_cache_dev_extent(dev_extent_cache, 0); > + if (!cache) > + break; > + rec = container_of(cache, struct dev_extent_record, cache); > + if (rec->state == REC_UNCHECKED) { > + fprintf(stderr, > + "Dev extent[%llu, %u, %llu] " > + "is not referred by any others\n", > + rec->objectid, > + rec->type, > + rec->offset); > + } > + > + remove_cache_dev_extent(dev_extent_cache, &rec->cache); > + free(rec); > + } > +} > + > +/* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */ > +static int check_chunk_refs(struct cache_tree *chunk_cache, > + struct cache_tree *block_group_cache, > + struct dev_extent_tree *dev_extent_cache) > +{ > + struct cache_extent *chunk_item; > + struct chunk_record *chunk_rec; > + int err = 0; > + > + chunk_item = find_first_cache_extent(chunk_cache, 0); > + while (chunk_item) { > + struct cache_extent *block_group_item; > + struct block_group_record *block_group_rec; > + > + struct cache_dev_extent *dev_extent_item; > + struct dev_extent_record *dev_extent_rec; > + int i; > + > + chunk_rec = container_of( > + chunk_item, struct chunk_record, cache); > + > + block_group_item = find_cache_extent(block_group_cache, > + chunk_rec->offset, 1); > + if (block_group_item) { > + block_group_rec = container_of(block_group_item, > + struct block_group_record, cache); > + > + if (chunk_rec->length != block_group_rec->offset) > + err = -2; > + if (chunk_rec->offset != block_group_rec->objectid) > + err = -2; > + if (chunk_rec->type != block_group_rec->flags) > + err = -2; > + > + if (err != 0) { > + BUG_ON(1); > + fprintf(stderr, > + "Chunk[%llu, %u, %llu]: " > + "length(%llu), offset(%llu), type(%llu) " > + "mismatch with block group[%llu, %u, %llu]: " > + "offset(%llu), objectid(%llu), flags(%llu)\n", > + chunk_rec->objectid, > + chunk_rec->type, > + chunk_rec->offset, > + chunk_rec->length, > + chunk_rec->offset, > + chunk_rec->type_flags, > + block_group_rec->objectid, > + block_group_rec->type, > + block_group_rec->offset, > + block_group_rec->offset, > + block_group_rec->objectid, > + block_group_rec->flags); > + } > + > + block_group_rec->state = REC_CHECKED; > + chunk_rec->state = REC_CHECKED; > + } else { > + fprintf(stderr, > + "Chunk[%llu, %u, %llu]: " > + "length(%llu), offset(%llu), type(%llu) " > + "is not found in block group\n", > + chunk_rec->objectid, > + chunk_rec->type, > + chunk_rec->offset, > + chunk_rec->length, > + chunk_rec->offset, > + chunk_rec->type_flags); > + err = -1; > + } > + > + for (i = 0; i < chunk_rec->num_stripes; ++i) { > + dev_extent_item = find_cache_dev_extent( > + dev_extent_cache, > + chunk_rec->stripes[i].devid, > + chunk_rec->stripes[i].offset); > + if (dev_extent_item) { > + dev_extent_rec = container_of(dev_extent_item, > + struct dev_extent_record, cache); > + dev_extent_rec->state = REC_CHECKED; > + chunk_rec->state = REC_CHECKED; > + } else { > + fprintf(stderr, > + "Chunk[%llu, %u, %llu] stripe[%llu, %llu]" > + "is not found in dev extent\n", > + chunk_rec->objectid, > + chunk_rec->type, > + chunk_rec->offset, > + chunk_rec->stripes[i].devid, > + chunk_rec->stripes[i].offset); > + err = -1; > + } > + } > + > + chunk_item = next_cache_extent(chunk_item); > + } > + return err; > +} > + > +/* check btrfs_dev_item -> btrfs_dev_extent */ > +static int check_dev_refs(struct cache_tree *dev_cache, > + struct dev_extent_tree *dev_extent_cache) > +{ > + struct cache_extent *dev_item; > + struct dev_record *dev_rec; > + int err = 0; > + > + dev_item = find_first_cache_extent(dev_cache, 0); > + while (dev_item) { > + struct cache_dev_extent *dev_extent_item; > + struct dev_extent_record *dev_extent_rec; > + u64 total_byte = 0; > + > + dev_rec = container_of(dev_item, struct dev_record, cache); > + > + dev_extent_item = find_first_cache_dev_extent( > + dev_extent_cache, 0); > + while (dev_extent_item) { > + dev_extent_rec = container_of(dev_extent_item, > + struct dev_extent_record, cache); > + > + if (dev_extent_rec->objectid == dev_rec->devid) > + total_byte += dev_extent_rec->length; > + > + dev_extent_item = next_cache_dev_extent( > + dev_extent_item); > + } > + > + if (total_byte != dev_rec->byte_used) { > + err = -2; > + > + BUG_ON(1); > + fprintf(stderr, > + "Dev extent''s total-byte(%llu)" > + "is not equal to byte-used(%llu) in" > + "dev[%llu, %u, %llu]\n", > + total_byte, > + dev_rec->byte_used, > + dev_rec->objectid, > + dev_rec->type, > + dev_rec->offset); > + } > + > + dev_rec->state = REC_CHECKED; > + > + dev_item = next_cache_extent(dev_item); > + } > + return err; > +} > + > static int check_extents(struct btrfs_trans_handle *trans, > struct btrfs_root *root, int repair) > { > + struct cache_tree dev_cache; > + struct cache_tree chunk_cache; > + struct cache_tree block_group_cache; > + struct dev_extent_tree dev_extent_cache; > + > struct cache_tree extent_cache; > struct cache_tree seen; > struct cache_tree pending; > @@ -3378,7 +3856,7 @@ static int check_extents(struct btrfs_trans_handle *trans, > struct btrfs_path path; > struct btrfs_key key; > struct btrfs_key found_key; > - int ret; > + int ret, err = 0; > u64 last = 0; > struct block_info *bits; > int bits_nr; > @@ -3386,6 +3864,11 @@ static int check_extents(struct btrfs_trans_handle *trans, > int slot; > struct btrfs_root_item ri; > > + cache_tree_init(&dev_cache); > + cache_tree_init(&chunk_cache); > + cache_tree_init(&block_group_cache); > + dev_extent_tree_init(&dev_extent_cache); > + > cache_tree_init(&extent_cache); > cache_tree_init(&seen); > cache_tree_init(&pending); > @@ -3452,11 +3935,28 @@ static int check_extents(struct btrfs_trans_handle *trans, > btrfs_release_path(root, &path); > while(1) { > ret = run_next_block(root, bits, bits_nr, &last, &pending, > - &seen, &reada, &nodes, &extent_cache); > + &seen, &reada, &nodes, &extent_cache, > + &chunk_cache, &dev_cache, > + &block_group_cache, &dev_extent_cache); > if (ret != 0) > break; > } > ret = check_extent_refs(trans, root, &extent_cache, repair); > + if (ret) { > + err = 1; > + fprintf(stderr, "Errors found in extent checking\n"); > + } > + ret = check_chunk_refs(&chunk_cache, > + &block_group_cache, &dev_extent_cache); > + if (ret) { > + err = 1; > + fprintf(stderr, "Errors found in chunk refs checking\n"); > + } > + ret = check_dev_refs(&dev_cache, &dev_extent_cache); > + if (ret) { > + err = 1; > + fprintf(stderr, "Errors found in dev refs checking\n"); > + } > > if (repair) { > free_corrupt_blocks(root->fs_info); > @@ -3465,7 +3965,12 @@ static int check_extents(struct btrfs_trans_handle *trans, > root->fs_info->corrupt_blocks = NULL; > } > > - return ret; > + free_chunk_cache(&chunk_cache); > + free_dev_cache(&dev_cache); > + free_block_group_cache(&block_group_cache); > + free_dev_extent_cache(&dev_extent_cache); > + > + return err; > } > > static void print_usage(void) > diff --git a/dev-extent-cache.c b/dev-extent-cache.c > new file mode 100644 > index 0000000..1f0d047 > --- /dev/null > +++ b/dev-extent-cache.c > @@ -0,0 +1,188 @@ > +/* > + * Copyright (C) 2012 Fujitsu. All rights reserved. > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public > + * License v2 as published by the Free Software Foundation. > + * > + * This program is distributed in the hope that it will be useful, > + * but WITHOUT ANY WARRANTY; without even the implied warranty of > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU > + * General Public License for more details. > + * > + * You should have received a copy of the GNU General Public > + * License along with this program; if not, write to the > + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, > + * Boston, MA 021110-1307, USA. > + */ > +#include <stdio.h> > +#include <stdlib.h> > +#include "kerncompat.h" > +#include "dev-extent-cache.h" > + > +void dev_extent_tree_init(struct dev_extent_tree *tree) > +{ > + tree->root.rb_node = NULL; > +} > + > +static struct rb_node *tree_insert(struct rb_root *root, u64 devno, > + u64 offset, struct rb_node *node) > +{ > + struct rb_node **p = &root->rb_node; > + struct rb_node *parent = NULL; > + struct cache_dev_extent *entry; > + > + while (*p) { > + parent = *p; > + entry = rb_entry(parent, struct cache_dev_extent, rb_node); > + > + if (devno == entry->devno) { > + if (offset < entry->offset) > + p = &(*p)->rb_left; > + else if (offset > entry->offset) > + p = &(*p)->rb_right; > + else > + return parent; > + } else { > + if (devno < entry->devno) > + p = &(*p)->rb_left; > + else if (devno > entry->devno) > + p = &(*p)->rb_right; > + else > + return parent; > + } > + } > + > + entry = rb_entry(parent, struct cache_dev_extent, rb_node); > + rb_link_node(node, parent, p); > + rb_insert_color(node, root); > + return NULL; > +} > + > +static struct rb_node *__tree_search(struct rb_root *root, u64 devno, > + u64 offset, struct rb_node **prev_ret) > +{ > + struct rb_node *n = root->rb_node; > + struct rb_node *prev = NULL; > + struct cache_dev_extent *entry; > + struct cache_dev_extent *prev_entry = NULL; > + > + while (n) { > + entry = rb_entry(n, struct cache_dev_extent, rb_node); > + prev = n; > + prev_entry = entry; > + > + if (devno == entry->devno) { > + if (offset < entry->offset) > + n = n->rb_left; > + else if (offset > entry->offset) > + n = n->rb_right; > + else > + return n; > + } else { > + if (devno < entry->devno) > + n = n->rb_left; > + else if (devno > entry->devno) > + n = n->rb_right; > + else > + return n; > + } > + } > + if (!prev_ret) > + return NULL; > + > + while (prev && devno >= prev_entry->devno + prev_entry->offset) { > + prev = rb_next(prev); > + prev_entry = rb_entry(prev, struct cache_dev_extent, rb_node); > + } > + *prev_ret = prev; > + return NULL; > +} > + > +struct cache_dev_extent *alloc_cache_dev_extent(u64 devno, u64 offset) > +{ > + struct cache_dev_extent *pe = malloc(sizeof(*pe)); > + > + if (!pe) > + return pe; > + pe->devno = devno; > + pe->offset = offset; > + return pe; > +} > + > +int insert_existing_cache_dev_extent(struct dev_extent_tree *tree, > + struct cache_dev_extent *pe) > +{ > + struct rb_node *found; > + > + found = tree_insert(&tree->root, pe->devno, pe->offset, &pe->rb_node); > + if (found) > + return -EEXIST; > + > + return 0; > +} > + > +int insert_cache_dev_extent(struct dev_extent_tree *tree, u64 devno, u64 offset) > +{ > + struct cache_dev_extent *pe = alloc_cache_dev_extent(devno, offset); > + int ret; > + ret = insert_existing_cache_dev_extent(tree, pe); > + if (ret) > + free(pe); > + return ret; > +} > + > +struct cache_dev_extent *find_cache_dev_extent(struct dev_extent_tree *tree, > + u64 devno, u64 offset) > +{ > + struct rb_node *prev; > + struct rb_node *ret; > + struct cache_dev_extent *entry; > + ret = __tree_search(&tree->root, devno, offset, &prev); > + if (!ret) > + return NULL; > + > + entry = rb_entry(ret, struct cache_dev_extent, rb_node); > + return entry; > +} > + > +struct cache_dev_extent *find_first_cache_dev_extent( > + struct dev_extent_tree *tree, u64 devno) > +{ > + struct rb_node *prev; > + struct rb_node *ret; > + struct cache_dev_extent *entry; > + > + ret = __tree_search(&tree->root, devno, 1, &prev); > + if (!ret) > + ret = prev; > + if (!ret) > + return NULL; > + entry = rb_entry(ret, struct cache_dev_extent, rb_node); > + return entry; > +} > + > +struct cache_dev_extent *prev_cache_dev_extent(struct cache_dev_extent *pe) > +{ > + struct rb_node *node = rb_prev(&pe->rb_node); > + > + if (!node) > + return NULL; > + return rb_entry(node, struct cache_dev_extent, rb_node); > +} > + > +struct cache_dev_extent *next_cache_dev_extent(struct cache_dev_extent *pe) > +{ > + struct rb_node *node = rb_next(&pe->rb_node); > + > + if (!node) > + return NULL; > + return rb_entry(node, struct cache_dev_extent, rb_node); > +} > + > +void remove_cache_dev_extent(struct dev_extent_tree *tree, > + struct cache_dev_extent *pe) > +{ > + rb_erase(&pe->rb_node, &tree->root); > +} > + > diff --git a/dev-extent-cache.h b/dev-extent-cache.h > new file mode 100644 > index 0000000..9be2e2f > --- /dev/null > +++ b/dev-extent-cache.h > @@ -0,0 +1,60 @@ > +/* > + * Copyright (C) 2012 Fujitsu. All rights reserved. > + * > + * This program is free software; you can redistribute it and/or > + * modify it under the terms of the GNU General Public > + * License v2 as published by the Free Software Foundation. > + * > + * This program is distributed in the hope that it will be useful, > + * but WITHOUT ANY WARRANTY; without even the implied warranty of > + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU > + * General Public License for more details. > + * > + * You should have received a copy of the GNU General Public > + * License along with this program; if not, write to the > + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, > + * Boston, MA 021110-1307, USA. > + */ > + > +#ifndef __PENDING_DEV_EXTENT__ > +#define __PENDING_DEV_EXTENT__ > +#include "kerncompat.h" > +#include "rbtree.h" > + > +struct dev_extent_tree { > + struct rb_root root; > +}; > + > +struct cache_dev_extent { > + struct rb_node rb_node; > + u64 devno; > + u64 offset; > +}; > + > +void dev_extent_tree_init(struct dev_extent_tree *tree); > +void remove_cache_dev_extent(struct dev_extent_tree *tree, > + struct cache_dev_extent *pe); > +struct cache_dev_extent *find_first_cache_dev_extent( > + struct dev_extent_tree *tree, u64 devno); > +struct cache_dev_extent *prev_cache_dev_extent(struct cache_dev_extent *pe); > +struct cache_dev_extent *next_cache_dev_extent(struct cache_dev_extent *pe); > +struct cache_dev_extent *find_cache_dev_extent(struct dev_extent_tree *tree, > + u64 devno, u64 offset); > +int insert_cache_dev_extent(struct dev_extent_tree *tree, > + u64 devno, u64 offset); > +int insert_existing_cache_dev_extent(struct dev_extent_tree *tree, > + struct cache_dev_extent *pe); > + > +static inline int dev_extent_tree_empty(struct dev_extent_tree *tree) > +{ > + return RB_EMPTY_ROOT(&tree->root); > +} > + > +static inline void free_cache_dev_extent(struct cache_dev_extent *pe) > +{ > + free(pe); > +} > + > +struct cache_dev_extent *alloc_pending_dev_extent(u64 devno, u64 offset); > + > +#endif >-- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html