[Gc] Example for premature reclaim caused by compiler optimization

Boehm, Hans hans.boehm at hp.com
Thu Sep 8 12:13:58 PDT 2005


This is actually not an example of an object being prematurely
reclaimed;  it is an example of an object being "prematurely" finalized.
The problem is not that a reachable object is collected.  A properly
unreachable object is being finalized.  It's just that the object became
unreachable before the programmer thought it would.  And the finalizer
(in this case the object's destructor) might proceed to destroy things
that are actually still live.

This is probably the most fundamental difficulty with finalizers, and
the reason they should be used very rarely and cautiously.  If you are
accessing members of a finalizable object that might be invalidated by
the finalizer, after the last reference to the object itself, you need
to somehow insert a final reference to the object itself.

There is a long discussion of these issues (in a Java context) in the
slides for my JavaOne talk.  You can find a variant of that (with HP
instead of Sun templates, and with a typo removed) at
http://www.hpl.hp.com/personal/Hans_Boehm/misc_slides/java_finalizers.pd
f .

This is also addressed, though again not very well, in Mike Spertus and
my proposal to add GC support to C++.  (See
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1833.pdf .
Mike and I are still discussing if we can do better, but it seems hard.)

I believe there are fundamentally two ways to address this problem:

1) Make it work as expected, by keeping (or appearing to keep) all
pointer variables around until the end of their scope.  That includes
keeping the target of the this pointer reachable while any method on the
object is executing.  I think this has to essentially affect most
pointers, since you rarely know whether the dynamic type of an object is
actually a finalizable subclass.  Hence it's potentially expensive.
(Measurements would be great.  As far as I know, there aren't any.)

2) Push the problem back onto the programmer, who generally knows when
this might be an issue, but will have a tough time debugging mistakes.

Note that C++ destructors have essentially the same problem.  After some
early hiccups in some implementations, the language went with option(1),
i.e. objects with destructors stay around until the end of their scope,
and are then destroyed in a mostly-well-defined order.  Given the fact
that destructors are pervasive, this was clearly the right choice.  And
you can tell statically whether something needs to have a destructor
invoked.

I believe that all common garbage-collected languages, Java in
particular, effectively went with (2), since finalizers are either rare,
or not supported at all.  (Languages that have weak references or the
like instead of finalizers usually have the same issues.)  In some
cases, it's not clear to me whether this decision was fully understood
when it was made.

The decision was reconsidered in the context of the Java during the
memory model discussions (JSR133).  And the conclusion to stick with (2)
was not unanimous, at least among the onlookers.  I argued for sticking
with (2), mostly because:

a) Option (1) would have had a major compiler impact and unknown,
probably significant, performance impact.  This would have made it much
harder to get such a change adopted, and might have caused even more
serious problems to also not get addressed.

b) This is basically an experts-only feature anyway, which is, or should
be, very rarely used.  Given that there was a manual workaround, it
really wasn't clear that it was worth slowing down the rest of the
language implementation for it.  (Actually, before JSR133, there was no
real manual workaround in Java.  Hence the desire to get something
accepted.)

Another argument for (2), is that in retrospect (1) is probably only a
98% solution.  If the for-loop in your first example where run in a
separate thread, you'd still need the programmer to explicitly keep
setholder alive to prevent this failure, even if it was automatically
retained until the end of its scope.  The same issue applies if you keep
the iterator past the end of setholder's scope.  Fundamentally, the
programmer unavoidably has to think about finalizer timing, no matter
what.  Thus (2) involves code overhead, but perhaps not much mental
overhead.

(Gc_cleanup and finalizers in our collector also have another known
problem.  By default it runs destructors synchronously from the
allocator.  That's wrong.  There is no clean way to implement finalizers
without threads, and they should be run in a separate thread.  There are
hooks to do that in the collector, but I suspect most people don't
bother.  For details see my paper "Destructors, Finalizers, and
Synchronization", POPL 2003.  This argument also applies to calling
destructors directly from refcount collectors.)

Hans


