openVswitch（OVS）源代码的分析技巧（哈希桶结构体为例）
最后更新于：2022-04-01 07:42:33
##前言：
个人认为学习openVswitch源代码是比较困难的，因为该项目开发出来不久（当然了这是相对于其他开源项目），一些资料不完全，网上也比较少资料（一般都是说怎么使用，比如：怎么安装，怎么配置，以及一些命令等。对源码分析的资料比较少），如果遇到问题只有自己看源代码，分析源代码，然后各种假设，再带着假设去阅读分析源代码。而源代码中注释的也比较少（只有几部分函数和结构体有注释）。所以对源代码的分析是比较困难的。不像linux（UNIX）方面的分析，因为linux项目已经开放出来好久了，资料漫天都是，各种内核源代码分析，只要你有耐心什么内核源代码分析，内核源代码全注释，都有各种详细版本供你参考。而我在学习openVswitch源代码的时候也遇到个比较大的问题，困扰了我比较久的时间，我也查看了几个模块的源代码发现都解决不了（因为各个模块中意思不能统一），今天拿出来和大家一起来探讨下，也顺便分享下我分析源代码和处理问题的方法。
顺便说下，我原本是要顺着ovs_dp_process_received_packet（）函数处理流程来分析所有的流程源代码，但分析完流表查询，觉得那个问题还是得处理下，所以在这里插入一篇blog来处理下那个问题。在之后会继续分析upcall和流表使用，action动作等模块。
##问题：
话不多说，还是看问题吧。其实在系列blog中的第二篇[openVswitch（OVS）源代码分析之数据结构](http://blog.csdn.net/yuzhihui_no1/article/details/39188373)已经说过。就是下面的结构体成员字段有歧义：
~~~
// 哈希桶结构
struct flex_array {
// 共用体，第二个成员为占位符，为共用体大小
union {
// 对于这个结构体的成员数据含义，真是花了我不少时间来研究，发现有歧义，（到后期流表匹配时会详细分析）。现在就我认为最正确的理解来分析
struct {
int element_size; // 无疑这是数组元素的大小
int total_nr_elements; // 这是数组元素的总个数
int elems_per_part; // 这是每个part指针指向的空间能存储多少元素
u32 reciprocal_elems;
struct flex_array_part *parts[]; // 结构体指针数组，里面存放的是struct flex_array_part结构的指针
};
char padding[FLEX_ARRAY_BASE_SIZE];
};
};
// 其实struct flex_array_part *parts[];中的结构体只是一个数组而已
struct flex_array_part {
char elements[FLEX_ARRAY_PART_SIZE]; // 里面是一个页大小的字符数组
};
~~~
上面这个结构的分析还是引用下第二篇blog的原文吧：
“顺序分析下去，应该是分析哈希桶结构体了，因为这个结构体设计的实在是太巧妙了。所以应该仔细的分析下。
这是一个共用体，是个设计非常巧妙的共用体。因为共用体的特点是：整个共用体的大小是其中最大成员变量的大小。也就是说 共用体成员中某个最大的成员的大小就是共用体的大小。正是利用这一点特性，最后一个char padding[FLEX_ARRAY_BASE_SIZE]其实是没有用的，仅仅是起到一个占位符的作用了。让整个共用体的大小为FLEX_ARRAY_BASE_SIZE（即是一个页的大小：4096），那为什么要这么费劲心机去设计呢？是因为struct flex_array_part *parts[]; 这个结构，这个结构并不多见，因为在标准的c/c++代码中是无效的，只有在GNU下才是合法的。这个称为弹性数组，或者可变数组，和常规的数组不一样。这里这个弹性数组的大小是一个页大小减去前面几个整型成员变量后所剩的大小。”
##分析：
这是前面blog中分析得，下面跟着源代码来分析下这个结构体成员变量的含义。
因为对这个哈希桶结构体有疑问，那么就到这个哈希桶结构内存申请的函数中去找，因为申请函数中肯定会有给结构体赋值的代码，只要弄清楚给结构体成员变量赋什么值就可以知道这个成员变量大概是什么意思了。
第一步
哈希桶结构的内存申请函数struct flex_array *flex_array_alloc(int element_size, unsigned int total, gfp_t flags);
记得前面说过分析函数代码，除了看实现代码外，函数参数和返回值也是重要的线索.那么element_size和total究竟是什么意思呢？（gfp_t flags这个参数学内核的大概都看过，就算没看过也能猜到是什么，就是在内核中内存申请的一些方式）， 要查看element_size和total是什么意思，就要查到谁（哪个函数）调用了flex_array_alloc()函数。
第二步
于是在整个项目中进行搜索得，也可以理性的去分析下哪个函数会调用下面的flex_array申请函数，其实就是buckets内存申请函数（alloc_buckets）了；在该函数中有行代码为：buckets = flex_array_alloc(sizeof(struct hlist_head *),n_buckets, GFP_KERNEL);
至此已经找到了 element_size的含义了，即：哈希头指针的大小。那么就剩下total参数了。
第三步
继续往上个查找，看看哪个函数调用了alloc_buckets()函数，用搜索或者理性分析，哪个函数会调用buckets来申请函数，其实和上面类似，就是table内存申请函数（__flow_tbl_alloc）了。
在_flow_tbl_alloc()函数中有行调用代码为：table->buckets = alloc_buckets(new_size)；到这里还是没有查找到total究竟是什么意思，只知道是new_size传过来的。
第四步
不要放弃，继续往上查找调用函数中，也是类似的方法，整个文件去搜索flow_tbl_alloc（_flow_tbl_alloc是基础函数，被包装后为flow_tbl_alloc）看看哪个函数调用了它。
最后搜索发现在static int flush_flows(struct datapath *dp)函数有行调用代码：new_table = ovs_flow_tbl_alloc(TBL_MIN_BUCKETS);这里问题终于明了了，total就是TBL_MIN_BUCKETS，那么TBL_MIN_BUCKETS是什么意思呢？只能搜索了，结果会发现就是宏定义：#define TBL_MIN_BUCKETS 1024。到此参数的问题解决了。
第五步
上面是分析方法，总结下可以得出：参数element_size为sizeof(struct hlist_head*)（其实这里暗示了element_size就是指哈希头的大小，后面会有用）；参数total为1024，是从最开始宏定义过来的，这个参数倒推不出什么含义，只是个数值。
上面element_size和total的含义是有前面的源代码推到而来，而源代码自带的注释含义为，element_size：数组中单个元素的大小；total：应该被创建的元素总个数。
~~~
// 参数element_size：数组中单个元素大小，其实暗示了该数组存放了struct hlist_head
// 参数total：没有别的意思，就是每次创建是最小的元素总是，默认设置为1024
struct flex_array *flex_array_alloc(int element_size, unsigned int total,
gfp_t flags)
{
struct flex_array *ret;
int elems_per_part = 0;
int reciprocal_elems = 0;
int max_size = 0;
// 这里不懂为什么还要对element_size判空，因为源代码中已经写死了：sizeof(struct hlist_head)
// 这里很明显恒成立。个人猜测是为了说明如果数组元素为空，则不能执行下面的操作
if (element_size) {
// 下面的代码让我很疑惑了，elems_per_part按照变量名的意思：每个part数组元素中存储了多少个元素
// 根据赋值情况分析，后面的宏定义为：#define FLEX_ARRAY_ELEMENTS_PER_PART(size) (FLEX_ARRAY_PART_SIZE / size)
// 得：（页大小/ element_size）== 表示一个页（1024）中能存放多少哈希头
elems_per_part = FLEX_ARRAY_ELEMENTS_PER_PART(element_size);
reciprocal_elems = reciprocal_value(elems_per_part);
// max_size也让我疑惑，按照变量名来说应该是，数组中存放了最大的元素数
// 根据赋值情况来分析，先分析等号右边的宏定义：
// #define FLEX_ARRAY_NR_BASE_PTRS (FLEX_ARRAY_BASE_BYTES_LEFT / sizeof(struct flex_array_part *))
// offsetof()宏用来求一个成员在结构体 中的偏移量
// #define FLEX_ARRAY_BASE_BYTES_LEFT （FLEX_ARRAY_BASE_SIZE - offsetof(struct flex_array, parts))
// 所以前面的 FLEX_ARRAY_NR_BASE_PTRS 为桶结构中弹性数组的大小，即：可以存放多少个flex_array_part *
// 后面的elems_per_part为每个数组元素中能存放多少哈希头，所以max_size就是该结构中最多能存放的哈希头数
max_size = FLEX_ARRAY_NR_BASE_PTRS * elems_per_part;
}
/* max_size will end up 0 if element_size > PAGE_SIZE */
// 上面自带的注释意思为如果数组元素为一个页的大小，那么max_size将会趋近于0
if (total > max_size)
return NULL;
ret = kzalloc(sizeof(struct flex_array), flags);// 为数组分配内存空间
if (!ret)
return NULL;
// 下面一系列的代码就是为结构体成员变量赋值
ret->element_size = element_size;
ret->total_nr_elements = total;
ret->elems_per_part = elems_per_part;
ret->reciprocal_elems = reciprocal_elems;
if (elements_fit_in_base(ret) && !(flags & __GFP_ZERO))
memset(&ret->parts[0], FLEX_ARRAY_FREE,
FLEX_ARRAY_BASE_BYTES_LEFT);
return ret;
}
~~~
##总结：
其实从上面的源代码已经可以初步的看出flex_array结构体中的各个成员变量的大概含义了，现来初步总结下各个成员的含义：
~~~
struct {
int element_size; // 这是flex_array_part结构体存放的哈希头指针的大小
int total_nr_elements; // 这是所有flex_array_part结构体中的哈希头指针的总个数
int elems_per_part; // 这是每个part指针指向的空间能存储多少个哈希头指针
u32 reciprocal_elems;
struct flex_array_part *parts[]; // 结构体指针数组，里面存放的是struct flex_array_part结构的指针
};
~~~
##矛盾：
按照上面的分析结论，发现在static inline int elements_fit_in_base(struct flex_array *fa)函数中是不怎么好理解的。至少我开始是理解不了，下面请看下该函数的具体实现：
~~~
static inline int elements_fit_in_base(struct flex_array *fa)
{
// fa->element_size 根据上面的结论应该是哈希头的大小，flex_array_part结构体中存放的哈希头大小
// fa->total_nr_elements 根据上面的结论应该是所有哈希头的总数
// 那么data_size 就是所有存储哈希头的空间大小了，矛盾来了
int data_size = fa->element_size * fa->total_nr_elements;
// FLEX_ARRAY_BASE_BYTES_LEFT是什么意思呢？
// #define FLEX_ARRAY_BASE_BYTES_LEFT (FLEX_ARRAY_BASE_SIZE - offsetof(struct flex_array, parts))
// offsetof()宏用来求一个成员在结构体中的偏移量
// 所以所有存储哈希头空间的大小和 FLEX_ARRAY_BASE_BYTES_LEFT 比较是什么意思呢？我当时的判断就是element_size和total_nr_elements这两个成员变量理解错了。
if (data_size <= FLEX_ARRAY_BASE_BYTES_LEFT)
return 1;
return 0;
}
~~~
##扩展：
为了解决上面这个问题，我对flex_array.h和flex_array.c文件进行了反复的分析，做各种假设最后终于解决了。但是还存在一个问题就是flex_array_part结构体：
~~~
struct flex_array_part {
char elements[FLEX_ARRAY_PART_SIZE];
};
~~~
仔细的学者会发现这个flex_array_part结构体中就是一个页长大小的字符数组，注意是char型的字符数组，那怎么存放哈希头指针呢？这是个问题，我也正在研究，当然如果对于只是用来工作的，那么可以不必计较的这么仔细。
转载请注明作者和原文出处，原文地址：[http://blog.csdn.net/yuzhihui_no1/article/details/39558815#t2](http://blog.csdn.net/yuzhihui_no1/article/details/39558815#t2)
分析得比较匆促，若有不正确之处，望大家指正，共同学习！谢谢！！！