Olaf Hering
2012-Jan-11 13:55 UTC
[PATCH] xenpaging: use flat index for pagefile and page-in requests
# HG changeset patch
# User Olaf Hering <olaf@aepfle.de>
# Date 1326290042 -3600
# Node ID 83cc7a3fbf4feb1f2a4492b1dcca4778ad81226a
# Parent 9cdcedc133e5227c635dbb00bd4779015311107a
xenpaging: use flat index for pagefile and page-in requests
This change is based on an idea by <hongkaixing@huawei.com> and
<bicky.shi@huawei.com>.
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@aepfle.de>
diff -r 9cdcedc133e5 -r 83cc7a3fbf4f 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 9cdcedc133e5 -r 83cc7a3fbf4f 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 9cdcedc133e5 -r 83cc7a3fbf4f tools/xenpaging/xenpaging.c
--- a/tools/xenpaging/xenpaging.c
+++ b/tools/xenpaging/xenpaging.c
@@ -430,6 +430,11 @@ static struct xenpaging *xenpaging_init(
}
DPRINTF("max_pages = %d\n", paging->max_pages);
+ 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 +473,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 +568,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 | PROT_WRITE, &gfn, 1);
+ page = xc_map_foreign_pages(xch, paging->mem_event.domain_id, PROT_READ
| PROT_WRITE, &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 +598,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 +718,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 +739,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 +751,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 +761,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 +769,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 +788,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 +820,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 +851,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 +900,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 +970,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 +990,6 @@ int main(int argc, char *argv[])
out:
close(fd);
unlink_pagefile();
- free(victims);
/* Tear down domain paging */
rc1 = xenpaging_teardown(paging);
diff -r 9cdcedc133e5 -r 83cc7a3fbf4f 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);