Commit | Line | Data |
---|---|---|
67b2561b | 1 | /* Copyright (C) 1998, 1999 Free Software Foundation, Inc. |
e1f2bf99 MD |
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. */ | |
1bbd0b84 GB |
41 | |
42 | /* Software engineering face-lift by Greg J. Badros, 11-Dec-1999, | |
43 | gjb@cs.washington.edu, http://www.cs.washington.edu/homes/gjb */ | |
44 | ||
e1f2bf99 MD |
45 | \f |
46 | ||
47 | /* This is an implementation of guardians as described in | |
48 | * R. Kent Dybvig, Carl Bruggeman, and David Eby (1993) "Guardians in | |
49 | * a Generation-Based Garbage Collector" ACM SIGPLAN Conference on | |
50 | * Programming Language Design and Implementation, June 1993 | |
51 | * ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/guardians.ps.gz | |
52 | * | |
53 | * Author: Michael N. Livshin | |
54 | * Modified by: Mikael Djurfeldt | |
55 | */ | |
56 | ||
57 | #include <stdio.h> | |
58 | #include <assert.h> | |
59 | ||
60 | #include "_scm.h" | |
61 | #include "print.h" | |
62 | #include "smob.h" | |
56366edf | 63 | #include "genio.h" |
e1f2bf99 | 64 | |
1bbd0b84 | 65 | #include "scm_validate.h" |
e1f2bf99 MD |
66 | #include "guardians.h" |
67 | ||
68 | static long scm_tc16_guardian; | |
69 | ||
70 | /* The live and zombies FIFOs are implemented as tconcs as described | |
71 | in Dybvig's paper. This decouples addition and removal of elements | |
72 | so that no synchronization between these needs to take place. | |
73 | */ | |
74 | #define TCONC_IN(tc, obj, pair) \ | |
d3a6bc94 | 75 | do { \ |
e1f2bf99 MD |
76 | SCM_SETCAR ((tc).tail, obj); \ |
77 | SCM_SETCAR (pair, SCM_BOOL_F); \ | |
78 | SCM_SETCDR (pair, SCM_BOOL_F); \ | |
79 | SCM_SETCDR ((tc).tail, pair); \ | |
80 | (tc).tail = pair; \ | |
d3a6bc94 | 81 | } while (0) |
e1f2bf99 MD |
82 | |
83 | #define TCONC_OUT(tc, res) \ | |
d3a6bc94 | 84 | do { \ |
e1f2bf99 MD |
85 | (res) = SCM_CAR ((tc).head); \ |
86 | (tc).head = SCM_CDR ((tc).head); \ | |
d3a6bc94 | 87 | } while (0) |
e1f2bf99 MD |
88 | |
89 | #define TCONC_EMPTYP(tc) ((tc).head == (tc).tail) | |
90 | ||
91 | typedef struct tconc_t | |
92 | { | |
93 | SCM head; | |
94 | SCM tail; | |
95 | } tconc_t; | |
96 | ||
97 | typedef struct guardian_t | |
98 | { | |
99 | tconc_t live; | |
100 | tconc_t zombies; | |
01a119ac | 101 | struct guardian_t *next; |
e1f2bf99 MD |
102 | } guardian_t; |
103 | ||
104 | #define GUARDIAN(x) ((guardian_t *) SCM_CDR (x)) | |
105 | #define GUARDIAN_LIVE(x) (GUARDIAN (x)->live) | |
106 | #define GUARDIAN_ZOMBIES(x) (GUARDIAN (x)->zombies) | |
01a119ac | 107 | #define GUARDIAN_NEXT(x) (GUARDIAN (x)->next) |
e1f2bf99 | 108 | |
01a119ac JB |
109 | static guardian_t *first_live_guardian = NULL; |
110 | static guardian_t **current_link_field = NULL; | |
e1f2bf99 MD |
111 | |
112 | static SCM | |
113 | g_mark (SCM ptr) | |
114 | { | |
01a119ac JB |
115 | *current_link_field = GUARDIAN (ptr); |
116 | current_link_field = &GUARDIAN_NEXT (ptr); | |
117 | GUARDIAN_NEXT (ptr) = NULL; | |
118 | ||
e1f2bf99 MD |
119 | /* Can't mark zombies here since they can refer to objects which are |
120 | living dead, thereby preventing them to join the zombies. */ | |
121 | return SCM_BOOL_F; | |
122 | } | |
123 | ||
e1f2bf99 MD |
124 | static int |
125 | g_print (SCM exp, SCM port, scm_print_state *pstate) | |
126 | { | |
127 | char buf[256]; | |
128 | sprintf (buf, "#<guardian live objs: %lu zombies: %lu>", | |
129 | scm_ilength (SCM_CDR (GUARDIAN_LIVE (exp).head)), | |
130 | scm_ilength (SCM_CDR (GUARDIAN_ZOMBIES (exp).head))); | |
131 | scm_puts (buf, port); | |
132 | ||
133 | return 1; | |
134 | } | |
135 | ||
e1f2bf99 MD |
136 | #define CCLO_G(cclo) (SCM_VELTS (cclo)[1]) |
137 | ||
138 | static SCM | |
139 | guard (SCM cclo, SCM arg) | |
140 | { | |
141 | if (!SCM_UNBNDP (arg)) | |
142 | { | |
143 | scm_guard (cclo, arg); | |
144 | return SCM_UNSPECIFIED; | |
145 | } | |
146 | else | |
147 | return scm_get_one_zombie (cclo); | |
148 | } | |
149 | ||
150 | static SCM guard1; | |
151 | ||
a1ec6916 | 152 | SCM_DEFINE (scm_make_guardian, "make-guardian", 0, 0, 0, |
1bbd0b84 GB |
153 | (), |
154 | "") | |
155 | #define FUNC_NAME s_scm_make_guardian | |
e1f2bf99 MD |
156 | { |
157 | SCM cclo = scm_makcclo (guard1, 2L); | |
1bbd0b84 | 158 | guardian_t *g = SCM_MUST_MALLOC_TYPE(guardian_t); |
e1f2bf99 MD |
159 | SCM z1 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); |
160 | SCM z2 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); | |
161 | SCM z; | |
e1f2bf99 MD |
162 | /* A tconc starts out with one tail pair. */ |
163 | g->live.head = g->live.tail = z1; | |
164 | g->zombies.head = g->zombies.tail = z2; | |
23a62151 MD |
165 | |
166 | SCM_NEWSMOB (z, scm_tc16_guardian, g); | |
e1f2bf99 MD |
167 | |
168 | CCLO_G (cclo) = z; | |
169 | ||
170 | return cclo; | |
171 | } | |
1bbd0b84 | 172 | #undef FUNC_NAME |
e1f2bf99 MD |
173 | |
174 | void | |
175 | scm_guardian_gc_init() | |
176 | { | |
01a119ac JB |
177 | current_link_field = &first_live_guardian; |
178 | first_live_guardian = NULL; | |
e1f2bf99 MD |
179 | } |
180 | ||
181 | void | |
182 | scm_guardian_zombify () | |
183 | { | |
01a119ac | 184 | guardian_t *g; |
55b7e0bd JB |
185 | |
186 | /* Note that new guardians may be stuck on the end of the live | |
187 | guardian list as we run this loop. As we move unmarked objects | |
188 | to the zombie list and mark them, we may find some guarded | |
189 | guardians. The guardian mark function will stick them on the end | |
190 | of this list, so they'll be processed properly. */ | |
01a119ac | 191 | for (g = first_live_guardian; g; g = g->next) |
e1f2bf99 | 192 | { |
67b2561b JB |
193 | /* Scan the live list for unmarked objects, and move them to the |
194 | zombies tconc. */ | |
01a119ac | 195 | SCM tconc_tail = g->live.tail; |
67b2561b | 196 | SCM *prev_ptr = &g->live.head; |
01a119ac | 197 | SCM pair = g->live.head; |
67b2561b | 198 | |
e1f2bf99 MD |
199 | while (pair != tconc_tail) |
200 | { | |
201 | SCM next_pair = SCM_CDR (pair); | |
202 | ||
203 | if (SCM_NMARKEDP (SCM_CAR (pair))) | |
204 | { | |
205 | /* got you, zombie! */ | |
206 | ||
207 | /* out of the live list! */ | |
67b2561b | 208 | *prev_ptr = next_pair; |
e1f2bf99 MD |
209 | |
210 | /* to the zombie list! */ | |
01a119ac | 211 | TCONC_IN (g->zombies, SCM_CAR (pair), pair); |
e1f2bf99 MD |
212 | } |
213 | else | |
67b2561b | 214 | prev_ptr = SCM_CDRLOC (pair); |
e1f2bf99 MD |
215 | |
216 | pair = next_pair; | |
217 | } | |
67b2561b JB |
218 | |
219 | /* Mark the cells of the live list. */ | |
220 | for (pair = g->live.head; SCM_NIMP (pair); pair = SCM_GCCDR (pair)) | |
221 | SCM_SETGCMARK (pair); | |
55b7e0bd JB |
222 | |
223 | /* Bring the zombies back from the dead. */ | |
01a119ac | 224 | scm_gc_mark (g->zombies.head); |
e1f2bf99 MD |
225 | } |
226 | } | |
227 | ||
228 | void | |
229 | scm_guard (SCM guardian, SCM obj) | |
230 | { | |
231 | SCM g = CCLO_G (guardian); | |
232 | ||
233 | if (SCM_NIMP (obj)) | |
234 | { | |
235 | SCM z; | |
236 | ||
237 | SCM_NEWCELL (z); | |
238 | ||
239 | /* This critical section barrier will be replaced by a mutex. */ | |
240 | SCM_DEFER_INTS; | |
241 | TCONC_IN (GUARDIAN_LIVE (g), obj, z); | |
242 | SCM_ALLOW_INTS; | |
243 | } | |
244 | } | |
245 | ||
246 | SCM | |
247 | scm_get_one_zombie (SCM guardian) | |
248 | { | |
249 | SCM g = CCLO_G (guardian); | |
250 | SCM res = SCM_BOOL_F; | |
251 | ||
252 | /* This critical section barrier will be replaced by a mutex. */ | |
253 | SCM_DEFER_INTS; | |
254 | if (!TCONC_EMPTYP (GUARDIAN_ZOMBIES (g))) | |
255 | TCONC_OUT (GUARDIAN_ZOMBIES (g), res); | |
256 | SCM_ALLOW_INTS; | |
257 | ||
258 | return res; | |
259 | } | |
260 | ||
261 | void | |
262 | scm_init_guardian() | |
263 | { | |
23a62151 MD |
264 | scm_tc16_guardian = scm_make_smob_type_mfpe ("guardian", sizeof (guardian_t), |
265 | g_mark, NULL, g_print, NULL); | |
e1f2bf99 MD |
266 | guard1 = scm_make_subr_opt ("guardian", scm_tc7_subr_2o, guard, 0); |
267 | ||
268 | #include "guardians.x" | |
269 | } |