Changeset 2511 for trunk/src/win32k/misc

Timestamp:

Jan 24, 2000, 7:19:01 PM (26 years ago)

Author:

bird

Message:

Heapchanges: Heap is splitted into a swappable and a resident. The heaps
are dynamically growable.

Location:

trunk/src/win32k/misc

Files:

• heaptest.c (modified) (19 diffs)
• makefile (added)
• malloc.c (modified) (11 diffs)
• malloc_old.c (modified) (2 diffs)
• rmalloc_avl.c (modified) (24 diffs)
• smalloc_avl.c (modified) (23 diffs)

trunk/src/win32k/misc/heaptest.c

@@ -1 @@
-/* $Id: heaptest.c,v 1.4 2000-01-24 03:05:13 bird Exp $
+/* $Id: heaptest.c,v 1.5 2000-01-24 18:18:59 bird Exp $
  *
  * Test of resident and swappable heaps.
@@ -13 +13 @@
 *   Defined Constants
 *******************************************************************************/
-#define NUMBER_OF_POINTERS      1024
-#define RANDOMTEST_ITERATIONS   65536*2
-#define Int3()          __interrupt(3)
-
+#define NUMBER_OF_POINTERS      16384
+#define RANDOMTEST_ITERATIONS   65536
+#define EXTRA_HEAPCHECK
 
 /*******************************************************************************
@@ -25 +24 @@
 #include "smalloc.h"
 #include "macros.h"
+#include "asmutils.h"
 #include <stdio.h>
 #include <stdlib.h>
 #include <memory.h>
-#include <builtin.h>
 
 
@@ -43 +42 @@
     unsigned      crealloc;
     int           i;
-    int           fResTests = 0;
-    int           fResSimple = 0;
-    int           fResRandom = 0;
+    int           fResTests = 1;
+    int           fResSimple = 1;
+    int           fResRandom = 1;
     int           fSwpTests = 1;
-    int           fSwpSimple = 0;
+    int           fSwpSimple = 1;
     int           fSwpRandom = 1;
     enum   {malloc,realloc, free, unknown} enmLast = unknown;
@@ -98 +97 @@
                         break;
                 }
-                memset(apv[i], 0xA, MIN(acb[i],16));
+                memset(apv[i], 0xA, acb[i]);
                 cb += acb[i];
             }
@@ -113 +112 @@
                 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] (%d)\n", i, cb, i, acb[i]);
+                memset(apv[i], 0xF, acb[i]);
                 rfree(apv[i]);
                 enmLast = free;
@@ -179 +179 @@
                             break;
                         }
-                        memset(apv[j], 0xA, MIN(acb[j],16));
+                        memset(apv[j], 0xA, acb[j]);
                         cAllocations++;
                         cb += acb[j];
@@ -236 +236 @@
                             apv[j] = pv;
                             acb[j] = cb;
+                            memset(apv[j], 0xB, acb[j]);
                         }
                         else
                         {   /* free */
+                            memset(apv[j], 0xF, acb[j]);
                             rfree(apv[j]);
                             enmLast = free;
@@ -247 +249 @@
                     }
                 }
+                #ifdef EXTRA_HEAPCHECK
                 _res_heap_check();
+                #endif
                 if (RANDOMTEST_ITERATIONS/2 == i)
                     _res_dump_subheaps();
@@ -277 +281 @@
     if (fSwpTests)
     {
+        printf("\nSwappable heap tests\nSwappable heap tests\n");
         if (fSwpSimple)
         {
@@ -282 +287 @@
              * Simple allocation test.
              */
+            printf("\nSimple swappable heap tests\nSimple swappable heap tests\n");
             for (i = 0; i < NUMBER_OF_POINTERS; i++)
             {
@@ -299 +305 @@
                         break;
                 }
-                memset(apv[i], 0xA, MIN(acb[i],16));
+                memset(apv[i], 0xA, acb[i]);
                 cb += acb[i];
             }
@@ -314 +320 @@
                 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] (%d)\n", i, cb, i, acb[i]);
+                memset(apv[i], 0xF, acb[i]);
                 sfree(apv[i]);
                 enmLast = free;
@@ -340 +347 @@
              */
             printf("\n"
-                   "Random allocation and freeing test:\n");
+                   "Random allocation and freeing test (swappable)\n"
+                   "Random allocation and freeing test (swappable)\n"
+                   );
             for (i = 0; i < NUMBER_OF_POINTERS; i++)
                 apv[i] = NULL, acb[i] = 0;
@@ -380 +389 @@
                             break;
                         }
-                        memset(apv[j], 0xA, MIN(acb[j],16));
+                        memset(apv[j], 0xA, acb[j]);
                         cAllocations++;
                         cb += acb[j];
@@ -437 +446 @@
                             apv[j] = pv;
                             acb[j] = cb;
+                            memset(apv[j], 0xB, acb[j]);
                         }
                         else
                         {   /* free */
+                            memset(apv[j], 0xF, acb[j]);
                             sfree(apv[j]);
                             enmLast = free;
@@ -448 +459 @@
                     }
                 }
+                #ifdef EXTRA_HEAPCHECK
                 _swp_heap_check();
+                #endif
                 if (RANDOMTEST_ITERATIONS/2 == i)
+                {
                     _swp_dump_subheaps();
+                    _res_dump_subheaps();
+                }
                 if ((i % 2048) == 0)
                     printf("i=%d cAllocations=%d\n", i, cAllocations);
@@ -459 +475 @@
             printf("_swp_dump_subheaps:\n");
             _swp_dump_subheaps();
+            printf("_res_dump_subheaps:\n");
+            _res_dump_subheaps();
 
             printf("_swp_memfree - before heapmin: %d\n", _swp_memfree());
@@ -466 +484 @@
             printf("_swp_dump_subheaps:\n");
             _swp_dump_subheaps();
+            printf("_res_dump_subheaps:\n");
+            _res_dump_subheaps();
         } /* fSwpRandom */
     }

trunk/src/win32k/misc/malloc.c

@@ -1 @@
-/* $Id: malloc.c,v 1.5 1999-11-10 01:45:36 bird Exp $
+/* $Id: malloc.c,v 1.6 2000-01-24 18:19:00 bird Exp $
  *
- * Heap.
+ * Common Heap - this forwards to the swappable heap!
  *
  * Note: This heap does very little checking on input.
  *       Use with care! We're running at Ring-0!
  *
- * Copyright (c) 1999 knut st. osmundsen
+ * Copyright (c) 1999-2000 knut st. osmundsen
  *
  * Project Odin Software License can be found in LICENSE.TXT
  *
  */
-
-#define static
-/******************************************************************************
-*  Defined macros and constants
-******************************************************************************/
-#ifdef DEBUG
-    #define DEBUG_ALLOC
-#endif
-
-#define SIGNATURE 0xBEEFFEEB
-/*#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
-#define CB_HDR (int)&(((PMEMBLOCK)0)->achUserData[0])
-#define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
-
-#define INCL_DOS
-#define INCL_DOSERRORS
-#ifdef RING0
-    #define INCL_NOAPI
-#else
-    #define INCL_DOSMEMMGR
-#endif
-
+/*******************************************************************************
+*   Defined Constants And Macros                                               *
+*******************************************************************************/
+#define INCL_NOAPI
 
 /******************************************************************************
@@ -38 +20 @@
 ******************************************************************************/
 #include <os2.h>
-#ifdef RING0
-    #include "dev32hlp.h"
-    #include "asmutils.h"
-#else
-    #include <builtin.h>
-    #define Int3() __interrupt(3)
-#endif
-#include "log.h"
-#include "malloc.h"
-#include <memory.h>
+#include "smalloc.h"
+#include "rmalloc.h"
+#include "options.h"
 
-
-/******************************************************************************
-*  Structs and Typedefs
-******************************************************************************/
-#pragma pack(1)
-typedef struct _MEMBLOCK /* MB */
-{
-#ifdef DEBUG_ALLOC
-   unsigned long     ulSignature;   /* should be SIGNATURE (0xBEEFFEEB) */
-#endif
-   unsigned          cbSize;        /* size of user space (achBlock)*/
-   struct _MEMBLOCK *pNext;
-   unsigned char     achUserData[1];
-} MEMBLOCK, *PMEMBLOCK;
-#pragma pack()
 
 /******************************************************************************
 *  Global data
 ******************************************************************************/
-/*#pragma info(nogen, nouni, noext)*/
-static PMEMBLOCK   pUsed;         /* pointer to the used memblock chain. */
-static PMEMBLOCK   pFree;         /* pointer to the free memblock chain. */
-static unsigned    cbFree;        /* bytes of free user memory in the heap.*/
-unsigned           _uHeapMinPtr;  /* heap pointers are greater or equal to this.*/
-unsigned           _uHeapMaxPtr;  /* heap pointers are less than this. */
 #ifndef RING0
     char           fInited;       /* init flag */
 #endif
 
-/******************************************************************************
-*  Internal functions
-******************************************************************************/
-static void         insertUsed(PMEMBLOCK pMemblock);
-static void         insertFree(PMEMBLOCK pMemblock);
-static PMEMBLOCK    getFreeMemblock(unsigned cbUserSize);
-static PMEMBLOCK    findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin);
 
 
 /**
- * Inserts a memblock into the used chain
- * @param    pMemblock  Pointer to memblock which is to inserted.
- * @remark   Sorts on address.
+ * Initiate the heap "subsystems" - both the resident and the swappable heaps.
+ * @returns   0 on success, not 0 on error.
+ * @param     cbResInit  Resident heap initial size.
+ * @param     cbResMax   Resident heap maximum size.
+ * @param     cbSwpInit  Swappable heap initial size.
+ * @param     cbSwpMax   Swappable heap maximum size.
  */
