浅析Linux Kernel 哈希路由表实现(二) -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 浅析Linux Kernel 哈希路由表实现(二)

浅析Linux Kernel 哈希路由表实现(二)

浏览:1942次出处信息

在向外发送数据包的时候，首先需要查询路由表来确定路由包的路由，主要由ip_route_output_key()函数来完成，该函数又调用了ip_route_output_flow()，而这个函数最终又调用了__ip_route_output_key()这个函数来进行路由的查询，下面主要来看一下这个函数：

int __ip_route_output_key(struct net *net, struct rtable **rp,
     const struct flowi *flp)
{
 unsigned int hash;
 int res;
 struct rtable *rth;
 
 if (!rt_caching(net))
  goto slow_output;
 
 hash = rt_hash(flp->fl4_dst, flp->fl4_src, flp->oif, rt_genid(net));
 
 rcu_read_lock_bh();
 for (rth = rcu_dereference_bh(rt_hash_table[hash].chain); rth;
  rth = rcu_dereference_bh(rth->dst.rt_next)) {
  if (rth->fl.fl4_dst == flp->fl4_dst &&
      rth->fl.fl4_src == flp->fl4_src &&
      rth->fl.iif == 0 &&
      rth->fl.oif == flp->oif &&
      rth->fl.mark == flp->mark &&
      !((rth->fl.fl4_tos ^ flp->fl4_tos) &
       (IPTOS_RT_MASK | RTO_ONLINK)) &&
      net_eq(dev_net(rth->dst.dev), net) &&
      !rt_is_expired(rth)) {
   dst_use(&rth->dst, jiffies);
   RT_CACHE_STAT_INC(out_hit);
   rcu_read_unlock_bh();
   *rp = rth;
   return 0;
  }
  RT_CACHE_STAT_INC(out_hlist_search);
 }
 rcu_read_unlock_bh();
 
slow_output:
 rcu_read_lock();
 res = ip_route_output_slow(net, rp, flp);
 rcu_read_unlock();
 return res;
}

Linux的路由表中的常用路由是存储在路由缓存中的，该路由缓存即是类型为struct rt_hash_bucket的全局列表rt_hash_table，该缓存列表在ip_rt_init()中初始化。

struct flowi结构中包含了查询路由表所需要的请求信息，是一个搜索健值。由代码可看出，首先在路由缓存列表rt_hash_table中查询精确匹配的未过期的路由表项struct rtable，(注，因为是出口路由，所以入口接口号是0)，若找到后增加路由表项的引用计数和后即刻返回。若未找到匹配的路由表项，则继续在路由表中查找匹配的路由表项，路由表中的查询速度会比路由缓存中慢，所以ip_route_output_slow()函数的命名就不难理解了，主动的路由解析工作都是在这个函数里面进行的，在看它的定义之前先看下服务类型和路由范围的相关定义：

#define IPTOS_TOS_MASK  0x1E
#define IPTOS_TOS(tos)  ((tos)&IPTOS_TOS_MASK)
#define IPTOS_LOWDELAY  0x10 /* 最小延时 */
#define IPTOS_THROUGHPUT 0x08 /* 最大吞吐量 */
#define IPTOS_RELIABILITY 0x04 /* 最高可靠性 */
#define IPTOS_MINCOST  0x02 /* 最小消费 */
#define RTO_ONLINK          0x01

由掩码可知，服务类型实际上用了从第2位到第5位共四位的数据，表示四种服务类型，而最低位的RTO_ONLINK如果置位，则scope为RT_SCOPE_LINK，或没有，则scope为RT_SCOPE_UNIVERSE，接下来看看scope的相关定义：

enum rt_scope_t {
 RT_SCOPE_UNIVERSE=0,  /* 表示在空间中的任何位置 */
/* User defined values  */
 RT_SCOPE_SITE=200,
 RT_SCOPE_LINK=253,   /* 与本地直接相连的地址 */
 RT_SCOPE_HOST=254,   /* 本地地址 */
 RT_SCOPE_NOWHERE=255  /* 不可达的地址 */
};

其中值越大所表示的范围便越精确，实际上这也不是什么范围的意思，只不过是到目的地址的某种距离的表示。OK，接下来看ip_route_output_slow()函数的定义：

static int ip_route_output_slow(struct net *net, struct rtable **rp,
    const struct flowi *oldflp)
{
 u32 tos = RT_FL_TOS(oldflp);
 struct flowi fl = { .nl_u = { .ip4_u =
          { .daddr = oldflp->fl4_dst,
     .saddr = oldflp->fl4_src,
     .tos = tos & IPTOS_RT_MASK,
     .scope = ((tos & RTO_ONLINK) ?
        RT_SCOPE_LINK :
        RT_SCOPE_UNIVERSE),
          } },
       .mark = oldflp->mark,
       .iif = net->loopback_dev->ifindex,
       .oif = oldflp->oif };
 struct fib_result res;
 unsigned int flags = 0;
 struct net_device *dev_out = NULL;
 int err;
 
 
 res.fi  = NULL;
#ifdef CONFIG_IP_MULTIPLE_TABLES
 res.r  = NULL;
#endif
 
 if (oldflp->fl4_src) {
  /* 若源地址为组播地址，受限广播地址(255.255.255.255)或0地址，
  均不合法，即刻返回 */
  err = -EINVAL;
  if (ipv4_is_multicast(oldflp->fl4_src) ||
      ipv4_is_lbcast(oldflp->fl4_src) ||
      ipv4_is_zeronet(oldflp->fl4_src))
   goto out;
 
  if (oldflp->oif == 0 &&
      (ipv4_is_multicast(oldflp->fl4_dst) ||
       ipv4_is_lbcast(oldflp->fl4_dst))) {
   /* 等价于inet_addr_type(saddr) == RTN_LOCAL, 
   __ip_dev_find()函数实际是搜索RT_TABLE_LOCAL
   路由表中的路由表项，如果未找到对应设备则返回，因为
   Linux不允许环回接口发组播或受限广播 */
   dev_out = __ip_dev_find(net, oldflp->fl4_src, false);
   if (dev_out == NULL)
    goto out;
 
   /* 给外面接口赋值后转去创建路由缓存 */
   fl.oif = dev_out->ifindex;
   goto make_route;
  }
 
  if (!(oldflp->flags & FLOWI_FLAG_ANYSRC)) {
   /* It is equivalent to inet_addr_type(saddr) == RTN_LOCAL */
   if (!__ip_dev_find(net, oldflp->fl4_src, false))
    goto out;
  }
 }
 
 
 if (oldflp->oif) {
  dev_out = dev_get_by_index_rcu(net, oldflp->oif);
  err = -ENODEV;
  if (dev_out == NULL)
   goto out;
 
  /* 如果外出接口示启用或外出接口对应的IPv4数据不存在，则返回网络不可达 */
  if (!(dev_out->flags & IFF_UP) || !__in_dev_get_rcu(dev_out)) {
   err = -ENETUNREACH;
   goto out;
  }
  /* 若是本地组播地址或受限广播地址则直接转去创建路由缓存 */
  if (ipv4_is_local_multicast(oldflp->fl4_dst) ||
      ipv4_is_lbcast(oldflp->fl4_dst)) {
   if (!fl.fl4_src)
    fl.fl4_src = inet_select_addr(dev_out, 0,
             RT_SCOPE_LINK);
   goto make_route;
  }
 
  /* 若未指定源地址，则根据目地地址类型创建选择一个源地址 */
  if (!fl.fl4_src) {
   if (ipv4_is_multicast(oldflp->fl4_dst))
    fl.fl4_src = inet_select_addr(dev_out, 0,
             fl.fl4_scope);
   else if (!oldflp->fl4_dst)
    fl.fl4_src = inet_select_addr(dev_out, 0,
             RT_SCOPE_HOST);
  }
 }
 
 /* 如果目的地址不存在，则令目的地址等于源地址，若都不存在，则使用环回接口，
  路由类型为本地路由，转而创建路由缓存 */
 if (!fl.fl4_dst) {
  fl.fl4_dst = fl.fl4_src;
  if (!fl.fl4_dst)
   fl.fl4_dst = fl.fl4_src = htonl(INADDR_LOOPBACK);
  dev_out = net->loopback_dev;
  fl.oif = net->loopback_dev->ifindex;
  res.type = RTN_LOCAL;
  flags |= RTCF_LOCAL;
  goto make_route;
 }
/*
OK, 走到这里先总结一下不需要查询路由表即可直接创建路由缓存的情况：
1. 指定了源地址，未指定外出接口，目的地址为组播地址或受限广播地址
2. 指定了外出接口，并且目的地址为本地组播地址或受限广播地址
3. 未指定目的地址。
 
若以上三种情况均未满足，则需要进行路由表查询。
*/
 
 if (fib_lookup(net, &fl, &res)) {
  res.fi = NULL;
  if (oldflp->oif) {
   /* 程序走到这里说明查询路由表失败，未找到对应的路由表项，
   但却指定了外出接口，这时候即便没有路由也是可以发送数据包的。
   当然，如果未指定外出接口，则只能返回网络不可达了。 */
   if (fl.fl4_src == 0)
    fl.fl4_src = inet_select_addr(dev_out, 0,
             RT_SCOPE_LINK);
   res.type = RTN_UNICAST;
   goto make_route;
  }
  err = -ENETUNREACH;
  goto out;
 }
 
 /* 若为本地路由，则使用环回接口 */
 if (res.type == RTN_LOCAL) {
  if (!fl.fl4_src) {
   if (res.fi->fib_prefsrc)
    fl.fl4_src = res.fi->fib_prefsrc;
   else
    fl.fl4_src = fl.fl4_dst;
  }
  dev_out = net->loopback_dev;
  fl.oif = dev_out->ifindex;
  res.fi = NULL;
  flags |= RTCF_LOCAL;
  goto make_route;
 }
 
/*  使用默认路由需要三个条件：
1. 若前缀为0，也即掩码长度为0，默认路由匹配所有的目的地址。
2. 路由类型为RTN_UNICAST，我们知道本地地址，组播地址和广播地址
3. 未指定出口设备，上面我们提到即便是没有路由的情况下提供了出口设备，
数据包也是可以发送的。
 这时候路由是默认路由，因此我们需要选择默认网关 */
 if (!res.prefixlen && res.type == RTN_UNICAST && !fl.oif)
  fib_select_default(net, &fl, &res);
 
 if (!fl.fl4_src)
  fl.fl4_src = FIB_RES_PREFSRC(res);
 
 dev_out = FIB_RES_DEV(res);
 fl.oif = dev_out->ifindex;
 
make_route:
 /* 创建一条路由缓存 */
 err = ip_mkroute_output(rp, &res, &fl, oldflp, dev_out, flags);
 
out: return err;
}

