std :: list thread_safety

1. да, нужна блокировка (какая-то синхронизация).
2. указатели на элементы std::list становятся недействительными, только если тот же элемент удален из списка. Поскольку ваш код никогда ничего не удаляет из списка, ваши указатели в безопасности.

По конкретной причине, по которой вам нужна блокировка, учтите, например, что list::push_back разрешено делать следующее в таком порядке:

1. выделить новый узел,
2. установить "следующий" указатель конца списка на новый узел,
3. установить "следующий" указатель нового узла в ноль (или какой-либо другой маркер конца списка),
4. установить "предыдущий" указатель нового узла на предыдущий хвост,
5. установить собственный указатель на хвост списка для нового узла.

Если ваш поток чтения находится между 2 и 3, он перейдет от предыдущего хвоста к новому узлу, а затем попытается следовать неинициализированному указателю. Бум.

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

Ваш код должен быть правильным, если вы представляете, что разные потоки работают на разных планетах, каждый со своей собственной копией памяти вашей программы, и передают изменения друг другу (а), когда вы используете объект синхронизации (или атомарную переменную в C ++ 11 ), плюс (b), когда вы не используете объект синхронизации, но передача определенного частичного изменения нарушит ваш код (например, одна половина объекта из двух слов или в этом случае одна из двух записей указателя, которые вам нужно выполнить в определенном порядке). Иногда эта модель более консервативна, чем это строго необходимо, и приводит к более медленному коду. Но менее консервативная модель полагается на специфические для реализации детали системы потоков и модели памяти.

Я хотел узнать, являются ли списки потокобезопасными в целом, поэтому я спросил и нашел эту ветку. Я пришел к выводу, что в текущей реализации std :: list в gcc libstdc ++ вы можете безопасно изменять список в одном потоке и произвольно перебирать списки одновременно, но не смейте два потока изменяют один и тот же список (без синхронизации). Более того, от этого поведения не следует зависеть. Я разорвал код библиотеки, чтобы более подробно указать на проблемы. Я надеюсь, что это будет полезно.

Сначала давайте начнем с общего вопроса о безопасности потоков для списков. Я подумал, что было бы неплохо «доказать», что списки небезопасны, на примере, поэтому я собрал следующий код вместе.

#include <iostream>
#include <list>
#include <mutex>
#include <thread>

using namespace std;

list<int> unsafe_list;

class : public list<int> {
  mutex m;
  public:
  void push_back(int i) {
    lock_guard<mutex> lock{m};
    list<int>::push_back(i);
  }
} safe_list;

template <typename List> void push(List &l) {
  for (auto i = 0; i < 10000; ++i)
    l.push_back(0);
}

void report_size(const list<int> &li, char const *name) {
  size_t count{};
  for (auto && i : li) ++count;
  cout << name << endl;
  cout << "size() == " << li.size() << endl;
  cout << "count  == " << count << endl;
}

int main() {
  auto unsafe = []() { push(unsafe_list); };
  auto safe = []() { push(safe_list); };
  thread pool[]{
      thread{unsafe}, thread{unsafe}, thread{unsafe},
      thread{safe},   thread{safe},   thread{safe},
  };
  for (auto &&t : pool)
    t.join();
  report_size(unsafe_list, "unsafe_list");
  report_size(safe_list, "safe_list");
}

Я получил следующий результат:

unsafe_list
size() == 19559
count  == 390
safe_list
size() == 30000
count  == 30000

Ой. Это означает, что вряд ли какие-либо элементы, которые я выдвинул, попали в список. Но это еще хуже! Он не только не имеет нужного количества элементов, он думает, что имеет другое число, чем есть на самом деле, и это число тоже не то, что я хочу! Хотя это означает, что почти наверняка есть утечка памяти, когда я запустил ее с помощью valgrind, все операции завершились успешно. Я слышал, что valgrind и другие инструменты могут быть менее чем полезными при попытке справиться с параллелизмом, я думаю, это свидетельство этого.

Сначала я попытался вставить 10 элементов за раз, но ничего подозрительного не произошло. Я подумал, что ему удалось продвинуть все в пределах своего временного интервала, поэтому я увеличил его до 10000 и получил желаемые результаты. Просто примечание для всех, кто пытается продублировать эксперимент, он может работать или нет, в зависимости от конфигурации системы, алгоритма планирования и т. Д.

