mm/heap2.c

   1 #include <stddef.h>
   2 #include <unistd.h>             /* getpagesize, mmap, ... */
   3 #include <sys/mman.h>
   4 #ifndef MAP_FAILED
   5 #define MAP_FAILED ((void*) -1)
   6 #endif
   7 #include <sys/types.h>
   8 #include <stdio.h>
   9 #include "../asmpart.h"
  10 #include "../callargs.h"
  11 #include "../threads/thread.h"
  12 #include "../threads/locks.h"
  13 #include <assert.h>
  14
  15 #include "mm.h"
  16
  17 #define PAGESIZE_MINUS_ONE      (getpagesize() - 1)
  18
  19 #undef ALIGN
  20 #undef OFFSET
  21
  22 #define GC_COLLECT_STATISTICS
  23 #define FINALIZER_COUNTING
  24
  25 #undef STRUCTURES_ON_HEAP
  26 //#define STRUCTURES_ON_HEAP
  27
  28 #define false 0
  29 #define true 1
  30
  31 #include "allocator.h" /* rev. 1 allocator */
  32 #include "bitmap2.h"   /* rev. 2 bitmap management */
  33
  34 bool collectverbose;
  35
  36 void gc_call (void);
  37
  38 /* --- macros */
  39
  40 #define align_size(size)        ((size) & ~((1 << ALIGN) - 1))
  41 #define MAP_ADDRESS                     (void*) 0x10000000
  42
  43 #define VERBOSITY_MESSAGE       1
  44 #define VERBOSITY_DEBUG         2
  45 #define VERBOSITY_MISTRUST      3
  46 #define VERBOSITY_TRACE         4
  47 #define VERBOSITY_PARANOIA      5
  48 #define VERBOSITY_LIFESPAN      6
  49
  50 //#define VERBOSITY                     VERBOSITY_MESSAGE
  51 //#define VERBOSITY                     VERBOSITY_PARANOIA
  52 #define VERBOSITY                       VERBOSITY_LIFESPAN
  53
  54 /* --- file-wide variables */
  55
  56 static void*    heap_base = NULL;
  57 static SIZE             heap_size = 0;
  58 static void*    heap_top = NULL;
  59 static void*    heap_limit = NULL;
  60 static void*    heap_next_collection = NULL;
  61
  62 static bitmap_t* start_bitmap = NULL;
  63 static BITBLOCK* start_bits = NULL;
  64 static bitmap_t* reference_bitmap = NULL;
  65 static BITBLOCK* reference_bits = NULL;
  66 static bitmap_t* mark_bitmap = NULL;
  67 static BITBLOCK* mark_bits = NULL;
  68
  69 static void**   stackbottom = NULL;
  70
  71 typedef struct address_list_node {
  72         void* address;
  73         struct address_list_node* prev;
  74         struct address_list_node* next;
  75 } address_list_node;
  76
  77 static address_list_node* references = NULL;
  78 static address_list_node* finalizers = NULL;
  79
  80 #ifdef GC_COLLECT_STATISTICS
  81
  82 static unsigned long gc_collections_count = 0;
  83
  84 static unsigned long gc_alloc_total = 0;
  85 static unsigned long gc_alloc_count = 0;
  86
  87 static unsigned long gc_mark_heapblocks_visited = 0;
  88 static unsigned long gc_mark_not_aligned = 0;
  89 static unsigned long gc_mark_not_inheap = 0;
  90 static unsigned long gc_mark_not_object = 0;
  91 static unsigned long gc_mark_objects_marked = 0;
  92 static unsigned long gc_mark_already_marked = 0;
  93
  94 #endif
  95
  96 #ifdef FINALIZER_COUNTING
  97
  98 static unsigned long gc_finalizers_executed = 0;
  99 static unsigned long gc_finalizers_detected = 0;
 100
 101 #endif
 102
 103 /* --- implementation */
 104
 105 void
 106 heap_init (SIZE size,
 107                    SIZE startsize, /* when should we collect for the first time ? */
 108                    void **in_stackbottom)
 109 {
 110 #if VERBOSITY == VERBOSITY_MESSAGE
 111         fprintf(stderr, "The heap is verbose.\n");
 112 #elif VERBOSITY == VERBOSITY_DEBUG
 113         fprintf(stderr, "The heap is in debug mode.\n");
 114 #elif VERBOSITY == VERBOSITY_MISTRUST
 115         fprintf(stderr, "The heap is mistrusting us.\n");
 116 #elif VERBOSITY == VERBOSITY_TRACE
 117         fprintf(stderr, "The heap is emitting trace information.\n");
 118 #elif VERBOSITY == VERBOSITY_PARANOIA
 119         fprintf(stderr, "The heap is paranoid.\n");
 120 #elif VERBOSITY == VERBOSITY_LIFESPAN
 121         fprintf(stderr, "The heap is collecting lifespan information.\n");
 122 #endif
 123
 124         /* 1. Initialise the freelists & reset the allocator's state */
 125         allocator_init();
 126
 127         /* 2. Allocate at least (alignment!) size bytes of memory for the heap */
 128         heap_size = align_size(size + ((1 << ALIGN) - 1));
 129
 130 #if 1
 131         /* For now, we'll try to map in the stack at a fixed address...
 132            ...this will change soon. -- phil. */
 133         heap_base = (void*) mmap (MAP_ADDRESS,
 134                                                           ((size_t)heap_size + PAGESIZE_MINUS_ONE) & ~PAGESIZE_MINUS_ONE,
 135                                                           PROT_READ | PROT_WRITE,
 136                                                           MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED,
 137                                                           -1,
 138                                                           (off_t) 0);
 139 #else
 140 #if 0
 141         heap_base = malloc(heap_size);
 142 #else
 143         heap_base = (void*) mmap (NULL,
 144                                                           ((size_t)heap_size + PAGESIZE_MINUS_ONE) & ~PAGESIZE_MINUS_ONE,
 145                                                           PROT_READ | PROT_WRITE,
 146                                                           MAP_PRIVATE | MAP_ANONYMOUS,
 147                                                           -1,
 148                                                           (off_t) 0);
 149 #endif
 150         fprintf(stderr, "heap @ 0x%lx\n", heap_base);
 151 #endif
 152
 153         if (heap_base == (void*)MAP_FAILED) {
 154                 /* unable to allocate the requested amount of memory */
 155                 fprintf(stderr, "The queen, mylord, is dead!\n");
 156                 exit(-1);
 157         }
 158
 159         /* 3. Allocate the bitmaps */
 160         start_bitmap = bitmap_allocate(heap_base, heap_size);
 161         reference_bitmap = bitmap_allocate(heap_base, heap_size);
 162         mark_bitmap = bitmap_allocate(heap_base, heap_size);
 163
 164         start_bits = start_bitmap->bitmap;
 165     reference_bits = reference_bitmap->bitmap;
 166     mark_bits = mark_bitmap->bitmap;
 167
 168         /* 4. Mark the first free-area as an object-start */
 169         bitmap_setbit(start_bits, heap_base);
 170
 171         /* 5. Initialise the heap's state (heap_top, etc.) */
 172         stackbottom = in_stackbottom; /* copy the stackbottom */
 173
 174         heap_top = heap_base; /* the current end of the heap (just behind the last allocated object) */
 175         heap_limit = (void*)((long)heap_base + heap_size); /* points just behind the last accessible block of the heap */
 176
 177         /* 6. calculate a useful first collection limit */
 178         /* This is extremly primitive at this point...
 179            we should replace it with something more useful -- phil. */
 180         heap_next_collection = (void*)((long)heap_base + (heap_size / 8));
 181
 182         /* 7. Init the global reference lists & finalizer addresses */
 183         references = NULL;
 184         finalizers = NULL;
 185
 186 #ifdef STRUCTURES_ON_HEAP
 187         heap_addreference(&references);
 188         heap_addreference(&finalizers);
 189 #endif
 190 }
 191
 192 void
 193 heap_close (void)
 194 {
 195         address_list_node* curr = finalizers;
 196
 197         /* 1. Clean up on the heap... finalize all remaining objects */
 198 #if 1
 199         while (curr) {
 200                 address_list_node* prev = curr;
 201
 202                 if (curr->address) {
 203                         if (bitmap_testbit(start_bits, curr->address)) {
 204 #ifdef FINALIZER_COUNTING
 205                                 ++gc_finalizers_executed;
 206 #endif
 207                                 asm_calljavamethod(((java_objectheader*)(curr->address))->vftbl->class->finalizer, curr->address, NULL, NULL, NULL);
 208
 209                         }
 210                 }
 211
 212                 curr = curr->next;
 213                 free(prev);
 214         }
 215 #endif
 216
 217         /* 2. Release the bitmaps */
 218         bitmap_release(start_bitmap);
 219         bitmap_release(reference_bitmap);
 220         bitmap_release(mark_bitmap);
 221
 222         /* 3. Release the memory allocated to the heap */
 223         if (heap_base)
 224                 munmap(heap_base, heap_size);
 225
 226 #ifdef FINALIZER_COUNTING
 227         sprintf(logtext, "%ld objects with a finalizer", gc_finalizers_detected);
 228         dolog();
 229
 230 #ifdef GC_COLLECT_STATISTICS
 231         /* 4. output statical data */
 232         sprintf(logtext, "%ld bytes for %ld objects allocated.",
 233                         gc_alloc_total, gc_alloc_count);
 234         dolog();
 235         sprintf(logtext, "%ld garbage collections performed.", gc_collections_count);
 236         dolog();
 237         sprintf(logtext, "%ld heapblocks visited, %ld objects marked",
 238                         gc_mark_heapblocks_visited, gc_mark_objects_marked);
 239         dolog();
 240         sprintf(logtext, "    %ld out of heap.", gc_mark_not_inheap);
 241         dolog();
 242         sprintf(logtext, "    %ld visits to objects already marked.", gc_mark_already_marked);
 243         dolog();
 244         sprintf(logtext, "    %ld not an object.", gc_mark_not_object);
 245         dolog();
 246         sprintf(logtext, "    %ld potential references not aligned.", gc_mark_not_aligned);
 247         dolog();
 248 #endif
 249
 250         if (gc_finalizers_detected != gc_finalizers_executed)
 251                 sprintf(logtext, "    all finalizers executed.");
 252         else
 253                 sprintf(logtext, "    only %ld finalizers executed.", gc_finalizers_executed);
 254         dolog();
 255 #endif
 256
 257 }
 258
 259 __inline__
 260 static
 261 void
 262 heap_add_address_to_address_list(address_list_node** list, void* address)
 263 {
 264         /* Note: address lists are kept sorted to simplify finalization */
 265
 266         address_list_node* new_node = malloc(sizeof(address_list_node));
 267         new_node->address = address;
 268         new_node->next = NULL;
 269
 270         while (*list && (*list)->next) {
 271 #if VERBOSITY >= VERBOSITY_PARANOIA
 272                 if ((*list)->address == address)
 273                         fprintf(stderr,
 274                                         "Attempt to add a duplicate adress to an adress list.\n");
 275 #endif
 276
 277                 if ((*list)->next->address < address)
 278                         list = &(*list)->next;
 279                 else {
 280                         new_node->next = *list;
 281                         *list = new_node;
 282                         return;
 283                 }
 284         }
 285
 286         new_node->next = *list;
 287         *list = new_node;
 288 }
 289
 290
 291 __inline__
 292 static
 293 void
 294 heap_add_finalizer_for_object_at(void* addr)
 295 {
 296         /* Finalizers seem to be very rare... for this reason, I keep a linked
 297            list of object addresses, which have a finalizer attached. This list
 298            is kept in ascending order according to the order garbage is freed.
 299            This list is currently kept separate from the heap, but should be
 300            moved onto it, but some JIT-marker code to handle these special
 301            objects will need to be added first. -- phil. */
 302
 303         heap_add_address_to_address_list(&finalizers, addr);
 304 }
 305
 306 void*
 307 heap_allocate (SIZE               in_length,
 308                            bool           references,
 309                            methodinfo *finalizer)
 310 {
 311         SIZE    length = align_size(in_length + ((1 << ALIGN) - 1));
 312         void*   free_chunk = NULL;
 313
 314 #if VERBOSITY >= VERBOSITY_MISTRUST && 0
 315         /* check for misaligned in_length parameter */
 316         if (length != in_length)
 317                 fprintf(stderr,
 318                                 "heap2.c: heap_allocate was passed unaligned in_length parameter: %ld, \n         aligned to %ld. (mistrust)\n",
 319                                 in_length, length);
 320 #endif
 321
 322         // fprintf(stderr, "heap_allocate: 0x%lx (%ld) requested, 0x%lx (%ld) aligned\n", in_length, in_length, length, length);
 323
 324 #ifdef FINALIZER_COUNTING
 325         if (finalizer)
 326                 ++gc_finalizers_detected;
 327 #endif
 328
 329 #if VERBOSITY >= VERBOSITY_LIFESPAN && 0
 330         /* perform garbage collection to collect data for lifespan analysis */
 331         if (heap_top > heap_base)
 332                 gc_call();
 333 #endif
 334
 335         intsDisable();
 336
 337  retry:
 338         /* 1. attempt to get a free block with size >= length from the freelists */
 339         free_chunk = allocator_alloc(length);
 340
 341         /* 2. if unsuccessful, try alternative allocation strategies */
 342         if (!free_chunk) {
 343                 /* 2.a if the collection threshold would be exceeded, collect the heap */
 344                 if ((long)heap_top + length > (long)heap_next_collection) {
 345                         /* 2.a.1. collect if the next_collection threshold would be exceeded */
 346                         gc_call();
 347
 348                         /* 2.a.2. we just ran a collection, recheck the freelists */
 349                         free_chunk = allocator_alloc(length);
 350                         if (free_chunk)
 351                                 goto success;
 352
 353                         /* 2.a.3. we can't satisfy the request from the freelists, check
 354                                   against the heap_limit whether growing the heap is possible */
 355                         if ((long)heap_top + length > (long)heap_limit)
 356                                 goto failure;
 357                 }
 358
 359                 /* 2.b. grow the heap */
 360                 free_chunk = heap_top;
 361                 heap_top = (void*)((long)heap_top + length);
 362         }
 363
 364  success:
 365         /* 3.a. mark all necessary bits, store the finalizer & return the newly allocate block */
 366 #if 0
 367         /* I don't mark the object-start anymore, as it always is at the beginning of a free-block,
 368            which already is marked (Note: The first free-block gets marked in heap_init). -- phil. */
 369         bitmap_setbit(start_bits, free_chunk); /* mark the new object */
 370 #endif
 371         bitmap_setbit(start_bits, (void*)((long)free_chunk + (long)length)); /* mark the freespace behind the new object */
 372         if (references)
 373                 bitmap_setbit(reference_bits, free_chunk);
 374         else
 375                 bitmap_clearbit(reference_bits, free_chunk);
 376
 377 #if 1
 378         /* store a hint, that there's a finalizer */
 379         if (finalizer)
 380                 heap_add_finalizer_for_object_at(free_chunk);
 381 #else
 382 #   warning "finalizers disabled."
 383 #endif
 384
 385 #if VERBOSITY >= VERBOSITY_TRACE && 0
 386         fprintf(stderr, "heap_allocate: returning free block of 0x%lx bytes at 0x%lx\n", length, free_chunk);
 387 #endif
 388 #if VERBOSITY >= VERBOSITY_PARANOIA && 0
 389         fprintf(stderr, "heap_allocate: reporting heap state variables:\n");
 390         fprintf(stderr, "\theap top              0x%lx\n", heap_top);
 391         fprintf(stderr, "\theap size             0x%lx (%ld)\n", heap_size, heap_size);
 392         fprintf(stderr, "\theap_limit            0x%lx\n", heap_limit);
 393         fprintf(stderr, "\theap next collection  0x%lx\n", heap_next_collection);
 394 #endif
 395
 396 #ifdef GC_COLLECT_STATISTICS
 397         gc_alloc_total += length;
 398         ++gc_alloc_count;
 399 #endif
 400
 401         return free_chunk;
 402
 403  failure:
 404         /* 3.b. failure to allocate enough memory... fail gracefully */
 405 #if VERBOSITY >= VERBOSITY_MESSAGE && 0
 406         fprintf(stderr,
 407                         "heap2.c: heap_allocate was unable to allocate 0x%lx bytes on the VM heap.\n",
 408                         length);
 409 #endif
 410
 411 #if VERBOSITY >= VERBOSITY_TRACE
 412         fprintf(stderr, "heap_allocate: returning NULL\n");
 413 #endif
 414
 415         return NULL;
 416
 417         intsRestore();
 418 }
 419
 420 void
 421 heap_addreference (void **reflocation)
 422 {
 423         /* I currently use a separate linked list (as in the original code) to hold
 424            the global reference locations, but I'll change this to allocate these
 425            in blocks on the heap; we'll have to add JIT-Marker code for those Java
 426            objects then. -- phil. */
 427
 428         heap_add_address_to_address_list(&references, reflocation);
 429 }
 430
 431 static
 432 __inline__
 433 void gc_finalize (void)
 434 {
 435         /* This will have to be slightly rewritten as soon the JIT-marked heap-based lists are used. -- phil. */
 436
 437         address_list_node*  curr = finalizers;
 438         address_list_node*  prev;
 439
 440 //      fprintf(stderr, "finalizing\n");
 441
 442 #if 0
 443         while (curr) {
 444                 if (!bitmap_testbit(mark_bits, curr->address)) {
 445                         /* I need a way to save derefs. Any suggestions? -- phil. */
 446                         asm_calljavamethod(((java_objectheader*)curr->address)->vftbl->class->finalizer,
 447                                                            curr->address, NULL, NULL, NULL);
 448
 449                         prev->next = curr->next;
 450                         free(curr);
 451                 } else {
 452                         prev = curr;
 453                         curr = curr->next;
 454                 }
 455         }
 456 #else
 457         while (curr) {
 458                 if (curr->address) {
 459                         if (!bitmap_testbit(mark_bits, curr->address)) {
 460
 461 #ifdef FINALIZER_COUNTING
 462                                 ++gc_finalizers_executed;
 463 #endif
 464                                 asm_calljavamethod(((java_objectheader*)curr->address)->vftbl->class->finalizer,
 465                                                                    curr->address, NULL, NULL, NULL);
 466                                 curr->address = 0;
 467                         }
 468                 }
 469
 470                 curr = curr->next;
 471         }
 472 #endif
 473
 474 //      fprintf(stderr, "done\n");
 475 }
 476
 477
 478 __inline__
 479 static
 480 void gc_reclaim (void)
 481 {
 482         void* free_start;
 483         void* free_end = heap_base;
 484         BITBLOCK* temp_bits;
 485         bitmap_t* temp_bitmap;
 486
 487         /* 1. reset the freelists */
 488         allocator_reset();
 489
 490         /* 2. reclaim unmarked objects */
 491 #if 0 && SIZE_FROM_CLASSINFO
 492         free_start = bitmap_find_next_combination_set_unset(start_bitmap,
 493                                                                                                                 mark_bitmap,
 494                                                                                                                 free_end);
 495         while (free_start < heap_top) {
 496                 if (!bitmap_testbit(start_bits, free_start) ||
 497                         bitmap_testbit(mark_bits, free_start)) {
 498                         fprintf(stderr, "gc_reclaim: inconsistent bit info for 0x%lx\n", free_start);
 499                 }
 500
 501                 free_end = free_start;
 502                 while((free_end < heap_top) &&
 503                           (!bitmap_testbit(mark_bits, free_end)) {
 504                         free_end +=
 505                 }
 506
 507
 508
 509 bitmap_find_next_setbit(mark_bitmap, free_start + 8); /* FIXME: constant used */
 510
 511                         //                      fprintf(stderr, "%lx -- %lx\n", free_start, free_end);
 512
 513                         if (free_end < heap_top) {
 514                                 allocator_free(free_start, free_end - free_start);
 515
 516                                 //                              fprintf(stderr, "gc_reclaim: freed 0x%lx bytes at 0x%lx\n", free_end - free_start, free_start);
 517
 518 #if !defined(JIT_MARKER_SUPPORT)
 519                                 /* might make trouble with JIT-Marker support. The Marker for unused blocks
 520                                    might be called, leading to a bad dereference. -- phil. */
 521                                 bitmap_setbit(mark_bits, free_start);
 522 #endif
 523                         }
 524                 } else {
 525                         //                      fprintf(stderr, "hmmm... found freeable area of 0 bytes at heaptop ?!\n");
 526                         free_end = heap_top;
 527                 }
 528         }
 529 #else
 530         while (free_end < heap_top) {
 531                 free_start = bitmap_find_next_combination_set_unset(start_bitmap,
 532                                                                                                                         mark_bitmap,
 533                                                                                                                         free_end);
 534
 535                 if (!bitmap_testbit(start_bits, free_start) ||
 536                         bitmap_testbit(mark_bits, free_start))
 537                         fprintf(stderr, "gc_reclaim: inconsistent bit info for 0x%lx\n", free_start);
 538
 539                 if (free_start < heap_top) {
 540                         free_end   = bitmap_find_next_setbit(mark_bitmap, (void*)((long)free_start + 8)); /* FIXME: constant used */
 541
 542                         //                      fprintf(stderr, "%lx -- %lx\n", free_start, free_end);
 543
 544                         if (free_end < heap_top) {
 545                                 allocator_free(free_start, (long)free_end - (long)free_start);
 546
 547                                 //                              fprintf(stderr, "gc_reclaim: freed 0x%lx bytes at 0x%lx\n", free_end - free_start, free_start);
 548
 549 #if !defined(JIT_MARKER_SUPPORT)
 550                                 /* might make trouble with JIT-Marker support. The Marker for unused blocks
 551                                    might be called, leading to a bad dereference. -- phil. */
 552                                 bitmap_setbit(mark_bits, free_start);
 553 #endif
 554                         }
 555                 } else {
 556                         //                      fprintf(stderr, "hmmm... found freeable area of 0 bytes at heaptop ?!\n");
 557                         free_end = heap_top;
 558                 }
 559         }
 560 #endif
 561
 562         /* 3.1. swap mark & start bitmaps */
 563         temp_bits = mark_bits;
 564         mark_bits = start_bits;
 565         start_bits = temp_bits;
 566
 567         temp_bitmap = mark_bitmap;
 568         mark_bitmap = start_bitmap;
 569         start_bitmap = temp_bitmap;
 570
 571         /* 3.2. mask reference bitmap */
 572 #warning "bitmap masking unimplemented --- references will not be cleared"
 573
 574         /* 3.3. update heap_top */
 575         if (free_start < heap_top)
 576                 heap_top = free_start;
 577
 578         if (heap_top < heap_limit)
 579                 bitmap_setbit(start_bits, heap_top);
 580
 581         /* 4. adjust the collection threshold */
 582         heap_next_collection = (void*)((long)heap_top + ((long)heap_limit - (long)heap_top) / 8);
 583         if (heap_next_collection > heap_limit)
 584                 heap_next_collection = heap_limit;
 585
 586 #if VERBOSITY >= VERBOSITY_PARANOIA && 0
 587         fprintf(stderr, "gc_reclaim: reporting heap state variables:\n");
 588         fprintf(stderr, "\theap top              0x%lx\n", heap_top);
 589         fprintf(stderr, "\theap size             0x%lx (%ld)\n", heap_size, heap_size);
 590         fprintf(stderr, "\theap_limit            0x%lx\n", heap_limit);
 591         fprintf(stderr, "\theap next collection  0x%lx\n", heap_next_collection);
 592
 593         allocator_dump();
 594 #endif
 595 }
 596
 597 __inline__
 598 static
 599 void
 600 gc_mark_object_at (void** addr)
 601 {
 602         /*
 603          * A note concerning the order of the tests:
 604          *
 605          * Statistics collected during a test run, where alignment
 606          * was tested before checking whether the addr points into
 607          * the heap:
 608          * >> LOG: 9301464 bytes for 196724 objects allocated.
 609          * >> LOG: 15 garbage collections performed.
 610          * >> LOG: 6568440 heapblocks visited, 469249 objects marked
 611          * >> LOG:     1064447 visits to objects already marked.
 612          * >> LOG:     988270 potential references not aligned.
 613          * >> LOG:     4049446 out of heap.
 614          * >> LOG:     5236 not an object.
 615          *
 616          * These results show, that only about 1/4 of all heapblocks
 617          * point to objects; The single most important reason why a
 618          * heapblock can not point at an object is, that it's value
 619          * doesn't fall within the heap area (this test was performed
 620          * with a 3MB heap).
 621          *
 622          * From the results, the various tests have to be conducted
 623          * in the following order for maximum efficiency:
 624          *    1. addr in heap?
 625          *    2. already marked ?
 626          *    3. aligned ?
 627          *    4. object ?
 628          *
 629          * The results after reordering:
 630          * >> LOG: 6568440 heapblocks visited, 469249 objects marked
 631          * >> LOG:     1064447 visits to objects already marked.
 632          * >> LOG:     350 potential references not aligned.
 633          * >> LOG:     5037366 out of heap.
 634          * >> LOG:     5236 not an object.
 635          *
 636          * And using:
 637          *    1. addr in heap?
 638          *    2. already marked ?
 639          *    3. object ?
 640          *    4. aligned ?
 641          *
 642          * >> LOG: 6568440 heapblocks visited, 469249 objects marked
 643          * >> LOG:     5037366 out of heap.
 644          * >> LOG:     1064456 visits to objects already marked.
 645          * >> LOG:     5539 not an object.
 646          * >> LOG:     38 potential references not aligned.
 647          *
 648          * Apparently, most unaligned values will already be eliminated
 649          * when checking against the bounds of the heap. Checking this
 650          * property first, should thus improve collection times.
 651          */
 652
 653
 654 #ifdef GC_COLLECT_STATISTICS
 655         if (!((void*)addr >= heap_base && (void*)addr < heap_top)) {
 656                 ++gc_mark_not_inheap;
 657                 return;
 658         }
 659
 660         if (bitmap_testbit(mark_bits, (void*)addr)) {
 661                 ++gc_mark_already_marked;
 662                 return;
 663         }
 664
 665         if (!bitmap_testbit(start_bits, (void*)addr)) {
 666                 ++gc_mark_not_object;
 667                 return;
 668         }
 669
 670         if ((long)addr & ((1 << ALIGN) - 1)) {
 671                 ++gc_mark_not_aligned;
 672                 return;
 673         }
 674
 675 #endif
 676
 677 #if 0
 678         //      fprintf(stderr, "gc_mark_object_at: called for address 0x%lx\n", addr);
 679
 680         if ((long)addr & ((1 << ALIGN) - 1)) {
 681                 fprintf(stderr, "non aligned pointer\n");
 682                 return;
 683         }
 684
 685         if (!((void*)addr >= heap_base && (void*)addr < heap_top)) {
 686                 fprintf(stderr, "not an address on the heap.\n");
 687                 return;
 688         }
 689
 690         if (!bitmap_testbit(start_bits, (void*)addr)) {
 691                 fprintf(stderr, "not an object.\n");
 692                 return;
 693         }
 694
 695         if (bitmap_testbit(mark_bits, (void*)addr)) {
 696                 fprintf(stderr, "already marked.\n");
 697                 return;
 698         }
 699 #endif
 700
 701         /* 1. is the addr aligned, on the heap && the start of an object */
 702         if (!((long)addr & ((1 << ALIGN) - 1)) &&
 703                 (void*)addr >= heap_base &&
 704                 (void*)addr < heap_top &&
 705                 bitmap_testbit(start_bits, (void*)addr) &&
 706                 !bitmap_testbit(mark_bits, (void*)addr)) {
 707                 bitmap_setbit(mark_bits, (void*)addr);
 708
 709 #ifdef GC_COLLECT_STATISTICS
 710                 ++gc_mark_objects_marked;
 711 #endif
 712
 713                 //              fprintf(stderr, "gc_mark_object_at: called for address 0x%lx: ", addr);
 714                 //              fprintf(stderr, "marking object.\n");
 715
 716 #ifdef JIT_MARKER_SUPPORT
 717                 /* 1.a. invoke the JIT-marker method */
 718                 asm_calljavamethod(addr->vftbl->class->marker, addr, NULL, NULL, NULL);
 719 #else
 720                 /* 1.b. mark the references contained */
 721                 if (bitmap_testbit(reference_bits, addr)) {
 722                         void** end;
 723 #ifdef SIZE_FROM_CLASSINFO
 724                         void** old_end;
 725
 726                         if (((java_objectheader*)addr)->vftbl == class_array->vftbl) {
 727                                 end = (void**)((long)addr + (long)((java_arrayheader*)addr)->alignedsize);
 728 //                              fprintf(stderr, "size found for array at 0x%lx: 0x%lx\n", addr, ((java_arrayheader*)addr)->alignedsize);
 729                         }
 730                         else {
 731                                 end = (void**)((long)addr + (long)((java_objectheader*)addr)->vftbl->class->alignedsize);
 732 //                              fprintf(stderr, "size found for 0x%lx: 0x%lx\n", addr, ((java_objectheader*)addr)->vftbl->class->alignedsize);
 733                         }
 734
 735                         old_end = (void**)bitmap_find_next_setbit(start_bitmap, (void*)addr + 8);
 736                         if (end != old_end) {
 737                                 fprintf(stderr, "inconsistent object length for object at 0x%lx:", addr);
 738                                 fprintf(stderr, " old = 0x%lx ; new = 0x%lx\n", old_end, end);
 739                         }
 740 #else
 741                         end = (void**)bitmap_find_next_setbit(start_bitmap, addr + 8); /* points just behind the object */
 742 #endif
 743
 744 #ifdef GC_COLLECT_STATISTICS
 745                 gc_mark_heapblocks_visited += ((long)end - (long)addr) >> ALIGN;
 746 #endif
 747
 748                         while (addr < end)
 749                                 gc_mark_object_at(*(addr++));
 750                 }
 751 #endif
 752         }
 753
 754         return;
 755 }
 756
 757
 758 __inline__
 759 static
 760 void gc_mark_references (void)
 761 {
 762         address_list_node* curr = references;
 763
 764         //      fprintf(stderr, "gc_mark_references\n");
 765
 766         while (curr) {
 767                 gc_mark_object_at(*((void**)(curr->address)));
 768                 curr = curr->next;
 769         }
 770 }
 771
 772 __inline__
 773 static
 774 void
 775 markreferences(void** start, void** end)
 776 {
 777         while (start < end)
 778                 gc_mark_object_at(*(start++));
 779 }
 780
 781 __inline__
 782 static
 783 void gc_mark_stack (void)
 784 {
 785         void *dummy;
 786
 787 #ifdef USE_THREADS
 788     thread *aThread;
 789
 790         if (currentThread == NULL) {
 791                 void **top_of_stack = &dummy;
 792
 793                 if (top_of_stack > stackbottom)
 794                         markreferences(stackbottom, top_of_stack);
 795                 else
 796                         markreferences(top_of_stack, stackbottom);
 797         }
 798         else {
 799                 for (aThread = liveThreads; aThread != 0;
 800                          aThread = CONTEXT(aThread).nextlive) {
 801                         mark_object_at((void*)aThread);
 802                         if (aThread == currentThread) {
 803                                 void **top_of_stack = &dummy;
 804
 805                                 if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
 806                                         markreferences((void**)CONTEXT(aThread).stackEnd, top_of_stack);
 807                                 else
 808                                         markreferences(top_of_stack, (void**)CONTEXT(aThread).stackEnd);
 809                         }
 810                         else {
 811                                 if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
 812                                         markreferences((void**)CONTEXT(aThread).stackEnd,
 813                                                                    (void**)CONTEXT(aThread).usedStackTop);
 814                                 else
 815                                         markreferences((void**)CONTEXT(aThread).usedStackTop,
 816                                                                    (void**)CONTEXT(aThread).stackEnd);
 817                         }
 818             }
 819
 820                 markreferences((void**)&threadQhead[0],
 821                                            (void**)&threadQhead[MAX_THREAD_PRIO]);
 822         }
 823 #else
 824     void **top_of_stack = &dummy;
 825
 826         //      fprintf(stderr, "gc_mark_stack\n");
 827
 828     if (top_of_stack > stackbottom) {
 829                 //              fprintf(stderr, "stack growing upward\n");
 830         markreferences(stackbottom, top_of_stack);
 831         } else {
 832                 //              fprintf(stderr, "stack growing downward\n");
 833         markreferences(top_of_stack, stackbottom);
 834         }
 835 #endif
 836 }
 837
 838
 839 static
 840 void gc_run (void)
 841 {
 842         static int armageddon_is_near = 0;
 843
 844         if (armageddon_is_near) {
 845                 /* armageddon_is_here! */
 846                 fprintf(stderr, "Oops, seems like there's a slight problem here: gc_run() called while still running?!\n");
 847                 return;
 848         }
 849
 850         armageddon_is_near = true;
 851         heap_next_collection = heap_limit;  /* try to avoid finalizer-induced collections */
 852
 853         bitmap_clear(mark_bitmap);
 854
 855         asm_dumpregistersandcall(gc_mark_stack);
 856         gc_mark_references();
 857         gc_finalize();
 858         gc_reclaim();
 859
 860         armageddon_is_near = false;
 861
 862 #ifdef GC_COLLECT_STATISTICS
 863         ++gc_collections_count;
 864 #endif
 865 }
 866
 867
 868 /************************* Function: gc_init **********************************
 869
 870   Initializes anything that must be initialized to call the gc on the right
 871   stack.
 872
 873 ******************************************************************************/
 874
 875 void
 876 gc_init (void)
 877 {
 878 }
 879
 880 /************************** Function: gc_call ********************************
 881
 882   Calls the garbage collector. The garbage collector should always be called
 883   using this function since it ensures that enough stack space is available.
 884
 885 ******************************************************************************/
 886
 887 void
 888 gc_call (void)
 889 {
 890 #ifdef USE_THREADS
 891         assert(blockInts == 0);
 892
 893         intsDisable();
 894         if (currentThread == NULL || currentThread == mainThread)
 895                 gc_run();
 896         else
 897                 asm_switchstackandcall(CONTEXT(mainThread).usedStackTop, gc_run);
 898         intsRestore();
 899 #else
 900         gc_run();
 901 #endif
 902 }
 903
 904
 905
 906 /*
 907  * These are local overrides for various environment variables in Emacs.
 908  * Please do not remove this and leave it at the end of the file, where
 909  * Emacs will automagically detect them.
 910  * ---------------------------------------------------------------------
 911  * Local variables:
 912  * mode: c
 913  * indent-tabs-mode: t
 914  * c-basic-offset: 4
 915  * tab-width: 4
 916  * End:
 917  */