Proposal: Use aliasing constructor of shared_ptr for BodyNodePtr

[mxgrey]

I recently stumbled across the marvelously useful "aliasing constructor" of std::shared_ptr. The aliasing constructor allows a std::shared_ptr to refer to an arbitrary object while its reference count is tied to another arbitrary object. We can apply this to BodyNodePtr by making it a std::shared_ptr which refers to a BodyNode object while its reference count is tied to the Skeleton object that owns the BodyNode.

This has the added benefit of allowing us to cast BodyNodePtr to a FramePtr and generally enabling us to unify the memory management of all shared DART objects under the umbrella of std::shared_ptr. So for example we could have a std::vector<FramePtr> which contains a set of both BodyNodePtr and SimpleFramePtr objects, as well as other Frame types. This memory management scheme would also work for JointPtr.

The one disadvantage is we'll lose the ability to implicitly cast a raw BodyNode* to a smart BodyNodePtr, because std::shared_ptr (very reasonably) does not allow implicit conversion from raw pointers. This could have a significant impact on some users and some DART-dependent frameworks, so I'd especially like to hear from Aikido developers (paging @jslee02 @gilwoolee, and @mkoval @psigen if you're still involved or interested in this topic). I think this disadvantage would be well worth the benefits of throwing away a custom smart pointer class and having unified, consistent memory management.

[jslee02]

This sounds really good to me as I generally prefer using STL. I think the custom smart pointer was introduced because we believed there was no solution with std:shared_ptr. Now it seems we have a solution (I haven't looked at "aliasing constructor" yet though. :smiling_imp: ).

The disadvantage seems fair enough and to make sense.

Also, I guess this change would go into the next major release as it would be API breaking changes.

[mxgrey]

Yeah, I wish I had known about the aliasing constructor back then. It would have saved me a significant amount of time and effort. Although I don't mind the fact that I got some practice creating a custom smart pointer type. Of course it shouldn't come as any surprise that the people on the ISO standards committee already anticipated our needs ahead of time.

It should definitely target dart-7, due to the slight API breakages. Should that be master branch, or should I create another branch (e.g. develop) for that?

[jslee02]

I think master should be the most bleeding edge branch; so let's (1) create release-6.3 for adding new features that don't break API compatibility and are expected to be released soon, and (2) bump up the master branch version to 7.0.0.

[psigen]

I am strongly in favor of this change.

When @mkoval and I were originally analyzing the resource management problem for Skeleton we were really hoping that something like this would exist, but somehow didn't find or think of a way to use the aliasing constructor. I think we might have been too focused on trying to override the internal ref count mechanism instead of thinking to alias against another object.

The downside of not being able to implictly cast a raw pointer to a shared pointer seems relatively minor. In most situations I can think of, the raw pointer would be derived from a shared pointer anyway, and functions that require a shared pointer are making an ownership demand that it is useful to make explicit in these situations.

[mxgrey]

Yeah, it doesn't help that information on the aliasing constructor tends to be one small footnote in a massive list of different ways of constructing a std::shared_ptr (see (8) here). I actually found out about it when I got curious about how the STL implements std::dynamic_pointer_cast, and I stumbled across the aliasing constructor, which resulted in a breathtaking epiphany.

I think the aliasing constructor deserves to have a big billboard at the top of any documentation about std::shared_ptr. Then again, if knowledge of it is too widespread, it could lead to abuse, since there are some risks to using it carelessly.

[mkoval]

I was aware of this when we were implementing the custom pointer types. The aliasing constructor not sufficient for our needs because there is no mechanism to transfer ownership of an object that between owners. This is necessary to implement any of DART's moveTo functions.

This is a fundamental limitation of the way shared_ptr is implemented. Every shared_ptr contains a pointer to a control block that contains its refcount. When a shared_ptr is copied, the new shared_ptr uses the same control block as the instance it was copied from and increments its refcount. When a shared_ptr is destructed, it decrements the refcount and (if zero) deletes the control block.

Aliasing is implemented by sharing one control block between multiple shared_ptrs. Changing the owner of a shared_ptr would require iterating over all of the shared_ptrs that reference the same control block and updating them to refer to a new control block. This is not possible using the standard library's implementation of shared_ptr because the control block does not maintain a list of the shared_ptrs are owned by it. It would also be difficult to make this operation atomic.

In summary: we either have to use a custom shared_ptr or remove the moveTo functions.

[mxgrey]

Oh, thanks for that reminder! I have to admit, I forgot about that part of the motivation for the custom pointer type.

That being said, I'm pretty sure we can still get it to work using the aliasing constructor. Here would be my proposal:

Node and Joint classes will hold a std::weak_ptr<std::shared_ptr<Skeleton>> which (for now) we can call mSkeletonPtrProxy (I'm very open to naming suggestions). When a BodyNodePtr is requested, the BodyNode will first check mSkeletonPtrProxy to see if it already exists.

1. If it does not exist, it will create a std::shared_ptr<std::shared_ptr<Skeleton>> where the inner std::shared_ptr<Skeleton> holds a reference to the BodyNode's current Skeleton. Then it will link mSkeletonPtrProxy to it and create a std::shared_ptr<BodyNode> using the aliasing constructor to tie it to the memory block of the std::shared_ptr<std::shared_ptr<Skeleton>> which is weakly held by mSkeletonPtrProxy. It then returns the std::shared_ptr<BodyNode>.

2. If it does already exist, it locks mSkeletonPtrProxy and then returns a std::shared_ptr<BodyNode> which is tied to the same memory block as mSkeletonPtrProxy using the aliasing constructor.

When we use the moveTo function (or any variant where the Skeleton ownership gets transferred), we check the mSkeletonPtrProxy field of each Node and Joint that has been moved. If the field is active, then we change the std::shared_ptr<Skeleton> that each mSkeletonPtrProxy is referring to.

Because naturally if one layer of std::shared_ptr doesn't solve all your memory management problems, two layers certainly will 😉

[mxgrey]

While I believe I'll be able to make this work for the NodePtr and BodyNodePtr classes, it does not seem possible for the JointPtr or DegreeOfFreedomPtr classes, because I forgot that those classes do a redirection in their arrow operator and dereference operator where they query their child BodyNode for the latest parent Joint or DegreeOfFreedom (which allows us to change joint types without invalidating JointPtr or DegreeOfFreedomPtr instances). This fundamentally cannot be accomplished with an aliased std::shared_ptr, except maybe with a complete template specialization of the std::shared_ptr class (with a complete specialization performed for every Joint type), which seems like a very bad idea to me.

The only way I can fathom using std::shared_ptr for joints and degrees of freedom is if we could do an aliasing construction where we pass the std::shared_ptr a lambda that returns a pointer and have it query the lambda for a pointer during each dereference operation. However, I don't see anything like that in the documentation on std::shared_ptr. Also, it wouldn't make sense for std::shared_ptr to offer such a thing, because it would eliminate the class's ability to sort and hash if the pointer value that it holds onto can change arbitrarily. We get around this in our existing code by having JointPtr sort and hash based on the underlying BodyNodePtr value. DegreeOfFreedomPtr does likewise, but then uses its index-in-the-joint value to break ties. It looks like we don't offer hash functions for either of them, though, which is kind of unfortunate.

For now, I think my plan will be to change the memory management for BodyNode and Node while leaving Joint and DegreeOfFreedom as-is. In the future, it might be interesting to consider using some kind of PIMPL design pattern to keep Joint references valid while the joint type changes.

At the very least, we'll have a unified memory management system for all the Frame classes, where every type of Frame can be managed as a std::shared_ptr<Frame>.

[mxgrey]

After implementing this, the unit tests have revealed one major flaw: std::weak_ptr does not have the expected/desired behavior. Since we return an aliased std::shared_ptr which is not tied to a memory block that directly manages the BodyNode, if we construct a std::weak_ptr from that std::shared_ptr, it is possible for the std::weak_ptr to expire, even while the BodyNode that it's intended to refer to is still alive. Here's some example code to demonstrate this:

// ... initialize skeleton as a dart::dynamics::SkeletonPtr ...
std::weak_ptr<BodyNode> weakPtr = skeleton->getRootBodyNode(0)->as_shared_ptr();
weakPtr.expired() // This returns true when it should return false

The object returned by as_shared_ptr() must be given to and held by a std::shared_ptr<BodyNode> in order for its memory block to remain valid. As long as a std::shared_ptr<BodyNode> holds it, the BodyNode and Skeleton that it's attached to will remain alive and valid, even if the BodyNode is moved between Skeletons. However, if we tie a std::weak_ptr<BodyNode> to it, then the lifecycle of that std::weak_ptr<BodyNode> will be tied to the memory block of the std::shared_ptr<BodyNode>, irrespective of the lifecycles of the actual BodyNode or Skeleton that are being referred to by the std::shared_ptr<BodyNode>. When the std::shared_ptr<BodyNode> instance gets destroyed, the std::weak_ptr<BodyNode> will consider itself expired, even if its BodyNode should still be available.

I still feel like it should be possible to make this work the way we want, but admittedly I'm a bit stumped at the moment over how to resolve this. I can easily think of ways to make the std::shared_ptrs work without the std::weak_ptrs or ways to make the std::weak_ptrs work without the std::shared_ptrs. I've even thought of a scheme that would provide both a BodyNode::as_shared_ptr() and a BodyNode::as_weak_ptr() function, which would allow us to have both types of pointers behave correctly individually, but it wouldn't allow those pointer types to interact with each other correctly, which I think is unacceptable.

If anyone has thoughts or ideas to try out, I'd love to hear them. Otherwise, I'm going to keep flexing my creativity to see if I can come up with something that allows both types of pointers to have the expected behavior.

[mxgrey]

I have a partial solution, although there's one big issue with it, which I'll mention at the end.

We can create a meta-object which, for now, I'll refer to as Environment (note that this is NOT a singleton). When you call the static function Skeleton::create() it will automatically create a std::shared_ptr<Environment> object, and the Environment instance will store a std::unique_ptr to the Skeleton. The Skeleton::create() function will then return an aliased std::shared_ptr<Skeleton> whose memory block is actually tied to the std::shared_ptr<Environment>. The Skeleton will retain a std::weak_ptr<Environment> inside itself.

When you call BodyNode::as_shared_ptr() you will receive a std::shared_ptr<BodyNode> which is aliased from the Skeleton's std::shared_ptr<Environment>.

Now suppose you create a second Skeleton which is tied to a second Environment instance, and you decide to move a BodyNode from the first Skeleton to the second. We will move ownership of all the Skeletons from one Environment to the other. Whichever Environment does not have ownership will store the other Environment in itself as a std::shared_ptr.

Now here's the big drawback: This makes it impossible to partially delete a Skeleton or to delete a Skeleton which is stored in the same Environment as another Skeleton that you don't want to delete. You can move BodyNodes around freely, but each time two Environments get merged, they're merged permanently, and nothing in any of them can be deleted unless everything in all of them is deleted. This could also produce some unexpected/undesirable memory inflation if someone performs frequent edits on a Skeleton where they "discard" BodyNodes and then create new ones, because those "discarded" BodyNodes would never actually be deleted until the whole Skeleton is deleted.

So there are two questions: (1) Would this be worth it, if no other solution is available? (2) Is there a better solution that I haven't thought of yet?

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 7 days if no further activity occurs. Thank you for your contributions.