Учитывая природу связанных списков, я ожидал, что в результате такого эксперимента будет получен сегментарный или иным образом поврежденный список. Сегмент-сбой был бы милостью, если бы он был причиной какой-то ошибки, которую вы искали.

Что, черт возьми, происходит

Здесь я точно объясню, что произошло и почему (или, по крайней мере, дам чрезвычайно правдоподобное объяснение). Если вы не знакомы с проблемами параллелизма, считайте это вступлением. Если вы эксперт, скажите, пожалуйста, в чем я ошибаюсь или не до конца.

Мне было любопытно, поэтому я просто посмотрел на реализацию gcc libstdc ++. Чтобы объяснить наблюдаемое поведение, необходимо краткое объяснение того, как работает список.

Детали реализации

В базовой структуре или алгоритме нет ничего интересного или странного, но необходимо упомянуть различные детали реализации C ++. Прежде всего, все узлы списка являются производными от общего базового класса, который хранит только два указателя. Таким образом, все поведение списка инкапсулируется. Фактические узлы, кроме производных от базы, представляют собой структуры с нестатическим элементом данных __gnu_cxx::__aligned_membuf<_Tp> _M_storage. Эти узлы знают value_type в списке и являются производными от allocator_type отскока к _List_node<_Tp>. Назначение этих узлов - получить и освободить хранилище для списка, а также использовать свою базу для поддержания структуры данных. (Я рекомендую этот документ для объяснения того, как типы выводятся из итераторов, он может пролить свет на то, почему определенные вещи реализованы именно так, как они есть http://www.stroustrup.com/SCARY.pdf. Для мазохистов посмотрите, как этот мастер объясняет красивый кошмар, которым являются распределители C ++ https://www.youtube.com/watch?v=YkiYOP3d64E). Затем список обрабатывает построение и разрушение и предоставляет интерфейс пользователю библиотеки, бла-бла-бла.

Основное преимущество наличия общего (не знающего типов) базового класса для узлов заключается в том, что вы можете связывать произвольные узлы вместе. Это не очень помогает, если делается безрассудно, но они используют это контролируемым образом. «Хвостовой узел» относится не к типу value_type, а к типу size_t. Хвостовой узел содержит размер списка! (Мне потребовалось несколько минут, чтобы разобраться, что происходит, но это было весело, так что ничего страшного. Основное преимущество этого состоит в том, что каждый существующий список может иметь хвостовой узел одного и того же типа, что сокращает дублирование кода. для обработки хвостового узла, а списку нужен только один нестатический член данных, чтобы делать то, что ему нужно).

Итак, когда я помещаю узел в конец списка, итератор end() передается следующей функции:

 template<typename... _Args>
   void
   _M_insert(iterator __position, _Args&&... __args)
   {
 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
 __tmp->_M_hook(__position._M_node);
 this->_M_inc_size(1);
   }

_M_create_node() в конечном итоге использует правильный распределитель для получения хранилища для узла, а затем пытается создать там элемент с предоставленными аргументами. «Точка» функции _M_hook() состоит в том, чтобы указывать указатели на указатели, на которые они должны указывать, и она указана здесь:

void
_List_node_base::
_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT
{
  this->_M_next = __position;
  this->_M_prev = __position->_M_prev;
  __position->_M_prev->_M_next = this;
  __position->_M_prev = this;
}

Порядок, в котором манипулируют указателями, важен. Это причина, по которой я утверждаю, что вы можете выполнять итерацию, одновременно управляя списком. Подробнее об этом позже. Затем размер корректируется:

void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }

Как я уже сказал, в списке есть хвостовой узел типа size_t, поэтому, как вы можете догадаться, _M_impl._M_node._M_valptr() извлекает указатель на это число, а затем += набирает нужное количество.

Наблюдаемое поведение

