Почему это состояние гонки происходит только с -O3 и только с определенным, на первый взгляд эквивалентным порядком кода? - PullRequest
Новая
       31

Почему это состояние гонки происходит только с -O3 и только с определенным, на первый взгляд эквивалентным порядком кода?

0 голосов
/ 15 апреля 2020

Я реализовал неизменную карту ha sh и сопровождающий контейнер STM, вдохновленный atom clojure, то есть чем-то похожим на std::unique_ptr C ++, в котором он управляет (но не обязательно владеет) другим объектом через указатель, который можно передавать и заменять, и только уменьшая счетчик ссылок на управляемый объект, а не уничтожая его напрямую. При запуске некоторого тестового кода, скомпилированного с -O3, я начал замечать неверные результаты.

Код для сравнения и обмена выглядит примерно так: 

hashmap *update(stm *stm, update_callback cb, void *user_args)
{
    while (1) {
        lock(stm->mutex);
        hashmap *current = stm->reference;
        increment_ref_count(current); // Line 6
        unlock(stm->mutex);

        hashmap *aspirant = cb(current, user_args); // returns a new, thread local instance
        increment_ref_count(aspirant);

        // Position 1

        lock(stm->mutex);
        if (current == stm->reference) { // success, no modification while we were busy
            stm->reference = aspirant;
            increment_ref_count(aspirant); // stm now has a reference
            unlock(stm->mutex);

            // Position 2.1
            decrement_ref_count(current); // release reference acquired at line 6

            decrement_ref_count(current); // stm no longer has a reference
            return aspirant;

        } else { // reference was modified, loop and try again
            unlock(stm->mutex);

            // Position 2.2
            decrement_ref_count(current); // release reference acquired at line 6

            decrement_ref_count(aspirant); // ref_count now at zero, aspirant is free'd
        }
    }
}

increment_ & decrement_ref_count вводит / уменьшает счетчик ссылок на хэш-карту атомарно. Если в результате уменьшения значение счетчика упадет до нуля, hasmap будет освобожден вскоре после этого.

Задача создания контейнера STM для указателя с подсчетом ссылок в основном заключалась в создании aquiring-the-reference -and-incrementing the-counter atomi c, поэтому я использую здесь блокировки.

В качестве теста я использую hashmap + STM для подсчета вхождений в списке слов.

Если я запускаю код, указанный здесь, условия гонки не возникают. Теперь возникает моя проблема : если я переместу decrement_ref_count(current); // for line 6 из if/else, из Positions 2.1/2.2 (сразу после второго заблокированного региона) и поставлю его на Position 1 (прямо перед вторым заблокирован регион), внезапно подсчет слов начинает становиться неправильным, и я понятия не имею, почему.

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

Очевидно, у меня есть обходной путь / решение проблемы; просто оставив decrement там, где они сейчас, но мне бы очень хотелось понять, почему это происходит.

Скомпилировано с: gcc -Wall -Wcast-align -Wswitch-enum -Wswitch-default -Winit-self -pedantic -O3 -DNDEBUG -std=gnu11 в подсистеме Windows для Linux.

1 Ответ

1 голос
/ 20 апреля 2020

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

 1 | hashmap *update(stm *stm, update_callback cb, void *user_args)
 2 | {
 3 |     while (1) {
 4 |         lock(stm->mutex);
 5 |         hashmap *current = stm->reference;
 6 |         increment_ref_count(current); // Line 6
 7 |         unlock(stm->mutex);
 8 | 
 9 |         hashmap *aspirant = cb(current, user_args); // returns a new, thread local instance
10 |         increment_ref_count(aspirant);
11 | 
12 |         decrement_ref_count(current); // current might get free'd here
13 | 
14 |         lock(stm->mutex);
15 |         if (current == stm->reference) { // success, no modification while we were busy
16 |             stm->reference = aspirant;
17 |             increment_ref_count(aspirant); // stm now has a reference
18 |             unlock(stm->mutex);
19 | 
20 |
21 |
22 | 
23 |             decrement_ref_count(current); // stm no longer has a reference
24 |             return aspirant;
25 | 
26 |         } else { // reference was modified, loop and try again
27 |             unlock(stm->mutex);
28 | 
29 |
30 |
31 | 
32 |             decrement_ref_count(aspirant); // ref_count now at zero, aspirant is free'd
33 |         }
34 |     }
35 | }

Проблема в основном в том, что в строке 15 я использую адрес, по которому я отказался контроль. Я предполагал, что если бы другой поток изменил stm->reference, он сделал бы это с другим адресом. Вместо этого произошло следующее: пока мой поток ожидал блокировки в строке 14, карта current ha sh была освобождена, и новая карта ha sh была выделена по тому же адресу памяти и успешно сохранена в * 1006. *. Тогда мой поток продолжил бы, обнаружив, что current == stm->reference, ошибочно заключив, что никаких изменений в stm->reference не произошло с момента получения ссылки и предварительной замены, таким образом теряя некоторые обновления.

Урок здесь: Никогда не используйте указатели, которые были free ', даже если только для сравнения адресов!

...