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( printf("Hash re-taken: %d (0x%08x)\n", hashcode, hashcode); );
 159
 160         } else {
 161
 162                 GC_SET_FLAGS(o, HDRFLAG_HASH_TAKEN);
 163
 164                 hashcode = (s4) (ptrint) o;
 165                 GC_LOG( printf("Hash taken: %d (0x%08x)\n", 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_REFTABLE*/ o->vftbl == 0x10) {
 314                 /* printf information */
 315                 printf("LRT");
 316
 317         } else if (/*IS_CLASS*/ o->vftbl->class == class_java_lang_Class) {
 318
 319                 /* get the class information */
 320                 c = (classinfo *) o;
 321
 322                 /* print the class information */
 323                 printf("CLS ");
 324                 class_print(c);
 325
 326         } else if (/*IS_ARRAY*/ o->vftbl->arraydesc != NULL) {
 327
 328                 /* get the array information */
 329                 a = (java_arrayheader *) o;
 330                 c = o->vftbl->class;
 331
 332                 /* print the array information */
 333                 printf("ARR ");
 334                 /*class_print(c);*/
 335                 utf_display_printable_ascii_classname(c->name);
 336                 printf(" (size=%d)", a->size);
 337
 338         } else /*IS_OBJECT*/ {
 339
 340                 /* get the object class */
 341                 c = o->vftbl->class;
 342
 343                 /* print the object information */
 344                 printf("OBJ ");
 345                 /*class_print(c);*/
 346                 utf_display_printable_ascii_classname(c->name);
 347                 if (c == class_java_lang_String) {
 348                         printf(" (string=\"");
 349                         utf_display_printable_ascii(
 350                                         javastring_toutf((java_lang_String *) o, false));
 351                         printf("\")");
 352                 }
 353
 354         }
 355 }
 356 #endif
 357
 358 #if !defined(NDEBUG)
 359 void heap_dump_region(regioninfo_t *region, bool marked_only)
 360 {
 361         java_objectheader *o;
 362         u4                 o_size;
 363
 364         /* some basic sanity checks */
 365         GC_ASSERT(region->base < region->ptr);
 366
 367         printf("Heap-Dump:\n");
 368
 369         /* walk the region in a linear style */
 370         o = region->base;
 371         while ((void *) o < region->ptr) {
 372
 373                 if (!marked_only || GC_IS_MARKED(o)) {
 374                         printf("\t");
 375                         heap_print_object(o);
 376                         printf("\n");
 377                 }
 378
 379                 /* get size of object */
 380                 o_size = get_object_size(o);
 381
 382                 /* walk to next object */
 383                 GC_ASSERT(o_size != 0);
 384                 o = ((u1 *) o) + o_size;
 385         }
 386
 387         printf("Heap-Dump finished.\n");
 388 }
 389 #endif
 390
 391
 392 s4 get_object_size(java_objectheader *o)
 393 {
 394         java_arrayheader *a;
 395         classinfo        *c;
 396         s4                o_size;
 397
 398         /* we can assume someone initialized the header */
 399         GC_ASSERT(o->hdrflags != 0);
 400
 401         /* get the wordcount from the header */
 402         o_size = GC_GET_SIZE(o);
 403
 404         /* maybe we need to calculate the size by hand */
 405         if (o_size != GC_SIZE_DUMMY) {
 406                 GC_ASSERT(o_size != 0);
 407                 o_size = o_size << 2;
 408         } else {
 409
 410                 /* TODO */
 411                 /* maybe this is not really an object */
 412                 if (/*IS_REFTABLE*/ o->vftbl == 0x10) {
 413                         /* TODO: this will not work for long */
 414                         o_size = sizeof(localref_table);
 415
 416                 } else if (/*IS_CLASS*/ o->vftbl->class == class_java_lang_Class) {
 417                         /* we know the size of a classinfo */
 418                         o_size = sizeof(classinfo);
 419
 420                 } else if (/*IS_ARRAY*/ o->vftbl->arraydesc != NULL) {
 421                         /* compute size of this array */
 422                         a = (java_arrayheader *) o;
 423                         c = o->vftbl->class;
 424                         o_size = c->vftbl->arraydesc->dataoffset +
 425                                         a->size * c->vftbl->arraydesc->componentsize;
 426
 427                 } else /*IS_OBJECT*/ {
 428                         /* get the object size */
 429                         c = o->vftbl->class;
 430                         o_size = c->instancesize;
 431                         GC_LOG( dolog("Got size (from Class): %d bytes", o_size); );
 432                 }
 433
 434         }
 435
 436         /* align the size */
 437         o_size = GC_ALIGN(o_size, GC_ALIGN_SIZE);
 438
 439         /* the hashcode attached to this object might increase the size */
 440         if (GC_TEST_FLAGS(o, HDRFLAG_HASH_ATTACHED))
 441                 o_size += SIZEOF_VOID_P;
 442
 443         return o_size;
 444 }
 445
 446
 447 java_objectheader *next;
 448
 449 void *gc_copy_forward(java_objectheader *o, void *src_start, void *src_end)
 450 {
 451         s4 o_size;
 452
 453         if (POINTS_INTO(o, src_start, src_end)) {
 454
 455                 /* update all references which point into the source region */
 456
 457                 /* NOTE: we use the marking bit here to mark object which have already
 458                  * been copied; in such a case the *vftbl contains the location of
 459                  * the copy */
 460                 if (GC_IS_MARKED(o)) {
 461
 462                         /* return the location of an already existing copy */
 463                         return o->vftbl;
 464
 465                 } else {
 466
 467                         /* calculate the size of the object to be copied */
 468                         o_size = get_object_size(o);
 469
 470                         /* copy the object pointed to by O to location NEXT */
 471                         memcpy(next, o, o_size);
 472
 473                         /* remember where the copy is located */
 474                         o->vftbl = (void *) next;
 475
 476                         /* increment NEXT to point past the copy of the object */
 477                         next = ((u1 *) next) + o_size;
 478
 479                         /* return the location of the copy */
 480                         return o->vftbl;
 481
 482                 }
 483
 484         } else {
 485
 486                 /* do not change references not pointing into the source region */
 487                 return o;
 488
 489         }
 490 }
 491
 492
 493 void gc_copy(regioninfo_t *src, regioninfo_t *dst, rootset_t *rs)
 494 {
 495         java_objectheader *scan;
 496         /*java_objectheader *next;*/
 497         /*classinfo         *c;*/
 498         java_objectheader *ref_old;
 499         java_objectheader *ref_new;
 500         int i;
 501
 502         /* initialize the scan and next pointer */
 503         scan = (java_objectheader *) dst->base;
 504         next = (java_objectheader *) dst->base;
 505
 506         /* for each root pointer R: replace R with forward(R) */
 507         for (i = 0; i < rs->refcount; i++) {
 508
 509                 ref_old = *( rs->refs[i] );
 510                 GC_LOG( printf("Will forward: ");
 511                                 heap_print_object(ref_old);
 512                                 printf("\n"); );
 513
 514                 ref_new = gc_copy_forward(ref_old, src->base, src->end);
 515
 516                 *( rs->refs[i] ) = ref_new;
 517                 GC_LOG( printf("New location: ");
 518                                 heap_print_object(ref_new);
 519                                 printf("\n"); );
 520         }
 521
 522         /* update all references for objects in the destination region.
 523          * when scan catches up with next, the algorithm is finished */
 524         while (scan < next)
 525         {
 526                 /* TODO: implement me! */
 527                 GC_LOG( printf("Will also forward pointers in ");
 528                                 heap_print_object(scan); printf("\n"); );
 529
 530                 scan = ((u1 *) scan) + get_object_size(scan);
 531         }
 532
 533         /* some basic assumptions */
 534         GC_ASSERT(scan == next);
 535         GC_ASSERT(scan < dst->end);
 536 }
 537
 538
 539 /*
 540  * These are local overrides for various environment variables in Emacs.
 541  * Please do not remove this and leave it at the end of the file, where
 542  * Emacs will automagically detect them.
 543  * ---------------------------------------------------------------------
 544  * Local variables:
 545  * mode: c
 546  * indent-tabs-mode: t
 547  * c-basic-offset: 4
 548  * tab-width: 4
 549  * End:
 550  * vim:noexpandtab:sw=4:ts=4:
 551  */