[PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[hongkaixing]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=us-ascii, Size: 3997 bytes --]

# HG changeset patch
# User hongkaixing<hongkaixing@huawei.com>
# Date 1325149704 -28800
# Node ID 052727b8165ce6e05002184ae894096214c8b537
# Parent  54a5e994a241a506900ee0e197bb42e5f1d8e759
xenpaging:add a new array to speed up page-in in xenpaging

This patch adds a new array named page_out_index to reserve the victim's index.
When page in a page,it has to go through a for loop from 0 to num_pages to find
the right page to read,and it costs much time in this loop.After adding the
page_out_index array,it just reads the arrry to get the right page,and saves much time.

The following is a xenpaging test on suse11-64 with 4G memories.

Nums of page_out pages	Page out time	Page in time(in unstable code) Page in time(apply this patch)
512M(131072)		    2.6s		           540s			             530s
2G(524288)		    15.5s		           2088s			     2055s

Signed-off-by£ºhongkaixing<hongkaixing@huawei.com>,shizhen<bicky.shi@huawei.com>

diff -r 54a5e994a241 -r 052727b8165c tools/xenpaging/xenpaging.c
--- a/tools/xenpaging/xenpaging.c	Wed Nov 02 17:09:09 2011 +0000
+++ b/tools/xenpaging/xenpaging.c	Thu Dec 29 17:08:24 2011 +0800
@@ -599,6 +599,7 @@
     struct sigaction act;
     xenpaging_t *paging;
     xenpaging_victim_t *victims;
+    victim_to_i_t *page_out_index = NULL;
     mem_event_request_t req;
     mem_event_response_t rsp;
     int i;
@@ -637,6 +638,17 @@
     }
 
     victims = calloc(paging->num_pages, sizeof(xenpaging_victim_t));
+    if (NULL == victims)
+    {
+        ERROR("Failed to alloc memory\n");
+        goto out;
+    }
+    page_out_index = (victim_to_i_t *)calloc(paging->domain_info->max_pages, sizeof(victim_to_i_t));
+    if ( NULL == page_out_index )
+    {
+        ERROR("Failed to alloc memory\n");
+        goto out;
+    }
 
     /* ensure that if we get a signal, we'll do cleanup, then exit */
     act.sa_handler = close_handler;
@@ -660,6 +672,7 @@
             break;
         if ( i % 100 == 0 )
             DPRINTF("%d pages evicted\n", i);
+        page_out_index[victims[i].gfn].index=i;
     }
 
     DPRINTF("%d pages evicted. Done.\n", i);
