Linux Kernel Interrupts and Handlers - Top and Bottom Halves

Rome was not built in one day; and so was interrupt handling in Linux!

That’s why I decided to divide this discussion in two parts:

• Part I is to help you understand interrupts, exceptions, things to know about interrupt handlers; both; top halves and bottom halves.
• Part II will take you through a dream ride in world of Linux interrupt handling – a code walk through kernel code using arm architecture as example (x86 is a cake walk, fun is going on a road less travelled, isn’t it?)

In this article, we will be only looking at Part I.

PART I – Interrupt Handlers (Top and Bottom Halves)

Imagine yourself eating cold plain bread and suddenly a cool breeze from window brings warm smell from nearby bar-be-que. You just can’t resist it! You stop doing your work and peep through the window. That’s it, you are interrupted!!

Similar to us, Linux also gets distracted and can’t resist interrupts but it handles them with much grace than us.

In Linux, interrupt signals are the distraction which diverts processor to a new activity outside normal flow of execution. This new activity is called interrupt handler or interrupt service routine (ISR). With the help of Interrupts, hardware signals the processor.

Interrupt handling is amongst the most sensitive tasks performed by kernel and it must satisfy following:

• Interrupts can come anytime. The kernel's goal is therefore to get the interrupt out of the way as soon as possible and defer as much processing as it can.
• Because interrupts can come anytime, the kernel might be handling one of them while another one (of a different type) occurs.
• Some critical regions exist inside the kernel code where interrupts must be disabled. Such critical regions must be limited as much as possible.

Before we dwell any further, first understand the difference between interrupts and exceptions

Exception	Synchronous and produced by the CPU control unit while executing instructions either in response to a programming error or abnormal conditions that must be handled by the kernel. Synchronous because control unit issues them only after terminating the execution of an instruction.
Interrupt	Asynchronous and generated by other hardware devices at arbitrary times with respect to the CPU clock signals.

There is a further classification of interrupts and exceptions.

Interrupts
Maskable	All Interrupt Requests (IRQs) issued by I/O devices give rise to maskable interrupts. A maskable interrupt can be in two states: masked or unmasked; a masked interrupt is ignored by the control unit as long as it remains masked.
Nonmaskable	Only a few critical events (such as hardware failures) give rise to nonmaskable interrupts. Nonmaskable interrupts are always recognized by the CPU.
Exceptions
Falts	Like Divide by zero, Page Fault, Segmentation Fault.
Traps	Reported immediately following the execution of the trapping instruction. Like Breakpoints
Aborts	Aborts are used to report severe errors, such as hardware failures and invalid or inconsistent values in system tables.

Does that mean we need to understand the handling of all above? Don’t worry, kernel developers are very nice and kernel infrastructure for handling the two is similar.

If you want to be a kernel developer, understand and remember this: interrupt handlers are different from other kernel functions. Kernel invokes them in response to interrupts and they run in a special context called interrupt context. This special context is also called atomic context because code executing in this context is unable to block. Process context is the mode of operation the kernel is in while it is executing on behalf of a process—for example, executing a system call or running a kernel thread.

For a device to interrupt, its device driver must register an interrupt handler. Drivers can register an interrupt handler and enable a given interrupt line for handling with the function request_irq(), which is declared in <linux/interrupt.h>:

int request_irq(unsigned int irq, irq_handler_t handler,unsigned long flags, const char name,

                          void *dev)

This function registers a handler, first making sure that the requested interrupt is a valid one, and that it is not already allocated to another device unless both devices understand shared IRQs (with help of flags)

Flags can be zero or bit mask of one or more of the flags. Let’s understand two important “flags” and I leave rest for the user to explore.

IRQF_DISABLED: When set, this flag instructs the kernel to disable all interrupts when executing this interrupt handler. When unset, interrupt handlers run with all interrupts except their own enabled. Since disabling all interrupts is bad (very bad), its use is reserved for performance-sensitive interrupts that execute quickly.

IRQF_SHARED: This flag specifies that the interrupt line can be shared among multiple interrupt handlers. Each handler registered on a given line must specify this flag; otherwise, only one handler can exist per line.

You must be wondering why IRQF_SHARED flag is needed? This is because IRQ lines are a limited resource. And a simple way to increase the number of devices a system can host is to allow multiple devices to share a common IRQ. Normally, each driver registers its own handler to the kernel for that IRQ. Instead of having the kernel receive the interrupt notification, find the right device, and invoke its handler, the kernel simply invokes all the handlers of those devices that registered for the same shared IRQ. It is up to the handlers to filter spurious invocations, such as by reading a registry on their devices.

In order to register a handler as shared, following must be satisfied:

• The IRQF_SHARED flag must be set in the flags argument to request_irq(). However, usage of IRQF_DISABLED can be mixed.
• The dev argument must be unique to each registered handler. A pointer to any per-device structure is sufficient; a common choice is the device structure as it is both unique and potentially useful to the handler. You cannot pass NULL for a shared handler.
• The interrupt handler must be capable of distinguishing whether its device actually generated an interrupt.

If any one device does not share fairly, none can share the line!

When your driver unloads, you need to unregister your interrupt handler and potentially disable the interrupt line. To do this, call:

void free_irq(unsigned int irq, void *dev)

If the specified interrupt line is not shared, this function removes the handler and disables the line. If the interrupt line is shared, the handler identified via dev is removed, but the interrupt line is disabled only when the last handler is removed.

Changes (important ones) were done in 2.6 kernel and it makes perfect sense to include them in our discussion:

• An option was added to reduce the process stack size from two pages down to one, providing only a 4KB stack on 32-bit systems. To cope with the reduced stack size, interrupt handlers were given their own stack, one stack per processor, one page in size. This stack is referred to as the interrupt stack.
• A new friend of “request_irq()” was introduced: “request_threaded_irq()”. It is important function to understand before we go further deep in world of bottom halves.

Threaded interrupt handlers were introduced to reduce the time spent in interrupt handler and deferring the rest of the work (i.e. processing) out into kernel threads. So the top half would consist of a "quick check handler" that just ensures the interrupt is from the device; if so, it simply acknowledges the interrupt to the hardware and tells the kernel to wake the interrupt handler thread.

A driver that wishes to request a threaded interrupt handler will use(defined in kernel/irq/manage.c):

int request_threaded_irq(unsigned int irq, irq_handler_t handler,irq_handler_t

                                            thread_fn, unsigned long flags, const char *name, void  dev)

handler - called when interrupt occurs

thread_fn – Function called from irq handler thread. If NULL, no irq thread is created

Handler is called in interrupt context and it’s job is usually to quite the device and return; it cannot sleep. If it’s return value is IRQ_WAKE_THREAD, the thread_fn() will be called in process context; it can sleep.

Often interrupt handlers have a large amount of work to perform. For example, consider the interrupt handler for a network device. On top of responding to the hardware, the interrupt handler needs to copy networking packets from the hardware into memory, process them, and push the packets down to the appropriate protocol stack or application.

You must be thinking why I am trying to confuse you by contradicting myself— that an interrupt handler execute quickly and perform a large amount of work. Because of these competing goals, the processing of interrupts is split into two parts, or halves.

• The interrupt handler is the top half. The top half is run immediately upon receipt of the interrupt and performs only the work that is time-critical, such as acknowledging receipt of the interrupt or resetting the hardware.
• Work that can be performed later is deferred until the bottom half. The bottom half runs in the future, at a more convenient time, with all interrupts enabled.

Soon we’ll be jumping on bottom halves but before we do so, there are few things worth mentioning here which you should never forget:

• Interrupt handlers in Linux need not be reentrant. When a given interrupt handler is executing, the corresponding interrupt line is masked out on all processors, preventing another interrupt on the same line from being received. Normally all other interrupts are enabled, so other interrupts are serviced, but the current line is always disabled. Consequently, the same interrupt handler is never invoked concurrently to service a nested interrupt. This greatly simplifies writing your interrupt handler. (Feeling any better?)
• Interrupt context is time-critical because the interrupt handler interrupts other code. Code should be quick and simple. Busy looping is possible, but discouraged. Always keep in mind that your interrupt handler has interrupted other code (possibly even another interrupt handler on a different line).
• Although the kernel may accept a new interrupt signal while handling a previous one, some critical regions exist inside the kernel code where interrupts must be disabled. Often, interrupts must be blocked while holding a spinlock to avoid deadlocking the system. Such critical regions must be limited as much as possible because, according to the previous requirement, the kernel, and particularly the interrupt handlers, should run most of the time with the interrupts enabled.
• Interrupt handlers do not run in process context; therefore, they cannot block.
• A handler can't transfer data to or from user space, because it doesn't execute in the context of a process.
• Handlers also cannot do anything that would sleep, such as calling wait_event, allocating memory with anything other than GFP_ATOMIC, or locking a semaphore.
• Handlers cannot call schedule.

By now you are aware of interrupt handlers and the limitations imposed upon them.

Let’s go further in our journey and understand “bottom halves”.

“The job of bottom halves is to perform any interrupt-related work not performed by the

interrupt handler.”

Bottom half is a generic operating system term referring to the deferred portion of interrupt processing, so named because it represents the second, or bottom, half of the interrupt processing solution.

There is no clear guideline on how to divide the work between the top and bottom half, following useful tips can help:

• If the work is time sensitive, perform it in the interrupt handler.
• If the work is related to the hardware, perform it in the interrupt handler.
• If the work needs to ensure that another interrupt (particularly the same interrupt) does not interrupt it, perform it in the interrupt handler.
• For everything else, consider performing the work in the bottom half.

The point of a bottom half is not to do work at some specific point in the future, but simply to defer work until any point in the future when the system is less busy and interrupts are again enabled. Often, bottom halves run immediately after the interrupt returns. The key is that they run with all interrupts enabled.

We will not discuss about original Bottom Halves “BH” and Task queues as they were removed in 2.5, lets understand what’s available in present world.

Softirqs:

Although they are rarely used directly; much more common form of bottom half is taklet. But since tasklets are built on softirqs, we will discuss them first. Softirq code is in kernel/softirq.c file

Softirqs are statically allocated at compile time, hence, you cannot dynamically register and destroy softirqs.

Softirqs are represented by softirq_action structure defined in <linux/interrupt.h>

struct softirq_action {

                void       (*action)(struct softirq_action *);

};

The prototype of a softirq handler, action, looks like

void softirq_handler(struct softirq_action *)

When the kernel runs a softirq handler, it executes this action function with a pointer to the corresponding softirq_action structure as its lone argument.

Few things to remember about softirqs: 

• A softirq never preempts another softirq. The only event that can preempt a softirq is an interrupt handler.
• The softirq handlers run with interrupts enabled and cannot sleep.
• While a handler runs, softirqs on the current processor are disabled Another softirq—even the same one—can run on another processor.

A registered softirq must be marked before it will execute. This is called raising the softirq. In order to do so, call raise_softirq() or raise_softirq_irqoff() (if interrupts are already off).

Usually, an interrupt handler marks its softirq for execution before returning. Then, at a suitable time, the softirq runs. Pending softirqs are checked for and executed in the following places:

• In the return from hardware interrupt code path.
• In the ksoftirqd kernel thread.
• In any code that explicitly checks for and executes pending softirqs, such as the networking subsystem

The softirq handler is registered at run-time via open_softirq(), which takes two parameters: the softirq’s index and its handler function. The kernel uses this index, which starts at zero, as a relative priority. Softirqs with the lowest numerical priority execute before those with a higher numerical priority.

Tasklet	Priority	Softirq Description
HI_SOFTIRQ	0	High-priority tasklets
TIMER_SOFTIRQ	1	Timers
NET_TX_SOFTIRQ	2	Send network packets
NET_RX_SOFTIRQ	3	Receive network packets
BLOCK_SOFTIRQ	4	Block devices
BLOCK_IOPOLL_SOFTIRQ	5	Block devices with I/O polling blocked on other CPUs
TASKLET_SOFTIRQ	6	Normal Priority tasklets
SCHED_SOFTIRQ	7	Scheduler
HRTIMER_SOFTIRQ	8	High-resolution timers
RCU_SOFTIRQ	9	RCU locking

Creating a new softirq includes adding a new entry to this enum.When adding a new softirq, you might not want to simply add your entry to the end of the list, as you would elsewhere. Instead, you need to insert the new entry depending on the priority you want to give it.

Softirqs are reserved for the most timing-critical and important bottom-half processing on the system. Normally you don’t need to add a new softirq, if you do, think why using a tasklet is insufficient. Nonetheless, for timing-critical applications that can do their own locking in an efficient way, softirqs might be the correct solution.

Tasklets:

Tasklets are implemented on top of softirqs, they are softirqs. They are represented by two softirqs: HI_SOFTIRQ and TASKLET_SOFTIRQ. The only difference in these types is that the HI_SOFTIRQ-based tasklets run prior to the TASKLET_SOFTIRQ based tasklets.

Although they are implemented on top of softirqs, but following differentiates them:

• Tasklets can be created statically and dynamically.
• Two different tasklets can run concurrently on different processors, but two of the same type of tasklet cannot run simultaneously.

Tasklets are represented by the tasklet_struct structure. Each structure represents a unique tasklet. The structure is declared in <linux/interrupt.h>:

 

struct tasklet_struct {

struct tasklet_struct *next;           /* next tasklet in the list */

unsigned long state;                      /* state of the tasklet */

atomic_t count;                             /* reference counter */

void (*func)(unsigned long);        /* tasklet handler function */

unsigned long data;                      /* argument to the tasklet function */

}; 

The func member is the tasklet handler (the equivalent of action to a softirq) and receives data as its sole argument.

Tasklets are scheduled (similar to raising the softirq) via the tasklet_schedule() and tasklet_hi_schedule() functions.

To statically create the tasklet (and thus have a direct reference to it), use one of two macros in <linux/interrupt.h>:

DECLARE_TASKLET(name, func, data)

DECLARE_TASKLET_DISABLED(name, func, data);

To initialize a tasklet given an indirect reference (a pointer) to a dynamically created struct tasklet_struct, t, call:

tasklet_init(t, tasklet_handler, dev); 

Work Queues:

They are quite different from softirqs, tasklets as:

• work queues defer work into a kernel thread. They always runs in process context. Thus, code deferred to a work queue has all the usual benefits of process context.
• work queues are schedulable and can therefore sleep.

Work queues let your driver create a kernel thread, called as worked thread, to handle deferred work.

Many drivers in the kernel defer their bottom-half work to the default thread called events/n (where n is the processor number). Unless a driver or subsystem has a strong requirement for creating its own thread, the default thread is preferred.

Work threads are represented by workqueue_struct structure defined in kernel/workqueue.c

To create the structure statically at runtime, use DECLARE_WORK:

DECLARE_WORK(name, void (*func)(void *), void *data);

This statically creates a work_struct structure named name with handler function func and argument data.

Alternatively, you can create work at runtime via a pointer:

INIT_WORK(struct work_struct *work, void (*func)(void *), void *data); 

This dynamically initializes the work queue pointed to by work with handler function func and argument data.

To queue a given work’s handler function with the default events worker threads, simply call

schedule_work(&work);

schedule_delayed_work(&work, delay);

With first call, the work is scheduled immediately and is run as soon as the events worker thread on the current processor wakes up.

While with second call, the work_struct represented by &work will not execute for at least delay timer ticks into the future.

In order to flush a work queue i.e. ensure given batch of work is completed, use:

void flush_scheduled_work(void);

This function waits until all entries in the queue are executed before returning. While waiting for any pending work to execute, the function sleeps. Therefore, you can call it only from process context. Note that this function does not cancel any delayed work.

You can create a new work queue and corresponding worker threads if default queue is insufficient via a simple functions: 

struct workqueue_struct *create_workqueue(const char *name);

Because this creates one worker thread per processor, you should create unique work queues only if your code needs the performance of a unique set of threads.

In order to understand the need for synchronization between thread/atomic and atomic/atomic context along with different primitives which allow you to do so, refer to linux kernel synchronization primitives.

Now you are aware of the weapons in the arsenal. But before you go out and use them in war, understand them clearly or else, they will back fire.

Bottom Half	Context	Inherit Serialization
Softirq	Interrupt	None
Tasklet	Interrupt	Against the same tasklet
Work Queue	Process	None (scheduled as process context)

Once you are ready with the basic concepts and understanding discussed here, in the next part we will look inside the kernel interrupt handling code.

Linux Kernel Synchronization Primitives

Linux kernel offers a synchronization technique for every possible need (you think it, they have it !).
It's like a fruit basket - you just ought to know what you want. Picking a wrong fruit can ruin the taste, so be careful !

Symmetrical Multi Processing (SMP) has also contributed greatly in this confusion. This guide tries to cover both, UP (uni processor) and SMP systems.

So let's begin the tour, grab your hot chocolate and sit comfortably to enjoy the ride.

Before we actually start looking into fruits, lets first understand the basket without which, all fruits will fall.

You want to protect critical regions and avoid race conditions in your code.
What is a critical region ? Code paths that access and manipulate shared data are called critical regions (also called critical sections). It is usually unsafe for multiple threads of execution to access the same resource simultaneously.
When this does occur, we call it a race condition, so-named because the threads raced to get there first.

Consider a simple shared resource, a single global integer, and a simple critical region, the operation of merely incrementing it: i++
Now, assume that there are two threads of execution, both enter this critical region, and the initial value of i is 7.The desired outcome is then similar to the following (with each row representing a unit of time):

Ensuring that unsafe concurrency is prevented and that race conditions do not occur is called synchronization.


It is God's will to prevent concurrent access during critical regions, the programmer must act as an angel to ensure that code executes atomically—that is, operations complete without interruption as if the entire critical region were one indivisible instruction. Failing to do so will bring curse upon you.

For those wondering about a newly added word in their vocabulary i.e., concurrency, please stay with me. Other wise men can skip this section and continue further.
"A concurrent system is a collection of interacting computational tasks that may execute in parallel. In user-space, synchronization is needed because programs are scheduled preemptively at the will of the scheduler. Because a process can be preempted at any time and another process can be scheduled onto the processor, a process can be involuntarily preempted in the middle of accessing a critical region. If the newly scheduled process then enters the same critical region (say, if the two processes manipulate the same shared memory or write to the same file descriptor), a race can occur.The same problem can occur with multiple single-threaded processes sharing files, or within a single program with signals, because signals can occur asynchronously.This type of concurrency—in which two things do not actually happen at the same time but interleave with each other such that they might as well—is called pseudo-concurrency. If you have a symmetrical multiprocessing machine, two processes can actually be executed in a critical region at the exact same time.That is called true concurrency."

The kernel has similar causes of concurrency:

• Interrupts— An interrupt can occur asynchronously at almost any time, interrupting the currently executing code.
• Softirqs and tasklets— The kernel can raise or schedule a softirq or tasklet at almost any time, interrupting the currently executing code.
• Kernel preemption— Because the kernel is preemptive, one task in the kernel can preempt another.
• Sleeping and synchronization with user-space— A task in the kernel can sleep and thus invoke the scheduler, resulting in the running of a new process.
• Symmetrical multiprocessing— Two or more processors can execute kernel code at exactly the same time.

Having understood synchronization and concurrency (the basket), now we need a way of making sure that only one thread manipulates the shared resource at a time—a mechanism for preventing access to a resource while another thread of execution is in the marked region.

This mechanism is provided by locks (the fruits).

The basic rule to locking is - Protect data, not code !! (never ever forget this)

Code that is safe from concurrent access from an interrupt handler is said to be interrupt-safe. Code that is safe from concurrency on symmetrical multiprocessing machines is SMP-safe. Code that is safe from concurrency with kernel preemption is preempt-safe. The actual mechanisms used to provide synchronization and protect against race conditions in all these cases are: 

• Atomic Operations: Atomic operations provide instructions that execute atomically—without interruption. Atomic operators are indivisible instructions. For example, an atomic increment can read and increment a variable by one in a single indivisible and uninterruptible step. Using atomic instructions requires understanding memory models and barriers. Beware of atomic instructions and memory barriers for they are subtle and quick to anger.

• Spin Locks: This is the most common lock in Linux kernel. The idea behind spin lock is to execute a tight loop or a busy wait until the lock is released (become available). So a spin lock is a lock that can be held by at most one thread of execution. 
• The executing core cannot be used for anything else while spinning.
• Spin-locks are usable in atomic context (ISR, softirqs, tasklets) as they do not sleep (read last two pointsagain until you remember them like your own name).
• They provide the needed protection from concurrency on multiprocessing machines. On uniprocessor machines, the locks compile away and do not exist; they simply act as markers to disable and enable kernel preemption. If kernel preempt is turned off, the locks compile away entirely.
• Spin locks are not recursive
•  Use spin locks when shared data can be accessed in atomic context to prevent thread/atomic or atomic/atomic race.
• If a spin lock is shared between a thread and interrupt handler, you must disable local interrupts (interrupt requests on the current processor) before obtaining the lock. Otherwise, it is possible for an interrupt handler to interrupt kernel code while the lock is held and attempt to reacquire the lock. The interrupt handler spins, waiting for the lock to become available.The lock holder, however, does not run until the interrupt handler completes. Note that you need to disable interrupts only on the current processor. If an interrupt occurs on a different processor, and it spins on the same lock, it does not prevent the lock holder (which is on a different processor) from eventually releasing the lock. The kernel provides an interface that conveniently disables interrupts (spin_lock_irqsave/spin_unlock_irqrestore, spin_lock_bh/spin_unlock_bh). If the data is shared between two different tasklets, however, you must obtain a normal spin lock before accessing the data in the bottom half.You do not need to disable bottom halves because a tasklet never preempts another running tasklet on the same processor. With softirqs, regardless of whether it is the same softirq type, if data is shared by softirqs, it must be protected with a lock. Softirqs, even two of the same type, might run simultaneously on multiple processors in the system.A softirq never preempts another softirq running on the same processor, however, so disabling bottom halves is not needed.
• Do not mask interrupts for protecting data shared between interrupt and non-interrupt context, use spin-locks instead.

• Reader-Writer Spin Locks: Reader-writer spin locks provide separate reader and writer variants of the lock. One or more readers can concurrently hold the reader lock.The writer lock, conversely, can be held by at most one writer with no concurrent readers. Reader/writer locks are sometimes called shared/exclusive or concurrent/exclusive locks because the lock is available in a shared (for readers) and an exclusive (for writers) form. Beware of r/w locks performance.

