Home Page Icon
Home Page
Table of Contents for
A. Solutions to Selected Exercises
Close
A. Solutions to Selected Exercises
by W. Richard Stevens, Gary R. Wright
TCP/IP Illustrated
TCP/IP Illustrated, Volume 2
Addison-Wesley Professional Computing Series
Preface
Introduction
Organization of the Book
Intended Audience
Source Code Copyright
Acknowledgments
Structure Definitions
Function and Macro Definitions
1. Introduction
1.1. Introduction
1.1. Introduction
1.2. Source Code Presentation
Set congestion window to one segment
Typographical Conventions
1.3. History
1.4. Application Programming Interfaces
1.5. Example Program
Create a datagram socket
Fill in sockaddr_in structure with server’s address
Send datagram to server
Read datagram returned by server
1.6. System Calls and Library Functions
1.7. Network Implementation Overview
1.8. Descriptors
1.9. Mbufs (Memory Buffers) and Output Processing
Mbuf Containing Socket Address Structure
Mbuf Containing Data
Prepending IP and UDP Headers
IP Output
Ethernet Output
Summary of UDP Output
1.10. Input Processing
Ethernet Input
IP Input
UDP Input
Process Input
1.11. Network Implementation Overview Revisited
1.12. Interrupt Levels and Concurrency
1.13. Source Code Organization
1.14. Test Network
1.15. Summary
1.15. Summary
Exercises
2. Mbufs: Memory Buffers
2.1. Introduction
2.1. Introduction
2.2. Code Introduction
Global Variables
Statistics
Kernel Statistics
2.3. Mbuf Definitions
2.4. mbuf Structure
2.5. Simple Mbuf Macros and Functions
m_get Function
MGET Macro
m_retry Function
Mbuf Locking
2.6. m_devget and m_pullup Functions
m_devget Function
mtod and dtom Macros
m_pullup Function and Contiguous Protocol Headers
m_pullup and IP Fragmentation and Reassembly
Avoidance of m_pullup by TCP Reassembly
Summary of m_pullup Usage
2.7. Summary of Mbuf Macros and Functions
2.8. Summary of Net/3 Networking Data Structures
2.9. m_copy and Cluster Reference Counts
2.10. Alternatives
2.11. Summary
2.11. Summary
Exercises
3. Interface Layer
3.1. Introduction
3.1. Introduction
3.2. Code Introduction
Global Variables
SNMP Variables
3.3. ifnet Structure
Common interface information
Interface timer
BSD Packet Filter
Interface characteristics
Interface statistics
Change timestamp
Interface functions
3.4. ifaddr Structure
3.5. sockaddr Structure
sockaddr structure
osockaddr structure
3.6. ifnet and ifaddr Specialization
3.7. Network Initialization Overview
3.8. Ethernet Initialization
le_softc structure
arpcom structure
Copy the hardware address from the device
Initialize the ifnet structure
3.9. SLIP Initialization
3.10. Loopback Initialization
3.11. if_attach Function
Resize ifnet_addrs array if necessary
Create link-level name and compute size of link-level address
The address
The mask
ether_ifattach function
3.12. ifinit Function
3.13. Summary
3.13. Summary
Exercises
4. Interfaces: Ethernet
4.1. Introduction
4.1. Introduction
4.2. Code Introduction
Global Variables
Statistics
SNMP Variables
4.3. Ethernet Interface
leintr Function
leread Function
ether_input Function
Broadcast and multicast recognition
Link-level demultiplexing
Queue the packet
ether_output Function
Host route
Gateway route
Avoid ARP flooding
IP output
Explicit Ethernet output
Unrecognized address families
Ethernet header
lestart Function
Interface must be initialized
Dequeue frame from output queue
Transmit frame and pass to BPF
Repeat if device is ready for more frames
Mark device as busy
4.4. ioctl System Call
ifioctl Function
ifconf Function
Example
Generic Interface ioctl commands
SIOCGIFFLAGS and SIOCGIFMETRIC
SIOCSIFFLAGS
Ignore IFF_CANTCHANGE flags
SIOCSIFMETRIC
if_down and if_up Functions
Ethernet, SLIP, and Loopback
4.5. Summary
4.5. Summary
Exercises
5. Interfaces: SLIP and Loopback
5.1. Introduction
5.1. Introduction
5.2. Code Introduction
Global Variables
Statistics
5.3. SLIP Interface
The SLIP Line Discipline: SLIPDISC
SLIP Initialization: slopen and slinit
SLIP Input Processing: slinput
SLIP Output Processing: sloutput
slstart Function
SLIP Packet Loss
SLIP Performance Considerations
slclose Function
sltioctl Function
5.4. Loopback Interface
5.5. Summary
5.5. Summary
Exercises
6. IP Addressing
6.1. Introduction
6.1. Introduction
IP Addresses
Typographical Conventions for IP Addresses
Hosts and Routers
6.2. Code Introduction
Global Variables
6.3. Interface and Address Summary
6.4. sockaddr_in Structure
6.5. in_ifaddr Structure
6.6. Address Assignment
ifioctl Function
in_control Function
Preconditions: SIOCSIFADDR, SIOCSIFNETMASK, and SIOCSIFDSTADDR
Superuser only
Allocate structure
Initialize structure
Address Assignment: SIOCSIFADDR
in_ifinit Function
Assign address and notify hardware
Ethernet configuration
Discard previous routes
Construct network mask and default subnetmask
Construct network and subnetwork numbers
Establish route for host or network
Join all-hosts group
Network Mask Assignment: SIOCSIFNETMASK
Destination Address Assignment: SIOCSIFDSTADDR
Retrieving Interface Information
Multiple IP Addresses per Interface
Additional IP Addresses: SIOCAIFADDR
Deleting IP Addresses: SIOCDIFADDR
6.7. Interface ioctl Processing
leioctl Function
Unrecognized commands
slioctl Function
Unrecognized commands
loioctl Function
Unrecognized commands
6.8. Internet Utility Functions
6.9. ifnet Utility Functions
6.10. Summary
6.10. Summary
Exercises
7. Domains and Protocols
7.1. Introduction
7.1. Introduction
7.2. Code Introduction
Global Variables
Statistics
7.3. domain Structure
7.4. protosw Structure
7.5. IP domain and protosw Structures
domaininit Function
7.6. pffindproto and pffindtype Functions
Example
7.7. pfctlinput Function
7.8. IP Initialization
Internet Transport Demultiplexing
ip_init Function
7.9. sysctl System Call
net_sysctl Function
7.10. Summary
7.10. Summary
Exercises
8. IP: Internet Protocol
8.1. Introduction
8.1. Introduction
8.2. Code Introduction
Global Variables
Statistics
SNMP Variables
8.3. IP Packets
8.4. Input Processing: ipintr Function
ipintr Overview
Verification
IP version
IP checksum
Byte ordering
Packet length
To Forward or Not To Forward?
Option processing
Final destination?
Forwarding
Reassembly and Demultiplexing
Transport demultiplexing
8.5. Forwarding: ip_forward Function
Is packet eligible for forwarding?
Decrement TTL
Locate next hop
Redirect Messages
Leaving on receiving interface?
Send redirect?
Select appropriate router
Forward packet
Send ICMP error?
8.6. Output Processing: ip_output Function
Header Initialization
Construct IP header
Packet already includes header
Route Selection
Verify cached route
Bypass routing
Locate route
Source Address Selection and Fragmentation
Select source address
Send packet
Fragment packet
Cleanup
8.7. Internet Checksum: in_cksum Function
Loop unrolling
More Optimizations
8.8. setsockopt and getsockopt System Calls
PRCO_SETOPT Processing
PRCO_GETOPT Processing
8.9. ip_sysctl Function
8.10. Summary
8.10. Summary
Exercises
9. IP Option Processing
9.1. Introduction
9.1. Introduction
9.2. Code Introduction
Global Variables
Statistics
9.3. Option Format
9.4. ip_dooptions Function
EOL and NOP processing
Source route forwarding
Error handling
9.5. Record Route Option
Record address
ip_rtaddr Function
Check IP forwarding cache
Locate route
Return route information
9.6. Source and Record Route Options
End of source route
Update packet for next hop
Multicast destinations
save_rte Function
ip_srcroute Function
Allocate mbuf for source route
9.7. Timestamp Option
Timestamp only
Timestamp and address
Timestamp at prespecified addresses
Insert timestamp
iptime Function
9.8. ip_insertoptions Function
9.9. ip_pcbopts Function
Discard previous options
Make room for first-hop destination
Scan option list
Rearrange LSRR or SSRR option
Cleanup
9.10. Limitations
9.11. Summary
9.11. Summary
Exercises
10. IP Fragmentation and Reassembly
10.1. Introduction
10.1. Introduction
10.2. Code Introduction
Global Variables
Statistics
10.3. Fragmentation
10.4. ip_optcopy Function
10.5. Reassembly
10.6. ip_reass Function
Create reassembly list
Reassembly timeout
Datagram identifiers
Reconstruct datagram header
Compute packet length
10.7. ip_slowtimo Function
ip_drain Function
10.8. Summary
10.8. Summary
Exercises
11. ICMP: Internet Control Message Protocol
11.1. Introduction
11.1. Introduction
11.2. Code Introduction
Global Variables
Statistics
SNMP Variables
11.3. icmp Structure
11.4. ICMP protosw Structure
11.5. Input Processing: icmp_input Function
Static structures
Validate message
Verify checksum
Verify type
Raw ICMP input
11.6. Error Processing
11.7. Request Processing
Echo Query: ICMP_ECHO and ICMP_ECHOREPLY
Timestamp Query: ICMP_TSTAMP and ICMP_TSTAMPREPLY
Address Mask Query: ICMP_MASKREQ and ICMP_MASKREPLY
Select subnet mask
Convert to reply
Select destination address
Information Query: ICMP_IREQ and ICMP_IREQREPLY
Router Discovery: icmp_routeradvert and icmp_routersolicit
11.8. Redirect Processing
Validate
Update routes
11.9. Reply Processing
11.10. Output Processing
11.11. icmp_error Function
11.12. icmp_reflect Function
Set destination address
Select source address
Get reversed source route
Add record route and timestamp options
Remove original options
Send message and cleanup
11.13. icmp_send Function
11.14. icmp_sysctl Function
11.15. Summary
11.15. Summary
Exercises
12. IP Multicasting
12.1. Introduction
12.1. Introduction
Well-Known IP Multicast Groups
12.2. Code Introduction
Global Variables
Statistics
12.3. Ethernet Multicast Addresses
IP to Ethernet Multicast Address Mapping
IP to Ethernet multicast mapping
12.4. ether_multi Structure
Ethernet multicast addresses
Ethernet multicast lookups
12.5. Ethernet Multicast Reception
12.6. in_multi Structure
IP multicast addresses
IP multicast lookups
12.7. ip_moptions Structure
Multicast options
12.8. Multicast Socket Options
12.9. Multicast TTL Values
The MBONE
Expanding-Ring Search
12.10. ip_setmoptions Function
Construct the defaults
Process options
Discard structure if defaults are OK
Selecting an Explicit Multicast Interface: IP_MULTICAST_IF
Validation
Select the default interface
Selecting an Explicit Multicast TTL: IP_MULTICAST_TTL
Validate and select the default TTL
Selecting Multicast Loopbacks: IP_MULTICAST_LOOP
Validate and select the loopback policy
12.11. Joining an IP Multicast Group
Validation
Locate the interface
Already a member?
Join the group
in_addmulti Function
Already a member
Update the in_multi list
Update the interface and announce the change
slioctl and loioctl Functions: SIOCADDMULTI and SIOCDELMULTI
leioctl Function: SIOCADDMULTI and SIOCDELMULTI
ether_addmulti Function
Initialize address range
Already receiving
Update ether_multi list
12.12. Leaving an IP Multicast Group
Validation
Delete membership references
in_delmulti Function
Update in_multi structure
ether_delmulti Function
Locate ether_multi structure
Delete ether_multi structure
12.13. ip_getmoptions Function
Copy the option data and return
12.14. Multicast Input Processing: ipintr Function
Forward packets if configured as multicast router
12.15. Multicast Output Processing: ip_output Function
Establish defaults
Select source address
Loopback or not?
Forward or not?
Transmit or not?
Send packet
ip_mloopback Function
Duplicate and queue packet
12.16. Performance Considerations
12.17. Summary
12.17. Summary
Exercises
13. IGMP: Internet Group Management Protocol
13.1. Introduction
13.1. Introduction
13.2. Code Introduction
Global Variables
Statistics
SNMP Variables
13.3. igmp Structure
13.4. IGMP protosw Structure
13.5. Joining a Group: igmp_joingroup Function
13.6. igmp_fasttimo Function
igmp_sendreport Function
13.7. Input Processing: igmp_input Function
Validate IGMP message
Pass IGMP messages to raw IP
Membership Query: IGMP_HOST_MEMBERSHIP_QUERY
Membership Report: IGMP_HOST_MEMBERSHIP_REPORT
13.8. Leaving a Group: igmp_leavegroup Function
13.9. Summary
13.9. Summary
Exercises
14. IP Multicast Routing
14.1. Introduction
14.1. Introduction
14.2. Code Introduction
Global Variables
Statistics
SNMP Variables
14.3. Multicast Output Processing Revisited
14.4. mrouted Daemon
14.5. Virtual Interfaces
Virtual Interface Table
add_vif Function
Validate index
Locate physical interface
Configure tunnel interface
Configure physical interface
Save multicast information
del_vif Function
Validate index
Delete interface
Adjust interface count
14.6. IGMP Revisited
add_lgrp Function
Validate add request
If needed, expand group array
Add new group
del_lgrp Function
Validate interface index
Update lookup cache
Delete group
grplst_member Function
Check the cache
Search the membership array
14.7. Multicast Routing
Multicast Routing Table
del_mrt Function
Find route entry
Delete route entry
add_mrt Function
Update existing route
Allocate new route
mrtfind Function
Check route lookup cache
Check the hash table
14.8. Multicast Forwarding: ip_mforward Function
Arrival on physical interface
Arrival on a tunnel
Delete tunnel options
Expired TTL or local multicast
No route available
Arrived on unexpected interface
phyint_send Function
tunnel_send Function
Will the tunnel options fit?
Duplicate the datagram and allocate mbuf for new header and tunnel options
Modify IP header
Construct tunnel options
Send the tunneled datagram
14.9. Cleanup: ip_mrouter_done Function
14.10. Summary
14.10. Summary
Exercises
15. Socket Layer
15.1. Introduction
15.1. Introduction
splnet Processing
15.2. Code Introduction
Global Variables
15.3. socket Structure
SS_NBIO and SS_ASYNC Flags
15.4. System Calls
Example
System Call Summary
15.5. Processes, Descriptors, and Sockets
15.6. socket System Call
socreate Function
Find protocol switch table
Allocate and initialize socket structure
PRU_ATTACH request
Cleanup and return
Superuser Privileges
15.7. getsock and sockargs Functions
15.8. bind System Call
sobind Function
15.9. listen System Call
solisten Function
15.10. tsleep and wakeup Functions
Example
15.11. accept System Call
Validate arguments
Wait for a connection
Asynchronous errors
Associate socket with descriptor
Protocol processing
soaccept Function
15.12. sonewconn and soisconnected Functions
Limit incoming connections
Allocate new socket
Queue connection
Protocol processing
Wakeup processes
Queue incomplete connections
Wakeup processes waiting for new connection
15.13. connect System call
Start connection processing
Wait for connection establishment
soconnect Function
Breaking a Connectionless Association
15.14. shutdown System Call
soshutdown and sorflush
Release control mbufs
15.15. close System Call
soo_close Function
soclose Function
Discard pending connections
Break established connection or association
Release data structures
Return if socket still in use
Remove from connection queues
Discard send and receive queues
15.16. Summary
15.16. Summary
Exercises
16. Socket I/O
16.1. Introduction
16.1. Introduction
16.2. Code Introduction
Global Variables
16.3. Socket Buffers
Socket Macros and Functions
16.4. write, writev, sendto, and sendmsg System Calls
Example
16.5. sendmsg System Call
Copy iov array
sendit and cleanup
16.6. sendit Function
uiomove Function
Example
sendit Code
Initialize auio
Copy address and control information from the process
Send data and cleanup
16.7. sosend Function
Reliable Protocol Buffering
Unreliable Protocol Buffering
sosend Code
Lock send buffer
Check for space
Use data from top
Copy data from process
Pass data to the protocol
Cleanup
Compute transfer size and semantics
If requested, disable routing
Compute available space
Enforce message size limit
Wait for more space?
Wait for space
Allocate packet header or standard mbuf
If possible, use a cluster
Prepare the mbuf
Get data from the process
Fill another buffer?
sosend Summary
Performance Considerations
16.8. read, readv, recvfrom, and recvmsg System Calls
16.9. recvmsg System Call
Copy iov array
recvit and cleanup
16.10. recvit Function
Call soreceive
Copy address and control information to the process
Cleanup
16.11. soreceive Function
Out-of-Band Data
Example
Other Receive Options
Receive Buffer Organization: Message Boundaries
Receive Buffer Organization: No Message Boundaries
Control Information and Out-of-band Data
16.12. soreceive Code
If necessary, wait for data
Process address and control information
Setup data transfer
Mbuf data transfer loop
Cleanup
Receive OOB data
Connection confirmation
Can the call be satisfied now?
Wait for more data?
Yes, wait for more data
dontblock
Return address information
Return control information
Prepare to transfer data
Check for transition between OOB and regular data
Update OOB mark
Finished with mbuf?
More data to process
Update OOB mark
End of logical record
MSG_WAITALL
Error or no more data will arrive
Wait for data to arrive
Synchronize m and nextrecord with receive buffer
Process next mbuf
Truncated message
End of record processing
Nothing transferred
Analysis
16.13. select System Call
Validation and setup
Copy file descriptor sets from process
Setup timeout value
Scan file descriptors
Error or some descriptors are ready
Timeout expired?
Status changed during selscan
Wait for buffer changes
Ready to return
selscan Function
Locate descriptors to be monitored
Poll descriptor
Descriptor is ready
soo_select Function
Is socket readable?
Is socket writeable?
Are there any exceptional conditions pending?
selrecord Function
Already selecting on this descriptor
Select collision with another process?
No collision
selwakeup Function
Wake all processes during a collision
16.14. Summary
16.14. Summary
Exercises
17. Socket Options
17.1. Introduction
17.1. Introduction
17.2. Code Introduction
Global Variables and Statistics
17.3. setsockopt System Call
sosetopt Function
17.4. getsockopt System Call
sogetopt Function
17.5. fcntl and ioctl System Calls
fcntl Code
ioctl Code
17.6. getsockname System Call
17.7. getpeername System Call
17.8. Summary
17.8. Summary
Exercises
18. Radix Tree Routing Tables
18.1. Introduction
18.1. Introduction
18.2. Routing Table Structure
Example—Host Match
Example—Host Match
Example—Network Match
Example—Default Match
Example—Network Match with Backtracking
Example—Backtracking Multiple Levels
Example—Host Match with Backtracking and Cloning
The Big Picture
18.3. Routing Sockets
18.4. Code Introduction
Global Variables
Statistics
SNMP Variables
18.5. Radix Node Data Structures
18.6. Routing Structures
18.7. Initialization: route_init and rtable_init Functions
18.8. Initialization: rn_init and rn_inithead Functions
Determine max_keylen
Allocate and initialize rn_zeros, rn_ones, and maskedKey
Initialize tree of masks
18.9. Duplicate Keys and Mask Lists
18.10. rn_match Function
Go down the tree to the corresponding leaf
Check for exact match
Explicit check for default
18.11. rn_search Function
18.12. Summary
18.12. Summary
Exercises
19. Routing Requests and Routing Messages
19.1. Introduction
19.1. Introduction
19.2. rtalloc and rtalloc1 Functions
Call rn_match
Search fails
Create clone entries
Clone creation fails
Check for external resolution
Increment reference count for normal successful search
19.3. RTFREE Macro and rtfree Function
Release interface reference
Release routing memory
Routing Table Reference Counts
19.4. rtrequest Function
Delete from routing tree
Remove reference to gateway routing table entry
Call interface request function
Return pointer or release reference
Locate corresponding interface
Allocate memory for routing table entry
Allocate and copy gateway address
Copy destination address
Add entry to routing tree
Store interface pointers
Copy metrics for newly cloned route
Call interface request function
Return pointer and increment reference count
Example: Cloned Routes with Network Masks
19.5. rt_setgate Function
Set lengths from socket address structures
Allocate memory
Use memory already allocated for key and gateway
Copy new gateway
Copy key from old memory to new memory
Release gateway routing pointer
Locate and store new gateway routing pointer
19.6. rtinit Function
Get destination address for route
Mask network address with network mask
Search for routing table entry
Process request
Generate routing message on successful delete
Successful add
Incorrect interface
Generate routing message
19.7. rtredirect Function
New gateway must be directly connected
Locate routing table entry for destination and validate redirect
Must create a new route
Create new host route
Create route
Modify existing host route
Ignore if destination is directly connected
Return pointer and increment statistic
Generate routing message
19.8. Routing Message Structures
19.9. rt_missmsg Function
Build message in mbuf chain
Finish building message
Set protocol of message, call raw_input
19.10. rt_ifmsg Function
Build message in mbuf chain
Finish building message
Set protocol of message, call raw_input
19.11. rt_newaddrmsg Function
Generate two routing messages
Generate message with up to four addresses
Finish building message
Build message
Set protocol of message, call raw_input
19.12. rt_msg1 Function
Get mbuf and determine fixed size of message
Verify structure fits in mbuf
Initialize mbuf packet header and zero structure
Copy socket address structures into mbuf chain
Store length, version, and type
19.13. rt_msg2 Function
Determine size of structure
Copy socket address structures
Check if data to be stored
Allocate buffer first time or if message length increases
Go around again and store result
Store length, version, and type
19.14. sysctl_rtable Function
Validate arguments
Initialize walkarg structure
Dump routing table
Return interface list
Release buffer
Update w_needed
Return actual size of message
Return estimated size of message
19.15. sysctl_dumpentry Function
Check flags of routing table entry
Form routing message
Copy message back to process
19.16. sysctl_iflist Function
Check interface index
Build routing message
Copy message back to process
Iterate through address structures, check address family
Build routing message
Copy message back to process
19.17. Summary
19.17. Summary
Exercises
20. Routing Sockets
20.1. Introduction
20.1. Introduction
20.2. routedomain and protosw Structures
20.3. Routing Control Blocks
20.4. raw_init Function
20.5. route_output Function
Check mbuf for validity
Allocate buffer
Check version number
Destination address required
Handle optional genmask
Locate existing entry
Do not allow network match
Use network mask to find correct entry
Return destination, gateway, and masks
Return interface information
Construct reply
Change gateway
Locate new interface
Check if interface changed
Update metrics
Call interface request function
Store clone generation mask
Update bitmask of locked metrics
Return error or OK
Release held route
No process to receive message
Other listeners but no loopback copy
Convert buffer into mbuf chain
Avoid loopback copy
Set address family of routing message
20.6. rt_xaddrs Function
20.7. rt_setmetrics Function
20.8. raw_input Function
Compare address family and protocol
Compare local and foreign addresses
Append message to socket receive buffer
20.9. route_usrreq Function
PRU_ATTACH: allocate control block
PRU_DETACH: decrement counters
Process request
Increment counters
Connect socket
Enable SO_USELOOPBACK by default
20.10. raw_usrreq Function
PRU_CONTROL requests invalid
Control information invalid
Socket must have a control block
20.11. raw_attach, raw_detach, and raw_disconnect Functions
20.12. Summary
20.12. Summary
Exercises
21. ARP: Address Resolution Protocol
21.1. Introduction
21.1. Introduction
21.2. ARP and the Routing Table
21.3. Code Introduction
Global Variables
Statistics
SNMP Variables
21.4. ARP Structures
21.5. arpwhohas Function
21.6. arprequest Function
Allocate and initialize mbuf
Initialize pointers
Fill in Ethernet header
Fill in ARP fields
Fill in sockaddr and call interface output function
21.7. arpintr Function
21.8. in_arpinput Function
Look for matching interface and IP address
Validate sender’s hardware address
Check sender’s IP address
Search routing table for match with sender’s IP address
Update existing entry or fill in new entry
Check if sender’s hardware addresses changed
Record sender’s hardware address
Update newly resolved ARP entry
Finished with ARP reply packets
This host is the target
Check if this host is a proxy server for target
Form proxy reply
Complete construction of ARP reply packet
Fill in sockaddr with Ethernet header
21.9. ARP Timer Functions
arptimer Function
Set next timeout
Check all ARP entries
arptfree Function
Invalidate (don’t delete) entries in use
Delete unreferenced entries
21.10. arpresolve Function
Handle broadcast and multicast destinations
Get pointer to llinfo_arp structure
Check ARP entry for validity
Hold only most recent IP datagram
Send ARP request but avoid ARP flooding
21.11. arplookup Function
Initialize sockaddr_inarp to look up
Look up entry in routing table
Decrement routing table reference count
21.12. Proxy ARP
21.13. arp_rtrequest Function
Initialize ARP timeout function
Ignore indirect routes
RTM_ADD command
Backward compatibility
Initialize entry for network route to interface
Send gratuitous ARP request
Verify sockaddr_dl Structure
Handle route changes
Initialize llinfo_arp structure
Handle local host specially
Make entry permanent and set Ethernet address
Set interface pointer to loopback interface
Verify la pointer
Delete llinfo_arp structure
21.14. ARP and Multicasting
21.15. Summary
21.15. Summary
Exercises
22. Protocol Control Blocks
22.1. Introduction
22.1. Introduction
22.2. Code Introduction
Global Variables
Statistics
22.3. inpcb Structure
22.4. in_pcballoc and in_pcbdetach Functions
Allocate PCB and initialize to zero
Link structures together
22.5. Binding, Connecting, and Demultiplexing
Binding of Local IP Address and Port Number
Connecting a UDP Socket
Demultiplexing of Received IP Datagrams by TCP
Demultiplexing of Received IP Datagrams by UDP
22.6. in_pcblookup Function
Compare local port number
Compare local address
Compare foreign address and foreign port number
Check if wildcard match allowed
Remember best match, return if exact match found
Example—Demultiplexing of Received TCP Segment
22.7. in_pcbbind Function
so_reuseaddr Examples
SO_REUSEPORT Socket Option
22.8. in_pcbconnect Function
Validate argument
Handle connection to 0.0.0.0 and 255.255.255.255 specially
Release route if no longer valid
Acquire route
Determine outgoing interface
Verify that socket pair is unique
Implicit bind and assignment of ephemeral port
Store foreign address and foreign port in PCB
IP Source Address Versus Outgoing Interface Address
22.9. in_pcbdisconnect Function
22.10. in_setsockaddr and in_setpeeraddr Functions
22.11. in_pcbnotify, in_rtchange, and in_losing Functions
Verify arguments
Handle redirects specially
Call notify function for selected PCBs
in_rtchange Function
Redirects and Raw Sockets
ICMP Errors and UDP Sockets
in_losing Function
Generate routing message
Delete or release route
22.12. Implementation Refinements
22.13. Summary
22.13. Summary
Exercises
23. UDP: User Datagram Protocol
23.1. Introduction
23.1. Introduction
23.2. Code Introduction
Global Variables
Statistics
SNMP Variables
23.3. UDP protosw Structure
23.4. UDP Header
23.5. udp_init Function
23.6. udp_output Function
Discard optional control information
Temporarily connect an unconnected socket
Prepend IP and UDP headers
Prepending IP/UDP Headers and Mbuf Clusters
UDP Checksum Calculation and Pseudo-Header
Prepare pseudo-header for checksum computation
Calculate checksum
Fill in UDP length, TTL, and TOS
Send datagram
Disconnect temporarily connected socket
23.7. udp_input Function
General Validation of Received UDP Datagram
Discard IP options
Verify UDP length
Save copy of IP header and verify UDP checksum
Demultiplexing Unicast Datagrams
Check one-behind cache
Search all UDP PCBs
Generate ICMP port unreachable error
Return source IP address and source port
IP_RECVDSTADDR socket option
Unimplemented socket options
Append data to socket’s receive queue
Error return
Demultiplexing Multicast and Broadcast Datagrams
Connected UDP Sockets and Multihomed Hosts
23.8. udp_saveopt Function
23.9. udp_ctlinput Function
udp_notify Function
23.10. udp_usrreq Function
23.11. udp_sysctl Function
23.12. Implementation Refinements
UDP PCB Cache
UDP Checksum
23.13. Summary
23.13. Summary
Exercises
24. TCP: Transmission Control Protocol
24.1. Introduction
24.1. Introduction
24.2. Code Introduction
Global Variables
Statistics
SNMP Variables
24.3. TCP protosw Structure
24.4. TCP Header
24.5. TCP Control Block
24.6. TCP State Transition Diagram
Half-Close
24.7. TCP Sequence Numbers
Modular Arithmetic with Sequence Numbers
Example—Sequence Number Comparisons
24.8. tcp_init Function
Set initial send sequence number (ISS)
Initialize linked list of TCP Internet PCBs
Calculate maximum protocol header length
MSL and Quiet Time Concept
24.9. Summary
24.9. Summary
Exercises
25. TCP Timers
25.1. Introduction
25.1. Introduction
25.2. Code Introduction
25.3. tcp_canceltimers Function
25.4. tcp_fasttimo Function
25.5. tcp_slowtimo Function
Check each timer counter in all TCP control blocks
Check if TCP control block has been deleted
Count idle time
Increment RTT counter
Increment initial send sequence number
Increment RFC 1323 timestamp value
25.6. tcp_timers Function
FIN_WAIT_2 and 2MSL Timers
2MSL timer
FIN_WAIT_2 timer
Persist Timer
Force window probe segment
Connection Establishment and Keepalive Timers
Connection-establishment timer expires after 75 seconds
Keepalive timer expires after 2 hours of idle time
Drop connection when no response
Send a keepalive probe
Reset keepalive timer
25.7. Retransmission Timer Calculations
25.8. tcp_newtcpcb Function
25.9. tcp_setpersist Function
Check retransmission timer not enabled
Calculate RTO
Apply exponential backoff
25.10. tcp_xmit_timer Function
Update smoothed estimators
Initialize smoothed estimators on first RTT measurement
Clear soft error variable
25.11. Retransmission Timeout: tcp_timers Function
Increment shift count
Drop connection
Calculate new RTO
Ask IP to find a new route
Clear estimators
Force retransmission of oldest unacknowledged data
Karn’s algorithm
Slow Start and Congestion Avoidance
Accuracy
25.12. An RTT Example
25.13. Summary
25.13. Summary
Exercises
26. TCP Output
26.1. Introduction
26.1. Introduction
26.2. tcp_output Overview
Is an ACK expected from the other end?
Go back to slow start
Send more than one segment
26.3. Determine if a Segment Should be Sent
Calculate amount of data to send
Check for window shrink
Enter persist state
Send one segment at a time
Turn off FIN flag if send buffer not emptied
Calculate window advertisement
Sender silly window avoidance
Example
Example
26.4. TCP Options
26.5. Window Scale Option
26.6. Timestamp Option
Which Timestamp to Echo, RFC 1323 Algorithm
Which Timestamp to Echo, Corrected Algorithm
Timestamps and Delayed ACKs
26.7. Send a Segment
Build MSS option
Should window scale option be sent?
Build window scale option
Should timestamp option be sent?
Build timestamp option
Check if options have overflowed segment
Update statistics
Allocate an mbuf for IP and TCP headers
Copy data into mbuf
Set PSH flag
Update statistics
Get mbuf for IP and TCP headers
Copy IP and TCP header templates into mbuf
Decrement snd_nxt if FIN is being retransmitted
Set sequence number field of segment
Set acknowledgment field of segment
Set header length if options present
Don’t advertise less than one full-sized segment
Observe upper limit for advertised window on this connection
Do not shrink window
Set urgent offset
Remember starting sequence number
Increment snd_nxt
Update snd_max
Set retransmission timer
Persist state
Add trace record for socket debugging
Set IP length, TTL, and TOS
Pass datagram to IP
Update rcv_adv and last_ack_sent
More data to send?
26.8. tcp_template Function
Allocate mbuf
Initialize header fields
Pseudo-header for TCP checksum computation
26.9. tcp_respond Function
Send keepalive probe when keepalive timer expires
Send RST segment in response to received segment
26.10. Summary
26.10. Summary
Exercises
27. TCP Functions
27.1. Introduction
27.1. Introduction
27.2. tcp_drain Function
27.3. tcp_drop Function
27.4. tcp_close Function
Route Characteristics
Check if enough data sent to update statistics
Update RTT
Update mean deviation
Resource Release
Release any mbufs on reassembly queue
Release header template and TCP control block
Release PCB
27.5. tcp_mss Function
Acquire a route if necessary
Initialize smoothed RTT estimator
Initialize smoothed mean deviation estimator
Calculate initial RTO
Use MSS from routing table MTU
Round MSS down to multiple of MCLBYTES
Check if destination local or nonlocal
Other end’s MSS is upper bound
Round buffer sizes to multiple of MSS
Initialize congestion window and slow start threshold
Example
27.6. tcp_ctlinput Function
27.7. tcp_notify Function
27.8. tcp_quench Function
27.9. TCP_REASS Macro and tcp_reass Function
TCP_REASS Macro
tcp_reass Function
27.10. tcp_trace Function
Sample Output
27.11. Summary
27.11. Summary
Exercises
28. TCP Input
28.1. Introduction
28.1. Introduction
28.2. Preliminary Processing
Get IP and TCP headers in first mbuf
Verify TCP checksum
Verify TCP offset field
Get headers plus option into first mbuf
Process timestamp option quickly
Save input flags and convert fields to host byte order
Locate Internet PCB
Drop segment and generate RST
Silently drop segment
Unscale advertised window
Save connection state and IP/TCP headers if socket debug option enabled
Create new socket if segment arrives for listening socket
Compute window scale factor
Reset idle time and keepalive timer
Process TCP options if not in LISTEN state
28.3. tcp_dooptions Function
Fetch option type and length
MSS option
Window scale option
Timestamp option
28.4. Header Prediction
Check if segment is the next expected
Update ts_recent from received timestamp
Test for pure ACK
Update RTT estimators
Delete acknowledged bytes from send buffer
Stop retransmit timer
Awaken waiting processes
Generate more output
Test for next in-sequence data segment
Complete processing of received data
Statistics
28.5. TCP Input: Slow Path Processing
Drop IP and TCP headers, including TCP options
Calculate receive window
28.6. Initiation of Passive Open, Completion of Active Open
Initiation of Passive Open
Drop if RST, ACK, or no SYN
Drop if broadcast or multicast
Get mbuf for client’s IP address and port
Set local address in PCB
Connect PCB to peer
Allocate and initialize IP and TCP header template
Process any TCP options
Initialize ISS
Initialize sequence number variables in control block
ACK the SYN and change state
Completion of Active Open
Verify received ACK
Process and drop RST segment
Verify SYN flag set
Process ACK
Turn off retransmission timer
Initialize receive sequence numbers
Connection is established
Check for window scale option
Pass any queued data to process
Update RTT estimators
Simultaneous open
Drop any received data that follows receive window
Force update of window variables
28.7. PAWS: Protection Against Wrapped Sequence Numbers
Basic PAWS test
Check for outdated timestamp
Drop duplicate segment
28.8. Trim Segment so Data is Within Window
Check if any duplicate data at front of segment
Remove duplicate SYN
Check for entire duplicate packet
Check for duplicate FIN
Generate duplicate ACK
Handle simultaneous open or self-connect
Update statistics for partial duplicate segments
Remove duplicate data and update urgent offset
Calculate number of bytes beyond right edge of window
Check for new incarnation of a connection in the TIME_WAIT state
Check for probe of closed window
Drop other segments that are completely outside window
Handle segments that contain some valid data
When to Drop an ACK
28.9. Self-Connects and Simultaneous Opens
28.10. Record Timestamp
28.11. RST Processing
SYN_RCVD state
Other states
28.12. Summary
28.12. Summary
Exercises
29. TCP Input
29.1. Introduction
29.1. Introduction
29.2. ACK Processing Overview
29.3. Completion of Passive Opens and Simultaneous Opens
Verify received ACK
Check for window scale option
Pass queued data to process
29.4. Fast Retransmit and Fast Recovery Algorithms
Number of consecutive duplicate ACKs reaches threshold of 3
Turn off retransmission timer
Retransmit missing segment
Set congestion window
Set snd_nxt
Number of consecutive duplicate ACKs exceeds threshold of 3
Skip remainder of ACK processing
29.5. ACK Processing
Adjust congestion window
Check for out-of-range ACK
Calculate number of bytes acknowledged
Update RTT estimators
Check if all outstanding data has been acknowledged
Unacknowledged data outstanding
Karn’s Algorithm and Timestamps
Update congestion window
Remove acknowledged bytes from the send buffer
Wakeup processes waiting on send buffer
Receipt of ACK in FIN_WAIT_1 state
Set FIN_WAIT_2 timer
Receipt of ACK in CLOSING state
Receipt of ACK in LAST_ACK state
Receipt of ACK in TIME WAIT state
29.6. Update Window Information
Check if send window should be updated
Update variables
29.7. Urgent Mode Processing
Check if URG flag should be processed
Ignore bogus urgent offsets
Calculate receive urgent pointer
Notify process of TCP’s urgent mode
Pull out-of-band byte out of normal data stream
Adjust receive urgent pointer if not urgent mode
29.8. tcp_pulloutofband Function
Skip to next mbuf in chain
29.9. Processing of Received Data
Guess size of other end’s send buffer
29.10. FIN Processing
Process first FIN received on connection
SYN_RCVD or ESTABLISHED states
FIN_WAIT_1 state
FIN_WAIT_2 state
Start TIME_WAIT timer
TIME_WAIT state
29.11. Final Processing
SO_DEBUG socket option
Call tcp_output
dropafterack
dropwithreset
Sequence number and acknowledgment number of RST segment
Rejecting connections
Destroy temporarily created socket
Drop (without ACK or RST)
29.12. Implementation Refinements
29.13. Header Compression
Introduction
Compression of Header Fields
Special Cases
Examples
Configuration
29.14. Summary
29.14. Summary
Exercises
30. TCP User Requests
30.1. Introduction
30.1. Introduction
30.2. tcp_usrreq Function
in_control processes ioctl requests
Control information is invalid
PRU_ATTACH request
PRU_DETACH request
Assign ephemeral port
Connect PCB
Initialize IP and TCP headers
Calculate window scale factor
Set socket and connection state
Initialize sequence numbers
Send initial SYN
PRU_SHUTDOWN request
PRU_RCVD request
PRU_SEND request
PRU_ABORT request
PRU_SENSE request
Verify that reading out-of-band data is appropriate
Check that out-of-band byte has arrived
Return out-of-band byte
Flip flags
Check for room and append to send buffer
Calculate urgent pointer
Force TCP output
30.3. tcp_attach Function
Allocate space for send buffer and receive buffer
Allocate Internet PCB and TCP control block
30.4. tcp_disconnect Function
Connection not yet synchronized
Hard disconnect
Graceful disconnect
Discard pending receive data
Change connection state
30.5. tcp_usrclosed Function
Simple close when SYN not received
Move to FIN_WAIT_1 state
Move to LAST_ACK state
30.6. tcp_ctloutput Function
TCP_NODELAY option
TCP_MAXSEG option
Release mbuf
30.7. Summary
30.7. Summary
Exercises
31. BPF: BSD Packet Filter
31.1. Introduction
31.1. Introduction
31.2. Code Introduction
Global Variables
Statistics
31.3. bpf_if Structure
Initialize bpf_if structure
Compute BPF header size
Initialize bpf_dtab table
Print console message
31.4. bpf_d Structure
Packet buffers
bpfopen Function
Allocate bpf_d structure
bpfioctl Function
bpf_setif Function
Locate matching ifnet structure
Attach bpf_d structure
bpf_attachd Function
31.5. BPF Input
bpf_tap Function
Pass packet to one or more BPF devices
catchpacket Function
Will the packet fit?
Immediate mode processing
Append BPF header
bpfread Function
Wait for data
Immediate mode
No packets available
Check hold buffer
Check store buffer
Packets are available
31.6. BPF Output
bpfwrite Function
Check device number
Copy data into mbuf chain
Queue packet
31.7. Summary
31.7. Summary
Exercises
32. Raw IP
32.1. Introduction
32.1. Introduction
32.2. Code Introduction
Global Variables
Statistics
32.3. Raw IP protosw Structure
32.4. rip_init Function
32.5. rip_input Function
Save source IP address
Search all raw IP PCBs for one or more matching entries
Compare protocols
Compare local and foreign IP addresses
Pass copy of received datagram to processes
Undeliverable datagram
32.6. rip_output Function
Kernel fills in IP header
Caller fills in IP header: IP_HDRINCL socket option
32.7. rip_usrreq Function
Verify superuser
Create Internet PCB and reserve buffer space
32.8. rip_ctloutput Function
32.9. Summary
32.9. Summary
Exercises
Epilogue
A. Solutions to Selected Exercises
Chapter 1
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Chapter 16
Chapter 17
Chapter 18
Chapter 19
Chapter 20
Chapter 21
Chapter 22
Chapter 23
Chapter 24
Chapter 25
Chapter 26
Chapter 27
Chapter 28
Chapter 29
Chapter 30
Chapter 31
Chapter 32
B. Source Code Availability
URLs: Uniform Resource Locators
URLs: Uniform Resource Locators
4.4BSD-Lite
Operating Systems that Run the 4.4BSD-Lite Networking Software
RFCs
GNU Software
PPP Software
mrouted Software
ISODE Software
C. RFC 1122 Compliance
C.1. Link-Layer Requirements
C.1. Link-Layer Requirements
C.2. IP Requirements
Multihoming
Broadcast
IP Interface
C.3. IP Options Requirements
Source Route Forwarding
C.4. IP Fragmentation and Reassembly Requirements
C.5. ICMP Requirements
C.6. Multicasting Requirements
C.7. IGMP Requirements
C.8. Routing Requirements
C.9. ARP Requirements
C.10. UDP Requirements
C.11. TCP Requirements
PSH Flag
Window
Urgent Data
TCP Options
TCP Checksums
Initial Sequence Number Selection
Opening Connections
Closing Connections
Retransmissions
Generating ACKs
Sending Data
Connection Failures
Keepalive Packets
IP Options
Receiving ICMP Messages from IP
Application Programming Interface
Bibliography
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Prev
Previous Chapter
Epilogue
Next
Next Chapter
B. Source Code Availability
Appendix A. Solutions to Selected Exercises
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Chapter 15
Chapter 16
Chapter 17
Chapter 18
Chapter 19
Chapter 20
Chapter 21
Chapter 22
Chapter 23
Chapter 24
Chapter 25
Chapter 26
Chapter 27
Chapter 28
Chapter 29
Chapter 30
Chapter 31
Chapter 32
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset