[LC++]Object Oriented, compiler supported MT race condition checking for STL containers.

Carlo Wood carlo at alinoe.com
Sun Sep 9 02:27:06 UTC 2001


As is described in http://www.cuj.com/experts/1902/alexandr.htm?topic=experts
`volatile' can be used to have the compiler help with checking for Multi-Threading
race conditions.

I'd like to investigate using this technique for the specific case of
(SGI) STL containers and their iterators, especially map<>.

In order to make this post interesting for the lesser expert, I'll add an
introduction:

Introduction
------------

You already need to be familiar with the STL and have basic understanding
of multi-threading.  First read the URL given above.  Further, make sure
to have read http://www.sgi.com/tech/stl/thread_safety.html.

When dealing with the STL map<> are two operations that are related to
locking the internal tree structure of the map:

1. Operations that change the internal tree structure of the map
   (insert, erase, operator= and swap).
2. Operations that read the internal tree structure of the map
   (operator==, operator<, begin, end, rbegin, rend, empty, size,
    max_size, operator[], find, count, lower_bound, upper_bound and
    equal_range).

Many of these member functions either take an iterator and/or return one.
Ignoring `reverse_iterator' for now, we have two types of iterators:
map::iterator and map::const_iterator.  Constant member functions return
the latter while non-const member functions return normal iterators.
Some member functions return these iterators as part of a pair<>.

There are two kind of relevant operations on iterators (which itself are
assumed not to be shared but automatic):

3. Operations that change the content of the element pointed to by
   an iterator.
4. Operations that read the content of the element pointed to by a
   const_iterator.

For both sets (1 and 2, and, 3 and 4) we can use read/write locks: locks
that allow one writer (and no readers) or multiple readers (and no writers).
The read/write lock on operation 3/4 could be one on a per-element basis,
but I doubt that is efficient in most practical cases and for the remainder
of this post I'll assume that we lock all elements at once.


Using qualifiers to check for proper locking
--------------------------------------------

When we use one read/write lock for accesses to elements through iterators,
then we don't need to use locks inside the Compare object of the map<>
provided that we also acquire a read lock for operations 3 and 4 prior to
an operation of type 2 (like find).  This is a second trade-off, as most
operations of type 2 do not access elements; actually, only operator==,
operator< and find (through the Compare object) do.

STL member functions do not have the volatile qualifier so that it is not
possible for the compiler to do checks, and we need to acquire the locks
prior to calling these methods in order to play safe.

My goal is to use `volatile' to check for the thread-safety of accesses
to the internal tree structure of a container, and to use `const' to check
for the thread-safety in relation to reading or writing.

The reason that we don't want to try to use `volatile' for iterators
is because we will only use automatic iterators.  These will only
be created inside critical sections and will thus be already be thread-safe.

In the context of this post, the meaning of `volatile' means: outside critical
section;  and the meaning of `const' is: outside a critical section with a
writers lock.

We then declare a shared map as follows:

static map<Key, T, Compare, Allocator> const volatile* map_ptr;

Which is initialized *once* in the first thread that will possibly use it
(so that during initialization no other threads are using the variable
`map_ptr', and that variable itself can be consider Single Threaded).
For example:

int main(void)
{
  map_ptr = new map<Key, T, Compare, Allocator>;
  ...
}

The fun of this all is thus that when you try to access any member function
of map_ptr, the compiler will complain because that member function is not
marked volatile: it is not possible to access the map at all.

Next, we need two read/write lock objects.  Consider a class RwLock with
the following members:

class RwLock {
public:
  void acquire_write_lock();
  void acquire_read_lock();
  void release_write_lock();
  void release_read_lock();
  void convert_read_lock_into_write_lock();
  void convert_write_lock_into_read_lock();
};

Further suppose we create the two read/write locks for the given operations
as follows:

RwLock map_ptr_lock;			// For operations 1 and 2.
RwLock map_ptr_iterator_lock;		// For operations 3 and 4.

Then it should be possible to write template classes like the one given by
Andrei Alexandrescu in http://www.cuj.com/experts/1902/alexandr.htm?topic=experts,
class LockingPtr, that control the read/write locks for our container.

Accesses to the map pointer `map_ptr' can work much as with LockingPtr,
but critical sections related to operations 3 and 4 may have a much
larger scope: as long as the automatic(!) iterator variable exists.

An example of the usage of the wanted interface could be:

map<Key, T, Compare, Allocator>::const_iterator
	iter(AcquireReadLock(map_ptr, map_ptr_lock)->find(...));

Where `AcquireReadLock' would start a critical section by acquiring
a read-lock on map_ptr_lock and then cast away the volatile of map_ptr.

Another example:

pair<map<Key, T, Compare, Allocator>::iterator, bool>
	result(AcquireWriteLock(map_ptr, map_ptr_lock)->insert(value));

Where `AcquireWriteLock' would start a critical section by acquiring
a write-lock on map_ptr_lock and then cast away both the const and the
volatile of map_ptr.

The problem of this is that in both cases the returned type is not safe.
What we need is are iterators whose construction acquire the
map_ptr_iterator_lock and whose destruction releases that lock again.

Perhaps working with a map<Key, T volatile, Compare, Allocator> (and
then casting away that volatile at the moment we acquire the lock)
is a solution here.  But I am sure that AcquireReadLock and
AcquireWriteLock need to do more; actually should apply an adaptor
to map_ptr in order to get full control over all types, in which case
`insert' would return an arbitrary different type.  The creation of
this type could then take care of the locking of map_ptr_iterator_lock.

I'd like to hear from others, what do you think of this idea?

-- 
Carlo Wood <carlo at alinoe.com>



More information about the tuxCPProgramming mailing list