lkml.org 
[lkml]   [2020]   [Apr]   [23]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Date
    Subject[PATCH 3.16 064/245] dm btree: increase rebalance threshold in __rebalance2()
    3.16.83-rc1 review patch.  If anyone has any objections, please let me know.

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

    From: Hou Tao <houtao1@huawei.com>

    commit 474e559567fa631dea8fb8407ab1b6090c903755 upstream.

    We got the following warnings from thin_check during thin-pool setup:

    $ thin_check /dev/vdb
    examining superblock
    examining devices tree
    missing devices: [1, 84]
    too few entries in btree_node: 41, expected at least 42 (block 138, max_entries = 126)
    examining mapping tree

    The phenomenon is the number of entries in one node of details_info tree is
    less than (max_entries / 3). And it can be easily reproduced by the following
    procedures:

    $ new a thin pool
    $ presume the max entries of details_info tree is 126
    $ new 127 thin devices (e.g. 1~127) to make the root node being full
    and then split
    $ remove the first 43 (e.g. 1~43) thin devices to make the children
    reblance repeatedly
    $ stop the thin pool
    $ thin_check

    The root cause is that the B-tree removal procedure in __rebalance2()
    doesn't guarantee the invariance: the minimal number of entries in
    non-root node should be >= (max_entries / 3).

    Simply fix the problem by increasing the rebalance threshold to
    make sure the number of entries in each child will be greater
    than or equal to (max_entries / 3 + 1), so no matter which
    child is used for removal, the number will still be valid.

    Signed-off-by: Hou Tao <houtao1@huawei.com>
    Acked-by: Joe Thornber <ejt@redhat.com>
    Signed-off-by: Mike Snitzer <snitzer@redhat.com>
    Signed-off-by: Ben Hutchings <ben@decadent.org.uk>
    ---
    drivers/md/persistent-data/dm-btree-remove.c | 8 +++++++-
    1 file changed, 7 insertions(+), 1 deletion(-)

    --- a/drivers/md/persistent-data/dm-btree-remove.c
    +++ b/drivers/md/persistent-data/dm-btree-remove.c
    @@ -203,7 +203,13 @@ static void __rebalance2(struct dm_btree
    struct btree_node *right = r->n;
    uint32_t nr_left = le32_to_cpu(left->header.nr_entries);
    uint32_t nr_right = le32_to_cpu(right->header.nr_entries);
    - unsigned threshold = 2 * merge_threshold(left) + 1;
    + /*
    + * Ensure the number of entries in each child will be greater
    + * than or equal to (max_entries / 3 + 1), so no matter which
    + * child is used for removal, the number will still be not
    + * less than (max_entries / 3).
    + */
    + unsigned int threshold = 2 * (merge_threshold(left) + 1);

    if (nr_left + nr_right < threshold) {
    /*
    \
     
     \ /
      Last update: 2020-04-24 01:20    [W:3.673 / U:0.176 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site