linux-kernel - Re: [PATCH] Percpu tag allocator

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]

Message-ID: <20130613193514.GD13970@mtj.dyndns.org>
Date:	Thu, 13 Jun 2013 12:35:14 -0700
From:	Tejun Heo <tj@...nel.org>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Kent Overstreet <koverstreet@...gle.com>,
	linux-kernel@...r.kernel.org, Oleg Nesterov <oleg@...hat.com>,
	Christoph Lameter <cl@...ux-foundation.org>,
	Ingo Molnar <mingo@...hat.com>,
	Andi Kleen <andi@...stfloor.org>, Jens Axboe <axboe@...nel.dk>,
	"Nicholas A. Bellinger" <nab@...ux-iscsi.org>,
	Jeff Layton <jlayton@...hat.com>,
	"J. Bruce Fields" <bfields@...ldses.org>
Subject: Re: [PATCH] Percpu tag allocator

Hello,

On Thu, Jun 13, 2013 at 12:23:39PM -0700, Andrew Morton wrote:
> > The lowest number guarantee makes them different.  Maybe tag
> > allocation can be layered on top as a caching layer, I don't know, but
> > at any rate we need at least two different operation modes.
> 
> Why?  Tag allocation doesn't care about the values - just that they be
> unique.

Hmmm?  Confused.  I was talking about other existing idr users which
need lowest-available allocation.  Tag allocation doesn't care.  ID
allocators do.

> > Maybe we can layer things so that we have percpu layer on top of
> > id[r|a] and, say, mapping id to point is still done by idr, or the
> > percpu tag allocator uses ida for tag chunk allocations, but it's
> > still gonna be something extra on top.
> 
> It's not obvious that explicit per-cpu is needed.  Get an ID from
> ida_get_new_above(), multiply it by 16 and store that in device-local
> storage, along with a 16-bit bitmap.  Blam, 30 lines of code and the
> ida_get_new_above() cost is reduced 16x and it's off the map.

I'm fairly sure it'd have to be per-cpu.  The idr allocation is
reduced 16x but now each of those 16 slots needs to be allocated.  The
problem hasn't gone away and we do need some sort of utility to help
that as drivers tend to resort to things like linear bitmap scan
combined with test_and_set_bit() making one cacheline extremely hot.

> Or perhaps you can think of something smarter, but first you have to
> start thinking of solutions rather than trying to find problems :(

I don't know.  It's pretty clear to me that we at least need two
different operation modes from the two conflicting requirements - one
with strict allocation ordering and the other with very high
scalability.  Please note that I'm not saying they both can't be built
into id[r|a], but we *need* two different operation modes.

Thanks.

-- 
tejun
--
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/