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;
014
015 import org.mmtk.plan.Plan;
016 import org.mmtk.vm.VM;
017
018 import org.vmmagic.pragma.*;
019
020 /**
021 * This is a very simple, generic malloc-free allocator. It works
022 * abstractly, in "units", which the user may associate with some
023 * other allocatable resource (e.g. heap blocks). The user issues
024 * requests for N units and the allocator returns the index of the
025 * first of a contiguous set of N units or fails, returning -1. The
026 * user frees the block of N units by calling <code>free()</code> with
027 * the index of the first unit as the argument.<p>
028 *
029 * Properties/Constraints:<ul>
030 * <li> The allocator consumes one word per allocatable unit (plus
031 * a fixed overhead of about 128 words).</li>
032 * <li> The allocator can only deal with MAX_UNITS units (see below for
033 * the value).</li>
034 * </ul>
035 *
036 * The basic data structure used by the algorithm is a large table,
037 * with one word per allocatable unit. Each word is used in a
038 * number of different ways, some combination of "undefined" (32),
039 * "free/used" (1), "multi/single" (1), "prev" (15), "next" (15) &
040 * "size" (15) where field sizes in bits are in parenthesis.
041 * <pre>
042 * +-+-+-----------+-----------+
043 * |f|m| prev | next/size |
044 * +-+-+-----------+-----------+
045 *
046 * - single free unit: "free", "single", "prev", "next"
047 * - single used unit: "used", "single"
048 * - contiguous free units
049 * . first unit: "free", "multi", "prev", "next"
050 * . second unit: "free", "multi", "size"
051 * . last unit: "free", "multi", "size"
052 * - contiguous used units
053 * . first unit: "used", "multi", "prev", "next"
054 * . second unit: "used", "multi", "size"
055 * . last unit: "used", "multi", "size"
056 * - any other unit: undefined
057 *
058 * +-+-+-----------+-----------+
059 * top sentinel |0|0| tail | head | [-1]
060 * +-+-+-----------+-----------+
061 * ....
062 * /-------- +-+-+-----------+-----------+
063 * | |1|1| prev | next | [j]
064 * | +-+-+-----------+-----------+
065 * | |1|1| | size | [j+1]
066 * free multi +-+-+-----------+-----------+
067 * unit block | ... | ...
068 * | +-+-+-----------+-----------+
069 * | |1|1| | size |
070 * >-------- +-+-+-----------+-----------+
071 * single free unit |1|0| prev | next |
072 * >-------- +-+-+-----------+-----------+
073 * single used unit |0|0| |
074 * >-------- +-+-+-----------------------+
075 * | |0|1| |
076 * | +-+-+-----------+-----------+
077 * | |0|1| | size |
078 * used multi +-+-+-----------+-----------+
079 * unit block | ... |
080 * | +-+-+-----------+-----------+
081 * | |0|1| | size |
082 * \-------- +-+-+-----------+-----------+
083 * ....
084 * +-+-+-----------------------+
085 * bottom sentinel |0|0| | [N]
086 * +-+-+-----------------------+
087 * </pre>
088 * The sentinels serve as guards against out of range coalescing
089 * because they both appear as "used" blocks and so will never
090 * coalesce. The top sentinel also serves as the head and tail of
091 * the doubly linked list of free blocks.
092 */
093 @Uninterruptible
094 public final class GenericFreeList extends BaseGenericFreeList implements Constants {
095
096 /****************************************************************************
097 *
098 * Public instance methods
099 */
100
101 /**
102 * Constructor
103 *
104 * @param units The number of allocatable units for this free list
105 */
106 public GenericFreeList(int units) {
107 this(units, units);
108 }
109
110 /**
111 * Constructor
112 *
113 * @param units The number of allocatable units for this free list
114 * @param grain Units are allocated such that they will never cross this granularity boundary
115 */
116 public GenericFreeList(int units, int grain) {
117 this(units, grain, 1);
118 }
119
120 /**
121 * Constructor
122 *
123 * @param units The number of allocatable units for this free list
124 * @param grain Units are allocated such that they will never cross this granularity boundary
125 * @param heads The number of free lists which will share this instance
126 */
127 public GenericFreeList(int units, int grain, int heads) {
128 this.parent = null;
129 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(units <= MAX_UNITS && heads <= MAX_HEADS);
130 this.heads = heads;
131 head = -1;
132
133 // allocate the data structure, including space for top & bottom sentinels
134 table = new int[(units + 1 + heads) << 1];
135 initializeHeap(units, grain);
136 }
137
138 /**
139 * Resize the free list for a parent free list.
140 * This must not be called dynamically (ie not after bootstrap).
141 *
142 * @param units The number of allocatable units for this free list
143 * @param grain Units are allocated such that they will never cross this granularity boundary
144 */
145 @Interruptible
146 public void resizeFreeList(int units, int grain) {
147 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(parent == null && !Plan.isInitialized());
148 table = new int[(units + 1 + heads) << 1];
149 initializeHeap(units, grain);
150 }
151
152 /**
153 * Resize the free list for a child free list.
154 * This must not be called dynamically (ie not after bootstrap).
155 */
156 @Interruptible
157 public void resizeFreeList() {
158 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(parent != null && !Plan.isInitialized());
159 table = parent.getTable();
160 }
161
162 /**
163 * Constructor
164 *
165 * @param parent The parent, owning the data structures this instance will share
166 * @param ordinal The ordinal number of this child
167 */
168 public GenericFreeList(GenericFreeList parent, int ordinal) {
169 this.parent = parent;
170 this.table = parent.getTable();
171 this.heads = parent.getHeads();
172 this.head = -(1 + ordinal);
173 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(-this.head <= this.heads);
174 }
175
176 /* Getter */
177 int[] getTable() { return table; }
178 int getHeads() { return heads; }
179
180 /**
181 * Initialize a unit as a sentinel
182 *
183 * @param unit The unit to be initialized
184 */
185 @Override
186 protected void setSentinel(int unit) {
187 setLoEntry(unit, NEXT_MASK & unit);
188 setHiEntry(unit, PREV_MASK & unit);
189 }
190
191 /**
192 * Get the size of a lump of units
193 *
194 * @param unit The first unit in the lump of units
195 * @return The size of the lump of units
196 */
197 @Override
198 protected int getSize(int unit) {
199 if ((getHiEntry(unit) & MULTI_MASK) == MULTI_MASK)
200 return (getHiEntry(unit + 1) & SIZE_MASK);
201 else
202 return 1;
203 }
204
205 /**
206 * Set the size of lump of units
207 *
208 * @param unit The first unit in the lump of units
209 * @param size The size of the lump of units
210 */
211 @Override
212 protected void setSize(int unit, int size) {
213 if (size > 1) {
214 setHiEntry(unit, getHiEntry(unit) | MULTI_MASK);
215 setHiEntry(unit + 1, MULTI_MASK | size);
216 setHiEntry(unit + size - 1, MULTI_MASK | size);
217 } else
218 setHiEntry(unit, getHiEntry(unit) & ~MULTI_MASK);
219 }
220
221 /**
222 * Establish whether a lump of units is free
223 *
224 * @param unit The first or last unit in the lump
225 * @return {@code true} if the lump is free
226 */
227 @Override
228 protected boolean getFree(int unit) {
229 return ((getLoEntry(unit) & FREE_MASK) == FREE_MASK);
230 }
231
232 /**
233 * Set the "free" flag for a lump of units (both the first and last
234 * units in the lump are set.
235 *
236 * @param unit The first unit in the lump
237 * @param isFree {@code true} if the lump is to be marked as free
238 */
239 @Override
240 protected void setFree(int unit, boolean isFree) {
241 int size;
242 if (isFree) {
243 setLoEntry(unit, getLoEntry(unit) | FREE_MASK);
244 if ((size = getSize(unit)) > 1)
245 setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) | FREE_MASK);
246 } else {
247 setLoEntry(unit, getLoEntry(unit) & ~FREE_MASK);
248 if ((size = getSize(unit)) > 1)
249 setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) & ~FREE_MASK);
250 }
251 }
252
253 /**
254 * Get the next lump in the doubly linked free list
255 *
256 * @param unit The index of the first unit in the current lump
257 * @return The index of the first unit of the next lump of units in the list
258 */
259 @Override
260 protected int getNext(int unit) {
261 int next = getHiEntry(unit) & NEXT_MASK;
262 return (next <= MAX_UNITS) ? next : head;
263 }
264
265 /**
266 * Set the next lump in the doubly linked free list
267 *
268 * @param unit The index of the first unit in the lump to be set
269 * @param next The value to be set.
270 */
271 @Override
272 protected void setNext(int unit, int next) {
273 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((next >= -heads) && (next <= MAX_UNITS));
274 int oldValue = getHiEntry(unit);
275 int newValue = (oldValue & ~NEXT_MASK) | (next & NEXT_MASK);
276 setHiEntry(unit, newValue);
277 }
278
279 /**
280 * Get the previous lump in the doubly linked free list
281 *
282 * @param unit The index of the first unit in the current lump
283 * @return The index of the first unit of the previous lump of units
284 * in the list
285 */
286 @Override
287 protected int getPrev(int unit) {
288 int prev = getLoEntry(unit) & PREV_MASK;
289 return (prev <= MAX_UNITS) ? prev : head;
290 }
291
292 /**
293 * Set the previous lump in the doubly linked free list
294 *
295 * @param unit The index of the first unit in the lump to be set
296 * @param prev The value to be set.
297 */
298 @Override
299 protected void setPrev(int unit, int prev) {
300 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((prev >= -heads) && (prev <= MAX_UNITS));
301 int oldValue = getLoEntry(unit);
302 int newValue = (oldValue & ~PREV_MASK) | (prev & PREV_MASK);
303 setLoEntry(unit, newValue);
304 }
305
306 /**
307 * Set the uncoalescable bit associated with this unit.
308 * This ensures this unit cannot be coalesced with units below
309 * it.
310 *
311 * @param unit The unit whose uncoalescable bit is to be set
312 */
313 public void setUncoalescable(int unit) {
314 setLoEntry(unit, getLoEntry(unit) | COALESC_MASK);
315 }
316
317 /**
318 * Clear the uncoalescable bit associated with this unit.
319 * This allows this unit to be coalesced with units below
320 * it.
321 *
322 * @param unit The unit whose uncoalescable bit is to be cleared
323 */
324 public void clearUncoalescable(int unit) {
325 setLoEntry(unit, getLoEntry(unit) & ~COALESC_MASK);
326 }
327
328 /**
329 * Return true if this unit may be coalesced with the unit below it.
330 *
331 * @param unit The unit in question
332 * @return {@code true} if this unit may be coalesced with the unit below it.
333 */
334 @Override
335 public boolean isCoalescable(int unit) {
336 return (getLoEntry(unit) & COALESC_MASK) == 0;
337 }
338
339 /**
340 * Get the lump to the "left" of the current lump (i.e. "above" it)
341 *
342 * @param unit The index of the first unit in the lump in question
343 * @return The index of the first unit in the lump to the
344 * "left"/"above" the lump in question.
345 */
346 @Override
347 protected int getLeft(int unit) {
348 if ((getHiEntry(unit - 1) & MULTI_MASK) == MULTI_MASK)
349 return unit - (getHiEntry(unit - 1) & SIZE_MASK);
350 else
351 return unit - 1;
352 }
353
354
355 /**
356 * Get the contents of an entry
357 *
358 * @param unit The index of the unit
359 * @return The contents of the unit
360 */
361 private int getLoEntry(int unit) {
362 return table[(unit + heads) << 1];
363 }
364 private int getHiEntry(int unit) {
365 return table[((unit + heads) << 1) + 1];
366 }
367
368 /**
369 * Set the contents of an entry
370 *
371 * @param unit The index of the unit
372 * @param value The contents of the unit
373 */
374 private void setLoEntry(int unit, int value) {
375 table[(unit + heads) << 1] = value;
376 }
377 private void setHiEntry(int unit, int value) {
378 table[((unit + heads) << 1) + 1] = value;
379 }
380
381 private static final int TOTAL_BITS = 32;
382 private static final int UNIT_BITS = (TOTAL_BITS - 2);
383 public static final int MAX_UNITS = (int) (((((long) 1) << UNIT_BITS) - 1) - MAX_HEADS - 1);
384 private static final int NEXT_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
385 private static final int PREV_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
386 private static final int FREE_MASK = 1 << (TOTAL_BITS - 1);
387 private static final int MULTI_MASK = 1 << (TOTAL_BITS - 1);
388 private static final int COALESC_MASK = 1 << (TOTAL_BITS - 2);
389 private static final int SIZE_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
390
391 private int[] table;
392 private final GenericFreeList parent;
393 }