This patch increases the speed of the SLUB fastpath by

improving the per cpu allocator and makes it usable for SLUB.
Currently allocpercpu manages arrays of pointer to per cpu objects.

This means that is has to allocate the arrays and then populate them

as needed with objects. Although these objects are called per cpu

objects they cannot be handled in the same way as per cpu objects

by adding the per cpu offset of the respective cpu.
The patch here changes that. We create a small memory pool in the

percpu area and allocate from there if alloc per cpu is called.

As a result we do not need the per cpu pointer arrays for each

object. This reduces memory usage and also the cache foot print

of allocpercpu users. Also the per cpu objects for a single processor

are tightly packed next to each other decreasing cache footprint

even further and making it possible to access multiple objects

in the same cacheline.
SLUB has the same mechanism implemented. After fixing up the

alloccpu stuff we throw the SLUB method out and use the new

allocpercpu handling. Then we optimize allocpercpu addressing

by adding a new function
	this_cpu_ptr()
that allows the determination of the per cpu pointer for the

current processor in an more efficient way on many platforms.
This increases the speed of SLUB (and likely other kernel subsystems

that benefit from the allocpercpu enhancements):
       SLAB    SLUB    SLUB+   SLUB-o	SLUB-a

   8    96      86      45      44      38	3 *

  16    84      92      49      48      43	2 *

  32    84      106     61      59      53	+++

  64    102     129     82      88      75	++

 128    147     226     188     181     176	-

 256    200     248     207     285     204	=

 512    300     301     260     209     250	+

1024    416     440     398     264     391	++

2048    720     542     530     390     511	+++

4096    1254    342     342     336     376	3 *
alloc/free test

      SLAB    SLUB    SLUB+   SLUB-o	SLUB-a

      137-146 151     68-72   68-74	56-...
[ message continues ]

All callers to __d_path pass the dentry and vfsmount of a struct

path to __d_path. Pass the struct path directly, instead.
Signed-off-by: Andreas Gruenbacher <agruen@suse.de>

Signed-off-by: Jan Blunck <jblunck@suse.de>

---

 fs/dcache.c |   12 +++++-------

 1 file changed, 5 insertions(+), 7 deletions(-)
Index: b/fs/dcache.c

===================================================================

--- a/fs/dcache.c

+++ b/fs/dcache.c

@@ -1778,9 +1778,8 @@ shouldnt_be_hashed:

  *

  * "buflen" should be positive. Caller holds the dcache_lock.

  */

-static char * __d_path( struct dentry *dentry, struct vfsmount *vfsmnt,

-			struct dentry *root, struct vfsmount *rootmnt,

-			char *buffer, int buflen)

