From patchwork Mon May 18 12:51:53 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Joe Thornber X-Patchwork-Id: 6428761 X-Patchwork-Delegate: snitzer@redhat.com Return-Path: X-Original-To: patchwork-dm-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 869C6C0432 for ; Mon, 18 May 2015 12:56:18 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id AD41C205BA for ; Mon, 18 May 2015 12:56:17 +0000 (UTC) Received: from mx5-phx2.redhat.com (mx5-phx2.redhat.com [209.132.183.37]) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 10BAB205BD for ; Mon, 18 May 2015 12:56:12 +0000 (UTC) Received: from lists01.pubmisc.prod.ext.phx2.redhat.com (lists01.pubmisc.prod.ext.phx2.redhat.com [10.5.19.33]) by mx5-phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t4ICq0KS057095; Mon, 18 May 2015 08:52:01 -0400 Received: from int-mx13.intmail.prod.int.phx2.redhat.com (int-mx13.intmail.prod.int.phx2.redhat.com [10.5.11.26]) by lists01.pubmisc.prod.ext.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id t4ICpxXt015581 for ; Mon, 18 May 2015 08:51:59 -0400 Received: from localhost (vpn1-5-251.ams2.redhat.com [10.36.5.251]) by int-mx13.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id t4ICpwtD030619 for ; Mon, 18 May 2015 08:51:59 -0400 Date: Mon, 18 May 2015 13:51:53 +0100 From: Joe Thornber To: device-mapper development Message-ID: <20150518125152.GA10459@rh-vpn> Mail-Followup-To: device-mapper development References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Scanned-By: MIMEDefang 2.68 on 10.5.11.26 X-loop: dm-devel@redhat.com Subject: Re: [dm-devel] Possible BUG in the entry removal process of dm-btree structure X-BeenThere: dm-devel@redhat.com X-Mailman-Version: 2.1.12 Precedence: junk Reply-To: device-mapper development List-Id: device-mapper development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: dm-devel-bounces@redhat.com Errors-To: dm-devel-bounces@redhat.com X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP On Mon, May 18, 2015 at 03:21:52PM +0800, Dennis Yang wrote: > Hi, > > Recently, I had run into the same dm-btree-remove bug reported before > in this mailing list. Hi Dennis, You diagnosis looks correct, though I think your patch introduces entry reordering. > In dm-btree-remove.c, there is a redistribute3() function which is > called when we try to rebalance the entry of three nodes with their > total entry count is higher than a defined threshold. I paste the code > below for further discussion. > > target = (nr_left + nr_center + nr_right) / 3; > if (nr_left < nr_right) { > s = nr_left - target; > > if (s < 0 && nr_center < -s) { > /* not enough in central node */ > shift(left, center, nr_center); > s = nr_center - target; > shift(left, right, s); > nr_right += s; > } else > shift(left, center, s); > > shift(center, right, target - nr_right); > } else { > > If the entry count of left node is smaller than target and the entry > count of center node is not enough to cover this gap, I think what we > try to do here is to move all the entries in the center node to the > left node first, then move some entries from the right node to the > left one to make its entry count equals to target. However, since > nr_center is always positive, the code above will first move up to > nr_center entries from the left node to the center node. Yep, this is a bug, it should be -nr_center. > To fix this issue, I think we should stick with the plan that move all > the entries from center node to left/right node first, and then make > it up to target entries by moving them from right/left node to it. I > have attached a simple patch to demonstrate the idea here. > > diff --git a/linux-3.12.6/drivers/md/persistent-data/dm-btree-remove.c > b/linux-3.12.6/drivers/md/persistent-data/dm-btree-remove.c > index b88757c..9026fb8 100644 > --- a/linux-3.12.6/drivers/md/persistent-data/dm-btree-remove.c > +++ b/linux-3.12.6/drivers/md/persistent-data/dm-btree-remove.c > @@ -309,8 +309,9 @@ static void redistribute3(struct dm_btree_info > *info, struct btree_node *parent, > > if (s < 0 && nr_center < -s) { > /* not enough in central node */ > - shift(left, center, nr_center); > - s = nr_center - target; > + shift(center, left, nr_center); You can't put the nodes out of order, what you actually want to do is: shift(left, center, -nr_center). Other than that your patch looks good. Updated patch below. Thanks, - Joe --- dm-devel mailing list dm-devel@redhat.com https://www.redhat.com/mailman/listinfo/dm-devel diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c index e04cfd2..9836c0a 100644 --- a/drivers/md/persistent-data/dm-btree-remove.c +++ b/drivers/md/persistent-data/dm-btree-remove.c @@ -309,8 +309,8 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, if (s < 0 && nr_center < -s) { /* not enough in central node */ - shift(left, center, nr_center); - s = nr_center - target; + shift(left, center, -nr_center); + s += nr_center; shift(left, right, s); nr_right += s; } else @@ -323,7 +323,7 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent, if (s > 0 && nr_center < s) { /* not enough in central node */ shift(center, right, nr_center); - s = target - nr_center; + s -= nr_center; shift(left, right, s); nr_left -= s; } else