[ovs-dev] [PATCH v4 9/9] classifier: Retire partitions.
Jarno Rajahalme
jrajahalme at nicira.com
Fri Aug 7 23:57:42 UTC 2015
Classifier partitions allowed skipping subtables when if was known
from the flow's metadata field that the subtable cannot possibly
match. This functionality was later implemented in a more general
fashion by staged lookup, where the first stage also covers the
metadata field, among the rest of the non-packet fields in the struct
flow. While in theory skipping a subtable on the basis of the
metadata field alone could produce more effective wildcards, on the
basis of our testsuite coverage it does not seem to be the case, as
removing the partitioning feature did not result in any test failures.
Removing the partitioning feature makes classifier lookups roughly 20%
faster when a wildcard mask is not needed, and roughly 10% faster when
a wildcard mask is needed, as tested with the test-classifier
benchmark with one lookup thread.
Found by profiling with 'perf'.
Signed-off-by: Jarno Rajahalme <jrajahalme at nicira.com>
---
lib/automake.mk | 2 -
lib/classifier-private.h | 15 -------
lib/classifier.c | 107 -----------------------------------------------
lib/tag.c | 64 ----------------------------
lib/tag.h | 100 -------------------------------------------
5 files changed, 288 deletions(-)
delete mode 100644 lib/tag.c
delete mode 100644 lib/tag.h
diff --git a/lib/automake.mk b/lib/automake.mk
index 15a9373..c262af8 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -245,8 +245,6 @@ lib_libopenvswitch_la_SOURCES = \
lib/syslog-provider.h \
lib/table.c \
lib/table.h \
- lib/tag.c \
- lib/tag.h \
lib/timer.c \
lib/timer.h \
lib/timeval.c \
diff --git a/lib/classifier-private.h b/lib/classifier-private.h
index b315a4c..9258ca1 100644
--- a/lib/classifier-private.h
+++ b/lib/classifier-private.h
@@ -21,7 +21,6 @@
#include "flow.h"
#include "hash.h"
#include "rculist.h"
-#include "tag.h"
/* Classifier internal definitions, subject to change at any time. */
@@ -40,7 +39,6 @@ struct cls_subtable {
* following data structures. */
/* 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 struct flowmap index_maps[CLS_MAX_INDICES + 1]; /* Stage maps. */
unsigned int trie_plen[CLS_MAX_TRIES]; /* Trie prefix length in 'mask'
@@ -55,16 +53,6 @@ struct cls_subtable {
/* 'mask' must be the last field. */
};
-/* Associates a metadata value (that is, a value of the OpenFlow 1.1+ metadata
- * field) with tags for the "cls_subtable"s that contain rules that match that
- * metadata value. */
-struct cls_partition {
- struct cmap_node cmap_node; /* In struct classifier's 'partitions' map. */
- ovs_be64 metadata; /* metadata value for this partition. */
- tag_type tags; /* OR of each flow's cls_subtable tag. */
- struct tag_tracker tracker; /* Tracks the bits in 'tags'. */
-};
-
/* Internal representation of a rule in a "struct cls_subtable".
*
* The 'next' member is an element in a singly linked, null-terminated list.
@@ -77,9 +65,6 @@ struct cls_match {
OVSRCU_TYPE(struct cls_match *) next; /* Equal, lower-priority matches. */
OVSRCU_TYPE(struct cls_conjunction_set *) conj_set;
- /* Accessed only by writers. */
- struct cls_partition *partition;
-
/* Accessed by readers interested in wildcarding. */
const int priority; /* Larger numbers are higher priorities. */
struct cmap_node index_nodes[CLS_MAX_INDICES]; /* Within subtable's
diff --git a/lib/classifier.c b/lib/classifier.c
index 3866f54..53bcbe7 100644
--- a/lib/classifier.c
+++ b/lib/classifier.c
@@ -321,7 +321,6 @@ classifier_init(struct classifier *cls, const uint8_t *flow_segments)
cls->n_rules = 0;
cmap_init(&cls->subtables_map);
pvector_init(&cls->subtables);
- cmap_init(&cls->partitions);
cls->n_flow_segments = 0;
if (flow_segments) {
while (cls->n_flow_segments < CLS_MAX_INDICES
@@ -343,7 +342,6 @@ void
classifier_destroy(struct classifier *cls)
{
if (cls) {
- struct cls_partition *partition;
struct cls_subtable *subtable;
int i;
@@ -356,11 +354,6 @@ classifier_destroy(struct classifier *cls)
}
cmap_destroy(&cls->subtables_map);
- CMAP_FOR_EACH (partition, cmap_node, &cls->partitions) {
- ovsrcu_postpone(free, partition);
- }
- cmap_destroy(&cls->partitions);
-
pvector_destroy(&cls->subtables);
}
}
@@ -493,43 +486,6 @@ classifier_count(const struct classifier *cls)
return cls->n_rules;
}
-static uint32_t
-hash_metadata(ovs_be64 metadata)
-{
- return hash_uint64((OVS_FORCE uint64_t) metadata);
-}
-
-static struct cls_partition *
-find_partition(const struct classifier *cls, ovs_be64 metadata, uint32_t hash)
-{
- struct cls_partition *partition;
-
- CMAP_FOR_EACH_WITH_HASH (partition, cmap_node, hash, &cls->partitions) {
- if (partition->metadata == metadata) {
- return partition;
- }
- }
-
- return NULL;
-}
-
-static struct cls_partition *
-create_partition(struct classifier *cls, struct cls_subtable *subtable,
- ovs_be64 metadata)
-{
- uint32_t hash = hash_metadata(metadata);
- struct cls_partition *partition = find_partition(cls, metadata, hash);
- if (!partition) {
- partition = xmalloc(sizeof *partition);
- partition->metadata = metadata;
- partition->tags = 0;
- tag_tracker_init(&partition->tracker);
- cmap_insert(&cls->partitions, &partition->cmap_node, hash);
- }
- tag_tracker_add(&partition->tracker, &partition->tags, subtable->tag);
- return partition;
-}
-
static inline ovs_be32 minimatch_get_ports(const struct minimatch *match)
{
/* Could optimize to use the same map if needed for fast path. */
@@ -545,9 +501,6 @@ subtable_replace_head_rule(struct classifier *cls OVS_UNUSED,
{
/* Rule's data is already in the tries. */
- new->partition = head->partition; /* Steal partition, if any. */
- head->partition = NULL;
-
for (int i = 0; i < subtable->n_indices; i++) {
cmap_replace(&subtable->indices[i], &head->index_nodes[i],
&new->index_nodes[i], ihash[i]);
@@ -629,17 +582,6 @@ classifier_replace(struct classifier *cls, const struct cls_rule *rule,
subtable->ports_mask_len);
}
- /* Add rule to partitions.
- *
- * Concurrent readers might miss seeing the rule until this update,
- * which might require being fixed up by revalidation later. */
- new->partition = NULL;
- if (minimask_get_metadata_mask(rule->match.mask) == OVS_BE64_MAX) {
- ovs_be64 metadata = miniflow_get_metadata(rule->match.flow);
-
- new->partition = create_partition(cls, subtable, metadata);
- }
-
/* Add new node to segment indices.
*
* Readers may find the rule in the indices before the rule is visible
@@ -779,7 +721,6 @@ const struct cls_rule *
classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
{
struct cls_match *rule, *prev, *next, *head;
- struct cls_partition *partition;
struct cls_conjunction_set *conj_set;
struct cls_subtable *subtable;
int i;
@@ -858,17 +799,6 @@ classifier_remove(struct classifier *cls, const struct cls_rule *cls_rule)
}
n_rules = cmap_remove(&subtable->rules, &rule->cmap_node, hash);
- partition = rule->partition;
- if (partition) {
- tag_tracker_subtract(&partition->tracker, &partition->tags,
- subtable->tag);
- if (!partition->tags) {
- cmap_remove(&cls->partitions, &partition->cmap_node,
- hash_metadata(partition->metadata));
- ovsrcu_postpone(free, partition);
- }
- }
-
if (n_rules == 0) {
destroy_subtable(cls, subtable);
} else {
@@ -1017,11 +947,8 @@ classifier_lookup__(const struct classifier *cls, cls_version_t version,
struct flow *flow, struct flow_wildcards *wc,
bool allow_conjunctive_matches)
{
- const struct cls_partition *partition;
struct trie_ctx trie_ctx[CLS_MAX_TRIES];
const struct cls_match *match;
- tag_type tags;
-
/* Highest-priority flow in 'cls' that certainly matches 'flow'. */
const struct cls_match *hard = NULL;
int hard_pri = INT_MIN; /* hard ? hard->priority : INT_MIN. */
@@ -1040,30 +967,6 @@ classifier_lookup__(const struct classifier *cls, cls_version_t version,
* startup. */
atomic_thread_fence(memory_order_acquire);
- /* Determine 'tags' such that, if 'subtable->tag' doesn't intersect them,
- * then 'flow' cannot possibly match in 'subtable':
- *
- * - If flow->metadata maps to a given 'partition', then we can use
- * 'tags' for 'partition->tags'.
- *
- * - If flow->metadata has no partition, then no rule in 'cls' has an
- * exact-match for flow->metadata. That means that we don't need to
- * search any subtable that includes flow->metadata in its mask.
- *
- * In either case, we always need to search any cls_subtables that do not
- * include flow->metadata in its mask. One way to do that would be to
- * check the "cls_subtable"s explicitly for that, but that would require an
- * extra branch per subtable. Instead, we mark such a cls_subtable's
- * 'tags' as TAG_ALL and make sure that 'tags' is never empty. This means
- * that 'tags' always intersects such a cls_subtable's 'tags', so we don't
- * need a special case.
- */
- partition = (cmap_is_empty(&cls->partitions)
- ? NULL
- : find_partition(cls, flow->metadata,
- hash_metadata(flow->metadata)));
- tags = partition ? partition->tags : TAG_ARBITRARY;
-
/* Initialize trie contexts for find_match_wc(). */
for (int i = 0; i < cls->n_tries; i++) {
trie_ctx_init(&trie_ctx[i], &cls->tries[i]);
@@ -1075,11 +978,6 @@ classifier_lookup__(const struct classifier *cls, cls_version_t version,
&cls->subtables) {
struct cls_conjunction_set *conj_set;
- /* Skip subtables not in our partition. */
- if (!tag_intersects(tags, subtable->tag)) {
- continue;
- }
-
/* Skip subtables with no match, or where the match is lower-priority
* than some certain match we've already found. */
match = find_match_wc(subtable, version, flow, trie_ctx, cls->n_tries,
@@ -1603,11 +1501,6 @@ insert_subtable(struct classifier *cls, const struct minimask *mask)
}
*CONST_CAST(uint8_t *, &subtable->n_indices) = index;
- *CONST_CAST(tag_type *, &subtable->tag) =
- (minimask_get_metadata_mask(mask) == OVS_BE64_MAX
- ? tag_create_deterministic(hash)
- : TAG_ALL);
-
for (i = 0; i < cls->n_tries; i++) {
subtable->trie_plen[i] = minimask_get_prefix_len(mask,
cls->tries[i].field);
diff --git a/lib/tag.c b/lib/tag.c
deleted file mode 100644
index 13d1829..0000000
--- a/lib/tag.c
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * Copyright (c) 2008, 2009, 2010, 2011, 2013 Nicira, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#include <config.h>
-#include "tag.h"
-
-#define LOG2_N_TAG_BITS (N_TAG_BITS == 32 ? 5 : N_TAG_BITS == 64 ? 6 : 0)
-BUILD_ASSERT_DECL(LOG2_N_TAG_BITS > 0);
-
-/* Returns a tag deterministically generated from 'seed'.
- *
- * 'seed' should have data in all of its bits; if it has data only in its
- * low-order bits then the resulting tags will be poorly distributed. Use a
- * hash function such as hash_bytes() to generate 'seed' if necessary. */
-tag_type
-tag_create_deterministic(uint32_t seed)
-{
- int x = seed & (N_TAG_BITS - 1);
- int y = (seed >> LOG2_N_TAG_BITS) % (N_TAG_BITS - 1);
- y += y >= x;
- return (1u << x) | (1u << y);
-}
-
-/* Initializes 'tracker'. */
-void
-tag_tracker_init(struct tag_tracker *tracker)
-{
- memset(tracker, 0, sizeof *tracker);
-}
-
-/* Adds 'add' to '*tags' and records the bits added in 'tracker'. */
-void
-tag_tracker_add(struct tag_tracker *tracker, tag_type *tags, tag_type add)
-{
- *tags |= add;
- for (; add; add = zero_rightmost_1bit(add)) {
- tracker->counts[rightmost_1bit_idx(add)]++;
- }
-}
-
-/* Removes 'sub' from 'tracker' and unsets any bits in '*tags' that no
- * remaining tag includes. */
-void
-tag_tracker_subtract(struct tag_tracker *tracker, tag_type *tags, tag_type sub)
-{
- for (; sub; sub = zero_rightmost_1bit(sub)) {
- if (!--tracker->counts[rightmost_1bit_idx(sub)]) {
- *tags &= ~rightmost_1bit(sub);
- }
- }
-}
diff --git a/lib/tag.h b/lib/tag.h
deleted file mode 100644
index c99fd09..0000000
--- a/lib/tag.h
+++ /dev/null
@@ -1,100 +0,0 @@
-/*
- * Copyright (c) 2008, 2011, 2012, 2013 Nicira, Inc.
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#ifndef TAG_H
-#define TAG_H 1
-
-#include <stdbool.h>
-#include <stdint.h>
-#include <limits.h>
-#include "util.h"
-
-/*
- * Tagging support.
- *
- * A 'tag' represents an arbitrary category. Currently, tags are used to
- * represent categories of flows and in particular the value of the 64-bit
- * "metadata" field in the flow. The universe of possible categories is very
- * large (2**64). The number of categories in use at a given time can also be
- * large. This means that keeping track of category membership via
- * conventional means (lists, bitmaps, etc.) is likely to be expensive.
- *
- * Tags are actually implemented via a "superimposed coding", as discussed in
- * Knuth TAOCP v.3 section 6.5 "Retrieval on Secondary Keys". A tag is an
- * unsigned integer in which exactly 2 bits are set to 1 and the rest set to 0.
- * For 32-bit integers (as currently used) there are 32 * 31 / 2 = 496 unique
- * tags; for 64-bit integers there are 64 * 63 / 2 = 2,016.
- *
- * Because there is a small finite number of unique tags, tags must collide
- * after some number of them have been created. In practice we generally
- * create tags by choosing bits randomly or based on a hash function.
- *
- * The key property of tags is that we can combine them without increasing the
- * amount of data required using bitwise-OR, since the result has the 1-bits
- * from both tags set. The necessary tradeoff is that the result is even more
- * ambiguous: if combining two tags yields a value with 4 bits set to 1, then
- * the result value will test as having 4 * 3 / 2 = 6 unique tags, not just the
- * two tags that we combined.
- *
- * The upshot is this: a value that is the bitwise-OR combination of a number
- * of tags will always include the tags that were combined, but it may contain
- * any number of additional tags as well. This is acceptable for our use,
- * since we want to be sure that we check every classifier table that contains
- * a rule with a given metadata value, but it is OK if we check a few extra
- * tables as well.
- *
- * If we combine too many tags, then the result will have every bit set, so
- * that it will test as including every tag. This can happen, but we hope that
- * this is not the common case.
- */
-
-/* Represents a tag, or the combination of 0 or more tags. */
-typedef uint32_t tag_type;
-
-#define N_TAG_BITS (CHAR_BIT * sizeof(tag_type))
-BUILD_ASSERT_DECL(IS_POW2(N_TAG_BITS));
-
-/* A 'tag_type' value that intersects every tag. */
-#define TAG_ALL UINT32_MAX
-
-/* An arbitrary tag. */
-#define TAG_ARBITRARY UINT32_C(3)
-
-tag_type tag_create_deterministic(uint32_t seed);
-static inline bool tag_intersects(tag_type, tag_type);
-
-/* Returns true if 'a' and 'b' have at least one tag in common,
- * false if their set of tags is disjoint. */
-static inline bool
-tag_intersects(tag_type a, tag_type b)
-{
- tag_type x = a & b;
- return (x & (x - 1)) != 0;
-}
-
-/* Adding tags is easy, but subtracting is hard because you can't tell whether
- * a bit was set only by the tag you're removing or by multiple tags. The
- * tag_tracker data structure counts the number of tags that set each bit,
- * which allows for efficient subtraction. */
-struct tag_tracker {
- unsigned int counts[N_TAG_BITS];
-};
-
-void tag_tracker_init(struct tag_tracker *);
-void tag_tracker_add(struct tag_tracker *, tag_type *, tag_type);
-void tag_tracker_subtract(struct tag_tracker *, tag_type *, tag_type);
-
-#endif /* tag.h */
--
2.1.4
More information about the dev
mailing list