Commit | Line | Data |
---|---|---|
dbb605f5 | 1 | /* Copyright (C) 1998,1999,2000,2001, 2006, 2008 Free Software Foundation, Inc. |
e1f2bf99 | 2 | * |
73be1d9e | 3 | * This library is free software; you can redistribute it and/or |
53befeb7 NJ |
4 | * modify it under the terms of the GNU Lesser General Public License |
5 | * as published by the Free Software Foundation; either version 3 of | |
6 | * the License, or (at your option) any later version. | |
e1f2bf99 | 7 | * |
53befeb7 NJ |
8 | * This library is distributed in the hope that it will be useful, but |
9 | * WITHOUT ANY WARRANTY; without even the implied warranty of | |
73be1d9e MV |
10 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
11 | * Lesser General Public License for more details. | |
e1f2bf99 | 12 | * |
73be1d9e MV |
13 | * You should have received a copy of the GNU Lesser General Public |
14 | * License along with this library; if not, write to the Free Software | |
53befeb7 NJ |
15 | * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
16 | * 02110-1301 USA | |
73be1d9e | 17 | */ |
1bbd0b84 | 18 | |
e1f2bf99 MD |
19 | \f |
20 | ||
21 | /* This is an implementation of guardians as described in | |
22 | * R. Kent Dybvig, Carl Bruggeman, and David Eby (1993) "Guardians in | |
23 | * a Generation-Based Garbage Collector" ACM SIGPLAN Conference on | |
24 | * Programming Language Design and Implementation, June 1993 | |
25 | * ftp://ftp.cs.indiana.edu/pub/scheme-repository/doc/pubs/guardians.ps.gz | |
26 | * | |
06c1d900 MV |
27 | * Original design: Mikael Djurfeldt |
28 | * Original implementation: Michael Livshin | |
29 | * Hacked on since by: everybody | |
30 | * | |
56495472 ML |
31 | * By this point, the semantics are actually quite different from |
32 | * those described in the abovementioned paper. The semantic changes | |
33 | * are there to improve safety and intuitiveness. The interface is | |
34 | * still (mostly) the one described by the paper, however. | |
35 | * | |
06c1d900 MV |
36 | * Boiled down again: Marius Vollmer |
37 | * | |
38 | * Now they should again behave like those described in the paper. | |
39 | * Scheme guardians should be simple and friendly, not like the greedy | |
40 | * monsters we had... | |
e1f2bf99 MD |
41 | */ |
42 | ||
dbb605f5 LC |
43 | #ifdef HAVE_CONFIG_H |
44 | # include <config.h> | |
45 | #endif | |
e1f2bf99 | 46 | |
a0599745 | 47 | #include "libguile/_scm.h" |
4e047c3e | 48 | #include "libguile/async.h" |
a0599745 MD |
49 | #include "libguile/ports.h" |
50 | #include "libguile/print.h" | |
51 | #include "libguile/smob.h" | |
a0599745 | 52 | #include "libguile/validate.h" |
56495472 | 53 | #include "libguile/root.h" |
d9dcd933 ML |
54 | #include "libguile/hashtab.h" |
55 | #include "libguile/weaks.h" | |
06c1d900 MV |
56 | #include "libguile/deprecation.h" |
57 | #include "libguile/eval.h" | |
56495472 | 58 | |
a0599745 | 59 | #include "libguile/guardians.h" |
e1f2bf99 | 60 | |
e1f2bf99 MD |
61 | |
62 | /* The live and zombies FIFOs are implemented as tconcs as described | |
63 | in Dybvig's paper. This decouples addition and removal of elements | |
64 | so that no synchronization between these needs to take place. | |
65 | */ | |
01449aa5 | 66 | |
455c0ac8 | 67 | typedef struct t_tconc |
01449aa5 DH |
68 | { |
69 | SCM head; | |
70 | SCM tail; | |
455c0ac8 | 71 | } t_tconc; |
01449aa5 | 72 | |
bc36d050 | 73 | #define TCONC_EMPTYP(tc) (scm_is_eq ((tc).head, (tc).tail)) |
01449aa5 | 74 | |
e1f2bf99 | 75 | #define TCONC_IN(tc, obj, pair) \ |
d3a6bc94 | 76 | do { \ |
e1f2bf99 | 77 | SCM_SETCAR ((tc).tail, obj); \ |
2ff08405 DH |
78 | SCM_SET_CELL_OBJECT_1 (pair, SCM_EOL); \ |
79 | SCM_SET_CELL_OBJECT_0 (pair, SCM_BOOL_F); \ | |
e1f2bf99 MD |
80 | SCM_SETCDR ((tc).tail, pair); \ |
81 | (tc).tail = pair; \ | |
d3a6bc94 | 82 | } while (0) |
e1f2bf99 MD |
83 | |
84 | #define TCONC_OUT(tc, res) \ | |
d3a6bc94 | 85 | do { \ |
e1f2bf99 MD |
86 | (res) = SCM_CAR ((tc).head); \ |
87 | (tc).head = SCM_CDR ((tc).head); \ | |
d3a6bc94 | 88 | } while (0) |
e1f2bf99 | 89 | |
e1f2bf99 | 90 | |
92c2555f | 91 | static scm_t_bits tc16_guardian; |
e1f2bf99 | 92 | |
455c0ac8 | 93 | typedef struct t_guardian |
e1f2bf99 | 94 | { |
455c0ac8 DH |
95 | t_tconc live; |
96 | t_tconc zombies; | |
97 | struct t_guardian *next; | |
455c0ac8 | 98 | } t_guardian; |
e1f2bf99 | 99 | |
06c1d900 | 100 | #define GUARDIAN_P(x) SCM_SMOB_PREDICATE(tc16_guardian, x) |
455c0ac8 | 101 | #define GUARDIAN_DATA(x) ((t_guardian *) SCM_CELL_WORD_1 (x)) |
56495472 | 102 | |
06c1d900 | 103 | static t_guardian *guardians; |
c0a5d888 | 104 | |
06c1d900 MV |
105 | void |
106 | scm_i_init_guardians_for_gc () | |
107 | { | |
108 | guardians = NULL; | |
109 | } | |
56495472 | 110 | |
06c1d900 MV |
111 | /* mark a guardian by adding it to the live guardian list. */ |
112 | static SCM | |
113 | guardian_mark (SCM ptr) | |
114 | { | |
115 | t_guardian *g = GUARDIAN_DATA (ptr); | |
116 | g->next = guardians; | |
117 | guardians = g; | |
56495472 | 118 | |
06c1d900 MV |
119 | return SCM_BOOL_F; |
120 | } | |
56495472 | 121 | |
06c1d900 MV |
122 | /* Identify inaccessible objects and move them from the live list to |
123 | the zombie list. An object is inaccessible when it is unmarked at | |
124 | this point. Therefore, the inaccessible objects are not marked yet | |
125 | since that would prevent them from being recognized as | |
126 | inaccessible. | |
e1f2bf99 | 127 | |
06c1d900 MV |
128 | The pairs that form the life list itself are marked, tho. |
129 | */ | |
130 | void | |
131 | scm_i_identify_inaccessible_guardeds () | |
56495472 | 132 | { |
06c1d900 | 133 | t_guardian *g; |
e1f2bf99 | 134 | |
06c1d900 | 135 | for (g = guardians; g; g = g->next) |
56495472 | 136 | { |
06c1d900 MV |
137 | SCM pair, next_pair; |
138 | SCM *prev_ptr; | |
139 | ||
140 | for (pair = g->live.head, prev_ptr = &g->live.head; | |
141 | !scm_is_eq (pair, g->live.tail); | |
142 | pair = next_pair) | |
143 | { | |
144 | SCM obj = SCM_CAR (pair); | |
145 | next_pair = SCM_CDR (pair); | |
146 | if (!SCM_GC_MARK_P (obj)) | |
147 | { | |
148 | /* Unmarked, move to 'inaccessible' list. | |
149 | */ | |
150 | *prev_ptr = next_pair; | |
151 | TCONC_IN (g->zombies, obj, pair); | |
152 | } | |
153 | else | |
154 | { | |
155 | SCM_SET_GC_MARK (pair); | |
156 | prev_ptr = SCM_CDRLOC (pair); | |
157 | } | |
158 | } | |
159 | SCM_SET_GC_MARK (pair); | |
56495472 | 160 | } |
56495472 | 161 | } |
e46f3fa6 | 162 | |
06c1d900 MV |
163 | int |
164 | scm_i_mark_inaccessible_guardeds () | |
01449aa5 | 165 | { |
06c1d900 MV |
166 | t_guardian *g; |
167 | int again = 0; | |
01449aa5 | 168 | |
06c1d900 MV |
169 | /* We never need to see the guardians again that are processed here, |
170 | so we clear the list. Calling scm_gc_mark below might find new | |
171 | guardians, however (and other things), and we inform the GC about | |
172 | this by returning non-zero. See scm_mark_all in gc-mark.c | |
173 | */ | |
01449aa5 | 174 | |
06c1d900 MV |
175 | g = guardians; |
176 | guardians = NULL; | |
177 | ||
178 | for (; g; g = g->next) | |
179 | { | |
180 | SCM pair; | |
181 | ||
182 | for (pair = g->zombies.head; | |
183 | !scm_is_eq (pair, g->zombies.tail); | |
184 | pair = SCM_CDR (pair)) | |
185 | { | |
186 | if (!SCM_GC_MARK_P (pair)) | |
187 | { | |
188 | scm_gc_mark (SCM_CAR (pair)); | |
189 | SCM_SET_GC_MARK (pair); | |
190 | again = 1; | |
191 | } | |
192 | } | |
193 | SCM_SET_GC_MARK (pair); | |
194 | } | |
195 | return again; | |
196 | } | |
01449aa5 | 197 | |
1be6b49c | 198 | static size_t |
01449aa5 DH |
199 | guardian_free (SCM ptr) |
200 | { | |
4c9419ac MV |
201 | scm_gc_free (GUARDIAN_DATA (ptr), sizeof (t_guardian), "guardian"); |
202 | return 0; | |
01449aa5 DH |
203 | } |
204 | ||
01449aa5 | 205 | static int |
e81d98ec | 206 | guardian_print (SCM guardian, SCM port, scm_print_state *pstate SCM_UNUSED) |
01449aa5 | 207 | { |
455c0ac8 | 208 | t_guardian *g = GUARDIAN_DATA (guardian); |
c0a5d888 | 209 | |
06c1d900 | 210 | scm_puts ("#<guardian ", port); |
0345e278 | 211 | scm_uintprint ((scm_t_bits) g, 16, port); |
c0a5d888 | 212 | |
06c1d900 MV |
213 | scm_puts (" (reachable: ", port); |
214 | scm_display (scm_length (SCM_CDR (g->live.head)), port); | |
215 | scm_puts (" unreachable: ", port); | |
216 | scm_display (scm_length (SCM_CDR (g->zombies.head)), port); | |
217 | scm_puts (")", port); | |
c0a5d888 ML |
218 | |
219 | scm_puts (">", port); | |
01449aa5 DH |
220 | |
221 | return 1; | |
222 | } | |
223 | ||
06c1d900 MV |
224 | static void |
225 | scm_i_guard (SCM guardian, SCM obj) | |
e46f3fa6 | 226 | { |
455c0ac8 | 227 | t_guardian *g = GUARDIAN_DATA (guardian); |
c0a5d888 | 228 | |
01449aa5 | 229 | if (!SCM_IMP (obj)) |
e46f3fa6 GH |
230 | { |
231 | SCM z; | |
16d4699b | 232 | z = scm_cons (SCM_BOOL_F, SCM_BOOL_F); |
c0a5d888 | 233 | TCONC_IN (g->live, obj, z); |
e46f3fa6 GH |
234 | } |
235 | } | |
236 | ||
06c1d900 MV |
237 | static SCM |
238 | scm_i_get_one_zombie (SCM guardian) | |
e46f3fa6 | 239 | { |
455c0ac8 | 240 | t_guardian *g = GUARDIAN_DATA (guardian); |
e46f3fa6 GH |
241 | SCM res = SCM_BOOL_F; |
242 | ||
c0a5d888 ML |
243 | if (!TCONC_EMPTYP (g->zombies)) |
244 | TCONC_OUT (g->zombies, res); | |
56495472 | 245 | |
e46f3fa6 GH |
246 | return res; |
247 | } | |
e1f2bf99 | 248 | |
06c1d900 MV |
249 | /* This is the Scheme entry point for each guardian: If OBJ is an |
250 | * object, it's added to the guardian's live list. If OBJ is unbound, | |
251 | * the next available unreachable object (or #f if none) is returned. | |
252 | * | |
253 | * If the second optional argument THROW_P is true (the default), then | |
254 | * an error is raised if GUARDIAN is greedy and OBJ is already greedily | |
255 | * guarded. If THROW_P is false, #f is returned instead of raising the | |
256 | * error, and #t is returned if everything is fine. | |
257 | */ | |
258 | static SCM | |
259 | guardian_apply (SCM guardian, SCM obj, SCM throw_p) | |
260 | { | |
261 | #if ENABLE_DEPRECATED | |
262 | if (!SCM_UNBNDP (throw_p)) | |
263 | scm_c_issue_deprecation_warning | |
264 | ("Using the 'throw?' argument of a guardian is deprecated " | |
265 | "and ineffective."); | |
266 | #endif | |
01449aa5 | 267 | |
06c1d900 MV |
268 | if (!SCM_UNBNDP (obj)) |
269 | { | |
270 | scm_i_guard (guardian, obj); | |
271 | return SCM_UNSPECIFIED; | |
272 | } | |
273 | else | |
274 | return scm_i_get_one_zombie (guardian); | |
275 | } | |
276 | ||
277 | SCM_DEFINE (scm_make_guardian, "make-guardian", 0, 0, 0, | |
278 | (), | |
279 | "Create a new guardian. A guardian protects a set of objects from\n" | |
280 | "garbage collection, allowing a program to apply cleanup or other\n" | |
281 | "actions.\n" | |
282 | "\n" | |
283 | "@code{make-guardian} returns a procedure representing the guardian.\n" | |
284 | "Calling the guardian procedure with an argument adds the argument to\n" | |
285 | "the guardian's set of protected objects. Calling the guardian\n" | |
286 | "procedure without an argument returns one of the protected objects\n" | |
287 | "which are ready for garbage collection, or @code{#f} if no such object\n" | |
288 | "is available. Objects which are returned in this way are removed from\n" | |
289 | "the guardian.\n" | |
290 | "\n" | |
291 | "You can put a single object into a guardian more than once and you can\n" | |
292 | "put a single object into more than one guardian. The object will then\n" | |
293 | "be returned multiple times by the guardian procedures.\n" | |
294 | "\n" | |
295 | "An object is eligible to be returned from a guardian when it is no\n" | |
296 | "longer referenced from outside any guardian.\n" | |
297 | "\n" | |
298 | "There is no guarantee about the order in which objects are returned\n" | |
299 | "from a guardian. If you want to impose an order on finalization\n" | |
300 | "actions, for example, you can do that by keeping objects alive in some\n" | |
301 | "global data structure until they are no longer needed for finalizing\n" | |
302 | "other objects.\n" | |
303 | "\n" | |
304 | "Being an element in a weak vector, a key in a hash table with weak\n" | |
305 | "keys, or a value in a hash table with weak value does not prevent an\n" | |
306 | "object from being returned by a guardian. But as long as an object\n" | |
307 | "can be returned from a guardian it will not be removed from such a\n" | |
308 | "weak vector or hash table. In other words, a weak link does not\n" | |
309 | "prevent an object from being considered collectable, but being inside\n" | |
310 | "a guardian prevents a weak link from being broken.\n" | |
311 | "\n" | |
312 | "A key in a weak key hash table can be though of as having a strong\n" | |
313 | "reference to its associated value as long as the key is accessible.\n" | |
314 | "Consequently, when the key only accessible from within a guardian, the\n" | |
315 | "reference from the key to the value is also considered to be coming\n" | |
316 | "from within a guardian. Thus, if there is no other reference to the\n" | |
317 | "value, it is eligible to be returned from a guardian.\n") | |
1bbd0b84 | 318 | #define FUNC_NAME s_scm_make_guardian |
e1f2bf99 | 319 | { |
4c9419ac | 320 | t_guardian *g = scm_gc_malloc (sizeof (t_guardian), "guardian"); |
e46f3fa6 GH |
321 | SCM z1 = scm_cons (SCM_BOOL_F, SCM_EOL); |
322 | SCM z2 = scm_cons (SCM_BOOL_F, SCM_EOL); | |
e1f2bf99 | 323 | SCM z; |
e46f3fa6 | 324 | |
e1f2bf99 MD |
325 | /* A tconc starts out with one tail pair. */ |
326 | g->live.head = g->live.tail = z1; | |
327 | g->zombies.head = g->zombies.tail = z2; | |
56495472 | 328 | |
c0a5d888 | 329 | g->next = NULL; |
23a62151 | 330 | |
01449aa5 | 331 | SCM_NEWSMOB (z, tc16_guardian, g); |
e1f2bf99 | 332 | |
01449aa5 | 333 | return z; |
e1f2bf99 | 334 | } |
1bbd0b84 | 335 | #undef FUNC_NAME |
e1f2bf99 | 336 | |
e1f2bf99 | 337 | void |
56495472 | 338 | scm_init_guardians () |
e1f2bf99 | 339 | { |
01449aa5 DH |
340 | tc16_guardian = scm_make_smob_type ("guardian", 0); |
341 | scm_set_smob_mark (tc16_guardian, guardian_mark); | |
342 | scm_set_smob_free (tc16_guardian, guardian_free); | |
343 | scm_set_smob_print (tc16_guardian, guardian_print); | |
06c1d900 | 344 | #if ENABLE_DEPRECATED |
c0a5d888 | 345 | scm_set_smob_apply (tc16_guardian, guardian_apply, 0, 2, 0); |
06c1d900 MV |
346 | #else |
347 | scm_set_smob_apply (tc16_guardian, guardian_apply, 0, 1, 0); | |
348 | #endif | |
d9dcd933 | 349 | |
a0599745 | 350 | #include "libguile/guardians.x" |
e1f2bf99 | 351 | } |
89e00824 ML |
352 | |
353 | /* | |
354 | Local Variables: | |
355 | c-file-style: "gnu" | |
356 | End: | |
357 | */ |