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 */ 013package org.mmtk.utility; 014 015import org.mmtk.vm.VM; 016 017import 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 { 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 * @param unit TODO needs documentation 134 * @return The index of the first of the <code>size</code> 135 * contiguous units, or -1 if the request can't be satisfied 136 */ 137 public final int alloc(int size, int unit) { 138 int s = 0; 139 140 if (getFree(unit) && (s = getSize(unit)) >= size) 141 return alloc(size, unit, s); 142 else 143 return FAILURE; 144 } 145 146 /** 147 * Allocate <code>size</code> units. Return the unit ID 148 * 149 * @param size The number of units to be allocated 150 * @param unit TODO needs documentation 151 * @param unitSize TODO needs documentation 152 * @return The index of the first of the <code>size</code> 153 * contiguous units, or -1 if the request can't be satisfied 154 */ 155 private int alloc(int size, int unit, int unitSize) { 156 if (unitSize >= size) { 157 if (unitSize > size) 158 split(unit, size); 159 removeFromFree(unit); 160 setFree(unit, false); 161 } 162 163 if (DEBUG) dbgPrintFree(); 164 165 return unit; 166 } 167 168 /** 169 * Free a previously allocated contiguous lump of units. 170 * 171 * @param unit The index of the first unit. 172 * @return return the size of the unit which was freed. 173 */ 174 public final int free(int unit) { 175 return free(unit, false); 176 } 177 178 /** 179 * Free a previously allocated contiguous lump of units. 180 * 181 * @param unit The index of the first unit. 182 * @param returnCoalescedSize if true, return the coalesced size 183 * @return The number of units freed. if returnCoalescedSize is 184 * false, return the size of the unit which was freed. Otherwise 185 * return the size of the unit now available (the coalesced size) 186 */ 187 public final int free(int unit, boolean returnCoalescedSize) { 188 int freed = getSize(unit); 189 int left = getLeft(unit); 190 int start = isCoalescable(unit) && getFree(left) ? left : unit; 191 int right = getRight(unit); 192 int end = isCoalescable(right) && getFree(right) ? right : unit; 193 if (start != end) 194 coalesce(start, end); 195 196 if (returnCoalescedSize) 197 freed = getSize(start); 198 addToFree(start); 199 200 if (DEBUG) dbgPrintFree(); 201 return freed; 202 } 203 204 /** 205 * Return the size of the specified lump of units 206 * 207 * @param unit The index of the first unit in the lump. 208 * @return The size of the lump, in units. 209 */ 210 public final int size(int unit) { 211 return getSize(unit); 212 } 213 214 /**************************************************************************** 215 * 216 * Private fields and methods 217 */ 218 219 /** 220 * Initialize a new heap. Fabricate a free list entry containing 221 * everything 222 * 223 * @param units The number of units in the heap 224 */ 225 protected final void initializeHeap(int units) { 226 initializeHeap(units, units); 227 } 228 229 /** 230 * Initialize a new heap. Fabricate a free list entry containing 231 * everything 232 * 233 * @param units The number of units in the heap 234 * @param grain TODO needs documentation 235 */ 236 protected final void initializeHeap(int units, int grain) { 237 // Initialize the sentinels 238 for (int i = 1; i <= heads; i++) 239 setSentinel(-i); 240 setSentinel(units); 241 242 // create the free list item 243 int offset = units % grain; 244 int cursor = units - offset; 245 if (offset > 0) { 246 setSize(cursor, offset); 247 addToFree(cursor); 248 } 249 cursor -= grain; 250 while (cursor >= 0) { 251 setSize(cursor, grain); 252 addToFree(cursor); 253 cursor -= grain; 254 } 255 if (DEBUG) dbgPrintFree(); 256 } 257 258 /** 259 * Reduce a lump of units to size, freeing any excess. 260 * 261 * @param unit The index of the first unit 262 * @param size The size of the first part 263 */ 264 private void split(int unit, int size) { 265 int basesize = getSize(unit); 266 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(basesize > size); 267 setSize(unit, size); 268 setSize(unit + size, basesize - size); 269 addToFree(unit + size); 270 if (DEBUG) dbgPrintFree(); 271 } 272 273 /** 274 * Coalesce two or three contiguous lumps of units, removing start 275 * and end lumps from the free list as necessary. 276 * @param start The index of the start of the first lump 277 * @param end The index of the start of the last lump 278 */ 279 private void coalesce(int start, int end) { 280 if (getFree(end)) 281 removeFromFree(end); 282 if (getFree(start)) 283 removeFromFree(start); 284 285 setSize(start, end - start + getSize(end)); 286 } 287 288 /** 289 * Add a lump of units to the free list 290 * 291 * @param unit The first unit in the lump of units to be added 292 */ 293 private void addToFree(int unit) { 294 setFree(unit, true); 295 int next = getNext(head); 296 setNext(unit, next); 297 setNext(head, unit); 298 setPrev(unit, head); 299 setPrev(next, unit); 300 } 301 302 /** 303 * Remove a lump of units from the free list 304 * 305 * @param unit The first unit in the lump of units to be removed 306 */ 307 private void removeFromFree(int unit) { 308 int next = getNext(unit); 309 int prev = getPrev(unit); 310 setNext(prev, next); 311 setPrev(next, prev); 312 if (DEBUG) dbgPrintFree(); 313 } 314 315 /** 316 * Get the lump to the "right" of the current lump (i.e. "below" it) 317 * 318 * @param unit The index of the first unit in the lump in question 319 * @return The index of the first unit in the lump to the 320 * "right"/"below" the lump in question. 321 */ 322 private int getRight(int unit) { 323 return unit + getSize(unit); 324 } 325 326 327 /** 328 * Print the free list (for debugging purposes) 329 */ 330 void dbgPrintFree() { 331 if (DEBUG) { 332 Log.write("FL["); 333 int i = head; 334 while ((i = getNext(i)) != head) { 335 boolean f = getFree(i); 336 int s = getSize(i); 337 if (!f) 338 Log.write("->"); 339 Log.write(i); 340 if (!f) 341 Log.write("<-"); 342 Log.write("("); 343 Log.write(s); 344 Log.write(")"); 345 Log.write(" "); 346 Log.flush(); 347 } 348 Log.writeln("]FL"); 349 } 350 } 351 352 abstract void setSentinel(int unit); 353 abstract int getSize(int unit); 354 abstract void setSize(int unit, int size); 355 abstract boolean getFree(int unit); 356 abstract void setFree(int unit, boolean isFree); 357 abstract int getNext(int unit); 358 abstract void setNext(int unit, int next); 359 abstract int getPrev(int unit); 360 abstract void setPrev(int unit, int prev); 361 abstract int getLeft(int unit); 362 abstract boolean isCoalescable(int unit); 363 364 protected static final boolean DEBUG = false; 365 public static final int FAILURE = -1; 366 protected static final int MAX_HEADS = 128; // somewhat arbitrary 367 368 protected int heads = 1; 369 protected int head = -heads; 370}