深入浅出DPDK学习笔记（6）———报文转发

ゞ浴缸里的玫瑰 2022-12-18 15:49 591阅读 0赞

### 报文转发 ###

*  网络处理模块划分
 *  转发框架介绍
 *   *  pipeline模型
     *  run to completion模型
     *  DPDK run to completion模型
     *  DPDK pipeline模型
 *  转发算法
 *   *  精确匹配算法
     *   *  分离链表(Separate chaining)
         *  开放地址(Open addressing)
     *  最长前缀匹配算法
     *  ACL算法
     *  报文分发

# 网络处理模块划分 #

网络报文的处理和转发主要分为硬件处理部分与软件处理部分,以下模块构成:  
·Packet input:报文输入。  
·Pre-processing:对报文进行比较粗粒度的处理。  
·Input classification:对报文进行较细粒度的分流。  
·Ingress queuing:提供基于描述符的队列FIFO。  
·Delivery/Scheduling:根据队列优先级和CPU状态进行调度。  
·Accelerator:提供加解密和压缩/解压缩等硬件功能。  
·Egress queueing:在出口上根据QOS等级进行调度。  
·Post processing:后期报文处理释放缓存。  
·Packet output:从硬件上发送出去。  
如图5-1所示,我们可以看到在浅色和阴影对应的模块都是和硬件相关的,因此要提升这部分性能的最佳选择就是尽量多地去选择网卡上或网络设备芯片上所提供的一些和网络特定功能相关的卸载的特性,而在深色软件部分可以通过提高算法的效率和结合CPU相关的并行指令来提升网络性能。了解了网络处理模块的基本组成部分后,我们再来看不同的转发框架下如何让这些模块协同工作完成网络包处理。  
![网络处理模块细分][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center]

# 转发框架介绍 #

传统的Network Processor(专用网络处理器)转发的模型可以分 为 run to completion ( 运 行 至 终 结 , 简 称 RTC ) 模 型 和pipeline(流水线)模型。

## pipeline模型 ##

从名字上,就可以看出pipeline模型借鉴于工业上的流水线模型,将一个功能(大于模块级的功能)分解成多个独立的阶段,不同阶段间通过队列传递产品。这样,对于一些CPU密集和I/O密集的应用,通过pipeline模型,我们可以把CPU密集的操作放在一个微处理引擎上执行,将I/O密集的操作放在另外一个微处理引擎上执行。通过过滤器可以为不同的操作分配不同的线程,通过连接两者的队列匹配两者的处理速度,从而达到最好的并发效率。

## run to completion模型 ##

run to completion(运行至终结)模型是主要针对DPDK一般程序的运行方法,一个程序中一般会分为几个不同的逻辑功能,但是这几个逻辑功能会在一个CPU的核上运行,我们可以进行水平扩展使得在SMP的系统中多个核上执行一样逻辑的程序,从而提高单位时间内事务处理的量。但是由于每个核上的处理能力其实都是一样的,并没有针对某个逻辑功能进行优化,因此在这个层面上与pipeline模型比较,run to completion模型是不高效的。  
![DPDK转发模型][DPDK]  
从图5-4a的run to completion的模型中,我们可以清楚地看出,每个IA的物理核都负责处理整个报文的生命周期从RX到TX。  
在图5-4b的pipeline模型中可以看出,报文的处理被划分成不同的逻辑功能单元A、B、C,一个报文需分别经历A、B、C三个阶段,这三个阶段的功能单元可以不止一个并且可以分布在不同的物理核上,不同的功能单元可以分布在相同的核上(也可以分布在不同的核上)。以下我们来看DPDK中这两种方法的优缺点。  
![DPDK RTC与pipeline的比较][DPDK RTC_pipeline]

## DPDK run to completion模型 ##

