Changeset 97926 in vbox for trunk

Timestamp:

Dec 30, 2022 11:40:02 PM (2 years ago)

Author:

vboxsync

Message:

Add/VBoxGuestR0LibPhysHeap.cpp: Restrict the number of free list entries we consider during allocation to prevent pointless search for a perfect match in a busy and fragmented heap.

Location:

trunk/src/VBox/Additions/common/VBoxGuest/lib

Files:

• VBoxGuestR0LibPhysHeap.cpp (modified) (9 diffs)
• testcase/tstVbglR0PhysHeap-1.cpp (modified) (4 diffs)

trunk/src/VBox/Additions/common/VBoxGuest/lib/VBoxGuestR0LibPhysHeap.cpp

@@ -81 +81 @@
 
 /* Heap block signature */
-#define VBGL_PH_BLOCKSIGNATURE (0xADDBBBBB)
-
+#define VBGL_PH_BLOCKSIGNATURE  UINT32_C(0xADDBBBBB)
 
 /* Heap chunk signature */
-#define VBGL_PH_CHUNKSIGNATURE (0xADDCCCCC)
+#define VBGL_PH_CHUNKSIGNATURE  UINT32_C(0xADDCCCCC)
 /* Heap chunk allocation unit */
-#define VBGL_PH_CHUNKSIZE (0x10000)
-
-/* Heap block bit flags */
-#define VBGL_PH_BF_ALLOCATED (0x1)
+#define VBGL_PH_CHUNKSIZE       (0x10000)
+
+/** Max number of free nodes to search before just using the best fit.
+ *
+ * This is used to limit the free list walking during allocation and just get
+ * on with the job.  A low number should reduce the cache trashing at the
+ * possible cost of heap fragmentation.
+ *
+ * Picked 16 after comparing the tstVbglR0PhysHeap-1 results w/ uRandSeed=42 for
+ * different max values.
+ */
+#define VBGL_PH_MAX_FREE_SEARCH         16
 
 /** Threshold at which to split out a tail free block when allocating.
@@ -438 +445 @@
 DECLR0VBGL(void *) VbglR0PhysHeapAlloc(uint32_t cbSize)
 {
-    VBGLPHYSHEAPBLOCK *pBlock, *pIter;
-    int rc;
+    VBGLPHYSHEAPBLOCK *pBlock;
+    VBGLPHYSHEAPBLOCK *pIter;
+    int32_t            cLeft;
+    int                rc;
 
     /*
@@ -457 +466 @@
      * there to be many blocks in the heap.
      */
-    /** @todo r=bird: Don't walk these lists for ever, use the block count
-     *        statistics to limit the walking to the first X or something. */
+    cLeft  = VBGL_PH_MAX_FREE_SEARCH;
     pBlock = NULL;
     if (cbSize <= PAGE_SIZE / 4 * 3)
@@ -465 +473 @@
            so HGCM processing in VMMDev can use page locks instead of several reads and writes. */
         VBGLPHYSHEAPBLOCK *pFallback = NULL;
-        for (pIter = g_vbgldata.pFreeBlocksHead; pIter != NULL; pIter = pIter->pNext)
+        for (pIter = g_vbgldata.pFreeBlocksHead; pIter != NULL; pIter = pIter->pNext, cLeft--)
         {
             AssertBreak(pIter->u32Signature == VBGL_PH_BLOCKSIGNATURE);
@@ -487 +495 @@
                             pBlock = pIter;
                 }
+
+                if (cLeft > 0)
+                { /* likely */ }
+                else
+                    break;
             }
         }
@@ -496 +509 @@
     {
         /* Large than 3/4 page:  Find closest free list match. */
-        for (pIter = g_vbgldata.pFreeBlocksHead; pIter != NULL; pIter = pIter->pNext)
+        for (pIter = g_vbgldata.pFreeBlocksHead; pIter != NULL; pIter = pIter->pNext, cLeft--)
         {
             AssertBreak(pIter->u32Signature == VBGL_PH_BLOCKSIGNATURE);
@@ -511 +524 @@
                 if (!pBlock || pIter->cbDataSize < pBlock->cbDataSize)
                     pBlock = pIter;
+
+                if (cLeft > 0)
+                { /* likely */ }
+                else
+                    break;
             }
         }
@@ -556 +574 @@
         dumpheap("post alloc");
 
