Linuxkernel路由机制分析

1、Linux kernel路由机制分析 目录(?)-1. 一前言2. 二概述1. 基于策略的路由2. 路由策略数据库3. 相关代码3. 三路由部分结构1. 总体结构2.3. IP接口部分结构4. 路由策略数据库部分结构5. 接口部分结构4. 四主要路由流程分析5. 五一些细节问题1. 关于路由中的错误处理2. 策略性路由NAT功能的实现6. 六总结一前言我对linux2.4.18的相关代码进行了阅读，从关键的几个接口函数入手，进而理清了整个路由部分的主要脉胳，理解了一些细节问题的处理，但还是有些问题还没有完全搞清楚。路由部分代码主要在linux代码树的/net/ipv4/下面：对于下面报告内容的

2、组织，我想通过由整体到部分到细节的顺序，尽量把我阅读代码学习到的所有的知识做一个有层次有条理的总结。二概述1. 基于策略的路由目前在计算机网络中使用的传统路由算法都是根据IP包目的地址进行路由选择.然而在现实应用中经常有这样的需求：进行路由选择时不仅仅根据数据报的目的地址，而且根据数据报的其他一些特性如：源地址、IP协议、传输层端口，甚至是数据包的负载部分内容，这种类型的路由选择被称作基于策略的路由。2. 路由策略数据库在Linux中，从2.1版本的内核开始就实现了对基于策略的路由的支持，它是通过使用路由策略数据库(RPDB，routing policy database)替代传统的、基于目的

3、地址的路由表来实现的。RPDB通过包含的一些规则和多张路由表来选定合适的IP路由。这些规则可能会包含很多各种不同类型的键值(key)，因此这些规则没有默认的特定次序，规则查找次序或规则优先级都是由网络或系统管理员设定的。如下图所示，Linux的RPDB是一个由数字优先级值进行排序的线性规则列表。RPDB能匹配数据报源地址、目的地址、TOS、进入接口和fwmark值等。每个路由策略规则由一个选择器和一个动作指示组成。RPDB按照优先级递增的顺序被扫描，RPDB包含的每条规则的选择器被应用于数据报的源地址、目的地址、进入接口、TOS和fwmark值。若数据报匹配该规则对应于该规则的动作被执行。若动

4、作成功返回，则规则输出将是一个有效的路由或是路由查找失败指示；否则查找RPDB的下一条规则。规则的动作通常是查一张与之对应的路由表，但也可以是如下几种：REJECT(丢弃)，PROHIBIT或决UNRECHABLE(丢弃并向源地址发送ICMP包)，NAT(源地址网络地址转换)等。路由表项的类型除了表示指出下一跳的相关信息外，还可以表示：BLACKHOLE(丢弃)，PROHIBIT或UNREACHABL(丢弃并向源地址发送ICMP包)E，NAT(目的地址网络地址转换)等。由图中所示，系统默认已经实现了三个策略（本地策略、主策略和默认策略），与之对应的是三张默认路由表（本地路由表、主路由表和默认路

