1 /*
2 * Part of Scheme 48 1.9. See file COPYING for notices and license.
3 *
4 * Authors: David Frese
5 */
6
7 /* Remembered Sets */
8
9 #include <stdlib.h>
10
11 #include "scheme48.h"
12
13 #include "remset.h"
14 #include "memory.h"
15 #include "utils.h"
16 #include "data.h"
17 #include "generation_gc.h"
18 #include "memory_map.h"
19 #include "gc_config.h"
20
21 #if (S48_USE_REMEMBERED_SETS)
22
23 static int s48_remset_member(s48_address ip, RemSet* remset);
24
25 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
26 /* Construction of a Rem_ip */
allocate_Rem_ip()27 static Rem_ip* allocate_Rem_ip(){
28 Rem_ip* rem_ip = (Rem_ip*)calloc(1,sizeof(Rem_ip));
29 if (!rem_ip){
30 s48_gc_error("allocate_Rem_ip: out of memory");
31 }
32 return rem_ip;
33 }
34
initialize_Rem_ip(Rem_ip * rem_ip)35 static void initialize_Rem_ip(Rem_ip* rem_ip){
36 rem_ip->ip = 0;
37 rem_ip->next_ip = 0;
38 }
39
make_Rem_ip()40 static Rem_ip* make_Rem_ip(){
41 Rem_ip* rem_ip = (Rem_ip*)allocate_Rem_ip();
42 initialize_Rem_ip(rem_ip);
43 return rem_ip;
44 }
45 #endif
46
47
48 /* Construction of a Rem_set */
allocate_RemSet()49 static RemSet* allocate_RemSet(){
50 RemSet* remset = (RemSet*)calloc(1, (sizeof(RemSet)));
51 if (!remset){
52 s48_gc_error("allocate_RemSet: out of memory");
53 }
54 return remset;
55 }
56
initialize_RemSet(RemSet * remset)57 static void initialize_RemSet(RemSet* remset){
58 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
59 Rem_ip* el = (Rem_ip*)make_Rem_ip();
60 remset->first_el = el;
61 remset->last_el = el;
62 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
63 remset->free_index = 0;
64 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
65 remset->free_index = 0;
66 remset->next_remset = NULL;
67 #endif
68 }
69
s48_make_remset()70 RemSet* s48_make_remset(){
71 RemSet* remset = allocate_RemSet();
72 initialize_RemSet(remset);
73 return remset;
74 }
75
s48_remset_size(RemSet * remset)76 int s48_remset_size(RemSet* remset){
77 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
78 Rem_ip* next = remset->first_el;
79 Rem_ip* empty = remset->last_el;
80 int size = 0;
81
82 while(next != empty){
83 size++;
84 next = next->next_ip;
85 }
86 return size;
87 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
88 return remset->free_index;
89 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
90 int size=0;
91 while(remset != NULL){
92 size += remset->free_index;
93 remset = remset->next_remset;
94 }
95 return size;
96 #endif
97 }
98
99
100 /* Adds an IP to a RS and returns a boolean */
s48_remset_add(s48_address ip,RemSet * remset)101 int s48_remset_add(s48_address ip, RemSet* remset){
102 #if S48_UNIQUE_REMEMBERED_SET==TRUE /* no duplicates */
103 if (s48_remset_member(ip, remset))
104 return TRUE;
105 #endif
106 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
107 {
108 Rem_ip* last = remset->last_el;
109 Rem_ip* new_el = make_Rem_ip();
110
111 last->ip = ip;
112 last->next_ip = new_el;
113 remset->last_el = new_el;
114 return TRUE;
115 }
116 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
117 if (remset->free_index == S48_REMEMBERED_SET_SIZE){
118 return FALSE;
119 }
120 else{
121 remset->elements[remset->free_index] = ip;
122 remset->free_index++;
123 return TRUE;
124 }
125 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
126 /* search or create a free remset */
127 while (remset->free_index == S48_REMEMBERED_SET_SIZE){
128 if (remset->next_remset == NULL)
129 remset->next_remset= s48_make_remset();
130 remset = remset->next_remset;
131 }
132
133 remset->elements[remset->free_index] = ip;
134 remset->free_index++;
135 return TRUE;
136 #endif /* S48_REMEMBERED_SET_TYPE */
137 }
138
139
s48_remset_member(s48_address ip,RemSet * remset)140 static int s48_remset_member(s48_address ip, RemSet* remset){
141 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
142 Rem_ip* next = remset->first_el;
143 Rem_ip* empty = remset->last_el;
144
145 /* if both pointers point to the same rem_ip -> not a member */
146 while(next != empty){
147 if ((s48_address)next->ip == ip){
148 return TRUE;
149 }
150 next = next->next_ip;
151 }
152 return FALSE;
153 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
154 int i;
155 for (i = 0; i < remset->free_index; i++){
156 if (remset->elements[i] == ip)
157 return TRUE;
158 }
159
160 return FALSE;
161 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
162 int i;
163 while (remset != NULL){
164 for (i = 0; i < remset->free_index; i++){
165 if (remset->elements[i] == ip)
166 return TRUE;
167 }
168 remset = remset->next_remset;
169 }
170 return FALSE;
171 #endif /* S48_REMEMBERED_SET_TYPE */
172 }
173
call_trace_locationsB(s48_address addr)174 static inline void call_trace_locationsB(s48_address addr) {
175 Area* area = (Area*)s48_memory_map_ref(addr);
176 /* we only want to trace locations, that are not currently
177 collected. This test should be sufficient */
178 if (area->action == GC_ACTION_IGNORE)
179 s48_internal_trace_locationsB(area, TRUE, addr, S48_ADDRESS_INC(addr), "call_trace_locationsB");
180 }
181
s48_trace_remset(RemSet * remset)182 void s48_trace_remset(RemSet* remset){
183 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
184 Rem_ip* next = remset->first_el;
185 Rem_ip* empty = remset->last_el;
186
187 /* if both pointers point to the same rem_ip -> done*/
188 while(next != empty){
189 call_trace_locationsB(next->ip);
190 next = next->next_ip;
191 }
192 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
193 int i;
194 for (i = 0; i < remset->free_index; i++)
195 call_trace_locationsB(remset->elements[i]);
196
197 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
198 int i;
199 while (remset != NULL){
200 for (i = 0; i < remset->free_index; i++)
201 call_trace_locationsB(remset->elements[i]);
202
203 remset = remset->next_remset;
204 }
205 #endif
206 }
207
s48_free_remset(RemSet * remset)208 void s48_free_remset(RemSet* remset){
209 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
210 Rem_ip* next_ip;
211 Rem_ip* rem_ip = remset->first_el;
212 while(rem_ip != NULL){
213 next_ip = rem_ip->next_ip;
214 free(rem_ip);
215 rem_ip = next_ip;
216 }
217 free(remset);
218 #elif S48_REMEMBERED_SET_TYPE==S48_STATIC_REMEMBERED_SETS
219 free(remset);
220 #elif S48_REMEMBERED_SET_TYPE==S48_EXTENSIBLE_REMEMBERED_SETS
221 RemSet* next_remset;
222 while(remset != NULL){
223 next_remset = remset->next_remset;
224 free(remset);
225 remset = next_remset;
226 }
227 #endif
228 }
229
s48_check_remset(RemSet * remset)230 void s48_check_remset(RemSet* remset) {
231 /* only implemented for dynamic remsets, for now */
232 #if S48_REMEMBERED_SET_TYPE==S48_DYNAMIC_REMEMBERED_SETS
233 Rem_ip* next = remset->first_el;
234 Rem_ip* empty = remset->last_el;
235
236 while(next != empty) {
237 Area* a = (Area*)s48_memory_map_ref(next->ip);
238 if ((a == NULL) || (next->ip >= a->frontier)) {
239 s48_gc_error("remembered-set currupted! Location 0x%X outside the heap.",
240 next->ip);
241 }
242 next = next->next_ip;
243 }
244 #endif
245 }
246
247 #endif
248