Commit | Line | Data |
---|---|---|
e46f3fa6 | 1 | /* Copyright (C) 1998, 1999, 2000 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 | ||
e1f2bf99 | 57 | |
a0599745 MD |
58 | #include "libguile/_scm.h" |
59 | #include "libguile/ports.h" | |
60 | #include "libguile/print.h" | |
61 | #include "libguile/smob.h" | |
e1f2bf99 | 62 | |
a0599745 MD |
63 | #include "libguile/validate.h" |
64 | #include "libguile/guardians.h" | |
e1f2bf99 | 65 | |
e1f2bf99 MD |
66 | |
67 | /* The live and zombies FIFOs are implemented as tconcs as described | |
68 | in Dybvig's paper. This decouples addition and removal of elements | |
69 | so that no synchronization between these needs to take place. | |
70 | */ | |
01449aa5 DH |
71 | |
72 | typedef struct tconc_t | |
73 | { | |
74 | SCM head; | |
75 | SCM tail; | |
76 | } tconc_t; | |
77 | ||
78 | #define TCONC_EMPTYP(tc) (SCM_EQ_P ((tc).head, (tc).tail)) | |
79 | ||
e1f2bf99 | 80 | #define TCONC_IN(tc, obj, pair) \ |
d3a6bc94 | 81 | do { \ |
e1f2bf99 MD |
82 | SCM_SETCAR ((tc).tail, obj); \ |
83 | SCM_SETCAR (pair, SCM_BOOL_F); \ | |
e46f3fa6 | 84 | SCM_SETCDR (pair, SCM_EOL); \ |
e1f2bf99 MD |
85 | SCM_SETCDR ((tc).tail, pair); \ |
86 | (tc).tail = pair; \ | |
d3a6bc94 | 87 | } while (0) |
e1f2bf99 MD |
88 | |
89 | #define TCONC_OUT(tc, res) \ | |
d3a6bc94 | 90 | do { \ |
e1f2bf99 MD |
91 | (res) = SCM_CAR ((tc).head); \ |
92 | (tc).head = SCM_CDR ((tc).head); \ | |
d3a6bc94 | 93 | } while (0) |
e1f2bf99 | 94 | |
e1f2bf99 | 95 | |
e841c3e0 | 96 | static scm_bits_t tc16_guardian; |
e1f2bf99 MD |
97 | |
98 | typedef struct guardian_t | |
99 | { | |
100 | tconc_t live; | |
101 | tconc_t zombies; | |
01a119ac | 102 | struct guardian_t *next; |
e1f2bf99 MD |
103 | } guardian_t; |
104 | ||
7fa93bf8 | 105 | #define GUARDIAN(x) ((guardian_t *) SCM_CELL_WORD_1 (x)) |
e1f2bf99 MD |
106 | #define GUARDIAN_LIVE(x) (GUARDIAN (x)->live) |
107 | #define GUARDIAN_ZOMBIES(x) (GUARDIAN (x)->zombies) | |
01a119ac | 108 | #define GUARDIAN_NEXT(x) (GUARDIAN (x)->next) |
e1f2bf99 | 109 | |
e1f2bf99 | 110 | |
01449aa5 DH |
111 | /* during the gc mark phase, live guardians are linked into a list here. */ |
112 | static guardian_t *first_live_guardian = NULL; | |
113 | static guardian_t **current_link_field = NULL; | |
114 | ||
e46f3fa6 | 115 | |
01449aa5 | 116 | /* mark a guardian by adding it to the live guardian list. */ |
e1f2bf99 | 117 | static SCM |
01449aa5 DH |
118 | guardian_mark (SCM ptr) |
119 | { | |
120 | *current_link_field = GUARDIAN (ptr); | |
121 | current_link_field = &GUARDIAN_NEXT (ptr); | |
122 | GUARDIAN_NEXT (ptr) = NULL; | |
123 | ||
124 | /* the objects protected by the guardian are not marked here: that | |
125 | would prevent them from ever getting collected. instead marking | |
126 | is done at the end of the mark phase by scm_guardian_zombify. */ | |
127 | return SCM_BOOL_F; | |
128 | } | |
129 | ||
130 | ||
131 | static scm_sizet | |
132 | guardian_free (SCM ptr) | |
133 | { | |
134 | scm_must_free (GUARDIAN (ptr)); | |
135 | return sizeof (guardian_t); | |
136 | } | |
137 | ||
138 | ||
139 | static int | |
140 | guardian_print (SCM g, SCM port, scm_print_state *pstate) | |
141 | { | |
142 | scm_puts ("#<guardian live objs: ", port); | |
143 | scm_display (scm_length (SCM_CDR (GUARDIAN_LIVE (g).head)), port); | |
144 | scm_puts (" zombies: ", port); | |
145 | scm_display (scm_length (SCM_CDR (GUARDIAN_ZOMBIES (g).head)), port); | |
146 | scm_puts (">", port); | |
147 | ||
148 | return 1; | |
149 | } | |
150 | ||
151 | ||
152 | /* This is the Scheme entry point for each guardian: If arg is an object, it's | |
153 | * added to the guardian's live list. If arg is unbound, the next available | |
154 | * zombified object (or #f if none) is returned. | |
155 | */ | |
156 | static SCM | |
157 | guardian_apply (SCM guardian, SCM arg) | |
e1f2bf99 MD |
158 | { |
159 | if (!SCM_UNBNDP (arg)) | |
160 | { | |
01449aa5 | 161 | scm_guard (guardian, arg); |
e1f2bf99 MD |
162 | return SCM_UNSPECIFIED; |
163 | } | |
164 | else | |
01449aa5 | 165 | return scm_get_one_zombie (guardian); |
e1f2bf99 MD |
166 | } |
167 | ||
01449aa5 | 168 | |
e46f3fa6 GH |
169 | void |
170 | scm_guard (SCM guardian, SCM obj) | |
171 | { | |
01449aa5 | 172 | if (!SCM_IMP (obj)) |
e46f3fa6 GH |
173 | { |
174 | SCM z; | |
01449aa5 | 175 | |
e46f3fa6 GH |
176 | SCM_NEWCELL (z); |
177 | ||
178 | /* This critical section barrier will be replaced by a mutex. */ | |
179 | SCM_DEFER_INTS; | |
01449aa5 | 180 | TCONC_IN (GUARDIAN_LIVE (guardian), obj, z); |
e46f3fa6 GH |
181 | SCM_ALLOW_INTS; |
182 | } | |
183 | } | |
184 | ||
01449aa5 | 185 | |
e46f3fa6 GH |
186 | SCM |
187 | scm_get_one_zombie (SCM guardian) | |
188 | { | |
e46f3fa6 GH |
189 | SCM res = SCM_BOOL_F; |
190 | ||
191 | /* This critical section barrier will be replaced by a mutex. */ | |
192 | SCM_DEFER_INTS; | |
01449aa5 DH |
193 | if (!TCONC_EMPTYP (GUARDIAN_ZOMBIES (guardian))) |
194 | TCONC_OUT (GUARDIAN_ZOMBIES (guardian), res); | |
e46f3fa6 GH |
195 | SCM_ALLOW_INTS; |
196 | return res; | |
197 | } | |
e1f2bf99 | 198 | |
01449aa5 | 199 | |
a1ec6916 | 200 | SCM_DEFINE (scm_make_guardian, "make-guardian", 0, 0, 0, |
1bbd0b84 | 201 | (), |
e46f3fa6 GH |
202 | "Create a new guardian.\n" |
203 | "A guardian protects a set of objects from garbage collection,\n" | |
204 | "allowing a program to apply cleanup or other actions.\n\n" | |
205 | ||
206 | "make-guardian returns a procedure representing the guardian.\n" | |
207 | "Calling the guardian procedure with an argument adds the\n" | |
208 | "argument to the guardian's set of protected objects.\n" | |
209 | "Calling the guardian procedure without an argument returns\n" | |
210 | "one of the protected objects which are ready for garbage\n" | |
211 | "collection or @code{#f} if no such object is available.\n" | |
212 | "Objects which are returned in this way are removed from\n" | |
92ccc1f1 | 213 | "the guardian.\n\n" |
e46f3fa6 | 214 | |
da4a1dba GB |
215 | "See R. Kent Dybvig, Carl Bruggeman, and David Eby (1993)\n" |
216 | "\"Guardians in a Generation-Based Garbage Collector\".\n" | |
217 | "ACM SIGPLAN Conference on Programming Language Design\n" | |
e46f3fa6 | 218 | "and Implementation, June 1993.") |
1bbd0b84 | 219 | #define FUNC_NAME s_scm_make_guardian |
e1f2bf99 | 220 | { |
01449aa5 | 221 | guardian_t *g = SCM_MUST_MALLOC_TYPE (guardian_t); |
e46f3fa6 GH |
222 | SCM z1 = scm_cons (SCM_BOOL_F, SCM_EOL); |
223 | SCM z2 = scm_cons (SCM_BOOL_F, SCM_EOL); | |
e1f2bf99 | 224 | SCM z; |
e46f3fa6 | 225 | |
e1f2bf99 MD |
226 | /* A tconc starts out with one tail pair. */ |
227 | g->live.head = g->live.tail = z1; | |
228 | g->zombies.head = g->zombies.tail = z2; | |
23a62151 | 229 | |
01449aa5 | 230 | SCM_NEWSMOB (z, tc16_guardian, g); |
e1f2bf99 | 231 | |
01449aa5 | 232 | return z; |
e1f2bf99 | 233 | } |
1bbd0b84 | 234 | #undef FUNC_NAME |
e1f2bf99 | 235 | |
e46f3fa6 | 236 | |
01449aa5 | 237 | /* called before gc mark phase begins to initialise the live guardian list. */ |
5d2565a7 | 238 | static void * |
01449aa5 | 239 | guardian_gc_init (void *dummy1, void *dummy2, void *dummy3) |
e1f2bf99 | 240 | { |
01a119ac JB |
241 | current_link_field = &first_live_guardian; |
242 | first_live_guardian = NULL; | |
5d2565a7 MD |
243 | |
244 | return 0; | |
e1f2bf99 MD |
245 | } |
246 | ||
e46f3fa6 GH |
247 | |
248 | /* this is called by the garbage collector between the mark and sweep | |
249 | phases. for each marked guardian, it moves any unmarked object in | |
250 | its live list (tconc) to its zombie list (tconc). */ | |
5d2565a7 | 251 | static void * |
01449aa5 | 252 | guardian_zombify (void *dummy1, void *dummy2, void *dummy3) |
e1f2bf99 | 253 | { |
50fecba9 ML |
254 | guardian_t *first_guardian; |
255 | guardian_t **link_field = &first_live_guardian; | |
55b7e0bd JB |
256 | |
257 | /* Note that new guardians may be stuck on the end of the live | |
258 | guardian list as we run this loop. As we move unmarked objects | |
259 | to the zombie list and mark them, we may find some guarded | |
260 | guardians. The guardian mark function will stick them on the end | |
261 | of this list, so they'll be processed properly. */ | |
e46f3fa6 | 262 | |
50fecba9 ML |
263 | do { |
264 | guardian_t *g; | |
265 | ||
266 | first_guardian = *link_field; | |
267 | link_field = current_link_field; | |
268 | ||
269 | /* first, scan all the guardians that are currently known to be live | |
270 | and move their unmarked objects to zombie lists. */ | |
271 | ||
272 | for (g = first_guardian; g; g = g->next) | |
273 | { | |
274 | SCM tconc_tail = g->live.tail; | |
275 | SCM *prev_ptr = &g->live.head; | |
276 | SCM pair = g->live.head; | |
277 | ||
278 | while (! SCM_EQ_P (pair, tconc_tail)) | |
279 | { | |
280 | SCM next_pair = SCM_CDR (pair); | |
281 | ||
282 | if (SCM_NMARKEDP (SCM_CAR (pair))) | |
283 | { | |
284 | /* got you, zombie! */ | |
285 | ||
286 | /* out of the live list! */ | |
287 | *prev_ptr = next_pair; | |
288 | ||
289 | /* into the zombie list! */ | |
290 | TCONC_IN (g->zombies, SCM_CAR (pair), pair); | |
291 | } | |
292 | else | |
293 | prev_ptr = SCM_CDRLOC (pair); | |
294 | ||
295 | pair = next_pair; | |
296 | } | |
297 | ||
298 | /* Mark the cells of the live list (yes, the cells in the list, | |
299 | even though we don't care about objects pointed to by the list | |
300 | cars, since we know they are already marked). */ | |
01449aa5 | 301 | for (pair = g->live.head; !SCM_NULLP (pair); pair = SCM_CDR (pair)) |
50fecba9 ML |
302 | SCM_SETGCMARK (pair); |
303 | } | |
304 | ||
305 | /* ghouston: Doesn't it seem a bit disturbing that if a zombie | |
306 | is returned to full life after getting returned from the | |
307 | guardian procedure, it may reference objects which are in a | |
308 | guardian's zombie list? Is it not necessary to move such | |
309 | zombies back to the live list, to avoid allowing the | |
310 | guardian procedure to return an object which is referenced, | |
311 | so not collectable? The paper doesn't give this | |
312 | impression. | |
01449aa5 | 313 | |
50fecba9 ML |
314 | cmm: the paper does explicitly say that an object that is |
315 | guarded more than once should be returned more than once. | |
316 | I believe this covers the above scenario. */ | |
01449aa5 | 317 | |
50fecba9 ML |
318 | /* Preserve the zombies in their undead state, by marking to |
319 | prevent collection. Note that this may uncover zombified | |
320 | guardians -- if so, they'll be processed in the next loop. */ | |
01449aa5 | 321 | for (g = first_guardian; g != *link_field; g = g->next) |
01a119ac | 322 | scm_gc_mark (g->zombies.head); |
50fecba9 | 323 | } while (current_link_field != link_field); |
5d2565a7 MD |
324 | |
325 | return 0; | |
e1f2bf99 MD |
326 | } |
327 | ||
e1f2bf99 MD |
328 | |
329 | void | |
330 | scm_init_guardian() | |
331 | { | |
01449aa5 DH |
332 | tc16_guardian = scm_make_smob_type ("guardian", 0); |
333 | scm_set_smob_mark (tc16_guardian, guardian_mark); | |
334 | scm_set_smob_free (tc16_guardian, guardian_free); | |
335 | scm_set_smob_print (tc16_guardian, guardian_print); | |
336 | scm_set_smob_apply (tc16_guardian, guardian_apply, 0, 1, 0); | |
337 | ||
338 | scm_c_hook_add (&scm_before_mark_c_hook, guardian_gc_init, 0, 0); | |
339 | scm_c_hook_add (&scm_before_sweep_c_hook, guardian_zombify, 0, 0); | |
e1f2bf99 | 340 | |
8dc9439f | 341 | #ifndef SCM_MAGIC_SNARFER |
a0599745 | 342 | #include "libguile/guardians.x" |
8dc9439f | 343 | #endif |
e1f2bf99 | 344 | } |
89e00824 ML |
345 | |
346 | /* | |
347 | Local Variables: | |
348 | c-file-style: "gnu" | |
349 | End: | |
350 | */ |