接下来看下创建路由缓存的函数：

static int ip_mkroute_output(struct rtable **rp,
        struct fib_result *res,
        const struct flowi *fl,
        const struct flowi *oldflp,
        struct net_device *dev_out,
        unsigned flags)
{
 struct rtable *rth = NULL;
 int err = __mkroute_output(&rth, res, fl, oldflp, dev_out, flags);
 unsigned hash;
 if (err == 0) {
  hash = rt_hash(oldflp->fl4_dst, oldflp->fl4_src, oldflp->oif,
          rt_genid(dev_net(dev_out)));
  err = rt_intern_hash(hash, rth, rp, NULL, oldflp->oif);
 }
 
 return err;
}

该函数首先调用__mkroute_output()函数生成一条路由缓存，然后再调用rt_intern_hash()函数写入到缓存列表中去。

 
static int rt_intern_hash(unsigned hash, struct rtable *rt,
     struct rtable **rp, struct sk_buff *skb, int ifindex)
{
 struct rtable *rth, *cand;
 struct rtable __rcu **rthp, **candp;
 unsigned long now;
 u32   min_score;
 int  chain_length;
 int attempts = !in_softirq();
 
restart:
 chain_length = 0;
 min_score = ~(u32)0;
 cand = NULL;
 candp = NULL;
 now = jiffies;
 
 if (!rt_caching(dev_net(rt->dst.dev))) {
/* 如果路由未进行缓存，那么把路由的DST标示设为DST_NOCACHE，调用者
 便会知道这条路由未进行缓存，使用完成之后可以根据该标志对路由进
 行释放。如果在这里把路由给丢掉的话，那么当没有进行路由缓存的情况
 下调用都就没办不法解析路由信息了。 */
  rt->dst.flags |= DST_NOCACHE;
  if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
   int err = arp_bind_neighbour(&rt->dst);
   if (err) {
    if (net_ratelimit())
     printk(KERN_WARNING
         \"Neighbour table failure & not caching routes.\\n\");
    ip_rt_put(rt);
    return err;
   }
  }
 
  goto skip_hashing;
 }
 
 
 rthp = &rt_hash_table[hash].chain;
 
