open vswitch研究：flow

neocai

　　struct sw_flow_key 用来唯一定义一个flow，该结构相当复杂，请参考源码
　　sw_flow_key分为四部分，分别代表switch, L2, L3, L4的profile

　　switch的profile是一个struct phy结构，包括了tunnel>　　struct sw_flow表示一个流，
　　struct sw_flow {
　　struct rcu_head rcu;
　　struct hlist_node hash_node[2];
　　u32 hash;
　　struct sw_flow_key key;
　　struct sw_flow_actions __rcu *sf_acts;
　　atomic_t refcnt;
　　bool dead;
　　spinlock_t lock;    /* Lock for values below. */
　　unsigned long used; /* Last used time (in jiffies). */
　　u64 packet_count;   /* Number of packets matched. */
　　u64 byte_count;     /* Number of bytes matched. */
　　u8 tcp_flags;       /* Union of seen TCP flags. */
　　};
　　hash_node,  hash表明了flow是被hash的，根据OVS的原理，对于每个包都会匹配一个flow，然后执行相应的action，这个action就保存在 struct sw_flow_actions *sf_acts里，key用来唯一标识一个flow，最后的used, packet_count,  byte_count都是统计信息
　　下面来分析flow.c的代码
　　check_header, 调用pskb_may_pull为skb预留len长度的头部空间，成功则返回0，否则返回错误码
　　arphdr_ok, check_iphdr, tcphdr_ok, udphdr_ok, icmphdr_ok都是这种检查，由于ip, tcp会多个option，所以代码稍微多一点，以check_iphdr为例，
　　static int check_iphdr(struct sk_buff *skb)
　　{
　　unsigned int nh_ofs = skb_network_offset(skb);
　　unsigned int ip_len;
　　int err;

　　err = check_header(skb, nh_ofs +>　　nh_ofs为IP头离skb->head的offset，这里表示要为skb预留nh_ofs+IP头长度的空间
　　if (unlikely(err))
　　return err;
　　ip_len = ip_hdrlen(skb);
　　ip_len是基于iphdr->ihl计算出的包括ip option的IP头的长度

　　if (unlikely(ip_len 　　skb->len < nh_ofs + ip_len))
　　return -EINVAL;
　　如果skb->len长度不够，报错退出
　　skb_set_transport_header(skb, nh_ofs + ip_len);
　　设置skb->transport_header, 把skb->data指向L4头的位置
　　return 0;
　　}
　　ovs_flow_actions_alloc, 分配一个sw_flow_actions结构，我们首先来看struct nlattr结构，
　　struct nlattr {
　　uint16_t nla_len;
　　uint16_t nla_type;
　　};
　　这是一个netlink数据包的包头部分（长度是NLA_HDRLEN），后面的线性空间是nla_data部分，而nla_len就是数据部分的 长度。在分配sw_flow_actions时，除了sizeof(struct  sw_flow_action)的头部之外，还要多一个nla_len长度的线性空间
　　我们先来看下flex_array这个数据结构：
　　作者在flex_array的注释中说，之所以创建这个数据结构，是为了防止大size的kmalloc失败，可以看到flex_array由多个 flex_array_part组成，每个flex_array_part是一个大小是PAGE_SIZE的空间，因此可以把flex_array看作 page的链表
　　struct flex_array {
　　union {
　　struct {
　　int element_size;
　　int total_nr_elements;
　　int elems_per_part;
　　u32 reciprocal_elems;
　　struct flex_array_part *parts[];
　　};
　　/*
　　* This little trick makes sure that

　　*>　　*/
　　char padding[FLEX_ARRAY_BASE_SIZE];
　　};
　　};
　　flex_array不算那些flex_array_part，本身最多占一个page大小，因此我们可以算出最多可以容纳多少个parts （FLEX_ARRAY_NR_BASE_PTRS宏）
　　flex_array_alloc函数这样看来就比较明了，该函数传入element_size, total,  计算出elems_per_part,  total_nr_elements，如果total个数的element计算下来可以放到flex_array所剩余的page里，那么memset这 段内存为0x6c，作为poison（否则肯定是到用的时候再分配咯）
　　flex_array_free_parts，用来free所有的parts所占的page；flex_array_free除了调用flex_array_free_parts，最后再free掉flex_array结构体
　　__fa_get_part，如果part_nr代表的flex_array_part指针存在，返回该指针，否则kmalloc一个page大小的flex_array_parts，并存在flex_array->parts[part_nr]中
　　flex_array_put，拷贝第element_nr个元素到flex_array中，该函数会检查flex_array是否只在一个 page中，如果不是那么找到element_nr对应的part的page，之后调用index_inside_part，找到元素的offset，最 后memcpy把数据拷贝到flex_array中
　　flex_array_clear，把第element_nr个元素从flex_array中清除，这块内存被设为poison 0x6c
　　flex_array_prealloc，传入start的元素，和需要分配的元素个数，会预先为这些元素分配part空间，如果需要的话
　　flex_array_get，返回第nr个flex_array里的元素
　　flex_array_shrink，对于没有元素的part，free掉所占用的page
　　ovs拿flex_array来做hlist_head*的数组，用来做存储flow的hash表，同一hash值的flow被挂在同一个bucket下面，我们先来看struct flow_table的结构如下：
　　struct flow_table {
　　struct flex_array *buckets;
　　unsigned int count, n_buckets;
　　struct rcu_head rcu;
　　int node_ver;
　　u32 hash_seed;
　　bool keep_flows;
　　};
　　核心是一个buckets的flex_array，就是哈希表的桶，所有的flow都挂在这些桶里
　　alloc_buckets，首先分配一个flex_array结构给buckets，之后为0-n_buckets个元素预分配好part的page空间
　　find_bucket，基于hash值，得到flex_array的hash索引的hlist_head*
　　free_buckets，释放flex_array和flex_array_part相应的page
　　下面是流表的操作：
　　ovs_flow_tbl_alloc，分配一个flow_table结构，调用alloc_buckets为table->buckets分配一个flex_array
　　ovs_flow_tbl_destroy，free flow_table和相应的flex_array空间
　　ovs_flow_tbl_next，拿到flow_table的下一条flow
　　ovs_flow_tbl_insert，就是一个哈希表的插入操作
　　ovs_flow_tbl_lookup，根据flow的key来查找流，ovs_flow_hash根据key, key  length首先计算出hash值，之后调用find_bucket找到hlist_head*，对于hlist_head下的每一个 hist_node，如果flow->key相同，则返回这条flow
　　ovs_flow_tbl_remove，由于flow结构里已经存了hlist_node的指针，那么直接调用hlist_del_rcu就可以了
　　ovs_flow_tbl_rehash,  ovs_flow_tbl_expand，重新分配一个新的flow_table结构，由于n_buckets大小发生了变化，顺便重新计算下hash 值，之后调用flow_table_copy_flows把老的流表里的流拷贝到新的流表里
　　flow_table_copy_flows，把老的流表里的流拷贝到新的流表里，同时更新流表的node_ver
　　ovs_flow_extract，根据skb的内容，解析出sw_flow_key的内容
　　ovs还可以通过netlink来交换flow信息，下面的函数涉及到flow和netlink之间的操作
　　先来看看netlink的封装实现
　　linux/netlink.h 是linux对netlink的定义，netlink可以通过netlink socket通信，其报文格式如下
　　
　　
　　+----------------+--------+--------------+--------+---------------------
　　|   nlmsghdr   |  Pad   |  Payload   |  Pad  |  nlmsghdr ...
　　+----------------+--------+--------------+--------+---------------------
　　netlink的 message header, payload都是要4字节对齐的，nlmsg_total_size是nlmsghdr +  payload对齐后的长度，而nlmsg_msg_size是nlmsghdr +  payload不对齐后的长度。nlmsg_data(nlmsghdr  *)可以返回payload的起始位置，nlmsg_next(nlmsghdr *)可以返回下一个netlink message的起始位置。
　　Payload Format:
　　           
　　+----------------------+-------+-----------------------+
　　|  Family Header  |  Pad  |  Attributes              |
　　+----------------------+-------+-----------------------+
　　^-- nlmsg_attrdata(nlmsghdr*, hdrlen)
　　payload的长度可以用nlmsghdr->nlmsg_len -  NLMSG_HDRLEN得到，可以看出其实nlmsghdr->nlmsg_len里就是NLMSG_HDRLEN+未对齐的payload长 度。nlmsg_attrlen(nlmsghdr,  hdrlen)则是payload长度减去对齐后的hdrlen的值。nlmsg_attrdata(nlmsghdr*,  hdrlen)则返回attributes头的位置
　　nlmsg_new，调用alloc_skb创建一个nlmsg_total_size(payload)大小的线性空间skb
　　nlmsg_put，为把长度nlmsg_total_size(payload)大小的netlink报文放入skb尾部的线性空间 skb_tailroom中准备空间。__nlmsg_put调用skb_put从skb线性空间的tail扩充一块 NLMSG_LENGTH(payload)大小的空间
　　nlmsg_get_pos，返回skb_tail_pointer(skb)
　　nlmsg_trim，调用skb_trim，进行skb线性空间的裁剪，只是操作下skb->tail的指针而已，这个和pskb_trim差别还是很大的
　　payload除去hdrlen的对齐部分就是一个attributes数组，其数据结构nlattr为
　　struct nlattr {
　　__u16 nla_len;
　　__u16 nla_type;
　　}
　　attributes数组的结构如下图：
　　
　　
　　+------------+-------+------------------+--------+--------
　　|  Header  |  Pad  |     Payload     |  Pad   | Header
　　+------------+-------+------------------+--------+--------
　　
　　其中nlattr->nla_len里的是nla_attr_size(payload)的长度
　　nla_reserve，在skb里预留nla_total_size(payload)长度的线性空间
　　nla_put，除了reserve以外，同时把数据拷贝到attr空间里
　　nla_append，把attribute添加到skb->tail下面的线性空间中
　　nla_put_XXX，把XXX当做attribute的payload，加到skb的线性空间中
　　nla_put_flag，设置nlattr的type
　　nlmsg_find_attr，调用nla_find，在nlmsg的payload里，查找相应attrtype的struct nlattr*
　　nlmsg_validate，调用nla_validate，在attributes的线性空间内验证attribute数据是否合法。 nla_validate对于attributes流里的每一个attribute，基于nla_policy调用validate_nla验证合法性， 这里的合法性主要是数据类型和长度是否匹配
　　nlmsg_parse，调用nla_parse，nla_parse传入attributes的线性内存，目的是parse这块内存里的各种attribute到一个struct nlattr* 数组中，数组大小由attribute type个数决定
　　ovs_flow_to_nlattrs，对于flow每个成员项，反复调用nla_put_uXX, nla_reserve，并把flow成员数据拷贝到相应attribute属性里
　　ovs_flow_from_nlattrs，先调用parse_flow_nlattrs把netlink message解析到一个struct nlattr*的数组中，数组个数为__OVS_KEY_ATTR_MAX，请参考enum ovs_key_attr
　　enum ovs_key_attr {
　　OVS_KEY_ATTR_UNSPEC,
　　OVS_KEY_ATTR_ENCAP, /* Nested set of encapsulated attributes. */
　　OVS_KEY_ATTR_PRIORITY,  /* u32 skb->priority */
　　OVS_KEY_ATTR_IN_PORT,   /* u32 OVS dp port number */
　　OVS_KEY_ATTR_ETHERNET,  /* struct ovs_key_ethernet */
　　OVS_KEY_ATTR_VLAN,  /* be16 VLAN TCI */
　　OVS_KEY_ATTR_ETHERTYPE, /* be16 Ethernet type */
　　OVS_KEY_ATTR_IPV4,      /* struct ovs_key_ipv4 */
　　OVS_KEY_ATTR_IPV6,      /* struct ovs_key_ipv6 */
　　OVS_KEY_ATTR_TCP,       /* struct ovs_key_tcp */
　　OVS_KEY_ATTR_UDP,       /* struct ovs_key_udp */
　　OVS_KEY_ATTR_ICMP,      /* struct ovs_key_icmp */
　　OVS_KEY_ATTR_ICMPV6,    /* struct ovs_key_icmpv6 */
　　OVS_KEY_ATTR_ARP,       /* struct ovs_key_arp */
　　OVS_KEY_ATTR_ND,        /* struct ovs_key_nd */

　　OVS_KEY_ATTR_TUN_ID = 63, /* be64 tunnel>　　__OVS_KEY_ATTR_MAX
　　};
　　看出来了把，对于flow的每一个成员，都有一个enum  ovs_key_attr里面的type与之对应，而这个type值就是nlattr里的nl_type。parse_flow_nlattrs在做解析 的时候，对每一个nlattr，解析出nl_type，把struct nlattr* 开头的线性空间存到struct nlattr*  a[type]里，同时对每个type都用一位来标记解析成功了
　　之后根据标记，对都数据被解析的type，调用nla_get_xxxx从a[type]里拿到数据，对于非简单类型的数据，用nla_data从a[type]里拿数据，最终组合成一个sw_flow_key