Changeset 2508

Timestamp:

Jan 24, 2000, 4:05:14 AM (25 years ago)

Author:

bird

Message:

Corrections. Still some bugs in smalloc_avl.c.

Location:

trunk/src/win32k/misc

Files:

• heaptest.c (modified) (12 diffs)
• rmalloc_avl.c (modified) (2 diffs)
• smalloc_avl.c (modified) (19 diffs)

trunk/src/win32k/misc/heaptest.c ¶

@@ -1 @@
-/* $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 +47 @@
     int           fResRandom = 0;
     int           fSwpTests = 1;
-    int           fSwpSimple = 1;
+    int           fSwpSimple = 0;
     int           fSwpRandom = 1;
+    enum   {malloc,realloc, free, unknown} enmLast = unknown;
 
     /*
@@ -90 +91 @@
                     acb[i] += 1024*260;
                 apv[i] = rmalloc(acb[i]);
+                enmLast = malloc;
                 if (apv[i] == NULL)
                 {
@@ -112 +114 @@
                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
                 rfree(apv[i]);
+                enmLast = free;
             }
 
@@ -168 +171 @@
                             acb[j] += 1024*256;
                         apv[j] = rmalloc(acb[j]);
+                        enmLast = malloc;
                         if (apv[j] == NULL)
                         {
@@ -224 +228 @@
                             */
                             pv = rrealloc(apv[j], cb);
+                            enmLast = realloc;
                             if (pv == NULL)
                             {
@@ -235 +240 @@
                         {   /* free */
                             rfree(apv[j]);
+                            enmLast = free;
                             apv[j] = NULL;
                             cAllocations--;
@@ -286 +292 @@
                     acb[i] += 1024*260;
                 apv[i] = smalloc(acb[i]);
+                enmLast = malloc;
                 if (apv[i] == NULL)
                 {
@@ -308 +315 @@
                     printf("size of avp[%d] (%d) != acb[%d] (%d)\n", i, cb, i, acb[i]);
                 sfree(apv[i]);
+                enmLast = free;
             }
 
@@ -364 +372 @@
                             acb[j] += 1024*256;
                         apv[j] = smalloc(acb[j]);
+                        enmLast = malloc;
                         if (apv[j] == NULL)
                         {
@@ -420 +429 @@
                             */
                             pv = srealloc(apv[j], cb);
+                            enmLast = realloc;
                             if (pv == NULL)
                             {
@@ -431 +441 @@
                         {   /* free */
                             sfree(apv[j]);
+                            enmLast = free;
                             apv[j] = NULL;
                             cAllocations--;

trunk/src/win32k/misc/rmalloc_avl.c ¶

@@ -1 @@
-/* $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 +121 @@
 ******************************************************************************/
 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. */
 

trunk/src/win32k/misc/smalloc_avl.c ¶

@@ -1 @@
-/* $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 +40 @@
                                 ((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 +77 @@
 *   Structures and Typedefs                                                    *
 *******************************************************************************/
-#pragma pack(1)
+#pragma pack(4)
 typedef struct _MEMBLOCK /* mb */
 {
@@ -93 +94 @@
     struct _MEMBLOCK   *pmbNext;        /* Pointer to list of blocks with the same size */
 } MEMBLOCK, *PMEMBLOCK;
-#pragma pack()
+
 
 typedef struct _HeapAnchor /* ha */
@@ -113 +114 @@
 
 
+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 +141 @@
 ******************************************************************************/
 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 +176 @@
 _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 +235 @@
 _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 +705 @@
 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 +714 @@
         if (phaFirst != NULL)
         {
+            unsigned  cbSize = MAX(BLOCKSIZE, cbSizeInit);
             memset(phaFirst, 0, sizeof(*phaFirst));
             #ifdef RING0
@@ -648 +728 @@
                 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 +774 @@
     }
     else
-        kprintf(("swpHeapInit: swpAllocateMemblock failed\n"));
+        kprintf(("swpHeapInit: swpAllocateMemblock failed.\n"));
     return -1;
 }
@@ -752 +832 @@
     }
     #endif
-    pmb = swpFindUsedBlock(SSToDS(&pha), pv));
+    pmb = swpFindUsedBlock(SSToDS(&pha), pv);
     if (pmb != NULL)
     {
@@ -771 +851 @@
                     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 +884 @@
                 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 +891 @@
                     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 +993 @@
     #endif
 
-    pmb = swpFindUsedBlock(SSToDS(&pha), pv));
+    pmb = swpFindUsedBlock(SSToDS(&pha), pv);
     return pmb != NULL ? pmb->u2.cbSize - CB_SIGNATURES : 0;
 }
@@ -1114 +1196 @@
                     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 +1236 @@
                     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;