 spin_lock_bh(rt_hash_lock_addr(hash));
 /* 开始遍历哈希链表 */
 while ((rth = rcu_dereference_protected(*rthp,
   lockdep_is_held(rt_hash_lock_addr(hash)))) != NULL) {
  /* 如果路由已过期，则直接从列表中删除并释放内存空间 */
  if (rt_is_expired(rth)) {
   *rthp = rth->dst.rt_next;
   rt_free(rth);
   continue;
  }
  /* 如果未过期，并在列表中找到了匹配的路由，则将该路由缓存项拿到
   链表的最新端，并增加引用计数，释放新建待插入的缓存项内存。 */
  if (compare_keys(&rth->fl, &rt->fl) && compare_netns(rth, rt)) {
   *rthp = rth->dst.rt_next;
   rcu_assign_pointer(rth->dst.rt_next,
        rt_hash_table[hash].chain);
   rcu_assign_pointer(rt_hash_table[hash].chain, rth);
 
   dst_use(&rth->dst, now);
   spin_unlock_bh(rt_hash_lock_addr(hash));
 
   rt_drop(rt);
   if (rp)
    *rp = rth;
   else
    skb_dst_set(skb, &rth->dst);
   return 0;
  }
 
  if (!atomic_read(&rth->dst.__refcnt)) {
   u32 score = rt_score(rth);
 
   if (score <= min_score) {
    cand = rth;
    candp = rthp;
    min_score = score;
   }
  }
 
  chain_length++;
 
  rthp = &rth->dst.rt_next;
 }
 
 if (cand) {
  /* ip_rt_gc_elasticity used to be average length of chain
   * length, when exceeded gc becomes really aggressive.
   *
   * The second limit is less certain. At the moment it allows
   * only 2 entries per bucket. We will see.
   */
  if (chain_length > ip_rt_gc_elasticity) {
   *candp = cand->dst.rt_next;
   rt_free(cand);
  }
 } else {
/* 如果某个哈希槽上的链表长度大于所能接受的链表的最大长度，
 则说明哈希碰撞太严重，需要重构哈希表，这个长度目前定义为20。
 如果需要重构则增加重构计数current_rt_cache_rebuild_count的值，
 rt_caching()函数就是简单地判断该值是否超过最大值来断定缓存是否
 正在进行的，最大值为4。 */
  if (chain_length > rt_chain_length_max &&
      slow_chain_length(rt_hash_table[hash].chain) > rt_chain_length_max) {
   struct net *net = dev_net(rt->dst.dev);
   int num = ++net->ipv4.current_rt_cache_rebuild_count;
   if (!rt_caching(net)) {
    printk(KERN_WARNING \"%s: %d rebuilds is over limit, route caching disabled\\n\",
     rt->dst.dev->name, num);
   }
   /* 重建哈希列表，然后重新开始此函数 */
   rt_emergency_hash_rebuild(net);
   spin_unlock_bh(rt_hash_lock_addr(hash));
 
   hash = rt_hash(rt->fl.fl4_dst, rt->fl.fl4_src,
     ifindex, rt_genid(net));
   goto restart;
  }
 }
 
 /* 当路由为单播路由或者为外出路由(iif为0的情况即为外出路由)
 则需要把路由绑定到arp */
 if (rt->rt_type == RTN_UNICAST || rt->fl.iif == 0) {
  int err = arp_bind_neighbour(&rt->dst);
  if (err) {
   spin_unlock_bh(rt_hash_lock_addr(hash));
 
   if (err != -ENOBUFS) {
    rt_drop(rt);
    return err;
   }
 
   /* Neighbour tables are full and nothing
      can be released. Try to shrink route cache,
      it is most likely it holds some neighbour records.
    */
   if (attempts-- > 0) {
    int saved_elasticity = ip_rt_gc_elasticity;
    int saved_int = ip_rt_gc_min_interval;
    ip_rt_gc_elasticity = 1;
    ip_rt_gc_min_interval = 0;
    /* 路由表进行垃圾回收，这个以后再写 */
    rt_garbage_collect(&ipv4_dst_ops);
    ip_rt_gc_min_interval = saved_int;
    ip_rt_gc_elasticity = saved_elasticity;
    goto restart;
   }
 
   if (net_ratelimit())
    printk(KERN_WARNING \"ipv4: Neighbour table overflow.\\n\");
   rt_drop(rt);
   return -ENOBUFS;
  }
 }
 
 /* 将该表项放至哈希链表的头部 */
 rt->dst.rt_next = rt_hash_table[hash].chain;
 
 /*
  * Since lookup is lockfree, we must make sure
  * previous writes to rt are comitted to memory
  * before making rt visible to other CPUS.
  */
 rcu_assign_pointer(rt_hash_table[hash].chain, rt);
 
 spin_unlock_bh(rt_hash_lock_addr(hash));
 
skip_hashing:
 if (rp)
  *rp = rt;
 else
  skb_dst_set(skb, &rt->dst);
 return 0;
}

简单注释了一下几个比较重要的函数，求大牛批评指正。

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：浅析Linux Kernel 哈希路由表实现(一)

后一篇：关于hashcode 里面使用31 系数的问题 >>

文章信息

作者：levin 来源： basic coder
标签： Kernel 哈希路由表
发布时间：2012-03-18 23:47:53

建议继续学习

近3天十大热文