Changeset 2503 for trunk/src

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.

Location:

trunk/src/win32k/misc

Files:

• heaptest.c (modified) (16 diffs)
• rmalloc.c (modified) (3 diffs)
• rmalloc_avl.c (modified) (29 diffs)

trunk/src/win32k/misc/heaptest.c

@@ -1 @@
-/* $Id: heaptest.c,v 1.1 2000-01-22 18:21:03 bird Exp $
+/* $Id: heaptest.c,v 1.2 2000-01-23 03:20:52 bird Exp $
  *
  * Test of resident and swappable heaps.
@@ -13 +13 @@
 *   Defined Constants
 *******************************************************************************/
-#define NUMBER_OF_POINTERS      10240
-#define RANDOMTEST_ITERATIONS   10240
+#define NUMBER_OF_POINTERS      16384
+#define RANDOMTEST_ITERATIONS   65536*2
+#define Int3()          __interrupt(3)
 
 
@@ -22 +23 @@
 #include "malloc.h"
 #include "rmalloc.h"
+#include "macros.h"
 #include <stdio.h>
 #include <stdlib.h>
+#include <memory.h>
+#include <builtin.h>
 
 
@@ -36 +40 @@
     unsigned      crmalloc;
     unsigned      crfree;
-
+    unsigned      crealloc;
     int           i;
 
@@ -54 +58 @@
  *
  */
