confusion over using upgradable lock on std::map's find/insert

Question

Consider a thread-safe getter method in its,relatively, simplest form:

std::map<std::string, boost::shared_ptr<AAA> > repo;
AAA & get(const std::string &key)
{
    boost::upgrade_lock<boost::shared_mutex> lock(repoMutex);
    std::map<std::string, boost::shared_ptr<AAA> >::iterator it = repo.find(key);
    if(it == repo.end()){       
        boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(lock);
        boost::shared_ptr<AAA> t(new AAA(key));
        repo.insert(std::make_pair(key,t));
        return *t;
    }
    return *it->second;
}

in above, I use a shared(upgradeable) lock to protect a find operation, and upgrade to unique lock only if I need to insert a key/value. So far so good?

What I imagine is the following(please let me know if in any step my concept is wrong):

1. Two threads enter the method

2. Both are allowed to run repo.find() for the same key at the same time(and the key doesn't exist).

3. Both of them fail.as the key doesn't exist .

4. first thread gets exclusive access by entering the upgraded area, while the second thread waiting to enter upgraded area.

5. first thread finishes its job of creating a new entry for key and then walks off.

6. second thread enters and overwrites the key/value inserted by the first thread.(which is not what anybody wants)

How do we solve this issue? thanks

Answer 1

In short, there's almost nothing wrong with your current solution.

First of all, the second thread won't overwrite the data written by the first one, because map::insert() inserts only new keys. You only have to check if insert really inserted the element and return corresponding value.

The only concern is possible unwanted creation of t for nothing. In this case you can add another check after locking:

std::map<std::string, boost::shared_ptr<AAA> >::iterator it = repo.find(key);
if(it == repo.end()){       
    boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(lock);
    if (repo.find(key) == repo.end() {
        ...
    }
}

But you should profile your code to see if this gives you any advantage.

Also, you can utilize map::insert() with hint to avoid double searching for the key:

std::map<std::string, boost::shared_ptr<AAA> >::iterator it = repo.find(key);
if(it == repo.end()){       
    boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(lock);
    it = repo.lower_bound(key);
    if (it->first != key)
        boost::shared_ptr<AAA> t(new AAA(key));
        repo.insert(it, std::make_pair(key,t));
        return *t;        
    } else {
        return *it->second;
    }
}