[dm-devel] kernel BUG at drivers/md/persistent-data/dm-btree-remove.c:182!

[Joe Thornber]

On Tue, Oct 20, 2015 at 10:39:31AM +0800, Dennis Yang wrote:
> Hi,
> 
> After I analyzed the metadata of this case couple months ago, I find
> out that there is another possible bug which might trigger this
> assertion fail in shift(). I had posted a patch two months ago on the
> list to explain and fix this issue. Could you help reviewing this?
> 
> https://www.redhat.com/archives/dm-devel/2015-August/msg00155.html

Yep, that's a bug.  Sorry I missed it before when you posted.  Here's
my fix:

commit 05ce4edf20c7e4a0d7a3c8d87a3d4b6744d0fea2
Author: Joe Thornber <ejt at redhat.com>
Date:   Wed Oct 21 18:36:49 2015 +0100

    [dm-btree] Fix bug when rebalancing nodes after removal
    
    The redistribute3 function takes 3 btree nodes and shares out the entries
    evenly between them.  If the three nodes in total contained
    (MAX_ENTRIES * 3) - 1 entries between them then this was erroneously getting
    rebalanced as (MAX_ENTRIES - 1) on the left and right, and (MAX_ENTRIES + 1) in
    the center.
    
    This patch is more careful about calculating the target nr entries for the left
    and right nodes.
    
    Unit tested in userspace using this program:
    
    https://github.com/jthornber/redistribute3-test/blob/master/redistribute3_t.c

diff --git a/drivers/md/persistent-data/dm-btree-remove.c b/drivers/md/persistent-data/dm-btree-remove.c
index 4222f77..1dac15d 100644
--- a/drivers/md/persistent-data/dm-btree-remove.c
+++ b/drivers/md/persistent-data/dm-btree-remove.c
@@ -301,11 +301,16 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent,
 {
        int s;
        uint32_t max_entries = le32_to_cpu(left->header.max_entries);
-       unsigned target = (nr_left + nr_center + nr_right) / 3;
-       BUG_ON(target > max_entries);
+       unsigned total = nr_left + nr_center + nr_right;
+       unsigned target_right = total / 3;
+       unsigned remainder = (target_right * 3) != total;
+       unsigned target_left = target_right + remainder;
+
+       BUG_ON(target_left > max_entries);
+       BUG_ON(target_right > max_entries);
 
        if (nr_left < nr_right) {
-               s = nr_left - target;
+               s = nr_left - target_left;
 
                if (s < 0 && nr_center < -s) {
                        /* not enough in central node */
@@ -316,10 +321,10 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent,
                } else
                        shift(left, center, s);
 
-               shift(center, right, target - nr_right);
+               shift(center, right, target_right - nr_right);
 
        } else {
-               s = target - nr_right;
+               s = target_right - nr_right;
                if (s > 0 && nr_center < s) {
                        /* not enough in central node */
                        shift(center, right, nr_center);
@@ -329,7 +334,7 @@ static void redistribute3(struct dm_btree_info *info, struct btree_node *parent,
                } else
                        shift(center, right, s);
 
-               shift(left, center, nr_left - target);
+               shift(left, center, nr_left - target_left);
        }
 
        *key_ptr(parent, c->index) = center->keys[0];