具有双链表正确性的无锁队列

Question

我需要一个无锁队列，它是由双链接列表实现的。

我的代码正确吗？有什么错误吗？是否有任何改善？

linkedlist.h

/*
 * linkedlist.h
 *
 *  Created on: 2014. 5. 10.
 *      Author: dlaru_000
 */

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_

/*
 * circular doubly linked list
 * PushBack / PopFront: single-producer, single-customer lock-free queue
 * Erase: thread-unsafe
 */

#include <stddef.h>
#include <stdint.h>

typedef struct tagLinkedListNode
{
    struct tagLinkedListNode * volatile pNext;
    struct tagLinkedListNode * volatile pPrev;
} LinkedListNode;

typedef struct tagLinkedList
{
    LinkedListNode dummy;

    /*
     * It can be invalid while some function is running on the other thread.
     * However it must valid after/before the function is finished.
     */
    uint32_t size;
} LinkedList;

void ckLinkedListInit(LinkedList *pList);

static inline LinkedListNode *ckLinkedListHead(LinkedList *pList) { return pList->dummy.pNext; }
static inline LinkedListNode *ckLinkedListTail(LinkedList *pList) { return pList->dummy.pPrev; }

void ckLinkedListPushBack(LinkedList *pList, void *pNode);
LinkedListNode *ckLinkedListPopFront(LinkedList *pList);

void ckLinkedListErase(LinkedList *pList, void *pNode);

#endif /* LINKEDLIST_H_ */

linkedlist.c

/*
 * linkedlist.c
 *
 *  Created on: 2014. 5. 10.
 *      Author: dlaru_000
 */

#include "linkedlist.h"

void ckLinkedListInit(LinkedList *pList)
{
    // circular linked list
    pList->dummy.pNext = &pList->dummy;
    pList->dummy.pPrev = &pList->dummy;
    pList->size = 0;
}

void ckLinkedListPushBack(LinkedList *pList, void *pNode)
{
    __sync_add_and_fetch(&pList->size, 1);

    LinkedListNode *dummy = &pList->dummy;

    LinkedListNode *ptr = (LinkedListNode *)pNode;
    LinkedListNode *tail;

    ptr->pNext = dummy;

    while (1)
    {
        tail = dummy->pPrev;
        ptr->pPrev = tail;
        if (__sync_bool_compare_and_swap(&dummy->pPrev, tail, ptr))
        {
            tail->pNext = ptr;
            break;
        }
    }
}

LinkedListNode *ckLinkedListPopFront(LinkedList *pList)
{
    LinkedListNode *dummy = &pList->dummy;

    LinkedListNode *ptr, *next, *dnext;

    ptr = dummy->pNext;
    if (ptr == dummy)
    {
        return NULL;
    }

    while (1)
    {
        next = ptr->pNext;
        if (__sync_bool_compare_and_swap(&next->pPrev, ptr, dummy))
        {
            dnext = dummy->pNext;
            __sync_bool_compare_and_swap(&dummy->pNext, dnext, next);
            break;
        }
    }

    __sync_sub_and_fetch(&pList->size, 1);
    return ptr;
}

void ckLinkedListErase(LinkedList *pList, void *pNode)
{
    LinkedListNode *ptr = (LinkedListNode *)pNode;
    LinkedListNode *prev = ptr->pPrev;
    LinkedListNode *next = ptr->pNext;

    prev->pNext = next;
    next->pPrev = prev;
    pList->size--;
}

PushBack的第二个参数的类型是void *，因为列表实际上包含如下内容：

struct SomeData
{
    LinkedListNode _node;
    ...
};

我用GCC的4.8.2和cygwin。

嗯，我注意到程序正在使用的"__sync“函数是遗留的，还有新功能__原子性。如何迁移到__atomic？

Answer 1

C11原子库

如果您想避免“遗留”函数，一种解决方案是使用C11 原子操作库。目前还没有得到广泛的支持。我知道GCC一直在做这个工作，但我不知道4.9版本是否已经实现了所有的操作。无论如何，如果您是一个兼容的编译器，您可以使用标准原子类型和原子操作。

例如，下面是用ckLinkedListPushBack原子模块重写的函数C11和ckLinkedListPopFront：

void ckLinkedListPushBack(LinkedList *pList, void *pNode)
{
    atomic_fetch_add(&pList->size, 1);

    LinkedListNode *dummy = &pList->dummy;

    LinkedListNode *ptr = (LinkedListNode *)pNode;
    LinkedListNode *tail;

    ptr->pNext = dummy;

    while (1)
    {
        tail = dummy->pPrev;
        ptr->pPrev = tail;
        if (atomic_compare_exchange_strong(&dummy->pPrev, tail, ptr))
        {
            tail->pNext = ptr;
            break;
        }
    }
}

LinkedListNode *ckLinkedListPopFront(LinkedList *pList)
{
    LinkedListNode *dummy = &pList->dummy;

    LinkedListNode *ptr, *next, *dnext;

    ptr = dummy->pNext;
    if (ptr == dummy)
    {
        return NULL;
    }

    while (1)
    {
        next = ptr->pNext;
        if (atomic_compare_exchange_strong(&next->pPrev, ptr, dummy))
        {
            dnext = dummy->pNext;
            atomic_compare_exchange_strong(&dummy->pNext, dnext, next);
            break;
        }
    }

    atomic_fetch_sub(&pList->size, 1);
    return ptr;
}

为了使其工作，您必须声明size是atomic_uint_least32_t的一个实例(不为atomics提供固定大小的类型)。

typedef struct

通过将LinkedListNode声明从实际声明中分离出来，可以使typedef声明更加清晰：

typedef struct tagLinkedListNode LinkedListNode;

struct tagLinkedListNode 
{
    LinkedListNode * volatile pNext;
    LinkedListNode * volatile pPrev;
};