On Wed, Aug 21, 2002 at 04:17:30AM -0400, Mike Lambert wrote:
> Just to complete this thread, I have committed the current version of my
> COW code, as I promised earlier this week.
Did you try running tests with GC_DEBUG on? I get numerous failures.
Here's a patch with a couple of fixes (not all of them gc-related),
though I should warn you that it is rather roughly carved out of my
local copy, which has far too many modifications at the moment.
With this patch, things work for me, but I punted in one place: if you
look at unmake_COW() in string.c, I just disabled garbage collection
around the reallocation. The problem seems to be that you change where
s->bufstart points to, then call Parrot_reallocate_string() on s. But
that can trigger a collection, and it gets confused by the
inconsistent state.
---
This patch also contains a debugging aid that I was speculating on
earlier. Whenever a buffer is marked as being live, it checks to see
if the buffer is on the free list. If so, it whines and complains.
(This is for finding premature killing of newborn Buffers; they'll go
through one sweep and get put on the free list, then get anchored to
the root set somehow. The next sweep will find them.)
This is not 100% accurate, because the stackwalk is conservative: it
assumes that anything whose pointer is in the appropriate range and
otherwise smells right must be a live PMC or Buffer. I thought that
finding old Buffers on the stack would be rare, but I was wrong -- the
problem is that if they were buried in some deeply nested call chain,
then because stack frames are not zeroed out upon allocation (which
would be horribly slow), a later call chain will dig them back up. And
the stackwalking code itself is deep enough and has large enough stack
frames to dig up quite a bit of junk.
So for the debugging code, I set a global flag
CONSERVATIVE_POINTER_CHASING when we're walking the stack, just so
that finding the living dead isn't such a traumatic affair. The rest
of the time, it will abort immediately.
Note that this is a real bug; we really shouldn't be poking into dead
Buffers. There's no telling what the current state of decomposition
is. A seg fault might jump out and bite us, or worse, because that
pointer may have been used by something else for its own twisted
purposes. And that something else could get very upset when it returns
to find that we've jammed flags into the corpse and used its liver for
a link in the ->next_for_GC chain.
It is unlikely to cause problems accidentally, I suppose -- pointers
are checked to make sure they're within one of the pools, so the only
way to run into problems is to have a pointer on the stack to
somewhere within a Buffer's memory, kill off the Buffer by forgetting
about it, then have DOD add the bogus Buffer back onto the free list.
Or have the COW code chase down a bogus tail pointer. Or use a bogus
PMC instead -- then you have ->vtable->mark() to worry about. Hm,
maybe it is dangerous.
Am I missing some reason why this is not a problem? It would slow
allocation and stackwalking way down if we have to keep a hashtable of
valid pointers on the side.
Index: dod.c
===================================================================
RCS file: /cvs/public/parrot/dod.c,v
retrieving revision 1.19
diff -p -u -r1.19 dod.c
--- dod.c 21 Aug 2002 08:00:10 -0000 1.19
+++ dod.c 21 Aug 2002 23:27:49 -0000
@@ -14,6 +14,11 @@
#include "parrot/parrot.h"
+#if GC_DEBUG
+/* Set when walking the system stack */
+int CONSERVATIVE_POINTER_CHASING = 0;
+#endif
+
static size_t find_common_mask(size_t val1, size_t val2);
PMC *
@@ -64,7 +69,9 @@ trace_active_PMCs(struct Parrot_Interp *
last = mark_used(current, last);
/* Find important stuff on the system stack */
+ CONSERVATIVE_POINTER_CHASING = 1;
last = trace_system_stack(interpreter,last);
+ CONSERVATIVE_POINTER_CHASING = 0;
/* Now, go run through the PMC registers and mark them as live */
/* First mark the current set. */
@@ -221,6 +228,12 @@ trace_active_buffers(struct Parrot_Inter
buffer_lives((Buffer *)interpreter->ctx.string_reg.registers[i]);
}
}
+
+ /* The interpreter has a few strings of its own */
+ if (interpreter->current_file)
+ buffer_lives((Buffer*)interpreter->current_file);
+ if (interpreter->current_package)
+ buffer_lives((Buffer*)interpreter->current_package);
/* Now walk the string stack. Make sure to walk from top down
* since stack may have segments above top that we shouldn't walk. */
Index: headers.c
===================================================================
RCS file: /cvs/public/parrot/headers.c,v
retrieving revision 1.8
diff -p -u -r1.8 headers.c
--- headers.c 21 Aug 2002 08:00:10 -0000 1.8
+++ headers.c 21 Aug 2002 23:27:50 -0000
@@ -101,7 +101,18 @@ get_free_buffer(struct Parrot_Interp *in
/* Don't let it point to garbage memory */
buffer->bufstart = NULL;
buffer->flags = BUFFER_selfpoolptr_FLAG;
-
+#if GC_DEBUG
+ buffer->version++;
+#endif
+
+ /* If you get the "Live buffer 0xnnnnnnn version m found on free
+ * list" message, try setting a conditional breakpoint on the
+ * following line. The condition should be
+ * (buffer == 0xnnnnnnnn) && (version == m)
+ * By looking at the stack trace, you can figure out what the
+ * buffer was being used for. Remember, though, that it might just
+ * be stale stack litter that is triggering the warning, and not a
+ * bug at all. */
return buffer;
}
void
Index: interpreter.c
===================================================================
RCS file: /cvs/public/parrot/interpreter.c,v
retrieving revision 1.97
diff -p -u -r1.97 interpreter.c
--- interpreter.c 21 Aug 2002 08:00:10 -0000 1.97
+++ interpreter.c 21 Aug 2002 23:27:51 -0000
@@ -566,9 +566,6 @@ make_interpreter(Interp_flags flags)
interpreter->ctx.pmc_reg_base->prev = NULL;
Parrot_clear_p(interpreter);
- interpreter->DOD_block_level--;
- interpreter->GC_block_level--;
-
/* Stack for lexical pads */
interpreter->ctx.pad_stack = new_stack(interpreter);
@@ -601,6 +598,12 @@ make_interpreter(Interp_flags flags)
string_make(interpreter, "(unknown file)", 14, NULL, 0, NULL);
interpreter->current_package =
string_make(interpreter, "(unknown package)", 18, NULL, 0, NULL);;
+
+ /* Okay, we've finished doing anything that might trigger GC. (The
+ * top of the stack hasn't been set yet, so we cannot allow GC to
+ * run up until now -- we might miss system stack values. */
+ interpreter->DOD_block_level--;
+ interpreter->GC_block_level--;
/* Done. Return and be done with it */
Index: resources.c
===================================================================
RCS file: /cvs/public/parrot/resources.c,v
retrieving revision 1.81
diff -p -u -r1.81 resources.c
--- resources.c 21 Aug 2002 08:00:10 -0000 1.81
+++ resources.c 21 Aug 2002 23:27:53 -0000
@@ -103,7 +103,7 @@ mem_allocate(struct Parrot_Interp *inter
Parrot_do_dod_run(interpreter);
if (pool->compact) {
(*pool->compact)(interpreter, pool);
- }
+ }
#endif
if (pool->top_block->free < size) {
/* Compact the pool if allowed and worthwhile */
@@ -207,14 +207,15 @@ static void compact_pool(struct Parrot_I
| BUFFER_constant_FLAG
| BUFFER_immobile_FLAG
| BUFFER_external_FLAG
- ))) {
- struct
- Buffer_Tail *tail =
+ )))
+ {
+ struct Buffer_Tail *tail =
(struct Buffer_Tail *)((char *)b->bufstart + b->buflen);
ptrdiff_t offset = (ptrdiff_t)((STRING*)b)->strstart -
(ptrdiff_t)b->bufstart;
/* buffer has already been moved; just change the header */
if (b->flags & BUFFER_COW_FLAG
- && tail->flags & TAIL_moved_FLAG) {
+ && tail->flags & TAIL_moved_FLAG)
+ {
/* Find out who else references our data */
Buffer* hdr = *(Buffer**)(b->bufstart);
/* Make sure they know that we own it too */
@@ -228,14 +229,13 @@ static void compact_pool(struct Parrot_I
((STRING*)b)->strstart = (char *)b->bufstart + offset;
}
}
- else
- if (b->flags & BUFFER_selfpoolptr_FLAG) {
+ else if (b->flags & BUFFER_selfpoolptr_FLAG)
+ {
struct Buffer_Tail *new_tail =
(struct Buffer_Tail *)((char *)cur_spot + b->buflen);
/* Copy our memory to the new pool */
- memcpy(cur_spot, b->bufstart,
- b->buflen);
- new_tail = 0;
+ memcpy(cur_spot, b->bufstart, b->buflen);
+ new_tail->flags = 0;
/* If we're COW */
if (b->flags & BUFFER_COW_FLAG) {
/* Let the old buffer know how to find us */
Index: string.c
===================================================================
RCS file: /cvs/public/parrot/string.c,v
retrieving revision 1.86
diff -p -u -r1.86 string.c
--- string.c 21 Aug 2002 08:00:10 -0000 1.86
+++ string.c 21 Aug 2002 23:27:55 -0000
@@ -32,15 +32,41 @@ unmake_COW(struct Parrot_Interp *interpr
else
#endif
if (s->flags & (BUFFER_COW_FLAG|BUFFER_constant_FLAG)) {
+ ptrdiff_t offset;
+
+ interpreter->GC_block_level++;
+ interpreter->DOD_block_level++;
+
+ /* Make the copy point to only the portion of the string that
+ * we are actually using. FIXME: If the string does not extend
+ * to the end of the buffer, this will waste space. To fix
+ * this, we need some way of translating a strlen back to a
+ * buflen (character count to byte count). That will need to
+ * be part of the string API. */
+ offset = (char*) s->strstart - (char*) s->bufstart;
s->bufstart = s->strstart;
- s->buflen = s->strlen;
+ s->buflen -= offset;
+
/* Create new pool data for this header to use,
* independant of the original COW data */
Parrot_reallocate_string(interpreter, s, s->buflen);
s->flags &= ~(UINTVAL)(BUFFER_COW_FLAG | BUFFER_constant_FLAG);
+ interpreter->GC_block_level--;
+ interpreter->DOD_block_level--;
}
}
+static void copy_string_header(String *dest, String *src)
+{
+#if GC_DEBUG
+ UINTVAL version = dest->version;
+ memcpy(dest, src, sizeof(String));
+ dest->version = version;
+#else
+ memcpy(dest, src, sizeof(String));
+#endif
+}
+
/* clone a string header without allocating a new buffer
* i.e. create a 'copy-on-write' string
*/
@@ -52,13 +78,13 @@ make_COW_reference(struct Parrot_Interp
d = new_string_header(interpreter,
s->flags & ~(UINTVAL)BUFFER_constant_FLAG);
s->flags |= BUFFER_COW_FLAG;
- memcpy(d, s, sizeof (STRING));
+ copy_string_header(d, s);
d->flags &= ~(UINTVAL)(BUFFER_constant_FLAG|BUFFER_selfpoolptr_FLAG);
}
else {
d = new_string_header(interpreter, s->flags);
s->flags |= BUFFER_COW_FLAG;
- memcpy(d, s, sizeof (STRING));
+ copy_string_header(d, s);
}
return d;
}
@@ -930,7 +956,7 @@ string_to_cstring(struct Parrot_Interp *
unmake_COW(interpreter, s);
- if (s->buflen == s->bufused) {
+ if (s->buflen == s->bufused) {
string_grow(interpreter, s, 1);
}
Index: include/parrot/dod.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/dod.h,v
retrieving revision 1.1
diff -p -u -r1.1 dod.h
--- include/parrot/dod.h 18 Jul 2002 04:32:53 -0000 1.1
+++ include/parrot/dod.h 21 Aug 2002 23:27:55 -0000
@@ -15,6 +15,7 @@
#if !defined(PARROT_DOD_H_GUARD)
#define PARROT_DOD_H_GUARD
+#include <assert.h>
#include "parrot/parrot.h"
void Parrot_do_dod_run(struct Parrot_Interp *);
@@ -24,9 +25,33 @@ PMC *trace_system_stack(struct Parrot_In
PMC * mark_used(PMC *used_pmc, PMC *current_end_of_list);
+#if GC_DEBUG
+/* Set when walking the system stack */
+extern int CONSERVATIVE_POINTER_CHASING;
+#endif
+
static void
buffer_lives(Buffer *buffer)
{
+#if GC_DEBUG
+ if (buffer->flags & BUFFER_on_free_list_FLAG) {
+ /* If a live buffer is found on the free list, warn. Note that
+ * this does NOT necessarily indicate the presence of a bug,
+ * because the stack is not zeroed out when a new stack frame
+ * is pushed, so old data on the stack might correctly point
+ * to a dead buffer. If the conservative_pointer_chasing flag
+ * is not set, this is not a possible explanation and the bug
+ * is real.
+ *
+ * If it *is* a bug, you may want to read the notes in
+ * get_free_buffer() in headers.c for tips on debugging using
+ * gdb with this pointer and version number. */
+ fprintf(stderr, "GC Warning! Live buffer %p version " INTVAL_FMT " found on
+free list\n", buffer, buffer->version);
+ if (! CONSERVATIVE_POINTER_CHASING) {
+ assert("parrot" == "bug-free");
+ }
+ }
+#endif
buffer->flags |= BUFFER_live_FLAG;
}
Index: include/parrot/interpreter.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/interpreter.h,v
retrieving revision 1.52
diff -p -u -r1.52 interpreter.h
--- include/parrot/interpreter.h 3 Aug 2002 07:35:36 -0000 1.52
+++ include/parrot/interpreter.h 21 Aug 2002 23:27:55 -0000
@@ -137,8 +137,8 @@ typedef struct Parrot_Interp {
void **prederef_code; /* The predereferenced code */
size_t current_line; /* Which line we're executing in the
* source */
- void *current_file; /* The file we're currently in */
- void *current_package; /* The package we're currently in */
+ String *current_file; /* The file we're currently in */
+ String *current_package; /* The package we're currently in */
/* Some counters for the garbage collector.xs */
size_t dod_runs; /* Number of times we've
Index: include/parrot/string.h
===================================================================
RCS file: /cvs/public/parrot/include/parrot/string.h,v
retrieving revision 1.45
diff -p -u -r1.45 string.h
--- include/parrot/string.h 21 Aug 2002 14:41:23 -0000 1.45
+++ include/parrot/string.h 21 Aug 2002 23:27:56 -0000
@@ -25,6 +25,9 @@ struct parrot_string_t {
void *bufstart;
UINTVAL buflen;
UINTVAL flags;
+#if GC_DEBUG
+ UINTVAL version;
+#endif
UINTVAL bufused;
void *strstart;
UINTVAL strlen;
@@ -42,6 +45,9 @@ typedef struct {
void *bufstart;
UINTVAL buflen;
UINTVAL flags;
+#if GC_DEBUG
+ UINTVAL version;
+#endif
} Buffer;
typedef struct parrot_string_t String;
