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.

Contents

Chapter 1
Introduction

1.1 Background

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.

1.2 Document Conventions

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.

1.3 Sample Network Example

Figure 1.1: Sample network structure.

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.

1.4 Copyright, License, and Disclaimer

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:

Please note any modifications including deletions.

This is a variation (changes are intentional) of the Linux Documentaion Project (LDP) License available at:

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.

1.5 Acknowledgements

Glenn Herrin
Major, United States Army
Primary Documenter and Researcher, Version 1.0
gherrin@cs.unh.edu

Chapter 2
Message Traffic Overview

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.

2.1 The Network Traffic Path

Figure 2.1: Abstraction of the Linux message traffic path.

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.

2.2 The Protocol Stack

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).

2.3 Packet Structure

Figure 2.2: Packet (sk_buff) structure.

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.

2.4 Internet Routing

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.

Chapter 3
Network Initialization

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.

3.1 Overview

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.

3.2 Startup

3.2.1 The Network Initialization Script

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.)

3.2.2 ifconfig

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):

ifconfig eth0 down — shut down eth0
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

3.2.3 route

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):

route add [-net | -host] target [option arg]
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

3.2.4 Dynamic Routing Programs

3.3 Examples

3.3.1 Home Computer

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.

NETWORKING=yes
FORWARD_IPV4=false
HOSTNAME=localhost.localdomain
GATEWAY=

DEVICE=lo
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

3.3.2 Host Computer on a LAN

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).

NETWORKING=yes
FORWARD_IPV4=false
HOSTNAME=stealth.cs.u.edu
DOMAINNAME=cs.u.edu
GATEWAY=172.16.1.1
GATEWAYDEV=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.

3.3.3 Network Routing Computer

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).

NETWORKING=yes
FORWARD_IPV4=true
HOSTNAME=dodge.u.edu
DOMAINNAME=u.edu
GATEWAY=172.16.0.1
GATEWAYDEV=eth1

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

DEVICE=eth1
IPADDR=172.16.0.7
NMASK=255.255.0.0
NETWORK=172.16.0.0
BCAST=172.16.255.255
ONBOOT=yes

3.4 Linux and Network Program Functions

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.rpm
cd /usr/src/redhat/SOURCES
tar xzf net-tools-1.53.tar.gz

3.4.1 ifconfig

3.4.2 route

Chapter 4
Connections

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.

4.1 Overview

4.2 Socket Structures

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.

• struct proto_ops *ops — this structure contains pointers to protocol specific functions for implementing general socket behavior. For example, ops- > sendmsg points to the inet_sendmsg() function.
• struct inode *inode — this structure points to the file inode that is associated with this socket.
• struct sock *sk — this is the INET socket that is associated with this socket.

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:

• struct sock *next, *pprev — all sockets are linked by various protocols, so these pointers allow the protocols to traverse them.
• struct dst_entry *dst_cache — this is a pointer to the route to the socket’s other side (the destination for sent packets).
• struct sk_buff_head receive_queue — this is the head of the receive queue.
• struct sk_buff_head write_queue — this is the head of the send queue.
• __u32 saddr — the (Internet) source address for this socket.
• struct sk_buff_head back_log,error_queue — extra queues for a backlog of packets (not to be confused with the main backlog queue) and erroneous packets for this socket.
• struct proto *prot — this structure contains pointers to transport layer protocol specific functions. For example, prot- > recvmsg may point to the tcp_v4_recvmsg() function.
• union struct tcp_op af_tcp; tp_pinfo — TCP options for this socket.
• struct socket *sock — the parent BSD socket.
• Note that there are many more fields within this structure; these are only the most critical and non-obvious. The rest are either not very important or have self-explanatory names (e.g., ip_ttl is the IP Time-To-Live counter).

4.3 Sockets and Routing

4.4 Connection Processes

4.4.1 Establishing Connections

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.

4.4.2 Socket Call Walk-Through

• Check for errors in call
• Create (allocate memory for) socket object
• Put socket into INODE list
• Establish pointers to protocol functions (INET)
• Store values for socket type and protocol family
• Set socket state to closed
• Initialize packet queues

4.4.3 Connect Call Walk-Through

• Check for errors
• Determine route to destination:
  • Check routing table for existing entry (return that if one exists)
  • Look up destination in FIB
  • Build new routing table entry
  • Put entry in routing table and return it

• Store pointer to routing entry in socket
• Call protocol specific connection function (e.g., send a TCP connection packet)
• Set socket state to established