• Semaphores: Semaphores in Linux are sleeping locks.When a task attempts to acquire a semaphore that is unavailable, 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 semaphore becomes available, one of the tasks on the wait queue is awakened so that it can then acquire the semaphore.
• Because sleeping nature, semaphores are well suited to locks that are held for a long time.
• They are not optimal for locks that are held for short periods
• Because a thread of execution sleeps on lock contention, semaphores must be obtained only in process context because interrupt context is not schedulable.
• You cannot hold a spin lock while you acquire a semaphore, because you might have to sleep while waiting for the semaphore, and you cannot sleep while holding a spin lock.
• Unlike spin locks, semaphore do not disable kernel preemption. A code holding a semaphore can be preempted.
• They can allow for at most count number of simultaneous lock holders. In that case, they are called counting semaphores. When count is equal to one, they are called binary semaphores.
• Although a binary semaphore provide mutual exclusion, but don’t use semaphores for mutual exclusion. That’s a job better handled by mutexes for two reasons. Firstly mutexes are faster (at least kernel-side). Secondly as mutexes have a more precise semantic, the implementation can automagically reports some bugs, for example unlocking a mutex before locking it. The kernel has a configuration option to enable such checks.
• Primary usage of semaphore should be for synchronization (between threads running in different context), not for locking.
• Do not use semaphores when better suited alternatives exist (this may sound harsh on semaphores but trust me, you don't want your life getting wasted in fixing semaphore induced bugs).

•  Reader-Writer Semaphores: The situations where reader-writer semaphores are preferred over standard semaphores are the same as with reader-writer spin locks versus standard spin locks.

• Mutexes: Sleeping(and sometimes adaptive) lock which allows mutual exclusion. It behaves similar to a semaphore with a count of one, but it has a simpler interface, more efficient performance, and additional constraints on its use.
• Only one task can hold the mutex at a time.That is, the usage count on a mutex is always one.
• Whoever locked a mutex must unlock it.That is, you cannot lock a mutex in one context and then unlock it in another.This means that the mutex isn’t suitable for more complicated synchronizations between kernel and user-space.
• Recursive locks and unlocks are not allowed.
• A process cannot exit while holding a mutex
• A mutex cannot be acquired by an interrupt handler or bottom half, even with
  mutex_trylock().

•  Completion Variables: Using completion variables is an easy way to synchronize between two tasks in the kernel when one task needs to signal to the other that an event has occurred. One task waits on the completion variable while another task performs some work.When the other task has completed the work, it uses the completion variable to wake up any waiting tasks. Do you hear bells ringing that sounds like semaphore ? If yes, (i am glad you are still awake) you are right—the idea is much the same. In fact, completion variables merely provide a simple solution to a problem whose answer is otherwise semaphores.

• Sequential Locks:  The sequential lock, generally shortened to seq lock provides a simple mechanism for reading and writing shared data. It works by maintaining a sequence counter.Whenever the data in question is written to, a lock is obtained and a sequence number is incremented. Prior to and after reading the data, the sequence number is read. If the values are the same, a write did not begin in the middle of the read. Further, if the values are even, a write is not underway. (Grabbing the write lock makes the value odd, whereas releasing it makes it even because the lock starts at zero.) Seq locks are useful to provide a lightweight and scalable lock for use with many readers and a few writers. Seq locks, however, favor writers over readers. An acquisition of the write lock always succeeds as long as there are no other writers. Readers do not affect the write lock, as is the case with reader-writer spin locks and semaphores. Furthermore, pending writers continually cause the read loop (the previous example) to repeat, until there are no longer any writers holding the lock.

• Preemption Disabling:  Remember if a spin lock is held, kernel is not preemptive. Disabling
  preemption (preempt_disable/preempt_enable) does not prevent ISRs and tasklets from running however. Moreover, disabling preemption should not be used for avoiding race conditions because:
• Disabling preemption operates on the current CPU core only and so does not prevent
  races in SMP systems.
• Disabling preemption has a global impact on thread latency and so can impact realtime.

• Barriers: Both the compiler and the processor can reorder reads and writes for performance reasons. When dealing with synchronization between multiple processors or with hardware devices, it is sometimes a requirement that memory-reads (loads) and memory-writes (stores) issue in the order specified in your program code. All processors that do reorder reads or writes provide machine instructions to enforce ordering requirements. It is also possible to instruct the compiler not to reorder instructions around a given point.These instructions are called barriers. I'll suggest you to save some juice and read kernel documentation on barriers clearly before you intend to use them. (http://kernel.org/doc/Documentation/memory-barriers.txt)

Don't tell me you are still looking for a fruit to satisfy your need.
If you are, then i strongly suggest to reconsider your requirement. But don't get disheartened, i am pretty sure there is a way out.

Did i forgot to mention not to rely on thread priorities to fix race conditions? If yes, then mark this one too on your nearby stone 

Ironically races are caused by lack of synchronization and deadlocks by excessive or incorrect synchronization. Concurrent programming is therefore a delicate dance between these two traps, and many lesser evils, to deliver the required feature set while maintaining the correctness of the system and providing adequate performance.

A deadlock occurs when each task in a set of tasks is blocked waiting for a resource owned by
another task in the set. All following conditions must hold true simultaneously for a deadlock to exist:

• Mutual exclusion: there are several resources that cannot be used by more than one task at a time.
• Hold and wait: tasks already holding a resource may block waiting for another resource.
• No preemption: resources cannot be forcibly removed from the task owning them.
• Only the owning task can release resources.
• Circular wait: there are several tasks forming a circular chain where each task waits on a resource owned by the next task in the chain.

Removing any of the above condition is sufficient to prevent deadlocks. Following should help you:

1. Try to limit design to single mutex. This removes the mutual exclusion condition.
2. Avoid acquiring more than one mutex/resource at a time and also avoid acquiring locks recursively. This removes the hold and wait condition.
3. Always acquire mutexes in same order and release them in opposite order to prevent cycles. This removes the circular wait condition. Define and document lock ordering hierarchy.
4. When ordering mutexes is not option, It is sometimes possible to avoid deadlocks by using “try” variants of the locking primitives that return an error if the lock is already held. This removes the hold and wait condition. The idea is to try to acquire the misordered lock. If the lock is acquired everything is fine. If the lock is already held some recovery action must be  taken, for example rolling back the shared resources to a consistent state, releasing all already held locks, and trying in-order acquisition.
5. Strive to unlock before calling unknown code.
6. Avoid invoking client-provided callbacks while holding locks.
7. Document callback calling context.
8. Beware of race conditions when evaluating the wake-up condition.

So by now you are aware of the basket and the fruit flavors it has. So satiate yourself with the fruit you desire.


I would say I am not the original writer to this information. I would like to thank the under link

http://linuxburps.blogspot.in/p/blog-page.html 

container_of()

Your usage example container_of(dev, struct wifi_device, dev); might be a bit misleading as you are mixing two namespaces there.
While the first dev in your example refers to the name of pointer the second dev refers to the name of a structure member.
Most probably this mix up is provoking all that headache. In fact the member parameter in your quote refers to the name given to that member in the container structure.
Taking this container for example:

struct container {
  int some_other_data;
  int this_data;
}

And a pointer int *my_ptr to the this_data member you'd use the macro to get a pointer to struct container *my_container by using:

struct container *my_container;
my_container = container_of(my_ptr, struct container, this_data);

Taking the offset of this_data to the beginning of the struct into account is essential to getting the correct pointer location.
Effectively you just have to subtract the offset of the member this_data from your pointer my_ptr to get the correct location.
That's exactly what the last line of the macro does.

Device Model

I am writing this notes from Linux device drivers book(LKD)

-The demands of newer systems, with their more complicated topologies and need to support features such as power management, made it clear, however, that a general abstraction describing the structure of the system was needed.
-device model provides that abstraction
1)Power management and system shutdown
2)Communications with user space
3)Hotpluggable devices
4)Device classes
5)Object lifecycles

Koject
- It was initially conceived as a simple reference counter, but its responsibilities have grown over time, and so have its fields.

The tasks handled by struct kobject and its supporting code now include:
1)Reference counting of objects
2)Sysfs representation
3)Data structure glue
4)Hotplug event handling

struct kobject {
        const char              *name;
        struct list_head        entry;
        struct kobject          *parent;
        struct kset             *kset;
        struct kobj_type        *ktype;
        struct sysfs_dirent     *sd;
        struct kref             kref;
        unsigned int state_initialized:1;
        unsigned int state_in_sysfs:1;
        unsigned int state_add_uevent_sent:1;
        unsigned int state_remove_uevent_sent:1;
        unsigned int uevent_suppress:1;
};

Embedding kobjects
- kobjects are used to control access to a larger, domain-specific object. To this end, kobjects are found embedded in other structures
- If you are used to thinking of things in object-oriented terms, kobjects can be seen as a top-level, abstract class from which other classes are derived.

struct cdev {
struct kobject kobj;
struct module *owner;
struct file_operations *ops;
struct list_head list;
dev_t dev;
unsigned int count;
};

Kobject initialization
-step 1    simply set the entire kobject to 0
-step 2    void kobject_init(struct kobject *kobj);
 kobject_init sets the kobject’s reference count to one.

-step 3(minimum set the name)   int kobject_set_name(struct kobject *kobj, const     char *format, ...);



Reference count manipulation
-struct kobject *kobject_get(struct kobject *kobj);
-void kobject_put(struct kobject *kobj);

Sometimes only refreance count does not work. We also need existent of module that created the koject. It would not do to unload that module while the kobject is still
being passed around.







Release functions and kobject types
- what happens to a kobject when its reference count reaches 0.
- The code that created the kobject generally does not know when that will happen
If it know than there would be no point in reference count.
-user-space programs can keep a reference to a kobject (by keeping one of its associated sysfs files open) for an arbitrary period of time.
- The reference count is not under the direct control of the code that created the kobject.
- So that code must be notified asynchronously whenever the last reference to one of its kobjects goes away
-This notification is done through a kobject’s release method.
-every kobject must have a release method.
- the release method is not stored in the kobject itself; instead, it is associated with the type of the structure that contains the kobject.

