記得Pascal之父、結構化程序設計的先驅Niklaus Wirth最著名的一本書，書名叫作《算法 + 數據結構 = 程序》。還有位傳奇的軟件工程師Frederick P. Brooks曾經說過：“給我看你的數據”。因此可見數據結構對于一個程序來說是多么的重要，如果你不了解程序中的數據結構，你根本就無法去理解整個程序的工作流程。所以在分析openVswitch（OVS）源代碼之前先來了解下openVswitch中一些重要的數據結構，這將對你分析后面的源代碼起著至關重要的作用。 按照數據包的流向來分析下涉及到一些重要的數據結構。 第一、vport端口模塊中涉及到的一些數據結構： ~~~ // 這是表示網橋中各個端口結構體 struct vport { struct rcu_head rcu; // 一種鎖機制 struct datapath *dp; // 網橋結構體指針，表示該端口是屬于哪個網橋的 u32 upcall_portid; // Netlink端口收到的數據包時使用的端口id u16 port_no; // 端口號，唯一標識該端口 // 因為一個網橋上有多個端口，而這些端口都是用哈希鏈表來存儲的， // 所以這是鏈表元素（里面沒有數據，只有next和prev前驅后繼指針，數據部分就是vport結構體中的其他成員） struct hlist_node hash_node; struct hlist_node dp_hash_node; // 這是網橋的哈希鏈表元素 const struct vport_ops *ops; // 這是端口結構體的操作函數指針結構體，結構體里面存放了很多操作函數的函數指針 struct pcpu_tstats __percpu *percpu_stats;// vport指向每個cpu的統計數據使用和維護 spinlock_t stats_lock; // 自旋鎖，防止異步操作，保護下面的兩個成員 struct vport_err_stats err_stats; // 錯誤狀態（錯誤標識）指出錯誤vport使用和維護的統計數字 struct ovs_vport_stats offset_stats; // 添加到實際統計數據,部分原因是為了兼容 }; // 端口參數，當創建一個新的vport端口是要傳入的參數 struct vport_parms { const char *name; // 新端口的名字 enum ovs_vport_type type; // 新端口的類型（端口不僅僅只有一種類型，后面會分析到） struct nlattr *options; // 這個沒怎么用到過，好像是從Netlink消息中得到的OVS_VPORT_ATTR_OPTIONS屬性 /* For ovs_vport_alloc(). */ struct datapath *dp; // 新的端口屬于哪個網橋的 u16 port_no; // 新端口的端口號 u32 upcall_portid; // 和Netlink通信時使用的端口id }; // 這是端口vport操作函數的函數指針結構體，是操作函數的集合，里面存放了所有有關vport操作函數的函數指針 struct vport_ops { enum ovs_vport_type type; // 端口的類型 u32 flags; // 標識符 // vport端口模塊的初始化加載和卸載函數 int (*init)(void); // 加載模塊函數，不成功則over void (*exit)(void); // 卸載端口模塊函數 // 新vport端口的創建函數和銷毀端口的函數 struct vport *(*create)(const struct vport_parms *); // 根據指定的參數配置創建個新的vport，成功返回新端口指針 void (*destroy)(struct vport *); // 銷毀端口函數 // 得到和設置option成員函數 int (*set_options)(struct vport *, struct nlattr *); int (*get_options)(const struct vport *, struct sk_buff *); // 得到端口名稱和配置以及發送數據包函數 const char *(*get_name)(const struct vport *); // 獲取指定端口的名稱 void (*get_config)(const struct vport *, void *);// 獲取指定端口的配置信息 int (*get_ifindex)(const struct vport *);// 獲取系統接口和設備間的指數 int (*send)(struct vport *, struct sk_buff *); // 發送數據包到設備上 }; // 端口vport的類型，枚舉類型存儲 enum ovs_vport_type{ OVS_VPORT_TYPE_UNSPEC, OVS_VPORT_TYPE_NETDEV, OVS_VPORT_TYPE_INTERNAL, OVS_VPORT_TYPE_GRE, OVS_VPORT_TYPE_VXLAN, OVS_VPORT_TYPE_GRE64 = 104, OVS_VPORT_TYPE_LISP = 105, _OVS_VPORT_TYPE_MAX }; ~~~ 第二、網橋模塊datapath中涉及到的一些數據結構： ~~~ // 網橋結構體 struct datapath { struct rcu_head rcu; // RCU調延遲破壞。 struct list_head list_node; // 網橋哈希鏈表元素，里面只有next和prev前驅后繼指針，數據時該結構體其他成員 /* Flow table. */ struct flow_table __rcu *table;// 這是哈希流表，里面包含了哈希桶的地址指針。該哈希表受_rcu機制保護 /* Switch ports. */ struct hlist_head *ports;// 一個網橋有多個端口，這些端口都是用哈希鏈表來鏈接的 /* Stats. */ struct dp_stats_percpu __percpu *stats_percpu; #ifdef CONFIG_NET_NS /* Network namespace ref. */ struct net *net; #endif }; ~~~ 其實上面的網橋結構也表示了整個openVswitch（OVS）的結構，如果能捋順這些結構的關系，那就對分析openVswitch源代碼有很多幫助，下面來看下這些結構的關系圖：  第三、流表模塊flow中涉及到的一些數據結構： ~~~ // 可以說這是openVswitch中最重要的結構體了（個人認為） // 這是key值，主要是提取數據包中協議相關信息，這是后期要進行流表匹配的關鍵結構 struct sw_flow_key { // 這是隧道相關的變量 struct ovs_key_ipv4_tunnel tun_key; /* Encapsulating tunnel key. */ struct { // 包的優先級 u32 priority; // 包的優先級 u32 skb_mark; // 包的mark值 u16 in_port; // 包進入的端口號 } phy; // 這是包的物理層信息結構體提取到的 struct { u8 src[ETH_ALEN]; // 源mac地址 u8 dst[ETH_ALEN]; // 目的mac地址 __be16 tci; // 這好像是局域網組號 __be16 type; // 包的類型，即：是IP包還是ARP包 } eth; // 這是包的二層幀頭信息結構體提取到的 struct { u8 proto; // 協議類型 TCP：6；UDP：17；ARP類型用低8位表示 u8 tos; // 服務類型 u8 ttl; // 生存時間，經過多少跳路由 u8 frag; // 一種OVS中特有的OVS_FRAG_TYPE_*. } ip; // 這是包的三層IP頭信息結構體提取到的 // 下面是共用體，有IPV4和IPV6兩個結構，為了后期使用IPV6適應 union { struct { struct { __be32 src; // 源IP地址 __be32 dst; // 目標IP地址 } addr; // IP中地址信息 // 這又是個共用體，有ARP包和TCP包（包含UDP）兩種 union { struct { __be16 src; // 源端口，應用層發送數據的端口 __be16 dst; // 目的端口，也是指應用層傳輸數據端口 } tp; // TCP（包含UDP）地址提取 struct { u8 sha[ETH_ALEN]; // ARP頭中源Mac地址 u8 tha[ETH_ALEN]; // ARP頭中目的Mac地址 } arp;ARP頭結構地址提取 }; } ipv4; // 下面是IPV6的相關信息，基本和IPV4類似，這里不講 struct { struct { struct in6_addr src; /* IPv6 source address. */ struct in6_addr dst; /* IPv6 destination address. */ } addr; __be32 label; /* IPv6 flow label. */ struct { __be16 src; /* TCP/UDP source port. */ __be16 dst; /* TCP/UDP destination port. */ } tp; struct { struct in6_addr target; /* ND target address. */ u8 sll[ETH_ALEN]; /* ND source link layer address. */ u8 tll[ETH_ALEN]; /* ND target link layer address. */ } nd; } ipv6; }; }; ~~~ ? ? ? 接下來要分析的數據結構是在網橋結構中涉及的的：struct flow_table __rcu *table; ~~~ //流表 struct flow_table { struct flex_array *buckets; //哈希桶地址指針 unsigned int count, n_buckets; // 哈希桶個數 struct rcu_head rcu; // rcu包含機制 struct list_head *mask_list; // struct sw_flow_mask鏈表頭指針 int node_ver; u32 hash_seed; //哈希算法需要的種子，后期匹配時要用到 bool keep_flows; //是否保留流表項 }; ~~~ 順序分析下去，應該是分析哈希桶結構體了，因為這個結構體設計的實在是太巧妙了。所以應該仔細的分析下。 這是一個共用體，是個設計非常巧妙的共用體。因為共用體的特點是：整個共用體的大小是其中最大成員變量的大小。也就是說?共用體成員中某個最大的成員的大小就是共用體的大小。正是利用這一點特性，最后一個char padding[FLEX_ARRAY_BASE_SIZE]其實是沒有用的，僅僅是起到一個占位符的作用了。讓整個共用體的大小為FLEX_ARRAY_BASE_SIZE（即是一個頁的大小：4096），那為什么要這么費勁心機去設計呢？是因為struct flex_array_part *parts[]; 這個結構，這個結構并不多見，因為在標準的c/c++代碼中是無效的，只有在GNU下才是合法的。這個稱為彈性數組，或者可變數組，和常規的數組不一樣。這里這個彈性數組的大小是一個頁大小減去前面幾個整型成員變量后所剩的大小。 ~~~ // 哈希桶結構 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結構的指針 }; /* * This little trick makes sure that * sizeof(flex_array) == PAGE_SIZE */ char padding[FLEX_ARRAY_BASE_SIZE]; }; }; // 其實struct flex_array_part *parts[];中的結構體只是一個數組而已 struct flex_array_part { char elements[FLEX_ARRAY_PART_SIZE]; // 里面是一個頁大小的字符數組 }; // 上面的字符數組中存放的就是流表項頭指針，流表項也是用雙鏈表鏈接而成的 //流表項結構體 struct sw_flow { struct rcu_head rcu; // rcu保護機制 struct hlist_node hash_node[2]; // 兩個節點指針，用來鏈接作用，前驅后繼指針 u32 hash; // hash值 struct sw_flow_key key; // 流表中的key值 struct sw_flow_key unmasked_key; // 也是流表中的key struct sw_flow_mask *mask; // 要匹配的mask結構體 struct sw_flow_actions __rcu *sf_acts; // 相應的action動作 spinlock_t lock; // 保護機制自旋鎖 unsigned long used; // 最后使用的時間 u64 packet_count; // 匹配過的數據包數量 u64 byte_count; // 匹配字節長度 u8 tcp_flags; // TCP標識 }; ~~~ 順序下來，應該輪到分析mask結構體鏈表了： ~~~ // 這個mask比較簡單，就幾個關鍵成員 struct sw_flow_mask { int ref_count; struct rcu_head rcu; struct list_head list;// mask鏈表元素，因為mask結構是個雙鏈表結構體 struct sw_flow_key_range range;// 操作范圍結構體，因為key值中有些數據時不要用來匹配的 struct sw_flow_key key;// 要和數據包操作的key，將要被用來匹配的key值 }; // key的匹配范圍，因為key值中有一部分的數據時不用匹配的 struct sw_flow_key_range { size_t start; // key值匹配數據開始部分 size_t end; // key值匹配數據結束部分 }; ~~~ 下面是整個openVswitch中數據結構所構成的圖示，也是整個openVswitch中主要結構：  轉載請注明原文出處，原文地址是：[http://blog.csdn.net/yuzhihui_no1/article/details/39188373](http://blog.csdn.net/yuzhihui_no1/article/details/39188373) ? ?? 如有不正確之處，望大家指正！謝謝！！！