Thoughts on infant mortality...
Piers Cawley
that hasn't been tried before...
1. The problem of infant mortality is that resource allocation can
trigger a DOD run could wipe out the very thing we were allocating
memory for.
2. This can be solved by extending the rootset to include the 'baby'
things that we're working on.
3. But scanning the C stack is tricky, and there's also the problem of
scanning registers to deal with.
So, consider the function:
alloc_and_link( void ** handle, size_t size);
The idea is that, as part of the allocation process you also set the
link to it so, if the thing that we're pointing at our newly allocated
block of memory is connected back to the rootset then said newly
allocated block can't be reaped.
Now define the rootset as:
1. The parrot register set
2. The tops of the appropriate parrot stacks
3. A set of one or more (possibly typed) 'scratch' handles for
hanging temporaries off.
Now, all our functions which create PMCs and the like will take an
extra argument -- a handle to hang the created object off and, if
that's null, then they are free to use the appropriate scratch
handle.
opcode functions (and probably only opcode functions) can then do
(pseudocode):
op_foo (IN reg_in, OUT reg_out)
new_pmc = make_a_pmc_with_register( reg_in, the_pmc_scratch_handle)
reg_out = new_pmc or UNDEF
the_pmc_scratch_handle = NULL
Note that NULLing the scratch handles could potentially be moved out
into the main oploop, making life easier for the programmer.
From my (admittedly handwaving) perspective, limiting the rootset to a
fixed list of things would seem to be a good idea. The question
is whether the cost of adding the extra target parameters to
everything is worth paying.
In a weird way, this can be thought of as a 'caller saves' approach to
allocation...
Leopold Toetsch
> alloc_and_link( void ** handle, size_t size);
This is covered in Steve Finks summary as solution 3.
There were also two code snippets by Brent Dax and Jerome Vouillon, that
deal with exception handling too. s. thread "Infant mortality" started
by Steve.
> Note that NULLing the scratch handles could potentially be moved out
> into the main oploop, making life easier for the programmer.
This is not an option, it would make the whole runloop slower. It does
also not work, when a PMC calls out to interpreted code, this would then
unanchor the handles.
But I still favor the combination of:
- code reordering, like done for pmc_new
- DOD/GC disabling (e.g. aggregate clone)
- active anchoring to the root set, where above is not applicable
leo
Nicholas Clark
> But I still favor the combination of:
> - code reordering, like done for pmc_new
> - DOD/GC disabling (e.g. aggregate clone)
> - active anchoring to the root set, where above is not applicable
Which combined means that there is no stackwalking?
ie user code has to have the discipline either to have things linked to the
root set by the time it makes a parrot call or explicitly disable DOD across
such a call.
(or to explode in a cloud of feathers)
Nicholas Clark
Leopold Toetsch
> On Thu, Jan 09, 2003 at 01:32:57PM +0100, Leopold Toetsch wrote:
>
>>But I still favor the combination of:
>>- code reordering, like done for pmc_new
>>- DOD/GC disabling (e.g. aggregate clone)
>>- active anchoring to the root set, where above is not applicable
>>
>
> Which combined means that there is no stackwalking?
Yep. This is the goal.
> ie user code has to have the discipline either to have things linked to the
> root set by the time it makes a parrot call or explicitly disable DOD across
> such a call.
Yes. We need some XS guidelines anyway. One more rule or less or some
ENTER/LEAVE or LOCAL_PMC macros, which do the Right Thing.
> (or to explode in a cloud of feathers)
Explode is a harsh word for a seg fault, though somehow softened by the
feathers :-)
> Nicholas Clark
leo
Dan Sugalski
>Nicholas Clark wrote:
>>ie user code has to have the discipline either to have things linked to the
>>root set by the time it makes a parrot call or explicitly disable DOD across
>>such a call.
>
>
>Yes. We need some XS guidelines anyway. One more rule or less or
>some ENTER/LEAVE or LOCAL_PMC macros, which do the Right Thing.
To be honest, I was going to cheat with XS code. Allocation of
PMC/Buffer/String objects through the XS interface would
automagically push those objects onto the user stack, and leaving the
XS routine would pop them back off. (They're presumably either rooted
or dead at that point)
A bit slower than could otherwise be, but...
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Dan Sugalski
>On Thu, Jan 09, 2003 at 01:32:57PM +0100, Leopold Toetsch wrote:
>> But I still favor the combination of:
>> - code reordering, like done for pmc_new
>> - DOD/GC disabling (e.g. aggregate clone)
>> - active anchoring to the root set, where above is not applicable
>
>Which combined means that there is no stackwalking?
While I'd like no stack walking, as it's pricey, I'm not sure it's
tenable. Skipping it makes things rather more fragile, as it means
that any code that may potentially trigger a DOD run while holding an
unrooted object needs to root it temporarily, and that's a lot of
code. Calling any vtable or string function will do it, which is
pretty common for most of the operations that are creating new
objects.
We could probably twist the design around such that unrooted live
objects are impossible, but I'm not sure I'm up to that level of
brain twisting.
Leopold Toetsch
> At 4:17 PM +0000 1/9/03, Nicholas Clark wrote:
>
>> On Thu, Jan 09, 2003 at 01:32:57PM +0100, Leopold Toetsch wrote:
>>
>>> But I still favor the combination of:
>>> - code reordering, like done for pmc_new
>>> - DOD/GC disabling (e.g. aggregate clone)
>>> - active anchoring to the root set, where above is not applicable
>>
>>
>> Which combined means that there is no stackwalking?
>
>
> While I'd like no stack walking, as it's pricey, I'm not sure it's
> tenable.
As the current clone changes does show, it's possible.
BTW current tests do succed w/o stackwalking - its disabled.
> ... Skipping it makes things rather more fragile, as it means that
> any code that may potentially trigger a DOD run while holding an
> unrooted object needs to root it temporarily, and that's a lot of code.
Its a bit more fragile, for unchecked or new code. PMCs ought to be
already save now. The "new" and "clone" ops do already anchor the newly
created object to the root set.
Also I was thinking of: trace_system_areas could be run last in marking
and if it finds some unanchored objects, it could print a warning, so we
could really check, if we ware safe.
leo
Steve Fink
> Also I was thinking of: trace_system_areas could be run last in marking
> and if it finds some unanchored objects, it could print a warning, so we
> could really check, if we ware safe.
That's what defining GC_VERBOSE in parrot.h will give you right now,
and it's usually too noisy to be useful. For some reason, it seems to
be very common to have old PMC pointers lying around on the stack.
(Which is a further argument against it, I guess -- the stackwalk may
hang onto significant chunks of memory and cause later allocations to
fail unnecessarily. That's true of most of the suggested schemes to
some degree, but GC_VERBOSE gives an estimate of how bad it is for
stackwalking. A poor estimate, though, since most of the stale
pointers it finds are probably not holding onto much memory, but it
can only get worse.)
I am committing the summary I wrote into parrot/docs/dev/infant.dev,
since I see that as the original idea behind the .dev files -- to
record the justifications for design decisions along with the other
variants, so people don't need to recreate them quite as often.
On the other hand, the other part of the impetus for *.dev files was
to pair them up with actual source files, but so far that doesn't
appear popular enough to actually happen. (I have mixed feelings
tending toward the negative about that idea anyway.)
The summary should really be updated to reflect some of the further
discussions we've had. I ought to add at least a section on hybrid
schemes (eg anchor what you can, have a temporary root for the rest),
interaction with the (weakened) finalization guarantees needed for
Perl6, and the schemes for allowing some of the listed approaches to
work in the presence of longjmp() and recursive calls.
But I don't have the time at the moment. Anyone else is more than free
to update it once it's checked in. [And it isn't yet -- looks like
/tmp is full on the cvs server at the moment.]
Leopold Toetsch
> On Jan-10, Leopold Toetsch wrote:
>
>>Also I was thinking of: trace_system_areas could be run last in marking
>>and if it finds some unanchored objects, it could print a warning, so we
>>could really check, if we ware safe.
>>
>
> That's what defining GC_VERBOSE in parrot.h will give you right now,
Gave, until pobject_lives() changes ;-)
But I did reintroduce this with above idea. And a local GC_VERBOSE for
easier switching.
> and it's usually too noisy to be useful. For some reason, it seems to
> be very common to have old PMC pointers lying around on the stack.
Yep. Seems so.
I'll continue my early anchoring patches, we will see.
> (Which is a further argument against it, I guess -- the stackwalk may
> hang onto significant chunks of memory and cause later allocations to
> fail unnecessarily. That's true of most of the suggested schemes to
> some degree, but GC_VERBOSE gives an estimate of how bad it is for
> stackwalking. A poor estimate, though, since most of the stale
> pointers it finds are probably not holding onto much memory, but it
> can only get worse.)
And it's getting worse with register walking on RISC machines.
> I am committing the summary I wrote into parrot/docs/dev/infant.dev,
Greate, thanks.
> On the other hand, the other part of the impetus for *.dev files was
> to pair them up with actual source files,
I'd rather have this kind of docu in the source file.
leo
Jason Gloudon
> >While I'd like no stack walking, as it's pricey, I'm not sure it's
> >tenable.
>
> As the current clone changes does show, it's possible.
>
> BTW current tests do succed w/o stackwalking - its disabled.
>
> >... Skipping it makes things rather more fragile, as it means that
> >any code that may potentially trigger a DOD run while holding an
> >unrooted object needs to root it temporarily, and that's a lot of code.
Without the stack/register examination the following can occur (though nothing
does this yet)
1) A PMC is accessible from the root set when a vtable is called. Either via a
reference or being a member of an aggregate.
2) A vtable function obtains a PMC* to that PMC.
3) The vtable calls some code deletes the reference to the PMC, which is now
no longer accessible from the root set. The vtable then attempts to allocate
some memory.
The vtable function will now contain the only remaining reference to the PMC,
but unless the vtable function has added that PMC to the root set somehow it
will be collected prematurely.
This means that even some would that are already rooted need to be treated
specially. From this example, any object in an aggregate.
On a related note, I have been looking at implementation techniques for
incremental/generational garbage collectors. A critical aspect of a
generational garbage collector is a write barrier, which records any pointer
writes that create references to a generation from an older generation.
In the context of parrot this means identifying every place that a PMC pointer
is updated. The only portable way to do this is by explicit checks in the
interpreter and code produced by the JIT. The current flexibility in parrot
allows C code to freely update PMC pointers, so such checks would have to be
manually inserted in so many places as to become untenable.
The non-portable techniques for implementing write barriers include marking
pages read-only and trapping SIGSEGV's on any write or using the hardware dirty
bits to find pages that have been written. Besides portability, these
techniques are not really well supported by the operating system and have their
own inefficiencies.
I believe the above considerations present some basic choices:
1) Create new conventions for manipulating the interpreter state from C code
that that make all PMC pointers immediately accesible to the garbage collector.
(The infant mortality issue has started movement in this direction)
This will make parrot slower in general (The C compiler will be unable to
perform register allocation of many PMC pointers in addition to the additional
overhead), but makes a stop the world collector faster and allows an
incremental collector which can shorten the pauses due to collector runs. It
also makes for more rules for core programmers or extension writers to follow.
2) Rework the implementation so that the vtables or any other opcodes that may
callback into parrot are entirely/mostly implemented in parrot ops that can be
JIT compiled. This way we can still get optimized vtable code that allows an
incremental collector.
3) Give up on a portable incremental collector and stick with the current stop
the world collector. Parrot's basic execution speed will be unchanged. By
trading heap size against frequency of collector runs, one could amortize the
cost of running the collector. Extension and core code programmers would never
have to think about the garbage collector in order to write correct code.
--
Jason
Leopold Toetsch
> 3) The vtable calls some code deletes the reference to the PMC, which is now
> no longer accessible from the root set. The vtable then attempts to allocate
> some memory.
>
> The vtable function will now contain the only remaining reference to the PMC,
> but unless the vtable function has added that PMC to the root set somehow it
> will be collected prematurely.
I don't get that.
When e.g. in 3) the hash containing the PMC is deleted, the PMC is
dead., when this was the last reference to the PMC. Working with it
doesn't make sense for me.
leo
Dan Sugalski
>On a related note, I have been looking at implementation techniques for
>incremental/generational garbage collectors. A critical aspect of a
>generational garbage collector is a write barrier, which records any pointer
>writes that create references to a generation from an older generation.
This is probably the single biggest thing that makes me want to mess
directly with the hardware.
What I've been contemplating is requiring PMC pointer stores to go
through a macro. (I know, I know--"Ick, macros! They're evil!") If
we're careful about it, it means that we can do some experimentation
with GC techniques (and yes, even potentially with refcounting)
without having to make huge changes to the source base.
Steve Fink
> On Fri, Jan 10, 2003 at 01:05:05PM +0100, Leopold Toetsch wrote:
>
> > >While I'd like no stack walking, as it's pricey, I'm not sure it's
> > >tenable.
> >
> > As the current clone changes does show, it's possible.
> >
> > BTW current tests do succed w/o stackwalking - its disabled.
> >
> > >... Skipping it makes things rather more fragile, as it means that
> > >any code that may potentially trigger a DOD run while holding an
> > >unrooted object needs to root it temporarily, and that's a lot of code.
>
> Without the stack/register examination the following can occur (though nothing
> does this yet)
>
> 1) A PMC is accessible from the root set when a vtable is called. Either via a
> reference or being a member of an aggregate.
>
> 2) A vtable function obtains a PMC* to that PMC.
>
> 3) The vtable calls some code deletes the reference to the PMC, which is now
> no longer accessible from the root set. The vtable then attempts to allocate
> some memory.
Nope, that example is just a plain ol' use-of-freed-memory bug. If you
delete something, don't look at it again. However, if you change the
example to simply unanchoring the PMC, then you have a problem. For
example, consider a vtable method that is removing a PMC from the
middle of one aggregate and pushing it onto the end of another. If you
remove the PMC first (replacing it with an undef PMC, say) and then
push it onto the second aggregate, the push operation may allocate
memory (to expand the aggregate) at a time when the PMC is unanchored.
This is similar to the infant mortality, but shows that it doesn't
only happen to infants.
The solution is also similar: reorder instructions. If you push
the PMC onto the second aggregate before removing it from the first,
you're ok. And once again, it's unclear how big of a restriction this
is in general, and in particular for extension code. (Although I'd
probably deal with extensions by disabling DOD for them by default,
but providing a flag bit they can set that says "in return for keeping
the garbage collector active while I run, I promise to follow all the
necessary rules.")
Re: incremental gc
It seems to me that the nice way of getting incremental gc would be to
only provide it on platforms that provide the necessary hardware
support. Then, rather than making the other platforms slower, have
them use a non-incremental collector. (Actually, we'd probably want
the option of not using the incremental collector even on the
platforms that support it, since it would most likely be trading
throughput for latency.) The trick is that the restrictions on
extension code would then need to be the union of the restrictions for
all the different gcs -- so those sets of restrictions had better be
very similar!
Jason Gloudon
> > reference or being a member of an aggregate.
> >
> > 2) A vtable function obtains a PMC* to that PMC.
> >
> > 3) The vtable calls some code deletes the reference to the PMC, which is now
> > no longer accessible from the root set. The vtable then attempts to allocate
> > some memory.
> Nope, that example is just a plain ol' use-of-freed-memory bug. If you
> delete something, don't look at it again. However, if you change the
The point here is that the PMC's reference may be deleted because you don't
know the side-effects of code that you're calling, so you would always have to
make sure it is anchored, and incur the overheads etc.
--
Jason