5、由表）3. 相关代码我们主要分析了内核关于路由部分的代码，主要如下：linux/net/ipv4/*route.c提供了路由部分给IP层调用的接口。fib_rules.c提供对路由策略数据库的查找接口，并维护策略表。fib_hash.c 对路由表的查找，维护等。fib_semantics.c路由表的语义操作，维护路由项信息表(fib_info_list)。fib_frontend.c提供对路由表进行操作的接口。linux/include/net/*route.h路由cache中相关的一些数据结构。ip_fib.h定义了路由部分很多重要的结构。neighbour.hstruct neighbou

6、r的定义。dst.h对路由cache结点中dst_entry结构的定义。linux/net/core/*dst.c对路由cache结点分配等动作。eighbour结构相关操作。三路由部分结构1. 总体结构内核路由部分代码实际上是ipv4协议栈的一部分，它被ip层的代码所调用。主要的调用时机有两个：一个是IP包输出时，需要确定由哪个端口出去；另一个是IP包输入时，需要确定是发给本机还是选择一个端口发送出去。整个路由系统可以分成三部分：IP层调用接口，路由策略数据库，和前后端接口。1 IP层调用接口主要是提供一组调用接口给IP层代码，这些接口最终完成了整个的路由工作。为了提

7、高效率，这部分代码维护了一个路由策略数据库的缓存或者叫cache，这部分代码另一个主要功能就是维护这个缓存了。这部分的代码主要在route.c文件中。2 路由策略数据库部分主要包括一个策略库和多张路由表，还有一些相关的操作它们的函数。当路由缓存没有命中的情况下，就要由这部分完成最后的查找工作。这部分的代码主要在fib_rules.c，fib_hash.c，fib_semantics.c中。3 前底端接口部分主要是给用户提供的一些对路由策略数据库增删改的操作函数，对/proc接口的实现，以及一些定时器的操作。这部分代码主要在fib_frontend.c中，还有一些分散在其它文件中。2. IP接口

8、部分结构这部分即是route.c的内容，主要定义了路由cache还有提供给IP层调用的几个接口函数。我们先来介绍一下路由cache的定义：static struct rt_hash_bucket *rt_hash_table;这个rt_hash_table即是路由cache，它是一个rt_hash_bucket结构：struct rt_hash_bucket struct rtable *chain; rwlock_t lock;struct rtable的结构定义如下：struct rtable union struct dst_entry dst; struct rtable *rt_ne

9、xt; u; unsigned rt_flags; unsigned rt_type; _u32 rt_dst; _u32 rt_src; int rt_iif; _u32 rt_gateway; struct rt_key key; _u32 rt_spec_dst; struct inet_peer *peer;#ifdef CONFIG_IP_ROUTE_NAT _u32 rt_src_map; _u32 rt_dst_map;#endif;struct rt_key _u32 dst; _u32 src; int iif; int oif; _u8 tos; _u8 scope; 实际

10、上这个rt_hash_table就是一张hash table。每个hash值相同的结点都挂在一个list上即struct rt_hash_bucket的chain成员，它的lock成员用于对这个list进行加锁以实现临界资源的互斥访问。每个结点是一个rtable结构，这个结构比较重要，实际上路由查询的最终结果就是把一个对应的rtable结构的地址赋给skb->dst。这个结构的域key就是hash表检索时所用来比较的关键字，这个结构包含了dst(目标地址),src(源地址),iif(入端口),oif(出端口),tos(服务类型),scope(目标地址的范围)，这些也就是查找路由缓存时所要

11、匹配的值，即如果这些都匹配了，那么说明cache命中，否则还要继续检索。下面这个图显示了路由缓存的完整结构：这一部分主要提供了两个供IP层调用的入口函数：int ip_route_input( struct sk_buff* skb, u32 dst, u32 src, u8 tos, struct net_device *dev );int ip_route_output( struct rtable *rp, u32 daddr, u32 saddr, u32 tos, int oif )其中ip_route_input函数即是在处理从网络上进来的IP包时调用的路由函数，它的结果主要有两个

12、：即如果是本地包则传给上层协议层，如果不是则选则一个出端口再发送出去。函数的参数有5个：skb表示ip包的缓冲区，dst目的地址，src源地址，tos表示IP包服务类型，dev表示入端口。函数返回值指示错误，如果成功查到路由，函数返回后，skb->dst会被赋值。与之相对ip_route_output函数则是处理本机发出的IP包时调用的路由函数，它的结果只是为其选择一个下一跳以及出端口。参数也是5个：rp是个输出参数，返回时*rp指向一个返回的rtable结构的路由结点；daddr目的地址，saddr源地址，tos服务类型，oif出接口。函数返回值指示错误。这一部分其它一些比较重要的函数

13、有：ip_route_input_slow：当ip_route_input查cache不命中时调用此函数，此函数进而调用路由策略数据库的查询接口进行查询，然后更新路由cache。ip_route_output_slow：当ip_route_output查cahe不命中是调用此函数，此函数进而调用路由策略数据库的查询接口进行查询，然后更新路由cache。rt_intern_hash：将新rtable结构的结点插入到路由缓存中。rt_garbage_collect：对路由缓存进和垃圾收集。3. 路由策略数据库部分结构这一部分主要包括策略表及路由表的定义，以及查询等操作。策略表static stru

14、ct fib_rule *fib_rules = &local_rule;fib_rules即是策略表，它是一个fib_rule结构：struct fib_rule struct fib_rule *r_next; atomic_t r_clntref; u32 r_preference; unsigned char r_table; unsigned char r_action; unsigned char r_dst_len; unsigned char r_src_len; u32 r_src; u32 r_srcmask; u32 r_dst; u32 r_dstmask; u

15、32 r_srcmap; u8 r_flags; u8 r_tos; int r_ifindex; char r_ifnameIFNAMSIZ; int r_dead;整个策略表的结构如下图：这个策略表实际上就是一个单链表，整个单链表按策略的优先级由高到低的顺序排列，表头指针即是fib_rule。每个策略是一个fib_rule结构。这个结构有几个重要的域：r_preference 这个策略的优先级。r_table 这个策略对应的路由表，它是路由表索引表fib_tables的一个索引值。r_action 策略的动作，如单播，丢弃，NAT等。r_src,r_srcmask,r_dst,r_dstm

16、ask,r_tos等策略的选择器，即描述什么样的IP包匹配这条策略。系统默认已经定义了三个策略：static struct fib_rule default_rule = r_clntref: ATOMIC_INIT(2), r_preference: 0x7FFF, r_table: RT_TABLE_DEFAULT, r_action: RTN_UNICAST,;static struct fib_rule main_rule = r_next: &default_rule, r_clntref: ATOMIC_INIT(2), r_preference: 0x7FFE, r_ta

17、ble: RT_TABLE_MAIN, r_action: RTN_UNICAST,;static struct fib_rule local_rule = r_next: &main_rule, r_clntref: ATOMIC_INIT(2), r_table: RT_TABLE_LOCAL, r_action: RTN_UNICAST,;可以看到这三个策略（本地策略，主策略，默认策略）按照优先级的由高到低的次序排列，它们的选择器都是0，即表示匹配所有类型的IP包。它们的动作都是单播就表示都是查对应的路由表。它们分别对应三张路由表（本地路由表，主路由表，默认路由表）。其意义就是对

18、于一个IP包，系统总是按本地路由表->主路由表->默认路由表的次序进行查找的。路由表定义如下：struct fib_table *local_table;struct fib_table *main_table;struct fib_table *fib_tablesRT_TABLE_MAX+1;它的数据结构是：struct fib_table unsigned char tb_id; unsigned tb_stamp; int (*tb_lookup)(struct fib_table *tb, const struct rt_key *key, struct fib_resu

19、lt *res); int (*tb_insert)(); int (*tb_delete)(); int (*tb_dump)(); int (*tb_flush)(struct fib_table *table); int (*tb_get_info)(); void (*tb_select_default)(); unsigned char tb_data0;fib_table是系统中所有路由表的索引数组。系统另外定义了两个路由表指针local_table和main_table，分别指向默认定义的两个路由表。在前面我们曾介绍系统定义了三张路由表，还有一张即是默认路由表，实际上它只是一张空

20、表，一般并没有用到。实际上,fib_table结构只是一个路由表结构中最上层的一个结构，它下面还很多的层次，下面这张图描绘了整个路由表的数据结构：整个结构看起来比较复杂，我们可以把它分成4个层次来看：第一个层次是fib_table和fn_hash结构。实际上，fn_hash结构即是fib_table的tb_data域。这一层主要是包括一个路由表所对应的标识符(tb_id)，操作函数指针(tb_looup等)，以及对所有路由项的一个总索引(fn_hash结构)。最为重要的就是这个索引，一个路由表把它所有的路由项划分成33个区域，划分的原则即是子网掩码的长度（从0到32），这33个区域分别对应着f

21、n_hash结构中的fz_zone0到fz_zone32。之所以这么划分的原因就因为，路由的表的查找要从最精确到最不精确，也就是说要从掩码最长的路由项查起。第二个层次是fn_zone结构。每个fn_zone代表了一个区域，由于并不是33个区域都会同时存在，一般往往只有常用到的掩码长度（如0,16,24,32位）对应的区域才存在，所以所有存在的区域按从大到小的顺序被链成一个list，从而提高查找的效率。这人fn_zone结构中最重要的就是fz_hash域了，它指向了一个hash table，这个hash table组织了这个区域下的所有路由项。第三个层次是代表路由项的fn_node结构。它是ha

22、sh table的结点，其中fn_key域即是hash查找的关键字，它实际上就是路由项的目标网络号。这个结构的提供了路由查找的结果信息，fn_type这个域指示了这个路由项的含义：单播转发，本地，丢弃，NAT等等。对于大多数情况，路由项都是单播转发类型的，这时关于下一跳的信息就入在fn_info中了，它指向一个fib_info结构。第四个层次即是fib_info结构。因为很多的路由项具有相同的下一跳信息，即fn_node与fib_info结构是多对一的关系。所以fn_node中只存放一个指向fib_info的指针fn_info。所有fib_info结构被单独管理，它们被组织成一个双向链表，表头

23、为fib_info_list。关于下一跳的具体信息由fib_nh数组指示，它是一个数组意味着一个下一跳决策可以对应着多个物理的下一跳，这是linux支持的一个MULITPATH功能。处理函数这部分的处理函数中最为重要的就是对路由策略数据库的查找函数fib_lookup，以及对单个路由表进行查找的fn_hash_lookup函数。fib_lookup的定义:int fib_lookup(const struct rt_key *key, struct fib_result *res)这个函数的工作就是对整个路由策略数据库进行查找，它会在需要的时候调用fn_hash_lookup查找特定的路由表。

24、函数有两个参数，key是查找的关键字，它与路由缓存查找时的key是一致的。res是输出参数，函数返回后如果成功则在res存入查找结果。函数的返回值用来指示错误。static intfn_hash_lookup(struct fib_table *tb, const struct rt_key *key, struct fib_result *res)这个函数的即是对路由进行查找。参数有3个，tb指示待查的路由表，key查找关键字，res指向的结构存放查找的结果。函数返回值指示错误。4. 接口部分结构这一部分主要实现以下几个功能：1对路由表，策略表进行增加项，删除项，创建表，表空路由缓存等操作。

25、2为路由策略数据库，路由缓存提供/proc接口。3设置定时器，以定时对路由缓存进行清理工作。四主要路由流程分析前面已经介绍过，IP层会在输入和输出两个时候去调用路由部分代码。输入路由过程更为复杂一些也更具代表性，所以我们下面主要分析一下IP包输入时的路由流程。下图描述了这个流程：当有数据到达网络设备的时候，会产生一个中断，中断处理函数会调用驱动层的net_rx函数，net_rx进而产生个软中断进入net_rx_action函数，进而如是发现这个数据帧是IP包的话，它就调用IP协议层的ip_rcv函数，它进而又调用ip_rcv_finish函数。在这个函数，它调用路由代码的IP接口函数ip_ro

26、ute_input进行路由。可以看到传递给路由代码的参数有5个：skb IP包缓冲区，iph->daddr IP包的目的地址，iph->saddr IP包源地址，iph->tos 服务类型，dev 输入的网络设备。当这个ip_route_input函数返回时，就意味着路由工作已经结束，如果返回值是0，那么就说明已经成功找到了路由。那么这个路由查询结果放在哪里呢？它就在skb->dst，它指向的就是查到的路由缓存中的一个结点。下边通过调用skb->dst->input(skb)就可以对这个IP进行处理了。这个input是路由缓存结点中的一个函数指针，如果这个路

27、由项表示转发的，那么这个指针实际上指向的是ip_local_deliver，而如果是传送给本地的，那么指向的是ip_forward。ip_local_deliver会将这个IP包进一步传给上层协议层处理，ip_forward则会再将这个IP包从网络设备发送出去。我们再来看一下路由的具体流程。首先调用的是ip_route_input，它的任务主要是查路由缓存，如果找到了那么它给skb->dst赋值并返回，如是没找到，它会调用ip_route_input_slow去查询路由策略数据库。下面是经过简化的代码和注释：int ip_route_input(struct sk_buff *skb,

28、u32 daddr, u32 saddr, u8 tos, struct net_device *dev)int iif = dev->ifindex;hash = rt_hash_code(daddr, saddr (iif << 5), tos);/*遍历hash table */for (rth = rt_hash_tablehash.chain; rth; rth = rth->u.rt_next ) /* 只有这五个量都匹配才算命中，要比较这么多量是因为在基于策略的路由中，有一个量不同就有可能选择不同的策略。*/if ( rth->key.dst = d

29、addr && rth->key.src = saddr && rth->key.iif = iif && rth->key.oif = 0 && rth->key.tos = tos ) rth-> = jiffies;dst_hold(&rth->u.dst);rth->+;/*关键的一步，为dst为赋值*/skb->dst = (struct dst_entry*)rth;return 0;/*如果缓存查不到，那么调用这个函数*/return ip_route_inpu

