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