Changeset 25065 in vbox for trunk/src/VBox/Runtime/common/alloc

Timestamp:

Nov 28, 2009 2:29:46 AM (15 years ago)

Author:

vboxsync

Message:

rtHeapOffsetAllocBlock: Rewrote the alignment handling so it doesn't blow up nor leaks memory.

File:

• trunk/src/VBox/Runtime/common/alloc/heapoffset.cpp (modified) (13 diffs)

trunk/src/VBox/Runtime/common/alloc/heapoffset.cpp

@@ -196 +196 @@
  */
 #ifdef RTHEAPOFFSET_STRICT
-# define RTHEAPOFF_TO_PTR(pHeapInt, off, type)   ( (type)rtHeapOffCheckedOffToPtr(pHeapInt, off) )
+# define RTHEAPOFF_TO_PTR_N(pHeapInt, off, type)   ( (type)rtHeapOffCheckedOffToPtr(pHeapInt, off, true /*fNull*/) )
 #else
-# define RTHEAPOFF_TO_PTR(pHeapInt, off, type)   ( (type)((off) ? (uint8_t *)(pHeapInt) + (off) : NULL) )
+# define RTHEAPOFF_TO_PTR_N(pHeapInt, off, type)   ( (type)((off) ? (uint8_t *)(pHeapInt) + (off) : NULL) )
+#endif
+
+/**
+ * Converts an offset to a pointer.
+ *
+ * All offsets are relative to the heap to make life simple.
+ *
+ * @returns Pointer of given type.
+ * @param   pHeapInt        Pointer to the heap anchor block.
+ * @param   off             The offset to convert.
+ * @param   type            The desired type.
+ */
+#ifdef RTHEAPOFFSET_STRICT
+# define RTHEAPOFF_TO_PTR(pHeapInt, off, type)   ( (type)rtHeapOffCheckedOffToPtr(pHeapInt, off, false /*fNull*/) )
+#else
+# define RTHEAPOFF_TO_PTR(pHeapInt, off, type)   ( (type)((uint8_t *)(pHeapInt) + (off)) )
 #endif
 
@@ -323 +339 @@
 #ifdef RTHEAPOFFSET_STRICT
 
-/** Checked version of RTHEAPOFF_TO_PTR. */
-DECLINLINE(void *) rtHeapOffCheckedOffToPtr(PRTHEAPOFFSETINTERNAL pHeapInt, uint32_t off)
-{
+/** Checked version of RTHEAPOFF_TO_PTR and RTHEAPOFF_TO_PTR_N. */
+DECLINLINE(void *) rtHeapOffCheckedOffToPtr(PRTHEAPOFFSETINTERNAL pHeapInt, uint32_t off, bool fNull)
+{
+    Assert(off || fNull);
     if (!off)
         return NULL;
@@ -505 +522 @@
      * Search for a fitting block from the lower end of the heap.
      */
-    for (pFree = RTHEAPOFF_TO_PTR(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE);
+    for (pFree = RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE);
          pFree;
-         pFree = RTHEAPOFF_TO_PTR(pHeapInt, pFree->offNext, PRTHEAPOFFSETFREE))
+         pFree = RTHEAPOFF_TO_PTR_N(pHeapInt, pFree->offNext, PRTHEAPOFFSETFREE))
     {
         uintptr_t offAlign;
@@ -520 +537 @@
         if (offAlign)
         {
+#define DONT_DONATE_ALIGNMENT
+#ifdef DONT_DONATE_ALIGNMENT
+            PRTHEAPOFFSETFREE pPrev;
+
+            offAlign = (uintptr_t)(&pFree[1].Core + 1) & (uAlignment - 1);
+            offAlign = uAlignment - offAlign;
+            if (pFree->cb < cb + offAlign + sizeof(RTHEAPOFFSETFREE))
+                continue;
+
+            /*
+             * Split up the free block into two, so that the 2nd is aligned as
+             * per specification.
+             */
+            pPrev = pFree;
+            pFree = (PRTHEAPOFFSETFREE)((uintptr_t)(pFree + 1) + offAlign);
+            pFree->Core.offPrev = pPrev->Core.offSelf;
+            pFree->Core.offNext = pPrev->Core.offNext;
+            pFree->Core.offSelf = RTHEAPOFF_TO_OFF(pHeapInt, pFree);
+            pFree->Core.fFlags  = RTHEAPOFFSETBLOCK_FLAGS_MAGIC | RTHEAPOFFSETBLOCK_FLAGS_FREE;
+            pFree->offPrev      = pPrev->Core.offSelf;
+            pFree->offNext      = pPrev->offNext;
+            pFree->cb           = (pFree->Core.offNext ? pFree->Core.offNext : pHeapInt->cbHeap)
+                                - pFree->Core.offSelf - sizeof(RTHEAPOFFSETBLOCK);
+
+            pPrev->Core.offNext = pFree->Core.offSelf;
+            pPrev->offNext      = pFree->Core.offSelf;
+            pPrev->cb           = pFree->Core.offSelf - pPrev->Core.offSelf - sizeof(RTHEAPOFFSETBLOCK);
+
+            if (pFree->Core.offNext)
+                RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETBLOCK)->offPrev = pFree->Core.offSelf;
+            if (pFree->offNext)
+                RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETFREE)->offPrev = pFree->Core.offSelf;
+            else
+                pHeapInt->offFreeTail = pFree->Core.offSelf;
+
+            pHeapInt->cbFree -= sizeof(RTHEAPOFFSETBLOCK);
+            ASSERT_BLOCK_FREE(pHeapInt, pPrev);
+            ASSERT_BLOCK_FREE(pHeapInt, pFree);
+
+#else  /* !DONT_DONATE_ALIGNMENT */
             RTHEAPOFFSETFREE Free;
             PRTHEAPOFFSETBLOCK pPrev;
@@ -542 +599 @@
              * for that.)
              */
