1
2
3
4 package joeq.Allocator;
5
6 import java.lang.reflect.Array;
7 import joeq.Class.PrimordialClassLoader;
8 import joeq.Class.jq_Array;
9 import joeq.Class.jq_Class;
10 import joeq.Class.jq_ClassFileConstants;
11 import joeq.Class.jq_InstanceField;
12 import joeq.Class.jq_Reference;
13 import joeq.Class.jq_StaticField;
14 import joeq.Class.jq_StaticMethod;
15 import joeq.Class.jq_Type;
16 import joeq.Memory.Address;
17 import joeq.Memory.HeapAddress;
18 import joeq.Runtime.Debug;
19 import joeq.Runtime.SystemInterface;
20 import joeq.Runtime.TypeCheck;
21 import jwutil.util.Assert;
22
23 /***
24 * HeapAllocator
25 *
26 * @author John Whaley <jwhaley@alum.mit.edu>
27 * @version $Id: HeapAllocator.java 2125 2005-01-21 07:13:15Z joewhaley $
28 */
29 public abstract class HeapAllocator implements jq_ClassFileConstants {
30
31
32
33 /*** Perform initialization for this allocator. This will be called before any other methods.
34 *
35 * @throws OutOfMemoryError if there is not enough memory for initialization
36 */
37 public abstract void init()
38 throws OutOfMemoryError;
39
40 /*** Allocate an object with the default alignment.
41 * If the object cannot be allocated due to lack of memory, throws OutOfMemoryError.
42 *
43 * @param size size of object to allocate (including object header), in bytes
44 * @param vtable vtable pointer for new object
45 * @return new uninitialized object
46 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
47 */
48 public abstract Object allocateObject(int size, Object vtable)
49 throws OutOfMemoryError;
50
51 /*** Allocate an object such that the first field is 8-byte aligned.
52 * If the object cannot be allocated due to lack of memory, throws OutOfMemoryError.
53 *
54 * @param size size of object to allocate (including object header), in bytes
55 * @param vtable vtable pointer for new object
56 * @return new uninitialized object
57 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
58 */
59 public abstract Object allocateObjectAlign8(int size, Object vtable)
60 throws OutOfMemoryError;
61
62 /*** Allocate an array with the default alignment.
63 * If length is negative, throws NegativeArraySizeException.
64 * If the array cannot be allocated due to lack of memory, throws OutOfMemoryError.
65 *
66 * @param length length of new array
67 * @param size size of array to allocate (including array header), in bytes
68 * @param vtable vtable pointer for new array
69 * @return new array
70 * @throws NegativeArraySizeException if length is negative
71 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
72 */
73 public abstract Object allocateArray(int length, int size, Object vtable)
74 throws OutOfMemoryError, NegativeArraySizeException;
75
76 /*** Allocate an array such that the elements are 8-byte aligned.
77 * If length is negative, throws NegativeArraySizeException.
78 * If the array cannot be allocated due to lack of memory, throws OutOfMemoryError.
79 *
80 * @param length length of new array
81 * @param size size of array to allocate (including array header), in bytes
82 * @param vtable vtable pointer for new array
83 * @return new array
84 * @throws NegativeArraySizeException if length is negative
85 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
86 */
87 public abstract Object allocateArrayAlign8(int length, int size, Object vtable)
88 throws OutOfMemoryError, NegativeArraySizeException;
89
90 /*** Returns an estimate of the amount of free memory available.
91 *
92 * @return bytes of free memory
93 */
94 public abstract int freeMemory();
95
96 /*** Returns an estimate of the total memory allocated (both used and unused).
97 *
98 * @return bytes of memory allocated
99 */
100 public abstract int totalMemory();
101
102 /***
103 * Returns whether the given address falls within the boundaries of this heap.
104 */
105 public abstract boolean isInHeap(Address a);
106
107 /***
108 * Initiate a garbage collection.
109 */
110 public abstract void collect();
111
112 /***
113 * Process a reference to a heap object during garbage collection.
114 */
115 public abstract void processObjectReference(Address a);
116
117 /***
118 * Process a possible reference to a heap object during garbage collection.
119 */
120 public abstract void processPossibleObjectReference(Address a);
121
122
123
124 public static final boolean TRACE = false;
125
126 /***
127 * Initialize class t and return a new uninitialized object of that type.
128 * If t is not a class type, throw a VerifyError.
129 *
130 * @param t type to initialize and create object of
131 * @return new uninitialized object of type t
132 * @throws VerifyError if t is not a class type
133 */
134 public static Object clsinitAndAllocateObject(jq_Type t)
135 throws VerifyError {
136 if (!t.isClassType())
137 throw new VerifyError();
138 jq_Class k = (jq_Class)t;
139 k.cls_initialize();
140 return k.newInstance();
141 }
142
143 /***
144 * Clone the given object. NOTE: Does not check if the object implements Cloneable.
145 *
146 * @return new clone
147 * @param o object to clone
148 * @throws OutOfMemoryError if there is not enough memory to perform operation
149 */
150 public static Object clone(Object o)
151 throws OutOfMemoryError {
152 jq_Reference t = jq_Reference.getTypeOf(o);
153 if (t.isClassType()) {
154 jq_Class k = (jq_Class)t;
155 Object p = k.newInstance();
156 if (k.getInstanceSize()-ObjectLayout.OBJ_HEADER_SIZE > 0)
157 SystemInterface.mem_cpy(HeapAddress.addressOf(p), HeapAddress.addressOf(o), k.getInstanceSize()-ObjectLayout.OBJ_HEADER_SIZE);
158 return p;
159 } else {
160 Assert._assert(t.isArrayType());
161 jq_Array k = (jq_Array)t;
162 int length = Array.getLength(o);
163 Object p = k.newInstance(length);
164 if (length > 0)
165 SystemInterface.mem_cpy(HeapAddress.addressOf(p), HeapAddress.addressOf(o), k.getInstanceSize(length)-ObjectLayout.ARRAY_HEADER_SIZE);
166 return p;
167 }
168 }
169
170 private static boolean isOutOfMemory = false;
171 private static final OutOfMemoryError outofmemoryerror = new OutOfMemoryError();
172
173 /***
174 * Called in an out of memory situation.
175 *
176 * @throws OutOfMemoryError always thrown
177 */
178 public static void outOfMemory()
179 throws OutOfMemoryError {
180 if (isOutOfMemory) {
181 SystemInterface.die(-1);
182 }
183 isOutOfMemory = true;
184 SystemInterface.debugwriteln("Out of memory!");
185 throw outofmemoryerror;
186 }
187
188
189 public static HeapAddress data_segment_start;
190 public static HeapAddress data_segment_end;
191
192 public static void initializeDataSegment() {
193
194
195 data_segment_start = (HeapAddress) HeapAddress.getNull().offset(-1);
196 data_segment_end = (HeapAddress) HeapAddress.getNull().offset(-1);
197 }
198
199 public static final boolean isInDataSegment(Address a) {
200 boolean b = a.difference(data_segment_start) > 0 &&
201 a.difference(data_segment_end) < 0;
202 return b;
203 }
204
205 public static boolean isValidHeapAddress(Address a) {
206 return DefaultHeapAllocator.isValidHeapAddress(a);
207 }
208
209 public static boolean getGCBit(Object o) {
210 int status = HeapAddress.addressOf(o).offset(ObjectLayout.STATUS_WORD_OFFSET).peek4();
211 return (status & ObjectLayout.GC_BIT) != 0;
212 }
213
214 public static void setGCBit(Object o, boolean b) {
215 HeapAddress a = (HeapAddress) HeapAddress.addressOf(o).offset(ObjectLayout.STATUS_WORD_OFFSET);
216 int status = a.peek4();
217 if (b) status |= ObjectLayout.GC_BIT;
218 else status &= ~ObjectLayout.GC_BIT;
219 a.poke4(status);
220 }
221
222 public static int[] getScalarObjectReferenceOffsets(Object o) {
223 jq_Class t = (jq_Class) jq_Reference.getTypeOf(o);
224 return t.getReferenceOffsets();
225 }
226
227 /***
228 * Check if the object references are legal up to a given depth.
229 *
230 * @param o
231 * @param depth
232 * @return true if object refs are legal
233 */
234 public static boolean checkObjectReferences(Object o, int depth) {
235 jq_Reference t = jq_Reference.getTypeOf(o);
236 if (t instanceof jq_Array) {
237 jq_Type elementType = ((jq_Array) t).getElementType();
238 if (elementType.isReferenceType() && !elementType.isAddressType()) {
239 int length = Array.getLength(o);
240 for (int i = 0; i < length; ++i) {
241 Address a = HeapAddress.addressOf(o).offset(ObjectLayout.ARRAY_ELEMENT_OFFSET + i * HeapAddress.size()).peek();
242 if (!isObjectAssignableType(a, (jq_Reference) elementType)) return false;
243 }
244 }
245 } else {
246 jq_InstanceField[] f = ((jq_Class) t).getInstanceFields();
247 for (int i = 0; i < f.length; ++i) {
248 jq_Type ft = f[i].getType();
249 if (ft.isReferenceType() && !ft.isAddressType()) {
250 Address a = HeapAddress.addressOf(o).offset(f[i].getOffset()).peek();
251 if (!isObjectAssignableType(a, (jq_Reference) ft)) return false;
252 }
253 }
254 }
255 return true;
256 }
257
258 /***
259 * Returns true if the given address looks like it points to an object.
260 *
261 * @param a
262 * @return true if it looks like a valid object
263 */
264 public static boolean isValidObject(Address a) {
265 return isValidObject(a, 0);
266 }
267
268 /***
269 * Returns true if the given address looks like it points to an object.
270 * Checks up to the given depth of object nesting.
271 *
272 * @param a
273 * @param depth
274 * @return true if it looks like a valid object
275 */
276 public static boolean isValidObject(Address a, int depth) {
277 if (TRACE) Debug.writeln("Checking if valid object ref: ", a);
278 if (!isValidHeapAddress(a)) {
279 if (TRACE) Debug.writeln("Cannot be object, invalid address");
280 return false;
281 }
282 Address vt = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
283 if (!isValidVTable(vt)) {
284 if (TRACE) Debug.writeln("Cannot be object, invalid vtable: ", vt);
285 return false;
286 }
287 if (depth > 0) {
288 Object o = ((HeapAddress) a).asObject();
289 if (!checkObjectReferences(o, depth)) {
290 return false;
291 }
292 }
293 if (TRACE) Debug.writeln("Valid object: ", a);
294 return true;
295 }
296
297 /***
298 * Returns true if the given address looks like it points to an array.
299 *
300 * @param a
301 * @return true if it looks like a valid array
302 */
303 public static boolean isValidArray(Address a) {
304 return isValidArray(a, 0);
305 }
306
307 /***
308 * Returns true if the given address looks like it points to an array.
309 * Checks up to the given depth of object nesting.
310 *
311 * @param a
312 * @param depth
313 * @return true if it looks like a valid array
314 */
315 public static boolean isValidArray(Address a, int depth) {
316 if (TRACE) Debug.writeln("Checking if valid array: ", a);
317 if (!isValidHeapAddress(a)) {
318 if (TRACE) Debug.writeln("Cannot be array, invalid address");
319 return false;
320 }
321 Address vt = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
322 if (!isValidArrayVTable(vt)) {
323 if (TRACE) Debug.writeln("Cannot be object, invalid array vtable: ", vt);
324 return false;
325 }
326 if (TRACE) Debug.writeln("Valid array: ", a);
327 if (depth > 0) {
328 Object o = ((HeapAddress) a).asObject();
329 jq_Array t = (jq_Array) jq_Reference.getTypeOf(o);
330 jq_Type elementType = ((jq_Array) t).getElementType();
331 if (elementType.isReferenceType() && !elementType.isAddressType()) {
332 int length = Array.getLength(o);
333 for (int i = 0; i < length; ++i) {
334 Address a2 = HeapAddress.addressOf(o).offset(ObjectLayout.ARRAY_ELEMENT_OFFSET + i * HeapAddress.size()).peek();
335 if (!isObjectAssignableType(a2, (jq_Reference) elementType)) return false;
336 }
337 }
338 }
339 return true;
340 }
341
342 /***
343 * Return true if the given address looks like it points to a vtable.
344 *
345 * @param a
346 * @return true if it looks like a vtable
347 */
348 public static boolean isValidVTable(Address a) {
349 if (TRACE) Debug.writeln("Checking if vtable: ", a);
350 if (!isValidHeapAddress(a)) {
351 if (TRACE) Debug.writeln("Cannot be vtable, invalid address");
352 return false;
353 }
354 Address vtableTypeAddr = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
355 jq_Reference r = PrimordialClassLoader.getAddressArray();
356 if (!isObjectExactType(vtableTypeAddr, r)) {
357 if (TRACE) Debug.writeln("Cannot be vtable, has wrong type: ", vtableTypeAddr);
358 return false;
359 }
360 boolean b = isValidReferenceType((HeapAddress) a.peek());
361 if (TRACE) {
362 if (b) Debug.writeln("Valid vtable: ", a);
363 else Debug.writeln("Cannot be vtable, invalid type in vtable[0]: ", a.peek());
364 }
365 return b;
366 }
367
368 /***
369 * Return true if the given address looks like it points to a vtable for an array object.
370 *
371 * @param a
372 * @return true if it looks like a valid array vtable
373 */
374 public static boolean isValidArrayVTable(Address a) {
375 if (TRACE) Debug.writeln("Checking if array vtable: ", a);
376 if (!isValidHeapAddress(a)) {
377 if (TRACE) Debug.writeln("Cannot be array vtable, invalid address");
378 return false;
379 }
380 Address vtableTypeAddr = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
381 jq_Reference r = PrimordialClassLoader.getAddressArray();
382 if (!isObjectExactType(vtableTypeAddr, r)) {
383 if (TRACE) Debug.writeln("Cannot be array vtable, has wrong type: ", vtableTypeAddr);
384 return false;
385 }
386 boolean b = isValidArrayType((HeapAddress) a.peek());
387 if (TRACE) {
388 if (b) Debug.writeln("Valid array vtable: ", a);
389 else Debug.writeln("Cannot be array vtable, invalid type in vtable[0]: ", a.peek());
390 }
391 return b;
392 }
393
394 /***
395 * Return true if the given address looks like it points to an object whose type is
396 * exactly the given reference type.
397 *
398 * @param a
399 * @param t
400 * @return true if it looks like an object of the correct type
401 */
402 public static boolean isObjectExactType(Address a, jq_Reference t) {
403 if (TRACE) {
404 Debug.writeln("Checking if matching type: ", a);
405 Debug.writeln(t.getDesc());
406 }
407 if (!isValidHeapAddress(a)) {
408 if (TRACE) Debug.writeln("Cannot be type, invalid address");
409 return false;
410 }
411
412 Address vtable = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
413 if (!isValidHeapAddress(vtable)) {
414 if (TRACE) Debug.writeln("Cannot be type, invalid vtable address: ", vtable);
415 return false;
416 }
417 Address type = vtable.peek();
418 Address expected = HeapAddress.addressOf(t);
419 boolean b = expected.difference(type) == 0;
420 if (TRACE) {
421 if (b) Debug.writeln("Matching type: ", type);
422 else {
423 Debug.writeln("Not matching type: ", type);
424 Debug.writeln(jq_Reference.getTypeOf(((HeapAddress) a).asObject()).getDesc());
425 }
426 }
427 return b;
428 }
429
430 /***
431 * Return true if the given address is null or looks like it points to an object
432 * whose type is assignable to the given reference type.
433 *
434 * @param a
435 * @param t
436 * @return true if it is null or looks like an object of assignable type
437 */
438 public static boolean isObjectAssignableType(Address a, jq_Reference t) {
439 if (TRACE) {
440 Debug.writeln("Checking if assignable type: ", a);
441 Debug.writeln(t.getDesc());
442 }
443 if (a.isNull()) return true;
444 if (!isValidHeapAddress(a)) {
445 if (TRACE) Debug.writeln("Cannot be type, invalid address");
446 return false;
447 }
448
449 Address vtable = a.offset(ObjectLayout.VTABLE_OFFSET).peek();
450 if (!isValidHeapAddress(vtable)) {
451 if (TRACE) Debug.writeln("Cannot be type, invalid vtable address: ", vtable);
452 return false;
453 }
454 Address type = vtable.peek();
455 if (!isValidReferenceType(type)) {
456 if (TRACE) Debug.writeln("Cannot be type, invalid type address: ", type);
457 return false;
458 }
459 jq_Reference t2 = (jq_Reference) ((HeapAddress) type).asObject();
460 if (!TypeCheck.isAssignable(t2, t)) {
461 Debug.writeln("Not matching type");
462 Debug.writeln(t2.getDesc());
463 }
464 if (TRACE) Debug.writeln("Matching type: ", type);
465 return true;
466 }
467
468 /***
469 * Given an address, return true if it looks like it points to a jq_Class or jq_Array object.
470 *
471 * @param typeAddress
472 * @return true if it looks like a jq_Class or jq_Array object
473 */
474 public static boolean isValidReferenceType(Address typeAddress) {
475 if (TRACE) Debug.writeln("Checking if valid type: ", typeAddress);
476 if (!isValidHeapAddress(typeAddress)) {
477 if (TRACE) Debug.writeln("Cannot be type, invalid address");
478 return false;
479 }
480
481
482 Object vtable = ObjectLayoutMethods.getVTable(((HeapAddress) typeAddress).asObject());
483 boolean valid = vtable == jq_Class._class.getVTable() ||
484 vtable == jq_Array._class.getVTable();
485 if (TRACE) {
486 if (valid) Debug.writeln("Matching vtable: ", HeapAddress.addressOf(vtable));
487 else Debug.writeln("Not matching vtable: ", HeapAddress.addressOf(vtable));
488 }
489 return valid;
490 }
491
492 /***
493 * Given an address, return true if it looks like it points to a jq_Array object.
494 *
495 * @param typeAddress
496 * @return true if it looks like a jq_Array object
497 */
498 public static boolean isValidArrayType(Address typeAddress) {
499 if (TRACE) Debug.writeln("Checking if valid array type: ", typeAddress);
500 if (!isValidHeapAddress(typeAddress)) {
501 if (TRACE) Debug.writeln("Cannot be array type, invalid address");
502 return false;
503 }
504
505 Object vtable = ObjectLayoutMethods.getVTable(((HeapAddress) typeAddress).asObject());
506 boolean valid = vtable == jq_Array._class.getVTable();
507 if (TRACE) {
508 if (valid) Debug.writeln("Matching array vtable: ", HeapAddress.addressOf(vtable));
509 else Debug.writeln("Not matching array vtable: ", HeapAddress.addressOf(vtable));
510 }
511 return valid;
512 }
513
514 /***
515 * An object of this class represents a pointer to a heap address.
516 * It is a wrapped version of HeapAddress, so it can be used like
517 * an object.
518 */
519 public static class HeapPointer implements Comparable {
520
521 /*** The (actual) address. */
522 private final HeapAddress ip;
523
524 /*** Create a new heap pointer.
525 * @param ip heap pointer value
526 */
527 public HeapPointer(HeapAddress ip) { this.ip = ip; }
528
529 /*** Extract the address of this heap pointer.
530 * @return address of this heap pointer
531 */
532 public HeapAddress get() { return ip; }
533
534 /*** Compare this heap pointer to another heap pointer.
535 * @param that heap pointer to compare against
536 * @return -1 if this ip is before the given ip, 0 if it is equal
537 * to the given ip, 1 if it is after the given ip
538 */
539 public int compareTo(HeapPointer that) {
540 if (this.ip.difference(that.ip) < 0) return -1;
541 if (this.ip.difference(that.ip) > 0) return 1;
542 return 0;
543 }
544
545 /*** Compares this heap pointer to the given object.
546 * @param that object to compare to
547 * @return -1 if this is less than, 0 if this is equal, 1 if this
548 * is greater than
549 */
550 public int compareTo(java.lang.Object that) {
551 return compareTo((HeapPointer) that);
552 }
553
554 /*** Returns true if this heap pointer refers to the same location
555 * as the given heap pointer, false otherwise.
556 * @param that heap pointer to compare to
557 * @return true if the heap pointers are equal, false otherwise
558 */
559 public boolean equals(HeapPointer that) {
560 return this.ip.difference(that.ip) == 0;
561 }
562
563 /*** Compares this heap pointer with the given object.
564 * @param that object to compare with
565 * @return true if these objects are equal, false otherwise
566 */
567 public boolean equals(Object that) {
568 return equals((HeapPointer) that);
569 }
570
571 /*** Returns the hash code of this heap pointer.
572 * @return hash code
573 */
574 public int hashCode() { return this.ip.to32BitValue(); }
575
576 }
577
578 public static final jq_Class _class;
579 public static final jq_StaticMethod _clsinitAndAllocateObject;
580 public static final jq_StaticField _data_segment_start;
581 public static final jq_StaticField _data_segment_end;
582 static {
583 _class = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Allocator/HeapAllocator;");
584 _clsinitAndAllocateObject = _class.getOrCreateStaticMethod("clsinitAndAllocateObject", "(Ljoeq/Class/jq_Type;)Ljava/lang/Object;");
585 _data_segment_start = _class.getOrCreateStaticField("data_segment_start", "Ljoeq/Memory/HeapAddress;");
586 _data_segment_end = _class.getOrCreateStaticField("data_segment_end", "Ljoeq/Memory/HeapAddress;");
587 }
588 }