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