Dynamic percpu data allocator

If static percpu area is around, can dynamic percpu data allocator be far behind ;-)

As a part of scalable kernel primitives work for higher-end SMP and NUMA architectures, we have been seeing increasing need for per-cpu data in various key areas. Rusty's percpu area work has added a way in 2.5 kernels to maintain static per-cpu data. Inspired by that work, I have implemented a dynamic per-cpu data allocator. Currently it is useful to us for -

1. Per-cpu data in dynamically allocated structures.
2. per-cpu statistics and reference counters
3. Per-cpu data in drivers/modules.
4. Scalable locking primitives like local spin only locks (or even big reader locks).

Included in this mail is a document that describes the allocator. I would really appreciate if people comment on it. I am particularly interested in eek-value of the interfaces, specially the bit about keeping the type information in a dummy variable in a union.

The actual patch will follow soon, unless someone convince me quickly that there is an saner way to do this.

Thanks

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

Per-CPU Data Allocator
----------------------

Interfaces
----------

The interfaces for per-cpu data allocator are similar to Rusty's static per-CPU data interfaces. One clear goal was to make sure that they leave no overhead in the UP kernels, so for UP kernels they reduce to ordinary variables. The basic interfaces are these -

1. percpu_data_declare(type,var)
2. percpu_data_alloc(var)
3. percpu_data(var,cpu)
4. this_percpu_data(var)
5. percpu_data_free(var)

For example, we can declare the following structure -

	struct yy {
		int a;
		percpu_data_declare(int, b);
		int c;
		int d;
	};

We can allocate memory for percpu int like this -

	struct yy y;

	if (percpu_data_alloc(y.b)) {
		/* Failed */
	}

To use it -

	cpu = smp_processor_id();
	percpu_data(y.b, cpu)++;

	or

	this_percpu_data(y.b)++;

To free the per-CPU data

	percpu_data_free(y.b);

The data declaration interface is a bit unnatural, but I can't think of anything better that would let me preserve the type information for the original variable so that appropriate typecasting can be done for other interfaces. percpu_data_declare(type,var) expands to -

	union {
		percpu_data_t *percpu;
		typeof(type) realtype;
	} var

percpu_data_t maintains the pointers necessary to lookup the real percpu data.

	typedef struct {
		void *blkaddrs[NR_CPUS];
		struct percpu_data_blk *blkp;
	} percpu_data_t;

The type information is used (using typeof()) to
typecast data accesses.

	#define percpu_data(var,cpu) \
			(*((typeof(var.realtype) *)var.percpu->blkaddrs[cpu]))

Using a pointer to percpu_data_t adds
an overhead of an additional memory reference while accessing percpu data. This can be avoided by embedding the percpu_data_t structure, but since percpu_data_t has an NR_CPUS array, it changes structure sizes very radically. It is a tradeoff, we could go either way.

Potential Uses
--------------

1. Scalable counters - they already use a scaled down version of the allocator inside. Per-cpu counters can reduce the overhead of cacheline bouncing.

2. Big reader lock - this need not be statically allocated anymore.

3. Per-CPU data in modules - the static per-cpu scheme by Rusty's doesn't work in modules, atleast I haven't seen a way to do this.

4. Scalable locks - per-cpu data is commonly used in scalable locks like MCS locks.

Allocator
---------

The current approach is that unless there is interest in a dynamic percpu data allocator, there is no point in spending too much time in writing a sophisticated.

Allocation Policy
-----------------

1. If the allocation requests size is a factor of SMP_CACHE_BYTES, then it will be interleaved to avoid fragmentation as much as possible. If the request size is a multiple of SMP_CACHE_BYTES, fragmentation will still be avoided. Anything else will result in fragmentation. The current allocator doesn't make any attempt to use the fragmented portion, in a sense it is like padding to cache line boundary.

2. A simple binary search tree is used to maintain the memory objects (could be blocks of them) of different sizes. For interleaving, the objects are maintained in blocks and a freelist mechanism similar to the slab allocator is used within the blocks to allocates objects from within. Each block is allocated from kmem_cache.

