ProfessionalLinuxKernel ArchitectureWolfgangMauererWILEYWileyPublishing,Inc
Mauerer ffirs.tex V2 - 08/26/2008 3:23am Page iii Professional Linux® Kernel Architecture Wolfgang Mauerer Wiley Publishing, Inc
Professional Linux? KernelArchitecturexxviiIntroduction1Chapter1:IntroductionandOverview.35Chapter2:ProcessManagementandScheduling133Chapter3:MemoryManagement289Chapter4:VirtualProcessMemory347Chapter5:LockingandInterprocessCommunication.391Chapter6:DeviceDrivers473Chapter7:Modules519Chapter8:TheVirtualFilesystem.583Chapter9:TheExtendedFilesystemFamily643Chapter1o:FilesystemswithoutPersistentStorage707Chapter11:ExtendedAttributesandAccessControl Lists733Chapter12:Networks819Chapter13:SystemCalls847Chapter14:KernelActivities893Chapter15:Timemanagement949Chapter16:PageandBufferCache.989Chapter17:DataSynchronization1023Chapter18:PageReclaimandSwapping.1097Chapter19:Auditing1117AppendixA:ArchitectureSpecifics.1141AppendixB:WorkingwiththeSourceCode.1175AppendixC:NotesonC..1223AppendixD:SystemStartup.1241AppendixE:TheELFBinaryFormat.1267AppendixF:TheKernelDevelopmentProcess.1289Bibliography1293Index
Mauerer ffirs.tex V2 - 08/26/2008 3:23am Page i Professional Linux® Kernel Architecture Introduction . xxvii Chapter 1: Introduction and Overview . 1 Chapter 2: Process Management and Scheduling . 35 Chapter 3: Memory Management . 133 Chapter 4: Virtual Process Memory . 289 Chapter 5: Locking and Interprocess Communication . 347 Chapter 6: Device Drivers . 391 Chapter 7: Modules . 473 Chapter 8: The Virtual Filesystem. 519 Chapter 9: The Extended Filesystem Family . 583 Chapter 10: Filesystems without Persistent Storage . 643 Chapter 11: Extended Attributes and Access Control Lists . 707 Chapter 12: Networks . 733 Chapter 13: System Calls . 819 Chapter 14: Kernel Activities . 847 Chapter 15: Time management . 893 Chapter 16: Page and Buffer Cache . 949 Chapter 17: Data Synchronization . 989 Chapter 18: Page Reclaim and Swapping. 1023 Chapter 19: Auditing . 1097 Appendix A: Architecture Specifics . 1117 Appendix B: Working with the Source Code . 1141 Appendix C: Notes on C . 1175 Appendix D: System Startup . 1223 Appendix E: The ELF Binary Format . 1241 Appendix F: The Kernel Development Process . 1267 Bibliography . 1289 Index . 1293
ProfessionalLinuxKernel ArchitectureWolfgangMauererWILEYWileyPublishing,Inc
Mauerer ffirs.tex V2 - 08/26/2008 3:23am Page iii Professional Linux® Kernel Architecture Wolfgang Mauerer Wiley Publishing, Inc
Professional Linux?Kernel ArchitecturePublished byWiley Publishing, Inc.10475CrosspointBoulevardIndianapolis,IN46256www.wiley.comCopyright 2008 by Wolfgang MauererPublished by Wiley Publishing, Inc., Indianapolis, IndianaPublished simultaneouslyin CanadaISBN: 978-0-470-34343-2Manufactured in the United States of America10987654321Library of Congress Cataloging-in-Publication Data:Mauerer,Wolfgang,1978-Professional Linux kernel architecture / Wolfgang Mauerer.p.cm.Includes index.ISBN 978-0-470-34343-2 (pbk.)1.Linux.2.Computerarchitecture.3.Applicationsoftware.ITitle.QA76.9.A73M382008005.4'32--dc222008028067No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by anymeans,electronic, mechanical, photocopying,recording, scanning or otherwise, except as permitted under Sections107or108ofthe1976United StatesCopyrightAct,withouteitherthepriorwrittenpermission of thePublisher,orauthorization through payment of the appropriate per-copy fee to the Copyright Clearance Center,222 RosewoodDrive,Danvers,MA01923,(978)750-8400,fax (978)646-8600.Requests to the Publisher for permission should beaddressed to the Legal Department, Wiley Publishing,Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, (317)572-3447,fax(317)572-4355,oronlineathttp://www.wi1ey.com/go/permissionsLimit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warrantieswith respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties,including without limitation warranties of fitness for a particular purpose.No warranty may be created or extendedby sales or promotional materials.The adviceand strategies contained herein may not be suitable for everysituation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting,or other professional services.If professional assistance is required,the services of a competent professional personshould be sought. Neither the publisher nor the author shall be liable for damages arising herefrom, The fact that anorganization or Website is referred to in this work as a citation and/or a potential source of further informationdoes not mean that the author or the publisher endorses the information the organization or Website may provideor recommendations it may make. Further, readers should be aware that Internet Websites listed in this work mayhave changed or disappeared between when this work was written and when it is read.For general information on our other products and services please contact our Customer Care Department within theUnited States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317)572-4002.Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Wrox Programmer to Programmer, and related trade dressare trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States andother countries, and may not be used without written permission. All other trademarks are the property of theirrespective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book.Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not beavailableinelectronicbooks
Mauerer ffirs.tex V2 - 08/26/2008 3:23am Page iv Professional Linux® Kernel Architecture Published by Wiley Publishing, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.com Copyright © 2008 by Wolfgang Mauerer Published by Wiley Publishing, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978-0-470-34343-2 Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 Library of Congress Cataloging-in-Publication Data: Mauerer, Wolfgang, 1978- Professional Linux kernel architecture / Wolfgang Mauerer. p. cm. Includes index. ISBN 978-0-470-34343-2 (pbk.) 1. Linux. 2. Computer architecture. 3. Application software. I. Title. QA76.9.A73M38 2008 005.4’32-dc22 2008028067 No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Legal Department, Wiley Publishing, Inc., 10475 Crosspoint Blvd., Indianapolis, IN 46256, (317) 572-3447, fax (317) 572-4355, or online at http://www.wiley.com/go/permissions. Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Website is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Website may provide or recommendations it may make. Further, readers should be aware that Internet Websites listed in this work may have changed or disappeared between when this work was written and when it is read. For general information on our other products and services please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Trademarks: Wiley, the Wiley logo, Wrox, the Wrox logo, Wrox Programmer to Programmer, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. All other trademarks are the property of their respective owners. Wiley Publishing, Inc., is not associated with any product or vendor mentioned in this book. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books
AbouttheAuthorWolfgang Mauerer is a quantumphysicist whose professional interests are centered around quantumcryptography,quantumelectrodynamics,and compilersfor-youguessed it-quantumarchitectures.With the confirmed capacity of being the worst experimentalist in the known universe, he sticks to thetheoretical side of his profession,which is especially reassuring considering his constant fear of acci-dentally destroying theuniverse.Outsidehis researchwork,heisfascinated by operating systems, andfor morethan a decade-starting with an article series about thekernel in 1997-hehas found greatpleasure in documenting and explaining Linux kernel internals. He is also the author of a book abouttypesetting with LaTeX and has written numerous articles that have been translated into seven languagesintotal.When he's not submerged in vast Hilbert spaces or large quantities of source code, he tries to take theopposite direction,namely,upwardbe this with model planes,a paraglider,or onfoot with an ice axin his hands: Mountains especially have the power to outrival even the Linux kernel. Consequently,heconsiders planning and accomplishing a first-ascentexpedition to the vast arctic glaciers of east Green-land to be the reallyuniqueachievement in hislifeBeing interested in everything that is fundamental, he is also the author of the first compiler forPlankalkil, the world's earliest high-level language devised in 1942-1946 by Konrad Zuse, the father ofthe computer.As an avid reader, he is proud that despite the two-digit number ofcomputers present inhis living room,thevolumerequired forbooksstill occupies a larger share
Mauerer fauth.tex V2 - 08/22/2008 4:52am Page v About the Author Wolfgang Mauerer is a quantum physicist whose professional interests are centered around quantum cryptography, quantum electrodynamics, and compilers for — you guessed it — quantum architectures. With the confirmed capacity of being the worst experimentalist in the known universe, he sticks to the theoretical side of his profession, which is especially reassuring considering his constant fear of accidentally destroying the universe. Outside his research work, he is fascinated by operating systems, and for more than a decade — starting with an article series about the kernel in 1997 — he has found great pleasure in documenting and explaining Linux kernel internals. He is also the author of a book about typesetting with LaTeX and has written numerous articles that have been translated into seven languages in total. When he’s not submerged in vast Hilbert spaces or large quantities of source code, he tries to take the opposite direction, namely, upward — be this with model planes, a paraglider, or on foot with an ice axe in his hands: Mountains especially have the power to outrival even the Linux kernel. Consequently, he considers planning and accomplishing a first-ascent expedition to the vast arctic glaciers of east Greenland to be the really unique achievement in his life. Being interested in everything that is fundamental, he is also the author of the first compiler for Plankalkul, the world’s earliest high-level language devised in 1942–1946 by Konrad Zuse, the father of ¨ the computer. As an avid reader, he is proud that despite the two-digit number of computers present in his living room, the volume required for books still occupies a larger share