POF技术分享（一）：基本原理

admin

</p>前言：

之前对POF基本原理、POF交换机源码结构进行解读，但是，要想完成POF交换机的二次开发和拓展，有必要对POF交换机特有的数据包处理流程、POF交换机和控制器交互模式进行了解，本节对数据包处理流程进行分析。

0 基础

在开始分析之前，先看看一个基本结构体和流程图：

结构体：pofdp_packet
这里需要明确一个重要结构体pofdp_packet（pof_datapath.h）,变量名一般为dpp。它是整个匹配处理的对象，集合了数据包相关内容、当前表和表项、待执行的instruction相关内容等，后面过程会用到。这里示意其中部分属性：  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/* Packet infomation including data, length, received port. */ struct pofdp_packet{ ... uint32_t ori_len; /* The original packet length. uint8_t *buf; /* The memery which stores the whole packet. */ /* Output. */ uint16_t output_packet_len; /* Byte unit. */ /* The length of output packet. */ uint16_t output_packet_offset; /* Byte unit. */ /* The start position of output. */ uint16_t output_metadata_len; /* Byte unit. */ uint16_t output_metadata_offset; /* Bit unit. */ /* The output metadata length and offset. * Packet data output right behind the metadata. */ uint16_t output_whole_len; /* = output_packet_len + output_metadata_len. */ uint8_t *buf_out; /* The memery which store the output data. */ /* Offset. */ uint16_t offset; /* Byte unit. */ /* The base offset of table field and actions. */ uint8_t *buf_offset; /* The packet pointer shift offset. * buf_offset = buf + offset */ uint32_t left_len; /* Length of left packet after shifting offset. * left_len = metadata->len - offset. */ /* Metadata. */ struct pofdp_metadata *metadata; /* The memery which stores the packet metadata. * The packet WHOLE length and input port index * has been stored in metadata. */ uint16_t metadata_len; /* The length of packet metadata in byte. */ /* Instruction & Actions. */ struct pof_instruction *ins;/* The memery which stores the instructions need * to be implemented. */ ... };




结构体pofdp_packet成员属性有很多，其中与packet内容相的属性非常重要，关系较为复杂。则下图示意出相关关系，黄色部分为转发出口待输出域：

流程图
数据包进入POF交换机后，会进行一系列匹配处理过程，为了方便后面分析和对照，这里先给出整体流程图：

一 Packet处理入口

有了以上基础，现在开始进入分析流程。pofdp_main_task（pof_datapath.c）函数是POF开启的一个线程任务，对进入pof交换机的packet进行循环、逐一的处理，主要代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

static uint32_t pofdp_main_task(void *arg_ptr){ ... struct pof_instruction first_ins[1] = {0}; ... set_goto_first_table_instruction(first_ins); while(1){ ret = pofdp_recv_raw(dpp); ... if(dpp->ori_l en > POFDP_PACKET_RAW_MAX_LEN){ ... } if(POF_OK != poflr_check_flow_table_exist(POFDP_FIRST_TABLE_ID)){ ... } /* Forward the packet. */ ret = pofdp_forward(dpp, first_ins); ... } return POF_OK; }

这里主要做了这么几件事情：

设定默认instruction，即goto第一张表0(set_goto_first_table_instruction)，为了每个进入交换机的packet都可以从表0开始匹配处理。如果想改变数据包处理流程，那就需要从这里入手。此后，采用while开始每个packet的循环处理;从端口的packet接收队列中读取packet数据（pofdp_recv_raw）;packet长度检测、第一个表存在性检测，如果检测出错则释放此packet缓存;packet转发处理（pofdp_forward函数）。

二 Packet的instruction集中处理

接上面，进入pofdp_forward函数（pof_datapath.c），主要代码：
ret = init_packet_metadata(dpp, (struct pofdp_metadata *)metadata, sizeof(metadata));
...
dpp->ins = first_ins;
dpp->ins_todo_num = 1;
ret = pofdp_instruction_execute(dpp)
这里进行两件事：

初始化dpp(pofdp_packet结构体)的一些属性：初始化dpp的元数据区metadata（初始化为0）、初始化dpp的instruction为firs_ins（即goto第一张表0）调用pofdp_instruction_execute函数，对dpp执行其instruction，这也是packet进入pof交换机第一次执行的instruction，即跳转到表0进行匹配。

在pofdp_instruction_execute函数中(pof_instruction.c)，通过while循环，检测dpp的所有instruction是否执行完，如果没有，则调用excute_##INSTRUCTIONS_NAME函数，执行相应instruction。当然，这里对于进入POF交换机的每一个packet来说，默认第一个动作是跳转表0，即调用execute_GOTO_TABLE函数，执行其跳转表0的动作。

三 跳转表instruction和匹配处理

对于数据包，默认的第一个动作就是跳转表0动作的执行，这里以这个为例分析。execute_GOTO_TABLE函数(pof_instruction.c)主要实现跳转到指定表，并且用跳转前生成的key，方便跳转后进行跳转表的匹配。
因为此节包含着数据包跳转前的处理、key的生成、表如何匹配等多项关键性内容，因此需要逐条分析。
3.1 基础内容
先来看看跳转的instruction结构体：
typedef struct pof_instruction_goto_table{
uint8_t next_table_id;
uint8_t match_field_num;
uint16_t packet_offset;
uint8_t pad[4]; /*8 bytes aligned*/
pof_match match[POF_MAX_MATCH_FIELD_NUM];
}pof_instruction_goto_table;

next_table_id：待跳转表id，具有全局性，之后会分析match_field_num：待跳转表的匹配域数量packet_offset：Byte类型，即跳转后packet指针的需要的偏移量，如果不偏移则为0match：待跳转表的匹配域内容，匹配域结构体为pof_match（包含field_id、offset和len）

3.2 packet偏移
p = (pof_instruction_goto_table *)dpp->ins->instruction_data;
...
ret = move_packet_offset_forward(dpp, p->packet_offset);
execute_GOTO_TABLE函数开始，将dpp中跳转instruction赋给p，然后对dpp进行偏移（由于是packet初次跳转，之前默认值为0，即不偏移）。当然，有必要看看如何偏移，进入函数move_packet_offset_forward：
if(offset > dpp->left_len){
...
}
dpp->left_len -= offset;
dpp->offset += offset;
dpp->buf_offset = dpp->buf + dpp->offset;
这里dpp的四个属性需要说明：

buf: 原始packet的指针初始位置buf_offset:目前packet指针偏移到的位置,这是匹配和action执行的基准。offset：从起始位置buf到目前位置buf_offfset的偏移量left_len：剩余packet的的内容长度，即从buf_offset到packet末端的内容长度。

3.3 跳转表id和类型获取
首先需要清楚，pof中表的类型type定义了四种，如下：
typedef enum pof_table_type{
POF_MM_TABLE = 0,
POF_LPM_TABLE,
POF_EM_TABLE,
POF_LINEAR_TABLE,
POF_MAX_TABLE_TYPE
}pof_table_type;
每张表有俩编号，在相同类型表中有编号id（相对的），在所有表（全部类型表的集合）也有一个全局编号id（绝对的），跳转instruction指定的ID为表的全局编号（大写ID区分）。要找到全局ID的表对应哪种类型中的哪个相对id的表，需要进行转化映射：
ret = poflr_table_ID_to_id(p->next_table_id, table_type, table_id);
其实映射法则很简单，就是查看每种类型表有很几个，进行累加，看看加到哪一种类型表的第几张表时恰好等于全局ID，则找到全局ID表对应的表类型(table_type)和表的相对id(table_id)。
3.4 待跳转表获取
所有表在一个全局的二维数组poflr_table_ptr中存储（维度即类型和相对id），知道了类型和相对id，很容易得到具体跳转的表：
poflr_get_flow_table(&table_vhal_ptr, *table_type, *table_id);
table_vhal_ptr（poflr_flow_table结构体）即返回得到的跳转表，poflr_flow_table结构体是具体一张表内容的集合，定义如下：
typedef struct poflr_flow_table{
pof_flow_table tbl_base_info;
poflr_flow_entry *entry_ptr;
uint32_t entry_num;
uint32_t state; // POFLR_STATE_VALID or POFLR_STATE_INVALID
}poflr_flow_table;

tbl_base_info：此表基本信息（结构体pof_flow_table），包含表名字，表全局ID，表类型，匹配域数量和所含有的匹配域基本信息等（结构体pof_match，这点和OF表不同，后面会具体分析）poflr_flow_entry：此表含有的所有流表项，后面会具体分析entry_num：流表项数量state：此表状态，用True 或False表示此表是否存在。