4.4.4 Closing Connections

4.4.5 Close Walk-Through

• Check for errors (does the socket exist?)
• Change the socket state to disconnecting to prevent further use
• Do any protocol closing actions (e.g., send a TCP packet with the FIN bit set)
• Free memory for socket data structures (TCP/UDP and INET)
• Remove socket from INODE list

4.5 Linux Functions

Chapter 5
Sending Messages

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.

5.1 Overview

Figure 5.1: Message transmission.

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.

5.2 Sending Walk-Through

5.2.1 Writing to a Socket

• Write data to a socket (application)
• Fill in message header with location of data (socket)
• Check for basic errors — is socket bound to a port? can the socket send messages? is there something wrong with the socket?
• Pass the message header to appropriate transport protocol (INET socket)

5.2.2 Creating a Packet with UDP

• Check for errors — is the data too big? is it a UDP connection?
• Make sure there is a route to the destination (call the IP routing routines if the route is not already established; fail if there is no route)
• Create a UDP header (for the packet)
• Call the IP build and transmit function

5.2.3 Creating a Packet with TCP

• Check connection — is it established? is it open? is the socket working?
• Check for and combine data with partial packets if possible
• Create a packet buffer
• Copy the payload from user space
• Add the packet to the outbound queue
• Build current TCP header into packet (with ACKs, SYN, etc.)
• Call the IP transmit function

5.2.4 Wrapping a Packet in IP

• Create a packet buffer (if necessary — UDP)
• Look up route to destination (if necessary — TCP)
• Fill in the packet IP header
• Copy the transport header and the payload from user space
• Send the packet to the destination route’s device output funtion

5.2.5 Transmitting a Packet

• Put the packet on the device output queue
• Wake up the device
• Wait for the scheduler to run the device driver
• Test the medium (device)
• Send the link header
• Tell the bus to transmit the packet over the medium

5.3 Linux Functions

Chapter 6
Receiving Messages

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.

6.1 Overview

Figure 6.1: Receiving messages.

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.)

6.2 Receiving Walk-Through

6.2.1 Reading from a Socket (Part I)

• Try to read data from a socket (application)
• Fill in message header with location of buffer (socket)
• Check for basic errors — is the socket bound to a port? can the socket accept messages? is there something wrong with the socket?
• Pass the message header with to the appropriate transport protocol (INET socket)
• Sleep until there is enough data to read from the socket (TCP/UDP)

6.2.2 Receiving a Packet

• Wake up the receiving device (interrupt)
• Test the medium (device)
• Receive the link header
• Allocate space for the packet
• Tell the bus to put the packet into the buffer
• Put the packet on the backlog queue
• Set the flag to run the network bottom half when possible
• Return control to the current process

6.2.3 Running the Network «Bottom Half»

• Run the network bottom half (scheduler)
• Send any packets that are waiting to prevent interrupts (bottom half)
• Loop through all packets in the backlog queue and pass the packet up to its Internet reception protocol — IP
• Flush the sending queue again
• Exit the bottom half

6.2.4 Unwrapping a Packet in IP

• Check packet for errors — too short? too long? invalid version? checksum error?
• Defragment the packet if necessary
• Get the route for the packet (could be for this host or could need to be forwarded)
• Send the packet to its destination handling routine (TCP or UDP reception, or possibly retransmission to another host)

6.2.5 Accepting a Packet in UDP

• Check UDP header for errors
• Match destination to socket
• Send an error message back if there is no such socket
• Put packet into appropriate socket receive queue
• Wake up any processes waiting for data from that socket

6.2.6 Accepting a Packet in TCP

• Check sequence and flags; store packet in correct space if possible
• If already received, send immediate ACK and drop packet
• Determine which socket packet belongs to
• Put packet into appropriate socket receive queue
• Wake up and processes waiting for data from that socket

6.2.7 Reading from a Socket (Part II)

• Wake up when data is ready (socket)
• Call transport layer receive function
• Move data from receive queue to user buffer (TCP/UDP)
• Return data and control to application (socket)

6.3 Linux Functions

Chapter 7
IP Forwarding

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.

7.1 Overview

See Figure 7.1 for an abstract diagram of the the forwarding process. (It is essentially a combination of the receiving and sending processes.)

Figure 7.1: IP forwarding.

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.

7.2 IP Forward Walk-Through

7.2.1 Receiving a Packet

