Xen devel - Apr 2010 - [PATCH] Add hypercall to mark superpages to improve performance

On 28/04/2010 15:33, "Dave McCracken" <dcm@mccr.org> wrote:
> The current method of mapping hugepages/superpages in the hypervisor
involves
> updating the reference counts of every page in the superpage.  This has
proved
> to be a significant performance bottleneck.
> 
> This patch adds a pair of MMUEXT hypercalls to mark and unmark a superpage.
> Once the superpage is marked, the type is locked to writable page until a
> companion unmark is done.  When that superpage is subsequently mapped, only
> the first page needs to be reference counted.
> 
> There are checks when the superpage is marked and unmarked to make sure no
> individual page mappings have skewed the reference counts.
First of all, that changes the semantics of hugepages, since they can
subsequently *only* be mapped as superpages. I''m not sure
that''s a
restriction we want. Secondly, I don''t really believe that the
mark/unmark
hypercalls are race-free -- bearing in mind, that other mappings (superpage
or otherwise) can be constructed or deleted in parallel on other cpus.
Finally, does this really require new hypercalls? Could there not instead be
an always-enabled robust method for Xen to do superpage tracking?

 -- Keir



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

The current method of mapping hugepages/superpages in the hypervisor involves 
updating the reference counts of every page in the superpage.  This has proved 
to be a significant performance bottleneck.

This patch adds a pair of MMUEXT hypercalls to mark and unmark a superpage.  
Once the superpage is marked, the type is locked to writable page until a 
companion unmark is done.  When that superpage is subsequently mapped, only 
the first page needs to be reference counted.

There are checks when the superpage is marked and unmarked to make sure no 
individual page mappings have skewed the reference counts.

Dave McCracken
Oracle Corp


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

On Wednesday 28 April 2010, Keir Fraser wrote:
> On 28/04/2010 15:33, "Dave McCracken" <dcm@mccr.org> wrote:
> > The current method of mapping hugepages/superpages in the hypervisor
> > involves updating the reference counts of every page in the superpage.
> > This has proved to be a significant performance bottleneck.
> >
> > This patch adds a pair of MMUEXT hypercalls to mark and unmark a
> > superpage. Once the superpage is marked, the type is locked to
writable
> > page until a companion unmark is done.  When that superpage is
> > subsequently mapped, only the first page needs to be reference
counted.
> >
> > There are checks when the superpage is marked and unmarked to make
sure
> > no individual page mappings have skewed the reference counts.
> 
> First of all, that changes the semantics of hugepages, since they can
> subsequently *only* be mapped as superpages. I''m not sure
that''s a
> restriction we want. 
That''s not correct.  Individual pages can be freely mapped as writable
pages
after the superpage flag is set.  The only requirement is they all be at a base 
mapping state at the time of setting the mark, and be returned to that state 
when the mark is removed.
> Secondly, I don''t really believe that the mark/unmark
> hypercalls are race-free -- bearing in mind, that other mappings (superpage
> or otherwise) can be constructed or deleted in parallel on other cpus.
I''ll look into what can be done to prevent races.  I suspect some races
we
don''t care about.
> Finally, does this really require new hypercalls? Could there not instead
>  be an always-enabled robust method for Xen to do superpage tracking?
I''m open to alternative suggestions on how to lock superpages into
writable
state once they''re mapped without having to touch each individual page,
even
on the first map/unmap.  We could refcount superpage mappings in the base page 
of each superpage and then whenever a small page is mapped check its base 
page, but that would require an additional refcounted field in struct 
page_info.  I figured that would not be considered acceptable.

Dave McCracken

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

On 30/04/2010 12:43, "Dave McCracken" <dcm@mccr.org> wrote:
>> Secondly, I don''t really believe that the mark/unmark
>> hypercalls are race-free -- bearing in mind, that other mappings
(superpage
>> or otherwise) can be constructed or deleted in parallel on other cpus.
> 
> I''ll look into what can be done to prevent races.  I suspect some
races we
> don''t care about.
I mean I think there are probably races that can result in inconsistent
reference counts. I reckon I''ll be able to find some when I''m
back from
travelling next week. Obviously, any such race would be unacceptable.

 -- Keir



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