3.5 查找key构造
要完成POF的GOTO_Table后的表的匹配，是需要根据key来对表的各个表项匹配域进行查找匹配的，因此需要先构造key。这里key用变量key_ptr（二维指针数组，存储key的各个匹配字段）表示，先对其分配空间初始化：
key_ptr = (uint8_t **)malloc(POF_MAX_MATCH_FIELD_NUM * sizeof(ptr_t));
for(i=0; i<POF_MAX_MATCH_FIELD_NUM; i++){
key_ptr = (uint8_t *)malloc(POF_MAX_FIELD_LENGTH_IN_BYTE);
key_ptr（查找key）直接分配最大数量的匹配字段（8个），每个匹配字段长度为最大（16Byte）,然后调用函数pofdp_find_key构造key。
pofdp_find_key输入为dpp->buf_offset(即指针packet，示意原数据包packet偏移到buf_offset处为基准的剩下数据)，metadata，此表的匹配域数量match_field_num和匹配域数组match。通过这些来构造key的match_field_num个待匹配字段。
每个match即结构体pof_match，有必要看其结构体：
typedef struct pof_match{
uint16_t field_id; /*0xffff means metadata*/
uint16_t offset; /*bit unit*/
uint16_t len; /*length in bit unit*/
uint8_t pad[2]; /*8 bytes aligned*/
}pof_match;
其属性field_id指示待匹配字段由packet还是metadata（field_id=0xFFFF）构成，还定义了偏移量（offset，单位bit）和长度（len，单位bit）。当field_id不是0xFFFF时，即意味着packet的buf_offset位置再偏移offset长度后的位置a处，a向后len长度的数据需要构成key的一个待匹配字段。代码如下：
for(i=0; i<match_field_num; i++){
tmp_match = match;
if(tmp_match.field_id != 0xFFFF){
pofdp_copy_bit(packet, key_ptr, tmp_match.offset, tmp_match.len);
}
if(tmp_match.field_id == 0xFFFF){
pofdp_copy_bit(metadata, key_ptr, tmp_match.offset, tmp_match.len);
可以看到，每个key的待匹配字段都由offset、len来从packet（或metadata）中取出构造，见函数 pofdp_copy_bit：
while(process_len_b < len_b){
*(data_res++) = POF_MOVE_BIT_LEFT(*ptr, offset_b_x) \
| POF_MOVE_BIT_RIGHT(*(++ptr), 8 - offset_b_x);
process_len_b += 8;
}
data_res--;
*data_res = *data_res & POF_MOVE_BIT_LEFT(0xff, process_len_b - len_b);
key的每个匹配域字段长度为16Byte（uint8_t，char类型），while循环把刚刚大于len的整数个Byte先赋值填充到匹配域字段，然后再把多于出来的bit位置0。其过程见示意图：
图例解释：pof_match的offset为9，len为14（即意味着取出偏移量为9长度为14个bit作为key的一个待匹待域），14位不足两个字节，用0填充。
首先明确，匹配域按字节算，且标记匹配域每个字节的data_res也是字节。可以得到offset_b_x=9%8=1,*ptr即字符“1”。
通过第一次while循环取出第一个字符‘1’的后七位和第二个字符‘！’的前一位，构成待匹配字段的第一个字节‘b’（方法：即第一个字节左移1位，即0(0110001)->(0110001)0,第二个字节右移7位，即(0010000)1->0(0010000),然后做逻辑或即可得。注意无符号数移位不足的用0补），此时process_len_b=0+8=8<14,需要进行第二次while循环，同样方法得到第二个字节‘c’，由于取出了两个字节（16位），比len要求的14位多两位，因此需要在while循环外对最后一个字节（即第二个字节）进行作与（后两位为0）。这样，则可以得到packet中指定的偏移量为9长度为14的所有14个bit值，后两位用0填充，这16位成为key的匹配域的第一个字段，其他字段构造同理。
当然，一般情况pof_match的offset和len都为8bit（1个字节）的整数倍，但不一定(如匹配字段是是IP层的一些位字段)。这里只是为了示意通用性，例子才这么设计。
3.6 流表项匹配
流表项匹配的主要过程代码如下：
if(pofdp_lookup_in_table((uint8_t **)key_ptr, table_vhal_ptr->tbl_base_info.match_field_num, \
*table_vhal_ptr, &dpp->flow_entry) != POF_OK){
...
ret = pofdp_entry_nomatch(dpp);
dpp->packet_done = TRUE;
}else{
...
dpp->ins = dpp->flow_entry->instruction;
dpp->ins_todo_num = dpp->flow_entry->instruction_num;
dpp->ins_done_num = 0;
}
没有匹配到，则调用函数pofdp_entry_nomatch，根据配置情况选择丢弃包或长传控制器；匹配到则将流表项instruction填充入dpp中，待执行。
主要看看POF匹配机制：在POF中，每张流表的pof_match结构体（之前提到）相对于流表的匹配域资源（基准），其定义了这张流表应该含有的所有匹配字段。同一张流表中的流表项的匹配域的匹配字段个数要和流表定义的相同，且又因key_ptr（待查询key）是按照流表匹配域基准构造的，则每条流表项的匹配域部分，其匹配字段的个数、顺序、匹配字段字节长度都是一致的。
因此，POF流表项查询机制很简单，就是逐条取出流表项匹配域，按照匹配字段顺序，然后一个个字节掩码后进行对比即可，遇到重复匹配到的流表项，考察优先级大的记录采用即可。
逐条匹配过程见pofdp_lookup_in_table(pof_lookup.c):
for(i=0; i<entry_num; entry_ptr++){
...
if(pofdp_match_per_entry(key_ptr, match_field_num, entry_ptr->entry.match) == TRUE){
if(priority == NULL){
priority = &entry_ptr->entry.priority;
*entry_ptrptr = &entry_ptr->entry;
}else{
if(*priority < entry_ptr->entry.priority){
每一条流表项其匹配域匹配细节见函数pofdp_lookup_in_table->pofdp_match_per_entry：
value = tmp_match.value;
mask = tmp_match.mask;
len_B = POF_BITNUM_TO_BYTENUM_CEIL(tmp_match.len);
for(j=0; j<len_B; j++){
if((mask[j] & key_ptr[j]) != (mask[j] & value[j]))
return FALSE;
可以看到，就是按照匹配字段的个数match_field_num，对每一个字段的每个字节，掩码后比对。所以，比对过程中，已经不需要偏移量和偏移长度了。
这里基本分析完数据包进入POF之后匹配处理等全部过程，接下来简单说明几个重要instruction的执行。

四 Instruction是APPLY_ACTIONS

APPLY_ACTIONS这种Instruaction，即可以包含很多立即执行的动作actions,执行函数为execute_APPLY_ACTIONS->pofdp_action_execute（pof_action.c）,循环执行完包含的各个action,这里根据action不同逐一简单说明：

execute_OUTPUT：packet/metadata端口发出。给定packet偏移量packet_offset（bit，相对于packet其实位dpp->buf的）、metadata偏移量metadata_offset和metadata偏移长度metadata_len，将metadata指定偏移量和产度的值放入data，再将packet指定偏移之后的值放入data（metadata放入之后），然后将data赋给dpp->buf_out，从指定端口发出。execute_ADD_FIELD:添加packet字段。顾名思义，在packet相应位置之后添加一个字段，修改dpp->metadata->len。（packet的实时长度由metadata->len记录）。execute_DELETE_FIELD：删除packet字段。与execute_ADD_FIELD同理，只是对packet删除一个字段。execute_SET_FIELD:设置packet字段。给出值、偏移量和长度（pof_match_x），对packet的相应偏移量和长度的相应位置的值用给出的值进行修改。execute_MODIFY_FIELD：修改packet/metadata字段。给出一个increment数值、偏移量和长度（pof_match），取出packet相应偏移量和长度位置处的值，强制加increment后，然后再填充到刚才偏移量和长度位置处；同样有可能是对metadata的某个字段进行强制加increment后修改。（场景，比如IPV4中TTL增加）execute_SET_FIELD_FROM_METADATA：通过metadata修改packet字段。给出metadata偏移量metadata_offset、packet偏移量offset和偏移长度len，然后用metadata的metadata_offset处长度为len的值覆盖packet偏移量为offset长度为len的值。

五 Instruction是execute_WRITE_METADATA

WRITE_METADATA和APPLY_ACTIONS的execute_SET_FIELD类似，功能是设置metadata字段。给出值value、metadata偏移位置metadata_offset和长度len,即对metadata的metadata_offset位置处长度为len的值写入value。

六 Instruction是execute_WRITE_METADATA_FROM_PACKET

WRITE_METADATA_FROM_PACKET和APPLY_ACTIONS的execute_SET_FIELD_FROM_METADATA是相反过程，通过packet设置metadata字段。给出metadata偏移量metadata_offset、packet偏移量offset和偏移长度len，然后将packet的metadata_offset处长度为len的值写入到metadata偏移量为offset长度为len处。
应用场景：将原packet字段值记录入metadata，后期可以通过metadata对原packet相应字段进行恢复或是直接通过metadata字段进行匹配操作。

后记


虽然POF和OVS等OpenFlow交换机大同小异，但是对于数据包的匹配处理流程还是有一些独有的特色。本文着重对数据包进入POF交换机后数据包处理、匹配、instruction执行等做了细节介绍，在学习POF交换机的过程中，感受到OpenFlow交换机在匹配处理过程中无法体现出来的灵活性，基于此可以拓展研究的地方也相对会多很多。
作者简介：
晏思宇，2014/09-至今，北京邮电大学信息与通信工程学院未来网络理论与应用实验室（北邮FNL实验室）攻读硕士研究生，主要研究方向为SDN、Open vSwtich拓展性、控制器业务开发等，具有一定SDN网络实验平台搭建部署和管理经验。
--------------华丽的分割线------------------
本文系《SDNLAB原创文章奖励计划》投稿文章，该计划旨在鼓励广大从业人员在SDN/NFV/Cloud网络领域创新技术、开源项目、产业动态等方面进行经验和成果的文字传播、分享、交流。有意向投稿的同学请通过官方唯一指定投稿通道进行文章投递，投稿细则请参考《SDNLAB原创文章奖励计划》
声明:本文转载自网络。版权归原作者所有,如有侵权请联系删除。