1 /* classes: h_files */ 2 3 #ifndef SCM_GC_H 4 #define SCM_GC_H 5 6 /* Copyright (C) 1995,1996,1998,1999,2000,2001, 2002, 2003, 2004, 2006 Free Software Foundation, Inc. 7 * 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. 12 * 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. 17 * 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 21 */ 22 23 24 25 #include "libguile/__scm.h" 26 27 #include "libguile/hooks.h" 28 #include "libguile/threads.h" 29 30 31 32 /* Cell allocation and garbage collection work rouhgly in the 33 following manner: 34 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.) 38 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 45 freed yet. 46 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. 51 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 57 started again. 58 */ 59 60 typedef struct scm_t_cell 61 { 62 SCM word_0; 63 SCM word_1; 64 } scm_t_cell; 65 66 /* 67 CARDS 68 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. 73 74 The size on a 32 bit machine is 256 cells = 2kb. The card [XXX] 75 */ 76 77 78 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. 85 */ 86 #ifdef _UNICOS 87 # define SCM2PTR(x) ((scm_t_cell *) (SCM_UNPACK (x) >> 3)) 88 # define PTR2SCM(x) (SCM_PACK (((scm_t_bits) (x)) << 3)) 89 #else 90 # define SCM2PTR(x) ((scm_t_cell *) (SCM_UNPACK (x))) 91 # define PTR2SCM(x) (SCM_PACK ((scm_t_bits) (x))) 92 #endif /* def _UNICOS */ 93 94 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) 98 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)) 105 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)))) 112 113 /* 114 Remove card flags. They hamper lazy initialization, and aren't used 115 anyways. 116 */ 117 118 /* card addressing. for efficiency, cards are *always* aligned to 119 SCM_GC_CARD_SIZE. */ 120 121 #define SCM_GC_CARD_SIZE_MASK (SCM_GC_SIZEOF_CARD-1) 122 #define SCM_GC_CARD_ADDR_MASK (~SCM_GC_CARD_SIZE_MASK) 123 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)) 131 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 134 135 /* low level bit banging aids */ 136 typedef unsigned long scm_t_c_bvec_long; 137 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 143 #else 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 148 #endif 149 150 #define SCM_C_BVEC_OFFSET(pos) (pos >> SCM_C_BVEC_OFFSET_SHIFT) 151 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))) 155 156 /* testing and changing GC marks */ 157 #define SCM_GC_MARK_P(x) SCM_GC_CELL_GET_BIT (x) 158 #define SCM_SET_GC_MARK(x) SCM_GC_CELL_SET_BIT (x) 159 #define SCM_CLEAR_GC_MARK(x) SCM_GC_CELL_CLEAR_BIT (x) 160 161 /* Low level cell data accessing macros. These macros should only be used 162 * from within code related to garbage collection issues, since they will 163 * never check the cells they are applied to - not even if guile is compiled 164 * in debug mode. In particular these macros will even work for free cells, 165 * which should never be encountered by user code. */ 166 167 #define SCM_GC_CELL_OBJECT(x, n) (((SCM *)SCM2PTR (x)) [n]) 168 #define SCM_GC_CELL_WORD(x, n) (SCM_UNPACK (SCM_GC_CELL_OBJECT ((x), (n)))) 169 170 #define SCM_GC_SET_CELL_OBJECT(x, n, v) ((((SCM *)SCM2PTR (x)) [n]) = (v)) 171 #define SCM_GC_SET_CELL_WORD(x, n, v) \ 172 (SCM_GC_SET_CELL_OBJECT ((x), (n), SCM_PACK (v))) 173 174 #define SCM_GC_CELL_TYPE(x) (SCM_GC_CELL_OBJECT ((x), 0)) 175 176 177 /* Except for the garbage collector, no part of guile should ever run over a 178 * free cell. Thus, if guile is compiled in debug mode the SCM_CELL_* and 179 * SCM_SET_CELL_* macros below report an error if they are applied to a free 180 * cell. Some other plausibility checks are also performed. However, if 181 * guile is not compiled in debug mode, there won't be any time penalty at all 182 * when using these macros. */ 183 184 #if (SCM_DEBUG_CELL_ACCESSES == 1) 185 # define SCM_VALIDATE_CELL(cell, expr) (scm_assert_cell_valid (cell), (expr)) 186 #else 187 # define SCM_VALIDATE_CELL(cell, expr) (expr) 188 #endif 189 190 #define SCM_CELL_WORD(x, n) \ 191 SCM_VALIDATE_CELL ((x), SCM_GC_CELL_WORD ((x), (n))) 192 #define SCM_CELL_WORD_0(x) SCM_CELL_WORD ((x), 0) 193 #define SCM_CELL_WORD_1(x) SCM_CELL_WORD ((x), 1) 194 #define SCM_CELL_WORD_2(x) SCM_CELL_WORD ((x), 2) 195 #define SCM_CELL_WORD_3(x) SCM_CELL_WORD ((x), 3) 196 197 #define SCM_CELL_OBJECT(x, n) \ 198 SCM_VALIDATE_CELL ((x), SCM_GC_CELL_OBJECT ((x), (n))) 199 #define SCM_CELL_OBJECT_0(x) SCM_CELL_OBJECT ((x), 0) 200 #define SCM_CELL_OBJECT_1(x) SCM_CELL_OBJECT ((x), 1) 201 #define SCM_CELL_OBJECT_2(x) SCM_CELL_OBJECT ((x), 2) 202 #define SCM_CELL_OBJECT_3(x) SCM_CELL_OBJECT ((x), 3) 203 204 #define SCM_SET_CELL_WORD(x, n, v) \ 205 SCM_VALIDATE_CELL ((x), SCM_GC_SET_CELL_WORD ((x), (n), (v))) 206 #define SCM_SET_CELL_WORD_0(x, v) SCM_SET_CELL_WORD ((x), 0, (v)) 207 #define SCM_SET_CELL_WORD_1(x, v) SCM_SET_CELL_WORD ((x), 1, (v)) 208 #define SCM_SET_CELL_WORD_2(x, v) SCM_SET_CELL_WORD ((x), 2, (v)) 209 #define SCM_SET_CELL_WORD_3(x, v) SCM_SET_CELL_WORD ((x), 3, (v)) 210 211 #define SCM_SET_CELL_OBJECT(x, n, v) \ 212 SCM_VALIDATE_CELL ((x), SCM_GC_SET_CELL_OBJECT ((x), (n), (v))) 213 #define SCM_SET_CELL_OBJECT_0(x, v) SCM_SET_CELL_OBJECT ((x), 0, (v)) 214 #define SCM_SET_CELL_OBJECT_1(x, v) SCM_SET_CELL_OBJECT ((x), 1, (v)) 215 #define SCM_SET_CELL_OBJECT_2(x, v) SCM_SET_CELL_OBJECT ((x), 2, (v)) 216 #define SCM_SET_CELL_OBJECT_3(x, v) SCM_SET_CELL_OBJECT ((x), 3, (v)) 217 218 #define SCM_CELL_OBJECT_LOC(x, n) (SCM_VALIDATE_CELL((x), &SCM_GC_CELL_OBJECT ((x), (n)))) 219 #define SCM_CARLOC(x) (SCM_CELL_OBJECT_LOC ((x), 0)) 220 #define SCM_CDRLOC(x) (SCM_CELL_OBJECT_LOC ((x), 1)) 221 222 #define SCM_CELL_TYPE(x) SCM_CELL_WORD_0 (x) 223 #define SCM_SET_CELL_TYPE(x, t) SCM_SET_CELL_WORD_0 ((x), (t)) 224 225 /* Freelists consist of linked cells where the type entry holds the value 226 * scm_tc_free_cell and the second entry holds a pointer to the next cell of 227 * the freelist. Due to this structure, freelist cells are not cons cells 228 * and thus may not be accessed using SCM_CAR and SCM_CDR. */ 229 230 #define SCM_FREE_CELL_CDR(x) \ 231 (SCM_GC_CELL_OBJECT ((x), 1)) 232 #define SCM_SET_FREE_CELL_CDR(x, v) \ 233 (SCM_GC_SET_CELL_OBJECT ((x), 1, (v))) 234 235 #if (SCM_DEBUG_CELL_ACCESSES == 1) 236 /* Set this to != 0 if every cell that is accessed shall be checked: 237 */ 238 SCM_API int scm_debug_cell_accesses_p; 239 SCM_API int scm_expensive_debug_cell_accesses_p; 240 SCM_API int scm_debug_cells_gc_interval ; 241 void scm_i_expensive_validation_check (SCM cell); 242 #endif 243 244 SCM_API scm_i_pthread_mutex_t scm_i_gc_admin_mutex; 245 246 #define scm_gc_running_p (SCM_I_CURRENT_THREAD->gc_running_p) 247 SCM_API scm_i_pthread_mutex_t scm_i_sweep_mutex; 248 249 #ifdef __ia64__ 250 void *scm_ia64_register_backing_store_base (void); 251 void *scm_ia64_ar_bsp (const void *); 252 #endif 253 254 255 256 #if (SCM_ENABLE_DEPRECATED == 1) 257 SCM_API size_t scm_default_init_heap_size_1; 258 SCM_API int scm_default_min_yield_1; 259 SCM_API size_t scm_default_init_heap_size_2; 260 SCM_API int scm_default_min_yield_2; 261 SCM_API size_t scm_default_max_segment_size; 262 #else 263 #define scm_default_init_heap_size_1 deprecated 264 #define scm_default_min_yield_1 deprecated 265 #define scm_default_init_heap_size_2 deprecated 266 #define scm_default_min_yield_2 deprecated 267 #define scm_default_max_segment_size deprecated 268 #endif 269 270 271 SCM_API size_t scm_max_segment_size; 272 273 #define SCM_SET_FREELIST_LOC(key,ptr) scm_i_pthread_setspecific ((key), (ptr)) 274 #define SCM_FREELIST_LOC(key) ((SCM *) scm_i_pthread_getspecific (key)) 275 SCM_API scm_i_pthread_key_t scm_i_freelist; 276 SCM_API scm_i_pthread_key_t scm_i_freelist2; 277 SCM_API struct scm_t_cell_type_statistics scm_i_master_freelist; 278 SCM_API struct scm_t_cell_type_statistics scm_i_master_freelist2; 279 #ifdef __MINGW32__ 280 SCM_API scm_i_pthread_key_t *scm_i_freelist_ptr; 281 SCM_API scm_i_pthread_key_t *scm_i_freelist2_ptr; 282 SCM_API struct scm_t_cell_type_statistics *scm_i_master_freelist_ptr; 283 SCM_API struct scm_t_cell_type_statistics *scm_i_master_freelist2_ptr; 284 #endif 285 286 SCM_API unsigned long scm_gc_cells_swept; 287 SCM_API unsigned long scm_gc_cells_collected; 288 SCM_API unsigned long scm_gc_malloc_collected; 289 SCM_API unsigned long scm_gc_ports_collected; 290 SCM_API unsigned long scm_cells_allocated; 291 SCM_API unsigned long scm_last_cells_allocated; 292 SCM_API int scm_gc_cell_yield_percentage; 293 SCM_API int scm_gc_malloc_yield_percentage; 294 SCM_API unsigned long scm_mallocated; 295 SCM_API unsigned long scm_mtrigger; 296 SCM_API double scm_gc_cells_allocated_acc; 297 298 299 300 SCM_API SCM scm_after_gc_hook; 301 302 SCM_API scm_t_c_hook scm_before_gc_c_hook; 303 SCM_API scm_t_c_hook scm_before_mark_c_hook; 304 SCM_API scm_t_c_hook scm_before_sweep_c_hook; 305 SCM_API scm_t_c_hook scm_after_sweep_c_hook; 306 SCM_API scm_t_c_hook scm_after_gc_c_hook; 307 308 #if defined (GUILE_DEBUG) || defined (GUILE_DEBUG_FREELIST) 309 #if (SCM_ENABLE_DEPRECATED == 1) 310 SCM scm_map_free_list (void); 311 #else 312 #define scm_map_free_list deprecated 313 #define scm_free_list_length deprecated 314 #endif 315 #endif 316 317 #if (SCM_ENABLE_DEPRECATED == 1) && defined (GUILE_DEBUG_FREELIST) 318 SCM_API SCM scm_gc_set_debug_check_freelist_x (SCM flag); 319 #endif 320 321 322 #if (SCM_DEBUG_CELL_ACCESSES == 1) 323 SCM_API void scm_assert_cell_valid (SCM); 324 #endif 325 326 SCM_API SCM scm_set_debug_cell_accesses_x (SCM flag); 327 328 329 SCM_API SCM scm_object_address (SCM obj); 330 SCM_API SCM scm_gc_stats (void); 331 SCM_API SCM scm_gc_live_object_stats (void); 332 SCM_API SCM scm_gc (void); 333 SCM_API void scm_gc_for_alloc (struct scm_t_cell_type_statistics *freelist); 334 SCM_API SCM scm_gc_for_newcell (struct scm_t_cell_type_statistics *master, SCM *freelist); 335 SCM_API void scm_i_gc (const char *what); 336 SCM_API void scm_gc_mark (SCM p); 337 SCM_API void scm_gc_mark_dependencies (SCM p); 338 SCM_API void scm_mark_locations (SCM_STACKITEM x[], unsigned long n); 339 SCM_API int scm_in_heap_p (SCM value); 340 SCM_API void scm_gc_sweep (void); 341 342 SCM_API void *scm_malloc (size_t size); 343 SCM_API void *scm_calloc (size_t size); 344 SCM_API void *scm_realloc (void *mem, size_t size); 345 SCM_API char *scm_strdup (const char *str); 346 SCM_API char *scm_strndup (const char *str, size_t n); 347 SCM_API void scm_gc_register_collectable_memory (void *mem, size_t size, 348 const char *what); 349 SCM_API void scm_gc_unregister_collectable_memory (void *mem, size_t size, 350 const char *what); 351 SCM_API void *scm_gc_calloc (size_t size, const char *what); 352 SCM_API void *scm_gc_malloc (size_t size, const char *what); 353 SCM_API void *scm_gc_realloc (void *mem, size_t old_size, 354 size_t new_size, const char *what); 355 SCM_API void scm_gc_free (void *mem, size_t size, const char *what); 356 SCM_API char *scm_gc_strdup (const char *str, const char *what); 357 SCM_API char *scm_gc_strndup (const char *str, size_t n, const char *what); 358 359 SCM_API void scm_remember_upto_here_1 (SCM obj); 360 SCM_API void scm_remember_upto_here_2 (SCM obj1, SCM obj2); 361 SCM_API void scm_remember_upto_here (SCM obj1, ...); 362 363 /* In GCC we can force a reference to an SCM by making it an input to an 364 empty asm. This avoids the code size and slowdown of an actual function 365 call. Unfortunately there doesn't seem to be any way to do the varargs 366 scm_remember_upto_here like this. 367 368 __volatile__ ensures nothing will be moved across the asm, and it won't 369 be optimized away (or only if proved unreachable). Constraint "g" can be 370 used on all processors and allows any memory or general register (or 371 immediate) operand. The actual asm syntax doesn't matter, we don't want 372 to use it, just ensure the operand is still alive. See "Extended Asm" in 373 the GCC manual for more. */ 374 375 #ifdef __GNUC__ 376 #define scm_remember_upto_here_1(x) \ 377 do { \ 378 __asm__ __volatile__ ("" : : "g" (x)); \ 379 } while (0) 380 #define scm_remember_upto_here_2(x, y) \ 381 do { \ 382 scm_remember_upto_here_1 (x); \ 383 scm_remember_upto_here_1 (y); \ 384 } while (0) 385 #endif 386 387 SCM_API SCM scm_return_first (SCM elt, ...); 388 SCM_API int scm_return_first_int (int x, ...); 389 SCM_API SCM scm_permanent_object (SCM obj); 390 SCM_API SCM scm_gc_protect_object (SCM obj); 391 SCM_API SCM scm_gc_unprotect_object (SCM obj); 392 SCM_API void scm_gc_register_root (SCM *p); 393 SCM_API void scm_gc_unregister_root (SCM *p); 394 SCM_API void scm_gc_register_roots (SCM *b, unsigned long n); 395 SCM_API void scm_gc_unregister_roots (SCM *b, unsigned long n); 396 SCM_API void scm_storage_prehistory (void); 397 SCM_API int scm_init_storage (void); 398 SCM_API void *scm_get_stack_base (void); 399 SCM_API void scm_init_gc (void); 400 401 #if SCM_ENABLE_DEPRECATED == 1 402 403 SCM_API SCM scm_deprecated_newcell (void); 404 SCM_API SCM scm_deprecated_newcell2 (void); 405 406 #define SCM_NEWCELL(_into) \ 407 do { _into = scm_deprecated_newcell (); } while (0) 408 #define SCM_NEWCELL2(_into) \ 409 do { _into = scm_deprecated_newcell2 (); } while (0) 410 411 SCM_API void * scm_must_malloc (size_t len, const char *what); 412 SCM_API void * scm_must_realloc (void *where, 413 size_t olen, size_t len, 414 const char *what); 415 SCM_API char *scm_must_strdup (const char *str); 416 SCM_API char *scm_must_strndup (const char *str, size_t n); 417 SCM_API void scm_done_malloc (long size); 418 SCM_API void scm_done_free (long size); 419 SCM_API void scm_must_free (void *obj); 420 421 #endif 422 423 #endif /* SCM_GC_H */ 424 425 /* 426 Local Variables: 427 c-file-style: "gnu" 428 End: 429 */ 430