On 30/04/2010 12:43, "Dave McCracken" <dcm@mccr.org> wrote:
>> Finally, does this really require new hypercalls? Could there not
instead
>>  be an always-enabled robust method for Xen to do superpage tracking?
> 
> I''m open to alternative suggestions on how to lock superpages into
writable
> state once they''re mapped without having to touch each individual
page, even
> on the first map/unmap.  We could refcount superpage mappings in the base
page
> of each superpage and then whenever a small page is mapped check its base
> page, but that would require an additional refcounted field in struct
> page_info.  I figured that would not be considered acceptable.
One option would be an array of reference counts indexed by superpage number
(i.e, mfn>>9). So kind of a separate array to page_info, and a non-zero
superpage refcount would arrange to hold a reference on every relevant page
in page_info.

That could be implemented with no extra hypercalls, and I reckon it''s
probably easier to make this race-free too. Obviously it does have extra
code complexity to construct this array (which I suppose needs to be sparse,
just like page_info array, in the face of very sparse memory maps). The
space overhead (about 8 bytes per 2MB, or 0.0004% of total system memory)
would be trivial. Compared with an extra reference count in every page_info,
which would have a much higher 0.2% overhead.

 -- Keir



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

On Friday 30 April 2010, Keir Fraser wrote:
> One option would be an array of reference counts indexed by superpage
>  number (i.e, mfn>>9). So kind of a separate array to page_info, and
a
>  non-zero superpage refcount would arrange to hold a reference on every
>  relevant page in page_info.
> 
> That could be implemented with no extra hypercalls, and I reckon
it''s
> probably easier to make this race-free too. Obviously it does have extra
> code complexity to construct this array (which I suppose needs to be
>  sparse, just like page_info array, in the face of very sparse memory
>  maps). The space overhead (about 8 bytes per 2MB, or 0.0004% of total
>  system memory) would be trivial. Compared with an extra reference count in
>  every page_info, which would have a much higher 0.2% overhead.
I like this idea.  I''ll look into it.

Dave

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

On 30/04/2010 14:43, "Dave McCracken" <dcm@mccr.org> wrote:
>> That could be implemented with no extra hypercalls, and I reckon
it''s
>> probably easier to make this race-free too. Obviously it does have
extra
>> code complexity to construct this array (which I suppose needs to be
>>  sparse, just like page_info array, in the face of very sparse memory
>>  maps). The space overhead (about 8 bytes per 2MB, or 0.0004% of total
>>  system memory) would be trivial. Compared with an extra reference
count in
>>  every page_info, which would have a much higher 0.2% overhead.
> 
> I like this idea.  I''ll look into it.
The algorithm for acquiring a superpage refcount would be something like:
 y = superpage_info->count
 do {
    x = y
    if ( x == 0 )
        for (each page in super_page)
            if (!get_page(page))
                goto undo_and_fail;
 } while ((y = cmpxchg(&superpage_info->count, x, x+1)) != x);

For destroying a superpage refcount:
 y = superpage_info->count
 do { x = y } while ((y = cmpxchg(..,x,x-1)) != x);
 if (x==1) for (each page in super_page) put_page(page)

I''d actually have two refcounts in superpage struct: one for read-only
mappings and one for read-write mappings. The latter would be updated as
above except for the use of {get,put}_page_and_type() instead of
{get,put}_page().

The other thing to note is that this approach is cheap when updating
superpage refcounts between non-zero values. If regularly
constructing/destroying the *only* superpage mapping of a page, then
obviously you are going to be continually taking the slow path. In that
case, pinning a superpage with new hypercalls as you suggested may have to
be done. It kind of depends on how your workloads interact with the
reference-counting. In any case, you could implement the basic version as
described here, and add hypercalls as a second stage if they turn out to be
needed.

I can help with further details and advice if need be.

 -- Keir



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

