一  什么时候发生路由查找？

首先认识路由树：

具体说来：

根据ip地址来区分参考“IPv6地址类型：单播/组播/任播地址”:

（1）If the destination address matchesFE80::<EUI64>//数据包是发给本机，执行一般的收发，对于PC机而言就是走这条。通过dst_entry 到ND协议，发给最近的路由主机。

skb->dst->input=ip6_input

 skb->dst->output=ip6_output---

（2）Else if the destination address’s first 10bits matches FE80:://数据包需要转发到 默认网关（也就是局域网内的路由器）

skb->dst->input=ip6_forward

skb->dst->output=ip6_output

（3）Else if the destination address’s first 8bits matches FF00:://数据包广播

skb->dst->input=ip6_mc_input

skb->dst->output=ip6_output

（4）Else ( no match)

skb->dst->input=ip6_pkt_discard

skb->dst->output=ip6_pkt_discard

 

“ip前缀”对应的 ”路由节点“树：

                               引用自“台湾宜兰大学互联网交换技术课程Linux IPv6 Packet Forwarding”

其次：关键数据结构dst_entry：

最终生成的IP数据报的路由称为目的入口(dst_entry)，目的入口反映了相邻的外部主机在主机内部的一种“映象”，

struct dst_entry {

…..

int                        (*input)(structsk_buff *);//决定该路由树节点是应该转发 还是 接收

int                        (*output)(structsk_buff *);//发送接口

…...

union{

structdst_entry        *next;

structrtable __rcu        *rt_next;

structrt6_info                *rt6_next;

structdn_route __rcu        *dn_next;

};

};

 

两种情况会发生路由查找：

1）接收数据的时候:ip6_route_input（）

就是在主机接收到数据包的时候发生路由查找，为什么在接收数据的时候呢？因为一个数据包，需要路由判断其目的地（

如果目的地是本机，则进入接收的流程；

如果不是本机，则通过forward处理，然后进入发送流程；

如果都不是，则丢弃.

 

大概路由查找的原理是：主机需要通过路由表来判断数据包的目的地在ip6_rcv_finish()里面，会调用ip6_route_input(skb)，这个函数返回的是路由表中对应的fib6_node，这个节点的input函数，就会根据不同的目的地调用不同的函数来处理。

 

2）发送时候发生的路由：ip6_route_output（）

 

二  路由查找的调用流程和查找算法

1）接收数据的时候:ip6_route_input（）

