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