dm-writecache: avoid unnecessary lookups in writecache_find_entry
PATCH 1/1 dm-writecache: avoid unnecessary lookups in writecache_find_entry
From: Huaisheng Ye <[email protected]>
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.
--- drivers/md/dm-writecache.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)
drivers/md/dm-writecache.c +10 -2
@@ -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)
Signature · 1 line
1.8.3.1
Mikulas Patocka
maintainerQuoted 7 lines · Huaisheng Ye
From: Huaisheng Ye <[email protected]>
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 uselessrb_prevorrb_next.
Hi
I don't quite see what is this patch trying to fix. Don't fix something that isn't broken.
Mikulas
Quoted 53 lines
Signed-off-by Huaisheng Ye <[email protected]>--- drivers/md/dm-writecache.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)drivers/md/dm-writecache.c +10
-2@@ -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)Signature · 1 line
1.8.3.1
From: Mikulas Patocka <[email protected]>
Sent: Tuesday, April 23, 2019 11:44 PM
Quoted 8 lines · Huaisheng Ye
Quoted 6 lines
From: Huaisheng Ye <[email protected]>
Only when entry has been found, that would only be necessary to check the lowest or highest seq-count.
Quoted 8 lines
Quoted 2 lines
Add local variable "found" in
writecache_find_entry, if no entry has been found, it is meaningless that having a uselessrb_prevorrb_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
Quoted 54 lines
Quoted 54 lines
Signed-off-by Huaisheng Ye <[email protected]>--- drivers/md/dm-writecache.c | 12 ++++++++++-- 1 file changed, 10 insertions(+), 2 deletions(-)drivers/md/dm-writecache.c +10
-3@@ -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
Mikulas Patocka
maintainerQuoted 31 lines · On Wed, 24 Apr 2019, Huaisheng HS1 Ye wrote:
From: Mikulas Patocka <[email protected]>
Sent: Tuesday, April 23, 2019 11:44 PMQuoted 8 lines · Huaisheng Ye
Quoted 6 lines
From: Huaisheng Ye <[email protected]>
Only when entry has been found, that would only be necessary to check the lowest or highest seq-count.
Quoted 8 lines
Quoted 2 lines
Add local variable "found" in
writecache_find_entry, if no entry has been found, it is meaningless that having a uselessrb_prevorrb_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 ofwritecache_find_entry.Let me give an example to illustrate the point below.
Suppose that is the case, here is a normal READ bio comes towritecache_map. And because of bio's direction is READ,writecache_find_entrywould be called with flagsWFE_RETURN_FOLLOWING.Now there are two scenarios,
1.writecache_find_entrysuccessfully get an existing entry by searchingrb_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 asWFE_LOWEST_SEQ.writecache_find_entrywill try to return an entry withHIGHEST_SEQ, if there are other entries which has sameoriginal_sectorinrb_tree. For this situation, the current code is okay to deal with it.
Quoted 8 lines
2.
writecache_find_entrycouldn't get an existing entry fromrb_tree, we could call it MISS. Because of same flagsWFE_RETURN_FOLLOWING,writecache_find_entrywill get other entry, which'soriginal_sectorwill slightly larger than input parameter block, with big probability. For this scenario, functionwritecache_find_entrydoesn't need to enter second 'while' loop. But current code would still try to check there were other entry with sameoriginal_sector.
So the additionalrb_nextorrb_previs unnecessary by this case, also the code doesn't need to compare theoriginal_sectorof '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
From: Mikulas Patocka <[email protected]>
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.
--- drivers/md/dm-writecache.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
drivers/md/dm-writecache.c +2 -2
@@ -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; } } }