2011-10-17

Policy routing details

Previously I published a graph about the process how does the policy routing works in Linux. Now, I want to explain it more detailed. This post is based on the third version (dst_entry-v2.1.pdf) of the graph.

The links below with function names, are linked to LXR. The details are based on Linux 2.6.35.14.


Entry point

The process starts at ip6_route_output. It sets up the flags (an integer value), and calls fib6_rule lookup. 
In this context fib means Forwarding Information Base.

Fib rule lookup - calling

The FIB lookup is an 'embedded' process. The main functions of it are the parts of the protocol-independent core (net/core/fib*), but it has to do a lot of protocol-dependent (in this case IPv6) checks and actions.
The ip6_route_output function calls fib6_rule_lookup. At this point, ip6_route_output specifies ip6_pol_route_output as a lookup function for later usage. Here comes the gateway between the protocol-dependent and -independent code. fib6_rule_lookup initializes the fib_lookup_arg struct (arg), and sets the lookup function as it has been provided by ip6_route_output.
When calling fib_rules_lookup, fib6_rule_lookup specifies IPv6-related functions for matching, and processing, which are coming from the net structure (net->ipv6.fib6_rules_ops). It is signed with light green on the graph.

Fib rule lookup - lookup


The fib_rules_lookup function iterates over the list of rules. It calls fib_rule_match for each rule to decide that is matches or not. The matching process is magnified at the left side of the picture.
First, it checks the ifindex (Interface Index) for inbound and outbound directions, and the (Netfilter) MARK. Next, it calls, the protocol-dependent match function. In our case it is fib6_rule_match. It checks the source and destination prefixes and the flow-label.
If the matching algorithm found the correct rule, fib_rules_lookup will call the protocol-dependent action-function, which specified at the same way as the match one. In our case it will be fib6_rule_action.

Rule action


The fib6_rule_action function gets the rule's matching routing table. It happens in fib6_get_table. Next, it calls the lookup function itself. If you remember for the second section (Fib rule lookup - lookup), fib6_rule_lookup specified a lookup function in the fib_lookup_arg struct. I our case it was ip6_pol_route_output. The fib6_rule_action calls now this, with the got routing table.
The fib6_pol_rout_output is just a wrapper function, it calls ip6_pol_route.

Table - nodes - info


The fib6_table contains a reference to the root node of the fib6_node tree. The tree order is based on the destination address (prefix). If the source routing is enabled in the kernel config, it is represented by subtrees. (It is signed with [] on the image). The routing information itself is stored in fib6_info.
If there are multiple routing entries for the same node (same conditions), there are multiple fib6_info entries for one fib6_node.

Node lookup


The fib6_lookup function creates an  array of lookup_args structs. It sets up the destination address, and if the the source routing is enabled, the source address as well. Next it calls the fib6_lookup_l recursive (recursion for subtrees) function. It will find the node which has Longest Prefix Match. The LPM condition is wired into the tree order, and not to the lookup algorithm.

Info lookup


If we have the correct node, we have to find the routing info itself. The rt6_select function initializes the process, and calls find_rr_leaf. It's using find_match inside the iterator loop to find the best route. The find_match function calls rt6_scrore_route to get the 'value' of the route, which helps to find the best one.


Disclaimer: This process is based on my debugging, and code examining. It may contain not correct parts. Comments are welcome.

0 comments:

Post a Comment

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | Top WordPress Themes