src/mm/cacao-gc/heap.c

   1 /* mm/cacao-gc/heap.c - GC module for heap management
   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 "region.h"
  41 #include "mm/memory.h"
  42 #include "native/jni.h"
  43 #include "src/native/include/java_lang_String.h" /* TODO: fix me! */
  44 #include "toolbox/logging.h"
  45 #include "vm/exceptions.h"
  46 #include "vm/global.h"
  47 /*#include "vm/options.h"*/
  48 #include "vm/jit/stacktrace.h"
  49
  50
  51 /* Global Variables ***********************************************************/
  52
  53 /*void *heap_base;*/       /* pointer to the base of the heap */
  54 /*void *heap_ptr;*/        /* current allocation ptr for linear alloc */
  55 s4 heap_current_size;  /* current size of the heap */
  56 s4 heap_maximal_size;  /* maximal size of the heap */
  57 s4 heap_free_size;     /* free bytes on the heap */
  58 s4 heap_used_size;     /* used bytes on the heap */
  59 regioninfo_t *heap_region_sys;
  60 regioninfo_t *heap_region_main;
  61
  62
  63 /* Helper Macros **************************************************************/
  64
  65 #define GC_ALIGN_SIZE SIZEOF_VOID_P
  66 #define GC_ALIGN(length,size) ((((length) + (size) - 1) / (size)) * (size))
  67
  68
  69 void heap_init_objectheader(java_objectheader *o, u4 bytelength)
  70 {
  71         u4 wordcount;
  72
  73         /* initialize the header flags */
  74         o->hdrflags = 0;
  75
  76         /* align the size */
  77         /* TODO */
  78
  79         /* calculate the wordcount as stored in the header */
  80     /* TODO: improve this to save wordcount and without header bytes */
  81     if ((bytelength & 0x03) == 0) {
  82         GC_ASSERT((bytelength & 0x03) == 0);
  83         wordcount = (bytelength >> 2);
  84         GC_ASSERT(wordcount != 0);
  85     } else {
  86         wordcount = GC_SIZE_DUMMY;
  87     }
  88
  89         /* set the wordcount in the header */
  90     if (wordcount >= GC_SIZE_DUMMY) {
  91         GC_SET_SIZE(o, GC_SIZE_DUMMY);
  92     } else {
  93         GC_SET_SIZE(o, wordcount);
  94     }
  95
  96 }
  97
  98
  99 s4 heap_increase_size() {
 100         void *p;
 101         s4    increasesize;
 102         s4    newsize;
 103
 104         /* TODO: locking for threads!!! */
 105
 106         /* only a quick sanity check */
 107         GC_ASSERT(heap_current_size <= heap_maximal_size);
 108
 109         /* check if we are allowed to enlarge the heap */
 110         if (heap_current_size == heap_maximal_size)
 111                 exceptions_throw_outofmemory_exit();
 112
 113         /* TODO: find out how much to increase the heap??? */
 114         increasesize = heap_maximal_size - heap_current_size;
 115         GC_LOG( dolog("GC: Increasing Heap Size by %d", increasesize); );
 116
 117         /* allocate new heap from the system */
 118         newsize = heap_current_size + increasesize;
 119         p = malloc(newsize);
 120
 121         /* check if the newly allocated heap exists */
 122         if (p == NULL)
 123                 exceptions_throw_outofmemory_exit();
 124
 125         /* TODO: copy the old content to the new heap */
 126         /* TODO: find a complete rootset and update it to the new position */
 127         /* TODO: free the old heap */
 128
 129         /* set the new values */
 130         /*heap_ptr = p + (heap_ptr - heap_base);
 131         heap_base = p;*/
 132         heap_current_size = newsize;
 133         heap_free_size += increasesize;
 134
 135         GC_LOG( dolog("GC: Increasing Heap Size was successful");
 136                         heap_println_usage(); );
 137
 138         /* only a quick sanity check */
 139         GC_ASSERT(heap_current_size <= heap_maximal_size);
 140
 141         return increasesize;
 142 }
 143
 144
 145 s4 heap_get_hashcode(java_objectheader *o)
 146 {
 147         s4 hashcode;
 148
 149         if (!o)
 150                 return 0;
 151
 152         /* TODO: we need to lock the object here i think!!! */
 153
 154         /* check if there is a hash attached to this object */
 155         if (GC_TEST_FLAGS(o, HDRFLAG_HASH_ATTACHED)) {
 156
 157                 hashcode = *( (s4 *) ( ((u1 *) o) + get_object_size(o) - SIZEOF_VOID_P ) ); /* TODO: clean this up!!! */
 158                 GC_LOG( dolog("GC: Hash re-taken: %d (0x%08x)", hashcode, hashcode); );
 159
 160         } else {
 161
 162                 GC_SET_FLAGS(o, HDRFLAG_HASH_TAKEN);
 163
 164                 hashcode = (s4) (ptrint) o;
 165                 GC_LOG( dolog("GC: Hash taken: %d (0x%08x)", hashcode, hashcode); );
 166
 167         }
 168
 169         return hashcode;
 170 }
 171
 172
 173 java_objectheader *heap_alloc_intern(u4 bytelength, regioninfo_t *region)
 174 {
 175         java_objectheader *p;
 176
 177         /* only a quick sanity check */
 178         GC_ASSERT(region);
 179         GC_ASSERT(bytelength >= sizeof(java_objectheader));
 180
 181         /* align objects in memory */
 182         bytelength = GC_ALIGN(bytelength, GC_ALIGN_SIZE);
 183
 184         /* check for sufficient free space */
 185         if (bytelength > region->free) {
 186                 dolog("GC: Region out of memory!");
 187                 /* TODO: change this to gc_collect() !!! */
 188                 /*gc_call();*/
 189                 return NULL;
 190         }
 191
 192         /* allocate the object in this region */
 193         p = region->ptr;
 194         region->ptr += bytelength;
 195         region->free -= bytelength;
 196
 197         /*heap_free_size -= bytelength;
 198         heap_used_size += bytelength;*/
 199
 200         /* clear allocated memory region */
 201         GC_ASSERT(p);
 202         MSET(p, 0, u1, bytelength);
 203
 204         /* set the header information */
 205         heap_init_objectheader(p, bytelength);
 206
 207         return p;
 208 }
 209
 210
 211 /* heap_allocate ***************************************************************
 212
 213    Allocates memory on the Java heap.
 214
 215 *******************************************************************************/
 216
 217 void *heap_allocate(u4 bytelength, u4 references, methodinfo *finalizer)
 218 {
 219         java_objectheader *p;
 220
 221         /* We can't use a bool here for references, as it's passed as a
 222            bitmask in builtin_new.  Thus we check for != 0. */
 223
 224         p = heap_alloc_intern(bytelength, heap_region_main);
 225
 226         if (p == NULL)
 227                 return NULL;
 228
 229         /* TODO: can this be overwritten by cloning??? */
 230         if (finalizer != NULL) {
 231                 GC_LOG( log_text("GC: Finalizer not yet implemented!"); );
 232                 GC_SET_FLAGS(p, GC_FLAG_FINALIZER);
 233         }
 234
 235         return p;
 236 }
 237
 238
 239 void *heap_alloc_uncollectable(u4 bytelength)
 240 {
 241         java_objectheader *p;
 242
 243         /* loader.c does this a lot for classes with fieldscount equal zero */
 244         if (bytelength == 0)
 245                 return NULL;
 246
 247         p = heap_alloc_intern(bytelength, heap_region_sys);
 248
 249         if (p == NULL)
 250                 return NULL;
 251
 252         /* TODO: can this be overwritten by cloning??? */
 253         /* remember this object as uncollectable */
 254         GC_SET_FLAGS(p, GC_FLAG_UNCOLLECTABLE);
 255
 256         return p;
 257 }
 258
 259
 260 void heap_free(void *p)
 261 {
 262         GC_LOG( dolog("GC: Free %p", p); );
 263         GC_ASSERT(0);
 264 }
 265
 266
 267 /* Debugging ******************************************************************/
 268
 269 #if !defined(NDEBUG)
 270 void heap_println_usage()
 271 {
 272         printf("Current Heap Usage: Size=%d Free=%d Used=%d\n",
 273                         heap_current_size, heap_free_size, heap_used_size);
 274
 275         GC_ASSERT(heap_current_size == heap_free_size + heap_used_size);
 276 }
 277 #endif
 278
 279
 280 #if !defined(NDEBUG)
 281 void heap_print_object_flags(java_objectheader *o)
 282 {
 283         printf("0x%02x [%s%s%s%s%s]",
 284                 GC_GET_SIZE(o),
 285                 GC_TEST_FLAGS(o, GC_FLAG_FINALIZER)     ? "F" : " ",
 286                 GC_TEST_FLAGS(o, HDRFLAG_HASH_ATTACHED) ? "A" : " ",
 287                 GC_TEST_FLAGS(o, HDRFLAG_HASH_TAKEN)    ? "T" : " ",
 288                 GC_TEST_FLAGS(o, GC_FLAG_UNCOLLECTABLE) ? "U" : " ",
 289                 GC_TEST_FLAGS(o, GC_FLAG_MARKED)        ? "M" : " ");
 290 }
 291 #endif
 292
 293
 294 #if !defined(NDEBUG)
 295 void heap_print_object(java_objectheader *o)
 296 {
 297         java_arrayheader  *a;
 298         classinfo         *c;
 299
 300         /* check for null pointers */
 301         if (o == NULL) {
 302                 printf("(NULL)");
 303                 return;
 304         }
 305
 306         /* print general information */
 307         printf("%p: ", (void *) o);
 308         heap_print_object_flags(o);
 309         printf(" ");
 310
 311         /* TODO */
 312         /* maybe this is not really an object */
 313         if (/*IS_CLASS*/ o->vftbl->class == class_java_lang_Class) {
 314
 315                 /* get the class information */
 316                 c = (classinfo *) o;
 317
 318                 /* print the class information */
 319                 printf("CLS ");
 320                 class_print(c);
 321
 322         } else if (/*IS_ARRAY*/ o->vftbl->arraydesc != NULL) {
 323
 324                 /* get the array information */
 325                 a = (java_arrayheader *) o;
 326                 c = o->vftbl->class;
 327
 328                 /* print the array information */
 329                 printf("ARR ");
 330                 /*class_print(c);*/
 331                 utf_display_printable_ascii_classname(c->name);
 332                 printf(" (size=%d)", a->size);
 333
 334         } else /*IS_OBJECT*/ {
 335
 336                 /* get the object class */
 337                 c = o->vftbl->class;
 338
 339                 /* print the object information */
 340                 printf("OBJ ");
 341                 /*class_print(c);*/
 342                 utf_display_printable_ascii_classname(c->name);
 343                 if (c == class_java_lang_String) {
 344                         printf(" (string=\"");
 345                         utf_display_printable_ascii(
 346                                         javastring_toutf((java_lang_String *) o, false));
 347                         printf("\")");
 348                 }
 349
 350         }
 351 }
 352 #endif
 353
 354 #if !defined(NDEBUG)
 355 void heap_dump_region(regioninfo_t *region, bool marked_only)
 356 {
 357         java_objectheader *o;
 358         u4                 o_size;
 359
 360         /* some basic sanity checks */
 361         GC_ASSERT(region->base < region->ptr);
 362
 363         printf("Heap-Dump:\n");
 364
 365         /* walk the region in a linear style */
 366         o = region->base;
 367         while ((void *) o < region->ptr) {
 368
 369                 if (!marked_only || GC_IS_MARKED(o)) {
 370                         printf("\t");
 371                         heap_print_object(o);
 372                         printf("\n");
 373                 }
 374
 375                 /* get size of object */
 376                 o_size = get_object_size(o);
 377
 378                 /* walk to next object */
 379                 GC_ASSERT(o_size != 0);
 380                 o = ((u1 *) o) + o_size;
 381         }
 382
 383         printf("Heap-Dump finished.\n");
 384 }
 385 #endif
 386
 387
 388 s4 get_object_size(java_objectheader *o)
 389 {
 390         java_arrayheader *a;
 391         classinfo        *c;
 392         s4                o_size;
 393
 394         /* we can assume someone initialized the header */
 395         GC_ASSERT(o->hdrflags != 0);
 396
 397         /* get the wordcount from the header */
 398         o_size = GC_GET_SIZE(o);
 399
 400         /* maybe we need to calculate the size by hand */
 401         if (o_size != GC_SIZE_DUMMY) {
 402                 GC_ASSERT(o_size != 0);
 403                 o_size = o_size << 2;
 404         } else {
 405
 406                 /* TODO */
 407                 /* maybe this is not really an object */
 408                 if (/*IS_CLASS*/ o->vftbl->class == class_java_lang_Class) {
 409                         /* we know the size of a classinfo */
 410                         o_size = sizeof(classinfo);
 411
 412                 } else if (/*IS_ARRAY*/ o->vftbl->arraydesc != NULL) {
 413                         /* compute size of this array */
 414                         a = (java_arrayheader *) o;
 415                         c = o->vftbl->class;
 416                         o_size = c->vftbl->arraydesc->dataoffset +
 417                                         a->size * c->vftbl->arraydesc->componentsize;
 418
 419                 } else /*IS_OBJECT*/ {
 420                         /* get the object size */
 421                         c = o->vftbl->class;
 422                         o_size = c->instancesize;
 423                         GC_LOG( dolog("Got size (from Class): %d bytes", o_size); );
 424                 }
 425
 426         }
 427
 428         /* align the size */
 429         o_size = GC_ALIGN(o_size, GC_ALIGN_SIZE);
 430
 431         /* the hashcode attached to this object might increase the size */
 432         if (GC_TEST_FLAGS(o, HDRFLAG_HASH_ATTACHED))
 433                 o_size += SIZEOF_VOID_P;
 434
 435         return o_size;
 436 }
 437
 438
 439 java_objectheader *next;
 440
 441 void *gc_copy_forward(java_objectheader *o, void *src_start, void *src_end)
 442 {
 443         s4 o_size;
 444
 445         if (POINTS_INTO(o, src_start, src_end)) {
 446
 447                 /* update all references which point into the source region */
 448
 449                 /* NOTE: we use the marking bit here to mark object which have already
 450                  * been copied; in such a case the *vftbl contains the location of
 451                  * the copy */
 452                 if (GC_IS_MARKED(o)) {
 453
 454                         /* return the location of an already existing copy */
 455                         return o->vftbl;
 456
 457                 } else {
 458
 459                         /* calculate the size of the object to be copied */
 460                         o_size = get_object_size(o);
 461
 462                         /* copy the object pointed to by O to location NEXT */
 463                         memcpy(next, o, o_size);
 464
 465                         /* remember where the copy is located */
 466                         o->vftbl = (void *) next;
 467
 468                         /* increment NEXT to point past the copy of the object */
 469                         next = ((u1 *) next) + o_size;
 470
 471                         /* return the location of the copy */
 472                         return o->vftbl;
 473
 474                 }
 475
 476         } else {
 477
 478                 /* do not change references not pointing into the source region */
 479                 return o;
 480
 481         }
 482 }
 483
 484
 485 void gc_copy(regioninfo_t *src, regioninfo_t *dst, rootset_t *rs)
 486 {
 487         java_objectheader *scan;
 488         /*java_objectheader *next;*/
 489         /*classinfo         *c;*/
 490         java_objectheader *ref_old;
 491         java_objectheader *ref_new;
 492         int i;
 493
 494         /* initialize the scan and next pointer */
 495         scan = (java_objectheader *) dst->base;
 496         next = (java_objectheader *) dst->base;
 497
 498         /* for each root pointer R: replace R with forward(R) */
 499         for (i = 0; i < rs->refcount; i++) {
 500
 501                 ref_old = *( rs->refs[i] );
 502                 GC_LOG( printf("Will forward: ");
 503                                 heap_print_object(ref_old);
 504                                 printf("\n"); );
 505
 506                 ref_new = gc_copy_forward(ref_old, src->base, src->end);
 507
 508                 *( rs->refs[i] ) = ref_new;
 509                 GC_LOG( printf("New location: ");
 510                                 heap_print_object(ref_new);
 511                                 printf("\n"); );
 512         }
 513
 514         /* update all references for objects in the destination region.
 515          * when scan catches up with next, the algorithm is finished */
 516         while (scan < next)
 517         {
 518                 /* TODO: implement me! */
 519                 GC_LOG( printf("Will also forward pointers in ");
 520                                 heap_print_object(scan); printf("\n"); );
 521
 522                 scan = ((u1 *) scan) + get_object_size(scan);
 523         }
 524
 525         /* some basic assumptions */
 526         GC_ASSERT(scan == next);
 527         GC_ASSERT(scan < dst->end);
 528 }
 529
 530
 531 /*
 532  * These are local overrides for various environment variables in Emacs.
 533  * Please do not remove this and leave it at the end of the file, where
 534  * Emacs will automagically detect them.
 535  * ---------------------------------------------------------------------
 536  * Local variables:
 537  * mode: c
 538  * indent-tabs-mode: t
 539  * c-basic-offset: 4
 540  * tab-width: 4
 541  * End:
 542  * vim:noexpandtab:sw=4:ts=4:
 543  */