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