[PATCH] SLAB - have index_of bug at compile time.

[PATCH] SLAB - have index_of bug at compile time.

[Steven Rostedt]

Hi,  after all the talk over SLAB and SLOBs I decided to make myself
useful, and I'm trying very hard to understand the Linux implementation
of SLAB.  So I'm going through ever line of code and examining it
thoroughly, when I find something that could be improved, either
performance wise (highly doubtful), clean up wise, documentation wise,
enhancement wise, or just have a question, I'll make myself known.

This email is enhancement wise. ;)

I noticed the code for index_of is a creative way of finding the cache
index using the compiler to optimize to a single hard coded number.  But
I couldn't help noticing that it uses two methods to let you know that
someone used it wrong.  One is at compile time (the correct way), and
the other is at run time (not good).

OK, this isn't really an enhancement since the code already works. But
this change can help those later who do real enhancements to SLAB.

-- Steve

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

Index: linux-2.6.15-rc6/mm/slab.c
===================================================================
--- linux-2.6.15-rc6.orig/mm/slab.c	2005-12-20 16:47:05.000000000 -0500
+++ linux-2.6.15-rc6/mm/slab.c	2005-12-21 10:20:03.000000000 -0500
@@ -315,6 +315,8 @@
  */
 static __always_inline int index_of(const size_t size)
 {
+	extern void __bad_size(void);
+
 	if (__builtin_constant_p(size)) {
 		int i = 0;
 
@@ -325,12 +327,9 @@
 		i++;
 #include "linux/kmalloc_sizes.h"
 #undef CACHE
-		{
-			extern void __bad_size(void);
-			__bad_size();
-		}
+		__bad_size();
 	} else
-		BUG();
+		__bad_size();
 	return 0;
 }
 

Re: [PATCH] SLAB - have index_of bug at compile time.

[Manfred Spraul]

Steven wrote:

>So I'm going through ever line of code and examining it
>thoroughly, when I find something that could be improved
>
Try to find a kfree implementation that doesn't need virt_to_page(). 
This is a big restriction of the current implementation: It's in the hot 
path, but the operation is only fast on simple systems, not on numa 
systems without a big memory map.
And it makes it impossible to use vmalloc memory as the basis for slabs, 
or to use slab for io memory.

--
    Manfred

Re: [PATCH] SLAB - have index_of bug at compile time.

[Steven Rostedt]

On Mon, 26 Dec 2005, Manfred Spraul wrote:

> Steven wrote:
>
> >So I'm going through ever line of code and examining it
> >thoroughly, when I find something that could be improved
> >
> Try to find a kfree implementation that doesn't need virt_to_page().
> This is a big restriction of the current implementation: It's in the hot
> path, but the operation is only fast on simple systems, not on numa
> systems without a big memory map.
> And it makes it impossible to use vmalloc memory as the basis for slabs,
> or to use slab for io memory.
>

Unfortunately, that virt_to_page helps make kmalloc and kfree more
efficient.  Since it allows the use of the mem_map pages that map to the
used memory to be used for storing information about the slab.

So removing virt_to_page means you need to store the information relative
to the memory that is mapped.  Thus you need to allocate more than is
needed.

Your question refers to only kfree, which would not really be that
difficult to remove the virt_to_page, since that would just need the extra
memory _for each allocation_.  But then you mention vmalloc and numa,
where it is the generic use of virt_to_page through out slab.c that is the
issue.  I counted 14 direct uses of virt_to_page in slab.c (2.6.15-rc5).
Now you need to find a way to store the information of the off slab
descriptors and for slabs that are more than one page.

Changing the use of virt_to_page would probably hurt those that can use
it, and the changes would not be accepted because of that.  Unless you can
keep the same speed and memory efficiency of those "simple systems".

Now, maybe NUMA and vmalloc might be a good reason to start a new
allocation system along side of slab?

-- Steve

Re: [PATCH] SLAB - have index_of bug at compile time.

[Pekka Enberg]

Hi Steven,

On 12/26/05, Steven Rostedt <rostedt@goodmis.org> wrote:
> Now, maybe NUMA and vmalloc might be a good reason to start a new
> allocation system along side of slab?

A better approach would probably be to introduce a vmem layer similar
to what Solaris has to solve I/O memory and vmalloc issue. What NUMA
issue are you referring to btw? I don't see any problem with the
current design (in fact, I stole it for my magazine allocator too).
It's just that the current implementation is bit hard to understand.

                         Pekka

Re: [PATCH] SLAB - have index_of bug at compile time.

[Manfred Spraul]

Pekka Enberg wrote:

>Hi Steven,
>
>On 12/26/05, Steven Rostedt <rostedt@goodmis.org> wrote:
>  
>
>>Now, maybe NUMA and vmalloc might be a good reason to start a new
>>allocation system along side of slab?
>>    
>>
>
>A better approach would probably be to introduce a vmem layer similar
>to what Solaris has to solve I/O memory and vmalloc issue. What NUMA
>issue are you referring to btw? I don't see any problem with the
>current design (in fact, I stole it for my magazine allocator too).
>It's just that the current implementation is bit hard to understand.
>
>  
>
This is virt_to_page() on i386: the object address is in %esi
     lea    0x40000000(%esi),%eax
     mov    0x0,%edx [0x0 is actually mem_map]
     shr    $0xc,%eax
     shl    $0x5,%eax
Just read the mem_map pointer and a few calculations.
And now retrieve the cachep pointer:
    mov    0x18(%eax,%edx,1),%edx

With NUMA on i386 (GENERIC_ARCH)
    lea    0x40000000(%edi),%eax
    mov    %eax,%ebx
    shr    $0x1c,%eax
    movsbl 0x0(%eax),%eax [ 0x0 is physnode_map]
    shr    $0xc,%ebx
    mov    0x0(,%eax,4),%ecx [0x0 is node_data]
    mov    %ebx,%eax
    mov    0xaa0(%ecx),%edx
    sub    %edx,%eax
    mov    0xa98(%ecx),%edx
    shl    $0x5,%eax
4 memory accesses.
    mov    0x18(%eax,%edx,1),%ebp

--
    Manfred