普通的Linux网络驱动中的扩展方法如下:把不同的收发包队列对应的中断转发到指定核的local APIC(本地中断控制器)上,并且使得每个核响应一个中断,从而处理此中断对应的队列集合中的相关报文。而在DPDK的轮询模式中主要通过一些DPDK中eal中的参数-c、-l、-l core s来设置哪些核可以被DPDK使用,最后再把处理对应收发队列的线程绑定到对应的核上。每个报文的整个生命周期都只可能在其中一个线程中出现。和普通网络处理器的run to completion的模式 相 比 , 基 于 IA 平 台 的 通 用 CPU 也 有 不 少 的 计 算 资 源 , 比 如 一 个socket上面可以有独立运行的16运算单元(核),每个核上面可以有两个逻辑运算单元(thread)共享物理的运算单元。而多个socket可以通过QPI总线连接在一起,这样使得每一个运算单元都可以独立地处理一个报文并且通用处理器上的编程更加简单高效,在快速开发网络功能的同时,利用硬件AES-NI、SHA-NI等特殊指令可以加速网络相关加解密和认证功能。运行到终结功能虽然有许多优势,但是针对单个报文的处理始终集中在一个逻辑单元上,无法利用其他运算单元,并且逻辑的耦合性太强,而流水线模型正好解决了以上的问题。下面我们来看DPDK的流水线模型,DPDK中称为Packet Framework。

## DPDK pipeline模型 ##

pipeline的主要思想就是不同的工作交给不同的模块,而每一个模块都是一个处理引擎,每个处理引擎都只单独处理特定的事务,每个处理引擎都有输入和输出,通过这些输入和输出将不同的处理引擎连接起来,完成复杂的网络功能,DPDK pipeline的多处理引擎实例和每个处理引擎中的组成框图可见图5-5中两个实例的图片:zoom out(多核应用框架)和zoom in(单个流水线模块)。  
![DPDK pipeline][]  
Zoom out的实例中包含了五个DPDK pipeline处理模块,每个pipeline作为一个特定功能的包处理模块。一个报文从进入到发送,会有两个不同的路径,上面的路径有三个模块(解析、分类、发送),下面的路径有四个模块(解析、查表、修改、发送)。Zoom in的图示中代表在查表的pipeline中有两张查找表,报文根据不同的条件可以通过一级表或两级表的查询从不同的端口发送出去。  
此外,从图5-5中的pipeline level我们知道,DPDK的pipeline是由三大部分组成的,逻辑端口(port)、查找表(table)和处理逻辑(action)。DPDK的pipeline模型中把网络端口作为每个处理模块的输入,所有的报文输入都通过这个端口来进行报文的输入。查找表是每个处理模块中重要的处理逻辑核心,不同的查找表就提供了不同的处理方法。而转发逻辑指明了报文的流向和处理,而这三大部分中的主要类型可参见表5-3。  
![DPDK Port、Table、Action支持的类型][DPDK Port_Table_Action]  
用户可以根据以上三大类构建数据自己的pipeline,然后把每个pipeline都绑定在指定的核上从而使得我们能快速搭建属于我们自己的packet framework。  
现在DPDK支持的pipeline有以下几种:  
·Packet I/O  
·Flow classification  
·Firewall  
·Routing  
·Metering  
·Traffic Mgmt  
DPDK以上的几个pipeline都是DPDK在packet framework中直接提供给用户的,用户可以通过简单的配置文件去利用这些现成的pipeline,加快开发速度。  
以Routing pipeline为例可以有以下构建形式:  
关于具体如何使用DPDK的packet framework去快速搭建属于自己的高性能网络应用,可以参考DPDK源码中的sample。  
![DPDK Routing Pipeline][]

# 转发算法 #

除了良好的转发框架之外,转发中很重要的一部分内容就是对于报文字段的匹配和识别,在DPDK中主要用到了精确匹配(Exact Match)算法和最长前缀匹配(Longest Prefix Matching,LPM)算法来进行报文的匹配从而获得相应的信息。

## 精确匹配算法 ##

精确匹配算法的主要思想就是利用哈希算法对所要匹配的值进行哈希,从而加快查找速度。决定哈希性能的主要参数是负载参数  
 L = n / k L=n/k L=n/k  
其中:n=总的数据条目,k=总的哈希桶的条目。  
当负载参数L值在某个合理的数值区间内时哈希算法效率会比较高。L值越大,发生冲突的几率就越大。哈希中冲突解决的办法主要有以下两种:

### 分离链表(Separate chaining) ###