If there is sufficient interest in the per-cpu data allocator, then I will revisit the allocator and see if fragmentation can be reduced for non-multiples/non-factors of SMP_CACHE_BYTES.

For non-factor allocations, the residual part of the cache-line can be maintained and a best-factor-fit alogorithm can be used to allocate this. This makes an assumption that kernel allocation requests are likely to contain repetitive patterns of similar sizes.

Alignment Issues
----------------

The current alignment strategy is this -

1. Minimum allocation size is sizeof(int).
2. Each block is aligned to cache line boundary and size of any object allocated within the block is either a factor of the block size or equal to the block size. However I am not sure if this guarantees proper alignment on all architectures. We need to investigate some more about this.

I am sure there is a 69-bit transputer architecture somewhere that breaks this allocator ;-)

Hello, Dipankar,

I would prefer to use the existing slab allocator for this. I am not sure if I understand your requirements for the per-cpu allocator correctly, please correct me if I do not.

What I would like to see

1. Have per-cpu slabs instead of per-cpu cpucache_t. One should be able to tell for which caches we want per-cpu slabs. This way we can make even kmalloc per-cpu. Since most of the kernel would use and dispose memory before they migrate across cpus. I think this would be useful, but again no data to back it up.

2. I hate the use of NR_CPUS. If I compiled an SMP kernel on a two CPU machine, I still end up with support for 32 CPUs. What I would like to see is that in new kernel code, we should use treat equivalent classes of CPUs as belonging to the same CPU. For example

   void *blkaddrs[NR_CPUS];

while searching, instead of doing

blkaddrs[smp_processor_id()], if the slot for smp_processor_id() is full, we should look through

for (i = 0; i < NR_CPUS; i++) {
look into blkaddrs[smp_processor_id() + i % smp_number_of_cpus()(or
whatever)]
if successful break
}

On a two CPU system 1,3,5 ... belong to the same equivalent class. So we might
as well utilize them. Even with a per-cpu pool, threads could use the slots in
the per-cpu equivalent classes in parallel (I have a very rough idea about this).

Does any of this make sense,
Balbir

|-----Original Message-----
|From: [email protected]
|[mailto:[email protected]]On Behalf Of Dipankar Sarma
|Sent: Thursday, May 23, 2002 6:39 PM
|To: [email protected]
|Cc: Rusty Russell; Paul McKenney; [email protected]
|Subject: [RFC] Dynamic percpu data allocator
|
|
|If static percpu area is around, can dynamic percpu data allocator
|be far behind ;-)
|
|As a part of scalable kernel primitives work for higher-end SMP
|and NUMA architectures, we have been seeing increasing need
|for per-cpu data in various key areas. Rusty's percpu area
|work has added a way in 2.5 kernels to maintain static per-cpu
|data. Inspired by that work, I have implemented a dynamic per-cpu
|data allocator. Currently it is useful to us for -
|
|1. Per-cpu data in dynamically allocated structures.
|2. per-cpu statistics and reference counters
|3. Per-cpu data in drivers/modules.
|4. Scalable locking primitives like local spin only locks
|   (or even big reader locks).
|
|Included in this mail is a document that describes the allocator.
|I would really appreciate if people comment on it. I am
|particularly interested in eek-value of the interfaces,
|specially the bit about keeping the type information in
|a dummy variable in a union.
|
|The actual patch will follow soon, unless someone convince
|me quickly that there is an saner way to do this.
|
|Thanks
|--
|Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
|Linux Technology Center, IBM Software Lab, Bangalore, India.
|

**************************Disclaimer************************************

Information contained in this E-MAIL being proprietary to Wipro Limited is 'privileged' and 'confidential' and intended for use only by the individual
or entity to which it is addressed. You are notified that any use, copying
or dissemination of the information contained in the E-MAIL in any manner whatsoever is strictly prohibited.

***************************************************************************

Allocating cpu-local memory is a different issue altogether. Eventually for NUMA support, we will have to do such allocations that supports choosing memory closest to a group of CPUs.

The per-cpu data allocator allocates one copy for *each* CPU. It uses the slab allocator underneath. Eventually, when/if we have per-cpu/numa-node slab allocation, the per-cpu data allocator can allocate every CPU's copy from memory closest to it.

