LinuxIPv4路由功能的分析.docx

《LinuxIPv4路由功能的分析.docx》由会员分享，可在线阅读，更多相关《LinuxIPv4路由功能的分析.docx（25页珍藏版）》请在三一办公上搜索。

1、IPv4路由设计与实现相关知识文档编号：00-6201-100 当前版本：1.0.0.0 创建日期：2011-9-1 编写作者：ganjingwei路由知识总结前言3关于此文档3参考资料3第一章 路由的基本概念41.1路由的作用41.2路由的工作原理4第二章数据结构52.1 fib_table52.2 fn_hash52.3 fn_zone52.4 fib_node62.5 fib_alias62.6 fib_info72.7 fib_nh7第三章路由表的创建93.1创建路由表93.2掩码长度分类级103.3网络地址分类级123.4路由信息分类级133.5具体创建过程16第四章 Linux路由

2、功能实现192.1数据包流程192.2数据包路由过程202.3相关代码222.3.1 ip_rcv_finish 函数222.3.2 ip_route_input 函数222.3.3 ip_route_input_slow 函数232.3.4 _mkroute_input 函数252.3.5 fib_lookup 函数26刖言关于此文档此文档是本人这段时间内学习Linux网络协议栈路由功能相关知识，总结 并且整理出来的文档。供大家参考。本文档描述Linux相关知识，各章节说明如下：1前言，即此章节；2路由理论知识；3相关数据结构；4路由表的创建；5 Linux路由的实现及数据包流程。参考资料网

3、络资源。本文中的所有代码以broadcom4.12L.01为依据，内核代码为2.6。第一章 路由的基本概念1.1路由的作用路由器工作在ISO层次结构中的三层，根据三层协议的各种信息，完成数 据包的选路和转发，最终达到目的地。1.2路由的工作原理路由与网桥的区别，在于路由了解整个网络，而网桥只了解相连接的主机 或网络。因此路由在选路的过程中，更具有目的性。路由维持一张（多张）路由表来支持选路的功能。路由表与网桥表不同， 路由表是人为配置的（这里说的人为配置，可能是用户通过接口进行配置，也可 以是应用层本身对内核进行路由配置，比如动态更新路由自主学习等）。每个路由表中记录的信息有：源地址（网络）、

