Deadlock avoidance by ordering std::mutex

Question

Is there a portable implementation of the deadlock avoidance logic here (see the section marked `NON-PORTABLE'):

#include <cstdint>
#include <iostream>
#include <mutex>
#include <thread>

typedef long Money; //In minor unit.

class Account {
public:
    bool transfer(Account& to,const Money amount);
    Money get_balance() const;
    Account(const Money deposit=0) : balance{deposit} {}
private:
    mutable std::mutex lock;
    Money balance;
};

bool Account::transfer(Account& to,const Money amount){
    std::unique_lock<decltype(this->lock)> flock{this->lock,std::defer_lock};
    std::unique_lock<decltype(to.lock)> tlock{to.lock,std::defer_lock};
//NON-PORTABLE:BEGIN: using intptr_t AND assuming Total Strict Order.
    const auto fi{reinterpret_cast<const std::intptr_t>(static_cast<const void*>(&this->lock))};
    const auto ti{reinterpret_cast<const std::intptr_t>(static_cast<const void*>(&to.lock))};
    if(fi<ti){
        flock.lock();
        tlock.lock();
    } else if (fi!=ti) {
        tlock.lock();
        flock.lock();
    } else {
        flock.lock();
    }
//NON-PORTABLE:END  
    this->balance-=amount;
    to.balance+=amount;
    return true;
}

Money Account::get_balance() const{
    const std::lock_guard<decltype(this->lock)> guard{this->lock};
    return this->balance;
}

void hammer_transfer(Account& from,Account& to,const Money amount, const int tries){
    for(int i{1};i<=tries;++i){
        from.transfer(to,amount);
    }
}

int main() {
    constexpr Money open_a{ 200000L};
    constexpr Money open_b{ 100000L};
    constexpr Money tran_ab{10};
    constexpr Money tran_ba{3};
    constexpr Money tran_aa{7};

    Account A{open_a};
    Account B{open_b};
    
    std::cout << "A Open:" << A.get_balance() << '\n';
    std::cout << "B Open:" << B.get_balance() << '\n';
    
    constexpr long tries{20000}; 
    std::thread TAB{hammer_transfer,std::ref(A),std::ref(B),tran_ab,tries};
    std::thread TBA{hammer_transfer,std::ref(B),std::ref(A),tran_ba,tries};
    std::thread TAA{hammer_transfer,std::ref(A),std::ref(A),tran_aa,tries};

    TAB.join();
    TBA.join();
    TAA.join();

    const auto close_a{A.get_balance()};
    const auto close_b{B.get_balance()};   
    
    std::cout << "A Close:" << close_a<< '\n';
    std::cout << "B Close:" << close_b<< '\n';
    
    int errors{0};
    if((close_a+close_b)!=(open_a+open_b)){
        std::cout << "ERROR: Money Leaked!\n";
        ++errors;
    }
    if(close_a!=(open_a+tries*(tran_ba-tran_ab)) ||
          close_b!=(open_b+tries*(tran_ab-tran_ba))
    ){
        std::cout << "ERROR: 'Lost' Transaction(s)\n";
        ++errors;
    }
    if(errors==0){
        std::cout << "* SUCCESS *\n";
    }else{
        std::cout << "** FAILED **\n";
    }
    std::cout << std::endl;
    return 0;
}

Runnable here: https://ideone.com/hAUfhM

The assumptions are (and I believe sufficient – anyone?) that intptr_t exists and that the relational operators on intptr_t imply a Total Strict Ordering on the pointer values they represent.

That assumed ordering is not guaranteed and could be less portable than the non-portability of ordering of pointers (e.g. if intptr_t is wider than the pointer and not all bits are written).

I am aware of some different riffs on this and other designs. I'll upvote all good answers even if not portable that identify their assumptions about the implementation and ideally a platform where they apply and preferably one where they don't!

Answer 1

std::lock() has an buildin deadlock avoiding algorithm.

https://en.cppreference.com/w/cpp/thread/lock

Answer 2

Once you start to have lock contention you have lost with this method and need to rethink the whole solution. And nearly all locks causes a context switch that will cost around 20000 cycles each.

Usually most accounts have either many ingoing (shops, arrangements) or outgoing (pensions, dole etc.)

Once you have identified the contended account you can queue up a lot of transactions and then lock the contented account and run the transactions by try_lock the other account, if the lock succeed the transaction is done. Try the try_lock a couple of times then do the scope_lock with both locks for the remaining taking all transactions common for those two.

Part 2. How do I ensure an safe ordering of my locks as comparing pointers that are not into the same area is UB.

You add an unique ID to the account and compare on that instead!

Answer 3

tl;dr - you can make your original pointer comparison portably in C++20. I'd probably wrap that code into a scoped_ordered_lock or something though, because the code is still a bit hairy.

---

The assumptions are (and I believe sufficient – anyone?) that intptr_t exists and that the relational operators on intptr_t imply a Total Strict Ordering on values when holding values cast from valid non-null pointers to std::mutex.

Not precisely. You do always have a total strict order on the integral values. The problem arises when the mapping from intptr_t to pointer is many-to-one (this is the case for the segmented address example here - ie, TSO on intptr_t is not sufficient).

The pointer to intptr_t mapping must also be injective (it doesn't have to be a bijection, because we don't care if some intptr_t values are unused/don't represent valid pointers).

Anyway, it's obvious that a total strict ordering on pointers can exist: it's just implementation-specific. Segmented addresses can be normalized or flattened, etc.

Fortunately, a suitable implementation-defined total strict ordering is provided: by the 3-way functor std::compare_three_way in C++20, and by the 2-way functors less, greater etc. prior to C++20 (and maybe also in C++20).

There is no equivalent language about the implementation-defined strict total order over pointers in the text about the spaceship operator - even though compare_three_way is described as calling that - or about the other relational operators.

This seems to be deliberate, so that the builtin operators <, >, , <=, >=, and <=> don't acquire new constraints that might be expensive on some platform. Indeed, the 2-way relational operators are explicitly described as a partial order on pointers.

So, this should be identical to your original code, except portable:

const auto order = std::compare_three_way{}(&this->lock, &to.lock);
if(order == std::strong_ordering::less){
    flock.lock();
    tlock.lock();
} else if (order == std::strong_ordering::greater) {
    tlock.lock();
    flock.lock();
} else {
    flock.lock();
}

Note

• as of C++20 (and specifically PDF:P1961R0), [comparisons.general] says

  For templates less, greater, less_­equal, and greater_­equal, the specializations for any pointer type yield a result consistent with the implementation-defined strict total order over pointers

  This is a weaker requirement which permits them to provide a partial order, so long as it never disagrees with the total order. It's not obvious whether this is a deliberate weakening, or it only intended to say that they must implement the same total order defined elsewhere.

• prior to C++20 less etc. did require a total order for these functors.

In any case, if you don't have access to C++20 and compare_three_way, your less etc. are guaranteed to provide the total ordering you need. Just don't rely on the raw relational operators.

Answer 4

This is a self-answer to show the revised code. The credit is due to the accepted answer above. The learning for me is that since C++14 std::less, std::greater, etc. define a Strict Total Order on pointers that is consistent with the partial order already defined by < and > etc.

By using those templates, this code is now guaranteed to be deadlock-free. In C++20 it can be made neater and potentially faster with std::compare_three_way<>.

https://ideone.com/ekuf2f

#include <functional>    
#include <iostream>
#include <mutex>
#include <thread>

typedef long Money; //In minor unit.

class Account {
public:
    bool transfer(Account& to,const Money amount);
    Money get_balance() const;
    Account(const Money deposit=0) : balance{deposit} {}
private:
    mutable std::mutex lock;
    Money balance;
};

namespace{
    std::less<void*> less{};
    std::equal_to<void*> equal_to{};
}

bool Account::transfer(Account& to,const Money amount){
    std::unique_lock<decltype(this->lock)> flock{this->lock,std::defer_lock};
    std::unique_lock<decltype(to.lock)> tlock{to.lock,std::defer_lock};
    if(less(&this->lock,&to.lock)){
        flock.lock();
        tlock.lock();
    } else if(equal_to(&this->lock,&to.lock)) {
        flock.lock();
    } else {
        tlock.lock();
        flock.lock();
    }
    this->balance-=amount;
    to.balance+=amount;
    return true;
}

Money Account::get_balance() const{
    const std::lock_guard<decltype(this->lock)> guard{this->lock};
    return this->balance;
}

void hammer_transfer(Account& from,Account& to,const Money amount, const int tries){
    for(int i{1};i<=tries;++i){
        from.transfer(to,amount);
    }
}

int main() {
    constexpr Money open_a{ 200000L};
     constexpr Money open_b{ 100000L};
    constexpr Money tran_ab{10};
    constexpr Money tran_ba{3};
    constexpr Money tran_aa{7};

    Account A{open_a};
    Account B{open_b};
    
    std::cout << "A Open:" << A.get_balance() << '\n';
    std::cout << "B Open:" << B.get_balance() << '\n';
    
    constexpr long tries{20000}; 
    std::thread TAB{hammer_transfer,std::ref(A),std::ref(B),tran_ab,tries};
    std::thread TBA{hammer_transfer,std::ref(B),std::ref(A),tran_ba,tries};
    std::thread TAA{hammer_transfer,std::ref(A),std::ref(A),tran_aa,tries};

    TAB.join();
    TBA.join();
    TAA.join();

    const auto close_a{A.get_balance()};
    const auto close_b{B.get_balance()};   
    
    std::cout << "A Close:" << close_a<< '\n';
    std::cout << "B Close:" << close_b<< '\n';
    
    int errors{0};
    if((close_a+close_b)!=(open_a+open_b)){
        std::cout << "ERROR: Money Leaked!\n";
        ++errors;
    }
    if(close_a!=(open_a+tries*(tran_ba-tran_ab)) ||
          close_b!=(open_b+tries*(tran_ab-tran_ba))
    ){
        std::cout << "ERROR: 'Lost' Transaction(s)\n";
        ++errors;
    }
    if(errors==0){
        std::cout << "* SUCCESS *\n";
    }else{
        std::cout << "** FAILED **\n";
    }
    std::cout << std::endl;
    return 0;
}