关于ICMP Redirect路由的一个不是bug的bug

注册 Vultr VPS 送你10美金 免费玩4个月

在新公司碰到的第一个网络问题竟然是关于重定向路由的,这个不常被关注的问题竟然花费了我整整一下午时间来整理,本文介绍Linux协议栈是如何对待重定向路由的。

路由项的生成方式

任何具备网络功能的设备在内部都有有一张路由表,该表指示数据包如何从该设备发出以及下一站发送到哪里。路由表由一项一项组成,每一项称为一条路由项,这些路由项有以下的生成方式:

1.自动发现的路由项

网卡启动并且配置上IP地址的时候,会自动生成与该IP地址以及前缀相匹配的链路层路由,由于是链路可达的,所有不需要nexthop,所有的元素都是可以马上确定的。因此此过程无需人工干预或者任何路由协议的干预。
       比如说,eth0上配置IP地址为192.168.41.150/24,那么根据这个IP地址,内核协议栈会算出该IP地址所在的网段为192.168.41.0/24,很显然,如果按照IP规范,与eth0直连的网卡所持有的IP地址也是192.168.41.0/24这个网段的,所有发往该网段的数据包无需nexthop可以链路层直达,对该网段的所有访问都是“直接的”,因此无需任何外部干预,即可生成一条路由:
192.168.41.0/24 dev eth0
表示所有访问192.168.41.0/24,均通过eth0直接发出,映射到具体的访问逻辑,那就是直接ARP目标地址即可。
       这种路由项在网卡的IP地址删除或者改变的时候被自动删除。

2.静态配置的路由项

如果目标地址不属于本机任意的网卡持有IP地址所在网段,天知道该怎么走,此时必然需要一种外部干预,一般分为两种,人工干预和协议干预。
       人工干预是指,通过系统集成的命令,手工配置一条路由,告诉协议栈通往该目标地址或者目标网段的下一跳是什么,以便可以将数据包往前推进一步,是为IP逐跳转发,下一跳IP地址所在的主机必须与本机直连,然而并不要求下一跳的IP地址必须与本机的任意一块网卡处在同一个IP段(由于存在force onlink)。因此如果本机唯一网卡eth0的IP为192.168.41.150/24,需要从本机访问1.2.3.0/24,就需要指定一个与192.168.41.150/24在同一网段的nexthop或者不在同一网段但是链路层直连的nexthop:
1.2.3.0/24 nexthop 192.168.41.254 dev eth0  –表示同一网段的nexthop
1.2.3.0/24 dev eth0 force onlink  –表示不在同一网段,但可以确保直连的nexthop
       这种路由项由管理员手工删除或者网卡对应nexthop同网段IP地址删除/改变时自动删除,另外对应网卡down掉也会删除路由项。

3.动态路由协议生成的路由项

除了手工通过命令配置,还可以通过动态路由协议生成路由项,所谓的路由协议就是通过一种约定俗成的协议给整个网络注入智能,使得其可以自动发现网络拓扑,这种方式比静态手工配置要来的更灵活,毕竟管理员的大脑不是专职记忆网络拓扑的,他是一个人,除了工作还要处理各种社会,家庭事务,即便是个工作狂,也不可能只是记忆并配置网络,所以还是把这件事交给专职执行者吧,这个执行者就是动态路由协议,在本文不深入解释动态路由协议,避免喧宾夺主。
       动态路由协议运行到收敛状态后,所有的网络设备(路由器等)均对网络拓扑达成了一致,也就是说,每一个设备在内存中均生成了一张地图,每一个设备均知道到达任意其它的目标该怎么走,下一跳是谁,它们均很清楚,生成的路由项与手工生成的路由项无异,不再赘述。
       动态路由项的删除机制与静态路由项类似,协议会删除路由项,手工也可以删除,底层的事件也会自动删除路由项,不同的是,路由项删除或者发生了底层事件,比如网卡热插拔,会触发路由协议重新计算收敛。

4.重定向路由项

