Concurrency and Race Conditions in Linux

Tip: For a better reading experience, it is recommended to read on a PC!

1

What are Concurrency and Race Conditions

In Linux systems, concurrency refers to the situation where multiple execution units (processes, threads, interrupts, etc.) access shared resources simultaneously or alternately, while a race condition refers to the uncertain behavior or errors caused by concurrent access.

2

Sources of Concurrency

• Interrupt handlers (can preempt current execution)

• Multiple processes/threads executing system calls simultaneously

• Multiple interfaces in kernel modules may be called concurrently

• Multi-core parallel execution in SMP (Symmetric Multi-Processing) environments

3

Methods for Handling Concurrency

To address the issues brought by concurrency, Linux has several methods:

1. Interrupt masking

2. Atomic operations

3. Spin locks

4. Semaphores

5. Mutexes

6. Completion variables

7. Read-write locks

Each of these methods for handling concurrency has its pros and cons, and the choice of which to use should be based on the actual situation.

3.1. Interrupt Masking

Usage:

local_irq_disable()  // Mask interrupts ....... code ....... local_irq_enable()  // Enable interrupts

The principle is to prevent the CPU from responding to interrupts. Generally, this method requires the code segment to be relatively short and not take up a lot of time.

3.2. Atomic Operations

Usage:

atomic_t v = ATOMIC_INIT(1); // Define atomic variable, initial value 1
// If the atomic variable decrements to 0, return true
if(atomic_dec_and_test(&v)){     ....    code    ...    atomic_inc(v); // Increment atomic variable by 1
}else{    atomic_inc(v);}

Atomic variables ensure that operations on an integer data type are exclusive. This means that the operation will not be interrupted by any other tasks or events until it is completed.Atomic variables can be thought of as integer variables that cannot be interrupted during operations, while ordinary integer variables can be interrupted.

3.3. Spin Locks

Usage:

spinlock_t lock = SPIN_LOCK_UNLOCKED; // Initialize spin lock
spin_lock(&lock); // Acquire spin lock
....// code....
spin_unlock(&lock); // Release spin lock

// Using irqsave to avoid deadlock caused by interrupt re-entry.
spin_lock_irqsave(&my_lock, flags);...
// code...
spin_unlock_irqrestore(&my_lock, flags);

Spin locks are a typical means of mutually accessing critical resources. When a spin lock is already held by another thread, another thread trying to acquire the spin lock will wait (spin in place). Recursive calls to spin locks can lead to system deadlocks.

3.4. Read-Write Locks

Usage:

rwlock_t lock;
rwlock_init(&lock);
// Acquire read lock
read_lock(&lock);
// Read critical section
read_unlock(&lock);
// Acquire write lock
write_lock(&lock);
// Write critical section
write_unlock(&lock);

Read-write locks are derived from spin locks. They allow multiple “readers” to access shared resources simultaneously, but when there is a “writer”, exclusive access to the resource is required. During writing, all other writes and reads are blocked, while during reading, multiple reads are allowed. Therefore, they are generally used in scenarios with “frequent reads and occasional writes”.

3.5. Semaphores

Usage:

struct semaphore sem;
sema_init(&sem, 1); // Initialize semaphore to 1, greater than 0 indicates free

down(&sem); // Decrement semaphore, if greater than or equal to 0, continue execution, otherwise sleep...
// code...
up(&sem); // Increment semaphore, if greater than 0, wake up processes in the waiting queue.

Unlike spin locks, when a semaphore cannot be acquired, the process does not spin in place but instead enters a sleep waiting state.Newer Linux kernels tend to use mutexes directly as a means of mutual exclusion, and semaphores are no longer recommended for mutual exclusion.

3.6. Mutexes

Usage:

struct mutex my_mutex;  // Define mutex
mutex_init(&my_mutex);  // Initialize mutex
mutex_lock(&my_mutex);  // Acquire mutex...
// code...
mutex_unlock(&my_mutex);  // Release mutex

When a process occupies a resource for a long time, using a mutex is preferable.

3.7. Completion Variables

Usage:

DECLARE_COMPLETION(com); // Define and initialize completion variable.
wait_for_completion(&com); // Thread enters sleep
complete_all(&com); // Wake up all waiting queue

The mechanism of completion variables is to implement a thread sending a signal to notify another thread that a certain task is complete. A thread calls wait_for_completion and then enters sleep, while another thread sends a notification to the sleeping thread after completing a task, allowing it to execute the code following wait_for_completion.

4

API Functions

4.1. Atomic Operations

