Commit | Line | Data |
---|---|---|
ac51e74b | 1 | /* Copyright (C) 1995,1996,1997,1998,1999,2000,2001, 2002, 2003, 2004, 2005, 2006, 2009 Free Software Foundation, Inc. |
c7743d02 | 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. | |
c7743d02 | 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. | |
c7743d02 | 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 | */ |
c7743d02 HWN |
18 | |
19 | ||
20 | \f | |
dbb605f5 | 21 | #ifdef HAVE_CONFIG_H |
3ba436c8 RB |
22 | # include <config.h> |
23 | #endif | |
24 | ||
c7743d02 HWN |
25 | #include <stdio.h> |
26 | #include <errno.h> | |
27 | #include <string.h> | |
28 | #include <assert.h> | |
29 | ||
30 | #ifdef __ia64__ | |
31 | #include <ucontext.h> | |
32 | extern unsigned long * __libc_ia64_register_backing_store_base; | |
33 | #endif | |
34 | ||
35 | #include "libguile/_scm.h" | |
36 | #include "libguile/eval.h" | |
37 | #include "libguile/stime.h" | |
38 | #include "libguile/stackchk.h" | |
39 | #include "libguile/struct.h" | |
40 | #include "libguile/smob.h" | |
41 | #include "libguile/unif.h" | |
42 | #include "libguile/async.h" | |
2fb924f6 | 43 | #include "libguile/programs.h" |
c7743d02 HWN |
44 | #include "libguile/ports.h" |
45 | #include "libguile/root.h" | |
46 | #include "libguile/strings.h" | |
47 | #include "libguile/vectors.h" | |
48 | #include "libguile/weaks.h" | |
49 | #include "libguile/hashtab.h" | |
50 | #include "libguile/tags.h" | |
51 | #include "libguile/private-gc.h" | |
52 | #include "libguile/validate.h" | |
53 | #include "libguile/deprecation.h" | |
54 | #include "libguile/gc.h" | |
06c1d900 | 55 | #include "libguile/guardians.h" |
c7743d02 HWN |
56 | |
57 | #ifdef GUILE_DEBUG_MALLOC | |
58 | #include "libguile/debug-malloc.h" | |
59 | #endif | |
60 | ||
61 | #ifdef HAVE_MALLOC_H | |
62 | #include <malloc.h> | |
63 | #endif | |
64 | ||
65 | #ifdef HAVE_UNISTD_H | |
66 | #include <unistd.h> | |
67 | #endif | |
68 | ||
6cc323e2 LC |
69 | int scm_i_marking = 0; |
70 | ||
c7743d02 HWN |
71 | /* |
72 | Entry point for this file. | |
73 | */ | |
74 | void | |
75 | scm_mark_all (void) | |
76 | { | |
77 | long j; | |
71c7cfa5 | 78 | int loops; |
06c1d900 | 79 | |
d09752ff | 80 | scm_i_marking = 1; |
06c1d900 MV |
81 | scm_i_init_weak_vectors_for_gc (); |
82 | scm_i_init_guardians_for_gc (); | |
c7743d02 HWN |
83 | |
84 | scm_i_clear_mark_space (); | |
40945e5e | 85 | scm_i_find_heap_calls = 0; |
c7743d02 HWN |
86 | /* Mark every thread's stack and registers */ |
87 | scm_threads_mark_stacks (); | |
88 | ||
c7743d02 HWN |
89 | j = SCM_NUM_PROTECTS; |
90 | while (j--) | |
91 | scm_gc_mark (scm_sys_protects[j]); | |
92 | ||
93 | /* mark the registered roots */ | |
94 | { | |
95 | size_t i; | |
c35738c1 | 96 | for (i = 0; i < SCM_HASHTABLE_N_BUCKETS (scm_gc_registered_roots); ++i) |
c7743d02 | 97 | { |
4057a3e0 | 98 | SCM l = SCM_HASHTABLE_BUCKET (scm_gc_registered_roots, i); |
d2e53ed6 | 99 | for (; !scm_is_null (l); l = SCM_CDR (l)) |
c7743d02 | 100 | { |
b9bd8526 | 101 | SCM *p = (SCM *) (scm_to_ulong (SCM_CAAR (l))); |
c7743d02 HWN |
102 | scm_gc_mark (*p); |
103 | } | |
104 | } | |
105 | } | |
06c1d900 | 106 | |
71c7cfa5 | 107 | loops = 0; |
06c1d900 MV |
108 | while (1) |
109 | { | |
06c1d900 | 110 | int again; |
71c7cfa5 | 111 | loops++; |
06c1d900 MV |
112 | |
113 | /* Mark the non-weak references of weak vectors. For a weak key | |
114 | alist vector, this would mark the values for keys that are | |
115 | marked. We need to do this in a loop until everything | |
116 | settles down since the newly marked values might be keys in | |
117 | other weak key alist vectors, for example. | |
118 | */ | |
119 | again = scm_i_mark_weak_vectors_non_weaks (); | |
120 | if (again) | |
121 | continue; | |
122 | ||
123 | /* Now we scan all marked guardians and move all unmarked objects | |
124 | from the accessible to the inaccessible list. | |
125 | */ | |
126 | scm_i_identify_inaccessible_guardeds (); | |
127 | ||
128 | /* When we have identified all inaccessible objects, we can mark | |
129 | them. | |
130 | */ | |
131 | again = scm_i_mark_inaccessible_guardeds (); | |
132 | ||
133 | /* This marking might have changed the situation for weak vectors | |
134 | and might have turned up new guardians that need to be processed, | |
135 | so we do it all over again. | |
136 | */ | |
137 | if (again) | |
138 | continue; | |
139 | ||
140 | /* Nothing new marked in this round, we are done. | |
141 | */ | |
142 | break; | |
143 | } | |
144 | ||
06c1d900 | 145 | /* Remove all unmarked entries from the weak vectors. |
c7743d02 | 146 | */ |
06c1d900 MV |
147 | scm_i_remove_weaks_from_weak_vectors (); |
148 | ||
149 | /* Bring hashtables upto date. | |
150 | */ | |
151 | scm_i_scan_weak_hashtables (); | |
d09752ff | 152 | scm_i_marking = 0; |
c7743d02 HWN |
153 | } |
154 | ||
155 | /* {Mark/Sweep} | |
156 | */ | |
157 | ||
c7743d02 HWN |
158 | /* |
159 | Mark an object precisely, then recurse. | |
160 | */ | |
161 | void | |
162 | scm_gc_mark (SCM ptr) | |
163 | { | |
164 | if (SCM_IMP (ptr)) | |
45a1c3e8 | 165 | return; |
c7743d02 HWN |
166 | |
167 | if (SCM_GC_MARK_P (ptr)) | |
45a1c3e8 | 168 | return; |
c7743d02 | 169 | |
7ddb9baf HWN |
170 | if (!scm_i_marking) |
171 | { | |
172 | static const char msg[] | |
173 | = "Should only call scm_gc_mark() during GC."; | |
174 | scm_c_issue_deprecation_warning (msg); | |
175 | } | |
176 | ||
c7743d02 HWN |
177 | SCM_SET_GC_MARK (ptr); |
178 | scm_gc_mark_dependencies (ptr); | |
179 | } | |
180 | ||
d09752ff | 181 | void |
7ddb9baf | 182 | scm_i_ensure_marking (void) |
d09752ff HWN |
183 | { |
184 | assert (scm_i_marking); | |
185 | } | |
186 | ||
c7743d02 HWN |
187 | /* |
188 | ||
189 | Mark the dependencies of an object. | |
190 | ||
33138b05 | 191 | Prefetching: |
c7743d02 HWN |
192 | |
193 | Should prefetch objects before marking, i.e. if marking a cell, we | |
194 | should prefetch the car, and then mark the cdr. This will improve CPU | |
82ae1b8e | 195 | cache misses, because the car is more likely to be in cache when we |
c7743d02 HWN |
196 | finish the cdr. |
197 | ||
198 | See http://www.hpl.hp.com/techreports/2000/HPL-2000-99.pdf, reducing | |
199 | garbage collector cache misses. | |
200 | ||
201 | Prefetch is supported on GCC >= 3.1 | |
202 | ||
33138b05 HWN |
203 | (Some time later.) |
204 | ||
205 | Tried this with GCC 3.1.1 -- the time differences are barely measurable. | |
206 | Perhaps this would work better with an explicit markstack? | |
207 | ||
208 | ||
209 | */ | |
06c1d900 | 210 | |
c7743d02 HWN |
211 | void |
212 | scm_gc_mark_dependencies (SCM p) | |
213 | #define FUNC_NAME "scm_gc_mark_dependencies" | |
214 | { | |
215 | register long i; | |
216 | register SCM ptr; | |
702551e6 | 217 | SCM cell_type; |
c7743d02 HWN |
218 | |
219 | ptr = p; | |
220 | scm_mark_dependencies_again: | |
76da80e7 | 221 | |
c7743d02 HWN |
222 | cell_type = SCM_GC_CELL_TYPE (ptr); |
223 | switch (SCM_ITAG7 (cell_type)) | |
224 | { | |
225 | case scm_tcs_cons_nimcar: | |
226 | if (SCM_IMP (SCM_CDR (ptr))) | |
227 | { | |
228 | ptr = SCM_CAR (ptr); | |
229 | goto gc_mark_nimp; | |
230 | } | |
33138b05 HWN |
231 | |
232 | ||
c7743d02 HWN |
233 | scm_gc_mark (SCM_CAR (ptr)); |
234 | ptr = SCM_CDR (ptr); | |
235 | goto gc_mark_nimp; | |
236 | case scm_tcs_cons_imcar: | |
237 | ptr = SCM_CDR (ptr); | |
238 | goto gc_mark_loop; | |
239 | case scm_tc7_pws: | |
33138b05 | 240 | |
c7743d02 HWN |
241 | scm_gc_mark (SCM_SETTER (ptr)); |
242 | ptr = SCM_PROCEDURE (ptr); | |
243 | goto gc_mark_loop; | |
244 | case scm_tcs_struct: | |
245 | { | |
246 | /* XXX - use less explicit code. */ | |
247 | scm_t_bits word0 = SCM_CELL_WORD_0 (ptr) - scm_tc3_struct; | |
248 | scm_t_bits * vtable_data = (scm_t_bits *) word0; | |
249 | SCM layout = SCM_PACK (vtable_data [scm_vtable_index_layout]); | |
eb01cb64 MV |
250 | long len = scm_i_symbol_length (layout); |
251 | const char *fields_desc = scm_i_symbol_chars (layout); | |
252 | scm_t_bits *struct_data = (scm_t_bits *) SCM_STRUCT_DATA (ptr); | |
c7743d02 HWN |
253 | |
254 | if (vtable_data[scm_struct_i_flags] & SCM_STRUCTF_ENTITY) | |
255 | { | |
256 | scm_gc_mark (SCM_PACK (struct_data[scm_struct_i_procedure])); | |
257 | scm_gc_mark (SCM_PACK (struct_data[scm_struct_i_setter])); | |
258 | } | |
259 | if (len) | |
260 | { | |
261 | long x; | |
262 | ||
263 | for (x = 0; x < len - 2; x += 2, ++struct_data) | |
264 | if (fields_desc[x] == 'p') | |
265 | scm_gc_mark (SCM_PACK (*struct_data)); | |
266 | if (fields_desc[x] == 'p') | |
267 | { | |
268 | if (SCM_LAYOUT_TAILP (fields_desc[x + 1])) | |
269 | for (x = *struct_data++; x; --x, ++struct_data) | |
270 | scm_gc_mark (SCM_PACK (*struct_data)); | |
271 | else | |
272 | scm_gc_mark (SCM_PACK (*struct_data)); | |
273 | } | |
274 | } | |
275 | /* mark vtable */ | |
276 | ptr = SCM_PACK (vtable_data [scm_vtable_index_vtable]); | |
277 | goto gc_mark_loop; | |
278 | } | |
279 | break; | |
280 | case scm_tcs_closures: | |
281 | if (SCM_IMP (SCM_ENV (ptr))) | |
282 | { | |
283 | ptr = SCM_CLOSCAR (ptr); | |
284 | goto gc_mark_nimp; | |
285 | } | |
286 | scm_gc_mark (SCM_CLOSCAR (ptr)); | |
287 | ptr = SCM_ENV (ptr); | |
288 | goto gc_mark_nimp; | |
2fb924f6 AW |
289 | case scm_tc7_program: |
290 | if (SCM_PROGRAM_FREE_VARIABLES (ptr) != SCM_BOOL_F) | |
291 | scm_gc_mark (SCM_PROGRAM_FREE_VARIABLES (ptr)); | |
292 | if (SCM_PROGRAM_OBJTABLE (ptr) != SCM_BOOL_F) | |
293 | scm_gc_mark (SCM_PROGRAM_OBJTABLE (ptr)); | |
294 | ptr = SCM_PROGRAM_OBJCODE (ptr); | |
295 | goto gc_mark_nimp; | |
c7743d02 | 296 | case scm_tc7_vector: |
4057a3e0 | 297 | i = SCM_SIMPLE_VECTOR_LENGTH (ptr); |
c7743d02 HWN |
298 | if (i == 0) |
299 | break; | |
300 | while (--i > 0) | |
33138b05 | 301 | { |
4057a3e0 MV |
302 | SCM elt = SCM_SIMPLE_VECTOR_REF (ptr, i); |
303 | if (SCM_NIMP (elt)) | |
304 | scm_gc_mark (elt); | |
33138b05 | 305 | } |
4057a3e0 | 306 | ptr = SCM_SIMPLE_VECTOR_REF (ptr, 0); |
c7743d02 | 307 | goto gc_mark_loop; |
eb01cb64 | 308 | |
c7743d02 | 309 | case scm_tc7_string: |
eb01cb64 MV |
310 | ptr = scm_i_string_mark (ptr); |
311 | goto gc_mark_loop; | |
312 | case scm_tc7_stringbuf: | |
313 | ptr = scm_i_stringbuf_mark (ptr); | |
314 | goto gc_mark_loop; | |
c7743d02 | 315 | |
534c55a9 | 316 | case scm_tc7_number: |
f92e85f7 MV |
317 | if (SCM_TYP16 (ptr) == scm_tc16_fraction) |
318 | { | |
319 | scm_gc_mark (SCM_CELL_OBJECT_1 (ptr)); | |
320 | ptr = SCM_CELL_OBJECT_2 (ptr); | |
321 | goto gc_mark_loop; | |
322 | } | |
534c55a9 DH |
323 | break; |
324 | ||
c7743d02 | 325 | case scm_tc7_wvect: |
06c1d900 | 326 | scm_i_mark_weak_vector (ptr); |
c7743d02 HWN |
327 | break; |
328 | ||
329 | case scm_tc7_symbol: | |
eb01cb64 | 330 | ptr = scm_i_symbol_mark (ptr); |
c7743d02 HWN |
331 | goto gc_mark_loop; |
332 | case scm_tc7_variable: | |
333 | ptr = SCM_CELL_OBJECT_1 (ptr); | |
334 | goto gc_mark_loop; | |
335 | case scm_tcs_subrs: | |
325226da AW |
336 | if (SCM_CELL_WORD_2 (ptr) && *(SCM*)SCM_CELL_WORD_2 (ptr)) |
337 | /* the generic associated with this primitive */ | |
338 | scm_gc_mark (*(SCM*)SCM_CELL_WORD_2 (ptr)); | |
339 | if (SCM_NIMP (((SCM*)SCM_CELL_WORD_3 (ptr))[1])) | |
340 | scm_gc_mark (((SCM*)SCM_CELL_WORD_3 (ptr))[1]); /* props */ | |
341 | ptr = ((SCM*)SCM_CELL_WORD_3 (ptr))[0]; /* name */ | |
342 | goto gc_mark_loop; | |
c7743d02 HWN |
343 | case scm_tc7_port: |
344 | i = SCM_PTOBNUM (ptr); | |
345 | #if (SCM_DEBUG_CELL_ACCESSES == 1) | |
346 | if (!(i < scm_numptob)) | |
be3ff021 HWN |
347 | { |
348 | fprintf (stderr, "undefined port type"); | |
1f584400 | 349 | abort (); |
be3ff021 | 350 | } |
c7743d02 | 351 | #endif |
1f584400 | 352 | if (SCM_PTAB_ENTRY (ptr)) |
c7743d02 HWN |
353 | scm_gc_mark (SCM_FILENAME (ptr)); |
354 | if (scm_ptobs[i].mark) | |
355 | { | |
356 | ptr = (scm_ptobs[i].mark) (ptr); | |
357 | goto gc_mark_loop; | |
358 | } | |
359 | else | |
360 | return; | |
361 | break; | |
362 | case scm_tc7_smob: | |
363 | switch (SCM_TYP16 (ptr)) | |
364 | { /* should be faster than going through scm_smobs */ | |
365 | case scm_tc_free_cell: | |
366 | /* We have detected a free cell. This can happen if non-object data | |
367 | * on the C stack points into guile's heap and is scanned during | |
368 | * conservative marking. */ | |
369 | break; | |
c7743d02 HWN |
370 | default: |
371 | i = SCM_SMOBNUM (ptr); | |
372 | #if (SCM_DEBUG_CELL_ACCESSES == 1) | |
373 | if (!(i < scm_numsmob)) | |
be3ff021 HWN |
374 | { |
375 | fprintf (stderr, "undefined smob type"); | |
1f584400 | 376 | abort (); |
be3ff021 | 377 | } |
c7743d02 HWN |
378 | #endif |
379 | if (scm_smobs[i].mark) | |
380 | { | |
381 | ptr = (scm_smobs[i].mark) (ptr); | |
382 | goto gc_mark_loop; | |
383 | } | |
384 | else | |
385 | return; | |
386 | } | |
387 | break; | |
388 | default: | |
be3ff021 | 389 | fprintf (stderr, "unknown type"); |
1f584400 | 390 | abort (); |
c7743d02 HWN |
391 | } |
392 | ||
393 | /* | |
394 | If we got here, then exhausted recursion options for PTR. we | |
395 | return (careful not to mark PTR, it might be the argument that we | |
396 | were called with.) | |
397 | */ | |
398 | return ; | |
06c1d900 MV |
399 | |
400 | gc_mark_loop: | |
c7743d02 HWN |
401 | if (SCM_IMP (ptr)) |
402 | return; | |
403 | ||
404 | gc_mark_nimp: | |
405 | { | |
406 | int valid_cell = CELL_P (ptr); | |
407 | ||
408 | ||
409 | #if (SCM_DEBUG_CELL_ACCESSES == 1) | |
410 | if (scm_debug_cell_accesses_p) | |
411 | { | |
412 | /* We are in debug mode. Check the ptr exhaustively. */ | |
413 | ||
40945e5e | 414 | valid_cell = valid_cell && scm_in_heap_p (ptr); |
c7743d02 HWN |
415 | } |
416 | ||
417 | #endif | |
418 | if (!valid_cell) | |
be3ff021 HWN |
419 | { |
420 | fprintf (stderr, "rogue pointer in heap"); | |
1f584400 | 421 | abort (); |
be3ff021 | 422 | } |
c7743d02 | 423 | } |
eab1b259 | 424 | |
82ae1b8e | 425 | if (SCM_GC_MARK_P (ptr)) |
76da80e7 | 426 | return; |
a54a94b3 | 427 | |
76da80e7 | 428 | SCM_SET_GC_MARK (ptr); |
eab1b259 | 429 | |
76da80e7 | 430 | goto scm_mark_dependencies_again; |
c7743d02 HWN |
431 | |
432 | } | |
433 | #undef FUNC_NAME | |
434 | ||
435 | ||
c7743d02 HWN |
436 | /* Mark a region conservatively */ |
437 | void | |
438 | scm_mark_locations (SCM_STACKITEM x[], unsigned long n) | |
439 | { | |
440 | unsigned long m; | |
441 | ||
442 | for (m = 0; m < n; ++m) | |
443 | { | |
444 | SCM obj = * (SCM *) &x[m]; | |
445 | long int segment = scm_i_find_heap_segment_containing_object (obj); | |
446 | if (segment >= 0) | |
447 | scm_gc_mark (obj); | |
448 | } | |
449 | } | |
450 | ||
451 | ||
452 | /* The function scm_in_heap_p determines whether an SCM value can be regarded as a | |
453 | * pointer to a cell on the heap. | |
454 | */ | |
455 | int | |
456 | scm_in_heap_p (SCM value) | |
457 | { | |
458 | long int segment = scm_i_find_heap_segment_containing_object (value); | |
459 | return (segment >= 0); | |
460 | } | |
461 | ||
462 | ||
463 | #if SCM_ENABLE_DEPRECATED == 1 | |
464 | ||
465 | /* If an allocated cell is detected during garbage collection, this | |
466 | * means that some code has just obtained the object but was preempted | |
467 | * before the initialization of the object was completed. This meanst | |
468 | * that some entries of the allocated cell may already contain SCM | |
469 | * objects. Therefore, allocated cells are scanned conservatively. | |
470 | */ | |
471 | ||
472 | scm_t_bits scm_tc16_allocated; | |
473 | ||
474 | static SCM | |
475 | allocated_mark (SCM cell) | |
476 | { | |
477 | unsigned long int cell_segment = scm_i_find_heap_segment_containing_object (cell); | |
478 | unsigned int span = scm_i_heap_segment_table[cell_segment]->span; | |
479 | unsigned int i; | |
480 | ||
481 | for (i = 1; i != span * 2; ++i) | |
482 | { | |
483 | SCM obj = SCM_CELL_OBJECT (cell, i); | |
484 | long int obj_segment = scm_i_find_heap_segment_containing_object (obj); | |
485 | if (obj_segment >= 0) | |
486 | scm_gc_mark (obj); | |
487 | } | |
488 | return SCM_BOOL_F; | |
489 | } | |
490 | ||
491 | SCM | |
492 | scm_deprecated_newcell (void) | |
493 | { | |
494 | scm_c_issue_deprecation_warning | |
495 | ("SCM_NEWCELL is deprecated. Use `scm_cell' instead.\n"); | |
496 | ||
497 | return scm_cell (scm_tc16_allocated, 0); | |
498 | } | |
499 | ||
500 | SCM | |
501 | scm_deprecated_newcell2 (void) | |
502 | { | |
503 | scm_c_issue_deprecation_warning | |
504 | ("SCM_NEWCELL2 is deprecated. Use `scm_double_cell' instead.\n"); | |
505 | ||
506 | return scm_double_cell (scm_tc16_allocated, 0, 0, 0); | |
507 | } | |
508 | ||
509 | #endif /* SCM_ENABLE_DEPRECATED == 1 */ | |
510 | ||
511 | ||
512 | void | |
1f584400 | 513 | scm_gc_init_mark (void) |
c7743d02 HWN |
514 | { |
515 | #if SCM_ENABLE_DEPRECATED == 1 | |
516 | scm_tc16_allocated = scm_make_smob_type ("allocated cell", 0); | |
517 | scm_set_smob_mark (scm_tc16_allocated, allocated_mark); | |
518 | #endif | |
519 | } | |
520 |