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 rootset\n"); );
  78
  79         /* walk through the references of this rootset */
  80         for (i = 0; i < rs->refcount; i++) {
  81
  82                 /* load the reference */
  83                 refptr = rs->refs[i];
  84                 ref = *( refptr );
  85
  86                 GC_LOG2( printf("\troot pointer to %p\n", (void *) ref); );
  87
  88                 /* thread the references */
  89                 GC_THREAD(ref, refptr, start, end);
  90
  91         }
  92 }
  93
  94
  95 /* compact_thread_classes ******************************************************
  96
  97    Threads all the references from classinfo structures (static fields)
  98
  99    IN:
 100       start.....Region to be compacted start here
 101       end.......Region to be compacted ends here
 102
 103 *******************************************************************************/
 104
 105 void compact_thread_classes(void *start, void *end)
 106 {
 107         java_objectheader  *ref;
 108         java_objectheader **refptr;
 109         classinfo          *c;
 110         fieldinfo          *f;
 111         void *sys_start, *sys_end;
 112         int i;
 113
 114         GC_LOG2( printf("threading in classes\n"); );
 115
 116         /* TODO: cleanup!!! */
 117         sys_start = heap_region_sys->base;
 118         sys_end = heap_region_sys->ptr;
 119
 120         /* walk through all classinfo blocks */
 121         for (c = sys_start; c < (classinfo *) sys_end; c++) {
 122
 123                 /* walk through all fields */
 124                 f = c->fields;
 125                 for (i = 0; i < c->fieldscount; i++, f++) {
 126
 127                         /* check if this is a static reference */
 128                         if (!IS_ADR_TYPE(f->type) || !(f->flags & ACC_STATIC))
 129                                 continue;
 130
 131                         /* load the reference */
 132                         refptr = (java_objectheader **) &(f->value);
 133                         ref = *( refptr );
 134
 135                         GC_LOG2( printf("\tclass-field points to %p\n", (void *) ref); );
 136                         /*GC_LOG2(
 137                                 printf("\tfield: "); field_print(f); printf("\n");
 138                                 printf("\tclass-field points to ");
 139                                 if (ref == NULL) {
 140                                         printf("(NULL)\n");
 141                                 } else if (GC_IS_THREADED(ref->vftbl)) {
 142                                         printf("(threaded)\n");
 143                                 } else {
 144                                                 heap_print_object(ref); printf("\n");
 145                                 }
 146                         );*/
 147
 148                         /* thread the reference */
 149                         GC_THREAD(ref, refptr, start, end);
 150
 151                 }
 152
 153         }
 154
 155 }
 156
 157
 158 /* compact_thread_references ***************************************************
 159
 160    Threads all the references of an object.
 161
 162    IN:
 163       o.........Object containing the references to be threaded.
 164       start.....Region to be compacted start here
 165       end.......Region to be compacted ends here
 166
 167 *******************************************************************************/
 168
 169 void compact_thread_references(java_objectheader *o, void *start, void *end)
 170 {
 171         java_objectheader  *ref;
 172         java_objectheader **refptr;
 173
 174         GC_LOG2( printf("threading in ");
 175                         heap_print_object(o); printf("\n"); );
 176
 177         if (IS_ARRAY(o)) {
 178
 179                 /* walk through the references of an Array */
 180                 FOREACH_ARRAY_REF(o,ref,refptr,
 181
 182                         GC_LOG2( printf("\tarray-entry points to %p\n", (void *) ref); );
 183
 184                         GC_THREAD(ref, refptr, start, end);
 185
 186                 );
 187
 188         } else {
 189
 190                 /* walk through the references of an Object */
 191                 FOREACH_OBJECT_REF(o,ref,refptr,
 192
 193                         GC_LOG2( printf("\tobject-field points to %p\n", (void *) ref); );
 194
 195                         GC_THREAD(ref, refptr, start, end);
 196
 197                 );
 198
 199         }
 200 }
 201
 202
 203 /* compact_unthread_references *************************************************
 204
 205    Unthreads all the references which previousely pointed to an object. The
 206    object itself is the head of the threading chain. All the references in the
 207    chain once pointed to the object and will point to it's new location
 208    afterwards.
 209
 210    IN:
 211       o.......Head of the threading chain
 212       new.....New Location of the object after compaction
 213
 214 *******************************************************************************/
 215
 216 void compact_unthread_references(java_objectheader *o, void *new)
 217 {
 218         java_objectheader **refptr;
 219         ptrint tmp;
 220
 221         GC_LOG2( printf("unthreading in ...\n"); );
 222
 223         /* some quick sanity checks */
 224         GC_ASSERT(o);
 225         GC_ASSERT(GC_IS_THREADED(o->vftbl));
 226
 227         /* walk down the threaded chain */
 228         refptr = (java_objectheader **) (ptrint) o->vftbl;
 229         while (GC_IS_THREADED(refptr)) {
 230
 231                 /* remove the threading bit */
 232                 refptr = (java_objectheader **) GC_REMOVE_THREAD_BIT(refptr);
 233
 234                 GC_LOG2( printf("\treference at %p\n", (void *) refptr); );
 235
 236                 /* update the reference in the chain */
 237                 tmp = (ptrint) *refptr;
 238                 *refptr = (java_objectheader *) (ptrint) new;
 239
 240                 /* skip to the next chain value */
 241                 refptr = (java_objectheader **) tmp;
 242
 243         }
 244
 245         /* finally restore the original vftbl pointer */
 246         o->vftbl = (struct _vftbl *) refptr;
 247         GC_ASSERT(o->vftbl);
 248
 249         GC_LOG2( printf("\t... pointed to "); heap_print_object(o); printf("\n"); );
 250         GC_LOG2( printf("\t... now points to %p\n", (void *) new); );
 251
 252 }
 253
 254
 255 /* compact_move ****************************************************************
 256
 257    Moves the content (including header) of an object around in memory
 258
 259    NOTE: Memory locations may overlap!
 260
 261    IN:
 262       old......Old Location of the object before compaction
 263       new......New Location of the object after compaction
 264       size.....Size of the object in bytes
 265
 266 *******************************************************************************/
 267
 268 void compact_move(u1 *old, u1 *new, u4 size)
 269 {
 270
 271         GC_ASSERT(new < old);
 272
 273         /* check if locations overlap */
 274         if (old + size >= new) {
 275                 /* overlapping: NO */
 276
 277                 /* copy old object content to new location */
 278                 MCOPY(new, old, u1, size);
 279
 280                 /* invalidate old object */
 281                 MSET(old, 0x44, u1, size);
 282
 283         } else {
 284                 /* overlapping: YES */
 285
 286                 GC_LOG( dolog("GC: OVERLAPPING!!!") );
 287
 288                 /* copy old object content to new location */
 289                 MMOVE(new, old, u1, size);
 290
 291         }
 292 }
 293
 294
 295 /* compact_me ******************************************************************
 296
 297    This function actually does the compaction in two passes. Look at the source
 298    for further details about the passes.
 299
 300    IN:
 301       rs.........Rootset, needed to update the root references
 302       region.....Region to be compacted
 303
 304 *******************************************************************************/
 305
 306 void compact_me(rootset_t *rs, regioninfo_t *region)
 307 {
 308         u1 *ptr;
 309         u1 *ptr_new;
 310         java_objectheader *o;
 311         u4 o_size;
 312         u4 used;
 313
 314         GC_LOG( dolog("GC: Compaction Phase 1 started ..."); );
 315
 316         /* Phase 0:
 317          *  - thread all references in classes
 318          *  - thread all references in the rootset */
 319         compact_thread_classes(region->base, region->ptr);
 320         compact_thread_rootset(rs, region->base, region->ptr);
 321
 322         /* Phase 1:
 323          *  - scan the heap
 324          *  - thread all references
 325          *  - update forward references */
 326         ptr = region->base; ptr_new = region->base;
 327         while (ptr < (u1 *) region->ptr) {
 328                 o = (java_objectheader *) ptr;
 329
 330                 /* TODO: uncollectable items should never be compacted, but for now we do it */
 331                 /*GC_ASSERT(!GC_TEST_FLAGS(o, GC_FLAG_UNCOLLECTABLE));*/
 332                 /*if (GC_TEST_FLAGS(o, GC_FLAG_UNCOLLECTABLE)) {
 333                         GC_SET_MARKED(o);
 334                 }*/
 335
 336                 /* if this object is already part of a threaded chain ... */
 337                 if (GC_IS_THREADED(o->vftbl)) {
 338
 339                         /* ... unthread the reference chain */
 340                         compact_unthread_references(o, ptr_new);
 341
 342                 }
 343
 344                 /* get the object size (objectheader is now unthreaded) */
 345                 o_size = get_object_size(o);
 346
 347                 /* only marked objects survive */
 348                 if (GC_IS_MARKED(o)) {
 349
 350                         /* thread all the references in this object */
 351                         compact_thread_references(o, region->base, region->ptr);
 352
 353                         /* object survives, place next object behind it */
 354                         ptr_new += o_size;
 355                 }
 356
 357                 /* skip to next object */
 358                 ptr += o_size;
 359         }
 360
 361         GC_LOG( dolog("GC: Compaction Phase 2 started ..."); );
 362
 363         /* Phase 2:
 364          *  - scan the heap again
 365          *  - update backward references
 366          *  - move the objects */
 367         used = 0;
 368         ptr = region->base; ptr_new = region->base;
 369         while (ptr < (u1 *) region->ptr) {
 370                 o = (java_objectheader *) ptr;
 371
 372                 /* if this object is still part of a threaded chain ... */
 373                 if (GC_IS_THREADED(o->vftbl)) {
 374
 375                         /* ... unthread the reference chain */
 376                         compact_unthread_references(o, ptr_new);
 377
 378                 }
 379
 380                 /* get the object size (objectheader is now unthreaded) */
 381                 o_size = get_object_size(o);
 382
 383                 /* move the surviving objects */
 384                 if (GC_IS_MARKED(o)) {
 385
 386                         GC_LOG2( printf("moving: %08x -> %08x (%d bytes)\n",
 387                                         (ptrint) ptr, (ptrint) ptr_new, o_size); );
 388
 389                         /* unmark the object */
 390                         GC_CLEAR_MARKED(o);
 391
 392                         /* move the object */
 393                         compact_move(ptr, ptr_new, o_size);
 394
 395                         /* object survives, place next object behind it */
 396                         ptr_new += o_size;
 397                         used += o_size;
 398                 }
 399
 400                 /* skip to next object */
 401                 ptr += o_size;
 402         }
 403
 404         GC_LOG( dolog("GC: Compaction finished."); );
 405
 406         GC_LOG( printf("Region-Used: %d -> %d\n", region->size - region->free, used); )
 407
 408         /* update the region information */
 409         region->ptr = ptr_new;
 410         region->free = region->size - used;
 411
 412 }
 413
 414
 415 /*
 416  * These are local overrides for various environment variables in Emacs.
 417  * Please do not remove this and leave it at the end of the file, where
 418  * Emacs will automagically detect them.
 419  * ---------------------------------------------------------------------
 420  * Local variables:
 421  * mode: c
 422  * indent-tabs-mode: t
 423  * c-basic-offset: 4
 424  * tab-width: 4
 425  * End:
 426  * vim:noexpandtab:sw=4:ts=4:
 427  */