linux-kernel - Re: [PATCH] fix idr_get_new

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <4696F5AD.1050306@gmail.com>
Date:	Fri, 13 Jul 2007 12:46:53 +0900
From:	Tejun Heo <htejun@...il.com>
To:	Andrew Morton <akpm@...ux-foundation.org>
CC:	jim.houston@...r.com,
	Hoang-Nam Nguyen <hnguyen@...ux.vnet.ibm.com>,
	linux-kernel@...r.kernel.org, linuxppc-dev@...abs.org,
	openib-general@...nib.org,
	Stefan Roscher <ossrosch@...ux.vnet.ibm.com>,
	raisch@...ibm.com, Kristian Hoegsberg <krh@...hat.com>
Subject: Re: [PATCH] fix idr_get_new_above id alias bugs

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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/