小草博客

A-A+

利用fib_lookup来查找路由表的方法、 source code 和参数说明

2015年11月24日 站长资讯 暂无评论

路由查找都是利用fib_lookup来查找路由表的。下面介绍它的方法和一些参数说明。

fib_lookup有两个版本，一个是当内核支持策略路由时使用；一个是当内核不支持策略路由时使用。

选择哪一个函数是在编译时决定的，所以当ip_route_input_slow和ip_route_output_slow调用fib_lookup时，它们透明地激活正确的查找函数。

fib_lookup程序是对每一个路由表所提供的查找函数的一个包装（wrapper）。当不支持策略路由时，查找函数版本是针对local表和main表。当支持策略路由时，逻辑更为复杂，需要查找由策略路由提供的路由表。

先看看没有策略路由时的source code：

  1. static inline int fib_lookup(struct net *net, const struct flowi *flp, struct fib_result *res)  
  2. {  
  3.     struct fib_table *table;  
  4.   
  5.     table = fib_get_table(net, RT_TABLE_LOCAL);  
  6.     if (!fib_table_lookup(table, flp, res)) return 0;  
  7.   
  8.     table = fib_get_table(net, RT_TABLE_MAIN);  
  9.     if (!fib_table_lookup(table, flp, res)) return 0;  
  10.     return -ENETUNREACH;  
  11. }  

在系统初始化时总是创建下面两个路由表，它们与内核配置选项无关：

RT_TABLE_LOCAL

内核将到本地地址的路由表项放在该表中，包括到相关的网段地址以及网段广播地址的路由表项，用户不能够直接配置该路由表。

RT_TABLE_MAIN

所有其他的路由表项（包括用户配置的静态路由表项，路由协议生成的动态路由表项）都放在该表内。

继续跟进到fib_table_lookup

  1. int fib_table_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)  
  2. {  
  3.     int err;  
  4.     struct fn_zone *fz;  
  5.     struct fn_hash *t = (struct fn_hash *)tb->tb_data;  
  6.   
  7.     read_lock(&fib_hash_lock);  
  8.     //对说有的网络掩码zone进行循环处理  
  9.     for (fz = t->fn_zone_list; fz; fzfz = fz->fz_next) {  
  10.         struct hlist_head *head;  
  11.         struct hlist_node *node;  
  12.         struct fib_node *f;  
  13.         __be32 k = fz_key(flp->fl4_dst, fz);//根据目标ip地址得到网络掩码  
  14.         head = &fz->fz_hash[fn_hash(k, fz)];//fib_node为链接元素的hash表  
  15.   
  16.         //对每个fib_node进行循环处理  
  17.         hlist_for_each_entry(f, node, head, fn_hash) {  
  18.             if (f->fn_key != k) continue;//网络掩码不同就退出  
  19.   
  20.             err = fib_semantic_match(&f->fn_alias, flp, res, fz->fz_order);//详细查找  
  21.             if (err <= 0) goto out;  
  22.         }  
  23.     }  
  24.     err = 1;  
  25. out:  
  26.     read_unlock(&fib_hash_lock);  
  27.     return err;  
  28. }  

参数说明如下:

tb 搜索的路由表。因为fn_hash_lookup是一个通用的查找程序，每次只能够查找一张表。

调用方根据是否支持策略路由和相关的因素，来决定搜索哪些路由表。

flp 搜索key。

res 查找成功时，利用路由信息来初始化res。

下面给出可能的返回值：

0：成功 已经根据转发信息初始化res（通过fib_semantic_match函数）。

1：失败 没有与搜索key匹配的路由项。

小于0： 管理失败（Administrative failure）

这表示查找不成功，因为查找到的路由没有价值：例如相关的主机可能被标记为不可达。

查找说明:

路由查找使用的算法是LPM,即最长匹配。匹配的网络掩码越长，说明路由更准确。

比如，10.1.1.0/16和10.1.1.0/24这两个网络掩码，覆盖的主机个数完全不是一个等级的。

根据LPM算法，10.1.1.0/24将首先进行匹配，匹配不符，才匹配10.1.1.0/16。

使用了的网络掩码zone都被连接到fn_zone_list这个双向链表上了，链接时，顺序就已经按照网络掩码长度，进行排序了。所以查找时，肯定是按照，最长匹配原则来查找。

在fib_table_lookup函数中，将目的IP地址与检查的active zone的网络掩码相与（ANDs），与操作的结果作为搜索key。例如，如果正在检查/24 zone，目的地址flp->fl4_dst为10.0.1.2，则搜索key k为10.0.1.2 & 255.255.255.0，结果为10.0.1.0。这意味着接下来的代码要搜索到子网10.0.1.0/24的路由：

u32 k = fz_key(flp->fl4_dst, fz);

因为路由被存储在哈希表（fz_hash）内，所以首先通过一个哈希函数对搜索key k进行哈希，得到相应的哈希桶head。接下来是遍历与该哈希桶相关的路由链表（fib_node结构），查找与k匹配的路由项。

一个fib_node覆盖了同一子网内的所有路由项，但这些路由项在诸如TOS等其他字段上可能不同。现在，如果fib_table_lookup函数找到了与搜索key k匹配的fib_node，它还需要检查每一个潜在的路由项，来查找与输入参数flp中其他搜索字段相匹配的路由。这个详细检查是由fib_semantic_match来完成的。

fib_semantic_match也用查找结果来初始化输入参数res，如果它返回成功，fn_hash_lookup就将该结果返回给调用方。fn_hash_lookup遍历路由表中所有的active zone，直到fib_semantic_match或者返回一个成功结果，或者发现该路由表中没有可用的路由（即这些路由项都不匹配）。

标签：

给我留言