linux-stable.git/lib/idr.c, branch v3.16.78

idr: reduce the unneeded check in free_layer()

2014-06-06T23:08:12+00:00

If "idr->hint == p" is true, it also implies "idr->hint" is true(not NULL).

Signed-off-by: Lai Jiangshan 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: don't need to shink the free list when idr_remove()

2014-06-06T23:08:12+00:00

After idr subsystem is changed to RCU-awared, the free layer will not go
to the free list.  The free list will not be filled up when
idr_remove().  So we don't need to shink it too.

Signed-off-by: Lai Jiangshan 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: fix idr_replace()'s returned error code

2014-06-06T23:08:12+00:00

When the smaller id is not found, idr_replace() returns -ENOENT.  But
when the id is bigger enough, idr_replace() returns -EINVAL, actually
there is no difference between these two kinds of ids.

These are all unallocated id, the return values of the idr_replace() for
these ids should be the same: -ENOENT.

Signed-off-by: Lai Jiangshan 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: fix NULL pointer dereference when ida_remove(unallocated_id)

2014-06-06T23:08:12+00:00

If the ida has at least one existing id, and when an unallocated ID
which meets a certain condition is passed to the ida_remove(), the
system will crash because it hits NULL pointer dereference.

The condition is that the unallocated ID shares the same lowest idr
layer with the existing ID, but the idr slot would be different if the
unallocated ID were to be allocated.

In this case the matching idr slot for the unallocated_id is NULL,
causing @bitmap to be NULL which the function dereferences without
checking crashing the kernel.

See the test code:

  static void test3(void)
  {
        int id;
        DEFINE_IDA(test_ida);

        printk(KERN_INFO "Start test3\n");
        if (ida_pre_get(&test_ida, GFP_KERNEL) < 0) return;
        if (ida_get_new(&test_ida,  &id) < 0) return;
        ida_remove(&test_ida, 4000); /* bug: null deference here */
        printk(KERN_INFO "End of test3\n");
  }

It happens only when the caller tries to free an unallocated ID which is
the caller's fault.  It is not a bug.  But it is better to add the
proper check and complain rather than crashing the kernel.

[tj@kernel.org: updated patch description]
Signed-off-by: Lai Jiangshan 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: fix unexpected ID-removal when idr_remove(unallocated_id)

2014-06-06T23:08:12+00:00

If unallocated_id = (ANY * idr_max(idp->layers) + existing_id) is passed
to idr_remove().  The existing_id will be removed unexpectedly.

The following test shows this unexpected id-removal:

  static void test4(void)
  {
        int id;
        DEFINE_IDR(test_idr);

        printk(KERN_INFO "Start test4\n");
        id = idr_alloc(&test_idr, (void *)1, 42, 43, GFP_KERNEL);
        BUG_ON(id != 42);
        idr_remove(&test_idr, 42 + IDR_SIZE);
        TEST_BUG_ON(idr_find(&test_idr, 42) != (void *)1);
        idr_destroy(&test_idr);
        printk(KERN_INFO "End of test4\n");
  }

ida_remove() shares the similar problem.

It happens only when the caller tries to free an unallocated ID which is
the caller's fault.  It is not a bug.  But it is better to add the
proper check and complain rather than removing an existing_id silently.

Signed-off-by: Lai Jiangshan 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: fix overflow bug during maximum ID calculation at maximum height

2014-06-06T23:08:12+00:00

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: Lai Jiangshan 
Acked-by: Tejun Heo 
Cc: 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib/idr.c: use RCU_INIT_POINTER(x, NULL)

2014-04-07T23:36:07+00:00

Replace rcu_assign_pointer(x, NULL) with RCU_INIT_POINTER(x, NULL)

The rcu_assign_pointer() ensures that the initialization of a structure
is carried out before storing a pointer to that structure.  And in the
case of the NULL pointer, there is no structure to initialize.

So, rcu_assign_pointer(p, NULL) can be safely converted to
RCU_INIT_POINTER(p, NULL)

Signed-off-by: Monam Agarwal 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: remove dead code

2014-04-07T23:36:07+00:00

Remove no longer used deprecated code, and make local functions
static.

Signed-off-by: Stephen Hemminger 
Acked-by: Jean Delvare 
Acked-by: Tejun Heo 
Cc: Jeff Layton 
Cc: Philipp Reisner 
Cc: Jens Axboe 
Cc: George Spelvin 
Cc: Randy Dunlap 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: Add new function idr_is_empty()

2014-02-17T15:27:47+00:00

Signed-off-by: Andreas Gruenbacher 
Signed-off-by: Philipp Reisner

idr: print a stack dump after ida_remove warning

2013-07-03T23:08:04+00:00

We print a dump stack after idr_remove warning.  This is useful to find
the faulty piece of code.  Let's do the same for ida_remove, as it would
be equally useful there.

[akpm@linux-foundation.org: convert the open-coded printk+dump_stack into WARN()]
Signed-off-by: Jean Delvare 
Cc: Tejun Heo 
Cc: Takashi Iwai 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds