Changeset 2503 for trunk/src/win32k/misc/rmalloc_avl.c

Timestamp:

Jan 23, 2000, 4:20:53 AM (26 years ago)

Author:

bird

Message:

Initial resident heap coding completed.
The AVL heap is seems to be much faster; it uses 40% of the time that the
traditional linked-list based heap is using when executing the heaptest.

File:

• trunk/src/win32k/misc/rmalloc_avl.c (modified) (29 diffs)

trunk/src/win32k/misc/rmalloc_avl.c

@@ -1 @@
-/* $Id: rmalloc_avl.c,v 1.1 2000-01-22 18:21:03 bird Exp $
+/* $Id: rmalloc_avl.c,v 1.2 2000-01-23 03:20:53 bird Exp $
  *
  * Resident Heap - AVL.
@@ -18 +18 @@
 #ifdef DEBUG
     #define DEBUG_ALLOC
-    #define ALLWAYS_HEAPCHECK
+    #undef ALLWAYS_HEAPCHECK
 #endif
 
@@ -31 +31 @@
                             ((PMEMBLOCKFREE)((unsigned)(a) - CB_HDR + 4))
 #define BLOCKSIZE (1024*256)            /* 256KB */
-
+#define ALIGNMENT 4
 
 #define INCL_DOS
@@ -139 +139 @@
 static PMEMBLOCK    resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
 static PMEMBLOCK    resFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
+static int          resCheckAVLTree(PMEMBLOCK pmb);
+static int          resCheckAVLTreeFree(PAVLNODECORE pNode);
 static unsigned     _res_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pCb);
 static unsigned     _res_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam);
@@ -193 +195 @@
             else
             {   /* other nodes of this size: replace pmbf with the first node in the chain. */
-                memcpy((void*)&pmbfTmp->pmbfNext->coreFree, (void*)&pmbfTmp->coreFree,
-                       sizeof(pmbfTmp->coreFree));
+                memcpy((void*)&pmbfTmp->pmbfNext->coreFree, (void*)&pmbfTmp->coreFree, sizeof(pmbfTmp->coreFree));
                 if (pmbfParent != NULL)
                 {
                     pmbfParent = MEMBLOCKFREE_FROM_FREESIZENODE(pmbfParent);
-                    if (pmbfTmp->coreFree.Key > pmbfParent->coreFree.Key)
-                        pmbfParent->coreFree.pLeft = (PAVLNODECORE)pmbf->pmbfNext;
+                    if (pmbfTmp->coreFree.Key < pmbfParent->coreFree.Key)
+                        pmbfParent->coreFree.pLeft = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
                     else
-                        pmbfParent->coreFree.pRight = (PAVLNODECORE)pmbf->pmbfNext;
+                        pmbfParent->coreFree.pRight = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
                 }
                 else
-                    pha->pcoreFreeSize = (PAVLNODECORE)pmbf->pmbfNext;
+                    pha->pcoreFreeSize = (PAVLNODECORE)&pmbf->pmbfNext->coreFree;
             }
         }
@@ -231 +232 @@
     }
     else
+    {
+        pmbf->pmbfNext = NULL;
         AVLInsert((PPAVLNODECORE)&pha->pcoreFreeSize, &pmbf->coreFree);
+    }
 }
 
@@ -271 +275 @@
     if (pmbfLeft == NULL && pmbfRight == NULL)
     {   /* 1 - insert no merge */
+        pmbf->core.Key = (AVLKEY)pmbf;
         AVLInsert((PPAVLNODECORE)&pha->pmbFree, (PAVLNODECORE)pmbf);
         resInsertIntoFreeSize(pha, pmbf);
     }
     else if (pmbfLeft != NULL && pmbfRight == NULL)
