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

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

[Matt Mackall]

On Tue, May 08, 2007 at 04:02:20PM -0700, akpm@linux-foundation.org wrote:
>  	bool "SLOB (Simple Allocator)"
>  	help
>  	   SLOB replaces the SLAB allocator with a drastically simpler
>  	   allocator.  SLOB is more space efficient that SLAB but does not
> -	   scale well (single lock for all operations) and is more susceptible
> -	   to fragmentation. SLOB it is a great choice to reduce
> -	   memory usage and code size for embedded systems.
> +	   scale well (single lock for all operations) and is also highly
> +	   susceptible to fragmentation. SLUB can accomplish a higher object
> +	   density. It is usually better to use SLUB instead of SLOB.

This isn't accurate.

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

Second, I think the fragmentation issues are exaggerated. Before SLAB
was introduced, Linux's kmalloc was the moral equivalent of SLOB
(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
large amounts of RAM - the old kmalloc (and SLOB) have performance
proportional to memory size.

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.

-- 
Mathematics is the supreme nostalgia of our time.

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

[Alan Cox]

> (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.

Alan

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

[Matt Mackall]

On Wed, May 09, 2007 at 01:32:20AM +0100, Alan Cox wrote:
> > (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.

-- 
Mathematics is the supreme nostalgia of our time.

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

[Christoph Lameter]

On Tue, 8 May 2007, Matt Mackall wrote:

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

I guess that you have not seen the slab defrag code for SLUB then.

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

[Christoph Lameter]

On Tue, 8 May 2007, Matt Mackall wrote:

> 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.
 
> 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?
 
> 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.

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

[Matt Mackall]

On Tue, May 08, 2007 at 05:51:27PM -0700, Christoph Lameter wrote:
> On Tue, 8 May 2007, Matt Mackall wrote:
> 
> > 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.

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.
  
> > 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?

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.

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

Perhaps. We'll need to look at some numbers.

-- 
Mathematics is the supreme nostalgia of our time.

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

[Christoph Lameter]

On Tue, 8 May 2007, Matt Mackall wrote:

> On Tue, May 08, 2007 at 05:51:27PM -0700, Christoph Lameter wrote:
> > On Tue, 8 May 2007, Matt Mackall wrote:
> > 
> > > 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.
> 
> 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?

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

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

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

[David Miller]

From: Christoph Lameter <clameter@sgi.com>
Date: Tue, 8 May 2007 18:32:35 -0700 (PDT)

> 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
:-)

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

[Christoph Lameter]

On Tue, 8 May 2007, David Miller wrote:

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

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

[David Miller]

From: Christoph Lameter <clameter@sgi.com>
Date: Tue, 8 May 2007 18:53:28 -0700 (PDT)

> On Tue, 8 May 2007, David Miller wrote:
> 
> > 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?

The page is filled entirely with descriptors in the not-in-use regions
of the page aparently.  So "freed_object - 1" will always give you
a descriptor.

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 :-)

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

[Christoph Lameter]

On Tue, 8 May 2007, David Miller wrote:

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

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

[Nick Piggin]

[-- Attachment #1: Type: text/plain, Size: 1207 bytes --]

David Miller wrote:
> From: Christoph Lameter <clameter@sgi.com>
> Date: Tue, 8 May 2007 18:32:35 -0700 (PDT)
> 
> 
>>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
> :-)

You know how big the being-freed blob is because the kmem cache structure
contains that. The free metadata is just needed for free area management.

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.

-- 
SUSE Labs, Novell Inc.

[-- Attachment #2: slob-add-rcu.patch --]
[-- Type: text/plain, Size: 2956 bytes --]

Index: linux-2.6/mm/slob.c
===================================================================
--- linux-2.6.orig/mm/slob.c	2007-04-12 14:35:11.000000000 +1000
+++ linux-2.6/mm/slob.c	2007-05-09 09:22:33.000000000 +1000
@@ -35,6 +35,7 @@
 #include <linux/init.h>
 #include <linux/module.h>
 #include <linux/timer.h>
+#include <linux/rcupdate.h>
 
 struct slob_block {
 	int units;
@@ -53,6 +54,11 @@
 };
 typedef struct bigblock bigblock_t;
 
+struct slob_rcu {
+	struct rcu_head rcu_head;
+	int size;
+};
+
 static slob_t arena = { .next = &arena, .units = 1 };
 static slob_t *slobfree = &arena;
 static bigblock_t *bigblocks;
@@ -242,6 +248,7 @@
 
 struct kmem_cache {
 	unsigned int size, align;
+	unsigned long flags;
 	const char *name;
 	void (*ctor)(void *, struct kmem_cache *, unsigned long);
 	void (*dtor)(void *, struct kmem_cache *, unsigned long);
@@ -259,6 +266,11 @@
 	if (c) {
 		c->name = name;
 		c->size = size;
+		if (flags & SLAB_DESTROY_BY_RCU) {
+			/* leave room for rcu header at the start of object */
+			c->size += sizeof(struct slob_rcu);
+		}
+		c->flags = flags;
 		c->ctor = ctor;
 		c->dtor = dtor;
 		/* ignore alignment unless it's forced */
@@ -281,11 +293,14 @@
 {
 	void *b;
 
-	if (c->size < PAGE_SIZE)
+	if (c->size < PAGE_SIZE) {
 		b = slob_alloc(c->size, flags, c->align);
-	else
+	} else
 		b = (void *)__get_free_pages(flags, find_order(c->size));
 
+	if (unlikely(c->flags & SLAB_DESTROY_BY_RCU))
+		b += sizeof(struct slob_rcu);
+
 	if (c->ctor)
 		c->ctor(b, c, SLAB_CTOR_CONSTRUCTOR);
 
@@ -303,15 +318,34 @@
 }
 EXPORT_SYMBOL(kmem_cache_zalloc);
 
+static void __kmem_cache_free(void *b, int size)
+{
+	if (size < PAGE_SIZE)
+		slob_free(b, size);
+	else
+		free_pages((unsigned long)b, find_order(size));
+}
+
+static void kmem_rcu_free(struct rcu_head *head)
+{
+	struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
+
+	__kmem_cache_free(head, slob_rcu->size);
+}
+
 void kmem_cache_free(struct kmem_cache *c, void *b)
 {
 	if (c->dtor)
 		c->dtor(b, c, 0);
 
-	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)) {
+		struct slob_rcu *slob_rcu;
+		b -= sizeof(struct slob_rcu);
+		slob_rcu = b;
+		slob_rcu->size = c->size;
+		call_rcu(&slob_rcu->rcu_head, kmem_rcu_free);
+	} else
+		__kmem_cache_free(b, c->size);
 }
 EXPORT_SYMBOL(kmem_cache_free);
 
Index: linux-2.6/init/Kconfig
===================================================================
--- linux-2.6.orig/init/Kconfig	2007-04-12 14:35:11.000000000 +1000
+++ linux-2.6/init/Kconfig	2007-05-09 09:11:14.000000000 +1000
@@ -476,7 +476,7 @@
 
 config SLAB
 	default y
-	bool "Use full SLAB allocator" if (EMBEDDED && !SMP && !SPARSEMEM)
+	bool "Use full SLAB allocator" if (EMBEDDED && !SPARSEMEM)
 	help
 	  Disabling this replaces the advanced SLAB allocator and
 	  kmalloc support with the drastically simpler SLOB allocator.

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

[David Miller]

From: Christoph Lameter <clameter@sgi.com>
Date: Tue, 8 May 2007 18:57:04 -0700 (PDT)

> On Tue, 8 May 2007, David Miller wrote:
> 
> > 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.

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

[Nick Piggin]

David Miller wrote:
> From: Christoph Lameter <clameter@sgi.com>
> Date: Tue, 8 May 2007 18:57:04 -0700 (PDT)
> 
> 
>>On Tue, 8 May 2007, David Miller wrote:
>>
>>
>>>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).

-- 
SUSE Labs, Novell Inc.

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

[Matt Mackall]

On Tue, May 08, 2007 at 06:32:35PM -0700, Christoph Lameter wrote:
> On Tue, 8 May 2007, Matt Mackall wrote:
> 
> > On Tue, May 08, 2007 at 05:51:27PM -0700, Christoph Lameter wrote:
> > > On Tue, 8 May 2007, Matt Mackall wrote:
> > > 
> > > > 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.
> > 
> > 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?

Whatever. I've already told you why it's a dontcare. I'm basically
done with this thread until some actual memory usage numbers are
injected into it.

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

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.

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

I've already explained this to you once tonight and there's only 8k of
code to read. It's also explained in the comment at the top:

 * SLAB is emulated on top of SLOB by simply calling constructors and
 * destructors for every SLAB allocation. Objects are returned with
 * the 8-byte alignment unless the SLAB_HWCACHE_ALIGN flag is
 * set, in which case the low-level allocator will fragment blocks to
 * create the proper alignment. Again, objects of page-size or greater
 * are allocated by calling __get_free_pages. As SLAB objects know
 * their size, no separate size bookkeeping is necessary and there is
 * essentially no allocation space overhead.

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.

Compare:

void *kmem_cache_alloc(struct kmem_cache *c, gfp_t flags)
{
...
                b = slob_alloc(c->size, flags, c->align);
...
}

void kmem_cache_free(struct kmem_cache *c, void *b)
{
...
                slob_free(b, c->size);
...
}

vs.

void *__kmalloc(size_t size, gfp_t gfp)
{
...
                m = slob_alloc(size + SLOB_UNIT, gfp, 0);
                return m ? (void *)(m + 1) : 0;
...
}

void kfree(const void *block)
{
...
        slob_free((slob_t *)block - 1, 0);
...
}

-- 
Mathematics is the supreme nostalgia of our time.

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

[Christoph Lameter]

On Wed, 9 May 2007, Nick Piggin wrote:

> 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).

