Changeset 72579 in vbox

Timestamp:

Jun 16, 2018 2:32:26 PM (7 years ago)

Author:

vboxsync

Message:

EM: Implemented a very simple history record replacement strategy. bugref:9044

Location:

trunk/src/VBox/VMM

Files:

• VMMAll/EMAll.cpp (modified) (2 diffs)
• VMMR3/EM.cpp (modified) (1 diff)
• include/EMInternal.h (modified) (1 diff)

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

@@ -529 +529 @@
      */
     AssertCompile(RT_ELEMENTS(pVCpu->em.s.aExitRecords) == 1024);
-#define EM_EXIT_RECORDS_IDX_MASK 1023
+#define EM_EXIT_RECORDS_IDX_MASK 0x3ff
     uintptr_t  idxSlot  = ((uintptr_t)uFlatPC >> 1) & EM_EXIT_RECORDS_IDX_MASK;
     PEMEXITREC pExitRec = &pVCpu->em.s.aExitRecords[idxSlot];
@@ -537 +537 @@
         pHistEntry->idxSlot = (uint32_t)idxSlot;
         if (pExitRec->uFlagsAndType == uFlagsAndType)
+        {
             pExitRec->uLastExitNo = uExitNo;
+            STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecHits[0]);
+        }
         else
+        {
+            STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecTypeChanged[0]);
             return emHistoryRecordInit(pExitRec, uFlatPC, uFlagsAndType, uExitNo);
+        }
     }
     else if (pExitRec->enmAction == EMEXITACTION_FREE_RECORD)
+    {
+        STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecNew[0]);
         return emHistoryRecordInitNew(pVCpu, pHistEntry, idxSlot, pExitRec, uFlatPC, uFlagsAndType, uExitNo);
