Поиск неисправностей в коде блокировки с атомами и фьютексами

Question

Я ужасно пытаюсь отлаживать тупик, вызывающий состояние гонки, в моих примитивах блокировки на основе Linux-futex и atomic-ops.Вот код, с которым я работаю (точно такая же логика, как у реального кода, только что вытащил зависимость от структур данных, которые не имеют отношения к проблеме):

int readers, writer, waiting;

void wrlock()
{
    int cur;
    while (atomic_swap(&writer, 1)) spin();
    while ((cur=readers)) futex_wait(&readers, cur);
}

void wrunlock()
{
    atomic_store(&writer, 0);
    if (waiting) futex_wake(&writer, ALL);
}

void rdlock()
{
    atomic_inc(&waiting);
    for (;;) {
        atomic_inc(&readers);
        if (!writer) return;
        atomic_dec(&readers);
        futex_wait(&writer, 1);
    }
}

void rdunlock()
{
    atomic_dec(&waiting);
    atomic_dec(&readers);
    if (writer) futex_wake(&readers, ALL);
}

atomic_* и spin функции довольно очевидны.Операционные функции Linux futex: futex_wait(int *mem, int val) и futex_wake(int *mem, int how_many_to_wake).

Условие тупика, с которым я сталкиваюсь, - это 3 потока, readers==0, writer==1, waiting==2 и все потоки, ожидающие на futex_wait,Я не понимаю, как это может произойти.

И для всех, кто хочет кричать на меня за то, что я не использую pthread примитивы, пожалуйста, сохраните его для другого вопроса.Это низкоуровневый код, который работает независимо от glibc / libpthread.В любом случае, я думаю, что этот вопрос, вероятно, будет полезен другим для изучения низкоуровневой черной магии параллелизма или, возможно, для того, чтобы кого-то напугать и попытаться написать такой код ...; -)

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

Вот сгенерированный asm для wrlock (в основном идентичныйверсия, которую я выложил, за исключением того, что она вызывает отдельную функцию lock для первого спин-блокировки).Дополнительный условный возврат в начале - «если мы не запускаем несколько потоков, выручите».0x338 и 0x33c соответствуют readers и writer.call 1af фактически является переадресацией для вызова futex_wait, который является внешним.

00000184 <wrlock>:
 184:   a1 18 00 00 00          mov    0x18,%eax
 189:   55                      push   %ebp
 18a:   85 c0                   test   %eax,%eax
 18c:   89 e5                   mov    %esp,%ebp
 18e:   75 02                   jne    192 <wrlock+0xe>
 190:   c9                      leave
 191:   c3                      ret
 192:   68 3c 03 00 00          push   $0x33c
 197:   e8 7e fe ff ff          call   1a <lock>
 19c:   58                      pop    %eax
 19d:   a1 38 03 00 00          mov    0x338,%eax
 1a2:   85 c0                   test   %eax,%eax
 1a4:   74 ea                   je     190 <wrlock+0xc>
 1a6:   6a 01                   push   $0x1
 1a8:   50                      push   %eax
 1a9:   68 38 03 00 00          push   $0x338
 1ae:   e8 fc ff ff ff          call   1af <wrlock+0x2b>
 1b3:   a1 38 03 00 00          mov    0x338,%eax
 1b8:   83 c4 0c                add    $0xc,%esp
 1bb:   85 c0                   test   %eax,%eax
 1bd:   75 e7                   jne    1a6 <wrlock+0x22>
 1bf:   eb cf                   jmp    190 <wrlock+0xc>

Answer 1

Я думаю, это иллюстрирует ваш потенциальный тупик.Предположим, что один процессор выполняет ваши 3 потока в следующей последовательности:

// to start, 
//   readers == 0, writer == 0, waiting == 0

Reader1
===================================

// in rdlock()
    atomic_inc(&waiting);
    for (;;) {
        atomic_inc(&readers);

    // if (!writer) has not been executed yet

    //   readers == 1, writer == 0, waiting == 1

writer 
===================================
// in wrlock()
while (atomic_swap(&writer, 1)) spin();
    while ((cur=readers)) futex_wait(&readers, cur)

    // writer thread is waiting

    // readers == 1, writer == 1, waiting == 1
    //   cur == 1



Reader1
===================================

// back to where it was in rdlock()
        if (!writer) return;
        atomic_dec(&readers);
        futex_wait(&writer, 1);

    // Reader1 is waiting
    //   readers == 0, writer == 1, waiting == 1

Reader2
===================================

// in rdlock()
    atomic_inc(&waiting);
    for (;;) {
        atomic_inc(&readers);
        if (!writer) return;
        atomic_dec(&readers);
        futex_wait(&writer, 1);

    // Reader2 is waiting
    //  readers == 0, writer == 1, waiting == 2

Теперь вы зашли в тупик.

Конечно, я не понимаю, как работает API futex (яЯ никогда не использовал их), так что дайте мне знать, если я здесь.Я предполагаю, что futex_wait(), который блокирует (потому что ожидаемое значение было правильным), не разблокируется, пока не будет futex_wake() вызов для этого адреса.

Если atomic_xxx() операции могут разблокировать futex_wait(), этот анализ неверен.

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

Answer 2

Я предполагаю, что это проблема с упорядочением памяти.Я не очень хорошо знаю модель памяти x86, но я сильно подозреваю, что вам нужен забор памяти вокруг ваших futex_* вызовов.Я понимаю, что x86 гарантирует, что одно ядро ​​будет обновлять содержимое памяти других ядер в том же порядке, в котором записаны ячейки памяти, но кажется, что вы полагаетесь на более сильное предположение - что записи на одном ядре будут немедленно видны другим,Например, скажем, что ядро ​​A имеет rdlock и только что выполнило rdunlock.Теперь он очищает как waiting, так и readers, но эта информация еще не дошла до ядра B к тому времени, когда ядро ​​B пытается wrlock.Core B успешно получает writer, но видит, что существуют readers.Обновление до writer не было отправлено в ядро ​​A к тому моменту, когда rdunlock проверяет, нужно ли ему futex_wake(&readers), поэтому не делает этого.Это может показать ваши симптомы, а также иметь свойство, которое будет восстановлено, если вызовы futex_* будут заменены простыми спинами.Имеет ли это для вас смысл?

Хм, while ((cur=readers)) futex_wait(&readers, cur); должно быть, пока ((cur==readers))...?