LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
* Re: [PATCH] dm-writecache: avoid unnecessary lookups in writecache_find_entry
@ 2019-04-29  2:06 Huaisheng HS1 Ye
  0 siblings, 0 replies; 3+ messages in thread
From: Huaisheng HS1 Ye @ 2019-04-29  2:06 UTC (permalink / raw)
  To: Mikulas Patocka
  Cc: snitzer, agk, prarit, NingTing Cheng, dm-devel, linux-kernel,
	Huaisheng Ye


From: Mikulas Patocka <mpatocka@redhat.com>
Sent: Friday, April 26, 2019 9:59 PM
> 
> 
> On Wed, 24 Apr 2019, Huaisheng HS1 Ye wrote:
> 
> > From: Mikulas Patocka <mpatocka@redhat.com>
> > Sent: Tuesday, April 23, 2019 11:44 PM
> > >
> > > On Sun, 21 Apr 2019, Huaisheng Ye wrote:
> > >
> > > > From: Huaisheng Ye <yehs1@lenovo.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
> 
> So, it seems that we don't need the "found" variable at all, we could just
> return the variable "e" directly when we are in a position where "found"
> is false.
> 
> What about this patch? Could you test it?
> 
> Mikulas


Hi Mikulas,

Sure, I like your patch. It is quite straight forward.
And there is no logical difference between them, I have tested it and get a positive result.

Cheers,
Huaisheng Ye | 叶怀胜
Linux kernel | Lenovo DCG

> 
> 
> From: Mikulas Patocka <mpatocka@redhat.com>
> Subject: [PATCH] dm-writecache: a small optimization in writecache_find_entry
> 
> If we go past the condition "if (unlikely(!node))", we can be certain that
> there is no entry in the tree that has the block equal to the "block"
> variable.
> 
> Consequently, we can return the next entry directly, we don't need to go
> to the second part of the function that finds the entry with lowest or
> highest seq number that matches the "block" variable.
> 
> Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> 
> ---
>  drivers/md/dm-writecache.c |    4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> Index: linux-2.6/drivers/md/dm-writecache.c
> ===================================================================
> --- linux-2.6.orig/drivers/md/dm-writecache.c	2019-03-18 10:28:50.000000000 +0100
> +++ linux-2.6/drivers/md/dm-writecache.c	2019-04-26 15:49:18.000000000 +0200
> @@ -553,14 +553,14 @@ static struct wc_entry *writecache_find_
>  				return NULL;
>  			}
>  			if (read_original_sector(wc, e) >= block) {
> -				break;
> +				return e;
>  			} else {
>  				node = rb_next(&e->rb_node);
>  				if (unlikely(!node)) {
>  					return NULL;
>  				}
>  				e = container_of(node, struct wc_entry, rb_node);
> -				break;
> +				return e;
>  			}
>  		}
>  	}

^ permalink raw reply	[flat|nested] 3+ messages in thread

* Re: [PATCH] dm-writecache: avoid unnecessary lookups in writecache_find_entry
  2019-04-20 16:21 Huaisheng Ye
@ 2019-04-23 15:44 ` Mikulas Patocka
  0 siblings, 0 replies; 3+ messages in thread
From: Mikulas Patocka @ 2019-04-23 15:44 UTC (permalink / raw)
  To: Huaisheng Ye
  Cc: snitzer, agk, prarit, chengnt, dm-devel, linux-kernel, Huaisheng Ye



On Sun, 21 Apr 2019, Huaisheng Ye wrote:

> From: Huaisheng Ye <yehs1@lenovo.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.

Mikulas


> Signed-off-by: Huaisheng Ye <yehs1@lenovo.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
> 
> 

^ permalink raw reply	[flat|nested] 3+ messages in thread

* [PATCH] dm-writecache: avoid unnecessary lookups in writecache_find_entry
@ 2019-04-20 16:21 Huaisheng Ye
  2019-04-23 15:44 ` Mikulas Patocka
  0 siblings, 1 reply; 3+ messages in thread
From: Huaisheng Ye @ 2019-04-20 16:21 UTC (permalink / raw)
  To: mpatocka, snitzer, agk
  Cc: prarit, chengnt, dm-devel, linux-kernel, Huaisheng Ye

From: Huaisheng Ye <yehs1@lenovo.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.

Signed-off-by: Huaisheng Ye <yehs1@lenovo.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



^ permalink raw reply	[flat|nested] 3+ messages in thread

end of thread, other threads:[~2019-04-29  2:07 UTC | newest]

Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-04-29  2:06 [PATCH] dm-writecache: avoid unnecessary lookups in writecache_find_entry Huaisheng HS1 Ye
  -- strict thread matches above, loose matches on Subject: below --
2019-04-20 16:21 Huaisheng Ye
2019-04-23 15:44 ` Mikulas Patocka

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).