30、t_slow(skb, daddr, saddr, tos, dev);ip_route_input_slow函数的主要任务是去调用路由策略数据库的查找函数fib_lookup进行查找，然后更新路由缓存。因为这个函数很长，我们用下面的流程图来表示一些主要的流程：当调用过fib_lookup后，函数会根据查找的结构进行不同的处理。一般情况是转发或者本地，这两种的情况都会先分配一个新的路由缓存结点，填充适当的值然后插入到缓存中；两者的不同主要在于，设置dst.input函数分别为ip_forward或ip_local_deliver，转发的情况还要绑定关于下一跳信息的neighbour(这个结构主

31、要用来得到网段上邻居的物理地址)。除了转发或本地还有可能是其它情况，比如有错误，没查到，丢弃，NAT等。fib_lookup函数是路由策略数据库的查询接口，它首先查找策略表，找到一条匹配的策略，然后再执行该策略所对应的动作，动作一般来说就是要查找对应的一张路由表，所以接下来会调用fn_hash_lookup函数进行处理。下面是这个函数的简化后的代码和相关注释：fib_lookup(const struct rt_key *key, struct fib_result *res) /*循环遍历策略表*/for (r = fib_rules; r; r=r->r_next) /*如果有一项不

32、符，继续查找下一个*/if ( (saddrr->r_src) & r->r_srcmask) | (daddrr->r_dst) & r->r_dstmask) | (r->r_tos && r->r_tos != key->tos) | (r->r_ifindex && r->r_ifindex != key->iif) )continue;/*判断策略的动作*/switch (r->r_action) case RTN_UNICAST:case RTN_NAT:policy

