Thread-Safe Hash Table Insertion with Per-Bucket Locking

The Anatomy of an Insertion

Let's start with a typical non-thread-safe insert function for a hash table that uses separate chaining. This will be our baseline for modification.

int HashTable_Insert(HashTable* table, const char* key, int value) {
    // 1. Calculate bucket index
    unsigned int index = hash(key) % TABLE_SIZE;

    // 2. Allocate a new node
    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        return -1; // Allocation failed
    }

    // strdup allocates memory for the key and copies it
    new_node->key = strdup(key); 
    if (new_node->key == NULL) {
        free(new_node);
        return -1; // Allocation failed
    }
    new_node->value = value;

    // 3. Link the new node at the head of the list
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;

    return 0; // Success
}

This code works perfectly in a single-threaded context. However, as we discussed previously, the section labeled "3. Link the new node" is a critical section. If two threads execute this section concurrently on the same bucket, a race condition will occur, leading to lost data.

Implementing the Locking Protocol

To make this function thread-safe according to our design, we must wrap the critical section with the appropriate per-bucket lock. The protocol is:

1. Calculate the bucket index.
2. Acquire the lock for that specific bucket.
3. Perform the linked list modification.
4. Release the lock for that bucket.

The following reading provides a clear, commented C implementation of inserting into a concurrent linked list. Since each bucket in our hash table is a linked list, this logic is exactly what we need.

From Basic to Optimized Locking

Let's integrate the insights from that reading into our HashTable_Insert function.

Version 1: Basic Locking

The simplest correct approach, as seen in Figure 29.7, is to lock around the entire operation, including memory allocation.

int HashTable_Insert_V1(HashTable* table, const char* key, int value) {
    unsigned int index = hash(key) % TABLE_SIZE;

    pthread_mutex_lock(&table->locks[index]); // Lock the bucket

    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        pthread_mutex_unlock(&table->locks[index]); // IMPORTANT: Unlock on error
        return -1;
    }

    new_node->key = strdup(key);
    if (new_node->key == NULL) {
        free(new_node);
        pthread_mutex_unlock(&table->locks[index]); // Unlock on error
        return -1;
    }
    new_node->value = value;

    // CRITICAL SECTION
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
    // END CRITICAL SECTION

    pthread_mutex_unlock(&table->locks[index]); // Unlock on success

    return 0;
}

This code is thread-safe. A crucial detail is ensuring the mutex is unlocked before returning from an error condition. Forgetting to do so would cause any other thread waiting on that bucket to deadlock permanently.

Version 2: Optimized Locking (Reducing Lock Contention)

As you saw in Figure 29.8, we can improve performance by minimizing the time a lock is held. Memory allocation (malloc, strdup) can be a relatively slow system call. More importantly, it operates on memory that is not yet part of the shared data structure—the new_node is private to the inserting thread until it's linked into the list.

Therefore, we can safely perform the allocations before acquiring the lock. This reduces lock contention, as threads will spend less time holding the lock, waiting on malloc.

This leads to a more efficient implementation:

int HashTable_Insert(HashTable* table, const char* key, int value) {
    // 1. Allocate and prepare the new node first (outside the lock)
    Node* new_node = malloc(sizeof(Node));
    if (new_node == NULL) {
        return -1; 
    }
    new_node->key = strdup(key);
    if (new_node->key == NULL) {
        free(new_node);
        return -1;
    }
    new_node->value = value;

    // 2. Calculate bucket index
    unsigned int index = hash(key) % TABLE_SIZE;

    // 3. Lock the specific bucket
    pthread_mutex_lock(&table->locks[index]);

    // 4. Link the node (the actual critical section)
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;

    // 5. Unlock the bucket
    pthread_mutex_unlock(&table->locks[index]);

    return 0; // Success
}

This second version is functionally identical in terms of thread safety but is superior in terms of performance design. It follows a key principle of concurrent programming: hold locks for the shortest possible duration.

A Practical Implementation Challenge

Now it's time to apply this yourself. The following exercise is based on a lab from MIT, where students are given a non-thread-safe hash table and asked to fix it. This is an excellent, practical test of your understanding.

The lab provides a file ph.c. Here are the relevant data structures and the non-thread-safe put function (their version of insert).

#define NBUCKET 5

// An entry in a bucket's linked list
struct entry {
  struct entry *next;
  char *key;
  int value;
};

// The hash table, modified to include our per-bucket locks
struct ph {
  pthread_mutex_t locks[NBUCKET]; // One lock per bucket
  struct entry *buckets[NBUCKET];
};

// The non-thread-safe put function
static void 
put(struct ph *t, char *key, int value)
{
  int i;
  struct entry *e;

  i = hash(key) % NBUCKET; // Simplified hash for example

  // Does not check for existing key, just inserts at head
  e = malloc(sizeof(struct entry));
  e->next = t->buckets[i];
  e->key = key; // Note: In the real lab, key is not copied, we assume it is.
  e->value = value;
  t->buckets[i] = e;
}

Your task is to rewrite the put function to make it thread-safe using our optimized, per-bucket locking strategy.

static void 
put(struct ph *t, char *key, int value)
{
  int i;
  struct entry *e;

  // Allocate memory outside the lock
  e = malloc(sizeof(struct entry));
  // A robust implementation would check for malloc failure
  // For simplicity here, we omit the check.
  e->key = key;
  e->value = value;

  // Calculate index
  i = hash(key) % NBUCKET;

  // Acquire the correct lock
  pthread_mutex_lock(&t->locks[i]);

  // Link the node into the list
  e->next = t->buckets[i];
  t->buckets[i] = e;

  // Release the lock
  pthread_mutex_unlock(&t->locks[i]);
}

Conclusion

Congratulations! You have successfully implemented a thread-safe insertion operation for a concurrent hash table. You've moved from theoretical design to practical, optimized code.

Key Takeaways:

• A thread-safe insert requires wrapping the linked list modification in a critical section protected by a mutex.
• The correct mutex to use is the one corresponding to the specific bucket being modified (table->locks[index]).
• It is crucial to release the mutex on all possible function exit paths, including error conditions, to prevent deadlocks.
• For optimal performance, expensive operations that don't access shared data (like malloc) should be performed before acquiring the lock to minimize lock hold time.

Preview of the Next Lesson:
With insertion secured, our next step is to implement a thread-safe lookup operation. This will involve the same per-bucket locking protocol, but we'll begin to see how read-only operations behave differently from write operations, setting the stage for more advanced concepts like read-write locks later in the course.