万事总有例外,这是铁律。在日常生活中,我们在办事时经常碰到踢皮球的情形,有人告诉你办这件事要找A,你找到了A,A告诉你要你直接去找B,因为她自己也要去找B…在路由转发的情况下,情况更简单些,如果本机IP地址为S,配置的下一跳网关为A,而A的下一跳网关为B,同时S,A,B三者均在同一个网段且链路层直连,最简单的情况,可以认为它们接在同一个交换机上,此处的逻辑很简单:既然S可以直达B,为何要麻烦A,然后再原路返回到达B呢?
       这就是重定向路由存在的理由,A为重定向路由的发出者,S为重定向路由的接收和处理者,S收到这个A发出的重定向路由后,就会在“路由表”(为何带引号?这正是本文的主题)中插入一条新的路由项,该路由项一般是一个针对特定IP而不是网段的重定向,比如:
S的IP:192.168.41.150/24
A的IP:192.168.41.253/24  GW192.168.41.254
B的IP:192.168.41.254/24
系统中一条既有的路由:2.2.2.0/24 nexthop 192.168.41.253
S发往2.2.2.100的数据包查找路由表首先到达A,随后A返回给S一个重定向:请直接发给B。
S收到重定向后,会生成下面的重定向路由:
2.2.2.100 nexthop 192.168.41.254 redirect
那么这条路由是直接插入到系统的路由表中吗?如果是,什么时候删除呢?毕竟前三种路由插入的同时都有删除机制,重定向路由到底什么时候删除呢?到底什么时候删除呢?到底什么时候删除呢?围绕着这个重定向路由如何删除的问题,我有一些总结如下文。

Linux的路由表

什么标准的路由表布局,路由项格式,查询算法之类的都是浮云!只要可以在数据包转发的时候迅速定位到nexthop,就是成功的!业内比较常见的做法比如基于路由表生成一张转发表,转发表内容可以注入到硬件实现高速硬件转发,也可以生成一张小得多(只是希望,事实不一定如此!)但是查询更加高效的cache表。像Cisco的高大上设备一般都有自己的线卡,路由表和转发表完全分离,转发表全硬实现,比如CEF技术。而对于Linux这类布局一个的协议栈实现而言,要更灵活一些,正是由于这种灵活,重定向路由保存的位置也一直在改变,对基础设施的更改难免会引入一些问题(比如我在2010年发现的那个Linux nat模块对TSO的bug…)。

1.以2.6.32为例

由于内核一直在变化,包括微小的变化以及大步跨越,我也不可能搜遍每一个细节,只能针对我曾经用过的内核做粗粒度的采样。在2.6.32版本以及之前的内核中,协议栈维护了一个route cache,你可以将其看作是那种“小得多但查询更有效率”的cache表,route cache中的内容就是内核标准路由表查询结果的cache,标准路由表在编译内核的时候有两种选择,分别是HASH表和Trie表,然而不管哪种表,理论和常识都让人认为一种一维的hash表cache要比内嵌“最长前缀匹配”的HASH/Trie表效率更高,这就是route cache存在的理由。
       数据包要发送的时候,首先查找route cache,如果命中则不必去查标准路由表,如果缺失则继续查找理论上效率更低的HASH表或者Trie表,事实上,和任何cache机制一样,这是一种赌博权衡,效率是否提升取决于cache的布局,后面我们会看到,和CPU cache不同的是,IP路由对于TCP流而言,具备时间局部性可用,然而没有空间局部性可用,相反,这一点可能会造成route cache攻击。
       在这个版本的内核中,重定向路由就保存在route cache中,这个地方是非常合理的一个选择,这是因为route cache有手工flush和超时过期两种删除机制,即便持续的重定向流量造成重定向的route cache永远不过期,还是可以手工flush的。
       但是在这个版本的内核中,如果内核禁用了route cache,比如你设置了net.ipv4.rt_cache_rebuild_count为-1,那么会造成重定向路由项永不可用,你持续发包,nexthop接收方持续拒收并发重定向,然而你禁用了route cache,并不接收这个重定向路由,目前没有机制禁止这种捣乱行为。但这问题不大,管理员会发现这种行为并及时纠正(不要什么事情都指望协议可以自动完成,那太复杂了!),你买了一件¥18000的西装给你的经理,还是货到付款,并且没有写发件人,受苦的快递员和商家,ICMP何尝不是总是做这个事儿啊。