+static char * __d_path(struct dentry *dentry, struct vfsmount *vfsmnt,

+		       struct path *root, char *buffer, int buflen)

 {

 	char * end = buffer+buflen;

 	char * retval;

@@ -1805,7 +1804,7 @@ static char * __d_path( struct dentry *d

 	for (;;) {

 		struct dentry * parent;
-		if (dentry == root && vfsmnt == rootmnt)

+		if (dentry == root->dentry && vfsmnt == root->mnt)

 			break;

 		if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {

 			/* Global root? */

@@ -1868,7 +1867,7 @@ char * d_path(struct dentry *dentry, str

 	path_get(&current->fs->root);

 	read_unlock(&current->fs->lock);

 	spin_lock(&dcache_lock);

-	res = __d_path(dentry, vfsmnt, root.dentry, root.mnt, buf, buflen);

+	res = __d_path(dentry, vfsmnt, &root, buf, buflen);

 	spin_unlock(&dcache_lock);

 	path_put(&root);

 	return res;

@@ -1936,8 +1935,7 @@ asmlinkage long sys_getcwd(char __user *

 		unsigned long len;

 		char * cwd;
-		cwd = __d_path(pwd.dentry, pwd.mnt, root.dentry, root.mnt,

-			       page, PAGE_SIZE);

+		cwd = __d_path(pwd.dentry, pwd.mnt, &root, page, PAGE_SIZE);

 		spin_unlock(&dcache_lock);
 		error = PTR_ERR(cwd);
-- 
-

Really sounds good Christoph, not only for SLUB, so I guess the 32k limit is

not enough because many things will use per_cpu if only per_cpu was reasonably

fast (ie not so many dereferences)
I think this question already came in the past and Linus already answered it,

but I again ask it. What about VM games with modern cpus (64 bits arches)
Say we reserve on x86_64 a really huge (2^32 bytes) area, and change VM layout

so that each cpu maps its own per_cpu area on this area, so that the local

per_cpu data sits in the same virtual address on each cpu. Then we dont need a

segment prefix nor adding a 'per_cpu offset'. No need to write special asm

functions to read/write/increment a per_cpu data and gcc could use normal

rules for optimizations.
We only would need adding "per_cpu offset" to get data for a given cpu.
-

That is basically what IA64 is doing but it not usable because you would

have addresses that mean different things on different cpus. List head

for example require back pointers. If you put a listhead into such a per

cpu area then you may corrupt another cpus per cpu area.
-

From: Christoph Lameter <clameter@sgi.com>
Indeed, but as I pointed out in another mail it actually works if you

set some rules:
1) List insert and delete is only allowed on local CPU lists.
2) List traversal is allowed on remote CPU lists.
I bet we could get all of the per-cpu users to abide by this

rule if we wanted to.
The remaining issue with accessing per-cpu areas at multiple virtual

addresses is D-cache aliasing.

-

But that is not an issue for physicallly mapped caches.
-

From: Christoph Lameter <clameter@sgi.com>
Right but I'd like to use this on sparc64 which has L1 D-cache

aliasing on some chips :-)

-

Hmmm... re my message I just send. Then we have to return the memory with

the virtual address not with the physical address on sparc. May result in

zones with holes though.
-

From: Eric Dumazet <dada1@cosmosbay.com>
This is a mechanism used partially on IA64 already.
I think you have to be very careful, and you can only use this per-cpu

fixed virtual address area in extremely limited cases.
The reason is, I think the address matters, consider list heads, for

example.
So you couldn't do:
	list_add(&obj->list, &per_cpu_ptr(list_head));
and use that per-cpu fixed virtual address.
IA64 seems to use it universally for every __get_cpu_var()

access, so maybe it works out somehow :-)))
I guess if list modifications by remote cpus are disallowed, it would

work (list traversal works because using the fixed virtual address as

the list head sentinal is OK), but that is an extremely fragile

assumption to base the entire mechanism upon.

-

IA64 does not do that. It addds the local cpu offset
#define __get_cpu_var(var) (*RELOC_HIDE(&per_cpu__##var,

__ia64_per_cpu_var(local_per_cpu_offset)))

#define __raw_get_cpu_var(var) (*RELOC_HIDE(&per_cpu__##var,

__ia64_per_cpu_var(local_per_cpu_offset)))
-

From: Christoph Lameter <clameter@sgi.com>
Oh I see, it's the offset itself which is accessed at the fixed

virtual address slot.

-

Are these patches against -mm or mainline?
I get a lot of rejects starting with patch 6 against

mainline and I really wanted to test them out on sparc64.
Thanks.

-

Hmmm... They are against the current slab performance head (which is in mm

but it has not been released yet ;-).
Do 
git pull git://git.kernel.org/pub/scm/linux/kernel/git/christoph/slab.git

performance
and then you should be able to apply these patches.
-

From: Christoph Lameter <clameter@sgi.com>
Thanks a lot Chrisoph.

-

Others may have the same issue.
git pull git://git.kernel.org/pub/scm/linux/kernel/git/christoph/slab.git allocpercpu
should get you the whole thing.
-

