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

idr: introduce idr_alloc_cyclic()

2013-04-30T01:28:41+00:00

As Tejun points out, there are several users of the IDR facility that
attempt to use it in a cyclic fashion.  These users are likely to see
-ENOSPC errors after the counter wraps one or more times however.

This patchset adds a new idr_alloc_cyclic routine and converts several
of these users to it.  Many of these users are in obscure parts of the
kernel, and I don't have a good way to test some of them.  The change is
pretty straightforward though, so hopefully it won't be an issue.

There is one other cyclic user of idr_alloc that I didn't touch in
ipc/util.c.  That one is doing some strange stuff that I didn't quite
understand, but it looks like it should probably be converted later
somehow.

This patch:

Thus spake Tejun Heo:

    Ooh, BTW, the cyclic allocation is broken.  It's prone to -ENOSPC
    after the first wraparound.  There are several cyclic users in the
    kernel and I think it probably would be best to implement cyclic
    support in idr.

This patch does that by adding new idr_alloc_cyclic function that such
users in the kernel can use.  With this, there's no need for a caller to
keep track of the last value used as that's now tracked internally.  This
should prevent the ENOSPC problems that can hit when the "last allocated"
counter exceeds INT_MAX.

Later patches will convert existing cyclic users to the new interface.

Signed-off-by: Jeff Layton 
Reviewed-by: Tejun Heo 
Cc: "David S. Miller" 
Cc: "J. Bruce Fields" 
Cc: Eric Paris 
Cc: Jack Morgenstein 
Cc: John McCutchan 
Cc: Neil Horman 
Cc: Or Gerlitz 
Cc: Robert Love 
Cc: Roland Dreier 
Cc: Sridhar Samudrala 
Cc: Steve Wise 
Cc: Tom Tucker 
Cc: Vlad Yasevich 

Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: idr_alloc() shouldn't trigger lowmem warning when preloaded

2013-03-13T22:21:49+00:00

GFP_NOIO is often used for idr_alloc() inside preloaded section as the
allocation mask doesn't really matter.  If the idr tree needs to be
expanded, idr_alloc() first tries to allocate using the specified
allocation mask and if it fails falls back to the preloaded buffer.  This
order prevent non-preloading idr_alloc() users from taking advantage of
preloading ones by using preload buffer without filling it shifting the
burden of allocation to the preload users.

Unfortunately, this allowed/expected-to-fail kmem_cache allocation ends up
generating spurious slab lowmem warning before succeeding the request from
the preload buffer.

This patch makes idr_layer_alloc() add __GFP_NOWARN to the first
kmem_cache attempt and try kmem_cache again w/o __GFP_NOWARN after
allocation from preload_buffer fails so that lowmem warning is generated
if not suppressed by the original @gfp_mask.

Signed-off-by: Tejun Heo 
Reported-by: David Teigland 
Tested-by: David Teigland 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: deprecate idr_pre_get() and idr_get_new[_above]()

2013-03-13T22:21:47+00:00

Now that all in-kernel users are converted to ues the new alloc
interface, mark the old interface deprecated.  We should be able to
remove these in a few releases.

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

idr: fix new kernel-doc warnings

2013-03-13T03:42:09+00:00

Fix new kernel-doc warnings in idr:

  Warning(include/linux/idr.h:113): No description found for parameter 'idr'
  Warning(include/linux/idr.h:113): Excess function parameter 'idp' description in 'idr_find'
  Warning(lib/idr.c:232): Excess function parameter 'id' description in 'sub_alloc'
  Warning(lib/idr.c:232): Excess function parameter 'id' description in 'sub_alloc'

Signed-off-by: Randy Dunlap 
Acked-by: Tejun Heo 
Signed-off-by: Linus Torvalds

idr: remove WARN_ON_ONCE() on negative IDs

2013-03-08T23:05:34+00:00

idr_find(), idr_remove() and idr_replace() used to silently ignore the
sign bit and perform lookup with the rest of the bits.  The weird behavior
has been changed such that negative IDs are treated as invalid.  As the
behavior change was subtle, WARN_ON_ONCE() was added in the hope of
determining who's calling idr functions with negative IDs so that they can
be examined for problems.

Up until now, all two reported cases are ID number coming directly from
userland and getting fed into idr_find() and the warnings seem to cause
more problems than being helpful.  Drop the WARN_ON_ONCE()s.

Signed-off-by: Tejun Heo 
Reported-by: 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: explain WARN_ON_ONCE() on negative IDs out-of-range ID

2013-02-28T03:10:21+00:00

