* [PATCH 01/14] btrfs: dedup: Introduce dedup framework and its header
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 02/14] btrfs: dedup: Introduce function to initialize dedup info Qu Wenruo
` (12 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Introduce the header for btrfs online(write time) de-duplication
framework and needed header.
The new de-duplication framework is going to support 2 different dedup
method and 1 dedup hash.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/ctree.h | 3 ++
fs/btrfs/dedup.h | 128 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 131 insertions(+)
create mode 100644 fs/btrfs/dedup.h
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 4c23f34..62fed1d 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1816,6 +1816,9 @@ struct btrfs_fs_info {
* and will be latter freed. Protected by fs_info->chunk_mutex.
*/
struct list_head pinned_chunks;
+
+ /* reference to inband de-duplication info */
+ struct btrfs_dedup_info *dedup_info;
};
struct btrfs_subvolume_writers {
diff --git a/fs/btrfs/dedup.h b/fs/btrfs/dedup.h
new file mode 100644
index 0000000..fd2e392
--- /dev/null
+++ b/fs/btrfs/dedup.h
@@ -0,0 +1,128 @@
+/*
+ * Copyright (C) 2015 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 __BTRFS_DEDUP__
+#define __BTRFS_DEDUP__
+
+#include <linux/btrfs.h>
+#include <crypto/hash.h>
+
+/*
+ * Dedup storage backend
+ * On disk is persist storage but overhead is large
+ * In memory is fast but will lose all its hash on umount
+ */
+#define BTRFS_DEDUP_BACKEND_INMEMORY 0
+#define BTRFS_DEDUP_BACKEND_ONDISK 1
+#define BTRFS_DEDUP_BACKEND_LAST 2
+
+/* Dedup block size limit and default value */
+#define BTRFS_DEDUP_BLOCKSIZE_MAX (128 * 1024)
+#define BTRFS_DEDUP_BLOCKSIZE_MIN (16 * 1024)
+#define BTRFS_DEDUP_BLOCKSIZE_DEFAULT (32 * 1024)
+
+/* Hash algorithm, only support SHA256 yet */
+#define BTRFS_DEDUP_HASH_SHA256 0
+
+static int btrfs_dedup_sizes[] = { 32 };
+
+struct btrfs_dedup_hash {
+ /*
+ * hash_node is for hash -> extent search(dedup search).
+ * bytenr_node is for extent(bytenr) -> hash search(free extent).
+ * lru_list is to maintain low memory usage. Currently they are
+ * only used in in-memory dedup mode.
+ */
+ struct rb_node hash_node;
+ struct rb_node bytenr_node;
+ struct list_head lru_list;
+
+ u64 bytenr;
+ u64 num_bytes;
+
+ /* last field is a variable length array of dedup hash */
+ u8 hash[];
+};
+
+struct btrfs_dedup_info {
+ /* dedup blocksize */
+ u64 blocksize;
+ u16 backend;
+ u16 hash_type;
+
+ /* Hash driver */
+ struct crypto_shash *dedup_driver;
+
+ /* following members are only used in in-memory dedup mode */
+ struct rb_root hash_root;
+ struct rb_root bytenr_root;
+ struct list_head lru_list;
+ spinlock_t lock;
+ u64 limit_nr;
+ u64 current_nr;
+};
+
+struct btrfs_trans_handle;
+
+int btrfs_dedup_hash_size(u16 type);
+struct btrfs_dedup_hash *btrfs_dedup_alloc_hash(u16 type);
+
+/*
+ * Initial inband dedup info
+ * Called at either dedup enable or mount time.
+ */
+int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
+ u64 blocksize, u64 limit);
+
+/*
+ * Disable dedup and invalidate all its dedup data.
+ * Called at dedup disable time.
+ */
+int btrfs_dedup_disable(struct btrfs_fs_info *fs_info);
+
+/*
+ * Calculate hash for dedup.
+ * Caller must ensure [start, start + dedup_bs) has valid data.
+ */
+int btrfs_dedup_calc_hash(struct btrfs_root *root, struct inode *inode,
+ u64 start, struct btrfs_dedup_hash *hash);
+
+/*
+ * Search for duplicated extents by calculated hash
+ * Caller must call btrfs_dedup_calc_hash() first to get the hash.
+ *
+ * @inode: the inode for we are writing
+ * @file_pos: offset inside the inode
+ * As we will increase extent ref immediately after a hash match,
+ * we need @file_pos and @inode in this case.
+ *
+ * Return > 0 for a hash match, and the extent ref will be
+ * INCREASED.
+ * Return 0 for a hash miss. Nothing is done
+ */
+int btrfs_dedup_search(struct inode *inode, u64 file_pos,
+ struct btrfs_dedup_hash *hash);
+
+/* Add a dedup hash into dedup tree */
+int btrfs_dedup_add(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ struct btrfs_dedup_hash *hash);
+
+/* Remove a dedup hash from dedup tree */
+int btrfs_dedup_del(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ u64 bytenr);
+#endif
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 02/14] btrfs: dedup: Introduce function to initialize dedup info
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
2015-12-29 8:01 ` [PATCH 01/14] btrfs: dedup: Introduce dedup framework and its header Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 03/14] btrfs: dedup: Introduce function to add hash into in-memory tree Qu Wenruo
` (11 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Add generic function to initialize dedup info.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/Makefile | 2 +-
fs/btrfs/dedup.c | 96 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
fs/btrfs/dedup.h | 14 ++++++--
3 files changed, 109 insertions(+), 3 deletions(-)
create mode 100644 fs/btrfs/dedup.c
diff --git a/fs/btrfs/Makefile b/fs/btrfs/Makefile
index 6d1d0b9..a8bd917 100644
--- a/fs/btrfs/Makefile
+++ b/fs/btrfs/Makefile
@@ -9,7 +9,7 @@ btrfs-y += super.o ctree.o extent-tree.o print-tree.o root-tree.o dir-item.o \
export.o tree-log.o free-space-cache.o zlib.o lzo.o \
compression.o delayed-ref.o relocation.o delayed-inode.o scrub.o \
reada.o backref.o ulist.o qgroup.o send.o dev-replace.o raid56.o \
- uuid-tree.o props.o hash.o
+ uuid-tree.o props.o hash.o dedup.o
btrfs-$(CONFIG_BTRFS_FS_POSIX_ACL) += acl.o
btrfs-$(CONFIG_BTRFS_FS_CHECK_INTEGRITY) += check-integrity.o
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
new file mode 100644
index 0000000..c1fadff
--- /dev/null
+++ b/fs/btrfs/dedup.c
@@ -0,0 +1,96 @@
+/*
+ * Copyright (C) 2015 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 "ctree.h"
+#include "dedup.h"
+#include "btrfs_inode.h"
+#include "transaction.h"
+#include "delayed-ref.h"
+
+int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
+ u64 blocksize, u64 limit)
+{
+ struct btrfs_dedup_info *dedup_info;
+ int ret = 0;
+
+ /* Sanity check */
+ if (blocksize > BTRFS_DEDUP_BLOCKSIZE_MAX ||
+ blocksize < BTRFS_DEDUP_BLOCKSIZE_MIN ||
+ blocksize < fs_info->tree_root->sectorsize ||
+ !is_power_of_2(blocksize))
+ return -EINVAL;
+ if (type > ARRAY_SIZE(btrfs_dedup_sizes))
+ return -EINVAL;
+ if (backend >= BTRFS_DEDUP_BACKEND_LAST)
+ return -EINVAL;
+ if (backend == BTRFS_DEDUP_BACKEND_INMEMORY && limit == 0)
+ limit = 4096; /* default value */
+ if (backend == BTRFS_DEDUP_BACKEND_ONDISK && limit != 0)
+ limit = 0;
+
+ if (fs_info->dedup_info) {
+ dedup_info = fs_info->dedup_info;
+
+ /* Check if we are re-enable for different dedup config */
+ if (dedup_info->blocksize != blocksize ||
+ dedup_info->hash_type != type ||
+ dedup_info->backend != backend) {
+ btrfs_dedup_disable(fs_info);
+ goto enable;
+ }
+
+ /* On-fly limit change is OK */
+ spin_lock(&dedup_info->lock);
+ fs_info->dedup_info->limit_nr = limit;
+ spin_unlock(&dedup_info->lock);
+ return 0;
+ }
+
+enable:
+ fs_info->dedup_info = kzalloc(sizeof(*dedup_info), GFP_NOFS);
+ if (!fs_info->dedup_info)
+ return -ENOMEM;
+
+ dedup_info = fs_info->dedup_info;
+
+ dedup_info->hash_type = type;
+ dedup_info->backend = backend;
+ dedup_info->blocksize = blocksize;
+ dedup_info->limit_nr = limit;
+
+ /* Only support SHA256 yet */
+ dedup_info->dedup_driver = crypto_alloc_shash("sha256", 0, 0);
+ if (IS_ERR(dedup_info->dedup_driver)) {
+ btrfs_err(fs_info, "failed to init sha256 driver");
+ ret = PTR_ERR(dedup_info->dedup_driver);
+ goto out;
+ }
+
+ dedup_info->hash_root = RB_ROOT;
+ dedup_info->bytenr_root = RB_ROOT;
+ dedup_info->current_nr = 0;
+ INIT_LIST_HEAD(&dedup_info->lru_list);
+ spin_lock_init(&dedup_info->lock);
+
+ fs_info->dedup_info = dedup_info;
+out:
+ if (ret < 0) {
+ kfree(dedup_info);
+ fs_info->dedup_info = NULL;
+ }
+ return ret;
+}
diff --git a/fs/btrfs/dedup.h b/fs/btrfs/dedup.h
index fd2e392..3cd6d14 100644
--- a/fs/btrfs/dedup.h
+++ b/fs/btrfs/dedup.h
@@ -79,8 +79,18 @@ struct btrfs_dedup_info {
struct btrfs_trans_handle;
-int btrfs_dedup_hash_size(u16 type);
-struct btrfs_dedup_hash *btrfs_dedup_alloc_hash(u16 type);
+static inline int btrfs_dedup_hash_size(u16 type)
+{
+ if (WARN_ON(type >= ARRAY_SIZE(btrfs_dedup_sizes)))
+ return -EINVAL;
+ return sizeof(struct btrfs_dedup_hash) + btrfs_dedup_sizes[type];
+}
+
+static inline struct btrfs_dedup_hash *btrfs_dedup_alloc_hash(u16 type)
+{
+ return kzalloc(btrfs_dedup_hash_size(type), GFP_NOFS);
+}
+
/*
* Initial inband dedup info
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 03/14] btrfs: dedup: Introduce function to add hash into in-memory tree
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
2015-12-29 8:01 ` [PATCH 01/14] btrfs: dedup: Introduce dedup framework and its header Qu Wenruo
2015-12-29 8:01 ` [PATCH 02/14] btrfs: dedup: Introduce function to initialize dedup info Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 04/14] btrfs: dedup: Introduce function to remove hash from " Qu Wenruo
` (10 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Introduce static function inmem_add() to add hash into in-memory tree.
And now we can implement the btrfs_dedup_add() interface.
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 116 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 116 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index c1fadff..cafbce1 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -94,3 +94,119 @@ out:
}
return ret;
}
+
+static int inmem_insert_hash(struct rb_root *root,
+ struct btrfs_dedup_hash *hash, int hash_len)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct btrfs_dedup_hash *entry = NULL;
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct btrfs_dedup_hash,
+ hash_node);
+ if (memcmp(hash->hash, entry->hash, hash_len) < 0)
+ p = &(*p)->rb_left;
+ else if (memcmp(hash->hash, entry->hash, hash_len) > 0)
+ p = &(*p)->rb_right;
+ else
+ return 1;
+ }
+ rb_link_node(&hash->hash_node, parent, p);
+ rb_insert_color(&hash->hash_node, root);
+ return 0;
+}
+
+static int inmem_insert_bytenr(struct rb_root *root,
+ struct btrfs_dedup_hash *hash)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct btrfs_dedup_hash *entry = NULL;
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct btrfs_dedup_hash, bytenr_node);
+ if (hash->bytenr < entry->bytenr)
+ p = &(*p)->rb_left;
+ else if (hash->bytenr > entry->bytenr)
+ p = &(*p)->rb_right;
+ else
+ return 1;
+ }
+ rb_link_node(&hash->bytenr_node, parent, p);
+ rb_insert_color(&hash->bytenr_node, root);
+ return 0;
+}
+
+static void __inmem_del(struct btrfs_dedup_info *dedup_info,
+ struct btrfs_dedup_hash *hash)
+{
+ list_del(&hash->lru_list);
+ rb_erase(&hash->hash_node, &dedup_info->hash_root);
+ rb_erase(&hash->bytenr_node, &dedup_info->bytenr_root);
+
+ if (!WARN_ON(dedup_info->current_nr == 0))
+ dedup_info->current_nr--;
+
+ kfree(hash);
+}
+
+/*
+ * Insert a hash into in-memory dedup tree
+ * Will remove exceeding last recent use hash.
+ *
+ * If the hash mathced with existing one, we won't insert it, to
+ * save memory
+ */
+static int inmem_add(struct btrfs_dedup_info *dedup_info,
+ struct btrfs_dedup_hash *hash)
+{
+ int ret = 0;
+ u16 type = dedup_info->hash_type;
+
+ spin_lock(&dedup_info->lock);
+ ret = inmem_insert_hash(&dedup_info->hash_root, hash,
+ btrfs_dedup_sizes[type]);
+ if (ret > 0) {
+ /* Same hash already in tree, don't insert */
+ kfree(hash);
+ ret = 0;
+ goto out;
+ }
+
+ inmem_insert_bytenr(&dedup_info->bytenr_root, hash);
+
+ list_add(&hash->lru_list, &dedup_info->lru_list);
+ dedup_info->current_nr++;
+
+ /* Remove the last dedup hash if we exceed limit */
+ while (dedup_info->current_nr > dedup_info->limit_nr) {
+ struct btrfs_dedup_hash *last;
+
+ last = list_entry(dedup_info->lru_list.prev,
+ struct btrfs_dedup_hash, lru_list);
+ __inmem_del(dedup_info, last);
+ }
+out:
+ spin_unlock(&dedup_info->lock);
+ return 0;
+}
+
+int btrfs_dedup_add(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ struct btrfs_dedup_hash *hash)
+{
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+
+ if (!dedup_info || !hash)
+ return 0;
+
+ if (WARN_ON(hash->bytenr == 0))
+ return -EINVAL;
+
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
+ return inmem_add(dedup_info, hash);
+ return -EINVAL;
+}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 04/14] btrfs: dedup: Introduce function to remove hash from in-memory tree
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (2 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 03/14] btrfs: dedup: Introduce function to add hash into in-memory tree Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 05/14] btrfs: dedup: Introduce function to search for an existing hash Qu Wenruo
` (9 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Introduce static function inmem_del() to remove hash from in-memory
dedup tree.
And implement btrfs_dedup_del() and btrfs_dedup_destroy() interfaces.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 77 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index cafbce1..658c493 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -210,3 +210,80 @@ int btrfs_dedup_add(struct btrfs_trans_handle *trans, struct btrfs_root *root,
return inmem_add(dedup_info, hash);
return -EINVAL;
}
+
+static struct btrfs_dedup_hash *
+inmem_search_bytenr(struct btrfs_dedup_info *dedup_info, u64 bytenr)
+{
+ struct rb_node **p = &dedup_info->bytenr_root.rb_node;
+ struct rb_node *parent = NULL;
+ struct btrfs_dedup_hash *entry = NULL;
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct btrfs_dedup_hash, bytenr_node);
+
+ if (bytenr < entry->bytenr)
+ p = &(*p)->rb_left;
+ else if (bytenr > entry->bytenr)
+ p = &(*p)->rb_right;
+ else
+ return entry;
+ }
+
+ return NULL;
+}
+
+/* Delete a hash from in-memory dedup tree */
+static int inmem_del(struct btrfs_dedup_info *dedup_info, u64 bytenr)
+{
+ struct btrfs_dedup_hash *hash;
+
+ spin_lock(&dedup_info->lock);
+ hash = inmem_search_bytenr(dedup_info, bytenr);
+ if (!hash) {
+ spin_unlock(&dedup_info->lock);
+ return 0;
+ }
+
+ __inmem_del(dedup_info, hash);
+ spin_unlock(&dedup_info->lock);
+ return 0;
+}
+
+/* Remove a dedup hash from dedup tree */
+int btrfs_dedup_del(struct btrfs_trans_handle *trans, struct btrfs_root *root,
+ u64 bytenr)
+{
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+
+ if (!dedup_info)
+ return 0;
+
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
+ return inmem_del(dedup_info, bytenr);
+ return -EINVAL;
+}
+
+static void inmem_destroy(struct btrfs_fs_info *fs_info)
+{
+ struct btrfs_dedup_hash *entry, *tmp;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+
+ spin_lock(&dedup_info->lock);
+ list_for_each_entry_safe(entry, tmp, &dedup_info->lru_list, lru_list)
+ __inmem_del(dedup_info, entry);
+ spin_unlock(&dedup_info->lock);
+}
+
+int btrfs_dedup_disable(struct btrfs_fs_info *fs_info)
+{
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+
+ if (!dedup_info)
+ return 0;
+
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
+ inmem_destroy(fs_info);
+ return 0;
+}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 05/14] btrfs: dedup: Introduce function to search for an existing hash
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (3 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 04/14] btrfs: dedup: Introduce function to remove hash from " Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 06/14] btrfs: dedup: Implement btrfs_dedup_calc_hash interface Qu Wenruo
` (8 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Introduce static function inmem_search() to handle the job for in-memory
hash tree.
The trick is, we must ensure the delayed ref head is not being run at
the time we search the for the hash.
With inmem_search(), we can implement the btrfs_dedup_search()
interface.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 154 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 154 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index 658c493..4b8676b 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -287,3 +287,157 @@ int btrfs_dedup_disable(struct btrfs_fs_info *fs_info)
inmem_destroy(fs_info);
return 0;
}
+
+/*
+ * Caller must ensure the corresponding ref head is not being run.
+ */
+static struct btrfs_dedup_hash *
+inmem_search_hash(struct btrfs_dedup_info *dedup_info, u8 *hash)
+{
+ struct rb_node **p = &dedup_info->hash_root.rb_node;
+ struct rb_node *parent = NULL;
+ struct btrfs_dedup_hash *entry = NULL;
+ u16 hash_type = dedup_info->hash_type;
+ int hash_len = btrfs_dedup_sizes[hash_type];
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct btrfs_dedup_hash, hash_node);
+
+ if (memcmp(hash, entry->hash, hash_len) < 0) {
+ p = &(*p)->rb_left;
+ } else if (memcmp(hash, entry->hash, hash_len) > 0) {
+ p = &(*p)->rb_right;
+ } else {
+ /* Found, need to re-add it to LRU list head */
+ list_del(&entry->lru_list);
+ list_add(&entry->lru_list, &dedup_info->lru_list);
+ return entry;
+ }
+ }
+ return NULL;
+}
+
+static int inmem_search(struct inode *inode, u64 file_pos,
+ struct btrfs_dedup_hash *hash)
+{
+ int ret;
+ struct btrfs_root *root = BTRFS_I(inode)->root;
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_trans_handle *trans;
+ struct btrfs_delayed_ref_root *delayed_refs;
+ struct btrfs_delayed_ref_head *head;
+ struct btrfs_dedup_hash *found_hash;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+ u64 bytenr, num_bytes;
+
+ spin_lock(&dedup_info->lock);
+ found_hash = inmem_search_hash(dedup_info, hash->hash);
+ /* If we don't find a duplicated extent, just return. */
+ if (!found_hash) {
+ spin_unlock(&dedup_info->lock);
+ return 0;
+ }
+ bytenr = found_hash->bytenr;
+ num_bytes = found_hash->num_bytes;
+ spin_unlock(&dedup_info->lock);
+
+ trans = btrfs_join_transaction(root);
+ if (IS_ERR(trans))
+ return PTR_ERR(trans);
+
+again:
+ delayed_refs = &trans->transaction->delayed_refs;
+
+ spin_lock(&delayed_refs->lock);
+ head = btrfs_find_delayed_ref_head(trans, bytenr);
+ if (!head || head->processing == 1) {
+ /*
+ * Somebody else may be trying to run the refs, the found
+ * duplicated extent may be freed, so here we just
+ * choose to abort this dedup handle.
+ * XXX: we need to find a better method to improve it.
+ */
+ spin_unlock(&delayed_refs->lock);
+ goto out;
+ }
+
+ /*
+ * we may have dropped the delayed_refs->lock to get the head mutex
+ * lock, and that might have given someone else time to free the head.
+ * If that's true, it has been removed from our list and we can move on.
+ */
+ ret = btrfs_delayed_ref_lock(trans, head);
+ spin_unlock(&delayed_refs->lock);
+ if (ret == -EAGAIN) {
+ spin_lock(&dedup_info->lock);
+ found_hash = inmem_search_hash(dedup_info, hash->hash);
+ if (!found_hash) {
+ spin_unlock(&dedup_info->lock);
+ goto out;
+ }
+ bytenr = found_hash->bytenr;
+ num_bytes = found_hash->num_bytes;
+ spin_unlock(&dedup_info->lock);
+ goto again;
+ }
+
+ /* We still need to look up the hash again... */
+ spin_lock(&dedup_info->lock);
+ found_hash = inmem_search_hash(dedup_info, hash->hash);
+ if (!found_hash) {
+ spin_unlock(&dedup_info->lock);
+ mutex_unlock(&head->mutex);
+ goto out;
+ }
+
+ /* The bytenr has changed, we need to re-lock the delayed_ref head */
+ if (found_hash->bytenr != bytenr) {
+ bytenr = found_hash->bytenr;
+ num_bytes = found_hash->num_bytes;
+ spin_unlock(&dedup_info->lock);
+ mutex_unlock(&head->mutex);
+ goto again;
+ }
+
+ hash->bytenr = bytenr;
+ hash->num_bytes = num_bytes;
+ spin_unlock(&dedup_info->lock);
+
+ /*
+ * Increase the extent ref right now, to avoid delayed ref run
+ * Or we may increase ref on non-exist extent.
+ */
+ btrfs_inc_extent_ref(trans, root, bytenr, num_bytes, 0,
+ root->root_key.objectid,
+ btrfs_ino(inode), file_pos);
+ mutex_unlock(&head->mutex);
+ btrfs_end_transaction(trans, root);
+
+ return 1;
+
+out:
+ btrfs_end_transaction(trans, root);
+ return 0;
+}
+
+int btrfs_dedup_search(struct inode *inode, u64 file_pos,
+ struct btrfs_dedup_hash *hash)
+{
+ struct btrfs_fs_info *fs_info = BTRFS_I(inode)->root->fs_info;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+ int ret = 0;
+
+ if (WARN_ON(!dedup_info || !hash))
+ return 0;
+
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
+ ret = inmem_search(inode, file_pos, hash);
+
+ /* It's possible hash->bytenr/num_bytenr already changed */
+ if (ret == 0) {
+ hash->num_bytes = 0;
+ hash->bytenr = 0;
+ }
+ return ret;
+}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 06/14] btrfs: dedup: Implement btrfs_dedup_calc_hash interface
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (4 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 05/14] btrfs: dedup: Introduce function to search for an existing hash Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 07/14] btrfs: ordered-extent: Add support for dedup Qu Wenruo
` (7 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Unlike in-memory or on-disk dedup method, only SHA256 hash method is
supported yet, so implement btrfs_dedup_calc_hash() interface using
SHA256.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 57 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index 4b8676b..f645101 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -441,3 +441,60 @@ int btrfs_dedup_search(struct inode *inode, u64 file_pos,
}
return ret;
}
+
+static int hash_data(struct btrfs_dedup_info *dedup_info, const char *data,
+ u64 length, struct btrfs_dedup_hash *hash)
+{
+ struct crypto_shash *tfm = dedup_info->dedup_driver;
+ struct {
+ struct shash_desc desc;
+ char ctx[crypto_shash_descsize(tfm)];
+ } sdesc;
+ int ret;
+
+ sdesc.desc.tfm = tfm;
+ sdesc.desc.flags = 0;
+
+ ret = crypto_shash_digest(&sdesc.desc, data, length,
+ (char *)(hash->hash));
+ return ret;
+}
+
+int btrfs_dedup_calc_hash(struct btrfs_root *root, struct inode *inode,
+ u64 start, struct btrfs_dedup_hash *hash)
+{
+ struct page *p;
+ struct btrfs_dedup_info *dedup_info = root->fs_info->dedup_info;
+ char *data;
+ int i;
+ int ret;
+ u64 dedup_bs;
+ u64 sectorsize = root->sectorsize;
+
+ if (!dedup_info || !hash)
+ return 0;
+
+ WARN_ON(!IS_ALIGNED(start, sectorsize));
+
+ dedup_bs = dedup_info->blocksize;
+ sectorsize = root->sectorsize;
+
+ data = kmalloc(dedup_bs, GFP_NOFS);
+ if (!data)
+ return -ENOMEM;
+ for (i = 0; sectorsize * i < dedup_bs; i++) {
+ char *d;
+
+ /* TODO: Add support for subpage size case */
+ p = find_get_page(inode->i_mapping,
+ (start >> PAGE_CACHE_SHIFT) + i);
+ WARN_ON(!p);
+ d = kmap_atomic(p);
+ memcpy((data + sectorsize * i), d, sectorsize);
+ kunmap_atomic(d);
+ page_cache_release(p);
+ }
+ ret = hash_data(dedup_info, data, dedup_bs, hash);
+ kfree(data);
+ return ret;
+}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 07/14] btrfs: ordered-extent: Add support for dedup
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (5 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 06/14] btrfs: dedup: Implement btrfs_dedup_calc_hash interface Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 08/14] btrfs: dedup: Inband in-memory only de-duplication implement Qu Wenruo
` (6 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Add ordered-extent support for dedup.
Note, current ordered-extent support only supports non-compressed source
extent.
Support for compressed source extent will be added later.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/ordered-data.c | 33 +++++++++++++++++++++++++++++----
fs/btrfs/ordered-data.h | 13 +++++++++++++
2 files changed, 42 insertions(+), 4 deletions(-)
diff --git a/fs/btrfs/ordered-data.c b/fs/btrfs/ordered-data.c
index 8c27292..46493f5 100644
--- a/fs/btrfs/ordered-data.c
+++ b/fs/btrfs/ordered-data.c
@@ -25,6 +25,7 @@
#include "btrfs_inode.h"
#include "extent_io.h"
#include "disk-io.h"
+#include "dedup.h"
static struct kmem_cache *btrfs_ordered_extent_cache;
@@ -183,12 +184,14 @@ static inline struct rb_node *tree_search(struct btrfs_ordered_inode_tree *tree,
*/
static int __btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
u64 start, u64 len, u64 disk_len,
- int type, int dio, int compress_type)
+ int type, int dio, int compress_type,
+ struct btrfs_dedup_hash *hash)
{
struct btrfs_root *root = BTRFS_I(inode)->root;
struct btrfs_ordered_inode_tree *tree;
struct rb_node *node;
struct btrfs_ordered_extent *entry;
+ struct btrfs_dedup_info *dedup_info = root->fs_info->dedup_info;
tree = &BTRFS_I(inode)->ordered_tree;
entry = kmem_cache_zalloc(btrfs_ordered_extent_cache, GFP_NOFS);
@@ -203,6 +206,20 @@ static int __btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
entry->inode = igrab(inode);
entry->compress_type = compress_type;
entry->truncated_len = (u64)-1;
+ entry->hash = NULL;
+ if (hash && dedup_info) {
+ entry->hash = btrfs_dedup_alloc_hash(dedup_info->hash_type);
+ if (!entry->hash) {
+ kmem_cache_free(btrfs_ordered_extent_cache, entry);
+ return -ENOMEM;
+ }
+ /* Hash contains locks, only copy what we need */
+ entry->hash->bytenr = hash->bytenr;
+ entry->hash->num_bytes = hash->num_bytes;
+ memcpy(entry->hash->hash, hash->hash,
+ btrfs_dedup_sizes[dedup_info->hash_type]);
+ }
+
if (type != BTRFS_ORDERED_IO_DONE && type != BTRFS_ORDERED_COMPLETE)
set_bit(type, &entry->flags);
@@ -249,15 +266,23 @@ int btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
{
return __btrfs_add_ordered_extent(inode, file_offset, start, len,
disk_len, type, 0,
- BTRFS_COMPRESS_NONE);
+ BTRFS_COMPRESS_NONE, NULL);
}
+int btrfs_add_ordered_extent_dedup(struct inode *inode, u64 file_offset,
+ u64 start, u64 len, u64 disk_len, int type,
+ struct btrfs_dedup_hash *hash)
+{
+ return __btrfs_add_ordered_extent(inode, file_offset, start, len,
+ disk_len, type, 0,
+ BTRFS_COMPRESS_NONE, hash);
+}
int btrfs_add_ordered_extent_dio(struct inode *inode, u64 file_offset,
u64 start, u64 len, u64 disk_len, int type)
{
return __btrfs_add_ordered_extent(inode, file_offset, start, len,
disk_len, type, 1,
- BTRFS_COMPRESS_NONE);
+ BTRFS_COMPRESS_NONE, NULL);
}
int btrfs_add_ordered_extent_compress(struct inode *inode, u64 file_offset,
@@ -266,7 +291,7 @@ int btrfs_add_ordered_extent_compress(struct inode *inode, u64 file_offset,
{
return __btrfs_add_ordered_extent(inode, file_offset, start, len,
disk_len, type, 0,
- compress_type);
+ compress_type, NULL);
}
/*
diff --git a/fs/btrfs/ordered-data.h b/fs/btrfs/ordered-data.h
index 23c9605..58519ce 100644
--- a/fs/btrfs/ordered-data.h
+++ b/fs/btrfs/ordered-data.h
@@ -139,6 +139,16 @@ struct btrfs_ordered_extent {
struct completion completion;
struct btrfs_work flush_work;
struct list_head work_list;
+
+ /*
+ * For inband deduplication
+ * If hash is NULL, no deduplication.
+ * If hash->bytenr is zero, means this is a dedup miss, hash will
+ * be added into dedup tree.
+ * If hash->bytenr is non-zero, this is a dedup hit. Extent ref is
+ * *ALREADY* increased.
+ */
+ struct btrfs_dedup_hash *hash;
};
/*
@@ -172,6 +182,9 @@ int btrfs_dec_test_first_ordered_pending(struct inode *inode,
int uptodate);
int btrfs_add_ordered_extent(struct inode *inode, u64 file_offset,
u64 start, u64 len, u64 disk_len, int type);
+int btrfs_add_ordered_extent_dedup(struct inode *inode, u64 file_offset,
+ u64 start, u64 len, u64 disk_len, int type,
+ struct btrfs_dedup_hash *hash);
int btrfs_add_ordered_extent_dio(struct inode *inode, u64 file_offset,
u64 start, u64 len, u64 disk_len, int type);
int btrfs_add_ordered_extent_compress(struct inode *inode, u64 file_offset,
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 08/14] btrfs: dedup: Inband in-memory only de-duplication implement
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (6 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 07/14] btrfs: ordered-extent: Add support for dedup Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 09/14] btrfs: dedup: Add basic tree structure for on-disk dedup method Qu Wenruo
` (5 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Core implement for inband de-duplication.
It reuse the async_cow_start() facility to do the calculate dedup hash.
And use dedup hash to do inband de-duplication at extent level.
The work flow is as below:
1) Run delalloc range for an inode
2) Calculate hash for the delalloc range at the unit of dedup_bs
3) For hash match(duplicated) case, just increase source extent ref
and insert file extent.
For hash mismatch case, go through the normal cow_file_range()
fallback, and add hash into dedup_tree.
Compress for hash miss case is not supported yet.
Current implement restore all dedup hash in memory rb-tree, with LRU
behavior to control the limit.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/extent-tree.c | 7 ++
fs/btrfs/extent_io.c | 30 ++---
fs/btrfs/extent_io.h | 15 +++
fs/btrfs/inode.c | 299 +++++++++++++++++++++++++++++++++++++++++++++++--
4 files changed, 328 insertions(+), 23 deletions(-)
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index c4661db..3f2ca718 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -36,6 +36,7 @@
#include "math.h"
#include "sysfs.h"
#include "qgroup.h"
+#include "dedup.h"
#undef SCRAMBLE_DELAYED_REFS
@@ -6654,6 +6655,12 @@ static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
btrfs_release_path(path);
if (is_data) {
+ ret = btrfs_dedup_del(trans, root, bytenr);
+ if (ret < 0) {
+ btrfs_abort_transaction(trans, extent_root,
+ ret);
+ goto out;
+ }
ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
if (ret) {
btrfs_abort_transaction(trans, extent_root, ret);
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 33a01ea..b7a6612 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -2549,7 +2549,7 @@ int end_extent_writepage(struct page *page, int err, u64 start, u64 end)
* Scheduling is not allowed, so the extent state tree is expected
* to have one and only one object corresponding to this IO.
*/
-static void end_bio_extent_writepage(struct bio *bio)
+void end_bio_extent_writepage(struct bio *bio)
{
struct bio_vec *bvec;
u64 start;
@@ -2813,8 +2813,8 @@ struct bio *btrfs_io_bio_alloc(gfp_t gfp_mask, unsigned int nr_iovecs)
}
-static int __must_check submit_one_bio(int rw, struct bio *bio,
- int mirror_num, unsigned long bio_flags)
+int __must_check submit_one_bio(int rw, struct bio *bio,
+ int mirror_num, unsigned long bio_flags)
{
int ret = 0;
struct bio_vec *bvec = bio->bi_io_vec + bio->bi_vcnt - 1;
@@ -2851,18 +2851,18 @@ static int merge_bio(int rw, struct extent_io_tree *tree, struct page *page,
}
-static int submit_extent_page(int rw, struct extent_io_tree *tree,
- struct writeback_control *wbc,
- struct page *page, sector_t sector,
- size_t size, unsigned long offset,
- struct block_device *bdev,
- struct bio **bio_ret,
- unsigned long max_pages,
- bio_end_io_t end_io_func,
- int mirror_num,
- unsigned long prev_bio_flags,
- unsigned long bio_flags,
- bool force_bio_submit)
+int submit_extent_page(int rw, struct extent_io_tree *tree,
+ struct writeback_control *wbc,
+ struct page *page, sector_t sector,
+ size_t size, unsigned long offset,
+ struct block_device *bdev,
+ struct bio **bio_ret,
+ unsigned long max_pages,
+ bio_end_io_t end_io_func,
+ int mirror_num,
+ unsigned long prev_bio_flags,
+ unsigned long bio_flags,
+ bool force_bio_submit)
{
int ret = 0;
struct bio *bio;
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index f4c1ae1..ae17832 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -360,6 +360,21 @@ int clean_io_failure(struct inode *inode, u64 start, struct page *page,
int end_extent_writepage(struct page *page, int err, u64 start, u64 end);
int repair_eb_io_failure(struct btrfs_root *root, struct extent_buffer *eb,
int mirror_num);
+int submit_extent_page(int rw, struct extent_io_tree *tree,
+ struct writeback_control *wbc,
+ struct page *page, sector_t sector,
+ size_t size, unsigned long offset,
+ struct block_device *bdev,
+ struct bio **bio_ret,
+ unsigned long max_pages,
+ bio_end_io_t end_io_func,
+ int mirror_num,
+ unsigned long prev_bio_flags,
+ unsigned long bio_flags,
+ bool force_bio_submit);
+int __must_check submit_one_bio(int rw, struct bio *bio,
+ int mirror_num, unsigned long bio_flags);
+void end_bio_extent_writepage(struct bio *bio);
/*
* When IO fails, either with EIO or csum verification fails, we
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index f82d1f4..6c4f0f9 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -60,6 +60,7 @@
#include "hash.h"
#include "props.h"
#include "qgroup.h"
+#include "dedup.h"
struct btrfs_iget_args {
struct btrfs_key *location;
@@ -666,6 +667,256 @@ static void free_async_extent_pages(struct async_extent *async_extent)
}
/*
+ * Run dedup for delalloc range
+ * Will calculate the hash for the range.
+ */
+static noinline int
+run_delalloc_dedup(struct inode *inode, struct page *locked_page, u64 start,
+ u64 end, struct async_cow *async_cow)
+{
+ struct btrfs_root *root = BTRFS_I(inode)->root;
+ struct bio *bio = NULL;
+ struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
+ struct extent_io_tree *tree = &BTRFS_I(inode)->io_tree;
+ struct extent_map *em;
+ struct page *page = NULL;
+ struct block_device *bdev;
+ struct btrfs_key ins;
+ u64 blocksize = root->sectorsize;
+ u64 num_bytes;
+ u64 cur_alloc_size;
+ u64 cur_end;
+ u64 alloc_hint = 0;
+ u64 iosize;
+ int found = 0;
+ int type = 0;
+ sector_t sector;
+ int ret = 0;
+ struct extent_state *cached_state = NULL;
+ struct btrfs_dedup_info *dedup_info = root->fs_info->dedup_info;
+ u64 dedup_bs = dedup_info->blocksize;
+ u16 hash_type = dedup_info->hash_type;
+ struct btrfs_dedup_hash *hash;
+
+ WARN_ON(btrfs_is_free_space_inode(inode));
+
+ num_bytes = ALIGN(end - start + 1, blocksize);
+ num_bytes = max(blocksize, num_bytes);
+
+ hash = btrfs_dedup_alloc_hash(hash_type);
+ if (!hash) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ btrfs_drop_extent_cache(inode, start, start + num_bytes - 1, 0);
+
+ while (num_bytes > 0) {
+ unsigned long op = 0;
+
+ /* page has been locked by caller */
+ page = find_get_page(inode->i_mapping,
+ start >> PAGE_CACHE_SHIFT);
+ WARN_ON(!page); /* page should be here */
+
+ /* already ordered? */
+ if (PagePrivate2(page))
+ goto submit;
+
+ /* too small data, go for normal path */
+ if (num_bytes < dedup_bs) {
+ int page_started = 0;
+ unsigned long nr_written = 0;
+
+ cur_end = start + num_bytes - 1;
+
+ /* Now locked_page is not dirty. */
+ if (page_offset(locked_page) >= start &&
+ page_offset(locked_page) <= cur_end) {
+ __set_page_dirty_nobuffers(locked_page);
+ }
+
+ lock_extent(tree, start, cur_end);
+
+ /* allocate blocks */
+ ret = cow_file_range(inode, locked_page, start, cur_end,
+ &page_started, &nr_written, 0);
+
+ if (!page_started && !ret)
+ extent_write_locked_range(tree, inode, start,
+ cur_end, btrfs_get_extent,
+ WB_SYNC_ALL);
+ else if (ret)
+ unlock_page(async_cow->locked_page);
+
+ if (ret)
+ SetPageError(page);
+
+ page_cache_release(page);
+ page = NULL;
+
+ num_bytes = 0;
+ start += num_bytes;
+ cond_resched();
+ continue;
+ }
+
+ cur_alloc_size = min_t(u64, num_bytes, dedup_bs);
+ WARN_ON(cur_alloc_size < dedup_bs); /* shouldn't happen */
+ cur_end = start + cur_alloc_size - 1;
+
+ /* see comments in compress_file_range */
+ extent_range_clear_dirty_for_io(inode, start, cur_end);
+
+ ret = btrfs_dedup_calc_hash(root, inode, start, hash);
+ if (ret < 0)
+ goto out_unlock;
+
+ found = btrfs_dedup_search(inode, start, hash);
+
+ if (found == 0) {
+ /* Dedup hash miss, normal routine */
+ ret = btrfs_reserve_extent(root, cur_alloc_size,
+ cur_alloc_size, 0, alloc_hint,
+ &ins, 1, 1);
+ if (ret < 0)
+ goto out_unlock;
+ } else {
+ /* Dedup hash hit, only insert file extent */
+ ins.objectid = hash->bytenr;
+ ins.offset = hash->num_bytes;
+ }
+
+ lock_extent(tree, start, cur_end);
+
+ em = alloc_extent_map();
+ if (!em) {
+ ret = -ENOMEM;
+ goto out_reserve;
+ }
+ em->start = start;
+ em->orig_start = em->start;
+ em->len = cur_alloc_size;
+ em->mod_start = em->start;
+ em->mod_len = em->len;
+
+ em->block_start = ins.objectid;
+ em->block_len = ins.offset;
+ em->orig_block_len = ins.offset;
+ em->bdev = root->fs_info->fs_devices->latest_bdev;
+ set_bit(EXTENT_FLAG_PINNED, &em->flags);
+ em->generation = -1;
+
+ while (1) {
+ write_lock(&em_tree->lock);
+ ret = add_extent_mapping(em_tree, em, 1);
+ write_unlock(&em_tree->lock);
+ if (ret != -EEXIST) {
+ free_extent_map(em);
+ break;
+ }
+ btrfs_drop_extent_cache(inode, start, cur_end, 0);
+ }
+ if (ret)
+ goto out_reserve;
+
+ ret = btrfs_add_ordered_extent_dedup(inode, start, ins.objectid,
+ cur_alloc_size, ins.offset,
+ type, hash);
+ if (ret)
+ goto out_reserve;
+
+ /*
+ * Do set the Private2 bit so we know this page was properly
+ * setup for writepage
+ */
+ op |= PAGE_SET_PRIVATE2 | PAGE_SET_WRITEBACK | PAGE_CLEAR_DIRTY;
+ extent_clear_unlock_delalloc(inode, start, cur_end,
+ NULL,
+ EXTENT_LOCKED | EXTENT_DELALLOC,
+ op);
+
+submit:
+ iosize = blocksize;
+
+ if (found == 0) {
+ em = btrfs_get_extent(inode, page, 0, start, blocksize,
+ 1);
+ if (IS_ERR(em)) {
+ /* btrfs_get_extent will not return NULL */
+ ret = PTR_ERR(em);
+ goto out_reserve;
+ }
+
+ sector = (em->block_start + start - em->start) >> 9;
+ bdev = em->bdev;
+ free_extent_map(em);
+ em = NULL;
+
+ /* TODO: rw can be WRTIE_SYNC */
+ ret = submit_extent_page(WRITE, tree, NULL, page,
+ sector, iosize, 0,
+ bdev, &bio,
+ 0, /* max_nr is no used */
+ end_bio_extent_writepage,
+ 0, 0, 0, 0);
+ if (ret)
+ break;
+ } else {
+ end_extent_writepage(page, 0, start,
+ start + iosize - 1);
+ /* we need to do this ourselves because we skip IO */
+ end_page_writeback(page);
+
+ /* Don't forget to free qgroup reserved space */
+ btrfs_qgroup_free_data(inode, start, cur_alloc_size);
+ }
+
+ unlock_page(page);
+ page_cache_release(page);
+ page = NULL;
+
+ num_bytes -= blocksize;
+ alloc_hint = ins.objectid + blocksize;
+ start += blocksize;
+ cond_resched();
+ }
+
+out_unlock:
+ if (bio) {
+ if (ret)
+ bio_put(bio);
+ else
+ ret = submit_one_bio(WRITE, bio, 0, 0);
+ bio = NULL;
+ }
+
+ if (ret && page)
+ SetPageError(page);
+ if (page) {
+ unlock_page(page);
+ page_cache_release(page);
+ }
+
+out:
+ if (ret && num_bytes > 0)
+ extent_clear_unlock_delalloc(inode,
+ start, start + num_bytes - 1, NULL,
+ EXTENT_DELALLOC | EXTENT_LOCKED | EXTENT_DEFRAG,
+ PAGE_UNLOCK | PAGE_SET_WRITEBACK |
+ PAGE_END_WRITEBACK | PAGE_CLEAR_DIRTY);
+
+ kfree(hash);
+ free_extent_state(cached_state);
+ return ret;
+
+out_reserve:
+ if (found == 0)
+ btrfs_free_reserved_extent(root, ins.objectid, ins.offset, 1);
+ goto out_unlock;
+}
+
+/*
* phase two of compressed writeback. This is the ordered portion
* of the code, which only gets called in the order the work was
* queued. We walk all the async extents created by compress_file_range
@@ -1077,11 +1328,19 @@ static noinline void async_cow_start(struct btrfs_work *work)
{
struct async_cow *async_cow;
int num_added = 0;
+ int ret = 0;
async_cow = container_of(work, struct async_cow, work);
- compress_file_range(async_cow->inode, async_cow->locked_page,
- async_cow->start, async_cow->end, async_cow,
- &num_added);
+ if (inode_need_compress(async_cow->inode))
+ compress_file_range(async_cow->inode, async_cow->locked_page,
+ async_cow->start, async_cow->end, async_cow,
+ &num_added);
+ else
+ ret = run_delalloc_dedup(async_cow->inode,
+ async_cow->locked_page, async_cow->start,
+ async_cow->end, async_cow);
+ WARN_ON(ret);
+
if (num_added == 0) {
btrfs_add_delayed_iput(async_cow->inode);
async_cow->inode = NULL;
@@ -1531,6 +1790,8 @@ static int run_delalloc_range(struct inode *inode, struct page *locked_page,
{
int ret;
int force_cow = need_force_cow(inode, start, end);
+ struct btrfs_root *root = BTRFS_I(inode)->root;
+ struct btrfs_dedup_info *dedup_info = root->fs_info->dedup_info;
if (BTRFS_I(inode)->flags & BTRFS_INODE_NODATACOW && !force_cow) {
ret = run_delalloc_nocow(inode, locked_page, start, end,
@@ -1538,7 +1799,7 @@ static int run_delalloc_range(struct inode *inode, struct page *locked_page,
} else if (BTRFS_I(inode)->flags & BTRFS_INODE_PREALLOC && !force_cow) {
ret = run_delalloc_nocow(inode, locked_page, start, end,
page_started, 0, nr_written);
- } else if (!inode_need_compress(inode)) {
+ } else if (!inode_need_compress(inode) && !dedup_info) {
ret = cow_file_range(inode, locked_page, start, end,
page_started, nr_written, 1);
} else {
@@ -2069,7 +2330,8 @@ static int insert_reserved_file_extent(struct btrfs_trans_handle *trans,
u64 disk_bytenr, u64 disk_num_bytes,
u64 num_bytes, u64 ram_bytes,
u8 compression, u8 encryption,
- u16 other_encoding, int extent_type)
+ u16 other_encoding, int extent_type,
+ struct btrfs_dedup_hash *hash)
{
struct btrfs_root *root = BTRFS_I(inode)->root;
struct btrfs_file_extent_item *fi;
@@ -2131,10 +2393,29 @@ static int insert_reserved_file_extent(struct btrfs_trans_handle *trans,
ins.objectid = disk_bytenr;
ins.offset = disk_num_bytes;
ins.type = BTRFS_EXTENT_ITEM_KEY;
- ret = btrfs_alloc_reserved_file_extent(trans, root,
+
+ /*
+ * Only for no-dedup or hash miss case, we need to increase
+ * extent reference
+ * For hash hit case, reference is already increased
+ */
+ if (!hash || hash->bytenr == 0)
+ ret = btrfs_alloc_reserved_file_extent(trans, root,
root->root_key.objectid,
btrfs_ino(inode), file_pos,
ram_bytes, &ins);
+ if (ret < 0)
+ goto out_qgroup;
+
+ /* Add missed hash into dedup tree */
+ if (hash && hash->bytenr == 0) {
+ hash->bytenr = ins.objectid;
+ hash->num_bytes = ins.offset;
+ ret = btrfs_dedup_add(trans, root, hash);
+ }
+
+out_qgroup:
+
/*
* Release the reserved range from inode dirty range map, as it is
* already moved into delayed_ref_head
@@ -2918,7 +3199,8 @@ static int btrfs_finish_ordered_io(struct btrfs_ordered_extent *ordered_extent)
ordered_extent->disk_len,
logical_len, logical_len,
compress_type, 0, 0,
- BTRFS_FILE_EXTENT_REG);
+ BTRFS_FILE_EXTENT_REG,
+ ordered_extent->hash);
if (!ret)
btrfs_release_delalloc_bytes(root,
ordered_extent->start,
@@ -9784,7 +10066,8 @@ static int __btrfs_prealloc_file_range(struct inode *inode, int mode,
cur_offset, ins.objectid,
ins.offset, ins.offset,
ins.offset, 0, 0, 0,
- BTRFS_FILE_EXTENT_PREALLOC);
+ BTRFS_FILE_EXTENT_PREALLOC,
+ NULL);
if (ret) {
btrfs_free_reserved_extent(root, ins.objectid,
ins.offset, 0);
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 09/14] btrfs: dedup: Add basic tree structure for on-disk dedup method
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (7 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 08/14] btrfs: dedup: Inband in-memory only de-duplication implement Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 10/14] btrfs: dedup: Introduce interfaces to resume and cleanup dedup info Qu Wenruo
` (4 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Liu Bo, Wang Xiaoguang
Introduce a new tree, dedup tree to record on-disk dedup hash.
As a persist hash storage instead of in-memeory only implement.
Unlike Liu Bo's implement, in this version we won't do hack for
bytenr -> hash search, but add a new type, DEDUP_BYTENR_ITEM for such
search case, just like in-memory backend.
Signed-off-by: Liu Bo <bo.li.liu@oracle.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
fs/btrfs/ctree.h | 67 +++++++++++++++++++++++++++++++++++++++++++-
fs/btrfs/dedup.h | 8 ++++++
fs/btrfs/disk-io.c | 1 +
include/trace/events/btrfs.h | 3 +-
4 files changed, 77 insertions(+), 2 deletions(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 62fed1d..60a10e4 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -96,6 +96,9 @@ struct btrfs_ordered_sum;
/* for storing items that use the BTRFS_UUID_KEY* types */
#define BTRFS_UUID_TREE_OBJECTID 9ULL
+/* on-disk dedup tree (EXPERIMENTAL) */
+#define BTRFS_DEDUP_TREE_OBJECTID 10ULL
+
/* for storing balance parameters in the root tree */
#define BTRFS_BALANCE_OBJECTID -4ULL
@@ -523,10 +526,12 @@ struct btrfs_super_block {
#define BTRFS_FEATURE_INCOMPAT_SKINNY_METADATA (1ULL << 8)
#define BTRFS_FEATURE_INCOMPAT_NO_HOLES (1ULL << 9)
+#define BTRFS_FEATURE_COMPAT_RO_DEDUP (1ULL << 0)
#define BTRFS_FEATURE_COMPAT_SUPP 0ULL
#define BTRFS_FEATURE_COMPAT_SAFE_SET 0ULL
#define BTRFS_FEATURE_COMPAT_SAFE_CLEAR 0ULL
-#define BTRFS_FEATURE_COMPAT_RO_SUPP 0ULL
+#define BTRFS_FEATURE_COMPAT_RO_SUPP \
+ (BTRFS_FEATURE_COMPAT_RO_DEDUP)
#define BTRFS_FEATURE_COMPAT_RO_SAFE_SET 0ULL
#define BTRFS_FEATURE_COMPAT_RO_SAFE_CLEAR 0ULL
@@ -954,6 +959,46 @@ struct btrfs_csum_item {
u8 csum;
} __attribute__ ((__packed__));
+/*
+ * Objectid: 0
+ * Type: BTRFS_DEDUP_STATUS_ITEM_KEY
+ * Offset: 0
+ */
+struct btrfs_dedup_status_item {
+ __le64 blocksize;
+ __le64 limit_nr;
+ __le16 hash_type;
+ __le16 backend;
+} __attribute__ ((__packed__));
+
+/*
+ * Objectid: Last 64 bit of the hash
+ * Type: BTRFS_DEDUP_HASH_ITEM_KEY
+ * Offset: Bytenr of the hash
+ *
+ * Used for hash <-> bytenr search
+ * XXX: On-disk format not stable yet, see the unsed one
+ */
+struct btrfs_dedup_hash_item {
+ /* on disk length of dedup range */
+ __le64 len;
+
+ /* Spare space */
+ u8 __unused[16];
+
+ /* Hash follows */
+} __attribute__ ((__packed__));
+
+/*
+ * Objectid: bytenr
+ * Type: BTRFS_DEDUP_BYTENR_ITEM_KEY
+ * offset: Last 64 bit of the hash
+ *
+ * Used for bytenr <-> hash search (for free_extent)
+ * all its content is hash.
+ * So no special item struct is needed.
+ */
+
struct btrfs_dev_stats_item {
/*
* grow this item struct at the end for future enhancements and keep
@@ -2100,6 +2145,13 @@ struct btrfs_ioctl_defrag_range_args {
#define BTRFS_CHUNK_ITEM_KEY 228
/*
+ * Dedup item and status
+ */
+#define BTRFS_DEDUP_STATUS_ITEM_KEY 230
+#define BTRFS_DEDUP_HASH_ITEM_KEY 231
+#define BTRFS_DEDUP_BYTENR_ITEM_KEY 232
+
+/*
* Records the overall state of the qgroups.
* There's only one instance of this key present,
* (0, BTRFS_QGROUP_STATUS_KEY, 0)
@@ -3157,6 +3209,19 @@ static inline unsigned long btrfs_leaf_data(struct extent_buffer *l)
return offsetof(struct btrfs_leaf, items);
}
+/* btrfs_dedup_status */
+BTRFS_SETGET_FUNCS(dedup_status_blocksize, struct btrfs_dedup_status_item,
+ blocksize, 64);
+BTRFS_SETGET_FUNCS(dedup_status_limit, struct btrfs_dedup_status_item,
+ limit_nr, 64);
+BTRFS_SETGET_FUNCS(dedup_status_hash_type, struct btrfs_dedup_status_item,
+ hash_type, 16);
+BTRFS_SETGET_FUNCS(dedup_status_backend, struct btrfs_dedup_status_item,
+ backend, 16);
+
+/* btrfs_dedup_hash_item */
+BTRFS_SETGET_FUNCS(dedup_hash_len, struct btrfs_dedup_hash_item, len, 64);
+
/* struct btrfs_file_extent_item */
BTRFS_SETGET_FUNCS(file_extent_type, struct btrfs_file_extent_item, type, 8);
BTRFS_SETGET_STACK_FUNCS(stack_file_extent_disk_bytenr,
diff --git a/fs/btrfs/dedup.h b/fs/btrfs/dedup.h
index 3cd6d14..bc37a8d 100644
--- a/fs/btrfs/dedup.h
+++ b/fs/btrfs/dedup.h
@@ -59,6 +59,8 @@ struct btrfs_dedup_hash {
u8 hash[];
};
+struct btrfs_root;
+
struct btrfs_dedup_info {
/* dedup blocksize */
u64 blocksize;
@@ -75,6 +77,12 @@ struct btrfs_dedup_info {
spinlock_t lock;
u64 limit_nr;
u64 current_nr;
+
+ /* for persist data like dedup-hash and dedup status */
+ struct btrfs_root *dedup_root;
+
+ /* on-disk mode only mutex */
+ struct mutex ondisk_lock;
};
struct btrfs_trans_handle;
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index b213439..cf9dbff 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -175,6 +175,7 @@ static struct btrfs_lockdep_keyset {
{ .id = BTRFS_TREE_RELOC_OBJECTID, .name_stem = "treloc" },
{ .id = BTRFS_DATA_RELOC_TREE_OBJECTID, .name_stem = "dreloc" },
{ .id = BTRFS_UUID_TREE_OBJECTID, .name_stem = "uuid" },
+ { .id = BTRFS_DEDUP_TREE_OBJECTID, .name_stem = "dedup" },
{ .id = 0, .name_stem = "tree" },
};
diff --git a/include/trace/events/btrfs.h b/include/trace/events/btrfs.h
index b4473da..655b630 100644
--- a/include/trace/events/btrfs.h
+++ b/include/trace/events/btrfs.h
@@ -46,12 +46,13 @@ struct btrfs_qgroup_operation;
{ BTRFS_QUOTA_TREE_OBJECTID, "QUOTA_TREE" }, \
{ BTRFS_TREE_RELOC_OBJECTID, "TREE_RELOC" }, \
{ BTRFS_UUID_TREE_OBJECTID, "UUID_RELOC" }, \
+ { BTRFS_DEDUP_TREE_OBJECTID, "DEDUP_TREE" }, \
{ BTRFS_DATA_RELOC_TREE_OBJECTID, "DATA_RELOC_TREE" })
#define show_root_type(obj) \
obj, ((obj >= BTRFS_DATA_RELOC_TREE_OBJECTID) || \
(obj >= BTRFS_ROOT_TREE_OBJECTID && \
- obj <= BTRFS_QUOTA_TREE_OBJECTID)) ? __show_root_type(obj) : "-"
+ obj <= BTRFS_DEDUP_TREE_OBJECTID)) ? __show_root_type(obj) : "-"
#define BTRFS_GROUP_FLAGS \
{ BTRFS_BLOCK_GROUP_DATA, "DATA"}, \
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 10/14] btrfs: dedup: Introduce interfaces to resume and cleanup dedup info
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (8 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 09/14] btrfs: dedup: Add basic tree structure for on-disk dedup method Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 11/14] btrfs: dedup: Add support for on-disk hash search Qu Wenruo
` (3 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
Since we will introduce a new on-disk based dedup method, introduce new
interfaces to resume previous dedup setup.
And since we introduce a new tree for status, also add disable handler
for it.
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 193 +++++++++++++++++++++++++++++++++++++++++++++++------
fs/btrfs/dedup.h | 11 +++
fs/btrfs/disk-io.c | 26 +++++++-
fs/btrfs/disk-io.h | 1 +
4 files changed, 210 insertions(+), 21 deletions(-)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index f645101..c05cf1f 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -20,11 +20,55 @@
#include "btrfs_inode.h"
#include "transaction.h"
#include "delayed-ref.h"
+#include "disk-io.h"
+
+static int init_dedup_info(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
+ u64 blocksize, u64 limit)
+{
+ struct btrfs_dedup_info *dedup_info;
+ int ret;
+
+ fs_info->dedup_info = kzalloc(sizeof(*dedup_info), GFP_NOFS);
+ if (!fs_info->dedup_info)
+ return -ENOMEM;
+
+ dedup_info = fs_info->dedup_info;
+
+ dedup_info->hash_type = type;
+ dedup_info->backend = backend;
+ dedup_info->blocksize = blocksize;
+ dedup_info->limit_nr = limit;
+
+ /* Only support SHA256 yet */
+ dedup_info->dedup_driver = crypto_alloc_shash("sha256", 0, 0);
+ if (IS_ERR(dedup_info->dedup_driver)) {
+ btrfs_err(fs_info, "failed to init sha256 driver");
+ ret = PTR_ERR(dedup_info->dedup_driver);
+ kfree(fs_info->dedup_info);
+ fs_info->dedup_info = NULL;
+ return ret;
+ }
+
+ dedup_info->hash_root = RB_ROOT;
+ dedup_info->bytenr_root = RB_ROOT;
+ dedup_info->current_nr = 0;
+ INIT_LIST_HEAD(&dedup_info->lru_list);
+ spin_lock_init(&dedup_info->lock);
+ mutex_init(&dedup_info->ondisk_lock);
+ return 0;
+}
int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
u64 blocksize, u64 limit)
{
struct btrfs_dedup_info *dedup_info;
+ struct btrfs_root *dedup_root;
+ struct btrfs_key key;
+ struct btrfs_trans_handle *trans;
+ struct btrfs_path *path;
+ struct btrfs_dedup_status_item *status;
+ int create_tree;
+ u64 compat_ro_flag = btrfs_super_compat_ro_flags(fs_info->super_copy);
int ret = 0;
/* Sanity check */
@@ -42,6 +86,18 @@ int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
if (backend == BTRFS_DEDUP_BACKEND_ONDISK && limit != 0)
limit = 0;
+ /*
+ * If current fs doesn't support DEDUP feature, don't enable
+ * on-disk dedup.
+ */
+ if (!(compat_ro_flag & BTRFS_FEATURE_COMPAT_RO_DEDUP) &&
+ backend == BTRFS_DEDUP_BACKEND_ONDISK)
+ return -EINVAL;
+
+ /* Meaningless and unable to enable dedup for RO fs */
+ if (fs_info->sb->s_flags & MS_RDONLY)
+ return -EINVAL;
+
if (fs_info->dedup_info) {
dedup_info = fs_info->dedup_info;
@@ -61,32 +117,63 @@ int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
}
enable:
- fs_info->dedup_info = kzalloc(sizeof(*dedup_info), GFP_NOFS);
- if (!fs_info->dedup_info)
- return -ENOMEM;
+ create_tree = compat_ro_flag & BTRFS_FEATURE_COMPAT_RO_DEDUP;
+ ret = init_dedup_info(fs_info, type, backend, blocksize, limit);
dedup_info = fs_info->dedup_info;
+ if (ret < 0)
+ goto out;
- dedup_info->hash_type = type;
- dedup_info->backend = backend;
- dedup_info->blocksize = blocksize;
- dedup_info->limit_nr = limit;
+ if (!create_tree)
+ goto out;
- /* Only support SHA256 yet */
- dedup_info->dedup_driver = crypto_alloc_shash("sha256", 0, 0);
- if (IS_ERR(dedup_info->dedup_driver)) {
- btrfs_err(fs_info, "failed to init sha256 driver");
- ret = PTR_ERR(dedup_info->dedup_driver);
+ /* Create dedup tree for status at least */
+ path = btrfs_alloc_path();
+ if (!path) {
+ ret = -ENOMEM;
goto out;
}
- dedup_info->hash_root = RB_ROOT;
- dedup_info->bytenr_root = RB_ROOT;
- dedup_info->current_nr = 0;
- INIT_LIST_HEAD(&dedup_info->lru_list);
- spin_lock_init(&dedup_info->lock);
+ trans = btrfs_start_transaction(fs_info->tree_root, 2);
+ if (IS_ERR(trans)) {
+ ret = PTR_ERR(trans);
+ btrfs_free_path(path);
+ goto out;
+ }
+
+ dedup_root = btrfs_create_tree(trans, fs_info,
+ BTRFS_DEDUP_TREE_OBJECTID);
+ if (IS_ERR(dedup_root)) {
+ ret = PTR_ERR(dedup_root);
+ btrfs_abort_transaction(trans, fs_info->tree_root, ret);
+ btrfs_free_path(path);
+ goto out;
+ }
+
+ dedup_info->dedup_root = dedup_root;
+
+ key.objectid = 0;
+ key.type = BTRFS_DEDUP_STATUS_ITEM_KEY;
+ key.offset = 0;
+
+ ret = btrfs_insert_empty_item(trans, dedup_root, path, &key,
+ sizeof(*status));
+ if (ret < 0) {
+ btrfs_abort_transaction(trans, fs_info->tree_root, ret);
+ btrfs_free_path(path);
+ goto out;
+ }
+ status = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_dedup_status_item);
+ btrfs_set_dedup_status_blocksize(path->nodes[0], status, blocksize);
+ btrfs_set_dedup_status_limit(path->nodes[0], status, limit);
+ btrfs_set_dedup_status_hash_type(path->nodes[0], status, type);
+ btrfs_set_dedup_status_backend(path->nodes[0], status, backend);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+
+ btrfs_free_path(path);
+ ret = btrfs_commit_transaction(trans, fs_info->tree_root);
- fs_info->dedup_info = dedup_info;
out:
if (ret < 0) {
kfree(dedup_info);
@@ -95,6 +182,68 @@ out:
return ret;
}
+int btrfs_dedup_resume(struct btrfs_fs_info *fs_info,
+ struct btrfs_root *dedup_root)
+{
+ struct btrfs_dedup_status_item *status;
+ struct btrfs_key key;
+ struct btrfs_path *path;
+ u64 blocksize;
+ u64 limit;
+ u16 type;
+ u16 backend;
+ int ret = 0;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ key.objectid = 0;
+ key.type = BTRFS_DEDUP_STATUS_ITEM_KEY;
+ key.offset = 0;
+
+ ret = btrfs_search_slot(NULL, dedup_root, &key, path, 0, 0);
+ if (ret > 0) {
+ ret = -ENOENT;
+ goto out;
+ } else if (ret < 0) {
+ goto out;
+ }
+
+ status = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_dedup_status_item);
+ blocksize = btrfs_dedup_status_blocksize(path->nodes[0], status);
+ limit = btrfs_dedup_status_limit(path->nodes[0], status);
+ type = btrfs_dedup_status_hash_type(path->nodes[0], status);
+ backend = btrfs_dedup_status_backend(path->nodes[0], status);
+
+ ret = init_dedup_info(fs_info, type, backend, blocksize, limit);
+ if (ret < 0)
+ goto out;
+ fs_info->dedup_info->dedup_root = dedup_root;
+
+out:
+ btrfs_free_path(path);
+ return ret;
+}
+
+static void inmem_destroy(struct btrfs_fs_info *fs_info);
+int btrfs_dedup_cleanup(struct btrfs_fs_info *fs_info)
+{
+ if (!fs_info->dedup_info)
+ return 0;
+ if (fs_info->dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
+ inmem_destroy(fs_info);
+ if (fs_info->dedup_info->dedup_root) {
+ free_root_extent_buffers(fs_info->dedup_info->dedup_root);
+ kfree(fs_info->dedup_info->dedup_root);
+ }
+ crypto_free_shash(fs_info->dedup_info->dedup_driver);
+ kfree(fs_info->dedup_info);
+ fs_info->dedup_info = NULL;
+ return 0;
+}
+
static int inmem_insert_hash(struct rb_root *root,
struct btrfs_dedup_hash *hash, int hash_len)
{
@@ -279,13 +428,19 @@ static void inmem_destroy(struct btrfs_fs_info *fs_info)
int btrfs_dedup_disable(struct btrfs_fs_info *fs_info)
{
struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+ int ret = 0;
if (!dedup_info)
return 0;
if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
inmem_destroy(fs_info);
- return 0;
+ if (dedup_info->dedup_root)
+ ret = btrfs_drop_snapshot(dedup_info->dedup_root, NULL, 1, 0);
+ crypto_free_shash(fs_info->dedup_info->dedup_driver);
+ kfree(fs_info->dedup_info);
+ fs_info->dedup_info = NULL;
+ return ret;
}
/*
diff --git a/fs/btrfs/dedup.h b/fs/btrfs/dedup.h
index bc37a8d..53f2a9c 100644
--- a/fs/btrfs/dedup.h
+++ b/fs/btrfs/dedup.h
@@ -114,6 +114,17 @@ int btrfs_dedup_enable(struct btrfs_fs_info *fs_info, u16 type, u16 backend,
int btrfs_dedup_disable(struct btrfs_fs_info *fs_info);
/*
+ * Restore previous dedup setup from disk
+ */
+int btrfs_dedup_resume(struct btrfs_fs_info *fs_info,
+ struct btrfs_root *dedup_root);
+
+/*
+ * Free current btrfs_dedup_info
+ */
+int btrfs_dedup_cleanup(struct btrfs_fs_info *fs_info);
+
+/*
* Calculate hash for dedup.
* Caller must ensure [start, start + dedup_bs) has valid data.
*/
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index cf9dbff..0d84e17 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -49,6 +49,7 @@
#include "raid56.h"
#include "sysfs.h"
#include "qgroup.h"
+#include "dedup.h"
#ifdef CONFIG_X86
#include <asm/cpufeature.h>
@@ -2127,7 +2128,7 @@ static void btrfs_stop_all_workers(struct btrfs_fs_info *fs_info)
btrfs_destroy_workqueue(fs_info->extent_workers);
}
-static void free_root_extent_buffers(struct btrfs_root *root)
+void free_root_extent_buffers(struct btrfs_root *root)
{
if (root) {
free_extent_buffer(root->node);
@@ -2449,7 +2450,25 @@ static int btrfs_read_roots(struct btrfs_fs_info *fs_info,
fs_info->uuid_root = root;
}
- return 0;
+ location.objectid = BTRFS_DEDUP_TREE_OBJECTID;
+ root = btrfs_read_tree_root(tree_root, &location);
+ if (IS_ERR(root)) {
+ ret = PTR_ERR(root);
+ if (ret != -ENOENT)
+ return ret;
+ /* Just OK if there is no dedup root */
+ return 0;
+ }
+
+ set_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state);
+ /* Found dedup root, resume previous dedup setup */
+ ret = btrfs_dedup_resume(fs_info, root);
+
+ if (ret < 0) {
+ free_root_extent_buffers(root);
+ kfree(root);
+ }
+ return ret;
}
int open_ctree(struct super_block *sb,
@@ -3836,6 +3855,9 @@ void close_ctree(struct btrfs_root *root)
btrfs_free_qgroup_config(fs_info);
+ /* Cleanup dedup info */
+ btrfs_dedup_cleanup(fs_info);
+
if (percpu_counter_sum(&fs_info->delalloc_bytes)) {
btrfs_info(fs_info, "at unmount delalloc count %lld",
percpu_counter_sum(&fs_info->delalloc_bytes));
diff --git a/fs/btrfs/disk-io.h b/fs/btrfs/disk-io.h
index adeb318..4cbdce1 100644
--- a/fs/btrfs/disk-io.h
+++ b/fs/btrfs/disk-io.h
@@ -70,6 +70,7 @@ struct btrfs_root *btrfs_read_fs_root(struct btrfs_root *tree_root,
int btrfs_init_fs_root(struct btrfs_root *root);
int btrfs_insert_fs_root(struct btrfs_fs_info *fs_info,
struct btrfs_root *root);
+void free_root_extent_buffers(struct btrfs_root *root);
void btrfs_free_fs_roots(struct btrfs_fs_info *fs_info);
struct btrfs_root *btrfs_get_fs_root(struct btrfs_fs_info *fs_info,
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 11/14] btrfs: dedup: Add support for on-disk hash search
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (9 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 10/14] btrfs: dedup: Introduce interfaces to resume and cleanup dedup info Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 12/14] btrfs: dedup: Add support for adding hash for on-disk backend Qu Wenruo
` (2 subsequent siblings)
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
Now on-disk backend should be able to search hash now.
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 169 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
fs/btrfs/dedup.h | 3 +
2 files changed, 171 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index c05cf1f..bebf180 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -444,6 +444,172 @@ int btrfs_dedup_disable(struct btrfs_fs_info *fs_info)
}
/*
+ * Return 0 for not found
+ * Return >0 for found and set bytenr_ret
+ * Return <0 for error
+ */
+static int ondisk_search_hash(struct btrfs_dedup_info *dedup_info, u8 *hash,
+ u64 *bytenr_ret, u64 *num_bytes_ret)
+{
+ struct btrfs_path *path;
+ struct btrfs_key key;
+ struct btrfs_root *dedup_root = dedup_info->dedup_root;
+ u8 *buf = NULL;
+ int hash_len = btrfs_dedup_sizes[dedup_info->hash_type];
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ buf = kmalloc(hash_len, GFP_NOFS);
+ if (!buf) {
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ memcpy(&key.objectid, hash + hash_len - 8, 8);
+ key.type = BTRFS_DEDUP_HASH_ITEM_KEY;
+ key.offset = 0;
+
+ ret = btrfs_search_slot(NULL, dedup_root, &key, path, 0, 0);
+ if (ret < 0)
+ goto out;
+ WARN_ON(ret == 0);
+ ret = 0;
+ while (1) {
+ struct extent_buffer *node = path->nodes[0];
+ struct btrfs_dedup_hash_item *hash_item;
+ int slot = path->slots[0];
+
+ if (slot >= btrfs_header_nritems(node))
+ goto next;
+
+ btrfs_item_key_to_cpu(node, &key, slot);
+
+ if (key.type != BTRFS_DEDUP_HASH_ITEM_KEY ||
+ memcmp(&key.objectid, hash + hash_len - 8, 8))
+ break;
+ hash_item = btrfs_item_ptr(node, slot,
+ struct btrfs_dedup_hash_item);
+ read_extent_buffer(node, buf, (unsigned long)(hash_item + 1),
+ hash_len);
+ if (!memcmp(buf, hash, hash_len)) {
+ ret = 1;
+ *bytenr_ret = key.offset;
+ *num_bytes_ret = btrfs_dedup_hash_len(node, hash_item);
+ break;
+ }
+
+next:
+ ret = btrfs_next_item(dedup_root, path);
+ if (ret < 0)
+ break;
+ if (ret > 0) {
+ ret = 0;
+ break;
+ }
+ }
+out:
+ kfree(buf);
+ btrfs_free_path(path);
+ return ret;
+}
+
+static int ondisk_search(struct inode *inode, u64 file_pos,
+ struct btrfs_dedup_hash *hash)
+{
+ int ret;
+ struct btrfs_root *root = BTRFS_I(inode)->root;
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_trans_handle *trans = NULL;
+ struct btrfs_delayed_ref_root *delayed_refs;
+ struct btrfs_delayed_ref_head *head;
+ struct btrfs_dedup_info *dedup_info = fs_info->dedup_info;
+ u64 old_bytenr;
+ u64 bytenr;
+ u64 num_bytes;
+
+ /*
+ * TODO: Opitmized the superhot mutex.
+ */
+ mutex_lock(&dedup_info->ondisk_lock);
+ ret = ondisk_search_hash(dedup_info, hash->hash, &bytenr, &num_bytes);
+ mutex_unlock(&dedup_info->ondisk_lock);
+ if (ret <= 0)
+ goto out;
+
+ trans = btrfs_join_transaction(root);
+ if (IS_ERR(trans))
+ return PTR_ERR(trans);
+
+again:
+ delayed_refs = &trans->transaction->delayed_refs;
+
+ spin_lock(&delayed_refs->lock);
+ head = btrfs_find_delayed_ref_head(trans, bytenr);
+ if (!head || head->processing == 1) {
+ /*
+ * Somebody else may be trying to run the refs, the found
+ * duplicated extent may be freed, so here we just
+ * choose to abort this dedup handle.
+ * XXX: we need to find a better method to improve it.
+ */
+ spin_unlock(&delayed_refs->lock);
+ ret = 0;
+ goto out;
+ }
+
+ ret = btrfs_delayed_ref_lock(trans, head);
+ spin_unlock(&delayed_refs->lock);
+ if (ret == -EAGAIN) {
+ mutex_lock(&dedup_info->ondisk_lock);
+ ret = ondisk_search_hash(dedup_info, hash->hash, &bytenr,
+ &num_bytes);
+ mutex_unlock(&dedup_info->ondisk_lock);
+ if (ret <= 0)
+ goto out;
+ goto again;
+ }
+ /*
+ * Still need to search the hash again to ensure the hash is not
+ * deleted in run_delayed_refs
+ */
+ old_bytenr = bytenr;
+ mutex_lock(&dedup_info->ondisk_lock);
+ ret = ondisk_search_hash(dedup_info, hash->hash, &bytenr, &num_bytes);
+ if (ret <= 0) {
+ mutex_unlock(&dedup_info->ondisk_lock);
+ mutex_unlock(&head->mutex);
+ goto out;
+ }
+
+ /* bytenr changed, we need to relock the delayed_ref head */
+ if (old_bytenr != bytenr) {
+ mutex_unlock(&dedup_info->ondisk_lock);
+ mutex_unlock(&head->mutex);
+ goto again;
+ }
+
+ /*
+ * finally, we found the matching hash, increase extent ref right now
+ * to avoid delayed ref run it
+ */
+ btrfs_inc_extent_ref(trans, root, bytenr, num_bytes, 0,
+ root->root_key.objectid,
+ btrfs_ino(inode), file_pos);
+ hash->bytenr = bytenr;
+ hash->num_bytes = num_bytes;
+ mutex_unlock(&dedup_info->ondisk_lock);
+ mutex_unlock(&head->mutex);
+ ret = 1;
+out:
+ if (trans)
+ btrfs_end_transaction(trans, root);
+ return ret;
+}
+
+/*
* Caller must ensure the corresponding ref head is not being run.
*/
static struct btrfs_dedup_hash *
@@ -588,7 +754,8 @@ int btrfs_dedup_search(struct inode *inode, u64 file_pos,
if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
ret = inmem_search(inode, file_pos, hash);
-
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_ONDISK)
+ ret = ondisk_search(inode, file_pos, hash);
/* It's possible hash->bytenr/num_bytenr already changed */
if (ret == 0) {
hash->num_bytes = 0;
diff --git a/fs/btrfs/dedup.h b/fs/btrfs/dedup.h
index 53f2a9c..df123e3 100644
--- a/fs/btrfs/dedup.h
+++ b/fs/btrfs/dedup.h
@@ -143,6 +143,9 @@ int btrfs_dedup_calc_hash(struct btrfs_root *root, struct inode *inode,
* Return > 0 for a hash match, and the extent ref will be
* INCREASED.
* Return 0 for a hash miss. Nothing is done
+ * Return <0 for error.
+ *
+ * Only on-disk backedn may return error though.
*/
int btrfs_dedup_search(struct inode *inode, u64 file_pos,
struct btrfs_dedup_hash *hash);
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 12/14] btrfs: dedup: Add support for adding hash for on-disk backend
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (10 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 11/14] btrfs: dedup: Add support for on-disk hash search Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 13/14] btrfs: dedup: Add support to delete " Qu Wenruo
2015-12-29 8:01 ` [PATCH 14/14] btrfs: dedup: Add ioctl for inband deduplication Qu Wenruo
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
Now on-disk backend can add hash now.
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 69 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index bebf180..82e21a6 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -227,6 +227,8 @@ out:
return ret;
}
+static int ondisk_search_hash(struct btrfs_dedup_info *dedup_info, u8 *hash,
+ u64 *bytenr_ret, u64 *num_bytes_ret);
static void inmem_destroy(struct btrfs_fs_info *fs_info);
int btrfs_dedup_cleanup(struct btrfs_fs_info *fs_info)
{
@@ -343,6 +345,71 @@ out:
return 0;
}
+static int ondisk_add(struct btrfs_trans_handle *trans,
+ struct btrfs_dedup_info *dedup_info,
+ struct btrfs_dedup_hash *hash)
+{
+ struct btrfs_path *path;
+ struct btrfs_root *dedup_root = dedup_info->dedup_root;
+ struct btrfs_key key;
+ struct btrfs_dedup_hash_item *hash_item;
+ u64 bytenr;
+ u64 num_bytes;
+ int hash_len = btrfs_dedup_sizes[dedup_info->hash_type];
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ mutex_lock(&dedup_info->ondisk_lock);
+ ret = ondisk_search_hash(dedup_info, hash->hash, &bytenr, &num_bytes);
+ if (ret < 0)
+ goto out;
+ /* Same hash found, don't re-add to save dedup tree space */
+ if (ret > 0) {
+ ret = 0;
+ goto out;
+ }
+
+ /* Insert hash->bytenr item */
+ memcpy(&key.objectid, hash->hash + hash_len - 8, 8);
+ key.type = BTRFS_DEDUP_HASH_ITEM_KEY;
+ key.offset = hash->bytenr;
+
+ ret = btrfs_insert_empty_item(trans, dedup_root, path, &key,
+ sizeof(*hash_item) + hash_len);
+ WARN_ON(ret == -EEXIST);
+ if (ret < 0)
+ goto out;
+ hash_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
+ struct btrfs_dedup_hash_item);
+ btrfs_set_dedup_hash_len(path->nodes[0], hash_item, hash->num_bytes);
+ write_extent_buffer(path->nodes[0], hash->hash,
+ (unsigned long)(hash_item + 1), hash_len);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+ btrfs_release_path(path);
+
+ /* Then bytenr->hash item */
+ key.objectid = hash->bytenr;
+ key.type = BTRFS_DEDUP_BYTENR_ITEM_KEY;
+ memcpy(&key.offset, hash->hash + hash_len - 8, 8);
+
+ ret = btrfs_insert_empty_item(trans, dedup_root, path, &key, hash_len);
+ WARN_ON(ret == -EEXIST);
+ if (ret < 0)
+ goto out;
+ write_extent_buffer(path->nodes[0], hash->hash,
+ btrfs_item_offset_nr(path->nodes[0], path->slots[0]),
+ hash_len);
+ btrfs_mark_buffer_dirty(path->nodes[0]);
+
+out:
+ mutex_unlock(&dedup_info->ondisk_lock);
+ btrfs_free_path(path);
+ return ret;
+}
+
int btrfs_dedup_add(struct btrfs_trans_handle *trans, struct btrfs_root *root,
struct btrfs_dedup_hash *hash)
{
@@ -357,6 +424,8 @@ int btrfs_dedup_add(struct btrfs_trans_handle *trans, struct btrfs_root *root,
if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
return inmem_add(dedup_info, hash);
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_ONDISK)
+ return ondisk_add(trans, dedup_info, hash);
return -EINVAL;
}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 13/14] btrfs: dedup: Add support to delete hash for on-disk backend
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (11 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 12/14] btrfs: dedup: Add support for adding hash for on-disk backend Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
2015-12-29 8:01 ` [PATCH 14/14] btrfs: dedup: Add ioctl for inband deduplication Qu Wenruo
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
Now on-disk backend can delete hash now.
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
fs/btrfs/dedup.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 54 insertions(+)
diff --git a/fs/btrfs/dedup.c b/fs/btrfs/dedup.c
index 82e21a6..704c3c7 100644
--- a/fs/btrfs/dedup.c
+++ b/fs/btrfs/dedup.c
@@ -468,6 +468,58 @@ static int inmem_del(struct btrfs_dedup_info *dedup_info, u64 bytenr)
return 0;
}
+static int ondisk_del(struct btrfs_trans_handle *trans,
+ struct btrfs_dedup_info *dedup_info, u64 bytenr)
+{
+ struct btrfs_root *dedup_root = dedup_info->dedup_root;
+ struct btrfs_path *path;
+ struct btrfs_key key;
+ int ret;
+
+ path = btrfs_alloc_path();
+ if (!path)
+ return -ENOMEM;
+
+ key.objectid = bytenr;
+ key.type = BTRFS_DEDUP_BYTENR_ITEM_KEY;
+ key.offset = 0;
+
+ mutex_lock(&dedup_info->ondisk_lock);
+
+ ret = btrfs_search_slot(trans, dedup_root, &key, path, -1, 1);
+ if (ret < 0)
+ goto out;
+
+ /* There should be at most one item with same objectid and type */
+ btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
+ if (key.objectid != bytenr || key.type != BTRFS_DEDUP_BYTENR_ITEM_KEY) {
+ ret = 0;
+ goto out;
+ }
+
+ btrfs_del_item(trans, dedup_root, path);
+ btrfs_release_path(path);
+
+ /* Search for hash item and delete it */
+ key.objectid = key.offset;
+ key.type = BTRFS_DEDUP_HASH_ITEM_KEY;
+ key.offset = bytenr;
+
+ ret = btrfs_search_slot(trans, dedup_root, &key, path, -1, 1);
+ if (WARN_ON(ret > 0)) {
+ ret = -ENOENT;
+ goto out;
+ }
+ if (ret < 0)
+ goto out;
+ btrfs_del_item(trans, dedup_root, path);
+
+out:
+ btrfs_free_path(path);
+ mutex_unlock(&dedup_info->ondisk_lock);
+ return ret;
+}
+
/* Remove a dedup hash from dedup tree */
int btrfs_dedup_del(struct btrfs_trans_handle *trans, struct btrfs_root *root,
u64 bytenr)
@@ -480,6 +532,8 @@ int btrfs_dedup_del(struct btrfs_trans_handle *trans, struct btrfs_root *root,
if (dedup_info->backend == BTRFS_DEDUP_BACKEND_INMEMORY)
return inmem_del(dedup_info, bytenr);
+ if (dedup_info->backend == BTRFS_DEDUP_BACKEND_ONDISK)
+ return ondisk_del(trans, dedup_info, bytenr);
return -EINVAL;
}
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread* [PATCH 14/14] btrfs: dedup: Add ioctl for inband deduplication
2015-12-29 8:01 [PATCH v2 00/14][For 4.6] Btrfs: Add inband (write time) de-duplication framework Qu Wenruo
` (12 preceding siblings ...)
2015-12-29 8:01 ` [PATCH 13/14] btrfs: dedup: Add support to delete " Qu Wenruo
@ 2015-12-29 8:01 ` Qu Wenruo
13 siblings, 0 replies; 15+ messages in thread
From: Qu Wenruo @ 2015-12-29 8:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: Wang Xiaoguang
From: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
Add ioctl interface for inband deduplication, which includes:
1) enable
2) disable
3) status
We will later add ioctl to disable inband dedup for given file/dir.
Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
---
fs/btrfs/ctree.h | 1 +
fs/btrfs/disk-io.c | 1 +
fs/btrfs/ioctl.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++
include/uapi/linux/btrfs.h | 23 +++++++++++++++++
4 files changed, 88 insertions(+)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 60a10e4..9b9fbb6 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1864,6 +1864,7 @@ struct btrfs_fs_info {
/* reference to inband de-duplication info */
struct btrfs_dedup_info *dedup_info;
+ struct mutex dedup_ioctl_mutex;
};
struct btrfs_subvolume_writers {
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 0d84e17..341f4f0 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -2562,6 +2562,7 @@ int open_ctree(struct super_block *sb,
mutex_init(&fs_info->delete_unused_bgs_mutex);
mutex_init(&fs_info->reloc_mutex);
mutex_init(&fs_info->delalloc_root_mutex);
+ mutex_init(&fs_info->dedup_ioctl_mutex);
seqlock_init(&fs_info->profiles_lock);
init_rwsem(&fs_info->delayed_iput_sem);
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 7375cf2..6749c84 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -59,6 +59,7 @@
#include "props.h"
#include "sysfs.h"
#include "qgroup.h"
+#include "dedup.h"
#ifdef CONFIG_64BIT
/* If we have a 32-bit userspace and 64-bit kernel, then the UAPI
@@ -3206,6 +3207,66 @@ out:
return ret;
}
+static long btrfs_ioctl_dedup_ctl(struct btrfs_root *root, void __user *args)
+{
+ struct btrfs_ioctl_dedup_args *dargs;
+ struct btrfs_fs_info *fs_info = root->fs_info;
+ struct btrfs_dedup_info *dedup_info;
+ int ret;
+
+ if (!capable(CAP_SYS_ADMIN))
+ return -EPERM;
+
+ dargs = memdup_user(args, sizeof(*dargs));
+ if (IS_ERR(dargs)) {
+ ret = PTR_ERR(dargs);
+ return ret;
+ }
+
+ if (dargs->cmd >= BTRFS_DEDUP_CTL_LAST) {
+ ret = -EINVAL;
+ goto out;
+ }
+ switch (dargs->cmd) {
+ case BTRFS_DEDUP_CTL_ENABLE:
+ ret = btrfs_dedup_enable(fs_info, dargs->hash_type,
+ dargs->backend, dargs->blocksize,
+ dargs->limit_nr);
+ break;
+ case BTRFS_DEDUP_CTL_DISABLE:
+ ret = btrfs_dedup_disable(fs_info);
+ break;
+ case BTRFS_DEDUP_CTL_STATUS:
+ dedup_info = fs_info->dedup_info;
+ if (dedup_info) {
+ dargs->status = 1;
+ dargs->blocksize = dedup_info->blocksize;
+ dargs->backend = dedup_info->backend;
+ dargs->hash_type = dedup_info->hash_type;
+ dargs->limit_nr = dedup_info->limit_nr;
+ dargs->current_nr = dedup_info->current_nr;
+ } else {
+ dargs->status = 0;
+ dargs->blocksize = 0;
+ dargs->backend = 0;
+ dargs->hash_type = 0;
+ dargs->limit_nr = 0;
+ dargs->current_nr = 0;
+ }
+ if (copy_to_user(args, dargs, sizeof(*dargs)))
+ ret = -EFAULT;
+ else
+ ret = 0;
+ break;
+ default:
+ ret = -EINVAL;
+ break;
+ }
+out:
+ kfree(dargs);
+ return ret;
+}
+
static int clone_finish_inode_update(struct btrfs_trans_handle *trans,
struct inode *inode,
u64 endoff,
@@ -5565,6 +5626,8 @@ long btrfs_ioctl(struct file *file, unsigned int
return btrfs_ioctl_set_fslabel(file, argp);
case BTRFS_IOC_FILE_EXTENT_SAME:
return btrfs_ioctl_file_extent_same(file, argp);
+ case BTRFS_IOC_DEDUP_CTL:
+ return btrfs_ioctl_dedup_ctl(root, argp);
case BTRFS_IOC_GET_SUPPORTED_FEATURES:
return btrfs_ioctl_get_supported_features(file, argp);
case BTRFS_IOC_GET_FEATURES:
diff --git a/include/uapi/linux/btrfs.h b/include/uapi/linux/btrfs.h
index dea8931..b33da24 100644
--- a/include/uapi/linux/btrfs.h
+++ b/include/uapi/linux/btrfs.h
@@ -445,6 +445,27 @@ struct btrfs_ioctl_get_dev_stats {
__u64 unused[128 - 2 - BTRFS_DEV_STAT_VALUES_MAX]; /* pad to 1k */
};
+/*
+ * de-duplication control modes
+ * For re-config, re-enable will handle it
+ * TODO: Add support to disable per-file/dir dedup operation
+ */
+#define BTRFS_DEDUP_CTL_ENABLE 1
+#define BTRFS_DEDUP_CTL_DISABLE 2
+#define BTRFS_DEDUP_CTL_STATUS 3
+#define BTRFS_DEDUP_CTL_LAST 4
+struct btrfs_ioctl_dedup_args {
+ __u16 cmd; /* In: command(see above macro) */
+ __u64 blocksize; /* In/Out: For enable/status */
+ __u64 limit_nr; /* In/Out: For enable/status */
+ __u64 current_nr; /* Out: For status output */
+ __u16 backend; /* In/Out: For enable/status */
+ __u16 hash_type; /* In/Out: For enable/status */
+ u8 status; /* Out: For status output */
+ /* pad to 512 bytes */
+ u8 __unused[489];
+};
+
#define BTRFS_QUOTA_CTL_ENABLE 1
#define BTRFS_QUOTA_CTL_DISABLE 2
#define BTRFS_QUOTA_CTL_RESCAN__NOTUSED 3
@@ -653,6 +674,8 @@ static inline char *btrfs_err_str(enum btrfs_err_code err_code)
struct btrfs_ioctl_dev_replace_args)
#define BTRFS_IOC_FILE_EXTENT_SAME _IOWR(BTRFS_IOCTL_MAGIC, 54, \
struct btrfs_ioctl_same_args)
+#define BTRFS_IOC_DEDUP_CTL _IOWR(BTRFS_IOCTL_MAGIC, 55, \
+ struct btrfs_ioctl_dedup_args)
#define BTRFS_IOC_GET_FEATURES _IOR(BTRFS_IOCTL_MAGIC, 57, \
struct btrfs_ioctl_feature_flags)
#define BTRFS_IOC_SET_FEATURES _IOW(BTRFS_IOCTL_MAGIC, 57, \
--
2.6.4
^ permalink raw reply related [flat|nested] 15+ messages in thread