Linux Kernel Programming

by Beck, Michael; Bohme, Harald; Bohme, Harald; Dziadzka, Mirko; Kunitz, Ulrich; Magnus, Robert; Verworner, Dirk

• ISBN13: 9780201719758
• ISBN10: 0201719754
• Edition: 3rd
• Format: Paperback
• Copyright: 2002-08-22
• Publisher: Addison-Wesley Professional

Summary

Preface to the 3rd edition

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

Authors' preface to the 1st edition

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: [e-mail]

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
10099 Berlin

Linus Torvalds' Preface to the 1st Edition

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.

Linus Torvalds
Helsinki, 28. 4. 1994

Acknowledgments

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!
Michael Beck,
Ulrich Kunitz, Harald Böh

Author Biography

Michael Beck is the director of software development for the DResearch Digital Media Systems GmbH.  Harold Boehme teaches computer science at Humboldt University.  Ulrich Kunitz is a software project manager for Internet Banking Solutions.  Claus Schroeter works in the Chemie.De information service.

Table of Contents

Preface	p. xi
Preface to the 3rd edition	p. xi
Preface to the 1st edition	p. xii
Linus Torvalds' preface to the 1st edition	p. xiii
Acknowledgments	p. xiv
Linux - The Operating System	p. 1
Main characteristics	p. 2
Linux distributions	p. 5
Compiling the Kernel	p. 6
Where is everything?	p. 6
Compiling	p. 8
Additional configuration facilities	p. 10
Introduction to the Kernel	p. 12
Important data structures	p. 16
The task structure	p. 16
The process table	p. 24
Files and inodes	p. 25
Dynamic memory management	p. 27
Queues and semaphores	p. 28
System time and timers	p. 30
Main algorithms	p. 31
Signals	p. 31
Hardware interrupts	p. 32
Software interrupts	p. 33
Booting the system	p. 34
Timer interrupts	p. 36
The scheduler	p. 39
Implementation of system calls	p. 42
How do system calls actually work?	p. 42
Examples of simple system calls	p. 44
Examples of more complex system calls	p. 45
Memory Management	p. 55
The architecture-independent memory model	p. 57
Pages of memory	p. 57
Virtual address space	p. 57
Converting the linear address	p. 59
Page directories	p. 61
The page table	p. 63
The virtual address space of a process	p. 65
The user segment	p. 65
Virtual memory areas	p. 67
The system call brk	p. 70
Mapping functions	p. 71
The kernel segment	p. 71
Memory allocation in the kernel segment during booting	p. 72
Dynamic memory management in the kernel segment	p. 72
Block device caching	p. 75
Block buffering	p. 75
Bdflush and kupdate	p. 77
List structures for the buffer cache	p. 78
Using the buffer cache	p. 79
Paging under Linux	p. 80
Memory management and the memory cache	p. 82
Reserving a page of memory	p. 84
Optimization of memory page management via kernel threads	p. 87
Page errors and reloading a page	p. 88
Interprocess Communication	p. 90
Synchronization in the kernel	p. 92
Communication via files	p. 97
Locking entire files	p. 98
Locking file areas	p. 99
Pipes	p. 103
Debugging using ptrace	p. 105
System V IPC	p. 108
Access rights, numbers, and keys	p. 109
Semaphores	p. 110
Message queues	p. 114
Shared memory	p. 117
The ipcs and ipcrm commands	p. 120
IPC with sockets	p. 121
A simple example	p. 122
The implementation of Unix domain sockets	p. 126
The Linux File System	p. 129
Basic principles	p. 130
The representation of file systems in the kernel	p. 132
Mounting	p. 134
The superblock	p. 134
Superblock operations	p. 136
The directory cache	p. 139
Dentry operations	p. 141
The inode	p. 142
Inode operations	p. 144
The file structure	p. 147
File operations	p. 148
Opening a file	p. 152
The Ext2 file system	p. 156
The structure of the Ext2 file system	p. 156
Directories in the Ext2 file system	p. 159
Block allocation in the Ext2 file system	p. 160
Extensions of the Ext2 file system	p. 161
The Proc file system	p. 162
Structures of the Proc file system	p. 163
Implementation of the Proc file system	p. 164
Device Drivers Under Linux	p. 169
Character and block devices	p. 171
Hardware	p. 172
Port I/O	p. 172
The PCI bus	p. 173
The dinosaur--the ISA bus	p. 184
ISA-PnP	p. 193
Polling, interrupts, and waiting queues	p. 198
Polling	p. 199
Interrupt mode	p. 200
Interrupt sharing	p. 201
Software interrupts	p. 202
Bottom halves--the lower interrupt halves	p. 203
Task queues	p. 204
Timers	p. 206
Implementing a driver	p. 207
Example of a PC loudspeaker driver	p. 207
A simple driver	p. 210
The setup function	p. 212
Init	p. 213
Open and release	p. 215
Read and write	p. 216
IOCTL	p. 219
Poll	p. 221
Llseek	p. 223
Mmap	p. 223
Fasync	p. 225
Readdir, Fsync	p. 228
Dynamic and static drivers	p. 228
Network Implementation	p. 230
Introduction and overview	p. 231
The layer model of the network implementation	p. 232
Getting the data from A to B	p. 232
Important structures	p. 236
The socket structure	p. 236
The sk_buff structure--buffer management in the network	p. 238
The INET socket--a special part of the socket	p. 241
Protocol operations in the proto structure	p. 246
The general structure of a socket address	p. 248
Network devices under Linux	p. 248
Ethernet	p. 255
SLIP and PLIP	p. 256
The loopback device	p. 257
The dummy device	p. 257
An example device	p. 257
Modules and Debugging	p. 261
What are modules?	p. 261
Implementation in the kernel	p. 262
Signatures of symbols	p. 264
The meaning of object sections for modules and kernels	p. 264
Parameter transfer and examples	p. 267
What can be implemented as a module?	p. 268
The kernel daemon	p. 270
Simple data swapping between modules	p. 270
An example module	p. 271
Debugging	p. 272
Changes are the beginning of the end	p. 272
The best debugger--printk ()	p. 273
Debugging with gdb	p. 274
Multiprocessing	p. 276
The Intel multiprocessor specification	p. 276
Problems with multiprocessor systems	p. 277
Changes to the kernel	p. 278
Kernel initialization	p. 278
Scheduling	p. 279
Interrupt handling	p. 279
Atomic operations	p. 279
The atomic data type	p. 280
Accessing the atomic data type	p. 280
Changing and testing atomic variables	p. 280
Spin locks	p. 281
Access functions	p. 281
Read-write spin locks	p. 282
System Calls	p. 283
Process management	p. 284
The file system	p. 329
Communication	p. 362
Memory management	p. 365
All that remains	p. 371
Kernel-Related Commands	p. 373
free--overview of the system's memory	p. 373
ps--output of process statistics	p. 374
top--the CPU charts	p. 378
init--primus inter pares	p. 380
shutdown--shutting down the system	p. 388
strace--monitoring a process	p. 389
Configuring the network interface	p. 392
traceroute--Ariadne's paths in the internet	p. 393
Configuring a serial interface	p. 395
Configuring a parallel interface	p. 397
Building a directory tree	p. 398
The Proc File System	p. 406
The /PROC/ directory	p. 406
The NET/ directory	p. 414
The SELF/ directory	p. 416
The SYS/ directory	p. 420
The Booting Process	p. 423
Carrying out the booting process	p. 423
LILO--the Linux loader	p. 425
Useful Kernel Functions	p. 434
References	p. 449
Index	p. 455
Table of Contents provided by Syndetics. All Rights Reserved.

Excerpts

Preface to the 3rd edition 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 Bouml;hme, Robert Magnus, Mirko Dziadzka, Claus Schrouml;ter Berlin/Frankfurt/Furtwangen, 24. 4. 2001 Authors' preface to the 1st edition 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 GuideJoh95), 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