[Xen-devel] [PATCH 1 of 9] xenpaging: use flat index for pagefile and page-in requests

[Olaf Hering <olaf@xxxxxxxxx>]

# HG changeset patch
# User Olaf Hering <olaf@xxxxxxxxx>
# Date 1329769124 -3600
# Node ID 4b2dbd2cb9977f357a5dd754c923ed14dda2ec51
# Parent  0900b1c905f1d038aad58a2732fe2bad682149a3
xenpaging: use flat index for pagefile and page-in requests

This change is based on an idea by <hongkaixing@xxxxxxxxxx> and
<bicky.shi@xxxxxxxxxx>.

Scanning the victims[] array is time consuming with a large number of
target pages. Replace the loop to find the slot in the pagefile which
holds the requested gfn with an index.

Remove the victims array and replace it with a flat array. This array
holds the gfn for a given slot in the pagefile. Adjust all users of the
victims array.

Rename variable in main() from i to slot to clearify the meaning.

Update xenpaging_evict_page() to pass a pointer to xen_pfn_t to
xc_map_foreign_pages().

Update policy_choose_victim() to return either a gfn or INVALID_MFN.

Signed-off-by: Olaf Hering <olaf@xxxxxxxxx>

diff -r 0900b1c905f1 -r 4b2dbd2cb997 tools/xenpaging/policy.h
--- a/tools/xenpaging/policy.h
+++ b/tools/xenpaging/policy.h
@@ -29,7 +29,7 @@
 
 
 int policy_init(struct xenpaging *paging);
-int policy_choose_victim(struct xenpaging *paging, struct victim *victim);
+unsigned long policy_choose_victim(struct xenpaging *paging);
 void policy_notify_paged_out(unsigned long gfn);
 void policy_notify_paged_in(unsigned long gfn);
 void policy_notify_paged_in_nomru(unsigned long gfn);
diff -r 0900b1c905f1 -r 4b2dbd2cb997 tools/xenpaging/policy_default.c
--- a/tools/xenpaging/policy_default.c
+++ b/tools/xenpaging/policy_default.c
@@ -77,7 +77,7 @@ int policy_init(struct xenpaging *paging
     return rc;
 }
 
-int policy_choose_victim(struct xenpaging *paging, struct victim *victim)
+unsigned long policy_choose_victim(struct xenpaging *paging)
 {
     xc_interface *xch = paging->xc_handle;
     unsigned long wrap = current_gfn;
@@ -102,16 +102,13 @@ int policy_choose_victim(struct xenpagin
                 /* One more round before returning ENOSPC */
                 continue;
             }
-            victim->gfn = INVALID_MFN;
-            return -ENOSPC;
+            return INVALID_MFN;
         }
     }
     while ( test_bit(current_gfn, bitmap) || test_bit(current_gfn, unconsumed) 
);
 
     set_bit(current_gfn, unconsumed);
-    victim->gfn = current_gfn;
-
-    return 0;
+    return current_gfn;
 }
 
 void policy_notify_paged_out(unsigned long gfn)
diff -r 0900b1c905f1 -r 4b2dbd2cb997 tools/xenpaging/xenpaging.c
--- a/tools/xenpaging/xenpaging.c
+++ b/tools/xenpaging/xenpaging.c
@@ -430,6 +430,12 @@ static struct xenpaging *xenpaging_init(
     }
     DPRINTF("max_pages = %d\n", paging->max_pages);
 
+    /* Allocate indicies for pagefile slots */
+    paging->slot_to_gfn = calloc(paging->max_pages, 
sizeof(*paging->slot_to_gfn));
+    paging->gfn_to_slot = calloc(paging->max_pages, 
sizeof(*paging->gfn_to_slot));
+    if ( !paging->slot_to_gfn || !paging->gfn_to_slot )
+        goto err;
+
     /* Initialise policy */
     rc = policy_init(paging);
     if ( rc != 0 )
@@ -468,6 +474,8 @@ static struct xenpaging *xenpaging_init(
 
         free(dom_path);
         free(watch_target_tot_pages);
+        free(paging->slot_to_gfn);
+        free(paging->gfn_to_slot);
         free(paging->bitmap);
         free(paging);
     }
@@ -561,31 +569,29 @@ static void put_response(struct mem_even
     RING_PUSH_RESPONSES(back_ring);
 }
 
