fn_hash_select_default函数的疑问1

jiufei19

内核版本V2.6.23，其他版本也类似，只是函数名改为fib_table_select_default
fn_hash_select_default函数的功能似乎是从多个可能的缺省路由中挑选一个，其代码逻辑我正在阅读，感到有点不太清楚，下面我先叙述第一个问题

   280 fn_hash_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
   281 {

   ...        ...

   285     struct fib_info *fi = NULL;
   ...        ...
   298     hlist_for_each_entry(f, node, &fz->fz_hash[0], fn_hash) { // 在代表多个缺省路由的fib_node结点链表上遍历
   299         struct fib_alias *fa;
   300
   301         list_for_each_entry(fa, &f->fn_alias, fa_list) { // 在当前fib_node结点的下属fib_alias结点链表上遍历

   315             if (fi == NULL) {
   316                 if (next_fi != res->fi)        
   317                     break;

   ...       ...

上面红色代码我有点不理解，我的问题是在第315行if条件成立的情况下，怎么可能还需要对第316行进行if判断呢，换句话讲，此时应该肯定有next_fi==res->fi成立才对。因为在fn_hash_lookup->fib_semantic_match调用过程中，我们已经找到了tos和scope都已确定的匹配路由，即res->fi就是已经找到的对应缺省路由，那么根据fib_node和fib_alias、fib_info的关系，即fib_alias按TOS属性的值进行升序排列，而相同tos的fib_alias再按其所关联的fib_info中的fib_priority的升序进行排列，此时的next_fi怎么可能与res->fi不等呢？

jiufei19

回复 1# jiufei19

为了描述更清晰些，下面我把相关场景代码列出，请大家解惑。
一、问题场景发生在本机发送外出报文时，进行 ip_route_output_slow路由查询，即如下：

  2142 static int ip_route_output_slow(struct rtable **rp, const struct flowi *oldflp)
  2143 {
  ...      ...
  2256     if (fib_lookup(&fl, &res)) {
  ...          ...
  2287     }
  ...      ...
  2310     if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
  2311         fib_select_default(&fl, &res);
  ...      ...



二、假定我们讨论的是非多路径路由场景，fib_lookup最终调用如下函数进行路由搜索：

   245 fn_hash_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
   246 {
   ...    ...
   252     for (fz = t->fn_zone_list; fz; fz = fz->fz_next) {
   253         struct hlist_head *head;
   254         struct hlist_node *node;
   255         struct fib_node *f;
   256         __be32 k = fz_key(flp->fl4_dst, fz);
   257            
   258         head = &fz->fz_hash[fn_hash(k, fz)];
   259         hlist_for_each_entry(f, node, head, fn_hash) {
   260         if (f->fn_key != k)
   261             continue;
   262
   263        err = fib_semantic_match(&f->fn_alias,
   264                     flp, res,
   265                     f->fn_key, fz->fz_mask,
   266                     fz->fz_order);


假定此时第252行已经遍历到的fz对应fn_zone[0]，即缺省路由，于是第259行在代表多个缺省路由的fib_node结点链表上遍历，于是第263行调用 fib_semantic_match函数对tos和scope两个路由属性进行匹配检查，并通过实参res带回找到的匹配项，并且我们假设：

1、对应0.0.0.0/0的fib_node结点中有两个缺省路由
2、fib_node中有4个fib_alias结点，分别为fib_alias1~fib_alias4，
3、进一步假设其中fib_alias2和fib_alias3具有相同的tos值， 并且与fib_alias1和fib_alias4的tos各不相同，并且fib_alias3的下属fib_info的fib_priority2大于fib_alias2下属的fib_info的fib_priority
4、fib_semantic_match函数在fib_node2的下属fib_alias2中找到了tos和scope都匹配

很显然，此时上面条件4fib_semantic_match函数所选出的匹配项就是fib_node2（以及其下的fib_alias2和再下的fib_info），于是第264行的res将对应此匹配项，那么就出现了我提出的疑问了，因为此时在fn_hash_select_default中第316行的比较就没有意义了。进一步我又对上面1-4条件进行了其他可能情况的假设，也有同样的问题出现！


我的理解哪里有误？

jiufei19

回复 2# jiufei19

又看了一遍相关代码，纠正下上面我说错的一个地方，即对应缺省路由而言，由于缺省路由为0.0.0.0/0，所以无论添加多少个缺省路由，始终都只对应一个fib_node结点，而不是我上面说的多个

jiufei19

回复 2# jiufei19

仔细研究了下代码，好像发现next_fi可以和res->fi不等，之前我按照Understanding Linux network Internal中的说明，认为fib_alias按tos和fib_priority的升序进行排列，现在发现好像该书似乎写错了，应该是fib_alias按tos降序排列，而在tos相同情况下，又按fib_priority的升序进行排列。

原文为：

Given a fib_node instance, the associated list of fib_alias instances is sorted in increasing order of IP TOS (i.e., the fa_tos field). fib_alias instances with the same value of fa_tos are sorted in increasing order of the associated fib_info's fib_protocol field.

jiufei19

回复 2# jiufei19

仔细研究了下代码，好像发现next_fi可以和res->fi不等，之前我按照Understanding Linux network Internal中的说明，认为fib_alias按tos和fib_priority的升序进行排列，现在发现好像该书似乎写错了，应该是fib_alias按tos降序排列，而在tos相同情况下，又按fib_priority的升序进行排列。

原文为：

Given a fib_node instance, the associated list of fib_alias instances is sorted in increasing order of IP TOS (i.e., the fa_tos field). fib_alias instances with the same value of fa_tos are sorted in increasing order of the associated fib_info's fib_protocol field.

jiufei19

回复 2# jiufei19

我又仔细看了遍代码，发现我之前对fib_alias结点的排序方法有点理解错误，之前我是按understanding Linux network internal一书中如下描述进行理解的：

Given a fib_node instance, the associated list of fib_alias instances is sorted in increasing order of IP TOS (i.e., the fa_tos field). fib_alias instances with the same value of fa_tos are sorted in increasing order of the associated fib_info's fib_priroity field.

现在发现该书好像写错了，应该是tos是按降序排列，而fib_priority是按升序排列。

如果这样的话，则next_fi似乎就可以和fi不是同一个了，因为在fn_hash_select_default函数中，是从fib_node的下属首个fib_alias开始进行遍历，只要改fib_alias结点不是之前fib_semantic_match函数所返回的那个fib_alias，则next_fi就和fi不一样了。

jiufei19

回复 6# jiufei19

经过仔细分析代码，发现导致next_fi可以不等于fi的根本原因是在fn_hash_select_default函数中不对tos进行判断所致，但是这样又引起了我的另外一个疑问，既然都不对tos进行限定判断了，那么下面的这个检查又有什么特别意义呢？
   308             if (next_fi->fib_priority > res->fi->fib_priority)
   309                 break;


上述这个检查实际是对当tos匹配下进行的进一步检查，但是现在并不考虑tos了，这个检查似乎就有点不好理解了，请问到底如何理解？

nswcfd

lookup和select_default之间有没有可能插入新的默认路由？

jiufei19

回复 8# nswcfd

从代码上看，fib_lookup后，在fn_hash_select_default之前是可以添加新的缺省路由的。

在fib_lookup时会加只读锁，结束后会释放只读锁


  2256     if (fib_lookup(&fl, &res)) {
  ...         ...
  2287     }
  2288     free_res = 1;
  ...      ...
  2310     if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
  2311         fib_select_default(&fl, &res);

那么当然可能在第2311行被执行前，另外一个操作刚好添加完一条新的缺省路由。不过暂且不论会出现这种情况，即便没有新增缺省路由的情况下，我现在对此函数的处理逻辑仍然感到不可理解，接下来我准备单独再发个帖子仔细描述下现在的疑问。