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. */ | |
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 | ||
e1f2bf99 MD |
119 | static int |
120 | g_print (SCM exp, SCM port, scm_print_state *pstate) | |
121 | { | |
122 | char buf[256]; | |
123 | sprintf (buf, "#<guardian live objs: %lu zombies: %lu>", | |
124 | scm_ilength (SCM_CDR (GUARDIAN_LIVE (exp).head)), | |
125 | scm_ilength (SCM_CDR (GUARDIAN_ZOMBIES (exp).head))); | |
126 | scm_puts (buf, port); | |
127 | ||
128 | return 1; | |
129 | } | |
130 | ||
e1f2bf99 MD |
131 | #define CCLO_G(cclo) (SCM_VELTS (cclo)[1]) |
132 | ||
133 | static SCM | |
134 | guard (SCM cclo, SCM arg) | |
135 | { | |
136 | if (!SCM_UNBNDP (arg)) | |
137 | { | |
138 | scm_guard (cclo, arg); | |
139 | return SCM_UNSPECIFIED; | |
140 | } | |
141 | else | |
142 | return scm_get_one_zombie (cclo); | |
143 | } | |
144 | ||
145 | static SCM guard1; | |
146 | ||
147 | SCM_PROC (s_make_guardian, "make-guardian", 0, 0, 0, scm_make_guardian); | |
148 | SCM | |
149 | scm_make_guardian () | |
150 | { | |
151 | SCM cclo = scm_makcclo (guard1, 2L); | |
152 | guardian_t *g = (guardian_t *) scm_must_malloc (sizeof (guardian_t), | |
153 | s_make_guardian); | |
154 | SCM z1 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); | |
155 | SCM z2 = scm_cons (SCM_BOOL_F, SCM_BOOL_F); | |
156 | SCM z; | |
e1f2bf99 MD |
157 | /* A tconc starts out with one tail pair. */ |
158 | g->live.head = g->live.tail = z1; | |
159 | g->zombies.head = g->zombies.tail = z2; | |
23a62151 MD |
160 | |
161 | SCM_NEWSMOB (z, scm_tc16_guardian, g); | |
e1f2bf99 MD |
162 | |
163 | CCLO_G (cclo) = z; | |
164 | ||
165 | return cclo; | |
166 | } | |
167 | ||
168 | void | |
169 | scm_guardian_gc_init() | |
170 | { | |
01a119ac JB |
171 | current_link_field = &first_live_guardian; |
172 | first_live_guardian = NULL; | |
e1f2bf99 MD |
173 | } |
174 | ||
175 | void | |
176 | scm_guardian_zombify () | |
177 | { | |
01a119ac | 178 | guardian_t *g; |
55b7e0bd JB |
179 | |
180 | /* Note that new guardians may be stuck on the end of the live | |
181 | guardian list as we run this loop. As we move unmarked objects | |
182 | to the zombie list and mark them, we may find some guarded | |
183 | guardians. The guardian mark function will stick them on the end | |
184 | of this list, so they'll be processed properly. */ | |
01a119ac | 185 | for (g = first_live_guardian; g; g = g->next) |
e1f2bf99 | 186 | { |
67b2561b JB |
187 | /* Scan the live list for unmarked objects, and move them to the |
188 | zombies tconc. */ | |
01a119ac | 189 | SCM tconc_tail = g->live.tail; |
67b2561b | 190 | SCM *prev_ptr = &g->live.head; |
01a119ac | 191 | SCM pair = g->live.head; |
67b2561b | 192 | |
e1f2bf99 MD |
193 | while (pair != tconc_tail) |
194 | { | |
195 | SCM next_pair = SCM_CDR (pair); | |
196 | ||
197 | if (SCM_NMARKEDP (SCM_CAR (pair))) | |
198 | { | |
199 | /* got you, zombie! */ | |
200 | ||
201 | /* out of the live list! */ | |
67b2561b | 202 | *prev_ptr = next_pair; |
e1f2bf99 MD |
203 | |
204 | /* to the zombie list! */ | |
01a119ac | 205 | TCONC_IN (g->zombies, SCM_CAR (pair), pair); |
e1f2bf99 MD |
206 | } |
207 | else | |
67b2561b | 208 | prev_ptr = SCM_CDRLOC (pair); |
e1f2bf99 MD |
209 | |
210 | pair = next_pair; | |
211 | } | |
67b2561b JB |
212 | |
213 | /* Mark the cells of the live list. */ | |
214 | for (pair = g->live.head; SCM_NIMP (pair); pair = SCM_GCCDR (pair)) | |
215 | SCM_SETGCMARK (pair); | |
55b7e0bd JB |
216 | |
217 | /* Bring the zombies back from the dead. */ | |
01a119ac | 218 | scm_gc_mark (g->zombies.head); |
e1f2bf99 MD |
219 | } |
220 | } | |
221 | ||
222 | void | |
223 | scm_guard (SCM guardian, SCM obj) | |
224 | { | |
225 | SCM g = CCLO_G (guardian); | |
226 | ||
227 | if (SCM_NIMP (obj)) | |
228 | { | |
229 | SCM z; | |
230 | ||
231 | SCM_NEWCELL (z); | |
232 | ||
233 | /* This critical section barrier will be replaced by a mutex. */ | |
234 | SCM_DEFER_INTS; | |
235 | TCONC_IN (GUARDIAN_LIVE (g), obj, z); | |
236 | SCM_ALLOW_INTS; | |
237 | } | |
238 | } | |
239 | ||
240 | SCM | |
241 | scm_get_one_zombie (SCM guardian) | |
242 | { | |
243 | SCM g = CCLO_G (guardian); | |
244 | SCM res = SCM_BOOL_F; | |
245 | ||
246 | /* This critical section barrier will be replaced by a mutex. */ | |
247 | SCM_DEFER_INTS; | |
248 | if (!TCONC_EMPTYP (GUARDIAN_ZOMBIES (g))) | |
249 | TCONC_OUT (GUARDIAN_ZOMBIES (g), res); | |
250 | SCM_ALLOW_INTS; | |
251 | ||
252 | return res; | |
253 | } | |
254 | ||
255 | void | |
256 | scm_init_guardian() | |
257 | { | |
23a62151 MD |
258 | scm_tc16_guardian = scm_make_smob_type_mfpe ("guardian", sizeof (guardian_t), |
259 | g_mark, NULL, g_print, NULL); | |
e1f2bf99 MD |
260 | guard1 = scm_make_subr_opt ("guardian", scm_tc7_subr_2o, guard, 0); |
261 | ||
262 | #include "guardians.x" | |
263 | } |