-    {   /* 2 - insert left merge */
+    {   /* 2 - insert left merge: just add pmbf to pmbfLeft. */
         resRemoveFromFreeSize(pha, pmbfLeft);
         pmbfLeft->coreFree.Key += CB_HDR + pmbf->coreFree.Key;
@@ -282 +287 @@
     }
     else if (pmbfLeft == NULL && pmbfRight != NULL)
-    {   /* 3 - insert right merge */
+    {   /* 3 - insert right merge: replace pmbfRight with pmbf in the pmbfFree tree; */
         resRemoveFromFreeSize(pha, pmbfRight);
-        memcpy((void*)&pmbf->pmbfNext->core, (void*)&pmbfRight->core,
-               sizeof(pmbf->core));
+        memcpy((void*)&pmbf->core, (void*)&pmbfRight->core, sizeof(pmbf->core));
         pmbf->core.Key = (AVLKEY)pmbf;
         pmbf->coreFree.Key += CB_HDR + pmbfRight->coreFree.Key;
@@ -302 +306 @@
     else
     {   /* 4 -insert both left and right merge */
+        if (AVLRemove((PPAVLNODECORE)&pha->pmbFree, (AVLKEY)pmbfRight) != (PAVLNODECORE)pmbfRight)
+        {
+            kprintf(("resInsertFree: AVLRemove on pmbfRight failed.\n"));
+            return;
+        }
         resRemoveFromFreeSize(pha, pmbfLeft);
         resRemoveFromFreeSize(pha, pmbfRight);
-        pmbfRight = (PMEMBLOCKFREE)AVLRemove((PPAVLNODECORE)&pha->pmbFree,
-                                             (AVLKEY)PNEXT_BLOCK(pmb));
         pmbfLeft->coreFree.Key += CB_HDR*2 + pmbf->coreFree.Key + pmbfRight->coreFree.Key;
         pha->cbFree += CB_HDR*2;
@@ -328 +335 @@
     unsigned cbTotalSize = 0;
 
-    cbUserSize = MAX(ALIGN(cbUserSize, 4), sizeof(MEMBLOCKFREE) - CB_HDR);
+    cbUserSize = MAX(ALIGN(cbUserSize, ALIGNMENT), sizeof(MEMBLOCKFREE) - CB_HDR);
 
     *ppha = phaFirst;
@@ -335 +342 @@
         if ((*ppha)->cbFree >= cbUserSize + CB_HDR)
         {
-            PMEMBLOCKFREE pmbfTmp;
             PMEMBLOCKFREE pmbf;
 
@@ -342 +348 @@
             {
                 pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pmbf);
-                if (pmbf->pmbfNext == NULL)
+                resRemoveFromFreeSize(*ppha, pmbf);
+                (*ppha)->cbFree -= pmbf->coreFree.Key;
+
+                /* pmbf is now the block which we are to return, but do we have to split it? */
+                if (pmbf->coreFree.Key > sizeof(MEMBLOCKFREE) + cbUserSize)
                 {
-                    if (AVLRemove(&(*ppha)->pcoreFreeSize, pmbf->coreFree.Key) == NULL)
-                    {
-                        kprintf(("resGetFreeMemblock: internal error AVLRemove from the free-size list failed.\n"));
-                        continue;
-                    }
+                    PMEMBLOCKFREE pmbfTmp = pmbf;
+                    pmbf = (PMEMBLOCKFREE)((unsigned)pmbfTmp + pmbfTmp->coreFree.Key - cbUserSize);
+                    #ifdef DEBUG_ALLOC
+                        pmbf->ulSignature = MEMBLOCK_SIGNATURE;
+                    #endif
+                    pmbfTmp->coreFree.Key -= CB_HDR + cbUserSize;
+                    pmbf->coreFree.Key = cbUserSize;
+                    (*ppha)->cbFree += pmbfTmp->coreFree.Key;
+                    resInsertIntoFreeSize(*ppha, pmbfTmp);
                 }
                 else
                 {
-                    pmbfTmp = pmbf;
-                    pmbf = pmbf->pmbfNext;
-                    pmbfTmp->pmbfNext = pmbf->pmbfNext;
-                }
-                AVLRemove((PPAVLNODECORE)&(*ppha)->pmbFree, (AVLKEY)pmbf);
-                (*ppha)->cbFree -= pmbf->coreFree.Key;
-
-                /* pmbf is now the block which we are to return, but do we have to split it? */
-                if (pmbf->coreFree.Key > sizeof(MEMBLOCKFREE) + cbUserSize)
-                {
-                    pmbfTmp = (PMEMBLOCKFREE)((unsigned)pmbf + CB_HDR + cbUserSize);
-                    #ifdef DEBUG_ALLOC
-                        pmbfTmp->ulSignature = MEMBLOCK_SIGNATURE;
-                    #endif
-                    pmbfTmp->coreFree.Key = pmbf->coreFree.Key - CB_HDR - cbUserSize;
-                    pmbf->coreFree.Key = cbUserSize;
-                    resInsertFree(*ppha, (PMEMBLOCK)pmbfTmp);
+                    PMEMBLOCKFREE pmbfTmp = (PMEMBLOCKFREE)AVLRemove((PPAVLNODECORE)&(*ppha)->pmbFree, (AVLKEY)pmbf);
+                    if (pmbfTmp != pmbf)
+                    {
+                        kprintf(("resGetFreeMemblock: Internal heap error - failed to Remove best fit block!\n"));
+                        return NULL;
+                    }
                 }
                 return (PMEMBLOCK)pmbf;
@@ -653 +656 @@
  * @returns   Pointer to new heapblock.
  * @param     pv     Pointer to the block to realloc.
+ *                   If pv is NULL, this call is equal to malloc.
  * @param     cbNew  The new block size.
  */
@@ -660 +664 @@
     PHEAPANCHOR pha;
 
+    #ifdef ALLWAYS_HEAPCHECK
+        if (!_res_heap_check())
+        {
+            kprintf(("rmalloc: _res_heap_check failed!\n"));
+            return NULL;
+        }
+    #endif
     pmb = resFindUsedBlock(SSToDS(&pha), pv);
     if (pmb != NULL)
@@ -665 +676 @@
         void *pvRet;
 
-        cbNew = ALIGN(cbNew, 4);
+        cbNew = MAX(ALIGN(cbNew, ALIGNMENT), sizeof(MEMBLOCKFREE) - CB_HDR);
         if (cbNew <= pmb->cbSize)
         {   /* shrink block */
@@ -671 +682 @@
             if (cbNew + sizeof(MEMBLOCKFREE) <= pmb->cbSize)
             {   /* split block */
-                PMEMBLOCK pmbNew = (PMEMBLOCK)((unsigned)pmb + CB_HDR + cbNew);
+                PMEMBLOCKFREE pmbfNew = (PMEMBLOCKFREE)((unsigned)pmb + CB_HDR + cbNew);
                 #ifdef DEBUG_ALLOC
-                    pmbNew->ulSignature = MEMBLOCK_SIGNATURE;
+                    pmbfNew->ulSignature = MEMBLOCK_SIGNATURE;
                 #endif
-                pmbNew->cbSize = pmb->cbSize - cbNew - CB_HDR;
+                pha->cbUsed -= pmb->cbSize - cbNew;
+                pmbfNew->coreFree.Key = pmb->cbSize - cbNew - CB_HDR;
                 pmb->cbSize = cbNew;
-                resInsertFree(pha, pmbNew);
+                resInsertFree(pha, (PMEMBLOCK)pmbfNew);
+                #ifdef ALLWAYS_HEAPCHECK
+                    if (!_res_heap_check())
+                    {
+                        kprintf(("rrealloc: _res_heap_check failed!\n"));
+                        return NULL;
+                    }
+                #endif
             }
         }
         else
         {   /* expand block - this code may be more optimized... */
-            pvRet = rmalloc(cbNew);
-            if (pvRet != NULL)
-            {
-                memcpy(pvRet, pv, pmb->cbSize);
-                rfree(pv);
-            }
+            #if 1
+                pvRet = rmalloc(cbNew);
+                if (pvRet != NULL)
+                {
+                    memcpy(pvRet, pv, pmb->cbSize);
+                    rfree(pv);
+                }
+            #else
+                /* optimized */
+                PMEMBLOCK pmb
+            #endif
         }
         return pvRet;
+    }
+    else
+    {
+        if (pv == NULL)
+            return rmalloc(cbNew);
+        kprintf(("rrealloc: invalid user pointer, pv=0x%08x\n", pv));
     }
     return NULL;
@@ -855 +885 @@
         {
             kprintf(("_res_heap_check: invalid signature for pha=0x%08x\n", pha));
+            Int3();
             return FALSE;
         }
@@ -861 +892 @@
         {
             kprintf(("_res_heap_check: cbFree + cbUsed >= cbSize for pha=0x%08x\n", pha));
+            Int3();
             return FALSE;
         }
@@ -867 +899 @@
         {
             kprintf(("_res_heap_check: error in heap anchor chain.\n"));
+            Int3();
             return FALSE;
         }
@@ -875 +908 @@
                      "    block. pmbFree=0x%08x, pmbUsed=0x%08x, pha+1=0x%08x\n",
                      pmbFree, pmbUsed, pha+1));
+            Int3();
+            return FALSE;
+        }
+
+        /*
+         * Check the tree AVL-trees - !extra debug test!
+         */
+        if (resCheckAVLTree(pha->pmbUsed) != 0)
+        {
+            kprintf(("_res_heap_check: the Used tree is invalid.\n"));
+            Int3();
+            return FALSE;
+        }
+        if (resCheckAVLTree(pha->pmbFree) != 0)
+        {
+            kprintf(("_res_heap_check: the Free tree is invalid.\n"));
+            Int3();
+            return FALSE;
+        }
+        if (resCheckAVLTreeFree(pha->pcoreFreeSize) != 0)
+        {
+            kprintf(("_res_heap_check: the free-size tree is invalid.\n"));
+            Int3();
             return FALSE;
         }
@@ -905 +961 @@
                 /* error hole */
                 kprintf(("_res_heap_check: internal error - memory hole!\n"));
+                Int3();
                 return FALSE;
                 }
@@ -914 +971 @@
                 cbUsed += pmbUsed->cbSize;
                 if (pmbUsed->ulSignature != MEMBLOCK_SIGNATURE)
+                {
+                    kprintf(("_res_heap_check: invalid signature on used block, pmbUsed=0x%08x\n", pmbUsed));
+                    Int3();
                     return FALSE;
+                }
+                if (pmbUsed->cbSize < sizeof(MEMBLOCKFREE) - CB_HDR)
+                {
+                    kprintf(("_res_heap_check: internal error - cbSize is to small! (used), cbSize=%d\n", pmbUsed->cbSize));
+                    Int3();
+                    return FALSE;
+                }
                 pmbLast = pmbUsed;
                 pmbUsed = pmbUsedNext;
@@ -921 +988 @@
             else
             {
+                PMEMBLOCKFREE pmbf = (PMEMBLOCKFREE)AVLGet((PPAVLNODECORE)&pha->pcoreFreeSize, pmbFree->cbSize);
+                if (pmbf != NULL)
+                {
+                    pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pmbf);
+                    while (pmbf != NULL && pmbf != (PMEMBLOCKFREE)pmbFree)
+                        pmbf = pmbf->pmbfNext;
+                    if (pmbf == NULL)
+                    {
+                        kprintf(("_res_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
+                        Int3();
+                        return FALSE;
+                    }
+                }
+                else
+                {
+                    kprintf(("_res_heap_check: pmbFree=0x%08 is not found in the free-size-tree.\n", pmbFree));
+                    Int3();
+                    return FALSE;
+                }
+
                 cbSize += CB_HDR + pmbFree->cbSize;
                 cbFree += pmbFree->cbSize;
                 if (pmbFree->ulSignature != MEMBLOCK_SIGNATURE)
+                {
+                    kprintf(("_res_heap_check: invalid signature on free block, pmbUsed=0x%08x\n", pmbFree));
+                    Int3();
                     return FALSE;
+                }
+                if (pmbFree->cbSize < sizeof(MEMBLOCKFREE) - CB_HDR)
+                {
+                    kprintf(("_res_heap_check: internal error - cbSize is to small! (free), cbSize=%d\n", pmbFree->cbSize));
+                    Int3();
+                    return FALSE;
+                }
                 pmbLast = pmbFree;
                 pmbFree = pmbFreeNext;
@@ -938 +1035 @@
         {
             kprintf(("_res_heap_check: cbFree(%d) != pha->cbFree(%d)\n", cbFree, pha->cbFree));
+            Int3();
             return FALSE;
         }
@@ -944 +1042 @@
         {
             kprintf(("_res_heap_check: cbUsed(%d) != pha->cbUsed(%d)\n", cbUsed, pha->cbUsed));
+            Int3();
             return FALSE;
         }
@@ -950 +1049 @@
         {
             kprintf(("_res_heap_check: cbTotal(%d) != pha->cbSize(%d)\n", cbSize, pha->cbSize));
+            Int3();
             return FALSE;
         }
@@ -960 +1060 @@
                      "    pmbLast(end)=0x%08x, pha+pha->cbSize=0x%08x\n",
                      pmbLast != NULL ? PNEXT_BLOCK(pmbLast) : NULL, (unsigned)pha + pha->cbSize));
