[PATCH 3.13.y-ckt 035/136] bcache: fix a livelock when we cause a huge number of cache misses

From: Kamal Mostafa
Date: Tue Feb 02 2016 - 13:58:15 EST


3.13.11-ckt34 -stable review patch. If anyone has any objections, please let me know.

---8<------------------------------------------------------------

From: Zheng Liu <gnehzuil.liu@xxxxxxxxx>

commit 2ef9ccbfcb90cf84bdba320a571b18b05c41101b upstream.

Subject : [PATCH v2] bcache: fix a livelock in btree lock
Date : Wed, 25 Feb 2015 20:32:09 +0800 (02/25/2015 04:32:09 AM)

This commit tries to fix a livelock in bcache. This livelock might
happen when we causes a huge number of cache misses simultaneously.

When we get a cache miss, bcache will execute the following path.

->cached_dev_make_request()
->cached_dev_read()
->cached_lookup()
->bch->btree_map_keys()
->btree_root() <------------------------
->bch_btree_map_keys_recurse() |
->cache_lookup_fn() |
->cached_dev_cache_miss() |
->bch_btree_insert_check_key() -|
[If btree->seq is not equal to seq + 1, we should return
EINTR and traverse btree again.]

In bch_btree_insert_check_key() function we first need to check upgrade
flag (op->lock == -1), and when this flag is true we need to release
read btree->lock and try to take write btree->lock. During taking and
releasing this write lock, btree->seq will be monotone increased in
order to prevent other threads modify this in cache miss (see btree.h:74).
But if there are some cache misses caused by some requested, we could
meet a livelock because btree->seq is always changed by others. Thus no
one can make progress.

This commit will try to take write btree->lock if it encounters a race
when we traverse btree. Although it sacrifice the scalability but we
can ensure that only one can modify the btree.

Signed-off-by: Zheng Liu <wenqing.lz@xxxxxxxxxx>
Tested-by: Joshua Schmid <jschmid@xxxxxxxx>
Tested-by: Eric Wheeler <bcache@xxxxxxxxxxxxxxxxxx>
Cc: Joshua Schmid <jschmid@xxxxxxxx>
Cc: Zhu Yanhai <zhu.yanhai@xxxxxxxxx>
Cc: Kent Overstreet <kmo@xxxxxxxxxxxxx>
Signed-off-by: Jens Axboe <axboe@xxxxxx>
Signed-off-by: Kamal Mostafa <kamal@xxxxxxxxxxxxx>
---
drivers/md/bcache/btree.c | 4 +++-
1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c
index 7966ff8..7b76e7b 100644
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@ -2213,8 +2213,10 @@ int bch_btree_insert_check_key(struct btree *b, struct btree_op *op,
rw_lock(true, b, b->level);

if (b->key.ptr[0] != btree_ptr ||
- b->seq != seq + 1)
+ b->seq != seq + 1) {
+ op->lock = b->level;
goto out;
+ }
}

SET_KEY_PTRS(check_key, 1);
--
1.9.1