openVswitch（OVS）源代碼的分析技巧（哈希桶結構體為例） · openVswitch（OVS）源代碼分析

##前言：個人認為學習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) 分析得比較匆促，若有不正確之處，望大家指正，共同學習！謝謝！！！