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 protected void setSentinel(int unit) {
186 setLoEntry(unit, NEXT_MASK & unit);
187 setHiEntry(unit, PREV_MASK & unit);
188 }
189
190 /**
191 * Get the size of a lump of units
192 *
193 * @param unit The first unit in the lump of units
194 * @return The size of the lump of units
195 */
196 protected int getSize(int unit) {
197 if ((getHiEntry(unit) & MULTI_MASK) == MULTI_MASK)
198 return (getHiEntry(unit + 1) & SIZE_MASK);
199 else
200 return 1;
201 }
202
203 /**
204 * Set the size of lump of units
205 *
206 * @param unit The first unit in the lump of units
207 * @param size The size of the lump of units
208 */
209 protected void setSize(int unit, int size) {
210 if (size > 1) {
211 setHiEntry(unit, getHiEntry(unit) | MULTI_MASK);
212 setHiEntry(unit + 1, MULTI_MASK | size);
213 setHiEntry(unit + size - 1, MULTI_MASK | size);
214 } else
215 setHiEntry(unit, getHiEntry(unit) & ~MULTI_MASK);
216 }
217
218 /**
219 * Establish whether a lump of units is free
220 *
221 * @param unit The first or last unit in the lump
222 * @return True if the lump is free
223 */
224 protected boolean getFree(int unit) {
225 return ((getLoEntry(unit) & FREE_MASK) == FREE_MASK);
226 }
227
228 /**
229 * Set the "free" flag for a lump of units (both the first and last
230 * units in the lump are set.
231 *
232 * @param unit The first unit in the lump
233 * @param isFree True if the lump is to be marked as free
234 */
235 protected void setFree(int unit, boolean isFree) {
236 int size;
237 if (isFree) {
238 setLoEntry(unit, getLoEntry(unit) | FREE_MASK);
239 if ((size = getSize(unit)) > 1)
240 setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) | FREE_MASK);
241 } else {
242 setLoEntry(unit, getLoEntry(unit) & ~FREE_MASK);
243 if ((size = getSize(unit)) > 1)
244 setLoEntry(unit + size - 1, getLoEntry(unit + size - 1) & ~FREE_MASK);
245 }
246 }
247
248 /**
249 * Get the next lump in the doubly linked free list
250 *
251 * @param unit The index of the first unit in the current lump
252 * @return The index of the first unit of the next lump of units in the list
253 */
254 protected int getNext(int unit) {
255 int next = getHiEntry(unit) & NEXT_MASK;
256 return (next <= MAX_UNITS) ? next : head;
257 }
258
259 /**
260 * Set the next lump in the doubly linked free list
261 *
262 * @param unit The index of the first unit in the lump to be set
263 * @param next The value to be set.
264 */
265 protected void setNext(int unit, int next) {
266 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((next >= -heads) && (next <= MAX_UNITS));
267 int oldValue = getHiEntry(unit);
268 int newValue = (oldValue & ~NEXT_MASK) | (next & NEXT_MASK);
269 setHiEntry(unit, newValue);
270 }
271
272 /**
273 * Get the previous lump in the doubly linked free list
274 *
275 * @param unit The index of the first unit in the current lump
276 * @return The index of the first unit of the previous lump of units
277 * in the list
278 */
279 protected int getPrev(int unit) {
280 int prev = getLoEntry(unit) & PREV_MASK;
281 return (prev <= MAX_UNITS) ? prev : head;
282 }
283
284 /**
285 * Set the previous lump in the doubly linked free list
286 *
287 * @param unit The index of the first unit in the lump to be set
288 * @param prev The value to be set.
289 */
290 protected void setPrev(int unit, int prev) {
291 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert((prev >= -heads) && (prev <= MAX_UNITS));
292 int oldValue = getLoEntry(unit);
293 int newValue = (oldValue & ~PREV_MASK) | (prev & PREV_MASK);
294 setLoEntry(unit, newValue);
295 }
296
297 /**
298 * Set the uncoalescable bit associated with this unit.
299 * This ensures this unit cannot be coalesced with units below
300 * it.
301 *
302 * @param unit The unit whose uncoalescable bit is to be set
303 */
304 public void setUncoalescable(int unit) {
305 setLoEntry(unit, getLoEntry(unit) | COALESC_MASK);
306 }
307
308 /**
309 * Clear the uncoalescable bit associated with this unit.
310 * This allows this unit to be coalesced with units below
311 * it.
312 *
313 * @param unit The unit whose uncoalescable bit is to be cleared
314 */
315 public void clearUncoalescable(int unit) {
316 setLoEntry(unit, getLoEntry(unit) & ~COALESC_MASK);
317 }
318
319 /**
320 * Return true if this unit may be coalesced with the unit below it.
321 *
322 * @param unit The unit in question
323 * @return True if this unit may be coalesced with the unit below it.
324 */
325 @Override
326 public boolean isCoalescable(int unit) {
327 return (getLoEntry(unit) & COALESC_MASK) == 0;
328 }
329
330 /**
331 * Get the lump to the "left" of the current lump (i.e. "above" it)
332 *
333 * @param unit The index of the first unit in the lump in question
334 * @return The index of the first unit in the lump to the
335 * "left"/"above" the lump in question.
336 */
337 protected int getLeft(int unit) {
338 if ((getHiEntry(unit - 1) & MULTI_MASK) == MULTI_MASK)
339 return unit - (getHiEntry(unit - 1) & SIZE_MASK);
340 else
341 return unit - 1;
342 }
343
344
345 /**
346 * Get the contents of an entry
347 *
348 * @param unit The index of the unit
349 * @return The contents of the unit
350 */
351 private int getLoEntry(int unit) {
352 return table[(unit + heads) << 1];
353 }
354 private int getHiEntry(int unit) {
355 return table[((unit + heads) << 1) + 1];
356 }
357
358 /**
359 * Set the contents of an entry
360 *
361 * @param unit The index of the unit
362 * @param value The contents of the unit
363 */
364 private void setLoEntry(int unit, int value) {
365 table[(unit + heads) << 1] = value;
366 }
367 private void setHiEntry(int unit, int value) {
368 table[((unit + heads) << 1) + 1] = value;
369 }
370
371 private static final int TOTAL_BITS = 32;
372 private static final int UNIT_BITS = (TOTAL_BITS - 2);
373 public static final int MAX_UNITS = (int) (((((long) 1) << UNIT_BITS) - 1) - MAX_HEADS - 1);
374 private static final int NEXT_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
375 private static final int PREV_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
376 private static final int FREE_MASK = 1 << (TOTAL_BITS - 1);
377 private static final int MULTI_MASK = 1 << (TOTAL_BITS - 1);
378 private static final int COALESC_MASK = 1 << (TOTAL_BITS - 2);
379 private static final int SIZE_MASK = (int) ((((long) 1) << UNIT_BITS) - 1);
380
381 private int[] table;
382 private final GenericFreeList parent;
383 }