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_InstanceMethod;
11 import joeq.Class.jq_Reference;
12 import joeq.Class.jq_Type;
13 import joeq.Memory.Address;
14 import joeq.Memory.CodeAddress;
15 import joeq.Memory.HeapAddress;
16 import joeq.Memory.StackAddress;
17 import joeq.Runtime.Debug;
18 import joeq.Runtime.StackCodeWalker;
19 import joeq.Runtime.SystemInterface;
20 import jwutil.util.Assert;
21
22 /***
23 * SimpleAllocator is a simple version of a heap allocator.
24 * It is basically a bump-pointer allocator with a free list.
25 *
26 * @author John Whaley <jwhaley@alum.mit.edu>
27 * @version $Id: SimpleAllocator.java 2466 2006-06-07 23:12:58Z joewhaley $
28 */
29 public class SimpleAllocator extends HeapAllocator {
30
31 public static boolean NO_GC = true;
32
33 public static boolean TRACE_ALLOC = false;
34 public static boolean TRACE_FREELIST = false;
35 public static boolean TRACE_GC = false;
36
37 /***
38 * Size of blocks allocated from the OS.
39 */
40 public static final int BLOCK_SIZE = 4194304;
41
42 /***
43 * Maximum memory, in bytes, to be allocated from the OS.
44 */
45 public static
46
47 /***
48 * Threshold for direct OS allocation. When an array overflows the current block
49 * and is larger than this size, it is allocated directly from the OS.
50 */
51 public static final int LARGE_THRESHOLD = 262144;
52
53 /***
54 * Pointers to the start, current, and end of the heap.
55 */
56 private HeapAddress heapFirst, heapCurrent, heapEnd;
57
58 /***
59 * Pointer to the start of the free list.
60 */
61 private HeapAddress firstFree;
62
63 /***
64 * Pointer to the start and current of the large object list.
65 */
66 private HeapAddress firstLarge, currLarge;
67
68 /***
69 * Simple work queue for GC.
70 */
71 private AddressQueue gcWorkQueue = new CircularAddressQueue();
72
73 /***
74 * The current state of the GC bit. Flips back and forth on every GC.
75 */
76 private boolean flip;
77
78 /***
79 * The number of GC's that have occurred.
80 */
81 private int numOfGC;
82
83 /***
84 * Are we currently doing a GC? For debugging purposes.
85 */
86 private boolean inGC;
87
88 /***
89 * Are we currently doing an allocation? For debugging purposes.
90 */
91 private boolean inAlloc;
92
93 /***
94 * Smallest object size allowed in free list.
95 */
96 public static final int MIN_SIZE = Math.max(ObjectLayout.OBJ_HEADER_SIZE, 8);
97
98 /***
99 * Allocate a new block of memory from the OS and return a pointer to it,
100 * throwing an OutOfMemoryError if we cannot allocate it.
101 *
102 * @return pointer to new block of memory
103 * @throws OutOfMemoryError if cannot allocate from OS
104 */
105 static final HeapAddress allocNewBlock() throws OutOfMemoryError {
106 HeapAddress block = (HeapAddress) SystemInterface.syscalloc(BLOCK_SIZE);
107 if (block.isNull()) {
108 HeapAllocator.outOfMemory();
109 }
110 return block;
111 }
112
113 /***
114 * Given a block, return its end address.
115 *
116 * @param block memory block
117 * @return end address
118 */
119 static final HeapAddress getBlockEnd(HeapAddress block) {
120
121
122 return (HeapAddress) block.offset(BLOCK_SIZE - HeapAddress.size());
123 }
124
125 /***
126 * Given a block, return its size in bytes.
127 *
128 * @param block memory block
129 * @return size in bytes
130 */
131 static final int getBlockSize(HeapAddress block) {
132 return BLOCK_SIZE;
133 }
134
135 /***
136 * Get the next pointer of a block.
137 *
138 * @param block memory block
139 * @return pointer to next block
140 */
141 static final HeapAddress getBlockNext(HeapAddress block) {
142 return (HeapAddress) block.offset(BLOCK_SIZE - HeapAddress.size()).peek();
143 }
144
145 /***
146 * Set the next pointer of a block.
147 *
148 * @param block memory block
149 * @param next new value of pointer
150 */
151 static final void setBlockNext(HeapAddress block, HeapAddress next) {
152 block.offset(BLOCK_SIZE - HeapAddress.size()).poke(next);
153 }
154
155 /***
156 * Get the size in bytes of a free list entry.
157 *
158 * @param free free list entry
159 * @return size in bytes
160 */
161 static final int getFreeSize(HeapAddress free) {
162 return free.offset(HeapAddress.size()).peek4();
163 }
164
165 /***
166 * Set the size in bytes of a free list entry.
167 *
168 * @param free free list entry
169 * @param size size in bytes
170 */
171 static final void setFreeSize(HeapAddress free, int size) {
172 Assert._assert(size >= HeapAddress.size()*2);
173 free.offset(HeapAddress.size()).poke4(size);
174 if (true) {
175 int size2 = size - HeapAddress.size()*2;
176 SystemInterface.mem_set(free.offset(HeapAddress.size()*2), (byte)0xbd, size2);
177 }
178 }
179
180 /***
181 * Given a free list entry, return its end address.
182 *
183 * @param free free list entry
184 * @return end address
185 */
186 static final HeapAddress getFreeEnd(HeapAddress free) {
187 int size = getFreeSize(free);
188 return (HeapAddress) free.offset(size);
189 }
190
191 /***
192 * Get the next pointer of a free list entry.
193 *
194 * @param free free list entry
195 * @return pointer to next free list entry
196 */
197 static final HeapAddress getFreeNext(HeapAddress free) {
198 return (HeapAddress) free.peek();
199 }
200
201 /***
202 * Set the next pointer of a free list entry.
203 *
204 * @param free free list entry
205 * @param next new value of pointer
206 */
207 static final void setFreeNext(HeapAddress free, HeapAddress next) {
208 free.poke(next);
209 }
210
211 /***
212 * Get the next pointer of a large object entry.
213 *
214 * @param large large object entry
215 * @return pointer to next block
216 */
217 static final HeapAddress getLargeNext(HeapAddress large) {
218 int size = getLargeSize(large);
219 return (HeapAddress) large.offset(size).peek();
220 }
221
222 /***
223 * Set the next pointer of a large object entry.
224 *
225 * @param large large object entry
226 * @param next new value of pointer
227 */
228 static final void setLargeNext(HeapAddress large, HeapAddress next) {
229 int size = getLargeSize(large);
230 large.offset(size).poke(next);
231 }
232
233 /***
234 * Return the object contained in a large object entry.
235 *
236 * @param large large object entry
237 * @return object
238 */
239 static final Object getLargeObject(HeapAddress large) {
240 Object o = ((HeapAddress) large.offset(ObjectLayout.ARRAY_HEADER_SIZE)).asObject();
241 return o;
242 }
243
244 /***
245 * Get the size in bytes of a large object entry.
246 *
247 * @param large large object entry
248 * @return size in bytes
249 */
250 static final int getLargeSize(HeapAddress large) {
251 Object o = ((HeapAddress) large.offset(ObjectLayout.ARRAY_HEADER_SIZE)).asObject();
252 int size = getObjectSize(o);
253 return size;
254 }
255
256 /***
257 * Perform initialization for this allocator. This will be called before any other methods.
258 * This allocates an initial block of memory from the OS and sets up relevant pointers.
259 *
260 * @throws OutOfMemoryError if there is not enough memory for initialization
261 */
262 public void init() throws OutOfMemoryError {
263 Assert._assert(!inGC);
264 Assert._assert(!inAlloc);
265 heapCurrent = heapFirst = allocNewBlock();
266 heapEnd = getBlockEnd(heapCurrent);
267 firstFree = firstLarge = currLarge = HeapAddress.getNull();
268 }
269
270 private void addToFreeList(HeapAddress addr, HeapAddress end) {
271 int size = end.difference(addr);
272 if (size >= MIN_SIZE) {
273
274 setFreeSize(addr, size);
275 HeapAddress curr_p = firstFree;
276 HeapAddress prev_p = HeapAddress.getNull();
277 if (TRACE_FREELIST) {
278 Debug.write("Adding free block ", addr);
279 Debug.write("-", end);
280 Debug.writeln(" size ", size);
281 }
282 for (;;) {
283 if (TRACE_FREELIST) Debug.writeln("Checking ", curr_p);
284 if (curr_p.isNull() || addr.difference(curr_p) < 0) {
285 if (prev_p.isNull()) {
286 firstFree = addr;
287 if (TRACE_FREELIST) Debug.writeln("New head of free list ", firstFree);
288 } else {
289 setFreeNext(prev_p, addr);
290 if (TRACE_FREELIST) Debug.writeln("Inserting after ", prev_p);
291 }
292 setFreeNext(addr, curr_p);
293 break;
294 }
295 HeapAddress next_p = getFreeNext(curr_p);
296 prev_p = curr_p;
297 curr_p = next_p;
298 }
299 }
300 }
301
302 /***
303 * Allocates a new block of memory from the OS, sets the current block to
304 * point to it, and makes the new block the current block.
305 *
306 * @throws OutOfMemoryError if there is not enough memory for initialization
307 */
308 private void allocateNewBlock() {
309 if (TRACE_ALLOC) Debug.writeln("Allocating new memory block.");
310 if (totalMemory() >= MAX_MEMORY) {
311 HeapAllocator.outOfMemory();
312 }
313
314 addToFreeList(heapCurrent, heapEnd);
315
316
317 heapCurrent = allocNewBlock();
318 HeapAddress lastBlock = (HeapAddress) heapEnd.offset(HeapAddress.size()-BLOCK_SIZE);
319 setBlockNext(lastBlock, heapCurrent);
320 heapEnd = getBlockEnd(heapCurrent);
321 }
322
323 /***
324 * Returns the number of bytes available in the free list.
325 *
326 * @return bytes available in the free list
327 */
328 int getFreeListBytes() {
329 int freeListMem = 0;
330 HeapAddress p = firstFree;
331 while (!p.isNull()) {
332 freeListMem += getFreeSize(p);
333 p = getFreeNext(p);
334 }
335 return freeListMem;
336 }
337
338 /***
339 * Returns the number of bytes allocated in the large object list.
340 *
341 * @return bytes allocated for large objects
342 */
343 int getLargeBytes() {
344 int largeMem = 0;
345 HeapAddress p = firstLarge;
346 while (!p.isNull()) {
347 largeMem += getLargeSize(p);
348 p = getLargeNext(p);
349 }
350 return largeMem;
351 }
352
353 /***
354 * Returns an estimate of the amount of free memory available.
355 *
356 * @return bytes of free memory
357 */
358 public int freeMemory() {
359 return getFreeListBytes() + heapEnd.difference(heapCurrent);
360 }
361
362 /***
363 * Returns an estimate of the total memory allocated (both used and unused).
364 *
365 * @return bytes of memory allocated
366 */
367 public int totalMemory() {
368 int total = 0;
369 HeapAddress ptr = heapFirst;
370 while (!ptr.isNull()) {
371 total += getBlockSize(ptr);
372 ptr = getBlockNext(ptr);
373 }
374 total += getLargeBytes();
375 return total;
376 }
377
378 /***
379 * Allocate an object with the default alignment.
380 * If the object cannot be allocated due to lack of memory, throws OutOfMemoryError.
381 *
382 * @param size size of object to allocate (including object header), in bytes
383 * @param vtable vtable pointer for new object
384 * @return new uninitialized object
385 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
386 */
387 public Object allocateObject(int size, Object vtable) throws OutOfMemoryError {
388 if (TRACE_ALLOC || inAlloc || inGC) {
389 if (inAlloc) {
390 Debug.writeln("BUG! Trying to allocate during another allocation!");
391 inAlloc = false; StackCodeWalker.stackDump(CodeAddress.getNull(), StackAddress.getBasePointer());
392 }
393 if (inGC) {
394 Debug.writeln("BUG! Trying to allocate during GC!");
395 }
396 Debug.write("Allocating object of size ", size);
397 jq_Type type = (jq_Type) ((HeapAddress) HeapAddress.addressOf(vtable).peek()).asObject();
398 Debug.write(" type ");
399 Debug.write(type.getDesc());
400 Debug.writeln(" vtable ", HeapAddress.addressOf(vtable));
401 }
402 inAlloc = true;
403 if (size < ObjectLayout.OBJ_HEADER_SIZE) {
404
405 inAlloc = false;
406 HeapAllocator.outOfMemory();
407 }
408
409 size = (size + 3) & ~3;
410 HeapAddress addr = (HeapAddress) heapCurrent.offset(ObjectLayout.OBJ_HEADER_SIZE);
411 heapCurrent = (HeapAddress) heapCurrent.offset(size);
412 if (heapEnd.difference(heapCurrent) < 0) {
413
414 heapCurrent = (HeapAddress) heapCurrent.offset(-size);
415 if (TRACE_ALLOC) Debug.writeln("Not enough free space: ", heapEnd.difference(heapCurrent));
416
417 Object o = allocObjectFromFreeList(size, vtable);
418 if (o != null) {
419 inAlloc = false;
420 return o;
421 }
422
423 allocateNewBlock();
424 addr = (HeapAddress) heapCurrent.offset(ObjectLayout.OBJ_HEADER_SIZE);
425 heapCurrent = (HeapAddress) heapCurrent.offset(size);
426 Assert._assert(heapEnd.difference(heapCurrent) >= 0);
427 } else {
428 if (TRACE_ALLOC) Debug.writeln("Fast path object allocation: ", addr);
429 }
430
431 addr.offset(ObjectLayout.VTABLE_OFFSET).poke(HeapAddress.addressOf(vtable));
432 if (flip) addr.offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(ObjectLayout.GC_BIT);
433 inAlloc = false;
434 return addr.asObject();
435 }
436
437 /***
438 * Try to allocate a region of memory from the free list.
439 * Returns a pointer to the allocated memory, or null if there is no
440 * block large enough.
441 *
442 * @param size size to allocate in bytes
443 * @return pointer to allocated memory or null
444 */
445 private HeapAddress allocFromFreeList(int size) {
446
447 HeapAddress prev_p = HeapAddress.getNull();
448 HeapAddress curr_p = firstFree;
449 if (TRACE_FREELIST) Debug.writeln("Searching free list for block of size: ", size);
450 while (!curr_p.isNull()) {
451 if (TRACE_FREELIST) Debug.writeln("Looking at block ", curr_p);
452 HeapAddress next_p = getFreeNext(curr_p);
453 int areaSize = getFreeSize(curr_p);
454 if (TRACE_FREELIST) Debug.writeln("Block size ", areaSize);
455 if (areaSize >= size) {
456
457 if (TRACE_FREELIST) Debug.writeln("Block fits, zeroing ", curr_p);
458
459 SystemInterface.mem_set(curr_p, (byte) 0, areaSize);
460
461 int newSize = areaSize - size;
462 if (TRACE_FREELIST) Debug.writeln("New size of block: ", newSize);
463 HeapAddress new_next_p;
464 if (newSize >= MIN_SIZE) {
465
466 Assert._assert(newSize >= HeapAddress.size() * 2);
467 new_next_p = (HeapAddress) curr_p.offset(size);
468 setFreeNext(new_next_p, next_p);
469 setFreeSize(new_next_p, newSize);
470 if (TRACE_FREELIST) Debug.writeln("Block shrunk, now ", new_next_p);
471 } else {
472
473 new_next_p = next_p;
474 if (TRACE_FREELIST) Debug.writeln("Result too small, new next ", new_next_p);
475 }
476 if (prev_p.isNull()) {
477
478 firstFree = new_next_p;
479 if (TRACE_FREELIST) Debug.writeln("New start of free list: ", firstFree);
480 } else {
481
482 setFreeNext(prev_p, new_next_p);
483 if (TRACE_FREELIST) Debug.writeln("Inserted after ", prev_p);
484 }
485 return curr_p;
486 }
487 prev_p = curr_p;
488 curr_p = next_p;
489 }
490
491 if (TRACE_FREELIST) Debug.writeln("Nothing in free list is big enough.");
492 return HeapAddress.getNull();
493 }
494
495 /***
496 * Try to allocate an object from the free list. If there is not enough space, do a
497 * garbage collection and try again. If there is still not enough space, return null.
498 *
499 * @param size size of object in bytes
500 * @param vtable vtable for object
501 * @return allocated object, or null
502 */
503 private Object allocObjectFromFreeList(int size, Object vtable) {
504 HeapAddress addr = allocFromFreeList(size);
505 if (addr.isNull()) {
506
507 collect();
508 addr = allocFromFreeList(size);
509 if (addr.isNull()) {
510
511 return null;
512 }
513 }
514 addr = (HeapAddress) addr.offset(ObjectLayout.OBJ_HEADER_SIZE);
515 addr.offset(ObjectLayout.VTABLE_OFFSET).poke(HeapAddress.addressOf(vtable));
516 if (flip) addr.offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(ObjectLayout.GC_BIT);
517 return addr.asObject();
518 }
519
520 /***
521 * Try to allocate an array from the free list. If there is not enough space, do a
522 * garbage collection and try again. If there is still not enough space, return null.
523 *
524 * @param length number of elements in array
525 * @param size size of array in bytes
526 * @param vtable vtable for array
527 * @return allocated array, or null
528 */
529 private Object allocArrayFromFreeList(int length, int size, Object vtable) {
530 HeapAddress addr = allocFromFreeList(size);
531 if (addr.isNull()) {
532
533 collect();
534 addr = allocFromFreeList(size);
535 if (addr.isNull()) {
536
537 return null;
538 }
539 }
540 addr = (HeapAddress) addr.offset(ObjectLayout.ARRAY_HEADER_SIZE);
541 addr.offset(ObjectLayout.ARRAY_LENGTH_OFFSET).poke4(length);
542 if (flip) addr.offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(ObjectLayout.GC_BIT);
543 addr.offset(ObjectLayout.VTABLE_OFFSET).poke(HeapAddress.addressOf(vtable));
544 return addr.asObject();
545 }
546
547 /***
548 * Try to allocate a large array.
549 *
550 * @param length
551 * @param size
552 * @param vtable
553 * @return new array object
554 * @throws OutOfMemoryError
555 */
556 private Object allocLargeArray(int length, int size, Object vtable) throws OutOfMemoryError {
557 HeapAddress addr = (HeapAddress) SystemInterface.syscalloc(size + HeapAddress.size());
558 if (addr.isNull())
559 outOfMemory();
560 if (firstLarge.isNull()) {
561 firstLarge = currLarge = addr;
562 } else {
563 setLargeNext(currLarge, addr);
564 currLarge = addr;
565 }
566 addr = (HeapAddress) addr.offset(ObjectLayout.ARRAY_HEADER_SIZE);
567 addr.offset(ObjectLayout.ARRAY_LENGTH_OFFSET).poke4(length);
568 if (flip) addr.offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(ObjectLayout.GC_BIT);
569 addr.offset(ObjectLayout.VTABLE_OFFSET).poke(HeapAddress.addressOf(vtable));
570 return addr.asObject();
571 }
572
573 public static final int getObjectSize(Object o) {
574 jq_Reference t = jq_Reference.getTypeOf(o);
575 int size;
576 if (t.isArrayType()) {
577 jq_Array a = (jq_Array) t;
578 int length = Array.getLength(o);
579 size = a.getInstanceSize(length);
580 } else {
581 jq_Class c = (jq_Class) t;
582 size = c.getInstanceSize();
583 }
584 size = (size + 3) & ~3;
585 return size;
586 }
587
588 /***
589 * Allocate an object such that the first field is 8-byte aligned.
590 * If the object cannot be allocated due to lack of memory, throws OutOfMemoryError.
591 *
592 * @param size size of object to allocate (including object header), in bytes
593 * @param vtable vtable pointer for new object
594 * @return new uninitialized object
595 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
596 */
597 public Object allocateObjectAlign8(int size, Object vtable) throws OutOfMemoryError {
598 heapCurrent = (HeapAddress) heapCurrent.offset(ObjectLayout.OBJ_HEADER_SIZE).align(3).offset(-ObjectLayout.OBJ_HEADER_SIZE);
599 return allocateObject(size, vtable);
600 }
601
602 /***
603 * Allocate an array with the default alignment.
604 * If length is negative, throws NegativeArraySizeException.
605 * If the array cannot be allocated due to lack of memory, throws OutOfMemoryError.
606 *
607 * @param length length of new array
608 * @param size size of array to allocate (including array header), in bytes
609 * @param vtable vtable pointer for new array
610 * @return new array
611 * @throws NegativeArraySizeException if length is negative
612 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
613 */
614 public Object allocateArray(int length, int size, Object vtable) throws OutOfMemoryError, NegativeArraySizeException {
615 if (length < 0) throw new NegativeArraySizeException(length + " < 0");
616
617 if (TRACE_ALLOC || inAlloc || inGC) {
618 if (inAlloc) {
619 Debug.writeln("BUG! Trying to allocate during another allocation!");
620 inAlloc = false; StackCodeWalker.stackDump(CodeAddress.getNull(), StackAddress.getBasePointer());
621 }
622 if (inGC) {
623 Debug.writeln("BUG! Trying to allocate during GC!");
624 }
625 Debug.write("Allocating array of size ", size);
626 jq_Type type = (jq_Type) ((HeapAddress) HeapAddress.addressOf(vtable).peek()).asObject();
627 Debug.write(" type ");
628 Debug.write(type.getDesc());
629 Debug.write(" length ", length);
630 Debug.writeln(" vtable ", HeapAddress.addressOf(vtable));
631 }
632
633 inAlloc = true;
634 if (size < ObjectLayout.ARRAY_HEADER_SIZE) {
635
636 inAlloc = false;
637 HeapAllocator.outOfMemory();
638 }
639 size = (size + 3) & ~3;
640 HeapAddress addr = (HeapAddress) heapCurrent.offset(ObjectLayout.ARRAY_HEADER_SIZE);
641 heapCurrent = (HeapAddress) heapCurrent.offset(size);
642 if (heapEnd.difference(heapCurrent) < 0) {
643
644 heapCurrent = (HeapAddress) heapCurrent.offset(-size);
645 if (size > LARGE_THRESHOLD) {
646
647 Object o = allocLargeArray(length, size, vtable);
648 inAlloc = false;
649 return o;
650 } else {
651 Object o = allocArrayFromFreeList(length, size, vtable);
652 if (o != null) {
653 inAlloc = false;
654 return o;
655 }
656
657 allocateNewBlock();
658 addr = (HeapAddress) heapCurrent.offset(ObjectLayout.ARRAY_HEADER_SIZE);
659 heapCurrent = (HeapAddress) heapCurrent.offset(size);
660 Assert._assert(heapEnd.difference(heapCurrent) >= 0);
661 }
662 } else {
663 if (TRACE_ALLOC) Debug.writeln("Fast path array allocation: ", addr);
664 }
665
666 addr.offset(ObjectLayout.ARRAY_LENGTH_OFFSET).poke4(length);
667 if (flip) addr.offset(ObjectLayout.STATUS_WORD_OFFSET).poke4(ObjectLayout.GC_BIT);
668 addr.offset(ObjectLayout.VTABLE_OFFSET).poke(HeapAddress.addressOf(vtable));
669 inAlloc = false;
670 return addr.asObject();
671 }
672
673 /***
674 * Allocate an array such that the elements are 8-byte aligned.
675 * If length is negative, throws NegativeArraySizeException.
676 * If the array cannot be allocated due to lack of memory, throws OutOfMemoryError.
677 *
678 * @param length length of new array
679 * @param size size of array to allocate (including array header), in bytes
680 * @param vtable vtable pointer for new array
681 * @return new array
682 * @throws NegativeArraySizeException if length is negative
683 * @throws OutOfMemoryError if there is insufficient memory to perform the operation
684 */
685 public Object allocateArrayAlign8(int length, int size, Object vtable) throws OutOfMemoryError, NegativeArraySizeException {
686 heapCurrent = (HeapAddress) heapCurrent.offset(ObjectLayout.ARRAY_HEADER_SIZE).align(3).offset(-ObjectLayout.ARRAY_HEADER_SIZE);
687 return allocateArray(length, size, vtable);
688 }
689
690
691
692
693 public void collect() {
694 if (NO_GC) {
695 return;
696 }
697 if (inGC) {
698 if (TRACE_GC) Debug.writeln("BUG! Recursively calling GC!");
699
700 return;
701 }
702 inGC = true;
703 ++numOfGC;
704 Debug.write("Starting GC #", numOfGC);
705 Debug.write(" total ", totalMemory() / 1024, "K");
706 Debug.writeln(" free ", freeMemory() / 1024, "K");
707 flip = !flip;
708 SemiConservative.collect();
709 Debug.write("Finished GC #", numOfGC);
710 Debug.write(" total ", totalMemory() / 1024, "K");
711 Debug.writeln(" free ", freeMemory() / 1024, "K");
712 inGC = false;
713 }
714
715 public void sweep() {
716 updateFreeList();
717 updateLargeObjectList();
718 }
719
720 void scanGCQueue() {
721 for (;;) {
722 HeapAddress o = (HeapAddress) gcWorkQueue.pull();
723 if (TRACE_GC) Debug.writeln("Pulled object from queue: ", HeapAddress.addressOf(o));
724 if (o.isNull()) break;
725 scanObject(o.asObject());
726 }
727 }
728
729 void updateLargeObjectList() {
730 HeapAddress prev_p = HeapAddress.getNull();
731 HeapAddress curr_p = firstLarge;
732 while (!curr_p.isNull()) {
733 Object o = getLargeObject(curr_p);
734 HeapAddress next_p = getLargeNext(curr_p);
735 int status = HeapAddress.addressOf(o).offset(ObjectLayout.STATUS_WORD_OFFSET).peek4();
736 if ((status & ObjectLayout.GC_BIT) == 0) {
737 if (prev_p.isNull()) {
738 firstLarge = next_p;
739 } else {
740 setLargeNext(prev_p, next_p);
741 }
742 if (curr_p.difference(currLarge) == 0) {
743 currLarge = prev_p;
744 }
745 }
746 prev_p = curr_p;
747 curr_p = next_p;
748 }
749 }
750
751 void updateFreeList() {
752 if (TRACE_FREELIST) Debug.writeln("Updating free list.");
753
754 HeapAddress currBlock = heapFirst;
755 while (!currBlock.isNull()) {
756 HeapAddress currBlockEnd = getBlockEnd(currBlock);
757 HeapAddress p = currBlock;
758 HeapAddress currFree, prevFree;
759 prevFree = HeapAddress.getNull();
760 currFree = firstFree;
761
762 while (!currFree.isNull() && currFree.difference(p) <= 0) {
763 prevFree = currFree;
764 currFree = getFreeNext(currFree);
765 }
766
767 if (TRACE_FREELIST) {
768 Debug.write("Visiting block ", currBlock);
769 Debug.write("-", currBlockEnd);
770 Debug.write(" free list ptr ", prevFree);
771 Debug.writeln(",", currFree);
772 }
773
774 boolean lastWasFree = false;
775
776
777 while (currBlockEnd.difference(p) > 0) {
778
779 if (TRACE_FREELIST) Debug.write("ptr=", p);
780
781 if (p.difference(currFree) == 0) {
782 if (TRACE_FREELIST) Debug.write(" on free list, ");
783 p = getFreeEnd(currFree);
784 if (lastWasFree) {
785 HeapAddress nextFree = getFreeNext(currFree);
786
787 int newSize = p.difference(prevFree);
788 setFreeSize(prevFree, newSize);
789 currFree = nextFree;
790 setFreeNext(prevFree, currFree);
791 if (TRACE_FREELIST) {
792 Debug.write("prev free area extended to size ", newSize);
793 Debug.writeln(", next free=", currFree);
794 }
795 } else {
796
797 prevFree = currFree;
798 currFree = getFreeNext(currFree);
799 if (TRACE_FREELIST) Debug.writeln(" on free list. Next free=", currFree);
800 }
801 lastWasFree = true;
802 continue;
803 }
804
805 HeapAddress lastEnd = p;
806 HeapAddress obj = HeapAddress.getNull();
807
808 while (currBlockEnd.difference(p) > 0) {
809 HeapAddress p2 = (HeapAddress) p.offset(ObjectLayout.ARRAY_HEADER_SIZE);
810 boolean b2 = isValidArray(p2);
811 if (b2) {
812 obj = p2;
813 if (TRACE_FREELIST) Debug.write(" array ", obj);
814 break;
815 }
816 HeapAddress p1 = (HeapAddress) p.offset(ObjectLayout.OBJ_HEADER_SIZE);
817 boolean b1 = isValidObject(p1);
818 if (b1) {
819 obj = p1;
820 if (TRACE_FREELIST) Debug.write(" object ", obj);
821 break;
822 }
823 p = (HeapAddress) p.offset(HeapAddress.size());
824 }
825
826 if (TRACE_FREELIST) {
827 Debug.write(" ");
828 }
829 HeapAddress next_p;
830 boolean isFree;
831 if (!obj.isNull()) {
832 Object o = obj.asObject();
833 if (TRACE_FREELIST) Debug.write(jq_Reference.getTypeOf(o).getDesc());
834 int size = getObjectSize(o);
835
836 next_p = (HeapAddress) p.offset(size).align(2);
837 isFree = getGCBit(o) != flip;
838 } else {
839 next_p = p;
840 isFree = !getBlockNext(currBlock).isNull();
841 if (TRACE_FREELIST) Debug.write("<end of block>");
842 }
843
844 if (TRACE_FREELIST) Debug.writeln(isFree?" free":" notfree");
845
846 if (isFree) {
847 if (lastWasFree) {
848
849 int newSize = next_p.difference(prevFree);
850 setFreeSize(prevFree, newSize);
851 if (TRACE_FREELIST) {
852 Debug.write("Free area ", prevFree);
853 Debug.writeln(" extended to size ", newSize);
854 }
855 } else {
856 int newSize = next_p.difference(lastEnd);
857 if (newSize >= HeapAddress.size() * 2) {
858
859 setFreeNext(lastEnd, currFree);
860 setFreeSize(lastEnd, newSize);
861 if (TRACE_FREELIST) {
862 Debug.write("Inserted free area ", prevFree);
863 Debug.write(", ", lastEnd);
864 Debug.write(", ", currFree);
865 Debug.writeln(" size ", newSize);
866 }
867 if (prevFree.isNull()) {
868 firstFree = lastEnd;
869 } else {
870 setFreeNext(prevFree, lastEnd);
871 }
872 prevFree = lastEnd;
873 } else {
874 if (TRACE_FREELIST) {
875 Debug.writeln("Free area too small, skipping: ", newSize);
876 }
877 }
878 }
879 }
880 lastWasFree = isFree;
881
882 p = next_p;
883 }
884 currBlock = (HeapAddress) getBlockNext(currBlock);
885 }
886 }
887
888 void scanObject(Object obj) {
889 jq_Reference type = jq_Reference.getTypeOf(obj);
890 if (type.isClassType()) {
891 if (TRACE_GC) Debug.writeln("Scanning object ", HeapAddress.addressOf(obj));
892 int[] referenceOffsets = ((jq_Class)type).getReferenceOffsets();
893 for (int i = 0, n = referenceOffsets.length; i < n; i++) {
894 HeapAddress objRef = HeapAddress.addressOf(obj);
895 if (TRACE_GC) Debug.writeln("Scanning offset ", referenceOffsets[i]);
896 DefaultHeapAllocator.processObjectReference((HeapAddress) objRef.offset(referenceOffsets[i]));
897 }
898 } else {
899 if (TRACE_GC) Debug.writeln("Scanning array ", HeapAddress.addressOf(obj));
900 jq_Type elementType = ((jq_Array)type).getElementType();
901 if (elementType.isReferenceType() && !elementType.isAddressType()) {
902 int num_elements = Array.getLength(obj);
903 int numBytes = num_elements * HeapAddress.size();
904 HeapAddress objRef = HeapAddress.addressOf(obj);
905 HeapAddress location = (HeapAddress) objRef.offset(ObjectLayout.ARRAY_ELEMENT_OFFSET);
906 HeapAddress end = (HeapAddress) location.offset(numBytes);
907 while (location.difference(end) < 0) {
908 if (TRACE_GC) Debug.writeln("Scanning address ", location);
909 DefaultHeapAllocator.processObjectReference(location);
910 location = (HeapAddress) location.offset(HeapAddress.size());
911 }
912 }
913 }
914 }
915
916
917
918
919 public void processObjectReference(Address a) {
920 if (TRACE_GC) Debug.writeln("Processing object reference at ", a);
921 HeapAddress a2 = (HeapAddress) a.peek();
922 if (a2.isNull()) {
923 return;
924 }
925 if (getGCBit(a2.asObject()) == flip) {
926 return;
927 }
928 setGCBit(a2.asObject(), flip);
929 gcWorkQueue.push(a2);
930 }
931
932
933
934
935 public void processPossibleObjectReference(Address a) {
936 if (TRACE_GC) Debug.writeln("Processing possible object reference at ", a);
937 HeapAddress a2 = (HeapAddress) a.peek();
938 if (!isValidObject(a2, 1)) {
939 if (TRACE_GC) Debug.writeln("Not a valid object, skipping: ", a2);
940 return;
941 }
942 if (getGCBit(a2.asObject()) == flip) {
943 return;
944 }
945
946 setGCBit(a2.asObject(), flip);
947 gcWorkQueue.push(a2);
948 }
949
950
951
952
953 public boolean isInHeap(Address a) {
954 HeapAddress p = heapFirst;
955 while (!p.isNull()) {
956 int diff = a.difference(p);
957 if (diff >= 0 && diff < BLOCK_SIZE - 2 * HeapAddress.size())
958 return true;
959 p = (HeapAddress) p.offset(BLOCK_SIZE - HeapAddress.size()).peek();
960 }
961 return false;
962 }
963
964 public static final jq_Class _class;
965 public static final jq_InstanceMethod _allocateObject;
966 public static final jq_InstanceMethod _allocateObjectAlign8;
967 public static final jq_InstanceMethod _allocateArray;
968 public static final jq_InstanceMethod _allocateArrayAlign8;
969
970 static {
971 _class = (jq_Class) PrimordialClassLoader.loader.getOrCreateBSType("Ljoeq/Allocator/SimpleAllocator;");
972 _allocateObject = _class.getOrCreateInstanceMethod("allocateObject", "(ILjava/lang/Object;)Ljava/lang/Object;");
973 _allocateObjectAlign8 = _class.getOrCreateInstanceMethod("allocateObjectAlign8", "(ILjava/lang/Object;)Ljava/lang/Object;");
974 _allocateArray = _class.getOrCreateInstanceMethod("allocateArray", "(IILjava/lang/Object;)Ljava/lang/Object;");
975 _allocateArrayAlign8 = _class.getOrCreateInstanceMethod("allocateArrayAlign8", "(IILjava/lang/Object;)Ljava/lang/Object;");
976 }
977
978 }