前面分析了openVswitch幾部分源代碼，對于openVswitch也有了個大概的理解，今天要分析得代碼將是整個openVswitch的重中之重。整個openVswitch的核心代碼在datapath文件中；而datapath文件中的核心代碼又在ovs_dp_process_received_packet(struct vport *p, struct sk_buff *skb);函數中；而在ovs_dp_process_received_packet(struct vport *p, struct sk_buff *skb);函數中的核心代碼又是流表查詢（流表匹配的）；有關于ovs_dp_process_received_packet(struct vport *p, struct sk_buff *skb);核心代碼的分析在前面的[openVswitch（OVS）源代碼分析之工作流程（數據包處理）](http://blog.csdn.net/yuzhihui_no1/article/details/39378195)中。今天要分析得就是其核心中的核心：流表的查詢（匹配流表項）源代碼。我分析源代碼一般是采用跟蹤的方法，一步步的往下面去分析，只會跟著主線走（主要函數調用），對其他的分支函數調用只作大概的說明，不會進入其實現函數去分析。由于流表的查詢設計到比較多的數據結構，所以建議對照著[openVswitch（OVS）源代碼分析之數據結構](http://blog.csdn.net/yuzhihui_no1/article/details/39188373)去分析，我自己對數據結構已經大概的分析了遍，可是分析流表查詢代碼時還是要時不時的倒回去看看以前的數據結構分析筆記。 注：這是我寫完全篇后補充的，我寫完后自己閱讀了下，發現如果就單純的看源代碼心里沒有個大概的輪廓，不是很好理解，再個最后面的那個圖，畫的不是很好（我也不知道怎么畫才能更好的表達整個意思，抱歉），所以覺得還是在這個位置（源代碼分析前）先來捋下框架（也可以先看完源碼分析再來看著框架總結，根據自己情況去學習吧）。上面已經說過了[openVswitch（OVS）源代碼分析之數據結構](http://blog.csdn.net/yuzhihui_no1/article/details/39188373)的重要性，現在把里面最后那幅圖拿來順著圖示來分析，會更好理解。（最后再來說下那幅圖是真的非常有用，那相當于openVswitch的整個框架圖了，如果你要分析源代碼，有了那圖絕對是事半功倍，希望閱讀源代碼的朋友重視起來，哈哈，絕不是黃婆賣瓜）  流表查詢框架（或者說理論）：從ovs_dp_process_received_packet(struct vport *p, struct sk_buff *skb)函數中開始調用函數查流表，怎么查呢？ 第一步、它會根據網橋上的流表結構體（table）中的mask_list成員來遍歷，這個mask_list成員是一條鏈表的頭結點，這條鏈表是由mask元素鏈接組成（里面的list是沒有數據的鏈表結構，作用就是負責鏈接多個mask結構，是mask的成員）；流表查詢函數開始就是循環遍歷這條鏈表，每遍歷到得到一個mask結構體，就調用函數進入第二步。 第二步、是操作key值，調用函數讓從數據包提取到的key值和第一步得到的mask中的key值，進行與操作，然后把結構存放到另外一個key值中（masked_key）。順序執行第三步。 第三步、把第二步中得到的那個與操作后的key值（masked_key），傳入?jhash2()算法函數中，該算法是經典的哈希算法，想深入了解可以自己查資料（不過都是些數學推理，感覺挺難的），linux內核中也多處使用到了這個算法函數。通過這個函數把key值（masked_key）轉換成hash關鍵字。 第四步、把第三步得到的hash值，傳入?find_bucket()函數中，在該函數中再通過jhash_1word()算法函數，把hash關鍵字再次哈希得到一個全新的hash關鍵字。這個函數和第三步的哈希算法函數類似，只是參數不同，多了一個word。經過兩個哈希算法函數的計算得到一個新的hash值。 第五步、?把第四步得到的hash關鍵字，傳入到flex_array_get()函數中，這個函數的作用就是找到對應的哈希頭位置。具體的請看上面的圖，流表結構（table）中有個buckets成員，該成員稱作為哈希桶，哈希桶里面存放的是成員字段和彈性數組parts[n]，而這個parts[n]數組里面存放的就是所要找的哈希頭指針，這個哈希頭指針指向了一個流表項鏈表（在圖中的最下面struct sw_flow），所以這個才是我們等下要匹配的流表項。（這個哈希桶到彈性數組這一段，我有點疑問，不是很清楚，在下一篇blog中會分析下這個疑問，大家看到如果和源代碼有出入，請按源代碼來分析），這一步就是根據hash關鍵字查找到流表項的鏈表頭指針。 第六步、由第五步得到的流表項鏈表頭指針，根據這個指針遍歷整個流表項節點元素（就是struct sw_flow結構體元素），每遍歷得到一個流表項sw_flow結構體元素，就把流表項中的mask成員和第一步遍歷得到的mask變量（忘記了可以重新回到第一步去看下）進行比較；比較完后還要讓流表項sw_flow結構體元素中的key值成員和第二步中得到的key值（masked_key）進行比較；只有當上面兩個比較都相等時，這個流表項才是我們要匹配查詢的流表項了。然后直接返回該流表項的地址。查詢完畢！！接下來分析源代碼了。 在ovs_dp_process_received_packet(struct vport *p, struct sk_buff *skb);函數中流表查詢調用代碼： ~~~ // ovs_flow_lookup()是流表查詢實現函數；參數rcu_dereference(dp->table)：網橋流表（不是流表項）； // 參數&key：數據包各層協議信息提取封裝的key地址;返回值flow：查詢到的或者說匹配到的流表項 flow = ovs_flow_lookup(rcu_dereference(dp->table), &key); ~~~ 這里要特別說明下：dp->table是流表，是結構體struct?flow_table的變量；而flow是流表項，是結構體struct?sw_flow的變量；我們平常習慣性說的查詢流表或者匹配流表，其實并不是說查詢或者匹配flow_table結構體的變量（在openVswitch中flow_table沒有鏈表，只有一個變量），而是struct sw_flow的結構體鏈表。所以確切的說應該是查詢和匹配流表項。這兩個結構是完全不同的，至于具體的是什么關系，有什么結構成員，可以查看下[openVswitch（OVS）源代碼分析之數據結構](http://blog.csdn.net/yuzhihui_no1/article/details/39188373)。如果不想看那么繁瑣的分析，也可以看下最后面的那張圖，可以大概的了解下他們的關系和區別。 ? ? ? 下面來著重的分析下ovs_flow_lookup()函數，主要是循環遍歷mask鏈表節點，和調用ovs_masked_flow_lookup()函數。 ~~~ // tbl是網橋結構中的table,key是包中提取的key的地址指針 struct sw_flow *ovs_flow_lookup(struct flow_table *tbl, const struct sw_flow_key *key) { struct sw_flow *flow = NULL;// 準備流表項，匹配如果匹配到流表項則返回這個變量 struct sw_flow_mask *mask;// 了解mask結構就非常好理解mask的作用 // 下面是從網橋上的table結構中頭mask_list指針開始遍歷mask鏈表， // 依次調用函數去查詢流表，如果得到流表項則退出循環 list_for_each_entry_rcu(mask, tbl->mask_list, list) { // 流表查詢函數（其實是key的匹配），參數分別是：網橋的table，和數據包的key，以及網橋上的mask節點 flow = ovs_masked_flow_lookup(tbl, key, mask); if (flow) /* Found */ break; } return flow; } ~~~ 接下來是flow = ovs_masked_flow_lookup(tbl, key, mask);函數的分析，該函數就是最后流表的比較了和查詢了。主要實現功能是對key值得操作，和哈希得到哈希值，然后根據哈希值查找哈希頭結點，最后在頭結點鏈表中遍歷流表項，匹配流表項。 ~~~ // table 是網橋結構體中成員，flow_key是數據包提取到的key值，mask是table中的sw_flow_mask結構體鏈表節點 static struct sw_flow *ovs_masked_flow_lookup(struct flow_table *table, const struct sw_flow_key *flow_key, struct sw_flow_mask *mask) { // 要返回的流表項指針，其實這里就可以斷定后面如果查詢成功的話，返回的是存儲flow的動態申請好的內存空間地址， // 因為這幾個函數都是返回flow的地址的，如果不是動態申請的地址，返回的就是局部變量，那后面使用時就是非法的了。 // 它這樣把地址一層一層的返回；若查詢失敗返回NULL。因為這里不涉及到對流表的修改，只是查詢而已，如果為了防止流表被更改， // 也可以自己動態的申請個flow空間，存儲查詢到的flow結構。 struct sw_flow *flow; struct hlist_head *head;// 哈希表頭結點 // 下面是mask結點結構體中成員變量：struct sw_flow_key_range range; // 而該結構體struct sw_flow_key_range有兩個成員，分別為start和end // 這兩個成員是確定key值要匹配的范圍，因為key值中的數據并不是全部都要進程匹配的 int key_start = mask->range.start; int key_len = mask->range.end; u32 hash; struct sw_flow_key masked_key;// 用來得到與操作后的結果key值 // 下面調用的ovs_flow_key_mask()函數是讓flow_key(最開始的數據包中提取到的key值)，和mask中的key進行與操作(操作范圍是 // 在mask的key中mask->range->start開始，到mask->range->end結束) 最后把與操作后的key存放在masked_key中 ovs_flow_key_mask(&masked_key, flow_key, mask); // 通過操作與得到的key，然后再通過jhash2算法得到個hash值，其操作范圍依然是 range->start 到range->end // 因為這個key只有在這段范圍中數據時有效的，對于匹配操作來說。返回個哈希值 hash = ovs_flow_hash(&masked_key, key_start, key_len); // 調用find_bucket通過hash值查找hash所在的哈希頭，為什么要查詢鏈表頭節點呢? // 因為openVswitch中有多條流表項鏈表，所以要先查找出要匹配的流表在哪個鏈表中，然后再去遍歷該鏈表 head = find_bucket(table, hash); // 重點戲來了，下面是遍歷流表項節點。由開始獲取到哈希鏈表頭節點，依次遍歷這個哈希鏈表中的節點元素， // 把每一個節點元素都進行比較操作，如果成功，則表示查詢成功，否則查詢失敗。 hlist_for_each_entry_rcu(flow, head, hash_node[table->node_ver]) { // 下面都是比較操作了，如果成功則返回對應的flow if (flow->mask == mask && __flow_cmp_key(flow, &masked_key, key_start, key_len)) // 上面的flow是流表項，masked_key是與操作后的key值， return flow; } return NULL; }? ?? ~~~ 分析到上面主線部分其實已經分析完了，但其中有幾個函數調用比較重要，不得不再來補充分析下。也是按順序依次分析下來， 第一個調用函數：ovs_flow_key_mask(&masked_key, flow_key, mask);分析。這個函數主要功能是讓數據包中提取到的key值和mask鏈表節點中key與操作，然后把結果存儲到masked_key中。 ~~~ // 要分析一個函數除了看實現代碼外，分析傳入的參數和返回的數據類型也是非常重要和有效的 // 傳入函數的參數要到調用該函數的地方去查找，返回值得類型可以在本函數內看到。 // 上面調用函數：ovs_flow_key_mask(&masked_key, flow_key, mask); // 所以dst是要存儲結構的key值變量地址，src是最開始數據包中提取的key值，mask是table中mask鏈表節點元素 void ovs_flow_key_mask(struct sw_flow_key *dst, const struct sw_flow_key *src, const struct sw_flow_mask *mask) { u8 *m = (u8 *)&mask->key + mask->range.start; u8 *s = (u8 *)src + mask->range.start; u8 *d = (u8 *)dst + mask->range.start; int i; memset(dst, 0, sizeof(*dst)); // ovs_sw_flow_mask_size_roundup()是求出range->end - range->start長度 // 循環讓最開始的key和mask中的key值進行與操作，放到目標key中 for (i = 0; i < ovs_sw_flow_mask_size_roundup(mask); i++) { *d = *s & *m; d++, s++, m++; } } ~~~ 第二個調用函數：hash = ovs_flow_hash(&masked_key, key_start, key_len);這個沒什么好分析得，只是函數里面調用了個jhash2算法來獲取一個哈希值。所以這個函數的整體功能是：由數據包中提取到的key值和每個mask節點中的key進行與操作后得到的有效masked_key，和key值的有效數據開始位置及其長度，通過jhash2算法得到一個hash值。 第三個調用函數：head = find_bucket(table, hash);分析，該函數實現的主要功能是對hash值調用jhash_1word()函數再次對hash進行哈希，最后遍歷哈希桶，查找對應的哈希鏈表頭節點。 ~~~ // 參數table：網橋上的流表；參數hash：由上面調用函數獲取到哈希值；返回 static struct hlist_head *find_bucket(struct flow_table *table, u32 hash) { // 由開始的hash值再和table結構中自帶的哈希算法種子通過jhash_1word()算法，再次hash得到哈希值 // 不知道為什么要哈希兩次，我個人猜測是因為第一次哈希的值，會有碰撞沖突。所以只能二次哈希來解決碰撞沖突 hash = jhash_1word(hash, table->hash_seed); // 傳入的參數數:buckets桶指針，哈希值hash(相當于關鍵字)n_buckets表示有多少個桶(其實相當于有多少個hlist頭結點) // hash&(table->n_buckets-1)表示根據hash關鍵字查找到第幾個桶，其實相當于求模算法，找出關鍵字hash應該存放在哪個桶里面 return flex_array_get(table->buckets, (hash & (table->n_buckets - 1))); } ~~~ 第四個調用函數：?__flow_cmp_key(flow, &masked_key, key_start, key_len));分析，該函數實現的功能是對流表中的key值和與操作后的key值（masked_key）進行匹配。 ~~~ // 參數flow：流表項鏈表節點元素；參數key：數據包key值和mask鏈表節點key值與操作后的key值； // 參數key_start：key值得有效開始位置；參數key_len：key值得有效長度 static bool __flow_cmp_key(const struct sw_flow *flow, const struct sw_flow_key *key, int key_start, int key_len) { return __cmp_key(&flow->key, key, key_start, key_len); } //用數據包中提取到的key和mask鏈表節點中的key操作后的key值（masked_key）和流表項里面的key比較 static bool __cmp_key(const struct sw_flow_key *key1, const struct sw_flow_key *key2, int key_start, int key_len) { return !memcmp((u8 *)key1 + key_start, (u8 *)key2 + key_start, (key_len - key_start)); } ~~~ 上面就是整個流表的匹配實現源代碼的分析，現在來整理下其流程，如下圖所示（圖有點丑見諒）：  到此流表查詢就就算結束了，分析了遍自己也清晰了遍。 轉載請注明作者和原文出處，原文地址：[http://blog.csdn.net/yuzhihui_no1/article/details/39504139](http://blog.csdn.net/yuzhihui_no1/article/details/39504139) 分析得比較匆促，若有不正確之處，望大家指正，共同學習！謝謝！！！