Yet Another In-band(online) deduplication implement

index aac314e..68ffd26 100644
@@ -3825,6 +3825,11 @@ int btrfs_lookup_bio_sums(struct btrfs_root *root, struct inode *inode,
 			  struct bio *bio, u32 *dst);
 int btrfs_lookup_bio_sums_dio(struct btrfs_root *root, struct inode *inode,
 			      struct bio *bio, u64 logical_offset);
+void btrfs_fill_file_extent(struct btrfs_trans_handle *trans,
+			    struct btrfs_path *path, u64 disk_bytenr,
+			    u64 disk_num_bytes, u64 offset, u64 num_bytes,
+			    u64 ram_bytes, u8 type, u8 compression,
+			    u8 encryption, u16 other_encoding);
 int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
 			     struct btrfs_root *root,
 			     u64 objectid, u64 pos,

index 58ece65..e1d7c03 100644
@@ -37,6 +37,46 @@
 				   sizeof(struct btrfs_ordered_sum)) / \
 				   sizeof(u32) * (r)->sectorsize)
 
+/*
+ * Fill contents of the file extent.
+ *
+ * The file extent is indicated by path.
+ * It's mainlly used to reduce the duplicated codes, but also added some extra
+ * safety check.
+ */
+void btrfs_fill_file_extent(struct btrfs_trans_handle *trans,
+			    struct btrfs_path *path, u64 disk_bytenr,
+			    u64 disk_num_bytes, u64 offset, u64 num_bytes,
+			    u64 ram_bytes, u8 type, u8 compression,
+			    u8 encryption, u16 other_encoding)
+{
+	struct btrfs_key key;
+	struct extent_buffer *node = path->nodes[0];
+	struct btrfs_file_extent_item *item;
+	int slot = path->slots[0];
+
+	BUG_ON(encryption || other_encoding);
+	BUG_ON(type == BTRFS_FILE_EXTENT_INLINE);
+
+	btrfs_item_key_to_cpu(node, &key, slot);
+	WARN_ON(key.type != BTRFS_EXTENT_DATA_KEY);
+
+	item = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
+
+	btrfs_set_file_extent_generation(node, item, trans->transid);
+	btrfs_set_file_extent_disk_bytenr(node, item, disk_bytenr);
+	btrfs_set_file_extent_disk_num_bytes(node, item, disk_num_bytes);
+	btrfs_set_file_extent_offset(node, item, offset);
+	btrfs_set_file_extent_num_bytes(node, item, num_bytes);
+	btrfs_set_file_extent_ram_bytes(node, item, ram_bytes);
+	btrfs_set_file_extent_type(node, item, type);
+	btrfs_set_file_extent_compression(node, item, compression);
+	btrfs_set_file_extent_other_encoding(node, item, 0);
+	btrfs_set_file_extent_encryption(node, item, 0);
+
+	btrfs_mark_buffer_dirty(node);
+}
+
 int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
 			     struct btrfs_root *root,
 			     u64 objectid, u64 pos,

index e1d7c03..87a8d85 100644
@@ -88,7 +88,6 @@ int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
 	struct btrfs_file_extent_item *item;
 	struct btrfs_key file_key;
 	struct btrfs_path *path;
-	struct extent_buffer *leaf;
 
 	path = btrfs_alloc_path();
 	if (!path)

