Implementacja kolejkowania bez użycia bloków kończy się pętlą pod obciążeniem

Question

Mam kolejki bez blokowania napisane w C w postaci połączonej listy zawierającej żądania z wielu wątków publikowanych i obsługiwanych w jednym wątku. Po kilku godzinach stresu dochodzę do następnego wskaźnika wskazującego na siebie samego, który tworzy nieskończoną pętlę i blokuje wątek obsługi.

Aplikacja działa (i kończy się niepowodzeniem) zarówno w systemie Linux, jak i Windows. Debuguję w systemie Windows, gdzie moje COMPARE_EXCHANGE_PTR mapuje na InterlockedCompareExchangePointer.

Jest to kod, który popycha wniosek do szefa listy, a nazywa się z kilku wątków:

void push_request(struct request * volatile * root, struct request * request) 
{ 
    assert(request); 

    do { 
     request->next = *root; 
    } while(COMPARE_EXCHANGE_PTR(root, request, request->next) != request->next); 
} 

Jest to kod, który otrzymuje wniosek od końca listy, a jest tylko wywoływana przez jeden wątek, który jest ich obsługi:

struct request * pop_request(struct request * volatile * root) 
{ 
    struct request * volatile * p; 
    struct request * request; 

    do { 
     p = root; 
     while(*p && (*p)->next) p = &(*p)->next; // <- loops here 
     request = *p; 
    } while(COMPARE_EXCHANGE_PTR(p, NULL, request) != request); 

    assert(request->next == NULL); 

    return request; 
} 

Należy pamiętać, że nie używam wskaźnik ogon, bo chciałem uniknąć komplikacji mając do czynienia ze wskaźnikiem ogonowej w push_request. Podejrzewam jednak, że problem może tkwić w sposobie, w jaki znajduję koniec listy.

Istnieje kilka miejsc, które popychają żądanie w kolejce, ale wszystkie wyglądają generaly tak:

// device->requests is defined as struct request * volatile requests; 
struct request * request = malloc(sizeof(struct request)); 
if(request) { 
    // fill out request fields 
    push_request(&device->requests, request); 
    sem_post(device->request_sem); 
} 

Kod, który obsługuje żądania robi więcej, ale w istocie robi to w sposób pętla:

if(sem_wait_timeout(device->request_sem, timeout) == sem_success) { 
    struct request * request = pop_request(&device->requests); 
    // handle request 
    free(request); 
} 

ja też po prostu dodaje funkcję, która sprawdza listę duplikatów przed i po każdej operacji, ale obawiam się, że ta kontrola będzie zmienić taktowanie tak, że nigdy nie spotkać się z punktu, w którym zawiedzie. (Czekam, aż się zepsuł, gdy to piszę.)

Po przerwaniu programu zawieszającego pętla wątku pętli w pop_request w zaznaczonej pozycji. Mam poprawną listę jednego lub więcej żądań, a następny wskaźnik wskazuje na siebie. Kolejki żądań są zwykle krótkie, nigdy nie widziałem więcej niż 10, a tylko 1 i 3 dwa razy mogłem rzucić okiem na ten błąd w debugerze.

Pomyślałem o tym tak dużo, jak tylko mogłem i doszedłem do wniosku, że nigdy nie będę w stanie znaleźć pętli na mojej liście, chyba że dwa razy poproszę o tę samą prośbę. Jestem pewien, że to się nigdy nie zdarza. Jestem też całkiem pewien (choć nie do końca), że to nie jest ABA problem.

Wiem, że mogę wysłać więcej niż jedną prośbę w tym samym czasie, ale uważam, że nie ma tu znaczenia i nigdy nie widziałem, żeby to się stało. (Naprawię to również)

Myślałem długo i mocno o tym, jak mogę złamać moją funkcję, ale nie widzę sposobu, aby zakończyć pętlę.

Pytanie brzmi: Czy ktoś może zobaczyć, jak to się może złamać? Czy ktoś może udowodnić, że tak nie jest?

W końcu to rozwiążę (może za pomocą wskaźnika ogona lub innego rozwiązania - blokowanie będzie problemem, ponieważ wątki, które poczta nie powinna być zablokowana, mam jednak pod ręką blokadę RW), ale chciałbym aby upewnić się, że zmiana listy faktycznie rozwiązuje mój problem (w przeciwieństwie do tego, że jest to mniej prawdopodobne ze względu na inny czas).

Answer 1

Jest subtelny, ale masz tam wyścigowy stan.

Zacznij od listy z jednym elementem, req1. Tak więc mamy:

device->requests == req1; 
req1->next == NULL; 

Teraz wciśnij nowy element req2, a jednocześnie starają się pop kolejkę. Najpierw uruchamia się funkcja push dla req2. Ciało pętli while działa, więc teraz mamy:

device->requests == req1; 
req1->next == NULL; 
req2->next == req1; 

wtedy COMPARE_EXCHANGE_PTR działa, więc mamy:

device->requests == req2; 
req1->next == NULL; 
req2->next == req1; 

... i COMPARE_EXCHANGE_PTR() powraca req1. Teraz, w tym momencie, przed porównaniem w while stanie, naciśnięcie zostaje przerwane i pop zaczyna działać.

pop przebiega prawidłowo do końca, pstrykaliśmy req1 - co oznacza, że ​​mamy:

device->requests == req2; 
req2->next == NULL; 

wznowi Push. Teraz pobiera on request->next, aby wykonać porównanie - i pobiera nową wartość o wartości req2->next, która jest NULL. Porównuje req1 z NULL porównanie się powiedzie, podczas gdy pętla uruchamia ponownie, a teraz mamy:

device->requests == req2; 
req2->next == req2; 

Tym razem test nie powiedzie się, wyjścia pętli while i masz pętlę.

---

To powinno go naprawić:

void push_request(struct request * volatile * root, struct request * request) 
{ 
    struct request *oldroot; 

    assert(request); 

    do { 
     request->next = oldroot = *root; 
    } while(COMPARE_EXCHANGE_PTR(root, request, oldroot) != oldroot); 
}