book

Design and Implementation of the FreeBSD Operating System, 2nd Edition

by Marshall Kirk McKusick, George V. Neville-Neil, Robert N.M. Watson

September 2014

Intermediate to advanced

928 pages

31h 47m

English

Addison-Wesley Professional

Read now

Unlock full access

UNIX-like SystemsBerkeley Software DistributionsMaterial Covered in this BookUse by Computer ProfessionalsUse in Courses on Operating SystemsOrganizationGetting BSDAcknowledgmentsReferences
1.1 History of the UNIX SystemOriginsResearch UNIXAT&T UNIX System III and System VBerkeley Software DistributionsUNIX in the World1.2 BSD and Other SystemsThe Influence of the User Community1.3 The Transition of BSD to Open SourceNetworking Release 2The Lawsuit4.4BSD4.4BSD-Lite Release 21.4 The FreeBSD Development ModelReferences

2.1 FreeBSD Facilities and the KernelThe Kernel2.2 Kernel Organization2.3 Kernel Services2.4 Process ManagementSignalsProcess Groups and Sessions2.5 SecurityProcess CredentialsPrivilege ModelDiscretionary Access ControlCapability ModelJail Lightweight VirtualizationMandatory Access ControlEvent AuditingCryptography and Random-Number Generators2.6 Memory ManagementBSD Memory-Management Design DecisionsMemory Management Inside the Kernel2.7 I/O System OverviewDescriptors and I/ODescriptor ManagementDevicesSocket IPCScatter-Gather I/OMultiple Filesystem Support2.8 Devices2.9 The Fast FilesystemFilestores2.10 The Zettabyte Filesystem2.11 The Network Filesystem2.12 Interprocess Communication2.13 Network-Layer Protocols2.14 Transport-Layer Protocols2.15 System Startup and ShutdownExercisesReferences
3.1 Kernel OrganizationSystem ProcessesSystem EntryRun-Time OrganizationEntry to the KernelReturn from the Kernel3.2 System CallsResult HandlingReturning from a System Call3.3 Traps and InterruptsI/O Device InterruptsSoftware Interrupts3.4 Clock InterruptsStatistics and Process SchedulingTimeouts3.5 Memory-Management Services3.6 Timing ServicesReal TimeExternal RepresentationAdjustment of the TimeInterval Time3.7 Resource ServicesProcess PrioritiesResource UtilizationResource LimitsFilesystem Quotas3.8 Kernel Tracing FacilitiesSystem-Call TracingDTraceKernel TracingExercisesReferences
4.1 Introduction to Process ManagementMultiprogrammingScheduling4.2 Process StateThe Process StructureThe Thread Structure4.3 Context SwitchingThread StateLow-Level Context SwitchingVoluntary Context SwitchingSynchronizationMutex SynchronizationMutex InterfaceLock SynchronizationDeadlock Prevention4.4 Thread SchedulingThe Low-Level SchedulerThread Run Queues and Context SwitchingTimeshare Thread SchedulingMultiprocessor SchedulingAdaptive IdleTraditional Timeshare Thread Scheduling4.5 Process Creation4.6 Process Termination4.7 SignalsPosting of a SignalDelivering a Signal4.8 Process Groups and SessionsProcess GroupsSessionsJob Control4.9 Process DebuggingExercisesReferences
5.1 Operating-System Security5.2 Security ModelProcess ModelDiscretionary and Mandatory Access ControlTrusted Computing Base (TCB)Other Kernel-Security Features5.3 Process CredentialsThe Credential StructureCredential Memory ModelAccess-Control Checks5.4 Users and GroupsSetuid and Setgid Binaries5.5 Privilege ModelImplicit PrivilegeExplicit Privilege5.6 Interprocess Access ControlVisibilitySignalsScheduling ControlWaiting on Process TerminationDebugging5.7 Discretionary Access ControlThe Virtual-Filesystem Interface and DACObject Owners and GroupsUNIX PermissionsAccess Control Lists (ACLs)POSIX.1e Access Control ListsNFSv4 Access Control Lists5.8 Capsicum Capability ModelCapsicum Application StructureCapability SystemsCapabilitiesCapability Mode5.9 Jails5.10 Mandatory Access-Control FrameworkMandatory PoliciesGuiding Design PrinciplesArchitecture of the MAC FrameworkFramework StartupPolicy RegistrationFramework Entry-Point Design ConsiderationsPolicy Entry-Point ConsiderationsKernel Service Entry-Point InvocationPolicy CompositionObject LabellingLabel Life Cycle and Memory ManagementLabel SynchronizationPolicy-Agnostic Label Management from Userspace5.11 Security Event AuditingAudit Events and RecordsBSM Audit Records and Audit TrailsKernel-Audit Implementation5.12 Cryptographic ServicesCryptographic FrameworkRandom-Number Generator5.13 GELI Full-Disk EncryptionConfidentiality and Integrity ProtectionKey ManagementStarting GELICryptographic Block ProtectionI/O ModelLimitationsExercisesReferences
6.1 TerminologyProcesses and MemoryPagingReplacement AlgorithmsWorking-Set ModelSwappingAdvantages of Virtual MemoryHardware Requirements for Virtual Memory6.2 Overview of the FreeBSD Virtual-Memory SystemUser Address-Space Management6.3 Kernel Memory ManagementKernel Maps and SubmapsKernel Address-Space AllocationThe Slab AllocatorThe Keg AllocatorThe Zone AllocatorKernel MallocKernel Zone Allocator6.4 Per-Process ResourcesFreeBSD Process Virtual-Address SpacePage-Fault DispatchMapping to Vm_objectsVm_objectsVm_objects to Pages6.5 Shared MemoryMmap ModelShared MappingPrivate MappingCollapsing of Shadow ChainsPrivate Snapshots6.6 Creation of a New ProcessReserving Kernel ResourcesDuplication of the User Address SpaceCreation of a New Process Without Copying6.7 Execution of a File6.8 Process Manipulation of Its Address SpaceChange of Process SizeFile MappingChange of Protection6.9 Termination of a Process6.10 The Pager InterfaceVnode PagerDevice PagerPhysical-Memory PagerSwap Pager6.11 PagingHardware-Cache DesignHardware Memory ManagementSuperpages6.12 Page ReplacementPaging ParametersThe Pageout DaemonSwappingThe Swap-In Process6.13 PortabilityThe Role of the pmap ModuleInitialization and StartupMapping Allocation and DeallocationChange of Access and Wiring Attributes for MappingsMaintenance of Physical Page-Usage InformationInitialization of Physical PagesManagement of Internal Data StructuresExercisesReferences
7.1 Descriptor Management and ServicesOpen File EntriesManagement of DescriptorsAsynchronous I/OFile-Descriptor LockingMultiplexing I/O on DescriptorsImplementation of SelectKqueues and KeventsMovement of Data Inside the Kernel7.2 Local Interprocess CommunicationSemaphoresMessage QueuesShared Memory7.3 The Virtual-Filesystem InterfaceContents of a VnodeVnode OperationsPathname TranslationExported Filesystem Services7.4 Filesystem-Independent ServicesThe Name CacheBuffer ManagementImplementation of Buffer Management7.5 Stackable FilesystemsSimple Filesystem LayersThe Union FilesystemOther FilesystemsExercisesReferences
8.1 Device OverviewThe PC I/O ArchitectureThe Structure of the FreeBSD Mass Storage I/O SubsystemDevice Naming and Access8.2 I/O Mapping from User to DeviceDevice DriversI/O QueueingInterrupt Handling8.3 Character DevicesRaw Devices and Physical I/OCharacter-Oriented DevicesEntry Points for Character Device Drivers8.4 Disk DevicesEntry Points for Disk Device DriversSorting of Disk I/O RequestsDisk Labels8.5 Network DevicesEntry Points for Network DriversConfiguration and ControlPacket ReceptionPacket Transmission8.6 Terminal HandlingTerminal-Processing ModesUser InterfaceProcess Groups, Sessions, and Terminal ControlTerminal OperationsTerminal Output (Upper Half)Terminal Output (Lower Half)Terminal InputClosing of Terminal Devices8.7 The GEOM LayerTerminology and Topology RulesChanging TopologyOperationTopological Flexibility8.8 The CAM LayerThe Path of a SCSI I/O Request Through the CAM SubsystemATA Disks8.9 Device ConfigurationDevice IdentificationAutoconfiguration Data StructuresResource Management8.10 Device VirtualizationInteraction with the HypervisorVirtioXenDevice Pass-ThroughExercisesReferences
9.1 Hierarchical Filesystem Management9.2 Structure of an InodeChanges to the Inode FormatExtended AttributesNew Filesystem CapabilitiesFile FlagsDynamic InodesInode Management9.3 NamingDirectoriesFinding of Names in DirectoriesPathname TranslationLinks9.4 Quotas9.5 File Locking9.6 Soft UpdatesUpdate Dependencies in the FilesystemDependency StructuresBitmap Dependency TrackingInode Dependency TrackingDirect-Block Dependency TrackingIndirect-Block Dependency TrackingDependency Tracking for New Indirect BlocksNew Directory-Entry Dependency TrackingNew Directory Dependency TrackingDirectory-Entry Removal-Dependency TrackingFile TruncationFile and Directory Inode ReclamationDirectory-Entry Renaming Dependency TrackingFsync Requirements for Soft UpdatesFile-Removal Requirements for Soft UpdatesSoft-Updates Requirements for fsck9.7 Filesystem SnapshotsCreating a Filesystem SnapshotMaintaining a Filesystem SnapshotLarge Filesystem SnapshotsBackground fsckUser-Visible SnapshotsLive Dumps9.8 Journaled Soft UpdatesBackground and IntroductionCompatibility with Other ImplementationsJournal FormatModifications That Require JournalingAdditional Requirements of JournalingThe Recovery ProcessPerformanceFuture WorkTracking File-Removal Dependencies9.9 The Local FilestoreOverview of the FilestoreUser I/O to a File9.10 The Berkeley Fast FilesystemOrganization of the Berkeley Fast FilesystemBoot BlocksOptimization of Storage UtilizationReading and Writing to a FileLayout PoliciesAllocation MechanismsBlock ClusteringExtent-Based AllocationExercisesReferences
10.1 Introduction10.2 ZFS OrganizationZFS DnodeZFS Block PointersZFS objset Structure10.3 ZFS StructureThe MOS LayerThe Object-Set Layer10.4 ZFS OperationWriting New Data to DiskLoggingRAIDZSnapshotsZFS Block AllocationFreeing BlocksDeduplicationRemote Replication10.5 ZFS Design TradeoffsExercisesReferences
11.1 Overview11.2 Structure and OperationThe FreeBSD NFS ImplementationClient–Server InteractionsSecurity IssuesTechniques for Improving Performance11.3 NFS EvolutionNamespaceAttributesAccess Control ListsCaching, Delegation, and CallbacksLockingSecurityCrash RecoveryExercisesReferences
12.1 Interprocess-Communication ModelUse of Sockets12.2 Implementation Structure and Overview12.3 Memory ManagementMbufsStorage-Management AlgorithmsMbuf Utility Routines12.4 IPC Data StructuresSocket AddressesLocks12.5 Connection Setup12.6 Data TransferTransmitting DataReceiving Data12.7 Socket Shutdown12.8 Network-Communication Protocol Internal StructureData FlowCommunication Protocols12.9 Socket-to-Protocol InterfaceProtocol User-Request RoutinesProtocol Control-Output Routine12.10 Protocol-to-Protocol Interfacepr_outputpr_inputpr_ctlinput12.11 Protocol-to-Network InterfaceNetwork Interfaces and Link-Layer ProtocolsPacket TransmissionPacket Reception12.12 Buffering and Flow ControlProtocol Buffering PoliciesQueue Limiting12.13 Network VirtualizationExercisesReferences
13.1 Internet Protocol Version 4IPv4 AddressesBroadcast AddressesInternet MulticastLink-Layer Address Resolution13.2 Internet Control Message Protocols (ICMP)13.3 Internet Protocol Version 6IPv6 AddressesIPv6 Packet FormatsChanges to the Socket APIAutoconfiguration13.4 Internet Protocols Code StructureOutputInputForwarding13.5 RoutingKernel Routing TablesRouting LookupRouting RedirectsRouting-Table InterfaceUser-Level Routing PoliciesUser-Level Routing Interface: Routing Socket13.6 Raw SocketsControl BlocksInput ProcessingOutput Processing13.7 SecurityIPSec OverviewSecurity ProtocolsKey ManagementIPSec Implementation13.8 Packet-Processing FrameworksBerkeley Packet FilterIP FirewallsIPFW and DummynetPacket Filter (PF)NetgraphNetmapExercisesReferences
14.1 Internet Ports and AssociationsProtocol Control Blocks14.2 User Datagram Protocol (UDP)InitializationOutputInputControl Operations14.3 Transmission Control Protocol (TCP)TCP Connection StatesSequence Variables14.4 TCP AlgorithmsTimersEstimation of Round-Trip TimeConnection EstablishmentSYN CacheSYN CookiesConnection Shutdown14.5 TCP Input Processing14.6 TCP Output ProcessingSending DataAvoidance of the Silly-Window SyndromeAvoidance of Small PacketsDelayed Acknowledgments and Window UpdatesSelective AcknowledgmentRetransmit StateSlow StartBuffer and Window SizingAvoidance of Congestion with Slow StartFast RetransmissionModular Congestion ControlThe Vegas AlgorithmThe Cubic Algorithm14.7 Stream Control Transmission Protocol (SCTP)ChunksAssociation SetupData TransferAssociation ShutdownMultihoming and HeartbeatsExercisesReferences
15.1 Firmware and BIOSes15.2 Boot LoadersMaster Boot Record and Globally Unique Identifier Partition TableThe Second-Stage Boot Loader: gptbootThe Final-Stage Boot Loader: /boot/loaderBoot Loading on Embedded Platforms15.3 Kernel BootAssembly-Language StartupPlatform-Specific C-Language StartupModular Kernel DesignModule InitializationBasic Kernel ServicesKernel-Thread InitializationDevice-Module InitializationLoadable Kernel Modules15.4 User-Level Initialization/sbin/initSystem Startup Scripts/usr/libexec/getty/usr/bin/login15.5 System OperationKernel ConfigurationSystem Shutdown and AutorebootSystem DebuggingPassage of Information To and From the KernelExercisesReferences

Content preview from Design and Implementation of the FreeBSD Operating System, 2nd Edition

Chapter 6. Memory Management

6.1 Terminology

A central component of any operating system is the memory-management system. As the name implies, memory-management facilities are responsible for the management of memory resources available on a machine. These resources are typically layered in a hierarchical fashion, with memory-access times inversely related to their proximity to the CPU (see Figure 6.1). The primary memory system is main memory; the next level of storage is secondary storage or backing storage. Main-memory systems usually are constructed from random-access memories, whereas secondary stores are placed on disk drives. In certain workstation environments, the common two-level hierarchy is a three-level hierarchy, with the addition ...