>From ba3bede253f1c9c53a558809d41d97612859edb6 Mon Sep 17 00:00:00 2001 From: Gwenael Casaccio Date: Wed, 15 Jun 2011 00:51:00 +0200 Subject: [PATCH 1/2] safe mark --- libgst/oop.c | 145 +++++++++++++--------------------------- libgst/oop.h | 9 ++- libgst/oop.inl | 3 +- snprintfv/snprintfv/filament.h | 4 +- snprintfv/snprintfv/printf.h | 8 +- snprintfv/snprintfv/stream.h | 4 +- 6 files changed, 64 insertions(+), 109 deletions(-) diff --git a/libgst/oop.c b/libgst/oop.c index 0a34f95..a80a45d 100644 --- a/libgst/oop.c +++ b/libgst/oop.c @@ -353,6 +353,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old, _gst_inc_init_registry (); } + _gst_mem.markQueue = xcalloc (4 * K, sizeof (*_gst_mem.markQueue)); + _gst_mem.currentMarkQueue = &_gst_mem.markQueue[0]; + _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * K]; } void _gst_update_object_memory_oop (OOP oop) @@ -2216,114 +2219,58 @@ mark_ephemeron_oops (void) } while(0) void -_gst_mark_an_oop_internal (OOP oop) +_gst_add_an_oop_to_mark_queue (OOP oop) { - OOP *curOOP, *atEndOOP; - goto markOne; + if (!IS_OOP (oop) || IS_OOP_MARKED (oop)) + return ; - markRange: - { /* in the loop! */ -#if defined (GC_DEBUGGING) - gst_object obj = (gst_object) (curOOP - 1); /* for debugging */ -#endif - for (;;) - { - /* in a loop, do next iteration */ - oop = *curOOP; - PREFETCH_LOOP (curOOP, PREF_READ | PREF_NTA); - curOOP++; - if (IS_OOP (oop)) - { -#if defined (GC_DEBUGGING) - if UNCOMMON (!IS_OOP_ADDR (oop)) - { - printf - ("Error! Invalid OOP %p was found inside %p!\n", - oop, obj); - abort (); - } - else -#endif - if (!IS_OOP_MARKED (oop)) - { - PREFETCH_START (oop->object, PREF_READ | PREF_NTA); - - /* On the last object in the set, reuse the - current invocation. oop is valid, so we go to - the single-object case */ - if UNCOMMON (curOOP == atEndOOP) - goto markOne; - - _gst_mark_an_oop_internal (oop); - continue; - } - } + if (_gst_mem.currentMarkQueue == _gst_mem.lastMarkQueue) + { + OOP *oldMarkQueue = _gst_mem.markQueue; + size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue; - /* Place the check here so that the continue above skips it. */ - if UNCOMMON (curOOP == atEndOOP) - return; - } - } + _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 4 * size); + _gst_mem.currentMarkQueue = &_gst_mem.markQueue[_gst_mem.currentMarkQueue - oldMarkQueue]; + _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * size]; + } - markOne: - { - OOP objClass; - gst_object object; - uintptr_t size; + oop->flags |= F_REACHABLE; + *_gst_mem.currentMarkQueue = oop; + _gst_mem.currentMarkQueue++; +} -#if defined (GC_DEBUGGING) - if UNCOMMON (IS_OOP_FREE (oop)) - { - printf ("Error! Free OOP %p is being marked!\n", oop); - abort (); - return; - } -#endif +void +_gst_mark (void) +{ + while (_gst_mem.currentMarkQueue > _gst_mem.markQueue) + { + int i, n; + OOP oop; -#if defined(GC_DEBUG_OUTPUT) - printf (">Mark "); - _gst_display_oop (oop); -#endif + PREFETCH_LOOP (_gst_mem.currentMarkQueue, PREF_READ | PREF_NTA); + _gst_mem.currentMarkQueue--; + oop = *_gst_mem.currentMarkQueue; - /* see if the object has pointers, set up to copy them if so. - */ - oop->flags |= F_REACHABLE; - object = OOP_TO_OBJ (oop); - objClass = object->objClass; - if UNCOMMON (oop->flags & F_CONTEXT) - { - gst_method_context ctx; - intptr_t methodSP; - ctx = (gst_method_context) object; - methodSP = TO_INT (ctx->spOffset); - /* printf("setting up for loop on context %x, sp = %d\n", - ctx, methodSP); */ - TAIL_MARK_OOPRANGE (&ctx->objClass, - ctx->contextStack + methodSP + 1); + if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK)) + { + if (oop->flags & F_EPHEMERON) + _gst_add_buf_pointer (oop); - } - else if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK)) - { - if (oop->flags & F_EPHEMERON) - _gst_add_buf_pointer (oop); - - /* In general, there will be many instances of a class, - but only the first time will it be unmarked. So I'm - marking this as uncommon. */ - if UNCOMMON (!IS_OOP_MARKED (objClass)) - TAIL_MARK_OOP (objClass); - } - else - { - size = NUM_OOPS (object); - if COMMON (size) - TAIL_MARK_OOPRANGE (&object->objClass, - object->data + size); + _gst_add_an_oop_to_mark_queue (oop->object->objClass); + } + else + { + n = scanned_fields_in (OOP_TO_OBJ (oop), oop->flags) - 1; - else if UNCOMMON (!IS_OOP_MARKED (objClass)) - TAIL_MARK_OOP (objClass); - } - } + for (i = 0; i < n; i++) + { + OOP newOOP = OOP_TO_OBJ (oop)->data[i]; + + if (IS_OOP (newOOP) && !IS_OOP_MARKED (newOOP)) + _gst_add_an_oop_to_mark_queue (newOOP); + } + } + } } void diff --git a/libgst/oop.h b/libgst/oop.h index 6816b3f..b33e645 100644 --- a/libgst/oop.h +++ b/libgst/oop.h @@ -193,6 +193,9 @@ struct memory_space struct new_space eden; struct surv_space surv[2], tenuring_queue; + OOP *markQueue; + OOP *currentMarkQueue, *lastMarkQueue; + /* The current state of the copying collector's scan phase. */ struct cheney_scan_state scan; @@ -381,7 +384,11 @@ extern void _gst_grey_oop_range (PTR from, ATTRIBUTE_HIDDEN; /* Mark OOP and the pointers pointed by that. */ -extern void _gst_mark_an_oop_internal (OOP oop) +extern void _gst_add_an_oop_to_mark_queue (OOP oop) + ATTRIBUTE_HIDDEN; + +/* Do the mark step with the current queue. */ +extern void _gst_mark (void) ATTRIBUTE_HIDDEN; /* Fully initialize the builtin objects, possible after the respective diff --git a/libgst/oop.inl b/libgst/oop.inl index 279dd1b..cda21d0 100644 --- a/libgst/oop.inl +++ b/libgst/oop.inl @@ -64,7 +64,8 @@ static inline OOP alloc_oop (PTR obj, intptr_t flags); and already-marked OOPs are not processed silently. */ #define MAYBE_MARK_OOP(oop) do { \ if (IS_OOP(oop) && !IS_OOP_MARKED(oop)) { \ - _gst_mark_an_oop_internal((oop)); \ + _gst_add_an_oop_to_mark_queue((oop)); \ + _gst_mark(); \ } \ } while(0) diff --git a/snprintfv/snprintfv/filament.h b/snprintfv/snprintfv/filament.h index 4a91eb6..8a7ce6c 100644 --- a/snprintfv/snprintfv/filament.h +++ b/snprintfv/snprintfv/filament.h @@ -1,4 +1,4 @@ -#line 1 "../../../snprintfv/snprintfv/filament.in" +#line 1 "./filament.in" /* -*- Mode: C -*- */ /* filament.h --- a bit like a string but different =)O| @@ -118,7 +118,7 @@ extern char * fildelete (Filament *fil); extern void _fil_extend (Filament *fil, size_t len, boolean copy); -#line 61 "../../../snprintfv/snprintfv/filament.in" +#line 61 "./filament.in" /* Save the overhead of a function call in the great majority of cases. */ #define fil_maybe_extend(fil, len, copy) \ diff --git a/snprintfv/snprintfv/printf.h b/snprintfv/snprintfv/printf.h index 49a2e9f..1437dd5 100644 --- a/snprintfv/snprintfv/printf.h +++ b/snprintfv/snprintfv/printf.h @@ -1,4 +1,4 @@ -#line 1 "../../../snprintfv/snprintfv/printf.in" +#line 1 "./printf.in" /* -*- Mode: C -*- */ /* printf.in --- printf clone for argv arrays @@ -266,7 +266,7 @@ enum } \ } SNV_STMT_END -#line 269 "../../../snprintfv/snprintfv/printf.in" +#line 269 "./printf.in" /** * printf_generic_info: * @pinfo: the current state information for the format @@ -302,7 +302,7 @@ extern int printf_generic_info (struct printf_info *const pinfo, size_t n, int * extern int printf_generic (STREAM *stream, struct printf_info *const pinfo, union printf_arg const *args); -#line 270 "../../../snprintfv/snprintfv/printf.in" +#line 270 "./printf.in" /** * register_printf_function: * @spec: the character which will trigger @func, cast to an unsigned int. @@ -789,7 +789,7 @@ extern int snv_vasprintf (char **result, const char *format, va_list ap); extern int snv_asprintfv (char **result, const char *format, snv_constpointer const args[]); -#line 271 "../../../snprintfv/snprintfv/printf.in" +#line 271 "./printf.in" /* If you don't want to use snprintfv functions for *all* of your string formatting API, then define COMPILING_SNPRINTFV_C and use the snv_ diff --git a/snprintfv/snprintfv/stream.h b/snprintfv/snprintfv/stream.h index 496bd33..0bebce1 100644 --- a/snprintfv/snprintfv/stream.h +++ b/snprintfv/snprintfv/stream.h @@ -1,4 +1,4 @@ -#line 1 "../../../snprintfv/snprintfv/stream.in" +#line 1 "./stream.in" /* -*- Mode: C -*- */ /* stream.h --- customizable stream routines @@ -180,7 +180,7 @@ extern int stream_puts (char *s, STREAM *stream); extern int stream_get (STREAM *stream); -#line 88 "../../../snprintfv/snprintfv/stream.in" +#line 88 "./stream.in" #ifdef __cplusplus #if 0 /* This brace is so that emacs can still indent properly: */ -- 1.7.4.1 >From 75b4a2108bf0e7c403dac4c676b3fd04b1829bb7 Mon Sep 17 00:00:00 2001 From: Gwenael Casaccio Date: Mon, 20 Jun 2011 23:35:18 +0200 Subject: [PATCH 2/2] iterative mark --- libgst/interp-bc.inl | 2 + libgst/oop.c | 57 ++++++++++++++++++++++++++++++++++++-------------- 2 files changed, 43 insertions(+), 16 deletions(-) diff --git a/libgst/interp-bc.inl b/libgst/interp-bc.inl index 9a1243e..3ee042b 100644 --- a/libgst/interp-bc.inl +++ b/libgst/interp-bc.inl @@ -173,6 +173,7 @@ } while(0) + void _gst_send_message_internal (OOP sendSelector, int sendArgs, @@ -192,6 +193,7 @@ _gst_send_message_internal (OOP sendSelector, zeros. */ _gst_sample_counter++; + hashIndex = METHOD_CACHE_HASH (sendSelector, method_class); methodData = &method_cache[hashIndex]; diff --git a/libgst/oop.c b/libgst/oop.c index a80a45d..9d7b242 100644 --- a/libgst/oop.c +++ b/libgst/oop.c @@ -66,6 +66,7 @@ /* Define this flag to turn on debugging code for OOP table management */ /* #define GC_DEBUGGING */ +#define GC_DEBUGGING /* Define this flag to disable incremental garbage collection */ /* #define NO_INCREMENTAL_GC */ @@ -353,9 +354,9 @@ _gst_init_mem (size_t eden, size_t survivor, size_t old, _gst_inc_init_registry (); } - _gst_mem.markQueue = xcalloc (4 * K, sizeof (*_gst_mem.markQueue)); + _gst_mem.markQueue = xcalloc (128 * K, sizeof (*_gst_mem.markQueue)); _gst_mem.currentMarkQueue = &_gst_mem.markQueue[0]; - _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * K]; + _gst_mem.lastMarkQueue = &_gst_mem.markQueue[128 * K]; } void _gst_update_object_memory_oop (OOP oop) @@ -2226,12 +2227,11 @@ _gst_add_an_oop_to_mark_queue (OOP oop) if (_gst_mem.currentMarkQueue == _gst_mem.lastMarkQueue) { - OOP *oldMarkQueue = _gst_mem.markQueue; - size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue; + const size_t size = _gst_mem.lastMarkQueue - _gst_mem.markQueue; - _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 4 * size); - _gst_mem.currentMarkQueue = &_gst_mem.markQueue[_gst_mem.currentMarkQueue - oldMarkQueue]; - _gst_mem.lastMarkQueue = &_gst_mem.markQueue[4 * size]; + _gst_mem.markQueue = (OOP *) xrealloc (_gst_mem.markQueue, 10 * size * sizeof (*_gst_mem.markQueue)); + _gst_mem.currentMarkQueue = &_gst_mem.markQueue[size]; + _gst_mem.lastMarkQueue = &_gst_mem.markQueue[10 * size]; } oop->flags |= F_REACHABLE; @@ -2246,29 +2246,54 @@ _gst_mark (void) { int i, n; OOP oop; + gst_object obj; PREFETCH_LOOP (_gst_mem.currentMarkQueue, PREF_READ | PREF_NTA); _gst_mem.currentMarkQueue--; oop = *_gst_mem.currentMarkQueue; + obj = OOP_TO_OBJ (oop); - if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK)) +#if defined(GC_DEBUG_OUTPUT) + printf (">Mark "); + _gst_display_oop (oop); + + if UNCOMMON (!IS_OOP_ADDR (oop)) + { + printf + ("Error! Invalid OOP %p was found inside %p!\n", + oop, obj); + abort (); + } +#endif + + if UNCOMMON (oop->flags & F_CONTEXT) + { + gst_method_context ctx; + intptr_t methodSP; + ctx = (gst_method_context) obj; + methodSP = TO_INT (ctx->spOffset); + n = ctx->contextStack + methodSP + 1 - obj->data; + + for (i = 0; i < n; i++) + _gst_add_an_oop_to_mark_queue (obj->data[i]); + + _gst_add_an_oop_to_mark_queue (obj->objClass); + } + else if UNCOMMON (oop->flags & (F_EPHEMERON | F_WEAK)) { if (oop->flags & F_EPHEMERON) _gst_add_buf_pointer (oop); - _gst_add_an_oop_to_mark_queue (oop->object->objClass); + _gst_add_an_oop_to_mark_queue (obj->objClass); } else { - n = scanned_fields_in (OOP_TO_OBJ (oop), oop->flags) - 1; + n = NUM_OOPS (obj); for (i = 0; i < n; i++) - { - OOP newOOP = OOP_TO_OBJ (oop)->data[i]; - - if (IS_OOP (newOOP) && !IS_OOP_MARKED (newOOP)) - _gst_add_an_oop_to_mark_queue (newOOP); - } + _gst_add_an_oop_to_mark_queue (obj->data[i]); + + _gst_add_an_oop_to_mark_queue (obj->objClass); } } } -- 1.7.4.1