-static int xenpaging_evict_page(struct xenpaging *paging, struct victim 
*victim, int fd, int i)
+static int xenpaging_evict_page(struct xenpaging *paging, unsigned long gfn, 
int fd, int slot)
 {
     xc_interface *xch = paging->xc_handle;
     void *page;
-    unsigned long gfn;
+    xen_pfn_t victim = gfn;
     int ret;
 
     DECLARE_DOMCTL;
 
     /* Map page */
-    gfn = victim->gfn;
     ret = -EFAULT;
-    page = xc_map_foreign_pages(xch, paging->mem_event.domain_id,
-                                PROT_READ, &gfn, 1);
+    page = xc_map_foreign_pages(xch, paging->mem_event.domain_id, PROT_READ, 
&victim, 1);
     if ( page == NULL )
     {
-        PERROR("Error mapping page %lx", victim->gfn);
+        PERROR("Error mapping page %lx", gfn);
         goto out;
     }
 
     /* Copy page */
-    ret = write_page(fd, page, i);
+    ret = write_page(fd, page, slot);
     if ( ret != 0 )
     {
-        PERROR("Error copying page %lx", victim->gfn);
+        PERROR("Error copying page %lx", gfn);
         munmap(page, PAGE_SIZE);
         goto out;
     }
@@ -593,17 +599,20 @@ static int xenpaging_evict_page(struct x
     munmap(page, PAGE_SIZE);
 
     /* Tell Xen to evict page */
-    ret = xc_mem_paging_evict(xch, paging->mem_event.domain_id,
-                              victim->gfn);
+    ret = xc_mem_paging_evict(xch, paging->mem_event.domain_id, gfn);
     if ( ret != 0 )
     {
-        PERROR("Error evicting page %lx", victim->gfn);
+        PERROR("Error evicting page %lx", gfn);
         goto out;
     }
 
-    DPRINTF("evict_page > gfn %lx pageslot %d\n", victim->gfn, i);
+    DPRINTF("evict_page > gfn %lx pageslot %d\n", gfn, slot);
     /* Notify policy of page being paged out */
-    policy_notify_paged_out(victim->gfn);
+    policy_notify_paged_out(gfn);
+
+    /* Update index */
+    paging->slot_to_gfn[slot] = gfn;
+    paging->gfn_to_slot[gfn] = slot;
 
     /* Record number of evicted pages */
     paging->num_paged_out++;
@@ -710,19 +719,19 @@ static void resume_pages(struct xenpagin
         page_in_trigger();
 }
 
-static int evict_victim(struct xenpaging *paging, struct victim *victim, int 
fd, int i)
+static int evict_victim(struct xenpaging *paging, int fd, int slot)
 {
     xc_interface *xch = paging->xc_handle;
+    unsigned long gfn;
     int j = 0;
     int ret;
 
     do
     {
-        ret = policy_choose_victim(paging, victim);
-        if ( ret != 0 )
+        gfn = policy_choose_victim(paging);
+        if ( gfn == INVALID_MFN )
         {
-            if ( ret != -ENOSPC )
-                ERROR("Error choosing victim");
+            ret = -ENOSPC;
             goto out;
         }
 
@@ -731,9 +740,9 @@ static int evict_victim(struct xenpaging
             ret = -EINTR;
             goto out;
         }
-        ret = xc_mem_paging_nominate(xch, paging->mem_event.domain_id, 
victim->gfn);
+        ret = xc_mem_paging_nominate(xch, paging->mem_event.domain_id, gfn);
         if ( ret == 0 )
-            ret = xenpaging_evict_page(paging, victim, fd, i);
+            ret = xenpaging_evict_page(paging, gfn, fd, slot);
         else
         {
             if ( j++ % 1000 == 0 )
@@ -743,7 +752,7 @@ static int evict_victim(struct xenpaging
     }
     while ( ret );
 
-    if ( test_and_set_bit(victim->gfn, paging->bitmap) )
+    if ( test_and_set_bit(gfn, paging->bitmap) )
         ERROR("Page has been evicted before");
 
     ret = 0;
@@ -753,7 +762,7 @@ static int evict_victim(struct xenpaging
 }
 
 /* Evict a batch of pages and write them to a free slot in the paging file */
-static int evict_pages(struct xenpaging *paging, int fd, struct victim 
*victims, int num_pages)
+static int evict_pages(struct xenpaging *paging, int fd, int num_pages)
 {
     xc_interface *xch = paging->xc_handle;
     int rc, slot, num = 0;
@@ -761,10 +770,10 @@ static int evict_pages(struct xenpaging 
     for ( slot = 0; slot < paging->max_pages && num < num_pages; slot++ )
     {
         /* Slot is allocated */
-        if ( victims[slot].gfn != INVALID_MFN )
+        if ( paging->slot_to_gfn[slot] )
             continue;
 
-        rc = evict_victim(paging, &victims[slot], fd, slot);
+        rc = evict_victim(paging, fd, slot);
         if ( rc == -ENOSPC )
             break;
         if ( rc == -EINTR )
@@ -780,11 +789,10 @@ int main(int argc, char *argv[])
 {
     struct sigaction act;
     struct xenpaging *paging;
-    struct victim *victims;
     mem_event_request_t req;
     mem_event_response_t rsp;
     int num, prev_num = 0;
-    int i;
+    int slot;
     int tot_pages;
     int rc = -1;
     int rc1;
@@ -813,15 +821,6 @@ int main(int argc, char *argv[])
         return 2;
     }
 
-    /* Allocate upper limit of pages to allow growing and shrinking */
-    victims = calloc(paging->max_pages, sizeof(struct victim));
-    if ( !victims )
-        goto out;
-
-    /* Mark all slots as unallocated */
-    for ( i = 0; i < paging->max_pages; i++ )
-        victims[i].gfn = INVALID_MFN;
-
     /* ensure that if we get a signal, we'll do cleanup, then exit */
     act.sa_handler = close_handler;
     act.sa_flags = 0;
@@ -853,32 +852,35 @@ int main(int argc, char *argv[])
         {
             get_request(&paging->mem_event, &req);
 
+            if ( req.gfn > paging->max_pages )
+            {
+                ERROR("Requested gfn %"PRIx64" higher than max_pages %lx\n", 
req.gfn, paging->max_pages);
+                goto out;
+            }
+
             /* Check if the page has already been paged in */
             if ( test_and_clear_bit(req.gfn, paging->bitmap) )
             {
                 /* Find where in the paging file to read from */
-                for ( i = 0; i < paging->max_pages; i++ )
+                slot = paging->gfn_to_slot[req.gfn];
+
+                /* Sanity check */
+                if ( paging->slot_to_gfn[slot] != req.gfn )
                 {
-                    if ( victims[i].gfn == req.gfn )
-                        break;
-                }
-    
-                if ( i >= paging->max_pages )
-                {
-                    DPRINTF("Couldn't find page %"PRIx64"\n", req.gfn);
+                    ERROR("Expected gfn %"PRIx64" in slot %d, but found gfn 
%lx\n", req.gfn, slot, paging->slot_to_gfn[slot]);
                     goto out;
                 }
-                
+
                 if ( req.flags & MEM_EVENT_FLAG_DROP_PAGE )
                 {
-                    DPRINTF("drop_page ^ gfn %"PRIx64" pageslot %d\n", 
req.gfn, i);
+                    DPRINTF("drop_page ^ gfn %"PRIx64" pageslot %d\n", 
req.gfn, slot);
                     /* Notify policy of page being dropped */
                     policy_notify_dropped(req.gfn);
                 }
                 else
                 {
                     /* Populate the page */
-                    rc = xenpaging_populate_page(paging, req.gfn, fd, i);
+                    rc = xenpaging_populate_page(paging, req.gfn, fd, slot);
                     if ( rc != 0 )
                     {
                         PERROR("Error populating page %"PRIx64"", req.gfn);
@@ -899,7 +901,7 @@ int main(int argc, char *argv[])
                 }
 
                 /* Clear this pagefile slot */
-                victims[i].gfn = INVALID_MFN;
+                paging->slot_to_gfn[slot] = 0;
             }
             else
             {
@@ -969,7 +971,7 @@ int main(int argc, char *argv[])
             /* Limit the number of evicts to be able to process page-in 
requests */
             if ( num > 42 )
                 num = 42;
-            evict_pages(paging, fd, victims, num);
+            evict_pages(paging, fd, num);
         }
         /* Resume some pages if target not reached */
         else if ( tot_pages < paging->target_tot_pages && 
paging->num_paged_out )
@@ -989,7 +991,6 @@ int main(int argc, char *argv[])
  out:
     close(fd);
     unlink_pagefile();
-    free(victims);
 
     /* Tear down domain paging */
     rc1 = xenpaging_teardown(paging);
diff -r 0900b1c905f1 -r 4b2dbd2cb997 tools/xenpaging/xenpaging.h
--- a/tools/xenpaging/xenpaging.h
+++ b/tools/xenpaging/xenpaging.h
@@ -46,6 +46,9 @@ struct xenpaging {
 
     unsigned long *bitmap;
 
+    unsigned long *slot_to_gfn;
+    int *gfn_to_slot;
+
     struct mem_event mem_event;
     /* number of pages for which data structures were allocated */
     int max_pages;
@@ -56,13 +59,6 @@ struct xenpaging {
     unsigned long pagein_queue[XENPAGING_PAGEIN_QUEUE_SIZE];
 };
 
-
-struct victim {
-    /* the gfn of the page to evict */
-    unsigned long gfn;
-};
-
-
 extern void create_page_in_thread(struct xenpaging *paging);
 extern void page_in_trigger(void);
 

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