Changeset 93716 in vbox for trunk/src/VBox

Timestamp:

Feb 14, 2022 10:36:21 AM (3 years ago)

Author:

vboxsync

Message:

VMM/PGM: Moved the physical handler allocation off the hyper heap and into its own slab, changing the it to the 'hardened' avl tree code. bugref:10093

Location:

trunk/src/VBox/VMM

Files:

• VMMAll/PGMAllBth.h (modified) (4 diffs)
• VMMAll/PGMAllHandler.cpp (modified) (43 diffs)
• VMMAll/PGMAllPhys.cpp (modified) (10 diffs)
• VMMR0/PGMR0.cpp (modified) (5 diffs)
• VMMR0/VMMR0.cpp (modified) (1 diff)
• VMMR3/PGM.cpp (modified) (10 diffs)
• VMMR3/PGMDbg.cpp (modified) (1 diff)
• VMMR3/PGMHandler.cpp (modified) (9 diffs)
• VMMR3/PGMPool.cpp (modified) (1 diff)
• VMMR3/PGMSavedState.cpp (modified) (1 diff)
• VMMR3/PGMSharedPage.cpp (modified) (1 diff)
• include/PGMInline.h (modified) (1 diff)
• include/PGMInternal.h (modified) (13 diffs)

trunk/src/VBox/VMM/VMMAll/PGMAllBth.h

@@ -240 +240 @@
         const RTGCPHYS  GCPhysFault = PGM_A20_APPLY(pVCpu, (RTGCPHYS)pvFault);
 # endif
-        PPGMPHYSHANDLER pCur = pgmHandlerPhysicalLookup(pVM, GCPhysFault);
-        if (pCur)
+        PPGMPHYSHANDLER pCur;
+        rcStrict = pgmHandlerPhysicalLookup(pVM, GCPhysFault, &pCur);
+        if (RT_SUCCESS(rcStrict))
         {
             PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE(pVM, pCur);
@@ -322 +323 @@
                                                       : (uintptr_t)PDMDeviceRing0IdxToInstance(pVM, pCur->uUser));
 
-#  ifdef VBOX_WITH_STATISTICS
-                    pCur = pgmHandlerPhysicalLookup(pVM, GCPhysFault); /* paranoia in case the handler deregistered itself */
-                    if (pCur)
-                        STAM_PROFILE_STOP(&pCur->Stat, h);
-#  endif
+                    STAM_PROFILE_STOP(&pCur->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
                 }
                 else
@@ -337 +334 @@
                     rcStrict = pCurType->pfnPfHandler(pVM, pVCpu, uErr, pRegFrame, pvFault, GCPhysFault, uUser);
 
-#  ifdef VBOX_WITH_STATISTICS
-                    PGM_LOCK_VOID(pVM);
-                    pCur = pgmHandlerPhysicalLookup(pVM, GCPhysFault);
-                    if (pCur)
-                        STAM_PROFILE_STOP(&pCur->Stat, h);
-                    PGM_UNLOCK(pVM);
-#  endif
+                    STAM_PROFILE_STOP(&pCur->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
                 }
             }
@@ -352 +343 @@
             return rcStrict;
         }
+        AssertMsgReturn(rcStrict == VERR_NOT_FOUND, ("%Rrc\n", VBOXSTRICTRC_VAL(rcStrict)), rcStrict);
     }
 

trunk/src/VBox/VMM/VMMAll/PGMAllHandler.cpp

@@ -111 +111 @@
 
 /**
- * Creates a physical access handler.
+ * Creates a physical access handler, allocation part.
  *
  * @returns VBox status code.
- * @retval  VINF_SUCCESS when successfully installed.
- * @retval  VINF_PGM_GCPHYS_ALIASED when the shadow PTs could be updated because
- *          the guest page aliased or/and mapped by multiple PTs. A CR3 sync has been
- *          flagged together with a pool clearing.
- * @retval  VERR_PGM_HANDLER_PHYSICAL_CONFLICT if the range conflicts with an existing
- *          one. A debug assertion is raised.
+ * @retval  VERR_OUT_OF_RESOURCES if no more handlers available.
  *
  * @param   pVM             The cross context VM structure.
@@ -146 +141 @@
      * Allocate and initialize the new entry.
      */
-    PPGMPHYSHANDLER pNew;
-    int rc = MMHyperAlloc(pVM, sizeof(*pNew), 0, MM_TAG_PGM_HANDLERS, (void **)&pNew);
-    if (RT_SUCCESS(rc))
-    {
-        pNew->Core.Key      = NIL_RTGCPHYS;
-        pNew->Core.KeyLast  = NIL_RTGCPHYS;
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
+
+    PPGMPHYSHANDLER pNew = pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.allocateNode();
+    if (pNew)
+    {
+        pNew->Key           = NIL_RTGCPHYS;
+        pNew->KeyLast       = NIL_RTGCPHYS;
         pNew->cPages        = 0;
         pNew->cAliasedPages = 0;
@@ -163 +160 @@
                             : pVM->pgm.s.aPhysHandlerTypes[hType & PGMPHYSHANDLERTYPE_IDX_MASK].pszDesc;
 #endif
+
+        PGM_UNLOCK(pVM);
         *ppPhysHandler = pNew;
         return VINF_SUCCESS;
     }
 
-    return rc;
+    PGM_UNLOCK(pVM);
+    return VERR_OUT_OF_RESOURCES;
 }
 
@@ -194 +194 @@
  * @returns VBox status code.
  * @retval  VINF_SUCCESS when successfully installed.
+ * @retval  VINF_PGM_GCPHYS_ALIASED could be returned.
  *
  * @param   pVM             The cross context VM structure.
@@ -205 +206 @@
      * Validate input.
      */
+    AssertReturn(pPhysHandler, VERR_INVALID_POINTER);
     PGMPHYSHANDLERTYPE const      hType = pPhysHandler->hType;
     PCPGMPHYSHANDLERTYPEINT const pType = pgmHandlerPhysicalTypeHandleToPtr(pVM, hType);
@@ -214 +216 @@
     Log(("pgmHandlerPhysicalExRegister: GCPhys=%RGp GCPhysLast=%RGp hType=%#x (%d, %s) pszDesc=%RHv:%s\n", GCPhys, GCPhysLast,
          hType, pType->enmKind, pType->pszDesc, pPhysHandler->pszDesc, R3STRING(pPhysHandler->pszDesc)));
-    AssertReturn(pPhysHandler->Core.Key == NIL_RTGCPHYS, VERR_WRONG_ORDER);
+    AssertReturn(pPhysHandler->Key == NIL_RTGCPHYS, VERR_WRONG_ORDER);
 
     AssertMsgReturn(GCPhys < GCPhysLast, ("GCPhys >= GCPhysLast (%#x >= %#x)\n", GCPhys, GCPhysLast), VERR_INVALID_PARAMETER);
+    Assert(GCPhysLast - GCPhys < _4G); /* ASSUMPTION in PGMAllPhys.cpp */
+
     switch (pType->enmKind)
     {
@@ -252 +256 @@
      * Try insert into list.
      */
-    pPhysHandler->Core.Key     = GCPhys;
-    pPhysHandler->Core.KeyLast = GCPhysLast;
-    pPhysHandler->cPages       = (GCPhysLast - (GCPhys & X86_PTE_PAE_PG_MASK) + GUEST_PAGE_SIZE) >> GUEST_PAGE_SHIFT;
-
-    PGM_LOCK_VOID(pVM);
-    if (RTAvlroGCPhysInsert(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, &pPhysHandler->Core))
-    {
-        int rc = pgmHandlerPhysicalSetRamFlagsAndFlushShadowPTs(pVM, pPhysHandler, pRam, NULL /*pvBitmap*/, 0 /*offBitmap*/);
-        if (rc == VINF_PGM_SYNC_CR3)
-            rc = VINF_PGM_GCPHYS_ALIASED;
+    pPhysHandler->Key     = GCPhys;
+    pPhysHandler->KeyLast = GCPhysLast;
+    pPhysHandler->cPages  = (GCPhysLast - (GCPhys & X86_PTE_PAE_PG_MASK) + GUEST_PAGE_SIZE) >> GUEST_PAGE_SHIFT;
+
+    int rc = PGM_LOCK(pVM);
+    if (RT_SUCCESS(rc))
+    {
+        rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->insert(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, pPhysHandler);
+        if (RT_SUCCESS(rc))
+        {
+            rc = pgmHandlerPhysicalSetRamFlagsAndFlushShadowPTs(pVM, pPhysHandler, pRam, NULL /*pvBitmap*/, 0 /*offBitmap*/);
+            if (rc == VINF_PGM_SYNC_CR3)
+                rc = VINF_PGM_GCPHYS_ALIASED;
 
 #if defined(IN_RING3) || defined(IN_RING0)
-        NEMHCNotifyHandlerPhysicalRegister(pVM, pType->enmKind, GCPhys, GCPhysLast - GCPhys + 1);
-#endif
+            NEMHCNotifyHandlerPhysicalRegister(pVM, pType->enmKind, GCPhys, GCPhysLast - GCPhys + 1);
+#endif
+            PGM_UNLOCK(pVM);
+
+            if (rc != VINF_SUCCESS)
+                Log(("PGMHandlerPhysicalRegisterEx: returns %Rrc (%RGp-%RGp)\n", rc, GCPhys, GCPhysLast));
+            return rc;
+        }
         PGM_UNLOCK(pVM);
-
-        if (rc != VINF_SUCCESS)
-            Log(("PGMHandlerPhysicalRegisterEx: returns %Rrc (%RGp-%RGp)\n", rc, GCPhys, GCPhysLast));
-        return rc;
-    }
-    PGM_UNLOCK(pVM);
-
-    pPhysHandler->Core.Key     = NIL_RTGCPHYS;
-    pPhysHandler->Core.KeyLast = NIL_RTGCPHYS;
+    }
+
+    pPhysHandler->Key     = NIL_RTGCPHYS;
+    pPhysHandler->KeyLast = NIL_RTGCPHYS;
+
+    AssertMsgReturn(rc == VERR_ALREADY_EXISTS, ("%Rrc GCPhys=%RGp GCPhysLast=%RGp\n", rc, GCPhys, GCPhysLast), rc);
 
 #if defined(IN_RING3) && defined(VBOX_STRICT)
@@ -352 +362 @@
     const unsigned          uState     = pCurType->uState;
     uint32_t                cPages     = pCur->cPages;
-    uint32_t                i          = (pCur->Core.Key - pRam->GCPhys) >> GUEST_PAGE_SHIFT;
+    uint32_t                i          = (pCur->Key - pRam->GCPhys) >> GUEST_PAGE_SHIFT;
     for (;;)
     {
@@ -415 +425 @@
 {
     LogFlow(("pgmHandlerPhysicalExDeregister: Removing Range %RGp-%RGp %s\n",
-             pPhysHandler->Core.Key, pPhysHandler->Core.KeyLast, R3STRING(pPhysHandler->pszDesc)));
-    AssertReturn(pPhysHandler->Core.Key != NIL_RTGCPHYS, VERR_PGM_HANDLER_NOT_FOUND);
+             pPhysHandler->Key, pPhysHandler->KeyLast, R3STRING(pPhysHandler->pszDesc)));
+
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
+
+    RTGCPHYS const GCPhys = pPhysHandler->Key;
+    AssertReturnStmt(GCPhys != NIL_RTGCPHYS, PGM_UNLOCK(pVM), VERR_PGM_HANDLER_NOT_FOUND);
 
     /*
      * Remove the handler from the tree.
      */
-    PGM_LOCK_VOID(pVM);
-    PPGMPHYSHANDLER pRemoved = (PPGMPHYSHANDLER)RTAvlroGCPhysRemove(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers,
-                                                                    pPhysHandler->Core.Key);
-    if (pRemoved == pPhysHandler)
-    {
+
+    PPGMPHYSHANDLER pRemoved;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->remove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pRemoved);
+    if (RT_SUCCESS(rc))
+    {
+        if (pRemoved == pPhysHandler)
+        {
+            /*
+             * Clear the page bits, notify the REM about this change and clear
+             * the cache.
+             */
+            pgmHandlerPhysicalResetRamFlags(pVM, pPhysHandler);
+            if (VM_IS_NEM_ENABLED(pVM))
+                pgmHandlerPhysicalDeregisterNotifyNEM(pVM, pPhysHandler);
+            pVM->pgm.s.idxLastPhysHandler = 0;
+
+            pPhysHandler->Key     = NIL_RTGCPHYS;
+            pPhysHandler->KeyLast = NIL_RTGCPHYS;
+
+            PGM_UNLOCK(pVM);
+
+            return VINF_SUCCESS;
+        }
+
         /*
-         * Clear the page bits, notify the REM about this change and clear
-         * the cache.
+         * Both of the failure conditions here are considered internal processing
+         * errors because they can only be caused by race conditions or corruption.
+         * If we ever need to handle concurrent deregistration, we have to move
+         * the NIL_RTGCPHYS check inside the PGM lock.
          */
-        pgmHandlerPhysicalResetRamFlags(pVM, pPhysHandler);
-        if (VM_IS_NEM_ENABLED(pVM))
-            pgmHandlerPhysicalDeregisterNotifyNEM(pVM, pPhysHandler);
-        pVM->pgm.s.pLastPhysHandlerR0 = 0;
-        pVM->pgm.s.pLastPhysHandlerR3 = 0;
-
-        pPhysHandler->Core.Key     = NIL_RTGCPHYS;
-        pPhysHandler->Core.KeyLast = NIL_RTGCPHYS;
-
-        PGM_UNLOCK(pVM);
-
-        return VINF_SUCCESS;
-    }
-
-    /*
-     * Both of the failure conditions here are considered internal processing
-     * errors because they can only be caused by race conditions or corruption.
-     * If we ever need to handle concurrent deregistration, we have to move
-     * the NIL_RTGCPHYS check inside the PGM lock.
-     */
-    if (pRemoved)
-        RTAvlroGCPhysInsert(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, &pRemoved->Core);
+        pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->insert(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, pRemoved);
+    }
 
     PGM_UNLOCK(pVM);
 
