`

`Petitioners Microsoft Corporation and HP Inc. - EX. 1019, Cover-2
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, Cover-2
`
`

`

`

`

`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. ii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. ii
`
`

`

`

`

`Linux Device Drivers
`by Alessandro Rubini
`
`Copyright© 1998 O'Reilly & Associates, Inc. All rights reserved.
`Printed in the United States of America.
`
`Published by O'Reilly & Associates, Inc., 101 Morris Street, Sebastopol, CA 95472.
`
`Editors: Andy Oram and Ellen Siever
`
`Production Editor: David Futato
`
`Printing History:
`
`February 1998:
`
`First Edition.
`
`Nutshell Handbook, the Nutshell Handbook logo, and the O'Reilly logo are registered
`trademarks and the Java™ Series is a trademark of O'Reilly & Associates, Inc. The association
`between images of the American West and the topic of Linux is a trademark of O'Reilly &
`Associates, Inc.
`
`Many of the designations used by manufacturers and sellers to distinguish their products are
`claimed as trademarks. Where those designations appear in this book, and O'Reilly &
`Associates, Inc. was aware of a trademark claim, the designations have been printed in caps
`or initial caps.
`
`While every precaution has been taken in the preparation of this book, the publisher assumes
`no responsibility for errors or omissions, or for damages resulting from the use of the
`information contained herein.
`
`ISBN: 1-56592-292-1
`[M]
`
`[6/00]
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. iv
`
`

`

`TABLE OF CONTENTS
`
`PREFACE _______________________ xi
`
`CHAPTER ONE
`AN INTRODUCTION TO THE LINUX KERNEL ______ l
`The Role of the Driver Writer
`1
`Splitting the Kernel
`3
`5
`Classes of Devices and Modules
`Security Issues
`7
`Version Numbering
`8
`License Terms
`10
`Overview of the Book
`11
`
`CHAPTER1WO
`BUILDING AND RUNNING MODULES __ __ ___ __ 13
`Modules Versus Applications
`14
`Compiling and Loading
`18
`The Kernel Symbol Table
`22
`Initialization and Shutdown
`24
`Using Resources
`28
`Automatic and Manual Configuration
`34
`36
`Doing It in User Space
`Quick Reference
`38
`
`V
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. v
`
`

`

`Table of Contents
`
`CHAPTER THREE
`41
`CHAR DRIVERS
`---------------------
`The Design of scull
`41
`Major and Minor Numbers
`42
`File Operations
`49
`52
`The file Structure
`Open and Close
`54
`Scull's Memory Usage
`58
`61
`Read and Write
`66
`Playing with the New Devices
`Quick Reference
`67
`
`CHAPTER FOUR
`DEBUGGING TECHNIQUES ____________ 69
`69
`Debugging by Printing
`Debugging by Querying
`73
`Debugging by Watching
`77
`Debugging System Faults
`79
`Using a Debugger
`88
`
`CHAPTER FIVE
`ENHANCED CHAR DRIVER OPERATIONS
`ioctl
`Blocking 1/0
`Select
`Asynchronous Notification
`Seeking a Device
`Access Control on a Device File
`Quick Reference
`
`_______ _..94
`
`95
`105
`114
`117
`121
`123
`128
`
`CHAPTER SIX
`FLOW OF TIME ________ ______ l31
`131
`Time Intervals in the Kernel
`Knowing the Current Time
`132
`134
`Delaying Execution
`Task Queues
`137
`
`vi
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. vi
`
`

`

`Kernel Timers
`Quick Reference
`
`Table of Contents
`
`147
`150
`
`CHAPTER SEVEN
`GETTING HOLD OF MEMORY __________ 152
`152
`The Real Story of kmalloc
`154
`get_ free_ page and Friends
`157
`vmalloc and Friends
`160
`Playing Dirty
`161
`Quick Reference
`
`CHAPTER EIGHT
`HARDWARE MANAGEMENT __ _____ __ __ l63
`164
`Using 1/0 Ports
`168
`Using the Parallel Port
`170
`Accessing Memory on Device Boards
`175
`Accessing the Text-Mode Video Buffer
`176
`Quick Reference
`
`CHAPTER NINE
`INTERRUPT HANDLING _ ___________ l 78
`178
`Preparing the Parallel Port
`179
`Installing an Interrupt Handler
`189
`Implementing a Handler
`194
`Bottom Halves
`199
`Interrupt Sharing
`202
`Interrupt-Driven 1/0
`203
`Race Conditions
`Version Dependencies of IRQ Handling
`211
`212
`Quick Reference
`
`CHAPTER TEN
`JUDICIOUS USE OF DATA TYPES __________ 214
`214
`Use of Standard C Types
`216
`Assigning an Explicit Size to Data Items
`Interface-Specific Types
`217
`
`vii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. vii
`
`

