注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

gmd20的个人空间

// 编程和生活

 
 
 

日志

 
 

2017-07-19-openvswitch源码阅读之flow匹配的实现.markdown  

2017-07-19 23:35:45|  分类: linux相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
[ovs datapath](http://docs.openvswitch.org/en/latest/topics/datapath/)
“UFID” 等概念的介绍
 

流表结构
=========
```text
struct datapath {
struct rcu_head rcu;
struct list_head list_node;

/* Flow table. */
struct flow_table table;     // 每个datapath有自己的流表,上来的包就是在这个流表里面搜索。但按照文档说法openflow有255个table的,不知道怎么从这个表跳到另外一个表。

/* Switch ports. */
struct hlist_head *ports;

/* Stats. */
struct dp_stats_percpu __percpu *stats_percpu;

/* Network namespace ref. */
possible_net_t net;

u32 user_features;

u32 max_headroom;
};



struct sw_flow {
struct rcu_head rcu;
struct {
struct hlist_node node[2];
u32 hash;
} flow_table, ufid_table;
int stats_last_writer; /* CPU id of the last writer on
* 'stats[0]'.
*/
struct sw_flow_key key;         // 用来算hash查找匹配流的, 就是从网络包里面提取的以太网头部,tcp端口之类的信息,很大的一个结构
struct sw_flow_id id;           // flow的UUID标识。底层有两个hash表,内核查找flow使用key来做哈希计算,用户空间用UFID计算哈希,在两个hash表里面走可以找到这个flow
struct sw_flow_mask *mask;      // key的mask,类似ip地址的mask
struct sw_flow_actions __rcu *sf_acts;
struct flow_stats __rcu *stats[]; /* One for each CPU.  First one
  * is allocated at flow creation time,
  * the rest are allocated on demand
  * while holding the 'stats[0].lock'.
  */
};



struct table_instance {  // 第2步的哈希表的数据结构
struct flex_array *buckets;
unsigned int n_buckets;
struct rcu_head rcu;
int node_ver;
u32 hash_seed;
bool keep_flows;
};

struct flow_table {
struct table_instance __rcu *ti;              // OVS_FLOW_ATTR_KEY 普通的哈希表
struct table_instance __rcu *ufid_ti;         // OVS_FLOW_ATTR_UFID 如果flow有ufid就使用这个哈希表。 是一个UUID字符串,不知道怎么区别这两种
struct mask_cache_entry __percpu *mask_cache;  // 每个cpu有个缓存mask cache,缓存这个flow使用的mask在mask_array里面的位置。是一个255个元素的哈希表
struct mask_array __rcu *mask_array;      // 所有flow使用到的mask的一个列表
unsigned long last_rehash;
unsigned int count;
unsigned int ufid_count;
};

ufid_ti 是供 “ovs-dpctl” 这些终端命令行通过指定flow的ufid(一个UUID)来操作flow用的? 一个flow应该同时在两个hash表里面。如果是网络包的查找
就用key 算hash找到flow,如果是命令行就根据指定的UUID找到对应的flow吧。这UFID主要是为了方便用户使用吧


mask_cache缓存的东西
struct mask_cache_entry {
u32 skb_hash;        //  linux内核的flow id
u32 mask_index;      //  这个linux flow(连接)应该使用的ovs哪一条flow的,那个flow的mask在mask_array里面的index
};


网络包进来的处理和查找flow
======================
flow.c 和 flow_table.c
```text
ovs_vport_receive
  ovs_flow_key_extract
    key_extract       // 这里会把skb的头部的mac地址ip地址端口等信息复制出来放到flow结构的key里面
  ovs_dp_process_packet
    ovs_flow_tbl_lookup_stats
      flow_lookup
```


flow的查找算法
==============

```text
/* Look up flow. */
flow = ovs_flow_tbl_lookup_stats(&dp->table, key, skb_get_hash(skb),
&n_mask_hit);

skb_get_hash是linux内核提供的函数,应该是linux内核提供的flow标识,应该是根据ip
tcp 端口这些计算生成的,同一个tcp连接的所有skb应该算出来是同一个hash值,表示
是属于同一个流的网络包。后面ovs里面应该用这个做流标识,用了缓存flow对应的mask的index。
参见内核源码  http://elixir.free-electrons.com/linux/latest/source/net/core/flow_dissector.c
/**
 * __skb_get_hash: calculate a flow hash
 * @skb: sk_buff to calculate flow hash from
 *
 * This function calculates a flow hash based on src/dst addresses
 * and src/dst port numbers.  Sets hash in skb to non-zero hash value
 * on success, zero indicates no valid hash.  Also, sets l4_hash in skb
 * if hash is a canonical 4-tuple hash over transport ports.
 */
void __skb_get_hash(struct sk_buff *skb)
{
struct flow_keys keys;
u32 hash;

__flow_hash_secret_init();

hash = ___skb_get_hash(skb, &keys, hashrnd);

__skb_set_sw_hash(skb, hash, flow_keys_have_l4(&keys));
}
EXPORT_SYMBOL(__skb_get_hash);



/*
 * mask_cache maps flow to probable mask. This cache is not tightly
 * coupled cache, It means updates to  mask list can result in inconsistent
 * cache entry in mask cache.
 * This is per cpu cache and is divided in MC_HASH_SEGS segments.
 * In case of a hash collision the entry is hashed in next segment.
 */
struct sw_flow *ovs_flow_tbl_lookup_stats(struct flow_table *tbl,
 const struct sw_flow_key *key,
 u32 skb_hash,
 u32 *n_mask_hit)
{
struct mask_array *ma = rcu_dereference(tbl->mask_array);
struct table_instance *ti = rcu_dereference(tbl->ti);
struct mask_cache_entry *entries, *ce;
struct sw_flow *flow;
u32 hash;
int seg;

*n_mask_hit = 0;
if (unlikely(!skb_hash)) {
u32 mask_index = 0;

return flow_lookup(tbl, ti, ma, key, n_mask_hit, &mask_index);
}

/* Pre and post recirulation flows usually have the same skb_hash
* value. To avoid hash collisions, rehash the 'skb_hash' with
* 'recirc_id'.  */
if (key->recirc_id)
skb_hash = jhash_1word(skb_hash, key->recirc_id);

ce = NULL;
hash = skb_hash;    // 这个linux内核的flow标识,同一个流比如tcp连接应该有一致的hash值
entries = this_cpu_ptr(tbl->mask_cache);    // 每个cpu核心都有per cpu cache

  // 根据前面定义的MC_HASH_ENTRIES常量,mask_cache是一个255个元素大小的哈希表,
  // 也就是说最多只能缓存255个flow,一般来说255也足够了吧。如果linux同时有255个
  // 以上的tcp连接不停频繁切换就会出现缓存不命中需要遍历做mask array的搜索了。
  // 这个255大小的“非开放链表式”hash表,对cpu缓存比较友好吧。而且看样子mask array
  // 数目应该是对应ovs里面配置的flow的条数的。如果一个table配置的flow条数不多,
  // 遍历一下也就是多做几次hash查找而已。
  //
  // MC_HASH_SEGS 应该是4,把skb_hash的4个字节的每个字节做一次查找,就是说在表
  // 里面探测了4个位置。
  /* Find the cache entry 'ce' to operate on. */
  for (seg = 0; seg < MC_HASH_SEGS; seg++) {
    int index = hash & (MC_HASH_ENTRIES - 1);
    struct mask_cache_entry *e;

e = &entries[index];
if (e->skb_hash == skb_hash) { // 找到这个linux flow应该使用哪个mask(rule)
flow = flow_lookup(tbl, ti, ma, key, n_mask_hit,
  &e->mask_index);
if (!flow)
e->skb_hash = 0;
return flow;
}

if (!ce || e->skb_hash < ce->skb_hash)
ce = e;  /* A better replacement cache candidate. */

hash >>= MC_HASH_SHIFT;
}

/* Cache miss, do full lookup. */
flow = flow_lookup(tbl, ti, ma, key, n_mask_hit, &ce->mask_index);
if (flow)
ce->skb_hash = skb_hash;

return flow;
}


/* Flow lookup does full lookup on flow table. It starts with
 * mask from index passed in *index.
 */
static struct sw_flow *flow_lookup(struct flow_table *tbl,
  struct table_instance *ti,
  const struct mask_array *ma,
  const struct sw_flow_key *key,
  u32 *n_mask_hit,
  u32 *index)
{
struct sw_flow_mask *mask;
struct sw_flow *flow;
int i;

if (*index < ma->max) {  // 快速路径 : 直接根据第1步cache命中的index找到mask,就可以直接到哈希表里面找flow了
mask = rcu_dereference_ovsl(ma->masks[*index]);
if (mask) {
flow = masked_flow_lookup(ti, key, mask, n_mask_hit);     // 第2步在哈希表里面找flow
if (flow)
return flow;
}
}

  // 慢路径: 前面的cache没有命中,只能遍历mask_array数组所有mask,每一个都查找一遍看看有匹配的没有
for (i = 0; i < ma->max; i++)  {

if (i == *index)
continue;

mask = rcu_dereference_ovsl(ma->masks[i]);
if (!mask)
continue;
    
    // 注意这个对每个mask的规则,都用mask 对 key做掩码之后才计算hash值,然后
    // 采用这个hash值去表里面找。
flow = masked_flow_lookup(ti, key, mask, n_mask_hit);  // 第2步在哈希表里面找flow
if (flow) { /* Found */
*index = i;     // 如果找到了匹配的flow,就把mask的index返回上次缓存起来。
return flow;
}
}

return NULL;
}


这个查找方法有点复杂,openvswith把它叫做"Megaflows"技术吧, 查找分为两步
第1步: 在 mask_array数组里面找到flow对应的mask,这里有一个简单的hash缓存的优化,可以避免顺序遍历数组搜索
第2步: 在 hash table里面找到flow,根据key + mask做完掩码之后才计算hash值来做哈希表查找。

ovs为什么分为两级的搜索,而不是每个linux flow 直接对应hash表里面的一项,那样只
做一次查找就可以了。听说一开始ovs是这么实现的,后来才改成先查找mask的方式,最近
才又引入了mask的hash查找加速。想了一下,如果每个linux的flow都建一个hash项的话,
确实数目可能比较多,导致hash表比较大,消耗内存多性能也不见的好。它搞成这种mask
归类匹配的话,也是和上层配置流的通配符wilcard支持相匹配的,归类之后需要创建的flow
的hash项就少很多了。  比如  “192.168.1.0/24 port=*” 一条flow就能匹配多个192.168.1.1
192.168.1.2 等多个ip的tcp连接了。如果直接使用linux flow对应的方式就需要255 * 65535
条hash项。肯定还是基于这种mask通配符的匹配更好了,基本ovs里面配置多少条flow就
只需要创建多少条 flow+mask的匹配项而已。

2017-07-23补充
[The Design and Implementation of Open vSwitch](https://benpfaff.org/papers/ovs.pdf) 这篇论文详细介绍了
openvswitch实现这个megaflow的设计思想,以及开发人员为什么要这么设计的,还做了详细的性能测试、缓存命中率、和
linux bridge的性能比较等等,感兴趣的可以看一下

往表中插入flow比较容易理解
/* Must be called with OVS mutex held. */
int ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
const struct sw_flow_mask *mask)
{
int err;

err = flow_mask_insert(table, flow, mask);   //  添加mask
if (err)
return err;
flow_key_insert(table, flow);            // 添加key对应hash项
if (ovs_identifier_is_ufid(&flow->id))
flow_ufid_insert(table, flow);        // 添加ufid对应的hash项

return 0;
}
```


ovs的resubmit这个action可以把包提交到另外table进行匹配时怎么实现的
==================================================================
```text
ovs应该只是openflow标准,可以有255个table,应该可以在多个table串联
出复杂的pipeline处理流程。

https://networkheresy.com/2014/11/13/accelerating-open-vswitch-to-ludicrous-speed/
这个megaflow技术确实大大提高了ovs的性能。
看这里的说法openvswitch的flow的创建是在用户空间的vswitchd里面创建的,我之前
一篇文章也概读了一下那个xlate的代码了。但table的跳转,还没有看到代码是怎么实现的。
感觉会不会是xlate在生成flow的action的时候,已经把所有的255个table合并在一起了。
上层推算的时候就完全可以把table 的区分去掉了。

xlate_ofpact_resubmit 
  xlate_table_action
    xlate_resubmit_resource_check

看看这几个函数代码,好像有点像是跟猜测的那样实现的,底层内核确实可以做到不区分table_id了
```

  评论这张
 
阅读(68)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017