@@ -687,17 +700,7 @@
             if ( test_and_clear_bit(req.gfn, paging->bitmap) )
             {
                 /* Find where in the paging file to read from */
-                for ( i = 0; i < paging->num_pages; i++ )
-                {
-                    if ( victims[i].gfn == req.gfn )
-                        break;
-                }
-    
-                if ( i >= paging->num_pages )
-                {
-                    DPRINTF("Couldn't find page %"PRIx64"\n", req.gfn);
-                    goto out;
-                }
+                i = page_out_index[req.gfn].index ;
                 
                 if ( req.flags & MEM_EVENT_FLAG_DROP_PAGE )
                 {
@@ -733,7 +736,11 @@
                 if ( interrupted )
                     victims[i].gfn = INVALID_MFN;
                 else
+                {
                     evict_victim(paging, &victims[i], fd, i);
+                    if( victims[i].gfn !=INVALID_MFN )
+                        page_out_index[victims[i].gfn].index = i;
+                }
             }
             else
             {
@@ -798,7 +805,15 @@
  out:
     close(fd);
     unlink_pagefile();
-    free(victims);
+    if ( NULL != victims )
+    {
+        free(victims);
+    }
+
+    if ( NULL != page_out_index )
+    {
+        free(page_out_index);
+    }
 
     /* Tear down domain paging */
     rc1 = xenpaging_teardown(paging);
diff -r 54a5e994a241 -r 052727b8165c tools/xenpaging/xenpaging.h
--- a/tools/xenpaging/xenpaging.h	Wed Nov 02 17:09:09 2011 +0000
+++ b/tools/xenpaging/xenpaging.h	Thu Dec 29 17:08:24 2011 +0800
@@ -54,6 +54,10 @@
     unsigned long pagein_queue[XENPAGING_PAGEIN_QUEUE_SIZE];
 } xenpaging_t;
 
+typedef struct victim_to_i {
+    /* the index of victim array to read from */
+    int index;
+} victim_to_i_t;
 
 typedef struct xenpaging_victim {
     /* the gfn of the page to evict */


[-- Attachment #2: Type: text/plain, Size: 138 bytes --]

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

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Ian Jackson]

hongkaixing@huawei.com writes ("[Xen-devel] [PATCH] xenpaging:add a new array to speed up page-in in xenpaging"):
> xenpaging:add a new array to speed up page-in in xenpaging
> 
> This patch adds a new array named page_out_index to reserve the
> victim's index.  When page in a page,it has to go through a for loop
> from 0 to num_pages to find the right page to read,and it costs much
> time in this loop.After adding the page_out_index array,it just
> reads the arrry to get the right page,and saves much time.

Thanks for this submission.  Olaf may well have some comments, but I
have some too:

> @@ -660,6 +672,7 @@
>              break;
>          if ( i % 100 == 0 )
>              DPRINTF("%d pages evicted\n", i);
> +        page_out_index[victims[i].gfn].index=i;

Surely this should be better done much closer to the actual point
where we page out ?

And you should reset the index entry when the page is read back in, I
think ?

Ian.

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Hongkaixing]

> -----邮件原件-----
> 发件人: Ian Jackson [mailto:Ian.Jackson@eu.citrix.com]
> 发送时间: 2012年1月6日 2:27
> 收件人: hongkaixing@huawei.com
> 抄送: Olaf Hering; xen-devel@lists.xensource.com
> 主题: Re: [Xen-devel] [PATCH] xenpaging:add a new array to speed up
page-in
> in xenpaging
> 
> hongkaixing@huawei.com writes ("[Xen-devel] [PATCH] xenpaging:add a new
> array to speed up page-in in xenpaging"):
> > xenpaging:add a new array to speed up page-in in xenpaging
> >
> > This patch adds a new array named page_out_index to reserve the
> > victim's index.  When page in a page,it has to go through a for loop
> > from 0 to num_pages to find the right page to read,and it costs much
> > time in this loop.After adding the page_out_index array,it just
> > reads the arrry to get the right page,and saves much time.
> 
> Thanks for this submission.  Olaf may well have some comments, but I
> have some too:
> 
> > @@ -660,6 +672,7 @@
> >              break;
> >          if ( i % 100 == 0 )
> >              DPRINTF("%d pages evicted\n", i);
> > +        page_out_index[victims[i].gfn].index=i;
> 
> Surely this should be better done much closer to the actual point
> where we page out ?

After we improve the page-in speed, search index in the for loop becomes the
bottleneck, extremely when the page number is big.

> 
> And you should reset the index entry when the page is read back in, I
> think ?

En, our idea is let it go lazy way. I will try my best to make it perfect.

> 
> Ian.


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

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Ian Jackson]

hongkaixing@huawei.com writes ("[Xen-devel] [PATCH] xenpaging:add a new array to speed up page-in in xenpaging"):
> xenpaging:add a new array to speed up page-in in xenpaging

Oh, and a couple of style points.  You should keep to the style of the
code you're editing.  So:

> +    if (NULL == victims)

In the xenpaging code this is written like this:

       if (victims == NULL)

You should do the same, throughout.

> +    page_out_index = (victim_to_i_t *)calloc(paging->domain_info->max_pages, sizeof(victim_to_i_t));

Do not cast the return value from malloc et al.

> +                i = page_out_index[req.gfn].index ;

The space before the semicolon is not the conventional style.

> +                    if( victims[i].gfn !=INVALID_MFN )

> -    free(victims);
> +    if ( NULL != victims )
> +    {
> +        free(victims);
> +    }

This is simply pointless.  free(NULL) is legal.

> +typedef struct victim_to_i {
> +    /* the index of victim array to read from */
> +    int index;
> +} victim_to_i_t;

Why wrap this up in a struct ?

Use of types with names ending in _t is reserved to the C
implementation (compiler and runtime).  I know xenpaging is full of
these but we shouldn't introduce any more.

Ian.

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Hongkaixing]

