Thread-safe linked list review

Question

I want to implement a thread-safe singly linked list in C. Its nodes contain unique entries and I only need functions to add nodes (to head only), remove nodes and to locate a specific node.

I am reasonably confident of the linked-list logic (any performance tips would be greatly appreciated though), but I am more concerned with my thread-safety logic. This is my first real foray into coding a thread-safe data structure. Is it optimal? Is it overkill? Is there a more performant way to get thread-safety for this data structure?

Thread-safety definitions from header:

#define MY_SPINLOCK_INIT 0
typedef volatile int MYSpinLock;

__attribute__((always_inline))
static inline void MYSpinLockLock(MYSpinLock *lock) {
    while (__sync_lock_test_and_set(lock, 1))
        while (*lock)
            ;
}
__attribute__((always_inline))
static inline void MYSpinLockUnlock(MYSpinLock *lock) {
    __sync_lock_release(lock);
}

Struct definitions:

typedef struct {
    const void *_key;
    uintptr_t _value;
} MYEntry;

typedef struct __MYNode {
    MYEntry _entry;
    struct __MYNode *_next;
} MYNode;

typedef struct {
    MYNode *_head;
    MYSpinLock _lockLL;
} MYLinkedList;

Implementation:

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &(list->_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)

MYLinkedList *MYLinkedListConstruct() {
    MYLinkedList *list = malloc(sizeof(MYLinkedList));
    list->_head = NULL;
    list->_lockLL = MY_SPINLOCK_INIT;
    return list;
}

void MYLinkedListFree(MYLinkedList *list) {
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    MYNode *next;
    while (node != NULL) {
        next = node->_next;
        free(node);
        node = next;
    }

    MY_LISTLOCK_UNLOCK;
    free(list);
}

void MYLinkedListAdd(MYLinkedList *list, MYEntry *entry) {
    MY_LISTLOCK_LOCK;

    MYNode *oldHead = list->_head;
    MYNode *newHead = malloc(sizeof(MYNode));
    newHead->_entry = *entry;
    newHead->_next = oldHead;
    list->_head = newHead;

    MY_LISTLOCK_UNLOCK;
}

MYBool MYLinkedListRemoveNodeWithEntryKey(MYLinkedList *list, void *keyOfNodeToRemove) {

    if (keyOfNodeToRemove == NULL) return MYFalse;
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    MYNode *prev = NULL;
    while (node != NULL) {
        // We found it, break
        if (node->_entry._key == keyOfNodeToRemove) break;

        prev = node;
        node = node->_next;
    }

    // We never found it
    if (node == NULL) {
        MY_LISTLOCK_UNLOCK;
        return MYFalse;
    }

    // We found it
    if (prev == NULL) {
        list->_head = node->_next;
        free(node);
    }
    else {
        prev->_next = node->_next;
        free(node);
    }

    MY_LISTLOCK_UNLOCK;
    return MYTrue;
}

MYNode *MYLinkedListFindNodeWithKey(MYLinkedList *list, void *keyToFind) {

    if (keyToFind == NULL) return NULL;
    MY_LISTLOCK_LOCK;

    MYNode *node = list->_head;
    while (node != NULL) {
        if (node->_entry._key == keyToFind) {
            MY_LISTLOCK_UNLOCK;
            return node;
        }
        node = node->_next;
    }

    MY_LISTLOCK_UNLOCK;
    return NULL;
}

Answer 1

Is there a more performant way to get thread-safety for this data structure?

It all depends on how the list will be used. Just a few examples:

• Reads are more common than writes - use separate read/write locks.
• Average list is short - use copy-on-write array instead of linked list.
• Average list is long - use more efficient search method.
• Lots of threads access list - use mutex instead of spinlock to avoid wasted cycles.
• Lots of elements is added/removed in bulk - use external lock.

Have you actually measured performance in real world scenarios and identified bottlenecks? It looks like most of it is prematurely optimized.

