LINUX.ORG.RU

Найти race condition

 , , , ,


0

3

Только что случившийся со мной случай.

Есть некий объект, упрощённое описание:

typedef struct {
  int status;
  int status2;
  void *data;
  rwlock lock1;
  rwlock lock2;
}
Предполагается, что разрешённые его состояния такие:
(1) status==0, status2==0, data==NULL
(2) status==0, status2==0, data!=NULL
(3) status!=0, status2==0, data==NULL
(4) status!=0, status2 [1..3], data==NULL
(5) status==0, status2==4, data!=NULL

Переходы между состояниями такие:

1->2, 1->3, 1->4, 4->5 делаются под write-lock1'ом

5->2 без write-lock1'а

внутри состояния 4 может меняться status2 - без write-lock1'а

status2 меняется между 0 и 4, а так же между 1-2-3 без write-lock1'а, потому что от этих изменений не зависит поведение остальных частей кода (интересующихся status'ом и data), а ещё у status2 есть lock2, который защищает от race между разными его переключалками (то есть именно тем кодом, чья логика завязана именно на него), тут он для упрощения не показан.

И есть ещё один тред, который эти поля иногда читает (использует) и заодно проверяет на корректность структуру (люблю рассовывать ассерты по всем подходящим местам, если оно не критично по времени). В частности, там есть такой код:

READ_LOCK(obj->lock1);
if(obj->status!=0) {
  .....
} else {
  assert(!obj->status2 || obj->status2==4 && obj->data);
  ...
}
READ_UNLOCK(obj->lock1);

Так вот, этот ассерт иногда падал. Кто угадает в чём причина?

Для справки: rwlock это примерно то же самое, что мютекс, но у него два вида блокировок, строгая - на запись, ей может владеть только один тред, и нестрогая - на чтение, ей может владеть одновременно сколько угодно тредов, при условии что никто не заблокировал на запись.

★★★★★

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

Ответ на: комментарий от SkyMaverick

Ну да, это проверка что объект либо в корректном состоянии #1 или #2 (status2==0) либо в корректном состоянии #5 (status2==4 && data!=NULL). Поскольку #3 и #4 уйдут в другую ветку if'а выше.

firkax ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

Ну, сомневаюсь: чтение/запись int-а или указателя, выровненного компилятором до правильной границы. Но даже если б была неатомарна, не вижу как оно могло бы повлиять. А неатомарность между разными полями защищена с помощью lock1 (чтение где ассерт завёрнуто в read-lock1, а все «коллективные» переключения - в write-lock1).

firkax ★★★★★
() автор топика
Последнее исправление: firkax (всего исправлений: 1)

А valgrind ничего не говорит?

Я тоже, помню, искал что-то подобное, а потом оказалось, что я на байт обсчитался и затирал переменную, лежащую ровно за структурой, из другого потока. Lock-и на это не влияют никак.

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

Valgrind-ом я если честно никогда не пользовался. Но нет, тут дело не в битье памяти, а именно честный race. Я наверно не очень обозначил суть ситуации. Проблему я уже решил, но итог оказался настолько для меня неожиданным (хотя на мой взгляд оно было полностью предсказуемо и я должен был сразу понять в чём дело, но без отладочных мероприятий не вышло, поэтому такой тэг последний), что я решил поделиться этим в качестве интересного примера, вдруг кому тоже полезно будет.

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

Ну на вскидку, вот здесь:

status2 меняется между 0 и 4, а так же между 1-2-3 без write-lock1’а,

ты ничего не сказал, что там при этом с data. И вообще какой-то бардак: status2 это часть состояния (1)-(5). Если ты без write-lock1 можешь поменять status2 из 0 в 4, и при этом status == 0, то ты считай выполнил полу-недо-переход из (1) в (5): полу-недо- потому что data осталось null. Это называется «дооптимизироваться до мышей». :) Впилил бы spinlock на любые операции со структурой (пофиг что там только exclusive т.е. write lock, зато он копеечный). У меня ассоциация с SQL: я всегда везде выставляю transaction isolation = serializable и сплю спокойно.

Короче, главный косяк тут – это неряшливое обращение с автоматом состояний. Пофиг, простое у тебя состояние или составное; изволь менять его атомарно.

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

Так вот, этот ассерт иногда падал. Кто угадает в чём причина?

что означит «падал»? срабатывал assert или падало типа segmentation fault.

опять же есть подозрение на оптимизацию типа взятия поля на регистр. я б не осмелился мультитредить без явных volatile.

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

Сказал выше, где состояния расписал - если меняется что-то кроме status2 то включается write-lock1.

Если ты без write-lock1 можешь поменять status2 из 0 в 4, и при этом status == 0, то ты считай выполнил полу-недо-переход из (1) в (5): полу-недо- потому что data осталось null.

Не, ну это совсем плохо было бы. В явную нарушения консистентности нигде не происходит. Все переключения только между указанными состояниями. То есть из (1) в (5) нельзя никак без write-lock1 и data должно поменяться.

Это называется «дооптимизироваться до мышей».

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

firkax ★★★★★
() автор топика
Последнее исправление: firkax (всего исправлений: 1)

насколько совместны след утверждения:

5->2 без write-lock1'а
assert(!obj->status2 || obj->status2==4 && obj->data);

по человечьи это:

assert(obj->status2==0 || obj->status2==4 && obj->data);

переход 5->2 это изменение status2 с 4 на 0. вот если он произошел после невыполнения первого условия (то, что перед || ), невыполнятся оба условия и будет ассерт…. но это если компилятор не взял на регистр status2… короче это место точно непонятное.

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от alysnix

Да :) Так и было, а я почему-то без сначала отладчика, потом отладочных логов, потом отладочных логов с запоминанием обоих status2 - не догадался что происходит. Вот таких, вместо ассерта:

if(!(e1=obj->status2) || (e2=obj->status2)==4 && obj->data)) {
  log ... e1 e2
  exit(-1)
}
Ковыряние в coredump-е выдавало просто status==0 status2==0 data!=NULL, ну и я думал «вот, другой поток просто успел всё доделать пока assert выводил ошибку в stderr, потому данные на момент ассерта я не увижу».

Но удивляет вот что: сравнение сначала с нулём, а затем с четвёркой - это почти соседние ассемблерные инструкции получаются. Интуитивно кажется, что вероятность между ними вклиниться status2=0; исчезающе мала, однако на практике оно весьма себя проявляет. Конечно, даже если бы вероятность и правда была незаметной, это был бы совсем не повод оставлять этот баг, но то что он вот так себя заметно проявил - это удивительно. И, наверно, хорошо - ведь иначе он остался бы в коде и проявился когда-нить спустя годы, и пришлось бы вспоминать что там вообще происходит. Исправил добавлением write-lock1 вокруг status2=0;.

но это если компилятор не взял на регистр status2… короче это место точно непонятное.

Там -O0, по крайней мере сейчас.

firkax ★★★★★
() автор топика
Последнее исправление: firkax (всего исправлений: 2)
Ответ на: комментарий от firkax

Но удивляет вот что: сравнение сначала с нулём, а затем с четвёркой - это почти соседние ассемблерные инструкции получаются. Интуитивно кажется, что вероятность между ними вклиниться status2=0; исчезающе мала, однако на практике оно весьма себя проявляет.

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

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

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

Да, именно так. И вобщем-то это полностью предсказуемо, но меня тоже смутило и я сразу не догадался, что одна и та же переменная в разных местах одного read-only выражения может оказаться с разным значением.

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

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

и длинное вычисление адреса - тоже несколько команд навроде

array[i,i] = 0;

если тут другой тред меняет i, то i могут быть разными, в данном выражении.

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от RussianWarShip

могут, но это ничто не меняет. для данного кода это будет выглядеть ровно также как и на одном ядре. в момент вычисления выражения на одном ядре, тред с другого ядра изменит входящую в выражение переменную.

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

Там -O0, по крайней мере сейчас.

Исправил добавлением write-lock1

Подозреваю что при включенной оптимизации Вы бы никогда этого не увидели. Ну или явно читать status2 один раз и только потом проверять. Может и не стоило платить лишним lock’ом?

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

не нуна. это костыль.

во-первых, другой чувак может прийти и выкинуть казалось бы лишнее присваивание, если ты не напишешь с нему 3-этажный коммент.

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

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

