home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / sa104os2.zip / SATHR104.ZIP / SATHER / SYSTEM / GC / GC_PRIV.H < prev    next >
C/C++ Source or Header  |  1994-11-08  |  45KB  |  1,270 lines
  1. /* 
  2.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  3.  * Copyright (c) 1991-1994 by Xerox Corporation.  All rights reserved.
  4.  *
  5.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  6.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  7.  *
  8.  * Permission is hereby granted to use or copy this program
  9.  * for any purpose,  provided the above notices are retained on all copies.
  10.  * Permission to modify the code and to distribute modified code is granted,
  11.  * provided the above notices are retained, and a notice that the code was
  12.  * modified is included with the above copyright notice.
  13.  */
  14. /* Boehm, November 8, 1994 5:49 pm PST */
  15.  
  16.  
  17. # ifndef GC_PRIVATE_H
  18. # define GC_PRIVATE_H
  19.  
  20. #if defined(mips) && defined(SYSTYPE_BSD) && defined(sony_news)
  21.     /* sony RISC NEWS, NEWSOS 4 */
  22. #   define BSD_TIME
  23.     typedef long ptrdiff_t;
  24. #endif
  25.  
  26. #if defined(mips) && defined(SYSTYPE_BSD43)
  27.     /* MIPS RISCOS 4 */
  28. #   define BSD_TIME
  29. #endif
  30.  
  31. #ifdef BSD_TIME
  32. #   include <sys/types.h>
  33. #   include <sys/time.h>
  34. #   include <sys/resource.h>
  35. #endif /* BSD_TIME */
  36.  
  37. # ifndef GC_H
  38. #   include "gc.h"
  39. # endif
  40.  
  41. typedef GC_word word;
  42. typedef GC_signed_word signed_word;
  43.  
  44. # ifndef CONFIG_H
  45. #   include "config.h"
  46. # endif
  47.  
  48. # ifndef HEADERS_H
  49. #   include "gc_hdrs.h"
  50. # endif
  51.  
  52. # ifndef bool
  53.     typedef int bool;
  54. # endif
  55. # define TRUE 1
  56. # define FALSE 0
  57.  
  58. typedef char * ptr_t;    /* A generic pointer to which we can add    */
  59.             /* byte displacements.                */
  60.             /* Preferably identical to caddr_t, if it     */
  61.             /* exists.                    */
  62.             
  63. #if defined(__STDC__)
  64. #   include <stdlib.h>
  65. #   if !(defined( sony_news ) )
  66. #       include <stddef.h>
  67. #   endif
  68.     typedef void * extern_ptr_t;
  69. #   define VOLATILE volatile
  70. #else
  71. #   ifdef MSWIN32
  72. #       include <stdlib.h>
  73. #   endif
  74.     typedef char * extern_ptr_t;
  75. #   define VOLATILE
  76. #endif
  77.  
  78. #ifdef AMIGA
  79. #   define GC_FAR __far
  80. #else
  81. #   define GC_FAR
  82. #endif
  83.  
  84. /*********************************/
  85. /*                               */
  86. /* Definitions for conservative  */
  87. /* collector                     */
  88. /*                               */
  89. /*********************************/
  90.  
  91. /*********************************/
  92. /*                               */
  93. /* Easily changeable parameters  */
  94. /*                               */
  95. /*********************************/
  96.  
  97. #define STUBBORN_ALLOC    /* Define stubborn allocation primitives    */
  98. #if defined(SRC_M3) || defined(SMALL_CONFIG)
  99. # undef STUBBORN_ALLOC
  100. #endif
  101.  
  102.  
  103. /* #define ALL_INTERIOR_POINTERS */
  104.             /* Forces all pointers into the interior of an     */
  105.             /* object to be considered valid.  Also causes the    */
  106.             /* sizes of all objects to be inflated by at least     */
  107.             /* one byte.  This should suffice to guarantee    */
  108.             /* that in the presence of a compiler that does    */
  109.             /* not perform garbage-collector-unsafe        */
  110.             /* optimizations, all portable, strictly ANSI    */
  111.             /* conforming C programs should be safely usable    */
  112.             /* with malloc replaced by GC_malloc and free    */
  113.             /* calls removed.  There are several disadvantages: */
  114.             /* 1. There are probably no interesting, portable,    */
  115.             /*    strictly ANSI    conforming C programs.        */
  116.             /* 2. This option makes it hard for the collector    */
  117.             /*    to allocate space that is not ``pointed to''  */
  118.             /*    by integers, etc.  Under SunOS 4.X with a     */
  119.             /*    statically linked libc, we empiricaly        */
  120.             /*    observed that it would be difficult to     */
  121.             /*      allocate individual objects larger than 100K.    */
  122.             /*       Even if only smaller objects are allocated,    */
  123.             /*    more swap space is likely to be needed.       */
  124.             /*    Fortunately, much of this will never be    */
  125.             /*    touched.                    */
  126.             /* If you can easily avoid using this option, do.    */
  127.             /* If not, try to keep individual objects small.    */
  128.             
  129. #define PRINTSTATS  /* Print garbage collection statistics              */
  130.             /* For less verbose output, undefine in reclaim.c     */
  131.  
  132. #define PRINTTIMES  /* Print the amount of time consumed by each garbage   */
  133.             /* collection.                                         */
  134.  
  135. #define PRINTBLOCKS /* Print object sizes associated with heap blocks,     */
  136.             /* whether the objects are atomic or composite, and    */
  137.             /* whether or not the block was found to be empty      */
  138.             /* duing the reclaim phase.  Typically generates       */
  139.             /* about one screenful per garbage collection.         */
  140. #undef PRINTBLOCKS
  141.  
  142. #define PRINTBLACKLIST     /* Print black listed blocks, i.e. values that     */
  143.             /* cause the allocator to avoid allocating certain */
  144.             /* blocks in order to avoid introducing "false       */
  145.             /* hits".                       */
  146. #undef PRINTBLACKLIST
  147.  
  148. #ifdef SILENT
  149. #  ifdef PRINTSTATS
  150. #    undef PRINTSTATS
  151. #  endif
  152. #  ifdef PRINTTIMES
  153. #    undef PRINTTIMES
  154. #  endif
  155. #  ifdef PRINTNBLOCKS
  156. #    undef PRINTNBLOCKS
  157. #  endif
  158. #endif
  159.  
  160. #if defined(PRINTSTATS) && !defined(GATHERSTATS)
  161. #   define GATHERSTATS
  162. #endif
  163.  
  164. # if defined(SOLARIS_THREADS) && !defined(SUNOS5)
  165. --> inconsistent configuration
  166. # endif
  167. # if defined(PCR) || defined(SRC_M3) || defined(SOLARIS_THREADS)
  168. #   define THREADS
  169. # endif
  170.  
  171. #if defined(SPARC) || defined(HP_PA)
  172. #   define ALIGN_DOUBLE  /* Align objects of size > 1 word on 2 word   */
  173.              /* boundaries.  Wasteful of memory, but       */
  174.              /* apparently required by SPARC architecture. */
  175. #   define ASM_CLEAR_CODE    /* Stack clearing is crucial, and we     */
  176.                 /* include assembly code to do it well.    */
  177. #endif
  178.  
  179. #ifdef HP_PA
  180. #   define ALIGN_DOUBLE
  181. #endif
  182.  
  183. #define MERGE_SIZES /* Round up some object sizes, so that fewer distinct */
  184.             /* free lists are actually maintained.  This applies  */
  185.             /* only to the top level routines in misc.c, not to   */
  186.             /* user generated code that calls GC_allocobj and     */
  187.             /* GC_allocaobj directly.                             */
  188.             /* Slows down average programs slightly.  May however */
  189.             /* substantially reduce fragmentation if allocation   */
  190.             /* request sizes are widely scattered.                */
  191.             /* May save significant amounts of space for obj_map  */
  192.             /* entries.                          */
  193.  
  194. /* ALIGN_DOUBLE requires MERGE_SIZES at present. */
  195. # if defined(ALIGN_DOUBLE) && !defined(MERGE_SIZES)
  196. #   define MERGE_SIZES
  197. # endif
  198.  
  199. #if defined(ALL_INTERIOR_POINTERS) && !defined(DONT_ADD_BYTE_AT_END)
  200. # define ADD_BYTE_AT_END
  201. #endif
  202.  
  203.  
  204. # define MINHINCR 16       /* Minimum heap increment, in blocks of HBLKSIZE  */
  205. # define MAXHINCR 512      /* Maximum heap increment, in blocks              */
  206.  
  207. # define TIME_LIMIT 50       /* We try to keep pause times from exceeding     */
  208.                /* this by much. In milliseconds.         */
  209.  
  210. /*********************************/
  211. /*                               */
  212. /* Stack saving for debugging     */
  213. /*                               */
  214. /*********************************/
  215.  
  216. /*
  217.  * Number of frames and arguments to save in objects allocated by
  218.  * debugging allocator.
  219.  */
  220. #   define NFRAMES 6    /* Number of frames to save. Even for        */
  221.             /* alignment reasons.                */
  222. #   define NARGS 2    /* Mumber of arguments to save for each call.    */
  223.  
  224.  
  225. #ifdef SAVE_CALL_CHAIN
  226.     struct callinfo {
  227.     word ci_pc;
  228.     word ci_arg[NARGS];    /* bit-wise complement to avoid retention */
  229.     };
  230.  
  231. /* Fill in the pc and argument information for up to NFRAMES of my    */
  232. /* callers.  Ignore my frame and my callers frame.            */
  233. void GC_save_callers (/* struct callinfo info[NFRAMES] */);
  234.  
  235. void GC_print_callers (/* struct callinfo info[NFRAMES] */);
  236.  
  237. #endif
  238.  
  239.  
  240. /*********************************/
  241. /*                               */
  242. /* OS interface routines     */
  243. /*                               */
  244. /*********************************/
  245.  
  246. #ifdef BSD_TIME
  247. #   undef CLOCK_TYPE
  248. #   undef GET_TIME
  249. #   undef MS_TIME_DIFF
  250. #   define CLOCK_TYPE struct timeval
  251. #   define GET_TIME(x) { struct rusage rusage; \
  252.              getrusage (RUSAGE_SELF,  &rusage); \
  253.              x = rusage.ru_utime; }
  254. #   define MS_TIME_DIFF(a,b) ((double) (a.tv_sec - b.tv_sec) * 1000.0 \
  255.                                + (double) (a.tv_usec - b.tv_usec) / 1000.0)
  256. #else /* !BSD_TIME */
  257. #   include <time.h>
  258. #   if !defined(__STDC__) && defined(SPARC) && defined(SUNOS4)
  259.       clock_t clock();    /* Not in time.h, where it belongs    */
  260. #   endif
  261. #   if defined(FREEBSD) && !defined(CLOCKS_PER_SEC)
  262. #     include <machine/limits.h>
  263. #     define CLOCKS_PER_SEC CLK_TCK
  264. #   endif
  265. #   if !defined(CLOCKS_PER_SEC)
  266. #     define CLOCKS_PER_SEC 1000000
  267. /*
  268.  * This is technically a bug in the implementation.  ANSI requires that
  269.  * CLOCKS_PER_SEC be defined.  But at least under SunOS4.1.1, it isn't.
  270.  * Also note that the combination of ANSI C and POSIX is incredibly gross
  271.  * here. The type clock_t is used by both clock() and times().  But on
  272.  * some machines these use different notions of a clock tick,  CLOCKS_PER_SEC
  273.  * seems to apply only to clock.  Hence we use it here.  On many machines,
  274.  * including SunOS, clock actually uses units of microseconds (which are
  275.  * not really clock ticks).
  276.  */
  277. #   endif
  278. #   define CLOCK_TYPE clock_t
  279. #   define GET_TIME(x) x = clock()
  280. #   define MS_TIME_DIFF(a,b) ((unsigned long) \
  281.         (1000.0*(double)((a)-(b))/(double)CLOCKS_PER_SEC))
  282. #endif /* !BSD_TIME */
  283.  
  284. /* We use bzero and bcopy internally.  They may not be available.    */
  285. # if defined(SPARC) && defined(SUNOS4)
  286. #   define BCOPY_EXISTS
  287. # endif
  288. # if defined(M68K) && defined(AMIGA)
  289. #   define BCOPY_EXISTS
  290. # endif
  291. # if defined(M68K) && defined(NEXT)
  292. #   define BCOPY_EXISTS
  293. # endif
  294. # if defined(VAX)
  295. #   define BCOPY_EXISTS
  296. # endif
  297. # if defined(AMIGA)
  298. #   include <string.h>
  299. #   define BCOPY_EXISTS
  300. # endif
  301.  
  302. # ifndef BCOPY_EXISTS
  303. #   include <string.h>
  304. #   define BCOPY(x,y,n) memcpy(y, x, (size_t)(n))
  305. #   define BZERO(x,n)  memset(x, 0, (size_t)(n))
  306. # else
  307. #   define BCOPY(x,y,n) bcopy((char *)(x),(char *)(y),(int)(n))
  308. #   define BZERO(x,n) bzero((char *)(x),(int)(n))
  309. # endif
  310.  
  311. /* HBLKSIZE aligned allocation.  0 is taken to mean failure     */
  312. /* space is assumed to be cleared.                */
  313. # ifdef PCR
  314.     char * real_malloc();
  315. #   define GET_MEM(bytes) HBLKPTR(real_malloc((size_t)bytes + HBLKSIZE) \
  316.                   + HBLKSIZE-1)
  317. # else
  318. #   ifdef OS2
  319.       void * os2_alloc(size_t bytes);
  320. #     define GET_MEM(bytes) HBLKPTR((ptr_t)os2_alloc((size_t)bytes + HBLKSIZE) \
  321.                                     + HBLKSIZE-1)
  322. #   else
  323. #     if defined(AMIGA) || defined(NEXT)
  324. #       define GET_MEM(bytes) HBLKPTR((size_t) \
  325.                       calloc(1, (size_t)bytes + HBLKSIZE) \
  326.                                       + HBLKSIZE-1)
  327. #     else
  328. #    ifdef MSWIN32
  329.           extern ptr_t GC_win32_get_mem();
  330. #         define GET_MEM(bytes) (struct hblk *)GC_win32_get_mem(bytes)
  331. #    else
  332. #      ifdef MACOS
  333. #        if defined(USE_TEMPORARY_MEMORY)
  334.         extern Ptr GC_MacTemporaryNewPtr(size_t size,
  335.                          Boolean clearMemory);
  336. #               define GET_MEM(bytes) HBLKPTR( \
  337.             GC_MacTemporaryNewPtr(bytes + HBLKSIZE, true) + HBLKSIZE-1)
  338. #        else
  339. #                 define GET_MEM(bytes) HBLKPTR( \
  340.             NewPtrClear(bytes + HBLKSIZE) + HBLKSIZE-1)
  341. #        endif
  342. #      else
  343.             extern ptr_t GC_unix_get_mem();
  344. #           define GET_MEM(bytes) (struct hblk *)GC_unix_get_mem(bytes)
  345. #      endif
  346. #    endif
  347. #     endif
  348. #   endif
  349. # endif
  350.  
  351. /*
  352.  * Mutual exclusion between allocator/collector routines.
  353.  * Needed if there is more than one allocator thread.
  354.  * FASTLOCK() is assumed to try to acquire the lock in a cheap and
  355.  * dirty way that is acceptable for a few instructions, e.g. by
  356.  * inhibiting preemption.  This is assumed to have succeeded only
  357.  * if a subsequent call to FASTLOCK_SUCCEEDED() returns TRUE.
  358.  * FASTUNLOCK() is called whether or not FASTLOCK_SUCCEEDED().
  359.  * If signals cannot be tolerated with the FASTLOCK held, then
  360.  * FASTLOCK should disable signals.  The code executed under
  361.  * FASTLOCK is otherwise immune to interruption, provided it is
  362.  * not restarted.
  363.  * DCL_LOCK_STATE declares any local variables needed by LOCK and UNLOCK
  364.  * and/or DISABLE_SIGNALS and ENABLE_SIGNALS and/or FASTLOCK.
  365.  * (There is currently no equivalent for FASTLOCK.)
  366.  */  
  367. # ifdef THREADS
  368. #  ifdef PCR_OBSOLETE    /* Faster, but broken with multiple lwp's    */
  369. #    include  "th/PCR_Th.h"
  370. #    include  "th/PCR_ThCrSec.h"
  371.      extern struct PCR_Th_MLRep GC_allocate_ml;
  372. #    define DCL_LOCK_STATE  PCR_sigset_t GC_old_sig_mask
  373. #    define LOCK() PCR_Th_ML_Acquire(&GC_allocate_ml) 
  374. #    define UNLOCK() PCR_Th_ML_Release(&GC_allocate_ml)
  375. #    define FASTLOCK() PCR_ThCrSec_EnterSys()
  376.      /* Here we cheat (a lot): */
  377. #        define FASTLOCK_SUCCEEDED() (*(int *)(&GC_allocate_ml) == 0)
  378.         /* TRUE if nobody currently holds the lock */
  379. #    define FASTUNLOCK() PCR_ThCrSec_ExitSys()
  380. #  endif
  381. #  ifdef PCR
  382. #    include <base/PCR_Base.h>
  383. #    include <th/PCR_Th.h>
  384.      extern PCR_Th_ML GC_allocate_ml;
  385. #    define DCL_LOCK_STATE \
  386.      PCR_ERes GC_fastLockRes; PCR_sigset_t GC_old_sig_mask
  387. #    define LOCK() PCR_Th_ML_Acquire(&GC_allocate_ml)
  388. #    define UNLOCK() PCR_Th_ML_Release(&GC_allocate_ml)
  389. #    define FASTLOCK() (GC_fastLockRes = PCR_Th_ML_Try(&GC_allocate_ml))
  390. #    define FASTLOCK_SUCCEEDED() (GC_fastLockRes == PCR_ERes_okay)
  391. #    define FASTUNLOCK()  {\
  392.         if( FASTLOCK_SUCCEEDED() ) PCR_Th_ML_Release(&GC_allocate_ml); }
  393. #  endif
  394. #  ifdef SRC_M3
  395.      extern word RT0u__inCritical;
  396. #    define LOCK() RT0u__inCritical++
  397. #    define UNLOCK() RT0u__inCritical--
  398. #  endif
  399. #  ifdef SOLARIS_THREADS
  400. #    include <thread.h>
  401. #    include <signal.h>
  402.      extern mutex_t GC_allocate_ml;
  403. #    define LOCK() mutex_lock(&GC_allocate_ml);
  404. #    define UNLOCK() mutex_unlock(&GC_allocate_ml);
  405. #  endif
  406. # else
  407. #    define LOCK()
  408. #    define UNLOCK()
  409. # endif
  410.  
  411. # ifndef DCL_LOCK_STATE
  412. #   define DCL_LOCK_STATE
  413. # endif
  414. # ifndef FASTLOCK
  415. #   define FASTLOCK() LOCK()
  416. #   define FASTLOCK_SUCCEEDED() TRUE
  417. #   define FASTUNLOCK() UNLOCK()
  418. # endif
  419.  
  420. /* Delay any interrupts or signals that may abort this thread.  Data    */
  421. /* structures are in a consistent state outside this pair of calls.    */
  422. /* ANSI C allows both to be empty (though the standard isn't very    */
  423. /* clear on that point).  Standard malloc implementations are usually    */
  424. /* neither interruptable nor thread-safe, and thus correspond to    */
  425. /* empty definitions.                            */
  426. # ifdef PCR
  427. #   define DISABLE_SIGNALS() \
  428.          PCR_Th_SetSigMask(PCR_allSigsBlocked,&GC_old_sig_mask)
  429. #   define ENABLE_SIGNALS() \
  430.         PCR_Th_SetSigMask(&GC_old_sig_mask, NIL)
  431. # else
  432. #   if defined(SRC_M3) || defined(AMIGA) || defined(SOLARIS_THREADS) \
  433.     || defined(MSWIN32) || defined(MACOS) || defined(NO_SIGNALS)
  434.             /* Also useful for debugging.        */
  435.     /* Should probably use thr_sigsetmask for SOLARIS_THREADS. */
  436. #     define DISABLE_SIGNALS()
  437. #     define ENABLE_SIGNALS()
  438. #   else
  439. #     define DISABLE_SIGNALS() GC_disable_signals()
  440.     void GC_disable_signals();
  441. #     define ENABLE_SIGNALS() GC_enable_signals()
  442.     void GC_enable_signals();
  443. #   endif
  444. # endif
  445.  
  446. /*
  447.  * Stop and restart mutator threads.
  448.  */
  449. # ifdef PCR
  450. #     include "th/PCR_ThCtl.h"
  451. #     define STOP_WORLD() \
  452.      PCR_ThCtl_SetExclusiveMode(PCR_ThCtl_ExclusiveMode_stopNormal, \
  453.                     PCR_allSigsBlocked, \
  454.                     PCR_waitForever)
  455. #     define START_WORLD() \
  456.     PCR_ThCtl_SetExclusiveMode(PCR_ThCtl_ExclusiveMode_null, \
  457.                     PCR_allSigsBlocked, \
  458.                     PCR_waitForever);
  459. # else
  460. #   ifdef SOLARIS_THREADS
  461. #     define STOP_WORLD() GC_stop_world()
  462. #     define START_WORLD() GC_start_world()
  463. #   else
  464. #     define STOP_WORLD()
  465. #     define START_WORLD()
  466. #   endif
  467. # endif
  468.  
  469. /* Abandon ship */
  470. # ifdef PCR
  471. #   define ABORT(s) PCR_Base_Panic(s)
  472. # else
  473. #   ifdef SMALL_CONFIG
  474. #    define ABORT(msg) abort();
  475. #   else
  476.     void GC_abort();
  477. #       define ABORT(msg) GC_abort(msg);
  478. #   endif
  479. # endif
  480.  
  481. /* Exit abnormally, but without making a mess (e.g. out of memory) */
  482. # ifdef PCR
  483. #   define EXIT() PCR_Base_Exit(1,PCR_waitForever)
  484. # else
  485. #   define EXIT() (void)exit(1)
  486. # endif
  487.  
  488. /* Print warning message, e.g. almost out of memory.    */
  489. # define WARN(s) GC_printf0(s)
  490.  
  491. /*********************************/
  492. /*                               */
  493. /* Word-size-dependent defines   */
  494. /*                               */
  495. /*********************************/
  496.  
  497. #if CPP_WORDSZ == 32
  498. #  define WORDS_TO_BYTES(x)   ((x)<<2)
  499. #  define BYTES_TO_WORDS(x)   ((x)>>2)
  500. #  define LOGWL               ((word)5)    /* log[2] of CPP_WORDSZ */
  501. #  define modWORDSZ(n) ((n) & 0x1f)        /* n mod size of word        */
  502. #  if ALIGNMENT != 4
  503. #    define UNALIGNED
  504. #  endif
  505. #endif
  506.  
  507. #if CPP_WORDSZ == 64
  508. #  define WORDS_TO_BYTES(x)   ((x)<<3)
  509. #  define BYTES_TO_WORDS(x)   ((x)>>3)
  510. #  define LOGWL               ((word)6)    /* log[2] of CPP_WORDSZ */
  511. #  define modWORDSZ(n) ((n) & 0x3f)        /* n mod size of word        */
  512. #  if ALIGNMENT != 8
  513. #    define UNALIGNED
  514. #  endif
  515. #endif
  516.  
  517. #define WORDSZ ((word)CPP_WORDSZ)
  518. #define SIGNB  ((word)1 << (WORDSZ-1))
  519. #define BYTES_PER_WORD      ((word)(sizeof (word)))
  520. #define ONES                ((word)(-1))
  521. #define divWORDSZ(n) ((n) >> LOGWL)       /* divide n by size of word      */
  522.  
  523. /*********************/
  524. /*                   */
  525. /*  Size Parameters  */
  526. /*                   */
  527. /*********************/
  528.  
  529. /*  heap block size, bytes. Should be power of 2 */
  530.  
  531. #ifdef SMALL_CONFIG
  532. #   define CPP_LOG_HBLKSIZE 10
  533. #else
  534. # if CPP_WORDSZ == 32
  535. #   define CPP_LOG_HBLKSIZE 12
  536. # else
  537. #   define CPP_LOG_HBLKSIZE 13
  538. # endif
  539. #endif
  540. #define LOG_HBLKSIZE   ((word)CPP_LOG_HBLKSIZE)
  541. #define CPP_HBLKSIZE (1 << CPP_LOG_HBLKSIZE)
  542. #define HBLKSIZE ((word)CPP_HBLKSIZE)
  543.  
  544.  
  545. /*  max size objects supported by freelist (larger objects may be   */
  546. /*  allocated, but less efficiently)                                */
  547.  
  548. #define CPP_MAXOBJSZ    BYTES_TO_WORDS(CPP_HBLKSIZE/2)
  549. #define MAXOBJSZ ((word)CPP_MAXOBJSZ)
  550.         
  551. # define divHBLKSZ(n) ((n) >> LOG_HBLKSIZE)
  552.  
  553. # define HBLK_PTR_DIFF(p,q) divHBLKSZ((ptr_t)p - (ptr_t)q)
  554.     /* Equivalent to subtracting 2 hblk pointers.    */
  555.     /* We do it this way because a compiler should    */
  556.     /* find it hard to use an integer division    */
  557.     /* instead of a shift.  The bundled SunOS 4.1    */
  558.     /* o.w. sometimes pessimizes the subtraction to    */
  559.     /* involve a call to .div.            */
  560.  
  561. # define modHBLKSZ(n) ((n) & (HBLKSIZE-1))
  562.  
  563. # define HBLKPTR(objptr) ((struct hblk *)(((word) (objptr)) & ~(HBLKSIZE-1)))
  564.  
  565. # define HBLKDISPL(objptr) (((word) (objptr)) & (HBLKSIZE-1))
  566.  
  567. /* Round up byte allocation requests to integral number of words, etc. */
  568. # ifdef ADD_BYTE_AT_END
  569. #   define ROUNDED_UP_WORDS(n) BYTES_TO_WORDS((n) + WORDS_TO_BYTES(1))
  570. #   ifdef ALIGN_DOUBLE
  571. #       define ALIGNED_WORDS(n) (BYTES_TO_WORDS((n) + WORDS_TO_BYTES(2)) & ~1)
  572. #   else
  573. #       define ALIGNED_WORDS(n) ROUNDED_UP_WORDS(n)
  574. #   endif
  575. #   define SMALL_OBJ(bytes) ((bytes) < WORDS_TO_BYTES(MAXOBJSZ))
  576. #   define ADD_SLOP(bytes) ((bytes)+1)
  577. # else
  578. #   define ROUNDED_UP_WORDS(n) BYTES_TO_WORDS((n) + (WORDS_TO_BYTES(1) - 1))
  579. #   ifdef ALIGN_DOUBLE
  580. #       define ALIGNED_WORDS(n) \
  581.             (BYTES_TO_WORDS((n) + WORDS_TO_BYTES(2) - 1) & ~1)
  582. #   else
  583. #       define ALIGNED_WORDS(n) ROUNDED_UP_WORDS(n)
  584. #   endif
  585. #   define SMALL_OBJ(bytes) ((bytes) <= WORDS_TO_BYTES(MAXOBJSZ))
  586. #   define ADD_SLOP(bytes) (bytes)
  587. # endif
  588.  
  589.  
  590. /*
  591.  * Hash table representation of sets of pages.  This assumes it is
  592.  * OK to add spurious entries to sets.
  593.  * Used by black-listing code, and perhaps by dirty bit maintenance code.
  594.  */
  595.  
  596. # define LOG_PHT_ENTRIES  14    /* Collisions are likely if heap grows    */
  597.                 /* to more than 16K hblks = 64MB.    */
  598.                 /* Each hash table occupies 2K bytes.   */
  599. # define PHT_ENTRIES ((word)1 << LOG_PHT_ENTRIES)
  600. # define PHT_SIZE (PHT_ENTRIES >> LOGWL)
  601. typedef word page_hash_table[PHT_SIZE];
  602.  
  603. # define PHT_HASH(addr) ((((word)(addr)) >> LOG_HBLKSIZE) & (PHT_ENTRIES - 1))
  604.  
  605. # define get_pht_entry_from_index(bl, index) \
  606.         (((bl)[divWORDSZ(index)] >> modWORDSZ(index)) & 1)
  607. # define set_pht_entry_from_index(bl, index) \
  608.         (bl)[divWORDSZ(index)] |= (word)1 << modWORDSZ(index)
  609. # define clear_pht_entry_from_index(bl, index) \
  610.         (bl)[divWORDSZ(index)] &= ~((word)1 << modWORDSZ(index))
  611.     
  612.  
  613.  
  614. /********************************************/
  615. /*                                          */
  616. /*    H e a p   B l o c k s                 */
  617. /*                                          */
  618. /********************************************/
  619.  
  620. /*  heap block header */
  621. #define HBLKMASK   (HBLKSIZE-1)
  622.  
  623. #define BITS_PER_HBLK (HBLKSIZE * 8)
  624.  
  625. #define MARK_BITS_PER_HBLK (BITS_PER_HBLK/CPP_WORDSZ)
  626.        /* upper bound                                    */
  627.        /* We allocate 1 bit/word.  Only the first word   */
  628.        /* in each object is actually marked.             */
  629.  
  630. # ifdef ALIGN_DOUBLE
  631. #   define MARK_BITS_SZ (((MARK_BITS_PER_HBLK + 2*CPP_WORDSZ - 1) \
  632.               / (2*CPP_WORDSZ))*2)
  633. # else
  634. #   define MARK_BITS_SZ ((MARK_BITS_PER_HBLK + CPP_WORDSZ - 1)/CPP_WORDSZ)
  635. # endif
  636.        /* Upper bound on number of mark words per heap block  */
  637.  
  638. struct hblkhdr {
  639.     word hb_sz;  /* If in use, size in words, of objects in the block. */
  640.          /* if free, the size in bytes of the whole block      */
  641.     struct hblk * hb_next;     /* Link field for hblk free list     */
  642.                     /* and for lists of chunks waiting to be */
  643.                     /* reclaimed.                 */
  644.     word hb_descr;           /* object descriptor for marking.  See    */
  645.                     /* mark.h.                */
  646.     char* hb_map;    /* A pointer to a pointer validity map of the block. */
  647.                       /* See GC_obj_map.                     */
  648.                      /* Valid for all blocks with headers.             */
  649.                      /* Free blocks point to GC_invalid_map.             */
  650.     unsigned char hb_obj_kind;
  651.                  /* Kind of objects in the block.  Each kind     */
  652.                  /* identifies a mark procedure and a set of     */
  653.                  /* list headers.  Sometimes called regions.    */
  654.     unsigned char hb_flags;
  655. #    define IGNORE_OFF_PAGE    1    /* Ignore pointers that do not    */
  656.                     /* point to the first page of     */
  657.                     /* this object.            */
  658.     unsigned short hb_last_reclaimed;
  659.                     /* Value of GC_gc_no when block was    */
  660.                     /* last allocated or swept. May wrap.   */
  661.     word hb_marks[MARK_BITS_SZ];
  662.                 /* Bit i in the array refers to the             */
  663.                 /* object starting at the ith word (header      */
  664.                 /* INCLUDED) in the heap block.                 */
  665.                 /* The lsb of word 0 is numbered 0.            */
  666. };
  667.  
  668. /*  heap block body */
  669.  
  670. # define DISCARD_WORDS 0
  671.     /* Number of words to be dropped at the beginning of each block    */
  672.     /* Must be a multiple of WORDSZ.  May reasonably be nonzero    */
  673.     /* on machines that don't guarantee longword alignment of    */
  674.     /* pointers, so that the number of false hits is minimized.    */
  675.     /* 0 and WORDSZ are probably the only reasonable values.    */
  676.  
  677. # define BODY_SZ ((HBLKSIZE-WORDS_TO_BYTES(DISCARD_WORDS))/sizeof(word))
  678.  
  679. struct hblk {
  680. #   if (DISCARD_WORDS != 0)
  681.         word garbage[DISCARD_WORDS];
  682. #   endif
  683.     word hb_body[BODY_SZ];
  684. };
  685.  
  686. # define HDR_WORDS ((word)DISCARD_WORDS)
  687. # define HDR_BYTES ((word)WORDS_TO_BYTES(DISCARD_WORDS))
  688.  
  689. # define OBJ_SZ_TO_BLOCKS(sz) \
  690.     divHBLKSZ(HDR_BYTES + WORDS_TO_BYTES(sz) + HBLKSIZE-1)
  691.     /* Size of block (in units of HBLKSIZE) needed to hold objects of    */
  692.     /* given sz (in words).                        */
  693.  
  694. /* Object free list link */
  695. # define obj_link(p) (*(ptr_t *)(p))
  696.  
  697. /*  lists of all heap blocks and free lists    */
  698. /* These are grouped together in a struct    */
  699. /* so that they can be easily skipped by the    */
  700. /* GC_mark routine.                */
  701. /* The ordering is weird to make GC_malloc    */
  702. /* faster by keeping the important fields    */
  703. /* sufficiently close together that a        */
  704. /* single load of a base register will do.    */
  705. /* Scalars that could easily appear to        */
  706. /* be pointers are also put here.        */
  707.  
  708. struct _GC_arrays {
  709.   word _heapsize;
  710.   ptr_t _last_heap_addr;
  711.   ptr_t _prev_heap_addr;
  712.   word _words_allocd_before_gc;
  713.         /* Number of words allocated before this    */
  714.         /* collection cycle.                */
  715. # ifdef GATHERSTATS
  716.     word _composite_in_use;
  717.            /* Number of words in accessible composite    */
  718.         /* objects.                    */
  719.     word _atomic_in_use;
  720.            /* Number of words in accessible atomic        */
  721.         /* objects.                    */
  722. # endif
  723.   word _words_allocd;
  724.       /* Number of words allocated during this collection cycle */
  725.   word _words_wasted;
  726.       /* Number of words wasted due to internal fragmentation     */
  727.       /* in large objects allocated since last gc. Approximate.*/
  728.   word _non_gc_bytes_at_gc;
  729.       /* Number of explicitly managed bytes of storage     */
  730.       /* at last collection.                    */
  731.   word _mem_freed;
  732.       /* Number of explicitly deallocated words of memory    */
  733.       /* since last collection.                */
  734.       
  735.   ptr_t _objfreelist[MAXOBJSZ+1];
  736.               /* free list for objects */
  737. # ifdef MERGE_SIZES
  738.     unsigned _size_map[WORDS_TO_BYTES(MAXOBJSZ+1)];
  739.         /* Number of words to allocate for a given allocation request in */
  740.         /* bytes.                             */
  741. # endif 
  742.   ptr_t _aobjfreelist[MAXOBJSZ+1];
  743.               /* free list for atomic objs     */
  744.  
  745.   ptr_t _uobjfreelist[MAXOBJSZ+1];
  746.               /* uncollectable but traced objs     */
  747.  
  748. # ifdef STUBBORN_ALLOC
  749.     ptr_t _sobjfreelist[MAXOBJSZ+1];
  750. # endif
  751.                 /* free list for immutable objects    */
  752.   ptr_t _obj_map[MAXOBJSZ+1];
  753.                        /* If not NIL, then a pointer to a map of valid  */
  754.                    /* object addresses. _obj_map[sz][i] is j if the    */
  755.                    /* address block_start+i is a valid pointer      */
  756.                    /* to an object at                */
  757.                    /* block_start+i&~3 - WORDS_TO_BYTES(j).        */
  758.                    /* (If ALL_INTERIOR_POINTERS is defined, then    */
  759.                    /* instead ((short *)(hbh_map[sz])[i] is j if    */
  760.                    /* block_start+WORDS_TO_BYTES(i) is in the    */
  761.                    /* interior of an object starting at        */
  762.                    /* block_start+WORDS_TO_BYTES(i-j)).        */
  763.                    /* It is OBJ_INVALID if                */
  764.                    /* block_start+WORDS_TO_BYTES(i) is not        */
  765.                    /* valid as a pointer to an object.              */
  766.                    /* We assume all values of j <= OBJ_INVALID.    */
  767.                    /* The zeroth entry corresponds to large objects.*/
  768. #   ifdef ALL_INTERIOR_POINTERS
  769. #    define map_entry_type short
  770. #       define OBJ_INVALID 0x7fff
  771. #    define MAP_ENTRY(map, bytes) \
  772.         (((map_entry_type *)(map))[BYTES_TO_WORDS(bytes)])
  773. #    define MAP_ENTRIES BYTES_TO_WORDS(HBLKSIZE)
  774. #    define MAP_SIZE (MAP_ENTRIES * sizeof(map_entry_type))
  775. #    define OFFSET_VALID(displ) TRUE
  776. #    define CPP_MAX_OFFSET (HBLKSIZE - HDR_BYTES - 1)
  777. #    define MAX_OFFSET ((word)CPP_MAX_OFFSET)
  778. #   else
  779. #    define map_entry_type char
  780. #       define OBJ_INVALID 0x7f
  781. #    define MAP_ENTRY(map, bytes) \
  782.         (map)[bytes]
  783. #    define MAP_ENTRIES HBLKSIZE
  784. #    define MAP_SIZE MAP_ENTRIES
  785. #    define CPP_MAX_OFFSET (WORDS_TO_BYTES(OBJ_INVALID) - 1)    
  786. #    define MAX_OFFSET ((word)CPP_MAX_OFFSET)
  787. #     define VALID_OFFSET_SZ \
  788.       (CPP_MAX_OFFSET > WORDS_TO_BYTES(CPP_MAXOBJSZ)? \
  789.        CPP_MAX_OFFSET+1 \
  790.        : WORDS_TO_BYTES(CPP_MAXOBJSZ)+1)
  791.       char _valid_offsets[VALID_OFFSET_SZ];
  792.                 /* GC_valid_offsets[i] == TRUE ==> i     */
  793.                 /* is registered as a displacement.    */
  794. #    define OFFSET_VALID(displ) GC_valid_offsets[displ]
  795.       char _modws_valid_offsets[sizeof(word)];
  796.                 /* GC_valid_offsets[i] ==>          */
  797.                 /* GC_modws_valid_offsets[i%sizeof(word)] */
  798. #   endif
  799. # ifdef STUBBORN_ALLOC
  800.       page_hash_table _changed_pages;
  801.         /* Stubborn object pages that were changes since last call to    */
  802.     /* GC_read_changed.                        */
  803.       page_hash_table _prev_changed_pages;
  804.         /* Stubborn object pages that were changes before last call to    */
  805.     /* GC_read_changed.                        */
  806. # endif
  807. # if defined(PROC_VDB) || defined(MPROTECT_VDB)
  808.       page_hash_table _grungy_pages; /* Pages that were dirty at last        */
  809.                      /* GC_read_dirty.               */
  810. # endif
  811. # define MAX_HEAP_SECTS 256    /* Separately added heap sections. */
  812.   struct HeapSect {
  813.       ptr_t hs_start; word hs_bytes;
  814.   } _heap_sects[MAX_HEAP_SECTS];
  815. # ifdef MSWIN32
  816.     ptr_t _heap_bases[MAX_HEAP_SECTS];
  817.             /* Start address of memory regions obtained from kernel. */
  818. # endif
  819.   /* Block header index; see gc_headers.h */
  820.   bottom_index * _all_nils;
  821.   bottom_index * _top_index [TOP_SZ];
  822. #ifdef SAVE_CALL_CHAIN
  823.   struct callinfo _last_stack[NFRAMES];    /* Stack at last garbage collection.*/
  824.                       /* Useful for debugging    mysterious  */
  825.                       /* object disappearances.        */
  826.                       /* In the multithreaded case, we    */
  827.                       /* currently only save the calling  */
  828.                       /* stack.                */
  829. #endif
  830. };
  831.  
  832. extern GC_FAR struct _GC_arrays GC_arrays; 
  833.  
  834. # define GC_objfreelist GC_arrays._objfreelist
  835. # define GC_aobjfreelist GC_arrays._aobjfreelist
  836. # define GC_uobjfreelist GC_arrays._uobjfreelist
  837. # define GC_sobjfreelist GC_arrays._sobjfreelist
  838. # define GC_valid_offsets GC_arrays._valid_offsets
  839. # define GC_modws_valid_offsets GC_arrays._modws_valid_offsets
  840. # ifdef STUBBORN_ALLOC
  841. #    define GC_changed_pages GC_arrays._changed_pages
  842. #    define GC_prev_changed_pages GC_arrays._prev_changed_pages
  843. # endif
  844. # define GC_obj_map GC_arrays._obj_map
  845. # define GC_last_heap_addr GC_arrays._last_heap_addr
  846. # define GC_prev_heap_addr GC_arrays._prev_heap_addr
  847. # define GC_words_allocd GC_arrays._words_allocd
  848. # define GC_words_wasted GC_arrays._words_wasted
  849. # define GC_non_gc_bytes_at_gc GC_arrays._non_gc_bytes_at_gc
  850. # define GC_mem_freed GC_arrays._mem_freed
  851. # define GC_heapsize GC_arrays._heapsize
  852. # define GC_words_allocd_before_gc GC_arrays._words_allocd_before_gc
  853. # define GC_heap_sects GC_arrays._heap_sects
  854. # define GC_last_stack GC_arrays._last_stack
  855. # ifdef MSWIN32
  856. #   define GC_heap_bases GC_arrays._heap_bases
  857. # endif
  858. # define GC_all_nils GC_arrays._all_nils
  859. # define GC_top_index GC_arrays._top_index
  860. # if defined(PROC_VDB) || defined(MPROTECT_VDB)
  861. #   define GC_grungy_pages GC_arrays._grungy_pages
  862. # endif
  863. # ifdef GATHERSTATS
  864. #   define GC_composite_in_use GC_arrays._composite_in_use
  865. #   define GC_atomic_in_use GC_arrays._atomic_in_use
  866. # endif
  867. # ifdef MERGE_SIZES
  868. #   define GC_size_map GC_arrays._size_map
  869. # endif
  870.  
  871. # define beginGC_arrays ((ptr_t)(&GC_arrays))
  872. # define endGC_arrays (((ptr_t)(&GC_arrays)) + (sizeof GC_arrays))
  873.  
  874.  
  875. # define MAXOBJKINDS 16
  876.  
  877. /* Object kinds: */
  878. extern struct obj_kind {
  879.    ptr_t *ok_freelist;    /* Array of free listheaders for this kind of object */
  880.                /* Point either to GC_arrays or to storage allocated */
  881.                /* with GC_scratch_alloc.                 */
  882.    struct hblk **ok_reclaim_list;
  883.                /* List headers for lists of blocks waiting to be */
  884.                /* swept.                      */
  885.    word ok_descriptor;  /* Descriptor template for objects in this    */
  886.                /* block.                    */
  887.    bool ok_relocate_descr;
  888.                /* Add object size in bytes to descriptor     */
  889.                /* template to obtain descriptor.  Otherwise    */
  890.                /* template is used as is.            */
  891.    bool ok_init;     /* Clear objects before putting them on the free list. */
  892. } GC_obj_kinds[MAXOBJKINDS];
  893. /* Predefined kinds: */
  894. # define PTRFREE 0
  895. # define NORMAL  1
  896. # define UNCOLLECTABLE 2
  897. # define STUBBORN 3
  898.  
  899. extern int GC_n_kinds;
  900.  
  901. extern word GC_n_heap_sects;    /* Number of separately added heap    */
  902.                 /* sections.                */
  903.  
  904. # ifdef MSWIN32
  905. extern word GC_n_heap_bases;    /* See GC_heap_bases.    */
  906. # endif
  907.  
  908. extern char * GC_invalid_map;
  909.             /* Pointer to the nowhere valid hblk map */
  910.             /* Blocks pointing to this map are free. */
  911.  
  912. extern struct hblk * GC_hblkfreelist;
  913.                 /* List of completely empty heap blocks    */
  914.                 /* Linked through hb_next field of     */
  915.                 /* header structure associated with    */
  916.                 /* block.                */
  917.  
  918. extern bool GC_is_initialized;        /* GC_init() has been run.    */
  919.  
  920. extern bool GC_objects_are_marked;    /* There are marked objects in  */
  921.                     /* the heap.            */
  922.  
  923. extern int GC_incremental;  /* Using incremental/generational collection. */
  924.  
  925. extern bool GC_dirty_maintained;/* Dirty bits are being maintained,     */
  926.                 /* either for incremental collection,    */
  927.                 /* or to limit the root set.        */
  928.  
  929. # ifndef PCR
  930.     extern ptr_t GC_stackbottom;    /* Cool end of user stack    */
  931. # endif
  932.  
  933. extern word GC_root_size;    /* Total size of registered root sections */
  934.  
  935. extern bool GC_debugging_started;    /* GC_debug_malloc has been called. */ 
  936.  
  937. extern ptr_t GC_least_plausible_heap_addr;
  938. extern ptr_t GC_greatest_plausible_heap_addr;
  939.             /* Bounds on the heap.  Guaranteed valid    */
  940.             /* Likely to include future heap expansion.    */
  941.             
  942. /* Operations */
  943. # ifndef abs
  944. #   define abs(x)  ((x) < 0? (-(x)) : (x))
  945. # endif
  946.  
  947.  
  948. /*  Marks are in a reserved area in                          */
  949. /*  each heap block.  Each word has one mark bit associated  */
  950. /*  with it. Only those corresponding to the beginning of an */
  951. /*  object are used.                                         */
  952.  
  953.  
  954. /* Mark bit perations */
  955.  
  956. /*
  957.  * Retrieve, set, clear the mark bit corresponding
  958.  * to the nth word in a given heap block.
  959.  *
  960.  * (Recall that bit n corresponds to object beginning at word n
  961.  * relative to the beginning of the block, including unused words)
  962.  */
  963.  
  964. # define mark_bit_from_hdr(hhdr,n) (((hhdr)->hb_marks[divWORDSZ(n)] \
  965.                 >> (modWORDSZ(n))) & (word)1)
  966. # define set_mark_bit_from_hdr(hhdr,n) (hhdr)->hb_marks[divWORDSZ(n)] \
  967.                 |= (word)1 << modWORDSZ(n)
  968.  
  969. # define clear_mark_bit_from_hdr(hhdr,n) (hhdr)->hb_marks[divWORDSZ(n)] \
  970.                 &= ~((word)1 << modWORDSZ(n))
  971.  
  972. /* Important internal collector routines */
  973.  
  974. void GC_apply_to_all_blocks(/*fn, client_data*/);
  975.             /* Invoke fn(hbp, client_data) for each     */
  976.             /* allocated heap block.            */
  977. struct hblk * GC_next_block(/* struct hblk * h */);
  978. void GC_mark_init();
  979. void GC_clear_marks();    /* Clear mark bits for all heap objects. */
  980. void GC_mark_from_mark_stack(); /* Mark from everything on the mark stack. */
  981.                 /* Return after about one pages worth of   */
  982.                 /* work.                   */
  983. bool GC_mark_stack_empty();
  984. bool GC_mark_some();    /* Perform about one pages worth of marking    */
  985.             /* work of whatever kind is needed.  Returns    */
  986.             /* quickly if no collection is in progress.    */
  987.             /* Return TRUE if mark phase finished.        */
  988. void GC_initiate_full();    /* initiate full collection.        */
  989. void GC_initiate_partial();    /* initiate partial collection.        */            
  990. void GC_push_all(/*b,t*/);    /* Push everything in a range         */
  991.                 /* onto mark stack.            */
  992. void GC_push_dirty(/*b,t*/);      /* Push all possibly changed         */
  993.                   /* subintervals of [b,t) onto        */
  994.                   /* mark stack.            */
  995. #ifndef SMALL_CONFIG
  996.   void GC_push_conditional(/* ptr_t b, ptr_t t, bool all*/);
  997. #else
  998. # define GC_push_conditional(b, t, all) GC_push_all(b, t)
  999. #endif
  1000.                                 /* Do either of the above, depending    */
  1001.                 /* on the third arg.            */
  1002. void GC_push_all_stack(/*b,t*/);    /* As above, but consider        */
  1003.                     /*  interior pointers as valid      */
  1004. void GC_push_roots(/* bool all */); /* Push all or dirty roots.    */
  1005. extern void (*GC_push_other_roots)();
  1006.             /* Push system or application specific roots    */
  1007.             /* onto the mark stack.  In some environments    */
  1008.             /* (e.g. threads environments) this is        */
  1009.             /* predfined to be non-zero.  A client supplied */
  1010.             /* replacement should also call the original    */
  1011.             /* function.                    */
  1012. void GC_push_regs();    /* Push register contents onto mark stack.    */
  1013. void GC_remark();    /* Mark from all marked objects.  Used    */
  1014.              /* only if we had to drop something.    */
  1015. void GC_push_one(/*p*/);    /* If p points to an object, mark it    */
  1016.                 /* and push contents on the mark stack    */
  1017. void GC_push_one_checked(/*p*/); /* Ditto, omits plausibility test    */
  1018. void GC_push_marked(/* struct hblk h, hdr * hhdr */);
  1019.         /* Push contents of all marked objects in h onto    */
  1020.         /* mark stack.                        */
  1021. #ifdef SMALL_CONFIG
  1022. # define GC_push_next_marked_dirty(h) GC_push_next_marked(h)
  1023. #else
  1024.   struct hblk * GC_push_next_marked_dirty(/* h */);
  1025.         /* Invoke GC_push_marked on next dirty block above h.    */
  1026.         /* Return a pointer just past the end of this block.    */
  1027. #endif /* !SMALL_CONFIG */
  1028. struct hblk * GC_push_next_marked(/* h */);
  1029.         /* Ditto, but also mark from clean pages.    */
  1030. struct hblk * GC_push_next_marked_uncollectable(/* h */);
  1031.         /* Ditto, but mark only from uncollectable pages.    */
  1032. bool GC_stopped_mark(); /* Stop world and mark from all roots    */
  1033.             /* and rescuers.            */
  1034. void GC_clear_hdr_marks(/* hhdr */);  /* Clear the mark bits in a header */
  1035. void GC_add_roots_inner();
  1036. bool GC_is_static_root(/* ptr_t p */);
  1037.         /* Is the address p in one of the registered static    */
  1038.         /* root sections?                    */
  1039. void GC_register_dynamic_libraries();
  1040.         /* Add dynamic library data sections to the root set. */
  1041.  
  1042. /* Machine dependent startup routines */
  1043. ptr_t GC_get_stack_base();
  1044. void GC_register_data_segments();
  1045.  
  1046. /* Black listing: */
  1047. void GC_bl_init();     
  1048. # ifndef ALL_INTERIOR_POINTERS
  1049.     void GC_add_to_black_list_normal(/* bits */);
  1050.             /* Register bits as a possible future false    */
  1051.             /* reference from the heap or static data    */
  1052. #   define GC_ADD_TO_BLACK_LIST_NORMAL(bits) GC_add_to_black_list_normal(bits)
  1053. # else
  1054. #   define GC_ADD_TO_BLACK_LIST_NORMAL(bits) GC_add_to_black_list_stack(bits)
  1055. # endif
  1056.  
  1057. void GC_add_to_black_list_stack(/* bits */);
  1058. struct hblk * GC_is_black_listed(/* h, len */);
  1059.             /* If there are likely to be false references    */
  1060.             /* to a block starting at h of the indicated    */
  1061.             /* length, then return the next plausible    */
  1062.             /* starting location for h that might avoid    */
  1063.             /* these false references.            */
  1064. void GC_promote_black_lists();
  1065.             /* Declare an end to a black listing phase.    */
  1066.              
  1067. ptr_t GC_scratch_alloc(/*bytes*/);
  1068.                 /* GC internal memory allocation for    */
  1069.                 /* small objects.  Deallocation is not  */
  1070.                 /* possible.                */
  1071.     
  1072. /* Heap block layout maps: */            
  1073. void GC_invalidate_map(/* hdr */);
  1074.                 /* Remove the object map associated    */
  1075.                 /* with the block.  This identifies    */
  1076.                 /* the block as invalid to the mark    */
  1077.                 /* routines.                */
  1078. bool GC_add_map_entry(/*sz*/);
  1079.                 /* Add a heap block map for objects of    */
  1080.                 /* size sz to obj_map.            */
  1081.                 /* Return FALSE on failure.        */
  1082. void GC_register_displacement_inner(/*offset*/);
  1083.                 /* Version of GC_register_displacement    */
  1084.                 /* that assumes lock is already held    */
  1085.                 /* and signals are already disabled.    */
  1086.  
  1087. /*  hblk allocation: */        
  1088. void GC_new_hblk(/*size_in_words, kind*/);
  1089.                 /* Allocate a new heap block, and build */
  1090.                 /* a free list in it.            */                
  1091. struct hblk * GC_allochblk(/*size_in_words, kind*/);
  1092.                 /* Allocate a heap block, clear it if    */
  1093.                 /* for composite objects, inform    */
  1094.                 /* the marker that block is valid    */
  1095.                 /* for objects of indicated size.    */
  1096.                 /* sz < 0 ==> atomic.            */ 
  1097. void GC_freehblk();        /* Deallocate a heap block and mark it  */
  1098.                 /* as invalid.                */
  1099.                 
  1100. /*  Misc GC: */
  1101. void GC_init_inner();
  1102. bool GC_expand_hp_inner();
  1103. void GC_start_reclaim(/*abort_if_found*/);
  1104.                 /* Restore unmarked objects to free    */
  1105.                 /* lists, or (if abort_if_found is    */
  1106.                 /* TRUE) report them.            */
  1107.                 /* Sweeping of small object pages is    */
  1108.                 /* largely deferred.            */
  1109. void GC_continue_reclaim(/*size, kind*/);
  1110.                 /* Sweep pages of the given size and    */
  1111.                 /* kind, as long as possible, and    */
  1112.                 /* as long as the corr. free list is    */
  1113.                 /* empty.                */
  1114. void GC_reclaim_or_delete_all();
  1115.                 /* Arrange for all reclaim lists to be    */
  1116.                 /* empty.  Judiciously choose between    */
  1117.                 /* sweeping and discarding each page.    */
  1118. bool GC_block_empty(/* hhdr */); /* Block completely unmarked?     */
  1119. void GC_gcollect_inner();
  1120.                 /* Collect; caller must have acquired    */
  1121.                 /* lock and disabled signals.        */
  1122.                 /* FALSE return indicates nothing was    */
  1123.                 /* done due to insufficient allocation. */
  1124. void GC_finish_collection();    /* Finish collection.  Mark bits are    */
  1125.                 /* consistent and lock is still held.    */
  1126. bool GC_collect_or_expand(/* needed_blocks */);
  1127.                 /* Collect or expand heap in an attempt */
  1128.                 /* make the indicated number of free    */
  1129.                 /* blocks available.  Should be called    */
  1130.                 /* until it fails by returning FALSE.    */
  1131. void GC_init();            /* Initialize collector.        */
  1132. void GC_collect_a_little_inner(/* int n */);
  1133.                 /* Do n units worth of garbage         */
  1134.                 /* collection work, if appropriate.    */
  1135.                 /* A unit is an amount appropriate for  */
  1136.                 /* HBLKSIZE bytes of allocation.    */
  1137. ptr_t GC_generic_malloc(/* bytes, kind */);
  1138.                 /* Allocate an object of the given    */
  1139.                 /* kind.  By default, there are only    */
  1140.                 /* two kinds: composite, and atomic.    */
  1141.                 /* We claim it's possible for clever    */
  1142.                 /* client code that understands GC    */
  1143.                 /* internals to add more, e.g. to    */
  1144.                 /* communicate object layout info    */
  1145.                 /* to the collector.            */
  1146. ptr_t GC_generic_malloc_inner(/* bytes, kind */);
  1147.                 /* Ditto, but I already hold lock, etc.    */
  1148. ptr_t GC_generic_malloc_words_small(/*words, kind*/);
  1149.                 /* As above, but size in units of words */
  1150.                 /* Bypasses MERGE_SIZES.  Assumes    */
  1151.                 /* words <= MAXOBJSZ.            */
  1152. ptr_t GC_generic_malloc_inner_ignore_off_page(/* bytes, kind */);
  1153.                 /* Allocate an object, where        */
  1154.                 /* the client guarantees that there    */
  1155.                 /* will always be a pointer to the     */
  1156.                 /* beginning of the object while the    */
  1157.                 /* object is live.            */
  1158. ptr_t GC_allocobj(/* sz_inn_words, kind */);
  1159.                 /* Make the indicated             */
  1160.                 /* free list nonempty, and return its    */
  1161.                 /* head.                */
  1162.  
  1163. void GC_init_headers();
  1164. bool GC_install_header(/*h*/);
  1165.                 /* Install a header for block h.    */
  1166.                 /* Return FALSE on failure.        */
  1167. bool GC_install_counts(/*h, sz*/);
  1168.                 /* Set up forwarding counts for block    */
  1169.                 /* h of size sz.            */
  1170.                 /* Return FALSE on failure.        */
  1171. void GC_remove_header(/*h*/);
  1172.                 /* Remove the header for block h.    */
  1173. void GC_remove_counts(/*h, sz*/);
  1174.                 /* Remove forwarding counts for h.    */
  1175. hdr * GC_find_header(/*p*/);    /* Debugging only.            */
  1176.  
  1177. void GC_finalize();    /* Perform all indicated finalization actions    */
  1178.             /* on unmarked objects.                */
  1179.             /* Unreachable finalizable objects are enqueued    */
  1180.             /* for processing by GC_invoke_finalizers.    */
  1181.             /* Invoked with lock.                */
  1182. void GC_invoke_finalizers();     /* Run eligible finalizers.    */
  1183.                 /* Invoked without lock.    */    
  1184.             
  1185. void GC_add_to_heap(/*p, bytes*/);
  1186.             /* Add a HBLKSIZE aligned chunk to the heap.    */
  1187.  
  1188. void GC_print_obj(/* ptr_t p */);
  1189.             /* P points to somewhere inside an object with    */
  1190.             /* debugging info.  Print a human readable    */
  1191.             /* description of the object to stderr.        */
  1192. extern void (*GC_check_heap)();
  1193.             /* Check that all objects in the heap with     */
  1194.             /* debugging info are intact.  Print         */
  1195.             /* descriptions of any that are not.        */
  1196.             
  1197. /* Virtual dirty bit implementation:        */
  1198. /* Each implementation exports the following:    */
  1199. void GC_read_dirty();    /* Retrieve dirty bits.    */
  1200. bool GC_page_was_dirty(/* struct hblk * h  */);
  1201.             /* Read retrieved dirty bits.    */
  1202. bool GC_page_was_ever_dirty(/* struct hblk * h  */);
  1203.             /* Could the page contain valid heap pointers?    */
  1204. void GC_is_fresh(/* struct hblk * h, word number_of_blocks  */);
  1205.             /* Assert the region currently contains no    */
  1206.             /* valid pointers.                */
  1207. void GC_write_hint(/* struct hblk * h  */);
  1208.             /* h is about to be written.    */
  1209. void GC_dirty_init();
  1210.  
  1211. /* Slow/general mark bit manipulation: */
  1212. bool GC_is_marked();
  1213. void GC_clear_mark_bit();
  1214. void GC_set_mark_bit();
  1215.  
  1216. /* Stubborn objects: */
  1217. void GC_read_changed();    /* Analogous to GC_read_dirty */
  1218. bool GC_page_was_changed(/* h */);    /* Analogous to GC_page_was_dirty */
  1219. void GC_clean_changing_list();    /* Collect obsolete changing list entries */
  1220. void GC_stubborn_init();
  1221.  
  1222. /* Debugging print routines: */
  1223. void GC_print_block_list();
  1224. void GC_print_hblkfreelist();
  1225.  
  1226. /* Make arguments appear live to compiler */
  1227. void GC_noop();
  1228.  
  1229. /* Logging and diagnostic output:     */
  1230. void GC_printf(/* format, a, b, c, d, e, f */);
  1231.             /* A version of printf that doesn't allocate,    */
  1232.             /* is restricted to long arguments, and        */
  1233.             /* (unfortunately) doesn't use varargs for    */
  1234.             /* portability.  Restricted to 6 args and    */
  1235.             /* 1K total output length.            */
  1236.             /* (We use sprintf.  Hopefully that doesn't    */
  1237.             /* allocate for long arguments.)          */
  1238. # define GC_printf0(f) GC_printf(f, 0l, 0l, 0l, 0l, 0l, 0l)
  1239. # define GC_printf1(f,a) GC_printf(f, (long)a, 0l, 0l, 0l, 0l, 0l)
  1240. # define GC_printf2(f,a,b) GC_printf(f, (long)a, (long)b, 0l, 0l, 0l, 0l)
  1241. # define GC_printf3(f,a,b,c) GC_printf(f, (long)a, (long)b, (long)c, 0l, 0l, 0l)
  1242. # define GC_printf4(f,a,b,c,d) GC_printf(f, (long)a, (long)b, (long)c, \
  1243.                         (long)d, 0l, 0l)
  1244. # define GC_printf5(f,a,b,c,d,e) GC_printf(f, (long)a, (long)b, (long)c, \
  1245.                           (long)d, (long)e, 0l)
  1246. # define GC_printf6(f,a,b,c,d,e,g) GC_printf(f, (long)a, (long)b, (long)c, \
  1247.                         (long)d, (long)e, (long)g)
  1248.  
  1249. void GC_err_printf(/* format, a, b, c, d, e, f */);
  1250. # define GC_err_printf0(f) GC_err_puts(f)
  1251. # define GC_err_printf1(f,a) GC_err_printf(f, (long)a, 0l, 0l, 0l, 0l, 0l)
  1252. # define GC_err_printf2(f,a,b) GC_err_printf(f, (long)a, (long)b, 0l, 0l, 0l, 0l)
  1253. # define GC_err_printf3(f,a,b,c) GC_err_printf(f, (long)a, (long)b, (long)c, \
  1254.                           0l, 0l, 0l)
  1255. # define GC_err_printf4(f,a,b,c,d) GC_err_printf(f, (long)a, (long)b, \
  1256.                             (long)c, (long)d, 0l, 0l)
  1257. # define GC_err_printf5(f,a,b,c,d,e) GC_err_printf(f, (long)a, (long)b, \
  1258.                               (long)c, (long)d, \
  1259.                               (long)e, 0l)
  1260. # define GC_err_printf6(f,a,b,c,d,e,g) GC_err_printf(f, (long)a, (long)b, \
  1261.                             (long)c, (long)d, \
  1262.                             (long)e, (long)g)
  1263.             /* Ditto, writes to stderr.            */
  1264.             
  1265. void GC_err_puts(/* char *s */);
  1266.             /* Write s to stderr, don't buffer, don't add    */
  1267.             /* newlines, don't ...                */
  1268.  
  1269. # endif /* GC_PRIVATE_H */
  1270.