On 30/04/2010 14:30, "Keir Fraser" <keir.fraser@eu.citrix.com>
wrote:
>>> Secondly, I don''t really believe that the mark/unmark
>>> hypercalls are race-free -- bearing in mind, that other mappings
(superpage
>>> or otherwise) can be constructed or deleted in parallel on other
cpus.
>> 
>> I''ll look into what can be done to prevent races.  I suspect
some races we
>> don''t care about.
> 
> I mean I think there are probably races that can result in inconsistent
> reference counts. I reckon I''ll be able to find some when
I''m back from
> travelling next week. Obviously, any such race would be unacceptable.
Here''s one that''s not even really a race: what if a guest
marks a superpage
(via hypercall), then creates a mapping of that superpage, then creates
single-page mappings of all pages in the superpage except the first, then
unmarks the superpage? All refcounts of pages in the superpage will be the
same (because the first page holds the superpage mapping count, and all
other pages have a count from their respectibve single-page mappings). So
unmark would succeed, but now destroying the superpage mapping will
erroneously decrement the refcount of every page in the superpage?

 -- Keir



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

On Friday 30 April 2010, Keir Fraser wrote:
> I''d actually have two refcounts in superpage struct: one for
read-only
> mappings and one for read-write mappings. The latter would be updated as
> above except for the use of {get,put}_page_and_type() instead of
> {get,put}_page().
> 
> The other thing to note is that this approach is cheap when updating
> superpage refcounts between non-zero values. If regularly
> constructing/destroying the only superpage mapping of a page, then
> obviously you are going to be continually taking the slow path. In that
> case, pinning a superpage with new hypercalls as you suggested may have to
> be done. It kind of depends on how your workloads interact with the
> reference-counting. In any case, you could implement the basic version as
> described here, and add hypercalls as a second stage if they turn out to be
> needed.
I have an alternative idea...

Make the superpage struct contain a single typecount field.  The two possible 
values fortype would be "superpage" and "conflicts with
superpage".  The
semantics of this typecount field would be the same as page_info... it can only 
change type when the count is zero.

The "superpage" type counts the times this superpage is mapped.

The "conflicts with superpage" type is used whenever any page in the
superpage
is set to a type that would conflict with a superpage mapping, basically any 
type other than readonly or read/write.  The count would be the sum of the 
mappings of the pages in the superpage with a conflicting type.

Permission checking would be very simple.  If get_superpage_and_type() returns 
a type mismatch error then the mapping will fail, in exactly the same fashion 
as get_page_and_type().

This model would completely eliminate the need to walk the pages in a 
superpage at mapping time, at the cost of one 
get_superpage_and_type()/put_superpage_and_type(). on each page table page.

One outstanding issue I see is how to handle readonly mappings.  If we follow 
the model of regular page typecount, readonly mappings of superpages would not 
conflict with the "conflicts with superpage" type.  This means a
subsequent
attempt to change it to a read/write mapping could fail, just like with a 
regular page.  Or we could count all mappings of superpages as if they were 
read/write.

What are your thoughts?  It seems fairly simple and elegant to me, and at this 
point I don''t see any big holes in it.

Dave McCracken
Oracle Corp.

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

On 02/05/2010 14:34, "Dave McCracken" <dcm@mccr.org> wrote:
> One outstanding issue I see is how to handle readonly mappings.  If we
follow
> the model of regular page typecount, readonly mappings of superpages would
not
> conflict with the "conflicts with superpage" type.  This means a
subsequent
> attempt to change it to a read/write mapping could fail, just like with a
> regular page.  Or we could count all mappings of superpages as if they were
> read/write.
I''d keep an extra refcount in superpage_info to track read-only
mappings (or
all superpage mappings, as page->count_info does for 4kB mappings).
It''s
trivial extra space and avoids having unexpected extra restrictions on
read-only superpage mappings.
> What are your thoughts?  It seems fairly simple and elegant to me, and at
this
> point I don''t see any big holes in it.
It does mean that creating/destroying pagetable pages causes an extra locked
read-modify-write cycle on a non-local cacheline (superpage_info refcount).
Would this be significant? Not sure. I guess we''d only be doing it for
guests with the superpage capability configured, and we could do some
performance comparisons with the capability enabled/disabled. I think
overall I quite like your suggestion.

 -- Keir



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

