Делаем любой объект потокобезопасным

[vesper-bot]

Вопрос на засыпку: сколько времени код проводит в ядре при реализации потокобезопасности таким образом? Т.е. есть у вас 10 потоков, выполняющих потокобезопасное сложение. Сколько времени относительно работы потоков занимает захват и освобождение мьютексов? Когда я писал свой колхоз многопоточной обработки, у меня 50% времени уходило на обеспечение потоковой безопасности (kernel time в диспетчере задач), пока я не переделал ввод-вывод на буферный. Здесь, судя по коду, ввод-вывод (доступ к объекту) атомарный для каждого объекта, и времени будет теряться прорва.

[a-tk]

Вдобавок: было бы неплохо ещё иметь семантику для объединения группы обращений к контейнеру в единую транзакцию вроде такой:

execute_around<std::vector<int>> vecc();
auto transaction = vecc.begin_transaction();
for (int i = 0; i < 100; ++i)
{
  vecc->push_back(i);
}

Но это приведёт к разрастанию контейнера и прокси-объекта, либо же к полиморфности прокси.

[AlexeyAB]

Так об этом вроде много написано в статье :)

safe_ptr<std::vector<int>> vecc;
{
  std::lock_guard<decltype(vecc)> lock(vecc); // или lock_timed_any_infinity lock(vecc)
  for (int i = 0; i < 100; ++i)
  {
    vecc->push_back(i);
  }
}

А в следующих статьях ещё есть xlock_safe_ptr.

[a-tk]

Я немножко другое имел в виду (или не так понял написанное): задача не в том, чтобы захватить несколько блокировок, а в том, чтобы минимизировать управление блокировками там, где это не нужно. Например, группу изменений закатать в транзакцию, сократив количество прыжков в kernel space.

[AlexeyAB]

Да, я именно об этом, чтобы минимизировать управление блокировками там, где это не нужно.
В моём примере выше — внутри цикла будет рекурсивное блокирование мьютекса, которое осуществляется исключительно в user-space, атомарно читая thread_id находящийся в кэш-L1 текущего ядра.
Используя xlock_safe_ptr() — блокировка вообще происходит только единожды.

[a-tk]

Понял свою ошибку, спасибо.

[ChiefPilot]

Извините, но не могу удержаться! :) Лучше была бы третья картинка, где на следующем по пути газоне тоже сделали бы нормальную дорожку. А то недоделка какая-то…

[AlexeyAB]

Заборы, барьеры — это должна быть картинка ко второй статье )

[kmu1990]

А если все операции такого цикла выполняются без пессимистических блокировок, то такой алгоритм называется lock-free.

Немного странное утверждение, алгоритм/структура данных является lock-free, если он/она предоставляет определенные гарантии прогресса, а не только, если в ней отсутствует использование блокировок. Таким образом, то что вы пишите не совсем согласуется с понятием lock-free:
1. заметим, что используя то, что вы назвали оптимистичной блокировкой (тот самый цикл с CAS операциями), можно реализовать то, что вы назвали пессимистичной блокировкой и использовать эту реализацию, таким образом, в алогоритме без явного использования блокировок блокировка может присутствовать неявно
2. то, что в алгоритме нет блокировок, не делает его автоматически lock-free, например, он может предоставлять более слабую гарантию obstruction-free.

[AlexeyAB]

Да, строго говоря, lock-free — гарантирует прогресс хотя бы одного потока в каждый момент времени. Но если есть пессимистическая блокировка (явная или неявная), то такая гарантия сразу пропадает. Т.е. отсутствие пессимистической блокировки условие необходимое, но недостаточное. Без пессимистических блокировок многопоточный алгоритм может быть: obstruction-free, lock-free, wait-free, write-contention-free.

[Videoman]

Ох. Тема конечно очень интересная и у вас основательно и по делу все расписано, но стоило бы упомянуть, что применение, на практики, а особенно в сложном коде идиомы «Execute Around Pointer» очень ограничено и не ни капельки не является «серебряной пулей». Особенно, это касается стандартных контейнеров и их тяге к производительности. Т.е. объекты конечно становятся потокобезопасными, но внезапно, становятся просто небезопасными. Приведу пример с вектором: операция взятия индекса или просто извлечения элемента, после применения «трюка», вдруг начинает приводит к UB, где в однопоточных ситуация гарантированно его небыло. Появляется куча операций, которыми, без существенного изменения интерфейса, просто не понятно как пользоваться, например pop_...()? Становятся нужны атомарные операции СheckAndDoSomthing ???
В общем слепым применением умного враппера, на практике, не обойтись. Повторюсь, из вашей основательной статьи это все следует, но, тем не менее, это не очевидно.

[AlexeyAB]

Вы сравнили многопоточное программирование используя «Execute Around Pointer» с однопоточным программированием — и тут ответ очевиден.
А если сравнить «Execute Around Pointer» с использованием отдельно std::mutex+std::map, то у последних все те же проблемы: deadlocks, возможность работы с инвалидированными индексами, итераторами, указателями и ссылками, плюс можно вообще забыть заблокировать mutex или заблокировать mutex от другого объекта.
Подробнее о недостатках «Execute Around Pointer» и о сравнении с std::mutex и lock-free написано в 3-ей статье.

Для атомарного выполнения сразу нескольких операций над одним контейнером можно использовать std::lock_guard.

std::safe_ptr<std::queue<int>> queue_ptr;
{
    std::lock_guard<decltype(queue_ptr)> lock(queue_ptr);
    int item = queue_ptr->front();
    queue_ptr->pop();
}

В стандарте C++17 добавлены составные операции для std::map, которые выполняться атомарно используя «Execute Around Pointer» без какого-либо дополнительного кода:

• insert_or_assign() – если есть элемент то присвоить, если нет то вставить
• try_emplace() – если элемента нет, то создать элемент
• merge() – слить 2 map в 1
• extract() – получить элемент, и удалить его из map

[Videoman]

Все верно. Замечание было об ограниченности данного подхода. Просто, чтобы не создавалось иллюзий, мол, взял класс, засунул во враппер и готово. Часто, голову придется сломать и перепроектировать весь интерфейс контейнера заново.

[kamushken]

Чёрт подери, опять эта картинка на Хабре…

[Bega]

круто

[veprbl]

А если иметь код (условно):

res1 = f(vecc1->a(), vecc2->a());
res2 = f(vecc2->a(), vecc1->a());

Могут быть дедлоки?

[AlexeyAB]

В таком коде не может быть дедлоков :)

lock_timed_any_infinity lock(vecc1, vecc2); // причем не важно в каком порядке они здесь идут
res1 = f(vecc1->a(), vecc2->a());
res2 = f(vecc2->a(), vecc1->a());

Даже если другой поток в другом месте делает так:

lock_timed_any_infinity lock(vecc2, vecc1); // причем не важно в каком порядке они здесь идут
res1 = f(vecc1->a(), vecc2->a());
res2 = f(vecc2->a(), vecc1->a());

[veprbl]

Если я правильно понял, в статье обсуждается эквивалентность следующему коду:

typedef execute_around<Foo> T;
{
T::proxy tmp1(vecc1.p.get(), *vecc1.mtx);
T::proxy tmp2(vecc2.p.get(), *vecc2.mtx);
res1 = f(tmp1.p->a(), tmp2.p ->a());
}
{
T::proxy tmp1(vecc2.p.get(), *vecc2.mtx);
T::proxy tmp2(vecc1.p.get(), *vecc1.mtx);
res2 = f(tmp2.p->a(), tmp1.p ->a());
}

[AlexeyAB]

В любом случае для двух и более контейнеров в одном выражении — вам надо использовать lock_timed_any_infinity lock(vecc1, vecc2); или единожды link_safe_ptrs(vecc1, vecc2), т.к. стандарт не гарантирует взаимный порядок создания временных переменных tmp1 и tmp2.

[nikitablack]

Т.е. функции move_money() и show_user_money_on_time() не были завершены и остановились навечно в deadlock. Решения есть 4:

Есть, по крайней мере, еще одно решение — std::lock().
Статья замечательная, респект за проделанную работу. Особое спасибо за оператор -> пишу на с++ много лет, но только сегодня узнал про «drill down behavior».

[AlexeyAB]

Спасибо.
Имелось ввиду 4 способа избежать deadlock именно для safe_ptr<>.
Да, std::lock() — разрешает проблему дедлоков, но только для объектов с публичными функциями try_lock(), lock(), unlock().
Но в safe_ptr<> функции try_lock() нету, а lock()/unlock() приватные — спрятаны, чтобы их не блокировал пользователь опасным способом без RAII.

Почему я не сделал свою функцию аналогично std::lock()?
Лично мне lock_timed_any_infinity использовать удобнее, чем std::lock() — приведу 3 примера — последний мне удобнее (да, у меня пропадает возможность разблокировать один safe_ptr<> явно раньше другого):

std::lock(mutex1, mutex2);
// critical section
mutex1.unlock();
mutex2.unlock();

{
  std::lock(mutex1, mutex2);
  std::lock_guard<std::mutex> lock1(mutex1, std::adopt_lock);
  std::lock_guard<std::mutex> lock2(mutex2, std::adopt_lock);
  // critical section
}

{
  lock_timed_any_infinity lock(safe_ptr1, safe_ptr2);
  // critical section
}

http://coliru.stacked-crooked.com/a/26b1b20bbcc87700
Поэтому для safe_ptr<> я сделал свой класс блокирования с разрешением дедлоков — lock_timed_any_infinity.

