The Design and Implementation of the FreeBSD Operating System

This title provides a concise overview of FreeBSD's design and implementation. While explaining key design decisions, it details the concepts, data structures, and algorithms used in implementing the systems facilities. It is both a practical reference and an in-depth study of a contemporary, portable, open source operating system. Cover......Page 1 Contents......Page 8 Preface......Page 20 About the Authors......Page 28 Part I: Overview......Page 30 1.1 History of the UNIX System......Page 32 1.2 BSD and Other Systems......Page 36 1.3 The Transition of BSD to Open Source......Page 38 1.4 The FreeBSD Development Model......Page 43 References......Page 46 2.1 FreeBSD Facilities and the Kernel......Page 50 2.2 Kernel Organization......Page 52 2.3 Kernel Services......Page 54 2.4 Process Management......Page 55 2.5 Memory Management......Page 58 2.6 I/O System......Page 62 2.7 Devices......Page 66 2.8 Filesystems......Page 67 2.9 Network Filesystem......Page 71 2.10 Terminals......Page 72 2.11 Interprocess Communication......Page 73 2.13 Network Implementation......Page 74 Exercises......Page 75 References......Page 76 3.1 Kernel Organization......Page 78 3.2 System Calls......Page 83 3.3 Traps and Interrupts......Page 85 3.4 Clock Interrupts......Page 86 3.5 Memory-Management Services......Page 90 3.6 Timing Services......Page 94 3.7 User, Group, and Other Identifiers......Page 95 3.8 Resource Services......Page 99 3.9 System-Operation Services......Page 102 Exercises......Page 103 References......Page 104 Part II: Processes......Page 106 4.1 Introduction to Process Management......Page 108 4.2 Process State......Page 111 4.3 Context Switching......Page 117 4.4 Thread Scheduling......Page 128 4.5 Process Creation......Page 137 4.6 Process Termination......Page 139 4.7 Signals......Page 140 4.8 Process Groups and Sessions......Page 148 4.9 Jails......Page 152 4.10 Process Debugging......Page 158 Exercises......Page 161 References......Page 162 5.1 Terminology......Page 164 5.2 Overview of the FreeBSD Virtual-Memory System......Page 170 5.3 Kernel Memory Management......Page 173 5.4 Per-Process Resources......Page 180 5.5 Shared Memory......Page 185 5.6 Creation of a New Process......Page 193 5.7 Execution of a File......Page 197 5.8 Process Manipulation of Its Address Space......Page 198 5.9 Termination of a Process......Page 201 5.10 The Pager Interface......Page 202 5.11 Paging......Page 209 5.12 Page Replacement......Page 216 5.13 Portability......Page 225 Exercises......Page 238 References......Page 239 Part III: I/O System......Page 242 6.1 I/O Mapping from User to Device......Page 244 6.2 Character Devices......Page 248 6.3 Disk Devices......Page 252 6.4 Descriptor Management and Services......Page 255 6.5 The Virtual-Filesystem Interface......Page 269 6.6 Filesystem-Independent Services......Page 275 6.7 Stackable Filesystems......Page 282 Exercises......Page 289 References......Page 290 7.1 Device Overview......Page 292 7.2 The GEOM Layer......Page 299 7.3 The CAM Layer......Page 305 7.4 The ATA Layer......Page 308 7.5 Device Configuration......Page 310 Exercises......Page 321 References......Page 322 8.1 Hierarchical Filesystem Management......Page 324 8.2 Structure of an Inode......Page 326 8.3 Naming......Page 336 8.4 Quotas......Page 344 8.5 File Locking......Page 348 8.6 Soft Updates......Page 353 8.7 Filesystem Snapshots......Page 378 8.8 The Local Filestore......Page 387 8.9 The Berkeley Fast Filesystem......Page 391 Exercises......Page 408 References......Page 410 9.1 History and Overview......Page 414 9.2 NFS Structure and Operation......Page 417 9.3 Techniques for Improving Performance......Page 430 Exercises......Page 438 References......Page 439 Chapter 10 Terminal Handling......Page 442 10.1 Terminal-Processing Modes......Page 443 10.2 Line Disciplines......Page 444 10.3 User Interface......Page 445 10.4 The tty Structure......Page 447 10.5 Process Groups, Sessions, and Terminal Control......Page 449 10.6 C-lists......Page 450 10.7 RS-232 and Modem Control......Page 451 10.8 Terminal Operations......Page 452 Exercises......Page 459 References......Page 460 Part IV: Interprocess Communication......Page 462 11.1 Interprocess-Communication Model......Page 464 11.2 Implementation Structure and Overview......Page 470 11.3 Memory Management......Page 472 11.4 Data Structures......Page 478 11.5 Connection Setup......Page 484 11.6 Data Transfer......Page 486 11.7 Socket Shutdown......Page 492 11.8 Local Interprocess-Communication......Page 493 Exercises......Page 498 References......Page 499 Chapter 12 Network Communication......Page 502 12.1 Internal Structure......Page 503 12.2 Socket-to-Protocol Interface......Page 513 12.3 Protocol–Protocol Interface......Page 517 12.4 Interface Between Protocol and Network Interface......Page 520 12.5 Routing......Page 523 12.6 Buffering and Congestion Control......Page 534 12.7 Raw Sockets......Page 535 12.8 Additional Network-Subsystem Topics......Page 537 Exercises......Page 539 References......Page 541 Chapter 13 Network Protocols......Page 542 13.1 IPv4 Network Protocols......Page 543 13.2 User Datagram Protocol (UDP)......Page 548 13.3 Internet Protocol (IP)......Page 551 13.4 Transmission Control Protocol (TCP)......Page 555 13.5 TCP Algorithms......Page 563 13.6 TCP Input Processing......Page 571 13.7 TCP Output Processing......Page 575 13.8 Internet Control Message Protocol (ICMP)......Page 585 13.9 IPv6......Page 587 13.10 Security......Page 598 Exercises......Page 613 References......Page 615 Part V: System Operation......Page 620 14.1 Overview......Page 622 14.2 Bootstrapping......Page 624 14.3 Kernel Initialization......Page 625 14.4 Kernel Module Initialization......Page 627 14.5 User-Level Initialization......Page 636 14.6 System Operation......Page 638 References......Page 643 A......Page 644 B......Page 645 C......Page 646 D......Page 649 E......Page 651 F......Page 652 H......Page 654 I......Page 655 K......Page 658 L......Page 659 M......Page 660 N......Page 662 O......Page 663 P......Page 664 R......Page 667 S......Page 670 T......Page 677 U......Page 679 W......Page 680 Z......Page 681 A......Page 682 B......Page 683 C......Page 684 D......Page 686 F......Page 688 G......Page 690 I......Page 691 J......Page 693 L......Page 694 M......Page 695 N......Page 696 O......Page 697 P......Page 698 R......Page 701 S......Page 702 T......Page 708 U......Page 709 V......Page 710 W......Page 711 Z......Page 712 Cover 1 Contents 8 Preface 20 About the Authors 28 Part I: Overview 30 Chapter 1 History and Goals 32 1.1 History of the UNIX System 32 1.2 BSD and Other Systems 36 1.3 The Transition of BSD to Open Source 38 1.4 The FreeBSD Development Model 43 References 46 Chapter 2 Design Overview of FreeBSD 50 2.1 FreeBSD Facilities and the Kernel 50 2.2 Kernel Organization 52 2.3 Kernel Services 54 2.4 Process Management 55 2.5 Memory Management 58 2.6 I/O System 62 2.7 Devices 66 2.8 Filesystems 67 2.9 Network Filesystem 71 2.10 Terminals 72 2.11 Interprocess Communication 73 2.12 Network Communication 74 2.13 Network Implementation 74 2.14 System Operation 75 Exercises 75 References 76 Chapter 3 Kernel Services 78 3.1 Kernel Organization 78 3.2 System Calls 83 3.3 Traps and Interrupts 85 3.4 Clock Interrupts 86 3.5 Memory-Management Services 90 3.6 Timing Services 94 3.7 User, Group, and Other Identifiers 95 3.8 Resource Services 99 3.9 System-Operation Services 102 Exercises 103 References 104 Part II: Processes 106 Chapter 4 Process Management 108 4.1 Introduction to Process Management 108 4.2 Process State 111 4.3 Context Switching 117 4.4 Thread Scheduling 128 4.5 Process Creation 137 4.6 Process Termination 139 4.7 Signals 140 4.8 Process Groups and Sessions 148 4.9 Jails 152 4.10 Process Debugging 158 Exercises 161 References 162 Chapter 5 Memory Management 164 5.1 Terminology 164 5.2 Overview of the FreeBSD Virtual-Memory System 170 5.3 Kernel Memory Management 173 5.4 Per-Process Resources 180 5.5 Shared Memory 185 5.6 Creation of a New Process 193 5.7 Execution of a File 197 5.8 Process Manipulation of Its Address Space 198 5.9 Termination of a Process 201 5.10 The Pager Interface 202 5.11 Paging 209 5.12 Page Replacement 216 5.13 Portability 225 Exercises 238 References 239 Part III: I/O System 242 Chapter 6 I/O System Overview 244 6.1 I/O Mapping from User to Device 244 6.2 Character Devices 248 6.3 Disk Devices 252 6.4 Descriptor Management and Services 255 6.5 The Virtual-Filesystem Interface 269 6.6 Filesystem-Independent Services 275 6.7 Stackable Filesystems 282 Exercises 289 References 290 Chapter 7 Devices 292 7.1 Device Overview 292 7.2 The GEOM Layer 299 7.3 The CAM Layer 305 7.4 The ATA Layer 308 7.5 Device Configuration 310 Exercises 321 References 322 Chapter 8 Local Filesystems 324 8.1 Hierarchical Filesystem Management 324 8.2 Structure of an Inode 326 8.3 Naming 336 8.4 Quotas 344 8.5 File Locking 348 8.6 Soft Updates 353 8.7 Filesystem Snapshots 378 8.8 The Local Filestore 387 8.9 The Berkeley Fast Filesystem 391 Exercises 408 References 410 Chapter 9 The Network Filesystem 414 9.1 History and Overview 414 9.2 NFS Structure and Operation 417 9.3 Techniques for Improving Performance 430 Exercises 438 References 439 Chapter 10 Terminal Handling 442 10.1 Terminal-Processing Modes 443 10.2 Line Disciplines 444 10.3 User Interface 445 10.4 The tty Structure 447 10.5 Process Groups, Sessions, and Terminal Control 449 10.6 C-lists 450 10.7 RS-232 and Modem Control 451 10.8 Terminal Operations 452 10.9 Other Line Disciplines 459 Exercises 459 References 460 Part IV: Interprocess Communication 462 Chapter 11 Interprocess Communication 464 11.1 Interprocess-Communication Model 464 11.2 Implementation Structure and Overview 470 11.3 Memory Management 472 11.4 Data Structures 478 11.5 Connection Setup 484 11.6 Data Transfer 486 11.7 Socket Shutdown 492 11.8 Local Interprocess-Communication 493 Exercises 498 References 499 Chapter 12 Network Communication 502 12.1 Internal Structure 503 12.2 Socket-to-Protocol Interface 513 12.3 Protocol–Protocol Interface 517 12.4 Interface Between Protocol and Network Interface 520 12.5 Routing 523 12.6 Buffering and Congestion Control 534 12.7 Raw Sockets 535 12.8 Additional Network-Subsystem Topics 537 Exercises 539 References 541 Chapter 13 Network Protocols 542 13.1 IPv4 Network Protocols 543 13.2 User Datagram Protocol (UDP) 548 13.3 Internet Protocol (IP) 551 13.4 Transmission Control Protocol (TCP) 555 13.5 TCP Algorithms 563 13.6 TCP Input Processing 571 13.7 TCP Output Processing 575 13.8 Internet Control Message Protocol (ICMP) 585 13.9 IPv6 587 13.10 Security 598 Exercises 613 References 615 Part V: System Operation 620 Chapter 14 Startup and Shutdown 622 14.1 Overview 622 14.2 Bootstrapping 624 14.3 Kernel Initialization 625 14.4 Kernel Module Initialization 627 14.5 User-Level Initialization 636 14.6 System Operation 638 Exercises 643 References 643 Glossary 644 A 644 B 645 C 646 D 649 E 651 F 652 G 654 H 654 I 655 J 658 K 658 L 659 M 660 N 662 O 663 P 664 R 667 S 670 T 677 U 679 V 680 W 680 Z 681 Index 682 A 682 B 683 C 684 D 686 E 688 F 688 G 690 H 691 I 691 J 693 K 694 L 694 M 695 N 696 O 697 P 698 Q 701 R 701 S 702 T 708 U 709 V 710 W 711 X 712 Z 712 As in earlier Addison-Wesley books on the UNIX-based BSD operating system, Kirk McKusick and George Neville-Neil deliver here the most comprehensive, up-to-date, and authoritative technical information on the internal structure of open source FreeBSD. Readers involved in technical and sales support can learn the capabilities and limitations of the system; applications developers can learn effectively and efficiently how to interface to the system; system administrators can learn how to maintain, tune, and configure the system; and systems programmers can learn how to extend, enhance, and interface to the system.The authors provide a concise overview of FreeBSD's design and implementation. Then, while explaining key design decisions, they detail the concepts, data structures, and algorithms used in implementing the systems facilities. As a result, readers can use this book as both a practical reference and an in-depth study of a contemporary, portable, open source operating system.This book: \* Details the many performance improvements in the virtual memory system \* Describes the new symmetric multiprocessor support \* Includes new sections on threads and their scheduling \* Introduces the new jail facility to ease the hosting of multiple domains \* Updates information on networking and interprocess communication Already widely used for Internet services and firewalls, high-availability servers, and general timesharing systems, the lean quality of FreeBSD also suits the growing area of embedded systems. Unlike Linux, FreeBSD does not require users to publicize any changes they make to the source code. As in earlier Addison-Wesley books on the UNIX-based BSD operating system, Kirk McKusick and George Neville-Neil deliver here the most comprehensive, up-to-date, and authoritative technical information on the internal structure of open source FreeBSD. Readers involved in technical and sales support can learn the capabilities and limitations of the system; applications developers can learn effectively and efficiently how to interface to the system; system administrators can learn how to maintain, tune, and configure the system; and systems programmers can learn how to extend, enhance, and interface to the system. The authors provide a concise overview of FreeBSD's design and implementation. Then, while explaining key design decisions, they detail the concepts, data structures, and algorithms used in implementing the systems facilities. As a result, readers can use this book as both a practical reference and an in-depth study of a contemporary, portable, open source operating system. This book: Details the many performance improvements in the virtual memory system Describes the new symmetric multiprocessor support Includes new sections on threads and their scheduling Introduces the new jail facility to ease the hosting of multiple domains Updates information on networking and interprocess communication Already widely used for Internet services and firewalls, high-availability servers, and general timesharing systems, the lean quality of FreeBSD also suits the growing area of embedded systems. Unlike Linux, FreeBSD does not require users to publicize any changes they make to the source code. This book contains comprehensive, up-to-date, and authoritative technical information on the internal structure of the FreeBSD open-source operating system. Coverage includes the capabilities of the system; how to effectively and efficiently interface to the system; how to maintain, tune, and configure the operating system; and how to extend and enhance the system. The authors provide a concise overview of FreeBSD's design and implementation. Then, while explaining key design decisions, they detail the concepts, data structures, and algorithms used in implementing the systems facilities. As a result, this book can be used as an operating systems textbook, a practical reference, or an in-depth study of a contemporary, portable, open-source operating system. -- Provided by publisher