+#if 1
     /*
      * Simple allocation test.
@@ -62 +67 @@
         {
             acb[i] = rand();
-        } while(acb[i] == 0 || acb[i] > 64);
-
+        } while(acb[i] == 0 || acb[i] > 127);
+
+        if ((i % (NUMBER_OF_POINTERS/3)) == 1)
+            acb[i] += 1024*260;
         apv[i] = rmalloc(acb[i]);
         if (apv[i] == NULL)
@@ -71 +78 @@
                 break;
         }
+        memset(apv[i], 0xA, MIN(acb[i],16));
         cb += acb[i];
     }
@@ -83 +91 @@
     {
         int cb = _res_msize(apv[i]);
-        if (cb != ((acb[i] + 3) & ~3) && (cb < ((acb[i] + 3) & ~3) || cb > 40 + ((acb[i] + 3) & ~3)) )
+        if (cb != ((acb[i] + 3) & ~3) && (cb < ((acb[i] + 3) & ~3) || cb > 52 + ((acb[i] + 3) & ~3)) )
             printf("size of avp[%d] (%d) != acb[%] (%d)\n", i, cb, i, acb[i]);
         rfree(apv[i]);
@@ -101 +109 @@
     printf("\n_res_dump_subheaps:\n");
     _res_dump_subheaps();
+#endif
 
 
@@ -115 +124 @@
     crfree = 0;
     crmalloc = 0;
+    crealloc = 0;
     while (i++ < RANDOMTEST_ITERATIONS || cAllocations > 0)
     {
@@ -120 +130 @@
         j = rand();
         if (cAllocations + (NUMBER_OF_POINTERS/20) < NUMBER_OF_POINTERS &&
-            (i < RANDOMTEST_ITERATIONS*1/4 ? (j % 8) > 1 :
-             i < RANDOMTEST_ITERATIONS*2/4 ? (j % 8) > 2 :
-             i < RANDOMTEST_ITERATIONS*3/4 ? (j % 8) > 3 :
+            (i < RANDOMTEST_ITERATIONS*1/4 ? (j % 8) > 2 :
+             i < RANDOMTEST_ITERATIONS*2/4 ? (j % 8) > 3 :
+             i < RANDOMTEST_ITERATIONS*3/4 ? (j % 8) > 4 :
              i < RANDOMTEST_ITERATIONS     ? (j % 8) > 5 : 0
              )
@@ -134 +144 @@
                 {
                     acb[j] = rand();
-                } while (acb[j] == 0 || acb[j] > 2048);
+                } while (acb[j] == 0 || (acb[j] > 2048 && (i % 11) != 10));
+                if ((i % (RANDOMTEST_ITERATIONS/20)) == 1)
+                    acb[j] += 1024*256;
                 apv[j] = rmalloc(acb[j]);
                 if (apv[j] == NULL)
@@ -141 +153 @@
                     if (acb[j] > 10000)
                         continue;
-                }
+                    break;
+                }
+                memset(apv[j], 0xA, MIN(acb[j],16));
                 cAllocations++;
                 cb += acb[j];
@@ -148 +162 @@
         }
         else
-        { /* free */
+        { /* free or realloc */
             if (cAllocations == 0)
                 continue;
+
             if (cAllocations < NUMBER_OF_POINTERS/10)
             {
@@ -162 +177 @@
                 {
                     j = rand();
-                } while (k < NUMBER_OF_POINTERS/2 && (j >= NUMBER_OF_POINTERS || apv[j] == NULL));
+                } while (k++ < NUMBER_OF_POINTERS/2 && (j >= NUMBER_OF_POINTERS || apv[j] == NULL));
                 if (k >= NUMBER_OF_POINTERS/2)
                 {
@@ -173 +188 @@
             {
                 int cb = _res_msize(apv[j]);
-                if (cb != ((acb[j] + 3) & ~3) && (cb < ((acb[j] + 3) & ~3) || cb > 40 + ((acb[j] + 3) & ~3)) )
+                if (cb != ((acb[j] + 3) & ~3) && (cb < ((acb[j] + 3) & ~3) || cb > 52 + ((acb[j] + 3) & ~3)) )
                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", j, cb, j, acb[j]);
-                rfree(apv[j]);
-                apv[j] = NULL;
-                cAllocations--;
-                crfree++;
+                if (i < RANDOMTEST_ITERATIONS*3/4 && j % 3 == 0)
+                {   /* realloc */
+                    int cb;
+                    void *pv;
+                    crealloc++;
+                    do
+                    {
+                        cb = rand();
+                    } while (cb == 0 || cb > 3072);
+                    /*
+                    if (i >= 0x1c14)
+                        Int3();
+                    */
+                    pv = rrealloc(apv[j], cb);
+                    if (pv == NULL)
+                    {
+                        printf("realloc(apv[%d](0x%08), %d) failed\n", j, apv[j], cb);
+                        continue;
+                    }
+                    apv[j] = pv;
+                    acb[j] = cb;
+                }
+                else
+                {   /* free */
+                    rfree(apv[j]);
+                    apv[j] = NULL;
+                    cAllocations--;
+                    crfree++;
+                }
             }
         }
-        _res_heap_check();
-        if (RANDOMTEST_ITERATIONS == i*2)
+        /*_res_heap_check();*/
+        if (RANDOMTEST_ITERATIONS/2 == i)
             _res_dump_subheaps();
-    }
-
-    printf("cb=%d crfree=%d crmalloc=%d\n", cb, crfree, crmalloc);
+        if ((i % 2048) == 0)
+            printf("i=%d cAllocations=%d\n", i, cAllocations);
+    }
+
+    printf("cb=%d crfree=%d crmalloc=%d crealloc=%d\n", cb, crfree, crmalloc, crealloc);
 
     printf("_res_dump_subheaps:\n");

trunk/src/win32k/misc/rmalloc.c

@@ -1 @@
-/* $Id: rmalloc.c,v 1.1 2000-01-22 18:21:03 bird Exp $
+/* $Id: rmalloc.c,v 1.2 2000-01-23 03:20:53 bird Exp $
  *
  * Resident Heap.
@@ -18 +18 @@
 #ifdef DEBUG
     #define DEBUG_ALLOC
-    #define ALLWAYS_HEAPCHECK
+    #undef ALLWAYS_HEAPCHECK
 #endif
 
@@ -553 +553 @@
                 pmbNew->cbSize = pmb->cbSize - cbNew - CB_HDR;
                 pmbNew->pNext = NULL;
+                pha->cbUsed -= pmb->cbSize - cbNew;
                 pmb->cbSize = cbNew;
                 resInsertFree(pha, pmbNew);

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;
+}