UNIX Systems Programming

Contents

Prefacexvii
 
    I  Fundamentals1
 
1   Technology's Impact on Programs3
1.1   Terminology of Change4
1.2   Time and Speed5
1.3   Multiprogramming and Time Sharing7
1.4   Concurrency at the Applications Level9
1.4.1   Interrupts9
1.4.2   Signals10
1.4.3   Input and Output10
1.4.4   Processes, threads and the sharing of resources11
1.4.5   Multiple processors with shared memory11
1.4.6   The network as the computer12
1.5   Security and Fault Tolerance13
1.6   Buffer Overflows for Breaking and Entering14
1.6.1   Consequences of buffer overflows15
1.6.2   Buffer overflows and security17
1.7   UNIX Standards18
1.8   Additional Reading20
 
2   Programs, Processes and Threads21
2.1   How a Program Becomes a Process22
2.2   Threads and Thread of Execution23
2.3   Layout of a Program Image24
2.4   Library Function Calls26
2.5   Function Return Values and Errors26
2.6   Argument Arrays31
2.6.1   Creating an argument array with makeargv32
2.6.2   Implementation of makeargv34
2.7   Thread-Safe Functions38
2.8   Use of Static Variables40
2.9   Structure of Static Objects42
2.10   Process Environment48
2.11   Process Termination51
2.12   Exercise: An env Utility54
2.13   Exercise: Message Logging55
2.14   Additional Reading56
 
3   Processes in UNIX59
3.1   Process Identification60
3.2   Process State61
3.3   UNIX Process Creation and fork64
3.4   The wait Function71
3.4.1   Status values76
3.5   The exec Function78
3.6   Background Processes and Daemons84
3.7   Critical Sections86
3.8   Exercise: Process Chains87
3.9   Exercise: Process Fans88
3.10   Additional Reading89
 
4   UNIX I/O91
4.1   Device Terminology92
4.2   Reading and Writing92
4.3   Opening and Closing Files102
4.4   The select Function107
4.5   The poll Function116
4.6   File Representation119
4.6.1   File descriptors119
4.6.2   File pointers and buffering122
4.6.3   Inheritance of file descriptors124
4.7   Filters and Redirection128
4.8   File Control132
4.9   Exercise: Atomic Logging135
4.9.1   An atomic logging library138
4.10   Exercise: A cat Utility141
4.11   Additional Reading143
 
5   Files and Directories145
5.1   UNIX File System Navigation146
5.1.1   The current working directory147
5.1.2   Search paths151
5.2   Directory Access152
5.2.1   Accessing file status information154
5.2.2   Determining the type of a file157
5.3   UNIX File System Implementation158
5.3.1   UNIX file implementation158
5.3.2   Directory implementation161
5.4   Hard Links and Symbolic Links162
5.4.1   Creating or removing a link163
5.4.2   Creating or removing a symbolic link168
5.5   Exercise: The which Command173
5.6   Exercise: Biffing174
5.7   Exercise: News biff177
5.8   Exercise: Traversing Directories179
5.9   Additional Reading181
 
6   UNIX Special Files183
6.1   Pipes184
6.2   Pipelines188
6.3   FIFOs192
6.4   Pipes and the Client-Server Model196
6.5   Terminal Control203
6.5.1   Canonical and noncanonical input processing209
6.6   Audio Device214
6.7   Exercise: Audio219
6.8   Exercise: Barriers221
6.9   Exercise: The stty Command223
6.10   Exercise: Client-Server Revisited223
6.11   Additional Reading223
 
7   Project: The Token Ring225
7.1   Ring Topology226
7.2   Ring Formation227
7.3   Ring Exploration234
7.4   Simple Communication236
7.5   Mutual Exclusion with Tokens237
7.6   Mutual Exclusion by Voting238
7.7   Leader Election on an Anonymous Ring239
7.8   Token Ring for Communication241
7.9   Pipelined Preprocessor243
7.10   Parallel Ring Algorithms246
7.10.1   Image filtering246
7.10.2   Matrix multiplication249
7.11   Flexible Ring250
7.12   Additional Reading251
 
II   Asynchronous Events253
 
8   Signals255
8.1   Basic Signal Concepts 256
8.2   Generating Signals 256
8.3   Manipulating Signal Masks and Signal Sets 261
8.4   Catching and Ignoring Signals--- sigaction 267
8.5   Waiting for Signals--- pause, sigsuspend and sigwait 273
8.5.1   The pause function273
8.5.2   The sigsuspend function274
8.5.3   The sigwait function282
8.6   Handling Signals: Errors and Async-signal Safety 283
8.7   Program Control with siglongjmp and sigsetjmp 286
8.8   Programming with Asynchronous I/O 288
8.9   Exercise: Dumping Statistics 299
8.10   Exercise: Spooling a Slow Device 299
8.11   Additional Reading 300
 
