From 2d9dac2a8bed3c8561138c9c9691deb8c627b405 Mon Sep 17 00:00:00 2001 From: phil Date: Mon, 9 Nov 1998 23:06:11 +0000 Subject: [PATCH] finally under version control! --- mm/Makefile | 4 +- mm/heap2.c | 657 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 659 insertions(+), 2 deletions(-) create mode 100644 mm/heap2.c diff --git a/mm/Makefile b/mm/Makefile index 28fbd07b3..4909cca92 100644 --- a/mm/Makefile +++ b/mm/Makefile @@ -1,12 +1,12 @@ # cacao/mm/Makefile -# $Id: Makefile 47 1998-11-09 13:44:47Z phil $ +# $Id: Makefile 51 1998-11-09 23:06:11Z phil $ AR = ar COMBINE = $(AR) rcs mm.o mm.o: actualtarget Makefile -actualtarget: old +actualtarget: gc2 clean: rm -rf *.o *~ diff --git a/mm/heap2.c b/mm/heap2.c new file mode 100644 index 000000000..85bfc9d0b --- /dev/null +++ b/mm/heap2.c @@ -0,0 +1,657 @@ +#include +#include /* getpagesize, mmap, ... */ +#include +#ifndef MAP_FAILED +#define MAP_FAILED ((void*) -1) +#endif +#include +#include +#include "../asmpart.h" +#include "../callargs.h" +#include "../threads/thread.h" +#include "../threads/locks.h" +#include + +#include "mm.h" + +#define PAGESIZE_MINUS_ONE (getpagesize() - 1) + +#undef ALIGN +#undef OFFSET + +#define false 0 +#define true 1 + +#include "allocator.h" /* rev. 1 allocator */ +#include "bitmap2.h" /* rev. 2 bitmap management */ + +bool collectverbose; + +void gc_call (void); + +/* --- macros */ + +#define align_size(size) ((size) & ~((1 << ALIGN) - 1)) +#define MAP_ADDRESS (void*) 0x10000000 + +#define VERBOSITY_MESSAGE 1 +#define VERBOSITY_DEBUG 2 +#define VERBOSITY_MISTRUST 3 +#define VERBOSITY_TRACE 4 +#define VERBOSITY_PARANOIA 5 +#define VERBOSITY_LIFESPAN 6 + +//#define VERBOSITY VERBOSITY_MESSAGE +//#define VERBOSITY VERBOSITY_PARANOIA +#define VERBOSITY VERBOSITY_LIFESPAN + +/* --- file-wide variables */ + +static void* heap_base = NULL; +static SIZE heap_size = 0; +static void* heap_top = NULL; +static void* heap_limit = NULL; +static void* heap_next_collection = NULL; + +static bitmap_t* start_bitmap = NULL; +static BITBLOCK* start_bits = NULL; +static bitmap_t* reference_bitmap = NULL; +static BITBLOCK* reference_bits = NULL; +static bitmap_t* mark_bitmap = NULL; +static BITBLOCK* mark_bits = NULL; + +static void** stackbottom = NULL; + +typedef struct address_list_node { + void* address; + struct address_list_node* next; +} address_list_node; + +static address_list_node* references = NULL; +static address_list_node* finalizers = NULL; + +/* --- implementation */ + +void +heap_init (SIZE size, + SIZE startsize, /* when should we collect for the first time ? */ + void **in_stackbottom) +{ +#if VERBOSITY == VERBOSITY_MESSAGE + fprintf(stderr, "The heap is verbose.\n"); +#elif VERBOSITY == VERBOSITY_DEBUG + fprintf(stderr, "The heap is in debug mode.\n"); +#elif VERBOSITY == VERBOSITY_MISTRUST + fprintf(stderr, "The heap is mistrusting us.\n"); +#elif VERBOSITY == VERBOSITY_TRACE + fprintf(stderr, "The heap is outputting trace information.\n"); +#elif VERBOSITY == VERBOSITY_PARANOIA + fprintf(stderr, "The heap is paranoid.\n"); +#elif VERBOSITY == VERBOSITY_LIFESPAN + fprintf(stderr, "The heap is collecting lifespan information.\n"); +#endif + + /* 1. Initialise the freelists & reset the allocator's state */ + allocator_init(); + + /* 2. Allocate at least (alignment!) size bytes of memory for the heap */ + heap_size = align_size(size + ((1 << ALIGN) - 1)); + +#if 1 + /* For now, we'll try to map in the stack at a fixed address... + ...this will change soon. -- phil. */ + heap_base = (void*) mmap (MAP_ADDRESS, + ((size_t)heap_size + PAGESIZE_MINUS_ONE) & ~PAGESIZE_MINUS_ONE, + PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, + -1, + (off_t) 0); +#else + heap_base = malloc(heap_size); +#endif + + if (heap_base == MAP_FAILED) { + /* unable to allocate the requested amount of memory */ + fprintf(stderr, "The queen, mylord, is dead!\n"); + exit(-1); + } + + /* 3. Allocate the bitmaps */ + start_bitmap = bitmap_allocate(heap_base, heap_size); + reference_bitmap = bitmap_allocate(heap_base, heap_size); + mark_bitmap = bitmap_allocate(heap_base, heap_size); + + start_bits = start_bitmap->bitmap; + reference_bits = reference_bitmap->bitmap; + mark_bits = mark_bitmap->bitmap; + + /* 4. Mark the first free-area as an object-start */ + bitmap_setbit(start_bits, heap_base); + + /* 5. Initialise the heap's state (heap_top, etc.) */ + stackbottom = in_stackbottom; /* copy the stackbottom */ + + heap_top = heap_base; /* the current end of the heap (just behind the last allocated object) */ + heap_limit = heap_base + heap_size; /* points just behind the last accessible block of the heap */ + + /* 6. calculate a useful first collection limit */ + /* This is extremly primitive at this point... + we should replace it with something more useful -- phil. */ + heap_next_collection = heap_base + (heap_size / 8); + + /* 7. Init the global reference lists & finalizer addresses */ + references = NULL; + finalizers = NULL; +} + +void +heap_close (void) +{ + /* 1. Clean up on the heap... finalize all remaining objects */ +#if 0 + address_list_node* curr = finalizers; + while (curr) { + address_list_node* prev = curr; + + if (bitmap_testbit(start_bits, curr->address)) + asm_calljavamethod(((java_objectheader*)(curr->address))->vftbl->class->finalizer, curr->address, NULL, NULL, NULL); + + curr = curr->next; + free(prev); + } +#endif + + /* 2. Release the bitmaps */ + bitmap_release(start_bitmap); + bitmap_release(reference_bitmap); + bitmap_release(mark_bitmap); + + /* 3. Release the memory allocated to the heap */ + if (heap_base) + munmap(heap_base, heap_size); +} + +static +inline +void +heap_add_address_to_address_list(address_list_node** list, void* address) +{ + /* Note: address lists are kept sorted to simplify finalization */ + + address_list_node* new_node = malloc(sizeof(address_list_node)); + new_node->address = address; + new_node->next = NULL; + + while (*list && (*list)->next) { +#if VERBOSITY >= VERBOSITY_PARANOIA + if ((*list)->address == address) + fprintf(stderr, + "Attempt to add a duplicate adress to an adress list.\n"); +#endif + + if ((*list)->next->address < address) + list = &(*list)->next; + else { + new_node->next = *list; + *list = new_node; + return; + } + } + + new_node->next = *list; + *list = new_node; +} + +static +inline +void +heap_add_finalizer_for_object_at(void* addr) +{ + /* Finalizers seem to be very rare... for this reason, I keep a linked + list of object addresses, which have a finalizer attached. This list + is kept in ascending order according to the order garbage is freed. + This list is currently kept separate from the heap, but should be + moved onto it, but some JIT-marker code to handle these special + objects will need to be added first. -- phil. */ + + heap_add_address_to_address_list(&finalizers, addr); +} + +void* +heap_allocate (SIZE in_length, + bool references, + methodinfo *finalizer) +{ + SIZE length = align_size(in_length + ((1 << 3) - 1)); + void* free_chunk = NULL; + +#if VERBOSITY >= VERBOSITY_MISTRUST && 0 + /* check for misaligned in_length parameter */ + if (length != in_length) + fprintf(stderr, + "heap2.c: heap_allocate was passed unaligned in_length parameter: %ld, \n aligned to %ld. (mistrust)\n", + in_length, length); +#endif + + // fprintf(stderr, "heap_allocate: 0x%lx (%ld) requested, 0x%lx (%ld) aligned\n", in_length, in_length, length, length); + + if (finalizer) + fprintf(stderr, "finalizer detected\n"); + +#if VERBOSITY >= VERBOSITY_LIFESPAN + /* perform garbage collection to collect data for lifespan analysis */ + if (heap_top > heap_base) + gc_call(); +#endif + + intsDisable(); + + retry: + /* 1. attempt to get a free block with size >= length from the freelists */ + free_chunk = allocator_alloc(length); + + /* 2. if unsuccessful, try alternative allocation strategies */ + if (!free_chunk) { + /* 2.a if the collection threshold would be exceeded, collect the heap */ + if (heap_top + length > heap_next_collection) { + /* 2.a.1. collect if the next_collection threshold would be exceeded */ + gc_call(); + + /* 2.a.2. we just ran a collection, recheck the freelists */ + free_chunk = allocator_alloc(length); + if (free_chunk) + goto success; + + /* 2.a.3. we can't satisfy the request from the freelists, check + against the heap_limit whether growing the heap is possible */ + if (heap_top + length > heap_limit) + goto failure; + } + + /* 2.b. grow the heap */ + free_chunk = heap_top; + heap_top += length; + } + + success: + /* 3.a. mark all necessary bits, store the finalizer & return the newly allocate block */ +#if 0 + /* I don't mark the object-start anymore, as it always is at the beginning of a free-block, + which already is marked (Note: The first free-block gets marked in heap_init). -- phil. */ + bitmap_setbit(start_bits, free_chunk); /* mark the new object */ +#endif + bitmap_setbit(start_bits, free_chunk + length); /* mark the freespace behind the new object */ + if (references) + bitmap_setbit(reference_bits, free_chunk); + else + bitmap_clearbit(reference_bits, free_chunk); + +#if 1 + /* store a hint, that there's a finalizer */ + if (finalizer) + heap_add_finalizer_for_object_at(free_chunk); +#else +# warning "finalizers disabled." +#endif + +#if VERBOSITY >= VERBOSITY_TRACE + fprintf(stderr, "heap_allocate: returning free block of 0x%lx bytes at 0x%lx\n", length, free_chunk); +#endif +#if VERBOSITY >= VERBOSITY_PARANOIA && 0 + fprintf(stderr, "heap_allocate: reporting heap state variables:\n"); + fprintf(stderr, "\theap top 0x%lx\n", heap_top); + fprintf(stderr, "\theap size 0x%lx (%ld)\n", heap_size, heap_size); + fprintf(stderr, "\theap_limit 0x%lx\n", heap_limit); + fprintf(stderr, "\theap next collection 0x%lx\n", heap_next_collection); +#endif + + return free_chunk; + + failure: + /* 3.b. failure to allocate enough memory... fail gracefully */ +#if VERBOSITY >= VERBOSITY_MESSAGE + fprintf(stderr, + "heap2.c: heap_allocate was unable to allocate 0x%lx bytes on the VM heap.\n", + length); +#endif + +#if VERBOSITY >= VERBOSITY_TRACE + fprintf(stderr, "heap_allocate: returning NULL\n"); +#endif + + return NULL; + + intsRestore(); +} + +void +heap_addreference (void **reflocation) +{ + /* I currently use a separate linked list (as in the original code) to hold + the global reference locations, but I'll change this to allocate these + in blocks on the heap; we'll have to add JIT-Marker code for those Java + objects then. -- phil. */ + + heap_add_address_to_address_list(&references, reflocation); +} + +static +inline +void gc_finalize (void) +{ + /* This will have to be slightly rewritten as soon the JIT-marked heap-based lists are used. -- phil. */ + + address_list_node* curr = finalizers; + address_list_node* prev; + +#if 0 + while (curr) { + if (!bitmap_testbit(mark_bits, curr->address)) { + /* I need a way to save derefs. Any suggestions? -- phil. */ + asm_calljavamethod(((java_objectheader*)curr->address)->vftbl->class->finalizer, + curr->address, NULL, NULL, NULL); + + prev->next = curr->next; + free(curr); + } else { + prev = curr; + curr = curr->next; + } + } +#else + while (curr) { + if (curr->address) { + if (!bitmap_testbit(mark_bits, curr->address)) { + fprintf(stderr, "executing finalizer\n"); + asm_calljavamethod(((java_objectheader*)curr->address)->vftbl->class->finalizer, + curr->address, NULL, NULL, NULL); + curr->address = 0; + } + } + + curr = curr->next; + } +#endif +} + +static +inline +void gc_reclaim (void) +{ + void* free_start; + void* free_end = heap_base; + BITBLOCK* temp_bits; + bitmap_t* temp_bitmap; + + /* 1. reset the freelists */ + allocator_reset(); + + /* 2. reclaim unmarked objects */ + while (free_end < heap_top) { + free_start = bitmap_find_next_combination_set_unset(start_bitmap, + mark_bitmap, + free_end); + + if (!bitmap_testbit(start_bits, free_start)) + fprintf(stderr, "gc_reclaim: inconsistent bit info for 0x%lx\n", free_start); + + if (free_start < heap_top) { + free_end = bitmap_find_next_setbit(mark_bitmap, free_start + 8); /* FIXME: constant used */ + + // fprintf(stderr, "%lx -- %lx\n", free_start, free_end); + + if (free_end < heap_top) { + allocator_free(free_start, free_end - free_start); + + // fprintf(stderr, "gc_reclaim: freed 0x%lx bytes at 0x%lx\n", free_end - free_start, free_start); + +#if !defined(JIT_MARKER_SUPPORT) + /* might make trouble with JIT-Marker support. The Marker for unused blocks + might be called, leading to a bad dereference. -- phil. */ + bitmap_setbit(mark_bits, free_start); +#endif + } + } else { + // fprintf(stderr, "hmmm... found freeable area of 0 bytes at heaptop ?!\n"); + free_end = heap_top; + } + } + + /* 3.1. swap mark & start bitmaps */ + temp_bits = mark_bits; + mark_bits = start_bits; + start_bits = temp_bits; + + temp_bitmap = mark_bitmap; + mark_bitmap = start_bitmap; + start_bitmap = temp_bitmap; + + /* 3.2. mask reference bitmap */ +#warning "bitmap masking unimplemented --- references will not be cleared" + + /* 3.3. update heap_top */ + if (free_start < heap_top) + heap_top = free_start; + + if (heap_top < heap_limit) + bitmap_setbit(start_bits, heap_top); + + /* 4. adjust the collection threshold */ + heap_next_collection = heap_top + (heap_limit - heap_top) / 8; + if (heap_next_collection > heap_limit) + heap_next_collection = heap_limit; + +#if VERBOSITY >= VERBOSITY_PARANOIA && 0 + fprintf(stderr, "gc_reclaim: reporting heap state variables:\n"); + fprintf(stderr, "\theap top 0x%lx\n", heap_top); + fprintf(stderr, "\theap size 0x%lx (%ld)\n", heap_size, heap_size); + fprintf(stderr, "\theap_limit 0x%lx\n", heap_limit); + fprintf(stderr, "\theap next collection 0x%lx\n", heap_next_collection); + + allocator_dump(); +#endif +} + +static +inline +void +gc_mark_object_at (void** addr) +{ + // fprintf(stderr, "gc_mark_object_at: called for address 0x%lx\n", addr); + + if (!((void*)addr >= heap_base && + (void*)addr < heap_top)) { + // fprintf(stderr, "not an address on the heap.\n"); + } else { + if (!bitmap_testbit(start_bits, (void*)addr)) { + // fprintf(stderr, "not an object.\n"); + } + else { + if (bitmap_testbit(mark_bits, (void*)addr)) { + // fprintf(stderr, "gc_mark_object_at: called for address 0x%lx: ", addr); + // fprintf(stderr, "already marked.\n"); + } + } + } + + /* 1. is the addr in the heap && the start of an object */ + if ((void*)addr >= heap_base && + (void*)addr < heap_top && + bitmap_testbit(start_bits, (void*)addr) && + !bitmap_testbit(mark_bits, (void*)addr)) { + bitmap_setbit(mark_bits, (void*)addr); + + // fprintf(stderr, "gc_mark_object_at: called for address 0x%lx: ", addr); + // fprintf(stderr, "marking object.\n"); + +#if JIT_MARKER_SUPPORT + /* 1.a. invoke the JIT-marker method */ + asm_calljavamethod(addr->vftbl->class->marker, addr, NULL, NULL, NULL); +#else + /* 1.b. mark the references contained */ + if (bitmap_testbit(reference_bits, addr)) { + void** end = (void**)bitmap_find_next_setbit(start_bitmap, addr + 8); /* points just behind the object */ + while (addr < end) + gc_mark_object_at(*(addr++)); + } +#endif + } + + return; +} + +static +inline +void gc_mark_references (void) +{ + address_list_node* curr = references; + + // fprintf(stderr, "gc_mark_references\n"); + + while (curr) { + gc_mark_object_at(*((void**)(curr->address))); + curr = curr->next; + } +} + +static +inline +void +markreferences(void** start, void** end) +{ + while (start < end) + gc_mark_object_at(*(start++)); +} + +static +inline +void gc_mark_stack (void) +{ + void *dummy; + +#ifdef USE_THREADS + thread *aThread; + + if (currentThread == NULL) { + void **top_of_stack = &dummy; + + if (top_of_stack > stackbottom) + markreferences(stackbottom, top_of_stack); + else + markreferences(top_of_stack, stackbottom); + } + else { + for (aThread = liveThreads; aThread != 0; + aThread = CONTEXT(aThread).nextlive) { + mark_object_at((void*)aThread); + if (aThread == currentThread) { + void **top_of_stack = &dummy; + + if (top_of_stack > (void**)CONTEXT(aThread).stackEnd) + markreferences((void**)CONTEXT(aThread).stackEnd, top_of_stack); + else + markreferences(top_of_stack, (void**)CONTEXT(aThread).stackEnd); + } + else { + if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd) + markreferences((void**)CONTEXT(aThread).stackEnd, + (void**)CONTEXT(aThread).usedStackTop); + else + markreferences((void**)CONTEXT(aThread).usedStackTop, + (void**)CONTEXT(aThread).stackEnd); + } + } + + markreferences((void**)&threadQhead[0], + (void**)&threadQhead[MAX_THREAD_PRIO]); + } +#else + void **top_of_stack = &dummy; + + // fprintf(stderr, "gc_mark_stack\n"); + + if (top_of_stack > stackbottom) { + // fprintf(stderr, "stack growing upward\n"); + markreferences(stackbottom, top_of_stack); + } else { + // fprintf(stderr, "stack growing downward\n"); + markreferences(top_of_stack, stackbottom); + } +#endif +} + + +static +void gc_run (void) +{ + static int armageddon_is_near = 0; + + if (armageddon_is_near) { + fprintf(stderr, "Oops, seems like there's a slight problem here: gc_run() called while still running?!\n"); + return; + } + + armageddon_is_near = true; + heap_next_collection = heap_limit; /* try to avoid finalizer-induced collections */ + + bitmap_clear(mark_bitmap); + + asm_dumpregistersandcall(gc_mark_stack); + gc_mark_references(); + gc_finalize(); + gc_reclaim(); + + armageddon_is_near = false; +} + + +/************************* Function: gc_init ********************************** + + Initializes anything that must be initialized to call the gc on the right + stack. + +******************************************************************************/ + +void +gc_init (void) +{ +} + +/************************** Function: gc_call ******************************** + + Calls the garbage collector. The garbage collector should always be called + using this function since it ensures that enough stack space is available. + +******************************************************************************/ + +void +gc_call (void) +{ +#ifdef USE_THREADS + assert(blockInts == 0); + + intsDisable(); + if (currentThread == NULL || currentThread == mainThread) + gc_run(); + else + asm_switchstackandcall(CONTEXT(mainThread).usedStackTop, gc_run); + intsRestore(); +#else + gc_run(); +#endif +} + + + +/* + * These are local overrides for various environment variables in Emacs. + * Please do not remove this and leave it at the end of the file, where + * Emacs will automagically detect them. + * --------------------------------------------------------------------- + * Local variables: + * mode: c + * indent-tabs-mode: t + * c-basic-offset: 4 + * tab-width: 4 + * End: + */ -- 2.25.1