kmalloc_percpu -- 1 of 2

Here's a 2.5.50 version of kmalloc_percpu originally submitted by Dipankar. This one incorporates Rusty's suggestions to rearrange code and sync up with its static counterpart. This version needs exposure of malloc_sizes in order to move the interfaces to percpu.c from slab.c (kmalloc_percpu and kfree_percpu donot have anything to do with the slab allocator itself). First of the two patches is to expose the malloc_sizes and the second one is the actual allocator. I'll follow this up with patchsets to enable networking mibs use kmalloc_percpu. We'll have to use kmalloc_percpu for mibs since DEFINE_PER_CPU won't work with modules (and ipv6 stuff can be compiled in as modules)

Following is the 1 of 2 patches.

D: Name: slabchange-2.5.50-1.patch
D: Description: Exposes malloc_sizes for kmalloc_percpu
D: Author: Ravikiran Thirumalai

 include/linux/slab.h |   13 +++++++++++++
 mm/slab.c            |    9 +--------
 2 files changed, 14 insertions(+), 8 deletions(-)

diff -ruN linux-2.5.50/include/linux/slab.h kmalloc_percpu-2.5.50/include/linux/slab.h
@@ -75,6 +75,19 @@
 extern kmem_cache_t	*sigact_cachep;
 extern kmem_cache_t	*bio_cachep;
 
+/* 
+ * Size description struct for general caches. 
+ * This had to be exposed for kmalloc_percpu.
+ */
+
+struct cache_sizes {
+	size_t           cs_size;
+	kmem_cache_t    *cs_cachep;
+	kmem_cache_t    *cs_dmacachep;
+};
+
+extern struct cache_sizes malloc_sizes[];
+
 #endif	/* __KERNEL__ */
 
 #endif	/* _LINUX_SLAB_H */

diff -ruN linux-2.5.50/mm/slab.c kmalloc_percpu-2.5.50/mm/slab.c
@@ -369,15 +369,8 @@
 #define	SET_PAGE_SLAB(pg,x)   ((pg)->list.prev = (struct list_head *)(x))
 #define	GET_PAGE_SLAB(pg)     ((struct slab *)(pg)->list.prev)
 
-/* Size description struct for general caches. */
-struct cache_sizes {
-	size_t		 cs_size;
-	kmem_cache_t	*cs_cachep;
-	kmem_cache_t	*cs_dmacachep;
-};
-
 /* These are the default caches for kmalloc. Custom caches can have other sizes. */