-static void insertUsed(PMEMBLOCK pMemblock)
+int heapInit(unsigned cbResInit, unsigned cbResMax,
+             unsigned cbSwpInit, unsigned cbSwpMax)
 {
-    if (pUsed == NULL || pUsed > pMemblock)
-    {
-        pMemblock->pNext = pUsed;
-        pUsed = pMemblock;
-    }
-    else
-    {
-        PMEMBLOCK pMb = pUsed;
-        while (pMb->pNext != NULL && pMb->pNext < pMemblock)
-            pMb = pMb->pNext;
+    int rc;
 
-        pMemblock->pNext = pMb->pNext;
-        pMb->pNext= pMemblock;
-    }
-}
-
-
-/**
- * Inserts a memblock into the free chain.
- * Merges blocks adjecent blocks.
- * @param    pMemblock  Pointer to memblock to insert into the free list.
- * @remark   Sorts on address.
- */
-static void insertFree(PMEMBLOCK pMemblock)
-{
-    cbFree += pMemblock->cbSize;
-    if (pMemblock < pFree || pFree == NULL)
-    {
-        /* test for merge with 2nd block */
-        if (pFree != NULL && PNEXT_BLOCK(pMemblock) == pFree)
-        {
-            cbFree += pMemblock->cbSize + CB_HDR;
-            pFree->cbSize += CB_HDR;
-            #ifdef DEBUG_ALLOC
-                pMemblock->ulSignature = 0xF0EEEE0F;
-            #endif
-        }
-        else
-        {
-           pMemblock->pNext = pFree;
-           pFree = pMemblock;
-
-        }
-    }
-    else
-    {
-        PMEMBLOCK pMb = pFree;
-        while (pMb->pNext != NULL && pMb->pNext < pMemblock)
-            pMb = pMb->pNext;
-
-        /* test for merge with left block */
-        if (PNEXT_BLOCK(pMb) == pMemblock)
-        {
-            pMb->cbSize += CB_HDR + pMemblock->cbSize;
-            cbFree += CB_HDR;
-            #ifdef DEBUG_ALLOC
-                pMemblock->ulSignature = 0xF0EEEE0F;
-            #endif
-            pMemblock = pMb;
-        }
-        else
-        {
-            pMemblock->pNext = pMb->pNext;
-            pMb->pNext = pMemblock;
-        }
-
-        /* test for merge with right block */
-        if (PNEXT_BLOCK(pMemblock) == pMemblock->pNext && pMemblock->pNext != NULL)
-        {
-            pMemblock->cbSize += CB_HDR + pMemblock->pNext->cbSize;
-            cbFree += CB_HDR;
-            #ifdef DEBUG_ALLOC
-                pMemblock->pNext->ulSignature = 0xF0EEEE0F;
-            #endif
-            pMemblock->pNext = pMemblock->pNext->pNext;
-        }
-    }
-}
-
-
-/**
- * Finds a free block at the requested size.
- * @returns  Pointer to block (not in free list any longer).
- * @param    cbUserSize  Bytes the user have requested.
- * @sketch   cbUserSize is aligned to nearest 4 bytes.
- *
- *
- */
-static PMEMBLOCK getFreeMemblock(unsigned cbUserSize)
-{
-    PMEMBLOCK pBestFit     = NULL;
-    PMEMBLOCK pBestFitPrev = NULL;
-    PMEMBLOCK pCur  = pFree;
-    PMEMBLOCK pPrev = NULL;
-
-    cbUserSize = (cbUserSize + 3) & ~3;
-
-    /* search for block */
-    while (pCur != NULL)
-    {
-        /* check for perfect match first */
-        if (pCur->cbSize == cbUserSize)
-            break;
-            /* TODO: The following test may need to be adjusted later. */
-        else if (pCur->cbSize >= cbUserSize
-                && (pBestFit == NULL || pCur->cbSize < pBestFit->cbSize)
-                )
-        {
-            pBestFit = pCur;
-            pBestFitPrev = pPrev;
-        }
-
-        /* next */
-        pPrev = pCur;
-        pCur = pCur->pNext;
-    }
-
-    /* link out block */
-    if (pCur != NULL)
-    {   /* prefect match */
-        if (pPrev != NULL)
-            pPrev->pNext = pCur->pNext;
-        else
-            pFree = pCur->pNext;
-
-        cbFree -= cbUserSize;
-    }
-    else if (pBestFit != NULL)
-    {   /* best fit */
-        /* two cases 1) split block. 2) block is too small to be splitted. */
-        if (pBestFit->cbSize > cbUserSize + CB_HDR)
-        {
-            pCur = (PMEMBLOCK)((unsigned)pBestFit + pBestFit->cbSize - cbUserSize);
-            #ifdef DEBUG_ALLOC
-                pCur->ulSignature = SIGNATURE;
-            #endif
-            pCur->cbSize = cbUserSize;
-            pBestFit->cbSize -= cbUserSize + CB_HDR;
-
-            cbFree -= cbUserSize + CB_HDR;
-        }
-        else
-        {
-            if (pBestFitPrev != NULL)
-                pBestFitPrev->pNext = pBestFit->pNext;
-            else
-                pFree = pBestFit->pNext;
-            pCur = pBestFit;
-
-            cbFree -= pCur->cbSize;
-        }
-    }
-
-    return pCur;
-}
-
-
-/**
- * Finds a memory block starting the search at pMemblock.
- * @returns   Pointer to memblock if found.
- * @param     pMemblock  Start node.
- * @param     pvUser     User pointer to find the block to.
- * @param     fWithin    When this flag is set, the pointer may point anywhere within the block.
- */
-static PMEMBLOCK    findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin)
-{
-    if (pvUser != NULL && pMemblock != NULL)
-    {
-        if (fWithin)
-            while (pMemblock != NULL &&
-                   !(pvUser >= (void*)pMemblock && pvUser < (void*)PNEXT_BLOCK(pMemblock))
-                   )
-                pMemblock = pMemblock->pNext;
-        else
-        {
-            pvUser = (void*)((unsigned)pvUser - CB_HDR);
-            while (pMemblock != NULL && pvUser != (void*)pMemblock)
-                pMemblock = pMemblock->pNext;
-        }
-    }
-    else
-        pMemblock = NULL;
-
-    return pMemblock;
-}
-
-
-/**
- * Initiate the heap "subsystem".
- * @returns   0 on success, not 0 on error.
- * @param     cbSize  Heapsize in bytes.
- */
-int heapInit(unsigned cbSize)
-{
-    pUsed = NULL;
-
-    #ifdef RING0
-        pFree = D32Hlp_VMAlloc(VMDHA_SWAP, cbSize, ~0UL);
-    #else
-        if (DosAllocMem((void*)&pFree, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
-            pFree = NULL;
-    #endif
-    if (pFree == NULL)
-    {
-        kprintf(("unable to allocate heap memory.\n"));
-        Int3();
-        return -1;
-    }
-
-    #ifdef DEBUG_ALLOC
-        pFree->ulSignature = SIGNATURE;
-    #endif
-    pFree->cbSize = cbSize - CB_HDR;
-    pFree->pNext = NULL;
-    cbFree = pFree->cbSize;
-
-    _uHeapMinPtr = (unsigned)pFree + CB_HDR;
-    _uHeapMaxPtr = (unsigned)pFree + cbSize;
-
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-        {
-            /* error! */
-            kprintf(("%s: _heap_check failed!\n", "heapInit"));
-            Int3();
-            return -2;
-        }
-    #endif
+    rc = resHeapInit(cbResInit, cbResMax);
+    if (rc != 0)
+        return rc;
+    rc = swpHeapInit(cbSwpInit, cbSwpMax);
+    if (rc != 0)
+        return rc;
     #ifdef RING3
         fInited = TRUE;
@@ -338 +69 @@
 void * malloc(unsigned cbSize)
 {
-    void *pvRet = NULL;
-
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-        {
-            kprintf(("%s: _heap_check failed!\n", "malloc"));
-            return NULL;
-        }
-    #endif
-
-    if (cbSize != 0)
-    {
-        PMEMBLOCK pMemblock = getFreeMemblock(cbSize);
-        if (pMemblock != NULL)
-        {
-            insertUsed(pMemblock);
-            pvRet = &pMemblock->achUserData[0];
-        }
-    }
-    else
-    {
-        /* error! */
-        kprintf(("%s: error cbSize = 0\n", "malloc"));
-    }
-
-    return pvRet;
+    return smalloc(cbSize);
 }
 
@@ -375 +81 @@
 void *realloc(void *pv, unsigned cbNew)
 {
-    PMEMBLOCK pMemblock;
-    pMemblock = findBlock(pUsed, pv, FALSE);
-    if (pMemblock != NULL)
-    {
-        void *pvRet;
-
-        cbNew = (cbNew + 3) & ~3;
-        if (cbNew <= pMemblock->cbSize)
-        {   /* shrink block */
-            pvRet = pv;
-            if (cbNew + CB_HDR < pMemblock->cbSize)
-            {   /* split block */
-                PMEMBLOCK pNewBlock = (PMEMBLOCK)((unsigned)pMemblock + CB_HDR + cbNew);
-                #ifdef DEBUG_ALLOC
-                    pNewBlock->ulSignature = SIGNATURE;
-                #endif
-                pNewBlock->cbSize = pMemblock->cbSize - cbNew - CB_HDR;
-                pNewBlock->pNext = NULL;
-                pMemblock->cbSize = cbNew;
-                insertFree(pNewBlock);
-            }
-        }
-        else
-        {   /* expand block */
-            pvRet = malloc(cbNew);
-            if (pvRet != NULL)
-            {
-                memcpy(pvRet, pv, pMemblock->cbSize);
-                free(pv);
-            }
-        }
-        return pvRet;
-    }
-    return NULL;
+    return srealloc(pv, cbNew);
 }
 
@@ -418 +91 @@
 void free(void *pv)
 {
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-        {
-            kprintf(("free: _heap_check failed!\n"));
-            return;
-        }
-    #endif
-
-    if (pv != NULL)
-    {
-        PMEMBLOCK pCur  = pUsed;
-        PMEMBLOCK pPrev = NULL;
-        pv = (void*)((int)pv - CB_HDR);
-
-        while (pCur != NULL &&
-        #ifdef DEBUG_ALLOC /* pointer within block */
-               !(pv >= (void*)pCur && (void*)((unsigned)pv + CB_HDR) < (void*)PNEXT_BLOCK(pCur))
-        #else
-               pv != (void*)pCur
-        #endif
-               )
-        {
-            pPrev = pCur;
-            pCur = pCur->pNext;
-        }
-
-        if (pCur != NULL)
-        {
-            if (pv == pCur)
-            {
-                if (pPrev != NULL)
-                    pPrev->pNext = pCur->pNext;
-                else
-                    pUsed = pCur->pNext;
-
-                insertFree(pCur);
-
-                #ifdef DEBUG_ALLOC
-                    if (!_heap_check())
-                        kprintf(("%s: _heap_check failed 3!\n", "free"));
-                #endif
-            }
-            else
-                kprintf(("free: pv is not pointing to start of block.\n"));
-        }
-        else
-            kprintf(("free: heap block not found!\n"));
-    }
-    else
-        kprintf(("free: Free received a NULL pointer!\n"));
+    sfree(pv);
 }
 
@@ -477 +101 @@
 unsigned _msize(void *pv)
 {
-    PMEMBLOCK pBlock;
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-            kprintf(("_msize: _heap_check failed!\n"));
-    #endif
-    pBlock = findBlock(pUsed, pv, FALSE);
-    return pBlock != NULL ? pBlock->cbSize : 0;
+    return _swp_msize(pv);
 }
 
@@ -494 +112 @@
 int _validptr(void *pv)
 {
-    PMEMBLOCK pBlock;
-
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-            kprintf(("_validptr: _heap_check failed!\n"));
-    #endif
-
-    pBlock = findBlock(pUsed, pv, TRUE);
-    return pBlock != NULL;
+    return _swp_validptr(pv);
 }
 
@@ -514 +124 @@
 int _validptr2(void *pv, unsigned cbSize)
 {
-    PMEMBLOCK pBlock;
-
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-            kprintf(("_validptr: _heap_check failed!\n"));
-    #endif
-
-    pBlock = findBlock(pUsed, pv, TRUE);
-    return pBlock != NULL ? (pBlock->cbSize - ((unsigned)pv - (unsigned)pBlock - CB_HDR)) >= cbSize : FALSE;
+    return _swp_validptr2(pv, cbSize);
 }
 
@@ -536 +138 @@
 unsigned _memfree(void)
 {
-    #ifdef DEBUG_ALLOC
-        if (!_heap_check())
-            kprintf(("_memfree: _heap_check failed!\n"));
-    #endif
-    return cbFree;
+    return _swp_memfree();
 }
 
@@ -552 +150 @@
 int _heap_check(void)
 {
-    #ifdef DEBUG_ALLOC
-        PMEMBLOCK pCurFree = pFree;
-        PMEMBLOCK pCurUsed = pUsed;
-
-        while (pCurFree != NULL || pCurUsed != NULL)
-        {
-            /** @sketch:
-             * check signatures and for lost memory.
-             *
-             * three cases:
-             *  1) pCurUsed adjecent to pCurUsed->pNext
-             *  2) pCurUsed adjecent to pCurFree
-             *  3) pCurFree adjecent to pCurFree->pNext
-             *  4) pCurFree adjecent to pCurUsed
-             *  5) pCurUsed is the last block
-             *  6) pCurFree is the last block
-             */
-            #if 0
-            if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext)       /* 1.*/
-                ;
-            else if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree)         /* 2.*/
-                ;
-            else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext)  /* 3.*/
-                ;
-            else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed)         /* 4.*/
-                ;
-            else if (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL)   /* 5.*/
-                ;
-            else if (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL)   /* 6.*/
-                ;
-            else
-            #else
-            if (!( (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext)    /* 1.*/
-                || (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree)           /* 2.*/
-                || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext)    /* 3.*/
-                || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed)           /* 4.*/
-                || (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
-                || (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
-                 )
-               )
-            #endif
-                {
-                /* error hole */
-                kprintf(("_heap_check: internal error - memory hole!\n"));
-                return FALSE;
-                }
-
-            /* check signature and advance to the next block */
-            if (pCurUsed != NULL && (pCurFree == NULL || pCurUsed < pCurFree))
-            {
-                if (pCurUsed->ulSignature != SIGNATURE)
-                    return FALSE;
-                pCurUsed = pCurUsed->pNext;
-            }
-            else
-            {
-                if (pCurFree->ulSignature != SIGNATURE)
-                    return FALSE;
-                pCurFree = pCurFree->pNext;
-            }
-        }
-    #endif
-    return TRUE;
+    return _swp_heap_check();
 }
 