`

`Table of Contents
`
`Other Portability Issues
`Quick Reference
`
`218
`220
`
`CHAPTER ELEVEN
`KERNELD AND ADVANCED MODULARIZATION ___ __ 222
`Loading Modules on Demand
`222
`Version Control in Modules
`227
`Persistent Storage Across Unload/Load
`231
`Quick Reference
`234
`
`CHAPTER TWELVE
`LOADING BLOCK DRIVERS ___________ 235
`Registering the Driver
`235
`240
`The Header File blk.h
`242
`Handling Requests
`How Mounting Works
`248
`The ioctl Method
`249
`252
`Removable Devices
`255
`Partitionable Devices
`263
`Interrupt-Driven Block Drivers
`265
`Quick Reference
`
`CHAPTER THIRTEEN
`MMAP AND DMA _____________ 267
`267
`Memory Management in Linux
`275
`The mmap Device Operation
`289
`Direct Memory Access
`298
`Quick Reference
`
`CHAPTER FOURTEEN
`NETWORK DRIVERS _____ __ __ __ __ _ 301
`302
`305
`310
`318
`320
`
`How snull Is Designed
`Connecting to the Kernel
`The device Structure in Detail
`Opening and Closing
`Packet Transmission
`
`vttt
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. viii
`
`

`

`Packet Reception
`Interrupt-Driven Operation
`The Socket Buffers
`Address Resolution
`Load-Time Configuration
`Run-Time Configuration
`Custom ioctl Commands
`Statistical Information
`Multicasting
`Quick Reference
`
`Table of Contents
`
`322
`324
`325
`328
`330
`332
`334
`335
`335
`339
`
`CHAPTER FIFfEEN
`OVERVIEW OF PERIPHERAL BUSES _________ 341
`341
`The PCI Interface
`356
`A Look Back: ISA
`358
`Other PC Buses
`359
`Sbus
`360
`Quick Reference
`
`CHAPTER SIXTEEN
`PHYSICAL LAYOUT OF THE KERNEL SOURCE _ _ __ _ _ 362
`362
`Booting the Kernel
`364
`Before Booting
`368
`The Init Process
`369
`The kernel Directory
`371
`The mm Directory
`373
`The fs Directory
`Networking
`377
`378
`IPC and lib Functions
`379
`Drivers
`380
`Architecture Dependencies
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. ix
`
`

`

`Table of Contents
`
`CHAPTERSEVENI'EEN
`RECENT DEVELOPMENTS
`Modularization
`File Operations
`Accessing User Space
`Task Queues
`Interrupt Management
`Bit Operations
`Conversion Functions
`vremap
`Virtual Memory
`Handling Kernel-Space Faults
`Other Changes
`
`INDEX
`
`82
`383
`387
`391
`395
`396
`396
`397
`398
`398
`398
`400
`
`403
`
`X
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. x
`
`

`

`PREFACE
`
`As an electronic e ngineer and a do-it-yourself kind of person, I have always
`
`e njoyed using the computer to contro l exte rnal hardware. Ever since the
`clays of my father's Apple-2e, I have been looking for anothe r platform
`where I could connect my custom circuiuy a nd w rite my own driver software.
`Unfortunately, the PC o f the eighties wasn't powerful e nough, at either the soft(cid:173)
`ware or the hardware level-the inte rnal design of the PC was much worse than
`that of the Apple-2e, and rhe available documentation for a long time was unsatis(cid:173)
`fying. But then Linux appeared, and I decided to give it a ny by buying an expen(cid:173)
`sive 386 motherboard a nd no commercial software at all.
`
`At the time, I was using Uni,x systems at the university, and was greatly excited by
`the smart operating system, panicula rly when supple me nted by the even smarte r
`utilities that the GNU project donates to the user base. Running Linux o n my own
`PC mothe rboard has always been an inte resting expe rie nce, and I could even
`write my own device drivers and play with the soldering iron once again. I con(cid:173)
`tinue to tell people "when I grow up, I wanna be a hacker," and Linux is the per(cid:173)
`fect platform for such dreams. Thar said, I don't know if I will e ver grow up.
`
`As Linux matures, more and mo re people get interested in writing drivers for cus(cid:173)
`tom circuiny and for comme rcial devices. As Linus Torvalcls noted, ·'We're back to
`the times when men were men and wrote their own device d rivers. "
`
`Not being able to write innovative code, I began writing technical articles for
`Linux Journal as a contribution to the Linux community; later, Andy Oram at
`O 'Reilly expressed an inte rest in having me write a whole book about de vice
`drivers, and I accepted this task. Altho ugh real hackers can find all the necessa1y
`information in the official kernel sources, a written text can be helpful in develop(cid:173)
`ing programming skills. The text you are approaching is the result of hours of
`
`.xi
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xi
`
`

`

`Preface
`
`patient grepping through the kernel sources, and I hope the final result is worth
`the effort it took. I hope this book will be useful as a starting point for people
`who want to become kernel hackers but don't know where to start.
`
`Audience of This Book
`On the technical side, this text should offer a hands-on approach to understanding
`the kernel internals and some of the design choices made by the Linux develop(cid:173)
`ers. Although the main and official target of the book is teaching how to write
`device drivers, the enclosed material should give an intriguing overview of kernel
`implementation as well.
`
`This book should be an interesting source of information both for people who
`want to play with their computer and for technical programmers who need to deal
`with the inner levels of a Linux box. Note that "a Linux box" is a wider concept
`than "a PC running Linux" as many platforms are supported by our operating sys(cid:173)
`tem, and kernel programming is by no means bound to a specific platform.
`
`The Linux enthusiast should find in this book enough food for her mind to start
`playing with the code base, and then be able to join the group of developers who
`are continuously working on new capabilities and performance enhancements.
`Linux is still a work-in-progress, and there's always a place for new programmers
`to jump into the game.
`
`If, on the other hand, you are just trying to write a device driver for your own
`device and don't want to muck with the kernel internals, the text should be modu(cid:173)
`larized enough to fit your needs as well. If you don't want to go deep into the
`details, you can just skip the most technical sections and stick to the standard API
`used by device drivers to seamlessly integrate with the rest of the kernel.
`
`The main target of this book is writing kernel modules for version 2.0 of the Linux
`kernel. A module is object code that can be loaded at run time to add new func(cid:173)
`tionality to a running kernel. The discussion also covers version 1. 2 of the kernel,
`and the last chapter describes the changes that the driver interface underwent from
`version 2.0 to version 2.1.43 (the latest-and-greatest at the time the book went to
`technical review).
`
`Organization of the Material
`The book introduces its topics in ascending order of complexity and can be
`divided into two parts. The first part (Chapters 1 through 10) begins with the
`proper setup of kernel modules, and goes on to describe the various aspects of
`programming that you'll need in order to write a full-featured driver for a char(cid:173)
`oriented device. Every chapter covers a distinct problem and includes a "symbol
`
`xii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xii
`
`

`

