Blogaria

The actual reason is that last thursday I was invited at the State Univ. of Groningen to present a C++ lecture, and I'd picked daemons, forking, threading, mutexes, and the whole shebang. I presented the following snippet of how globals could be locked in a threaded program:

// EXAMPLE 1  
// Write something to cout, without other threads interfering in the displayed line.
mutex_lock(&cout);
cout << "Hello World!\n";
mutex_unlock(&cout);

// EXAMPLE 2	
// Function gethostbyname() (DNS resolving) is known to be not thread-safe in many implementations
mutex_lock(gethostbyname);
struct hostent *hostaddr = gethostbyname("www.kubat.nl");
if (hostaddr) {
    .
    . Host successfully resolved
    .
} else {
    .
    . Hostname could not be resolved
    .
}	
mutex_unlock(gethostbyname);	

How not to do it

typedef std::map<void *, pthread_mutex_t> LockMap;
static LockMap lockmap;

static void lock_ptr(void *p) {
    if (lockmap.find(p) == lockmap.end() && pthread_mutex_init(&lockmap[p], 0))
	throw "Failed to initialize mutex";
    if (pthread_mutex_lock(&lockmap[p]))
	throw "Failed to lock mutex";
}
static void unlock_ptr(void *p) {
    if (pthread_mutex_unlock(&lockmap[p]))
	throw "Failed to unlock mutex";
}

void mutex_lock(void *p) {
    lock_ptr(&lockmap);
    lock_ptr(p);
    unlock_ptr(&lockmap);
}
void mutex_unlock(void *p) {
    unlock_ptr(p);
}

What's the problem?

"Aha," said the audience (specifically Thomas ten C., thanks for all the comments!), "there's a potential problem there!" The implementation of the Standard Template Library (STL) isn't guaranteed to be thread-safe; e.g., consider the following:

• A thread is unlocking an object. It is at the statement lockmap[p] in line 12.
• Another thread is at that time locking, and is at line 5, at lockmap.find(p) == lockmap.end().
• But, if the STL implementation for std::map isn't thread-safe, then these two threads might mess up the underlying map beyond imagination...

I had assumed that reading the map wouldn't modify its layout, so that entire map locking would be only necesary during the writing phase, i.e., the locking of a particular object. Not necessarily true. "Assume nothing", I should've known... Thomas commented in a mail:

Microsoft writes: "A single object is thread safe for reading from multiple threads. [...] If a single object is being written to by one thread, then all reads and writes to that object on the same or other threads must be protected."

The SGI implementation, and the GNU implementation which uses this, is thread-safe when reading: "The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe." Gnu uses the same definition: "We currently use the SGI STL definition of thread safety."

Now what

If you are interested in a source file having all this code inside: you can grab it here. All classes and members are contained in one file - including a main() function to test it all. If you want to use it, then feel free to split it up and customize it however you like.

Basic Mutex

class Mutex {
public:
    Mutex(): _initialized(false) 	{ }
    void lock();
    void unlock();
private:
    pthread_mutex_t _mutex;
    bool _initialized;
};

void Mutex::lock() {
    if (!_initialized) {
	_initialized = true;
	if (pthread_mutex_init(&_mutex, 0))
	    throw "Failed to initialize mutex";
    }
    if (pthread_mutex_lock(&_mutex))
	throw "Failed to lock mutex";
}    

void Mutex::unlock() {
    if (pthread_mutex_unlock(&_mutex))
	throw "Failed to unlock mutex";
}

Mutex Nodes

class MutexNode {
public:
    MutexNode(void *o);
    ~MutexNode();
    
    void obj(void *o)			{ _obj = o; }
    void *obj() const  			{ return _obj; }

    void left(MutexNode *l)		{ _left = l; }
    MutexNode *left() const   		{ return _left; }

    void right(MutexNode *l)		{ _right = l; }
    MutexNode *right() const   		{ return _right; }

    void lock()				{ _mutex.lock(); }
    void unlock()			{ _mutex.unlock(); }
    
private:
    Mutex _mutex;
    void *_obj;
    MutexNode *_left, *_right;
};

MutexNode::MutexNode(void *o): _mutex(), _obj(o) {
    _left = _right = 0;
}

MutexNode::~MutexNode() {
    delete _left;
    delete _right;
}

The Mutex Tree

   
class MutexTree {
public:
    MutexTree();
    ~MutexTree();
    
    void lock(void *o);
    void unlock(void *o);
    
private:
    void locktree()		{ _treelock.lock(); };
    void unlocktree()		{ _treelock.unlock(); }
    MutexNode *nodelock(void *o, MutexNode *start);
    void nodeunlock(void *o, MutexNode *start);
    
    MutexNode *_root;
    Mutex _treelock;
};

MutexTree::MutexTree(): _treelock() {
    _root = 0;
}

MutexTree::~MutexTree() {
    delete _root;
}

void MutexTree::lock(void *o) {
    locktree();
    _root = nodelock(o, _root);
    unlocktree();
}

void MutexTree::unlock(void *o) {
    nodeunlock(o, _root);
}

MutexNode *MutexTree::nodelock(void *o, MutexNode *start) {
    if (!start) {
	start = new MutexNode(o);
	start->lock();
    } else if (start->obj() == o)
	start->lock();
    else if (start->obj() < o)
	start->left(nodelock(o, start->left()));
    else
	start->right(nodelock(o, start->right()));
    
    return start;
}

void MutexTree::nodeunlock(void *o, MutexNode *start) {
    if (!start)
	return;
    
    if (start->obj() == o)
	start->unlock();
    else if (start->obj() < o)
	nodeunlock(o, start->left());
    else
	nodeunlock(o, start->right());
}

Translating to mutex_lock() and mutex_unlock()

static MutexTree mt;

void mutex_lock(void *obj) {
    mt.lock(obj);
}

void mutex_unlock(void *obj) {
    mt.unlock(obj);
}

Test Harnass

void *test(void *data) {
    for (int i = 1; i <= 10; i++) {
	if (i & 1) {
	    mutex_lock(&cout);    
	    cout << pthread_self() << " testing cout, loop " << i << '\n';
	    mutex_unlock(&cout);
	} else {
	    mutex_lock(&cerr);
	    cerr << pthread_self() << " testing cerr, loop " << i << '\n';
	    mutex_unlock(&cerr);
	}
    }
    return 0;
}

int main() {
    try {
	pthread_t th, threads[10];
	for (unsigned i = 0; i < sizeof(threads) / sizeof(pthread_t); i++) {
	    pthread_create(&th, 0, test, 0);
	    threads[i] = th;
	}
	for (unsigned i = 0; i < sizeof(threads) / sizeof(pthread_t); i++)
	    pthread_join(threads[i], 0);
	cout << "Done!\n";
	return 0;
    } catch (char const *s) {
	cerr << s << "\n";
	return 1;
    }
}  

Update: I've modified the above version for faster access - which can be useful in programs that use up a lot of mutexes. The modified version has a hash-table, which indexes trees. The first lookup of a mutex given a void* is therefore much faster. Drop me a note if you are interested. The hash-table version wins performance-wise in a worst-case scenario where loads of mutexes are being used, all relating to linearly situated objects. E.g, consider: int obj[5000]; for (int i = 0; i < 5000; i++) mutex_lock(&obj[i]); This is the worst case, in the sense that each consecutive object to lock is (pointer-wise) 'larger' than the previous. The binary tree of MutexTree will degenerate into a list. That's where the hash table is beneficial. However, most programs (a) won't have that many mutexes, and (b) won't suffer from such linearity. I think therefore that in most situations the binary tree approach will do quite nicely.