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