@@ -103,21 +102,10 @@ int btrfs_insert_file_extent(struct btrfs_trans_handle *trans,
 	if (ret < 0)
 		goto out;
 	BUG_ON(ret); /* Can't happen */
-	leaf = path->nodes[0];
-	item = btrfs_item_ptr(leaf, path->slots[0],
-			      struct btrfs_file_extent_item);
-	btrfs_set_file_extent_disk_bytenr(leaf, item, disk_offset);
-	btrfs_set_file_extent_disk_num_bytes(leaf, item, disk_num_bytes);
-	btrfs_set_file_extent_offset(leaf, item, offset);
-	btrfs_set_file_extent_num_bytes(leaf, item, num_bytes);
-	btrfs_set_file_extent_ram_bytes(leaf, item, ram_bytes);
-	btrfs_set_file_extent_generation(leaf, item, trans->transid);
-	btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
-	btrfs_set_file_extent_compression(leaf, item, compression);
-	btrfs_set_file_extent_encryption(leaf, item, encryption);
-	btrfs_set_file_extent_other_encoding(leaf, item, other_encoding);
-
-	btrfs_mark_buffer_dirty(leaf);
+	btrfs_fill_file_extent(trans, path, disk_offset, disk_num_bytes,
+			       offset, num_bytes, ram_bytes,
+			       BTRFS_FILE_EXTENT_REG, compression, encryption,
+			       other_encoding);
 out:
 	btrfs_free_path(path);
 	return ret;

index e33dff3..3221010 100644
@@ -2052,7 +2052,6 @@ static int insert_reserved_file_extent(struct btrfs_trans_handle *trans,
 	struct btrfs_root *root = BTRFS_I(inode)->root;
 	struct btrfs_file_extent_item *fi;
 	struct btrfs_path *path;
-	struct extent_buffer *leaf;
 	struct btrfs_key ins;
 	int extent_inserted = 0;
 	int ret;

@@ -2087,21 +2086,9 @@ static int insert_reserved_file_extent(struct btrfs_trans_handle *trans,
 		if (ret)
 			goto out;
 	}
-	leaf = path->nodes[0];
-	fi = btrfs_item_ptr(leaf, path->slots[0],
-			    struct btrfs_file_extent_item);
-	btrfs_set_file_extent_generation(leaf, fi, trans->transid);
-	btrfs_set_file_extent_type(leaf, fi, extent_type);
-	btrfs_set_file_extent_disk_bytenr(leaf, fi, disk_bytenr);
-	btrfs_set_file_extent_disk_num_bytes(leaf, fi, disk_num_bytes);
-	btrfs_set_file_extent_offset(leaf, fi, 0);
-	btrfs_set_file_extent_num_bytes(leaf, fi, num_bytes);
-	btrfs_set_file_extent_ram_bytes(leaf, fi, ram_bytes);
-	btrfs_set_file_extent_compression(leaf, fi, compression);
-	btrfs_set_file_extent_encryption(leaf, fi, encryption);
-	btrfs_set_file_extent_other_encoding(leaf, fi, other_encoding);
-
-	btrfs_mark_buffer_dirty(leaf);
+	btrfs_fill_file_extent(trans, path, disk_bytenr, disk_num_bytes, 0,
+			       num_bytes, ram_bytes, extent_type, compression,
+			       encryption, other_encoding);
 	btrfs_release_path(path);
 
 	inode_add_bytes(inode, num_bytes);

@@ -2391,7 +2378,6 @@ static noinline int relink_extent_backref(struct btrfs_path *path,
 				 struct sa_defrag_extent_backref *backref)
 {
 	struct btrfs_file_extent_item *extent;
-	struct btrfs_file_extent_item *item;
 	struct btrfs_ordered_extent *ordered;
 	struct btrfs_trans_handle *trans;
 	struct btrfs_fs_info *fs_info;

@@ -2548,21 +2534,9 @@ again:
 		goto out_free_path;
 	}
 
-	leaf = path->nodes[0];
-	item = btrfs_item_ptr(leaf, path->slots[0],
-				struct btrfs_file_extent_item);
-	btrfs_set_file_extent_disk_bytenr(leaf, item, new->bytenr);
-	btrfs_set_file_extent_disk_num_bytes(leaf, item, new->disk_len);
-	btrfs_set_file_extent_offset(leaf, item, start - new->file_pos);
-	btrfs_set_file_extent_num_bytes(leaf, item, len);
-	btrfs_set_file_extent_ram_bytes(leaf, item, new->len);
-	btrfs_set_file_extent_generation(leaf, item, trans->transid);
-	btrfs_set_file_extent_type(leaf, item, BTRFS_FILE_EXTENT_REG);
-	btrfs_set_file_extent_compression(leaf, item, new->compress_type);
-	btrfs_set_file_extent_encryption(leaf, item, 0);
-	btrfs_set_file_extent_other_encoding(leaf, item, 0);
-
-	btrfs_mark_buffer_dirty(leaf);
+	btrfs_fill_file_extent(trans, path, new->bytenr, new->disk_len,
+			       start - new->file_pos, len, new->len,
+			       BTRFS_FILE_EXTENT_REG, new->compress_type, 0, 0);
 	inode_add_bytes(inode, len);
 	btrfs_release_path(path);
 

index 68ffd26..7f37637 100644
@@ -38,6 +38,7 @@
 #include "extent_io.h"
 #include "extent_map.h"
 #include "async-thread.h"
+#include "dedup.h"
 
 struct btrfs_trans_handle;
 struct btrfs_transaction;

@@ -1788,6 +1789,9 @@ struct btrfs_fs_info {
 	 * and will be latter freed. Protected by fs_info->chunk_mutex.
 	 */
 	struct list_head pinned_chunks;
+
+	/* Inband deduplication stuff */
+	struct btrfs_dedup_root *dedup_root;
 };
 
 struct btrfs_subvolume_writers {

@@ -3685,6 +3689,7 @@ static inline void free_fs_info(struct btrfs_fs_info *fs_info)
 	kfree(fs_info->super_copy);
 	kfree(fs_info->super_for_commit);
 	security_free_mnt_opts(&fs_info->security_opts);
+	btrfs_free_dedup(fs_info);
 	kfree(fs_info);
 }
 

88 lines not on this page · raw message

84 lines not on this page · raw message

index a9aadb2..3997bd9 100644
@@ -49,6 +49,7 @@
 #include "raid56.h"
 #include "sysfs.h"
 #include "qgroup.h"
+#include "dedup.h"
 
 #ifdef CONFIG_X86
 #include <asm/cpufeature.h>

@@ -2633,6 +2634,12 @@ int open_ctree(struct super_block *sb,
 
 	INIT_LIST_HEAD(&fs_info->pinned_chunks);
 
+	/* TODO: use real dedup type other than 0 */
+	ret = btrfs_init_dedup(fs_info, 0);
+	if (ret) {
+		err = -ret;
+		goto fail_alloc;
+	}
 	ret = btrfs_alloc_stripe_hash_table(fs_info);
 	if (ret) {
 		err = ret;

index 41f70f5..2bce303 100644
@@ -78,11 +78,176 @@ fail:
 	return ret;
 }
 
+static void __dedup_del_hash(struct btrfs_dedup_root *root,
+			     struct btrfs_dedup_hash *hash)
+{
+	list_del(&hash->lru_list);
+	rb_erase(&hash->hash_node, &root->hash_root);
+	rb_erase(&hash->bytenr_node, &root->bytenr_root);
+
+	WARN_ON(root->current_nr == 0);
+	root->current_nr--;
+}
+
 void btrfs_free_dedup(struct btrfs_fs_info *fs_info)
 {
-	if (!fs_info->dedup_root)
+	struct btrfs_dedup_hash *entry, *tmp;
+	struct btrfs_dedup_root *dedup_root = fs_info->dedup_root;
+
+	if (!dedup_root)
 		return;
 
-	kfree(fs_info->dedup_root);
+	spin_lock(&dedup_root->lock);
+	list_for_each_entry_safe(entry, tmp, &dedup_root->lru_list, lru_list) {
+		__dedup_del_hash(dedup_root, entry);
+		kmem_cache_free(btrfs_dedup_hash_cachep, entry);
+	}
+	spin_unlock(&dedup_root->lock);
+	kfree(dedup_root);
 	return;
 }
+
+static int __hash_page(struct btrfs_dedup_root *root, struct page *page,
+		       char *out)
+{
+	struct crypto_shash *tfm = root->dedup_driver;
+	struct {
+		struct shash_desc desc;
+		char ctx[crypto_shash_descsize(tfm)];
+	} sdesc;
+	char *kaddr;
+	int ret = 0;
+
+	sdesc.desc.tfm = tfm;
+	sdesc.desc.flags = 0;
+
+	kaddr = kmap_atomic(page);
+	ret = crypto_shash_digest(&sdesc.desc, kaddr, PAGE_SIZE,
+				  out);
+	kunmap_atomic(kaddr);
+
+	return ret;
+}
+
+/*
+ * Return 1 when the extent already exists
+ * Return 0 when inserted the one into bytenr tree.
+ */
+static int 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 + hash->offset < entry->bytenr + entry->offset)
+			p = &(*p)->rb_left;
+		else if (hash->bytenr + hash->offset > entry->bytenr +
+			 entry->offset)
+			p = &(*p)->rb_right;
+		else
+			return 1;
+	}
+	rb_link_node(&hash->bytenr_node, parent, p);
+	rb_insert_color(&hash->bytenr_node, root);
+	return 0;
+}
+
+/*
+ * Must ensure insert_bytenr is called before, ensure this dedup_hash
+ * is not already in the tree
+ */
+static int 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;
+		/* Now hash matches, still allow it to be inserted */
+		else if (hash->bytenr + hash->offset < entry->bytenr +
+			 entry->offset)
+			p = &(*p)->rb_left;
+		else if (hash->bytenr + hash->offset > entry->bytenr +
+			 entry->offset)
+			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 dedup_add_hash(struct btrfs_dedup_root *root,
+			  struct btrfs_dedup_hash *hash)
+{
+	int ret = 0;
+
+	WARN_ON(hash->bytenr == 0);
+
+	spin_lock(&root->lock);
+
+	ret = insert_bytenr(&root->bytenr_root, hash);
+	/* Already in tree */
+	if (ret > 0)
+		goto out;
+	insert_hash(&root->hash_root, hash,
+		    btrfs_dedup_sizes[root->dedup_type]);
+	list_add(&hash->lru_list, &root->lru_list);
+
+	root->current_nr++;
+
+	/* Remove the last dedup hash if we exceed limit */
+	while (root->limit_nr && root->current_nr > root->limit_nr) {
+		struct btrfs_dedup_hash *last;
+
+		last = list_entry(root->lru_list.prev, struct btrfs_dedup_hash,
+				  lru_list);
+		__dedup_del_hash(root, last);
+		kmem_cache_free(btrfs_dedup_hash_cachep, last);
+	}
+out:
+	spin_unlock(&root->lock);
+	return ret;
+}
+
+/*
+ * Caller must hold lock on dedup_root->lock during the use of the hash.
+ * As the dedup_hash hash can be freed at anytime.
+ */
+static struct btrfs_dedup_hash *
+dedup_search_by_hash(struct btrfs_dedup_root *root, u8 *hash)
+{
+	struct rb_node **p = &root->hash_root.rb_node;
+	struct rb_node *parent = NULL;
+	struct btrfs_dedup_hash *entry = NULL;
+	int hash_len = btrfs_dedup_sizes[root->dedup_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, &root->lru_list);
+			return entry;
+		}
+	}
+	return NULL;
+}