For kmalloc caches you will not have the object size on kfree. In that 
case the slob_t structure is needed before the object.

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

[Christoph Lameter]

On Tue, 8 May 2007, Matt Mackall wrote:

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

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

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

Its simple and easy to do and it was done in SLUB.

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

[Nick Piggin]

Christoph Lameter wrote:
> On Tue, 8 May 2007, Matt Mackall wrote:
> 
> 
>>>>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.
> 
> 
>>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.

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?

-- 
SUSE Labs, Novell Inc.

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

[Matt Mackall]

On Wed, May 09, 2007 at 12:02:29PM +1000, Nick Piggin 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...).

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:

> +	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.

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

> -	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)) {
> +		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.

We might as well add slab_is_available and make the damn thing work on
sparsemem again too.

-- 
Mathematics is the supreme nostalgia of our time.

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

[Christoph Lameter]

On Wed, 9 May 2007, Nick Piggin wrote:

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

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

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

[Nick Piggin]

Christoph Lameter wrote:
> On Wed, 9 May 2007, Nick Piggin wrote:

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

Yeah, but even then I think the SLUB approach is a very nice one for a
general purpose system. Don't get me wrong, SLOB definitely is not good
for that :)


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

Right, and it takes a long long time to do anything on my 4G system ;)

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

-- 
SUSE Labs, Novell Inc.

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

[Christoph Lameter]

On Wed, 9 May 2007, Nick Piggin wrote:

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

The problem here is that you trade off more objects (SLUB) against more 
flexibility (SLOB). We need some experiments with 4M systems to see how 
this works out. It may be better to be able to allocate more objects. I 
estimate that we will have a need for about 30 active slabs (note the 
low number comes about because SLUB will merge similar slabs together 
into one) on such a system. Most of those can have two pages. So you will 
likely still be better off with SLUB than SLOB.

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

[Matt Mackall]

On Tue, May 08, 2007 at 07:24:07PM -0700, Christoph Lameter wrote:
> On Tue, 8 May 2007, Matt Mackall wrote:
> 
> > > > 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.

Ahh, I'd forgotten about that feature.

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

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:

+/*
+ * We keep the general caches in an array of slab caches that are used for
+ * 2^x bytes of allocations.
+ */
+extern struct kmem_cache kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
...
+	if (size <=        128) return 7;

As I pointed out in our private thread, according to these
measurements:

http://lwn.net/Articles/124374/

total bytes allocated: 47118848   
slack bytes allocated:  8717262
number of allocs:        132796

...the average kmalloc allocation with SLAB is 355 bytes with an
average slack of 66 bytes. As SLUB uses the same kmalloc cache size
strategy, I expect the same there.

