[Xen-devel] [PATCHv12 5/5] [RFC] gnttab: steal maptrack entries from other VCPUs

[David Vrabel <david.vrabel@xxxxxxxxxx>]

If a guest is not evenly grant mapping across its VCPUs one of the
VCPUs may run out of free maptrack entries even though other VCPUs
have many free.

If this happens, "steal" free entries from other VCPUs.  We want to
steal entries such that:

a) We avoid ping-ponging stolen entries between VCPUs.

b) The number of free entries owned by each VCPUs tends (over time) to
   the number it uses.

So when stealing, we select a VCPU at random (reducing (a)) and we
transfer the stolen entries to the thief VCPU (aiming for (b)).

Signed-off-by: David Vrabel <david.vrabel@xxxxxxxxxx>
---
v12:
- New.
---
 xen/common/grant_table.c |   73 ++++++++++++++++++++++++++++++++++++----------
 1 file changed, 58 insertions(+), 15 deletions(-)

diff --git a/xen/common/grant_table.c b/xen/common/grant_table.c
index 41d4e0f..5d91d38 100644
--- a/xen/common/grant_table.c
+++ b/xen/common/grant_table.c
@@ -277,26 +277,65 @@ __get_maptrack_handle(
     struct grant_table *t,
     struct vcpu *v)
 {
-    unsigned int head, next;
+    unsigned int head, next, prev_head;
 
-    /* No maptrack pages allocated for this VCPU yet? */
-    head = v->maptrack_head;
-    if ( unlikely(head == MAPTRACK_TAIL) )
-        return -1;
+    do {
+        /* No maptrack pages allocated for this VCPU yet? */
+        head = read_atomic(&v->maptrack_head);
+        if ( unlikely(head == MAPTRACK_TAIL) )
+            return -1;
 
-    /*
-     * Always keep one entry in the free list to make it easier to add
-     * free entries to the tail.
-     */
-    next = read_atomic(&maptrack_entry(t, head).ref);
-    if ( unlikely(next == MAPTRACK_TAIL) )
-        return -1;
+        /*
+         * Always keep one entry in the free list to make it easier to
+         * add free entries to the tail.
+         */
+        next = read_atomic(&maptrack_entry(t, head).ref);
+        if ( unlikely(next == MAPTRACK_TAIL) )
+            return -1;
 
-    v->maptrack_head = next;
+        prev_head = head;
+        head = cmpxchg(&v->maptrack_head, prev_head, next);
+    } while ( head != prev_head );
 
     return head;
 }
 
+/*
+ * Try to "steal" a free maptrack entry from another VCPU.
+ *
+ * A stolen entry is transferred to the thief, so the number of
+ * entries for each VCPU should tend to the usage pattern.
+ *
+ * To avoid having to atomically count the number of free entries on
+ * each VCPU and to avoid two VCPU repeatedly stealing entries from
+ * each other, the initial victim VCPU is selected randomly.
+ */
+static int steal_maptrack_handle(struct grant_table *t, struct vcpu *v)
+{
+    struct domain *d = v->domain;
+    unsigned int first, i;
+
+    /* Find an initial victim. */
+    first = i = NOW() % d->max_vcpus;
+
+    do {
+        unsigned int handle;
+
+        handle = __get_maptrack_handle(t, d->vcpu[i]);
+        if ( handle >= 0 ) {
+            maptrack_entry(t, handle).vcpu = v->vcpu_id;
+            return handle;
+        }
+
+        i++;
+        if ( i == d->max_vcpus )
+            i = 0;
+    } while ( i != first );
+
+    /* No free handles on any VCPU. */
+    return -1;
+}
+
 static inline void
 put_maptrack_handle(
     struct grant_table *t, int handle)
@@ -337,10 +376,14 @@ get_maptrack_handle(
     /*
      * max_maptrack_frames is per domain so each VCPU gets a share of
      * the maximum, but allow at least one frame per VCPU.
+     *
+     * If this VCPU has run out of frames, try stealing an entry from
+     * another VCPU (in case the guest isn't mapping across its VCPUs
+     * evenly).
      */
     if ( v->maptrack_frames
          && v->maptrack_frames >= max_maptrack_frames / v->domain->max_vcpus )
-        return -1;
+        return steal_maptrack_handle(lgt, v);
 
     new_mt = alloc_xenheap_page();
     if ( !new_mt )
@@ -358,7 +401,7 @@ get_maptrack_handle(
     new_mt[i - 1].ref = v->maptrack_head;
     new_mt[i - 1].vcpu = v->vcpu_id;
 
-    v->maptrack_head = lgt->maptrack_pages * MAPTRACK_PER_PAGE;
+    write_atomic(&v->maptrack_head, lgt->maptrack_pages * MAPTRACK_PER_PAGE);
 
     /* Set tail directly if this is the first page for this VCPU. */
     if ( v->maptrack_tail == MAPTRACK_TAIL )
-- 
1.7.10.4


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