> -----邮件原件-----
> 发件人: Ian Jackson [mailto:Ian.Jackson@eu.citrix.com]
> 发送时间: 2012年1月6日 2:31
> 收件人: hongkaixing@huawei.com
> 抄送: Olaf Hering; xen-devel@lists.xensource.com
> 主题: Re: [Xen-devel] [PATCH] xenpaging:add a new array to speed up
page-in
> in xenpaging
> 
> hongkaixing@huawei.com writes ("[Xen-devel] [PATCH] xenpaging:add a new
> array to speed up page-in in xenpaging"):
> > xenpaging:add a new array to speed up page-in in xenpaging
> 
> Oh, and a couple of style points.  You should keep to the style of the
> code you're editing.  So:
> 
> > +    if (NULL == victims)
> 
> In the xenpaging code this is written like this:
> 
>        if (victims == NULL)
> 

Oh, This is our coding style, I will modify it according your opinion.

> You should do the same, throughout.
> 
> > +    page_out_index = (victim_to_i_t
> *)calloc(paging->domain_info->max_pages, sizeof(victim_to_i_t));
> 
> Do not cast the return value from malloc et al.
> 
> > +                i = page_out_index[req.gfn].index ;
> 
> The space before the semicolon is not the conventional style.
> 
> > +                    if( victims[i].gfn !=INVALID_MFN )
> 
> > -    free(victims);
> > +    if ( NULL != victims )
> > +    {
> > +        free(victims);
> > +    }
> 
> This is simply pointless.  free(NULL) is legal.

I see...

> 
> > +typedef struct victim_to_i {
> > +    /* the index of victim array to read from */
> > +    int index;
> > +} victim_to_i_t;
> 
> Why wrap this up in a struct ?

We want to keep the same style with

typedef struct xenpaging_victim {
    /* the gfn of the page to evict */
    unsigned long gfn;
} xenpaging_victim_t;

> 
> Use of types with names ending in _t is reserved to the C
> implementation (compiler and runtime).  I know xenpaging is full of
> these but we shouldn't introduce any more.
> 
> Ian.


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

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Fri, Jan 06, Hongkaixing wrote:

> > Why wrap this up in a struct ?
> 
> We want to keep the same style with
> 
> typedef struct xenpaging_victim {
>     /* the gfn of the page to evict */
>     unsigned long gfn;
> } xenpaging_victim_t;

This dates back to the initial implementation of xenpaging.

In my testing I started a guest paused, paged it all out, and paged all
back into memory. By monitoring nr_pages I noticed that page-in got
slightly slower over time, so your suggestion to use two indexes will
speed things up a bit.


Looking through xenpaging.c, I think its best to have two flat arrays:
unsigned long slot_to_gfn[paging->max_pages]; /* was victims */
int gfn_to_slot[paging->max_pages];

I will prepare a patch to implement this.

Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Hongkaixing]

Sorry, this mail is sent out in hurry. In fact we send out 2 patches , and this is only one patch. The second patch is the key.

The second patch is about adding a fast way to trigger page-in. 
Titile is [PATCH 2 of 2] xenpaging:change page-in process to speed up page-in in xenpaging.

http://lists.xen.org/archives/html/xen-devel/2012-01/msg00210.html

In this patch, we get the return value from p2m_mem_paging_populate(). 
Because we want to known whether this p2mt is changed by balloon or others.

After this patch is published, we have received much advice, so a more perfect patch will be sent out later 

> -----Original Message-----
> From: Olaf Hering [mailto:olaf@aepfle.de]
> Sent: Wednesday, January 11, 2012 1:40 AM
> To: Hongkaixing
> Cc: 'Ian Jackson'; xen-devel@lists.xensource.com; 'bicky.'
> Subject: Re: [Xen-devel] [PATCH] xenpaging:add a new array to speed up page-in in xenpaging
> 
> On Fri, Jan 06, Hongkaixing wrote:
> 
> > > Why wrap this up in a struct ?
> >
> > We want to keep the same style with
> >
> > typedef struct xenpaging_victim {
> >     /* the gfn of the page to evict */
> >     unsigned long gfn;
> > } xenpaging_victim_t;
> 
> This dates back to the initial implementation of xenpaging.
> 
> In my testing I started a guest paused, paged it all out, and paged all
> back into memory. By monitoring nr_pages I noticed that page-in got
> slightly slower over time, so your suggestion to use two indexes will
> speed things up a bit.
> 
> 
> Looking through xenpaging.c, I think its best to have two flat arrays:
> unsigned long slot_to_gfn[paging->max_pages]; /* was victims */
> int gfn_to_slot[paging->max_pages];
> 
> I will prepare a patch to implement this.
> 
> Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Wed, Jan 11, Hongkaixing wrote:

> Sorry, this mail is sent out in hurry. In fact we send out 2 patches , and this is only one patch. The second patch is the key.
> 
> The second patch is about adding a fast way to trigger page-in. 
> Titile is [PATCH 2 of 2] xenpaging:change page-in process to speed up page-in in xenpaging.
> 
> http://lists.xen.org/archives/html/xen-devel/2012-01/msg00210.html
> 
> In this patch, we get the return value from p2m_mem_paging_populate(). 
> Because we want to known whether this p2mt is changed by balloon or others.
> 
> After this patch is published, we have received much advice, so a more perfect patch will be sent out later 

There is work being done to do page-in and page-out in a different way.
Please have a look at this work, it replaces what is currently done:
http://lists.xen.org/archives/html/xen-devel/2012-01/msg00753.html

Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Thu, Jan 05, Ian Jackson wrote:

> Use of types with names ending in _t is reserved to the C
> implementation (compiler and runtime).  I know xenpaging is full of
> these but we shouldn't introduce any more.

I will prepare patches to remove the typedefs from xenpaging.

Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Thu, Jan 05, hongkaixing@huawei.com wrote:

> # HG changeset patch
> # User hongkaixing<hongkaixing@huawei.com>
> # Date 1325149704 -28800
> # Node ID 052727b8165ce6e05002184ae894096214c8b537
> # Parent  54a5e994a241a506900ee0e197bb42e5f1d8e759
> xenpaging:add a new array to speed up page-in in xenpaging
> 
> This patch adds a new array named page_out_index to reserve the victim's index.
> When page in a page,it has to go through a for loop from 0 to num_pages to find
> the right page to read,and it costs much time in this loop.After adding the
> page_out_index array,it just reads the arrry to get the right page,and saves much time.
> 
> The following is a xenpaging test on suse11-64 with 4G memories.
> 
> Nums of page_out pages	Page out time	Page in time(in unstable code) Page in time(apply this patch)
> 512M(131072)		    2.6s		           540s			             530s
> 2G(524288)		    15.5s		           2088s			     2055s

Thanks for your work on this.

Is the page-out time for 512M really that fast? For me page-out is still
really slow even when the pagefile is in tmpfs. It takes several
minutes, I get around 4MB/s. page-in is around 20MB/s.

Wether an extra array is needed, we have to decide as it costs some
runtime memory. I was thinking already about better bitop functions,
like xc_find_next_bit_set and similar, just what xenpaging needs, to
remove the test bits one-by-one.

As for the new page-in op, there was some offline discussion about doing
page-in/page-out differently. If these ideas make into xen-unstable most
of domctls will disappear, and also the mmap to trigger page-in is not
needed anymore.

Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Hongkaixing]

Oh, sorry, this patch is sent in hurry, the whole version is sent out follow this one. 

According to our analysis, the old page in method spends much time in xc_map_foreign_pages, so we introduce a direct way to trigger page in.  This is the point.
After our new page-in method is applied, a new array can speed up page in significantly.

Result shows the page-in speed can reach the hard disk's limit, above 120M/s



