Указатели на опасность с четко определенными распределителями в C ++

Question

Я прочитал следующее примечание в главе 7 книги C ++ Concurrency in Action (стр. 194). Мой вопрос: есть ли в стандартной библиотеке какой-либо распределитель, для которого то, что мы делаем в указателях опасности , четко определено?

Использование таких указателей опасности зависит от того, что безопасно использовать значение указателя после удаления объекта, на который он ссылается. Это технически неопределенное поведение, если вы используете реализацию по умолчанию new и delete, поэтому вам нужно либо убедиться, что ваша реализация разрешает это, либо вам нужно использовать настраиваемый распределитель, который разрешает такое использование.

Здесь - это сообщение, относящееся к неопределенному / неопределенному поведению, о котором я говорю здесь. В приведенном выше примечании имеется следующий фрагмент кода:

std::shared_ptr<T> pop() {
  std::atomic<void*>& hp=get_hazard_pointer_for_current_thread();
  node* old_head=head.load();
  node* temp;
  do {
    temp=old_head;         // Here we are reading (not dereferencing) a pointer that might have been deleted already
    hp.store(old_head);    // And here
    old_head=head.load();
  } while(old_head!=temp); // And here
  // ...
}

На самом деле, я бы сказал, что та же проблема существует, когда используется подсчет ссылок вместо указателей опасности (в книге нет такого Запрос). Ниже показано, как помещать элемент в стек с помощью подсчета ссылок (стр. 208). Вся цель while-l oop в этом коде - убедиться, что значение new_node.ptr->next допустимо, и это включает чтение указателя, который, возможно, уже был удален.

void push(T const& data) {
  counted_node_ptr new_node;
  new_node.ptr=new node(data);
  new_node.external_count=1;
  new_node.ptr->next=head.load(std::memory_order_relaxed)
  while(!head.compare_exchange_weak(
                new_node.ptr->next,
                new_node,
                std::memory_order_release,
                std::memory_order_relaxed)); }

Answer 1

Это так называемая «проблема восстановления памяти» - объект не должен быть удален, пока какой-то поток все еще может содержать ссылку на него и, таким образом, все еще может обращаться к нему. Если поток хочет «освободить» какой-либо объект, он обычно не вызывает delete напрямую, а вызывает некоторую retire функцию, которая хранит указатель и откладывает восстановление до более позднего времени, когда это будет безопасно (например, в случае указателей опасности, пока поток держит HP для этого объекта). Поскольку сканирование указателей опасности всех потоков довольно дорогое, это делается только после того, как количество удаленных объектов достигает некоторого порога. Таким образом, абсолютно возможно реализовать указатели опасности с четко определенным поведением.

В коде вашей операции pop отсутствуют некоторые важные детали - вы собираетесь заменить head, но что вы делаете со старым значением? Как его вернуть? Вы просто вызываете delete?

Arch D. Робисон предложил N3712: Дизайн на основе политик для безопасного уничтожения в параллельных контейнерах в качестве универсального c интерфейса для схем восстановления памяти для стандарта C ++. Общая идея состоит в том, что у вас есть концепция guard_ptr, которая содержит безопасную ссылку на объект (похожую на share_ptr). Пока какой-либо поток хранит такой guard_ptr для объекта, этот объект нельзя удалить, и вы можете получить доступ к объекту только после получения такого guard_ptr. Если вы хотите вернуть объект, вы просто звоните guard_ptr::retire. Затем объект будет в конечном итоге удален базовой реализацией, как только он станет безопасным.

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

Что касается вашей операции pu sh, которая использует подсчет ссылок - это совершенно безопасно. Пока l oop пытается обновить head на new_node, где new_node.ptr->next - ожидаемое значение. Если CAS выходит из строя, текущее значение сохраняется в new_node.ptr->next, но это нормально, потому что, поскольку CAS вышел из строя, new_node не отображается, поэтому никакой другой поток не может получить к нему доступ. Как вы думаете, где мы читаем указатель, который, возможно, уже был удален.

Если вам интересен этот топ c Я могу отослать вас к моей диссертации Эффективное восстановление памяти для данных без блокировки структуры в C ++ . Он не только обеспечивает общее обсуждение большого количества схем рекультивации, но также очень подробно описывает мою собственную реализацию различных схем рекультивации, основанную на адаптированной версии ранее упомянутого интерфейса, предложенного Arch D. Robison.

Основываясь на моей работе над этой диссертацией, я создал библиотеку с открытым исходным кодом, которая обеспечивает реализации различных схем восстановления (включая указатели опасности и подсчет ссылок без блокировки) и параллельных структур данных: xenium

Обновление
Что касается вашего утверждения о том, что «чтение значения (а не разыменование) уже освобожденного указателя обычно не определено» - у меня нет этой книги, поэтому я не уверен, что автор относится к. И я не знаю, почему authro в упомянутом ответе SO утверждает, что «Использование» включает «копирование значения». Стандарт C ++ 17 говорит о недопустимых значениях указателя следующее:

Косвенное обращение через недопустимое значение указателя и передача недопустимого значения указателя в функцию освобождения имеют неопределенное поведение. Любое другое использование недопустимого значения указателя имеет поведение, определяемое реализацией.

И в качестве примечания:

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

1052 Однако мне неизвестна какая-либо текущая архитектура или компилятор, на которых чтение недопустимого значения указателя могло бы вызвать такую ​​ошибку.

Концепция pointer_safety была добавлена ​​в C ++ 11 как часть интерфейса сборщика мусора. (см. предложение N2670: минимальная поддержка сборки мусора и обнаружения утечек на основе достижимости ). В книге Бьярна Страуструпа «Язык программирования C ++» (4-е издание) о значениях pointer_safety говорится следующее:

• смягчено: Безопасно выведено и небезопасно указатели считаются эквивалентными. Соберите каждый объект, для которого нет безопасного производного или отслеживаемого указателя.
• предпочтительно: Подобно расслабленному, но сборщик мусора может работать как детектор утечек и / или детектор разыменование «плохих указателей».
• strict: Безопасно выведенные и небезопасные указатели могут обрабатываться по-разному; то есть может быть запущен сборщик мусора, который будет игнорировать указатели, которые не были получены безопасным образом.

Таким образом, pointer_safety имеет значение только тогда, когда вы используете сборщик мусора.