Strong Exception-Safe Storage

Strong Exception-Safe Storage

By Anthony Williams

During discussions on the Boost mailing list [1] about the implementation of a variant type, the issue of exception safety came up — how could you provide any level of exception-safety guarantees for objects of a variant class, when you have no knowledge of the guarantees given by the objects that would be contained within? In particular, how could you provide even a basic exception-safety guarantee for operations like copy assignment, given that copy assignment for a variant class involves destroying the destination object and copy constructing a source object that may have a different type?

The standard technique for writing exception-safe assignment operators is to perform any operations that may throw exceptions first, "off to one side," so that the existing state is left unchanged if an exception occurs. When all the operations that might throw exceptions have been completed, the existing state is discarded, and the new state is swapped in using simple no-throw operations such as exchanging pointer values:

SomeClass& SomeClass::operator=(const SomeClass& other)
{
   SomeClass temp(other); 
        // create a new copy "off to one side"
   swap(temp); 
        // swap the data; this is a no-throw 
        // operation
   return *this; 
        // discard the old data with "temp"
}

If you were using dynamic storage for the variant type, you could easily follow the procedure just described — allocate a new chunk of memory, copy construct the source into the new chunk of memory, and exchange the pointers — so that the source becomes the contained object — then discard the original contained object and free its memory. This way, the state of the destination variant object remains unchanged until all the operations that might throw exceptions (memory allocation and copy construction) are complete. You thus provide not just a basic guarantee, but a strong exception-safety guarantee for the assignment. Indeed, this is precisely the technique used by boost::any.

However, one of the key design features of a particular new variant type is that there should be no dynamic memory allocation — the contained object should exist within the memory occupied by the variant object itself (as it would in a normal member variable), so you can't use this technique directly.

Similar Problems And Common Solutions

Games programmers have a similar problem when performing display updates. Rendering the screen is a complex, time-consuming operation, and users don't want to see a partially drawn screen; they're better off seeing the previous complete picture than a partial picture. A common solution is double buffering, which requires you to allocate space for two screens, one of which is shown to users and one of which is not. All updates are done to the invisible screen, and then, when the round of updates is complete, the screens are swapped so that the invisible buffer becomes visible and the previously visible buffer becomes invisible. This way, users only see complete screens.

You can use this idea to solve the aforementioned problem; if you allocate two buffers within the variant object, only one of which is live, you can construct the new value in the invisible buffer, switch the invisible buffer with the live buffer, then destroy the value in the old live buffer (which is now invisible). If the attempt to construct the new value fails, you can rollback without any changes to the visible state of the object, thus providing a strong exception-safety guarantee.

This technique can be used to provide a strong exception-safety guarantee for assignment and swap functions of any type, not just variant types. This is a good thing since the implementation of a variant type is a complex task unto itself (as Andrei Alexandrescu has shown [2][3][4]). Therefore, the code I provide here is for the StrongStorage class template, each object of which contains a single object of the template type parameter T. This class uses our technique to ensure that copy assignment and swap functions for objects of type StrongStorage<T> provide a strong exception-safety guarantee, even if T itself doesn't give a basic guarantee. The only requirement is that T can be copy constructed and has a no-throw destructor.

To provide buffers, you need a means of obtaining an array of char that can be stored as a member of the class, while being correctly aligned to store an object of type T. There is an example of such a class as part of the Boost Optional library [5] (boost::optional_detail::aligned_storage<T>), but the supplied code provides a basic implementation using a union of lots of POD types to try and ensure a worst-case alignment for the buffer.

The implementation of assignment (Listing 1) is straightforward. As you can see, Listing 1 closely matches the following pseudocode:

<ul>
<li>If the other object is empty, clear the live cache.

<li>Otherwise,

      - Construct a copy of the other object in the spare cache.

      - Clear the "live" cache.

      - Swap the cache indicator so the other cache is now "live."
</ul>

Swap (Listing 2), on the other hand, is more complicated. Listing 2 closely matches this pseudocode:

<ul>
<li>If the other object is not empty, construct a copy in the spare cache.

<li>If this object is not empty, construct a copy in the spare cache of the other object.

<li>If the second copy failed, destroy the result of the first copy (if any) and give up.

<li>Otherwise,

      - Destroy the originals.

      - Flip the two cache indicators.

      - Swap the "cache is empty" flags.
</ul>

The key is to perform all the operations that might throw an exception (such as copying objects) before modifying the visible state, ensuring that appropriate cleanup occurs if an exception is thrown.

Conclusion

So, if you need to provide either basic or strong exception-safety guarantees, and have no information on the types of your member variables, consider the double-buffer technique in cases where dynamic memory allocation is undesirable — it avoids dynamic memory at the expense of a larger memory footprint.

The code for this article is available at http://www.cuj.com/code/.

References

[1] Boost mailing list. http://www.boost.org/more/mailing_lists.htm#main, archives available online at http://aspn.activestate.com/ASPN/Mail/Archives/boost/.

[2] Andrei Alexandrescu. "Generic<Programming>: Discriminated Unions (I)." C/C++ User's Journal C++ Experts Forum, 20(4), April 2002. http://www.cuj.com/experts/2004/alexandr.htm.

[3] Andrei Alexandrescu. "Generic<Programming>: Discriminated Unions (II)." C/C++ User's Journal C++ Experts Forum, 20(6), June 2002. http://www.cuj.com/experts/2006/alexandr.htm.

[4] Andrei Alexandrescu. "Generic<Programming>: Discriminated Unions (III)." C/C++ User's Journal C++ Experts Forum, 20(8), August 2002. http://www.cuj.com/experts/2008/alexandr.htm.

[5] Boost Optional library. http://www.boost.org/libs/optional/doc/optional.html.

Endnote

The variant library that was under discussion has now been accepted into Boost and uses a technique similar to that discussed here to provide the strong exception-safety guarantee. The library is part of the Boost CVS source tree, but is not yet part of any release. The documentation can be viewed online at http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/*checkout*/boost/boost/libs/variant/doc/index.html.