Implementación de cola sin bloqueo termina teniendo un ciclo bajo estrés

Question

Tengo colas sin cierre escritas en C en forma de una lista vinculada que contiene solicitudes de varios hilos publicados y manejados en un único hilo. Después de algunas horas de estrés, termino teniendo el próximo puntero de la última solicitud apuntando hacia sí mismo, lo que crea un ciclo sin fin y bloquea el hilo de manejo.

La aplicación se ejecuta (y falla) tanto en Linux como en Windows. Estoy depurando en Windows, donde mis mapas COMPARE_EXCHANGE_PTR a InterlockedCompareExchangePointer.

Este es el código que empuja una solicitud a la cabeza de la lista, y se llama a partir de varios hilos:

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

Este es el código que recibe una solicitud desde el final de la lista, y es Sólo llamado por un único hilo que los está manejando:

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

tenga en cuenta que no estoy usando un puntero de cola porque quería evitar la complicación de tener que lidiar con el puntero de cola en push_request. Sin embargo, sospecho que el problema podría estar en la forma en que encuentro el final de la lista.

Hay varios lugares que empujan a una solicitud en la cola, pero todos se ven generaly así:

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

El código que controla la solicitud está haciendo más que eso, pero en esencia hace de una loop:

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

también acaba de agregar una función que está revisando la lista de duplicados antes y después de cada operación, pero me temo que esta comprobación cambiará la distribución de tal forma que nunca voy a encontrar el punto donde se falla (Estoy esperando que se rompa mientras escribo esto.)

Cuando rompo el programa de colgar, el hilo del manejador gira en pop_request en la posición marcada. Tengo una lista válida de una o más solicitudes y el último puntero apunta a sí mismo. Las colas de solicitudes suelen ser cortas, nunca he visto más de 10, y solo 1 y 3 las dos veces que pude echar un vistazo a esta falla en el depurador.

Pensé en esto tanto como pude y llegué a la conclusión de que nunca sería capaz de terminar con un ciclo en mi lista a menos que presione la misma solicitud dos veces. Estoy bastante seguro de que esto nunca sucede. También estoy bastante seguro (aunque no completamente) de que no es el ABA problem.

Sé que podría aparecer más de una solicitud al mismo tiempo, pero creo que esto es irrelevante aquí, y nunca lo he visto. (Voy a arreglar esto también)

Pensé largo y tendido acerca de cómo puedo romper mi función, pero no veo una manera de terminar con un ciclo.

Así que la pregunta es: ¿Alguien puede ver cómo se puede romper esto? ¿Alguien puede probar que esto no puede?

Eventualmente voy a resolver esto (tal vez usando un puntero en la cola o alguna otra solución - el bloqueo sería un problema porque los hilos que publican no deberían estar bloqueados, aunque tengo un bloqueo RW) pero me gustaría para asegurarme de que el cambio de la lista realmente resuelve mi problema (en lugar de hacerlo menos probable debido a un calendario diferente).

Answer 1

Es sutil pero tienes una condición de carrera allí.

Comience con una lista con un elemento en ella, req1. Así tenemos:

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

Ahora, empujamos un nuevo elemento req2, y al mismo tiempo tratar de hacer estallar la cola. El impulso para req2 comienza primero. El cuerpo del bucle, mientras corre, así que ahora tenemos:

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

Entonces los COMPARE_EXCHANGE_PTR carreras, por lo que tenemos:

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

... y los retornos COMPARE_EXCHANGE_PTR()req1. Ahora, en este punto, antes de la comparación en la condición while, el impulso se interrumpe y el pop se inicia.

El estallido se ejecuta correctamente hasta su finalización, haciendo estallar fuera req1 - lo que significa que tenemos:

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

Se reinicia el empuje. Ahora busca request->next para hacer la comparación, y obtiene el nuevo valor de req2->next, que es NULL. Se compara con req1NULL, la comparación tiene éxito, el bucle while se ejecuta de nuevo, y ahora tenemos:

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

Esta vez la prueba falla, las salidas de bucle while, y tiene su bucle.

---

Esto debería solucionarlo:

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