Git next: Second stage of cpu_alloc patches

Git next: Second stage of cpu_alloc patches

[Christoph Lameter]

The second stage of the cpu_alloc patchset can be pulled from

kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2

Stage 2 includes the conversion of the page allocator, vm statistics 
and slub allocator to the use of the cpu allocator and it includes the 
core of the atomic vs. interrupt cpu ops.

commit c9112914d224fbead980438877212c0f003c624e
Author: Christoph Lameter <clameter@sgi.com>
Date:   Tue Nov 6 11:33:51 2007 -0800

     cpu alloc: page allocator conversion

     Use the new cpu_alloc functionality to avoid per cpu arrays in struct zone.
     This drastically reduces the size of struct zone for systems with a large
     amounts of processors and allows placement of critical variables of struct
     zone in one cacheline even on very large systems.

     Another effect is that the pagesets of one processor are placed near one
     another. If multiple pagesets from different zones fit into one cacheline
     then additional cacheline fetches can be avoided on the hot paths when
     allocating memory from multiple zones.

     Surprisingly this clears up much of the painful NUMA bringup. Bootstrap
     becomes simpler if we use the same scheme for UP, SMP, NUMA. #ifdefs are
     reduced and we can drop the zone_pcp macro.

     Hotplug handling is also simplified since cpu alloc can bring up and
     shut down cpu areas for a specific cpu as a whole. So there is no need to
     allocate or free individual pagesets.

     Signed-off-by: Christoph Lameter <clameter@sgi.com>

commit 8a6784bb0da03ea87bab414e9f8de51dcd399490
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:39 2008 -0600

     x86_64: Support for cpu ops

     Support fast cpu ops in x86_64 by providing a series of functions that
     generate the proper instructions.

     Define CONFIG_HAVE_CPU_OPS so that core code
     can exploit the availability of fast per cpu operations.

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

commit e872b7e4dc22f746df8435f1b4b7208b56a68fd6
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:39 2008 -0600

     VM statistics: Use CPU ops

     The use of CPU ops here avoids the offset calculations that we used to have
     to do with per cpu operations. The result of this patch is that event counters
     are coded with a single instruction the following way:

     	incq   %gs:offset(%rip)

     Without these patches this was:

     	mov    %gs:0x8,%rdx
     	mov    %eax,0x38(%rsp)
     	mov    xxx(%rip),%eax
     	mov    %eax,0x48(%rsp)
     	mov    varoffset,%rax
     	incq   0x110(%rax,%rdx,1)

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

commit a81123720c0786d2847f4eaa145da61348f369ab
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:38 2008 -0600

     cpu ops: Core piece for generic atomic per cpu operations

     Currently the per cpu subsystem is not able to use the atomic capabilities
     that are provided by many of the available processors.

     This patch adds new functionality that allows the optimizing of per cpu
     variable handling. In particular it provides a simple way to exploit
     atomic operations in order to avoid having to disable interrupts or
     performing address calculation to access per cpu data.

     F.e. Using our current methods we may do

     	unsigned long flags;
     	struct stat_struct *p;

     	local_irq_save(flags);
     	/* Calculate address of per processor area */
     	p = CPU_PTR(stat, smp_processor_id());
     	p->counter++;
     	local_irq_restore(flags);

     The segment can be replaced by a single atomic CPU operation:

     	CPU_INC(stat->counter);

     Most processors have instructions to perform the increment using a
     a single atomic instruction. Processors may have segment registers,
     global registers or per cpu mappings of per cpu areas that can be used
     to generate atomic instructions that combine the following in a single
     operation:

     1. Adding of an offset / register to a base address
     2. Read modify write operation on the address calculated by
        the instruction.

     If 1+2 are combined in an instruction then the instruction is atomic
     vs interrupts. This means that percpu atomic operations do not need
     to disable interrupts to increments counters etc.

     The existing methods in use in the kernel cannot utilize the power of
     these atomic instructions. local_t is not really addressing the issue
     since the offset calculation performed before the atomic operation. The
     operation is therefor not atomic. Disabling interrupt or preemption is
     required in order to use local_t.

     local_t is also very specific to the x86 processor. The solution here can
     utilize other methods than just those provided by the x86 instruction set.



     On x86 the above CPU_INC translated into a single instruction:

     	inc %%gs:(&stat->counter)

     This instruction is interrupt safe since it can either be completed
     or not. Both adding of the offset and the read modify write are combined
     in one instruction.

     The determination of the correct per cpu area for the current processor
     does not require access to smp_processor_id() (expensive...). The gs
     register is used to provide a processor specific offset to the respective
     per cpu area where the per cpu variable resides.

     Note that the counter offset into the struct was added *before* the segment
     selector was added. This is necessary to avoid calculations.  In the past
     we first determine the address of the stats structure on the respective
     processor and then added the field offset. However, the offset may as
     well be added earlier. The adding of the per cpu offset (here through the
     gs register) must be done by the instruction used for atomic per cpu
     access.



     If "stat" was declared via DECLARE_PER_CPU then this patchset is capable of
     convincing the linker to provide the proper base address. In that case
     no calculations are necessary.

     Should the stat structure be reachable via a register then the address
     calculation capabilities can be leveraged to avoid calculations.

     On IA64 we can get the same combination of operations in a single instruction
     by using the virtual address that always maps to the local per cpu area:

     	fetchadd &stat->counter + (VCPU_BASE - __per_cpu_start)

     The access is forced into the per cpu address reachable via the virtualized
     address. IA64 allows the embedding of an offset into the instruction. So the
     fetchadd can perform both the relocation of the pointer into the per cpu
     area as well as the atomic read modify write cycle.



     In order to be able to exploit the atomicity of these instructions we
     introduce a series of new functions that take either:

     1. A per cpu pointer as returned by cpu_alloc() or CPU_ALLOC().

     2. A per cpu variable address as returned by per_cpu_var(<percpuvarname>).

     CPU_READ()
     CPU_WRITE()
     CPU_INC
     CPU_DEC
     CPU_ADD
     CPU_SUB
     CPU_XCHG
     CPU_CMPXCHG

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

commit bf49f4db6d6582675dbcb38189fc943e2dc8ba8d
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:38 2008 -0600

     cpu alloc: Remove slub fields

     Remove the fields in kmem_cache_cpu that were used to cache data from
     kmem_cache when they were in different cachelines. The cacheline that holds
     the per cpu array pointer now also holds these values. We can cut down the
     struct kmem_cache_cpu size to almost half.

     The get_freepointer() and set_freepointer() functions that used to be only
     intended for the slow path now are also useful for the hot path since access
     to the field does not require accessing an additional cacheline anymore. This
     results in consistent use of setting the freepointer for objects throughout
     SLUB.

     Also we initialize all possible kmem_cache_cpu structures when a slab is
     created. No need to initialize them when a processor or node comes online.
     And all fields are set to zero. So just use __GFP_ZERO on cpu alloc.

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

commit e88a3b4cf66e40d81e8fcda870260a237a58a920
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:38 2008 -0600

     cpu alloc: Use in slub

     Using cpu alloc removes the needs for the per cpu arrays in the kmem_cache struct.
     These could get quite big if we have to support system of up to thousands of cpus.
     The use of cpu_alloc means that:

     1. The size of kmem_cache for SMP configuration shrinks since we will only
        need 1 pointer instead of NR_CPUS. The same pointer can be used by all
        processors. Reduces cache footprint of the allocator.

     2. We can dynamically size kmem_cache according to the actual nodes in the
        system meaning less memory overhead for configurations that may potentially
        support up to 1k NUMA nodes / 4k cpus.

     3. We can remove the diddle widdle with allocating and releasing of
        kmem_cache_cpu structures when bringing up and shutting down cpus. The cpu
        alloc logic will do it all for us. Removes some portions of the cpu hotplug
        functionality.

     4. Fastpath performance increases.

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

commit 240314584fcc19042c6d016954f3b9971d94bf2f
Author: Christoph Lameter <cl@linux-foundation.org>
Date:   Tue Nov 4 16:32:38 2008 -0600

     Increase default reserve percpu area

     SLUB now requires a portion of the per cpu reserve. There are on average
     about 70 real slabs on a system (aliases do not count) and each needs 12 bytes
     of per cpu space. Thats 840 bytes. In debug mode all slabs will be real slabs
     which will make us end up with 150 -> 1800.

     Things work fine without this patch but then slub will reduce the percpu reserve
     for modules.

     Percpu data must be available regardless if modules are in use or not. So get
     rid of the #ifdef CONFIG_MODULES.

     Make the size of the percpu area dependant on the size of a machine word. That
     way we have larger sizes for 64 bit machines. 64 bit machines need more percpu
     memory since the pointer and counters may have double the size. Plus there is
     lots of memory available on 64 bit.

     Signed-off-by: Christoph Lameter <cl@linux-foundation.org>

Re: Git next: Second stage of cpu_alloc patches

[Andrew Morton]

On Tue, 4 Nov 2008 20:56:52 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:

> The second stage of the cpu_alloc patchset can be pulled from
> 
> kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2

Please send the patches for review.  Always.


