Abstract
This document is a guide to understanding how the Linux kernel (version 2.2.14 specifically) implements networking protocols, focused primarily on the Internet Protocol (IP). It is intended as a complete reference for experimenters with overviews, walk-throughs, source code explanations, and examples. The first part contains an in-depth examination of the code, data structures, and functionality involved with networking. There are chapters on initialization, connections and sockets, and receiving, transmitting, and forwarding packets. The second part contains detailed instructions for modifiying the kernel source code and installing new modules. There are chapters on kernel installation, modules, the proc file system, and a complete example.
This document is an effort to bring together many of these sources into one coherent reference on and guide to modifying the networking code within the Linux kernel. It presents the internal workings on four levels: a general overview, more specific examinations of network activities, detailed function walk-throughs, and references to the actual code and data structures. It is designed to provide as much or as little detail as the reader desires. This guide was written specifically about the Linux 2.2.14 kernel (which has already been superseded by 2.2.15) and many of the examples come from the Red Hat 6.1 distribution; hopefully the information provided is general enough that it will still apply across distributions and new kernels. It also focuses almost exclusively on TCP/UDP, IP, and Ethernet - which are the most common but by no means the only networking protocols available for Linux platforms.
As a reference for kernel programmers, this document includes information and pointers on editing and recompiling the kernel, writing and installing modules, and working with the /proc file system. It also presents an example of a program that drops packets for a selected host, along with analysis of the results. Between the descriptions and the examples, this should answer most questions about how Linux performs networking operations and how you can modify it to suit your own purposes.
This project began in a Computer Science Department networking lab at the University of New Hampshire as an effort to institute changes in the Linux kernel to experiment with different routing algorithms. It quickly became apparent that blindly hacking the kernel was not a good idea, so this document was born as a research record and a reference for future programmers. Finally it became large enough (and hopefully useful enough) that we decided to generalize it, formalize it, and release it for public consumption.
As a final note, Linux is an ever-changing system and truly mastering it, if such a thing is even possible, would take far more time than has been spent putting this reference together. If you notice any misstatements, omissions, glaring errors, or even typos (!) within this document, please contact the person who is currently maintaining it. The goal of this project has been to create a freely available and useful reference for Linux programmers.
Almost all of the code presented requires superuser access to implement. Some of the examples can create security holes where none previously existed; programmers should be careful to restore their systems to a normal state after experimenting with the kernel.
File references and program names are written in a slanted font.
Code, command line entries, and machine names are written in a typewriter font.
Generic entries or variables (such as an output filename) and comments are written in an italic font.
This network represents the computer system at a fictional unnamed University (U!). It has a router connected to the Internet at large (chrysler). That machine is connected (through the jeep interface) to the campus-wide network, u.edu, consisting of computers named for Chrysler owned car companies (dodge, eagle, etc.). There is also a LAN subnet for the computer science department, cs.u.edu, whose hosts are named after Dodge vehicle models (stealth, neon, etc.). They are connected to the campus network by the dodge/viper computer. Both the u.edu and cs.u.edu networks use Ethernet hardware and protocols.
This is obviously not a real network. The IP addresses are all taken from the block reserved for class B private networks (that are not guaranteed to be unique). Most real class B networks would have many more computers, and a network with only eight computers would probably not have a subnet. The connection to the Internet (through chrysler) would usually be via a T1 or T3 line, and that router would probably be a ``real'' router (i.e. a Cisco Systems hardware router) rather than a computer with two network cards. However, this example is realistic enough to serve its purpose: to illustrate the the Linux network implementation and the interactions between hosts, subnets, and networks.
Copyright (c) 2000 by Glenn Herrin. This document may be freely reproduced in whole or in part provided credit is given to the author with a line similar to the following:
Copied from Linux IP Networking, available at http://www.cs.unh.edu/cnrg/gherrin.(The visibility of the credit should be proportional to the amount of the document reproduced!) Commercial redistribution is permitted and encouraged. All modifications of this document, including translations, anthologies, and partial documents, must meet the following requirements:
Please note any modifications including deletions.
This is a variation (changes are intentional) of the Linux Documentaion Project (LDP) License available at:
http://www.linuxdoc.org/COPYRIGHT.htmlThis document is not currently part of the LDP, but it may be submitted in the future.
This document is distributed in the hope that it will be useful but (of course)without any given or implied warranty of fitness for any purpose whatsoever. Use it at your own risk.
Glenn Herrin
Major, United States Army
Primary Documenter and Researcher, Version 1.0
gherrin@cs.unh.edu
This chapter presents an overview of the entire Linux messaging system. It provides a discussion of configurations, introduces the data structures involved, and describes the basics of IP routing.
When an application generates traffic, it sends packets through sockets to a transport layer (TCP or UDP) and then on to the network layer (IP). In the IP layer, the kernel looks up the route to the host in either the routing cache or its Forwarding Information Base (FIB). If the packet is for another computer, the kernel addresses it and then sends it to a link layer output interface (typically an Ethernet device) which ultimately sends the packet out over the physical medium.
When a packet arrives over the medium, the input interface receives it and checks to see if the packet is indeed for the host computer. If so, it sends the packet up to the IP layer, which looks up the route to the packet's destination. If the packet has to be forwarded to another computer, the IP layer sends it back down to an output interface. If the packet is for an application, it sends it up through the transport layer and sockets for the application to read when it is ready.
Along the way, each socket and protocol performs various checks and formatting functions, detailed in later chapters. The entire process is implemented with references and jump tables that isolate each protocol, most of which are set up during initialization when the computer boots. See Chapter 3 for details of the initialization process.
IP is the standard network layer protocol. It checks incoming packets to see if they are for the host computer or if they need to be forwarded. It defragments packets if necessary and delivers them to the transport protocols. It maintains a database of routes for outgoing packets; it addresses and fragments them if necessary before sending them down to the link layer.
TCP and UDP are the most common transport layer protocols. UDP simply provides a framework for addressing packets to ports within a computer, while TCP allows more complex connection based operations, including recovery mechanisms for packet loss and traffic management implementations. Either one copies the packet's payload between user and kernel space. However, both are just part of the intermediate layer between the applications and the network.
IP Specific INET Sockets are the data elements and implementations of generic sockets. They have associated queues and code that executes socket operations such as reading, writing, and making connections. They act as the intermediary between an application's generic socket and the transport layer protocol.
Generic BSD Sockets are more abstract structures that contain INET sockets. Applications read from and write to BSD sockets; the BSD sockets translate the operations into INET socket operations. See Chapter 4 for more on sockets.
Applications, run in user space, form the top level of the protocol stack; they can be as simple as two-way chat connection or as complex as the Routing Information Protocol (RIP - see Chapter 9).
This structure contains pointers to all of the information about a packet - its socket, device, route, data locations, etc. Transport protocols create these packet structures from output buffers, while device drivers create them for incoming data. Each layer then fills in the information that it needs as it processes the packet. All of the protocols - transport (TCP/UDP), internet (IP), and link level (Ethernet) - use the same socket buffer.
The FIB is the primary routing reference; it contains up to 32 zones (one for each bit in an IP address) and entries for every known destination. Each zone contains entries for networks or hosts that can be uniquely identified by a certain number of bits - a network with a netmask of 255.0.0.0 has 8 significant bits and would be in zone 8, while a network with a netmask of 255.255.255.0 has 24 significant bits and would be in zone 24. When IP needs a route, it begins with the most specific zones and searches the entire table until it finds a match (there should always be at least one default entry). The file /proc/net/route has the contents of the FIB.
The routing cache is a hash table that IP uses to actually route packets. It contains up to 256 chains of current routing entries, with each entry's position determined by a hash function. When a host needs to send a packet, IP looks for an entry in the routing cache. If there is none, it finds the appropriate route in the FIB and inserts a new entry into the cache. (This entry is what the various protocols use to route, not the FIB entry.) The entries remain in the cache as long as they are being used; if there is no traffic for a destination, the entry times out and IP deletes it. The file /proc/net/rt_cache has the contents of the routing cache.
These tables perform all the routing on a normal system. Even other protocols (such as RIP) use the same structures; they just modify the existing tables within the kernel using the ioctl() function. See Chapter 8 for routing details.
This chapter presents network initialization on startup. It provides an overview of what happens when the Linux operating system boots, shows how the kernel and supporting programs ifconfig and route establish network links, shows the differences between several example configurations, and summarizes the implementation code within the kernel and network programs.
The entire configuration process can be static or dynamic. If addresses and names never (or infrequently) change, the system administrator must define options and variables in files when setting up the system. In a more mutable environment, a host will use a protocol like the Dynamic Hardware Configuration Protocol (DHCP) to ask for an address, router, and DNS server information with which to configure itself when it boots. (In fact, in either case, the administrator will almost always use a GUI interface - like Red Hat's Control Panel - which automatically writes the configuration files shown below.)
An important point to note is that while most computers running Linux start up the same way, the programs and their locations are not by any means standardized; they may vary widely depending on distribution, security concerns, or whim of the system administrator. This chapter presents as generic a description as possible but assumes a Red Hat Linux 6.1 distribution and a generally static network environment.
The script(s) involved in establishing networking can be very straightforward; it is entirely possible to have one big script that simply executes a series of commands that will set up a single machine properly. However, most Linux distributions come with a large number of generic scripts that work for a wide variety of machine setups. This leaves a lot of indirection and conditional execution in the scripts, but actually makes setting up any one machine much easier. For example, on Red Hat distributions, the /etc/rc.d/init.d/network script runs several other scripts and sets up variables like interfaces_boot to keep track of which /etc/sysconfig/network-scripts/ifup scripts to run. Tracing the process manually is very complicated, but simple modifications of only two configuration files (putting the proper names and IP addresses in the /etc/sysconfig/network and /etc/sysconfig/network-scripts/ifcfg-eth0 files) sets up the entire system properly (and a GUI makes the process even simpler).
When the network script finishes, the FIB contains the specified routes to given hosts or networks and the routing cache and neighbor tables are empty. When traffic begins to flow, the kernel will update the neighbor table and routing cache as part of the normal network operations. (Network traffic may begin during initialization if a host is dynamically configured or consults a network clock, for example.)
ifconfig ${DEVICE} ${IPADDR} netmask ${NMASK} broadcast ${BCAST}(where the variables are either written directly in the script or are defined in other scripts).
The ifconfig program can also provide information about currently configured network devices (calling with no arguments displays all the active interfaces; calling with the -a option displays all interfaces, active or not):
ifconfigThis provides all the information available about each working interface; addresses, status, packet statistics, and operating system specifics. Usually there will be at least two interfaces - a network card and the loopback device. The information for each interface looks like this (this is the viper interface):
eth0 Link encap:Ethernet HWaddr 00:C1:4E:7D:9E:25
inet addr:172.16.1.1 Bcast:172.16.1.255 Mask:255.255.255.0
UP BROADCAST RUNNING MULTICAST MTU:1500 Metric:1
RX packets:389016 errors:16534 dropped:0 overruns:0 frame:24522
TX packets:400845 errors:0 dropped:0 overruns:0 carrier:0
collisions:0 txqueuelen:100
Interrupt:11 Base address:0xcc00
A superuser can use ifconfig to change interface settings from the command line; here is the syntax:
ifconfig interface [aftype] options | address ...... and some of the more useful calls:
ifconfig eth0 down - shut down eth0Note that modifying an interface configuration can indirectly change the routing tables. For example, changing the netmask may make some routes moot (including the default or even the route to the host itself) and the kernel will delete them.
ifconfig eth1 up - activate eth1
ifconfig eth0 arp - enable ARP on eth0
ifconfig eth0 -arp - disable ARP on eth0
ifconfig eth0 netmask 255.255.255.0 - set the eth0 netmask
ifconfig lo mtu 2000 - set the loopback maximum transfer unit
ifconfig eth1 172.16.0.7 - set the eth1 IP address
route add -net ${NETWORK} netmask ${NMASK} dev ${DEVICE} -or-(where the variables are again spelled out or defined in other scripts).
route add -host ${IPADDR} ${DEVICE}
The route program can also delete routes (if run with the del option) or provide information about the routes that are currently defined (if run with no options):
routeThis displays the Kernel IP routing table (the FIB, not the routing cache). For example (the stealth computer):
A superuser can use route to add and delete IP routes from the command line; here is the basic syntax:Kernel IP routing table Destination Gateway Genmask Flags Metric Ref Use Iface 172.16.1.4 * 255.255.255.255 UH 0 0 0 eth0 172.16.1.0 * 255.255.255.0 U 0 0 0 eth0 127.0.0.0 * 255.0.0.0 U 0 0 0 lo default viper.u.edu 0.0.0.0 UG 0 0 0 eth0
route add [-net|-host] target [option arg]... and some useful examples:
route del [-net|-host] target [option arg]
route add -host 127.16.1.0 eth1 - adds a route to a host
route add -net 172.16.1.0 netmask 255.255.255.0 eth0 - adds a network
route add default gw jeep - sets the default route through jeep
(Note that a route to jeep must already be set up)
route del -host 172.16.1.16 - deletes entry for host 172.16.1.16
This is the first file the network script will read; it sets several environment variables. The first two variables set the computer to run networking programs (even though it is not on a network) but not to forward packets (since it has nowhere to send them). The last two variables are generic entries.
/etc/sysconfig/network
NETWORKING=yesAfter setting these variables, the network script will decide that it needs to configure at least one network device in order to be part of a network. The next file (which is almost exactly the same on all Linux computers) sets up environment variables for the loopback device. It names it and gives it its (standard) IP address, network mask, and broadcast address as well as any other device specific variables. (The ONBOOT variable is a flag for the script program that tells it to configure this device when it boots.) Most computers, even those that will never connect to the Internet, install the loopback device for inter-process communication.
FORWARD_IPV4=false
HOSTNAME=localhost.localdomain
GATEWAY=
/etc/sysconfig/network-scripts/ifcfg-lo
DEVICE=loAfter setting these variables, the script will run the ifconfig program and stop, since there is nothing else to do at the moment. However, when the ppp program connects to an Internet Service Provider, it will establish a ppp device and addressing and routes based on the dynamic values assigned by the ISP. The DNS server and other connection information should be in an ifcfg-ppp file.
IPADDR=127.0.0.1
NMASK=255.0.0.0
NETWORK=127.0.0.0
BCAST=127.255.255.255
ONBOOT=yes
NAME=loopback
BOOTPROTO=none
This is the first file the network script will read; again the first variables simply determine that the computer will do networking but that it will not forward packets. The last four variables identify the computer and its link to the rest of the Internet (everything that is not on the LAN).
/etc/sysconfig/network
NETWORKING=yesAfter setting these variables, the network script will configure the network devices. This file sets up environment variables for the Ethernet card. It names the device and gives it its IP address, network mask, and broadcast address as well as any other device specific variables. This kind of computer would also have a loopback configuration file exactly like the one for a non-networked computer.
FORWARD_IPV4=false
HOSTNAME=stealth.cs.u.edu
DOMAINNAME=cs.u.edu
GATEWAY=172.16.1.1
GATEWAYDEV=eth0
/etc/sysconfig/network-scripts/ifcfg-eth0
DEVICE=eth0
IPADDR=172.16.1.4
NMASK=255.255.255.0
NETWORK=172.16.1.0
BCAST=172.16.1.255
ONBOOT=yes
BOOTPROTO=none
After setting these variables, the network script will run the ifconfig program to start the device. Finally, the script will run the route program to add the default route (GATEWAY) and any other specified routes (found in the /etc/sysconfig/static-routes file, if any). In this case only the default route is specified, since all traffic either stays on the LAN (where the computer will use ARP to find other hosts) or goes through the router to get to the outside world.
This is the first file the network script will read; it sets several environment variables. The first two simply determine that the computer will do networking (since it is on a network) and that this one will forward packets (from one network to the other). IP Forwarding is built into most kernels, but it is not active unless there is a 1 ``written'' to the /proc/net/ipv4/ip_forward file. (One of the network scripts performs an echo 1 > /proc/net/ipv4/ip_forward if FORWARD_IPV4 is true.) The last four variables identify the computer and its link to the rest of the Internet (everything that is not on one of its own networks).
/etc/sysconfig/network
NETWORKING=yesAfter setting these variables, the network script will configure the network devices. These files set up environment variables for two Ethernet cards. They name the devices and give them their IP addresses, network masks, and broadcast addresses. (Note that the BOOTPROTO variable remains defined for the second card.) Again, this computer would have the standard loopback configuration file.
FORWARD_IPV4=true
HOSTNAME=dodge.u.edu
DOMAINNAME=u.edu
GATEWAY=172.16.0.1
GATEWAYDEV=eth1
/etc/sysconfig/network-scripts/ifcfg-eth0
DEVICE=eth0
IPADDR=172.16.1.1
NMASK=255.255.255.0
NETWORK=172.16.1.0
BCAST=172.16.1.255
ONBOOT=yes
BOOTPROTO=static
/etc/sysconfig/network-scripts/ifcfg-eth1
DEVICE=eth1After setting these variables, the network script will run the ifconfig program to start each device. Finally, the script will run the route program to add the default route (GATEWAY) and any other specified routes (found in the /etc/sysconfig/static-routes file, if any). In this case again, the default route is the only specified route, since all traffic will go on the network indicated by the network masks or through the default router to reach the rest of the Internet.
IPADDR=172.16.0.7
NMASK=255.255.0.0
NETWORK=172.16.0.0
BCAST=172.16.255.255
ONBOOT=yes
These sources are available as a package separate from the kernel source (Red Hat Linux uses the rpm package manager). The code below is from the net-tools-1.53-1 source code package, 29 August 1999. The packages are available from the www.redhat.com/apps/download web page. Once downloaded, root can install the package with the following commands (starting from the directory with the package):
rpm -i net-tools-1.53-1.src.rpmThis creates a /usr/src/redhat/SOURCES/net-tools-1.53 directory and fills it with the source code for the ifconfig and route programs (among others). This process should be similar (but is undoubtably not exactly the same) for other Linux distributions.
cd /usr/src/redhat/SOURCES
tar xzf net-tools-1.53.tar.gz
devinet_ioctl() - net/ipv4/devinet.c (398)
creates an info request (ifreq) structure and copies data from
user to kernel space
if it is an INET level request or action, executes it
if it is a device request or action, calls a device function
copies ifreq back into user memory
returns 0 for success
>>> ifconfig main() - SOURCES/ifconfig.c (478)
opens a socket (only for use with ioctl function)
searches command line arguments for options
calls if_print() if there were no arguments or the only argument
is an interface name
loops through remaining arguments, setting or clearing flags or
calling ioctl() to set variables for the interface
if_fetch() - SOURCES/lib/interface.c (338)
fills in an interface structure with multiple calls to ioctl() for
flags, hardware address, metric, MTU, map, and address information
if_print() - SOURCES/ifconfig.c (121)
calls ife_print() for given (or all) interface(s)
(calls if_readlist() to fill structure list if necessary and
then displays information about each interface)
if_readlist() - SOURCES/lib/interface.c (261)
opens /proc/net/dev and parses data into interface structures
calls add_interface() for each device to put structures into a list
inet_ioctl() - net/ipv4/af_inet.c (855)
executes a switch based on the command passed
[for ifconfig, calls devinet_ioctl()]
ioctl() -
jumps to appropriate handler routine [= inet_ioctl()]
INET_rinput() - SOURCES/lib/inet_sr.c (305)
checks for errors (cannot flush table or modify routing cache)
calls INET_setroute()
INET_rprint() - SOURCES/lib/inet_gr.c (442)
if the FIB flag is set, calls rprint_fib()
(reads, parses, and displays contents of /proc/net/route)
if the CACHE flag is set, calls rprint_cache()
(reads, parses, and displays contents of /proc/net/rt_cache)
INET_setroute() - SOURCE/lib/inet_sr.c (57)
establishes whether route is to a network or a host
checks to see if address is legal
loops through arguments, filling in rtentry structure
checks for netmask conflicts
creates a temporary socket
calls ioctl() with rtentry to add or delete route
closes socket and returns 0
ioctl() -
jumps to appropriate handler routine [= ip_rt_ioctl()]
ip_rt_ioctl() - net/ipv4/fib_frontend.c (246)
converts passed parameters to routing table entry (struct rtentry)
if deleting a route:
calls fib_get_table() to find the appropriate table
calls the table->tb_delete() function to remove it
if adding a route
calls fib_net_table() to find an entry point
calls the table->tb_insert() function to add the entry
returns 0 for success
>>> route main() - SOURCES/route.c (106)
calls initialization routines that set print and edit functions
gets and parses the command line options (acts on some options
directly by setting flags or displaying information)
checks the options (prints a usage message if there is an error)
if there are no options, calls route_info()
if the option is to add, delete, or flush routes,
calls route_edit() with the passed parameters
if the option is invalid, prints a usage message
returns result of
route_edit() - SOURCES/lib/setroute.c (69)
calls get_aftype() to translate address family from text to a pointer
checks for errors (unsupported or nonexistent family)
calls the address family rinput() function [= INET_rinput()]
route_info() - SOURCES/lib/getroute.c (72)
calls get_aftype() to translate address family from text to a pointer
checks for errors (unsupported or nonexistent family)
calls the address family rprint() function [= INET_rprint()]
This chapter presents the connection process. It provides an overview of the connection process, a description of the socket data structures, an introduction to the routing system, and summarizes the implementation code within the kernel.
BSD sockets are of type struct socket as defined in include/linux/socket.h. BSD socket variables are usually named sock or some variation thereof. This structure has only a few entries, the most important of which are described below.
INET sockets are of type struct sock as defined in include/net/sock.h. INET socket variables are usually named sk or some variation thereof. This structure has many entries related to a wide variety of uses; there are many hacks and configuration dependent fields. The most important data members are described below:
/* look up host */
server = gethostbyname(SERVER_NAME);
/* get socket */
sockfd = socket(AF_INET, SOCK_STREAM, 0);
/* set up address */
address.sin_family = AF_INET;
address.sin_port = htons(PORT_NUM);
memcpy(&address.sin_addr,server->h_addr,server->h_length);
/* connect to server */
connect(sockfd, &address, sizeof(address));
The gethostbyname() function simply looks up a host (such as ``viper.cs.u.edu'') and returns a structure that contains an Internet (IP) address. This has very little to do with routing (only inasmuch as the host may have to query the network to look up an address) and is simply a translation from a human readable form (text) to a computer compatible one (an unsigned 4 byte integer).
The socket() call is more interesting. It creates a socket object, with the appropriate data type (a sock for INET sockets) and initializes it. The socket contains inode information and protocol specific pointers for various network functions. It also establishes defaults for queues (incoming, outgoing, error, and backlog), a dummy header info for TCP sockets, and various state information.
Finally, the connect() call goes to the protocol dependent connection routine (e.g., tcp_v4_connect() or udp_connect()). UDP simply establishes a route to the destination (since there is no virtual connection). TCP establishes the route and then begins the TCP connection process, sending a packet with appropriate connection and window flags set.
destroy_sock - net/ipv4/af_inet.c (195)
deletes any timers
calls any protocols specific destroy functions
frees the socket's queues
frees the socket structure itself
fib_lookup() - include/net/ip_fib.h (153)
calls tb_lookup() [= fn_hash_lookup()] on local and main tables
returns route or unreachable error
fn_hash_lookup() - net/ipv4/fib_hash.c (261)
looks up and returns route to an address
inet_create() - net/ipv4/af_inet.c (326)
calls sk_alloc() to get memory for sock
initializes sock structure:
sets proto structure to appropriate values for TCP or UDP
calls sock_init_data()
sets family,protocol,etc. variables
calls the protocol init function (if any)
inet_release() - net/ipv4/af_inet.c (463)
changes socket state to disconnecting
calls ip_mc_drop_socket to leave multicast group (if necessary)
sets owning socket's data member to NULL
calls sk->prot->close() [=TCP/UDP_close()]
ip_route_connect() - include/net/route.h (140)
calls ip_route_output() to get a destination address
returns if the call works or generates an error
otherwise clears the route pointer and try again
ip_route_output() - net/ipv4/route.c (1664)
calculates hash value for address
runs through table (starting at hash) to match addresses and TOS
if there is a match, updates stats and return route entry
else calls ip_route_output_slow()
ip_route_output_slow() - net/ipv4/route.c (1421)
if source address is known, looks up output device
if destination address is unknown, sets up loopback
calls fib_lookup() to find route in FIB
allocates memory new routing table entry
initializes table entry with source, destination, TOS, output device,
flags
calls rt_set_nexthop() to find next destination
returns rt_intern_hash(), which installs route in routing table
rt_intern_hash() - net/ipv4/route.c (526)
loops through rt_hash_table (starting at hash value)
if keys match, put rtable entry in front bucket
else put rtable entry into hash table at hash
>>> sock_close() - net/socket.c (476)
checks if socket exists (could be null)
calls sock_fasync() to remove socket from async list
calls sock_release()
>>> sock_create() - net/socket.c (571)
checks parameters
calls sock_alloc() to get an available inode for the socket and
initialize it
sets socket->type (to SOCK_STREAM, SOCK_DGRAM...)
calls net_family->create() [= inet_create()] to build sock structure
returns established socket
sock_init_data() - net/core/sock.c (1018)
initializes all generic sock values
sock_release() - net/socket.c (309)
changes state to disconnecting
calls sock->ops->release() [= inet_release()]
calls iput() to remove socket from inode list
sys_socket() - net/socket.c (639)
calls sock_create() to get and initialize socket
calls get_fd() to assign an fd to the socket
sets socket->file to fcheck() (pointer to file)
calls sock_release() if anything fails
tcp_close() - net/ipv4/tcp.c (1502)
check for errors
pops and discards all packets off incoming queue
sends messages to destination to close connection (if required)
tcp_connect() - net/ipv4/tcp_output.c (910)
completes connection packet with appropriate bits and window sizes set
puts packet on socket output queue
calls tcp_transmit_skb() to send packet, initiating TCP connection
tcp_v4_connect() - net/ipv4/tcp_ipv4.c (571)
checks for errors
calls ip_route_connect() to find route to destination
creates connection packet
calls tcp_connect() to send packet
udp_close() - net/ipv4/udp.c (954)
calls udp_v4_unhash() to remove socket from socket list
calls destroy_sock()
udp_connect() - net/ipv4/udp.c (900)
calls ip_route_connect() to find route to destination
updates socket with source and destination addresses and ports
changes socket state to established
saves the destination route in sock->dst_cache
This chapter presents the sending side of message trafficking. It provides an overview of the process, examines the layers packets travel through, details the actions of each layer, and summarizes the implementation code within the kernel.
An outgoing message begins with an application system call to write data to a socket. The socket examines its own connection type and calls the appropriate send routine (typically INET). The send function verifies the status of the socket, examines its protocol type, and sends the data on to the transport layer routine (such as TCP or UDP). This protocol creates a new buffer for the outgoing packet (a socket buffer, or struct sk_buff skb), copies the data from the application buffer, and fills in its header information (such as port number, options, and checksum) before passing the new buffer to the network layer (usually IP). The IP send functions fill in more of the buffer with its own protocol headers (such as the IP address, options, and checksum). It may also fragment the packet if required. Next the IP layer passes the packet to the link layer function, which moves the packet onto the sending device's xmit queue and makes sure the device knows that it has traffic to send. Finally, the device (such as a network card) tells the bus to send the packet.
dev_queue_xmit() - net/core/dev.c (579)
calls start_bh_atomic()
if device has a queue
calls enqueue() to add packet to queue
calls qdisc_wakeup() [= qdisc_restart()] to wake device
else calls hard_start_xmit()
calls end_bh_atomic()
DEVICE->hard_start_xmit() - device dependent, drivers/net/DEVICE.c
tests to see if medium is open
sends header
tells bus to send packet
updates status
inet_sendmsg() - net/ipv4/af_inet.c (786)
extracts pointer to socket sock
checks socket to make sure it is working
verifies protocol pointer
returns sk->prot[tcp/udp]->sendmsg()
ip_build_xmit - net/ipv4/ip_output.c (604)
calls sock_alloc_send_skb() to establish memory for skb
sets up skb header
calls getfrag() [= udp_getfrag()] to copy buffer from user space
returns rt->u.dst.output() [= dev_queue_xmit()]
ip_queue_xmit() - net/ipv4/ip_output.c (234)
looks up route
builds IP header
fragments if required
adds IP checksum
calls skb->dst->output() [= dev_queue_xmit()]
qdisc_restart() - net/sched/sch_generic.c (50)
pops packet off queue
calls dev->hard_start_xmit()
updates status
if there was an error, requeues packet
sock_sendmsg() - net/socket.c (325)
calls scm_sendmsg() [socket control message]
calls sock->ops[inet]->sendmsg() and destroys scm
>>> sock_write() - net/socket.c (399)
calls socki_lookup() to associate socket with fd/file inode
creates and fills in message header with data size/addresses
returns sock_sendmsg()
tcp_do_sendmsg() - net/ipv4/tcp.c (755)
waits for connection, if necessary
calls skb_tailroom() and adds data to waiting packet if possible
checks window status
calls sock_wmalloc() to get memory for skb
calls csum_and_copy_from_user() to copy packet and do checksum
calls tcp_send_skb()
tcp_send_skb() - net/ipv4/tcp_output.c (160)
calls __skb_queue_tail() to add packet to queue
calls tcp_transmit_skb() if possible
tcp_transmit_skb() - net/ipv4/tcp_output.c (77)
builds TCP header and adds checksum
calls tcp_build_and_update_options()
checks ACKs,SYN
calls tp->af_specific[ip]->queue_xmit()
tcp_v4_sendmsg() - net/ipv4/tcp_ipv4.c (668)
checks for IP address type, opens connection, port addresses
returns tcp_do_sendmsg()
udp_getfrag() - net/ipv4/udp.c (516)
copies and checksums a buffer from user space
udp_sendmsg() - net/ipv4/udp.c (559)
checks length, flags, protocol
sets up UDP header and address info
checks multicast
fills in route
fills in remainder of header
calls ip_build_xmit()
updates UDP status
returns err
This chapter presents the receiving side of message trafficking. It provides an overview of the process, examines the layers packets travel through, details the actions of each layer, and summarizes the implementation code within the kernel.
An incoming message begins with an interrupt when the system notifies the device that a message is ready. The device allocates storage space and tells the bus to put the message into that space. It then passes the packet to the link layer, which puts it on the backlog queue, and marks the network flag for the next ``bottom-half'' run.
The bottom-half is a Linux system that minimizes the amount of work done during an interrupt. Doing a lot of processing during an interrupt is not good precisely because it interrupts a running process; instead, interrupt handlers have a ``top-half'' and a ``bottom-half''. When the interrupt arrives, the top-half runs and takes care of any critical operations, such as moving data from a device queue into kernel memory. It then marks a flag that tells the kernel that there is more work to do - when the processor has time - and returns control to the current process. The next time the process scheduler runs, it sees the flag, does the extra work, and only then schedules any normal processes.
When the process scheduler sees that there are networking tasks to do it runs the network bottom-half. This function pops packets off of the backlog queue, matches them to a known protocol (typically IP), and passes them to that protocol's receive function. The IP layer examines the packet for errors and routes it; the packet will go into an outgoing queue (if it is for another host) or up to the transport layer (such as TCP or UDP). This layer again checks for errors, looks up the socket associated with the port specified in the packet, and puts the packet at the end of that socket's receive queue.
Once the packet is in the socket's queue, the socket will wake up the application process that owns it (if necessary). That process may then make or return from a read system call that copies the data from the packet in the queue into its own buffer. (The process may also do nothing for the time being if it was not waiting for the packet, and get the data off the queue when it needs it.)
>>> DEVICE_rx() - device dependent, drivers/net/DEVICE.c
(gets control from interrupt)
performs status checks to make sure it should be receiving
calls dev_alloc_skb() to reserve space for packet
gets packet off of system bus
calls eth_type_trans() to determine protocol type
calls netif_rx()
updates card status
(returns from interrupt)
inet_recvmsg() - net/ipv4/af_inet.c (764)
extracts pointer to socket sock
checks socket to make sure it is accepting
verifies protocol pointer
returns sk->prot[tcp/udp]->recvmsg()
ip_rcv() - net/ipv4/ip_input.c (395)
examines packet for errors:
invalid length (too short or too long)
incorrect version (not 4)
invalid checksum
calls __skb_trim() to remove padding
defrags packet if necessary
calls ip_route_input() to route packet
examines and handle IP options
returns skb->dst->input() [= tcp_rcv,udp_rcv()]
net_bh() - net/core/dev.c (835)
(run by scheduler)
if there are packets waiting to go out, calls qdisc_run_queues()
(see sending section)
while the backlog queue is not empty
let other bottom halves run
call skb_dequeue() to get next packet
if the packet is for someone else (FASTROUTED) put onto send queue
loop through protocol lists (taps and main) to match protocol type
call pt_prev->func() [= ip_rcv()] to pass packet to appropriate
protocol
call qdisc_run_queues() to flush output (if necessary)
netif_rx() - net/core/dev.c (757)
puts time in skb->stamp
if backlog queue is too full, drops packet
else
calls skb_queue_tail() to put packet into backlog queue
marks bottom half for later execution
sock_def_readable() - net/core/sock.c (989)
calls wake_up_interruptible() to put waiting process on run queue
calls sock_wake_async() to send SIGIO to socket process
sock_queue_rcv_skb() - include/net/sock.h (857)
calls skb_queue_tail() to put packet in socket receive queue
calls sk->data_ready() [= sock_def_readable()]
>>> sock_read() - net/socket.c (366)
sets up message headers
returns sock_recvmsg() with result of read
sock_recvmsg() - net/socket.c (338)
reads socket management packet (scm) or packet by
calling sock->ops[inet]->recvmsg()
tcp_data() - net/ipv4/tcp_input.c (1507)
shrinks receive queue if necessary
calls tcp_data_queue() to queue packet
calls sk->data_ready() to wake socket
tcp_data_queue() - net/ipv4/tcp_input.c (1394)
if packet is out of sequence:
if old, discards immediately
else calculates appropriate storage location
calls __skb_queue_tail() to put packet in socket receive queue
updates connection state
tcp_rcv_established() - net/ipv4/tcp_input.c (1795)
if fast path
checks all flags and header info
sends ACK
calls _skb_queue_tail() to put packet in socket receive queue
else (slow path)
if out of sequence, sends ACK and drops packet
check for FIN, SYN, RST, ACK
calls tcp_data() to queue packet
sends ACK
tcp_recvmsg() - net/ipv4/tcp.c (1149)
checks for errors
wait until there is at least one packet available
cleans up socket if connection closed
calls memcpy_toiovec() to copy payload from the socket buffer into
the user space
calls cleanup_rbuf() to release memory and send ACK if necessary
calls remove_wait_queue() to wake process (if necessary)
udp_queue_rcv_skb() - net/ipv4/udp.c (963)
calls sock_queue_rcv_skb()
updates UDP status (frees skb if queue failed)
udp_rcv() - net/ipv4/udp.c (1062)
gets UDP header, trims packet, verifies checksum (if required)
checks multicast
calls udp_v4_lookup() to match packet to socket
if no socket found, send ICMP message back, free skb, and stop
calls udp_deliver() [= udp_queue_rcv_skb()]
udp_recvmsg() - net/ipv4/udp.c (794)
calls skb_recv_datagram() to get packet from queue
calls skb_copy_datagram_iovec() to move the payload from the socket buffer
into the user space
updates the socket timestamp
fills in the source information in the message header
frees the packet memory
This chapter presents the pure routing side (by IP forwarding) of message traffic. It provides an overview of the process, examines the layers packets travel through, details the actions of each layer, and summarizes the implementation code within the kernel.
See Figure 7.1 for an abstract diagram of the the forwarding process. (It is essentially a combination of the receiving and sending processes.)
A forwarded packet arrives with an interrupt when the system notifies the device that a message is ready. The device allocates storage space and tells the bus to put the message into that space. It then passes the packet to the link layer, which puts it on the backlog queue, marks the network flag for the next ``bottom-half'' run, and returns control to the current process.
When the process scheduler next runs, it sees that there are networking tasks to do and runs the network ``bottom-half''. This function pops packets off of the backlog queue, matches them to IP, and passes them to the receive function. The IP layer examines the packet for errors and routes it; the packet will go up to the transport layer (such as TCP or UDP if it is for this host) or sideways to the IP forwarding function. Within the forwarding function, IP checks the packet and sends an ICMP message back to the sender if anything is wrong. It then copies the packet into a new buffer and fragments it if necessary.
Finally the IP layer passes the packet to the link layer function, which moves the packet onto the sending device's xmit queue and makes sure the device knows that it has traffic to send. Finally, the device (such as a network card) tells the bus to send the packet.
dev_queue_xmit() - net/core/dev.c (579)
calls start_bh_atomic()
if device has a queue
calls enqueue() to add packet to queue
calls qdisc_wakeup() [= qdisc_restart()] to wake device
else calls hard_start_xmit()
calls end_bh_atomic()
DEVICE->hard_start_xmit() - device dependent, drivers/net/DEVICE.c
tests to see if medium is open
sends header
tells bus to send packet
updates status
>>> DEVICE_rx() - device dependent, drivers/net/DEVICE.c
(gets control from interrupt)
performs status checks to make sure it should be receiving
calls dev_alloc_skb() to reserve space for packet
gets packet off of system bus
calls eth_type_trans() to determine protocol type
calls netif_rx()
updates card status
(returns from interrupt)
ip_finish_output() - include/net/ip.h (140)
sets sending device to output device for given route
calls output function for destination [= dev_queue_xmit()]
ip_forward() - net/ipv4/ip_forward.c (72)
checks for router alert
if packet is not meant for any host, drops it
if TTL has expired, drops packet and sends ICMP message back
if strict route cannot be followed, drops packet and sends ICMP
message back to sender
if necessary, sends ICMP message telling sender packet is redirected
copies and releases old packet
decrements TTL
if there are options, calls ip_forward_options() to set them
calls ip_send()
ip_rcv() - net/ipv4/ip_input.c (395)
examines packet for errors:
invalid length (too short or too long)
incorrect version (not 4)
invalid checksum
calls __skb_trim() to remove padding
defrags packet if necessary
calls ip_route_input() to route packet
examines and handle IP options
returns skb->dst->input() [= ip_forward()]
ip_route_input() - net/ipv4/route.c (1366)
calls rt_hash_code() to get index for routing table
loops through routing table (starting at hash) to find match for packet
if it finds match:
updates stats for route (time and usage)
sets packet destination to routing table entry
returns success
else
checks for multicasting addresses
returns result of ip_route_input_slow() (attempted routing)
ip_route_output_slow() - net/ipv4/route.c (1421)
if source address is known, looks up output device
if destination address is unknown, set up loopback
calls fib_lookup() to find route
allocates memory new routing table entry
initializes table entry with source, destination, TOS, output device,
flags
calls rt_set_nexthop() to find next destination
returns rt_intern_hash(), which installs route in routing table
ip_send() - include/net/ip.h (162)
calls ip_fragment() if packet is too big for device
calls ip_finish_output()
net_bh() - net/core/dev.c (835)
(run by scheduler)
if there are packets waiting to go out, calls qdisc_run_queues()
(see sending section)
while the backlog queue is not empty
let other bottom halves run
call skb_dequeue() to get next packet
if the packet is for someone else (FASTROUTED) put onto send queue
loop through protocol lists (taps and main) to match protocol type
call pt_prev->func() [= ip_rcv()] to pass packet to appropriate
protocol
call qdisc_run_queues() to flush output (if necessary)
netif_rx() - net/core/dev.c (757)
puts time in skb->stamp
if backlog queue is too full, drops packet
else
calls skb_queue_tail() to put packet into backlog queue
marks bottom half for later execution
qdisc_restart() - net/sched/sch_generic.c (50)
pops packet off queue
calls dev->hard_start_xmit()
updates status
if there was an error, requeues packet
rt_intern_hash() - net/ipv4/route.c (526)
puts new route in routing table
This chapter presents the basics of IP Routing. It provides an overview of how routing works, examines how routing tables are established and updated, and summarizes the implementation code within the kernel.
The neighbor table contains address information for computers that are physically connected to the host (hence the name ``neighbor''). It includes information on which device connects to which neighbor and what protocols to use in exchanging data. Linux uses the Address Resolution Protocol (ARP) to maintain and update this table; it is dynamic in that entries are added when needed but eventually disappear if not used again within a certain time. (However, administrators can set up entries to be permanent if doing so makes sense.)
Linux uses two complex sets of routing tables to maintain IP addresses: an all-purpose Forwarding Information Base (FIB) with directions to every possible address, and a smaller (and faster) routing cache with data on frequently used routes. When an IP packet needs to go to a distant host, the IP layer first checks the routing cache for an entry with the appropriate source, destination, and type of service. If there is such an entry, IP uses it. If not, IP requests the routing information from the more complete (but slower) FIB, builds a new cache entry with that data, and then uses the new entry. While the FIB entries are semi-permanent (they usually change only when routers come up or go down) the cache entries remain only until they become obsolete (they are unused for a ``long'' period).
struct neigh_table *neigh_tables - this global variable is a pointer to a list of neighbor tables; each table contains a set of general functions and data and a hash table of specific information about a set of neighbors. This is a very detailed, low level table containing specific information such as the approximate transit time for messages, queue sizes, device pointers, and pointers to device functions.
Neighbor Table (struct neigh_table) Structure - this structure (a list element) contains common neighbor information and table of neighbor data and pneigh data. All computers connected through a single type of connection (such as a single Ethernet card) will be in the same table.
Neighbor Data (struct neighbour) Structure - these structures contain the specific information about each neighbor.
The Forwarding Information Base (FIB) is the most important routing structure in the kernel; it is a complex structure that contains the routing information needed to reach any valid IP address by its network mask. Essentially it is a large table with general address information at the top and very specific information at the bottom. The IP layer enters the table with the destination address of a packet and compares it to the most specific netmask to see if they match. If they do not, IP goes on to the next most general netmask and again compares the two. When it finally finds a match, IP copies the ``directions'' to the distant host into the routing cache and sends the packet on its way. See Figures 8.3 and 8.4 for the organization and data structures used in the FIB - note that Figure 8.3 shows some different FIB capabilities, like two sets of network information for a single zone, and so does not follow the general example.)
struct fib_table *local_table, *main_table - these global variables are the access points to the FIB tables; they point to table structures that point to hash tables that point to zones. The contents of the main_table variable are in /proc/net/route.
FIB Table fib_table Structure - include/net/ip_fib.h - these structures contain function jump tables and each points to a hash table containing zone information. There are usually only one or two of these.
Netmask Table fn_hash Structure - net/ipv4/fib_hash.c - these structures contain pointers to the individual zones, organized by netmask. (Each zone corresponds to a uniquely specific network mask.) There is one of these for each FIB table (unless two tables point to the same hash table).
Network Zone fn_zone Structure - net/ipv4/fib_hash.c - these structures contain some hashing information and pointers to hash tables of nodes. There is one of these for each known netmask.
Network Node Information fib_node Structure - net/ipv4/fib_hash.c - these structures contain the information unique to each set of addresses and a pointer to information about common features (such as device and protocols); there is one for each known network (unique source/destination/TOS combination).
Network Protocol Information (fib_info) Structure - include/net/ip_fib.h - these structures contain protocol and hardware information that are specific to an interface and therefore common to many potential zones; several networks may be addressable through the same interface (like the one that leads to the rest of the Internet). There is one of these for each interface.
FIB Traversal Example:
The routing cache is the fastest method Linux has to find a route; it keeps every route that is currently in use or has been used recently in a hash table. When IP needs a route, it goes to the appropriate hash bucket and searches the chain of cached routes until finds a match, then sends the packet along that path. (See Section 8.2.2 for what happens when the route is not yet in the cache.) Routes are chained in order, most frequently used first, and have timers and counters that remove them from the table when they are no longer in use. See Figure 8.5 for an abstract overview and Figures 8.6 and 8.7 for detailed diagrams of the data structures.
struct rtable *rt_hash_table[RT_HASH_DIVISOR] - this global variable contains 256 buckets of (pointers to) chains of routing cache (rtable) entries; the hash function combines the source address, destination address, and TOS to get an entry point to the table (between 0 and 255). The contents of this table are listed in /proc/net/rt_cache.
Routing Table Entry (rtable) Structure - include/net/route.h - these structures contain the destination cache entries and identification information specific to each route.
Destination Cache (dst_entry) Structure - include/net/dst.h - these structures contain pointers to specific input and output functions and data for a route.
Neighbor Link (neighbor) Structure - include/net/neighbor.h - these structures, one for each host that is exactly one hop away, contain pointers to their access functions and information.
Routing Cache Traversal Example:
The neighbor table changes as network traffic is exchanged. If a host needs to send something to an address that is on the local subnet but not already in the neighbor table, it simply broadcasts an ARP request and adds a new entry in the neighbor table when it gets a reply. Periodically entries time out and disappear; this cycle continues indefinitely (unless a route has been specifically marked as ARP permanent). The kernel handles most changes automatically.
The FIB on most hosts and even routers remains static; it is filled in during initialization with every possible zone to route through all connected routers and never changes unless one of the routers goes down. (See Chapter 9 for details on IP routing daemons). Changes have to come through external ioctl() calls to add or delete zones.
The routing cache changes frequently depending on message traffic. If a host needs to send packets to a remote address, it looks up the address in the routing cache (and FIB if necessary) and sends the packet off through the appropriate router. On a host connected to a LAN with one router to the Internet, every entry will point to either a neighbor or the router, but there may be many entries that point to the router (one for each distant address). The entries are created as connections are made and time out quickly when traffic to that address stops flowing. Everything is done with IP level calls to create routes and kernel timers to delete them.
arp_rcv() - net/ipv4/arp.c (542)
checks for errors (non-ARP device, no device, packet not for host,
device type does not match, etc.)
check for operation - only understands REPLY and REQUEST
extracts data from packet
check for bad requests - loopback or multicast addresses
checks for duplicate address detection packet (sends reply if necessary)
if the message is a request and ip_route_input() is true:
if the packet is a local one:
calls neigh_event_ns() to look up and update neighbor that sent packet
checks for hidden device (does not reply if hidden)
sends reply with the device address
otherwise:
calls neigh_event_ns() to look up and update neighbor that sent packet
calls neigh_release()
if necessary, calls arp_send() with the address
otherwise calls pneigh_enqueue() and returns 0
if the message is a reply:
calls __neigh_lookup()
checks to see if multiple ARP replies have come in; keeps only the
fastest (first) one
calls neigh_update() to update ARP entry
calls neigh_release()
frees the skbuffer and returns 0
arp_send() - net/ipv4/arp.c (434)
checks to make sure device supports ARP
allocates an skbuffer
fills in buffer header information
fills in the ARP information
calls dev_queue_xmit() with the finished packet
arp_req_get() - net/ipv4/arp.c (848)
calls __neigh_lookup() to find entry for given address
copies data from neighbor entry to arpreq entry
returns 0 if found or ENXIO if address not in ARP table
fib_get_procinfo() - net/ipv4/fib_frontend.c (109)
prints header and results of main_table->fn_hash_get_info() for proc FS
fib_lookup() - include/net/ip_fib.h (153)
calls tb_lookup() [= fn_hash_lookup()] on local_table and main_table
if either one has an entry, it fills in fib_result and returns 0
else returns unreachable error
fib_node_get_info() - net/ipv4/fib_semantics.c (971)
prints fib_node and fib_info contents for proc FS
fib_validate_source() - net/ipv4/fib_frontend.c (191)
tests incoming packet's device and address
returns error code if something is wrong
returns 0 if packet seems legal
fn_hash() - net/ipv4/fib_hash.c (108)
performs a hash function on a destination address:
u32 h = ntohl(daddr)>>(32 - fib_zone->fz_order);
h ^= (h>>20);
h ^= (h>>10);
h ^= (h>>5);
h &= FZ_HASHMASK(fz); // FZ_HASHMASK is 15 for almost all zones
fn_hash_get_info() - net/ipv4/fib_hash.c (723)
loops through zones in a FIB table printing fib_node_get_info() for
proc FS
fn_hash_lookup() - net/ipv4/fib_hash.c (261)
loops through the zones in the given table
loops through the nodes in each zone (starting at the hash entry)
if the netmasks (node and destination) match
checks the TOS and node status
calls fib_semantic_match() to check packet type
fills in fib_result with success data and returns 0
returns 1 if nothing matched
fn_new_zone() - net/ipv4/fib_hash.c (220)
allocates memory (in kernel) for new zone
allocates space for 16 node buckets for zone (except first zone -
0.0.0.0 [loopback] - which only gets one)
stores netmask (leftmost n bits on, where n is the position of the
zone in the table)
searches for more specific zone in parent table
inserts zone into zone list (most specific zone is head)
installs new zone into parent table
returns new zone
fz_chain() - net/ipv4/fib_hash.c (133)
calls fn_hash() to get a hash value
returns the fib_node in the fib_zone at the hash index
ip_dev_find() - net/ipv4/fib_frontend.c (147)
looks up and returns the device with a given address in the local table
ip_route_connect() - include/net/route.h (140)
calls ip_route_output() to get a destination address
returns if the call works or generates an error
otherwise clears the route pointer and try again
ip_route_input() - net/ipv4/route.c (1366)
calculates hash value for address
runs through table (starting at hash) to find connection match
(source, destination, TOS, and IIF/OIF)
if there is a match, updates stats and returns routing entry
else calls ip_route_input_slow()
ip_route_input_slow() - net/ipv4/route.c (1097)
creates a routing table cache key
checks for special addresses (like loopback, broadcast, or errors)
calls fib_lookup() to find route
allocates memory for new routing table entry
initializes table entry with source, destination, TOS, output device,
flags
calls fib_validate_source() to test packet source
printks message and returns error if source is bad
calls rt_set_nexthop() to find next destination (neighbor)
returns rt_intern_hash(), which installs route in routing table
ip_route_output() - net/ipv4/route.c (1664)
calculates hash value for address
runs through table (starting at hash) to find connection match
(source, destination, TOS, and IIF/OIF)
if there is a match, updates stats and returns routing entry
else calls ip_route_output_slow()
ip_route_output_slow() - net/ipv4/route.c (1421)
creates a routing table cache key
if source address is known, calls ip_dev_find to determine output device
if destination address is unknown, set up loopback
calls fib_lookup() to find route
allocates memory for new routing table entry
initializes table entry with source, destination, TOS, output device,
flags
calls rt_set_nexthop() to find next destination (neighbor)
returns rt_intern_hash(), which installs route in routing table
ip_rt_ioctl() - net/ipv4/fib_frontend.c (250)
switches on SIOCADDRT or SIOCDELRT (returns EINVAL otherwise)
verifies permission and copies argument to kernel space
converts copied argument to an rtentry structure
if deleting a route, calls fib_get_table() and table->delete()
else calls fib_new_table() and table->insert()
frees argument space and returns 0 for success
neigh_event_ns() - net/core/neighbour.c (760)
calls __neigh_lookup() to find up address in neighbor table
calls neigh_update()
returns pointer to designated neighbor
neigh_update() - net/core/neighbour.c (668)
checks permissions to modify table
checks neighbor status if this is not a new entry
compares given address to cached one:
if null or device has no address, uses current address
if different, check override flag
calls neigh_sync() to verify neighbor is still up
updates neighbor contact time
if old entry was valid and new one does not change address, returns 0
if new address is different from old, replaces old with new
if new and old states match, returns 0
calls neigh_connect() or neigh_suspect() to make/check connection
if old state was invalid:
goes through packets in ARP queue, calling the neighbor output()
function on each
purges the ARP queue
returns 0
rt_cache_get_info() - net/ipv4/route.c (191)
prints header and all elements of rt_hash_table for proc FS
rt_hash_code() - net/ipv4/route.c (18)
uses source address, destination address, and type of service to
determine (and return) a hash value:
hash = ((daddr&0xF0F0F0F0)>>4)|((daddr&0x0F0F0F0F)<<4);
hash = hash^saddr^tos;
hash = hash^(hash>>16);
hash = (hash^(hash>>8)) & 0xFF;
rt_intern_hash() - net/ipv4/route.c (526)
puts new route in routing table
This chapter presents dynamic routing as performed by a router (as opposed to an end host computer). It provides an overview of how the routed program implements routing protocols under Linux, examines how it modifies the kernel routing tables, and summarizes the implementation code.
However, a router must make decisions on where to send traffic. There may be several routes to a destination, and the router must select one (based on distance, measured in hops or some other metric such as the nebulous quality of service). The Routing Information Protocol (RIP) is a simple protocol that allows routing computers to track the distance to various destinations and to share this information amongst themselves.
Using RIP, each node maintains a table that contains the distance from itself to other networks and the route along which it will send packets to that destination. Periodically the routers update each other; when shorter routes becomes apparent, the node updates its table. Updates are simply RIP messages with the destination address and metric components of this table. See Figure 9.1 for a diagram of an RIP routing table and an RIP packet.
When the update timer expires, every TIMER_RATE seconds, routed goes through every entry in both tables and updates their timers. Entries which are out of date are set to a distance of infinity (HOPCNT_INFINITY) and entries which are too old are deleted (only from the RIP table, not from the kernel's FIB). Finally, it sends an update to its neighboring routers. This update contains the new table information (response messages) for any entries which have changed since the last update.
routed leaves the actual routing to the normal kernel routing mechanisms; all it does is update the kernel's tables based on information from other routers and pass on its own routing information. The updates then change how the kernel routes packets, but routed itself does not actually do any routing.
The routed source is available as a package separate from the kernel source (Red Hat Linux uses the rpm package manager). The code below is from the netkit-routed-0.10 source code package, 8 March 1997. This package is available from the www.redhat.com/apps/download web page; specifically this came from www.redhat.com/swt/src/netkit-routed-0.10.src.html. Once downloaded, root can install the package with the following commands (starting from the directory with the package):
rpm -i netkit-routed-0.10.src.rpmThis creates a /usr/src/redhat/SOURCES/netkit-routed-0.10 directory and fills it with the source code for the routed program. This process should be similar (but is undoubtably not exactly the same) for other Linux distributions.
cd /usr/src/redhat/SOURCES
tar xzf netkit-routed-0.10.tar.gz
ifinit() - SOURCES/routed/startup.c (88)
opens a UDP socket
calls ioctl(SIOCFIGCONF) to get interface configuration
loops through interfaces:
calls ioctl() to get flags, broadcast address, metric, and netmask
creates a new interface structure
copies info into interface structure
calls addrouteforif() to add routing entry for interface
sets supplier variable if necessary
closes socket
process() - SOURCES/routed/main.c (298)
starts a continuous loop:
receives a packet (waits)
verifies that packet is correct size
calls rip_input() to handle (RIP) packet
rip_input() - SOURCES/routed/input.c (60)
traces input if necessary
checks packet to make sure protocol and address are supported
checks for RIP version (cannot be 0)
switch based on packet content -
if packet is a request:
checks request for validity
if request is for all entries, calls supply()
else looks up requested address, builds and sends response packet
if packet is a trace on or off:
verifies request came from a valid port
if all is in order, sets trace to on or off
if packet is a response:
verifies response came from a router
updates timer for interface
loops through each entry in received packet:
parses route information
validates address family, host, and metric information
updates hop count (adds metric in message to hop count to router
that send message, subject to HOPCNT_INFINITY maximum)
calls rtlookup() to find address in routing table
if this seems to be a new route:
calls rtfind() to look for an equivalent route
if it really is new, calls rtadd() and returns
calls rtchange() to modify route if necessary (new route or
hopcount change)
updates route timers
if there were changes:
sends an update if neccessary
updates general update timer information
>>> routed main() - SOURCES/routed/main.c (78)
opens routed log file
calls getservbyname() to get UDP router
sets up a UDP socket for RIP message traffic
runs through command line arguments to set flags
if not debugging, forks and runs program in new session (parent dies)
calls rtinit() to initialize data tables
calls ifinit() to fill in interface information
calls toall() to request info from all other routers
installs signal handlers for ALRM,HUP,TERM,INT,USR1,and USR2
starts a continuous loop:
if in need of update, sets up timer variables
calls select() to wait for traffic
if select() returns an error (other than EINTR), logs it
if select() times out (time for update)
calls toall() to broadcast update
resets timer variables
if there is traffic waiting on the socket, calls process()
rtadd() - SOURCES/routed/tables.c (138)
verifies address family is in proper range
calls family af_rtflags() function to set routing flags
determines hash value for appropriate table (host or net)
creates and fills in new rt_entry structure
calls insque() to add entry to table
calls rtioctl() to add entry to kernel table
if call fails:
if route should work, calls family af_format() to add destination
and gateway to kernel tables
if host is unreachable, removes and frees entry
rtchange() - SOURCES/routed/tables.c (207)
determines if change necessitates adding or deleting gateways
calls rtioctl() to add and/or delete routes
rtfind() - SOURCES/routed/tables.c (100)
determines hash value for host table
loops through table; returns entry if addresses are equal
determines hash value for net table
goes back to loop through table, this time returning entry if a call
to family af_netmatch() function returns true
returns null (0) if no match
rtinit() - SOURCES/routed/tables.c (336)
loops through the net hash table, setting forward and back pointers
loops through the host hash table, setting forward and back pointers
rtioctl() - SOURCES/routed/tables.c (346)
fills in rtentry structure from parameters
outputs trace actions if necessary
calls ioctl(SIOCADDRT or SIOCDELRT) to update kernel table
returns result of ioctl() call (or -1 for erroneous parameter)
rtlookup() - SOURCES/routed/tables.c (65)
determines hash value for address
runs through host table looking for match
if unsuccessful at first, tries again with net table
returns pointer to entry or null (0)
sndmsg() - SOURCES/routed/output.c (77)
calls the appropriate family output function
traces the packet if necessary
supply() - SOURCES/routed/ouput.c (91)
creates an RIP response message
loops through the routing host table
loops through the routing entries
checks to see if routing host needs the entry
if so, puts routing info into packet and sends it
goes back and does it again with the routing net table
timer() - SOURCES/routed/timer.c (56)
updates timer variables
loops through the host table
updates timer information for each entry
deletes entry if it is too old
changes metric to infinity if it is getting old
goes back and does it again with net table
calls toall() if update is due
toall() - SOURCES/routed/output.c (55)
loops through interfaces:
sets destination address to broadcast or specific address
calls passed function [sndmsg() or supply()] with address
This is an overview of the Linux source directory structure (not all branches are shown:
/usr/src/linux/
These tags work even as you make changes to the source files, though they will run slower as more and more changes are made. EMACS stores the tags in a file (defaulted to TAGS) with each reference, filename, and line number. If the tag is not at the stored line number, EMACS will search the file to find the new location.
The command to make a tags file is:
etags filenameThe command to append new information onto a tags file is:
etags -a filenameThese put the new tags into the file TAGS in the current directory. Filenames are stored as given, so absolute references will always refer to the same files while relative references depend on the position of the TAGS file. (Read the man page for etags for more information).
For example, to create a tags file for the ipv4 source files, enter:
etags /usr/src/linux/net/ipv4/*.cTo add the header files, enter:
etags -a /usr/src/include/net/*.hThe TAGS file will now contain quick references to all the C source code and header information in those directories.
This is a quick step-by-step guide to recompiling and installing a kernel from scratch.
mv /lib/modules/2.2.xx /lib/modules/2.2.xx-old(Note that you will not have to do this if you are compiling a completely new version; the old ones will still be in /lib/modules/2.2.xx when you build version 2.2.yy.)
cp arch/i386/boot/bzImage /boot/vmlinuz-2.2.xx
ln -sf /boot/vmlinuz-2.2.xx /boot/vmlinuz
cp System.map /boot/System.map-2.2.xx
ln -sf /boot/System.map-2.2.xx /boot/System.map
/sbin/mkinitrd /boot/initrd-2.2.xx.img 2.2.xx
Linux is a constantly changing operating system; updates can be released every few months. There are two ways to install a new kernel version: downloading the new source in its entirety or downloading patches and applying them.
Downloading the entire source may be preferable to guarantee everything works properly. To do so, download the latest kernel source and install (untar) it. Note that this will (probably) be a complete distribution, not a machine-specific one, and will contain a lot of extra code. Much of this can be deleted, but the configuration Makefiles rely on some for information. If space is an issue, delete the *.c and *.h files in the non-i386 arch/ and include/asm-* directories, but tread lightly.
Downloading patches may be quicker to do, but is somewhat harder. Because of distribution variations, changes you have made, or other modifications the patches may not quite work properly. You must apply patch files in order (to go from 2.2.12 to 2.2.14, first apply patch 2.2.13 then apply 2.2.14). Nevertheless, patches may be preferable because they work on an existing directory tree.
Once you have downloaded a patch (and unzipped it, if necessary), simply put it in the directory above linux (e.g., /usr/src/) and run the patch program to install it:
patch -Np0 -verbose -r rejfile < patch-2.2.xx (where xx is the patch version)The -N option ignores patches that are already applied, and the -p0 assumes the patch wants to apply itself to a source in a linux directory. The -r rejfile option puts all the patch rejects into one file (rejfile) - which may or may not be what you want to do. If you have not kept the entire source distribution, you will have to skip many changes (for different processor architectures) by simply hitting ``ENTER'' at the ``patch which file'' and ``ignore patch'' prompts. Once you are comfortable with the process, run it without the -verbose and -r rejfile options.
Once you have a new kernel version, follow the instructions on rebuilding the kernel to actually start using it. You probably will not have to change any of the configurations options, but you will almost definitely want to run make clean to remove any old object files.
This chapter presents the Linux module system. It provides an overview of how modules work, describes how to install and remove them, and presents an example program.
Another advantage of modules is that the kernel can load and unload them dynamically (and automatically with the kerneld daemon). This means that a (super) user can load a module, test it, unload it, and debug it repeatedly without having to reboot the computer. This document assumes that the user has superuser access (you must be root to install and remove modules) and the kernel is configured for modules. (With a monolithic kernel, it is possible to set configuration options not to even allow modules.)
This is the general module format:
#define MODULE
#include <linux/module.h>
/* ... other required header files ... */
/*
* ... module declarations and functions ...
*/
int init_module() {
/* code kernel will call when installing module */
}
void cleanup_module() {
/* code kernel will call when removing module */
}
Modules that use the kernel source must be compiled with gcc with the option -I/usr/src/linux/include; this ensures that the files included will be from the proper source tree.
Note that not all kernel variables are exported for modules to use, even if the code declares them to be extern. The /proc/ksyms file or ksyms program display the exported symbols (not many of which are useful for networking). Recent Linux kernels export both the symbol and its version number using the EXPORT_SYMBOL(x) macro. For user created variables, use the EXPORT_SYMBOL_NOVERS(x) macro instead or the linker will not retain the variable in the kernel symbol table. Module writers may also want to use the EXPORT_NO_SYMBOLS macro; modules export all of their variables by default.
The insmod program installs a module; it first links the module with the kernel's exported symbol table to resolve references and then installs the code in kernel space.
/sbin/insmod module_name
The rmmod program removes an installed module and any references that it has exported.
/sbin/rmmod module_name
The lsmod program lists all the currently installed modules:
/sbin/lsmod
Module Size Used by
cdrom 13368 0 (autoclean) [ide-cd]
3c59x 19112 1 (autoclean)
simple_module.c
/* simple_module.c
*
* This program provides an example of how to install a trivial module
* into the Linux kernel. All the module does is put a message into
* the log file when it is installed and removed.
*
*/
#define MODULE
#include <linux/module.h>
/* kernel.h contains the printk function */
#include <linux/kernel.h>
/*************************************************************** init_module
* the kernel calls this function when it loads the module */
int init_module() {
printk("<1>The simple module installed itself properly.\n");
return 0;
} /* init_module */
/************************************************************ cleanup_module
* the kernel calls this function when it removes the module */
void cleanup_module() {
printk("<1>The simple module is now uninstalled.\n");
} /* cleanup_module */
This is the Makefile:
# Makefile for simple_module CC = gcc -I/usr/src/linux/include/config CFLAGS = -O2 -D__KERNEL__ -Wall simple_module.o: simple_module.c install: /sbin/insmod simple_module remove: /sbin/rmmod simple_module
To use (must be root):
root# make root# make install root# make remove root# tail /var/log/messages ... kernel: The simple module installed itself properly. ... kernel: The simple module is now uninstalled.
This chapter presents the virtual proc file system. It provides an overview of how the file system works, shows how the existing network code uses the system, and details how to write and use proc entries from programs.
The proc directory has many subdirectories - one for each running process and others for subsystems such as file systems, interfaces, terminals, and networking (/proc/net). There are also many files in the main /proc directory itself - interrupts, ioports, loadavg, and version to name a few. Within each process subdirectory (named for the process number) are files that describe the process' command line, current working directory, status, and so on.
The kernel traps proc file access and instead of executing ``normal'' file operations on them calls special (individually registered) functions instead. When a file in the /proc directory is ``created'', it is registered with a set of functions that tell the kernel what to do when the file is read from or written to. Most entries only allow reads and they simply print out the state of certain system variables for use by other programs or for perusal by knowledgeable users.
The only tricky thing about using proc files is that the kernel calls the information generation function each and every time the file is read; subsequent reads of a changing file without copying and buffering the results may yield very different results. The best way to use a proc file is to read it into a PAGE_SIZE-byte buffer. This will read the entire entry at once and the buffer will then allow consistent random accesses.
static int read_proc_function(char *buf,char **start,off_t offset,int len,int unused)
This is the function that the Linux kernel will call whenever it tries to read from the newly created proc ``file''. The only parameter that is usually significant is buf - a pointer to the buffer the kernel makes available for storing information. The others normally will not change. (read_proc_function is of course the name of the new function.)
Typically this function prints out a header, iterates through a list or table printing its contents (using the normal sprintf routine), and returns the length of the resulting string. The only limitation is that the buffer (buf) is at most PAGE_SIZE bytes (this is at least 4KB).
For an example of this kind of function, look at the fib_get_procinfo() function beginning on line 109 of net/ipv4/fib_frontend.c. This function displays the contents of the main FIB table.
#include <linux/proc_fs.h>
struct proc_dir_entry new_proc_entry = {
0, // low_ino - inode number (0 for dynamic)
5, // namelen - length of entry name
"entry", // name
S_IFREG | S_IRUGO, // mode
1, // nlinks
0, // uid - owner
0, // gid - group
0, // size - not used
NULL, // ops - inode operations (use default)
&read_proc_function // read_proc - address of read function
// leave rest blank!
}
The contents of this block can be used as shown by simply replacing the namelen, name, and read_proc_function fields with the desired values. Note that many of the kernel defined entries have predefined inode numbers (like PROC_NET_ROUTE, part of an enumeration defined in include/linux/proc_fs.h.
For an example of this kind of entry, look at the __init_func() function beginning on line 607 of net/ipv4/fib_frontend.c. This functions calls proc_net_register() (described below) with a newly created proc_dir_entry structure.
int proc_register(struct proc_dir_entry *dir, struct proc_dir_entry *entry)
int proc_net_register(struct proc_dir_entry *entry)
dir is a pointer to the directory in which the entry belongs - &proc_root and proc_net (defined in include/proc_fs.h) are probably the most useful. entry is a pointer to the entry itself, as created above. These two functions are identical except that proc_net_register automatically uses the /proc/net directory. They return either 0 (success) or EAGAIN (if there are no available inodes).
int proc_unregister(struct proc_dir_entry *dir,int inode)
int proc_net_unregister(int inode)
dir is the proc directory in which the file resides, and inode is the inode number of the file. (The inode is available in the entry's struct proc_dir_entry.low_ino field if it is not a constant.) Again, these functions are identical except that proc_net_unregister automatically uses the /proc/net directory. They return either 0 (success) or EINVAL (if there is no such entry).
simple_entry.c
/* simple_entry.c
*
* This program provides an example of how to install an entry into the
* /proc File System. All this entry does is display some statistical
* information about IP.
*/
#define MODULE
#include <linux/module.h>
/* proc_fs.h contains proc_dir_entry and register/unregister prototypes */
#include <linux/proc_fs.h>
/* ip.h contains the ip_statistics variable */
#include <net/ip.h>
/************************************************************ show_ip_stats
* this function is what the /proc FS will call when anything tries to read
* from the file /proc/simple_entry - it puts some of the kernel global
* variable ip_statistics's contents into the return buffer */
int show_ip_stats(char *buf,char **start,off_t offset,int len,int unused) {
len = sprintf(buf,"Some IP Statistics:\nIP Forwarding is ");
if (ip_statistics.IpForwarding)
len += sprintf(buf+len,"on\n");
else
len += sprintf(buf+len,"off\n");
len += sprintf(buf+len,"Default TTL: %lu\n",ip_statistics.IpDefaultTTL);
len += sprintf(buf+len,"Frag Creates: %lu\n",ip_statistics.IpFragCreates);
/* this could show more.... */
return len;
} /* show_ip_stats */
/**************************************************************** test_entry
* this structure is a sort of registration form for the /proc FS; it tells
* the FS to allocate a dynamic inode, gives the "file" a name, and gives
* the address of a function to call when the file is read */
struct proc_dir_entry test_entry = {
0, /* low_ino - inode number (0 for dynamic) */
12, /* namelen - length of entry name */
"simple_entry", /* name */
S_IFREG | S_IRUGO, /* mode */
1, /* nlinks */
0, /* uid - owner */
0, /* gid - group */
0, /* size - not used */
NULL, /* ops - inode operations (use default) */
&show_ip_stats /* read_proc - address of read function */
/* leave rest blank! */
};
/*************************************************************** init_module
* this function installs the module; it simply registers a directory entry
* with the /proc FS */
int init_module() {
/* register the function with the proc FS */
int err = proc_register(&proc_root,&test_entry);
/* put the registration results in the log */
if (!err)
printk("<1> simple_entry: registered with inode %d.\n",
test_entry.low_ino);
else
printk("<1> simple_entry: registration error, code %d.\n",err);
return err;
} /* init_module */
/************************************************************ cleanup_module
* this function removes the module; it simply unregisters the directory
* entry from the /proc FS */
void cleanup_module() {
/* unregister the function from the proc FS */
int err = proc_unregister(&proc_root,test_entry.low_ino);
/* put the unregistration results in the log */
if (!err)
printk("<1> simple_entry: unregistered inode %d.\n",
test_entry.low_ino);
else
printk("<1> simple_entry: unregistration error, code %d.\n",err);
} /* cleanup_module */
This is the Makefile:
# Makefile for simple_entry CC = gcc -I/usr/src/linux/include CFLAGS = -O2 -D__KERNEL__ -Wall simple_entry.o: simple_entry.c install: /sbin/insmod simple_entry remove: /sbin/rmmod simple_entry
To use (must be root):
root# make root# make install root# cat /proc/simple_entry Some IP Statistics: IP Forwarding is on Default TTL: 64 Frag Creates: 0 root# make remove root# tail /var/log/messages ... kernel: simple_entry: registered with inode 4365. ... kernel: simple_entry: unregistered inode 4365.
This sample experiment inserts a routine into the kernel that selectively drops packets to a given host. It discusses the placement of the code, outlines the data from an actual trial, presents a lightweight analysis of the results, and includes the code itself.
The switch is a Cisco Catalyst 2900 set up with Virtual LANs (VLANs) for each ``subnetwork'' (one for the source computer and one for the destination computer, with the routing computer acting as the router between the two. The switch operates entirely on the link level and is essentially invisible for routing purposes.
The routing computer (dodge/viper) is a Dell Optiplex GX1 with a Pentium II/350 processor and 128M of RAM. It has three 3Com 3c59x Ethernet cards with 10Mbps connections to the switch.
One host computer (neon) is an AST Premmia GX with a Pentium/100 processor and 32M of RAM. It has an AMD Lance Ethernet card with a 10Mbps connection to the switch.
The other host computer (eagle) is a Dell Optiplex XL590 with a Pentium/90 processor and 32M of RAM. It has a 3Com 3c509 Ethernet card with a 10Mbps connection to the switch.
All computers have the Red Hat 6.1 distribution of Linux; the source and destination computers have standard recompiled version 2.2.14 kernels, while the router uses either a standard (2.2.14) kernel or a slightly modified one as indicated.
The first benchmark is a ``ping-pong'' test that establishes a TCP connection and then repeatedly sends packets back and forth. It returns a total transmission time (from start to finish, not including making and closing the connection); dividing the time by the number of iterations yields an average Round Trip Time (RTT). This test was run with 20,000 iterations of 5 byte packets and 5,000 iterations of 500 byte packets.
The second benchmark is a ``blast'' test that establishes a TCP connection and then sends data from a source to a destination. It returns a total transmission time (from start to finish, not including making and closing the connection); multiplying the number of packets by the size of the packets and dividing by the time yields the throughput. This test was run with 50,000 5 byte packets, 5,000 500 byte packets, and 1,000 1500 byte packets.
The benchmarks were run on both machines (i.e., from neon to eagle and from eagle to neon), but in both cases only packets to eagle were dropped. In each trial the blast test was run once with default settings (100 packets of 1 byte each) before running the performance tests ``for record'' to ensure that the routing cache and any protocol tables were in a normalized state. The complete suite was run ten times to capture variations between trials (the averages are presented here). None of the machines (including the router) were running any other user programs beyond a login shell and the appropriate module, client, or server programs (not even X Windows).
ping-pong
Mean Time (sec) Average RTT (millisec)
Drop Rate 20K@5 5K@500 20K@5 5K@500
Direct -
neon to eagle: --- 17.24 28.98 0.86 5.80
eagle to neon: --- 17.20 28.99 0.86 5.80
Routed -
neon to eagle: (0.0%) 24.53 48.59 1.23 9.72
eagle to neon: (0.0%) 24.36 48.46 1.22 9.69
blast
Mean Time (sec) Throughput (Mbits/sec)
Drop Rate 50K*5 10K*500 1K*1500 50K*5 10K*500 1K*1500
Direct -
neon to eagle: --- 0.56 3.19 1.89 3.55 6.26 6.36
eagle to neon: --- 0.78 3.03 1.77 2.58 6.61 6.76
Routed -
neon to eagle: (0.0%) 0.56 3.19 1.92 3.60 6.27 6.26
eagle to neon: (0.0%) 0.77 3.19 1.93 2.60 6.27 6.23
ping-pong
Mean Time (sec) Average RTT (millisec)
Drop Rate 20K@5 5K@500 20K@5 5K@500
neon to eagle: 0.0% 25.55 49.12 1.28 9.82
0.1% 29.87 51.11 1.49 10.22
0.5% 44.78 58.07 2.24 11.61
1.0% 65.37 68.77 3.27 13.75
5.0% 245.51 160.09 12.28 32.02
10.0% 506.03 290.77 25.30 58.15
eagle to neon: 0.0% 25.53 49.21 1.28 9.84
0.1% 29.08 50.92 1.45 10.18
0.5% 45.87 59.21 2.29 11.84
1.0% 66.19 68.66 3.31 13.73
5.0% 235.68 156.94 11.78 31.39
10.0% 519.61 297.02 25.98 59.40
blast
Mean Time (sec) Throughput (Mbits/sec)
Drop Rate 50K*5 10K*500 1K*1500 50K*5 10K*500 1K*1500
neon to eagle: 0.0% 0.55 3.19 1.91 3.64 6.26 6.27
0.1% 0.55 3.07 1.93 3.62 6.51 6.21
0.5% 0.55 2.95 1.76 3.64 6.77 6.82
1.0% 0.55 2.87 1.75 3.65 6.96 6.87
2.5% 0.59 3.36 2.04 3.38 5.59 5.90
5.0% 0.63 4.63 2.71 3.19 4.31 4.43
10.0% 1.06 7.08 5.11 1.89 2.83 2.35
20.0% 3.43 30.35 18.55 0.58 0.66 0.65
eagle to neon: 0.0% 0.79 3.21 1.93 2.53 6.23 6.23
0.1% 0.77 3.22 1.89 2.59 6.20 6.35
0.5% 0.80 3.24 1.88 2.51 6.17 6.39
1.0% 0.77 3.24 1.91 2.60 6.17 6.27
2.5% 0.79 3.17 1.90 2.53 6.31 6.33
5.0% 0.78 3.17 1.91 2.57 6.31 6.29
10.0% 0.81 3.85 2.51 2.48 5.20 4.78
20.0% 2.02 4.06 2.51 0.99 4.92 4.78
The kernel modifications and module insertion had a small but measurable impact on a TCP connection (measured by the increased RTT). For very small packets, this difference was approximately 0.05 msec; for large packets it was 0.10 msec. Why should there be a difference? Note that the direction of travel and packet size made a large difference on the throughput. This is an indication that processor speed and layering overhead are affecting the RTT; for a 1500 byte packet, 66 bytes of wrappers (20 for TCP, 20 for IP, and at least 26 for Ethernet) are not very significant - but for a 5 byte packet, that overhead is very large. Assume that the actual ``cost'' of inserting the module the delay for the larger packets, 0.10 msec.
Dropping packets from a TCP connection resulted in a fairly linear drop in performance on the ping-pong test; see the graph in Figure 13.2. This is as expected; when either a packet or acknowledgement is lost, the sender pauses and then sends again. The RTT is also very close (certainly within the expected experimental error) no matter which machine is the ``source''; again this is because the benchmark tests the behavior of both machines at the same time.
At low packet sizes, the throughput was very different depending on which way data was sent. This is because one machine (eagle) was slower than the other. For a large number of very small packets, the chokepoint in the network is not the medium or the interface, but the speed at which the processor can build and send packets. However, for larger packet sizes, the throughput (for low error rate) for both sources is similar; in this case the network is the limiting factor, not the processor.
The most surprising result is the apparent peak in throughput when the loss rate is approximately 1% - better even than no loss at all (for blasted data; loss of ACKs sent from the receiver to the source had little impact). This is a very counter-intuitive finding; why should losing packets speed up the throughput? A 1% error might be just enough to prevent a TCP exponential back-off algorithm from slowing the traffic rate. The immediate ACK that the receiver sends when an out-of-sequence packet arrives might include window size information that keeps the sender from pausing. Interrupts caused by out-of-sequence packets might result in the scheduler running the benchmark process more frequently, emptying the buffer window and again keeping the sender from pausing. There are many potential causes; determining the real one would take much more study - but would be very interesting.
net/core/dev.c (after line 579)
...
int *test_function(struct sk_buff *)=0; /* new */
int dev_queue_xmit(struct sk_buff *skb)...
...struct Qdisc *q;
if (test_function && (*test_function)(skb)) { /* new */
kfree_skb(skb); /* new */
return 0; /* new */
} /* new */
#ifdef CONFIG_NET_PROFILE...
net/netsyms.c (after line 544)
... extern int (*test_function)(struct sk_buff *); /* new */ EXPORT_SYMBOL_NOVERS(test_function); /* new */ EXPORT_SYMBOL(register_gifconf);...
packet_dropper.c
/* packet_dropper.c
*
* This program provides an example of how to install a module into a
* slightly modified kernel that will randomly drop packets for a specific
* (hard-coded) host.
*
* See linux/drivers/char/random.c for details of get_random_bytes().
*
* Usage (must be root to use):
* /sbin/insmod packet_dropper
* /sbin/rmmod packet_dropper
*/
#define MODULE
#define MAX_UNSIGNED_SHORT 65535
#include <linux/module.h>
#include <linux/skbuff.h> /* for struct sk_buff */
#include <linux/ip.h> /* for struct iphdr */
extern int (*test_function)(struct sk_buff *); /* calling function */
extern void get_random_bytes(void *buf, int nbytes); /* random function */
unsigned short cutoff; /* drop cutoff */
float rate = 0.050; /* drop percentage */
__u32 target = 0x220010AC; /* 172.16.0.34 */
/************************************************************ packet_dropper
* this is what dev_queue_xmit will call while this module is installed */
int packet_dropper(struct sk_buff *skb) {
unsigned short t;
if (skb->nh.iph->daddr == target) {
get_random_bytes(&t,2);
if (t <= cutoff) return 1; /* drop this packet */
}
return 0; /* continue with normal routine */
} /* packet_dropper */
/*************************************************************** init_module
* this function replaces the null pointer with a real one */
int init_module() {
EXPORT_NO_SYMBOLS;
cutoff = rate * MAX_UNSIGNED_SHORT;
test_function = packet_dropper;
printk("<1> packet_dropper: now dropping packets\n");
return 0;
} /* init_module */
/************************************************************ cleanup_module
* this function resets the function pointer back to null */
void cleanup_module() {
test_function = 0;
printk("<1> packet_dropper: uninstalled\n");
} /* cleanup_module */