From: Julian Stecklina
Subject: Real-Time Garbage Collection
Date: 
Message-ID: <8664wse7q1.fsf@dellbeast.localnet>
Hello,

This is a question specific to Baker's original paper about real-time
garbage collection from 1978 which may be found via portal.acm.org. If
there is a better place to ask this, please feel free to point me
there.

In his paper he presents a method of incrementally scanning the user
stack. This is done by using a stack scan pointer that points to the
bottom of the stack, each time the algorithm completed copying. 

My problem is that he assumes that if the Bottom heap pointer meets
the top heap pointer (-> heap is full) the current stack scan pointer
must be pointing to the top of stack. If have code like the following
this is easily violated:

                 ; Heap is full here, stack is fully scanned
push(foo)        ; unscanned item on stack
x := cons(a, b); ; cons fails due to unscanned item on stack

Am I missing something?

Regards,
-- 
Julian Stecklina

"Object-oriented programming offers a sustainable way to write
spaghetti code." - Paul Graham

From: Pascal Bourguignon
Subject: Re: Real-Time Garbage Collection
Date: 
Message-ID: <87k6l75dzn.fsf@thalassa.informatimago.com>
Julian Stecklina <··········@web.de> writes:
> My problem is that he assumes that if the Bottom heap pointer meets
> the top heap pointer (-> heap is full) the current stack scan pointer
> must be pointing to the top of stack. If have code like the following
> this is easily violated:
>
>                  ; Heap is full here, stack is fully scanned
> push(foo)        ; unscanned item on stack
> x := cons(a, b); ; cons fails due to unscanned item on stack
>
> Am I missing something?

Where is x?

If it's a local variable or a parameter it's probably on the stack.
If it's a global variable, it may be on the heap, and refered.

The problem occurs when x is a register.  But note that when the
garbage collector works, it should have saved the registers on the
stack, so problem solved...

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
You never feed me.
Perhaps I'll sleep on your face.
That will sure show you.
From: Hannah Schroeter
Subject: Re: Real-Time Garbage Collection
Date: 
Message-ID: <d83t1l$egp$1@c3po.use.schlund.de>
Hello!

Pascal Bourguignon  <···@informatimago.com> wrote:
>Julian Stecklina <··········@web.de> writes:
>> My problem is that he assumes that if the Bottom heap pointer meets
>> the top heap pointer (-> heap is full) the current stack scan pointer
>> must be pointing to the top of stack. If have code like the following
>> this is easily violated:

>>                  ; Heap is full here, stack is fully scanned
>> push(foo)        ; unscanned item on stack
>> x := cons(a, b); ; cons fails due to unscanned item on stack

>> Am I missing something?

>Where is x?

>If it's a local variable or a parameter it's probably on the stack.
>If it's a global variable, it may be on the heap, and refered.

>The problem occurs when x is a register.  But note that when the
>garbage collector works, it should have saved the registers on the
>stack, so problem solved...

Alternatively it should get passed a bitmask on invocation which
registers to include in the root set.

Kind regards,

Hannah.
From: Julian Stecklina
Subject: Re: Real-Time Garbage Collection
Date: 
Message-ID: <86vf4o5xtj.fsf@dellbeast.localnet>
Pascal Bourguignon <···@informatimago.com> writes:

> Julian Stecklina <··········@web.de> writes:
>> My problem is that he assumes that if the Bottom heap pointer meets
>> the top heap pointer (-> heap is full) the current stack scan pointer
>> must be pointing to the top of stack. If have code like the following
>> this is easily violated:
>>
>>                  ; Heap is full here, stack is fully scanned
>> push(foo)        ; unscanned item on stack
>> x := cons(a, b); ; cons fails due to unscanned item on stack
>>
>> Am I missing something?
>
> Where is x?
>
> If it's a local variable or a parameter it's probably on the stack.
> If it's a global variable, it may be on the heap, and refered.
>
> The problem occurs when x is a register.  But note that when the
> garbage collector works, it should have saved the registers on the
> stack, so problem solved...

x could be a register. But I already solved the problem. Maybe I
misunderstood the paper the first time. The solution is that you only
need to scan the stack from the bottom to the point where the last
fromspace/tospace-flip occured and not all the way to the top, as the
latter part can only contain tospace pointers.

Thanks anyway.  :) Are these questions better asked in comp.compilers?

Regards,
-- 
Julian Stecklina

"We were not out to win over the Lisp programmers; we were after the
C++ programmers. We managed to drag a lot of them about halfway to
Lisp." - Guy Steele, Java spec co-author
From: Hannah Schroeter
Subject: Re: Real-Time Garbage Collection
Date: 
Message-ID: <d87uin$tah$1@c3po.use.schlund.de>
Hello!

Julian Stecklina  <··········@web.de> wrote:
>[...]

>x could be a register. But I already solved the problem. Maybe I
>misunderstood the paper the first time. The solution is that you only
>need to scan the stack from the bottom to the point where the last
>fromspace/tospace-flip occured and not all the way to the top, as the
>latter part can only contain tospace pointers.

*nods*

>Thanks anyway.  :) Are these questions better asked in comp.compilers?

Not exactly. There's a mailing list for GC related stuff called
gclist.

See http://www.iecc.com/gclist/

Kind regards,

Hannah.