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
35namespace BPrivate {
36
37class processHeap;
38
39class 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
225void
226hoardHeap::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
237void
238hoardHeap::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
247void
248hoardHeap::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
259void
260hoardHeap::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
269void
270hoardHeap::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
280int
281hoardHeap::maxInUse(int sizeclass)
282{
283	assert(_magic == HEAP_MAGIC);
284	return _stats[sizeclass].getUmax();
285}
286
287
288int
289hoardHeap::maxAllocated(int sizeclass)
290{
291	assert(_magic == HEAP_MAGIC);
292	return _stats[sizeclass].getAmax();
293}
294#endif	// HEAP_STATS
295
296
297superblock *
298hoardHeap::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
385int
386hoardHeap::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
399size_t
400hoardHeap::sizeFromClass(const int sizeclass)
401{
402	assert(sizeclass >= 0);
403	assert(sizeclass < SIZE_CLASSES);
404	return _sizeTable[sizeclass];
405}
406
407
408int
409hoardHeap::getReleaseThreshold(const int sizeclass)
410{
411	assert(sizeclass >= 0);
412	assert(sizeclass < SIZE_CLASSES);
413	return _threshold[sizeclass];
414}
415
416
417int
418hoardHeap::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
431void
432hoardHeap::lock(void)
433{
434	assert(_magic == HEAP_MAGIC);
435	hoardLock(_lock);
436}
437
438
439void
440hoardHeap::unlock(void)
441{
442	assert(_magic == HEAP_MAGIC);
443	hoardUnlock(_lock);
444}
445
446
447void
448hoardHeap::initLock(void)
449{
450	// Initialize the per-heap lock.
451	hoardLockInit(_lock, "hoard heap");
452}
453
454
455size_t
456hoardHeap::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
465void
466hoardHeap::setIndex(int i)
467{
468	_index = i;
469}
470
471
472int
473hoardHeap::getIndex(void)
474{
475	return _index;
476}
477
478
479void
480hoardHeap::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
495superblock *
496hoardHeap::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