Skip to contentSkip to conversation

mm: Reimplementation of dynamic percpu memory allocator

PATCH In review Ravikiran G Thirumalai 3 participants 10 messages Jan 13, 2005 – Jan 18, 2005

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 mm: Reimplementation of dynamic percpu memory allocator

Hi Andrew,
Could you consider this for inclusion in the mm tree? The patch has been tested in user space and kernel space. Manfred seems to like the fact that allocator doesn't depend on slab, so that it can be used for slab's internal head arrays. He had questions about fragmentation which I have answered.

Patch follows

Thanks,
Kiran

The following patch re-implements the linux dynamic percpu memory allocator so that:
1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.
2. Better memory usage
- Doesn't need a NR_CPUS pointer array for each allocation
- Interlaces objects making better utilization of memory/cachelines
- Userspace tests show 98% utilization with random sized allocations after repeated random frees
3. Provides truly node local allocation
- The percpu memory with existing alloc_percpu does node local allocation, but the NR_CPUS place holder is not node local. This problem doesn't exist with the new implementation.

Design:
We have "blocks" of memory akin to slabs. Each block has
(percpu blocksize) * NR_CPUS + (block management data structures) of kernel VA space allocated to it. Node local pages are allocated and mapped against the corresponding cpus' VA space. Pages are allocated for block management data structures and mapped to their corresponding VA. These reside at (percpu blocksize) * NR_CPUS offset from the beginning of the block. The allocator maintains a circular linked list of blocks, sorted in descending order of block utilization. On requests for objects, allocator tries to serve the request from the most utilized block.
The allocator allocates memory in multiples of a fixed currency size for a request. The allocator returns address of the percpu
object corresponding to cpu0. The cpu local variable for any given cpu can be obtained by simple arithmetic:
obj_address + cpu_id * PCPU_BLKSIZE.

Testing:
The block allocator has undergone some userspace stress testing with small counter sized objects as well as a large number of random sized objects.

Changes:
- Cleaned up userspace compatibility bits
- Fixed bufctl corruption due to bad arithmetic in free_bufctl

---

 include/linux/kernel.h |    2 
 include/linux/percpu.h |   18 -
 mm/Makefile            |    1 
 mm/percpu.c            |  703 +++++++++++++++++++++++++++++++++++++++++++++++++
 mm/slab.c              |   70 ----
 5 files changed, 713 insertions(+), 81 deletions(-)
include/linux/kernel.h +2 -0
diff -ruN -X dontdiff2 linux-2.6.10-mm2/include/linux/kernel.h alloc_percpu-2.6.10-mm2/include/linux/kernel.h
@@ -29,6 +29,8 @@
 
 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 #define ALIGN(x,a) (((x)+(a)-1)&~((a)-1))
+#define IS_ALIGNED(x,a) (!(((a) - 1) & (x)))
+#define IS_POWEROFTWO(x) (!(((x) - 1) & (x)))
 
 #define	KERN_EMERG	"<0>"	/* system is unusable			*/
 #define	KERN_ALERT	"<1>"	/* action must be taken immediately	*/
include/linux/percpu.h +7 -11
diff -ruN -X dontdiff2 linux-2.6.10-mm2/include/linux/percpu.h alloc_percpu-2.6.10-mm2/include/linux/percpu.h
@@ -15,23 +15,19 @@
 #define get_cpu_var(var) (*({ preempt_disable(); &__get_cpu_var(var); }))
 #define put_cpu_var(var) preempt_enable()
 
-#ifdef CONFIG_SMP
-
-struct percpu_data {
-	void *ptrs[NR_CPUS];
-	void *blkp;
-};
+/* This is the upper bound for an object using alloc_percpu */
+#define PCPU_BLKSIZE (PAGE_SIZE << 1)
+#define PCPU_CURR_SIZE        (sizeof (void *))
 
+#ifdef CONFIG_SMP
 /* 
  * Use this to get to a cpu's version of the per-cpu object allocated using
  * alloc_percpu.  Non-atomic access to the current CPU's version should
  * probably be combined with get_cpu()/put_cpu().
  */ 
 #define per_cpu_ptr(ptr, cpu)                   \
-({                                              \
-        struct percpu_data *__p = (struct percpu_data *)~(unsigned long)(ptr); \
-        (__typeof__(ptr))__p->ptrs[(cpu)];	\
-})
+	((__typeof__(ptr))                      \
+	(RELOC_HIDE(ptr,  PCPU_BLKSIZE * cpu)))
 
 extern void *__alloc_percpu(size_t size, size_t align);
 extern void free_percpu(const void *);
@@ -56,6 +52,6 @@
 
 /* Simple wrapper for the common case: zeros memory. */
 #define alloc_percpu(type) \