ipv6_rcv（）---->ip6_rcv_finish（）----》ip6_route_input{

voidip6_route_input(struct sk_buff *skb)

{

conststruct ipv6hdr *iph = ipv6_hdr(skb);

structnet *net = dev_net(skb->dev);

intflags = RT6_LOOKUP_F_HAS_SADDR;

structflowi6 fl6 = {

.flowi6_iif= skb->dev->ifindex,

.daddr= iph->daddr,

.saddr= iph->saddr,

.flowlabel= ip6_flowinfo(iph),

.flowi6_mark= skb->mark,

.flowi6_proto= iph->nexthdr,

};

 

skb_dst_set(skb, ip6_route_input_lookup(net, skb->dev,&fl6, flags));

}

static inline voidskb_dst_set(struct sk_buff *skb, struct dst_entry *dst)

{

skb->_skb_refdst = (unsigned long)dst;---执行ip6_route_input_lookup（）

}

static structdst_entry *ip6_route_input_lookup(structnet *net,

structnet_device *dev,

structflowi6 *fl6, int flags)

{

if(rt6_need_strict(&fl6->daddr) && dev->type != ARPHRD_PIMREG)

flags|= RT6_LOOKUP_F_IFACE;

 

returnfib6_rule_lookup(net, fl6,flags, ip6_pol_route_input);

}

最终跑到：ip6_pol_route_input（）--->ip6_pol_route()--->fib6_lookup()----->---》fib6_lookup_1（）//查找路由表的Radix树。

 

2）发送时候发生的路由：ip6_route_output（）

所有在ip6_xmit之前都会先进行路由查找：例如：

Tcp_ipv6.c(trunk\kernel-3.10\net\ipv6):                err= ip6_xmit(sk, skb, fl6, np->opt, np->tclass);

Tcp_ipv6.c(trunk\kernel-3.10\net\ipv6):                ip6_xmit(ctl_sk,buff, &fl6, NULL, tclass);

Ipv6.c(trunk\kernel-3.10\net\dccp):                err= ip6_xmit(sk, skb, &fl6, np->opt, np->tclass);

dccp_v6_send_response（）---->ip6_dst_lookup_flow()进行路由查找

Ipv6.c(trunk\kernel-3.10\net\dccp):                ip6_xmit(ctl_sk,skb, &fl6, NULL, 0);

tcp_v6_send_synack()----》inet6_csk_route_req（）----ip6_dst_lookup_flow（）//进行路由查找

Ipv6.c(trunk\kernel-3.10\net\sctp):        returnip6_xmit(sk, skb, fl6, np->opt, np->tclass);

Inet6_connection_sock.c(trunk\kernel-3.10\net\ipv6):        res= ip6_xmit(sk, skb, &fl6, np->opt, np->tclass);

 

例如一般的tcp发送数据，tcp层到--->网络层：

Inet6_connection_sock.c@ inet6_csk_xmit(struct sk_buff *skb, struct flowi*fl_unused){

完成的工作：路由查找（就是找到一个合适的正确的dst）

int inet6_csk_xmit(struct sk_buff *skb, struct flowi*fl_unused)

{

structsock *sk = skb->sk;

structipv6_pinfo *np = inet6_sk(sk);

structflowi6 fl6;

struct dst_entry *dst;

intres;

//开始路由查找：

dst =inet6_csk_route_socket(sk, &fl6);//查找路由表，目的是根据路由表信息，找到该数据包的下一条地址。

...

skb_dst_set_noref(skb, dst);//把查找到的dst 赋值给，上层下来的skb包中的成员：skb->_skb_refdst

 

/* Restore final destination back after routing done */

fl6.daddr= np->daddr;

//路由查找结束；

res= ip6_xmit(sk, skb, &fl6, np->opt,np->tclass);

rcu_read_unlock();

returnres;

}

static structdst_entry *inet6_csk_route_socket(struct sock*sk,

structflowi6 *fl6)

{

structinet_sock *inet = inet_sk(sk);

structipv6_pinfo *np = inet6_sk(sk);

structin6_addr *final_p, final;

structdst_entry *dst;

//更新 一条dst 到flowi 信息

memset(fl6,0, sizeof(*fl6));

fl6->flowi6_proto= sk->sk_protocol;

fl6->daddr= np->daddr;

fl6->saddr= np->saddr;

fl6->flowlabel= np->flow_label;

IP6_ECN_flow_xmit(sk,fl6->flowlabel);

fl6->flowi6_oif= sk->sk_bound_dev_if;

fl6->flowi6_mark= sk->sk_mark;

fl6->fl6_sport= inet->inet_sport;

fl6->fl6_dport= inet->inet_dport;

fl6->flowi6_uid= sock_i_uid(sk);

security_sk_classify_flow(sk,flowi6_to_flowi(fl6));

 

final_p= fl6_update_dst(fl6, np->opt, &final);

//首先查找路由缓存中是否有匹配的dst

dst= __inet6_csk_dst_check(sk, np->dst_cookie);

if(!dst) {

//其次 到路由表里面去查找 dst

dst= ip6_dst_lookup_flow(sk, fl6, final_p, false);

 

if(!IS_ERR(dst))

__inet6_csk_dst_store(sk,dst, NULL, NULL);

}

returndst;

}

//到路由表里面去查找 dst的 流程是：

ip6_dst_lookup_flow（）-----》ip6_dst_lookup_tail（）----》ip6_route_output（）----》fib6_rule_lookup（）----》ip6_pol_route_output（）

----ip6_pol_route（）---》fib6_lookup（）---》fib6_lookup_1（）//查找路由表的Radix树。

 

 

 

3）查找算法：

fib6_lookup_1（）