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 [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
