LinuxIPv4路由功能的分析

IPv4 路由设计与实现相关知识路由设计与实现相关知识 文档编号 00 6201 100 当前版本 1 0 0 0 创建日期 2011 9 1 编写作者 ganjingwei 路由知识总结路由知识总结 前言 3 关于此文档 3 参考资料 3 第一章 路由的基本概念 4 1 1 路由的作用 4 1 2 路由的工作原理 4 第二章 数据结构 5 2 1 fib table 5 2 2 fn hash 5 2 3 fn zone 5 2 4 fib node 6 2 5 fib alias 6 2 6 fib info 7 2 7 fib nh 7 第三章 路由表的创建 9 3 1 创建路由表 9 3 2 掩码长度分类级 10 3 3 网络地址分类级 12 3 4 路由信息分类级 13 3 5 具体创建过程 16 第四章 Linux 路由功能实现 19 2 1 数据包流程 19 2 2 数据包路由过程 20 2 3 相关代码 22 2 3 1 ip rcv finish 函数 22 2 3 2 ip route input 函数 22 2 3 3 ip route input slow 函数 23 2 3 4 mkroute input 函数 25 2 3 5 fib lookup 函数 26 前言前言 关于此文档关于此文档 此文档是本人这段时间内学习 Linux 网络协议栈路由功能相关知识 总结 并且整理出来的文档 供大家参考 本文档描述 Linux 相关知识 各章节说明如下 1 前言 即此章节 2 路由理论知识 3 相关数据结构 4 路由表的创建 5 Linux 路由的实现及数据包流程 参考资料参考资料 网络资源 本文中的所有代码以 broadcom4 12L 01 为依据 内核代码为 2 6 第一章第一章 路由的基本概念路由的基本概念 1 1 路由的作用路由的作用 路由器工作在 ISO 层次结构中的三层 根据三层协议的各种信息 完成数 据包的选路和转发 最终达到目的地 1 2 路由的工作原理路由的工作原理 路由与网桥的区别 在于路由了解整个网络 而网桥只了解相连接的主机 或网络 因此路由在选路的过程中 更具有目的性 路由维持一张 多张 路由表来支持选路的功能 路由表与网桥表不同 路由表是人为配置的 这里说的人为配置 可能是用户通过接口进行配置 也 可以是应用层本身对内核进行路由配置 比如动态更新路由自主学习等 每个路由表中记录的信息有 源地址 网络 目的地址 网络 目的网 关 scope 距离 查询根据这些来匹配 匹配过程中 先匹配一个路由缓存 再匹配路由表 路由缓存是由内核维持的 而路由表是人为配置的 缓存根据 最近使用的表项来更新 目的是为了提高查询效率 和 CPU 的 cache 一样 在 内核中 路由表由 fib table hash 表示 路由缓存由 rt hash table 表示 第二章第二章 数据结构数据结构 2 1 fib table 这是一个路由表的最高级结构 struct fib table struct hlist node tb hlist u32tb id unsigned tb stamp inttb default int 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 struct fib table table void tb select default struct fib table table const struct flowi flp struct fib result res unsigned char tb data 0 2 2 fn hash 这是路由表一级查找 按掩码查找 的散列结构体 包含了散列表头和散 列数组 struct fn hash struct fn zone fn zones 33 struct fn zone fn zone list 2 3 fn zone 这是路由表一级查找 按掩码查找 的具体信息保存的结构体 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 mask define FZ MASK fz fz fz mask 2 4 fib node 这是路由表二级查找 网络地址查找 具体信息存放的结构体 其中 fn key 就是网络地址 通过 fn key 和掩码长度来计算散列定位 struct fib node struct hlist nodefn hash struct list headfn alias be32fn key struct fib alias fn embedded alias 2 5 fib alias 这个结构体包含了路由的具体信息的结构体 但是它不对其进行描述 而 是描述一些键值 用于标识和排序那些信息 真正的信息包含在 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 TRIE struct rcu headrcu endif 2 6 fib info 这个才是真正的路由信息结构 struct fib info struct hlist nodefib hash struct hlist nodefib lhash struct net fib net intfib treeref atomic tfib clntref intfib dead unsignedfib flags intfib protocol be32fib prefsrc u32fib priority u32fib metrics RTAX MAX define fib mtu fib metrics RTAX MTU 1 define fib window fib metrics RTAX WINDOW 1 define fib rtt fib metrics RTAX RTT 1 define fib advmss fib metrics RTAX ADVMSS 1 intfib nhs ifdef CONFIG IP ROUTE MULTIPATH intfib power endif struct fib nhfib nh 0 define fib devfib nh 0 nh dev 2 7 fib nh 这个结构被包含在 fib info 中 是路由下一条的信息 一般来说只有一 个 但是如果有多通路 也就是配置了 CONFIG IP ROUTE MULTIPATH 才会有 多个 struct fib nh struct net device nh dev struct hlist nodenh hash struct fib info nh parent unsignednh flags unsigned charnh scope ifdef CONFIG IP ROUTE MULTIPATH intnh weight intnh power endif ifdef CONFIG NET CLS ROUTE u32nh tclassid endif intnh oif be32nh gw 第三章第三章 路由表的创建路由表的创建 3 1 创建路由表创建路由表 默认路由表由内核创建的函数调用流程为 inet init ip init ip fib init fib net init ip fib net init net ipv4 fib frontend c 在这个函数中 首先为路由表分配空间 这里的每个表项 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 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 hlist add head rcu 最后生成的结构如图 3 1 LOCAL 表位于 fib table hash 0 MAIN 表位 于 fib table hash 1 两张表通过结构 tb hlist 链入链表 而 tb id 则标识 了功能 255 是 LOCAL 表 254 是 MAIN 表 图图 3 1 路由表内核内部结构路由表内核内部结构 路由表的查找效率是第一位的 因此内核在实现时使用了多级索引来进行 加速 第一级 fn zone 按不同掩码长度分类 如 5 和 24 第二级 fib node 按不同网络地址分类 如 124 44 33 0 24 第三级 fib info 按下一跳路由信息 当然 我们创建路由表也要按照这个顺序 3 2 掩码长度分类级掩码长度分类级 关于上一节说的 struct fn hash 它表示了不同子网掩码长度 hash 表 即 fn zone 对于 ipv4 从 0 32 共 33 个 而 fn hash 的实现则是 fib table 的最后一个参数 unsigned char tb data 0 注意这里 fn zone 还只是空指针 我们还只完成了路由表初始化的一部分 在启动阶段还会调用 inet rtm newroute fib table insert fn new zone fib hash c 来创建 fn zone 结构 前面已经讲过 fn zone 一共有 33 个 其中掩码长度为 0 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 实际是用于求余数的 当算出 hash 值 再 hash fz fz hash fz hash alloc fz fz divisor fz fz order z fz fz mask inet make mask z 从子网长度大于新添加 fz 的 fn zone 中挑选一个不为空的 fn zones i 将新创建 fz 设成 fn zones i next 然后将 fz 根据掩码长度添加到 fn zones 中相应位置 fn zone list 始终指向掩码长度最长的 fn zone for i z 1 ifn zones i break if i 32 fz fz next table fn zone list table fn zone list fz else fz fz next table fn zones i fz next table fn zones i fz next fz table fn zones z fz fn hash 包含 33 数组元素 每个元素存放一定掩码长度的 fn zone 其中 fn zone i 存储掩码长度为 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 ipv4 fib hash c 这里 f 是 fib node 可以理解为具有相同网络地址的路由项集合 根据 fn key 网络地址 和 fz 掩码长度 来计算 hash 值 决定将 f 插入 fz hash 的 哪个项 struct hlist head head hlist add head 如果 fib node 不存在 则会创建它 这里的 kmem cache zalloc 其实就 是内存分配 new f kmem cache zalloc fn hash kmem GFP KERNEL if new f NULL goto out INIT HLIST NODE INIT LIST HEAD new f fn key key f new f 3 4 路由信息分类级路由信息分类级 路由表最后一层是 fib info 具体的路由信息都存储在此 它由 fib create info 创建 首先为 fib info 分配空间 由于 fib info 的最后一个属性是 struct fib nh fib nh 0 因此大小是 fib info nhs fib nh 这里的 fib nh 代 表了下一跳 next hop 的信息 nhs 代表了下一跳的数目 一般情况下 nhs 1 除非配置了支持多路径 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 nexthops 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 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 链入链表中 这里要注意的是所有的 fib info 只要创建了的 都 会加入 fib info hash 中 如果路由项使用了优先地址属性 还会加入 fib info laddrhash 中 hlist add head if fi fib prefsrc struct hlist head head head hlist add head 无论 fib info 在路由表中位于哪个掩码 哪个网段结构下 都与 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 nexthops fi hash fib devindex hashfn nexthop nh nh dev ifindex head hlist add head endfor nexthops fi 3 5 具体创建过程具体创建过程 上面讲过了路由表各个部分的创建 现在来看下它们是如何一起工作的 在 fib table insert net ipv4 fib hash c 完成整个的路由表创建过程 下面来看下 fib table insert 函数 从 fn zones 中取出掩码长度为 fc dst len 的项 如果该项不存在 则创 建它 fn zone 的创建前面已经讲过 fz table fn zones cfg fc dst len if fz 然后创建 fib info 结构 前面已经讲过 fi fib create info cfg 然后在掩码长度相同项里查找指定网络地址 key 如 145 222 33 0 24 查找的结果如图 3 5 所示 f fib find node fz key 图图 3 5 查找网络地址查找网络地址 key 如果不存在该网络地址项 则创建相应的 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 INIT LIST HEAD new f fn key key f new f fib insert node fz new f 如果存在该网络地址项 则在 fib node 的属性 fn alias 中以 tos 和 fi fib priority 作为键值查找 一个 fib node 可以有多个 fib alias 相对应 这些 fib alias 以链表形式存在 并按 tos 并从大到小的顺序排列 因此 fib find alias 查找到的是第一个 fib alias tos 不大于 tos 的 fib alias 项 fa fib find alias 如果查找到的 fa 与与要插入的路由项完全相同 则按照设置的标置位进 行操作 NLM F REPLACE 则替换掉旧的 NLM F APPEND 添加在后面 设置要插入的 fib alias 的属性 包括最重要的 fib alias fa info 设 置为 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 最后 由于新插入的路由表项 会发出通告 告知所以加入 RTNLGRP IPV4 ROUTE 组的成员 这个功能可以在 linux 中使用 ip route monitor 来测试 最终的路由表如图 3 6 所示 rtmsg fib RTM NEWROUTE key new fa cfg fc dst len tb tb id 图图 3 6 路由表总体结构路由表总体结构 第四章第四章 Linux 路由功能实现路由功能实现 2 1 数据包流程数据包流程 ip rcvPRE ROUTING ip rcv finish ip local deliverip forward LOCAL INFORWARD ip local deliver finish ip forward finis h ip outputLOCAL OUT ip build and se nd pkt ip queue xmit ip push pending frames POST ROUTIN G ip finish output ip finish output 2 图图 4 1 Linux 网络层的数据包函数调用流程网络层的数据包函数调用流程 如图 4 1 所示 ip rcv 是 IPv4 数据包的基本接收函数 由下层调用 这 个函数完成一系列的校验 协议处理等等 然后进入第一个 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 函数来确定 去处 这个 output 也是在之前的路由过程中确定的 具体是单播 多播 还是 广播等等 视之前的路由和协议而定 2 2 数据包路由过程数据包路由过程 之前说了 ip rcv finish 函数中 调用 ip route input 函数来进行本机 路由 具体流程如图 4 2 所示 ip route input ip route input slow fib lookup ip mkroute input 本机 mkroute input forward Local return ip fcv finish 图图 4 2 路由过程路由过程 ip route input 函数中 首先去路由缓存 rt hash table 中查找 如果 找到则直接返回 如果没有找到 则调用 ip route input slow 来查找路由表 ip route input slow 函数中调用 fib lookup 来查找 fib lookup 有两 种定义 根据不同的功能编译开关 一种是只查找 main 表和 local 表 这是低 级路由 另一种则会遍历 rule 表 先匹配应该查找哪一张路由表 可能是高级 路由配置的 然后再对该表进行查询 如果查询结果是本机的数据包 则会在 ip route input slow 函数的后面 部分进行数据包路由信息的更改 最重要的是入口函数改成 ip local deliver 然后调用 rt intern hash 函数来更新路由缓存 如果结果是需要转发的 则调用 ip mkroute input mkroute input 来 做进一步的处理 ip mkroute input 中有一个分支 多路路由 这里不作介绍 也就是把查找到的路由信息加入路由缓存 并把路由结果传递给数据包 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 STATS BH dev net skb dev IPSTATS MIB INNOROUTES goto drop 2 3 2 ip route input 函数函数 for rth rcu dereference rt hash table hash 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 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 goto no route if res type RTN LOCAL int result result fib validate source saddr daddr tos net loopback dev ifindex dev if result u dst output ip rt bug rth rt genid rt genid net atomic set rth u dst 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 f