home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / xp / xp_tracker.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  24.9 KB  |  1,161 lines
  1. /* -*- Mode: C++; tab-width: 8; 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.  
  20. #ifdef XP_MAC
  21. #include "TypesAndSwitches.h"
  22.  
  23. #if DEBUG_MAC_MEMORY
  24. #define    BUILD_TRACKER    1
  25. #endif
  26.  
  27. #include <Types.h>
  28. #include <unistd.h>
  29. #include <fcntl.h>
  30. #endif /* XP_MAC */
  31.  
  32.  
  33. #include <stdio.h>
  34. #include <string.h>
  35. #ifndef NSPR20
  36. #include "prglobal.h"
  37. #include "prfile.h"
  38. #endif
  39. #include "xp_tracker.h"
  40.  
  41.  
  42.  
  43. /*
  44.  * These should all be runtime options.
  45.  */
  46. #define    LOG_ALL_OPEN_SETS        1
  47. //#define    LOG_SITE_LEAKS_ONLY        1
  48.  
  49. /*
  50.  * Considering that this is meant to help us reduce memory consumption, my use of memory
  51.  * here is pretty appalling. However, I think optimizations here are only worth the time
  52.  * if they're needed. The most important thing is to get this working quickly and start
  53.  * using it. Then I'll come back and fix this other stuff up.
  54.  */
  55.  
  56. #define    kNumBlocksTracked            100000
  57. #define    kBlockAllocationLongs        (( kNumBlocksTracked + 31 ) >> 5 )
  58. #define    kHashMod                    1091
  59. #define    kNumAllocationSites            30000
  60. #define    kNumAllocationSets            20
  61. #define    kInvalidIndex                0xFFFFFFFF
  62.  
  63.  
  64. /*
  65.  * Hash Table crap
  66.  */
  67. typedef struct HashBlock HashBlock;
  68. typedef struct HashTable HashTable;
  69.  
  70. typedef unsigned long (*HashFunction)( void * key );
  71. typedef Boolean (*HashCompare) ( void * key1, void *key2 );
  72.  
  73.  
  74. struct HashBlock {
  75.     struct HashBlock *    next;
  76.     char                key[];
  77. };
  78.  
  79. struct HashTable {
  80.     HashFunction    hashFunction;
  81.     HashCompare        compareFunction;
  82.     HashBlock *        index[ kHashMod ];
  83. };
  84.  
  85.  
  86.  
  87. static void HashInitialize ( HashTable * table, HashFunction hash, HashCompare compare );
  88. static HashBlock * HashFind ( HashTable * table, void * key );
  89. static void HashInsert ( HashTable * table, HashBlock * block );
  90. static void HashRemove ( HashTable * table, HashBlock * block );
  91.  
  92.  
  93. /*
  94.  * Internal tracker data structures and constants
  95.  */
  96.  
  97.  
  98. // decoder table
  99. #define    kNumDecoderTypes    10
  100.  
  101. typedef struct DecoderTable {
  102.     UInt32        decoderTag[ kNumDecoderTypes ];
  103.     DecoderProc    decoderProc[ kNumDecoderTypes ];
  104. } DecoderTable;
  105.  
  106. typedef struct AllocationSite AllocationSite;
  107.  
  108. typedef struct Block {
  109.     unsigned long        blockNum;
  110.     unsigned long        blockID;
  111.     unsigned long        blockSize;
  112.     void *                blockAddress;
  113.     AllocationSite *    site;
  114.     unsigned char        blockState;
  115.     unsigned char        refCount;
  116.     unsigned char        overhead;
  117.     unsigned char        pad;
  118.     struct Block *        next;
  119. } Block;
  120.  
  121. struct AllocationSet {
  122.     unsigned long    numBlocks;
  123.     unsigned long    totalAllocation;
  124.     unsigned long    currentAllocation;
  125.     unsigned long    maxAllocation;
  126.     unsigned long    blockSet[ kBlockAllocationLongs ];
  127.     unsigned char    inUse;
  128.     unsigned char    enabledState;
  129.     char            name[ 256 ];
  130. };
  131.  
  132. typedef Block * Bucket;
  133.  
  134. struct AllocationSite {
  135.     AllocationSite *    next;
  136.     
  137.     /* This is gross. The next two fields need to be in this order as the hash */
  138.     /* key function depends on it */
  139.     unsigned long        tag;
  140.     void *                stackCrawl[ kStackDepth ];
  141.     
  142.     unsigned long        siteIndex;
  143.     unsigned long        currentBlocks;
  144.     unsigned long        currentMemUsed;
  145.     unsigned long        maxMemUsed;
  146.     unsigned long        maxBlocks;
  147.     unsigned long        totalBlocks;
  148.     unsigned long        totalMemUsed;
  149. };
  150.  
  151. AllocationSite * NewAllocationSite ( void ** stackCrawl, UInt32 tag, UInt32 blockSize );
  152.  
  153.  
  154. #if BUILD_TRACKER
  155. Block                gBlockPool[ kNumBlocksTracked ];
  156. Block *                gFreeBlocks;
  157. Block *                gBlockIndex[ kHashMod ];
  158. unsigned long        gIndexSize;
  159. unsigned long        gBlockNumber;
  160. unsigned long        gNumActiveTrackerBlocks;
  161. unsigned long        gNumHeapBlocks;
  162. unsigned long        gMaxNumHeapBlocks;
  163. unsigned long        gNumAllocations;
  164. AllocationSite        gAllocationSites[ kNumAllocationSites ];
  165. unsigned long        gAllocationSitesUsed;
  166. HashTable            gSiteTable;
  167. AllocationSet        gAllocationSetPool[ kNumAllocationSets ];
  168. unsigned char        gTrackerInitialized = false;
  169. Boolean                gNeverInitialized = true;
  170. unsigned long        gTrackerEnableState = 0;
  171. DecoderTable        gDecoderTable;
  172. HistogramLog        gSizeHistogram;
  173.  
  174. long                gNumActiveSets = 0;
  175. long                gNumEnabledSets = 0;
  176.  
  177. static PRFileHandle    gLogFile = NULL;
  178.  
  179. #endif
  180.  
  181.  
  182. static Block * AllocateBlockFromPool ( void );
  183. static void FreeBlockFromPool ( Block * block );
  184. static Block * FindBlock ( void * address );
  185. static void InsertBlock ( Block * block );
  186. static void RemoveBlock ( Block * block );
  187. static Block * FindBlockBucket ( void * address, Bucket ** bucket );
  188. static void AddBlockReference ( Block * block );
  189. static void RemoveBlockReference ( Block * block );
  190.  
  191. static void AddNewBlockToAllocationSet ( AllocationSet * set, Block * block );
  192. static void MarkBlockFreeFromSet ( AllocationSet * set, Block * block );
  193. static void BlockFreedFromSite ( AllocationSite * site, unsigned long blockSize );
  194.  
  195.  
  196. static unsigned long AllocationSiteHash( void ** stackCrawl );
  197. static Boolean AllocationSiteHashCompare ( void ** site1, void ** site2 );
  198.  
  199. void InitializeMemoryTracker ( void )
  200. {
  201. #if BUILD_TRACKER
  202.     unsigned long        count;
  203.     unsigned long        blockCount;
  204.     AllocationSet *        set;
  205.     Block *                block;
  206.     Block **            blockIndex;
  207.  
  208.     /* do any one time init */
  209.     if ( gNeverInitialized )
  210.         {
  211.         gNeverInitialized = false;
  212.         }
  213.                 
  214.     /* Be sure to dispose of ourselves if already allocated */
  215.     if ( gTrackerInitialized != false )
  216.         {
  217.         ExitMemoryTracker();
  218.         }
  219.         
  220.     gBlockNumber = 0;
  221.     gNumActiveTrackerBlocks = 0;
  222.     gNumHeapBlocks = 0;
  223.     gMaxNumHeapBlocks = 0;
  224.     gNumAllocations = 0;
  225.     gAllocationSitesUsed = 0;
  226.     gIndexSize = 0;
  227.     gNumActiveSets = 0;
  228.     gNumEnabledSets = 0;
  229.     
  230.     gLogFile = NULL;
  231.     
  232.     block = gBlockPool;
  233.     gFreeBlocks = NULL;
  234.     
  235.     for ( count = 0; count < kNumBlocksTracked; ++count )
  236.         {
  237.         block->refCount = 0;
  238.         block->blockAddress = NULL;
  239.         block->blockID = count;
  240.         block->next = gFreeBlocks;
  241.         gFreeBlocks = block;
  242.         
  243.         ++block;
  244.         }
  245.         
  246.     blockIndex = gBlockIndex;
  247.  
  248.     for ( count = 0; count < kHashMod; ++count )
  249.         {
  250.         *blockIndex++ = NULL;
  251.         }    
  252.         
  253.     set = gAllocationSetPool;
  254.     
  255.     for ( count = 0; count < kNumAllocationSets; ++count )
  256.         {
  257.         set->inUse = false;
  258.         
  259.         for ( blockCount = 0; blockCount < kBlockAllocationLongs; ++blockCount )
  260.             {
  261.             set->blockSet[ blockCount ] = 0;
  262.             }
  263.         
  264.         ++set;
  265.         }
  266.     
  267.     for ( count = 0; count < kNumDecoderTypes; ++count )
  268.         {
  269.         gDecoderTable.decoderTag[ count ] = 0;
  270.         gDecoderTable.decoderProc[ count ] = 0L;
  271.         }
  272.     
  273.     memset ( &gSizeHistogram, 0, sizeof(gSizeHistogram) );
  274.     gSizeHistogram.header.logTag = kSIZE_HISTOGRAM;
  275.     gSizeHistogram.header.logSize = sizeof(HistogramLog);
  276.         
  277.     HashInitialize ( &gSiteTable, (HashFunction) &AllocationSiteHash,
  278.         (HashCompare) AllocationSiteHashCompare );
  279.         
  280.     gTrackerInitialized = true;
  281.     gTrackerEnableState = 0;
  282.     
  283.     NewAllocationSet ( 0, "InitializeMemoryTracker" );
  284. #endif
  285. }
  286.  
  287.  
  288. void ExitMemoryTracker ( void )
  289. {
  290. #if BUILD_TRACKER
  291.     gTrackerInitialized = false;
  292.     
  293.     if ( gLogFile != NULL )
  294.         {
  295.         gLogFile = 0;
  296.         }
  297. #endif
  298. }
  299.  
  300.  
  301. void DisableMemoryTracker ( void )
  302. {
  303. #if BUILD_TRACKER
  304.     ++gTrackerEnableState;
  305. #endif
  306. }
  307.  
  308.  
  309. void EnableMemoryTracker ( void )
  310. {
  311. #if BUILD_TRACKER
  312.     if ( gTrackerEnableState > 0 )
  313.         {
  314.         --gTrackerEnableState;
  315.         }
  316. #endif
  317. }
  318.  
  319.  
  320. void SetTrackerDataDecoder ( UInt32 tag, DecoderProc proc )
  321. {
  322. #if BUILD_TRACKER
  323.     UInt32    count;
  324.     
  325.     /* find a free entry and set it */
  326.     for ( count = 0; count < kNumDecoderTypes; ++count )
  327.         {
  328.         if ( gDecoderTable.decoderProc[ count ] == NULL )
  329.             {
  330.             gDecoderTable.decoderTag[ count ] = tag;
  331.             gDecoderTable.decoderProc[ count ] = proc;
  332.             break;
  333.             }
  334.         }
  335. #else
  336. #pragma unused( tag, proc )
  337. #endif
  338. }
  339.  
  340.  
  341. void DumpMemoryTrackerState ( void )
  342. {
  343. #if BUILD_TRACKER
  344.     UInt32        count;
  345.     UInt32        bytesOut;
  346.     
  347.     if ( gLogFile == NULL )
  348.         {
  349.         gLogFile = PR_OpenFile ( "MemoryLog.bin", O_WRONLY | O_CREAT | O_TRUNC, 0644 );
  350.         PR_ASSERT(gLogFile);
  351.         }
  352.     
  353.     /* dump the size histogram */
  354.     bytesOut = _OS_WRITE ( gLogFile, (char *) &gSizeHistogram, sizeof(gSizeHistogram) );
  355.     PR_ASSERT(bytesOut == sizeof(gSizeHistogram));
  356.         
  357. #if LOG_ALL_OPEN_SETS    
  358.     /* Log all active allocation sets */
  359.     for ( count = 0; count < kNumAllocationSets; ++count )
  360.         {
  361.         if ( gAllocationSetPool[ count ].inUse == true )
  362.             {
  363.             LogAllocationSetState ( &gAllocationSetPool[ count ] );
  364.             }
  365.         }
  366. #endif
  367.     
  368.     DumpAllocationSites();
  369. #endif
  370. }
  371.  
  372.  
  373. void DumpAllocationSites ( void )
  374. {
  375. #if BUILD_TRACKER
  376.     unsigned long            count;
  377.     AllocationSite *        site;
  378.     AllocationSiteLogEntry    logEntry;
  379.     AllocationSiteLog        logHeader;
  380.     long                    size;
  381.     int32                    err;
  382.     UInt32                    decoderCount;
  383.     DecoderProc                proc;
  384.     
  385.     if ( gLogFile != NULL )
  386.         {
  387.         logHeader.header.logTag = kALLOCATION_SITE_LIST;
  388.         logHeader.header.logSize = sizeof(AllocationSiteLog) +
  389.             ( gAllocationSitesUsed * sizeof(AllocationSiteLogEntry) );
  390.         logHeader.numEntries = gAllocationSitesUsed;
  391.         
  392.         size = sizeof(logHeader);
  393.         err = _OS_WRITE ( gLogFile, (char *) &logHeader, size );
  394.         PR_ASSERT(err == size);
  395.         
  396.         for ( count = 0; count < gAllocationSitesUsed; ++count )
  397.             {
  398.             site = &gAllocationSites[ count ];
  399.  
  400.             memset( &logEntry, 0, sizeof(logEntry) );
  401.  
  402.             // find the decoder routine and call it */
  403.             for ( decoderCount = 0; decoderCount < kNumDecoderTypes; ++decoderCount )
  404.                 {
  405.                 if ( gDecoderTable.decoderTag[ decoderCount ] == site->tag )
  406.                     {
  407.                     proc = gDecoderTable.decoderProc[ decoderCount ];
  408.                     if ( proc != NULL )
  409.                         {
  410.                         proc ( site->stackCrawl, logEntry.stackNames );
  411.                         break;
  412.                         }
  413.                     }
  414.                 }
  415.             
  416.             logEntry.tag = site->tag;
  417.             logEntry.currentBlocks = site->currentBlocks;
  418.             logEntry.currentMemUsed = site->currentMemUsed;
  419.             logEntry.maxMemUsed = site->maxMemUsed;
  420.             logEntry.maxBlocks = site->maxBlocks;
  421.             logEntry.totalBlocks = site->totalBlocks;
  422.             logEntry.totalMemUsed = site->totalMemUsed;
  423.             
  424.             size = sizeof(logEntry);
  425.             err = _OS_WRITE ( gLogFile, (char *) &logEntry, size );
  426.             PR_ASSERT(err == size);
  427.             }
  428.         }
  429. #endif
  430. }
  431.  
  432.  
  433. void TrackItem ( void * address, size_t blockSize, size_t overhead, UInt32 tag,
  434.     void * decoderData )
  435. {
  436. #if BUILD_TRACKER
  437.     AllocationSite *    site;
  438.     Block *                block;
  439.     unsigned long        setCount;
  440.     UInt32                histIndex;
  441.     
  442.     ++gNumHeapBlocks;
  443.     ++gNumAllocations;
  444.  
  445.     if ( gNumHeapBlocks > gMaxNumHeapBlocks )
  446.         {
  447.         gMaxNumHeapBlocks = gNumHeapBlocks;
  448.         }
  449.     
  450.     histIndex = CONVERT_SIZE_TO_INDEX(blockSize);
  451.     gSizeHistogram.count[ histIndex ].total++;
  452.     gSizeHistogram.count[ histIndex ].current++;
  453.     if ( gSizeHistogram.count[ histIndex ].current > gSizeHistogram.count[ histIndex ].max )
  454.         {
  455.         gSizeHistogram.count[ histIndex ].max = gSizeHistogram.count[ histIndex ].current;
  456.         }
  457.     
  458.     /* don't do anything if we have nowhere to put it */
  459.     if ( gNumActiveSets == 0 )
  460.         {
  461.         return;
  462.         }
  463.     
  464.     /* if we don't have any enabled sets, then bail */
  465.     if ( gNumEnabledSets == 0 )
  466.         {
  467.         return;
  468.         }
  469.             
  470.     /* tracking a null block will hose us big time */
  471.     if ( ( address == NULL ) || ( gTrackerInitialized == false ) || ( gTrackerEnableState > 0 ) )
  472.         {
  473.         return;
  474.         }
  475.         
  476.     /*
  477.      * Find a free block in our block pool
  478.      */
  479.     block = AllocateBlockFromPool();
  480.     
  481.     /* if we found a block, allocate it */
  482.     if ( block != NULL )
  483.         {
  484.         /* Find the allocation site for this block */
  485.         site = NewAllocationSite ( decoderData, tag, blockSize );
  486.         
  487.         block->blockNum = gBlockNumber++;
  488.         block->blockSize = blockSize;
  489.         block->blockAddress = address;
  490.         block->refCount = 0;
  491.         block->overhead = overhead;
  492.         block->blockState = kBlockAllocated;
  493.         block->site = site;
  494.         
  495.         /* insert this block into the block index */
  496.         InsertBlock ( block );
  497.         
  498.         /* add our own reference to this block */
  499.         AddBlockReference ( block );
  500.         
  501.         /* and then add it to all relevant allocation sets */
  502.         for ( setCount = 0; setCount < kNumAllocationSets; ++setCount )
  503.             {
  504.             if ( gAllocationSetPool[ setCount ].inUse == true )
  505.                 {
  506.                 AddNewBlockToAllocationSet ( &gAllocationSetPool[ setCount ], block );
  507.                 }
  508.             }
  509.         }
  510. #else
  511. #pragma unused(address, blockSize, overhead, tag, decoderData)
  512. #endif
  513. }
  514.  
  515.  
  516. void ReleaseItem ( void * address )
  517. {
  518. #if BUILD_TRACKER
  519.     unsigned long        count;
  520.     Block *                block;
  521.         
  522.     --gNumHeapBlocks;
  523.  
  524.     if ( ( gTrackerInitialized == false ) || ( gTrackerEnableState > 0 ) )
  525.         {
  526.         return;
  527.         }
  528.         
  529.     block = NULL;
  530.     
  531.     block = FindBlockBucket ( address, NULL );
  532.     
  533.     if ( block != NULL )
  534.         {    
  535.         block->blockState = kBlockFree;
  536.  
  537.         gSizeHistogram.count[ CONVERT_SIZE_TO_INDEX(block->blockSize) ].current--;
  538.  
  539.         BlockFreedFromSite ( block->site, block->blockSize );
  540.         
  541.         /* remove our own reference from this block */
  542.         RemoveBlockReference ( block );
  543.  
  544.         /* remove block from all sets */
  545.         for ( count = 0; count < kNumAllocationSets; ++count )
  546.             {
  547.             if ( gAllocationSetPool[ count ].inUse == true )
  548.                 {
  549.                 MarkBlockFreeFromSet ( &gAllocationSetPool[ count ], block );
  550.                 }
  551.             }
  552.         }
  553. #else
  554. #pragma unused(address)
  555. #endif
  556. }
  557.  
  558. AllocationSite * NewAllocationSite ( void ** stackCrawl, UInt32 tag, UInt32 blockSize )
  559. {
  560. #if BUILD_TRACKER
  561.     AllocationSite *    site;
  562.     unsigned long        stackCount;
  563.     void *                hashKey[ kStackDepth + 1 ];
  564.     
  565.         /* turn the stack crawl and data tag into a hash key */
  566.         hashKey[ 0 ] = (void *) tag;
  567.         for ( stackCount = 1; stackCount < kStackDepth + 1; ++stackCount )
  568.             {
  569.             hashKey[ stackCount ] = stackCrawl[ stackCount - 1 ];
  570.             }
  571.             
  572.         site = (AllocationSite *) HashFind ( &gSiteTable, hashKey );
  573.         if ( site == NULL )
  574.             {
  575.             if ( gAllocationSitesUsed < kNumAllocationSites )
  576.                 {
  577.                 site = &gAllocationSites[ gAllocationSitesUsed++ ];
  578.                 for ( stackCount = 0; stackCount < kStackDepth; ++stackCount )
  579.                     {
  580.                     site->stackCrawl[ stackCount ] = stackCrawl[ stackCount ];
  581.                     }
  582.  
  583.                 site->siteIndex = gAllocationSitesUsed - 1;
  584.                 site->tag = tag;
  585.                 site->currentBlocks = 0;
  586.                 site->currentMemUsed = 0;
  587.                 site->maxMemUsed = 0;
  588.                 site->maxBlocks = 0;
  589.                 site->totalBlocks = 0;
  590.                 site->totalMemUsed = 0;
  591.                 
  592.                 HashInsert ( &gSiteTable, (HashBlock *) site );
  593.                 }
  594.             }
  595.  
  596.     if ( site != NULL )
  597.         {
  598.         ++site->currentBlocks;
  599.         if ( site->currentBlocks > site->maxBlocks )
  600.             {
  601.             site->maxBlocks = site->currentBlocks;
  602.             }
  603.             
  604.         site->currentMemUsed += blockSize;
  605.         if ( site->currentMemUsed > site->maxMemUsed )
  606.             {
  607.             site->maxMemUsed = site->currentMemUsed;
  608.             }
  609.             
  610.         ++site->totalBlocks;
  611.         site->totalMemUsed += blockSize;
  612.         }
  613.         
  614.     return site;
  615. #else
  616. #pragma unused(stackCrawl,tag, blockSize)
  617.     return NULL;
  618. #endif
  619. }
  620.  
  621.  
  622. void BlockFreedFromSite ( AllocationSite * site, unsigned long blockSize )
  623. {
  624.     if ( site != NULL )
  625.         {
  626.         --site->currentBlocks;
  627.         site->currentMemUsed -= blockSize;
  628.         }
  629. }
  630.  
  631.  
  632. static unsigned long AllocationSiteHash( void ** stackCrawl )
  633. {
  634.     unsigned long    hash;
  635.     unsigned long    count;
  636.     
  637.     hash = 0;
  638.  
  639.     for ( count = 0; count < kStackDepth + 1; ++count )
  640.         {
  641.         hash += (unsigned long) stackCrawl[ count ];
  642.         }
  643.     
  644.     return hash;
  645. }
  646.  
  647.  
  648. static Boolean AllocationSiteHashCompare ( void ** site1, void ** site2 )
  649. {
  650.     Boolean            matched;
  651.     unsigned long    count;
  652.     
  653.     matched = true;
  654.     for ( count = 0; count < kStackDepth; ++count )
  655.         {
  656.         if ( site1[ count ] != site2[ count ] )
  657.             {
  658.             matched = false;
  659.             break;
  660.             }
  661.         }
  662.     
  663.     return matched;
  664. }
  665.  
  666.  
  667. AllocationSet * NewAllocationSet ( unsigned long trackingOptions, char * name )
  668. {
  669. #pragma unused(trackingOptions)
  670. #if BUILD_TRACKER
  671.     AllocationSet *    set;
  672.     unsigned long    count;
  673.     
  674.     set = NULL;
  675.  
  676.     /* find a free set */
  677.     for ( count = 0; count < kNumAllocationSets; ++count )
  678.         {
  679.         if ( gAllocationSetPool[ count ].inUse == false )
  680.             {
  681.             set = &gAllocationSetPool[ count ];
  682.             break;
  683.             }
  684.         }
  685.     
  686.     if ( set != NULL )
  687.         {
  688.         set->inUse = true;
  689.         set->numBlocks = 0;
  690.         set->totalAllocation = 0;
  691.         set->currentAllocation = 0;
  692.         set->maxAllocation = 0;
  693.         set->enabledState = 0;
  694.         strcpy ( set->name, name );
  695.         
  696.         /* clear all blocks from this set */
  697.         for ( count = 0; count < kBlockAllocationLongs; ++count )
  698.             {
  699.             set->blockSet[ count ] = 0;
  700.             }
  701.         
  702.         ++gNumActiveSets;
  703.         ++gNumEnabledSets;
  704.         }
  705.     
  706.     return set;
  707. #else
  708. #pragma unused(name)
  709.     return NULL;
  710. #endif
  711. }
  712.  
  713.  
  714. void EnableAllocationSet ( AllocationSet * set )
  715. {
  716. #if BUILD_TRACKER
  717.     if ( set->enabledState > 0 )
  718.         {
  719.         --set->enabledState;
  720.         ++gNumEnabledSets;
  721.         }
  722. #else
  723. #pragma unused(set)
  724. #endif
  725. }
  726.  
  727.  
  728. void DisableAllocationSet ( AllocationSet * set )
  729. {
  730. #if BUILD_TRACKER
  731.     PR_ASSERT(set->enabledState != 255);
  732.     
  733.     ++set->enabledState;
  734.     --gNumEnabledSets;
  735. #else
  736. #pragma unused(set)
  737. #endif
  738. }
  739.  
  740.  
  741. void AddNewBlockToAllocationSet ( AllocationSet * set, Block * block )
  742. {
  743. #if BUILD_TRACKER
  744.     unsigned long    blockID;
  745.     unsigned long    blockMask;
  746.     unsigned long *    blockSetLong;
  747.     
  748.     /* if we're not enabled, then bail */
  749.     if ( set->enabledState != 0 )
  750.         {
  751.         return;
  752.         }
  753.         
  754.     blockID = block->blockID;
  755.     blockSetLong = &set->blockSet[ blockID >> 5 ];
  756.     
  757.     blockMask = 1L << ( 31 - ( blockID & 0x1F ) );
  758.     
  759.     if ( *blockSetLong & blockMask )
  760.         {
  761.         return;
  762.         }
  763.  
  764.     set->numBlocks++;
  765.     set->totalAllocation += block->blockSize;
  766.     set->currentAllocation += block->blockSize;
  767.         
  768.     if ( set->currentAllocation > set->maxAllocation )
  769.         {
  770.         set->maxAllocation = set->currentAllocation;
  771.         }
  772.         
  773.     *blockSetLong |= blockMask;
  774.     AddBlockReference ( block );
  775. #else
  776. #pragma unused(set, block)
  777. #endif
  778. }
  779.  
  780.  
  781. void MarkBlockFreeFromSet ( AllocationSet * set, Block * block )
  782. {
  783. #if BUILD_TRACKER
  784.     unsigned long    blockID;
  785.     unsigned long    blockMask;
  786.     unsigned long *    blockSetLong;
  787.     
  788.     blockID = block->blockID;
  789.     blockSetLong = &set->blockSet[ blockID >> 5 ];
  790.     
  791.     blockMask = 1L << ( 31 - ( blockID & 0x1F ) );
  792.     
  793.     if ( ( *blockSetLong & blockMask ) == 0 )
  794.         {
  795.         return;
  796.         }
  797.     
  798.     *blockSetLong &= ~blockMask;
  799.  
  800.     set->numBlocks--;
  801.     set->currentAllocation -= block->blockSize;
  802.  
  803.     RemoveBlockReference ( block );
  804. #else
  805. #pragma unused(set, block)
  806. #endif
  807. }
  808.  
  809.  
  810. void LogAllocationSetState ( AllocationSet * set )
  811. {
  812. #if BUILD_TRACKER
  813.     unsigned long    blockCount;
  814.     unsigned long    blockMask;
  815.     unsigned long *    setLongPtr;
  816.     unsigned long    setLong;
  817.     Block *            block;
  818.     AllocationSetLogEntry    logEntry;
  819.     AllocationSetLog        logHeader;
  820.     long                    size;
  821.     OSErr                    err;
  822.     
  823.     if ( set == NULL )
  824.         {
  825.         return;
  826.         }
  827.  
  828.     if ( gLogFile == NULL )
  829.         {
  830.         gLogFile = PR_OpenFile ( "MemoryLog.bin", O_WRONLY | O_CREAT | O_TRUNC, 0644 );
  831.         PR_ASSERT(gLogFile);
  832.         }
  833.     
  834.     if ( gLogFile != NULL )
  835.         {
  836.         memset( &logHeader, 0, sizeof(logHeader) );
  837.         logHeader.header.logTag = kSET_BLOCK_LIST;
  838.         logHeader.header.logSize = sizeof(AllocationSetLog) +
  839.             ( set->numBlocks * sizeof(AllocationSetLogEntry) );
  840.         
  841.         logHeader.numEntries = set->numBlocks;
  842.         logHeader.totalAllocation = set->totalAllocation;
  843.         logHeader.currentAllocation = set->currentAllocation;
  844.         logHeader.maxAllocation = set->maxAllocation;
  845.         strcpy ( logHeader.name, set->name );
  846.         
  847.         size = sizeof(logHeader);
  848.         err = _OS_WRITE ( gLogFile, (char *) &logHeader, size );
  849.         PR_ASSERT(err == size);
  850.         
  851.         blockMask = 0;
  852.         setLongPtr = set->blockSet;
  853.  
  854.         for ( blockCount = 0; blockCount < kNumBlocksTracked; ++blockCount )
  855.             {
  856.             if ( blockMask == 0 )
  857.                 {
  858.                 blockMask = 0x80000000;
  859.                 setLong = *setLongPtr++;
  860.                 }
  861.             
  862.             if ( setLong & blockMask )
  863.                 {
  864.                 block = &gBlockPool[ blockCount ];
  865.                 
  866.                 memset( &logEntry, 0, sizeof(logEntry) );
  867.                 logEntry.address = (unsigned long) block->blockAddress;
  868.                 logEntry.blockNumber = block->blockNum;
  869.                 logEntry.size = block->blockSize;
  870.                 if ( block->site != NULL )
  871.                     {
  872.                     logEntry.siteIndex = block->site->siteIndex;
  873.                     }
  874.                 else
  875.                     {
  876.                     logEntry.siteIndex = -1;
  877.                     }
  878.                     
  879.                 logEntry.blockState = block->blockState;
  880.                 logEntry.overhead = block->overhead;
  881.                 
  882.                 size = sizeof(logEntry);
  883.                 err = _OS_WRITE ( gLogFile, (char *) &logEntry, size );
  884.                 PR_ASSERT(err == size);
  885.                 }
  886.             
  887.             blockMask >>= 1;
  888.             }
  889.         }
  890. #else
  891. #pragma unused(set)
  892. #endif
  893. }
  894.  
  895.  
  896. void DisposeAllocationSet ( AllocationSet * set )
  897. {
  898. #if BUILD_TRACKER
  899.     unsigned long    blockIndex;
  900.     unsigned long *    setBlocksPtr;
  901.     unsigned long    setBlocksLong;
  902.     unsigned long    blockMask;
  903.     
  904.     if ( set == NULL )
  905.         {
  906.         return;
  907.         }
  908.         
  909.     /* release all the blocks we own */
  910.     setBlocksPtr = set->blockSet;
  911.     blockMask = 0;
  912.     
  913.     for ( blockIndex = 0; blockIndex < kNumBlocksTracked; ++blockIndex )
  914.         {
  915.         if ( blockMask == 0 )
  916.             {
  917.             blockMask = 0x80000000;
  918.             setBlocksLong = *setBlocksPtr++;
  919.             }
  920.         
  921.         if ( blockMask & setBlocksLong )
  922.             {
  923.             RemoveBlockReference ( &gBlockPool[ blockIndex ] );
  924.             }
  925.         
  926.         blockMask >>= 1;
  927.         }
  928.  
  929.     set->inUse = false;
  930.     --gNumActiveSets;
  931. #else
  932. #pragma unused(set)
  933. #endif
  934. }
  935.  
  936.  
  937. /* These utility routines can all go if we're not on */
  938. #if BUILD_TRACKER
  939. static Block * AllocateBlockFromPool ( void )
  940. {
  941.     Block *            block;
  942.     
  943.     block = gFreeBlocks;
  944.     if ( block != NULL )
  945.         {
  946.         ++gNumActiveTrackerBlocks;
  947.         gFreeBlocks = block->next;
  948.         }
  949.  
  950.     return block;
  951. }
  952.  
  953.  
  954. static void FreeBlockFromPool ( Block * block )
  955. {
  956.     /* this sucks to research the hash table, but I don't want to eat more */
  957.     /* memory */
  958.     RemoveBlock ( block );
  959.     
  960.     --gNumActiveTrackerBlocks;
  961.     
  962.     block->next = gFreeBlocks;
  963.     gFreeBlocks = block;
  964. }
  965.  
  966.  
  967. static void InsertBlock ( Block * block )
  968. {
  969.     Bucket *        bucket;
  970.     
  971.     bucket = &gBlockIndex[ (unsigned long) block->blockAddress % kHashMod ];
  972.     block->next = *bucket;
  973.     *bucket = block;
  974. }
  975.  
  976.  
  977. static void RemoveBlock ( Block * block )
  978. {
  979.     Bucket *        bucket;
  980.     Block *            prev;
  981.     Block *            next;
  982.     Block *            walker;
  983.     
  984.     bucket = &gBlockIndex[ (unsigned long) block->blockAddress % kHashMod ];
  985.         
  986.     /* walk the list, find our guy and remove it */
  987.     prev = NULL;
  988.     walker = *bucket;
  989.     
  990.     while ( walker != NULL )
  991.         {
  992.         next = walker->next;
  993.         
  994.         if ( walker == block )
  995.             {
  996.             if ( prev == NULL )
  997.                 {
  998.                 /* first block in the list */
  999.                 *bucket = next;
  1000.                 }
  1001.             else
  1002.                 {
  1003.                 prev->next = next;
  1004.                 }
  1005.             
  1006.             break;
  1007.             }
  1008.         
  1009.         prev = walker;
  1010.         walker = next;
  1011.         }
  1012. }
  1013.  
  1014.  
  1015. static Block * FindBlockBucket ( void * address, Bucket ** bucket )
  1016. {
  1017.     unsigned long    hashIndex;
  1018.     Bucket *        hashBucket;
  1019.     Block *            blockWalker;
  1020.     Block *            block;
  1021.     
  1022.     block = NULL;
  1023.     
  1024.     hashIndex = (unsigned long) address % kHashMod;
  1025.     hashBucket = &gBlockIndex[ hashIndex ];
  1026.     if ( bucket != NULL )
  1027.         {
  1028.         *bucket = hashBucket;
  1029.         }
  1030.     
  1031.     blockWalker = *hashBucket;
  1032.     while ( blockWalker != NULL )
  1033.         {
  1034.         if ( blockWalker->blockAddress == address )
  1035.             {
  1036.             block = blockWalker;
  1037.             break;
  1038.             }
  1039.         
  1040.         blockWalker = blockWalker->next;
  1041.         }
  1042.     
  1043.     return block;
  1044. }
  1045.  
  1046.  
  1047. static void AddBlockReference ( Block * block )
  1048. {
  1049.     ++block->refCount;
  1050.         
  1051.     /* make sure we didn't wrap the refCount */
  1052.     PR_ASSERT(block->refCount != 0);
  1053. }
  1054.  
  1055. static void RemoveBlockReference ( Block * block )
  1056. {
  1057.     if ( --block->refCount == 0 )
  1058.         {
  1059.         FreeBlockFromPool ( block );
  1060.         }
  1061. }
  1062.  
  1063.  
  1064. static void HashInitialize ( HashTable * table, HashFunction hash, HashCompare compare )
  1065. {
  1066.     unsigned long    count;
  1067.     
  1068.     table->hashFunction = hash;
  1069.     table->compareFunction = compare;
  1070.     
  1071.     for ( count = 0; count < kHashMod; ++count )
  1072.         {
  1073.         table->index[ count ] = NULL;
  1074.         }
  1075. }
  1076.  
  1077.  
  1078. static void HashInsert ( HashTable * table, HashBlock * block )
  1079. {
  1080.     HashBlock **    bucket;
  1081.     unsigned long    hash;
  1082.     
  1083.     hash = (*table->hashFunction) ( block->key ) % kHashMod;
  1084.     
  1085.     bucket = &table->index[ hash ];
  1086.     block->next = *bucket;
  1087.     *bucket = block;
  1088. }
  1089.  
  1090.  
  1091. static void HashRemove ( HashTable * table, HashBlock * block )
  1092. {
  1093.     HashBlock **    bucket;
  1094.     HashBlock *        prev;
  1095.     HashBlock *        next;
  1096.     HashBlock *        walker;
  1097.     unsigned long    hash;
  1098.     
  1099.     hash = (*table->hashFunction) ( block->key ) % kHashMod;
  1100.     
  1101.     bucket = &table->index[ hash ];
  1102.         
  1103.     /* walk the list, find our guy and remove it */
  1104.     prev = NULL;
  1105.     walker = *bucket;
  1106.     
  1107.     while ( walker != NULL )
  1108.         {
  1109.         next = walker->next;
  1110.         
  1111.         if ( (*table->compareFunction)( walker->key, block->key ) )
  1112.             {
  1113.             if ( prev == NULL )
  1114.                 {
  1115.                 /* first block in the list */
  1116.                 *bucket = next;
  1117.                 }
  1118.             else
  1119.                 {
  1120.                 prev->next = next;
  1121.                 }
  1122.             
  1123.             break;
  1124.             }
  1125.         
  1126.         prev = walker;
  1127.         walker = next;
  1128.         }
  1129. }
  1130.  
  1131.  
  1132. static HashBlock * HashFind ( HashTable * table, void * key )
  1133. {
  1134.     HashBlock **    bucket;
  1135.     HashBlock *        blockWalker;
  1136.     HashBlock *        block;
  1137.     unsigned long    hash;
  1138.     
  1139.     hash = (*table->hashFunction) ( key ) % kHashMod;
  1140.     
  1141.     bucket = &table->index[ hash ];
  1142.     
  1143.     block = NULL;
  1144.     blockWalker = *bucket;
  1145.     
  1146.     while ( blockWalker != NULL )
  1147.         {
  1148.         if ( (*table->compareFunction) ( blockWalker->key, key ) )
  1149.             {
  1150.             block = blockWalker;
  1151.             break;
  1152.             }
  1153.         
  1154.         blockWalker = blockWalker->next;
  1155.         }
  1156.     
  1157.     return block;
  1158. }
  1159.  
  1160. #endif
  1161.