clone_p_p segfaults with self-referential Hash pmc.

[Austin_Hastings]

If a complex data structure, built with Hash and Array structures, is self-referencing, running clone_p_p on it will quickly segfault.

our %Global_hash;

sub bsu() {
	say("BSU: starting.");
	%Global_hash<key><key2> := 1;
	%Global_hash<key><loop> := %Global_hash;
	
	my %local := %Global_hash;
	
	my $result := Q:PIR {{
		$P0 = find_lex '%local'
		%r = clone $P0
	}};
	
	say("BSU: returning.");
	return $result;
	
}

bsu();

The solution here is likely to be involved -- perhaps disabling the GC and using the mark bit to track what has been cloned. But segmentation fault is not a parrot exception, which is what a memory problem should become.

Dukeleto confirms this problem exists on Darwin, and his Linux box.

FYI: I discovered this because PCT clones the symbol table of PAST::Block nodes.

[whiteknight]

clone_p_p is pretty naive, so it doesn't surprise me that there is a problem like this to be found in it. Actually, I'm surprised we haven't seen an issue like this sooner.

I suggest that what we should do when cloning an aggregate is keep a cache of already-cloned PMCs, and when we reach a PMC reference that exists in the cache we can swap it out with the already-cloned PMC reference from the cache.

Looking at an example:

$P0 = new 'Integer'
$P1 = new 'ResizablePMCArray'
$P1[0] = $P0
$P1[1] = $P0

In this case, the array contains two references to a single object, and we would expect that changing the value of the PMC in $P1[0] will also have an effect on the value in $P1[1]. A clone should follow these same semantics, I think.

This kind of solution would also allow us to avoid cycles: When we find a nested reference to something we've already cloned, we just swap references with the clone and the new datastructure is properly self-referential too.

I would like to hear some feedback before attempting to implement this fix.

[nick@…]

On Thu, Sep 17, 2009 at 01:09:12PM -0000, Parrot wrote:

>  I suggest that what we should do when cloning an aggregate is keep a cache
>  of already-cloned PMCs, and when we reach a PMC reference that exists in
>  the cache we can swap it out with the already-cloned PMC reference from
>  the cache.
> 
>  Looking at an example:
> 
>  {{{
>  $P0 = new 'Integer'
>  $P1 = new 'ResizablePMCArray'
>  $P1[0] = $P0
>  $P1[1] = $P0
>  }}}
> 
>  In this case, the array contains two references to a single object, and we
>  would expect that changing the value of the PMC in $P1[0] will also have
>  an effect on the value in $P1[1]. A clone should follow these same
>  semantics, I think.
> 
>  This kind of solution would also allow us to avoid cycles: When we find a
>  nested reference to something we've already cloned, we just swap
>  references with the clone and the new datastructure is properly self-
>  referential too.
> 
>  I would like to hear some feedback before attempting to implement this
>  fix.

This is certainly what Perl 5's Storable module does to detect things like
this, and I think what most of the dumper and cloner modules do.

In Perl 5 land, if we use a regular perl hash as the "seen" hash, it requires
roughly the same amount of memory for itself as the structure being copied.

It's more efficient to use some sort of smaller structure, that is specialised
to hash fixed length keys and fixed length values (void* and void*
respectively), but that could mean more code.

However, I think that there is code (at least was, back in 2005) in Parrot
to do this, used by the GC to track the set of externally rooted PMCs. So
it might not be much more code - if what it has is custom hashing, key is
address, value is integer seen count, then the value becomes a union of seen
count (for the GC) and pointer (for this).

Nicholas Clark

[Austin_Hastings]

Given that this is being implemented in core, we can probably just add a temporary pointer in the PMC header to do the job. (return clone_ptr ? clone_ptr : (clone_ptr = do_clone(self)); )

[whiteknight]

patch that fixes the clone issue using a new "clone registry" API. PGE fails to build with this however

[whiteknight]

Okay, I've attached my first stab at a patch. This patch is not intended to be committed as-is.

I created a new set of API functions for a "clone registry". The registry keeps track of objects that have been cloned in the current operation, so we don't recurse. The API is ugly (I can already think of a few ways to make it better and more performant), but it appears to mostly work. A short test program segfaults before the patch, and doesn't segfault after it:

.sub main :main
    $P0 = new 'Hash'
    $S0 = "Whatever"
    $P0[$S0] = $P0
    $P1 = clone $P0
    say "Ok"