From: Christoph Lameter <clameter@sgi.com>
This patch fixes build failures with DEBUG_VM disabled.
diff --git a/include/linux/percpu.h b/include/linux/percpu.h

index 4b167c0..d414703 100644

--- a/include/linux/percpu.h

+++ b/include/linux/percpu.h

@@ -36,7 +36,7 @@

 #ifdef CONFIG_DEBUG_VM

 #define __percpu_disguise(pdata) ((void *)~(unsigned long)(pdata))

 #else

-#define __percpu_disguide(pdata) ((void *)(pdata))

+#define __percpu_disguise(pdata) ((void *)(pdata))

 #endif
 /*

-

> This patch fixes build failures with DEBUG_VM disabled.
Well there is more there. Last minute mods sigh. With DEBUG_VM you likely

need this patch.
---

 include/linux/percpu.h |    4 ++--

 1 file changed, 2 insertions(+), 2 deletions(-)
Index: linux-2.6/include/linux/percpu.h

===================================================================

--- linux-2.6.orig/include/linux/percpu.h	2007-10-31 17:48:38.020499686 -0700

+++ linux-2.6/include/linux/percpu.h	2007-10-31 17:51:01.423372247 -0700

@@ -36,7 +36,7 @@

 #ifdef CONFIG_DEBUG_VM

 #define __percpu_disguise(pdata) ((void *)~(unsigned long)(pdata))

 #else

-#define __percpu_disguide(pdata) ((void *)(pdata))

+#define __percpu_disguise(pdata) ((void *)(pdata))

 #endif
 /*

@@ -53,7 +53,7 @@
 #define this_cpu_ptr(ptr)           			\

 ({							\

-	void *p = ptr;					\

+	void *p = __percpu_disguise(ptr);		\

     	(__typeof__(ptr))(p + this_cpu_offset());	\

 })
-

From: Christoph Lameter <clameter@sgi.com>
Without DEBUG_VM I get a loop of crashes shortly after SSHD

is started, I'll try to track it down.

-

Check how much per cpu memory is in use by
cat /proc/vmstat
currently we have a 32k limit there.
-

From: Christoph Lameter <clameter@sgi.com>
It crashes when SSHD starts, the serial console GETTY hasn't

started up yet so I can't even log in to run those commands

Christoph.
All I can do now is bisect and then try to figure out what about the

guilty change might cause the problem.
This is on a 64-cpu sparc64 box, and fast cmpxchg local is not set, so

maybe it's one of the locking changes.

-

Reverting the 7th patch should avoid using the sparc register that caches

the per cpu area offset? (I though so, does it?)

-

From: Christoph Lameter <clameter@sgi.com>
Yes, that's right, %g5 holds the local cpu's per-cpu offset.

-

Hmmmm... Got this to run on an ia64 big iron. One problem is the sizing of

the pool. Somehow this needs to be dynamic.
Apply this fix on top of the others.
---

 include/asm-ia64/page.h   |    2 +-

 include/asm-ia64/percpu.h |    9 ++++++---

 mm/allocpercpu.c          |   12 ++++++++++--

 3 files changed, 17 insertions(+), 6 deletions(-)
Index: linux-2.6/mm/allocpercpu.c

===================================================================

--- linux-2.6.orig/mm/allocpercpu.c	2007-10-31 20:53:16.565486654 -0700

+++ linux-2.6/mm/allocpercpu.c	2007-10-31 21:00:27.553486484 -0700

@@ -28,7 +28,12 @@

 /*

  * Maximum allowed per cpu data per cpu

  */

+#ifdef CONFIG_NUMA

+#define PER_CPU_ALLOC_SIZE (32768 + MAX_NUMNODES * 512)

+#else

 #define PER_CPU_ALLOC_SIZE 32768

+#endif

+
 #define UNIT_SIZE sizeof(unsigned long long)

 #define UNITS_PER_CPU (PER_CPU_ALLOC_SIZE / UNIT_SIZE)

@@ -37,7 +42,7 @@ enum unit_type { FREE, END, USED };
 static u8 cpu_alloc_map[UNITS_PER_CPU] = { 1, };

 static DEFINE_SPINLOCK(cpu_alloc_map_lock);

-static DEFINE_PER_CPU(int, cpu_area)[UNITS_PER_CPU];

+static DEFINE_PER_CPU(unsigned long long, cpu_area)[UNITS_PER_CPU];
 #define CPU_DATA_OFFSET ((unsigned long)&per_cpu__cpu_area)
@@ -97,8 +102,11 @@ static void *cpu_alloc(unsigned long siz

 		while (start < UNITS_PER_CPU &&

 				cpu_alloc_map[start] != FREE)

 			start++;

-		if (start == UNITS_PER_CPU)

+		if (start == UNITS_PER_CPU) {

+			spin_unlock(&cpu_alloc_map_lock);

+			printk(KERN_CRIT "Dynamic per cpu memory exhausted\n");

 			return NULL;

+		}
 		end = start + 1;

 		while (end < UNITS_PER_CPU && end - start < units &&

Index: linux-2.6/include/asm-ia64/page.h

===================================================================

--- linux-2.6.orig/include/asm-ia64/page.h	2007-10-31 20:53:16.573486483 -0700

+++ linux-2.6/include/asm-ia64/page.h	2007-10-31 20:56:19.372870091 -0700

@@ -44,7 +44,7 @@

 #define PAGE_MASK		(~(PAGE_SIZE - 1))

 #...
[ message continues ]

From: Christoph Lameter <clameter@sgi.com>
This hunk helped the sparc64 looping OOPS I was getting, but cpus hang

in some other fashion soon afterwards.
I'll try to debug this some more later, I've dumped enough time into

this already :-)

-

From: David Miller <davem@davemloft.net>
And if I bump PER_CPU_ALLOC_SIZE up to 128K it seems to mostly work.
You'll definitely need to make this work dynamically somehow.

-

Obviously. Any ideas how?
I can probably calculate the size based on the number of online nodes when

the per cpu areas are setup. But the setup is done before we even parse

command line arguments. That would still mean a fixed size after bootup.
In order to make it truly dynamic we would have to virtually map the area.

vmap? But that reduces performance.
-

From: Christoph Lameter <clameter@sgi.com>
But it would still be faster than the double-indirection we do now,

right?

-

I think I have an idea how to do this. Its a bit x86_64 specific but here

it goes.
We define a virtual area of NR_CPUS * 2M areas that are each mapped by a

PMD. That means we have a fixed virtual address for each cpus per cpu

area. 
First cpu is at PER_CPU_START

Second cpu is at PER_CPU_START + 2M
So the per cpu area for cpu n is easily calculated using
PER_CPU_START + cpu << 19
without any lookups.
On bootup we allocate the 2M pages.
After boot is complete we allow the reduction of the size of the per cpu

areas . Lets say we only need 128k per cpu. Then the remaining pages will

be returned to the page allocator.
We create some sysfs thingy were one can see the current reserves of per

cpu storage. If one wants to reduce memory then one can write something to

that to return the remainder of the memory.
-

From: Christoph Lameter <clameter@sgi.com>
You don't know how much you will need.  I exhausted the limit on

sparc64 very late in the boot process when the last few userland

services were starting up.
And if I subsequently bring up 100,000 IP tunnels, it will exhaust the

per-cpu allocation area.
You have to make it fully dynamic, there is no way around it.

-

Well you would be able to specify how much will remain. If not it will 
Na. Some reasonable upper limit needs to be set. If we set that to say

32Megabytes and do the virtual mapping then we can just populate the first

2M and only allocate the remainder if we need it. Then we need to rely on

Mel's defrag stuff though defrag memory if we need it.
-

well, if we move last_rx to a percpu var, we need  8 bytes of percpu space per 
If a 2MB page is not available, could we revert using 4KB pages ? (like

vmalloc stuff), paying an extra runtime overhead of course.
-

Hmmm... On x86_64 we could take 8 terabyte virtual space (bit order 43)
With the worst case scenario of 16k of cpus (bit order 16) we are looking

at 43-16 = 27 ~ 128MB per cpu. Each percpu can at max be mapped by 64 pmd

entries. 4k support is actually max for projected hw. So we'd get

to 512M. 
On IA64 we could take half of the vmemmap area which is 45 bits. So

we could get up to 512MB (with 16k pages, 64k pages can get us even

further) assuming we can at some point run 16 processors per node (4k is

the current max which would put the limit on the per cpu area >1GB).
Lets say you have a system with 64 cpus and an area of 128M of per cpu

storage. Then we are using 8GB of total memory for per cpu storage. The

128M allows us to store f.e.  16 M of word size counters.
With SLAB and the current allocpercpu you would need the following for

16M counters:
16M*32*64 (minimum alloc size of SLAB is 32 byte and we alloc via

		kmalloc) for the data.
16M*64*8 for the pointer arrays. 16M allocpercpu areas for 64 processors

		and a pointer size of 8 bytes.
So you would need to use 40G in current systems. The new scheme

would only need 8GB for the same amount of counters.
So I think its unreasonable to assume that currently systems exist that

can use more than 128m of allocpercpu space (assuming 64 cpus).
---

 include/asm-x86/pgtable_64.h |    4 ++++

 1 file changed, 4 insertions(+)
Index: linux-2.6/include/asm-x86/pgtable_64.h

===================================================================

--- linux-2.6.orig/include/asm-x86/pgtable_64.h	2007-11-01 18:15:52.282577904 -0700

+++ linux-2.6/include/asm-x86/pgtable_64.h	2007-11-01 18:18:02.886979040 -0700

@@ -138,10 +138,14 @@ static inline pte_t ptep_get_and_clear_f

 #define VMALLOC_START    _AC(0xffffc20000000000, UL)

 #define VMALLOC_END      _AC(0xffffe1ffffffffff, UL)

 #define VMEMMAP_START	 _AC(0xffffe20000000000, UL)

+#define PERCPU_START	 _AC(0xfffff20000000000, UL)

+#define PERCPU_END	 _AC(0xfffffa00000...
[ message continues ]

Sure. Its going to be like vmemmap. There will be limited imposed though

by the amount of virtual space available. Basically the dynamic per cpu

area can be at maximum
available_virtual_space / NR_CPUS
-

From: Christoph Lameter <clameter@sgi.com>
Each IP compression tunnel instance does an alloc_percpu().
Since you're the one who wants to change the semantics and guarentees

of this interface, perhaps it might help if you did some greps around

the tree to see how alloc_percpu() is actually used.  That's what

I did when I started running into trouble with your patches.
You cannot put limits of the amount of alloc_percpu() memory available

to clients, please let's proceed with that basic understanding in

mind.  We're wasting a ton of time discussing this fundamental issue.

-

Actually all IPComp tunnels share one set of objects which are

allocated per-cpu.  So only the first tunnel would do that.
In fact that was precisely the reason why per-cpu is used in

IPComp as otherwise we can just allocate normal memory.
Cheers,

--

Visit Openswan at http://www.openswan.org/

Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>

Home Page: http://gondor.apana.org.au/~herbert/

PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

-

From: Herbert Xu <herbert@gondor.apana.org.au>
Hmmm... indeed.  Thanks for clearing this up.

-

Ahh so the need to be able to expand per cpu memory storage on demand

is not as critical as we thought.
-

Yes, but still desirable for future optimizations.
For example, I do think using a per cpu memory storage on net_device refcnt &

last_rx could give us some speedups.
-

We do want to keep a very tight handle on bloat in per-cpu

allocations.  By definition the total allocation is multiplied

by the number of cpus.  Only ia64 has outrageous numbers of

cpus in a single system image today ... but the trend in

multi-core chips looks to have a Moore's law arc to it, so

everyone is going to be looking at lots of cpus before long.
-Tony

-

I dont think this is a problem. Cpus numbers and ram size are related, even if

Moore didnt predicted it;
Nobody wants to ship/build a 4096 cpus machine with 256 MB of ram inside.

Or call it a GPU and dont expect it to run linux :)
99,9% of linux machines running on earth have less than 8 cpus and less than