struct kobj_type {
void (*release)(struct kobject *);
struct sysfs_ops *sysfs_ops;
struct attribute **default_attrs;
};

-Confusingly, the pointer to this structure can be found in two different places. The kobject structure itself contains a field (called ktype) that can contain this pointer.

 If, however, this kobject is a member of a kset, the kobj_type pointer is provided by that kset instead.

macro:
struct kobj_type *get_ktype(struct kobject *kobj);

finds the kobj_type pointer for a given kobject.


Kobject Hierarchies, Ksets, and Subsystems
-The kobject structure is often used to link together objects into a hierarchical struc-
ture that matches the structure of the subsystem being modeled.
-there are two separate mechanize,parent pointer and kset.
eg. for example, a kobject represents a USB device, its parent pointer may indicate the object representing the hub into which the device is plugged.
-The main use for the parent pointer is to position the object in the sysfs hierarchy.

Ksets-a kset is a collection of kobjects embedded within structures of the same type.
- The two concepts have been separated so that objects of identical type can appear in distinct sets.
- the main function of a kset is containment.
- In fact, each kset contains its own kobject internally, and it can, in many ways, be treated the same way as a kobject.
-It is worth noting that ksets are always represented in sysfs; once a kset has been set up and added to the system, there will be a sysfs directory for it. Kobjects do not necessarily show up in sysfs, but every kobject that is a member of a kset is represented there.
 -Adding a kobject to a kset
step1: The kobject’s kset field must be pointed at the kset of interest;
step2:then
int kobject_add(struct kobject *kobj);

-extern int kobject_register(struct kobject *kobj);
This function is simply a combination of kobject_init and kobject_add.


-When a kobject is passed to kobject_add, its reference count is incremented

-kobject will probably have to be removed from the kset to clear that reference;
void kobject_del(struct kobject *kobj);

-There is also a kobject_unregister function, which is a combination of kobject_del and kobject_put.
-kset keeps its children in standard link list,in most of the case kobject in the kset as pointer pointing to kset in parent field of the kobject.

Operations on ksets
-void kset_init(struct kset *kset);
int kset_add(struct kset *kset);
int kset_register(struct kset *kset);
void kset_unregister(struct kset *kset);

-To manage the reference count of kset
struct kset *kset_get(struct kset *kset);
void kset_put(struct kset *kset);

- kset also has a name, which is stored in the embedded kobject
kobject_set_name(&my_set->kobj, "The name");

Subsystems- Subsystems usually (but not always) show up at the top of the sysfs hierarchy.
If probleby you want to create a new subsystem that means you need to create new class
A subsystem is represented by a simple structure:
struct subsystem {
struct kset kset;
struct rw_semaphore rwsem;
};
-subsystem is just a wrapper around a kset with a semaphore thrown in it.

Subsystems are often declared with a special macro:
-decl_subsys(name, struct kobj_type *type,struct kset_hotplug_ops *hotplug_ops);

Subsystems have the usual list of setup and teardown functions:
-void subsystem_init(struct subsystem *subsys);
-int subsystem_register(struct subsystem *subsys);
-void subsystem_unregister(struct subsystem *subsys);
-struct subsystem *subsys_get(struct subsystem *subsys)
-void subsys_put(struct subsystem *subsys);

Low-Level Sysfs Operations-Kobjects are the mechanism behind the sysfs virtual filesystem. For every directory
found in sysfs, there is a kobject lurking somewhere within the kernel.
-Every kobject of interest also exports one or more attributes.

-try to look at this <linux/sysfs.h>.

 This section examines how kobjects and sysfs interact at a low level.

- kobject to show up in sysfs is simply a matter of calling kobject_add.

 -Sysfs entries for kobjects are always directories, so a call to kobject_add  results in
the creation of a directory in sysfs.

-The name assigned to the kobject (with kobject_set_name) is the name used for
the sysfs directory.

- The sysfs entry is located in the directory corresponding to the kobject’s parent
pointer.

Default Attributesstruct kobj_type
{
void (*release)(struct kobject *);
struct sysfs_ops *sysfs_ops;
struct attribute **default_attrs;
};

struct attribute
{
char *name;//name is the name of the attribute
struct module *owner;//pointer to the module that is responsible for implementation of this attribute
mode_t mode;//projection bit appilted to this attribute
};

-default_attrs array says what the attributes are but does not tell sysfs how to actually implement those attributes.

-That task falls to the kobj_type->sysfs_ops field,
which points to a structure defined as:

struct sysfs_ops {
ssize_t (*show)(struct kobject *kobj, struct attribute *attr,
char *buffer);
ssize_t (*store)(struct kobject *kobj, struct attribute *attr,
const char *buffer, size_t size);
};