`Preface
`
`table" at the end, which can be used as a reference during actual development. As
`I wrote my own drivers, I found myself referring back to my own chapters, and I
`hope you too will exploit the symbol tables.
`
`Throughout the first part of the book, the organization of the material moves
`roughly from the software-oriented concepts to the hardware-related ones. This is
`meant to allow you to test the software on your own computer as far as possible
`without the need to plug external hardware into the machine. Every chapter
`includes source code and points to sample drivers that you can run on any Linux
`computer. In Chapters 8 and 9, however, I'll ask you to connect an inch of wire to
`the parallel port in order to test out hardware handling, but this requirement
`should be manageable by everyone.
`
`The second half of the book describes block drivers and network interfaces and
`goes deeper into more advanced topics. Most likely you won't need this informa(cid:173)
`tion to write actual drivers, but I hope you appreciate the first part enough to be
`induced to go on reading.
`
`As a matter of fact, most of the material I present can be interesting independent
`of the actual need to write device drivers. Several students were referred to me for
`Linux information for their theses while I was writing this book; all of them
`enjoyed reading the appropriate chapter to support their work, even if their task
`didn't involve writing a driver.
`
`Background Information
`In order to be able to face this book, you need to be confident with C program(cid:173)
`ming. A little Unix expertise is needed as well, as I often refer to Unix commands
`and pipelines.
`
`At the hardware level, no previous expertise is required, as long as the general
`concepts are clear in advance. The text isn't based on specific PC hardware, and I
`provide all the needed information when I do refer to specific hardware.
`
`Being able to connect to the Internet would be beneficial for the reader because
`many interesting documents and upgrades can be retrieved from the network.
`Being wired is, however, not strictly necessary, and I myself have quite poor con(cid:173)
`nectivity (mainly due to the high rates of the Italian telecommunication company).
`
`As far as the software is concerned, you'll need to have Linux installed on your
`computer to run the sample drivers, but any distribution will do (and almost any
`hardware platform as well). A complete list of the needed software packages is
`found in Chapter 1, as many readers just wouldn't receive the information if it was
`in the Preface. (I expect many will skip Chapter 1 as well; most of the readers are
`hackers, aren't you?)
`
`xiii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xiii
`
`

`

`Preface
`
`Sources for Further Information
`Most of the information I provide in this book is extracted directly from the kernel
`sources. As long as you have them installed in your system, you'll rarely need
`other documents to supplement the information. There are a few interesting books
`out there that can help in writing device drivers, although the main sources of
`information are the kernel sources and the technical documentation about your
`devices. Needless to say, you'll appreciate the manuals that describe your own
`computer platform.
`
`As far as kernel hacking is concerned, the best information (after the source files)
`is available on the Internet. Linux Journal also hosts some interesting technical
`articles. Check the "Kernel Korner" column, but skip my own articles, as I tend to
`repeat myself; non-Kernel Korner articles are interesting as well, but rarely as
`technical as the average reader of this book will appreciate.
`
`On the Internet, I'd suggest looking in the following places:
`
`http://www.redhat.com:8080/
`The "HyperNews" server at Red Hat carries the Kernel Hacker's Guide, an
`interesting document about the kernel internals. Some of its chapters are quite
`old, but some have been introduced or updated recently. The material is quite
`interesting, in my opinion.
`
`http://www.kernel.org/
`ftp:! /ftp.kernel. orgl
`This site is the home of Linux kernel development. You'll find the latest ker(cid:173)
`nel release and related information. Note that the FTP site is mirrored through(cid:173)
`out the world, so you'll most likely find a mirror near you.
`
`ftp://sunsite.unc.edu/pub/Linuxldocsl
`ftp:l/tsx-11. mit.edulpub/linux/docs/
`The "Linux Documentation Project" carries a lot of interesting documents
`called "HOWfOs"; some of them are pretty technical and cover kernel-related
`topics. Sunsite and tsx-11 also carry most of the programs available for Linux;
`they are interesting in general, not only for their docs/ directory. Well, I'm sure
`you know about these archives already, but I think it's worth mentioning
`them.
`
`http://www.ssc.com/
`SSC, Specialized System Consultants, are the publishers of Linux Journal, and
`their site carries the HTML version of most of the articles they've published.
`Any interesting article they print is converted to HTML shortly after publication
`and is made available on the Web.
`
`xtv
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xiv
`
`

`

`Preface
`
`http://www.conecta.it/linuxl
`This Italian site is one of the places where a Linux enthusiast keeps updated
`information about all the ongoing projects involving Linux. Maybe you already
`know an interesting site with HTIP links about Linux development; if not, this
`one is a good starting point.
`
`Relevant Books
`In addition to source code and Internet resources, a number of good books cover
`some of the topics discussed in this book. The following list represents my per(cid:173)
`sonal anthology in the field. The books I list here either document software fea(cid:173)
`tures of Unix systems or describe interesting hardware topics. I won't name any
`books about the PC architecture, as there are too many of them. Unfortunately, I
`also can't suggest any book about the Spare architecture, as I found none. If you
`need information, I'm pretty sure a quick search through the Web will fill the gap.
`[O] Bach, Maurice. 1be Design of the Unix Operating System. Prentice Hall. 1986.
`
`This book, though quite old, covers all the issues related to Unix implementations. It
`has been the main source of inpiration for Linus to write the first Linux versions.
`[1] Beck, Michael. Linux Kernel Internals. Addison-Wesley. 1997.
`
`This book concentrates on the internal data structures and algorithms of Linux; you'll
`like it if you appreciate detailed descriptions. The first edition treated version 1.2; I
`don't know how far through later versions the new edition has moved. Version 2.0 and
`later are quite different from 1.2 in their internal details.
`[2] Stevens, Richard. Advanced Programming in 1be Unix Environment. Addison(cid:173)
`Wesley. 1992.
`
`Every detail of Unix system calls is described herein. The book is a good companion
`when implementing advanced features in the device methods. Any conceivable doubt
`about Unix semantics can be solved by referring to this book.
`[31 Stevens, Richard. Unix Network Programming. Prentice Hall. 1990.
`
`As you might imagine, this book is a high-quality reference about networking issues. It
`matches "Advanced Programming" in both quality and coverage of the subject matter.
`The books is full of source code to test every bit of user-space networking.
`[4] Comer, Douglas, and Stevens, David. Internetworking with TCP/IP Vols I, II and
`III. Prentice Hall. 1991.
`
`This heavy collection of networking information is a complete tutorial about everything
`in the Internet field. The books describe the suite of Internet Protocols and their imple(cid:173)
`mentation.
`
`xv
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xv
`
`

`

`Preface
`
`[51 Shanley, Tom, and Anderson, Don. PC/ Sytem Architecture. Addison-Wesley.
`1995.
`
`This book thoroughly describes the PCI bus and its interface standard. You'll find simi(cid:173)
`lar "System Architecture" titles for most of the hardware topics, all by the same authors.
`All these books are very interesting, although somehow PC-biased. This volume about
`PCI is the one I liked best. I disliked at least one of the books, but a careful analysis
`revealed that the book is good and just describes a bad architecture.
`[6] Digital Semiconductor. Alpha AXP Architecture Handbook. Digital Semiconduc(cid:173)
`tor. 1994.
`
`This book and the "Alpha AXP Reference Manual" are available for free from Digital
`Semiconductor. They describes the machine language of die Alpha processors and the
`underlying design issues that have been dealt with. The order number for this book is
`EC-QD2KA-TE.
`
`Conventions Used in This Book
`The following is a list of the typographical conventions used in this book.
`
`Italic
`is used for file and directory names, program and command names, com(cid:173)
`mand-line options, email addresses and path names, URLs, and for emphasiz(cid:173)
`ing new terms.
`
`Boldface
`is used to symbolize keystrokes (i.e., Ctrl-N).
`
`Constant Width
`is used in examples to show the contents of code files or the output from
`commands, and to indicate environment variables and keywords that appear
`in code.
`
`Constant Italic
`is used to indicate variable options, keywords, or text that the user is to
`replace with an actual value.
`
`Constant Bold
`is used in examples to show commands or other text that should be typed lit(cid:173)
`erally by the user.
`
`We'd Like to Hear from You
`We have tested and verified all of the information in this book to the best of our
`ability, but you may find that features have changed (or even that we have made
`
`xvi
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xvi
`
`

`

`mistakes!). Please let us know about any errors you find, as well as your sugges(cid:173)
`tions for future editions, by writing:
`
`Preface
`
`O'Reilly & Associates, Inc.
`101 Morris Street
`Sebastopol, CA 95472
`1-800-998-9938 (in the US or Canada)
`1-707-829-0515 (international/local)
`1-707-829-0104 (FAX)
`
`You can also send us messages electronically. To be put on the mailing list or
`request a catalog, send email to:
`
`info@oreilly.com
`
`(via the Internet)
`
`To ask technical questions or comment on the book, send email to:
`
`bookquestions@oreilly.com (via the Internet)
`
`Finally, we can be found on the World Wide Web at http://www.oreilly.com/.
`
`Acknowledgments
`This book isn't completely mine: I've had external help both in hardware material
`and human support. I want to thank Mr. Dreyer of Quant-X for loaning me an
`Alpha computer so I could test portability of the sample code included in this
`book. Sun-Italia has been kind as well, by loaning me a Spare machine; this
`allowed me to upgrade the box from their OS to mine. ImageNation helped by
`donating a PCI frame grabber, which I used to dissect PCI and OMA features.
`
`Surely this book would never have been finished without the help of Andy Oram
`and Michael Johnson, and the psychological support of Federica, my girlfriend(cid:173)
`ehm, wife. Andy has been my mighty editor, and Michael is the one who asked
`me to write for the Linux journal and then sent me to Andy-if someone is guilty
`for this work, that's Michael. I'd like to thank Georg van Zezschwitz, who intro(cid:173)
`duced me to the fascinating world of kernel modules and helped in writing for the
`Linux Journal. I want to thank Silvana Ranzoli, my teacher of English at high
`school, for her relentless (though sometimes perceived as cruel) commitment to
`the benefit of her classroom. I am grateful to Ellen Siever, who fixed all the lin(cid:173)
`guistic misfeatures I learned after high school; she patiently dealt with my ten(cid:173)
`dency towards hackerisms and subtleties-I'm never satisfied with rewritings.
`
`My text has been technically reviewed by Alan Cox, Greg Hankins, Hans Lermen,
`Heiko Eissfeldt, and Miguel de Icaza (in alphabetic order by first name). Their
`comments and suggestions have been very useful in pinpointing oversights and
`deficiencies of mine. I wish to thank them for spending their qualified time over
`my writing, which looks so irrelevant to their guru's activity.
`
`xvii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xvii
`
`

`

`Preface
`
`I also want to acknowledge people who allowed me to take time from "real jobs"
`to concentrate on the Linux kernel. This includes Virginia Cantoni, Alberto Bian(cid:173)
`cardi, and other people in the Vision Lab at the University, as well as Davide
`Yachaya and the staff at systemy.it, where I help as network administrator.
`
`Thanks also to the O'Reilly staff: David Futato, the copyeditor and production edi(cid:173)
`tor; Chris Reilley, the technical illustrator; Jane Ellin and Nicole Gipson Arigo for
`quality assurance; Seth Maislin, who produced the index; Len Muellner and Chris
`Maden for tools support; Edie Freedman for the cover design; Nancy Priest, who
`did the interior design; and Sheryl Avruch, the production manager.
`
`Last but not least, I thank the Linux developers for their relentless work. This
`includes both the kernel programmers and the user-space people, who often get
`forgotten. In this book I chose never to call them by name in order to avoid being
`unfair to someone I might forget. I sometimes made an exception to this rule and
`called Linus by name-hope he doesn't mind.
`
`xviii
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. xviii
`
`

`

`

`

`Chapter 1: An Introduction to the Linux Kernel
`
`The distinction between mechanism and policy is one of the best ideas behind the
`Unix design. Most programming problems can indeed be split into two parts:
`"what needs to be done" (the mechanism) and "how can the program be used"
`(the policy). If the two issues are addressed by different parts of the program, or
`even by different programs altogether, the software package is much easier to
`develop and to adapt to particular needs.
`
`For example, Unix management of the graphic display is split between the X
`server, which knows the hardware and offers a unified interface to user programs,
`and the window manager, which implements a particular policy without knowing
`anything about the hardware. People can use the same window manager on dif(cid:173)
`ferent hardware, and different users can run different configurations on the same
`workstation. Another example is the layered structure of TCP /IP networking: the
`operating system offers the socket abstraction, which is policy-free, while different
`servers are in charge of the services. Moreover, a server like f tpd provides the file
`transfer mechanism, while users can use whatever client they prefer; both com(cid:173)
`mand-line and graphic clients exist, and anyone can write a new user interface to
`transfer files.
`
`Where drivers are concerned, the same role-splitting applies. The floppy driver is
`policy-free-its role is only to show the diskette as a continuous byte array. How
`to use the device is the role of the application: tar writes it sequentially, while
`mkfs prepares the device to be mounted, and mcopy relies on the existence of a
`specific data structure on the device.
`
`When writing drivers, a programmer should pay particular attention to this funda(cid:173)
`mental problem: we need to write kernel code to access the hardware, but we
`shouldn't force particular policies on the user, since different users have different
`needs. The driver should only deal with hardware handling, leaving all the issues
`about how to use the hardware to the applications. A driver, then, is "flexible" if it
`offers access to the hardware capabilities without adding constraints. Sometimes,
`however, some policy decisions must be made.
`
`You can also look at your driver from a different perspective: it is a software layer
`that lies between the applications and the actual device. This privileged role of the
`driver allows the driver programmer to choose exactly how the device should
`appear: different drivers can offer different capabilities, even for the same device.
`The actual driver design should be a balance between many different considera(cid:173)
`tions. For instance, a single device may be used concurrently by different pro(cid:173)
`grams, and the driver programmer has complete freedom to determine how to
`handle concurrency. You could implement memory mapping on the device inde(cid:173)
`pendently of its hardware capabilities, or you could provide a user library to help
`application programmers implement new policies on top of the available primi(cid:173)
`tives, and so forth. One major consideration is the tradeoff between the desire to
`present the user with as many options as possible, balanced against the time you
`have to do the writing and the need to keep things simple so that errors don't
`creep in.
`
`2
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. 2
`
`

`

`Splitting the Kernel
`
`If a driver is designed for both synchronous and asynchronous operations, if it
`allows itself to be opened multiple times, and if it is able to exploit all the hard(cid:173)
`ware capabilities without adding a software layer "to simplify things"-like con(cid:173)
`verting binary data to text or other policy-related operations-then it will tum out
`to be easier to write and to maintain. Being "policy-free" is actually a common tar(cid:173)
`get for software designers.
`
`Most device drivers, indeed, are released together with user programs to help with
`configuration and access to the target device. Those programs can range from sim(cid:173)
`ple configuring utilities to complete graphical applications. Usually a client library
`is provided as well.
`
`The scope of this book is the kernel, so we'll try not to deal with policy issues,
`nor with application programs or support libraries. Sometimes I'll talk about differ(cid:173)
`ent policies and how to support them, but I won't go into much detail about pro(cid:173)
`grams using the device or the policies they enforce. You should understand,
`however, that user programs are an integral part of a software package and that
`even policy-free packages are distributed with configuration files that apply a
`default behavior to the underlying mechanisms.
`
`Splitting the Kernel
`In a Unix system, several concurrent processes attend to different tasks. Each pro(cid:173)
`cess asks for system resources, be it computing power, memory, network connec(cid:173)
`tivity, or some other resource. The kernel is the big chunk of executable code in
`charge of handling all such requests. Though the distinction between the different
`kernel tasks isn't always clearly marked, the kernel's role can be split, as shown in
`Figure 1-1, into the following parts:
`
`Process management
`The kernel is in charge of creating and destroying processes, and handling
`their connection to the outside world (input and output). Communication
`among different processes (through signals, pipes, or interprocess communica(cid:173)
`tion primitives) is basic to the overall system functionality, and is also handled
`by the kernel. In addition, the scheduler, probably the most critical routine in
`the whole operating system, is part of process managem~nt. More generally,
`the kernel's process management activity implements the abstraction of several
`processes on top of a single CPU.
`
`Memory management
`The computer's memory is a major resource, and the policy used to deal with
`it is a critical one for system performance. The kernel builds up a virtual
`addressing space for any and all processes on top of the limited available
`resources. The different parts of the kernel interact with the memory(cid:173)
`management subsystem through a set of function calls, ranging from simple
`mallod free equivalents to much more exotic functionalities.
`
`3
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1019, p. 3
`
`

`

`

`

`Classes of Devices and Modules
`
`Networking
`Networking must be managed by the operating system because most network
`operations are not specific to a process: incoming packets are asynchronous
`events. The packets must be collected, identified, and dispatched before a
`process takes care of them. The system is in charge of delivering data packets
`across program and network interfaces, and it must correctly put to sleep and
`wake programs waiting for data from the network. Additionally, all the routing
`and address resolution issues are implemented within the kernel.
`
`Towards the end of this book, in Chapter 16, Physical Layout of the Kernel Source,
`you'll find a roadmap to the Linux kernel, but these few words should suffice for
`now.
`
`One of the good features of Linux is the ability to expand the kernel code at run
`time. This means that you can add functionality to the kernel while the system is
`up and running.
`
`Each piece of code that can be added to the kernel is called a module. The Linux
`kernel offers support for quite a few different types (or "classes") of modules,
`including, but not limited to, device drivers. Each module is made up of object
`code (not linked to be a complete executable) that can be dynamically linked to
`the running kernel by the insmod program and can be unlinked by the rmmod
`program.
`
`In Figure 1-1, you can identify different classes of modules in charge of specific
`tasks-a module is said to belong to a specific class according to the funct