+ fix-spellings-of-slab-allocator-section-in-init-kconfig.patch added to -mm tree

(without SLAB emulation) and fragmentation was not the driving force for replacement. Small Linux 1.x machines frequently had uptimes of 1+ years without fragmenting to death. Instead, it was performance with

Quoted 3 lines

(without SLAB emulation) and fragmentation was not the driving force for replacement. Small Linux 1.x machines frequently had uptimes of 1+ years without fragmenting to death. Instead, it was performance with

8MB for a bit over 3 years.... (1.2.13lmp)

The fragmentation issue I think is overbaked. A lot of the academic work argues that there is pretty much no long term difference between first fit, best fit, and most of the clever algorithms (obviously stupid ones like "take the middle out of the biggest space allocator" do perform worse). For MMUless boxes fragmentation is a big issue but not for normal systems.

Further, the received wisdom that fragmentation of SLAB-like systems is better is not above doubt. Our own issues with dcache fragmentation suggest it's far from perfect.

First, SLOB no longer runs on SMP because SLAB grew some RCU-related hair. So it now effectively has no locks at all!

Third, I don't think it's possible even in theory for a SLAB-like allocator to be as efficient as SLOB simply due to the constraints of putting only objects of the same size on a given page. So consider me skeptical on the density claim.

It is usually better to use SLUB simply because you're more likely to have 1GB of RAM rather than 4MB.

Quoted 2 lines · Matt Mackall

First, SLOB no longer runs on SMP because SLAB grew some RCU-related hair. So it now effectively has no locks at all!

Well it seems that SLOB was not well maintained. RCU has been around for a long time and SLOB has not been updated to cope with it.

Quoted 4 lines

Third, I don't think it's possible even in theory for a SLAB-like allocator to be as efficient as SLOB simply due to the constraints of putting only objects of the same size on a given page. So consider me skeptical on the density claim.

SLUB can put 32 objects sized 128 byte each in a 4k page. Can SLOB do the same?

Quoted 2 lines

It is usually better to use SLUB simply because you're more likely to have 1GB of RAM rather than 4MB.

SLUB should be perfectly fine for that environment provided you adjust the cacheline alignment and switch off SLUB debugging. define L1_CACHE_BYTES to be 4 or so.

Quoted 5 lines · Christoph Lameter

Quoted 2 lines · Matt Mackall

First, SLOB no longer runs on SMP because SLAB grew some RCU-related hair. So it now effectively has no locks at all!

Quoted 2 lines

Well it seems that SLOB was not well maintained. RCU has been around for a long time and SLOB has not been updated to cope with it.

RCU's incursion into SLAB that broke SLOB is relatively new. And it only broke for people using SMP or SPARSEMEM. Intersection with target audience of SLOB: ~0.

Quoted 2 lines

SLUB can put 32 objects sized 128 byte each in a 4k page. Can SLOB do the same?

Yes. It can in fact put 512 8-byte objects in a 4k page. More

importantly, it can put 2 1k objects and 16 128-byte objects on the same page instead of on two pages.

That SLUB cannot do. And I do not believe you. SLOB must have some way to distinguish the objects and their sizes since kfree does not include size information. You can mix slabs of different size on the same page without metadata. Magic?

So how does kfree then know how to free the object? There must be some way where you get the metainformation. What is the point of your 8 byte metadata that keeps getting inserted? That does not consume memory on a page?

SLOB seems to look at the descriptor in the previous blob to figure out how big the being-freed blob is. That's actually kind of clever :-)

Quoted 4 lines

SLOB seems to look at the descriptor in the previous blob to figure out how big the being-freed blob is. That's actually kind of clever :-)

We were assuming that the objects are actually allocated. How does it figure out the previous blobs boundaries without metadata?

I'm just reading over the code to figure out what to type to you, you could read the code too it's not very complicated :-)

Quoted 3 lines

I'm just reading over the code to figure out what to type to you, you could read the code too it's not very complicated :-)

I have read it numerous times and my conclusion is that it uses the descriptors for that purpose. But Matt claims they are not necessary. So I am just trying to figure out how one can get to that conclusion.

From: Christoph Lameter <[email protected]>
Date: Tue, 8 May 2007 18:57:04 -0700 (PDT)

Quoted 3 lines · David Miller

Quoted 4 lines

Quoted 2 lines

I'm just reading over the code to figure out what to type to you, you could read the code too it's not very complicated :-)

I have read it numerous times and my conclusion is that it uses the descriptors for that purpose. But Matt claims they are not necessary. So I am just trying to figure out how one can get to that conclusion.

He is saying the metadata is not necessary for allocated objects. At least that's my take.

Right. You only need to know blob boundaries for free blobs (so you can allocate from or merge to). For allocated blobs, you know the start (which is the address of the memory), and the end (which is the start + the size contained in kmem_cache structure).

From: Christoph Lameter <[email protected]>
Date: Tue, 8 May 2007 18:32:35 -0700 (PDT)

Quoted 3 lines

That SLUB cannot do. And I do not believe you. SLOB must have some way to distinguish the objects and their sizes since kfree does not include size information. You can mix slabs of different size on the same page without metadata. Magic?

So how does kfree then know how to free the object? There must be some way where you get the metainformation. What is the point of your 8 byte metadata that keeps getting inserted? That does not consume memory on a page?

SLOB uses metadata, but that metadata seemingly only needs to be uptodate in freed objects.

SLOB seems to look at the descriptor in the previous blob to figure out how big the being-freed blob is. That's actually kind of clever :-)

BTW, we _really_ should be doing RCU properly in slob, because you technically can't noop RCU on UP (even though the current users may be safe...).

Quoted 3 lines · Nick Piggin

BTW, we _really_ should be doing RCU properly in slob, because you technically can't noop RCU on UP (even though the current users may be safe...).

Thanks. Hugh was pretty convinced it was unneeded:

http://marc.info/?l=linux-mm&m=116413907023393&w=2

And since I didn't care much about the SMP case, I didn't pursue it.

This almost looks reasonable. I think HW_ALIGN | RCU is going to make it break though:

Review

Quoted 3 lines

(quoted diff) +3 -0

+	if (unlikely(c->flags & SLAB_DESTROY_BY_RCU))
+		b += sizeof(struct slob_rcu);
+

That could be dealt with by putting the slob_rcu at the end of the object and having the RCU helper function use ->size to work backward to the actual pointer.

Quoted 4 lines

void kmem_cache_free(struct kmem_cache *c, void *b)

