Re: [ovs-dev] [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
Thanks for the comments, please see my reply inlined. I made all the changes
you suggested and included in v5 which I will send out soon.
>> diff --git a/lib/cmap.c b/lib/cmap.c
>> index 07719a8..db1c806 100644
>> --- a/lib/cmap.c
>> +++ b/lib/cmap.c
>> @@ -373,6 +373,79 @@ cmap_find(const struct cmap *cmap, uint32_t hash)
>> hash);
>> }
>>
>> +/* Find a node by the index of the entry of cmap. For example, index 7
>> +means
>> + * the second bucket and the third item.
>> + * Notice that it is not protected by the optimistic lock (versioning)
>> +because
>> + * of performance reasons. Currently it is only used by the datapath DFC
>> cache.
>> + *
>> + * Return node for the entry of index or NULL if the index beyond
>> +boundary */ const struct cmap_node * cmap_find_by_index(const struct
>> +cmap *cmap, uint16_t index) {
>> +const struct cmap_impl *impl = cmap_get_impl(cmap);
>> +
>> +uint32_t b = index / CMAP_K;
>> +uint32_t e = index % CMAP_K;
>> +
>> +if (b > impl->mask) {
>> +return NULL;
>> +}
>> +
>> +const struct cmap_bucket *bucket = >buckets[b];
>> +
>> +return cmap_node_next(>nodes[e]);
>> +}
>> +
>> +/* Find the index of certain hash value. Currently only used by the
>> +datapath
>> + * DFC cache.
>> + *
>> + * Return the index of the entry if found, or UINT32_MAX if not found
>[[BO'M]] An intro the concept of index would be useful here especially as it
>does not currently exist in cmap. Something like: "The
>'index' of a cmap entry is a way to combine the specific bucket and item
>occupied by an entry into a convenient single integer value. It
>is not used internally by cmap." Unless of course that is actually wrong :)
[Wang, Yipeng] I will add the comments you suggested. It indeed makes it more
understandable.
>If a cmap's capacity exceeds the range of UINT32_MAX what happens? Does
>something different happen if the entry is in a bucket
>that can be expressed in a uint32_t versus a bucket that is outside of that
>range?
[Wang, Yipeng] I currently assume the cmap cannot be larger than uint32_max. It
is a very large number and I guess OvS should not deal with
this big table. But you are right that I should make it clear,
I add comments in cmap header file and other places to explain this
restriction for the newly added API.
>
>> +*/
>> @@ -155,6 +166,11 @@ struct netdev_flow_key { #define
>> EM_FLOW_HASH_MASK (EM_FLOW_HASH_ENTRIES - 1) #define
>> EM_FLOW_HASH_SEGS 2
>>
>> +#define SMC_ENTRY_PER_BUCKET 4
>[[BO'M]] SMC_ENTRY_PER_BUCKET -> SMC_ENTRIES_PER_BUCKET.
>Also a comment something like "A bucket forms the set of possible entries that
>a flow hash can occupy. Therefore
>SMC_ENTRIES_PER_BUCKET for SMC in analagous to EM_FLOW_HASH_SEGS for EMC."
>Might help people familiar with the current
>EMC to grok the SMC a little faster.
>
[Wang, Yipeng] I added more explanations as you suggested. For the
SMC_ENTRIES_PER_BUCKET, it is actually slightly different from
EM_FLOW_HASH_SEGS. For EMC, two hash functions are used to index two
locations, for SMC currently, I just use one hash
function to index a bucket, and iterate the entries in that bucket. It is more
like a middle ground between EMC and CMAP.
>> @@ -2297,6 +2373,76 @@ emc_lookup(struct emc_cache *cache, const struct
>> netdev_flow_key *key)
>> return NULL;
>> }
>>
>> +static inline const struct cmap_node *
>> +smc_entry_get(struct dp_netdev_pmd_thread *pmd, struct smc_cache *cache,
>> +const uint32_t hash)
>> +{
>> +struct smc_bucket *bucket = >buckets[hash & SMC_MASK];
>> +uint16_t sig = hash >> 16;
>> +uint16_t index = UINT16_MAX;
>> +
>> +for (int i = 0; i < SMC_ENTRY_PER_BUCKET; i++) {
>> +if (bucket->sig[i] == sig) {
>> +index = bucket->flow_idx[i];
>> +break;
>> +}
>> +}
>> +if (index != UINT16_MAX) {
>> +return cmap_find_by_index(>flow_table, index);
>> +}
>> +return NULL;
>> +}
>> +
>> +static void
>> +smc_clear_entry(struct smc_bucket *b, int idx) {
>> +b->flow_idx[idx] = UINT16_MAX;
>> +}
>> +
>> +static inline int
>[[BO'M]] As return value seems to be 1 for ok and 0 for failure suggest using
>a bool for the return value. Also a comment describing
>when an insert may fail. Describe insertion strategy which seems to be 'if
>entry already exists update it, otherwise insert in a free
>space, if no free space available randomly pick an entry form the bucket'
>
[Wang, Yipeng] Thanks for pointing it out. I eventually changed it to void
function since I realize that I do not need a return value indeed.
I will include this change and more comments for the logic in V5.
>> +smc_insert(struct dp_netdev_pmd_thread *pmd,
>> + const struct netdev_flow_key *key,
>> + uint32_t hash)
>> +{
>> +struct smc_cache *smc_cache = >flow_cache.smc_cache;
>> +struct smc_bucket *bucket = _cache->buckets[key->hash &
>> SMC_MASK];
>> +
Re: [ovs-dev] [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
Thanks for the comments, please see my reply inlined.
>I've checked the latest patch and the performance results I get are similar to
>the ones give in the previous patches. Also
>enabling/disabling the DFC on the fly works as expected.
>
>The main query I have regards the slow sweep for SMC
>
>[[BO'M]] The slow sweep removes EMC entries that are no longer valid because
>the associated dpcls rule has been changed or has
>expired. Is there a mechanism to remove SMC entries associated with a
>changed/expired dpcls rules?
[Wang, Yipeng] It is a good question. EMC needs to sweep is mostly because EMC
holds pointers to the dp_netdev_flow. If EMC does not sweep and release the
pointers, a dead dpcls rule cannot be de-allocated from memory as long as the
EMC entry referencing it stays. SMC does not hold pointers, so the dead dpcls
can be de-allocated at any time. SMC holds an index to flow_table. If the entry
in flow_table is removed, SMC will just find a miss (and it is OK since SMC is
just a cache). So functionally, slow sweeping is not needed. However,
sweeping SMC may periodically give new flows more empty entries in SMC. But
this adds code complexity so we eventually decide to remove this part of code.
>> }
>>
>> +/* Find a node by the index of the entry of cmap. For example, index 7
>> +means
>> + * the second bucket and the third item.
>[[BO'M]] Is this is assuming 4 for the bucket size. Maybe explicitly add where
>the bucket size is coming from - CMAP_K ? If so is that
>value not 5 for a 64 bit system?
>
[Wang, Yipeng] I will change the comment to use CMAP_K instead of the numbers
as example.
>> +++ b/lib/dpif-netdev.c
>> @@ -129,7 +129,9 @@ struct netdev_flow_key {
>> uint64_t buf[FLOW_MAX_PACKET_U64S]; };
>>
>> -/* Exact match cache for frequently used flows
>> +/* EMC cache and SMC cache compose of the datapath flow cache (DFC)
>[[BO'M]] 'compose of the' -> 'compose the' or else 'together make the'
>> @@ -2297,6 +2373,76 @@ emc_lookup(struct emc_cache *cache, const struct
>> netdev_flow_key *key)
>> return NULL;
>> }
>>
>> +static inline const struct cmap_node *
>> +smc_entry_get(struct dp_netdev_pmd_thread *pmd, struct smc_cache *cache,
>> +const uint32_t hash)
>[[BO'M]] Minor quibble. We can get cache arg from pmd arg -
>pmd->flow_cache->smc_cache.
[Wang, Yipeng] I will fix all the issues you mentioned above.
Thanks!
Yipeng
___
dev mailing list
d...@openvswitch.org
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
Re: [ovs-dev] [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
Hi Yipeng,
Some further comments below. Mainly to do with readability and understanding of
the changes.
Regards,
Billy.
> -Original Message-
> From: Wang, Yipeng1
> Sent: Friday, June 29, 2018 6:53 PM
> To: d...@openvswitch.org
> Cc: Wang, Yipeng1 ; jan.scheur...@ericsson.com;
> Stokes, Ian ; O Mahony, Billy
> ; Loftus, Ciara
> Subject: [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
>
> This patch adds a signature match cache (SMC) after exact match cache (EMC).
> The difference between SMC and EMC is SMC only stores a signature of a flow
> thus it is much more memory efficient. With same memory space, EMC can
> store 8k flows while SMC can store 1M flows. It is generally beneficial to
> turn on
> SMC but turn off EMC when traffic flow count is much larger than EMC size.
>
> SMC cache will map a signature to an netdev_flow index in flow_table. Thus, we
> add two new APIs in cmap for lookup key by index and lookup index by key.
>
> For now, SMC is an experimental feature that it is turned off by default. One
> can
> turn it on using ovsdb options.
>
> Signed-off-by: Yipeng Wang
> ---
> Documentation/topics/dpdk/bridge.rst | 15 ++
> NEWS | 2 +
> lib/cmap.c | 73 +
> lib/cmap.h | 5 +
> lib/dpif-netdev-perf.h | 1 +
> lib/dpif-netdev.c| 310
> ++-
> tests/pmd.at | 1 +
> vswitchd/vswitch.xml | 13 ++
> 8 files changed, 383 insertions(+), 37 deletions(-)
>
> diff --git a/Documentation/topics/dpdk/bridge.rst
> b/Documentation/topics/dpdk/bridge.rst
> index 63f8a62..df74c02 100644
> --- a/Documentation/topics/dpdk/bridge.rst
> +++ b/Documentation/topics/dpdk/bridge.rst
> @@ -102,3 +102,18 @@ For certain traffic profiles with many parallel flows,
> it's
> recommended to set ``N`` to '0' to achieve higher forwarding performance.
>
> For more information on the EMC refer to :doc:`/intro/install/dpdk` .
> +
> +
> +SMC cache (experimental)
> +-
> +
> +SMC cache or signature match cache is a new cache level after EMC cache.
> +The difference between SMC and EMC is SMC only stores a signature of a
> +flow thus it is much more memory efficient. With same memory space, EMC
> +can store 8k flows while SMC can store 1M flows. When traffic flow
> +count is much larger than EMC size, it is generally beneficial to turn
> +off EMC and turn on SMC. It is currently turned off by default and an
> experimental feature.
> +
> +To turn on SMC::
> +
> +$ ovs-vsctl --no-wait set Open_vSwitch .
> + other_config:smc-enable=true
> diff --git a/NEWS b/NEWS
> index cd15a33..26d6ef1 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -40,6 +40,8 @@ Post-v2.9.0
> ovs-appctl dpif-netdev/pmd-perf-show
> * Supervision of PMD performance metrics and logging of suspicious
> iterations
> + * Add signature match cache (SMC) as experimental feature. When turned
> on,
> + it improves throughput when traffic has many more flows than EMC size.
> - ERSPAN:
> * Implemented ERSPAN protocol (draft-foschiano-erspan-00.txt) for
> both kernel datapath and userspace datapath.
> diff --git a/lib/cmap.c b/lib/cmap.c
> index 07719a8..db1c806 100644
> --- a/lib/cmap.c
> +++ b/lib/cmap.c
> @@ -373,6 +373,79 @@ cmap_find(const struct cmap *cmap, uint32_t hash)
> hash);
> }
>
> +/* Find a node by the index of the entry of cmap. For example, index 7
> +means
> + * the second bucket and the third item.
> + * Notice that it is not protected by the optimistic lock (versioning)
> +because
> + * of performance reasons. Currently it is only used by the datapath DFC
> cache.
> + *
> + * Return node for the entry of index or NULL if the index beyond
> +boundary */ const struct cmap_node * cmap_find_by_index(const struct
> +cmap *cmap, uint16_t index) {
> +const struct cmap_impl *impl = cmap_get_impl(cmap);
> +
> +uint32_t b = index / CMAP_K;
> +uint32_t e = index % CMAP_K;
> +
> +if (b > impl->mask) {
> +return NULL;
> +}
> +
> +const struct cmap_bucket *bucket = >buckets[b];
> +
> +return cmap_node_next(>nodes[e]);
> +}
> +
> +/* Find the index of certain hash value. Currently only used by the
> +datapath
> + * DFC cache.
> + *
> + * Return the index of the entry if found, or UINT32_MAX if not found
[[BO'M]] An intro the concept of index would be useful here especially as it
does not currently exist in cmap. Something like: "The 'index' of a cmap entry
is a way to combine the specific bucket and item occupied by an entry into a
convenient single integer value. It is not used internally by cmap." Unless of
course that is actually wrong :)
If a cmap's capacity exceeds the range of UINT32_MAX what happens? Does
something different happen if the entry is in a bucket that can be expressed in
a
Re: [ovs-dev] [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
Hi,
I've checked the latest patch and the performance results I get are similar to
the ones give in the previous patches. Also enabling/disabling the DFC on the
fly works as expected.
The main query I have regards the slow sweep for SMC
[[BO'M]] The slow sweep removes EMC entries that are no longer valid because
the associated dpcls rule has been changed or has expired. Is there a mechanism
to remove SMC entries associated with a changed/expired dpcls rules?
Further comments, queries inline. Review not complete yet, I'll try to finish
off tomorrow.
Regards,
Billy.
> -Original Message-
> From: Wang, Yipeng1
> Sent: Friday, June 29, 2018 6:53 PM
> To: d...@openvswitch.org
> Cc: Wang, Yipeng1 ; jan.scheur...@ericsson.com;
> Stokes, Ian ; O Mahony, Billy
> ; Loftus, Ciara
> Subject: [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
>
> This patch adds a signature match cache (SMC) after exact match cache (EMC).
> The difference between SMC and EMC is SMC only stores a signature of a flow
> thus it is much more memory efficient. With same memory space, EMC can
> store 8k flows while SMC can store 1M flows. It is generally beneficial to
> turn on
> SMC but turn off EMC when traffic flow count is much larger than EMC size.
>
> SMC cache will map a signature to an netdev_flow index in flow_table. Thus, we
> add two new APIs in cmap for lookup key by index and lookup index by key.
>
> For now, SMC is an experimental feature that it is turned off by default. One
> can
> turn it on using ovsdb options.
>
> Signed-off-by: Yipeng Wang
> ---
> Documentation/topics/dpdk/bridge.rst | 15 ++
> NEWS | 2 +
> lib/cmap.c | 73 +
> lib/cmap.h | 5 +
> lib/dpif-netdev-perf.h | 1 +
> lib/dpif-netdev.c| 310
> ++-
> tests/pmd.at | 1 +
> vswitchd/vswitch.xml | 13 ++
> 8 files changed, 383 insertions(+), 37 deletions(-)
>
> diff --git a/Documentation/topics/dpdk/bridge.rst
> b/Documentation/topics/dpdk/bridge.rst
> index 63f8a62..df74c02 100644
> --- a/Documentation/topics/dpdk/bridge.rst
> +++ b/Documentation/topics/dpdk/bridge.rst
> @@ -102,3 +102,18 @@ For certain traffic profiles with many parallel flows,
> it's
> recommended to set ``N`` to '0' to achieve higher forwarding performance.
>
> For more information on the EMC refer to :doc:`/intro/install/dpdk` .
> +
> +
> +SMC cache (experimental)
> +-
> +
> +SMC cache or signature match cache is a new cache level after EMC cache.
> +The difference between SMC and EMC is SMC only stores a signature of a
> +flow thus it is much more memory efficient. With same memory space, EMC
> +can store 8k flows while SMC can store 1M flows. When traffic flow
> +count is much larger than EMC size, it is generally beneficial to turn
> +off EMC and turn on SMC. It is currently turned off by default and an
> experimental feature.
> +
> +To turn on SMC::
> +
> +$ ovs-vsctl --no-wait set Open_vSwitch .
> + other_config:smc-enable=true
> diff --git a/NEWS b/NEWS
> index cd15a33..26d6ef1 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -40,6 +40,8 @@ Post-v2.9.0
> ovs-appctl dpif-netdev/pmd-perf-show
> * Supervision of PMD performance metrics and logging of suspicious
> iterations
> + * Add signature match cache (SMC) as experimental feature. When turned
> on,
> + it improves throughput when traffic has many more flows than EMC size.
> - ERSPAN:
> * Implemented ERSPAN protocol (draft-foschiano-erspan-00.txt) for
> both kernel datapath and userspace datapath.
> diff --git a/lib/cmap.c b/lib/cmap.c
> index 07719a8..db1c806 100644
> --- a/lib/cmap.c
> +++ b/lib/cmap.c
> @@ -373,6 +373,79 @@ cmap_find(const struct cmap *cmap, uint32_t hash)
> hash);
> }
>
> +/* Find a node by the index of the entry of cmap. For example, index 7
> +means
> + * the second bucket and the third item.
[[BO'M]] Is this is assuming 4 for the bucket size. Maybe explicitly add where
the bucket size is coming from - CMAP_K ? If so is that value not 5 for a 64
bit system?
> + * Notice that it is not protected by the optimistic lock (versioning)
> +because
> + * of performance reasons. Currently it is only used by the datapath DFC
> cache.
> + *
> + * Return node for the entry of index or NULL if the index beyond
> +boundary */ const struct cmap_node * cmap_find_by_index(const struct
> +cmap *cmap, uint16_t index) {
> +const struct cmap_impl *impl = cmap_get_impl(cmap);
> +
> +uint32_t b = index / CMAP_K;
> +uint32_t e = index % CMAP_K;
> +
> +if (b > impl->mask) {
> +return NULL;
> +}
> +
> +const struct cmap_bucket *bucket = >buckets[b];
> +
> +return cmap_node_next(>nodes[e]);
> +}
> +
> +/* Find the index of certain hash value. Currently only
[ovs-dev] [PATCH v4 1/2] dpif-netdev: Add SMC cache after EMC cache
This patch adds a signature match cache (SMC) after exact match
cache (EMC). The difference between SMC and EMC is SMC only stores
a signature of a flow thus it is much more memory efficient. With
same memory space, EMC can store 8k flows while SMC can store 1M
flows. It is generally beneficial to turn on SMC but turn off EMC
when traffic flow count is much larger than EMC size.
SMC cache will map a signature to an netdev_flow index in
flow_table. Thus, we add two new APIs in cmap for lookup key by
index and lookup index by key.
For now, SMC is an experimental feature that it is turned off by
default. One can turn it on using ovsdb options.
Signed-off-by: Yipeng Wang
---
Documentation/topics/dpdk/bridge.rst | 15 ++
NEWS | 2 +
lib/cmap.c | 73 +
lib/cmap.h | 5 +
lib/dpif-netdev-perf.h | 1 +
lib/dpif-netdev.c| 310 ++-
tests/pmd.at | 1 +
vswitchd/vswitch.xml | 13 ++
8 files changed, 383 insertions(+), 37 deletions(-)
diff --git a/Documentation/topics/dpdk/bridge.rst
b/Documentation/topics/dpdk/bridge.rst
index 63f8a62..df74c02 100644
--- a/Documentation/topics/dpdk/bridge.rst
+++ b/Documentation/topics/dpdk/bridge.rst
@@ -102,3 +102,18 @@ For certain traffic profiles with many parallel flows,
it's recommended to set
``N`` to '0' to achieve higher forwarding performance.
For more information on the EMC refer to :doc:`/intro/install/dpdk` .
+
+
+SMC cache (experimental)
+-
+
+SMC cache or signature match cache is a new cache level after EMC cache.
+The difference between SMC and EMC is SMC only stores a signature of a flow
+thus it is much more memory efficient. With same memory space, EMC can store 8k
+flows while SMC can store 1M flows. When traffic flow count is much larger than
+EMC size, it is generally beneficial to turn off EMC and turn on SMC. It is
+currently turned off by default and an experimental feature.
+
+To turn on SMC::
+
+$ ovs-vsctl --no-wait set Open_vSwitch . other_config:smc-enable=true
diff --git a/NEWS b/NEWS
index cd15a33..26d6ef1 100644
--- a/NEWS
+++ b/NEWS
@@ -40,6 +40,8 @@ Post-v2.9.0
ovs-appctl dpif-netdev/pmd-perf-show
* Supervision of PMD performance metrics and logging of suspicious
iterations
+ * Add signature match cache (SMC) as experimental feature. When turned on,
+ it improves throughput when traffic has many more flows than EMC size.
- ERSPAN:
* Implemented ERSPAN protocol (draft-foschiano-erspan-00.txt) for
both kernel datapath and userspace datapath.
diff --git a/lib/cmap.c b/lib/cmap.c
index 07719a8..db1c806 100644
--- a/lib/cmap.c
+++ b/lib/cmap.c
@@ -373,6 +373,79 @@ cmap_find(const struct cmap *cmap, uint32_t hash)
hash);
}
+/* Find a node by the index of the entry of cmap. For example, index 7 means
+ * the second bucket and the third item.
+ * Notice that it is not protected by the optimistic lock (versioning) because
+ * of performance reasons. Currently it is only used by the datapath DFC cache.
+ *
+ * Return node for the entry of index or NULL if the index beyond boundary */
+const struct cmap_node *
+cmap_find_by_index(const struct cmap *cmap, uint16_t index)
+{
+const struct cmap_impl *impl = cmap_get_impl(cmap);
+
+uint32_t b = index / CMAP_K;
+uint32_t e = index % CMAP_K;
+
+if (b > impl->mask) {
+return NULL;
+}
+
+const struct cmap_bucket *bucket = >buckets[b];
+
+return cmap_node_next(>nodes[e]);
+}
+
+/* Find the index of certain hash value. Currently only used by the datapath
+ * DFC cache.
+ *
+ * Return the index of the entry if found, or UINT32_MAX if not found */
+
+uint32_t
+cmap_find_index(const struct cmap *cmap, uint32_t hash)
+{
+const struct cmap_impl *impl = cmap_get_impl(cmap);
+uint32_t h1 = rehash(impl, hash);
+uint32_t h2 = other_hash(h1);
+
+uint32_t b_index1 = h1 & impl->mask;
+uint32_t b_index2 = h2 & impl->mask;
+
+uint32_t c1, c2;
+uint32_t index = UINT32_MAX;
+
+const struct cmap_bucket *b1 = >buckets[b_index1];
+const struct cmap_bucket *b2 = >buckets[b_index2];
+
+do {
+do {
+c1 = read_even_counter(b1);
+for (int i = 0; i < CMAP_K; i++) {
+if (b1->hashes[i] == hash) {
+index = b_index1 * CMAP_K + i;
+ }
+}
+} while (OVS_UNLIKELY(counter_changed(b1, c1)));
+if (index != UINT32_MAX) {
+break;
+}
+do {
+c2 = read_even_counter(b2);
+for (int i = 0; i < CMAP_K; i++) {
+if (b2->hashes[i] == hash) {
+index = b_index2 * CMAP_K + i;
+}
+}
+} while (OVS_UNLIKELY(counter_changed(b2, c2)));
+
+if
