Index: trunk/src/win32k/misc/heaptest.c
===================================================================
--- trunk/src/win32k/misc/heaptest.c	(revision 2507)
+++ trunk/src/win32k/misc/heaptest.c	(revision 2508)
@@ -1,3 +1,3 @@
-/* $Id: heaptest.c,v 1.3 2000-01-24 01:45:20 bird Exp $
+/* $Id: heaptest.c,v 1.4 2000-01-24 03:05:13 bird Exp $
  *
  * Test of resident and swappable heaps.
@@ -47,6 +47,7 @@
     int           fResRandom = 0;
     int           fSwpTests = 1;
-    int           fSwpSimple = 1;
+    int           fSwpSimple = 0;
     int           fSwpRandom = 1;
+    enum   {malloc,realloc, free, unknown} enmLast = unknown;
 
     /*
@@ -90,4 +91,5 @@
                     acb[i] += 1024*260;
                 apv[i] = rmalloc(acb[i]);
+                enmLast = malloc;
                 if (apv[i] == NULL)
                 {
@@ -112,4 +114,5 @@
                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
                 rfree(apv[i]);
+                enmLast = free;
             }
 
@@ -168,4 +171,5 @@
                             acb[j] += 1024*256;
                         apv[j] = rmalloc(acb[j]);
+                        enmLast = malloc;
                         if (apv[j] == NULL)
                         {
@@ -224,4 +228,5 @@
                             */
                             pv = rrealloc(apv[j], cb);
