bcache: fix a livelock in btree lock
PATCH 1/1 bcache: fix a livelock in btree lock
From: Zheng Liu <[email protected]>
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.
--- drivers/md/bcache/btree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
drivers/md/bcache/btree.c +3 -1
@@ -2163,8 +2163,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->c->root->level +1 ; goto out; + } }SET_KEY_PTRS (check_key,1 );
Signature · 1 line
2.1.2
Zheng,
It should be 'op->lock = b->level', not 'op->lock = b->c->root->level
+ 1', otherwise we will stop all concurrency writes unconditionally in the second round. Isn't it?
-zyh
2015-02-03 19:21 GMT+08:00 Joshua Schmid <[email protected]>:
Quoted 61 lines
From: Zheng Liu <[email protected]>
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 readbtree->lockand try to take writebtree->lock. During taking and releasing this write lock,btree->seqwill 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 becausebtree->seqis always changed by others. Thus no one can make progress.This commit will try to take write
btree->lockif 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 <[email protected]>Tested-by Joshua Schmid <[email protected]>--- drivers/md/bcache/btree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)drivers/md/bcache/btree.c +3
-2@@ -2163,8 +2163,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->c->root->level +1 ; goto out; + } }SET_KEY_PTRS (check_key,1 ); --2.1.2
--
To unsubscribe from this list: send the line "unsubscribe linux-bcache" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Quoted 5 lines · Zhu Yanhai
Zheng,
It should be '
op->lock=b->level', not 'op->lock=b->c->root->level
+ 1', otherwise we will stop all concurrency writes unconditionally in the second round. Isn't it?
You're right. I will fix this problem and re-send the patch that will be rebased against the latest upstream kernel.
Thanks,
- Zheng
Quoted 69 lines
-zyh
2015-02-03 19:21 GMT+08:00 Joshua Schmid <[email protected]>:
Quoted 57 lines
From: Zheng Liu <[email protected]>
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 readbtree->lockand try to take writebtree->lock. During taking and releasing this write lock,btree->seqwill 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 becausebtree->seqis always changed by others. Thus no one can make progress.This commit will try to take write
btree->lockif 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 <[email protected]>Tested-by Joshua Schmid <[email protected]>--- drivers/md/bcache/btree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)drivers/md/bcache/btree.c +3
-2@@ -2163,8 +2163,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->c->root->level +1 ; goto out; + } }SET_KEY_PTRS (check_key,1 ); --2.1.2
Quoted 4 lines
--
To unsubscribe from this list: send the line "unsubscribe linux-bcache" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html--
To unsubscribe from this list: send the line "unsubscribe linux-bcache" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html