4、目的地址（网络）、目的网 关、scope （距离）。查询根据这些来匹配。匹配过程中，先匹配一个路由缓存， 再匹配路由表。路由缓存是由内核维持的，而路由表是人为配置的。缓存根据最 近使用的表项来更新，目的是为了提高查询效率，和CPU的cache 一样。在内核 中，路由表由fib_table_hash表示，路由缓存由rt_hash_table表示。第二章数据结构2.1 fib_table这是一个路由表的最高级结构。struct fib_table (struct hlist_node tb_hlist;u32 tb_id;unsigned tb_stamp;inttb_default;int (*

5、tb_lookup)(struct fib_table *tb, const struct flowi *flp, struct fib_result *res);int(*tb_insert)(struct fib_table *, struct fib_config *);int(*tb_delete)(struct fib_table *, struct fib_config *);int(*tb_dump)(struct fib_table *table, struct sk_buff *skb,struct netlink_callback *cb);int(*tb_flush)(s

6、truct fib_table *table);void(*tb_select_default)(struct fib_table *table,const struct flowi *flp, struct fib_result *res);unsigned char tb_data0;2.2 fn_hash这是路由表一级查找(按掩码查找)的散列结构体，包含了散列表头和散 列数组。struct fn_hash (struct fn_zone *fn_zones33;struct fn_zone *fn_zone_list;2.3 fn_zone这是路由表一级查找(按掩码查找)的具体信息保存的

7、结构体。struct fn_zone (struct fn_zone *fz_next; /* Next not empty zone */struct hlist_head*fz_hash;/* Hash table pointer*/intfz_nent; /* Number of entries*/intfz_divisor; /* Hash divisor*/u32fz_hashmask; /* (fz_divisor - 1)*/#define FZ_HASHMASK(fz) (fz)-fz_hashmask)intfz_order; /* Zone order */_be32fz_

8、mask;#define FZ_MAS K(fz) (fz)-fz_mask) ;2.4 fib_node这是路由表二级查找（网络地址查找）具体信息存放的结构体，其中fn_key 就是网络地址，通过fn_key和掩码长度来计算散列定位。struct fib_node （struct hlist_nodestruct list_head_be32struct fib_aliasfn_hash;fn_alias;fn_key;fn_embedded_alias;2.5 fibalias这个结构体包含了路由的具体信息的结构体，但是它不对其进行描述，而 是描述一些键值，用于标识和排序那些信息。真正的信

9、息包含在fa_info中。struct fib_alias (struct list_headfa_list;struct fib_info*fa_info;u8fa_tos;u8fa_type;u8fa_scope;u8fa_state;#ifdef CONFIG_IP_FIB_TRIEstruct rcu_head rcu;#endif;2.6 fib_info这个才是真正的路由信息结构。struct fib_info (struct hlist_node fib_hash;struct hlist_node fib_lhash;struct net*fib_net;intfib_tree

10、ref;atomic_tfib_clntref;intfib_dead;unsignedfib_flags;intfib_protocol;_be32fib_prefsrc;u32fib_priority;u32fib_metricsRTAX_MAX;#define fib_mtu fib_metricsRTAX_MTU-1#define fib_window fib_metricsRTAX_WINDOW-1#define fib_rtt fib_metricsRTAX_RTT-1#define fib_advmss fib_metricsRTAX_ADVMSS-1intfib_nhs;#if

11、def CONFIG_IP_ROUTE_MULTIPATHintfib_power;#endifstruct fib_nhfib_nh0;#define fib_devfib_nh0.nh_dev;2.7 fib_nh这个结构被包含在fib_info中，是路由下一条的信息，一般来说只有一个， 但是如果有多通路，也就是配置了 CONFIG_IP_ROUTE_MULTIPATH，才会有多个。 struct fib_nh (struct net_device *nh_dev;struct hlist_node nh_hash;struct fib_info *nh_parent;unsigned n

12、h_flags;unsigned char nh_scope;#ifdef CONFIG_IP_ROUTE_MULTIPATHintnh_weight;intnh_power;#endif#ifdef CONFIG_NET_CLS_ROUTE_u32nh_tclassid;#endifintnh_oif;_be32nh_gw;第三章路由表的创建3.1创建路由表默认路由表由内核创建的函数调用流程为：inet_init()-ip_init()-ip_fib_init()-fib_net_init()-ip_fib_net_init()net/ipv4/fib_frontend.c在这个函数中，首先

13、为路由表分配空间，这里的每个表项hlist_head实际 都会链接一个单独的路由表，FIB_TABLE_HASHSZ表示了分配多少个路由表，一 般情况下至少有两个LOCAL和MAIN。注意这里仅仅是表头的空间分配，还没 有真正分配路由表空间。net-ipv4.fib_table_hash = kzalloc(sizeof(struct hlist_head)*FIB_TABLE_HASHSZ, GFP_KERNEL);接下来的err = fib4_rules_init(net);真正分配了路由表空间 local_table = fib_hash_table(RT_TABLE_LOCAL);if

14、 (local_table = NULL)return -ENOMEM;main_table = fib_hash_table(RT_TABLE_MAIN);if (main_table = NULL)goto fail;然后将local和main表链入之前的fib_table_hash中 hlist_add_head_rcu(&local_table-tb_hlist, &net-ipv4.fib_table_hashTABLE_LOCAL_INDEX);hlist_add_head_rcu(&main_table-tb_hlist,&net-ipv4.fib_table_hashTABLE

15、_MAIN_INDEX);最后生成的结构如图3-1, LOCAL表位于fib_table_hash0, MAIN表位于 fib_table_hash1；两张表通过结构tb_hlist链入链表，而tb_id则标识了功 能，255 是 LOCAL 表，254 是 MAIN 表。图3-1路由表内核内部结构路由表的查找效率是第一位的，因此内核在实现时使用了多级索引来进行 加速：第一级：fn_zone，按不同掩码长度分类(如/5和/24)；第二级：fib_node，按不同网络地址分类(如124.44.33.0/24)；第三级：fib_info，按下一跳路由信息。当然，我们创建路由表也要按照这个顺序。3.

16、2掩码长度分类级关于上一节说的struct fn_hash，它表示了不同子网掩码长度hash表(即 fn_zone)，对于 ipv4，从 032 共 33 个。而 fn_hash 的实现则是 fib_table 的 最后一个参数 unsigned char tb_data0。注意这里fn_zone还只是空指针，我们还只完成了路由表初始化的一部分。 在 启 动 阶 段 还 会 调 用 inet_rtm_newroute()-fib_table_insert()-fn_new_zone()fib_hash.c 来 创建fn_zone结构，前面已经讲过，fn_zone 一共有33个，其中掩码长度为0

17、/0 表示为默认路由，fn_zone可以理解为相同掩码的地址集合。首先为fn_zone分配空间struct fn_zone *fz = kzalloc(sizeof(struct fn_zone), GFP_KERNEL);传入参数z代表掩码长度，z=0的掩码用于默认路由，一般只有一个，所以 fz_divisor只需设1；其它设为16；这里要提到fz_divisor的作用，fz-fz_hash 并不是个单链表，而是一个哈希表，而哈希表的大小就是fz_divisor。if (z) (fz-fz_divisor = 16; else (fz-fz_divisor = 1;fz_hashmask实际

18、是用于求余数的，当算出hash值，再hash & fz_hashmask 就得出了在哈希表的位置；而fz_hash就是下一层的哈希表了，前面已经提过路 由表被多组分层了，这里fz_hash就是根据fz_divisor大小来创建的；fz_order 就是子网掩码长度；fz_mask就是子网掩码。fz-fz_hashmask = (fz-fz_divisor - 1);fz-fz_hash = fz_hash_alloc(fz-fz_divisor);fz-fz_order = z;fz-fz_mask = inet_make_mask(z);从子网长度大于新添加fz的fn_zone中挑选一个不为

19、空的fn_zonesi， 将新创建fz设成fn_zonesi.next；然后将fz根据掩码长度添加到fn_zones 中相应位置；fn_zone_list始终指向掩码长度最长的fn_zone。for (i=z+1; ifn_zonesi)break;if (i32) (fz-fz_next = table-fn_zone_list;table-fn_zone_list = fz; else (fz-fz_next = table-fn_zonesi-fz_next;table-fn_zonesi-fz_next = fz;table-fn_zonesz = fz;fn_hash包含33数组元素

20、，每个元素存放一定掩码长度的fn_zone，其中 fn_zonei存储掩码长度为i。而fn_zone通过内部属性fz_next又彼此串连起 来，形成单向链表，其中fn_zone_list可以看作链表头，而这里链表的组织顺 序是倒序的，即从掩码长到短。其中结构如图3-2所示。图3-2路由表一级查找结构3.3网络地址分类级到上一节为止，fz_hash所分配的哈希表还没有插入内容，这部分为 fib_insert_node()完成：inet_rtm_newroute()-fib_table_insert()-fib_insert_node()net/i pv4/fib_hash.c。这里f是fib_n

21、ode，可以理解为具有相同网络地址的路由项集合。根据 fn_key(网络地址)和fz(掩码长度)来计算hash值，决定将f插入fz_hash的哪 个项。struct hlist_head *head = &fz-fz_hashfn_hash(f-fn_key, fz);hlist_add_head(&f-fn_hash, head);如果fib_node不存在，则会创建它，这里的kmem_cache_zalloc()其实就 是内存分配。new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);if (new_f = NULL)goto out;IN

22、IT_HLIST_NODE(&new_f-fn_hash);INIT_LIST_HEAD(&new_f-fn_alias);new_f-fn_key = key;f = new_f;3.4路由信息分类级路由表最后一层是fib_info，具体的路由信息都存储在此，它由 fib_create_info()创建。首先为fib_info分配空间，由于fib_info的最后一个属性是struct fib_nh fib_nh0，因此大小是 fib_info + nhs * fib_nh，这里的 fib_nh 代 表了下一跳(next hop)的信息，nhs代表了下一跳的数目，一般情况下nhs=1， 除非配

23、置了支持多路径。fi = kzalloc(sizeof(*fi)+nhs*sizeof(struct fib_nh), GFP_KERNEL);设置fi的相关属性fi-fib_net = hold_net(net);fi-fib_protocol = cfg-fc_protocol;fi-fib_flags = cfg-fc_flags;fi-fib_priority = cfg-fc_priority;fi-fib_prefsrc = cfg-fc_prefsrc;fi-fib_nhs = nhs;使fi后面所有的nh-nh_parent指向fi，设置后如图3-3所示change_nexth

24、ops(fi) (nexthop_nh-nh_parent = fi; endfor_nexthops(fi)图3-3 fib_info结构体设置fib_nh的属性，这里仅展示了单一路径的情况：struct fib_nh *nh = fi-fib_nh;nh-nh_oif = cfg-fc_oif;nh-nh_gw = cfg-fc_gw;nh-nh_flags = cfg-fc_flags;然后，再根据cfg-fc_scope值来设置nh的其余属性。如果scope是 RT_SCOPE_HOST，则设置下一跳 scope 为 RT_SCOPE_NOWHERE。if (cfg-fc_scope

25、= RT_SCOPE_HOST) (struct fib_nh *nh = fi-fib_nh;nh-nh_scope = RT_SCOPE_NOWHERE;nh-nh_dev = dev_get_by_index(net, fi-fib_nh-nh_oif);如果 scope 是 RT_SCOPE_LINK 或 RT_SCOPE_UNIVERSE，则设置下跳：change_nexthops(fi) (if (err = fib_check_nh(cfg, fi, nexthop_nh) != 0)goto failure; endfor_nexthops(fi)最后，将fi链入链表中，这里要

26、注意的是所有的fib_info(只要创建了的) 都会加入fib_info_hash中，如果路由项使用了优先地址属性，还会加入 fib_info_laddrhash 中。hlist_add_head(&fi-fib_hash,&fib_info_hashfib_info_hashfn(fi);if (fi-fib_prefsrc) (struct hlist_head *head;head = &fib_info_laddrhashfib_laddr_hashfn(fi-fib_prefsrc);hlist_add_head(&fi-fib_lhash, head);无论fib_info在路由表

27、中位于哪个掩码、哪个网段结构下，都与 fib_info_hash和fib_info_laddrhash无关，这两个哈希表与路由表独立，主 要是用于加速路由信息fib_info的查找。哈希表的大小为fib_hash_size，当 超过这个限制时，fib_hash_size * 2（如果哈希函数够好，每个bucket都有一 个fib_info） 。 fib_info在哈希表如图3-4所示。图3-4 fib_info结构与它的hash表由于路由表信息也可能要以设备dev为键值搜索，因此还存在 fib_info_devhash 哈希表，用于存储 nh 的设置 dev-ifindex。change_ne

28、xthops(fi) (hash = fib_devindex_hashfn(nexthop_nh-nh_dev-ifindex);head = &fib_info_devhashhash;hlist_add_head(&nexthop_nh-nh_hash, head); endfor_nexthops(fi)3.5具体创建过程上面讲过了路由表各个部分的创建，现在来看下它们是如何一起工作的， 在fib_table_insert()net/ipv4/fib_hash.c完成整个的路由表创建过程。下 面来看下 fib_table_insert()函数：从fn_zones中取出掩码长度为fc_ds

29、t_len的项，如果该项不存在，则创 建它(fn_zone的创建前面已经讲过)。fz = table-fn_zonescfg-fc_dst_len;if (!fz & !(fz = fn_new_zone(table, cfg-fc_dst_len)return -ENOBUFS;然后创建fib_info结构，(前面已经讲过) fi = fib_create_info(cfg);然后在掩码长度相同项里查找指定网络地址key(如145.222.33.0/24)，查 找的结果如图3-5所示.f = fib_find_node(fz, key);图3-5查找网络地址key如果不存在该网络地址项，则创

30、建相应的fib_node，并加入到链表fz_hash中。if (!f) (new_f = kmem_cache_zalloc(fn_hash_kmem, GFP_KERNEL);if (new_f = NULL)goto out;INIT_HLIST_NODE(&new_f-fn_hash);INIT_LIST_HEAD(&new_f-fn_alias);new_f-fn_key = key;f = new_f;fib_insert_node(fz, new_f);如果存在该网络地址项，则在fib_node的属性fn_alias中以tos和 fi-fib_priority作为键值查找。一个fi

31、b_node可以有多个fib_alias相对应， 这些fib_alias以链表形式存在，并按tos并从大到小的顺序排列。因此， fib_find_alias 查找到的是第一个 fib_alias-tos 不大于 tos 的 fib_alias 项。fa = fib_find_alias(&f-fn_alias, tos, fi-fib_priority);如果查找到的fa与与要插入的路由项完全相同，则按照设置的标置位进行 操作，NLM_F_REPLACE则替换掉旧的，NLM_F_APPEND添加在后面。设置要插入的fib_alias的属性，包括最重要的fib_alias-fa_info设置 为

32、fi。new_fa-fa_info = fi;new_fa-fa_tos = tos;new_fa-fa_type = cfg-fc_type;new_fa-fa_scope = cfg-fc_scope;new_fa-fa_state = 0;如果没有要插入路由的网络地址项fib_node，则之前已经创建了新的，现 在将它插入到路由表中fib_insert_node()；然后将new_fa链入到 fib_node-fn_alias 中。if (new_f)fib_insert_node(fz, new_f);list_add_tail(&new_fa-fa_list,(fa ? &fa-fa

33、_list : &f-fn_alias);最后，由于新插入的路由表项，会发出通告，告知所以加入 RTNLGRP_IPV4_ROUTE组的成员，这个功能可以在 linux中使用” ip route monitor”来测试。最终的路由表如图3-6所示。new_fa, cfg-fc_dst_len, tb-tb_id,rtmsg_fib(RTM_NEWROUTE, key, &cfg-fc_nlinfo, 0);Nist head-*图3-6路由表总体结构hlist head fa iiTifn一 fa info第四章Linux路由功能实现2.1数据包流程-ip_local_deliverLOCAL

34、_IN.Y1 ip_local_deliver finiship_build_and_send pktip_queue_xmitLOCAL_OUTip_push_pendingframesip_forwardFORWARDip_forward_finiship_outputpost_RoutinGip_rcvPRE_ROUTINGip_rcv_finiship_finish_output ip_finish_output2图4-1 Linux网络层的数据包函数调用流程如图4-1所示，ip_rcv是IPv4数据包的基本接收函数，由下层调用。这个 函数完成一系列的校验、协议处理等等，然后进入第一个

35、HOOK点，这是在本机 路由前的点。在ip_rcv_finish函数中，会调用ip_route_input函数来进行本机路由， 判断是发送给本机的，还是需要转发的，由此来知道下一处理函数是 ip_local_deliver，还是 ip_forward。至于 ip_route_input 是如何进行路由的， 将在下一节进行讲解。ip_local_deliver以上，是本机数据包流程，这与路由无关，这里不做赘 述。ip_forward进行一些路由的处理，比如设置网关、MTU，TTL减1等等。然 后进入ip_forward_finish，根据之前设置的skb-dst-output函数来确定去 处。这

36、个output也是在之前的路由过程中确定的，具体是单播、多播、还是广 播等等，视之前的路由和协议而定。2.2数据包路由过程之前说了 ip_rcv_finish函数中，调用ip_route_input函数来进行本机路 由。具体流程如图4-2所示。图4-2路由过程ip_route_input函数中，首先去路由缓存rt_ hash_table中查找，如果找 到则直接返回。如果没有找到，则调用ip_route_input_slow来查找路由表。ip_route_input_slow 函数中调用 fib_lookup 来查找。fib_lookup 有两种 定义，根据不同的功能编译开关。一种是只查找mai

37、n表和local表，这是低级 路由。另一种则会遍历rule表，先匹配应该查找哪一张路由表（可能是高级路 由配置的），然后再对该表进行查询。如果查询结果是本机的数据包，则会在ip_route_input_slow函数的后面 部分进行数据包路由信息的更改，最重要的是入口函数改成ip_local_deliver。 然后调用rt_intern_hash函数来更新路由缓存。如果结果是需要转发的，则调用ip_mkroute_input-_mkroute_input来 做进一步的处理（ip_mkroute_input中有一个分支，多路路由，这里不作介绍）。 也就是把查找到的路由信息加入路由缓存，并把路由结果

38、传递给数据包。2.3相关代码2.3.1 ip_rcv_finish 函数if (skb-dst = NULL) (int err = ip_route_input(skb, READ32_ALIGNED(iph-daddr), READ32_ALIGNED(iph-saddr), iph-tos, skb-dev);if (unlikely(err) (if (err = -EHOSTUNREACH)IP_INC_STATS_BH(dev_net(skb-dev),IPSTATS_MIB_INADDRERRORS);else if (err = -ENETUNREACH)IP_INC_STAT

39、S_BH(dev_net(skb-dev),IPSTATS_MIB_INNOROUTES);goto drop;2.3.2 ip_route_input 函数for (rth = rcu_dereference(rt_hash_tablehash.chain); rth;rth = rcu_dereference(rth-u.dst.rt_next) ( if (rth-fl.fl4_dst daddr) |(rth-fl.fl4_src saddr) |(rth-fl.iif iif) |rth-fl.oif |(rth-fl.fl4_tos tos) = 0 & rth-fl.mark =

40、 skb-mark & net_eq(dev_net(rth-u.dst.dev), net) &!rt_is_expired(rth) (dst_use(&rth-u.dst, jiffies);RT_CACHE_STAT_INC(in_hit);rcu_read_unlock();skb-rtable = rth;return 0;return ip_route_input_slow(skb, daddr, saddr, tos, dev);2.3.3 ip_route_input_slow 函数if (err = fib_lookup(net, &fl, &res) != 0) (if

41、(!IN_DEV_FORWARD(in_dev)goto e_hostunreach;goto no_route;if (res.type = RTN_LOCAL) (int result;result = fib_validate_source(saddr, daddr, tos, net-loopback_dev-ifindex, dev, &spec_dst, &itag);if (result u.dst.output= ip_rt_bug;rth-rt_genid = rt_genid(net);atomic_set(&rth-u.dst. _refcnt, 1);rth-u.dst

42、.flags= DST_HOST;if (IN_DEV_CONF_GET(in_dev, NOPOLICY) rth-u.dst.flags |= DST_NOPOLICY;rth-fl.fl4_dst = daddr;rth-rt_dst = daddr;rth-fl.fl4_tos = tos;rth-fl.mark = skb-mark;rth-fl.fl4_src = saddr;rth-rt_src = saddr;rth-rt_iif =rth-fl.iif = dev-ifindex;rth-u.dst.dev = net-loopback_dev;dev_hold(rth-u.

43、dst.dev);rth-idev = in_dev_get(rth-u.dst.dev);rth-rt_gateway = daddr;rth-rt_spec_dst= spec_dst;rth-u.dst.input= ip_local_deliver;rth-rt_flags = flags|RTCF_LOCAL;if (res.type = RTN_UNREACHABLE) (rth-u.dst.input= ip_error;rth-u.dst.error= -err;rth-rt_flags &= RTCF_LOCAL;rth-rt_type = res.type;hash = r

44、t_hash(daddr, saddr, fl.iif, rt_genid(net);err = rt_intern_hash(hash, rth, &skb-rtable);2.3.4 _mkroute_input 函数rth-u.dst.flags= DST_HOST;if (IN_DEV_CONF_GET(in_dev, NOPOLICY) rth-u.dst.flags |= DST_NOPOLICY;if (IN_DEV_CONF_GET(out_dev, NOXFRM) rth-u.dst.flags |= DST_NOXFRM;rth-fl.fl4dst= daddr;rth-rtdst =daddr;rth-fl.fl4tos=tos;rth-fl.mark= skb-mark;rth-fl.fl4src= saddr;rth-rtsrc =saddr;rth-rt_gatewayrth-rtiif =daddr;