Understanding Linux Network Internals

Hash Table Organization

The data structures described in this section vary slightly among L3 protocols. In IPv4, hash table buckets are of type rt_hash_bucket, a structure that includes only a pointer to the list of colliding elements and a lock. The use of the lock is described in the section "Cache Locking."

Elements of the cache are of type rtable. This structure includes some protocol-dependent fields, described in the section "rtable Structure" in Chapter 36, and a protocol-independent data structure of type dst_entry, shown in Figure 33-1. The dst_entry structure includes the interface to the neighboring layer and its cache, transformers (such as IPsec), and routing cache management. The section "dst_entry Structure" in Chapter 36 describes the data structure in detail, and Chapter 27 goes over the interface to the neighboring layer.

The first field of the rtable structure is a union; this makes it easy for the rtable and dst_entry structures to share values such as the pointer to the next colliding hash table entry. The names of the pointers differ (dst_entry uses next, whereas rtable uses rt_next), but they refer to the same memory location.

Figure 33-1. Routing cache structure

struct rtable
{
        union
        {
                struct dst_entry dst;
                struct rtable *rt_next;
        } u;
        ... ... ...
}

A pointer to an rtable structure can be safely typecast to a pointer to a dst_entry, and vice versa.

When accessing ...