[ovs-dev] dpif-netdev: Optimize the exact match lookup.

Message ID 1501223880-41630-1-git-send-email-xiangxia.m.yue@gmail.com
State Changes Requested
Delegated to: Ian Stokes
Headers show

Commit Message

Tonghao Zhang July 28, 2017, 6:38 a.m.
When inserting or updating (e.g. emc_insert) a flow to EMC,
we compare (e.g the hash and miniflow ) the netdev_flow_key.
If the key is matched, we will update it. If we didn’t find
the miniflow in the cache, the new flow will be stored.

But when looking up the flow, we compare the hash and miniflow
of key and make sure it is alive. If a flow is not alive but
the key is matched, we still will go to next loop. More important,
we can’t find the flow in the next loop (the flow is not alive in
the previous loop). This patch simply compares the miniflows of
the packets.

The topo is shown as below. VM01 sends TCP packets to VM02, and
OvS forwards packtets.

	VM01 -- OVS+DPDK VM02 -- VM03

With this patch, the TCP throughput between VMs is
5.37, 5.45, 5.48, 5.59, 5.65, 5.60 Gbs/sec avg: 5.52 Gbs/sec

up to:
5.64, 5.65, 5.66, 5.67, 5.62, 5.67 Gbs/sec avg: 5.65 Gbs/sec

(maybe ~2.3% performance improve, but it is hard to tell exactly
due to variance in the test results).

Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com>
---
 lib/dpif-netdev.c | 17 ++---------------
 1 file changed, 2 insertions(+), 15 deletions(-)

Comments

Ben Pfaff Oct. 30, 2017, 11:15 p.m. | #1
On Thu, Jul 27, 2017 at 11:38:00PM -0700, Tonghao Zhang wrote:
> When inserting or updating (e.g. emc_insert) a flow to EMC,
> we compare (e.g the hash and miniflow ) the netdev_flow_key.
> If the key is matched, we will update it. If we didn’t find
> the miniflow in the cache, the new flow will be stored.
> 
> But when looking up the flow, we compare the hash and miniflow
> of key and make sure it is alive. If a flow is not alive but
> the key is matched, we still will go to next loop. More important,
> we can’t find the flow in the next loop (the flow is not alive in
> the previous loop). This patch simply compares the miniflows of
> the packets.
> 
> The topo is shown as below. VM01 sends TCP packets to VM02, and
> OvS forwards packtets.
> 
> 	VM01 -- OVS+DPDK VM02 -- VM03
> 
> With this patch, the TCP throughput between VMs is
> 5.37, 5.45, 5.48, 5.59, 5.65, 5.60 Gbs/sec avg: 5.52 Gbs/sec
> 
> up to:
> 5.64, 5.65, 5.66, 5.67, 5.62, 5.67 Gbs/sec avg: 5.65 Gbs/sec
> 
> (maybe ~2.3% performance improve, but it is hard to tell exactly
> due to variance in the test results).
> 
> Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com>

Thank you for the patch.  I haven't spotted any reviews for this on the
mailing list.  I apologize for that--usually I expect to see a review
much more quickly than this.  I hope that someone who understands the
dpif-netdev code well will provide a review soon.
Bodireddy, Bhanuprakash Dec. 8, 2017, 2:16 p.m. | #2
Hi Tonghao,

>On Thu, Jul 27, 2017 at 11:38:00PM -0700, Tonghao Zhang wrote:

>> When inserting or updating (e.g. emc_insert) a flow to EMC, we compare

>> (e.g the hash and miniflow ) the netdev_flow_key.

>> If the key is matched, we will update it. If we didn’t find the

>> miniflow in the cache, the new flow will be stored.

>>

>> But when looking up the flow, we compare the hash and miniflow of key

>> and make sure it is alive. If a flow is not alive but the key is

>> matched, we still will go to next loop. More important, we can’t find

>> the flow in the next loop (the flow is not alive in the previous

>> loop). This patch simply compares the miniflows of the packets.

>>

>> The topo is shown as below. VM01 sends TCP packets to VM02, and OvS

>> forwards packtets.

>>

>> 	VM01 -- OVS+DPDK VM02 -- VM03

>>

>> With this patch, the TCP throughput between VMs is 5.37, 5.45, 5.48,

>> 5.59, 5.65, 5.60 Gbs/sec avg: 5.52 Gbs/sec

>>

>> up to:

>> 5.64, 5.65, 5.66, 5.67, 5.62, 5.67 Gbs/sec avg: 5.65 Gbs/sec

>>

>> (maybe ~2.3% performance improve, but it is hard to tell exactly due

>> to variance in the test results).

>>

>> Signed-off-by: Tonghao Zhang <xiangxia.m.yue@gmail.com>

>

>Thank you for the patch.  I haven't spotted any reviews for this on the mailing

>list.  I apologize for that--usually I expect to see a review much more quickly

>than this.  I hope that someone who understands the dpif-netdev code well

>will provide a review soon.


I reviewed and tested this patch and the performance improvement is marginal and varies a lot depending on traffic pattern.

In the original implementation, if the hashes match and the entry is alive in EMC then the Miniflows are compared using memcmp() and takes
Significant cycles.
With the change proposed in this patch, if the hash matches we would do the Miniflow comparison(takes significant cycles depending on key->len) and then go on to check if the entry is alive. In case the entry isn't available(With EMC saturated and packets hitting classifier) we probably would have wasted lot of cycles in this case doing the expensive memcmp().

What do you think?

- Bhanuprakash.

Patch

diff --git a/lib/dpif-netdev.c b/lib/dpif-netdev.c
index 47a9fa0..86a6073 100644
--- a/lib/dpif-netdev.c
+++ b/lib/dpif-netdev.c
@@ -1904,16 +1904,6 @@  netdev_flow_key_equal(const struct netdev_flow_key *a,
     return a->hash == b->hash && !memcmp(&a->mf, &b->mf, a->len);
 }
 
-/* Used to compare 'netdev_flow_key' in the exact match cache to a miniflow.
- * The maps are compared bitwise, so both 'key->mf' and 'mf' must have been
- * generated by miniflow_extract. */
-static inline bool
-netdev_flow_key_equal_mf(const struct netdev_flow_key *key,
-                         const struct miniflow *mf)
-{
-    return !memcmp(&key->mf, mf, key->len);
-}
-
 static inline void
 netdev_flow_key_clone(struct netdev_flow_key *dst,
                       const struct netdev_flow_key *src)
@@ -2088,12 +2078,9 @@  emc_lookup(struct emc_cache *cache, const struct netdev_flow_key *key)
     struct emc_entry *current_entry;
 
     EMC_FOR_EACH_POS_WITH_HASH(cache, current_entry, key->hash) {
-        if (current_entry->key.hash == key->hash
-            && emc_entry_alive(current_entry)
-            && netdev_flow_key_equal_mf(&current_entry->key, &key->mf)) {
-
+        if (netdev_flow_key_equal(&current_entry->key, key)) {
             /* We found the entry with the 'key->mf' miniflow */
-            return current_entry->flow;
+            return emc_entry_alive(current_entry) ? current_entry->flow : NULL;
         }
     }