This adds nilfs_bmap_compare() function and its helper routine
(nilfs_bmap_do_compare function). The nilfs_bmap_compare function
enumerates changes on the data blocks that given two bmap objects
hold. These functions are available to efficiently find out changes
on meta-data or user data between two checkpoints.
Signed-off-by: Ryusuke Konishi <konishi.ryusuke@xxxxxxxxxxxxx>
---
fs/nilfs2/bmap.c | 154 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
fs/nilfs2/bmap.h | 15 +++++
2 files changed, 169 insertions(+), 0 deletions(-)
diff --git a/fs/nilfs2/bmap.c b/fs/nilfs2/bmap.c
index aadbd0b..84c4866 100644
--- a/fs/nilfs2/bmap.c
+++ b/fs/nilfs2/bmap.c
@@ -422,6 +422,160 @@ int nilfs_bmap_test_and_clear_dirty(struct nilfs_bmap *bmap)
return ret;
}
+static ssize_t nilfs_bmap_do_compare(struct nilfs_bmap *bmap1,
+ struct nilfs_bmap *bmap2, __u64 start,
+ struct nilfs_bmap_diff *diffs,
+ size_t maxdiffs)
+{
+ __u64 key1, key2;
+ __u64 ptr1, ptr2;
+ void *ctx1, *ctx2;
+ ssize_t n = 0;
+ int next1 = false, next2 = false;
+ int done1 = false, done2 = false;
+ int ret;
+
+ key1 = start;
+ ret = bmap1->b_ops->bop_find(bmap1, &key1, &ptr1, &ctx1);
+ if (ret < 0) {
+ if (ret != -ENOENT) {
+ n = ret;
+ goto out;
+ }
+ done1 = true;
+ ctx1 = NULL; /* ensure ->bop_find_close(bmap1, ctx1) safe */
+ }
+
+ key2 = start;
+ ret = bmap2->b_ops->bop_find(bmap2, &key2, &ptr2, &ctx2);
+ if (ret < 0) {
+ if (ret != -ENOENT) {
+ n = ret;
+ goto out;
+ }
+ done2 = true;
+ ctx2 = NULL; /* ensure ->bop_find_close(bmap2, ctx2) safe */
+ }
+
+ while (1) {
+ if (done1) {
+ if (done2)
+ break;
+
+ diffs[n].key = key2;
+ diffs[n].ptr1 = NILFS_BMAP_INVALID_PTR;
+ diffs[n].ptr2 = ptr2;
+ next2 = true;
+ } else if (done2) {
+ diffs[n].key = key1;
+ diffs[n].ptr1 = ptr1;
+ diffs[n].ptr2 = NILFS_BMAP_INVALID_PTR;
+ next1 = true;
+ } else if (key1 == key2) {
+ next1 = true;
+ next2 = true;
+
+ if (ptr1 == ptr2)
+ goto lookup_next;
+
+ diffs[n].key = key1;
+ diffs[n].ptr1 = ptr1;
+ diffs[n].ptr2 = ptr2;
+ } else if (key1 < key2) {
+ diffs[n].key = key1;
+ diffs[n].ptr1 = ptr1;
+ diffs[n].ptr2 = NILFS_BMAP_INVALID_PTR;
+ next1 = true;
+ } else /* key1 > key2 */ {
+ diffs[n].key = key2;
+ diffs[n].ptr1 = NILFS_BMAP_INVALID_PTR;
+ diffs[n].ptr2 = ptr2;
+ next2 = true;
+ }
+
+ n++;
+ if (n == maxdiffs)
+ break;
+
+ lookup_next:
+ if (next1) {
+ ret = bmap1->b_ops->bop_find_next(bmap1, &key1,
+ &ptr1, ctx1);
+ if (ret < 0) {
+ if (ret != -ENOENT) {
+ n = ret;
+ break;
+ }
+ done1 = true;
+ }
+ next1 = false;
+ }
+ if (next2) {
+ ret = bmap2->b_ops->bop_find_next(bmap2, &key2,
+ &ptr2, ctx2);
+ if (ret < 0) {
+ if (ret != -ENOENT) {
+ n = ret;
+ break;
+ }
+ done2 = true;
+ }
+ next2 = false;
+ }
+ }
+out:
+ bmap2->b_ops->bop_find_close(bmap2, ctx2);
+ bmap1->b_ops->bop_find_close(bmap1, ctx1);
+ return n;
+}
+
+/**
+ * nilfs_bmap_compare - compare two bmaps and find their differences
+ * @bmap1: source bmap
+ * @bmap2: target bmap
+ * @start: start key
+ * @diffs: pointer to an array of nilfs_bmap_diff structures
+ * @maxdiffs: number of nilfs_bmap_diff structures
+ *
+ * Description: nilfs_bmap_compare() compares two versions of bmap and
+ * stores their differences in nilfs_bmap_diff structures given by
+ * @diffs and @maxdiffs.
+ *
+ * Return Value: On success, number of items stored to @diffs are
+ * returned. On error, one of the following negative error codes are
+ * returned.
+ *
+ * %-EIO - I/O error.
+ *
+ * %-ENOMEM - Insufficient amount of memory available.
+ */
+ssize_t nilfs_bmap_compare(struct nilfs_bmap *bmap1, struct nilfs_bmap *bmap2,
+ __u64 start, struct nilfs_bmap_diff *diffs,
+ size_t maxdiffs)
+{
+ ssize_t ret;
+
+ if (maxdiffs == 0)
+ return 0;
+
+ /*
+ * hold semaphore with smaller address first to avoid possible
+ * deadlock problem.
+ */
+ if (bmap1 < bmap2) {
+ down_read(&bmap1->b_sem);
+ down_read(&bmap2->b_sem);
+ } else {
+ down_read(&bmap2->b_sem);
+ down_read(&bmap1->b_sem);
+ }
+
+ ret = nilfs_bmap_do_compare(bmap1, bmap2, start, diffs, maxdiffs);
+
+ up_read(&bmap1->b_sem);
+ up_read(&bmap2->b_sem);
+ return ret;
+}
/*
* Internal use only
diff --git a/fs/nilfs2/bmap.h b/fs/nilfs2/bmap.h
index cff22c2..2e57537 100644
--- a/fs/nilfs2/bmap.h
+++ b/fs/nilfs2/bmap.h
@@ -56,6 +56,18 @@ struct nilfs_bmap_stats {
};
/**
+ * struct nilfs_bmap_diff - array item to store bmap comparison result
+ * @key: key index
+ * @ptr: bmap pointer 1
+ * @ptr: bmap pointer 2
+ */
+struct nilfs_bmap_diff {
+ __u64 key;
+ __u64 ptr1;
+ __u64 ptr2;
+};
+
+/**
* struct nilfs_bmap_operations - bmap operation table
*/
struct nilfs_bmap_operations {
@@ -162,6 +174,9 @@ int nilfs_bmap_assign(struct nilfs_bmap *, struct buffer_head **,
unsigned long, union nilfs_binfo *);
int nilfs_bmap_lookup_at_level(struct nilfs_bmap *, __u64, int, __u64 *);
int nilfs_bmap_mark(struct nilfs_bmap *, __u64, int);
+ssize_t nilfs_bmap_compare(struct nilfs_bmap *bmap1, struct nilfs_bmap *bmap2,
+ __u64 start, struct nilfs_bmap_diff *diffs,
+ size_t maxdiffs);
void nilfs_bmap_init_gc(struct nilfs_bmap *);
--
1.7.3.5
--
To unsubscribe from this list: send the line "unsubscribe linux-nilfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