Until recently, when an negative ID is specified, idr functions used to
ignore the sign bit and proceeded with the operation with the rest of
bits, which is bizarre and error-prone.  The behavior recently got changed
so that negative IDs are treated as invalid but we're triggering
WARN_ON_ONCE() on negative IDs just in case somebody was depending on the
sign bit being ignored, so that those can be detected and fixed easily.

We only need this for a while.  Explain why WARN_ON_ONCE()s are there and
that they can be removed later.

Signed-off-by: Tejun Heo 
Acked-by: Thomas Gleixner 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: implement lookup hint

2013-02-28T03:10:21+00:00

While idr lookup isn't a particularly heavy operation, it still is too
substantial to use in hot paths without worrying about the performance
implications.  With recent changes, each idr_layer covers 256 slots
which should be enough to cover most use cases with single idr_layer
making lookup hint very attractive.

This patch adds idr->hint which points to the idr_layer which
allocated an ID most recently and the fast path lookup becomes

	if (look up target's prefix matches that of the hinted layer)
		return hint->ary[ID's offset in the leaf layer];

which can be inlined.

idr->hint is set to the leaf node on idr_fill_slot() and cleared from
free_layer().

[andriy.shevchenko@linux.intel.com: always do slow path when hint is uninitialized]
Signed-off-by: Tejun Heo 
Cc: Kirill A. Shutemov 
Cc: Sasha Levin 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: add idr_layer->prefix

2013-02-28T03:10:20+00:00

Add a field which carries the prefix of ID the idr_layer covers.  This
will be used to implement lookup hint.

This patch doesn't make use of the new field and doesn't introduce any
behavior difference.

Signed-off-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: remove length restriction from idr_layer->bitmap

2013-02-28T03:10:20+00:00

Currently, idr->bitmap is declared as an unsigned long which restricts
the number of bits an idr_layer can contain.  All bitops can handle
arbitrary positive integer bit number and there's no reason for this
restriction.

Declare idr_layer->bitmap using DECLARE_BITMAP() instead of a single
unsigned long.

* idr_layer->bitmap is now an array.  '&' dropped from params to
  bitops.

* Replaced "== IDR_FULL" tests with bitmap_full() and removed
  IDR_FULL.

* Replaced find_next_bit() on ~bitmap with find_next_zero_bit().

* Replaced "bitmap = 0" with bitmap_clear().

This patch doesn't (or at least shouldn't) introduce any behavior
changes.

[akpm@linux-foundation.org: checkpatch fixes]
Signed-off-by: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

idr: remove MAX_IDR_MASK and move left MAX_IDR_* into idr.c

2013-02-28T03:10:20+00:00

MAX_IDR_MASK is another weirdness in the idr interface.  As idr covers
whole positive integer range, it's defined as 0x7fffffff or INT_MAX.

Its usage in idr_find(), idr_replace() and idr_remove() is bizarre.
They basically mask off the sign bit and operate on the rest, so if
the caller, by accident, passes in a negative number, the sign bit
will be masked off and the remaining part will be used as if that was
the input, which is worse than crashing.

The constant is visible in idr.h and there are several users in the
kernel.

* drivers/i2c/i2c-core.c:i2c_add_numbered_adapter()

  Basically used to test if adap->nr is a negative number which isn't
  -1 and returns -EINVAL if so.  idr_alloc() already has negative
  @start checking (w/ WARN_ON_ONCE), so this can go away.

* drivers/infiniband/core/cm.c:cm_alloc_id()
  drivers/infiniband/hw/mlx4/cm.c:id_map_alloc()

  Used to wrap cyclic @start.  Can be replaced with max(next, 0).
  Note that this type of cyclic allocation using idr is buggy.  These
  are prone to spurious -ENOSPC failure after the first wraparound.

* fs/super.c:get_anon_bdev()

  The ID allocated from ida is masked off before being tested whether
  it's inside valid range.  ida allocated ID can never be a negative
  number and the masking is unnecessary.

Update idr_*() functions to fail with -EINVAL when negative @id is
specified and update other MAX_IDR_MASK users as described above.

This leaves MAX_IDR_MASK without any user, remove it and relocate
other MAX_IDR_* constants to lib/idr.c.

Signed-off-by: Tejun Heo 
Cc: Jean Delvare 
Cc: Roland Dreier 
Cc: Sean Hefty 
Cc: Hal Rosenstock 
Cc: "Marciniszyn, Mike" 
Cc: Jack Morgenstein 
Cc: Or Gerlitz 
Cc: Al Viro 
Acked-by: Wolfram Sang 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds