src/mm/cacao-gc/compact.c

   1 /* mm/cacao-gc/compact.c - GC module for compacting heap regions
   2
   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
   7
   8    This file is part of CACAO.
   9
  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.
  14
  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.
  19
  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
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Michael Starzinger
  28
  29    $Id$
  30
  31 */
  32
  33
  34 #include "config.h"
  35 #include "vm/types.h"
  36
  37 #include "gc.h"
  38 #include "heap.h"
  39 #include "mark.h"
  40 #include "mm/memory.h"
  41 #include "toolbox/logging.h"
  42
  43
  44 /* Threading macros ***********************************************************/
  45
  46 #define GC_THREAD_BIT 0x01
  47
  48 #define GC_IS_THREADED(ptr)       (((ptrint) ptr) & GC_THREAD_BIT)
  49 #define GC_REMOVE_THREAD_BIT(ptr) (((ptrint) ptr) & ~GC_THREAD_BIT)
  50 #define GC_SET_THREAD_BIT(ptr)    (((ptrint) ptr) | GC_THREAD_BIT)
  51
  52 #define GC_THREAD(ref, refptr, start, end) \
  53         if (POINTS_INTO(ref, start, end)) { \
  54                 GC_ASSERT(GC_IS_MARKED(ref)); \
  55                 *refptr = (java_objectheader *) ref->vftbl; \
  56                 ref->vftbl = (struct _vftbl *)  GC_SET_THREAD_BIT(refptr); \
  57         }
  58
  59
  60 /* compact_thread_rootset ******************************************************
  61
  62    Threads all the references in the rootset
  63
  64    IN:
  65       rs........Rootset containing the references to be threaded.
  66       start.....Region to be compacted start here
  67       end.......Region to be compacted ends here
  68
  69 *******************************************************************************/
  70
  71 void compact_thread_rootset(rootset_t *rs, void *start, void *end)
  72 {
  73         java_objectheader  *ref;
  74         java_objectheader **refptr;
  75         int i;
  76
  77         GC_LOG2( printf("threading in rootsets\n"); );
  78
  79         /* walk through all rootsets */
  80         while (rs) {
  81
  82                 /* walk through the references of this rootset */
  83                 for (i = 0; i < rs->refcount; i++) {
  84
  85                         /* load the reference */
  86                         refptr = rs->refs[i];
  87                         ref = *( refptr );
  88
  89                         GC_LOG2( printf("\troot pointer to %p\n", (void *) ref); );
  90
  91                         /* thread the references */
  92                         GC_THREAD(ref, refptr, start, end);
  93
  94                 }
  95
  96                 /* skip to next rootset in chain */
  97                 rs = rs->next;
  98
  99         }
 100 }
 101
 102
 103 /* compact_thread_classes ******************************************************
 104
 105    Threads all the references from classinfo structures (static fields)
 106
 107    IN:
 108       start.....Region to be compacted start here
 109       end.......Region to be compacted ends here
 110
 111 *******************************************************************************/
 112
 113 void compact_thread_classes(void *start, void *end)
 114 {
 115         java_objectheader  *ref;
 116         java_objectheader **refptr;
 117         classinfo          *c;
 118         fieldinfo          *f;
 119         /*hashtable_classloader_entry *cle;*/
 120         void *sys_start, *sys_end;
 121         int i;
 122
 123         GC_LOG2( printf("threading in classes\n"); );
 124
 125         /* TODO: cleanup!!! */
 126         sys_start = heap_region_sys->base;
 127         sys_end = heap_region_sys->ptr;
 128
 129 #if 0
 130         /* walk through all classloaders */
 131         for (i = 0; i < hashtable_classloader->size; i++) {
 132                 cle = hashtable_classloader->ptr[i];
 133
 134                 while (cle) {
 135
 136                         /* thread the classloader */
 137                         refptr = &( cle->object );
 138                         ref = *( refptr );
 139                         GC_LOG2( printf("\tclassloader from hashtable at %p\n", (void *) ref); );
 140                         GC_THREAD(ref, refptr, start, end);
 141
 142                         cle = cle->hashlink;
 143                 }
 144         }
 145 #endif
 146
 147         /* walk through all classinfo blocks */
 148         for (c = sys_start; c < (classinfo *) sys_end; c++) {
 149
 150                 /* thread the classloader */
 151                 /*refptr = &( c->classloader );
 152                 ref = *( refptr );
 153                 GC_LOG2( printf("\tclassloader from classinfo at %p\n", (void *) ref); );
 154                 GC_THREAD(ref, refptr, start, end);*/
 155
 156                 /* walk through all fields */
 157                 f = c->fields;
 158                 for (i = 0; i < c->fieldscount; i++, f++) {
 159
 160                         /* check if this is a static reference */
 161                         if (!IS_ADR_TYPE(f->type) || !(f->flags & ACC_STATIC))
 162                                 continue;
 163
 164                         /* load the reference */
 165                         refptr = (java_objectheader **) &(f->value);
 166                         ref = *( refptr );
 167
 168                         GC_LOG2( printf("\tclass-field points to %p\n", (void *) ref); );
 169                         /*GC_LOG2(
 170                                 printf("\tfield: "); field_print(f); printf("\n");
 171                                 printf("\tclass-field points to ");
 172                                 if (ref == NULL) {
 173                                         printf("(NULL)\n");
 174                                 } else if (GC_IS_THREADED(ref->vftbl)) {
 175                                         printf("(threaded)\n");
 176                                 } else {
 177                                         heap_print_object(ref); printf("\n");
 178                                 }
 179                         );*/
 180
 181                         /* thread the reference */
 182                         GC_THREAD(ref, refptr, start, end);
 183
 184                 }
 185
 186         }
 187
 188 }
 189
 190
 191 /* compact_thread_references ***************************************************
 192
 193    Threads all the references of an object.
 194
 195    IN:
 196       o.........Object containing the references to be threaded.
 197       start.....Region to be compacted start here
 198       end.......Region to be compacted ends here
 199
 200 *******************************************************************************/
 201
 202 void compact_thread_references(java_objectheader *o, void *start, void *end)
 203 {
 204         java_objectheader  *ref;
 205         java_objectheader **refptr;
 206
 207         GC_LOG2( printf("threading in ");
 208                         heap_print_object(o); printf("\n"); );
 209
 210         if (IS_ARRAY(o)) {
 211
 212                 /* walk through the references of an Array */
 213                 FOREACH_ARRAY_REF(o,ref,refptr,
 214
 215                         GC_LOG2( printf("\tarray-entry points to %p\n", (void *) ref); );
 216
 217                         GC_THREAD(ref, refptr, start, end);
 218
 219                 );
 220
 221         } else {
 222
 223                 /* walk through the references of an Object */
 224                 FOREACH_OBJECT_REF(o,ref,refptr,
 225
 226                         GC_LOG2( printf("\tobject-field points to %p\n", (void *) ref); );
 227
 228                         GC_THREAD(ref, refptr, start, end);
 229
 230                 );
 231
 232         }
 233 }
 234
 235
 236 /* compact_unthread_references *************************************************
 237
 238    Unthreads all the references which previousely pointed to an object. The
 239    object itself is the head of the threading chain. All the references in the
 240    chain once pointed to the object and will point to it's new location
 241    afterwards.
 242
 243    IN:
 244       o.......Head of the threading chain
 245       new.....New Location of the object after compaction
 246
 247 *******************************************************************************/
 248
 249 void compact_unthread_references(java_objectheader *o, void *new)
 250 {
 251         java_objectheader **refptr;
 252         ptrint tmp;
 253
 254         GC_LOG2( printf("unthreading in ...\n"); );
 255
 256         /* some quick sanity checks */
 257         GC_ASSERT(o);
 258         GC_ASSERT(GC_IS_THREADED(o->vftbl));
 259
 260         /* walk down the threaded chain */
 261         refptr = (java_objectheader **) (ptrint) o->vftbl;
 262         while (GC_IS_THREADED(refptr)) {
 263
 264                 /* remove the threading bit */
 265                 refptr = (java_objectheader **) GC_REMOVE_THREAD_BIT(refptr);
 266
 267                 GC_LOG2( printf("\treference at %p\n", (void *) refptr); );
 268
 269                 /* update the reference in the chain */
 270                 tmp = (ptrint) *refptr;
 271                 *refptr = (java_objectheader *) (ptrint) new;
 272
 273                 /* skip to the next chain value */
 274                 refptr = (java_objectheader **) tmp;
 275
 276         }
 277
 278         /* finally restore the original vftbl pointer */
 279         o->vftbl = (struct _vftbl *) refptr;
 280         GC_ASSERT(o->vftbl);
 281
 282         GC_LOG2( printf("\t... pointed to "); heap_print_object(o); printf("\n"); );
 283         GC_LOG2( printf("\t... now points to %p\n", (void *) new); );
 284
 285 }
 286
 287
 288 /* compact_move ****************************************************************
 289
 290    Moves the content (including header) of an object around in memory
 291
 292    NOTE: Memory locations may overlap!
 293    NOTE: The size of the object can change by moving it around (hashcode)!
 294
 295    IN:
 296       old......Old Location of the object before compaction
 297       new......New Location of the object after compaction
 298       size.....Size of the object in bytes
 299
 300    OUT:
 301       New size of the object after moving it
 302
 303 *******************************************************************************/
 304
 305 u4 compact_move(u1 *old, u1 *new, u4 size)
 306 {
 307         s4 hashcode;
 308         u4 new_size;
 309
 310         GC_ASSERT(new <= old);
 311
 312         /* check if locations overlap */
 313         if (new + size < old) {
 314                 /* overlapping: NO */
 315
 316                 /* copy old object content to new location */
 317                 MCOPY(new, old, u1, size);
 318
 319 #if !defined(NDEBUG)
 320                 /* invalidate old object */
 321                 MSET(old, MEMORY_CLEAR_BYTE, u1, size);
 322 #endif
 323
 324         } else {
 325                 /* overlapping: YES */
 326
 327                 GC_LOG2( printf("\tcompact_move(old=%p, new=%p, size=0x%x) overlapps!", old, new, size) );
 328
 329                 /* copy old object content to new location */
 330                 MMOVE(new, old, u1, size);
 331
 332         }
 333
 334         new_size = size;
 335
 336         /* check if we need to attach the hashcode to the object */
 337         if (GC_TEST_FLAGS((java_objectheader *) new, HDRFLAG_HASH_TAKEN)) {
 338
 339                 /* TODO: move this whole bunch to heap_attach_hashcode() */
 340
 341                 /* change the flags accordingly */
 342                 GC_CLEAR_FLAGS((java_objectheader *) new, HDRFLAG_HASH_TAKEN);
 343                 GC_SET_FLAGS((java_objectheader *) new, HDRFLAG_HASH_ATTACHED);
 344
 345                 /* attach the hashcode at the end of the object */
 346                 new_size += SIZEOF_VOID_P;
 347                 hashcode = (s4) (ptrint) old;
 348                 *( (s4 *) (new + new_size - SIZEOF_VOID_P) ) = hashcode; /* TODO: clean this up */
 349
 350                 GC_ASSERT(new + SIZEOF_VOID_P < old);
 351                 GC_LOG2( dolog("GC: Hash attached: %d (0x%08x) to new object at %p", hashcode, hashcode, new); );
 352
 353         }
 354
 355         return new_size;
 356 }
 357
 358
 359 /* compact_me ******************************************************************
 360
 361    This function actually does the compaction in two passes. Look at the source
 362    for further details about the passes.
 363
 364    IN:
 365       rs.........Rootset, needed to update the root references
 366       region.....Region to be compacted
 367
 368 *******************************************************************************/
 369
 370 void compact_me(rootset_t *rs, regioninfo_t *region)
 371 {
 372         u1 *ptr;
 373         u1 *ptr_new;
 374         java_objectheader *o;
 375         u4 o_size;
 376         u4 o_size_new;
 377         u4 used;
 378
 379         GC_LOG( dolog("GC: Compaction Phase 0 started ..."); );
 380
 381         /* Phase 0:
 382          *  - thread all references in classes
 383          *  - thread all references in the rootset */
 384         /*compact_thread_classes(region->base, region->ptr);*/
 385         compact_thread_rootset(rs, region->base, region->ptr);
 386
 387         GC_LOG( dolog("GC: Compaction Phase 1 started ..."); );
 388
 389         /* Phase 1:
 390          *  - scan the heap
 391          *  - thread all references
 392          *  - update forward references */
 393         ptr = region->base; ptr_new = region->base;
 394         while (ptr < region->ptr) {
 395                 o = (java_objectheader *) ptr;
 396
 397                 /* uncollectable items should never be compacted */
 398                 GC_ASSERT(!GC_TEST_FLAGS(o, HDRFLAG_UNCOLLECTABLE));
 399
 400                 /* if this object is already part of a threaded chain ... */
 401                 if (GC_IS_THREADED(o->vftbl)) {
 402
 403                         /* ... unthread the reference chain */
 404                         compact_unthread_references(o, ptr_new);
 405
 406                 }
 407
 408                 /* get the object size (objectheader is now unthreaded) */
 409                 o_size = get_object_size(o);
 410
 411                 /* only marked objects survive */
 412                 if (GC_IS_MARKED(o)) {
 413
 414 #if defined(GCCONF_HDRFLAG_REFERENCING)
 415                         /* check if this objects contains references */
 416                         if (GC_TEST_FLAGS(o, HDRFLAG_REFERENCING))
 417 #endif
 418
 419                         /* thread all the references in this object */
 420                         compact_thread_references(o, region->base, region->ptr);
 421
 422                         /* object survives, place next object behind it */
 423                         ptr_new += o_size;
 424
 425                         /* size might change because of attached hashcode */
 426                         if (GC_TEST_FLAGS(o, HDRFLAG_HASH_TAKEN))
 427                                 ptr_new += SIZEOF_VOID_P;
 428                 }
 429
 430                 /* skip to next object */
 431                 ptr += o_size;
 432         }
 433
 434         GC_LOG( dolog("GC: Compaction Phase 2 started ..."); );
 435
 436         /* Phase 2:
 437          *  - scan the heap again
 438          *  - update backward references
 439          *  - move the objects */
 440         used = 0;
 441         ptr = region->base; ptr_new = region->base;
 442         while (ptr < region->ptr) {
 443                 o = (java_objectheader *) ptr;
 444
 445                 /* if this object is still part of a threaded chain ... */
 446                 if (GC_IS_THREADED(o->vftbl)) {
 447
 448                         /* ... unthread the reference chain */
 449                         compact_unthread_references(o, ptr_new);
 450
 451                 }
 452
 453                 /* get the object size (objectheader is now unthreaded) */
 454                 o_size = get_object_size(o);
 455
 456                 /* move the surviving objects */
 457                 if (GC_IS_MARKED(o)) {
 458
 459                         GC_LOG2( printf("moving: %08x -> %08x (%d bytes)\n",
 460                                         (ptrint) ptr, (ptrint) ptr_new, o_size); );
 461
 462                         /* unmark the object */
 463                         GC_CLEAR_MARKED(o);
 464
 465                         /* move the object (size can change) */
 466                         o_size_new = compact_move(ptr, ptr_new, o_size);
 467
 468                         /* object survives, place next object behind it */
 469                         ptr_new += o_size_new;
 470                         used += o_size_new;
 471                 }
 472
 473                 /* skip to next object */
 474                 ptr += o_size;
 475         }
 476
 477         GC_LOG( dolog("GC: Compaction finished."); );
 478
 479         GC_LOG( printf("Region-Used: %d -> %d\n", region->size - region->free, used); )
 480         GC_LOG( printf("Region-Free: %d -> %d\n", region->free, region->size - used); )
 481
 482         /* update the region information */
 483         region->ptr = ptr_new;
 484         region->free = region->size - used;
 485
 486 }
 487
 488
 489 /*
 490  * These are local overrides for various environment variables in Emacs.
 491  * Please do not remove this and leave it at the end of the file, where
 492  * Emacs will automagically detect them.
 493  * ---------------------------------------------------------------------
 494  * Local variables:
 495  * mode: c
 496  * indent-tabs-mode: t
 497  * c-basic-offset: 4
 498  * tab-width: 4
 499  * End:
 500  * vim:noexpandtab:sw=4:ts=4:
 501  */