linux-toradex.git/lib/idr.c, branch v3.4.73

idr: fix a subtle bug in idr_get_next()

2013-03-03T22:06:40+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

Merge tag 'module-for-3.4' of git://git.kernel.org/pub/scm/linux/kernel/git/paulg/linux

2012-03-24T17:24:31+00:00

Pull cleanup of fs/ and lib/ users of module.h from Paul Gortmaker:
 "Fix up files in fs/ and lib/ dirs to only use module.h if they really
  need it.

  These are trivial in scope vs the work done previously.  We now have
  things where any few remaining cleanups can be farmed out to arch or
  subsystem maintainers, and I have done so when possible.  What is
  remaining here represents the bits that don't clearly lie within a
  single arch/subsystem boundary, like the fs dir and the lib dir.

  Some duplicate includes arising from overlapping fixes from
  independent subsystem maintainer submissions are also quashed."

Fix up trivial conflicts due to clashes with other include file cleanups
(including some due to the previous bug.h cleanup pull).

* tag 'module-for-3.4' of git://git.kernel.org/pub/scm/linux/kernel/git/paulg/linux:
  lib: reduce the use of module.h wherever possible
  fs: reduce the use of module.h wherever possible
  includecheck: delete any duplicate instances of module.h

idr: make idr_get_next() good for rcu_read_lock()

2012-03-22T00:55:01+00:00

Make one small adjustment to idr_get_next(): take the height from the top
layer (stable under RCU) instead of from the root (unprotected by RCU), as
idr_find() does: so that it can be used with RCU locking.  Copied comment
on RCU locking from idr_find().

Signed-off-by: Hugh Dickins 
Acked-by: KAMEZAWA Hiroyuki 
Acked-by: Li Zefan 
Cc: Eric Dumazet 
Acked-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib: reduce the use of module.h wherever possible

2012-03-07T20:04:04+00:00

For files only using THIS_MODULE and/or EXPORT_SYMBOL, map
them onto including export.h -- or if the file isn't even
using those, then just delete the include.  Fix up any implicit
include dependencies that were being masked by module.h along
the way.

Signed-off-by: Paul Gortmaker

ida: make ida_simple_get/put() IRQ safe

2011-11-02T23:07:00+00:00

It's often convenient to be able to release resource from IRQ context.
Make ida_simple_*() use irqsave/restore spin ops so that they are IRQ
safe.

Signed-off-by: Tejun Heo 
Acked-by: Rusty Russell 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

lib/idr.c: fix comment for ida_get_new_above()

2011-11-01T00:30:56+00:00

Signed-off-by: Wang Sheng-Hui 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

Merge branch 'master' into for-next

2011-09-15T13:08:18+00:00

Fast-forward merge with Linus to be able to merge patches
based on more recent version of the tree.

Fix kernel-doc comment typo '@id'

2011-08-04T13:42:05+00:00

Signed-off-by: Paul Bolle 
Signed-off-by: Jiri Kosina

ida: simplified functions for id allocation

2011-08-04T00:25:20+00:00

The current hyper-optimized functions are overkill if you simply want to
allocate an id for a device.  Create versions which use an internal
lock.

In followup patches, numerous drivers are converted to use this
interface.

Thanks to Tejun for feedback.

Signed-off-by: Rusty Russell 
Acked-by: Tejun Heo 
Acked-by: Jonathan Cameron 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

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