c_src/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         BOX_struct box;
  84
  85         assert(ISOBJ(object) && !ISNULL(object));
  86         if (GET_MARKBIT(object) != (bigint)0) {
  87                 /* Object already evacuated. So forward it. */
  88                 newAdress = REMOVE_MARKBIT((bigint)((object)->vft));
  89         } else {
  90                 newAdress = (val_t)gc_allocation_pointer;
  91                 if (OBJ_IS_ARRAY(object)) {
  92                         array = (Nit_NativeArray)object;
  93                         size = sizeof(struct Nit_NativeArray) + ((array->size - 1) * sizeof(val_t));
  94                 } else if (OBJ_IS_BOX(object)) {
  95                         box = (BOX_struct)object;
  96                         size = sizeof(struct TBOX_struct);
  97                 } else {
  98                         objectSize = (bigint)((object)[0].vft[1].i);
  99                         size = (objectSize) * sizeof(val_t);
 100                 }
 101                 memcpy(gc_allocation_pointer, object, size);
 102                 (object)[0].vft = (classtable_elt_t*)gc_allocation_pointer;
 103                 SET_MARKBIT(object);
 104                 gc_allocation_pointer += size;
 105         }
 106
 107         return newAdress;
 108 }
 109
 110 /** Process the next evacuated object to copy/update its fields. */
 111 static void GC_scavenging(void) {
 112         obj_t object;
 113         int size;
 114         int i;
 115         val_t referencedObject;
 116
 117         object = (obj_t)gc_scavenging_pointer;
 118         if (OBJ_IS_BOX(object)) {
 119                 size = sizeof(struct TBOX_struct);
 120         } else if (OBJ_IS_ARRAY(object)) {
 121                 Nit_NativeArray array = (Nit_NativeArray)gc_scavenging_pointer;
 122                 size = sizeof(struct Nit_NativeArray) + ((array->size - 1) * sizeof(val_t));
 123                 for (i = 0; i < array->size; i++) {
 124                         referencedObject = array->val[i];
 125                         if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) {
 126                                 array->val[i] = GC_evacuation((obj_t)referencedObject);
 127                         }
 128                 }
 129         } else {
 130                 bigint objectSize = (bigint)((object)->vft[1].i);
 131                 size = (objectSize) * sizeof(val_t);
 132                 for (i = 2; i < objectSize; i++) {
 133                         referencedObject = object[i].objectSize;
 134                         if (!ISNULL(referencedObject) && ISOBJ(referencedObject)) {
 135                                 object[i].objectSize = GC_evacuation((obj_t)referencedObject);
 136                         }
 137                 }
 138         }
 139
 140         gc_scavenging_pointer += size;
 141 }
 142
 143 /** Collect live objects in the old head and copy them to the active heap. */
 144 static void GC_collect(void) {
 145         val_t *pointer;
 146         int i;
 147         int j;
 148         struct stack_frame_t *frame = stack_frame_head;
 149         GC_static_object *staticObject = staticObjects.top;
 150         val_t object;
 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 function frames (local variables) */
 165         while (frame != NULL) {
 166                 for (j = 0; j < frame->REG_size; j++) {
 167                         object = frame->REG[j];
 168                         if (!ISNULL(object) && ISOBJ(object)) {
 169                                 frame->REG[j] = GC_evacuation((obj_t)object);
 170                         }
 171                 }
 172                 if (frame == frame->prev) break;
 173                 frame = frame->prev;
 174         }
 175         while (gc_allocation_pointer != gc_scavenging_pointer) {
 176                 GC_scavenging();
 177         }
 178
 179         gc_scavenging_pointer = NULL;
 180
 181         gc_used_size = gc_allocation_pointer - gc_heap_pointer;
 182 }
 183
 184 /** Allocate a new active heap. */
 185 static void GC_prepare_heap_size(size_t size) {
 186         assert(gc_old_heap_pointer == NULL);
 187         gc_old_heap_pointer = gc_heap_pointer;
 188
 189         gc_heap_pointer = calloc(1, size);
 190         if (gc_heap_pointer == NULL) {
 191                 exit(1);
 192         }
 193         gc_heap_size = size;
 194 }
 195
 196 void Nit_gc_print_usage(void) {
 197 #if __STDC_VERSION >= 199901L
 198         /* If we are compiling with standard C99 or more recent, we can use %zu. */
 199         printf("GC: Size %zu usage %zu (%.2f%%)\n", gc_heap_size, gc_used_size, 100.0*gc_used_size/gc_heap_size);
 200 #else
 201         /* 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 !*/
 202         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);
 203 #endif
 204 }
 205
 206 /** Enlarge the heap and collect dead objects. Can also shrink the heap.
 207  * Size is the aditionnal number of bytes required. */
 208 static void GC_enlarge_and_collect(size_t size) {
 209         size_t try_size;
 210
 211         /* Heap grows exponentially. */
 212         try_size = gc_heap_size;
 213         while (size > (try_size - gc_used_size)) {
 214                 try_size = try_size * 1.5;
 215         }
 216
 217         /* Build a new heap. */
 218         GC_prepare_heap_size(try_size);
 219
 220         /* Collect. */
 221         GC_collect();
 222
 223         /* Free the old heap. */
 224         free(gc_old_heap_pointer);
 225         gc_old_heap_pointer = NULL;
 226
 227         /* Shrink heap. */
 228         while (gc_heap_size > 2*page_size && 3*(gc_used_size+size) < gc_heap_size)
 229                 gc_heap_size = gc_heap_size / 1.5;
 230         /*Nit_gc_print_usage();*/
 231 }
 232
 233 void *Nit_gc_malloc(size_t size) {
 234         char *result;
 235
 236         if (size > (gc_heap_size - gc_used_size))
 237                 GC_enlarge_and_collect(size);
 238
 239         result = gc_allocation_pointer;
 240         gc_allocation_pointer += size;
 241         gc_used_size += size;
 242
 243         return result;
 244 }
 245
 246 void GC_add_static_object(val_t *pointer) {
 247         GC_List_Push(&staticObjects, pointer);
 248 }
 249