I've forgotten how this whole cpu_alloc thing worked and now it's all
stuffed away in some git tree somewhere.  Oh well, whee...

Re: Git next: Second stage of cpu_alloc patches

[Stephen Rothwell]

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

Hi Christoph,

On Tue, 4 Nov 2008 19:52:05 -0800 Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Tue, 4 Nov 2008 20:56:52 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:
> 
> > The second stage of the cpu_alloc patchset can be pulled from
> > 
> > kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2
> 
> Please send the patches for review.  Always.

And I would like to see a bit of positive feedback from the first set
(given we have boot failures bisected down to this stuff) before we add
more on top.

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: Git next: Second stage of cpu_alloc patches

[Vegard Nossum]

On Wed, Nov 5, 2008 at 8:26 AM, Stephen Rothwell <sfr@canb.auug.org.au> wrote:
> Hi Christoph,
>
> On Tue, 4 Nov 2008 19:52:05 -0800 Andrew Morton <akpm@linux-foundation.org> wrote:
>>
>> On Tue, 4 Nov 2008 20:56:52 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:
>>
>> > The second stage of the cpu_alloc patchset can be pulled from
>> >
>> > kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2
>>
>> Please send the patches for review.  Always.
>
> And I would like to see a bit of positive feedback from the first set
> (given we have boot failures bisected down to this stuff) before we add
> more on top.

Thanks. I will try out today's linux-next later today (if I can find
the time for it).

Just in case it helps track down the problem: Adding percpu=100000 to
the kernel command line got the thing booting for me. The number
itself was picked at random, but it worked on the first try. The
machine is a single-core P4 3.0 GHz with HT, 1G RAM, using slightly
modified F9 config.


Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: Git next: Second stage of cpu_alloc patches

[Christoph Lameter]

On Tue, 4 Nov 2008, Andrew Morton wrote:

> On Tue, 4 Nov 2008 20:56:52 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:
>
>> The second stage of the cpu_alloc patchset can be pulled from
>>
>> kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2
>
> Please send the patches for review.  Always.

Well okay can we define a process how to get patches merged with the -next 
tree involved? It was nice when you handled all of this but the last 
version of the cpu_alloc was thrown out of mm because of a -next conflict 
and so it seemed better to go to the source than risk this again.

> I've forgotten how this whole cpu_alloc thing worked and now it's all
> stuffed away in some git tree somewhere.  Oh well, whee...

Ok so post a patchset to lkml and at the same time offer a git tree?

Re: Git next: Second stage of cpu_alloc patches

[Christoph Lameter]

On Wed, 5 Nov 2008, Vegard Nossum wrote:

> Just in case it helps track down the problem: Adding percpu=100000 to
> the kernel command line got the thing booting for me. The number
> itself was picked at random, but it worked on the first try. The
> machine is a single-core P4 3.0 GHz with HT, 1G RAM, using slightly
> modified F9 config.

Its only happening if !CONFIG_MODULES because then the reserve size is 
zero. The second stage patches fix that because there will then be other 
uses of the allocator so that reserves are always needed. This hunk from 
the second stage fixes the !CONFIG_MODULES issue.


Index: linux-2.6/include/linux/percpu.h
===================================================================
--- linux-2.6.orig/include/linux/percpu.h	2008-11-05 07:41:22.134646124 -0600
+++ linux-2.6/include/linux/percpu.h	2008-11-05 07:44:28.603155403 -0600
@@ -44,11 +44,7 @@
  extern unsigned int percpu_reserve;
  /* Enough to cover all DEFINE_PER_CPUs in kernel, including modules. */
  #ifndef PERCPU_AREA_SIZE
-#ifdef CONFIG_MODULES
  #define PERCPU_RESERVE_SIZE	8192
-#else
-#define PERCPU_RESERVE_SIZE	0
-#endif

  #define PERCPU_AREA_SIZE						\
  	(__per_cpu_end - __per_cpu_start + percpu_reserve)

Re: Git next: Second stage of cpu_alloc patches

[Andrew Morton]

On Wed, 5 Nov 2008 07:54:39 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:

> On Tue, 4 Nov 2008, Andrew Morton wrote:
> 
> > On Tue, 4 Nov 2008 20:56:52 -0600 (CST) Christoph Lameter <cl@linux-foundation.org> wrote:
> >
> >> The second stage of the cpu_alloc patchset can be pulled from
> >>
> >> kernel.org/pub/scm/linux/kernel/git/christoph/work.git cpu_alloc_stage2
> >
> > Please send the patches for review.  Always.
> 
> Well okay can we define a process how to get patches merged with the -next 
> tree involved? It was nice when you handled all of this but the last 
> version of the cpu_alloc was thrown out of mm because of a -next conflict 
> and so it seemed better to go to the source than risk this again.
> 
> > I've forgotten how this whole cpu_alloc thing worked and now it's all
> > stuffed away in some git tree somewhere.  Oh well, whee...
> 
> Ok so post a patchset to lkml and at the same time offer a git tree?