9   Times and Timers301
9.1   POSIX Times 302
9.1.1   Expressing time in seconds since the Epoch 302
9.1.2   Displaying date and time 303
9.1.3   Using struct timeval to express time 306
9.1.4   Using realtime clocks 307
9.1.5   Contrasting elapsed time to processor time 311
9.2   Sleep Functions 314
9.3   POSIX:XSI Interval Timers 315
9.4   Realtime Signals 320
9.5   POSIX:TMR Interval Timers 324
9.6   Timer Drift, Overruns and Absolute Time 329
9.7   Additional Reading 339
 
10   Project: Virtual Timers341
10.1   Project Overview 342
10.2   Simple Timers 344
10.3   Setting One of Five Single Timers 347
10.3.1   The virtualtimers object 347
10.3.2   The hardwaretimer object 350
10.3.3   Main program implementation 351
10.3.4   Instrumentation of the timer code with show 351
10.4   Using Multiple Timers 357
10.4.1   Setting multiple timers 358
10.4.2   Testing with multiple timers 361
10.5   A Robust Implementation of Multiple Timers 363
10.6   POSIX:TMR Timer Implementation 367
10.7   mycron,\ a Small Cron Facility 367
10.8   Additional Reading 368
 
11   Project: Cracking Shells369
11.1   Building a Simple Shell 370
11.2   Redirection 374
11.3   Pipelines 376
11.4   Signal Handling in the Foreground 380
11.5   Process Groups, Sessions and Controlling Terminals 386
11.5.1   Process Groups 386
11.5.2   Sessions 388
11.6   Background Processes in ush 391
11.7   Job Control 398
11.8   Job Control for ush 402
11.8.1   A job list object 402
11.8.2   The job list in ush 403
11.8.3   Job control in ush 404
11.8.4   Process behavior in waiting for a pipeline 404
11.9   Additional Reading 405
 
III  Concurrency407
 
12   POSIX Threads409
12.1   A Motivating Problem: Monitoring File Descriptors 410
12.2   Use of Threads to Monitor Multiple File Descriptors 411
12.3   Thread Management 415
12.3.1   Referencing threads by ID 416
12.3.2   Creating a thread 416
12.3.3   Detaching and joining 417
12.3.4   Exiting and cancellation 420
12.3.5   Passing parameters to threads and returning values 422
12.4   Thread Safety 431
12.5   User Threads versus Kernel Threads 433
12.6   Thread Attributes 436
12.6.1   The thread state 437
12.6.2   The thread stack 438
12.6.3   Thread scheduling 439
12.7   Exercise: Parallel File Copy 443
12.8   Additional Reading 444
 
13   Thread Synchronization447
13.1   POSIX Synchronization Functions 448
13.2   Mutex Locks 448
13.2.1   Creating and initializing a mutex 449
13.2.2   Destroying a mutex 450
13.2.3   Locking and unlocking a mutex 451
13.2.4   Protecting unsafe library functions 453
13.2.5   Synchronizing flags and global values 454
13.2.6   Making data structures thread-safe 459
13.3   At-Most-Once and At-Least-Once-Execution 461
13.4   Condition Variables 465
13.4.1   Creating and destroying condition variables 467
13.4.2   Waiting and signaling on condition variables 469
13.5   Signal Handling and Threads 473
13.5.1   Directing a signal to a particular thread 473
13.5.2   Masking signals for threads 474
13.5.3   Dedicating threads for signal handling 475
13.6   Readers and Writers 478
13.7   A strerror_r Implementation 483
13.8   Deadlocks and Other Pesky Problems 483
13.9   Exercise: Multiple Barriers 485
13.10   Additional Reading 486
 
14   Critical Sections and Semaphores487
14.1   Dealing with Critical Sections 488
14.2   Semaphores 491
14.3   POSIX:SEM Unnamed Semaphores 494
14.4   POSIX:SEM Semaphore Operations 496
14.5   POSIX:SEM Named Semaphores 502
14.5.1   Creating and opening named semaphores 502
14.5.2   Closing and unlinking named semaphores 504
14.6   Exercise: License Manager 507
14.6.1   License object 508
14.6.2   The runsim main program 508
14.6.3   Extensions to the license manager 509
14.7   Additional Reading 509
 
