Lockless Queue-Implementierung endet mit einer Schleife unter Belastung

Question

Ich habe Lockless-Warteschlangen in C in Form einer verketteten Liste geschrieben, die Anforderungen von mehreren Threads enthält, die in einem einzigen Thread veröffentlicht und behandelt werden. Nach ein paar Stunden Stress habe ich den nächsten Zeiger der nächsten Anfrage, der auf sich selbst zeigt, was eine Endlosschleife erzeugt und den Handhabungsthread blockiert.

Die Anwendung läuft (und scheitert) auf Linux und Windows. Ich debugge unter Windows, wo meine COMPARE_EXCHANGE_PTR auf InterlockedCompareExchangePointer mappt.

Dies ist der Code, der eine Anfrage an die Spitze der Liste drückt, und aus mehreren Threads aufgerufen wird:

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); 
} 

Dies ist der Code, der eine Anforderung von dem Ende der Liste bekommt, und ist nur von einem einzigen Thread genannt, die sie ist der Umgang:

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; 
} 

Bitte beachte, dass ich keinen Schwanz Zeiger verwenden, weil ich die Komplikation zu müssen, beschäftigen sich mit dem Endzeiger in push_request vermeiden wollte. Ich vermute jedoch, dass das Problem in der Art und Weise liegt, wie ich das Ende der Liste finde.

Es gibt mehrere Orte, die eine Anforderung in die Warteschlange schieben, aber sie sehen alle generaly wie folgt aus:

// 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); 
} 

Der Code, der die Anforderung verarbeitet wird mehr als das zu tun, aber im Grunde tut dies in einem Schleife:

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

ich habe auch nur eine Funktion, die die Liste für Duplikate vor und nach jeder Operation wird überprüft, aber ich habe Angst, dass diese Prüfung das Timing ändern wird, so dass ich nie den Punkt stoßen es in dem schlägt fehl. (Ich warte darauf, dass es bricht, während ich dies schreibe.)

Wenn ich das hängende Programm aufbringe, schleift der Handler-Thread in pop_request an der markierten Position. Ich habe eine gültige Liste von einer oder mehreren Anfragen und der letzte Zeiger zeigt auf sich selbst. Die Anforderungswarteschlangen sind normalerweise kurz, ich habe nie mehr als 10 gesehen, und nur 1 und 3 die zwei Male, die ich mir diesen Fehler im Debugger ansehen konnte.

Ich dachte das durch so viel wie ich konnte und ich kam zu dem Schluss, dass ich nie in der Lage sein würde, mit einer Schleife in meiner Liste zu enden, es sei denn, ich die gleiche Anfrage zweimal drücken. Ich bin mir ziemlich sicher, dass das nie passiert. Ich bin mir auch ziemlich sicher (wenn auch nicht vollständig), dass es nicht die ABA problem ist.

Ich weiß, dass ich mehr als eine Anfrage zur gleichen Zeit veröffentlichen könnte, aber ich glaube, das ist hier irrelevant, und ich habe es noch nie gesehen. (Ich werde das auch beheben)

Ich habe lange und gründlich darüber nachgedacht, wie ich meine Funktion brechen kann, aber ich sehe keinen Weg, mit einer Schleife zu enden.

So ist die Frage: Kann jemand einen Weg sehen, wie dies brechen kann? Kann jemand beweisen, dass dies nicht möglich ist?

Schließlich werde ich das lösen (vielleicht mit einem Tail-Pointer oder einer anderen Lösung - Sperren wäre ein Problem, weil die Threads, die Post sollte nicht gesperrt sein, ich habe zwar eine RW-Sperre zur Hand, aber ich möchte) um sicherzustellen, dass das Ändern der Liste tatsächlich mein Problem löst (im Gegensatz dazu macht es aufgrund des unterschiedlichen Timings weniger wahrscheinlich).

Answer 1

Es ist subtil, aber Sie haben dort eine Race Condition.

Beginnen Sie mit einer Liste mit einem Element, req1. So haben wir:

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

Nun schieben wir ein neues Element req2, und gleichzeitig versuchen, die Warteschlange Pop. Der Push für req2 startet zuerst. Die while-Schleife Körper läuft, so haben wir jetzt:

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

dann die COMPARE_EXCHANGE_PTR läuft, so haben wir:

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

... und die COMPARE_EXCHANGE_PTR() kehrt req1. Nun, an diesem Punkt, vor dem Vergleich in der while Bedingung, wird der Push unterbrochen und der Pop beginnt zu laufen.

Das Pop richtig läuft bis zur Fertigstellung, Abspringen req1 - was bedeutet, dass wir haben:

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

Die Push neu gestartet. Es holt jetzt request->next, um den Vergleich zu machen - und es holt den neuen Wert req2->next, der NULL ist. Er vergleicht req1 mit NULL, der Vergleich erfolgreich ist, läuft die while-Schleife wieder, und jetzt haben wir:

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

Dieses Mal den Test, die während Schleife beendet, und Sie haben Ihre Schleife ausfällt.

---

Dies sollte es beheben:

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); 
}