1000 ethernet/network devices.
In case we increase the number of cpus on a machine, the limiting factor is

the fact that cpus have to continually exchange on memory bus those highly

touched cache lines that contain refcounters or stats.
-

From: Eric Dumazet <dada1@cosmosbay.com>
I totally agree with everything Eric is saying here.

-

Note that there was a new patchset posted (titled cpu alloc v1) that=20

provides on demand extension of the cpu areas.
See http://marc.info/?l=3Dlinux-kernel&m=3D119438261304093&w=3D2

Thank you Christoph. I was traveling last week so I missed that.
This new patchset looks very interesting, you did a fantastic job !
-

From: Eric Dumazet <dada1@cosmosbay.com>
Yes I like it too.  It's in my backlog of things to test on

sparc64.

-

This fancy new BDI stuff also lives off percpu_counter/alloc_percpu().
That means that for example each NFS mount also consumes a number of

words - not quite sure from the top of my head how many, might be in the

order of 24 bytes or something.
I once before started looking at this, because the current

alloc_percpu() can have some false sharing - not that I have machines

that are overly bothered by that. I like the idea of a strict percpu

region, however do be aware of the users.
-

Yes there are numerous uses. I even can increase page allocator 
Well I wonder if I should introduce it not as a replacement but as an

alternative to allocpercpu? We can then gradually switch over. The

