[ovs-discuss] conn_key_hash change hash arithmetic

liucheng (J) liucheng11 at huawei.com
Fri Dec 15 03:27:05 UTC 2017


Thanks for your reply. And my reply as below.

发件人: Darrell Ball [mailto:dball at vmware.com]
发送时间: 2017年12月15日 1:56
收件人: liucheng (J); ovs-discuss at openvswitch.org
主题: Re: [ovs-discuss] conn_key_hash change hash arithmetic



From: <ovs-discuss-bounces at openvswitch.org<mailto:ovs-discuss-bounces at openvswitch.org>> on behalf of "liucheng (J)" <liucheng11 at huawei.com<mailto:liucheng11 at huawei.com>>
Date: Wednesday, December 13, 2017 at 9:04 AM
To: "ovs-discuss at openvswitch.org<mailto:ovs-discuss at openvswitch.org>" <ovs-discuss at openvswitch.org<mailto:ovs-discuss at openvswitch.org>>
Subject: [ovs-discuss] conn_key_hash change hash arithmetic

>> Hello all,
>> I run a test with the user conntrack. And I found if I only change the udp port, then the hash with function “conn_key_hash” is not balance.

>> [Darrell] You are changing src and dst UDP ports; what algorithm is used to select the ports ?

[liucheng] UDP src and dst port increase from 1024 to 65530. Using tesgine(a packet transmitter) send the packets.


>> I change the hmap num(ct->buckets) to 4096

>> [Darrell] I assume you refer to CONNTRACK_BUCKETS ?

[liucheng] Yes, CONNTRACK_BUCKETS is 4096.

>> and ct->n_conn_limit to 30,000,000.

>> [Darrell] That is a large number for only varying the L4 ports; don’t you think ?
>>                 Do you think this represents a common use case or connection distribution?

[liucheng] Yes. This is not a common application scenarios.But I try to change the ip from 192.168.0.1 to 192.168.0.10, and this problem is still exist.


>> And I print the num of the nodes contained in the hmap’s bucket.
>> As an example, a result looks like below. Most bucket is empty, and some bucket contain hundreds of nodes;
>> ~~~~~~~~~~~~~~~~~hmap 4095 count 4310 mask 4095~~~~~~~~~~~~~~~
>> buket 488 content 367 node
>> buket 1077 content 514 node
>> buket 1118 content 281 node
>> buket 1261 content 423 node
>> buket 1280 content 268 node
>> buket 1603 content 319 node
>> buket 1724 content 352 node
>> buket 2676 content 155 node
>> buket 2993 content 471 node
>> buket 3028 content 325 node
>> buket 3836 content 355 node
>> buket 4060 content 480 node

>> [Darrell] I assume you are referring to ct->buckets; i.e. first level buckets ?

[liucheng] I mean ctb->connections’s buckets. As it is a hmap, and has “struct hmap_node **buckets”. It has “mask + 1 “ buckets. i.e. buckets[488] contain 367 nodes. As code is below:
    for (i = 0; i < CONNTRACK_BUCKETS; i++) {
        struct conntrack_bucket *ctb = &ct->buckets[i];
        struct conn *conn;
        uint64_t count;

        ct_lock_lock(&ctb->lock);
        ds_put_format(&reply, "~~~~~~~~~~~~~~~~~hmap %d count %lu mask %lu~~~~~~~~~~~~~~~\n",
            i, hmap_count(&ctb->connections), ctb->connections.mask);
        for (j = 0; j <= ctb->connections.mask; j++) {
            count = 0;
            HMAP_FOR_EACH_IN_BUCKET(conn, node, j, &ctb->connections) {
                count++;
            }
            ds_put_format(&reply, "buket %d content %lu node\n", j, count);
        }

        ct_lock_unlock(&ctb->lock);
    }

>> Then I change the code in conn_key_hash as the patch. And test result is the max nodes in one bucket is 12.
>> The num of the bucket contained only one node is 5000542.
>> The num of the bucket contained only two node is 4337097.
>> The num of the bucket contained only three node is 2588535.
>> The num of the bucket contained only four node is 1196063.
>> The num of the bucket contained only five node is 460865.
>> The num of the bucket contained only six node is 155936.
>> The num of the bucket contained only seven node is 48727.
>> Most buckets contain few nodes.

>>  [Darrell] I am assuming you are referring to ct->buckets, still ?
>>                 1 of 4096 first level buckets ?

[liucheng] As above say, there is 4096(CONNTRACK_BUCKETS) hmap(), echo hmap mask is 4096. So I total have 16,000,000 buckets in all the hmap. And I have 5000542 buckets which has only one node(struct conn *conn).


diff --git a/lib/conntrack.c b/lib/conntrack.c
index 6d078f5..3edf809 100644
--- a/lib/conntrack.c
+++ b/lib/conntrack.c
@@ -2034,7 +2034,7 @@ conn_key_hash(const struct conn_key *key, uint32_t basis)
     hdst = ct_endpoint_hash_add(hdst, &key->dst);

     /* Even if source and destination are swapped the hash will be the same. */
-    hash = hsrc ^ hdst;
+    hash = hsrc + hdst;

     /* Hash the rest of the key(L3 and L4 types and zone). */
     hash = hash_words((uint32_t *) (&key->dst + 1),

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-discuss/attachments/20171215/a8675bd9/attachment-0001.html>


More information about the discuss mailing list