Library thread-safety from a user's point of view, with wording

1. Introduction
2. An informal, type-based approach
3. More formality by analogizing objects to memory locations
4. Design decisions
5. Existing practice
6. Proposed wording
7. Acknowledgements
8. Revision history
9. References

Introduction

With the introduction of multi-threading into the C++ standard, the contract between standard library users and implementers needs to explicitly state the conditions under which concurrent operations on standard library components have defined behavior. This must be at a higher level than the memory model itself so that users don't need to know exactly which memory operations a given invocation performs.

An informal, type-based approach

There are three levels at which a type can informally be "thread-safe".

• Separate instances of the type can be constructed and accessed concurrently by different threads. This prohibits unsynchronized access to static objects in the type's methods. It probably requires copy-on-write implementations to synchronize their shared internals. I believe this is what N2410 calls the "basic" thread-safety guarantee. This has little or no impact on performance and does actually deliver the promised safety, so it should be required of implementations.
• Concurrent calls to const methods (and possibly others specially noted as non-modifying) are safe, but non-const method calls must be related to all other calls by the happens-before relation. This makes caching more expensive and rules out some amortized data structures like splay trees. This level of thread-safety is not widely recognized or named in the literature, but it's important because it matches the guarantees provided by the memory model for primitive types. I'd suggest calling it the "primitive", "scalar", or "const" thread-safety guarantee. Because it describes the guarantees currently made by STL implementers, it should also be required of implementations.
• Concurrent calls to all methods are safe. I believe N2410 calls this the "strong" thread-safety guarantee. This is the guarantee provided for the atomic<T> family, but it can have a severe negative impact on performance. Furthermore, real safety often requires atomicity across several member function calls, so providing per-function-call locking would create an illusion of safety that did in fact not exist. For these reasons, implementations should not be required to provide this level of thread-safety for most of the classes in the standard library.

In the rest of this paper, I will assume types make the "const" guarantee by default, I will call types that make only the basic guarantee "thread-isolated", and I'll call types that make the strong guarantee "concurrency-tolerant". (These names are Lawrence Crowl's and my invention and don't reflect any sort of consensus. Better adjectives would be welcome.)

A function can only be thread-safe or not. If it uses a non-const static object without synchronization, it is quite likely not to be thread-safe. Note that reentrancy is related to but not identical to thread-safety. A function may use a thread-specific object to get thread-safety without thereby getting reentrancy.

Arguments complicate this story. For instance, it's not safe to call

    void square_in_place(int* i) {
        *i *= *i;
    }

concurrently on the same int, even though the function itself is thread-safe. Functions that take two non-const, non-concurrency-tolerant arguments (including *this for methods) are a recipe for deadlock, unless at most one of the troublesome arguments is shared between threads.

More formality by analogizing objects to memory locations

In order to deal with arguments in a uniform way and make a stab at a more formal definition, I'm going to steal a page from the memory model. Let's say that an object sits at a single notional memory location, which can be accessed and modified independent of the actual memory locations that comprise the object. The notional location of a scalar object is identical to its memory location. Some objects, such as containers, may have both the shallow location representing the whole object, and deep locations representing user-visible subobjects, frequently of user-defined types, but these objects need to be called out specifically. In general, passing a const object to a function (including to a method as *this) should be an access to the object's memory location, and passing a non-const object should be a modification. Then [1.10p3]'s definition of conflict carries over (renamed to "object conflict"), as does [1.10p11]'s definition of a data race (now called an "object race"). It is the user's responsibility to avoid object races, and it is the library implementer's responsibility to ensure that a lack of object races implies a lack of data races.

Thread-isolated objects can express their restrictions concisely by saying that all method calls are modifications instead of only the non-const ones. Concurrency-tolerant objects could say that all methods are simple accesses, but that violates my intuition about modifications, so I've introduced the idea of a concurrency-tolerant method that can modify an object without conflicting with other concurrency-tolerant methods. These closely resemble atomic operations, but may not appear to happen all at once.

Objects, even if not all methods are concurrency-tolerant, also have the opportunity to provide edges in the happens-before relation. In particular, a type may specify that certain methods perform a release operation on the object, and that others perform an acquire operation. The effect is exactly the same as if the operations were performed on a real memory location, even if the object implements them differently. Users should be able to safely treat objects identically to real memory locations.

Design decisions

N2410 requires most standard library functions to be reentrant. This is unrelated to thread-safety, although it seems like a good idea. (I'd be surprised if sort()'s comparator was not allowed to call sort()!) I've included it here too, but replaced the undefined term "reentrant" with recursive and thread-safe.

Existing practice

As far as is known, the proposed wording reflects existing practice in current implementations of the standard library.

Proposed Wording

Insert new definitions in 17.1:

access [defns.access]

An object is accessed by any modification, any direct access to a member variable, any member function call on the object, or any call to a standard library function taking the object as a parameter.

concurrency-tolerant [defns.concurrency.tolerant]

A term applied to functions that relaxes certain restrictions on concurrent calls to other concurrency-tolerant functions ([library.concurrency]). [Note: Constructors and destructors cannot be concurrency-tolerant, although they can be synchronization operations as in the case of unique_lock and thread. --end note]