existing API does not allow the specification of gfp_masks or alignements.
-

I've thought about suggesting that very thing. However, I think we need

to have a clear view of where we're going with that so that we don't end

up with two per cpu allocators because some users could not be converted

over or some such.
-

At least in my tests so far show that it can be a full replacement but

then I have only tested on x86_64 and Ia64. Its likely much easier to go

for the full replacement rather than in steps.
If we want dynamically sized virtually mapped per cpu areas then we may

have issues on 32 bit platforms and with !MMU. So I would think that a

fallback to a statically sized version may be needed. On the other hand

!MMU and 32 bit do not support a large number of processors. So we may be

able to get away on 32 bit with a small virtual memory area.
-

There is no point in making absolute demands like "no limits". There are

always limits to everything. 
A new implementation avoids the need to allocate per cpu arrays and also

avoids the 32 bytes per object times cpus that are mostly wasted for small

allocations today. So its going to potentially allow more per cpu objects

that available today.
A reasonable implementation for 64 bit is likely going to depend on

reserving some virtual memory space for the per cpu mappings so that they

can be dynamically grown up to what the reserved virtual space allows.
F.e. If we reserve 256G of virtual space and support a maximum of 16k cpus

then there is a limit on the per cpu space available of 16MB.

-

From: Christoph Lameter <clameter@sgi.com>
Now that I understand your implementation better, yes this

sounds just fine.

-

From: Christoph Lameter <clameter@sgi.com>
Christoph, as Rusty found out years ago when he first wrote this code,

you cannot put hard limits on the alloc_percpu() allocations.
They can be done by anyone, any module, and since there was no limit

before you cannot reasonably add one now.
As just one of many examples, several networking devices use

alloc_percpu() for each instance they bring up.  This alone can

request arbitrary amounts of per-cpu data.
Therefore, you'll need to do your optimization without imposing any

size limits.

-

And if I add the address of a percpu variable then I get to the variable

for this cpu right?
-

From: Christoph Lameter <clameter@sgi.com>
Right.
I bisected the crash down to:
	[PATCH] newallocpercpu

-