-            pPrev = RTHEAPOFF_TO_PTR(pHeapInt, Free.Core.offPrev, PRTHEAPOFFSETBLOCK);
+            pPrev = RTHEAPOFF_TO_PTR_N(pHeapInt, Free.Core.offPrev, PRTHEAPOFFSETBLOCK);
             if (pPrev)
             {
@@ -582 +639 @@
             ASSERT_BLOCK_FREE(pHeapInt, pFree);
             ASSERT_BLOCK_USED(pHeapInt, pPrev);
+#endif /* !DONT_DONATE_ALIGNMENT */
         }
 
@@ -590 +648 @@
         {
             /*
-             * Move the FREE block up to make room for the new USED block.
+             * Create a new FREE block at then end of this one.
              */
             PRTHEAPOFFSETFREE   pNew = (PRTHEAPOFFSETFREE)((uintptr_t)&pFree->Core + cb + sizeof(RTHEAPOFFSETBLOCK));
@@ -616 +674 @@
 
             /*
-             * Update the old FREE node making it a USED node.
+             * Adjust and convert the old FREE node into a USED node.
              */
             pFree->Core.fFlags &= ~RTHEAPOFFSETBLOCK_FLAGS_FREE;
@@ -720 +778 @@
     if (pHeapInt->offFreeTail)
     {
-        pRight = RTHEAPOFF_TO_PTR(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETFREE);
+        pRight = RTHEAPOFF_TO_PTR_N(pHeapInt, pFree->Core.offNext, PRTHEAPOFFSETFREE);
         while (pRight && !RTHEAPOFFSETBLOCK_IS_FREE(&pRight->Core))
         {
             ASSERT_BLOCK(pHeapInt, &pRight->Core);
-            pRight = RTHEAPOFF_TO_PTR(pHeapInt, pRight->Core.offNext, PRTHEAPOFFSETFREE);
+            pRight = RTHEAPOFF_TO_PTR_N(pHeapInt, pRight->Core.offNext, PRTHEAPOFFSETFREE);
         }
         if (!pRight)
-            pLeft = RTHEAPOFF_TO_PTR(pHeapInt, pHeapInt->offFreeTail, PRTHEAPOFFSETFREE);
+            pLeft = RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeTail, PRTHEAPOFFSETFREE);
         else
         {
             ASSERT_BLOCK_FREE(pHeapInt, pRight);
-            pLeft = RTHEAPOFF_TO_PTR(pHeapInt, pRight->offPrev, PRTHEAPOFFSETFREE);
+            pLeft = RTHEAPOFF_TO_PTR_N(pHeapInt, pRight->offPrev, PRTHEAPOFFSETFREE);
         }
         if (pLeft)
@@ -739 +797 @@
     ASSERT_L(RTHEAPOFF_TO_OFF(pHeapInt, pLeft), RTHEAPOFF_TO_OFF(pHeapInt, pFree));
     Assert(!pRight || (uintptr_t)pRight > (uintptr_t)pFree);
-    Assert(!pLeft || RTHEAPOFF_TO_PTR(pHeapInt, pLeft->offNext, PRTHEAPOFFSETFREE) == pRight);
+    Assert(!pLeft || RTHEAPOFF_TO_PTR_N(pHeapInt, pLeft->offNext, PRTHEAPOFFSETFREE) == pRight);
 
     /*
@@ -746 +804 @@
     if (!pLeft)
     {
-        Assert(pRight == RTHEAPOFF_TO_PTR(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE));
+        Assert(pRight == RTHEAPOFF_TO_PTR_N(pHeapInt, pHeapInt->offFreeHead, PRTHEAPOFFSETFREE));
         pFree->Core.fFlags |= RTHEAPOFFSETBLOCK_FLAGS_FREE;
         pFree->offPrev = 0;
@@ -831 +889 @@
     for (pBlock = (PRTHEAPOFFSETFREE)(pHeapInt + 1);
          pBlock;
-         pBlock = RTHEAPOFF_TO_PTR(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE))
+         pBlock = RTHEAPOFF_TO_PTR_N(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE))
     {
         if (RTHEAPOFFSETBLOCK_IS_FREE(&pBlock->Core))
@@ -923 +981 @@
     for (pBlock = (PRTHEAPOFFSETFREE)(pHeapInt + 1);
          pBlock;
-         pBlock = RTHEAPOFF_TO_PTR(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE))
+         pBlock = RTHEAPOFF_TO_PTR_N(pHeapInt, pBlock->Core.offNext, PRTHEAPOFFSETFREE))
     {
         size_t cb = (pBlock->offNext ? pBlock->Core.offNext : pHeapInt->cbHeap)