Итак, что происходит? Потоки вступают в гонку данных (https://en.cppreference.com/w/cpp/language/memory_model) в функциях _M_hook() и _M_inc_size(). Я не могу найти красивую картинку в Интернете, поэтому допустим, что T - это хвост, B - "спина", и мы хотим отодвинуть 1 назад. То есть у нас есть список (фрагмент) B <-> T, а мы хотим B <-> 1 <-> T. В конце концов, 1 вызывает _M_hook на T, а затем происходит следующее:

1. 1 указывает на T
2. 1 указывает назад на B
3. B указывает на 1
4. T указывает назад на 1

Таким образом, ни одно местоположение никогда не «забывается». Теперь предположим, что 1 и 2 возвращаются в разные потоки одного и того же списка. Вполне вероятно, что шаги (1) и (2) выполняются для 1, затем 2 полностью отбрасывается, а затем (1) должен завершиться. Что происходит в этом случае? У нас есть список B <-> 2 <-> T, но 1 указывает на B и T, поэтому, когда их указатели настроены, список выглядит как B <-> 1 <-> T, и это сын утечки памяти.

Что касается итерации, не имеет значения, двигаетесь ли вы вперед или назад, вы всегда будете увеличивать список правильно. Однако такое поведение не, по-видимому, гарантируется стандартом, поэтому, если коды зависят от этого поведения, это ненадежно.

А как насчет размера ???

Хорошо, это похоже на параллелизм 101, старая история, вероятно, много раз рассказывалась лучше, я надеюсь, что хотя бы стоит посмотреть код библиотеки. Вопрос размера, я думаю, немного более интересен, и я, конечно, кое-что узнал, разобравшись в нем.

По сути, поскольку увеличиваемое значение не является «локальной» переменной, его значение должно быть считано в регистр, к этому значению добавляется единица, а затем это значение сохраняется обратно в переменную. Давайте посмотрим на некоторую сборку (моя сборочная игра слабая, пожалуйста, не будьте любезны, если у вас есть исправление). Рассмотрим следующую программу:

int i{};
int main() {
  ++i;
}

Когда я запускаю objdump -D для объекта, я получаю:

Disassembly of section .text:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   8b 05 00 00 00 00       mov    0x0(%rip),%eax        # a <main+0xa>
   a:   83 c0 01                add    $0x1,%eax
   d:   89 05 00 00 00 00       mov    %eax,0x0(%rip)        # 13 <main+0x13>
  13:   b8 00 00 00 00          mov    $0x0,%eax
  18:   5d                      pop    %rbp
  19:   c3                      retq   

4: перемещает значение i в регистр eax. 0x1 добавляется к eax, затем eax перемещается обратно в i. Итак, какое это имеет отношение к гонкам данных? Взглянем еще раз на функцию, которая обновляет размер списка:

void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; }

Вполне вероятно, что текущий размер списка загружается в регистр, а затем другой поток, работающий с этим списком, выполняет нашу операцию. Итак, у нас есть старое значение списка, хранящееся в регистре, но мы должны сохранить это состояние и передать управление кому-то другому. Возможно, они успешно добавили элемент в список и обновили размер, а затем вернули нам контроль. Мы восстанавливаем свое состояние, но наше состояние больше не действует! У нас есть старый размер списка, который мы затем увеличиваем и значение которого мы сохраняем обратно в память, забывая об операции, выполненной другим потоком.

Последняя вещь

Как я упоминал ранее, в приведенной выше программе задействовано "местонахождение" i. Важность этого можно увидеть в следующем:

int main() {
  int i{};
  ++i;
}

Disassembly of section .text:

0000000000000000 <main>:
   0:   55                      push   %rbp
   1:   48 89 e5                mov    %rsp,%rbp
   4:   c7 45 fc 00 00 00 00    movl   $0x0,-0x4(%rbp)
   b:   83 45 fc 01             addl   $0x1,-0x4(%rbp)
   f:   b8 00 00 00 00          mov    $0x0,%eax
  14:   5d                      pop    %rbp
  15:   c3                      retq   

Здесь можно увидеть, что никакое значение не сохраняется в регистре, и никакой регистр не помещается в какую-либо переменную. К сожалению, насколько я могу судить, это не лучший способ избежать проблем с параллелизмом, поскольку несколько потоков, работающих с одной и той же переменной, обязательно должны будут работать с ней через доступ к памяти, а не только через регистры. Я быстро выхожу из своей лиги здесь, но я почти уверен, что это так. Лучше всего использовать atomic<int>, но эта чертова штука уже слишком длинная.