Robust Lock

[vlad-nn]

Hi!

In attempts to find robust mutex implementation for MacOS, I found this article, and this repo.

Just some notes on your RobustLock implementation.

1. void RobustLock::lock() method: if the process gets killed just before exclusive_owner = getpid(); assignment, then robust recovery mechanism will break: exclusive_owner will be zero, while mutex will be held by dead process. I understand, that this is extremely rare and artificial event, but technically, it is a race condition.

2. void RobustLock::unlock() method: if the process gets killed just before mutex_.unlock(); call, then robust recovery mechanism will again break: exclusive_owner will be zero, while mutex will be held by dead process. I understand, that this is again extremely rare and artificial event, but technically, it is another race condition.

3. The process of mutex initialization in interprocess shared memory is out of the scope of RobustLock class, but probably it is implemented somewhere. That place is also prone to race conditions when one process already operates with mutex, while another process just initializes it. This initialization process is usually not atomic and therefore should be protected by some other interprocess lock (for example, file-based).

4. In this aspect it is not clear, why exclusive_owner = 0 assignement is present in the destructor. Imagine a situation when a process owning a mutex exits gracefully with execution of all destructors while still holding the mutex (programming error). This will effectively disable robust recovery mechanism, since exclusive_owner is 0 but mutex is locked.

5. Same reasoning applies to the constructor: std::atomic<__pid_t> exclusive_owner{0};. Assuming that the RobustLock object resides in interprocess shared memory (otherwise how it will be possible to implement interprocess shared lock, right?), then on construction of an object exclusive_owner member will be zeroed. It at this time some other process already operates with this shared mutex, robust recovery mechanism will be again broken.

6. Robust recovery mechanism uses non-documented feature that a mutex can be unlocked from another thread. Yes, by looking in the source code of pthread implementation for both Mac and Linux, it is like that. But technically, it is undefined behavior (see here: https://man7.org/linux/man-pages/man3/pthread_rwlock_unlock.3p.html): quote:

Results are undefined if the read-write lock rwlock is not held by the calling thread.

7. Also the polling used in lock() method to periodically check for dead process is not very optimal/efficient: instead of effective waiting, the thread is awake executing while() loop body periodically sleeping for tiny 1 us. I understand that polling is a necessary evil here, but at least sleep can be done with ever increasing duration (but capped to, say, 1ms).

8. And as you already know, PIDs get recycled because PID space is just 100K.

[Squadrick]

@vlad-nn You've raised great points, let me respond to them all:

1. Correct, this is possible.
2. Correct, this is possible. I couldn't think of any way to avoid this edge case, do you have any suggestions?
3. The mutex is initialized in shm::memory::Memory. It uses POSIX shm_open's EEXIST error code to ensure that the shared memory is initialized only once. There's another mechanism here to protect against dead processes too (PIDSet). The initialization is slow, but happens only once across all the processes communicating.
4. Good catch. I'll raise a PR to fix this.
5. See 3., the RobustMutex will be initialized only once, which is when it is set to 0, and unlocked.
6. Correct. I had to rely on undefined behaviour for this implementation. Necessary evil.
7. True, this can be optimized. Let me raise a PR for adding bigger sleep + exp backoff.
8. Correct. There's a way to protect against PID recycle by tracking both the PID and the time of lock acquisition. When checking if a PID is alive, also check for when the process was created. Haven't thought deeply about it, but don't see any obvious flaw; what do you think?

[vlad-nn]

2. Unfortunately, no suggestions. While 1. can be addressed by assigning exclusive_owner to current PID before locking (hoping that if we get killed after that, the next process will recover mutex), 2. is impossible to fix. This is the reason I started looking for robust lock implementation for MacOS. Otherwise I already have pretty robust solution very similar to yours, but with all ohter aforementioned problems adressed.

3. Yes, either that, or some GUID, which is generated at the process startup and appended to real PID. You use PID to check for dead preocess, while a suffix allows discriminating between different processes with the same PID.