Safe and effective way to put a mutex on a container entry

Question

C++'s std::mutex does not have a move constructor. There is a good reason for that. Basically, move constructors themselves are not generally thread safe, and the whole point of a mutex is that multiple threads will be trying to access it simultaneously.

An unfortunate implication of this is that a mutex cannot be placed into a container directly. Containers need the ability to safely move their contents around, and you can't do that with a mutex.

The easy way out is to just protect the entire container with a single separate mutex. But suppose I want finer-grained control than that? If I'm implementing a database via a container (eg: std::map), it seems reasonable to want the ability to lock individual records, not just the whole database.

The next thing that comes to mind is to hack around the problem by using std::unique_ptr. That would compile, but it doesn't really change the basic problem, does it? The scenario where there's a problem with move is where thread1 makes a container change that causes an entry move while thread2 is in the middle of using that container entry. In this scenario, thread2 could just as easily end up holding a destructed entry or smart pointer. It seems like no matter what, you end up having to lock the entire container with a mutex before doing anything.

It seems like there ought to be a known idiom for doing these kinds of things.

@erenon: It would. But it would be nicer if there were a solution that didn't involve dynamic allocation. — Mike Seymour, Dec 03 '14 at 16:26
Well, in case of std:: containers, most likely you are already using dynamic memory. A preallocated set of mutexes and pointers to them in the structure might ease it. — erenon, Dec 03 '14 at 16:36
One interesting idea... you have a mutex... why can't a move constructor lock (the mutex), perform the move semantics, and then unlock it? This may not be the best way, but it is certainly thread-safe, and as long as you are only working with a single mutex at a time, it will be deadlock-free. — Ken P, Dec 03 '14 at 16:38
You could put it in a `map` without making it dynamic... but then the `map` itself is what's making it dynamic. — Barry, Dec 03 '14 at 16:40
@erenon: it's still an extra level of indirection (and fingers crossed for good memory locality) — Karoly Horvath, Dec 03 '14 at 16:41
@KarolyHorvath: but it solves the problem described in the question. — erenon, Dec 03 '14 at 16:43
It seems like you would want a mutex outside of the container anyway. Say two things want to operate on the container at the same time, if thread A grabs the lock first, and then _moves_ the container to a new location, thread B would then get the lock afterwards and be operating on an empty container. — mukunda, Dec 03 '14 at 16:52
"It seems like there ought to be a known idiom for doing these kinds of things" - unique_ptr? if you want to go for high performance I guess you need MT containers doing their own locking (supporting complex operations with effective locking like traversing, find, transform....). You would probably need this anyways, imagine putting a mutex on each node in `std::map`, you will have huge contention on the root node, pretty much forcing the operations to be executed sequentially. — Karoly Horvath, Dec 03 '14 at 17:01
When do you need to move mutex-protected map values? Can you show a usage scenario, with code? As for vectors and similar, you simply have to lock the entire vector. This issue has nothing to do with move construction. — n. m. could be an AI, Dec 03 '14 at 17:07
@kenp the linked answer explains why this can't work on many popular implementations — sehe, Dec 03 '14 at 17:26
`std::map` elements are stable, why would they be getting moved? You can put a structure containing a `std::mutex` into a `std::map` using `emplace(key, lockable_object{})` or for more control over constructing the mapped type: `emplace(std::piecewise_construct, std::make_tuple(key), std::make_tuple(args, for, mapped, type))` — Jonathan Wakely, Dec 03 '14 at 17:27

Adrian Maire · Answer 1 · 2014-12-04T06:45:40.153

1

The mutex does not require to be moved:

Imagine that every row in your map is like:

template <class T>
class row
{
    shared_ptr<mutex> m;
    T data;
    ...
};

So if your row need to be moved or copied, there is no problem.

Then, you may access the mutex from every process to access the data.

Of course, you need a global mutex to perform changes on the whole map: insert / delete / [] / any other operation that change the state of the map.

EDITED:

Following a simple example of code with a mutex in every row. (It does not implement anything else that just the data structure)

#include <memory>
#include <map>
#include <mutex>

template <class T>
class row
{
    std::shared_ptr<std::mutex> m;
    T data;
public:
    row( std::shared_ptr<std::mutex> mut): m(mut){};
};

auto main () -> int
{
    std::shared_ptr<std::mutex> mut(new std::mutex);
    std::map<int,row<int>> db;
    row<int> a(mut);
    db.insert(std::pair<int, row<int>>(1, a));
    return 0;
}

edited Dec 04 '14 at 06:45

answered Dec 03 '14 at 17:37

Adrian Maire

14,354
9
45
85

This seems like a legit point. Of course, changes to the whole map are I believe the only thing that could cause the mutex object to need to be moved in the first place, which means with the proper global locking in place, all I need is a hack to get around the compiler issue of std::mutex not having a move constructor. – T.E.D. Dec 03 '14 at 17:52
1

...also as a nit, operator[] potentially does an insert, so safely doing a lookup with that operator would require locking the whole "database" as well. – T.E.D. Dec 03 '14 at 18:19
@T.E.D. I just edited to add a sample that compile correctly with a mutex inside the map. To be honest, I do not understand exactly your current problem, I hope this will help you. – Adrian Maire Dec 03 '14 at 18:43
Is it me, or you have a double free there? – UldisK Dec 04 '14 at 06:37
You don't need this. Use a mutex directly, rather than a pointer to one. You never should move or copy a row, or even expose it to the outside world in any way. Emplace when you insert, return the data (reference) when you get. You also need a mutex on `operator[]`. – n. m. could be an AI Dec 04 '14 at 10:06
@n.m. - On my compiler the code flat out would not compile with a mutex in the map, as it insisted the entire entry be moveable. – T.E.D. Dec 04 '14 at 13:54
Which code, which compiler? `[]` naturally won't work, use `emplace` and `find`. http://ideone.com/zrJOBt – n. m. could be an AI Dec 04 '14 at 14:52
"`operator[]` potentially does an insert" doesn't matter, you need a mutex on `find` too, because it reads something that can be modified by other threads. – n. m. could be an AI Dec 04 '14 at 15:05
The read does not need to be on mutex, only to ensure there is no writing operation at the same time: For example a flag (modified with mutex) may be activated when writing, and only tested for reading, that allow lot of read at the same time without to sync (and much better efficiency). Well, it is a bit more complicated, but reading does not need to be on mutex condition. – Adrian Maire Dec 04 '14 at 17:11
@AdrianMaire yes you can implement a reader-writer lock but it is indeed more complicated. – n. m. could be an AI Dec 04 '14 at 21:24

Safe and effective way to put a mutex on a container entry

1 Answers1

Linked