[boost] Cyclic smart pointers (holy grail: the uber-pointer)

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-28 10:47:44

I've received a few suggestions for methods to achieve non-leaking
cyclic smart pointers (henceforth called "uber pointers").  I've looked 
into some of them.  Following is a report on what I've found.

Here is my context: I want to write a library L consisting of a set of 
interconnected classes, {C}, in the pimpl idiom: each class C in {C} has 
only one member variable -- a pointer ("impl_pointer") to its class 
implementation I:C.  (impl_pointer is "smart", but not "uber".)  Default 
C++ copy semantics are used when copying {C} objects (meaning 
impl_pointer is copied, but not *impl_pointer).  This should ensure that 
instances of {C} classes are "first class objects" -- no restrictions on 
what I can do with them (i.e. I can assign from one to another, pass 
them as params, return them from functions, store them in STL 
collections, put them in object heirarchies, etc).  This freedom should 
ideally apply both internally (within library L code) and most 
importantly, externally (in the code of users of library L).  Crucially, 
{C} is recursive -- circular references are normal, in particular 
externally (which we can't control).  I want to ensure the destruction 
of any {C} objects which are not ultimately reachable externally. 
Periodically invoking a garbage-collector is fine.

-------------------------------------------------

boost/libs/smart_ptr/src/sp_collector.cpp:

There is no sample program to compile/run, so I have to guess somewhat 
at how to use this one.

The basic idea is to intercept all memory allocations -- p = new X; -- 
saving the info with "map[p] = sizeof(X);".  To find the 
interconnections between objects, you do this:

     for (map_type::iterator it = map.begin(); it != map.end(); ++it) {
         char *p = it->first;
         unsigned size = it->second;
         for (char *v = p; v + 4 <= p + size; v += 4) {
             char *q = *(reinterpret_cast<char **>(v));
             if (map.count(q)) {
                 // connection detected from object p to object q
             }
         }
     }

That is, for each known object p, you scan its allocated memory, 
examining each 4-byte chunk, q.  If map[q] exists, then you assume q 
refers to an object, and therefore, that a connection exists from p to 
q.  Given this map, you can detect stranded pools of objects (using 
dynamic programming, presumably, although I don't see any in 
sp_collector.cpp).  You then run this algorithm periodically to detect & 
destroy stale objects.

You might object that you'll sometimes mis-identify q as an object, when 
in fact it is just some random data.  True, although tricks can be (and 
are, in sp_collector.cpp) used to minimize this to a vanishingly small 
likelihood (i.e. by marking legit pointers with a signature byte 
sequence).  The consequence of mis-identification is that you may fail 
to destroy some unused objects.  If this leads to nothing worse than 
some leaked memory, then it's not a real problem -- it will be a 
vanishingly small amount of memory.

Another problem is, how do you track external references to your 
objects?  Indeed, that's the whole goal -- to find which objects are 
ultimately referenced from the "outside world" (and to destroy the 
rest).  I don't see how sp_collector.cpp does this.  Sample code would 
be nice -- then I could quickly watch in the debugger and see.  Perhaps 
it depends on the fact that only boost::shared_ptr's are supported, and 
these store their info in allocated memory.  I don't know - just 
speculating.

One big problem with this approach is that you end up having to scan all 
of your memory.  This could (and for me, would) be an outrageous 
proposition, as only a tiny portion of memory relates to my object set. 
  Most of it will be raw data (e.g. images, etc).

------------------------------------------------------------------------

My own semi-uber pointer implementation (concept):

sp_collector.cpp isn't itself suitable, but it does give me some ideas. 
  We could store the range [pointer,size] for C implementations (i.e. 
for I:C objects) in impl_map (inserting/deleting during I:C 'structors), 
and pointers to C objects in obj_set (inserting/deleting during C 
'structors).  We can associate each object pointed to in obj_set, with 
an implementation in impl_map, by examining the memory ranges in 
impl_map.  If an object isn't associated with any implementation, then 
it is "external" -- otherwise it is "internal".  Given the resulting 
interconnection map, we apply dynamic programming to detect/delete dead 
object pools.

This would work, as long as internal {C} objects are always directly 
represented in other {C} objects.  But what if you put {C} objects in a 
standard container, inside an I:C (i.e. {C} implementation) object? 
Then you're hosed.

Still, that's something.  It would be necessary to implement your own 
containers for {C} objects, for use within I:C objects -- these 
containers would themselves be {C} objects.  A very simple container you 
get "for free" is an array, which might be enough for some problem 
spaces.  Note that externally, you could use regular STL containers, or 
anything you want.

This is a half-way-OK solution.  It means that the writer of library L, 
which makes use of the uber-pointer library, must take great care, and 
perhaps go to alot of trouble writing custom containers.  But the user 
of library L has great freedom -- worry-free use!

Further, it would be possible to supply containers with the uber-pointer 
library: ultimately, a whole set of containers, parallel to the standard 
containers, could be supplied.  Indeed, with a bit of macro and/or 
template magic, the same code could be used for the STL and uber-pointer 
containers.

Advantages of uber-pointer vs. sp_collector.cpp:

     * uber-pointer would make you pay only for what you used -- vs.
       scanning the whole heap.

     * uber-pointer would be quite portable.  It might even be strictly
       portable.

     * uber-pointer would be strictly correct -- not subject to spurrious
       failure to find dead objects.

     * uber-pointer pointers would be smaller -- no special identifying
       signature need be stored with the pointer.

Disadvantages of uber-pointer vs. sp_collector.cpp:

     * care must be taken, internally (i.e. within L), to reference
       {C} objects only from within other {C} objects.  Crucially, you
       can't put {C} objects in STL containers, internally.  (Users of
       your library have no restrictions -- they can put {C} objects in
       STL containers).

---
Note: any {C} objects on the stack will be considered to be external 
(hence, not garbage-collected), even if they are on the stack in 
"internal" (i.e. library) code.  That is exactly as it should be.  After 
all, we can't go deleting objects which are being actively referenced!
----------------------------------------------------------------------
cyclic_ptr.hpp in Boost contributions
I studied this a while, but must confess I couldn't wrap my head around 
it.  I did find one interesting thing: the way cyclic_ptr "traces" 
pointer references is by doing the following:
     T *p = reinterpret_cast<T*>(raw memory pointer);
     *p = *p;
that is, by copying an object onto itself.  This causes copy 
constructors to be called on all contained objects.  The copy 
constructors are the "hook" by which any embedded cyclic_ptr's are detected.
One thing that means is that if your object isn't copyable, you're in 
trouble.  That seems to rule out the use of cyclic_ptr for my problem 
space.  After all, fundamental to my framework is that the I:C objects 
(implementation classes) aren't copyable.  Indeed, I generally declare 
them with boost::noncopyable, to ensure this.  They often contain things 
like boost::mutex and boost::condition.
Yes, I could make my I:C objects copyable, by writing copy constructors 
which do the right thing (i.e. don't copy the non-copyable parts). 
However, I then have to make sure I copy everything.  I think this is a 
horrible design -- very prone to bug creation: whenever I add a new 
member variable, I have to remember to add it to the copy constructor. 
What if I forget?  There's no compiler warning, and non run-time 
warning.  I get a nasty bug -- a silent killer.
Because of this, I decided not to pursue cyclic_ptr.  Perhaps someone 
how understand cyclic_ptr could set me straight, if I've got it wrong.
Also, I'd love to understand how it works -- perhaps I could use some of 
its ideas...
-----------------------------------------------------------------------
NoPtr lib -- noptrlib.sourceforge.net
 From what I can tell, this library is not at all suitable for what I 
want.  It appears to be a set of traditional smart pointers -- with 
components which are somewhere between auto_ptr and shared_ptr.  I saw 
no mention of detecting dead cyclic object pools.
-----------------------------------------------------------------------
Well, that's it, then.  I'm fishing for some feedback from people more 
knowledgeable than myself...
     - Chuck