From mboxrd@z Thu Jan  1 00:00:00 1970
From: Jean Guyader <jean.guyader@eu.citrix.com>
Subject: [PATCH] permute with 2MB chunk
Date: Tue, 18 Mar 2008 18:03:13 +0000
Message-ID: <47E003E1.1090908@eu.citrix.com>
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="------------070705090706070607090407"
Return-path: <xen-devel-bounces@lists.xensource.com>
List-Unsubscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>,
	<mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
List-Post: <mailto:xen-devel@lists.xensource.com>
List-Help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-Subscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>,
	<mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
Sender: xen-devel-bounces@lists.xensource.com
Errors-To: xen-devel-bounces@lists.xensource.com
To: xen-devel@lists.xensource.com
List-Id: xen-devel@lists.xenproject.org

This is a multi-part message in MIME format.
--------------070705090706070607090407
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit


The memory permutation cause a slow down in case of a save/restore (bug 
1143). It works better when the mixing is done with 2MB chunks.

Signed-off-by: Jean Guyader <jean.guyader@eu.citrix.com>

--------------070705090706070607090407
Content-Type: text/x-diff;
 name="fix-permute.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="fix-permute.patch"

diff -r 59b8768d0d0d tools/libxc/xc_domain_save.c
--- a/tools/libxc/xc_domain_save.c	Wed Mar 05 11:18:25 2008 +0000
+++ b/tools/libxc/xc_domain_save.c	Tue Mar 18 17:45:03 2008 +0000
@@ -125,34 +125,22 @@ static inline int count_bits ( int nr, v
     return count;
 }
 
-static inline int permute( int i, int nr, int order_nr  )
+static inline int permute(unsigned long i, unsigned long order_nr)
 {
     /* Need a simple permutation function so that we scan pages in a
        pseudo random order, enabling us to get a better estimate of
        the domain's page dirtying rate as we go (there are often
        contiguous ranges of pfns that have similar behaviour, and we
        want to mix them up. */
+  
+  unsigned char keep = 9; /* chunk of 2 MB */
+  unsigned char shift_low = (order_nr - keep) / 2 + ((order_nr - keep) / 2) % 2;
+  unsigned char shift_high = order_nr - keep - shift_low;
 
-    /* e.g. nr->oder 15->4 16->4 17->5 */
-    /* 512MB domain, 128k pages, order 17 */
+  unsigned long high = (i >> (keep + shift_low));
+  unsigned long low = (i >> keep) & ((1 << shift_low) - 1);
 
-    /*
-      QPONMLKJIHGFEDCBA
-             QPONMLKJIH
-      GFEDCBA
-     */
-
-    /*
-      QPONMLKJIHGFEDCBA
-                  EDCBA
-             QPONM
-      LKJIHGF
-      */
-
-    do { i = ((i>>(order_nr-10)) | ( i<<10 ) ) & ((1<<order_nr)-1); }
-    while ( i >= nr ); /* this won't ever loop if nr is a power of 2 */
-
-    return i;
+  return (i & ((1 << keep) - 1)) | (low << (shift_high + keep)) | (high << keep);
 }
 
 static uint64_t tv_to_us(struct timeval *new)
@@ -1126,7 +1114,7 @@ int xc_domain_save(int xc_handle, int io
                    (batch < MAX_BATCH_SIZE) && (N < p2m_size);
                    N++ )
             {
-                int n = permute(N, p2m_size, order_nr);
+                int n = permute(N, order_nr);
 
                 if ( debug )
                 {

--------------070705090706070607090407
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--------------070705090706070607090407--