linux-kernel - RE: [External] Re: [PATCH] dm-writecache: avoid unnecessary lookups in writecache_find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Wed, 24 Apr 2019 04:08:24 +0000
From:   Huaisheng HS1 Ye <yehs1@...ovo.com>
To:     Mikulas Patocka <mpatocka@...hat.com>
CC:     "snitzer@...hat.com" <snitzer@...hat.com>,
        "agk@...hat.com" <agk@...hat.com>,
        "prarit@...hat.com" <prarit@...hat.com>,
        NingTing Cheng <chengnt@...ovo.com>,
        "dm-devel@...hat.com" <dm-devel@...hat.com>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>,
        Huaisheng Ye <yehs2007@...o.com>
Subject: RE: [External]  Re: [PATCH] dm-writecache: avoid unnecessary lookups
 in writecache_find_entry

From: Mikulas Patocka <mpatocka@...hat.com>
Sent: Tuesday, April 23, 2019 11:44 PM
> 
> On Sun, 21 Apr 2019, Huaisheng Ye wrote:
> 
> > From: Huaisheng Ye <yehs1@...ovo.com>
> >
> > Only when entry has been found, that would only be necessary to check the
> > lowest or highest seq-count.
> >
> > Add local variable "found" in writecache_find_entry, if no entry has been
> > found, it is meaningless that having a useless rb_prev or rb_next.
> 
> 
> Hi
> 
> I don't quite see what is this patch trying to fix.
> Don't fix something that isn't broken

Hi Mikulas,

Thanks for your reply.
This patch is not designed for fixing logical error. That is used for optimizing the behavior of writecache_find_entry.

Let me give an example to illustrate the point below.
Suppose that is the case, here is a normal READ bio comes to writecache_map. And because of bio's direction is READ, writecache_find_entry would be called with flags WFE_RETURN_FOLLOWING.

Now there are two scenarios, 
1. writecache_find_entry successfully get an existing entry by searching rb_tree, we could call it HIT. Then the first 'while' will be finished by 'break'. Next it will move to second 'while' loop, because of the flags hasn't been marked as WFE_LOWEST_SEQ. writecache_find_entry will try to return an entry with HIGHEST_SEQ, if there are other entries which has same original_sector in rb_tree.
For this situation, the current code is okay to deal with it.

2. writecache_find_entry couldn't get an existing entry from rb_tree, we could call it MISS. Because of same flags WFE_RETURN_FOLLOWING, writecache_find_entry will get other entry, which's original_sector will slightly larger than input parameter block, with big probability.
For this scenario, function writecache_find_entry doesn't need to enter second 'while' loop. But current code would still try to check there were other entry with same original_sector.
So the additional rb_next or rb_prev is unnecessary by this case, also the code doesn't need to compare the original_sector of 'e2' with parameter 'block'.

My patch is designed to optimize the second case. so we could skip the second 'while' loop when the block is missed from rb_tree.

Cheers,
Huaisheng Ye

> 
> > Signed-off-by: Huaisheng Ye <yehs1@...ovo.com>
> > ---
> >  drivers/md/dm-writecache.c | 12 ++++++++++--
> >  1 file changed, 10 insertions(+), 2 deletions(-)
> >
> > diff --git a/drivers/md/dm-writecache.c b/drivers/md/dm-writecache.c
> > index ddf1732..047ae09 100644
> > --- a/drivers/md/dm-writecache.c
> > +++ b/drivers/md/dm-writecache.c
> > @@ -537,14 +537,18 @@ static struct wc_entry *writecache_find_entry(struct dm_writecache *wc,
> >  {
> >  	struct wc_entry *e;
> >  	struct rb_node *node = wc->tree.rb_node;
> > +	bool found = false;
> >
> >  	if (unlikely(!node))
> >  		return NULL;
> >
> >  	while (1) {
> >  		e = container_of(node, struct wc_entry, rb_node);
> > -		if (read_original_sector(wc, e) == block)
> > +		if (read_original_sector(wc, e) == block) {
> > +			found = true;
> >  			break;
> > +		}
> > +
> >  		node = (read_original_sector(wc, e) >= block ?
> >  			e->rb_node.rb_left : e->rb_node.rb_right);
> >  		if (unlikely(!node)) {
> > @@ -564,7 +568,8 @@ static struct wc_entry *writecache_find_entry(struct dm_writecache *wc,
> >  		}
> >  	}
> >
> > -	while (1) {
> > +	/* only need to check lowest or highest seq-count when entry has been found */
> > +	while (found) {
> >  		struct wc_entry *e2;
> >  		if (flags & WFE_LOWEST_SEQ)
> >  			node = rb_prev(&e->rb_node);
> > @@ -577,6 +582,9 @@ static struct wc_entry *writecache_find_entry(struct dm_writecache *wc,
> >  			return e;
> >  		e = e2;
> >  	}
> > +
> > +	/* no entry has been found, return the following entry */
> > +	return e;
> >  }
> >
> >  static void writecache_insert_entry(struct dm_writecache *wc, struct wc_entry *ins)
> > --
> > 1.8.3.1
> >
> >