Interrupt Handling in Linux

What is Interrupt?

An interrupt (also known as an exception or trap) is an event that causes the CPU to stop executing the current program and start executing a special piece of code called an interrupt handler or interrupt service routine (ISR).

There are two different kinds of interrupts:

•Synchronous interrupt (Exception) produced by the CPU while processing instructions
•Asynchronous interrupt (Interrupt) issued by other hardware devices

Handling interrupts:
•Interrupts can occur at any time, the kernel tries to get it out of the way as soon as possible
•An interrupt can be interrupted by another interrupt
•There are regions in the kernel which must not be interrupted at all

Two different interrupt levels are defined:
•Maskable interrupts issued by I/O devices; can be in two states, masked or unmasked. Only unmasked interrupts are getting processed.
•Nonmaskable interrupts; critical malfunctions (f.e. hardware failure); always processed by the CPU.

Every hardware device has it's own Interrupt Request (IRQ) line. The IRQs are numbered starting from 0. All IRQ lines are connected to a Programmable Interrupt Controller (PIC). The PIC listens on IRQs and assigns them to the CPU. It is also possible to disable a specific IRQ line.

Top Half and Bottom Half:

One of the main problems with interrupt handling is how to perform lengthy tasks within a handler. Often a substantial amount of workmust be done in response to a device interrupt, but interrupt handlers need to finish up quickly and not keep interrupts blocked for long. These two needs (work and speed) conflict with each other,leaving the driver writer in a bit of a bind.

Linux (along with many other systems) resolves this problem by splitting the interrupt handler into two halves. The so-called top half is the routine that actually responds to the interrupt—the one you register with request_irq. The bottom half is a routine that is scheduled by the top half to be executed later, at a safer time. The big difference between the top-half handler and the bottom half is that all interrupts are enabled during execution of the bottom half—that’s why it runs at a safer time.

To implement bottom halves,two methods:
1) task lets
2) work queues

Linux Kernel Modules

Linux kernel modules are pieces of code that can be loaded and unloaded from kernel on demand.

Kernel modules offers an easy way to extend the functionality of the base kernel without having to rebuild or recompile the kernel again. Most of the drivers are implemented as a Linux kernel modules. When those drivers are not needed, we can unload only that specific driver, which will reduce the kernel image size.

Kernel modules will have extension .ko
Kernel modules will operate on kernel space.
All Drivers are modules. Not all modules are drivers.

Kernel Modules Commands:
lsmod: To see list of modules that already loaded on system
insmod: To insert modules into kernel
modinfo: To display modules information
rmmod: To remove modules from kernel
How to Write Kernel Modules:
module.c

#include <linux/module.h>    // included for all kernel modules
#include <linux/kernel.h>    // included for KERN_INFO
#include <linux/init.h>      // included for __init and __exit macros

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Name");
MODULE_DESCRIPTION("Hello World module");

static int __init hello_init(void)
{
    printk(KERN_INFO "Hello world!\n");
    return 0;    // Non-zero return means that the module couldn't be loaded.
}

static void __exit hello_cleanup(void)
{
    printk(KERN_INFO "Cleaning up module.\n");
}

module_init(hello_init);
module_exit(hello_cleanup);

Makefile to compile module:

obj-m += hello.o

all:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
    make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

When a module is inserted into the kernel, the module_init macro will be invoked, which will call the function hello_init. Similarly, when the module is removed with rmmod, module_exit macro will be invoked, which will call the hello_exit. Using dmesg command, we can see the output from the sample Kernel module.

printk() is used for printing kernel messages

Latest Kernel version

Current stable kernel version: 4.5.1
https://www.kernel.org/

Useful linux commands

Vi Editor:

    x          Delete character at cursor
    X          Delete character before cursor
    Y or yy  Yank (copy) current line into "unnamed" storage buffer.
    p          Paste unnamed storage buffer after current line.
    P          Paste unnamed storage buffer before current line.
    r           Replace character
    R          Overwrite characters from cursor onward
    s          Substitute one character under cursor continue to insert
    S          Substitute entire line and begin to insert at beginning of line
    J           Join current and following line into one line

• Use command: ":e filename"

       Start new edit session on specified file name without closing current vi /        vim editor process.

• Find/Replace:Example:

       :%s/fff/rrrrr/  -   For all lines in a file, find string "fff" and replace with                                   string "rrrrr" for the first instance on a line.

       :%s/fff/rrrrr/g -  For all lines in a file, find string "fff" and replace with                                   string "rrrrr" for each instance on a line.

       :%s/fff/rrrrr/gc - For all lines in a file, find string "fff" and replace with                                   string "rrrrr" for each instance on a line. Ask for                                           confirmation
       :%s/fff/rrrrr/gi - For all lines in a file, find string "fff" and replace with                                   string "rrrrr" for each instance on a line. Case                                               insensitive.

Extract or Unpack a tar File:

• To extract tar file of type:

       tar -xvf <filename>.tar

• To extract .tar.gz (gzip) file
  
  tar -xzvf <file name>.tar.gz
• To extract .tar.bz2 (bzip2) file

       tar -xjvf file.tar.bz2

• To extarct single file from tar file

        tar -xvf file.tar foo.txt 

        tar -xzvf file.tar.gz foo.txt 

        tar -xjvf file.tar.bz2 foo.txt

Where,
-x : Extract a tar ball.
-v : Verbose output or show progress while extracting files.
-f : Specify an archive or a tarball filename.
-j : Decompress and extract the contents of the compressed archive created by bzip2 program (tar.bz2 extension).
-z : Decompress and extract the contents of the compressed archive created by gzip program (tar.gz extension).

Linux: Process & Threads

• Threads share the address space of the process that created it; processes have their own address space. 
• Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process. 
• Threads can directly communicate with other threads of its process; processes must use inter process communication to communicate with sibling processes. 
• Threads have almost no overhead; processes have considerable overhead. 
• New threads are easily created; new processes require duplication of the parent process. 
• Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes. 
• Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process; changes to the parent process does not affect child processes.

Linux: Device drivers

Device drivers interface applications to hardware.They are run in Kernel space. they are part of Kernel process and are loaded dynamically. 

Linux provides a feature called Kernel modules through which we can extend the functionality of the Kernel at run time.

Device Drivers in Linux are Kernel Modules. 

Device drivers are classified into three types:

1. Character device driver
2. Block device driver
3. Network device driver

Character Device driver:

• Device which works on stream of bytes. 
• This type of device is exposed to client via character device driver. 
• Driver implements – open, close, ioclt, read, write, mmap functionality. 

Block Device driver:

• Devices which work on data chuncks/blocks. Example Hard disk/Flash drives. 
• Block drivers have a completely different interface from character drivers. 

Network interfaces:

• Any network transaction is made through this interface. 
• Interface is defined and implemented for communication with network drivers by linux kernel.

Linux: Named Pipes(FIFO)

A named pipe is really just a special kind of file (a FIFO file) on the local hard drive. Unlike a regular file, a FIFO file does not contain any user information. Instead, it allows two or more processes to communicate with each other by reading/writing to/from this file.

A named pipe works much like a regular pipe, but does have some noticeable differences.

• Named pipes exist as a device special file in the file system.
• Processes of different ancestry can share data through a named pipe.
• When all I/O is done by sharing processes, the named pipe remains in the file system for later use.

The easiest way to create a FIFO file is to use the mkfifo command. This command is part of the standard Linux utilities and can simply be typed at the command prompt of your shell. You may also use the mknod command to accomplish the same thing.

prompt> mkfifo /tmp/myFIFO

we can also use of the mknod() system call:

LIBRARY FUNCTION: mknod(); 

PROTOTYPE: int mknod( char *pathname, mode_t mode, dev_t dev);

RETURNS: 0 on success, -1 on error: 

              errno = EFAULT (pathname invalid) 

                         EACCES (permission denied) 

                         ENAMETOOLONG (pathname too long) 

                         ENOENT (invalid pathname) 

                         ENOTDIR (invalid pathname)

mknod("/tmp/MYFIFO", S_IFIFO|0666, 0);

Normally, blocking occurs on a FIFO. In other words, if the FIFO is opened for reading, the process will "block" until some other process opens it for writing. This action works vice-versa as well. If this behavior is undesirable, the O_NONBLOCK flag can be used in an open() call to disable the default blocking action

