www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Garbage collector memory leak "feature"?

reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
Something has come to light in a few posts that has described memory leak 
problems because the garbage collector finds ghost pointers in hash data. 
My understanding of the problem is that the garbage collector marks data 
allocations as having pointers or not having pointers, and then searches 
through all the data to see if there are any valid pointers, finding data 
that looks like a pointer, but is not. (BTW, this seems inefficient to me, 
but I have no idea how to write a garbage collector)

The most disturbing thing I've seen in these posts is the assumption that 
this is just the way the garbage collector is, and shame on me for writing 
code that fools it.

So I have some questions, coming from someone who knows nothing about 
writing garbage collectors, but loves the usage of them.

1. Is this just the way all garbage collectors are?  Is there not a way to 
solve this problem?
2. Does Tango have this problem?  I know the GC's are different, and I use 
tango, so maybe I could just say, too bad for phobos users and be on my way 
:)
3. If it is solvable, is anyone working on this?  If not, they should be. 
Add this to the list of things that need to be fixed before D has widespread 
adoption.  Memory leaks == bad bad bad.

-Steve
Oct 10 2007
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Steven Schveighoffer wrote:

 Something has come to light in a few posts that has described memory leak 
 problems because the garbage collector finds ghost pointers in hash data. 
 My understanding of the problem is that the garbage collector marks data 
 allocations as having pointers or not having pointers, and then searches 
 through all the data to see if there are any valid pointers, finding data 
 that looks like a pointer, but is not. (BTW, this seems inefficient to me, 
 but I have no idea how to write a garbage collector)
 
 The most disturbing thing I've seen in these posts is the assumption that 
 this is just the way the garbage collector is, and shame on me for writing 
 code that fools it.
 
 So I have some questions, coming from someone who knows nothing about 
 writing garbage collectors, but loves the usage of them.
 
 1. Is this just the way all garbage collectors are?  Is there not a way to 
 solve this problem?


Not all garbage collectors are like this.  Java, for example, uses an 
exact GC.  The accuracy of a GC is really a combination of the GC design 
and of the reflection facilities provided by the language.  D's 
reflection facilities are somewhat limited and will likely never be 
perfect because it is a systems programming language and does not run in 
a VM.


 2. Does Tango have this problem?  I know the GC's are different, and I use 
 tango, so maybe I could just say, too bad for phobos users and be on my way 
 :)


Tango's GC was more accurate than the Phobos GC when Tango was 
announced, but Phobos has since caught up.  As things stand now, the two 
are roughly equivalent, though there are a few places in the Tango 
runtime which provide a bit more accuracy than Phobos (such as the AA code).


 3. If it is solvable, is anyone working on this?  If not, they should be. 
 Add this to the list of things that need to be fixed before D has widespread 
 adoption.  Memory leaks == bad bad bad.


One slightly weird or confusing thing about D now is that void[] arrays 
are treated as if they contains pointers.  This is likely a significant 
source of "leaks."  However, treating void[] arrays as if they contain 
pointers is reasonable, given the concept that void represents.

The accuracy of garbage collection in D could be further improved by 
increasing the amount of type information available to the GC.  For 
example, if the GC knew /where/ in a memory block the pointers were, it 
could ignore the other parts.  However, this would also increase the 
memory used by the GC because it would have to store mask info or 
something comparable for allocated blocks.  It could also slow down 
collection in well-behaved (ie. lucky) apps because the collection 
algorithm would be a bit more complicated.

There are also other GC designs that could be used, but those would 
mostly affect the speed of garbage collection rather than its accuracy.


Sean
Oct 10 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Sean Kelly" wrote

 Steven Schveighoffer wrote:

 1. Is this just the way all garbage collectors are?  Is there not a way 
 to solve this problem?


 Not all garbage collectors are like this.  Java, for example, uses an 
 exact GC.  The accuracy of a GC is really a combination of the GC design 
 and of the reflection facilities provided by the language.  D's reflection 
 facilities are somewhat limited and will likely never be perfect because 
 it is a systems programming language and does not run in a VM.


OK, I can see where you are coming from.


 One slightly weird or confusing thing about D now is that void[] arrays 
 are treated as if they contains pointers.  This is likely a significant 
 source of "leaks."  However, treating void[] arrays as if they contain 
 pointers is reasonable, given the concept that void represents.


Yeah, I'd say if you are relying on void arrays to store your pointers, you 
should be SOL.  If you want to use void[] to contain pointers, you should 
also have to maintain the pointer somewhere else as well to prevent the 
memory from being collected.  Can anyone give an example of where this is 
*necessary* and not just convenient?

If this problem did not exist with void[], would these memory leak problems 
be solved?


 The accuracy of garbage collection in D could be further improved by 
 increasing the amount of type information available to the GC.  For 
 example, if the GC knew /where/ in a memory block the pointers were, it 
 could ignore the other parts.  However, this would also increase the 
 memory used by the GC because it would have to store mask info or 
 something comparable for allocated blocks.  It could also slow down 
 collection in well-behaved (ie. lucky) apps because the collection 
 algorithm would be a bit more complicated.


It would be nice if this was up to the developer.  For example, Microsoft 
C++.NET solves this problem by having two types of memory, gc memory and 
'classic' memory.  If you want to use the garbage collector (they call it 
'managed' code), you declare your class with a __gc modifier.

Would it be possible to allow for optimizations for people who are not 
interested in garbage collection, but are interested in speed/mem usage, to 
use some other memory allocation scheme that does not use the garbage 
collector?  Then throw away the assumptions that have caused these leaks to 
occur (e.g. void[] can contain pointers)?


 There are also other GC designs that could be used, but those would mostly 
 affect the speed of garbage collection rather than its accuracy.


to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer == broken 
gc.  Speed/mem usage is secondary.

-Steve
Oct 10 2007
next sibling parent reply 0ffh <spam frankhirsch.net> writes:
Steven Schveighoffer wrote:

 Yeah, I'd say if you are relying on void arrays to store your pointers,
 you should be SOL.  If you want to use void[] to contain pointers, you
 should also have to maintain the pointer somewhere else as well to
 prevent the memory from being collected.  Can anyone give an example of
 where this is *necessary* and not just convenient?


If you want to keep extra copies of your pointers, then just do it for
glod's sake, and use ubyte[] for memory allocation!
There is no need at all  to change the behaviour of the gc WRT void[].


 Would it be possible to allow for optimizations for people who are not 
 interested in garbage collection, but are interested in speed/mem usage,
 to use some other memory allocation scheme that does not use the garbage
  collector?  Then throw away the assumptions that have caused these
 leaks to occur (e.g. void[] can contain pointers)?


IIRC just use std.c.malloc to get unmanaged memory blocks.


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.


Well, the rest of us calls it "conservative garbage collector"... =)

Regards, Frank
Oct 10 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"0ffh" wrote

 Steven Schveighoffer wrote:

 Yeah, I'd say if you are relying on void arrays to store your pointers,
 you should be SOL.  If you want to use void[] to contain pointers, you
 should also have to maintain the pointer somewhere else as well to
 prevent the memory from being collected.  Can anyone give an example of
 where this is *necessary* and not just convenient?


 If you want to keep extra copies of your pointers, then just do it for
 glod's sake, and use ubyte[] for memory allocation!
 There is no need at all  to change the behaviour of the gc WRT void[].


I was not promoting the use of void[] to keep an only copy of a pointer.  I 
was against it.  And I think if the gc is going to assume for *my* benefit 
that random data I create could be a pointer, and therefore not collect data 
it points to, then it needs to be changed.

I personally don't use void[] for anything because I don't see the need for 
it in my code, but I can't make other libraries that I use change their 
code.

But why should the GC have to worry about pointers in random data?  My 
question is, is there a *need* for the GC to assume any data could be a 
pointer, does any code actually *depend* on that behavior?  I really would 
like to see an example of where it is necessary.


 Would it be possible to allow for optimizations for people who are not 
 interested in garbage collection, but are interested in speed/mem usage,
 to use some other memory allocation scheme that does not use the garbage
  collector?  Then throw away the assumptions that have caused these
 leaks to occur (e.g. void[] can contain pointers)?


 IIRC just use std.c.malloc to get unmanaged memory blocks.


Cool.  So there is a way to do this, and therefore the garbage collector can 
use more memory if it needs to in order to not leak memory, and people who 
want less memory usage/speed could use malloc.


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.


 Well, the rest of us calls it "conservative garbage collector"... =)


So it's fine with you if your application keeps crashing every 2 days 
because it gradually leaks all the memory on your system?  I'm sure that 
will do wonders for the adoption of D.

IMO conservative would be the other way around.  Conservative would be to 
not assume something is a pointer unless it is.  I would call the current 
behavior ... overassuming, maybe neurotic, or paranoid even? :)

coder: GC, there is only random data in that block
GC: NO!!! it could be a POINTER!!!  THEY'RE EVERYWHERE!!!

-Steve
Oct 10 2007
parent reply 0ffh <spam frankhirsch.net> writes:
Steven Schveighoffer wrote:

 "0ffh" wrote

 Steven Schveighoffer wrote:

 Yeah, I'd say if you are relying on void arrays to store your pointers,
 you should be SOL.  If you want to use void[] to contain pointers, you
 should also have to maintain the pointer somewhere else as well to
 prevent the memory from being collected.  Can anyone give an example of
 where this is *necessary* and not just convenient?


 If you want to keep extra copies of your pointers, then just do it for
 glod's sake, and use ubyte[] for memory allocation!
 There is no need at all  to change the behaviour of the gc WRT void[].


 I was not promoting the use of void[] to keep an only copy of a pointer.  I 
 was against it.  And I think if the gc is going to assume for *my* benefit 
 that random data I create could be a pointer, and therefore not collect data 
 it points to, then it needs to be changed.


I was not suggestung you were promoting the use of void[] to keep an only
copy of a pointer. :)
I /was/ suggesting you were suggesting to not scan void-type (=untyped)
memory blocks for pointers, and keep the pointers (or copies of them)
elsewhere to circumvent collection of life objects.
I was further suggesting that by using ubyte[] instead of void[] you
can do that already, as ubyte[] is not scanned for pointers.


 But why should the GC have to worry about pointers in random data?  My 
 question is, is there a *need* for the GC to assume any data could be a 
 pointer, does any code actually *depend* on that behavior?  I really would 
 like to see an example of where it is necessary.


Well, we are not just talking about random data, but of data which is
excplicitly defined as "data of random type, including pointers".
It is a feature, not a bug; and not incidentally, but planned this way.


 IMO conservative would be the other way around.  Conservative would be to 
 not assume something is a pointer unless it is.  I would call the current 
 behavior ... overassuming, maybe neurotic, or paranoid even? :)


It's called conservative, because if it can't tell it will err on the side
of safety.


 coder: GC, there is only random data in that block


Then call it ubyte[] to void[].
If it's void[] you are saying "here be pointers, possibly".


 GC: NO!!! it could be a POINTER!!!  THEY'RE EVERYWHERE!!!


They are! Believe me, I've seen them! =)

regards, Frank
Oct 10 2007
parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"0ffh" wrote

 Steven Schveighoffer wrote:

 "0ffh" wrote
 But why should the GC have to worry about pointers in random data?  My 
 question is, is there a *need* for the GC to assume any data could be a 
 pointer, does any code actually *depend* on that behavior?  I really 
 would like to see an example of where it is necessary.


 Well, we are not just talking about random data, but of data which is
 excplicitly defined as "data of random type, including pointers".
 It is a feature, not a bug; and not incidentally, but planned this way.


OK, I understand it is planned this way.  I even understand the rationale 
behind it.  But this is more of a "functions as designed" feature than a 
real feature.  I'm sure the writer of the GC did not intend for this side 
effect to occur.

I think we are way off track here.  There is a problem with the garbage 
collector in that it can assume data that is not a pointer is a pointer, and 
therefore not collect the data pointed to when it should.  It may be that 
not scanning void[] is not the solution to the problem, but there is 
definitely a problem.

Maybe the solution is for data to have the type information instead of the 
pointer type containing the type information.  What I mean is, even though 
it is a void *, it points to some data.  If the type of that data is stored 
with the data, then you can tell if the pointed-to data has pointers in it, 
regardless of the fact that the type is void.

Maybe there is another solution.

All I know is that if it's going to leak memory for no good reason that I 
can see, then I don't want to use it in a production-quality product, 
because not only is it impossible to tell whether it will leak data (note 
that this problem is completely non-deterministic), but it is impossible to 
FIX the problem without significantly paranoid code.  And oh by the way I 
need to see all the source code to all libraries I use so that I don't 
accidentally use something that contains a void *.

-Steve
Oct 10 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Steven Schveighoffer wrote:

 "0ffh" wrote

 Steven Schveighoffer wrote:

 "0ffh" wrote
 But why should the GC have to worry about pointers in random data?  My 
 question is, is there a *need* for the GC to assume any data could be a 
 pointer, does any code actually *depend* on that behavior?  I really 
 would like to see an example of where it is necessary.


 Well, we are not just talking about random data, but of data which is
 excplicitly defined as "data of random type, including pointers".
 It is a feature, not a bug; and not incidentally, but planned this way.


 
 OK, I understand it is planned this way.  I even understand the rationale 
 behind it.  But this is more of a "functions as designed" feature than a 
 real feature.  I'm sure the writer of the GC did not intend for this side 
 effect to occur.
 
 I think we are way off track here.  There is a problem with the garbage 
 collector in that it can assume data that is not a pointer is a pointer, and 
 therefore not collect the data pointed to when it should.  It may be that 
 not scanning void[] is not the solution to the problem, but there is 
 definitely a problem.


Well a good start would be to fix phobos' AA implementation so that it 
doesn't generate so many false positives.  Tango improves on it some, 
but I wonder if Tango does ok on the test case here:
     http://d.puremagic.com/issues/show_bug.cgi?id=1561



 All I know is that if it's going to leak memory for no good reason that I 
 can see, then I don't want to use it in a production-quality product, 
 because not only is it impossible to tell whether it will leak data (note 
 that this problem is completely non-deterministic), but it is impossible to 
 FIX the problem without significantly paranoid code.  And oh by the way I 
 need to see all the source code to all libraries I use so that I don't 
 accidentally use something that contains a void *.


Better diagnostic tools would help.  If you could run a memory profile 
and find out that the GC is keeping memory block A allocated here 
because this thing in memory block B allocated here is referring to it, 
then it would be much easier to find and fix these spurious references.

Also fixing it so the core library constructs don't generate spurious 
references would be nice too.  I don't think anyone expects a core 
language feature like AAs to interact poorly with another core langauge 
feature, the GC.

But hey, on the bright side, things have come a long way in D.  It used 
to be that just creating large buffers of floats could bring a system to 
its knees. :-)

--bb
Oct 10 2007
parent reply Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
Bill Baxter wrote:


 Well a good start would be to fix phobos' AA implementation so that it
 doesn't generate so many false positives.  Tango improves on it some,
 but I wonder if Tango does ok on the test case here:
 http://d.puremagic.com/issues/show_bug.cgi?id=1561


I just modified the code you provided for tango and ran it: Tango's AAs seem
not to exhibit this problem at all. (check bug for details)

Christian
Oct 10 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Christian Kamm wrote:

 Bill Baxter wrote:
 

 Well a good start would be to fix phobos' AA implementation so that it
 doesn't generate so many false positives.  Tango improves on it some,
 but I wonder if Tango does ok on the test case here:
 http://d.puremagic.com/issues/show_bug.cgi?id=1561


 
 I just modified the code you provided for tango and ran it: Tango's AAs seem
 not to exhibit this problem at all. (check bug for details)
 
 Christian



Thanks for trying that out.  I don't understand why it would work on 
Tango, though. There must be something different happening from what I 
guessed originally, because keysize and valuesize should both be equal 
to (void*).sizeof on a 32 bit machine, and thus Tango shouldn't be 
setting the NO_SCAN flag.

Actually looking closer, it appears that the hash value used by DMD 
doesn't even look pointer-like.   Actually it's just an identity function:
     int x = 99;
     typeid(int).getHash(cast(void*)&x) // == 99

In the example we're just hashing values 0-999, so those shouldn't be 
mistaken as pointers.

Can anyone explain why Tango's AA's work right when Phobos's don't here?


--bb
Oct 10 2007
prev sibling parent reply BCS <ao pathlink.com> writes:
Reply to Steven,


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.
 
 -Steve
 


IIRC there is a proof that without some restriction (which are not possible 
under D) Either a GC will leak, or collect memory early.
Oct 10 2007
parent reply David Brown <dlang davidb.org> writes:
On Wed, Oct 10, 2007 at 03:21:56PM +0000, BCS wrote:

 Reply to Steven,


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.
 -Steve


 IIRC there is a proof that without some restriction (which are not possible 
 under D) Either a GC will leak, or collect memory early.


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.

This is might actually keep me from using D for one application I'm
writing.  I've managed to carefully place 'delete' statements for the
large, obvious leaks, but the other auto-gc features of D are mostly what
make it a better language for me to use.  As is, my program gradually leaks
more and more memory over time.  It would be cumbersome to have to track
each '~' or array resize and properly free up the old data.

There is a lot about tradeoffs, though.  .NET has an exact GC (or at least
could), but makes interfacing with C code much more cumbersome.

Dave
Oct 10 2007
next sibling parent reply BCS <BCS pathlink.com> writes:
David Brown wrote:

 On Wed, Oct 10, 2007 at 03:21:56PM +0000, BCS wrote:
 

 Reply to Steven,


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.
 -Steve



 IIRC there is a proof that without some restriction (which are not 
 possible under D) Either a GC will leak, or collect memory early.


 
 
 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.
 


The restriction, IIRC, basically limit you to a language like LISP. 
Inline ASM, aliasing of data, unions, direct pointer manipulation, 
passing references to unknown code, etc. prevent you from getting an 
exact GC. (note: I'm working from memory from several different 
conversations over a period of years so don't take this as gospel)


 It might not meet some performance or other memory requirements some users
 have, but it should be possible to make the GC exact.
 
 This is might actually keep me from using D for one application I'm
 writing.  I've managed to carefully place 'delete' statements for the
 large, obvious leaks, but the other auto-gc features of D are mostly what
 make it a better language for me to use.  As is, my program gradually leaks
 more and more memory over time.  It would be cumbersome to have to track
 each '~' or array resize and properly free up the old data.
 
 There is a lot about tradeoffs, though.  .NET has an exact GC (or at least
 could), but makes interfacing with C code much more cumbersome.
 
 Dave
Oct 10 2007
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
BCS wrote:

 David Brown wrote:

 On Wed, Oct 10, 2007 at 03:21:56PM +0000, BCS wrote:


 Reply to Steven,


 to me, gc-that-leaks-memory-by-assuming-random-data-is-a-pointer ==
 broken gc.  Speed/mem usage is secondary.
 -Steve



 IIRC there is a proof that without some restriction (which are not 
 possible under D) Either a GC will leak, or collect memory early.



 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.


 
 The restriction, IIRC, basically limit you to a language like LISP. 
 Inline ASM, aliasing of data, unions, direct pointer manipulation, 
 passing references to unknown code, etc. prevent you from getting an 
 exact GC. (note: I'm working from memory from several different 
 conversations over a period of years so don't take this as gospel)


Storing type information of all allocations (of heap, stack _and_ static 
variety) would mean that only unions (mixing ptr/refs & other types) and 
void[]s (and static void[N]s) screw up exactness[2]. I think a 
mostly-exact[1] GC could be created, as long as it doesn't move or 
deallocate memory blocks that appear to be referenced by memory whose 
type is indeterminate.
IIRC the spec already states that dereferencing pointers obtained by 
casting from non-pointer data is disallowed, so the other things you 
mention could mostly be "fixed" by disallowing the uses of such 
functionality which break that rule[3].
Other cases can be handled by keeping the current conservative behavior 
(but this should only be done if there's no other reasonable way).

I think that such a GC, even though not exact, would still be a huge 
improvement. I think the cases where conservative behavior is required 
should be pretty easy to keep to a minimum.


[1] Or perhaps a better term is "slightly conservative"?
[2] Probably register contents too; it'll probably be horribly 
space-inefficient to include a mapping of every program location to the 
set of registers containing pointers. (Remember, when a GC pauses all 
other threads so it can collect those other threads could be at any 
instruction in the program)
[3] Or require that objects manipulated in such ways be pinned first.
Oct 10 2007
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
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.

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.


Sean
Oct 10 2007
next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
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).
Oct 10 2007
parent reply "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Thu, 11 Oct 2007 03:22:24 +0300, Frits van Bommel
<fvbommel remwovexcapss.nl> wrote:


 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.


Maybe I'm missing some pieces of the picture, but this mean that every time a
value is pushed onto the stack, or the meaning of a value changes, that some
bit somewhere is set/reset, possibly involving synchronization? That would be
quite a performance penalty (up to 100% in stack-heavy programs), no?

-- 
Best regards,
 Vladimir                          mailto:thecybershadow gmail.com
Oct 11 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 03:22:24 +0300, Frits van Bommel
<fvbommel remwovexcapss.nl> wrote:
 

 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.


 
 Maybe I'm missing some pieces of the picture, but this mean that every time a
value is pushed onto the stack, or the meaning of a value changes, that some
bit somewhere is set/reset, possibly involving synchronization? That would be
quite a performance penalty (up to 100% in stack-heavy programs), no?


First of all, the size and layout of a stack frame are usually pretty 
constant throughout the execution of a function. DMD and IIRC GDC as 
well just subtract a constant from the stack pointer at the beginning of 
a function to allocate all local variables[0]. Only function calls can 
sometimes change the layout (if their parameters are pushed instead of 
MOVed into place). The latter will be even less of an issue on 
architectures (such as amd64) where several parameters are passed in 
registers.
If we allow typeless "gaps" in the stack (such as frames for non-D 
functions and perhaps function parameters that aren't included in the 
stack frame descriptions of the calling functions) those will 
unfortunately also need to be treated conservatively.

On architectures I'm aware of (mostly x86 & amd64) the address of the 
current stack frame is held in a register where it can be easily found 
by the GC, and the current instruction pointer can be used to perform 
the lookup in the table I described. This does mean that things like 
GCCs -fomit-frame-pointer shouldn't be used (which it isn't by default), 
but other than that it should work with all existing code without 
modification. If there are architectures[1] where the address of the 
current stack frame can't be defined in a way that remains constant 
throughout the execution of a function[2] some other solution may have 
to be found there.


[0] Of course, if we model this as "one description per function" there 
may be some false positives if the GC pauses the thread before all local 
variables are initialized, but this should only happen for a single 
function per thread per GC run.
[1] Including x86/amd64 gcc with -fomit-frame-pointer
[2] Or at least throughout large sections of functions
Oct 11 2007
parent reply "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel
<fvbommel remwovexcapss.nl> wrote:


 First of all, the size and layout of a stack frame are usually pretty
 constant throughout the execution of a function. DMD and IIRC GDC as
 well just subtract a constant from the stack pointer at the beginning of
 a function to allocate all local variables[0]. Only function calls can
 sometimes change the layout (if their parameters are pushed instead of
 MOVed into place). The latter will be even less of an issue on
 architectures (such as amd64) where several parameters are passed in
 registers.
 If we allow typeless "gaps" in the stack (such as frames for non-D
 functions and perhaps function parameters that aren't included in the
 stack frame descriptions of the calling functions) those will
 unfortunately also need to be treated conservatively.

 On architectures I'm aware of (mostly x86 & amd64) the address of the
 current stack frame is held in a register where it can be easily found
 by the GC, and the current instruction pointer can be used to perform
 the lookup in the table I described. This does mean that things like
 GCCs -fomit-frame-pointer shouldn't be used (which it isn't by default),
 but other than that it should work with all existing code without
 modification. If there are architectures[1] where the address of the
 current stack frame can't be defined in a way that remains constant
 throughout the execution of a function[2] some other solution may have
 to be found there.


 [0] Of course, if we model this as "one description per function" there
 may be some false positives if the GC pauses the thread before all local
 variables are initialized, but this should only happen for a single
 function per thread per GC run.
 [1] Including x86/amd64 gcc with -fomit-frame-pointer
 [2] Or at least throughout large sections of functions


