Garbage collector memory leak "feature"?

[Frits van Bommel]

Sean Kelly wrote:
> David Brown wrote:
>>
>> I'm not sure I understand why these restrictions aren't possible under D.
>> They might not be possible with the current implementation, but I didn't
>> see anything in the language spec that requires inexactness to the GC.
>>
>> It might not meet some performance or other memory requirements some 
>> users
>> have, but it should be possible to make the GC exact.
> 
> With one stipulation, I believe this could be true of blocks allocated 
> by the GC.  Type information could be supplied by the runtime, etc, to 
> allow exact scanning.  The stipulation being that D users may have a 
> desire or a need to occasionally allocate untyped memory blocks, such as 
> void[].  In these cases, conservative scanning would be necessary.

I completely agree.

> However, that still leaves the stack as an unknown element.  At present, 
> the GC doesn't know anything about what a pointer-sized stack value 
> represents, and I don't see how this could be communicated or 
> determined.  But perhaps this is just a gap in my knowledge of GC theory.

Couldn't this be implemented as a lookup table, with elements like 
(start addr, end addr, (pointer to) stack frame description)? Since this 
is only needed when the GC paused all threads (assuming a stop-the-world 
collector) this would allow the GC to walk over all stack frames and use 
the stack frame descriptions to determine which cells contain pointers. 
The descriptions could be as simple as
struct stackframeInfo {
     /// The range of addresses covered by this entry.
     void* startAddress;
     void* endAddress;   /// ditto

     /// Number of cells in the stackframe.
     size_t cellCount;
     /// Cell nr of the return address in the frame, to walk the stack.
     size_t returnAddrCell;
     /** Trailing bitsequence: a 1 means the corresponding cell is a
      *  pointer and a 0 means it isn't.
      *  After cellCount bits the rest of the last element should be 0.
      */
     uint[0] pointerBits;
}
but there may need to be an extra member to allow an offset from EBP so 
this can also specify the types of stack-based parameters; however those 
are perhaps best handled on the calling side to deal with varargs and 
with partial call sequence (the GC interrupting a thread that has pushed 
parameters but hasn't yet actually called the function it's pushing them 
for).

To cut down on space overhead, this could perhaps also be integrated 
into the exception handling tables; they'll typically cover similar 
regions. That'd probably increase the overhead for exception handling 
though, since suddenly every function has an exception table that needs 
to be inspected (not just the ones with try/catch or scope() statements).