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 35using namespace BPrivate; 36 37 38processHeap::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. 90void 91processHeap::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 128void 129processHeap::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 145void 146processHeap::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 162void 163processHeap::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