There were definately some problems in there.  I've made some changes and
tested with a lot of bounds.  I don't have a machine with enough memory to
fill it up (it would take ~16GB on a 64-bit machine), but I use the "above"
code to simulate a lot of situations.

The problems were:

    * IDR_FULL was not the right value
    * idr_get_new_above() was not defined in the headers or documented.
    * idr_alloc() bug-ed if there was a race and not enough memory was
      allocated.  It should have returned NULL.
    * id will overflow when you go past the end.
    * There was a "(id >= (1 << (layers*IDR_BITS)))" comparison, but at
      the top layer it would overflow the id and be zero.
    * The allocation should return ENOSPC for an "above" value with
      nothing above it, but it returned EAGAIN.

I have not tested on 64-bits (as I don't have a 64-bit machine).

I've included the files, a diff from the previous version, and my test
programs.

For the test programs, idr_test <size> will just attempt to allocate 
<size> elements, check them, free them, and check them again.

idr_test2 <size> <incr> will allocate <size> element with <incr> between
them.

idr_test3 just tests some bounds and tries all values with just a few in
the idr.
Signed-off-by: Andrew Morton <akpm@osdl.org>
Signed-off-by: Linus Torvalds <torvalds@osdl.org>