所有发生冲突的项通过链式相连,在查找元素时需要遍历某个哈希桶下面对应的链表中的元素,优点是不额外占用哈希桶,缺点是速度较慢。从图5-7中可以看到,John Smith和Sandra Dee做完哈希以后都落入152这个哈希桶,这两个条目通过链表相连,查找Sandra Dee这个条目时,先命中152对应的哈希桶,然后通过分别匹配152下面链表中的两个元素找到Sandra Dee这个条目。  
![分离链表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center 1]

### 开放地址(Open addressing) ###

所有发生冲突的项自动往当前所对应可使用的哈希桶的下一个哈希桶进行填充,不需要链表操作,但有时会加剧冲突的发生。如图5-8所示,还查看John Smith和Sandra Dee这两个条目,都哈希到152这个条目,John Smith先放入152中,当Sandra Dee再次需要加入152中时就自动延后到153这个条目。  
![开放地址][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center 2]  
介绍了哈希相关的一些基础后,我们来看下DPDK的具体实现。DPDK中主要支持CRC32和J hash,这里主要介绍CRC相关的内容和优化。  
其实,精确匹配主要需要解决两个问题:进行数据的签名(哈希),解决哈希的冲突问题。CRC32和J hash是两个数字签名的不同算法。我们先来看下CRC。  
CRC检验原理实际上就是在一个p位二进制数据序列之后附加一个r位二进制检验码(序列),从而构成一个总长为n=p+r位的二进制序列;附加在数据序列之后的这个检验码与数据序列的内容之间存在着某种特定的关系。如果因干扰等原因使数据序列中的某一位或某些位发生错误,这种特定关系就会被破坏。因此,通过检查这一关系,就可以实现对数据正确性的检验。  
CRC中的两个主要概念如下:

1.  多项式模2运行:  
    实际上是按位异或(Exclusive OR)运算,即相同为0,相异为1 ,也就是不考虑进位、借位的二进制加减运算。如:  
    10011011+11001010=01010001。
2.  生成多项式:  
    当进行CRC检验时,发送方与接收方需要事先约定一个除数,即生成多项式,一般记作G(x)。生成多项式的最高位与最低位必须是1。常用的CRC码的生成多项式有:  
    CRC8=X8+X5+X4+1  
    CRC-CCITT=X16+X12+X5+1  
    CRC16=X16+X15+X5+1  
    CRC12=X12+X11+X3+X2+1  
    CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1  
    每一个生成多项式都可以与一个代码相对应,如CRC8对应代码100110001。  
    计算示例:  
    设需要发送的信息为M=1010001101,产生多项式对应的代码为P=110101,R=5。在M后加5个0,然后对P做模2除法运算,得余数 r ( x ) 对 应 的 代 码 : 01110 。 故 实 际 需 要 发 送 的 数 据 是101000110101110,见图5-9。  
    ![CRC计算示例][CRC]  
    在CRC32的算法上DPDK做了以下的优化:  
    首先,将数据流按照8字节(优先处理)和4字节为单位进行处理,以8字节为例:  
    方法一:当支持CRC32\_SSE42\_x64时,可以直接使用IA的硬件指令来一次处理:指令8crc32q。  
    方法二:当支持CRC32\_SSE42时,可以直接使用IA的硬件指令来一次处理:指令crc32l。  
    方法三:当不允许或不能使用硬件相关指令进行加速操作时,可以直接使用查表的方法进行,利用空间换时间。  
    具体的哈希性能,DPDK有相关的单元测试,有兴趣的读者可以参考DPDK的源代码。  
    在处理哈希的冲突时用了如下的定义:

struct rte_ 哈希 _signatures signatures[RTE_ 哈希 _ 哈希桶 _ENTRIES];
    /* Includes dummy key index that always contains index 0 */
    uint32_t key_idx[RTE_ 哈希 _ 哈希桶 _ENTRIES + 1];
    uint8_t flag[RTE_ 哈希 _ 哈希桶 _ENTRIES];
    } __rte_cache_aligned;

在rte的一个哈希桶中将会有RTE\_哈希\_哈希桶\_ENTRIES个entry来解决冲突问题,可以说融合了分离链表和开放地址方法的优点。  
在 处 理 哈 希 、 找 到 对 应 的 数 据 时 , DPDK 提 供 了 rte\_ 哈 希\_lookup\_multi。这个函数利用了multi-buffer的方式降低了指令之间的依赖,增强了并行性,加快了哈希处理速度。

