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!
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();
}
as of C++20 (and specifically PDF:P1961R0), [comparisons.general] says
For templates
less,greater,less_equal, andgreater_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.