On 02/05/2010 16:54, "Keir Fraser" <keir.fraser@eu.citrix.com>
wrote:
>> What are your thoughts?  It seems fairly simple and elegant to me, and
at
>> this
>> point I don''t see any big holes in it.
> 
> It does mean that creating/destroying pagetable pages causes an extra
locked
> read-modify-write cycle on a non-local cacheline (superpage_info refcount).
> Would this be significant? Not sure. I guess we''d only be doing it
for
> guests with the superpage capability configured, and we could do some
> performance comparisons with the capability enabled/disabled. I think
> overall I quite like your suggestion.
Oh, now I think about it, although your suggestion deals with type
conflicts, it doesn''t handle page lifetimes. What if a page is only
mapped
as a superpage? The page->count_info would not be incremented by the
superpage mappings, and the page would be erroneously freed to the Xen free
pools? So I''m not so sure we can so easily avoid the
mess-with-every-page''s-refcount on first mapping of a superpage... :-(

 -- Keir



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

On Sunday 02 May 2010, Keir Fraser wrote:
> Oh, now I think about it, although your suggestion deals with type
> conflicts, it doesn''t handle page lifetimes. What if a page is
only mapped
> as a superpage? The page->count_info would not be incremented by the
> superpage mappings, and the page would be erroneously freed to the Xen free
> pools? So I''m not so sure we can so easily avoid the
> mess-with-every-page''s-refcount on first mapping of a superpage...
:-(
It should be simple enough to also check superpage->count_info in those 
places.  So the total mappings of a page would be page->count_info + 
superpage->count_info.  Good thing you suggested we also have a count in the 
superpage_info struct :)

Dave

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

On 03/05/2010 02:55, "Dave McCracken" <dcm@mccr.org> wrote:
> On Sunday 02 May 2010, Keir Fraser wrote:
>> Oh, now I think about it, although your suggestion deals with type
>> conflicts, it doesn''t handle page lifetimes. What if a page is
only mapped
>> as a superpage? The page->count_info would not be incremented by the
>> superpage mappings, and the page would be erroneously freed to the Xen
free
>> pools? So I''m not so sure we can so easily avoid the
>> mess-with-every-page''s-refcount on first mapping of a
superpage... :-(
> 
> It should be simple enough to also check superpage->count_info in those
> places.  So the total mappings of a page would be page->count_info +
> superpage->count_info.  Good thing you suggested we also have a count in
the
> superpage_info struct :)
I think you''re going to have trouble handling two separate reference
counts,
for superpages and single pages, in a race-free manner that is any better
than checking/updating reference counts across all pages in a superpage on
first superpage mapping.

 -- Keir



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

On 03/05/2010 17:09, "Keir Fraser" <keir.fraser@eu.citrix.com>
wrote:
>> It should be simple enough to also check superpage->count_info in
those
>> places.  So the total mappings of a page would be page->count_info +
>> superpage->count_info.  Good thing you suggested we also have a
count in the
>> superpage_info struct :)
> 
> I think you''re going to have trouble handling two separate
reference counts,
> for superpages and single pages, in a race-free manner that is any better
> than checking/updating reference counts across all pages in a superpage on
> first superpage mapping.
For example: When making first superpage mapping, how do you know that all
pages belong to the relevant domain, without scanning every page_info? When
destructing last superpage mapping (or single-page mapping) how do you
safely check the ''other'' reference count to decide whether the
page is
freeable, without having races (last single-page and superpage mappings
could be destructed concurrently, need to ensure any given page gets freed
exactly once). And I could think of others no doubt... Just pointing out how
careful you have to be if you think you can avoid the naïve
refcount-updatign algorithms I suggested. I''d rather shoot down the
obvious
races before you do the coding.

 -- Keir



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