-static struct cache_sizes malloc_sizes[] = {
+struct cache_sizes malloc_sizes[] = {
 #if PAGE_SIZE == 4096
 	{    32,	NULL, NULL},
 #endif

Here's a 2.5.50 version of kmalloc_percpu originally submitted by Dipankar. This one incorporates Rusty's suggestions to rearrange code and sync up with its static counterpart. This version needs exposure of malloc_sizes in order to move the interfaces to percpu.c from slab.c (kmalloc_percpu and kfree_percpu donot have anything to do with the slab allocator itself). First of the two patches is to expose the malloc_sizes and the second one is the actual allocator. I'll follow this up with patchsets to enable networking mibs use kmalloc_percpu. We'll have to use kmalloc_percpu for mibs since DEFINE_PER_CPU won't work with modules (and ipv6 stuff can be compiled in as modules)

Following is the 2 of 2 patches.

D: Name: kmalloc_percpu-2.5.50-1.patch
D: Description: Dynamic per-cpu kernel memory allocator
D: Author: Dipankar Sarma & Ravikiran Thirumalai

 include/linux/percpu.h |   39 ++++
 init/main.c            |    1 
 kernel/Makefile        |    4 
 kernel/ksyms.c         |    4 
 kernel/percpu.c        |  452 +++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 498 insertions(+), 2 deletions(-)

diff -ruN linux-2.5.50/include/linux/percpu.h kmalloc_percpu-2.5.50/include/linux/percpu.h
@@ -1,10 +1,49 @@
 #ifndef __LINUX_PERCPU_H
 #define __LINUX_PERCPU_H
 #include <linux/spinlock.h> /* For preempt_disable() */
+#include <linux/slab.h> /* For kmalloc_percpu() */
 #include <asm/percpu.h>
 
 /* Must be an lvalue. */
 #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;
+};
+
+/* Use this with kmalloc_percpu */
+#define per_cpu_ptr(ptr, cpu)                   \
+({                                              \
+        struct percpu_data *__p = (struct percpu_data *)~(unsigned long)(ptr); \
+        (__typeof__(ptr))__p->ptrs[(cpu)];	\
+})
+
+extern void *kmalloc_percpu(size_t size, int flags);
+extern void kfree_percpu(const void *);
+extern void kmalloc_percpu_init(void);
+
+#else /* CONFIG_SMP */
+
+#define per_cpu_ptr(ptr, cpu) (ptr)
+
+static inline void *kmalloc_percpu(size_t size, int flags)
+{
+	return(kmalloc(size, flags));
+}
+static inline void kfree_percpu(const void *ptr)
+{	
+	kfree(ptr);
+}
+static inline void kmalloc_percpu_init(void) { }
+
+#endif /* CONFIG_SMP */
+
+/* Use these with kmalloc_percpu */
+#define get_cpu_ptr(ptr) per_cpu_ptr(ptr, get_cpu())
+#define put_cpu_ptr(ptr) put_cpu()
+
 #endif /* __LINUX_PERCPU_H */

diff -ruN linux-2.5.50/init/main.c kmalloc_percpu-2.5.50/init/main.c
@@ -423,6 +423,7 @@
 	page_address_init();
 	mem_init();
 	kmem_cache_sizes_init();
+	kmalloc_percpu_init();
 	pidhash_init();
 	pgtable_cache_init();
 	pte_chain_init();

diff -ruN linux-2.5.50/kernel/Makefile kmalloc_percpu-2.5.50/kernel/Makefile
@@ -4,7 +4,7 @@
 
 export-objs = signal.o sys.o kmod.o workqueue.o ksyms.o pm.o exec_domain.o \
 		printk.o platform.o suspend.o dma.o module.o cpufreq.o \
-		profile.o rcupdate.o intermodule.o
+		profile.o rcupdate.o intermodule.o percpu.o
 
 obj-y     = sched.o fork.o exec_domain.o panic.o printk.o profile.o \
 	    exit.o itimer.o time.o softirq.o resource.o \

@@ -13,7 +13,7 @@
 	    rcupdate.o intermodule.o extable.o
 
 obj-$(CONFIG_GENERIC_ISA_DMA) += dma.o
-obj-$(CONFIG_SMP) += cpu.o
+obj-$(CONFIG_SMP) += cpu.o percpu.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += ksyms.o module.o
 obj-$(CONFIG_KALLSYMS) += kallsyms.o

diff -ruN linux-2.5.50/kernel/ksyms.c kmalloc_percpu-2.5.50/kernel/ksyms.c
@@ -97,6 +97,10 @@
 EXPORT_SYMBOL(remove_shrinker);
 EXPORT_SYMBOL(kmalloc);
 EXPORT_SYMBOL(kfree);
+#ifdef CONFIG_SMP
+EXPORT_SYMBOL(kmalloc_percpu);
+EXPORT_SYMBOL(kfree_percpu);
+#endif
 EXPORT_SYMBOL(vfree);
 EXPORT_SYMBOL(__vmalloc);
 EXPORT_SYMBOL(vmalloc);

Well, they are similar, aren't they ? get_cpu_ptr() can just be thought of as the dynamic twin of get_cpu_var(). So, in that sense it seems ok to me.

The interlaced allocator allows you to save space when kmalloc_percpu() is used to allocate small objects. That is done by interlacing each CPU's copy of the objects just like the static per-cpu data area.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

hm. spose so.

Where in the kernel is such a large number of 4-, 8- or 16-byte objects being used?

The slab allocator will support caches right down to 1024 x 4-byte objects per page. Why is that not appropriate?

If it is for locality-of-reference between individual objects then where in the kernel is this required, and are performance measurements available? It is very unusual to have objects which are so small, and a better design would be to obtain the locality of reference by aggregating the data into an array or structure.

Sorry, but you have what is basically a brand new allocator in there, and we need a very good reason for including it. I'd like to know what that reason is, please.

I will argue not on the frequency of calls but on the preciousness of space; highmem feels very serious pain when internal fragmentation of pinned pages occurs (which this is designed to prevent). I don't have direct experience with this patch/API, but I can say that fragmentation in ZONE_NORMAL is deadly (witness pagetable occupancy vs. ZONE_NORMAL consumption, which motivated highpte, despite my pagetable reclamation smoke blowing).

Bill

Hi Andrew,

Well, kernel objects may not be that small, but one would expect the per-cpu parts of the kernel objects to be sometimes small, often down to a couple of counters counting statistics.

Well, if you allocated 4-byte objects directly from the slab allocator, you aren't guranteed to *not* share a cache line with another object modified by a different cpu.

The reason is concern about per-cpu allocation for small per-CPU parts (typically counters) of objects. If a driver has two counters counting reads and writes, you don't want to eat up a whole cacheline for them for each CPU per instance of the device.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

Doesn't your allocator increase chances of cache conflict on the same cpu ?

This is so; I'm personally far more concerned about ZONE_NORMAL space consumption in the cacheline aligned case.

Bill

You mean by increasing the footprint and the chance of eviction ? It is a compromise. Or you would face NR_CPUS bloat and non-NUMA-node-local accesses for all CPUs outside the NUMA node where your NR_CPUS array is located.

Thanks

Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
Linux Technology Center, IBM Software Lab, Bangalore, India.

What do you base the trade-off decision on?

---------------------------------------------------------
Victor Yodaiken 
Finite State Machine Labs: The RTLinux Company.
www.fsmlabs.com  www.rtlinux.com
1+ 505 838 9109

Sorry, "one would expect" is not sufficient grounds for incorporation of a new allocator. As far as I can tell, all the proposed users are in fact allocating decent-sized aggregates, and that will remain the usual case.

The code exists, great. We can pull it in when there is a demonstrated need for it. But until that need is shown, this is overdesign.

If that's a problem it can be addressed in the slab head arrays - make sure that they are always filled and emptied in multiple-of-cacheline-sized units for objects which are smaller than a cacheline. That benefits all slab users.

I don't buy it.

- If the driver has two counters per device then the storage is infinitesimal.

- If it has multiple counters per device (always the case) then the driver will aggregate them anyway.

I am not aware of any situations in which a driver has a large (or even medium) number of small, discrete counters of this nature. Sufficiently large to justify a new allocator.

I'd suggest that you drop the new allocator until a compelling need for it (in real, live 2.5/2.6 code) has been demonstrated.

Fine with me since atleast one workaround for fragmentation with small allocations is known. I can't see anything in 2.5 timeframe requiring small per-cpu allocations.

Would you like me to resubmit a simple kmalloc-only version ?

Thanks
Dipankar

I think that would be best.

BTW, looking at the snmp application of this work:

+#define ICMP_INC_STATS_USER_FIELD(offt)                                \
+       (*((unsigned long *) ((void *)                                  \
+                            per_cpu_ptr(icmp_statistics[1],            \

+ smp_processor_id())) + offt))++;

This guy is racy on preempt. Just a little bit. It is effectively:

	ptr = per_cpu_ptr(...);
	(*ptr)++;

On some architectures, `(*ptr)++' is not atomic wrt interrupts. The CPU could be preempted midway through the increment.

Surely it's not an issue for SNMP stats, but for some applications such as struct page_state, such a permanent off-by-a-little-bit would be a showstopper.

So some big loud comments which describe the worthiness of get_cpu_ptr(), and the potential inaccuracy of per_cpu_ptr would be useful.

And as this is the first application of the kmalloc_precpu infrastructure, it may be best to convert it to use get_cpu_ptr/put_cpu_ptr.

Hi Andrew,
Sorry for the delayed response... I was out of station and couldn't reply earlier ....

The main objective of the interlaced allocator was cacheline utilisation more than main memory fragmentation (That has been my understanding at least). Without the interlaced allocator, we'd just pad up data and lose precious cacheline space. If you have a general purpose object allocator, one would want objects in different cachelines as kmalloc does, but that is not the case for kmalloc_percpu users. If obj A and obj B exists on the same cacheline, atleast objB does not take another cacheline...If you hit objB after objA, you gain, but if you don't, you don't lose.

As for the object sizes
1. We are assuming 32 bytes cachelines in this thread I suppose But ppc64 has a 128 byte cacheline and s390 a 256 byte Jumbo cacheline. I guess with larger cacheline sizes you have lesser no of cachelines -- makes cachelines all the more precious. (Right now, I am speaking in ignorance of the ppc64 and s390 cache architectures .. I can just see L1_CACHE_SHIFT in the kernel sources). So wouldn't interlaced allocations help these archs .. even when you have 64 bytes big objects?

2. When we have a case for data structures to be per-cpued, not all the members will be frequently modified or 'bouncy'... say if you take netdevice stats, rx and tx counters are likely to be hot and bouncy....and others not that hot... making the whole structure per-cpu might not be good, but we did not have
a clean workaround until kmalloc_percpu. So when you start identifying hot objects in these data structures, and making per-cpu objects only of hot objects, your object size
tends to go down .. making a case for the interlaced allocator ..... This capability is not possible without the interlaced allocator no?

Does this make a reasonable case for interlaced allocator now? (Of course, blklist init in the patch has to be modified to create blklists for objects of size 4, 8 .... SMP_CACHE_BYTES/2)

Thanks,
Kiran

You're assuming that the slab allocator always returns cachesize-padded objects. It does not have to do that. It can return 4-byte-sized and -aligned objects if you ask it to.

Oh I can see the benefits, but they appear to be rather theoretical.

I'm just applying some pressure here against adding another allocator unless it is really needed. On principle.

A slab cache of 4-byte objects will tend to give you what you want anyway, due to the batch filling and freeing of the head arrays. If that is proven to be insufficient then it would be better to put development effort into strengthening slab, rather than competely bypassing it.

(And a really simple solution would be to create a separate slab cache per cpu...)

You're assuming that the slab allocator always returns cachesize-padded objects. It does not have to do that. It can return 4-byte-sized and -aligned objects if you ask it to.

Oh I can see the benefits, but they appear to be rather theoretical.

I'm just applying some pressure here against adding another allocator unless it is really needed. On principle.

A slab cache of 4-byte objects will tend to give you what you want anyway, due to the batch filling and freeing of the head arrays. If that is proven to be insufficient then it would be better to put development effort into strengthening slab, rather than competely bypassing it.

(And a really simple solution would be to create a separate slab cache per cpu...)