@@ -626 +162 @@
 int _rmem_init(void)
 {
-    int rc = heapInit(0x100000);
+    int rc = heapInit(CB_RES_INIT, CB_RES_MAX, CB_SWP_INIT, CB_SWP_MAX);
     return rc;
 }

trunk/src/win32k/misc/malloc_old.c

@@ -1 @@
-/* $Id: malloc_old.c,v 1.1 2000-01-24 12:48:42 bird Exp $
+/* $Id: malloc_old.c,v 1.2 2000-01-24 18:19:00 bird Exp $
  *
  * Heap.
@@ -40 +40 @@
 #ifdef RING0
     #include "dev32hlp.h"
-    #include "asmutils.h"
-#else
-    #include <builtin.h>
-    #define Int3() __interrupt(3)
 #endif
+#include "asmutils.h"
 #include "log.h"
 #include "malloc.h"

trunk/src/win32k/misc/rmalloc_avl.c

@@ -1 @@
-/* $Id: rmalloc_avl.c,v 1.4 2000-01-24 03:05:14 bird Exp $
+/* $Id: rmalloc_avl.c,v 1.5 2000-01-24 18:19:00 bird Exp $
  *
  * Resident Heap - AVL.
@@ -16 +16 @@
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
+#pragma info(notrd)
 #ifdef DEBUG
     #define DEBUG_ALLOC
-    #define ALLWAYS_HEAPCHECK
+    #undef ALLWAYS_HEAPCHECK
+    #undef SOMETIMES_HEAPCHECK
 #endif
 
@@ -41 +43 @@
 #endif
 
-
 /******************************************************************************
 *  Headerfiles
@@ -48 +49 @@
 #ifdef RING0
     #include "dev32hlp.h"
-    #include "asmutils.h"
-#else
-    #include <builtin.h>
-    #define Int3() __interrupt(3)
 #endif
+#include "asmutils.h"
 #include "log.h"
 #include "rmalloc.h"
-#include <memory.h>
 #include "dev32.h"
 #include "avl.h"
 #include "macros.h"
+#include <memory.h>
 
 
@@ -139 +137 @@
 static PMEMBLOCK    resFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
 static PMEMBLOCK    resFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
+#ifdef DEBUG_ALLOC
 static int          resCheckAVLTree(PMEMBLOCK pmb);
 static int          resCheckAVLTreeFree(PAVLNODECORE pNode);
+#endif
 static unsigned     _res_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pCb);
 static unsigned     _res_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam);
@@ -252 +252 @@
     PMEMBLOCKFREE   pmbfRightParent;
     PMEMBLOCKFREE   pmbfLeft;
-    PMEMBLOCKFREE   pmbfTmp;
 
     pha->cbFree += pmb->cbSize;
@@ -592 +591 @@
     resInsertFree(phaFirst, pmb);
 
-    #ifdef ALLWAYS_HEAPCHECK
+    #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
         if (!_res_heap_check())
         {   /* error! */
@@ -602 +601 @@
         }
     #endif
-    #ifdef RING3
-        fInited = TRUE;
+    #ifndef RING0
+        fResInited = TRUE;
     #endif
     return 0;
@@ -618 +617 @@
 void * rmalloc(unsigned cbSize)
 {
-    #ifdef ALLWAYS_HEAPCHECK
+    #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
     if (!_res_heap_check())
     {
@@ -655 +654 @@
     PHEAPANCHOR pha;
 
-    #ifdef ALLWAYS_HEAPCHECK
+    #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
     if (!_res_heap_check())
     {
@@ -778 +777 @@
 void rfree(void *pv)
 {
-    #ifdef ALLWAYS_HEAPCHECK
-        if (!_res_heap_check())
-        {
-            kprintf(("rfree: _res_heap_check failed!\n"));
-            return;
-        }
+    #if defined(ALLWAYS_HEAPCHECK) || defined(SOMETIMES_HEAPCHECK)
+    if (!_res_heap_check())
+    {
+        kprintf(("rfree: _res_heap_check failed!\n"));
+        return;
+    }
     #endif
 
@@ -825 +824 @@
 
     #ifdef ALLWAYS_HEAPCHECK
-        if (!_res_heap_check())
-            kprintf(("_res_msize: _res_heap_check failed!\n"));
+    if (!_res_heap_check())
+        kprintf(("_res_msize: _res_heap_check failed!\n"));
     #endif
 
@@ -841 +840 @@
 int _res_validptr(void *pv)
 {
-    PHEAPANCHOR pha;
     PMEMBLOCK   pmb;
 
     #ifdef ALLWAYS_HEAPCHECK
-        if (!_res_heap_check())
-            kprintf(("_res_validptr: _res_heap_check failed!\n"));
+    if (!_res_heap_check())
+        kprintf(("_res_validptr: _res_heap_check failed!\n"));
     #endif
 
@@ -862 +860 @@
 int _res_validptr2(void *pv, unsigned cbSize)
 {
-    PHEAPANCHOR pha;
     PMEMBLOCK   pmb;
 
     #ifdef ALLWAYS_HEAPCHECK
-        if (!_res_heap_check())
-            kprintf(("_res_validptr: _res_heap_check failed!\n"));
+    if (!_res_heap_check())
+        kprintf(("_res_validptr: _res_heap_check failed!\n"));
     #endif
 
@@ -889 +886 @@
 
     #ifdef ALLWAYS_HEAPCHECK
-        if (!_res_heap_check())
-            kprintf(("_res_memfree: _res_heap_check failed!\n"));
+    if (!_res_heap_check())
+        kprintf(("_res_memfree: _res_heap_check failed!\n"));
     #endif
 
@@ -917 +914 @@
         AVLENUMDATA FreeEnumData;
         AVLENUMDATA UsedEnumData;
-        PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbFree, &FreeEnumData, TRUE);
-        PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(&FreeEnumData);
-        PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbUsed, &UsedEnumData, TRUE);
-        PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(&UsedEnumData);
+        PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbFree,
+                                                        SSToDS(&FreeEnumData), TRUE);
+        PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&FreeEnumData));
+        PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree((PPAVLNODECORE)&pha->pmbUsed,
+                                                        SSToDS(&UsedEnumData), TRUE);
+        PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&UsedEnumData));
         PMEMBLOCK pmbLast = NULL;
         unsigned  cbFree = 0;
@@ -1031 +1030 @@
                 pmbLast = pmbUsed;
                 pmbUsed = pmbUsedNext;
-                pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(&UsedEnumData);
+                pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&UsedEnumData));
             }
             else
@@ -1071 +1070 @@
                 pmbLast = pmbFree;
                 pmbFree = pmbFreeNext;
-                pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(&FreeEnumData);
+                pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(SSToDS(&FreeEnumData));
             }
         }
@@ -1133 +1132 @@
 
 
+#ifdef DEBUG_ALLOC
 /**
  * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
@@ -1143 +1143 @@
     {
         kprintf(("resCheckAVLTree: Invalid Key!\n"));
+        Int3();
+        return -1;
+    }
+    if (pmb->core.Key % ALIGNMENT != 0)
+    {
+        kprintf(("resCheckAVLTree: Data is not correctly aligned, uData=0x%08x\n", pmb->core.Key));
         Int3();
         return -1;
@@ -1223 +1229 @@
     return 0;
 }
+#endif
 
 
@@ -1289 +1296 @@
     while (pha != NULL)
     {
-        PMEMBLOCK pmb;
-        SUBHEAPS_CALLBACK_PARAM FreeParam = {0};
-        SUBHEAPS_CALLBACK_PARAM UsedParam = {0};
+        SUBHEAPS_CALLBACK_PARAM FreeParam = {0, 0};
+        SUBHEAPS_CALLBACK_PARAM UsedParam = {0, 0};
 
         AVLDoWithAll((PPAVLNODECORE)&pha->pmbUsed, 1,
-                     (PAVLCALLBACK)_res_dump_subheaps_callback, &UsedParam);
+                     (PAVLCALLBACK)_res_dump_subheaps_callback, SSToDS(&UsedParam));
         AVLDoWithAll((PPAVLNODECORE)&pha->pmbFree, 1,
-                     (PAVLCALLBACK)_res_dump_subheaps_callback, &FreeParam);
+                     (PAVLCALLBACK)_res_dump_subheaps_callback, SSToDS(&FreeParam));
 
         kprintf(("HeapAnchor %2d addr=0x%08x cbSize=%6d cbFree=%6d cbUsed=%6d cUsed=%4d cFree=%d\n",
@@ -1338 +1344 @@
 {
     PHEAPANCHOR pha;
-    ALLOCATED_CALLBACK_PARAM Param = {0};
+    ALLOCATED_CALLBACK_PARAM Param = {cb, 0, 0};
 
     kprintf(("----------------------------\n"
@@ -1349 +1355 @@
         /* iterate thru tree using callback */
         AVLDoWithAll((PPAVLNODECORE)&pha->pmbUsed, TRUE,
-                     (PAVLCALLBACK)_res_dump_allocated_callback, &Param);
+                     (PAVLCALLBACK)_res_dump_allocated_callback, SSToDS(&Param));
 
         /* next */

