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.vm.VM;
016
017 import org.vmmagic.pragma.*;
018
019 /**
020 * This is a very simple, generic malloc-free allocator. It works
021 * abstractly, in "units", which the user may associate with some
022 * other allocatable resource (e.g. heap blocks). The user issues
023 * requests for N units and the allocator returns the index of the
024 * first of a contiguous set of N units or fails, returning -1. The
025 * user frees the block of N units by calling <code>free()</code> with
026 * the index of the first unit as the argument.<p>
027 *
028 * Properties/Constraints:<ul>
029 * <li> The allocator consumes one word per allocatable unit (plus
030 * a fixed overhead of about 128 words).</li>
031 * <li> The allocator can only deal with MAX_UNITS units (see below for
032 * the value).</li>
033 * </ul>
034 *
035 * The basic data structure used by the algorithm is a large table,
036 * with one word per allocatable unit. Each word is used in a
037 * number of different ways, some combination of "undefined" (32),
038 * "free/used" (1), "multi/single" (1), "prev" (15), "next" (15) &
039 * "size" (15) where field sizes in bits are in parenthesis.
040 * <pre>
041 * +-+-+-----------+-----------+
042 * |f|m| prev | next/size |
043 * +-+-+-----------+-----------+
044 *
045 * - single free unit: "free", "single", "prev", "next"
046 * - single used unit: "used", "single"
047 * - contiguous free units
048 * . first unit: "free", "multi", "prev", "next"
049 * . second unit: "free", "multi", "size"
050 * . last unit: "free", "multi", "size"
051 * - contiguous used units
052 * . first unit: "used", "multi", "prev", "next"
053 * . second unit: "used", "multi", "size"
054 * . last unit: "used", "multi", "size"
055 * - any other unit: undefined
056 *
057 * +-+-+-----------+-----------+
058 * top sentinel |0|0| tail | head | [-1]
059 * +-+-+-----------+-----------+
060 * ....
061 * /-------- +-+-+-----------+-----------+
062 * | |1|1| prev | next | [j]
063 * | +-+-+-----------+-----------+
064 * | |1|1| | size | [j+1]
065 * free multi +-+-+-----------+-----------+
066 * unit block | ... | ...
067 * | +-+-+-----------+-----------+
068 * | |1|1| | size |
069 * >-------- +-+-+-----------+-----------+
070 * single free unit |1|0| prev | next |
071 * >-------- +-+-+-----------+-----------+
072 * single used unit |0|0| |
073 * >-------- +-+-+-----------------------+
074 * | |0|1| |
075 * | +-+-+-----------+-----------+
076 * | |0|1| | size |
077 * used multi +-+-+-----------+-----------+
078 * unit block | ... |
079 * | +-+-+-----------+-----------+
080 * | |0|1| | size |
081 * \-------- +-+-+-----------+-----------+
082 * ....
083 * +-+-+-----------------------+
084 * bottom sentinel |0|0| | [N]
085 * +-+-+-----------------------+
086 * </pre>
087 * The sentinels serve as guards against out of range coalescing
088 * because they both appear as "used" blocks and so will never
089 * coalesce. The top sentinel also serves as the head and tail of
090 * the doubly linked list of free blocks.
091 */
092 @Uninterruptible abstract class BaseGenericFreeList implements Constants {
093
094 /****************************************************************************
095 *
096 * Public instance methods
097 */
098
099 /**
100 * Allocate <code>size</code> units. Return the unit ID
101 *
102 * @param size The number of units to be allocated
103 * @return The index of the first of the <code>size</code>
104 * contiguous units, or -1 if the request can't be satisfied
105 */
106 public final int alloc(int size) {
107 // Note: -1 is both the default return value *and* the start sentinel index
108 int unit = head; // HEAD = -1
109 int s = 0;
110 while (((unit = getNext(unit)) != head) && ((s = getSize(unit)) < size));
111
112 return (unit == head) ? FAILURE : alloc(size, unit, s);
113 }
114
115 /**
116 * Would an allocation of <code>size</code> units succeed?
117 *
118 * @param size The number of units to test for
119 * @return True if such a request could be satisfied.
120 */
121 public final boolean couldAlloc(int size) {
122 // Note: -1 is both the default return value *and* the start sentinel index
123 int unit = head; // HEAD = -1
124 while (((unit = getNext(unit)) != head) && (getSize(unit) < size));
125
126 return (unit != head);
127 }
128
129 /**
130 * Allocate <code>size</code> units. Return the unit ID
131 *
132 * @param size The number of units to be allocated
133 * @return The index of the first of the <code>size</code>
134 * contiguous units, or -1 if the request can't be satisfied
135 */
136 public final int alloc(int size, int unit) {
137 int s = 0;
138
139 if (getFree(unit) && (s = getSize(unit)) >= size)
140 return alloc(size, unit, s);
141 else
142 return FAILURE;
143 }
144
145 /**
146 * Allocate <code>size</code> units. Return the unit ID
147 *
148 * @param size The number of units to be allocated
149 * @return The index of the first of the <code>size</code>
150 * contiguous units, or -1 if the request can't be satisfied
151 */
152 private int alloc(int size, int unit, int unitSize) {
153 if (unitSize >= size) {
154 if (unitSize > size)
155 split(unit, size);
156 removeFromFree(unit);
157 setFree(unit, false);
158 }
159
160 if (DEBUG) dbgPrintFree();
161
162 return unit;
163 }
164
165 /**
166 * Free a previously allocated contiguous lump of units.
167 *
168 * @param unit The index of the first unit.
169 * @return return the size of the unit which was freed.
170 */
171 public final int free(int unit) {
172 return free(unit, false);
173 }
174
175 /**
176 * Free a previously allocated contiguous lump of units.
177 *
178 * @param unit The index of the first unit.
179 * @param returnCoalescedSize if true, return the coalesced size
180 * @return The number of units freed. if returnCoalescedSize is
181 * false, return the size of the unit which was freed. Otherwise
182 * return the size of the unit now available (the coalesced size)
183 */
184 public final int free(int unit, boolean returnCoalescedSize) {
185 int freed = getSize(unit);
186 int left = getLeft(unit);
187 int start = isCoalescable(unit) && getFree(left) ? left : unit;
188 int right = getRight(unit);
189 int end = isCoalescable(right) && getFree(right) ? right : unit;
190 if (start != end)
191 coalesce(start, end);
192
193 if (returnCoalescedSize)
194 freed = getSize(start);
195 addToFree(start);
196
197 if (DEBUG) dbgPrintFree();
198 return freed;
199 }
200
201 /**
202 * Return the size of the specified lump of units
203 *
204 * @param unit The index of the first unit in the lump.
205 * @return The size of the lump, in units.
206 */
207 public final int size(int unit) {
208 return getSize(unit);
209 }
210
211 /****************************************************************************
212 *
213 * Private fields and methods
214 */
215
216 /**
217 * Initialize a new heap. Fabricate a free list entry containing
218 * everything
219 *
220 * @param units The number of units in the heap
221 */
222 protected final void initializeHeap(int units) {
223 initializeHeap(units, units);
224 }
225
226 /**
227 * Initialize a new heap. Fabricate a free list entry containing
228 * everything
229 *
230 * @param units The number of units in the heap
231 */
232 protected final void initializeHeap(int units, int grain) {
233 // Initialize the sentinels
234 for (int i = 1; i <= heads; i++)
235 setSentinel(-i);
236 setSentinel(units);
237
238 // create the free list item
239 int offset = units % grain;
240 int cursor = units - offset;
241 if (offset > 0) {
242 setSize(cursor, offset);
243 addToFree(cursor);
244 }
245 cursor -= grain;
246 while (cursor >= 0) {
247 setSize(cursor, grain);
248 addToFree(cursor);
249 cursor -= grain;
250 }
251 if (DEBUG) dbgPrintFree();
252 }
253
254 /**
255 * Reduce a lump of units to size, freeing any excess.
256 *
257 * @param unit The index of the first unit
258 * @param size The size of the first part
259 */
260 private void split(int unit, int size) {
261 int basesize = getSize(unit);
262 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(basesize > size);
263 setSize(unit, size);
264 setSize(unit + size, basesize - size);
265 addToFree(unit + size);
266 if (DEBUG) dbgPrintFree();
267 }
268
269 /**
270 * Coalesce two or three contiguous lumps of units, removing start
271 * and end lumps from the free list as necessary.
272 * @param start The index of the start of the first lump
273 * @param end The index of the start of the last lump
274 */
275 private void coalesce(int start, int end) {
276 if (getFree(end))
277 removeFromFree(end);
278 if (getFree(start))
279 removeFromFree(start);
280
281 setSize(start, end - start + getSize(end));
282 }
283
284 /**
285 * Add a lump of units to the free list
286 *
287 * @param unit The first unit in the lump of units to be added
288 */
289 private void addToFree(int unit) {
290 setFree(unit, true);
291 int next = getNext(head);
292 setNext(unit, next);
293 setNext(head, unit);
294 setPrev(unit, head);
295 setPrev(next, unit);
296 }
297
298 /**
299 * Remove a lump of units from the free list
300 *
301 * @param unit The first unit in the lump of units to be removed
302 */
303 private void removeFromFree(int unit) {
304 int next = getNext(unit);
305 int prev = getPrev(unit);
306 setNext(prev, next);
307 setPrev(next, prev);
308 if (DEBUG) dbgPrintFree();
309 }
310
311 /**
312 * Get the lump to the "right" of the current lump (i.e. "below" it)
313 *
314 * @param unit The index of the first unit in the lump in question
315 * @return The index of the first unit in the lump to the
316 * "right"/"below" the lump in question.
317 */
318 private int getRight(int unit) {
319 return unit + getSize(unit);
320 }
321
322
323 /**
324 * Print the free list (for debugging purposes)
325 */
326 void dbgPrintFree() {
327 if (DEBUG) {
328 Log.write("FL[");
329 int i = head;
330 while ((i = getNext(i)) != head) {
331 boolean f = getFree(i);
332 int s = getSize(i);
333 if (!f)
334 Log.write("->");
335 Log.write(i);
336 if (!f)
337 Log.write("<-");
338 Log.write("(");
339 Log.write(s);
340 Log.write(")");
341 Log.write(" ");
342 Log.flush();
343 }
344 Log.writeln("]FL");
345 }
346 }
347
348 abstract void setSentinel(int unit);
349 abstract int getSize(int unit);
350 abstract void setSize(int unit, int size);
351 abstract boolean getFree(int unit);
352 abstract void setFree(int unit, boolean isFree);
353 abstract int getNext(int unit);
354 abstract void setNext(int unit, int next);
355 abstract int getPrev(int unit);
356 abstract void setPrev(int unit, int prev);
357 abstract int getLeft(int unit);
358 abstract boolean isCoalescable(int unit);
359
360 protected static final boolean DEBUG = false;
361 public static final int FAILURE = -1;
362 protected static final int MAX_HEADS = 128; // somewhat arbitrary
363
364 protected int heads = 1;
365 protected int head = -heads;
366 }