[Gc] Cheaper finalisation and weak pointers

Petter Urkedal petter.urkedal at nordita.dk
Wed Feb 2 11:44:01 PST 2005


I am working with expression trees for first-order logic.  The GC has
been ideal for this purpose, but now I want to switch my expression
tree to use maximum sharing implemented by hash construction.  This is
a special case of a more general problem of designing "weak
containers", by which I mean containers with either collectable keys
or collectable nodes.  They requires heavy use of either disappearing
links or finalisers.  Thus, I propose more lightweight alternatives,
"weak poiners" which is a special case of disappearing links and
"finalisation queues".

I have a working patch with multi-threaded test-cases, but I have a
some questions before I propose an inclusion, and of course, the big
question if its even interesting enough to be included in a future
version.

The goals are

    Goal 1.  Reduce the number of memory fragments, and thus reduce
    the number of page faults.

    Goal 2.  Try to utilize all processors on an SMP system most
    of the time.  The qustionable part, which my patch doesn't cover,
    is the code that inspects mark bits.

    Goal 3.  Reduce the memory overhead.

Please, skip to the proposed solutions if my motivating sections
are boring.


Usage.  Weak Containers

    Consider the design of making "weak" containers, i.e. containers
    where elements are removed when they are no longer visible from
    outside the container.

    Weak maps can be used to associate arbitrary data (values) to
    allocated objects (keys).  This may be needed if the implementer
    of some object type has not added a hooks for client data, which
    may even be infeasible to do if several clients share the objects.
    Another reason to keep the values separate from the keys may be
    that there are many (key, value)-mappings with unpredictable
    life-times compared to the keys.

    As a special case where weak nodes (as opposed to weak keys) are
    most optimal, is hash contruction described next.


Usage.  Hash Construction of Expression Trees

    That is, given a vector of pointers to the operator and operands,
    make a hash of them, look it up in a hash table.  If the
    expression exists, return the node, else return a newly inserted
    node.  As an example, ATerm library does this.

    This not only saves space by sharing common subexpressions, but
    more importantly, I think, it means that all objects are
    identified by a unique word-sized number, the node pointer.  That
    is, the equality predicate and hash function becomes constant
    time.  I think this is a genuine gain due to effectively
    "pre-processing" or "caching" the eq/hash during construction.

    The current GC implementation incurs a significant overhead for
    implementing this.  I need a hash table with weak keys, meaning
    that each tree-node needs to be registered with either a weak
    pointer or a finaliser.  I expect most my allocations to be binary
    expressions, and involve only 6 words (2 for an entry in a
    half-filled hash table, 3 for the expression and 1 for an internal
    hash link inside it).  In addition comes the GC internal overhead
    and.  Also, using disappearing links, the hash link must be split
    out of the expression.

    The solutions using the present GC functionality gives the
    following overhead, not counting asymptotically negligible parts:

	disappearing links:		5 words extra, 3 fragments
	    hash-table links must be moved into separate memory
	    fragments (+ 1 word) and disappearing links cost 4 words.

	finalisers:			7 words extra, 2 fragments
	    hash-table links can remain in expressions, but finalisers
	    cost 7 words.

    The alternatives I suggest gives:

	weak pointers:			2 words extra, 2 fragments
	    hash-table links must be moved into separate fragments
	    and the weak pointer requires an additional link
	finalisation queues:		1 word extra, 1 fragment


Usage.  Dynamically Typed Languages

    I suspect that the finalisation queues described below could be
    used by dynamic languages to reduce the overhead for finalisable
    objects.  Since the objects typically contains a type or a link to
    a virtual function table, they can process finalisation queues and
    dispatch to the correct finalisers.  This may not be that
    important, though, since finalisers are generally used in
    scattered cases to release non-memory resources.


Solution.  Weak Pointers

    The interface may look like:

	typedef struct GC_weakptr_node GC_weakptr;

	typedef struct { /* private fields */
	    GC_word next; /* hidden */
	    GC_word hptr; /* hidden */
	};

	void GC_weakptr_init(GC_weakptr *, void *ptr);
	void GC_weakptr_set(GC_weakptr *, void *ptr);
	void *GC_weakptr_get(GC_weakptr *);

    GC_weakptr_init clears ptr and links GC_weakptr_node into a global
    or thread-local singly linked list.  It will only be unlinked when
    the object containing it is ready to be reclaimed.  The other two
    functions are trivial macros or inliners, but provided to make it
    clear that the fields of GC_weakptr_node are private.

    After a global mark, the collector follows all weak pointer nodes,
    unregisters those which are placed in unmarked objects and for the
    rest, clears hptr if it points to an unmarked object.

    I think this solution is easy to use and has clean semantics, as
    well as being easy to implement in the current collector code.  It
    does not support containers with collectable nodes, so that means
    an extra fragment in cases where the keys can be inlined into the
    container's nodes.


Solution.  Finalisation Queues

    The interface (fiq = finalisation queueing):

	typedef struct GC_fiq_queue GC_fiq_queue;

	void GC_fiq_init(GC_fiq_queue *fq);

	void *GC_fiq_malloc(GC_fiq_queue *q, size_t size);
	void *GC_fiq_malloc_atomic(GC_fiq_queue *q, size_t size);

	void GC_fiq_is_dead(void *obj_fiq_base);
	int GC_fiq_has_dead(struct GC_fiq_queue *q);
	void *GC_fiq_pop_dead(GC_fiq_queue *q);

    The data structures may look like:

	struct GC_fiq_queue {
	    GC_word next_in_gc;	/* GC's link of queues to process */
	    GC_word live;	/* stack of GC_fiq_node (hidden links) */
	    GC_word dead;	/* queue of GC_fiq_node (not hidden) */
	    GC_word *dead_end;	/* for appending to queue */
	};
	struct GC_fiq_node {
	    GC_word next_in_fiq; /* next live (hidden) or dead */
	    /* real object pointer starts here */
	};

    In addition to the above minimal interface

	void GC_fiq_free_dead(void *obj_fiq_base);
	void GC_fiq_resurrect_dead(GC_fiq_queue *fq, void *ptr);

    GC_fiq_free_dead would often be safe to call after finalisation of
    a node since the nodes are typically internal to the container
    which owns the queue, and thus should have no further finalisers.

    With GC_fiq_resurrect_dead, the container can reuse nodes when
    feasible.


The Patch

    The attached patch is for gc6.4.  I have tried to minimise changes
    to the existing GC code by adding a "plugin" facility,

	GC_register_plugin(GC_plugin_inspector_proc ip,
			   GC_plugin_finalization_proc fp, void *cd);

    declared in gc_plugin.h.  The "inspector" is called in a
    GC_finalize to check the marks, which means that it works in a
    rather restricted environment.

    The real additions are in
	include/gc_weakptr.h  weakptr.c		Weak pointers
	include/gc_fiq.h      fiq.c		Finalisation queues

    I added two test cases in the contrib subdir.  It includes a weak
    pointer hash map (GC_wpmap) which was useful for testing weak
    pointers, though it may not be a good idea to ship too much
    unrelated things with the GC, so I can write a more direct
    test-case.


Questions

    Shall I keep the "plugin" facility?  If so, is it better to
    register inspectors and finalisers separately?  I.e.:

	GC_register_inspection_plugin(GC_inspection_plugin_proc);
	GC_register_finalization_plugin(GC_finalization_plugin_proc);

    As things are now, inspection plugins are only useful when defined
    in the GC source tree, since it will need access to private
    functions to do anything useful.  That ok for me if my other
    additions are accepted.  However, exporting the necessary
    low-level functions with appropriate warnings about their use
    could make it easier for people to test extensions without
    patching the GC.  Good/bad?

    Ad Goal 2: The comment above GC_finalize says it runs with the
    world stopped.  Is this still the case?  Is it possible to either
    run client code in parallel using thread-local alloc, or to spawn
    additional threads (= number of CPUs) for the inspection phase?

    Any preference of interface changes or renaming?

    Are there still platforms which the collector supports which
    require K&R prototype?  (I have some fixing to do in that case.)

    How shall the license blurb at the top look like; shall I keep
    only the last (C) from the other files, or duplicate all?

I can maintain the patch separately for some time until a suitable
point of inclusion.  At the moment, I just want some feedback.

Sincerely,
Petter Urkedal
-------------- next part --------------
diff -Naur gc6.4/configure.in gc6.4-fiq/configure.in
--- gc6.4/configure.in	2004-12-18 02:28:48.000000000 +0100
+++ gc6.4-fiq/configure.in	2005-02-01 19:35:00.000000000 +0100
@@ -450,7 +450,7 @@
 
 AM_CONDITIONAL(USE_LIBDIR, test -z "$with_cross_host")
 
