Table of Contents: Operating System Design Volume 2


Foreword

Preface

Chapter 1 Introduction and Overview

1.1 Introduction 1
1.2 Internetworking 2
1.3 Design Methodology 2
1.4 Goals 3
1.5 A Target System 3
1.6 User Interface 3
1.6.1 Other System Information Commands 5
1.6.2 Background Processing 6
1.6.3 Changing To Background 7
1.6.4 I/O Redirection 7
1.6.5 Quoting 8
1.7 Internetwork Communication 9
1.8 Design Plan 9
1.9 Summary 11
For Further Study 11
Exercises 12

Chapter 2 An Overview of Network Hardware

2.1 Introduction 13
2.2 Two Approaches To Network Communication 13
2.3 Long-Haul And Local-Area Networks 14
2.4 Ethernet Packet-Switched Network Technology 15
2.5 Properties Of An Ethernet 18
2.6 Collision Detection And Recovery 18
2.7 Ethernet Capacity 19
2.8 Ethernet Addresses 19
2.9 Ethernet Frame Format 20
2.10 DEQNA Ethernet Interface 21
2.10.1 DEQNA CSR 21
2.10.2 The DEQNA CSR Bits 22
2.11 Format Of DEQNA Command Lists 23
2.12 Summary 23
For Further Study 24
Exercises 24

Chapter 3 Physical Transport

3.1 Introduction 27
3.2 Blocks And Frames 27
3.3 An Example Implementation Using Xinu 29
3.3.1 Ethernet And Interface Device Definitions 29
3.4 Ethernet Definitions 32
3.5 Frame Format In Memory 34
3.6 The Ethernet Frame Type 34
3.7 Ethernet Device Control Block 34
3.8 Upper-Half Input Routine 35
3.9 Upper-Half Output Routine 38
3.10 The Lower-Half Routines 40
3.11 Device And Driver Initialization 43
3.12 Ethernet Device Driver Configuration 46
3.13 Summary 46
For Further Study 47
Exercises 47

Chapter 4 Internetworking

4.1 Introduction 49
4.2 Why An Internet? 50
4.2.1 Properties Of The Internet 50
4.3 The DARPA Internet 51
4.3.1 Internet Architecture 51
4.3.2 Gateways 53
4.3.3 Internet Addressing 53
4.3.4 Network And Broadcast Addresses 54
4.3.5 Dotted Decimal Notation 54
4.3.6 The User's View 55
4.3.7 An Example 56
4.4 Network Byte Order 59
4.5 Computing A Network Address 61
4.6 The Unanswered Questions 62
4.7 Summary 63
For Further Study 63
Exercises 63

Chapter 5 Address Determination at Boot Time

5.1 Introduction 65
5.2 A Mechanism For Timing Responses 66
5.3 Reverse Address Resolution Protocol (RARP) 68
5.3.1 Sending A RARP Packet 71
5.3.2 Handling RARP Responses 72
5.4 Summary 75
For Further Study 75
Exercises 76

Chapter 6 Address Resolution at Run Time

6.1 Introduction 77
6.2 ARP: An Address Resolution Protocol 78
6.2.1 Refinements 78
6.3 ARP Implementation 79
6.3.1 Finding A Physical Address 79
6.3.2 Searching The ARP cache 81
6.3.3 Handling Incoming ARP Packets 83
6.4 ARP And RARP Initialization 86
6.5 Summary 87
For Further Study 87
Exercises 87

Chapter 7 The Internet Protocol and Routing

7.1 Introduction 89
7.2 A Virtual Network 89
7.3 Internet Datagram 90
7.3.1 Datagram Length And Fragmentation 90
7.3.2 Datagram Format 90
7.4 Sending An IP Datagram 93
7.5 Routing 94
7.5.1 Direct Routing 95
7.5.2 Indirect Routing 95
7.5.3 Simplified Routing For Single Connections 96
7.6 Summary 98
For Further Study 98
Exercises 98

Chapter 8 Internet Control Messages

8.1 Introduction 101
8.2 Extranormal Communication 101
8.3 Internet Control Message Protocol 102
8.3.1 ICMP Messages 102
8.3.2 ICMP Echo Request And Reply Messages 103
8.3.3 ICMP Redirect Messages 103
8.3.4 ICMP Source Quench 103
8.4 An Implementation Of ICMP 104
8.4.1 ICMP Message Input Processing 105
8.5 Summary 107
For Further Study 107
Exercises 108

