Is there a TestAndSet(volatile int *lock) function in a common C library?

Question

...or do I have to write my own? (BTW I'm working in C)

I'm writing an implementation similar to what's on wikipedia:

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1);
    critical section // only one process can be in this section at a time
    lock = 0 // release lock when finished with the critical section
}

But I can't seem to find a prebuilt TestAndSet(volatile int *lock).

Examples of what they might look like include:

#define LOCKED 1
int TestAndSet(volatile int* lockPtr) {
    int oldValue;
    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    return oldValue;
}

Ideally I'd like something that can work on both linux and windows. As well, I've read that the execution of atomic instructions is hardware dependant. I'm not sure this plays into things or how to tell if hardware supports it, and then run an alternative.

Thank you!

Additional contextual info: The reason I'm asking this question is for the development of a set of functions for accessing a data structure (e.g. add() fetch() delete() etc...) Several threads are accessing it for modification and for real-time displaying of certain elements.

Mutexes: I voted against mutexes (correct me if my rationale is ill-founded) because the critical area is not the entire hash table, but the specific member being accessed by a given function. So using a mutex would result in a bottleneck in performance of the whole data structure.

Alternative: What led me to looking at TestAndSet() is because it made more sense to put a "beingAccessed" flag on each element in the data structure. This flag would be checked by a function that wanted to access it, be set to true if it were false and then the function would do what it had to, then release that one element without freezing up the whole structure.

Comment @M.M: The sample implementation didn't feel right for the reason @chux and you both mention. For the busy wait, it's my understanding that it's used at a low level to develop higher level synchronization mechanisms. Please see my edit above re: mutexes. The volatile was not an attempt to ensure atomicity, but to ensure the value was loaded each time it was accessed when it was being checked by an atomic function because several threads could modify that variable at any time. The atomicity I imagine/am hoping is provided by the function acting on the variable in question. Question specific to something you wrote: your code says “Note: do not use "volatile"” but the standard function prototype you provided is volatile, so is the non volatile flag variable cast as volatile in the atomic function? Thank you.

Answer 1

C11 contains new atomic library that provides this functionality. See the atomic_flag_test_and_set functions; just replace your int* with an atomic_flag*

You may want to just use the mutex (mtx_*) functions provided in C11's threads.h, instead of rolling your own synchronization.

Answer 2

In the C11 standard, your flag would look like:

#include <stdatomic.h>

// Lock-free atomic flag, initially unset. Note: do not use "volatile"
atomic_flag lock = ATOMIC_FLAG_INIT;

and there is a standard functions:

_Bool atomic_flag_test_and_set(volatile atomic_flag *object);

which performs the operation you require.

Note that your sample implementation is invalid because the flag may be changed by another thread in between the read and write of lock_ptr. I tested with clang 3.7 and gcc 5.x, and they implemented atomic_flag_test_and_set as the XCHG assembly instruction.

---

Also, your Critical function implements a "spin lock", i.e. it's going to max out the CPU continually banging away at attempting to change the flag. This is only a good idea for cases when the lock will only ever be held for a handful of CPU cycles. For further reading on this topic see this thread.

For a normal use where the code protected by the critical section may make a system call, it would be preferable to use an operating system facility to do a non-busy wait on the flag.

The C11 Thread Library includes a mutex. As of 2015, apparently no major compiler/library combo natively supports C11 thread, although as answered on that thread there is a github project which implements C11 threads over POSIX threads.

Of course you could use the time-honored technique of #if to select a CRITICAL_SECTION in Windows, and the pthread library mutex in all other OSs.

---

On the use of volatile: this is neither necessary nor sufficient for multithreading.

It's not sufficient because it does not guarantee atomicity. A volatile object may still be read/written simultaneously by multiple threads (data race, UB). You must use atomic objects, either using the C11 Atomics or a compiler-specific atomic feature.

And it's not necessary because , since C11, the language specification includes memory ordering rules that prevent the compiler re-ordering operations on atomics. You can read more about the various supported memory ordering models in the C11 standard (or N1570).

volatile sig_atomic_t was recommended in C99 as a bit of a hack, because the C99 Standard did not have any notion of a memory fence. However, moving forward, now that actual atomics are available , the volatile hack should be consigned to the trash heap.

Answer 3

This is often done with either inline assembly language or compiler extensions. For instance you can use GCC Atomic Functions in both Linux and Windows. Microsoft C compiler might have something equivalent.

Answer 4

On Linux (and generally all *nix-es) you can use pthread:

#include <pthread.h>
pthread_mutex_t mutex;
void init_mutex() {
    pthread_mutex_init(&mutex, NULL);
}
void lock_mutex() {
    pthread_mutex_lock(&mutex);
}
void release_mutex() {
    pthread_mutex_unlock(&mutex);
}
void delete_mutex() {
    pthread_mutex_destroy(&mutex);
}

You can off course get a pointer to mutex and cast it to int*, but it's non-sense! These four functions do:

• init_mutex - Call on program start, initialize resources may be even called before main (mark it with __attribute__((constructor)) before "void" keyword.
• delete_mutex - Call on program finish, release resources.
• lock_mutex - Will lock your lock, not allowing other threads to access this function (there is no way to restrict it between processes).
• release_mutex - Call it to let runtime know that critical section has ended and it's ready to accept next thread.

These functions will build a queue of threads waiting on mutex. See this example (six threads):

A -> B -> C -> D -> E -> [MUTEX] -> F (critical) -> [MUTEX END]
[F] release_mutex
A -> B -> C -> D -> [MUTEX] -> E (critical) -> [MUTEX END] -> F

I don't know a way to do it on Windows. if you think about something generic for Linux and Windows, it's not good. If you think about hardware, I have to say NO! Threads are managed by kernel (sometimes by C library).