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