Staging: xvmalloc memory allocator
authorNitin Gupta <ngupta@vflare.org>
Tue, 22 Sep 2009 04:56:52 +0000 (10:26 +0530)
committerGreg Kroah-Hartman <gregkh@suse.de>
Fri, 11 Dec 2009 20:23:04 +0000 (12:23 -0800)
commit644bf7b5983cf2540b57a5b25b775cb3c1e8e943
tree011667c2bd293164205fd83180517ba552283e2e
parentefdf83c1763156220a74c8f2755c1a6fa1e1c26b
Staging: xvmalloc memory allocator

* Features:
 - Low metadata overhead (just 4 bytes per object)
 - O(1) Alloc/Free - except when we have to call system page allocator to
   get additional memory.
 - Very low fragmentation: In all tests, xvmalloc memory usage is within 12%
   of "Ideal".
 - Pool based allocator: Each pool can grow and shrink.
 - It maps pages only when required. So, it does not hog vmalloc area which
   is very small on 32-bit systems.

SLUB allocator could not be used due to fragmentation issues:
http://code.google.com/p/compcache/wiki/AllocatorsComparison
Data here shows kmalloc using ~43% more memory than TLSF and xvMalloc
is showed ~2% more space efficiency than TLSF (due to smaller metadata).
Creating various kmem_caches can reduce space efficiency gap but still
problem of being limited to low memory exists. Also, it depends on
allocating higher order pages to reduce fragmentation - this is not
acceptable for ramzswap as it is used under memory crunch (its a swap
device!).

SLOB allocator could not be used do to reasons mentioned here:
http://lkml.org/lkml/2009/3/18/210

* Implementation:
It uses two-level bitmap search to find free list containing block of
correct size. This idea is taken from TLSF (Two-Level Segregate Fit)
allocator and is well explained in its paper (see [Links] below).

* Limitations:
 - Poor scalability: No per-cpu data structures (work in progress).

[Links]
1. Details and Performance data:
http://code.google.com/p/compcache/wiki/xvMalloc
http://code.google.com/p/compcache/wiki/xvMallocPerformance

2. TLSF memory allocator:
home: http://rtportal.upv.es/rtmalloc/
paper: http://rtportal.upv.es/rtmalloc/files/MRBC_2008.pdf

Signed-off-by: Nitin Gupta <ngupta@vflare.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@suse.de>
drivers/staging/ramzswap/xvmalloc.c [new file with mode: 0644]
drivers/staging/ramzswap/xvmalloc.h [new file with mode: 0644]
drivers/staging/ramzswap/xvmalloc_int.h [new file with mode: 0644]