+                            enmLast = realloc;
                             if (pv == NULL)
                             {
@@ -235,4 +240,5 @@
                         {   /* free */
                             rfree(apv[j]);
+                            enmLast = free;
                             apv[j] = NULL;
                             cAllocations--;
@@ -286,4 +292,5 @@
                     acb[i] += 1024*260;
                 apv[i] = smalloc(acb[i]);
+                enmLast = malloc;
                 if (apv[i] == NULL)
                 {
@@ -308,4 +315,5 @@
                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
                 sfree(apv[i]);
+                enmLast = free;
             }
 
@@ -364,4 +372,5 @@
                             acb[j] += 1024*256;
                         apv[j] = smalloc(acb[j]);
+                        enmLast = malloc;
                         if (apv[j] == NULL)
                         {
@@ -420,4 +429,5 @@
                             */
                             pv = srealloc(apv[j], cb);
+                            enmLast = realloc;
                             if (pv == NULL)
                             {
@@ -431,4 +441,5 @@
                         {   /* free */
                             sfree(apv[j]);
+                            enmLast = free;
                             apv[j] = NULL;
                             cAllocations--;
Index: trunk/src/win32k/misc/rmalloc_avl.c
===================================================================
--- trunk/src/win32k/misc/rmalloc_avl.c	(revision 2507)
+++ trunk/src/win32k/misc/rmalloc_avl.c	(revision 2508)
@@ -1,3 +1,3 @@
-/* $Id: rmalloc_avl.c,v 1.3 2000-01-24 01:45:20 bird Exp $
+/* $Id: rmalloc_avl.c,v 1.4 2000-01-24 03:05:14 bird Exp $
  *
  * Resident Heap - AVL.
@@ -121,5 +121,5 @@
 ******************************************************************************/
 static PHEAPANCHOR  phaFirst;           /* Pointer to the first anchor block.*/
-static PHEAPANCHOR  phaLast;            /* Pointer to the first anchor block.*/
+static PHEAPANCHOR  phaLast;            /* Pointer to the last anchor block.*/
 static unsigned     cbResHeapMax;       /* Maximum amount of memory used by the heap. */
 
Index: trunk/src/win32k/misc/smalloc_avl.c
===================================================================
--- trunk/src/win32k/misc/smalloc_avl.c	(revision 2507)
+++ trunk/src/win32k/misc/smalloc_avl.c	(revision 2508)
@@ -1,3 +1,3 @@
-/* $Id: smalloc_avl.c,v 1.1 2000-01-24 01:45:21 bird Exp $
+/* $Id: smalloc_avl.c,v 1.2 2000-01-24 03:05:14 bird Exp $
  *
  * Swappable Heap - AVL.
@@ -40,6 +40,7 @@
                                 ((PMEMBLOCK)((unsigned)(a) - (unsigned)(&((PMEMBLOCK)0)->u2.coreFree)))
 
-#define BLOCKSIZE (1024*256)            /* 256KB */
-#define ALIGNMENT (sizeof(unsigned))
+#define BLOCKSIZE               (1024*256)            /* 256KB */
+#define ALIGNMENT               (sizeof(unsigned))
+#define MEMBLOCKS_PER_CHUNK     (256)
 
 
@@ -76,5 +77,5 @@
 *   Structures and Typedefs                                                    *
 *******************************************************************************/
-#pragma pack(1)
+#pragma pack(4)
 typedef struct _MEMBLOCK /* mb */
 {
@@ -93,5 +94,5 @@
     struct _MEMBLOCK   *pmbNext;        /* Pointer to list of blocks with the same size */
 } MEMBLOCK, *PMEMBLOCK;
-#pragma pack()
+
 
 typedef struct _HeapAnchor /* ha */
@@ -113,4 +114,13 @@
 
 
+typedef struct _MemblockChunk /* mc */
+{
+    struct _MemblockChunk * pNext;      /* Pointer to next chunk */
+    unsigned            cFree;          /* Number of free memblocks */
+    char                achBitmap[MEMBLOCKS_PER_CHUNK/8]; /* Used(1)/Free(0) bitmap */
+    MEMBLOCK            amb[MEMBLOCKS_PER_CHUNK]; /* Array of memblocks */
+} MEMBLOCKCHUNK, *PMEMBLOCKCHUNK;
+
+
 typedef struct _SubHeaps_Callback_param
 {
@@ -131,6 +141,7 @@
 ******************************************************************************/
 static PHEAPANCHOR  phaFirst;           /* Pointer to the first anchor block.*/
-static PHEAPANCHOR  phaLast;            /* Pointer to the first anchor block.*/
+static PHEAPANCHOR  phaLast;            /* Pointer to the last anchor block.*/
 static unsigned     cbSwpHeapMax;       /* Maximum amount of memory used by the heap. */
+static PMEMBLOCKCHUNK pmcFirst;          /* Pointer to the first memblock chunk. */
 
 #ifndef RING0
@@ -165,8 +176,53 @@
 _Inline PMEMBLOCK swpAllocateMemblock(void)
 {
+    #if 0
     PMEMBLOCK pmb = (PMEMBLOCK)rmalloc(sizeof(MEMBLOCK));
     if (pmb != NULL)
         memset(pmb, 0, sizeof(*pmb));
     return pmb;
+
+    #else
+
+    unsigned long *pul;
+    unsigned long  ul;
+    int            i = 0;
+    PMEMBLOCKCHUNK pmcLast = NULL;
+    PMEMBLOCKCHUNK pmc = pmcFirst;
+    while (pmc != NULL && pmc->cFree == 0)
+    {
+        pmcLast =  pmc;
+        pmc = pmc->pNext;
+    }
+
+    /* allocate another chunk? */
+    if (pmc == NULL)
+    {
+        pmc = rmalloc(sizeof(*pmc));
+        if (pmc != NULL)
+        {
+            memset(pmc, 0, sizeof(*pmc));
+            pmc->cFree = MEMBLOCKS_PER_CHUNK;
+            if (pmcLast == NULL)
+                pmcFirst = pmc;
+            else
+                pmcLast->pNext = pmc;
+        }
+        else
+        {
+            kprintf(("swpAllocateMemblock: rmalloc failed\n"));
+            return NULL;
+        }
+    }
+
+    /* find first free */
+    pmc->cFree--;
+    pul = (unsigned long*)pmc->achBitmap;
+    while (*pul == 0xFFFFFFFF)
+        pul++, i += 8*4;
+    while (pmc->achBitmap[i/8] & (0x1 << (i%8)))
+        i++;
+    pmc->achBitmap[i/8] |=  0x1 << (i%8);
+    return &pmc->amb[i];
+    #endif
 }
 
@@ -179,6 +235,29 @@
 _Inline void swpReleaseMemblock(PMEMBLOCK pmb)
 {
+    #if 0
     if (pmb != NULL)
         rfree(pmb);
+    #else
+    int             i;
+    PMEMBLOCKCHUNK  pmc = pmcFirst;
+    while (pmc != NULL && !((void*)pmc < (void*)pmb && (unsigned)pmc + sizeof(*pmc) > (unsigned)pmb))
+        pmc = pmc->pNext;
+
+    if (pmc != NULL)
+    {
+        i = ((unsigned)pmb - (unsigned)pmc->amb) / sizeof(pmc->amb[0]);
+        #ifdef DEBUG
+        if ((pmc->achBitmap[i / 8] & (1 << (i % 8))) == 0)
+        {
+            kprintf(("swpReleaseMemblock: the memblock requested to be freed are allread free!\n"));
+            pmc->cFree++;
+        }
+        #endif
+        pmc->cFree--;
+        pmc->achBitmap[i / 8] &= pmc->achBitmap[i / 8] & ~(0x1 << i % 8);
+        #endif
+    }
+    else
+        kprintf(("swpReleaseMemblock: hmm pmb is not found within any pmc.\n"));
 }
 
@@ -626,8 +705,8 @@
 int swpHeapInit(unsigned cbSizeInit, unsigned cbSizeMax)
 {
-    unsigned  cbSize = MAX(BLOCKSIZE, cbSizeInit);
-    PMEMBLOCK pmbFree = swpAllocateMemblock();
+    PMEMBLOCK pmbFree;
     cbSwpHeapMax = cbSizeMax;
-
+    pmcFirst = NULL;
+    pmbFree = swpAllocateMemblock();
     if (pmbFree != NULL)
     {
@@ -635,4 +714,5 @@
         if (phaFirst != NULL)
         {
+            unsigned  cbSize = MAX(BLOCKSIZE, cbSizeInit);
             memset(phaFirst, 0, sizeof(*phaFirst));
             #ifdef RING0
@@ -648,9 +728,9 @@
                 phaFirst->ulSignature = HEAPANCHOR_SIGNATURE;
                 #endif
-                phaFirst->cbSize = cbSizeInit;
+                phaFirst->cbSize = cbSize;
 
                 /* free memblock */
                 pmbFree->u1.uData = (unsigned)phaFirst->pvBlock;
-                pmbFree->u2.cbSize = cbSizeInit;
+                pmbFree->u2.cbSize = cbSize;
                 #ifdef DEBUG_ALLOC
                 pmbFree->u1.puData[0] = SIGNATURE_START;
@@ -694,5 +774,5 @@
     }
     else
-        kprintf(("swpHeapInit: swpAllocateMemblock failed\n"));
+        kprintf(("swpHeapInit: swpAllocateMemblock failed.\n"));
     return -1;
 }
@@ -752,5 +832,5 @@
     }
     #endif
-    pmb = swpFindUsedBlock(SSToDS(&pha), pv));
+    pmb = swpFindUsedBlock(SSToDS(&pha), pv);
     if (pmb != NULL)
     {
@@ -771,4 +851,5 @@
                     pmb->u2.cbSize = cbNew;
                     #ifdef DEBUG_ALLOC
+                    pmbNew->u1.puData[-1] = SIGNATURE_END;
                     pmbNew->u1.puData[0] = SIGNATURE_START;
                     pmbNew->u1.puData[(pmbNew->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
@@ -803,5 +884,5 @@
                 pvRet = pv;
                 /* split the free block? */
-                if (pmbRight->u2.cbSize + pmb->u2.cbSize + CB_SIGNATURES > cbNew)
+                if (pmbRight->u2.cbSize + pmb->u2.cbSize - CB_SIGNATURES > cbNew)
                 {
                     pha->cbFree -= pmbRight->u2.cbSize;
@@ -810,4 +891,5 @@
                     pmbRight->u2.cbSize = pmbRight->u2.cbSize + pmb->u2.cbSize - cbNew;
                     #ifdef DEBUG_ALLOC
+                    pmbRight->u1.puData[-1] = SIGNATURE_END;
                     pmbRight->u1.puData[0] = SIGNATURE_START;
                     pmbRight->u1.puData[(pmbRight->u2.cbSize / sizeof(unsigned)) - 1] = SIGNATURE_END;
@@ -911,5 +993,5 @@
     #endif
 
-    pmb = swpFindUsedBlock(SSToDS(&pha), pv));
+    pmb = swpFindUsedBlock(SSToDS(&pha), pv);
     return pmb != NULL ? pmb->u2.cbSize - CB_SIGNATURES : 0;
 }
@@ -1114,7 +1196,7 @@
                     return FALSE;
                 }
-                if (pmbUsed->u1.puData[(pmbUsed->u2.cbSize/sizeof(unsigned)) - 1] != SIGNATURE_END)
-                {
-                    kprintf(("_swp_heap_check: invalid start signature on used block, pv=0x%08x\n", pmbUsed->u1.pvData));
+                if (pmbUsed->u1.puData[(pmbUsed->u2.cbSize / sizeof(unsigned)) - 1] != SIGNATURE_END)
+                {
+                    kprintf(("_swp_heap_check: invalid end signature on used block, pv=0x%08x\n", pmbUsed->u1.pvData));
                     Int3();
                     return FALSE;
@@ -1154,7 +1236,7 @@
                     return FALSE;
                 }
-                if (pmbFree->u1.puData[(pmbFree->u2.cbSize/sizeof(unsigned)) - 1] != SIGNATURE_END)
-                {
-                    kprintf(("_swp_heap_check: invalid start signature on free block, pv=0x%08x\n", pmbUsed->u1.pvData));
+                if (pmbFree->u1.puData[(pmbFree->u2.cbSize / sizeof(unsigned)) - 1] != SIGNATURE_END)
+                {
+                    kprintf(("_swp_heap_check: invalid end signature on free block, pv=0x%08x\n", pmbUsed->u1.pvData));
                     Int3();
                     return FALSE;