-AC_OUTPUT([Makefile doc/Makefile include/Makefile],,
+AC_OUTPUT([Makefile doc/Makefile include/Makefile contrib/Makefile],,
 srcdir=${srcdir}
 host=${host}
 CONFIG_SHELL=${CONFIG_SHELL-/bin/sh}
diff -Naur gc6.4/include/Makefile.am gc6.4-fiq/include/Makefile.am
--- gc6.4/include/Makefile.am	2003-05-30 02:11:51.000000000 +0200
+++ gc6.4-fiq/include/Makefile.am	2005-02-02 18:33:25.000000000 +0100
@@ -16,12 +16,13 @@
 # installed headers
 #
 pkginclude_HEADERS = gc.h gc_typed.h gc_inl.h \
-    gc_inline.h gc_mark.h gc_cpp.h \
+    gc_inline.h gc_mark.h gc_cpp.h gc_plugin.h \
     weakpointer.h gc_alloc.h new_gc_alloc.h \
     gc_allocator.h gc_backptr.h \
     gc_gcj.h gc_local_alloc.h leak_detector.h \
     gc_amiga_redirects.h gc_pthread_redirects.h \
-    gc_config_macros.h
+    gc_config_macros.h \
+    gc_plugin.h gc_weakptr.h gc_fiq.h
 
 # headers which are not installed
 #
diff -Naur gc6.4/include/gc_plugin.h gc6.4-fiq/include/gc_plugin.h
--- gc6.4/include/gc_plugin.h	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/include/gc_plugin.h	2005-01-31 18:42:00.000000000 +0100
@@ -0,0 +1,29 @@
+#ifndef _GC_PLUGIN_H
+
+# define _GC_PLUGIN_H
+
+#include "gc.h"
+
+# ifdef __cplusplus
+    extern "C" {
+# endif
+
+typedef void (*GC_plugin_inspector_proc) GC_PROTO((void *cd));
+typedef void (*GC_plugin_finalization_proc) GC_PROTO((void *cd));
+typedef struct GC_plugin *GC_plugin_handle;
+
+GC_API GC_plugin_handle GC_register_plugin
+	GC_PROTO((GC_plugin_inspector_proc ip,
+		  GC_plugin_finalization_proc fp,
+		  void *cd));
+GC_API GC_plugin_handle GC_register_plugin_inner
+	GC_PROTO((GC_plugin_inspector_proc ip,
+		  GC_plugin_finalization_proc fp,
+		  void *cd));
+
+GC_API void GC_unregister_plugin GC_PROTO((GC_plugin_handle));
+
+# ifdef __cplusplus
+    }
+# endif
+#endif
diff -Naur gc6.4/include/gc_fiq.h gc6.4-fiq/include/gc_fiq.h
--- gc6.4/include/gc_fiq.h	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/include/gc_fiq.h	2005-02-02 20:24:48.048629728 +0100
@@ -0,0 +1,78 @@
+#ifndef _GC_FIQ_H
+# define _GC_FIQ_H
+# include "gc.h"
+# ifdef __cplusplus
+    extern "C" {
+# endif
+
+struct GC_fiq_queue;
+
+typedef void (*GC_fiq_finalizer_proc) GC_PROTO((struct GC_fiq_queue *q));
+	/* This is the type of finalizers which are attached to		*/
+	/* finalization queues.  They are called after each global	*/
+	/* mark, and may be used to process the objects queued for	*/
+	/* finalization.						*/
+
+/* Internal, needed for private fields of GC_fiq_queue.			*/
+typedef char *GCpriv_ptr_t;
+typedef void (*GCpriv_finalization_mark_proc) GC_PROTO((char *fo));
+
+/* The GC_fiq_queue struct holds the data to manage finalization	*/
+/* queues.  It is typically embedded in "weak" containers, i.e.		*/
+/* containers with nodes which may be collected before the container	*/
+/* itself.  This can be done by hiding pointers to nodes from the	*/
+/* collector, and unlinking objects which appear in the queue.		*/
+struct GC_fiq_queue
+{
+    /* OBS. Fields of this struct are private and should not be		*/
+    /* modified directly by client code.				*/
+    GC_word next_in_gc;
+    GC_word live;
+    GC_word dead;
+    GC_word *dead_end;
+    GC_fiq_finalizer_proc finalize;
+    GCpriv_finalization_mark_proc mark_proc;
+};
+
+GC_API void GC_fiq_queue_init
+	GC_PROTO((struct GC_fiq_queue *q, GC_fiq_finalizer_proc finalize));
+GC_API void GC_fiq_queue_init_ignore_self
+	GC_PROTO((struct GC_fiq_queue *q, GC_fiq_finalizer_proc finalize));
+GC_API void GC_fiq_queue_init_no_order
+	GC_PROTO((struct GC_fiq_queue *q, GC_fiq_finalizer_proc finalize));
+	/* These functions initialize a finalization queue and		*/
+	/* associates an optional finalizer to be run after each global	*/
+	/* mark.  Objects which are allocated with GC_fiq_malloc or	*/
+	/* GC_fiq_malloc_atomic will appear in q when they become	*/
+	/* unreachable.							*/
+	/* The _ignore_self and _no_order variants are analogous to	*/
+	/* the corresponding GC_register_finalizer variants.		*/
+
+GC_API void *GC_fiq_malloc GC_PROTO((struct GC_fiq_queue *q, size_t size));
+	/* Allocate non-atomic memory which will appear in q when	*/
+	/* determined to be unreachable by the collector.		*/
+
+GC_API void *GC_fiq_malloc_atomic GC_PROTO((struct GC_fiq_queue *q,
+					    size_t size));
+	/* Allocate atomic memory which will appear in q when		*/
+	/* determined to be unreachable by the collector.		*/
+
+#define GC_fiq_queue_is_empty(q) ((q)->dead == 0)
+	/* This function returns non-zero iff q has no objects ready	*/
+	/* for finalization.						*/
+
+GC_API void *GC_fiq_queue_pop GC_PROTO((struct GC_fiq_queue *q));
+	/* Pop off the next object in q to be finalized.  If there are	*/
+	/* no objects left in q, return NULL.				*/
+
+#define GC_fiq_obj_is_dead(ptr) ((*((GC_word *)(ptr) - 1) & 1) == 0)
+	/* This provides a quick test if the object at ptr, which must	*/
+	/* have been allocated with GC_fiq_malloc or			*/
+	/* GC_fiq_malloc_atomic, has been put in the corresponding	*/
+	/* finalization queue.  Call this function before using a node	*/
+	/* in a weak container, to make sure it is still valid.		*/
+
+# ifdef __cplusplus
+    }
+# endif
+#endif
diff -Naur gc6.4/include/gc_weakptr.h gc6.4-fiq/include/gc_weakptr.h
--- gc6.4/include/gc_weakptr.h	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/include/gc_weakptr.h	2005-02-02 20:24:59.691859688 +0100
@@ -0,0 +1,14 @@
+#ifndef _GC_WEAKPTR_H
+# define _GC_WEAKPTR_H
+# include "gc.h"
+
+typedef struct {
+    GC_word next;
+    GC_word hptr;
+} GC_weakptr;
+
+GC_API void GC_weakptr_init GC_PROTO((GC_weakptr *wptr, void *ptr));
+#define GC_weakptr_get(wptr) ((void *)~(wptr)->hptr)
+#define GC_weakptr_set(wptr, ptr) ((wptr)->hptr = ~(GC_word)(ptr))
+
+#endif
diff -Naur gc6.4/finalize.c gc6.4-fiq/finalize.c
--- gc6.4/finalize.c	2004-08-27 02:35:55.000000000 +0200
+++ gc6.4-fiq/finalize.c	2005-02-02 20:26:53.632538072 +0100
@@ -15,6 +15,7 @@
 /* Boehm, February 1, 1996 1:19 pm PST */
 # define I_HIDE_POINTERS
 # include "private/gc_pmark.h"
+# include "gc_plugin.h"
 
 # ifdef FINALIZE_ON_DEMAND
     int GC_finalize_on_demand = 1;
@@ -85,12 +86,21 @@
 
 word GC_fo_entries = 0;
 
+struct GC_plugin {
+    struct GC_plugin *prev, *next;
+    GC_plugin_inspector_proc inspect;
+    GC_plugin_finalization_proc finalize;
+    void *cd;
+} GC_plugin_head = { &GC_plugin_head, &GC_plugin_head, 0, 0, 0 };
+
 void GC_push_finalizer_structures GC_PROTO((void))
 {
     GC_push_all((ptr_t)(&dl_head), (ptr_t)(&dl_head) + sizeof(word));
     GC_push_all((ptr_t)(&fo_head), (ptr_t)(&fo_head) + sizeof(word));
     GC_push_all((ptr_t)(&GC_finalize_now),
 		(ptr_t)(&GC_finalize_now) + sizeof(word));
+    GC_push_all((ptr_t)(&GC_plugin_head),
+		(ptr_t)(&GC_plugin_head) + sizeof(GC_plugin_head));
 }
 
 /* Double the size of a hash table. *size_ptr is the log of its current	*/
@@ -511,6 +521,61 @@
     				ocd, GC_null_finalize_mark_proc);
 }
 
