Understanding Linux Network Internals

The Table Lookup: fn_hash_lookup

All routing table lookups , regardless of the tables provided by Policy Routing and the direction of the traffic, are done with fn_hash_lookup. This function is registered as the handler for the tb_lookup function pointer of the fib_table structure in fib_hash_init (see the section "Routing Table Initialization" in Chapter 34).

The function's lookup algorithm uses the LPM algorithm introduced in Chapter 30. The execution of this algorithm is facilitated by the organization of routes into per-netmask hash tables, as shown in Figure 34-1 in Chapter 34. fn_hash_lookup searches for the fib_node instance that has the information to route packets to a particular destination.

The prototype for fn_hash_lookup is:

static int
fn_hash_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)

Here is the meaning of its input parameters:

tb

The routing table to search. Because fn_hash_lookup is a generic lookup routine that runs on one table at a time, the tables to search are decided by the caller, depending on Policy Routing support and related factors.

flp

Search key.

res

Upon success, res is initialized with the routing information.

And these are the possible return values:

0: success

res has been initialized (by fib_semantic_match) with the forwarding information.

1: failure

No route matched the search key.

Less than 0: Administrative failure

This means the lookup cannot succeed because the route found is of no value: for instance, the associated ...