modification [defns.modification]

An object is modified by its constructor and destructor, by directly modifying a member variable, and, unless otherwise specified, by calling non-const member functions on the object or passing the object as a non-const parameter to a standard library function. [Note: This definition implies that an object need not be modified when a memory location inside it is modified (for example, when an object contains mutable members). This helps insulate users from implementation details, and, combined with the requirement in [res.on.thread.safety], restricts the implementation of such objects. --end note]

Insert a new section between 17.3 and 17.4, titled "Concurrent use of the library [library.concurrency]":

Two expression evaluations have an object conflict if one of them modifies an object and the other one accesses the same object. The execution of a program contains an object race if it contains two object-conflicting actions in different threads, at least one of which is not concurrency-tolerant, and neither happens before the other. Any such object race results in undefined behavior. Unless otherwise specified, operations on objects in the standard library are not concurrency-tolerant and are not synchronization operations.

Replace section 17.4.4.5 with one titled "Recursion [recursion]":

Functions in the C++ Standard Library that can call user-defined functions must be able to be called recursively from them.

Insert a new section between 17.4.4.5 and 17.4.4.6, titled "Thread safety [res.on.thread.safety]":

The implementation must ensure that, when uses of the standard library are free of object races, calls to standard library functions do not introduce any data races, except where otherwise specified.

To 3.7.3 Dynamic storage duration [basic.stc.dynamic], add:

Any allocation and/or deallocation functions defined in a C++ program, including the default versions in the library, shall not introduce data races (1.10 [intro.multithread]) as a result of concurrent calls from different threads. Calls that allocate or deallocate a particular unit of storage shall occur in a single total order, and each such deallocation call happens before the next allocation (if any) in this order. [Note: [basic.stc.dynamic.deallocation] implies that the behavior is undefined if the call to allocate a particular unit of storage does not happen before the call that deallocates it. --end note]

Change 19.3 Error numbers [errno] paragraph 1 as indicated:

The header <cerrno> is described in (Table 29). Its contents are the same as the POSIX header <errno.h>, except that errno shall be defined as a macro that expands to a separate modifiable lvalue for each thread of execution. [Note: The intent is to remain in close alignment with the POSIX standard. --end note]

To 20.6.1 The default allocator [default.allocator], add:

All member functions of the default allocator are concurrency-tolerant ([library.concurrency]). Allocation and deallocation calls that allocate or return a particular unit of storage shall occur in a single total order, and each such deallocation call happens before the next allocation (if any) in this order. [Note: [basic.stc.dynamic.deallocation] implies that the behavior is undefined if the call to allocate a particular unit of storage does not happen before the call that deallocates it. --end note]

To 20.7 Date and Time [date.time], add:

The functions asctime, ctime, gmtime, and localtime may introduce a data race if called concurrently with each other ([res.on.thread.safety]).

To 21.5 Null-terminated sequence utilities [c.strings], add:

The functions strerror and strtok may introduce a data race if called concurrently with each other ([res.on.thread.safety]).

To 23.1 Container requirements [container.requirements], add a paragraph between paragraphs 11 and 12.

All of begin, end, rbegin, rend, front, back, at, find, lower_bound, upper_bound, and equal_range do not modify containers other than basic_string. operator[] does not modify sequences other than basic_string. [Note: operator[] does modify associative containers, even if it does not result in a change in the caller-visible state of the object. --end note] An iterator is modified when it is invalidated. An object is modified when a pointer or reference that refers to it is invalidated.

To 23.3.5 Class template bitset [template.bitset], add:

A bitset of any size may consist of just a single memory location, so accesses and modifications to any contained bits, including through references, conflict.

Change 26.7 C Library [c.math] paragraph 5 and 6 as indicated:

The rand function has the semantics specified in the C standard, except that the implementation may specify that particular library functions may call rand. The rand function may introduce a data race if called concurrently with itself ([res.on.thread.safety]). [Note: This does not imply that functions specified to call rand may introduce data races. --end note]

Add to Chapter 27 Input/output library [input.output] (somewhere):

When a standard iostream object str is synchronized with a standard stdio stream f [ios.members.static], all operations on str are concurrency-tolerant. Concurrent access to other objects in the iostreams library must be locked as usual. [Note: This is the minimum guarantee to match POSIX behavior on files. --end note]

Acknowledgements

This document builds upon wording in N2298 and N2410. Without encouragement from Lawrence Crowl, this paper would never have been written, and he and Matt Austern helped to flesh out the ideas and get the new wording right.

Revision history

N2519 - Initial version.

References

N2334, Concurrency memory model (revised again), Clark Nelson and Hans-J. Boehm

N2410, Thread-Safety in the Standard Library (Rev 1), Beman Dawes, Peter Dimov, and Herb Sutter

N2447, Multi-threading Library for Standard C++, Howard E. Hinnant, Jeff Garland, Alisdair Meredith, Chris Kohlhoff, Dietmar Kühl, Nathan Myers, PremAnand M Rao, and Nick Stoughton

flockfile() and friends, from the POSIX Threads Extension (1003.1c-1995).