diff -r f1fb228b43ac xen/arch/x86/mm/shadow/multi.c
--- a/xen/arch/x86/mm/shadow/multi.c	Mon Aug 31 09:45:27 2009 +0100
+++ b/xen/arch/x86/mm/shadow/multi.c	Wed Oct 07 11:08:44 2009 +0100
@@ -3266,7 +3266,10 @@
                 regs->error_code | PFEC_page_present);
 #endif /* (SHADOW_OPTIMIZATIONS & SHOPT_VIRTUAL_TLB) */
 
-    shadow_lock(d);
+    /* We can reach here with the lcok held if we took the "rewalk" path. 
+     * We checked for recursive faults already, so this is OK. */
+    if ( !shadow_locked_by_me(d) )
+        shadow_lock(d);
 
     /* Make sure there is enough free shadow memory to build a chain of
      * shadow tables. (We never allocate a top-level shadow on this path,
@@ -3298,7 +3301,6 @@
     /* Second bit set: Resynced a page. Re-walk needed. */
     if ( rc & GW_RMWR_REWALK )
     {
-        shadow_unlock(d);
         goto rewalk;
     }
 #endif /* OOS */
@@ -3306,7 +3308,6 @@
     if ( !shadow_check_gwalk(v, va, &gw) )
     {
         perfc_incr(shadow_inconsistent_gwalk);
-        shadow_unlock(d);
         goto rewalk;
     }