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 *global_ref;
 150         struct nitni_ref_array_link *local_ref_array_link; /* for native interface */
 151
 152         gc_allocation_pointer = gc_heap_pointer;
 153         gc_scavenging_pointer = gc_heap_pointer;
 154
 155         /* Process global objects (registered by GC_add_static_object) */
 156         for (i = 0; i < staticObjects.size; i++) {
 157                 object = *(val_t*)(staticObject->pointer);
 158                 if (!ISNULL(object) && ISOBJ(object)) {
 159                         *(staticObject->pointer) = GC_evacuation((obj_t)object);
 160                 }
 161                 staticObject = staticObject->next;
 162         }
 163
 164         /* Process global reference to Nit objects from C code */
 165         global_ref = nitni_global_ref_list->head;
 166         while (global_ref != NULL) {
 167                 object = global_ref->val;
 168                 if (!ISNULL(object) && ISOBJ(object)) {
 169                         global_ref->val = GC_evacuation((obj_t)object);
 170                 }
 171                 global_ref = global_ref->next;
 172         }
 173
 174         /* Process function frames (local variables) */
 175         while (frame != NULL) {
 176                 for (j = 0; j < frame->REG_size; j++) {
 177                         object = frame->REG[j];
 178                         if (!ISNULL(object) && ISOBJ(object)) {
 179                                 frame->REG[j] = GC_evacuation((obj_t)object);
 180                         }
 181                 }
 182
 183                 /* Process C references to Nit objects */
 184                 local_ref_array_link = frame->nitni_local_ref_head;
 185                 while ( local_ref_array_link != NULL )
 186                 {
 187                         for (j = 0; j < local_ref_array_link->count; j++) {
 188                                 object = local_ref_array_link->reg[j]->val;
 189                                 if (!ISNULL(object) && ISOBJ(object)) {
 190                                         local_ref_array_link->reg[j]->val = GC_evacuation((obj_t)object);
 191                                 }
 192                         }
 193                         local_ref_array_link = local_ref_array_link->next;
 194                 }
 195
 196                 if (frame == frame->prev) break;
 197                 frame = frame->prev;
 198         }
 199         while (gc_allocation_pointer != gc_scavenging_pointer) {
 200                 GC_scavenging();
 201         }
 202
 203         gc_scavenging_pointer = NULL;
 204
 205         gc_used_size = gc_allocation_pointer - gc_heap_pointer;
 206 }
 207
 208 /** Allocate a new active heap. */
 209 static void GC_prepare_heap_size(size_t size) {
 210         assert(gc_old_heap_pointer == NULL);
 211         gc_old_heap_pointer = gc_heap_pointer;
 212
 213         gc_heap_pointer = calloc(1, size);
 214         if (gc_heap_pointer == NULL) {
 215                 exit(1);
 216         }
 217         gc_heap_size = size;
 218 }
 219
 220 void Nit_gc_print_usage(void) {
 221 #if __STDC_VERSION >= 199901L
 222         /* If we are compiling with standard C99 or more recent, we can use %zu. */
 223         printf("GC: Size %zu usage %zu (%.2f%%)\n", gc_heap_size, gc_used_size, 100.0*gc_used_size/gc_heap_size);
 224 #else
 225         /* 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 !*/
 226         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);
 227 #endif
 228 }
 229
 230 /** Enlarge the heap and collect dead objects. Can also shrink the heap.
 231  * Size is the aditionnal number of bytes required. */
 232 static void GC_enlarge_and_collect(size_t size) {
 233         size_t try_size;
 234
 235         /* Heap grows exponentially. */
 236         try_size = gc_heap_size;
 237         while (size > (try_size - gc_used_size)) {
 238                 try_size = try_size * 1.5;
 239         }
 240
 241         /* Build a new heap. */
 242         GC_prepare_heap_size(try_size);
 243
 244         /* Collect. */
 245         GC_collect();
 246
 247         /* Free the old heap. */
 248         free(gc_old_heap_pointer);
 249         gc_old_heap_pointer = NULL;
 250
 251         /* Shrink heap. */
 252         while (gc_heap_size > 2*page_size && 3*(gc_used_size+size) < gc_heap_size)
 253                 gc_heap_size = gc_heap_size / 1.5;
 254         /*Nit_gc_print_usage();*/
 255 }
 256
 257 void *Nit_gc_malloc(size_t size) {
 258         char *result;
 259
 260         if (size > (gc_heap_size - gc_used_size))
 261                 GC_enlarge_and_collect(size);
 262
 263         result = gc_allocation_pointer;
 264         gc_allocation_pointer += size;
 265         gc_used_size += size;
 266
 267         return result;
 268 }
 269
 270 void GC_add_static_object(val_t *pointer) {
 271         GC_List_Push(&staticObjects, pointer);
 272 }
 273
 274 /* Is invoked by intern method Sys:force_garbage_collection */
 275 void Nit_gc_force_garbage_collection( void ) {
 276         GC_enlarge_and_collect( 0 );
 277 }