Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932362AbcCBBPz (ORCPT ); Tue, 1 Mar 2016 20:15:55 -0500 Received: from mail333.us4.mandrillapp.com ([205.201.137.77]:34623 "EHLO mail333.us4.mandrillapp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755630AbcCAXzj (ORCPT ); Tue, 1 Mar 2016 18:55:39 -0500 DomainKey-Signature: a=rsa-sha1; c=nofws; q=dns; s=mandrill; d=linuxfoundation.org; b=Ial61V+cI1gYBqNprCEmXSrE+ksu774WuNkr6GXvCp6adAfVr5HJAllx2hjnK3ztlSNwF7VfRHKJ 4GJspBKSlXoDS5IqQ0sMwh/WlIXfk85UcRc40QmBeL0OwAz6RbG2pwVWCq7m4m3QQGhl4G9hYPCp e8T7UqM6w6LKX02M4Nk=; From: Greg Kroah-Hartman Subject: [PATCH 4.4 062/342] bcache: fix a livelock when we cause a huge number of cache misses X-Mailer: git-send-email 2.7.2 To: Cc: Greg Kroah-Hartman , , Zheng Liu , Joshua Schmid , Eric Wheeler , Zhu Yanhai , Kent Overstreet , Jens Axboe Message-Id: <20160301234530.006909801@linuxfoundation.org> In-Reply-To: <20160301234527.990448862@linuxfoundation.org> References: <20160301234527.990448862@linuxfoundation.org> X-Report-Abuse: Please forward a copy of this message, including all headers, to abuse@mandrill.com X-Report-Abuse: You can also report abuse here: http://mandrillapp.com/contact/abuse?id=30481620.f0298d185fb74c10bed0f73433025cf2 X-Mandrill-User: md_30481620 Date: Tue, 01 Mar 2016 23:54:04 +0000 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 2551 Lines: 68 4.4-stable review patch. If anyone has any objections, please let me know. ------------------ From: Zheng Liu 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 Tested-by: Joshua Schmid Tested-by: Eric Wheeler Cc: Joshua Schmid Cc: Zhu Yanhai Cc: Kent Overstreet Signed-off-by: Jens Axboe Signed-off-by: Greg Kroah-Hartman --- drivers/md/bcache/btree.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) --- a/drivers/md/bcache/btree.c +++ b/drivers/md/bcache/btree.c @@ -2162,8 +2162,10 @@ int bch_btree_insert_check_key(struct bt 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);