/* -----------------------------------------------------------------------------
- * $Id: Stable.c,v 1.1 1999/01/27 10:11:27 simonm Exp $
*
- * (c) The GHC Team 1998-1999
+ * (c) The GHC Team, 1998-2002
*
* Stable names and stable pointers.
*
* ---------------------------------------------------------------------------*/
+// Make static versions of inline functions in Stable.h:
+#define RTS_STABLE_C
+
+#include "PosixSource.h"
#include "Rts.h"
#include "Hash.h"
-#include "StablePriv.h"
-#include "GC.h"
#include "RtsUtils.h"
+#include "OSThreads.h"
#include "Storage.h"
#include "RtsAPI.h"
#include "RtsFlags.h"
+#include "OSThreads.h"
/* Comment from ADR's implementation in old RTS:
deRefStablePtr# :: StablePtr# a -> State# RealWorld ->
(# State# RealWorld, a #)
\end{verbatim}
- There is also a C procedure @FreeStablePtr@ which frees a stable pointer.
There may be additional functions on the C side to allow evaluation,
application, etc of a stable pointer.
- When Haskell calls C, it normally just passes over primitive integers,
- floats, bools, strings, etc. This doesn't cause any problems at all
- for garbage collection because the act of passing them makes a copy
- from the heap, stack or wherever they are onto the C-world stack.
- However, if we were to pass a heap object such as a (Haskell) @String@
- and a garbage collection occured before we finished using it, we'd run
- into problems since the heap object might have been moved or even
- deleted.
-
- So, if a C call is able to cause a garbage collection or we want to
- store a pointer to a heap object between C calls, we must be careful
- when passing heap objects. Our solution is to keep a table of all
- objects we've given to the C-world and to make sure that the garbage
- collector collects these objects --- updating the table as required to
- make sure we can still find the object.
*/
-snEntry *stable_ptr_table;
-snEntry *stable_ptr_free;
+snEntry *stable_ptr_table = NULL;
+static snEntry *stable_ptr_free = NULL;
-unsigned int SPT_size;
+static unsigned int SPT_size = 0;
+
+#ifdef THREADED_RTS
+static Mutex stable_mutex;
+#endif
/* This hash table maps Haskell objects to stable names, so that every
* call to lookupStableName on a given object will return the same
* stable name.
*
+ * OLD COMMENTS about reference counting follow. The reference count
+ * in a stable name entry is now just a counter.
+ *
* Reference counting
* ------------------
* A plain stable name entry has a zero reference count, which means
*
* A stable pointer has a weighted reference count N attached to it
* (actually in its upper 5 bits), which represents the weight
- * 2^N. The stable name entry keeps a 32-bit reference count, which
+ * 2^(N-1). The stable name entry keeps a 32-bit reference count, which
* represents any weight between 1 and 2^32 (represented as zero).
* When the weight is 2^32, the stable name table owns "all" of the
* stable pointers to this object, and the entry can be garbage
* to the weight stored in the table entry.
* */
-HashTable *addrToStableHash;
+static HashTable *addrToStableHash = NULL;
#define INIT_SPT_SIZE 64
-static inline void
+STATIC_INLINE void
initFreeList(snEntry *table, nat n, snEntry *free)
{
snEntry *p;
for (p = table + n - 1; p >= table; p--) {
- p->addr = (P_)free;
+ p->addr = (P_)free;
+ p->old = NULL;
+ p->ref = 0;
+ p->sn_obj = NULL;
free = p;
}
stable_ptr_free = table;
void
initStablePtrTable(void)
{
- /* the table will be allocated the first time makeStablePtr is
- * called */
- stable_ptr_table = NULL;
- stable_ptr_free = NULL;
- addrToStableHash = NULL;
- SPT_size = 0;
+ if (SPT_size > 0)
+ return;
+
+ SPT_size = INIT_SPT_SIZE;
+ stable_ptr_table = stgMallocBytes(SPT_size * sizeof(snEntry),
+ "initStablePtrTable");
+
+ /* we don't use index 0 in the stable name table, because that
+ * would conflict with the hash table lookup operations which
+ * return NULL if an entry isn't found in the hash table.
+ */
+ initFreeList(stable_ptr_table+1,INIT_SPT_SIZE-1,NULL);
+ addrToStableHash = allocHashTable();
+
+#ifdef THREADED_RTS
+ initMutex(&stable_mutex);
+#endif
}
-StgWord
-lookupStableName(StgPtr p)
+/*
+ * get at the real stuff...remove indirections.
+ *
+ * ToDo: move to a better home.
+ */
+static
+StgClosure*
+removeIndirections(StgClosure* p)
+{
+ StgClosure* q = p;
+
+ while (get_itbl(q)->type == IND ||
+ get_itbl(q)->type == IND_STATIC ||
+ get_itbl(q)->type == IND_OLDGEN ||
+ get_itbl(q)->type == IND_PERM ||
+ get_itbl(q)->type == IND_OLDGEN_PERM ) {
+ q = ((StgInd *)q)->indirectee;
+ }
+ return q;
+}
+
+static StgWord
+lookupStableName_(StgPtr p)
{
StgWord sn;
+ void* sn_tmp;
if (stable_ptr_free == NULL) {
enlargeStablePtrTable();
}
-
- (void *)sn = lookupHashTable(addrToStableHash,(W_)p);
+
+ /* removing indirections increases the likelihood
+ * of finding a match in the stable name hash table.
+ */
+ p = (StgPtr)removeIndirections((StgClosure*)p);
+
+ sn_tmp = lookupHashTable(addrToStableHash,(W_)p);
+ sn = (StgWord)sn_tmp;
if (sn != 0) {
ASSERT(stable_ptr_table[sn].addr == p);
- IF_DEBUG(stable,fprintf(stderr,"cached stable name %d at %p\n",sn,p));
+ IF_DEBUG(stable,debugBelch("cached stable name %ld at %p\n",sn,p));
return sn;
} else {
sn = stable_ptr_free - stable_ptr_table;
- (P_)stable_ptr_free = stable_ptr_free->addr;
- stable_ptr_table[sn].weight = 0;
+ stable_ptr_free = (snEntry*)(stable_ptr_free->addr);
+ stable_ptr_table[sn].ref = 0;
stable_ptr_table[sn].addr = p;
- /* IF_DEBUG(stable,fprintf(stderr,"new stable name %d at
- %p\n",sn,p)); */
+ stable_ptr_table[sn].sn_obj = NULL;
+ /* IF_DEBUG(stable,debugBelch("new stable name %d at %p\n",sn,p)); */
/* add the new stable name to the hash table */
insertHashTable(addrToStableHash, (W_)p, (void *)sn);
}
}
-static inline void
+StgWord
+lookupStableName(StgPtr p)
+{
+ StgWord res;
+
+ initStablePtrTable();
+ ACQUIRE_LOCK(&stable_mutex);
+ res = lookupStableName_(p);
+ RELEASE_LOCK(&stable_mutex);
+ return res;
+}
+
+STATIC_INLINE void
freeStableName(snEntry *sn)
{
+ ASSERT(sn->sn_obj == NULL);
+ if (sn->addr != NULL) {
+ removeHashTable(addrToStableHash, (W_)sn->addr, NULL);
+ }
sn->addr = (P_)stable_ptr_free;
stable_ptr_free = sn;
}
StgStablePtr
getStablePtr(StgPtr p)
{
- StgWord sn = lookupStableName(p);
- StgWord weight, weight_2;
-
- weight = stable_ptr_table[sn].weight;
- if (weight == 0) {
- weight = 1 << (BITS_IN(StgWord)-1);
- stable_ptr_table[sn].weight = weight;
- return (StgStablePtr)(sn + ((BITS_IN(StgWord)-1) << STABLEPTR_WEIGHT_SHIFT));
- }
- else if (weight == 1) {
- barf("getStablePtr: too light");
- }
- else {
- weight /= 2;
- /* find log2(weight) */
- for (weight_2 = 1; weight != 1; weight_2++) {
- weight >>= 1;
+ StgWord sn;
+
+ initStablePtrTable();
+ ACQUIRE_LOCK(&stable_mutex);
+ sn = lookupStableName_(p);
+ stable_ptr_table[sn].ref++;
+ RELEASE_LOCK(&stable_mutex);
+ return (StgStablePtr)(sn);
+}
+
+void
+freeStablePtr(StgStablePtr sp)
+{
+ snEntry *sn;
+
+ initStablePtrTable();
+ ACQUIRE_LOCK(&stable_mutex);
+
+ sn = &stable_ptr_table[(StgWord)sp];
+
+ ASSERT((StgWord)sp < SPT_size && sn->addr != NULL && sn->ref > 0);
+
+ sn->ref--;
+
+ // If this entry has no StableName attached, then just free it
+ // immediately. This is important; it might be a while before the
+ // next major GC which actually collects the entry.
+ if (sn->sn_obj == NULL && sn->ref == 0) {
+ freeStableName(sn);
}
- stable_ptr_table[sn].weight -= 2^weight_2;
- return (StgStablePtr)(sn + (weight_2 << STABLEPTR_WEIGHT_SHIFT));
- }
+
+ RELEASE_LOCK(&stable_mutex);
}
void
enlargeStablePtrTable(void)
{
nat old_SPT_size = SPT_size;
-
- if (SPT_size == 0) {
- /* 1st time */
- SPT_size = INIT_SPT_SIZE;
- stable_ptr_table = stgMallocWords(SPT_size * sizeof(snEntry),
- "initStablePtrTable");
-
- initFreeList(stable_ptr_table+1,INIT_SPT_SIZE-1,NULL);
- addrToStableHash = allocHashTable();
- }
- else {
- /* 2nd and subsequent times */
- SPT_size *= 2;
- stable_ptr_table =
- stgReallocWords(stable_ptr_table, SPT_size * sizeof(snEntry),
+
+ // 2nd and subsequent times
+ SPT_size *= 2;
+ stable_ptr_table =
+ stgReallocBytes(stable_ptr_table,
+ SPT_size * sizeof(snEntry),
"enlargeStablePtrTable");
-
- initFreeList(stable_ptr_table + old_SPT_size, old_SPT_size, NULL);
- }
+
+ initFreeList(stable_ptr_table + old_SPT_size, old_SPT_size, NULL);
}
/* -----------------------------------------------------------------------------
* Treat stable pointers as roots for the garbage collector.
*
- * A stable pointer is any stable name entry with a weight > 0. We'll
+ * A stable pointer is any stable name entry with a ref > 0. We'll
* take the opportunity to zero the "keep" flags at the same time.
* -------------------------------------------------------------------------- */
void
-markStablePtrTable(rtsBool full)
+markStablePtrTable(evac_fn evac)
{
- snEntry *p, *end_stable_ptr_table;
- StgPtr q;
- StgClosure *new;
-
- if (SPT_size == 0)
- return;
+ snEntry *p, *end_stable_ptr_table;
+ StgPtr q;
+
+ end_stable_ptr_table = &stable_ptr_table[SPT_size];
+
+ // Mark all the stable *pointers* (not stable names).
+ // _starting_ at index 1; index 0 is unused.
+ for (p = stable_ptr_table+1; p < end_stable_ptr_table; p++) {
+ q = p->addr;
+
+ // Internal pointers are free slots. If q == NULL, it's a
+ // stable name where the object has been GC'd, but the
+ // StableName object (sn_obj) is still alive.
+ if (q && (q < (P_)stable_ptr_table || q >= (P_)end_stable_ptr_table)) {
+
+ // save the current addr away: we need to be able to tell
+ // whether the objects moved in order to be able to update
+ // the hash table later.
+ p->old = p->addr;
+
+ // if the ref is non-zero, treat addr as a root
+ if (p->ref != 0) {
+ evac((StgClosure **)&p->addr);
+ }
+ }
+ }
+}
- if (full) {
- freeHashTable(addrToStableHash,NULL);
- addrToStableHash = allocHashTable();
- }
+/* -----------------------------------------------------------------------------
+ * Thread the stable pointer table for compacting GC.
+ *
+ * Here we must call the supplied evac function for each pointer into
+ * the heap from the stable pointer table, because the compacting
+ * collector may move the object it points to.
+ * -------------------------------------------------------------------------- */
- end_stable_ptr_table = &stable_ptr_table[SPT_size];
+void
+threadStablePtrTable( evac_fn evac )
+{
+ snEntry *p, *end_stable_ptr_table;
+ StgPtr q;
+
+ end_stable_ptr_table = &stable_ptr_table[SPT_size];
+
+ for (p = stable_ptr_table+1; p < end_stable_ptr_table; p++) {
+
+ if (p->sn_obj != NULL) {
+ evac((StgClosure **)&p->sn_obj);
+ }
- /* Mark all the stable *pointers* (not stable names)
- */
- for (p = stable_ptr_table; p < end_stable_ptr_table; p++) {
- q = p->addr;
- /* internal pointers or NULL are free slots */
- if (q && (q < (P_)stable_ptr_table || q >= (P_)end_stable_ptr_table)) {
- if (p->weight != 0) {
- new = MarkRoot((StgClosure *)q);
- /* Update the hash table */
- if (full) {
- insertHashTable(addrToStableHash, (W_)new, (void *)(p - stable_ptr_table));
- (StgClosure *)p->addr = new;
- } else if ((P_)new != q) {
- removeHashTable(addrToStableHash, (W_)q, NULL);
- insertHashTable(addrToStableHash, (W_)new, (void *)(p - stable_ptr_table));
- (StgClosure *)p->addr = new;
+ q = p->addr;
+ if (q && (q < (P_)stable_ptr_table || q >= (P_)end_stable_ptr_table)) {
+ evac((StgClosure **)&p->addr);
}
- /* IF_DEBUG(stable, fprintf(stderr,"Stable ptr %d still alive
- at %p, weight %d\n", p - stable_ptr_table, new,
- p->weight)); */
- }
- else {
- /* reset the keep flag */
- p->keep = rtsFalse;
- }
}
- }
}
/* -----------------------------------------------------------------------------
*
* A dead entry has:
*
- * - a weight of zero (i.e. 2^32)
- * - a false keep flag
+ * - a zero reference count
+ * - a dead sn_obj
*
- * The keep flag is set by the garbage collector whenever it
- * encounters a StableName object on the heap.
+ * Both of these conditions must be true in order to re-use the stable
+ * name table entry. We can re-use stable name table entries for live
+ * heap objects, as long as the program has no StableName objects that
+ * refer to the entry.
+ * -------------------------------------------------------------------------- */
+
+void
+gcStablePtrTable( void )
+{
+ snEntry *p, *end_stable_ptr_table;
+ StgPtr q;
+
+ end_stable_ptr_table = &stable_ptr_table[SPT_size];
+
+ // NOTE: _starting_ at index 1; index 0 is unused.
+ for (p = stable_ptr_table + 1; p < end_stable_ptr_table; p++) {
+
+ // Update the pointer to the StableName object, if there is one
+ if (p->sn_obj != NULL) {
+ p->sn_obj = isAlive(p->sn_obj);
+ }
+
+ // Internal pointers are free slots. If q == NULL, it's a
+ // stable name where the object has been GC'd, but the
+ // StableName object (sn_obj) is still alive.
+ q = p->addr;
+ if (q && (q < (P_)stable_ptr_table || q >= (P_)end_stable_ptr_table)) {
+
+ // StableNames only:
+ if (p->ref == 0) {
+ if (p->sn_obj == NULL) {
+ // StableName object is dead
+ freeStableName(p);
+ IF_DEBUG(stable, debugBelch("GC'd Stable name %ld\n",
+ p - stable_ptr_table));
+ continue;
+
+ } else {
+ p->addr = (StgPtr)isAlive((StgClosure *)p->addr);
+ IF_DEBUG(stable, debugBelch("Stable name %ld still alive at %p, ref %ld\n", p - stable_ptr_table, p->addr, p->ref));
+ }
+ }
+ }
+ }
+}
+
+/* -----------------------------------------------------------------------------
+ * Update the StablePtr/StableName hash table
*
* The boolean argument 'full' indicates that a major collection is
* being done, so we might as well throw away the hash table and build
* -------------------------------------------------------------------------- */
void
-gcStablePtrTable(rtsBool full)
+updateStablePtrTable(rtsBool full)
{
- snEntry *p, *end_stable_ptr_table;
- StgPtr q, new;
-
- if (SPT_size == 0) {
- return;
- }
-
- end_stable_ptr_table = &stable_ptr_table[SPT_size];
-
- for (p = stable_ptr_table; p < end_stable_ptr_table; p++) {
- q = p->addr;
-
- if (q && (q < (P_)stable_ptr_table || q >= (P_)end_stable_ptr_table)) {
-
- /* We're only interested in Stable Names here. */
- if (p->weight == 0) {
+ snEntry *p, *end_stable_ptr_table;
+
+ if (full && addrToStableHash != NULL) {
+ freeHashTable(addrToStableHash,NULL);
+ addrToStableHash = allocHashTable();
+ }
+
+ end_stable_ptr_table = &stable_ptr_table[SPT_size];
+
+ // NOTE: _starting_ at index 1; index 0 is unused.
+ for (p = stable_ptr_table + 1; p < end_stable_ptr_table; p++) {
- if (((StgClosure *)new = isAlive((StgClosure *)q))) {
- IF_DEBUG(stable, fprintf(stderr,"Stable name %d still alive at %p, weight %d\n", p - stable_ptr_table, new, p->weight));
-
- p->addr = new;
- /* Re-hash this stable name */
- if (full) {
- insertHashTable(addrToStableHash, (W_)new, (void *)(p - stable_ptr_table));
- } else if (new != q) {
- removeHashTable(addrToStableHash, (W_)q, NULL);
- insertHashTable(addrToStableHash, (W_)new, (void *)(p - stable_ptr_table));
- }
+ if (p->addr == NULL) {
+ if (p->old != NULL) {
+ // The target has been garbage collected. Remove its
+ // entry from the hash table.
+ removeHashTable(addrToStableHash, (W_)p->old, NULL);
+ p->old = NULL;
+ }
}
-
- else {
- /* If there are still StableName objects in the heap
- * pointing to this entry (p->keep == rtsTrue), then
- * don't free the entry just yet.
- */
- if (p->keep)
- p->addr = NULL;
- else
- freeStableName(p);
+ else if (p->addr < (P_)stable_ptr_table
+ || p->addr >= (P_)end_stable_ptr_table) {
+ // Target still alive, Re-hash this stable name
+ if (full) {
+ insertHashTable(addrToStableHash, (W_)p->addr,
+ (void *)(p - stable_ptr_table));
+ } else if (p->addr != p->old) {
+ removeHashTable(addrToStableHash, (W_)p->old, NULL);
+ insertHashTable(addrToStableHash, (W_)p->addr,
+ (void *)(p - stable_ptr_table));
+ }
}
- }
}
- }
}