Concurrency and Race Condition in Linux 2.6

Summary：
This document is a brief summary of reading Concurrent and Race Condition chapter of Linux Device Driver.

1 Mutual exclusion Operations
1.1 Semaphores
Semaphores in Linux system is used for mutual exclusion operations.
It needs to get semaphore firstly that thread want to come into the critical section protected by semaphore. If semaphore has held by another thread, thread want to come into critical section will to go to sleep and this thread will be woke up by kernel later.

To use semaphores, code need include .

1.1.1 Create a Semaphore
struct semaphore sem;
void sema_init(struct semaphore *sem, int val)
void init_MUTEX(struct semaphore *sem)
void init_MUTEX_LOCKED(struct semaphore *sem)

DECLARE_MUTEX(name)
DECLARE_MUTEX_LOCKED(name)

1.1.2 Hold a Semaphore
void down(struct semaphore *sem)
It can be broke by interruption, when it is blocking for hold the “Semaphore”.

void down_interruptible(struct semaphore *sem)
It can not be broke by interruption, when it is blocking for hold the “Semaphore”.

void down_trylock(struct semaphore *sem)
It is not be blocked when request to hold a semaphore.

1.1.3 Release a Semaphore
void up(struct semaphore *sem)

1.2 Spin Lock
“Spinlock” is a lock that is used to mutual exclusion. It is different from “Semaphore” that using “Spinlock” will not bring thread into sleeping. It will run like a loop to check the lock status.

To use “Spinlock”, we need to include .

1.2.1 Create Spinlock
spinlock_t my_lock = SPIN_LOCK_UNLOCKED;

void spin_lock_init(spinlock_t *lock);
1.2.2 Hold a Spinlock
void spin_lock(spinlock_t *lock);
It cannot be broke by interruption during blocking for hold a lock. The procedure in critical section that protected by Spinlock should not be broke by interruption or be forced to go to sleep for any blocking operations.

spin_lock_irqsave
Before into the critical section, it disables the IRQ and save the status of current IRQ.
spin_lock_irq
Before into the critical section, it disables the IRQ but not save the status of current IRQ.
spin_lock_bh
Before into the critical section, it disables the software IRQ but still enable the hardware IRQ.

spin_trylock
spin_trylock_bh
These two APIs are not block during the requesting of hold Spinlock.

1.2.3 Release a Spinlock
Void spin_unlock(spinlock_t *lock);

spin_unlock_irqrestore
spin_unlock_irq
spin_unlock_bh

2 Synchronization Operations
2.1 Completions
“Completions” in Linux is used to synchronize tasks between threads.
To use “Completions”, we need to include .

2.1.1 Create a “Completions”
DECLARE_COMPLETION(my_completion)

Struct completion my_completion;
Init_completion(&my_completion);

2.1.2 Wait for Completed
void wait_for_completion(struct completion *c)
It cannot be broke by interruption during the waiting for “Completion”.

Flowing APIs defined in Linux kernel version more than 2.6.11.
unsigned long wait_for_completion_timeout(struct completion *x, unsigned long timeout)
int wait_for_completion_interruptible(struct completion *x)
unsigned long wait_for_completion_interruptible_timeout(struct completion *x, unsigned long timeout)

2.1.3 Wake up waited threads
void complete(struct completion *c)
Wake up one thread that is waiting for.

void complete_all(struct completion *c)
Wake up all threads that are waiting for.
After call complete_all API, we need to reinitialize the “Completion” using INIT_COMPLETION.

2.2 Wait Queue
If want a process or thread go to sleep for waiting to get a special condition, we can use “Wait Queue”. What difference between “Wait Queue” and “Completion” is “Wait Queue” can check the condition before or after sleep.

2.2.1 Create a “Wait Queue”
DECLARE_WAIT_QUEUE_HEAD(name)

wait_queue_head_t my_queue;
init_waitqueue_head(&my_queue);

2.2.2 Wait for expected condition
wait_event(queue, condition)
“queue” is the head of “Wait Queue”. “condition” is an expression used to evaluate the condition.

wait_event_interruptable(queue, condition)
It can be broke during sleeping.

wait_event_timeout(queue, condition, timeout)
wait_event_interruptable_timeout(queue, condition, timeout)

2.2.3 Wake up waiting thread of process
wake_up(wait_queue_head_t *queue)
wake_up_interruptable(wait_queue_head_t *queue)