Commit | Line | Data |
---|---|---|
e1f2bf99 MD |
1 | /* Copyright (C) 1998 Free Software Foundation, Inc. |
2 | * | |
3 | * This program is free software; you can redistribute it and/or modify | |
4 | * it under the terms of the GNU General Public License as published by | |
5 | * the Free Software Foundation; either version 2, or (at your option) | |
6 | * any later version. | |
7 | * | |
8 | * This program is distributed in the hope that it will be useful, | |
9 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
11 | * GNU General Public License for more details. | |
12 | * | |
13 | * You should have received a copy of the GNU General Public License | |
14 | * along with this software; see the file COPYING. If not, write to | |
15 | * the Free Software Foundation, Inc., 59 Temple Place, Suite 330, | |
16 | * Boston, MA 02111-1307 USA | |
17 | * | |
18 | * As a special exception, the Free Software Foundation gives permission | |
19 | * for additional uses of the text contained in its release of GUILE. | |
20 | * | |
21 | * The exception is that, if you link the GUILE library with other files | |
22 | * to produce an executable, this does not by itself cause the | |
23 | * resulting executable to be covered by the GNU General Public License. | |
24 | * Your use of that executable is in no way restricted on account of | |
25 | * linking the GUILE library code into it. | |
26 | * | |
27 | * This exception does not however invalidate any other reasons why | |
28 | * the executable file might be covered by the GNU General Public License. | |
29 | * | |
30 | * This exception applies only to the code released by the | |
31 | * Free Software Foundation under the name GUILE. If you copy | |
32 | * code from other Free Software Foundation releases into a copy of | |
33 | * GUILE, as the General Public License permits, the exception does | |
34 | * not apply to the code that you add in this way. To avoid misleading | |
35 | * anyone as to the status of such modified files, you must delete | |
36 | * this exception notice from them. | |
37 | * | |
38 | * If you write modifications of your own for GUILE, it is your choice | |
39 | * whether to permit this exception to apply to your modifications. | |
40 | * If you do not wish that, delete this exception notice. */ | |
41 | \f | |
42 | ||
43 | /* This is an implementation of guardians as described in | |
44 | * R. Kent Dybvig, Carl Bruggeman, and David Eby (1993) "Guardians in | |
45 | * a Generation-Based Garbage Collector" ACM SIGPLAN Conference on | |
46 | * Programming Language Design and Implementation, June 1993 | |
47 | * ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/guardians.ps.gz | |
48 | * | |
49 | * Author: Michael N. Livshin | |
50 | * Modified by: Mikael Djurfeldt | |
51 | */ | |
52 | ||
53 | #include <stdio.h> | |
54 | #include <assert.h> | |
55 | ||
56 | #include "_scm.h" | |
57 | #include "print.h" | |
58 | #include "smob.h" | |
56366edf | 59 | #include "genio.h" |
e1f2bf99 MD |
60 | |
61 | #include "guardians.h" | |
62 | ||
63 | static long scm_tc16_guardian; | |
64 | ||
65 | /* The live and zombies FIFOs are implemented as tconcs as described | |
66 | in Dybvig's paper. This decouples addition and removal of elements | |
67 | so that no synchronization between these needs to take place. | |
68 | */ | |
69 | #define TCONC_IN(tc, obj, pair) \ | |
70 | { \ | |
71 | SCM_SETCAR ((tc).tail, obj); \ | |
72 | SCM_SETCAR (pair, SCM_BOOL_F); \ | |
73 | SCM_SETCDR (pair, SCM_BOOL_F); \ | |
74 | SCM_SETCDR ((tc).tail, pair); \ | |
75 | (tc).tail = pair; \ | |
76 | } \ | |
77 | ||
78 | #define TCONC_OUT(tc, res) \ | |
79 | { \ | |
80 | (res) = SCM_CAR ((tc).head); \ | |
81 | (tc).head = SCM_CDR ((tc).head); \ | |
82 | } \ | |
83 | ||
84 | #define TCONC_EMPTYP(tc) ((tc).head == (tc).tail) | |
85 | ||
86 | typedef struct tconc_t | |
87 | { | |
88 | SCM head; | |
89 | SCM tail; | |
90 | } tconc_t; | |
91 | ||
92 | typedef struct guardian_t | |
93 | { | |
94 | tconc_t live; | |
95 | tconc_t zombies; | |
01a119ac | 96 | struct guardian_t *next; |
e1f2bf99 MD |
97 | } guardian_t; |
98 | ||
99 | #define GUARDIAN(x) ((guardian_t *) SCM_CDR (x)) | |
100 | #define GUARDIAN_LIVE(x) (GUARDIAN (x)->live) | |
101 | #define GUARDIAN_ZOMBIES(x) (GUARDIAN (x)->zombies) | |
01a119ac | 102 | #define GUARDIAN_NEXT(x) (GUARDIAN (x)->next) |
e1f2bf99 | 103 | |
01a119ac JB |
104 | static guardian_t *first_live_guardian = NULL; |
105 | static guardian_t **current_link_field = NULL; | |
e1f2bf99 MD |
106 | |
107 | static SCM | |
108 | g_mark (SCM ptr) | |
109 | { | |
01a119ac JB |
110 | *current_link_field = GUARDIAN (ptr); |
111 | current_link_field = &GUARDIAN_NEXT (ptr); | |
112 | GUARDIAN_NEXT (ptr) = NULL; | |
113 | ||
e1f2bf99 MD |
114 | /* Can't mark zombies here since they can refer to objects which are |
115 | living dead, thereby preventing them to join the zombies. */ | |
116 | return SCM_BOOL_F; | |
117 | } | |
118 | ||
119 | static scm_sizet | |
120 | g_free (SCM ptr) | |
121 | { | |
122 | scm_must_free ((char *) GUARDIAN (ptr)); | |
123 | return sizeof (guardian_t); | |
124 | } | |
125 | ||
126 | static int | |
127 | g_print (SCM exp, SCM port, scm_print_state *pstate) | |
128 | { | |
129 | char buf[256]; | |
130 | sprintf (buf, "#<guardian live objs: %lu zombies: %lu>", | |
131 | scm_ilength (SCM_CDR (GUARDIAN_LIVE (exp).head)), | |
132 | scm_ilength (SCM_CDR (GUARDIAN_ZOMBIES (exp).head))); | |
133 | scm_puts (buf, port); | |
134 | ||
135 | return 1; | |
136 | } | |
137 | ||
138 | static scm_smobfuns g_smob = { | |
139 | g_mark, | |
140 | g_free, | |
141 | g_print, | |
142 | 0 /* g_equalp */ | |
143 | }; | |
144 | ||
145 | #define CCLO_G(cclo) (SCM_VELTS (cclo)[1]) | |
146 | ||
147 | static SCM | |
148 | guard (SCM cclo, SCM arg) | |
149 | { | |
150 | if (!SCM_UNBNDP (arg)) | |
151 | { | |
152 | scm_guard (cclo, arg); | |
153 | return SCM_UNSPECIFIED; | |
154 | } | |
155 | else | |
156 | return scm_get_one_zombie (cclo); | |
157 | } | |
158 | ||
159 | static SCM guard1; | |
160 | ||
161 | SCM_PROC (s_make_guardian, "make-guardian", 0, 0, 0, scm_make_guardian); | |
162 | SCM | |
163 | scm_make_guardian () | |
164 | { | |
165 | SCM cclo = scm_makcclo (guard1, 2L); | |
166 | guardian_t *g = (guardian_t *) scm_must_malloc (sizeof (guardian_t), | |
167 | s_make_guardian); | |
168 | SCM z1 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); | |
169 | SCM z2 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); | |
170 | SCM z; | |
171 | SCM_NEWCELL (z); | |
172 | ||
173 | SCM_DEFER_INTS; | |
174 | /* A tconc starts out with one tail pair. */ | |
175 | g->live.head = g->live.tail = z1; | |
176 | g->zombies.head = g->zombies.tail = z2; | |
177 | SCM_SETCDR (z, g); | |
178 | SCM_SETCAR (z, scm_tc16_guardian); | |
179 | SCM_ALLOW_INTS; | |
180 | ||
181 | CCLO_G (cclo) = z; | |
182 | ||
183 | return cclo; | |
184 | } | |
185 | ||
186 | void | |
187 | scm_guardian_gc_init() | |
188 | { | |
01a119ac JB |
189 | current_link_field = &first_live_guardian; |
190 | first_live_guardian = NULL; | |
e1f2bf99 MD |
191 | } |
192 | ||
193 | void | |
194 | scm_guardian_zombify () | |
195 | { | |
01a119ac JB |
196 | guardian_t *g; |
197 | for (g = first_live_guardian; g; g = g->next) | |
e1f2bf99 | 198 | { |
e1f2bf99 MD |
199 | /* Loop through the live list and |
200 | 1. move unmarked objects to the zombies tconc | |
201 | 2. mark the live tconc. | |
202 | */ | |
01a119ac | 203 | SCM tconc_tail = g->live.tail; |
e1f2bf99 | 204 | SCM prev_pair = SCM_BOOL_F; |
01a119ac | 205 | SCM pair = g->live.head; |
e1f2bf99 MD |
206 | while (pair != tconc_tail) |
207 | { | |
208 | SCM next_pair = SCM_CDR (pair); | |
209 | ||
210 | if (SCM_NMARKEDP (SCM_CAR (pair))) | |
211 | { | |
212 | /* got you, zombie! */ | |
213 | ||
214 | /* out of the live list! */ | |
215 | if (SCM_FALSEP (prev_pair)) | |
01a119ac | 216 | g->live.head = next_pair; |
e1f2bf99 MD |
217 | else |
218 | /* mark previous pair */ | |
219 | SCM_SETCDR (prev_pair, next_pair | 1); | |
220 | ||
221 | /* to the zombie list! */ | |
01a119ac | 222 | TCONC_IN (g->zombies, SCM_CAR (pair), pair); |
e1f2bf99 MD |
223 | } |
224 | else | |
225 | { | |
226 | if (SCM_NFALSEP (prev_pair)) | |
227 | /* mark previous pair */ | |
228 | SCM_SETCDR (prev_pair, pair | 1); | |
229 | prev_pair = pair; | |
230 | } | |
231 | ||
232 | pair = next_pair; | |
233 | } | |
234 | if (SCM_NFALSEP (prev_pair)) | |
235 | /* mark previous pair */ | |
236 | SCM_SETCDR (prev_pair, pair | 1); | |
237 | /* mark live list tail */ | |
238 | SCM_SETOR_CDR (tconc_tail, 1); | |
239 | ||
01a119ac | 240 | scm_gc_mark (g->zombies.head); |
e1f2bf99 MD |
241 | } |
242 | } | |
243 | ||
244 | void | |
245 | scm_guard (SCM guardian, SCM obj) | |
246 | { | |
247 | SCM g = CCLO_G (guardian); | |
248 | ||
249 | if (SCM_NIMP (obj)) | |
250 | { | |
251 | SCM z; | |
252 | ||
253 | SCM_NEWCELL (z); | |
254 | ||
255 | /* This critical section barrier will be replaced by a mutex. */ | |
256 | SCM_DEFER_INTS; | |
257 | TCONC_IN (GUARDIAN_LIVE (g), obj, z); | |
258 | SCM_ALLOW_INTS; | |
259 | } | |
260 | } | |
261 | ||
262 | SCM | |
263 | scm_get_one_zombie (SCM guardian) | |
264 | { | |
265 | SCM g = CCLO_G (guardian); | |
266 | SCM res = SCM_BOOL_F; | |
267 | ||
268 | /* This critical section barrier will be replaced by a mutex. */ | |
269 | SCM_DEFER_INTS; | |
270 | if (!TCONC_EMPTYP (GUARDIAN_ZOMBIES (g))) | |
271 | TCONC_OUT (GUARDIAN_ZOMBIES (g), res); | |
272 | SCM_ALLOW_INTS; | |
273 | ||
274 | return res; | |
275 | } | |
276 | ||
277 | void | |
278 | scm_init_guardian() | |
279 | { | |
280 | scm_tc16_guardian = scm_newsmob (&g_smob); | |
e1f2bf99 MD |
281 | guard1 = scm_make_subr_opt ("guardian", scm_tc7_subr_2o, guard, 0); |
282 | ||
283 | #include "guardians.x" | |
284 | } |