+            Int3();
             return FALSE;
         }
@@ -975 +1076 @@
     {
         kprintf(("_res_heap_check: internal error - heap anchor chain didn't end on phaLast\n"));
+        Int3();
         return FALSE;
     }
@@ -983 +1085 @@
 }
 
+
+/**
+ * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
+ */
+static int resCheckAVLTree(PMEMBLOCK pmb)
+{
+    if (pmb == NULL)
+        return 0;
+    if (pmb->core.Key != (AVLKEY)pmb)
+    {
+        kprintf(("resCheckAVLTree: Invalid Key!\n"));
+        Int3();
+        return -1;
+    }
+    if (pmb->core.pLeft != NULL && (pmb->core.pLeft < (PAVLNODECORE)0x10000 || pmb->core.Key <= (AVLKEY)pmb->core.pLeft))
+    {
+        kprintf(("resCheckAVLTree: Invalid pLeft!\n"));
+        Int3();
+        return -1;
+    }
+    if (pmb->core.pRight != NULL && (pmb->core.pRight < (PAVLNODECORE)0x10000 || pmb->core.Key >= (AVLKEY)pmb->core.pRight))
+    {
+        kprintf(("resCheckAVLTree: Invalid pRight!\n"));
+        Int3();
+        return -1;
+    }
+    if (pmb->core.pLeft != NULL && resCheckAVLTree((PMEMBLOCK)pmb->core.pLeft) != 0)
+        return -1;
+    if (pmb->core.pRight != NULL && resCheckAVLTree((PMEMBLOCK)pmb->core.pRight) != 0)
+        return -1;
+    return 0;
+}
+
+
+/**
+ * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
+ */
+static int resCheckAVLTreeFree(PAVLNODECORE pNode)
+{
+    PMEMBLOCKFREE pmbf;
+    if (pNode == NULL)
+        return 0;
+    if (pNode->Key < 4 || (pNode->Key % 4) != 0)
+    {
+        kprintf(("resCheckAVLTreeFree: Invalid Key! 0x%08x\n", pNode->Key));
+        Int3();
+        return -1;
+    }
+    if (pNode->pLeft != NULL && (pNode->pLeft < (PAVLNODECORE)0x10000 || pNode->Key <= pNode->pLeft->Key))
+    {
+        kprintf(("resCheckAVLTreeFree: Invalid pLeft!\n"));
+        Int3();
+        return -1;
+    }
+    if (pNode->pRight != NULL && (pNode->pRight < (PAVLNODECORE)0x10000 || pNode->Key >= pNode->pRight->Key))
+    {
+        kprintf(("resCheckAVLTreeFree: Invalid pRight!\n"));
+        Int3();
+        return -1;
+    }
+    pmbf = MEMBLOCKFREE_FROM_FREESIZENODE(pNode);
+    if (pmbf->pmbfNext != NULL && pmbf->pmbfNext < (PMEMBLOCKFREE)0x10000)
+    {
+        kprintf(("resCheckAVLTreeFree: invalid pmbfNext pointer, pmbfNext=0x%08x\n", pmbf->pmbfNext));
+        Int3();
+        return -1;
+    }
+    while (pmbf->pmbfNext != NULL)
+    {
+        if (pmbf->pmbfNext < (PMEMBLOCKFREE)0x10000)
+        {
+            kprintf(("resCheckAVLTreeFree: invalid pmbfNext pointer, pmbfNext=0x%08x\n", pmbf->pmbfNext));
+            Int3();
+            return -1;
+        }
+        if (pmbf->coreFree.Key != pNode->Key)
+        {
+            kprintf(("resCheckAVLTreeFree: invalid key, pmbf->coreFree.Key=%d, pNode->Key=%d\n", pmbf->coreFree.Key, pNode->Key));
+            Int3();
+            return -1;
+        }
+        /* next */
+        pmbf = pmbf->pmbfNext;
+    }
+
+    if (pNode->pLeft != NULL && resCheckAVLTreeFree(pNode->pLeft) != 0)
+        return -1;
+    if (pNode->pRight != NULL && resCheckAVLTreeFree(pNode->pRight) != 0)
+        return -1;
+    return 0;
+}