Small course Loadable Kernel Modules in linux Kernel 2.6
Loadable Kernel Modules in linux Kernel 2.6
Learning Objectives
Reference
History of Loadable Module
Advantages of using LKMs
Inserting kernel Modules
Removing Modules
Using modprobe
Learning Objectives
- Discuss History of Loadable Kernel Modules (LKM).
- Describe advantages of Using LKMs
- Describe what LKMs can do.
- Discuss LKM Utilities
- Installing and removing
- Loadable Kernel Modules in Kernel 2.6
Reference
- Module-HOWTO
- /usr/share/doc/howto/en/html/Module-HOWTO
History of Loadable Module
- Loadable Kernel Modules did not exist in Linux in the beginning.
- Loadable Kernel Modules have been around at least since Linux1.2 (1995).
- Device drivers were always quite modular, and only small amount of work was needed to make them Loadable Kernel Module.
- Since about 2000 everything that make sense as an LKM had the option of being LKM.
Advantages of using LKMs
- Don’t have to rebuild Kernel Often
- Helps you diagnose system problem
- Saves Memory because only required modules will be loaded in the memory.
- Faster to maintain and debug.
- Gives same performance as Kernel built-in code.
- Device drivers
- File System Drivers
- System Calls
- Network Drivers
- TTY line disciplines
- Executable interpreters
- Loadable Kernel Modules are also know as Kernel Modules.
- After building the Kernel image issue following commands: make modules Above command compiles the source code and creates module object files
- Then issue the following commands make modules_install Above command will copy all modules over to the conventional locations
- insmod Insert an LKM into the kernel.
- rmmod Remove an LKM from the kernel.
- depmod Determine interdependencies between LKMs.
- lsmod List currently loaded LKMs.
- modinfo Display contents of .modinfo section in an LKM object file.
- modprobe Insert or remove an LKM or set of LKMs intelligently. For example, if load A before loading B, Modprobe will automatically load A when you tell it to load B.
Inserting kernel Modules
- Basic program for inserting LKMs is insmod.
- Try to load the modules “msdos” and “ntfs”.
- Try following commands to load the modules msdos, the path for module may change depending on your Kernel Version:
# cd /lib/modules/2.6.18-53el5/kernel/fs
# insmod msdos/msdos.ko
- Loaded modules may be listed by using the “lsmod” command.
- You may also get information about modules from “/proc/modules” cat /proc/modules
- You may also get information about “devices” and “interrupts” from “/proc/devices” and “/proc/interrupts”
Removing Modules
- Modules may be removed by using “rmmod” command.
- All these commands must be executed by superuser.
Using modprobe
- Using modprobe is a better way of loading modules. Modprobe checks dependencies and also loads the modules needed to support the module being loaded.
- Many modules such as some CDROM Drivers and Networks Drivers require certain parameters to be passed with the modules.
- The files “/etc/modprobe.conf”, “/etc/modprobe.conf.local” and the directory “/etc/modprobe.d” contains parameters for modules that directly access the hardware. As modprobe can use information from these files it is a better method to load modules.
- There are no standard module parameters, drivers may have their own set of parameters. To find out parameters of a driver read the documentation for that module in the directory “/usr/src/linux/documentation”.
- Kmod automates the process of loading Kernel Module.
- Kmod keeps on running in the background and automatically loads a kernel Module using “modprobe” whenever a desired feature is needed in the Kernel.
- Kmod does not unload the modules if not required in feature but with Amount of RAM available this is not a big issue.
- The Linux 2.6 kernel introduces a new, unified framework for device drivers, which requires changes to custom device drivers developed to run under earlier versions of the Linux kernel.
- The new driver model provides a framework for full and complete support for
- device Plug and Play
- power management
- Defines the interfaces that these subsystems can use when communicating with individual drivers.
- The new driver framework provides a much cleaner separation of responsibilities between buses and drivers.
- The 2.6 Linux kernel also introduces the sysfs filesystem to provide a hierarchical view of each system's device tree (and to prevent further overloading of the proc filesystem).
- A new naming convention for loadable kernel modules, using the .ko extension (kernel object) rather than the standard .o (object) extension used in all previous stable releases of the Linux kernel.
- Kernel loadable module reduce the size of Kernel.
- It is easier to debug your system when using Kernel Modules.
- New drivers can be added to system without recompiling the Kernel.
- A set of utilities is available to manage Kernel Modules.
Overview of the linux kernel
Overview of the linux kernel
Abstract
This article discusses the basic kernel features of the linux kernel.It starts from the history of the linux kernel to basic operataing designs required for a kernel and how linux implements it in a nutshell.Then it concludes by promising future articles on different layers of the linux kernel and also an articles on Linux kernel 2.6 features,Future of Linux which will be contributed by different members of the lkg_india group.
Audience
I myself being a kernel newbie,has intended to write the article in such a fashion that it will be understood by anyone who has used the computer.It can also be read by experienced kernel developers so as to refresh their thoughts and also suggest/crticise the mistakes in the article.This article is dedicated for free for the benefit and education of all. That a person seeking knowledge should have the opportunity to find it.Thanks to every other document written with the same vein which has made this article possible.
Intoduction
To start off immediately what does kernel mean?Well thats what this blog is for,for us to understand what the kernel is.Hopefully future articles in the blog will make us understand the kernel completely and clearly.Well here is the literal meaning of the word "kernel" straight from dict.org
"The central, substantial or essential part of anything;the gist; the core;"
This is how the Online dictionary of computing defines the word kernel
"The essential part of Unix or other operating systems, responsible for resource allocation,low-level hardware interfaces, security etc"
Operating System
Any computer system includes a basic set of programs called the operating system. The most important program in the set is called the kernel.The other programs are less crucial utilities; they can provide a wide variety of interactive experiences for the user as well as doing all the jobs the user bought the computer for but the essential shape and capabilities of the system are determined by the kernel.
Is kernel the entire operating system?
No,as discussed above.The kernel is the core component of the operating system.The operating system contains the Kernel plus other systen utilities which use the kernel to provide higher level house keeping tasks.Technically speaking,Linux is only the kernel,as it does not provide system utilities like file system utilities,compilers,editors,the graphical user interface which are provided by any other operating system.So linux users typically rely on commercial ditributions like Suse,Red Hat etc., to have the entire operating system.Having known the what a Operating system and what the kernel is,let us know something about the history of the Linux kernel.
Linux,the revolutionay open source kernel
Linux was intially developed by Linus in Aug 1991.As a source of inspiration listed below is his mail on the famous comp.os.newsgroup
"----- Message from "Linus Benedict Torvalds"
on Mon, 26 Aug 1991 02:27:08 +0530 -----
Subject: What would you like to see most in minix?
Hello everybody out there using minix-
I'm doing a (free) operating system (just a hobby, won't be big
and professional like gnu) for 386(486) AT clones. This has
been brewing since april, and is starting to get ready. I'd like
any feedback on things people like/dislike in minix; as my OS
resembles it somewhat (same physical layout of the file-sytem
due to practical reasons)among other things.
I've currently ported bash (1.08) an gcc (1.40), and things seem to work.
This implies that i'll get something practical within a few months, and I'd
like to know what features most people want. Any suggestions are welcome,
but I won't promise I'll implement them :-)
Linus Torvalds torvalds@kruuna.helsinki.fi"
As seen from the mail there was an effort by the FSF(Free Software Foundation) headed by Richard Stallman to build a complete free professional Operating System. So lets talk about FSF before proceeding further.
FSF - RICHARD STALLMAN
The FSF was founded by Richard Stallman in 1984.Its also know as the GNU software project which was launched to built a complete free operating system.When richard started working for writing a free OS he felt that he should use a free editor to write programs for the Operating system,then he wrote the GNU emacs editor.Then they needed a free compiler to compile their C programs,thereby was born the GNU Compiler collection(gcc).Later when linus released Linux kernel free and it became popular,it was adopted by FSF as their kernel.So GNU utilities were used with the Linux kernel to make the complete Operating System.Now Linux remains as one of the most popular Open source operating system in the world.
Features of the Linux Kernel
I.Monolithic kernel with module support
The linux kernel is monolithic with module suport.So now let us try to decipher the meaning of the previous sentence and why linux adopted a monolithic kernel with module strategy.
Monolithic kernel
A monolithic kernel is a single large complex "do-it-yourself" kernel program which is composed of several different logical entities(kernel layers).Each kernel layer is integrated in to the large kernel program and runs in kernel mode(more on kernel mode later)on behalf of the current process.
Microkernel
A micro kernel consists of a small set of important fucntions in the kernel generally a simple scheduler,synchronisation primitives.Several System processes that run on top of the kernel to implement other OS layer functions like memory allocators,device drivers,system calls,file system etc., These kernel layers cordinate together by message passing between them.Therby because of the message passing the microkernel is slower than the monolithic kernel.
Monolithic Vs Microkernel
Monolithic Kernel is faster than microkernel as stated above.However,Microkernel has some theoritical advantages over the monolithic kernel.They are as follows,
1.The microkernel occupies less RAM,since system processes(as disscussed above) that are not doing their functionalities are swapped out or destroyed.
2.The architecture of the microkernel forces the programmers to adopt a modularized approach
as different layers of the kernel are independant of each other.Moreover,the different layers interact with each other through clear well defined software interfaces.
3.Moreover, an existing microkernel operating system can be fairly easily ported to other architectures, since all hardware dependent components are generally encapsulated in the microkernel code.
Modules,the linux way
Modules are a kernel feature that effectively achieves many of the theoretical advantages of microkernels without introducing performance penalties. A module is an object file whose code can be linked to (and unlinked from) the kernel at runtime. The object code usually consists of a set of functions that implements a filesystem, a device driver, or other features at the kernel's upper layer. The module, unlike the external layers of microkernel operating systems, does not run as a specific process. Instead, it is executed in Kernel Mode on behalf of the current process, like any other statically linked kernel function.
Advantages provided by a monolithic kernel with modules
1.Less main memory usage
A module is linked to the kernel when its functionality is needed and unlinked when its no longer used.This mechanism is done automatically by the kernel and is transparent to the user.
2.Modularized approach
Modules force the programmers to intoduce well defined software interfaces for interaction.
3.Platform independence
A module does not depend on a fixed hardware platform.A module like device driver is infact specfic to the device but not to the hardware platform(x86,sparc etc..,)
4.Faster
Since the module is linked in to the kernel,it is faster like the monolithic kernel as there is no message passing as in microkernel.Infact there is small time we lose for linking and unlinking of the modules which is less than that of the time required for message passing in microkernels.
II.Linux Filesystem
Files are a basic abstraction provided by the operating system along with processes(more about processes later).A file is an information container structured as a sequence of bytes.From the user's point of view, files are organized in a tree-structured name space starting from /(parent) which is called the root directory.
Different file types in linux
The beauty of linux lies in the fact that it almost treats everything as files including devices. There are the following types of files
1. Regular files
2. Directory files
3. Symbolic links
4. Device files(character,block).
5. Pipes
6. Sockets
The first three types are constituents of the linux filesystem.Device files are related to I/O devices and device drivers integrated into the kernel.Pipes and sockets are special files used for interprocess communication.
Inode
All information needed by the filesystem to handle a file in included in a data structure called the inode.Each file has its own inode which the filesystem uses to identify the file.The following information is kept in the inode
1.File type(as discussed above)
2.Number of hard links associated with the file(see next section)
3.File length in bytes
4.Inode number that identifies the file within the filesystem
5.User ID of the file owner(discussed below)
5.Group ID of the file(discussed below)
6.The last modify time
7.Access rights and file mode (discussed below)
Hard links and symbolic links
The same file may have several links included in the same directory or in different ones, thus several filenames.
Hardlink
A hardlink is just a different filename but points to the same inode on the disc.So the file information of the both the file and the hard link will coincide as they point to the same inode.The unix command used to create a hard link is
$ln f1 f2
f2 is the hard link for file f1
Limitations of hard link
1.Hard links cannot exist to directories as it might transform the tree structure in to a graph with cycles thus making ti impossible to locate a file according to its name.
2.Hard links can be created only for files in the same filesystem as inode is the same.This is a serious limitation as Linux supports variuos other filesystems.
Softlink
Symbolic links are short files that contain an arbitrary pathname of another file. The pathname may refer to any file located in any filesystem,it may even refer to a non exixtent file or a file in another filesystem.Thus symbolic links are short files than contain the pathname of the file that is linked to.So a symbolic link will have a separate inode for itself.The unix command to create a symbolic link is
$ln -s f1 f2
f2 is a symbolic link to f1.The linux filesystem will create a sym link f2 and will write in to it the pathname for f1.In this way f2 can refer to f1.
Users and Groups
A multiuser system is a computer that is able to concurrently and independently execute several applications belonging to two or more users. "Concurrently" means that applications can be active at the same time and contend for the various resources such as CPU, memory, hard disks, and so on. "Independently" means that each application can perform its task with no concern for what the applications of the other users are doing.
In a multiuser system, each user has a private space on the machine: typically, he owns some quota of the disk space to store files, receives private mail messages, and so on. The operating system must ensure that the private portion of a user space is visible only to its owner. In particular, it must ensure that no user can exploit a system application for the purpose of
of violating the private space of the another user.
All users are identified by a unique number called the User ID , or UID. Usually only a restricted number of persons are allowed to make use of a computer system. When one of these users starts a working session, the operating system asks for a login name and a password.If the user does not input a valid pair, the system denies access. Since the password the assumed to be private the users privacy is maintained.In order to selectively share material with other users, each user is a member of one or more groups, which are identified by a unique number called a Group ID,or GID. Each file is associated with a UID and GID.
Access rights and mode
The users of a file fall in to one of this three classes
1.The owner of the file
2.The users who belong to the same groups as that of the owner
3.All other users(others) in the system
There are three types of access rights for each of these classes namely
Read,write and execute.
Thus the set of access rights associated with a file in linux consists of nine(3(for diff classes of users) * 3(for different access rights)) different flags.There are three additional flags which define the file mode which have a meaning when applied to executable files.They are
1.SUID flag
If the executable file has the SUID flag set, the process gets the UID of the file owner.
2.SGID
If the executable file has the SUID flag set, the process gets the GID of the file group.
The suid and sgid programs are important programs to be protected in a secure system as they change the id's during execution.So an intruder might use these programs for executing something malicious on behalf of the user who is suid or sgid.
3.sticky
An executable file with the sticky flag set corresponds to a request to the kernel to keep the program in memory after its execution terminates.These flag is set when many processes share the same program for example vi might be used by many processes.So vi can have its sticky bit set.This flag has become obsolete as other approaches like copy-on-write are used now for sharing code pages between processes.
chmod is the unix command used to allow the user to set access and mode flags for a file.
Example
$chmod 4777 f1
4777 in binary is 100111111111.So there are 12 bits corresponding to User classes,access and mode permissions as below.
100---will set the suid flag for f1(mode of the file)
111---will give read,write,exec access to owner of f1
111---will give read,write,exec access to other users of the group which the user belongs to.
111---will give read,write,exec access to other remaining users in the system.
Virtual File System technology
Linux follows a object oriented Virtual File System technology inspired from SVR4 and solaris.There linux supports most of the filesystems like DOS,FAT,ext3,resierfs,JFS etc..,Also porting a file system to Linux is very easy task because of the VFS technology that linux follows.
III.Processes in Linux
Process is another fundamental abstraction(apart from File) provided by the OS.Having seen a overview of the filesystem in linux let us see how linux handles processes.
A process can be defined either as "an instance of a program in execution," or as the "execution context" of a running program. In traditional operating systems, a process executes a single sequence of instructions in an address space,the address space is the set of memory addresses that the process is allowed to reference.Operating systems like linux allow multiple execution flows,that is,multiple sequences of instructions executed in the same address space.
Multiuser systems must allow different processes to be active concurrently and thereby contend for tbe resources,mainly the CPU.Such systems are said to be multitasking systems.The scheduler is the part of the kernel which decided which process will run on the CPU at a given instant of time.It is done in such a manner that every process feels that it is the only process running on the CPU.This concept is called virtualization of the processor.Another virtualisation that is provided by linux(or any OS) to processes is the virtual memory where in a process feels that it has the entire memory on system available to it.Processes of a multiuser system must be preemptive ie., the scheduler of the kernel will decide how long each process can hold the CPU.Thereby if a higher priority process comes in to execution the scheduler will preempt the lower priority running process.
Linux is a multiprocessing system with preemptive processes.
Process management in Linux
The fork( ) and exit( ) system calls are used respectively to create a new process and to terminate it.Linux maintains a clear distinction between the process and the program by using exec( )-like system call to load a new program.After exec has been done the process resumes execution with a brand new address space containing the loaded program.
Process Creation
Processes in Linux follow a parent child relationship.The Process which invokes the fork is the parent and the process that is created is the child.The init process(created by the init.c of the kernel) is the root parent of all the other processes in linux.The task_struct is the data structure in the kernel that defines the process.Parents and children can easily find each other as the data structure contains information about the relationship.Linux implements fork using the copy-on-write approach which defers address space duplication of parent to the child on fork.The address space is copied only when a write is being made in to the address space.So till a write happens the parent and the child share only the Page tables and not the address space.The copy-on-write has the following advantage
1.Most instances of fork are followed by an exec to a program as the child does some other functionailty when compared to the program.Thereby it is a waste(an overhead) to copy the address space of the parent to the child and then again immediately overwrite the address space.So this overhead is reduced by the copy-on-write approach.
Process Termination
The exit system call is used to terminate a process.The kernel handles this system call by releasing the resources owned by the process and sending the parent process a SIGCHLD signal, which is ignored by default.
Zombie processes
The parent enquires about the termination of the child process by the wait( ) system call which allows a process to wait until one of its children terminates; it returns the process ID (PID) of the terminated child.A special zombie process state is introduced to represent terminated processes on which the parent has not issued a wait system call.The process descriptor of the child is released after the wait is executed by the parent and the child process goes to the stopped state.Now the question arises if the parent does not issue a wait call and if it terminates what happens to the child in Zombie state.There will be many zombies which will occupy useful memory.The solution lies in init process which takes over as the parent of child process whose parents have terminated.It routinely issues wait calls thereby getting rid of the zombies.
IV.The process/Kernel model
Having known about the kernel architecture and the basic abstractions(file,process) let us now see how the linux kernel is modelled.On multiuser/multitasking systems the operating system must hide all low level details concerning the physical organization of the computer from applications run by user.So when a user application wants to access a hardware,it request the kernel which evaluates the request and if it chooses to grant access,it interacts with the hardware on behalf of the process.This thereby enhances the security on multiuser systems which prevent user applications from damaging the system hardware resources.Probably,this is the reason why DOS does not require such a model as it is single user system which allows the user to do anything with the systems hardware.
Well how does linux implement the above mentioned feature.All modern operating systems,implement the above mentioned feature with the help of hardware specific features which forbids the user programs to interact directly with the hardware.For example,the x86 CPU provides four rings of execution from ring 0 to ring 3 in the order of descending privileges.Linux uses the two rings namely ring 0 and ring 3 for implementing the feature.User mode applications run in ring 3 of x86 and kernel runs in ring 0 of x86.Therefore these rings correspond to the User mode and kernel mode concept of the linux operating system.
Note:Intel introduced protected mode(ring levels) starting from 80386.So Linux was developed for 80386 and above(commonly referred as i386/i686 architectures).
When a program is executed in User Mode, it cannot directly access the kernel data structures or the kernel programs. When an application executes in Kernel Mode, however, these restrictions no longer apply. Each CPU model provides special instructions to switch from User Mode to Kernel Mode and vice versa. A program executes most of the time in User Mode and switches to Kernel Mode only when requesting a service provided by the kernel. When the kernel has satisfied the program's request, it puts the program back in User Mode.
The kernel is a process manager and not a process by itself.The creation,deletion and handling of processes are done by a group of routines in the kernel.The process/kernel model in linux allows a process to request a kernel service through system calls.System calls thereby take the process from user mode to kernel mode,does the necessary request and puts the process back in the user mode.
A switch to Kernel mode from user mode will happen by any one of these methods
1.Through system call by a process as discussed above
2.The CPU exceutes an exception.The exception has to be handled by the kernel on behalf of the process that caused the exception.For example,the kernel must handle the page fault exception.
3.A device issues an interrupt to the CPU to notify the CPU an event.In this case the kernel executes the corresponding interrupt handler for the device.
Linux also has some privileged kernel level processes.They are called kernel threads.Linux uses kernel threads in a limited way for certain functionalites.They execute in the kernel thread.keventd is an example of a kernel thread.
V.Kernel Synchronisation
On multiuser/multitasking systems many processes must be handled by the kernel at a single instant of time as several processes may be executing in the kernel at the same time.For example ,a process executing on a CPU in a uniprocessor system might be waiting on some I/0.During this time the process in kernel mode is interleaved and another process is executed in the kernel.When the I/O interrupt is finished the process waiting for I/O is executed again.So the Linux kernel must be reentrant,ie..,multiple processes must be handled by the kernel maintaining the global data structures they use in a consistent state.
Before proceeding further,we will see the definition of a kernel control path.A kernel control path is a sequence of instructions executed in the kernel mode on behalf of a process or on behalf of an interupt.
How can Kernel reentrancy be achieved?
The following are the methods to achieve kernel reentrancy
1.Reentrant functions
2.Atomic operations
3.Non Premptive kernel
4.Interrupt disabling
5.Locking mechanisms(semaphores and spinlocks)
Reentrant functions
Reentrant functions are those functions which operate only on local variable and not on global data structures.But the kernel cannot only be limited to reentrant functions.Also the kernel has a fixed stack which is small,so local variable must be less.
Before looking at other mechanisms of achieving reentarncy let us see what a race condition is and what is a critical region.
Assume that there is a global data structure(a resource) R1.If R1 is one the resource is free.Now a kernel control path KCP1 reads the value of R1 which is 1 i.e.., the resource is free.Now if KCP1 is interleaved from the kernel and if KCP2 reads the value of R1 which is still 1.It will take the resource and decrement the value to 0.Now if KCP1 resumes execution it still sees that the resource is free and decrements the value of R1 to -1,thereby taking the resource.So both the KCP's are using the resources leading to dangerous effects.This is a race condition.
Atomic operations
It is always safe to access a global variable with a single atomic uninteruptible instruction.For example in the previuos example if the two kernel paths have read the data and decremented the value of R1 in a singl operation there would have been no race condition.
But its always not possible to access data structures in a single atomic operation.Any section of code that should be finished by a process befored another process is scheduled is called the critical region.Further mechanisms we will see how to protect critical regions.
Non Premptive kernel
A simple solution to synchronisation problems is to make the kernel non preemptive ie., when a process is in kernel mode it cannot be interleaved by any other process until it voluntarily relinquishes the CPU(in which case it makes sure that the Data structures are in a consistent state).Therefore in a non preemptive kernel all the global data structures except those that are used by interupts and exceptions are safe(as interleaving of a process in kernel mode happens when a interuppt or exception occurs).Non premptability is ineffective in Multiprocessor systems as two kernel control paths executing in different CPU's can access the same data structure.The linux kernel was non preemptable until 2.5 devt series and 2.6 stable series.Now the kernel is preemptible.Preemptible kernels are more suited for time critical real time processes.
Interrupt disabling
Another method to achieve synchronisation is to disable interuppts before entering a critical region and enabling it after the critical region.This is a simple solution but is not optimal as large critical region will have the Hardware interrupts freezed for a long time leading to a freeze.Also it is ineffective in multiprocessor systems as the data structure might be accessed by another process running in a different CPU.
Locking mechanisms
The locking mechanisms lock the corresponding global data structure in question thereby making sure that when the lock is acquired only a single process can access the data structure.They are effective both in Uniprocessor and Multiprocessor systems.The locking mechanisms used by the linux kernel are
1.Semaphores
2.Spin Locks
Semaphores
A semaphore is simply a counter associated with a data structure; the semaphore is checked by all kernel threads before they try to access the data structure.Each semaphore may be viewed as an object composed of:
a)An integer variable
b)A list of waiting processes
c)Two atomic methods: down() and up()
The down() method decrements the value of the semaphore. If the new value is less than 0, the method adds the running process to the semaphore list and then blocks (i.e., invokes the scheduler). The up() method increments the value of the semaphore and, if its new value is greater than or equal to 0, reactivates one or more processes in the semaphore list. Each data structure to be protected has its own semaphore, which is initialized to 1. When a kernel control path wishes to access the data structure, it executes the down() method on the proper semaphore. If the value of the new semaphore isn't negative, access to the data structure is granted. Otherwise, the process that is executing the kernel control path is added to the semaphore list and blocked. When another process executes the up() method on that semaphore, one of the processes in the semaphore list is allowed to proceed.
SpinLocks
In multiprocessor systems, semaphores are not always the best solution to the synchronization problems. Some kernel data structures should be protected from being concurrently accessed by kernel control paths that run on different CPUs. In this case, if the time required to update the data structure is short, a semaphore could be very inefficient. To check a semaphore, the kernel must insert a process in the semaphore list and then suspend it. Since both operations are relatively expensive, in the time it takes to complete them, the other kernel control path could have already released the semaphore. In these cases, multiprocessor operating systems make use of spin locks. A spin lock is very similar to a semaphore, but it has no process list: when a process finds the lock closed by another process, it "spins" around repeatedly, executing a tight instruction loop until the lock becomes open. Of course, spin locks are useless in a uniprocessor environment. When a kernel control path tries to access a locked data structure, it starts an endless loop. Therefore, the kernel control path that is updating the protected data structure would not have a chance to continue the execution and release the spin lock. The final result is that the system hangs.
Signals and interprocess communication
The linux kernel implements signals for communicating to the process an event.For example,SIGKILL is sent to the process if it receives a terminate signal.The linux kernel implements 32 different posix signals.User processes can communicate with each other with the help of SYS V IPCs like sahred memory,pipes,fifos,semaphores and message queues.
VI.Memory Management in Linux
Memory management is the most complex(as it is architecture dependant) and important activity in the kernel.Linux supports Virtual memory management.Linux uses paging to implement virtual memory concept.Linux does not use segmentation.Memory management will be described in detail in a later article.For now the advantages a virtual memory offers are
1.Several processes can be executed concurrently.
2.It is possible to run applications whose memory needs are larger than the available physical memory.
3.Processes can execute a program whose code is only partially loaded in memory.
4.Each process is allowed to access a subset of the available physical memory.
5.Processes can share a single memory image of a library or program
6.Programs can be relocatable, that is, they can be placed anywhere in physical memory.
7.Programmers can write machine-independent code, since they do not need to be concerned about physical memory organization.
RAM USAGE
The usage of memory is one very important thing that has to be taken care by the kernel.Linux clearly distiguishes between Memory that is dedicated to the kernel and the memory that can be used by the processes.The static kernel image is loaded from the 1st Megabyte of the RAM and is pinned(it is not swapped or paged out).The remaining part of the RAM is used for
1.Kernel dynamic structures
2.Memory for processes
3.Caches for disks etc., to get better performance.
How the memory is allocated for above mentioned three is very important and hence requires a separate article.In a few words, linux takes care of memory allocation problems like internal fragmentation,external fragmentation etc., by making use of buddy system algorithm and slab allocation mechanism.So Linux uses a Slab allocator on top of a buddy system algorithm.
Virtual Adddress space of a process
Every process in linux has a virtual address space(ranging from 0 to 4GB on a 32 bit intel CPU).
A address space of a process contains all the virtual memory addresses that the process can reference.The kernel usually stores a process virtual address space as a list of memory area descriptors(for example memory area descriptors to the code segment,stack segment,heap etc.,).Linux uses demand paging ie., the page is allocated after a page fault happens.
VII.Device drivers
Having discussed most of kernel subsystems namely filesystem,process,synchronisation,interrupts,syscalls,meory management lets see in a nutshell about device drivers.The kernel interacts with I/O devices with help of device drivers.Device drivers are included in the kernel and consist of data structures and functions that control one or more devices like hard disks,keyboard,mouse etc.,Each driver interacts with the remaining part of the kernel (even with other drivers) through a specific interface.There the device driver layer can be seen as the last layer in the kernel interacting with other layers through well defined interfaces.This approach helps programmers to write device specfic code in a separate module without knowing about the kernel source code as well as the internal architecture.
VIII.Linux implementation of threads
Finally,it is mandatory to discuss how linux supports multithreaded application programming as it does in a unique manner.In linux threads are also processes which share the address space of the processes.Linux implements threads as processes because the process creation time in linux is much faster compared to other OS'es.A thread is therefore a process which can scheduled independently of the main process and it shares the same address space.
SUMMARY
In summary a linux kernel is monolithic with modular support and consists of the following subsystems,
1.Filesystem
2.Process management
3.Memory management
4.Synchronisation
5.System calls
6.Device drivers
7.Interrupts and exceptions
8.Signals
The explanation and deciphering of the different kernel layers will be explained in future articles contirbuted by the various members of the lkg_india.I also promise two more articles which will be extension of this article namely
1.Linux kernel 2.6 features
2.Linux VS other Operating systems and the future of linux
Abstract
This article discusses the basic kernel features of the linux kernel.It starts from the history of the linux kernel to basic operataing designs required for a kernel and how linux implements it in a nutshell.Then it concludes by promising future articles on different layers of the linux kernel and also an articles on Linux kernel 2.6 features,Future of Linux which will be contributed by different members of the lkg_india group.
Audience
I myself being a kernel newbie,has intended to write the article in such a fashion that it will be understood by anyone who has used the computer.It can also be read by experienced kernel developers so as to refresh their thoughts and also suggest/crticise the mistakes in the article.This article is dedicated for free for the benefit and education of all. That a person seeking knowledge should have the opportunity to find it.Thanks to every other document written with the same vein which has made this article possible.
Intoduction
To start off immediately what does kernel mean?Well thats what this blog is for,for us to understand what the kernel is.Hopefully future articles in the blog will make us understand the kernel completely and clearly.Well here is the literal meaning of the word "kernel" straight from dict.org
"The central, substantial or essential part of anything;the gist; the core;"
This is how the Online dictionary of computing defines the word kernel
"The essential part of Unix or other operating systems, responsible for resource allocation,low-level hardware interfaces, security etc"
Operating System
Any computer system includes a basic set of programs called the operating system. The most important program in the set is called the kernel.The other programs are less crucial utilities; they can provide a wide variety of interactive experiences for the user as well as doing all the jobs the user bought the computer for but the essential shape and capabilities of the system are determined by the kernel.
Is kernel the entire operating system?
No,as discussed above.The kernel is the core component of the operating system.The operating system contains the Kernel plus other systen utilities which use the kernel to provide higher level house keeping tasks.Technically speaking,Linux is only the kernel,as it does not provide system utilities like file system utilities,compilers,editors,the graphical user interface which are provided by any other operating system.So linux users typically rely on commercial ditributions like Suse,Red Hat etc., to have the entire operating system.Having known the what a Operating system and what the kernel is,let us know something about the history of the Linux kernel.
Linux,the revolutionay open source kernel
Linux was intially developed by Linus in Aug 1991.As a source of inspiration listed below is his mail on the famous comp.os.newsgroup
"----- Message from "Linus Benedict Torvalds"
on Mon, 26 Aug 1991 02:27:08 +0530 -----
Subject: What would you like to see most in minix?
Hello everybody out there using minix-
I'm doing a (free) operating system (just a hobby, won't be big
and professional like gnu) for 386(486) AT clones. This has
been brewing since april, and is starting to get ready. I'd like
any feedback on things people like/dislike in minix; as my OS
resembles it somewhat (same physical layout of the file-sytem
due to practical reasons)among other things.
I've currently ported bash (1.08) an gcc (1.40), and things seem to work.
This implies that i'll get something practical within a few months, and I'd
like to know what features most people want. Any suggestions are welcome,
but I won't promise I'll implement them :-)
Linus Torvalds torvalds@kruuna.helsinki.fi"
As seen from the mail there was an effort by the FSF(Free Software Foundation) headed by Richard Stallman to build a complete free professional Operating System. So lets talk about FSF before proceeding further.
FSF - RICHARD STALLMAN
The FSF was founded by Richard Stallman in 1984.Its also know as the GNU software project which was launched to built a complete free operating system.When richard started working for writing a free OS he felt that he should use a free editor to write programs for the Operating system,then he wrote the GNU emacs editor.Then they needed a free compiler to compile their C programs,thereby was born the GNU Compiler collection(gcc).Later when linus released Linux kernel free and it became popular,it was adopted by FSF as their kernel.So GNU utilities were used with the Linux kernel to make the complete Operating System.Now Linux remains as one of the most popular Open source operating system in the world.
Features of the Linux Kernel
I.Monolithic kernel with module support
The linux kernel is monolithic with module suport.So now let us try to decipher the meaning of the previous sentence and why linux adopted a monolithic kernel with module strategy.
Monolithic kernel
A monolithic kernel is a single large complex "do-it-yourself" kernel program which is composed of several different logical entities(kernel layers).Each kernel layer is integrated in to the large kernel program and runs in kernel mode(more on kernel mode later)on behalf of the current process.
Microkernel
A micro kernel consists of a small set of important fucntions in the kernel generally a simple scheduler,synchronisation primitives.Several System processes that run on top of the kernel to implement other OS layer functions like memory allocators,device drivers,system calls,file system etc., These kernel layers cordinate together by message passing between them.Therby because of the message passing the microkernel is slower than the monolithic kernel.
Monolithic Vs Microkernel
Monolithic Kernel is faster than microkernel as stated above.However,Microkernel has some theoritical advantages over the monolithic kernel.They are as follows,
1.The microkernel occupies less RAM,since system processes(as disscussed above) that are not doing their functionalities are swapped out or destroyed.
2.The architecture of the microkernel forces the programmers to adopt a modularized approach
as different layers of the kernel are independant of each other.Moreover,the different layers interact with each other through clear well defined software interfaces.
3.Moreover, an existing microkernel operating system can be fairly easily ported to other architectures, since all hardware dependent components are generally encapsulated in the microkernel code.
Modules,the linux way
Modules are a kernel feature that effectively achieves many of the theoretical advantages of microkernels without introducing performance penalties. A module is an object file whose code can be linked to (and unlinked from) the kernel at runtime. The object code usually consists of a set of functions that implements a filesystem, a device driver, or other features at the kernel's upper layer. The module, unlike the external layers of microkernel operating systems, does not run as a specific process. Instead, it is executed in Kernel Mode on behalf of the current process, like any other statically linked kernel function.
Advantages provided by a monolithic kernel with modules
1.Less main memory usage
A module is linked to the kernel when its functionality is needed and unlinked when its no longer used.This mechanism is done automatically by the kernel and is transparent to the user.
2.Modularized approach
Modules force the programmers to intoduce well defined software interfaces for interaction.
3.Platform independence
A module does not depend on a fixed hardware platform.A module like device driver is infact specfic to the device but not to the hardware platform(x86,sparc etc..,)
4.Faster
Since the module is linked in to the kernel,it is faster like the monolithic kernel as there is no message passing as in microkernel.Infact there is small time we lose for linking and unlinking of the modules which is less than that of the time required for message passing in microkernels.
II.Linux Filesystem
Files are a basic abstraction provided by the operating system along with processes(more about processes later).A file is an information container structured as a sequence of bytes.From the user's point of view, files are organized in a tree-structured name space starting from /(parent) which is called the root directory.
Different file types in linux
The beauty of linux lies in the fact that it almost treats everything as files including devices. There are the following types of files
1. Regular files
2. Directory files
3. Symbolic links
4. Device files(character,block).
5. Pipes
6. Sockets
The first three types are constituents of the linux filesystem.Device files are related to I/O devices and device drivers integrated into the kernel.Pipes and sockets are special files used for interprocess communication.
Inode
All information needed by the filesystem to handle a file in included in a data structure called the inode.Each file has its own inode which the filesystem uses to identify the file.The following information is kept in the inode
1.File type(as discussed above)
2.Number of hard links associated with the file(see next section)
3.File length in bytes
4.Inode number that identifies the file within the filesystem
5.User ID of the file owner(discussed below)
5.Group ID of the file(discussed below)
6.The last modify time
7.Access rights and file mode (discussed below)
Hard links and symbolic links
The same file may have several links included in the same directory or in different ones, thus several filenames.
Hardlink
A hardlink is just a different filename but points to the same inode on the disc.So the file information of the both the file and the hard link will coincide as they point to the same inode.The unix command used to create a hard link is
$ln f1 f2
f2 is the hard link for file f1
Limitations of hard link
1.Hard links cannot exist to directories as it might transform the tree structure in to a graph with cycles thus making ti impossible to locate a file according to its name.
2.Hard links can be created only for files in the same filesystem as inode is the same.This is a serious limitation as Linux supports variuos other filesystems.
Softlink
Symbolic links are short files that contain an arbitrary pathname of another file. The pathname may refer to any file located in any filesystem,it may even refer to a non exixtent file or a file in another filesystem.Thus symbolic links are short files than contain the pathname of the file that is linked to.So a symbolic link will have a separate inode for itself.The unix command to create a symbolic link is
$ln -s f1 f2
f2 is a symbolic link to f1.The linux filesystem will create a sym link f2 and will write in to it the pathname for f1.In this way f2 can refer to f1.
Users and Groups
A multiuser system is a computer that is able to concurrently and independently execute several applications belonging to two or more users. "Concurrently" means that applications can be active at the same time and contend for the various resources such as CPU, memory, hard disks, and so on. "Independently" means that each application can perform its task with no concern for what the applications of the other users are doing.
In a multiuser system, each user has a private space on the machine: typically, he owns some quota of the disk space to store files, receives private mail messages, and so on. The operating system must ensure that the private portion of a user space is visible only to its owner. In particular, it must ensure that no user can exploit a system application for the purpose of
of violating the private space of the another user.
All users are identified by a unique number called the User ID , or UID. Usually only a restricted number of persons are allowed to make use of a computer system. When one of these users starts a working session, the operating system asks for a login name and a password.If the user does not input a valid pair, the system denies access. Since the password the assumed to be private the users privacy is maintained.In order to selectively share material with other users, each user is a member of one or more groups, which are identified by a unique number called a Group ID,or GID. Each file is associated with a UID and GID.
Access rights and mode
The users of a file fall in to one of this three classes
1.The owner of the file
2.The users who belong to the same groups as that of the owner
3.All other users(others) in the system
There are three types of access rights for each of these classes namely
Read,write and execute.
Thus the set of access rights associated with a file in linux consists of nine(3(for diff classes of users) * 3(for different access rights)) different flags.There are three additional flags which define the file mode which have a meaning when applied to executable files.They are
1.SUID flag
If the executable file has the SUID flag set, the process gets the UID of the file owner.
2.SGID
If the executable file has the SUID flag set, the process gets the GID of the file group.
The suid and sgid programs are important programs to be protected in a secure system as they change the id's during execution.So an intruder might use these programs for executing something malicious on behalf of the user who is suid or sgid.
3.sticky
An executable file with the sticky flag set corresponds to a request to the kernel to keep the program in memory after its execution terminates.These flag is set when many processes share the same program for example vi might be used by many processes.So vi can have its sticky bit set.This flag has become obsolete as other approaches like copy-on-write are used now for sharing code pages between processes.
chmod is the unix command used to allow the user to set access and mode flags for a file.
Example
$chmod 4777 f1
4777 in binary is 100111111111.So there are 12 bits corresponding to User classes,access and mode permissions as below.
100---will set the suid flag for f1(mode of the file)
111---will give read,write,exec access to owner of f1
111---will give read,write,exec access to other users of the group which the user belongs to.
111---will give read,write,exec access to other remaining users in the system.
Virtual File System technology
Linux follows a object oriented Virtual File System technology inspired from SVR4 and solaris.There linux supports most of the filesystems like DOS,FAT,ext3,resierfs,JFS etc..,Also porting a file system to Linux is very easy task because of the VFS technology that linux follows.
III.Processes in Linux
Process is another fundamental abstraction(apart from File) provided by the OS.Having seen a overview of the filesystem in linux let us see how linux handles processes.
A process can be defined either as "an instance of a program in execution," or as the "execution context" of a running program. In traditional operating systems, a process executes a single sequence of instructions in an address space,the address space is the set of memory addresses that the process is allowed to reference.Operating systems like linux allow multiple execution flows,that is,multiple sequences of instructions executed in the same address space.
Multiuser systems must allow different processes to be active concurrently and thereby contend for tbe resources,mainly the CPU.Such systems are said to be multitasking systems.The scheduler is the part of the kernel which decided which process will run on the CPU at a given instant of time.It is done in such a manner that every process feels that it is the only process running on the CPU.This concept is called virtualization of the processor.Another virtualisation that is provided by linux(or any OS) to processes is the virtual memory where in a process feels that it has the entire memory on system available to it.Processes of a multiuser system must be preemptive ie., the scheduler of the kernel will decide how long each process can hold the CPU.Thereby if a higher priority process comes in to execution the scheduler will preempt the lower priority running process.
Linux is a multiprocessing system with preemptive processes.
Process management in Linux
The fork( ) and exit( ) system calls are used respectively to create a new process and to terminate it.Linux maintains a clear distinction between the process and the program by using exec( )-like system call to load a new program.After exec has been done the process resumes execution with a brand new address space containing the loaded program.
Process Creation
Processes in Linux follow a parent child relationship.The Process which invokes the fork is the parent and the process that is created is the child.The init process(created by the init.c of the kernel) is the root parent of all the other processes in linux.The task_struct is the data structure in the kernel that defines the process.Parents and children can easily find each other as the data structure contains information about the relationship.Linux implements fork using the copy-on-write approach which defers address space duplication of parent to the child on fork.The address space is copied only when a write is being made in to the address space.So till a write happens the parent and the child share only the Page tables and not the address space.The copy-on-write has the following advantage
1.Most instances of fork are followed by an exec to a program as the child does some other functionailty when compared to the program.Thereby it is a waste(an overhead) to copy the address space of the parent to the child and then again immediately overwrite the address space.So this overhead is reduced by the copy-on-write approach.
Process Termination
The exit system call is used to terminate a process.The kernel handles this system call by releasing the resources owned by the process and sending the parent process a SIGCHLD signal, which is ignored by default.
Zombie processes
The parent enquires about the termination of the child process by the wait( ) system call which allows a process to wait until one of its children terminates; it returns the process ID (PID) of the terminated child.A special zombie process state is introduced to represent terminated processes on which the parent has not issued a wait system call.The process descriptor of the child is released after the wait is executed by the parent and the child process goes to the stopped state.Now the question arises if the parent does not issue a wait call and if it terminates what happens to the child in Zombie state.There will be many zombies which will occupy useful memory.The solution lies in init process which takes over as the parent of child process whose parents have terminated.It routinely issues wait calls thereby getting rid of the zombies.
IV.The process/Kernel model
Having known about the kernel architecture and the basic abstractions(file,process) let us now see how the linux kernel is modelled.On multiuser/multitasking systems the operating system must hide all low level details concerning the physical organization of the computer from applications run by user.So when a user application wants to access a hardware,it request the kernel which evaluates the request and if it chooses to grant access,it interacts with the hardware on behalf of the process.This thereby enhances the security on multiuser systems which prevent user applications from damaging the system hardware resources.Probably,this is the reason why DOS does not require such a model as it is single user system which allows the user to do anything with the systems hardware.
Well how does linux implement the above mentioned feature.All modern operating systems,implement the above mentioned feature with the help of hardware specific features which forbids the user programs to interact directly with the hardware.For example,the x86 CPU provides four rings of execution from ring 0 to ring 3 in the order of descending privileges.Linux uses the two rings namely ring 0 and ring 3 for implementing the feature.User mode applications run in ring 3 of x86 and kernel runs in ring 0 of x86.Therefore these rings correspond to the User mode and kernel mode concept of the linux operating system.
Note:Intel introduced protected mode(ring levels) starting from 80386.So Linux was developed for 80386 and above(commonly referred as i386/i686 architectures).
When a program is executed in User Mode, it cannot directly access the kernel data structures or the kernel programs. When an application executes in Kernel Mode, however, these restrictions no longer apply. Each CPU model provides special instructions to switch from User Mode to Kernel Mode and vice versa. A program executes most of the time in User Mode and switches to Kernel Mode only when requesting a service provided by the kernel. When the kernel has satisfied the program's request, it puts the program back in User Mode.
The kernel is a process manager and not a process by itself.The creation,deletion and handling of processes are done by a group of routines in the kernel.The process/kernel model in linux allows a process to request a kernel service through system calls.System calls thereby take the process from user mode to kernel mode,does the necessary request and puts the process back in the user mode.
A switch to Kernel mode from user mode will happen by any one of these methods
1.Through system call by a process as discussed above
2.The CPU exceutes an exception.The exception has to be handled by the kernel on behalf of the process that caused the exception.For example,the kernel must handle the page fault exception.
3.A device issues an interrupt to the CPU to notify the CPU an event.In this case the kernel executes the corresponding interrupt handler for the device.
Linux also has some privileged kernel level processes.They are called kernel threads.Linux uses kernel threads in a limited way for certain functionalites.They execute in the kernel thread.keventd is an example of a kernel thread.
V.Kernel Synchronisation
On multiuser/multitasking systems many processes must be handled by the kernel at a single instant of time as several processes may be executing in the kernel at the same time.For example ,a process executing on a CPU in a uniprocessor system might be waiting on some I/0.During this time the process in kernel mode is interleaved and another process is executed in the kernel.When the I/O interrupt is finished the process waiting for I/O is executed again.So the Linux kernel must be reentrant,ie..,multiple processes must be handled by the kernel maintaining the global data structures they use in a consistent state.
Before proceeding further,we will see the definition of a kernel control path.A kernel control path is a sequence of instructions executed in the kernel mode on behalf of a process or on behalf of an interupt.
How can Kernel reentrancy be achieved?
The following are the methods to achieve kernel reentrancy
1.Reentrant functions
2.Atomic operations
3.Non Premptive kernel
4.Interrupt disabling
5.Locking mechanisms(semaphores and spinlocks)
Reentrant functions
Reentrant functions are those functions which operate only on local variable and not on global data structures.But the kernel cannot only be limited to reentrant functions.Also the kernel has a fixed stack which is small,so local variable must be less.
Before looking at other mechanisms of achieving reentarncy let us see what a race condition is and what is a critical region.
Assume that there is a global data structure(a resource) R1.If R1 is one the resource is free.Now a kernel control path KCP1 reads the value of R1 which is 1 i.e.., the resource is free.Now if KCP1 is interleaved from the kernel and if KCP2 reads the value of R1 which is still 1.It will take the resource and decrement the value to 0.Now if KCP1 resumes execution it still sees that the resource is free and decrements the value of R1 to -1,thereby taking the resource.So both the KCP's are using the resources leading to dangerous effects.This is a race condition.
Atomic operations
It is always safe to access a global variable with a single atomic uninteruptible instruction.For example in the previuos example if the two kernel paths have read the data and decremented the value of R1 in a singl operation there would have been no race condition.
But its always not possible to access data structures in a single atomic operation.Any section of code that should be finished by a process befored another process is scheduled is called the critical region.Further mechanisms we will see how to protect critical regions.
Non Premptive kernel
A simple solution to synchronisation problems is to make the kernel non preemptive ie., when a process is in kernel mode it cannot be interleaved by any other process until it voluntarily relinquishes the CPU(in which case it makes sure that the Data structures are in a consistent state).Therefore in a non preemptive kernel all the global data structures except those that are used by interupts and exceptions are safe(as interleaving of a process in kernel mode happens when a interuppt or exception occurs).Non premptability is ineffective in Multiprocessor systems as two kernel control paths executing in different CPU's can access the same data structure.The linux kernel was non preemptable until 2.5 devt series and 2.6 stable series.Now the kernel is preemptible.Preemptible kernels are more suited for time critical real time processes.
Interrupt disabling
Another method to achieve synchronisation is to disable interuppts before entering a critical region and enabling it after the critical region.This is a simple solution but is not optimal as large critical region will have the Hardware interrupts freezed for a long time leading to a freeze.Also it is ineffective in multiprocessor systems as the data structure might be accessed by another process running in a different CPU.
Locking mechanisms
The locking mechanisms lock the corresponding global data structure in question thereby making sure that when the lock is acquired only a single process can access the data structure.They are effective both in Uniprocessor and Multiprocessor systems.The locking mechanisms used by the linux kernel are
1.Semaphores
2.Spin Locks
Semaphores
A semaphore is simply a counter associated with a data structure; the semaphore is checked by all kernel threads before they try to access the data structure.Each semaphore may be viewed as an object composed of:
a)An integer variable
b)A list of waiting processes
c)Two atomic methods: down() and up()
The down() method decrements the value of the semaphore. If the new value is less than 0, the method adds the running process to the semaphore list and then blocks (i.e., invokes the scheduler). The up() method increments the value of the semaphore and, if its new value is greater than or equal to 0, reactivates one or more processes in the semaphore list. Each data structure to be protected has its own semaphore, which is initialized to 1. When a kernel control path wishes to access the data structure, it executes the down() method on the proper semaphore. If the value of the new semaphore isn't negative, access to the data structure is granted. Otherwise, the process that is executing the kernel control path is added to the semaphore list and blocked. When another process executes the up() method on that semaphore, one of the processes in the semaphore list is allowed to proceed.
SpinLocks
In multiprocessor systems, semaphores are not always the best solution to the synchronization problems. Some kernel data structures should be protected from being concurrently accessed by kernel control paths that run on different CPUs. In this case, if the time required to update the data structure is short, a semaphore could be very inefficient. To check a semaphore, the kernel must insert a process in the semaphore list and then suspend it. Since both operations are relatively expensive, in the time it takes to complete them, the other kernel control path could have already released the semaphore. In these cases, multiprocessor operating systems make use of spin locks. A spin lock is very similar to a semaphore, but it has no process list: when a process finds the lock closed by another process, it "spins" around repeatedly, executing a tight instruction loop until the lock becomes open. Of course, spin locks are useless in a uniprocessor environment. When a kernel control path tries to access a locked data structure, it starts an endless loop. Therefore, the kernel control path that is updating the protected data structure would not have a chance to continue the execution and release the spin lock. The final result is that the system hangs.
Signals and interprocess communication
The linux kernel implements signals for communicating to the process an event.For example,SIGKILL is sent to the process if it receives a terminate signal.The linux kernel implements 32 different posix signals.User processes can communicate with each other with the help of SYS V IPCs like sahred memory,pipes,fifos,semaphores and message queues.
VI.Memory Management in Linux
Memory management is the most complex(as it is architecture dependant) and important activity in the kernel.Linux supports Virtual memory management.Linux uses paging to implement virtual memory concept.Linux does not use segmentation.Memory management will be described in detail in a later article.For now the advantages a virtual memory offers are
1.Several processes can be executed concurrently.
2.It is possible to run applications whose memory needs are larger than the available physical memory.
3.Processes can execute a program whose code is only partially loaded in memory.
4.Each process is allowed to access a subset of the available physical memory.
5.Processes can share a single memory image of a library or program
6.Programs can be relocatable, that is, they can be placed anywhere in physical memory.
7.Programmers can write machine-independent code, since they do not need to be concerned about physical memory organization.
RAM USAGE
The usage of memory is one very important thing that has to be taken care by the kernel.Linux clearly distiguishes between Memory that is dedicated to the kernel and the memory that can be used by the processes.The static kernel image is loaded from the 1st Megabyte of the RAM and is pinned(it is not swapped or paged out).The remaining part of the RAM is used for
1.Kernel dynamic structures
2.Memory for processes
3.Caches for disks etc., to get better performance.
How the memory is allocated for above mentioned three is very important and hence requires a separate article.In a few words, linux takes care of memory allocation problems like internal fragmentation,external fragmentation etc., by making use of buddy system algorithm and slab allocation mechanism.So Linux uses a Slab allocator on top of a buddy system algorithm.
Virtual Adddress space of a process
Every process in linux has a virtual address space(ranging from 0 to 4GB on a 32 bit intel CPU).
A address space of a process contains all the virtual memory addresses that the process can reference.The kernel usually stores a process virtual address space as a list of memory area descriptors(for example memory area descriptors to the code segment,stack segment,heap etc.,).Linux uses demand paging ie., the page is allocated after a page fault happens.
VII.Device drivers
Having discussed most of kernel subsystems namely filesystem,process,synchronisation,interrupts,syscalls,meory management lets see in a nutshell about device drivers.The kernel interacts with I/O devices with help of device drivers.Device drivers are included in the kernel and consist of data structures and functions that control one or more devices like hard disks,keyboard,mouse etc.,Each driver interacts with the remaining part of the kernel (even with other drivers) through a specific interface.There the device driver layer can be seen as the last layer in the kernel interacting with other layers through well defined interfaces.This approach helps programmers to write device specfic code in a separate module without knowing about the kernel source code as well as the internal architecture.
VIII.Linux implementation of threads
Finally,it is mandatory to discuss how linux supports multithreaded application programming as it does in a unique manner.In linux threads are also processes which share the address space of the processes.Linux implements threads as processes because the process creation time in linux is much faster compared to other OS'es.A thread is therefore a process which can scheduled independently of the main process and it shares the same address space.
SUMMARY
In summary a linux kernel is monolithic with modular support and consists of the following subsystems,
1.Filesystem
2.Process management
3.Memory management
4.Synchronisation
5.System calls
6.Device drivers
7.Interrupts and exceptions
8.Signals
The explanation and deciphering of the different kernel layers will be explained in future articles contirbuted by the various members of the lkg_india.I also promise two more articles which will be extension of this article namely
1.Linux kernel 2.6 features
2.Linux VS other Operating systems and the future of linux
A thread and A task
A thread is a point of control flow in a task. A task
exists to provide resources for the threads it contains. This split is made to provide
for parallelism and resource sharing.
A thread
* is a point of control flow in a task.
* has access to all of the elements of the containing task.
* executes (potentially) in parallel with other threads, even threads within the same task.
* has minimal state information for low overhead.
A task
* is a collection of system resources. These resources, with the exception of the address space, are referenced by ports. These resources may be shared with other tasks if rights to the ports are so distributed.
* provides a large, potentially sparse address space, referenced by virtual address.Portions of this space may be shared through inheritance or external memory management.
* contains some number of threads.
exists to provide resources for the threads it contains. This split is made to provide
for parallelism and resource sharing.
A thread
* is a point of control flow in a task.
* has access to all of the elements of the containing task.
* executes (potentially) in parallel with other threads, even threads within the same task.
* has minimal state information for low overhead.
A task
* is a collection of system resources. These resources, with the exception of the address space, are referenced by ports. These resources may be shared with other tasks if rights to the ports are so distributed.
* provides a large, potentially sparse address space, referenced by virtual address.Portions of this space may be shared through inheritance or external memory management.
* contains some number of threads.
Packet Processing In iptables ..
Packet Processing In iptables ..
All packets inspected by iptables pass through a sequence of built-in tables (queues) for processing. Each of these queues is dedicated to a particular type of packet activity and is controlled by an associated packet transformation/filtering chain.
There are three tables in total. The first is the mangle table which is responsible for the alteration of quality of service bits in the TCP header. This is hardly used in a home or SOHO environment.
The second table is the filter queue which is responsible for packet filtering. It has three built-in chains in which you can place your firewall policy rules. These are the:
* Forward chain: Filters packets to servers protected by the firewall.
* Input chain: Filters packets destined for the firewall.
* Output chain: Filters packets originating from the firewall.
The third table is the nat queue which is responsible for network address translation. It has two built-in chains; these are:
* Pre-routing chain: NATs packets when the destination address of the packet needs to be changed.
* Post-routing chain: NATs packets when the source address of the packet needs to be changed
All packets inspected by iptables pass through a sequence of built-in tables (queues) for processing. Each of these queues is dedicated to a particular type of packet activity and is controlled by an associated packet transformation/filtering chain.
There are three tables in total. The first is the mangle table which is responsible for the alteration of quality of service bits in the TCP header. This is hardly used in a home or SOHO environment.
The second table is the filter queue which is responsible for packet filtering. It has three built-in chains in which you can place your firewall policy rules. These are the:
* Forward chain: Filters packets to servers protected by the firewall.
* Input chain: Filters packets destined for the firewall.
* Output chain: Filters packets originating from the firewall.
The third table is the nat queue which is responsible for network address translation. It has two built-in chains; these are:
* Pre-routing chain: NATs packets when the destination address of the packet needs to be changed.
* Post-routing chain: NATs packets when the source address of the packet needs to be changed
What is iptables?
What is iptables?
Originally, the most popular firewall/NAT package running on Linux was ipchains, but it had a number of shortcomings. To rectify this, the Netfilter organization decided to create a new product called iptables, giving it such improvements as:
* Better integration with the Linux kernel with the capability of loading iptables-specific kernel modules designed for improved speed and reliability.
* Stateful packet inspection. This means that the firewall keeps track of each connection passing through it and in certain cases will view the contents of data flows in an attempt to anticipate the next action of certain protocols. This is an important feature in the support of active FTP and DNS, as well as many other network services.
* Filtering packets based on a MAC address and the values of the flags in the TCP header. This is helpful in preventing attacks using malformed packets and in restricting access from locally attached servers to other networks in spite of their IP addresses.
* System logging that provides the option of adjusting the level of detail of the reporting.
* Better network address translation.
* Support for transparent integration with such Web proxy programs as Squid.
* A rate limiting feature that helps iptables block some types of denial of service (DoS) attacks.
Considered a faster and more secure alternative to ipchains, iptables has become the default firewall package installed under RedHat and Fedora Linux.
How To Start iptables?
You can start, stop, and restart iptables after booting by using the commands:
[root@bigboy tmp]# service iptables start
[root@bigboy tmp]# service iptables stop
[root@bigboy tmp]# service iptables restart
To get iptables configured to start at boot, use the chkconfig command:.
[root@bigboy tmp]# chkconfig iptables on
Determining The Status of iptables
You can determine whether iptables is running or not via the service iptables status command. Fedora Core will give a simple status message. For example
[root@bigboy tmp]# service iptables status
Firewall is stopped.
[root@bigboy tmp]#
Originally, the most popular firewall/NAT package running on Linux was ipchains, but it had a number of shortcomings. To rectify this, the Netfilter organization decided to create a new product called iptables, giving it such improvements as:
* Better integration with the Linux kernel with the capability of loading iptables-specific kernel modules designed for improved speed and reliability.
* Stateful packet inspection. This means that the firewall keeps track of each connection passing through it and in certain cases will view the contents of data flows in an attempt to anticipate the next action of certain protocols. This is an important feature in the support of active FTP and DNS, as well as many other network services.
* Filtering packets based on a MAC address and the values of the flags in the TCP header. This is helpful in preventing attacks using malformed packets and in restricting access from locally attached servers to other networks in spite of their IP addresses.
* System logging that provides the option of adjusting the level of detail of the reporting.
* Better network address translation.
* Support for transparent integration with such Web proxy programs as Squid.
* A rate limiting feature that helps iptables block some types of denial of service (DoS) attacks.
Considered a faster and more secure alternative to ipchains, iptables has become the default firewall package installed under RedHat and Fedora Linux.
How To Start iptables?
You can start, stop, and restart iptables after booting by using the commands:
[root@bigboy tmp]# service iptables start
[root@bigboy tmp]# service iptables stop
[root@bigboy tmp]# service iptables restart
To get iptables configured to start at boot, use the chkconfig command:.
[root@bigboy tmp]# chkconfig iptables on
Determining The Status of iptables
You can determine whether iptables is running or not via the service iptables status command. Fedora Core will give a simple status message. For example
[root@bigboy tmp]# service iptables status
Firewall is stopped.
[root@bigboy tmp]#
Passwords and Permisssions
Ordinary users have two ways of protecting the data in their accounts:
1. choose a secure password
2. set permissions
Changing your password:
- One of the easiest method of breaking into a system is to crack a weak password. To create a secure password:
- The password should be at least 6 characters long.
- You should not use names or phrases that are easily obtained; do NOT use your name; do NOT use your dog's name; do NOT use your spouse's name; do NOT use your licence plate; do NOT use your birthdate ...
- Include both CAPITAL and lowercase letters.
- Include special characters ( ! @ # $ % ... )
- Include digits
- One way to create a secure password is suggested in the passwd man page.
- choose 2 small words ( eg: why not )
- mix in some capitalization ( eg: whY Not )
- join them with a special character ( eg: whY%Not )
- The command to change your password is: passwd
Setting permissions:
Access to files and directories is controlled by a permissions at both the file and directory levels.
- permissions can be any combination of read, write, execute for the owner, group and world.
- for a file:
- without read permission, a user cannot view the contents of a file
- without write permission, a user cannot modify the contents of the file
- without execute permission, a user cannot execute the file.
- for a directory:
- without read permission, a user cannot get a directory listing
- without write permission, a user cannot create new files
- without execute permission, a user cannot cd to the directory, list the directory contents or save a file in the directory.
- chmod - change permissions.
- Read, write and execute permissions are set for three groups: the owner, the group and everyone else.
- chmod 543 myfile would set access rights as follows:
owner: 5 = 101 binary = read, not write, execute
group: 4 = 100 binary = read, not write, not execute
others: 3 = 011 binary = not read, write, execute
- chmod - version 2
- permissions can also be set using a text representation
u - user or owner
g - group
o - others
r - read permission
w - write permission
x - execute permission - chmod u+w file1
adds write permission for the user - chmod +w file1
adds write permission for the user, group and others - chmod go-x file1
deletes execute permission for the group and others - chmod u=r file1
changes the permissions for the user to be just read permission (group and other permissions are not changed)
- permissions can also be set using a text representation
Exercises:
- Try to change your password to cat. What error message did you get?
- Try to change your password to blackcat. What error message did you get?
- Think up a password and change your password.
- Try to the password for another user. For example, enter the command:
passwd floopy
What error message did you get?
- Can you view the contents of the directory /sbin?
- What are the permissions for the directory /sbin?
- Change the permissions on "readme" in your own home so that you have read/write access, the group has read access and others have no access.
- Change permissions on your home directory so that you have read/write/execute permissions, the group has read/execute permissions, and everyone else has no access.
- Make sure that you are in your own home directory. Create a subdirectory called ddd and copy readme to ddd/fff (a file called fff in the ddd subdirectory).
- what are the permissions on ddd and fff? ____________________
- change the permissions on fff to only rwx for the owner.
- Try the following exercise to see some of the operations that you can and cannot do when you have only read permission on a directory.
- change the permissions on ddd only r for the owner (no permissions for the group and the world)
- can you get a directory listing for ddd? _____
- can you cd to ddd? _____
- can you view the contents of fff with the command: cat ddd/fff ? ______
- can you delete fff with the command: rm ddd/fff ?______
- Try the following to see what you can do when you have read and execute permission for a directory.
- change the permissions on ddd only rx for the owner (no permissions for the group and the world)
- can you get a directory listing for ddd? _____
- can you cd to ddd? _____
- can you view the contents of fff with the command: cat ddd/fff ? ______
- can you delete fff with the command: rm ddd/fff ? ______
- Try the following to see what you can do when you have write and execute permissions for a directory.
- change the permissions on ddd only wx for the owner (no permissions for the group and the world)
- can you get a directory listing for ddd? _____
- can you cd to ddd? _____
- can you view the contents of fff with the command: cat ddd/fff ? ______
- can you delete fff with the command: rm ddd/fff ? ______
- can you execute the command: cd ; cp readme ddd/fff _____
- Try the following to see what you can do when you have only execute permissions for a directory.
- change the permissions on ddd only x for the owner (no permissions for the group and the world)
- can you get a directory listing for ddd? _____
- can you cd to ddd? _____
- can you view the contents of fff with the command: cat ddd/fff ? ______
- can you delete with the command: rm ddd/fff
- can you execute the command: cd ; cp readme ddd/fff _____
Questions and Answers:
- The directory entries for the /etc directory and the file /etc/passwd are:
-rwxr-xr-x 18 root root 1024 May 20 11:58 /etc
-rw-r--r-- 1 root root 658 May 20 11:58 /etc/passwd
Can you modify this file (assuming you are not root)?
Answer: No.
- Can you copy /etc/passwd to your own home directory assuming that you have write and execute permissions for your own home directory?
Answer: Yes. Everyone has read permission for this file and can make a copy.
- If you are not floopy, can you copy /etc/passwd (permissions rw-r--r--) to the directory /home/floopy? The permissions on /home/floopy are rwxr-xr-x.
Answer: No. /home/floopy is owned by floopy and the permissions are rwxr-xr-x meaning that everyone can read the contents of the directory but only floopy can store files in this directory.
- File1 has permissions: r--r--r--
You enter the command: chmod ug+w file1
What are the new permissions?
Answer: rw-rw-r--
- What command will change the permissions on dir1 so that only the owner has read/execute access?
Answer: chmod 500 dir1
- Can you cd to dir1 given the permissions are drw-------?
Answer: No. Without execute access, you cannot cd to a directory or access any of the files in the directory.
- What command will change the permissions on dir1 so that you have write/execute permissions only?
Answer: chmod 300 dir1
- Can you copy readme (permissions r--r--r--) to dir1 (permissions d-wx------ ) if you own dir1?
Answer: Yes
- Can you get a directory listing for dir1 permissions (d-wx-wx-wx)?
Answer: No. If you do not have read permission for a directory, then essentially you have blind access; you can write files in the dir1 but you cannot get a directory listing.
Source:http://floppix.ccai.com/protect.html
Important linux commands used in real time scenarios..
This is a linux command line reference for common operations.
Examples marked with • are valid/safe to paste without modification into a terminal, so
you may want to keep a terminal window open while reading this so you can cut & paste.
All these commands have been tested both on Fedora and Ubuntu.
Examples marked with • are valid/safe to paste without modification into a terminal, so
you may want to keep a terminal window open while reading this so you can cut & paste.
All these commands have been tested both on Fedora and Ubuntu.
| Command | Description | |
| • | apropos whatis | Show commands pertinent to string. See also threadsafe |
| • | man -t man | ps2pdf - > man.pdf | make a pdf of a manual page |
| which command | Show full path name of command | |
| time command | See how long a command takes | |
| • | time cat | Start stopwatch. Ctrl-d to stop. See also sw |
| • | nice info | Run a low priority command (The "info" reader in this case) |
| • | renice 19 -p $$ | Make shell (script) low priority. Use for non interactive tasks |
| dir navigation | ||
| • | cd - | Go to previous directory |
| • | cd | Go to $HOME directory |
| (cd dir && command) | Go to dir, execute command and return to current dir | |
| • | pushd . | Put current dir on stack so you can popd back to it |
| file searching | ||
| • | alias l='ls -l --color=auto' | quick dir listing |
| • | ls -lrt | List files by date. See also newest and find_mm_yyyy |
| • | ls /usr/bin | pr -T9 -W$COLUMNS | Print in 9 columns to width of terminal |
| find -name '*.[ch]' | xargs grep -E 'expr' | Search 'expr' in this dir and below. See also findrepo | |
| find -type f -print0 | xargs -r0 grep -F 'example' | Search all regular files for 'example' in this dir and below | |
| find -maxdepth 1 -type f | xargs grep -F 'example' | Search all regular files for 'example' in this dir | |
| find -maxdepth 1 -type d | while read dir; do echo $dir; echo cmd2; done | Process each item with multiple commands (in while loop) | |
| • | find -type f ! -perm -444 | Find files not readable by all (useful for web site) |
| • | find -type d ! -perm -111 | Find dirs not accessible by all (useful for web site) |
| • | locate -r 'file[^/]*\.txt' | Search cached index for names. This re is like glob *file*.txt |
| • | look reference | Quickly search (sorted) dictionary for prefix |
| • | grep --color reference /usr/share/dict/words | Highlight occurances of regular expression in dictionary |
| archives and compression | ||
| gpg -c file | Encrypt file | |
| gpg file.gpg | Decrypt file | |
| tar -c dir/ | bzip2 > dir.tar.bz2 | Make compressed archive of dir/ | |
| bzip2 -dc dir.tar.bz2 | tar -x | Extract archive (use gzip instead of bzip2 for tar.gz files) | |
| tar -c dir/ | gzip | gpg -c | ssh user@remote 'dd of=dir.tar.gz.gpg' | Make encrypted archive of dir/ on remote machine | |
| find dir/ -name '*.txt' | tar -c --files-from=- | bzip2 > dir_txt.tar.bz2 | Make archive of subset of dir/ and below | |
| find dir/ -name '*.txt' | xargs cp -a --target-directory=dir_txt/ --parents | Make copy of subset of dir/ and below | |
| ( tar -c /dir/to/copy ) | ( cd /where/to/ && tar -x -p ) | Copy (with permissions) copy/ dir to /where/to/ dir | |
| ( cd /dir/to/copy && tar -c . ) | ( cd /where/to/ && tar -x -p ) | Copy (with permissions) contents of copy/ dir to /where/to/ | |
| ( tar -c /dir/to/copy ) | ssh -C user@remote 'cd /where/to/ && tar -x -p' | Copy (with permissions) copy/ dir to remote:/where/to/ dir | |
| dd bs=1M if=/dev/sda | gzip | ssh user@remote 'dd of=sda.gz' | Backup harddisk to remote machine | |
| rsync (Network efficient file copier: Use the --dry-run option for testing) | ||
| rsync -P rsync://rsync.server.com/path/to/file file | Only get diffs. Do multiple times for troublesome downloads | |
| rsync --bwlimit=1000 fromfile tofile | Locally copy with rate limit. It's like nice for I/O | |
| rsync -az -e ssh --delete ~/public_html/ remote.com:'~/public_html' | Mirror web site (using compression and encryption) | |
| rsync -auz -e ssh remote:/dir/ . && rsync -auz -e ssh . remote:/dir/ | Synchronize current directory with remote one | |
| ssh (Secure SHell) | ||
| ssh $USER@$HOST command | Run command on $HOST as $USER (default command=shell) | |
| • | ssh -f -Y $USER@$HOSTNAME xeyes | Run GUI command on $HOSTNAME as $USER |
| scp -p -r $USER@$HOST: file dir/ | Copy with permissions to $USER's home directory on $HOST | |
| ssh -g -L 8080:localhost:80 root@$HOST | Forward connections to $HOSTNAME:8080 out to $HOST:80 | |
| ssh -R 1434:imap:143 root@$HOST | Forward connections from $HOST:1434 in to imap:143 | |
| wget (multi purpose download tool) | ||
| • | (cd dir/ && wget -nd -pHEKk http://www.pixelbeat.org/cmdline.html) | Store local browsable version of a page to the current dir |
| wget -c http://www.example.com/large.file | Continue downloading a partially downloaded file | |
| wget -r -nd -np -l1 -A '*.jpg' http://www.example.com/dir/ | Download a set of files to the current directory | |
| wget ftp://remote/file[1-9].iso/ | FTP supports globbing directly | |
| • | wget -q -O- http://www.pixelbeat.org/timeline.html | grep 'a href' | head | Process output directly |
| echo 'wget url' | at 01:00 | Download url at 1AM to current dir | |
| wget --limit-rate=20k url | Do a low priority download (limit to 20KB/s in this case) | |
| wget -nv --spider --force-html -i bookmarks.html | Check links in a file | |
| wget --mirror http://www.example.com/ | Efficiently update a local copy of a site (handy from cron) | |
| networking (Note ifconfig, route, mii-tool, nslookup commands are obsolete) | ||
| ethtool eth0 | Show status of ethernet interface eth0 | |
| ethtool --change eth0 autoneg off speed 100 duplex full | Manually set ethernet interface speed | |
| iwconfig eth1 | Show status of wireless interface eth1 | |
| iwconfig eth1 rate 1Mb/s fixed | Manually set wireless interface speed | |
| • | iwlist scan | List wireless networks in range |
| • | ip link show | List network interfaces |
| ip link set dev eth0 name wan | Rename interface eth0 to wan | |
| ip link set dev eth0 up | Bring interface eth0 up (or down) | |
| • | ip addr show | List addresses for interfaces |
| ip addr add 1.2.3.4/24 brd + dev eth0 | Add (or del) ip and mask (255.255.255.0) | |
| • | ip route show | List routing table |
| ip route add default via 1.2.3.254 | Set default gateway to 1.2.3.254 | |
| • | tc qdisc add dev lo root handle 1:0 netem delay 20msec | Add 20ms latency to loopback device (for testing) |
| • | tc qdisc del dev lo root | Remove latency added above |
| • | host pixelbeat.org | Lookup DNS ip address for name or vice versa |
| • | hostname -i | Lookup local ip address (equivalent to host `hostname`) |
| • | whois pixelbeat.org | Lookup whois info for hostname or ip address |
| • | netstat -tupl | List internet services on a system |
| • | netstat -tup | List active connections to/from system |
| windows networking (Note samba is the package that provides all this windows specific networking support) | ||
| • | smbtree | Find windows machines. See also findsmb |
| nmblookup -A 1.2.3.4 | Find the windows (netbios) name associated with ip address | |
| smbclient -L windows_box | List shares on windows machine or samba server | |
| mount -t smbfs -o fmask=666,guest //windows_box/share /mnt/share | Mount a windows share | |
| echo 'message' | smbclient -M windows_box | Send popup to windows machine (off by default in XP sp2) | |
| text manipulation (Note sed uses stdin and stdout. Newer versions support inplace editing with the -i option) | ||
| sed 's/string1/string2/g' | Replace string1 with string2 | |
| sed 's/\(.*\)1/\12/g' | Modify anystring1 to anystring2 | |
| sed '/ *#/d; /^ *$/d' | Remove comments and blank lines | |
| sed ':a; /\\$/N; s/\\\n//; ta' | Concatenate lines with trailing \ | |
| sed 's/[ \t]*$//' | Remove trailing spaces from lines | |
| sed 's/\([`"$\]\)/\\\1/g' | Escape shell metacharacters active within double quotes | |
| • | seq 10 | sed "s/^/ /; s/ *\(.\{7,\}\)/\1/" | Right align numbers |
| sed -n '1000p;1000q' | Print 1000th line | |
| sed -n '10,20p;20q' | Print lines 10 to 20 | |
| sed -n 's/.* | ||