• Lai Jiangshan's avatar
    idr: fix overflow bug during maximum ID calculation at maximum height · 3afb69cb
    Lai Jiangshan authored
    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@kernel.org: Updated patch description.]
    Signed-off-by: default avatarLai Jiangshan <laijs@cn.fujitsu.com>
    Acked-by: default avatarTejun Heo <tj@kernel.org>
    Cc: <stable@vger.kernel.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    Signed-off-by: default avatarLinus Torvalds <torvalds@linux-foundation.org>
    3afb69cb
idr.c 28.5 KB