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