-    if (!pRemoved)
-        AssertMsgFailed(("Didn't find range starting at %RGp in the tree!\n", pPhysHandler->Core.Key));
+    if (RT_FAILURE(rc))
+        AssertMsgFailed(("Didn't find range starting at %RGp in the tree! %Rrc=rc\n", GCPhys, rc));
     else
         AssertMsgFailed(("Found different handle at %RGp in the tree: got %p insteaded of %p\n",
-                         pPhysHandler->Core.Key, pRemoved, pPhysHandler));
+                         GCPhys, pRemoved, pPhysHandler));
     return VERR_PGM_HANDLER_IPE_1;
 }
@@ -478 +494 @@
     {
         AssertPtr(pHandler);
-        AssertReturn(pHandler->Core.Key == NIL_RTGCPHYS, VERR_WRONG_ORDER);
-        MMHyperFree(pVM, pHandler);
+        AssertReturn(pHandler->Key == NIL_RTGCPHYS, VERR_WRONG_ORDER);
+
+        int rc = PGM_LOCK(pVM);
+        if (RT_SUCCESS(rc))
+        {
+            rc = pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.freeNode(pHandler);
+            PGM_UNLOCK(pVM);
+        }
+        return rc;
     }
     return VINF_SUCCESS;
@@ -494 +517 @@
 VMMDECL(int)  PGMHandlerPhysicalDeregister(PVMCC pVM, RTGCPHYS GCPhys)
 {
+    AssertReturn(pVM->VMCC_CTX(pgm).s.pPhysHandlerTree, VERR_PGM_HANDLER_IPE_1);
+
     /*
      * Find the handler.
      */
-    PGM_LOCK_VOID(pVM);
-    PPGMPHYSHANDLER pRemoved = (PPGMPHYSHANDLER)RTAvlroGCPhysRemove(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (pRemoved)
-    {
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
+
+    PPGMPHYSHANDLER pRemoved;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->remove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pRemoved);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pRemoved->Key == GCPhys);
         LogFlow(("PGMHandlerPhysicalDeregister: Removing Range %RGp-%RGp %s\n",
-                 pRemoved->Core.Key, pRemoved->Core.KeyLast, R3STRING(pRemoved->pszDesc)));
+                 pRemoved->Key, pRemoved->KeyLast, R3STRING(pRemoved->pszDesc)));
 
         /*
@@ -511 +540 @@
         if (VM_IS_NEM_ENABLED(pVM))
             pgmHandlerPhysicalDeregisterNotifyNEM(pVM, pRemoved);
-        pVM->pgm.s.pLastPhysHandlerR0 = 0;
-        pVM->pgm.s.pLastPhysHandlerR3 = 0;
+        pVM->pgm.s.idxLastPhysHandler = 0;
+
+        pRemoved->Key = NIL_RTGCPHYS;
+        rc = pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.freeNode(pRemoved);
 
         PGM_UNLOCK(pVM);
-
-        pRemoved->Core.Key = NIL_RTGCPHYS;
-        pgmHandlerPhysicalExDestroy(pVM, pRemoved);
-        return VINF_SUCCESS;
+        return rc;
     }
 
     PGM_UNLOCK(pVM);
 
-    AssertMsgFailed(("Didn't find range starting at %RGp\n", GCPhys));
-    return VERR_PGM_HANDLER_NOT_FOUND;
+    if (rc == VERR_NOT_FOUND)
+    {
+        AssertMsgFailed(("Didn't find range starting at %RGp\n", GCPhys));
+        rc = VERR_PGM_HANDLER_NOT_FOUND;
+    }
+    return rc;
 }
 
@@ -535 +567 @@
 #ifdef VBOX_WITH_NATIVE_NEM
     PCPGMPHYSHANDLERTYPEINT pCurType    = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
-    RTGCPHYS                GCPhysStart = pCur->Core.Key;
-    RTGCPHYS                GCPhysLast  = pCur->Core.KeyLast;
+    RTGCPHYS                GCPhysStart = pCur->Key;
+    RTGCPHYS                GCPhysLast  = pCur->KeyLast;
 
     /*
@@ -545 +577 @@
      * included in the REM notification or not.
      */
-    if (   (pCur->Core.Key           & GUEST_PAGE_OFFSET_MASK)
-        || ((pCur->Core.KeyLast + 1) & GUEST_PAGE_OFFSET_MASK))
+    if (   (pCur->Key           & GUEST_PAGE_OFFSET_MASK)
+        || ((pCur->KeyLast + 1) & GUEST_PAGE_OFFSET_MASK))
     {
         Assert(pCurType->enmKind != PGMPHYSHANDLERKIND_MMIO);
@@ -614 +646 @@
     for (;;)
     {
-        PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGetBestFit(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys, fAbove);
-        if (   !pCur
-            || ((fAbove ? pCur->Core.Key : pCur->Core.KeyLast) >> GUEST_PAGE_SHIFT) != (GCPhys >> GUEST_PAGE_SHIFT))
+        PPGMPHYSHANDLER pCur;
+        int rc;
+        if (fAbove)
+            rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookupMatchingOrAbove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator,
+                                                                              GCPhys, &pCur);
+        else
+            rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookupMatchingOrBelow(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator,
+                                                                              GCPhys, &pCur);
+        if (rc == VERR_NOT_FOUND)
+            break;
+        AssertRCBreak(rc);
+        if (((fAbove ? pCur->Key : pCur->KeyLast) >> GUEST_PAGE_SHIFT) != (GCPhys >> GUEST_PAGE_SHIFT))
             break;
         PCPGMPHYSHANDLERTYPEINT pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
@@ -623 +664 @@
         /* next? */
         RTGCPHYS GCPhysNext = fAbove
-                            ? pCur->Core.KeyLast + 1
-                            : pCur->Core.Key - 1;
+                            ? pCur->KeyLast + 1
+                            : pCur->Key     - 1;
         if ((GCPhysNext >> GUEST_PAGE_SHIFT) != (GCPhys >> GUEST_PAGE_SHIFT))
             break;
@@ -714 +755 @@
     if (fDoAccounting)
     {
-        PPGMPHYSHANDLER pHandler = pgmHandlerPhysicalLookup(pVM, GCPhysPage);
-        if (RT_LIKELY(pHandler))
+        PPGMPHYSHANDLER pHandler;
+        rc = pgmHandlerPhysicalLookup(pVM, GCPhysPage, &pHandler);
+        if (RT_SUCCESS(rc))
         {
             Assert(pHandler->cAliasedPages > 0);
@@ -721 +763 @@
         }
         else
-            AssertFailed();
+            AssertMsgFailed(("rc=%Rrc GCPhysPage=%RGp\n", rc, GCPhysPage));
     }
 
@@ -760 +802 @@
      */
     RTUINT          cPages   = pCur->cPages;
-    RTGCPHYS        GCPhys   = pCur->Core.Key;
+    RTGCPHYS        GCPhys   = pCur->Key;
     PPGMRAMRANGE    pRamHint = NULL;
     for (;;)
@@ -815 +857 @@
      * Check for partial start and end pages.
      */
-    if (pCur->Core.Key & GUEST_PAGE_OFFSET_MASK)
-        pgmHandlerPhysicalRecalcPageState(pVM, pCur->Core.Key - 1, false /* fAbove */, &pRamHint);
-    if ((pCur->Core.KeyLast & GUEST_PAGE_OFFSET_MASK) != GUEST_PAGE_OFFSET_MASK)
-        pgmHandlerPhysicalRecalcPageState(pVM, pCur->Core.KeyLast + 1, true /* fAbove */, &pRamHint);
+    if (pCur->Key & GUEST_PAGE_OFFSET_MASK)
+        pgmHandlerPhysicalRecalcPageState(pVM, pCur->Key - 1, false /* fAbove */, &pRamHint);
+    if ((pCur->KeyLast & GUEST_PAGE_OFFSET_MASK) != GUEST_PAGE_OFFSET_MASK)
+        pgmHandlerPhysicalRecalcPageState(pVM, pCur->KeyLast + 1, true /* fAbove */, &pRamHint);
 }
 
@@ -945 +987 @@
      * Find the handler and make the change.
      */