## 最长前缀匹配算法 ##

最长前缀匹配(Longest Prefix Matching,LPM)算法是指在IP协议中被路由器用于在路由表中进行选择的一个算法。  
因为路由表中的每个表项都指定了一个网络,所以一个目的地址可能与多个表项匹配。最明确的一个表项——即子网掩码最长的一个——就叫做最长前缀匹配。之所以这样称呼它,是因为这个表项也是路由表中与目的地址的高位匹配得最多的表项。  
例如,考虑下面这个IPv4的路由表(这里用CIDR来表示):  
192.168.20.16/28  
192.168.0.0/16  
DPDK中LPM的具体实现综合考虑了空间和时间,见图5-10。  
![DPDK LPM框图][DPDK LPM]  
前缀的24位共有2^24条条目,每条对应每个24位前缀,每个条目关联到最后的8位后缀上,最后的256个条目可以按需进行分配,所以说空间和时间上都可以兼顾。  
当前DPDK使用的LPM算法就利用内存的消耗来换取LPM查找的性能提升。当查找表条目的前缀长度小于24位时,只需要一次访存就能找到下一条,根据概率统计,这是占较大概率的,当前缀大于24位时,则需要两次访存,但是这种情况是小概率事件。  
LPM主要结构体为:一张有2^24条目的表,多个有 2^8条目的。第一级表叫做tbl24,第二级表叫做tbl8。  
·tbl24中条目的字段有:

struct rte_lpm_tbl24_entry { 
    /* Stores Next hop or group index (i.e. gindex)into tbl8. */
            union { 
                    uint8_t next_hop;
                    uint8_t tbl8_gindex;
            };
    /* Using single uint8_t to store 3 values. */
            uint8_t valid :1; /**< Validation flag. */
            uint8_t ext_entry :1; /**< External entry. */
            uint8_t depth :6; /**< Rule depth. */
    };

·tbl8中每条entry的字段有:

struct rte_lpm_tbl8_entry { 
            uint8_t next_hop; /**< next hop. */
    /* Using single uint8_t to store 3 values. */
            uint8_t valid :1; /**< Validation flag. */
            uint8_t valid_group :1; /**< Group validation flag. */
            uint8_t depth :6; /**< Rule depth. */
    };

用IP地址的前24位进行查找时,先看tbl24中的entry,当valid字段有效而ext\_entry为0时,直接命中,查看next\_hop知道下一跳。当 valid 为 1 而 ext\_entry 为 1 时 , 查 看 next\_hop 字 段 知 道 tbl8 的index,此时根据IP中的后8位确定tbl8中具体entry的下标,然后根据rte\_lpm\_tbl8\_entry中的next\_hop找下一跳地址。  
同样,关于具体的LPM性能,DPDK也有相关的单元测试,有兴趣的读者可以参考DPDK的源代码。

## ACL算法 ##

ACL库利用N元组的匹配规则去进行类型匹配,提供以下基本操作:  
·创建AC(access domain)的上下文。  
·加规则到AC的上下文中。  
·对于所有规则创建相关的结构体。  
·进行入方向报文分类。  
·销毁AC相关的资源。  
现在的DPDK实现允许用户在每个AC的上下文中定义自己的规则,AC规则中的字段用以下方式结构体进行表示:

struct rte_acl_field_def { 
            uint8_t type; /**< type - RTE_ACL_FIELD_TYPE_*. */
            uint8_t size; /**< size of field 1,2,4, or 8. */
            uint8_t field_index; /**< index of field inside the rule. */
            uint8_t input_index; /**< 0-N input index. */
            uint32_t offset; /**< offset to start of field. */
    };

如果要定义一个ipv4的5元组的过滤规则,可以用以下方式:

struct rte_acl_field_def ipv4_defs[NUM_FIELDS_IPV4] = { 
            { 
    .                type = RTE_ACL_FIELD_TYPE_BITMASK,
    .                size = sizeof(uint8_t),
                    .field_index = PROTO_FIELD_IPV4,
                    .input_index = PROTO_FIELD_IPV4,
                    .offset = offsetof(struct ipv4_5tuple, proto),
            },
            { 
                    .type = RTE_ACL_FIELD_TYPE_MASK,
                    .size = sizeof(uint32_t),
                    .field_index = SRC_FIELD_IPV4,
                    .input_index = SRC_FIELD_IPV4,
                    .offset = offsetof(struct ipv4_5tuple, ip_src),
            },
            { 
                    .type = RTE_ACL_FIELD_TYPE_MASK,
                    .size = sizeof(uint32_t),
                    .field_index = DST_FIELD_IPV4,
                    .input_index = DST_FIELD_IPV4,
                    .offset = offsetof(struct ipv4_5tuple, ip_dst),
            },
            { 
                    .type = RTE_ACL_FIELD_TYPE_RANGE,
                    .size = sizeof(uint16_t),
                    .field_index = SRCP_FIELD_IPV4,
                    .input_index = SRCP_FIELD_IPV4,
                    .offset = offsetof(struct ipv4_5tuple, port_src),
            },
            { 
                    .type = RTE_ACL_FIELD_TYPE_RANGE,
                    .size = sizeof(uint16_t),
                    .field_index = DSTP_FIELD_IPV4,
                    .input_index = SRCP_FIELD_IPV4,
                    .offset = offsetof(struct ipv4_5tuple, port_dst),
            },
    };

而定义规则时有以下几个字段需要注意:  
priority:定义了规则的优先级。  
category\_mask:表明规则属于哪个分类。  
userdata:当最高优先级的规则匹配时,会使用此userdata放入category\_mask中指定的下标中。  
ACL常用的API见表5-4  
![DPDK ACL常用API][DPDK ACL_API]  
ACL主要思路就是创建了Tier相关的数据结构,匹配字段中每个字段中的每个字节都会作为Tier中的一层进行匹配,每一层都作为到达最终匹配结果的一个路径。关于具体的ACL相关的使用,有兴趣的读者可以参考DPDK的源代码。

## 报文分发 ##

Packet distributor(报文分发)是DPDK提供给用户的一个用于包分发的API库,用于进行包分发。主要功能可以用图5-11进行描述。  
![DPDK Redistributor框图][DPDK Redistributor]  
从图5-11中可以看出,一般是通过一个distributor分发到不同的worker 上 进 行 报 文 处 理 , 当 报 文 处 理 完 后 再 通 过 worker 返 回 给distributor,具体实现可以参考DPDK的源代码。本书只列举出以下几个点:  
·Mbuf中的tag可以通过硬件的卸载功能从描述符中获取,也可以通过纯软件获取,DPDK的distributor负责把新产生的stream关联到某一个worker上并记录此Mbuf中的哈希值,等下一次同样stream的报文再过来的时候,只会放到同一tag对应的编号最小的worker中对应的backlog中。  
·distributor主要处理的函数是rte\_distributor\_process,它的主要作用就是进行报文分发,并且如果第一个worker的backlog已经满了,可能会将相同的流分配到不同的worker上。  
·worker 通 过 rte\_distributor\_get\_pkt 来 向 distributor 请 求 报文。  
·worker将处理完的报文返回给distributor,然后distributor可以配合第3章提到的ordering的库来进行排序。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/b869b416a1444c17a5017b8827a2cc26.png
[DPDK]: /images/20221122/9da335d571c64a488fe5387813572831.png
[DPDK RTC_pipeline]: /images/20221122/bff40fed00bf4fc9b0cacc3643fa3ef6.png
[DPDK pipeline]: /images/20221122/ec4b033bafb24f489f71f23705df42df.png
[DPDK Port_Table_Action]: /images/20221122/1aa4168696c34f40b67a44d06d09dfcb.png
[DPDK Routing Pipeline]: /images/20221122/be8943db30264f88be482c112b3ac75d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/c3d1ed092ac64bfb8c569d960d2d0641.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyYmZseQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/78d4929ba24440d0b174f57cbe3bfe2c.png
[CRC]: /images/20221122/b8079339dafd401c846bd9026ef747ee.png
[DPDK LPM]: /images/20221122/4949c26784c045319208b28b34d7e28b.png
[DPDK ACL_API]: /images/20221122/c72fe87f185746d49dce17d19c8c5637.png
[DPDK Redistributor]: /images/20221122/0040c52e26d4473da3ccf6aaa8333c63.png