From 4e6a13c22d7c384c3bebb45016338edd91cd45ea Mon Sep 17 00:00:00 2001 From: Julien Chevalier Date: Fri, 14 Aug 2009 14:11:04 -0400 Subject: [PATCH] gc: add Nit GC Signed-off-by: Julien Chevalier Signed-off-by: Jean Privat --- clib/gc.c | 199 +++++++++++++++++++++++++++++++++++++++++ clib/gc.h | 61 +++++++++++++ clib/gc_static_objects_list.c | 32 +++++++ clib/gc_static_objects_list.h | 35 ++++++++ clib/nit_main.c | 16 +++- src/compiling/compiling.nit | 2 + 6 files changed, 343 insertions(+), 2 deletions(-) create mode 100644 clib/gc.c create mode 100644 clib/gc.h create mode 100644 clib/gc_static_objects_list.c create mode 100644 clib/gc_static_objects_list.h diff --git a/clib/gc.c b/clib/gc.c new file mode 100644 index 0000000..5b72a6b --- /dev/null +++ b/clib/gc.c @@ -0,0 +1,199 @@ +/* This file is part of NIT ( http://www.nitlanguage.org ). + * + * Copyright 2009 Julien Chevalier + * + * This file is free software, which comes along with NIT. This software is + * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; + * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. You can modify it is you want, provided this header + * is kept unaltered, and a notification of the changes is added. + * You are allowed to redistribute it and sell it, alone or is a part of + * another product. + */ + +#include "gc.h" +#include + +void Nit_gc_init(){ + heapActive = malloc(sizeof(heap)); + heapInactive = malloc(sizeof(heap)); + + heapActive->heapPointer = malloc(HEAP_ACTIVE_SIZE_MIN); + heapInactive->heapPointer = malloc(HEAP_ACTIVE_SIZE_MIN); + + if (heapActive->heapPointer==NULL) exit(1); + if (heapInactive->heapPointer==NULL) exit(1); + + heapActive->size = HEAP_ACTIVE_SIZE_MIN; + heapInactive->size = HEAP_ACTIVE_SIZE_MIN; + + allocationPointer = heapActive->heapPointer; + + evacuationPointer = heapInactive->heapPointer; + scavengingPointer = evacuationPointer; + + GC_List_Init(&staticObjects); +} + +val_t GC_evacuation(obj_t object){ + bigint size; + bigint objectSize; + val_t newAdress; + Nit_NativeArray array; + BOX_struct box; + + assert(ISOBJ(object) && !ISNULL(object)); + if ( GET_MARKBIT(object) != (bigint)0) { + newAdress = REMOVE_MARKBIT((bigint)((object)->vft)); + }else{ + newAdress = (val_t)evacuationPointer; + if (OBJ_IS_ARRAY(object)) { + array = (Nit_NativeArray ) object; + size = sizeof(struct Nit_NativeArray) + ((array->size - 1) * sizeof(val_t)); + memcpy((void *)evacuationPointer, (array), size); + (array)->vft = (classtable_elt_t*)evacuationPointer; + }else if(IS_BOX(object)){ + box = (BOX_struct)object; + size = sizeof(struct TBOX_struct); + memcpy((void *)evacuationPointer, object, size); + box->vft = (classtable_elt_t*)evacuationPointer; + }else{ + objectSize = (bigint)((object)[0].vft[1].i); + size = (objectSize) * sizeof(val_t); + memcpy((void *)evacuationPointer, object, size); + (object)[0].vft = (classtable_elt_t*)evacuationPointer; + } + SET_MARKBIT(object); + evacuationPointer += size; + } + + return newAdress; +} + +void GC_scavenging(){ + obj_t object = (obj_t)scavengingPointer; + obj_t * object2 = (obj_t *)&scavengingPointer; + int size; + int i; + obj_t referencedObject; + bigint objectSize; + Nit_NativeArray * array; + + if ( IS_BOX(object)) { + size = sizeof(struct TBOX_struct); + }else{ + array = (Nit_NativeArray*)&scavengingPointer; + if (OBJ_IS_ARRAY((obj_t)*array)) { + size = sizeof(struct Nit_NativeArray) + (((*array)->size - 1) * sizeof(val_t)); + for (i = 0; i < (*array)->size; i++) { + referencedObject = (obj_t)((*array)->val[i]); + if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) { + (*array)->val[i] = (bigint)GC_evacuation(referencedObject); + } + } + }else{ + objectSize = (bigint)((object)->vft[1].i); + size = (objectSize) * sizeof(val_t); + for (i = 2; i < objectSize; i++) { + referencedObject = (obj_t)(object[i].objectSize); + if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) { + ((object)[i].objectSize) = (bigint)GC_evacuation(referencedObject); + } + } + } + } + scavengingPointer += size; +} + +void GC_collect(){ + val_t ** pointers; + val_t * pointer; + int i; + int j; + struct trace_t * frame = tracehead; + GC_static_object * staticObject = staticObjects.top; + val_t object; + heap * tempPointer; + + evacuationPointer = heapInactive->heapPointer; + scavengingPointer = heapInactive->heapPointer; + for (i = 0; i < staticObjects.size; i++) { + object = *(val_t*)(staticObject->pointer); + if(!ISNULL(object) && ISOBJ(object)){ + *(staticObject->pointer) = (val_t)GC_evacuation((obj_t)object); + } + staticObject = staticObject->next; + } + while (frame != NULL) { + pointers = frame->REG_pointer; + for (j = 0; j < frame->REG_size; j++) { + object = (val_t)(pointers[j]); + if(!ISNULL(object) && ISOBJ(object)){ + pointers[j] = (val_t*)GC_evacuation((obj_t)object); + } + } + if (frame == frame->prev) break; + frame = frame->prev; + } + while ( evacuationPointer != scavengingPointer) { + GC_scavenging(); + } + + /* pour tests seulement, pas necessaire */ + memset((void *)heapActive->heapPointer, 0, heapActive->size); + allocationPointer = evacuationPointer; + + /* inverse le tas actif et le tas inactif */ + tempPointer = heapActive; + heapActive = heapInactive; + heapInactive = tempPointer; + + heapActiveUsedSize = (int)allocationPointer - (int)heapActive->heapPointer; +} + +void GC_set_heap_size(size_t newHeapSize){ + free(heapInactive->heapPointer); + heapInactive->heapPointer = malloc(newHeapSize); + if(heapInactive->heapPointer == NULL) { + exit(1); + } + heapInactive->size = newHeapSize; + memset(heapInactive->heapPointer, 0, newHeapSize); +} + +void GC_detect_memory_needs( size_t size ) { + if ( size > (heapActive->size - heapActiveUsedSize)) { + GC_collect(); + if (heapActive->size - heapActiveUsedSize > heapActive->size / 2 && heapActive->size * 3 / 4 > HEAP_ACTIVE_SIZE_MIN){ + GC_set_heap_size(heapActive->size * 3 / 4); + GC_collect(); + GC_set_heap_size(heapActive->size); + } + } + if ( size > (heapActive->size - heapActiveUsedSize)) { + int try_size = heapInactive->size * 2; + while (size > (try_size - heapActiveUsedSize)){ + try_size *= 2; + } + GC_set_heap_size(try_size); + GC_collect(); + GC_set_heap_size(heapActive->size); + } +} + +void *Nit_gc_malloc( size_t size ) { + char *result; + + GC_detect_memory_needs(size); + + result = allocationPointer; + heapActiveUsedSize += size; + allocationPointer += size; + + return result; +} + +void GC_add_static_object(val_t * pointer){ + GC_List_Push(&staticObjects, pointer); +} + diff --git a/clib/gc.h b/clib/gc.h new file mode 100644 index 0000000..8dd4af2 --- /dev/null +++ b/clib/gc.h @@ -0,0 +1,61 @@ +/* This file is part of NIT ( http://www.nitlanguage.org ). + * + * Copyright 2009 Julien Chevalier + * + * This file is free software, which comes along with NIT. This software is + * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; + * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. You can modify it is you want, provided this header + * is kept unaltered, and a notification of the changes is added. + * You are allowed to redistribute it and sell it, alone or is a part of + * another product. + */ + +#ifndef GC +#define GC + +#include +#include +#include +#include "nit_common.h" +#include "gc_static_objects_list.h" + +/* Markbit manipulations */ +#define GET_MARKBIT(x) (((val_t)(x[0].vft)) & 1) +#define SET_MARKBIT(x) ((x)->vft = (void*)(((bigint)((x)->vft)) | 1)) +#define REMOVE_MARKBIT(x) (x ^ 1) + +#define HEAP_ACTIVE_SIZE_MIN 3000 + +typedef struct heap { + char *heapPointer; + unsigned long size; +}heap; + +typedef struct TBOX_struct { + const classtable_elt_t * vft; + char * val; + bigint object_id; +} * BOX_struct; + +heap* heapActive; +heap* heapInactive; +char *allocationPointer; +char *evacuationPointer; +char *scavengingPointer; + +unsigned long heapActiveUsedSize; + +GC_List staticObjects; + +void Nit_gc_init(); + +val_t GC_evacuation(obj_t object); + +void GC_scavenging(); + +void* Nit_gc_malloc( size_t size ); + +void GC_add_static_object(val_t * pointer); + +#endif diff --git a/clib/gc_static_objects_list.c b/clib/gc_static_objects_list.c new file mode 100644 index 0000000..662967a --- /dev/null +++ b/clib/gc_static_objects_list.c @@ -0,0 +1,32 @@ +/* This file is part of NIT ( http://www.nitlanguage.org ). + * + * Copyright 2009 Julien Chevalier + * + * This file is free software, which comes along with NIT. This software is + * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; + * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. You can modify it is you want, provided this header + * is kept unaltered, and a notification of the changes is added. + * You are allowed to redistribute it and sell it, alone or is a part of + * another product. + */ + +#include "gc_static_objects_list.h" + +void GC_List_Init (GC_List * list){ + list->top = NULL; + list->size = 0; +} + +int GC_List_Push (GC_List * list, val_t *pointer){ + GC_static_object *newElement; + if ((newElement = (GC_static_object *) malloc (sizeof (GC_static_object))) == NULL) + return -1; + + newElement->pointer = pointer; + newElement->next = list->top; + list->top = newElement; + list->size++; + return 0; +} + diff --git a/clib/gc_static_objects_list.h b/clib/gc_static_objects_list.h new file mode 100644 index 0000000..7f42f61 --- /dev/null +++ b/clib/gc_static_objects_list.h @@ -0,0 +1,35 @@ +/* This file is part of NIT ( http://www.nitlanguage.org ). + * + * Copyright 2009 Julien Chevalier + * + * This file is free software, which comes along with NIT. This software is + * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; + * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A + * PARTICULAR PURPOSE. You can modify it is you want, provided this header + * is kept unaltered, and a notification of the changes is added. + * You are allowed to redistribute it and sell it, alone or is a part of + * another product. + */ + +#ifndef GC_LIST +#define GC_LIST + +#include +#include +#include +#include "nit_common.h" + +typedef struct GC_static_object { + val_t * pointer; + struct GC_static_object *next; +}GC_static_object; + +typedef struct GC_List{ + GC_static_object *top; + int size; +}GC_List; + +void GC_List_Init (GC_List *list); +int GC_List_Push (GC_List *list, val_t *pointer); + +#endif diff --git a/clib/nit_main.c b/clib/nit_main.c index 6169787..5497708 100644 --- a/clib/nit_main.c +++ b/clib/nit_main.c @@ -14,9 +14,10 @@ #include "nit_common.h" #include #include +#include "gc.h" bigint object_id_counter = 1000000; -enum gc_option { large, boehm } gc_option; +enum gc_option { large, boehm, nitgc } gc_option; #ifdef WITH_LIBGC #define GC_DEBUG @@ -25,11 +26,18 @@ enum gc_option { large, boehm } gc_option; void *raw_alloc(size_t s0) { - return alloc(s0); + switch (gc_option) { + case nitgc: return malloc(s0); break; + default: return alloc(s0); + } } void register_static_object(val_t *o) { + switch (gc_option) { + case nitgc: GC_add_static_object(o); break; + default: break; + } return; } @@ -55,6 +63,7 @@ void * alloc(size_t s0) #ifdef WITH_LIBGC case boehm: return GC_MALLOC(s0); #endif + case nitgc: return Nit_gc_malloc(s0); case large: default: return large_alloc(s0); } @@ -85,6 +94,8 @@ void initialize_gc_option(void) { #else fprintf(stderr, "Compiled without Boehm GC support. Using default.\n"); #endif + } else if (strcmp(opt, "nitgc")==0) { + gc_option = nitgc; } else if (strcmp(opt, "large")==0) { gc_option = large; } else { @@ -97,6 +108,7 @@ void initialize_gc_option(void) { #ifdef WITH_LIBGC case boehm: GC_INIT(); break; #endif + case nitgc: Nit_gc_init(); break; default: break; /* Nothing */ } } diff --git a/src/compiling/compiling.nit b/src/compiling/compiling.nit index 0fa87b9..4f142fd 100644 --- a/src/compiling/compiling.nit +++ b/src/compiling/compiling.nit @@ -41,6 +41,8 @@ redef class MMModule var files = new Array[String] var includes = new ArraySet[String] files.add("$CLIBDIR/nit_main.c") + files.add("$CLIBDIR/gc.c") + files.add("$CLIBDIR/gc_static_objects_list.c") tc.info("Generating C code",1) for m in mhe.greaters_and_self do files.add("{tc.compdir}/{m.name}._sep.c") -- 1.7.9.5