Chapter 9 User Datagram Protocol

9.1 Introduction 109
9.2 Identifying The Ultimate Destination 109
9.3 The Important Concept Of Unreliable Delivery 110
9.4 DARPA User Datagram Protocol 111
9.4.1 The Relationship Between Packet Layout And Protocol Software 111
9.4.2 UDP Declarations 113
9.4.3 Sending User Datagrams 114
9.4.4 Assigning The IP Packet Type 115
9.4.5 Passing A User Datagram To Lower Layers 115
9.5 Summary 115
For Further Study 116
Exercises 116

Chapter 10 Network Input and Protocol Demultiplexing

10.1 Introduction 117
10.2 A Network Input Process 117
10.3 Demultiplexing 120
10.4 Implementation Of The Network Input Process 120
10.4.1 General Network Declarations 120
10.4.2 The Network Input Procedure 122
10.4.3 Network Initialization 123
10.4.4 Output By The Network Input Process 125
10.4.5 Implementation Of Network Output Process 125
10.5 The Details Of Datagram Demultiplexing 127
10.5.1 Datagram Timeout 129
10.6 The Needed Interface 129
10.7 Summary 129
For Further Study 130
Exercises 130

Chapter 11 Device Interface for Datagram Communication

11.1 Datagram Interface And Copying 131
11.2 Data Or Datagram Oriented User Interface 132
11.3 Datagram Pseudo-Device Interface 133
11.4 Datagram Pseudo-Device Implementation 133
11.4.1 Datagram Pseudo-device Initialization 135
11.4.2 Utility Procedures 136
11.4.3 Opening A Datagram Pseudo-Device 140
11.4.4 Closing A Datagram Pseudo-Device 141
11.4.5 Data Transfer Operations 142
11.4.6 Modes Of Transfer 143
11.4.7 Implementation Of Datagram Write 143
11.4.8 Implementation Of Datagram Read 145
11.4.9 Datagram Device Control Functions 148
11.5 Datagram Pseudo-Device Interface Configuration 149
11.6 Summary 150
For Further Study 151
Exercises 151

Chapter 12 The Client-Server Interaction Paradigm

12.1 Introduction 153
12.2 The Client-Server Model 154
12.3 UDP Echo Server 154
12.4 Echo Server Implementation 155
12.5 Time And Date Service 156
12.5.1 Representation For The Date And Time 156
12.5.2 Maintaining The Time-of-Day In Xinu 157
12.5.3 Local And Universal Time 159
12.5.4 Obtaining The Time 161
12.6 RARP Client 164
12.7 The ICMP Echo Server And Client-Server Model 165
12.8 Alternatives To The Client-Server Model 166
12.9 A Machine Status Service 166
12.10 Implementation Of The Machine Status Service 167
12.10.1 Rwho Packet Format 167
12.10.2 Rwho Information Collection Daemon 169
12.10.3 Clock Consistency 171
12.10.4 Rwho Output Daemon 172
12.10.5 Rwho Subsystem Startup 174
12.11 Summary 175
For Further Study 175
Exercises 175

Chapter 13 A Stateless File Server

13.1 Introduction 177
13.2 Remote Files Vs. Remote Disks 177
13.3 The Property Of Statelessness In Servers 179
13.4 Statelessness In A File Server 180
13.5 File Requests And Responses 180
13.6 Efficient, Stateless File Access 181
13.7 UNIX Implementation Of A File Server 182
13.7.1 Server Declarations 182
13.7.2 Xinu Include Files 184
13.7.3 Utility Procedures 188
13.7.4 Closing A File 188
13.7.5 Seeking In A File 189
13.7.6 Removing A File 190
13.7.7 Opening A UNIX file 190
13.7.8 Checking The Cache For Open Files 192
13.7.9 Removing Cached Information 194
13.7.10 Organization Of The Server 194
13.7.11 Acquiring A Request 196
13.7.12 Sending Replies 197
13.8 Handlers For File Operations 198
13.8.1 Mapping Requests To Handlers 198
13.8.2 Handling The Close Operation 200
13.8.3 Handling The Access Operation 200
13.8.4 Handling The Unlink Operation 201
13.8.5 Handling The Open Operation 202
13.8.6 Handling The Read Operation 202
13.8.7 Handling The Write Operation 203
13.8.8 Handling The Mkdir Operation 204
13.8.9 Handling The Rmdir Operation 205
13.8.10 Handling The Rename Operation 206
13.9 Server Initialization 208
13.9.1 Command Line Arguments 208
13.9.2 Extracting Arguments At Run-Time 209
13.9.3 Server Initialization 211
13.10 Summary 212
For Further Study 213
Exercises 213

