[Xen-changelog] [xen-unstable] xenpaging: improve performance in policy_choose_victim

[Xen patchbot-unstable <patchbot@xxxxxxx>]

# HG changeset patch
# User Olaf Hering <olaf@xxxxxxxxx>
# Date 1329769124 -3600
# Node ID 6b14211c3e7729252d00b52976d96cd80153bbef
# Parent  68f149bbee77b3ce12702475b27d3d5002cf4c19
xenpaging: improve performance in policy_choose_victim

policy_choose_victim() is one of the bottlenecks in xenpaging. It is called
alot to find free bits in the fragmented bitmaps.

Reduce turnaround time by skipping longs with all bits set.
Adjust wrap detection in loop.

v2:
 - fix copy&paste error, bitmap was tested twice

Signed-off-by: Olaf Hering <olaf@xxxxxxxxx>
Committed-by: Ian Jackson <ian.jackson.citrix.com>
---


diff -r 68f149bbee77 -r 6b14211c3e77 tools/xenpaging/policy_default.c
--- a/tools/xenpaging/policy_default.c  Mon Feb 20 21:18:44 2012 +0100
+++ b/tools/xenpaging/policy_default.c  Mon Feb 20 21:18:44 2012 +0100
@@ -80,33 +80,58 @@
 unsigned long policy_choose_victim(struct xenpaging *paging)
 {
     xc_interface *xch = paging->xc_handle;
-    unsigned long wrap = current_gfn;
+    unsigned long i;
 
-    do
+    /* One iteration over all possible gfns */
+    for ( i = 0; i < max_pages; i++ )
     {
+        /* Try next gfn */
         current_gfn++;
+
+        /* Restart on wrap */
         if ( current_gfn >= max_pages )
             current_gfn = 0;
-        /* Could not nominate any gfn */
-        if ( wrap == current_gfn )
+
+        if ( (current_gfn & (BITS_PER_LONG - 1)) == 0 )
         {
-            paging->use_poll_timeout = 1;
-            /* Count wrap arounds */
-            unconsumed_cleared++;
-            /* Force retry every few seconds (depends on poll() timeout) */
-            if ( unconsumed_cleared > 123)
+            /* All gfns busy */
+            if ( ~bitmap[current_gfn >> ORDER_LONG] == 0 || 
~unconsumed[current_gfn >> ORDER_LONG] == 0 )
             {
-                /* Force retry of unconsumed gfns */
-                bitmap_clear(unconsumed, max_pages);
-                unconsumed_cleared = 0;
-                DPRINTF("clearing unconsumed, wrap %lx", wrap);
-                /* One more round before returning ENOSPC */
+                current_gfn += BITS_PER_LONG;
+                i += BITS_PER_LONG;
                 continue;
             }
-            return INVALID_MFN;
         }
+
+        /* gfn busy */
+        if ( test_bit(current_gfn, bitmap) )
+            continue;
+
+        /* gfn already tested */
+        if ( test_bit(current_gfn, unconsumed) )
+            continue;
+
+        /* gfn found */
+        break;
     }
-    while ( test_bit(current_gfn, bitmap) || test_bit(current_gfn, unconsumed) 
);
+
+    /* Could not nominate any gfn */
+    if ( i >= max_pages )
+    {
+        /* No more pages, wait in poll */
+        paging->use_poll_timeout = 1;
+        /* Count wrap arounds */
+        unconsumed_cleared++;
+        /* Force retry every few seconds (depends on poll() timeout) */
+        if ( unconsumed_cleared > 123)
+        {
+            /* Force retry of unconsumed gfns on next call */
+            bitmap_clear(unconsumed, max_pages);
+            unconsumed_cleared = 0;
+            DPRINTF("clearing unconsumed, current_gfn %lx", current_gfn);
+        }
+        return INVALID_MFN;
+    }
 
     set_bit(current_gfn, unconsumed);
     return current_gfn;

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