Linux Device Drivers

Linux Device Drivers


Linux
Modules
Character drivers
IO & Memory
Linux Kernel
Process Management
Process Address space

Linux Scheduler
Memory Management
Interrupts
Signals
System Calls
Kernel Synchronization
Linux Inter Process Communications




Serial Ports
Parallel Ports
Introduction to Hardware
Linux Timers
DMA in Linux
Linux Threads
Linux Thread Synchronization

Linux Multi Threading
Debugging in Linux
GDB GNU Debugger
KDB Kernel Debugger
KGDB Kernel GNU Debugger
Example Ethernet Driver




Kernel Synchronization

Kernel Synchronization

 

Concurrency and Race conditions

 

     Kernel code does not run in simple environment like application s /w and must be written with the idea that many things can be happening at once.

     Multiple processes can be trying to use the driver at the same time that our driver is trying to do something else.

     In addition several other s /w abstractions ( such as kernel timers ) run asynchronously.

     Lastly ( but not least ) Linux run on SMP, with the result that your driver could be executing concurrently on more than one CPU.

     So Linux kernel , including driver code, must be reentrant it must be capable of running in more than one context at the same time.

 

Race Condition: Situations in which an unfortunate order of execution causes undesirable behavior

 

Dealing with Race conditions / protecting data from concurrent access

 

     Using lock variables those are atomically incremented and decremented

     Using spinlocks to enforce mutual exclusions

     Using semaphore

 

Using Lock Variables

 

The kernel provides a set of functions that may be used to provide atomic (non-interruptible) access to variables. The Linux kernel exports two sets of functions to deal with locks: bit operations and access to the atomic data type.

 

Bit Operations: Its quite common to have a single bit lock variable or to update device status flags at interrupt time while a process may be accessing them The kernel offers a set of functions that modify or test single bits atomically, declared in <asm/bitops.h>.

 

void set_bit(nr, void *addr);

void clear_bit(nr, void *addr);

void change_bit(nr, void *addr);

void test_bit(nr, void *addr);

 

Using Lock Variables

 

Atomic integer operations: Kernel programmers often need to share an integer variable between an interrupt handler and other functions, defined in <asm/atomic.h>.void atomic_set (atomic_t*v, inti);void atomic_read(atomic_t*v);

 

Spin locks

 

     Spinlocks works through a shared variable

     A function may acquire the lock by setting the variable to a specific value

     Any other function needing the lock will query it and seeing that it is not available , will spin in a busy_waitloop until it is available

 

#include <linux/spinlock.h>

spinlock_t my_lock = SPIN_LOCK_UNLOCKED ;

 

If it is necessary to initialize a spinlock at runtime spin_lock_init( &my_lock) ;

 

spin_lock( spinlock_t*lock ) ;

spin_unlock( spinlock_t*lock ) ;

 

spin_lock locks the given lock, perhaps waiting until it becomes available. The lock can then be released with spin_unlock.

 

Semaphore

 

When a task attempts to acquire a semaphore that is already held, the semaphore places the task onto a wait queue and puts the task to sleep. The processor is then free to execute other code. When the processes holding the semaphore release the lock, one of the tasks on the wait queue is awakened so that it can then acquire the semaphore.

 

Creating and initializing Semaphores

 

Semaphore implementation is architecture dependent and defined in <asm/semaphore.h>.

The struct semaphore type represents semaphores. Statically declared semaphore are created via:

static DECLARE_SEMAPHORE_GENERIC(name, count);

where name is the variables name and count is the usage count of the semaphore.

 

To create more common mutex, use

static DECLARE_MUTEX(name);

 

To initialize a dynamically created semaphore, use

sema_init(sem, count);

where semis a pointer and count is the usage count of semaphore.

 

Similarly initialize a dynamically created mutex, you can use

init_MUTEX(sem);

 

Using Semaphores

 

The function down_interruptible() attempts to acquire the given semaphore . If it fails, it sleeps in the TASK_INTERRUPTIBLE state.

If the task receives a signal, it is awakened and down_interruptible() returns EINTR.

The function down() places the task in TASK_UNINTERRUPTIBLE state if it sleeps.

To release a given semaphore, call up().

 

Consider an example:

 

/* define and declare a semaphore, named nr_sem, with a count of one */

 

static DECLARE_MUTEX(nr_sem);

 

/* attempt to acquire the semaphore */

if (down_interruptible(&mr_sem) {

/* signal received, semaphore not acquired */

}

 

/* critical region */

/* release the given semaphore */

up(&nr_sem);

 

Spin Locks Vs Semaphores

Only a spinlock can be used in interrupt context, whereas only a semaphore can be held while a task sleeps.

 

Requirement Recommended lock

Low overhead locking Spin lock is preferred

Short lock hold time Spin lock is preferred

Long lock hold time Semaphore is preferred

Need to lock from interrupt context Spin lock is required

Need to sleep while holding lock Semaphore is required

 

 

Blocking I/O

 

One problem that might arise with read is what to do when there's no data yet, but were not at end-of-file. The default answer is go to sleep waiting for data.‟‟ How aprocess is put to sleep, how it is awakened, and how an application can ask if there is data without just blindly issuing a read call and blocking. We then apply the same concepts to write.

 

Whenever a process must wait for an event (such as the arrival of data or the termination of a process), it should go to sleep. Sleeping causes the process to suspend execution, freeing the processor for other uses. At some future time, when the event being waited for occurs, the process will be woken up and will continue with its job.

 

Wait Queue

 

Sleep and Awakening: A wait queue is a queue of processes that are waiting for an event. The kernel uses a simple data structure, a wait queue, which consists of a pointer to the processes task_struct and a pointer to the next element in the wait queue. When processes are added to the end of a wait queue they can either be interruptible or uninterruptible. Wait queues are declared and initialized as follows:

wait_queue_head_tmy_queue;

init_wait_queue_head(&my_queue);

To initialize the queue statically:

DECLARE_WAIT_QUEUE_HEAD(my_queue);

 

To sleep:

sleep_on(wait_queue_head_t*queue);

 

Puts the process to sleep on this queue

 

interruptible_sleep_on(wait_queue_head_t*queue);

 

The interruptible variant works just like sleep_on, except that the sleep can be interrupted by a signal.

 

sleep_on_timeout(wait_queue_head_t*queue, long timeout);

 

To wakeup:

 

wake_up(wait_queue_head_t*queue);

wake up all processes that are waiting on this event queue.

 

wake_up_interruptible(wait_queue_head_t*queue);

wakes up only the processes that are in interruptible sleeps.

 

 

Synchronization Techniques

 

     Hardware Support

     Atomic Operations

     Disabling Interrupt

     Locking

o      Spin locks

o      Semaphores

 

Hardware Support

 

     Fundamentally, Mutual Exclusion Requires Hardware Support

     Bootstrap from hardware-supported atomic action

     Single Processor

cli and sti instruction: disable (and enable) all interrupts

     SMP Architecture

The "lock" instruction prefix: lock the memory bus for this instruction (so no other CPU can access the memory until this instruction is done)

 

Atomic Operations

Execute a Single Instruction in an "Atomic" Way, Even Under Multiprocessor System

o      Supported by SMP hardware (with the "lock" instruction prefix)

o      Two types: bit ops and atomic integer variable

 

     Bit Ops: Change a Bit in Any Memory Address

In include/asm-i386/bitops.h

void set_bit(intnr, volatile void * addr)

void clean_bit(intnr, volatile void * addr)

int test_and_set_bit(intnr, volatile void * addr)

 

Atomic Integer Variable

 

     Atomic Operations on Integer Instead of Bit

     Defined in include/asm-i386/atomic.h

     Data Structure: Type atomic_t

 

     Functions:

atomic_read(v)

atomic_set(v,i)

atomic_add(i,v)

atomic_inc(v)

...

 

Interrupt Disabling

 

Disable/Enable All Interrupts in This CPU: Use

local_irq_disable()or local_irq_enable()

 

     Implemented by clior stiinstruction

     If SMP system: has no effect on other CPUs

 

Global Interrupt Disabling/Enabling: cli()or sti()

     In uniprocessorsystem: same as cliand stiinstruction

     SMP: use spin lock to delay interrupt handlers in other CPUs

     Implemented as __global_cli()and __global_sti()

     See arch/i386/kernel/irq.c

 

Saving eflags Register Content

 

Must Save Register Content Before Interrupt Disabling and Restore it After Re-enabling

 

     Register includes the interrupt flag (IF)

     See include/asm-i386/system.h

 

Local Save/Restore Flags

__save_flags(long)and __restore_flags(long)

 

Global Save/Restore Flags

     save_flags(long)and restore_flags(long)

     SMP: implemented as

     x = __global_save_flags()and

__global_restore_flags(x)

     See arch/i386/kernel/irq.c

 

Spin Lock

 

     A Locking Mechanism for SMP System

     Through a shared variable

     Acquire the lock by setting the variable

     "Spin" in a busy-wait loop until the variable is unset

     Should be used with care: holding a spin lock too long may cause other CPUs to waste time in busy waiting

 

In a UniprocessorSystem

Implemented as no-op (because it is the only process running)

 

Spin Lock Implementation

 

Defined In include/asm-i386/spinlock.h

Data type: spinlock_t

typedef struct{

volatile unsigned int lock;

// 1: unlocked, <=0: locked

} spinlock_t;

 

To lock: spin_lock(lock) macro

1: lock; decb(lock->lock)

2: cmpb$0, (lock->lock)

js 2f

rep;

nop

jle 2b

jmp 1b

 

To unlock: spin_unlock(lock) macro

movb$1, (lock->lock)

 

Using Spin Lock

 

Include <linux/spinlock.h>

     Define spin lock variable:

     spinlock_tmy_lock= SPIN_LOCK_UNLOCKED;

     To lock, call spin_lock(my_lock)

o      Variants:

       With IRQ disabled: spin_lock_irq(),

spin_lock_irqsave()

o      With BH disabled: spin_lock_bh()

     To unlock, call spin_unlock(my_lock)

     To check, spin_is_locked(my_lock)returns 1/0

o      Variants: spin_trylock(), spin_unlock_wait()

 

Read/Write Spin Lock

 

     Allow Multiple Readers but Only One Writer

     Data type: rwlock_t

o      In include/asm-i386/spinlock.h

o      Ex: rwlock_tmy_lock= RW_LOCK_UNLOCKED;

 

     Operations:

o      void read_lock(rwlock_t*rw)

o      void read_unlock(rwlock_t*rw)

o      void write_lock(rwlock_t*rw)

o      void write_unlock(rwlock_t*rw)

o      And more (with _irq, _irqsave, _bh, ...)

 

Kernel Semaphores

 

     Concept of Semaphore

o      A number of resource available for claimed by task

o      Task put on the wait queue if resource unavailable

o      Task waits up when resource available (released)

     Data Structure

o      In include/asm-i386/semaphore.h

struct semaphore {

atomic_tcount; // > 0: available,

//<=0: busy

int sleepers;

wait_queue_head_twait;

};

 

More on Kernel Semaphores

 

     MUTEX: Number of Resource is 1

     To Initialize: sema_init(structsemaphore *, int)

     To Use a Resource: down(structsemaphore * sem)

o      Atomically decrease count

o      Put current on the wait queue if count<0

o      See __down() in arch/i386/kernel/semaphore.c

     To Release: up(structsemaphore * sem)

o      Atomically increment count

o      Wake up one task on wait queue if count<=0

o      See __up()in arch/i386/kernel/semaphore.c

 

How to Protect Critical Session?

 

     A Simple Way (Using Interrupt Disabling)

...

unsigned long flags;

save_flags(flags);

cli();

... critical section ...

restore_flags(flags);

...

 

     Disadvantage: stops all CPU, really expensive

 

     The Better Way: Use spin lock!