+        /*
+         * Return success.
+         */
         rc = RTSemFastMutexRelease(g_vbgldata.mutexHeap);
 
@@ -562 +583 @@
     }
 
+    /*
+     * Return failure.
+     */
     rc = RTSemFastMutexRelease(g_vbgldata.mutexHeap);
     AssertRC(rc);

trunk/src/VBox/Additions/common/VBoxGuest/lib/testcase/tstVbglR0PhysHeap-1.cpp

@@ -159 +159 @@
         return rc;
     RTTestBanner(hTest);
+
+    /*
+     * Arguments are taken to be random seeding.
+     */
+    uint64_t uRandSeed = RTTimeNanoTS();
+    for (int i = 1; i < argc; i++)
+    {
+        rc = RTStrToUInt64Full(argv[i], 0, &uRandSeed);
+        if (rc != VINF_SUCCESS)
+        {
+            RTTestIFailed("Invalid parameter: %Rrc: %s\n", rc, argv[i]);
+            return RTTestSummaryAndDestroy(hTest);
+        }
+    }
 
     /*
@@ -276 +290 @@
     if (RT_FAILURE(rc))
         return RTTestSummaryAndDestroy(hTest);
-#if 0
-    RTRandAdvSeed(hRand, 42);
-#else
-    RTRandAdvSeed(hRand, RTTimeNanoTS());
-#endif
+    RTRandAdvSeed(hRand, uRandSeed);
+    RTTestValue(hTest, "RandSeed", uRandSeed, RTTESTUNIT_NONE);
 
     static TSTHISTORYENTRY s_aHistory[3072];
@@ -364 +375 @@
         {
             /* free all */
+            RTTestIPrintf(RTTESTLVL_ALWAYS, "Free-all-pre:  cFreeBlocks=%u cAllocedBlocks=%u in %u chunk(s)\n",
+                          g_vbgldata.acBlocks[0], g_vbgldata.acBlocks[1], g_cChunks);
             for (i = 0; i < RT_ELEMENTS(s_aHistory); i++)
             {
@@ -369 +382 @@
                 s_aHistory[i].pv = NULL;
             }
-            RTTestIPrintf(RTTESTLVL_ALWAYS, "after free-all: cFreeBlocks=%u in %u chunk(s)\n", g_vbgldata.acBlocks[0], g_cChunks);
+            RTTestIPrintf(RTTESTLVL_ALWAYS, "Free-all-post: cFreeBlocks=%u in %u chunk(s)\n", g_vbgldata.acBlocks[0], g_cChunks);
             RTTESTI_CHECK_MSG(g_cChunks == 1, ("g_cChunks=%d\n", g_cChunks));
             RTTESTI_CHECK_MSG(g_vbgldata.acBlocks[1] == 0, ("g_vbgldata.acBlocks[1]=%d\n", g_vbgldata.acBlocks[0]));
-#if 0
-            for (VBGLPHYSHEAPCHUNK *pCurChunk = g_vbgldata.pChunkHead; pCurChunk; pCurChunk = pCurChunk->pNext)
-            {
-                RTTestIPrintf(RTTESTLVL_ALWAYS, "pCurChunk=%p: cAllocatedBlocks=%d\n", pCurChunk, pCurChunk->cAllocatedBlocks);
-                uintptr_t const          uEnd        = (uintptr_t)pCurChunk + pCurChunk->cbSize;
-                const VBGLPHYSHEAPBLOCK *pCurBlock   = (const VBGLPHYSHEAPBLOCK *)(pCurChunk + 1);
-                unsigned                 iCurBlock   = 0;
-                while ((uintptr_t)pCurBlock < uEnd)
-                {
-                    RTTestIPrintf(RTTESTLVL_ALWAYS, "  #%2u/%p: cb=%#x %s byte0=%02x\n",
-                                  iCurBlock, pCurBlock, pCurBlock->cbDataSize, pCurBlock->fu32Flags ? "alloc" : "free",
-                                  *(uint8_t const *)(pCurBlock + 1));
-                    pCurBlock = (const VBGLPHYSHEAPBLOCK *)((uintptr_t)(pCurBlock + 1) + pCurBlock->cbDataSize);
-                    iCurBlock++;
-                }
-            }
-#endif
 
             //size_t cbAfterRand = VbglR0PhysHeapGetFreeSize();