| 1 | /* Copyright (C) 1998, 1999 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 | |
| 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 | |
| 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 "ports.h" |
| 62 | #include "print.h" |
| 63 | #include "smob.h" |
| 64 | #include "vectors.h" |
| 65 | |
| 66 | #include "validate.h" |
| 67 | #include "guardians.h" |
| 68 | |
| 69 | static long scm_tc16_guardian; |
| 70 | |
| 71 | /* The live and zombies FIFOs are implemented as tconcs as described |
| 72 | in Dybvig's paper. This decouples addition and removal of elements |
| 73 | so that no synchronization between these needs to take place. |
| 74 | */ |
| 75 | #define TCONC_IN(tc, obj, pair) \ |
| 76 | do { \ |
| 77 | SCM_SETCAR ((tc).tail, obj); \ |
| 78 | SCM_SETCAR (pair, SCM_BOOL_F); \ |
| 79 | SCM_SETCDR (pair, SCM_BOOL_F); \ |
| 80 | SCM_SETCDR ((tc).tail, pair); \ |
| 81 | (tc).tail = pair; \ |
| 82 | } while (0) |
| 83 | |
| 84 | #define TCONC_OUT(tc, res) \ |
| 85 | do { \ |
| 86 | (res) = SCM_CAR ((tc).head); \ |
| 87 | (tc).head = SCM_CDR ((tc).head); \ |
| 88 | } while (0) |
| 89 | |
| 90 | #define TCONC_EMPTYP(tc) ((tc).head == (tc).tail) |
| 91 | |
| 92 | typedef struct tconc_t |
| 93 | { |
| 94 | SCM head; |
| 95 | SCM tail; |
| 96 | } tconc_t; |
| 97 | |
| 98 | typedef struct guardian_t |
| 99 | { |
| 100 | tconc_t live; |
| 101 | tconc_t zombies; |
| 102 | struct guardian_t *next; |
| 103 | } guardian_t; |
| 104 | |
| 105 | #define GUARDIAN(x) ((guardian_t *) SCM_CDR (x)) |
| 106 | #define GUARDIAN_LIVE(x) (GUARDIAN (x)->live) |
| 107 | #define GUARDIAN_ZOMBIES(x) (GUARDIAN (x)->zombies) |
| 108 | #define GUARDIAN_NEXT(x) (GUARDIAN (x)->next) |
| 109 | |
| 110 | static guardian_t *first_live_guardian = NULL; |
| 111 | static guardian_t **current_link_field = NULL; |
| 112 | |
| 113 | static SCM |
| 114 | g_mark (SCM ptr) |
| 115 | { |
| 116 | *current_link_field = GUARDIAN (ptr); |
| 117 | current_link_field = &GUARDIAN_NEXT (ptr); |
| 118 | GUARDIAN_NEXT (ptr) = NULL; |
| 119 | |
| 120 | /* Can't mark zombies here since they can refer to objects which are |
| 121 | living dead, thereby preventing them to join the zombies. */ |
| 122 | return SCM_BOOL_F; |
| 123 | } |
| 124 | |
| 125 | static int |
| 126 | g_print (SCM exp, SCM port, scm_print_state *pstate) |
| 127 | { |
| 128 | char buf[256]; |
| 129 | sprintf (buf, "#<guardian live objs: %lu zombies: %lu>", |
| 130 | scm_ilength (SCM_CDR (GUARDIAN_LIVE (exp).head)), |
| 131 | scm_ilength (SCM_CDR (GUARDIAN_ZOMBIES (exp).head))); |
| 132 | scm_puts (buf, port); |
| 133 | |
| 134 | return 1; |
| 135 | } |
| 136 | |
| 137 | #define CCLO_G(cclo) (SCM_VELTS (cclo)[1]) |
| 138 | |
| 139 | static SCM |
| 140 | guard (SCM cclo, SCM arg) |
| 141 | { |
| 142 | if (!SCM_UNBNDP (arg)) |
| 143 | { |
| 144 | scm_guard (cclo, arg); |
| 145 | return SCM_UNSPECIFIED; |
| 146 | } |
| 147 | else |
| 148 | return scm_get_one_zombie (cclo); |
| 149 | } |
| 150 | |
| 151 | static SCM guard1; |
| 152 | |
| 153 | SCM_DEFINE (scm_make_guardian, "make-guardian", 0, 0, 0, |
| 154 | (), |
| 155 | "Return a new guardian object.\n" |
| 156 | "A guardian allows dynamically allocated objects to be\n" |
| 157 | "saved from deallocation by the garbage collector so that\n" |
| 158 | "clean up or other actions can be performed using the data\n" |
| 159 | "stored within the objects.\n" |
| 160 | "See R. Kent Dybvig, Carl Bruggeman, and David Eby (1993)\n" |
| 161 | "\"Guardians in a Generation-Based Garbage Collector\".\n" |
| 162 | "ACM SIGPLAN Conference on Programming Language Design\n" |
| 163 | "and Implementation, June 1993\n.") |
| 164 | #define FUNC_NAME s_scm_make_guardian |
| 165 | { |
| 166 | SCM cclo = scm_makcclo (guard1, 2L); |
| 167 | guardian_t *g = SCM_MUST_MALLOC_TYPE(guardian_t); |
| 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 | /* A tconc starts out with one tail pair. */ |
| 172 | g->live.head = g->live.tail = z1; |
| 173 | g->zombies.head = g->zombies.tail = z2; |
| 174 | |
| 175 | SCM_NEWSMOB (z, scm_tc16_guardian, g); |
| 176 | |
| 177 | CCLO_G (cclo) = z; |
| 178 | |
| 179 | return cclo; |
| 180 | } |
| 181 | #undef FUNC_NAME |
| 182 | |
| 183 | void |
| 184 | scm_guardian_gc_init() |
| 185 | { |
| 186 | current_link_field = &first_live_guardian; |
| 187 | first_live_guardian = NULL; |
| 188 | } |
| 189 | |
| 190 | void |
| 191 | scm_guardian_zombify () |
| 192 | { |
| 193 | guardian_t *g; |
| 194 | |
| 195 | /* Note that new guardians may be stuck on the end of the live |
| 196 | guardian list as we run this loop. As we move unmarked objects |
| 197 | to the zombie list and mark them, we may find some guarded |
| 198 | guardians. The guardian mark function will stick them on the end |
| 199 | of this list, so they'll be processed properly. */ |
| 200 | for (g = first_live_guardian; g; g = g->next) |
| 201 | { |
| 202 | /* Scan the live list for unmarked objects, and move them to the |
| 203 | zombies tconc. */ |
| 204 | SCM tconc_tail = g->live.tail; |
| 205 | SCM *prev_ptr = &g->live.head; |
| 206 | SCM pair = g->live.head; |
| 207 | |
| 208 | while (pair != tconc_tail) |
| 209 | { |
| 210 | SCM next_pair = SCM_CDR (pair); |
| 211 | |
| 212 | if (SCM_NMARKEDP (SCM_CAR (pair))) |
| 213 | { |
| 214 | /* got you, zombie! */ |
| 215 | |
| 216 | /* out of the live list! */ |
| 217 | *prev_ptr = next_pair; |
| 218 | |
| 219 | /* to the zombie list! */ |
| 220 | TCONC_IN (g->zombies, SCM_CAR (pair), pair); |
| 221 | } |
| 222 | else |
| 223 | prev_ptr = SCM_CDRLOC (pair); |
| 224 | |
| 225 | pair = next_pair; |
| 226 | } |
| 227 | |
| 228 | /* Mark the cells of the live list. */ |
| 229 | for (pair = g->live.head; SCM_NIMP (pair); pair = SCM_GCCDR (pair)) |
| 230 | SCM_SETGCMARK (pair); |
| 231 | |
| 232 | /* Bring the zombies back from the dead. */ |
| 233 | scm_gc_mark (g->zombies.head); |
| 234 | } |
| 235 | } |
| 236 | |
| 237 | void |
| 238 | scm_guard (SCM guardian, SCM obj) |
| 239 | { |
| 240 | SCM g = CCLO_G (guardian); |
| 241 | |
| 242 | if (SCM_NIMP (obj)) |
| 243 | { |
| 244 | SCM z; |
| 245 | |
| 246 | SCM_NEWCELL (z); |
| 247 | |
| 248 | /* This critical section barrier will be replaced by a mutex. */ |
| 249 | SCM_DEFER_INTS; |
| 250 | TCONC_IN (GUARDIAN_LIVE (g), obj, z); |
| 251 | SCM_ALLOW_INTS; |
| 252 | } |
| 253 | } |
| 254 | |
| 255 | SCM |
| 256 | scm_get_one_zombie (SCM guardian) |
| 257 | { |
| 258 | SCM g = CCLO_G (guardian); |
| 259 | SCM res = SCM_BOOL_F; |
| 260 | |
| 261 | /* This critical section barrier will be replaced by a mutex. */ |
| 262 | SCM_DEFER_INTS; |
| 263 | if (!TCONC_EMPTYP (GUARDIAN_ZOMBIES (g))) |
| 264 | TCONC_OUT (GUARDIAN_ZOMBIES (g), res); |
| 265 | SCM_ALLOW_INTS; |
| 266 | |
| 267 | return res; |
| 268 | } |
| 269 | |
| 270 | void |
| 271 | scm_init_guardian() |
| 272 | { |
| 273 | scm_tc16_guardian = scm_make_smob_type_mfpe ("guardian", sizeof (guardian_t), |
| 274 | g_mark, NULL, g_print, NULL); |
| 275 | guard1 = scm_make_subr_opt ("guardian", scm_tc7_subr_2o, guard, 0); |
| 276 | |
| 277 | #include "guardians.x" |
| 278 | } |
| 279 | |
| 280 | /* |
| 281 | Local Variables: |
| 282 | c-file-style: "gnu" |
| 283 | End: |
| 284 | */ |