Thread safe std::map: Locking the entire map and individual values

Question

struct Data
{
 ...
 CRITICAL_SECTION valLock;
}    
std::map<int, Data> mp;
CRITICAL_SECTION mpLock;

I am currently using two critical sections to make this thread safe.

I have to lock both map and Data for updating a Data

//Lock mpLock
//Lock mp[key1].valLock
mp[key1].something = something_new;
//unlock mp[key1].valLock
//unlock mpLock

I looked into intel's concurrent hashmap, which does not need two locks and handles this internally.Is there any other way, if i don't want to use intel's tbb. I have only c++ 98 support.Can use boost though. Looked into boost::shared_mutex, but could not relate how i can use it in my current scenario.

EDIT: Is the lock on container really required? Can't i use Data::valLock to read/write Data.Any insertion in mp is not going to affect the existing iterators, so no lock is needed.Any deletion from mp will be preceded with Data::valLock.What cases could be missed here?

EDIT 2:

UpdateThread()
{
   //Lock mp[key].valLock
   mp[key].a = b;         //Line 1
   //unlock mp[key].valLock
}

ReadThread()
{
    //Lock mp[key].valLock
   something = mp[key].a;   //Line 2
   //unlock mp[key].valLock
}

So i am thinking that Line 2 can execute only if Line 1 has completed(or vice versa) i.e. mp has been updated(along with the map internals).So is it not safe? If not then it means if one thread modifies mp[key1], and another reads mp[key2], this is data race?

Answer 1

One mutex is needed to make the container thread-safe. And a per-object mutex to make each of these objects thread-safe.

A per-object mutex is rather a sub-optimal design. Another design is use copyable but immutable objects or store shared/intrusive pointers in the container.

With immutable objects readers lock the container (for read), make a copy of the element and unlock the container. Writers lock the container (for write) add/remove/modify elements and unlock. Because readers always make a copy of the element, there is never a contention between threads on elements.

With shared pointers readers do as above. Writers also do as above, but rather then modifying existing elements, writers always create a new element and replace the existing one.

Example with immutable objects:

template<class Key, class Value>
class ThreadSafeMap
{
    std::mutex m_;
    std::map<Key, Value> c_;

public:
    Value get(Key const& k) {
        std::unique_lock<decltype(m_)> lock(m_);
        return c_[k]; // Return a copy.
    }

    template<class Value2>
    void set(Key const& k, Value2&& v) {
        std::unique_lock<decltype(m_)> lock(m_);
        c_[k] = std::forward<Value2>(v);
    }
};

You may also like to use std::unordered_map (or open source ones) instead of std::map to get better performance. std::map is rather cache-unfriendly.

Answer 2

Is the lock on container really required?

Yes

Can't i use Data::valLock to read/write Data.

Of course you can, that's already what you're using it for.

Any insertion in mp is not going to affect the existing iterators, so no lock is needed

Wrong.

Insertions into a map don't invalidate existing iterators, but if you have two threads inserting or deleting at the same time (or one thread inserting/deleting and another thread finding), it's not safe. This is not because of iterators being invalidated, but because updating and traversing the internal node pointer graph can't safely be done concurrently.

The same is potentially true of any other node-based container.

Now, if you get (and keep) an iterator to your map while holding the container lock, you can keep referring to that single node via that iterator without holding the container lock, so long as the iterator isn't invalidated. This is fine.

If you want to do anything with the iterator other than dereference it, then you need the container lock again. Advancing the iterator, or finding another iterator, both have to traverse the node graph which (if you don't hold the lock) could be mutated underneath you by another thread performing an insertion or deletion.