.end

However, with this patch, PGE fails with a weird error:

../../parrot  /home/andrew/Projects/parrot/runtime/parrot/library/PGE/Perl6Grammar.pir \
	    --output=src/Grammar_gen.pir src/Grammar.pg
Can only replace inside string or index after end of string
current instr.: 'parrot;PGE;OPTable;newtok' pc 893 (compilers/pge/PGE/OPTable.pir:158)
called from Sub 'parrot;PGE;P5Regex;__onload' pc 12224 (compilers/pge/PGE/P5Regex.pir:86)
called from Sub 'parrot;PGE;Perl6Grammar;Compiler;__onload' pc 24 (/home/andrew/Projects/parrot/runtime/parrot/library/PGE/Perl6Grammar.pir:75)

so once we fix this PGE issue, rework the API to be better and clean up the patch a little bit, this should be what we need.

This patch only currently prevents recursions in Hash. I haven't used the new API in any other aggregate types where it is probably necessary to prevent recursions. Once we get everything working we will probably want to apply it to more PMC types to prevent issues from developing there too.

[whiteknight]

chromatic has a great point here, there's no reason why we couldn't
find a general solution to it. The basic requirements are (1) to store
a list of objects that have already been traversed (possibly with
metadata like a cloned version) and (2) be able to search for and
return the record of that traversal along with the associated
metadata.

Deep clone and PMC freeze are probably the best two candidates for a
change like this (I'm actually surprised we haven't seen more
segfaults in the past because of cyclic structures!). GC mark is a
little different because the PMC structure uses flags and other
pointers to keep track of which objects have been marked, and a
general solution might not work in all possible cores.

The patch I posted on TT #1015 is mostly a proof-of-concept that we
can resolve the particular segfault problem by caching
previously-traversed aggregates. As I've mentioned before, if we want
clone to preserve relationships between objects (repeated references),
we'll also want to cache everything that gets cloned. Take this for
example:

$P0 = new 'ResizablePMCArray'
$P0[0] = $P1
$P0[1] = $P1
$P2 = clone $P0

Here the data structure $P0 consists of two PMCs, while currently the
clone $P2 contains three! The two objects, though "clones", will
hardly behave similarly.

This brings us to two questions:

1) What is a generalized API for solving all these problems going to look like?
2) How widespread do we want it's use to be? Is the PIR example above
a problem for people?

--Andrew Whitworth



On Fri, Sep 18, 2009 at 9:54 PM, chromatic <chromatic@wgz.org> wrote:
> On Friday 18 September 2009 18:26:35 Parrot wrote:
>
>>  I created a new set of API functions for a "clone registry". The registry
>>  keeps track of objects that have been cloned in the current operation, so
>>  we don't recurse. The API is ugly (I can already think of a few ways to
>>  make it better and more performant), but it appears to mostly work.
>
> Note that "freeze", "deep clone", and "GC mark" are all so conceptually
> similar that they're the same problem: traversing a cyclic graph while
> avoiding cycles.
>
> If we can solve it for one case, perhaps we can solve it for all cases.
>
> -- c
> _______________________________________________
> parrot-tickets mailing list
> parrot-tickets@lists.parrot.org
> http://lists.parrot.org/mailman/listinfo/parrot-tickets
>

[coke]

On Fri, Sep 18, 2009 at 9:54 PM, chromatic <chromatic@wgz.org> wrote:
> On Friday 18 September 2009 18:26:35 Parrot wrote:
>
>>  I created a new set of API functions for a "clone registry". The registry
>>  keeps track of objects that have been cloned in the current operation, so
>>  we don't recurse. The API is ugly (I can already think of a few ways to
>>  make it better and more performant), but it appears to mostly work.
>
> Note that "freeze", "deep clone", and "GC mark" are all so conceptually
> similar that they're the same problem: traversing a cyclic graph while
> avoiding cycles.

See also the dumper lib.

> If we can solve it for one case, perhaps we can solve it for all cases.
>
> -- c
> _______________________________________________
> parrot-tickets mailing list
> parrot-tickets@lists.parrot.org
> http://lists.parrot.org/mailman/listinfo/parrot-tickets
>



-- 
Will "Coke" Coleda

[jkeenan]

whiteknight,

Can we get an update on the status of issues discussed in this ticket?

Thank you very much.

kid51