Динамический поиск потенциальных взаимоблокировок

[Suvitruf]

<irony>Радует обилие комментариев в коде</irony>

[eshirshov]

спасибо. промышленный код. теперь лучше?

[nickolaym]

А не слишком ли дорого задействовать BGL для отслеживания циклов?
Критические секции ведь не зря называются критическими. А вмешательство во временную диаграмму может искажать картинку.

Тем более, граф там простейший: двудольный список.
Если мьютексы не создаются на лету, то даже ABA-проблемы не возникнет, как мне кажется, так что несложно lock-free реализацию сделать.
Если создаются, — то lock-based. Операции почти мгновенные, можно себе позволить; а глобальный мьютекс всегда лочится самым последним и очень ненадолго.

Я когда-то такой велосипед для себя делал, без BGL, но с кучей возможностей для отладки: там и имена файлов и функций фиксировались, и точки прерывания были — чтоб можно было в момент дедлока встать и проследить цепочку прямо по-живому, и замена дедлоков на ливлоки, чтобы дебаггер не плакался, что все потоки сидят в ядре.

[eshirshov]

— да, дороговато. Но это не имеет почти никакого значения. Нужен только однократный тестовый прогон. Сложность графа получаемых зависимостей заранее, не зная проекта досконально, предсказать нельзя. Самописный граф тоже имеет право на существование.

— Мне кажется возможно Вы ввелись в заблуждение: Здесь не realtime ловля моментов deadlock, а поиск ситуаций которые могут к нему приводить.

[nickolaym]

А, понял!
То есть, мы делаем предположение, что, вне зависимости от временной диаграммы, путь обхода одним потоком всех его ресурсов выглядит одинаково.
И на основании этого, построив такие пути для всех потоков, выясняем, могут ли в принципе возникать дедлоки.

Это предположение крайне важно.
Во-первых, оно может давать ложные срабатывания — там, где из-за каких-то обстоятельств временная диаграмма в принципе не может сложиться так, что возникнет дедлок. Но, как говорится, бережёного бог бережёт.
Пример:

void threadA() {
  ResetEvent(flag); // это асимметричная зависимость: очередь сообщений, сокет, условная переменная и т.п.
  Enter(mutex1);
  Enter(mutex2);
  Leave(mutex2);
  Leave(mutex1);
  SetEvent(flag);
}

void threadB() {
  WaitEvent(flag);
  Enter(mutex2);
  Enter(mutex1);
  Leave(mutex1);
  Leave(mutex2);
}

Как мы видим, два потока только делают вид, что готовы схватиться в клинче.

Во-вторых, оно может не давать полноценное покрытие кода — если тот чувствителен ко временной диаграмме.

volatile bool ready; // да, я знаю про неэффективность volatile, но это же псевдокод.
Some data;

void threadA() {
  while(!ready) {
    // возможно, в тестовом прогоне мы сюда просто никогда не попадём
    DoSomeIdleWork(); // с мьютексами и прочим добром
    Sleep(0);
  }
  Consume(data); // пусть там всё защищено и аккуратно
}

void threadB() {
  Sleep(rand());
  Produce(data);
  ready = true;
  if(rand()) // ещё один способ не попасть в сложное положение
    DoAnotherIdleWork(); // чтобы заклинило с DoSomeIdleWork
}

Но опять же, если проблема существует хоть на каком-то варианте развития событий, её там следует убрать, от греха подальше.

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

Резюмирую:
— идея интересная и правильная
— но не является серебряной пулей, и хорошо бы ещё и в реальном времени ловить дедлоки

А, кстати!
Дедлоки возникают ведь не только на мьютексах, но и взаимном ожидании несимметричных объектов (очередей сообщений, семафоров в режиме producer-consumer), и на всяких RPC.
В принципе, метод их ловли примерно такой же: строится граф зависимостей…
Если вашу библиотеку можно дополнить поддержкой таких явлений, это будет вообще здорово.

[eshirshov]

Полностью с Вами согласен.
Перефразируя: каждый проблемный код несчастен по своему.
Инвидуальный подход никто не отменял.

[petropavel]

в MariaDB такое уже несколько лет как работает. Только в debug-сборке, конечно. И на С. А так — то же самое, строится граф, какой мьютекс перед каким берется, если получается цикл — бьем тревогу. Помогало не раз.

Но это, конечно, не «поиск дедлоков», а поиск нарушений в порядке взятия мьютексов.