Xen devel - Oct 2008 - [PATCH] use tlsf for xmalloc engine

This patch replaces the Xen xmalloc engine with tlsf, an allocation
engine that is both more space efficient and time-bounded, especially
for allocation sizes between PAGE_SIZE/2 and PAGE_SIZE.

The file xmalloc.c is deprecated but not yet deleted.  A simple
switch of a comment line in common/Makefile will change back
to the legacy xmalloc/xfree if needed for testing.

Code adapted from Nitin Gupta''s tlsf-kmod, rev 229, found here:
http://code.google.com/p/compcache/source/browse/trunk/sub-projects/allocators/tlsf-kmod
with description and performance details here:
http://code.google.com/p/compcache/wiki/TLSFAllocator
(new Xen code uses 4K=PAGE_SIZE for the region size)

For detailed info on tlsf, see:
http://rtportal.upv.es/rtmalloc/

(NOTE to Isaku-san: There may be some subtle alignment or PAGE_SIZE
issues to get tlsf to work on ia64.  I have not tried it.
If problems, use an ifdef in common/Makefile to change to
the legacy xmalloc on ia64.)

Signed-off by: Dan Magenheimer <dan.magenheimer@oracle.com>

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On Wed, Oct 15, 2008 at 02:03:34PM -0700, Dan Magenheimer
wrote:
> This patch replaces the Xen xmalloc engine with tlsf, an allocation
> engine that is both more space efficient and time-bounded, especially
> for allocation sizes between PAGE_SIZE/2 and PAGE_SIZE.
> 
> The file xmalloc.c is deprecated but not yet deleted.  A simple
> switch of a comment line in common/Makefile will change back
> to the legacy xmalloc/xfree if needed for testing.
> 
> Code adapted from Nitin Gupta''s tlsf-kmod, rev 229, found here:
>
http://code.google.com/p/compcache/source/browse/trunk/sub-projects/allocators/tlsf-kmod
> with description and performance details here:
> http://code.google.com/p/compcache/wiki/TLSFAllocator
> (new Xen code uses 4K=PAGE_SIZE for the region size)
> 
> For detailed info on tlsf, see:
> http://rtportal.upv.es/rtmalloc/
> 
> (NOTE to Isaku-san: There may be some subtle alignment or PAGE_SIZE
> issues to get tlsf to work on ia64.  I have not tried it.
> If problems, use an ifdef in common/Makefile to change to
> the legacy xmalloc on ia64.)
I did a very light test. It booted and pv domain and hvm domain can 
boot.
Looking at xmalloc use in ia64 specific code, it seems ok
to allow cache line size alignment at most.

Thank you for reminding me.
-- 
yamahata

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On 15/10/08 22:03, "Dan Magenheimer"
<dan.magenheimer@oracle.com> wrote:
> This patch replaces the Xen xmalloc engine with tlsf, an allocation
> engine that is both more space efficient and time-bounded, especially
> for allocation sizes between PAGE_SIZE/2 and PAGE_SIZE.
> 
> The file xmalloc.c is deprecated but not yet deleted.  A simple
> switch of a comment line in common/Makefile will change back
> to the legacy xmalloc/xfree if needed for testing.
Fixed for style, fixed to satisfy requested alignment parameter to
xmalloc(), and fixed for multi-page allocations to include the
BHDR_OVERHEAD. Checked in as c/s 18638.

 -- Keir



_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

> Checked in as c/s 18638.
Excellent!

However, I should have mentioned that I had a reason for exposing
the tlsf-direct (non-xmalloc) interface, which you have hidden by
static''izing some of the routines and removing xmalloc_tlsf.h:

The pool capability can be used to "group" allocated pages so as to
improve locality and reduce fragmentation (kind of similar to
slab/slub but across a wide range of allocation sizes). IOW,
if I want to allocate a large and diverse set of data structures
of types X, Y, and Z, and I can "partition" them into pools
A, B, and C, I should get fewer page translation misses when I walk
the A-specific data structures than if the allocations are all
done via xmalloc.  Further, if I free all of A''s data structures,
all the pages will be returned to the free page pool, whereas if
I use xmalloc/xfree, B''s and C''s allocations will be
intermingled
so many/most pages may not be freed.

Since you''ve retained the getmem/putmem function parameters and
struct pool parameter, this should be easy to patch later, but
please don''t specialize it further to meet only xmalloc''s
needs
as I intend to use pools in my current project (hcache).

Thanks,
Dan
> -----Original Message-----
> From: Keir Fraser [mailto:keir.fraser@eu.citrix.com]
> Sent: Thursday, October 16, 2008 4:12 AM
> To: Dan Magenheimer; Xen-Devel (E-mail)
> Cc: Diwaker Gupta; Isaku Yamahata; Kurt Hackel; Nitin Gupta
> Subject: Re: [Xen-devel] [PATCH] use tlsf for xmalloc engine
> 
> 
> On 15/10/08 22:03, "Dan Magenheimer" 
> <dan.magenheimer@oracle.com> wrote:
> 
> > This patch replaces the Xen xmalloc engine with tlsf, an allocation
> > engine that is both more space efficient and time-bounded, 
> especially
> > for allocation sizes between PAGE_SIZE/2 and PAGE_SIZE.
> > 
> > The file xmalloc.c is deprecated but not yet deleted.  A simple
> > switch of a comment line in common/Makefile will change back
> > to the legacy xmalloc/xfree if needed for testing.
> 
> Fixed for style, fixed to satisfy requested alignment parameter to
> xmalloc(), and fixed for multi-page allocations to include the
> BHDR_OVERHEAD. Checked in as c/s 18638.
> 
>  -- Keir
> 
> 
>
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel