Fine-Grained Locking for Linked List Search

Revisiting the Traversal Protocol

At its core, a search is a traversal. Let's start by reviewing the general-purpose, hand-over-hand traversal function from the "COLUMNS" article by Terence Kelly, which we have used as a reference. This code provides the blueprint for any safe traversal of our fine-grained list.

The key insight from this hoh() function is the locking order: LOCK(n) happens before UNLK(p). For a brief moment, the traversing thread holds locks on two consecutive nodes.

Why is Hand-over-Hand Locking Necessary for a Search?

In the last lesson, holding two locks was necessary to safely modify pred->next. But a search doesn't modify anything. So, why can't we use a simpler protocol, like this?

1. Lock curr.
2. Read curr->data and next_ptr = curr->next.
3. Unlock curr.
4. curr = next_ptr and repeat.

This seemingly logical approach contains a critical race condition. Between steps 3 and 4, another thread could acquire locks on the node before curr and on curr itself, and then delete curr. When our search thread then tries to execute curr = next_ptr and later lock this new curr, it would be dereferencing a dangling pointer, leading to a crash or undefined behavior.

The hand-over-hand protocol prevents this. By locking the next node n while still holding the lock on the predecessor p, you guarantee that n is a valid, live node. Another thread cannot delete n because it would first need to acquire the lock on p, which your search thread is still holding. Once you have safely secured the lock on n, you can release the lock on p and proceed.

Therefore, the correct traversal protocol for a read-only search is the same as for an insert: you must use hand-over-hand locking to guarantee the integrity of the traversal itself.

Implementing the Search Function

Now, let's adapt the traversal logic into a concrete list_search function. The function will traverse the list using the hand-over-hand protocol. Inside the loop, after securing the lock on the current node curr and releasing the predecessor pred, we will check if curr->data matches the value we're looking for.

Here is a C implementation. This code assumes the same node_t structure with an embedded pthread_mutex_t and a dummy head node.

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

// Assume node_t and list_t are defined as before:
// typedef struct node {
//     int             data;
//     pthread_mutex_t m;
//     struct node*    next;
// } node_t;

/**
 * Searches for a value in a sorted linked list using hand-over-hand locking.
 * Returns 1 if the value is found, 0 otherwise.
 * head: Pointer to the dummy head node of the list.
 * value: The integer value to search for.
 */
int list_search(node_t* head, int value) {
    node_t* pred = NULL;
    node_t* curr = NULL;
    int found = 0;

    pred = head;
    pthread_mutex_lock(&pred->m); // Start by locking the dummy head

    curr = pred->next;
    while (curr != NULL) {
        pthread_mutex_lock(&curr->m); // Lock the current node (hand-over)

        // Now that `curr` is locked, we can safely release `pred`
        pthread_mutex_unlock(&pred->m);

        if (curr->data == value) {
            found = 1; // Found the value
            // We can break the loop and exit.
            // `curr` is still locked, so we must unlock it before returning.
            break;
        } else if (curr->data > value) {
            // In a sorted list, if we see a larger value, the target is not present.
            break; 
        }

        // Advance pointers for the next iteration
        pred = curr;
        curr = curr->next; // `curr->next` is safe to read while `curr` is locked
    }

    // --- Cleanup Phase ---
    // The loop can terminate in three ways:
    // 1. `curr` is NULL (end of list reached). `pred` is the last node and is locked.
    // 2. `found` is true. `curr` is the found node and is locked.
    // 3. `curr->data > value`. `curr` is the first node > value and is locked.
    
    // If the loop broke, `curr` is not NULL and its lock is held. We must release it.
    if (curr != NULL) {
        pthread_mutex_unlock(&curr->m);
    } else {
        // If the loop ran to completion, `curr` is NULL, but `pred` (the last node) is still locked.
        pthread_mutex_unlock(&pred->m);
    }

    return found;
}

Let's carefully analyze the code's logic:

1. Initialization: We lock the dummy head node to begin the traversal safely.
2. The Loop: The while loop iterates as long as curr is not NULL.
3. Hand-over-Hand: The first action in the loop is to pthread_mutex_lock(&curr->m). Immediately after, we pthread_mutex_unlock(&pred->m). At this point, only curr is locked by our thread. This is the "hand-over-hand" step that ensures safe traversal.
4. Search Logic: We check curr->data. Since our list is sorted, we can stop not only on a match but also if we find a value greater than our target.
5. Pointer Advancement: We set pred = curr and then read curr->next. This read is safe because we hold the lock on curr.
6. Cleanup: This is a crucial and tricky part. When the loop terminates, a lock is still being held.
   • If we broke the loop (curr is not NULL), we must unlock curr.
   • If the loop finished naturally (curr is NULL), the last node we locked was pred, which we must unlock.

Conclusion

In this lesson, we completed the implementation of a thread-safe search operation for our fine-grained linked list. While the operation is read-only, we discovered that the hand-over-hand locking protocol is still essential—not for modifying pointers, but for ensuring the structural integrity of the traversal itself.

Key Takeaways:

• Safe Traversal is Paramount: The primary role of hand-over-hand locking in a search context is to prevent a thread from following a dangling pointer if another thread deletes a node concurrently.
• Identical Traversal Protocol: The core traversal mechanism (lock-next, unlock-previous) is the same for search, insertion, and deletion. The differences lie in what you do once the locks are acquired.
• High Concurrency for Reads: Although the protocol is the same, search operations are highly concurrent. Because a search thread only holds a lock on one node at a time while inspecting data, multiple searchers can "stream" through the list without blocking one another.
• Careful Lock Management: Implementing these functions requires meticulous attention to lock and unlock calls, especially in the cleanup phase after a loop terminates.

Preview of the Next Lesson:
We have now designed the hand-over-hand protocol and used it to implement both insertion and search. We are leaving linked lists for now and moving on to another fundamental data structure. In the next lesson, we will begin our work on a concurrent hash table by first designing a basic hash table data structure using separate chaining. We will then build on that design to make it thread-safe.