Thread-safe linked list review

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->_ent

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.

StackExchange Code Review Q#33311, answer score: 5