[PATCH v15 04/10] x86/shadow: reduce amount of work to do by shadow_unhook_mappings()

[Jan Beulich <jbeulich@xxxxxxxx>]

When preemption is enabled for uses of shadow_blow_tables(), the
granularity of preemption checks in both of the present two passes can
be pretty coarse, as deep table hierarchies may need processing. Reduce
shadow page table depth up front by introducing a third (earlier) pass
processing first L2, then L3 tables by doing hash lookups instead of
tree traversal.

Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
The way need for preemption is being checked for is crude, but the least
intrusive variant I could think of while still respecting hash_foreach()
not permitting further traversal after a removal from the hash.

I've deliberately chosen 0 as the "wildcard", as using INVALID_MFN looks
somewhat more fragile/risky to me. Of course we might consider
introducing WILDCARD_MFN, which then could be non-zero but still
distinct from INVALID_MFN.

I've further deliberately made hash_foreach() return "int", not "bool",
since at least transiently I was also playing with returning -ERESTART
from some of the callback functions.

We could avoid the hash walk for guests which never entered 64-bit mode.
That would require tracking the maximum shadow paging level that was
ever used (perhaps since the last [completed] shadow_blow_tables()) by a
domain. (This would similarly apply to future 5-level support, where we
could avoid the SHF_L4_ANY walk for guests never having entered 5-level
mode.)

The same may want (need) adding to _shadow_prealloc() and perhaps
elsewhere. However, for zapping entries from alive domains hash lookup
pulling most recently used entries to the front means most recently used
entries would then also be zapped first, which isn't very nice.
---
v14: Exclude 32-bit L2 types. Re-base.
v13: New.

--- a/xen/arch/x86/mm/shadow/common.c
+++ b/xen/arch/x86/mm/shadow/common.c
@@ -268,6 +268,32 @@ sh_validate_guest_entry(struct vcpu *v,
     return result;
 }
 
+typedef int (*hash_callback_t)(struct domain *d, mfn_t smfn, mfn_t other_mfn);
+
+#define HASH_CALLBACKS_CHECK(mask) \
+    BUILD_BUG_ON((mask) > (1U << ARRAY_SIZE(callbacks)) - 1)
+
+static int hash_foreach(struct domain *d,
+                        unsigned int callback_mask,
+                        const hash_callback_t callbacks[],
+                        mfn_t callback_mfn);
+
+/*
+ * Dispatch table for getting per-type functions: each level must
+ * be called with the function to remove a lower-level shadow.
+ */
+static const hash_callback_t remove_callbacks[SH_type_unused] = {
+#ifdef CONFIG_HVM
+    [SH_type_l2_32_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 2),
+    [SH_type_l2_pae_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 3),
+#endif
+    [SH_type_l2_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 4),
+#ifdef CONFIG_PV32
+    [SH_type_l2h_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 4),
+#endif
+    [SH_type_l3_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l2_shadow, 4),
+    [SH_type_l4_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l3_shadow, 4),
+};
 
 /**************************************************************************/
 /* Memory management for shadow pages. */
@@ -476,7 +502,35 @@ void shadow_blow_tables(struct domain *d
     if ( !d->vcpu[0] )
         return;
 
-    /* Pass one: unpin all pinned pages */
+    /* First pass: reduce page table depth */
+    if ( preempted )
+    {
+#define callbacks remove_callbacks
+        static const unsigned int masks[] = {
+            SHF_L2_ANY & ~(SHF_L2_32 | SHF_L2_PAE),
+            SHF_L3_ANY,
+#if CONFIG_PAGING_LEVELS > 4
+            SHF_L4_ANY,
+#endif
+        };
+
+        HASH_CALLBACKS_CHECK(SHF_page_type_mask & ~(SHF_L1_ANY | SHF_FL1_ANY));
+
+        for ( i = 0; i < ARRAY_SIZE(masks); ++i )
+        {
+            while ( hash_foreach(d, masks[i], callbacks, _mfn(0)) )
+            {
+                if ( general_preempt_check() )
+                {
+                    *preempted = true;
+                    return;
+                }
+            }
+        }
+#undef callbacks
+    }
+
+    /* Second pass: unpin all pinned pages */
     foreach_pinned_shadow(d, sp, t)
     {
         smfn = page_to_mfn(sp);
@@ -488,7 +542,7 @@ void shadow_blow_tables(struct domain *d
         }
     }
 
-    /* Second pass: unhook entries of in-use shadows */
+    /* Third pass: unhook entries of in-use shadows */
     for_each_vcpu(d, v)
         for ( i = 0; i < ARRAY_SIZE(v->arch.paging.shadow.shadow_table); i++ )
             if ( !pagetable_is_null(v->arch.paging.shadow.shadow_table[i]) )
@@ -1151,15 +1205,10 @@ bool shadow_hash_delete(struct domain *d
     return true;
 }
 
-typedef int (*hash_callback_t)(struct domain *d, mfn_t smfn, mfn_t other_mfn);
-
-#define HASH_CALLBACKS_CHECK(mask) \
-    BUILD_BUG_ON((mask) > (1U << ARRAY_SIZE(callbacks)) - 1)
-
-static void hash_foreach(struct domain *d,
-                         unsigned int callback_mask,
-                         const hash_callback_t callbacks[],
-                         mfn_t callback_mfn)
+static int hash_foreach(struct domain *d,
+                        unsigned int callback_mask,
+                        const hash_callback_t callbacks[],
+                        mfn_t callback_mfn)
 /* Walk the hash table looking at the types of the entries and
  * calling the appropriate callback function for each entry.
  * The mask determines which shadow types we call back for, and the array
@@ -1176,7 +1225,7 @@ static void hash_foreach(struct domain *
 
     /* Can be called via p2m code &c after shadow teardown. */
     if ( unlikely(!d->arch.paging.shadow.hash_table) )
-        return;
+        return 0;
 
     /* Say we're here, to stop hash-lookups reordering the chains */
     ASSERT(d->arch.paging.shadow.hash_walking == 0);
@@ -1201,6 +1250,8 @@ static void hash_foreach(struct domain *
         if ( done ) break;
     }
     d->arch.paging.shadow.hash_walking = 0;
+
+    return done;
 }
 
 