I suppose you worked on DYNIX/ptx ? Think of this as dynamic plocal.

If you don't like it, just define NR_CPUS to 2 and recompile.

How will it work ? You could be accessing memory beyond blkaddrs[].

I use NR_CPUS for allocations because if I don't, supporting CPU hotplug will be a nightmare. Resizing so many data structures is not an option. I believe Rusty and/or cpu hotplug work is adding a for_each_cpu() macro to walk the CPUs that take care of everything including sparse CPU numbers. Until then, I would use for (i = 0; i < smp_num_cpus; i++).

Thanks

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

In an SMP system, the entire memory is equidistant from the CPUs. So, any memory that is exclusively accessed by once cpu only is CPU-local. On a NUMA machine however that isn't true, so you need special schemes.

The thing about one-copy-per-cpu allocator that I describe is that it interleaves per-cpu data to save on space. That is if you allocate per-cpu ints i1, i2, it will be laid out in memory like this -

CPU #0 CPU#1

--------- --------- Start of cache line
i1 i1
i2 i2

   .               .
   .               .
   .               .
   .               .
   .               .

--------- ---------- End of cache line

The per-cpu copies of i1 and i2 for CPU #0 and CPU #1 are allocated from different cache lines of memory, but copy of i1 and i2 for CPU #0 are in the same cache line. This interleaving saves space by avoiding the need to pad small data structures to cache line sizes. This essentially how the static per-cpu data area in 2.5 kernel is laid out in memory. Since copies for CPU #0 and CPU #1 for the same variable are on different cache lines, assuming that code that accesses "this" CPU's copy will not result in cache line bouncing. On an SMP machine, I can allocate the cache lines for different CPUs, where the interleaved data structures are laid out, using the slab allocator. On a NUMA machine however, I would want to make sure that cache line allocated for this purpose for CPU #N is closest possible to CPU #N.

Thanks

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

Thanks, when I ment CPU local memory on SMP, I ment CPU cache. Sorry for the confusion. I think your dynamic allocator makes sense.

Balbir

|
|On Fri, May 24, 2002 at 02:08:50PM +0530, BALBIR SINGH wrote:
|> 
|> Sure, I understand what you are talking about now. That makes a lot
|> of sense, I will go through your document once more and read it.
|> I was thinking of the two combined (allocating CPU local memory
|> for certain data structs also includes allocating one copy per CPU).
|> Is there a reason to delay the implementation of CPU local memory,
|> or are we waiting for NUMA guys to do it? Is it not useful in an
|> SMP system to allocate CPU local memory?
|
|In an SMP system, the entire memory is equidistant from the CPUs.
|So, any memory that is exclusively accessed by once cpu only
|is CPU-local. On a NUMA machine however that isn't true, so
|you need special schemes.
|
|The thing about one-copy-per-cpu allocator that I describe is that
|it interleaves per-cpu data to save on space. That is if you
|allocate per-cpu ints i1, i2, it will be laid out in memory like this -
|
|   CPU #0          CPU#1
|
| ---------       ---------         Start of cache line
|   i1              i1
|   i2              i2 
|
|   .               .
|   .               .
|   .               .
|   .               .
|   .               .
|
| ---------       ----------        End of cache line
|
|The per-cpu copies of i1 and i2 for CPU #0 and CPU #1 are allocated from 
|different cache lines of memory, but copy of i1 and i2 for CPU #0 are
|in the same cache line. This interleaving saves space by avoiding
|the need to pad small data structures to cache line sizes.
|This essentially how the static per-cpu data area in 2.5 kernel
|is laid out in memory. Since copies for CPU #0 and CPU #1 for
|the same variable are on different cache lines, assuming that
|code that accesses "this" CPU's copy will not result in cache line
|bouncing. On an SMP machine, I can allocate the cache lines
|for different CPUs, where the interleaved data structures are
|laid out, using the slab allocator. On a NUMA machine however,
|I would want to make sure that cache line allocated for this
|purpose for CPU #N is closest possible to CPU #N.
|
|
|Thanks
|-- 
|Dipankar Sarma  <[email protected]> http://lse.sourceforge.net
|Linux Technology Center, IBM Software Lab, Bangalore, India.
|-
|To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
|the body of a message to [email protected]
|More majordomo info at  http://vger.kernel.org/majordomo-info.html
|Please read the FAQ at  http://www.tux.org/lkml/

