clib/gc.c

   1 /* This file is part of NIT ( http://www.nitlanguage.org ).
   2  *
   3  * Copyright 2009 Julien Chevalier <chevjulien@gmail.com>
   4  *
   5  * This file is free software, which comes along with NIT.  This software is
   6  * distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
   7  * without  even  the implied warranty of  MERCHANTABILITY or  FITNESS FOR A
   8  * PARTICULAR PURPOSE.  You can modify it is you want,  provided this header
   9  * is kept unaltered, and a notification of the changes is added.
  10  * You  are  allowed  to  redistribute it and sell it, alone or is a part of
  11  * another product.
  12  */
  13
  14 #include "gc.h"
  15 #ifdef DEBUG
  16 #       include <assert.h>
  17 #else
  18 #       define assert(x) while(0)
  19 #endif
  20 #include <unistd.h>
  21 #include "gc_static_objects_list.h"
  22
  23 /** The current active heap.
  24  * During GC collect, it is the destination (i.e. the next active heap). */
  25 char *gc_heap_pointer;
  26
  27 /** The inactive heap.
  28  * During GC collect, is is the source (i.e. the previous active heap). */
  29 char *gc_old_heap_pointer;
  30
  31 /** The size (total capacity) of the active heap. */
  32 size_t gc_heap_size;
  33
  34 /** The total size of currently allocated objects. */
  35 size_t gc_used_size;
  36
  37 /** Typedef used by boxing val. FIXME: Do someting better! */
  38 typedef struct TBOX_struct {
  39         const classtable_elt_t *vft;
  40         char *val;
  41         bigint object_id;
  42 } *BOX_struct;
  43
  44 /** First free position in the active heap. */
  45 char *gc_allocation_pointer;
  46
  47 /** Position of objects copied but not yet visited (during GC collect). */
  48 char *gc_scavenging_pointer;
  49
  50 /** List of global objects. */
  51 GC_List staticObjects;
  52
  53 /** Size of a memory page. Used to grow or shrink the GC heap. */
  54 unsigned long page_size;
  55
  56 /* Markbit manipulations */
  57 #define GET_MARKBIT(x) (((val_t)((x)[0].vft)) & 1)
  58 #define SET_MARKBIT(x) ((x)->vft = (void*)(((bigint)((x)->vft)) | 1))
  59 #define REMOVE_MARKBIT(x) ((x) ^ 1)
  60
  61 void Nit_gc_init(void) {
  62         page_size = sysconf(_SC_PAGESIZE);
  63
  64         gc_heap_pointer = calloc(1, page_size);
  65         if (gc_heap_pointer==NULL) exit(1);
  66         gc_heap_size = page_size;
  67         gc_used_size = 0;
  68
  69         gc_allocation_pointer = gc_heap_pointer;
  70
  71         gc_old_heap_pointer = NULL;
  72         gc_scavenging_pointer = NULL;
  73
  74         GC_List_Init(&staticObjects);
  75 }
  76
  77 /** Copy object to the new heap if needed then return the address of the copy. */
  78 static val_t GC_evacuation(obj_t object) {
  79         bigint size;
  80         bigint objectSize;
  81         val_t newAdress;
  82         Nit_NativeArray array;
  83
  84         assert(ISOBJ(object) && !ISNULL(object));
  85         if (GET_MARKBIT(object) != (bigint)0) {
  86                 /* Object already evacuated. So forward it. */
  87                 newAdress = REMOVE_MARKBIT((bigint)((object)->vft));
  88         } else {
  89                 newAdress = (val_t)gc_allocation_pointer;
  90                 if (OBJ_IS_ARRAY(object)) {
  91                         array = (Nit_NativeArray)object;
  92                         size = sizeof(struct Nit_NativeArray) + ((array->size - 1) * sizeof(val_t));
  93                 } else if (OBJ_IS_BOX(object)) {
  94                         size = sizeof(struct TBOX_struct);
  95                 } else {
  96                         objectSize = (bigint)((object)[0].vft[1].i);
  97                         size = (objectSize) * sizeof(val_t);
  98                 }
  99                 memcpy(gc_allocation_pointer, object, size);
 100                 (object)[0].vft = (classtable_elt_t*)gc_allocation_pointer;
 101                 SET_MARKBIT(object);
 102                 gc_allocation_pointer += size;
 103         }
 104
 105         return newAdress;
 106 }
 107
 108 /** Process the next evacuated object to copy/update its fields. */
 109 static void GC_scavenging(void) {
 110         obj_t object;
 111         int size;
 112         int i;
 113         val_t referencedObject;
 114
 115         object = (obj_t)gc_scavenging_pointer;
 116         if (OBJ_IS_BOX(object)) {
 117                 size = sizeof(struct TBOX_struct);
 118         } else if (OBJ_IS_ARRAY(object)) {
 119                 Nit_NativeArray array = (Nit_NativeArray)gc_scavenging_pointer;
 120                 size = sizeof(struct Nit_NativeArray) + ((array->size - 1) * sizeof(val_t));
 121                 for (i = 0; i < array->size; i++) {
 122                         referencedObject = array->val[i];
 123                         if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) {
 124                                 array->val[i] = GC_evacuation((obj_t)referencedObject);
 125                         }
 126                 }
 127         } else {
 128                 bigint objectSize = (bigint)((object)->vft[1].i);
 129                 size = (objectSize) * sizeof(val_t);
 130                 for (i = 2; i < objectSize; i++) {
 131                         referencedObject = object[i].objectSize;
 132                         if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) {
 133                                 object[i].objectSize = GC_evacuation((obj_t)referencedObject);
 134                         }
 135                 }
 136         }
 137
 138         gc_scavenging_pointer += size;
 139 }
 140
 141 /** Collect live objects in the old head and copy them to the active heap. */
 142 static void GC_collect(void) {
 143         val_t *pointer;
 144         int i;
 145         int j;
 146         struct stack_frame_t *frame = stack_frame_head;
 147         GC_static_object *staticObject = staticObjects.top;
 148         val_t object;
 149         struct nitni_ref_array_link *local_ref_array_link; /* for native interface */
 150
 151         gc_allocation_pointer = gc_heap_pointer;
 152         gc_scavenging_pointer = gc_heap_pointer;
 153
 154         /* Process global objects (registered by GC_add_static_object) */
 155         for (i = 0; i < staticObjects.size; i++) {
 156                 object = *(val_t*)(staticObject->pointer);
 157                 if (!ISNULL(object) && ISOBJ(object)) {
 158                         *(staticObject->pointer) = GC_evacuation((obj_t)object);
 159                 }
 160                 staticObject = staticObject->next;
 161         }
 162
 163         /* Process function frames (local variables) */
 164         while (frame != NULL) {
 165                 for (j = 0; j < frame->REG_size; j++) {
 166                         object = frame->REG[j];
 167                         if (!ISNULL(object) && ISOBJ(object)) {
 168                                 frame->REG[j] = GC_evacuation((obj_t)object);
 169                         }
 170                 }
 171
 172                 /* Process C references to Nit objects */
 173                 local_ref_array_link = frame->nitni_local_ref_head;
 174                 while ( local_ref_array_link != NULL )
 175                 {
 176                         for (j = 0; j < local_ref_array_link->count; j++) {
 177                                 object = local_ref_array_link->reg[j]->val;
 178                                 if (!ISNULL(object) && ISOBJ(object)) {
 179                                         local_ref_array_link->reg[j]->val = GC_evacuation((obj_t)object);
 180                                 }
 181                         }
 182                         local_ref_array_link = local_ref_array_link->next;
 183                 }
 184
 185                 if (frame == frame->prev) break;
 186                 frame = frame->prev;
 187         }
 188         while (gc_allocation_pointer != gc_scavenging_pointer) {
 189                 GC_scavenging();
 190         }
 191
 192         gc_scavenging_pointer = NULL;
 193
 194         gc_used_size = gc_allocation_pointer - gc_heap_pointer;
 195 }
 196
 197 /** Allocate a new active heap. */
 198 static void GC_prepare_heap_size(size_t size) {
 199         assert(gc_old_heap_pointer == NULL);
 200         gc_old_heap_pointer = gc_heap_pointer;
 201
 202         gc_heap_pointer = calloc(1, size);
 203         if (gc_heap_pointer == NULL) {
 204                 exit(1);
 205         }
 206         gc_heap_size = size;
 207 }
 208
 209 void Nit_gc_print_usage(void) {
 210 #if __STDC_VERSION >= 199901L
 211         /* If we are compiling with standard C99 or more recent, we can use %zu. */
 212         printf("GC: Size %zu usage %zu (%.2f%%)\n", gc_heap_size, gc_used_size, 100.0*gc_used_size/gc_heap_size);
 213 #else
 214         /* We are not compiling with a standard that allows us to use %zu, let's cast the two unsigned integers into the biggest we can !*/
 215         printf("GC: Size %lu usage %lu (%.2f%%)\n", (unsigned long)gc_heap_size, (unsigned long)gc_used_size, 100.0*gc_used_size/gc_heap_size);
 216 #endif
 217 }
 218
 219 /** Enlarge the heap and collect dead objects. Can also shrink the heap.
 220  * Size is the aditionnal number of bytes required. */
 221 static void GC_enlarge_and_collect(size_t size) {
 222         size_t try_size;
 223
 224         /* Heap grows exponentially. */
 225         try_size = gc_heap_size;
 226         while (size > (try_size - gc_used_size)) {
 227                 try_size = try_size * 1.5;
 228         }
 229
 230         /* Build a new heap. */
 231         GC_prepare_heap_size(try_size);
 232
 233         /* Collect. */
 234         GC_collect();
 235
 236         /* Free the old heap. */
 237         free(gc_old_heap_pointer);
 238         gc_old_heap_pointer = NULL;
 239
 240         /* Shrink heap. */
 241         while (gc_heap_size > 2*page_size && 3*(gc_used_size+size) < gc_heap_size)
 242                 gc_heap_size = gc_heap_size / 1.5;
 243         /*Nit_gc_print_usage();*/
 244 }
 245
 246 void *Nit_gc_malloc(size_t size) {
 247         char *result;
 248
 249         if (size > (gc_heap_size - gc_used_size))
 250                 GC_enlarge_and_collect(size);
 251
 252         result = gc_allocation_pointer;
 253         gc_allocation_pointer += size;
 254         gc_used_size += size;
 255
 256         return result;
 257 }
 258
 259 void GC_add_static_object(val_t *pointer) {
 260         GC_List_Push(&staticObjects, pointer);
 261 }
 262
 263 /* Is invoked by intern method Sys:force_garbage_collection */
 264 void Nit_gc_force_garbage_collection( void ) {
 265         GC_enlarge_and_collect( 0 );
 266 }