Example of a Multithreaded C program

Question

In answering password cracker in c with multithreading, I ended up writing a sample in C, which is not my forte.

Is there anything that I missed which should have been included in a responsible sample (read: likely to be copied and pasted into production code)?

// compile with `gcc counter.c -o counter -lpthread -Wall -std=gnu99`
#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define SEARCH_THREAD_COUNT (10)
#define SEARCH_VALUE (21325)
#define SEARCH_MAX (INT_MAX)

typedef struct {
    int start;
    int end;
    int search;

    bool* shouldStop;
    int* answer;
    pthread_mutex_t* answerMutex;
    pthread_cond_t* answerFound;

    pthread_t thisThread;
} find_worker_init;

void* find_value(void* vpInitInfo) {
    find_worker_init* pUnitOfWork = (find_worker_init*)vpInitInfo;

    int cValue = pUnitOfWork->start;
    while (!(*(pUnitOfWork->shouldStop))) {
        if (cValue == pUnitOfWork->search) {
            printf("found value\n");

            // found the search value
            pthread_mutex_lock(pUnitOfWork->answerMutex);
            if (!(*(pUnitOfWork->shouldStop))) {
                *(pUnitOfWork->shouldStop) = true;
                *(pUnitOfWork->answer) = cValue;

                pthread_cond_broadcast(pUnitOfWork->answerFound);
            }
            pthread_mutex_unlock(pUnitOfWork->answerMutex);
            return NULL;
        }

        cValue++;
        if (cValue == pUnitOfWork->end) {
            // we exhausted our search space, end.
            printf("exhausted\n");
            return NULL;
        }
    }

    // we were usurped by another thread
    printf("usurped\n");
    return NULL;
}

int main( int argc, const char* argv[] ) {
    pthread_mutex_t answerMutex = PTHREAD_MUTEX_INITIALIZER;
    pthread_cond_t answerFound = PTHREAD_COND_INITIALIZER;
    bool shouldStop = false;
    int answer = -1;

    // initialize thread jobs
    find_worker_init startInfo[SEARCH_THREAD_COUNT];
    int current_search_start = 0;
    int search_unit = SEARCH_MAX / SEARCH_THREAD_COUNT;
    for (int i = 0; i < SEARCH_THREAD_COUNT; i++) {
        startInfo[i].start = current_search_start;

        // set the search space for this thread to be either the standard
        // search space, or for the last thread, whatever is remaining
        // (this is to prevent integer-division from skipping a portion
        // at the end)
        int current_size = (i == SEARCH_THREAD_COUNT - 1) 
            ? (SEARCH_MAX - current_search_start) 
            : search_unit;

        startInfo[i].end = current_search_start + current_size;
        startInfo[i].search = SEARCH_VALUE;

        startInfo[i].shouldStop = &shouldStop;
        startInfo[i].answer = &answer;
        startInfo[i].answerMutex = &answerMutex;
        startInfo[i].answerFound = &answerFound;
    }

    // start threads
    for (int i = 0; i < SEARCH_THREAD_COUNT; i++) {
        if (pthread_create(&(startInfo[i].thisThread), NULL, find_value, 
            &(startInfo[i]))) 
        {
            fprintf(stderr, "Error creating thread\n");
            return 1;
        }
    }

    // wait for answer to be found
    pthread_mutex_lock(&answerMutex);
    while (!shouldStop) {
        pthread_cond_wait(&answerFound, &answerMutex);
    }
    printf("signaled\n");

    // join
    for (int i = 0; i < SEARCH_THREAD_COUNT; i++) {
        if (pthread_join(startInfo[i].thisThread, NULL)) {
            fprintf(stderr, "Error joining thread\n");
            return 1;
        }
    }

    // answer
    printf("answer: %d\n", answer);

    pthread_mutex_unlock(&answerMutex);

    return 0;
}

Answer 1

Other than the problems the other post adressed (and the extra parentheses, unusual indentation and camel_casing really scream "I'm not comfortable driving this language" to me, which is not a bad thing, but it really stands out), you have one large problem with your code.

Your reading of the value pointed to by shouldStop violates the pthreads standard. Specifically this part: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_11

"Applications shall ensure that access to any memory location by more than one thread of control (threads or processes) is restricted such that no thread of control can read or modify a memory location while another thread of control may be modifying it."

This is not just to avoid race conditions as many people seem to believe. If you want your pthreads code to be fully portable you can't assume that it will be running on a cache coherent architecture. Which means that without calling one of the locking functions (or other memory synchronizing functions mentioned in there) you can't assume that you'll ever see the modified value of shouldStop.

This actually makes stopping worker threads really hard to get right. If you have a tight loop that is doing many cheap operations the overhead of locking on every loop step would be too high. You'd basically end up being contended on the lock and serialize the whole program and make the threads a waste of time. Even read rwlocks end up serializing things because of how the memory coherency protocol works on most CPUs.

Your best bet to stop worker threads is to check that condition with locking after "enough" work units have been performed. For some hand tuned value of "enough".

You could also use pthread_cancel, but it is very hard to get right as soon as you start doing something complex. As soon as you enable asynchronous delivery of cancellation you have to disable it in the parts of the code that allocate resources or take locks (to avoid resource leaks) and your code ends up being an endless mess of calls to pthread_setcancelstate.

Another option is to use <stdatomic.h> from C11. Which should work even though its interaction with pthreads isn't really standardized.

Or just ignore the problem like most of the world does. Because the people who run on architectures that aren't cache coherent are quite used to nothing working on their systems anyway.

Answer 2

Mitch, you have a nice program there. As I pointed out above, current_search_start is not updated which means 9 of 10 threads are searching the same space and the last searches the whole space. Minor error though.

Your use of condition variables and mutexes is nicely done. Overall, nothing significant to comment on.

Some minor comments:

• The precedence of -> is higher than that of * so this:

  if (!(*(pUnitOfWork->shouldStop))) {
  

  can be written:

  if (!(*pUnitOfWork->shouldStop)) {
  

  or some might prefer:

  if (*pUnitOfWork->shouldStop == false) {
  

  And

  *(pUnitOfWork->shouldStop) = true;
  

  can omit the parenthesis and be neater.

• I would change some variable names. cValue seems meaningless. pUnitOfWork would be just work. The p (and vp) prefixes you used look like Hungarian. I would never use such things unless forced to by an outdated coding convention.

• find_value should strictly be static

• The loop in find_value would be more normal as a for:

  for (int c = work->start; c < work->end; ++c) {
      if (*work->shouldStop) { ... }
      if (c == work->search) { ... }
  }
  

Also I would add a thread number and some debug to see which thread number is successful (especially with the current_search_start bug, as the thread is not always the same :-)