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