Actually, while thinking about it, I got a better idea. 
The compiler knows the exact layout of the stack frame at any point of the
function's execution.
Thus, the compiler could build tables of stack layout bits for various segments
of the function (the boundaries of such a segment would be branches and calls).
Then, during a GC pass, the GC would look at the instruction pointer of the
thread to retrieve the current stack layout for that thread/stack frame.
This way, there isn't any cost during execution - just during collection.

Downsides:
1) needs extra information that would increase binary size (most likely less
than generating code that would save stack description at runtime, though)
2) may involve complex changes to the compiler
3) will make GC scanning slower (it would have to do lookups for every stack
frame in every thread)
4) does not apply to non-D code using D memory (assembly code, statically or
dynamically linked non-D libraries, etc.) - these would have to be
conservative, unless we force the user to pass only "non-managed" memory to
non-D code
4b) if the external code doesn't use stack frames, I think it's impossible to
find any stack frames at all without heuristics

The question is, however: is conservative scanning of the stack that bad? IMO,
it's much less problematic just to tell the user to store large amounts of
pseudo-random/pointer-like data in the heap or in static arrays (data segment).

-- 
Best regards,
 Vladimir                          mailto:thecybershadow gmail.com
Oct 11 2007
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel
<fvbommel remwovexcapss.nl> wrote:
 
 The question is, however: is conservative scanning of the stack that bad? IMO,
it's much less problematic just to tell the user to store large amounts of
pseudo-random/pointer-like data in the heap or in static arrays (data segment).
 


My thinking exactly.  Seems like figuring out how to get classes and 
structs with pointers to not scan as all pointers is where the bigger 
payoff lies.  Stacks don't usually contain much pointer-like random data 
I wouldn't think.

--bb
Oct 11 2007
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Bill Baxter wrote:

 Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel 
 <fvbommel remwovexcapss.nl> wrote:




[apparently snipped by Bill]

 The question is, however: is conservative scanning of the stack that 
 bad? IMO, it's much less problematic just to tell the user to store 
 large amounts of pseudo-random/pointer-like data in the heap or in 
 static arrays (data segment).


 
 My thinking exactly.  Seems like figuring out how to get classes and 
 structs with pointers to not scan as all pointers is where the bigger 
 payoff lies.  Stacks don't usually contain much pointer-like random data 
 I wouldn't think.


You say structs should be scanned, but stacks shouldn't. In my 
experience, structs are quite often stored on the stack...

(Unless you meant heap/statically-allocated structs instead of structs 
in general)
Oct 11 2007
next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Frits van Bommel wrote:

 Bill Baxter wrote:

 Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel 
 <fvbommel remwovexcapss.nl> wrote:




 [apparently snipped by Bill]

 The question is, however: is conservative scanning of the stack that 
 bad? IMO, it's much less problematic just to tell the user to store 
 large amounts of pseudo-random/pointer-like data in the heap or in 
 static arrays (data segment).


 My thinking exactly.  Seems like figuring out how to get classes and 
 structs with pointers to not scan as all pointers is where the bigger 
 payoff lies.  Stacks don't usually contain much pointer-like random 
 data I wouldn't think.




For got to mention: I do agree that the heap should be considered a 
priority. I just think that after that, the stack is the next logical 
target[1].
Not having pointer information for the stack may significantly impede a 
moving collector.


[1] Though static data is probably simpler to implement since it's, 
well, static.
Oct 11 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Frits van Bommel wrote:

 Frits van Bommel wrote:

 Bill Baxter wrote:

 Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel 
 <fvbommel remwovexcapss.nl> wrote:




 [apparently snipped by Bill]

 The question is, however: is conservative scanning of the stack that 
 bad? IMO, it's much less problematic just to tell the user to store 
 large amounts of pseudo-random/pointer-like data in the heap or in 
 static arrays (data segment).


 My thinking exactly.  Seems like figuring out how to get classes and 
 structs with pointers to not scan as all pointers is where the bigger 
 payoff lies.  Stacks don't usually contain much pointer-like random 
 data I wouldn't think.




 
 For got to mention: I do agree that the heap should be considered a 
 priority. I just think that after that, the stack is the next logical 
 target[1].


Agreed.  There's certainly nothing wrong with trying to make the stack a 
safe place for random data.  But it's smaller than the heap, and 
generally has short-lived data, among other things.  So it's not as big 
a threat.

--bb
Oct 11 2007
prev sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Frits van Bommel wrote:

 Bill Baxter wrote:

 Vladimir Panteleev wrote:

 On Thu, 11 Oct 2007 14:44:04 +0300, Frits van Bommel 
 <fvbommel remwovexcapss.nl> wrote:




 [apparently snipped by Bill]

 The question is, however: is conservative scanning of the stack that 
 bad? IMO, it's much less problematic just to tell the user to store 
 large amounts of pseudo-random/pointer-like data in the heap or in 
 static arrays (data segment).


 My thinking exactly.  Seems like figuring out how to get classes and 
 structs with pointers to not scan as all pointers is where the bigger 
 payoff lies.  Stacks don't usually contain much pointer-like random 
 data I wouldn't think.


 
 You say structs should be scanned, but stacks shouldn't. In my 
 experience, structs are quite often stored on the stack...
 
 (Unless you meant heap/statically-allocated structs instead of structs 
 in general)