Sure.

For important things I think it doesn't hurt to resend even if they've
been "reviewed" beforehand.  Particularly if you don't think enough
attention was paid to them.

These patches are a good example of that.  By the time 2.6.29 opens
everyone will have forgotten what all this stuff does and how it
works.

We need to get alpha sorted out too.  Frankly, if we can't get anyone to
review/test/ack the alpha genirq conversion then I'd say merge it
anyway.  I'll make sure that it at least compiles.

Re: Git next: Second stage of cpu_alloc patches

[Vegard Nossum]

On Wed, Nov 5, 2008 at 5:27 PM, Andrew Morton <akpm@linux-foundation.org> wrote:
> We need to get alpha sorted out too.  Frankly, if we can't get anyone to
> review/test/ack the alpha genirq conversion then I'd say merge it
> anyway.  I'll make sure that it at least compiles.

Sounds like a bad strategy. What are these patches you're talking
about, and where can I find them?

I mean, isn't "merge anyway" the same as admitting defeat? I thought
we were going for 100% "review coverage".


Vegard

-- 
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

Re: Git next: Second stage of cpu_alloc patches

[Andrew Morton]

On Wed, 5 Nov 2008 22:12:04 +0100
"Vegard Nossum" <vegard.nossum@gmail.com> wrote:

> On Wed, Nov 5, 2008 at 5:27 PM, Andrew Morton <akpm@linux-foundation.org> wrote:
> > We need to get alpha sorted out too.  Frankly, if we can't get anyone to
> > review/test/ack the alpha genirq conversion then I'd say merge it
> > anyway.  I'll make sure that it at least compiles.
> 
> Sounds like a bad strategy. What are these patches you're talking
> about, and where can I find them?

The cpu_alloc patches broke the alpha build.  The proposed fix is below.

> I mean, isn't "merge anyway" the same as admitting defeat? I thought
> we were going for 100% "review coverage".

alpha development isn't exactly proceeding at a feverish rate lately. 
No blame attached to that - the reasons are pretty obvious.  I expect
that at some stage we'll remove it altogether.

In the meanwhile if alpha (or anything similar) gets in the way of core
kernel development, all we can do is best-effort maintenance of it
while hoping it didn't break too badly.  We cannot stop core kernel
development.




From: Christoph Lameter <cl@linux-foundation.org>

The percpu support for alpha currently expects a percpu variable to be
passed to SHIFT_PERCPU_PTR.  However, SHIFT_PERCPU_PTR takes a pointer
and not a variable.  This breaks code that uses SHIFT_PERCPU_PTR on a
pointer.

Simply switch alpha to use generic cpu.

The purpose of the special percpu code seems to be optmization.  That
could be done by modifying the per_cpu_var() (and related) macros which
indeed take a variable as a parameter.

Signed-off-by: Christoph Lameter <cl@linux-foundation.org>
Cc: Jay Estabrook <jay.estabrook@hp.com>
Cc: Rusty Russell <rusty@rustcorp.com.au>
Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
Cc: Richard Henderson <rth@twiddle.net>
CC: Stephen Rothwell <sfr@canb.auug.org.au>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
---

 arch/alpha/include/asm/percpu.h |   77 ------------------------------
 1 file changed, 1 insertion(+), 76 deletions(-)

diff -puN arch/alpha/include/asm/percpu.h~alpha-use-generic-percpu-support arch/alpha/include/asm/percpu.h
--- a/arch/alpha/include/asm/percpu.h~alpha-use-generic-percpu-support
+++ a/arch/alpha/include/asm/percpu.h
@@ -1,79 +1,4 @@
 #ifndef __ALPHA_PERCPU_H
 #define __ALPHA_PERCPU_H