__attribute__((always_inline))

Is this really necessary? Does it bring any measurable performance gain?

while (__sync_lock_test_and_set(lock, 1))
    while (*lock)

I do not understand this second while loop. Why are you checking the value twice?

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &(list->_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)

Avoid macros which can be replaced with functions.

MYBool

Use bool from stdbool.h.

Answer 2

Some comments, discussed in the order of reading the code:

Why so many leading underscores in the structures? What do you think is gained by using them? They are just noise to me. They are also reserved by something or other (Posix?) and so should be avoided. And using MY as a prefix for everything is distracting. Try lowercase if you really need a prefix - but you don't, so just drop it.

What is the context in which you want to use this code and its locks? You say you want it thread safe, but without knowing your context, I'm wondering about the lock and whether spinning is appropriate.

• In SpinLockLock, if the lock is busy, you spin in the inner while(*lock) loop, reading the lock to detect when it becomes free. If you omit the inner loop, the function spins writing the lock. Is there an advantage in reading rather than writing?
• As you are spinning (hogging the CPU), another thread can free the lock only if threads are time-slicing (in other words the lock is held by another thread that got sliced-out while holding the lock).
• Alternatively, the lock can be freed if another processor/core releases it - is this what you are planning?

Your MY_LISTLOCK_LOCK and MY_LISTLOCK_UNLOCK macros are a bad idea. Macros are a bad idea in general, inline functions being preferable. But here you have macros that use a variable from their context instead of using a call parameter and one that defines and hides a variable that both it and the next macro use. What is wrong with:

SpinLockLock(&list->lock);

...

SpinLockUnlock(&list->lock);

In LinkedListFree you are careful to protect the freeing of each node within the locked section. But then you free the list structure itself outside of the locked section. Clearly you should not free a lock while you are using it, so what you do might be logical. But if there was any point in protecting the freeing of nodes, it must be necessary also to protect the freeing of the list itself. For example another thread could get in (and presumably do something) between your unlocking the list and freeing it.

static void LinkedListFree(LinkedList **list)
{
    SpinLockLock(&(*list)->lock);
    LinkedList *l = *list;
    *list = NULL;

    Node *node = l->head;
    while (node != NULL) {
        Node *next = node->next;
        free(node);
        node = next;
    }
    SpinLockUnlock(&l->lock);
    free(l);
}

Note the double pointer to the list so we can clear the list in the caller. Note also that other functions must now check for a NULL list. This is probably excessive (but it is consistent), as you are most likely to free the list when everything is done and you know that no other thread will be using the list - in which case there is no point in protecting the freeing of nodes.

In LinkedListAdd, oldHead is redundant.

In LinkedListRemoveNodeWithEntryKey, the function name is verbose. Would LinkedListRemove not suffice? There is no other removal function after all. In this function the ambiguity of the void *key in the Entry structure is apparent.

if (node->entry.key == keyOfNodeToRemove) break;

This is comparing two pointers implying that the 'key' exists outside of the list for the duration of the list's existence (as opposed to being passed in and then forgotten about). That might be true - maybe you have some organized data that you want to reorganize as a list.... - is that so? The key clearly is a pointer, not just something else that takes the same space as a pointer cast into a pointer, because you treat 0 as an invalid value (although you don't check for it when adding to the list).

Also in that function, I don't much like the twin exits that must unlock the spin lock. It is usually better to have just one lock and one corresponding unlock.

Function LinkedListFindNodeWithKey suffers the same problems as the previous function. The name is too long (LinkedListFind perhaps), the key/pointer comparison is the same and there are two unlock calls. You can reorgansie to avoid the latter with:

LISTLOCK_LOCK;
Node *node = list->head;
while (node != NULL) {
    if (node->entry.key == keyToFind) {
        break;
    }
    node = node->next;
}
LISTLOCK_UNLOCK;
return node;