We found this problem in a druntime GC benchmark. https://github.com/D-Programming-Language/druntime/pull/818#issuecomment-46001787 It seems like the compiler inlines some functions and therefor a false pointer to a stale node remains in a register or on the stack. Furthermore every previously allocated node is referenced from that pointer. I could resolve the issue by nulling _left, _right and _parent at the end of Node.remove (https://github.com/D-Programming-Language/phobos/blob/bb4f8e876b6278ad3b18d3ebb2f6597757b782f2/std/container.d#L5245), but I don't understand enough of the implementation to be sure that this doesn't break anything.
Can we just null the end node's pointers on the destructor? this should dereference all the nodes. BTW, I think there is a previous bug on that same behavior: https://issues.dlang.org/show_bug.cgi?id=5650
RedBlackTree does not guarantee that remove operations won't invalidate iterators, this guarantee is only present for inserts. So I think this is acceptable. As you've stated, we must use _left, _right and _parent to null out the pointers. (In reply to Steven Schveighoffer from comment #1) > Can we just null the end node's pointers on the destructor? this should > dereference all the nodes. This can be done in addition to Martin's solution, just call clear(). I'm not sure this will have a big impact: The RedBlackTree's nodes form a cycle, a false pointer into any node will still cause the entire tree to be retained. And since the begin & end pointers are always on the heap, as the number of nodes in the tree increases the likely hood of the begin & end being the ones causing the leak diminishes. If this is a pervasive issue, perhaps a function which recursively nulls the pointers is in order (and optionally manually deallocates.) Nulling would invalidate iterators, manually deallocating invalidates references.
OK, I misunderstood. I thought the issue was that the red black tree itself was being pointed at, and that was causing the leak. We certainly can null pointers as the nodes are deallocated. But the tree does not go through and destroy all the nodes if you just forget the tree (and I would argue it shouldn't). So this may solve the specific use case, but not the general one.
(In reply to Steven Schveighoffer from comment #3) > We certainly can null pointers as the nodes are deallocated. But the tree > does not go through and destroy all the nodes if you just forget the tree > (and I would argue it shouldn't). Clear simply resets the begin & end pointers. > So this may solve the specific use case, but not the general one. The general case is only solved by precise GC. We can only help specific use cases: - Nulling on element removal. - Manually specified complete destruction. etc.
Commits pushed to master at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/43a1e276fe00c70239f713757f4161303f114c1d fix Issue 12915 - RedBlackTree leaks memory https://github.com/D-Programming-Language/phobos/commit/3ebaa088eecc5322ab7bf8a80124c4ef9f4be223 Merge pull request #2625 from MartinNowak/fix12915 fix Issue 12915 - RedBlackTree leaks memory
Commits pushed to 2.067 at https://github.com/D-Programming-Language/phobos https://github.com/D-Programming-Language/phobos/commit/43a1e276fe00c70239f713757f4161303f114c1d fix Issue 12915 - RedBlackTree leaks memory https://github.com/D-Programming-Language/phobos/commit/3ebaa088eecc5322ab7bf8a80124c4ef9f4be223 Merge pull request #2625 from MartinNowak/fix12915