home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / lib / mac / MacMemoryAllocator / src / fastmem.h < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  13.4 KB  |  275 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 <Types.h>
  20. #include <Memory.h>
  21. #include <stdlib.h>
  22.  
  23. #define DEBUG_MAC_MEMORY 0
  24. #define STATS_MAC_MEMORY 0
  25.  
  26. //##############################################################################
  27. //##############################################################################
  28.  
  29. enum {
  30.     kMaxTableAllocatedBlockSize        = 256,
  31.     kRecordingDepthOfStackLevels    = 3
  32. };
  33.  
  34. typedef void *(* AllocMemoryBlockProcPtr)(size_t blockSize, void *refcon);
  35. typedef void (* FreeMemoryBlockProcPtr)(void *freeBlock, void *refcon);
  36.  
  37. struct AllocMemoryBlockDescriptor {
  38.     AllocMemoryBlockProcPtr        allocRoutine;
  39.     void                        *refcon;        
  40. };
  41.  
  42. typedef struct AllocMemoryBlockDescriptor AllocMemoryBlockDescriptor;
  43.  
  44. struct FreeMemoryBlockDescriptor {
  45.     FreeMemoryBlockProcPtr        freeRoutine;
  46.     void                        *refcon;        
  47. };
  48.  
  49. typedef struct FreeMemoryBlockDescriptor FreeMemoryBlockDescriptor;
  50.  
  51. //##############################################################################
  52. //##############################################################################
  53.  
  54. #if DEBUG_MAC_MEMORY
  55. typedef    UInt32 MemoryBlockTag;
  56. #endif
  57.  
  58. typedef struct MemoryBlockHeader MemoryBlockHeader;
  59.  
  60. struct MemoryBlockHeader {
  61.     FreeMemoryBlockDescriptor        *blockFreeRoutine;
  62. #if DEBUG_MAC_MEMORY || STATS_MAC_MEMORY
  63.     size_t                            blockSize;
  64. #endif
  65. #if DEBUG_MAC_MEMORY
  66.     MemoryBlockHeader                *next;
  67.     MemoryBlockHeader                *prev;
  68.     UInt32                            blockNum;
  69.     void                            *whoAllocated[kRecordingDepthOfStackLevels];
  70.     MemoryBlockTag                    headerTag;
  71. #endif
  72. };
  73.  
  74. #if DEBUG_MAC_MEMORY
  75. typedef struct MemoryBlockTrailer MemoryBlockTrailer; 
  76.  
  77. struct MemoryBlockTrailer {
  78.     MemoryBlockTag        trailerTag;
  79. };
  80. #define MEMORY_BLOCK_TAILER_SIZE sizeof(struct MemoryBlockTrailer)
  81. #else
  82. #define MEMORY_BLOCK_TAILER_SIZE 0
  83. #endif
  84.  
  85. //##############################################################################
  86. //##############################################################################
  87. #pragma mark STANDARD (SLOW!) ALLOCATOR DEFINITIONS
  88.  
  89. void *StandardAlloc(size_t blockSize, void *refcon);
  90. void StandardFree(void *block, void *refcon);
  91.  
  92. //##############################################################################
  93. //##############################################################################
  94. #pragma mark FIXED SIZED (COMPACT) ALLOCATOR DEFINITIONS
  95.  
  96. typedef struct FixedSizeCompactAllocationChunk FixedSizeCompactAllocationChunk;
  97.  
  98. typedef struct FixedSizeCompactAllocationRoot FixedSizeCompactAllocationRoot;
  99.  
  100. struct FixedSizeCompactAllocationChunk {
  101.     FixedSizeCompactAllocationChunk            *next;
  102.     FixedSizeCompactAllocationRoot            *root;
  103.     UInt32                                    chunkUsage;
  104. };
  105.  
  106.  
  107. struct FixedSizeCompactAllocationRoot {
  108.     FixedSizeCompactAllocationChunk            *firstChunk;
  109.     UInt32                                    blockSize;
  110.     FreeMemoryBlockDescriptor                *freeDescriptorTable;
  111. };
  112.  
  113. void *FixedSizeCompactAlloc(size_t blockSize, void *refcon);
  114. void FixedSizeCompactFree(void *block, void *refcon);
  115.  
  116. #define DeclareFixedSizeCompactAllocator(blockSize) \
  117. FreeMemoryBlockDescriptor FixedSizeCompact##blockSize##AllocationFreeDescriptors[] = { \
  118. { &FixedSizeCompactFree, (void *)((0L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 0 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  119. { &FixedSizeCompactFree, (void *)((1L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 1 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  120. { &FixedSizeCompactFree, (void *)((2L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 2 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  121. { &FixedSizeCompactFree, (void *)((3L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 3 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  122. { &FixedSizeCompactFree, (void *)((4L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 4 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  123. { &FixedSizeCompactFree, (void *)((5L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 5 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  124. { &FixedSizeCompactFree, (void *)((6L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 6 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  125. { &FixedSizeCompactFree, (void *)((7L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 7 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  126. { &FixedSizeCompactFree, (void *)((8L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 8 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  127. { &FixedSizeCompactFree, (void *)((9L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 9 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  128. { &FixedSizeCompactFree, (void *)((10L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 10 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  129. { &FixedSizeCompactFree, (void *)((11L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 11 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  130. { &FixedSizeCompactFree, (void *)((12L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 12 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  131. { &FixedSizeCompactFree, (void *)((13L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 13 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  132. { &FixedSizeCompactFree, (void *)((14L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 14 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  133. { &FixedSizeCompactFree, (void *)((15L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 15 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  134. { &FixedSizeCompactFree, (void *)((16L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 16 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  135. { &FixedSizeCompactFree, (void *)((17L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 17 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  136. { &FixedSizeCompactFree, (void *)((18L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 18 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  137. { &FixedSizeCompactFree, (void *)((19L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 19 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  138. { &FixedSizeCompactFree, (void *)((20L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 20 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  139. { &FixedSizeCompactFree, (void *)((21L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 21 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  140. { &FixedSizeCompactFree, (void *)((22L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 22 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  141. { &FixedSizeCompactFree, (void *)((23L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 23 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  142. { &FixedSizeCompactFree, (void *)((24L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 24 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  143. { &FixedSizeCompactFree, (void *)((25L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 25 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  144. { &FixedSizeCompactFree, (void *)((26L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 26 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  145. { &FixedSizeCompactFree, (void *)((27L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 27 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  146. { &FixedSizeCompactFree, (void *)((28L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 28 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  147. { &FixedSizeCompactFree, (void *)((29L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 29 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  148. { &FixedSizeCompactFree, (void *)((30L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 30 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) },\
  149. { &FixedSizeCompactFree, (void *)((31L << 16) | (sizeof(FixedSizeCompactAllocationChunk) + 31 * (blockSize + sizeof(MemoryBlockHeader) + MEMORY_BLOCK_TAILER_SIZE))) }\
  150. };\
  151. FixedSizeCompactAllocationRoot    gFixedSizeCompact##blockSize##Root = { NULL, blockSize, FixedSizeCompact##blockSize##AllocationFreeDescriptors }\
  152.  
  153. //##############################################################################
  154. //##############################################################################
  155. #pragma mark FIXED SIZED (FAST) ALLOCATOR DEFINITIONS
  156.  
  157. typedef struct FixedSizeFastMemoryBlockHeader FixedSizeFastMemoryBlockHeader;
  158.  
  159. struct FixedSizeFastMemoryBlockHeader {
  160.     FixedSizeFastMemoryBlockHeader            *nextFree;
  161.     MemoryBlockHeader                        realHeader;
  162. };
  163.  
  164. typedef struct FixedSizeFastAllocationChunk FixedSizeFastAllocationChunk;
  165.  
  166. struct FixedSizeFastAllocationChunk {
  167.     FixedSizeFastAllocationChunk            *next;
  168. };
  169.  
  170. typedef struct FixedSizeFastAllocationRoot FixedSizeFastAllocationRoot;
  171.  
  172. struct FixedSizeFastAllocationRoot {
  173.     FixedSizeFastAllocationChunk            *firstChunk;
  174.     FixedSizeFastMemoryBlockHeader            *firstFree;
  175.     UInt32                                    blockSize;
  176.     UInt32                                    blocksPerChunk;
  177.     FreeMemoryBlockDescriptor                *freeDescriptor;
  178. };
  179.  
  180. void *FixedSizeFastAlloc(size_t blockSize, void *refcon);
  181. void FixedSizeFastFree(void *block, void *refcon);
  182.  
  183. #define DeclareFixedSizeFastAllocator(blockSize, blocksPerChunk) \
  184. extern FixedSizeFastAllocationRoot    gFixedSizeFast##blockSize##Root; \
  185. FreeMemoryBlockDescriptor FixedSizeFast##blockSize##AllocationFreeDescriptor = { &FixedSizeFastFree, (void *)&gFixedSizeFast##blockSize##Root}; \
  186. FixedSizeFastAllocationRoot    gFixedSizeFast##blockSize##Root = { NULL, NULL, blockSize, blocksPerChunk, &FixedSizeFast##blockSize##AllocationFreeDescriptor }
  187.  
  188. //##############################################################################
  189. //##############################################################################
  190. #pragma mark SMALL HEAP ALLOCATOR DEFINITIONS
  191.  
  192. typedef struct SmallHeapBlock SmallHeapBlock;
  193.  
  194. struct SmallHeapBlock {
  195.     SmallHeapBlock            *prevBlock;
  196.     UInt32                    blockSize;
  197.     union {
  198.         struct {
  199.             SmallHeapBlock    *nextFree;
  200.             SmallHeapBlock    *prevFree;
  201.         }                    freeInfo;
  202.         struct {
  203.             UInt32            filler;
  204.             MemoryBlockHeader freeProc;    
  205.         }                    inUseInfo;
  206.     }                        info;
  207. };
  208.  
  209. enum {
  210.     kBlockInUseFlag                = 0x80000000,
  211.     kDefaultSmallHeadMinSize    = 4L,
  212.     kDefaultSmallHeapBins         = 64L,
  213.     kMaximumBinBlockSize        = kDefaultSmallHeadMinSize + 4L * kDefaultSmallHeapBins - 1,
  214.     kSmallHeapSize                = 256 * 1024
  215. };
  216.  
  217. typedef struct SmallHeapChunk SmallHeapChunk;
  218.  
  219. typedef struct SmallHeapRoot SmallHeapRoot;
  220.  
  221. struct SmallHeapRoot {
  222.     FreeMemoryBlockDescriptor    *blockFreeRoutine;
  223.     SmallHeapChunk                *firstChunk;
  224.     SmallHeapBlock                *overflow;
  225.     SmallHeapBlock                *bins[kDefaultSmallHeapBins];
  226. };
  227.  
  228. struct SmallHeapChunk {
  229.     SmallHeapChunk            *nextChunk;
  230. };
  231.  
  232. #define DeclareSmallHeapAllocator() \
  233. extern SmallHeapRoot    gSmallHeapRoot; \
  234. FreeMemoryBlockDescriptor SmallHeapAllocationFreeDescriptor = { &SmallHeapFree, (void *)&gSmallHeapRoot}; \
  235. SmallHeapRoot    gSmallHeapRoot = { &SmallHeapAllocationFreeDescriptor }
  236.  
  237. void *SmallHeapAlloc(size_t blockSize, void *refcon);
  238. void SmallHeapFree(void *address, void *refcon);
  239.  
  240. //##############################################################################
  241. //##############################################################################
  242.  
  243. //    Clients must provide the following two entry points.
  244.  
  245. extern AllocMemoryBlockDescriptor gFastMemSmallSizeAllocators[];
  246. extern Ptr AllocateRawMemory(Size blockSize);
  247. extern void FreeRawMemory(Ptr reclaimedRawBlock);
  248.  
  249. //    VerifyMallocHeapIntegrity will report any block headers or
  250. //    trailers that have been overwritten.
  251.  
  252. extern void InstallMemoryManagerPatches();
  253. extern void VerifyMallocHeapIntegrity();
  254. static void TagReferencedBlocks();
  255. extern void DumpAllocHeap();
  256.  
  257. //##############################################################################
  258. //##############################################################################
  259.  
  260. #ifdef DEBUG_MAC_MEMORY
  261.  
  262. extern UInt32                        gVerifyHeapOnEveryMalloc;
  263. extern UInt32                        gVerifyHeapOnEveryFree;
  264. extern UInt32                        gFillUsedBlocksWithPattern;
  265. extern UInt32                        gFillFreeBlocksWithPattern;
  266. extern UInt32                        gTrackLeaks;
  267. extern UInt32                        gDontActuallyFreeMemory;
  268. extern SInt32                        gFailToAllocateAfterNMallocs;
  269.  
  270. extern SInt32                        gReportActiveBlocks;
  271. extern SInt32                        gReportLeaks;
  272.  
  273. #endif
  274.  
  275.