[dm-devel] Possible bug when redistributing entries between dm-btree node

[Dennis Yang]

Hi,

I discover that the patch I post in the last mail is wrong. The
correct one is as follow.
The total number of entries of all three nodes should not be #MAX * 3
- 1 instead of #MAX * 3 + 2 to fix this bug.
Sorry for the troubles.

Dennis

 PATCH 1: skip redistributing entries
 ==========================================================
 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 6ec6065..592cd63 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
 @@ -313,7 +313,8 @@ static void redistribute3(struct dm_btree_info
*info, struct btree_node *parent,
         unsigned target = (nr_left + nr_center + nr_right) / 3;
         BUG_ON(target > max_entries);

 +       if (nr_left + nr_center + nr_right == max_entries * 3 - 1)
 +               return;

         if (nr_left < nr_right) {
                 s = nr_left - target;

 PATCH 2: bypass step 2
 =========================================================
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 6ec6065..2844a71 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
@@ -327,6 +325,9 @@ static void redistribute3(struct dm_btree_info
*info, struct btree_node *parent,
                } else
                        shift(left, center, s);

+               if (nr_left + nr_center + nr_right == max_entries * 3 - 1)
+                               return;
+
                shift(center, right, target - nr_right);

        } else {
@@ -340,6 +341,9 @@ static void redistribute3(struct dm_btree_info
*info, struct btree_node *parent,
                } else
                        shift(center, right, s);

+               if (nr_left + nr_center + nr_right == max_entries * 3 - 1)
+                               return;
+
                shift(left, center, nr_left - target);
        }




> Message: 1
> Date: Tue, 25 Aug 2015 19:12:15 +0800
> From: Dennis Yang <shinrairis at gmail.com>
> To: device-mapper development <dm-devel at redhat.com>
> Subject: [dm-devel] Possible bug when redistributing entries between
>         dm-btree node
> Message-ID:
>         <CAKTMprMdHAg4cFUw5NACnCg1zTJx-i=N8w0NRY8zujKQdoOYeA at mail.gmail.com>
> Content-Type: text/plain; charset=UTF-8
>
> Hi,
>
> A couple of months ago, I had been working on a dm-btree-remove bug
> reported before in this mailing list.
> (https://www.redhat.com/archives/dm-devel/2013-February/msg00063.html)
> We eventually found a bug in dm-btree-remove.c and delivered a patch
> to fix this, and you can find the discussion in this thread.
> (https://www.redhat.com/archives/dm-devel/2015-May/msg00113.html)
>
> However, I surprisingly find out that this patch did not solve our
> original issue which triggers the BUG_ON of shift() in
> dm-btree-remove.c when removing entries from btrees. Finally, we have
> discovered another corner case which might be the root cause of this
> issue. When redistributing entries between three nodes L (with #MAX
> entries), C (with #MAX-1 entries), and R (with #MAX entries), the
> redistribute3() will set target to #MAX-1 entries and start to move
> entry in the following steps.
>
> 1. Move 1 entry from node R to node C to make node R meet the target
> (#MAX-1) we set.
> 2. Move 1 entry from node L to node C to make node L also meet the
> target (#MAX-1)
>
> After step1, both node L and node C will have #MAX entries while node
> R has #MAX-1 entries.
> When doing step2, moving 1 entry from node L to node C will make node
> C has #MAX+1 entries which is not allowed and triggers the BUG_ON of
> shift().
>
> To solve this, we could bypass step2 or simply skip redistributing
> entries between nodes when the total entries of all three nodes equals
> (3 * #MAX + 2).
>
> PATCH 1: skip redistributing entries
> ======================================================================================================
> 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 6ec6065..592cd63 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
> @@ -313,7 +313,8 @@ static void redistribute3(struct dm_btree_info
> *info, struct btree_node *parent,
>         unsigned target = (nr_left + nr_center + nr_right) / 3;
>         BUG_ON(target > max_entries);
>
> +       if (nr_left + nr_center + nr_right == max_entries * 3 + 2)
> +               return;
>
>         if (nr_left < nr_right) {
>                 s = nr_left - target;
>
> PATCH 2: bypass step 2
> ======================================================================================================
> 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 6ec6065..2844a71 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
> @@ -327,6 +325,9 @@ static void redistribute3(struct dm_btree_info
> *info, struct btree_node *parent,
>                 } else
>                         shift(left, center, s);
>
> +               if (nr_left + nr_center + nr_right == max_entries * 3 + 2)
> +                               return;
> +
>                 shift(center, right, target - nr_right);
>
>         } else {
> @@ -340,6 +341,9 @@ static void redistribute3(struct dm_btree_info
> *info, struct btree_node *parent,
>                 } else
>                         shift(center, right, s);
>
> +               if (nr_left + nr_center + nr_right == max_entries * 3 + 2)
> +                               return;
> +
>                 shift(left, center, nr_left - target);
>         }
>
> Dennis