Как предотвратить повреждение в параллельном стеке lifo, реализованном с помощью атомарного сравнения и свопинга

Question

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

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

Есть ли способ надежно использовать один и тот же узел с одним и тем же стеком более одного раза? Это преувеличенный пример, но даже возвращение неизмененного узла в gHead может привести к утечке других узлов. Первоначальной целью этой структуры данных было многократное использование одних и тех же узлов.

typedef struct test_node {
    struct test_node *next;
    void *data;
} *test_node_p;

test_node_p gHead = NULL;
unsigned gThreadsDone = 0;

void test_put( test_node_p inMemory ) {
    test_node_p scratch;

    do {
        scratch = gHead;
        inMemory->next = scratch;
    } while ( !__sync_bool_compare_and_swap( &gHead , scratch , inMemory ) );
}

test_node_p test_get( void ) {
    test_node_p result;
    test_node_p scratch;

    do {
        result = gHead;
        if ( NULL == result ) break;
        //  other thread acquires result, modifies next
        scratch = result->next;     //  scratch is 0xDEFACED...
        //  other thread returns result to gHead
    } while ( !__sync_bool_compare_and_swap( &gHead , result , scratch ) );
    //  this thread corrupts gHead with 0xDEFACED... value

    if ( NULL == result ) {
        result = (test_node_p)malloc( sizeof(struct test_node) );
    }

    return result;
}

void *memory_entry( void *in ) {
    test_node_p node;
    int index , count = 1000;
    for ( index = 0 ; index < count ; ++index ) {
        node = test_get();
        *(uint64_t *)(node) |= 0xDEFACED000000000ULL;
        test_put( node );
    }

    __sync_add_and_fetch(&gThreadsDone,1);

    return NULL;
}

void main() {
    unsigned    index , count = 8;
    pthread_t   thread;

    gThreadsDone = 0;

    for ( index = 0 ; index < count ; ++index ) {
        pthread_create( &thread , NULL , memory_entry , NULL );
        pthread_detach( thread );
    }

    while ( __sync_add_and_fetch(&gThreadsDone,0) < count ) {}
}

Я запускаю этот тест с 8 логическими ядрами. Когда я использую только 4 потока, проблема возникает редко, но с 8 это легко воспроизводимо. У меня есть MacBook с Intel Core i7.

Я не заинтересован в использовании какой-либо библиотеки или фреймворка, который решил это, я хочу знать, как это было решено. Спасибо.

Редактировать:

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

Некоторые архитектуры предоставляют пары инструкций ll / sc, которые выполняют атомарные проверки адреса вместо значения. Любая запись по адресу, даже одного и того же значения, предотвращает успех.

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

Вот игра игры игры. Две нити, A и B, достигают точки в test_get где они имеют одинаковое значение для result и это не NULL, Затем происходит следующая последовательность:

1. Поток А проходит сравнение и обмен и возвращает result от test_get
2. Тема А изменяет содержание result
3. Тема B разыменовывается resultполучая какую-нить А положи туда
4. Нить А заканчивается result и звонки test_put
5. Поток А проходит сравнение и обмен в test_put вернуть результат на gHead
6. Поток B достигает сравнения и меняет местами test_get и проходит
7. Тема B теперь повреждена gHead со значением из темы A

Вот аналогичный сценарий с тремя потоками, которые не требуют потока A для изменения result,

1. Поток А проходит сравнение и обмен и возвращает result от test_get
2. Тема А не изменяет содержание result
3. Тема B разыменовывается result, получив действительное значение в scratch
4. Тема C звонки test_put с несвязанным значением и успешно
5. Тема звонков test_put и удается положить result обратно на gHead
6. Поток B достигает сравнения и меняет местами test_get и проходит
7. Тема B теперь повреждена gHead утечка какой-либо нить C добавил

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

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

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

Также обратите внимание, что атомарный означает, что он успешен или провален в целом. Любое выровненное чтение указателя неявно атомарно на рассматриваемом оборудовании. Что касается других потоков, то нет прерываемой точки, где была бы прочитана только половина указателя.

Answer 1

(Я отказываюсь от своего предыдущего ответа.)

Проблема в том, что у вас нет механизма атомарного чтения gHead а также gHead->next, но это необходимо для достижения вашего стека без блокировки. Так как вы все равно намереваетесь использовать занятый цикл для обработки коллизий сравнения и обмена, вы можете использовать эквивалент спин-блокировки:

void lock_get () {
    while (!_sync_bool_compare_and_swap(&gGetLock, 0, 1)) {}
}

void unlock_get () {
    unlock_get_success = _sync_bool_compare_and_swap(&gGetLock, 1, 0);
    assert(unlock_get_success);
}

Теперь цикл в test_get() может быть окружен lock_get() а также unlock_get(), Цикл CAS test_get() это всего лишь один поток, борющийся с test_put(), Внедрение Дженсом цикла CAS кажется более чистым.

lock_get();
result = __sync_val_compare_and_swap(&gHead, 0, 0);
while ((oldval = result)) {
   result = __sync_val_compare_and_swap(&gHead, result, result->next);
   if (oldval == result) break;
}
unlock_get();

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

Answer 2

Никогда не получайте доступ к атомарной переменной с помощью простой оценки. Кроме того, для сравнения и обмена цикла, как у вас, __sync_val_compare_and_swap удобнее, я думаю.

/* read the head atomically */
result = __sync_val_compare_and_swap(&gHead, 0, 0);
/* compare and swap until we succeed placing the next field */
while ((oldval = result)) {
   result = __sync_val_compare_and_swap(&gHead, result, result->next);
   if (oldval == result) break;
}

Answer 3

Если у вас есть переменная CAS (в вашем случае gHead). Вы должны всегда использовать CAS для доступа к нему. Или защитить его с помощью замка. Для чтения и письма. Вещи вроде "result = gHead;" это большой нет-нет.

Перечитывая ваш вопрос, LIFO - это стек. Реализация любой структуры данных, основанной на CAS, основана на наличии только ОДНОЙ вещи, которую можно изменить. В стеке, который является вершиной стека. Вы, кажется, делаете связанный список. Я уверен, что есть классные способы сделать атомарный связанный список.

Но для стека сделайте один указатель стека, как и все остальные:)