Linux: Pipes(Half Duplex)

Pipe is an effective way of communication(Half Duplex) between process. Pipe has two descriptors. One descriptor is used for reading while other end is used for writing.

Usage of pipe is to have communication between child and parent process. We also use pipe to redirect of output of a process to another process. We often use pipe in our shell scripts.

With half-duplex pipes, any connected processes must share a related ancestry. Since the pipe resides within the confines of the kernel, any process that is not in the ancestry for the creator of the pipe has no way of addressing it. This is not the case with named pipes (FIFOS).

SYSTEM CALL: pipe(); 

PROTOTYPE: int pipe( int fd[2] ); 

RETURNS: 0 on success -1 on error: 

               errno = EMFILE (no free descriptors) 

                          EMFILE (system file table is full) 

                          EFAULT (fd array is not valid) 

NOTES: fd[0] is set up for reading, fd[1] is set up for writing

Virtual File System on Linux

VFS is a kernel software layer that handles all system calls related to file systems. Its main strength is providing a common interface to several kinds of file systems.So that it is possible to separate actual "low-level" filesystem code from the rest of the kernel. 

Interrupt Handling in Linux

What is Interrupt?

An interrupt (also known as an exception or trap) is an event that causes the CPU to stop executing the current program and start executing a special piece of code called an interrupt handler or interrupt service routine (ISR).

There are two different kinds of interrupts:

         •Synchronous interrupt (Exception) produced by the CPU while processing instructions
         •Asynchronous interrupt (Interrupt) issued by other hardware devices

Handling interrupts:
   •Interrupts can occur at any time, the kernel tries to get it out of the way as soon as possible

   •An interrupt can be interrupted by another interrupt
   •There are regions in the kernel which must not be interrupted at all

Two different interrupt levels are defined:
   •Maskable interrupts issued by I/O devices; can be in two states, masked or unmasked. Only   

     unmasked interrupts are getting processed.

   •Nonmaskable interrupts; critical malfunctions (f.e. hardware failure); always processed by the 

    CPU.

Every hardware device has it's own Interrupt Request (IRQ) line. The IRQs are numbered starting from 0. All IRQ lines are connected to a Programmable Interrupt Controller (PIC). The PIC listens on IRQs and assigns them to the CPU. It is also possible to disable a specific IRQ line.

Top Half and Bottom Half:

One of the main problems with interrupt handling is how to perform lengthy tasks within a handler. Often a substantial amount of workmust be done in response to a device interrupt, but interrupt handlers need to finish up quickly and not keep interrupts blocked for long. These two needs (work and speed) conflict with each other,leaving the driver writer in a bit of a bind.

Linux (along with many other systems) resolves this problem by splitting the interrupt handler into two halves. The so-called top half is the routine that actually responds to the interrupt—the one you register with request_irq. The bottom half is a routine that is scheduled by the top half to be executed later, at a safer time. The big difference between the top-half handler and the bottom half is that all interrupts are enabled during execution of the bottom half—that’s why it runs at a safer time.

To implement bottom halves,two methods:
1) task lets
2) work queues

Linux: Kernel

A kernel is a central component of an operating system. It acts as an interface between the user applications and the hardware. The sole aim of the kernel is to manage the communication between the software (user level applications) and the hardware (CPU, disk memory etc). The main tasks of the kernel are :

• Process management 
• Device management 
• Memory management 
• Interrupt handling 
• I/O communication 
• File system...etc..

What is a PCB (process control block)? What is its significance in the kernel?

A process control block or PCB is a data structure (a table) that holds information about a process. Every process or program that runs needs a PCB. When a user requests to run a particular program, the operating system constructs a process control block for that program. The PCB contains important information about the specific process including:-

• The current state of the process i.e., whether it is ready, running, waiting, or whatever. 
• Unique identification of the process in order to track "which is which" information. 
• A pointer to parent process. 
• Similarly, a pointer to child process (if it exists). 
• The priority of process (a part of CPU scheduling information). 
• Pointers to locate memory of processes. 
• A register save area. 
• The processor it is running on.

Semaphore and Mutex

