[Xen-devel] [RFC] Replacing Xen's xmalloc engine and(?) API

[Dan Magenheimer <dan.magenheimer@xxxxxxxxxx>]

Xen hypervisor experts --

I'm looking at replacing the engine of Xen's xmalloc/xfree
(dynamic memory allocation) with a low fragmentation, fixed
overhead dynamic allocator called TLSF ("two-level sequential
fit").  TLSF info can be found here:

http://rtportal.upv.es/rtmalloc/

TLSF has been modified to work with Linux and for an unlimited
collection of page-sized regions by Nitin Gupta here:

http://code.google.com/p/compcache/wiki/TLSFAllocator

The code I started with (thanks Nitin!) is here:

http://code.google.com/p/compcache/source/browse/trunk/sub-projects/allocators/tlsf-kmod

(Note that a lot of this code can be stripped out for Xen.)

Xen's current xmalloc engine (essentially a first-fit algorithm) is
adequate for current needs, but I'm working on a project (see
"Paravirtualized Paging" at WIOV in December) that emphasizes its
weaknesses, the largest being that maximum calltime is essentially
unbounded, especially when allocating a large number of near-page-sized
items.  (I'm measuring millions of cycles to do some xfree's.) Another
project that may soon make it into Xen (see "Difference Engine" at
OSDI in December) has similarly intense near-page-sized needs.

Anyway, I've hacked a version of TLSF into Xen, enough to meet
my needs for now, but one of the xmalloc weaknesses (from my pov
anyway) is built into the API: xmalloc'ing a page actually
allocates two contiguous pages, xmalloc'ing two pages actually
allocates four and so on.  Worse, xmalloc'ing slightly LESS than
a page, actually allocates two contiguous pages, etc., because
the current mechanism requires space for a block header.

As a result, I'd like to propose a change to the xmalloc interface
to make this issue more explicit:  I'd like to change xmalloc/xfree
to FAIL on allocation sizes greater than PAGE_SIZE - DELTA, where
DELTA is a defined constant.   Callers that require an allocation
larger than that MUST use the page_alloc (and corresponding
page_free) interfaces.  In other words, for any dynamic allocation
code that needs a dynamically computed size that might exceed a
page, the test must be done on the caller-side... and the caller
is responsible for remembering whether the subpage allocator or
the page-plus allocator was used, and free'ing with the matching
subpage-free or page-plus-free routine.  While I'd never propose
this unforgiving API for user-land code, I think it isn't unreasonable
in a hypervisor.

One compromise might be to retain the existing interface for
xmalloc_array() as calls to that routine are much more likely
to exceed a page.

Another might be to retain the existing xmalloc interface...
and maybe even the existing engine... but supplement it with
a new xmalloc_subpage() interface and change caller-side code
over time to use the new interface(/engine).

Comments?  (on both the API proposal and the engine)

Thanks,
Dan


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