Ignore:
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.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/win32k/misc/malloc.c

    r1678 r2511  
    1 /* $Id: malloc.c,v 1.5 1999-11-10 01:45:36 bird Exp $
     1/* $Id: malloc.c,v 1.6 2000-01-24 18:19:00 bird Exp $
    22 *
    3  * Heap.
     3 * Common Heap - this forwards to the swappable heap!
    44 *
    55 * Note: This heap does very little checking on input.
    66 *       Use with care! We're running at Ring-0!
    77 *
    8  * Copyright (c) 1999 knut st. osmundsen
     8 * Copyright (c) 1999-2000 knut st. osmundsen
    99 *
    1010 * Project Odin Software License can be found in LICENSE.TXT
    1111 *
    1212 */
    13 
    14 #define static
    15 /******************************************************************************
    16 *  Defined macros and constants
    17 ******************************************************************************/
    18 #ifdef DEBUG
    19     #define DEBUG_ALLOC
    20 #endif
    21 
    22 #define SIGNATURE 0xBEEFFEEB
    23 /*#define CB_HDR (sizeof(MEMBLOCK) - 1) /* size of MEMBLOCK header (in bytes) */
    24 #define CB_HDR (int)&(((PMEMBLOCK)0)->achUserData[0])
    25 #define PNEXT_BLOCK(a) ((PMEMBLOCK)((unsigned)(a) + CB_HDR + (a)->cbSize))
    26 
    27 #define INCL_DOS
    28 #define INCL_DOSERRORS
    29 #ifdef RING0
    30     #define INCL_NOAPI
    31 #else
    32     #define INCL_DOSMEMMGR
    33 #endif
    34 
     13/*******************************************************************************
     14*   Defined Constants And Macros                                               *
     15*******************************************************************************/
     16#define INCL_NOAPI
    3517
    3618/******************************************************************************
    … …  
    3820******************************************************************************/
    3921#include <os2.h>
    40 #ifdef RING0
    41     #include "dev32hlp.h"
    42     #include "asmutils.h"
    43 #else
    44     #include <builtin.h>
    45     #define Int3() __interrupt(3)
    46 #endif
    47 #include "log.h"
    48 #include "malloc.h"
    49 #include <memory.h>
     22#include "smalloc.h"
     23#include "rmalloc.h"
     24#include "options.h"
    5025
    51 
    52 /******************************************************************************
    53 *  Structs and Typedefs
    54 ******************************************************************************/
    55 #pragma pack(1)
    56 typedef struct _MEMBLOCK /* MB */
    57 {
    58 #ifdef DEBUG_ALLOC
    59    unsigned long     ulSignature;   /* should be SIGNATURE (0xBEEFFEEB) */
    60 #endif
    61    unsigned          cbSize;        /* size of user space (achBlock)*/
    62    struct _MEMBLOCK *pNext;
    63    unsigned char     achUserData[1];
    64 } MEMBLOCK, *PMEMBLOCK;
    65 #pragma pack()
    6626
    6727/******************************************************************************
    6828*  Global data
    6929******************************************************************************/
    70 /*#pragma info(nogen, nouni, noext)*/
    71 static PMEMBLOCK   pUsed;         /* pointer to the used memblock chain. */
    72 static PMEMBLOCK   pFree;         /* pointer to the free memblock chain. */
    73 static unsigned    cbFree;        /* bytes of free user memory in the heap.*/
    74 unsigned           _uHeapMinPtr;  /* heap pointers are greater or equal to this.*/
    75 unsigned           _uHeapMaxPtr;  /* heap pointers are less than this. */
    7630#ifndef RING0
    7731    char           fInited;       /* init flag */
    7832#endif
    7933
    80 /******************************************************************************
    81 *  Internal functions
    82 ******************************************************************************/
    83 static void         insertUsed(PMEMBLOCK pMemblock);
    84 static void         insertFree(PMEMBLOCK pMemblock);
    85 static PMEMBLOCK    getFreeMemblock(unsigned cbUserSize);
    86 static PMEMBLOCK    findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin);
    8734
    8835
    8936/**
    90  * Inserts a memblock into the used chain
    91  * @param    pMemblock  Pointer to memblock which is to inserted.
    92  * @remark   Sorts on address.
     37 * Initiate the heap "subsystems" - both the resident and the swappable heaps.
     38 * @returns   0 on success, not 0 on error.
     39 * @param     cbResInit  Resident heap initial size.
     40 * @param     cbResMax   Resident heap maximum size.
     41 * @param     cbSwpInit  Swappable heap initial size.
     42 * @param     cbSwpMax   Swappable heap maximum size.
    9343 */
    94 static void insertUsed(PMEMBLOCK pMemblock)
     44int heapInit(unsigned cbResInit, unsigned cbResMax,
     45             unsigned cbSwpInit, unsigned cbSwpMax)
    9546{
    96     if (pUsed == NULL || pUsed > pMemblock)
    97     {
    98         pMemblock->pNext = pUsed;
    99         pUsed = pMemblock;
    100     }
    101     else
    102     {
    103         PMEMBLOCK pMb = pUsed;
    104         while (pMb->pNext != NULL && pMb->pNext < pMemblock)
    105             pMb = pMb->pNext;
     47    int rc;
    10648
    107         pMemblock->pNext = pMb->pNext;
    108         pMb->pNext= pMemblock;
    109     }
    110 }
    111 
    112 
    113 /**
    114  * Inserts a memblock into the free chain.
    115  * Merges blocks adjecent blocks.
    116  * @param    pMemblock  Pointer to memblock to insert into the free list.
    117  * @remark   Sorts on address.
    118  */
    119 static void insertFree(PMEMBLOCK pMemblock)
    120 {
    121     cbFree += pMemblock->cbSize;
    122     if (pMemblock < pFree || pFree == NULL)
    123     {
    124         /* test for merge with 2nd block */
    125         if (pFree != NULL && PNEXT_BLOCK(pMemblock) == pFree)
    126         {
    127             cbFree += pMemblock->cbSize + CB_HDR;
    128             pFree->cbSize += CB_HDR;
    129             #ifdef DEBUG_ALLOC
    130                 pMemblock->ulSignature = 0xF0EEEE0F;
    131             #endif
    132         }
    133         else
    134         {
    135            pMemblock->pNext = pFree;
    136            pFree = pMemblock;
    137 
    138         }
    139     }
    140     else
    141     {
    142         PMEMBLOCK pMb = pFree;
    143         while (pMb->pNext != NULL && pMb->pNext < pMemblock)
    144             pMb = pMb->pNext;
    145 
    146         /* test for merge with left block */
    147         if (PNEXT_BLOCK(pMb) == pMemblock)
    148         {
    149             pMb->cbSize += CB_HDR + pMemblock->cbSize;
    150             cbFree += CB_HDR;
    151             #ifdef DEBUG_ALLOC
    152                 pMemblock->ulSignature = 0xF0EEEE0F;
    153             #endif
    154             pMemblock = pMb;
    155         }
    156         else
    157         {
    158             pMemblock->pNext = pMb->pNext;
    159             pMb->pNext = pMemblock;
    160         }
    161 
    162         /* test for merge with right block */
    163         if (PNEXT_BLOCK(pMemblock) == pMemblock->pNext && pMemblock->pNext != NULL)
    164         {
    165             pMemblock->cbSize += CB_HDR + pMemblock->pNext->cbSize;
    166             cbFree += CB_HDR;
    167             #ifdef DEBUG_ALLOC
    168                 pMemblock->pNext->ulSignature = 0xF0EEEE0F;
    169             #endif
    170             pMemblock->pNext = pMemblock->pNext->pNext;
    171         }
    172     }
    173 }
    174 
    175 
    176 /**
    177  * Finds a free block at the requested size.
    178  * @returns  Pointer to block (not in free list any longer).
    179  * @param    cbUserSize  Bytes the user have requested.
    180  * @sketch   cbUserSize is aligned to nearest 4 bytes.
    181  *
    182  *
    183  */
    184 static PMEMBLOCK getFreeMemblock(unsigned cbUserSize)
    185 {
    186     PMEMBLOCK pBestFit     = NULL;
    187     PMEMBLOCK pBestFitPrev = NULL;
    188     PMEMBLOCK pCur  = pFree;
    189     PMEMBLOCK pPrev = NULL;
    190 
    191     cbUserSize = (cbUserSize + 3) & ~3;
    192 
    193     /* search for block */
    194     while (pCur != NULL)
    195     {
    196         /* check for perfect match first */
    197         if (pCur->cbSize == cbUserSize)
    198             break;
    199             /* TODO: The following test may need to be adjusted later. */
    200         else if (pCur->cbSize >= cbUserSize
    201                 && (pBestFit == NULL || pCur->cbSize < pBestFit->cbSize)
    202                 )
    203         {
    204             pBestFit = pCur;
    205             pBestFitPrev = pPrev;
    206         }
    207 
    208         /* next */
    209         pPrev = pCur;
    210         pCur = pCur->pNext;
    211     }
    212 
    213     /* link out block */
    214     if (pCur != NULL)
    215     {   /* prefect match */
    216         if (pPrev != NULL)
    217             pPrev->pNext = pCur->pNext;
    218         else
    219             pFree = pCur->pNext;
    220 
    221         cbFree -= cbUserSize;
    222     }
    223     else if (pBestFit != NULL)
    224     {   /* best fit */
    225         /* two cases 1) split block. 2) block is too small to be splitted. */
    226         if (pBestFit->cbSize > cbUserSize + CB_HDR)
    227         {
    228             pCur = (PMEMBLOCK)((unsigned)pBestFit + pBestFit->cbSize - cbUserSize);
    229             #ifdef DEBUG_ALLOC
    230                 pCur->ulSignature = SIGNATURE;
    231             #endif
    232             pCur->cbSize = cbUserSize;
    233             pBestFit->cbSize -= cbUserSize + CB_HDR;
    234 
    235             cbFree -= cbUserSize + CB_HDR;
    236         }
    237         else
    238         {
    239             if (pBestFitPrev != NULL)
    240                 pBestFitPrev->pNext = pBestFit->pNext;
    241             else
    242                 pFree = pBestFit->pNext;
    243             pCur = pBestFit;
    244 
    245             cbFree -= pCur->cbSize;
    246         }
    247     }
    248 
    249     return pCur;
    250 }
    251 
    252 
    253 /**
    254  * Finds a memory block starting the search at pMemblock.
    255  * @returns   Pointer to memblock if found.
    256  * @param     pMemblock  Start node.
    257  * @param     pvUser     User pointer to find the block to.
    258  * @param     fWithin    When this flag is set, the pointer may point anywhere within the block.
    259  */
    260 static PMEMBLOCK    findBlock(PMEMBLOCK pMemblock, void *pvUser, int fWithin)
    261 {
    262     if (pvUser != NULL && pMemblock != NULL)
    263     {
    264         if (fWithin)
    265             while (pMemblock != NULL &&
    266                    !(pvUser >= (void*)pMemblock && pvUser < (void*)PNEXT_BLOCK(pMemblock))
    267                    )
    268                 pMemblock = pMemblock->pNext;
    269         else
    270         {
    271             pvUser = (void*)((unsigned)pvUser - CB_HDR);
    272             while (pMemblock != NULL && pvUser != (void*)pMemblock)
    273                 pMemblock = pMemblock->pNext;
    274         }
    275     }
    276     else
    277         pMemblock = NULL;
    278 
    279     return pMemblock;
    280 }
    281 
    282 
    283 /**
    284  * Initiate the heap "subsystem".
    285  * @returns   0 on success, not 0 on error.
    286  * @param     cbSize  Heapsize in bytes.
    287  */
    288 int heapInit(unsigned cbSize)
    289 {
    290     pUsed = NULL;
    291 
    292     #ifdef RING0
    293         pFree = D32Hlp_VMAlloc(VMDHA_SWAP, cbSize, ~0UL);
    294     #else
    295         if (DosAllocMem((void*)&pFree, cbSize, PAG_COMMIT | PAG_READ | PAG_WRITE) != 0)
    296             pFree = NULL;
    297     #endif
    298     if (pFree == NULL)
    299     {
    300         kprintf(("unable to allocate heap memory.\n"));
    301         Int3();
    302         return -1;
    303     }
    304 
    305     #ifdef DEBUG_ALLOC
    306         pFree->ulSignature = SIGNATURE;
    307     #endif
    308     pFree->cbSize = cbSize - CB_HDR;
    309     pFree->pNext = NULL;
    310     cbFree = pFree->cbSize;
    311 
    312     _uHeapMinPtr = (unsigned)pFree + CB_HDR;
    313     _uHeapMaxPtr = (unsigned)pFree + cbSize;
    314 
    315     #ifdef DEBUG_ALLOC
    316         if (!_heap_check())
    317         {
    318             /* error! */
    319             kprintf(("%s: _heap_check failed!\n", "heapInit"));
    320             Int3();
    321             return -2;
    322         }
    323     #endif
     49    rc = resHeapInit(cbResInit, cbResMax);
     50    if (rc != 0)
     51        return rc;
     52    rc = swpHeapInit(cbSwpInit, cbSwpMax);
     53    if (rc != 0)
     54        return rc;
    32455    #ifdef RING3
    32556        fInited = TRUE;
    … …  
    33869void * malloc(unsigned cbSize)
    33970{
    340     void *pvRet = NULL;
    341 
    342     #ifdef DEBUG_ALLOC
    343         if (!_heap_check())
    344         {
    345             kprintf(("%s: _heap_check failed!\n", "malloc"));
    346             return NULL;
    347         }
    348     #endif
    349 
    350     if (cbSize != 0)
    351     {
    352         PMEMBLOCK pMemblock = getFreeMemblock(cbSize);
    353         if (pMemblock != NULL)
    354         {
    355             insertUsed(pMemblock);
    356             pvRet = &pMemblock->achUserData[0];
    357         }
    358     }
    359     else
    360     {
    361         /* error! */
    362         kprintf(("%s: error cbSize = 0\n", "malloc"));
    363     }
    364 
    365     return pvRet;
     71    return smalloc(cbSize);
    36672}
    36773
    … …  
    37581void *realloc(void *pv, unsigned cbNew)
    37682{
    377     PMEMBLOCK pMemblock;
    378     pMemblock = findBlock(pUsed, pv, FALSE);
    379     if (pMemblock != NULL)
    380     {
    381         void *pvRet;
    382 
    383         cbNew = (cbNew + 3) & ~3;
    384         if (cbNew <= pMemblock->cbSize)
    385         {   /* shrink block */
    386             pvRet = pv;
    387             if (cbNew + CB_HDR < pMemblock->cbSize)
    388             {   /* split block */
    389                 PMEMBLOCK pNewBlock = (PMEMBLOCK)((unsigned)pMemblock + CB_HDR + cbNew);
    390                 #ifdef DEBUG_ALLOC
    391                     pNewBlock->ulSignature = SIGNATURE;
    392                 #endif
    393                 pNewBlock->cbSize = pMemblock->cbSize - cbNew - CB_HDR;
    394                 pNewBlock->pNext = NULL;
    395                 pMemblock->cbSize = cbNew;
    396                 insertFree(pNewBlock);
    397             }
    398         }
    399         else
    400         {   /* expand block */
    401             pvRet = malloc(cbNew);
    402             if (pvRet != NULL)
    403             {
    404                 memcpy(pvRet, pv, pMemblock->cbSize);
    405                 free(pv);
    406             }
    407         }
    408         return pvRet;
    409     }
    410     return NULL;
     83    return srealloc(pv, cbNew);
    41184}
    41285
    … …  
    41891void free(void *pv)
    41992{
    420     #ifdef DEBUG_ALLOC
    421         if (!_heap_check())
    422         {
    423             kprintf(("free: _heap_check failed!\n"));
    424             return;
    425         }
    426     #endif
    427 
    428     if (pv != NULL)
    429     {
    430         PMEMBLOCK pCur  = pUsed;
    431         PMEMBLOCK pPrev = NULL;
    432         pv = (void*)((int)pv - CB_HDR);
    433 
    434         while (pCur != NULL &&
    435         #ifdef DEBUG_ALLOC /* pointer within block */
    436                !(pv >= (void*)pCur && (void*)((unsigned)pv + CB_HDR) < (void*)PNEXT_BLOCK(pCur))
    437         #else
    438                pv != (void*)pCur
    439         #endif
    440                )
    441         {
    442             pPrev = pCur;
    443             pCur = pCur->pNext;
    444         }
    445 
    446         if (pCur != NULL)
    447         {
    448             if (pv == pCur)
    449             {
    450                 if (pPrev != NULL)
    451                     pPrev->pNext = pCur->pNext;
    452                 else
    453                     pUsed = pCur->pNext;
    454 
    455                 insertFree(pCur);
    456 
    457                 #ifdef DEBUG_ALLOC
    458                     if (!_heap_check())
    459                         kprintf(("%s: _heap_check failed 3!\n", "free"));
    460                 #endif
    461             }
    462             else
    463                 kprintf(("free: pv is not pointing to start of block.\n"));
    464         }
    465         else
    466             kprintf(("free: heap block not found!\n"));
    467     }
    468     else
    469         kprintf(("free: Free received a NULL pointer!\n"));
     93    sfree(pv);
    47094}
    47195
    … …  
    477101unsigned _msize(void *pv)
    478102{
    479     PMEMBLOCK pBlock;
    480     #ifdef DEBUG_ALLOC
    481         if (!_heap_check())
    482             kprintf(("_msize: _heap_check failed!\n"));
    483     #endif
    484     pBlock = findBlock(pUsed, pv, FALSE);
    485     return pBlock != NULL ? pBlock->cbSize : 0;
     103    return _swp_msize(pv);
    486104}
    487105
    … …  
    494112int _validptr(void *pv)
    495113{
    496     PMEMBLOCK pBlock;
    497 
    498     #ifdef DEBUG_ALLOC
    499         if (!_heap_check())
    500             kprintf(("_validptr: _heap_check failed!\n"));
    501     #endif
    502 
    503     pBlock = findBlock(pUsed, pv, TRUE);
    504     return pBlock != NULL;
     114    return _swp_validptr(pv);
    505115}
    506116
    … …  
    514124int _validptr2(void *pv, unsigned cbSize)
    515125{
    516     PMEMBLOCK pBlock;
    517 
    518     #ifdef DEBUG_ALLOC
    519         if (!_heap_check())
    520             kprintf(("_validptr: _heap_check failed!\n"));
    521     #endif
    522 
    523     pBlock = findBlock(pUsed, pv, TRUE);
    524     return pBlock != NULL ? (pBlock->cbSize - ((unsigned)pv - (unsigned)pBlock - CB_HDR)) >= cbSize : FALSE;
     126    return _swp_validptr2(pv, cbSize);
    525127}
    526128
    … …  
    536138unsigned _memfree(void)
    537139{
    538     #ifdef DEBUG_ALLOC
    539         if (!_heap_check())
    540             kprintf(("_memfree: _heap_check failed!\n"));
    541     #endif
    542     return cbFree;
     140    return _swp_memfree();
    543141}
    544142
    … …  
    552150int _heap_check(void)
    553151{
    554     #ifdef DEBUG_ALLOC
    555         PMEMBLOCK pCurFree = pFree;
    556         PMEMBLOCK pCurUsed = pUsed;
    557 
    558         while (pCurFree != NULL || pCurUsed != NULL)
    559         {
    560             /** @sketch:
    561              * check signatures and for lost memory.
    562              *
    563              * three cases:
    564              *  1) pCurUsed adjecent to pCurUsed->pNext
    565              *  2) pCurUsed adjecent to pCurFree
    566              *  3) pCurFree adjecent to pCurFree->pNext
    567              *  4) pCurFree adjecent to pCurUsed
    568              *  5) pCurUsed is the last block
    569              *  6) pCurFree is the last block
    570              */
    571             #if 0
    572             if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext)       /* 1.*/
    573                 ;
    574             else if (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree)         /* 2.*/
    575                 ;
    576             else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext)  /* 3.*/
    577                 ;
    578             else if (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed)         /* 4.*/
    579                 ;
    580             else if (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL)   /* 5.*/
    581                 ;
    582             else if (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL)   /* 6.*/
    583                 ;
    584             else
    585             #else
    586             if (!( (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurUsed->pNext)    /* 1.*/
    587                 || (pCurUsed != NULL && PNEXT_BLOCK(pCurUsed) == pCurFree)           /* 2.*/
    588                 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurFree->pNext)    /* 3.*/
    589                 || (pCurFree != NULL && PNEXT_BLOCK(pCurFree) == pCurUsed)           /* 4.*/
    590                 || (pCurUsed != NULL && pCurFree == NULL && pCurUsed->pNext == NULL) /* 5.*/
    591                 || (pCurFree != NULL && pCurUsed == NULL && pCurFree->pNext == NULL) /* 6.*/
    592                  )
    593                )
    594             #endif
    595                 {
    596                 /* error hole */
    597                 kprintf(("_heap_check: internal error - memory hole!\n"));
    598                 return FALSE;
    599                 }
    600 
    601             /* check signature and advance to the next block */
    602             if (pCurUsed != NULL && (pCurFree == NULL || pCurUsed < pCurFree))
    603             {
    604                 if (pCurUsed->ulSignature != SIGNATURE)
    605                     return FALSE;
    606                 pCurUsed = pCurUsed->pNext;
    607             }
    608             else
    609             {
    610                 if (pCurFree->ulSignature != SIGNATURE)
    611                     return FALSE;
    612                 pCurFree = pCurFree->pNext;
    613             }
    614         }
    615     #endif
    616     return TRUE;
     152    return _swp_heap_check();
    617153}
    618154
    … …  
    626162int _rmem_init(void)
    627163{
    628     int rc = heapInit(0x100000);
     164    int rc = heapInit(CB_RES_INIT, CB_RES_MAX, CB_SWP_INIT, CB_SWP_MAX);
    629165    return rc;
    630166}
Note: See TracChangeset for help on using the changeset viewer.