+GC_API GC_plugin_handle
+	GC_register_plugin_inner(GC_plugin_inspector_proc inspect,
+				 GC_plugin_finalization_proc finalize,
+				 void *cd)
+{
+    GC_plugin_handle h;
+    h = (GC_plugin_handle)GC_INTERNAL_MALLOC(sizeof(struct GC_plugin), NORMAL);
+    if (!h) {
+	WARN("Insufficient memory for registration of plugin.", 0);
+	return NULL;
+    }
+    h -> inspect = inspect;
+    h -> finalize = finalize;
+    h -> next = &GC_plugin_head;
+    h -> prev = GC_plugin_head.prev;
+    h -> prev -> next = h;
+    GC_plugin_head . prev = h;
+    return h;
+}
+
+GC_API GC_plugin_handle GC_register_plugin(GC_plugin_inspector_proc inspect,
+					   GC_plugin_finalization_proc finalize,
+					   void *cd)
+{
+    GC_plugin_handle h;
+    DCL_LOCK_STATE;
+#   ifdef THREADS
+	LOCK();
+#   endif
+    h = GC_register_plugin_inner(inspect, finalize, cd);
+#   ifdef THERADS
+	UNLOCK();
+#   endif
+    return h;
+}
+
+GC_API void GC_unregister_plugin_inner(GC_plugin_handle h)
+{
+    h -> prev -> next = h -> next;
+    h -> next -> prev = h -> prev;
+    h -> prev = h -> next = NULL;
+}
+
+GC_API void GC_unregsiter_plugin(GC_plugin_handle h)
+{
+    DCL_LOCK_STATE;
+#   ifdef THREADS
+	LOCK();
+#   endif
+    GC_unregister_plugin_inner(h);
+#   ifdef THREADS
+	UNLOCK();
+#   endif
+}
+
 #ifndef NO_DEBUGGING
 void GC_dump_finalization()
 {
@@ -549,6 +614,7 @@
     register int i;
     int dl_size = (log_dl_table_size == -1 ) ? 0 : (1 << log_dl_table_size);
     int fo_size = (log_fo_table_size == -1 ) ? 0 : (1 << log_fo_table_size);
+    GC_plugin_handle curr_plugin;
     
   /* Make disappearing links disappear */
     for (i = 0; i < dl_size; i++) {
@@ -665,6 +731,12 @@
         }
       }
     }
+
+    for (curr_plugin = GC_plugin_head.next;
+	 curr_plugin != &GC_plugin_head;
+	 curr_plugin = curr_plugin->next)
+	if (curr_plugin->inspect)
+	    (*curr_plugin->inspect)(curr_plugin->cd);
 }
 
 #ifndef JAVA_FINALIZATION_NOT_NEEDED
@@ -765,7 +837,14 @@
     int count = 0;
     word mem_freed_before;
     DCL_LOCK_STATE;