// Define atomic variable v and initialize to 0
atomic_t v = ATOMIC_INIT(0); 
// Get the value of the atomic variable
atomic_read(atomic_t *v);
// Set the value of the atomic variable
void atomic_set(atomic_t *v, int i); /* Set the atomic variable to i */
// Atomic variable add/subtract
void atomic_add(int i, atomic_t *v); /* Add i to atomic variable */
void atomic_sub(int i, atomic_t *v);/* Subtract i from atomic variable */
// Atomic variable increment/decrement
void atomic_inc(atomic_t *v); /* Increment atomic variable by 1 */
void atomic_dec(atomic_t *v); /* Decrement atomic variable by 1 */
// Atomic variable increment/decrement, and return the value of v
int atomic_inc_return(atomic_t *v);
int atomic_dec_return(atomic_t *v);
// Operate and test
// Increment, decrement, and subtract operations on the atomic variable, testing if it is 0, returning true if 0, otherwise false
int atomic_inc_and_test(atomic_t *v);
int atomic_dec_and_test(atomic_t *v);
int atomic_sub_and_test(int i, atomic_t *v);

4.2. Spin Locks

// Define and initialize spin lock
DEFINE_SPINLOCK(spinlock_t lock) // Define and initialize spin lock
spinlock_t lock;
spin_lock_init(lock);
// Acquire spin lock
void spin_lock(spinlock_t *lock);/* If acquisition fails, it will spin in place */
void spin_trylock(spinlock_t *lock);/* If acquisition fails, return false, will not spin in place */
// Release spin lock
void spin_unlock(spinlock_t *lock);
// Disable local interrupts and acquire spin lock
void spin_lock_irq(spinlock_t *lock);
// Enable local interrupts and release spin lock
void spin_unlock_irq(spinlock_t *lock);
// Save interrupt state, disable local interrupts, and acquire spin lock
spin_lock_irqsave(lock, flags)  /* This is a macro */
// Restore interrupt state to previous state, enable local interrupts, and release spin lock
void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);

4.3. Read-Write Locks

// Define and initialize read-write lock
DEFINE_RWLOCK(x);
// Initialize read-write lock
rwlock_init(lock);
/************Read Lock*****************/
// Acquire read lock
read_lock(lock);
// Release read lock
read_unlock(lock);
// Save interrupt state, disable local interrupts, and acquire read lock
read_lock_irqsave(lock, flags);
// Restore interrupt state to previous state, enable local interrupts, and release read lock
read_unlock_irqrestore(lock, flags);
/************Write Lock*****************/
// Acquire write lock
write_lock(lock);
// Release write lock
write_unlock(lock);
// Save interrupt state, disable local interrupts, and acquire write lock
write_lock_irqsave(lock, flags);
// Restore interrupt state to previous state, enable local interrupts, and release write lock
write_unlock_irqrestore(lock, flags); 

4.4. Semaphores

// Define and initialize semaphore
DEFINE_SEMAPHORE(name);
// Define and initialize semaphore
struct semaphore sem;
void sema_init(struct semaphore *sem, int val);
// Acquire semaphore
void down(struct semaphore *sem);/* This function will cause sleep, so it cannot be used in interrupt context */
int down_trylock(struct semaphore *sem); /* Try to acquire semaphore, if successful, return 0. If not, return non-zero and will not sleep. */
// Release semaphore
void up(struct semaphore *sem);/* Release semaphore, wake up waiters */

4.5. Mutexes

// Define and initialize mutex
DEFINE_MUTEX(mutexname);
// Define and initialize mutex
struct mutex my_mutex;
mutex_init(&my_mutex);
// Acquire mutex
void __sched mutex_lock(struct mutex *lock);/* If cannot acquire, enter sleep */
int mutex_trylock(struct mutex *lock);/* Try to acquire mutex, if successful return 1, if failed return 0, will not sleep */
// Release mutex
void __sched mutex_unlock(struct mutex *lock);
// Check if mutex is locked
bool mutex_is_locked(struct mutex *lock);

5

Conclusion

(1) When using shared resources in interrupts, only spin locks should be chosen, not semaphores, as semaphores can cause processes to enter sleep.(2) Spin locks do not allow blocking during the locking period, so the critical section must be small. Mutexes allow blocking in the critical section and can be suitable for larger critical sections.

(3) The most commonly used in drivers are mutexes.

Previous Recommendations:

Linux Kernel Linked List

In-depth Understanding of Widgets

In-depth Understanding of Kcontrol

Introduction to Linux Audio Application Development

Analysis of Linux Drivers: Sound Card Driver