-	((type *)(__alloc_percpu(sizeof(type), __alignof__(type))))
+	((type *)(__alloc_percpu(ALIGN(sizeof (type), PCPU_CURR_SIZE),  __alignof__(type))))
 
 #endif /* __LINUX_PERCPU_H */
mm/Makefile +1 -0
diff -ruN -X dontdiff2 linux-2.6.10-mm2/mm/Makefile alloc_percpu-2.6.10-mm2/mm/Makefile
@@ -17,4 +17,5 @@
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
 obj-$(CONFIG_SHMEM) += shmem.o
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o
+obj-$(CONFIG_SMP)	+= percpu.o
 
mm/percpu.c +703 -0

703 lines not on this page · raw message

mm/slab.c +0 -70

82 lines not on this page · raw message

#1 lore raw
Quoted 3 lines · Ravikiran G Thirumalai

...
The following patch re-implements the linux dynamic percpu memory allocator

Heavens, it's complex.

Quoted 4 lines

1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.
2. Better memory usage

Quoted 8 lines

- Doesn't need a NR_CPUS pointer array for each allocation
- Interlaces objects making better utilization of memory/cachelines
- Userspace tests show 98% utilization with random sized allocations after repeated random frees
3. Provides truly node local allocation
- The percpu memory with existing alloc_percpu does node local allocation, but the NR_CPUS place holder is not node local. This problem doesn't exist with the new implementation.

But it does consume vmalloc space and will incur additional TLB reload costs.

mm/percpu.c line 116

