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