linux-kernel - Re: [patch] SLQB slab 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-Id: <200902031242.56206.nickpiggin@yahoo.com.au>
Date:	Tue, 3 Feb 2009 12:42:54 +1100
From:	Nick Piggin <nickpiggin@...oo.com.au>
To:	Christoph Lameter <cl@...ux-foundation.org>
Cc:	Nick Piggin <npiggin@...e.de>,
	Pekka Enberg <penberg@...helsinki.fi>,
	"Zhang, Yanmin" <yanmin_zhang@...ux.intel.com>,
	Lin Ming <ming.m.lin@...el.com>, linux-mm@...ck.org,
	linux-kernel@...r.kernel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	Linus Torvalds <torvalds@...ux-foundation.org>
Subject: Re: [patch] SLQB slab allocator

On Tuesday 27 January 2009 04:46:49 Christoph Lameter wrote:
> On Sat, 24 Jan 2009, Nick Piggin wrote:
> > > > SLUB can directly free an object to any slab page. "Queuing" on free
> > > > via the per cpu slab is only possible if the object came from that
> > > > per cpu slab. This is typically only the case for objects that were
> > > > recently allocated.
> > >
> > > Ah yes ok that's right. But then you don't get LIFO allocation
> > > behaviour for those cases.
> >
> > And actually really this all just stems from conceptually in fact you
> > _do_ switch to a different queue (from the one being allocated from)
> > to free the object if it is on a different page. Because you have a
> > set of queues (a queue per-page). So freeing to a different queue is
> > where you lose LIFO property.
>
> Yes you basically go for locality instead of LIFO if the free does not hit
> the per cpu slab. If the object is not in the per cpu slab then it is
> likely that it had a long lifetime and thus LIFOness does not matter
> too much. It is likely that many objects from that slab are going to be
> freed at the same time. So the first free warms up the "queue" of the page
> you are freeing to.

I don't really understand this. It is easy to lose cache hotness information.
Free two objects from different pages. The first one to be freed is likely
to be cache hot, but it will not be allocated again (any time soon).


> This is an increasingly important feature since memory chips prefer
> allocations next to each other. Same page accesses are faster
> in recent memory subsystems than random accesses across memory.

DRAM chips? How about avoiding the problem and keeping the objects in cache
so you don't have to go to RAM.


> LIFO used
> to be better but we are increasingly getting into locality of access being
> very important for access.

Locality of access includes temporal locality. Which is very important. Which
SLUB doesn't do as well at.


> Especially with the NUMA characteristics of the
> existing AMD and upcoming Nehalem processors this will become much more
> important.

Can you demonstrate that LIFO used to be better but no longer is? What
NUMA characteristics are you talking about?

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