Yes, but there just aren't generally that many of them, and they don't 
usually hang around that long.  If you thought they were going to hang 
around a long time you'd have allocated em on the heap.  Thus they're 
not so likely to have so many spurious pointers that you end up with 
memory exhaustion.  Also the workaround is simple, just heap allocate 
any big trouble makers.

And yes, I meant classes and structs on the heap not the stack (and that 
includes structs that are members of a class, which is a pretty common 
case for me.)


--bb
Oct 11 2007
prev sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Vladimir Panteleev wrote:

 Actually, while thinking about it, I got a better idea. 
 The compiler knows the exact layout of the stack frame at any point of the
function's execution.
 Thus, the compiler could build tables of stack layout bits for various
segments of the function (the boundaries of such a segment would be branches
and calls). Then, during a GC pass, the GC would look at the instruction
pointer of the thread to retrieve the current stack layout for that
thread/stack frame.
 This way, there isn't any cost during execution - just during collection.


Ehm, you just described the approach I've been advocating all along...
Oct 11 2007
parent "Vladimir Panteleev" <thecybershadow gmail.com> writes:
On Thu, 11 Oct 2007 16:47:27 +0300, Frits van Bommel
<fvbommel remwovexcapss.nl> wrote:


 Ehm, you just described the approach I've been advocating all along...


Oops, for some reason I understood that you were going for accounting the stack
information at runtime... >_<
Serves me right for not actually reading what I'm replying to.

-- 
Best regards,
 Vladimir                          mailto:thecybershadow gmail.com
Oct 11 2007
prev sibling next sibling parent BCS <BCS pathlink.com> writes:
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 was trying to think of a case where you could have untyped data space 
with hard to track pointers. one case came to mind:

file formats. One way to read binary files is to define the format in 
such a way that a whole file can be read into memory and then have "file 
pointers" patched up as "memory pointers". The block that gets read is 
of unknown types. Slight variations on this result in having lost of 
small blocks of memory with data in them where the only way to known the 
type is to walk into it from who only known where. To GC that correctly 
you would need to walk the data tree correctly, and you can bet there 
will be some unions of pointers in there.


 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.
 


you could even have the stack precisely scanable by treating each stack 
frame as a object (push a function pointer on for every stack frame, 
this function picks out the pointer of the current stack frame) But that 
is just wrong.


 
 Sean
Oct 10 2007
prev sibling parent BLS <nanali nospam-wanadoo.fr> writes:
Sean Kelly schrieb:

 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.
 
 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.
 
 
 Sean


Hi Sean,
Even if slightly off topic I guess you will find it interesting
It is about a /third/ way ...
One reference only, (ORO) memory management)

Third way means : Not a mark-and-sweep, not a reference-counting GC
http://newlisp.org/MemoryManagement.html

Bjoern
Oct 11 2007
prev sibling next sibling parent reply 0ffh <spam frankhirsch.net> writes:
More comments on what

Steven Schveighoffer wrote:

 1. Is this just the way all garbage collectors are?  Is there not a way to 
 solve this problem?


No, only "conservative" gcs. There are also "exact" gc, but they have one
big drawback: No void* type at all is possible!
So either you want them, then you must use a conservative gc, or you don't
then you can have an exact gc.
D wants void*, so there is just no way round.


 2. Does Tango have this problem?  I know the GC's are different, and I use 
 tango, so maybe I could just say, too bad for phobos users and be on my way 


Tango is D too, so it must have the same "problem".


 3. If it is solvable, is anyone working on this?  If not, they should be. 
 Add this to the list of things that need to be fixed before D has widespread 
 adoption.  Memory leaks == bad bad bad.


It is not technically correct to call prudently retained memory blocks
a "memory leak". Those are distinct concepts, in my book at least.

Regards, Frank
Oct 10 2007
next sibling parent reply David Brown <dlang davidb.org> writes:
On Wed, Oct 10, 2007 at 05:29:01PM +0200, 0ffh wrote:


 No, only "conservative" gcs. There are also "exact" gc, but they have one
 big drawback: No void* type at all is possible!
 So either you want them, then you must use a conservative gc, or you don't
 then you can have an exact gc.
 D wants void*, so there is just no way round.


You can have limited void*, if you retain the types in the blocks that are
allocated.  What you can't do is use casts to view things of one type as a
different type.


 It is not technically correct to call prudently retained memory blocks
 a "memory leak". Those are distinct concepts, in my book at least.


It depends on how much gets prudently retained.  My experience so far is
that long-running programs continue to retain more and more memory.  I
would certainly call this a leak.

Dave
Oct 10 2007
parent reply 0ffh <spam frankhirsch.net> writes:
David Brown wrote:

 On Wed, Oct 10, 2007 at 05:29:01PM +0200, 0ffh wrote:

 No, only "conservative" gcs. There are also "exact" gc, but they have one
 big drawback: No void* type at all is possible!
 So either you want them, then you must use a conservative gc, or you 
 don't then you can have an exact gc.
 D wants void*, so there is just no way round.


 You can have limited void*, if you retain the types in the blocks that are
 allocated.  What you can't do is use casts to view things of one type as a
 different type.


If you always have to retain the types, what would be the use of void*s?
The point about them is that a void* may point to anything, pointers
included, which is what makes them painful for the gc.
Btw unions of pointer- and non-pointer types cause the same problem,
so it's not even all about void* (probably most, though).


 It is not technically correct to call prudently retained memory blocks
 a "memory leak". Those are distinct concepts, in my book at least.


 It depends on how much gets prudently retained.  My experience so far is
 that long-running programs continue to retain more and more memory.  I
 would certainly call this a leak.


IIRC it could be that the current GC doesn't use all of the available
information for collecting. It might be worthwhile to fix this, but
it's not trivial.

Regards, Frank
Oct 10 2007
parent reply David Brown <dlang davidb.org> writes:
On Wed, Oct 10, 2007 at 05:47:12PM +0200, 0ffh wrote:


 You can have limited void*, if you retain the types in the blocks that are
 allocated.  What you can't do is use casts to view things of one type as a
 different type.


 If you always have to retain the types, what would be the use of void*s?
 The point about them is that a void* may point to anything, pointers
 included, which is what makes them painful for the gc.
 Btw unions of pointer- and non-pointer types cause the same problem,
 so it's not even all about void* (probably most, though).


