Open vSwitchのソースコードを読む(3) Kernel ModuleのFlow Table

2013-05-16 by Daisuke Kotani

前回はKernel moduleのパケットの入力から出力までの流れを追いました。今回はflow tableに関する処理を見ていきます。主な対象はdatapath/flow.h、datapath/flow.cです。

flow関連の構造体

flow関連と思われる構造体(flow_table, sw_flow, sw_flow_key, sw_flow_actions)がdatapath/flow.hにあります。ちょっと長いですが引用します。 struct flow tableはflow tableの本体、struct sw_flowはflow tableの1エントリ、struct sw_flow_keyはflow tableの1エントリのキー、struct sw_flow_actionsはキーに一致したパケットに対する処理を格納しておくものです。

struct sw_flow_actions {
    struct rcu_head rcu;
    u32 actions_len;
    struct nlattr actions[];
};

struct sw_flow_key {
    struct ovs_key_ipv4_tunnel tun_key;  /* Encapsulating tunnel key. */
    struct {
        u32    priority;    /* Packet QoS priority. */
        u32    skb_mark;    /* SKB mark. */
        u16    in_port;    /* Input switch port (or DP_MAX_PORTS). */
    } phy;
    struct {
        u8     src[ETH_ALEN];    /* Ethernet source address. */
        u8     dst[ETH_ALEN];    /* Ethernet destination address. */
        __be16 tci;        /* 0 if no VLAN, VLAN_TAG_PRESENT set otherwise. */
        __be16 type;        /* Ethernet frame type. */
    } eth;
    struct {
        u8     proto;        /* IP protocol or lower 8 bits of ARP opcode. */
        u8     tos;        /* IP ToS. */
        u8     ttl;        /* IP TTL/hop limit. */
        u8     frag;        /* One of OVS_FRAG_TYPE_*. */
    } ip;
    union {
        struct {
            struct {
                __be32 src;    /* IP source address. */
                __be32 dst;    /* IP destination address. */
            } addr;
            union {
                struct {
                    __be16 src;        /* TCP/UDP source port. */
                    __be16 dst;        /* TCP/UDP destination port. */
                } tp;
                struct {
                    u8 sha[ETH_ALEN];    /* ARP source hardware address. */
                    u8 tha[ETH_ALEN];    /* ARP target hardware address. */
                } arp;
            };
        } 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 sw_flow {
    struct rcu_head rcu;
    struct hlist_node hash_node[2];
    u32 hash;

    struct sw_flow_key key;
    struct sw_flow_actions __rcu *sf_acts;

    spinlock_t lock;    /* Lock for values below. */
    unsigned long used;    /* Last used time (in jiffies). */
    u64 packet_count;    /* Number of packets matched. */
    u64 byte_count;        /* Number of bytes matched. */
    u8 tcp_flags;        /* Union of seen TCP flags. */
};

struct flow_table {
    struct flex_array *buckets;
    unsigned int count, n_buckets;
    struct rcu_head rcu;
    int node_ver;
    u32 hash_seed;
    bool keep_flows;
};

struct sw_flow_keyはTCP/UDPのポートまで持っているようです。 struct sw_flowの時間に関する情報はlast used timeのみで、timeoutみたいなものはないですね。これらを頭の隅に入れておいて、flow tableに関する処理を読みます。

flow keyの抽出

パケットからflow keyを作る処理は、datapath/flow.cの616行目付近にあるovs_flow_extract関数で行われています。パケットをパースして、sw_flow_key構造体のメンバに値を代入しています。

int ovs_flow_extract(struct sk_buff *skb, u16 in_port, struct sw_flow_key *key,
         int *key_lenp)
{
    int error = 0;
    int key_len = SW_FLOW_KEY_OFFSET(eth);
    struct ethhdr *eth;

    （とっても長いので略）
}

flow tableの検索

flow tableの検索はovs_flow_tbl_lookup関数です。datapath/flow.cの796行目付近にあります。flow tableはhash tableのようで、ハッシュ値を求めて(ovs_flow_hash)、そのハッシュ値に該当するbucketを取ってきてその中の要素から一致するものを検索する、ということをしています。つまり完全一致検索しかしていないってことです。

struct sw_flow *ovs_flow_tbl_lookup(struct flow_table *table,
                struct sw_flow_key *key, int key_len)
{
    struct sw_flow *flow;
    struct hlist_node *n;
    struct hlist_head *head;
    u8 *_key;
    int key_start;
    u32 hash;

    key_start = flow_key_start(key);
    hash = ovs_flow_hash(key, key_start, key_len);

    _key = (u8 *) key + key_start;
    head = find_bucket(table, hash);
    hlist_for_each_entry_rcu(flow, n, head, hash_node[table->node_ver]) {

        if (flow->hash == hash &&
            !memcmp((u8 *)&flow->key + key_start, _key, key_len - key_start)) {
            return flow;
        }
    }
    return NULL;
}

ワイルドカードはどうしてるんでしょう・・・という疑問はuserlandのovs-vswitchdを読んだ時に解決されそうです。

flow tableのエントリの追加

flow tableにエントリを追加する時に呼ばれるのは、ovs_flow_tbl_insert関数（datapath/flow.cの821行目付近）です。この関数の引数にはflow keyのポインタがついていて、このポインタが指すflow keyには既に値が代入されていることが想定されています。

void ovs_flow_tbl_insert(struct flow_table *table, struct sw_flow *flow,
             struct sw_flow_key *key, int key_len)
{
    flow->hash = ovs_flow_hash(key, flow_key_start(key), key_len);
    memcpy(&flow->key, key, sizeof(flow->key));
    __flow_tbl_insert(table, flow);
}

さらに__flow_tbl_insert関数を追います。

static void __flow_tbl_insert(struct flow_table *table, struct sw_flow *flow)
{
    struct hlist_head *head;
    head = find_bucket(table, flow->hash);
    hlist_add_head_rcu(&flow->hash_node[table->node_ver], head);
    table->count++;
}

ハッシュ値を計算して、hash tableにエントリを1つ追加しているだけでした。

flow tableのエントリの削除

flow tableからエントリを削除するのはovs_flow_tbl_remove関数です。datapath/flow.cの829行目付近にあります。

void ovs_flow_tbl_remove(struct flow_table *table, struct sw_flow *flow)
{
    hlist_del_rcu(&flow->hash_node[table->node_ver]);
    table->count--;
    BUG_ON(table->count < 0);
}

hash tableからエントリを削除しているだけですね。

次回の予定

datapathの処理の流れは一通り分かったとして、次からはuserlandのプロセス(ovs-vswitchd)を読んでいくつもりです。

Links
About me