1 /*
2
3 This file is part of the Maude 2 interpreter.
4
5 Copyright 1997-2003 SRI International, Menlo Park, CA 94025, USA.
6
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
20
21 */
22
23 //
24 // Class for small garbage collected chunks of memory.
25 //
26 #ifndef _memoryCell_hh_
27 #define _memoryCell_hh_
28 #include "sort.hh"
29
30 class MemoryCell
31 {
32 NO_COPYING(MemoryCell);
33 //
34 // MemoryCells can only be made via allocateMemoryCell().
35 //
MemoryCell()36 MemoryCell(){};
37
38 public:
39 //
40 // This is the raison d'etre for MemoryCell - fast allocation
41 // of small garbage collected chunks of memory.
42 //
43 static MemoryCell* allocateMemoryCell();
44 static void* allocateStorage(size_t bytesNeeded);
45 //
46 // Normally we just inform the allocator at times when all the non-garbage
47 // is accessible via root pointers.
48 //
49 static void okToCollectGarbage();
50 //
51 // Sometime we want separate the check and the call to the garbage collector
52 // so we can do some extra work just before a garbage collect to make
53 // sure all non-garbage is accessible from root pointers.
54 //
55 static bool wantToCollectGarbage();
56 static void collectGarbage();
57
58 static void setShowGC(bool polarity);
59
60 //
61 // Access to the unused byte and half word in a raw memory cell.
62 //
63 int getHalfWord() const;
64 void setHalfWord(int hw);
65 int getByte() const;
66 void setByte(int bt);
67 //
68 // Flags 1, 2, 4, 8, 16 and 32 are available for derived classes.
69 // Flags 64 and 128 are reserved for garbage collector.
70 //
71 bool getFlag(int flag) const;
72 void setFlag(int flag);
73 void clearFlag(int flag);
74 void copySetFlags(int flags, const MemoryCell* other);
75 //
76 // Access to garbage collector flags. We can't allow marked flag
77 // to be cleared and it only makes sense to clear the call dtor
78 // flag if we are clearing all flags other than marked.
79 //
80 bool isMarked() const;
81 void setMarked();
82 bool needToCallDtor() const;
83 void setCallDtor();
84 //
85 // This is needed when a fresh cell is allocated. The reason
86 // for not doing this in the allocation code is to allow the compiler
87 // to combine clearing all flags with immediately setting one or
88 // more flags.
89 //
90 void clearAllFlags();
91 //
92 // This is needed when we reallocate a node that is already in use
93 // (for in-place replacement of a subterm); the marked flag must
94 // be preserved.
95 //
96 void clearAllExceptMarked();
97 //
98 // This is used when a fresh cell is allocated and we want to start
99 // with the flags in a state other than all clear.
100 //
101 void initFlags(int flags);
102
103 private:
104 enum Sizes
105 {
106 //
107 // Memory cells have this much extra memory allocated for
108 // derived classes to use. Some uses require at least room
109 // for 5 pointers so this is the minimum value.
110 //
111 NR_EXTRA_WORDS = 5 // minimum value seems best on average
112 };
113
114 enum Flags
115 {
116 MARKED = 64, // marked in most recent mark phase
117 CALL_DTOR = 128 // call DagNode::~DagNode() before reusing
118 };
119
120 enum MemoryManagementParameters
121 {
122 ARENA_SIZE = 5460, // arena size in nodes;
123 // 5460 * 6 + 1 + new/malloc_overhead <= 32768 words
124 RESERVE_SIZE = 256, // if fewer nodes left call GC when allowed
125 BUCKET_MULTIPLIER = 8, // to determine bucket size for huge allocations
126 MIN_BUCKET_SIZE = 256 * 1024 - 8, // bucket size for normal allocations
127 INITIAL_TARGET = 220 * 1024, // just under 8/9 of MIN_BUCKET_SIZE
128 TARGET_MULTIPLIER = 8 // to determine bucket usage target
129 };
130
131 struct Header;
132 struct FullSizeMemoryCell; // this is what we allocate internally
133 struct Arena; // arena of fixed size nodes
134 struct Bucket; // bucket of variable length allocations
135
136 static bool showGC; // do we report GC stats to user
137 //
138 // Arena management variables.
139 //
140 static int nrArenas;
141 static int nrNodesInUse;
142 static bool currentArenaPastActiveArena;
143 static bool needToCollectGarbage;
144 static Arena* firstArena;
145 static Arena* lastArena;
146 static Arena* currentArena;
147 static FullSizeMemoryCell* nextNode;
148 static FullSizeMemoryCell* endPointer;
149 static Arena* lastActiveArena;
150 static FullSizeMemoryCell* lastActiveNode;
151 //
152 // Bucket management variables.
153 //
154 static int nrBuckets; // total number of buckets
155 static Bucket* bucketList; // linked list of "in use" buckets
156 static Bucket* unusedList; // linked list of unused buckets
157 static size_t bucketStorage; // total amount of bucket storage (bytes)
158 static size_t storageInUse; // amount of bucket storage in use (bytes)
159 static size_t target; // amount to use before GC (bytes)
160
161 static Arena* allocateNewArena();
162 static void tidyArenas();
163 static MemoryCell* slowNew();
164 static void* slowAllocateStorage(size_t bytesNeeded);
165
166 void callDtor();
167
168 #ifdef GC_DEBUG
169 static void stompArenas();
170 static void checkArenas();
171 static void checkInvariant();
172 static void dumpMemoryVariables(ostream& s);
173 #endif
174
175 MachineWord filler[NR_EXTRA_WORDS];
176 static const int dagNodeSize;
177 };
178
179 //
180 // Header info associated to but not in each MemoryCell.
181 // Header occupies one machine word, but actually we only need
182 // two flag bits for memory management. The remaining storage
183 // is made available to the MemoryCell.
184 //
185 struct MemoryCell::Header
186 {
187 short halfWord;
188 Byte byte;
189 Ubyte flags;
190 };
191
192 //
193 // A FullSizeMemoryCell is a MemoryCell with associated
194 // header info. The header info is actually at the end of the cell.
195 //
196 struct MemoryCell::FullSizeMemoryCell : MemoryCell
197 {
198 Header h;
199 };
200
201 struct MemoryCell::Bucket
202 {
203 size_t bytesFree;
204 void* nextFree;
205 size_t nrBytes;
206 Bucket* nextBucket;
207 };
208
209 inline int
getHalfWord() const210 MemoryCell::getHalfWord() const
211 {
212 return (static_cast<const FullSizeMemoryCell*>(this))->h.halfWord;
213 }
214
215 inline void
setHalfWord(int hw)216 MemoryCell::setHalfWord(int hw)
217 {
218 (static_cast<FullSizeMemoryCell*>(this))->h.halfWord = hw;
219 }
220
221 inline int
getByte() const222 MemoryCell::getByte() const
223 {
224 return (static_cast<const FullSizeMemoryCell*>(this))->h.byte;
225 }
226
227 inline void
setByte(int bt)228 MemoryCell::setByte(int bt)
229 {
230 (static_cast<FullSizeMemoryCell*>(this))->h.byte = bt;
231 }
232
233 inline bool
getFlag(int flag) const234 MemoryCell::getFlag(int flag) const
235 {
236 return (static_cast<const FullSizeMemoryCell*>(this))->h.flags & flag;
237 }
238
239 inline void
setFlag(int flag)240 MemoryCell::setFlag(int flag)
241 {
242 (static_cast<FullSizeMemoryCell*>(this))->h.flags |= flag;
243 }
244
245 inline void
clearAllFlags()246 MemoryCell::clearAllFlags()
247 {
248 (static_cast<FullSizeMemoryCell*>(this))->h.flags = 0;
249 }
250
251 inline void
initFlags(int flags)252 MemoryCell::initFlags(int flags)
253 {
254 (static_cast<FullSizeMemoryCell*>(this))->h.flags = flags;
255 }
256
257 inline void
clearFlag(int flag)258 MemoryCell::clearFlag(int flag)
259 {
260 (static_cast<FullSizeMemoryCell*>(this))->h.flags &= ~flag;
261 }
262
263 inline void
copySetFlags(int flags,const MemoryCell * other)264 MemoryCell::copySetFlags(int flags, const MemoryCell* other)
265 {
266 (static_cast<FullSizeMemoryCell*>(this))->h.flags |= flags &
267 (static_cast<const FullSizeMemoryCell*>(other))->h.flags;
268 }
269
270 inline bool
isMarked() const271 MemoryCell::isMarked() const
272 {
273 return getFlag(MARKED);
274 }
275
276 inline void
setMarked()277 MemoryCell::setMarked()
278 {
279 ++nrNodesInUse;
280 setFlag(MARKED);
281 }
282
283 inline void
clearAllExceptMarked()284 MemoryCell::clearAllExceptMarked()
285 {
286 clearFlag(~MARKED);
287 }
288
289 inline bool
needToCallDtor() const290 MemoryCell::needToCallDtor() const
291 {
292 return getFlag(CALL_DTOR);
293 }
294
295 inline void
setCallDtor()296 MemoryCell::setCallDtor()
297 {
298 setFlag(CALL_DTOR);
299 }
300
301 inline void
okToCollectGarbage()302 MemoryCell::okToCollectGarbage()
303 {
304 if (needToCollectGarbage)
305 collectGarbage();
306 }
307
308 inline bool
wantToCollectGarbage()309 MemoryCell::wantToCollectGarbage()
310 {
311 return needToCollectGarbage;
312 }
313
314 inline void*
allocateStorage(size_t bytesNeeded)315 MemoryCell::allocateStorage(size_t bytesNeeded)
316 {
317 Assert(bytesNeeded % sizeof(MachineWord) == 0,
318 "only whole machine words can be allocated");
319 storageInUse += bytesNeeded;
320 if (storageInUse > target)
321 needToCollectGarbage = true;
322 for (Bucket* b = bucketList; b; b = b->nextBucket)
323 {
324 if (b->bytesFree >= bytesNeeded)
325 {
326 b->bytesFree -= bytesNeeded;
327 void* t = b->nextFree;
328 b->nextFree = static_cast<char*>(t) + bytesNeeded;
329 return t;
330 }
331 }
332 return slowAllocateStorage(bytesNeeded);
333 }
334
335 inline void
setShowGC(bool polarity)336 MemoryCell::setShowGC(bool polarity)
337 {
338 showGC = polarity;
339 }
340
341 inline void
callDtor()342 MemoryCell::callDtor()
343 {
344 //
345 // MemoryCell cannot have a virtual destructor since we want to
346 // avoid a virtual function table pointer. Instead we assume
347 // it is a DagNode and crosscast it. This means that only classes
348 // derived from DagNode can use the call dtor flag.
349 //
350 (static_cast<DagNode*>(static_cast<void*>(this)))->~DagNode();
351 }
352
353 inline MemoryCell*
allocateMemoryCell()354 MemoryCell::allocateMemoryCell()
355 {
356 #ifdef GC_DEBUG
357 checkInvariant();
358 #endif
359 FullSizeMemoryCell* e = endPointer;
360 for (FullSizeMemoryCell* c = nextNode; c != e; c++)
361 {
362 if ((c->h.flags & (MARKED | CALL_DTOR)) == 0)
363 {
364 nextNode = c + 1;
365 return c;
366 }
367 if ((c->h.flags & MARKED) == 0)
368 {
369 c->callDtor();
370 nextNode = c + 1;
371 return c;
372 }
373 c->clearFlag(MARKED);
374 }
375 return slowNew();
376 }
377
378 #endif
379