/* begincopyright
Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
Use and copying of this software and preparation of derivative works based
upon this software are permitted. Any distribution of this software or
derivative works must comply with all applicable United States export
control laws. This software is made available AS IS, and Xerox Corporation
makes no warranty about the software, its performance or its conformity to
any specification. Any person obtaining a copy of this software is requested
to send their name and post office or electronic mail address to:
PCR Coordinator
Xerox PARC
3333 Coyote Hill Rd.
Palo Alto, CA 94304
Parts of this software were derived from code bearing the copyright notice:
Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
This material may be freely distributed, provided this notice is retained.
This material is provided as is, with no warranty expressed or implied.
Use at your own risk.
endcopyright */
/*
* GC.h
*
* Basic public type definitions for Xerox Runtime
* storage managment package.
*
* Mark Weiser, October 18, 1989
* Alan Ishigo, November 14, 1988 4:38:01 pm PST
* Demers, October 24, 1989 1:58:02 pm PDT
* Boehm, July 19, 1990 1:18:27 pm PDT
*
*/
#ifndef ←XR←GC←
#define ←XR←GC← 1
#ifndef ←XR←BASIC←TYPES←
#include "xr/BasicTypes.h"
#endif
/* The garbage collector used to assume sizeof (bool) = sizeof (long) */
/* It may still. */
#ifndef ←XR←THREADS←
#include "xr/Threads.h"
#endif
/* Public variables. May be altered by client. */
extern bool GC←dont←gc; /* inhibit collection */
extern bool GC←markCarefully;
/* Try to keep working set down during marking, */
/* at the expense of about a factor of 2 in cpu */
/* time. Ignored during partial collections. */
/* Setting or clearing this has only a transient */
/* effect, up to at least the next collection. */
extern bool GC←ok←to←panic; /* OK to call XR←panic if things go completely */
/* haywire. */
extern unsigned GC←partial←gc←allocs;
/* Number of words to be allocated between */
/* partial collections. */
/* 0 ==> use default value based on number */
/* of composite objects in use. */
extern unsigned GC←full←gc←allocs;
/* Number of words to be allocated between */
/* full collections. 0 ==> collect only when */
/* heap is full. */
extern unsigned GC←free←mem←ratio;
/* Collector tries to expand heap until */
/* 2*GC←composite←in←use/GC←free←mem←ratio */
/* words are reclaimed at full collections. */
/* Greater values imply smaller heaps, but */
/* risk excessive GC frequency. */
/* This is all very approximate. */
extern bool GC←fix←heap←size; /* Avoid expanding the heap if at all possible. */
extern unsigned long GC←max←heap←size;
/* An attempt to expand the heap past this */
/* amount will fail. */
typedef void (*GC←expand←call←back←type)(/*XR←Pointer client←data*/);
void GC←register←expand←callback(/* GC←expand←call←back←type fn,
XR←Pointer data,
GC←expand←call←back←type *Ofn,
XR←Pointer *Odata */);
/* Register a function to be called when the collector would have */
/* liked to expand the heap, but couldn't. The callback function */
/* can't safely do much other than set a global flag or increase */
/* GC←max←heap←size. */
/* Public variables. Read only for the client. Set by collector. */
extern char * GC←heapstart; /* A lower bound on all heap addresses */
/* Known to be HBLKSIZE aligned. */
/* Zero before GC initialization. */
extern char * GC←heaplim; /* 1 + last address in heap */
extern long GC←heapsize; /* Heap size in bytes */
extern char * GC←sys←mem←end; /* 1 + end of memory allocated from system. */
/* May differ from GC←heaplim if other */
/* allocation, e.g. for block headers */
/* is going on. */
extern long GC←mem←found; /* Number of words reclaimed since start of last */
/* collection. Only a lower bound. */
extern long GC←mem←freed; /* Number of longwords explicitly */
/* freed since last garbage collection. */
extern long GC←composite←in←use; /* Number of longwords in accessible */
/* composite objects. */
extern long GC←atomic←in←use; /* Number of longwords in accessible atomic */
/* objects. */
/* Both of the above numbers are good upper */
/* bounds, as of the last collection. */
extern long GC←objects←in←use; /* Number of live objects found during last */
/* collection. */
extern bool GC←running←exclusive; /* True if a single process has taken */
/* over all the processors. */
extern bool GC←collection←in←progress;
/* A parallel collection is currently */
/* running. Changed to true only while */
/* GC←allocate←ml is held. */
/* Currently not set during stop-the-world */
/* collections. */
extern char XR←gcVersion[]; /* read-only */
/* Publically readable variables that may not remain meaningful */
/* if the collector changes. Should be used only in disposable code. */
extern long GC←markfaults; /* The number of page faults that occurred during */
/* the last mark phase. */
extern long GC←max←markfaults; /* The recent max of above */
extern long GC←gc←no; /* How many times have we collected? */
extern bool GC←full←gc; /* A full collection is in progress */
extern bool GC←after←full; /* Cleaning up a full GC */
extern long GC←tenure←count; /* Number of tenured blocks */
extern int GC←n←maps←cached;
/* The number of heap block maps currently in the cache */
extern int GC←words←at←full←gc; /* Words accessible after last full */
/* collection. */
extern int GC←composite←at←full←gc; /* Composite words accessible */
/* after last full collection. */
/* The following are meaningful for any collector, but can only be */
/* maintained at significant expense, and may thus eventually disappear. */
/* The object counts are more likely to disappear, since they are */
/* useless to the collector itself. */
extern unsigned GC←words←allocd;
/* Number of words allocated since last collection */
extern unsigned GC←words←allocd←before←gc;
/* Words allocated up to last garbage */
/* collection. The sum of this and the */
/* preceding variable is the total */
/* number of words allocated since the */
/* beginning of the world. */
extern unsigned GC←objects←allocd; /* Number of objects allocated since last */
/* collection. */
extern unsigned GC←objects←allocd←before←gc;
/* Objects allocated up to last */
/* garbage collection. */
/* All routines in the GC interface start with either XR← or GC←. Internal */
/* routines start with GC←. */
/***** Informational Routines *****/
extern unsigned GC←size(/* XR←Pointer p */);
/* Return the number of bytes allocated for p. May be larger than */
/* originally requested allocation size. */
extern unsigned
XR←GCCurrentByteCount();
/* Return the current number of bytes allocated.
This number increases continuously (at each allocation) but shrinks
only after collections. */
extern unsigned
XR←GCCurrentObjectCount();
/* Return the current number of objects allocated.
This number increases continuously (at each allocation) but shrinks
only after collections.
*/
extern unsigned
XR←GCTotalByteCount();
/* Return the current number of bytes allocated. This number increases
continuously.
*/
extern unsigned
XR←GCTotalObjectCount();
/* Return the current number of bytes allocated.
This number increases continuously.
*/
extern bool
XR←NfreePagesP(/* unsigned N */);
/*
* Returns 1 if at least N GC pages (i.e. hblocks) are free (no
* objects at all on them) and 0 otherwise.
* (Written this way, rather than just to return the number of free
* pages, to keep working set down by truncating search.)
*/
/***** Routines to Control Behavior *****/
/* The ...Set... routines always return the old value. */
extern bool
XR←GCGetNeverCollectAtAll(), XR←GCSetNeverCollectAtAll(/* bool */);
/* A value of TRUE causes no collection activity whatsoever.
A value of FALSE causes normal collection behavior (subject to the
NeverFree boolean).
*/
extern unsigned
XR←GCHeapSize();
/* Returns the size of the heap in bytes. */
extern void
GC←explicitly←managed(/* int incr */);
/* Increment the amount of explicitly managed memory currently in use. */
/* Used only for scheduling garbage collections. */
/* Should be called with a positive argument before allocating */
/* explicitly managed storage, and with a negative argument after */
/* deallocating it. */
extern bool
XR←Increase←Heap(/* unsigned */);
/* The heap is grown by the indicated number of bytes, rounded up to
a pagesize. Returns true if successful, false otherwise.
*/
extern bool
XR←GCSetMarkCarefully(/* bool */), XR←GCGetMarkCarefully( /* bool */);
/* If this switch is set, then the objects to be marked are kept
sorted in page order so as to reduce paging behavior, at the obvious
cost of cpu time. The switch is set by the collector after excessive
paging activity, and reset after a full collection with low paging
activity.
*/
extern unsigned
XR←GCSetMode(/* unsigned */);
# define GC←INCREMENTAL 1
# define GC←PARALLEL 2
/* Turn on or off parallel and or incremental collection. Default with */
/* STICKY←MARK←BITS defined is both. For batch processes it pays to */
/* turn off GC←PARALLEL. For short-lived batch processes, and/or */
/* batch processes in small address spaces, it pays to turn both off. */
/* Turning both off will usually remove virtual dirty bit overhead. */
unsigned
XR←SetBytesAfterWhichToCollect(/* unsigned */), XR←GetBytesAfterWhichToCollect();
/* A non-zero value causes a collection whenever this many bytes have
been allocated since the last collection.
*/
void
XR←CollectOnlyWhenFull(), XR←CollectAfterTwoMegabytes(), XR←CollectAfterOneMegabyte();
/*
Convenient access to XR←SetBytesAfterWhichToCollect for folks
without access to arguments (e.g., via the 'pcr:' prompt.)
*/
/***** Routines to cause behavior. *****/
/* These routines are all monitored and safe to call at any time.
They are the basic interfaces into storage management.
*/
void
XR←GCollect();
/* initiate a garbage collection. */
void XR←GCollect2(/* bool wait, bool full */);
/* As above; wait ==> return only when finished; full ==> force full */
/* collection; wait && full also implies stop the world. */
/* general purpose allocation routines: */
XR←Pointer
GC←malloc(/* unsigned ObjectSizeInBytes */);
/* Allocates a new object of at least the specified length. The object is
cleared. It will be aligned on at least a 4 byte boundary. If the
architecture requires n byte alignment for certain objects, then it will
be n byte aligned unless the requested size is less than n. If the
requested size is a multiple of n, where n is a power of 2 no larger than
16, then the object will also be n byte aligned. No space is implicitly
reserved for type tags or the like. Returns (XR←Pointer)0 if no memory
is available.
*/
XR←Pointer
GC←malloc←atomic(/* unsigned ObjectSizeInBytes */);
/* Identical to GC←malloc, except that the object is assumed to contain no
pointers, amd the object is not cleared. Is faster than, and results in
faster collections than GC←malloc.
*/
XR←Pointer GC←realloc(/* XR←Pointer old←object, unsigned ObjectSizeInBytes */);
/* Return a new object with indicated size, and contents of the old object.
The new object is assumed to not contain any pointers if the old object
was known not to contain pointers. The new object is identical to the old
object whenever this can be easily arranged. May be much faster than
a new allocation followed by a copy, but this probably happens only if the
client program uses a stupid algorithm. Unfortunately, such clients are
common, at least in the C world.
*/
void GC←free(/* XR←Pointer object */);
/* Explicitly deallocate an object. The object should have been allocated by
one of the above routines, NOT by one of those below. Results in disaster
if the object is subsequently accessed.
*/
void XR←free(/* XR←Pointer p */);
/* Similar to GC←free, but p may point to the interior of an object. May */
/* be used with any allocated object. */
XR←Pointer
XR←valloc(/* unsigned ObjectSizeInbytes */);
/* allocates an object of size at least ObjectSizeInbytes, whose
first address is at a system page boundary. The object is also
made noncollectable, and can be made collectable by calling valloc←free.
The object is assumed to contain NO pointers, and is not cleared.
*/
void
XR←valloc←free(/* XR←Pointer ObjectAddress */);
/* permits an object allocated by valloc to be collected if there
are no pointers to it.
*/
void
XR←make←uncollectable(/* XR←Pointer RealObjectAddress,
XR←Pointer AlternateAddressForRelease */);
/* prevents the object pointed to by ObjectAddress from ever being collected. */
void
XR←unmake←uncollectable(/* XR←Pointer ObjectAddress */);
/* permits an object made uncollectable by a call on XR←make←uncollectable
to again enter the possible collection pool. ObjectAddress can
be either the RealObjectAddress or the AlternateAddressForRelease give
to XR←make←uncollectable.
*/
/* The following routines are OBSOLETE. They return pointers into the
middle of objects, leaving room for 8 byte headers.
*/
XR←Pointer
XR←calloc(/* unsigned ObjectCount, ObjectSizeInBytes */);
/* allocates a new object of length at least ObjectCount * ObjectSizeInBytes.
The object is assumed to contain pointers, and is cleared to all zeros.
OBSOLETE */
XR←Pointer
XR←clear←new(/* unsigned ObjectCount, ObjectSizeInBytes */);
/* allocates a new object of length at least ObjectCount * ObjectSizeInBytes.
The object is assumed to contain pointers, and is cleared to all zeros.
OBSOLETE*/
XR←Pointer
XR←new(/* unsigned ObjectSizeInBytes */);
/* allocates a new object at least ObjectSizeInBytes.
The object is assumed to contain pointers, and is cleared to all zeros.
*/
XR←Pointer
XR←pointerfree←new(/* unsigned ObjectSizeInBytes */);
/* allocates a new object at least ObjectSizeInBytes.
The object is assumed to contain NO pointers, and is not cleared.
OBSOLETE */
XR←Pointer
XR←ralloc(/* unsigned ObjectSizeIn32BitWords */);
/* allocates a new object of at least ObjectSizeIn32BitWords.
The object is assumed to contain NO pointers, and is not cleared.
OBSOLETE */
XR←Pointer
XR←ralloc←comp(/* unsigned ObjectSizeIn32BitWords */);
/* allocates a new object of at least ObjectSizeIn32BitWords.
The object is assumed to contain pointers, and is cleared to zeros.
OBSOLETE */
XR←Pointer
XR←realloc(/* unsigned ObjectAddress; unsigned ObjectSizeInBytes */);
/* allocates a new object of size at least ObjectSizeInBytes, and
copies the bytes at ObjectAddress into the new object.
ObjectSizeInBytes are always copied, so XR←realloc only makes
sense for growing, not shrinking, objects. The object is assumed
to contain pointers, and any additional space is cleared to zeros.
OBSOLETE */
XR←Pointer
XR←malloc(/* unsigned ObjectSizeInBytes */);
/* allocates an object of size at least ObjectSizeInBytes, and
return the address. The object is assumed to contain pointers,
and is cleared to zeros.
OBSOLETE */
void XR←unsafe←free(/* XR←Pointer */);
/* Alias for XR←free. */
/* The following control routines are also OBSOLETE: */
extern bool
XR←GCGetMiserlyHeap(), XR←GCSetMiserlyHeap(/* bool */);
/* Do nothing at the moment. Return FALSE */
/*
* Allocation and deallocation routines that traffic in uncollectable
* objects. These were introduced as a patch to exisiting problems.
* They should be considered instantly OBSOLETE.
*/
XR←Pointer
XR←UNCollect←malloc(/* long size */);
XR←Pointer
XR←UNCollect←calloc(/* long size←elem, long num←elem */);
XR←Pointer
XR←UNCollect←realloc(/* XR←Pointer old, long size */);
void
XR←UNCollect←free(/* XR←Pointer ptr */);
/***** Unix interface replacements (see Unix manuals). *****/
/* All objects are assumed to possibly contain pointers, except valloc.
These are here for compatibility of pre-existing code, but for the
sake of clarity, because of slightly different semantics, it is
prefered to use the XR←foo name instead of just foo.
realloc
cfree
free
malloc
calloc
valloc - special note: valloced objects in PCR are assumed to
contain no pointers, and are made not collectable.
valloc←free is available to make them collectable.
*/
/* Routines below are not for casual users */
void
XR←add←data←list(/* XR←Pointer startAddress, endAddress */);
/* To be called by the initializing world to add a root.
Can be called at any time to add additional roots.
The words between startAddress and endAddress will be used as an
additional root set for garbage collections. This is not for
casual use: only world initialization and dynamic loading ordinarly
use it. The last word checked starts at endAddress-4.
*/
typedef struct GC←InfoRep {
bool gci←full←collection; /* This is a full collection */
/* More to come? */
} * GC←Info;
typedef void (*RegisterGCCallbackType)(/* XR←Pointer clientdata,
GC←Info info */);
void
XR←RegisterGCCallBackBefore(/* RegisterGCCallbackType proc, XR←Pointer clientdata, RegisterGCCallbackType *oldproc, XR←Pointer *oldclientdata */);
void
XR←RegisterGCCallBackAfter(/* RegisterGCCallbackType proc; XR←Pointer clientdata, RegisterGCCallbackType *oldproc; XR←Pointer *oldclientdata */);
void
XR←RegisterGCCallBackDuringInner(/* RegisterGCCallbackType proc; XR←Pointer clientdata, RegisterGCCallbackType *oldproc; XR←Pointer *oldclientdata */);
/* Registers subroutines to be called-back just before, and just after,
garbage collection. These routines are not for casual use: they
may be called inside the GC monitor lock, and so must not allocate
any storage. Also, only one is kept, any new registration replaces
the old. (The old proc and client data values are returned in the
locations pointed to by oldproc and oldclientdata, unless these are null.)
Registering NIL turns off callback. The call is made by the
GC daemon thread. A failure to return promptly can be disastrous.
The callback is made as:
(*proc)(clientdata, full←gc)
For present purposes, a collection is defined to be occurring only
while the world is stopped. The first two routines are called
just before and just after this occurs. The fact that the collector
does much of its work concurrently is ignored.
A collection is defined to be full if no objects are preserved
simply because they survived some combination of previous collections.
The routine XR←RegisterGCCallBackDuringInner expects to be called with
GC←allocate←ml already held.
The routine registered by XR←RegisterGCCallBackDuringInner is called
with the world stopped, and with the allocate, virtual dirty bit,
and IOP order locks held. It is called after all mark bits
have attained their final value.
*/
typedef XR←Pointer (*GC←alloc←call←back←type)
(/* long sz, bool is←atomic, XR←Pointer client←data */);
void GC←register←alloc←callback
(/* GC←alloc←call←back←type fn, XR←Pointer client←data,
GC←alloc←call←back←type *Ofn, XR←Pointer *Oclient←data */);
/* Register a routine to be called before every allocation. If it returns
* a non-NIL value, then that value is returned as the result of the
* allocator call. Fn is run before the allocation monitor lock is acquired,
* but after acquiring a spearate monitor lock. It should be safe to have
* fn unregister the callback (by passing 0 as the fn argument), and then
* recursively invoke the allocator. A recursive invocation of the callback
* wwould result in deadlock.
* Client←data is passed to fn. The old values of fn and client←data are
* returned in the third and fourth arguments.
* Most applications will want to have fn always return NIL.
*/
void
XR←SetupGC();
/* Set up for garbage collection. Called only by initializing world. */
void
GC←register←displacement(/* unsigned DisplacementInBytes */);
/* Register the given displacement as a valid displacement of a pointer
to an object into an object. All values equal to an object address
plus the given displacement will henceforth be treated as pointers.
Ignored if the collector is not compiled to keep track of
such things. Calling this after allocation has taken place is more
expensive, but still safe. We claim it is unreasonable to ever
unregister a displacement. Thus there is no way to do it.
*/
#if defined(FINALIZE)
/***** Finalization *****/
/*
The finalization described here is the innermost level, and is not
indended for direct use. Rather, language implementors are expected
to wrap their own layers around this. For instance, there is a
different Cedar layer for use by Cedar/Mesa programmers.
*/
/*
* Finalizable Object structures and Finalization Queues:
*
* Invariants:
*
* firstword, secondword - encode a pointer to an object
* (a) disguised as pair < ptr&0xffff, (ptr>>16)&0xffff >
* if it's finalizable
* (b) undisguised as < ptr , nil > if it's not finalizable
* N.B. since first 64K of address space isn't in heap, this
* means (secondword == 0) iff the pointer is undisguised.
* associatedFQ - pointer to a FinalizationQueueStructure
* non-NIL iff the object is finalizable or on the finalization queue
*
* Thus, finalization states can be determined by:
* enabled: (secondword != 0)
* disabled: (associatedFQ == NIL)
* onFQ: otherwise
*/
typedef struct XR←FinalizationQueueStructure {
struct XR←FinalizableObjectStructure * head;
struct XR←FinalizableObjectStructure * tail;
struct XR←CVRep fqNonempty;
} * XR←FinalizationQueue;
typedef struct XR←FinalizableObjectStructure {
unsigned long firstword;
unsigned long secondword;
XR←FinalizationQueue associatedFQ;
struct XR←FinalizableObjectStructure *next;
} * XR←FinalizationHandle;
#define XR←IsDisguised(h) ((h)->secondword != 0)
#define XR←FetchFromDisguised(h) ( ((h)->firstword) | ((h)->secondword << 16) )
#define XR←FetchFromUndisguised(h) ( (h)->firstword )
#define XR←StoreDisguised(w,h) { \
(h)->firstword = ((unsigned long)(w)) & 0xffff; \
(h)->secondword = (((unsigned long)(w)) >> 16) & 0xffff; \
}
#define XR←StoreUndisguised(w,h) { \
(h)->firstword = ((unsigned long)(w)); \
(h)->secondword = 0; \
}
typedef enum {
fzsEnabled = 0,
fzsOnFQ = 1,
fzsDisabled = 2,
fzsError = 0x7fffffff /* force to 32 bits */
} XR←FinalizationState;
XR←FinalizationQueue
XR←NewFQ();
/* return a new, empty, initialized finalization queue. */
XR←FinalizationHandle
XR←FQNextNoAbort(/* XR←FinalizationQueue fq */);
/* return the next handle on queue 'fq', waiting on a condition variable
until there is an item if necessary. If the
wait is interrupted, return NIL */
bool
XR←FQEmpty(/* XR←FinalizationQueue fq */);
XR←FinalizationHandle
XR←NewFinalizationHandle();
/* return a new, empty, initialized handle for an object to be finalized. */
void
XR←EnableFinalization(/* XR←Pointer object;
XR←FinalizationQueue fq;
XR←FinalizationHandle h */);
/* Cause the object to be enabled for finalization.
'h' is updated to describe the object. When the time comes,
fq will be the finalization queue on which the object is placed.
*/
XR←FinalizationState
XR←DisableFinalization(/* XR←FinalizationHandle h */);
/* Disable the object described by 'h' for finalization. Return its
prior XR←FinalizationState. If it is already on a finalize q, remove it.
*/
XR←FinalizationState
XR←ReenableFinalization(/* XR←FinalizationHandle h;
XR←FinalizationQueue fq */);
/* Causes an object which was once finalizable to be so again, now
on queue 'fq'. If it is on some other queue, it is removed first.
Prior state is returned.
*/
XR←FinalizationState
XR←GetFinalizationState(/* XR←FinalizationHandle h */);
/* get the finalization state of the object */
XR←Pointer
XR←HandleToObject(/* XR←FinalizationHandle h */);
/* Get the pointer to the real object, given its handle */
#endif /* FINALIZE */
#endif /* ←XR←GC← */