Re: [ovs-dev] [PATCH 3/4] classifier: Remove rare optimization case.

[Ben Pfaff]

On Wed, Apr 13, 2016 at 07:06:45PM -0700, Jarno Rajahalme wrote:
> This optimization applied when a staged lookup index would narrow down
> to a single rule, which happens sometimes is simple test cases, but
> presumably less often in more populated flow tables.  The result of
> this optimization allowed a bit more general megaflows, but the bit
> patterns produced were sometimes cryptic.  Finally, a later fix to a
> more important performance problem does not allow for this
> optimization any more, so remove it now.
> 
> Signed-off-by: Jarno Rajahalme 

If it causes problems, we can try harder.

Acked-by: Ben Pfaff 
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

Re: [ovs-dev] [PATCH 3/4] classifier: Remove rare optimization case.

[Ryan Moats]

> --- Original Message ---
> This optimization applied when a staged lookup index would narrow down
> to a single rule, which happens sometimes is simple test cases, but
> presumably less often in more populated flow tables.  The result of
> this optimization allowed a bit more general megaflows, but the bit
> patterns produced were sometimes cryptic.  Finally, a later fix to a
> more important performance problem does not allow for this
> optimization any more, so remove it now.
>
> Signed-off-by: Jarno Rajahalme 
> ---

Acked-by: Ryan Moats 
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

[ovs-dev] [PATCH 3/4] classifier: Remove rare optimization case.

[Jarno Rajahalme]

This optimization applied when a staged lookup index would narrow down
to a single rule, which happens sometimes is simple test cases, but
presumably less often in more populated flow tables.  The result of
this optimization allowed a bit more general megaflows, but the bit
patterns produced were sometimes cryptic.  Finally, a later fix to a
more important performance problem does not allow for this
optimization any more, so remove it now.

Signed-off-by: Jarno Rajahalme 
---
 lib/classifier.c  | 75 +--
 tests/classifier.at   | 10 +++
 tests/ofproto-dpif.at | 14 +-
 3 files changed, 13 insertions(+), 86 deletions(-)

diff --git a/lib/classifier.c b/lib/classifier.c
index 1fbaa0c..ebd31fb 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -1649,54 +1649,6 @@ find_match(const struct cls_subtable *subtable, 
cls_version_t version,
 return NULL;
 }
 
-/* Returns true if 'target' satisifies 'flow'/'mask', that is, if each bit
- * for which 'flow', for which 'mask' has a bit set, specifies a particular
- * value has the correct value in 'target'.
- *
- * This function is equivalent to miniflow_and_mask_matches_flow() but this
- * version fills in the mask bits in 'wc'. */
-static inline bool
-miniflow_and_mask_matches_flow_wc(const struct miniflow *flow,
-  const struct minimask *mask,
-  const struct flow *target,
-  struct flow_wildcards *wc)
-{
-const uint64_t *flowp = miniflow_get_values(flow);
-const uint64_t *maskp = miniflow_get_values(>masks);
-const uint64_t *target_u64 = (const uint64_t *)target;
-uint64_t *wc_u64 = (uint64_t *)>masks;
-uint64_t diff;
-size_t idx;
-map_t map;
-
-FLOWMAP_FOR_EACH_MAP (map, mask->masks.map) {
-MAP_FOR_EACH_INDEX(idx, map) {
-uint64_t msk = *maskp++;
-
-diff = (*flowp++ ^ target_u64[idx]) & msk;
-if (diff) {
-goto out;
-}
-
-/* Fill in the bits that were looked at. */
-wc_u64[idx] |= msk;
-}
-target_u64 += MAP_T_BITS;
-wc_u64 += MAP_T_BITS;
-}
-return true;
-
-out:
-/* Only unwildcard if none of the differing bits is already
- * exact-matched. */
-if (!(wc_u64[idx] & diff)) {
-/* Keep one bit of the difference.  The selected bit may be
- * different in big-endian v.s. little-endian systems. */
-wc_u64[idx] |= rightmost_1bit(diff);
-}
-return false;
-}
-
 static const struct cls_match *
 find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
   const struct flow *flow, struct trie_ctx trie_ctx[CLS_MAX_TRIES],
@@ -1715,8 +1667,6 @@ find_match_wc(const struct cls_subtable *subtable, 
cls_version_t version,
 
 /* Try to finish early by checking fields in segments. */
 for (i = 0; i < subtable->n_indices; i++) {
-const struct cmap_node *inode;
-
 if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
 subtable->index_maps[i], flow, wc)) {
 /* 'wc' bits for the trie field set, now unwildcard the preceding
@@ -1731,32 +1681,9 @@ find_match_wc(const struct cls_subtable *subtable, 
cls_version_t version,
subtable->index_maps[i],
_offset, );
 
-inode = cmap_find(>indices[i], hash);
-if (!inode) {
+if (!cmap_find(>indices[i], hash)) {
 goto no_match;
 }
-
-/* If we have narrowed down to a single rule already, check whether
- * that rule matches.  Either way, we're done.
- *
- * (Rare) hash collisions may cause us to miss the opportunity for this
- * optimization. */
-if (!cmap_node_next(inode)) {
-const struct cls_match *head;
-
-ASSIGN_CONTAINER(head, inode - i, index_nodes);
-if (miniflow_and_mask_matches_flow_wc(>flow, >mask,
-  flow, wc)) {
-/* Return highest priority rule that is visible. */
-CLS_MATCH_FOR_EACH (rule, head) {
-if (OVS_LIKELY(cls_match_visible_in_version(rule,
-version))) {
-return rule;
-}
-}
-}
-return NULL;
-}
 }
 /* Trie check for the final range. */
 if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
diff --git a/tests/classifier.at b/tests/classifier.at
index b110508..e56ba3a 100644
--- a/tests/classifier.at
+++ b/tests/classifier.at
@@ -49,7 +49,7 @@ Datapath actions: 1
 ])
 AT_CHECK([ovs-appctl ofproto/trace br0