Mutex implementation without built-ins

Question

I want to implement simplest mutex without built-in functions or the <pthread.h> module.

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <string.h> // strcpy
#include <unistd.h> // usleep

#define MICROS (1)
#define THREADS (300)
#define ACCESSES (1000000)

char * names[] = {"alpha",   "bravo",    "charlie", "delta", 
                  "echo",    "foxtrot",  "golf",    "hotel", 
                  "india",   "juliet",   "kilo",    "lima",
                  "mike",    "november", "oscar",   "papa", 
                  "quebec",  "romeo",    "sierra",  "tango", 
                  "uniform", "victor",   "whiskey", "x-ray", 
                  "yankee",  "zulu"};

void mutex_lock();
void mutex_unlock();

int mx = 0;
int counter = 0;
char pool[128] = {0};
pthread_t threads[THREADS];

void fill_pool(int number)
{
    int i;
    counter++;
    for (i = 0; i < 10000; i++)
        strcpy(pool, names[number % 26]);
}

void show_pool(int number)
{
    printf("%04d - %04d - %s\n", counter, number, pool);
    if (strcmp(pool, names[number % 26]))
    {
        printf("Thread race detected!\n");
        exit(1);
    }
}

void * thread_fnc(void * index)
{
    int number = (int)index;
    int i;
    for (i = 0; i < ACCESSES; i++)
    {
        usleep(random() % 1000);
        mutex_lock();
        {
            fill_pool(number);
            show_pool(number);
        }
        mutex_unlock();
    }    
}

int atomic_xchg(int * ptr, int val)
{
    unsigned int  tmp = val;
    __asm__(
        "xchgl %0, %1;\n"       
        : "=r"(tmp), "+m"(*ptr)
        : "0"(tmp)              
        :"memory");             
    return tmp;
}

int test_and_set(void)
{
    return atomic_xchg(&mx, 1);
}

void mutex_lock()
{
    while (test_and_set()) // Comment this line
                           // to test race
    {
        usleep(MICROS);
    }
}

void mutex_unlock()
{
    mx = 0;
}

int main()
{
    int i;    

    printf(" ##  - THRD - name\n");    

    for (i = 0; i < THREADS; i++)
        pthread_create(&threads[i], NULL, thread_fnc, (void *)i);

    for (i = 0; i < THREADS; i++) 
        pthread_join(threads[i], NULL);

    return 0;
}

This code works and does not fail after ~1 000 000 iterations. When I use simple while (mx) ... mx = 1 it fails after ~17 000 iterations.

Is this code totally thread-safe? I worry about passing pointer to atomic_xchg, since it needs dereferencing.

To compile:

gcc -pthread ./lock.c -o lock.s -lpthread && ./lock.elf`

Answer 1

I don't like the way the tests are mixed in with the function code here. It would be a lot easier to review (and to use) if there was clear separation of the two.

The inline (x86?) assembly code makes this program much less portable than one using <pthread.h> or compiler intrinsics. I'm assuming you're doing this for autodidactic reasons, not as part of your production code?

The polling approach in mutex_lock is fine for short waits - when code may be blocked for longer, it's normal to fall back to a more heavyweight approach (putting the thread on a wait queue) after a certain number of iterations.

mutex_unlock() seems to be missing a memory barrier to make the assignment visible to other threads.