2.以3.0.1为例

在这个版本中,将重定向路由的处理换了个地方,也许此时已经发现了route cache终将下课,提前撤侨的吧,赶紧把这个重定向路由从route cache转移到了inet_peer。
       首先简单解释一下什么是inet_peer。inet_peer是一个端到端的概念,不同于IP路由的逐跳转发,inet_peer直接记录了与之通信的对端,比如你在公司内部与美国的朋友聊QQ,peer指的是美国朋友,身在美国,而逐跳的nexthop则可能是你公司的出口路由器地址甚至是你部门的VLAN的出口网关地址。那么inet_peer中可以保存什么呢?各个内核版本中inet_peer保存的内容几乎在变化,主要看端到端的语义,可以说,只要是端到端有意义的,都可以保存在inet_peer中,典型的就是TCP信息(与时间戳有关的,inet_peer代表了对端机器上所有的到本机的TCP连接!),那么重定向路由保存在这里当然也比较合理了,它表示了“到达对端的下一站是哪里”这种信息。
       重定向路由换了归宿搬了家,也就不会再受到禁用route cache的影响了。有问题吗?貌似没有。因为inet_peer也拥有自己的删除机制,就是超时老化机制,这是唯一的删除机制。之所以不提供手工flush机制是因为类似TCP这样的“有连接有状态”协议用到了inet_peer,直接暴力删除会影响到连接状态。难道唯一的超时老化机制不够吗?
       我个人站在自圆其说的角度考虑是够了,只要有一种机制可以使其删除就够了!现在的问题是如何使inet_peer过期,很简单,只要持续不用到它就会过期。但是问题是如果有流量持续查找路由,持续在get_peer操作中查找到它,由于IP路由是没有状态的,所以只要有这种情况发生,inet_peer就永远都不会过期,于是问题转化成要想使inet_peer过期,比如阻滞到达peer的流量(仅限于本地始发流量,非转发流量!)。开始的时候我想用iptables DROP阻滞掉到达peer的OUTPUT流量,然而由于OUTPUT chain call位于IP路由之后进行,就只好作罢!于是只能手工在应用层停止所有的到达peer的服务!

       到此为止,可能有点乱,我总结一下3.0.1版本的路由查找过程。

R1-route cache
R2-标准路由表
R3-inet_peer保存的重定向路由

R1=查找route cache
if R1未命中
    R2=查找路由表
    if R2未命中
        丢弃
    else
        R3=查找inet_peer
        if R3未命中
            使用R2
        else
            使用R3中保存的重定向路由!
else

    使用R1

这下一目了然了!其中R3由且仅有唯一的过期删除机制,没有flush机制。那么为了如果想删除inet_peer,只好首先阻滞掉到达inet_peer的所有流量,然后通过sysctl设置inet_peer的超时参数为最短,手工flush掉route cache,等待超时删除inet_peer之后,放行阻滞的流量,方可使用标准路由表的路由。这个过程太复杂且让不熟悉这块内核实现的人不知其所以然,以至于被作为一个bug。
       社区的一个patch解决了这个问题。事实上,人们希望,在调用ip route flush cache的时候,把inet_peer保存的重定向nexthop设置为不可用即可。于是该patch新增了两个单调递增的计数器,一个是全局的,一个是inet_peer的字段,二者必须一致的时候,inet_peer保存的重定向nexthop才可用,于是逻辑变成了下面的样子:

R1-route cache

R2-标准路由表
R3-inet_peer保存的重定向路由

R3.genid-inet_peer的ID字段
G_genid-全局ID字段

FLUSH CACHE:
G_genid++

SET REDIRECT ROUTE:
R3.gw = ICMP Redirect中的nexthop
R3.genid = G_genid

LOOKUP:
R1=查找route cache
if R1未命中
    R2=查找路由表
    if R2未命中
        丢弃
    else
        R3=查找inet_peer
        if R3未命中
            使用R2
        else if R3.genid不等于G_genid
            使用R2
        else
            使用R3中保存的重定向路由R3.gw!
