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