Contents733Chapter12:Networks734LinkedComputers734ISo/OSIandTCP/IPReferenceModel738CommunicationviaSockets738Creating a Socket740Using Sockets744DatagramSockets745TheLayerModelofNetworkImplementation747NetworkingNamespaces749Socket Buffers750DataManagementUsingSocketBuffers753ManagementDataofSocketBuffers754NetworkAccessLayer755RepresentationofNetworkDevices760ReceivingPackets768SendingPackets768Network LayerIPv4769771ReceivingPackets772LocalDeliverytotheTransportLayer774Packet Forwarding775SendingPackets778NetfilterIPv6783785TransportLayerUDP785TCP787799ApplicationLayer799SocketData Structures803SocketsandFiles804ThesocketcallSystemCall805Creating Sockets807Receiving Data808Sending Data808NetworkingfromwithintheKernel808CommunicationFunctions810TheNetlinkMechanism817Summaryxvili
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xviii Contents Chapter 12: Networks 733 Linked Computers 734 ISO/OSI and TCP/IP Reference Model 734 Communication via Sockets 738 Creating a Socket 738 Using Sockets 740 Datagram Sockets 744 The Layer Model of Network Implementation 745 Networking Namespaces 747 Socket Buffers 749 Data Management Using Socket Buffers 750 Management Data of Socket Buffers 753 Network Access Layer 754 Representation of Network Devices 755 Receiving Packets 760 Sending Packets 768 Network Layer 768 IPv4 769 Receiving Packets 771 Local Delivery to the Transport Layer 772 Packet Forwarding 774 Sending Packets 775 Netfilter 778 IPv6 783 Transport Layer 785 UDP 785 TCP 787 Application Layer 799 Socket Data Structures 799 Sockets and Files 803 The socketcall System Call 804 Creating Sockets 805 Receiving Data 807 Sending Data 808 Networking from within the Kernel 808 Communication Functions 808 The Netlink Mechanism 810 Summary 817 xviii
Contents819Chapter13:SystemCalls820BasicsofSystemProgramming820TracingSystemCalls823SupportedStandards824RestartingSystemCalls826AvailableSystemCalls830ImplementationofSystemCallsStructureof SystemCalls830837AccesstoUserspace838SystemCall TracingSummary846847Chapter14:KerneLActivities848Interrupts848InterruptTypesHardwareIRQs849850ProcessingInterrupts853DataStructures860InterruptFlowHandling864InitializingandReservingIRQs866Servicing IRQs875SoftwareInterrupts877Starting SoftiRQProcessing878TheSoftiRQDaemon879Tasklets880GeneratingTasklets880RegisteringTasklets881ExecutingTasklets882WaitQueuesandCompletions882WaitQueuesCompletions887WorkQueues889891Summary893Chapter15:TimeManagementOverview893893TypesofTimers896ConfigurationOptionsxix
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xix Contents Chapter 13: System Calls 819 Basics of System Programming 820 Tracing System Calls 820 Supported Standards 823 Restarting System Calls 824 Available System Calls 826 Implementation of System Calls 830 Structure of System Calls 830 Access to Userspace 837 System Call Tracing 838 Summary 846 Chapter 14: Kernel Activities 847 Interrupts 848 Interrupt Types 848 Hardware IRQs 849 Processing Interrupts 850 Data Structures 853 Interrupt Flow Handling 860 Initializing and Reserving IRQs 864 Servicing IRQs 866 Software Interrupts 875 Starting SoftIRQ Processing 877 The SoftIRQ Daemon 878 Tasklets 879 Generating Tasklets 880 Registering Tasklets 880 Executing Tasklets 881 Wait Queues and Completions 882 Wait Queues 882 Completions 887 Work Queues 889 Summary 891 Chapter 15: Time Management 893 Overview 893 Types of Timers 893 Configuration Options 896 xix
Contents897ImplementationofLow-ResolutionTimers897TimerActivationand Process Accounting900WorkingwithJiffies900DataStructures902Dynamic Timers907GenericTimeSubsystem908Overview909Configuration Options910TimeRepresentation911ObjectsforTimeManagement920High-Resolution Timers921Data Structures925SettingTimers926Implementation931Periodic Tick Emulation932Switchingto High-ResolutionTimers933DynamicTicks934Data StructuresDynamicTicksforLow-ResolutionSystems935938DynamicTicksforHigh-ResolutionSystems939StoppingandStartingPeriodic Ticks943BroadcastMode944ImplementingTimer-RelatedSystemCalls944TimeBases945Thealarmand setitimerSystemCalls947Getting the Current Time947ManagingProcessTimes948Summary949Chapter16:PageandBufferCache950StructureofthePageCache951ManagingandFindingCached Pages952WritingBackModifiedData954StructureoftheBufferCache955AddressSpacesData Structures956958PageTrees961OperationsonAddressSpaces966ImplementationofthePageCacheAllocatingPages966967Finding PagesXX
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xx Contents Implementation of Low-Resolution Timers 897 Timer Activation and Process Accounting 897 Working with Jiffies 900 Data Structures 900 Dynamic Timers 902 Generic Time Subsystem 907 Overview 908 Configuration Options 909 Time Representation 910 Objects for Time Management 911 High-Resolution Timers 920 Data Structures 921 Setting Timers 925 Implementation 926 Periodic Tick Emulation 931 Switching to High-Resolution Timers 932 Dynamic Ticks 933 Data Structures 934 Dynamic Ticks for Low-Resolution Systems 935 Dynamic Ticks for High-Resolution Systems 938 Stopping and Starting Periodic Ticks 939 Broadcast Mode 943 Implementing Timer-Related System Calls 944 Time Bases 944 The alarm and setitimer System Calls 945 Getting the Current Time 947 Managing Process Times 947 Summary 948 Chapter 16: Page and Buffer Cache 949 Structure of the Page Cache 950 Managing and Finding Cached Pages 951 Writing Back Modified Data 952 Structure of the Buffer Cache 954 Address Spaces 955 Data Structures 956 Page Trees 958 Operations on Address Spaces 961 Implementation of the Page Cache 966 Allocating Pages 966 Finding Pages 967 xx
Contents968Waitingon Pages969OperationswithWholePages970PageCacheReadahead974ImplementationoftheBufferCache975Data Structures976Operations977InteractionofPageandBufferCache982IndependentBuffers988Summary989Chapter1Z:DataSynchronization989Overview991Thepdf1ushMechanism993Starting a New Thread994Thread Initialization995PerformingActualWork996PeriodicFlushing996AssociatedDataStructures996PageStatus998WritebackControl1000AdjustableParametersCentral Control10001002SuperblockSynchronization1003InodeSynchronization1003WalkingtheSuperblocks1003ExaminingSuperblockInodes1006WritingBackSingleInodes1009Congestion1009DataStructuresThresholds10101011Setting and Clearing theCongested State1012WaitingonCongestedQueues1013ForcedWriteback1015LaptopMode1016SystemCallsforSynchronizationControl1016Full SynchronizationSynchronization of Inodes10181019Synchronizationof Individual Files1021SynchronizationofMemoryMappings1022Summaryxxi
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xxi Contents Waiting on Pages 968 Operations with Whole Pages 969 Page Cache Readahead 970 Implementation of the Buffer Cache 974 Data Structures 975 Operations 976 Interaction of Page and Buffer Cache 977 Independent Buffers 982 Summary 988 Chapter 17: Data Synchronization 989 Overview 989 The pdflush Mechanism 991 Starting a New Thread 993 Thread Initialization 994 Performing Actual Work 995 Periodic Flushing 996 Associated Data Structures 996 Page Status 996 Writeback Control 998 Adjustable Parameters 1000 Central Control 1000 Superblock Synchronization 1002 Inode Synchronization 1003 Walking the Superblocks 1003 Examining Superblock Inodes 1003 Writing Back Single Inodes 1006 Congestion 1009 Data Structures 1009 Thresholds 1010 Setting and Clearing the Congested State 1011 Waiting on Congested Queues 1012 Forced Writeback 1013 Laptop Mode 1015 System Calls for Synchronization Control 1016 Full Synchronization 1016 Synchronization of Inodes 1018 Synchronization of Individual Files 1019 Synchronization of Memory Mappings 1021 Summary 1022 xxi
Contents1023Chapter18:PageReclaim andSwapping1023OverviewSwappablePages10241025Page Thrashing1026Page-SwappingAlgorithms1027PageReclaimandSwappingintheLinuxKernel1028OrganizationoftheSwapArea1029CheckingMemoryUtilization1029SelectingPagestoBeSwappedOut1029Handling PageFaults1030ShrinkingKernelCaches1030ManagingSwapAreas1030Data StructuresCreatinga SwapArea10351036ActivatingaSwapArea1039TheSwapCache1041IdentifyingSwapped-OutPages1044Structure of the Cache1045Adding New Pages1050Searching fora Page1051WritingDataBack1052PageReclaim1053OverviewData Structures10551057Determining PageActivity1062ShrinkingZones1065IsolatingLRUPagesandLumpyReclaim1068ShrinkingtheListof ActivePages1072Reclaiming InactivePages1079TheSwapToken1082HandlingSwap-PageFaultsSwappingPagesin10831084Reading the Data1085Swap Readahead1086InitiatingMemoryReclaimPeriodic Reclaim withkswapd10871090Swap-outintheEventof AcuteMemoryShortage1092ShrinkingOtherCaches1092Data Structures1093RegisteringandRemovingShrinkers1093Shrinking Caches1095Summaryxxii
Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xxii Contents Chapter 18: Page Reclaim and Swapping 1023 Overview 1023 Swappable Pages 1024 Page Thrashing 1025 Page-Swapping Algorithms 1026 Page Reclaim and Swapping in the Linux Kernel 1027 Organization of the Swap Area 1028 Checking Memory Utilization 1029 Selecting Pages to Be Swapped Out 1029 Handling Page Faults 1029 Shrinking Kernel Caches 1030 Managing Swap Areas 1030 Data Structures 1030 Creating a Swap Area 1035 Activating a Swap Area 1036 The Swap Cache 1039 Identifying Swapped-Out Pages 1041 Structure of the Cache 1044 Adding New Pages 1045 Searching for a Page 1050 Writing Data Back 1051 Page Reclaim 1052 Overview 1053 Data Structures 1055 Determining Page Activity 1057 Shrinking Zones 1062 Isolating LRU Pages and Lumpy Reclaim 1065 Shrinking the List of Active Pages 1068 Reclaiming Inactive Pages 1072 The Swap Token 1079 Handling Swap-Page Faults 1082 Swapping Pages in 1083 Reading the Data 1084 Swap Readahead 1085 Initiating Memory Reclaim 1086 Periodic Reclaim with kswapd 1087 Swap-out in the Event of Acute Memory Shortage 1090 Shrinking Other Caches 1092 Data Structures 1092 Registering and Removing Shrinkers 1093 Shrinking Caches 1093 Summary 1095 xxii