-#include <linux/compiler.h>
-#include <linux/threads.h>
-
-/*
- * Determine the real variable name from the name visible in the
- * kernel sources.
- */
-#define per_cpu_var(var) per_cpu__##var
-
-#ifdef CONFIG_SMP
-
-/*
- * per_cpu_offset() is the offset that has to be added to a
- * percpu variable to get to the instance for a certain processor.
- */
-extern unsigned long __per_cpu_offset[NR_CPUS];
-
-#define per_cpu_offset(x) (__per_cpu_offset[x])
-
-#define __my_cpu_offset per_cpu_offset(raw_smp_processor_id())
-#ifdef CONFIG_DEBUG_PREEMPT
-#define my_cpu_offset per_cpu_offset(smp_processor_id())
-#else
-#define my_cpu_offset __my_cpu_offset
-#endif
-
-#ifndef MODULE
-#define SHIFT_PERCPU_PTR(var, offset) RELOC_HIDE(&per_cpu_var(var), (offset))
-#define PER_CPU_ATTRIBUTES
-#else
-/*
- * To calculate addresses of locally defined variables, GCC uses 32-bit
- * displacement from the GP. Which doesn't work for per cpu variables in
- * modules, as an offset to the kernel per cpu area is way above 4G.
- *
- * This forces allocation of a GOT entry for per cpu variable using
- * ldq instruction with a 'literal' relocation.
- */
-#define SHIFT_PERCPU_PTR(var, offset) ({		\
-	extern int simple_identifier_##var(void);	\
-	unsigned long __ptr, tmp_gp;			\
-	asm (  "br	%1, 1f		  	      \n\
-	1:	ldgp	%1, 0(%1)	    	      \n\
-		ldq %0, per_cpu__" #var"(%1)\t!literal"		\
-		: "=&r"(__ptr), "=&r"(tmp_gp));		\
-	(typeof(&per_cpu_var(var)))(__ptr + (offset)); })
-
-#define PER_CPU_ATTRIBUTES	__used
-
-#endif /* MODULE */
-
-/*
- * A percpu variable may point to a discarded regions. The following are
- * established ways to produce a usable pointer from the percpu variable
- * offset.
- */
-#define per_cpu(var, cpu) \
-	(*SHIFT_PERCPU_PTR(var, per_cpu_offset(cpu)))
-#define __get_cpu_var(var) \
-	(*SHIFT_PERCPU_PTR(var, my_cpu_offset))
-#define __raw_get_cpu_var(var) \
-	(*SHIFT_PERCPU_PTR(var, __my_cpu_offset))
-
-#else /* ! SMP */
-
-#define per_cpu(var, cpu)		(*((void)(cpu), &per_cpu_var(var)))
-#define __get_cpu_var(var)		per_cpu_var(var)
-#define __raw_get_cpu_var(var)		per_cpu_var(var)
-#define per_cpu_offset(x) 0
-
-#define PER_CPU_ATTRIBUTES
-
-#endif /* SMP */
-
-#define DECLARE_PER_CPU(type, name) extern __typeof__(type) per_cpu_var(name)
-
+#include <asm-generic/percpu.h>
 #endif /* __ALPHA_PERCPU_H */
_

Re: Git next: Second stage of cpu_alloc patches

[Johannes Weiner]

On Wed, Nov 05, 2008 at 07:54:39AM -0600, Christoph Lameter wrote:
> Ok so post a patchset to lkml and at the same time offer a git tree?

Git is perhaps a more convenient way to pick up changesets compared to
extracting them from emails but review and discussion should still
happen by Email, no?

	Hannes

Re: Git next: Second stage of cpu_alloc patches

[Stephen Rothwell]

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

On Thu, 6 Nov 2008 00:58:42 +0100 Johannes Weiner <hannes@cmpxchg.org> wrote:
>
> On Wed, Nov 05, 2008 at 07:54:39AM -0600, Christoph Lameter wrote:
> > Ok so post a patchset to lkml and at the same time offer a git tree?
> 
> Git is perhaps a more convenient way to pick up changesets compared to
> extracting them from emails but review and discussion should still
> happen by Email, no?

Correct.

-- 
Cheers,
Stephen Rothwell                    sfr@canb.auug.org.au
http://www.canb.auug.org.au/~sfr/

[-- Attachment #2: Type: application/pgp-signature, Size: 197 bytes --]

Re: Git next: Second stage of cpu_alloc patches

[Christoph Lameter]

On Thu, 6 Nov 2008, Stephen Rothwell wrote:

> On Thu, 6 Nov 2008 00:58:42 +0100 Johannes Weiner <hannes@cmpxchg.org> wrote:
> >
> > On Wed, Nov 05, 2008 at 07:54:39AM -0600, Christoph Lameter wrote:
> > > Ok so post a patchset to lkml and at the same time offer a git tree?
> >
> > Git is perhaps a more convenient way to pick up changesets compared to
> > extracting them from emails but review and discussion should still
> > happen by Email, no?
>
> Correct.

So what are the criteria when to repost a patchset? How extensive must the
changes be? This one has just minor fixes to the prior post.