unfair_recursive_mutex.hpp

// Copyright Take Vos 2020.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#pragma once
 
#include "unfair_mutex.hpp"
#include "thread.hpp"
#include <thread>
 
namespace hi::inline v1 {
 
class unfair_recursive_mutex {
    /* Thread annotation syntax.
     *
     * FIRST - The thread that acquires/acquired the mutex
     * OWNER - The FIRST thread that recursively requests a lock.
     * OTHER - Another thread while the mutex is held.
     */
 
    unfair_mutex_impl<false> mutex;
 
    // FIRST=write, OWNER|OTHER=read
    std::atomic<thread_id> owner = 0;
 
    // FIRST=write, OWNER=increment, FIRST|OWNER=decrement
    uint32_t count = 0;
 
public:
    unfair_recursive_mutex(unfair_recursive_mutex const &) = delete;
    unfair_recursive_mutex &operator=(unfair_recursive_mutex const &) = delete;
 
    unfair_recursive_mutex() = default;
    ~unfair_recursive_mutex() = default;
 
    [[nodiscard]] int recurse_lock_count() const noexcept
    {
        // The following load() is:
        // - valid-and-equal to thread_id when the OWNER has the lock.
        // - zero or valid-and-not-equal to thread_id when this is an OTHER thread.
        //
        // This only works for comparing the owner with the current thread, it would
        // not work to check the owner with a thread_id of another thread.
        if (owner.load(std::memory_order::acquire) == current_thread_id()) {
            return count;
        } else {
            return 0;
        }
    }
 
    [[nodiscard]] bool try_lock() noexcept
    {
        // FIRST | OWNER | OTHER
        hilet thread_id = current_thread_id();
 
        // The following load() is:
        // - valid-and-equal to thread_id when the OWNER has the lock.
        // - zero or valid-and-not-equal to thread_id when this is an OTHER thread.
        //
        // note: theoretically a relaxed load could be enough, but in C++20 any undefined behaviour causing an out-of-bound
        //       array access inside the critical section protected by the unfair_recursive_mutex will overwrite owner
        //       from the point of view of the optimizer.
        if (owner.load(std::memory_order::acquire) == thread_id) {
            // FIRST | OWNER
            hi_axiom(count != 0);
            ++count;
 
            // OWNER
            return true;
 
        } else if (mutex.try_lock()) { // OTHER (inside the if expression)
            // FIRST
            hi_axiom(count == 0);
            count = 1;
            hi_axiom(owner == 0);
 
            // note: theoretically a relaxed store could be enough, but in C++20 any undefined behaviour causing an out-of-bound
            //       array access inside the critical section protected by the unfair_recursive_mutex will overwrite owner
            //       from the point of view of the optimizer.
            owner.store(thread_id, std::memory_order::release);
 
            return true;
 
        } else {
            // OTHER
            return false;
        }
    }
 
    void lock() noexcept
    {
        // FIRST | OWNER | OTHER
        hilet thread_id = current_thread_id();
 
        // The following load() is:
        // - valid-and-equal to thread_id when the OWNER has the lock.
        // - zero or valid-and-not-equal to thread_id when this is an OTHER thread.
        //
        // note: theoretically a relaxed load could be enough, but in C++20 any undefined behaviour causing an out-of-bound
        //       array access inside the critical section protected by the unfair_recursive_mutex will overwrite owner
        //       from the point of view of the optimizer.
        if (owner.load(std::memory_order::acquire) == thread_id) {
            // FIRST | OWNER
            hi_axiom(count != 0);
            ++count;
 
            // OWNER
 
        } else {
            // OTHER
            mutex.lock();
 
            // FIRST
            hi_axiom(count == 0);
            count = 1;
            hi_axiom(owner == 0);
 
            // note: theoretically a relaxed store could be enough, but in C++20 any undefined behaviour causing an out-of-bound
            //       array access inside the critical section protected by the unfair_recursive_mutex will overwrite owner
            //       from the point of view of the optimizer.
            owner.store(thread_id, std::memory_order::release);
        }
    }
 
    void unlock() noexcept
    {
        // FIRST | OWNER
 
        // Unlock must be called on the thread that locked the mutex
        hi_axiom(recurse_lock_count());
 
        if (--count == 0) {
            // FIRST
 
            // Only OTHER can execute in `lock()` or `try_lock()`,
            // where it will either see the thread_id of FIRST or zero.
            // In both cases the OTHER thread is detected correctly.
            owner.store(0, std::memory_order::release);
 
            mutex.unlock();
            // OTHER
        }
        // OWNER | OTHER
    }
};
 
} // namespace hi::inline v1