• Wake up the receiving device (interrupt)
• Test the medium (device)
• Receive the link header
• Allocate space for the packet
• Tell the bus to put the packet into the buffer
• Put the packet on the backlog queue
• Set the flag to run the network bottom half when possible
• Return control to the current process

7.2.2 Running the Network «Bottom Half»

• Run the network bottom half (scheduler)
• Send any packets that are waiting to prevent interrupts (net_bh)
• Loop through all packets in the backlog queue and pass the packet up to its Internet reception protocol — IP
• Flush the sending queue again
• Exit the bottom half

7.2.3 Examining a Packet in IP

• Check packet for errors — too short? too long? invalid version? checksum error?
• Defragment the packet if necessary
• Get the route for the packet (could be for this host or could need to be forwarded)
• Send the packet to its destination handling routine (retransmission to another host in this case)

7.2.4 Forwarding a Packet in IP

• Check TTL field (and decrement it)
• Check packet for improper (undesired) routing
• Send ICMP back to sender if there are any problems
• Copy packet into new buffer and free old one
• Set any IP options
• Fragment packet if it is too big for new destination
• Send the packet to the destination route’s device output function

7.2.5 Transmitting a Packet

• Put the packet on the device output queue
• Wake up the device
• Wait for the scheduler to run the device driver
• Test the medium (device)
• Send the link header
• Tell the bus to transmit the packet over the medium

7.3 Linux Functions

Chapter 8
Basic Internet Protocol Routing

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.

8.1 Overview

Figure 8.1: General routing table example.

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).

8.2 Routing Tables

8.2.1 The Neighbor Table

Figure 8.2: Neighbor Table data structure relationships.

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.

• struct neigh_table *next — pointer to the next table in the list.
• struct neigh_parms parms — structure containing message travel time, queue length, and statistical information; this is actually the head of a list.
• struct neigh_parms *parms_list — pointer to a list of information structures.
• struct neighbour *hash_buckets[] — hash table of neighbors associated with this table; there are NEIGH_HASHMASK+1 (32) buckets.
• struct pneigh_entry *phash_buckets[] — hash table of structures containing device pointers and keys; there are PNEIGH_HASHMASK+1 (16) buckets.
• Other fields include timer information, function pointers, locks, and statistics.

Neighbor Data (struct neighbour) Structure — these structures contain the specific information about each neighbor.

• struct device *dev — pointer to the device that is connected to this neighbor.
• __u8 nud_state — status flags; values can be incomplete, reachable, stale, etc.; also contains state information for permanence and ARP use.
• struct hh_cache *hh — pointer to cached hardware header for transmissions to this neighbor.
• struct sk_buff_head arp_queue — pointer to ARP packets for this neighbor.
• Other fields include list pointers, function (table) pointers, and statistical information.

8.2.2 The Forwarding Information Base

Figure 8.3: Forwarding Information Base (FIB) conceptual organization.

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.

• int (*tb_functions)() — pointers to table functions (lookup, delete, insert, etc.) that are set during initialization to fn_hash_function().
• unsigned char tb_data[0] — pointer to the associated FIB hash table (despite its declaration as a character array).
• unsigned char tb_id — table identifier; 255 for local_table, 254 for main_table.
• unsigned tb_stamp

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).

• struct fn_zone *fn_zones[33] — pointers to zone entries (one zone for each bit in the mask; fn_zone[0] points to the zone for netmask 0x0000, fn_zone[1] points to the zone for 0x8000, and fn_zone[32] points to the zone for 0xFFFF.
• struct fn_zone *fn_zone_list — pointer to first (most specific) non-empty zone in the list; if there is an entry for netmask 0xFFFF it will point to that zone, otherwise it may point to zone 0xFFF0 or 0xFF00 or 0xF000 etc.

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.

• struct fn_zone *fz_next — pointer to the next non-empty zone in the hash structure (the next most general netmask; e.g., fn_hash- > fn_zone[28]- > fz_next might point to fn_hash- > fn_zone[27]).
• struct fib_node **fz_hash — pointer to a hash table of nodes for this zone.
• int fz_nent — the number of entries (nodes) in this zone.
• int fx_divisor — the number of buckets in the hash table associated with this zone; there are 16 buckets in the table for most zones (except the first zone — 0000 — the loopback device).
• u32 fz_hashmask — a mask for entering the hash table of nodes; 15 (0x0F) for most zones, 0 for zone 0).
• int fz_order — the index of this zone in the parent fn_hash structure (0 to 32).
• u32 fz_mask — the zone netmask defined as