33、= r;break;default:case RTN_BLACKHOLE:read_unlock(&fib_rules_lock);return -EINVAL;/*得到策略所对应的路由表*/if (tb = fib_get_table(r->r_table) = NULL) continue;/*查找路由表*/err = tb->tb_lookup(tb, key, res);/*返回0表示查找成功*/if (err = 0) res->r = policy; return 0; /*如果有错误，则返回错误号，如果是-EAGAIN或正数则查下一策略*/if (err

34、 < 0 && err != -EAGAIN) return err;return -ENETUNREACH;fn_hash_lookup函数的主要功能即是对路由表的查找。如下：int fn_hash_lookup(struct fib_table *tb, const struct rt_key *key, struct fib_result *res)/*从大到小遍历区域*/for (fz = t->fn_zone_list; fz; fz = fz->fz_next) fn_key_t k = fz_key(key->dst, fz);/*遍历一区

35、域内的hash table */for (f = fz_chain(k, fz); f; f = f->fn_next) if (!fn_key_eq(k, f->fn_key) if (fn_key_leq(k, f->fn_key) break;else continue;/*找到匹配的路由项*/if (f->fn_state&FN_S_ZOMBIE) continue;/*进行语义上的检查和设置如果是单播，把fib_info赋给res 如果是其它，相应作一些处理*/err = fib_semantic_match(f->fn_type, FIB_IN

36、FO(f), key, res);/*没有错误的情况*/if (err = 0) res->type = f->fn_type;res->prefixlen = fz->fz_order;goto out;if (err < 0) goto out;/*如果没有找到匹配的路由项，返回正值表示上层函数处理下一个策略*/err = 1;out: return err;五一些细节问题1. 关于路由中的错误处理这里的错误是指找不到路由项，还包括丢弃、禁止、不可到达等情况。这些情况产生的原因可能是因为路由表中找不到相应的项或是用户设置了相应的策略或路由项对特定IP包进行丢弃

37、等处理。在这种情况下fib_lookup会返回一个错误值，如-ENETUNREACH，-BLACKHOLE等。接着在ip_route_input_slow中 if (err = fib_lookup(&key, &res) != 0) if (!IN_DEV_FORWARD(in_dev) goto e_inval; goto no_route; 即会跳到no_route处：no_route:rt_cache_statsmp_processor_id().in_no_route+;spec_dst = inet_select_addr(dev, 0, RT_SCOPE_UNIVERSE);res.type = RTN_UNREACHABLE;goto local_input;它把res.type标记成RTN_UNREACHABLE然后跳到本地包情况的处理代码，先是更新路由缓存，然后遇到如下代码： if (res.type = RTN_UNREACHABLE) rth->u.dst.input= ip_error; rth->u.dst.error= -err; rth->rt_flags &= RTCF_LOCAL; rth->rt_type = re