else

    使用R1

这样也就完美解决了问题,调用ip route flush cache的同时也就禁用了之前所有的重定向路由。

3.kernel 3.17以及以后

这个版本中已经没有了route cache,其实在这个版本之前很早route cache就下课了,由于route cache项为严格的IP地址二元组且IP路由行为没有空间局部性,如果攻击者伪造源IP地址或者目标IP地址,就可能使得route cache表变得畸形,即便限制总的hash表长度,也可能会导致route cache频繁缺失且持续rebuild,造成一种“不那么严重”的Dos,即便不是攻击流量,如果IP地址规划得不好,也会导致route cache hash表畸形,因此route cache最终还是下课了。其实,这种软件cache的缺失带来的副作用非常大,因为软件cache和正常的HASH/Trie查询使用的都是同样的CPU,它们之间的资源分配关系是等比例的,相反,硬件cache的缺失带来的开销却可以保持在一个恒定的范围,因为硬件cache和慢速查询使用的资源不同,硬件cache一般都有自己的硬件逻辑,速度要比CPU查询高几个数量级。
       现在言归正传,此时重定向路由保存在哪里呢?是继续在inet_peer中吗?事实上完全可以,但是它还是搬到了另外一个地方,此结构体为fib_nh_exception。重定向路由项的持续搬家让我想起了我自己,不断地变换地点,哈尔滨,长春,郑州,上海,深圳…但是每一次搬家都有一些看似很必须事实上都是借口的理由。

       将重定向路由从inet_peer搬家到fib_nh_exception之后,在执行逻辑上几乎没有任何变化:

R2-标准路由表
R3-fib_nh_exception保存的重定向路由

R3.genid-inet_peer的ID字段
nsG_genid-netnamesapce内全局ID字段

FLUSH CACHE:
nsG_genid++

SET REDIRECT ROUTE:
R3.gw = ICMP Redirect中的nexthop
R3.genid = G_genid

LOOKUP:
R2=查找路由表
if R2未命中
    丢弃
else
    R3=查找fib_nh_exception
    if R3未命中
        使用R2
    else if R3.genid不等于nsG_genid
        使用R2
    else

        使用R3中保存的重定向路由R3.gw!

可以看到就是将inet_peer换成了fib_nh_exception之外加了netnamespace的支持。
       在这个搬家完成以后,操作几乎没有任何改变,重定向路由依然和3.0版本内核打上redirect rt patch一样,在执行flush cache的时候,会递增本命名空间的genid,这样一来即便是R3命中,由于其genid已经相异与nsG_genid,故而依然不能使用。

合理性问题

内核3.0版本没有考虑flush的问题,因此无法删除重定向路由,故而只能靠inet_peer超时删除,打上patch之后,引入了genid就可以在flush cache的同时删除重定向路由项了,后来route cache下课之后,重定向路由搬家到了fib_nh_exception,从命名可以看出,重定向路由属于“异常”情况,属于被遗弃的孤儿,后来的版本中,几乎只能手工flush掉重定向路由。在此有个形而上的问题,这种重定向的路由到底应该由谁来删除,最好的回答看起来应该是谁添加的谁删除,但是,但是虽然是系统添加的这种路由,其根源还是管理员或者路由协议的配置失误,动态路由协议导致重定向路由的可能性非常小几乎为0,因为重定向路由是作用于主机的,也就是本地始发数据包的,因此责任就全部推给了静态路由的配置者,即网络管理员或者系统管理员。
       目前我比较倾向于仅仅保留手工删除重定向路由的方式,不能支持超时删除重定向路由的方式。这样保留单一的删除入口会给运维和排错带来比较大的便利。至于说Linux 3.0版本内核的重定向路由无法通过手工flush的方式将其删除是不是一个bug,如果站在我的立场上,确实是一个bug,但是毕竟它还是可以通过阻滞流量-过期删除的方式将重定向路由删除,因此也不算个bug。关键的问题在于,发生了问题,只要能解决就是成功,其它的都是浮云,留给哲学系的学究们去讨论吧….

注册 Vultr VPS 送你10美金 免费玩4个月