15   POSIX IPC511
15.1   POSIX:XSI Interprocess Communication 512
15.1.1   Identifying and accessing IPC objects 512
15.1.2   Accessing POSIX:XSI IPC resources from the shell 513
15.2   POSIX:XSI Semaphore Sets 514
15.2.1   Semaphore creation 515
15.2.2   Semaphore control 517
15.2.3   POSIX semaphore set operations 519
15.3   POSIX:XSI Shared Memory 525
15.3.1   Accessing a shared memory segment 526
15.3.2   Attaching and detaching a shared memory segment 526
15.3.3   Controlling shared memory 527
15.3.4   Shared memory examples 528
15.4   POSIX:XSI Message Queues 535
15.4.1   Accessing a message queue 535
15.5   Exercise: POSIX Unnamed Semaphores 542
15.6   Exercise: POSIX Named Semaphores 543
15.7   Exercise: Implementing Pipes with Shared Memory 544
15.8   Exercise: Implementing Pipes with Message Queues 547
15.9   Additional Reading 548
 
16   Project: Producer Consumer Synchronization549
16.1   The Producer-Consumer Problem 550
16.2   Bounded Buffer Protected by Mutex Locks 551
16.3   Buffer Implementation with Semaphores 555
16.4   Introduction to a Simple Producer-Consumer Problem 560
16.5   Bounded Buffer Implementation Using Condition Variables 564
16.6   Buffers with Done Conditions 565
16.7   Parallel File Copy 573
16.7.1   Parallel file copy producer 573
16.7.2   Parallel file copy consumer 574
16.7.3   Parallel file copy main program 574
16.7.4   Parallel file copy enhancements 575
16.8   Threaded Print Server 575
16.8.1   The request buffer 577
16.8.2   The producer thread 578
16.8.3   The consumer threads 578
16.8.4   The print server 579
16.8.5   Other enhancements 579
16.9   Additional Reading 580
 
17   Project: The Not Too Parallel Virtual Machine581
17.1   PVM History, Terminology, and Architecture 582
17.2   The Not Too Parallel Virtual Machine 584
17.3   NTPVM Project Overview 585
17.3.1   NEWTASK \ packets 589
17.3.2   DATA \ packets 590
17.3.3   DONE \ packets 590
17.4   I/O and Testing of Dispatcher 591
17.4.1   Testing with multiple windows 596
17.4.2   Testing with remote logging 598
17.5   Single Task with No Input 600
17.6   Sequential Tasks 601
17.6.1   The input thread 602
17.6.2   The output thread 603
17.7   Concurrent Tasks 604
17.8   Packet Communication, Broadcast and Barriers 605
17.9   Termination and Signals 605
17.10   Ordered Message Delivery 606
17.11   Additional Reading 606
 
IV   Communication607
 
18   Connection-Oriented Communication609
18.1   The Client-Server Model 610
18.2   Communication Channels 610
18.3   Connection-Oriented Server Strategies 614
18.4   Universal Internet Communication Interface (UICI) 618
18.4.1   Handling errors 620
18.4.2   Reading and writing 620
18.5   UICI Implementations of Different Server Strategies 621
18.6   UICI Clients 624
18.7   Socket Implementation of UICI 629
18.7.1   The socket function 630
18.7.2   The bind function 631
18.7.3   The listen function 633
18.7.4   Implementation of u_open 634
18.7.5   The accept function 635
18.7.6   Implementation of u_accept 636
18.7.7   The connect function 638
18.7.8   Implementation of u_connect 638
18.8   Host Names and IP Addresses 641
18.9   Thread-Safe UICI 649
18.10   Exercise: Ping Server 652
18.11   Exercise: Transmission of Audio 653
18.12   Additional Reading 655
 
19   Project: WWW Redirection657
19.1   The World Wide Web 658
19.2   Uniform Resource Locators (URLs) 658
19.3   HTTP Primer 660
19.3.1   Client requests 660
19.3.2   Server response 662
19.3.3   HTTP message exchange 662
19.4   Web Communication Patterns 665
19.4.1   Tunnels 665
19.4.2   Proxies 667
19.4.3   Caching and Transparency 668
19.4.4   Gateways 670
19.5   Pass-through Monitoring of Single Connections 672
19.6   Tunnel Server Implementation 674
19.7   Server Driver for Testing 675
19.8   HTTP Header Parsing 676
19.9   Simple Proxy Server 679
19.10   Proxy Monitor 680
19.11   Proxy Cache 683
19.12   Gateways as Portals 684
19.13   Gateway for Load Balancing 685
19.14   Postmortem 686
19.14.1   Threading and timing errors 686
19.14.2   Uncaught errors and bad exits 687
19.14.3   Writing style and presentation 687
19.14.4   Poor testing and presentation of results 688
19.14.5   Programming errors and bad style 689
19.15   Additional Reading 690
 
