基于__sync_bool_compare_and_swap的无锁链表多线程测试异常排查

Hey, let's break down why your consumers are only picking up 1-3 nodes instead of the 10 your producer inserts. The symptom (first node's next is NULL even though 10 should be present) points straight to a race condition in how you're handling tail insertion or boundary cases like empty/single-node lists. Let's walk through the most likely culprits and fixes:

1. Your Tail Insertion Logic Is Missing Atomic Guardrails #

Lock-free tail insertion is tricky because you have two linked operations: updating the previous tail's next pointer, and updating the list's tail reference. If these aren't coordinated with CAS, nodes can get "dropped" or linked to invalid pointers.

Common Bad Implementation (That Causes Your Issue) #

If your llist_insert_tail looks anything like this, you're asking for trouble:

bool llist_insert_tail(struct llist_head *head, struct llist_node *new_node) {
    new_node->next = NULL;
    struct llist_node *old_tail = head->tail;
    // ❌ Critical race: setting next before CAS-ing tail
    old_tail->next = new_node;
    return __sync_bool_compare_and_swap(&head->tail, old_tail, new_node);
}

Here's the problem: After you set old_tail->next = new_node but before you CAS the tail pointer, a consumer could delete that last node (the old tail). Now your producer is linking the new node to a node that's already been removed from the list—so the new node is effectively lost, and your list appears empty even though you just inserted it.

2. Boundary Case Handling (Empty/Single-Node Lists) Is Broken #

Without a sentinel (dummy) node, handling empty lists or lists with one node is a minefield. For example:

• When the list is empty, your producer has to set both head and tail to the new node. If these aren't atomic, a consumer could check head before it's set, think the list is empty, and miss the node.
• When the last node is deleted, if you don't update tail to match head, your producer will try to link new nodes to a stale tail pointer (pointing to a node that's already been consumed).

3. Your Head Removal Logic Isn't Syncing Tail #

If your llist_remove_head only updates the head pointer and ignores tail when the last node is removed, you'll end up with a tail that points to a node no longer in the list. Here's what that might look like:

struct llist_node *llist_remove_head(struct llist_head *head) {
    struct llist_node *old_head = head->head;
    if (!old_head) return NULL;
    // ❌ Forgets to update tail when deleting the last node
    if (!__sync_bool_compare_and_swap(&head->head, old_head, old_head->next)) {
        return NULL;
    }
    return old_head;
}

After deleting the last node, head is NULL but tail still points to the old node. Your next insertion will link to that stale node's next (which is NULL), making your new node invisible to consumers.

Fixes to Try #

Let's fix these issues step by step:

Step 1: Add a Sentinel Node to Simplify Boundaries #

A sentinel (permanent dummy node) eliminates empty-list edge cases. Your list will never be truly empty—there's always the sentinel. Here's how to adjust your structs:

struct llist_node {
    struct llist_node *next;
    // Your data fields here
};

struct llist_head {
    struct llist_node sentinel; // Always exists, never removed
    struct llist_node *tail;
};

// Initialize the list once
void llist_init(struct llist_head *head) {
    head->sentinel.next = NULL;
    head->tail = &head->sentinel;
}

Step 2: Fix Tail Insertion with CAS Ordering #

For your single-producer scenario, we can make this robust by first ensuring the new node is linked into the list, then updating the tail (even if the tail update fails, subsequent operations will clean it up):

bool llist_insert_tail(struct llist_head *head, struct llist_node *new_node) {
    new_node->next = NULL;
    while (1) {
        struct llist_node *old_tail = head->tail;
        // First: CAS to link the new node to the old tail's next
        if (__sync_bool_compare_and_swap(&old_tail->next, NULL, new_node)) {
            // Second: Try to update tail (ok if this fails—other ops will fix it)
            __sync_bool_compare_and_swap(&head->tail, old_tail, new_node);
            return true;
        }
        // If CAS failed, tail is stale—advance it to the real tail
        __sync_bool_compare_and_swap(&head->tail, old_tail, old_tail->next);
    }
}

The key here is linking the node first before touching the tail. Even if the tail update fails, the next insertion will see that old_tail->next isn't NULL and fix the tail pointer automatically.

Step 3: Update Head Removal to Sync Tail #

With the sentinel, your removal logic needs to reset the tail to the sentinel when the last valid node is deleted:

struct llist_node *llist_remove_head(struct llist_head *head) {
    while (1) {
        struct llist_node *first_valid = head->sentinel.next;
        if (!first_valid) return NULL; // No nodes to consume
        struct llist_node *next_node = first_valid->next;
        // CAS to take the first valid node
        if (__sync_bool_compare_and_swap(&head->sentinel.next, first_valid, next_node)) {
            // If we just deleted the last node, reset tail to sentinel
            if (!next_node) {
                __sync_bool_compare_and_swap(&head->tail, first_valid, &head->sentinel);
            }
            return first_valid;
        }
    }
}

This ensures the tail never points to a node that's been removed from the list.

Step 4: Check Node Lifetime #

Make sure consumers aren't freeing nodes immediately after removing them—if your producer is still trying to access a freed node's next pointer, you'll get undefined behavior (like NULL pointers where they shouldn't be). Keep nodes alive until you're sure no threads are referencing them, or use a memory allocator designed for concurrent use.

Step 5: Add Debug Logs to Trace Races #

Add logs around your CAS operations to see exactly what's happening:

// In insertion code
printf("[Producer] Attempting insert: new_node=%p, old_tail=%p, old_tail->next=%p\n", 
       new_node, old_tail, old_tail->next);
if (__sync_bool_compare_and_swap(&old_tail->next, NULL, new_node)) {
    printf("[Producer] Linked node successfully: old_tail->next now=%p\n", old_tail->next);
    bool tail_ok = __sync_bool_compare_and_swap(&head->tail, old_tail, new_node);
    printf("[Producer] Tail update %s: new tail=%p\n", tail_ok ? "succeeded" : "failed", new_node);
} else {
    printf("[Producer] Link failed—old_tail->next is now=%p\n", old_tail->next);
}

// In removal code (pass thread ID for clarity)
printf("[Consumer %d] Attempting remove: first_valid=%p, next=%p\n", 
       thread_id, first_valid, next_node);
if (__sync_bool_compare_and_swap(&head->sentinel.next, first_valid, next_node)) {
    printf("[Consumer %d] Removed node: new head.next=%p\n", thread_id, next_node);
    if (!next_node) {
        bool tail_ok = __sync_bool_compare_and_swap(&head->tail, first_valid, &head->sentinel);
        printf("[Consumer %d] Tail reset to sentinel: %s\n", thread_id, tail_ok ? "success" : "failed");
    }
}

These logs will show you if nodes are being linked properly, if tail updates are failing, or if consumers are removing nodes faster than the producer can link them in a way that breaks the list.

Final Notes #

Your issue is almost certainly due to missing atomic coordination between linking nodes and updating the tail pointer, or mishandling the tail when the last node is removed. Adding the sentinel node alone will eliminate most of the boundary case races, and fixing the CAS order in insertion will ensure nodes don't get lost.

If you still hit issues, share your exact llist_insert_tail and llist_remove_head code—we can dive deeper into the specifics.

内容的提问来源于stack exchange，提问作者chris.sun