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 package org.mmtk.utility.alloc;
014
015 import org.mmtk.policy.Space;
016 import org.mmtk.utility.*;
017
018 import org.mmtk.vm.VM;
019
020 import org.vmmagic.pragma.*;
021 import org.vmmagic.unboxed.*;
022
023 /**
024 * This class implements "block" data structures of various sizes.<p>
025 *
026 * Blocks are a non-shared (thread-local) coarse-grained unit of
027 * storage. Blocks are available in power-of-two sizes.
028 *
029 * Virtual memory space is taken from a VM resource, and pages
030 * consumed by blocks are accounted for by a memory resource.
031 */
032 @Uninterruptible
033 public final class BlockAllocator implements Constants {
034 /****************************************************************************
035 *
036 * Class variables
037 */
038
039 // block freelist
040 public static final int LOG_MIN_BLOCK = 12; // 4K bytes
041 public static final int LOG_MAX_BLOCK = 15; // 32K bytes
042 public static final byte MAX_BLOCK_SIZE_CLASS = LOG_MAX_BLOCK - LOG_MIN_BLOCK;
043 public static final int BLOCK_SIZE_CLASSES = MAX_BLOCK_SIZE_CLASS + 1;
044
045 // metadata
046 private static final Offset NEXT_OFFSET = Offset.zero();
047 private static final Offset BMD_OFFSET = NEXT_OFFSET.plus(BYTES_IN_ADDRESS);
048 private static final Offset CSC_OFFSET = BMD_OFFSET.plus(1);
049 private static final Offset IU_OFFSET = CSC_OFFSET.plus(1);
050 private static final Offset FL_META_OFFSET = IU_OFFSET.plus(BYTES_IN_SHORT);
051 private static final byte BLOCK_SC_MASK = 0xf; // lower 4 bits
052 private static final int BLOCK_PAGE_OFFSET_SHIFT = 4; // higher 4 bits
053 private static final int MAX_BLOCK_PAGE_OFFSET = (1<<4)-1; // 4 bits
054 private static final int LOG_BYTES_IN_BLOCK_META = LOG_BYTES_IN_ADDRESS + 2;
055 private static final int LOG_BYTE_COVERAGE = LOG_MIN_BLOCK - LOG_BYTES_IN_BLOCK_META;
056
057 public static final int META_DATA_BYTES_PER_REGION = 1 << (EmbeddedMetaData.LOG_BYTES_IN_REGION - LOG_BYTE_COVERAGE);
058 public static final Extent META_DATA_EXTENT = Extent.fromIntSignExtend(META_DATA_BYTES_PER_REGION);
059
060 /****************************************************************************
061 *
062 * Allocation & freeing
063 */
064
065 /**
066 * Allocate a block, returning the address of the first usable byte
067 * in the block.
068 *
069 * @param blockSizeClass The size class for the block to be allocated.
070 * @return The address of the first usable byte in the block, or
071 * zero on failure.
072 */
073 public static Address alloc(Space space, int blockSizeClass) {
074 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((blockSizeClass >= 0) && (blockSizeClass <= MAX_BLOCK_SIZE_CLASS));
075 int pages = pagesForSizeClass(blockSizeClass);
076 Address result = space.acquire(pages);
077 if (!result.isZero()) {
078 setBlkSizeMetaData(result, (byte) blockSizeClass);
079 }
080 return result;
081 }
082
083 /**
084 * Free a block. If the block is a sub-page block and the page is
085 * not completely free, then the block is added to the free list.
086 * Otherwise the block is returned to the virtual memory resource.
087 *
088 * @param block The address of the block to be freed
089 */
090 public static void free(Space space, Address block) {
091 space.release(block);
092 }
093
094 /**
095 * Return the size in bytes of a block of a given size class
096 *
097 * @param blockSizeClass The size class in question
098 * @return The size in bytes of a block of this size class
099 */
100 @Inline
101 public static int blockSize(int blockSizeClass) {
102 return 1 << (LOG_MIN_BLOCK + blockSizeClass);
103 }
104
105 /**
106 * Return the number of pages required when allocating space for
107 * this size class.
108 *
109 * @param blockSizeClass The size class in question
110 * @return The number of pages required when allocating a block (or
111 * blocks) of this size class.
112 */
113 @Inline
114 private static int pagesForSizeClass(int blockSizeClass) {
115 return 1 << (LOG_MIN_BLOCK + blockSizeClass - LOG_BYTES_IN_PAGE);
116 }
117
118 /****************************************************************************
119 *
120 * Block meta-data manipulation
121 */
122
123 /**
124 * Set the <i>block size class</i> meta data field for a given
125 * address (all blocks on a given page are homogeneous with respect
126 * to block size class).
127 *
128 * @param block The address of interest
129 * @param sc The value to which this field is to be set
130 */
131 @Inline
132 private static void setBlkSizeMetaData(Address block, byte sc) {
133 if (VM.VERIFY_ASSERTIONS) {
134 VM.assertions._assert(block.EQ(Conversions.pageAlign(block)));
135 VM.assertions._assert(pagesForSizeClass(sc) - 1 <= MAX_BLOCK_PAGE_OFFSET);
136 }
137 Address address = block;
138 for (int i = 0; i < pagesForSizeClass(sc); i++) {
139 byte value = (byte) ((i << BLOCK_PAGE_OFFSET_SHIFT) | sc);
140 getMetaAddress(address).store(value, BMD_OFFSET);
141 if (VM.VERIFY_ASSERTIONS) {
142 VM.assertions._assert(getBlkStart(address).EQ(block));
143 VM.assertions._assert(getBlkSizeClass(address) == sc);
144 }
145 address = address.plus(1<<VM.LOG_BYTES_IN_PAGE);
146 }
147 }
148
149 /**
150 * Get the <i>block size class</i> meta data field for a given page
151 * (all blocks on a given page are homogeneous with respect to block
152 * size class).
153 *
154 * @param address The address of interest
155 * @return The size class field for the block containing the given address
156 */
157 @Inline
158 private static byte getBlkSizeClass(Address address) {
159 address = Conversions.pageAlign(address);
160 byte rtn = (byte) (getMetaAddress(address).loadByte(BMD_OFFSET) & BLOCK_SC_MASK);
161 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(rtn >= 0 && rtn <= MAX_BLOCK_SIZE_CLASS);
162 return rtn;
163 }
164
165 /**
166 * Get the <i>address of the start of a block size class</i> a given page
167 * within the block.
168 *
169 * @param address The address of interest
170 * @return The address of the block containing the address
171 */
172 @Inline
173 public static Address getBlkStart(Address address) {
174 address = Conversions.pageAlign(address);
175 byte offset = (byte) (getMetaAddress(address).loadByte(BMD_OFFSET) >>> BLOCK_PAGE_OFFSET_SHIFT);
176 return address.minus(offset<<LOG_BYTES_IN_PAGE);
177 }
178
179 /**
180 * Set the <i>client size class</i> meta data field for a given
181 * address (all blocks on a given page are homogeneous with respect
182 * to block size class).
183 *
184 * @param block The address of interest
185 * @param sc The value to which this field is to be set
186 */
187 @Inline
188 public static void setAllClientSizeClass(Address block, int blocksc, byte sc) {
189 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(block.EQ(Conversions.pageAlign(block)));
190 Address address = block;
191 for (int i = 0; i < pagesForSizeClass(blocksc); i++) {
192 getMetaAddress(address).store(sc, CSC_OFFSET);
193 address = address.plus(1<<VM.LOG_BYTES_IN_PAGE);
194 }
195 }
196
197 /**
198 * Get the <i>client size class</i> meta data field for a given page
199 * (all blocks on a given page are homogeneous with respect to block
200 * size class).
201 *
202 * @param address The address of interest
203 * @return The size class field for the block containing the given address
204 */
205 @Inline
206 public static byte getClientSizeClass(Address address) {
207 address = Conversions.pageAlign(address);
208 byte rtn = getMetaAddress(address).loadByte(CSC_OFFSET);
209 return rtn;
210 }
211
212 /**
213 * Set the free list meta data field for a given address (this is
214 * per-block meta data that is stored along with the block metadata
215 * but not used by the block allocator).
216 *
217 * @param address The address of interest
218 * @param value The value to which this field is to be set
219 */
220 @Inline
221 public static void setFreeListMeta(Address address, Address value) {
222 getMetaAddress(address).plus(FL_META_OFFSET).store(value);
223 }
224
225 /**
226 * Get the free list meta data field for a given address (this is
227 * per-block meta data that is stored along with the block metadata
228 * but not used by the block allocator).
229 *
230 * @param address The address of interest
231 * @return The free list meta data field for the block containing
232 * the given address
233 */
234 @Inline
235 public static Address getFreeListMeta(Address address) {
236 return getMetaAddress(address).plus(FL_META_OFFSET).loadAddress();
237 }
238
239 /**
240 * Set the <i>prev</i> meta data field for a given address
241 *
242 * @param address The address of interest
243 * @param prev The value to which this field is to be set
244 */
245 @Inline
246 public static void setNext(Address address, Address prev) {
247 getMetaAddress(address, NEXT_OFFSET).store(prev);
248 }
249
250 /**
251 * Get the <i>prev</i> meta data field for a given address
252 *
253 * @param address The address of interest
254 * @return The prev field for the block containing the given address
255 */
256 @Inline
257 public static Address getNext(Address address) {
258 return getMetaAddress(address, NEXT_OFFSET).loadAddress();
259 }
260
261 /**
262 * Get the address of some metadata given the address for which the
263 * metadata is required and the offset into the metadata that is of
264 * interest.
265 *
266 * @param address The address for which the metadata is required
267 * @return The address of the specified meta data
268 */
269 @Inline
270 private static Address getMetaAddress(Address address) {
271 return getMetaAddress(address, Offset.zero());
272 }
273
274 /**
275 * Get the address of some metadata given the address for which the
276 * metadata is required and the offset into the metadata that is of
277 * interest.
278 *
279 * @param address The address for which the metadata is required
280 * @param offset The offset (in bytes) into the metadata block (eg
281 * for the prev pointer, or next pointer)
282 * @return The address of the specified meta data
283 */
284 @Inline
285 private static Address getMetaAddress(Address address, Offset offset) {
286 return EmbeddedMetaData.getMetaDataBase(address).plus(
287 EmbeddedMetaData.getMetaDataOffset(address, LOG_BYTE_COVERAGE, LOG_BYTES_IN_BLOCK_META)).plus(offset);
288 }
289
290 /****************************************************************************
291 *
292 * Block marking
293 */
294
295 /**
296 * Mark the metadata for this block.
297 *
298 * @param ref
299 */
300 @Inline
301 public static void markBlockMeta(ObjectReference ref) {
302 getMetaAddress(VM.objectModel.refToAddress(ref)).plus(FL_META_OFFSET).store(Word.one());
303 }
304
305 /**
306 * Mark the metadata for this block.
307 *
308 * @param block The block address
309 */
310 @Inline
311 public static void markBlockMeta(Address block) {
312 getMetaAddress(block).plus(FL_META_OFFSET).store(Word.one());
313 }
314
315 /**
316 * Return true if the metadata for this block was set.
317 *
318 * @param block The block address
319 * @return value of the meta data.
320 */
321 @Inline
322 public static boolean checkBlockMeta(Address block) {
323 return getMetaAddress(block).plus(FL_META_OFFSET).loadWord().EQ(Word.one());
324 }
325
326 /**
327 * Clear the metadata for this block
328 *
329 * @param block The block address
330 */
331 @Inline
332 public static void clearBlockMeta(Address block) {
333 getMetaAddress(block).plus(FL_META_OFFSET).store(Word.zero());
334 }
335 }