4
\$\begingroup\$

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;
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Can you please revise the title to state the exact purpose of the code? \$\endgroup\$
    – Jamal
    Oct 6, 2014 at 2:55
  • \$\begingroup\$ @Jamal, happily. What would you suggest? The purpose of my post is to find out if I missed anything in providing an example of a multithreaded C program. Beyond that, the program is an absurdly inefficient way of saying int answer = SEARCH_VALUE; print answer; \$\endgroup\$
    – Mitch
    Oct 6, 2014 at 5:30
  • \$\begingroup\$ Perhaps something that describes this example, if possible. \$\endgroup\$
    – Jamal
    Oct 6, 2014 at 5:38
  • \$\begingroup\$ current_search_start is not updated. Problem? \$\endgroup\$ Oct 6, 2014 at 18:19
  • \$\begingroup\$ @WilliamMorris, good catch. \$\endgroup\$
    – Mitch
    Oct 6, 2014 at 18:51

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Just when you start to think you understand memory accesses... ugh. Thank you for the reference to stdatomic.h. \$\endgroup\$
    – Mitch
    Nov 1, 2014 at 21:07
3
\$\begingroup\$

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 :-)

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.