[PATCH] fix idr_get_new_above id alias bugs

[Tejun Heo]

Hello,

Andrew Morton wrote:
>> Hoang-Nam Nguyen reported a bug in idr_get_new_above() 
>> which occurred with a starting id value like 0x3ffffffc.
>> His test module easily reproduced the problem.  Thanks.
>>
>> The test revealed the following bugs:
>>
>> 1. Relying on shift operations which have undefined results
>>    e.g.: 1 << n where n > word size.  On i386 an integer shift
>>    only uses the low 5 bits of the shift count.
>>
>> 2. An off by one error which prevented the top most layer
>>    of the radix tree from being allocated.  This meant that
>>    sub_alloc() would allocate an entry in the existing portion
>>    of the radix tree which aliased the requested address.  When
>>    it tried to allocate id 0x40000000, it might use the slot 
>>    belonging to id 0.
>>
>> 3. There was also a failure in the code which walked back up
>>    the tree if an allocation failed.  The normal case is to
>>    descend the tree checking the starting id value against the
>>    bitmap at each level.  If the bit is set, we know that the
>>    entire sub-tree is full and we can short cut the search.
>>    We may still descend to the lowest level and find that the
>>    portion of the id space we want is full.  In this case we
>>    need to walk back up the tree and continue the search.
>>    The existing code just returned to the previous level and
>>    continued.  This resulted in an attempt to allocate an id
>>    above 0x3ffffffc using the slot for id 0x3ffffc00 instead of
>>    0x40000000 which it then claimed to have allocated.  The same
>>    problem occurs with 0x3ff as the requested id value if it
>>    is already in use.

The third one sounds like the bug I fixed.  With it fixed, I verified
idr works correctly at least in the lower range of allocation by running
it parallelly with simple bitmap allocator but haven't tested higher
range like 0x3ffffffc.

-- 
tejun