SLOB's kmalloc overhead is 8 bytes, always. That's 1/8th the average
SLAB kmalloc overhead.
 
-- 
Mathematics is the supreme nostalgia of our time.

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

[Nick Piggin]

[-- Attachment #1: Type: text/plain, Size: 1886 bytes --]

Matt Mackall wrote:
> On Wed, May 09, 2007 at 12:02:29PM +1000, Nick Piggin 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...).
> 
> 
> 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.

Sure the anonvma cache is OK on UP, but I'm just saying that in the
general case, you cannot noop RCU on UP systems.

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


> This almost looks reasonable. I think HW_ALIGN | RCU is going to make
> it break though:
> 
> 
>>+	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.

Sure, OK.


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

Yeah, thinko... thanks.


>>-	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)) {
>>+		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.

OK, updated patch (about-to-be-tested) attached.

-- 
SUSE Labs, Novell Inc.

[-- Attachment #2: slob-add-rcu.patch --]
[-- Type: text/plain, Size: 2821 bytes --]

Index: linux-2.6/mm/slob.c
===================================================================
--- linux-2.6.orig/mm/slob.c	2007-04-12 14:35:11.000000000 +1000
+++ linux-2.6/mm/slob.c	2007-05-09 11:01:09.000000000 +1000
@@ -35,6 +35,7 @@
 #include <linux/init.h>
 #include <linux/module.h>
 #include <linux/timer.h>
+#include <linux/rcupdate.h>
 
 struct slob_block {
 	int units;
@@ -53,6 +54,11 @@
 };
 typedef struct bigblock bigblock_t;
 
+struct slob_rcu {
+	struct rcu_head rcu_head;
+	struct kmem_cache *c;
+};
+
 static slob_t arena = { .next = &arena, .units = 1 };
 static slob_t *slobfree = &arena;
 static bigblock_t *bigblocks;
@@ -242,6 +248,7 @@
 
 struct kmem_cache {
 	unsigned int size, align;
+	unsigned long flags;
 	const char *name;
 	void (*ctor)(void *, struct kmem_cache *, unsigned long);
 	void (*dtor)(void *, struct kmem_cache *, unsigned long);
@@ -259,6 +266,11 @@
 	if (c) {
 		c->name = name;
 		c->size = size;
+		if (flags & SLAB_DESTROY_BY_RCU) {
+			/* leave room for rcu footer at the end of object */
+			c->size += sizeof(struct slob_rcu);
+		}
+		c->flags = flags;
 		c->ctor = ctor;
 		c->dtor = dtor;
 		/* ignore alignment unless it's forced */
@@ -281,9 +293,9 @@
 {
 	void *b;
 
-	if (c->size < PAGE_SIZE)
+	if (c->size < PAGE_SIZE) {
 		b = slob_alloc(c->size, flags, c->align);
-	else
+	} else
 		b = (void *)__get_free_pages(flags, find_order(c->size));
 
 	if (c->ctor)
@@ -303,7 +315,7 @@
 }
 EXPORT_SYMBOL(kmem_cache_zalloc);
 
-void kmem_cache_free(struct kmem_cache *c, void *b)
+static void __kmem_cache_free(struct kmem_cache *c, void *b)
 {
 	if (c->dtor)
 		c->dtor(b, c, 0);
@@ -313,6 +325,25 @@
 	else
 		free_pages((unsigned long)b, find_order(c->size));
 }
+
+static void kmem_rcu_free(struct rcu_head *head)
+{
+	struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
+	void *b = (void *)slob_rcu - slob_rcu->c->size;
+
+	__kmem_cache_free(b, slob_rcu->c);
+}
+
+void kmem_cache_free(struct kmem_cache *c, void *b)
+{
+	if (unlikely(c->flags & SLAB_DESTROY_BY_RCU)) {
+		struct slob_rcu *slob_rcu;
+		slob_rcu = b + c->size;;
+		slob_rcu->c = c;
+		call_rcu(&slob_rcu->rcu_head, kmem_rcu_free);
+	} else
+		__kmem_cache_free(b, c);
+}
 EXPORT_SYMBOL(kmem_cache_free);
 
 unsigned int kmem_cache_size(struct kmem_cache *c)
Index: linux-2.6/init/Kconfig
===================================================================
--- linux-2.6.orig/init/Kconfig	2007-04-12 14:35:11.000000000 +1000
+++ linux-2.6/init/Kconfig	2007-05-09 09:11:14.000000000 +1000
@@ -476,7 +476,7 @@
 
 config SLAB
 	default y
-	bool "Use full SLAB allocator" if (EMBEDDED && !SMP && !SPARSEMEM)
+	bool "Use full SLAB allocator" if (EMBEDDED && !SPARSEMEM)
 	help
 	  Disabling this replaces the advanced SLAB allocator and
 	  kmalloc support with the drastically simpler SLOB allocator.

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

[Christoph Lameter]

On Tue, 8 May 2007, Matt Mackall wrote:

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

There is a 96 sized general slab. So it would go up to that size. But you 
can create a 80 byte slab of course. And that may cost minimal overhead 
since 80 byte slabs may be merged. If one already exist then you get it 
for free.

> +/*
> + * We keep the general caches in an array of slab caches that are used for
> + * 2^x bytes of allocations.
> + */
> +extern struct kmem_cache kmalloc_caches[KMALLOC_SHIFT_HIGH + 1];
> ..
> +	if (size <=        128) return 7;

96 please. You skipped the first part.

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

SLUB can generate an 80 byte slab with minimal overhead if you wanted. But 
yes I agree the flexbility there is an advantage if you have objects of 
various sizes.

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

[Matt Mackall]

On Tue, May 08, 2007 at 07:57:37PM -0700, Christoph Lameter wrote:
> On Wed, 9 May 2007, Nick Piggin wrote:
> 
> > > 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.
> 
> > 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 expectation would be (PAGE_SIZE + (PAGE_SIZE % size))/2 on average
per cache.
 
> 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.

A 4M system has approximately zero pages free once you've actually got
stuff running in userspace. The marginal utility of each page is very
high.

-- 
Mathematics is the supreme nostalgia of our time.

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

[Christoph Lameter]

On Wed, 9 May 2007, Nick Piggin wrote:

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

Signal handling is using RCU too right?

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

According to SLAB code: RCU cannot have a dtor.

kmem_cache_create()

     if (flags & SLAB_DESTROY_BY_RCU)
                BUG_ON(dtor);

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

[Nick Piggin]

Nick Piggin wrote:

> +static void kmem_rcu_free(struct rcu_head *head)
> +{
> +	struct slob_rcu *slob_rcu = (struct slob_rcu *)head;
> +	void *b = (void *)slob_rcu - slob_rcu->c->size;

No, I forgot that c->size includes the size of struct slob_rcu here.
Will send updated patch which is tested and includes SOB.

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

-- 
SUSE Labs, Novell Inc.

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

[Andrew Morton]

On Wed, 09 May 2007 12:02:29 +1000
Nick Piggin <nickpiggin@yahoo.com.au> 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.

Does it work?

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

[Nick Piggin]

Andrew Morton wrote:
> On Wed, 09 May 2007 12:02:29 +1000
> Nick Piggin <nickpiggin@yahoo.com.au> 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.
> 
> 
> 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.

-- 
SUSE Labs, Novell Inc.

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

[Matt Mackall]

On Thu, May 10, 2007 at 11:00:17AM +1000, Nick Piggin wrote:
> Andrew Morton wrote:
> >On Wed, 09 May 2007 12:02:29 +1000
> >Nick Piggin <nickpiggin@yahoo.com.au> 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.
> >
> >
> >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 <mpm@selenic.com>

-- 
Mathematics is the supreme nostalgia of our time.