-    int rc;
-    PGM_LOCK_VOID(pVM);
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (pCur)
-    {
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
+
+    PPGMPHYSHANDLER pCur;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
         pCur->uUser = uUser;
-        rc = VINF_SUCCESS;
-    }
-    else
+    }
+    else if (rc == VERR_NOT_FOUND)
     {
         AssertMsgFailed(("Didn't find range starting at %RGp\n", GCPhys));
@@ -1125 +1169 @@
 {
     LogFlow(("PGMHandlerPhysicalReset GCPhys=%RGp\n", GCPhys));
-    PGM_LOCK_VOID(pVM);
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
 
     /*
      * Find the handler.
      */
-    int rc;
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (RT_LIKELY(pCur))
-    {
+    PPGMPHYSHANDLER pCur;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
+
         /*
          * Validate kind.
@@ -1147 +1194 @@
                 PPGMRAMRANGE pRam = pgmPhysGetRange(pVM, GCPhys);
                 Assert(pRam);
-                Assert(pRam->GCPhys     <= pCur->Core.Key);
-                Assert(pRam->GCPhysLast >= pCur->Core.KeyLast);
+                Assert(pRam->GCPhys     <= pCur->Key);
+                Assert(pRam->GCPhysLast >= pCur->KeyLast);
 
                 if (pCurType->enmKind == PGMPHYSHANDLERKIND_MMIO)
@@ -1159 +1206 @@
                     if (pCur->cAliasedPages)
                     {
-                        PPGMPAGE    pPage      = &pRam->aPages[(pCur->Core.Key - pRam->GCPhys) >> GUEST_PAGE_SHIFT];
-                        RTGCPHYS    GCPhysPage = pCur->Core.Key;
+                        PPGMPAGE    pPage      = &pRam->aPages[(pCur->Key - pRam->GCPhys) >> GUEST_PAGE_SHIFT];
+                        RTGCPHYS    GCPhysPage = pCur->Key;
                         uint32_t    cLeft      = pCur->cPages;
                         while (cLeft-- > 0)
@@ -1206 +1253 @@
         }
     }
-    else
+    else if (rc == VERR_NOT_FOUND)
     {
         AssertMsgFailed(("Didn't find MMIO Range starting at %#x\n", GCPhys));
@@ -1238 +1285 @@
      * Find the handler.
      */
-    int rc;
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (RT_LIKELY(pCur))
-    {
+    PPGMPHYSHANDLER pCur;
+    int rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
+
         /*
          * Validate kind.
@@ -1253 +1302 @@
             PPGMRAMRANGE pRam = pgmPhysGetRange(pVM, GCPhys);
             Assert(pRam);
-            Assert(pRam->GCPhys     <= pCur->Core.Key);
-            Assert(pRam->GCPhysLast >= pCur->Core.KeyLast);
+            Assert(pRam->GCPhys     <= pCur->Key);
+            Assert(pRam->GCPhysLast >= pCur->KeyLast);
 
             /*
@@ -1273 +1322 @@
         }
     }
-    else
+    else if (rc == VERR_NOT_FOUND)
     {
         AssertMsgFailed(("Didn't find MMIO Range starting at %#x\n", GCPhys));
@@ -1305 +1354 @@
 {
     LogFlow(("PGMHandlerPhysicalPageTempOff GCPhysPage=%RGp\n", GCPhysPage));
-    PGM_LOCK_VOID(pVM);
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
 
     /*
      * Validate the range.
      */
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (RT_LIKELY(pCur))
-    {
-        if (RT_LIKELY(   GCPhysPage >= pCur->Core.Key
-                      && GCPhysPage <= pCur->Core.KeyLast))
-        {
-            Assert(!(pCur->Core.Key & GUEST_PAGE_OFFSET_MASK));
-            Assert((pCur->Core.KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK);
+    PPGMPHYSHANDLER pCur;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
+        if (RT_LIKELY(   GCPhysPage >= pCur->Key
+                      && GCPhysPage <= pCur->KeyLast))
+        {
+            Assert(!(pCur->Key & GUEST_PAGE_OFFSET_MASK));
+            Assert((pCur->KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK);
 
             PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE(pVM, pCur);
@@ -1330 +1382 @@
             PPGMPAGE     pPage;
             PPGMRAMRANGE pRam;
-            int rc = pgmPhysGetPageAndRangeEx(pVM, GCPhysPage, &pPage, &pRam);
+            rc = pgmPhysGetPageAndRangeEx(pVM, GCPhysPage, &pPage, &pRam);
             AssertReturnStmt(RT_SUCCESS_NP(rc), PGM_UNLOCK(pVM), rc);
             if (PGM_PAGE_GET_HNDL_PHYS_STATE(pPage) != PGM_PAGE_HNDL_PHYS_STATE_DISABLED)
@@ -1354 +1406 @@
         }
         PGM_UNLOCK(pVM);
-        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n",
-                         GCPhysPage, pCur->Core.Key, pCur->Core.KeyLast));
+        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n", GCPhysPage, pCur->Key, pCur->KeyLast));
         return VERR_INVALID_PARAMETER;
     }
     PGM_UNLOCK(pVM);
-    AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
-    return VERR_PGM_HANDLER_NOT_FOUND;
+
+    if (rc == VERR_NOT_FOUND)
+    {
+        AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
+        return VERR_PGM_HANDLER_NOT_FOUND;
+    }
+    return rc;
 }
 
@@ -1461 +1517 @@
     AssertReturn(!VM_IS_NEM_ENABLED(pVM) || !pVM->pgm.s.fNemMode, VERR_PGM_NOT_SUPPORTED_FOR_NEM_MODE);
 #endif
-    PGM_LOCK_VOID(pVM);
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
 
     /*
@@ -1480 +1537 @@
      * Lookup and validate the range.
      */
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (RT_LIKELY(pCur))
-    {
-        if (RT_LIKELY(   GCPhysPage >= pCur->Core.Key
-                      && GCPhysPage <= pCur->Core.KeyLast))
+    PPGMPHYSHANDLER pCur;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
+        if (RT_LIKELY(   GCPhysPage >= pCur->Key
+                      && GCPhysPage <= pCur->KeyLast))
         {
             PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
             AssertReturnStmt(pCurType->enmKind == PGMPHYSHANDLERKIND_MMIO, PGM_UNLOCK(pVM), VERR_ACCESS_DENIED);
-            AssertReturnStmt(!(pCur->Core.Key & GUEST_PAGE_OFFSET_MASK), PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
-            AssertReturnStmt((pCur->Core.KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK,
+            AssertReturnStmt(!(pCur->Key & GUEST_PAGE_OFFSET_MASK), PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
+            AssertReturnStmt((pCur->KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK,
                              PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
 
@@ -1497 +1556 @@
             PPGMPAGE     pPage;
             PPGMRAMRANGE pRam;
-            int rc = pgmPhysGetPageAndRangeEx(pVM, GCPhysPage, &pPage, &pRam);
+            rc = pgmPhysGetPageAndRangeEx(pVM, GCPhysPage, &pPage, &pRam);
             AssertReturnStmt(RT_SUCCESS_NP(rc), PGM_UNLOCK(pVM), rc);
             if (PGM_PAGE_GET_TYPE(pPage) != PGMPAGETYPE_MMIO)
@@ -1556 +1615 @@
 
         PGM_UNLOCK(pVM);
-        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n",
-                         GCPhysPage, pCur->Core.Key, pCur->Core.KeyLast));
+        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n", GCPhysPage, pCur->Key, pCur->KeyLast));
         return VERR_INVALID_PARAMETER;
     }
 
     PGM_UNLOCK(pVM);
-    AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
-    return VERR_PGM_HANDLER_NOT_FOUND;
+    if (rc == VERR_NOT_FOUND)
+    {
+        AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
+        return VERR_PGM_HANDLER_NOT_FOUND;
+    }
+    return rc;
 }
 
@@ -1604 +1666 @@
     AssertReturn(!VM_IS_NEM_ENABLED(pVM) || !pVM->pgm.s.fNemMode, VERR_PGM_NOT_SUPPORTED_FOR_NEM_MODE);
 #endif
-    PGM_LOCK_VOID(pVM);
+    int rc = PGM_LOCK(pVM);
+    AssertRCReturn(rc, rc);
 
     /*
      * Lookup and validate the range.
      */
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)RTAvlroGCPhysGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (RT_LIKELY(pCur))
-    {
-        if (RT_LIKELY(    GCPhysPage >= pCur->Core.Key
-                      &&  GCPhysPage <= pCur->Core.KeyLast))
+    PPGMPHYSHANDLER pCur;
+    rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
+    {
+        Assert(pCur->Key == GCPhys);
+        if (RT_LIKELY(    GCPhysPage >= pCur->Key
+                      &&  GCPhysPage <= pCur->KeyLast))
         {
             PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
             AssertReturnStmt(pCurType->enmKind == PGMPHYSHANDLERKIND_MMIO, PGM_UNLOCK(pVM), VERR_ACCESS_DENIED);
-            AssertReturnStmt(!(pCur->Core.Key & GUEST_PAGE_OFFSET_MASK), PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
-            AssertReturnStmt((pCur->Core.KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK,
+            AssertReturnStmt(!(pCur->Key & GUEST_PAGE_OFFSET_MASK), PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
+            AssertReturnStmt((pCur->KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK,
                              PGM_UNLOCK(pVM), VERR_INVALID_PARAMETER);
 
@@ -1625 +1690 @@
              */
             PPGMPAGE pPage;
-            int rc = pgmPhysGetPageEx(pVM, GCPhysPage, &pPage);
+            rc = pgmPhysGetPageEx(pVM, GCPhysPage, &pPage);
             AssertReturnStmt(RT_SUCCESS_NP(rc), PGM_UNLOCK(pVM), rc);
             if (PGM_PAGE_GET_TYPE(pPage) != PGMPAGETYPE_MMIO)
@@ -1673 +1738 @@
         }
         PGM_UNLOCK(pVM);
-        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n",
-                         GCPhysPage, pCur->Core.Key, pCur->Core.KeyLast));
+        AssertMsgFailed(("The page %#x is outside the range %#x-%#x\n", GCPhysPage, pCur->Key, pCur->KeyLast));
         return VERR_INVALID_PARAMETER;
     }
     PGM_UNLOCK(pVM);
 
-    AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
-    return VERR_PGM_HANDLER_NOT_FOUND;
+    if (rc == VERR_NOT_FOUND)
+    {
+        AssertMsgFailed(("Specified physical handler start address %#x is invalid.\n", GCPhys));
+        return VERR_PGM_HANDLER_NOT_FOUND;
+    }
+    return rc;
 }
 
@@ -1699 +1767 @@
      */
     PGM_LOCK_VOID(pVM);
-    PPGMPHYSHANDLER pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-    if (pCur)
+    PPGMPHYSHANDLER pCur;
+    int rc = pgmHandlerPhysicalLookup(pVM, GCPhys, &pCur);
+    if (RT_SUCCESS(rc))
     {
 #ifdef VBOX_STRICT
-        Assert(GCPhys >= pCur->Core.Key && GCPhys <= pCur->Core.KeyLast);
+        Assert(GCPhys >= pCur->Key && GCPhys <= pCur->KeyLast);
         PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
         Assert(   pCurType->enmKind == PGMPHYSHANDLERKIND_WRITE
@@ -1731 +1800 @@
 {
     PGM_LOCK_VOID(pVM);
-    PPGMPHYSHANDLER pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-    if (!pCur)
-    {
-        PGM_UNLOCK(pVM);
-        AssertFailed();
-        return true;
-    }
+    PPGMPHYSHANDLER pCur;
+    int rc = pgmHandlerPhysicalLookup(pVM, GCPhys, &pCur);
+    AssertRCReturnStmt(rc, PGM_UNLOCK(pVM), true);
 
     /* Only whole pages can be disabled. */
-    Assert(   pCur->Core.Key     <= (GCPhys & ~(RTGCPHYS)GUEST_PAGE_OFFSET_MASK)
-           && pCur->Core.KeyLast >= (GCPhys | GUEST_PAGE_OFFSET_MASK));
+    Assert(   pCur->Key     <= (GCPhys & ~(RTGCPHYS)GUEST_PAGE_OFFSET_MASK)
+           && pCur->KeyLast >= (GCPhys | GUEST_PAGE_OFFSET_MASK));
 
     PCPGMPHYSHANDLERTYPEINT const pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
@@ -1789 +1854 @@
      * Check the RAM flags against the handlers.
      */
+    PPGMPHYSHANDLERTREE const pPhysHandlerTree = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree;
     for (PPGMRAMRANGE pRam = pPGM->CTX_SUFF(pRamRangesX); pRam; pRam = pRam->CTX_SUFF(pNext))
     {
@@ -1806 +1872 @@
                 {
                     /* the first */
-                    PPGMPHYSHANDLER pPhys = (PPGMPHYSHANDLER)RTAvlroGCPhysRangeGet(&pPGM->CTX_SUFF(pTrees)->PhysHandlers, State.GCPhys);
-                    if (!pPhys)
+                    PPGMPHYSHANDLER pPhys;
+                    int rc = pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, State.GCPhys, &pPhys);
+                    if (rc == VERR_NOT_FOUND)
                     {
-                        pPhys = (PPGMPHYSHANDLER)RTAvlroGCPhysGetBestFit(&pPGM->CTX_SUFF(pTrees)->PhysHandlers, State.GCPhys, true);
-                        if (    pPhys
-                            &&  pPhys->Core.Key > (State.GCPhys + GUEST_PAGE_SIZE - 1))
-                            pPhys = NULL;
-                        Assert(!pPhys || pPhys->Core.Key >= State.GCPhys);
+                        rc = pPhysHandlerTree->lookupMatchingOrAbove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator,
+                                                                     State.GCPhys, &pPhys);
+                        if (RT_SUCCESS(rc))
+                        {
+                            Assert(pPhys->Key >= State.GCPhys);
+                            if (pPhys->Key > (State.GCPhys + GUEST_PAGE_SIZE - 1))
+                                pPhys = NULL;
+                        }
+                        else
+                            AssertLogRelMsgReturn(rc == VERR_NOT_FOUND, ("rc=%Rrc GCPhys=%RGp\n", rc, State.GCPhys), 999);
                     }
+                    else
+                        AssertLogRelMsgReturn(RT_SUCCESS(rc), ("rc=%Rrc GCPhys=%RGp\n", rc, State.GCPhys), 999);
+
                     if (pPhys)
                     {
@@ -1821 +1896 @@
 
                         /* more? */
-                        while (pPhys->Core.KeyLast < (State.GCPhys | GUEST_PAGE_OFFSET_MASK))
+                        while (pPhys->KeyLast < (State.GCPhys | GUEST_PAGE_OFFSET_MASK))
                         {
-                            PPGMPHYSHANDLER pPhys2 = (PPGMPHYSHANDLER)RTAvlroGCPhysGetBestFit(&pPGM->CTX_SUFF(pTrees)->PhysHandlers,
-                                                                                              pPhys->Core.KeyLast + 1, true);
-                            if (    !pPhys2
-                                ||  pPhys2->Core.Key > (State.GCPhys | GUEST_PAGE_OFFSET_MASK))
+                            PPGMPHYSHANDLER pPhys2;
+                            rc = pPhysHandlerTree->lookupMatchingOrAbove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator,
+                                                                         pPhys->KeyLast + 1, &pPhys2);
+                            if (rc == VERR_NOT_FOUND)
+                                break;
+                            AssertLogRelMsgReturn(RT_SUCCESS(rc), ("rc=%Rrc KeyLast+1=%RGp\n", rc, pPhys->KeyLast + 1), 999);
+                            if (pPhys2->Key > (State.GCPhys | GUEST_PAGE_OFFSET_MASK))
                                 break;
                             PCPGMPHYSHANDLERTYPEINT pPhysType2 = pgmHandlerPhysicalTypeHandleToPtr(pVM, pPhys2->hType);

trunk/src/VBox/VMM/VMMAll/PGMAllPhys.cpp

@@ -112 +112 @@
 #endif
 
+
+
+/**
+ * Calculate the actual table size.
+ *
+ * The memory is layed out like this:
+ *      - PGMPHYSHANDLERTREE (8 bytes)
+ *      - Allocation bitmap (8-byte size align)
+ *      - Slab of PGMPHYSHANDLER. Start is 64 byte aligned.
+ */
+uint32_t pgmHandlerPhysicalCalcTableSizes(uint32_t *pcEntries, uint32_t *pcbTreeAndBitmap)
+{
+    /*
+     * A minimum of 64 entries and a maximum of ~64K.
+     */
+    uint32_t cEntries = *pcEntries;
+    if (cEntries <= 64)
+        cEntries = 64;
+    else if (cEntries >= _64K)
+        cEntries = _64K;
+    else
+        cEntries = RT_ALIGN_32(cEntries, 16);
+
+    /*
+     * Do the initial calculation.
+     */
+    uint32_t cbBitmap        = RT_ALIGN_32(cEntries, 64) / 8;
+    uint32_t cbTreeAndBitmap = RT_ALIGN_32(sizeof(PGMPHYSHANDLERTREE) + cbBitmap, 64);
+    uint32_t cbTable         = cEntries * sizeof(PGMPHYSHANDLER);
+    uint32_t cbTotal         = cbTreeAndBitmap + cbTable;
+
+    /*
+     * Align the total and try use up extra space from that.
+     */
+    uint32_t cbTotalAligned = RT_ALIGN_32(cbTotal, RT_MAX(HOST_PAGE_SIZE, _16K));
+    uint32_t cAvail         = cbTotalAligned - cbTotal;
+    cAvail /= sizeof(PGMPHYSHANDLER);
+    if (cAvail >= 1)
+        for (;;)
+        {
+            cbBitmap        = RT_ALIGN_32(cEntries, 64) / 8;
+            cbTreeAndBitmap = RT_ALIGN_32(sizeof(PGMPHYSHANDLERTREE) + cbBitmap, 64);
+            cbTable         = cEntries * sizeof(PGMPHYSHANDLER);
+            cbTotal         = cbTreeAndBitmap + cbTable;
+            if (cbTotal <= cbTotalAligned)
+                break;
+            cEntries--;
+            Assert(cEntries >= 16);
+        }
+
+    /*
+     * Return the result.
+     */
+    *pcbTreeAndBitmap = cbTreeAndBitmap;
+    *pcEntries        = cEntries;
+    return cbTotalAligned;
+}
 
 
@@ -2407 +2464 @@
         || PGM_PAGE_IS_MMIO_OR_SPECIAL_ALIAS(pPage))
     {
-        PPGMPHYSHANDLER pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-        if (pCur)
-        {
-            Assert(pCur && GCPhys >= pCur->Core.Key && GCPhys <= pCur->Core.KeyLast);
-            Assert((pCur->Core.Key     & GUEST_PAGE_OFFSET_MASK) == 0);
-            Assert((pCur->Core.KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK);
+        PPGMPHYSHANDLER pCur;
+        rc = pgmHandlerPhysicalLookup(pVM, GCPhys, &pCur);
+        if (RT_SUCCESS(rc))
+        {
+            Assert(pCur && GCPhys >= pCur->Key && GCPhys <= pCur->KeyLast);
+            Assert((pCur->Key     & GUEST_PAGE_OFFSET_MASK) == 0);
+            Assert((pCur->KeyLast & GUEST_PAGE_OFFSET_MASK) == GUEST_PAGE_OFFSET_MASK);
 #ifndef IN_RING3
             if (enmOrigin != PGMACCESSORIGIN_IEM)
@@ -2435 +2493 @@
             PGM_LOCK_VOID(pVM);
 
-#ifdef VBOX_WITH_STATISTICS
-            pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-            if (pCur)
-                STAM_PROFILE_STOP(&pCur->Stat, h);
-#else
+            STAM_PROFILE_STOP(&pCur->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
             pCur = NULL; /* might not be valid anymore. */
-#endif
             AssertLogRelMsg(PGM_HANDLER_PHYS_IS_VALID_STATUS(rcStrict, false),
                             ("rcStrict=%Rrc GCPhys=%RGp\n", VBOXSTRICTRC_VAL(rcStrict), GCPhys));
@@ -2451 +2504 @@
             }
         }
+        else if (rc == VERR_NOT_FOUND)
+            AssertLogRelMsgFailed(("rc=%Rrc GCPhys=%RGp cb=%#x\n", rc, GCPhys, cb));
         else
-            AssertLogRelMsgFailed(("GCPhys=%RGp cb=%#x\n", GCPhys, cb));
+            AssertLogRelMsgFailedReturn(("rc=%Rrc GCPhys=%RGp cb=%#x\n", rc, GCPhys, cb), rc);
     }
 
@@ -2646 +2701 @@
      */
     PVMCPUCC pVCpu = VMMGetCpu(pVM);
-    PPGMPHYSHANDLER pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-    if (pCur)
-    {
-        Assert(GCPhys >= pCur->Core.Key && GCPhys <= pCur->Core.KeyLast);
+    PPGMPHYSHANDLER pCur;
+    rcStrict = pgmHandlerPhysicalLookup(pVM, GCPhys, &pCur);
+    if (RT_SUCCESS(rcStrict))
+    {
+        Assert(GCPhys >= pCur->Key && GCPhys <= pCur->KeyLast);
 #ifndef IN_RING3
         if (enmOrigin != PGMACCESSORIGIN_IEM)
@@ -2655 +2711 @@
             return VERR_PGM_PHYS_WR_HIT_HANDLER;
 #endif
-        size_t cbRange = pCur->Core.KeyLast - GCPhys + 1;
+        size_t cbRange = pCur->KeyLast - GCPhys + 1;
         if (cbRange > cbWrite)
             cbRange = cbWrite;
@@ -2687 +2743 @@
             }
 
-#ifdef VBOX_WITH_STATISTICS
-            pCur = pgmHandlerPhysicalLookup(pVM, GCPhys);
-            if (pCur)
-                STAM_PROFILE_STOP(&pCur->Stat, h);
-#else
+            STAM_PROFILE_STOP(&pCur->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
             pCur = NULL; /* might not be valid anymore. */
-#endif
             if (rcStrict == VINF_PGM_HANDLER_DO_DEFAULT)
             {
@@ -2721 +2772 @@
         pvDst    = (uint8_t *)pvDst + cbRange;
     }
-    else /* The handler is somewhere else in the page, deal with it below. */
+    else if (rcStrict == VERR_NOT_FOUND) /* The handler is somewhere else in the page, deal with it below. */
         rcStrict = VINF_SUCCESS;
+    else
+        AssertMsgFailedReturn(("rcStrict=%Rrc GCPhys=%RGp\n", VBOXSTRICTRC_VAL(rcStrict), GCPhys), rcStrict);
     Assert(!PGM_PAGE_IS_MMIO_OR_ALIAS(pPage)); /* MMIO handlers are all GUEST_PAGE_SIZEed! */
 
@@ -2752 +2805 @@
         if (fMorePhys && !pPhys)
         {
-            pPhys = pgmHandlerPhysicalLookup(pVM, GCPhys);
-            if (pPhys)
+            rcStrict = pgmHandlerPhysicalLookup(pVM, GCPhys, &pPhys);
+            if (RT_SUCCESS_NP(rcStrict))
             {
                 offPhys = 0;
-                offPhysLast = pPhys->Core.KeyLast - GCPhys; /* ASSUMES < 4GB handlers... */
+                offPhysLast = pPhys->KeyLast - GCPhys; /* ASSUMES < 4GB handlers... */
             }
             else
             {
-                pPhys = (PPGMPHYSHANDLER)RTAvlroGCPhysGetBestFit(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers,
-                                                                 GCPhys, true /* fAbove */);
-                if (    pPhys
-                    &&  pPhys->Core.Key <= GCPhys + (cbWrite - 1))
+                AssertMsgReturn(rcStrict == VERR_NOT_FOUND, ("%Rrc GCPhys=%RGp\n", VBOXSTRICTRC_VAL(rcStrict), GCPhys), rcStrict);
+
+                rcStrict = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookupMatchingOrAbove(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator,
+                                                                                        GCPhys, &pPhys);
+                AssertMsgReturn(RT_SUCCESS(rcStrict) || rcStrict == VERR_NOT_FOUND,
+                                ("%Rrc GCPhys=%RGp\n", VBOXSTRICTRC_VAL(rcStrict), GCPhys), rcStrict);
+
+                if (   RT_SUCCESS(rcStrict)
+                    && pPhys->Key <= GCPhys + (cbWrite - 1))
                 {
-                    offPhys     = pPhys->Core.Key     - GCPhys;
-                    offPhysLast = pPhys->Core.KeyLast - GCPhys; /* ASSUMES < 4GB handlers... */
+                    offPhys     = pPhys->Key     - GCPhys;
+                    offPhysLast = pPhys->KeyLast - GCPhys; /* ASSUMES < 4GB handlers... */
+                    Assert(pPhys->KeyLast - pPhys->Key < _4G);
                 }
                 else
@@ -2818 +2877 @@
             }
 
-#ifdef VBOX_WITH_STATISTICS
-            pPhys = pgmHandlerPhysicalLookup(pVM, GCPhys);
-            if (pPhys)
-                STAM_PROFILE_STOP(&pPhys->Stat, h);
-#else
+            STAM_PROFILE_STOP(&pPhys->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
             pPhys = NULL; /* might not be valid anymore. */
-#endif
             AssertLogRelMsg(PGM_HANDLER_PHYS_IS_VALID_STATUS(rcStrict2, true),
                             ("rcStrict2=%Rrc (rcStrict=%Rrc) GCPhys=%RGp pPage=%R[pgmpage] %s\n", VBOXSTRICTRC_VAL(rcStrict2),

trunk/src/VBox/VMM/VMMR0/PGMR0.cpp

@@ -35 +35 @@
 #include <iprt/mem.h>
 #include <iprt/memobj.h>
+#include <iprt/process.h>
 #include <iprt/rand.h>
 #include <iprt/string.h>
@@ -82 +83 @@
         pGVM->pgmr0.s.ahPoolMapObjs[i] = NIL_RTR0MEMOBJ;
     }
+    pGVM->pgmr0.s.hPhysHandlerMemObj = NIL_RTR0MEMOBJ;
+    pGVM->pgmr0.s.hPhysHandlerMapObj = NIL_RTR0MEMOBJ;
 
     /*
@@ -251 +254 @@
             pGVM->pgmr0.s.ahPoolMemObjs[i] = NIL_RTR0MEMOBJ;
         }
+    }
+
+    if (pGVM->pgmr0.s.hPhysHandlerMapObj != NIL_RTR0MEMOBJ)
+    {
+        int rc = RTR0MemObjFree(pGVM->pgmr0.s.hPhysHandlerMapObj, true /*fFreeMappings*/);
+        AssertRC(rc);
+        pGVM->pgmr0.s.hPhysHandlerMapObj = NIL_RTR0MEMOBJ;
+    }
+
+    if (pGVM->pgmr0.s.hPhysHandlerMemObj != NIL_RTR0MEMOBJ)
+    {
+        int rc = RTR0MemObjFree(pGVM->pgmr0.s.hPhysHandlerMemObj, true /*fFreeMappings*/);
+        AssertRC(rc);
+        pGVM->pgmr0.s.hPhysHandlerMemObj = NIL_RTR0MEMOBJ;
     }
 
@@ -749 +766 @@
     return SUPR0PageMapKernel(pGVM->pSession, pvR3, (uint32_t)offSub, (uint32_t)cbSub, 0 /*fFlags*/, ppvMapping);
 #endif
+}
+
+
+/**
+ * This is called during PGMR3Init to init the physical access handler allocator
+ * and tree.
+ *
+ * @returns VBox status code.
+ * @param   pGVM        Pointer to the global VM structure.
+ * @param   cEntries    Desired number of physical access handlers to reserve
+ *                      space for (will be adjusted).
+ * @thread  EMT(0)
+ */
+VMMR0_INT_DECL(int) PGMR0PhysHandlerInitReqHandler(PGVM pGVM, uint32_t cEntries)
+{
+    /*
+     * Validate the input and state.
+     */
+    int rc = GVMMR0ValidateGVMandEMT(pGVM, 0);
+    AssertRCReturn(rc, rc);
+    VM_ASSERT_STATE_RETURN(pGVM, VMSTATE_CREATING, VERR_VM_INVALID_VM_STATE); /** @todo ring-0 safe state check. */
+
+    AssertReturn(pGVM->pgmr0.s.PhysHandlerAllocator.m_paNodes == NULL, VERR_WRONG_ORDER);
+    AssertReturn(pGVM->pgm.s.PhysHandlerAllocator.m_paNodes == NULL, VERR_WRONG_ORDER);
+
+    AssertLogRelMsgReturn(cEntries <= _64K, ("%#x\n", cEntries), VERR_OUT_OF_RANGE);
+
+    /*
+     * Calculate the table size and allocate it.
+     */
+    uint32_t       cbTreeAndBitmap = 0;
+    uint32_t const cbTotalAligned  = pgmHandlerPhysicalCalcTableSizes(&cEntries, &cbTreeAndBitmap);
+    RTR0MEMOBJ     hMemObj         = NIL_RTR0MEMOBJ;
+    rc = RTR0MemObjAllocPage(&hMemObj, cbTotalAligned, false);
+    if (RT_SUCCESS(rc))
+    {
+        RTR0MEMOBJ hMapObj = NIL_RTR0MEMOBJ;
+        rc = RTR0MemObjMapUser(&hMapObj, hMemObj, (RTR3PTR)-1, 0, RTMEM_PROT_READ | RTMEM_PROT_WRITE, RTR0ProcHandleSelf());
+        if (RT_SUCCESS(rc))
+        {
+            uint8_t *pb = (uint8_t *)RTR0MemObjAddress(hMemObj);
+            if (!RTR0MemObjWasZeroInitialized(hMemObj))
+                RT_BZERO(pb, cbTotalAligned);
+
+            pGVM->pgmr0.s.PhysHandlerAllocator.initSlabAllocator(cEntries, (PPGMPHYSHANDLER)&pb[cbTreeAndBitmap],
+                                                                 (uint64_t *)&pb[sizeof(PGMPHYSHANDLERTREE)]);
+            pGVM->pgmr0.s.pPhysHandlerTree = (PPGMPHYSHANDLERTREE)pb;
+            pGVM->pgmr0.s.pPhysHandlerTree->initWithAllocator(&pGVM->pgmr0.s.PhysHandlerAllocator);
+            pGVM->pgmr0.s.hPhysHandlerMemObj = hMemObj;
+            pGVM->pgmr0.s.hPhysHandlerMapObj = hMapObj;
+
+            AssertCompile(sizeof(pGVM->pgm.s.PhysHandlerAllocator) == sizeof(pGVM->pgmr0.s.PhysHandlerAllocator));
+            RTR3PTR R3Ptr = RTR0MemObjAddressR3(hMapObj);
+            pGVM->pgm.s.pPhysHandlerTree                    = R3Ptr;
+            pGVM->pgm.s.PhysHandlerAllocator.m_paNodes      = R3Ptr + cbTreeAndBitmap;
+            pGVM->pgm.s.PhysHandlerAllocator.m_pbmAlloc     = R3Ptr + sizeof(PGMPHYSHANDLERTREE);
+            pGVM->pgm.s.PhysHandlerAllocator.m_cNodes       = cEntries;
+            pGVM->pgm.s.PhysHandlerAllocator.m_cErrors      = 0;
+            pGVM->pgm.s.PhysHandlerAllocator.m_idxAllocHint = 0;
+            pGVM->pgm.s.PhysHandlerAllocator.m_uPadding     = 0;
+            return VINF_SUCCESS;
+        }
+
+        RTR0MemObjFree(hMemObj, true /*fFreeMappings*/);
+    }
+    return rc;
 }
 
@@ -1156 +1239 @@
      */
     PGM_LOCK_VOID(pGVM);
-    PPGMPHYSHANDLER          pHandler     = pgmHandlerPhysicalLookup(pGVM, GCPhysFault);
-    PCPGMPHYSHANDLERTYPEINT  pHandlerType = RT_LIKELY(pHandler) ? PGMPHYSHANDLER_GET_TYPE_NO_NULL(pGVM, pHandler) : NULL;
-    if (RT_LIKELY(pHandler && pHandlerType->enmKind != PGMPHYSHANDLERKIND_WRITE))
-    {
-        /*
-         * If the handle has aliases page or pages that have been temporarily
-         * disabled, we'll have to take a detour to make sure we resync them
-         * to avoid lots of unnecessary exits.
-         */
-        PPGMPAGE pPage;
-        if (   (   pHandler->cAliasedPages
-                || pHandler->cTmpOffPages)
-            && (   (pPage = pgmPhysGetPage(pGVM, GCPhysFault)) == NULL
-                || PGM_PAGE_GET_HNDL_PHYS_STATE(pPage) == PGM_PAGE_HNDL_PHYS_STATE_DISABLED)
-           )
-        {
-            Log(("PGMR0Trap0eHandlerNPMisconfig: Resyncing aliases / tmp-off page at %RGp (uErr=%#x) %R[pgmpage]\n", GCPhysFault, uErr, pPage));
-            STAM_COUNTER_INC(&pGVCpu->pgm.s.Stats.StatR0NpMiscfgSyncPage);
-            rc = pgmShwSyncNestedPageLocked(pGVCpu, GCPhysFault, 1 /*cPages*/, enmShwPagingMode);
-            PGM_UNLOCK(pGVM);
-        }
-        else
-        {
-            if (pHandlerType->pfnPfHandler)
+    PPGMPHYSHANDLER pHandler;
+    rc = pgmHandlerPhysicalLookup(pGVM, GCPhysFault, &pHandler);
+    if (RT_SUCCESS(rc))
+    {
+        PCPGMPHYSHANDLERTYPEINT pHandlerType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pGVM, pHandler);
+        if (RT_LIKELY(pHandlerType->enmKind != PGMPHYSHANDLERKIND_WRITE))
+        {
+            /*
+             * If the handle has aliases page or pages that have been temporarily
+             * disabled, we'll have to take a detour to make sure we resync them
+             * to avoid lots of unnecessary exits.
+             */
+            PPGMPAGE pPage;
+            if (   (   pHandler->cAliasedPages
+                    || pHandler->cTmpOffPages)
+                && (   (pPage = pgmPhysGetPage(pGVM, GCPhysFault)) == NULL
+                    || PGM_PAGE_GET_HNDL_PHYS_STATE(pPage) == PGM_PAGE_HNDL_PHYS_STATE_DISABLED)
+               )
             {
-                uint64_t const uUser = !pHandlerType->fRing0DevInsIdx ? pHandler->uUser
-                                     : (uintptr_t)PDMDeviceRing0IdxToInstance(pGVM, pHandler->uUser);
-                STAM_PROFILE_START(&pHandler->Stat, h);
+                Log(("PGMR0Trap0eHandlerNPMisconfig: Resyncing aliases / tmp-off page at %RGp (uErr=%#x) %R[pgmpage]\n", GCPhysFault, uErr, pPage));
+                STAM_COUNTER_INC(&pGVCpu->pgm.s.Stats.StatR0NpMiscfgSyncPage);
+                rc = pgmShwSyncNestedPageLocked(pGVCpu, GCPhysFault, 1 /*cPages*/, enmShwPagingMode);
                 PGM_UNLOCK(pGVM);
-
-                Log6(("PGMR0Trap0eHandlerNPMisconfig: calling %p(,%#x,,%RGp,%p)\n", pHandlerType->pfnPfHandler, uErr, GCPhysFault, uUser));
-                rc = pHandlerType->pfnPfHandler(pGVM, pGVCpu, uErr == UINT32_MAX ? RTGCPTR_MAX : uErr, pRegFrame,
-                                                GCPhysFault, GCPhysFault, uUser);
-
-#ifdef VBOX_WITH_STATISTICS
-                PGM_LOCK_VOID(pGVM);
-                pHandler = pgmHandlerPhysicalLookup(pGVM, GCPhysFault);
-                if (pHandler)
-                    STAM_PROFILE_STOP(&pHandler->Stat, h);
-                PGM_UNLOCK(pGVM);
-#endif
             }
             else
             {
-                PGM_UNLOCK(pGVM);
-                Log(("PGMR0Trap0eHandlerNPMisconfig: %RGp (uErr=%#x) -> R3\n", GCPhysFault, uErr));
-                rc = VINF_EM_RAW_EMULATE_INSTR;
+                if (pHandlerType->pfnPfHandler)
+                {
+                    uint64_t const uUser = !pHandlerType->fRing0DevInsIdx ? pHandler->uUser
+                                         : (uintptr_t)PDMDeviceRing0IdxToInstance(pGVM, pHandler->uUser);
+                    STAM_PROFILE_START(&pHandler->Stat, h);
+                    PGM_UNLOCK(pGVM);
+
+                    Log6(("PGMR0Trap0eHandlerNPMisconfig: calling %p(,%#x,,%RGp,%p)\n", pHandlerType->pfnPfHandler, uErr, GCPhysFault, uUser));
+                    rc = pHandlerType->pfnPfHandler(pGVM, pGVCpu, uErr == UINT32_MAX ? RTGCPTR_MAX : uErr, pRegFrame,
+                                                    GCPhysFault, GCPhysFault, uUser);
+
+                    STAM_PROFILE_STOP(&pHandler->Stat, h); /* no locking needed, entry is unlikely reused before we get here. */
+                }
+                else
+                {
+                    PGM_UNLOCK(pGVM);
+                    Log(("PGMR0Trap0eHandlerNPMisconfig: %RGp (uErr=%#x) -> R3\n", GCPhysFault, uErr));
+                    rc = VINF_EM_RAW_EMULATE_INSTR;
+                }
             }
+            STAM_PROFILE_STOP(&pGVCpu->pgm.s.Stats.StatR0NpMiscfg, a);
+            return rc;
         }
     }
     else
-    {
-        /*
-         * Must be out of sync, so do a SyncPage and restart the instruction.
-         *
-         * ASSUMES that ALL handlers are page aligned and covers whole pages
-         * (assumption asserted in PGMHandlerPhysicalRegisterEx).
-         */
-        Log(("PGMR0Trap0eHandlerNPMisconfig: Out of sync page at %RGp (uErr=%#x)\n", GCPhysFault, uErr));
-        STAM_COUNTER_INC(&pGVCpu->pgm.s.Stats.StatR0NpMiscfgSyncPage);
-        rc = pgmShwSyncNestedPageLocked(pGVCpu, GCPhysFault, 1 /*cPages*/, enmShwPagingMode);
-        PGM_UNLOCK(pGVM);
-    }
+        AssertMsgReturn(rc == VERR_NOT_FOUND, ("%Rrc GCPhysFault=%RGp\n", VBOXSTRICTRC_VAL(rc), GCPhysFault), rc);
+
+    /*
+     * Must be out of sync, so do a SyncPage and restart the instruction.
+     *
+     * ASSUMES that ALL handlers are page aligned and covers whole pages
+     * (assumption asserted in PGMHandlerPhysicalRegisterEx).
+     */
+    Log(("PGMR0Trap0eHandlerNPMisconfig: Out of sync page at %RGp (uErr=%#x)\n", GCPhysFault, uErr));
+    STAM_COUNTER_INC(&pGVCpu->pgm.s.Stats.StatR0NpMiscfgSyncPage);
+    rc = pgmShwSyncNestedPageLocked(pGVCpu, GCPhysFault, 1 /*cPages*/, enmShwPagingMode);
+    PGM_UNLOCK(pGVM);
 
     STAM_PROFILE_STOP(&pGVCpu->pgm.s.Stats.StatR0NpMiscfg, a);

trunk/src/VBox/VMM/VMMR0/VMMR0.cpp

@@ -1904 +1904 @@
             break;
 
+        case VMMR0_DO_PGM_PHYS_HANDLER_INIT:
+            if (idCpu != 0 || pReqHdr != NULL || u64Arg > UINT32_MAX)
+                return VERR_INVALID_PARAMETER;
+            rc = PGMR0PhysHandlerInitReqHandler(pGVM, (uint32_t)u64Arg);
+            break;
+
         /*
          * GMM wrappers.

trunk/src/VBox/VMM/VMMR3/PGM.cpp

@@ -606 +606 @@
 #include <VBox/vmm/hm.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include <VBox/vmm/uvm.h>
 #include "PGMInline.h"
@@ -933 +933 @@
 
     /*
-     * Trees
-     */
-    rc = MMHyperAlloc(pVM, sizeof(PGMTREES), 0, MM_TAG_PGM, (void **)&pVM->pgm.s.pTreesR3);
-    if (RT_SUCCESS(rc))
-        pVM->pgm.s.pTreesR0 = MMHyperR3ToR0(pVM, pVM->pgm.s.pTreesR3);
-
-    /*
      * Setup the zero page (HCPHysZeroPg is set by ring-0).
      */
@@ -958 +951 @@
     AssertRelease(pVM->pgm.s.HCPhysMmioPg != 0);
     pVM->pgm.s.HCPhysInvMmioPg = pVM->pgm.s.HCPhysMmioPg;
+
+    /*
+     * Initialize physical access handlers.
+     */
+    /** @cfgm{/PGM/MaxPhysicalAccessHandlers, uint32_t, 32, 65536, 6144}
+     * Number of physical access handlers allowed (subject to rounding).  This is
+     * managed as one time allocation during initializations.  The default is
+     * lower for a driverless setup. */
+    /** @todo can lower it for nested paging too, at least when there is no
+     *        nested guest involved. */
+    uint32_t cAccessHandlers = 0;
+    rc = CFGMR3QueryU32Def(pCfgPGM, "MaxPhysicalAccessHandlers", &cAccessHandlers, !fDriverless ? 6144 : 640);
+    AssertLogRelRCReturn(rc, rc);
+    AssertLogRelMsgStmt(cAccessHandlers >= 32, ("cAccessHandlers=%#x, min 32\n", cAccessHandlers), cAccessHandlers = 32);
+    AssertLogRelMsgStmt(cAccessHandlers <= _64K, ("cAccessHandlers=%#x, max 65536\n", cAccessHandlers), cAccessHandlers = _64K);
+    if (!fDriverless)
+    {
+        rc = VMMR3CallR0(pVM, VMMR0_DO_PGM_PHYS_HANDLER_INIT, cAccessHandlers, NULL);
+        AssertRCReturn(rc, rc);
+        AssertPtr(pVM->pgm.s.pPhysHandlerTree);
+        AssertPtr(pVM->pgm.s.PhysHandlerAllocator.m_paNodes);
+        AssertPtr(pVM->pgm.s.PhysHandlerAllocator.m_pbmAlloc);
+    }
+    else
+    {
+        uint32_t       cbTreeAndBitmap = 0;
+        uint32_t const cbTotalAligned  = pgmHandlerPhysicalCalcTableSizes(&cAccessHandlers, &cbTreeAndBitmap);
+        uint8_t       *pb = NULL;
+        rc = SUPR3PageAlloc(cbTotalAligned >> HOST_PAGE_SHIFT, 0, (void **)&pb);
+        AssertLogRelRCReturn(rc, rc);
+
+        pVM->pgm.s.PhysHandlerAllocator.initSlabAllocator(cAccessHandlers, (PPGMPHYSHANDLER)&pb[cbTreeAndBitmap],
+                                                          (uint64_t *)&pb[sizeof(PGMPHYSHANDLERTREE)]);
+        pVM->pgm.s.pPhysHandlerTree = (PPGMPHYSHANDLERTREE)pb;
+        pVM->pgm.s.pPhysHandlerTree->initWithAllocator(&pVM->pgm.s.PhysHandlerAllocator);
+    }
 
     /*
@@ -1219 +1248 @@
         AssertRC(rc);
 
+#define PGM_REG_U64(a, b, c) \
+        rc = STAMR3RegisterF(pVM, a, STAMTYPE_U64, STAMVISIBILITY_ALWAYS, STAMUNIT_OCCURENCES, c, b); \
+        AssertRC(rc);
+
+#define PGM_REG_U64_RESET(a, b, c) \
+        rc = STAMR3RegisterF(pVM, a, STAMTYPE_U64_RESET, STAMVISIBILITY_ALWAYS, STAMUNIT_OCCURENCES, c, b); \
+        AssertRC(rc);
+
+#define PGM_REG_U32(a, b, c) \
+        rc = STAMR3RegisterF(pVM, a, STAMTYPE_U32, STAMVISIBILITY_ALWAYS, STAMUNIT_OCCURENCES, c, b); \
+        AssertRC(rc);
+
 #define PGM_REG_COUNTER_BYTES(a, b, c) \
         rc = STAMR3RegisterF(pVM, a, STAMTYPE_COUNTER, STAMVISIBILITY_ALWAYS, STAMUNIT_BYTES, c, b); \
@@ -1283 +1324 @@
     PGM_REG_COUNTER(&pStats->StatRZPhysHandlerLookupMisses,     "/PGM/RZ/PhysHandlerLookupMisses",    "The number of cache misses when looking up physical handlers.");
     PGM_REG_COUNTER(&pStats->StatR3PhysHandlerLookupMisses,     "/PGM/R3/PhysHandlerLookupMisses",    "The number of cache misses when looking up physical handlers.");
-
+#endif /* VBOX_WITH_STATISTICS */
+    PPGMPHYSHANDLERTREE pPhysHndlTree = pVM->pgm.s.pPhysHandlerTree;
+    PGM_REG_U32(&pPhysHndlTree->m_cErrors,                      "/PGM/PhysHandlerTree/ErrorsTree",    "Physical access handler tree errors.");
+    PGM_REG_U32(&pVM->pgm.s.PhysHandlerAllocator.m_cErrors,     "/PGM/PhysHandlerTree/ErrorsAllocatorR3", "Physical access handler tree allocator errors (ring-3 only).");
+    PGM_REG_U64_RESET(&pPhysHndlTree->m_cInserts,               "/PGM/PhysHandlerTree/Inserts",       "Physical access handler tree inserts.");
+    PGM_REG_U32(&pVM->pgm.s.PhysHandlerAllocator.m_cNodes,      "/PGM/PhysHandlerTree/MaxHandlers",   "Max physical access handlers.");
+    PGM_REG_U64_RESET(&pPhysHndlTree->m_cRemovals,              "/PGM/PhysHandlerTree/Removals",      "Physical access handler tree removals.");
+    PGM_REG_U64_RESET(&pPhysHndlTree->m_cRebalancingOperations, "/PGM/PhysHandlerTree/RebalancingOperations", "Physical access handler tree rebalancing transformations.");
+
+#ifdef VBOX_WITH_STATISTICS
     PGM_REG_COUNTER(&pStats->StatRZPageReplaceShared,           "/PGM/RZ/Page/ReplacedShared",        "Times a shared page was replaced.");
     PGM_REG_COUNTER(&pStats->StatRZPageReplaceZero,             "/PGM/RZ/Page/ReplacedZero",          "Times the zero page was replaced.");
@@ -1323 +1373 @@
 
 #undef PGM_REG_COUNTER
+#undef PGM_REG_U64
+#undef PGM_REG_U64_RESET
+#undef PGM_REG_U32
 #undef PGM_REG_PROFILE
 #undef PGM_REG_PROFILE_NS
@@ -2104 +2157 @@
                         pszType = "MMIO";
                         PGM_LOCK_VOID(pVM);
-                        PPGMPHYSHANDLER pHandler = pgmHandlerPhysicalLookup(pVM, iFirstPage * X86_PAGE_SIZE);
-                        if (pHandler)
+                        PPGMPHYSHANDLER pHandler;
+                        int rc = pgmHandlerPhysicalLookup(pVM, iFirstPage * X86_PAGE_SIZE, &pHandler);
+                        if (RT_SUCCESS(rc))
                             pszMore = pHandler->pszDesc;
                         PGM_UNLOCK(pVM);
@@ -2537 +2591 @@
 {
     bool                    fLeftToRight;    /**< true: left-to-right; false: right-to-left. */
+    uint32_t                cErrors;
     PPGMPHYSHANDLER         pPrevPhys;
     PVM                     pVM;
@@ -2548 +2603 @@
  * @param   pvUser      pVM.
  */
-static DECLCALLBACK(int) pgmR3CheckIntegrityPhysHandlerNode(PAVLROGCPHYSNODECORE pNode, void *pvUser)
+static DECLCALLBACK(int) pgmR3CheckIntegrityPhysHandlerNode(PPGMPHYSHANDLER pNode, void *pvUser)
 {
     PPGMCHECKINTARGS pArgs = (PPGMCHECKINTARGS)pvUser;
-    PPGMPHYSHANDLER pCur = (PPGMPHYSHANDLER)pNode;
-    AssertReleaseReturn(!((uintptr_t)pCur & 7), 1);
-    AssertReleaseMsg(pCur->Core.Key <= pCur->Core.KeyLast,
-                     ("pCur=%p %RGp-%RGp %s\n", pCur, pCur->Core.Key, pCur->Core.KeyLast, pCur->pszDesc));
-    AssertReleaseMsg(   !pArgs->pPrevPhys
-                     || (  pArgs->fLeftToRight
-                         ? pArgs->pPrevPhys->Core.KeyLast < pCur->Core.Key
-                         : pArgs->pPrevPhys->Core.KeyLast > pCur->Core.Key),
-                     ("pPrevPhys=%p %RGp-%RGp %s\n"
-                      "     pCur=%p %RGp-%RGp %s\n",
-                      pArgs->pPrevPhys, pArgs->pPrevPhys->Core.Key, pArgs->pPrevPhys->Core.KeyLast, pArgs->pPrevPhys->pszDesc,
-                      pCur, pCur->Core.Key, pCur->Core.KeyLast, pCur->pszDesc));
-    pArgs->pPrevPhys = pCur;
+
+    AssertLogRelMsgReturnStmt(!((uintptr_t)pNode & 7), ("pNode=%p\n", pNode), pArgs->cErrors++, VERR_INVALID_POINTER);
+
+    AssertLogRelMsgStmt(pNode->Key <= pNode->KeyLast,
+                        ("pNode=%p %RGp-%RGp %s\n", pNode, pNode->Key, pNode->KeyLast, pNode->pszDesc),
+                        pArgs->cErrors++);
+
+    AssertLogRelMsgStmt(   !pArgs->pPrevPhys
+                        || (  pArgs->fLeftToRight
+                            ? pArgs->pPrevPhys->KeyLast < pNode->Key
+                            : pArgs->pPrevPhys->KeyLast > pNode->Key),
+                        ("pPrevPhys=%p %RGp-%RGp %s\n"
+                         "    pNode=%p %RGp-%RGp %s\n",
+                         pArgs->pPrevPhys, pArgs->pPrevPhys->Key, pArgs->pPrevPhys->KeyLast, pArgs->pPrevPhys->pszDesc,
+                         pNode, pNode->Key, pNode->KeyLast, pNode->pszDesc),
+                        pArgs->cErrors++);
+
+    pArgs->pPrevPhys = pNode;
     return 0;
 }
@@ -2580 +2640 @@
      * Check the trees.
      */
-    int cErrors = 0;
-    const PGMCHECKINTARGS LeftToRight = {  true, NULL, pVM };
-    const PGMCHECKINTARGS RightToLeft = { false, NULL, pVM };
-    PGMCHECKINTARGS Args = LeftToRight;
-    cErrors += RTAvlroGCPhysDoWithAll(&pVM->pgm.s.pTreesR3->PhysHandlers,       true,  pgmR3CheckIntegrityPhysHandlerNode, &Args);
-    Args = RightToLeft;
-    cErrors += RTAvlroGCPhysDoWithAll(&pVM->pgm.s.pTreesR3->PhysHandlers,       false, pgmR3CheckIntegrityPhysHandlerNode, &Args);
-
-    return !cErrors ? VINF_SUCCESS : VERR_INTERNAL_ERROR;
-}
-
+    PGMCHECKINTARGS Args = { true, 0, NULL, pVM };
+    int rc = pVM->pgm.s.pPhysHandlerTree->doWithAllFromLeft(&pVM->pgm.s.PhysHandlerAllocator,
+                                                            pgmR3CheckIntegrityPhysHandlerNode, &Args);
+    AssertLogRelRCReturn(rc, rc);
+
+    Args.fLeftToRight = false;
+    Args.pPrevPhys    = NULL;
+    rc = pVM->pgm.s.pPhysHandlerTree->doWithAllFromRight(&pVM->pgm.s.PhysHandlerAllocator,
+                                                         pgmR3CheckIntegrityPhysHandlerNode, &Args);
+    AssertLogRelMsgReturn(pVM->pgm.s.pPhysHandlerTree->m_cErrors == 0,
+                          ("m_cErrors=%#x\n", pVM->pgm.s.pPhysHandlerTree->m_cErrors == 0),
+                          VERR_INTERNAL_ERROR);
+
+    return Args.cErrors == 0 ? VINF_SUCCESS : VERR_INTERNAL_ERROR;
+}
+

trunk/src/VBox/VMM/VMMR3/PGMDbg.cpp

@@ -25 +25 @@
 #include <VBox/vmm/stam.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include <VBox/vmm/uvm.h>
 #include "PGMInline.h"

trunk/src/VBox/VMM/VMMR3/PGMHandler.cpp

@@ -34 +34 @@
 #include <VBox/vmm/ssm.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include "PGMInline.h"
 #include <VBox/dbg.h>
@@ -52 +52 @@
 *   Internal Functions                                                                                                           *
 *********************************************************************************************************************************/
-static DECLCALLBACK(int) pgmR3HandlerPhysicalOneClear(PAVLROGCPHYSNODECORE pNode, void *pvUser);
-static DECLCALLBACK(int) pgmR3HandlerPhysicalOneSet(PAVLROGCPHYSNODECORE pNode, void *pvUser);
-static DECLCALLBACK(int) pgmR3InfoHandlersPhysicalOne(PAVLROGCPHYSNODECORE pNode, void *pvUser);
+static DECLCALLBACK(int) pgmR3HandlerPhysicalOneClear(PPGMPHYSHANDLER pHandler, void *pvUser);
+static DECLCALLBACK(int) pgmR3HandlerPhysicalOneSet(PPGMPHYSHANDLER pHandler, void *pvUser);
+static DECLCALLBACK(int) pgmR3InfoHandlersPhysicalOne(PPGMPHYSHANDLER pHandler, void *pvUser);
 
 
@@ -143 +143 @@
      */
     PGM_LOCK_VOID(pVM);
-    RTAvlroGCPhysDoWithAll(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers,  true, pgmR3HandlerPhysicalOneClear, pVM);
-    RTAvlroGCPhysDoWithAll(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, false, pgmR3HandlerPhysicalOneSet, pVM);
+
+    int rc = pVM->pgm.s.pPhysHandlerTree->doWithAllFromLeft(&pVM->pgm.s.PhysHandlerAllocator, pgmR3HandlerPhysicalOneClear, pVM);
+    AssertRC(rc);
+    rc = pVM->pgm.s.pPhysHandlerTree->doWithAllFromRight(&pVM->pgm.s.PhysHandlerAllocator, pgmR3HandlerPhysicalOneSet, pVM);
+    AssertRC(rc);
+
     PGM_UNLOCK(pVM);
 }
@@ -153 +157 @@
  *
  * @returns 0
- * @param   pNode   Pointer to a PGMPHYSHANDLER.
- * @param   pvUser  Pointer to the VM.
- */
-static DECLCALLBACK(int) pgmR3HandlerPhysicalOneClear(PAVLROGCPHYSNODECORE pNode, void *pvUser)
-{
-    PPGMPHYSHANDLER pCur     = (PPGMPHYSHANDLER)pNode;
+ * @param   pHandler    The physical access handler entry.
+ * @param   pvUser      Pointer to the VM.
+ */
+static DECLCALLBACK(int) pgmR3HandlerPhysicalOneClear(PPGMPHYSHANDLER pHandler, void *pvUser)
+{
     PPGMRAMRANGE    pRamHint = NULL;
-    RTGCPHYS        GCPhys   = pCur->Core.Key;
-    RTUINT          cPages   = pCur->cPages;
+    RTGCPHYS        GCPhys   = pHandler->Key;
+    RTUINT          cPages   = pHandler->cPages;
     PVM             pVM      = (PVM)pvUser;
     for (;;)
@@ -198 +201 @@
  *
  * @returns 0
- * @param   pNode   Pointer to a PGMPHYSHANDLER.
- * @param   pvUser  Pointer to the VM.
- */
-static DECLCALLBACK(int) pgmR3HandlerPhysicalOneSet(PAVLROGCPHYSNODECORE pNode, void *pvUser)
+ * @param   pHandler    The physical access handler entry.
+ * @param   pvUser      Pointer to the VM.
+ */
+static DECLCALLBACK(int) pgmR3HandlerPhysicalOneSet(PPGMPHYSHANDLER pHandler, void *pvUser)
 {
     PVM                     pVM       = (PVM)pvUser;
-    PPGMPHYSHANDLER         pCur      = (PPGMPHYSHANDLER)pNode;
-    PCPGMPHYSHANDLERTYPEINT pCurType  = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pCur);
-    unsigned                uState    = pCurType->uState;
+    PCPGMPHYSHANDLERTYPEINT pType     = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pVM, pHandler);
+    unsigned                uState    = pType->uState;
     PPGMRAMRANGE            pRamHint  = NULL;
-    RTGCPHYS                GCPhys    = pCur->Core.Key;
-    RTUINT                  cPages    = pCur->cPages;
+    RTGCPHYS                GCPhys    = pHandler->Key;
+    RTUINT                  cPages    = pHandler->cPages;
     for (;;)
     {
@@ -275 +277 @@
      */
     pHlp->pfnPrintf(pHlp,
-                    "Physical handlers: (PhysHandlers=%d (%#x))\n"
+                    "Physical handlers: max %#x, %u allocator error%s, %u tree error%s\n"
                     "%*s %*s %*s uUser             Type     Description\n",
-                    pVM->pgm.s.pTreesR3->PhysHandlers, pVM->pgm.s.pTreesR3->PhysHandlers,
+                    pVM->pgm.s.PhysHandlerAllocator.m_cNodes,
+                    pVM->pgm.s.PhysHandlerAllocator.m_cErrors, pVM->pgm.s.PhysHandlerAllocator.m_cErrors != 0 ? "s" : "",
+                    pVM->pgm.s.pPhysHandlerTree->m_cErrors, pVM->pgm.s.pPhysHandlerTree->m_cErrors != 0 ? "s" : "",
                     - (int)sizeof(RTGCPHYS) * 2,     "From",
                     - (int)sizeof(RTGCPHYS) * 2 - 3, "- To (incl)",
                     - (int)sizeof(RTHCPTR)  * 2 - 1, "Handler (R3)");
-    RTAvlroGCPhysDoWithAll(&pVM->pgm.s.pTreesR3->PhysHandlers, true, pgmR3InfoHandlersPhysicalOne, &Args);
+    pVM->pgm.s.pPhysHandlerTree->doWithAllFromLeft(&pVM->pgm.s.PhysHandlerAllocator, pgmR3InfoHandlersPhysicalOne, &Args);
 }
 
@@ -289 +293 @@
  *
  * @returns 0
- * @param   pNode   Pointer to a PGMPHYSHANDLER.
- * @param   pvUser  Pointer to command helper functions.
- */
-static DECLCALLBACK(int) pgmR3InfoHandlersPhysicalOne(PAVLROGCPHYSNODECORE pNode, void *pvUser)
-{
-    PPGMPHYSHANDLER         pCur     = (PPGMPHYSHANDLER)pNode;
-    PPGMHANDLERINFOARG      pArgs    = (PPGMHANDLERINFOARG)pvUser;
-    PCDBGFINFOHLP           pHlp     = pArgs->pHlp;
-    PCPGMPHYSHANDLERTYPEINT pCurType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pArgs->pVM, pCur);
+ * @param   pHandler    The physical access handler entry.
+ * @param   pvUser      Pointer to command helper functions.
+ */
+static DECLCALLBACK(int) pgmR3InfoHandlersPhysicalOne(PPGMPHYSHANDLER pHandler, void *pvUser)
+{
+    PPGMHANDLERINFOARG      pArgs = (PPGMHANDLERINFOARG)pvUser;
+    PCDBGFINFOHLP           pHlp  = pArgs->pHlp;
+    PCPGMPHYSHANDLERTYPEINT pType = PGMPHYSHANDLER_GET_TYPE_NO_NULL(pArgs->pVM, pHandler);
     const char *pszType;
-    switch (pCurType->enmKind)
+    switch (pType->enmKind)
     {
         case PGMPHYSHANDLERKIND_MMIO:   pszType = "MMIO   "; break;
@@ -309 +312 @@
     char   szFlags[80];
     size_t cchFlags = 0;
-    if (pCurType->fKeepPgmLock)
+    if (pType->fKeepPgmLock)
         cchFlags = RTStrPrintf(szFlags, sizeof(szFlags), "(keep-pgm-lock");
-    if (pCurType->fRing0DevInsIdx)
+    if (pType->fRing0DevInsIdx)
         cchFlags += RTStrPrintf(&szFlags[cchFlags], sizeof(szFlags) - cchFlags, cchFlags ? ", keep-pgm-lock" : "(keep-pgm-lock");
-    if (pCurType->fRing0Enabled)
+    if (pType->fRing0Enabled)
         cchFlags += RTStrPrintf(&szFlags[cchFlags], sizeof(szFlags) - cchFlags, cchFlags ? ", r0-enabled)" : "(r0-enabled)");
     else
@@ -320 +323 @@
     pHlp->pfnPrintf(pHlp,
                     "%RGp - %RGp  %p  %016RX64  %s  %s  %s\n",
-                    pCur->Core.Key, pCur->Core.KeyLast, pCurType->pfnHandler, pCur->uUser, pszType, pCur->pszDesc, szFlags);
+                    pHandler->Key, pHandler->KeyLast, pType->pfnHandler, pHandler->uUser, pszType, pHandler->pszDesc, szFlags);
 #ifdef VBOX_WITH_STATISTICS
     if (pArgs->fStats)
         pHlp->pfnPrintf(pHlp, "   cPeriods: %9RU64  cTicks: %11RU64  Min: %11RU64  Avg: %11RU64 Max: %11RU64\n",
-                        pCur->Stat.cPeriods, pCur->Stat.cTicks, pCur->Stat.cTicksMin,
-                        pCur->Stat.cPeriods ? pCur->Stat.cTicks / pCur->Stat.cPeriods : 0, pCur->Stat.cTicksMax);
+                        pHandler->Stat.cPeriods, pHandler->Stat.cTicks, pHandler->Stat.cTicksMin,
+                        pHandler->Stat.cPeriods ? pHandler->Stat.cTicks / pHandler->Stat.cPeriods : 0, pHandler->Stat.cTicksMax);
 #endif
     return 0;

trunk/src/VBox/VMM/VMMR3/PGMPool.cpp

@@ -101 +101 @@
 #include <VBox/vmm/mm.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include <VBox/vmm/uvm.h>
 #include "PGMInline.h"

trunk/src/VBox/VMM/VMMR3/PGMSavedState.cpp

@@ -28 +28 @@
 #include <VBox/vmm/pdmdev.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include "PGMInline.h"
 

trunk/src/VBox/VMM/VMMR3/PGMSharedPage.cpp

@@ -26 +26 @@
 #include <VBox/vmm/uvm.h>
 #include "PGMInternal.h"
-#include <VBox/vmm/vm.h>
+#include <VBox/vmm/vmcc.h>
 #include <VBox/sup.h>
 #include <VBox/param.h>

trunk/src/VBox/VMM/include/PGMInline.h

@@ -968 +968 @@
  * Cached physical handler lookup.
  *
- * @returns Physical handler covering @a GCPhys.
- * @param   pVM                 The cross context VM structure.
- * @param   GCPhys              The lookup address.
- */
-DECLINLINE(PPGMPHYSHANDLER) pgmHandlerPhysicalLookup(PVMCC pVM, RTGCPHYS GCPhys)
-{
-    PPGMPHYSHANDLER pHandler = pVM->pgm.s.CTX_SUFF(pLastPhysHandler);
+ * @returns VBox status code.
+ * @retval  VERR_NOT_FOUND if no handler.
+ * @param   pVM         The cross context VM structure.
+ * @param   GCPhys      The lookup address.
+ * @param   ppHandler   Where to return the handler pointer.
+ */
+DECLINLINE(int) pgmHandlerPhysicalLookup(PVMCC pVM, RTGCPHYS GCPhys, PPGMPHYSHANDLER *ppHandler)
+{
+    PPGMPHYSHANDLER pHandler = pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.ptrFromInt(pVM->pgm.s.idxLastPhysHandler);
     if (   pHandler
-        && GCPhys >= pHandler->Core.Key
-        && GCPhys < pHandler->Core.KeyLast)
+        && pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.isPtrRetOkay(pHandler)
+        && GCPhys >= pHandler->Key
+        && GCPhys <  pHandler->KeyLast
+        && pHandler->hType != NIL_PGMPHYSHANDLERTYPE
+        && pHandler->hType != 0)
+
     {
         STAM_COUNTER_INC(&pVM->pgm.s.Stats.CTX_MID_Z(Stat,PhysHandlerLookupHits));
-        return pHandler;
+        *ppHandler = pHandler;
+        return VINF_SUCCESS;
     }
 
     STAM_COUNTER_INC(&pVM->pgm.s.Stats.CTX_MID_Z(Stat,PhysHandlerLookupMisses));
-    pHandler = (PPGMPHYSHANDLER)RTAvlroGCPhysRangeGet(&pVM->pgm.s.CTX_SUFF(pTrees)->PhysHandlers, GCPhys);
-    if (pHandler)
-        pVM->pgm.s.CTX_SUFF(pLastPhysHandler) = pHandler;
-    return pHandler;
+    AssertPtrReturn(pVM->VMCC_CTX(pgm).s.pPhysHandlerTree, VERR_PGM_HANDLER_IPE_1);
+    int rc = pVM->VMCC_CTX(pgm).s.pPhysHandlerTree->lookup(&pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator, GCPhys, &pHandler);
+    if (RT_SUCCESS(rc))
+    {
+        *ppHandler = pHandler;
+        pVM->pgm.s.idxLastPhysHandler = pVM->VMCC_CTX(pgm).s.PhysHandlerAllocator.ptrToInt(pHandler);
+        return VINF_SUCCESS;
+    }
+    *ppHandler = NULL;
+    return rc;
 }
 

trunk/src/VBox/VMM/include/PGMInternal.h

@@ -43 +43 @@
 #include <iprt/list-off32.h>
 #include <iprt/sha.h>
+#include <iprt/cpp/hardavlrange.h>
 
 
@@ -563 +564 @@
 typedef struct PGMPHYSHANDLER
 {
-    AVLROGCPHYSNODECORE                 Core;
+    /** @name Tree stuff.
+     * @{  */
+    /** First address. */
+    RTGCPHYS                            Key;
+    /** Last address. */
+    RTGCPHYS                            KeyLast;
+    uint32_t                            idxLeft;
+    uint32_t                            idxRight;
+    uint8_t                             cHeight;
+    /**  @}  */
+    uint8_t                             abPadding[3];
     /** Number of pages to update. */
     uint32_t                            cPages;
@@ -570 +581 @@
     /** Set if we have pages that have temporarily been disabled. */
     uint32_t                            cTmpOffPages;
-    uint32_t                            u32Padding;
     /** Registered handler type handle.
      * @note Marked volatile to prevent re-reading after validation. */
@@ -578 +588 @@
     /** Description / Name. For easing debugging. */
     R3PTRTYPE(const char *)             pszDesc;
-#ifdef VBOX_WITH_STATISTICS
-    /** Profiling of this handler. */
+    /** Profiling of this handler.
+     * @note VBOX_WITH_STATISTICS only, but included to keep structure stable. */
     STAMPROFILE                         Stat;
-#endif
 } PGMPHYSHANDLER;
+AssertCompileSize(PGMPHYSHANDLER, 12*8);
 /** Pointer to a physical page access handler structure. */
 typedef PGMPHYSHANDLER *PPGMPHYSHANDLER;
@@ -606 +616 @@
 #define PGMPHYSHANDLER_GET_TYPE_NO_NULL(a_pVM, a_pPhysHandler) \
     pgmHandlerPhysicalTypeHandleToPtr2(a_pVM, (a_pPhysHandler) ? (a_pPhysHandler)->hType : NIL_PGMPHYSHANDLERTYPE)
+
+/** Physical access handler allocator. */
+typedef RTCHardAvlTreeSlabAllocator<PGMPHYSHANDLER>   PGMPHYSHANDLERALLOCATOR;
+
+/** Physical access handler tree. */
+typedef RTCHardAvlRangeTree<PGMPHYSHANDLER, RTGCPHYS> PGMPHYSHANDLERTREE;
+/** Pointer to a physical access handler tree. */
+typedef PGMPHYSHANDLERTREE                           *PPGMPHYSHANDLERTREE;
 
 
@@ -2361 +2379 @@
 
 /**
- * Roots and anchors for trees and list employing self relative offsets as
- * pointers.
- *
- * When using self-relative offsets instead of pointers, the offsets needs to be
- * the same in all offsets.  Thus the roots and anchors needs to live on the
- * hyper heap just like the nodes.
- */
-typedef struct PGMTREES
-{
-    /** Physical access handlers (AVL range+offsetptr tree). */
-    AVLROGCPHYSTREE                 PhysHandlers;
-    uint32_t                        u32PaddingTo8Bytes;
-} PGMTREES;
-/** Pointer to PGM trees. */
-typedef PGMTREES *PPGMTREES;
-
-
-/**
  * Guest page table walk for the AMD64 mode.
  */
@@ -2957 +2957 @@
     /** Root of the RAM range search tree for ring-3. */
     R3PTRTYPE(PPGMRAMRANGE)         pRamRangeTreeR3;
-    /** PGM offset based trees - R3 Ptr. */
-    R3PTRTYPE(PPGMTREES)            pTreesR3;
-    /** Caching the last physical handler we looked up in R3. */
-    R3PTRTYPE(PPGMPHYSHANDLER)      pLastPhysHandlerR3;
     /** Shadow Page Pool - R3 Ptr. */
     R3PTRTYPE(PPGMPOOL)             pPoolR3;
@@ -2978 +2974 @@
     /** Root of the RAM range search tree for ring-0. */
     R0PTRTYPE(PPGMRAMRANGE)         pRamRangeTreeR0;
-    /** PGM offset based trees - R0 Ptr. */
-    R0PTRTYPE(PPGMTREES)            pTreesR0;
-    /** Caching the last physical handler we looked up in R0. */
-    R0PTRTYPE(PPGMPHYSHANDLER)      pLastPhysHandlerR0;
     /** Shadow Page Pool - R0 Ptr. */
     R0PTRTYPE(PPGMPOOL)             pPoolR0;
@@ -2998 +2990 @@
      * Initialized to callback causing guru meditations and invalid enmKind. */
     PGMPHYSHANDLERTYPEINTR3         aPhysHandlerTypes[PGMPHYSHANDLERTYPE_COUNT];
+    /** Physical handler allocator, ring-3 edition. */
+#ifdef IN_RING3
+    PGMPHYSHANDLERALLOCATOR         PhysHandlerAllocator;
+#else
+    RTCHardAvlTreeSlabAllocatorR3_T PhysHandlerAllocator;
+#endif
+    /** The pointer to the ring-3 mapping of the physical access handler tree. */
+    R3PTRTYPE(PPGMPHYSHANDLERTREE)  pPhysHandlerTree;
+    /** Caching the last physical handler we looked. */
+    uint32_t                        idxLastPhysHandler;
+
+    uint32_t                        au64Padding3[5];
 
     /** PGM critical section.
@@ -3558 +3562 @@
 
 
+#if defined(IN_RING0) || defined(DOXYGEN_RUNNING)
+
 /**
  * PGM GVMCPU instance data.
@@ -3563 +3569 @@
 typedef struct PGMR0PERVCPU
 {
-#ifdef VBOX_WITH_STATISTICS
+# ifdef VBOX_WITH_STATISTICS
     /** R0: Which statistic this \#PF should be attributed to. */
     R0PTRTYPE(PSTAMPROFILE)         pStatTrap0eAttributionR0;
-#endif
+# endif
     uint64_t                        u64Dummy;
 } PGMR0PERVCPU;
@@ -3589 +3595 @@
      * Initialized to callback causing return to ring-3 and invalid enmKind. */
     PGMPHYSHANDLERTYPEINTR0         aPhysHandlerTypes[PGMPHYSHANDLERTYPE_COUNT];
+    /** Physical handler allocator, ring-3 edition. */
+    PGMPHYSHANDLERALLOCATOR         PhysHandlerAllocator;
+    /** The pointer to the ring-3 mapping of the physical access handler tree. */
+    PPGMPHYSHANDLERTREE             pPhysHandlerTree;
+    /** The allocation object for the physical access handler tree. */
+    RTR0MEMOBJ                      hPhysHandlerMemObj;
+    /** The ring-3 mapping object for the physicall access handler tree. */
+    RTR0MEMOBJ                      hPhysHandlerMapObj;
 } PGMR0PERVM;
+
+#endif /* IN_RING0 || DOXYGEN_RUNNING */
 
 RT_C_DECLS_BEGIN
@@ -3618 +3634 @@
 #define PGM_LOCK_ASSERT_OWNER_EX(a_pVM, a_pVCpu)  Assert(PDMCritSectIsOwnerEx((a_pVCpu), &(a_pVM)->pgm.s.CritSectX))
 
+uint32_t        pgmHandlerPhysicalCalcTableSizes(uint32_t *pcEntries, uint32_t *pcbTreeAndBitmap);
 int             pgmHandlerPhysicalExCreate(PVMCC pVM, PGMPHYSHANDLERTYPE hType, uint64_t uUser,
                                            R3PTRTYPE(const char *) pszDesc, PPGMPHYSHANDLER *ppPhysHandler);