Re: [PATCH 1/6] idr: fix top layer handling

From: Andrew Morton
Date: Mon Feb 11 2013 - 18:40:08 EST

On Fri, 8 Feb 2013 13:00:50 -0800
Tejun Heo <tj@xxxxxxxxxx> 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 <tj@xxxxxxxxxx>
> Cc: stable@xxxxxxxxxxxxxxx

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

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 majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at