Section 27.1.  Main Data Structures

27.1. Main Data Structures To understand the code for the neighboring infrastructure, we first need to describe a few data structures used heavily in the neighboring subsystem, and see how they interact with each other. Most of the definitions for these structures can be found in the file include/net/neighbour.h. Note that the Linux kernel code uses the British spelling neighbour for data structures and functions related to this subsystem. When speaking generically of neighbors, this book sticks to the American spelling, which is the spelling found in RFCs and other official documents. struct neighbour Stores information about a neighbor, such as the L2 and L3 addresses, the NUD state, the device through which the neighbor can be reached, etc. Note that a neighbour enTRy is associated not with a host, but with an L3 address. There can be more than one L3 address for a host. For example, routers, among other systems, have multiple interfaces and therefore multiple L3 addresses. struct neigh_table Describes a neighboring protocol's parameters and functions. There is one instance of this structure for each neighboring protocol. All of the structures are inserted into a global list pointed to by the static variable neigh_tables and protected by the lock neigh_tbl_lock. This lock protects the integrity of the list, but not the content of each entry. struct neigh_parms A set of parameters that can be used to tune the behavior of a neighboring protocol on a per-device basis. Since more than one protocol can be enabled on most interfaces (for instance, IPv4 and IPv6), more than one neigh_parms structure can be associated with a net_device structure. struct neigh_ops A set of functions that represents the interface between the L3 protocols such as IP and dev_queue_xmit, the API introduced in Chapter 11 and described briefly in the upcoming section "Common Interface Between L3 Protocols and Neighboring Protocols." The virtual functions can change based on the context in which they are used (that is, on the status of the neighbor, as described in Chapter 26). struct hh_cache Caches link layer headers to speed up transmission. It is faster to copy a cached header into a buffer in one shot than to fill in its fields one by one. Not all device drivers implement header caching. See the section "L2 Header Caching." struct rtable struct dst_entry When a host needs to route a packet, it first consults its cache and then, in the case of a cache miss, it queries the routing table. Every time the host queries the routing table, the result is saved into the cache. The IPv4 routing cache is composed of rtable structures. Each instance is associated with a different destination IP address. Among the fields of the rtable structure are the destination address, the next hop (router), and a structure of type dst_entry that is used to store the protocol-independent information. dst_entry includes a pointer to the neighbour structure associated with the next hop. I cover the dst_entry data structure in detail in Chapter 36. In the rest of this chapter, I will often refer to dst_entry structures as elements of the routing table cache, even though dst_entry is actually only a field of the rtable structure. Figure 27-1 shows how dst_entry structures are linked to hh_cache and neighbour structures. The neighboring code also uses some other small data structures. For instance, struct pneigh_entry is used by destination-based proxying, and struct neigh_statistics is used to collect statistics about neighboring protocols. The first structure is described in the section "Acting As a Proxy," and the second one is described in the section "Statistics" in Chapter 29. Figure 27-2 also includes the following data structure types, described in greater detail in Chapters 22 and 23: Figure 27-1. Relationship among dst_entry, neighbour, and hh_cache structures in_device, inet6_dev Used to store the IPv4 and IPv6 configurations of a device, respectively. net_device There is one net_device structure for each network device recognized by the kernel. See Chapter 8. Figure 27-2 shows the relationships between the most important data structures. Right now it might seem a big mess, but it will make much more sense by the end of this chapter. Here are the main points shown in Figure 27-2: In the central part of the figure, you can see that each network device has a pointer to a data structure that holds the configuration for each L3 protocol configured on the device. In the example shown in the figure, IPv6 is configured on one device and IPv4 is configured on both. Both the in_device structure (IPv4 configuration) and inet6_dev structure (IPv6 configuration) include a pointer to the configuration used by their neighboring protocols, respectively ARP and ND. All of the neigh_parms structures used by any given protocol are linked together in a unidirectional list whose root is stored in the protocol's neigh_table structure. The top and bottom of the figure show that each protocol keeps two hash tables. The first one, hash_buckets, caches the L3-to-L2 mappings resolved by the protocol or statically configured. The second one, phash_bucket, stores those IP addresses that are proxied, as described in the section "Per-Device Proxying and Per-Destination Proxying." Note that phash_bucket is not a cache, so its elements do not expire and don't need confirmation. Each pneigh_entry structure Figure 27-2. Data structures' relationships includes a pointer (not depicted in Figure 27-2) to its associated net_device structure. Figure 27-6 gives more detail on the structure of the cache hash_buckets. Each neighbour instance is associated with one or more hh_cache structures, if the device supports header caching. The section "L2 Header Caching," and Figures 27-1 and 27-10, give more details about the relationship between neighbour and hh_cache structures.