Fine-Grained Locking for Linked List Insertion

The Challenge of Concurrent Insertion

Inserting a node into a linked list involves modifying a next pointer. In a concurrent environment, this is a dangerous operation. If one thread is modifying pred->next while another thread is reading it, a data race occurs, leading to undefined behavior—the second thread might read a stale pointer, miss the new node entirely, or even crash.

The hand-over-hand protocol we designed solves this. To insert a new_node between pred and curr, a thread must hold the locks on both pred and curr. This guarantees that no other thread can be traversing past pred or modifying either pred or curr while we rewire the pointers.

Implementing Sorted Insertion

To make this practical, we'll implement insertion into a sorted linked list. This is a common and instructive use case because it forces us to traverse the list to find the correct insertion point, using the full hand-over-hand locking protocol. Insertion into an unordered list is simpler (often just an insertion at the head), but the sorted case better demonstrates the power of this technique.

Let's start by reviewing the basic structure of the node and list, which we'll base on the USENIX article from our last lesson. We'll use a dummy head node to simplify edge cases like inserting at the beginning of the list.

As a reminder, our node structure looks like this:

typedef struct node {
    pthread_mutex_t m;  // The mutex for this node
    int             data;
    struct node*    next;
} node_t;

Our task is to write a function, list_insert_sorted, that takes the list's head and a new value, and correctly inserts a new node while maintaining both sort order and thread safety.

The Insertion Algorithm

The core of the implementation combines traversal with the final insertion logic. Here is the step-by-step algorithm:

1. Allocate and Initialize: Create the new_node and initialize its data, next pointer, and its own mutex.
2. Start Traversal: Begin at the dummy head node. Lock it.
3. Hand-Over-Hand Search: Traverse the list using two pointers, pred and curr.
   • Hold the lock on pred.
   • Lock curr.
   • If curr is the right spot for insertion (i.e., curr->data >= value), stop. You now hold locks on pred and curr, the two nodes that will bracket your insertion.
   • If not, unlock pred, advance your pointers (pred = curr), and continue the traversal.
4. Perform Insertion: With both pred and curr locked, safely perform the pointer assignments:
   • new_node->next = curr;
   • pred->next = new_node;
5. Release Locks: Unlock pred and curr. The operation is complete.

The following resource provides excellent C-like pseudocode that illustrates this exact process.

Translating to C Code

Let's now translate that algorithm and pseudocode into a complete C function. We'll use a dummy head node, which simplifies the logic by ensuring that pred is never NULL and that insertion at the "start" of the list is handled by the same code path as insertion in the middle.

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>

// Assume node_t and a global 'head' are defined as in the USENIX article
// typedef struct node { ... } node_t;
// extern node_t head; // Dummy head node

void list_insert_sorted(node_t* head, int value) {
    // 1. Allocate and initialize the new node
    node_t* new_node = malloc(sizeof(node_t));
    if (new_node == NULL) {
        perror("malloc");
        return; // Or handle error more gracefully
    }
    new_node->data = value;
    pthread_mutex_init(&new_node->m, NULL);

    node_t* pred = head;
    node_t* curr = NULL;

    // 2. Start traversal by locking the predecessor (initially the dummy head)
    pthread_mutex_lock(&pred->m);
    curr = pred->next;

    // 3. Hand-over-hand search for the insertion point
    while (curr != NULL) {
        pthread_mutex_lock(&curr->m); // Lock the current node
        if (curr->data >= value) {
            // Found the spot. Break the loop while holding locks on pred and curr.
            break; 
        }
        
        // Didn't find it, so advance pointers.
        pthread_mutex_unlock(&pred->m); // Release the old predecessor
        pred = curr;                    // The current node is now the predecessor
        curr = curr->next;              // Move to the next node (which is currently unlocked)
    }

    // This block runs after the loop, either because we found a spot or reached the end.
    // In all cases, `pred` is locked.
    // If `curr` is not NULL, `curr` is also locked.

    // 4. Perform insertion
    new_node->next = curr;
    pred->next = new_node;

    // 5. Release locks
    if (curr != NULL) {
        pthread_mutex_unlock(&curr->m);
    }
    pthread_mutex_unlock(&pred->m);
}

Let's trace the locking logic in the while loop carefully.

• A thread locks pred.
• It then locks curr. Now it holds two locks.
• It checks if curr is the insertion point.
  • If yes, it breaks the loop, holding both locks. The state is perfect for insertion.
  • If no, it unlocks pred, making pred available to other threads. It then updates pred to be curr, and curr to be curr->next. At the end of the while block, it still holds the lock on the new pred (the old curr). The next iteration of the loop will then lock the new curr. This is the "hand-over-hand" motion.

This implementation correctly handles insertion at the beginning (right after the dummy head), in the middle, and at the end of the list.

A Note on Unordered Lists

While we focused on a sorted list, it's worth noting how much simpler insertion is if order doesn't matter. The USENIX article you've seen touches on this.

For an unordered list, you can simply insert at the head. The logic becomes:

1. Lock the dummy head node.
2. Set new_node->next = head->next.
3. Set head->next = new_node.
4. Unlock the dummy head node.

This is extremely fast because it involves only one lock and no traversal. This illustrates an important trade-off in concurrent data structure design: the functional requirements of the data structure (e.g., sorted vs. unordered) can have a dramatic impact on the complexity and performance of its concurrent implementation.

Conclusion

In this lesson, we successfully moved from design to a concrete C implementation. You have now learned how to write a thread-safe insertion function for a sorted linked list using fine-grained, hand-over-hand locking.

Key Takeaways:

• Insertion Point Safety: The critical operation of changing pred->next is only performed when the thread holds locks on both pred and curr, ensuring the list's integrity.
• Algorithm: The implementation combines a hand-over-hand traversal loop to find the insertion point with pointer manipulation inside the locked critical section.
• Dummy Head Nodes: Using a dummy head node is a powerful technique in C to simplify list algorithms, as it eliminates special-case logic for insertions at the beginning of the list or into an empty list.
• Sorted vs. Unordered: The complexity of insertion depends heavily on whether the list must be ordered. Unordered insertion can be a much faster, constant-time operation.

Preview of the Next Lesson:
We have now covered traversal design and insertion implementation. In the next lesson, we will round out the basic operations by tackling implementing the search operation for a linked list using fine-grained locking. This will be similar to the traversal we've already done, but we'll consider the specific requirements of a read-only operation.