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 /* hoardHeap, the base class for threadHeap and processHeap. */
21
22 #ifndef _HEAP_H_
23 #define _HEAP_H_
24
25 #include <OS.h>
26 #include <cstddef>
27
28 #include "config.h"
29
30 #include "arch-specific.h"
31 #include "superblock.h"
32 #include "heapstats.h"
33
34
35 namespace BPrivate {
36
37 class processHeap;
38
39 class hoardHeap {
40 public:
41 hoardHeap(void);
42
43 // A superblock that holds more than one object must hold at least
44 // this many bytes.
45 enum { SUPERBLOCK_SIZE = 8192 };
46
47 // A thread heap must be at least 1/EMPTY_FRACTION empty before we
48 // start returning superblocks to the process heap.
49 enum { EMPTY_FRACTION = SUPERBLOCK_FULLNESS_GROUP - 1 };
50
51 // Reset value for the least-empty bin. The last bin
52 // (SUPERBLOCK_FULLNESS_GROUP-1) is for completely full superblocks,
53 // so we use the next-to-last bin.
54 enum { RESET_LEAST_EMPTY_BIN = SUPERBLOCK_FULLNESS_GROUP - 2 };
55
56 // The number of empty superblocks that we allow any thread heap to
57 // hold once the thread heap has fallen below 1/EMPTY_FRACTION
58 // empty.
59 enum { MAX_EMPTY_SUPERBLOCKS = EMPTY_FRACTION };
60
61 //
62 // The number of size classes. This combined with the
63 // SIZE_CLASS_BASE determine the maximum size of an object.
64 //
65 // NB: Once this is changed, you must execute maketable.cpp and put
66 // the generated values into heap.cpp.
67
68 #if MAX_INTERNAL_FRAGMENTATION == 2
69 enum { SIZE_CLASSES = 115 };
70 #elif MAX_INTERNAL_FRAGMENTATION == 6
71 enum { SIZE_CLASSES = 46 };
72 #elif MAX_INTERNAL_FRAGMENTATION == 10
73 enum { SIZE_CLASSES = 32 };
74 #else
75 # error "Undefined size class base."
76 #endif
77
78 // Every object is aligned so that it can always hold any type.
79 enum { ALIGNMENT = HAIKU_MEMORY_ALIGNMENT };
80
81 // ANDing with this rounds to ALIGNMENT.
82 enum { ALIGNMENT_MASK = ALIGNMENT - 1 };
83
84 // Used for sanity checking.
85 enum { HEAP_MAGIC = 0x0badcafe };
86
87 // Get the usage and allocated statistics.
88 inline void getStats(int sizeclass, int &U, int &A);
89
90
91 #if HEAP_STATS
92 // How much is the maximum ever in use for this size class?
93 inline int maxInUse(int sizeclass);
94
95 // How much is the maximum memory allocated for this size class?
96 inline int maxAllocated(int sizeclass);
97 #endif
98
99 // Insert a superblock into our list.
100 void insertSuperblock(int sizeclass, superblock *sb, processHeap *pHeap);
101
102 // Remove the superblock with the most free space.
103 superblock *removeMaxSuperblock(int sizeclass);
104
105 // Find an available superblock (i.e., with some space in it).
106 inline superblock *findAvailableSuperblock(int sizeclass,
107 block * &b, processHeap * pHeap);
108
109 // Lock this heap.
110 inline void lock(void);
111
112 // Unlock this heap.
113 inline void unlock(void);
114
115 // Init this heap lock.
116 inline void initLock(void);
117
118 // Set our index number (which heap we are).
119 inline void setIndex(int i);
120
121 // Get our index number (which heap we are).
122 inline int getIndex(void);
123
124 // Free a block into a superblock.
125 // This is used by processHeap::free().
126 // Returns 1 iff the superblock was munmapped.
127 int freeBlock(block * &b, superblock * &sb, int sizeclass,
128 processHeap * pHeap);
129
130 //// Utility functions ////
131
132 // Return the size class for a given size.
133 inline static int sizeClass(const size_t sz);
134
135 // Return the size corresponding to a given size class.
136 inline static size_t sizeFromClass(const int sizeclass);
137
138 // Return the release threshold corresponding to a given size class.
139 inline static int getReleaseThreshold(const int sizeclass);
140
141 // Return how many blocks of a given size class fit into a superblock.
142 inline static int numBlocks(const int sizeclass);
143
144 // Align a value.
145 inline static size_t align(const size_t sz);
146
147 private:
148 // Disable copying and assignment.
149
150 hoardHeap(const hoardHeap &);
151 const hoardHeap & operator=(const hoardHeap &);
152
153 // Recycle a superblock.
154 inline void recycle(superblock *);
155
156 // Reuse a superblock (if one is available).
157 inline superblock *reuse(int sizeclass);
158
159 // Remove a particular superblock.
160 void removeSuperblock(superblock *, int sizeclass);
161
162 // Move a particular superblock from one bin to another.
163 void moveSuperblock(superblock *,
164 int sizeclass, int fromBin, int toBin);
165
166 // Update memory in-use and allocated statistics.
167 // (*UStats = just update U.)
168 inline void incStats(int sizeclass, int updateU, int updateA);
169 inline void incUStats(int sizeclass);
170
171 inline void decStats(int sizeclass, int updateU, int updateA);
172 inline void decUStats(int sizeclass);
173
174 //// Members ////
175
176 // Heap statistics.
177 heapStats _stats[SIZE_CLASSES];
178
179 // The per-heap lock.
180 hoardLockType _lock;
181
182 // Which heap this is (0 = the process (global) heap).
183 int _index;
184
185 // Reusable superblocks.
186 superblock *_reusableSuperblocks;
187 int _reusableSuperblocksCount;
188
189 // Lists of superblocks.
190 superblock *_superblocks[SUPERBLOCK_FULLNESS_GROUP][SIZE_CLASSES];
191
192 // The current least-empty superblock bin.
193 int _leastEmptyBin[SIZE_CLASSES];
194
195 #if HEAP_DEBUG
196 // For sanity checking.
197 const unsigned long _magic;
198 #else
199 # define _magic HEAP_MAGIC
200 #endif
201
202 // The lookup table for size classes.
203 static size_t _sizeTable[SIZE_CLASSES];
204
205 // The lookup table for release thresholds.
206 static size_t _threshold[SIZE_CLASSES];
207
208 public:
209 static void initNumProcs(void);
210
211 protected:
212 // The maximum number of thread heaps we allow. (NOT the maximum
213 // number of threads -- Hoard imposes no such limit.) This must be
214 // a power of two! NB: This number is twice the maximum number of
215 // PROCESSORS supported by Hoard.
216 static int fMaxThreadHeaps;
217
218 // number of CPUs, cached
219 static int _numProcessors;
220 static int _numProcessorsMask;
221 };
222
223
224
225 void
incStats(int sizeclass,int updateU,int updateA)226 hoardHeap::incStats(int sizeclass, int updateU, int updateA)
227 {
228 assert(_magic == HEAP_MAGIC);
229 assert(updateU >= 0);
230 assert(updateA >= 0);
231 assert(sizeclass >= 0);
232 assert(sizeclass < SIZE_CLASSES);
233 _stats[sizeclass].incStats(updateU, updateA);
234 }
235
236
237 void
incUStats(int sizeclass)238 hoardHeap::incUStats(int sizeclass)
239 {
240 assert(_magic == HEAP_MAGIC);
241 assert(sizeclass >= 0);
242 assert(sizeclass < SIZE_CLASSES);
243 _stats[sizeclass].incUStats();
244 }
245
246
247 void
decStats(int sizeclass,int updateU,int updateA)248 hoardHeap::decStats(int sizeclass, int updateU, int updateA)
249 {
250 assert(_magic == HEAP_MAGIC);
251 assert(updateU >= 0);
252 assert(updateA >= 0);
253 assert(sizeclass >= 0);
254 assert(sizeclass < SIZE_CLASSES);
255 _stats[sizeclass].decStats(updateU, updateA);
256 }
257
258
259 void
decUStats(int sizeclass)260 hoardHeap::decUStats(int sizeclass)
261 {
262 assert(_magic == HEAP_MAGIC);
263 assert(sizeclass >= 0);
264 assert(sizeclass < SIZE_CLASSES);
265 _stats[sizeclass].decUStats();
266 }
267
268
269 void
getStats(int sizeclass,int & U,int & A)270 hoardHeap::getStats(int sizeclass, int &U, int &A)
271 {
272 assert(_magic == HEAP_MAGIC);
273 assert(sizeclass >= 0);
274 assert(sizeclass < SIZE_CLASSES);
275 _stats[sizeclass].getStats(U, A);
276 }
277
278
279 #if HEAP_STATS
280 int
maxInUse(int sizeclass)281 hoardHeap::maxInUse(int sizeclass)
282 {
283 assert(_magic == HEAP_MAGIC);
284 return _stats[sizeclass].getUmax();
285 }
286
287
288 int
maxAllocated(int sizeclass)289 hoardHeap::maxAllocated(int sizeclass)
290 {
291 assert(_magic == HEAP_MAGIC);
292 return _stats[sizeclass].getAmax();
293 }
294 #endif // HEAP_STATS
295
296
297 superblock *
findAvailableSuperblock(int sizeclass,block * & b,processHeap * pHeap)298 hoardHeap::findAvailableSuperblock(int sizeclass,
299 block * &b, processHeap * pHeap)
300 {
301 assert(this);
302 assert(_magic == HEAP_MAGIC);
303 assert(sizeclass >= 0);
304 assert(sizeclass < SIZE_CLASSES);
305
306 superblock *sb = NULL;
307 int reUsed = 0;
308
309 // Look through the superblocks, starting with the almost-full ones
310 // and going to the emptiest ones. The Least Empty Bin for a
311 // sizeclass is a conservative approximation (fixed after one
312 // iteration) of the first bin that has superblocks in it, starting
313 // with (surprise) the least-empty bin.
314
315 for (int i = _leastEmptyBin[sizeclass]; i >= 0; i--) {
316 sb = _superblocks[i][sizeclass];
317 if (sb == NULL) {
318 if (i == _leastEmptyBin[sizeclass]) {
319 // There wasn't a superblock in this bin,
320 // so we adjust the least empty bin.
321 _leastEmptyBin[sizeclass]--;
322 }
323 } else if (sb->getNumAvailable() > 0) {
324 assert(sb->getOwner() == this);
325 break;
326 }
327 sb = NULL;
328 }
329
330 #if 1
331 if (sb == NULL) {
332 // Try to reuse a superblock.
333 sb = reuse(sizeclass);
334 if (sb) {
335 assert(sb->getOwner() == this);
336 reUsed = 1;
337 }
338 }
339 #endif
340
341 if (sb != NULL) {
342 // Sanity checks:
343 // This superblock is 'valid'.
344 assert(sb->isValid());
345 // This superblock has the right ownership.
346 assert(sb->getOwner() == this);
347
348 int oldFullness = sb->getFullness();
349
350 // Now get a block from the superblock.
351 // This superblock must have space available.
352 b = sb->getBlock();
353 assert(b != NULL);
354
355 // Update the stats.
356 incUStats(sizeclass);
357
358 if (reUsed) {
359 insertSuperblock(sizeclass, sb, pHeap);
360 // Fix the stats (since insert will just have incremented them
361 // by this amount).
362 decStats(sizeclass,
363 sb->getNumBlocks() - sb->getNumAvailable(),
364 sb->getNumBlocks());
365 } else {
366 // If we've crossed a fullness group,
367 // move the superblock.
368 int fullness = sb->getFullness();
369
370 if (fullness != oldFullness) {
371 // Move the superblock.
372 moveSuperblock(sb, sizeclass, oldFullness, fullness);
373 }
374 }
375 }
376 // Either we didn't find a superblock or we did and got a block.
377 assert((sb == NULL) || (b != NULL));
378 // Either we didn't get a block or we did and we also got a superblock.
379 assert((b == NULL) || (sb != NULL));
380
381 return sb;
382 }
383
384
385 int
sizeClass(const size_t sz)386 hoardHeap::sizeClass(const size_t sz)
387 {
388 // Find the size class for a given object size
389 // (the smallest i such that _sizeTable[i] >= sz).
390 int sizeclass = 0;
391 while (_sizeTable[sizeclass] < sz) {
392 sizeclass++;
393 assert(sizeclass < SIZE_CLASSES);
394 }
395 return sizeclass;
396 }
397
398
399 size_t
sizeFromClass(const int sizeclass)400 hoardHeap::sizeFromClass(const int sizeclass)
401 {
402 assert(sizeclass >= 0);
403 assert(sizeclass < SIZE_CLASSES);
404 return _sizeTable[sizeclass];
405 }
406
407
408 int
getReleaseThreshold(const int sizeclass)409 hoardHeap::getReleaseThreshold(const int sizeclass)
410 {
411 assert(sizeclass >= 0);
412 assert(sizeclass < SIZE_CLASSES);
413 return _threshold[sizeclass];
414 }
415
416
417 int
numBlocks(const int sizeclass)418 hoardHeap::numBlocks(const int sizeclass)
419 {
420 assert(sizeclass >= 0);
421 assert(sizeclass < SIZE_CLASSES);
422 const size_t s = sizeFromClass(sizeclass);
423 assert(s > 0);
424 const int blksize = align(sizeof(block) + s);
425 // Compute the number of blocks that will go into this superblock.
426 int nb = max_c(1, ((SUPERBLOCK_SIZE - sizeof(superblock)) / blksize));
427 return nb;
428 }
429
430
431 void
lock(void)432 hoardHeap::lock(void)
433 {
434 assert(_magic == HEAP_MAGIC);
435 hoardLock(_lock);
436 }
437
438
439 void
unlock(void)440 hoardHeap::unlock(void)
441 {
442 assert(_magic == HEAP_MAGIC);
443 hoardUnlock(_lock);
444 }
445
446
447 void
initLock(void)448 hoardHeap::initLock(void)
449 {
450 // Initialize the per-heap lock.
451 hoardLockInit(_lock, "hoard heap");
452 }
453
454
455 size_t
align(const size_t sz)456 hoardHeap::align(const size_t sz)
457 {
458 // Align sz up to the nearest multiple of ALIGNMENT.
459 // This is much faster than using multiplication
460 // and division.
461 return (sz + ALIGNMENT_MASK) & ~ALIGNMENT_MASK;
462 }
463
464
465 void
setIndex(int i)466 hoardHeap::setIndex(int i)
467 {
468 _index = i;
469 }
470
471
472 int
getIndex(void)473 hoardHeap::getIndex(void)
474 {
475 return _index;
476 }
477
478
479 void
recycle(superblock * sb)480 hoardHeap::recycle(superblock *sb)
481 {
482 assert(sb != NULL);
483 assert(sb->getOwner() == this);
484 assert(sb->getNumBlocks() > 1);
485 assert(sb->getNext() == NULL);
486 assert(sb->getPrev() == NULL);
487 assert(hoardHeap::numBlocks(sb->getBlockSizeClass()) > 1);
488 sb->insertBefore(_reusableSuperblocks);
489 _reusableSuperblocks = sb;
490 ++_reusableSuperblocksCount;
491 // printf ("count: %d => %d\n", getIndex(), _reusableSuperblocksCount);
492 }
493
494
495 superblock *
reuse(int sizeclass)496 hoardHeap::reuse(int sizeclass)
497 {
498 if (_reusableSuperblocks == NULL)
499 return NULL;
500
501 // Make sure that we aren't using a sizeclass
502 // that is too big for a 'normal' superblock.
503 if (hoardHeap::numBlocks(sizeclass) <= 1)
504 return NULL;
505
506 // Pop off a superblock from the reusable-superblock list.
507 assert(_reusableSuperblocksCount > 0);
508 superblock *sb = _reusableSuperblocks;
509 _reusableSuperblocks = sb->getNext();
510 sb->remove();
511 assert(sb->getNumBlocks() > 1);
512 --_reusableSuperblocksCount;
513
514 // Reformat the superblock if necessary.
515 if (sb->getBlockSizeClass() != sizeclass) {
516 decStats(sb->getBlockSizeClass(),
517 sb->getNumBlocks() - sb->getNumAvailable(),
518 sb->getNumBlocks());
519
520 sb = new((char *)sb) superblock(numBlocks(sizeclass),
521 sizeclass, this);
522
523 incStats(sizeclass,
524 sb->getNumBlocks() - sb->getNumAvailable(),
525 sb->getNumBlocks());
526 }
527
528 assert(sb->getOwner() == this);
529 assert(sb->getBlockSizeClass() == sizeclass);
530 return sb;
531 }
532
533 } // namespace BPrivate
534
535 #endif // _HEAP_H_
536