*comprehensive updated material - approx 40% of material updated
*covers the latest version of Linux 2.4
From the Second Edition:
"If you intend to write kernel code or a kernel module, or just want to know how the kernel of a Linux system works, this book is an excellent source of information... I highly recommend this book for anyone who is serious about writing code or who wants to know what is in the Linux kernel."
-- Phil Hughes, Linux Journal
Since the introduction of Linux version 1.2 in March 1995, the reliability and flexibility of this free operating system has attracted a vast community of programmers from all over the world. Now at version 2.4, Linux is being successfully employed in commercial software development by internet providers and in research and teaching.
As the acknowledged leading reference on the subject, this third edition of Linux Kernel Programming is for anyone who requires a deeper understanding of the operating system. It explains the technology internals of the successful Linux OS, including:
This third edition of Linux Kernel Programming:
The accompanying CD-ROM contains the Linux Kernel version 2.4.4, plus sources from other programs and documents from the Linux Documentation Project.
Preface to the 3rd Edition.
Preface to the 1st Edition.
Torvalds' Preface to the 1st Edition.
1. linux — the Operating System.
Where is Everything?
Additional Configuration Facilities.
Important Data Structures.
The Task Structure.
The Process Table.
Files and Inodes.
Dynamic Memory Management.
Queues and Semaphores.
System Time and Timers.
Booting the System.
Implementation of System Calls.
How Do System Calls Actually Work?
Examples of Simple System Calls.
Examples of More Complex System Calls.
The Architecture-Independent Memory Model.
Pages of Memory.
Virtual Address Space.
Converting the Linear Address.
The Page Table.
The Virtual Address Space of a Process.
The User Segment.
Virtual Memory Areas.
The System Call BRK.
The Kernel Segment.
Memory Allocation in the Kernel Segment During Booting.
Dynamic Memory Management in the Kernel Segment.
Block Device Caching.
Bdflush and Kupdate.
List Structures for the Buffer Cache.
Using the Buffer Cache.
Paging Under Linux.
Memory Management and the Memory Cache.
Reserving a Page of Memory.
Optimization of Memory Page Management Via Kernel Threads.
Page Errors and Reloading a Page.
Synchronization in the Kernel.
Communication via Files.
Locking Entire Files.
Locking File Areas.
Debugging Using Ptrace.
System V IPC.
Access Rights, Numbers, and Keys.
The IPCS and IPCRM Commands.
IPC with Sockets.
A Simple Example.
The Implementation of Unix Domain Sockets.
The Representation of File Systems in the Kernel.
The Directory Cache.
The File Structure.
Opening a File.
The Ext2 File System.
The Structure of the Ext2 File System.
Directories in the Ext2 File System.
Block Allocation in the Ext2 File System.
Extensions of the Ext2 File System.
The Proc File System.
Structures of the Proc File System.
Implementation of the Proc File System.
Character and Block Devices.
The PCI bus.
The Dinosaur — the ISA Bus.
Polling, Interrupts, and Waiting Queues.
Bottom Halves — The Lower Interrupt Halves.
Implementing a Driver.
Example of a PC Loudspeaker Driver.
A Simple Driver.
The Setup Function.
Open and Release.
Read and Write.
Dynamic and Static Drivers.
Introduction and Overview.
The Layer Model of the Network Implementation.
Getting the Data from A to B.
The Socket Structure.
The sk_buff Structure — Buffer Management in the Network.
The INET Socket — A Special Part of the Socket.
Protocol Operations in the Proto Structure.
The General Structure of a Socket Address.
Network Devices under Linux.
SLIP and PLIP.
The Loopback Device.
The Dummy Device.
An Example Device.
What are Modules?
Implementation in the Kernel.
Signatures of Symbols.
The Meaning of Object Sections for Modules and Kernels.
Parameter Transfer and Examples.
What Can be Implemented as a Module?
The Kernel Daemon.
Simple Data Swapping between Modules.
An Example Module.
Changes are the Beginning of the End.
The Best Debugger — printk().
Debugging with gdb.
The Intel Multiprocessor Specification.
Problems with Multiprocessor Systems.
Changes to the Kernel.
The Atomic Data Type.
Accessing the Atomic Data Type.
Changing and Testing Atomic Variables.
Read-Write Spin Locks.
The File System.
All That Remains.
Free — Overview of the System's Memory.
PS — Output of Process Statistics.
Top — The CPU Charts.
Init — Primus Inter Pares.
Shutdown — Shutting Down The System.
strace — Monitoring a Process.
Configuring the Network Interface.
Traceroute — Ariadne's Paths in the Internet.
Configuring a Serial Interface.
Configuring a Parallel Interface.
Building a Directory Tree.
The /PROC/ Directory.
The NET/ Directory.
The SELF/ Directory.
The SYS/ Directory.
Carrying Out the Booting Process.
LILO — The Linux Loader.
In a competition at this year's CeBIT, one of the questions was: which linux version came before version 0.95? I have to admit that I don't know the answer, but I know for sure that it was not 0.94.
This reminds us of the early days of linux, and the creative chaos that surrounded it. At that time it was a challenge for many co-developers of linux to understand and modify the sources of an operating system.
Since then, linux has not only reached the magical milestone of version 2.4, but also won a solid position in the highly competitive software field. With regard to the challenge of understanding an operating system, nothing has changed, in fact it has become even greater.
Many of the features added since the last milestone version not only embody the very simple functions of an operating system, but more and more functions which provide compatibility with large software products, support new hardware, or improve the performance of the system. Version 2.4 also offers exciting new concepts like IP tables and improved plug-and-play.
As with every new milestone of the linux kernel, a kernel book must also be revised to cover the new features. Despite big changes to interfaces and concepts, the book again gives an insight into the workings of linux. We hope you will not only enjoy reading it, but also enjoy experimenting with the linux kernel.
Michael Beck, Ulrich Kunitz, Harald Böhme,
Robert Magnus, Mirko Dziadzka, Claus Schröter
Berlin/Frankfurt/Furtwangen, 24. 4. 2001
linux has been around for about two years. What started as a programming exercise by the computer science student Linus Torvalds, has become one of the most successfulfree software projects of today, and gives serious competition to commercial systems. This is the result of the voluntary work of a worldwide programming community connected by the internet, an effective communication medium. The free availability of linux has contributed to its quick distribution. Therefore it is hard to estimate the number of linux users. In Germany there are more than ten thousand.
We discovered the linux system about 18 months ago. One result of this is that we now have a "correct" Unix system for our local PCs, without having to put thousands of dollars on the table, which, as students, we didn't have anyway.
The other, perhaps more important, benefit for us, and possibly for the majority of the linux community in the world, is the availability of the source code of the linux system. It is quite simply fun to root about in the internals of an operating system to try out your own ideas, and out of pure interest to adapt the system to your own wishes. This book is aimed at everybody who thinks the same way, but also at those who simply want to find out how a 32-bit operating system works.
The linux kernel has increased in size over time, and one can no longer obtain a good overview. Since the documentation is thin (the only documentation we know of is the outline of the linux Kernel Hackers Guide Joh95), in 1993 we started a linux seminar in the summer semester. Everybody involved in linux at our workplace, gave an insight into his or her area of interest, knowledge, and experience with "kernel hacking." In the seminar there were often discussions about modeling concepts, implementation variants, and implementation details, which were grasped in various ways. In the context of this seminar we began to write down our knowledge about the system, to make it simpler for others. This knowledge is revised and represented here.
As the development of linux progresses so quickly, we couldn't allow ourselves too much time to write the book. We therefore divided the book into chapters according to the respective area of interest of the authors. Ulrich Kunitz wrote the introduction, the chapter about memory management and the chapter about interprocess communication. Mirko Dziadzka took responsibility for the introduction to the kernel. Harald Bohme, our net expert, surely ought to have written a whole book explaining the network implementation extensively. He could only write an introduction to the matter here. The thankless task of working out the referencing of system calls and explaining system commands was given to Robert Magnus. The other authors split the rest of the chapters between them.
Identifiers from the source code are set in a sanserif font in the text. Parameters are set in an italic serif font. For example:
% make Argument
Since not all readers of this book have access to the internet, the enclosed CD contains the Slackware distribution 1.2.0 and German LST distribution 1.7. They allow you to install corresponding startup disks from the CD, which have been produced with the assistance of the MS-DOS programs GZIP.EXE and RAWRITE.EXE. The authors would like to express their thanks to Patrick J.Volkerding and the linux support team, consisting of Ralf Flaxa and Stefan Probst, for the very extensive work that has been put into this book.
The CD contains the linux-Kernel version 1.0.91 and the sources of the programs explained in Appendix B as well as the sources of the GNU C library and the G ++ library. It also contains texts from the linux Documentation Project and the internet RFCs. The files aren't compressed and can be integrated in the directory structure in linux using the mount command.
The contents of the book correspond to our present knowledge of the linux kernel 1.0 but this knowledge is not yet complete. We would be grateful for any corrections, suggestions, notes, and comments.
We can be reached by e-mail at this address: firstname.lastname@example.org
Those who do not have access to e-mail can write to us at: linux-Team
Humboldt-Universität zu Berlin
Institut für Informatik
Creating an operating system has been (and still is) an exciting project, and has been made even more rewarding through the extensive (and almost uniformly positive) feedback from users and developers alike.
One of the problems for people wanting to get to know the kernel internals better has been the lack of documentation, and fledgling kernel hackers have had to resort to reading the actual source code of the system for most of the details. While I think that is still a good idea, I'm happy that there is now more documentation like this which explains the use of linux and its internals.
I hope you enjoy linux and this book.
Helsinki, 28. 4. 1994
This book would not have been possible without the work of several other people.
First we would like to thank all the linux hackers in the world, and of course Linus Torvalds. A further thank you goes to the Free Software Foundation (also known as GNU). Without GNU software, linux would not be what it is today.
We would also like to thank the employees and students at the Institute of Computer Science of the Humboldt-University of Berlin and the Faculty of Computer Science at Furtwangen Technical College who have supported us in our work.
Finally we would like to thank the innumerable copy editors, first of all Ralf Kühnel; the meticulous corrections were a great help to us.
Martin von Löwis also deserves to be mentioned, as he gave constructive criticism and supported us in the implementation of the Windows NT file system for linux.
Have a good time reading and working with linux!
Ulrich Kunitz, Harald Böhme,
Robert Magnus, Mirko Dziadzka, Dirk Verworner
Berlin/Furtwangen, 1. 5. 94