Contents1097Chapter 19:AuditingOverview10971099AuditRules1100ImplementationData Structures11001106Initialization1107ProcessingRequestsLogging Events11081110System Call Auditing1116Summary1117Appendix A:Architecture SpecificsOverview11171118DataTypes1119AlignmentMemoryPages11191120SystemCalls1120StringProcessing1122Thread RepresentationIA-321122IA-641124ARM1126Sparc641128Alpha1129Mips1131PowerPC1132AMD6411341135BitOperationsandEndianness1135Manipulationof BitChainsConversionbetween ByteOrders11361137PageTables1137Miscellaneous1137ChecksumCalculation1137ContextSwitchFindingtheCurrentProcess11381139Summary1141AppendixB:WorkingwiththeSourceCode1141OrganizationoftheKernelSources1144ConfigurationwithKconfig1144ASampleConfigurationFilexxili
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xxiii Contents Chapter 19: Auditing 1097 Overview 1097 Audit Rules 1099 Implementation 1100 Data Structures 1100 Initialization 1106 Processing Requests 1107 Logging Events 1108 System Call Auditing 1110 Summary 1116 Appendix A: Architecture Specifics 1117 Overview 1117 Data Types 1118 Alignment 1119 Memory Pages 1119 System Calls 1120 String Processing 1120 Thread Representation 1122 IA-32 1122 IA-64 1124 ARM 1126 Sparc64 1128 Alpha 1129 Mips 1131 PowerPC 1132 AMD64 1134 Bit Operations and Endianness 1135 Manipulation of Bit Chains 1135 Conversion between Byte Orders 1136 Page Tables 1137 Miscellaneous 1137 Checksum Calculation 1137 Context Switch 1137 Finding the Current Process 1138 Summary 1139 Appendix B: Working with the Source Code 1141 Organization of the Kernel Sources 1141 Configuration with Kconfig 1144 A Sample Configuration File 1144 xxiii
Contents1147Language Elementsof Kconfig1152ProcessingConfigurationInformation1154CompilingtheKernelwithKbuild1154UsingtheKbuildSystem1156StructureoftheMakefilesUseful Tools1160LXR11611163Patchand DiffGit11651169DebuggingandAnalyzingtheKernel1170GDBandDDDLocal Kernel1171KGDB11721173User-ModeLinux1174Summary1175AppendixC:NotesonC1175HowtheGNUCCompilerWorks1176FromSourceCodetoMachineProgram1180AssemblyandLinking1180ProcedureCallsOptimization11851192InlineFunctions1192Attributes1194InlineAssembler1198_builtinFunctions1200PointerArithmetic1200StandardDataStructuresandTechniquesoftheKernel1200Reference Counters1201PointerTypeConversions1202Alignment Issues1203Bit Arithmetic1206Pre-ProcessorTricks1207Miscellaneous1209Doubly Linked Lists1214HashLists1214Red-Black TreesRadixTrees12161221Summaryxxiv
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xxiv Contents Language Elements of Kconfig 1147 Processing Configuration Information 1152 Compiling the Kernel with Kbuild 1154 Using the Kbuild System 1154 Structure of the Makefiles 1156 Useful Tools 1160 LXR 1161 Patch and Diff 1163 Git 1165 Debugging and Analyzing the Kernel 1169 GDB and DDD 1170 Local Kernel 1171 KGDB 1172 User-Mode Linux 1173 Summary 1174 Appendix C: Notes on C 1175 How the GNU C Compiler Works 1175 From Source Code to Machine Program 1176 Assembly and Linking 1180 Procedure Calls 1180 Optimization 1185 Inline Functions 1192 Attributes 1192 Inline Assembler 1194 _builtin Functions 1198 Pointer Arithmetic 1200 Standard Data Structures and Techniques of the Kernel 1200 Reference Counters 1200 Pointer Type Conversions 1201 Alignment Issues 1202 Bit Arithmetic 1203 Pre-Processor Tricks 1206 Miscellaneous 1207 Doubly Linked Lists 1209 Hash Lists 1214 Red-Black Trees 1214 Radix Trees 1216 Summary 1221 xxiv
Contents1223AppendixD:SystemStartup1224Architecture-SpecificSetuponIA-32Systems1225High-Level InitializationSubsystemInitialization12251239Summary1241AppendixE:TheELEBinaryFormat1241LayoutandStructureELFHeader12431244ProgramHeaderTableSections12461248SymbolTableStringTables12491250DataStructuresintheKernel1250DataTypesHeaders1251StringTables1257SymbolTables12571259RelocationEntries1263Dynamic Linking1265Summary1267AppendixE:TheKernelDevelopmentProcess1267Introduction1268KernelTreesandtheStructureofDevelopment1269TheCommandChain1269TheDevelopmentCycle1272OnlineResources1273TheStructureofPatches1273TechnicalIssuesSubmissionandReview12771281LinuxandAcademia1282SomeExamples1284AdoptingResearch1287Summary1289ReferencesIndex1293XXV
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xxv Contents Appendix D: System Startup 1223 Architecture-Specific Setup on IA-32 Systems 1224 High-Level Initialization 1225 Subsystem Initialization 1225 Summary 1239 Appendix E: The ELF Binary Format 1241 Layout and Structure 1241 ELF Header 1243 Program Header Table 1244 Sections 1246 Symbol Table 1248 String Tables 1249 Data Structures in the Kernel 1250 Data Types 1250 Headers 1251 String Tables 1257 Symbol Tables 1257 Relocation Entries 1259 Dynamic Linking 1263 Summary 1265 Appendix F: The Kernel Development Process 1267 Introduction 1267 Kernel Trees and the Structure of Development 1268 The Command Chain 1269 The Development Cycle 1269 Online Resources 1272 The Structure of Patches 1273 Technical Issues 1273 Submission and Review 1277 Linux and Academia 1281 Some Examples 1282 Adopting Research 1284 Summary 1287 References 1289 Index 1293 xxv
IntroductionUnix is simpleand coherent, but ittakes agenius(oratanyrateaprogrammer)tounderstandand appreciate the simplicity-DennisRitchieNotefromtheauthors:Yes,wehavelostourminds.Be forewarned: You will lose yours too.BennyGoodheart&JamesCoxUnix is distinguished by a simple, coherent, and elegant design-truly remarkablefeatures that haveenabled the system to influence the world formore than a quarter ofa century.And especially thanksto the growing presence of Linux, the idea is still picking up momentum, with no end of the growthin sight.Unix and Linux carry a certainfascination,and the two quotations above hopefully capturethe spirit ofthisattraction.ConsiderDennisRitchie'squote:IsthecoinventorofUNixatBell Labscompletelyrightin saying that only a genius can appreciate the simplicity of Unix? Luckily not, because he puts himselfintoperspectiveimmediatelybyaddingthatprogrammersalsoqualifytovaluetheessenceofUnixUnderstanding the meagerly documented, demanding,and complex sources of Unix as well as of Linuxis notalways an easy task.But once one has started to experience the rich insights that canbegained fromthekernel sources, it ishard toescapethefascination of Linux.It seems fair towarn youthat it's easyto get addicted to the joy of the operating system kernel once starting to dive into it. This was alreadynoted by Benny Goodheart and James Cox, whosepreface to theirbookThe Magic Garden Explained(second quotation above)explained the internals of Unix System V.And Linux is definitely also capableof helpingyou to lose your mind!This book acts as a guide and companion that takes you through thekernel sources and sharpens your-estheticsoftheirconcepts.Thereare,how-awarenessofthebeauty,elegance,andlastbutnotleastever,some prerequisites to foster an understanding of thekernel. C should not just be a letter; neithershould itbea foreignlanguage.Operating systems are supposed tobemore than justa"Start"button,andasmallamountofalgorithmicscanalsodonoharm.Finally,itispreferableifcomputerarchitectureisnotjust about howto build themostfancy case.From an academicpoint ofview,this comes closest tothelectures"Systems Programming,""Algorithmics,"and"Fundamentals of Operating Systems."The pre-vious edition of this book has been used to teach the fundamentals of Linux to advanced undergraduatestudentsinseveraluniversities,andI hopethatthecurrenteditionwill servethesamepurpose.Discussing all aforementioned topics in detail is outside the scope of this book, and when you considerthemass of paper you are holding in your hands right now (or maybeyou are not holding it, for thisvery reason),you'll surely agree that this would not be a good idea. When a topic not directly related to
Mauerer flast.tex V2 - 09/05/2008 12:08pm Page xxvii Introduction Unix is simple and coherent, but it takes a genius (or at any rate a programmer) to understand and appreciate the simplicity. — Dennis Ritchie Note from the authors: Yes, we have lost our minds. Be forewarned: You will lose yours too. — Benny Goodheart & James Cox Unix is distinguished by a simple, coherent, and elegant design — truly remarkable features that have enabled the system to influence the world for more than a quarter of a century. And especially thanks to the growing presence of Linux, the idea is still picking up momentum, with no end of the growth in sight. Unix and Linux carry a certain fascination, and the two quotations above hopefully capture the spirit of this attraction. Consider Dennis Ritchie’s quote: Is the coinventor of Unix at Bell Labs completely right in saying that only a genius can appreciate the simplicity of Unix? Luckily not, because he puts himself into perspective immediately by adding that programmers also qualify to value the essence of Unix. Understanding the meagerly documented, demanding, and complex sources of Unix as well as of Linux is not always an easy task. But once one has started to experience the rich insights that can be gained from the kernel sources, it is hard to escape the fascination of Linux. It seems fair to warn you that it’s easy to get addicted to the joy of the operating system kernel once starting to dive into it. This was already noted by Benny Goodheart and James Cox, whose preface to their book The Magic Garden Explained (second quotation above) explained the internals of Unix System V. And Linux is definitely also capable of helping you to lose your mind! This book acts as a guide and companion that takes you through the kernel sources and sharpens your awareness of the beauty, elegance, and — last but not least — esthetics of their concepts. There are, however, some prerequisites to foster an understanding of the kernel. C should not just be a letter; neither should it be a foreign language. Operating systems are supposed to be more than just a ‘‘Start” button, and a small amount of algorithmics can also do no harm. Finally, it is preferable if computer architecture is not just about how to build the most fancy case. From an academic point of view, this comes closest to the lectures ‘‘Systems Programming,” ‘‘Algorithmics,” and ‘‘Fundamentals of Operating Systems.” The previous edition of this book has been used to teach the fundamentals of Linux to advanced undergraduate students in several universities, and I hope that the current edition will serve the same purpose. Discussing all aforementioned topics in detail is outside the scope of this book, and when you consider the mass of paper you are holding in your hands right now (or maybe you are not holding it, for this very reason), you’ll surely agree that this would not be a good idea. When a topic not directly related to
Introductionthekernel, but required to understand what the kernel does, is encountered in this book, I will brieflyintroduceyouto it.Togain amorethoroughunderstanding,however,consultthebooksoncomputingfundamentalsthatIrecommend.Naturally,thereisalargeselection.oftexts,butsomebooksthatIfoundparticularly insightful and illuminating include C Programming Language, by Brian W.Kernighan andDenis M.Ritchie[KR88];Modern Operating Systems, byAndrewS.Tanenbaum[Tan07] on thebasics ofoperatingsystemsingeneral;OperatingSystems:DesignandImplementation,byAndrewS.TanenbaumandAlbert S.Woodhull [TWO6] on UNix (Minix) in particular;Adoanced Programming in the UnixEnvironment,by W.Richard Stevens and Stephen A.Rago [SR05] on userspace programming; and the two volumesComputerArchitectureandComputerOrganizationandDesign,onthefoundationsofcomputerarchitectureby John L. Hennessy and David A. Patterson [HP06, PH07]. All have established themselves as classicsintheliterature.Additionally,Appendix C contains some information about extensions of the GNU C compiler that areused by the kernel, but do not necessarily find widespread use in general programmingWhen thefirst edition of thisbook waswritten,a scheduleforkernel releases was more orless nonexis-tent.This has changed drastically during the development ofkernel 2.6, and as I discuss in AppendixF,kernel developers havebecomeprettygoodat issuingnew releases atperiodic,predictableintervals.Ihavefocused onkernel 2.6.24,buthavealso included somereferencesto2.6.25and2.6.26,whichwerereleased afterthis book was written but before all technical publishing stepshad been completed.Sinceanumber ofcomprehensive changes tothe wholekernel havebeenmerged into2.6.24,picking this releaseasthetargetseemsagoodchoice.Whilea detail hereortherewill havechanged inmorerecentkernelversions as compared to the code discussed in this book,the big picture will remain the samefor quitesometime.In the discussion of the various components and subsystems of thekernel,I have tried to avoid over-loading the text with unimportantdetails.Likewise,Ihavetried notto losetrack of the connection withsourcecode.Itisaveryfortunatesituationthat,thankstoLinux,weareabletoinspectthesourceofareal, working,production operatingsystem,and it would be sad toneglectthis essential aspectofthekernel.Tokeep the book's volume below the space of a whole bookshelf, I have selected onlythemostcrucial parts of the sources.Appendix F introduces some techniques that ease reading of and workingwiththerealsource,anindispensablesteptowardunderstandingthestructureandimplementationofthe Linuxkernel.One particularly interesting observation about Linux (and Unix in general) is that it is well suited toevokeemotions.Flame wars on the Internetand heated technical debates aboutoperatingsystemsmaybeone thing,but for which other operating system does there exist a handbook (The Unix-Haters Handbook,edited bySimsonGarfinkel et al.[GWS94])on howbest tohateit?WhenIwrote theprefaceto thefirstedition,Inotedthatitisnotabadsignforthefuturethatacertaininternationalsoftwarecompanyresponds to Linux with a mixture of abstruse accusations and polemics.Five years later, the situationhas improved, and the aforementioned vendor has more or less officially accepted thefact that Linux hasbecomea serious competitor in the operating system world.And things are certainly going to improveeven more during the next five years. ..Naturally (and not astonishingly), I admit that I am definitely fascinated by Linux (and, sometimes, amalsosurethatIhavelostmymindbecauseofthis),and ifthisbookhelpstocarrythisexcitementtothereader, the long hours (and especially nights) spent writing it were worth every minute!Suggestionsfor improvements and constrictivecritique canbepassed towm@linux-kernel.net,or viawww.wrox.com.Naturally,I'malsohappyifyoutellmethatyou liked thebook!Xxvili
Mauerer flast.tex V2 - 09/05/2008 12:08pm Page xxviii Introduction the kernel, but required to understand what the kernel does, is encountered in this book, I will briefly introduce you to it. To gain a more thorough understanding, however, consult the books on computing fundamentals that I recommend. Naturally, there is a large selection of texts, but some books that I found particularly insightful and illuminating include C Programming Language, by Brian W. Kernighan and Denis M. Ritchie [KR88]; Modern Operating Systems, by Andrew S. Tanenbaum [Tan07] on the basics of operating systems in general; Operating Systems: Design and Implementation, by Andrew S. Tanenbaum and Albert S. Woodhull [TW06] on Unix (Minix) in particular; Advanced Programming in the Unix Environment, by W. Richard Stevens and Stephen A. Rago [SR05] on userspace programming; and the two volumes Computer Architecture and Computer Organization and Design, on the foundations of computer architecture by John L. Hennessy and David A. Patterson [HP06, PH07]. All have established themselves as classics in the literature. Additionally, Appendix C contains some information about extensions of the GNU C compiler that are used by the kernel, but do not necessarily find widespread use in general programming. When the first edition of this book was written, a schedule for kernel releases was more or less nonexistent. This has changed drastically during the development of kernel 2.6, and as I discuss in Appendix F, kernel developers have become pretty good at issuing new releases at periodic, predictable intervals. I have focused on kernel 2.6.24, but have also included some references to 2.6.25 and 2.6.26, which were released after this book was written but before all technical publishing steps had been completed. Since a number of comprehensive changes to the whole kernel have been merged into 2.6.24, picking this release as the target seems a good choice. While a detail here or there will have changed in more recent kernel versions as compared to the code discussed in this book, the big picture will remain the same for quite some time. In the discussion of the various components and subsystems of the kernel, I have tried to avoid overloading the text with unimportant details. Likewise, I have tried not to lose track of the connection with source code. It is a very fortunate situation that, thanks to Linux, we are able to inspect the source of a real, working, production operating system, and it would be sad to neglect this essential aspect of the kernel. To keep the book’s volume below the space of a whole bookshelf, I have selected only the most crucial parts of the sources. Appendix F introduces some techniques that ease reading of and working with the real source, an indispensable step toward understanding the structure and implementation of the Linux kernel. One particularly interesting observation about Linux (and Unix in general) is that it is well suited to evoke emotions. Flame wars on the Internet and heated technical debates about operating systems may be one thing, but for which other operating system does there exist a handbook (The Unix-Haters Handbook, edited by Simson Garfinkel et al. [GWS94]) on how best to hate it? When I wrote the preface to the first edition, I noted that it is not a bad sign for the future that a certain international software company responds to Linux with a mixture of abstruse accusations and polemics. Five years later, the situation has improved, and the aforementioned vendor has more or less officially accepted the fact that Linux has become a serious competitor in the operating system world. And things are certainly going to improve even more during the next five years. . . . Naturally (and not astonishingly), I admit that I am definitely fascinated by Linux (and, sometimes, am also sure that I have lost my mind because of this), and if this book helps to carry this excitement to the reader, the long hours (and especially nights) spent writing it were worth every minute! Suggestions for improvements and constrictive critique can be passed to wm@linux-kernel.net, or via www.wrox.com. Naturally, I’m also happy if you tell me that you liked the book! xxviii