> -----Original Message-----
> From: gc-bounces at napali.hpl.hp.com 
> [mailto:gc-bounces at napali.hpl.hp.com] On Behalf Of Martin Wartens
> Sent: Thursday, September 08, 2005 7:08 AM
> To: gc at napali.hpl.hp.com
> Subject: [Gc] Example for premature reclaim caused by 
> compiler optimization
> 
> 
> Hi,
> I have recently encountered an error with a premature reclaim 
> of an object, 
> which was caused by a compiler optimization. The pointer to 
> the newly created 
> object gets optimized away by the compiler so that it is not 
> held in any 
> register nor on the stack. When there is no other reference 
> to the object in 
> memory, the gc thinks the object is dead and removes it. This 
> may happen even 
> if there are still live pointers to other objects reachable 
> only by first 
> object.
> Given below is an example program to demonstrate the problem. 
> There are two 
> examples which are basically identical. The first example 
> creates a set and 
> tries to iterate over it. During the iteration the set is 
> collected away, which 
> makes the iterators point to garbage. The second example is a 
> stripped down 
> version of the first and uses a mockup list instead of a set. 
> For compiling the example program, use "g++ -O2 -I./include 
> -I./gc6.5/include -
> o mygctest mygctest.cpp   ./lib/libgc.a  -lpthread -ldl", 
> which was tested on 
> linux with gcc3.3, or VC7.1 with /O2 switch. 
> It is quite hard to find such a bug, since it only shows in 
> optimized code. 
> Trying to output the wrongly destroyed pointer can keep it 
> alive and make the 
> error go away. The first step to finding such a bug is to 
> clutter the code with 
> multiple forced collector calls: "GC_gcollect(); 
> GC_gcollect(); GC_gcollect(); 
> GC_gcollect();". This hopefully makes the bug appear at a 
> deterministic point 
> early in the program.
> Removing the bug is not so hard: Either create the offending 
> object on the 
> stack (not with new), or call delete for the pointer to that 
> object. With both 
> variants, the pointer to the object seems to survive 
> somewhere in memory so 
> that the gc can find it.
> 
> ==============================================================
> ===========
> #include <iostream>
> #include <set>
> using namespace std;
> 
> #include "gc_cpp.h"
> #include "gc_allocator.h"
> 
> 
> /****************first example********************/
> struct SetHolder : public gc_cleanup
> {
>         typedef std::set<unsigned, std::less<unsigned>,
>                          gc_allocator<unsigned> > SetT;
>         SetT set;
> 
>         SetHolder()
>         {
>                 //create set and insert some data
>                 set.insert(147);
>         }
>         ~SetHolder()
>         {
>                 cout<<"Destroy SetHolder"<<endl;
>                 //destroy set
>         }
> };
> 
> void testgcset(){ 
>         SetHolder* setholder = new SetHolder();
>         SetHolder::SetT::const_iterator lineIt = 
> setholder->set.begin();
>         SetHolder::SetT::const_iterator lineEnd = 
> setholder->set.end();
> 
>         //iterate over set contents
>         for(; lineIt != lineEnd; lineIt++){
>                 GC_gcollect(); GC_gcollect();
>         }
>         cout<<"end of loop"<<endl;
> }
> 
> 
> /****************second example********************/
> //single linked list node
> struct Node: public gc
> {
>         //pointer to next node in list
>         Node* next_node;
>         Node* getNext()
>         {
>                 if(next_node==0)
>                    cout<<"Iterator increment: invalid ptr"<<endl;
>                 return next_node;
>         }
> };
> 
> //mockup of a single linked list
> struct FakeList : public gc_cleanup
> {
>         //first node in list
>         Node* first_node;
>         FakeList()
>         {
>                 //create first node and another node,
>                 //let first point to another_node
>                 first_node = new Node();
>                 Node* another_node = new Node();
>                 first_node->next_node = another_node;
>         }
>         //get first node in list
>         Node* begin(){ return first_node; }
>         //get last node in list
>         Node* end(){ return first_node->next_node; }
>         ~FakeList()
>         {
>                 first_node->next_node = 0;
>                 first_node = 0;
>                 cout<<"fake list destroyed"<<endl;
>         }
> };
> 
> void testgclist(){ 
>         //create new list. this pointer will be optimized away
>         FakeList* fakelist = new FakeList();
> 
>         Node* iter = fakelist->begin();
>         Node* lastptr = fakelist->end();
> 
>         //iterate over list contents
>         while(iter!=lastptr)
>         {
>                 //this will trigger collection of fakelist,
>                 //while we are still iterating over it.
>                 GC_gcollect(); GC_gcollect();
>                 //this fails, iter is dead
>                 iter=iter->getNext();
>         }
>         cout<<"end of loop, everything fine"<<endl;
> }       
> 
> int main()
> {
>     testgcset();
>     testgclist();    
>     GC_gcollect();
> }
> 
> 
> _______________________________________________
> Gc mailing list
> Gc at linux.hpl.hp.com 
> http://www.hpl.hp.com/hosted/linux/mail-archives/gc/
> 



More information about the Gc mailing list