[176] | 1 | /* -*- C++ -*- */ |
---|
| 2 | |
---|
| 3 | #ifndef _ALIGNEDCHUNK_H_ |
---|
| 4 | #define _ALIGNEDCHUNK_H_ |
---|
| 5 | |
---|
| 6 | /* |
---|
| 7 | |
---|
| 8 | Heap Layers: An Extensible Memory Allocation Infrastructure |
---|
| 9 | |
---|
| 10 | Copyright (C) 2000-2003 by Emery Berger |
---|
| 11 | http://www.cs.umass.edu/~emery |
---|
| 12 | emery@cs.umass.edu |
---|
| 13 | |
---|
| 14 | This program is free software; you can redistribute it and/or modify |
---|
| 15 | it under the terms of the GNU General Public License as published by |
---|
| 16 | the Free Software Foundation; either version 2 of the License, or |
---|
| 17 | (at your option) any later version. |
---|
| 18 | |
---|
| 19 | This program is distributed in the hope that it will be useful, |
---|
| 20 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 21 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 22 | GNU General Public License for more details. |
---|
| 23 | |
---|
| 24 | You should have received a copy of the GNU General Public License |
---|
| 25 | along with this program; if not, write to the Free Software |
---|
| 26 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
---|
| 27 | |
---|
| 28 | */ |
---|
| 29 | |
---|
| 30 | #include <stdlib.h> |
---|
| 31 | #include <malloc.h> |
---|
| 32 | #include <assert.h> |
---|
| 33 | |
---|
| 34 | #include "bitindex.h" |
---|
| 35 | |
---|
| 36 | /* |
---|
| 37 | An aligned chunk is a chunk of memory |
---|
| 38 | containing a number of fixed-size "slots". |
---|
| 39 | As long as the chunk is naturally aligned, |
---|
| 40 | each slot will also be naturally aligned. |
---|
| 41 | |
---|
| 42 | This alignment allows us to use address masking to find |
---|
| 43 | which chunk a given pointer belongs to. |
---|
| 44 | |
---|
| 45 | All information about the chunk is stored at the end |
---|
| 46 | of the chunk. |
---|
| 47 | |
---|
| 48 | */ |
---|
| 49 | |
---|
| 50 | // AlignHeap aligns every memory request to chunkSize. |
---|
| 51 | // |
---|
| 52 | // If you know that memory allocations are always aligned to chunkSize |
---|
| 53 | // from your allocator of choice, don't use AlignHeap because it |
---|
| 54 | // will waste memory. |
---|
| 55 | |
---|
| 56 | namespace HL { |
---|
| 57 | |
---|
| 58 | template <int chunkSize, class Super> |
---|
| 59 | class AlignHeap { |
---|
| 60 | public: |
---|
| 61 | inline void * malloc (size_t sz) { |
---|
| 62 | // Get a piece of memory large enough to be able to guarantee alignment. |
---|
| 63 | void * buf = ::malloc (sz + chunkSize); |
---|
| 64 | // Align the buffer. |
---|
| 65 | void * alignedBuf = (void *) (((unsigned long) buf + sizeof(unsigned long) + chunkSize - 1) & -chunkSize); |
---|
| 66 | // Record the original buffer's address right behind the aligned part. |
---|
| 67 | assert ((unsigned long) alignedBuf - (unsigned long) buf > sizeof(unsigned long)); |
---|
| 68 | *((unsigned long *) alignedBuf - 1) = (unsigned long) buf; |
---|
| 69 | return alignedBuf; |
---|
| 70 | } |
---|
| 71 | |
---|
| 72 | void free (void * ptr) { |
---|
| 73 | // Get the original buffer's address and free that. |
---|
| 74 | ::free ((void *) *((unsigned long *) ptr - 1)); |
---|
| 75 | } |
---|
| 76 | }; |
---|
| 77 | |
---|
| 78 | |
---|
| 79 | // An aligned chunk is of size chunkSize and is divided up into 32 pieces |
---|
| 80 | // of size slotSize. The 32nd one will not be available for allocation |
---|
| 81 | // because it is used for 'header' information (albeit stored in the footer). |
---|
| 82 | |
---|
| 83 | // Some restrictions: chunkSize MUST BE A POWER OF TWO. |
---|
| 84 | // slotSize MUST BE AT LEAST THE SIZE OF A DOUBLE. |
---|
| 85 | |
---|
| 86 | // The amount of memory that this approach wastes is small in practice: |
---|
| 87 | // For one aligned chunk, utilization is 31/32 = 97%. |
---|
| 88 | // For two nested chunks, utilization is (31/32)^2 = 94%. |
---|
| 89 | // For three nested chunks, utilization is (31/32)^3 = 91%. |
---|
| 90 | // Note that the smallest possible size of a three-deep aligned chunk |
---|
| 91 | // is 32 * 32 * 32 * 32 = one megabyte. |
---|
| 92 | |
---|
| 93 | template <int chunkSize, int slotSize> |
---|
| 94 | class AlignedChunk { |
---|
| 95 | public: |
---|
| 96 | |
---|
| 97 | AlignedChunk (void) |
---|
| 98 | : prev (NULL), |
---|
| 99 | next (NULL), |
---|
| 100 | status (ACQUIRED), |
---|
| 101 | inUse (0) |
---|
| 102 | { |
---|
| 103 | // Make sure there's enough slop to let us store the chunk information! |
---|
| 104 | assert (getNumSlots() * slotSize + sizeof(AlignedChunk) <= chunkSize); |
---|
| 105 | // The slot size must be at least large enough to hold a double. |
---|
| 106 | assert (slotSize == align(slotSize)); |
---|
| 107 | // Initialize the bitmap. |
---|
| 108 | freeBitmap = 0; |
---|
| 109 | // Block the last slot. |
---|
| 110 | BitIndex::set (freeBitmap, 0); |
---|
| 111 | emptyBitmap = freeBitmap; |
---|
| 112 | } |
---|
| 113 | |
---|
| 114 | ~AlignedChunk (void) |
---|
| 115 | {} |
---|
| 116 | |
---|
| 117 | |
---|
| 118 | // Get and put slots. |
---|
| 119 | // These are ATOMIC and lock-free. |
---|
| 120 | |
---|
| 121 | // Get returns NULL iff there are no slots available. |
---|
| 122 | void * getSlot (void) { |
---|
| 123 | RETRY_UNSET: |
---|
| 124 | unsigned long currBitmap = freeBitmap; |
---|
| 125 | // If currBitmap is all ones, everything is in use. |
---|
| 126 | // Just return NULL. |
---|
| 127 | if (currBitmap == (unsigned long) -1) { |
---|
| 128 | assert (inUse == getNumSlots()); |
---|
| 129 | return NULL; |
---|
| 130 | } |
---|
| 131 | // Find an unset bit. |
---|
| 132 | // We flip the bits in currBitmap and find the index of a one bit |
---|
| 133 | // (which corresponds to the index of a zero in currBitmap). |
---|
| 134 | int bitIndex; |
---|
| 135 | unsigned long oneBit = (~currBitmap) & (-((signed long) ~currBitmap)); |
---|
| 136 | assert (oneBit != 0); |
---|
| 137 | bitIndex = BitIndex::msb (oneBit); |
---|
| 138 | if (bitIndex > getNumSlots()) { |
---|
| 139 | assert (inUse == getNumSlots()); |
---|
| 140 | return NULL; |
---|
| 141 | } |
---|
| 142 | assert (inUse < getNumSlots()); |
---|
| 143 | assert (bitIndex < getNumSlots() + 1); |
---|
| 144 | // Set it. |
---|
| 145 | unsigned long oldBitmap = currBitmap; |
---|
| 146 | BitIndex::set (currBitmap, bitIndex); |
---|
| 147 | unsigned long updatedBitmap = InterlockedExchange ((long *) &freeBitmap, currBitmap); |
---|
| 148 | if (updatedBitmap == oldBitmap) { |
---|
| 149 | // Success. |
---|
| 150 | // Return a pointer to the appropriate slot. |
---|
| 151 | char * start = (char *) ((unsigned long) this & -chunkSize); |
---|
| 152 | inUse++; |
---|
| 153 | return start + slotSize * (getNumSlots() - bitIndex); |
---|
| 154 | } |
---|
| 155 | // Someone changed the bitmap before we were able to write it. |
---|
| 156 | // Try again. |
---|
| 157 | goto RETRY_UNSET; |
---|
| 158 | } |
---|
| 159 | |
---|
| 160 | |
---|
| 161 | // Put returns 1 iff the chunk is now completely empty. |
---|
| 162 | inline int putSlot (void * ptr) { |
---|
| 163 | assert (inUse >= 1); |
---|
| 164 | AlignedChunk * ch = getChunk (ptr); |
---|
| 165 | assert (ch == this); |
---|
| 166 | // Find the index of this pointer. |
---|
| 167 | // Since slotSize is known at compile time and is usually a power of two, |
---|
| 168 | // the divide should be turned into shifts and will be fast. |
---|
| 169 | char * start = (char *) ((unsigned long) ptr & -chunkSize); |
---|
| 170 | int bitIndex = getNumSlots() - (((unsigned long) ((char *) ptr - start)) / slotSize); |
---|
| 171 | RETRY_RESET: |
---|
| 172 | unsigned long currBitmap = freeBitmap; |
---|
| 173 | unsigned long oldBitmap = currBitmap; |
---|
| 174 | BitIndex::reset (currBitmap, bitIndex); |
---|
| 175 | unsigned long updatedBitmap = InterlockedExchange ((long *) &freeBitmap, currBitmap); |
---|
| 176 | if (updatedBitmap == oldBitmap) { |
---|
| 177 | // Success. |
---|
| 178 | inUse--; |
---|
| 179 | assert ((inUse != 0) || (currBitmap == emptyBitmap)); |
---|
| 180 | assert ((inUse == 0) || (currBitmap != emptyBitmap)); |
---|
| 181 | // Return 1 iff the chunk is now empty. |
---|
| 182 | if (currBitmap == emptyBitmap) { |
---|
| 183 | assert (inUse == 0); |
---|
| 184 | return 1; |
---|
| 185 | } else { |
---|
| 186 | assert (inUse > 0); |
---|
| 187 | return 0; |
---|
| 188 | } |
---|
| 189 | } |
---|
| 190 | // Try again. |
---|
| 191 | goto RETRY_RESET; |
---|
| 192 | } |
---|
| 193 | |
---|
| 194 | |
---|
| 195 | // How many slots are there in total? |
---|
| 196 | inline static int getNumSlots (void) { |
---|
| 197 | return 31; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | inline int isReleased (void) { |
---|
| 201 | return (status == RELEASED); |
---|
| 202 | } |
---|
| 203 | |
---|
| 204 | inline void acquire (void) { |
---|
| 205 | assert (status == RELEASED); |
---|
| 206 | status = ACQUIRED; |
---|
| 207 | } |
---|
| 208 | |
---|
| 209 | inline void release (void) { |
---|
| 210 | assert (status == ACQUIRED); |
---|
| 211 | status = RELEASED; |
---|
| 212 | } |
---|
| 213 | |
---|
| 214 | // Find a chunk for a given slot. |
---|
| 215 | inline static AlignedChunk * getChunk (void * slot) { |
---|
| 216 | // Here's where the alignment is CRITICAL!! |
---|
| 217 | // Verify that chunkSize is a power of two. |
---|
| 218 | assert ((chunkSize & (chunkSize - 1)) == 0); |
---|
| 219 | // Mask off the slot to find the start of the chunkSize block. |
---|
| 220 | char * start = (char *) ((unsigned long) slot & -chunkSize); |
---|
| 221 | // Find the end of the block. |
---|
| 222 | char * eob = (start + chunkSize); |
---|
| 223 | // Now locate the 'header' (in this case, it's actually a footer). |
---|
| 224 | char * headerPos = eob - sizeof(AlignedChunk); |
---|
| 225 | return (AlignedChunk *) headerPos; |
---|
| 226 | } |
---|
| 227 | |
---|
| 228 | |
---|
| 229 | // Add doubly linked-list operations. |
---|
| 230 | AlignedChunk * getNext (void) { return next; } |
---|
| 231 | AlignedChunk * getPrev (void) { return prev; } |
---|
| 232 | void setNext (AlignedChunk * p) { next = p; } |
---|
| 233 | void setPrev (AlignedChunk * p) { prev = p; } |
---|
| 234 | |
---|
| 235 | private: |
---|
| 236 | |
---|
| 237 | enum { RELEASED = 0, ACQUIRED = 1 }; |
---|
| 238 | |
---|
| 239 | static inline size_t align (size_t sz) { |
---|
| 240 | return (sz + (sizeof(double) - 1)) & ~(sizeof(double) - 1); |
---|
| 241 | } |
---|
| 242 | |
---|
| 243 | int inUse; // For debugging only. |
---|
| 244 | unsigned long freeBitmap; |
---|
| 245 | unsigned long emptyBitmap; |
---|
| 246 | int status; |
---|
| 247 | AlignedChunk * prev; |
---|
| 248 | AlignedChunk * next; |
---|
| 249 | }; |
---|
| 250 | |
---|
| 251 | |
---|
| 252 | // AlignedChunkHeap manages a number of chunks. |
---|
| 253 | |
---|
| 254 | template <int maxFree, int chunkSize, int slotSize, class Super> |
---|
| 255 | class AlignedChunkHeap : public Super { |
---|
| 256 | public: |
---|
| 257 | |
---|
| 258 | AlignedChunkHeap (void) |
---|
| 259 | : chunkList (NULL), |
---|
| 260 | length (0) |
---|
| 261 | {} |
---|
| 262 | |
---|
| 263 | virtual ~AlignedChunkHeap (void) |
---|
| 264 | { |
---|
| 265 | chunkType * ch, * tmp; |
---|
| 266 | ch = chunkList; |
---|
| 267 | while (ch != NULL) { |
---|
| 268 | tmp = ch; |
---|
| 269 | ch = ch->getNext(); |
---|
| 270 | assert (tmp->isReleased()); |
---|
| 271 | Super::free ((char *) ((unsigned long) tmp & -chunkSize)); |
---|
| 272 | } |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | // Malloc a CHUNK. Returns a pointer to the start of the allocated block. |
---|
| 276 | inline void * malloc (size_t sz) |
---|
| 277 | { |
---|
| 278 | assert (sz == chunkSize); |
---|
| 279 | chunkType * ch; |
---|
| 280 | // Get a chunk from our chunk list |
---|
| 281 | // or make one. |
---|
| 282 | if (chunkList != NULL) { |
---|
| 283 | ch = chunkList; |
---|
| 284 | chunkList = chunkList->getNext(); |
---|
| 285 | length--; |
---|
| 286 | ch->acquire(); |
---|
| 287 | } else { |
---|
| 288 | // Make a buffer large enough to hold the chunk. |
---|
| 289 | void * buf = Super::malloc (chunkSize); |
---|
| 290 | // The buffer MUST BE ALIGNED. |
---|
| 291 | assert ((unsigned long) buf == ((unsigned long) buf & -chunkSize)); |
---|
| 292 | // Instantiate the chunk "header" (actually the footer) |
---|
| 293 | // at the end of the chunk. |
---|
| 294 | ch = new (chunkType::getChunk (buf)) chunkType; |
---|
| 295 | } |
---|
| 296 | // Now return the start of the chunk's buffer. |
---|
| 297 | assert (!ch->isReleased()); |
---|
| 298 | return (void *) ((unsigned long) ch & -chunkSize); |
---|
| 299 | } |
---|
| 300 | |
---|
| 301 | // Free a CHUNK. |
---|
| 302 | // The pointer is to the chunk header. |
---|
| 303 | inline void free (void * ptr) |
---|
| 304 | { |
---|
| 305 | chunkType * ch = (chunkType *) AlignedChunk<chunkSize, slotSize>::getChunk(ptr); |
---|
| 306 | assert (ch->isReleased()); |
---|
| 307 | if (length > maxFree) { |
---|
| 308 | Super::free ((void *) ((unsigned long) ch & -chunkSize)); |
---|
| 309 | } else { |
---|
| 310 | ch->setNext (chunkList); |
---|
| 311 | chunkList = ch; |
---|
| 312 | length++; |
---|
| 313 | } |
---|
| 314 | } |
---|
| 315 | |
---|
| 316 | size_t size (void * ptr) { |
---|
| 317 | return slotSize; |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | private: |
---|
| 321 | |
---|
| 322 | typedef AlignedChunk<chunkSize, slotSize> chunkType; |
---|
| 323 | |
---|
| 324 | chunkType * chunkList; |
---|
| 325 | int length; |
---|
| 326 | }; |
---|
| 327 | |
---|
| 328 | |
---|
| 329 | // An AlignedSlotHeap holds at most one chunk. |
---|
| 330 | // When all of the slots are allocated from the chunk, |
---|
| 331 | // the chunk is "released" so that it may be freed back |
---|
| 332 | // to the super heap when all of its slots are freed. |
---|
| 333 | |
---|
| 334 | template <int chunkSize, int slotSize, class Super> |
---|
| 335 | class AlignedSlotHeap : public Super { |
---|
| 336 | public: |
---|
| 337 | |
---|
| 338 | AlignedSlotHeap (void) |
---|
| 339 | : myChunk (NULL) |
---|
| 340 | {} |
---|
| 341 | |
---|
| 342 | virtual ~AlignedSlotHeap (void) { |
---|
| 343 | // Note that this is NOT enough to completely clean up after ourselves!! |
---|
| 344 | if (myChunk != NULL) { |
---|
| 345 | myChunk->release(); |
---|
| 346 | Super::free ((void *) ((unsigned long) myChunk & -chunkSize)); |
---|
| 347 | } |
---|
| 348 | } |
---|
| 349 | |
---|
| 350 | // Malloc a SLOT. |
---|
| 351 | // Use up a chunk, if we've got one. |
---|
| 352 | // Once it's used up, 'release it' and get another one. |
---|
| 353 | inline void * malloc (size_t sz) { |
---|
| 354 | assert (sz <= slotSize); |
---|
| 355 | void * ptr = NULL; |
---|
| 356 | while (ptr == NULL) { |
---|
| 357 | if (myChunk == NULL) { |
---|
| 358 | myChunk = AlignedChunk<chunkSize, slotSize>::getChunk(Super::malloc (chunkSize)); |
---|
| 359 | } |
---|
| 360 | ptr = myChunk->getSlot(); |
---|
| 361 | if (ptr == NULL) { |
---|
| 362 | // This chunk is completely in use. |
---|
| 363 | // "Release" it. |
---|
| 364 | myChunk->release(); |
---|
| 365 | myChunk = NULL; |
---|
| 366 | } |
---|
| 367 | }; |
---|
| 368 | return ptr; |
---|
| 369 | } |
---|
| 370 | |
---|
| 371 | // Free a SLOT. |
---|
| 372 | // If the chunk is now completely empty and has been 'released', |
---|
| 373 | // free the whole chunk. |
---|
| 374 | inline void free (void * ptr) |
---|
| 375 | { |
---|
| 376 | // Find out which chunk this slot belongs to. |
---|
| 377 | AlignedChunk<chunkSize, slotSize> * ch = AlignedChunk<chunkSize, slotSize>::getChunk (ptr); |
---|
| 378 | // Return it to its chunk. |
---|
| 379 | int empty = ch->putSlot (ptr); |
---|
| 380 | if (empty && ch->isReleased()) { |
---|
| 381 | Super::free ((void *) ((unsigned long) ch & -chunkSize)); |
---|
| 382 | } |
---|
| 383 | } |
---|
| 384 | |
---|
| 385 | private: |
---|
| 386 | |
---|
| 387 | // A one chunk buffer. Emptied when the chunk is completely allocated. |
---|
| 388 | AlignedChunk<chunkSize, slotSize> * myChunk; |
---|
| 389 | |
---|
| 390 | }; |
---|
| 391 | |
---|
| 392 | |
---|
| 393 | template <int maxFree, int chunkSize, int slotSize, class Super> |
---|
| 394 | class AlignedChunkHeapFoo : public AlignedSlotHeap<chunkSize, slotSize, AlignedChunkHeap<maxFree, chunkSize, slotSize, Super> > {}; |
---|
| 395 | |
---|
| 396 | }; |
---|
| 397 | |
---|
| 398 | #endif |
---|