Algorithm for a simple non-locking-on-read concurrent map?

Question

I'm trying to write a map that is thread-safe, but never locks or blocks on read. My attempt is to use a read-only map that gets copied out on write. The idea is get() is lock-free, and put() copies the current read-only underlying map to a new one, does the put, and swaps out the current underlying map for a new one. (yes, put() is inefficient since it copies the entire map, but I do not care for my use case)

My first stab at this used std::atomic<*StringMap> for the read-only map BUT there is a huge bug with this, probably due to my java background. get() atomically gets a pointer to the underlying map, which may or may not be the current one when it loads it (which is ok). But put() deletes the underlying map after it swaps it out for the new one. If get() is calling the old map just as it gets deleted, this will obviously crash.

A friend of mine suggested shared_ptr, but he's not sure if the shared_ptr operations do any locking under the covers. The docs say it is thread-safe, though. Edit: As nosid points out, it is not thread safe and I need the special atomic operation from std::atomic.

So my questions are: 1. Is this algorithm viable? 2. Do shared_ptr operations do any locking, especially on access?

#include <unordered_map>
#include <atomic>
#include <pthread.h>
#include <memory>

typedef std::unordered_map<std::string, std::string> StringMap;

class NonBlockingReadMap {
private:
    pthread_mutex_t fMutex;    
    std::shared_ptr<StringMap> fspReadMapReference;


public:

    NonBlockingReadMap() {
        fspReadMapReference = std::make_shared<StringMap>();
    }

    ~NonBlockingReadMap() {
        //so, nothing here?
    }

    std::string get(std::string &key) {
        //does this access trigger any locking?
        return fspReadMapReference->at(key);
    }

    void put(std::string &key, std::string &value) {
        pthread_mutex_lock(&fMutex);
        std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference);
        std::pair<std::string, std::string> kvPair(key, value);
        spMapCopy->insert(kvPair);
        fspReadMapReference.swap(spMapCopy);
        pthread_mutex_unlock(&fMutex);
    }

    void clear() {
        pthread_mutex_lock(&fMutex);
        std::shared_ptr<StringMap> spMapCopy = std::make_shared<StringMap>(*fspReadMapReference);
        fspReadMapReference.swap(spMapCopy);
        spMapCopy->clear();
        pthread_mutex_unlock(&fMutex);
    }

};

Answer 1

Your code contains a data race on the std::shared_ptr, and the behaviour of programs with data races is undefined in C++.

The problem is: The class std::shared_ptr is not thread-safe. However, there are special atomic operations for std::shared_ptr, which can be used to solve the problem.

You can find more information about these atomic operations on the following webpage:

• http://en.cppreference.com/w/cpp/memory/shared_ptr/atomic