On Fri, 8 Feb 2013 13:00:50 -0800 Tejun Heo <t...@kernel.org> wrote: > Most functions in idr fail to deal with the high bits when the idr > tree grows to the maximum height. > > * idr_get_empty_slot() stops growing idr tree once the depth reaches > MAX_IDR_LEVEL - 1, which is one depth shallower than necessary to > cover the whole range. The function doesn't even notice that it > didn't grow the tree enough and ends up allocating the wrong ID > given sufficiently high @starting_id. > > For example, on 64 bit, if the starting id is 0x7fffff01, > idr_get_empty_slot() will grow the tree 5 layer deep, which only > covers the 30 bits and then proceed to allocate as if the bit 30 > wasn't specified. It ends up allocating 0x3fffff01 without the bit > 30 but still returns 0x7fffff01. > > * __idr_remove_all() will not remove anything if the tree is fully > grown. > > * idr_find() can't find anything if the tree is fully grown. > > * idr_for_each() and idr_get_next() can't iterate anything if the tree > is fully grown. > > Fix it by introducing idr_max() which returns the maximum possible ID > given the depth of tree and replacing the id limit checks in all > affected places. > > As the idr_layer pointer array pa[] needs to be 1 larger than the > maximum depth, enlarge pa[] arrays by one. > > While this plugs the discovered issues, the whole code base is > horrible and in desparate need of rewrite. It's fragile like hell, > difficult to read and maintain, and plain ugly. > > Signed-off-by: Tejun Heo <t...@kernel.org> > Cc: sta...@vger.kernel.org
This doesn't apply happily to 3.7, so Greg will be needing a redone version when the time arrives. But does it really need backporting? Is anyone likely to hit this in practice? Also, I assume you have some sort of IDR test harness over there. Is it something we can get into the tree in some fashion to help with ongoing maintenance? -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