+    }
     else
     {
         /*
-         * Collision. Figure out later.
+         * Collision.  We calculate a new hash for stepping away from the first,
+         * doing up to 8 steps away before replacing the least recently used record.
          */
-        return NULL;
-    }
-
+        uintptr_t idxOldest     = idxSlot;
+        uint64_t  uOldestExitNo = pExitRec->uLastExitNo;
+        unsigned  iOldestStep   = 0;
+        unsigned  iStep         = 1;
+        uintptr_t const idxAdd  = (uintptr_t)(uFlatPC >> 11) & (EM_EXIT_RECORDS_IDX_MASK / 4);
+        for (;;)
+        {
+            Assert(iStep < RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecHits));
+            AssertCompile(RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecNew)         == RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecHits));
+            AssertCompile(RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecReplaced)    == RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecHits));
+            AssertCompile(RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecTypeChanged) == RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecHits));
+
+            /* Step to the next slot. */
+            idxSlot += idxAdd;
+            idxSlot &= EM_EXIT_RECORDS_IDX_MASK;
+            pExitRec = &pVCpu->em.s.aExitRecords[idxSlot];
+
+            /* Does it match? */
+            if (pExitRec->uFlatPC == uFlatPC)
+            {
+                Assert(pExitRec->enmAction != EMEXITACTION_FREE_RECORD);
+                pHistEntry->idxSlot = (uint32_t)idxSlot;
+                if (pExitRec->uFlagsAndType == uFlagsAndType)
+                {
+                    pExitRec->uLastExitNo = uExitNo;
+                    STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecHits[iStep]);
+                    break;
+                }
+                STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecTypeChanged[iStep]);
+                return emHistoryRecordInit(pExitRec, uFlatPC, uFlagsAndType, uExitNo);
+            }
+
+            /* Is it free? */
+            if (pExitRec->enmAction == EMEXITACTION_FREE_RECORD)
+            {
+                STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecNew[iStep]);
+                return emHistoryRecordInitNew(pVCpu, pHistEntry, idxSlot, pExitRec, uFlatPC, uFlagsAndType, uExitNo);
+            }
+
+            /* Is it the least recently used one? */
+            if (pExitRec->uLastExitNo < uOldestExitNo)
+            {
+                uOldestExitNo = pExitRec->uLastExitNo;
+                idxOldest     = idxSlot;
+                iOldestStep   = iStep;
+            }
+
+            /* Next iteration? */
+            iStep++;
+            Assert(iStep < RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecReplaced));
+            if (RT_LIKELY(iStep < 8 + 1))
+            { /* likely */ }
+            else
+            {
+                /* Replace the least recently used slot. */
+                STAM_REL_COUNTER_INC(&pVCpu->em.s.aStatHistoryRecReplaced[iOldestStep]);
+                pExitRec = &pVCpu->em.s.aExitRecords[idxOldest];
+                return emHistoryRecordInitNew(pVCpu, pHistEntry, idxOldest, pExitRec, uFlatPC, uFlagsAndType, uExitNo);
+            }
+        }
+    }
 
     /*

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

@@ -451 +451 @@
 
         rc = STAMR3RegisterF(pVM, &pVCpu->em.s.iNextExit, STAMTYPE_U64, STAMVISIBILITY_ALWAYS, STAMUNIT_OCCURENCES,
-                             "Number of recorded exits (R0/RC).", "/PROF/CPU%u/EM/RecordedExits", i);
+                             "Number of recorded exits.", "/PROF/CPU%u/EM/RecordedExits", i);
         AssertRC(rc);
 
+        /* History record statistics */
+        rc = STAMR3RegisterF(pVM, &pVCpu->em.s.cExitRecordUsed, STAMTYPE_U32, STAMVISIBILITY_ALWAYS, STAMUNIT_OCCURENCES,
+                             "Number of used hash table entries.", "/EM/CPU%u/ExitHashing/Used", i);
+        AssertRC(rc);
+
+        for (uint32_t iStep = 0; iStep < RT_ELEMENTS(pVCpu->em.s.aStatHistoryRecHits); iStep++)
+        {
+            rc = STAMR3RegisterF(pVM, &pVCpu->em.s.aStatHistoryRecHits[iStep], STAMTYPE_COUNTER, STAMVISIBILITY_USED, STAMUNIT_OCCURENCES,
+                                 "Number of hits at this step.",             "/EM/CPU%u/ExitHashing/Step%02u-Hits", i, iStep);
+            AssertRC(rc);
+            rc = STAMR3RegisterF(pVM, &pVCpu->em.s.aStatHistoryRecTypeChanged[iStep], STAMTYPE_COUNTER, STAMVISIBILITY_USED, STAMUNIT_OCCURENCES,
+                                 "Number of type changes at this step.",     "/EM/CPU%u/ExitHashing/Step%02u-TypeChanges", i, iStep);
+            AssertRC(rc);
+            rc = STAMR3RegisterF(pVM, &pVCpu->em.s.aStatHistoryRecTypeChanged[iStep], STAMTYPE_COUNTER, STAMVISIBILITY_USED, STAMUNIT_OCCURENCES,
+                                 "Number of replacments at this step.",     "/EM/CPU%u/ExitHashing/Step%02u-Replacments", i, iStep);
+            AssertRC(rc);
+            rc = STAMR3RegisterF(pVM, &pVCpu->em.s.aStatHistoryRecNew[iStep], STAMTYPE_COUNTER, STAMVISIBILITY_USED, STAMUNIT_OCCURENCES,
+                                 "Number of new inserts at this step.",     "/EM/CPU%u/ExitHashing/Step%02u-NewInserts", i, iStep);
+            AssertRC(rc);
+        }
     }
 

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

@@ -506 +506 @@
     /** Exit history table (6KB). */
     EMEXITENTRY             aExitHistory[256];
+
+    /** Hit statistics for each lookup step. */
+    STAMCOUNTER             aStatHistoryRecHits[16];
+    /** Type change statistics for each lookup step. */
+    STAMCOUNTER             aStatHistoryRecTypeChanged[16];
+    /** Replacement statistics for each lookup step. */
+    STAMCOUNTER             aStatHistoryRecReplaced[16];
+    /** New record statistics for each lookup step. */
+    STAMCOUNTER             aStatHistoryRecNew[16];
     /** Number of exit records in use. */
     uint32_t                cExitRecordUsed;
-    /** Number of exit records collisions. */
-    uint32_t                cExitRecordCollisions;
+    /** Explicit padding. */
+    uint32_t                uPadding2;
     /** Exit records (32KB). (Aligned on 32 byte boundrary.) */
     EMEXITREC               aExitRecords[1024];