trunk/src/win32k/misc/smalloc_avl.c

@@ -1 @@
-/* $Id: smalloc_avl.c,v 1.2 2000-01-24 03:05:14 bird Exp $
+/* $Id: smalloc_avl.c,v 1.3 2000-01-24 18:19:00 bird Exp $
  *
  * Swappable Heap - AVL.
@@ -16 +16 @@
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
+#pragma info(notrd)
 #ifdef DEBUG
     #define DEBUG_ALLOC
-    #define ALLWAYS_HEAPCHECK
-    #define SOMETIMES_HEAPCHECK
+    #undef ALLWAYS_HEAPCHECK
+    #undef SOMETIMES_HEAPCHECK
 #endif
 
@@ -60 +61 @@
 #ifdef RING0
     #include "dev32hlp.h"
-    #include "asmutils.h"
-#else
-    #include <builtin.h>
-    #define Int3() __interrupt(3)
 #endif
+#include "asmutils.h"
 #include "log.h"
 #include "smalloc.h"
 #include "rmalloc.h"
-#include <memory.h>
 #include "dev32.h"
 #include "avl.h"
 #include "macros.h"
+#include <memory.h>
 
 
@@ -162 +160 @@
 static PMEMBLOCK    swpFindUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
 static PMEMBLOCK    swpFindWithinUsedBlock(PHEAPANCHOR *ppha, void *pvUser);
+#ifdef DEBUG_ALLOC
 static int          swpCheckAVLTree(PMEMBLOCK pmb);
 static int          swpCheckAVLTreeFree(PAVLNODECORE pNode);
+#endif
 static unsigned     _swp_dump_subheaps_callback(PMEMBLOCK pmb, PSUBHEAPS_CALLBACK_PARAM pCb);
 static unsigned     _swp_dump_allocated_callback(PMEMBLOCK pmb, PALLOCATED_CALLBACK_PARAM pParam);
@@ -185 +185 @@
 
     unsigned long *pul;
-    unsigned long  ul;
     int            i = 0;
     PMEMBLOCKCHUNK pmcLast = NULL;
@@ -222 +221 @@
     while (pmc->achBitmap[i/8] & (0x1 << (i%8)))
         i++;
-    pmc->achBitmap[i/8] |=  0x1 << (i%8);
+    pmc->achBitmap[i/8] |=  (0x1 << (i%8));
     return &pmc->amb[i];
     #endif
@@ -251 +250 @@
         {
             kprintf(("swpReleaseMemblock: the memblock requested to be freed are allread free!\n"));
-            pmc->cFree++;
+            pmc->cFree--;
         }
         #endif
-        pmc->cFree--;
-        pmc->achBitmap[i / 8] &= pmc->achBitmap[i / 8] & ~(0x1 << i % 8);
-        #endif
+        pmc->cFree++;
+        pmc->achBitmap[i / 8] &= pmc->achBitmap[i / 8] & ~(0x1 << (i % 8));
     }
     else
         kprintf(("swpReleaseMemblock: hmm pmb is not found within any pmc.\n"));
+    #endif
 }
 
@@ -368 +367 @@
     PMEMBLOCK   pmbRightParent;
     PMEMBLOCK   pmbLeft;
-    PMEMBLOCK   pmbTmp;
 
     pha->cbFree += pmb->u2.cbSize;
@@ -753 +751 @@
                     }
                 #endif
-                #ifdef RING3
-                    fInited = TRUE;
+                #ifndef RING0
+                    fSwpInited = TRUE;
                 #endif
 
@@ -920 +918 @@
                 if (pvRet != NULL)
                 {
-                    memcpy(pvRet, pv, pmb->u2.cbSize);
+                    memcpy(pvRet, pv, pmb->u2.cbSize-CB_SIGNATURES);
                     sfree(pv);
                 }
@@ -1005 +1003 @@
 int _swp_validptr(void *pv)
 {
-    PHEAPANCHOR pha;
     PMEMBLOCK   pmb;
 
@@ -1029 +1026 @@
 int _swp_validptr2(void *pv, unsigned cbSize)
 {
-    PHEAPANCHOR pha;
     PMEMBLOCK   pmb;
 
@@ -1090 +1086 @@
         AVLENUMDATA FreeEnumData;
         AVLENUMDATA UsedEnumData;
-        PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreFree, &FreeEnumData, TRUE);
-        PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(&FreeEnumData);
-        PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreUsed, &UsedEnumData, TRUE);
-        PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(&UsedEnumData);
+        PMEMBLOCK pmbFree = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreFree,
+                                                        (PAVLENUMDATA)SSToDS(&FreeEnumData), TRUE);
+        PMEMBLOCK pmbFreeNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&FreeEnumData));
+        PMEMBLOCK pmbUsed = (PMEMBLOCK)AVLBeginEnumTree(&pha->pcoreUsed,
+                                                        (PAVLENUMDATA)SSToDS(&UsedEnumData), TRUE);
+        PMEMBLOCK pmbUsedNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&UsedEnumData));
         PMEMBLOCK pmbLast = NULL;
         unsigned  cbFree = 0;
@@ -1204 +1202 @@
                 pmbLast = pmbUsed;
                 pmbUsed = pmbUsedNext;
-                pmbUsedNext = (PMEMBLOCK)AVLGetNextNode(&UsedEnumData);
+                pmbUsedNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&UsedEnumData));
             }
             else
@@ -1244 +1242 @@
                 pmbLast = pmbFree;
                 pmbFree = pmbFreeNext;
-                pmbFreeNext = (PMEMBLOCK)AVLGetNextNode(&FreeEnumData);
+                pmbFreeNext = (PMEMBLOCK)AVLGetNextNode((PAVLENUMDATA)SSToDS(&FreeEnumData));
             }
         }
@@ -1305 +1303 @@
 }
 
-
+#ifdef DEBUG_ALLOC
 /**
  * Check the integrity of the a Free/Used AVL tree where Key == node pointer.
@@ -1316 +1314 @@
     {
         kprintf(("swpCheckAVLTree: Invalid Key!\n"));
+        Int3();
+        return -1;
+    }
+    if (pmb->u1.uData % ALIGNMENT != 0)
+    {
+        kprintf(("swpCheckAVLTree: Data is not correctly aligned, uData=0x%08x\n", pmb->u1.uData));
         Int3();
         return -1;
@@ -1399 +1403 @@
     return 0;
 }
+#endif
 
 
@@ -1406 +1411 @@
 void _swp_heapmin(void)
 {
+    PMEMBLOCKCHUNK pmcLast;
+    PMEMBLOCKCHUNK pmc;
     PHEAPANCHOR pha = phaLast;
 
@@ -1438 +1445 @@
             pha = pha->pPrev;
     }
+
+    pmcLast = NULL;
+    pmc = pmcFirst;
+    while (pmc != NULL)
+    {
+        #ifdef DEBUG_ALLOC
+        if (pmc->cFree > MEMBLOCKS_PER_CHUNK)
+        {
+            kprintf(("_swp_heapmin: internal heap error - pmc->cFree(%d) > MEMBLOCKS_PER_CHUNK(%d)\n",
+                     pmc->cFree, MEMBLOCKS_PER_CHUNK));
+        }
+        #endif
+        if (pmc->cFree == MEMBLOCKS_PER_CHUNK && pmcLast != NULL)
+        {
+            pmcLast->pNext = pmc->pNext;
+            rfree(pmc);
+            pmc = pmcLast->pNext;
+        }
+        else
+        {
+            pmcLast = pmc;
+            pmc = pmc->pNext;
+        }
+    }
 }
 
@@ -1466 +1497 @@
     while (pha != NULL)
     {
-        PMEMBLOCK pmb;
-        SUBHEAPS_CALLBACK_PARAM FreeParam = {0};
-        SUBHEAPS_CALLBACK_PARAM UsedParam = {0};
+        SUBHEAPS_CALLBACK_PARAM FreeParam = {0, 0};
+        SUBHEAPS_CALLBACK_PARAM UsedParam = {0, 0};
 
         AVLDoWithAll(&pha->pcoreUsed, 1,
-                     (PAVLCALLBACK)_swp_dump_subheaps_callback, &UsedParam);
+                     (PAVLCALLBACK)_swp_dump_subheaps_callback, SSToDS(&UsedParam));
         AVLDoWithAll(&pha->pcoreFree, 1,
-                     (PAVLCALLBACK)_swp_dump_subheaps_callback, &FreeParam);
+                     (PAVLCALLBACK)_swp_dump_subheaps_callback, SSToDS(&FreeParam));
 
         kprintf(("HeapAnchor %2d addr=0x%08x cbSize=%6d cbFree=%6d cbUsed=%6d cUsed=%4d cFree=%d\n",
@@ -1515 +1545 @@
 {
     PHEAPANCHOR pha;
-    ALLOCATED_CALLBACK_PARAM Param = {0};
+    ALLOCATED_CALLBACK_PARAM Param = {cb, 0, 0};
 
     kprintf(("----------------------------\n"
@@ -1526 +1556 @@
         /* iterate thru tree using callback */
         AVLDoWithAll((PPAVLNODECORE)&pha->pcoreUsed, TRUE,
-                     (PAVLCALLBACK)_swp_dump_allocated_callback, &Param);
+                     (PAVLCALLBACK)_swp_dump_allocated_callback, SSToDS(&Param));
 
         /* next */