Quoted 8 lines
mm/percpu.c +8 -0
+static void *
+valloc_percpu(void)
+{
+	int i,j = 0;
+	unsigned int nr_pages;
+	struct vm_struct *area, tmp;
+	struct page **tmppage;
+	struct page *pages[BLOCK_MANAGEMENT_PAGES];

How much stackspace is this guy using on 512-way?

mm/percpu.c line 126

Quoted 10 lines
mm/percpu.c +10 -0
+	unsigned int cpu_pages = PCPU_BLKSIZE >> PAGE_SHIFT;
+	struct pcpu_block *blkp = NULL;
+
+	BUG_ON(!IS_ALIGNED(PCPU_BLKSIZE, PAGE_SIZE));
+	BUG_ON(!PCPU_BLKSIZE);
+	nr_pages = PCPUPAGES_PER_BLOCK + BLOCK_MANAGEMENT_PAGES;	
+
+	/* Alloc Managent block pages */
+	for ( i = 0; i < BLOCK_MANAGEMENT_PAGES; i++) {
+		pages[i] = alloc_pages(GFP_KERNEL, 0);

Can use __GFP_ZERO here.

mm/percpu.c line 133

Quoted 7 lines
mm/percpu.c +7 -0
+		if (!pages[i]) {
+			while ( --i >= 0 ) 
+				__free_pages(pages[i], 0);
+			return NULL;
+		}
+		/* Zero the alloced page */
+		clear_page(page_address(pages[i]));

And so can remove this.

Cannot highmem pages be used here?

mm/percpu.c line 151

Quoted 1 line
mm/percpu.c +1 -0
+	for ( i = 0; i < BLOCK_MANAGEMENT_PAGES; i++)

Patch has a fair amount of whitespace oddities.

mm/percpu.c line 156

Quoted 3 lines
mm/percpu.c +3 -0
+	/* Alloc node local pages for all cpus possible */
+	for (i = 0; i < NR_CPUS; i++) {
+		if (cpu_possible(i)) {

Isn't this equivalent to for_each_cpu()?

mm/percpu.c line 170

Quoted 3 lines
mm/percpu.c +3 -0
+	/* Map pages for each cpu by splitting vm_struct for each cpu */
+	for (i = 0; i < NR_CPUS; i++) {
+		if (cpu_possible(i)) {

etc.

mm/percpu.c line 320

Quoted 3 lines
mm/percpu.c +3 -0
+/* Sort obj_map array in ascending order -- simple bubble sort */
+static void
+sort_obj_map(struct obj_map_elmt map[], int nr)

That'll be unpopular ;) Why not extract qsort from XFS?

Why cannot the code simply call vmalloc rather than copying its internals?

Have you considered trying a simple __alloc_pages, fall back to vmalloc if that fails, or if the requested size is more than eight pages, or something of that sort?

#2 lore raw
Quoted 6 lines · Andrew Morton
Quoted 3 lines · Ravikiran G Thirumalai

...
The following patch re-implements the linux dynamic percpu memory allocator

Heavens, it's complex.

:p

Quoted 17 lines
Quoted 13 lines

1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.
2. Better memory usage
- Doesn't need a NR_CPUS pointer array for each allocation
- Interlaces objects making better utilization of memory/cachelines
- Userspace tests show 98% utilization with random sized allocations after repeated random frees
3. Provides truly node local allocation
- The percpu memory with existing alloc_percpu does node local allocation, but the NR_CPUS place holder is not node local. This problem doesn't exist with the new implementation.

But it does consume vmalloc space and will incur additional TLB reload costs.

Quoted 10 lines

mm/percpu.c line 116

Quoted 8 lines
mm/percpu.c +8 -0
+static void *
+valloc_percpu(void)
+{
+	int i,j = 0;
+	unsigned int nr_pages;
+	struct vm_struct *area, tmp;
+	struct page **tmppage;
+	struct page *pages[BLOCK_MANAGEMENT_PAGES];

How much stackspace is this guy using on 512-way?

36 bytes. BLOCK_MANAGEMENT_PAGES is not dependent on NR_CPUS. It depends on the number of objects in a block -- depends on the currency size and the max obj size. With current values, BLOCK_MANAGEMENT_PAGES is 9

Quoted 24 lines

mm/percpu.c line 126

Quoted 11 lines
mm/percpu.c +10 -0
+	unsigned int cpu_pages = PCPU_BLKSIZE >> PAGE_SHIFT;
+	struct pcpu_block *blkp = NULL;
+
+	BUG_ON(!IS_ALIGNED(PCPU_BLKSIZE, PAGE_SIZE));
+	BUG_ON(!PCPU_BLKSIZE);
+	nr_pages = PCPUPAGES_PER_BLOCK + BLOCK_MANAGEMENT_PAGES;	
+
+	/* Alloc Managent block pages */
+	for ( i = 0; i < BLOCK_MANAGEMENT_PAGES; i++) {
+		pages[i] = alloc_pages(GFP_KERNEL, 0);

Can use __GFP_ZERO here.

mm/percpu.c line 133

Quoted 7 lines
mm/percpu.c +7 -0
+		if (!pages[i]) {
+			while ( --i >= 0 ) 
+				__free_pages(pages[i], 0);
+			return NULL;
+		}
+		/* Zero the alloced page */
+		clear_page(page_address(pages[i]));

And so can remove this.

Quoted 1 line

Cannot highmem pages be used here?

Yes. Will change patch to do that.

Quoted 4 lines

mm/percpu.c line 151

Quoted 2 lines
mm/percpu.c +1 -0
+	for ( i = 0; i < BLOCK_MANAGEMENT_PAGES; i++)

Patch has a fair amount of whitespace oddities.

Will fix this.

Quoted 6 lines

mm/percpu.c line 156

Quoted 4 lines
mm/percpu.c +3 -0
+	/* Alloc node local pages for all cpus possible */
+	for (i = 0; i < NR_CPUS; i++) {
+		if (cpu_possible(i)) {

Isn't this equivalent to for_each_cpu()?

Yes. Will fix this too. This patch has been in the cans for quite some time and for_each_cpu wasn't available when I coded this up...

Quoted 7 lines

mm/percpu.c line 170

Quoted 4 lines
mm/percpu.c +3 -0
+	/* Map pages for each cpu by splitting vm_struct for each cpu */
+	for (i = 0; i < NR_CPUS; i++) {
+		if (cpu_possible(i)) {

etc.

Quoted 5 lines

mm/percpu.c line 320

Quoted 3 lines
mm/percpu.c +3 -0
+/* Sort obj_map array in ascending order -- simple bubble sort */
+static void
+sort_obj_map(struct obj_map_elmt map[], int nr)

That'll be unpopular ;) Why not extract qsort from XFS?

Ok, I'll make a patch to move qsort to a common place like linux/lib and use it in the next iteration. Just out of curiosity, is bubble sort unpopular or having two sort functions in the kernel source tree an issue here?

Quoted 2 lines

Why cannot the code simply call vmalloc rather than copying its internals?

Node local allocation. vmalloc cannot ensure pages for correspomding cpus are node local. Also, design goal was to allocate pages for cpu_possible cpus only. With plain vmalloc, we will end up allocating pages for NR_CPUS.

Quoted 4 lines

Have you considered trying a simple __alloc_pages, fall back to vmalloc if that fails, or if the requested size is more than eight pages, or something of that sort?

Again, node local allocation will be difficult and also this means we allocate pages for !cpu_possible cpus too.

I am travelling (we have a long weekend here), I will mail the revised patch early next week. Thanks for the review comments.

Thanks,
Kiran
Thanks,
Kiran

#3 lore raw
Quoted 4 lines · Ravikiran G Thirumalai

Just out of curiosity, is bubble
sort unpopular or having two sort functions in the kernel source tree an issue here?

yes and yes ;)

Quoted 7 lines
Quoted 2 lines

Why cannot the code simply call vmalloc rather than copying its internals?

Node local allocation. vmalloc cannot ensure pages for correspomding cpus are node local. Also, design goal was to allocate pages for cpu_possible cpus only. With plain vmalloc, we will end up allocating pages for NR_CPUS.

So... is it not possible to enhance vmalloc() for node-awareness, then just use it?

#4 lore raw
Quoted 5 lines · Andrew Morton
Quoted 3 lines · Ravikiran G Thirumalai
Quoted 2 lines

Why cannot the code simply call vmalloc rather than copying its internals?

Quoted 8 lines
Quoted 4 lines

Node local allocation. vmalloc cannot ensure pages for correspomding cpus are node local. Also, design goal was to allocate pages for cpu_possible cpus only. With plain vmalloc, we will end up allocating pages for NR_CPUS.

So... is it not possible to enhance vmalloc() for node-awareness, then just use it?

Memory for block management (free lists, bufctl lists) is also resident in one block. A typical block in this allocator looks like this:

VMALLOC_ADDR PAGE_ADDR BLOCK
============ ========= ========

0xa0000 0x10100 ----------------- ^ ^

  .				|		|	|	|
  .				|   cpu 0	| PCPU_BLKSIZE	|
				|		|	|	|
0xa0100		0x30100		-----------------	v	|
				|		|		|
				|   cpu 1	|		|
				|		|		|
0xa0200		   -		-----------------	     NR_CPUS		
				|		|		|
				| !cpu_possible	|		|
				|		|		|
0xa0300		   -		-----------------		|
				|		|		|
				| !cpu_possible	|		|
				|		|		|
0xa0400		0x10300		-----------------	  ^	v
				|		|	  |
				|  Block mgmt	|BLOCK_MANAGEMENT_SIZE	
				|		|	  |
0xa05ff				-----------------	  v

This block is setup by valloc_percpu in the allocator code. There is lot of allocator specific stuff like the PCPU_BLKSIZE, BLOCK_MANAGEMENT_SIZE used here. I thought it was not appropriate to put them in vmalloc.c. A common vmalloc_percpu which can take arguments for PCPU_BLKSIZE and BLOCK_MANAGEMENT_SIZE is not useful anywhere else.

Changed patchset with other modifications suggested will follow.

Thanks,
Kiran

#5 lore raw
Quoted 8 lines · Ravikiran G Thirumalai
Quoted 4 lines

So... is it not possible to enhance vmalloc() for node-awareness, then just use it?

Memory for block management (free lists, bufctl lists) is also resident in one block. A typical block in this allocator looks like this:

I still don't get it. It is possible to calculate the total size of the block beforehand, yes? So why not simply vmalloc_numa() a block of that size then populate it?

#6 lore raw
Quoted 6 lines · Andrew Morton
Quoted 5 lines · Ravikiran G Thirumalai
Quoted 4 lines

So... is it not possible to enhance vmalloc() for node-awareness, then just use it?

Quoted 7 lines
Quoted 3 lines

Memory for block management (free lists, bufctl lists) is also resident in one block. A typical block in this allocator looks like this:

I still don't get it. It is possible to calculate the total size of the block beforehand, yes? So why not simply vmalloc_numa() a block of that size then populate it?

I should be excited to add a new api ;), but, then we would have something like:

void *vmalloc_numa(unsigned long size, unsigned long extra)

which would
1. Allocate (size * NR_CPUS + extra) worth of va space (vm_struct)
2. Allocate node local pages amounting to 'size' for each possible cpu
3. Allocate pages for 'extra'
4. Mapping 'size' amount of pages allocated for cpus to corresponding va space beginning from vm_struct.addr to
(vm_struct.addr + NR_CPUS * size - 1)
5. Map vm_struct.addr + NR_CPUS * size to pages allocated for extra in (3).

It is the need for this 'extra' -- the block management memory, which made me think against a common api outside the allocator. If you feel vmalloc_numa is the right approach, I will make a patch to put it in vmalloc.c in the next iteration.

Thanks,
Kiran

#7 lore raw
In reply to Ravikiran G Thirumalai
Quoted 12 lines · Ravikiran G Thirumalai

Hi Andrew,
Could you consider this for inclusion in the mm tree? The patch has been tested in user space and kernel space. Manfred seems to like the fact that allocator doesn't depend on slab, so that it can be used for slab's internal head arrays. He had questions about fragmentation which I have answered.

Patch follows

Thanks,
Kiran

Quoted 5 lines

The following patch re-implements the linux dynamic percpu memory allocator so that:
1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.

Hmm, for me one point of a good dynamic per-cpu implementation is that the same per_cpu_offset be used as for the static per-cpu variables. This means that architectures can put it in a register. It also has different properties than slab, because tiny allocations will be more common (ie. one counter).

I've had this implementation sitting around for a while: it's not enormously fast, but it is space-efficient, and would need a cache on the front if people started doing a high rate of allocs. First patch is merely a cleanup.

Rusty.
Name: Unification of per-cpu headers for SMP
Author: Rusty Russell
Status: Trivial
Depends: Percpu/percpu-up-unify.patch.gz

There's really only one sane way to implement accessing other CPU's variables, there's no real reason for archs to use a method other than __per_cpu_offset[], so move that from asm-*/percpu.h to linux/percpu.h.

include/asm-ia64/percpu.h +0 -3
Index: linux-2.6.11-rc1-bk1-Percpu/include/asm-ia64/percpu.h
===================================================================
@@ -35,9 +35,6 @@
  * external routine, to avoid include-hell.
  */
 #ifdef CONFIG_SMP
-
-extern unsigned long __per_cpu_offset[NR_CPUS];
-
 /* Equal to __per_cpu_offset[smp_processor_id()], but faster to access: */
 DECLARE_PER_CPU(unsigned long, local_per_cpu_offset);
 
init/main.c +1 -2
Index: linux-2.6.11-rc1-bk1-Percpu/init/main.c
===================================================================
@@ -305,11 +305,10 @@
 
 #else
 
-#ifdef __GENERIC_PER_CPU
 unsigned long __per_cpu_offset[NR_CPUS];
-
 EXPORT_SYMBOL(__per_cpu_offset);
 
+#ifdef __GENERIC_PER_CPU
 static void __init setup_per_cpu_areas(void)
 {
 	unsigned long size, i;
arch/ia64/kernel/setup.c +0 -5
Index: linux-2.6.11-rc1-bk1-Percpu/arch/ia64/kernel/setup.c
===================================================================
@@ -56,11 +56,6 @@
 # error "struct cpuinfo_ia64 too big!"
 #endif
 
-#ifdef CONFIG_SMP
-unsigned long __per_cpu_offset[NR_CPUS];
-EXPORT_SYMBOL(__per_cpu_offset);
-#endif
-
 DEFINE_PER_CPU(struct cpuinfo_ia64, cpu_info);
 DEFINE_PER_CPU(unsigned long, local_per_cpu_offset);
 DEFINE_PER_CPU(unsigned long, ia64_phys_stacked_size_p8);
include/linux/percpu.h +3 -0
Index: linux-2.6.11-rc1-bk1-Percpu/include/linux/percpu.h
===================================================================
@@ -16,6 +16,9 @@
 #define put_cpu_var(var) preempt_enable()
 
 #ifdef CONFIG_SMP
+/* var is in discarded region: offset to particular copy we want */
+#define per_cpu(var, cpu) (*RELOC_HIDE(&per_cpu__##var, __per_cpu_offset[cpu]))
+extern unsigned long __per_cpu_offset[NR_CPUS];
 
 struct percpu_data {
 	void *ptrs[NR_CPUS];
include/asm-generic/percpu.h +0 -4
Index: linux-2.6.11-rc1-bk1-Percpu/include/asm-generic/percpu.h
===================================================================
@@ -5,14 +5,10 @@
 #define __GENERIC_PER_CPU
 #ifdef CONFIG_SMP
 
-extern unsigned long __per_cpu_offset[NR_CPUS];
-
 /* Separate out the type, so (int[3], foo) works. */
 #define DEFINE_PER_CPU(type, name) \
     __attribute__((__section__(".data.percpu"))) __typeof__(type) per_cpu__##name
 
-/* var is in discarded region: offset to particular copy we want */
-#define per_cpu(var, cpu) (*RELOC_HIDE(&per_cpu__##var, __per_cpu_offset[cpu]))
 #define __get_cpu_var(var) per_cpu(var, smp_processor_id())
 
 /* A macro to avoid #include hell... */

Name: Dynamic per-cpu allocation using static per-cpu mechanism
Author: Rusty Russell
Status: Tested on 2.6.10-rc2-bk13

This patch replaces the dynamic per-cpu allocator, alloc_percpu, to make it use the same mechanism as the static per-cpu variables, ie. ptr + __per_cpu_offset[smp_processor_id()] gives the variable address. This increases space and time efficiency of reference at the same time.

This is a generalization of the allocator in kernel/module.c: it gets moved to its own (SMP-only) file: mm/percpu.c.

The basic idea is that when we need more memory, we allocate another NR_CPUS*sizeof(.data.percpu section), and hand allocations out from that (minus the __per_cpu_offset, which is set at boot from the difference between the .data.percpu section and the initial NR_CPUS*sizeof(.data.percpu section) allocation.

The situation is made trickier by archs which want to allocate per-cpu memory near the CPUs which use them: hooks are provided for the initial alloc (arch_alloc_percpu_bootmem(), which can also change the size of the allocation, eg. to page-align) and arch_alloc_percpu(). __GENERIC_PER_CPU gets sane default implementations.

mm/percpu.c new file +334 -0

334 lines not on this page · raw message

init/main.c +0 -29
Index: linux-2.6.11-rc1-bk1-Percpu/init/main.c
===================================================================
@@ -300,38 +300,9 @@
 #define smp_init()	do { } while (0)
 #endif
 
-static inline void setup_per_cpu_areas(void) { }
 static inline void smp_prepare_cpus(unsigned int maxcpus) { }
 
 #else
-
-unsigned long __per_cpu_offset[NR_CPUS];
-EXPORT_SYMBOL(__per_cpu_offset);
-
-#ifdef __GENERIC_PER_CPU
-static void __init setup_per_cpu_areas(void)
-{
-	unsigned long size, i;
-	char *ptr;
-	/* Created by linker magic */
-	extern char __per_cpu_start[], __per_cpu_end[];
-
-	/* Copy section for each CPU (we discard the original) */
-	size = ALIGN(__per_cpu_end - __per_cpu_start, SMP_CACHE_BYTES);
-#ifdef CONFIG_MODULES
-	if (size < PERCPU_ENOUGH_ROOM)
-		size = PERCPU_ENOUGH_ROOM;
-#endif
-
-	ptr = alloc_bootmem(size * NR_CPUS);
-
-	for (i = 0; i < NR_CPUS; i++, ptr += size) {
-		__per_cpu_offset[i] = ptr - __per_cpu_start;
-		memcpy(ptr, __per_cpu_start, __per_cpu_end - __per_cpu_start);
-	}
-}
-#endif /* !__GENERIC_PER_CPU */
-
 /* Called by boot processor to activate the rest. */
 static void __init smp_init(void)
 {
kernel/module.c +0 -139

152 lines not on this page · raw message

include/linux/percpu.h +16 -14
Index: linux-2.6.11-rc1-bk1-Percpu/include/linux/percpu.h
===================================================================
@@ -1,7 +1,7 @@
 #ifndef __LINUX_PERCPU_H
 #define __LINUX_PERCPU_H
 #include <linux/spinlock.h> /* For preempt_disable() */
-#include <linux/slab.h> /* For kmalloc() */
+#include <linux/slab.h> /* FIXME: remove this, fix hangers-on --RR */
 #include <linux/smp.h>
 #include <linux/string.h> /* For memset() */
 #include <asm/percpu.h>
@@ -20,24 +20,18 @@
 #define per_cpu(var, cpu) (*RELOC_HIDE(&per_cpu__##var, __per_cpu_offset[cpu]))
 extern unsigned long __per_cpu_offset[NR_CPUS];
 
-struct percpu_data {
-	void *ptrs[NR_CPUS];
-	void *blkp;
-};
-
 /* 
  * Use this to get to a cpu's version of the per-cpu object allocated using
- * alloc_percpu.  Non-atomic access to the current CPU's version should
- * probably be combined with get_cpu()/put_cpu().
+ * alloc_percpu.  If you want to get "this cpu's version", maybe you want
+ * to use get_cpu_ptr... 
  */ 
-#define per_cpu_ptr(ptr, cpu)                   \
-({                                              \
-        struct percpu_data *__p = (struct percpu_data *)~(unsigned long)(ptr); \
-        (__typeof__(ptr))__p->ptrs[(cpu)];	\
-})
+#define per_cpu_ptr(ptr, cpu)						\
+        ((__typeof__(ptr))((void *)ptr + __per_cpu_offset[(cpu)]))
 
-extern void *__alloc_percpu(size_t size, size_t align);
+extern void *__alloc_percpu(unsigned long size, unsigned long align);
 extern void free_percpu(const void *);
+extern void *percpu_modalloc(unsigned long size, unsigned long align);
+extern void percpu_modfree(void *freeme);
 
 #else /* CONFIG_SMP */
 
@@ -55,6 +49,14 @@
 	kfree(ptr);
 }
 
+static inline void *percpu_modalloc(unsigned long size, unsigned long align)
+{
+	return NULL;
+}
+	
+static inline void percpu_modfree(void *freeme)
+{
+}
 #endif /* CONFIG_SMP */
 
 /* Simple wrapper for the common case: zeros memory. */
mm/slab.c +0 -70

82 lines not on this page · raw message

mm/Makefile +1 -1
Index: linux-2.6.11-rc1-bk1-Percpu/mm/Makefile
===================================================================
@@ -17,4 +17,4 @@
 obj-$(CONFIG_NUMA) 	+= mempolicy.o
 obj-$(CONFIG_SHMEM) += shmem.o
 obj-$(CONFIG_TINY_SHMEM) += tiny-shmem.o
-
+obj-$(CONFIG_SMP)	+= percpu.o
include/asm-generic/percpu.h +8 -1
Index: linux-2.6.11-rc1-bk1-Percpu/include/asm-generic/percpu.h
===================================================================
@@ -10,6 +10,8 @@
     __attribute__((__section__(".data.percpu"))) __typeof__(type) per_cpu__##name
 
 #define __get_cpu_var(var) per_cpu(var, smp_processor_id())
+#define __get_cpu_ptr(ptr) \
+	((__typeof__(ptr))((void *)ptr + __per_cpu_offset[smp_processor_id()]))
 
 /* A macro to avoid #include hell... */
 #define percpu_modcopy(pcpudst, src, size)			\
@@ -20,6 +22,8 @@
 			memcpy((pcpudst)+__per_cpu_offset[__i],	\
 			       (src), (size));			\
 } while (0)
+
+void setup_per_cpu_areas(void);
 #else /* ! SMP */
 
 #define DEFINE_PER_CPU(type, name) \
@@ -27,7 +31,10 @@
 
 #define per_cpu(var, cpu)			(*((void)cpu, &per_cpu__##var))
 #define __get_cpu_var(var)			per_cpu__##var
-
+#define __get_cpu_ptr(ptr)			(ptr)
+static inline void setup_per_cpu_areas(void)
+{
+}
 #endif	/* SMP */
 
 #define DECLARE_PER_CPU(type, name) extern __typeof__(type) per_cpu__##name
Signature · 1 line
A bad analogy is like a leaky screwdriver -- Richard Braakman
#8 lore raw
Quoted 9 lines · Rusty Russell
Quoted 7 lines · Ravikiran G Thirumalai

...

The following patch re-implements the linux dynamic percpu memory allocator so that:
1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.

Quoted 3 lines

Hmm, for me one point of a good dynamic per-cpu implementation is that the same per_cpu_offset be used as for the static per-cpu variables. This means that architectures can put it in a register.

The allocator I have posted can be easily fixed for that. In fact, I had a version which used per_cpu_offset. My earlier experiments proved that pointer arithmetic is marginally faster than the per_cpu_offset based version. Also, why waste a register if we can achieve same dereference speeds without using a register? But as I said, we can modify the allocator I posted to use per_cpu_offset.

Quoted 3 lines

It also has
different properties than slab, because tiny allocations will be more common (ie. one counter).

As regards tiny allocations, many existing users of alloc_percpu are structures which are aggregations of many counters -- like the mib statistics, disk_stats etc. So IMHO, dynamic percpu allocator should work well for both small and large objects. I have done some user space measurements with my version and the allocator behaves well with both small and random sized objects.

The advantages of my implementation as I see it is:
1. Independent of slab/kmalloc
2. Doesn't need arches to do their own node local allocation -- generic version does that.
3. Space efficient -- about 98% utilization achieved in userspace tests
4. Allocates pages for cpu_possible cpus only

disadvantage:
1. Uses vmalloc area and hence additional tlb foot print -- but is there a better way to keep node local allocations, simple pointer arithmetic and page allocations for cpu_possible cpus only

Thanks,
Kiran

#9 lore raw
Quoted 14 lines · Ravikiran G Thirumalai
Quoted 9 lines · Rusty Russell
Quoted 7 lines · Ravikiran G Thirumalai

...

The following patch re-implements the linux dynamic percpu memory allocator so that:
1. Percpu memory dereference is faster
- One less memory reference compared to existing simple alloc_percpu
- As fast as with static percpu areas, one mem ref less actually.

Quoted 3 lines

Hmm, for me one point of a good dynamic per-cpu implementation is that the same per_cpu_offset be used as for the static per-cpu variables. This means that architectures can put it in a register.

Quoted 6 lines

The allocator I have posted can be easily fixed for that. In fact, I had a version which used per_cpu_offset. My earlier experiments proved that pointer arithmetic is marginally faster than the per_cpu_offset based version. Also, why waste a register if we can achieve same dereference speeds without using a register? But as I said, we can modify the allocator I posted to use per_cpu_offset.

Because we ALSO use per_cpu_offset for static per-cpu. In fact, it starts to make sense to make smp_processor_id a normal per-cpu variable, since increasingly we just want "this cpu's version of the datastructure".

ie. increasingly, this cpu's per_cpu_offset is fundamental. The fact that currently smp_processor_id() is fundamental and per_cpu_offset derived warps current timings.

Quoted 6 lines

As regards tiny allocations, many existing users of alloc_percpu are structures which are aggregations of many counters -- like the mib statistics, disk_stats etc. So IMHO, dynamic percpu allocator should work well for both small and large objects. I have done some user space measurements with my version and the allocator behaves well with both small and random sized objects.

See this experimental kref replacement to see what I mean.

BTW, I'm really glad someone's working on this. Thanks! Rusty.

Author: Rusty Russell
Status: Experimental
Depends: Percpu/kmalloc_percpu-full.patch.gz

This is an implementation of cache-friendly reference counts, using kmalloc_percpu.

The refcounters work in two modes: the normal mode just incs and decs a per-cpu counter. When someone is waiting for the reference count to hit 0, a common counter is used.

kernel/bigref.c new file +98 -0
Index: linux-2.6.10-rc2-bk13-Percpu/kernel/bigref.c
===================================================================
@@ -0,0 +1,98 @@
+#include <linux/bigref.h>
+#include <linux/compiler.h>
+#include <linux/percpu.h>
+#include <linux/rcupdate.h>
+#include <linux/module.h>
+#include <asm/system.h>
+
+static inline int is_slow_mode(const struct bigref *bigref)
+{
+	return atomic_read(&bigref->slow_ref) != 0;
+}
+
+/* Initialize reference to 1. */
+void bigref_init(struct bigref *bigref)
+{
+	bigref->local_ref = alloc_percpu(local_t);
+
+	/* If we can't allocate, we just stay in slow mode. */
+	if (!bigref->local_ref)
+		atomic_set(&bigref->slow_ref, 1);
+	else {
+		/* Bump any counter to 1. */
+		local_set(__get_cpu_ptr(bigref->local_ref), 1);
+		atomic_set(&bigref->slow_ref, 0);
+	}
+}
+
+/* Disown reference: next bigref_put can hit zero */
+void bigref_disown(struct bigref *bigref)
+{
+	int i, bias = 0x7FFFFFFF;
+	if (unlikely(is_slow_mode(bigref))) {
+		/* Must have been alloc fail, not double disown. */
+		BUG_ON(bigref->local_ref);
+		return;
+	}
+
+	/* Insert high number so this doesn't go to zero now. */
+	atomic_set(&bigref->slow_ref, bias);
+
+	/* Make sure everyone sees it and is using slow mode. */
+	synchronize_kernel();
+
+	/* Take away bias, and add sum of local counters. */
+	for_each_cpu(i)
+		bias -= local_read(per_cpu_ptr(bigref->local_ref, i));
+	atomic_sub(bias, &bigref->slow_ref);
+
+	/* This caller should be holding one reference. */
+	BUG_ON(atomic_read(&bigref->slow_ref) == 0);
+}
+
+/* Grab reference */
+void bigref_get(struct bigref *bigref)
+{
+	if (unlikely(is_slow_mode(bigref)))
+		atomic_inc(&bigref->slow_ref);
+	else
+		local_inc(__get_cpu_ptr(bigref->local_ref));
+}
+
+/* Drop reference */
+void bigref_put(struct bigref *bigref, void (*release)(struct bigref *bigref))
+{
+	if (unlikely(is_slow_mode(bigref))) {
+		if (atomic_dec_and_test(&bigref->slow_ref)) {
+			free_percpu(bigref->local_ref);
+			release(bigref);
+		}
+	} else
+		local_dec(__get_cpu_ptr(bigref->local_ref));
+}
+
+void bigref_destroy(struct bigref *bigref)
+{
+	if (bigref->local_ref)
+		free_percpu(bigref->local_ref);
+}
+
+/* Get current value of reference, useful for debugging info. */
+unsigned int bigref_val(struct bigref *bigref)
+{
+	unsigned int sum = 0, i;
+
+	if (unlikely(is_slow_mode(bigref)))
+		sum = atomic_read(&bigref->slow_ref);
+	else
+		for_each_cpu(i)
+			sum += local_read(per_cpu_ptr(bigref->local_ref, i));
+	return sum;
+}
+
+EXPORT_SYMBOL(bigref_init);
+EXPORT_SYMBOL(bigref_disown);
+EXPORT_SYMBOL(bigref_get);
+EXPORT_SYMBOL(bigref_put);
+EXPORT_SYMBOL(bigref_destroy);
+EXPORT_SYMBOL(bigref_val);
include/linux/bigref.h new file +76 -0

76 lines not on this page · raw message

kernel/Makefile +1 -1
Index: linux-2.6.10-rc2-bk13-Percpu/kernel/Makefile
===================================================================
@@ -11,7 +11,7 @@
 
 obj-$(CONFIG_FUTEX) += futex.o
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-obj-$(CONFIG_SMP) += cpu.o spinlock.o
+obj-$(CONFIG_SMP) += cpu.o spinlock.o bigref.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_KALLSYMS) += kallsyms.o
Signature · 1 line
A bad analogy is like a leaky screwdriver -- Richard Braakman