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

idr: fix a subtle bug in idr_get_next()

2013-03-03T22:09:04+00:00

commit 6cdae7416a1c45c2ce105a78187d9b7e8feb9e24 upstream.

The iteration logic of idr_get_next() is borrowed mostly verbatim from
idr_for_each().  It walks down the tree looking for the slot matching
the current ID.  If the matching slot is not found, the ID is
incremented by the distance of single slot at the given level and
repeats.

The implementation assumes that during the whole iteration id is aligned
to the layer boundaries of the level closest to the leaf, which is true
for all iterations starting from zero or an existing element and thus is
fine for idr_for_each().

However, idr_get_next() may be given any point and if the starting id
hits in the middle of a non-existent layer, increment to the next layer
will end up skipping the same offset into it.  For example, an IDR with
IDs filled between [64, 127] would look like the following.

          [  0  64 ... ]
       /----/   |
       |        |
      NULL    [ 64 ... 127 ]

If idr_get_next() is called with 63 as the starting point, it will try
to follow down the pointer from 0.  As it is NULL, it will then try to
proceed to the next slot in the same level by adding the slot distance
at that level which is 64 - making the next try 127.  It goes around the
loop and finds and returns 127 skipping [64, 126].

Note that this bug also triggers in idr_for_each_entry() loop which
deletes during iteration as deletions can make layers go away leaving
the iteration with unaligned ID into missing layers.

Fix it by ensuring proceeding to the next slot doesn't carry over the
unaligned offset - ie.  use round_up(id + 1, slot_distance) instead of
id += slot_distance.

Signed-off-by: Tejun Heo 
Reported-by: David Teigland 
Cc: KAMEZAWA Hiroyuki 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds 
Signed-off-by: Greg Kroah-Hartman

docbook: add idr/ida to kernel-api docbook

2010-10-27T00:40:56+00:00

Add idr/ida to kernel-api docbook.
Fix typos and kernel-doc notation.

Signed-off-by: Randy Dunlap 
Acked-by: Tejun Heo 
Cc: Naohiro Aota 
Cc: Jiri Kosina 
Signed-off-by: Linus Torvalds

idr: fix idr_pre_get() locking description

2010-10-26T23:52:18+00:00

Despite the idr_pre_get() kernel-doc, there are some cases where you can
call idr_pre_get() from within locked regions.  Add a description for such
cases.

See also: http://lkml.org/lkml/2010/9/16/462

[akpm@linux-foundation.org: cleanups, grammatical fixes]
Signed-off-by: Naohiro Aota 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: describe how nextidp works in idr_get_next().

2010-08-31T07:43:59+00:00

It was unclear in original kernel-doc how nextidp worked in
idr_get_next(). Let's describe it.

Signed-off-by: Naohiro Aota 
Acked-by: Tejun Heo 
Signed-off-by: Jiri Kosina

idr: fix kernel-doc warnings.

2010-08-31T07:32:02+00:00

Fix the following kernel-doc warnings.

% perl scripts/kernel-doc lib/idr.c > /dev/null
Warning(lib/idr.c:300): No description found for parameter 'starting_id'
Warning(lib/idr.c:300): Excess function parameter 'start_id' description in 'idr_get_new_above'
Warning(lib/idr.c:485): No description found for parameter 'idp'
Warning(lib/idr.c:596): No description found for parameter 'nextidp'
Warning(lib/idr.c:596): Excess function parameter 'id' description in 'idr_get_next'
Warning(lib/idr.c:774): No description found for parameter 'starting_id'
Warning(lib/idr.c:774): Excess function parameter 'staring_id' description in 'ida_get_new_above'
Warning(lib/idr.c:918): No description found for parameter 'ida'

Signed-off-by: Naohiro Aota 
Acked-by: Tejun Heo 
Signed-off-by: Jiri Kosina

idr: fix RCU lockdep splat in idr_get_next()

2010-06-23T13:50:45+00:00

Convert to rcu_dereference_raw() given that many callers may have many
different locking models.

Located-by: Miles Lane 
Tested-by: Miles Lane 
Signed-off-by: Paul E. McKenney

idr: fix backtrack logic in idr_remove_all

2010-05-27T16:12:48+00:00

Currently idr_remove_all will fail with a use after free error if
idr::layers is bigger than 2, which on 32 bit systems corresponds to items
more than 1024.  This is due to stepping back too many levels during
backtracking.  For simplicity let's assume that IDR_BITS=1 -> we have 2
nodes at each level below the root node and each leaf node stores two IDs.
 (In reality for 32 bit systems IDR_BITS=5, with 32 nodes at each sub-root
level and 32 IDs in each leaf node).  The sequence of freeing the nodes at
the moment is as follows:

layer
1 ->                       a(7)
2 ->            b(3)                  c(5)
3 ->        d(1)   e(2)           f(4)    g(6)

Until step 4 things go fine, but then node c is freed, whereas node g
should be freed first.  Since node c contains the pointer to node g we'll
have a use after free error at step 6.

How many levels we step back after visiting the leaf nodes is currently
determined by the msb of the id we are currently visiting:

Step
1.          node d with IDs 0,1 is freed, current ID is advanced to 2.
            msb of the current ID bit 1. This means we need to step back
            1 level to node b and take the next sibling, node e.
2-3.        node e with IDs 2,3 is freed, current ID is 4, msb is bit 2.
            This means we need to step back 2 levels to node a, freeing
            node b on the way.
4-5.        node f with IDs 4,5 is freed, current ID is 6, msb is still
            bit 2. This means we again need to step back 2 levels to node
            a and free c on the way.
6.          We should visit node g, but its pointer is not available as
            node c was freed.

The fix changes how we determine the number of levels to step back.
Instead of deducting this merely from the msb of the current ID, we should
really check if advancing the ID causes an overflow to a bit position
corresponding to a given layer.  In the above example overflow from bit 0
to bit 1 should mean stepping back 1 level.  Overflow from bit 1 to bit 2
should mean stepping back 2 levels and so on.

The fix was tested with IDs up to 1 << 20, which corresponds to 4 layers
on 32 bit systems.

Signed-off-by: Imre Deak 
Reviewed-by: Tejun Heo 
Cc: Eric Paris 
Cc: "Paul E. McKenney" 
Cc: 		[2.6.34.1]
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6

2010-03-26T14:55:59+00:00

Conflicts:
	drivers/mtd/nand/sh_flctl.c

Maxim's patch to initialise sysfs attributes depends on the patch which
actually adds sysfs_attr_init().

Merge branch 'master' of git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux-2.6

2010-02-26T19:06:24+00:00

The SmartMedia FTL code depends on new kfifo bits from 2.6.33

idr: export idr_get_next()

2010-02-25T11:54:51+00:00

idr_get_next() was accidentally not exported when added.  It is about
to be used by mtdcore, which may be built as a module.

Signed-off-by: Ben Hutchings 
Acked-by: KAMEZAWA Hiroyuki 
Signed-off-by: Artem Bityutskiy 
Signed-off-by: David Woodhouse