> -----邮件原件-----
> 发件人: Olaf Hering [mailto:olaf@aepfle.de]
> 发送时间: 2012年1月6日 4:59
> 收件人: hongkaixing@huawei.com
> 抄送: xen-devel@lists.xensource.com
> 主题: Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging
> 
> On Thu, Jan 05, hongkaixing@huawei.com wrote:
> 
> > # HG changeset patch
> > # User hongkaixing<hongkaixing@huawei.com>
> > # Date 1325149704 -28800
> > # Node ID 052727b8165ce6e05002184ae894096214c8b537
> > # Parent  54a5e994a241a506900ee0e197bb42e5f1d8e759
> > xenpaging:add a new array to speed up page-in in xenpaging
> >
> > This patch adds a new array named page_out_index to reserve the victim's
> index.
> > When page in a page,it has to go through a for loop from 0 to num_pages to
> find
> > the right page to read,and it costs much time in this loop.After adding the
> > page_out_index array,it just reads the arrry to get the right page,and saves
> much time.
> >
> > The following is a xenpaging test on suse11-64 with 4G memories.
> >
> > Nums of page_out pages	Page out time	Page in time(in unstable code)
> Page in time(apply this patch)
> > 512M(131072)		    2.6s		           540s
> 530s
> > 2G(524288)		    15.5s		           2088s
> 2055s
> 
> Thanks for your work on this.
> 
> Is the page-out time for 512M really that fast? For me page-out is still
> really slow even when the pagefile is in tmpfs. It takes several
> minutes, I get around 4MB/s. page-in is around 20MB/s.
> 
> Wether an extra array is needed, we have to decide as it costs some
> runtime memory. I was thinking already about better bitop functions,
> like xc_find_next_bit_set and similar, just what xenpaging needs, to
> remove the test bits one-by-one.
> 
> As for the new page-in op, there was some offline discussion about doing
> page-in/page-out differently. If these ideas make into xen-unstable most
> of domctls will disappear, and also the mmap to trigger page-in is not
> needed anymore.
> 
> Olaf


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

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Thu, Jan 05, Olaf Hering wrote:

> Is the page-out time for 512M really that fast? For me page-out is still
> really slow even when the pagefile is in tmpfs. It takes several
> minutes, I get around 4MB/s. page-in is around 20MB/s.

Wait, the slow page-out is due to the poll() timeout in
xenpaging_wait_for_event_or_timeout(). This can be fixed with some sort
of dynamic timeout while there is still something to page-out.

Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Hongkaixing]

> -----Original Message-----
> From: Olaf Hering [mailto:olaf@aepfle.de]
> Sent: Friday, January 06, 2012 9:08 PM
> To: hongkaixing@huawei.com
> Cc: xen-devel@lists.xensource.com
> Subject: Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging
> 
> On Thu, Jan 05, Olaf Hering wrote:
> 
> > Is the page-out time for 512M really that fast? For me page-out is still
> > really slow even when the pagefile is in tmpfs. It takes several
> > minutes, I get around 4MB/s. page-in is around 20MB/s.
> 
> Wait, the slow page-out is due to the poll() timeout in
> xenpaging_wait_for_event_or_timeout(). This can be fixed with some sort
> of dynamic timeout while there is still something to page-out.

   I don't think so. Our approach still use 100ms in poll(), Using 10ms seems no significant change.

   In my opinion, In order to improve speed , 2 points are necessary:
   1. put page-in request fast
   2. request should be in disk order. Especially for a large swap file.


> 
> Olaf

Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging

[Olaf Hering]

On Sat, Jan 07, Hongkaixing wrote:

> 
> > -----Original Message-----
> > From: Olaf Hering [mailto:olaf@aepfle.de]
> > Sent: Friday, January 06, 2012 9:08 PM
> > To: hongkaixing@huawei.com
> > Cc: xen-devel@lists.xensource.com
> > Subject: Re: [PATCH] xenpaging:add a new array to speed up page-in in xenpaging
> > 
> > On Thu, Jan 05, Olaf Hering wrote:
> > 
> > > Is the page-out time for 512M really that fast? For me page-out is still
> > > really slow even when the pagefile is in tmpfs. It takes several
> > > minutes, I get around 4MB/s. page-in is around 20MB/s.
> > 
> > Wait, the slow page-out is due to the poll() timeout in
> > xenpaging_wait_for_event_or_timeout(). This can be fixed with some sort
> > of dynamic timeout while there is still something to page-out.
> 
>    I don't think so. Our approach still use 100ms in poll(), Using 10ms seems no significant change.

Sure, I was talking about page-out. With my change to use no timeout for
poll() the guests memory was paged-out in a few seconds.
I will send a patch for that today.

page-in is still slow as you know, we need to improve that in some way.

Olaf