@@ -1640,21 +1691,6 @@ void sh_remove_shadows(struct domain *d,
     mfn_t smfn;
     unsigned char t;
 
-    /* Dispatch table for getting per-type functions: each level must
-     * be called with the function to remove a lower-level shadow. */
-    static const hash_callback_t callbacks[SH_type_unused] = {
-#ifdef CONFIG_HVM
-        [SH_type_l2_32_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 2),
-        [SH_type_l2_pae_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 3),
-#endif
-        [SH_type_l2_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 4),
-#ifdef CONFIG_PV32
-        [SH_type_l2h_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l1_shadow, 4),
-#endif
-        [SH_type_l3_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l2_shadow, 4),
-        [SH_type_l4_64_shadow] = SHADOW_INTERNAL_NAME(sh_remove_l3_shadow, 4),
-    };
-
     /* Another lookup table, for choosing which mask to use */
     static const unsigned int masks[SH_type_unused] = {
 #ifdef CONFIG_HVM
@@ -1689,6 +1725,8 @@ void sh_remove_shadows(struct domain *d,
     /* Search for this shadow in all appropriate shadows */
     perfc_incr(shadow_unshadow);
 
+#define callbacks remove_callbacks
+
     /*
      * Lower-level shadows need to be excised from upper-level shadows. This
      * call to hash_foreach() looks dangerous but is in fact OK: each call
@@ -1736,6 +1774,7 @@ void sh_remove_shadows(struct domain *d,
     DO_UNSHADOW(SH_type_l1_64_shadow);
 
 #undef DO_UNSHADOW
+#undef callbacks
 
     /* If that didn't catch the shadows, something is wrong */
     if ( !fast && all && (pg->count_info & PGC_shadowed_pt) )
--- a/xen/arch/x86/mm/shadow/multi.c
+++ b/xen/arch/x86/mm/shadow/multi.c
@@ -3644,10 +3644,12 @@ int cf_check sh_remove_l1_shadow(struct
 
     FOREACH_PRESENT_L2E(sl2mfn, sl2e, NULL, done, d,
     {
-        if ( mfn_eq(shadow_l2e_get_mfn(*sl2e), sl1mfn) )
+        mfn_t mfn = shadow_l2e_get_mfn(*sl2e);
+
+        if ( !mfn_x(sl1mfn) || mfn_eq(mfn, sl1mfn) )
         {
             shadow_set_l2e(d, sl2e, shadow_l2e_empty(), sl2mfn);
-            if ( mfn_to_page(sl1mfn)->u.sh.type == 0 )
+            if ( !mfn_to_page(mfn)->u.sh.type )
                 /* This breaks us cleanly out of the FOREACH macro */
                 done = 1;
         }
@@ -3664,10 +3666,12 @@ int cf_check sh_remove_l2_shadow(struct
 
     FOREACH_PRESENT_L3E(sl3mfn, sl3e, NULL, done,
     {
-        if ( mfn_eq(shadow_l3e_get_mfn(*sl3e), sl2mfn) )
+        mfn_t mfn = shadow_l3e_get_mfn(*sl3e);
+
+        if ( !mfn_x(sl2mfn) || mfn_eq(mfn, sl2mfn) )
         {
             shadow_set_l3e(d, sl3e, shadow_l3e_empty(), sl3mfn);
-            if ( mfn_to_page(sl2mfn)->u.sh.type == 0 )
+            if ( !mfn_to_page(mfn)->u.sh.type )
                 /* This breaks us cleanly out of the FOREACH macro */
                 done = 1;
         }
@@ -3683,10 +3687,12 @@ int cf_check sh_remove_l3_shadow(struct
 
     FOREACH_PRESENT_L4E(sl4mfn, sl4e, NULL, done, d,
     {
-        if ( mfn_eq(shadow_l4e_get_mfn(*sl4e), sl3mfn) )
+        mfn_t mfn = shadow_l4e_get_mfn(*sl4e);
+
+        if ( !mfn_x(sl3mfn) || mfn_eq(mfn, sl3mfn) )
         {
             shadow_set_l4e(d, sl4e, shadow_l4e_empty(), sl4mfn);
-            if ( mfn_to_page(sl3mfn)->u.sh.type == 0 )
+            if ( !mfn_to_page(mfn)->u.sh.type )
                 /* This breaks us cleanly out of the FOREACH macro */
                 done = 1;
         }
--- a/xen/arch/x86/mm/shadow/private.h
+++ b/xen/arch/x86/mm/shadow/private.h
@@ -282,6 +282,9 @@ static inline void sh_terminate_list(str
 
 #define SHF_L1_ANY  (SHF_L1_32|SHF_L1_PAE|SHF_L1_64)
 #define SHF_FL1_ANY (SHF_FL1_32|SHF_FL1_PAE|SHF_FL1_64)
+#define SHF_L2_ANY  (SHF_L2_32|SHF_L2_PAE|SHF_L2H_64|SHF_L2_64)
+#define SHF_L3_ANY  SHF_L3_64
+#define SHF_L4_ANY  SHF_L4_64
 
 #if (SHADOW_OPTIMIZATIONS & SHOPT_OUT_OF_SYNC)
 /* Marks a guest L1 page table which is shadowed but not write-protected.