If the type is retained in the managed GC-allocated blocks, the GC can
determine if a void* points to a GC-allocated block or not (it already
decides this).  It can then look at the header to see if the block contains
pointers.

In fact, it already does this.  It's just that the determination of whether
the block contains pointers is a binary flag covering the whole block.
Approaches I've seen are to reorder GC-managed blocks so that the pointers
were always at the beginning, and have in the header a count of how many
pointers are in the blocks.

The other important part is when you walk the stack (and static data) for
pointers, you need to be able to tell what is and isn't a pointer.  This
requires the compiler to sufficiently annotate it's stack frames.  The D
spec indicates that Walter at least thought about this, whether the current
compiler does this or not.

David
Oct 10 2007
parent reply "nick.b" <nick.barbalich gmail.com> writes:
David Brown wrote:

 On Wed, Oct 10, 2007 at 05:47:12PM +0200, 0ffh wrote:
 

 You can have limited void*, if you retain the types in the blocks 
 that are
 allocated.  What you can't do is use casts to view things of one type 
 as a
 different type.


 If you always have to retain the types, what would be the use of void*s?
 The point about them is that a void* may point to anything, pointers
 included, which is what makes them painful for the gc.
 Btw unions of pointer- and non-pointer types cause the same problem,
 so it's not even all about void* (probably most, though).


 
 If the type is retained in the managed GC-allocated blocks, the GC can
 determine if a void* points to a GC-allocated block or not (it already
 decides this).  It can then look at the header to see if the block contains
 pointers.
 
 In fact, it already does this.  It's just that the determination of whether
 the block contains pointers is a binary flag covering the whole block.
 Approaches I've seen are to reorder GC-managed blocks so that the pointers
 were always at the beginning, and have in the header a count of how many
 pointers are in the blocks.
 
 The other important part is when you walk the stack (and static data) for
 pointers, you need to be able to tell what is and isn't a pointer.  This
 requires the compiler to sufficiently annotate it's stack frames.  The D
 spec indicates that Walter at least thought about this, whether the current
 compiler does this or not.
 
 David


There have been a lot of excellent posts on this issue, and suggestions 
on how this issue could be fixed/corrected.  I have one question:  Has 
anyone posted this as a bug ?

Nick
Oct 12 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
nick.b wrote:

 David Brown wrote:

 On Wed, Oct 10, 2007 at 05:47:12PM +0200, 0ffh wrote:


 You can have limited void*, if you retain the types in the blocks 
 that are
 allocated.  What you can't do is use casts to view things of one 
 type as a
 different type.


 If you always have to retain the types, what would be the use of void*s?
 The point about them is that a void* may point to anything, pointers
 included, which is what makes them painful for the gc.
 Btw unions of pointer- and non-pointer types cause the same problem,
 so it's not even all about void* (probably most, though).


 If the type is retained in the managed GC-allocated blocks, the GC can
 determine if a void* points to a GC-allocated block or not (it already
 decides this).  It can then look at the header to see if the block 
 contains
 pointers.

 In fact, it already does this.  It's just that the determination of 
 whether
 the block contains pointers is a binary flag covering the whole block.
 Approaches I've seen are to reorder GC-managed blocks so that the 
 pointers
 were always at the beginning, and have in the header a count of how many
 pointers are in the blocks.

 The other important part is when you walk the stack (and static data) for
 pointers, you need to be able to tell what is and isn't a pointer.  This
 requires the compiler to sufficiently annotate it's stack frames.  The D
 spec indicates that Walter at least thought about this, whether the 
 current
 compiler does this or not.

 David


 
 There have been a lot of excellent posts on this issue, and suggestions 
 on how this issue could be fixed/corrected.  I have one question:  Has 
 anyone posted this as a bug ?


I posted a bug about AA's causing memory exhaustion (with a test case). 
  If you're talking about a bug where false pointers on the stack cause 
memory exhaustion, I don't think anyone has actually run across such a 
case in practice.

--bb
Oct 12 2007
next sibling parent reply "nick.b" <nick.barbalich gmail.com> writes:
Bill Baxter wrote:

 nick.b wrote:

 There have been a lot of excellent posts on this issue, and 
 suggestions on how this issue could be fixed/corrected.  I have one 
 question:  Has anyone posted this as a bug ?


 
 I posted a bug about AA's causing memory exhaustion (with a test case). 
  If you're talking about a bug where false pointers on the stack cause 
 memory exhaustion, I don't think anyone has actually run across such a 
 case in practice.
 
 --bb


Bill - the original post on this issue was by David Brown on 9/10/2007 
at 5:04am.  I have copied part of his original post below:

"I've been developing an application on x86_64 (dgcc) without any problems.
Yesterday, I tried building it on x86 to discover that it has a memory 
leak on that platform.  The leak is rather significant, and the program 
quickly exhausts memory and is killed.

Any suggestions from the list on how to debug/fix this? "

I tracked all the posts on this issue.
The following day David posts some more details. Here is a snip of his 
post:

"Hmm, the keys of my hash were all stored in an AA.  At least the AA 
only  has the first 4 bytes of the hash rather than the whole thing."


So, thanks for posting the bug with the test case. I had thought there 
was an outstanding issue, but this does not seem to be the case.

Nick
Oct 13 2007
parent David Brown <dlang davidb.org> writes:
On Sat, Oct 13, 2007 at 09:07:12PM +1300, nick.b wrote:


 "Hmm, the keys of my hash were all stored in an AA.  At least the AA only  
 has the first 4 bytes of the hash rather than the whole thing."

 So, thanks for posting the bug with the test case. I had thought there was 
 an outstanding issue, but this does not seem to be the case.


It still leaks, just more slowly now.  By making the key a reference (a
class) instead of a struct, I store much less data directly in the AA for
the GC to follow, it still follows the random pointers of the hash field.

Or at least this is my suspicion.  There is a lot of other stuff going on,
so it certainly isn't a good minimal example of reproducing the problem.