{
	if (c->dtor)
		c->dtor(b, c, 0);

I think if we want RCU to actually work, we want to run ->dtor in __kmem_cache_free?

Quoted 5 lines

(quoted diff) +1 -4

-	if (c->size < PAGE_SIZE)
-		slob_free(b, c->size);
-	else
-		free_pages((unsigned long)b, find_order(c->size));
+	if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {

Review

Quoted 4 lines

(quoted diff) +4 -0

+		struct slob_rcu *slob_rcu;
+		b -= sizeof(struct slob_rcu);
+		slob_rcu = b;
+		slob_rcu->size = c->size;

Which means just store c in the header^Wfooter, then we can retrieve the size and the dtor in the RCU helper.

SLAB_DESTROY_BY_RCU is quite a nice way to mitigate some RCU freeing overheads for small objects, so I'd expect it may see wider use in future. Maybe all those users would be fine too, but it's a bit nasty to have already tricky RCU semantics deviate...

Quoted 2 lines

I think if we want RCU to actually work, we want to run ->dtor in __kmem_cache_free?

Yeah, thinko... thanks.

mm/slob.c +3 -0

+
+	__kmem_cache_free(b, slob_rcu->c);
+}

BTW, we _really_ should be doing RCU properly in slob, because you technically can't noop RCU on UP (even though the current users may be safe...).

Patch attached to do that.

On Wed, 09 May 2007 12:02:29 +1000
Nick Piggin <[email protected]> wrote:

Quoted 5 lines

BTW, we _really_ should be doing RCU properly in slob, because you technically can't noop RCU on UP (even though the current users may be safe...).

Patch attached to do that.

Does it work?

Quoted 11 lines · Andrew Morton

Quoted 5 lines · On Wed, 09 May 2007 12:02:29 +1000 Nick Piggin <[email protected]> wrote:

BTW, we _really_ should be doing RCU properly in slob, because you technically can't noop RCU on UP (even though the current users may be safe...).

Patch attached to do that.

Quoted 1 line

Does it work?

That one booted my desktop (very slowly) but as Matt pointed out, it broke alignment on RCU slabs. The last version I posted should work and has the alignment problem fixed. I can retest and resubmit it to you if you like, I was just waiting on an ack from Matt.

Looks good to me, but haven't had time to actually test it.

Acked-by Matt Mackall <[email protected]>

Review line 303

Quoted 10 lines · Nick Piggin

(quoted diff) +6 -0

@@ -283,6 +295,12 @@
 	if (c) {
 		c->name = name;
 		c->size = size;
+		if (flags & SLAB_DESTROY_BY_RCU) {
+			BUG_ON(c->dtor);
+			/* leave room for rcu footer at the end of object */
+			c->size += sizeof(struct slob_rcu);
+		}
+		c->flags = flags;

might want to put this hunt below

Review line 305

Quoted 2 lines

(quoted diff) +0 -0

 		c->ctor = ctor;
 		c->dtor = dtor;

here; for c->dtor is not initialised quite yet at the BUG_ON site.

Indeed, how's this?

plain text document attachment (slob-add-rcu-fix.patch)
Index: linux-2.6/mm/slob.c
===================================================================

Quoted 6 lines · Matt Mackall

Quoted 5 lines · Christoph Lameter

Quoted 2 lines · Matt Mackall

First, SLOB no longer runs on SMP because SLAB grew some RCU-related hair. So it now effectively has no locks at all!

Quoted 6 lines

Quoted 2 lines

Well it seems that SLOB was not well maintained. RCU has been around for a long time and SLOB has not been updated to cope with it.

RCU's incursion into SLAB that broke SLOB is relatively new. And it only broke for people using SMP or SPARSEMEM. Intersection with target audience of SLOB: ~0.

New meaning in the last 3 years?

Quoted 4 lines

Quoted 2 lines

SLUB can put 32 objects sized 128 byte each in a 4k page. Can SLOB do the same?

Yes. It can in fact put 512 8-byte objects in a 4k page. More

So can SLUB.

Quoted 2 lines

importantly, it can put 2 1k objects and 16 128-byte objects on the same page instead of on two pages.

That SLUB cannot do. And I do not believe you. SLOB must have some way to distinguish the objects and their sizes since kfree does not include size information. You can mix slabs of different size on the same page without metadata. Magic?

So how does kfree then know how to free the object? There must be some way where you get the metainformation. What is the point of your 8 byte metadata that keeps getting inserted? That does not consume memory on a page?

Quoted 3 lines

Quoted 1 line

Yes. It can in fact put 512 8-byte objects in a 4k page. More

So can SLUB.

Not without at least a bit per-object of overhead. So you can either fit 512 objects in 4160 bytes or 504 objects in 4k.

For the kmalloc case, we do have an 8-byte header, which works out to be about 1/8th of the slop that mainline kmalloc over SLAB has on

average due to power of two cache sizes. So in both cases, less overhead than SLAB and different-sized objects can be comingled. SLUB would be awfully hard-pressed to have lower space overhead.

Quoted 6 lines · Matt Mackall

Quoted 3 lines

Quoted 1 line

Yes. It can in fact put 512 8-byte objects in a 4k page. More

So can SLUB.

Not without at least a bit per-object of overhead. So you can either fit 512 objects in 4160 bytes or 504 objects in 4k.

Slub uses a linked list pointer in the page struct which is NULL if all objects are allocated. There is no bit per object overhead.

Quoted 2 lines

For the kmalloc case, we do have an 8-byte header, which works out to be about 1/8th of the slop that mainline kmalloc over SLAB has on

Exactly. That overhead does not exist in SLUB. Thus SLOB is less efficient than SLUB.

Quoted 2 lines

Exactly. That overhead does not exist in SLUB. Thus SLOB is less efficient than SLUB.

What you trade for that is that one page page can only serve one slab.

For small systems, I would not be surprised if that was less space efficient, even just looking at kmalloc caches in isolation. Or do you have numbers to support your conclusion?

Quoted 3 lines · Nick Piggin

For small systems, I would not be surprised if that was less space efficient, even just looking at kmalloc caches in isolation. Or do you have numbers to support your conclusion?

No I do not have any number beyond the efficiency calculations based on whole slabs. We would have to do some experiments to figure out how much space is actually wasted through partial slabs.

If you just do straight allocation on a UP system then there is at maximum one partial slab per slabcache with SLUB.

The situation becomes different with allocation and frees. Then we may have lots of partial slabs that we allocate from.

But the SLOB approach also will have holes to manage. So I do not see how this could be a benefit unless you only have a few precious pages and you need to put multiple object sizes into it. A 4M system still has 1000 pages.

But that 4MB system might not even have 50 pages that you'd want to use for slab.

Quoted 4 lines · Nick Piggin

Quoted 2 lines

Exactly. That overhead does not exist in SLUB. Thus SLOB is less efficient than SLUB.

What you trade for that is that one page page can only serve one slab.

Right.

Quoted 3 lines

For small systems, I would not be surprised if that was less space efficient, even just looking at kmalloc caches in isolation. Or do you have numbers to support your conclusion?

No I do not have any number beyond the efficiency calculations based on whole slabs. We would have to do some experiments to figure out how much space is actually wasted through partial slabs.

The situation becomes different with allocation and frees. Then we may have lots of partial slabs that we allocate from. But the SLOB approach also will have holes to manage. So I do not see how this could be a benefit unless you only have a few precious pages and you need to put multiple object sizes into it. A 4M system still has 1000 pages.

Quoted 6 lines · Matt Mackall

Quoted 3 lines

Quoted 1 line

Yes. It can in fact put 512 8-byte objects in a 4k page. More

So can SLUB.

Not without at least a bit per-object of overhead. So you can either fit 512 objects in 4160 bytes or 504 objects in 4k.

Slub uses a linked list pointer in the page struct which is NULL if all objects are allocated. There is no bit per object overhead.

Quoted 2 lines

For the kmalloc case, we do have an 8-byte header, which works out to be about 1/8th of the slop that mainline kmalloc over SLAB has on

Exactly. That overhead does not exist in SLUB. Thus SLOB is less efficient than SLUB.

Quoted 2 lines

Exactly. That overhead does not exist in SLUB. Thus SLOB is less efficient than SLUB.

What size object does kmalloc(80) return? In SLAB, the answer is 128 bytes with 48 bytes of slack space. In SLOB, the answer is 88 for 8 bytes of slack space. Looks like SLUB is in the same camp as SLAB here:

SLOB's kmalloc overhead is 8 bytes, always. That's 1/8th the average SLAB kmalloc overhead.