6 /* Copyright (C) 1995,1996,1998,1999,2000,2001, 2002, 2003, 2004, 2006, 2008 Free Software Foundation, Inc.
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 #include "libguile/__scm.h"
27 #include "libguile/hooks.h"
28 #include "libguile/threads.h"
32 /* Cell allocation and garbage collection work rouhgly in the
35 Each thread has a 'freelist', which is a list of available cells.
36 (It actually has two freelists, one for single cells and one for
37 double cells. Everything works analogous for double cells.)
39 When a thread wants to allocate a cell and the freelist is empty,
40 it refers to a global list of unswept 'cards'. A card is a small
41 block of cells that are contigous in memory, together with the
42 corresponding mark bits. A unswept card is one where the mark bits
43 are set for cells that have been in use during the last global mark
44 phase, but the unmarked cells of the card have not been scanned and
47 The thread takes one of the unswept cards and sweeps it, thereby
48 building a new freelist that it then uses. Sweeping a card will
49 call the smob free functions of unmarked cells, for example, and
50 thus, these free functions can run at any time, in any thread.
52 When there are no more unswept cards available, the thread performs
53 a global garbage collection. For this, all other threads are
54 stopped. A global mark is performed and all cards are put into the
55 global list of unswept cards. Whennecessary, new cards are
56 allocated and initialized at this time. The other threads are then
60 typedef struct scm_t_cell
69 A card is a small `page' of memory; it will be the unit for lazy
70 sweeping, generations, etc. The first cell of a card contains a
71 pointer to the mark bitvector, so that we can find the bitvector
72 efficiently: we knock off some lowerorder bits.
74 The size on a 32 bit machine is 256 cells = 2kb. The card [XXX]
79 /* Cray machines have pointers that are incremented once for each
80 * word, rather than each byte, the 3 most significant bits encode the
81 * byte within the word. The following macros deal with this by
82 * storing the native Cray pointers like the ones that looks like scm
83 * expects. This is done for any pointers that point to a cell,
84 * pointers to scm_vector elts, functions, &c are not munged.
87 # define SCM2PTR(x) ((scm_t_cell *) (SCM_UNPACK (x) >> 3))
88 # define PTR2SCM(x) (SCM_PACK (((scm_t_bits) (x)) << 3))
90 # define SCM2PTR(x) ((scm_t_cell *) (SCM_UNPACK (x)))
91 # define PTR2SCM(x) (SCM_PACK ((scm_t_bits) (x)))
92 #endif /* def _UNICOS */
95 #define SCM_GC_CARD_N_HEADER_CELLS 1
96 #define SCM_GC_CARD_N_CELLS 256
97 #define SCM_GC_SIZEOF_CARD SCM_GC_CARD_N_CELLS * sizeof (scm_t_cell)
99 #define SCM_GC_CARD_BVEC(card) ((scm_t_c_bvec_long *) ((card)->word_0))
100 #define SCM_GC_SET_CARD_BVEC(card, bvec) \
101 ((card)->word_0 = (SCM) (bvec))
102 #define SCM_GC_GET_CARD_FLAGS(card) ((long) ((card)->word_1))
103 #define SCM_GC_SET_CARD_FLAGS(card, flags) \
104 ((card)->word_1 = (SCM) (flags))
106 #define SCM_GC_GET_CARD_FLAG(card, shift) \
107 (SCM_GC_GET_CARD_FLAGS (card) & (1L << (shift)))
108 #define SCM_GC_SET_CARD_FLAG(card, shift) \
109 (SCM_GC_SET_CARD_FLAGS (card, SCM_GC_GET_CARD_FLAGS(card) | (1L << (shift))))
110 #define SCM_GC_CLEAR_CARD_FLAG(card, shift) \
111 (SCM_GC_SET_CARD_FLAGS (card, SCM_GC_GET_CARD_FLAGS(card) & ~(1L << (shift))))
114 Remove card flags. They hamper lazy initialization, and aren't used
118 /* card addressing. for efficiency, cards are *always* aligned to
121 #define SCM_GC_CARD_SIZE_MASK (SCM_GC_SIZEOF_CARD-1)
122 #define SCM_GC_CARD_ADDR_MASK (~SCM_GC_CARD_SIZE_MASK)
124 #define SCM_GC_CELL_CARD(x) ((scm_t_cell *) ((long) (x) & SCM_GC_CARD_ADDR_MASK))
125 #define SCM_GC_CELL_OFFSET(x) (((long) (x) & SCM_GC_CARD_SIZE_MASK) >> SCM_CELL_SIZE_SHIFT)
126 #define SCM_GC_CELL_BVEC(x) SCM_GC_CARD_BVEC (SCM_GC_CELL_CARD (x))
127 #define SCM_GC_SET_CELL_BVEC(x, bvec) SCM_GC_SET_CARD_BVEC (SCM_GC_CELL_CARD (x), bvec)
128 #define SCM_GC_CELL_GET_BIT(x) SCM_C_BVEC_GET (SCM_GC_CELL_BVEC (x), SCM_GC_CELL_OFFSET (x))
129 #define SCM_GC_CELL_SET_BIT(x) SCM_C_BVEC_SET (SCM_GC_CELL_BVEC (x), SCM_GC_CELL_OFFSET (x))
130 #define SCM_GC_CELL_CLEAR_BIT(x) SCM_C_BVEC_CLEAR (SCM_GC_CELL_BVEC (x), SCM_GC_CELL_OFFSET (x))
132 #define SCM_GC_CARD_UP(x) SCM_GC_CELL_CARD ((char *) (x) + SCM_GC_SIZEOF_CARD - 1)
133 #define SCM_GC_CARD_DOWN SCM_GC_CELL_CARD
135 /* low level bit banging aids */
136 typedef unsigned long scm_t_c_bvec_long
;
138 #if (SCM_SIZEOF_UNSIGNED_LONG == 8)
139 # define SCM_C_BVEC_LONG_BITS 64
140 # define SCM_C_BVEC_OFFSET_SHIFT 6
141 # define SCM_C_BVEC_POS_MASK 63
142 # define SCM_CELL_SIZE_SHIFT 4
144 # define SCM_C_BVEC_LONG_BITS 32
145 # define SCM_C_BVEC_OFFSET_SHIFT 5
146 # define SCM_C_BVEC_POS_MASK 31
147 # define SCM_CELL_SIZE_SHIFT 3
150 #define SCM_C_BVEC_OFFSET(pos) (pos >> SCM_C_BVEC_OFFSET_SHIFT)
152 #define SCM_C_BVEC_GET(bvec, pos) (bvec[SCM_C_BVEC_OFFSET (pos)] & (1L << (pos & SCM_C_BVEC_POS_MASK)))
153 #define SCM_C_BVEC_SET(bvec, pos) (bvec[SCM_C_BVEC_OFFSET (pos)] |= (1L << (pos & SCM_C_BVEC_POS_MASK)))
154 #define SCM_C_BVEC_CLEAR(bvec, pos) (bvec[SCM_C_BVEC_OFFSET (pos)] &= ~(1L << (pos & SCM_C_BVEC_POS_MASK)))
156 /* testing and changing GC marks */
157 #define SCM_GC_MARK_P(x) SCM_GC_CELL_GET_BIT (x)
159 SCM_INTERNAL
void scm_i_ensure_marking(void);
161 #if (SCM_DEBUG_MARKING_API == 1)
162 #define SCM_I_ENSURE_MARKING scm_i_ensure_marking(),
164 #define SCM_I_ENSURE_MARKING
167 #define SCM_SET_GC_MARK(x) SCM_I_ENSURE_MARKING SCM_GC_CELL_SET_BIT (x)
168 #define SCM_CLEAR_GC_MARK(x) SCM_I_ENSURE_MARKING SCM_GC_CELL_CLEAR_BIT (x)
170 /* Low level cell data accessing macros. These macros should only be used
171 * from within code related to garbage collection issues, since they will
172 * never check the cells they are applied to - not even if guile is compiled
173 * in debug mode. In particular these macros will even work for free cells,
174 * which should never be encountered by user code. */
176 #define SCM_GC_CELL_OBJECT(x, n) (((SCM *)SCM2PTR (x)) [n])
177 #define SCM_GC_CELL_WORD(x, n) (SCM_UNPACK (SCM_GC_CELL_OBJECT ((x), (n))))
179 #define SCM_GC_SET_CELL_OBJECT(x, n, v) ((((SCM *)SCM2PTR (x)) [n]) = (v))
180 #define SCM_GC_SET_CELL_WORD(x, n, v) \
181 (SCM_GC_SET_CELL_OBJECT ((x), (n), SCM_PACK (v)))
183 #define SCM_GC_CELL_TYPE(x) (SCM_GC_CELL_OBJECT ((x), 0))
186 /* Except for the garbage collector, no part of guile should ever run over a
187 * free cell. Thus, if guile is compiled in debug mode the SCM_CELL_* and
188 * SCM_SET_CELL_* macros below report an error if they are applied to a free
189 * cell. Some other plausibility checks are also performed. However, if
190 * guile is not compiled in debug mode, there won't be any time penalty at all
191 * when using these macros. */
193 #if (SCM_DEBUG_CELL_ACCESSES == 1)
194 # define SCM_VALIDATE_CELL(cell, expr) (scm_assert_cell_valid (cell), (expr))
196 # define SCM_VALIDATE_CELL(cell, expr) (expr)
199 #define SCM_CELL_WORD(x, n) \
200 SCM_VALIDATE_CELL ((x), SCM_GC_CELL_WORD ((x), (n)))
201 #define SCM_CELL_WORD_0(x) SCM_CELL_WORD ((x), 0)
202 #define SCM_CELL_WORD_1(x) SCM_CELL_WORD ((x), 1)
203 #define SCM_CELL_WORD_2(x) SCM_CELL_WORD ((x), 2)
204 #define SCM_CELL_WORD_3(x) SCM_CELL_WORD ((x), 3)
206 #define SCM_CELL_OBJECT(x, n) \
207 SCM_VALIDATE_CELL ((x), SCM_GC_CELL_OBJECT ((x), (n)))
208 #define SCM_CELL_OBJECT_0(x) SCM_CELL_OBJECT ((x), 0)
209 #define SCM_CELL_OBJECT_1(x) SCM_CELL_OBJECT ((x), 1)
210 #define SCM_CELL_OBJECT_2(x) SCM_CELL_OBJECT ((x), 2)
211 #define SCM_CELL_OBJECT_3(x) SCM_CELL_OBJECT ((x), 3)
213 #define SCM_SET_CELL_WORD(x, n, v) \
214 SCM_VALIDATE_CELL ((x), SCM_GC_SET_CELL_WORD ((x), (n), (v)))
215 #define SCM_SET_CELL_WORD_0(x, v) SCM_SET_CELL_WORD ((x), 0, (v))
216 #define SCM_SET_CELL_WORD_1(x, v) SCM_SET_CELL_WORD ((x), 1, (v))
217 #define SCM_SET_CELL_WORD_2(x, v) SCM_SET_CELL_WORD ((x), 2, (v))
218 #define SCM_SET_CELL_WORD_3(x, v) SCM_SET_CELL_WORD ((x), 3, (v))
220 #define SCM_SET_CELL_OBJECT(x, n, v) \
221 SCM_VALIDATE_CELL ((x), SCM_GC_SET_CELL_OBJECT ((x), (n), (v)))
222 #define SCM_SET_CELL_OBJECT_0(x, v) SCM_SET_CELL_OBJECT ((x), 0, (v))
223 #define SCM_SET_CELL_OBJECT_1(x, v) SCM_SET_CELL_OBJECT ((x), 1, (v))
224 #define SCM_SET_CELL_OBJECT_2(x, v) SCM_SET_CELL_OBJECT ((x), 2, (v))
225 #define SCM_SET_CELL_OBJECT_3(x, v) SCM_SET_CELL_OBJECT ((x), 3, (v))
227 #define SCM_CELL_OBJECT_LOC(x, n) (SCM_VALIDATE_CELL((x), &SCM_GC_CELL_OBJECT ((x), (n))))
228 #define SCM_CARLOC(x) (SCM_CELL_OBJECT_LOC ((x), 0))
229 #define SCM_CDRLOC(x) (SCM_CELL_OBJECT_LOC ((x), 1))
231 #define SCM_CELL_TYPE(x) SCM_CELL_WORD_0 (x)
232 #define SCM_SET_CELL_TYPE(x, t) SCM_SET_CELL_WORD_0 ((x), (t))
234 /* Freelists consist of linked cells where the type entry holds the value
235 * scm_tc_free_cell and the second entry holds a pointer to the next cell of
236 * the freelist. Due to this structure, freelist cells are not cons cells
237 * and thus may not be accessed using SCM_CAR and SCM_CDR. */
239 #define SCM_FREE_CELL_CDR(x) \
240 (SCM_GC_CELL_OBJECT ((x), 1))
241 #define SCM_SET_FREE_CELL_CDR(x, v) \
242 (SCM_GC_SET_CELL_OBJECT ((x), 1, (v)))
244 #if (SCM_DEBUG_CELL_ACCESSES == 1)
245 /* Set this to != 0 if every cell that is accessed shall be checked:
247 SCM_API
int scm_debug_cell_accesses_p
;
248 SCM_API
int scm_expensive_debug_cell_accesses_p
;
249 SCM_API
int scm_debug_cells_gc_interval
;
250 void scm_i_expensive_validation_check (SCM cell
);
253 SCM_INTERNAL scm_i_pthread_mutex_t scm_i_gc_admin_mutex
;
255 #define scm_gc_running_p (SCM_I_CURRENT_THREAD->gc_running_p)
256 SCM_INTERNAL scm_i_pthread_mutex_t scm_i_sweep_mutex
;
259 void *scm_ia64_register_backing_store_base (void);
260 void *scm_ia64_ar_bsp (const void *);
265 #if (SCM_ENABLE_DEPRECATED == 1)
266 SCM_API
size_t scm_default_init_heap_size_1
;
267 SCM_API
int scm_default_min_yield_1
;
268 SCM_API
size_t scm_default_init_heap_size_2
;
269 SCM_API
int scm_default_min_yield_2
;
270 SCM_API
size_t scm_default_max_segment_size
;
272 #define scm_default_init_heap_size_1 deprecated
273 #define scm_default_min_yield_1 deprecated
274 #define scm_default_init_heap_size_2 deprecated
275 #define scm_default_min_yield_2 deprecated
276 #define scm_default_max_segment_size deprecated
280 SCM_API
size_t scm_max_segment_size
;
282 #define SCM_SET_FREELIST_LOC(key,ptr) scm_i_pthread_setspecific ((key), (ptr))
283 #define SCM_FREELIST_LOC(key) ((SCM *) scm_i_pthread_getspecific (key))
284 SCM_API scm_i_pthread_key_t scm_i_freelist
;
285 SCM_API scm_i_pthread_key_t scm_i_freelist2
;
286 SCM_API
struct scm_t_cell_type_statistics scm_i_master_freelist
;
287 SCM_API
struct scm_t_cell_type_statistics scm_i_master_freelist2
;
289 SCM_API
unsigned long scm_gc_malloc_collected
;
290 SCM_API
int scm_gc_malloc_yield_percentage
;
291 SCM_API
unsigned long scm_mallocated
;
292 SCM_API
unsigned long scm_mtrigger
;
294 SCM_API SCM scm_after_gc_hook
;
296 SCM_API scm_t_c_hook scm_before_gc_c_hook
;
297 SCM_API scm_t_c_hook scm_before_mark_c_hook
;
298 SCM_API scm_t_c_hook scm_before_sweep_c_hook
;
299 SCM_API scm_t_c_hook scm_after_sweep_c_hook
;
300 SCM_API scm_t_c_hook scm_after_gc_c_hook
;
302 #if defined (GUILE_DEBUG) || defined (GUILE_DEBUG_FREELIST)
303 #if (SCM_ENABLE_DEPRECATED == 1)
304 SCM
scm_map_free_list (void);
306 #define scm_map_free_list deprecated
307 #define scm_free_list_length deprecated
311 #if (SCM_ENABLE_DEPRECATED == 1) && defined (GUILE_DEBUG_FREELIST)
312 SCM_API SCM
scm_gc_set_debug_check_freelist_x (SCM flag
);
316 #if (SCM_DEBUG_CELL_ACCESSES == 1)
317 SCM_API
void scm_assert_cell_valid (SCM
);
320 SCM_API SCM
scm_set_debug_cell_accesses_x (SCM flag
);
323 SCM_API SCM
scm_object_address (SCM obj
);
324 SCM_API SCM
scm_gc_stats (void);
325 SCM_API SCM
scm_gc_live_object_stats (void);
326 SCM_API SCM
scm_gc (void);
327 SCM_API
void scm_gc_for_alloc (struct scm_t_cell_type_statistics
*freelist
);
328 SCM_API SCM
scm_gc_for_newcell (struct scm_t_cell_type_statistics
*master
, SCM
*freelist
);
329 SCM_INTERNAL
void scm_i_gc (const char *what
);
330 SCM_API
void scm_gc_mark (SCM p
);
331 SCM_API
void scm_gc_mark_dependencies (SCM p
);
332 SCM_API
void scm_mark_locations (SCM_STACKITEM x
[], unsigned long n
);
333 SCM_API
int scm_in_heap_p (SCM value
);
334 SCM_API
void scm_gc_sweep (void);
336 SCM_API
void *scm_malloc (size_t size
);
337 SCM_API
void *scm_calloc (size_t size
);
338 SCM_API
void *scm_realloc (void *mem
, size_t size
);
339 SCM_API
char *scm_strdup (const char *str
);
340 SCM_API
char *scm_strndup (const char *str
, size_t n
);
341 SCM_API
void scm_gc_register_collectable_memory (void *mem
, size_t size
,
343 SCM_API
void scm_gc_unregister_collectable_memory (void *mem
, size_t size
,
345 SCM_API
void *scm_gc_calloc (size_t size
, const char *what
);
346 SCM_API
void *scm_gc_malloc (size_t size
, const char *what
);
347 SCM_API
void *scm_gc_realloc (void *mem
, size_t old_size
,
348 size_t new_size
, const char *what
);
349 SCM_API
void scm_gc_free (void *mem
, size_t size
, const char *what
);
350 SCM_API
char *scm_gc_strdup (const char *str
, const char *what
);
351 SCM_API
char *scm_gc_strndup (const char *str
, size_t n
, const char *what
);
353 SCM_API
void scm_remember_upto_here_1 (SCM obj
);
354 SCM_API
void scm_remember_upto_here_2 (SCM obj1
, SCM obj2
);
355 SCM_API
void scm_remember_upto_here (SCM obj1
, ...);
357 /* In GCC we can force a reference to an SCM by making it an input to an
358 empty asm. This avoids the code size and slowdown of an actual function
359 call. Unfortunately there doesn't seem to be any way to do the varargs
360 scm_remember_upto_here like this.
362 __volatile__ ensures nothing will be moved across the asm, and it won't
363 be optimized away (or only if proved unreachable). Constraint "g" can be
364 used on all processors and allows any memory or general register (or
365 immediate) operand. The actual asm syntax doesn't matter, we don't want
366 to use it, just ensure the operand is still alive. See "Extended Asm" in
367 the GCC manual for more. */
370 #define scm_remember_upto_here_1(x) \
372 __asm__ __volatile__ ("" : : "g" (x)); \
374 #define scm_remember_upto_here_2(x, y) \
376 scm_remember_upto_here_1 (x); \
377 scm_remember_upto_here_1 (y); \
381 SCM_API SCM
scm_return_first (SCM elt
, ...);
382 SCM_API
int scm_return_first_int (int x
, ...);
383 SCM_API SCM
scm_permanent_object (SCM obj
);
384 SCM_API SCM
scm_gc_protect_object (SCM obj
);
385 SCM_API SCM
scm_gc_unprotect_object (SCM obj
);
386 SCM_API
void scm_gc_register_root (SCM
*p
);
387 SCM_API
void scm_gc_unregister_root (SCM
*p
);
388 SCM_API
void scm_gc_register_roots (SCM
*b
, unsigned long n
);
389 SCM_API
void scm_gc_unregister_roots (SCM
*b
, unsigned long n
);
390 SCM_API
void scm_storage_prehistory (void);
391 SCM_API
int scm_init_storage (void);
392 SCM_API
void *scm_get_stack_base (void);
393 SCM_INTERNAL
void scm_init_gc (void);
395 #if SCM_ENABLE_DEPRECATED == 1
397 SCM_API SCM
scm_deprecated_newcell (void);
398 SCM_API SCM
scm_deprecated_newcell2 (void);
400 #define SCM_NEWCELL(_into) \
401 do { _into = scm_deprecated_newcell (); } while (0)
402 #define SCM_NEWCELL2(_into) \
403 do { _into = scm_deprecated_newcell2 (); } while (0)
405 SCM_API
void * scm_must_malloc (size_t len
, const char *what
);
406 SCM_API
void * scm_must_realloc (void *where
,
407 size_t olen
, size_t len
,
409 SCM_API
char *scm_must_strdup (const char *str
);
410 SCM_API
char *scm_must_strndup (const char *str
, size_t n
);
411 SCM_API
void scm_done_malloc (long size
);
412 SCM_API
void scm_done_free (long size
);
413 SCM_API
void scm_must_free (void *obj
);
417 #endif /* SCM_GC_H */