From: "J . Bruce Fields" <bfields@fieldses.org>
To: Trond Myklebust <trondmy@gmail.com>
Cc: linux-nfs@vger.kernel.org
Subject: Re: [PATCH 15/15] knfsd: Improve lookup performance in the duplicate reply cache using an rbtree
Date: Wed, 3 Oct 2018 20:44:33 -0400 [thread overview]
Message-ID: <20181004004433.GK17517@fieldses.org> (raw)
In-Reply-To: <20181001144157.3515-16-trond.myklebust@hammerspace.com>
On Mon, Oct 01, 2018 at 10:41:57AM -0400, Trond Myklebust wrote:
> Use an rbtree to ensure the lookup/insert of an entry in a DRC bucket is
> O(log(N)).
So the naming on those hash chain statistics are off now, but I guess
that's harmless.
All looks good to me, thanks--applying.
--b.
>
> Signed-off-by: Trond Myklebust <trond.myklebust@hammerspace.com>
> ---
> fs/nfsd/cache.h | 1 +
> fs/nfsd/nfscache.c | 37 ++++++++++++++++++++++++++-----------
> 2 files changed, 27 insertions(+), 11 deletions(-)
>
> diff --git a/fs/nfsd/cache.h b/fs/nfsd/cache.h
> index cbcdc15753b7..ef1c8aa89ca4 100644
> --- a/fs/nfsd/cache.h
> +++ b/fs/nfsd/cache.h
> @@ -29,6 +29,7 @@ struct svc_cacherep {
> struct sockaddr_in6 k_addr;
> } c_key;
>
> + struct rb_node c_node;
> struct list_head c_lru;
> unsigned char c_state, /* unused, inprog, done */
> c_type, /* status, buffer */
> diff --git a/fs/nfsd/nfscache.c b/fs/nfsd/nfscache.c
> index 230cc83921ad..e2fe0e9ce0df 100644
> --- a/fs/nfsd/nfscache.c
> +++ b/fs/nfsd/nfscache.c
> @@ -30,6 +30,7 @@
> #define TARGET_BUCKET_SIZE 64
>
> struct nfsd_drc_bucket {
> + struct rb_root rb_head;
> struct list_head lru_head;
> spinlock_t cache_lock;
> };
> @@ -129,6 +130,7 @@ nfsd_reply_cache_alloc(struct svc_rqst *rqstp, __wsum csum)
> if (rp) {
> rp->c_state = RC_UNUSED;
> rp->c_type = RC_NOCACHE;
> + RB_CLEAR_NODE(&rp->c_node);
> INIT_LIST_HEAD(&rp->c_lru);
>
> memset(&rp->c_key, 0, sizeof(rp->c_key));
> @@ -145,13 +147,14 @@ nfsd_reply_cache_alloc(struct svc_rqst *rqstp, __wsum csum)
> }
>
> static void
> -nfsd_reply_cache_free_locked(struct svc_cacherep *rp)
> +nfsd_reply_cache_free_locked(struct nfsd_drc_bucket *b, struct svc_cacherep *rp)
> {
> if (rp->c_type == RC_REPLBUFF && rp->c_replvec.iov_base) {
> drc_mem_usage -= rp->c_replvec.iov_len;
> kfree(rp->c_replvec.iov_base);
> }
> if (rp->c_state != RC_UNUSED) {
> + rb_erase(&rp->c_node, &b->rb_head);
> list_del(&rp->c_lru);
> atomic_dec(&num_drc_entries);
> drc_mem_usage -= sizeof(*rp);
> @@ -163,7 +166,7 @@ static void
> nfsd_reply_cache_free(struct nfsd_drc_bucket *b, struct svc_cacherep *rp)
> {
> spin_lock(&b->cache_lock);
> - nfsd_reply_cache_free_locked(rp);
> + nfsd_reply_cache_free_locked(b, rp);
> spin_unlock(&b->cache_lock);
> }
>
> @@ -219,7 +222,7 @@ void nfsd_reply_cache_shutdown(void)
> struct list_head *head = &drc_hashtbl[i].lru_head;
> while (!list_empty(head)) {
> rp = list_first_entry(head, struct svc_cacherep, c_lru);
> - nfsd_reply_cache_free_locked(rp);
> + nfsd_reply_cache_free_locked(&drc_hashtbl[i], rp);
> }
> }
>
> @@ -258,7 +261,7 @@ prune_bucket(struct nfsd_drc_bucket *b)
> if (atomic_read(&num_drc_entries) <= max_drc_entries &&
> time_before(jiffies, rp->c_timestamp + RC_EXPIRE))
> break;
> - nfsd_reply_cache_free_locked(rp);
> + nfsd_reply_cache_free_locked(b, rp);
> freed++;
> }
> return freed;
> @@ -349,17 +352,29 @@ static struct svc_cacherep *
> nfsd_cache_insert(struct nfsd_drc_bucket *b, struct svc_cacherep *key)
> {
> struct svc_cacherep *rp, *ret = key;
> - struct list_head *rh = &b->lru_head;
> + struct rb_node **p = &b->rb_head.rb_node,
> + *parent = NULL;
> unsigned int entries = 0;
> + int cmp;
>
> - list_for_each_entry(rp, rh, c_lru) {
> + while (*p != NULL) {
> ++entries;
> - if (nfsd_cache_key_cmp(key, rp) == 0) {
> + parent = *p;
> + rp = rb_entry(parent, struct svc_cacherep, c_node);
> +
> + cmp = nfsd_cache_key_cmp(key, rp);
> + if (cmp < 0)
> + p = &parent->rb_left;
> + else if (cmp > 0)
> + p = &parent->rb_right;
> + else {
> ret = rp;
> - break;
> + goto out;
> }
> }
> -
> + rb_link_node(&key->c_node, parent, p);
> + rb_insert_color(&key->c_node, &b->rb_head);
> +out:
> /* tally hash chain length stats */
> if (entries > longest_chain) {
> longest_chain = entries;
> @@ -414,7 +429,7 @@ nfsd_cache_lookup(struct svc_rqst *rqstp)
> spin_lock(&b->cache_lock);
> found = nfsd_cache_insert(b, rp);
> if (found != rp) {
> - nfsd_reply_cache_free_locked(rp);
> + nfsd_reply_cache_free_locked(NULL, rp);
> rp = found;
> goto found_entry;
> }
> @@ -462,7 +477,7 @@ nfsd_cache_lookup(struct svc_rqst *rqstp)
> break;
> default:
> printk(KERN_WARNING "nfsd: bad repcache type %d\n", rp->c_type);
> - nfsd_reply_cache_free_locked(rp);
> + nfsd_reply_cache_free_locked(b, rp);
> }
>
> goto out;
> --
> 2.17.1
next prev parent reply other threads:[~2018-10-04 7:35 UTC|newest]
Thread overview: 26+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-10-01 14:41 [PATCH 00/15] Performance improvements for knfsd Trond Myklebust
2018-10-01 14:41 ` [PATCH 01/15] SUNRPC: Remove the server 'authtab_lock' and just use RCU Trond Myklebust
2018-10-01 14:41 ` [PATCH 02/15] SUNRPC: Add lockless lookup of the server's auth domain Trond Myklebust
2018-10-01 14:41 ` [PATCH 03/15] SUNRPC: Allow cache lookups to use RCU protection rather than the r/w spinlock Trond Myklebust
2018-10-01 14:41 ` [PATCH 04/15] SUNRPC: Make server side AUTH_UNIX use lockless lookups Trond Myklebust
2018-10-01 14:41 ` [PATCH 05/15] knfsd: Allow lockless lookups of the exports Trond Myklebust
2018-10-01 14:41 ` [PATCH 06/15] SUNRPC: Lockless server RPCSEC_GSS context lookup Trond Myklebust
2018-10-01 14:41 ` [PATCH 07/15] knfsd: Lockless lookup of NFSv4 identities Trond Myklebust
2018-10-01 14:41 ` [PATCH 08/15] NFS: Lockless DNS lookups Trond Myklebust
2018-10-01 14:41 ` [PATCH 09/15] SUNRPC: Remove non-RCU protected lookup Trond Myklebust
2018-10-01 14:41 ` [PATCH 10/15] SUNRPC: Replace the cache_detail->hash_lock with a regular spinlock Trond Myklebust
2018-10-01 14:41 ` [PATCH 11/15] SUNRPC: Simplify TCP receive code Trond Myklebust
2018-10-01 14:41 ` [PATCH 12/15] knfsd: Remove dead code from nfsd_cache_lookup Trond Myklebust
2018-10-01 14:41 ` [PATCH 13/15] knfsd: Simplify NFS duplicate replay cache Trond Myklebust
2018-10-01 14:41 ` [PATCH 14/15] knfsd: Further simplify the cache lookup Trond Myklebust
2018-10-01 14:41 ` [PATCH 15/15] knfsd: Improve lookup performance in the duplicate reply cache using an rbtree Trond Myklebust
2018-10-04 0:44 ` J . Bruce Fields [this message]
2018-10-03 17:14 ` [PATCH 13/15] knfsd: Simplify NFS duplicate replay cache J . Bruce Fields
2018-10-03 18:01 ` Trond Myklebust
2018-10-03 18:11 ` bfields
2018-10-03 23:51 ` bfields
2018-10-03 16:10 ` [PATCH 08/15] NFS: Lockless DNS lookups J . Bruce Fields
2018-10-03 17:55 ` Trond Myklebust
2018-10-03 16:08 ` [PATCH 03/15] SUNRPC: Allow cache lookups to use RCU protection rather than the r/w spinlock J . Bruce Fields
2018-10-02 19:39 ` [PATCH 01/15] SUNRPC: Remove the server 'authtab_lock' and just use RCU J . Bruce Fields
2018-10-01 15:29 ` [PATCH 00/15] Performance improvements for knfsd Trond Myklebust
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=20181004004433.GK17517@fieldses.org \
--to=bfields@fieldses.org \
--cc=linux-nfs@vger.kernel.org \
--cc=trondmy@gmail.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).