Chapter 1.Introduction 1
1.1 Introduction 1
1.2 Source Code Presentation 1
1.3 History 3
1.4 Application Programming Interfaces 5
1.5 Example Program 5
1.6 System Calls and Library Functions 7
1.7 Network Implementation Overview 9
1.8 Descriptors 10
1.9 Mbufs (Memory Buffers) and Output Processing 15
1.10 Input Processing 19
1.11 Network Implementation Overview Revisited 22
1.12 Interrupt Levels and Concurrency 23
1.13 Source Code Organization 26
1.14 Test Network 28
1.15 Summary 29
Chapter 2.Mbufs:Memory Buffers 31
2.1 Introduction 31
2.2 Code Introduction 36
2.3 Mbuf Definitions 37
mbuf 38
2.4 mbuf Structure 38
2.5 Simple Mbuf Macros and Functions 40
2.6 m_devget and m_pullup Functions 44
2.7 Summary of Mbuf Macros and Functions 51
2.8 Summary of Net/3 Networking Data Structures 54
2.9 m_copy and Cluster Reference Counts 56
2.10 Alternatives 60
2.11 Summary 60
3.1 Introduction 63
Chapter 3.Interface Layer 63
3.2 Code Introduction 64
3.3 ifnet Structure 65
ifnet 67
ifqueue 71
3.4 ifaddr Structure 73
ifaddr 73
3.5 sockaddr Structure 74
osockaddr 75
sockaddr 75
3.6 ifnet and ifaddr Specialization 76
3.7 Network Initialization Overview 77
pdevinit 78
le_softc 80
Structure Definitions 80
arpcom 80
3.8 Ethernet Initialization 80
3.9 SLIP Initialization 82
sl_softc 83
3.10 Loopback Initialization 85
3.11 if_attach Function 85
sockaddr_dl 87
3.12 ifinit Function 93
3.13 Summary 94
Chapter 4.Interfaces:Ethernet 95
4.1 Introduction 95
4.2 Code Introduction 96
4.3 Ethemet Interface 98
ether_header 102
timeval 106
4.4 ioctl System Call 114
ifreq 117
ifconf 117
4.5 Summary 125
5.2 Code Introduction 127
5.1 Introduction 127
Chapter 5.Interfaces:SLIP and Loopback 127
5.3 SLIP Interface 128
5.4 Loopback Interface 150
5.5 Summary 153
Chapter 6.IP Addressing 155
6.1 Introduction 155
6.2 Code Introduction 158
6.3 Interface and Address Summary 158
in_addr 160
sockaddr_in 160
6.4 sockaddr_in Structure 160
6.5 in_ifaddr Structure 161
6.6 Address Assignment 161
in_ifaddr 161
in_aliasreq 174
6.7 Interface ioctl Processing 177
6.8 Internet Utility Functions 181
6.9 ifnet Utility Functions 182
6.10 Summary 183
7.1 Introduction 185
Chapter 7.Domains and Protocols 185
7.2 Code Introduction 186
7.3 domain Structure 187
domain 187
7.4 protosw Structure 188
protosw 188
7.5 IP domain and protosw Structures 191
7.6 pffindproto and pffindtype Functions 196
7.7 pfctlinput Function 198
7.8 IP Initialization 199
7.9 sysctl System Call 201
7.10 Summary 204
Chapter 8.IP:Internet Protocol 205
8.1 Introduction 205
8.2 Code Introduction 206
8.3 IP Packets 210
ip 211
8.4 Input Processing:ipintr Function 212
8.5 Forwarding:ip_forward Function 220
route 220
8.6 Output Processing:ip_output Function 228
8.7 Internet Checksum:in_cksum Function 234
8.8 setsockopt and getsockopt System Calls 239
8.9 ip_sysctl Function 244
8.10 Summary 245
9.2 Code Introduction 247
9.1 Introduction 247
Chapter 9.IP Option Processing 247
9.3 Option Format 248
9.4 ip_dooptions Function 249
9.5 Record Route Option 252
9.6 Source and Record Route Options 254
ip_srcrt 258
9.7 Timestamp Option 261
ip_timestamp 262
ipoption 265
9.8 ip_insertoptions Function 265
9.9 ip_pcbopts Function 269
9.10 Limitations 272
9.11 Summary 272
10.1 Introduction 275
Chapter 10.IP Fragmentation and Reassembly 275
10.2 Code Introduction 277
10.3 Fragmentation 278
10.4 ip_optcopy Function 282
10.5 Reassembly 283
ipq 286
10.6 ip_reass Function 286
ipasfrag 287
10.7 ip_slowtimo Function 298
10.8 Summary 300
Chapter 11.ICMP:Internet Control Message Protocol 301
11.1 Introduction 301
11.2 Code Introduction 305
icmp 308
11.3 icmp Structure 308
11.4 ICMP protosw Structure 309
11.5 Input Processing:icmp_input Function 310
11.6 Error Processing 313
11.7 Request Processing 316
11.8 Redirect Processing 321
11.9 Reply Processing 323
11.10 Output Processing 324
11.11 icmp_error Function 324
11.12 icmp_reflect Function 328
11.13 icmp_send Function 333
11.14 icmp_sysctl Function 334
11.15 Summary 335
12.1 Introduction 337
Chapter 12.IP Multicasting 337
12.2 Code Introduction 340
12.3 Ethernet Multicast Addresses 341
ether_multi 342
12.4 ether_multi Structure 342
12.5 Ethernet Multicast Reception 344
12.6 in_multi Structure 345
in_multi 345
ip_moptions 347
12.7 ip_moptions Structure 347
12.8 Multicast Socket Options 348
12.9 Multicast TTL Values 348
12.10 ip_setmoptions Function 351
12.11 Joining an IP Multicast Group 355
ip_mreq 356
12.12 Leaving an IP Multicast Group 366
12.13 ip_getmoptions Function 371
12.14 Multicast Input Processing:ipintr Function 373
12.15 Multicast Output Processing:ip_output Function 375
12.16 Performance Considerations 379
12.17 Summary 379
Chapter 13.IGMP:Internet Group Management Protocol 381
13.1 Introduction 381
13.2 Code Introduction 382
igmp 384
13.3 igmp Structure 384
13.4 IGMP protosw Structure 384
13.5 Joining a Group:igmp_joingroup Function 386
13.6 igmp_fasttimo Function 387
13.7 Input Processing:igmp_input Function 391
13.8 Leaving a Group:igmp_leavegroup Function 395
13.9 Summary 396
Chapter 14.IP Multicast Routing 397
14.1 Introduction 397
14.2 Code Introduction 398
14.3 Multicast Output Processing Revisited 399
14.4 mrouted Daemon 401
14.5 Virtual Interfaces 404
vif 406
vifctl 407
14.6 IGMP Revisited 411
lgrplctl 411
14.7 Multicast Routing 416
mrt 419
mrtctl 420
14.8 Multicast Forwarding:ip_mforward Function 424
14.9 Cleanup:ip_mrouter_done Function 433
14.10 Summary 434
Chapter 15.Socket Layer 435
15.1 Introduction 435
15.2 Code Introduction 436
15.3 socket Structure 437
socket 438
15.4 System Calls 441
sysent 443
socket_args 444
15.5 Processes,Descriptors,and Sockets 445
15.6 socket System Call 447
15.7 getsock and sockargs Functions 451
15.8 bind System Call 453
15.9 listen System Call 455
15.10 tsleep and wakeup Functions 456
15.11 accept System Call 457
15.12 sonewconn and soisconnected Functions 461
15.13 connect System call 464
15.14 shutdown System Call 468
15.15 close System Call 471
15.16 Summary 474
Chapter 16.Socket I/O 475
16.1 Introduction 475
16.2 Code Introduction 475
sockbuf 476
16.3 Socket Buffers 476
16.4 write,writev,sendto,and sendmsg System Calls 480
iovec 481
cmsghdr 482
msghdr 482
16.5 sendmsg System Call 483
uio 485
16.6 sendit Function 485
16.7 sosend Function 489
16.8 read,readv,recvfrom,and recvmsg System Calls 500
16.9 recvmsg System Call 501
16.10 recvit Function 503
16.11 soreceive Function 505
16.12 soreceive Code 510
16.13 select System Call 524
selinfo 531
16.14 Summary 534
Chapter 17.Socket Options 537
17.1 Introduction 537
17.2 Code Introduction 538
17.3 setsockopt System Call 539
linger 542
17.4 getsockopt System Call 545
17.5 fcntl and ioctl System Calls 548
17.6 getsockname System Call 554
17.7 getpeername System Call 554
17.8 Summary 557
Chapter 18.Radix Tree Routing Tables 559
18.1 Introduction 559
18.2 Routing Table Structure 560
18.3 Routing Sockets 569
18.4 Code Introduction 570
18.5 Radix Node Data Structures 573
radix_node_head 574
radix_node 575
18.6 Routing Structures 578
radix_mask 578
rtentry 579
rt_metrics 580
18.7 Initialization:route_init and rtable_init Functions 581
18.8 Initiallzation:rn_init and rn_inithead Functions 584
18.9 Duplicate Keys and Mask Lists 587
18.10 rn_match Function 591
18.12 Summary 599
18.11 rn_search Function 599
Chapter 19.Routing Requests and Routing Messages 601
19.1 Introduction 601
19.2 rtalloc and rtallocl Functions 601
19.3 RTFREE Macro and rtfree Function 604
19.4 rtrequest Function 607
19.5 rt_setgate Function 612
19.6 rtinit Function 615
19.7 rtredirect Function 617
19.8 Routing Message Structures 621
if_msghdr 622
ifa_msghdr 622
rt_msghdr 622
rt_addrinfo 623
route_cb 625
19.9 rt_missmsg Function 625
sockproto 626
19.10 rt_ifmsg Function 627
19.11 rt_newaddrmsg Function 628
19.12 rt_msg1 Function 630
walkarg 632
19.13 rt_msg2 Function 632
19.14 sysctl_rtable Function 635
19.15 sysctl_dumpentry Function 640
19.16 sysctl_iflist Function 642
19.17 Summary 644
Chapter 20.Routing Sockets 645
20.1 Introduction 645
20.2 routedomain and protosw Structures 646
20.4 raw_init Function 647
rawcb 647
20.3 Routing Control Blocks 647
20.5 route_output Function 648
20.6 rt_xaddrs Function 660
20.7 rt_setmetrics Function 661
20.8 raw_input Function 662
20.9 route_usrreq Function 664
20.10 raw_usrreq Function 666
20.11 raw_attach,raw_detach,and raw_disconnect Function 671
20.12 Summary 672
Chapter 21.ARP:Address Resolution Protocol 675
21.1 Introduction 675
21.2 ARP and the Routing Table 675
21.3 Code Introduction 678
21.4 ARP Structures 681
ether_arp 682
arphdr 682
llinfo_arp 682
21.5 arpwhohas Function 683
21.6 arprequest Function 684
21.7 arpintr Function 687
21.8 in_arpinput Function 688
21.9 ARP Timer Functions 694
21.10 arpresolve Function 696
21.11 arplockup Function 701
sockaddr_inarp 701
21.12 Proxy ARP 703
21.13 arp_rtrequest Function 704
21.14 ARP and Multicasting 710
21.15 Summary 711
Chapter 22.Protocol Control Blocks 713
22.1 Introduction 713
22.2 Code Introduction 715
inpcb 716
22.3 inpcb Structure 716
22.4 in_pcballoc and in_pcbdetach Functions 717
22.5 Binding,Connecting,and Demultiplexing 719
22.6 in_pcblookup Function 724
22.7 in_pcbbind Function 728
22.8 in_pcbconnect Function 735
22.9 in_pcbdisconnect Function 741
22.10 in_setsockaddr and in_setpeeraddr Functions 741
22.11 in_pcbnotify,in_rtchange,and in_losing Functions 742
22.12 Implementation Refinements 750
22.13 Summary 751
Chapter 23.UDP:User Datagram Protocol 755
23.1 Introduction 755
23.2 Code Introduction 755
23.3 UDP protosw Structure 758
udphdr 759
23.4 UDP Header 759
udpiphdr 759
ipovly 760
23.6 udp_output Function 760
23.5 udp_init Function 760
23.7 udp_input Function 769
23.8 udp_saveopt Function 781
23.9 udp_ctlinput Function 782
23.10 udp_usrreq Function 784
23.11 udp_sysctl Function 790
23.12 Implementation Refinements 791
23.13 Summary 793
Chapter 24.TCP:Transmission Control Protocol 795
24.1 Introduction 795
24.2 Code Introduction 795
24.3 TCP protosw Structure 801
24.4 TCP Header 801
tcphdr 801
24.5 TCP Control BLock 803
tcpiphdr 803
tcpcb 804
24.6 TCP State Transition Diagram 805
24.7 TCP Sequence Numbers 807
24.8 tcp_init Function 812
24.9 Summary 815
Chapter 25.TCP Timers 817
25.1 Introduction 817
25.2 Code Introduction 819
25.3 tcp_cancelzimers Function 821
25.4 tcp_fasttimo Function 821
25.5 tcp_slowt imo Function 822
25.6 tcp_timers Function 824
25.7 Retransmission Timer Calculations 831
25.8 tcp_newtcpcb Function 833
25.9 tcp_setpersist Function 835
25.10 tcp_xmit_timcr Function 836
25.11 Retransmission Timeout:tcp_Limers Function 841
25.12 An RTT Example 846
25.13 Summary 848
Chapter 26.TCP Output 851
26.1 Introduction 851
26.2 tcp_output Overview 852
26.3 Determine if a Segment Should be Sent 852
26.4 TCP Options 864
26.6 Timestamp Option 866
26.5 Window Scale Option 866
26.7 Send a Segment 871
26.8 tcp_template Function 884
26.9 tcp_respond Function 885
26.10 Summary 888
Chapter 27.TCP Functions 891
27.1 Introduction 891
27.3 tcp_drop Function 892
27.2 tcp_drain Function 892
27.4 tcp_close Function 893
27.5 tcp_mss Function 897
27.7 tcp_notify Function 904
27.6 tcp_ctlinput Function 904
27.8 tcp_quench Function 906
27.9 TCP_REASS Macro and tcp_reass Function 906
tcp_debug 916
27.10 tcp_trace Function 916
27.11 Summary 920
Chapter 28.TCP Input 923
28.1 Introduction 923
28.2 Preliminary Processing 925
28.3 tcp_dooptions Function 933
28.4 Header Prediction 934
28.5 TCP Input:Slow Path Processing 941
28.6 Initiation of Passive Open,Completion of Active Open 942
28.7 PAWS:Protection Against Wrapped Sequence Numbers 951
28.8 Trim Segment so Data is Within Window 954
28.9 Self-Connects and Simultaneous Opens 960
28.10 Record Timestamp 963
28.11 RST Processing 963
28.12 Summary 965
Chapter 29.TCP Input (Continued) 967
29.1 Introduction 967
29.2 ACK Processing Overview 967
29.3 Completion of Passive Opens and Simultaneous Opens 967
29.4 Fast Retransmit and Fast Recovery Algorithms 970
29.5 ACK Processing 974
29.6 Update Window Information 981
29.7 Urgent Mode Processing 983
29.8 tcp_pulloutofband Function 986
29.9 Processing of Received Data 988
29.10 FIN Processing 990
29.11 Final Processing 992
29.12 Implementation Refinements 994
29.13 Header Compression 995
29.14 Summary 1004
Chapter 30.TCP User Requests 1007
30.1 Introduction 1007
30.2 tcp_usrreq Function 1007
30.3 tcp_attach Function 1018
30.4 tcp_disconnect Function 1019
30.5 tcp_usrclosed Function 1021
30.6 tcp_ctloutput Function 1022
30.7 Summary 1025
31.1 Introduction 1027
Chapter 31.BPF:DSD Packet Filter 1027
31.2 Code Introduction 1028
31.3 bpf_if Structure 1029
hpf_if 1029
bpf_hdr 1029
31.4 bpf_d Structure 1032
hpf_d 1033
31.5 BPF Input 1040
31.6 BPF Output 1046
31.7 Summary 1047
Chapter 32.Raw IP 1049
32.1 Introduction 1049
32.2 Code Introduction 1050
32.3 Raw IP protosw Structure 1051
32.5 rip_input Function 1053
32.4 rip_init Function 1053
32.6 rip_output Function 1056
32.7 rip_usrreq Function 1058
32.8 rip_ctloutput Function 1063
32.9 Summary 1065
Epilogue 1067
Appendix A.Solutions to Selected Exercises 1069
Appendix B.Source Code Availability 1093
Appendix C.RFC 1122 Compliance 1097
C.1 Link-Layer Requirements 1097
C.2 IP Requirements 1098
C.3 IP Options Requirements 1102
C.4 IP Fragmentation and Reassembly Requirements 1104
C.5 ICMP Requirements 1105
C.6 Multicasting Requirements 1110
C.7 IGMP Requirements 1111
C.8 Routing Requirements 1111
C.9 ARP Requirements 1113
C.10 UDP Requirements 1113
C.11 TCP Requirements 1115
Bibliography 1125
Index 1133