Chapter 14 Remote File Access

14.1 Introduction 215
14.2 Remote File Pseudo-Devices 215
14.3 Maintaining State Information 216
14.4 Remote File Pseudo-Device Support Routines 216
14.5 Composing Request Packets 220
14.6 A Universal Remote I/O Routine 223
14.7 Opening A Remote File 224
14.8 Closing A Remote File 225
14.9 Reading From A Remote File 227
14.10 Writing To A Remote File 227
14.11 Single Character Transfer Operations 228
14.12 Seeking In A Remote File 230
14.13 Operations On Remote Files 230
14.14 Remote File Device Initialization 233
14.15 Remote File Pseudo-Device Configuration 235
14.16 Summary 236
For Further Study 236
Exercises 236

Chapter 15 A Syntactic Namespace

15.1 Introduction 239
15.2 The Problem With File Names 240
15.2.1 MS-DOS 240
15.2.2 UNIX 240
15.2.3 V System 241
15.2.4 Newcastle Connection 241
15.2.5 IBIS 241
15.2.6 TILDE 241
15.3 Naming System Design Alternatives 241
15.4 A Syntactic Namespace 242
15.5 Patterns And Replacements 242
15.6 Prefix Patterns 243
15.7 Implementation Of A Simple Syntactic Namespace 243
15.7.1 The Pseudo-Device NAMESPACE 243
15.7.2 Definitions Of Data Structures And Constants 244
15.7.3 Adding Mappings To The Prefix Table 245
15.7.4 Removing A Name Mapping 246
15.7.5 Mapping Names With The Prefix Table 247
15.7.6 Iterative Resolution Of Recursive Mappings 249
15.7.7 Opening A Named File 250
15.7.8 Namespace Initialization 250
15.8 Choosing Initial Prefix Mappings 252
15.8.1 Default Hierarchy And The Null Prefix 253
15.8.2 A Common Name Syntax 254
15.9 Additional File Manipulation Commands 254
15.9.1 Removing A File 254
15.9.2 Renaming A File 256
15.9.3 Testing File Accessibility 257
15.10 Advantages Of The Namespace Approach 257
15.11 The Limits Of Fixed Prefix Patterns 258
15.12 Generalized Patterns 258
15.13 Configuring The Namespace Pseudo-Device 259
15.14 Summary 260
For Further Study 260
Exercises 261

Chapter 16 User Interface Design

16.1 Introduction 263
16.2 What Is A User Interface? 263
16.3 The Definition Of Goodness 264
16.4 What We Seek 264
16.5 Interface Hardware 265
16.5.1 Keyboard Input Hardware 265
16.5.2 Display Hardware 266
16.5.3 Pointing Device 267
16.6 The Two-Tier Interface Model 268
16.7 Syntactic Flexibility 268
16.8 Semantic Features And Issues 269
16.8.1 Command Set 269
16.8.2 Design Principles 269
16.8.3 Concurrent Processing 270
16.8.4 Interprocess Communication 271
16.8.5 I/O And File Specification 271
16.8.6 Response To Requests 271
16.9 Syntactic Features And Issues 272
16.9.1 Lexical Conventions And Quoting 272
16.9.2 Command History And Editing 272
16.9.3 Abbreviations And Command Aliases 273
16.9.4 Command Name Expansion 273
16.9.5 Typed Vs. Untyped Arguments 273
16.9.6 Programming Language Constructs 274
16.9.7 Windows 275
16.10 Modifying The Syntactic Interface 276
16.10.1 Parameterization Vs. Extensibility 277
16.10.2 Multiple Syntactic Interfaces 277
16.11 Summary 278
For Further Study 278
Exercises 279

Chapter 17 An Example User Interface: The Xinu Shell