Perhaps taking the test case and using random numbers instead of
incrementing integers will show the problem.

Dave
Oct 13 2007
prev sibling parent reply David Brown <dlang davidb.org> writes:
On Sat, Oct 13, 2007 at 02:07:28PM +0900, Bill Baxter wrote:


 I posted a bug about AA's causing memory exhaustion (with a test case).  If 
 you're talking about a bug where false pointers on the stack cause memory 
 exhaustion, I don't think anyone has actually run across such a case in 
 practice.


The reason is that as long as the set of false pointers is bounded, the
amount of unreclaimed memory is also unbounded.

The bad leaks happen when the allocated blocks themselves contain false
pointers, and continuous allocation generates more false pointers.

A good reference about this is:
    <http://www.hpl.hp.com/techreports/2001/HPL-2001-251.html>

It explains that as long as the the number of misidentified pointers is
itself is bounded, then it will at worst result in a constant size of
unreclaimed memory.

In other words, it would probably be good to come up with a way to
distinguish pointers in classes from other data, since this easily results
in unbounded leaks, but false pointers on the stack don't cause unbounded
leaks.

The paper also explains how (provided you get rid of the unbounded leaks),
the constant unreclaimed data will be better than a continual leak caused
by a manually managed program with a gradual leak.

David
Oct 12 2007
parent "nick.b" <nick.barbalich gmail.com> writes:
David Brown wrote:

 On Sat, Oct 13, 2007 at 02:07:28PM +0900, Bill Baxter wrote:
 

 I posted a bug about AA's causing memory exhaustion (with a test 
 case).  If you're talking about a bug where false pointers on the 
 stack cause memory exhaustion, I don't think anyone has actually run 
 across such a case in practice.


 
 The reason is that as long as the set of false pointers is bounded, the
 amount of unreclaimed memory is also unbounded.
 
 The bad leaks happen when the allocated blocks themselves contain false
 pointers, and continuous allocation generates more false pointers.
 
 A good reference about this is:
    <http://www.hpl.hp.com/techreports/2001/HPL-2001-251.html>
 



David - thanks for the reference to the 9 page PDF. It looks like an 
excellent document.

Nick
Oct 13 2007
prev sibling next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
0ffh wrote:

 
 More comments on what
 
 Steven Schveighoffer wrote:

 1. Is this just the way all garbage collectors are?  Is there not a 
 way to solve this problem?


 
 No, only "conservative" gcs. There are also "exact" gc, but they have one
 big drawback: No void* type at all is possible!
 So either you want them, then you must use a conservative gc, or you don't
 then you can have an exact gc.
 D wants void*, so there is just no way round.


I think the main outstanding issues with D's GC are not so much about 
existence of void* but rather inability to differentiate between pointer 
and non-pointer data within a class.  Just having void* isn't what's 
causing the headaches here from what I can tell.  It's that a hash value 
or floating point value stored in the same aggregate as a pointer is 
also treated as a pointer.  That seems fixable through the use of extra 
time, space, or both.


 3. If it is solvable, is anyone working on this?  If not, they should 
 be. Add this to the list of things that need to be fixed before D has 
 widespread adoption.  Memory leaks == bad bad bad.


 
 It is not technically correct to call prudently retained memory blocks
 a "memory leak". Those are distinct concepts, in my book at least.


Agreed.  But I don't know what the proper term is.  And apparently you 
don't either or you would have given us something better than "prudently 
retained memory blocks".   Ghost references maybe?

--bb
Oct 10 2007
prev sibling parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
0ffh wrote:

 
 More comments on what
 
 Steven Schveighoffer wrote:

 1. Is this just the way all garbage collectors are?  Is there not a 
 way to solve this problem?


 
 No, only "conservative" gcs. There are also "exact" gc, but they have one
 big drawback: No void* type at all is possible!


Why would a void* not be possible with an exact gc?
I can see how allocating void[]s could be problematic, but if that were 
disallowed the gc could store exact pointer info for each allocation and 
use that when collecting. (You'd still be able to allocate an array and 
have it implicitly convert to void[], just not allocate it as one 
directly because allocations would need an actual type)

The only issues left then would be static data and the stack.


 So either you want them, then you must use a conservative gc, or you don't
 then you can have an exact gc.
 D wants void*, so there is just no way round.
 

 2. Does Tango have this problem?  I know the GC's are different, and I 
 use tango, so maybe I could just say, too bad for phobos users and be 
 on my way 


 
 Tango is D too, so it must have the same "problem".


I think with proper compiler support, current D can get pretty close to 
supporting an exact gc. Being conservative for arrays allocated as 
void[] might not be such a big issue as data that's definitely 
non-pointer (such as hash values) which is currently searched for 
pointers anyway.


 3. If it is solvable, is anyone working on this?  If not, they should 
 be. Add this to the list of things that need to be fixed before D has 
 widespread adoption.  Memory leaks == bad bad bad.


 
 It is not technically correct to call prudently retained memory blocks
 a "memory leak". Those are distinct concepts, in my book at least.


If you can't reach an allocated memory block through some chain of valid 
pointers or references (starting on the stack or in static data), it 
should be deallocated. If it isn't, it's a memory leak. Unfortunately, 
conservative collectors suffer from them.
Oct 10 2007
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Steven Schveighoffer" wrote

 Something has come to light in a few posts that has described memory leak 
 problems because the garbage collector finds ghost pointers in hash data. 
 My understanding of the problem is that the garbage collector marks data 
 allocations as having pointers or not having pointers, and then searches 
 through all the data to see if there are any valid pointers, finding data 
 that looks like a pointer, but is not.


Here's another reason why this is no good.  A copying garbage collector (as 
described on the D garbage collection page 
http://www.digitalmars.com/d/garbage.html) would not be possible.  Imagine 
using a hash value that happens to look like a valid pointer.  The copying 
garbage collector comes along and tries to compact the data, and in doing so 
moves the data that is "pointed to" by this hash code.  It would then change 
the hash code to point to the new data!

-Steve
Oct 10 2007