**************************Disclaimer************************************

Information contained in this E-MAIL being proprietary to Wipro Limited is 'privileged' and 'confidential' and intended for use only by the individual
or entity to which it is addressed. You are notified that any use, copying
or dissemination of the information contained in the E-MAIL in any manner whatsoever is strictly prohibited.

***************************************************************************

|> Hello, Dipankar,
|>
|> I would prefer to use the existing slab allocator for this.
|> I am not sure if I understand your requirements for the per-cpu
|> allocator correctly, please correct me if I do not.
|>
|> What I would like to see
|>
|> 1. Have per-cpu slabs instead of per-cpu cpucache_t. One should
|>    be able to tell for which caches we want per-cpu slabs. This
|>    way we can make even kmalloc per-cpu. Since most of the kernel
|>    would use and dispose memory before they migrate across cpus.
|>    I think this would be useful, but again no data to back it up.
|
|Allocating cpu-local memory is a different issue altogether.
|Eventually for NUMA support, we will have to do such allocations
|that supports choosing memory closest to a group of CPUs.
|
|The per-cpu data allocator allocates one copy for *each* CPU.
|It uses the slab allocator underneath. Eventually, when/if we have
|per-cpu/numa-node slab allocation, the per-cpu data allocator
|can allocate every CPU's copy from memory closest to it.
|
|I suppose you worked on DYNIX/ptx ? Think of this as dynamic
|plocal.

Sure, I understand what you are talking about now. That makes a lot of sense, I will go through your document once more and read it. I was thinking of the two combined (allocating CPU local memory for certain data structs also includes allocating one copy per CPU). Is there a reason to delay the implementation of CPU local memory, or are we waiting for NUMA guys to do it? Is it not useful in an SMP system to allocate CPU local memory?

|
|>
|> 2. I hate the use of NR_CPUS. If I compiled an SMP kernel on a two
|>    CPU machine, I still end up with support for 32 CPUs. What I would
|
|If you don't like it, just define NR_CPUS to 2 and recompile.
|

That does make sense, but I would like to keep my headers in sync, so that all patches apply cleanly.

|
|>    like to see is that in new kernel code, we should use treat equivalent
|>    classes of CPUs as belonging to the same CPU. For example
|>
|>    void *blkaddrs[NR_CPUS];
|>
|>    while searching, instead of doing
|>
|>    blkaddrs[smp_processor_id()], if the slot for
|smp_processor_id() is full,
|>    we should look through
|>
|>    for (i = 0; i < NR_CPUS; i++) {
|>      look into blkaddrs[smp_processor_id() + i % smp_number_of_cpus()(or
|> whatever)]
|>      if successful break
|>    }
|
|How will it work ? You could be accessing memory beyond blkaddrs[].
|

Sorry that could happen, it should be (smp_processor_id + i) % smp_number_of_cpus().

|I use NR_CPUS for allocations because if I don't, supporting CPU
|hotplug will be a nightmare. Resizing so many data structures is
|not an option. I believe Rusty and/or cpu hotplug work is
|adding a for_each_cpu() macro to walk the CPUs that take
|care of everything including sparse CPU numbers. Until then,
|I would use for (i = 0; i < smp_num_cpus; i++).

I think that does make a whole lot of sense, I was not thinking about HotPluging CPUs (dumb me).

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

**************************Disclaimer************************************

Information contained in this E-MAIL being proprietary to Wipro Limited is 'privileged' and 'confidential' and intended for use only by the individual
or entity to which it is addressed. You are notified that any use, copying
or dissemination of the information contained in the E-MAIL in any manner whatsoever is strictly prohibited.

***************************************************************************

That should be pretty easy to do now, if I understand what you're asking for ... when you allocate the area for cpu N, just do alloc_pages_node (cpu_to_nid(smp_processor_id())) or something similar.

M.