lkml.org 
[lkml]   [2016]   [Jan]   [27]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 4.2.y-ckt 069/268] bcache: fix a livelock when we cause a huge number of cache misses
    Date
    4.2.8-ckt3 -stable review patch.  If anyone has any objections, please let me know.

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

    From: Zheng Liu <gnehzuil.liu@gmail.com>

    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@taobao.com>
    Tested-by: Joshua Schmid <jschmid@suse.com>
    Tested-by: Eric Wheeler <bcache@linux.ewheeler.net>
    Cc: Joshua Schmid <jschmid@suse.com>
    Cc: Zhu Yanhai <zhu.yanhai@gmail.com>
    Cc: Kent Overstreet <kmo@daterainc.com>
    Signed-off-by: Jens Axboe <axboe@fb.com>
    Signed-off-by: Kamal Mostafa <kamal@canonical.com>
    ---
    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 00cde40..9aaa8f8 100644
    --- a/drivers/md/bcache/btree.c
    +++ b/drivers/md/bcache/btree.c
    @@ -2162,8 +2162,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
    \
     
     \ /
      Last update: 2016-01-27 23:01    [W:4.191 / U:0.196 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site