A Mutex controls access to a single shared resource. It provides operations to acquire() access to that resource and release() it when done.

A Semaphore controls access to a shared pool of resources. It provides operations to Wait() until one of the resources in the pool becomes available, and Signal() when it is given back to the pool.

There are two types of Semaphores:

1. Counting Semaphore
2. Binary Semaphore                                

When number of resources a Semaphore protects is greater than 1, it is called a Counting Semaphore. When it controls one resource, it is called a Binary Semaphore. A Binary semaphore is equivalent to a mutex.

Linux: Kernel Space and User Space

Linux kernel runs under a special privileged mode as compared to user space applications. 

Kernel runs in a protected memory space and it has access to entire hardware. This memory space and this privileged state collectively known as kernel space or kernel mode.

User space programs runs in a unprivileged mode and it has limited access to resources and hardware.

User space applications can not directly access to kernel memory but kernel has access to entire memory space.

Linux: fork() system call

System call fork() is used to create the new process,which becomes the child process of the caller.After a new child process is created ,both the will execute the next instruction following the fork() system call.

If fork() returns negative value,creation of child process unsuccessful

fork() returns “0” to the newly created child process.

fork() returns positive value,process ID of the child process to parent.

Linux will make the exact copy of the parents address space and give it to the child process. So ,the parent and child processes have separate address spaces.

main()
{
           fork();
           fork();
           fork();
        printf("hello world");
}
— will print 8 times.

What is Spinlock?

A spinlock is a lock where the thread simply waits in a loop ("spins") repeatedly checking until the lock becomes available. Since the thread remains active but isn't performing a useful task, the use of such a lock is a kind of busy waiting.

Spinlocks are efficient if threads are only likely to be blocked for a short period of time, as they avoid overhead from operating system process re-scheduling or context switching. For this reason, spinlocks are often used inside operating system kernels. However, spinlocks become wasteful if held for longer durations, preventing other threads from running and requiring re-scheduling.

Scheduling Algorithms in RTOS

  Based on scheduling algorithms, scheduler decides the task execution. 

There are two types

·         Preemptive priority based scheduling:

o   Most real time kernels use this scheduling by default.

o   Real-time kernels generally support 256 priority levels, in which 0 is the highest and 255 thelowest. Some kernels appoint the priorities in reverse order,

o   Tasks are assigned Priority levels when they are created, task priority can be changed dynamically using kernel provided calls.

o     With a preemptive priority-based scheduler, each task has a priority, and the highest-priority task runs first.

o   Task 1 ispreempted by higher-priority task 2, which is then preempted by task 3. When task 3 completes,task 2 resumes; likewise, when task 2 completes, task 1 resumes.

·         Round Robin scheduling:

o   Round-robin scheduling provides each task an equal share of the CPU execution time.

o   Which uses time slicing toachieve equal allocation of the CPU for tasks of the same priority.

o     A run-time counter tracks the time slice for each task, incrementing onevery clock tick. When one task’s time slice completes, the counter is cleared, and the task isplaced at the end of the cycle.

If a task in a round-robin cycle is preempted by a higher-priority task, its run-time count is savedand then restored when the interrupted task is again eligible for execution. This idea is illustratedin Figure, in which task 1 is preempted by a higher-priority task 4 but resumes where it left offwhen task 4 completes.

Linux Boot Process

BIOS (Basic Input/output System):

·         When we power on BIOS performs Power On Self Test (POST) for all different hardware components in the system to make sure that everything is working properly.

·         Also it checks, computer is being started from off position (cold boot) or restart(warm boot).

·         Retrieves information from CMOS (Complementary Metal-Oxide Semiconductor) a battery operated memory chip on the motherboard that stores time, date, and critical system information.

·         Once BIOS sees everything is fine, it will start searching for boot loader.

·         It looks for boot loader in floppy, cd-rom, or hard drive. You can press a key (typically F12 of F2, but it depends on your system) during the BIOS startup to change the boot sequence.

·         Once the boot loader program is detected and loaded into the memory, BIOS gives the control to it.

·         So, in simple terms BIOS loads and executes the MBR boot loader.

MBR (Master Boot Record):

·         MBR stands for Master Boot Record.

