• Zheng Liu's avatar
    bcache: fix a livelock when we cause a huge number of cache misses · dbec969a
    Zheng Liu authored
    commit 2ef9ccbf 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: default avatarZheng Liu <wenqing.lz@taobao.com>
    Tested-by: default avatarJoshua Schmid <jschmid@suse.com>
    Tested-by: default avatarEric 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: default avatarJens Axboe <axboe@fb.com>
    Signed-off-by: default avatarLuis Henriques <luis.henriques@canonical.com>
    dbec969a
btree.c 56.4 KB