RE: [RFC] Replacing Xen's xmalloc engine and(?) API

[Dan Magenheimer <dan.magenheimer@oracle.com>]

> > On 11/10/08 22:44, "Dan Magenheimer" 
> <dan.magenheimer@oracle.com> wrote:
> > 
> >> 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.
>
> This sounds crazy to me. xmalloc() should work like malloc().

While I agree completely in principle, abstractions can be costly.
In this case, the fact that xmalloc(PAGE_SIZE-1) actually uses
2*PAGE_SIZE of space (and fails even if there are lots of free
pages but no pair of contiguous pages) is an undocumented consequence
of the underlying implementation... which is not entirely
unreasonable in user-land but is IMHO questionable in the guts
of a hypervisor where memory shouldn't be accidentally wasted.

To date, Xen hasn't focused much on optimizing memory usage but
I think that will change over the next year or two.
 
> For example, why not take Linux's SLUB allocator? The fact 
> it's tried and
> tested in a real-world environment not unlike our own is a 
> big advantage to
> my mind.

The slub allocator is still quite a bit more complex than
xmalloc or TLSF and its not clear that that complexity will add
much value, or solve the worst-case issues when allocating
a huge number of different-sized near-page-size units.

TLSF is very similar to the existing xmalloc except that it has
better response time, MUCH better worst-case response time,
and better fragmentation characteristics.

Adding a slub allocator to Xen might be useful to solve some other
problems but it doesn't help me (or future de-duplication code
I don't think).

(BTW, my proposal above to change the API is orthogonal to this
discussion.)