libguile/gc.h

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