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/* 21 superblock.h 22 ------------------------------------------------------------------------ 23 The superblock class controls a number of blocks (which are 24 allocatable units of memory). 25 ------------------------------------------------------------------------ 26 Emery Berger | <http://www.cs.utexas.edu/users/emery> 27 Department of Computer Sciences | <http://www.cs.utexas.edu> 28 University of Texas at Austin | <http://www.utexas.edu> 29 ======================================================================== 30*/ 31 32#ifndef _SUPERBLOCK_H_ 33#define _SUPERBLOCK_H_ 34 35#include "config.h" 36#include "arch-specific.h" 37#include "block.h" 38 39 40namespace BPrivate { 41 42class hoardHeap; // forward declaration 43class processHeap; // forward declaration 44 45class superblock { 46 public: 47 // Construct a superblock for a given size class and set the heap 48 // owner. 49 superblock(int numblocks, int sizeclass, hoardHeap *owner); 50 ~superblock(void) {} 51 52 // Make (allocate or re-use) a superblock for a given size class. 53 static superblock *makeSuperblock(int sizeclass, processHeap *pHeap); 54 55 // Find out who allocated this superblock. 56 inline hoardHeap *getOwner(void); 57 58 // Set the superblock's owner. 59 inline void setOwner(hoardHeap *o); 60 61 // Get a block from the superblock. 62 inline block *getBlock(void); 63 64 // Put a block back in the superblock. 65 inline void putBlock(block *b); 66 67 // How many blocks are available? 68 inline int getNumAvailable(void); 69 70 // How many blocks are there, in total? 71 inline int getNumBlocks(void); 72 73 // What size class are blocks in this superblock? 74 inline int getBlockSizeClass(void); 75 76 // Insert this superblock before the next one. 77 inline void insertBefore(superblock *nextSb); 78 79 // Return the next pointer (to the next superblock in the list). 80 inline superblock *const getNext(void); 81 82 // Return the prev pointer (to the previous superblock in the list). 83 inline superblock *const getPrev(void); 84 85 // Compute the 'fullness' of this superblock. 86 inline void computeFullness(void); 87 88 // Return the 'fullness' of this superblock. 89 inline int getFullness(void); 90 91#if HEAP_FRAG_STATS 92 // Return the amount of waste in every allocated block. 93 int getMaxInternalFragmentation(void); 94#endif 95 96 // Remove this superblock from its linked list. 97 inline void remove(void); 98 99 // Is this superblock valid? (i.e., 100 // does it have the right magic number?) 101 inline int isValid(void); 102 103 void 104 upLock(void) 105 { 106 hoardLock(_upLock); 107 } 108 109 void 110 upUnlock(void) 111 { 112 hoardUnlock(_upLock); 113 } 114 115 private: 116 // Disable copying and assignment. 117 118 superblock(const superblock &); 119 const superblock & operator=(const superblock &); 120 121 // Used for sanity checking. 122 enum { SUPERBLOCK_MAGIC = 0xCAFEBABE }; 123 124#if HEAP_DEBUG 125 unsigned long _magic; 126#endif 127 128 const int _sizeClass; // The size class of blocks in the superblock. 129 const int _numBlocks; // The number of blocks in the superblock. 130 int _numAvailable; // The number of blocks available. 131 int _fullness; // How full is this superblock? 132 // (which SUPERBLOCK_FULLNESS group is it in) 133 block *_freeList; // A pointer to the first free block. 134 hoardHeap *_owner; // The heap who owns this superblock. 135 superblock *_next; // The next superblock in the list. 136 superblock *_prev; // The previous superblock in the list. 137 138 hoardLockType _upLock; // Lock this when moving a superblock to the global (process) heap. 139 140 // We insert a cache pad here to prevent false sharing with the 141 // first block (which immediately follows the superblock). 142 double _pad[CACHE_LINE / sizeof(double)]; 143}; 144 145 146hoardHeap * 147superblock::getOwner(void) 148{ 149 assert(isValid()); 150 hoardHeap *o = _owner; 151 return o; 152} 153 154 155void 156superblock::setOwner(hoardHeap *o) 157{ 158 assert(isValid()); 159 _owner = o; 160} 161 162 163block * 164superblock::getBlock(void) 165{ 166 assert(isValid()); 167 // Pop off a block from this superblock's freelist, 168 // if there is one available. 169 if (_freeList == NULL) { 170 // The freelist is empty. 171 assert(getNumAvailable() == 0); 172 return NULL; 173 } 174 175 assert(getNumAvailable() > 0); 176 block *b = _freeList; 177 _freeList = _freeList->getNext(); 178 _numAvailable--; 179 180 b->setNext(NULL); 181 182 computeFullness(); 183 return b; 184} 185 186 187void 188superblock::putBlock(block *b) 189{ 190 assert(isValid()); 191 // Push a block onto the superblock's freelist. 192 assert(b->isValid()); 193 assert(b->getSuperblock() == this); 194 assert(getNumAvailable() < getNumBlocks()); 195 b->setNext(_freeList); 196 _freeList = b; 197 _numAvailable++; 198 computeFullness(); 199} 200 201 202int 203superblock::getNumAvailable(void) 204{ 205 assert(isValid()); 206 return _numAvailable; 207} 208 209 210int 211superblock::getNumBlocks(void) 212{ 213 assert(isValid()); 214 return _numBlocks; 215} 216 217 218int 219superblock::getBlockSizeClass(void) 220{ 221 assert(isValid()); 222 return _sizeClass; 223} 224 225 226superblock * const 227superblock::getNext(void) 228{ 229 assert(isValid()); 230 return _next; 231} 232 233superblock * const 234superblock::getPrev(void) 235{ 236 assert(isValid()); 237 return _prev; 238} 239 240 241void 242superblock::insertBefore(superblock * nextSb) 243{ 244 assert(isValid()); 245 // Insert this superblock before the next one (nextSb). 246 assert(nextSb != this); 247 _next = nextSb; 248 if (nextSb) { 249 _prev = nextSb->_prev; 250 nextSb->_prev = this; 251 } 252} 253 254 255void 256superblock::remove(void) 257{ 258 // Remove this superblock from a doubly-linked list. 259 if (_next) 260 _next->_prev = _prev; 261 if (_prev) 262 _prev->_next = _next; 263 264 _prev = NULL; 265 _next = NULL; 266} 267 268 269int 270superblock::isValid(void) 271{ 272 assert(_numBlocks > 0); 273 assert(_numAvailable <= _numBlocks); 274 assert(_sizeClass >= 0); 275 return 1; 276} 277 278 279void 280superblock::computeFullness(void) 281{ 282 assert(isValid()); 283 _fullness = (((SUPERBLOCK_FULLNESS_GROUP - 1) 284 * (getNumBlocks() - getNumAvailable())) / getNumBlocks()); 285} 286 287 288int 289superblock::getFullness(void) 290{ 291 assert(isValid()); 292 return _fullness; 293} 294 295} // namespace BPrivate 296 297#endif // _SUPERBLOCK_H_ 298