Реализация очереди без блокировки заканчивается циклом под нагрузкой

Это код, который помещает запрос в начало списка и вызывается из нескольких потоков:

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

Это код, который получает запрос из конца списка и вызывается только одним потоком, который их обрабатывает:

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

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

Есть несколько мест, которые помещают запрос в очередь, но все они выглядят примерно так:

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

Код, обрабатывающий запрос, делает больше, но по сути делает это в цикле:

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

Я также только что добавил функцию, которая проверяет список на наличие дубликатов до и после каждой операции, но я боюсь, что эта проверка изменит время, так что я никогда не столкнусь с моментом, когда она выйдет из строя. (Я жду, когда он сломается, пока пишу это.)

Когда я прерываю зависшую программу, поток обработчика зацикливается на pop_request в отмеченной позиции. У меня есть действительный список из одного или нескольких запросов, и последний следующий указатель указывает на себя. Очереди запросов обычно короткие, я никогда не видел больше 10, и только 1 и 3 два раза я мог посмотреть на этот сбой в отладчике.