20   Connectionless Communication and Multicast691
20.1   Introduction to Connectionless Communication 692
20.2   Simplified Interface for Connectionless Communication 693
20.2.1   Host names and the u_buf_t structure 695
20.2.2   UICI UDP return errors 695
20.2.3   UDP buffer size and UICI UDP 696
20.3   Simple-Request Protocols 697
20.4   Request-Reply Protocols 702
20.5   Request-Reply with Timeouts and Retries 708
20.6   Request-Reply-Acknowledge Protocols 714
20.7   Implementation of UICI UDP 715
20.7.1   Implementation of u_openudp 715
20.7.2   The sendto function 717
20.7.3   Implementation of u_sendto and u_sendtohost 718
20.7.4   The recvfrom function 719
20.7.5   Implementation of u_recvfrom and u_recvfromtimed 720
20.7.6   Host names and u_buf_t 722
20.8   Comparison of UDP and TCP 724
20.9   Multicast 725
20.9.1   Multicast Addressing 725
20.9.2   Implementation of u_join 728
20.9.3   Implementation of u_leave 728
20.10   Exercise: UDP Port Server 729
20.11   Exercise: Stateless File Server 730
20.11.1   Remote File Services 731
20.12   Additional Reading 732
 
21   Project: Internet Radio733
21.1   Project Overview 734
21.2   Audio Device Simulation 735
21.3   UDP Implementation with One Program and One Receiver 735
21.3.1   Simple implementation 736
21.3.2   Termination of the receiver 739
21.3.3   Buffering by the receiver to handle network latency 740
21.3.4   Buffering by the receiver to handle out-of-order delivery 743
21.4   UDP Implementation with Multiple Programs and Receivers 746
21.4.1   Multiple programs and one receiver 746
21.4.2   Multiple programs and multiple receivers 747
21.5   UDP Implementation of Radio Broadcasts 747
21.6   Multicast Implementation of Radio Broadcasts 750
21.7   TCP Implementation Differences 750
21.7.1   TCP implementation of one program and one receiver 751
21.7.2   TCP implementation of multiple programs with one receiver 752
21.7.3   TCP implementation of radio broadcasts 753
21.8   Receiving Streaming Audio Through a Browser 755
21.8.1   Using browser helper applications 755
21.8.2   Setting a new mime type in your web server 757
21.8.3   Setting your browser to handle a new mime type 758
21.8.4   Creating a web page 758
21.8.5   Using a predefined mime type 758
21.9   Additional Reading 759
 
22   Project: Server Performance761
22.1   Server Performance Costs 762
22.2   Server Architectures 762
22.3   Project Overview 767
22.4   Single-Client Driver 767
22.4.1   Processing a connection 768
22.4.2   Programming the response 768
22.4.3   Gathering statistics 769
22.4.4   Testing the client 770
22.5   Multiple-Client Driver 771
22.5.1   Alternative multiple-client design 773
22.6   Thread-per-request and Process-per-request Implementations 774
22.7   Thread-worker-pool Strategy 774
22.8   Thread-worker Pool with Bounded Buffer 775
22.9   Process-worker Pool 775
22.10   Influence of Disk I/O 776
22.11   Performance Studies 780
22.11.1   Baseline measurements 780
22.11.2   Sources of variability 781
22.11.3   Measurement errors 782
22.11.4   Synchronization 784
22.11.5   Just plain errors 785
22.11.6   What to measure? 787
22.11.7   Data analysis and presentation 789
22.12   Report Writing 790
22.12.1   Introduction 790
22.12.2   Design, implementation and testing 790
22.12.3   Experiments 791
22.12.4   Results and analysis 791
22.12.5   Conclusion 792
22.12.6   Bibliography 792
22.13   Additional Reading 792
 
Appendices795
 
A   UNIX Fundamentals797
A.1   Manual Pages 797
A.2   Compilation 800
A.2.1   Header files 802
A.2.2   Linking and libraries 804
A.2.3   Macros and conditional compilation 805
A.3   Makefiles 807
A.4   Debugging Aids 809
A.4.1   The lint utility 809
A.4.2   Debuggers 810
A.4.3   The truss utility 811
A.4.4   Profilers 812
A.5   Identifiers, Storage Classes and Linkage Classes 812
A.6   Additional Reading 814
 
B   Restart Library815
 
C   UICI Implementation825
C.1   Connection-Oriented UICI TCP Implementation 825
C.2   Name Resolution Implementations 829
C.2.1   Implementation with gethostbyaddr and gethostbyname    830
C.2.2   Reentrant versions of name resolution functions 830
C.2.3   Reentrant name resolution with mutex locks 831
C.3   Connectionless UICI UDP Implementation 834
 
D   Logging Functions841
D.1   Local Atomic Logging 841
D.2   Remote Logging 846
D.2.1   Use of the remote logging facility 855
D.2.2   Implementation details 857
 
E   POSIX Extensions859
 
Bibliography861
 
Program Index871
 
Index875