developer, who certainly needs to understand the inner workings of the kernel, shouldhave a good understanding of how the interfaces are actually used. At the same time, adevice driver writer can benefit from a good understanding of the implementationbehind the interface.This is akin to learning some library's API versus studying the actual implementationof the library.At first glance, an application programmer needs to understand only theAPI-it is often taught to treat interfaces as a black box. Likewise, a library developer isconcerned only with the library's design and implementation.I believe, however, bothparties should investtime in learning the otherhalf.An applicationprogrammer whobetter understands the underlying operating system can make much greater use of it.Similarly, the library developer should not grow out of touch with the reality and practi-cality of the applications that use the library. Consequently, I discuss both the design andusage of kernel subsystems, not only in hopes that this book will be useful to eitherparty, but also in hopes that the whole book is useful to both parties.I assume that the reader knows the C programming language and is familiar withLinux systems. Some experience with operating system design and related computer sci-ence topics is beneficial, but I try to explain concepts as much as possibleif not,theBibliography includes some excellent books on operating system design.This book is appropriatefor an undergraduate course introducing operating systemdesign as the applied text if accompanied by an introductory book on theory.This bookshould fare well either in an advanced undergraduate course or in a graduate-levelcourse without ancillary material.ThirdEditionAcknowledgmentsLike most authors, I did not write this book in a cave, which is a good thing, becausethere are bears in caves.Consequently many hearts and minds contributed to the com-pletion of this manuscript. Although no list could be complete, it is my sincere pleasureto acknowledge the assistance of many friends and colleagues who provided encourage-ment,knowledge,and constructive criticism.First,I would like to thank myteam at Addison-Wesley and Pearson who workedlong and hard to make this a better book,particularly Mark Taber for spearheading thisthird edition from conception to final product; Michael Thurston, development editor;and Tonya Simpson, project editor.A special thanks to my technical editor on this edition, Robert PJ. Day. His insight,experience, and corrections improved this book immeasurably. Despite his sterling effort,however, any remaining mistakes remain my own.I have the same gratitude to AdamBelay,Zack Brown, Martin Pool,and Chris Rivera, whose excellent technical editingefforts on the first and second editions still shine through.Many fellow kernel developers answered questions,provided support, or simply wrotecode interesting enough on which to write a book.They include Andrea Arcangeli, AlanCox, Greg Kroah-Hartman, Dave Miller, Patrick Mochel, Andrew Morton, Nick Piggin,and Linus Torvalds.www.it-ebooks.info
ptg developer, who certainly needs to understand the inner workings of the kernel, should have a good understanding of how the interfaces are actually used.At the same time, a device driver writer can benefit from a good understanding of the implementation behind the interface. This is akin to learning some library’s API versus studying the actual implementation of the library.At first glance, an application programmer needs to understand only the API—it is often taught to treat interfaces as a black box. Likewise, a library developer is concerned only with the library’s design and implementation. I believe, however, both parties should invest time in learning the other half.An application programmer who better understands the underlying operating system can make much greater use of it. Similarly, the library developer should not grow out of touch with the reality and practicality of the applications that use the library. Consequently, I discuss both the design and usage of kernel subsystems, not only in hopes that this book will be useful to either party, but also in hopes that the whole book is useful to both parties. I assume that the reader knows the C programming language and is familiar with Linux systems. Some experience with operating system design and related computer science topics is beneficial, but I try to explain concepts as much as possible—if not, the Bibliography includes some excellent books on operating system design. This book is appropriate for an undergraduate course introducing operating system design as the applied text if accompanied by an introductory book on theory.This book should fare well either in an advanced undergraduate course or in a graduate-level course without ancillary material. Third Edition Acknowledgments Like most authors, I did not write this book in a cave, which is a good thing, because there are bears in caves. Consequently many hearts and minds contributed to the completion of this manuscript.Although no list could be complete, it is my sincere pleasure to acknowledge the assistance of many friends and colleagues who provided encouragement, knowledge, and constructive criticism. First, I would like to thank my team at Addison–Wesley and Pearson who worked long and hard to make this a better book, particularly Mark Taber for spearheading this third edition from conception to final product; Michael Thurston, development editor; and Tonya Simpson, project editor. A special thanks to my technical editor on this edition, Robert P. J. Day. His insight, experience, and corrections improved this book immeasurably. Despite his sterling effort, however, any remaining mistakes remain my own. I have the same gratitude to Adam Belay, Zack Brown, Martin Pool, and Chris Rivera, whose excellent technical editing efforts on the first and second editions still shine through. Many fellow kernel developers answered questions, provided support, or simply wrote code interesting enough on which to write a book.They include Andrea Arcangeli,Alan Cox, Greg Kroah-Hartman, Dave Miller, Patrick Mochel,Andrew Morton, Nick Piggin, and Linus Torvalds. www.it-ebooks.info
A big thank you to my colleagues at Google, the most creative and intelligent groupwith which I have ever had the pleasure to work. Too many names would fill these pagesifI listed them all, but I will single out Alan Blount, Jay Crim, Chris Danis, ChrisDiBona, Eric Flatt, Mike Lockwood, San Mehat, Brian Rogan, Brian Swetland, JonTrowbridge, and SteveVinter for their friendship,knowledge, and support.RespectandlovetoPaul Amici,MikeyBabbitt,KeithBarbag,JacobBerkman,NatFriedman, Dustin Hall, Joyce Hawkins, Miguel de Icaza, Jimmy Krehl, Doris Love, LindaLove,Brette Luck, Randy O'Dowd, Sal Ribaudo and mother, Chris Rivera, CarolynRodon, Joey Shaw, Sarah Stewart, Jeremy VanDoren and family, Luis Villa, Steve Weisbergand family, and Helen Whisnant.Finally, thank you to my parents for so much,particularly my well-proportioned ears.Happy Hacking!Robert LoveBostonAbouttheAuthorRobert Love is an open source programmer, speaker, and author who has been usingand contributing to Linux for more than 15 years.Robert is currently senior softwareengineer at Google, where he was a member of the team that developed the Androidmobile platform's kernel. Prior to Google, he was Chief Architect, Linux Desktop, atNovell.BeforeNovell, hewas akernel engineerat MontaVista SoftwareandXimian.Robert's kernel projects include the preemptive kernel, the process scheduler, thekernel events layer, inotify,VM enhancements, and several device drivers.Robert has given numerous talks on and has written multiple articles about the Linuxkernel.He is a contributing editor for Linux Journal. His other books include LinuxSystemProgrammingandLinuxina Nutshell.Robert received a B.A. degree in mathematics and a B.S. degree in computer sciencefrom theUniversityof Florida.Helives inBoston.www.it-ebooks.info
ptg A big thank you to my colleagues at Google, the most creative and intelligent group with which I have ever had the pleasure to work.Too many names would fill these pages if I listed them all, but I will single out Alan Blount, Jay Crim, Chris Danis, Chris DiBona, Eric Flatt, Mike Lockwood, San Mehat, Brian Rogan, Brian Swetland, Jon Trowbridge, and Steve Vinter for their friendship, knowledge, and support. Respect and love to Paul Amici, Mikey Babbitt, Keith Barbag, Jacob Berkman, Nat Friedman, Dustin Hall, Joyce Hawkins, Miguel de Icaza, Jimmy Krehl, Doris Love, Linda Love, Brette Luck, Randy O’Dowd, Sal Ribaudo and mother, Chris Rivera, Carolyn Rodon, Joey Shaw, Sarah Stewart, Jeremy VanDoren and family, Luis Villa, Steve Weisberg and family, and Helen Whisnant. Finally, thank you to my parents for so much, particularly my well-proportioned ears. Happy Hacking! Robert Love Boston About the Author Robert Love is an open source programmer, speaker, and author who has been using and contributing to Linux for more than 15 years. Robert is currently senior software engineer at Google, where he was a member of the team that developed the Android mobile platform’s kernel. Prior to Google, he was Chief Architect, Linux Desktop, at Novell. Before Novell, he was a kernel engineer at MontaVista Software and Ximian. Robert’s kernel projects include the preemptive kernel, the process scheduler, the kernel events layer, inotify,VM enhancements, and several device drivers. Robert has given numerous talks on and has written multiple articles about the Linux kernel. He is a contributing editor for Linux Journal. His other books include Linux System Programming and Linux in a Nutshell. Robert received a B.A. degree in mathematics and a B.S. degree in computer science from the University of Florida. He lives in Boston. www.it-ebooks.info
1Introduction tothe Linux Kernelhis chapter introduces the Linux kernel and Linux operating system,placing them inthe historical context of Unix.Today,Unix is a family of operating systems implementinga similar application programming interface (API)and built around shared design deci-sions.But Unix is also a specific operating system, first built more than 40 years ago.Tounderstand Linux, we must first discuss the first Unix system.History of UnixAfterfourdecades ofuse,computer scientists continue to regard theUnixoperatingsystemas one of the most powerful and elegant systems in existence. Since the creation of Unix in1969,the brainchild of Dennis Ritchie and Ken Thompson has become a creature of legends,a systemwhosedesignhas withstood thetest of timewithfewbruisesto itsnameUnix grew out of Multics, a failed multiuser operating system project in which BellLaboratories was involved.With the Multics project terminated,members of Bell Labora-tories'Computer Sciences Research Center found themselves without a capable interac-tive operating system.In the summer of 1969, Bell Lab programmers sketched out afilesystem design that ultimately evolved into Unix.Testing itsdesign,Thompson imple-mented the new system on an otherwise-idle PDP-7.In 1971,Unix was ported to thePDP-11,and in1973,the operating system was rewritten inC--anunprecedentedstepatthe time, but one that paved the way for future portability The first Unix widely usedoutside Bell Labs was Unix System, Sixth Edition,more commonly calledV6.Othercompaniesported Unixto newmachines.Accompanyingtheseports wereenhancements that resulted in several variants of the operating system. In 1977, Bell Labsreleased a combination of these variants into a single system, Unix System IIl; in 1982,AT&T released SystemVWhataboutSystemIv?It wasan internaldevelopmentversion.www.it-ebooks.info
ptg 1 Introduction to the Linux Kernel This chapter introduces the Linux kernel and Linux operating system, placing them in the historical context of Unix.Today, Unix is a family of operating systems implementing a similar application programming interface (API) and built around shared design decisions. But Unix is also a specific operating system, first built more than 40 years ago.To understand Linux, we must first discuss the first Unix system. History of Unix After four decades of use, computer scientists continue to regard the Unix operating system as one of the most powerful and elegant systems in existence. Since the creation of Unix in 1969, the brainchild of Dennis Ritchie and KenThompson has become a creature of legends, a system whose design has withstood the test of time with few bruises to its name. Unix grew out of Multics, a failed multiuser operating system project in which Bell Laboratories was involved.With the Multics project terminated, members of Bell Laboratories’ Computer Sciences Research Center found themselves without a capable interactive operating system. In the summer of 1969, Bell Lab programmers sketched out a filesystem design that ultimately evolved into Unix.Testing its design,Thompson implemented the new system on an otherwise-idle PDP-7. In 1971, Unix was ported to the PDP-11, and in 1973, the operating system was rewritten in C—an unprecedented step at the time, but one that paved the way for future portability.The first Unix widely used outside Bell Labs was Unix System, Sixth Edition, more commonly called V6. Other companies ported Unix to new machines.Accompanying these ports were enhancements that resulted in several variants of the operating system. In 1977, Bell Labs released a combination of these variants into a single system, Unix System III; in 1982, AT&T released System V.1 1 What about System IV? It was an internal development version. www.it-ebooks.info
2Chapter1 Introduction to the Linux KernelThe simplicity of Unix's design, coupled with the fact that it was distributed withsource code, led to further development at external organizations.The most influential ofthese contributors was theUniversityof California at Berkeley Variants of Unix fromBerkeley areknown as Berkeley SoftwareDistributions, orBSD.Berkeley's first release,1BSDin1977,wasacollection ofpatchesandadditional softwareontop of Bell LabsUnix.2BSD in 1978 continued this trend, adding thecsh and vi utilities,which persiston Unix systems to this day. The first standalone Berkeley Unix was 3BSD in 1979.Itadded virtual memory (VM) to an already impressive list offeatures.A series of 4BSDreleases,4.0BSD,4.1BSD,4.2BSD,4.3BSD,followed 3BSD.These versions ofUnix addedjob control, demand paging, and TCP/IP. In 1994, the university released the final officialBerkeley Unix,featuring a rewrittenVM subsystem,as 4.4BSD.Today, thanks toBSD'spermissive license, development of BSD continues with the Darwin, FreeBSD, NetBSD,andOpenBSDsystemsIn the1980s and 1990s,multiple workstationand server companies introduced theirown commercial versions of Unix.These systems were based on either anAT&T or aBerkeley release and supported high-end features developed for their particular hardwarearchitecture.Among these systems were Digital's Tru64, Hewlett Packard's HP-UX, IBM'sAIX,Sequent'sDYNIX/ptx,SGI'sIRIX,and Sun's Solaris&SunOS.The original elegant design ofthe Unix system,along with theyears of innovationand evolutionary improvement thatfollowed, has resulted in a powerful,robust,and stableoperating system.A handful of characteristics of Unix are at the core of its strength.First,Unix is simple: Whereas some operating systems implement thousands of system calls andhave unclear design goals, Unix systems implement only hundreds of system calls andhavea straightforward,even basic,design.Second, in Unix, everything is a file.This simpli-fies the manipulation of data and devices into a set of core system calls: open(),read(),write(),lseek(),and close().Third, the Unix kernel and related system utilities arewritten in Ca property that gives Unix its amazing portability to diverse hardwarearchitectures and accessibility to a wide range ofdevelopers.Fourth,Unix has fast processcreation time and the unique fork() system call.Finally,Unix provides simple yet robustinterprocess communication (IPC) primitives that, when coupled with thefast processcreation time, enable the creation of simple programs that do one thing and do it well.Thesesingle-purpose programs can be strung together to accomplish tasks of increasing com-plexity. Unix systems thus exhibit clean layering, with a strong separation between policyand mechanism.Today, Unix is a modern operating system supporting preemptive multitasking, multi-threading,virtual memory,demand paging,shared libraries with demand loading,and2Well,okay,noteverything-butmuch isrepresentedas afile.Socketsarea notable exception.Somerecentefforts,suchasUnix'ssuccessoratBell Labs,Plan9,implementnearlyallaspectsofthesystemasafile.www.it-ebooks.info
ptg 2 Chapter 1 Introduction to the Linux Kernel The simplicity of Unix’s design, coupled with the fact that it was distributed with source code, led to further development at external organizations. The most influential of these contributors was the University of California at Berkeley. Variants of Unix from Berkeley are known as Berkeley Software Distributions, or BSD. Berkeley’s first release, 1BSD in 1977, was a collection of patches and additional software on top of Bell Labs’ Unix. 2BSD in 1978 continued this trend, adding the csh and vi utilities, which persist on Unix systems to this day. The first standalone Berkeley Unix was 3BSD in 1979. It added virtual memory (VM) to an already impressive list of features.A series of 4BSD releases, 4.0BSD, 4.1BSD, 4.2BSD, 4.3BSD, followed 3BSD.These versions of Unix added job control, demand paging, and TCP/IP. In 1994, the university released the final official Berkeley Unix, featuring a rewritten VM subsystem, as 4.4BSD.Today, thanks to BSD’s permissive license, development of BSD continues with the Darwin, FreeBSD, NetBSD, and OpenBSD systems. In the 1980s and 1990s, multiple workstation and server companies introduced their own commercial versions of Unix.These systems were based on either an AT&T or a Berkeley release and supported high-end features developed for their particular hardware architecture.Among these systems were Digital’s Tru64, Hewlett Packard’s HP-UX, IBM’s AIX, Sequent’s DYNIX/ptx, SGI’s IRIX, and Sun’s Solaris & SunOS. The original elegant design of the Unix system, along with the years of innovation and evolutionary improvement that followed, has resulted in a powerful, robust, and stable operating system.A handful of characteristics of Unix are at the core of its strength. First, Unix is simple:Whereas some operating systems implement thousands of system calls and have unclear design goals, Unix systems implement only hundreds of system calls and have a straightforward, even basic, design. Second, in Unix, everything is a file. 2 This simplifies the manipulation of data and devices into a set of core system calls: open(), read(), write(), lseek(), and close().Third, the Unix kernel and related system utilities are written in C—a property that gives Unix its amazing portability to diverse hardware architectures and accessibility to a wide range of developers. Fourth, Unix has fast process creation time and the unique fork() system call. Finally, Unix provides simple yet robust interprocess communication (IPC) primitives that, when coupled with the fast process creation time, enable the creation of simple programs that do one thing and do it well.These single-purpose programs can be strung together to accomplish tasks of increasing complexity. Unix systems thus exhibit clean layering, with a strong separation between policy and mechanism. Today, Unix is a modern operating system supporting preemptive multitasking, multithreading, virtual memory, demand paging, shared libraries with demand loading, and 2 Well, okay, not everything—but much is represented as a file. Sockets are a notable exception. Some recent efforts, such as Unix’s successor at Bell Labs, Plan9, implement nearly all aspects of the system as a file. www.it-ebooks.info
3Along Came Linus:Introduction to LinuxTCP/IP networking.ManyUnixvariants scale to hundreds of processors,whereas otherUnix systems run on small, embedded devices.Although Unix is no longer a researchproject,Unix systems continue to benefit from advances in operating system design whileremainingapractical andgeneral-purpose operating system.Unix owes its success to the simplicity and elegance of its design. Its strength todayderives from the inaugural decisions that Dennis Ritchie,Ken Thompson, and otherearly developers made: choices that have endowed Unix with the capability to evolvewithoutcompromisingitself.AlongCameLinus:IntroductiontoLinuxLinus Torvalds developed the first version of Linux in 1991 as an operating system forcomputers powered bythe Intel 80386 microprocessor,which at the time was a new andadvanced processor. Linus, then a student at the University of Helsinki, was perturbed bythe lack of a powerful yet free Unix system.The reigning personal computer OS of theday,Microsoft'sDOS, was useful toTorvalds for littleother than playingPrince of Persia.Linus did use Minix, a low-cost Unix created as a teaching aid, but he was discouraged bythe inability to easily make and distribute changes to the systems source code (because ofMinix's license) and bydesign decisions made by Minix's author.In response to his predicament, Linus did what any normal college student would do:He decided to write his own operating system.Linus began by writing a simple terminalemulator, which he used to connect to larger Unix systems at his school. Over the courseof the academic year, his terminal emulator evolved and improved. Before long,Linus hadan immature but full-fledged Unix on his hands.He posted an earlyrelease to the Inter-net inlate 1991.Use of Linux took off, with early Linux distributions quickly gaining many users.More important to its initial success, however, is that Linux quickly attracted many devel-opers-hackers adding,changing,improving code.Because of the terms of its license,Linux swiftly evolved into a collaborative project developed by many.Fast forward to the present. Today, Linux is a full-fledged operating system also runningonAlpha,ARM, PowerPC, SPARC,x86-64 and many other architectures.It runs on sys-tems as small as a watch to machines as large as room-flling super-computer clusters.Linux powers the smallest consumer electronics and thelargest Datacenters.Today,com-mercial interest inLinux is strong.Both new Linux-specific corporations,such as RedHat, and existing powerhouses, such as IBM, are providing Linux-based solutions forembedded,mobile,desktop,and serverneedsLinux is a Unix-like system, but it is not Unix.That is,although Linux borrows manyideas from Unix and implements the Unix API (as defined by POSIX and the SingleUnix Specification),it is not a direct descendant of the Unix source code like other Unixsystems.Where desired, it has deviated from the path taken by other implementations, butit has not forsaken the general design goals of Unix orbroken standardized applicationinterfaces.www.it-ebooks.info
ptg Along Came Linus: Introduction to Linux 3 TCP/IP networking. Many Unix variants scale to hundreds of processors, whereas other Unix systems run on small, embedded devices.Although Unix is no longer a research project, Unix systems continue to benefit from advances in operating system design while remaining a practical and general-purpose operating system. Unix owes its success to the simplicity and elegance of its design. Its strength today derives from the inaugural decisions that Dennis Ritchie, Ken Thompson, and other early developers made: choices that have endowed Unix with the capability to evolve without compromising itself. Along Came Linus: Introduction to Linux Linus Torvalds developed the first version of Linux in 1991 as an operating system for computers powered by the Intel 80386 microprocessor, which at the time was a new and advanced processor. Linus, then a student at the University of Helsinki, was perturbed by the lack of a powerful yet free Unix system.The reigning personal computer OS of the day, Microsoft’s DOS, was useful to Torvalds for little other than playing Prince of Persia. Linus did use Minix, a low-cost Unix created as a teaching aid, but he was discouraged by the inability to easily make and distribute changes to the system’s source code (because of Minix’s license) and by design decisions made by Minix’s author. In response to his predicament, Linus did what any normal college student would do: He decided to write his own operating system. Linus began by writing a simple terminal emulator, which he used to connect to larger Unix systems at his school. Over the course of the academic year, his terminal emulator evolved and improved. Before long, Linus had an immature but full-fledged Unix on his hands. He posted an early release to the Internet in late 1991. Use of Linux took off, with early Linux distributions quickly gaining many users. More important to its initial success, however, is that Linux quickly attracted many developers—hackers adding, changing, improving code. Because of the terms of its license, Linux swiftly evolved into a collaborative project developed by many. Fast forward to the present.Today, Linux is a full-fledged operating system also running on Alpha,ARM, PowerPC, SPARC, x86-64 and many other architectures. It runs on systems as small as a watch to machines as large as room-filling super-computer clusters. Linux powers the smallest consumer electronics and the largest Datacenters.Today, commercial interest in Linux is strong. Both new Linux-specific corporations, such as Red Hat, and existing powerhouses, such as IBM, are providing Linux-based solutions for embedded, mobile, desktop, and server needs. Linux is a Unix-like system, but it is not Unix.That is, although Linux borrows many ideas from Unix and implements the Unix API (as defined by POSIX and the Single Unix Specification), it is not a direct descendant of the Unix source code like other Unix systems.Where desired, it has deviated from the path taken by other implementations, but it has not forsaken the general design goals of Unix or broken standardized application interfaces. www.it-ebooks.info