17.1 Introduction 281
17.2 The Assumed Interface Hardware 281
17.3 A Basic Design Decision 282
17.4 Overview Of Shell Organization And Operation 282
17.4.1 Input Form 282
17.5 Imperative Vs. Interrogative Interaction Form 282
17.5.1 Processes Vs. Procedures 283
17.5.2 File Name Independence 283
17.6 Command Syntax 283
17.6.1 The Definition Of Lexical Tokens 284
17.6.2 The Definition Of Command-Line Syntax 284
17.7 Shell Semantics 285
17.8 Implementation Of The Xinu Shell 286
17.8.1 Shell Definitions 286
17.8.2 Declaration Of Commands 287
17.8.3 Dividing The Command Line Into Tokens 289
17.8.4 The Heart Of The Command Interpreter 291
17.8.5 Command Lookup And Invocation Of Builtins 296
17.8.6 I/O Redirection 296
17.8.7 Passing Arguments To The Command Process 297
17.8.8 Starting A Command In Background 301
17.8.9 Foreground Processing And Command Expansion 301
17.8.10 Moving A Command To Background 302
17.8.11 User Login 303
17.9 Summary 305
For Further Study 305
Exercises 306

Chapter 18 An Example Set Of Shell Commands

18.1 Introduction 309
18.2 Command And Procedure Names 309
18.2.1 Choosing Command Names 309
18.2.2 Choosing Procedure Names 310
18.3 Types Of Commands 310
18.4 Command Implementation 311
18.5 General Information Commands 311
18.5.1 Time And Date Command 311
18.5.2 Help Command 315
18.5.3 Uptime And Ruptime Commands 317
18.6 System Information Commands 320
18.6.1 Bpool Command 320
18.6.2 Devs Command 321
18.6.3 Dg Command 322
18.6.4 Mem Command 323
18.6.5 Netstat Command 325
18.6.6 Ps Command 327
18.6.7 Rf Command 329
18.6.8 Routes Command 330
18.6.9 Who Command 332
18.7 Computational Commands 333
18.7.1 Cat Command 333
18.7.2 Close Command 335
18.7.3 Cp Command 336
18.7.4 Create Command 337
18.7.5 Echo Command 341
18.7.6 Exit And Logout Commands 342
18.7.7 Kill Command 343
18.7.8 Mount Command 344
18.7.9 Mv Command 346
18.7.10 Reboot Command 346
18.7.11 Rm Command 347
18.7.12 Rls Command 348
18.7.13 Sleep Command 350
18.7.14 Snap Command 351
18.7.15 Unmount Command 355
18.8 Summary 355
For Further Study 356
Exercises 356

Chapter 19 Resolving High-Level Machine Names

19.1 Introduction 359
19.2 Naming Machines 359
19.3 Flat Namespace 360
19.4 Hierarchical Names 361
19.5 Distributed Hierarchical Namespace 361
19.6 Subset Authority 362
19.7 Nameservers 362
19.8 Efficient Distributed Name Resolution 363
19.9 Name Abbreviation 364
19.10 The DARPA Domain Name System 364
19.11 Domain Nameservers 365
19.12 DARPA Domain Name Resolution 365
19.13 Pointer Queries And Inverse Mappings 366
19.14 Example Domain Name Resolution Software 366
19.15 Compressed Name Format 369
19.16 Mapping An Internet Address To A Domain Name 369
19.17 Obtaining A Machine Name 372
19.18 Summary 373
For Further Study 373
Exercises 373

Chapter 20 Higher-Level Protocols

20.1 Introduction 375
20.2 Reliable End-To-End Communication 375
20.3 The DARPA Transmission Control Protocol (TCP) 376
20.4 Remote Interactive Computing 377
20.5 DARPA TELNET Protocol 377
20.6 4.2 UNIX Rlogin 378
20.7 File Transport 378
20.8 DARPA File Transport Protocol (FTP) 379
20.9 Mail Transport Protocols 380
20.10 DARPA Simplified Mail Transport Protocol (SMTP) 380
20.11 Protocol Dependencies 380
20.12 Summary 381
For Further Study 381
Exercises 382
Cross-Development Commands 419
System Calls 444
Library Procedures 502
Device Descriptions 529
DARPA ARP and RARP Protocol Format 541
Ethernet Link-Level Protocol Format 542
Xinu Ethernet Downloader (ELOAD) Protocol Format 543
Xinu File Server (FS) Protocol Format 545
DARPA ICMP Protocol Format 546
DARPA IP Protocol Format 547
Xinu PURPLE Downloading Protocol Format 549
DARPA UDP Protocol Format 551

Bibliography

Index



Return to list of Comer's OS books



Return to Comer's homepage