LINUX.ORG.RU

Не возникнет ли гонка данных?

 


3

6

Суть в том, что чтение из одного блока данных происходит очень часто из разных потоков, но в определенный момент один(заранее заданный поток) может обновить данные, так как код используется в очень критичном месте и обновление данных происходит очень быстро, никакой блокировки с засыпанием быть не должно (mutex, shared_mutex). Написал свой велосипед:

Сама структура:

struct BufferData {
  ...
  volatile std::atomic<bool> m_remapFlag{false}; //флаг, если происходит запись
  volatile std::atomic<std::size_t> m_usageCounter{0}; //количество чтений
};

Блокировка/освобождение на чтение (блокировка на чтение не должно блокировать другое чтение):

BufferData *OGLBuffer::lock() {
  std::shared_ptr<BufferData> ptr;
  if (!m_data.expired()) {
    ptr = m_data.lock();
  } else
    throw std::runtime_error("Buffer page deleted");
  //Ждем пока обновляют данные
  while (ptr->m_remapFlag) {
    continue;
  }
  //Увеличиваем счетчик
  ptr->m_usageCounter++;
  if (!ptr->m_remapFlag) {
    //Если за это время не начали обновлять данные то возвращаем указатель
    return ptr.get();
  } else {
    //Иначе повторяем попытку
    unlock();
    return lock();
  }

//Метод освобождения довольно прост
void OGLBuffer::unlock() { m_data.lock()->m_usageCounter--; }

Теперь блокировка/освобождение на запись:

void OGLPage::lockBuffer(std::size_t const &id) {
  m_buffers[id]->m_remapFlag = true; //Ставим флаг на запись
  //Ждем конца чтений
  while (m_buffers[id]->m_usageCounter > 0) {
    continue;
  }
}

void OGLPage::unlockBuffer(std::size_t const &id) {
  //Чистим флаг
  m_buffers[id]->m_remapFlag = false;
}

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

★

Последнее исправление: maxis11 (всего исправлений: 2)

TSAN пробовал?

// Тред не читал

volatile std::atomic<bool>

Тут от volatile мало толку. Лучше использовать соответствующий std::memory_order для .store() и .load()

KennyMinigun ★★★★★
()
while (ptr->m_remapFlag) {
    continue;
}

Что мешает, сделать паралельно ещё один лок на запись после завершения этого цикла, но до инкремента?

pon4ik ★★★★★
()

volatile std::atomic

Сильно.

anonymous
()
Ответ на: комментарий от KennyMinigun

Я просто боялся что какое нибудь значение закешируется, но судя по докам, .load гарантированно прочтет, то что запрятано в .store (при cst, acq/rel). Сейчас исправлю.

maxis11 ★
() автор топика
  while (ptr->m_remapFlag) {
    continue;
  }


в разы хуже любых mutex.
std::this_thread::yield() используй хотя бы.

dib2 ★★★★★
()
Ответ на: комментарий от pon4ik

Да, rwlock создает bottleneck в этом месте. Тут нужен RWSpinLock (как уже ниже написали), только оптимизированный под один writer (который очень редко запускается).

maxis11 ★
() автор топика

Basic или Pascal пробовали?...

anonymous
()

Как уже советовали, включи TSAN и посмотри что он тебе скажет.

pftBest ★★★★
()

std::shared_ptr + std::atomic_load/std::atomic_store. Три строчки реализации, меньшее количество атомарных операций при чтении/записи, гарантируется, что запись не подвиснет. Минус: дёрганье new при записи, но если она редкая, то это не важно. </thread>

vzzo ★★★
()

Как уже писали выше:

  • volatile не нужен
  • std::thist_thread::yield() в циклах ожидания всегда даёт лучший результат(хотя это по моим наколенным тестам на linux, но не думаю что под оффтопиком ситуация отличается)
  • нужна rw-блокировка с активным ожиданием - не такая уж редкая ситуация, бери готовое

P. S.

if (!ptr->m_remapFlag) {
//Если за это время не начали обновлять данные то возвращаем указатель

А что будет если за это время уже обновили?

Deleted
()
Ответ на: комментарий от vzzo

std::atomic, к сожалению, не всегда гарантирует lock-free. Для std::shared_ptr есть даже заметка на cppreference:

These functions are typically implemented using mutexes, stored in a global hash table where the pointer value is used as the key.

Ну и как выше описал: mutex/shared_mutex не подходят.

maxis11 ★
() автор топика
Ответ на: комментарий от Deleted

А что будет если за это время уже обновили?

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

maxis11 ★
() автор топика

Как-то очень сложно ты все придумал. Наверняка, можно просто сделать атомарный указатель на данные. Когда их нужно поменять, ты просто создаешь их в новом месте (new Data()), инициализируешь как надо, а затем меняешь указатель (атомарный) это эти новые данные (сами данные не атомарные, доступ к ним синхронизируется через обновление атомарного указателя).

Только там приключится одна заморочка, свойственная lock-free алгоритмам в C++ - нужно будет озаботиться специализированным сборщиком мусора. Потому что возможен вариант, когда какой-то поток-читатель получил указатель на старые данные, затем поток писатель обновил указатель на новые данные, а первый поток-читатель все еще работает со старыми данными... Их нужно будет удалить не после обновления указателя, а когда все читатели старых данных закончат с ними работать (также возможна ситуация, когда кто-то работает со старыми данными, а какие-то потоки уже с новыми...).

anonymous
()
Ответ на: комментарий от maxis11

std::atomic, к сожалению, не всегда гарантирует lock-free. Для std::shared_ptr есть даже заметка на cppreference:

cmpxchg16 поддерживается любыми процессорами предназначенными для производительных рассчетов. Если же ты пытаешься запустить критичную к скорости работы программу на телефоне, то не нужно рассчитывать, что она будет быстро работать на процессоре рассчитанном на мобильность...

shared_ptr - это 2 указателя, т.е. 16 байт, будет работать без блокировок всегда (правда gcc7 генерит для него такой код, что обращение к атомарному shared_ptr отрабатывает тактов под 100, но без блокировки).

anonymous
()
Ответ на: комментарий от anonymous

Как-то очень сложно ты все придумал. Наверняка, можно просто сделать атомарный указатель на данные. Когда их нужно поменять, ты просто создаешь их в новом месте (new Data()), инициализируешь как надо, а затем меняешь указатель (атомарный) это эти новые данные (сами данные не атомарные, доступ к ним синхронизируется через обновление атомарного указателя).

Сейчас придёт kawaii_neko и будет тебя убеждать, что это не работает, данные тоже должны быть атомарными.

utf8nowhere ★★★★
()
Ответ на: комментарий от utf8nowhere

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

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

P.S. Lock-free запись и чтение указателя (атомарного std::shared_ptr) в этой задаче не факт что будут работать быстрее, чем работа через mutex.

anonymous
()
Ответ на: комментарий от anonymous

Ему же надо сделать достаточно сложную операцию: атомарно считать указатель и увеличить рефкаунт по этому указателю.

https://godbolt.org/g/EeBnk9: для test() генерирует вызовы к _Sp_locker: https://code.woboq.org/gcc/libstdc++-v3/src/c++11/shared_ptr.cc.html#_ZNSt10_...

vzzo ★★★
()
Ответ на: комментарий от vzzo

Я это тоже проверил, ток проще

std::shared_ptr<int> ptr;
  std::cout << std::boolalpha << std::atomic_is_lock_free(&ptr) << std::endl;

Результат был: false

maxis11 ★
() автор топика
Ответ на: комментарий от vzzo

Ему же надо сделать достаточно сложную операцию: атомарно считать указатель и увеличить рефкаунт по этому указателю.

При копировании shared_ptr std::shared_ptr<Data> new_one = std::atomic_load( &old_one ) ему нужно скопировать старый (16 байт) и увеличить счетчик ссылок. Но!!!! пока операция не завершится предыдущий shared_ptr не исчезнет, а потому счетчик ссылок до нуля никак не упадет, т.е. эта операция происходит как две атомарных: скопировать 16 байт, увеличить счетчик ссылок. Если же нужно обменять содержимое указателя std::atomic_exchange( &ptr, std::shared_ptr<Data>(new Data()) );, то все ограничивается обменом 16-ти байтными блоками.

Я также в курсе про Sp_locker::_Sp_locker. Насколько я понимаю, он появился в gcc7 из-за того, что там обнаружили, что в какой-то экзотической ситуации старый алгоритм не совсем удовлетворяет требованиям стандарта, в результате вместо генерации операции cmpxchg16... сделали вызов фукнций, причем из shared library и теперь атомарные операции с 16-ти байтными блоками стали дико медленными. Однако, этот Sp_locker ничего не делает (нет там блокировки) и в результате все работает как раньше без блокировок, только через разделяемые библиотеки и дико медленно (вместо 20-40 тактов на cmpxchg16 в случае когда нужная функция уже подгружена это займет 100+ тактов на вызов нескольких функций, которые ничего не делают, кроме того же cmpxchg16).

Пример работы: https://godbolt.org/g/KkEXFv

P.S. Я в курсе, что текущий синтаксис объявлен устаревшим (deprecated) в c++20 и заменен другим.

anonymous
()
Ответ на: комментарий от anonymous

Похоже, std::shared_ptr работают с блокировками. Но я так и не понял, почему.

anonymous
()
Ответ на: комментарий от anonymous

нужно будет озаботиться специализированным сборщиком мусора.

Да, я думал над этим, самым логичным будет подключить libcds, взять от туда GC, использовать hazard pointer для этого дела (они примерно так и работает как Вы описали). Я даже так и делаю в моем хобби проекте (concurrent graph based task system). Ток эта вещь пишется для работы, который до сих пор собирается под msvc2013 (там минимальная версия: 2015). Я примерно понял как это сделать можно (указатель на данные, атомарный счетчик читающих и флаг на то что данные обновлены, в деструкторе будет вычитаться из счетчика и идти проверка: если читающих осталось нуль и данные устарели - удаляем указатель), только надо составить бенчмарки на все четыре варианта (tbb::spin_rw_mutex, folly::RWSpinLock, мой вариант спинлока с доработками, замена указателя, как Вы описали) и выбрать самый подходящий из них.

maxis11 ★
() автор топика
Вы не можете добавлять комментарии в эту тему: топик перемещен в архив.