-    
+    GC_plugin_handle curr_plugin;
+
+    for (curr_plugin = GC_plugin_head.next;
+	 curr_plugin != &GC_plugin_head; 
+	 curr_plugin = curr_plugin->next)
+	if (curr_plugin->finalize)
+	    (*curr_plugin->finalize)(curr_plugin->cd);
+
     while (GC_finalize_now != 0) {
 #	ifdef THREADS
 	    DISABLE_SIGNALS();
diff -Naur gc6.4/contrib/Makefile.am gc6.4-fiq/contrib/Makefile.am
--- gc6.4/contrib/Makefile.am	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/Makefile.am	2005-02-02 19:04:19.000000000 +0100
@@ -0,0 +1,15 @@
+AM_CPPFLAGS = \
+	-I$(top_srcdir)/include -I$(top_builddir)/include
+
+contribdir = $(includedir)/gc/contrib
+contrib_HEADERS = wpmap.h diag.h
+lib_LTLIBRARIES = libgc-contrib.la
+libgc_contrib_la_SOURCES = wpmap.c
+
+TESTS = fiq_t0 wpmap_t0
+check_PROGRAMS = fiq_t0 wpmap_t0
+
+wpmap_t0_SOURCES = wpmap_t0.c
+wpmap_t0_LDADD = libgc-contrib.la ../libgc.la
+fiq_t0_SOURCES = fiq_t0.c
+fiq_t0_LDADD = ../libgc.la
diff -Naur gc6.4/contrib/diag.h gc6.4-fiq/contrib/diag.h
--- gc6.4/contrib/diag.h	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/diag.h	2005-01-22 14:58:26.000000000 +0100
@@ -0,0 +1,26 @@
+#ifndef _GC_DIAG_H
+#define _GC_DIAG_H
+
+#include "private/gc_priv.h"
+#ifdef __cplusplus
+#endif
+
+#define GC_err_die0(msg) \
+	do { GC_err_printf0(msg); ABORT("irrecoverable error"); } while (0)
+#define GC_err_die1(msg, arg0) \
+	do { GC_err_printf1(msg, arg0); \
+	     ABORT("irrecoverable error"); } while (0)
+#define GC_err_die2(msg, arg0, arg1) \
+	do { GC_err_printf2(msg, arg0, arg1); \
+	     ABORT("irrecoverable error"); } while (0)
+#define GC_err_die3(msg, arg0, arg1, arg2) \
+	do { GC_err_printf3(msg, arg0, arg1, arg2); \
+	     ABORT("irrecoverable error"); } while (0)
+#define GC_err_die4(msg, arg0, arg1, arg2, arg3) \
+	do { GC_err_printf4(msg, arg0, arg1, arg2, arg3); \
+	     ABORT("irrecoverable error"); } while (0)
+
+#ifdef __cplusplus
+}
+#endif
+#endif
diff -Naur gc6.4/contrib/fiq_t0.c gc6.4-fiq/contrib/fiq_t0.c
--- gc6.4/contrib/fiq_t0.c	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/fiq_t0.c	2005-02-02 08:52:17.000000000 +0100
@@ -0,0 +1,101 @@
+#include "gc_fiq.h"
+#include "gc.h"
+#include <stdio.h>
+#include <stdint.h>
+
+#define TEST_THREAD_CNT 16
+#define TEST_REPEAT_CNT 256
+#define TEST_OBJ_CNT 1024
+
+#define test_assert(test)					\
+	((test)							\
+	 ? (void)0						\
+	 : (fprintf(stderr, "Assertion '"#test"' failed.\n"),	\
+	    ++test_error_cnt))
+
+#define test_assert_eq(lhs, rhs) test_assert_eq_impl(lhs, rhs, #lhs, #rhs)
+
+static int test_error_cnt = 0;
+
+void
+test_assert_eq_impl(long lhs, long rhs,
+		    char const *str_lhs, char const *str_rhs)
+{
+    if (lhs != rhs) {
+	fprintf(stderr, "error: %s = %ld != %s = %ld\n",
+		str_lhs, lhs, str_rhs, rhs);
+	++test_error_cnt;
+    }
+}
+
+typedef struct test_s *test_t;
+struct test_s
+{
+    int biscuit;
+    struct GC_fiq_queue q;
+    int *obj_arr[TEST_OBJ_CNT];
+};
+
+void *
+test_thread(void *ign)
+{
+    int i;
+    test_t t = GC_NEW(struct test_s);
+    int fin_cnt = 0;
+    int dead_cnt = 0;
+
+    GC_fiq_queue_init(&t->q, NULL);
+
+    for (i = 0; i < TEST_OBJ_CNT; ++i) {
+	t->obj_arr[i] = GC_fiq_malloc(&t->q, sizeof(int));
+	*t->obj_arr[i] = i;
+    }
+    GC_gcollect();
+    GC_invoke_finalizers();
+
+    test_assert(GC_fiq_queue_is_empty(&t->q));
+    for (i = 0; i < TEST_OBJ_CNT; i += 2)
+	t->obj_arr[i] = (void *)~(uintptr_t)t->obj_arr[i];
+
+    GC_gcollect();
+    GC_invoke_finalizers();
+
+    for (i = 0; i < TEST_OBJ_CNT; i += 2)
+	if (GC_fiq_obj_is_dead((void *)~(uintptr_t)t->obj_arr[i]))
+	    ++dead_cnt;
+    for (i = 1; i < TEST_OBJ_CNT; i += 2)
+	test_assert(!GC_fiq_obj_is_dead(t->obj_arr[i]));
+
+    while (!GC_fiq_queue_is_empty(&t->q)) {
+	int *o = GC_fiq_queue_pop(&t->q);
+	test_assert((*o & 1) == 0);
+	++fin_cnt;
+    }
+    test_assert(fin_cnt >= dead_cnt && dead_cnt > fin_cnt/2);
+    if (dead_cnt < fin_cnt)
+	printf("dead_cnt = %d != %d = fin_cnt\n", dead_cnt, fin_cnt);
+    test_assert(TEST_OBJ_CNT/3 <= fin_cnt && fin_cnt <= TEST_OBJ_CNT/2);
+    if (fin_cnt < TEST_OBJ_CNT/2)
+	printf("Only %d out of %d objects finalized.\n",
+	       fin_cnt, TEST_OBJ_CNT/2);
+    printf("Leaving thread.\n");
+    return NULL;
+}
+
+int
+main(int argc, char **argv)
+{
+    pthread_t th_idr[TEST_THREAD_CNT - 1];
+    int i;
+    GC_init();
+    for (i = 0; i < TEST_THREAD_CNT - 1; ++i)
+	if (GC_pthread_create(&th_idr[i], NULL, test_thread, NULL) != 0) {
+	    perror(argv[0]);
+	    exit(2);
+	}
+    test_thread(NULL);
+    for (i = 0; i < TEST_THREAD_CNT - 1; ++i)
+	GC_pthread_join(th_idr[i], NULL);
+    printf("All done, %d errors.\n", test_error_cnt);
+    return test_error_cnt? 2 : 0;
+}
diff -Naur gc6.4/contrib/wpmap.h gc6.4-fiq/contrib/wpmap.h
--- gc6.4/contrib/wpmap.h	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/wpmap.h	2005-02-01 20:00:02.000000000 +0100
@@ -0,0 +1,67 @@
+/* The weak pointer property maps defined here are hash maps from weak
+ * pointers to arbitrary objects.  The pointer-typed keys of the maps
+ * are not seen by the collector from the map.  When the object which
+ * a key points to is ready to be recycled by the collector, the
+ * corresponding association is removed from the map.
+ *
+ * GC_WPMAP_IS_THREAD_LOCAL can only be defined if it is guaranteed
+ * that GC_wpmap_t is used locally within a thread and the collector
+ * runs in the same thread.  Thus, it is only feasible for single
+ * threaded applications. */
+
+#ifndef _GC_WPMAP_H
+#define _GC_WPMAP_H
+
+#define GC_I_HIDE_POINTERS 1
+#include "gc.h"
+#include "gc_weakptr.h"
+#include <stdlib.h>
+#include <pthread.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+typedef size_t GC_wpmap_hash_t;
+typedef struct GC_wpmap_node_s *GC_wpmap_node_t;
+typedef struct GC_wpmap_s *GC_wpmap_t;
+
+struct GC_wpmap_node_s
+{
+    GC_wpmap_node_t next;
+    GC_weakptr key;
+};
+
+struct GC_wpmap_s
+{
+    GC_wpmap_node_t *arr;
+    size_t size;
+    size_t mask;
+    pthread_mutex_t mutex;
+};
+
+/* Construct a weak pointer property map. */
+void GC_wpmap_cct(GC_wpmap_t map);
+
+/* Return a collectable and constructed weak pointer property map. */
+GC_wpmap_t GC_wpmap_new(void);
+
+#define GC_wpmap_size(map) ((map)->size)
+
+void GC_wpmap_prune(GC_wpmap_t map);
+
+int GC_wpmap_insert_mem(GC_wpmap_t map, void *key,
+			size_t value_size, void *value_slot_out);
+
+int GC_wpmap_insert_ptr(GC_wpmap_t map, void *key, void *value_ptr_slot_out);
+
+int GC_wpmap_erase(GC_wpmap_t map, void *key);
+
+void *GC_wpmap_find_mem(GC_wpmap_t map, void *key);
+
+void *GC_wpmap_find_ptr(GC_wpmap_t map, void *key);
+
+#ifdef __cplusplus
+}
+#endif
+#endif
diff -Naur gc6.4/contrib/wpmap.c gc6.4-fiq/contrib/wpmap.c
--- gc6.4/contrib/wpmap.c	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/wpmap.c	2005-02-01 21:22:14.000000000 +0100
@@ -0,0 +1,231 @@
+#include "wpmap.h"
+#include "diag.h"
+#include <stddef.h>
+
+#define HASHX(key) (((key) ^ ((key) >> 7)) - (((key) >> 11) ^ ((key) >> 19)))
+#define HASH(key) HASHX((GC_wpmap_hash_t)key)
+#define INITIAL_CAPACITY 4
+#define MIN_FILL_NOM 1
+#define MIN_FILL_DENOM 3
+#define MAX_FILL_NOM 2
+#define MAX_FILL_DENOM 3
+
+static void GC_wpmap_set_capacity(GC_wpmap_t map, size_t new_cap);
+
+void
+GC_wpmap_lock(GC_wpmap_t map)
+{
+    int err = pthread_mutex_lock(&map->mutex);
+    if (err != 0)
+	GC_err_die1("Unexpected problems with locking GC_wpmap_t mutex. "
+		    "(err = %d)", err);
+}
+#define GC_wpmap_unlock(map) pthread_mutex_unlock(&(map)->mutex)
+
+#if 0
+void
+GC_wpmap_finaliser(struct GC_cofi_header *hdr)
+{
+    GC_wpmap_t map = (void *)((char *)hdr - offsetof(struct GC_wpmap_s, cofi));
+    GC_wpmap_node_t *head;
+    GC_wpmap_node_t *arr_end;
+    size_t new_size;
+    GC_wpmap_lock(map);
+    arr_end = map->arr + (map->mask + 1);
+    new_size = map->size;
+    for (head = map->arr; head != arr_end; ++head) {
+	GC_wpmap_node_t *node = head;
+	while (*node) {
+	    void *key = REVEAL_POINTER((*node)->hkey);
+	    if (GC_cofi_is_reclaimable(key)) {
+		*node = (*node)->next;
+		--new_size;
+	    }
+	    else
+		node = &(*node)->next;
+	}
+    }
+    map->size = new_size;
+    if (map->size*MIN_FILL_DENOM < map->mask*MIN_FILL_NOM) {
+	size_t new_mask = map->size*MIN_FILL_NOM/MIN_FILL_DENOM;
+	int shift = 1;
+	while ((new_mask & (new_mask + 1)) != 0) {
+	    new_mask |= new_mask >> shift;
+	    shift *= 2;
+	}
+	GC_ASSERT(new_mask != map->mask);
+	GC_wpmap_set_capacity(map, new_mask + 1);
+    }
+    GC_wpmap_unlock(map);
+}
+#endif
+
+void
+GC_wpmap_cct(GC_wpmap_t map)
+{
+    map->arr = GC_malloc(INITIAL_CAPACITY*sizeof(GC_wpmap_node_t));
+    if (map->arr == NULL)
+	GC_err_die1("out of memory in GC_wpmap_t constructor for %p.", map);
+    map->size = 0;
+    map->mask = INITIAL_CAPACITY - 1;
+    memset(map->arr, 0, INITIAL_CAPACITY*sizeof(GC_wpmap_node_t));
+    pthread_mutex_init(&map->mutex, NULL);
+}
+
+GC_wpmap_t
+GC_wpmap_new()
+{
+    GC_wpmap_t map = GC_malloc(sizeof(struct GC_wpmap_s));
+    if (!map)
+	GC_err_die0("Out of memory in GC_wpmap_new.");
+    GC_wpmap_cct(map);
+    return map;
+}
+
+/* Lock must be held. */
+static void
+GC_wpmap_set_capacity(GC_wpmap_t map, size_t new_cap)
+{
+    size_t old_cap = map->mask + 1;
+    GC_wpmap_node_t *old_arr = map->arr;
+    GC_wpmap_node_t *old_arr_end = old_arr + old_cap;
+    size_t new_mask = new_cap - 1;
+    GC_wpmap_node_t *new_arr;
+    GC_wpmap_node_t *head;
+
+    GC_ASSERT((new_cap & new_mask) == 0); /* capacity must be power of 2 */
+    new_arr = GC_malloc(new_cap*sizeof(GC_wpmap_node_t));
+    if (!new_arr)
+	GC_err_die2("Out of memory while expanding GC_wpmap_t at %p to %ld "
+		    "entries.", map, new_cap);
+    memset(new_arr, 0, new_cap*sizeof(GC_wpmap_node_t));
+    for (head = old_arr; head != old_arr_end; ++head) {
+	GC_wpmap_node_t node = *head;
+	while (node) {
+	    void *key = GC_weakptr_get(&node->key);
+	    GC_wpmap_node_t next_node = node->next;
+	    GC_wpmap_hash_t hash = HASH(key);
+	    GC_wpmap_node_t *dst_node = &new_arr[hash & new_mask];
+	    node->next = *dst_node;
+	    *dst_node = node;
+	    node = next_node;
+	}
+    }
+    memset(old_arr, 0, old_cap*sizeof(GC_wpmap_node_t));
+    map->arr = new_arr;
+    map->mask = new_mask;
+}
+
+void
+GC_wpmap_prune(GC_wpmap_t map)
+{
+    GC_wpmap_node_t *head;
+    GC_wpmap_node_t *arr_end;
+    GC_wpmap_lock(map);
+    arr_end = map->arr + map->mask + 1;
+    for (head = map->arr; head != arr_end; ++head) {
+	GC_wpmap_node_t *node = head;
+	while (*node) {
+	    if (GC_weakptr_get(&(*node)->key) == NULL) {
+		*node = (*node)->next;
+		--map->size;
+	    }
+	    else
+		node = &(*node)->next;
+	}
+    }
+    if (map->size*MIN_FILL_DENOM < map->mask*MIN_FILL_NOM)
+	GC_wpmap_set_capacity(map, (map->mask + 1)/2);
+    GC_wpmap_unlock(map);
+}
+
+int
+GC_wpmap_insert_mem(GC_wpmap_t map, void *key,
+		    size_t value_size, void *value_slot_out)
+{
+    GC_wpmap_node_t *dst_node, node;
+    GC_wpmap_lock(map);
+    if (map->size*MAX_FILL_DENOM > map->mask*MAX_FILL_NOM)
+	GC_wpmap_set_capacity(map, (map->mask + 1)*2);
+    dst_node = &map->arr[HASH(key) & map->mask];
+    for (node = *dst_node; node; node = node->next) {
+	if (key == GC_weakptr_get(&node->key)) {
+	    GC_wpmap_unlock(map);
+	    *(void **)value_slot_out = (void *)(node + 1);
+	    return 0;
+	}
+    }
+    node = GC_malloc(sizeof(struct GC_wpmap_node_s) + value_size);
+    if (!node)
+	GC_err_die1("Out of memory while allocating node in GC_wpmap_t at %p",
+		    map);
+    node->next = *dst_node;
+    GC_weakptr_init(&node->key, key);
+    *dst_node = node;
+    ++map->size;
+    GC_wpmap_unlock(map);
+    *(void **)value_slot_out = (void *)(node + 1);
+    return 1;
+}
+
+int
+GC_wpmap_insert_ptr(GC_wpmap_t map, void *key, void *ptr_slot)
+{
+    return GC_wpmap_insert_mem(map, key, sizeof(void *), ptr_slot);
+}
+
+int
+GC_wpmap_erase(GC_wpmap_t map, void *key)
+{
+    GC_wpmap_node_t *node;
+    GC_wpmap_lock(map);
+    node = &map->arr[HASH(key) & map->mask];
+    while (*node) {
+	if (GC_weakptr_get(&(*node)->key) == key) {
+	    *node = (*node)->next;
+	    --map->size;
+	    if (map->size*MIN_FILL_DENOM < map->mask*MIN_FILL_NOM &&
+		map->mask > INITIAL_CAPACITY - 1)
+		GC_wpmap_set_capacity(map, (map->mask + 1)/2);
+	    GC_wpmap_unlock(map);
+	    return 1;
+	}
+	node = &(*node)->next;
+    }
+    GC_wpmap_unlock(map);
+    return 0;
+}
+
+void *
+GC_wpmap_find_mem(GC_wpmap_t map, void *key)
+{
+    GC_wpmap_node_t node;
+    GC_wpmap_lock(map);
+    node = map->arr[HASH(key) & map->mask];
+    while (node) {
+	if (GC_weakptr_get(&node->key) == key) {
+	    GC_wpmap_unlock(map);
+	    return (void *)(node + 1);
+	}
+	node = node->next;
+    }
+    GC_wpmap_unlock(map);
+    return NULL;
+}
+
+void *
+GC_wpmap_find_ptr(GC_wpmap_t map, void *key)
+{
+    GC_wpmap_node_t node;
+    GC_wpmap_lock(map);
+    node = map->arr[HASH(key) & map->mask];
+    while (node) {
+	if (GC_weakptr_get(&node->key) == key) {
+	    GC_wpmap_unlock(map);
+	    return *(void **)(node + 1);
+	}
+	node = node->next;
+    }
+    GC_wpmap_unlock(map);
+    return NULL;
+}
diff -Naur gc6.4/contrib/wpmap_t0.c gc6.4-fiq/contrib/wpmap_t0.c
--- gc6.4/contrib/wpmap_t0.c	1970-01-01 01:00:00.000000000 +0100
+++ gc6.4-fiq/contrib/wpmap_t0.c	2005-02-01 21:27:58.000000000 +0100
@@ -0,0 +1,118 @@
+#include "wpmap.h"
+#include <stdio.h>
+
+#define TEST_THREAD_CNT 16
+#define TEST_PTR_CNT 1024
+#define TEST_REPEAT_CNT 128
+
+#define test_assert(test)					\
+	((test)							\
+	 ? (void)0						\
+	 : (fprintf(stderr, "Assertion '"#test"' failed.\n"),	\
+	    ++test_error_cnt))
+
+#define test_assert_eq(lhs, rhs) test_assert_eq_impl(lhs, rhs, #lhs, #rhs)
+
+static int test_error_cnt = 0;
+
+void
+test_assert_eq_impl(long lhs, long rhs,
+		    char const *str_lhs, char const *str_rhs)
+{
+    if (lhs != rhs) {
+	fprintf(stderr, "error: %s = %ld != %s = %ld\n",
+		str_lhs, lhs, str_rhs, rhs);
+	++test_error_cnt;
+    }
+}
+
+void
+prop_set(GC_wpmap_t prop_map, void *ptr, int n)
+{
+    int *slot;
+    if (GC_wpmap_insert_mem(prop_map, ptr, sizeof(int), &slot))
+	*slot = n;
+}
+
+void
+prop_clear(GC_wpmap_t prop_map, void *ptr)
+{
+    GC_wpmap_erase(prop_map, ptr);
+}
+
+int
+prop_get(GC_wpmap_t prop_map, void *ptr)
+{
+    int *slot = GC_wpmap_find_mem(prop_map, ptr);
+    return slot? *slot : -1;
+}
+
+void
+test()
+{
+    size_t i;
+    int *ptr_arr[TEST_PTR_CNT];
+
+    /* Create a large number of associations */
+    GC_wpmap_t prop_map = GC_wpmap_new();
+    for (i = 0; i < TEST_PTR_CNT; ++i) {
+	ptr_arr[i] = GC_malloc(sizeof(int));
+	*ptr_arr[i] = i;
+	prop_set(prop_map, ptr_arr[i], -i);
+    }
+    GC_gcollect();
+    GC_invoke_finalizers();
+    GC_wpmap_prune(prop_map);
+    for (i = 0; i < TEST_PTR_CNT; ++i)
+	test_assert_eq(prop_get(prop_map, ptr_arr[i]), -*ptr_arr[i]);
+    test_assert_eq(GC_wpmap_size(prop_map), TEST_PTR_CNT);
+
+    /* Clear some pointers and collect */
+    for (i = 0; i < TEST_PTR_CNT; i += 2)
+	ptr_arr[i] = NULL;
+    GC_gcollect();
+    GC_invoke_finalizers();
+    GC_wpmap_prune(prop_map);
+    test_assert(GC_wpmap_size(prop_map) >= TEST_PTR_CNT/2 &&
+		GC_wpmap_size(prop_map) < 2*TEST_PTR_CNT/3);
+    if (GC_wpmap_size(prop_map) > TEST_PTR_CNT/2)
+	printf("%lu properties still in map, only %d are needed\n",
+	       (long)GC_wpmap_size(prop_map), TEST_PTR_CNT/2);
+    for (i = 1; i < TEST_PTR_CNT; i += 2)
+	test_assert_eq(prop_get(prop_map, ptr_arr[i]), -*ptr_arr[i]);
+
+    /* Explicitely erase some associations */
+    for (i = 1; i < TEST_PTR_CNT/2; i += 2)
+	prop_clear(prop_map, ptr_arr[i]);
+    for (i = TEST_PTR_CNT/2 + 1; i < TEST_PTR_CNT; i += 2)
+	test_assert_eq(prop_get(prop_map, ptr_arr[i]), -*ptr_arr[i]);
+}
+
+void *
+test_thread(void *clos_arg)
+{
+    int i;
+    printf("Entering test_thread()\n");
+    for (i = 0; i < TEST_REPEAT_CNT/TEST_THREAD_CNT; ++i)
+	test();
+    printf("Leaving test_thread()\n");
+    return NULL;
+}
+
+int
+main(int argc, char **argv)
+{
+    pthread_t th_idr[TEST_THREAD_CNT - 1];
+    int i;
+    GC_init();
+    for (i = 0; i < TEST_THREAD_CNT - 1; ++i)
+	if (GC_pthread_create(&th_idr[i], NULL, test_thread, NULL) != 0) {
+	    perror(argv[0]);
+	    exit(2);
+	}
+    test_thread(NULL);
+    for (i = 0; i < TEST_THREAD_CNT - 1; ++i)
+	GC_pthread_join(th_idr[i], NULL);
+    printf("All done, %d errors.\n", test_error_cnt);
+    return test_error_cnt? 2 : 0;
+}


More information about the Gc mailing list