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

From: Andrew Morton
Date: Tue Feb 12 2013 - 16:23:45 EST

On Tue, 12 Feb 2013 09:10:49 -0800
Tejun Heo <tj@xxxxxxxxxx> wrote:

> Hey, Andrew.
> On Mon, Feb 11, 2013 at 03:39:55PM -0800, Andrew Morton wrote:
> > 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?
> For most cases, probably not. IDR_BITS being 5 and 6 on 32 and 64bit
> respectively, the only misbehaving bit is bit 30, so unless ID goes
> over 1G, which should be close to non-existent if the IDs are being
> allocated from zero, it shouldn't be a problem; however, we do have
> users where IDR is used to allocate cyclic IDs. They maintain and
> progress the last allocated ID so that IDs don't get recycled without
> wrapping around. I have no idea whether any of them would be
> allocating IDs fast enough to go over 1G limit in any reasonable
> amount of time or whether there are such ID allocations which can be
> exploited from userland without root priviliedges, in which case it
> would probably directly lead to oops.
> So, to sum up, at least I can't rule out the issue happening or being
> exploited in the wild with older kernels. It isn't too likely to
> happen naturally but if there's a userland exploitable cyclic
> alloction, going over 1G wouldn't be too difficult.

OK. The changelog has the cc:stable tag so I'll let you and Greg duke
it out ;)

> > 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?
> Right now, it's just a messy test module with ad-hoc loops and manual
> alloc/frees with a lot of printks sprinkled everywhere, so I'm afraid
> it wouldn't be suitable for any form of automated test. It sure would
> be great to have a testing harness for this tho.

I slapped together a userspace test harness for lib/radix-tree.c many
years ago. It's at Whenever
anyone does any significant radix-tree work, they download that, update
it to test their new stuff then send me an rtth diff.

I suppose we could move that code into the kernel tree and use/maintain
it there. That would create a framework and precedent for new things
like the idr test harness. iirc the test harness uses the kernel's
radix-tree.c and radix-tree.h unaltered - it provides a pile of hacky
header files sufficient to make the kernel code compilable into the
userspace test app.

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