From: Jiri Denemark <jdenemar@redhat.com>
Date: Fri, 17 Apr 2009 16:02:48 +0200
Subject: [xen] live migration failure due to fragmented memory
Message-id: 20090417140247.GA18963@orkuz.home
O-Subject: Re: [RHEL5.4 PATCH] Fix live migration failure due to fragmented memory
Bugzilla: 469130
RH-Acked-by: Markus Armbruster <armbru@redhat.com>
RH-Acked-by: Chris Lalancette <clalance@redhat.com>

commit 46acb0e1d5f24af980d471cf51398fa1868bbb9b
Author: Jiri Denemark <jdenemar@redhat.com>
Date:   Thu Mar 26 15:39:29 2009 +0100

    Fix live migration failure due to fragmented memory

    Backport of the following upstream changeset (16109 in xen-unstable):

    User Tim Deegan <Tim.Deegan@xensource.com>
    Date 1192436894 -3600
    Node ID 415beae13d068ab9a3643eb0e0b95cedee3b3380
    Parent  a76f3f7ddca06e5bf33b31028d475f608661bbf7
    PV guests don't require order-non-zero pages for shadowing, hence lift
    the requirement on such being available for allocation when enabling
    shadow mode, removing the potential for live migration to fail due to
    fragmented memory.

    Has seen little testing only so far.

    Signed-off-by: Jan Beulich <jbeulich@novell.com>

diff --git a/arch/x86/mm/shadow/common.c b/arch/x86/mm/shadow/common.c
index 8ae8174..90fa955 100644
--- a/arch/x86/mm/shadow/common.c
+++ b/arch/x86/mm/shadow/common.c
@@ -771,14 +771,29 @@ shadow_order(unsigned int shadow_type)
 }
 
 
-/* Do we have a free chunk of at least this order? */
-static inline int chunk_is_available(struct domain *d, int order)
+static inline unsigned int
+shadow_max_order(struct domain *d)
 {
-    int i;
-    
-    for ( i = order; i <= SHADOW_MAX_ORDER; i++ )
-        if ( !list_empty(&d->arch.paging.shadow.freelists[i]) )
-            return 1;
+    return is_hvm_domain(d) ? SHADOW_MAX_ORDER : 0;
+}
+
+/* Do we have at total of count pages of the requested order free? */
+static inline int space_is_available(
+    struct domain *d,
+    unsigned int order,
+    unsigned int count)
+{
+    for ( ; order <= shadow_max_order(d); ++order )
+    {
+        unsigned int n = count;
+        const struct list_head *p;
+
+        list_for_each ( p, &d->arch.paging.shadow.freelists[order] )
+            if ( --n == 0 )
+                return 1;
+        count = (count + 1) >> 1;
+    }
+
     return 0;
 }
 
@@ -814,12 +829,12 @@ static void shadow_unhook_mappings(struct vcpu *v, mfn_t smfn)
 }
 
 