К тому же во время отладки я могу в lock_timed_any_infinity устанавливать очень большое значение таймаута и добавлять логирование ситуаций, при которых он превышен — тем самым находя места, на которых тратятся ресурсы для разрешения вероятных deadlock-ов. А для рилиза ставить стандартное значение таймаута — для автоматического разрешения дедлоков, которые ещё не нашел.

Плюс бывает полезно самому контролировать алгоритм разрешения дедлоков (графы или таймауты) и размер таймаута. Стандарт позволяет разным реализациям компиляторов использовать разные алгоритмы разрешения дедлоков в void std::lock() / int std::try_lock().

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/n4606.pdf

§ 30.4.3 Generic locking algorithms
(5)
Effects: All arguments are locked via a sequence of calls to lock(), try_lock(), or unlock() on each
argument. The sequence of calls shall not result in deadlock, but is otherwise unspecified. [ Note: A
deadlock avoidance algorithm such as try-and-back-off must be used, but the specific algorithm is not
specified to avoid over-constraining implementations. — end note ] If a call to lock() or try_lock()
throws an exception, unlock() shall be called for any argument that had been locked by a call to
lock() or try_lock().

[degs]

Мне показалось, или у вас действительно не определены операторы копирования/присвоения для safe_ptr?
Без них (точнее с автоматическими версиями) он сам по себе потоконебезопасен и полезность его очень ограничена.

[AlexeyAB]

Он удален, но неявно.
Внутри safe_ptr<> имеется константная переменная-член класса

const std::shared_ptr<T> ptr;

, которая неявно удаляет operator=().
http://coliru.stacked-crooked.com/a/e892d7d56bddbc1b

safe_ptr<int> safe_ptr1 = 1;            // OK
safe_ptr<int> safe_ptr2 = 2;            // OK
safe_ptr<int> safe_ptr3 = safe_ptr2;    // OK
safe_ptr1 = safe_ptr2;  // error: operator=() is implicitly deleted because the default definition would be ill-formed

[degs]

Получается, копирование разрешено а присвоение запрещено. И default copy-ctor вдруг оказывается безопасен. Красиво сделано, спасибо.

[prog_ilya]

Стандлартная библиотека C++ (std) не предназначена для высоконагруженных приложений.

[vital72]

другими словами, С++ не предназначен для высоконагруженных приложений. так чтоли?

[JKot]

Поясните, пожалуйста, следующий момент. Внутри safe_ptr указатель на поинтер завернут в shared_ptr. При этом в auto_lock_t используется сырой указатель, разве там не должен быть shared_ptr? Что будет если удалить safe_ptr в те время пока существуют живые экземпляры auto_lock_t?

[JozeAlehandro]

В части враппера над мапой - есть ли большой смысл 2 разных внутренних класса создавать (auto_lock_t и auto_lock_obj_t) ?

Почему не:

template<typename T, typename mutex_t = std::recursive_mutex, typename x_lock_t = std::unique_lock<mutex_t>,
    typename s_lock_t = std::unique_lock<mutex_t >>
class safe_ptr {
    typedef mutex_t mtx_t;
    const std::shared_ptr<T> ptr;
    std::shared_ptr<mutex_t> mtx_ptr;

    template<typename req_lock>
    class auto_lock_t {
        T * const ptr;
        req_lock lock;
    public:
        auto_lock_t(auto_lock_t&& o) : ptr(std::move(o.ptr)), lock(std::move(o.lock)) { }
        auto_lock_t(T * const _ptr, mutex_t& _mtx) : ptr(_ptr), lock(_mtx){}
        T* operator -> () { return ptr; }
        const T* operator -> () const { return ptr; }
        
        template<typename arg_t>
        auto operator [] (arg_t arg) -> decltype((*ptr)[arg]) { return (*ptr)[arg]; }
    };


    void lock() { mtx_ptr->lock(); }
    void unlock() { mtx_ptr->unlock(); }
    friend struct link_safe_ptrs;
    template<typename mutex_type> friend class std::lock_guard;
    //template<class... mutex_types> friend class std::lock_guard;    // C++17
public:
    template<typename... Args>
    safe_ptr(Args... args) : ptr(std::make_shared<T>(args...)), mtx_ptr(std::make_shared<mutex_t>()) {}

    auto_lock_t<x_lock_t> operator -> () { return auto_lock_t<x_lock_t>(ptr.get(), *mtx_ptr); }
    auto_lock_t<x_lock_t> operator * () { return auto_lock_t<x_lock_t>(ptr.get(), *mtx_ptr); }
    const auto_lock_t<s_lock_t> operator -> () const { return auto_lock_t<s_lock_t>(ptr.get(), *mtx_ptr); }
    const auto_lock_t<s_lock_t> operator * () const { return auto_lock_t<s_lock_t>(ptr.get(), *mtx_ptr); }
};

http://coliru.stacked-crooked.com/a/19a0a524c899a52e