lkml.org 
[lkml]   [2015]   [Nov]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 4.1 49/86] dm btree remove: fix a bug when rebalancing nodes after removal
    Date
    4.1-stable review patch.  If anyone has any objections, please let me know.

    ------------------

    From: Joe Thornber <ejt@redhat.com>

    commit 2871c69e025e8bc507651d5a9cf81a8a7da9d24b upstream.

    Commit 4c7e309340ff ("dm btree remove: fix bug in redistribute3") wasn't
    a complete fix for redistribute3().

    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.

    Fix this issue by being more careful about calculating the target number
    of 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

    Signed-off-by: Joe Thornber <ejt@redhat.com>
    Signed-off-by: Mike Snitzer <snitzer@redhat.com>
    Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

    ---
    drivers/md/persistent-data/dm-btree-remove.c | 17 +++++++++++------
    1 file changed, 11 insertions(+), 6 deletions(-)

    --- 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_btre
    {
    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_btre
    } 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_btre
    } 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];



    \
     
     \ /
      Last update: 2015-11-06 21:41    [W:3.392 / U:0.008 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site