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
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.