SEGFAULT при использовании shared_ptr
Я пытаюсь реализовать Ленивый параллельный набор на основе списка в C ++ с помощью shared_ptr, Я считаю, что unreachable nodes будет автоматически освобожден последним shared_ptr, Насколько я понимаю, операция увеличения и уменьшения на shared_ptr's reference count атомно. Что означает только последний shared_ptr со ссылкой на узел следует вызвать удалить / бесплатно для этого узла. Я запустил программу для несколько потоков, но моя программа вылетает с ошибкой double free called или просто Ошибка сегментации (SIGSEGV). Я не понимаю, как это возможно. Ниже приведен мой код для реализации с именами методов, обозначающими их предполагаемую операцию.
#include<thread>
#include<iostream>
#include<mutex>
#include<climits>
using namespace std;
class Thread
{
public:
std::thread t;
};
int n=50,ki=100,kd=100,kc=100;`/*no of threads, no of inserts,deletes & searches*/`class Node
{
public:
int key;
shared_ptr<Node> next;
bool marked;
std::mutex nodeLock;
Node() {
key=0;
next = nullptr;
marked = false;
}
Node(int k) {
key = k;
next = nullptr;
marked = false;
}
void lock() {
nodeLock.lock();
}
void unlock() {
nodeLock.unlock();
}
~Node()
{
}
};
class List {
shared_ptr<Node> head;
shared_ptr<Node> tail;
public:
bool validate(shared_ptr<Node> pred, shared_ptr<Node> curr) {
return !(pred->marked) && !(curr->marked) && ((pred->next) == curr);
}
List() {
head=make_shared<Node>(INT_MIN);
tail=make_shared<Node>(INT_MAX);
head->next=tail;
}
bool add(int key)
{
while(true)
{
/*shared_ptr<Node> pred = head;
shared_ptr<Node> curr = pred->next;*/
auto pred = head;
auto curr = pred->next;
while (key>(curr->key))
{
pred = curr;
curr = curr->next;
}
pred->lock();
curr->lock();
if (validate(pred,curr))
{
if (curr->key == key)
{
curr->unlock();
pred->unlock();
return false;
}
else
{
shared_ptr<Node> newNode(new Node(key));
//auto newNode = make_shared<Node>(key);
//shared_ptr<Node> newNode = make_shared<Node>(key);
newNode->next = curr;
pred->next = newNode;
curr->unlock();
pred->unlock();
return true;
}
}
curr->unlock();
pred->unlock();
}
}
bool remove(int key)
{
while(true)
{
/*shared_ptr<Node> pred = head;
shared_ptr<Node> curr = pred->next;*/
auto pred = head;
auto curr = pred->next;
while (key>(curr->key))
{
pred = curr;
curr = curr->next;
}
pred->lock();
curr->lock();
if (validate(pred,curr))
{
if (curr->key != key)
{
curr->unlock();
pred->unlock();
return false;
}
else
{
curr->marked = true;
pred->next = curr->next;
curr->unlock();
pred->unlock();
return true;
}
}
curr->unlock();
pred->unlock();
}
}
bool contains(int key) {
//shared_ptr<Node> curr = head->next;
auto curr = head->next;
while (key>(curr->key)) {
curr = curr->next;
}
return curr->key == key && !curr->marked;
}
}list;
void test(int curr)
{
bool test;
int time;
int val, choice;
int total,k=0;
total=ki+kd+kc;
int i=0,d=0,c=0;
while(k<total)
{
choice = (rand()%3)+1;
if(choice==1)
{
if(i<ki)
{
val = (rand()%99)+1;
test = list.add(val);
i++;
k++;
}
}
else if(choice==2)
{
if(d<kd)
{
val = (rand()%99)+1;
test = list.remove(val);
d++;
k++;
}
}
else if(choice==3)
{
if(c<kc)
{
val = (rand()%99)+1;
test = list.contains(val);
c++;
k++;
}
}
}
}
int main()
{
int i;
vector<Thread>thr(n);
for(i=0;i<n;i++)
{
thr[i].t = thread(test,i+1);
}
for(i=0;i<n;i++)
{
thr[i].t.join();
}
return 0;
}
Я не могу понять, что не так с приведенным выше кодом. Ошибки различаются каждый раз, некоторые из которых просто SEGFAULTS или же
pure virtual method called
terminate called without an active exception
Aborted (core dumped)
Не могли бы вы указать, что я делаю неправильно в приведенном выше коде? И как исправить эту ошибку?
РЕДАКТИРОВАТЬ: Добавил очень сырой test function который случайным образом называет три list methods, Кроме того, количество потоков и число каждой операции объявляются глобально. Грубое программирование, но оно воссоздает Segfault.
Решение
Проблема в том, что вы не используете атомарные операции сохранения и загрузки для вашего shared_ptrs.
Это правда, что счетчик ссылок в блоке управления (к которому каждый shared_ptr участие в владении конкретным общим объектом имеет указатель на) shared_ptr однако, атомные данные членов shared_ptr сам по себе не.
Таким образом, безопасно иметь несколько потоков, каждый со своим shared_ptr к общему объекту, но нельзя сохранить, чтобы несколько потоков обращались к одному shared_ptr как только один из них использует неконстантную функцию-член, что вы и делаете при переназначении next указатель.
Иллюстрируя проблему
Давайте посмотрим на (упрощенный и предварительно проверенный) конструктор копирования libstdc ++ shared_ptr реализация:
shared_ptr(const shared_ptr& rhs)
: m_ptr(rhs.m_ptr),
m_refcount(rhs.m_refcount)
{ }
Вот m_ptr это просто необработанный указатель на общий объект, и m_refcount это класс, который выполняет подсчет ссылок, а также обрабатывает возможное удаление объекта m_ptr указывает на.
Только один пример того, что может пойти не так: предположим, что в настоящее время поток пытается выяснить, содержится ли определенный ключ в списке. Начинается с копирования-инициализации auto curr = head->next в List::contains, Сразу после того, как удалось инициализировать curr.m_ptr планировщик ОС решает, что этот поток должен приостановиться, и планирует другой поток.
Этот другой поток удаляет преемника head, Так как реф подсчет head->next по-прежнему равен 1 (в конце концов, ref-count head->next еще не был изменен потоком 1), когда второй поток завершил удаление узла, он удаляется.
Затем, через некоторое время, продолжается первый поток. Завершает инициализацию curr, но с тех пор m_ptr был уже инициализирован до того, как поток 2 начал удаление, он все еще указывает на удаленный узел. При попытке сравнить key > curr->key поток 1 будет обращаться к недействительной памяти.
Использование std :: atomic_load и std :: atomic_store для предотвращения проблемы
std::atomic_load а также std::atomic_store предотвратить возникновение проблемы, заблокировав мьютекс перед вызовом оператора копирования / копирования-присвоения оператора shared_ptr это передается указателем. Если все читает и пишет в shared_ptrS, которые являются общими для нескольких потоков, проходят через std::atomic_load/std::atomic_store соответственно никогда не может случиться так, что один поток только изменил m_ptr но не счетчик ссылок в тот момент, когда другой поток начинает читать или изменять то же самое shared_ptr,
С необходимыми атомными нагрузками и хранит List Функции-члены должны выглядеть следующим образом:
bool validate(Node const& pred, Node const& curr) {
return !(pred.marked) && !(curr.marked) &&
(std::atomic_load(&pred.next).get() == &curr);
}
bool add(int key) {
while (true) {
auto pred = std::atomic_load(&head);
auto curr = std::atomic_load(&pred->next);
while (key > (curr->key)) {
pred = std::move(curr);
curr = std::atomic_load(&pred->next);
}
std::scoped_lock lock{pred->nodeLock, curr->nodeLock};
if (validate(*pred, *curr)) {
if (curr->key == key) {
return false;
} else {
auto new_node = std::make_shared<Node>(key);
new_node->next = std::move(curr);
std::atomic_store(&pred->next, std::move(new_node));
return true;
}
}
}
}
bool remove(int key) {
while (true) {
auto pred = std::atomic_load(&head);
auto curr = std::atomic_load(&pred->next);
while (key > (curr->key)) {
pred = std::move(curr);
curr = std::atomic_load(&pred->next);
}
std::scoped_lock lock{pred->nodeLock, curr->nodeLock};
if (validate(*pred, *curr)) {
if (curr->key != key) {
return false;
} else {
curr->marked = true;
std::atomic_store(&pred->next, std::atomic_load(&curr->next));
return true;
}
}
}
}
bool contains(int key) {
auto curr = std::atomic_load(&head->next);
while (key > (curr->key)) {
curr = std::atomic_load(&curr->next);
}
return curr->key == key && !curr->marked;
}
Кроме того, вы должны также сделать Node::marked std::atomic_bool,
Другие решения
Других решений пока нет …
detector