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;
}

#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

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  /* 不可达的地址 */
};

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;
}

 
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;
}