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