An algorithm for heap-reclamation on failure

[Thomas Charles CONWAY]

Hi

Here is a new algorithm for allowing the reclamaition of heap on failure
(which we currently do in non-gc grades) for the case where multiple
threads of execution may use a single heap. Your comments would be welcome,
especially if you find a bug in it.

The heap grows up, and hp is the register that points to the top of the
heap. Currently, when a choice-point is created, we save the value of hp
into the choice point so that on backtracking we can reset the value of
hp to what it was when we started the failed computation (this is safe
because a failed computation may not have any side-effects or output
bindings, so nothing that it allocated can be refered to again). This
is a very cheap form of garbage collection which is important for some
programs.

In the case of an implementation that allows multiple goals to execute in
an interleaved fashion, it is not possible to do this heap-reclamation in
the same way because if goal A allocates some data, then goal B gets
executed for a bit and allocates some data, then goal A executes some more
and fails, it cannot simply truncate the heap back to where it created
the choice point, since it may reset hp to a point below (or in) B's data,
which would the be overwritten when A did more allocation. It is safe
however for A to reset hp back as far as the top of B's data. This may
mean that not all of A's garbage gets deallocated on backtracking, but
it does ensure that none of B's live data gets corrupted.

The algorithm I propose is this:
Each goal has a data structure with bits of 'state' for that goal in it
(eg the stack pointer, succip, etc). In that data structure we store
a copy of hp (to which I'll refer as `saved') and the lowest value to which
it is safe to reset hp (to which I'll refer as `min'). When we create
the state structure for the goal, we initialize `saved' to NULL.

When we decide to stop executing a goal to allow some execution to take
place in another goal, we save the values of various global registers
(of the virtual machine) into the goal's state structure (eg sp and succip).
We save the current value of `hp' at this point into the `saved' field
of this structure.

When we make a goal the currently executing goal, we load various bits
of its state into the global registers (eg sp and succip). We also do
a comparison of `saved' and `hp'. The following cases can occur:

`saved' == NULL	: this is the first time this goal has been scheduled,
		  so the lowest value to which we can safely reset `hp'
		  is whatever the current value of `hp' is.

`saved' < `hp'	: some other goal[s] have allocated data on the heap since
		  we last scheduled this goal. Therefore the lowest value
		  to which we can safely reset `hp' is whatever the current
		  value of `hp' is.

`saved' == `hp'	: no data has been allocated since this goal was last
		  scheduled (or if it has, it has all been reclaimed by
		  backtracking). Therefore the lowest value to which we
		  can reset `hp' on backtracking is whatever the lowest
		  value was last time we were scheduled.

`saved' > `hp'	: ask yourself "how can it happen that the value of `hp'
		  is lower when we resume than it was when we were last
		  being executed?" It took me a while to figure it out.
		  If goal A runs and allocates data, then goal B  runs but
		  does not allocate data, when goal A runs again `hp' ==
		  its `saved' value, so it can reclaim heap on backtracking.
		  When B next runs `hp' may then be less than it was before.
		  It is safe for this goal to reset `hp' to whatever the
		  current value of `hp' is.

This suggests the following code:

code for resuming execution of a goal:
	...
	if (goal_state->saved == NULL || goal_state->saved != hp)
	{
		min = hp;
	}
	else
	{
		min = goal_state->min;
	}
	....

code for saving the state of a goal before scheduling another goal:
	...
	goal_state->saved = hp;
	goal_state->min = min;
	....

code for reclaiming heap on backtracking:
	...
	/* oldval is the value of hp that was stored in the choice-point */
	hp = (oldval > min ? oldval : min);
	....

Comments?
-- 
Thomas Conway               				      conway at cs.mu.oz.au
AD DEUM ET VINUM	  "Thomas Tallis is dead, and muic dies." - William Byrd