home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / tvision / dpmi / clib / malloc.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-05-28  |  10.8 KB  |  514 lines
  1. //=====================================================================
  2. //
  3. //  malloc.cpp
  4. //
  5. //  memory allocation routines
  6. //
  7. //  These are clunky and slow, but they should work.
  8. //
  9. //  Protected Mode version
  10. //
  11. //  Copyright (c) 1994, Kevin Morgan, All rights reserved.
  12. //
  13. //=====================================================================
  14. #define PROTECT
  15.  
  16. #include <stdio.h>
  17. #include <alloc.h>
  18. #include <dos.h>
  19. #include <string.h>
  20.  
  21. #include <stdlib.h>
  22. #include <stdarg.h>
  23. #include <conio.h>
  24.  
  25. #ifdef PROTECT
  26. #define MHUGE far
  27. #define INITIAL_CHUNK_NODES 2000
  28. #include "dpmish.h"
  29. #else
  30. #define INITIAL_CHUNK_NODES 700
  31. #define MHUGE huge
  32. #endif
  33.  
  34. //#define DEBUG
  35.  
  36. #define pause()
  37.  
  38. //=====================================================================
  39. //
  40. // _heaplen
  41. //
  42. // can be pre-initialized to specify how much heap to allocate
  43. // initially.
  44. //
  45. //=====================================================================
  46. extern unsigned long _protheaplen;
  47.  
  48. class MemoryChunk {
  49.     public:
  50.         unsigned long ptr;
  51.         unsigned long sz;
  52.         MemoryChunk *next;
  53.         MemoryChunk *prev;
  54.         int inuse;
  55. };
  56.  
  57. MemoryChunk *realMem = 0;
  58. MemoryChunk *rootMem = 0;
  59. MemoryChunk *freeNodes=0;        // unused memory nodes
  60. unsigned long memoryLeft = 0;
  61. int heapErrors = 0;
  62.  
  63. extern "C" void CreateHeap(void);
  64. void checkHeap(char *);
  65. void CreateChunkNodes();
  66.  
  67. void *makeSegPtr(unsigned long addr)
  68. {
  69. #ifdef PROTECT
  70.     return (void *) addr;
  71. #else
  72.     unsigned seg = addr>>4;
  73.     unsigned offs = addr&15;
  74.     return MK_FP(seg,offs);
  75. #endif
  76. }
  77.  
  78. #pragma argsused
  79. void fillHeap(MemoryChunk *p)
  80. {
  81. #ifdef DEBUG
  82.     unsigned MHUGE *q = (unsigned MHUGE *) makeSegPtr(p->ptr);
  83.     unsigned long i;
  84.     for (i=0;i<8;i++)
  85.         *q++ = 0xbad;
  86. #ifdef BRUTAL
  87.     if (p->inuse==0)
  88.         for (i=8;i<p->sz/2;i++) {
  89.             *q++ = 0xbad;
  90.         }
  91. #endif
  92. #endif    
  93. }
  94.  
  95. void freeChunkNode(MemoryChunk *p)
  96. {
  97.     p->next = freeNodes;
  98.     freeNodes = p;
  99. }
  100.  
  101. //extern "C" void debug_out(char *, int, int);
  102.  
  103. #pragma argsused
  104. void mprintf(char *fmt, ...)
  105. {
  106. #ifdef DEBUG
  107.     va_list argptr;
  108.     unsigned count;
  109.     char buf[80];
  110.     va_start(argptr, fmt);
  111.     vsprintf(buf, fmt, argptr);
  112.     va_end(argptr);
  113.     _dos_write(1, buf, strlen(buf), &count);
  114. //    debug_out(buf, 24*80, 80);
  115. #endif
  116. }
  117.  
  118.  
  119. MemoryChunk * getChunkNode(unsigned long segp, unsigned long sz, int inUse)
  120. {
  121.     if (!freeNodes)
  122.         CreateChunkNodes();
  123.     MemoryChunk *p = freeNodes;
  124.     if (p) {
  125.         freeNodes = freeNodes->next;
  126.         p->ptr = segp;
  127.         p->sz = sz;
  128.         p->inuse = inUse;
  129.         p->next = p;
  130.         p->prev = p;
  131.         mprintf("getChunkNode at(%08lx) for %08lx\r\n", segp, sz);
  132.  
  133.     }
  134.     return p;
  135. }
  136.  
  137.  
  138. MemoryChunk *findChunk(void *ptr)
  139. {
  140. #ifdef PROTECT
  141.     unsigned long addr = (unsigned long) ptr;
  142. #else
  143.     unsigned long addr = long(FP_SEG(ptr))*16 + FP_OFF(ptr);
  144. #endif
  145.  
  146. #ifdef DEBUG
  147.     addr -= 16;
  148. #endif
  149.     // find a free memory chunk
  150.     MemoryChunk *m = realMem;
  151.     for (;;) {
  152.         if ( m->inuse!=0 && m->ptr==addr ) {
  153.             return m;
  154.         }
  155.         m = m->next;
  156.         if (m==realMem) {
  157.             return 0;    // could not find
  158.         }
  159.     }
  160. }
  161.  
  162. void insertChunk(MemoryChunk *& root, MemoryChunk *leftover)
  163. {
  164.     if (root==0) {
  165.         root = leftover;
  166.         root->next = root;
  167.         root->prev = root;
  168.     }
  169.     else {
  170.         MemoryChunk *m = root;
  171.         // find m where:
  172.         //  m->ptr < leftover->ptr  < m->next->ptr
  173.         for (;;) {
  174.             if (leftover->ptr < m->next->ptr) break;
  175.             if (m->next == root) break;
  176.             m = m->next;
  177.         }
  178.  
  179.         MemoryChunk *nextChunk = m->next;
  180.         leftover->next = nextChunk;
  181.         m->next = leftover;
  182.         nextChunk->prev = leftover;
  183.         leftover->prev = m;
  184.  
  185.         if (leftover->ptr < root->ptr)
  186.             root = leftover;
  187.     }
  188. }
  189.  
  190. MemoryChunk *returnExcess(MemoryChunk *m, unsigned long resizeTo)
  191. {
  192.     MemoryChunk *leftover = getChunkNode(m->ptr+resizeTo, m->sz-resizeTo, 0);
  193.  
  194.     if (leftover==0) {
  195.         return 0;    // couldn't allocate a descriptor
  196.     }
  197.  
  198.     // carve up this chunk
  199.     {
  200.         m->sz = resizeTo;
  201.         MemoryChunk *nextChunk = m->next;
  202.         leftover->next = m->next;
  203.         m->next = leftover;
  204.         nextChunk->prev = leftover;
  205.         leftover->prev = m;
  206.         realMem = leftover;
  207.         fillHeap(leftover);
  208.     }
  209.     return m;
  210. }
  211.  
  212. #ifdef PROTECT
  213. void CreateChunkNodes()
  214. {
  215.     unsigned selector;
  216.  
  217.     freeNodes = 0;
  218.     unsigned nodeSz = INITIAL_CHUNK_NODES * sizeof(MemoryChunk);
  219.     nodeSz = (nodeSz+15);
  220.     nodeSz = nodeSz - (nodeSz&15);
  221.     if (Dpmi.getMappedMemory(nodeSz, selector, AccessRightsData)!=DPMI_OK) {
  222.         mprintf("cannot get memory for MemoryChunks\n");
  223.         return;
  224.     }
  225.  
  226.     mprintf("freeNodes at(%04x,%04x) for %04x\r\n", selector,0, nodeSz);
  227.  
  228.     MemoryChunk *freeArray = (MemoryChunk *) MK_FP(selector, 0);
  229.     int i;
  230.     for (i=0;i<INITIAL_CHUNK_NODES;i++)
  231.         freeChunkNode( &freeArray[i] );
  232. }
  233.  
  234. void CreateHeap(void)
  235. {
  236.     mprintf("create heap\n");
  237.     freeNodes = 0;
  238.     CreateChunkNodes();
  239.     int i;
  240.     realMem = 0;
  241.     while (_protheaplen>0) {
  242.         unsigned selector;
  243.         long sz = 0x10000l;
  244.         if (sz>_protheaplen) sz = _protheaplen;
  245.         if (Dpmi.getMappedMemory(sz, selector, AccessRightsData)!=DPMI_OK) {
  246.             mprintf("cannot get memory\n");
  247.             return;
  248.         }
  249.         MemoryChunk *chunk = getChunkNode( long(selector)<<16, sz, 0);
  250.         fillHeap(chunk);
  251.         insertChunk(rootMem, chunk);
  252.         memoryLeft += sz;
  253.         _protheaplen -= sz;
  254.     }
  255.     realMem = rootMem;
  256. }
  257. #else
  258. void CreateChunkNodes(void)
  259. {
  260. }
  261.  
  262. void CreateHeap(void)
  263. {
  264.     unsigned segp;
  265.     unsigned sz = 64000;
  266.     if (_dos_allocmem(sz, &segp)!=0) {
  267.         sz = segp;
  268.         if (_dos_allocmem(sz, &segp)!=0)
  269.             return;
  270.     }
  271.     
  272.     {
  273.         freeNodes = 0;
  274.         unsigned nodeSz = INITIAL_CHUNK_NODES * sizeof(MemoryChunk);
  275.         nodeSz = (nodeSz+15);
  276.         nodeSz = nodeSz - (nodeSz&15);
  277.  
  278.         mprintf("freeNodes at(%04x,%04x) for %04x\r\n", segp,0, nodeSz);
  279.  
  280.         MemoryChunk *freeArray = (MemoryChunk *) MK_FP(segp, 0);
  281.         segp += (nodeSz>>4);
  282.         sz -= (nodeSz>>4);
  283.         int i;
  284.         for (i=0;i<INITIAL_CHUNK_NODES;i++)
  285.             freeChunkNode( &freeArray[i] );
  286.     }
  287.  
  288.     realMem = getChunkNode( long(segp)<<4, long(sz)<<4, 0);
  289.     rootMem = realMem;
  290.     memoryLeft += (long(sz)<<4);
  291.     fillHeap(rootMem);
  292.     checkHeap("CreatHeap");
  293. }
  294. #endif
  295.  
  296. #pragma startup CreateHeap 4
  297.  
  298.  
  299. unsigned long roundUp(unsigned long sz)
  300. {
  301.     unsigned long roundedSz = sz+15;
  302. #ifdef DEBUG
  303.     roundedSz += 16;
  304. #endif
  305.     return roundedSz - (roundedSz&15);
  306. }
  307.  
  308. void *farmalloc(unsigned long sz)
  309. {
  310.     if (!realMem) return 0;
  311.     mprintf("malloc(%04x)\r\n", sz);
  312.     unsigned long roundedSz = roundUp(sz);
  313.  
  314.     // find a free memory chunk
  315.     MemoryChunk *m = realMem;
  316.     for (;;) {
  317.         if (m->inuse==0 && m->sz>=roundedSz)
  318.             break;
  319.         m = m->next;
  320.         if (m==realMem) {
  321.             mprintf("malloc(%04lx) no more memory %04lx left\r\n", sz, memoryLeft);
  322.             return 0;    // could not allocate
  323.         }
  324.     }
  325.  
  326.     if (roundedSz<m->sz) {    // get remainder node
  327.         if (!returnExcess(m, roundedSz)) {
  328.             mprintf("malloc(%04x) no more descriptors\r\n", sz);
  329.             return 0;
  330.         }
  331.     }
  332.  
  333.     // note that all pointers have a zero offset.
  334.     m->inuse = 1;
  335.     memoryLeft -= roundedSz;
  336.     mprintf("malloc(%04lx, %04lx <- %04lx) %04lx left\r\n", m->ptr, roundedSz, sz, memoryLeft);
  337. #ifdef DEBUG
  338.     fillHeap(m);
  339.     checkHeap("after malloc");
  340.     return makeSegPtr(m->ptr+16);
  341. #else
  342.     return makeSegPtr(m->ptr);
  343. #endif
  344. }
  345.  
  346. void *malloc(size_t sz)
  347. {
  348.     return farmalloc(sz);
  349. }
  350.  
  351. void *farrealloc(void *p, unsigned long sz)
  352. {
  353.     if (!p) return farmalloc(sz);
  354.     unsigned long roundSz = roundUp(sz);
  355.     MemoryChunk *oldChunk = findChunk(p);
  356.     if (oldChunk->sz==roundSz)
  357.         return p;
  358. #ifdef BAD
  359.     if (oldChunk->sz<roundSz) {    // shrink region
  360.         if (!returnExcess(oldChunk, roundSz)) {
  361.             mprintf("farrealloc(%04x) no more descriptors\r\n", sz);
  362.             return 0;
  363.         }
  364.         return p;
  365.     }
  366. #endif
  367.     void *newRegion = farmalloc(sz);
  368.     if (!newRegion) return 0;
  369.     memcpy(newRegion, p, sz);
  370.     farfree(p);
  371.     return newRegion;
  372. }
  373.  
  374. void *realloc(void *p, size_t sz)
  375. {
  376.     return farrealloc(p,sz);
  377. }
  378.  
  379. #pragma argsused
  380. void traceback(unsigned bp)
  381. {
  382. #ifndef PROTECT
  383.     int i;
  384.     extern unsigned _psp;
  385.  
  386.     mprintf("    cs=%04x ss=%04x psp=%04x\r\n", _CS, _SS, _psp );
  387.     for (i=0;i<5;i++) {
  388.         unsigned *p = (unsigned *) MK_FP(_SS,bp);
  389.         mprintf("    return to bp=%04x , pc=%04x:%04x (%04x:%04x rel)\r\n        ", p[0], p[2], p[1], p[2]-_psp-0x10, p[1] );
  390.         int j;
  391.         for (j=0;j<5;j++)
  392.             mprintf(" %04x", p[j]);
  393.         mprintf("\r\n");
  394.         if (p[0]<=bp) break;
  395.         bp = p[0];
  396.     }
  397. #endif
  398. }
  399.  
  400. int mergeChunks(MemoryChunk *m)
  401. {
  402.     // combine with upper region
  403.     MemoryChunk *nextChunk = m->next;
  404.     if (m->inuse==0 && nextChunk->inuse==0 && nextChunk->ptr == m->ptr+m->sz) {
  405.         m->next = nextChunk->next;
  406.         m->next->prev = m;
  407.         m->sz += nextChunk->sz;
  408.         if (nextChunk==realMem) realMem = m;
  409.         freeChunkNode(nextChunk);
  410.         return 1;
  411.     }
  412.     return 0;
  413. }
  414.  
  415. void farfree(void far *ptr)
  416. {
  417.     if (!ptr) return;
  418.  
  419.     MemoryChunk *m = findChunk(ptr);
  420.     if (!m) {
  421.         mprintf("free(%04x:%04x) block not allocated free\r\n", FP_SEG(ptr), FP_OFF(ptr) );
  422.         traceback(_BP);
  423.         return;
  424.     }
  425.     m->inuse = 0;
  426.     unsigned long sz = m->sz;
  427.     memoryLeft += sz;
  428.  
  429.     MemoryChunk *prev = m->prev;
  430.     mergeChunks(m);
  431.     if (mergeChunks(prev)) m = prev;
  432. #ifdef DEBUG
  433.     fillHeap(m);
  434.     checkHeap("after free");
  435. //    mprintf("free(%04x:%04x,%04lx)\r\n", FP_SEG(ptr), FP_OFF(ptr), sz );
  436. #endif
  437. }
  438.  
  439. void free(void *p)
  440. {
  441.     farfree(p);
  442. }
  443.  
  444. int farheapcheck1(void)
  445. {
  446.     MemoryChunk *p = rootMem;
  447.     for (;;) {
  448.         MemoryChunk *next = p->next;
  449. #ifndef PROTECT
  450.         if (next!=rootMem) {
  451.             unsigned long nextptr = p->ptr + p->sz;
  452.             if (nextptr!=next->ptr) {
  453.                 mprintf("MemoryChunk list corrupt! %04lx + %04lx != %04lx %04lx\r\n",
  454.                         p->ptr, p->sz, nextptr, next->ptr);
  455.                 return _HEAPCORRUPT;
  456.             }
  457.         }
  458. #endif
  459.  
  460. #ifdef DEBUG
  461.         unsigned MHUGE *q = (unsigned MHUGE *) makeSegPtr(p->ptr);
  462.         unsigned long i;
  463.         for (i=0;i<8;i++)
  464.             if ((*q++) != 0xbad) {
  465.                 mprintf("Memory at %06lx corrupt\r\n", p->ptr);
  466.                 return _HEAPCORRUPT;
  467.             }
  468. #ifdef BRUTAL
  469.         if (p->inuse==0)
  470.             for (i=8;i<p->sz/2;i++)
  471.                 if ((*q++) != 0xbad) {
  472.                     mprintf("Memory at %06lx corrupt\r\n", p->ptr);
  473.                     return _HEAPCORRUPT;
  474.                 }
  475. #endif
  476. #endif
  477.         p = next;
  478.         if (p==rootMem) break;
  479.     }
  480.     return _HEAPOK;
  481. }
  482.  
  483. int farheapcheck(void)
  484. {
  485.     return _HEAPOK;
  486. }
  487.  
  488. int heapcheck(void)
  489. {
  490.     return farheapcheck();
  491. }
  492.  
  493. unsigned long coreleft()
  494. {
  495.     return memoryLeft;
  496. }
  497.  
  498. unsigned long farcoreleft()
  499. {
  500.     return memoryLeft;
  501. }
  502.  
  503. void checkHeap(char *where)
  504. {
  505.     if (heapErrors<20) {
  506.         if (farheapcheck1()!=_HEAPOK) {
  507.             mprintf("heap corrupt from %s\n", where);
  508.             heapErrors++;
  509.         }
  510.     }
  511. }
  512.  
  513.  
  514.