Linkedlist access multi-threaded application

Question

I have a multi-threaded application where multiple threads access the same variable - to a pointer. volatile would not be used for the purpose of ensuring atomic access (which doesn't exists), rather to ensure compile doesn't kick in hard optimization because it thinks that one thread cannot affect thread 2 and says no way it can change....

I've seen several volatile is useless in multi-threaded applications post. I have a linked list, that is accessed in 2 threads. Effectively does the following:

Thread 1

• Allocates memory for structure
• Puts the thread to linked list
• Processes the linked list and checks when some value is set to xyz

Thread 2

• Reads the linked list
• Does some processing
• Sets the value to xyz

All operations to linked list are protected by system mutex (FreeRTOS), but this doesn't ensure thread 2 sees the same value as thread 1 from start linked list pointer.

There are in my opinion 2 critical parts in the code:

• What threads see from list_starts pointer
• What threads see in the e->data value inside the pointer

This is the code, that is done wrongly - it is a reference code, not used in the production.

#include <stdint.h>
#include <stdlib.h>
#include <stdatomic.h>

typedef struct mytype {
    struct mytype* next;
    int data;
} mytype_t;
typedef _Atomic mytype_t mytype_atomic_t;

mytype_t* list_starts;
//mytype_atomic_t* list_starts;

void
thread1() {
    //Start thread2 here...
    //start_thread(thread2);

    //Run the thread here...
    while (1) {
        //mutex_lock();
        /* Create the entry */
        mytype_t* entry = malloc(sizeof(*entry));
        if (entry != NULL) {
            entry->next = list_starts;
            list_starts = entry;
        }
        //mutex_unlock();
        
        //mutex_lock();
start_over:
        for (mytype_t* e = list_starts, *prev = NULL; e != NULL; prev = e, e = e->next) {
            //mutex_unlock();
            //Simply wait to become 3
            while (e->data != 3) {}
            //mutex_lock();

            //Remove from the list
            if (prev == NULL) {
                list_starts = e->next;
            } else {
                prev->next = e->next;
            }
            free(e);
            goto start_over;
        }
        //mutex_unlock();
    }
}

Godbolt with -mcpu=cortex-m4 -O2 produces: https://godbolt.org/z/T84K3x3G4

thread1:
        push    {r4, lr}
        ldr     r4, .L12
.L4:
        movs    r0, #8
        bl      malloc
        cbz     r0, .L2
        ldr     r3, [r4]
        str     r3, [r0]
.L6:
        //Critical part - loaded once
        ldr     r3, [r0, #4]
.L5:
        //Comparison and BNE between self -> no reload
        cmp     r3, #3
        bne     .L5
        ldr     r3, [r0]
        str     r3, [r4]
        bl      free
        ldr     r0, [r4]
        cmp     r0, #0
        bne     .L6
        b       .L4
.L2:
        ldr     r0, [r4]
        cmp     r0, #0
        beq     .L4
        b       .L6
.L12:
        .word   .LANCHOR0
list_starts:

If we change the original code by using mytype_atomic_t* type in the for loop, like so

for (mytype_atomic_t* e = list_starts, *prev = NULL; e != NULL; prev = e, e = e->next) {
    while (e->data != 3) {}
}

Then godbolt produces: https://godbolt.org/z/94an17x1G

thread1:
        push    {r3, r4, r5, lr}
        ldr     r4, .L13
        ldr     r5, [r4]
.L4:
        movs    r0, #8
        bl      malloc
        cbz     r0, .L2
        str     r5, [r0]
        str     r0, [r4]
.L6:
        adds    r2, r0, #4
.L5:
        //Barrier
        dmb     ish
        //Load first...
        ldr     r3, [r2]
        dmb     ish
        cmp     r3, #3
        //Jump back to pre-load
        bne     .L5
        dmb     ish
        ldr     r3, [r0]
        dmb     ish
        str     r3, [r4]
        bl      free
        ldr     r0, [r4]
        cmp     r0, #0
        bne     .L6
.L7:
        movs    r5, #0
        b       .L4
.L2:
        cmp     r5, #0
        beq     .L7
        mov     r0, r5
        b       .L6
.L13:
        .word   .LANCHOR0
list_starts:

The ultimate question - is it enough to simply:

• declare custom type with _Atomic keyword?
• Do not use volatile at all in such case?

Answer 1

The ultimate question - is it enough to simply:

• declare custom type with _Atomic keyword?

No, this is wrong for your purpose. You are not allowed to access the members of an atomic structure (undefined behavior results). All you can do with one is read or write its whole (structure) value.

If you were not performing deletes, then it might sufficient to declare both members _Atomic, and also the list head pointer:

struct mytype {
    struct mytype * _Atomic next;
    _Atomic int data;
};

struct mytype * _Atomic list_starts;

(Apply typedefs if you feel you must, though as a general rule, I recommend avoiding them.)

• Do not use volatile at all in such case?

You do not need volatile, and it would not be sufficient if you used it (as far as can be judged by the C language specification; implementations may provide stronger guarantees).

However, the involvement of deletions from the list, and especially of frees, will require you to perform some kind of locking. No thread may access an allocated object after it has been freed, and you cannot ensure that it is safe to free one of your list nodes without engaging some kind of modifiable state that advises (or forces) other threads to wait -- that's the definition of a lock.

I can see why you want to avoid mutexes here, and especially to avoid a single mutex for the whole list. You may want to consider rolling your own lock with an additional _Atomic member of the structure, used with a busy loop performing an atomic compare and swap to perform locking and unlocking. Something like this, maybe:

struct mytype {
    struct mytype * _Atomic next;
    _Atomic int data;
    _Atomic _Bool is_locked;
};

void lock_mytype(struct mytype *x) {
    _Bool locked;
    do {
        locked = 0;
    } while (!atomic_compare_exchange_weak(&x->is_locked, &locked, 1));
}

void unlock_mytype(struct mytype *x) {
    _Bool locked = 1;
    if (!atomic_compare_exchange_weak(&x->is_locked, &locked, 0)) {
        // attempted to unlock a mutex that is not locked
        abort();
    }
}

That's pretty bare-bones, of course. At minimum, you could consider augmenting it to recognize which thread holds the lock, and to fail if a different one tries to unlock it.

To a first approximation, each thread will need to lock each node before accessing its members (other than is_locked). That moots the other members being atomic. To perform a deletion safely, you must lock both the predecessor and the node to delete, predecessor first. Update the predecessor's next member while holding both locks, then the predecessor's lock may be released. The deleted node's lock does not need to be released.

Note also that structuring linked lists with dummy head nodes instead of bare head pointers tends to provide for simpler code by eliminating the need for special cases. You might find that especially useful here, yielding something more like this:

struct mytype {
    struct mytype* next;
    int data;
    _Atomic _Bool is_locked;
};

struct mytype dummy_list_head;

void thread1() {
    while (1) {
        mytype_t* entry = malloc(sizeof(*entry));
        if (entry == NULL) {
            abort();
        }
        lock_mytype(&dummy_list_head);
        entry->next = dummy_list_head.next;
        dummy_list_head.next = entry;
        unlock_mytype(&dummy_list_head);
        
        while (1) {
            struct mytype *e;
            lock_mytype(&dummy_list_head);
            e = dummy_list_head.next;
            unlock_mytype(&dummy_list_head);
            if (e == NULL) break;

            int data;
            do {
                lock_mytype(e);
                int data = e->data;
                unlock_mytype(e);
            } while (data != 3);

            lock_mytype(&dummy_list_head);
            lock_mytype(e);
            dummy_list_head.next = e->next;
            unlock_mytype(&dummy_list_head);
            free(e);
        } 
    }
}

You might be able to tweak that a bit based on the knowledge that thread 1 is the only one that will ever perform deletions. That might involve making the data member atomic after all. But again, you need some form of locking here.