1 /* mm/cacao-gc/compact.c - GC module for compacting heap regions
3 Copyright (C) 2006 R. Grafl, A. Krall, C. Kruegel,
4 C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
5 E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
6 J. Wenninger, Institut f. Computersprachen - TU Wien
8 This file is part of CACAO.
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2, or (at
13 your option) any later version.
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
36 #include "mm/memory.h"
37 #include "toolbox/logging.h"
40 /* Threading macros ***********************************************************/
42 #define GC_THREAD_BIT 0x01
44 #define GC_IS_THREADED(ptr) (((ptrint) ptr) & GC_THREAD_BIT)
45 #define GC_REMOVE_THREAD_BIT(ptr) (((ptrint) ptr) & ~GC_THREAD_BIT)
46 #define GC_SET_THREAD_BIT(ptr) (((ptrint) ptr) | GC_THREAD_BIT)
48 #define GC_THREAD(ref, refptr, start, end) \
49 if (POINTS_INTO(ref, start, end)) { \
50 GC_ASSERT(GC_IS_MARKED(ref)); \
51 *refptr = (java_object_t *) ref->vftbl; \
52 ref->vftbl = (struct _vftbl *) GC_SET_THREAD_BIT(refptr); \
56 /* compact_thread_rootset ******************************************************
58 Threads all the references in the rootset
61 rs........Rootset containing the references to be threaded.
62 start.....Region to be compacted start here
63 end.......Region to be compacted ends here
65 *******************************************************************************/
67 static void compact_thread_rootset(rootset_t *rs, void *start, void *end)
70 java_object_t **refptr;
73 GC_LOG2( printf("threading in rootsets\n"); );
75 /* walk through all rootsets */
78 /* walk through the references of this rootset */
79 for (i = 0; i < rs->refcount; i++) {
81 /* load the reference */
82 refptr = rs->refs[i].ref;
85 GC_LOG2( printf("\troot pointer to %p\n", (void *) ref); );
87 /* thread the references */
88 GC_THREAD(ref, refptr, start, end);
92 /* skip to next rootset in chain */
99 /* compact_thread_classes ******************************************************
101 Threads all the references from classinfo structures (static fields)
104 start.....Region to be compacted start here
105 end.......Region to be compacted ends here
107 *******************************************************************************/
109 static void compact_thread_classes(void *start, void *end)
112 java_object_t **refptr;
115 /*hashtable_classloader_entry *cle;*/
116 void *sys_start, *sys_end;
119 GC_LOG2( printf("threading in classes\n"); );
121 /* TODO: cleanup!!! */
122 sys_start = heap_region_sys->base;
123 sys_end = heap_region_sys->ptr;
126 /* walk through all classloaders */
127 for (i = 0; i < hashtable_classloader->size; i++) {
128 cle = hashtable_classloader->ptr[i];
132 /* thread the classloader */
133 refptr = &( cle->object );
135 GC_LOG2( printf("\tclassloader from hashtable at %p\n", (void *) ref); );
136 GC_THREAD(ref, refptr, start, end);
143 /* walk through all classinfo blocks */
144 for (c = sys_start; c < (classinfo *) sys_end; c++) {
146 /* thread the classloader */
147 /*refptr = &( c->classloader );
149 GC_LOG2( printf("\tclassloader from classinfo at %p\n", (void *) ref); );
150 GC_THREAD(ref, refptr, start, end);*/
152 /* walk through all fields */
154 for (i = 0; i < c->fieldscount; i++, f++) {
156 /* check if this is a static reference */
157 if (!IS_ADR_TYPE(f->type) || !(f->flags & ACC_STATIC))
160 /* load the reference */
161 refptr = (java_object_t **) &(f->value);
164 GC_LOG2( printf("\tclass-field points to %p\n", (void *) ref); );
166 printf("\tfield: "); field_print(f); printf("\n");
167 printf("\tclass-field points to ");
170 } else if (GC_IS_THREADED(ref->vftbl)) {
171 printf("(threaded)\n");
173 heap_print_object(ref); printf("\n");
177 /* thread the reference */
178 GC_THREAD(ref, refptr, start, end);
187 /* compact_thread_references ***************************************************
189 Threads all the references of an object.
192 o.........Object containing the references to be threaded.
193 start.....Region to be compacted start here
194 end.......Region to be compacted ends here
196 *******************************************************************************/
198 static void compact_thread_references(java_object_t *o, void *start, void *end)
201 java_object_t **refptr;
203 GC_LOG2( printf("threading in ");
204 heap_print_object(o); printf("\n"); );
208 /* walk through the references of an Array */
209 FOREACH_ARRAY_REF(o,ref,refptr,
211 GC_LOG2( printf("\tarray-entry points to %p\n", (void *) ref); );
213 GC_THREAD(ref, refptr, start, end);
219 /* walk through the references of an Object */
220 FOREACH_OBJECT_REF(o,ref,refptr,
222 GC_LOG2( printf("\tobject-field points to %p\n", (void *) ref); );
224 GC_THREAD(ref, refptr, start, end);
232 /* compact_unthread_references *************************************************
234 Unthreads all the references which previousely pointed to an object. The
235 object itself is the head of the threading chain. All the references in the
236 chain once pointed to the object and will point to it's new location
240 o.......Head of the threading chain
241 new.....New Location of the object after compaction
243 *******************************************************************************/
245 static void compact_unthread_references(java_object_t *o, void *new)
247 java_object_t **refptr;
250 GC_LOG2( printf("unthreading in ...\n"); );
252 /* some quick sanity checks */
254 GC_ASSERT(GC_IS_THREADED(o->vftbl));
256 /* walk down the threaded chain */
257 refptr = (java_object_t **) (ptrint) o->vftbl;
258 while (GC_IS_THREADED(refptr)) {
260 /* remove the threading bit */
261 refptr = (java_object_t **) GC_REMOVE_THREAD_BIT(refptr);
263 GC_LOG2( printf("\treference at %p\n", (void *) refptr); );
265 /* update the reference in the chain */
266 tmp = (ptrint) *refptr;
267 *refptr = (java_object_t *) (ptrint) new;
269 /* skip to the next chain value */
270 refptr = (java_object_t **) tmp;
274 /* finally restore the original vftbl pointer */
275 o->vftbl = (struct _vftbl *) refptr;
278 GC_LOG2( printf("\t... pointed to "); heap_print_object(o); printf("\n"); );
279 GC_LOG2( printf("\t... now points to %p\n", (void *) new); );
284 /* compact_move ****************************************************************
286 Moves the content (including header) of an object around in memory
288 NOTE: Memory locations may overlap!
289 NOTE: The size of the object can change by moving it around (hashcode)!
292 old......Old Location of the object before compaction
293 new......New Location of the object after compaction
294 size.....Size of the object in bytes
297 New size of the object after moving it
299 *******************************************************************************/
301 static u4 compact_move(u1 *old, u1 *new, u4 size)
306 GC_ASSERT(new <= old);
308 /* check if locations overlap */
309 if (new + size < old) {
310 /* overlapping: NO */
312 /* copy old object content to new location */
313 MCOPY(new, old, u1, size);
315 #if defined(ENABLE_MEMCHECK)
316 /* invalidate old object */
317 MSET(old, MEMORY_CLEAR_BYTE, u1, size);
321 /* overlapping: YES */
323 GC_LOG2( printf("\tcompact_move(old=%p, new=%p, size=0x%x) overlapps!", old, new, size) );
325 /* copy old object content to new location */
326 MMOVE(new, old, u1, size);
332 /* check if we need to attach the hashcode to the object */
333 if (GC_TEST_FLAGS((java_object_t *) new, HDRFLAG_HASH_TAKEN)) {
335 /* TODO: move this whole bunch to heap_attach_hashcode() */
337 /* change the flags accordingly */
338 GC_CLEAR_FLAGS((java_object_t *) new, HDRFLAG_HASH_TAKEN);
339 GC_SET_FLAGS((java_object_t *) new, HDRFLAG_HASH_ATTACHED);
341 /* attach the hashcode at the end of the object */
342 new_size += SIZEOF_VOID_P;
343 hashcode = (s4) (ptrint) old;
344 *( (s4 *) (new + new_size - SIZEOF_VOID_P) ) = hashcode; /* TODO: clean this up */
346 GC_ASSERT(new + SIZEOF_VOID_P < old);
347 GC_LOG2( dolog("GC: Hash attached: %d (0x%08x) to new object at %p", hashcode, hashcode, new); );
355 /* compact_me ******************************************************************
357 This function actually does the compaction in two passes. Look at the source
358 for further details about the passes.
361 rs.........Rootset, needed to update the root references
362 region.....Region to be compacted
364 *******************************************************************************/
366 void compact_me(rootset_t *rs, regioninfo_t *region)
375 GC_LOG( dolog("GC: Compaction Phase 0 started ..."); );
378 * - thread all references in classes
379 * - thread all references in the rootset */
380 /*compact_thread_classes(region->base, region->ptr);*/
381 compact_thread_rootset(rs, region->base, region->ptr);
383 GC_LOG( dolog("GC: Compaction Phase 1 started ..."); );
387 * - thread all references
388 * - update forward references */
389 ptr = region->base; ptr_new = region->base;
390 while (ptr < region->ptr) {
391 o = (java_object_t *) ptr;
393 /* uncollectable items should never be compacted */
394 GC_ASSERT(!GC_TEST_FLAGS(o, HDRFLAG_UNCOLLECTABLE));
396 /* if this object is already part of a threaded chain ... */
397 if (GC_IS_THREADED(o->vftbl)) {
399 /* ... unthread the reference chain */
400 compact_unthread_references(o, ptr_new);
404 /* get the object size (objectheader is now unthreaded) */
405 o_size = get_object_size(o);
407 /* only marked objects survive */
408 if (GC_IS_MARKED(o)) {
410 #if defined(GCCONF_HDRFLAG_REFERENCING)
411 /* check if this objects contains references */
412 if (GC_TEST_FLAGS(o, HDRFLAG_REFERENCING))
415 /* thread all the references in this object */
416 compact_thread_references(o, region->base, region->ptr);
418 /* object survives, place next object behind it */
421 /* size might change because of attached hashcode */
422 if (GC_TEST_FLAGS(o, HDRFLAG_HASH_TAKEN))
423 ptr_new += SIZEOF_VOID_P;
426 /* skip to next object */
430 GC_LOG( dolog("GC: Compaction Phase 2 started ..."); );
433 * - scan the heap again
434 * - update backward references
435 * - move the objects */
437 ptr = region->base; ptr_new = region->base;
438 while (ptr < region->ptr) {
439 o = (java_object_t *) ptr;
441 /* if this object is still part of a threaded chain ... */
442 if (GC_IS_THREADED(o->vftbl)) {
444 /* ... unthread the reference chain */
445 compact_unthread_references(o, ptr_new);
449 /* get the object size (objectheader is now unthreaded) */
450 o_size = get_object_size(o);
452 /* move the surviving objects */
453 if (GC_IS_MARKED(o)) {
455 GC_LOG2( printf("moving: %08x -> %08x (%d bytes)\n",
456 (ptrint) ptr, (ptrint) ptr_new, o_size); );
458 /* unmark the object */
461 /* move the object (size can change) */
462 o_size_new = compact_move(ptr, ptr_new, o_size);
464 /* object survives, place next object behind it */
465 ptr_new += o_size_new;
469 /* skip to next object */
473 GC_LOG( dolog("GC: Compaction finished."); );
475 GC_LOG( printf("Region-Used: %d -> %d\n", region->size - region->free, used); )
476 GC_LOG( printf("Region-Free: %d -> %d\n", region->free, region->size - used); )
478 /* update the region information */
479 region->ptr = ptr_new;
480 region->free = region->size - used;
486 * These are local overrides for various environment variables in Emacs.
487 * Please do not remove this and leave it at the end of the file, where
488 * Emacs will automagically detect them.
489 * ---------------------------------------------------------------------
492 * indent-tabs-mode: t
496 * vim:noexpandtab:sw=4:ts=4: