[ovs-dev] [PATCH 4/5] classifier: Pre-compute stage masks.
Jarno Rajahalme
jrajahalme at nicira.com
Wed Aug 5 17:53:45 UTC 2015
This makes stage mask computation happen only when a subtable is
inserted and allows simplification of the main lookup function.
Classifier benchmark shows that this speeds up the classification
(with wildcards) about 5%.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/classifier-private.h | 107 +++++++++---------------------
lib/classifier.c | 168 ++++++++++++++++++++++++++++-------------------
lib/flow.c | 2 +-
lib/flow.h | 10 ++-
4 files changed, 139 insertions(+), 148 deletions(-)
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index 3a150ab..cc255fe 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -42,7 +42,7 @@ struct cls_subtable {
/* These fields are accessed by readers who care about wildcarding. */
const tag_type tag; /* Tag generated from mask for partitioning. */
const uint8_t n_indices; /* How many indices to use. */
- const uint8_t index_ofs[CLS_MAX_INDICES]; /* u64 segment boundaries. */
+ const struct miniflow index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */
unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'
* (runtime configurable). */
const int ports_mask_len;
@@ -226,54 +226,6 @@ struct trie_node {
* These are only used by the classifier, so place them here to allow
* for better optimization. */
-/* Initializes 'map->tnl_map' and 'map->pkt_map' with a subset of 'miniflow'
- * that includes only the portions with u64-offset 'i' such that start <= i <
- * end. Does not copy any data from 'miniflow' to 'map'.
- *
- * TODO: Ensure that 'start' and 'end' are compile-time constants. */
-static inline unsigned int /* offset */
-miniflow_get_map_in_range(const struct miniflow *miniflow,
- uint8_t start, uint8_t end, struct miniflow *map)
-{
- unsigned int offset = 0;
-
- map->tnl_map = miniflow->tnl_map;
- map->pkt_map = miniflow->pkt_map;
-
- if (start >= FLOW_TNL_U64S) {
- offset += count_1bits(map->tnl_map);
- map->tnl_map = 0;
- if (start > FLOW_TNL_U64S) {
- /* Clear 'start - FLOW_TNL_U64S' LSBs from pkt_map. */
- start -= FLOW_TNL_U64S;
- uint64_t msk = (UINT64_C(1) << start) - 1;
-
- offset += count_1bits(map->pkt_map & msk);
- map->pkt_map &= ~msk;
- }
- } else if (start > 0) {
- /* Clear 'start' LSBs from tnl_map. */
- uint64_t msk = (UINT64_C(1) << start) - 1;
-
- offset += count_1bits(map->tnl_map & msk);
- map->tnl_map &= ~msk;
- }
-
- if (end <= FLOW_TNL_U64S) {
- map->pkt_map = 0;
- if (end < FLOW_TNL_U64S) {
- /* Keep 'end' LSBs in tnl_map. */
- map->tnl_map &= (UINT64_C(1) << end) - 1;
- }
- } else {
- if (end < FLOW_U64S) {
- /* Keep 'end - FLOW_TNL_U64S' LSBs in pkt_map. */
- map->pkt_map &= (UINT64_C(1) << (end - FLOW_TNL_U64S)) - 1;
- }
- }
- return offset;
-}
-
/* Returns a hash value for the bits of 'flow' where there are 1-bits in
* 'mask', given 'basis'.
*
@@ -333,28 +285,29 @@ miniflow_hash_in_minimask(const struct miniflow *flow,
static inline uint32_t
flow_hash_in_minimask_range(const struct flow *flow,
const struct minimask *mask,
- uint8_t start, uint8_t end, uint32_t *basis)
+ const struct miniflow *maps,
+ unsigned int *offset,
+ uint32_t *basis)
{
const uint64_t *mask_values = miniflow_get_values(&mask->masks);
+ const uint64_t *p = mask_values + *offset;
const uint64_t *flow_u64 = (const uint64_t *)flow;
- unsigned int offset;
- struct miniflow map;
- const uint64_t *p;
uint32_t hash = *basis;
size_t idx;
- offset = miniflow_get_map_in_range(&mask->masks, start, end, &map);
- p = mask_values + offset;
- MAP_FOR_EACH_INDEX(idx, map.tnl_map) {
- hash = hash_add64(hash, flow_u64[idx] & *p++);
+ if (OVS_UNLIKELY(maps->tnl_map)) {
+ MAP_FOR_EACH_INDEX(idx, maps->tnl_map) {
+ hash = hash_add64(hash, flow_u64[idx] & *p++);
+ }
}
flow_u64 += FLOW_TNL_U64S;
- MAP_FOR_EACH_INDEX(idx, map.pkt_map) {
+ MAP_FOR_EACH_INDEX(idx, maps->pkt_map) {
hash = hash_add64(hash, flow_u64[idx] & *p++);
}
*basis = hash; /* Allow continuation from the unfinished value. */
- return hash_finish(hash, (p - mask_values) * 8);
+ *offset = p - mask_values;
+ return hash_finish(hash, *offset * 8);
}
/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask. */
@@ -365,24 +318,25 @@ flow_wildcards_fold_minimask(struct flow_wildcards *wc,
flow_union_with_miniflow(&wc->masks, &mask->masks);
}
-/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask
- * in range [start, end). */
+/* Fold minimask 'mask''s wildcard mask into 'wc's wildcard mask for bits in
+ * 'map'. The 1-bits in 'map' correspond to the first 1-bits in 'mask''s
+ * map. */
static inline void
-flow_wildcards_fold_minimask_range(struct flow_wildcards *wc,
- const struct minimask *mask,
- uint8_t start, uint8_t end)
+flow_wildcards_fold_minimask_in_map(struct flow_wildcards *wc,
+ const struct minimask *mask,
+ const struct miniflow *map)
{
const uint64_t *p = miniflow_get_values(&mask->masks);
uint64_t *dst_u64 = (uint64_t *)&wc->masks;
- struct miniflow map;
size_t idx;
- p += miniflow_get_map_in_range(&mask->masks, start, end, &map);
- MAP_FOR_EACH_INDEX(idx, map.tnl_map) {
- dst_u64[idx] |= *p++;
+ if (map->tnl_map) {
+ MAP_FOR_EACH_INDEX(idx, map->tnl_map) {
+ dst_u64[idx] |= *p++;
+ }
}
dst_u64 += FLOW_TNL_U64S;
- MAP_FOR_EACH_INDEX(idx, map.pkt_map) {
+ MAP_FOR_EACH_INDEX(idx, map->pkt_map) {
dst_u64[idx] |= *p++;
}
}
@@ -437,27 +391,26 @@ minimatch_hash(const struct minimatch *match, uint32_t basis)
* The hash values returned by this function are the same as those returned by
* flow_hash_in_minimask_range(), only the form of the arguments differ. */
static inline uint32_t
-minimatch_hash_range(const struct minimatch *match, uint8_t start, uint8_t end,
+minimatch_hash_range(const struct minimatch *match,
+ const struct miniflow *maps, unsigned int *offset,
uint32_t *basis)
{
const uint64_t *p = miniflow_get_values(match->flow);
const uint64_t *q = miniflow_get_values(&match->mask->masks);
- unsigned int offset;
- struct miniflow map;
uint32_t hash = *basis;
int n, i;
- offset = miniflow_get_map_in_range(&match->mask->masks, start, end, &map);
- n = miniflow_n_values(&map);
+ n = miniflow_n_values(maps);
- q += offset;
- p += offset;
+ q += *offset;
+ p += *offset;
for (i = 0; i < n; i++) {
hash = hash_add64(hash, p[i] & q[i]);
}
*basis = hash; /* Allow continuation from the unfinished value. */
- return hash_finish(hash, (offset + n) * 8);
+ *offset += n;
+ return hash_finish(hash, *offset * 8);
}
#endif
diff --git a/lib/classifier.c b/lib/classifier.c
index cba80b5..975d04f 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -579,9 +579,9 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
struct cls_match *new;
struct cls_subtable *subtable;
uint32_t ihash[CLS_MAX_INDICES];
- uint8_t prev_be64ofs = 0;
struct cls_match *head;
size_t n_rules = 0;
+ unsigned int mask_offset;
uint32_t basis;
uint32_t hash;
int i;
@@ -598,12 +598,13 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
/* Compute hashes in segments. */
basis = 0;
+ mask_offset = 0;
for (i = 0; i < subtable->n_indices; i++) {
- ihash[i] = minimatch_hash_range(&rule->match, prev_be64ofs,
- subtable->index_ofs[i], &basis);
- prev_be64ofs = subtable->index_ofs[i];
+ ihash[i] = minimatch_hash_range(&rule->match, &subtable->index_maps[i],
+ &mask_offset, &basis);
}
- hash = minimatch_hash_range(&rule->match, prev_be64ofs, FLOW_U64S, &basis);
+ hash = minimatch_hash_range(&rule->match, &subtable->index_maps[i],
+ &mask_offset, &basis);
head = find_equal(subtable, rule->match.flow, hash);
if (!head) {
@@ -784,7 +785,7 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
struct cls_subtable *subtable;
int i;
uint32_t basis = 0, hash, ihash[CLS_MAX_INDICES];
- uint8_t prev_be64ofs = 0;
+ unsigned int mask_offset;
size_t n_rules;
rule = cls_rule->cls_match;
@@ -800,13 +801,14 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
subtable = find_subtable(cls, cls_rule->match.mask);
ovs_assert(subtable);
+ mask_offset = 0;
for (i = 0; i < subtable->n_indices; i++) {
- ihash[i] = minimatch_hash_range(&cls_rule->match, prev_be64ofs,
- subtable->index_ofs[i], &basis);
- prev_be64ofs = subtable->index_ofs[i];
+ ihash[i] = minimatch_hash_range(&cls_rule->match,
+ &subtable->index_maps[i],
+ &mask_offset, &basis);
}
- hash = minimatch_hash_range(&cls_rule->match, prev_be64ofs, FLOW_U64S,
- &basis);
+ hash = minimatch_hash_range(&cls_rule->match, &subtable->index_maps[i],
+ &mask_offset, &basis);
head = find_equal(subtable, cls_rule->match.flow, hash);
@@ -1527,6 +1529,45 @@ find_subtable(const struct classifier *cls, const struct minimask *mask)
return NULL;
}
+/* Initializes 'map' with a subset of 'miniflow''s maps that includes only the
+ * portions with u64-offset 'i' such that 'start' <= i < 'end'. Does not copy
+ * any data from 'miniflow' to 'map'. */
+static void
+miniflow_get_map_in_range(const struct miniflow *miniflow,
+ uint8_t start, uint8_t end, struct miniflow *map)
+{
+ *map = *miniflow; /* Copy maps. */
+
+ if (start >= FLOW_TNL_U64S) {
+ map->tnl_map = 0;
+ if (start > FLOW_TNL_U64S) {
+ /* Clear 'start - FLOW_TNL_U64S' LSBs from pkt_map. */
+ start -= FLOW_TNL_U64S;
+ uint64_t msk = (UINT64_C(1) << start) - 1;
+
+ map->pkt_map &= ~msk;
+ }
+ } else if (start > 0) {
+ /* Clear 'start' LSBs from tnl_map. */
+ uint64_t msk = (UINT64_C(1) << start) - 1;
+
+ map->tnl_map &= ~msk;
+ }
+
+ if (end <= FLOW_TNL_U64S) {
+ map->pkt_map = 0;
+ if (end < FLOW_TNL_U64S) {
+ /* Keep 'end' LSBs in tnl_map. */
+ map->tnl_map &= (UINT64_C(1) << end) - 1;
+ }
+ } else {
+ if (end < FLOW_U64S) {
+ /* Keep 'end - FLOW_TNL_U64S' LSBs in pkt_map. */
+ map->pkt_map &= (UINT64_C(1) << (end - FLOW_TNL_U64S)) - 1;
+ }
+ }
+}
+
/* The new subtable will be visible to the readers only after this. */
static struct cls_subtable *
insert_subtable(struct classifier *cls, const struct minimask *mask)
@@ -1534,7 +1575,7 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
uint32_t hash = minimask_hash(mask, 0);
struct cls_subtable *subtable;
int i, index = 0;
- struct flow_wildcards old, new;
+ struct minimask stage_mask;
uint8_t prev;
size_t count = miniflow_n_values(&mask->masks);
@@ -1544,29 +1585,29 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
&mask->masks, count);
/* Init indices for segmented lookup, if any. */
- flow_wildcards_init_catchall(&new);
- old = new;
prev = 0;
for (i = 0; i < cls->n_flow_segments; i++) {
- flow_wildcards_fold_minimask_range(&new, mask, prev,
- cls->flow_segments[i]);
+ miniflow_get_map_in_range(&mask->masks, prev, cls->flow_segments[i],
+ &stage_mask.masks);
/* Add an index if it adds mask bits. */
- if (!flow_wildcards_equal(&new, &old)) {
+ if (!minimask_is_catchall(&stage_mask)) {
cmap_init(&subtable->indices[index]);
- *CONST_CAST(uint8_t *, &subtable->index_ofs[index])
- = cls->flow_segments[i];
+ *CONST_CAST(struct miniflow *, &subtable->index_maps[index])
+ = stage_mask.masks;
index++;
- old = new;
}
prev = cls->flow_segments[i];
}
- /* Check if the rest of the subtable's mask adds any bits,
+ /* Map for the final stage. */
+ miniflow_get_map_in_range(
+ &mask->masks, prev, FLOW_U64S,
+ CONST_CAST(struct miniflow *, &subtable->index_maps[index]));
+ /* Check if the final stage adds any bits,
* and remove the last index if it doesn't. */
if (index > 0) {
- flow_wildcards_fold_minimask_range(&new, mask, prev, FLOW_U64S);
- if (flow_wildcards_equal(&new, &old)) {
+ if (miniflow_equal_maps(&subtable->index_maps[index],
+ &subtable->index_maps[index - 1])) {
--index;
- *CONST_CAST(uint8_t *, &subtable->index_ofs[index]) = 0;
cmap_destroy(&subtable->indices[index]);
}
}
@@ -1617,11 +1658,6 @@ destroy_subtable(struct classifier *cls, struct cls_subtable *subtable)
ovsrcu_postpone(free, subtable);
}
-struct range {
- uint8_t start;
- uint8_t end;
-};
-
static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs);
/* Return 'true' if can skip rest of the subtable based on the prefix trie
@@ -1629,7 +1665,7 @@ static unsigned int be_get_bit_at(const ovs_be32 value[], unsigned int ofs);
static inline bool
check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
const unsigned int field_plen[CLS_MAX_TRIES],
- const struct range ofs, const struct flow *flow,
+ const struct miniflow *range_map, const struct flow *flow,
struct flow_wildcards *wc)
{
int j;
@@ -1645,7 +1681,7 @@ check_tries(struct trie_ctx trie_ctx[CLS_MAX_TRIES], unsigned int n_tries,
uint8_t be64ofs = be32ofs / 2;
/* Is the trie field within the current range of fields? */
- if (be64ofs >= ofs.start && be64ofs < ofs.end) {
+ if (MINIFLOW_IN_MAP(range_map, be64ofs)) {
/* On-demand trie lookup. */
if (!ctx->lookup_done) {
memset(&ctx->match_plens, 0, sizeof ctx->match_plens);
@@ -1796,16 +1832,6 @@ out:
return false;
}
-/* Unwildcard the fields looked up so far, if any. */
-static void
-fill_range_wc(const struct cls_subtable *subtable, struct flow_wildcards *wc,
- uint8_t to)
-{
- if (to) {
- flow_wildcards_fold_minimask_range(wc, &subtable->mask, 0, to);
- }
-}
-
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],
@@ -1814,35 +1840,37 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
uint32_t basis = 0, hash;
const struct cls_match *rule = NULL;
int i;
- struct range ofs;
+ struct miniflow stages_map;
+ unsigned int mask_offset = 0;
if (OVS_UNLIKELY(!wc)) {
return find_match(subtable, version, flow,
flow_hash_in_minimask(flow, &subtable->mask, 0));
}
- ofs.start = 0;
+ memset(&stages_map, 0, sizeof stages_map);
/* Try to finish early by checking fields in segments. */
for (i = 0; i < subtable->n_indices; i++) {
const struct cmap_node *inode;
- ofs.end = subtable->index_ofs[i];
-
- if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow,
- wc)) {
+ 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
* bits used so far. */
- fill_range_wc(subtable, wc, ofs.start);
- return NULL;
+ goto no_match;
}
- hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
- ofs.end, &basis);
+
+ /* Accumulate the map used so far. */
+ stages_map.tnl_map |= subtable->index_maps[i].tnl_map;
+ stages_map.pkt_map |= subtable->index_maps[i].pkt_map;
+
+ hash = flow_hash_in_minimask_range(flow, &subtable->mask,
+ &subtable->index_maps[i],
+ &mask_offset, &basis);
+
inode = cmap_find(&subtable->indices[i], hash);
if (!inode) {
- /* No match, can stop immediately, but must fold in the bits
- * used in lookup so far. */
- fill_range_wc(subtable, wc, ofs.end);
- return NULL;
+ goto no_match;
}
/* If we have narrowed down to a single rule already, check whether
@@ -1866,21 +1894,20 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
}
return NULL;
}
- ofs.start = ofs.end;
}
- ofs.end = FLOW_U64S;
/* Trie check for the final range. */
- if (check_tries(trie_ctx, n_tries, subtable->trie_plen, ofs, flow, wc)) {
- fill_range_wc(subtable, wc, ofs.start);
- return NULL;
+ if (check_tries(trie_ctx, n_tries, subtable->trie_plen,
+ &subtable->index_maps[i], flow, wc)) {
+ goto no_match;
}
- hash = flow_hash_in_minimask_range(flow, &subtable->mask, ofs.start,
- ofs.end, &basis);
+ hash = flow_hash_in_minimask_range(flow, &subtable->mask,
+ &subtable->index_maps[i],
+ &mask_offset, &basis);
rule = find_match(subtable, version, flow, hash);
if (!rule && subtable->ports_mask_len) {
- /* Ports are always part of the final range, if any.
- * No match was found for the ports. Use the ports trie to figure out
- * which ports bits to unwildcard. */
+ /* The final stage had ports, but there was no match. Instead of
+ * unwildcarding all the ports bits, use the ports trie to figure out a
+ * smaller set of bits to unwildcard. */
unsigned int mbits;
ovs_be32 value, plens, mask;
@@ -1891,15 +1918,18 @@ find_match_wc(const struct cls_subtable *subtable, cls_version_t version,
((OVS_FORCE ovs_be32 *)&wc->masks)[TP_PORTS_OFS32] |=
mask & be32_prefix_mask(mbits);
- /* Unwildcard all bits in the mask upto the ports, as they were used
- * to determine there is no match. */
- fill_range_wc(subtable, wc, TP_PORTS_OFS64);
- return NULL;
+ goto no_match;
}
/* Must unwildcard all the fields, as they were looked at. */
flow_wildcards_fold_minimask(wc, &subtable->mask);
return rule;
+
+no_match:
+ /* Unwildcard the bits in stages so far, as they were used in determining
+ * there is no match. */
+ flow_wildcards_fold_minimask_in_map(wc, &subtable->mask, &stages_map);
+ return NULL;
}
static struct cls_match *
diff --git a/lib/flow.c b/lib/flow.c
index 72c172c..9a2bb6b 100644
--- a/lib/flow.c
+++ b/lib/flow.c
@@ -2317,7 +2317,7 @@ miniflow_equal(const struct miniflow *a, const struct miniflow *b)
const uint64_t *ap = miniflow_get_values(a);
const uint64_t *bp = miniflow_get_values(b);
- if (OVS_LIKELY(a->tnl_map == b->tnl_map && a->pkt_map == b->pkt_map)) {
+ if (OVS_LIKELY(miniflow_equal_maps(a, b))) {
return !memcmp(ap, bp, miniflow_n_values(a) * sizeof *ap);
} else {
uint64_t map;
diff --git a/lib/flow.h b/lib/flow.h
index 96aa4aa..17745ad 100644
--- a/lib/flow.h
+++ b/lib/flow.h
@@ -590,7 +590,7 @@ miniflow_get__(const struct miniflow *mf, size_t u64_idx)
: miniflow_values_get__(miniflow_get_values(mf), mf->tnl_map, u64_idx);
}
-#define MINIFLOW_IN_MAP(MF, U64_IDX) \
+#define MINIFLOW_IN_MAP(MF, U64_IDX) \
(OVS_LIKELY(U64_IDX >= FLOW_TNL_U64S) \
? (MF)->pkt_map & (UINT64_C(1) << ((U64_IDX) - FLOW_TNL_U64S)) \
: (MF)->tnl_map & (UINT64_C(1) << (U64_IDX)))
@@ -627,6 +627,8 @@ static inline ovs_be32 miniflow_get_be32(const struct miniflow *,
static inline uint16_t miniflow_get_vid(const struct miniflow *);
static inline uint16_t miniflow_get_tcp_flags(const struct miniflow *);
static inline ovs_be64 miniflow_get_metadata(const struct miniflow *);
+static inline bool miniflow_equal_maps(const struct miniflow *a,
+ const struct miniflow *b);
bool miniflow_equal(const struct miniflow *a, const struct miniflow *b);
bool miniflow_equal_in_minimask(const struct miniflow *a,
@@ -752,6 +754,12 @@ miniflow_get_metadata(const struct miniflow *flow)
return MINIFLOW_GET_BE64(flow, metadata);
}
+static inline bool
+miniflow_equal_maps(const struct miniflow *a, const struct miniflow *b)
+{
+ return a->tnl_map == b->tnl_map && a->pkt_map == b->pkt_map;
+}
+
/* Returns the mask for the OpenFlow 1.1+ "metadata" field in 'mask'.
*
* The return value is all-1-bits if 'mask' matches on the whole value of the
--
2.1.4
More information about the dev
mailing list