lkml.org 
[lkml]   [2014]   [Apr]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 1/7 V3] idr: fix overflow bug during maximum ID calculation at maximum height
    Date
    idr_replace() open-codes the logic to calculate the maximum valid ID
    given the height of the idr tree; unfortunately, the open-coded logic
    doesn't account for the fact that the top layer may have unused slots
    and over-shifts the limit to zero when the tree is at its maximum
    height.

    The following test code shows it fails to replace the value for id=((1<<27)+42):

    static void test5(void)
    {
    int id;
    DEFINE_IDR(test_idr);
    #define TEST5_START ((1<<27)+42) /* use the highest layer */

    printk(KERN_INFO "Start test5\n");
    id = idr_alloc(&test_idr, (void *)1, TEST5_START, 0, GFP_KERNEL);
    BUG_ON(id != TEST5_START);
    TEST_BUG_ON(idr_replace(&test_idr, (void *)2, TEST5_START) != (void *)1);
    idr_destroy(&test_idr);
    printk(KERN_INFO "End of test5\n");
    }

    Fix the bug by using idr_max() which correctly takes into account the
    maximum allowed shift.

    sub_alloc() shares the same problem and may incorrectly fail with
    -EAGAIN; however, this bug doesn't affect correct operation because
    idr_get_empty_slot(), which already uses idr_max(), retries with the
    increased @id in such cases.

    tj: Updated patch description.

    CC: stable@vger.kernel.org
    Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
    Acked-by: Tejun Heo <tj@kernel.org>
    ---
    lib/idr.c | 8 +++-----
    1 files changed, 3 insertions(+), 5 deletions(-)

    diff --git a/lib/idr.c b/lib/idr.c
    index 2642fa8..4df6792 100644
    --- a/lib/idr.c
    +++ b/lib/idr.c
    @@ -249,7 +249,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,
    id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;

    /* if already at the top layer, we need to grow */
    - if (id >= 1 << (idp->layers * IDR_BITS)) {
    + if (id > idr_max(idp->layers)) {
    *starting_id = id;
    return -EAGAIN;
    }
    @@ -811,12 +811,10 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
    if (!p)
    return ERR_PTR(-EINVAL);

    - n = (p->layer+1) * IDR_BITS;
    -
    - if (id >= (1 << n))
    + if (id > idr_max(p->layer + 1))
    return ERR_PTR(-EINVAL);

    - n -= IDR_BITS;
    + n = p->layer * IDR_BITS;
    while ((n > 0) && p) {
    p = p->ary[(id >> n) & IDR_MASK];
    n -= IDR_BITS;
    --
    1.7.4.4


    \
     
     \ /
      Last update: 2014-04-22 08:41    [W:5.619 / U:0.020 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site