前言
本文以openvswitch 2.5.0源码，主要介绍**应用层**openflow处理引擎相关的数据结构，分析其设计的原因和精彩之处。
报文结构
网络中最重要的就是报文，因此首先分析报文结构struct dp_packet：
/* Buffer for holding packet data. A dp_packet is automatically reallocated
* as necessary if it grows too large for the available memory.
*/
struct dp_packet {
#ifdef DPDK_NETDEV
struct rte_mbuf mbuf; /* DPDK mbuf */
#else
void *base_; /* First byte of allocated space. */
uint16_t allocated_; /* Number of bytes allocated. */
uint16_t data_ofs; /* First byte actually in use. */
uint32_t size_; /* Number of bytes in use. */
uint32_t rss_hash; /* Packet hash. */
bool rss_hash_valid; /* Is the 'rss_hash' valid? */
#endif
enum dp_packet_source source; /* Source of memory allocated as 'base'. */
uint8_t l2_pad_size; /* Detected l2 padding size.
* Padding is non-pullable. */
uint16_t l2_5_ofs; /* MPLS label stack offset, or UINT16_MAX */
uint16_t l3_ofs; /* Network-level header offset,
* or UINT16_MAX. */
uint16_t l4_ofs; /* Transport-level header offset,
or UINT16_MAX. */
struct pkt_metadata md;
};可以看出，在采用dpdk时直接使用struct rte_mbuf结构，再加上部分辅助字段。
struct pkt_metadata结构如下：
/* Datapath packet metadata */
struct pkt_metadata {
uint32_t recirc_id; /* Recirculation id carried with the
recirculating packets. 0 for packets
received from the wire. */
uint32_t dp_hash; /* hash value computed by the recirculation
action. */
uint32_t skb_priority; /* Packet priority for QoS. */
uint32_t pkt_mark; /* Packet mark. */
uint16_t ct_state; /* Connection state. */
uint16_t ct_zone; /* Connection zone. */
uint32_t ct_mark; /* Connection mark. */
ovs_u128 ct_label; /* Connection label. */
union flow_in_port in_port; /* Input port. */
struct flow_tnl tunnel; /* Encapsulating tunnel parameters. Note that
* if 'ip_dst' == 0, the rest of the fields may
* be uninitialized. */
};这个结构用于存储报文的一些元数据和隧道信息，在报文第一次处理前进行初始化。
匹配结构
匹配结构的主角是struct flow，其包含了一个报文的完整特征。此结构连接了配置和报文处理，是openflow的核心结构：
struct flow {
/* Metadata */
struct flow_tnl tunnel; /* Encapsulating tunnel parameters. */
ovs_be64 metadata; /* OpenFlow Metadata. */
uint32_t regs[FLOW_N_REGS]; /* Registers. */
uint32_t skb_priority; /* Packet priority for QoS. */
uint32_t pkt_mark; /* Packet mark. */
uint32_t dp_hash; /* Datapath computed hash value. The exact
* computation is opaque to the user space. */
union flow_in_port in_port; /* Input port.*/
uint32_t recirc_id; /* Must be exact match. */
uint16_t ct_state; /* Connection tracking state. */
uint16_t ct_zone; /* Connection tracking zone. */
uint32_t ct_mark; /* Connection mark.*/
uint8_t pad1[4]; /* Pad to 64 bits. */
ovs_u128 ct_label; /* Connection label. */
uint32_t conj_id; /* Conjunction ID. */
ofp_port_t actset_output; /* Output port in action set. */
uint8_t pad2[2]; /* Pad to 64 bits. */
/* L2, Order the same as in the Ethernet header! (64-bit aligned) */
struct eth_addr dl_dst; /* Ethernet destination address. */
struct eth_addr dl_src; /* Ethernet source address. */
ovs_be16 dl_type; /* Ethernet frame type. */
ovs_be16 vlan_tci; /* If 802.1Q, TCI | VLAN_CFI; otherwise 0. */
ovs_be32 mpls_lse[ROUND_UP(FLOW_MAX_MPLS_LABELS, 2)]; /* MPLS label stack
(with padding). */
/* L3 (64-bit aligned) */
ovs_be32 nw_src; /* IPv4 source address. */
ovs_be32 nw_dst; /* IPv4 destination address. */
struct in6_addr ipv6_src; /* IPv6 source address. */
struct in6_addr ipv6_dst; /* IPv6 destination address. */
ovs_be32 ipv6_label; /* IPv6 flow label. */
uint8_t nw_frag; /* FLOW_FRAG_* flags. */
uint8_t nw_tos; /* IP ToS (including DSCP and ECN). */
uint8_t nw_ttl; /* IP TTL/Hop Limit. */
uint8_t nw_proto; /* IP protocol or low 8 bits of ARP opcode. */
struct in6_addr nd_target; /* IPv6 neighbor discovery (ND) target. */
struct eth_addr arp_sha; /* ARP/ND source hardware address. */
struct eth_addr arp_tha; /* ARP/ND target hardware address. */
ovs_be16 tcp_flags; /* TCP flags. With L3 to avoid matching L4. */
ovs_be16 pad3; /* Pad to 64 bits. */
/* L4 (64-bit aligned) */
ovs_be16 tp_src; /* TCP/UDP/SCTP source port/ICMP type. */
ovs_be16 tp_dst; /* TCP/UDP/SCTP destination port/ICMP code. */
ovs_be32 igmp_group_ip4; /* IGMP group IPv4 address.
* Keep last for BUILD_ASSERT_DECL below. */
};在报文处理流程中，使用最多的结构是struct netdev_flow_key，每个报文在匹配时前都会解析到其中：
/* Stores a miniflow with inline values */
struct netdev_flow_key {
uint32_t hash; /* Hash function differs for different users. */
uint32_t len; /* Length of the following miniflow (incl. map). */
struct miniflow mf;
uint64_t buf[FLOW_MAX_PACKET_U64S];
};包含了hash值，这个值可以是由网卡计算的rss；也可以是多次处理时由软件计算出的。计算方法的不同可以用于查找flow或者flow_cache。len字段大小等于miniflow加上实际的buf数据长度，用于快速匹配。
接着来看struct miniflow这个结构：
typedef unsigned long long map_t;
#define MAP_T_BITS (sizeof(map_t) * CHAR_BIT)
#define FLOW_U64S (sizeof(struct flow) / sizeof(uint64_t))
#define DIV_ROUND_UP(X, Y) (((X) + ((Y) - 1)) / (Y))
#define FLOWMAP_UNITS DIV_ROUND_UP(FLOW_U64S, MAP_T_BITS)
struct flowmap {
map_t bits[FLOWMAP_UNITS];
};
struct miniflow {
struct flowmap map;
/* Followed by:
* uint64_t values[n];
* where 'n' is miniflow_n_values(miniflow). */
};这里把一些辅助的宏也罗列出来。
从名称上看也可以得知这是一个精简的flow的表示方法，因为struct flow结构有552字节大小，如果每包直接匹配552字节的flow，会对性能造成很大的影响。
从结构来看这是一个bitmap，大小为16字节，这个结构十分精巧，每bit对应表示flow对应位置的8字节是否存在数据。
struct netdev_flow_key的buf字段（480字节，因为struct flow中部分字段不用作键值）用于紧密放置真实的flow字段数据。
在进行cache匹配时，hash查找到桶，判断cache有效性后，直接从struct netdev_flow_key的mf字段开始比较（使用桶内的len字段作为比较长度），如果在报文类型存在不同，会在开始的16字节bitmap就匹配失败，大大节省了匹配时间；并且len极大地减小了需比较的长度，避免出现比较552字节的尴尬。struct miniflow是openflow快速匹配的精髓所在。
但是需要注意，这个结构只能用作精确比较，无法直接用于比较分类器（dpcls）。
如果cache无法命中，就需要去查找flow，同样的道理，直接比较552字节很不合理，因此抽象出一个结构struct dpcls_rule用于查找flow，如下所示：
/* Simple non-wildcarding single-priority classifier. */
struct dpcls {
struct cmap subtables_map;
struct pvector subtables;
};
/* A rule to be inserted to the classifier. */
struct dpcls_rule {
struct cmap_node cmap_node; /* Within struct dpcls_subtable 'rules'. */
struct netdev_flow_key *mask; /* Subtable's mask. */
struct netdev_flow_key flow; /* Matching key. */
/* 'flow' must be the last field, additional space is allocated here. */
};