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 40 namespace BPrivate { 41 42 class hoardHeap; // forward declaration 43 class processHeap; // forward declaration 44 45 class 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 146 hoardHeap * 147 superblock::getOwner(void) 148 { 149 assert(isValid()); 150 hoardHeap *o = _owner; 151 return o; 152 } 153 154 155 void 156 superblock::setOwner(hoardHeap *o) 157 { 158 assert(isValid()); 159 _owner = o; 160 } 161 162 163 block * 164 superblock::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 187 void 188 superblock::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 202 int 203 superblock::getNumAvailable(void) 204 { 205 assert(isValid()); 206 return _numAvailable; 207 } 208 209 210 int 211 superblock::getNumBlocks(void) 212 { 213 assert(isValid()); 214 return _numBlocks; 215 } 216 217 218 int 219 superblock::getBlockSizeClass(void) 220 { 221 assert(isValid()); 222 return _sizeClass; 223 } 224 225 226 superblock * const 227 superblock::getNext(void) 228 { 229 assert(isValid()); 230 return _next; 231 } 232 233 superblock * const 234 superblock::getPrev(void) 235 { 236 assert(isValid()); 237 return _prev; 238 } 239 240 241 void 242 superblock::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 255 void 256 superblock::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 269 int 270 superblock::isValid(void) 271 { 272 assert(_numBlocks > 0); 273 assert(_numAvailable <= _numBlocks); 274 assert(_sizeClass >= 0); 275 return 1; 276 } 277 278 279 void 280 superblock::computeFullness(void) 281 { 282 assert(isValid()); 283 _fullness = (((SUPERBLOCK_FULLNESS_GROUP - 1) 284 * (getNumBlocks() - getNumAvailable())) / getNumBlocks()); 285 } 286 287 288 int 289 superblock::getFullness(void) 290 { 291 assert(isValid()); 292 return _fullness; 293 } 294 295 } // namespace BPrivate 296 297 #endif // _SUPERBLOCK_H_ 298