linux-kernel - Re: [PATCH] idr: Document ida tree sections

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, 14 Aug 2013 17:04:27 -0700
From:	Kent Overstreet <kmo@...erainc.com>
To:	Tejun Heo <tj@...nel.org>
Cc:	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	Stephen Rothwell <sfr@...b.auug.org.au>,
	Fengguang Wu <fengguang.wu@...el.com>
Subject: Re: [PATCH] idr: Document ida tree sections

On Tue, Aug 13, 2013 at 07:59:47PM -0400, Tejun Heo wrote:
> Hey, Kent.
> 
> On Tue, Aug 13, 2013 at 04:51:33PM -0700, Kent Overstreet wrote:
> > Should probably be almost as good, yeah... in theory, but the space
> > efficiency still isn't going to be as good, and it'll probably be more
> > code... and at this point I really just don't want to futz with it more.
> > At this point unless there's something really wrong with this code I
> > just want to move onto something else :P
> 
> I think it probably would be okay in most cases but don't feel
> confident about acking as it's making trade-offs which are unnecessary
> and unusual.  So, ummm, I really don't know.  Maybe it's better enough
> than what we have now but at the same time if you want to reimplement
> the whole thing you should be persistent / reliable enough to see it
> through this time around too, right?

I was just telling you how I felt :) Regardless of that, IMO what I've
got now is superior to any radix tree based approach for what ida/idr
are supposed to do. I could of course be wrong, but I'm not convinced...

Re: caching the last allocation with a radix tree based implementation.
I thought about that more last night, I don't think that would be viable
for using ida underneath the percpu ida allocator.

Reason being percpu ida has to heavily optimize for the case where
almost all of the id space is allocated, and after awhile the id space
is going to be fragmented - so caching the last allocated id is going to
be useless.

This is also why I implemented the ganged allocation bit, to amortize
the bitmap tree traversal. So we'd lose out on that going back to a
radix tree, or have to reimplement it (and it'll be slower due to
pointer chasing).

Which is all not the end of the world, but it means that if we punt on
the ida/idr rewrites for now or change our minds about them - we _do_
have quite a bit of stuff waiting on the percpu ida allocator, so for
that to go in separate I'll have to change it back to using a stack of
integers for the global freelist - which does use significantly more
memory.
--
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/