правильно тут вообще избавиться от проблемы - либо закомментить проверку и написать почему, либо переход 5->2 делать под write локом. я бы делал это под write локом lock1, ты же захватываешь его рид лок. то есть находишься в его охраняемом участке. вот и используй это дело.

твоя задача писать безошибочный код, а не ошибочный, подпертый костылями.

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

не нуна. это костыль.

Мнения разнятся. Мне не шашечки - мне ехать.

я бы делал это под write локом lock1

То что Вы ярый сторонник вусмерть пересинхронизованных очередей - мы давно усвоили. Нормальные люди стараются не платить лишнего там где это возможно.

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

Мнения разнятся. Мне не шашечки - мне ехать.

у чувака проблема в том, что у него есть нечеткое состояние системы, а не только перечисленные им стейты. и он пытается проверять некие инварианты стейтов и в некоторые моменты оно ломается, когда он попадает в нечеткое состояние.

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

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

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от alysnix

ПыСы

я бы делал это под write локом lock1

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

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

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

читай предыдущую мессагу и много думай… прод/шмод/дебаг. причем тут это все. прога должна быть алгоритмически корректной вне зависимости от прода или шмода.

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

Тут только одну и нужно - остальные защищены локом от изменений. Единственный разрешённый в этом контексте переход это 5->2 т.е. status2 с 4 на 0.

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

Вот тут конечно может крыться опасность. Но разве может выйти что он решит локальную переменную закешировать в памяти по указателю откуда она взята? Обычно оптимизации наоборот кешируют локально места из памяти.

Делать лишний лок, когда можно без него, и правда не очень хорошо.

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

у чувака проблема в том, что у него есть нечеткое состояние системы, а не только перечисленные им стейты.

Вовсе нет, состояние ограничено перечисленными стейтами. Ни в какой момент времени за пределами лока оно не оказывается другим. Переключение 5->2 атомарно т.к. это переписать строго один int.

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

прога должна быть алгоритмически корректной

вне зависимости от прода или шмода

Вы яркий пример того что я называю «академическим программированием». Меня, по большому счету, ничего кроме поведения проги в проде не интересует. Больше скажу - имхо, баги которые не вылезают в проде не стоят потраченного времени (но об этом можно спорить - всё рисками определяется). А Вы всё так и пилите своего «сферического коня в вакууме».

ПыСы. Хех, ведь зарекался же с Вами в полемику вступать…

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

Переключение 5->2 атомарно т.к. это переписать строго один int.

у вас проблема не в «атомарности переключения», а в неатомарности использования. рид лок ее бы давал, но вам тут неохота делать write lock.

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

даю академическое определение:

программный костыль это участок кода, нивелирующий в некотором конкретном месте ошибочную работу алгоритмически некорректной программы.
alysnix ★★★
()
Ответ на: комментарий от alysnix

а в неатомарности использования.

Так если переменную прочесть 1 раз это как раз и будет атомарное использование, но тебе такой вариант тоже не нравится, почему?

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

Вот это вот:

а ещё у status2 есть lock2, который защищает от race между разными его переключалками

намекает на то что брать write-lock1 на 5->2 как-то не очень правильно. Тогда уж write-lock2, и брать read-lock2 вокруг этого assertion (в предположении что никто нигде не берёт эти locks в обратном порядке). Подчеркну - только ради assertion я бы этого точно не делал.

Но что-то совсем не так: 4->5 меняет все 3 поля, что означает status2 не особо ортагонален к status/data. Почему у него свой rwlock - не совсем понятно. Возможно более правильным было бы сделать его атомиком и избавиться от lock2, но не имея «big picture» что-то советовать трудно.

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

А зачем? Проблема уже решена, а тема создана как развлекательно-образовательная, проверить свою внимательность на такие штуки.

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

Вот тут конечно может крыться опасность.

Специально сегодня проконсультировался с одним из знакомых gcc devs: стандарт гарантирует что в ситуации

void foo(int* ptr) {
   int i = *ptr;
   // i дальше используется многократно
   // ptr больше никогда explicitly не трогается, ни как ptr, ни как *ptr
}

memload из *ptr произойдёт ровно 1 раз, и даже при наличии significant register pressure «i» будет «offloaded» на стек. Вы - «safe». Ie optimizer не имеет права предполагать что *ptr не изменился.

bugfixer ★★★★
()