·         It is located in the 1st sector of the bootable disk. Typically /dev/hda, or /dev/sda

·         MBR is less than 512 bytes in size. This has three components 1) primary boot loader info in 1st 446 bytes 2) partition table info in next 64 bytes 3) mbr validation check in last 2 bytes.

·         It contains information about GRUB (or LILO in old systems).

·         So, in simple terms MBR loads and executes the GRUB boot loader.

Boot Loader:

·         A boot loader, also called a boot manager, is a small program that places the operating system (OS) of a computer into memory.

·         GRUB stands for Grand Unified Boot loader:

o   GRUB displays a splash screen, waits for few seconds, if you don’t enter anything, it loads the default kernel image as specified in the grub configuration file.

o   GRUB has the knowledge of the file system (the older Linux loader LILO didn’t understand filessystem).

o   Grub configuration file is /boot/grub/grub.conf (/etc/grub.conf is a link to this).

·         LILO(Linux Loader):

o   LILO is a linux boot loader which is too big to fit into single sector of 512-bytes.

o   So it is divided into two parts: an installer and a runtime module.

o   The installer module places the runtime module on MBR.The runtime module has the info about all operating systems installed.

o   When the runtime module is executed it selects the operating system to load and transfers the control to kernel.

o   LILO does not understand filesystems and boot images to be loaded and treats them as raw disk offsets

Kernel:

·         Mounts Root file system.

·         Initializes devices and loads initrd module.

·         initrd stands for Initial RAM Disk.

·         initrd is used by kernel as temporary root file system until kernel is booted and the real root file system is mounted. It also contains necessary drivers compiled inside, which helps it to access the hard drive partitions, and other hardware.

·         init was the 1st program to be executed by Linux Kernel, it has the process id (PID) of 1.

Init:

·         First process which is started in linux is init process.

·         Looks at the /etc/inittab file to decide the Linux run level.

·         Following are the available run levels

o   0 – halt

o   1 – Single user mode

o   2 – Multiuser, without NFS

o   3 – Full multiuser mode

o   4 – unused

o   5 – X11

o   6 – reboot

·         Init identifies the default initlevel from /etc/inittab and uses that to load all appropriate program.

Run Levels:

·         When the Linux system is booting up, you might see various services getting started. For example, it might say “starting sendmail …. OK”. Those are the runlevel programs, executed from the run level directory as defined by your run level.

·         Depending on your default init level setting, the system will execute the programs from one of the following directories.

o   Run level 0 – /etc/rc.d/rc0.d/

o   Run level 1 – /etc/rc.d/rc1.d/

o   Run level 2 – /etc/rc.d/rc2.d/

o   Run level 3 – /etc/rc.d/rc3.d/

o   Run level 4 – /etc/rc.d/rc4.d/

o   Run level 5 – /etc/rc.d/rc5.d/

o   Run level 6 – /etc/rc.d/rc6.d/

RTOS Features

1)    Multithreading and preemptability:The schedulershould be able to preempt any task in the system and allocate the resource to the task that needs it most even at peakload.

2)    Thread Priority: All the tasks are assigned priority level to facilitate preemption. The highest priority task that is ready to run will be the task that will be running.

3)    Inter Task communication and synchronization:For multiple tasks to communicate in a timely manner and to ensure data integrity among each other, reliable and

sufficient inter-task communication and synchronization mechanisms are required.

4)    Priority inheritance: Should priority inversion this is required       

5)    Short Latencies:

·         Task switching Latency: The time needed to save the context of currently executing task and switching to another task.

·         Interrupt Latency:The time elapsed between execution of the last instruction of the interrupted task and the firstinstruction in the interrupt handler.

·         Interrupt dispatch Latency:The time from the last instruction in the interrupt handler to the next task scheduled torun.

Different Types of RTOS

Hard Real time:Hard real time systems are the ones in which critical deadlines are met strictly. Missing a deadline means failure of the system.

Ex: Mission critical systems like missile launching systems.

Firm Real time:If missing its deadline makes the result useless, but missing does

not cause serious damage

Soft Real Time:In Soft real time systems, occasional missing of deadlines (small delays) are acceptable and not considered as failure. Rather it is considered as performances degrade.

Ex: Cell phones