On Tue, Mar 22, 2016 at 09:35:35AM +0800, Qu Wenruo wrote:
> Introduce a new tree, dedupe tree to record on-disk dedupe 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.
Thanks for refreshing this again, I'm starting to go through the disk
format in more detail.
>
> Signed-off-by: Liu Bo <bo.li.liu@xxxxxxxxxx>
> Signed-off-by: Wang Xiaoguang <wangxg.fnst@xxxxxxxxxxxxxx>
> Signed-off-by: Qu Wenruo <quwenruo@xxxxxxxxxxxxxx>
> ---
> fs/btrfs/ctree.h | 63 +++++++++++++++++++++++++++++++++++++++++++-
> fs/btrfs/dedupe.h | 5 ++++
> fs/btrfs/disk-io.c | 1 +
> include/trace/events/btrfs.h | 3 ++-
> 4 files changed, 70 insertions(+), 2 deletions(-)
>
> diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
> index 022ab61..bed9273 100644
> --- a/fs/btrfs/ctree.h
> +++ b/fs/btrfs/ctree.h
> @@ -100,6 +100,9 @@ struct btrfs_ordered_sum;
> /* tracks free space in block groups. */
> #define BTRFS_FREE_SPACE_TREE_OBJECTID 10ULL
>
> +/* on-disk dedupe tree (EXPERIMENTAL) */
> +#define BTRFS_DEDUPE_TREE_OBJECTID 11ULL
> +
> /* device stats in the device tree */
> #define BTRFS_DEV_STATS_OBJECTID 0ULL
>
> @@ -508,6 +511,7 @@ struct btrfs_super_block {
> * ones specified below then we will fail to mount
> */
> #define BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE (1ULL << 0)
> +#define BTRFS_FEATURE_COMPAT_RO_DEDUPE (1ULL << 1)
>
> #define BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF (1ULL << 0)
> #define BTRFS_FEATURE_INCOMPAT_DEFAULT_SUBVOL (1ULL << 1)
> @@ -537,7 +541,8 @@ struct btrfs_super_block {
> #define BTRFS_FEATURE_COMPAT_SAFE_CLEAR 0ULL
>
> #define BTRFS_FEATURE_COMPAT_RO_SUPP \
> - (BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE)
> + (BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE | \
> + BTRFS_FEATURE_COMPAT_RO_DEDUPE)
>
> #define BTRFS_FEATURE_COMPAT_RO_SAFE_SET 0ULL
> #define BTRFS_FEATURE_COMPAT_RO_SAFE_CLEAR 0ULL
> @@ -959,6 +964,42 @@ struct btrfs_csum_item {
> u8 csum;
> } __attribute__ ((__packed__));
>
> +/*
> + * Objectid: 0
> + * Type: BTRFS_DEDUPE_STATUS_ITEM_KEY
> + * Offset: 0
> + */
> +struct btrfs_dedupe_status_item {
> + __le64 blocksize;
> + __le64 limit_nr;
> + __le16 hash_type;
> + __le16 backend;
> +} __attribute__ ((__packed__));
> +
> +/*
> + * Objectid: Last 64 bit of the hash
> + * Type: BTRFS_DEDUPE_HASH_ITEM_KEY
> + * Offset: Bytenr of the hash
> + *
> + * Used for hash <-> bytenr search
> + */
> +struct btrfs_dedupe_hash_item {
> + /* length of dedupe range */
> + __le32 len;
> +
> + /* Hash follows */
> +} __attribute__ ((__packed__));
Are you storing the entire hash, or just the parts not represented in
the key? I'd like to keep the on-disk part as compact as possible for
this part.
> +
> +/*
> + * Objectid: bytenr
> + * Type: BTRFS_DEDUPE_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.
> + */
> +
Can we do this instead with a backref from the extent? It'll save us a
huge amount of IO as we delete things.
-chris
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