-/* Make sure there is at least one chunk of the required order available
- * in the shadow page pool. This must be called before any calls to
- * shadow_alloc().  Since this will free existing shadows to make room,
- * it must be called early enough to avoid freeing shadows that the
- * caller is currently working on. */
-void shadow_prealloc(struct domain *d, unsigned int order)
+/* Make sure there are at least count order-sized pages
+ * available in the shadow page pool. */
+static void _shadow_prealloc(
+    struct domain *d,
+    unsigned int order,
+    unsigned int count)
 {
     /* Need a vpcu for calling unpins; for now, since we don't have
      * per-vcpu shadows, any will do */
@@ -830,7 +845,8 @@ void shadow_prealloc(struct domain *d, unsigned int order)
     mfn_t smfn;
     int i;
 
-    if ( chunk_is_available(d, order) ) return; 
+    ASSERT(order <= shadow_max_order(d));
+    if ( space_is_available(d, order, count) ) return;
     
     v = current;
     if ( v->domain != d )
@@ -847,8 +863,8 @@ void shadow_prealloc(struct domain *d, unsigned int order)
         /* Unpin this top-level shadow */
         sh_unpin(v, smfn);
 
-        /* See if that freed up a chunk of appropriate size */
-        if ( chunk_is_available(d, order) ) return;
+        /* See if that freed up enough space */
+        if ( space_is_available(d, order, count) ) return;
     }
 
     /* Stage two: all shadow pages are in use in hierarchies that are
@@ -865,8 +881,8 @@ void shadow_prealloc(struct domain *d, unsigned int order)
                                pagetable_get_mfn(v2->arch.shadow_table[i]));
                 cpus_or(flushmask, v2->vcpu_dirty_cpumask, flushmask);
 
-                /* See if that freed up a chunk of appropriate size */
-                if ( chunk_is_available(d, order) ) 
+                /* See if that freed up enough space */
+                if ( space_is_available(d, order, count) )
                 {
                     flush_tlb_mask(flushmask);
                     return;
@@ -876,15 +892,26 @@ void shadow_prealloc(struct domain *d, unsigned int order)
     
     /* Nothing more we can do: all remaining shadows are of pages that
      * hold Xen mappings for some vcpu.  This can never happen. */
-    SHADOW_ERROR("Can't pre-allocate %i shadow pages!\n"
+    SHADOW_ERROR("Can't pre-allocate %u order-%u shadow pages!\n"
                  "  shadow pages total = %u, free = %u, p2m=%u\n",
-                 1 << order,
+                 count, order,
                  d->arch.paging.shadow.total_pages,
                  d->arch.paging.shadow.free_pages,
                  d->arch.paging.shadow.p2m_pages);
     BUG();
 }
 
+/* Make sure there are at least count pages of the order according to
+ * type available in the shadow page pool.
+ * This must be called before any calls to shadow_alloc().  Since this
+ * will free existing shadows to make room, it must be called early enough
+ * to avoid freeing shadows that the caller is currently working on. */
+void shadow_prealloc(struct domain *d, u32 type, unsigned int count)
+{
+    ASSERT(type != SH_type_p2m_table);
+    return _shadow_prealloc(d, shadow_order(type), count);
+}
+
 /* Deliberately free all the memory we can: this will tear down all of
  * this domain's shadows */
 static void shadow_blow_tables(struct domain *d) 
@@ -961,7 +988,9 @@ mfn_t shadow_alloc(struct domain *d,
     int i;
 
     ASSERT(shadow_locked_by_me(d));
-    ASSERT(order <= SHADOW_MAX_ORDER);
+    if (shadow_type == SH_type_p2m_table && order > shadow_max_order(d))
+        order = shadow_max_order(d);
+    ASSERT(order <= shadow_max_order(d));
     ASSERT(shadow_type != SH_type_none);
     perfc_incr(shadow_alloc);
 
@@ -1062,7 +1091,7 @@ void shadow_free(struct domain *d, mfn_t smfn)
     }
 
     /* Merge chunks as far as possible. */
-    while ( order < SHADOW_MAX_ORDER )
+    for ( ; order < shadow_max_order(d); ++order )
     {
         mask = 1 << order;
         if ( (mfn_x(shadow_page_to_mfn(sp)) & mask) ) {
@@ -1077,7 +1106,6 @@ void shadow_free(struct domain *d, mfn_t smfn)
                 break;
             list_del(&(sp+mask)->list);
         }
-        order++;
     }
 
     sp->order = order;
@@ -1099,16 +1127,18 @@ sh_alloc_p2m_pages(struct domain *d)
 {
     struct page_info *pg;
     u32 i;
+    unsigned int order = shadow_max_order(d);
+
     ASSERT(shadow_locked_by_me(d));
     
     if ( d->arch.paging.shadow.total_pages 
-         < (shadow_min_acceptable_pages(d) + (1<<SHADOW_MAX_ORDER)) )
+         < (shadow_min_acceptable_pages(d) + (1 << order)) )
         return 0; /* Not enough shadow memory: need to increase it first */
     
     pg = mfn_to_page(shadow_alloc(d, SH_type_p2m_table, 0));
-    d->arch.paging.shadow.p2m_pages += (1<<SHADOW_MAX_ORDER);
-    d->arch.paging.shadow.total_pages -= (1<<SHADOW_MAX_ORDER);
-    for (i = 0; i < (1<<SHADOW_MAX_ORDER); i++)
+    d->arch.paging.shadow.p2m_pages += (1 << order);
+    d->arch.paging.shadow.total_pages -= (1 << order);
+    for (i = 0; i < (1U << order); i++)
     {
         /* Unlike shadow pages, mark p2m pages as owned by the domain.
          * Marking the domain as the owner would normally allow the guest to
@@ -1228,7 +1258,7 @@ static unsigned int sh_set_allocation(struct domain *d,
 {
     struct shadow_page_info *sp;
     unsigned int lower_bound;
-    int j;
+    unsigned int j, order = shadow_max_order(d);
 
     ASSERT(shadow_locked_by_me(d));
     
@@ -1249,15 +1279,15 @@ static unsigned int sh_set_allocation(struct domain *d,
         {
             /* Need to allocate more memory from domheap */
             sp = (struct shadow_page_info *)
-                alloc_domheap_pages(NULL, SHADOW_MAX_ORDER, 0); 
+                alloc_domheap_pages(NULL, order, 0);
             if ( sp == NULL ) 
             { 
                 SHADOW_PRINTK("failed to allocate shadow pages.\n");
                 return -ENOMEM;
             }
-            d->arch.paging.shadow.free_pages += 1<<SHADOW_MAX_ORDER;
-            d->arch.paging.shadow.total_pages += 1<<SHADOW_MAX_ORDER;
-            for ( j = 0; j < 1<<SHADOW_MAX_ORDER; j++ ) 
+            d->arch.paging.shadow.free_pages += 1 << order;
+            d->arch.paging.shadow.total_pages += 1 << order;
+            for ( j = 0; j < 1U << order; j++ )
             {
                 sp[j].type = 0;  
                 sp[j].pinned = 0;
@@ -1265,21 +1295,20 @@ static unsigned int sh_set_allocation(struct domain *d,
                 sp[j].mbz = 0;
                 sp[j].tlbflush_timestamp = 0; /* Not in any TLB */
             }
-            sp->order = SHADOW_MAX_ORDER;
-            list_add_tail(&sp->list, 
-                          &d->arch.paging.shadow.freelists[SHADOW_MAX_ORDER]);
+            sp->order = order;
+            list_add_tail(&sp->list, &d->arch.paging.shadow.freelists[order]);
         } 
         else if ( d->arch.paging.shadow.total_pages > pages ) 
         {
             /* Need to return memory to domheap */
-            shadow_prealloc(d, SHADOW_MAX_ORDER);
-            ASSERT(!list_empty(&d->arch.paging.shadow.freelists[SHADOW_MAX_ORDER]));
-            sp = list_entry(d->arch.paging.shadow.freelists[SHADOW_MAX_ORDER].next, 
+            _shadow_prealloc(d, order, 1);
+            ASSERT(!list_empty(&d->arch.paging.shadow.freelists[order]));
+            sp = list_entry(d->arch.paging.shadow.freelists[order].next,
                             struct shadow_page_info, list);
             list_del(&sp->list);
-            d->arch.paging.shadow.free_pages -= 1<<SHADOW_MAX_ORDER;
-            d->arch.paging.shadow.total_pages -= 1<<SHADOW_MAX_ORDER;
-            free_domheap_pages((struct page_info *)sp, SHADOW_MAX_ORDER);
+            d->arch.paging.shadow.free_pages -= 1 << order;
+            d->arch.paging.shadow.total_pages -= 1 << order;
+            free_domheap_pages((struct page_info *)sp, order);
         }
 
         /* Check to see if we need to yield and try again */
diff --git a/arch/x86/mm/shadow/multi.c b/arch/x86/mm/shadow/multi.c
index 2c2f98b..c6cefd0 100644
--- a/arch/x86/mm/shadow/multi.c
+++ b/arch/x86/mm/shadow/multi.c
@@ -1668,7 +1668,7 @@ sh_make_monitor_table(struct vcpu *v)
     ASSERT(pagetable_get_pfn(v->arch.monitor_table) == 0);
     
     /* Guarantee we can get the memory we need */
-    shadow_prealloc(d, SHADOW_MAX_ORDER);
+    shadow_prealloc(d, SH_type_monitor_table, CONFIG_PAGING_LEVELS - 1);
 
 #if CONFIG_PAGING_LEVELS == 4    
     {
@@ -2822,10 +2822,13 @@ static int sh_page_fault(struct vcpu *v,
     }
 
     /* Make sure there is enough free shadow memory to build a chain of
-     * shadow tables: one SHADOW_MAX_ORDER chunk will always be enough
-     * to allocate all we need.  (We never allocate a top-level shadow
-     * on this path, only a 32b l1, pae l2+1 or 64b l3+2+1) */
-    shadow_prealloc(d, SHADOW_MAX_ORDER);
+     * shadow tables. (We never allocate a top-level shadow on this path,
+     * only a 32b l1, pae l1, or 64b l3+2+1. Note that while
+     * SH_type_l1_shadow isn't correct in the latter case, all page
+     * tables are the same size there.) */
+    shadow_prealloc(d,
+                    SH_type_l1_shadow,
+                    GUEST_PAGING_LEVELS < 4 ? 1 : GUEST_PAGING_LEVELS - 1);
 
     /* Acquire the shadow.  This must happen before we figure out the rights 
      * for the shadow entry, since we might promote a page here. */
@@ -3446,7 +3449,7 @@ sh_set_toplevel_shadow(struct vcpu *v,
     if ( !mfn_valid(smfn) )
     {
         /* Make sure there's enough free shadow memory. */
-        shadow_prealloc(d, SHADOW_MAX_ORDER); 
+        shadow_prealloc(d, root_type, 1);
         /* Shadow the page. */
         smfn = sh_make_shadow(v, gmfn, root_type);
     }
diff --git a/arch/x86/mm/shadow/private.h b/arch/x86/mm/shadow/private.h
index 2944095..2006a5c 100644
--- a/arch/x86/mm/shadow/private.h
+++ b/arch/x86/mm/shadow/private.h
@@ -359,7 +359,7 @@ void shadow_promote(struct vcpu *v, mfn_t gmfn, u32 type);
 void shadow_demote(struct vcpu *v, mfn_t gmfn, u32 type);
 
 /* Shadow page allocation functions */
-void  shadow_prealloc(struct domain *d, unsigned int order);
+void  shadow_prealloc(struct domain *d, u32 shadow_type, unsigned int count);
 mfn_t shadow_alloc(struct domain *d, 
                     u32 shadow_type,
                     unsigned long backpointer);