home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / mac / MacMemoryAllocator / src / MemoryTracker.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  30.6 KB  |  1,390 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  2.  *
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  *
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  *
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. #include <assert.h>
  20. #include <stdio.h>
  21. #include <string.h>
  22. #include <Types.h>
  23. #include <Files.h>
  24. #include <Gestalt.h>
  25. #include <Processes.h>
  26.  
  27. #include "TypesAndSwitches.h"
  28. #include "MemoryTracker.h"
  29. #include "prthread.h"
  30.  
  31.  
  32. /*
  33.  * These should all be runtime options.
  34.  */
  35. #define    LOG_ALL_OPEN_SETS        1
  36. //#define    LOG_SITE_LEAKS_ONLY        1
  37.  
  38. /*
  39.  * Considering that this is meant to help us reduce memory consumption, my use of memory
  40.  * here is pretty appalling. However, I think optimizations here are only worth the time
  41.  * if they're needed. The most important thing is to get this working quickly and start
  42.  * using it. Then I'll come back and fix this other stuff up.
  43.  */
  44.  
  45. #define    kNumBlocksTracked            100000
  46. #define    kBlockAllocationLongs        (( kNumBlocksTracked + 31 ) >> 5 )
  47. #define    kHashMod                    1091
  48. #define    kNumAllocationSites            30000
  49. #define    kNumAllocationSets            20
  50. #define    kMaxInstructionScanDistance    4096
  51. #define    kInvalidIndex                0xFFFFFFFF
  52.  
  53.  
  54. /*
  55.  * Hash Table crap
  56.  */
  57. typedef struct HashBlock HashBlock;
  58. typedef struct HashTable HashTable;
  59. typedef struct AllocationSite AllocationSite;
  60.  
  61. typedef unsigned long (*HashFunction)( void * key );
  62. typedef Boolean (*HashCompare) ( void * key1, void *key2 );
  63.  
  64.  
  65. struct HashBlock {
  66.     struct HashBlock *    next;
  67.     char                key[];
  68. };
  69.  
  70. struct HashTable {
  71.     HashFunction    hashFunction;
  72.     HashCompare        compareFunction;
  73.     HashBlock *        index[ kHashMod ];
  74. };
  75.  
  76.  
  77. static void HashInitialize ( HashTable * table, HashFunction hash, HashCompare compare );
  78. static HashBlock * HashFind ( HashTable * table, void * key );
  79. static void HashInsert ( HashTable * table, HashBlock * block );
  80. static void HashRemove ( HashTable * table, HashBlock * block );
  81.  
  82.  
  83.  
  84. typedef struct Block {
  85.     unsigned long        blockNum;
  86.     unsigned long        blockID;
  87.     unsigned long        blockSize;
  88.     void *                blockAddress;
  89.     AllocationSite *    site;
  90.     unsigned char        allocType;
  91.     unsigned char        blockState;
  92.     unsigned char        refCount;
  93.     unsigned char        overhead;
  94.     struct Block *        next;
  95. } Block;
  96.  
  97. struct AllocationSet {
  98.     unsigned long    numBlocks;
  99.     unsigned long    totalAllocation;
  100.     unsigned long    currentAllocation;
  101.     unsigned long    maxAllocation;
  102.     unsigned long    blockSet[ kBlockAllocationLongs ];
  103.     unsigned char    inUse;
  104.     unsigned char    enabledState;
  105.     char            name[ 256 ];
  106. };
  107.  
  108. typedef Block * Bucket;
  109.  
  110. struct AllocationSite {
  111.     AllocationSite *    next;
  112.     void *                stackCrawl[ kStackDepth ];
  113.     unsigned long        siteIndex;
  114.     unsigned long        currentBlocks;
  115.     unsigned long        currentMemUsed;
  116.     unsigned long        maxMemUsed;
  117.     unsigned long        totalBlocks;
  118.     unsigned long        totalMemUsed;
  119. };
  120.  
  121.  
  122. pascal void TrackerExitToShellPatch(void);
  123. asm void * GetCurrentStackPointer();
  124.  
  125. #if DEBUG_MAC_MEMORY
  126. Block                gBlockPool[ kNumBlocksTracked ];
  127. Block *                gFreeBlocks;
  128. Block *                gBlockIndex[ kHashMod ];
  129. unsigned long        gIndexSize;
  130. unsigned long        gBlockNumber;
  131. unsigned long        gNumActiveTrackerBlocks;
  132. unsigned long        gNumHeapBlocks;
  133. unsigned long        gMaxNumHeapBlocks;
  134. unsigned long        gNumAllocations;
  135. AllocationSite        gAllocationSites[ kNumAllocationSites ];
  136. unsigned long        gAllocationSitesUsed;
  137. HashTable            gSiteTable;
  138. AllocationSet        gAllocationSetPool[ kNumAllocationSets ];
  139. unsigned char        gTrackerInitialized = false;
  140. Boolean                gNeverInitialized = true;
  141. unsigned long        gTrackerEnableState = 0;
  142.  
  143. static void *        gMemoryTop;
  144. static short        gLogFile = 0;
  145.  
  146.  
  147. UniversalProcPtr    gExitToShellPatchCallThru = NULL;
  148. #if GENERATINGCFM
  149. enum {
  150.     uppExitToShellProcInfo                 = kPascalStackBased
  151. };
  152.  
  153. RoutineDescriptor     gExitToShellPatchRD = BUILD_ROUTINE_DESCRIPTOR(uppExitToShellProcInfo, &TrackerExitToShellPatch);
  154. #else
  155. #define gExitToShellPatchRD ExitToShellPatch
  156. #endif
  157. #endif
  158.  
  159. void        *        gOurApplicationHeapBase;
  160. void        *        gOurApplicationHeapMax;
  161.  
  162.  
  163. static Block * AllocateBlockFromPool ( void );
  164. static void FreeBlockFromPool ( Block * block );
  165. static Block * FindBlock ( void * address );
  166. static void InsertBlock ( Block * block );
  167. static void RemoveBlock ( Block * block );
  168. static Block * FindBlockBucket ( void * address, Bucket ** bucket );
  169. static void AddBlockReference ( Block * block );
  170. static void RemoveBlockReference ( Block * block );
  171. static void CatenateRoutineNameFromPC( char * string, void *currentPC );
  172. static void PrintHexNumber( char * string, UInt32 hexNumber );
  173. static void PrintStackCrawl ( char * name, void ** stackCrawl );
  174.  
  175. static void AddNewBlockToAllocationSet ( AllocationSet * set, Block * block );
  176. static void MarkBlockFreeFromSet ( AllocationSet * set, Block * block );
  177. static void BlockFreedFromSite ( AllocationSite * site, unsigned long blockSize );
  178.  
  179.  
  180. static unsigned long AllocationSiteHash( void ** stackCrawl );
  181. static Boolean AllocationSiteHashCompare ( void ** site1, void ** site2 );
  182.  
  183. void InitializeMemoryTracker ( void )
  184. {
  185. #if DEBUG_MAC_MEMORY
  186.     unsigned long        count;
  187.     unsigned long        blockCount;
  188.     AllocationSet *        set;
  189.     Block *                block;
  190.     Block **            blockIndex;
  191.     OSErr                err;
  192.     ProcessSerialNumber    thisProcess = { 0, kCurrentProcess };
  193.     ProcessInfoRec        processInfo;
  194.  
  195.     processInfo.processInfoLength = sizeof(processInfo);
  196.     processInfo.processName = NULL;
  197.     processInfo.processAppSpec = NULL;
  198.  
  199.     GetProcessInformation(&thisProcess, &processInfo);
  200.  
  201.     gOurApplicationHeapBase = processInfo.processLocation;
  202.     gOurApplicationHeapMax = (Ptr)gOurApplicationHeapBase + processInfo.processSize;
  203.  
  204.     err = Gestalt ( gestaltLogicalRAMSize, (long *) &gMemoryTop );
  205.     if ( err != noErr )
  206.         {
  207.         DebugStr ( "\pThis machine has no logical ram?" );
  208.         ExitToShell();
  209.         }
  210.  
  211.     /* do any one time init */
  212.     if ( gNeverInitialized )
  213.         {
  214.         gNeverInitialized = false;
  215.         gExitToShellPatchCallThru = GetToolboxTrapAddress(0x01F4);
  216.         SetToolboxTrapAddress((UniversalProcPtr)&gExitToShellPatchRD, 0x01F4);
  217.         }
  218.                 
  219.     /* Be sure to dispose of ourselves if already allocated */
  220.     if ( gTrackerInitialized != false )
  221.         {
  222.         ExitMemoryTracker();
  223.         }
  224.         
  225.     gBlockNumber = 0;
  226.     gNumActiveTrackerBlocks = 0;
  227.     gNumHeapBlocks = 0;
  228.     gMaxNumHeapBlocks = 0;
  229.     gNumAllocations = 0;
  230.     gAllocationSitesUsed = 0;
  231.     gIndexSize = 0;
  232.     
  233.     FSDelete ( "\pMemoryLog.bin", 0 );
  234.     Create ( "\pMemoryLog.bin", 0, 'shan', 'binl' );
  235.     err = FSOpen ( "\pMemoryLog.bin", 0, &gLogFile );
  236.     if ( err != noErr )
  237.         {
  238.         gLogFile = 0;
  239.         }
  240.     
  241.     block = gBlockPool;
  242.     gFreeBlocks = NULL;
  243.     
  244.     for ( count = 0; count < kNumBlocksTracked; ++count )
  245.         {
  246.         block->refCount = 0;
  247.         block->blockAddress = NULL;
  248.         block->blockID = count;
  249.         block->next = gFreeBlocks;
  250.         gFreeBlocks = block;
  251.         
  252.         ++block;
  253.         }
  254.         
  255.     blockIndex = gBlockIndex;
  256.  
  257.     for ( count = 0; count < kHashMod; ++count )
  258.         {
  259.         *blockIndex++ = NULL;
  260.         }    
  261.         
  262.     set = gAllocationSetPool;
  263.     
  264.     for ( count = 0; count < kNumAllocationSets; ++count )
  265.         {
  266.         set->inUse = false;
  267.         
  268.         for ( blockCount = 0; blockCount < kBlockAllocationLongs; ++blockCount )
  269.             {
  270.             set->blockSet[ blockCount ] = 0;
  271.             }
  272.         
  273.         ++set;
  274.         }
  275.     
  276.     HashInitialize ( &gSiteTable, (HashFunction) &AllocationSiteHash,
  277.         (HashCompare) AllocationSiteHashCompare );
  278.         
  279.     gTrackerInitialized = true;
  280.     gTrackerEnableState = 0;
  281.     
  282.     NewAllocationSet ( 0, "InitializeMemoryTracker" );
  283. #endif
  284. }
  285.  
  286.  
  287. void ExitMemoryTracker ( void )
  288. {
  289. #if DEBUG_MAC_MEMORY
  290.     gTrackerInitialized = false;
  291.     
  292.     if ( gLogFile != NULL )
  293.         {
  294.         FSClose ( gLogFile );
  295.         gLogFile = 0;
  296.         }
  297. #endif
  298. }
  299.  
  300.  
  301. void DisableMemoryTracker ( void )
  302. {
  303. #if DEBUG_MAC_MEMORY
  304.     ++gTrackerEnableState;
  305. #endif
  306. }
  307.  
  308.  
  309. void EnableMemoryTracker ( void )
  310. {
  311. #if DEBUG_MAC_MEMORY
  312.     if ( gTrackerEnableState > 0 )
  313.         {
  314.         --gTrackerEnableState;
  315.         }
  316. #endif
  317. }
  318.  
  319.  
  320. void DumpMemoryTrackerState ( void )
  321. {
  322. #if DEBUG_MAC_MEMORY
  323.     unsigned long        count;
  324.     
  325.     printf ( "Number of tracker blocks in use: %ld\n", gNumActiveTrackerBlocks );
  326.     printf ( "Number of heap blocks in use: %ld\n", gNumHeapBlocks );
  327.     printf ( "Max Number of heap blocks in use: %ld\n", gMaxNumHeapBlocks );
  328.     printf ( "Total number of allcations %ld\n", gNumAllocations );
  329.  
  330. #if LOG_ALL_OPEN_SETS    
  331.     /* Log all active allocation sets */
  332.     for ( count = 0; count < kNumAllocationSets; ++count )
  333.         {
  334.         if ( gAllocationSetPool[ count ].inUse == true )
  335.             {
  336.             LogAllocationSetState ( &gAllocationSetPool[ count ] );
  337.             }
  338.         }
  339. #endif
  340.     
  341.     DumpAllocationSites();
  342. #endif
  343. }
  344.  
  345.  
  346. void DumpAllocationSites ( void )
  347. {
  348. #if DEBUG_MAC_MEMORY
  349.     unsigned long            count;
  350.     AllocationSite *        site;
  351.     AllocationSiteLogEntry    logEntry;
  352.     AllocationSiteLog        logHeader;
  353.     long                    size;
  354.     OSErr                    err;
  355.     
  356.     if ( gLogFile != NULL )
  357.         {
  358.         logHeader.header.logTag = kALLOCATION_SITE_LIST;
  359.         logHeader.header.logSize = sizeof(AllocationSiteLog) +
  360.             ( gAllocationSitesUsed * sizeof(AllocationSiteLogEntry) );
  361.         logHeader.numEntries = gAllocationSitesUsed;
  362.         
  363.         size = sizeof(logHeader);
  364.         err = FSWrite ( gLogFile, &size, &logHeader );
  365.         if ( err != noErr )
  366.             {
  367.             DebugStr ( "\pWrite failed" );
  368.             return;
  369.             }
  370.         
  371.         for ( count = 0; count < gAllocationSitesUsed; ++count )
  372.             {
  373.             site = &gAllocationSites[ count ];
  374.  
  375.             memset( &logEntry, 0, sizeof(logEntry) );
  376.  
  377.             PrintStackCrawl ( logEntry.stackNames, site->stackCrawl );
  378.             
  379.             logEntry.currentBlocks = site->currentBlocks;
  380.             logEntry.currentMemUsed = site->currentMemUsed;
  381.             logEntry.maxMemUsed = site->maxMemUsed;
  382.             logEntry.totalBlocks = site->totalBlocks;
  383.             logEntry.totalMemUsed = site->totalMemUsed;
  384.             
  385.             size = sizeof(logEntry);
  386.             err = FSWrite ( gLogFile, &size, &logEntry );
  387.             if ( err != noErr )
  388.                 {
  389.                 DebugStr ( "\pWrite failed" );
  390.                 return;
  391.                 }
  392.             }
  393.         }
  394. #endif
  395. }
  396.  
  397.  
  398. void AddNewBlock ( void * address, size_t blockSize, size_t overhead, AllocatorType allocType,
  399.     void * stackCrawl )
  400. {
  401. #if DEBUG_MAC_MEMORY
  402.     AllocationSite *    site;
  403.     Block *                block;
  404.     unsigned long        setCount;
  405.     
  406.     ++gNumHeapBlocks;
  407.     ++gNumAllocations;
  408.  
  409.     if ( gNumHeapBlocks > gMaxNumHeapBlocks )
  410.         {
  411.         gMaxNumHeapBlocks = gNumHeapBlocks;
  412.         }
  413.         
  414.     /* tracking a null block will hose us big time */
  415.     if ( ( address == NULL ) || ( gTrackerInitialized == false ) || ( gTrackerEnableState > 0 ) )
  416.         {
  417.         return;
  418.         }
  419.         
  420.     /*
  421.      * Find a free block in our block pool
  422.      */
  423.     block = AllocateBlockFromPool();
  424.     
  425.     /* if we found a block, allocate it */
  426.     if ( block != NULL )
  427.         {
  428.         /* Find the allocation site for this block */
  429.         site = NewAllocationSite ( stackCrawl, blockSize );
  430.         
  431.         block->blockNum = gBlockNumber++;
  432.         block->blockSize = blockSize;
  433.         block->blockAddress = address;
  434.         block->allocType = allocType;
  435.         block->refCount = 0;
  436.         block->overhead = overhead;
  437.         block->blockState = kBlockAllocated;
  438.         block->site = site;
  439.         
  440.         /* insert this block into the block index */
  441.         InsertBlock ( block );
  442.         
  443.         /* add our own reference to this block */
  444.         AddBlockReference ( block );
  445.         
  446.         /* and then add it to all relevant allocation sets */
  447.         for ( setCount = 0; setCount < kNumAllocationSets; ++setCount )
  448.             {
  449.             if ( gAllocationSetPool[ setCount ].inUse == true )
  450.                 {
  451.                 AddNewBlockToAllocationSet ( &gAllocationSetPool[ setCount ], block );
  452.                 }
  453.             }
  454.         }
  455. #else
  456. #pragma unused(address, blockSize, overhead, allocType, stackCrawl)
  457. #endif
  458. }
  459.  
  460.  
  461. void FreeBlock ( void * address )
  462. {
  463. #if DEBUG_MAC_MEMORY
  464.     unsigned long        count;
  465.     Block *                block;
  466.         
  467.     --gNumHeapBlocks;
  468.  
  469.     if ( ( gTrackerInitialized == false ) || ( gTrackerEnableState > 0 ) )
  470.         {
  471.         return;
  472.         }
  473.         
  474.     block = NULL;
  475.     
  476.     block = FindBlockBucket ( address, NULL );
  477.     
  478.     if ( block != NULL )
  479.         {    
  480.         block->blockState = kBlockFree;
  481.  
  482.         BlockFreedFromSite ( block->site, block->blockSize );
  483.         
  484.         /* remove our own reference from this block */
  485.         RemoveBlockReference ( block );
  486.  
  487.         /* remove block from all sets */
  488.         for ( count = 0; count < kNumAllocationSets; ++count )
  489.             {
  490.             if ( gAllocationSetPool[ count ].inUse == true )
  491.                 {
  492.                 MarkBlockFreeFromSet ( &gAllocationSetPool[ count ], block );
  493.                 }
  494.             }
  495.         }
  496.     else
  497.         {
  498. //        DebugStr ( "\pCan't find block?" );
  499.         }
  500. #else
  501. #pragma unused(address)
  502. #endif
  503. }
  504.  
  505. AllocationSite * NewAllocationSite ( void ** stackCrawl, unsigned long blockSize )
  506. {
  507. #if DEBUG_MAC_MEMORY
  508.     AllocationSite *    site;
  509.     unsigned long        stackCount;
  510.  
  511.         site = (AllocationSite *) HashFind ( &gSiteTable, stackCrawl );
  512.         if ( site == NULL )
  513.             {
  514.             if ( gAllocationSitesUsed < kNumAllocationSites )
  515.                 {
  516.                 site = &gAllocationSites[ gAllocationSitesUsed++ ];
  517.                 for ( stackCount = 0; stackCount < kStackDepth; ++stackCount )
  518.                     {
  519.                     site->stackCrawl[ stackCount ] = stackCrawl[ stackCount ];
  520.                     }
  521.  
  522.                 site->siteIndex = gAllocationSitesUsed - 1;
  523.                 site->currentBlocks = 0;
  524.                 site->currentMemUsed = 0;
  525.                 site->maxMemUsed = 0;
  526.                 site->totalBlocks = 0;
  527.                 site->totalMemUsed = 0;
  528.                 }
  529.             else
  530.                 {
  531.     //            DebugStr ( "\pOut of allocation sites..." );
  532.                 }
  533.             
  534.             HashInsert ( &gSiteTable, (HashBlock *) site );
  535.             }
  536.  
  537.     if ( site != NULL )
  538.         {
  539.         ++site->currentBlocks;
  540.         site->currentMemUsed += blockSize;
  541.         if ( site->currentMemUsed > site->maxMemUsed )
  542.             {
  543.             site->maxMemUsed = site->currentMemUsed;
  544.             }
  545.             
  546.         ++site->totalBlocks;
  547.         site->totalMemUsed += blockSize;
  548.         }
  549.         
  550.     return site;
  551. #else
  552. #pragma unused(stackCrawl, blockSize)
  553.     return NULL;
  554. #endif
  555. }
  556.  
  557.  
  558. void BlockFreedFromSite ( AllocationSite * site, unsigned long blockSize )
  559. {
  560.     if ( site != NULL )
  561.         {
  562.         --site->currentBlocks;
  563.         site->currentMemUsed -= blockSize;
  564.         }
  565. }
  566.  
  567.  
  568. static unsigned long AllocationSiteHash( void ** stackCrawl )
  569. {
  570.     unsigned long    hash;
  571.     unsigned long    count;
  572.     
  573.     hash = 0;
  574.  
  575.     for ( count = 0; count < kStackDepth; ++count )
  576.         {
  577.         hash += (unsigned long) stackCrawl[ count ];
  578.         }
  579.     
  580.     return hash;
  581. }
  582.  
  583.  
  584. static Boolean AllocationSiteHashCompare ( void ** site1, void ** site2 )
  585. {
  586.     Boolean            matched;
  587.     unsigned long    count;
  588.     
  589.     matched = true;
  590.     for ( count = 0; count < kStackDepth; ++count )
  591.         {
  592.         if ( site1[ count ] != site2[ count ] )
  593.             {
  594.             matched = false;
  595.             break;
  596.             }
  597.         }
  598.     
  599.     return matched;
  600. }
  601.  
  602.  
  603. AllocationSet * NewAllocationSet ( unsigned long trackingOptions, char * name )
  604. {
  605. #pragma unused(trackingOptions)
  606. #if DEBUG_MAC_MEMORY
  607.     AllocationSet *    set;
  608.     unsigned long    count;
  609.     
  610.     set = NULL;
  611.  
  612.     /* find a free set */
  613.     for ( count = 0; count < kNumAllocationSets; ++count )
  614.         {
  615.         if ( gAllocationSetPool[ count ].inUse == false )
  616.             {
  617.             set = &gAllocationSetPool[ count ];
  618.             break;
  619.             }
  620.         }
  621.     
  622.     if ( set != NULL )
  623.         {
  624.         set->inUse = true;
  625.         set->numBlocks = 0;
  626.         set->totalAllocation = 0;
  627.         set->currentAllocation = 0;
  628.         set->maxAllocation = 0;
  629.         set->enabledState = 0;
  630.         strcpy ( set->name, name );
  631.         
  632.         /* clear all blocks from this set */
  633.         for ( count = 0; count < kBlockAllocationLongs; ++count )
  634.             {
  635.             set->blockSet[ count ] = 0;
  636.             }
  637.         }
  638.     
  639.     return set;
  640. #else
  641. #pragma unused(name)
  642.     return NULL;
  643. #endif
  644. }
  645.  
  646.  
  647. void EnableAllocationSet ( AllocationSet * set )
  648. {
  649.     if ( set->enabledState > 0 )
  650.         {
  651.         --set->enabledState;
  652.         }
  653. }
  654.  
  655.  
  656. void DisableAllocationSet ( AllocationSet * set )
  657. {
  658.     if ( set->enabledState == 255 )
  659.         {
  660. //        DebugStr ( "\pAllocationSet's enabledState overflowed!" );
  661.         }
  662.     
  663.     ++set->enabledState;
  664. }
  665.  
  666.  
  667. void AddNewBlockToAllocationSet ( AllocationSet * set, Block * block )
  668. {
  669. #if DEBUG_MAC_MEMORY
  670.     unsigned long    blockID;
  671.     unsigned long    blockMask;
  672.     unsigned long *    blockSetLong;
  673.     
  674.     /* if we're not enabled, then bail */
  675.     if ( set->enabledState != 0 )
  676.         {
  677.         return;
  678.         }
  679.         
  680.     blockID = block->blockID;
  681.     blockSetLong = &set->blockSet[ blockID >> 5 ];
  682.     
  683.     blockMask = 1L << ( 31 - ( blockID & 0x1F ) );
  684.     
  685.     if ( *blockSetLong & blockMask )
  686.         {
  687. //        DebugStr ( "\pWe suck, this block is already part of the set" );
  688.         return;
  689.         }
  690.  
  691.     set->numBlocks++;
  692.     set->totalAllocation += block->blockSize;
  693.     set->currentAllocation += block->blockSize;
  694.         
  695.     if ( set->currentAllocation > set->maxAllocation )
  696.         {
  697.         set->maxAllocation = set->currentAllocation;
  698.         }
  699.         
  700.     *blockSetLong |= blockMask;
  701.     AddBlockReference ( block );
  702. #else
  703. #pragma unused(set, block)
  704. #endif
  705. }
  706.  
  707.  
  708. void MarkBlockFreeFromSet ( AllocationSet * set, Block * block )
  709. {
  710. #if DEBUG_MAC_MEMORY
  711.     unsigned long    blockID;
  712.     unsigned long    blockMask;
  713.     unsigned long *    blockSetLong;
  714.     
  715.     blockID = block->blockID;
  716.     blockSetLong = &set->blockSet[ blockID >> 5 ];
  717.     
  718.     blockMask = 1L << ( 31 - ( blockID & 0x1F ) );
  719.     
  720.     if ( ( *blockSetLong & blockMask ) == 0 )
  721.         {
  722.         return;
  723.         }
  724.     
  725.     *blockSetLong &= ~blockMask;
  726.  
  727.     set->numBlocks--;
  728.     set->currentAllocation -= block->blockSize;
  729.  
  730.     RemoveBlockReference ( block );
  731. #else
  732. #pragma unused(set, block)
  733. #endif
  734. }
  735.  
  736.  
  737. void LogAllocationSetState ( AllocationSet * set )
  738. {
  739. #if DEBUG_MAC_MEMORY
  740.     unsigned long    blockCount;
  741.     unsigned long    blockMask;
  742.     unsigned long *    setLongPtr;
  743.     unsigned long    setLong;
  744.     Block *            block;
  745.     AllocationSetLogEntry    logEntry;
  746.     AllocationSetLog        logHeader;
  747.     long                    size;
  748.     OSErr                    err;
  749.     
  750.     if ( set == NULL )
  751.         {
  752.         return;
  753.         }
  754.     
  755.     if ( gLogFile != NULL )
  756.         {
  757.         memset( &logHeader, 0, sizeof(logHeader) );
  758.         logHeader.header.logTag = kSET_BLOCK_LIST;
  759.         logHeader.header.logSize = sizeof(AllocationSetLog) +
  760.             ( set->numBlocks * sizeof(AllocationSetLogEntry) );
  761.         
  762.         logHeader.numEntries = set->numBlocks;
  763.         logHeader.totalAllocation = set->totalAllocation;
  764.         logHeader.currentAllocation = set->currentAllocation;
  765.         logHeader.maxAllocation = set->maxAllocation;
  766.         strcpy ( logHeader.name, set->name );
  767.         
  768.         size = sizeof(logHeader);
  769.         err = FSWrite ( gLogFile, &size, &logHeader );
  770.         if ( err != noErr )
  771.             {
  772.             DebugStr ( "\pWrite failed" );
  773.             return;
  774.             }
  775.         
  776.         blockMask = 0;
  777.         setLongPtr = set->blockSet;
  778.  
  779.         for ( blockCount = 0; blockCount < kNumBlocksTracked; ++blockCount )
  780.             {
  781.             if ( blockMask == 0 )
  782.                 {
  783.                 blockMask = 0x80000000;
  784.                 setLong = *setLongPtr++;
  785.                 }
  786.             
  787.             if ( setLong & blockMask )
  788.                 {
  789.                 block = &gBlockPool[ blockCount ];
  790.                 
  791.                 memset( &logEntry, 0, sizeof(logEntry) );
  792.                 logEntry.address = (unsigned long) block->blockAddress;
  793.                 logEntry.blockNumber = block->blockNum;
  794.                 logEntry.size = block->blockSize;
  795.                 if ( block->site != NULL )
  796.                     {
  797.                     logEntry.siteIndex = block->site->siteIndex;
  798.                     }
  799.                 else
  800.                     {
  801.                     logEntry.siteIndex = -1;
  802.                     }
  803.                     
  804.                 logEntry.allocType = block->allocType;
  805.                 logEntry.blockState = block->blockState;
  806.                 logEntry.overhead = block->overhead;
  807.                 
  808.                 size = sizeof(logEntry);
  809.                 err = FSWrite ( gLogFile, &size, &logEntry );
  810.                 if ( err != noErr )
  811.                     {
  812.                     DebugStr ( "\pWrite failed" );
  813.                     return;
  814.                     }
  815.                 }
  816.             
  817.             blockMask >>= 1;
  818.             }
  819.         }
  820. #else
  821. #pragma unused(set)
  822. #endif
  823. }
  824.  
  825.  
  826. void DisposeAllocationSet ( AllocationSet * set )
  827. {
  828. #if DEBUG_MAC_MEMORY
  829.     unsigned long    blockIndex;
  830.     unsigned long *    setBlocksPtr;
  831.     unsigned long    setBlocksLong;
  832.     unsigned long    blockMask;
  833.         
  834.     /* release all the blocks we own */
  835.     setBlocksPtr = set->blockSet;
  836.     blockMask = 0;
  837.     
  838.     for ( blockIndex = 0; blockIndex < kNumBlocksTracked; ++blockIndex )
  839.         {
  840.         if ( blockMask == 0 )
  841.             {
  842.             blockMask = 0x80000000;
  843.             setBlocksLong = *setBlocksPtr++;
  844.             }
  845.         
  846.         if ( blockMask & setBlocksLong )
  847.             {
  848.             RemoveBlockReference ( &gBlockPool[ blockIndex ] );
  849.             }
  850.         
  851.         blockMask >>= 1;
  852.         }
  853.  
  854.     set->inUse = false;
  855. #else
  856. #pragma unused(set)
  857. #endif
  858. }
  859.  
  860.  
  861. /* These utility routines can all go if we're not on */
  862. #if DEBUG_MAC_MEMORY
  863. static Block * AllocateBlockFromPool ( void )
  864. {
  865.     Block *            block;
  866.     
  867.     block = gFreeBlocks;
  868.     if ( block != NULL )
  869.         {
  870.         ++gNumActiveTrackerBlocks;
  871.         gFreeBlocks = block->next;
  872.         }
  873.  
  874.     return block;
  875. }
  876.  
  877.  
  878. static void FreeBlockFromPool ( Block * block )
  879. {
  880.     /* this sucks to research the hash table, but I don't want to eat more */
  881.     /* memory */
  882.     RemoveBlock ( block );
  883.     
  884.     --gNumActiveTrackerBlocks;
  885.     
  886.     block->next = gFreeBlocks;
  887.     gFreeBlocks = block;
  888. }
  889.  
  890.  
  891. static void InsertBlock ( Block * block )
  892. {
  893.     Bucket *        bucket;
  894.     
  895.     bucket = &gBlockIndex[ (unsigned long) block->blockAddress % kHashMod ];
  896.     block->next = *bucket;
  897.     *bucket = block;
  898. }
  899.  
  900.  
  901. static void RemoveBlock ( Block * block )
  902. {
  903.     Bucket *        bucket;
  904.     Block *            prev;
  905.     Block *            next;
  906.     Block *            walker;
  907.     
  908.     bucket = &gBlockIndex[ (unsigned long) block->blockAddress % kHashMod ];
  909.         
  910.     /* walk the list, find our guy and remove it */
  911.     prev = NULL;
  912.     walker = *bucket;
  913.     
  914.     while ( walker != NULL )
  915.         {
  916.         next = walker->next;
  917.         
  918.         if ( walker == block )
  919.             {
  920.             if ( prev == NULL )
  921.                 {
  922.                 /* first block in the list */
  923.                 *bucket = next;
  924.                 }
  925.             else
  926.                 {
  927.                 prev->next = next;
  928.                 }
  929.             
  930.             break;
  931.             }
  932.         
  933.         prev = walker;
  934.         walker = next;
  935.         }
  936. }
  937.  
  938.  
  939. static Block * FindBlockBucket ( void * address, Bucket ** bucket )
  940. {
  941.     unsigned long    hashIndex;
  942.     Bucket *        hashBucket;
  943.     Block *            blockWalker;
  944.     Block *            block;
  945.     
  946.     block = NULL;
  947.     
  948.     hashIndex = (unsigned long) address % kHashMod;
  949.     hashBucket = &gBlockIndex[ hashIndex ];
  950.     if ( bucket != NULL )
  951.         {
  952.         *bucket = hashBucket;
  953.         }
  954.     
  955.     blockWalker = *hashBucket;
  956.     while ( blockWalker != NULL )
  957.         {
  958.         if ( blockWalker->blockAddress == address )
  959.             {
  960.             block = blockWalker;
  961.             break;
  962.             }
  963.         
  964.         blockWalker = blockWalker->next;
  965.         }
  966.     
  967.     return block;
  968. }
  969.  
  970.  
  971. static void AddBlockReference ( Block * block )
  972. {
  973.     ++block->refCount;
  974.         
  975.     /* make sure we didn't wrap the refCount */
  976.     assert(block->refCount != 0);
  977. }
  978.  
  979. static void RemoveBlockReference ( Block * block )
  980. {
  981.     if ( --block->refCount == 0 )
  982.         {
  983.         FreeBlockFromPool ( block );
  984.         }
  985. }
  986.  
  987.  
  988. static void PrintStackCrawl ( char * name, void ** stackCrawl )
  989. {
  990.     unsigned long        currentStackLevel;
  991.     
  992.     *name = 0;
  993.     
  994.     for (currentStackLevel = 0; currentStackLevel < kStackDepth; currentStackLevel++)
  995.         {
  996.         CatenateRoutineNameFromPC ( name, stackCrawl[ currentStackLevel ] );
  997.         
  998.         if (currentStackLevel < kStackDepth - 1)
  999.             strcat( name, "," );
  1000.         }
  1001. }
  1002.  
  1003.  
  1004. static void CatenateRoutineNameFromPC( char * string, void *currentPC )
  1005. {
  1006.     UInt32        instructionsToLook = kMaxInstructionScanDistance;
  1007.     UInt32        *currentPCAsLong = (UInt32 *)currentPC;
  1008.     UInt32        offset = 0;
  1009.     char        labelString[ 512 ];
  1010.     char        lameString[ 512 ];
  1011.     
  1012.     if (currentPC == NULL)
  1013.         return;
  1014.  
  1015.     /* make sure we're not out in the weeds */
  1016.     if ( (unsigned long) currentPC > (unsigned long) gMemoryTop )
  1017.         return;
  1018.         
  1019.     if ( (unsigned long) currentPC & 0x3 )
  1020.         return;
  1021.     
  1022.     *labelString = 0;
  1023.     *lameString = 0;
  1024.     
  1025.     while (instructionsToLook--) {
  1026.     
  1027.         if (*currentPCAsLong == 0x4E800020) {
  1028.             char    stringLength = *((char *)currentPCAsLong + 21);
  1029.             memset( labelString, 0, 512 );
  1030.             BlockMoveData( ((char *)currentPCAsLong + 22), labelString, stringLength );
  1031.             
  1032.             // if there was no routine name, then just put down the address.
  1033.             if ( *labelString == 0 )
  1034.                 {
  1035.                 PrintHexNumber( lameString, (unsigned long) currentPC );
  1036.                 goto bail;
  1037.                 }
  1038.             else
  1039.                 {
  1040.                 strcat ( lameString, labelString );
  1041.                 }
  1042.             break;
  1043.         }
  1044.     
  1045.         currentPCAsLong++;
  1046.     }
  1047.     
  1048.     instructionsToLook = kMaxInstructionScanDistance;
  1049.     currentPCAsLong = (UInt32 *)currentPC;
  1050.     
  1051.     *labelString = 0;
  1052.     
  1053.     while (instructionsToLook--) {
  1054.         if (*currentPCAsLong == 0x7C0802A6) {
  1055.             strcat ( lameString, "+" );
  1056.  
  1057.             PrintHexNumber( labelString, offset - 4 );
  1058.             strcat ( lameString, labelString );
  1059.             break;
  1060.         }
  1061.         currentPCAsLong--;
  1062.         offset += 4;
  1063.     }
  1064.  
  1065. bail:    
  1066.     /* make sure we don't end up being too big */
  1067.     lameString[ kNameMaxLength ] = 0;
  1068.     strcat ( string, lameString );
  1069. }
  1070.  
  1071.  
  1072. static void PrintHexNumber( char * string, UInt32 hexNumber )
  1073. {
  1074.     char        hexString[11];
  1075.     char        hexMap[] = "0123456789ABCDEF";
  1076.     long        digits = 8;
  1077.         
  1078.     
  1079.     hexString[0] = '0';
  1080.     hexString[1] = 'x';
  1081.     
  1082.     while (digits) {
  1083.         hexString[digits + 1] = *((hexNumber & 0x0F) + hexMap);
  1084.         hexNumber = hexNumber >> 4;
  1085.         digits--;
  1086.     }
  1087.     hexString[10] = 0;
  1088.     
  1089.     strcat ( string, hexString );
  1090. }
  1091.  
  1092.  
  1093. static void HashInitialize ( HashTable * table, HashFunction hash, HashCompare compare )
  1094. {
  1095.     unsigned long    count;
  1096.     
  1097.     table->hashFunction = hash;
  1098.     table->compareFunction = compare;
  1099.     
  1100.     for ( count = 0; count < kHashMod; ++count )
  1101.         {
  1102.         table->index[ count ] = NULL;
  1103.         }
  1104. }
  1105.  
  1106.  
  1107. static void HashInsert ( HashTable * table, HashBlock * block )
  1108. {
  1109.     HashBlock **    bucket;
  1110.     unsigned long    hash;
  1111.     
  1112.     hash = (*table->hashFunction) ( block->key ) % kHashMod;
  1113.     
  1114.     bucket = &table->index[ hash ];
  1115.     block->next = *bucket;
  1116.     *bucket = block;
  1117. }
  1118.  
  1119.  
  1120. static void HashRemove ( HashTable * table, HashBlock * block )
  1121. {
  1122.     HashBlock **    bucket;
  1123.     HashBlock *        prev;
  1124.     HashBlock *        next;
  1125.     HashBlock *        walker;
  1126.     unsigned long    hash;
  1127.     
  1128.     hash = (*table->hashFunction) ( block->key ) % kHashMod;
  1129.     
  1130.     bucket = &table->index[ hash ];
  1131.         
  1132.     /* walk the list, find our guy and remove it */
  1133.     prev = NULL;
  1134.     walker = *bucket;
  1135.     
  1136.     while ( walker != NULL )
  1137.         {
  1138.         next = walker->next;
  1139.         
  1140.         if ( (*table->compareFunction)( walker->key, block->key ) )
  1141.             {
  1142.             if ( prev == NULL )
  1143.                 {
  1144.                 /* first block in the list */
  1145.                 *bucket = next;
  1146.                 }
  1147.             else
  1148.                 {
  1149.                 prev->next = next;
  1150.                 }
  1151.             
  1152.             break;
  1153.             }
  1154.         
  1155.         prev = walker;
  1156.         walker = next;
  1157.         }
  1158. }
  1159.  
  1160.  
  1161. static HashBlock * HashFind ( HashTable * table, void * key )
  1162. {
  1163.     HashBlock **    bucket;
  1164.     HashBlock *        blockWalker;
  1165.     HashBlock *        block;
  1166.     unsigned long    hash;
  1167.     
  1168.     hash = (*table->hashFunction) ( key ) % kHashMod;
  1169.     
  1170.     bucket = &table->index[ hash ];
  1171.     
  1172.     block = NULL;
  1173.     blockWalker = *bucket;
  1174.     
  1175.     while ( blockWalker != NULL )
  1176.         {
  1177.         if ( (*table->compareFunction) ( blockWalker->key, key ) )
  1178.             {
  1179.             block = blockWalker;
  1180.             break;
  1181.             }
  1182.         
  1183.         blockWalker = blockWalker->next;
  1184.         }
  1185.     
  1186.     return block;
  1187. }
  1188.  
  1189. pascal void TrackerExitToShellPatch(void)
  1190. {
  1191. static Boolean gBeenHere = false;
  1192.  
  1193.     /* if we haven't been here, then dump our memory state, otherwise don't */
  1194.     /* this way we don't hose ourselves if we crash in here */
  1195.     if ( !gBeenHere )
  1196.         {
  1197.         gBeenHere = true;
  1198.         DumpMemoryTrackerState();
  1199.         }
  1200.  
  1201.     ExitMemoryTracker();
  1202.     
  1203. #if GENERATINGCFM
  1204.     CallUniversalProc(gExitToShellPatchCallThru, uppExitToShellProcInfo);
  1205. #else 
  1206.     {
  1207.         ExitToShellProc    *exitProc = (ExitToShellProc *)&gExitToShellPatchCallThru;
  1208.         (*exitProc)();
  1209.     }
  1210. #endif
  1211. }
  1212.  
  1213. #endif
  1214.  
  1215. asm void *GetCurrentStackPointer() 
  1216. {
  1217.     mr        r3, sp
  1218.     lwz        r3, 0(r3)
  1219.     blr
  1220. }
  1221.  
  1222.  
  1223. void GetCurrentStackTrace(void **stackCrawl)
  1224. {
  1225.     void *        currentSP;
  1226.     void *        interfaceLibSP;
  1227.     void *        callerFirstStackFrame;
  1228.     void *        callerSP;
  1229.     UInt32        stackFrameLevel;
  1230.     UInt8        isPowerPC = true;
  1231.     void *        nextFrame;
  1232.     long        nativeFrames;
  1233.     PRThread *    curThread;
  1234.     void *        stackMin;
  1235.     void *        stackMax;
  1236.         
  1237.     memset(stackCrawl, 0, sizeof(void *) * kStackDepth);
  1238.     
  1239. #if !GENERATINGPOWERPC
  1240.     return;
  1241. #endif
  1242.  
  1243.     curThread = PR_CurrentThread();
  1244.     if ( curThread != NULL && curThread->stack->stackBottom != 0 )
  1245.         {
  1246.         stackMin = curThread->stack->stackBottom;
  1247.         stackMax = curThread->stack->stackTop;
  1248.         }
  1249.     else
  1250.         {
  1251.         stackMin = gOurApplicationHeapBase;
  1252.         stackMax = gOurApplicationHeapMax;
  1253.         }
  1254.  
  1255.     //    If the current SP is not in our heap, then bail .
  1256.     
  1257. #if GENERATINGPOWERPC
  1258.     currentSP = GetCurrentStackPointer();
  1259. #endif
  1260.  
  1261.     if ((currentSP > gOurApplicationHeapMax) || (currentSP < gOurApplicationHeapBase))
  1262.         return;
  1263.         
  1264.     interfaceLibSP = *((void **)currentSP);
  1265.     
  1266.     callerFirstStackFrame = interfaceLibSP;
  1267.     nextFrame = callerFirstStackFrame;
  1268.         
  1269.     //    What we really want to do here is walk up the stack until we get to a native frame that is in
  1270.     //    one of our Shared libraries... Since they can live in temp mem, this gets whacky.
  1271.     
  1272.     //    So, for now, I just walk up until I hit two native frames in a row...
  1273.     nativeFrames = 0;
  1274.     
  1275.     while (1) {
  1276.         // if this frame is outside of our thread's stack, then bail
  1277.         if ( ( nextFrame > stackMax ) || ( nextFrame < stackMin ) )
  1278.             {
  1279.             return;
  1280.             }
  1281.                 
  1282.         //    Walk the stack differently whether we are at a
  1283.         //    PowerPC or 68K frame...
  1284.  
  1285.         if (isPowerPC) {
  1286.  
  1287. #if 0
  1288.             void    *framePC;
  1289.  
  1290.             //    If we are PowerPC, check to see if the PC
  1291.             //    corresponding to the current frame is in the
  1292.             //    the app's code space.  If so, then we are
  1293.             //    done and we break out.
  1294.             
  1295.             framePC = *((void **)callerFirstStackFrame + 2);
  1296.             if ((framePC < gOurApplicationHeapMax) && (framePC > gOurApplicationHeapBase))
  1297.                 break;
  1298. #endif
  1299.                 
  1300.             //    Otherwise, check the pointer to the next
  1301.             //    stack frame.  If its low bit is set, then
  1302.             //    it is a mixed-mode switch frame, and 
  1303.             //    we need to switch to 68K frames.
  1304.  
  1305.             nextFrame = *((void **)callerFirstStackFrame);
  1306.             
  1307.             isPowerPC = ((UInt32)nextFrame & 0x00000001) == 0;            
  1308.             callerFirstStackFrame = (void *)((UInt32)nextFrame & 0xFFFFFFFE);
  1309.             if ( isPowerPC != false )
  1310.                 {
  1311.                 if ( ++nativeFrames >= 1 )
  1312.                     {
  1313.                     break;
  1314.                     }
  1315.                 }
  1316.         }
  1317.     
  1318.         else {
  1319.             
  1320.             nativeFrames = 0;
  1321.             
  1322.             //    68K case:  If the location immediately above the stack
  1323.             //    frame pointer is -1, then we are at a switch frame,
  1324.             //    move back to PowerPC.
  1325.  
  1326.             if (*((UInt32 *)callerFirstStackFrame - 1) == 0xFFFFFFFF)
  1327.                 isPowerPC = true;
  1328.             callerFirstStackFrame = *((void **)callerFirstStackFrame);
  1329.             nextFrame = callerFirstStackFrame;
  1330.         }
  1331.     
  1332.     }
  1333.     
  1334.     callerSP = callerFirstStackFrame;
  1335.     
  1336.     for (stackFrameLevel = 0; stackFrameLevel < kStackDepth; stackFrameLevel++) {
  1337.     
  1338.         if ( ( callerSP > stackMax ) || ( callerSP < stackMin ) )
  1339.             {
  1340.             return;
  1341.             }
  1342.             
  1343.         stackCrawl[stackFrameLevel] = *(((void **)callerSP) + 2);
  1344.         
  1345.         callerSP = *((void **)callerSP);
  1346.     
  1347.     }
  1348. }
  1349.  
  1350.  
  1351. void GetCurrentNativeStackTrace ( void ** stackCrawl )
  1352. {
  1353.     void *        currentSP;
  1354.     UInt32        stackFrameLevel;
  1355.     PRThread *    curThread;
  1356.     void *        stackMin;
  1357.     void *        stackMax;
  1358.     
  1359.     memset(stackCrawl, 0, sizeof(void *) * kStackDepth);
  1360.     
  1361. #if GENERATINGPOWERPC
  1362.     currentSP = GetCurrentStackPointer();
  1363. #else
  1364.     return;
  1365. #endif
  1366.  
  1367.     curThread = PR_CurrentThread();
  1368.     if ( curThread != NULL && curThread->stack->stackBottom != 0 )
  1369.         {
  1370.         stackMin = curThread->stack->stackBottom;
  1371.         stackMax = curThread->stack->stackTop;
  1372.         }
  1373.     else
  1374.         {
  1375.         stackMin = gOurApplicationHeapBase;
  1376.         stackMax = gOurApplicationHeapMax;
  1377.         }
  1378.         
  1379.     for (stackFrameLevel = 0; stackFrameLevel < kStackDepth; stackFrameLevel++) {
  1380.         if ( ( currentSP > stackMax ) || ( currentSP < stackMin ) )
  1381.             {
  1382.             return;
  1383.             }
  1384.             
  1385.         stackCrawl[stackFrameLevel] = *((void **)((char *)currentSP + 8));
  1386.         currentSP = *((void **)currentSP);
  1387.     }
  1388. }
  1389.  
  1390.