1 ///-*-C++-*-////////////////////////////////////////////////////////////////// 2 // 3 // Hoard: A Fast, Scalable, and Memory-Efficient Allocator 4 // for Shared-Memory Multiprocessors 5 // Contact author: Emery Berger, http://www.cs.utexas.edu/users/emery 6 // 7 // Copyright (c) 1998-2000, The University of Texas at Austin. 8 // 9 // This library is free software; you can redistribute it and/or modify 10 // it under the terms of the GNU Library General Public License as 11 // published by the Free Software Foundation, http://www.fsf.org. 12 // 13 // This library is distributed in the hope that it will be useful, but 14 // WITHOUT ANY WARRANTY; without even the implied warranty of 15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 16 // Library General Public License for more details. 17 // 18 ////////////////////////////////////////////////////////////////////////////// 19 20 #include <string.h> 21 #include <stdio.h> 22 23 #include "config.h" 24 25 #if USE_PRIVATE_HEAPS 26 # include "privateheap.h" 27 # define HEAPTYPE privateHeap 28 #else 29 # define HEAPTYPE threadHeap 30 # include "threadheap.h" 31 #endif 32 33 #include "processheap.h" 34 35 using namespace BPrivate; 36 37 38 processHeap::processHeap() 39 : 40 theap((HEAPTYPE*)hoardSbrk(sizeof(HEAPTYPE) * fMaxThreadHeaps)), 41 #if HEAP_FRAG_STATS 42 _currentAllocated(0), 43 _currentRequested(0), 44 _maxAllocated(0), 45 _inUseAtMaxAllocated(0), 46 _maxRequested(0), 47 #endif 48 #if HEAP_LOG 49 _log((Log<MemoryRequest>*) 50 hoardSbrk(sizeof(Log<MemoryRequest>) * (fMaxThreadHeaps + 1))), 51 #endif 52 _buffer(NULL), 53 _bufferCount(0) 54 { 55 if (theap == NULL) 56 return; 57 new(theap) HEAPTYPE[fMaxThreadHeaps]; 58 59 #if HEAP_LOG 60 if (_log == NULL) 61 return; 62 new(_log) Log<MemoryRequest>[fMaxThreadHeaps + 1]; 63 #endif 64 65 int i; 66 // The process heap is heap 0. 67 setIndex(0); 68 for (i = 0; i < fMaxThreadHeaps; i++) { 69 // Set every thread's process heap to this one. 70 theap[i].setpHeap(this); 71 // Set every thread heap's index. 72 theap[i].setIndex(i + 1); 73 } 74 #if HEAP_LOG 75 for (i = 0; i < fMaxThreadHeaps + 1; i++) { 76 char fname[255]; 77 sprintf(fname, "log%d", i); 78 unlink(fname); 79 _log[i].open(fname); 80 } 81 #endif 82 #if HEAP_FRAG_STATS 83 hoardLockInit(_statsLock, "hoard stats"); 84 #endif 85 hoardLockInit(_bufferLock, "hoard buffer"); 86 } 87 88 89 // Print out statistics information. 90 void 91 processHeap::stats(void) 92 { 93 #if HEAP_STATS 94 int umax = 0; 95 int amax = 0; 96 for (int j = 0; j < fMaxThreadHeaps; j++) { 97 for (int i = 0; i < SIZE_CLASSES; i++) { 98 amax += theap[j].maxAllocated(i) * sizeFromClass(i); 99 umax += theap[j].maxInUse(i) * sizeFromClass(i); 100 } 101 } 102 printf("Amax <= %d, Umax <= %d\n", amax, umax); 103 104 #if HEAP_FRAG_STATS 105 amax = getMaxAllocated(); 106 umax = getMaxRequested(); 107 printf 108 ("Maximum allocated = %d\nMaximum in use = %d\nIn use at max allocated = %d\n", 109 amax, umax, getInUseAtMaxAllocated()); 110 printf("Still in use = %d\n", _currentRequested); 111 printf("Fragmentation (3) = %f\n", 112 (float)amax / (float)getInUseAtMaxAllocated()); 113 printf("Fragmentation (4) = %f\n", (float)amax / (float)umax); 114 #endif 115 #endif // HEAP_STATS 116 117 #if HEAP_LOG 118 printf("closing logs.\n"); 119 fflush(stdout); 120 for (int i = 0; i < fMaxThreadHeaps + 1; i++) { 121 _log[i].close(); 122 } 123 #endif 124 } 125 126 127 #if HEAP_FRAG_STATS 128 void 129 processHeap::setAllocated(int requestedSize, int actualSize) 130 { 131 hoardLock(_statsLock); 132 _currentRequested += requestedSize; 133 _currentAllocated += actualSize; 134 if (_currentRequested > _maxRequested) { 135 _maxRequested = _currentRequested; 136 } 137 if (_currentAllocated > _maxAllocated) { 138 _maxAllocated = _currentAllocated; 139 _inUseAtMaxAllocated = _currentRequested; 140 } 141 hoardUnlock(_statsLock); 142 } 143 144 145 void 146 processHeap::setDeallocated(int requestedSize, int actualSize) 147 { 148 hoardLock(_statsLock); 149 _currentRequested -= requestedSize; 150 _currentAllocated -= actualSize; 151 hoardUnlock(_statsLock); 152 } 153 #endif // HEAP_FRAG_STATS 154 155 156 // free (ptr, pheap): 157 // inputs: a pointer to an object allocated by malloc(). 158 // side effects: returns the block to the object's superblock; 159 // updates the thread heap's statistics; 160 // may release the superblock to the process heap. 161 162 void 163 processHeap::free(void *ptr) 164 { 165 // Return if ptr is 0. 166 // This is the behavior prescribed by the standard. 167 if (ptr == 0) 168 return; 169 170 // Find the block and superblock corresponding to this ptr. 171 172 block *b = (block *) ptr - 1; 173 assert(b->isValid()); 174 175 // Check to see if this block came from a memalign() call. 176 if (((unsigned long)b->getNext() & 1) == 1) { 177 // It did. Set the block to the actual block header. 178 b = (block *) ((unsigned long)b->getNext() & ~1); 179 assert(b->isValid()); 180 } 181 182 b->markFree(); 183 184 superblock *sb = b->getSuperblock(); 185 assert(sb); 186 assert(sb->isValid()); 187 188 const int sizeclass = sb->getBlockSizeClass(); 189 190 // 191 // Return the block to the superblock, 192 // find the heap that owns this superblock 193 // and update its statistics. 194 // 195 196 hoardHeap *owner; 197 198 // By acquiring the up lock on the superblock, 199 // we prevent it from moving to the global heap. 200 // This eventually pins it down in one heap, 201 // so this loop is guaranteed to terminate. 202 // (It should generally take no more than two iterations.) 203 sb->upLock(); 204 while (1) { 205 owner = sb->getOwner(); 206 owner->lock(); 207 if (owner == sb->getOwner()) { 208 break; 209 } else { 210 owner->unlock(); 211 } 212 // Suspend to allow ownership to quiesce. 213 hoardYield(); 214 } 215 216 #if HEAP_LOG 217 MemoryRequest m; 218 m.free(ptr); 219 getLog(owner->getIndex()).append(m); 220 #endif 221 #if HEAP_FRAG_STATS 222 setDeallocated(b->getRequestedSize(), 0); 223 #endif 224 225 int sbUnmapped = owner->freeBlock(b, sb, sizeclass, this); 226 227 owner->unlock(); 228 if (!sbUnmapped) 229 sb->upUnlock(); 230 } 231