linux-kernel - Re: [RFC PATCH] greatly reduce SLOB external fragmentation

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]

Date:	Thu, 10 Jan 2008 08:13:03 -0800 (PST)
From:	Linus Torvalds <torvalds@...ux-foundation.org>
To:	Pekka J Enberg <penberg@...helsinki.fi>
cc:	Matt Mackall <mpm@...enic.com>,
	Christoph Lameter <clameter@....com>,
	Ingo Molnar <mingo@...e.hu>, Hugh Dickins <hugh@...itas.com>,
	Andi Kleen <andi@...stfloor.org>,
	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: [RFC PATCH] greatly reduce SLOB external fragmentation

On Thu, 10 Jan 2008, Pekka J Enberg wrote:
> 
> We probably don't have the same version of GCC which perhaps affects 
> memory layout (struct sizes) and thus allocation patterns?

No, struct sizes will not change with compiler versions - that would 
create binary incompatibilities for libraries etc.

So apart from the kernel itself working around some old gcc bugs by making 
spinlocks have different size depending on the compiler version, sizes of 
structures should be the same (as long as the configuration is the same, 
of course).

However, a greedy first-fit allocator will be *very* sensitive to 
allocation pattern differences, so timing will probably make a big 
difference. In contrast, SLUB and SLAB both use fixed sizes per allocation 
queue, which makes them almost totally impervious to any allocation 
pattern from different allocation sizes (they still end up caring about 
the pattern *within* one size, but those tend to be much stabler).

There really is a reason why traditional heaps with first-fit are almost 
never used for any real loads.

(I'm not a fan of slabs per se - I think all the constructor/destructor 
crap is just that: total crap - but the size/type binning is a big deal, 
and I think SLOB was naïve to think a pure first-fit makes any sense. Now 
you guys are size-binning by just two or three bins, and it seems to make 
a difference for some loads, but compared to SLUB/SLAB it's a total hack).

I would suggest that if you guys are really serious about memory use, try 
to do a size-based heap thing, and do best-fit in that heap. Or just some 
really simple size-based binning, eg

	if (size > 2*PAGE_SIZE)
		goto page_allocator;
	bin = lookup_bin[(size+31) >> 5];

or whatever. Because first-fit is *known* to be bad.

At try to change it to address-ordered first-fit or something (which is 
much more complex than just plain LIFO, but hey, that's life).

I haven't checked much, but I *think* SLOB is just basic first-fit 
(perhaps the "next-fit" variation?) Next-fit is known to be EVEN WORSE 
than the simple first-fit when it comes to fragmentation (so no, Knuth was 
not always right - let's face it, much of Knuth is simply outdated).

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