1 /* This file is part of NIT ( http://www.nitlanguage.org ).
3 * Copyright 2009 Julien Chevalier <chevjulien@gmail.com>
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
18 # define assert(x) while(0)
21 #include "gc_static_objects_list.h"
23 /** The current active heap.
24 * During GC collect, it is the destination (i.e. the next active heap). */
25 char *gc_heap_pointer
;
27 /** The inactive heap.
28 * During GC collect, is is the source (i.e. the previous active heap). */
29 char *gc_old_heap_pointer
;
31 /** The size (total capacity) of the active heap. */
34 /** The total size of currently allocated objects. */
37 /** Typedef used by boxing val. FIXME: Do someting better! */
38 typedef struct TBOX_struct
{
39 const classtable_elt_t
*vft
;
44 /** First free position in the active heap. */
45 char *gc_allocation_pointer
;
47 /** Position of objects copied but not yet visited (during GC collect). */
48 char *gc_scavenging_pointer
;
50 /** List of global objects. */
51 GC_List staticObjects
;
53 /** Size of a memory page. Used to grow or shrink the GC heap. */
54 unsigned long page_size
;
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)
61 void Nit_gc_init(void) {
62 page_size
= sysconf(_SC_PAGESIZE
);
64 gc_heap_pointer
= calloc(1, page_size
);
65 if (gc_heap_pointer
==NULL
) exit(1);
66 gc_heap_size
= page_size
;
69 gc_allocation_pointer
= gc_heap_pointer
;
71 gc_old_heap_pointer
= NULL
;
72 gc_scavenging_pointer
= NULL
;
74 GC_List_Init(&staticObjects
);
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
) {
82 Nit_NativeArray array
;
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
));
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
);
98 objectSize
= (bigint
)((object
)[0].vft
[1].i
);
99 size
= (objectSize
) * sizeof(val_t
);
101 memcpy(gc_allocation_pointer
, object
, size
);
102 (object
)[0].vft
= (classtable_elt_t
*)gc_allocation_pointer
;
104 gc_allocation_pointer
+= size
;
110 /** Process the next evacuated object to copy/update its fields. */
111 static void GC_scavenging(void) {
115 val_t referencedObject
;
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
);
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
);
140 gc_scavenging_pointer
+= size
;
143 /** Collect live objects in the old head and copy them to the active heap. */
144 static void GC_collect(void) {
148 struct stack_frame_t
*frame
= stack_frame_head
;
149 GC_static_object
*staticObject
= staticObjects
.top
;
152 gc_allocation_pointer
= gc_heap_pointer
;
153 gc_scavenging_pointer
= gc_heap_pointer
;
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
);
161 staticObject
= staticObject
->next
;
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
);
172 if (frame
== frame
->prev
) break;
175 while (gc_allocation_pointer
!= gc_scavenging_pointer
) {
179 gc_scavenging_pointer
= NULL
;
181 gc_used_size
= gc_allocation_pointer
- gc_heap_pointer
;
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
;
189 gc_heap_pointer
= calloc(1, size
);
190 if (gc_heap_pointer
== NULL
) {
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
);
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
);
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
) {
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;
217 /* Build a new heap. */
218 GC_prepare_heap_size(try_size
);
223 /* Free the old heap. */
224 free(gc_old_heap_pointer
);
225 gc_old_heap_pointer
= NULL
;
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();*/
233 void *Nit_gc_malloc(size_t size
) {
236 if (size
> (gc_heap_size
- gc_used_size
))
237 GC_enlarge_and_collect(size
);
239 result
= gc_allocation_pointer
;
240 gc_allocation_pointer
+= size
;
241 gc_used_size
+= size
;
246 void GC_add_static_object(val_t
*pointer
) {
247 GC_List_Push(&staticObjects
, pointer
);