home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / MacPerl 5.0.3 / MacPerl Source ƒ / Perl5 / icemalloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-27  |  37.5 KB  |  1,521 lines  |  [TEXT/MPS ]
  1.  
  2. /*
  3. **
  4. ** Notice.
  5. **
  6. ** This source code was written by Tim Endres. time@ice.com
  7. ** Copyright 1988-1991 © By Tim Endres. All rights reserved.
  8. ** 8840 Main Street, Whitmore Lake, MI  48189
  9. **
  10. ** You may use this source code for any purpose you can dream
  11. ** of as long as this notice is never modified nor removed.
  12. **
  13. ** Please email me any improvements that you might make. Any
  14. ** reasonable form of diff (compare) on the files changes will
  15. ** do nicely. You can mail "time@ice.com". Thank you.
  16. **
  17. ** BTW: In case it is not obvious, do not #define DOCUMENTATION ;)
  18. **
  19. * $Log: icemalloc.c,v $
  20.  * Revision 1.3  1994/05/04  02:10:46  neeri
  21.  * Rewrote memory management.
  22.  *
  23.  * Revision 1.2  1994/04/01  17:51:22  neeri
  24.  * Bucket allocator works.
  25.  *
  26. */
  27.  
  28. /* DISPATCH_START */
  29. #include <Types.h>
  30. #include <Memory.h>
  31. #include <Files.h>
  32.  
  33. #include <stdarg.h>
  34.  
  35. #include "icemalloc.h"
  36.  
  37. #undef PARANOID
  38.  
  39. #define mNEWPTR(size)            ( NewPtr ( (size) ) )
  40. #define mDISPOSPTR(ptr)            ( DisposPtr ( (ptr) ) )
  41.  
  42. _mem_pool    _mem_system_pool = {
  43.     0,                        /* id */
  44.     SUGGESTED_BLK_SIZE,        /* pref_blk_size */
  45.     0,                        /* blk_list */
  46.     0,                        /* next */
  47. #ifdef _PM_STATS
  48.     0,                        /* total_memory */
  49.     0,                        /* total_storage */
  50.     0,                        /* total_malloc */
  51.     0,                        /* max_blk_size */
  52.     0.0,                    /* ave_req_size */
  53.     0,                        /* ave_req_total */
  54.     0.0,                    /* ave_blk_size */
  55.     0,                        /* ave_blk_total */
  56. #endif
  57.     };
  58. _mem_pool_ptr                _mem_pool_forest = & _mem_system_pool;
  59.  
  60. #undef DEBUG
  61. /* DISPATCH_END */
  62.  
  63. #ifdef MALLOC_LOG
  64. short gMallocLogFile = 0;
  65.  
  66. void MallocLog(const char * fmt, ...)
  67. {
  68.     char         mallocbuf[64];
  69.     va_list    args;
  70.     long        len;
  71.     
  72.     if (!gMallocLogFile)
  73.         FSOpen("\pMalloc Log", 0, &gMallocLogFile);
  74.     
  75.     va_start(args, fmt);
  76.     len = vsprintf(mallocbuf, fmt, args);
  77.     FSWrite(gMallocLogFile, &len, mallocbuf);
  78.     va_end(args);
  79. }
  80. #else
  81. void MallocLog(const char * fmt, ...)
  82. {
  83. }
  84. #endif
  85.  
  86. #ifdef PARANOID
  87. /* Check for black choppers */
  88. void CheckBucketIntegrity(_mem_pool_ptr pool, _mem_bucket_ptr bucket)
  89. {
  90.     while (bucket) {
  91.         char * freeList = bucket->free;
  92.         int     count     =    bucket->free_count;
  93.         
  94.         while (freeList) {
  95.             if (freeList < bucket->memory || freeList > bucket->memory + pool->pref_blk_size)
  96.                 DebugStr((StringPtr) "\pFree list damaged!");    
  97.             freeList     = *(char **) freeList;
  98.             if (!count--)
  99.                 DebugStr((StringPtr) "\pFree list too short!");;
  100.         }
  101.         if (count)
  102.             DebugStr((StringPtr) "\pFree list too long!");
  103.         bucket = bucket->next;
  104.     }
  105. }
  106.  
  107. void CheckPoolIntegrity(_mem_pool_ptr pool)
  108. {
  109.     CheckBucketIntegrity(pool, pool->blk_16);
  110.     CheckBucketIntegrity(pool, pool->blk_32);
  111.     CheckBucketIntegrity(pool, pool->blk_64);
  112. }
  113. #else
  114. #define CheckBucketIntegrity(x, y)    0
  115. #define CheckPoolIntegrity(x)        0
  116. #endif
  117.  
  118. #ifdef DOCUMENTATION
  119.  
  120.     malloc() will allocate "size" bytes from the default malloc pool.
  121.     
  122. #endif
  123.  
  124. /* DISPATCH_START */
  125. void    *
  126. malloc (size_t size )
  127. {
  128.     _mem_pool_ptr    pool;
  129.     char *            mem;
  130.  
  131.     pool = _default_mem_pool;
  132.     if (pool == (_mem_pool_ptr)0)
  133.         return (char *)0;
  134.     
  135.     mem = pool_malloc(pool, size);
  136.     
  137. #ifdef MALLOC_LOG
  138.     MallocLog("%d %d\n", (int) mem, (int) size); 
  139. #endif
  140.  
  141.     return mem;
  142. }
  143. /* DISPATCH_END */
  144.  
  145.  
  146. #ifdef DOCUMENTATION
  147.  
  148.     free() will free the memory occupied by the "ptr" allocated by malloc().
  149.     
  150. #endif
  151.  
  152. /* DISPATCH_START */
  153. void free(void * ptr)
  154. {
  155.     
  156. #ifdef MALLOC_LOG
  157.     MallocLog("%d\n", (int) ptr); 
  158. #endif
  159.     
  160.     pool_free((char *) ptr);
  161. }
  162. /* DISPATCH_END */
  163.  
  164. #ifdef DOCUMENTATION
  165.  
  166.     MN 15May93 realloc() tries to change the size of the memory pointed 
  167.     to by "ptr". No optimizations are attempted.
  168.     
  169. #endif
  170.  
  171. /* DISPATCH_START */
  172. void * realloc(void * old, u_long size)
  173. {
  174.     void *            nu;
  175.     
  176.     nu = malloc(size);
  177.     
  178.     if (!old || !nu)
  179.         return nu;
  180.     
  181.     memcpy(nu, old, size);
  182.     
  183.     free(old);
  184.     
  185.     return nu;
  186. }
  187. /* DISPATCH_END */
  188.  
  189. void * pool_realloc(_mem_pool_ptr pool, void * old, u_long size)
  190. {
  191.     void *            nu;
  192.     
  193.     nu = pool_malloc(pool, size);
  194.     
  195.     if (!old || !nu)
  196.         return nu;
  197.     
  198.     memcpy(nu, old, size);
  199.     
  200.     pool_free(old);
  201.     
  202.     return nu;
  203. }
  204.  
  205. #ifdef DOCUMENTATION
  206.  
  207.     MN 27Jul94 calloc() tries to change the size of the memory pointed 
  208.     to by "ptr". No optimizations are attempted.
  209.     
  210. #endif
  211.  
  212. /* DISPATCH_START */
  213. void *
  214. calloc(u_long nmemb, u_long size)
  215. {
  216.     return malloc(nmemb*size);
  217. }
  218. /* DISPATCH_END */
  219.  
  220. void fastzero(void * ptr, u_long size)
  221. {
  222.     int     portiuncula;
  223.     int     longs;
  224.     int     max;
  225.     long    *lptr;
  226.  
  227.     longs = size >> 2;
  228.     lptr  = (long *) ptr;
  229.     max   = 8;
  230.     
  231.     switch (longs) {
  232.     default:
  233.         *lptr++ = 0;
  234.     case 7:
  235.         *lptr++ = 0;
  236.     case 6:
  237.         *lptr++ = 0;
  238.     case 5:
  239.         *lptr++ = 0;
  240.     case 4:
  241.         *lptr++ = 0;
  242.     case 3:
  243.         *lptr++ = 0;
  244.     case 2:
  245.         *lptr++ = 0;
  246.     case 1:
  247.         *lptr++ = 0;
  248.     case 0:
  249.         break;
  250.     }
  251.     
  252.     for (longs -= 8; longs > 0; longs -= portiuncula) {
  253.         portiuncula = longs > max ? max : longs;
  254.         BlockMove((Ptr)(lptr - portiuncula), (Ptr) lptr, portiuncula*4);
  255.         max += portiuncula;
  256.         lptr += portiuncula;
  257.     }
  258. }
  259.  
  260. #ifdef DOCUMENTATION
  261.  
  262.     set_default_pool() - given a pool id, this routine will make it the default
  263.     pool from which malloc() allocates memory.
  264.     
  265. #endif
  266.  
  267. int set_default_pool(int id)
  268. {
  269.     _mem_pool_ptr    pool, last;
  270.  
  271.     if (_default_mem_pool->id == id)
  272.         return 0;
  273.     
  274.     last = _default_mem_pool;
  275.     pool = _default_mem_pool->next;
  276.     for ( ; pool != (_mem_pool_ptr)0 ; pool = pool->next) {
  277.         if (pool->id == id) {
  278.             last->next = pool->next;
  279.             pool->next = _default_mem_pool;
  280.             _default_mem_pool = pool;
  281.             return 0;
  282.         }
  283.     }
  284.     
  285.     return -1;
  286. }
  287.  
  288.  
  289. #ifdef DOCUMENTATION
  290.  
  291.     new_malloc_pool() creates a new pool from which memory can be malloc()-ed.
  292.     
  293. #endif
  294.  
  295. _mem_pool_ptr
  296. new_malloc_pool(int id, u_long pref_blk_size )
  297. {
  298.     _mem_pool_ptr    new_pool;
  299.  
  300.     new_pool = find_pool(id);
  301.     if (new_pool != NULL)            /* ? Is this the best choice? Its not ID-able */
  302.         return new_pool;
  303.  
  304.     new_pool = (_mem_pool_ptr) mNEWPTR(sizeof(_mem_pool));
  305.     if (new_pool == (_mem_pool_ptr)0)
  306.         return new_pool;
  307.     
  308.     new_pool->id = id;                            /* The pool's ID. */
  309.     new_pool->pref_blk_size = pref_blk_size;    /* The preferred size of new blks. */
  310.     new_pool->limit_blk_size = pref_blk_size*7 >> 4;
  311.     new_pool->blk_list = NULL;                    /* The list of blocks in the pool. */
  312.     new_pool->blk_16 = nil;
  313.     new_pool->blk_32 = nil;
  314.     new_pool->blk_64 = nil;
  315.     new_pool->free_16 = nil;
  316.     new_pool->free_32 = nil;
  317.     new_pool->free_64 = nil;
  318.     
  319.     /* The next two lines insert right after the default, so we don't change it. */
  320.     new_pool->next = _mem_pool_forest->next;
  321.     _mem_pool_forest->next = new_pool;
  322.  
  323. #ifdef _PM_STATS
  324.     new_pool->total_memory = 0;            /* The total allocated memory by this pool */
  325.     new_pool->total_storage = 0;        /* The total malloc-able storage in this pool */
  326.     new_pool->total_malloc = 0;            /* The total malloc-ed storage not freed. */
  327.     new_pool->max_blk_size = 0;            /* The maximum block size allocated. */
  328.     new_pool->ave_req_size = 0.0;        /* The ave allocated request size */
  329.     new_pool->ave_req_total = 0;        /* The total requests in the average. */
  330.     new_pool->ave_blk_size = 0.0;        /* The ave sallocated blk size */
  331.     new_pool->ave_blk_total = 0;        /* The total blks in the average. */
  332. #endif
  333.  
  334.     return new_pool;
  335. }
  336.  
  337.  
  338. #ifdef DOCUMENTATION
  339.  
  340.     find_pool() will find the pool with the given "id" and return its pointer.
  341.     
  342. #endif
  343.  
  344. _mem_pool_ptr find_pool(int id)
  345. {
  346.     _mem_pool_ptr    pool;
  347.  
  348.     for (pool = _mem_pool_forest ; pool != (_mem_pool_ptr)0 ; pool = pool->next) {
  349.         if (pool->id == id)
  350.             break;
  351.     }
  352.         
  353.     return pool;
  354. }
  355.  
  356.  
  357. #ifdef DOCUMENTATION
  358.  
  359.     free_pool_memory() this will free and *release* all memory occupied by the
  360.     pool but not free the pool, letting you allocate some more.
  361.     
  362. #endif
  363.  
  364. int free_pool_memory(int id)
  365. {
  366.     _mem_pool_ptr        pool;
  367.     _mem_blk_ptr        blk, nextblk;
  368.     _mem_bucket_ptr    bucket;
  369.  
  370.     pool = find_pool(id);
  371.     if (pool == NULL)
  372.         return -1;
  373.     
  374.     /* The buckets themselves are always allocated from the pool and therefore
  375.        don't need to be disposed explicitely.
  376.     */
  377.     
  378.     for ( bucket = pool->blk_16; bucket; bucket = bucket->next)
  379.         mDISPOSPTR((Ptr) bucket->memory);
  380.     for ( bucket = pool->blk_32; bucket; bucket = bucket->next)
  381.         mDISPOSPTR((Ptr) bucket->memory);
  382.     for ( bucket = pool->blk_64; bucket; bucket = bucket->next)
  383.         mDISPOSPTR((Ptr) bucket->memory);
  384.     
  385.     pool->blk_16 = nil;
  386.     pool->blk_32 = nil;
  387.     pool->blk_64 = nil;
  388.     pool->free_16 = nil;
  389.     pool->free_32 = nil;
  390.     pool->free_64 = nil;
  391.     
  392.     for ( blk = pool->blk_list ; blk != (_mem_blk_ptr)0 ; ) {
  393.         nextblk = blk->next;
  394.         DPRINTF(3, ("pool_find_free_blk() Freeing Block x%lx from pool #%d!\n",
  395.                         blk, blk->pool->id));
  396. #ifdef _PM_STATS
  397.         pool->total_memory -= sizeof(_mem_blk) + blk->size;
  398.         pool->total_storage -= blk->size;
  399. #endif
  400.         mDISPOSPTR((Ptr)blk->memory);
  401.         mDISPOSPTR((Ptr)blk);
  402.  
  403.         blk = nextblk;
  404.     }
  405.  
  406.     pool->blk_list = NULL;
  407.     
  408.     return 0;
  409. }
  410.  
  411.  
  412. #ifdef DOCUMENTATION
  413.  
  414.     free_pool() will free the pool's memory *and* free the pool (removing
  415.     it from the pool list) releasing all memory back to the heap.
  416.     
  417. #endif
  418.  
  419. int free_pool(int id)
  420. {
  421.     _mem_pool_ptr    pool;
  422.  
  423.     if (free_pool_memory(id) == -1)
  424.         return -1;
  425.     
  426.     pool = find_pool(id);
  427.     if (pool == NULL)
  428.         return -1;
  429.     
  430.     mDISPOSPTR((Ptr)pool);
  431.     
  432.     return 0;
  433. }
  434.  
  435.  
  436. #ifdef DOCUMENTATION
  437.  
  438.     pool_malloc() does the low level malloc() work in a specified pool.
  439.     
  440. #endif
  441.  
  442. static char * _bucket_malloc(
  443.                 _mem_pool_ptr         pool, 
  444.                 u_long                 size, 
  445.                 _mem_bucket_ptr *    free,
  446.                 _mem_bucket_ptr *    buckets,
  447.                 short                    shift);
  448. static char * _blk_malloc(_mem_pool_ptr pool, u_long size);
  449. static _mem_blk_ptr _pool_new_blk(_mem_pool_ptr pool, u_long size_req);
  450. static _mem_blk_ptr _pool_find_free_blk(_mem_pool_ptr pool, u_long size_req, _mem_ptr_hdr_ptr * hdr_ptr);
  451.  
  452. void    * pool_malloc(_mem_pool_ptr pool, u_long size)
  453. {
  454.     if (size < 33)
  455.         if (size < 17)
  456.             return _bucket_malloc(pool, 16, &pool->free_16, &pool->blk_16, 4);
  457.         else
  458.             return _bucket_malloc(pool, 32, &pool->free_32, &pool->blk_32, 5);
  459.     else  if (size < 65)
  460.         return _bucket_malloc(pool, 64, &pool->free_64, &pool->blk_64, 6);
  461.     else
  462.         return _blk_malloc(pool, size);
  463. }
  464.  
  465. char * _bucket_malloc(
  466.                 _mem_pool_ptr         pool, 
  467.                 u_long                 size, 
  468.                 _mem_bucket_ptr *    free,
  469.                 _mem_bucket_ptr *    buckets,
  470.                 short                    shift)
  471. {
  472.     _mem_bucket_ptr    bucket;
  473.     char *                 mem;
  474.  
  475.     CheckBucketIntegrity(pool, *buckets);
  476.     
  477.     if (!(bucket = *free)) {
  478.         for (bucket = *buckets; bucket && !bucket->free_count; bucket = bucket->next);
  479.     
  480.         if (!bucket) {
  481.             int count;
  482.             int max                = pool->pref_blk_size >> shift;
  483.             char * next;
  484.             
  485.             if (!(bucket = (_mem_bucket_ptr) _blk_malloc(pool, sizeof(_mem_bucket))))
  486.                 return nil;
  487.                 
  488.             bucket->prev        = (_mem_bucket_ptr) buckets;
  489.             bucket->next         = *buckets;
  490.             *buckets             = bucket;
  491.             bucket->pool         = pool;
  492.             bucket->max_count    = max;
  493.             bucket->free_count= max;
  494.             
  495.             if (!(bucket->memory = mem = mNEWPTR(pool->pref_blk_size)))
  496.                 return nil;
  497.             
  498.             *(char **) mem = nil;
  499.             for (count = 1; count++ < max; mem = next) {
  500.                 next = mem + size;
  501.                 *(char **) next = mem;
  502.             }
  503.             bucket->free        = next;
  504.         }
  505.         *free = bucket;
  506.     }
  507.     mem                 = bucket->free;
  508.     bucket->free     = *(char **) mem;
  509.     if (!--bucket->free_count)
  510.         *free = nil;
  511.     else if (bucket->free < bucket->memory || bucket->free > bucket->memory + pool->pref_blk_size)
  512.         DebugStr((StringPtr) "\pFatal allocation error!");
  513.  
  514.     fastzero(mem, size);
  515.     
  516.     return mem;
  517. }
  518.  
  519. char    * _blk_malloc(_mem_pool_ptr pool, u_long size)
  520. {
  521.     _mem_blk_ptr        blk;
  522.     _mem_ptr_hdr_ptr    hdr = (_mem_ptr_hdr_ptr)0, freehdr;
  523.     u_long                freesize, size_req;
  524.     char                *ptr = (char *)0;
  525.  
  526.     DPRINTF(5, ("_pool_malloc() request of %ld bytes in pool #%d [x%lx]\n",
  527.                 size, pool->id, pool));
  528.         
  529.     size_req = (size < _PM_MIN_ALLOC_SIZE) ? _PM_MIN_ALLOC_SIZE : size;
  530.     size_req = INT_ALIGN(size_req, ALIGNMENT);
  531.  
  532. #ifdef _PM_STATS
  533.     pool->ave_req_size = ( ( (pool->ave_req_size * (float)pool->ave_req_total) + (float)size_req )
  534.                             / (float)(pool->ave_req_total + 1) );
  535.     pool->ave_req_total++;
  536. #endif
  537.  
  538.     blk = pool->blk_list;
  539.     if (blk == NULL) {
  540.         /* No blocks in pool, allocate one... */
  541.         blk = _pool_new_blk(pool, size_req);
  542.     } else {
  543.         blk = _pool_find_free_blk(pool, size_req, &hdr);
  544.  
  545.         if (blk == (_mem_blk_ptr)0 || hdr == (_mem_ptr_hdr_ptr)0) {
  546.             /* No blocks that can support this size... */
  547.             blk = _pool_new_blk(pool, size_req);
  548.         } else
  549.             DPRINTF(5, ("_pool_malloc() found free: blk x%lx hdr x%lx\n",
  550.                         blk, hdr));
  551.     }
  552.     
  553.     if (blk != (_mem_blk_ptr)0) {
  554.         /* Determine the pointer's location, establish, return. */
  555.         if (hdr == (_mem_ptr_hdr_ptr)0) {
  556.             hdr = (_mem_ptr_hdr_ptr) blk->memory;
  557.             DPRINTF(5, ("_pool_malloc() header of new blk blk->memory x%lx\n", blk->memory));
  558.         }
  559.         
  560.         DPRINTF(5, ("_pool_malloc() free hdr x%lx size %ld\n", hdr, GET_PTR_SIZE(hdr)));
  561.         if (hdr != (_mem_ptr_hdr_ptr)0) {
  562.             ptr = (char *)hdr + sizeof(_mem_ptr_hdr);
  563.             
  564.             if (size_req < GET_PTR_SIZE(hdr)) {
  565.                 /* Split this free block... */
  566.                 DPRINTF(5, ("_pool_malloc() split hdr x%lx into %ld used and %ld free\n",
  567.                             hdr, size_req, GET_PTR_SIZE(hdr) - (size_req + sizeof(_mem_ptr_hdr))));
  568.  
  569.                 freehdr = (_mem_ptr_hdr_ptr)
  570.                             ( (char *)hdr + sizeof(_mem_ptr_hdr) + size_req );
  571.                 freesize = GET_PTR_SIZE(hdr) - (sizeof(_mem_ptr_hdr) + size_req);
  572.                 fastzero(freehdr, sizeof(_mem_ptr_hdr));
  573.                 SET_PTR_FREE(freehdr);
  574.                 SET_PTR_SIZE(freehdr, freesize);
  575.                 blk->max_free -= sizeof(_mem_ptr_hdr);
  576.             }
  577.  
  578. #ifdef _PM_STATS    
  579.             pool->total_malloc += size_req;
  580. #endif
  581.  
  582.             blk->max_free -= size_req;
  583.             SET_PTR_USED(hdr);
  584.             SET_PTR_SIZE(hdr, size_req);
  585.             fastzero(ptr, size_req);        /* Programmer's expect malloc() to zero. */
  586.         } else {
  587.             /* ERROR: This should not happen!!! */
  588.             DPRINTF(1, ("ERROR: pool_malloc() could not get block's free hdr ptr\n"));
  589.             DACTION(2, { list_pool_forest(NULL); });
  590.         }
  591.     } else {
  592.         /* ERROR, no block, no memory. */
  593.         DPRINTF(1, ("ERROR: pool_malloc() could not get a block\n"));
  594.         DACTION(2, { list_pool_forest(NULL); });
  595.     }
  596.     
  597.     DPRINTF(5, ("_pool_malloc() returning ptr x%lx\n", ptr));
  598.     return ptr;
  599. }
  600.  
  601. #ifdef DOCUMENTATION
  602.  
  603.     pool_free() does the low level work of a free().
  604.     
  605. #endif
  606.  
  607. static _mem_bucket_ptr _pool_find_ptr_bucket(char * ptr);
  608. static int _block_is_freed(_mem_blk_ptr blk);
  609. static _mem_blk_ptr _pool_find_ptr_blk(char    * ptr);
  610.  
  611. int pool_free(void * ptr)
  612. {
  613.     _mem_pool_ptr        pool;
  614.     _mem_blk_ptr        blk;
  615.     _mem_ptr_hdr_ptr    hdr, adjhdr, limit;
  616.     int                    result = 0;
  617.     u_long                ptr_size, new_size;
  618.     _mem_bucket_ptr    bucket;
  619.  
  620.     if (ptr == (void *)0) {
  621.         /* WHOAH! NULL Pointers... */
  622.         DPRINTF(1, ("pool_free() ptr NULL!"));
  623.         return -1;
  624.     }
  625.     
  626.     if ( ( (u_long)ptr & 1 ) != 0 ) {
  627.         /* WHOAH! ODD Pointers... */
  628.         DPRINTF(1, ("pool_free() ptr ODD!"));
  629.         return -1;
  630.     }
  631.     
  632.     DPRINTF(5, ("pool_free() free ptr x%lx\n", ptr));
  633.  
  634.     if (bucket = _pool_find_ptr_bucket(ptr)) {
  635.         CheckBucketIntegrity(bucket->pool, bucket);
  636.         if (
  637.             ++bucket->free_count == bucket->max_count
  638.         ) {    /* Kick the bucket */
  639.             bucket->prev->next = bucket->next;
  640.             
  641.             if (bucket->next)
  642.                 bucket->next->prev = bucket->prev;
  643.             
  644.             mDISPOSPTR(bucket->memory);
  645.             pool_free(bucket);
  646.         } else {
  647.             *(char **) ptr = bucket->free;
  648.             bucket->free = ptr;
  649.         }
  650.         return -1;
  651.     }
  652.         
  653.     blk = _pool_find_ptr_blk(ptr);
  654.     
  655.     if (blk == (_mem_blk_ptr)0) {
  656.         /* We could not find this thing's blk! BUG!!! */
  657.         DPRINTF(1, ("ERROR: free(x%lx) could not find ptr's blk\n", ptr));
  658.         DACTION(2, { list_pool_forest(NULL); });
  659.         result = -1;
  660.     } else {
  661.         /*
  662.         ** Now, if it is adjacent to free memory, combine.
  663.         ** NOTE: We only do this because it is SO DAMN CHEAP!!!!!
  664.         */
  665.  
  666.         /* Delay these assigns til we know ptr is good. (now) */
  667.         hdr = (_mem_ptr_hdr_ptr) ( (u_long)ptr - sizeof(_mem_ptr_hdr) );
  668.         ptr_size = GET_PTR_SIZE(hdr);
  669.  
  670.         DPRINTF(5, ("pool_free() free hdr x%lx size %ld flags x%02x in blk x%lx\n",
  671.                     hdr, ptr_size, GET_PTR_FLAGS(hdr), blk));
  672.     
  673.         pool = blk->pool;
  674.         SET_PTR_FREE(hdr);
  675.         blk->max_free += ptr_size;
  676.         
  677.         adjhdr = (_mem_ptr_hdr_ptr)
  678.                     ( (char *)hdr + GET_PTR_SIZE(hdr) +
  679.                       sizeof(_mem_ptr_hdr) );
  680.         limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  681.         
  682.         if (adjhdr < limit && IS_PTR_FREE(adjhdr)) {
  683.             DPRINTF(5, ("pool_free() merging hdr x%lx with freehdr x%lx\n", hdr, adjhdr));
  684.             
  685.             new_size =    GET_PTR_SIZE(hdr) +
  686.                         GET_PTR_SIZE(adjhdr) +
  687.                         sizeof(_mem_ptr_hdr);
  688.  
  689.             DPRINTF(5, ("pool_free() merged hdr new_size %ld\n", new_size));
  690.             SET_PTR_SIZE(hdr, new_size);
  691.             blk->max_free += sizeof(_mem_ptr_hdr);
  692.         }    /* is adjacent free ? */
  693.         
  694. #ifdef _PM_STATS    
  695.         pool->total_malloc -= ptr_size;
  696. #endif
  697.  
  698. #ifdef _PM_DYNAMIC_FREE
  699.         if (_block_is_freed(blk)) {
  700.             /* This blk is free-ed ... */
  701.             _mem_blk_ptr    tmpblk;
  702.  
  703.             if (blk == blk->pool->blk_list) {
  704.                 blk->pool->blk_list = blk->next;
  705.             } else {
  706.                 tmpblk = blk->pool->blk_list;
  707.                 while (tmpblk != (_mem_blk_ptr)0) {
  708.                     if (tmpblk->next == blk) {
  709.                         tmpblk->next = blk->next;
  710.                         break;
  711.                     } else
  712.                         tmpblk = tmpblk->next;
  713.                 }
  714.                 if (tmpblk == (_mem_blk_ptr)0)
  715.                     DPRINTF(1, ("ERROR: could not free blk x%lx from list!\n", blk));
  716.             }
  717.             
  718.             DPRINTF(3, ("pool_free() Freeing Block x%lx from pool #%d!\n",
  719.                         blk, blk->pool->id));
  720. #ifdef _PM_STATS
  721.             pool->total_memory -= sizeof(_mem_blk) + blk->size;
  722.             pool->total_storage -= blk->size;
  723. #endif
  724.             mDISPOSPTR((Ptr)blk->memory);
  725.             mDISPOSPTR((Ptr)blk);
  726.         }    /* if (block_is_freed(blk)) */
  727. #endif _PM_DYNAMIC_FREE
  728.  
  729.         result = 0;
  730.     }    /* else we found the block containing the ptr. */
  731.     
  732.     return result;
  733. }
  734.  
  735. #ifdef DOCUMENTATION
  736.  
  737.     _block_is_freed() determines if all memory in a given block is free.
  738.     
  739. #endif
  740.  
  741. int _block_is_freed(_mem_blk_ptr blk)
  742. {
  743.     int            freed = 1;
  744.     _mem_ptr_hdr_ptr    loophdr, limit;
  745.  
  746. /*
  747. ** This loop is not as expensive as you might think, since most of the
  748. ** time we've "merged" into few "ptrs", and in allocated cases we will
  749. ** break out of the loop almost immediately.
  750. */
  751.  
  752.     if (blk != NULL) {
  753.         loophdr = (_mem_ptr_hdr_ptr) blk->memory;
  754.         limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  755.         while (loophdr < limit) {
  756.             if (! IS_PTR_FREE(loophdr)) {
  757.                 freed = 0;
  758.                 break;
  759.                 }
  760.             
  761.             loophdr = (_mem_ptr_hdr_ptr)
  762.                         ((char *)loophdr + GET_PTR_SIZE(loophdr) + sizeof(_mem_ptr_hdr));
  763.             }
  764.         }
  765.     else
  766.         freed = 0;    /* ? Or is it really free? */
  767.     
  768.     return freed;
  769.     }
  770.  
  771.  
  772. #ifdef DOCUMENTATION
  773.  
  774.     _pool_new_blk() allocate a new memory block to a pool. This is called
  775.     by the low level malloc() code when new memory is needed.
  776.     
  777. #endif
  778.  
  779. _mem_blk_ptr _pool_new_blk(_mem_pool_ptr pool, u_long size_req)
  780. {
  781.     u_long                blk_size;
  782.     _mem_blk_ptr        new_blk;
  783.     _mem_ptr_hdr_ptr    hdr;
  784.  
  785.     DPRINTF(5, ("_pool_new_blk() req_size %ld pool #%d [x%lx]\n", size_req, pool->id, pool));
  786.  
  787.     /* MN 29Mar94 To avoid agonizing death from internal fragmentation, we make an 
  788.        allocation "private" if it would occupy more than about 45% of a block.
  789.     */
  790.     if ((size_req + sizeof(_mem_ptr_hdr)) > pool->limit_blk_size) {
  791.         blk_size = size_req + sizeof(_mem_ptr_hdr);
  792. #ifdef _PM_STATS
  793.         if (blk_size > pool->max_blk_size)
  794.             pool->max_blk_size = blk_size;
  795. #endif
  796.     } else
  797.         blk_size = pool->pref_blk_size;
  798.     
  799.     blk_size = INT_ALIGN(blk_size, ALIGNMENT);
  800.     
  801. #ifdef _PM_STATS
  802.     pool->ave_blk_size = ( ( (pool->ave_blk_size * (float)pool->ave_blk_total) + (float)blk_size )
  803.                             / (float)(pool->ave_blk_total + 1) );
  804.     pool->ave_blk_total++;
  805. #endif
  806.  
  807.     new_blk = (_mem_blk_ptr) mNEWPTR(sizeof(_mem_blk));
  808.     if (new_blk == (_mem_blk_ptr)0)
  809.         return new_blk;
  810.     
  811.     /*
  812.     ** NOTE: We assume here that mNEWPTR() gives us proper alignment.
  813.     */
  814.     new_blk->memory = (char *) mNEWPTR(blk_size);
  815. #ifdef NEVER_DEFINED
  816.     if (new_blk->memory == (char *)0) {
  817.         /* Attempt to handle the request only. */
  818.         blk_size = size_req + sizeof(_mem_ptr_hdr);
  819.         blk_size = INT_ALIGN(blk_size, ALIGNMENT);
  820.         new_blk->memory = (char *) mNEWPTR(blk_size);
  821.     }
  822. #endif
  823.     
  824.     if (new_blk->memory == (char *)0) {
  825.         mDISPOSPTR((Ptr)new_blk);
  826.         DPRINTF(10, ("_pool_new_blk(pool:x%lx, size:%ld) Out of memory.\n", pool, size_req));
  827.         return (_mem_blk_ptr)0;
  828.     }
  829.     
  830. #ifdef _PM_STATS
  831.     pool->total_memory += sizeof(_mem_blk) + blk_size;
  832.     pool->total_storage += blk_size;
  833. #endif
  834.  
  835.     new_blk->pool = pool;
  836.     new_blk->size = blk_size;
  837.     new_blk->max_free = blk_size - sizeof(_mem_ptr_hdr);
  838.     
  839.     /* Add to the block list. */
  840.     new_blk->next = pool->blk_list;
  841.     pool->blk_list = new_blk;
  842.     
  843.     hdr = (_mem_ptr_hdr_ptr) new_blk->memory;
  844.     fastzero(hdr, sizeof(_mem_ptr_hdr));
  845.     
  846.     SET_PTR_FREE(hdr);
  847.     SET_PTR_SIZE(hdr, ( blk_size - sizeof(_mem_ptr_hdr) ) );
  848.     
  849.     DPRINTF(5, ("_pool_new_blk() new blk x%lx size %ld memory x%lx pool #%d [x%lx]\n",
  850.             new_blk, new_blk->size, new_blk->memory, pool->id, pool));
  851.     return new_blk;
  852. }
  853.     
  854.  
  855. #ifdef DOCUMENTATION
  856.  
  857.     _pool_find_free_blk() looks for a block in the pool with enough free memory
  858.     to allocate the "size_req" bytes.
  859.     
  860. #endif
  861.  
  862. _mem_blk_ptr _pool_find_free_blk(_mem_pool_ptr pool, u_long size_req, _mem_ptr_hdr_ptr    * hdr_ptr)
  863. {
  864. _mem_blk_ptr        blk, use_this_blk;
  865. _mem_ptr_hdr_ptr    loophdr, limit;
  866. long                hdrsize, max_size;
  867.  
  868. #ifdef _PM_DYNAMIC_MERGING
  869. _mem_ptr_hdr_ptr    lasthdr, nexthdr, blkhdr;
  870. long                lastsize, nextsize;
  871. #endif _PM_DYNAMIC_MERGING
  872.  
  873.     blk = pool->blk_list;
  874.     max_size = 0x3FFFFFFF;
  875.     for (use_this_blk=NULL; blk != (_mem_blk_ptr)0 ; blk=blk->next) {
  876.         if (blk->max_free >= size_req) {
  877.             if (use_this_blk == NULL) {
  878.                 use_this_blk = blk;
  879.                 max_size = blk->size;
  880.             } else if (blk->size < max_size) {
  881.                 use_this_blk = blk;
  882.                 max_size = blk->size;
  883.             }
  884.         }
  885.     }
  886.     
  887.     blk = use_this_blk;
  888.     if (blk != NULL) {
  889.         loophdr = (_mem_ptr_hdr_ptr) blk->memory;
  890.         limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  891. #ifdef _PM_DYNAMIC_MERGING
  892.         lasthdr = (_mem_ptr_hdr_ptr)0;
  893. #endif _PM_DYNAMIC_MERGING
  894.         while (loophdr < limit) {
  895.             if (IS_PTR_FREE(loophdr)) {
  896.                 hdrsize = GET_PTR_SIZE(loophdr);
  897.                 if (hdrsize >= size_req) {
  898.                     DPRINTF(5, ("pool_find_free_blk() Found blk x%lx hdr x%lx pool #%d [x%lx]\n",
  899.                                 blk, loophdr, pool->id, pool));
  900.                     
  901.                     *hdr_ptr = loophdr;
  902.                     return blk;
  903.                 }
  904.  
  905. #ifdef _PM_DYNAMIC_MERGING
  906.                 else {
  907.                     nexthdr = (_mem_ptr_hdr_ptr)
  908.                                 ( (char *)loophdr + hdrsize + sizeof(_mem_ptr_hdr) );
  909.                     if (nexthdr < limit) {
  910.                         if (IS_PTR_FREE(nexthdr)) {
  911.                             nextsize = GET_PTR_SIZE(nexthdr);
  912.                             blk->max_free += sizeof(_mem_ptr_hdr);    /* We're gonna merge... */
  913.                             if ((nextsize + hdrsize + sizeof(_mem_ptr_hdr)) >= size_req) {
  914.                                 DPRINTF(3, ("pool_find_free_blk() F-Merge blk x%lx hdr1 x%lx hdr2 x%lx \n",
  915.                                             blk, loophdr, nexthdr));
  916.                                 
  917.                                 hdrsize = nextsize + hdrsize + sizeof(_mem_ptr_hdr);
  918.                                 SET_PTR_SIZE(loophdr, hdrsize);
  919.                                 *hdr_ptr = loophdr;
  920.                                 return blk;
  921.                             } else {
  922.                                 /* OK, so merge anyways... */
  923.                                 hdrsize = nextsize + hdrsize + sizeof(_mem_ptr_hdr);
  924.                                 SET_PTR_SIZE(loophdr, hdrsize);
  925.                             }
  926.                         }
  927.                     }
  928.                     if (lasthdr != (_mem_ptr_hdr_ptr)0) {
  929.                         if (IS_PTR_FREE(lasthdr)) {
  930.                             lastsize = GET_PTR_SIZE(lasthdr);
  931.                             blk->max_free += sizeof(_mem_ptr_hdr);    /* We're gonna merge... */
  932.                             if ((lastsize + hdrsize + sizeof(_mem_ptr_hdr)) >= size_req) {
  933.                                 DPRINTF(3, ("pool_find_free_blk() R-Merge blk x%lx hdr1 x%lx hdr2 x%lx \n",
  934.                                             blk, lasthdr, loophdr));
  935.                                 
  936.                                 hdrsize = lastsize + hdrsize + sizeof(_mem_ptr_hdr);
  937.                                 SET_PTR_SIZE(lasthdr, hdrsize);
  938.                                 *hdr_ptr = lasthdr;
  939.                                 return blk;
  940.                             } else {
  941.                                 /* OK, so merge anyways... */
  942.                                 hdrsize = lastsize + hdrsize + sizeof(_mem_ptr_hdr);
  943.                                 SET_PTR_SIZE(lasthdr, hdrsize);
  944.                             }
  945.                             loophdr = lasthdr;
  946.                             lasthdr = (_mem_ptr_hdr_ptr)0;
  947.                         }
  948.                     }
  949. #ifdef _PM_DYNAMIC_FREE
  950.                     blkhdr = (_mem_ptr_hdr_ptr)blk->memory;
  951.                     if (IS_PTR_FREE(blkhdr)) {
  952.                         if ((GET_PTR_SIZE(blkhdr) + sizeof(_mem_ptr_hdr)) == blk->size) {
  953.                             /* This blk is free-ed ... */
  954.                             
  955.                             _mem_blk_ptr    tmpblk, next;
  956.             
  957.                             if (blk == blk->pool->blk_list) {
  958.                                 blk->pool->blk_list = next = blk->next;
  959.                             } else {
  960.                                 tmpblk = blk->pool->blk_list;
  961.                                 while (tmpblk != (_mem_blk_ptr)0) {
  962.                                     if (tmpblk->next == blk) {
  963.                                         tmpblk->next = next = blk->next;
  964.                                         break;
  965.                                     } else
  966.                                         tmpblk = tmpblk->next;
  967.                                 }
  968.                                 if (tmpblk == (_mem_blk_ptr)0)
  969.                                     DPRINTF(1, ("pool_find_free_blk() ERROR: could not free blk x%lx from list!\n", blk));
  970.                             }
  971.                             
  972.                             DPRINTF(3, ("pool_find_free_blk() Freeing Block x%lx from pool #%d!\n",
  973.                                         blk, blk->pool->id));
  974. #ifdef _PM_STATS
  975.                             pool->total_memory -= sizeof(_mem_blk) + blk->size;
  976.                             pool->total_storage -= blk->size;
  977. #endif
  978.                             mDISPOSPTR((Ptr)blk->memory);
  979.                             mDISPOSPTR((Ptr)blk);
  980.                             blk = next;
  981.                             break;    /* The while (hdr) loop, into while (blk) loop */
  982.                         }
  983.                     }    /* if (IS_PTR_FREE(blkhdr)) */
  984. #endif _PM_DYNAMIC_FREE
  985.  
  986.                 }
  987. #endif _PM_DYNAMIC_MERGING
  988.  
  989.             }
  990. #ifdef _PM_DYNAMIC_MERGING
  991.             lasthdr = loophdr;
  992. #endif _PM_DYNAMIC_MERGING
  993.             loophdr = (_mem_ptr_hdr_ptr)
  994.                         ((char *)loophdr + GET_PTR_SIZE(loophdr) + sizeof(_mem_ptr_hdr));
  995.         }
  996.     }
  997.     
  998.     *hdr_ptr = (_mem_ptr_hdr_ptr)0;
  999.     return blk;
  1000. }
  1001.     
  1002.  
  1003. #ifdef DOCUMENTATION
  1004.  
  1005.     _pool_find_ptr_blk() finds the block containing this pointer in "ptr".
  1006.     
  1007. #endif
  1008.  
  1009. _mem_bucket_ptr _pool_find_ptr_bucket(char * ptr)
  1010. {
  1011.     _mem_pool_ptr        pool;
  1012.     _mem_bucket_ptr    bucket;
  1013.  
  1014.     /*
  1015.     ** Since the default list is stored at the front of the forest list,
  1016.     ** we inherently search the default forest first. Nice.
  1017.     */
  1018.     pool = _mem_pool_forest;
  1019.     
  1020.     while (pool != (_mem_pool_ptr)0) {
  1021.         if (bucket = pool->free_16)
  1022.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size) {
  1023.                 if (bucket->free_count+1 == bucket->max_count)
  1024.                     pool->free_16 = nil;
  1025.                 return bucket;
  1026.             }
  1027.         if (bucket = pool->free_32)
  1028.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size)    {
  1029.                 if (bucket->free_count+1 == bucket->max_count)
  1030.                     pool->free_32 = nil;
  1031.                 return bucket;
  1032.             }
  1033.         if (bucket = pool->free_64)
  1034.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size) {
  1035.                 if (bucket->free_count+1 == bucket->max_count)
  1036.                     pool->free_64 = nil;
  1037.                 return bucket;
  1038.             }
  1039.         
  1040.         for (bucket = pool->blk_16; bucket; bucket = bucket->next)
  1041.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size)
  1042.                 return bucket;
  1043.         for (bucket = pool->blk_32; bucket; bucket = bucket->next)
  1044.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size)
  1045.                 return bucket;
  1046.         for (bucket = pool->blk_64; bucket; bucket = bucket->next)
  1047.             if (ptr > bucket->memory && ptr < bucket->memory + pool->pref_blk_size)
  1048.                 return bucket;
  1049.         
  1050.         pool = pool->next;
  1051.     }
  1052.     
  1053.     return (_mem_bucket_ptr)0;
  1054. }
  1055.  
  1056. _mem_blk_ptr _pool_find_ptr_blk(char    * ptr)
  1057. {
  1058.     _mem_pool_ptr    pool;
  1059.     _mem_blk_ptr    blk;
  1060.  
  1061.     /*
  1062.     ** Since the default list is stored at the front of the forest list,
  1063.     ** we inherently search the default forest first. Nice.
  1064.     */
  1065.     pool = _mem_pool_forest;
  1066.     
  1067.     while (pool != (_mem_pool_ptr)0) {
  1068.         blk = pool->blk_list;
  1069.         
  1070.         while (blk != (_mem_blk_ptr)0) {
  1071.             if ( ( ptr >= blk->memory ) &&
  1072.                  ( ptr <= ((char *)blk->memory + blk->size) ) )
  1073.                 return blk;
  1074.             else
  1075.                 blk = blk->next;
  1076.         }
  1077.         
  1078.         pool = pool->next;
  1079.     }
  1080.     
  1081.     return (_mem_blk_ptr)0;
  1082. }
  1083.  
  1084.  
  1085. #ifdef DOCUMENTATION
  1086.  
  1087.     merge_free_list() runs the routine to merge and "release" any free-ed
  1088.     blocks back into the heap.
  1089.     
  1090. #endif
  1091.  
  1092. static int _pool_free_list_merge(_mem_pool_ptr pool);
  1093.  
  1094. int merge_free_list()
  1095. {
  1096.     return _pool_free_list_merge(_default_mem_pool);
  1097. }
  1098.  
  1099. #ifdef DOCUMENTATION
  1100.  
  1101.     _pool_free_list_merge() will merge and "release" any free-ed blocks
  1102.     back into the heap.
  1103.     
  1104. #endif
  1105.  
  1106. int _pool_free_list_merge(_mem_pool_ptr pool)
  1107. {
  1108.     _mem_blk_ptr        blk, nextblk;
  1109.     _mem_ptr_hdr_ptr    loophdr, limit, nexthdr, blkhdr;
  1110.     int                    result = 0;
  1111.     long                hdrsize, nextsize;
  1112.  
  1113.     blk = pool->blk_list;
  1114.     while (blk != (_mem_blk_ptr)0) {
  1115.         loophdr = blkhdr = (_mem_ptr_hdr_ptr)blk->memory;
  1116.         limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  1117.         while (loophdr < limit) {
  1118.             if (IS_PTR_FREE(loophdr)) {
  1119.                 hdrsize = GET_PTR_SIZE(loophdr);
  1120.                 nexthdr = (_mem_ptr_hdr_ptr)
  1121.                             ( (char *)loophdr + hdrsize + sizeof(_mem_ptr_hdr) );
  1122.                 /* Now loop and merge free ptr's til used one is hit... */
  1123.                 while (nexthdr < limit) {
  1124.                     if (IS_PTR_FREE(nexthdr)) {
  1125.                         nextsize = GET_PTR_SIZE(nexthdr);
  1126.                         blk->max_free += sizeof(_mem_ptr_hdr);    /* We're gonna merge... */
  1127.                         hdrsize = nextsize + hdrsize + sizeof(_mem_ptr_hdr);
  1128.                         SET_PTR_SIZE(loophdr, hdrsize);
  1129.                         nexthdr = (_mem_ptr_hdr_ptr)
  1130.                                     ( (char *)loophdr + hdrsize + sizeof(_mem_ptr_hdr) );
  1131.                     } else
  1132.                         break;
  1133.                 }
  1134.             }
  1135.             
  1136.             loophdr = (_mem_ptr_hdr_ptr)
  1137.                         ((char *)loophdr + GET_PTR_SIZE(loophdr) + sizeof(_mem_ptr_hdr));
  1138.         }
  1139.  
  1140.         /* Get next block now, so _PM_DYNAMIC_FREE can modify blk as desired */
  1141.         nextblk = blk->next;
  1142.  
  1143. #ifdef _PM_DYNAMIC_FREE
  1144.         if (IS_PTR_FREE(blkhdr)) {
  1145.             if ((GET_PTR_SIZE(blkhdr) + sizeof(_mem_ptr_hdr)) == blk->size) {
  1146.                 /* This blk is free-ed ... */
  1147.                 _mem_blk_ptr    tmpblk;
  1148.  
  1149.                 if (blk == blk->pool->blk_list) {
  1150.                     blk->pool->blk_list = blk->next;
  1151.                 } else {
  1152.                     tmpblk = blk->pool->blk_list;
  1153.                     while (tmpblk != (_mem_blk_ptr)0) {
  1154.                         if (tmpblk->next == blk) {
  1155.                             tmpblk->next = blk->next;
  1156.                             break;
  1157.                         } else
  1158.                             tmpblk = tmpblk->next;
  1159.                     }
  1160.                     if (tmpblk == (_mem_blk_ptr)0)
  1161.                         DPRINTF(1, ("pool_find_free_blk() ERROR: could not free blk x%lx from list!\n", blk));
  1162.                 }
  1163.                 
  1164.                 DPRINTF(3, ("pool_find_free_blk() Freeing Block x%lx from pool #%d!\n",
  1165.                             blk, blk->pool->id));
  1166. #ifdef _PM_STATS
  1167.                 pool->total_memory -= sizeof(_mem_blk) + blk->size;
  1168.                 pool->total_storage -= blk->size;
  1169. #endif
  1170.                 result += blk->size + sizeof(_mem_blk);
  1171.                 mDISPOSPTR((Ptr)blk->memory);
  1172.                 mDISPOSPTR((Ptr)blk);
  1173.             }
  1174.             
  1175.         }    /* if (IS_PTR_FREE(blkhdr)) */
  1176. #endif _PM_DYNAMIC_FREE
  1177.         
  1178.         blk = nextblk;
  1179.     }
  1180.     
  1181.     return result;
  1182. }
  1183.     
  1184.  
  1185. #ifdef DOCUMENTATION
  1186.  
  1187.     get_malloc_stats() return several statistics about the default heap.
  1188.     
  1189. #endif
  1190.  
  1191. void get_malloc_stats(long * total_memory, long * total_free, long * total_malloc)
  1192. {
  1193.     _mem_pool_ptr        pool;
  1194.     _mem_blk_ptr        blk;
  1195.     _mem_ptr_hdr_ptr    hdr, limit;
  1196.     u_long                total_size, used_space, free_space;
  1197.     u_long                ptr_size;
  1198.  
  1199.     pool = _default_mem_pool;
  1200.     blk = pool->blk_list;
  1201.     total_size = used_space = free_space = 0;
  1202.     for ( ; blk != (_mem_blk_ptr)0; ) {
  1203.         hdr = (_mem_ptr_hdr_ptr) blk->memory;
  1204.         limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  1205.         total_size += blk->size;
  1206.         for ( ; hdr && hdr < limit; ) {
  1207.             ptr_size = GET_PTR_SIZE(hdr);
  1208.             if (IS_PTR_FREE(hdr))
  1209.                 free_space += ptr_size;
  1210.             else
  1211.                 used_space += ptr_size;
  1212.             
  1213.             hdr = (_mem_ptr_hdr_ptr)
  1214.                     ( (char *)hdr + GET_PTR_SIZE(hdr) + sizeof(_mem_ptr_hdr) );
  1215.         }
  1216.         
  1217.         blk = blk->next;
  1218.     }
  1219.     
  1220.     *total_memory = total_size;
  1221.     *total_free = free_space;
  1222.     *total_malloc = used_space;
  1223. }
  1224.  
  1225. #ifdef DEBUG
  1226.  
  1227. #include <stdio.h>
  1228.  
  1229. char    temp_str[512];
  1230.  
  1231. list_all_pool_stats(file)
  1232. FILE    *file;
  1233. {
  1234. _mem_pool_ptr        pool;
  1235.  
  1236.     pool = _mem_pool_forest;
  1237.     
  1238.     while (pool != (_mem_pool_ptr)0) {
  1239.         
  1240.         list_pool_stats(file, pool);
  1241.  
  1242.         pool = pool->next;
  1243.         }
  1244.     
  1245.     }
  1246.  
  1247.  
  1248. list_pool_stats(file, pool)
  1249. FILE    *file;
  1250. _mem_pool_ptr        pool;
  1251. {
  1252. _mem_blk_ptr        blk;
  1253. _mem_ptr_hdr_ptr    hdr, limit;
  1254. int                    i, j;
  1255. int                    num_used_hdrs, num_free_hdrs;
  1256. u_long                used_hdr_space, free_hdr_space;
  1257. u_long                ptr_size, max_free_size, max_used_size;
  1258. float                ave_used_size, ave_free_size, frag_ratio;
  1259.  
  1260.     if (file == (FILE *)0) {
  1261.         file = stdout;
  1262.         }
  1263.     
  1264.     fprintf(file, "POOL STATISTICS FOR ID#%d @ x%lx blk_list x%lx pref_blk_size %ld\n",
  1265.             pool->id, pool, pool->blk_list, pool->pref_blk_size);
  1266.  
  1267. #ifdef _PM_STATS
  1268.     fprintf(file, "\tMEMORY: Total memory %ld Total ptr space %ld Currently malloc-ed %ld\n",
  1269.             pool->total_memory, pool->total_storage, pool->total_malloc);
  1270.     fprintf(file, "\tREQUESTS: Ave req size %f Total reqs %ld Total size reqs %f\n",
  1271.             pool->ave_req_size, pool->ave_req_total, 
  1272.             (float) (pool->ave_req_size * (float)pool->ave_req_total));
  1273.     fprintf(file, "\tBLOCKS: Max block size %ld Ave block size %f\n",
  1274.             pool->max_blk_size, pool->ave_blk_size);
  1275.     fprintf(file, "\tBLOCKS: Total ave blocks %ld Total ave size %f\n",
  1276.             pool->ave_blk_total,(float) (pool->ave_blk_size * (float)pool->ave_blk_total));
  1277. #endif
  1278.  
  1279.         fprintf(file, "POOL BLOCK STATISTICS:\n");
  1280.         
  1281.         blk = pool->blk_list;
  1282.         for (i=0; blk != (_mem_blk_ptr)0; i++) {
  1283.             hdr = (_mem_ptr_hdr_ptr) blk->memory;
  1284.             limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  1285.             num_used_hdrs = num_free_hdrs = 0;
  1286.             used_hdr_space = free_hdr_space = 0;
  1287.             max_free_size = max_used_size = 0;
  1288.             for (j=0; hdr && hdr < limit; j++) {
  1289.                 ptr_size = GET_PTR_SIZE(hdr);
  1290.                 if (IS_PTR_FREE(hdr)) {
  1291.                     num_free_hdrs++;
  1292.                     free_hdr_space += ptr_size;
  1293.                     if (ptr_size > max_free_size)
  1294.                         max_free_size = ptr_size;
  1295.                     }
  1296.                 else {
  1297.                     num_used_hdrs++;
  1298.                     used_hdr_space += ptr_size;
  1299.                     if (ptr_size > max_used_size)
  1300.                         max_used_size = ptr_size;
  1301.                     }
  1302.                 
  1303.                 hdr = (_mem_ptr_hdr_ptr)
  1304.                         ( (char *)hdr + GET_PTR_SIZE(hdr) + sizeof(_mem_ptr_hdr) );
  1305.                 }
  1306.             
  1307.             if (num_free_hdrs == 0)
  1308.                 ave_free_size = (float)0.0;
  1309.             else
  1310.                 ave_free_size = (float)free_hdr_space / (float)num_free_hdrs;
  1311.             
  1312.             if (num_used_hdrs == 0)
  1313.                 ave_used_size = (float)0.0;
  1314.             else
  1315.                 ave_used_size = (float)used_hdr_space / (float)num_used_hdrs;
  1316.             
  1317.             if (num_used_hdrs == 0) {
  1318.                 frag_ratio = (float)num_free_hdrs / 2.0;
  1319.                 }
  1320.             else {
  1321.                 frag_ratio = (float)num_free_hdrs / (float)num_used_hdrs;
  1322.                 }
  1323.             
  1324.             fprintf(file, "\tBLOCK #%-4d Fragmentation Ratio %5.2f\n", i, frag_ratio);
  1325.             fprintf(file, "\t      #%-4d    Block Size %ld Ptr x%lx MaxFree %ld\n",
  1326.                     i, blk->size, blk->memory, blk->max_free);
  1327.             fprintf(file, "\t      #%-4d    Number free ptrs %d Number used ptrs %d\n",
  1328.                     i, num_free_hdrs, num_used_hdrs);
  1329.             fprintf(file, "\t      #%-4d    Free space %ld Used space %ld\n",
  1330.                     i, free_hdr_space, used_hdr_space);
  1331.             fprintf(file, "\t      #%-4d    Max free ptr %ld Max used ptr %ld\n",
  1332.                     i, max_free_size, max_used_size);
  1333.             fprintf(file, "\t      #%-4d    Ave free ptr size %5.1f Ave used ptr size %5.1f\n",
  1334.                     i, ave_free_size, ave_used_size);
  1335.  
  1336.             blk = blk->next;
  1337.             }
  1338.     }
  1339.  
  1340.  
  1341. list_pool_forest(file, with_data)
  1342. FILE    *file;
  1343. int        with_data;
  1344. {
  1345. _mem_pool_ptr        pool;
  1346. _mem_blk_ptr        blk;
  1347. _mem_ptr_hdr_ptr    hdr, limit;
  1348. int                    i, j;
  1349. extern char            temp_str[];
  1350.  
  1351.     if (file == (FILE *)0) {
  1352.         file = stdout;
  1353.         }
  1354.     
  1355.     pool = _mem_pool_forest;
  1356.     while (pool != (_mem_pool_ptr)0) {
  1357.         
  1358.         list_pool_stats(file, pool);
  1359.         
  1360.         blk = pool->blk_list;
  1361.         for (i=0; blk != (_mem_blk_ptr)0; i++) {
  1362.             fprintf(file, "   BLK #%05d ; @ x%lx ; blk_size %ld ; memory x%lx ; max_free %ld\n",
  1363.                     i, blk, blk->size, blk->memory, blk->max_free);
  1364.             fprintf(file, "   BLK          pool x%lx ; next blk x%lx\n", blk->pool, blk->next);
  1365.             
  1366.             hdr = (_mem_ptr_hdr_ptr) blk->memory;
  1367.             limit = (_mem_ptr_hdr_ptr) ((char *)blk->memory + blk->size);
  1368.             for (j=0; hdr && hdr < limit; j++) {
  1369.                 sprintf(temp_str, "      PTR #%d ; hdr x%lx ; nxt x%08lx ; size %ld ; flgs x%02x",
  1370.                         j, hdr, hdr->size, GET_PTR_SIZE(hdr), GET_PTR_FLAGS(hdr));
  1371.                 if (with_data)
  1372.                     hex_dump(file, temp_str,
  1373.                             (char *)((char *)hdr + sizeof(_mem_ptr_hdr)),
  1374.                             GET_PTR_SIZE(hdr));
  1375.                 else
  1376.                     fprintf(file, "%s\n", temp_str);
  1377.                 
  1378.                 hdr = (_mem_ptr_hdr_ptr)
  1379.                         ( (char *)hdr + GET_PTR_SIZE(hdr) + sizeof(_mem_ptr_hdr) );
  1380.                 }
  1381.             
  1382.             blk = blk->next;
  1383.             }
  1384.         
  1385.         pool = pool->next;
  1386.         }
  1387.     }
  1388.  
  1389. #define ROW_BYTES        16
  1390.  
  1391. hex_dump(output, title, ptr, bytes)
  1392. FILE    *output;
  1393. char    *title;
  1394. char    *ptr;
  1395. long    bytes;
  1396. {
  1397. int                rows, residue, i, j;
  1398. unsigned char    save_buf[ROW_BYTES+2];
  1399. unsigned char    hex_buf[4];
  1400. char            hex_chars[20];
  1401.     strcpy(hex_chars, "0123456789ABCDEF");
  1402.     
  1403.     fprintf(output, "\n%s - x%lX (%ld) bytes.\n", title, bytes, bytes);
  1404.     rows = bytes >> 4;
  1405.     residue = bytes & 0x0000000F;
  1406.     for (i=0; i<rows; i++) {
  1407.         fprintf(output, "%04.4X:", i * ROW_BYTES);
  1408.         for (j=0; j<ROW_BYTES; j++) {
  1409.             save_buf[j] = *ptr++;
  1410.             hex_buf[0] = hex_chars[(save_buf[j] >> 4) & 0x0F];
  1411.             hex_buf[1] = hex_chars[save_buf[j] & 0x0F];
  1412.             hex_buf[2] = '\0';
  1413.             fprintf(output, " %2.2s", hex_buf);
  1414.             if (save_buf[j] < 0x20 || save_buf[j] > 0xD9) save_buf[j] = '.';
  1415.             }
  1416.         save_buf[ROW_BYTES+1] = '\0';
  1417.         fprintf(output, "\t/* %16.16s */\n", save_buf);
  1418.         }
  1419.     if (residue) {
  1420.         fprintf(output, "%04.4X:", i * ROW_BYTES);
  1421.         for (j=0; j<residue; j++) {
  1422.             save_buf[j] = *ptr++;
  1423.             hex_buf[0] = hex_chars[(save_buf[j] >> 4) & 0x0F];
  1424.             hex_buf[1] = hex_chars[save_buf[j] & 0x0F];
  1425.             hex_buf[2] = '\0';
  1426.             fprintf(output, " %2.2s", hex_buf);
  1427.             if (save_buf[j] < 0x20 || save_buf[j] > 0xD9) save_buf[j] = '.';
  1428.             }
  1429.         for (/*j INHERITED*/; j<ROW_BYTES; j++) {
  1430.             save_buf[j] = ' ';
  1431.             fprintf(output, "   ");
  1432.             }
  1433.         save_buf[ROW_BYTES+1] = '\0';
  1434.         fprintf(output, "\t/* %16.16s */\n", save_buf);
  1435.         }
  1436.     }
  1437.  
  1438. #ifdef TESTING
  1439.  
  1440. main(argc, argv)
  1441. char    *argc;
  1442. char    *argv[];
  1443. {
  1444. int        i;
  1445. _mem_pool_ptr pool;
  1446. char    *ptr, *aptr[20];
  1447. char    input[128];
  1448. #pragma unused (argc, argv)
  1449.  
  1450.     printf("Debug level?\n");
  1451.     gets(input);
  1452.     if (input[0] == '\0' || input[0] == 'q')
  1453.         return 0;
  1454.     
  1455.     pool_malloc_debug_level = atoi(input);
  1456.     printf("Debug level set to %d\n", pool_malloc_debug_level);
  1457.     
  1458.     fprintf(stderr, "******************** START ********************\n");
  1459.     list_pool_forest(stderr, 0);
  1460.     
  1461.     printf("Allocating in default (system) pool...\n");
  1462.     for (i = 10 ; i < (10 * 1024) ; i += 128)
  1463.         if (malloc(i) == NULL)
  1464.             break;
  1465.     
  1466.     fprintf(stderr, "******************** ## 1 ## ********************\n");
  1467.     list_pool_forest(stderr, 0);
  1468.     
  1469.     printf("Allocating and Free-ing in default (system) pool...\n");
  1470.     for (i = 10 ; i < (10 * 1024) ; i += 128)
  1471.         if ((ptr = malloc(i)) != NULL)
  1472.             free(ptr);
  1473.         else
  1474.             break;
  1475.         
  1476.     fprintf(stderr, "******************** ## 2 ## ********************\n");
  1477.     list_pool_forest(stderr, 0);
  1478.     
  1479.     printf("Allocating and Free-ing again in default (system) pool...\n");
  1480.     for (i = 0 ; i < 20 ; i++)
  1481.         aptr[i] = NULL;
  1482.     for (i = 0 ; i < 20 ; i++) {
  1483.         aptr[i] = malloc(i * 128);
  1484.         if (aptr[i] == NULL)
  1485.             break;
  1486.         }
  1487.     for (i = 19 ; i >= 0 ; i--)
  1488.         if (aptr[i] != NULL) {
  1489.             free(aptr[i]);
  1490.             }
  1491.         
  1492.     fprintf(stderr, "******************** ## 3 ## ********************\n");
  1493.     list_pool_forest(stderr, 0);
  1494.     
  1495.     pool = new_malloc_pool ( 2001, (16 * 1024) );
  1496.     printf("new_malloc_pool ( 2001, %d ) returns x%lx\n", (16 * 1024), pool);
  1497.     if (pool) {
  1498.         set_default_pool ( 2001 );
  1499.         
  1500.         printf("Allocating in pool #2001...\n");
  1501.         for (i = 10 ; i < (10 * 1024) ; i += 128)
  1502.             if (malloc(i) == NULL)
  1503.                 break;
  1504.         }
  1505.  
  1506.     fprintf(stderr, "******************** ## 4 ## ********************\n");
  1507.     list_pool_forest(stderr, 0);
  1508.     
  1509.     printf("Free-ing memory in pool #2001...\n");
  1510.     free_pool_memory ( 2001 );
  1511.  
  1512.     fprintf(stderr, "******************** ## 5 ## ********************\n");
  1513.     list_pool_forest(stderr, 0);
  1514.     
  1515.     printf("Done.\n");
  1516.     }
  1517.  
  1518. #endif TESTING
  1519.  
  1520. #endif _PM_STATS
  1521.