001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013
014 package org.mmtk.utility.alloc;
015
016 import org.mmtk.policy.Space;
017 import org.mmtk.policy.immix.Block;
018 import org.mmtk.policy.immix.Chunk;
019 import org.mmtk.policy.immix.Line;
020 import org.mmtk.policy.immix.ImmixSpace;
021 import static org.mmtk.policy.immix.ImmixConstants.*;
022
023 import org.mmtk.utility.Constants;
024 import org.mmtk.utility.Log;
025 import org.mmtk.utility.options.Options;
026 import org.mmtk.vm.VM;
027
028 import org.vmmagic.unboxed.*;
029 import org.vmmagic.pragma.*;
030
031 /**
032 *
033 */
034 @Uninterruptible
035 public class ImmixAllocator extends Allocator implements Constants {
036
037 /****************************************************************************
038 *
039 * Instance variables
040 */
041
042 /** space this allocator is associated with */
043 protected final ImmixSpace space;
044 private final boolean hot;
045 private final boolean copy;
046
047 /** bump pointer */
048 private Address cursor;
049 /** limit for bump pointer */
050 private Address limit;
051 /** bump pointer for large objects */
052 private Address largeCursor;
053 /** limit for bump pointer for large objects */
054 private Address largeLimit;
055 /** is the current request for large or small? */
056 private boolean requestForLarge;
057 /** did the last allocation straddle a line? */
058 private boolean straddle;
059 /** approximation to bytes allocated (measured at 99% accurate) 07/10/30 */
060 private int lineUseCount;
061 private Address markTable;
062 private Address recyclableBlock;
063 private int line;
064 private boolean recyclableExhausted;
065
066 /**
067 * Constructor.
068 *
069 * @param space The space to bump point into.
070 * @param hot TODO
071 * @param copy TODO
072 */
073 public ImmixAllocator(ImmixSpace space, boolean hot, boolean copy) {
074 this.space = space;
075 this.hot = hot;
076 this.copy = copy;
077 reset();
078 }
079
080 /**
081 * Reset the allocator. Note that this does not reset the space.
082 */
083 public void reset() {
084 cursor = Address.zero();
085 limit = Address.zero();
086 largeCursor = Address.zero();
087 largeLimit = Address.zero();
088 markTable = Address.zero();
089 recyclableBlock = Address.zero();
090 requestForLarge = false;
091 recyclableExhausted = false;
092 line = LINES_IN_BLOCK;
093 lineUseCount = 0;
094 }
095
096 /*****************************************************************************
097 *
098 * Public interface
099 */
100
101 /**
102 * Allocate space for a new object. This is frequently executed code and
103 * the coding is deliberately sensitive to the optimizing compiler.
104 * After changing this, always check the IR/MC that is generated.
105 *
106 * @param bytes The number of bytes allocated
107 * @param align The requested alignment
108 * @param offset The offset from the alignment
109 * @return The address of the first byte of the allocated region
110 */
111 @Inline
112 public final Address alloc(int bytes, int align, int offset) {
113 /* establish how much we need */
114 Address start = alignAllocationNoFill(cursor, align, offset);
115 Address end = start.plus(bytes);
116
117 /* check whether we've exceeded the limit */
118 if (end.GT(limit)) {
119 if (bytes > BYTES_IN_LINE)
120 return overflowAlloc(bytes, align, offset);
121 else
122 return allocSlowHot(bytes, align, offset);
123 }
124
125 /* sufficient memory is available, so we can finish performing the allocation */
126 fillAlignmentGap(cursor, start);
127 cursor = end;
128
129 return start;
130 }
131
132 /**
133 * Allocate space for a new object. This is frequently executed code and
134 * the coding is deliberately sensitive to the optimizing compiler.
135 * After changing this, always check the IR/MC that is generated.
136 *
137 * @param bytes The number of bytes allocated
138 * @param align The requested alignment
139 * @param offset The offset from the alignment
140 * @return The address of the first byte of the allocated region
141 */
142 public final Address overflowAlloc(int bytes, int align, int offset) {
143 /* establish how much we need */
144 Address start = alignAllocationNoFill(largeCursor, align, offset);
145 Address end = start.plus(bytes);
146
147 /* check whether we've exceeded the limit */
148 if (end.GT(largeLimit)) {
149 requestForLarge = true;
150 Address rtn = allocSlowInline(bytes, align, offset);
151 requestForLarge = false;
152 return rtn;
153 }
154
155 /* sufficient memory is available, so we can finish performing the allocation */
156 fillAlignmentGap(largeCursor, start);
157 largeCursor = end;
158
159 return start;
160 }
161
162 @Inline
163 public final boolean getLastAllocLineStraddle() {
164 return straddle;
165 }
166
167 /**
168 * External allocation slow path (called by superclass when slow path is
169 * actually taken. This is necessary (rather than a direct call
170 * from the fast path) because of the possibility of a thread switch
171 * and corresponding re-association of bump pointers to kernel
172 * threads.
173 *
174 * @param bytes The number of bytes allocated
175 * @param align The requested alignment
176 * @param offset The offset from the alignment
177 * @return The address of the first byte of the allocated region or
178 * zero on failure
179 */
180 @Override
181 protected final Address allocSlowOnce(int bytes, int align, int offset) {
182 Address ptr = space.getSpace(hot, copy, lineUseCount);
183
184 if (ptr.isZero()) {
185 lineUseCount = 0;
186 return ptr; // failed allocation --- we will need to GC
187 }
188
189 /* we have been given a clean block */
190 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(Block.isAligned(ptr));
191 lineUseCount = LINES_IN_BLOCK;
192
193 if (requestForLarge) {
194 largeCursor = ptr;
195 largeLimit = ptr.plus(BYTES_IN_BLOCK);
196 } else {
197 cursor = ptr;
198 limit = ptr.plus(BYTES_IN_BLOCK);
199 }
200
201 return alloc(bytes, align, offset);
202 }
203
204 /****************************************************************************
205 *
206 * Bump allocation
207 */
208
209 /**
210 * Internal allocation slow path. This is called whenever the bump
211 * pointer reaches the internal limit. The code is forced out of
212 * line. If required we perform an external slow path take, which
213 * we inline into this method since this is already out of line.
214 *
215 * @param bytes The number of bytes allocated
216 * @param align The requested alignment
217 * @param offset The offset from the alignment
218 * @return The address of the first byte of the allocated region
219 */
220 @NoInline
221 private Address allocSlowHot(int bytes, int align, int offset) {
222 if (acquireRecyclableLines(bytes, align, offset))
223 return alloc(bytes, align, offset);
224 else
225 return allocSlowInline(bytes, align, offset);
226 }
227
228 private boolean acquireRecyclableLines(int bytes, int align, int offset) {
229 while (line < LINES_IN_BLOCK || acquireRecyclableBlock()) {
230 line = space.getNextAvailableLine(markTable, line);
231 if (line < LINES_IN_BLOCK) {
232 int endLine = space.getNextUnavailableLine(markTable, line);
233 cursor = recyclableBlock.plus(Extent.fromIntSignExtend(line<<LOG_BYTES_IN_LINE));
234 limit = recyclableBlock.plus(Extent.fromIntSignExtend(endLine<<LOG_BYTES_IN_LINE));
235 if (SANITY_CHECK_LINE_MARKS) {
236 Address tmp = cursor;
237 while (tmp.LT(limit)) {
238 if (tmp.loadByte() != (byte) 0) {
239 Log.write("cursor: "); Log.writeln(cursor);
240 Log.write(" limit: "); Log.writeln(limit);
241 Log.write("current: "); Log.write(tmp);
242 Log.write(" value: "); Log.write(tmp.loadByte());
243 Log.write(" line: "); Log.write(line);
244 Log.write("endline: "); Log.write(endLine);
245 Log.write(" chunk: "); Log.write(Chunk.align(cursor));
246 Log.write(" hw: "); Log.write(Chunk.getHighWater(Chunk.align(cursor)));
247 Log.writeln(" values: ");
248 Address tmp2 = cursor;
249 while(tmp2.LT(limit)) { Log.write(tmp2.loadByte()); Log.write(" ");}
250 Log.writeln();
251 }
252 VM.assertions._assert(tmp.loadByte() == (byte) 0);
253 tmp = tmp.plus(1);
254 }
255 }
256 if (VM.VERIFY_ASSERTIONS && bytes <= BYTES_IN_LINE) {
257 Address start = alignAllocationNoFill(cursor, align, offset);
258 Address end = start.plus(bytes);
259 VM.assertions._assert(end.LE(limit));
260 }
261 VM.memory.zero(false, cursor, limit.diff(cursor).toWord().toExtent());
262 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
263 Log.write("Z["); Log.write(cursor); Log.write("->"); Log.write(limit); Log.writeln("]");
264 }
265
266 line = endLine;
267 if (VM.VERIFY_ASSERTIONS && copy) VM.assertions._assert(!Block.isDefragSource(cursor));
268 return true;
269 }
270 }
271 return false;
272 }
273
274 private boolean acquireRecyclableBlock() {
275 boolean rtn;
276 rtn = acquireRecyclableBlockAddressOrder();
277 if (rtn) {
278 markTable = Line.getBlockMarkTable(recyclableBlock);
279 line = 0;
280 }
281 return rtn;
282 }
283
284 @Inline
285 private boolean acquireRecyclableBlockAddressOrder() {
286 if (recyclableExhausted) {
287 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
288 Log.writeln("[no recyclable available]");
289 }
290 return false;
291 }
292 int markState = 0;
293 boolean usable = false;
294 while (!usable) {
295 Address next = recyclableBlock.plus(BYTES_IN_BLOCK);
296 if (recyclableBlock.isZero() || ImmixSpace.isRecycleAllocChunkAligned(next)) {
297 recyclableBlock = space.acquireReusableBlocks();
298 if (recyclableBlock.isZero()) {
299 recyclableExhausted = true;
300 if (VM.VERIFY_ASSERTIONS && Options.verbose.getValue() >= 9) {
301 Log.writeln("[recyclable exhausted]");
302 }
303 line = LINES_IN_BLOCK;
304 return false;
305 }
306 } else {
307 recyclableBlock = next;
308 }
309 markState = Block.getBlockMarkState(recyclableBlock);
310 usable = (markState > 0 && markState <= ImmixSpace.getReusuableMarkStateThreshold(copy));
311 if (copy && Block.isDefragSource(recyclableBlock))
312 usable = false;
313 }
314 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(!Block.isUnused(recyclableBlock));
315 Block.setBlockAsReused(recyclableBlock);
316
317 lineUseCount += (LINES_IN_BLOCK-markState);
318 return true; // found something good
319 }
320
321 private void zeroBlock(Address block) {
322 // FIXME: efficiency check here!
323 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(block.toWord().and(Word.fromIntSignExtend(BYTES_IN_BLOCK-1)).isZero());
324 VM.memory.zero(false, block, Extent.fromIntZeroExtend(BYTES_IN_BLOCK));
325 }
326
327 /** @return the space associated with this squish allocator */
328 @Override
329 public final Space getSpace() { return space; }
330
331 /**
332 * Print out the status of the allocator (for debugging)
333 */
334 public final void show() {
335 Log.write("cursor = "); Log.write(cursor);
336 Log.write(" limit = "); Log.writeln(limit);
337 }
338 }