From: Timofey Titovets <nefelim4ag@gmail.com>
To: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
Cc: linux-btrfs <linux-btrfs@vger.kernel.org>,
wangxg.fnst@cn.fujitsu.com, Qu Wenruo <quwenruo@cn.fujitsu.com>
Subject: Re: [PATCH v15.1 03/13] btrfs: dedupe: Introduce function to add hash into in-memory tree
Date: Thu, 8 Nov 2018 23:18:07 +0300 [thread overview]
Message-ID: <CAGqmi769aCwRcC893u+ms101_BEG5uaS-3_Nh7jYQhhCkzRARA@mail.gmail.com> (raw)
In-Reply-To: <20181106064122.6154-4-lufq.fnst@cn.fujitsu.com>
вт, 6 нояб. 2018 г. в 9:41, Lu Fengqi <lufq.fnst@cn.fujitsu.com>:
>
> 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_dedupe_add() interface.
>
> Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
> Signed-off-by: Wang Xiaoguang <wangxg.fnst@cn.fujitsu.com>
> Reviewed-by: Josef Bacik <jbacik@fb.com>
> Signed-off-by: Lu Fengqi <lufq.fnst@cn.fujitsu.com>
> ---
> fs/btrfs/dedupe.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 150 insertions(+)
>
> diff --git a/fs/btrfs/dedupe.c b/fs/btrfs/dedupe.c
> index 06523162753d..784bb3a8a5ab 100644
> --- a/fs/btrfs/dedupe.c
> +++ b/fs/btrfs/dedupe.c
> @@ -19,6 +19,14 @@ struct inmem_hash {
> u8 hash[];
> };
>
> +static inline struct inmem_hash *inmem_alloc_hash(u16 algo)
> +{
> + if (WARN_ON(algo >= ARRAY_SIZE(btrfs_hash_sizes)))
> + return NULL;
> + return kzalloc(sizeof(struct inmem_hash) + btrfs_hash_sizes[algo],
> + GFP_NOFS);
> +}
> +
> static struct btrfs_dedupe_info *
> init_dedupe_info(struct btrfs_ioctl_dedupe_args *dargs)
> {
> @@ -167,3 +175,145 @@ int btrfs_dedupe_disable(struct btrfs_fs_info *fs_info)
> /* Place holder for bisect, will be implemented in later patches */
> return 0;
> }
> +
> +static int inmem_insert_hash(struct rb_root *root,
> + struct inmem_hash *hash, int hash_len)
> +{
> + struct rb_node **p = &root->rb_node;
> + struct rb_node *parent = NULL;
> + struct inmem_hash *entry = NULL;
> +
> + while (*p) {
> + parent = *p;
> + entry = rb_entry(parent, struct inmem_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 inmem_hash *hash)
> +{
> + struct rb_node **p = &root->rb_node;
> + struct rb_node *parent = NULL;
> + struct inmem_hash *entry = NULL;
> +
> + while (*p) {
> + parent = *p;
> + entry = rb_entry(parent, struct inmem_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_dedupe_info *dedupe_info,
> + struct inmem_hash *hash)
> +{
> + list_del(&hash->lru_list);
> + rb_erase(&hash->hash_node, &dedupe_info->hash_root);
> + rb_erase(&hash->bytenr_node, &dedupe_info->bytenr_root);
> +
> + if (!WARN_ON(dedupe_info->current_nr == 0))
> + dedupe_info->current_nr--;
> +
> + kfree(hash);
> +}
> +
> +/*
> + * Insert a hash into in-memory dedupe 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_dedupe_info *dedupe_info,
> + struct btrfs_dedupe_hash *hash)
> +{
> + int ret = 0;
> + u16 algo = dedupe_info->hash_algo;
> + struct inmem_hash *ihash;
> +
> + ihash = inmem_alloc_hash(algo);
> +
> + if (!ihash)
> + return -ENOMEM;
> +
> + /* Copy the data out */
> + ihash->bytenr = hash->bytenr;
> + ihash->num_bytes = hash->num_bytes;
> + memcpy(ihash->hash, hash->hash, btrfs_hash_sizes[algo]);
> +
> + mutex_lock(&dedupe_info->lock);
> +
> + ret = inmem_insert_bytenr(&dedupe_info->bytenr_root, ihash);
> + if (ret > 0) {
> + kfree(ihash);
> + ret = 0;
> + goto out;
> + }
> +
> + ret = inmem_insert_hash(&dedupe_info->hash_root, ihash,
> + btrfs_hash_sizes[algo]);
> + if (ret > 0) {
> + /*
> + * We only keep one hash in tree to save memory, so if
> + * hash conflicts, free the one to insert.
> + */
> + rb_erase(&ihash->bytenr_node, &dedupe_info->bytenr_root);
> + kfree(ihash);
> + ret = 0;
> + goto out;
> + }
> +
> + list_add(&ihash->lru_list, &dedupe_info->lru_list);
> + dedupe_info->current_nr++;
> +
> + /* Remove the last dedupe hash if we exceed limit */
> + while (dedupe_info->current_nr > dedupe_info->limit_nr) {
> + struct inmem_hash *last;
> +
> + last = list_entry(dedupe_info->lru_list.prev,
> + struct inmem_hash, lru_list);
> + __inmem_del(dedupe_info, last);
> + }
> +out:
> + mutex_unlock(&dedupe_info->lock);
> + return 0;
> +}
> +
> +int btrfs_dedupe_add(struct btrfs_fs_info *fs_info,
> + struct btrfs_dedupe_hash *hash)
> +{
> + struct btrfs_dedupe_info *dedupe_info = fs_info->dedupe_info;
> +
> + if (!fs_info->dedupe_enabled || !hash)
> + return 0;
> +
> + if (WARN_ON(dedupe_info == NULL))
> + return -EINVAL;
> +
> + if (WARN_ON(!btrfs_dedupe_hash_hit(hash)))
> + return -EINVAL;
> +
> + /* ignore old hash */
> + if (dedupe_info->blocksize != hash->num_bytes)
> + return 0;
> +
> + if (dedupe_info->backend == BTRFS_DEDUPE_BACKEND_INMEMORY)
> + return inmem_add(dedupe_info, hash);
> + return -EINVAL;
> +}
> --
> 2.19.1
>
>
>
Reviewed-by: Timofey Titovets <nefelim4ag@gmail.com>
Thanks.
--
Have a nice day,
Timofey.
next prev parent reply other threads:[~2018-11-08 20:18 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-11-06 6:41 [PATCH v15.1 00/13] Btrfs In-band De-duplication Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 01/13] btrfs: dedupe: Introduce dedupe framework and its header Lu Fengqi
2018-11-08 9:53 ` Timofey Titovets
2018-11-09 21:10 ` Josef Bacik
2018-11-06 6:41 ` [PATCH v15.1 02/13] btrfs: dedupe: Introduce function to initialize dedupe info Lu Fengqi
2018-11-08 12:31 ` Timofey Titovets
2018-11-06 6:41 ` [PATCH v15.1 03/13] btrfs: dedupe: Introduce function to add hash into in-memory tree Lu Fengqi
2018-11-08 20:18 ` Timofey Titovets [this message]
2018-11-06 6:41 ` [PATCH v15.1 04/13] btrfs: dedupe: Introduce function to remove hash from " Lu Fengqi
2018-11-09 21:17 ` Josef Bacik
2018-11-06 6:41 ` [PATCH v15.1 05/13] btrfs: delayed-ref: Add support for increasing data ref under spinlock Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 06/13] btrfs: dedupe: Introduce function to search for an existing hash Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 07/13] btrfs: dedupe: Implement btrfs_dedupe_calc_hash interface Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 08/13] btrfs: ordered-extent: Add support for dedupe Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 09/13] btrfs: introduce type based delalloc metadata reserve Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 10/13] btrfs: dedupe: Inband in-memory only de-duplication implement Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 11/13] btrfs: dedupe: Add ioctl for inband deduplication Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 12/13] btrfs: relocation: Enhance error handling to avoid BUG_ON Lu Fengqi
2018-11-06 6:41 ` [PATCH v15.1 13/13] btrfs: dedupe: Introduce new reconfigure ioctl Lu Fengqi
2018-11-10 7:21 ` [PATCH v15.1 00/13] Btrfs In-band De-duplication Anand Jain
2018-11-13 13:45 ` David Sterba
2018-11-14 3:47 ` Lu Fengqi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAGqmi769aCwRcC893u+ms101_BEG5uaS-3_Nh7jYQhhCkzRARA@mail.gmail.com \
--to=nefelim4ag@gmail.com \
--cc=linux-btrfs@vger.kernel.org \
--cc=lufq.fnst@cn.fujitsu.com \
--cc=quwenruo@cn.fujitsu.com \
--cc=wangxg.fnst@cn.fujitsu.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).