linux-kernel - Re: [PATCH v1 1/6] idr: introduce idr_alloc

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 27 Mar 2013 13:21:41 -0400
From:	Jeff Layton <jlayton@...hat.com>
To:	Tejun Heo <tj@...nel.org>
Cc:	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v1 1/6] idr: introduce idr_alloc_cyclic

On Wed, 27 Mar 2013 10:01:35 -0700
Tejun Heo <tj@...nel.org> wrote:

> Hello,
> 
> On Wed, Mar 27, 2013 at 12:48:04PM -0400, Jeff Layton wrote:
> > > > + * Note that people using cyclic allocation to avoid premature reuse of an
> > > > + * already-used ID may be in for a nasty surprise after idr->cur wraps. The
> > > > + * IDR code is designed to avoid unnecessary allocations. If there is space
> > > > + * in an existing layer that holds high IDs then it will return one of those
> > > > + * instead of allocating a new layer at the bottom of the range.
> > > 
> > > Ooh, does it?  Where?
> > > 
> > 
> > That's what I gathered from looking at idr_get_empty_slot. I could be
> > wrong here, so please correct me if I am. The IDR internals are really
> > hard to follow...
> 
> Amen, it's horrible.
> 
> > In any case, it looks like it only tries to allocate a new layer if:
> > 
> > idr->top is empty
> > 
> > ...or...
> > 
> > while (id > idr_max(layers)) {
> > ...
> > }
> >
> > After the wrap, idr->top won't be empty if we have at least one layer
> > still in use. We start with id = starting_id, which after wrap will be
> > much lower than idr_max() at that point (right?).
> > 
> > So we'll skip the while loop and fall right into sub_alloc and will
> > quite possibly end up allocating a slot out of the current layer, which
> > is almost certainly not near the bottom of the range.
> > 
> > Again, I'm far from sure of my understanding of the internals here, so
> > please do correct me if that's not right...
> 
> So, there are two paths which do layer allocation.
> idr_get_empty_slot() does bottom -> top expansion.  ie. it grows the
> tree if the current position can't be covered by the current tree.
> Note that the tree can always point to zero.  That is, the first slot
> of the top layer always includes zero.
> 
> The other part - building tree top -> bottom - happens in sub_alloc()
> which traverses the tree downwards for the current position and
> creates new idr_layer if it doesn't exist.
> 
> So, after wrap, the tree is already tall enough so
> idr_get_empty_slot() will just call into sub_alloc() which will build
> the tree downwards.  AFAICS, it does guarantee lowest-packing.
> 

Ok, that's good to know, and I'll remove the comment for the v2 patch.
I'm glad to be wrong in this case :)

-- 
Jeff Layton <jlayton@...hat.com>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/