Using Semaphores and Mutex in Linux Device drivers to tackle concurency

Semaphores provide a satisfactory solution for issues related to concurrency . Access to critical section is controlled by enforcing threads to hold a lock before entering the critical section , Without a semaphore being unlocked no thread is allowed access to execute in the critical section .

Semaphore is a single integer value bound to two functions P and V . P is called down or some variation of that name and V is called up . Function P is used to lock the critical region and V is used to unlock . Function P decreases the count of semaphores , for example from 1 to 0 . When the value of the semaphore still remains 0 or less no other threads are allowed to execute in the critical region . There are made to wait or even may be put to sleep till the region is unlocked .

Functions of type V releases the semaphores that’s being help , these category of functions increases the value count of the semaphore and may even wake up the processes waiting for the access into the critical region .

Semaphores are generally and mostly used for the purpose of mutual exclusion , that is to make sure that only one thread of execution or a process executes in the critical section .

 Linux Implementation of Semaphores

<asm/semaphore.h> defines several functionalities for semaphore and mutex implementation ( Mutexes are just a special case of semaphores ) .

To initialize a declared semaphore ,

void sema_init(struct semaphore *sema, int val) can be used ,

 this initializes the declared mutex to value val ( The second argument to the function ) ;

But , as i had mentioned earlier semaphores are generally used for implementation of mutex ,

the following two functions declare and initialize the mutex

DECLARE_MUTEX(mutex_name ) ;

DECLARE_MUTEX_LOCKED(mutex_name) ;

 These functions declares mutex named as ‘mutex_name’ , the function DECLARE_MUTEX declares the mutex and initializes it to 1 ( 1 is the unlocked state , a thread or a process can possibly lock the critical region ) , wherein the later function declares the mutex and initializes it to 0 ( 0 is the locked state ) , mutex has to be explicitly unlocked before it can be used for locking .

 

 For initializing the mutex at runtime the following functions can be used ,

void init_MUTEX(struct semaphore *sema ) ;

void init_MUTEX_LOCKED(struct semaphore *sema) ;

 Holding and releasing Mutex ( The version of P [down] and V[up] functions )

 Linux kernel provides three versions of down function

  1. void down(struct semaphore *sema) ;

  2. int down_interruptible(struct semaphore *sema) ;

  3. int down_trylock(struct semaphore *sema ) ;

As briefed earlier down decrements the value of the semaphore , successful exection of any version of down function leads to locking of the critical region of the code , and the thread of execution or the process is said to have acquired the lock . Other user space process trying to access the critical region of code will be made to wait .

In case of the first version of down ( void down_interruptible() ) , the user space process waiting for the mutex to be released cannot to interrupted , it’ll be running in a dreaded state . This is not desirable in many cases , so the second version of down allows the waiting user space process to be interrupted .

The third version can used to test and lock , if the lock is already being held the function returns with a negative value , If no other thread is holding the lock , the lock will be acquired . Using down_trylock() the process wont wait for the acquired lock to be released , it returns immediately .

void up(struct semaphore * sema) is used to unlock the acquired lock and even wake up the processes waiting on the semaphore .

When executing in the critical region on occurance of error its very important to unlock the region before returning

 

 

 

 

 

Concurrency issues in Linux Device Drivers and protection from concurrency

Concurrency was not a big issue till kernel support was introduced for SMP systems . Before there were only few sources of concurrency like the interrupt handling context , but with introduction of kernel support for SMP systems it also drastically increased the chances of  code being vulnerable for concurrency issues .SMP (Symmetric Multi Processing ) systems involve architecture with multiple processors , this introduces the possibility of the same code snippet being run in more than one processors at a given point of time . Codes running in kernel context are pre-emtible too , it may lose the processor at any point of time and the process scheduled next may run in your driver .There are surprisingly many ways where the Device Driver or a program running in kernel context becomes vulnerable for concurrency related issues , In the computing world where one in a million probable event too can happen every second bugs related to concurrency are difficult to identify even for expert kernel developers .

Reasons for concurrency

Consider this small code snippet in your driver

if(!dptr->data[block]) { //1.check whether memory is already allocated 
    dptr->data[block] = kmalloc(block_size , GFP_KERNEL); //2.allocate memory if its not allocated 
    if(!dptr->data[block] ) //3.check whether the memory allocation was successful 
         end the program ; 4.//exit if memory allocation fails 
}

Consider the case wherein processes A and B both try to access the driver . When both A and B arrives at the condition to check for memory allocation (line 1 ) , both predicts the memory to be not to be allocated and moves ahead executing the lines to follow allocating the memory .

The second process to allocate memory by executing kmalloc() wipes out the memory allocated by the first process . The second process gets the inconsistent view of the variable .

Such piece of code which is vulnerable for concurrency related bugs should be protected , such snippet of code is called as critical region of code . Critical region code should be protected from concurrent access , access to the critical region of code should be controlled and managed .

There are few rules following which the concurency related issues can be minimized and solved .Reduce the use of shared resources

  1. Hardware resources are shared and likewise many structures and variables too are accessible for any no.of.threads of execution , unless there is a strong reason its better not to make use of shared resoures ( like global variables ) .If there are no shared resources there wont be any concurrency issues , but sharing is often required and all varialbles in the driver by default is accessible all threads of execution .

  2. Use kernel’s locking primitives to manage and control access to critical region, if critical section of code is secured or prevented from multiple processes to execute simultaneously the issue can be solved .Kernel Provides different primitives to handle concurrency related issues since the triggering factor for all concurrency related issues are not same . Concurrency in the driver may be purely due to access from user space or code executed by asynchronous events like interrupt handling or kernel timer mechanisms . 

Ways of protecting critical section of code from concurrent access and kernel primitives and API’s that can be used in device drivers to protect the critical section of code will be discussed in the next post . Till then have great time coding ……….. 🙂