Friday, May 28, 2010

Tracking Object Ownership in C++

Ever since the beginning when people program in C/C++, the need to track object ownership is recognized, but there has been a lot of confusions. We need ownership tracking in order to know who is responsible for freeing an object. This is essential for preventing memory leaks, since C++ does not typically use garbage collection (though it can use something like Boehm GC). Ownership tracking is also essential for preventing double-free, which can corrupt the memory allocator's internal data structure.

Ownership tracking does not sufficiently prevent all memory related error. For example, another part of the program could retain an aliased const reference to an object and use it after the true owner frees it. After the memory occupied by the object is returned to the allocator, it could be subsequently used for other purpose, which could be corrupted when someone modifies the aliased original object that no longer exists.

We will need to use the concept of linearity if we also want to prevent aliasing, but a lot of seasoned C++ programmers don't understand this. It is evident, for example, from their disdain about std::auto_ptr<>: when an STL algorithm such as sort() is broken when you use auto_ptr, they blame auto_ptr for the culprit. However, I would argue that the culprit is sort(), which creates an alias for an item in the container and abandons it without proof that it is safe to do so (perhaps because by default, C++ treats everything as plain old data, which means copying and assignment has no side-effect). If an algorithm observes object linearity, then it will work with auto_ptr<>. There has been significant research in the programming language ATS which strictly enforces linearity in its type system, and there is a lot of code implementing common algorithms that satisfy linearity.

While it is great if you can use a new language with built-in linearity checking, what if you're stuck with C++ (e.g. I miss template meta-programming and curiously recurring template pattern)?

The real problem I have with auto_ptr<> is that it automatically frees the object when the auto_ptr<> object is destructed. This means that non-linear code can run for a while, erroneously freeing objects until everything mysteriously disappears, and you will be puzzled by what is going on. Distinguishing move semantic and copy semantic is a start: it alleviates the need of the auto_ptr_ref hack (otherwise auto_ptr<> cannot be returned from functions due to the non-const copying constructor). But move semantics doesn't enforce linearity; items can still mysteriously disappear after they're moved out of the container but not moved back in.

C++ type system does not have the power to enforce linearity during compile time, but the next best thing to do is to make programs crash early when non-linearity is detected. I've been using a home-brew linear_ptr<> class which the only difference from auto_ptr<> is that, whenever there is a delete p, I remove it and replace it with assert(p == NULL). Regardless of move or copy semantics, a linear pointer only tracks the ownership but never frees an object. I've been using this ubiquitously in an implementation of a memory allocator with great success.

In using linear_ptr<>, I came to realize that a lot of times, a function or method doesn't intend to take ownership of the object passed in as an argument, nor does it alias the object pointer, but we want to have call-by-reference argument semantics. In these cases, I use the idiom const linear_ptr<T>& which means that the pointer itself should not be modified (still points to the same object, not taking ownership) but the object itself is non-const, so it could be mutated.

It turns out that in a regular C++ program, you don't need to use linear pointer to express the intention that a function does not intend to take ownership of an object. Just use a reference! The key idea is that delete takes a pointer, not a reference. Since a reference cannot be deleted, it signifies the fact that the caller does not pass ownership of the object to the function. Furthermore, it signifies that the reference cannot be NULL, so the object has to exist prior to the call. The caller loans the object to the function; the function borrows the object from the caller. Of course, the function should still refrain from converting the reference to a pointer or making an alias of the reference, but it is much easier for a programmer to self-discipline in a local context of a function.

The role of references in C++ is often under-appreciated. For example, Google C++ Style Guide imposes a rule on references that prevents you from writing a function that wishes to mutate an object but will not claim ownership.

However, it is important to note that, unlike pointers, C++ references cannot be reassigned. Assignment on a reference will be applied on the object being referenced to, not the reference itself. This means that if you want to repeatedly borrow objects in a recursively defined data structure (e.g. singly linked list, binary search tree), you will have to write recursive functions rather than doing it in a loop.

In the case where you really want to write a loop that repeatedly borrows objects from a data structure, you can use a loan pointer, where the object pointer is cast to a pointer of a loan class of that object. A loan class is a mixin that merely disables the constructor and destructor by making them private.
template<class superTp>
class loan : public superTp {
  // Disallow constructor and destructor.
It most certainly should disallow copy constructor as well, but this is left for an exercise to the reader. When we want to signify the intention to retain ownership, we will make a loan pointer using the following function:
template<class superTp>
loan<superTp> *make_loan(superTp *objp) {
  return static_cast<loan<superTp>*>(objp);
A similar function can be written for linear_ptr<> as well, to convert from a const linear_ptr<T>& to loan<T> *.

A loan pointer can be reassigned to reference a different object, but the usual caution about aliasing applies. A function should not retain the alias beyond the scope of the function. I rarely use the loan<T> * idiom myself because C++ reference works most of the times for me to write a function with the intent not to claim object ownership from the owner.

In conclusion, yes, there is a difference between pointer and reference in C++, and the difference is often under-appreciated. You may use pointer argument to signal the intent of the function to take ownership from the caller; but when you use a reference argument, the caller keeps ownership, and the function merely borrows the object for use in the function scope. This takes care of ownership dispute in function call. However, outside of a function call, auto_ptr<> is not enough to enforce linearity in code. Since C++ type system does not statically enforce linearity, the next best alternative is to use linear_ptr<> that detects non-linearity and crashes the program in run-time the earliest possible. These facilities can be used together to help programmers write linear code that is free of memory leak and memory corruption problems due to double-free and free-after-use.

No comments: