Reimplementation of linux dynamic percpu memory allocator
Hi kiran,
Quoted 6 lines
+ *
+ * Originally by Dipankar Sarma and Ravikiran Thirumalai,
+ * This reimplementsalloc_percputo make it
+ * 1. Independent of slab/kmalloc
Probably the right approach. slab should use per-cpu for it's internal head arrays, but I've never converted the slab code due to chicken-and-egg problems and due to the additional pointer dereference.
Quoted 4 lines
+ * Allocator is slow -- expected to be called during module/subsytem
+ * init.alloc_percpucan block.
How slow is slow?
I think the block subsystem uses alloc_percpu for some statistics counters, i.e. one alloc during creation of a new disk. The slab implementation was really slow and that caused problems with LVM (or something like that) stress tests.
Review
Quoted 11 lines
(quoted diff) +9
-0+ /* Map pages for each cpu by splitting vm_struct for each cpu */ + for (i = 0; i < NR_CPUS; i++) { + if (cpu_possible(i)) { + tmppage = &blkp->pages[i*cpu_pages]; + tmp.addr = area->addr + i * PCPU_BLKSIZE; + /* map_vm_area assumes a guard page of size PAGE_SIZE */ + tmp.size = PCPU_BLKSIZE + PAGE_SIZE; + if (map_vm_area(&tmp, PAGE_KERNEL, &tmppage)) + goto fail_map;
That means no large pte entries for the per-cpu allocations, right?
I think that's a bad idea for non-numa systems. What about a fallback to simple getfreepages() for non-numa systems?
Quoted 5 lines
+ * This allocator is slow as we assume allocs to come
+ * by during boot/module init.
+ * Should not be called from interrupt context
"Must not" - it contains down() and thus can sleep.
--
Manfred
Quoted 10 lines · Manfred Spraul
Quoted 1 line
Probably the right approach. slab should use per-cpu for it's internal head arrays, but I've never converted the slab code due to chicken-and-egg problems and due to the additional pointer dereference.
Quoted 4 lines
+ * Allocator is slow -- expected to be called during module/subsytem
+ * init.alloc_percpucan block.How slow is slow?
Haven't measured it, but the allocator is not designed for speed. Once the block to be alloced from is identified, the allocator builds and sorts a map of objects in ascending order so that we allocate from the smallest chunk. Goal is to enhance memory/cacheline utlization and reduce fragmentation rather than speed. It is not expected that the allocator will be used from the fastpath.
Quoted 4 lines
I think the block subsystem uses
alloc_percpufor some statistics counters, i.e. one alloc during creation of a new disk. The slab implementation was really slow and that caused problems with LVM (or something like that) stress tests.
Hmmm..I knew from some experiments earlier that access to per cpu versions of memory was slow with the slab based implementation -- which this patch addresses, but I didn't know allocs themselves were slow... Creation of a disk should not be a fast path no?
Quoted 16 lines
Review
Quoted 13 lines
(quoted diff) +6
-0+ /* Map pages for each cpu by splitting vm_struct for each cpu */ + for (i = 0; i < NR_CPUS; i++) { + if (cpu_possible(i)) { + tmppage = &blkp->pages[i*cpu_pages]; + tmp.addr = area->addr + i * PCPU_BLKSIZE; + /* map_vm_area assumes a guard page of size
PAGE_SIZE*/(quoted diff) +3
-0+ tmp.size = PCPU_BLKSIZE + PAGE_SIZE; + if (map_vm_area(&tmp, PAGE_KERNEL, &tmppage)) + goto fail_map;That means no large pte entries for the per-cpu allocations, right? I think that's a bad idea for non-numa systems. What about a fallback to simple
getfreepages()for non-numa systems?
Can we have large pte entries with PAGE_SIZEd pages?
Quoted 7 lines
Quoted 5 lines
+ * This allocator is slow as we assume allocs to come
+ * by during boot/module init.
+ * Should not be called from interrupt context"Must not" - it contains
down()and thus can sleep.
:D Yes will replace 'should not' with 'must not' in my next iteration.
Thanks for the comments and feedback.
Kiran
Quoted 6 lines · Ravikiran G Thirumalai
Hmmm..I knew from some experiments earlier that access to per cpu versions of memory was slow with the slab based implementation -- which this patch addresses, but I didn't know allocs themselves were slow... Creation of a disk should not be a fast path no?
No, not fast path. But it can happen a few thousand times. The slab implementation failed due to heavy internal fragmentation. If your code runs fine with a few thousand users, then there shouldn't be a problem.
Quoted 11 lines
Quoted 6 lines
Quoted 2 lines
That means no large pte entries for the per-cpu allocations, right?
I think that's a bad idea for non-numa systems. What about a fallback to simplegetfreepages()for non-numa systems?Can we have large pte entries with
PAGE_SIZEdpages?
For non-NUMA systems, I would use get_free_pages() to allocate a multi-page area instead of map_vm_area(). Typically, get_free_pages() is backed by large pte memory and map_vm_area() by normal virtual memory.
--
Manfred
Quoted 4 lines · Manfred Spraul
Quoted 1 line
No, not fast path. But it can happen a few thousand times. The slab implementation failed due to heavy internal fragmentation. If your code runs fine with a few thousand users, then there shouldn't be a problem.
If there is a stress test I can use, I can try running it.
Quoted 5 lines
Quoted 2 lines
Quoted 1 line
Quoted 1 line
..
For non-NUMA systems, I would use
get_free_pages()to allocate a multi-page area instead ofmap_vm_area(). Typically,get_free_pages()is backed by large pte memory andmap_vm_area()by normal virtual memory.
Hmm...the arithmetic becomes tricky then. Right now I allocate NR_CPUS * PCU_BLOCKSIZE + BLOCK_MANAGEMENT_SIZE amount of KVA for a block, allocate pages for cpu_possible cpus and map corresponding va space with allocated pages using map_vm_area. We may fragment if NR_CPUS * PCPU_BLOCKSIZE doesn't fit into a proper page order, also we'd be wasting pages for !cpu_possible(cpus) of NR_CPUS
Thanks,
Kiran
Quoted 9 lines · Ravikiran G Thirumalai
Quoted 3 lines · Manfred Spraul
No, not fast path. But it can happen a few thousand times. The slab implementation failed due to heavy internal fragmentation. If your code runs fine with a few thousand users, then there shouldn't be a problem.
Could you ask Badari Pulavarty ([email protected])?
He noticed the fragmentation problem with the original kmem_cache_alloc_node implementation. Perhaps he could just run your version with his test setup:
The thread with the fix is at:
http://marc.theaimsgroup.com/?t=109735434400002&r=1&w=2
--
Manfred
Quoted 13 lines · Manfred Spraul
Quoted 11 lines · Ravikiran G Thirumalai
Quoted 5 lines · Manfred Spraul
No, not fast path. But it can happen a few thousand times. The slab implementation failed due to heavy internal fragmentation. If your code runs fine with a few thousand users, then there shouldn't be a problem.
Quoted 4 lines
Could you ask Badari Pulavarty ([email protected])?
He noticed the fragmentation problem with the originalkmem_cache_alloc_nodeimplementation. Perhaps he could just run your version with his test setup:
Yes I will. Thanks for the pointer.
Thanks,
Kiran
Quoted 11 lines · Manfred Spraul
Quoted 1 line · Ravikiran G Thirumalai
Could you ask Badari Pulavarty ([email protected])?
He noticed the fragmentation problem with the originalkmem_cache_alloc_nodeimplementation. Perhaps he could just run your version with his test setup:
The thread with the fix is at:
Manfred,
Badari's test was to create thousands of scsi devices with scsi_debug on a multiprocessor x86_64 box with CONFIG_NUMA.
I tried out something similar -- create 2000 scsi disks on 2 way x86_64 box. Here are the results; All numbers in kB from /proc/meminfo.
1) Without your patch to reduce fragmentation due to kmem_cache_alloc_node:
Before After disk Difference disks creation ----------------------------------
MemTotal 5009956 5009956 0
MemFree 4949428 4868300 81128
2) With your patch to reduce fragmentation due to kmem_cache_alloc_node:
Before After disk Difference disks creation ----------------------------------
MemTotal 5009956 5009956 0
MemFree 4947380 4874876 72504
3) With the new alloc_percpu implementation which does not use slab:
Before After disk Difference disks creation ----------------------------------
MemTotal 5009956 5009956 0
MemFree 4923244 4851648 71596
As you can see, the alloc_percpu reimplementation doesn't fragment.
Also, I'd ran some user space stress tests to check the allocator's utilization levels. I reran them and here's the result:
A) Test description and results for a 'counters only' test run:
With a block size of 8192 bytes,
1. Allocate 2000 4 byte counters
At the end of allocation, 1 8192byte block exists with a usecount of 8000
2. Free a random number of objects in random order. After freeing 3992 bytes of memory, one block exists in the allocator with a usecount of 4008
3. Allocate 2000 4 byte counters again
At the end of allocation 2 blocks exists with usecounts of 8192 and 3816
4. Free all remaining objects
All objects go away and the allocator doesn't have any blocks left
B) Test description and results for a 'random sized objects' test run:
With a block size of 8192 bytes,
1. Allocate 2000 random sized objects with random alignment specifications At the end of allocation, 504 8192byte blocks exist in the system after allocating 4076556 bytes of objects -- with 98.7 % utilization
2. Free a random number of objects in random order.
After freeing 2020220 bytes of memory, 458 blocks exist. Utilization is 2056336/3751936 -- 54.8 %
3. Allocate 2000 random sized objects as in step 1 again After adding 4155972 bytes of objects, 772 blocks summing up to 6324224 bytes exist in the allocator. objects adding up to 6212308 bytes have been allocated, which means a utilization level of 98.2 %.
I guess this proves that the allocator behaves quite well in terms of fragmentation.
Thanks,
Kiran