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